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