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