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
25struct _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
45static const gchar *
46gvdb_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 (value: item->key_start);
53 *size = guint16_from_le (value: 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
62static gconstpointer
63gvdb_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 (value: pointer->start);
71 end = guint32_from_le (value: 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
81static void
82gvdb_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, alignment: 4, size: &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 (value: header->n_bloom_words);
98 n_buckets = guint32_from_le (value: 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 **/
139GvdbTable *
140gvdb_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, size: &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 (value: 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 (value: header->version) == 0)
165 file->byteswapped = TRUE;
166
167 else
168 goto invalid;
169
170 gvdb_table_setup_root (file, pointer: &header->root);
171
172 return file;
173
174invalid:
175 g_set_error_literal (err: error, G_FILE_ERROR, code: G_FILE_ERROR_INVAL, message: "invalid gvdb header");
176
177 g_bytes_unref (bytes: 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 **/
201GvdbTable *
202gvdb_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 (file: mapped);
215 table = gvdb_table_new_from_bytes (bytes, trusted, error);
216 g_mapped_file_unref (file: mapped);
217 g_bytes_unref (bytes);
218
219 g_prefix_error (err: error, format: "%s: ", filename);
220
221 return table;
222}
223
224static gboolean
225gvdb_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 (value: file->bloom_words[word]) & mask) == mask;
238}
239
240static gboolean
241gvdb_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, size: &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 (value: 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 item: &file->hash_items[parent],
267 key, key_length);
268
269 return FALSE;
270}
271
272static const struct gvdb_hash_item *
273gvdb_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 (value: file->hash_buckets[bucket]);
294
295 if (bucket == file->n_buckets - 1 ||
296 (lastno = guint32_from_le(value: 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 (value: 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
314static gboolean
315gvdb_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 (file: table, pointer: &item->value.pointer, alignment: 4, size: &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 **/
349gchar **
350gvdb_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 (value: item->parent);
415
416 if (parent == 0xffffffffu)
417 {
418 /* it's a root item */
419 name = gvdb_table_item_get_key (file: table, item, size: &name_length);
420
421 if (name != NULL)
422 {
423 names[i] = g_strndup (str: name, n: 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 (file: table, item, size: &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 (s: parent_name);
444 fullname = g_malloc (n_bytes: parent_length + name_length + 1);
445 memcpy (dest: fullname, src: parent_name, n: parent_length);
446 memcpy (dest: fullname + parent_length, src: name, n: 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 (reserved_size: n_names + 1 /* NULL terminator */);
466 for (i = 0; i < n_names; i++)
467 if (names[i] != NULL)
468 g_ptr_array_add (array: fixed_names, data: names[i]);
469
470 g_free (mem: names);
471 n_names = fixed_names->len;
472 g_ptr_array_add (array: fixed_names, NULL);
473 names = (gchar **) g_ptr_array_free (array: 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 **/
504gchar **
505gvdb_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, type: 'L')) == NULL)
515 return NULL;
516
517 if (!gvdb_table_list_from_item (table: file, item, list: &list, length: &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 (value: 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, size: &strsize);
534
535 if (string != NULL)
536 strv[i] = g_strndup (str: string, n: strsize);
537 else
538 strv[i] = g_malloc0 (n_bytes: 1);
539 }
540 else
541 strv[i] = g_malloc0 (n_bytes: 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 **/
561gboolean
562gvdb_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, type: 'v');
569
570 if (item == NULL)
571 return FALSE;
572
573 return gvdb_table_dereference (file, pointer: &item->value.pointer, alignment: 8, size: &size) != NULL;
574}
575
576static GVariant *
577gvdb_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 (file: table, pointer: &item->value.pointer, alignment: 8, size: &size);
586
587 if G_UNLIKELY (data == NULL)
588 return NULL;
589
590 bytes = g_bytes_new_from_bytes (bytes: table->bytes, offset: ((gchar *) data) - table->data, length: size);
591 variant = g_variant_new_from_bytes (G_VARIANT_TYPE_VARIANT, bytes, trusted: table->trusted);
592 value = g_variant_get_variant (value: variant);
593 g_variant_unref (value: 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 **/
615GVariant *
616gvdb_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, type: 'v')) == NULL)
623 return NULL;
624
625 value = gvdb_table_value_from_item (table: 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 **/
651GVariant *
652gvdb_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 (file: table, key, type: '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 **/
683GvdbTable *
684gvdb_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, type: 'H');
691
692 if (item == NULL)
693 return NULL;
694
695 new = g_slice_new0 (GvdbTable);
696 new->bytes = g_bytes_ref (bytes: 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 (file: new, pointer: &item->value.pointer);
703
704 return new;
705}
706
707/**
708 * gvdb_table_free:
709 * @file: a #GvdbTable
710 *
711 * Frees @file.
712 **/
713void
714gvdb_table_free (GvdbTable *file)
715{
716 g_bytes_unref (bytes: 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 **/
732gboolean
733gvdb_table_is_valid (GvdbTable *table)
734{
735 return !!*table->data;
736}
737

source code of gtk/subprojects/glib/gio/gvdb/gvdb-reader.c