gio/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 of the licence, 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   gint ref_count;
  27
  28   const gchar *data;
  29   gsize size;
  30
  31   gpointer user_data;
  32   GvdbRefFunc ref_user_data;
  33   GDestroyNotify unref_user_data;
  34
  35   gboolean byteswapped;
  36   gboolean trusted;
  37
  38   const guint32_le *bloom_words;
  39   guint32 n_bloom_words;
  40   guint bloom_shift;
  41
  42   const guint32_le *hash_buckets;
  43   guint32 n_buckets;
  44
  45   struct gvdb_hash_item *hash_items;
  46   guint32 n_hash_items;
  47 };
  48
  49 static const gchar *
  50 gvdb_table_item_get_key (GvdbTable                   *file,
  51                          const struct gvdb_hash_item *item,
  52                          gsize                       *size)
  53 {
  54   guint32 start, end;
  55
  56   start = guint32_from_le (item->key_start);
  57   *size = guint16_from_le (item->key_size);
  58   end = start + *size;
  59
  60   if G_UNLIKELY (start > end || end > file->size)
  61     return NULL;
  62
  63   return file->data + start;
  64 }
  65
  66 static gconstpointer
  67 gvdb_table_dereference (GvdbTable                 *file,
  68                         const struct gvdb_pointer *pointer,
  69                         gint                       alignment,
  70                         gsize                     *size)
  71 {
  72   guint32 start, end;
  73
  74   start = guint32_from_le (pointer->start);
  75   end = guint32_from_le (pointer->end);
  76
  77   if G_UNLIKELY (start > end || end > file->size || start & (alignment - 1))
  78     return NULL;
  79
  80   *size = end - start;
  81
  82   return file->data + start;
  83 }
  84
  85 static void
  86 gvdb_table_setup_root (GvdbTable                 *file,
  87                        const struct gvdb_pointer *pointer)
  88 {
  89   const struct gvdb_hash_header *header;
  90   guint32 n_bloom_words;
  91   guint32 n_buckets;
  92   gsize size;
  93
  94   header = gvdb_table_dereference (file, pointer, 4, &size);
  95
  96   if G_UNLIKELY (header == NULL || size < sizeof *header)
  97     return;
  98
  99   size -= sizeof *header;
 100
 101   n_bloom_words = guint32_from_le (header->n_bloom_words);
 102   n_buckets = guint32_from_le (header->n_buckets);
 103   n_bloom_words &= (1u << 27) - 1;
 104
 105   if G_UNLIKELY (n_bloom_words * sizeof (guint32_le) > size)
 106     return;
 107
 108   file->bloom_words = (gpointer) (header + 1);
 109   size -= n_bloom_words * sizeof (guint32_le);
 110   file->n_bloom_words = n_bloom_words;
 111
 112   if G_UNLIKELY (n_buckets > G_MAXUINT / sizeof (guint32_le) ||
 113                  n_buckets * sizeof (guint32_le) > size)
 114     return;
 115
 116   file->hash_buckets = file->bloom_words + file->n_bloom_words;
 117   size -= n_buckets * sizeof (guint32_le);
 118   file->n_buckets = n_buckets;
 119
 120   if G_UNLIKELY (size % sizeof (struct gvdb_hash_item))
 121     return;
 122
 123   file->hash_items = (gpointer) (file->hash_buckets + n_buckets);
 124   file->n_hash_items = size / sizeof (struct gvdb_hash_item);
 125 }
 126
 127 static GvdbTable *
 128 new_from_data (const void    *data,
 129                gsize          data_len,
 130                gboolean       trusted,
 131                gpointer       user_data,
 132                GvdbRefFunc    ref,
 133                GDestroyNotify unref,
 134                const char    *filename,
 135                GError       **error)
 136 {
 137   GvdbTable *file;
 138
 139   file = g_slice_new0 (GvdbTable);
 140   file->data = data;
 141   file->size = data_len;
 142   file->trusted = trusted;
 143   file->ref_count = 1;
 144   file->ref_user_data = ref;
 145   file->unref_user_data = unref;
 146   file->user_data = user_data;
 147
 148   if (sizeof (struct gvdb_header) <= file->size)
 149     {
 150       const struct gvdb_header *header = (gpointer) file->data;
 151
 152       if (header->signature[0] == GVDB_SIGNATURE0 &&
 153           header->signature[1] == GVDB_SIGNATURE1 &&
 154           guint32_from_le (header->version) == 0)
 155         file->byteswapped = FALSE;
 156
 157       else if (header->signature[0] == GVDB_SWAPPED_SIGNATURE0 &&
 158                header->signature[1] == GVDB_SWAPPED_SIGNATURE1 &&
 159                guint32_from_le (header->version) == 0)
 160         file->byteswapped = TRUE;
 161
 162       else
 163         {
 164           if (filename)
 165             g_set_error (error, G_FILE_ERROR, G_FILE_ERROR_INVAL,
 166                          "%s: invalid header", filename);
 167           else
 168             g_set_error (error, G_FILE_ERROR, G_FILE_ERROR_INVAL,
 169                          "invalid gvdb header");
 170           g_slice_free (GvdbTable, file);
 171           if (unref)
 172             unref (user_data);
 173
 174           return NULL;
 175         }
 176
 177       gvdb_table_setup_root (file, &header->root);
 178     }
 179
 180   return file;
 181 }
 182
 183 /**
 184  * gvdb_table_new:
 185  * @filename: the path to the hash file
 186  * @trusted: if the contents of @filename are trusted
 187  * @error: %NULL, or a pointer to a %NULL #GError
 188  *
 189  * Creates a new #GvdbTable from the contents of the file found at
 190  * @filename.
 191  *
 192  * The only time this function fails is if the file cannot be opened.
 193  * In that case, the #GError that is returned will be an error from
 194  * g_mapped_file_new().
 195  *
 196  * An empty or otherwise corrupted file is considered to be a valid
 197  * #GvdbTable with no entries.
 198  *
 199  * You should call gvdb_table_unref() on the return result when you no
 200  * longer require it.
 201  *
 202  * Returns: a new #GvdbTable
 203  **/
 204 GvdbTable *
 205 gvdb_table_new (const gchar  *filename,
 206                 gboolean      trusted,
 207                 GError      **error)
 208 {
 209   GMappedFile *mapped;
 210
 211   if ((mapped = g_mapped_file_new (filename, FALSE, error)) == NULL)
 212     return NULL;
 213
 214   return new_from_data (g_mapped_file_get_contents (mapped),
 215                         g_mapped_file_get_length (mapped),
 216                         trusted,
 217                         mapped,
 218                         (GvdbRefFunc)g_mapped_file_ref,
 219                         (GDestroyNotify)g_mapped_file_unref,
 220                         filename,
 221                         error);
 222 }
 223
 224 /**
 225  * gvdb_table_new_from_data:
 226  * @data: the data
 227  * @data_len: the length of @data in bytes
 228  * @trusted: if the contents of @data are trusted
 229  * @user_data: User supplied data that owns @data
 230  * @ref: Ref function for @user_data
 231  * @unref: Unref function for @user_data
 232  *
 233  * Creates a new #GvdbTable from the data in @data.
 234  *
 235  * An empty or otherwise corrupted data is considered to be a valid
 236  * #GvdbTable with no entries.
 237  *
 238  * You should call gvdb_table_unref() on the return result when you no
 239  * longer require it.
 240  *
 241  * Returns: a new #GvdbTable
 242  **/
 243 GvdbTable *
 244 gvdb_table_new_from_data (const void    *data,
 245                           gsize          data_len,
 246                           gboolean       trusted,
 247                           gpointer       user_data,
 248                           GvdbRefFunc    ref,
 249                           GDestroyNotify unref,
 250                           GError        **error)
 251 {
 252   return new_from_data (data, data_len,
 253                         trusted,
 254                         user_data, ref, unref,
 255                         NULL,
 256                         error);
 257 }
 258
 259 static gboolean
 260 gvdb_table_bloom_filter (GvdbTable *file,
 261                           guint32    hash_value)
 262 {
 263   guint32 word, mask;
 264
 265   if (file->n_bloom_words == 0)
 266     return TRUE;
 267
 268   word = (hash_value / 32) % file->n_bloom_words;
 269   mask = 1 << (hash_value & 31);
 270   mask |= 1 << ((hash_value >> file->bloom_shift) & 31);
 271
 272   return (guint32_from_le (file->bloom_words[word]) & mask) == mask;
 273 }
 274
 275 static gboolean
 276 gvdb_table_check_name (GvdbTable             *file,
 277                        struct gvdb_hash_item *item,
 278                        const gchar           *key,
 279                        guint                  key_length)
 280 {
 281   const gchar *this_key;
 282   gsize this_size;
 283   guint32 parent;
 284
 285   this_key = gvdb_table_item_get_key (file, item, &this_size);
 286
 287   if G_UNLIKELY (this_key == NULL || this_size > key_length)
 288     return FALSE;
 289
 290   key_length -= this_size;
 291
 292   if G_UNLIKELY (memcmp (this_key, key + key_length, this_size) != 0)
 293     return FALSE;
 294
 295   parent = guint32_from_le (item->parent);
 296   if (key_length == 0 && parent == 0xffffffffu)
 297     return TRUE;
 298
 299   if G_LIKELY (parent < file->n_hash_items && this_size > 0)
 300     return gvdb_table_check_name (file,
 301                                    &file->hash_items[parent],
 302                                    key, key_length);
 303
 304   return FALSE;
 305 }
 306
 307 static const struct gvdb_hash_item *
 308 gvdb_table_lookup (GvdbTable   *file,
 309                    const gchar *key,
 310                    gchar        type)
 311 {
 312   guint32 hash_value = 5381;
 313   guint key_length;
 314   guint32 bucket;
 315   guint32 lastno;
 316   guint32 itemno;
 317
 318   if G_UNLIKELY (file->n_buckets == 0 || file->n_hash_items == 0)
 319     return NULL;
 320
 321   for (key_length = 0; key[key_length]; key_length++)
 322     hash_value = (hash_value * 33) + ((signed char *) key)[key_length];
 323
 324   if (!gvdb_table_bloom_filter (file, hash_value))
 325     return NULL;
 326
 327   bucket = hash_value % file->n_buckets;
 328   itemno = guint32_from_le (file->hash_buckets[bucket]);
 329
 330   if (bucket == file->n_buckets - 1 ||
 331       (lastno = guint32_from_le(file->hash_buckets[bucket + 1])) > file->n_hash_items)
 332     lastno = file->n_hash_items;
 333
 334   while G_LIKELY (itemno < lastno)
 335     {
 336       struct gvdb_hash_item *item = &file->hash_items[itemno];
 337
 338       if (hash_value == guint32_from_le (item->hash_value))
 339         if G_LIKELY (gvdb_table_check_name (file, item, key, key_length))
 340           if G_LIKELY (item->type == type)
 341             return item;
 342
 343       itemno++;
 344     }
 345
 346   return NULL;
 347 }
 348
 349 static const struct gvdb_hash_item *
 350 gvdb_table_get_item (GvdbTable  *table,
 351                      guint32_le  item_no)
 352 {
 353   guint32 item_no_native = guint32_from_le (item_no);
 354
 355   if G_LIKELY (item_no_native < table->n_hash_items)
 356     return table->hash_items + item_no_native;
 357
 358   return NULL;
 359 }
 360
 361 static gboolean
 362 gvdb_table_list_from_item (GvdbTable                    *table,
 363                            const struct gvdb_hash_item  *item,
 364                            const guint32_le            **list,
 365                            guint                        *length)
 366 {
 367   gsize size;
 368
 369   *list = gvdb_table_dereference (table, &item->value.pointer, 4, &size);
 370
 371   if G_LIKELY (*list == NULL || size % 4)
 372     return FALSE;
 373
 374   *length = size / 4;
 375
 376   return TRUE;
 377 }
 378
 379
 380 /**
 381  * gvdb_table_list:
 382  * @file: a #GvdbTable
 383  * @key: a string
 384  *
 385  * List all of the keys that appear below @key.  The nesting of keys
 386  * within the hash file is defined by the program that created the hash
 387  * file.  One thing is constant: each item in the returned array can be
 388  * concatenated to @key to obtain the full name of that key.
 389  *
 390  * It is not possible to tell from this function if a given key is
 391  * itself a path, a value, or another hash table; you are expected to
 392  * know this for yourself.
 393  *
 394  * You should call g_strfreev() on the return result when you no longer
 395  * require it.
 396  *
 397  * Returns: a %NULL-terminated string array
 398  **/
 399 gchar **
 400 gvdb_table_list (GvdbTable   *file,
 401                  const gchar *key)
 402 {
 403   const struct gvdb_hash_item *item;
 404   const guint32_le *list;
 405   gchar **strv;
 406   guint length;
 407   guint i;
 408
 409   if ((item = gvdb_table_lookup (file, key, 'L')) == NULL)
 410     return NULL;
 411
 412   if (!gvdb_table_list_from_item (file, item, &list, &length))
 413     return NULL;
 414
 415   strv = g_new (gchar *, length + 1);
 416   for (i = 0; i < length; i++)
 417     {
 418       guint32 itemno = guint32_from_le (list[i]);
 419
 420       if (itemno < file->n_hash_items)
 421         {
 422           const struct gvdb_hash_item *item;
 423           const gchar *string;
 424           gsize strsize;
 425
 426           item = file->hash_items + itemno;
 427
 428           string = gvdb_table_item_get_key (file, item, &strsize);
 429
 430           if (string != NULL)
 431             strv[i] = g_strndup (string, strsize);
 432           else
 433             strv[i] = g_malloc0 (1);
 434         }
 435       else
 436         strv[i] = g_malloc0 (1);
 437     }
 438
 439   strv[i] = NULL;
 440
 441   return strv;
 442 }
 443
 444 /**
 445  * gvdb_table_has_value:
 446  * @file: a #GvdbTable
 447  * @key: a string
 448  *
 449  * Checks for a value named @key in @file.
 450  *
 451  * Note: this function does not consider non-value nodes (other hash
 452  * tables, for example).
 453  *
 454  * Returns: %TRUE if @key is in the table
 455  **/
 456 gboolean
 457 gvdb_table_has_value (GvdbTable    *file,
 458                       const gchar  *key)
 459 {
 460   return gvdb_table_lookup (file, key, 'v') != NULL;
 461 }
 462
 463 static GVariant *
 464 gvdb_table_value_from_item (GvdbTable                   *table,
 465                             const struct gvdb_hash_item *item)
 466 {
 467   GVariant *variant, *value;
 468   gconstpointer data;
 469   gsize size;
 470
 471   data = gvdb_table_dereference (table, &item->value.pointer, 8, &size);
 472
 473   if G_UNLIKELY (data == NULL)
 474     return NULL;
 475
 476   variant = g_variant_new_from_data (G_VARIANT_TYPE_VARIANT,
 477                                      data, size, table->trusted,
 478                                      table->unref_user_data,
 479                                      table->ref_user_data ? table->ref_user_data (table->user_data) : table->user_data);
 480   value = g_variant_get_variant (variant);
 481   g_variant_unref (variant);
 482
 483   return value;
 484 }
 485
 486 /**
 487  * gvdb_table_get_value:
 488  * @file: a #GvdbTable
 489  * @key: a string
 490  *
 491  * Looks up a value named @key in @file.
 492  *
 493  * If the value is not found then %NULL is returned.  Otherwise, a new
 494  * #GVariant instance is returned.  The #GVariant does not depend on the
 495  * continued existence of @file.
 496  *
 497  * You should call g_variant_unref() on the return result when you no
 498  * longer require it.
 499  *
 500  * Returns: a #GVariant, or %NULL
 501  **/
 502 GVariant *
 503 gvdb_table_get_value (GvdbTable    *file,
 504                       const gchar  *key)
 505 {
 506   const struct gvdb_hash_item *item;
 507   GVariant *value;
 508
 509   if ((item = gvdb_table_lookup (file, key, 'v')) == NULL)
 510     return NULL;
 511
 512   value = gvdb_table_value_from_item (file, item);
 513
 514   if (value && file->byteswapped)
 515     {
 516       GVariant *tmp;
 517
 518       tmp = g_variant_byteswap (value);
 519       g_variant_unref (value);
 520       value = tmp;
 521     }
 522
 523   return value;
 524 }
 525
 526 /**
 527  * gvdb_table_get_raw_value:
 528  * @table: a #GvdbTable
 529  * @key: a string
 530  *
 531  * Looks up a value named @key in @file.
 532  *
 533  * This call is equivalent to gvdb_table_get_value() except that it
 534  * never byteswaps the value.
 535  *
 536  * Returns: a #GVariant, or %NULL
 537  **/
 538 GVariant *
 539 gvdb_table_get_raw_value (GvdbTable   *table,
 540                           const gchar *key)
 541 {
 542   const struct gvdb_hash_item *item;
 543
 544   if ((item = gvdb_table_lookup (table, key, 'v')) == NULL)
 545     return NULL;
 546
 547   return gvdb_table_value_from_item (table, item);
 548 }
 549
 550 /**
 551  * gvdb_table_get_table:
 552  * @file: a #GvdbTable
 553  * @key: a string
 554  *
 555  * Looks up the hash table named @key in @file.
 556  *
 557  * The toplevel hash table in a #GvdbTable can contain reference to
 558  * child hash tables (and those can contain further references...).
 559  *
 560  * If @key is not found in @file then %NULL is returned.  Otherwise, a
 561  * new #GvdbTable is returned, referring to the child hashtable as
 562  * contained in the file.  This newly-created #GvdbTable does not depend
 563  * on the continued existence of @file.
 564  *
 565  * You should call gvdb_table_unref() on the return result when you no
 566  * longer require it.
 567  *
 568  * Returns: a new #GvdbTable, or %NULL
 569  **/
 570 GvdbTable *
 571 gvdb_table_get_table (GvdbTable   *file,
 572                       const gchar *key)
 573 {
 574   const struct gvdb_hash_item *item;
 575   GvdbTable *new;
 576
 577   item = gvdb_table_lookup (file, key, 'H');
 578
 579   if (item == NULL)
 580     return NULL;
 581
 582   new = g_slice_new0 (GvdbTable);
 583   new->user_data = file->ref_user_data ? file->ref_user_data (file->user_data) : file->user_data;
 584   new->ref_user_data = file->ref_user_data;
 585   new->unref_user_data = file->unref_user_data;
 586   new->byteswapped = file->byteswapped;
 587   new->trusted = file->trusted;
 588   new->data = file->data;
 589   new->size = file->size;
 590   new->ref_count = 1;
 591
 592   gvdb_table_setup_root (new, &item->value.pointer);
 593
 594   return new;
 595 }
 596
 597 /**
 598  * gvdb_table_ref:
 599  * @file: a #GvdbTable
 600  *
 601  * Increases the reference count on @file.
 602  *
 603  * Returns: a new reference on @file
 604  **/
 605 GvdbTable *
 606 gvdb_table_ref (GvdbTable *file)
 607 {
 608   g_atomic_int_inc (&file->ref_count);
 609
 610   return file;
 611 }
 612
 613 /**
 614  * gvdb_table_unref:
 615  * @file: a #GvdbTable
 616  *
 617  * Decreases the reference count on @file, possibly freeing it.
 618  *
 619  * Since: 2.26
 620  **/
 621 void
 622 gvdb_table_unref (GvdbTable *file)
 623 {
 624   if (g_atomic_int_dec_and_test (&file->ref_count))
 625     {
 626       if (file->unref_user_data)
 627         file->unref_user_data (file->user_data);
 628       g_slice_free (GvdbTable, file);
 629     }
 630 }
 631
 632 /**
 633  * gvdb_table_is_valid:
 634  * @table: a #GvdbTable
 635  *
 636  * Checks if the table is still valid.
 637  *
 638  * An on-disk GVDB can be marked as invalid.  This happens when the file
 639  * has been replaced.  The appropriate action is typically to reopen the
 640  * file.
 641  *
 642  * Returns: %TRUE if @table is still valid
 643  **/
 644 gboolean
 645 gvdb_table_is_valid (GvdbTable *table)
 646 {
 647   return !!*table->data;
 648 }
 649
 650 /**
 651  * gvdb_table_walk:
 652  * @table: a #GvdbTable
 653  * @key: a key corresponding to a list
 654  * @open_func: the #GvdbWalkOpenFunc
 655  * @value_func: the #GvdbWalkValueFunc
 656  * @close_func: the #GvdbWalkCloseFunc
 657  * @user_data: data to pass to the callbacks
 658  *
 659  * Looks up the list at @key and iterate over the items in it.
 660  *
 661  * First, @open_func is called to signal that we are starting to iterate over
 662  * the list.  Then the list is iterated.  When all items in the list have been
 663  * iterated over, the @close_func is called.
 664  *
 665  * When iterating, if a given item in the list is a value then @value_func is
 666  * called.
 667  *
 668  * If a given item in the list is itself a list then @open_func is called.  If
 669  * that function returns %TRUE then the walk begins iterating the items in the
 670  * sublist, until there are no more items, at which point a matching
 671  * @close_func call is made.  If @open_func returns %FALSE then no iteration of
 672  * the sublist occurs and no corresponding @close_func call is made.
 673  **/
 674 void
 675 gvdb_table_walk (GvdbTable         *table,
 676                  const gchar       *key,
 677                  GvdbWalkOpenFunc   open_func,
 678                  GvdbWalkValueFunc  value_func,
 679                  GvdbWalkCloseFunc  close_func,
 680                  gpointer           user_data)
 681 {
 682   const struct gvdb_hash_item *item;
 683   const guint32_le *pointers[64];
 684   const guint32_le *enders[64];
 685   gsize name_lengths[64];
 686   gint index = 0;
 687
 688   item = gvdb_table_lookup (table, key, 'L');
 689   name_lengths[0] = 0;
 690   pointers[0] = NULL;
 691   enders[0] = NULL;
 692   goto start_here;
 693
 694   while (index)
 695     {
 696       close_func (name_lengths[index], user_data);
 697       index--;
 698
 699       while (pointers[index] < enders[index])
 700         {
 701           const gchar *name;
 702           gsize name_len;
 703
 704           item = gvdb_table_get_item (table, *pointers[index]++);
 705  start_here:
 706
 707           if (item != NULL &&
 708               (name = gvdb_table_item_get_key (table, item, &name_len)))
 709             {
 710               if (item->type == 'L')
 711                 {
 712                   if (open_func (name, name_len, user_data))
 713                     {
 714                       guint length = 0;
 715
 716                       index++;
 717                       g_assert (index < 64);
 718
 719                       gvdb_table_list_from_item (table, item,
 720                                                  &pointers[index],
 721                                                  &length);
 722                       enders[index] = pointers[index] + length;
 723                       name_lengths[index] = name_len;
 724                     }
 725                 }
 726               else if (item->type == 'v')
 727                 {
 728                   GVariant *value;
 729
 730                   value = gvdb_table_value_from_item (table, item);
 731
 732                   if (value != NULL)
 733                     {
 734                       if (table->byteswapped)
 735                         {
 736                           GVariant *tmp;
 737
 738                           tmp = g_variant_byteswap (value);
 739                           g_variant_unref (value);
 740                           value = tmp;
 741                         }
 742
 743                       value_func (name, name_len, value, user_data);
 744                       g_variant_unref (value);
 745                     }
 746                 }
 747             }
 748         }
 749     }
 750 }