fuzz: use qemu_get_exec_dir
[qemu.git] / qobject / block-qdict.c
1 /*
2 * Special QDict functions used by the block layer
3 *
4 * Copyright (c) 2013-2018 Red Hat, Inc.
5 *
6 * This work is licensed under the terms of the GNU LGPL, version 2.1 or later.
7 * See the COPYING.LIB file in the top-level directory.
8 */
9
10 #include "qemu/osdep.h"
11 #include "block/qdict.h"
12 #include "qapi/qmp/qbool.h"
13 #include "qapi/qmp/qlist.h"
14 #include "qapi/qmp/qnum.h"
15 #include "qapi/qmp/qstring.h"
16 #include "qapi/qobject-input-visitor.h"
17 #include "qemu/cutils.h"
18 #include "qapi/error.h"
19
20 /**
21 * qdict_copy_default(): If no entry mapped by 'key' exists in 'dst' yet, the
22 * value of 'key' in 'src' is copied there (and the refcount increased
23 * accordingly).
24 */
25 void qdict_copy_default(QDict *dst, QDict *src, const char *key)
26 {
27 QObject *val;
28
29 if (qdict_haskey(dst, key)) {
30 return;
31 }
32
33 val = qdict_get(src, key);
34 if (val) {
35 qdict_put_obj(dst, key, qobject_ref(val));
36 }
37 }
38
39 /**
40 * qdict_set_default_str(): If no entry mapped by 'key' exists in 'dst' yet, a
41 * new QString initialised by 'val' is put there.
42 */
43 void qdict_set_default_str(QDict *dst, const char *key, const char *val)
44 {
45 if (qdict_haskey(dst, key)) {
46 return;
47 }
48
49 qdict_put_str(dst, key, val);
50 }
51
52 static void qdict_flatten_qdict(QDict *qdict, QDict *target,
53 const char *prefix);
54
55 static void qdict_flatten_qlist(QList *qlist, QDict *target, const char *prefix)
56 {
57 QObject *value;
58 const QListEntry *entry;
59 QDict *dict_val;
60 QList *list_val;
61 char *new_key;
62 int i;
63
64 /* This function is never called with prefix == NULL, i.e., it is always
65 * called from within qdict_flatten_q(list|dict)(). Therefore, it does not
66 * need to remove list entries during the iteration (the whole list will be
67 * deleted eventually anyway from qdict_flatten_qdict()). */
68 assert(prefix);
69
70 entry = qlist_first(qlist);
71
72 for (i = 0; entry; entry = qlist_next(entry), i++) {
73 value = qlist_entry_obj(entry);
74 dict_val = qobject_to(QDict, value);
75 list_val = qobject_to(QList, value);
76 new_key = g_strdup_printf("%s.%i", prefix, i);
77
78 /*
79 * Flatten non-empty QDict and QList recursively into @target,
80 * copy other objects to @target
81 */
82 if (dict_val && qdict_size(dict_val)) {
83 qdict_flatten_qdict(dict_val, target, new_key);
84 } else if (list_val && !qlist_empty(list_val)) {
85 qdict_flatten_qlist(list_val, target, new_key);
86 } else {
87 qdict_put_obj(target, new_key, qobject_ref(value));
88 }
89
90 g_free(new_key);
91 }
92 }
93
94 static void qdict_flatten_qdict(QDict *qdict, QDict *target, const char *prefix)
95 {
96 QObject *value;
97 const QDictEntry *entry, *next;
98 QDict *dict_val;
99 QList *list_val;
100 char *key, *new_key;
101
102 entry = qdict_first(qdict);
103
104 while (entry != NULL) {
105 next = qdict_next(qdict, entry);
106 value = qdict_entry_value(entry);
107 dict_val = qobject_to(QDict, value);
108 list_val = qobject_to(QList, value);
109
110 if (prefix) {
111 key = new_key = g_strdup_printf("%s.%s", prefix, entry->key);
112 } else {
113 key = entry->key;
114 new_key = NULL;
115 }
116
117 /*
118 * Flatten non-empty QDict and QList recursively into @target,
119 * copy other objects to @target.
120 * On the root level (if @qdict == @target), remove flattened
121 * nested QDicts and QLists from @qdict.
122 *
123 * (Note that we do not need to remove entries from nested
124 * dicts or lists. Their reference count is decremented on
125 * the root level, so there are no leaks. In fact, if they
126 * have a reference count greater than one, we are probably
127 * well advised not to modify them altogether.)
128 */
129 if (dict_val && qdict_size(dict_val)) {
130 qdict_flatten_qdict(dict_val, target, key);
131 if (target == qdict) {
132 qdict_del(qdict, entry->key);
133 }
134 } else if (list_val && !qlist_empty(list_val)) {
135 qdict_flatten_qlist(list_val, target, key);
136 if (target == qdict) {
137 qdict_del(qdict, entry->key);
138 }
139 } else if (target != qdict) {
140 qdict_put_obj(target, key, qobject_ref(value));
141 }
142
143 g_free(new_key);
144 entry = next;
145 }
146 }
147
148 /**
149 * qdict_flatten(): For each nested non-empty QDict with key x, all
150 * fields with key y are moved to this QDict and their key is renamed
151 * to "x.y". For each nested non-empty QList with key x, the field at
152 * index y is moved to this QDict with the key "x.y" (i.e., the
153 * reverse of what qdict_array_split() does).
154 * This operation is applied recursively for nested QDicts and QLists.
155 */
156 void qdict_flatten(QDict *qdict)
157 {
158 qdict_flatten_qdict(qdict, qdict, NULL);
159 }
160
161 /* extract all the src QDict entries starting by start into dst.
162 * If dst is NULL then the entries are simply removed from src. */
163 void qdict_extract_subqdict(QDict *src, QDict **dst, const char *start)
164
165 {
166 const QDictEntry *entry, *next;
167 const char *p;
168
169 if (dst) {
170 *dst = qdict_new();
171 }
172 entry = qdict_first(src);
173
174 while (entry != NULL) {
175 next = qdict_next(src, entry);
176 if (strstart(entry->key, start, &p)) {
177 if (dst) {
178 qdict_put_obj(*dst, p, qobject_ref(entry->value));
179 }
180 qdict_del(src, entry->key);
181 }
182 entry = next;
183 }
184 }
185
186 static int qdict_count_prefixed_entries(const QDict *src, const char *start)
187 {
188 const QDictEntry *entry;
189 int count = 0;
190
191 for (entry = qdict_first(src); entry; entry = qdict_next(src, entry)) {
192 if (strstart(entry->key, start, NULL)) {
193 if (count == INT_MAX) {
194 return -ERANGE;
195 }
196 count++;
197 }
198 }
199
200 return count;
201 }
202
203 /**
204 * qdict_array_split(): This function moves array-like elements of a QDict into
205 * a new QList. Every entry in the original QDict with a key "%u" or one
206 * prefixed "%u.", where %u designates an unsigned integer starting at 0 and
207 * incrementally counting up, will be moved to a new QDict at index %u in the
208 * output QList with the key prefix removed, if that prefix is "%u.". If the
209 * whole key is just "%u", the whole QObject will be moved unchanged without
210 * creating a new QDict. The function terminates when there is no entry in the
211 * QDict with a prefix directly (incrementally) following the last one; it also
212 * returns if there are both entries with "%u" and "%u." for the same index %u.
213 * Example: {"0.a": 42, "0.b": 23, "1.x": 0, "4.y": 1, "o.o": 7, "2": 66}
214 * (or {"1.x": 0, "4.y": 1, "0.a": 42, "o.o": 7, "0.b": 23, "2": 66})
215 * => [{"a": 42, "b": 23}, {"x": 0}, 66]
216 * and {"4.y": 1, "o.o": 7} (remainder of the old QDict)
217 */
218 void qdict_array_split(QDict *src, QList **dst)
219 {
220 unsigned i;
221
222 *dst = qlist_new();
223
224 for (i = 0; i < UINT_MAX; i++) {
225 QObject *subqobj;
226 bool is_subqdict;
227 QDict *subqdict;
228 char indexstr[32], prefix[32];
229 size_t snprintf_ret;
230
231 snprintf_ret = snprintf(indexstr, 32, "%u", i);
232 assert(snprintf_ret < 32);
233
234 subqobj = qdict_get(src, indexstr);
235
236 snprintf_ret = snprintf(prefix, 32, "%u.", i);
237 assert(snprintf_ret < 32);
238
239 /* Overflow is the same as positive non-zero results */
240 is_subqdict = qdict_count_prefixed_entries(src, prefix);
241
242 /*
243 * There may be either a single subordinate object (named
244 * "%u") or multiple objects (each with a key prefixed "%u."),
245 * but not both.
246 */
247 if (!subqobj == !is_subqdict) {
248 break;
249 }
250
251 if (is_subqdict) {
252 qdict_extract_subqdict(src, &subqdict, prefix);
253 assert(qdict_size(subqdict) > 0);
254 } else {
255 qobject_ref(subqobj);
256 qdict_del(src, indexstr);
257 }
258
259 qlist_append_obj(*dst, subqobj ?: QOBJECT(subqdict));
260 }
261 }
262
263 /**
264 * qdict_split_flat_key:
265 * @key: the key string to split
266 * @prefix: non-NULL pointer to hold extracted prefix
267 * @suffix: non-NULL pointer to remaining suffix
268 *
269 * Given a flattened key such as 'foo.0.bar', split it into two parts
270 * at the first '.' separator. Allows double dot ('..') to escape the
271 * normal separator.
272 *
273 * e.g.
274 * 'foo.0.bar' -> prefix='foo' and suffix='0.bar'
275 * 'foo..0.bar' -> prefix='foo.0' and suffix='bar'
276 *
277 * The '..' sequence will be unescaped in the returned 'prefix'
278 * string. The 'suffix' string will be left in escaped format, so it
279 * can be fed back into the qdict_split_flat_key() key as the input
280 * later.
281 *
282 * The caller is responsible for freeing the string returned in @prefix
283 * using g_free().
284 */
285 static void qdict_split_flat_key(const char *key, char **prefix,
286 const char **suffix)
287 {
288 const char *separator;
289 size_t i, j;
290
291 /* Find first '.' separator, but if there is a pair '..'
292 * that acts as an escape, so skip over '..' */
293 separator = NULL;
294 do {
295 if (separator) {
296 separator += 2;
297 } else {
298 separator = key;
299 }
300 separator = strchr(separator, '.');
301 } while (separator && separator[1] == '.');
302
303 if (separator) {
304 *prefix = g_strndup(key, separator - key);
305 *suffix = separator + 1;
306 } else {
307 *prefix = g_strdup(key);
308 *suffix = NULL;
309 }
310
311 /* Unescape the '..' sequence into '.' */
312 for (i = 0, j = 0; (*prefix)[i] != '\0'; i++, j++) {
313 if ((*prefix)[i] == '.') {
314 assert((*prefix)[i + 1] == '.');
315 i++;
316 }
317 (*prefix)[j] = (*prefix)[i];
318 }
319 (*prefix)[j] = '\0';
320 }
321
322 /**
323 * qdict_is_list:
324 * @maybe_list: dict to check if keys represent list elements.
325 *
326 * Determine whether all keys in @maybe_list are valid list elements.
327 * If @maybe_list is non-zero in length and all the keys look like
328 * valid list indexes, this will return 1. If @maybe_list is zero
329 * length or all keys are non-numeric then it will return 0 to indicate
330 * it is a normal qdict. If there is a mix of numeric and non-numeric
331 * keys, or the list indexes are non-contiguous, an error is reported.
332 *
333 * Returns: 1 if a valid list, 0 if a dict, -1 on error
334 */
335 static int qdict_is_list(QDict *maybe_list, Error **errp)
336 {
337 const QDictEntry *ent;
338 ssize_t len = 0;
339 ssize_t max = -1;
340 int is_list = -1;
341 int64_t val;
342
343 for (ent = qdict_first(maybe_list); ent != NULL;
344 ent = qdict_next(maybe_list, ent)) {
345 int is_index = !qemu_strtoi64(ent->key, NULL, 10, &val);
346
347 if (is_list == -1) {
348 is_list = is_index;
349 }
350
351 if (is_index != is_list) {
352 error_setg(errp, "Cannot mix list and non-list keys");
353 return -1;
354 }
355
356 if (is_index) {
357 len++;
358 if (val > max) {
359 max = val;
360 }
361 }
362 }
363
364 if (is_list == -1) {
365 assert(!qdict_size(maybe_list));
366 is_list = 0;
367 }
368
369 /* NB this isn't a perfect check - e.g. it won't catch
370 * a list containing '1', '+1', '01', '3', but that
371 * does not matter - we've still proved that the
372 * input is a list. It is up the caller to do a
373 * stricter check if desired */
374 if (len != (max + 1)) {
375 error_setg(errp, "List indices are not contiguous, "
376 "saw %zd elements but %zd largest index",
377 len, max);
378 return -1;
379 }
380
381 return is_list;
382 }
383
384 /**
385 * qdict_crumple:
386 * @src: the original flat dictionary (only scalar values) to crumple
387 *
388 * Takes a flat dictionary whose keys use '.' separator to indicate
389 * nesting, and values are scalars, empty dictionaries or empty lists,
390 * and crumples it into a nested structure.
391 *
392 * To include a literal '.' in a key name, it must be escaped as '..'
393 *
394 * For example, an input of:
395 *
396 * { 'foo.0.bar': 'one', 'foo.0.wizz': '1',
397 * 'foo.1.bar': 'two', 'foo.1.wizz': '2' }
398 *
399 * will result in an output of:
400 *
401 * {
402 * 'foo': [
403 * { 'bar': 'one', 'wizz': '1' },
404 * { 'bar': 'two', 'wizz': '2' }
405 * ],
406 * }
407 *
408 * The following scenarios in the input dict will result in an
409 * error being returned:
410 *
411 * - Any values in @src are non-scalar types
412 * - If keys in @src imply that a particular level is both a
413 * list and a dict. e.g., "foo.0.bar" and "foo.eek.bar".
414 * - If keys in @src imply that a particular level is a list,
415 * but the indices are non-contiguous. e.g. "foo.0.bar" and
416 * "foo.2.bar" without any "foo.1.bar" present.
417 * - If keys in @src represent list indexes, but are not in
418 * the "%zu" format. e.g. "foo.+0.bar"
419 *
420 * Returns: either a QDict or QList for the nested data structure, or NULL
421 * on error
422 */
423 QObject *qdict_crumple(const QDict *src, Error **errp)
424 {
425 const QDictEntry *ent;
426 QDict *two_level, *multi_level = NULL, *child_dict;
427 QDict *dict_val;
428 QList *list_val;
429 QObject *dst = NULL, *child;
430 size_t i;
431 char *prefix = NULL;
432 const char *suffix = NULL;
433 int is_list;
434
435 two_level = qdict_new();
436
437 /* Step 1: split our totally flat dict into a two level dict */
438 for (ent = qdict_first(src); ent != NULL; ent = qdict_next(src, ent)) {
439 dict_val = qobject_to(QDict, ent->value);
440 list_val = qobject_to(QList, ent->value);
441 if ((dict_val && qdict_size(dict_val))
442 || (list_val && !qlist_empty(list_val))) {
443 error_setg(errp, "Value %s is not flat", ent->key);
444 goto error;
445 }
446
447 qdict_split_flat_key(ent->key, &prefix, &suffix);
448 child = qdict_get(two_level, prefix);
449 child_dict = qobject_to(QDict, child);
450
451 if (child) {
452 /*
453 * If @child_dict, then all previous keys with this prefix
454 * had a suffix. If @suffix, this one has one as well,
455 * and we're good, else there's a clash.
456 */
457 if (!child_dict || !suffix) {
458 error_setg(errp, "Cannot mix scalar and non-scalar keys");
459 goto error;
460 }
461 }
462
463 if (suffix) {
464 if (!child_dict) {
465 child_dict = qdict_new();
466 qdict_put(two_level, prefix, child_dict);
467 }
468 qdict_put_obj(child_dict, suffix, qobject_ref(ent->value));
469 } else {
470 qdict_put_obj(two_level, prefix, qobject_ref(ent->value));
471 }
472
473 g_free(prefix);
474 prefix = NULL;
475 }
476
477 /* Step 2: optionally process the two level dict recursively
478 * into a multi-level dict */
479 multi_level = qdict_new();
480 for (ent = qdict_first(two_level); ent != NULL;
481 ent = qdict_next(two_level, ent)) {
482 dict_val = qobject_to(QDict, ent->value);
483 if (dict_val && qdict_size(dict_val)) {
484 child = qdict_crumple(dict_val, errp);
485 if (!child) {
486 goto error;
487 }
488
489 qdict_put_obj(multi_level, ent->key, child);
490 } else {
491 qdict_put_obj(multi_level, ent->key, qobject_ref(ent->value));
492 }
493 }
494 qobject_unref(two_level);
495 two_level = NULL;
496
497 /* Step 3: detect if we need to turn our dict into list */
498 is_list = qdict_is_list(multi_level, errp);
499 if (is_list < 0) {
500 goto error;
501 }
502
503 if (is_list) {
504 dst = QOBJECT(qlist_new());
505
506 for (i = 0; i < qdict_size(multi_level); i++) {
507 char *key = g_strdup_printf("%zu", i);
508
509 child = qdict_get(multi_level, key);
510 g_free(key);
511
512 if (!child) {
513 error_setg(errp, "Missing list index %zu", i);
514 goto error;
515 }
516
517 qlist_append_obj(qobject_to(QList, dst), qobject_ref(child));
518 }
519 qobject_unref(multi_level);
520 multi_level = NULL;
521 } else {
522 dst = QOBJECT(multi_level);
523 }
524
525 return dst;
526
527 error:
528 g_free(prefix);
529 qobject_unref(multi_level);
530 qobject_unref(two_level);
531 qobject_unref(dst);
532 return NULL;
533 }
534
535 /**
536 * qdict_crumple_for_keyval_qiv:
537 * @src: the flat dictionary (only scalar values) to crumple
538 * @errp: location to store error
539 *
540 * Like qdict_crumple(), but additionally transforms scalar values so
541 * the result can be passed to qobject_input_visitor_new_keyval().
542 *
543 * The block subsystem uses this function to prepare its flat QDict
544 * with possibly confused scalar types for a visit. It should not be
545 * used for anything else, and it should go away once the block
546 * subsystem has been cleaned up.
547 */
548 static QObject *qdict_crumple_for_keyval_qiv(QDict *src, Error **errp)
549 {
550 QDict *tmp = NULL;
551 char *buf;
552 const char *s;
553 const QDictEntry *ent;
554 QObject *dst;
555
556 for (ent = qdict_first(src); ent; ent = qdict_next(src, ent)) {
557 buf = NULL;
558 switch (qobject_type(ent->value)) {
559 case QTYPE_QNULL:
560 case QTYPE_QSTRING:
561 continue;
562 case QTYPE_QNUM:
563 s = buf = qnum_to_string(qobject_to(QNum, ent->value));
564 break;
565 case QTYPE_QDICT:
566 case QTYPE_QLIST:
567 /* @src isn't flat; qdict_crumple() will fail */
568 continue;
569 case QTYPE_QBOOL:
570 s = qbool_get_bool(qobject_to(QBool, ent->value))
571 ? "on" : "off";
572 break;
573 default:
574 abort();
575 }
576
577 if (!tmp) {
578 tmp = qdict_clone_shallow(src);
579 }
580 qdict_put_str(tmp, ent->key, s);
581 g_free(buf);
582 }
583
584 dst = qdict_crumple(tmp ?: src, errp);
585 qobject_unref(tmp);
586 return dst;
587 }
588
589 /**
590 * qdict_array_entries(): Returns the number of direct array entries if the
591 * sub-QDict of src specified by the prefix in subqdict (or src itself for
592 * prefix == "") is valid as an array, i.e. the length of the created list if
593 * the sub-QDict would become empty after calling qdict_array_split() on it. If
594 * the array is not valid, -EINVAL is returned.
595 */
596 int qdict_array_entries(QDict *src, const char *subqdict)
597 {
598 const QDictEntry *entry;
599 unsigned i;
600 unsigned entries = 0;
601 size_t subqdict_len = strlen(subqdict);
602
603 assert(!subqdict_len || subqdict[subqdict_len - 1] == '.');
604
605 /* qdict_array_split() loops until UINT_MAX, but as we want to return
606 * negative errors, we only have a signed return value here. Any additional
607 * entries will lead to -EINVAL. */
608 for (i = 0; i < INT_MAX; i++) {
609 QObject *subqobj;
610 int subqdict_entries;
611 char *prefix = g_strdup_printf("%s%u.", subqdict, i);
612
613 subqdict_entries = qdict_count_prefixed_entries(src, prefix);
614
615 /* Remove ending "." */
616 prefix[strlen(prefix) - 1] = 0;
617 subqobj = qdict_get(src, prefix);
618
619 g_free(prefix);
620
621 if (subqdict_entries < 0) {
622 return subqdict_entries;
623 }
624
625 /* There may be either a single subordinate object (named "%u") or
626 * multiple objects (each with a key prefixed "%u."), but not both. */
627 if (subqobj && subqdict_entries) {
628 return -EINVAL;
629 } else if (!subqobj && !subqdict_entries) {
630 break;
631 }
632
633 entries += subqdict_entries ? subqdict_entries : 1;
634 }
635
636 /* Consider everything handled that isn't part of the given sub-QDict */
637 for (entry = qdict_first(src); entry; entry = qdict_next(src, entry)) {
638 if (!strstart(qdict_entry_key(entry), subqdict, NULL)) {
639 entries++;
640 }
641 }
642
643 /* Anything left in the sub-QDict that wasn't handled? */
644 if (qdict_size(src) != entries) {
645 return -EINVAL;
646 }
647
648 return i;
649 }
650
651 /**
652 * qdict_join(): Absorb the src QDict into the dest QDict, that is, move all
653 * elements from src to dest.
654 *
655 * If an element from src has a key already present in dest, it will not be
656 * moved unless overwrite is true.
657 *
658 * If overwrite is true, the conflicting values in dest will be discarded and
659 * replaced by the corresponding values from src.
660 *
661 * Therefore, with overwrite being true, the src QDict will always be empty when
662 * this function returns. If overwrite is false, the src QDict will be empty
663 * iff there were no conflicts.
664 */
665 void qdict_join(QDict *dest, QDict *src, bool overwrite)
666 {
667 const QDictEntry *entry, *next;
668
669 entry = qdict_first(src);
670 while (entry) {
671 next = qdict_next(src, entry);
672
673 if (overwrite || !qdict_haskey(dest, entry->key)) {
674 qdict_put_obj(dest, entry->key, qobject_ref(entry->value));
675 qdict_del(src, entry->key);
676 }
677
678 entry = next;
679 }
680 }
681
682 /**
683 * qdict_rename_keys(): Rename keys in qdict according to the replacements
684 * specified in the array renames. The array must be terminated by an entry
685 * with from = NULL.
686 *
687 * The renames are performed individually in the order of the array, so entries
688 * may be renamed multiple times and may or may not conflict depending on the
689 * order of the renames array.
690 *
691 * Returns true for success, false in error cases.
692 */
693 bool qdict_rename_keys(QDict *qdict, const QDictRenames *renames, Error **errp)
694 {
695 QObject *qobj;
696
697 while (renames->from) {
698 if (qdict_haskey(qdict, renames->from)) {
699 if (qdict_haskey(qdict, renames->to)) {
700 error_setg(errp, "'%s' and its alias '%s' can't be used at the "
701 "same time", renames->to, renames->from);
702 return false;
703 }
704
705 qobj = qdict_get(qdict, renames->from);
706 qdict_put_obj(qdict, renames->to, qobject_ref(qobj));
707 qdict_del(qdict, renames->from);
708 }
709
710 renames++;
711 }
712 return true;
713 }
714
715 /*
716 * Create a QObject input visitor for flat @qdict with possibly
717 * confused scalar types.
718 *
719 * The block subsystem uses this function to visit its flat QDict with
720 * possibly confused scalar types. It should not be used for anything
721 * else, and it should go away once the block subsystem has been
722 * cleaned up.
723 */
724 Visitor *qobject_input_visitor_new_flat_confused(QDict *qdict,
725 Error **errp)
726 {
727 QObject *crumpled;
728 Visitor *v;
729
730 crumpled = qdict_crumple_for_keyval_qiv(qdict, errp);
731 if (!crumpled) {
732 return NULL;
733 }
734
735 v = qobject_input_visitor_new_keyval(crumpled);
736 qobject_unref(crumpled);
737 return v;
738 }