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