lib/bootconfig.c

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