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);
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 (*members)[i++].type = g_variant_type_info_get (item_type);
361 item_type = g_variant_type_next (item_type);
364 g_assert (i == *n_members);
367 /* this is g_variant_type_info_query for a given member of the tuple.
368 * before the access is done, it is ensured that the item is within
369 * range and %FALSE is returned if not.
372 tuple_get_item (TupleInfo *info,
373 GVariantMemberInfo *item,
377 if (&info->members[info->n_members] == item)
380 *d = item->type->alignment;
381 *e = item->type->fixed_size;
385 /* Read the documentation for #GVariantMemberInfo in gvarianttype.h
386 * before attempting to understand this.
388 * This function adds one set of "magic constant" values (for one item
389 * in the tuple) to the table.
391 * The algorithm in tuple_generate_table() calculates values of 'a', 'b'
392 * and 'c' for each item, such that the procedure for finding the item
393 * is to start at the end of the previous variable-sized item, add 'a',
394 * then round up to the nearest multiple of 'b', then then add 'c'.
395 * Note that 'b' is stored in the usual "one less than" form. ie:
397 * start = ROUND_UP(prev_end + a, (b + 1)) + c;
399 * We tweak these values a little to allow for a slightly easier
400 * computation and more compact storage.
403 tuple_table_append (GVariantMemberInfo **items,
409 GVariantMemberInfo *item = (*items)++;
411 /* We can shift multiples of the alignment size from 'c' into 'a'.
412 * As long as we're shifting whole multiples, it won't affect the
413 * result. This means that we can take the "aligned" portion off of
414 * 'c' and add it into 'a'.
416 * Imagine (for sake of clarity) that ROUND_10 rounds up to the
417 * nearest 10. It is clear that:
419 * ROUND_10(a) + c == ROUND_10(a + 10*(c / 10)) + (c % 10)
421 * ie: remove the 10s portion of 'c' and add it onto 'a'.
423 * To put some numbers on it, imagine we start with a = 34 and c = 27:
425 * ROUND_10(34) + 27 = 40 + 27 = 67
427 * but also, we can split 27 up into 20 and 7 and do this:
429 * ROUND_10(34 + 20) + 7 = ROUND_10(54) + 7 = 60 + 7 = 67
431 * without affecting the result. We do that here.
433 * This reduction in the size of 'c' means that we can store it in a
434 * gchar instead of a gsize. Due to how the structure is packed, this
435 * ends up saving us 'two pointer sizes' per item in each tuple when
436 * allocating using GSlice.
438 a += ~b & c; /* take the "aligned" part of 'c' and add to 'a' */
439 c &= b; /* chop 'c' to contain only the unaligned part */
442 /* Finally, we made one last adjustment. Recall:
444 * start = ROUND_UP(prev_end + a, (b + 1)) + c;
446 * Forgetting the '+ c' for the moment:
448 * ROUND_UP(prev_end + a, (b + 1));
450 * we can do a "round up" operation by adding 1 less than the amount
451 * to round up to, then rounding down. ie:
453 * #define ROUND_UP(x, y) ROUND_DOWN(x + (y-1), y)
455 * Of course, for rounding down to a power of two, we can just mask
456 * out the appropriate number of low order bits:
458 * #define ROUND_DOWN(x, y) (x & ~(y - 1))
462 * #define ROUND_UP(x, y) (x + (y - 1) & ~(y - 1))
464 * but recall that our alignment value 'b' is already "one less".
465 * This means that to round 'prev_end + a' up to 'b' we can just do:
467 * ((prev_end + a) + b) & ~b
469 * Associativity, and putting the 'c' back on:
471 * (prev_end + (a + b)) & ~b + c
473 * Now, since (a + b) is constant, we can just add 'b' to 'a' now and
474 * store that as the number to add to prev_end. Then we use ~b as the
475 * number to take a bitwise 'and' with. Finally, 'c' is added on.
477 * Note, however, that all the low order bits of the 'aligned' value
478 * are masked out and that all of the high order bits of 'c' have been
479 * "moved" to 'a' (in the previous step). This means that there are
480 * no overlapping bits in the addition -- so we can do a bitwise 'or'
483 * This means that we can now compute the start address of a given
484 * item in the tuple using the algorithm given in the documentation
485 * for #GVariantMemberInfo:
487 * item_start = ((prev_end + a) & b) | c;
497 tuple_align (gsize offset,
500 return offset + ((-offset) & alignment);
503 /* This function is the heart of the algorithm for calculating 'i', 'a',
504 * 'b' and 'c' for each item in the tuple.
506 * Imagine we want to find the start of the "i" in the type "(su(qx)ni)".
507 * That's a string followed by a uint32, then a tuple containing a
508 * uint16 and a int64, then an int16, then our "i". In order to get to
511 * Start at the end of the string, align to 4 (for the uint32), add 4.
512 * Align to 8, add 16 (for the tuple). Align to 2, add 2 (for the
513 * int16). Then we're there. It turns out that, given 3 simple rules,
514 * we can flatten this iteration into one addition, one alignment, then
517 * The loop below plays through each item in the tuple, querying its
518 * alignment and fixed_size into 'd' and 'e', respectively. At all
519 * times the variables 'a', 'b', and 'c' are maintained such that in
520 * order to get to the current point, you add 'a', align to 'b' then add
521 * 'c'. 'b' is kept in "one less than" form. For each item, the proper
522 * alignment is applied to find the values of 'a', 'b' and 'c' to get to
523 * the start of that item. Those values are recorded into the table.
524 * The fixed size of the item (if applicable) is then added on.
526 * These 3 rules are how 'a', 'b' and 'c' are modified for alignment and
527 * addition of fixed size. They have been proven correct but are
528 * presented here, without proof:
530 * 1) in order to "align to 'd'" where 'd' is less than or equal to the
531 * largest level of alignment seen so far ('b'), you align 'c' to
533 * 2) in order to "align to 'd'" where 'd' is greater than the largest
534 * level of alignment seen so far, you add 'c' aligned to 'b' to the
535 * value of 'a', set 'b' to 'd' (ie: increase the 'largest alignment
536 * seen') and reset 'c' to 0.
537 * 3) in order to "add 'e'", just add 'e' to 'c'.
540 tuple_generate_table (TupleInfo *info)
542 GVariantMemberInfo *items = info->members;
543 gsize i = -1, a = 0, b = 0, c = 0, d, e;
545 /* iterate over each item in the tuple.
546 * 'd' will be the alignment of the item (in one-less form)
547 * 'e' will be the fixed size (or 0 for variable-size items)
549 while (tuple_get_item (info, items, &d, &e))
553 c = tuple_align (c, d); /* rule 1 */
555 a += tuple_align (c, b), b = d, c = 0; /* rule 2 */
557 /* the start of the item is at this point (ie: right after we
558 * have aligned for it). store this information in the table.
560 tuple_table_append (&items, i, a, b, c);
562 /* "move past" the item by adding in its size. */
566 * we'll have an offset stored to mark the end of this item, so
567 * just bump the offset index to give us a new starting point
568 * and reset all the counters.
578 tuple_set_base_info (TupleInfo *info)
580 GVariantTypeInfo *base = &info->container.info;
582 if (info->n_members > 0)
584 GVariantMemberInfo *m;
586 /* the alignment requirement of the tuple is the alignment
587 * requirement of its largest item.
590 for (m = info->members; m < &info->members[info->n_members]; m++)
591 /* can find the max of a list of "one less than" powers of two
594 base->alignment |= m->type->alignment;
596 m--; /* take 'm' back to the last item */
598 /* the structure only has a fixed size if no variable-size
599 * offsets are stored and the last item is fixed-sized too (since
600 * an offset is never stored for the last item).
602 if (m->i == -1 && m->type->fixed_size)
603 /* in that case, the fixed size can be found by finding the
604 * start of the last item (in the usual way) and adding its
607 * if a tuple has a fixed size then it is always a multiple of
608 * the alignment requirement (to make packing into arrays
609 * easier) so we round up to that here.
612 tuple_align (((m->a & m->b) | m->c) + m->type->fixed_size,
615 /* else, the tuple is not fixed size */
616 base->fixed_size = 0;
620 /* the empty tuple: '()'.
622 * has a size of 1 and an no alignment requirement.
624 * It has a size of 1 (not 0) for two practical reasons:
626 * 1) So we can determine how many of them are in an array
627 * without dividing by zero or without other tricks.
629 * 2) Even if we had some trick to know the number of items in
630 * the array (as GVariant did at one time) this would open a
631 * potential denial of service attack: an attacker could send
632 * you an extremely small array (in terms of number of bytes)
633 * containing trillions of zero-sized items. If you iterated
634 * over this array you would effectively infinite-loop your
635 * program. By forcing a size of at least one, we bound the
636 * amount of computation done in response to a message to a
637 * reasonable function of the size of that message.
640 base->fixed_size = 1;
644 static ContainerInfo *
645 tuple_info_new (const GVariantType *type)
649 info = g_slice_new (TupleInfo);
650 info->container.info.container_class = TUPLE_INFO_CLASS;
652 tuple_allocate_members (type, &info->members, &info->n_members);
653 tuple_generate_table (info);
654 tuple_set_base_info (info);
656 return (ContainerInfo *) info;
660 * g_variant_type_info_n_members:
661 * @info: a #GVariantTypeInfo for a tuple or dictionary entry type
663 * Returns the number of members in a tuple or dictionary entry type.
664 * For a dictionary entry this will always be 2.
667 g_variant_type_info_n_members (GVariantTypeInfo *info)
669 return TUPLE_INFO (info)->n_members;
673 * g_variant_type_info_member_info:
674 * @info: a #GVariantTypeInfo for a tuple or dictionary entry type
675 * @index: the member to fetch information for
677 * Returns the #GVariantMemberInfo for a given member. See
678 * documentation for that structure for why you would want this
681 * @index must refer to a valid child (ie: strictly less than
682 * g_variant_type_info_n_members() returns).
684 const GVariantMemberInfo *
685 g_variant_type_info_member_info (GVariantTypeInfo *info,
688 TupleInfo *tuple_info = TUPLE_INFO (info);
690 if (index < tuple_info->n_members)
691 return &tuple_info->members[index];
696 /* == new/ref/unref == */
697 static GStaticRecMutex g_variant_type_info_lock = G_STATIC_REC_MUTEX_INIT;
698 static GHashTable *g_variant_type_info_table;
701 * g_variant_type_info_get:
702 * @type: a #GVariantType
704 * Returns a reference to a #GVariantTypeInfo for @type.
706 * If an info structure already exists for this type, a new reference is
707 * returned. If not, the required calculations are performed and a new
708 * info structure is returned.
710 * It is appropriate to call g_variant_type_info_unref() on the return
714 g_variant_type_info_get (const GVariantType *type)
718 type_char = g_variant_type_peek_string (type)[0];
720 if (type_char == G_VARIANT_TYPE_INFO_CHAR_MAYBE ||
721 type_char == G_VARIANT_TYPE_INFO_CHAR_ARRAY ||
722 type_char == G_VARIANT_TYPE_INFO_CHAR_TUPLE ||
723 type_char == G_VARIANT_TYPE_INFO_CHAR_DICT_ENTRY)
725 GVariantTypeInfo *info;
728 if G_UNLIKELY (g_variant_type_info_table == NULL)
729 g_variant_type_info_table = g_hash_table_new (g_str_hash,
732 type_string = g_variant_type_dup_string (type);
734 g_static_rec_mutex_lock (&g_variant_type_info_lock);
735 info = g_hash_table_lookup (g_variant_type_info_table, type_string);
739 ContainerInfo *container;
741 if (type_char == G_VARIANT_TYPE_INFO_CHAR_MAYBE ||
742 type_char == G_VARIANT_TYPE_INFO_CHAR_ARRAY)
744 container = array_info_new (type);
746 else /* tuple or dict entry */
748 container = tuple_info_new (type);
751 info = (GVariantTypeInfo *) container;
752 container->type_string = type_string;
753 container->ref_count = 1;
755 g_hash_table_insert (g_variant_type_info_table, type_string, info);
759 g_variant_type_info_ref (info);
761 g_static_rec_mutex_unlock (&g_variant_type_info_lock);
762 g_variant_type_info_check (info, 0);
763 g_free (type_string);
769 const GVariantTypeInfo *info;
772 index = type_char - 'b';
773 g_assert (G_N_ELEMENTS (g_variant_type_info_basic_table) == 24);
774 g_assert_cmpint (0, <=, index);
775 g_assert_cmpint (index, <, 24);
777 info = g_variant_type_info_basic_table + index;
778 g_variant_type_info_check (info, 0);
780 return (GVariantTypeInfo *) info;
785 * g_variant_type_info_ref:
786 * @info: a #GVariantTypeInfo
788 * Adds a reference to @info.
791 g_variant_type_info_ref (GVariantTypeInfo *info)
793 g_variant_type_info_check (info, 0);
795 if (info->container_class)
797 ContainerInfo *container = (ContainerInfo *) info;
799 g_assert_cmpint (container->ref_count, >, 0);
800 g_atomic_int_inc (&container->ref_count);
807 * g_variant_type_info_unref:
808 * @info: a #GVariantTypeInfo
810 * Releases a reference held on @info. This may result in @info being
814 g_variant_type_info_unref (GVariantTypeInfo *info)
816 g_variant_type_info_check (info, 0);
818 if (info->container_class)
820 ContainerInfo *container = (ContainerInfo *) info;
822 if (g_atomic_int_dec_and_test (&container->ref_count))
824 g_static_rec_mutex_lock (&g_variant_type_info_lock);
825 g_hash_table_remove (g_variant_type_info_table,
826 container->type_string);
827 g_static_rec_mutex_unlock (&g_variant_type_info_lock);
829 g_free (container->type_string);
831 if (info->container_class == ARRAY_INFO_CLASS)
832 array_info_free (info);
834 else if (info->container_class == TUPLE_INFO_CLASS)
835 tuple_info_free (info);
838 g_assert_not_reached ();