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  * read_znode - read an indexing node from flash and fill znode.
255  * @c: UBIFS file-system description object
263  * %-EINVAL.
268 	int lnum = zzbr->lnum;  in read_znode()
269 	int offs = zzbr->offs;  in read_znode()
270 	int len = zzbr->len;  in read_znode()  local
274 	idx = kmalloc(c->max_idx_node_sz, GFP_NOFS);  in read_znode()
276 		return -ENOMEM;  in read_znode()
278 	err = ubifs_read_node(c, idx, UBIFS_IDX_NODE, len, lnum, offs);  in read_znode()
284 	err = ubifs_node_check_hash(c, idx, zzbr->hash);  in read_znode()
286 		ubifs_bad_hash(c, idx, zzbr->hash, lnum, offs);  in read_znode()
291 	znode->child_cnt = le16_to_cpu(idx->child_cnt);  in read_znode()
292 	znode->level = le16_to_cpu(idx->level);  in read_znode()
295 		lnum, offs, znode->level, znode->child_cnt);  in read_znode()
297 	if (znode->child_cnt > c->fanout || znode->level > UBIFS_MAX_LEVELS) {  in read_znode()
299 			  c->fanout, znode->child_cnt);  in read_znode()
301 			  UBIFS_MAX_LEVELS, znode->level);  in read_znode()
306 	for (i = 0; i < znode->child_cnt; i++) {  in read_znode()
308 		struct ubifs_zbranch *zbr = &znode->zbranch[i];  in read_znode()
310 		key_read(c, &br->key, &zbr->key);  in read_znode()
311 		zbr->lnum = le32_to_cpu(br->lnum);  in read_znode()
312 		zbr->offs = le32_to_cpu(br->offs);  in read_znode()
313 		zbr->len  = le32_to_cpu(br->len);  in read_znode()
314 		ubifs_copy_hash(c, ubifs_branch_hash(c, br), zbr->hash);  in read_znode()
315 		zbr->znode = NULL;  in read_znode()
319 		if (zbr->lnum < c->main_first ||  in read_znode()
320 		    zbr->lnum >= c->leb_cnt || zbr->offs < 0 ||  in read_znode()
321 		    zbr->offs + zbr->len > c->leb_size || zbr->offs & 7) {  in read_znode()
327 		switch (key_type(c, &zbr->key)) {  in read_znode()
335 				  i, key_type(c, &zbr->key));  in read_znode()
340 		if (znode->level)  in read_znode()
343 		type = key_type(c, &zbr->key);  in read_znode()
344 		if (c->ranges[type].max_len == 0) {  in read_znode()
345 			if (zbr->len != c->ranges[type].len) {  in read_znode()
347 					  type, zbr->len);  in read_znode()
348 				ubifs_err(c, "have to be %d", c->ranges[type].len);  in read_znode()
352 		} else if (zbr->len < c->ranges[type].min_len ||  in read_znode()
353 			   zbr->len > c->ranges[type].max_len) {  in read_znode()
355 				  type, zbr->len);  in read_znode()
356 			ubifs_err(c, "have to be in range of %d-%d",  in read_znode()
357 				  c->ranges[type].min_len,  in read_znode()
358 				  c->ranges[type].max_len);  in read_znode()
368 	for (i = 0; i < znode->child_cnt - 1; i++) {  in read_znode()
371 		key1 = &znode->zbranch[i].key;  in read_znode()
372 		key2 = &znode->zbranch[i + 1].key;  in read_znode()
393 	ubifs_dump_node(c, idx, c->max_idx_node_sz);  in read_znode()
395 	return -EINVAL;  in read_znode()
399  * ubifs_load_znode - load znode to TNC cache.
400  * @c: UBIFS file-system description object
416 	ubifs_assert(c, !zbr->znode);  in ubifs_load_znode()
421 	znode = kzalloc(c->max_znode_sz, GFP_NOFS);  in ubifs_load_znode()
423 		return ERR_PTR(-ENOMEM);  in ubifs_load_znode()
429 	atomic_long_inc(&c->clean_zn_cnt);  in ubifs_load_znode()
433 	 * global and per-FS clean znode counters may be inconsistent for some  in ubifs_load_znode()
439 	zbr->znode = znode;  in ubifs_load_znode()
440 	znode->parent = parent;  in ubifs_load_znode()
441 	znode->time = ktime_get_seconds();  in ubifs_load_znode()
442 	znode->iip = iip;  in ubifs_load_znode()
452  * ubifs_tnc_read_node - read a leaf node from the flash media.
453  * @c: UBIFS file-system description object
463 	union ubifs_key key1, *key = &zbr->key;  in ubifs_tnc_read_node()
468 	 * 'zbr' has to point to on-flash node. The node may sit in a bud and  in ubifs_tnc_read_node()
471 	wbuf = ubifs_get_wbuf(c, zbr->lnum);  in ubifs_tnc_read_node()
473 		err = ubifs_read_node_wbuf(wbuf, node, type, zbr->len,  in ubifs_tnc_read_node()
474 					   zbr->lnum, zbr->offs);  in ubifs_tnc_read_node()
476 		err = ubifs_read_node(c, node, type, zbr->len, zbr->lnum,  in ubifs_tnc_read_node()
477 				      zbr->offs);  in ubifs_tnc_read_node()
488 			  zbr->lnum, zbr->offs);  in ubifs_tnc_read_node()
491 		ubifs_dump_node(c, node, zbr->len);  in ubifs_tnc_read_node()
492 		return -EINVAL;  in ubifs_tnc_read_node()
495 	err = ubifs_node_check_hash(c, node, zbr->hash);  in ubifs_tnc_read_node()
497 		ubifs_bad_hash(c, node, zbr->hash, zbr->lnum, zbr->offs);  in ubifs_tnc_read_node()