subprojects/gvdb/gvdb/gvdb-reader.c

   1 /*
   2  * Copyright © 2010 Codethink Limited
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Lesser General Public
  15  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
  16  *
  17  * Author: Ryan Lortie <desrt@desrt.ca>
  18  */
  19
  20 #include "gvdb-reader.h"
  21 #include "gvdb-format.h"
  22
  23 #include <string.h>
  24
  25 struct _GvdbTable {
  26   GBytes *bytes;
  27
  28   const gchar *data;
  29   gsize size;
  30
  31   gboolean byteswapped;
  32   gboolean trusted;
  33
  34   const guint32_le *bloom_words;
  35   guint32 n_bloom_words;
  36   guint bloom_shift;
  37
  38   const guint32_le *hash_buckets;
  39   guint32 n_buckets;
  40
  41   struct gvdb_hash_item *hash_items;
  42   guint32 n_hash_items;
  43 };
  44
  45 static const gchar *
  46 gvdb_table_item_get_key (GvdbTable                   *file,
  47                          const struct gvdb_hash_item *item,
  48                          gsize                       *size)
  49 {
  50   guint32 start, end;
  51
  52   start = guint32_from_le (item->key_start);
  53   *size = guint16_from_le (item->key_size);
  54   end = start + *size;
  55
  56   if G_UNLIKELY (start > end || end > file->size)
  57     return NULL;
  58
  59   return file->data + start;
  60 }
  61
  62 static gconstpointer
  63 gvdb_table_dereference (GvdbTable                 *file,
  64                         const struct gvdb_pointer *pointer,
  65                         gint                       alignment,
  66                         gsize                     *size)
  67 {
  68   guint32 start, end;
  69
  70   start = guint32_from_le (pointer->start);
  71   end = guint32_from_le (pointer->end);
  72
  73   if G_UNLIKELY (start > end || end > file->size || start & (alignment - 1))
  74     return NULL;
  75
  76   *size = end - start;
  77
  78   return file->data + start;
  79 }
  80
  81 static void
  82 gvdb_table_setup_root (GvdbTable                 *file,
  83                        const struct gvdb_pointer *pointer)
  84 {
  85   const struct gvdb_hash_header *header;
  86   guint32 n_bloom_words;
  87   guint32 n_buckets;
  88   gsize size;
  89
  90   header = gvdb_table_dereference (file, pointer, 4, &size);
  91
  92   if G_UNLIKELY (header == NULL || size < sizeof *header)
  93     return;
  94
  95   size -= sizeof *header;
  96
  97   n_bloom_words = guint32_from_le (header->n_bloom_words);
  98   n_buckets = guint32_from_le (header->n_buckets);
  99   n_bloom_words &= (1u << 27) - 1;
 100
 101   if G_UNLIKELY (n_bloom_words * sizeof (guint32_le) > size)
 102     return;
 103
 104   file->bloom_words = (gpointer) (header + 1);
 105   size -= n_bloom_words * sizeof (guint32_le);
 106   file->n_bloom_words = n_bloom_words;
 107
 108   if G_UNLIKELY (n_buckets > G_MAXUINT / sizeof (guint32_le) ||
 109                  n_buckets * sizeof (guint32_le) > size)
 110     return;
 111
 112   file->hash_buckets = file->bloom_words + file->n_bloom_words;
 113   size -= n_buckets * sizeof (guint32_le);
 114   file->n_buckets = n_buckets;
 115
 116   if G_UNLIKELY (size % sizeof (struct gvdb_hash_item))
 117     return;
 118
 119   file->hash_items = (gpointer) (file->hash_buckets + n_buckets);
 120   file->n_hash_items = size / sizeof (struct gvdb_hash_item);
 121 }
 122
 123 /**
 124  * gvdb_table_new_from_bytes:
 125  * @bytes: the #GBytes with the data
 126  * @trusted: if the contents of @bytes are trusted
 127  * @error: %NULL, or a pointer to a %NULL #GError
 128  *
 129  * Creates a new #GvdbTable from the contents of @bytes.
 130  *
 131  * This call can fail if the header contained in @bytes is invalid or if @bytes
 132  * is empty; if so, %G_FILE_ERROR_INVAL will be returned.
 133  *
 134  * You should call gvdb_table_free() on the return result when you no
 135  * longer require it.
 136  *
 137  * Returns: a new #GvdbTable
 138  **/
 139 GvdbTable *
 140 gvdb_table_new_from_bytes (GBytes    *bytes,
 141                            gboolean   trusted,
 142                            GError   **error)
 143 {
 144   const struct gvdb_header *header;
 145   GvdbTable *file;
 146
 147   file = g_slice_new0 (GvdbTable);
 148   file->bytes = g_bytes_ref (bytes);
 149   file->data = g_bytes_get_data (bytes, &file->size);
 150   file->trusted = trusted;
 151
 152   if (file->size < sizeof (struct gvdb_header))
 153     goto invalid;
 154
 155   header = (gpointer) file->data;
 156
 157   if (header->signature[0] == GVDB_SIGNATURE0 &&
 158       header->signature[1] == GVDB_SIGNATURE1 &&
 159       guint32_from_le (header->version) == 0)
 160     file->byteswapped = FALSE;
 161
 162   else if (header->signature[0] == GVDB_SWAPPED_SIGNATURE0 &&
 163            header->signature[1] == GVDB_SWAPPED_SIGNATURE1 &&
 164            guint32_from_le (header->version) == 0)
 165     file->byteswapped = TRUE;
 166
 167   else
 168     goto invalid;
 169
 170   gvdb_table_setup_root (file, &header->root);
 171
 172   return file;
 173
 174 invalid:
 175   g_set_error_literal (error, G_FILE_ERROR, G_FILE_ERROR_INVAL, "invalid gvdb header");
 176
 177   g_bytes_unref (file->bytes);
 178
 179   g_slice_free (GvdbTable, file);
 180
 181   return NULL;
 182 }
 183
 184 /**
 185  * gvdb_table_new:
 186  * @filename: a filename
 187  * @trusted: if the contents of @bytes are trusted
 188  * @error: %NULL, or a pointer to a %NULL #GError
 189  *
 190  * Creates a new #GvdbTable using the #GMappedFile for @filename as the
 191  * #GBytes.
 192  *
 193  * This function will fail if the file cannot be opened.
 194  * In that case, the #GError that is returned will be an error from
 195  * g_mapped_file_new().
 196  *
 197  * An empty or corrupt file will result in %G_FILE_ERROR_INVAL.
 198  *
 199  * Returns: a new #GvdbTable
 200  **/
 201 GvdbTable *
 202 gvdb_table_new (const gchar  *filename,
 203                 gboolean      trusted,
 204                 GError      **error)
 205 {
 206   GMappedFile *mapped;
 207   GvdbTable *table;
 208   GBytes *bytes;
 209
 210   mapped = g_mapped_file_new (filename, FALSE, error);
 211   if (!mapped)
 212     return NULL;
 213
 214   bytes = g_mapped_file_get_bytes (mapped);
 215   table = gvdb_table_new_from_bytes (bytes, trusted, error);
 216   g_mapped_file_unref (mapped);
 217   g_bytes_unref (bytes);
 218
 219   g_prefix_error (error, "%s: ", filename);
 220
 221   return table;
 222 }
 223
 224 static gboolean
 225 gvdb_table_bloom_filter (GvdbTable *file,
 226                           guint32    hash_value)
 227 {
 228   guint32 word, mask;
 229
 230   if (file->n_bloom_words == 0)
 231     return TRUE;
 232
 233   word = (hash_value / 32) % file->n_bloom_words;
 234   mask = 1 << (hash_value & 31);
 235   mask |= 1 << ((hash_value >> file->bloom_shift) & 31);
 236
 237   return (guint32_from_le (file->bloom_words[word]) & mask) == mask;
 238 }
 239
 240 static gboolean
 241 gvdb_table_check_name (GvdbTable             *file,
 242                        struct gvdb_hash_item *item,
 243                        const gchar           *key,
 244                        guint                  key_length)
 245 {
 246   const gchar *this_key;
 247   gsize this_size;
 248   guint32 parent;
 249
 250   this_key = gvdb_table_item_get_key (file, item, &this_size);
 251
 252   if G_UNLIKELY (this_key == NULL || this_size > key_length)
 253     return FALSE;
 254
 255   key_length -= this_size;
 256
 257   if G_UNLIKELY (memcmp (this_key, key + key_length, this_size) != 0)
 258     return FALSE;
 259
 260   parent = guint32_from_le (item->parent);
 261   if (key_length == 0 && parent == 0xffffffffu)
 262     return TRUE;
 263
 264   if G_LIKELY (parent < file->n_hash_items && this_size > 0)
 265     return gvdb_table_check_name (file,
 266                                    &file->hash_items[parent],
 267                                    key, key_length);
 268
 269   return FALSE;
 270 }
 271
 272 static const struct gvdb_hash_item *
 273 gvdb_table_lookup (GvdbTable   *file,
 274                    const gchar *key,
 275                    gchar        type)
 276 {
 277   guint32 hash_value = 5381;
 278   guint key_length;
 279   guint32 bucket;
 280   guint32 lastno;
 281   guint32 itemno;
 282
 283   if G_UNLIKELY (file->n_buckets == 0 || file->n_hash_items == 0)
 284     return NULL;
 285
 286   for (key_length = 0; key[key_length]; key_length++)
 287     hash_value = (hash_value * 33) + ((signed char *) key)[key_length];
 288
 289   if (!gvdb_table_bloom_filter (file, hash_value))
 290     return NULL;
 291
 292   bucket = hash_value % file->n_buckets;
 293   itemno = guint32_from_le (file->hash_buckets[bucket]);
 294
 295   if (bucket == file->n_buckets - 1 ||
 296       (lastno = guint32_from_le(file->hash_buckets[bucket + 1])) > file->n_hash_items)
 297     lastno = file->n_hash_items;
 298
 299   while G_LIKELY (itemno < lastno)
 300     {
 301       struct gvdb_hash_item *item = &file->hash_items[itemno];
 302
 303       if (hash_value == guint32_from_le (item->hash_value))
 304         if G_LIKELY (gvdb_table_check_name (file, item, key, key_length))
 305           if G_LIKELY (item->type == type)
 306             return item;
 307
 308       itemno++;
 309     }
 310
 311   return NULL;
 312 }
 313
 314 static gboolean
 315 gvdb_table_list_from_item (GvdbTable                    *table,
 316                            const struct gvdb_hash_item  *item,
 317                            const guint32_le            **list,
 318                            guint                        *length)
 319 {
 320   gsize size;
 321
 322   *list = gvdb_table_dereference (table, &item->value.pointer, 4, &size);
 323
 324   if G_LIKELY (*list == NULL || size % 4)
 325     return FALSE;
 326
 327   *length = size / 4;
 328
 329   return TRUE;
 330 }
 331
 332 /**
 333  * gvdb_table_get_names:
 334  * @table: a #GvdbTable
 335  * @length: (out) (optional): the number of items returned, or %NULL
 336  *
 337  * Gets a list of all names contained in @table.
 338  *
 339  * No call to gvdb_table_get_table(), gvdb_table_list() or
 340  * gvdb_table_get_value() will succeed unless it is for one of the
 341  * names returned by this function.
 342  *
 343  * Note that some names that are returned may still fail for all of the
 344  * above calls in the case of the corrupted file.  Note also that the
 345  * returned strings may not be utf8.
 346  *
 347  * Returns: (array length=length): a %NULL-terminated list of strings, of length @length
 348  **/
 349 gchar **
 350 gvdb_table_get_names (GvdbTable *table,
 351                       gsize     *length)
 352 {
 353   gchar **names;
 354   guint n_names;
 355   guint filled;
 356   guint total;
 357   guint i;
 358
 359   /* We generally proceed by iterating over the list of items in the
 360    * hash table (in order of appearance) recording them into an array.
 361    *
 362    * Each item has a parent item (except root items).  The parent item
 363    * forms part of the name of the item.  We could go fetching the
 364    * parent item chain at the point that we encounter each item but then
 365    * we would need to implement some sort of recursion along with checks
 366    * for self-referential items.
 367    *
 368    * Instead, we do a number of passes.  Each pass will build up one
 369    * level of names (starting from the root).  We continue to do passes
 370    * until no more items are left.  The first pass will only add root
 371    * items and each further pass will only add items whose direct parent
 372    * is an item added in the immediately previous pass.  It's also
 373    * possible that items get filled if they follow their parent within a
 374    * particular pass.
 375    *
 376    * At most we will have a number of passes equal to the depth of the
 377    * tree.  Self-referential items will never be filled in (since their
 378    * parent will have never been filled in).  We continue until we have
 379    * a pass that fills in no additional items.
 380    *
 381    * This takes an O(n) algorithm and turns it into O(n*m) where m is
 382    * the depth of the tree, but typically the tree won't be very
 383    * deep and the constant factor of this algorithm is lower (and the
 384    * complexity of coding it, as well).
 385    */
 386
 387   n_names = table->n_hash_items;
 388   names = g_new0 (gchar *, n_names + 1);
 389
 390   /* 'names' starts out all-NULL.  On each pass we record the number
 391    * of items changed from NULL to non-NULL in 'filled' so we know if we
 392    * should repeat the loop.  'total' counts the total number of items
 393    * filled.  If 'total' ends up equal to 'n_names' then we know that
 394    * 'names' has been completely filled.
 395    */
 396
 397   total = 0;
 398   do
 399     {
 400       /* Loop until we have filled no more entries */
 401       filled = 0;
 402
 403       for (i = 0; i < n_names; i++)
 404         {
 405           const struct gvdb_hash_item *item = &table->hash_items[i];
 406           const gchar *name;
 407           gsize name_length;
 408           guint32 parent;
 409
 410           /* already got it on a previous pass */
 411           if (names[i] != NULL)
 412             continue;
 413
 414           parent = guint32_from_le (item->parent);
 415
 416           if (parent == 0xffffffffu)
 417             {
 418               /* it's a root item */
 419               name = gvdb_table_item_get_key (table, item, &name_length);
 420
 421               if (name != NULL)
 422                 {
 423                   names[i] = g_strndup (name, name_length);
 424                   filled++;
 425                 }
 426             }
 427
 428           else if (parent < n_names && names[parent] != NULL)
 429             {
 430               /* It's a non-root item whose parent was filled in already.
 431                *
 432                * Calculate the name of this item by combining it with
 433                * its parent name.
 434                */
 435               name = gvdb_table_item_get_key (table, item, &name_length);
 436
 437               if (name != NULL)
 438                 {
 439                   const gchar *parent_name = names[parent];
 440                   gsize parent_length;
 441                   gchar *fullname;
 442
 443                   parent_length = strlen (parent_name);
 444                   fullname = g_malloc (parent_length + name_length + 1);
 445                   memcpy (fullname, parent_name, parent_length);
 446                   memcpy (fullname + parent_length, name, name_length);
 447                   fullname[parent_length + name_length] = '\0';
 448                   names[i] = fullname;
 449                   filled++;
 450                 }
 451             }
 452         }
 453
 454       total += filled;
 455     }
 456   while (filled && total < n_names);
 457
 458   /* If the table was corrupted then 'names' may have holes in it.
 459    * Collapse those.
 460    */
 461   if G_UNLIKELY (total != n_names)
 462     {
 463       GPtrArray *fixed_names;
 464
 465       fixed_names = g_ptr_array_sized_new (n_names + 1  /* NULL terminator */);
 466       for (i = 0; i < n_names; i++)
 467         if (names[i] != NULL)
 468           g_ptr_array_add (fixed_names, names[i]);
 469
 470       g_free (names);
 471       n_names = fixed_names->len;
 472       g_ptr_array_add (fixed_names, NULL);
 473       names = (gchar **) g_ptr_array_free (fixed_names, FALSE);
 474     }
 475
 476   if (length)
 477     {
 478       G_STATIC_ASSERT (sizeof (*length) >= sizeof (n_names));
 479       *length = n_names;
 480     }
 481
 482   return names;
 483 }
 484
 485 /**
 486  * gvdb_table_list:
 487  * @file: a #GvdbTable
 488  * @key: a string
 489  *
 490  * List all of the keys that appear below @key.  The nesting of keys
 491  * within the hash file is defined by the program that created the hash
 492  * file.  One thing is constant: each item in the returned array can be
 493  * concatenated to @key to obtain the full name of that key.
 494  *
 495  * It is not possible to tell from this function if a given key is
 496  * itself a path, a value, or another hash table; you are expected to
 497  * know this for yourself.
 498  *
 499  * You should call g_strfreev() on the return result when you no longer
 500  * require it.
 501  *
 502  * Returns: a %NULL-terminated string array
 503  **/
 504 gchar **
 505 gvdb_table_list (GvdbTable   *file,
 506                  const gchar *key)
 507 {
 508   const struct gvdb_hash_item *item;
 509   const guint32_le *list;
 510   gchar **strv;
 511   guint length;
 512   guint i;
 513
 514   if ((item = gvdb_table_lookup (file, key, 'L')) == NULL)
 515     return NULL;
 516
 517   if (!gvdb_table_list_from_item (file, item, &list, &length))
 518     return NULL;
 519
 520   strv = g_new (gchar *, length + 1);
 521   for (i = 0; i < length; i++)
 522     {
 523       guint32 itemno = guint32_from_le (list[i]);
 524
 525       if (itemno < file->n_hash_items)
 526         {
 527           const struct gvdb_hash_item *item;
 528           const gchar *string;
 529           gsize strsize;
 530
 531           item = file->hash_items + itemno;
 532
 533           string = gvdb_table_item_get_key (file, item, &strsize);
 534
 535           if (string != NULL)
 536             strv[i] = g_strndup (string, strsize);
 537           else
 538             strv[i] = g_malloc0 (1);
 539         }
 540       else
 541         strv[i] = g_malloc0 (1);
 542     }
 543
 544   strv[i] = NULL;
 545
 546   return strv;
 547 }
 548
 549 /**
 550  * gvdb_table_has_value:
 551  * @file: a #GvdbTable
 552  * @key: a string
 553  *
 554  * Checks for a value named @key in @file.
 555  *
 556  * Note: this function does not consider non-value nodes (other hash
 557  * tables, for example).
 558  *
 559  * Returns: %TRUE if @key is in the table
 560  **/
 561 gboolean
 562 gvdb_table_has_value (GvdbTable    *file,
 563                       const gchar  *key)
 564 {
 565   static const struct gvdb_hash_item *item;
 566   gsize size;
 567
 568   item = gvdb_table_lookup (file, key, 'v');
 569
 570   if (item == NULL)
 571     return FALSE;
 572
 573   return gvdb_table_dereference (file, &item->value.pointer, 8, &size) != NULL;
 574 }
 575
 576 static GVariant *
 577 gvdb_table_value_from_item (GvdbTable                   *table,
 578                             const struct gvdb_hash_item *item)
 579 {
 580   GVariant *variant, *value;
 581   gconstpointer data;
 582   GBytes *bytes;
 583   gsize size;
 584
 585   data = gvdb_table_dereference (table, &item->value.pointer, 8, &size);
 586
 587   if G_UNLIKELY (data == NULL)
 588     return NULL;
 589
 590   bytes = g_bytes_new_from_bytes (table->bytes, ((gchar *) data) - table->data, size);
 591   variant = g_variant_new_from_bytes (G_VARIANT_TYPE_VARIANT, bytes, table->trusted);
 592   value = g_variant_get_variant (variant);
 593   g_variant_unref (variant);
 594   g_bytes_unref (bytes);
 595
 596   return value;
 597 }
 598
 599 /**
 600  * gvdb_table_get_value:
 601  * @file: a #GvdbTable
 602  * @key: a string
 603  *
 604  * Looks up a value named @key in @file.
 605  *
 606  * If the value is not found then %NULL is returned.  Otherwise, a new
 607  * #GVariant instance is returned.  The #GVariant does not depend on the
 608  * continued existence of @file.
 609  *
 610  * You should call g_variant_unref() on the return result when you no
 611  * longer require it.
 612  *
 613  * Returns: a #GVariant, or %NULL
 614  **/
 615 GVariant *
 616 gvdb_table_get_value (GvdbTable    *file,
 617                       const gchar  *key)
 618 {
 619   const struct gvdb_hash_item *item;
 620   GVariant *value;
 621
 622   if ((item = gvdb_table_lookup (file, key, 'v')) == NULL)
 623     return NULL;
 624
 625   value = gvdb_table_value_from_item (file, item);
 626
 627   if (value && file->byteswapped)
 628     {
 629       GVariant *tmp;
 630
 631       tmp = g_variant_byteswap (value);
 632       g_variant_unref (value);
 633       value = tmp;
 634     }
 635
 636   return value;
 637 }
 638
 639 /**
 640  * gvdb_table_get_raw_value:
 641  * @table: a #GvdbTable
 642  * @key: a string
 643  *
 644  * Looks up a value named @key in @file.
 645  *
 646  * This call is equivalent to gvdb_table_get_value() except that it
 647  * never byteswaps the value.
 648  *
 649  * Returns: a #GVariant, or %NULL
 650  **/
 651 GVariant *
 652 gvdb_table_get_raw_value (GvdbTable   *table,
 653                           const gchar *key)
 654 {
 655   const struct gvdb_hash_item *item;
 656
 657   if ((item = gvdb_table_lookup (table, key, 'v')) == NULL)
 658     return NULL;
 659
 660   return gvdb_table_value_from_item (table, item);
 661 }
 662
 663 /**
 664  * gvdb_table_get_table:
 665  * @file: a #GvdbTable
 666  * @key: a string
 667  *
 668  * Looks up the hash table named @key in @file.
 669  *
 670  * The toplevel hash table in a #GvdbTable can contain reference to
 671  * child hash tables (and those can contain further references...).
 672  *
 673  * If @key is not found in @file then %NULL is returned.  Otherwise, a
 674  * new #GvdbTable is returned, referring to the child hashtable as
 675  * contained in the file.  This newly-created #GvdbTable does not depend
 676  * on the continued existence of @file.
 677  *
 678  * You should call gvdb_table_free() on the return result when you no
 679  * longer require it.
 680  *
 681  * Returns: a new #GvdbTable, or %NULL
 682  **/
 683 GvdbTable *
 684 gvdb_table_get_table (GvdbTable   *file,
 685                       const gchar *key)
 686 {
 687   const struct gvdb_hash_item *item;
 688   GvdbTable *new;
 689
 690   item = gvdb_table_lookup (file, key, 'H');
 691
 692   if (item == NULL)
 693     return NULL;
 694
 695   new = g_slice_new0 (GvdbTable);
 696   new->bytes = g_bytes_ref (file->bytes);
 697   new->byteswapped = file->byteswapped;
 698   new->trusted = file->trusted;
 699   new->data = file->data;
 700   new->size = file->size;
 701
 702   gvdb_table_setup_root (new, &item->value.pointer);
 703
 704   return new;
 705 }
 706
 707 /**
 708  * gvdb_table_free:
 709  * @file: a #GvdbTable
 710  *
 711  * Frees @file.
 712  **/
 713 void
 714 gvdb_table_free (GvdbTable *file)
 715 {
 716   g_bytes_unref (file->bytes);
 717   g_slice_free (GvdbTable, file);
 718 }
 719
 720 /**
 721  * gvdb_table_is_valid:
 722  * @table: a #GvdbTable
 723  *
 724  * Checks if the table is still valid.
 725  *
 726  * An on-disk GVDB can be marked as invalid.  This happens when the file
 727  * has been replaced.  The appropriate action is typically to reopen the
 728  * file.
 729  *
 730  * Returns: %TRUE if @table is still valid
 731  **/
 732 gboolean
 733 gvdb_table_is_valid (GvdbTable *table)
 734 {
 735   return !!*table->data;
 736 }