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 
xbc_get_embedded_bootconfig(size_t * size)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__
xbc_alloc_mem(size_t size)59 static inline void * __init xbc_alloc_mem(size_t size)
60 {
61 	return memblock_alloc(size, SMP_CACHE_BYTES);
62 }
63 
xbc_free_mem(void * addr,size_t size)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 
xbc_alloc_mem(size_t size)71 static inline void *xbc_alloc_mem(size_t size)
72 {
73 	return malloc(size);
74 }
75 
xbc_free_mem(void * addr,size_t size)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  */
xbc_get_info(int * node_size,size_t * data_size)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 
xbc_parse_error(const char * msg,const char * p)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  */
xbc_root_node(void)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  */
xbc_node_index(struct xbc_node * node)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  */
xbc_node_get_parent(struct xbc_node * node)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  */
xbc_node_get_child(struct xbc_node * node)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  */
xbc_node_get_next(struct xbc_node * node)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  */
xbc_node_get_data(struct xbc_node * node)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
xbc_node_match_prefix(struct xbc_node * node,const char ** prefix)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
xbc_node_find_subkey(struct xbc_node * parent,const char * key)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
xbc_node_find_value(struct xbc_node * parent,const char * key,struct xbc_node ** vnode)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  */
xbc_node_compose_key_after(struct xbc_node * root,struct xbc_node * node,char * buf,size_t size)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  */
xbc_node_find_next_leaf(struct xbc_node * root,struct xbc_node * node)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  */
xbc_node_find_next_key_value(struct xbc_node * root,struct xbc_node ** leaf)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 
xbc_init_node(struct xbc_node * node,char * data,uint32_t flag)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 
xbc_add_node(char * data,uint32_t flag)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 
xbc_last_sibling(struct xbc_node * node)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 
xbc_last_child(struct xbc_node * node)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 
__xbc_add_sibling(char * data,uint32_t flag,bool head)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 
xbc_add_sibling(char * data,uint32_t flag)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 
xbc_add_head_sibling(char * data,uint32_t flag)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 
xbc_add_child(char * data,uint32_t flag)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 
xbc_valid_keyword(char * key)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 
skip_comment(char * p)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 
skip_spaces_until_newline(char * p)524 static char *skip_spaces_until_newline(char *p)
525 {
526 	while (isspace(*p) && *p != '\n')
527 		p++;
528 	return p;
529 }
530 
__xbc_open_brace(char * p)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 
__xbc_close_brace(char * p)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  */
__xbc_parse_value(char ** __v,char ** __n)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 
xbc_parse_array(char ** __v)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
find_match_node(struct xbc_node * node,char * k)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 
__xbc_add_key(char * k)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 
__xbc_parse_keys(char * k)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 
xbc_parse_kv(char ** k,char * v,int op)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 
xbc_parse_key(char ** k,char * n)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 
xbc_open_brace(char ** k,char * n)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 
xbc_close_brace(char ** k,char * n)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 
xbc_verify_tree(void)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. */
xbc_parse_tree(void)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  */
xbc_exit(void)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  */
xbc_init(const char * data,size_t size,const char ** emsg,int * epos)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 }
986