77 static int insert_old_idx(struct ubifs_info *c, int lnum, int offs)  in insert_old_idx()  argument
88 	p = &c->old_idx.rb_node;  in insert_old_idx()
101 			ubifs_err(c, "old idx added twice!");  in insert_old_idx()
107 	rb_insert_color(&old_idx->rb, &c->old_idx);  in insert_old_idx()
118 int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode)  in insert_old_idx_znode()  argument
125 			return insert_old_idx(c, zbr->lnum, zbr->offs);  in insert_old_idx_znode()
127 		if (c->zroot.len)  in insert_old_idx_znode()
128 			return insert_old_idx(c, c->zroot.lnum,  in insert_old_idx_znode()
129 					      c->zroot.offs);  in insert_old_idx_znode()
140 static int ins_clr_old_idx_znode(struct ubifs_info *c,  in ins_clr_old_idx_znode()  argument
150 			err = insert_old_idx(c, zbr->lnum, zbr->offs);  in ins_clr_old_idx_znode()
158 		if (c->zroot.len) {  in ins_clr_old_idx_znode()
159 			err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs);  in ins_clr_old_idx_znode()
162 			c->zroot.lnum = 0;  in ins_clr_old_idx_znode()
163 			c->zroot.offs = 0;  in ins_clr_old_idx_znode()
164 			c->zroot.len = 0;  in ins_clr_old_idx_znode()
179 void destroy_old_idx(struct ubifs_info *c)  in destroy_old_idx()  argument
183 	rbtree_postorder_for_each_entry_safe(old_idx, n, &c->old_idx, rb)  in destroy_old_idx()
186 	c->old_idx = RB_ROOT;  in destroy_old_idx()
196 static struct ubifs_znode *copy_znode(struct ubifs_info *c,  in copy_znode()  argument
201 	zn = kmalloc(c->max_znode_sz, GFP_NOFS);  in copy_znode()
205 	memcpy(zn, znode, c->max_znode_sz);  in copy_znode()
226 	atomic_long_inc(&c->dirty_zn_cnt);  in copy_znode()
238 static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt)  in add_idx_dirt()  argument
240 	c->calc_idx_sz -= ALIGN(dirt, 8);  in add_idx_dirt()
241 	return ubifs_add_dirt(c, lnum, dirt);  in add_idx_dirt()
251 static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c,  in dirty_cow_znode()  argument
261 			atomic_long_inc(&c->dirty_zn_cnt);  in dirty_cow_znode()
262 			atomic_long_dec(&c->clean_zn_cnt);  in dirty_cow_znode()
264 			err = add_idx_dirt(c, zbr->lnum, zbr->len);  in dirty_cow_znode()
271 	zn = copy_znode(c, znode);  in dirty_cow_znode()
276 		err = insert_old_idx(c, zbr->lnum, zbr->offs);  in dirty_cow_znode()
279 		err = add_idx_dirt(c, zbr->lnum, zbr->len);  in dirty_cow_znode()
313 static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr,  in lnc_add()  argument
322 	ubifs_assert(is_hash_key(c, &zbr->key));  in lnc_add()
324 	err = ubifs_validate_entry(c, dent);  in lnc_add()
327 		ubifs_dump_node(c, dent);  in lnc_add()
349 static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr,  in lnc_add_directly()  argument
357 	err = ubifs_validate_entry(c, node);  in lnc_add_directly()
360 		ubifs_dump_node(c, node);  in lnc_add_directly()
392 static int tnc_read_node_nm(struct ubifs_info *c, struct ubifs_zbranch *zbr,  in tnc_read_node_nm()  argument
397 	ubifs_assert(is_hash_key(c, &zbr->key));  in tnc_read_node_nm()
406 	err = ubifs_tnc_read_node(c, zbr, node);  in tnc_read_node_nm()
411 	err = lnc_add(c, zbr, node);  in tnc_read_node_nm()
439 static int try_read_node(const struct ubifs_info *c, void *buf, int type,  in try_read_node()  argument
448 	err = ubifs_leb_read(c, lnum, buf, offs, len, 1);  in try_read_node()
450 		ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d",  in try_read_node()
465 	if (type == UBIFS_DATA_NODE && c->no_chk_data_crc && !c->mounting &&  in try_read_node()
466 	    !c->remounting_rw)  in try_read_node()
487 static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,  in fallible_read_node()  argument
494 	ret = try_read_node(c, node, key_type(c, key), zbr->len, zbr->lnum,  in fallible_read_node()
501 		key_read(c, &dent->key, &node_key);  in fallible_read_node()
502 		if (keys_cmp(c, key, &node_key) != 0)  in fallible_read_node()
505 	if (ret == 0 && c->replaying)  in fallible_read_node()
522 static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr,  in matches_name()  argument
534 		err = ubifs_tnc_read_node(c, zbr, dent);  in matches_name()
539 		err = lnc_add_directly(c, zbr, dent);  in matches_name()
572 static struct ubifs_znode *get_znode(struct ubifs_info *c,  in get_znode()  argument
581 		znode = ubifs_load_znode(c, zbr, znode, n);  in get_znode()
594 static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n)  in tnc_next()  argument
613 			znode = get_znode(c, znode, nn);  in tnc_next()
617 				znode = get_znode(c, znode, 0);  in tnc_next()
639 static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n)  in tnc_prev()  argument
657 			znode = get_znode(c, znode, nn);  in tnc_prev()
662 				znode = get_znode(c, znode, nn);  in tnc_prev()
691 static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key,  in resolve_collision()  argument
697 	err = matches_name(c, &(*zn)->zbranch[*n], nm);  in resolve_collision()
706 			err = tnc_prev(c, zn, n);  in resolve_collision()
714 			if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {  in resolve_collision()
745 					err = tnc_next(c, zn, n);  in resolve_collision()
758 			err = matches_name(c, &(*zn)->zbranch[*n], nm);  in resolve_collision()
773 			err = tnc_next(c, &znode, &nn);  in resolve_collision()
778 			if (keys_cmp(c, &znode->zbranch[nn].key, key))  in resolve_collision()
780 			err = matches_name(c, &znode->zbranch[nn], nm);  in resolve_collision()
809 static int fallible_matches_name(struct ubifs_info *c,  in fallible_matches_name()  argument
822 		err = fallible_read_node(c, &zbr->key, zbr, dent);  in fallible_matches_name()
832 		err = lnc_add_directly(c, zbr, dent);  in fallible_matches_name()
879 static int fallible_resolve_collision(struct ubifs_info *c,  in fallible_resolve_collision()  argument
887 	cmp = fallible_matches_name(c, &znode->zbranch[nn], nm);  in fallible_resolve_collision()
907 			err = tnc_prev(c, zn, n);  in fallible_resolve_collision()
915 			if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {  in fallible_resolve_collision()
918 					err = tnc_next(c, zn, n);  in fallible_resolve_collision()
931 			err = fallible_matches_name(c, &(*zn)->zbranch[*n], nm);  in fallible_resolve_collision()
955 			err = tnc_next(c, &znode, &nn);  in fallible_resolve_collision()
960 			if (keys_cmp(c, &znode->zbranch[nn].key, key))  in fallible_resolve_collision()
962 			err = fallible_matches_name(c, &znode->zbranch[nn], nm);  in fallible_resolve_collision()
1023 static int resolve_collision_directly(struct ubifs_info *c,  in resolve_collision_directly()  argument
1038 		err = tnc_prev(c, &znode, &nn);  in resolve_collision_directly()
1043 		if (keys_cmp(c, &znode->zbranch[nn].key, key))  in resolve_collision_directly()
1056 		err = tnc_next(c, &znode, &nn);  in resolve_collision_directly()
1061 		if (keys_cmp(c, &znode->zbranch[nn].key, key))  in resolve_collision_directly()
1080 static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c,  in dirty_cow_bottom_up()  argument
1084 	int *path = c->bottom_up_buf, p = 0;  in dirty_cow_bottom_up()
1086 	ubifs_assert(c->zroot.znode);  in dirty_cow_bottom_up()
1088 	if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) {  in dirty_cow_bottom_up()
1089 		kfree(c->bottom_up_buf);  in dirty_cow_bottom_up()
1090 		c->bottom_up_buf = kmalloc(c->zroot.znode->level * sizeof(int),  in dirty_cow_bottom_up()
1092 		if (!c->bottom_up_buf)  in dirty_cow_bottom_up()
1094 		path = c->bottom_up_buf;  in dirty_cow_bottom_up()
1096 	if (c->zroot.znode->level) {  in dirty_cow_bottom_up()
1105 			ubifs_assert(p < c->zroot.znode->level);  in dirty_cow_bottom_up()
1122 			znode = dirty_cow_znode(c, zbr);  in dirty_cow_bottom_up()
1124 			ubifs_assert(znode == c->zroot.znode);  in dirty_cow_bottom_up()
1125 			znode = dirty_cow_znode(c, &c->zroot);  in dirty_cow_bottom_up()
1159 int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key,  in ubifs_lookup_level0()  argument
1167 	ubifs_assert(key_type(c, key) < UBIFS_INVALID_KEY);  in ubifs_lookup_level0()
1169 	znode = c->zroot.znode;  in ubifs_lookup_level0()
1171 		znode = ubifs_load_znode(c, &c->zroot, NULL, 0);  in ubifs_lookup_level0()
1181 		exact = ubifs_search_zbranch(c, znode, key, n);  in ubifs_lookup_level0()
1197 		znode = ubifs_load_znode(c, zbr, znode, *n);  in ubifs_lookup_level0()
1203 	if (exact || !is_hash_key(c, key) || *n != -1) {  in ubifs_lookup_level0()
1251 	err = tnc_prev(c, &znode, n);  in ubifs_lookup_level0()
1259 	if (keys_cmp(c, key, &znode->zbranch[*n].key)) {  in ubifs_lookup_level0()
1295 static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key,  in lookup_level0_dirty()  argument
1304 	znode = c->zroot.znode;  in lookup_level0_dirty()
1306 		znode = ubifs_load_znode(c, &c->zroot, NULL, 0);  in lookup_level0_dirty()
1311 	znode = dirty_cow_znode(c, &c->zroot);  in lookup_level0_dirty()
1320 		exact = ubifs_search_zbranch(c, znode, key, n);  in lookup_level0_dirty()
1331 			znode = dirty_cow_znode(c, zbr);  in lookup_level0_dirty()
1338 		znode = ubifs_load_znode(c, zbr, znode, *n);  in lookup_level0_dirty()
1341 		znode = dirty_cow_znode(c, zbr);  in lookup_level0_dirty()
1347 	if (exact || !is_hash_key(c, key) || *n != -1) {  in lookup_level0_dirty()
1356 	err = tnc_prev(c, &znode, n);  in lookup_level0_dirty()
1364 	if (keys_cmp(c, key, &znode->zbranch[*n].key)) {  in lookup_level0_dirty()
1371 		znode = dirty_cow_bottom_up(c, znode);  in lookup_level0_dirty()
1391 static int maybe_leb_gced(struct ubifs_info *c, int lnum, int gc_seq1)  in maybe_leb_gced()  argument
1395 	gced_lnum = c->gced_lnum;  in maybe_leb_gced()
1397 	gc_seq2 = c->gc_seq;  in maybe_leb_gced()
1409 	if (gced_lnum != c->gced_lnum)  in maybe_leb_gced()
1430 int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key,  in ubifs_tnc_locate()  argument
1438 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_locate()
1439 	found = ubifs_lookup_level0(c, key, &znode, &n);  in ubifs_tnc_locate()
1452 	if (is_hash_key(c, key)) {  in ubifs_tnc_locate()
1457 		err = tnc_read_node_nm(c, zt, node);  in ubifs_tnc_locate()
1461 		err = ubifs_tnc_read_node(c, zt, node);  in ubifs_tnc_locate()
1466 	gc_seq1 = c->gc_seq;  in ubifs_tnc_locate()
1467 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_locate()
1469 	if (ubifs_get_wbuf(c, zbr.lnum)) {  in ubifs_tnc_locate()
1471 		err = ubifs_tnc_read_node(c, &zbr, node);  in ubifs_tnc_locate()
1475 	err = fallible_read_node(c, key, &zbr, node);  in ubifs_tnc_locate()
1476 	if (err <= 0 || maybe_leb_gced(c, zbr.lnum, gc_seq1)) {  in ubifs_tnc_locate()
1487 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_locate()
1504 int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu)  in ubifs_tnc_get_bu_keys()  argument
1508 	unsigned int block = key_block(c, &bu->key);  in ubifs_tnc_get_bu_keys()
1515 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_get_bu_keys()
1517 	err = ubifs_lookup_level0(c, &bu->key, &znode, &n);  in ubifs_tnc_get_bu_keys()
1540 		err = tnc_next(c, &znode, &n);  in ubifs_tnc_get_bu_keys()
1546 		if (key_inum(c, key) != key_inum(c, &bu->key) ||  in ubifs_tnc_get_bu_keys()
1547 		    key_type(c, key) != UBIFS_DATA_KEY) {  in ubifs_tnc_get_bu_keys()
1574 		next_block = key_block(c, key);  in ubifs_tnc_get_bu_keys()
1593 	bu->gc_seq = c->gc_seq;  in ubifs_tnc_get_bu_keys()
1594 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_get_bu_keys()
1616 	block = key_block(c, &bu->key) + bu->blk_cnt;  in ubifs_tnc_get_bu_keys()
1619 		if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block)  in ubifs_tnc_get_bu_keys()
1639 	const struct ubifs_info *c = wbuf->c;  in read_wbuf()  local
1643 	ubifs_assert(wbuf && lnum >= 0 && lnum < c->leb_cnt && offs >= 0);  in read_wbuf()
1644 	ubifs_assert(!(offs & 7) && offs < c->leb_size);  in read_wbuf()
1645 	ubifs_assert(offs + len <= c->leb_size);  in read_wbuf()
1652 		return ubifs_leb_read(c, lnum, buf, offs, len, 0);  in read_wbuf()
1666 		return ubifs_leb_read(c, lnum, buf, offs, rlen, 0);  in read_wbuf()
1679 static int validate_data_node(struct ubifs_info *c, void *buf,  in validate_data_node()  argument
1687 		ubifs_err(c, "bad node type (%d but expected %d)",  in validate_data_node()
1692 	err = ubifs_check_node(c, buf, zbr->lnum, zbr->offs, 0, 0);  in validate_data_node()
1694 		ubifs_err(c, "expected node type %d", UBIFS_DATA_NODE);  in validate_data_node()
1700 		ubifs_err(c, "bad node length %d, expected %d", len, zbr->len);  in validate_data_node()
1705 	key_read(c, buf + UBIFS_KEY_OFFSET, &key1);  in validate_data_node()
1706 	if (!keys_eq(c, &zbr->key, &key1)) {  in validate_data_node()
1707 		ubifs_err(c, "bad key in node at LEB %d:%d",  in validate_data_node()
1719 	ubifs_err(c, "bad node at LEB %d:%d", zbr->lnum, zbr->offs);  in validate_data_node()
1720 	ubifs_dump_node(c, buf);  in validate_data_node()
1735 int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu)  in ubifs_tnc_bulk_read()  argument
1744 		ubifs_err(c, "buffer too small %d vs %d", bu->buf_len, len);  in ubifs_tnc_bulk_read()
1749 	wbuf = ubifs_get_wbuf(c, lnum);  in ubifs_tnc_bulk_read()
1753 		err = ubifs_leb_read(c, lnum, bu->buf, offs, len, 0);  in ubifs_tnc_bulk_read()
1756 	if (maybe_leb_gced(c, lnum, bu->gc_seq))  in ubifs_tnc_bulk_read()
1760 		ubifs_err(c, "failed to read from LEB %d:%d, error %d",  in ubifs_tnc_bulk_read()
1770 		err = validate_data_node(c, buf, &bu->zbranch[i]);  in ubifs_tnc_bulk_read()
1792 static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,  in do_lookup_nm()  argument
1799 	mutex_lock(&c->tnc_mutex);  in do_lookup_nm()
1800 	found = ubifs_lookup_level0(c, key, &znode, &n);  in do_lookup_nm()
1811 	err = resolve_collision(c, key, &znode, &n, nm);  in do_lookup_nm()
1820 	err = tnc_read_node_nm(c, &znode->zbranch[n], node);  in do_lookup_nm()
1823 	mutex_unlock(&c->tnc_mutex);  in do_lookup_nm()
1840 int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,  in ubifs_tnc_lookup_nm()  argument
1850 	err = ubifs_tnc_lookup(c, key, node);  in ubifs_tnc_lookup_nm()
1862 	return do_lookup_nm(c, key, node, nm);  in ubifs_tnc_lookup_nm()
1874 static void correct_parent_keys(const struct ubifs_info *c,  in correct_parent_keys()  argument
1885 	while (keys_cmp(c, key, key1) < 0) {  in correct_parent_keys()
1886 		key_copy(c, key, key1);  in correct_parent_keys()
1958 static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,  in tnc_insert()  argument
1965 	ubifs_assert(n >= 0 && n <= c->fanout);  in tnc_insert()
1970 	if (znode->child_cnt < c->fanout) {  in tnc_insert()
1971 		ubifs_assert(n != c->fanout);  in tnc_insert()
1978 			correct_parent_keys(c, znode);  in tnc_insert()
1994 		ins_clr_old_idx_znode(c, znode);  in tnc_insert()
1996 	zn = kzalloc(c->max_znode_sz, GFP_NOFS);  in tnc_insert()
2003 	if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {  in tnc_insert()
2005 		if (n == c->fanout) {  in tnc_insert()
2007 			if (key_inum(c, key1) == key_inum(c, key) &&  in tnc_insert()
2008 			    key_type(c, key1) == UBIFS_DATA_KEY)  in tnc_insert()
2012 	} else if (appending && n != c->fanout) {  in tnc_insert()
2016 		if (n >= (c->fanout + 1) / 2) {  in tnc_insert()
2018 			if (key_inum(c, key1) == key_inum(c, key) &&  in tnc_insert()
2019 			    key_type(c, key1) == UBIFS_DATA_KEY) {  in tnc_insert()
2021 				if (key_inum(c, key1) != key_inum(c, key) ||  in tnc_insert()
2022 				    key_type(c, key1) != UBIFS_DATA_KEY) {  in tnc_insert()
2024 					move = c->fanout - keep;  in tnc_insert()
2033 		keep = c->fanout;  in tnc_insert()
2036 		keep = (c->fanout + 1) / 2;  in tnc_insert()
2037 		move = c->fanout - keep;  in tnc_insert()
2062 	atomic_long_inc(&c->dirty_zn_cnt);  in tnc_insert()
2088 			correct_parent_keys(c, znode);  in tnc_insert()
2107 	zi = kzalloc(c->max_znode_sz, GFP_NOFS);  in tnc_insert()
2115 	atomic_long_inc(&c->dirty_zn_cnt);  in tnc_insert()
2119 	zi->zbranch[0].lnum = c->zroot.lnum;  in tnc_insert()
2120 	zi->zbranch[0].offs = c->zroot.offs;  in tnc_insert()
2121 	zi->zbranch[0].len = c->zroot.len;  in tnc_insert()
2125 	c->zroot.lnum = 0;  in tnc_insert()
2126 	c->zroot.offs = 0;  in tnc_insert()
2127 	c->zroot.len = 0;  in tnc_insert()
2128 	c->zroot.znode = zi;  in tnc_insert()
2150 int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,  in ubifs_tnc_add()  argument
2156 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_add()
2158 	found = lookup_level0_dirty(c, key, &znode, &n);  in ubifs_tnc_add()
2166 		key_copy(c, key, &zbr.key);  in ubifs_tnc_add()
2167 		err = tnc_insert(c, znode, &zbr, n + 1);  in ubifs_tnc_add()
2172 		err = ubifs_add_dirt(c, zbr->lnum, zbr->len);  in ubifs_tnc_add()
2179 		err = dbg_check_tnc(c, 0);  in ubifs_tnc_add()
2180 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_add()
2199 int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,  in ubifs_tnc_replace()  argument
2205 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_replace()
2208 	found = lookup_level0_dirty(c, key, &znode, &n);  in ubifs_tnc_replace()
2220 			err = ubifs_add_dirt(c, zbr->lnum, zbr->len);  in ubifs_tnc_replace()
2227 		} else if (is_hash_key(c, key)) {  in ubifs_tnc_replace()
2228 			found = resolve_collision_directly(c, key, &znode, &n,  in ubifs_tnc_replace()
2240 					znode = dirty_cow_bottom_up(c, znode);  in ubifs_tnc_replace()
2248 				err = ubifs_add_dirt(c, zbr->lnum,  in ubifs_tnc_replace()
2260 		err = ubifs_add_dirt(c, lnum, len);  in ubifs_tnc_replace()
2263 		err = dbg_check_tnc(c, 0);  in ubifs_tnc_replace()
2266 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_replace()
2282 int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,  in ubifs_tnc_add_nm()  argument
2288 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_add_nm()
2291 	found = lookup_level0_dirty(c, key, &znode, &n);  in ubifs_tnc_add_nm()
2298 		if (c->replaying)  in ubifs_tnc_add_nm()
2299 			found = fallible_resolve_collision(c, key, &znode, &n,  in ubifs_tnc_add_nm()
2302 			found = resolve_collision(c, key, &znode, &n, nm);  in ubifs_tnc_add_nm()
2311 			znode = dirty_cow_bottom_up(c, znode);  in ubifs_tnc_add_nm()
2322 			err = ubifs_add_dirt(c, zbr->lnum, zbr->len);  in ubifs_tnc_add_nm()
2337 		key_copy(c, key, &zbr.key);  in ubifs_tnc_add_nm()
2338 		err = tnc_insert(c, znode, &zbr, n + 1);  in ubifs_tnc_add_nm()
2341 		if (c->replaying) {  in ubifs_tnc_add_nm()
2350 			err = dbg_check_tnc(c, 0);  in ubifs_tnc_add_nm()
2351 			mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_add_nm()
2354 			return ubifs_tnc_remove_nm(c, key, &noname);  in ubifs_tnc_add_nm()
2360 		err = dbg_check_tnc(c, 0);  in ubifs_tnc_add_nm()
2361 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_add_nm()
2374 static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)  in tnc_delete()  argument
2382 	ubifs_assert(n >= 0 && n < c->fanout);  in tnc_delete()
2388 	err = ubifs_add_dirt(c, zbr->lnum, zbr->len);  in tnc_delete()
2390 		ubifs_dump_znode(c, znode);  in tnc_delete()
2414 		atomic_long_dec(&c->dirty_zn_cnt);  in tnc_delete()
2416 		err = insert_old_idx_znode(c, znode);  in tnc_delete()
2422 			atomic_long_inc(&c->clean_zn_cnt);  in tnc_delete()
2446 			znode = get_znode(c, znode, 0);  in tnc_delete()
2449 			znode = dirty_cow_znode(c, zbr);  in tnc_delete()
2454 			if (c->zroot.len) {  in tnc_delete()
2455 				err = insert_old_idx(c, c->zroot.lnum,  in tnc_delete()
2456 						     c->zroot.offs);  in tnc_delete()
2460 			c->zroot.lnum = zbr->lnum;  in tnc_delete()
2461 			c->zroot.offs = zbr->offs;  in tnc_delete()
2462 			c->zroot.len = zbr->len;  in tnc_delete()
2463 			c->zroot.znode = znode;  in tnc_delete()
2466 			atomic_long_dec(&c->dirty_zn_cnt);  in tnc_delete()
2470 				atomic_long_inc(&c->clean_zn_cnt);  in tnc_delete()
2487 int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)  in ubifs_tnc_remove()  argument
2492 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_remove()
2494 	found = lookup_level0_dirty(c, key, &znode, &n);  in ubifs_tnc_remove()
2500 		err = tnc_delete(c, znode, n);  in ubifs_tnc_remove()
2502 		err = dbg_check_tnc(c, 0);  in ubifs_tnc_remove()
2505 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_remove()
2517 int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,  in ubifs_tnc_remove_nm()  argument
2523 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_remove_nm()
2525 	err = lookup_level0_dirty(c, key, &znode, &n);  in ubifs_tnc_remove_nm()
2530 		if (c->replaying)  in ubifs_tnc_remove_nm()
2531 			err = fallible_resolve_collision(c, key, &znode, &n,  in ubifs_tnc_remove_nm()
2534 			err = resolve_collision(c, key, &znode, &n, nm);  in ubifs_tnc_remove_nm()
2541 				znode = dirty_cow_bottom_up(c, znode);  in ubifs_tnc_remove_nm()
2547 			err = tnc_delete(c, znode, n);  in ubifs_tnc_remove_nm()
2553 		err = dbg_check_tnc(c, 0);  in ubifs_tnc_remove_nm()
2554 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_remove_nm()
2567 static int key_in_range(struct ubifs_info *c, union ubifs_key *key,  in key_in_range()  argument
2570 	if (keys_cmp(c, key, from_key) < 0)  in key_in_range()
2572 	if (keys_cmp(c, key, to_key) > 0)  in key_in_range()
2587 int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key,  in ubifs_tnc_remove_range()  argument
2594 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_remove_range()
2597 		err = ubifs_lookup_level0(c, from_key, &znode, &n);  in ubifs_tnc_remove_range()
2604 			err = tnc_next(c, &znode, &n);  in ubifs_tnc_remove_range()
2612 			if (!key_in_range(c, key, from_key, to_key)) {  in ubifs_tnc_remove_range()
2620 			znode = dirty_cow_bottom_up(c, znode);  in ubifs_tnc_remove_range()
2630 			if (!key_in_range(c, key, from_key, to_key))  in ubifs_tnc_remove_range()
2633 			err = ubifs_add_dirt(c, znode->zbranch[i].lnum,  in ubifs_tnc_remove_range()
2636 				ubifs_dump_znode(c, znode);  in ubifs_tnc_remove_range()
2648 		err = tnc_delete(c, znode, n);  in ubifs_tnc_remove_range()
2655 		err = dbg_check_tnc(c, 0);  in ubifs_tnc_remove_range()
2656 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_remove_range()
2669 int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum)  in ubifs_tnc_remove_ino()  argument
2681 	lowest_xent_key(c, &key1, inum);  in ubifs_tnc_remove_ino()
2686 		xent = ubifs_tnc_next_ent(c, &key1, &nm);  in ubifs_tnc_remove_ino()
2700 		err = ubifs_tnc_remove_nm(c, &key1, &nm);  in ubifs_tnc_remove_ino()
2706 		lowest_ino_key(c, &key1, xattr_inum);  in ubifs_tnc_remove_ino()
2707 		highest_ino_key(c, &key2, xattr_inum);  in ubifs_tnc_remove_ino()
2708 		err = ubifs_tnc_remove_range(c, &key1, &key2);  in ubifs_tnc_remove_ino()
2716 		key_read(c, &xent->key, &key1);  in ubifs_tnc_remove_ino()
2720 	lowest_ino_key(c, &key1, inum);  in ubifs_tnc_remove_ino()
2721 	highest_ino_key(c, &key2, inum);  in ubifs_tnc_remove_ino()
2723 	return ubifs_tnc_remove_range(c, &key1, &key2);  in ubifs_tnc_remove_ino()
2749 struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c,  in ubifs_tnc_next_ent()  argument
2753 	int n, err, type = key_type(c, key);  in ubifs_tnc_next_ent()
2760 	ubifs_assert(is_hash_key(c, key));  in ubifs_tnc_next_ent()
2762 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_next_ent()
2763 	err = ubifs_lookup_level0(c, key, &znode, &n);  in ubifs_tnc_next_ent()
2770 			err = resolve_collision(c, key, &znode, &n, nm);  in ubifs_tnc_next_ent()
2778 		err = tnc_next(c, &znode, &n);  in ubifs_tnc_next_ent()
2793 			err = tnc_next(c, &znode, &n);  in ubifs_tnc_next_ent()
2811 	if (key_inum(c, dkey) != key_inum(c, key) ||  in ubifs_tnc_next_ent()
2812 	    key_type(c, dkey) != type) {  in ubifs_tnc_next_ent()
2817 	err = tnc_read_node_nm(c, zbr, dent);  in ubifs_tnc_next_ent()
2821 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_next_ent()
2827 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_next_ent()
2837 static void tnc_destroy_cnext(struct ubifs_info *c)  in tnc_destroy_cnext()  argument
2841 	if (!c->cnext)  in tnc_destroy_cnext()
2843 	ubifs_assert(c->cmt_state == COMMIT_BROKEN);  in tnc_destroy_cnext()
2844 	cnext = c->cnext;  in tnc_destroy_cnext()
2851 	} while (cnext && cnext != c->cnext);  in tnc_destroy_cnext()
2858 void ubifs_tnc_close(struct ubifs_info *c)  in ubifs_tnc_close()  argument
2860 	tnc_destroy_cnext(c);  in ubifs_tnc_close()
2861 	if (c->zroot.znode) {  in ubifs_tnc_close()
2864 		n = atomic_long_read(&c->clean_zn_cnt);  in ubifs_tnc_close()
2865 		freed = ubifs_destroy_tnc_subtree(c->zroot.znode);  in ubifs_tnc_close()
2869 	kfree(c->gap_lebs);  in ubifs_tnc_close()
2870 	kfree(c->ilebs);  in ubifs_tnc_close()
2871 	destroy_old_idx(c);  in ubifs_tnc_close()
2882 static struct ubifs_znode *left_znode(struct ubifs_info *c,  in left_znode()  argument
2896 			znode = get_znode(c, znode, n);  in left_znode()
2901 				znode = get_znode(c, znode, n);  in left_znode()
2919 static struct ubifs_znode *right_znode(struct ubifs_info *c,  in right_znode()  argument
2933 			znode = get_znode(c, znode, n);  in right_znode()
2937 				znode = get_znode(c, znode, 0);  in right_znode()
2972 static struct ubifs_znode *lookup_znode(struct ubifs_info *c,  in lookup_znode()  argument
2979 	ubifs_assert(key_type(c, key) < UBIFS_INVALID_KEY);  in lookup_znode()
2989 	znode = c->zroot.znode;  in lookup_znode()
2991 		znode = ubifs_load_znode(c, &c->zroot, NULL, 0);  in lookup_znode()
2996 	if (c->zroot.lnum == lnum && c->zroot.offs == offs)  in lookup_znode()
3002 		ubifs_search_zbranch(c, znode, key, &n);  in lookup_znode()
3012 			znode = left_znode(c, znode);  in lookup_znode()
3017 			ubifs_search_zbranch(c, znode, key, &n);  in lookup_znode()
3022 		znode = get_znode(c, znode, n);  in lookup_znode()
3028 		return get_znode(c, znode, n);  in lookup_znode()
3030 	if (!is_hash_key(c, key))  in lookup_znode()
3044 			znode = left_znode(c, znode);  in lookup_znode()
3054 			return get_znode(c, znode, n);  in lookup_znode()
3056 		if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)  in lookup_znode()
3066 			znode = right_znode(c, znode);  in lookup_znode()
3076 			return get_znode(c, znode, n);  in lookup_znode()
3078 		if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)  in lookup_znode()
3101 int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,  in is_idx_node_in_tnc()  argument
3106 	znode = lookup_znode(c, key, level, lnum, offs);  in is_idx_node_in_tnc()
3128 static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,  in is_leaf_node_in_tnc()  argument
3134 	const int unique = !is_hash_key(c, key);  in is_leaf_node_in_tnc()
3136 	found = ubifs_lookup_level0(c, key, &znode, &n);  in is_leaf_node_in_tnc()
3154 		err = tnc_prev(c, &znode, &n);  in is_leaf_node_in_tnc()
3159 		if (keys_cmp(c, key, &znode->zbranch[n].key))  in is_leaf_node_in_tnc()
3169 		err = tnc_next(c, &znode, &n);  in is_leaf_node_in_tnc()
3175 		if (keys_cmp(c, key, &znode->zbranch[n].key))  in is_leaf_node_in_tnc()
3198 int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,  in ubifs_tnc_has_node()  argument
3203 	mutex_lock(&c->tnc_mutex);  in ubifs_tnc_has_node()
3205 		err = is_idx_node_in_tnc(c, key, level, lnum, offs);  in ubifs_tnc_has_node()
3217 		err = is_leaf_node_in_tnc(c, key, lnum, offs);  in ubifs_tnc_has_node()
3220 	mutex_unlock(&c->tnc_mutex);  in ubifs_tnc_has_node()
3238 int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,  in ubifs_dirty_idx_node()  argument
3244 	mutex_lock(&c->tnc_mutex);  in ubifs_dirty_idx_node()
3245 	znode = lookup_znode(c, key, level, lnum, offs);  in ubifs_dirty_idx_node()
3252 	znode = dirty_cow_bottom_up(c, znode);  in ubifs_dirty_idx_node()
3259 	mutex_unlock(&c->tnc_mutex);  in ubifs_dirty_idx_node()
3274 int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode,  in dbg_check_inode_size()  argument
3284 	if (!dbg_is_chk_gen(c))  in dbg_check_inode_size()
3288 	data_key_init(c, &from_key, inode->i_ino, block);  in dbg_check_inode_size()
3289 	highest_data_key(c, &to_key, inode->i_ino);  in dbg_check_inode_size()
3291 	mutex_lock(&c->tnc_mutex);  in dbg_check_inode_size()
3292 	err = ubifs_lookup_level0(c, &from_key, &znode, &n);  in dbg_check_inode_size()
3301 	err = tnc_next(c, &znode, &n);  in dbg_check_inode_size()
3311 	if (!key_in_range(c, key, &from_key, &to_key))  in dbg_check_inode_size()
3315 	block = key_block(c, key);  in dbg_check_inode_size()
3316 	ubifs_err(c, "inode %lu has size %lld, but there are data at offset %lld",  in dbg_check_inode_size()
3319 	mutex_unlock(&c->tnc_mutex);  in dbg_check_inode_size()
3320 	ubifs_dump_inode(c, inode);  in dbg_check_inode_size()
3325 	mutex_unlock(&c->tnc_mutex);  in dbg_check_inode_size()