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