Branch data Line data Source code
1 : : /*
2 : : * Copyright © 2008 Ryan Lortie
3 : : * Copyright © 2010 Codethink Limited
4 : : *
5 : : * SPDX-License-Identifier: LGPL-2.1-or-later
6 : : *
7 : : * This library is free software; you can redistribute it and/or
8 : : * modify it under the terms of the GNU Lesser General Public
9 : : * License as published by the Free Software Foundation; either
10 : : * version 2.1 of the License, or (at your option) any later version.
11 : : *
12 : : * This library is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 : : * Lesser General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU Lesser General Public
18 : : * License along with this library; if not, see <http://www.gnu.org/licenses/>.
19 : : *
20 : : * Author: Ryan Lortie <desrt@desrt.ca>
21 : : */
22 : :
23 : : #include "config.h"
24 : :
25 : : #include "gvarianttype-private.h"
26 : : #include "gvarianttypeinfo.h"
27 : :
28 : : #include <glib/gtestutils.h>
29 : : #include <glib/gthread.h>
30 : : #include <glib/gslice.h>
31 : : #include <glib/ghash.h>
32 : : #include <glib/grefcount.h>
33 : :
34 : : #include "glib-private.h"
35 : : #include "glib_trace.h"
36 : :
37 : : /* < private >
38 : : * GVariantTypeInfo:
39 : : *
40 : : * This structure contains the necessary information to facilitate the
41 : : * serialization and fast deserialization of a given type of GVariant
42 : : * value. A GVariant instance holds a pointer to one of these
43 : : * structures to provide for efficient operation.
44 : : *
45 : : * The GVariantTypeInfo structures for all of the base types, plus the
46 : : * "variant" type are stored in a read-only static array.
47 : : *
48 : : * For container types, a hash table and reference counting is used to
49 : : * ensure that only one of these structures exists for any given type.
50 : : * In general, a container GVariantTypeInfo will exist for a given type
51 : : * only if one or more GVariant instances of that type exist or if
52 : : * another GVariantTypeInfo has that type as a subtype. For example, if
53 : : * a process contains a single GVariant instance with type "(asv)", then
54 : : * container GVariantTypeInfo structures will exist for "(asv)" and
55 : : * for "as" (note that "s" and "v" always exist in the static array).
56 : : *
57 : : * The trickiest part of GVariantTypeInfo (and in fact, the major reason
58 : : * for its existence) is the storage of somewhat magical constants that
59 : : * allow for O(1) lookups of items in tuples. This is described below.
60 : : *
61 : : * 'container_class' is set to 'a' or 'r' if the GVariantTypeInfo is
62 : : * contained inside of an ArrayInfo or TupleInfo, respectively. This
63 : : * allows the storage of the necessary additional information.
64 : : *
65 : : * 'fixed_size' is set to the fixed size of the type, if applicable, or
66 : : * 0 otherwise (since no type has a fixed size of 0).
67 : : *
68 : : * 'alignment' is set to one less than the alignment requirement for
69 : : * this type. This makes many operations much more convenient.
70 : : */
71 : : struct _GVariantTypeInfo
72 : : {
73 : : gsize fixed_size;
74 : : guchar alignment;
75 : : guchar container_class;
76 : : };
77 : :
78 : : /* Container types are reference counted. They also need to have their
79 : : * type string stored explicitly since it is not merely a single letter.
80 : : */
81 : : typedef struct
82 : : {
83 : : GVariantTypeInfo info;
84 : :
85 : : gchar *type_string;
86 : : gatomicrefcount ref_count;
87 : : } ContainerInfo;
88 : :
89 : : /* For 'array' and 'maybe' types, we store some extra information on the
90 : : * end of the GVariantTypeInfo struct -- the element type (ie: "s" for
91 : : * "as"). The container GVariantTypeInfo structure holds a reference to
92 : : * the element typeinfo.
93 : : */
94 : : typedef struct
95 : : {
96 : : ContainerInfo container;
97 : :
98 : : GVariantTypeInfo *element;
99 : : } ArrayInfo;
100 : :
101 : : /* For 'tuple' and 'dict entry' types, we store extra information for
102 : : * each member -- its type and how to find it inside the serialized data
103 : : * in O(1) time using 4 variables -- 'i', 'a', 'b', and 'c'. See the
104 : : * comment on GVariantMemberInfo in gvarianttypeinfo.h.
105 : : */
106 : : typedef struct
107 : : {
108 : : ContainerInfo container;
109 : :
110 : : GVariantMemberInfo *members;
111 : : gsize n_members;
112 : : } TupleInfo;
113 : :
114 : :
115 : : /* Hard-code the base types in a constant array */
116 : : static const GVariantTypeInfo g_variant_type_info_basic_table[24] = {
117 : : #define fixed_aligned(x) x, x - 1, 0
118 : : #define not_a_type 0, 0, 0
119 : : #define unaligned 0, 0, 0
120 : : #define aligned(x) 0, x - 1, 0
121 : : /* 'b' */ { fixed_aligned(1) }, /* boolean */
122 : : /* 'c' */ { not_a_type },
123 : : /* 'd' */ { fixed_aligned(8) }, /* double */
124 : : /* 'e' */ { not_a_type },
125 : : /* 'f' */ { not_a_type },
126 : : /* 'g' */ { unaligned }, /* signature string */
127 : : /* 'h' */ { fixed_aligned(4) }, /* file handle (int32) */
128 : : /* 'i' */ { fixed_aligned(4) }, /* int32 */
129 : : /* 'j' */ { not_a_type },
130 : : /* 'k' */ { not_a_type },
131 : : /* 'l' */ { not_a_type },
132 : : /* 'm' */ { not_a_type },
133 : : /* 'n' */ { fixed_aligned(2) }, /* int16 */
134 : : /* 'o' */ { unaligned }, /* object path string */
135 : : /* 'p' */ { not_a_type },
136 : : /* 'q' */ { fixed_aligned(2) }, /* uint16 */
137 : : /* 'r' */ { not_a_type },
138 : : /* 's' */ { unaligned }, /* string */
139 : : /* 't' */ { fixed_aligned(8) }, /* uint64 */
140 : : /* 'u' */ { fixed_aligned(4) }, /* uint32 */
141 : : /* 'v' */ { aligned(8) }, /* variant */
142 : : /* 'w' */ { not_a_type },
143 : : /* 'x' */ { fixed_aligned(8) }, /* int64 */
144 : : /* 'y' */ { fixed_aligned(1) }, /* byte */
145 : : #undef fixed_aligned
146 : : #undef not_a_type
147 : : #undef unaligned
148 : : #undef aligned
149 : : };
150 : :
151 : : /* We need to have type strings to return for the base types. We store
152 : : * those in another array. Since all base type strings are single
153 : : * characters this is easy. By not storing pointers to strings into the
154 : : * GVariantTypeInfo itself, we save a bunch of relocations.
155 : : */
156 : : static const char g_variant_type_info_basic_chars[24][2] = {
157 : : "b", " ", "d", " ", " ", "g", "h", "i", " ", " ", " ", " ",
158 : : "n", "o", " ", "q", " ", "s", "t", "u", "v", " ", "x", "y"
159 : : };
160 : :
161 : : /* sanity checks to make debugging easier */
162 : : static void
163 : 65166316 : g_variant_type_info_check (const GVariantTypeInfo *info,
164 : : char container_class)
165 : : {
166 : : #if defined(G_ENABLE_DEBUG) && !defined(G_DISABLE_ASSERT)
167 : 65166316 : g_assert (!container_class || info->container_class == container_class);
168 : :
169 : : /* alignment can only be one of these */
170 : 65166316 : g_assert (info->alignment == 0 || info->alignment == 1 ||
171 : : info->alignment == 3 || info->alignment == 7);
172 : :
173 : 65166316 : if (info->container_class)
174 : : {
175 : 33402528 : ContainerInfo *container = (ContainerInfo *) info;
176 : :
177 : : /* extra checks for containers */
178 : 33402528 : g_assert (!g_atomic_ref_count_compare (&container->ref_count, 0));
179 : 33402528 : g_assert (container->type_string != NULL);
180 : : }
181 : : else
182 : : {
183 : : gint index;
184 : :
185 : : /* if not a container, then ensure that it is a valid member of
186 : : * the basic types table
187 : : */
188 : 31763788 : index = info - g_variant_type_info_basic_table;
189 : :
190 : : g_assert (G_N_ELEMENTS (g_variant_type_info_basic_table) == 24);
191 : : g_assert (G_N_ELEMENTS (g_variant_type_info_basic_chars) == 24);
192 : 31763788 : g_assert (0 <= index && index < 24);
193 : 31763788 : g_assert (g_variant_type_info_basic_chars[index][0] != ' ');
194 : : }
195 : : #endif /* G_ENABLE_DEBUG && !G_DISABLE_ASSERT */
196 : 65166316 : }
197 : :
198 : : /* < private >
199 : : * g_variant_type_info_get_type_string:
200 : : * @info: a #GVariantTypeInfo
201 : : *
202 : : * Gets the type string for @info. The string is nul-terminated.
203 : : */
204 : : const gchar *
205 : 25973691 : g_variant_type_info_get_type_string (GVariantTypeInfo *info)
206 : : {
207 : 25973691 : g_variant_type_info_check (info, 0);
208 : :
209 : 25973691 : if (info->container_class)
210 : : {
211 : 10474704 : ContainerInfo *container = (ContainerInfo *) info;
212 : :
213 : : /* containers have their type string stored inside them */
214 : 10474704 : return container->type_string;
215 : : }
216 : : else
217 : : {
218 : : gint index;
219 : :
220 : : /* look up the type string in the base type array. the call to
221 : : * g_variant_type_info_check() above already ensured validity.
222 : : */
223 : 15498987 : index = info - g_variant_type_info_basic_table;
224 : :
225 : 15498987 : return g_variant_type_info_basic_chars[index];
226 : : }
227 : : }
228 : :
229 : : /* < private >
230 : : * g_variant_type_info_query:
231 : : * @info: a #GVariantTypeInfo
232 : : * @alignment: (out) (optional): the location to store the alignment, or %NULL
233 : : * @fixed_size: (out) (optional): the location to store the fixed size, or %NULL
234 : : *
235 : : * Queries @info to determine the alignment requirements and fixed size
236 : : * (if any) of the type.
237 : : *
238 : : * @fixed_size, if non-%NULL is set to the fixed size of the type, or 0
239 : : * to indicate that the type is a variable-sized type. No type has a
240 : : * fixed size of 0.
241 : : *
242 : : * @alignment, if non-%NULL, is set to one less than the required
243 : : * alignment of the type. For example, for a 32bit integer, @alignment
244 : : * would be set to 3. This allows you to round an integer up to the
245 : : * proper alignment by performing the following efficient calculation:
246 : : *
247 : : * offset += ((-offset) & alignment);
248 : : */
249 : : void
250 : 31415187 : g_variant_type_info_query (GVariantTypeInfo *info,
251 : : guint *alignment,
252 : : gsize *fixed_size)
253 : : {
254 : 31415187 : if (alignment)
255 : 18824247 : *alignment = info->alignment;
256 : :
257 : 31415187 : if (fixed_size)
258 : 28662919 : *fixed_size = info->fixed_size;
259 : 31415187 : }
260 : :
261 : : /* < private >
262 : : * g_variant_type_info_query_depth:
263 : : * @info: a #GVariantTypeInfo
264 : : *
265 : : * Queries @info to determine the depth of the type.
266 : : *
267 : : * See g_variant_type_string_get_depth_() for more details.
268 : : *
269 : : * Returns: depth of @info
270 : : * Since: 2.60
271 : : */
272 : : gsize
273 : 1002626 : g_variant_type_info_query_depth (GVariantTypeInfo *info)
274 : : {
275 : 1002626 : g_variant_type_info_check (info, 0);
276 : :
277 : 1002626 : if (info->container_class)
278 : : {
279 : 117690 : ContainerInfo *container = (ContainerInfo *) info;
280 : 117690 : return g_variant_type_string_get_depth_ (container->type_string);
281 : : }
282 : :
283 : 884936 : return 1;
284 : : }
285 : :
286 : : /* == array == */
287 : : #define GV_ARRAY_INFO_CLASS 'a'
288 : : static ArrayInfo *
289 : 11042947 : GV_ARRAY_INFO (GVariantTypeInfo *info)
290 : : {
291 : 11042947 : g_variant_type_info_check (info, GV_ARRAY_INFO_CLASS);
292 : :
293 : 11042947 : return (ArrayInfo *) info;
294 : : }
295 : :
296 : : static void
297 : 8039 : array_info_free (GVariantTypeInfo *info)
298 : : {
299 : : ArrayInfo *array_info;
300 : :
301 : 8039 : g_assert (info->container_class == GV_ARRAY_INFO_CLASS);
302 : 8039 : array_info = (ArrayInfo *) info;
303 : :
304 : 8039 : g_variant_type_info_unref (array_info->element);
305 : 8039 : g_slice_free (ArrayInfo, array_info);
306 : 8039 : }
307 : :
308 : : static ContainerInfo *
309 : 8649 : array_info_new (const GVariantType *type)
310 : : {
311 : : ArrayInfo *info;
312 : :
313 : 8649 : info = g_slice_new (ArrayInfo);
314 : 8649 : info->container.info.container_class = GV_ARRAY_INFO_CLASS;
315 : :
316 : 8649 : info->element = g_variant_type_info_get (g_variant_type_element (type));
317 : 8649 : info->container.info.alignment = info->element->alignment;
318 : 8649 : info->container.info.fixed_size = 0;
319 : :
320 : 8649 : return (ContainerInfo *) info;
321 : : }
322 : :
323 : : /* < private >
324 : : * g_variant_type_info_element:
325 : : * @info: a #GVariantTypeInfo for an array or maybe type
326 : : *
327 : : * Returns the element type for the array or maybe type. A reference is
328 : : * not added, so the caller must add their own.
329 : : */
330 : : GVariantTypeInfo *
331 : 3246141 : g_variant_type_info_element (GVariantTypeInfo *info)
332 : : {
333 : 3246141 : return GV_ARRAY_INFO (info)->element;
334 : : }
335 : :
336 : : /* < private >
337 : : * g_variant_type_query_element:
338 : : * @info: a #GVariantTypeInfo for an array or maybe type
339 : : * @alignment: (out) (optional): the location to store the alignment, or %NULL
340 : : * @fixed_size: (out) (optional): the location to store the fixed size, or %NULL
341 : : *
342 : : * Returns the alignment requires and fixed size (if any) for the
343 : : * element type of the array. This call is a convenience wrapper around
344 : : * g_variant_type_info_element() and g_variant_type_info_query().
345 : : */
346 : : void
347 : 7796806 : g_variant_type_info_query_element (GVariantTypeInfo *info,
348 : : guint *alignment,
349 : : gsize *fixed_size)
350 : : {
351 : 7796806 : g_variant_type_info_query (GV_ARRAY_INFO (info)->element,
352 : : alignment, fixed_size);
353 : 7796806 : }
354 : :
355 : : /* == tuple == */
356 : : #define GV_TUPLE_INFO_CLASS 'r'
357 : : static TupleInfo *
358 : 9588092 : GV_TUPLE_INFO (GVariantTypeInfo *info)
359 : : {
360 : 9588092 : g_variant_type_info_check (info, GV_TUPLE_INFO_CLASS);
361 : :
362 : 9588092 : return (TupleInfo *) info;
363 : : }
364 : :
365 : : static void
366 : 21123 : tuple_info_free (GVariantTypeInfo *info)
367 : : {
368 : : TupleInfo *tuple_info;
369 : : gsize i;
370 : :
371 : 21123 : g_assert (info->container_class == GV_TUPLE_INFO_CLASS);
372 : 21123 : tuple_info = (TupleInfo *) info;
373 : :
374 : 458575 : for (i = 0; i < tuple_info->n_members; i++)
375 : 437452 : g_variant_type_info_unref (tuple_info->members[i].type_info);
376 : :
377 : 21123 : g_slice_free1 (sizeof (GVariantMemberInfo) * tuple_info->n_members,
378 : 21123 : tuple_info->members);
379 : 21123 : g_slice_free (TupleInfo, tuple_info);
380 : 21123 : }
381 : :
382 : : static void
383 : 21787 : tuple_allocate_members (const GVariantType *type,
384 : : GVariantMemberInfo **members,
385 : : gsize *n_members)
386 : : {
387 : : const GVariantType *item_type;
388 : 21787 : gsize i = 0;
389 : :
390 : 21787 : *n_members = g_variant_type_n_items (type);
391 : 21787 : *members = g_slice_alloc (sizeof (GVariantMemberInfo) * *n_members);
392 : :
393 : 21787 : item_type = g_variant_type_first (type);
394 : 460604 : while (item_type)
395 : : {
396 : 438817 : GVariantMemberInfo *member = &(*members)[i++];
397 : :
398 : 438817 : member->type_info = g_variant_type_info_get (item_type);
399 : 438817 : item_type = g_variant_type_next (item_type);
400 : :
401 : 438817 : if (member->type_info->fixed_size)
402 : 376662 : member->ending_type = G_VARIANT_MEMBER_ENDING_FIXED;
403 : 62155 : else if (item_type == NULL)
404 : 9921 : member->ending_type = G_VARIANT_MEMBER_ENDING_LAST;
405 : : else
406 : 52234 : member->ending_type = G_VARIANT_MEMBER_ENDING_OFFSET;
407 : : }
408 : :
409 : 21787 : g_assert (i == *n_members);
410 : 21787 : }
411 : :
412 : : /* this is g_variant_type_info_query for a given member of the tuple.
413 : : * before the access is done, it is ensured that the item is within
414 : : * range and %FALSE is returned if not.
415 : : */
416 : : static gboolean
417 : 460604 : tuple_get_item (TupleInfo *info,
418 : : GVariantMemberInfo *item,
419 : : gsize *d,
420 : : gsize *e)
421 : : {
422 : 460604 : if (&info->members[info->n_members] == item)
423 : 21787 : return FALSE;
424 : :
425 : 438817 : *d = item->type_info->alignment;
426 : 438817 : *e = item->type_info->fixed_size;
427 : 438817 : return TRUE;
428 : : }
429 : :
430 : : /* Read the documentation for #GVariantMemberInfo in gvarianttype.h
431 : : * before attempting to understand this.
432 : : *
433 : : * This function adds one set of "magic constant" values (for one item
434 : : * in the tuple) to the table.
435 : : *
436 : : * The algorithm in tuple_generate_table() calculates values of 'a', 'b'
437 : : * and 'c' for each item, such that the procedure for finding the item
438 : : * is to start at the end of the previous variable-sized item, add 'a',
439 : : * then round up to the nearest multiple of 'b', then then add 'c'.
440 : : * Note that 'b' is stored in the usual "one less than" form. ie:
441 : : *
442 : : * start = ROUND_UP(prev_end + a, (b + 1)) + c;
443 : : *
444 : : * We tweak these values a little to allow for a slightly easier
445 : : * computation and more compact storage.
446 : : */
447 : : static void
448 : 438817 : tuple_table_append (GVariantMemberInfo **items,
449 : : gsize i,
450 : : gsize a,
451 : : gsize b,
452 : : gsize c)
453 : : {
454 : 438817 : GVariantMemberInfo *item = (*items)++;
455 : :
456 : : /* We can shift multiples of the alignment size from 'c' into 'a'.
457 : : * As long as we're shifting whole multiples, it won't affect the
458 : : * result. This means that we can take the "aligned" portion off of
459 : : * 'c' and add it into 'a'.
460 : : *
461 : : * Imagine (for sake of clarity) that ROUND_10 rounds up to the
462 : : * nearest 10. It is clear that:
463 : : *
464 : : * ROUND_10(a) + c == ROUND_10(a + 10*(c / 10)) + (c % 10)
465 : : *
466 : : * ie: remove the 10s portion of 'c' and add it onto 'a'.
467 : : *
468 : : * To put some numbers on it, imagine we start with a = 34 and c = 27:
469 : : *
470 : : * ROUND_10(34) + 27 = 40 + 27 = 67
471 : : *
472 : : * but also, we can split 27 up into 20 and 7 and do this:
473 : : *
474 : : * ROUND_10(34 + 20) + 7 = ROUND_10(54) + 7 = 60 + 7 = 67
475 : : * ^^ ^
476 : : * without affecting the result. We do that here.
477 : : *
478 : : * This reduction in the size of 'c' means that we can store it in a
479 : : * gchar instead of a gsize. Due to how the structure is packed, this
480 : : * ends up saving us 'two pointer sizes' per item in each tuple when
481 : : * allocating using GSlice.
482 : : */
483 : 438817 : a += ~b & c; /* take the "aligned" part of 'c' and add to 'a' */
484 : 438817 : c &= b; /* chop 'c' to contain only the unaligned part */
485 : :
486 : :
487 : : /* Finally, we made one last adjustment. Recall:
488 : : *
489 : : * start = ROUND_UP(prev_end + a, (b + 1)) + c;
490 : : *
491 : : * Forgetting the '+ c' for the moment:
492 : : *
493 : : * ROUND_UP(prev_end + a, (b + 1));
494 : : *
495 : : * we can do a "round up" operation by adding 1 less than the amount
496 : : * to round up to, then rounding down. ie:
497 : : *
498 : : * #define ROUND_UP(x, y) ROUND_DOWN(x + (y-1), y)
499 : : *
500 : : * Of course, for rounding down to a power of two, we can just mask
501 : : * out the appropriate number of low order bits:
502 : : *
503 : : * #define ROUND_DOWN(x, y) (x & ~(y - 1))
504 : : *
505 : : * Which gives us
506 : : *
507 : : * #define ROUND_UP(x, y) (x + (y - 1) & ~(y - 1))
508 : : *
509 : : * but recall that our alignment value 'b' is already "one less".
510 : : * This means that to round 'prev_end + a' up to 'b' we can just do:
511 : : *
512 : : * ((prev_end + a) + b) & ~b
513 : : *
514 : : * Associativity, and putting the 'c' back on:
515 : : *
516 : : * (prev_end + (a + b)) & ~b + c
517 : : *
518 : : * Now, since (a + b) is constant, we can just add 'b' to 'a' now and
519 : : * store that as the number to add to prev_end. Then we use ~b as the
520 : : * number to take a bitwise 'and' with. Finally, 'c' is added on.
521 : : *
522 : : * Note, however, that all the low order bits of the 'aligned' value
523 : : * are masked out and that all of the high order bits of 'c' have been
524 : : * "moved" to 'a' (in the previous step). This means that there are
525 : : * no overlapping bits in the addition -- so we can do a bitwise 'or'
526 : : * equivalently.
527 : : *
528 : : * This means that we can now compute the start address of a given
529 : : * item in the tuple using the algorithm given in the documentation
530 : : * for #GVariantMemberInfo:
531 : : *
532 : : * item_start = ((prev_end + a) & b) | c;
533 : : */
534 : :
535 : 438817 : item->i = i;
536 : 438817 : item->a = a + b;
537 : 438817 : item->b = ~b;
538 : 438817 : item->c = c;
539 : 438817 : }
540 : :
541 : : static gsize
542 : 444985 : tuple_align (gsize offset,
543 : : guint alignment)
544 : : {
545 : 444985 : return offset + ((-offset) & alignment);
546 : : }
547 : :
548 : : /* This function is the heart of the algorithm for calculating 'i', 'a',
549 : : * 'b' and 'c' for each item in the tuple.
550 : : *
551 : : * Imagine we want to find the start of the "i" in the type "(su(qx)ni)".
552 : : * That's a string followed by a uint32, then a tuple containing a
553 : : * uint16 and an int64, then an int16, then our "i". In order to get to
554 : : * our "i" we:
555 : : *
556 : : * Start at the end of the string, align to 4 (for the uint32), add 4.
557 : : * Align to 8, add 16 (for the tuple). Align to 2, add 2 (for the
558 : : * int16). Then we're there. It turns out that, given 3 simple rules,
559 : : * we can flatten this iteration into one addition, one alignment, then
560 : : * one more addition.
561 : : *
562 : : * The loop below plays through each item in the tuple, querying its
563 : : * alignment and fixed_size into 'd' and 'e', respectively. At all
564 : : * times the variables 'a', 'b', and 'c' are maintained such that in
565 : : * order to get to the current point, you add 'a', align to 'b' then add
566 : : * 'c'. 'b' is kept in "one less than" form. For each item, the proper
567 : : * alignment is applied to find the values of 'a', 'b' and 'c' to get to
568 : : * the start of that item. Those values are recorded into the table.
569 : : * The fixed size of the item (if applicable) is then added on.
570 : : *
571 : : * These 3 rules are how 'a', 'b' and 'c' are modified for alignment and
572 : : * addition of fixed size. They have been proven correct but are
573 : : * presented here, without proof:
574 : : *
575 : : * 1) in order to "align to 'd'" where 'd' is less than or equal to the
576 : : * largest level of alignment seen so far ('b'), you align 'c' to
577 : : * 'd'.
578 : : * 2) in order to "align to 'd'" where 'd' is greater than the largest
579 : : * level of alignment seen so far, you add 'c' aligned to 'b' to the
580 : : * value of 'a', set 'b' to 'd' (ie: increase the 'largest alignment
581 : : * seen') and reset 'c' to 0.
582 : : * 3) in order to "add 'e'", just add 'e' to 'c'.
583 : : */
584 : : static void
585 : 21787 : tuple_generate_table (TupleInfo *info)
586 : : {
587 : 21787 : GVariantMemberInfo *items = info->members;
588 : 21787 : gsize i = -1, a = 0, b = 0, c = 0, d, e;
589 : :
590 : : /* iterate over each item in the tuple.
591 : : * 'd' will be the alignment of the item (in one-less form)
592 : : * 'e' will be the fixed size (or 0 for variable-size items)
593 : : */
594 : 460604 : while (tuple_get_item (info, items, &d, &e))
595 : : {
596 : : /* align to 'd' */
597 : 438817 : if (d <= b)
598 : 371867 : c = tuple_align (c, d); /* rule 1 */
599 : : else
600 : 66950 : a += tuple_align (c, b), b = d, c = 0; /* rule 2 */
601 : :
602 : : /* the start of the item is at this point (ie: right after we
603 : : * have aligned for it). store this information in the table.
604 : : */
605 : 438817 : tuple_table_append (&items, i, a, b, c);
606 : :
607 : : /* "move past" the item by adding in its size. */
608 : 438817 : if (e == 0)
609 : : /* variable size:
610 : : *
611 : : * we'll have an offset stored to mark the end of this item, so
612 : : * just bump the offset index to give us a new starting point
613 : : * and reset all the counters.
614 : : */
615 : 62155 : i++, a = b = c = 0;
616 : : else
617 : : /* fixed size */
618 : 376662 : c += e; /* rule 3 */
619 : : }
620 : 21787 : }
621 : :
622 : : static void
623 : 21787 : tuple_set_base_info (TupleInfo *info)
624 : : {
625 : 21787 : GVariantTypeInfo *base = &info->container.info;
626 : :
627 : 21787 : if (info->n_members > 0)
628 : : {
629 : : GVariantMemberInfo *m;
630 : :
631 : : /* the alignment requirement of the tuple is the alignment
632 : : * requirement of its largest item.
633 : : */
634 : 21694 : base->alignment = 0;
635 : 460511 : for (m = info->members; m < &info->members[info->n_members]; m++)
636 : : /* can find the max of a list of "one less than" powers of two
637 : : * by 'or'ing them
638 : : */
639 : 438817 : base->alignment |= m->type_info->alignment;
640 : :
641 : 21694 : m--; /* take 'm' back to the last item */
642 : :
643 : : /* the structure only has a fixed size if no variable-size
644 : : * offsets are stored and the last item is fixed-sized too (since
645 : : * an offset is never stored for the last item).
646 : : */
647 : 21694 : if (m->i == (gsize) -1 && m->type_info->fixed_size)
648 : : /* in that case, the fixed size can be found by finding the
649 : : * start of the last item (in the usual way) and adding its
650 : : * fixed size.
651 : : *
652 : : * if a tuple has a fixed size then it is always a multiple of
653 : : * the alignment requirement (to make packing into arrays
654 : : * easier) so we round up to that here.
655 : : */
656 : 6168 : base->fixed_size =
657 : 6168 : tuple_align (((m->a & m->b) | m->c) + m->type_info->fixed_size,
658 : 6168 : base->alignment);
659 : : else
660 : : /* else, the tuple is not fixed size */
661 : 15526 : base->fixed_size = 0;
662 : : }
663 : : else
664 : : {
665 : : /* the empty tuple: '()'.
666 : : *
667 : : * has a size of 1 and a no alignment requirement.
668 : : *
669 : : * It has a size of 1 (not 0) for two practical reasons:
670 : : *
671 : : * 1) So we can determine how many of them are in an array
672 : : * without dividing by zero or without other tricks.
673 : : *
674 : : * 2) Even if we had some trick to know the number of items in
675 : : * the array (as GVariant did at one time) this would open a
676 : : * potential denial of service attack: an attacker could send
677 : : * you an extremely small array (in terms of number of bytes)
678 : : * containing trillions of zero-sized items. If you iterated
679 : : * over this array you would effectively infinite-loop your
680 : : * program. By forcing a size of at least one, we bound the
681 : : * amount of computation done in response to a message to a
682 : : * reasonable function of the size of that message.
683 : : */
684 : 93 : base->alignment = 0;
685 : 93 : base->fixed_size = 1;
686 : : }
687 : 21787 : }
688 : :
689 : : static ContainerInfo *
690 : 21787 : tuple_info_new (const GVariantType *type)
691 : : {
692 : : TupleInfo *info;
693 : :
694 : 21787 : info = g_slice_new (TupleInfo);
695 : 21787 : info->container.info.container_class = GV_TUPLE_INFO_CLASS;
696 : :
697 : 21787 : tuple_allocate_members (type, &info->members, &info->n_members);
698 : 21787 : tuple_generate_table (info);
699 : 21787 : tuple_set_base_info (info);
700 : :
701 : 21787 : return (ContainerInfo *) info;
702 : : }
703 : :
704 : : /* < private >
705 : : * g_variant_type_info_n_members:
706 : : * @info: a #GVariantTypeInfo for a tuple or dictionary entry type
707 : : *
708 : : * Returns the number of members in a tuple or dictionary entry type.
709 : : * For a dictionary entry this will always be 2.
710 : : */
711 : : gsize
712 : 1875030 : g_variant_type_info_n_members (GVariantTypeInfo *info)
713 : : {
714 : 1875030 : return GV_TUPLE_INFO (info)->n_members;
715 : : }
716 : :
717 : : /* < private >
718 : : * g_variant_type_info_member_info:
719 : : * @info: a #GVariantTypeInfo for a tuple or dictionary entry type
720 : : * @index: the member to fetch information for
721 : : *
722 : : * Returns the #GVariantMemberInfo for a given member. See
723 : : * documentation for that structure for why you would want this
724 : : * information.
725 : : *
726 : : * @index must refer to a valid child (ie: strictly less than
727 : : * g_variant_type_info_n_members() returns).
728 : : */
729 : : const GVariantMemberInfo *
730 : 7713062 : g_variant_type_info_member_info (GVariantTypeInfo *info,
731 : : gsize index)
732 : : {
733 : 7713062 : TupleInfo *tuple_info = GV_TUPLE_INFO (info);
734 : :
735 : 7713062 : if (index < tuple_info->n_members)
736 : 7713062 : return &tuple_info->members[index];
737 : :
738 : 0 : return NULL;
739 : : }
740 : :
741 : : /* == new/ref/unref == */
742 : : static GRecMutex g_variant_type_info_lock;
743 : : static GHashTable *g_variant_type_info_table;
744 : : static GPtrArray *g_variant_type_info_gc;
745 : :
746 : : #define GC_THRESHOLD 32
747 : :
748 : : static void
749 : 943 : gc_while_locked (void)
750 : : {
751 : 31187 : while (g_variant_type_info_gc->len > 0)
752 : : {
753 : 29301 : GVariantTypeInfo *info = g_ptr_array_steal_index_fast (g_variant_type_info_gc, 0);
754 : 29301 : ContainerInfo *container = (ContainerInfo *)info;
755 : :
756 : 29301 : if (g_atomic_ref_count_dec (&container->ref_count))
757 : : {
758 : 29162 : TRACE(GLIB_VARIANT_TYPE_INFO_FREE(info));
759 : :
760 : 29162 : g_hash_table_remove (g_variant_type_info_table,
761 : 29162 : container->type_string);
762 : :
763 : 29162 : g_free (container->type_string);
764 : :
765 : 29162 : if (info->container_class == GV_ARRAY_INFO_CLASS)
766 : 8039 : array_info_free (info);
767 : 21123 : else if (info->container_class == GV_TUPLE_INFO_CLASS)
768 : 21123 : tuple_info_free (info);
769 : : else
770 : : g_assert_not_reached ();
771 : : }
772 : : }
773 : 943 : }
774 : :
775 : : /* < private >
776 : : * g_variant_type_info_get:
777 : : * @type: a #GVariantType
778 : : *
779 : : * Returns a reference to a #GVariantTypeInfo for @type.
780 : : *
781 : : * If an info structure already exists for this type, a new reference is
782 : : * returned. If not, the required calculations are performed and a new
783 : : * info structure is returned.
784 : : *
785 : : * It is appropriate to call g_variant_type_info_unref() on the return
786 : : * value.
787 : : */
788 : : GVariantTypeInfo *
789 : 4504986 : g_variant_type_info_get (const GVariantType *type)
790 : : {
791 : 4504986 : const gchar *type_string = g_variant_type_peek_string (type);
792 : 4504986 : const char type_char = type_string[0];
793 : :
794 : 4504986 : if (type_char == G_VARIANT_TYPE_INFO_CHAR_MAYBE ||
795 : 4367693 : type_char == G_VARIANT_TYPE_INFO_CHAR_ARRAY ||
796 : 4245418 : type_char == G_VARIANT_TYPE_INFO_CHAR_TUPLE ||
797 : : type_char == G_VARIANT_TYPE_INFO_CHAR_DICT_ENTRY)
798 : : {
799 : : GVariantTypeInfo *info;
800 : :
801 : 532759 : g_rec_mutex_lock (&g_variant_type_info_lock);
802 : :
803 : 532759 : if (g_variant_type_info_table == NULL)
804 : : {
805 : 135 : g_variant_type_info_table = g_hash_table_new ((GHashFunc)_g_variant_type_hash,
806 : : (GEqualFunc)_g_variant_type_equal);
807 : 135 : g_ignore_leak (g_variant_type_info_table);
808 : : }
809 : 532759 : info = g_hash_table_lookup (g_variant_type_info_table, type_string);
810 : :
811 : 532759 : if (info == NULL)
812 : : {
813 : : ContainerInfo *container;
814 : :
815 : 30436 : if (type_char == G_VARIANT_TYPE_INFO_CHAR_MAYBE ||
816 : : type_char == G_VARIANT_TYPE_INFO_CHAR_ARRAY)
817 : : {
818 : 8649 : container = array_info_new (type);
819 : : }
820 : : else /* tuple or dict entry */
821 : : {
822 : 21787 : container = tuple_info_new (type);
823 : : }
824 : :
825 : 30436 : info = (GVariantTypeInfo *) container;
826 : 30436 : container->type_string = g_variant_type_dup_string (type);
827 : 30436 : g_atomic_ref_count_init (&container->ref_count);
828 : :
829 : 30436 : TRACE(GLIB_VARIANT_TYPE_INFO_NEW(info, container->type_string));
830 : :
831 : 30436 : g_hash_table_replace (g_variant_type_info_table,
832 : 30436 : container->type_string, info);
833 : : }
834 : : else
835 : 502323 : g_variant_type_info_ref (info);
836 : :
837 : 532759 : g_rec_mutex_unlock (&g_variant_type_info_lock);
838 : 532759 : g_variant_type_info_check (info, 0);
839 : :
840 : 532759 : return info;
841 : : }
842 : : else
843 : : {
844 : : const GVariantTypeInfo *info;
845 : : int index;
846 : :
847 : 3972227 : index = type_char - 'b';
848 : : g_assert (G_N_ELEMENTS (g_variant_type_info_basic_table) == 24);
849 : 3972227 : g_assert_cmpint (0, <=, index);
850 : 3972227 : g_assert_cmpint (index, <, 24);
851 : :
852 : 3972227 : info = g_variant_type_info_basic_table + index;
853 : 3972227 : g_variant_type_info_check (info, 0);
854 : :
855 : 3972227 : TRACE(GLIB_VARIANT_TYPE_INFO_NEW(info, g_variant_type_info_basic_chars[index]));
856 : :
857 : 3972227 : return (GVariantTypeInfo *) info;
858 : : }
859 : : }
860 : :
861 : : /* < private >
862 : : * g_variant_type_info_ref:
863 : : * @info: a #GVariantTypeInfo
864 : : *
865 : : * Adds a reference to @info.
866 : : */
867 : : GVariantTypeInfo *
868 : 4527185 : g_variant_type_info_ref (GVariantTypeInfo *info)
869 : : {
870 : 4527185 : g_variant_type_info_check (info, 0);
871 : :
872 : 4527185 : if (info->container_class)
873 : : {
874 : 808458 : ContainerInfo *container = (ContainerInfo *) info;
875 : :
876 : 808458 : g_atomic_ref_count_inc (&container->ref_count);
877 : : }
878 : :
879 : 4527185 : return info;
880 : : }
881 : :
882 : : /* < private >
883 : : * g_variant_type_info_unref:
884 : : * @info: a #GVariantTypeInfo
885 : : *
886 : : * Releases a reference held on @info. This may result in @info being
887 : : * freed.
888 : : */
889 : : void
890 : 8526789 : g_variant_type_info_unref (GVariantTypeInfo *info)
891 : : {
892 : 8526789 : g_variant_type_info_check (info, 0);
893 : :
894 : 8526789 : if (info->container_class)
895 : : {
896 : 837878 : ContainerInfo *container = (ContainerInfo *) info;
897 : :
898 : 837878 : g_rec_mutex_lock (&g_variant_type_info_lock);
899 : 837878 : if (g_atomic_ref_count_dec (&container->ref_count))
900 : : {
901 : 29945 : if (g_variant_type_info_gc == NULL)
902 : : {
903 : 135 : g_variant_type_info_gc = g_ptr_array_new ();
904 : 135 : g_ignore_leak (g_variant_type_info_gc);
905 : : }
906 : :
907 : : /* Steal this instance and place it onto the GC queue.
908 : : * We may bring it back to life before the next GC.
909 : : */
910 : 29945 : g_atomic_ref_count_init (&container->ref_count);
911 : 29945 : g_ptr_array_add (g_variant_type_info_gc, info);
912 : :
913 : 29945 : if (g_variant_type_info_gc->len > GC_THRESHOLD)
914 : 926 : gc_while_locked ();
915 : : }
916 : 837878 : g_rec_mutex_unlock (&g_variant_type_info_lock);
917 : : }
918 : 8526789 : }
919 : :
920 : : void
921 : 17 : g_variant_type_info_assert_no_infos (void)
922 : : {
923 : : G_GNUC_UNUSED gboolean empty;
924 : :
925 : 17 : g_rec_mutex_lock (&g_variant_type_info_lock);
926 : 17 : if (g_variant_type_info_table != NULL)
927 : 17 : gc_while_locked ();
928 : 34 : empty = (g_variant_type_info_table == NULL ||
929 : 17 : g_hash_table_size (g_variant_type_info_table) == 0);
930 : 17 : g_rec_mutex_unlock (&g_variant_type_info_lock);
931 : :
932 : 17 : g_assert (empty);
933 : 17 : }
|
