lib/bootconfig.c

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