1 // SPDX-License-Identifier: GPL-2.0-only
5  * Copyright (C) 2006-2008 Nokia Corporation.
12  * This file contains miscelanious TNC-related functions shared betweend
14  * sub-system. The file was created because there is a lot of TNC code and
21  * ubifs_tnc_levelorder_next - next TNC tree element in levelorder traversal.
22  * @c: UBIFS file-system description object
42 		if (znode->level == 0)  in ubifs_tnc_levelorder_next()
47 	level = znode->level;  in ubifs_tnc_levelorder_next()
49 	iip = znode->iip;  in ubifs_tnc_levelorder_next()
51 		ubifs_assert(c, znode->level <= zr->level);  in ubifs_tnc_levelorder_next()
57 		while (znode->parent != zr && iip >= znode->parent->child_cnt) {  in ubifs_tnc_levelorder_next()
58 			znode = znode->parent;  in ubifs_tnc_levelorder_next()
59 			iip = znode->iip;  in ubifs_tnc_levelorder_next()
62 		if (unlikely(znode->parent == zr &&  in ubifs_tnc_levelorder_next()
63 			     iip >= znode->parent->child_cnt)) {  in ubifs_tnc_levelorder_next()
65 			level -= 1;  in ubifs_tnc_levelorder_next()
76 			iip = -1;  in ubifs_tnc_levelorder_next()
82 		zn = ubifs_tnc_find_child(znode->parent, iip + 1);  in ubifs_tnc_levelorder_next()
85 			iip = znode->parent->child_cnt;  in ubifs_tnc_levelorder_next()
90 		while (zn->level != level) {  in ubifs_tnc_levelorder_next()
98 				iip = znode->iip;  in ubifs_tnc_levelorder_next()
104 			ubifs_assert(c, zn->level >= 0);  in ubifs_tnc_levelorder_next()
111  * ubifs_search_zbranch - search znode branch.
112  * @c: UBIFS file-system description object
119  *   o exact match, then %1 is returned, and the slot number of the branch is
121  *   o no exact match, then %0 is returned and the slot number of the left
123  *     greater than @key, then %-1 is returned in @n.
129 	int beg = 0, end = znode->child_cnt, mid;  in ubifs_search_zbranch()
131 	const struct ubifs_zbranch *zbr = &znode->zbranch[0];  in ubifs_search_zbranch()
148 	*n = end - 1;  in ubifs_search_zbranch()
151 	ubifs_assert(c, *n >= -1 && *n < znode->child_cnt);  in ubifs_search_zbranch()
152 	if (*n == -1)  in ubifs_search_zbranch()
156 	if (*n + 1 < znode->child_cnt)  in ubifs_search_zbranch()
163  * ubifs_tnc_postorder_first - find first znode to do postorder tree traversal.
164  * @znode: znode to start at (root of the sub-tree to traverse)
174 	while (znode->level > 0) {  in ubifs_tnc_postorder_first()
187  * ubifs_tnc_postorder_next - next TNC tree element in postorder traversal.
188  * @c: UBIFS file-system description object
200 	if (unlikely(!znode->parent))  in ubifs_tnc_postorder_next()
204 	zn = ubifs_tnc_find_child(znode->parent, znode->iip + 1);  in ubifs_tnc_postorder_next()
207 		return znode->parent;  in ubifs_tnc_postorder_next()
214  * ubifs_destroy_tnc_subtree - destroy all znodes connected to a subtree.
215  * @c: UBIFS file-system description object
230 		for (n = 0; n < zn->child_cnt; n++) {  in ubifs_destroy_tnc_subtree()
231 			if (!zn->zbranch[n].znode)  in ubifs_destroy_tnc_subtree()
234 			if (zn->level > 0 &&  in ubifs_destroy_tnc_subtree()
235 			    !ubifs_zn_dirty(zn->zbranch[n].znode))  in ubifs_destroy_tnc_subtree()
239 			kfree(zn->zbranch[n].znode);  in ubifs_destroy_tnc_subtree()
254  * ubifs_destroy_tnc_tree - destroy all znodes connected to the TNC tree.
255  * @c: UBIFS file-system description object
264 	if (!c->zroot.znode)  in ubifs_destroy_tnc_tree()
267 	n = atomic_long_read(&c->clean_zn_cnt);  in ubifs_destroy_tnc_tree()
268 	freed = ubifs_destroy_tnc_subtree(c, c->zroot.znode);  in ubifs_destroy_tnc_tree()
272 	c->zroot.znode = NULL;  in ubifs_destroy_tnc_tree()
276  * read_znode - read an indexing node from flash and fill znode.
277  * @c: UBIFS file-system description object
285  * %-EINVAL.
290 	int lnum = zzbr->lnum;  in read_znode()
291 	int offs = zzbr->offs;  in read_znode()
292 	int len = zzbr->len;  in read_znode()  local
296 	idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);  in read_znode()
298 		return -ENOMEM;  in read_znode()
300 	err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);  in read_znode()
306 	err = ubifs_node_check_hash(c, idx, zzbr->hash);  in read_znode()
308 		ubifs_bad_hash(c, idx, zzbr->hash, lnum, offs);  in read_znode()
313 	znode->child_cnt = le16_to_cpu(idx->child_cnt);  in read_znode()
314 	znode->level = le16_to_cpu(idx->level);  in read_znode()
317 		lnum, offs, znode->level, znode->child_cnt);  in read_znode()
319 	if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) {  in read_znode()
321 			  c->fanout, znode->child_cnt);  in read_znode()
323 			  UBIFS_MAX_LEVELS, znode->level);  in read_znode()
328 	for (i = 0; i < znode->child_cnt; i++) {  in read_znode()
330 		struct ubifs_zbranch *zbr = &znode->zbranch[i];  in read_znode()
332 		key_read(c, &br->key, &zbr->key);  in read_znode()
333 		zbr->lnum = le32_to_cpu(br->lnum);  in read_znode()
334 		zbr->offs = le32_to_cpu(br->offs);  in read_znode()
335 		zbr->len  = le32_to_cpu(br->len);  in read_znode()
336 		ubifs_copy_hash(c, ubifs_branch_hash(c, br), zbr->hash);  in read_znode()
337 		zbr->znode = NULL;  in read_znode()
341 		if (zbr->lnum < c->main_first ||  in read_znode()
342 		    zbr->lnum >= c->leb_cnt || zbr->offs < 0 ||  in read_znode()
343 		    zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) {  in read_znode()
349 		switch (key_type(c, &zbr->key)) {  in read_znode()
357 				  i, key_type(c, &zbr->key));  in read_znode()
362 		if (znode->level)  in read_znode()
365 		type = key_type(c, &zbr->key);  in read_znode()
366 		if (c->ranges[type].max_len == 0) {  in read_znode()
367 			if (zbr->len != c->ranges[type].len) {  in read_znode()
369 					  type, zbr->len);  in read_znode()
370 				ubifs_err(c, "have to be %d", c->ranges[type].len);  in read_znode()
374 		} else if (zbr->len < c->ranges[type].min_len ||  in read_znode()
375 			   zbr->len > c->ranges[type].max_len) {  in read_znode()
377 				  type, zbr->len);  in read_znode()
378 			ubifs_err(c, "have to be in range of %d-%d",  in read_znode()
379 				  c->ranges[type].min_len,  in read_znode()
380 				  c->ranges[type].max_len);  in read_znode()
390 	for (i = 0; i < znode->child_cnt - 1; i++) {  in read_znode()
393 		key1 = &znode->zbranch[i].key;  in read_znode()
394 		key2 = &znode->zbranch[i + 1].key;  in read_znode()
415 	ubifs_dump_node(c, idx, c->max_idx_node_sz);  in read_znode()
417 	return -EINVAL;  in read_znode()
421  * ubifs_load_znode - load znode to TNC cache.
422  * @c: UBIFS file-system description object
438 	ubifs_assert(c, !zbr->znode);  in ubifs_load_znode()
443 	znode = kzalloc(c->max_znode_sz, GFP_NOFS);  in ubifs_load_znode()
445 		return ERR_PTR(-ENOMEM);  in ubifs_load_znode()
451 	atomic_long_inc(&c->clean_zn_cnt);  in ubifs_load_znode()
455 	 * global and per-FS clean znode counters may be inconsistent for some  in ubifs_load_znode()
461 	zbr->znode = znode;  in ubifs_load_znode()
462 	znode->parent = parent;  in ubifs_load_znode()
463 	znode->time = ktime_get_seconds();  in ubifs_load_znode()
464 	znode->iip = iip;  in ubifs_load_znode()
474  * ubifs_tnc_read_node - read a leaf node from the flash media.
475  * @c: UBIFS file-system description object
485 	union ubifs_key key1, *key = &zbr->key;  in ubifs_tnc_read_node()
490 	 * 'zbr' has to point to on-flash node. The node may sit in a bud and  in ubifs_tnc_read_node()
493 	wbuf = ubifs_get_wbuf(c, zbr->lnum);  in ubifs_tnc_read_node()
495 		err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len,  in ubifs_tnc_read_node()
496 					   zbr->lnum, zbr->offs);  in ubifs_tnc_read_node()
498 		err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum,  in ubifs_tnc_read_node()
499 				      zbr->offs);  in ubifs_tnc_read_node()
510 			  zbr->lnum, zbr->offs);  in ubifs_tnc_read_node()
513 		ubifs_dump_node(c, node, zbr->len);  in ubifs_tnc_read_node()
514 		return -EINVAL;  in ubifs_tnc_read_node()
517 	err = ubifs_node_check_hash(c, node, zbr->hash);  in ubifs_tnc_read_node()
519 		ubifs_bad_hash(c, node, zbr->hash, zbr->lnum, zbr->offs);  in ubifs_tnc_read_node()