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