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