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)
syntax error
(emitted by cppcheck)
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 can not 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) + ((signed char *) 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;
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 }