hivex/hivex.c

   1 /* hivex - Windows Registry "hive" extraction library.
   2  * Copyright (C) 2009-2010 Red Hat Inc.
   3  * Derived from code by Petter Nordahl-Hagen under a compatible license:
   4  *   Copyright (c) 1997-2007 Petter Nordahl-Hagen.
   5  * Derived from code by Markus Stephany under a compatible license:
   6  *   Copyright (c) 2000-2004, Markus Stephany.
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation;
  11  * version 2.1 of the License.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * See file LICENSE for the full license.
  19  */
  20
  21 #include <config.h>
  22
  23 #include <stdio.h>
  24 #include <stdlib.h>
  25 #include <stdint.h>
  26 #include <stddef.h>
  27 #include <inttypes.h>
  28 #include <string.h>
  29 #include <fcntl.h>
  30 #include <unistd.h>
  31 #include <errno.h>
  32 #include <iconv.h>
  33 #include <sys/mman.h>
  34 #include <sys/stat.h>
  35 #include <assert.h>
  36
  37 #include "c-ctype.h"
  38 #include "full-read.h"
  39 #include "full-write.h"
  40
  41 #ifndef O_CLOEXEC
  42 #define O_CLOEXEC 0
  43 #endif
  44
  45 #define STREQ(a,b) (strcmp((a),(b)) == 0)
  46 #define STRCASEEQ(a,b) (strcasecmp((a),(b)) == 0)
  47 //#define STRNEQ(a,b) (strcmp((a),(b)) != 0)
  48 //#define STRCASENEQ(a,b) (strcasecmp((a),(b)) != 0)
  49 #define STREQLEN(a,b,n) (strncmp((a),(b),(n)) == 0)
  50 //#define STRCASEEQLEN(a,b,n) (strncasecmp((a),(b),(n)) == 0)
  51 //#define STRNEQLEN(a,b,n) (strncmp((a),(b),(n)) != 0)
  52 //#define STRCASENEQLEN(a,b,n) (strncasecmp((a),(b),(n)) != 0)
  53 #define STRPREFIX(a,b) (strncmp((a),(b),strlen((b))) == 0)
  54
  55 #include "hivex.h"
  56 #include "byte_conversions.h"
  57
  58 /* These limits are in place to stop really stupid stuff and/or exploits. */
  59 #define HIVEX_MAX_SUBKEYS       10000
  60 #define HIVEX_MAX_VALUES         1000
  61 #define HIVEX_MAX_VALUE_LEN   1000000
  62 #define HIVEX_MAX_ALLOCATION  1000000
  63
  64 static char *windows_utf16_to_utf8 (/* const */ char *input, size_t len);
  65
  66 struct hive_h {
  67   char *filename;
  68   int fd;
  69   size_t size;
  70   int msglvl;
  71   int writable;
  72
  73   /* Registry file, memory mapped if read-only, or malloc'd if writing. */
  74   union {
  75     char *addr;
  76     struct ntreg_header *hdr;
  77   };
  78
  79   /* Use a bitmap to store which file offsets are valid (point to a
  80    * used block).  We only need to store 1 bit per 32 bits of the file
  81    * (because blocks are 4-byte aligned).  We found that the average
  82    * block size in a registry file is ~50 bytes.  So roughly 1 in 12
  83    * bits in the bitmap will be set, making it likely a more efficient
  84    * structure than a hash table.
  85    */
  86   char *bitmap;
  87 #define BITMAP_SET(bitmap,off) (bitmap[(off)>>5] |= 1 << (((off)>>2)&7))
  88 #define BITMAP_CLR(bitmap,off) (bitmap[(off)>>5] &= ~ (1 << (((off)>>2)&7)))
  89 #define BITMAP_TST(bitmap,off) (bitmap[(off)>>5] & (1 << (((off)>>2)&7)))
  90 #define IS_VALID_BLOCK(h,off)               \
  91   (((off) & 3) == 0 &&                      \
  92    (off) >= 0x1000 &&                       \
  93    (off) < (h)->size &&                     \
  94    BITMAP_TST((h)->bitmap,(off)))
  95
  96   /* Fields from the header, extracted from little-endianness hell. */
  97   size_t rootoffs;              /* Root key offset (always an nk-block). */
  98   size_t endpages;              /* Offset of end of pages. */
  99
 100   /* For writing. */
 101   size_t endblocks;             /* Offset to next block allocation (0
 102                                    if not allocated anything yet). */
 103 };
 104
 105 /* NB. All fields are little endian. */
 106 struct ntreg_header {
 107   char magic[4];                /* "regf" */
 108   uint32_t sequence1;
 109   uint32_t sequence2;
 110   char last_modified[8];
 111   uint32_t major_ver;           /* 1 */
 112   uint32_t minor_ver;           /* 3 */
 113   uint32_t unknown5;            /* 0 */
 114   uint32_t unknown6;            /* 1 */
 115   uint32_t offset;              /* offset of root key record - 4KB */
 116   uint32_t blocks;              /* pointer AFTER last hbin in file - 4KB */
 117   uint32_t unknown7;            /* 1 */
 118   /* 0x30 */
 119   char name[64];                /* original file name of hive */
 120   char unknown_guid1[16];
 121   char unknown_guid2[16];
 122   /* 0x90 */
 123   uint32_t unknown8;
 124   char unknown_guid3[16];
 125   uint32_t unknown9;
 126   /* 0xa8 */
 127   char unknown10[340];
 128   /* 0x1fc */
 129   uint32_t csum;                /* checksum: xor of dwords 0-0x1fb. */
 130   /* 0x200 */
 131   char unknown11[3528];
 132   /* 0xfc8 */
 133   char unknown_guid4[16];
 134   char unknown_guid5[16];
 135   char unknown_guid6[16];
 136   uint32_t unknown12;
 137   uint32_t unknown13;
 138   /* 0x1000 */
 139 } __attribute__((__packed__));
 140
 141 struct ntreg_hbin_page {
 142   char magic[4];                /* "hbin" */
 143   uint32_t offset_first;        /* offset from 1st block */
 144   uint32_t page_size;           /* size of this page (multiple of 4KB) */
 145   char unknown[20];
 146   /* Linked list of blocks follows here. */
 147 } __attribute__((__packed__));
 148
 149 struct ntreg_hbin_block {
 150   int32_t seg_len;              /* length of this block (-ve for used block) */
 151   char id[2];                   /* the block type (eg. "nk" for nk record) */
 152   /* Block data follows here. */
 153 } __attribute__((__packed__));
 154
 155 #define BLOCK_ID_EQ(h,offs,eqid) \
 156   (STREQLEN (((struct ntreg_hbin_block *)((h)->addr + (offs)))->id, (eqid), 2))
 157
 158 static size_t
 159 block_len (hive_h *h, size_t blkoff, int *used)
 160 {
 161   struct ntreg_hbin_block *block;
 162   block = (struct ntreg_hbin_block *) (h->addr + blkoff);
 163
 164   int32_t len = le32toh (block->seg_len);
 165   if (len < 0) {
 166     if (used) *used = 1;
 167     len = -len;
 168   } else {
 169     if (used) *used = 0;
 170   }
 171
 172   return (size_t) len;
 173 }
 174
 175 struct ntreg_nk_record {
 176   int32_t seg_len;              /* length (always -ve because used) */
 177   char id[2];                   /* "nk" */
 178   uint16_t flags;
 179   char timestamp[8];
 180   uint32_t unknown1;
 181   uint32_t parent;              /* offset of owner/parent */
 182   uint32_t nr_subkeys;          /* number of subkeys */
 183   uint32_t nr_subkeys_volatile;
 184   uint32_t subkey_lf;           /* lf record containing list of subkeys */
 185   uint32_t subkey_lf_volatile;
 186   uint32_t nr_values;           /* number of values */
 187   uint32_t vallist;             /* value-list record */
 188   uint32_t sk;                  /* offset of sk-record */
 189   uint32_t classname;           /* offset of classname record */
 190   uint16_t max_subkey_name_len; /* maximum length of a subkey name in bytes
 191                                    if the subkey was reencoded as UTF-16LE */
 192   uint16_t unknown2;
 193   uint32_t unknown3;
 194   uint32_t max_vk_name_len;     /* maximum length of any vk name in bytes
 195                                    if the name was reencoded as UTF-16LE */
 196   uint32_t max_vk_data_len;     /* maximum length of any vk data in bytes */
 197   uint32_t unknown6;
 198   uint16_t name_len;            /* length of name */
 199   uint16_t classname_len;       /* length of classname */
 200   char name[1];                 /* name follows here */
 201 } __attribute__((__packed__));
 202
 203 struct ntreg_lf_record {
 204   int32_t seg_len;
 205   char id[2];                   /* "lf"|"lh" */
 206   uint16_t nr_keys;             /* number of keys in this record */
 207   struct {
 208     uint32_t offset;            /* offset of nk-record for this subkey */
 209     char hash[4];               /* hash of subkey name */
 210   } keys[1];
 211 } __attribute__((__packed__));
 212
 213 struct ntreg_ri_record {
 214   int32_t seg_len;
 215   char id[2];                   /* "ri" */
 216   uint16_t nr_offsets;          /* number of pointers to lh records */
 217   uint32_t offset[1];           /* list of pointers to lh records */
 218 } __attribute__((__packed__));
 219
 220 /* This has no ID header. */
 221 struct ntreg_value_list {
 222   int32_t seg_len;
 223   uint32_t offset[1];           /* list of pointers to vk records */
 224 } __attribute__((__packed__));
 225
 226 struct ntreg_vk_record {
 227   int32_t seg_len;              /* length (always -ve because used) */
 228   char id[2];                   /* "vk" */
 229   uint16_t name_len;            /* length of name */
 230   /* length of the data:
 231    * If data_len is <= 4, then it's stored inline.
 232    * If data_len is 0x80000000, then it's an inline dword.
 233    * Top bit may be set or not set at random.
 234    */
 235   uint32_t data_len;
 236   uint32_t data_offset;         /* pointer to the data (or data if inline) */
 237   uint32_t data_type;           /* type of the data */
 238   uint16_t flags;               /* bit 0 set => key name ASCII,
 239                                    bit 0 clr => key name UTF-16.
 240                                    Only seen ASCII here in the wild.
 241                                    NB: this is CLEAR for default key. */
 242   uint16_t unknown2;
 243   char name[1];                 /* key name follows here */
 244 } __attribute__((__packed__));
 245
 246 struct ntreg_sk_record {
 247   int32_t seg_len;              /* length (always -ve because used) */
 248   char id[2];                   /* "sk" */
 249   uint16_t unknown1;
 250   uint32_t sk_next;             /* linked into a circular list */
 251   uint32_t sk_prev;
 252   uint32_t refcount;            /* reference count */
 253   uint32_t sec_len;             /* length of security info */
 254   char sec_desc[1];             /* security info follows */
 255 } __attribute__((__packed__));
 256
 257 static uint32_t
 258 header_checksum (const hive_h *h)
 259 {
 260   uint32_t *daddr = (uint32_t *) h->addr;
 261   size_t i;
 262   uint32_t sum = 0;
 263
 264   for (i = 0; i < 0x1fc / 4; ++i) {
 265     sum ^= le32toh (*daddr);
 266     daddr++;
 267   }
 268
 269   return sum;
 270 }
 271
 272 hive_h *
 273 hivex_open (const char *filename, int flags)
 274 {
 275   hive_h *h = NULL;
 276
 277   assert (sizeof (struct ntreg_header) == 0x1000);
 278   assert (offsetof (struct ntreg_header, csum) == 0x1fc);
 279
 280   h = calloc (1, sizeof *h);
 281   if (h == NULL)
 282     goto error;
 283
 284   h->msglvl = flags & HIVEX_OPEN_MSGLVL_MASK;
 285
 286   const char *debug = getenv ("HIVEX_DEBUG");
 287   if (debug && STREQ (debug, "1"))
 288     h->msglvl = 2;
 289
 290   if (h->msglvl >= 2)
 291     fprintf (stderr, "hivex_open: created handle %p\n", h);
 292
 293   h->writable = !!(flags & HIVEX_OPEN_WRITE);
 294   h->filename = strdup (filename);
 295   if (h->filename == NULL)
 296     goto error;
 297
 298   h->fd = open (filename, O_RDONLY | O_CLOEXEC);
 299   if (h->fd == -1)
 300     goto error;
 301
 302   struct stat statbuf;
 303   if (fstat (h->fd, &statbuf) == -1)
 304     goto error;
 305
 306   h->size = statbuf.st_size;
 307
 308   if (!h->writable) {
 309     h->addr = mmap (NULL, h->size, PROT_READ, MAP_SHARED, h->fd, 0);
 310     if (h->addr == MAP_FAILED)
 311       goto error;
 312
 313     if (h->msglvl >= 2)
 314       fprintf (stderr, "hivex_open: mapped file at %p\n", h->addr);
 315   } else {
 316     h->addr = malloc (h->size);
 317     if (h->addr == NULL)
 318       goto error;
 319
 320     if (full_read (h->fd, h->addr, h->size) < h->size)
 321       goto error;
 322   }
 323
 324   /* Check header. */
 325   if (h->hdr->magic[0] != 'r' ||
 326       h->hdr->magic[1] != 'e' ||
 327       h->hdr->magic[2] != 'g' ||
 328       h->hdr->magic[3] != 'f') {
 329     fprintf (stderr, "hivex: %s: not a Windows NT Registry hive file\n",
 330              filename);
 331     errno = ENOTSUP;
 332     goto error;
 333   }
 334
 335   /* Check major version. */
 336   uint32_t major_ver = le32toh (h->hdr->major_ver);
 337   if (major_ver != 1) {
 338     fprintf (stderr,
 339              "hivex: %s: hive file major version %" PRIu32 " (expected 1)\n",
 340              filename, major_ver);
 341     errno = ENOTSUP;
 342     goto error;
 343   }
 344
 345   h->bitmap = calloc (1 + h->size / 32, 1);
 346   if (h->bitmap == NULL)
 347     goto error;
 348
 349   /* Header checksum. */
 350   uint32_t sum = header_checksum (h);
 351   if (sum != le32toh (h->hdr->csum)) {
 352     fprintf (stderr, "hivex: %s: bad checksum in hive header\n", filename);
 353     errno = EINVAL;
 354     goto error;
 355   }
 356
 357   if (h->msglvl >= 2) {
 358     char *name = windows_utf16_to_utf8 (h->hdr->name, 64);
 359
 360     fprintf (stderr,
 361              "hivex_open: header fields:\n"
 362              "  file version             %" PRIu32 ".%" PRIu32 "\n"
 363              "  sequence nos             %" PRIu32 " %" PRIu32 "\n"
 364              "    (sequences nos should match if hive was synched at shutdown)\n"
 365              "  original file name       %s\n"
 366              "    (only 32 chars are stored, name is probably truncated)\n"
 367              "  root offset              0x%x + 0x1000\n"
 368              "  end of last page         0x%x + 0x1000 (total file size 0x%zx)\n"
 369              "  checksum                 0x%x (calculated 0x%x)\n",
 370              major_ver, le32toh (h->hdr->minor_ver),
 371              le32toh (h->hdr->sequence1), le32toh (h->hdr->sequence2),
 372              name ? name : "(conversion failed)",
 373              le32toh (h->hdr->offset),
 374              le32toh (h->hdr->blocks), h->size,
 375              le32toh (h->hdr->csum), sum);
 376     free (name);
 377   }
 378
 379   h->rootoffs = le32toh (h->hdr->offset) + 0x1000;
 380   h->endpages = le32toh (h->hdr->blocks) + 0x1000;
 381
 382   if (h->msglvl >= 2)
 383     fprintf (stderr, "hivex_open: root offset = 0x%zx\n", h->rootoffs);
 384
 385   /* We'll set this flag when we see a block with the root offset (ie.
 386    * the root block).
 387    */
 388   int seen_root_block = 0, bad_root_block = 0;
 389
 390   /* Collect some stats. */
 391   size_t pages = 0;           /* Number of hbin pages read. */
 392   size_t smallest_page = SIZE_MAX, largest_page = 0;
 393   size_t blocks = 0;          /* Total number of blocks found. */
 394   size_t smallest_block = SIZE_MAX, largest_block = 0, blocks_bytes = 0;
 395   size_t used_blocks = 0;     /* Total number of used blocks found. */
 396   size_t used_size = 0;       /* Total size (bytes) of used blocks. */
 397
 398   /* Read the pages and blocks.  The aim here is to be robust against
 399    * corrupt or malicious registries.  So we make sure the loops
 400    * always make forward progress.  We add the address of each block
 401    * we read to a hash table so pointers will only reference the start
 402    * of valid blocks.
 403    */
 404   size_t off;
 405   struct ntreg_hbin_page *page;
 406   for (off = 0x1000; off < h->size; off += le32toh (page->page_size)) {
 407     if (off >= h->endpages)
 408       break;
 409
 410     page = (struct ntreg_hbin_page *) (h->addr + off);
 411     if (page->magic[0] != 'h' ||
 412         page->magic[1] != 'b' ||
 413         page->magic[2] != 'i' ||
 414         page->magic[3] != 'n') {
 415       fprintf (stderr, "hivex: %s: trailing garbage at end of file (at 0x%zx, after %zu pages)\n",
 416                filename, off, pages);
 417       errno = ENOTSUP;
 418       goto error;
 419     }
 420
 421     size_t page_size = le32toh (page->page_size);
 422     if (h->msglvl >= 2)
 423       fprintf (stderr, "hivex_open: page at 0x%zx, size %zu\n", off, page_size);
 424     pages++;
 425     if (page_size < smallest_page) smallest_page = page_size;
 426     if (page_size > largest_page) largest_page = page_size;
 427
 428     if (page_size <= sizeof (struct ntreg_hbin_page) ||
 429         (page_size & 0x0fff) != 0) {
 430       fprintf (stderr, "hivex: %s: page size %zu at 0x%zx, bad registry\n",
 431                filename, page_size, off);
 432       errno = ENOTSUP;
 433       goto error;
 434     }
 435
 436     /* Read the blocks in this page. */
 437     size_t blkoff;
 438     struct ntreg_hbin_block *block;
 439     size_t seg_len;
 440     for (blkoff = off + 0x20;
 441          blkoff < off + page_size;
 442          blkoff += seg_len) {
 443       blocks++;
 444
 445       int is_root = blkoff == h->rootoffs;
 446       if (is_root)
 447         seen_root_block = 1;
 448
 449       block = (struct ntreg_hbin_block *) (h->addr + blkoff);
 450       int used;
 451       seg_len = block_len (h, blkoff, &used);
 452       if (seg_len <= 4 || (seg_len & 3) != 0) {
 453         fprintf (stderr, "hivex: %s: block size %" PRIu32 " at 0x%zx, bad registry\n",
 454                  filename, le32toh (block->seg_len), blkoff);
 455         errno = ENOTSUP;
 456         goto error;
 457       }
 458
 459       if (h->msglvl >= 2)
 460         fprintf (stderr, "hivex_open: %s block id %d,%d at 0x%zx size %zu%s\n",
 461                  used ? "used" : "free", block->id[0], block->id[1], blkoff,
 462                  seg_len, is_root ? " (root)" : "");
 463
 464       blocks_bytes += seg_len;
 465       if (seg_len < smallest_block) smallest_block = seg_len;
 466       if (seg_len > largest_block) largest_block = seg_len;
 467
 468       if (is_root && !used)
 469         bad_root_block = 1;
 470
 471       if (used) {
 472         used_blocks++;
 473         used_size += seg_len;
 474
 475         /* Root block must be an nk-block. */
 476         if (is_root && (block->id[0] != 'n' || block->id[1] != 'k'))
 477           bad_root_block = 1;
 478
 479         /* Note this blkoff is a valid address. */
 480         BITMAP_SET (h->bitmap, blkoff);
 481       }
 482     }
 483   }
 484
 485   if (!seen_root_block) {
 486     fprintf (stderr, "hivex: %s: no root block found\n", filename);
 487     errno = ENOTSUP;
 488     goto error;
 489   }
 490
 491   if (bad_root_block) {
 492     fprintf (stderr, "hivex: %s: bad root block (free or not nk)\n", filename);
 493     errno = ENOTSUP;
 494     goto error;
 495   }
 496
 497   if (h->msglvl >= 1)
 498     fprintf (stderr,
 499              "hivex_open: successfully read Windows Registry hive file:\n"
 500              "  pages:          %zu [sml: %zu, lge: %zu]\n"
 501              "  blocks:         %zu [sml: %zu, avg: %zu, lge: %zu]\n"
 502              "  blocks used:    %zu\n"
 503              "  bytes used:     %zu\n",
 504              pages, smallest_page, largest_page,
 505              blocks, smallest_block, blocks_bytes / blocks, largest_block,
 506              used_blocks, used_size);
 507
 508   return h;
 509
 510  error:;
 511   int err = errno;
 512   if (h) {
 513     free (h->bitmap);
 514     if (h->addr && h->size && h->addr != MAP_FAILED) {
 515       if (!h->writable)
 516         munmap (h->addr, h->size);
 517       else
 518         free (h->addr);
 519     }
 520     if (h->fd >= 0)
 521       close (h->fd);
 522     free (h->filename);
 523     free (h);
 524   }
 525   errno = err;
 526   return NULL;
 527 }
 528
 529 int
 530 hivex_close (hive_h *h)
 531 {
 532   int r;
 533
 534   free (h->bitmap);
 535   if (!h->writable)
 536     munmap (h->addr, h->size);
 537   else
 538     free (h->addr);
 539   r = close (h->fd);
 540   free (h->filename);
 541   free (h);
 542
 543   return r;
 544 }
 545
 546 /*----------------------------------------------------------------------
 547  * Reading.
 548  */
 549
 550 hive_node_h
 551 hivex_root (hive_h *h)
 552 {
 553   hive_node_h ret = h->rootoffs;
 554   if (!IS_VALID_BLOCK (h, ret)) {
 555     errno = ENOKEY;
 556     return 0;
 557   }
 558   return ret;
 559 }
 560
 561 char *
 562 hivex_node_name (hive_h *h, hive_node_h node)
 563 {
 564   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
 565     errno = EINVAL;
 566     return NULL;
 567   }
 568
 569   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
 570
 571   /* AFAIK the node name is always plain ASCII, so no conversion
 572    * to UTF-8 is necessary.  However we do need to nul-terminate
 573    * the string.
 574    */
 575
 576   /* nk->name_len is unsigned, 16 bit, so this is safe ...  However
 577    * we have to make sure the length doesn't exceed the block length.
 578    */
 579   size_t len = le16toh (nk->name_len);
 580   size_t seg_len = block_len (h, node, NULL);
 581   if (sizeof (struct ntreg_nk_record) + len - 1 > seg_len) {
 582     if (h->msglvl >= 2)
 583       fprintf (stderr, "hivex_node_name: returning EFAULT because node name is too long (%zu, %zu)\n",
 584               len, seg_len);
 585     errno = EFAULT;
 586     return NULL;
 587   }
 588
 589   char *ret = malloc (len + 1);
 590   if (ret == NULL)
 591     return NULL;
 592   memcpy (ret, nk->name, len);
 593   ret[len] = '\0';
 594   return ret;
 595 }
 596
 597 #if 0
 598 /* I think the documentation for the sk and classname fields in the nk
 599  * record is wrong, or else the offset field is in the wrong place.
 600  * Otherwise this makes no sense.  Disabled this for now -- it's not
 601  * useful for reading the registry anyway.
 602  */
 603
 604 hive_security_h
 605 hivex_node_security (hive_h *h, hive_node_h node)
 606 {
 607   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
 608     errno = EINVAL;
 609     return 0;
 610   }
 611
 612   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
 613
 614   hive_node_h ret = le32toh (nk->sk);
 615   ret += 0x1000;
 616   if (!IS_VALID_BLOCK (h, ret)) {
 617     errno = EFAULT;
 618     return 0;
 619   }
 620   return ret;
 621 }
 622
 623 hive_classname_h
 624 hivex_node_classname (hive_h *h, hive_node_h node)
 625 {
 626   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
 627     errno = EINVAL;
 628     return 0;
 629   }
 630
 631   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
 632
 633   hive_node_h ret = le32toh (nk->classname);
 634   ret += 0x1000;
 635   if (!IS_VALID_BLOCK (h, ret)) {
 636     errno = EFAULT;
 637     return 0;
 638   }
 639   return ret;
 640 }
 641 #endif
 642
 643 /* Structure for returning 0-terminated lists of offsets (nodes,
 644  * values, etc).
 645  */
 646 struct offset_list {
 647   size_t *offsets;
 648   size_t len;
 649   size_t alloc;
 650 };
 651
 652 static void
 653 init_offset_list (struct offset_list *list)
 654 {
 655   list->len = 0;
 656   list->alloc = 0;
 657   list->offsets = NULL;
 658 }
 659
 660 #define INIT_OFFSET_LIST(name) \
 661   struct offset_list name; \
 662   init_offset_list (&name)
 663
 664 /* Preallocates the offset_list, but doesn't make the contents longer. */
 665 static int
 666 grow_offset_list (struct offset_list *list, size_t alloc)
 667 {
 668   assert (alloc >= list->len);
 669   size_t *p = realloc (list->offsets, alloc * sizeof (size_t));
 670   if (p == NULL)
 671     return -1;
 672   list->offsets = p;
 673   list->alloc = alloc;
 674   return 0;
 675 }
 676
 677 static int
 678 add_to_offset_list (struct offset_list *list, size_t offset)
 679 {
 680   if (list->len >= list->alloc) {
 681     if (grow_offset_list (list, list->alloc ? list->alloc * 2 : 4) == -1)
 682       return -1;
 683   }
 684   list->offsets[list->len] = offset;
 685   list->len++;
 686   return 0;
 687 }
 688
 689 static void
 690 free_offset_list (struct offset_list *list)
 691 {
 692   free (list->offsets);
 693 }
 694
 695 static size_t *
 696 return_offset_list (struct offset_list *list)
 697 {
 698   if (add_to_offset_list (list, 0) == -1)
 699     return NULL;
 700   return list->offsets;         /* caller frees */
 701 }
 702
 703 /* Iterate over children, returning child nodes and intermediate blocks. */
 704 #define GET_CHILDREN_NO_CHECK_NK 1
 705
 706 static int
 707 get_children (hive_h *h, hive_node_h node,
 708               hive_node_h **children_ret, size_t **blocks_ret,
 709               int flags)
 710 {
 711   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
 712     errno = EINVAL;
 713     return -1;
 714   }
 715
 716   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
 717
 718   size_t nr_subkeys_in_nk = le32toh (nk->nr_subkeys);
 719
 720   INIT_OFFSET_LIST (children);
 721   INIT_OFFSET_LIST (blocks);
 722
 723   /* Deal with the common "no subkeys" case quickly. */
 724   if (nr_subkeys_in_nk == 0)
 725     goto ok;
 726
 727   /* Arbitrarily limit the number of subkeys we will ever deal with. */
 728   if (nr_subkeys_in_nk > HIVEX_MAX_SUBKEYS) {
 729     errno = ERANGE;
 730     goto error;
 731   }
 732
 733   /* Preallocate space for the children. */
 734   if (grow_offset_list (&children, nr_subkeys_in_nk) == -1)
 735     goto error;
 736
 737   /* The subkey_lf field can point either to an lf-record, which is
 738    * the common case, or if there are lots of subkeys, to an
 739    * ri-record.
 740    */
 741   size_t subkey_lf = le32toh (nk->subkey_lf);
 742   subkey_lf += 0x1000;
 743   if (!IS_VALID_BLOCK (h, subkey_lf)) {
 744     if (h->msglvl >= 2)
 745       fprintf (stderr, "hivex_node_children: returning EFAULT because subkey_lf is not a valid block (0x%zx)\n",
 746                subkey_lf);
 747     errno = EFAULT;
 748     goto error;
 749   }
 750
 751   if (add_to_offset_list (&blocks, subkey_lf) == -1)
 752     goto error;
 753
 754   struct ntreg_hbin_block *block =
 755     (struct ntreg_hbin_block *) (h->addr + subkey_lf);
 756
 757   /* Points to lf-record?  (Note, also "lh" but that is basically the
 758    * same as "lf" as far as we are concerned here).
 759    */
 760   if (block->id[0] == 'l' && (block->id[1] == 'f' || block->id[1] == 'h')) {
 761     struct ntreg_lf_record *lf = (struct ntreg_lf_record *) block;
 762
 763     /* Check number of subkeys in the nk-record matches number of subkeys
 764      * in the lf-record.
 765      */
 766     size_t nr_subkeys_in_lf = le16toh (lf->nr_keys);
 767
 768     if (h->msglvl >= 2)
 769       fprintf (stderr, "hivex_node_children: nr_subkeys_in_nk = %zu, nr_subkeys_in_lf = %zu\n",
 770                nr_subkeys_in_nk, nr_subkeys_in_lf);
 771
 772     if (nr_subkeys_in_nk != nr_subkeys_in_lf) {
 773       errno = ENOTSUP;
 774       goto error;
 775     }
 776
 777     size_t len = block_len (h, subkey_lf, NULL);
 778     if (8 + nr_subkeys_in_lf * 8 > len) {
 779       if (h->msglvl >= 2)
 780         fprintf (stderr, "hivex_node_children: returning EFAULT because too many subkeys (%zu, %zu)\n",
 781                  nr_subkeys_in_lf, len);
 782       errno = EFAULT;
 783       goto error;
 784     }
 785
 786     size_t i;
 787     for (i = 0; i < nr_subkeys_in_lf; ++i) {
 788       hive_node_h subkey = le32toh (lf->keys[i].offset);
 789       subkey += 0x1000;
 790       if (!(flags & GET_CHILDREN_NO_CHECK_NK)) {
 791         if (!IS_VALID_BLOCK (h, subkey)) {
 792           if (h->msglvl >= 2)
 793             fprintf (stderr, "hivex_node_children: returning EFAULT because subkey is not a valid block (0x%zx)\n",
 794                      subkey);
 795           errno = EFAULT;
 796           goto error;
 797         }
 798       }
 799       if (add_to_offset_list (&children, subkey) == -1)
 800         goto error;
 801     }
 802     goto ok;
 803   }
 804   /* Points to ri-record? */
 805   else if (block->id[0] == 'r' && block->id[1] == 'i') {
 806     struct ntreg_ri_record *ri = (struct ntreg_ri_record *) block;
 807
 808     size_t nr_offsets = le16toh (ri->nr_offsets);
 809
 810     /* Count total number of children. */
 811     size_t i, count = 0;
 812     for (i = 0; i < nr_offsets; ++i) {
 813       hive_node_h offset = le32toh (ri->offset[i]);
 814       offset += 0x1000;
 815       if (!IS_VALID_BLOCK (h, offset)) {
 816         if (h->msglvl >= 2)
 817           fprintf (stderr, "hivex_node_children: returning EFAULT because ri-offset is not a valid block (0x%zx)\n",
 818                    offset);
 819         errno = EFAULT;
 820         goto error;
 821       }
 822       if (!BLOCK_ID_EQ (h, offset, "lf") && !BLOCK_ID_EQ (h, offset, "lh")) {
 823         if (h->msglvl >= 2)
 824           fprintf (stderr, "get_children: returning ENOTSUP because ri-record offset does not point to lf/lh (0x%zx)\n",
 825                    offset);
 826         errno = ENOTSUP;
 827         goto error;
 828       }
 829
 830       if (add_to_offset_list (&blocks, offset) == -1)
 831         goto error;
 832
 833       struct ntreg_lf_record *lf =
 834         (struct ntreg_lf_record *) (h->addr + offset);
 835
 836       count += le16toh (lf->nr_keys);
 837     }
 838
 839     if (h->msglvl >= 2)
 840       fprintf (stderr, "hivex_node_children: nr_subkeys_in_nk = %zu, counted = %zu\n",
 841                nr_subkeys_in_nk, count);
 842
 843     if (nr_subkeys_in_nk != count) {
 844       errno = ENOTSUP;
 845       goto error;
 846     }
 847
 848     /* Copy list of children.  Note nr_subkeys_in_nk is limited to
 849      * something reasonable above.
 850      */
 851     for (i = 0; i < nr_offsets; ++i) {
 852       hive_node_h offset = le32toh (ri->offset[i]);
 853       offset += 0x1000;
 854       if (!IS_VALID_BLOCK (h, offset)) {
 855         if (h->msglvl >= 2)
 856           fprintf (stderr, "hivex_node_children: returning EFAULT because ri-offset is not a valid block (0x%zx)\n",
 857                    offset);
 858         errno = EFAULT;
 859         goto error;
 860       }
 861       if (!BLOCK_ID_EQ (h, offset, "lf") && !BLOCK_ID_EQ (h, offset, "lh")) {
 862         if (h->msglvl >= 2)
 863           fprintf (stderr, "get_children: returning ENOTSUP because ri-record offset does not point to lf/lh (0x%zx)\n",
 864                    offset);
 865         errno = ENOTSUP;
 866         goto error;
 867       }
 868
 869       struct ntreg_lf_record *lf =
 870         (struct ntreg_lf_record *) (h->addr + offset);
 871
 872       size_t j;
 873       for (j = 0; j < le16toh (lf->nr_keys); ++j) {
 874         hive_node_h subkey = le32toh (lf->keys[j].offset);
 875         subkey += 0x1000;
 876         if (!(flags & GET_CHILDREN_NO_CHECK_NK)) {
 877           if (!IS_VALID_BLOCK (h, subkey)) {
 878             if (h->msglvl >= 2)
 879               fprintf (stderr, "hivex_node_children: returning EFAULT because indirect subkey is not a valid block (0x%zx)\n",
 880                        subkey);
 881             errno = EFAULT;
 882             goto error;
 883           }
 884         }
 885         if (add_to_offset_list (&children, subkey) == -1)
 886           goto error;
 887       }
 888     }
 889     goto ok;
 890   }
 891   /* else not supported, set errno and fall through */
 892   if (h->msglvl >= 2)
 893     fprintf (stderr, "get_children: returning ENOTSUP because subkey block is not lf/lh/ri (0x%zx, %d, %d)\n",
 894              subkey_lf, block->id[0], block->id[1]);
 895   errno = ENOTSUP;
 896  error:
 897   free_offset_list (&children);
 898   free_offset_list (&blocks);
 899   return -1;
 900
 901  ok:
 902   *children_ret = return_offset_list (&children);
 903   *blocks_ret = return_offset_list (&blocks);
 904   if (!*children_ret || !*blocks_ret)
 905     goto error;
 906   return 0;
 907 }
 908
 909 hive_node_h *
 910 hivex_node_children (hive_h *h, hive_node_h node)
 911 {
 912   hive_node_h *children;
 913   size_t *blocks;
 914
 915   if (get_children (h, node, &children, &blocks, 0) == -1)
 916     return NULL;
 917
 918   free (blocks);
 919   return children;
 920 }
 921
 922 /* Very inefficient, but at least having a separate API call
 923  * allows us to make it more efficient in future.
 924  */
 925 hive_node_h
 926 hivex_node_get_child (hive_h *h, hive_node_h node, const char *nname)
 927 {
 928   hive_node_h *children = NULL;
 929   char *name = NULL;
 930   hive_node_h ret = 0;
 931
 932   children = hivex_node_children (h, node);
 933   if (!children) goto error;
 934
 935   size_t i;
 936   for (i = 0; children[i] != 0; ++i) {
 937     name = hivex_node_name (h, children[i]);
 938     if (!name) goto error;
 939     if (STRCASEEQ (name, nname)) {
 940       ret = children[i];
 941       break;
 942     }
 943     free (name); name = NULL;
 944   }
 945
 946  error:
 947   free (children);
 948   free (name);
 949   return ret;
 950 }
 951
 952 hive_node_h
 953 hivex_node_parent (hive_h *h, hive_node_h node)
 954 {
 955   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
 956     errno = EINVAL;
 957     return 0;
 958   }
 959
 960   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
 961
 962   hive_node_h ret = le32toh (nk->parent);
 963   ret += 0x1000;
 964   if (!IS_VALID_BLOCK (h, ret)) {
 965     if (h->msglvl >= 2)
 966       fprintf (stderr, "hivex_node_parent: returning EFAULT because parent is not a valid block (0x%zx)\n",
 967               ret);
 968     errno = EFAULT;
 969     return 0;
 970   }
 971   return ret;
 972 }
 973
 974 static int
 975 get_values (hive_h *h, hive_node_h node,
 976             hive_value_h **values_ret, size_t **blocks_ret)
 977 {
 978   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
 979     errno = EINVAL;
 980     return -1;
 981   }
 982
 983   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
 984
 985   size_t nr_values = le32toh (nk->nr_values);
 986
 987   if (h->msglvl >= 2)
 988     fprintf (stderr, "hivex_node_values: nr_values = %zu\n", nr_values);
 989
 990   INIT_OFFSET_LIST (values);
 991   INIT_OFFSET_LIST (blocks);
 992
 993   /* Deal with the common "no values" case quickly. */
 994   if (nr_values == 0)
 995     goto ok;
 996
 997   /* Arbitrarily limit the number of values we will ever deal with. */
 998   if (nr_values > HIVEX_MAX_VALUES) {
 999     errno = ERANGE;
1000     goto error;
1001   }
1002
1003   /* Preallocate space for the values. */
1004   if (grow_offset_list (&values, nr_values) == -1)
1005     goto error;
1006
1007   /* Get the value list and check it looks reasonable. */
1008   size_t vlist_offset = le32toh (nk->vallist);
1009   vlist_offset += 0x1000;
1010   if (!IS_VALID_BLOCK (h, vlist_offset)) {
1011     if (h->msglvl >= 2)
1012       fprintf (stderr, "hivex_node_values: returning EFAULT because value list is not a valid block (0x%zx)\n",
1013                vlist_offset);
1014     errno = EFAULT;
1015     goto error;
1016   }
1017
1018   if (add_to_offset_list (&blocks, vlist_offset) == -1)
1019     goto error;
1020
1021   struct ntreg_value_list *vlist =
1022     (struct ntreg_value_list *) (h->addr + vlist_offset);
1023
1024   size_t len = block_len (h, vlist_offset, NULL);
1025   if (4 + nr_values * 4 > len) {
1026     if (h->msglvl >= 2)
1027       fprintf (stderr, "hivex_node_values: returning EFAULT because value list is too long (%zu, %zu)\n",
1028                nr_values, len);
1029     errno = EFAULT;
1030     goto error;
1031   }
1032
1033   size_t i;
1034   for (i = 0; i < nr_values; ++i) {
1035     hive_node_h value = vlist->offset[i];
1036     value += 0x1000;
1037     if (!IS_VALID_BLOCK (h, value)) {
1038       if (h->msglvl >= 2)
1039         fprintf (stderr, "hivex_node_values: returning EFAULT because value is not a valid block (0x%zx)\n",
1040                  value);
1041       errno = EFAULT;
1042       goto error;
1043     }
1044     if (add_to_offset_list (&values, value) == -1)
1045       goto error;
1046   }
1047
1048  ok:
1049   *values_ret = return_offset_list (&values);
1050   *blocks_ret = return_offset_list (&blocks);
1051   if (!*values_ret || !*blocks_ret)
1052     goto error;
1053   return 0;
1054
1055  error:
1056   free_offset_list (&values);
1057   free_offset_list (&blocks);
1058   return -1;
1059 }
1060
1061 hive_value_h *
1062 hivex_node_values (hive_h *h, hive_node_h node)
1063 {
1064   hive_value_h *values;
1065   size_t *blocks;
1066
1067   if (get_values (h, node, &values, &blocks) == -1)
1068     return NULL;
1069
1070   free (blocks);
1071   return values;
1072 }
1073
1074 /* Very inefficient, but at least having a separate API call
1075  * allows us to make it more efficient in future.
1076  */
1077 hive_value_h
1078 hivex_node_get_value (hive_h *h, hive_node_h node, const char *key)
1079 {
1080   hive_value_h *values = NULL;
1081   char *name = NULL;
1082   hive_value_h ret = 0;
1083
1084   values = hivex_node_values (h, node);
1085   if (!values) goto error;
1086
1087   size_t i;
1088   for (i = 0; values[i] != 0; ++i) {
1089     name = hivex_value_key (h, values[i]);
1090     if (!name) goto error;
1091     if (STRCASEEQ (name, key)) {
1092       ret = values[i];
1093       break;
1094     }
1095     free (name); name = NULL;
1096   }
1097
1098  error:
1099   free (values);
1100   free (name);
1101   return ret;
1102 }
1103
1104 char *
1105 hivex_value_key (hive_h *h, hive_value_h value)
1106 {
1107   if (!IS_VALID_BLOCK (h, value) || !BLOCK_ID_EQ (h, value, "vk")) {
1108     errno = EINVAL;
1109     return 0;
1110   }
1111
1112   struct ntreg_vk_record *vk = (struct ntreg_vk_record *) (h->addr + value);
1113
1114   /* AFAIK the key is always plain ASCII, so no conversion to UTF-8 is
1115    * necessary.  However we do need to nul-terminate the string.
1116    */
1117
1118   /* vk->name_len is unsigned, 16 bit, so this is safe ...  However
1119    * we have to make sure the length doesn't exceed the block length.
1120    */
1121   size_t len = le16toh (vk->name_len);
1122   size_t seg_len = block_len (h, value, NULL);
1123   if (sizeof (struct ntreg_vk_record) + len - 1 > seg_len) {
1124     if (h->msglvl >= 2)
1125       fprintf (stderr, "hivex_value_key: returning EFAULT because key length is too long (%zu, %zu)\n",
1126                len, seg_len);
1127     errno = EFAULT;
1128     return NULL;
1129   }
1130
1131   char *ret = malloc (len + 1);
1132   if (ret == NULL)
1133     return NULL;
1134   memcpy (ret, vk->name, len);
1135   ret[len] = '\0';
1136   return ret;
1137 }
1138
1139 int
1140 hivex_value_type (hive_h *h, hive_value_h value, hive_type *t, size_t *len)
1141 {
1142   if (!IS_VALID_BLOCK (h, value) || !BLOCK_ID_EQ (h, value, "vk")) {
1143     errno = EINVAL;
1144     return -1;
1145   }
1146
1147   struct ntreg_vk_record *vk = (struct ntreg_vk_record *) (h->addr + value);
1148
1149   if (t)
1150     *t = le32toh (vk->data_type);
1151
1152   if (len) {
1153     *len = le32toh (vk->data_len);
1154     if (*len == 0x80000000) {   /* special case */
1155       *len = 4;
1156       if (t) *t = hive_t_dword;
1157     }
1158     *len &= 0x7fffffff;
1159   }
1160
1161   return 0;
1162 }
1163
1164 char *
1165 hivex_value_value (hive_h *h, hive_value_h value,
1166                    hive_type *t_rtn, size_t *len_rtn)
1167 {
1168   if (!IS_VALID_BLOCK (h, value) || !BLOCK_ID_EQ (h, value, "vk")) {
1169     errno = EINVAL;
1170     return NULL;
1171   }
1172
1173   struct ntreg_vk_record *vk = (struct ntreg_vk_record *) (h->addr + value);
1174
1175   hive_type t;
1176   size_t len;
1177
1178   t = le32toh (vk->data_type);
1179
1180   len = le32toh (vk->data_len);
1181   if (len == 0x80000000) {      /* special case */
1182     len = 4;
1183     t = hive_t_dword;
1184   }
1185   len &= 0x7fffffff;
1186
1187   if (h->msglvl >= 2)
1188     fprintf (stderr, "hivex_value_value: value=0x%zx, t=%d, len=%zu\n",
1189              value, t, len);
1190
1191   if (t_rtn)
1192     *t_rtn = t;
1193   if (len_rtn)
1194     *len_rtn = len;
1195
1196   /* Arbitrarily limit the length that we will read. */
1197   if (len > HIVEX_MAX_VALUE_LEN) {
1198     errno = ERANGE;
1199     return NULL;
1200   }
1201
1202   char *ret = malloc (len);
1203   if (ret == NULL)
1204     return NULL;
1205
1206   /* If length is <= 4 it's always stored inline. */
1207   if (len <= 4) {
1208     memcpy (ret, (char *) &vk->data_offset, len);
1209     return ret;
1210   }
1211
1212   size_t data_offset = le32toh (vk->data_offset);
1213   data_offset += 0x1000;
1214   if (!IS_VALID_BLOCK (h, data_offset)) {
1215     if (h->msglvl >= 2)
1216       fprintf (stderr, "hivex_value_value: returning EFAULT because data offset is not a valid block (0x%zx)\n",
1217                data_offset);
1218     errno = EFAULT;
1219     free (ret);
1220     return NULL;
1221   }
1222
1223   /* Check that the declared size isn't larger than the block its in.
1224    *
1225    * XXX Some apparently valid registries are seen to have this,
1226    * so turn this into a warning and substitute the smaller length
1227    * instead.
1228    */
1229   size_t blen = block_len (h, data_offset, NULL);
1230   if (len > blen - 4 /* subtract 4 for block header */) {
1231     if (h->msglvl >= 2)
1232       fprintf (stderr, "hivex_value_value: warning: declared data length is longer than the block it is in (data 0x%zx, data len %zu, block len %zu)\n",
1233                data_offset, len, blen);
1234     len = blen - 4;
1235   }
1236
1237   char *data = h->addr + data_offset + 4;
1238   memcpy (ret, data, len);
1239   return ret;
1240 }
1241
1242 static char *
1243 windows_utf16_to_utf8 (/* const */ char *input, size_t len)
1244 {
1245   iconv_t ic = iconv_open ("UTF-8", "UTF-16");
1246   if (ic == (iconv_t) -1)
1247     return NULL;
1248
1249   /* iconv(3) has an insane interface ... */
1250
1251   /* Mostly UTF-8 will be smaller, so this is a good initial guess. */
1252   size_t outalloc = len;
1253
1254  again:;
1255   size_t inlen = len;
1256   size_t outlen = outalloc;
1257   char *out = malloc (outlen + 1);
1258   if (out == NULL) {
1259     int err = errno;
1260     iconv_close (ic);
1261     errno = err;
1262     return NULL;
1263   }
1264   char *inp = input;
1265   char *outp = out;
1266
1267   size_t r = iconv (ic, &inp, &inlen, &outp, &outlen);
1268   if (r == (size_t) -1) {
1269     if (errno == E2BIG) {
1270       size_t prev = outalloc;
1271       /* Try again with a larger output buffer. */
1272       free (out);
1273       outalloc *= 2;
1274       if (outalloc < prev)
1275         return NULL;
1276       goto again;
1277     }
1278     else {
1279       /* Else some conversion failure, eg. EILSEQ, EINVAL. */
1280       int err = errno;
1281       iconv_close (ic);
1282       free (out);
1283       errno = err;
1284       return NULL;
1285     }
1286   }
1287
1288   *outp = '\0';
1289   iconv_close (ic);
1290
1291   return out;
1292 }
1293
1294 char *
1295 hivex_value_string (hive_h *h, hive_value_h value)
1296 {
1297   hive_type t;
1298   size_t len;
1299   char *data = hivex_value_value (h, value, &t, &len);
1300
1301   if (data == NULL)
1302     return NULL;
1303
1304   if (t != hive_t_string && t != hive_t_expand_string && t != hive_t_link) {
1305     free (data);
1306     errno = EINVAL;
1307     return NULL;
1308   }
1309
1310   char *ret = windows_utf16_to_utf8 (data, len);
1311   free (data);
1312   if (ret == NULL)
1313     return NULL;
1314
1315   return ret;
1316 }
1317
1318 static void
1319 free_strings (char **argv)
1320 {
1321   if (argv) {
1322     size_t i;
1323
1324     for (i = 0; argv[i] != NULL; ++i)
1325       free (argv[i]);
1326     free (argv);
1327   }
1328 }
1329
1330 /* Get the length of a UTF-16 format string.  Handle the string as
1331  * pairs of bytes, looking for the first \0\0 pair.
1332  */
1333 static size_t
1334 utf16_string_len_in_bytes (const char *str)
1335 {
1336   size_t ret = 0;
1337
1338   while (str[0] || str[1]) {
1339     str += 2;
1340     ret += 2;
1341   }
1342
1343   return ret;
1344 }
1345
1346 /* http://blogs.msdn.com/oldnewthing/archive/2009/10/08/9904646.aspx */
1347 char **
1348 hivex_value_multiple_strings (hive_h *h, hive_value_h value)
1349 {
1350   hive_type t;
1351   size_t len;
1352   char *data = hivex_value_value (h, value, &t, &len);
1353
1354   if (data == NULL)
1355     return NULL;
1356
1357   if (t != hive_t_multiple_strings) {
1358     free (data);
1359     errno = EINVAL;
1360     return NULL;
1361   }
1362
1363   size_t nr_strings = 0;
1364   char **ret = malloc ((1 + nr_strings) * sizeof (char *));
1365   if (ret == NULL) {
1366     free (data);
1367     return NULL;
1368   }
1369   ret[0] = NULL;
1370
1371   char *p = data;
1372   size_t plen;
1373
1374   while (p < data + len && (plen = utf16_string_len_in_bytes (p)) > 0) {
1375     nr_strings++;
1376     char **ret2 = realloc (ret, (1 + nr_strings) * sizeof (char *));
1377     if (ret2 == NULL) {
1378       free_strings (ret);
1379       free (data);
1380       return NULL;
1381     }
1382     ret = ret2;
1383
1384     ret[nr_strings-1] = windows_utf16_to_utf8 (p, plen);
1385     ret[nr_strings] = NULL;
1386     if (ret[nr_strings-1] == NULL) {
1387       free_strings (ret);
1388       free (data);
1389       return NULL;
1390     }
1391
1392     p += plen + 2 /* skip over UTF-16 \0\0 at the end of this string */;
1393   }
1394
1395   free (data);
1396   return ret;
1397 }
1398
1399 int32_t
1400 hivex_value_dword (hive_h *h, hive_value_h value)
1401 {
1402   hive_type t;
1403   size_t len;
1404   char *data = hivex_value_value (h, value, &t, &len);
1405
1406   if (data == NULL)
1407     return -1;
1408
1409   if ((t != hive_t_dword && t != hive_t_dword_be) || len != 4) {
1410     free (data);
1411     errno = EINVAL;
1412     return -1;
1413   }
1414
1415   int32_t ret = *(int32_t*)data;
1416   free (data);
1417   if (t == hive_t_dword)        /* little endian */
1418     ret = le32toh (ret);
1419   else
1420     ret = be32toh (ret);
1421
1422   return ret;
1423 }
1424
1425 int64_t
1426 hivex_value_qword (hive_h *h, hive_value_h value)
1427 {
1428   hive_type t;
1429   size_t len;
1430   char *data = hivex_value_value (h, value, &t, &len);
1431
1432   if (data == NULL)
1433     return -1;
1434
1435   if (t != hive_t_qword || len != 8) {
1436     free (data);
1437     errno = EINVAL;
1438     return -1;
1439   }
1440
1441   int64_t ret = *(int64_t*)data;
1442   free (data);
1443   ret = le64toh (ret);          /* always little endian */
1444
1445   return ret;
1446 }
1447
1448 /*----------------------------------------------------------------------
1449  * Visiting.
1450  */
1451
1452 int
1453 hivex_visit (hive_h *h, const struct hivex_visitor *visitor, size_t len,
1454              void *opaque, int flags)
1455 {
1456   return hivex_visit_node (h, hivex_root (h), visitor, len, opaque, flags);
1457 }
1458
1459 static int hivex__visit_node (hive_h *h, hive_node_h node, const struct hivex_visitor *vtor, char *unvisited, void *opaque, int flags);
1460
1461 int
1462 hivex_visit_node (hive_h *h, hive_node_h node,
1463                   const struct hivex_visitor *visitor, size_t len, void *opaque,
1464                   int flags)
1465 {
1466   struct hivex_visitor vtor;
1467   memset (&vtor, 0, sizeof vtor);
1468
1469   /* Note that len might be larger *or smaller* than the expected size. */
1470   size_t copysize = len <= sizeof vtor ? len : sizeof vtor;
1471   memcpy (&vtor, visitor, copysize);
1472
1473   /* This bitmap records unvisited nodes, so we don't loop if the
1474    * registry contains cycles.
1475    */
1476   char *unvisited = malloc (1 + h->size / 32);
1477   if (unvisited == NULL)
1478     return -1;
1479   memcpy (unvisited, h->bitmap, 1 + h->size / 32);
1480
1481   int r = hivex__visit_node (h, node, &vtor, unvisited, opaque, flags);
1482   free (unvisited);
1483   return r;
1484 }
1485
1486 static int
1487 hivex__visit_node (hive_h *h, hive_node_h node,
1488                    const struct hivex_visitor *vtor, char *unvisited,
1489                    void *opaque, int flags)
1490 {
1491   int skip_bad = flags & HIVEX_VISIT_SKIP_BAD;
1492   char *name = NULL;
1493   hive_value_h *values = NULL;
1494   hive_node_h *children = NULL;
1495   char *key = NULL;
1496   char *str = NULL;
1497   char **strs = NULL;
1498   int i;
1499
1500   /* Return -1 on all callback errors.  However on internal errors,
1501    * check if skip_bad is set and suppress those errors if so.
1502    */
1503   int ret = -1;
1504
1505   if (!BITMAP_TST (unvisited, node)) {
1506     if (h->msglvl >= 2)
1507       fprintf (stderr, "hivex__visit_node: contains cycle: visited node 0x%zx already\n",
1508                node);
1509
1510     errno = ELOOP;
1511     return skip_bad ? 0 : -1;
1512   }
1513   BITMAP_CLR (unvisited, node);
1514
1515   name = hivex_node_name (h, node);
1516   if (!name) return skip_bad ? 0 : -1;
1517   if (vtor->node_start && vtor->node_start (h, opaque, node, name) == -1)
1518     goto error;
1519
1520   values = hivex_node_values (h, node);
1521   if (!values) {
1522     ret = skip_bad ? 0 : -1;
1523     goto error;
1524   }
1525
1526   for (i = 0; values[i] != 0; ++i) {
1527     hive_type t;
1528     size_t len;
1529
1530     if (hivex_value_type (h, values[i], &t, &len) == -1) {
1531       ret = skip_bad ? 0 : -1;
1532       goto error;
1533     }
1534
1535     key = hivex_value_key (h, values[i]);
1536     if (key == NULL) {
1537       ret = skip_bad ? 0 : -1;
1538       goto error;
1539     }
1540
1541     if (vtor->value_any) {
1542       str = hivex_value_value (h, values[i], &t, &len);
1543       if (str == NULL) {
1544         ret = skip_bad ? 0 : -1;
1545         goto error;
1546       }
1547       if (vtor->value_any (h, opaque, node, values[i], t, len, key, str) == -1)
1548         goto error;
1549       free (str); str = NULL;
1550     }
1551     else {
1552       switch (t) {
1553       case hive_t_none:
1554         str = hivex_value_value (h, values[i], &t, &len);
1555         if (str == NULL) {
1556           ret = skip_bad ? 0 : -1;
1557           goto error;
1558         }
1559         if (t != hive_t_none) {
1560           ret = skip_bad ? 0 : -1;
1561           goto error;
1562         }
1563         if (vtor->value_none &&
1564             vtor->value_none (h, opaque, node, values[i], t, len, key, str) == -1)
1565           goto error;
1566         free (str); str = NULL;
1567         break;
1568
1569       case hive_t_string:
1570       case hive_t_expand_string:
1571       case hive_t_link:
1572         str = hivex_value_string (h, values[i]);
1573         if (str == NULL) {
1574           if (errno != EILSEQ && errno != EINVAL) {
1575             ret = skip_bad ? 0 : -1;
1576             goto error;
1577           }
1578           if (vtor->value_string_invalid_utf16) {
1579             str = hivex_value_value (h, values[i], &t, &len);
1580             if (vtor->value_string_invalid_utf16 (h, opaque, node, values[i], t, len, key, str) == -1)
1581               goto error;
1582             free (str); str = NULL;
1583           }
1584           break;
1585         }
1586         if (vtor->value_string &&
1587             vtor->value_string (h, opaque, node, values[i], t, len, key, str) == -1)
1588           goto error;
1589         free (str); str = NULL;
1590         break;
1591
1592       case hive_t_dword:
1593       case hive_t_dword_be: {
1594         int32_t i32 = hivex_value_dword (h, values[i]);
1595         if (vtor->value_dword &&
1596             vtor->value_dword (h, opaque, node, values[i], t, len, key, i32) == -1)
1597           goto error;
1598         break;
1599       }
1600
1601       case hive_t_qword: {
1602         int64_t i64 = hivex_value_qword (h, values[i]);
1603         if (vtor->value_qword &&
1604             vtor->value_qword (h, opaque, node, values[i], t, len, key, i64) == -1)
1605           goto error;
1606         break;
1607       }
1608
1609       case hive_t_binary:
1610         str = hivex_value_value (h, values[i], &t, &len);
1611         if (str == NULL) {
1612           ret = skip_bad ? 0 : -1;
1613           goto error;
1614         }
1615         if (t != hive_t_binary) {
1616           ret = skip_bad ? 0 : -1;
1617           goto error;
1618         }
1619         if (vtor->value_binary &&
1620             vtor->value_binary (h, opaque, node, values[i], t, len, key, str) == -1)
1621           goto error;
1622         free (str); str = NULL;
1623         break;
1624
1625       case hive_t_multiple_strings:
1626         strs = hivex_value_multiple_strings (h, values[i]);
1627         if (strs == NULL) {
1628           if (errno != EILSEQ && errno != EINVAL) {
1629             ret = skip_bad ? 0 : -1;
1630             goto error;
1631           }
1632           if (vtor->value_string_invalid_utf16) {
1633             str = hivex_value_value (h, values[i], &t, &len);
1634             if (vtor->value_string_invalid_utf16 (h, opaque, node, values[i], t, len, key, str) == -1)
1635               goto error;
1636             free (str); str = NULL;
1637           }
1638           break;
1639         }
1640         if (vtor->value_multiple_strings &&
1641             vtor->value_multiple_strings (h, opaque, node, values[i], t, len, key, strs) == -1)
1642           goto error;
1643         free_strings (strs); strs = NULL;
1644         break;
1645
1646       case hive_t_resource_list:
1647       case hive_t_full_resource_description:
1648       case hive_t_resource_requirements_list:
1649       default:
1650         str = hivex_value_value (h, values[i], &t, &len);
1651         if (str == NULL) {
1652           ret = skip_bad ? 0 : -1;
1653           goto error;
1654         }
1655         if (vtor->value_other &&
1656             vtor->value_other (h, opaque, node, values[i], t, len, key, str) == -1)
1657           goto error;
1658         free (str); str = NULL;
1659         break;
1660       }
1661     }
1662
1663     free (key); key = NULL;
1664   }
1665
1666   children = hivex_node_children (h, node);
1667   if (children == NULL) {
1668     ret = skip_bad ? 0 : -1;
1669     goto error;
1670   }
1671
1672   for (i = 0; children[i] != 0; ++i) {
1673     if (h->msglvl >= 2)
1674       fprintf (stderr, "hivex__visit_node: %s: visiting subkey %d (0x%zx)\n",
1675                name, i, children[i]);
1676
1677     if (hivex__visit_node (h, children[i], vtor, unvisited, opaque, flags) == -1)
1678       goto error;
1679   }
1680
1681   if (vtor->node_end && vtor->node_end (h, opaque, node, name) == -1)
1682     goto error;
1683
1684   ret = 0;
1685
1686  error:
1687   free (name);
1688   free (values);
1689   free (children);
1690   free (key);
1691   free (str);
1692   free_strings (strs);
1693   return ret;
1694 }
1695
1696 /*----------------------------------------------------------------------
1697  * Writing.
1698  */
1699
1700 /* Allocate an hbin (page), extending the malloc'd space if necessary,
1701  * and updating the hive handle fields (but NOT the hive disk header
1702  * -- the hive disk header is updated when we commit).  This function
1703  * also extends the bitmap if necessary.
1704  *
1705  * 'allocation_hint' is the size of the block allocation we would like
1706  * to make.  Normally registry blocks are very small (avg 50 bytes)
1707  * and are contained in standard-sized pages (4KB), but the registry
1708  * can support blocks which are larger than a standard page, in which
1709  * case it creates a page of 8KB, 12KB etc.
1710  *
1711  * Returns:
1712  * > 0 : offset of first usable byte of new page (after page header)
1713  * 0   : error (errno set)
1714  */
1715 static size_t
1716 allocate_page (hive_h *h, size_t allocation_hint)
1717 {
1718   /* In almost all cases this will be 1. */
1719   size_t nr_4k_pages =
1720     1 + (allocation_hint + sizeof (struct ntreg_hbin_page) - 1) / 4096;
1721   assert (nr_4k_pages >= 1);
1722
1723   /* 'extend' is the number of bytes to extend the file by.  Note that
1724    * hives found in the wild often contain slack between 'endpages'
1725    * and the actual end of the file, so we don't always need to make
1726    * the file larger.
1727    */
1728   ssize_t extend = h->endpages + nr_4k_pages * 4096 - h->size;
1729
1730   if (h->msglvl >= 2) {
1731     fprintf (stderr, "allocate_page: current endpages = 0x%zx, current size = 0x%zx\n",
1732              h->endpages, h->size);
1733     fprintf (stderr, "allocate_page: extending file by %zd bytes (<= 0 if no extension)\n",
1734              extend);
1735   }
1736
1737   if (extend > 0) {
1738     size_t oldsize = h->size;
1739     size_t newsize = h->size + extend;
1740     char *newaddr = realloc (h->addr, newsize);
1741     if (newaddr == NULL)
1742       return 0;
1743
1744     size_t oldbitmapsize = 1 + oldsize / 32;
1745     size_t newbitmapsize = 1 + newsize / 32;
1746     char *newbitmap = realloc (h->bitmap, newbitmapsize);
1747     if (newbitmap == NULL) {
1748       free (newaddr);
1749       return 0;
1750     }
1751
1752     h->addr = newaddr;
1753     h->size = newsize;
1754     h->bitmap = newbitmap;
1755
1756     memset (h->addr + oldsize, 0, newsize - oldsize);
1757     memset (h->bitmap + oldbitmapsize, 0, newbitmapsize - oldbitmapsize);
1758   }
1759
1760   size_t offset = h->endpages;
1761   h->endpages += nr_4k_pages * 4096;
1762
1763   if (h->msglvl >= 2)
1764     fprintf (stderr, "allocate_page: new endpages = 0x%zx, new size = 0x%zx\n",
1765              h->endpages, h->size);
1766
1767   /* Write the hbin header. */
1768   struct ntreg_hbin_page *page =
1769     (struct ntreg_hbin_page *) (h->addr + offset);
1770   page->magic[0] = 'h';
1771   page->magic[1] = 'b';
1772   page->magic[2] = 'i';
1773   page->magic[3] = 'n';
1774   page->offset_first = htole32 (offset - 0x1000);
1775   page->page_size = htole32 (nr_4k_pages * 4096);
1776   memset (page->unknown, 0, sizeof (page->unknown));
1777
1778   if (h->msglvl >= 2)
1779     fprintf (stderr, "allocate_page: new page at 0x%zx\n", offset);
1780
1781   /* Offset of first usable byte after the header. */
1782   return offset + sizeof (struct ntreg_hbin_page);
1783 }
1784
1785 /* Allocate a single block, first allocating an hbin (page) at the end
1786  * of the current file if necessary.  NB. To keep the implementation
1787  * simple and more likely to be correct, we do not reuse existing free
1788  * blocks.
1789  *
1790  * seg_len is the size of the block (this INCLUDES the block header).
1791  * The header of the block is initialized to -seg_len (negative to
1792  * indicate used).  id[2] is the block ID (type), eg. "nk" for nk-
1793  * record.  The block bitmap is updated to show this block as valid.
1794  * The rest of the contents of the block will be zero.
1795  *
1796  * Returns:
1797  * > 0 : offset of new block
1798  * 0   : error (errno set)
1799  */
1800 static size_t
1801 allocate_block (hive_h *h, size_t seg_len, const char id[2])
1802 {
1803   if (!h->writable) {
1804     errno = EROFS;
1805     return 0;
1806   }
1807
1808   if (seg_len < 4) {
1809     /* The caller probably forgot to include the header.  Note that
1810      * value lists have no ID field, so seg_len == 4 would be possible
1811      * for them, albeit unusual.
1812      */
1813     if (h->msglvl >= 2)
1814       fprintf (stderr, "allocate_block: refusing too small allocation (%zu), returning ERANGE\n",
1815                seg_len);
1816     errno = ERANGE;
1817     return 0;
1818   }
1819
1820   /* Refuse really large allocations. */
1821   if (seg_len > HIVEX_MAX_ALLOCATION) {
1822     if (h->msglvl >= 2)
1823       fprintf (stderr, "allocate_block: refusing large allocation (%zu), returning ERANGE\n",
1824                seg_len);
1825     errno = ERANGE;
1826     return 0;
1827   }
1828
1829   /* Round up allocation to multiple of 8 bytes.  All blocks must be
1830    * on an 8 byte boundary.
1831    */
1832   seg_len = (seg_len + 7) & ~7;
1833
1834   /* Allocate a new page if necessary. */
1835   if (h->endblocks == 0 || h->endblocks + seg_len > h->endpages) {
1836     size_t newendblocks = allocate_page (h, seg_len);
1837     if (newendblocks == 0)
1838       return 0;
1839     h->endblocks = newendblocks;
1840   }
1841
1842   size_t offset = h->endblocks;
1843
1844   if (h->msglvl >= 2)
1845     fprintf (stderr, "allocate_block: new block at 0x%zx, size %zu\n",
1846              offset, seg_len);
1847
1848   struct ntreg_hbin_block *blockhdr =
1849     (struct ntreg_hbin_block *) (h->addr + offset);
1850
1851   blockhdr->seg_len = htole32 (- (int32_t) seg_len);
1852   if (id[0] && id[1] && seg_len >= sizeof (struct ntreg_hbin_block)) {
1853     blockhdr->id[0] = id[0];
1854     blockhdr->id[1] = id[1];
1855   }
1856
1857   BITMAP_SET (h->bitmap, offset);
1858
1859   h->endblocks += seg_len;
1860
1861   /* If there is space after the last block in the last page, then we
1862    * have to put a dummy free block header here to mark the rest of
1863    * the page as free.
1864    */
1865   ssize_t rem = h->endpages - h->endblocks;
1866   if (rem > 0) {
1867     if (h->msglvl >= 2)
1868       fprintf (stderr, "allocate_block: marking remainder of page free starting at 0x%zx, size %zd\n",
1869                h->endblocks, rem);
1870
1871     assert (rem >= 4);
1872
1873     blockhdr = (struct ntreg_hbin_block *) (h->addr + h->endblocks);
1874     blockhdr->seg_len = htole32 ((int32_t) rem);
1875   }
1876
1877   return offset;
1878 }
1879
1880 /* 'offset' must point to a valid, used block.  This function marks
1881  * the block unused (by updating the seg_len field) and invalidates
1882  * the bitmap.  It does NOT do this recursively, so to avoid creating
1883  * unreachable used blocks, callers may have to recurse over the hive
1884  * structures.  Also callers must ensure there are no references to
1885  * this block from other parts of the hive.
1886  */
1887 static void
1888 mark_block_unused (hive_h *h, size_t offset)
1889 {
1890   assert (h->writable);
1891   assert (IS_VALID_BLOCK (h, offset));
1892
1893   if (h->msglvl >= 2)
1894     fprintf (stderr, "mark_block_unused: marking 0x%zx unused\n", offset);
1895
1896   struct ntreg_hbin_block *blockhdr =
1897     (struct ntreg_hbin_block *) (h->addr + offset);
1898
1899   size_t seg_len = block_len (h, offset, NULL);
1900   blockhdr->seg_len = htole32 (seg_len);
1901
1902   BITMAP_CLR (h->bitmap, offset);
1903 }
1904
1905 /* Delete all existing values at this node. */
1906 static int
1907 delete_values (hive_h *h, hive_node_h node)
1908 {
1909   assert (h->writable);
1910
1911   hive_value_h *values;
1912   size_t *blocks;
1913   if (get_values (h, node, &values, &blocks) == -1)
1914     return -1;
1915
1916   size_t i;
1917   for (i = 0; blocks[i] != 0; ++i)
1918     mark_block_unused (h, blocks[i]);
1919
1920   free (blocks);
1921
1922   for (i = 0; values[i] != 0; ++i) {
1923     struct ntreg_vk_record *vk =
1924       (struct ntreg_vk_record *) (h->addr + values[i]);
1925
1926     size_t len;
1927     len = le32toh (vk->data_len);
1928     if (len == 0x80000000)      /* special case */
1929       len = 4;
1930     len &= 0x7fffffff;
1931
1932     if (len > 4) {              /* non-inline, so remove data block */
1933       size_t data_offset = le32toh (vk->data_offset);
1934       data_offset += 0x1000;
1935       mark_block_unused (h, data_offset);
1936     }
1937
1938     /* remove vk record */
1939     mark_block_unused (h, values[i]);
1940   }
1941
1942   free (values);
1943
1944   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
1945   nk->nr_values = htole32 (0);
1946   nk->vallist = htole32 (0xffffffff);
1947
1948   return 0;
1949 }
1950
1951 int
1952 hivex_commit (hive_h *h, const char *filename, int flags)
1953 {
1954   if (flags != 0) {
1955     errno = EINVAL;
1956     return -1;
1957   }
1958
1959   if (!h->writable) {
1960     errno = EROFS;
1961     return -1;
1962   }
1963
1964   filename = filename ? : h->filename;
1965   int fd = open (filename, O_WRONLY|O_CREAT|O_TRUNC|O_NOCTTY, 0666);
1966   if (fd == -1)
1967     return -1;
1968
1969   /* Update the header fields. */
1970   uint32_t sequence = le32toh (h->hdr->sequence1);
1971   sequence++;
1972   h->hdr->sequence1 = htole32 (sequence);
1973   h->hdr->sequence2 = htole32 (sequence);
1974   /* XXX Ought to update h->hdr->last_modified. */
1975   h->hdr->blocks = htole32 (h->endpages - 0x1000);
1976
1977   /* Recompute header checksum. */
1978   uint32_t sum = header_checksum (h);
1979   h->hdr->csum = htole32 (sum);
1980
1981   if (h->msglvl >= 2)
1982     fprintf (stderr, "hivex_commit: new header checksum: 0x%x\n", sum);
1983
1984   if (full_write (fd, h->addr, h->size) != h->size) {
1985     int err = errno;
1986     close (fd);
1987     errno = err;
1988     return -1;
1989   }
1990
1991   if (close (fd) == -1)
1992     return -1;
1993
1994   return 0;
1995 }
1996
1997 /* Calculate the hash for a lf or lh record offset.
1998  */
1999 static void
2000 calc_hash (const char *type, const char *name, char *ret)
2001 {
2002   size_t len = strlen (name);
2003
2004   if (STRPREFIX (type, "lf"))
2005     /* Old-style, not used in current registries. */
2006     memcpy (ret, name, len < 4 ? len : 4);
2007   else {
2008     /* New-style for lh-records. */
2009     size_t i, c;
2010     uint32_t h = 0;
2011     for (i = 0; i < len; ++i) {
2012       c = c_toupper (name[i]);
2013       h *= 37;
2014       h += c;
2015     }
2016     *((uint32_t *) ret) = htole32 (h);
2017   }
2018 }
2019
2020 /* Create a completely new lh-record containing just the single node. */
2021 static size_t
2022 new_lh_record (hive_h *h, const char *name, hive_node_h node)
2023 {
2024   static const char id[2] = { 'l', 'h' };
2025   size_t seg_len = sizeof (struct ntreg_lf_record);
2026   size_t offset = allocate_block (h, seg_len, id);
2027   if (offset == 0)
2028     return 0;
2029
2030   struct ntreg_lf_record *lh = (struct ntreg_lf_record *) (h->addr + offset);
2031   lh->nr_keys = htole16 (1);
2032   lh->keys[0].offset = htole32 (node - 0x1000);
2033   calc_hash ("lh", name, lh->keys[0].hash);
2034
2035   return offset;
2036 }
2037
2038 /* Insert node into existing lf/lh-record at position.
2039  * This allocates a new record and marks the old one as unused.
2040  */
2041 static size_t
2042 insert_lf_record (hive_h *h, size_t old_offs, size_t posn,
2043                   const char *name, hive_node_h node)
2044 {
2045   assert (IS_VALID_BLOCK (h, old_offs));
2046
2047   /* Work around C stupidity.
2048    * http://www.redhat.com/archives/libguestfs/2010-February/msg00056.html
2049    */
2050   int test = BLOCK_ID_EQ (h, old_offs, "lf") || BLOCK_ID_EQ (h, old_offs, "lh");
2051   assert (test);
2052
2053   struct ntreg_lf_record *old_lf =
2054     (struct ntreg_lf_record *) (h->addr + old_offs);
2055   size_t nr_keys = le16toh (old_lf->nr_keys);
2056
2057   nr_keys++; /* in new record ... */
2058
2059   size_t seg_len = sizeof (struct ntreg_lf_record) + (nr_keys-1) * 8;
2060   size_t new_offs = allocate_block (h, seg_len, old_lf->id);
2061   if (new_offs == 0)
2062     return 0;
2063
2064   struct ntreg_lf_record *new_lf =
2065     (struct ntreg_lf_record *) (h->addr + new_offs);
2066   new_lf->nr_keys = htole16 (nr_keys);
2067
2068   /* Copy the keys until we reach posn, insert the new key there, then
2069    * copy the remaining keys.
2070    */
2071   size_t i;
2072   for (i = 0; i < posn; ++i)
2073     new_lf->keys[i] = old_lf->keys[i];
2074
2075   new_lf->keys[i].offset = htole32 (node - 0x1000);
2076   calc_hash (new_lf->id, name, new_lf->keys[i].hash);
2077
2078   for (i = posn+1; i < nr_keys; ++i)
2079     new_lf->keys[i] = old_lf->keys[i-1];
2080
2081   /* Old block is unused, return new block. */
2082   mark_block_unused (h, old_offs);
2083   return new_offs;
2084 }
2085
2086 /* Compare name with name in nk-record. */
2087 static int
2088 compare_name_with_nk_name (hive_h *h, const char *name, hive_node_h nk_offs)
2089 {
2090   assert (IS_VALID_BLOCK (h, nk_offs));
2091   assert (BLOCK_ID_EQ (h, nk_offs, "nk"));
2092
2093   /* Name in nk is not necessarily nul-terminated. */
2094   char *nname = hivex_node_name (h, nk_offs);
2095
2096   /* Unfortunately we don't have a way to return errors here. */
2097   if (!nname) {
2098     perror ("compare_name_with_nk_name");
2099     return 0;
2100   }
2101
2102   int r = strcasecmp (name, nname);
2103   free (nname);
2104
2105   return r;
2106 }
2107
2108 hive_node_h
2109 hivex_node_add_child (hive_h *h, hive_node_h parent, const char *name)
2110 {
2111   if (!h->writable) {
2112     errno = EROFS;
2113     return 0;
2114   }
2115
2116   if (!IS_VALID_BLOCK (h, parent) || !BLOCK_ID_EQ (h, parent, "nk")) {
2117     errno = EINVAL;
2118     return 0;
2119   }
2120
2121   if (name == NULL || strlen (name) == 0) {
2122     errno = EINVAL;
2123     return 0;
2124   }
2125
2126   if (hivex_node_get_child (h, parent, name) != 0) {
2127     errno = EEXIST;
2128     return 0;
2129   }
2130
2131   /* Create the new nk-record. */
2132   static const char nk_id[2] = { 'n', 'k' };
2133   size_t seg_len = sizeof (struct ntreg_nk_record) + strlen (name);
2134   hive_node_h node = allocate_block (h, seg_len, nk_id);
2135   if (node == 0)
2136     return 0;
2137
2138   if (h->msglvl >= 2)
2139     fprintf (stderr, "hivex_node_add_child: allocated new nk-record for child at 0x%zx\n", node);
2140
2141   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
2142   nk->flags = htole16 (0x0020); /* key is ASCII. */
2143   nk->parent = htole32 (parent - 0x1000);
2144   nk->subkey_lf = htole32 (0xffffffff);
2145   nk->subkey_lf_volatile = htole32 (0xffffffff);
2146   nk->vallist = htole32 (0xffffffff);
2147   nk->classname = htole32 (0xffffffff);
2148   nk->name_len = htole16 (strlen (name));
2149   strcpy (nk->name, name);
2150
2151   /* Inherit parent sk. */
2152   struct ntreg_nk_record *parent_nk =
2153     (struct ntreg_nk_record *) (h->addr + parent);
2154   size_t parent_sk_offset = le32toh (parent_nk->sk);
2155   parent_sk_offset += 0x1000;
2156   if (!IS_VALID_BLOCK (h, parent_sk_offset) ||
2157       !BLOCK_ID_EQ (h, parent_sk_offset, "sk")) {
2158     if (h->msglvl >= 2)
2159       fprintf (stderr, "hivex_node_add_child: returning EFAULT because parent sk is not a valid block (%zu)\n",
2160                parent_sk_offset);
2161     errno = EFAULT;
2162     return 0;
2163   }
2164   struct ntreg_sk_record *sk =
2165     (struct ntreg_sk_record *) (h->addr + parent_sk_offset);
2166   sk->refcount = htole32 (le32toh (sk->refcount) + 1);
2167   nk->sk = htole32 (parent_sk_offset - 0x1000);
2168
2169   /* Inherit parent timestamp. */
2170   memcpy (nk->timestamp, parent_nk->timestamp, sizeof (parent_nk->timestamp));
2171
2172   /* What I found out the hard way (not documented anywhere): the
2173    * subkeys in lh-records must be kept sorted.  If you just add a
2174    * subkey in a non-sorted position (eg. just add it at the end) then
2175    * Windows won't see the subkey _and_ Windows will corrupt the hive
2176    * itself when it modifies or saves it.
2177    *
2178    * So use get_children() to get a list of intermediate
2179    * lf/lh-records.  get_children() returns these in reading order
2180    * (which is sorted), so we look for the lf/lh-records in sequence
2181    * until we find the key name just after the one we are inserting,
2182    * and we insert the subkey just before it.
2183    *
2184    * The only other case is the no-subkeys case, where we have to
2185    * create a brand new lh-record.
2186    */
2187   hive_node_h *unused;
2188   size_t *blocks;
2189
2190   if (get_children (h, parent, &unused, &blocks, 0) == -1)
2191     return 0;
2192   free (unused);
2193
2194   size_t i, j;
2195   size_t nr_subkeys_in_parent_nk = le32toh (parent_nk->nr_subkeys);
2196   if (nr_subkeys_in_parent_nk == 0) { /* No subkeys case. */
2197     /* Free up any existing intermediate blocks. */
2198     for (i = 0; blocks[i] != 0; ++i)
2199       mark_block_unused (h, blocks[i]);
2200     size_t lh_offs = new_lh_record (h, name, node);
2201     if (lh_offs == 0) {
2202       free (blocks);
2203       return 0;
2204     }
2205
2206     if (h->msglvl >= 2)
2207       fprintf (stderr, "hivex_node_add_child: no keys, allocated new lh-record at 0x%zx\n", lh_offs);
2208
2209     parent_nk->subkey_lf = htole32 (lh_offs - 0x1000);
2210   }
2211   else {                        /* Insert subkeys case. */
2212     size_t old_offs = 0, new_offs = 0;
2213     struct ntreg_lf_record *old_lf = NULL;
2214
2215     /* Find lf/lh key name just after the one we are inserting. */
2216     for (i = 0; blocks[i] != 0; ++i) {
2217       if (BLOCK_ID_EQ (h, blocks[i], "lf") ||
2218           BLOCK_ID_EQ (h, blocks[i], "lh")) {
2219         old_offs = blocks[i];
2220         old_lf = (struct ntreg_lf_record *) (h->addr + old_offs);
2221         for (j = 0; j < le16toh (old_lf->nr_keys); ++j) {
2222           hive_node_h nk_offs = le32toh (old_lf->keys[j].offset);
2223           nk_offs += 0x1000;
2224           if (compare_name_with_nk_name (h, name, nk_offs) < 0)
2225             goto insert_it;
2226         }
2227       }
2228     }
2229
2230     /* Insert it at the end.
2231      * old_offs points to the last lf record, set j.
2232      */
2233     assert (old_offs != 0);   /* should never happen if nr_subkeys > 0 */
2234     j = le16toh (old_lf->nr_keys);
2235
2236     /* Insert it. */
2237   insert_it:
2238     if (h->msglvl >= 2)
2239       fprintf (stderr, "hivex_node_add_child: insert key in existing lh-record at 0x%zx, posn %zu\n", old_offs, j);
2240
2241     new_offs = insert_lf_record (h, old_offs, j, name, node);
2242     if (new_offs == 0) {
2243       free (blocks);
2244       return 0;
2245     }
2246
2247     if (h->msglvl >= 2)
2248       fprintf (stderr, "hivex_node_add_child: new lh-record at 0x%zx\n",
2249                new_offs);
2250
2251     /* If the lf/lh-record was directly referenced by the parent nk,
2252      * then update the parent nk.
2253      */
2254     if (le32toh (parent_nk->subkey_lf) + 0x1000 == old_offs)
2255       parent_nk->subkey_lf = htole32 (new_offs - 0x1000);
2256     /* Else we have to look for the intermediate ri-record and update
2257      * that in-place.
2258      */
2259     else {
2260       for (i = 0; blocks[i] != 0; ++i) {
2261         if (BLOCK_ID_EQ (h, blocks[i], "ri")) {
2262           struct ntreg_ri_record *ri =
2263             (struct ntreg_ri_record *) (h->addr + blocks[i]);
2264           for (j = 0; j < le16toh (ri->nr_offsets); ++j)
2265             if (le32toh (ri->offset[j] + 0x1000) == old_offs) {
2266               ri->offset[j] = htole32 (new_offs - 0x1000);
2267               goto found_it;
2268             }
2269         }
2270       }
2271
2272       /* Not found ..  This is an internal error. */
2273       if (h->msglvl >= 2)
2274         fprintf (stderr, "hivex_node_add_child: returning ENOTSUP because could not find ri->lf link\n");
2275       errno = ENOTSUP;
2276       free (blocks);
2277       return 0;
2278
2279     found_it:
2280       ;
2281     }
2282   }
2283
2284   free (blocks);
2285
2286   /* Update nr_subkeys in parent nk. */
2287   nr_subkeys_in_parent_nk++;
2288   parent_nk->nr_subkeys = htole32 (nr_subkeys_in_parent_nk);
2289
2290   /* Update max_subkey_name_len in parent nk. */
2291   uint16_t max = le16toh (parent_nk->max_subkey_name_len);
2292   if (max < strlen (name) * 2)  /* *2 because "recoded" in UTF16-LE. */
2293     parent_nk->max_subkey_name_len = htole16 (strlen (name) * 2);
2294
2295   return node;
2296 }
2297
2298 /* Decrement the refcount of an sk-record, and if it reaches zero,
2299  * unlink it from the chain and delete it.
2300  */
2301 static int
2302 delete_sk (hive_h *h, size_t sk_offset)
2303 {
2304   if (!IS_VALID_BLOCK (h, sk_offset) || !BLOCK_ID_EQ (h, sk_offset, "sk")) {
2305     if (h->msglvl >= 2)
2306       fprintf (stderr, "delete_sk: not an sk record: 0x%zx\n", sk_offset);
2307     errno = EFAULT;
2308     return -1;
2309   }
2310
2311   struct ntreg_sk_record *sk = (struct ntreg_sk_record *) (h->addr + sk_offset);
2312
2313   if (sk->refcount == 0) {
2314     if (h->msglvl >= 2)
2315       fprintf (stderr, "delete_sk: sk record already has refcount 0: 0x%zx\n",
2316                sk_offset);
2317     errno = EINVAL;
2318     return -1;
2319   }
2320
2321   sk->refcount--;
2322
2323   if (sk->refcount == 0) {
2324     size_t sk_prev_offset = sk->sk_prev;
2325     sk_prev_offset += 0x1000;
2326
2327     size_t sk_next_offset = sk->sk_next;
2328     sk_next_offset += 0x1000;
2329
2330     /* Update sk_prev/sk_next SKs, unless they both point back to this
2331      * cell in which case we are deleting the last SK.
2332      */
2333     if (sk_prev_offset != sk_offset && sk_next_offset != sk_offset) {
2334       struct ntreg_sk_record *sk_prev =
2335         (struct ntreg_sk_record *) (h->addr + sk_prev_offset);
2336       struct ntreg_sk_record *sk_next =
2337         (struct ntreg_sk_record *) (h->addr + sk_next_offset);
2338
2339       sk_prev->sk_next = htole32 (sk_next_offset - 0x1000);
2340       sk_next->sk_prev = htole32 (sk_prev_offset - 0x1000);
2341     }
2342
2343     /* Refcount is zero so really delete this block. */
2344     mark_block_unused (h, sk_offset);
2345   }
2346
2347   return 0;
2348 }
2349
2350 /* Callback from hivex_node_delete_child which is called to delete a
2351  * node AFTER its subnodes have been visited.  The subnodes have been
2352  * deleted but we still have to delete any lf/lh/li/ri records and the
2353  * value list block and values, followed by deleting the node itself.
2354  */
2355 static int
2356 delete_node (hive_h *h, void *opaque, hive_node_h node, const char *name)
2357 {
2358   /* Get the intermediate blocks.  The subkeys have already been
2359    * deleted by this point, so tell get_children() not to check for
2360    * validity of the nk-records.
2361    */
2362   hive_node_h *unused;
2363   size_t *blocks;
2364   if (get_children (h, node, &unused, &blocks, GET_CHILDREN_NO_CHECK_NK) == -1)
2365     return -1;
2366   free (unused);
2367
2368   /* We don't care what's in these intermediate blocks, so we can just
2369    * delete them unconditionally.
2370    */
2371   size_t i;
2372   for (i = 0; blocks[i] != 0; ++i)
2373     mark_block_unused (h, blocks[i]);
2374
2375   free (blocks);
2376
2377   /* Delete the values in the node. */
2378   if (delete_values (h, node) == -1)
2379     return -1;
2380
2381   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
2382
2383   /* If the NK references an SK, delete it. */
2384   size_t sk_offs = le32toh (nk->sk);
2385   if (sk_offs != 0xffffffff) {
2386     sk_offs += 0x1000;
2387     if (delete_sk (h, sk_offs) == -1)
2388       return -1;
2389     nk->sk = htole32 (0xffffffff);
2390   }
2391
2392   /* If the NK references a classname, delete it. */
2393   size_t cl_offs = le32toh (nk->classname);
2394   if (cl_offs != 0xffffffff) {
2395     cl_offs += 0x1000;
2396     mark_block_unused (h, cl_offs);
2397     nk->classname = htole32 (0xffffffff);
2398   }
2399
2400   /* Delete the node itself. */
2401   mark_block_unused (h, node);
2402
2403   return 0;
2404 }
2405
2406 int
2407 hivex_node_delete_child (hive_h *h, hive_node_h node)
2408 {
2409   if (!h->writable) {
2410     errno = EROFS;
2411     return -1;
2412   }
2413
2414   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
2415     errno = EINVAL;
2416     return -1;
2417   }
2418
2419   if (node == hivex_root (h)) {
2420     if (h->msglvl >= 2)
2421       fprintf (stderr, "hivex_node_delete_child: cannot delete root node\n");
2422     errno = EINVAL;
2423     return -1;
2424   }
2425
2426   hive_node_h parent = hivex_node_parent (h, node);
2427   if (parent == 0)
2428     return -1;
2429
2430   /* Delete node and all its children and values recursively. */
2431   static const struct hivex_visitor visitor = { .node_end = delete_node };
2432   if (hivex_visit_node (h, node, &visitor, sizeof visitor, NULL, 0) == -1)
2433     return -1;
2434
2435   /* Delete the link from parent to child.  We need to find the lf/lh
2436    * record which contains the offset and remove the offset from that
2437    * record, then decrement the element count in that record, and
2438    * decrement the overall number of subkeys stored in the parent
2439    * node.
2440    */
2441   hive_node_h *unused;
2442   size_t *blocks;
2443   if (get_children (h, parent, &unused, &blocks, GET_CHILDREN_NO_CHECK_NK)== -1)
2444     return -1;
2445   free (unused);
2446
2447   size_t i, j;
2448   for (i = 0; blocks[i] != 0; ++i) {
2449     struct ntreg_hbin_block *block =
2450       (struct ntreg_hbin_block *) (h->addr + blocks[i]);
2451
2452     if (block->id[0] == 'l' && (block->id[1] == 'f' || block->id[1] == 'h')) {
2453       struct ntreg_lf_record *lf = (struct ntreg_lf_record *) block;
2454
2455       size_t nr_subkeys_in_lf = le16toh (lf->nr_keys);
2456
2457       for (j = 0; j < nr_subkeys_in_lf; ++j)
2458         if (le32toh (lf->keys[j].offset) + 0x1000 == node) {
2459           for (; j < nr_subkeys_in_lf - 1; ++j)
2460             memcpy (&lf->keys[j], &lf->keys[j+1], sizeof (lf->keys[j]));
2461           lf->nr_keys = htole16 (nr_subkeys_in_lf - 1);
2462           goto found;
2463         }
2464     }
2465   }
2466   if (h->msglvl >= 2)
2467     fprintf (stderr, "hivex_node_delete_child: could not find parent to child link\n");
2468   errno = ENOTSUP;
2469   return -1;
2470
2471  found:;
2472   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + parent);
2473   size_t nr_subkeys_in_nk = le32toh (nk->nr_subkeys);
2474   nk->nr_subkeys = htole32 (nr_subkeys_in_nk - 1);
2475
2476   if (h->msglvl >= 2)
2477     fprintf (stderr, "hivex_node_delete_child: updating nr_subkeys in parent 0x%zx to %zu\n",
2478              parent, nr_subkeys_in_nk);
2479
2480   return 0;
2481 }
2482
2483 int
2484 hivex_node_set_values (hive_h *h, hive_node_h node,
2485                        size_t nr_values, const hive_set_value *values,
2486                        int flags)
2487 {
2488   if (!h->writable) {
2489     errno = EROFS;
2490     return -1;
2491   }
2492
2493   if (!IS_VALID_BLOCK (h, node) || !BLOCK_ID_EQ (h, node, "nk")) {
2494     errno = EINVAL;
2495     return -1;
2496   }
2497
2498   /* Delete all existing values. */
2499   if (delete_values (h, node) == -1)
2500     return -1;
2501
2502   if (nr_values == 0)
2503     return 0;
2504
2505   /* Allocate value list node.  Value lists have no id field. */
2506   static const char nul_id[2] = { 0, 0 };
2507   size_t seg_len =
2508     sizeof (struct ntreg_value_list) + (nr_values - 1) * sizeof (uint32_t);
2509   size_t vallist_offs = allocate_block (h, seg_len, nul_id);
2510   if (vallist_offs == 0)
2511     return -1;
2512
2513   struct ntreg_nk_record *nk = (struct ntreg_nk_record *) (h->addr + node);
2514   nk->nr_values = htole32 (nr_values);
2515   nk->vallist = htole32 (vallist_offs - 0x1000);
2516
2517   struct ntreg_value_list *vallist =
2518     (struct ntreg_value_list *) (h->addr + vallist_offs);
2519
2520   size_t i;
2521   for (i = 0; i < nr_values; ++i) {
2522     /* Allocate vk record to store this (key, value) pair. */
2523     static const char vk_id[2] = { 'v', 'k' };
2524     seg_len = sizeof (struct ntreg_vk_record) + strlen (values[i].key);
2525     size_t vk_offs = allocate_block (h, seg_len, vk_id);
2526     if (vk_offs == 0)
2527       return -1;
2528
2529     vallist->offset[i] = htole32 (vk_offs - 0x1000);
2530
2531     struct ntreg_vk_record *vk = (struct ntreg_vk_record *) (h->addr + vk_offs);
2532     size_t name_len = strlen (values[i].key);
2533     vk->name_len = htole16 (name_len);
2534     strcpy (vk->name, values[i].key);
2535     vk->data_type = htole32 (values[i].t);
2536     vk->data_len = htole16 (values[i].len);
2537     vk->flags = name_len == 0 ? 0 : 1;
2538
2539     if (values[i].len <= 4)     /* Store data inline. */
2540       memcpy (&vk->data_offset, values[i].value, values[i].len);
2541     else {
2542       size_t offs = allocate_block (h, values[i].len + 4, nul_id);
2543       if (offs == 0)
2544         return -1;
2545       memcpy (h->addr + offs + 4, values[i].value, values[i].len);
2546       vk->data_offset = htole32 (offs - 0x1000);
2547     }
2548
2549     if (name_len * 2 > le32toh (nk->max_vk_name_len))
2550       /* * 2 for UTF16-LE "reencoding" */
2551       nk->max_vk_name_len = htole32 (name_len * 2);
2552     if (values[i].len > le32toh (nk->max_vk_data_len))
2553       nk->max_vk_data_len = htole32 (values[i].len);
2554   }
2555
2556   return 0;
2557 }