lib/bootconfig.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Extra Boot Config
   4  * Masami Hiramatsu <[email protected]>
   5  */
   6
   7 #ifdef __KERNEL__
   8 #include <linux/bootconfig.h>
   9 #include <linux/bug.h>
  10 #include <linux/ctype.h>
  11 #include <linux/errno.h>
  12 #include <linux/kernel.h>
  13 #include <linux/memblock.h>
  14 #include <linux/string.h>
  15
  16 #ifdef CONFIG_BOOT_CONFIG_EMBED
  17 /* embedded_bootconfig_data is defined in bootconfig-data.S */
  18 extern __visible const char embedded_bootconfig_data[];
  19 extern __visible const char embedded_bootconfig_data_end[];
  20
  21 const char * __init xbc_get_embedded_bootconfig(size_t *size)
  22 {
  23         *size = embedded_bootconfig_data_end - embedded_bootconfig_data;
  24         return (*size) ? embedded_bootconfig_data : NULL;
  25 }
  26 #endif
  27
  28 #else /* !__KERNEL__ */
  29 /*
  30  * NOTE: This is only for tools/bootconfig, because tools/bootconfig will
  31  * run the parser sanity test.
  32  * This does NOT mean lib/bootconfig.c is available in the user space.
  33  * However, if you change this file, please make sure the tools/bootconfig
  34  * has no issue on building and running.
  35  */
  36 #include <linux/bootconfig.h>
  37 #endif
  38
  39 /*
  40  * Extra Boot Config (XBC) is given as tree-structured ascii text of
  41  * key-value pairs on memory.
  42  * xbc_parse() parses the text to build a simple tree. Each tree node is
  43  * simply a key word or a value. A key node may have a next key node or/and
  44  * a child node (both key and value). A value node may have a next value
  45  * node (for array).
  46  */
  47
  48 static struct xbc_node *xbc_nodes __initdata;
  49 static int xbc_node_num __initdata;
  50 static char *xbc_data __initdata;
  51 static size_t xbc_data_size __initdata;
  52 static struct xbc_node *last_parent __initdata;
  53 static const char *xbc_err_msg __initdata;
  54 static int xbc_err_pos __initdata;
  55 static int open_brace[XBC_DEPTH_MAX] __initdata;
  56 static int brace_index __initdata;
  57
  58 #ifdef __KERNEL__
  59 static inline void * __init xbc_alloc_mem(size_t size)
  60 {
  61         return memblock_alloc(size, SMP_CACHE_BYTES);
  62 }
  63
  64 static inline void __init xbc_free_mem(void *addr, size_t size, bool early)
  65 {
  66         if (early)
  67                 memblock_free(addr, size);
  68         else if (addr)
  69                 memblock_free_late(__pa(addr), size);
  70 }
  71
  72 #else /* !__KERNEL__ */
  73
  74 static inline void *xbc_alloc_mem(size_t size)
  75 {
  76         return malloc(size);
  77 }
  78
  79 static inline void xbc_free_mem(void *addr, size_t size, bool early)
  80 {
  81         free(addr);
  82 }
  83 #endif
  84 /**
  85  * xbc_get_info() - Get the information of loaded boot config
  86  * @node_size: A pointer to store the number of nodes.
  87  * @data_size: A pointer to store the size of bootconfig data.
  88  *
  89  * Get the number of used nodes in @node_size if it is not NULL,
  90  * and the size of bootconfig data in @data_size if it is not NULL.
  91  * Return 0 if the boot config is initialized, or return -ENODEV.
  92  */
  93 int __init xbc_get_info(int *node_size, size_t *data_size)
  94 {
  95         if (!xbc_data)
  96                 return -ENODEV;
  97
  98         if (node_size)
  99                 *node_size = xbc_node_num;
 100         if (data_size)
 101                 *data_size = xbc_data_size;
 102         return 0;
 103 }
 104
 105 static int __init xbc_parse_error(const char *msg, const char *p)
 106 {
 107         xbc_err_msg = msg;
 108         xbc_err_pos = (int)(p - xbc_data);
 109
 110         return -EINVAL;
 111 }
 112
 113 /**
 114  * xbc_root_node() - Get the root node of extended boot config
 115  *
 116  * Return the address of root node of extended boot config. If the
 117  * extended boot config is not initiized, return NULL.
 118  */
 119 struct xbc_node * __init xbc_root_node(void)
 120 {
 121         if (unlikely(!xbc_data))
 122                 return NULL;
 123
 124         return xbc_nodes;
 125 }
 126
 127 /**
 128  * xbc_node_index() - Get the index of XBC node
 129  * @node: A target node of getting index.
 130  *
 131  * Return the index number of @node in XBC node list.
 132  */
 133 int __init xbc_node_index(struct xbc_node *node)
 134 {
 135         return node - &xbc_nodes[0];
 136 }
 137
 138 /**
 139  * xbc_node_get_parent() - Get the parent XBC node
 140  * @node: An XBC node.
 141  *
 142  * Return the parent node of @node. If the node is top node of the tree,
 143  * return NULL.
 144  */
 145 struct xbc_node * __init xbc_node_get_parent(struct xbc_node *node)
 146 {
 147         return node->parent == XBC_NODE_MAX ? NULL : &xbc_nodes[node->parent];
 148 }
 149
 150 /**
 151  * xbc_node_get_child() - Get the child XBC node
 152  * @node: An XBC node.
 153  *
 154  * Return the first child node of @node. If the node has no child, return
 155  * NULL.
 156  */
 157 struct xbc_node * __init xbc_node_get_child(struct xbc_node *node)
 158 {
 159         return node->child ? &xbc_nodes[node->child] : NULL;
 160 }
 161
 162 /**
 163  * xbc_node_get_next() - Get the next sibling XBC node
 164  * @node: An XBC node.
 165  *
 166  * Return the NEXT sibling node of @node. If the node has no next sibling,
 167  * return NULL. Note that even if this returns NULL, it doesn't mean @node
 168  * has no siblings. (You also has to check whether the parent's child node
 169  * is @node or not.)
 170  */
 171 struct xbc_node * __init xbc_node_get_next(struct xbc_node *node)
 172 {
 173         return node->next ? &xbc_nodes[node->next] : NULL;
 174 }
 175
 176 /**
 177  * xbc_node_get_data() - Get the data of XBC node
 178  * @node: An XBC node.
 179  *
 180  * Return the data (which is always a null terminated string) of @node.
 181  * If the node has invalid data, warn and return NULL.
 182  */
 183 const char * __init xbc_node_get_data(struct xbc_node *node)
 184 {
 185         int offset = node->data & ~XBC_VALUE;
 186
 187         if (WARN_ON(offset >= xbc_data_size))
 188                 return NULL;
 189
 190         return xbc_data + offset;
 191 }
 192
 193 static bool __init
 194 xbc_node_match_prefix(struct xbc_node *node, const char **prefix)
 195 {
 196         const char *p = xbc_node_get_data(node);
 197         int len = strlen(p);
 198
 199         if (strncmp(*prefix, p, len))
 200                 return false;
 201
 202         p = *prefix + len;
 203         if (*p == '.')
 204                 p++;
 205         else if (*p != '\0')
 206                 return false;
 207         *prefix = p;
 208
 209         return true;
 210 }
 211
 212 /**
 213  * xbc_node_find_subkey() - Find a subkey node which matches given key
 214  * @parent: An XBC node.
 215  * @key: A key string.
 216  *
 217  * Search a key node under @parent which matches @key. The @key can contain
 218  * several words jointed with '.'. If @parent is NULL, this searches the
 219  * node from whole tree. Return NULL if no node is matched.
 220  */
 221 struct xbc_node * __init
 222 xbc_node_find_subkey(struct xbc_node *parent, const char *key)
 223 {
 224         struct xbc_node *node;
 225
 226         if (parent)
 227                 node = xbc_node_get_subkey(parent);
 228         else
 229                 node = xbc_root_node();
 230
 231         while (node && xbc_node_is_key(node)) {
 232                 if (!xbc_node_match_prefix(node, &key))
 233                         node = xbc_node_get_next(node);
 234                 else if (*key != '\0')
 235                         node = xbc_node_get_subkey(node);
 236                 else
 237                         break;
 238         }
 239
 240         return node;
 241 }
 242
 243 /**
 244  * xbc_node_find_value() - Find a value node which matches given key
 245  * @parent: An XBC node.
 246  * @key: A key string.
 247  * @vnode: A container pointer of found XBC node.
 248  *
 249  * Search a value node under @parent whose (parent) key node matches @key,
 250  * store it in *@vnode, and returns the value string.
 251  * The @key can contain several words jointed with '.'. If @parent is NULL,
 252  * this searches the node from whole tree. Return the value string if a
 253  * matched key found, return NULL if no node is matched.
 254  * Note that this returns 0-length string and stores NULL in *@vnode if the
 255  * key has no value. And also it will return the value of the first entry if
 256  * the value is an array.
 257  */
 258 const char * __init
 259 xbc_node_find_value(struct xbc_node *parent, const char *key,
 260                     struct xbc_node **vnode)
 261 {
 262         struct xbc_node *node = xbc_node_find_subkey(parent, key);
 263
 264         if (!node || !xbc_node_is_key(node))
 265                 return NULL;
 266
 267         node = xbc_node_get_child(node);
 268         if (node && !xbc_node_is_value(node))
 269                 return NULL;
 270
 271         if (vnode)
 272                 *vnode = node;
 273
 274         return node ? xbc_node_get_data(node) : "";
 275 }
 276
 277 /**
 278  * xbc_node_compose_key_after() - Compose partial key string of the XBC node
 279  * @root: Root XBC node
 280  * @node: Target XBC node.
 281  * @buf: A buffer to store the key.
 282  * @size: The size of the @buf.
 283  *
 284  * Compose the partial key of the @node into @buf, which is starting right
 285  * after @root (@root is not included.) If @root is NULL, this returns full
 286  * key words of @node.
 287  * Returns the total length of the key stored in @buf. Returns -EINVAL
 288  * if @node is NULL or @root is not the ancestor of @node or @root is @node,
 289  * or returns -ERANGE if the key depth is deeper than max depth.
 290  * This is expected to be used with xbc_find_node() to list up all (child)
 291  * keys under given key.
 292  */
 293 int __init xbc_node_compose_key_after(struct xbc_node *root,
 294                                       struct xbc_node *node,
 295                                       char *buf, size_t size)
 296 {
 297         uint16_t keys[XBC_DEPTH_MAX];
 298         int depth = 0, ret = 0, total = 0;
 299
 300         if (!node || node == root)
 301                 return -EINVAL;
 302
 303         if (xbc_node_is_value(node))
 304                 node = xbc_node_get_parent(node);
 305
 306         while (node && node != root) {
 307                 keys[depth++] = xbc_node_index(node);
 308                 if (depth == XBC_DEPTH_MAX)
 309                         return -ERANGE;
 310                 node = xbc_node_get_parent(node);
 311         }
 312         if (!node && root)
 313                 return -EINVAL;
 314
 315         while (--depth >= 0) {
 316                 node = xbc_nodes + keys[depth];
 317                 ret = snprintf(buf, size, "%s%s", xbc_node_get_data(node),
 318                                depth ? "." : "");
 319                 if (ret < 0)
 320                         return ret;
 321                 if (ret > size) {
 322                         size = 0;
 323                 } else {
 324                         size -= ret;
 325                         buf += ret;
 326                 }
 327                 total += ret;
 328         }
 329
 330         return total;
 331 }
 332
 333 /**
 334  * xbc_node_find_next_leaf() - Find the next leaf node under given node
 335  * @root: An XBC root node
 336  * @node: An XBC node which starts from.
 337  *
 338  * Search the next leaf node (which means the terminal key node) of @node
 339  * under @root node (including @root node itself).
 340  * Return the next node or NULL if next leaf node is not found.
 341  */
 342 struct xbc_node * __init xbc_node_find_next_leaf(struct xbc_node *root,
 343                                                  struct xbc_node *node)
 344 {
 345         struct xbc_node *next;
 346
 347         if (unlikely(!xbc_data))
 348                 return NULL;
 349
 350         if (!node) {    /* First try */
 351                 node = root;
 352                 if (!node)
 353                         node = xbc_nodes;
 354         } else {
 355                 /* Leaf node may have a subkey */
 356                 next = xbc_node_get_subkey(node);
 357                 if (next) {
 358                         node = next;
 359                         goto found;
 360                 }
 361
 362                 if (node == root)       /* @root was a leaf, no child node. */
 363                         return NULL;
 364
 365                 while (!node->next) {
 366                         node = xbc_node_get_parent(node);
 367                         if (node == root)
 368                                 return NULL;
 369                         /* User passed a node which is not uder parent */
 370                         if (WARN_ON(!node))
 371                                 return NULL;
 372                 }
 373                 node = xbc_node_get_next(node);
 374         }
 375
 376 found:
 377         while (node && !xbc_node_is_leaf(node))
 378                 node = xbc_node_get_child(node);
 379
 380         return node;
 381 }
 382
 383 /**
 384  * xbc_node_find_next_key_value() - Find the next key-value pair nodes
 385  * @root: An XBC root node
 386  * @leaf: A container pointer of XBC node which starts from.
 387  *
 388  * Search the next leaf node (which means the terminal key node) of *@leaf
 389  * under @root node. Returns the value and update *@leaf if next leaf node
 390  * is found, or NULL if no next leaf node is found.
 391  * Note that this returns 0-length string if the key has no value, or
 392  * the value of the first entry if the value is an array.
 393  */
 394 const char * __init xbc_node_find_next_key_value(struct xbc_node *root,
 395                                                  struct xbc_node **leaf)
 396 {
 397         /* tip must be passed */
 398         if (WARN_ON(!leaf))
 399                 return NULL;
 400
 401         *leaf = xbc_node_find_next_leaf(root, *leaf);
 402         if (!*leaf)
 403                 return NULL;
 404         if ((*leaf)->child)
 405                 return xbc_node_get_data(xbc_node_get_child(*leaf));
 406         else
 407                 return "";      /* No value key */
 408 }
 409
 410 /* XBC parse and tree build */
 411
 412 static int __init xbc_init_node(struct xbc_node *node, char *data, uint32_t flag)
 413 {
 414         unsigned long offset = data - xbc_data;
 415
 416         if (WARN_ON(offset >= XBC_DATA_MAX))
 417                 return -EINVAL;
 418
 419         node->data = (uint16_t)offset | flag;
 420         node->child = 0;
 421         node->next = 0;
 422
 423         return 0;
 424 }
 425
 426 static struct xbc_node * __init xbc_add_node(char *data, uint32_t flag)
 427 {
 428         struct xbc_node *node;
 429
 430         if (xbc_node_num == XBC_NODE_MAX)
 431                 return NULL;
 432
 433         node = &xbc_nodes[xbc_node_num++];
 434         if (xbc_init_node(node, data, flag) < 0)
 435                 return NULL;
 436
 437         return node;
 438 }
 439
 440 static inline __init struct xbc_node *xbc_last_sibling(struct xbc_node *node)
 441 {
 442         while (node->next)
 443                 node = xbc_node_get_next(node);
 444
 445         return node;
 446 }
 447
 448 static inline __init struct xbc_node *xbc_last_child(struct xbc_node *node)
 449 {
 450         while (node->child)
 451                 node = xbc_node_get_child(node);
 452
 453         return node;
 454 }
 455
 456 static struct xbc_node * __init __xbc_add_sibling(char *data, uint32_t flag, bool head)
 457 {
 458         struct xbc_node *sib, *node = xbc_add_node(data, flag);
 459
 460         if (node) {
 461                 if (!last_parent) {
 462                         /* Ignore @head in this case */
 463                         node->parent = XBC_NODE_MAX;
 464                         sib = xbc_last_sibling(xbc_nodes);
 465                         sib->next = xbc_node_index(node);
 466                 } else {
 467                         node->parent = xbc_node_index(last_parent);
 468                         if (!last_parent->child || head) {
 469                                 node->next = last_parent->child;
 470                                 last_parent->child = xbc_node_index(node);
 471                         } else {
 472                                 sib = xbc_node_get_child(last_parent);
 473                                 sib = xbc_last_sibling(sib);
 474                                 sib->next = xbc_node_index(node);
 475                         }
 476                 }
 477         } else
 478                 xbc_parse_error("Too many nodes", data);
 479
 480         return node;
 481 }
 482
 483 static inline struct xbc_node * __init xbc_add_sibling(char *data, uint32_t flag)
 484 {
 485         return __xbc_add_sibling(data, flag, false);
 486 }
 487
 488 static inline struct xbc_node * __init xbc_add_head_sibling(char *data, uint32_t flag)
 489 {
 490         return __xbc_add_sibling(data, flag, true);
 491 }
 492
 493 static inline __init struct xbc_node *xbc_add_child(char *data, uint32_t flag)
 494 {
 495         struct xbc_node *node = xbc_add_sibling(data, flag);
 496
 497         if (node)
 498                 last_parent = node;
 499
 500         return node;
 501 }
 502
 503 static inline __init bool xbc_valid_keyword(char *key)
 504 {
 505         if (key[0] == '\0')
 506                 return false;
 507
 508         while (isalnum(*key) || *key == '-' || *key == '_')
 509                 key++;
 510
 511         return *key == '\0';
 512 }
 513
 514 static char *skip_comment(char *p)
 515 {
 516         char *ret;
 517
 518         ret = strchr(p, '\n');
 519         if (!ret)
 520                 ret = p + strlen(p);
 521         else
 522                 ret++;
 523
 524         return ret;
 525 }
 526
 527 static char *skip_spaces_until_newline(char *p)
 528 {
 529         while (isspace(*p) && *p != '\n')
 530                 p++;
 531         return p;
 532 }
 533
 534 static int __init __xbc_open_brace(char *p)
 535 {
 536         /* Push the last key as open brace */
 537         open_brace[brace_index++] = xbc_node_index(last_parent);
 538         if (brace_index >= XBC_DEPTH_MAX)
 539                 return xbc_parse_error("Exceed max depth of braces", p);
 540
 541         return 0;
 542 }
 543
 544 static int __init __xbc_close_brace(char *p)
 545 {
 546         brace_index--;
 547         if (!last_parent || brace_index < 0 ||
 548             (open_brace[brace_index] != xbc_node_index(last_parent)))
 549                 return xbc_parse_error("Unexpected closing brace", p);
 550
 551         if (brace_index == 0)
 552                 last_parent = NULL;
 553         else
 554                 last_parent = &xbc_nodes[open_brace[brace_index - 1]];
 555
 556         return 0;
 557 }
 558
 559 /*
 560  * Return delimiter or error, no node added. As same as lib/cmdline.c,
 561  * you can use " around spaces, but can't escape " for value.
 562  */
 563 static int __init __xbc_parse_value(char **__v, char **__n)
 564 {
 565         char *p, *v = *__v;
 566         int c, quotes = 0;
 567
 568         v = skip_spaces(v);
 569         while (*v == '#') {
 570                 v = skip_comment(v);
 571                 v = skip_spaces(v);
 572         }
 573         if (*v == '"' || *v == '\'') {
 574                 quotes = *v;
 575                 v++;
 576         }
 577         p = v - 1;
 578         while ((c = *++p)) {
 579                 if (!isprint(c) && !isspace(c))
 580                         return xbc_parse_error("Non printable value", p);
 581                 if (quotes) {
 582                         if (c != quotes)
 583                                 continue;
 584                         quotes = 0;
 585                         *p++ = '\0';
 586                         p = skip_spaces_until_newline(p);
 587                         c = *p;
 588                         if (c && !strchr(",;\n#}", c))
 589                                 return xbc_parse_error("No value delimiter", p);
 590                         if (*p)
 591                                 p++;
 592                         break;
 593                 }
 594                 if (strchr(",;\n#}", c)) {
 595                         *p++ = '\0';
 596                         v = strim(v);
 597                         break;
 598                 }
 599         }
 600         if (quotes)
 601                 return xbc_parse_error("No closing quotes", p);
 602         if (c == '#') {
 603                 p = skip_comment(p);
 604                 c = '\n';       /* A comment must be treated as a newline */
 605         }
 606         *__n = p;
 607         *__v = v;
 608
 609         return c;
 610 }
 611
 612 static int __init xbc_parse_array(char **__v)
 613 {
 614         struct xbc_node *node;
 615         char *next;
 616         int c = 0;
 617
 618         if (last_parent->child)
 619                 last_parent = xbc_node_get_child(last_parent);
 620
 621         do {
 622                 c = __xbc_parse_value(__v, &next);
 623                 if (c < 0)
 624                         return c;
 625
 626                 node = xbc_add_child(*__v, XBC_VALUE);
 627                 if (!node)
 628                         return -ENOMEM;
 629                 *__v = next;
 630         } while (c == ',');
 631         node->child = 0;
 632
 633         return c;
 634 }
 635
 636 static inline __init
 637 struct xbc_node *find_match_node(struct xbc_node *node, char *k)
 638 {
 639         while (node) {
 640                 if (!strcmp(xbc_node_get_data(node), k))
 641                         break;
 642                 node = xbc_node_get_next(node);
 643         }
 644         return node;
 645 }
 646
 647 static int __init __xbc_add_key(char *k)
 648 {
 649         struct xbc_node *node, *child;
 650
 651         if (!xbc_valid_keyword(k))
 652                 return xbc_parse_error("Invalid keyword", k);
 653
 654         if (unlikely(xbc_node_num == 0))
 655                 goto add_node;
 656
 657         if (!last_parent)       /* the first level */
 658                 node = find_match_node(xbc_nodes, k);
 659         else {
 660                 child = xbc_node_get_child(last_parent);
 661                 /* Since the value node is the first child, skip it. */
 662                 if (child && xbc_node_is_value(child))
 663                         child = xbc_node_get_next(child);
 664                 node = find_match_node(child, k);
 665         }
 666
 667         if (node)
 668                 last_parent = node;
 669         else {
 670 add_node:
 671                 node = xbc_add_child(k, XBC_KEY);
 672                 if (!node)
 673                         return -ENOMEM;
 674         }
 675         return 0;
 676 }
 677
 678 static int __init __xbc_parse_keys(char *k)
 679 {
 680         char *p;
 681         int ret;
 682
 683         k = strim(k);
 684         while ((p = strchr(k, '.'))) {
 685                 *p++ = '\0';
 686                 ret = __xbc_add_key(k);
 687                 if (ret)
 688                         return ret;
 689                 k = p;
 690         }
 691
 692         return __xbc_add_key(k);
 693 }
 694
 695 static int __init xbc_parse_kv(char **k, char *v, int op)
 696 {
 697         struct xbc_node *prev_parent = last_parent;
 698         struct xbc_node *child;
 699         char *next;
 700         int c, ret;
 701
 702         ret = __xbc_parse_keys(*k);
 703         if (ret)
 704                 return ret;
 705
 706         c = __xbc_parse_value(&v, &next);
 707         if (c < 0)
 708                 return c;
 709
 710         child = xbc_node_get_child(last_parent);
 711         if (child && xbc_node_is_value(child)) {
 712                 if (op == '=')
 713                         return xbc_parse_error("Value is redefined", v);
 714                 if (op == ':') {
 715                         unsigned short nidx = child->next;
 716
 717                         xbc_init_node(child, v, XBC_VALUE);
 718                         child->next = nidx;     /* keep subkeys */
 719                         goto array;
 720                 }
 721                 /* op must be '+' */
 722                 last_parent = xbc_last_child(child);
 723         }
 724         /* The value node should always be the first child */
 725         if (!xbc_add_head_sibling(v, XBC_VALUE))
 726                 return -ENOMEM;
 727
 728 array:
 729         if (c == ',') { /* Array */
 730                 c = xbc_parse_array(&next);
 731                 if (c < 0)
 732                         return c;
 733         }
 734
 735         last_parent = prev_parent;
 736
 737         if (c == '}') {
 738                 ret = __xbc_close_brace(next - 1);
 739                 if (ret < 0)
 740                         return ret;
 741         }
 742
 743         *k = next;
 744
 745         return 0;
 746 }
 747
 748 static int __init xbc_parse_key(char **k, char *n)
 749 {
 750         struct xbc_node *prev_parent = last_parent;
 751         int ret;
 752
 753         *k = strim(*k);
 754         if (**k != '\0') {
 755                 ret = __xbc_parse_keys(*k);
 756                 if (ret)
 757                         return ret;
 758                 last_parent = prev_parent;
 759         }
 760         *k = n;
 761
 762         return 0;
 763 }
 764
 765 static int __init xbc_open_brace(char **k, char *n)
 766 {
 767         int ret;
 768
 769         ret = __xbc_parse_keys(*k);
 770         if (ret)
 771                 return ret;
 772         *k = n;
 773
 774         return __xbc_open_brace(n - 1);
 775 }
 776
 777 static int __init xbc_close_brace(char **k, char *n)
 778 {
 779         int ret;
 780
 781         ret = xbc_parse_key(k, n);
 782         if (ret)
 783                 return ret;
 784         /* k is updated in xbc_parse_key() */
 785
 786         return __xbc_close_brace(n - 1);
 787 }
 788
 789 static int __init xbc_verify_tree(void)
 790 {
 791         int i, depth, len, wlen;
 792         struct xbc_node *n, *m;
 793
 794         /* Brace closing */
 795         if (brace_index) {
 796                 n = &xbc_nodes[open_brace[brace_index]];
 797                 return xbc_parse_error("Brace is not closed",
 798                                         xbc_node_get_data(n));
 799         }
 800
 801         /* Empty tree */
 802         if (xbc_node_num == 0) {
 803                 xbc_parse_error("Empty config", xbc_data);
 804                 return -ENOENT;
 805         }
 806
 807         for (i = 0; i < xbc_node_num; i++) {
 808                 if (xbc_nodes[i].next > xbc_node_num) {
 809                         return xbc_parse_error("No closing brace",
 810                                 xbc_node_get_data(xbc_nodes + i));
 811                 }
 812         }
 813
 814         /* Key tree limitation check */
 815         n = &xbc_nodes[0];
 816         depth = 1;
 817         len = 0;
 818
 819         while (n) {
 820                 wlen = strlen(xbc_node_get_data(n)) + 1;
 821                 len += wlen;
 822                 if (len > XBC_KEYLEN_MAX)
 823                         return xbc_parse_error("Too long key length",
 824                                 xbc_node_get_data(n));
 825
 826                 m = xbc_node_get_child(n);
 827                 if (m && xbc_node_is_key(m)) {
 828                         n = m;
 829                         depth++;
 830                         if (depth > XBC_DEPTH_MAX)
 831                                 return xbc_parse_error("Too many key words",
 832                                                 xbc_node_get_data(n));
 833                         continue;
 834                 }
 835                 len -= wlen;
 836                 m = xbc_node_get_next(n);
 837                 while (!m) {
 838                         n = xbc_node_get_parent(n);
 839                         if (!n)
 840                                 break;
 841                         len -= strlen(xbc_node_get_data(n)) + 1;
 842                         depth--;
 843                         m = xbc_node_get_next(n);
 844                 }
 845                 n = m;
 846         }
 847
 848         return 0;
 849 }
 850
 851 /* Need to setup xbc_data and xbc_nodes before call this. */
 852 static int __init xbc_parse_tree(void)
 853 {
 854         char *p, *q;
 855         int ret = 0, c;
 856
 857         last_parent = NULL;
 858         p = xbc_data;
 859         do {
 860                 q = strpbrk(p, "{}=+;:\n#");
 861                 if (!q) {
 862                         p = skip_spaces(p);
 863                         if (*p != '\0')
 864                                 ret = xbc_parse_error("No delimiter", p);
 865                         break;
 866                 }
 867
 868                 c = *q;
 869                 *q++ = '\0';
 870                 switch (c) {
 871                 case ':':
 872                 case '+':
 873                         if (*q++ != '=') {
 874                                 ret = xbc_parse_error(c == '+' ?
 875                                                 "Wrong '+' operator" :
 876                                                 "Wrong ':' operator",
 877                                                         q - 2);
 878                                 break;
 879                         }
 880                         fallthrough;
 881                 case '=':
 882                         ret = xbc_parse_kv(&p, q, c);
 883                         break;
 884                 case '{':
 885                         ret = xbc_open_brace(&p, q);
 886                         break;
 887                 case '#':
 888                         q = skip_comment(q);
 889                         fallthrough;
 890                 case ';':
 891                 case '\n':
 892                         ret = xbc_parse_key(&p, q);
 893                         break;
 894                 case '}':
 895                         ret = xbc_close_brace(&p, q);
 896                         break;
 897                 }
 898         } while (!ret);
 899
 900         return ret;
 901 }
 902
 903 /**
 904  * _xbc_exit() - Clean up all parsed bootconfig
 905  * @early: Set true if this is called before budy system is initialized.
 906  *
 907  * This clears all data structures of parsed bootconfig on memory.
 908  * If you need to reuse xbc_init() with new boot config, you can
 909  * use this.
 910  */
 911 void __init _xbc_exit(bool early)
 912 {
 913         xbc_free_mem(xbc_data, xbc_data_size, early);
 914         xbc_data = NULL;
 915         xbc_data_size = 0;
 916         xbc_node_num = 0;
 917         xbc_free_mem(xbc_nodes, sizeof(struct xbc_node) * XBC_NODE_MAX, early);
 918         xbc_nodes = NULL;
 919         brace_index = 0;
 920 }
 921
 922 /**
 923  * xbc_init() - Parse given XBC file and build XBC internal tree
 924  * @data: The boot config text original data
 925  * @size: The size of @data
 926  * @emsg: A pointer of const char * to store the error message
 927  * @epos: A pointer of int to store the error position
 928  *
 929  * This parses the boot config text in @data. @size must be smaller
 930  * than XBC_DATA_MAX.
 931  * Return the number of stored nodes (>0) if succeeded, or -errno
 932  * if there is any error.
 933  * In error cases, @emsg will be updated with an error message and
 934  * @epos will be updated with the error position which is the byte offset
 935  * of @buf. If the error is not a parser error, @epos will be -1.
 936  */
 937 int __init xbc_init(const char *data, size_t size, const char **emsg, int *epos)
 938 {
 939         int ret;
 940
 941         if (epos)
 942                 *epos = -1;
 943
 944         if (xbc_data) {
 945                 if (emsg)
 946                         *emsg = "Bootconfig is already initialized";
 947                 return -EBUSY;
 948         }
 949         if (size > XBC_DATA_MAX || size == 0) {
 950                 if (emsg)
 951                         *emsg = size ? "Config data is too big" :
 952                                 "Config data is empty";
 953                 return -ERANGE;
 954         }
 955
 956         xbc_data = xbc_alloc_mem(size + 1);
 957         if (!xbc_data) {
 958                 if (emsg)
 959                         *emsg = "Failed to allocate bootconfig data";
 960                 return -ENOMEM;
 961         }
 962         memcpy(xbc_data, data, size);
 963         xbc_data[size] = '\0';
 964         xbc_data_size = size + 1;
 965
 966         xbc_nodes = xbc_alloc_mem(sizeof(struct xbc_node) * XBC_NODE_MAX);
 967         if (!xbc_nodes) {
 968                 if (emsg)
 969                         *emsg = "Failed to allocate bootconfig nodes";
 970                 _xbc_exit(true);
 971                 return -ENOMEM;
 972         }
 973         memset(xbc_nodes, 0, sizeof(struct xbc_node) * XBC_NODE_MAX);
 974
 975         ret = xbc_parse_tree();
 976         if (!ret)
 977                 ret = xbc_verify_tree();
 978
 979         if (ret < 0) {
 980                 if (epos)
 981                         *epos = xbc_err_pos;
 982                 if (emsg)
 983                         *emsg = xbc_err_msg;
 984                 _xbc_exit(true);
 985         } else
 986                 ret = xbc_node_num;
 987
 988         return ret;
 989 }