Changeset 145

Timestamp:

02/15/09 18:36:20 (16 years ago)

Author:

tim

Message:

decoupled value parsing from key parsing

moved linking of value records and data records up to the load layer

rewrote key/value/data linking algorithm in reglookup-recover which improved recovery results

fixed a NULL pointer dereference in range_list.c

Location:

trunk

Files:

• Makefile (modified) (1 diff)
• include/regfi.h (modified) (6 diffs)
• lib/range_list.c (modified) (2 diffs)
• lib/regfi.c (modified) (14 diffs)
• src/reglookup-recover.c (modified) (12 diffs)

trunk/Makefile

@@ -11 +11 @@
 
 CC=gcc
-#OPTS=-std=gnu89 -pedantic -Wall -ggdb
-OPTS=-std=gnu89 -pedantic -Wall
+OPTS=-std=gnu89 -pedantic -Wall -ggdb
+#OPTS=-std=gnu89 -pedantic -Wall
 INC=-I/usr/local/include
 LIB=-L/usr/local/lib -lm

trunk/include/regfi.h

@@ -191 +191 @@
 
 
-typedef struct 
+typedef struct _regfi_subkey_list
 {
   /* Real offset of this record's cell in the file */
@@ -210 +210 @@
   bool recursive_type;  
 } REGFI_SUBKEY_LIST;
+
+
+typedef uint32 REGFI_VALUE_LIST_ELEM;
+typedef struct _regfi_value_list
+{
+  /* Actual number of values referenced by this list.  
+   * May differ from parent key's num_values if there were parsing errors. 
+   */
+  uint32 num_values;
+
+  REGFI_VALUE_LIST_ELEM* elements;
+} REGFI_VALUE_LIST;
 
 
@@ -269 +281 @@
 
   /* link in the other records here */
-  REGFI_VK_REC** values;
+  REGFI_VALUE_LIST* values;
   REGFI_SUBKEY_LIST* subkeys;
   
@@ -427 +439 @@
 /* Middle-layer structure caching, loading, and linking */
 /********************************************************/
-REGFI_HBIN*           regfi_lookup_hbin(REGFI_FILE* file, uint32 offset);
+REGFI_HBIN*           regfi_lookup_hbin(REGFI_FILE* file, uint32 voffset);
 REGFI_NK_REC*         regfi_load_key(REGFI_FILE* file, uint32 offset, 
                                      bool strict);
@@ -433 +445 @@
                                             uint32 num_keys, uint32 max_size, 
                                             bool strict);
-REGFI_VK_REC**        regfi_load_valuelist(REGFI_FILE* file, uint32 offset, 
+REGFI_VK_REC*         regfi_load_value(REGFI_FILE* file, uint32 offset, 
+                                       bool strict);
+REGFI_VALUE_LIST*     regfi_load_valuelist(REGFI_FILE* file, uint32 offset, 
                                            uint32 num_values, uint32 max_size, 
                                            bool strict);
@@ -465 +479 @@
                                      uint32 max_size, bool strict);
 
-uint8*                regfi_parse_data(REGFI_FILE* file, uint32 offset, 
+uint8*                regfi_parse_data(REGFI_FILE* file, 
+                                       uint32 data_type, uint32 offset, 
                                        uint32 length, uint32 max_size, 
-                                       bool strict);
+                                       bool data_in_offset, bool strict);
 
 REGFI_SK_REC*         regfi_parse_sk(REGFI_FILE* file, uint32 offset, 

trunk/lib/range_list.c

@@ -265 +265 @@
   range_list_element* elem;
 
+  if(rl->size == 0)
+    return -1;
+
   if((offset < rl->elements[0]->offset)
      || (offset > rl->elements[rl->size-1]->offset 
          + rl->elements[rl->size-1]->length))
-    return -1;
+    return -2;
 
   prev_idx = range_list_find_previous(rl, offset);
@@ -275 +278 @@
     return prev_idx;
 
-  return -2;
+  return -3;
 }
 

trunk/lib/regfi.c

