2 * Copyright © 2008 Ryan Lortie
3 * Copyright © 2010 Codethink Limited
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the
17 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 * Boston, MA 02111-1307, USA.
20 * Author: Ryan Lortie <desrt@desrt.ca>
23 #include "gvarianttypeinfo.h"
31 * This structure contains the necessary information to facilitate the
32 * serialisation and fast deserialisation of a given type of GVariant
33 * value. A GVariant instance holds a pointer to one of these
34 * structures to provide for efficient operation.
36 * The GVariantTypeInfo structures for all of the base types, plus the
37 * "variant" type are stored in a read-only static array.
39 * For container types, a hash table and reference counting is used to
40 * ensure that only one of these structures exists for any given type.
41 * In general, a container GVariantTypeInfo will exist for a given type
42 * only if one or more GVariant instances of that type exist or if
43 * another GVariantTypeInfo has that type as a subtype. For example, if
44 * a process contains a single GVariant instance with type "(asv)", then
45 * container GVariantTypeInfo structures will exist for "(asv)" and
46 * for "as" (note that "s" and "v" always exist in the static array).
48 * The trickiest part of GVariantTypeInfo (and in fact, the major reason
49 * for its existance) is the storage of somewhat magical constants that
50 * allow for O(1) lookups of items in tuples. This is described below.
52 * 'container_class' is set to 'a' or 'r' if the GVariantTypeInfo is
53 * contained inside of an ArrayInfo or TupleInfo, respectively. This
54 * allows the storage of the necessary additional information.
56 * 'fixed_size' is set to the fixed size of the type, if applicable, or
57 * 0 otherwise (since no type has a fixed size of 0).
59 * 'alignment' is set to one less than the alignment requirement for
60 * this type. This makes many operations much more convenient.
62 struct _GVariantTypeInfo
66 guchar container_class;
69 /* Container types are reference counted. They also need to have their
70 * type string stored explicitly since it is not merely a single letter.
74 GVariantTypeInfo info;
80 /* For 'array' and 'maybe' types, we store some extra information on the
81 * end of the GVariantTypeInfo struct -- the element type (ie: "s" for
82 * "as"). The container GVariantTypeInfo structure holds a reference to
83 * the element typeinfo.
87 ContainerInfo container;
89 GVariantTypeInfo *element;
92 /* For 'tuple' and 'dict entry' types, we store extra information for
93 * each member -- its type and how to find it inside the serialised data
94 * in O(1) time using 4 variables -- 'i', 'a', 'b', and 'c'. See the
95 * comment on GVariantMemberInfo in gvarianttypeinfo.h.
99 ContainerInfo container;
101 GVariantMemberInfo *members;
106 /* Hard-code the base types in a constant array */
107 static const GVariantTypeInfo g_variant_type_info_basic_table[24] = {
108 #define fixed_aligned(x) x, x - 1
109 #define unaligned 0, 0
110 #define aligned(x) 0, x - 1
111 /* 'b' */ { fixed_aligned(1) }, /* boolean */
113 /* 'd' */ { fixed_aligned(8) }, /* double */
116 /* 'g' */ { unaligned }, /* signature string */
117 /* 'h' */ { fixed_aligned(4) }, /* file handle (int32) */
118 /* 'i' */ { fixed_aligned(4) }, /* int32 */
123 /* 'n' */ { fixed_aligned(2) }, /* int16 */
124 /* 'o' */ { unaligned }, /* object path string */
126 /* 'q' */ { fixed_aligned(2) }, /* uint16 */
128 /* 's' */ { unaligned }, /* string */
129 /* 't' */ { fixed_aligned(8) }, /* uint64 */
130 /* 'u' */ { fixed_aligned(4) }, /* uint32 */
131 /* 'v' */ { aligned(8) }, /* variant */
133 /* 'x' */ { fixed_aligned(8) }, /* int64 */
134 /* 'y' */ { fixed_aligned(1) }, /* byte */
140 /* We need to have type strings to return for the base types. We store
141 * those in another array. Since all base type strings are single
142 * characters this is easy. By not storing pointers to strings into the
143 * GVariantTypeInfo itself, we save a bunch of relocations.
145 static const char g_variant_type_info_basic_chars[24][2] = {
146 "b", " ", "d", " ", " ", "g", "h", "i", " ", " ", " ", " ",
147 "n", "o", " ", "q", " ", "s", "t", "u", "v", " ", "x", "y"
150 /* sanity checks to make debugging easier */
152 g_variant_type_info_check (const GVariantTypeInfo *info,
153 char container_class)
155 g_assert (!container_class || info->container_class == container_class);
157 /* alignment can only be one of these */
158 g_assert (info->alignment == 0 || info->alignment == 1 ||
159 info->alignment == 3 || info->alignment == 7);
161 if (info->container_class)
163 ContainerInfo *container = (ContainerInfo *) info;
165 /* extra checks for containers */
166 g_assert_cmpint (container->ref_count, >, 0);
167 g_assert (container->type_string != NULL);
173 /* if not a container, then ensure that it is a valid member of
174 * the basic types table
176 index = info - g_variant_type_info_basic_table;
178 g_assert (G_N_ELEMENTS (g_variant_type_info_basic_table) == 24);
179 g_assert (G_N_ELEMENTS (g_variant_type_info_basic_chars) == 24);
180 g_assert (0 <= index && index < 24);
181 g_assert (g_variant_type_info_basic_chars[index][0] != ' ');
186 * g_variant_type_info_get_type_string:
187 * @info: a #GVariantTypeInfo
189 * Gets the type string for @info. The string is nul-terminated.
192 g_variant_type_info_get_type_string (GVariantTypeInfo *info)
194 g_variant_type_info_check (info, 0);
196 if (info->container_class)
198 ContainerInfo *container = (ContainerInfo *) info;
200 /* containers have their type string stored inside them */
201 return container->type_string;
207 /* look up the type string in the base type array. the call to
208 * g_variant_type_info_check() above already ensured validity.
210 index = info - g_variant_type_info_basic_table;
212 return g_variant_type_info_basic_chars[index];
217 * g_variant_type_info_query:
218 * @info: a #GVariantTypeInfo
219 * @alignment: the location to store the alignment, or %NULL
220 * @fixed_size: the location to store the fixed size, or %NULL
222 * Queries @info to determine the alignment requirements and fixed size
223 * (if any) of the type.
225 * @fixed_size, if non-%NULL is set to the fixed size of the type, or 0
226 * to indicate that the type is a variable-sized type. No type has a
229 * @alignment, if non-%NULL, is set to one less than the required
230 * alignment of the type. For example, for a 32bit integer, @alignment
231 * would be set to 3. This allows you to round an integer up to the
232 * proper alignment by performing the following efficient calculation:
234 * offset += ((-offset) & alignment);
237 g_variant_type_info_query (GVariantTypeInfo *info,
241 g_variant_type_info_check (info, 0);
244 *alignment = info->alignment;
247 *fixed_size = info->fixed_size;
251 #define ARRAY_INFO_CLASS 'a'
253 ARRAY_INFO (GVariantTypeInfo *info)
255 g_variant_type_info_check (info, ARRAY_INFO_CLASS);
257 return (ArrayInfo *) info;
261 array_info_free (GVariantTypeInfo *info)
263 ArrayInfo *array_info;
265 g_assert (info->container_class == ARRAY_INFO_CLASS);
266 array_info = (ArrayInfo *) info;
268 g_variant_type_info_unref (array_info->element);
269 g_slice_free (ArrayInfo, array_info);
272 static ContainerInfo *
273 array_info_new (const GVariantType *type)
277 info = g_slice_new (ArrayInfo);
278 info->container.info.container_class = ARRAY_INFO_CLASS;
280 info->element = g_variant_type_info_get (g_variant_type_element (type));
281 info->container.info.alignment = info->element->alignment;
282 info->container.info.fixed_size = 0;
284 return (ContainerInfo *) info;
288 * g_variant_type_info_element:
289 * @info: a #GVariantTypeInfo for an array or maybe type
291 * Returns the element type for the array or maybe type. A reference is
292 * not added, so the caller must add their own.
295 g_variant_type_info_element (GVariantTypeInfo *info)
297 return ARRAY_INFO (info)->element;
301 * g_variant_type_query_element:
302 * @info: a #GVariantTypeInfo for an array or maybe type
303 * @alignment: the location to store the alignment, or %NULL
304 * @fixed_size: the location to store the fixed size, or %NULL
306 * Returns the alignment requires and fixed size (if any) for the
307 * element type of the array. This call is a convenience wrapper around
308 * g_variant_type_info_element() and g_variant_type_info_query().
311 g_variant_type_info_query_element (GVariantTypeInfo *info,
315 g_variant_type_info_query (ARRAY_INFO (info)->element,
316 alignment, fixed_size);
320 #define TUPLE_INFO_CLASS 'r'
322 TUPLE_INFO (GVariantTypeInfo *info)
324 g_variant_type_info_check (info, TUPLE_INFO_CLASS);
326 return (TupleInfo *) info;
330 tuple_info_free (GVariantTypeInfo *info)
332 TupleInfo *tuple_info;
335 g_assert (info->container_class == TUPLE_INFO_CLASS);
336 tuple_info = (TupleInfo *) info;
338 for (i = 0; i < tuple_info->n_members; i++)
339 g_variant_type_info_unref (tuple_info->members[i].type_info);
341 g_slice_free1 (sizeof (GVariantMemberInfo) * tuple_info->n_members,
342 tuple_info->members);
343 g_slice_free (TupleInfo, tuple_info);
347 tuple_allocate_members (const GVariantType *type,
348 GVariantMemberInfo **members,
351 const GVariantType *item_type;
354 *n_members = g_variant_type_n_items (type);
355 *members = g_slice_alloc (sizeof (GVariantMemberInfo) * *n_members);
357 item_type = g_variant_type_first (type);
360 GVariantMemberInfo *member = &(*members)[i++];
362 member->type_info = g_variant_type_info_get (item_type);
363 item_type = g_variant_type_next (item_type);
365 if (member->type_info->fixed_size)
366 member->ending_type = G_VARIANT_MEMBER_ENDING_FIXED;
367 else if (item_type == NULL)
368 member->ending_type = G_VARIANT_MEMBER_ENDING_LAST;
370 member->ending_type = G_VARIANT_MEMBER_ENDING_OFFSET;
373 g_assert (i == *n_members);
376 /* this is g_variant_type_info_query for a given member of the tuple.
377 * before the access is done, it is ensured that the item is within
378 * range and %FALSE is returned if not.
381 tuple_get_item (TupleInfo *info,
382 GVariantMemberInfo *item,
386 if (&info->members[info->n_members] == item)
389 *d = item->type_info->alignment;
390 *e = item->type_info->fixed_size;
394 /* Read the documentation for #GVariantMemberInfo in gvarianttype.h
395 * before attempting to understand this.
397 * This function adds one set of "magic constant" values (for one item
398 * in the tuple) to the table.
400 * The algorithm in tuple_generate_table() calculates values of 'a', 'b'
401 * and 'c' for each item, such that the procedure for finding the item
402 * is to start at the end of the previous variable-sized item, add 'a',
403 * then round up to the nearest multiple of 'b', then then add 'c'.
404 * Note that 'b' is stored in the usual "one less than" form. ie:
406 * start = ROUND_UP(prev_end + a, (b + 1)) + c;
408 * We tweak these values a little to allow for a slightly easier
409 * computation and more compact storage.
412 tuple_table_append (GVariantMemberInfo **items,
418 GVariantMemberInfo *item = (*items)++;
420 /* We can shift multiples of the alignment size from 'c' into 'a'.
421 * As long as we're shifting whole multiples, it won't affect the
422 * result. This means that we can take the "aligned" portion off of
423 * 'c' and add it into 'a'.
425 * Imagine (for sake of clarity) that ROUND_10 rounds up to the
426 * nearest 10. It is clear that:
428 * ROUND_10(a) + c == ROUND_10(a + 10*(c / 10)) + (c % 10)
430 * ie: remove the 10s portion of 'c' and add it onto 'a'.
432 * To put some numbers on it, imagine we start with a = 34 and c = 27:
434 * ROUND_10(34) + 27 = 40 + 27 = 67
436 * but also, we can split 27 up into 20 and 7 and do this:
438 * ROUND_10(34 + 20) + 7 = ROUND_10(54) + 7 = 60 + 7 = 67
440 * without affecting the result. We do that here.
442 * This reduction in the size of 'c' means that we can store it in a
443 * gchar instead of a gsize. Due to how the structure is packed, this
444 * ends up saving us 'two pointer sizes' per item in each tuple when
445 * allocating using GSlice.
447 a += ~b & c; /* take the "aligned" part of 'c' and add to 'a' */
448 c &= b; /* chop 'c' to contain only the unaligned part */
451 /* Finally, we made one last adjustment. Recall:
453 * start = ROUND_UP(prev_end + a, (b + 1)) + c;
455 * Forgetting the '+ c' for the moment:
457 * ROUND_UP(prev_end + a, (b + 1));
459 * we can do a "round up" operation by adding 1 less than the amount
460 * to round up to, then rounding down. ie:
462 * #define ROUND_UP(x, y) ROUND_DOWN(x + (y-1), y)
464 * Of course, for rounding down to a power of two, we can just mask
465 * out the appropriate number of low order bits:
467 * #define ROUND_DOWN(x, y) (x & ~(y - 1))
471 * #define ROUND_UP(x, y) (x + (y - 1) & ~(y - 1))
473 * but recall that our alignment value 'b' is already "one less".
474 * This means that to round 'prev_end + a' up to 'b' we can just do:
476 * ((prev_end + a) + b) & ~b
478 * Associativity, and putting the 'c' back on:
480 * (prev_end + (a + b)) & ~b + c
482 * Now, since (a + b) is constant, we can just add 'b' to 'a' now and
483 * store that as the number to add to prev_end. Then we use ~b as the
484 * number to take a bitwise 'and' with. Finally, 'c' is added on.
486 * Note, however, that all the low order bits of the 'aligned' value
487 * are masked out and that all of the high order bits of 'c' have been
488 * "moved" to 'a' (in the previous step). This means that there are
489 * no overlapping bits in the addition -- so we can do a bitwise 'or'
492 * This means that we can now compute the start address of a given
493 * item in the tuple using the algorithm given in the documentation
494 * for #GVariantMemberInfo:
496 * item_start = ((prev_end + a) & b) | c;
506 tuple_align (gsize offset,
509 return offset + ((-offset) & alignment);
512 /* This function is the heart of the algorithm for calculating 'i', 'a',
513 * 'b' and 'c' for each item in the tuple.
515 * Imagine we want to find the start of the "i" in the type "(su(qx)ni)".
516 * That's a string followed by a uint32, then a tuple containing a
517 * uint16 and a int64, then an int16, then our "i". In order to get to
520 * Start at the end of the string, align to 4 (for the uint32), add 4.
521 * Align to 8, add 16 (for the tuple). Align to 2, add 2 (for the
522 * int16). Then we're there. It turns out that, given 3 simple rules,
523 * we can flatten this iteration into one addition, one alignment, then
526 * The loop below plays through each item in the tuple, querying its
527 * alignment and fixed_size into 'd' and 'e', respectively. At all
528 * times the variables 'a', 'b', and 'c' are maintained such that in
529 * order to get to the current point, you add 'a', align to 'b' then add
530 * 'c'. 'b' is kept in "one less than" form. For each item, the proper
531 * alignment is applied to find the values of 'a', 'b' and 'c' to get to
532 * the start of that item. Those values are recorded into the table.
533 * The fixed size of the item (if applicable) is then added on.
535 * These 3 rules are how 'a', 'b' and 'c' are modified for alignment and
536 * addition of fixed size. They have been proven correct but are
537 * presented here, without proof:
539 * 1) in order to "align to 'd'" where 'd' is less than or equal to the
540 * largest level of alignment seen so far ('b'), you align 'c' to
542 * 2) in order to "align to 'd'" where 'd' is greater than the largest
543 * level of alignment seen so far, you add 'c' aligned to 'b' to the
544 * value of 'a', set 'b' to 'd' (ie: increase the 'largest alignment
545 * seen') and reset 'c' to 0.
546 * 3) in order to "add 'e'", just add 'e' to 'c'.
549 tuple_generate_table (TupleInfo *info)
551 GVariantMemberInfo *items = info->members;
552 gsize i = -1, a = 0, b = 0, c = 0, d, e;
554 /* iterate over each item in the tuple.
555 * 'd' will be the alignment of the item (in one-less form)
556 * 'e' will be the fixed size (or 0 for variable-size items)
558 while (tuple_get_item (info, items, &d, &e))
562 c = tuple_align (c, d); /* rule 1 */
564 a += tuple_align (c, b), b = d, c = 0; /* rule 2 */
566 /* the start of the item is at this point (ie: right after we
567 * have aligned for it). store this information in the table.
569 tuple_table_append (&items, i, a, b, c);
571 /* "move past" the item by adding in its size. */
575 * we'll have an offset stored to mark the end of this item, so
576 * just bump the offset index to give us a new starting point
577 * and reset all the counters.
587 tuple_set_base_info (TupleInfo *info)
589 GVariantTypeInfo *base = &info->container.info;
591 if (info->n_members > 0)
593 GVariantMemberInfo *m;
595 /* the alignment requirement of the tuple is the alignment
596 * requirement of its largest item.
599 for (m = info->members; m < &info->members[info->n_members]; m++)
600 /* can find the max of a list of "one less than" powers of two
603 base->alignment |= m->type_info->alignment;
605 m--; /* take 'm' back to the last item */
607 /* the structure only has a fixed size if no variable-size
608 * offsets are stored and the last item is fixed-sized too (since
609 * an offset is never stored for the last item).
611 if (m->i == -1 && m->type_info->fixed_size)
612 /* in that case, the fixed size can be found by finding the
613 * start of the last item (in the usual way) and adding its
616 * if a tuple has a fixed size then it is always a multiple of
617 * the alignment requirement (to make packing into arrays
618 * easier) so we round up to that here.
621 tuple_align (((m->a & m->b) | m->c) + m->type_info->fixed_size,
624 /* else, the tuple is not fixed size */
625 base->fixed_size = 0;
629 /* the empty tuple: '()'.
631 * has a size of 1 and an no alignment requirement.
633 * It has a size of 1 (not 0) for two practical reasons:
635 * 1) So we can determine how many of them are in an array
636 * without dividing by zero or without other tricks.
638 * 2) Even if we had some trick to know the number of items in
639 * the array (as GVariant did at one time) this would open a
640 * potential denial of service attack: an attacker could send
641 * you an extremely small array (in terms of number of bytes)
642 * containing trillions of zero-sized items. If you iterated
643 * over this array you would effectively infinite-loop your
644 * program. By forcing a size of at least one, we bound the
645 * amount of computation done in response to a message to a
646 * reasonable function of the size of that message.
649 base->fixed_size = 1;
653 static ContainerInfo *
654 tuple_info_new (const GVariantType *type)
658 info = g_slice_new (TupleInfo);
659 info->container.info.container_class = TUPLE_INFO_CLASS;
661 tuple_allocate_members (type, &info->members, &info->n_members);
662 tuple_generate_table (info);
663 tuple_set_base_info (info);
665 return (ContainerInfo *) info;
669 * g_variant_type_info_n_members:
670 * @info: a #GVariantTypeInfo for a tuple or dictionary entry type
672 * Returns the number of members in a tuple or dictionary entry type.
673 * For a dictionary entry this will always be 2.
676 g_variant_type_info_n_members (GVariantTypeInfo *info)
678 return TUPLE_INFO (info)->n_members;
682 * g_variant_type_info_member_info:
683 * @info: a #GVariantTypeInfo for a tuple or dictionary entry type
684 * @index: the member to fetch information for
686 * Returns the #GVariantMemberInfo for a given member. See
687 * documentation for that structure for why you would want this
690 * @index must refer to a valid child (ie: strictly less than
691 * g_variant_type_info_n_members() returns).
693 const GVariantMemberInfo *
694 g_variant_type_info_member_info (GVariantTypeInfo *info,
697 TupleInfo *tuple_info = TUPLE_INFO (info);
699 if (index < tuple_info->n_members)
700 return &tuple_info->members[index];
705 /* == new/ref/unref == */
706 static GStaticRecMutex g_variant_type_info_lock = G_STATIC_REC_MUTEX_INIT;
707 static GHashTable *g_variant_type_info_table;
710 * g_variant_type_info_get:
711 * @type: a #GVariantType
713 * Returns a reference to a #GVariantTypeInfo for @type.
715 * If an info structure already exists for this type, a new reference is
716 * returned. If not, the required calculations are performed and a new
717 * info structure is returned.
719 * It is appropriate to call g_variant_type_info_unref() on the return
723 g_variant_type_info_get (const GVariantType *type)
727 type_char = g_variant_type_peek_string (type)[0];
729 if (type_char == G_VARIANT_TYPE_INFO_CHAR_MAYBE ||
730 type_char == G_VARIANT_TYPE_INFO_CHAR_ARRAY ||
731 type_char == G_VARIANT_TYPE_INFO_CHAR_TUPLE ||
732 type_char == G_VARIANT_TYPE_INFO_CHAR_DICT_ENTRY)
734 GVariantTypeInfo *info;
737 if G_UNLIKELY (g_variant_type_info_table == NULL)
738 g_variant_type_info_table = g_hash_table_new (g_str_hash,
741 type_string = g_variant_type_dup_string (type);
743 g_static_rec_mutex_lock (&g_variant_type_info_lock);
744 info = g_hash_table_lookup (g_variant_type_info_table, type_string);
748 ContainerInfo *container;
750 if (type_char == G_VARIANT_TYPE_INFO_CHAR_MAYBE ||
751 type_char == G_VARIANT_TYPE_INFO_CHAR_ARRAY)
753 container = array_info_new (type);
755 else /* tuple or dict entry */
757 container = tuple_info_new (type);
760 info = (GVariantTypeInfo *) container;
761 container->type_string = type_string;
762 container->ref_count = 1;
764 g_hash_table_insert (g_variant_type_info_table, type_string, info);
768 g_variant_type_info_ref (info);
770 g_static_rec_mutex_unlock (&g_variant_type_info_lock);
771 g_variant_type_info_check (info, 0);
772 g_free (type_string);
778 const GVariantTypeInfo *info;
781 index = type_char - 'b';
782 g_assert (G_N_ELEMENTS (g_variant_type_info_basic_table) == 24);
783 g_assert_cmpint (0, <=, index);
784 g_assert_cmpint (index, <, 24);
786 info = g_variant_type_info_basic_table + index;
787 g_variant_type_info_check (info, 0);
789 return (GVariantTypeInfo *) info;
794 * g_variant_type_info_ref:
795 * @info: a #GVariantTypeInfo
797 * Adds a reference to @info.
800 g_variant_type_info_ref (GVariantTypeInfo *info)
802 g_variant_type_info_check (info, 0);
804 if (info->container_class)
806 ContainerInfo *container = (ContainerInfo *) info;
808 g_assert_cmpint (container->ref_count, >, 0);
809 g_atomic_int_inc (&container->ref_count);
816 * g_variant_type_info_unref:
817 * @info: a #GVariantTypeInfo
819 * Releases a reference held on @info. This may result in @info being
823 g_variant_type_info_unref (GVariantTypeInfo *info)
825 g_variant_type_info_check (info, 0);
827 if (info->container_class)
829 ContainerInfo *container = (ContainerInfo *) info;
831 if (g_atomic_int_dec_and_test (&container->ref_count))
833 g_static_rec_mutex_lock (&g_variant_type_info_lock);
834 g_hash_table_remove (g_variant_type_info_table,
835 container->type_string);
836 g_static_rec_mutex_unlock (&g_variant_type_info_lock);
838 g_free (container->type_string);
840 if (info->container_class == ARRAY_INFO_CLASS)
841 array_info_free (info);
843 else if (info->container_class == TUPLE_INFO_CLASS)
844 tuple_info_free (info);
847 g_assert_not_reached ();
852 /* used from the test cases */
853 #define assert_no_type_infos() \
854 g_assert_cmpint (g_hash_table_size (g_variant_type_info_table), ==, 0)