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