@@ -475 +475 @@
  * The offset is a virtual file offset.
  *******************************************************************/
-static bool regfi_offset_in_hbin(REGFI_HBIN* hbin, uint32 offset)
+static bool regfi_offset_in_hbin(REGFI_HBIN* hbin, uint32 voffset)
 {
   if(!hbin)
     return false;
 
-  if((offset > hbin->first_hbin_off) 
-     && (offset < (hbin->first_hbin_off + hbin->block_size)))
+  if((voffset > hbin->first_hbin_off) 
+     && (voffset < (hbin->first_hbin_off + hbin->block_size)))
     return true;
                 
@@ -493 +493 @@
  * block for it.  NULL if one doesn't exist.
  *******************************************************************/
-REGFI_HBIN* regfi_lookup_hbin(REGFI_FILE* file, uint32 offset)
-{
-  return (REGFI_HBIN*)range_list_find_data(file->hbins, offset+REGFI_REGF_SIZE);
+REGFI_HBIN* regfi_lookup_hbin(REGFI_FILE* file, uint32 voffset)
+{
+  return (REGFI_HBIN*)range_list_find_data(file->hbins, voffset+REGFI_REGF_SIZE);
 }
 
@@ -870 +870 @@
 
 
-uint32* regfi_parse_valuelist(REGFI_FILE* file, uint32 offset, 
-                              uint32 num_values, bool strict)
-{
-  uint32* ret_val;
+REGFI_VALUE_LIST* regfi_parse_valuelist(REGFI_FILE* file, uint32 offset, 
+                                        uint32 num_values, bool strict)
+{
+  REGFI_VALUE_LIST* ret_val;
   uint32 i, cell_length, length, read_len;
   bool unalloc;
@@ -886 +886 @@
   if(cell_length != (cell_length & 0xFFFFFFF8))
   {
+    regfi_add_message(file, REGFI_MSG_WARN, "Cell length not a multiple of 8"
+                      " while parsing value list at offset 0x%.8X.", offset);
     if(strict)
       return NULL;
     cell_length = cell_length & 0xFFFFFFF8;
   }
+
   if((num_values * sizeof(uint32)) > cell_length-sizeof(uint32))
   {
     regfi_add_message(file, REGFI_MSG_WARN, "Too many values found"
                       " while parsing value list at offset 0x%.8X.", offset);
-    /* XXX: During non-strict, should reduce num_values appropriately and
-     *      continue instead of bailing out.
-     */
-    return NULL;
+    if(strict)
+      return NULL;
+    num_values = cell_length/sizeof(uint32) - sizeof(uint32);
   }
 
   read_len = num_values*sizeof(uint32);
-  ret_val = (uint32*)malloc(read_len);
+  ret_val = (REGFI_VALUE_LIST*)malloc(sizeof(REGFI_VALUE_LIST));
   if(ret_val == NULL)
     return NULL;
 
+  ret_val->elements = (REGFI_VALUE_LIST_ELEM*)malloc(read_len);
+  if(ret_val->elements == NULL)
+  {
+    free(ret_val);
+    return NULL;
+  }
+  ret_val->num_values = num_values;
+
   length = read_len;
-  if((regfi_read(file->fd, (uint8*)ret_val, &length) != 0) || length != read_len)
+  if((regfi_read(file->fd, (uint8*)ret_val->elements, &length) != 0) 
+     || length != read_len)
   {
     regfi_add_message(file, REGFI_MSG_ERROR, "Failed to read value pointers"
                       " while parsing value list at offset 0x%.8X.", offset);
+    free(ret_val->elements);
     free(ret_val);
     return NULL;
@@ -917 +929 @@
   {
     /* Fix endianness */
-    ret_val[i] = IVAL(&ret_val[i], 0);
+    ret_val->elements[i] = IVAL(&ret_val->elements[i], 0);
 
     /* Validate the first num_values values to ensure they make sense */
     if(strict)
     {
-      if((ret_val[i] + REGFI_REGF_SIZE > file->file_length)
-         || ((ret_val[i] & 0xFFFFFFF8) != ret_val[i]))
+      /* XXX: Need to revisit this file length check when we start dealing 
+       *      with partial files. */
+      if((ret_val->elements[i] + REGFI_REGF_SIZE > file->file_length)
+         || ((ret_val->elements[i] & 0xFFFFFFF8) != ret_val->elements[i]))
       {
-        regfi_add_message(file, REGFI_MSG_ERROR, "Invalid value pointer"
+        regfi_add_message(file, REGFI_MSG_WARN, "Invalid value pointer"
                           " (0x%.8X) found while parsing value list at offset"
-                          " 0x%.8X.", ret_val[i], offset);
+                          " 0x%.8X.", ret_val->elements[i], offset);
+        free(ret_val->elements);
         free(ret_val);
         return NULL;
@@ -940 +955 @@
 
 /******************************************************************************
+ ******************************************************************************/
+REGFI_VK_REC* regfi_load_value(REGFI_FILE* file, uint32 offset, bool strict)
+{
+  REGFI_VK_REC* ret_val = NULL;
+  REGFI_HBIN* hbin;
+  uint32 data_offset, data_maxsize;
+
+  hbin = regfi_lookup_hbin(file, offset - REGFI_REGF_SIZE);
+  if(!hbin)
+    return NULL;
+  
+  ret_val = regfi_parse_vk(file, offset, 
+                           hbin->block_size + hbin->file_off - offset, strict);
+
+  if(ret_val == NULL)
+    return NULL;
+
+  if(ret_val->data_size == 0)
+    ret_val->data = NULL;
+  else
+  {
+    if(ret_val->data_in_offset)
+    {
+      ret_val->data = regfi_parse_data(file, ret_val->type, ret_val->data_off,
+                                       ret_val->data_size, 4,
+                                       ret_val->data_in_offset, strict);
+    }
+    else
+    {
+      hbin = regfi_lookup_hbin(file, ret_val->data_off);
+      if(hbin)
+      {
+        data_offset = ret_val->data_off+REGFI_REGF_SIZE;
+        data_maxsize = hbin->block_size + hbin->file_off - data_offset;
+        ret_val->data = regfi_parse_data(file, ret_val->type, data_offset, 
+                                         ret_val->data_size, data_maxsize, 
+                                         ret_val->data_in_offset, strict);
+      }
+      else
+      {
+        regfi_add_message(file, REGFI_MSG_WARN, "Could not find HBIN for data"
+                          " while parsing VK record at offset 0x%.8X.", 
+                          ret_val->offset);
+        ret_val->data = NULL;
+      }
+    }
+
+    if(ret_val->data == NULL)
+    {
+      regfi_add_message(file, REGFI_MSG_WARN, "Could not parse data record"
+                        " while parsing VK record at offset 0x%.8X.", 
+                        ret_val->offset);
+    }
+  }
+
+  return ret_val;
+}
+
+
+/******************************************************************************
  * If !strict, the list may contain NULLs, VK records may point to NULL.
  ******************************************************************************/
-REGFI_VK_REC** regfi_load_valuelist(REGFI_FILE* file, uint32 offset, 
-                                   uint32 num_values, uint32 max_size, 
-                                   bool strict)
-{
-  REGFI_VK_REC** ret_val;
-  REGFI_HBIN* hbin;
-  uint32 i, vk_offset, vk_max_length, usable_num_values;
-  uint32* voffsets;
+REGFI_VALUE_LIST* regfi_load_valuelist(REGFI_FILE* file, uint32 offset, 
+                                       uint32 num_values, uint32 max_size, 
+                                       bool strict)
+{
+  uint32 usable_num_values;
 
   if((num_values+1) * sizeof(uint32) > max_size)
   {
+    regfi_add_message(file, REGFI_MSG_WARN, "Number of values indicated by"
+                      " parent key (%d) would cause cell to straddle HBIN"
+                      " boundary while loading value list at offset"
+                      " 0x%.8X.", num_values, offset);
     if(strict)
       return NULL;
@@ -960 +1036 @@
     usable_num_values = num_values;
 
-  voffsets = regfi_parse_valuelist(file, offset, usable_num_values, strict);
-  if(voffsets == NULL)
-    return NULL;
-
-  ret_val = (REGFI_VK_REC**)zalloc(sizeof(REGFI_VK_REC*) * usable_num_values);
-  if(ret_val == NULL)
-  {
-    free(voffsets);
-    return NULL;
-  }
-  
-  for(i=0; i < usable_num_values; i++)
-  {
-    hbin = regfi_lookup_hbin(file, voffsets[i]);
-    if(!hbin)
-    {
-      free(voffsets);
-      free(ret_val);
-      return NULL;
-    }
-
-    vk_offset =  voffsets[i] + REGFI_REGF_SIZE;
-    vk_max_length = hbin->block_size + hbin->file_off - vk_offset;
-    ret_val[i] = regfi_parse_vk(file, vk_offset, vk_max_length, strict);
-    if(ret_val[i] == NULL)
-    { /* If we're being strict, throw out the whole list.
-       * Otherwise, let it be NULL.
-       */
-      if(strict)
-      {
-        free(voffsets);
-        free(ret_val);
-        return NULL;
-      }
-    }
-  }
-
-  free(voffsets);
-  return ret_val;
+  return regfi_parse_valuelist(file, offset, usable_num_values, strict);
 }
 
@@ -1051 +1089 @@
       nk->values = regfi_load_valuelist(file, off, nk->num_values, max_length, 
                                         true);
-      if(strict && nk->values == NULL)
+      if(nk->values == NULL)
       {
-        regfi_add_message(file, REGFI_MSG_ERROR, "Could not load value list"
-                          " for NK record at offset 0x%.8X.",
-                          offset);
-        free(nk);
-        return NULL;
+        regfi_add_message(file, REGFI_MSG_WARN, "Could not load value list"
+                          " for NK record at offset 0x%.8X.", offset);
+        if(strict)
+        {
+          free(nk);
+          return NULL;
+        }
       }
-
     }
   }
@@ -1271 +1310 @@
 void regfi_key_free(REGFI_NK_REC* nk)
 {
-  uint32 i;
-  
   if((nk->values != NULL) && (nk->values_off!=REGFI_OFFSET_NONE))
   {
-    for(i=0; i < nk->num_values; i++)
-    {
-      if(nk->values[i]->valuename != NULL)
-        free(nk->values[i]->valuename);
-      if(nk->values[i]->data != NULL)
-        free(nk->values[i]->data);
-      free(nk->values[i]);
-    }
+    if(nk->values->elements != NULL)
+      free(nk->values->elements);
     free(nk->values);
   }
@@ -1628 +1659 @@
 {
   REGFI_VK_REC* ret_val = NULL;
-  if(i->cur_value < i->cur_key->num_values)
-    ret_val = i->cur_key->values[i->cur_value];
+  uint32 voffset;
+
+  if(i->cur_key->values != NULL && i->cur_key->values->elements != NULL)
+  {
+    if(i->cur_value < i->cur_key->values->num_values)
+    {
+      voffset = i->cur_key->values->elements[i->cur_value];
+      ret_val = regfi_load_value(i->f, voffset+REGFI_REGF_SIZE, true);
+    }
+  }
 
   return ret_val;
@@ -2050 +2089 @@
  *******************************************************************/
 REGFI_VK_REC* regfi_parse_vk(REGFI_FILE* file, uint32 offset, 
-                            uint32 max_size, bool strict)
+                             uint32 max_size, bool strict)
 {
   REGFI_VK_REC* ret_val;
-  REGFI_HBIN *hbin;
   uint8 vk_header[REGFI_VK_MIN_LENGTH];
   uint32 raw_data_size, length, cell_length;
-  uint32 data_offset, data_maxsize;
   bool unalloc = false;
 
@@ -2159 +2196 @@
   }
 
-  if(ret_val->data_size == 0)
-    ret_val->data = NULL;
-  else
-  {
-    if(ret_val->data_in_offset)
-    {
-      ret_val->data = regfi_parse_data(file, ret_val->data_off, 
-                                       raw_data_size, 4, strict);
-    }
-    else
-    {
-      hbin = regfi_lookup_hbin(file, ret_val->data_off);
-      if(hbin)
-      {
-        data_offset = ret_val->data_off+REGFI_REGF_SIZE;
-        data_maxsize = hbin->block_size + hbin->file_off - data_offset;
-        ret_val->data = regfi_parse_data(file, data_offset, raw_data_size,
-                                         data_maxsize, strict);
-        
-      }
-      else
-      {
-        regfi_add_message(file, REGFI_MSG_WARN, "Could not find hbin for data"
-                          " while parsing VK record at offset 0x%.8X.", offset);
-        ret_val->data = NULL;
-      }
-    }
-
-    if(ret_val->data == NULL)
-    {
-      regfi_add_message(file, REGFI_MSG_WARN, "Could not parse data record"
-                        " while parsing VK record at offset 0x%.8X.", offset);
-    }
-  }
-
   return ret_val;
 }
 
 
-uint8* regfi_parse_data(REGFI_FILE* file, uint32 offset, uint32 length,
-                        uint32 max_size, bool strict)
+uint8* regfi_parse_data(REGFI_FILE* file, 
+                        uint32 data_type, uint32 offset,
+                        uint32 length, uint32 max_size, 
+                        bool data_in_offset, bool strict)
 {
   uint8* ret_val;
@@ -2207 +2211 @@
 
   /* The data is typically stored in the offset if the size <= 4 */
-  if (length & REGFI_VK_DATA_IN_OFFSET)
-  {
-    length = length & ~REGFI_VK_DATA_IN_OFFSET;
+  if(data_in_offset)
+  {
     if(length > 4)
     {
@@ -2244 +2247 @@
     if(cell_length > max_size)
     {
-      regfi_add_message(file, REGFI_MSG_WARN, "Cell extends past hbin boundary"
-                        " while parsing data record at offset 0x%.8X.", 
+      regfi_add_message(file, REGFI_MSG_WARN, "Cell extends past HBIN boundary"
+                        " while parsing data record at offset 0x%.8X.",
                         offset);
       if(strict)

trunk/src/reglookup-recover.c

@@ -416 +416 @@
 
 
+int extractVKs(REGFI_FILE* f,
+               range_list* unalloc_cells,
+               range_list* unalloc_values)
+{
+  const range_list_element* cur_elem;
+  REGFI_VK_REC* vk;
+  uint32 i, j;
+
+  for(i=0; i < range_list_size(unalloc_cells); i++)
+  {
+    printMsgs(f);
+    cur_elem = range_list_get(unalloc_cells, i);
+    for(j=0; j <= cur_elem->length; j+=8)
+    {
+      vk = regfi_parse_vk(f, cur_elem->offset+j, 
+                           cur_elem->length-j, false);
+      printMsgs(f);
+
+      if(vk != NULL)
+      {
+        if(!range_list_add(unalloc_values, vk->offset,
+                           vk->cell_size, vk))
+        {
+          fprintf(stderr, "ERROR: Couldn't add value to unalloc_values.\n");
+          return 20;
+        }
+        j+=vk->cell_size-8;
+      }
+    }
+  }
+
+  /* Remove value ranges from the unalloc_cells before we continue. */
+  for(i=0; i<range_list_size(unalloc_values); i++)
+  {
+    cur_elem = range_list_get(unalloc_values, i);
+    if(!removeRange(unalloc_cells, cur_elem->offset, cur_elem->length))
+      return 30;
+  }
+
+  return 0;
+}
+
+
+int extractDataCells(REGFI_FILE* f,
+                     range_list* unalloc_cells,
+                     range_list* unalloc_values)
+{
+  const range_list_element* cur_elem;
+  REGFI_VK_REC* vk;
+  REGFI_HBIN* hbin;
+  uint32 i, off, data_offset, data_maxsize;
+
+  for(i=0; i<range_list_size(unalloc_values); i++)
+  {
+    cur_elem = range_list_get(unalloc_values, i);
+    vk = (REGFI_VK_REC*)cur_elem->data;
+    if(vk == NULL)
+      return 40;
+
+    if(vk->data_size == 0)
+      vk->data = NULL;
+    else
+    {
+      off = vk->data_off+REGFI_REGF_SIZE;
+
+      if(vk->data_in_offset)
+      {
+        vk->data = regfi_parse_data(f, vk->type, vk->data_off,
+                                    vk->data_size, 4,
+                                    vk->data_in_offset, false);
+      }
+      else if(range_list_has_range(unalloc_cells, off, vk->data_size))
+      {
+        hbin = regfi_lookup_hbin(f, vk->data_off);
+        if(hbin)
+        {
+          data_offset = vk->data_off+REGFI_REGF_SIZE;
+          data_maxsize = hbin->block_size + hbin->file_off - data_offset;
+          vk->data = regfi_parse_data(f, vk->type, data_offset, 
+                                      vk->data_size, data_maxsize, 
+                                      vk->data_in_offset, false);
+          if(vk->data != NULL)
+          {
+            /* XXX: This strict checking prevents partial recovery of data 
+             *      cells.  Also, see code for regfi_parse_data and note that
+             *      lengths indicated in VK records are sometimes just plain 
+             *      wrong.  Need a feedback mechanism to be more fuzzy with 
+             *      data cell lengths and the ranges removed. 
+             */
+            /* A data record was recovered. Remove from unalloc_cells. */
+            if(!removeRange(unalloc_cells, off, vk->data_size))
+              return 50;
+          }
+        }
+        else
+          vk->data = NULL;
+      }
+    }
+  }
+
+  return 0;
+}
+
+
 /* NOTE: unalloc_keys should be an empty range_list. */
 int extractKeys(REGFI_FILE* f, 
@@ -459 +563 @@
 }
 
-
 int extractValueLists(REGFI_FILE* f,
                       range_list* unalloc_cells,
-                      range_list* unalloc_keys)
+                      range_list* unalloc_keys,
+                      range_list* unalloc_linked_values)
 {
   REGFI_NK_REC* nk;
+  REGFI_VK_REC* vk;
   REGFI_HBIN* hbin;
   const range_list_element* cur_elem;
@@ -485 +590 @@
         off = nk->values_off + REGFI_REGF_SIZE;
         max_length = hbin->block_size + hbin->file_off - off;
-        /* XXX: This is a hack.  We parse all value-lists, VK records,
-         *      and data records without regard for current allocation status.  
-         *      On the off chance that such a record correctly parsed but is 
-         *      actually a reallocated structure used by something else, we 
-         *      simply prune it after the fact.  Would be faster to check this
-         *      up front somehow.
-         */
-        nk->values = regfi_load_valuelist(f, off, nk->num_values, max_length,
-                                          false);
-        values_length = (nk->num_values+1)*sizeof(uint32);
-        if(values_length != (values_length & 0xFFFFFFF8))
-          values_length = (values_length & 0xFFFFFFF8) + 8;
-
-        if(nk->values != NULL)
+        nk->values = regfi_load_valuelist(f, off, nk->num_values, 
+                                          max_length, false);
+        if(nk->values != NULL && nk->values->elements != NULL)
         {
+          /* Number of elements in the value list may be shorter than advertised 
+           * by NK record due to cell truncation.  We'll consider this valid and 
+           * only throw out the whole value list if it bleeds into an already 
+           * parsed structure.
+           */
+          values_length = (nk->values->num_values+1)*sizeof(uint32);
+          if(values_length != (values_length & 0xFFFFFFF8))
+            values_length = (values_length & 0xFFFFFFF8) + 8;
+
           if(!range_list_has_range(unalloc_cells, off, values_length))
           { /* We've parsed a values-list which isn't in the unallocated list,
-             * so prune it. 
+             * so prune it.
              */
-            for(j=0; j<nk->num_values; j++)
-            {
-              if(nk->values[j] != NULL)
-              {
-                if(nk->values[j]->data != NULL)
-                  free(nk->values[j]->data);
-                free(nk->values[j]);
-              }
-            }
+            free(nk->values->elements);
             free(nk->values);
             nk->values = NULL;
@@ -523 +618 @@
               return 20;
 
-            for(j=0; j < nk->num_values; j++)
+            for(j=0; j < nk->values->num_values; j++)
             {
-              if(nk->values[j] != NULL)
+              /* Don't bother to restrict cell length here, since we'll
+               * check our unalloc_cells range_list later. 
+               */
+              vk = regfi_parse_vk(f, nk->values->elements[j]+REGFI_REGF_SIZE,
+                                  0x7FFFFFFF, false);
+              printMsgs(f);
+              
+              if(vk != NULL)
               {
-                if(!range_list_has_range(unalloc_cells, nk->values[j]->offset, 
-                                         nk->values[j]->cell_size))
-                { /* We've parsed a value which isn't in the unallocated list,
-                   * so prune it.
-                   */
-                  if(nk->values[j]->data != NULL)
-                    free(nk->values[j]->data);
-                  free(nk->values[j]);
-                  nk->values[j] = NULL;
+                if(range_list_has_range(unalloc_cells, 
+                                        vk->offset, vk->cell_size))
+                {
+                  if(!range_list_add(unalloc_linked_values, vk->offset,
+                                     vk->cell_size, vk))
+                  {
+                    free(vk);
+                    return 30;
+                  }
+
+                  if(!removeRange(unalloc_cells, vk->offset, vk->cell_size))
+                    return 40;
                 }
                 else
-                {
-                  /* A VK record was recovered.  Remove from unalloc_cells
-                   * and inspect data.
-                   */
-                  if(!removeRange(unalloc_cells, nk->values[j]->offset,
-                                  nk->values[j]->cell_size))
-                    return 21;
-
-                  /* Don't bother pruning or removing from unalloc_cells if 
-                   * there is no data, or it is stored in the offset.
-                   */
-                  if(nk->values[j]->data != NULL && !nk->values[j]->data_in_offset)
-                  {
-                    off = nk->values[j]->data_off+REGFI_REGF_SIZE;
-                    if(!range_list_has_range(unalloc_cells, off, 
-                                             nk->values[j]->data_size))
-                    { /* We've parsed a data cell which isn't in the unallocated 
-                       * list, so prune it.
-                       */
-                      free(nk->values[j]->data);
-                      nk->values[j]->data = NULL;
-                    }
-                    else
-                    { /*A data record was recovered. Remove from unalloc_cells.*/
-                      if(!removeRange(unalloc_cells, off, 
-                                      nk->values[j]->data_size))
-                        return 22;
-                    }
-                  }
-                }
+                  free(vk);
               }
             }
@@ -579 +655 @@
 }
 
-
-/* NOTE: unalloc_values should be an empty range_list. */
-int extractValues(REGFI_FILE* f,
-                  range_list* unalloc_cells,
-                  range_list* unalloc_values)
-{
-  const range_list_element* cur_elem;
-  REGFI_VK_REC* vk;
-  uint32 i, j, off;
-
-  for(i=0; i < range_list_size(unalloc_cells); i++)
-  {
-    printMsgs(f);
-    cur_elem = range_list_get(unalloc_cells, i);
-    for(j=0; j <= cur_elem->length; j+=8)
-    {
-      vk = regfi_parse_vk(f, cur_elem->offset+j, 
-                           cur_elem->length-j, false);
-      printMsgs(f);
-
-      if(vk != NULL)
-      {
-        if(!range_list_add(unalloc_values, vk->offset,
-                           vk->cell_size, vk))
-        {
-          fprintf(stderr, "ERROR: Couldn't add value to unalloc_values.\n");
-          return 20;
-        }
-        j+=vk->cell_size-8;
-      }
-    }
-  }
-  
-  /* Remove value ranges from the unalloc_cells before we continue. */
-  for(i=0; i<range_list_size(unalloc_values); i++)
-  {
-    cur_elem = range_list_get(unalloc_values, i);
-    if(!removeRange(unalloc_cells, cur_elem->offset, cur_elem->length))
-      return 30;
-  }
-
-  /* Now see if the data associated with each value is intact */
-  for(i=0; i<range_list_size(unalloc_values); i++)
-  {
-    cur_elem = range_list_get(unalloc_values, i);
-    vk = (REGFI_VK_REC*)cur_elem->data;
-    if(vk == NULL)
-      return 40;
-
-    if(vk->data != NULL && !vk->data_in_offset)
-    {
-      off = vk->data_off+REGFI_REGF_SIZE;
-      if(!range_list_has_range(unalloc_cells, off, vk->data_size))
-      { /* We've parsed a data cell which isn't in the unallocated 
-         * list, so prune it.
-         */
-        free(vk->data);
-        vk->data = NULL;
-      }
-      else
-      { /*A data record was recovered. Remove from unalloc_cells.*/
-        if(!removeRange(unalloc_cells, off, vk->data_size))
-          return 50;
-      }
-    }
-  }
-
-  return 0;
-}
 
 
@@ -699 +706 @@
   range_list* unalloc_cells;
   range_list* unalloc_keys;
+  range_list* unalloc_linked_values;
   range_list* unalloc_values;
   range_list* unalloc_sks;
@@ -707 +715 @@
   REGFI_VK_REC* tmp_value;
   uint32 argi, arge, i, j, ret, num_unalloc_keys;
-  /* uint32 test_offset;*/
   
   /* Process command line arguments */
@@ -772 +779 @@
     return 10;
 
+  unalloc_linked_values = range_list_new();
+  if(unalloc_linked_values == NULL)
+    return 10;
+
   unalloc_values = range_list_new();
   if(unalloc_values == NULL)
@@ -787 +798 @@
   }
 
-  ret = extractValueLists(f, unalloc_cells, unalloc_keys);
+  ret = extractValueLists(f, unalloc_cells, unalloc_keys,unalloc_linked_values);
   if(ret != 0)
   {
@@ -794 +805 @@
   }
 
-  /* Carve any orphan values and associated data */
-  ret = extractValues(f, unalloc_cells, unalloc_values);
+  /* Carve any orphan values */
+  ret = extractVKs(f, unalloc_cells, unalloc_values);
   if(ret != 0)
   {
-    fprintf(stderr, "ERROR: extractValues() failed with %d.\n", ret);
+    fprintf(stderr, "ERROR: extractVKs() failed with %d.\n", ret);
     return ret;
   }
 
+  /* Carve any data associated with VK records */
+  ret = extractDataCells(f, unalloc_cells, unalloc_linked_values);
+  if(ret != 0)
+  {
+    fprintf(stderr, "ERROR: extractDataCells() failed with %d.\n", ret);
+    return ret;
+  }
+  ret = extractDataCells(f, unalloc_cells, unalloc_values);
+  if(ret != 0)
+  {
+    fprintf(stderr, "ERROR: extractDataCells() failed with %d.\n", ret);
+    return ret;
+  }
+  
   /* Carve any SK records */
   ret = extractSKs(f, unalloc_cells, unalloc_sks);
@@ -832 +857 @@
   
   /* Now start the output */
-
   for(i=0; i < num_unalloc_keys; i++)
   {
@@ -850 +874 @@
 
       sprintf(tmp_path, "%s/%s", parent_paths[i], tmp_name);
-      for(j=0; j < tmp_key->num_values; j++)
+      for(j=0; j < tmp_key->values->num_values; j++)
       {
-        tmp_value = tmp_key->values[j];
+        tmp_value = 
+          (REGFI_VK_REC*)range_list_find_data(unalloc_linked_values, 
+                                              tmp_key->values->elements[j]
+                                              + REGFI_REGF_SIZE);
         if(tmp_value != NULL)
           printValue(f, tmp_value, tmp_path);