xref: /openbmc/linux/fs/ubifs/tnc.c (revision 4800cd83)
1 /*
2  * This file is part of UBIFS.
3  *
4  * Copyright (C) 2006-2008 Nokia Corporation.
5  *
6  * This program is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License version 2 as published by
8  * the Free Software Foundation.
9  *
10  * This program is distributed in the hope that it will be useful, but WITHOUT
11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
13  * more details.
14  *
15  * You should have received a copy of the GNU General Public License along with
16  * this program; if not, write to the Free Software Foundation, Inc., 51
17  * Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  *
19  * Authors: Adrian Hunter
20  *          Artem Bityutskiy (Битюцкий Артём)
21  */
22 
23 /*
24  * This file implements TNC (Tree Node Cache) which caches indexing nodes of
25  * the UBIFS B-tree.
26  *
27  * At the moment the locking rules of the TNC tree are quite simple and
28  * straightforward. We just have a mutex and lock it when we traverse the
29  * tree. If a znode is not in memory, we read it from flash while still having
30  * the mutex locked.
31  */
32 
33 #include <linux/crc32.h>
34 #include <linux/slab.h>
35 #include "ubifs.h"
36 
37 /*
38  * Returned codes of 'matches_name()' and 'fallible_matches_name()' functions.
39  * @NAME_LESS: name corresponding to the first argument is less than second
40  * @NAME_MATCHES: names match
41  * @NAME_GREATER: name corresponding to the second argument is greater than
42  *                first
43  * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media
44  *
45  * These constants were introduce to improve readability.
46  */
47 enum {
48 	NAME_LESS    = 0,
49 	NAME_MATCHES = 1,
50 	NAME_GREATER = 2,
51 	NOT_ON_MEDIA = 3,
52 };
53 
54 /**
55  * insert_old_idx - record an index node obsoleted since the last commit start.
56  * @c: UBIFS file-system description object
57  * @lnum: LEB number of obsoleted index node
58  * @offs: offset of obsoleted index node
59  *
60  * Returns %0 on success, and a negative error code on failure.
61  *
62  * For recovery, there must always be a complete intact version of the index on
63  * flash at all times. That is called the "old index". It is the index as at the
64  * time of the last successful commit. Many of the index nodes in the old index
65  * may be dirty, but they must not be erased until the next successful commit
66  * (at which point that index becomes the old index).
67  *
68  * That means that the garbage collection and the in-the-gaps method of
69  * committing must be able to determine if an index node is in the old index.
70  * Most of the old index nodes can be found by looking up the TNC using the
71  * 'lookup_znode()' function. However, some of the old index nodes may have
72  * been deleted from the current index or may have been changed so much that
73  * they cannot be easily found. In those cases, an entry is added to an RB-tree.
74  * That is what this function does. The RB-tree is ordered by LEB number and
75  * offset because they uniquely identify the old index node.
76  */
77 static int insert_old_idx(struct ubifs_info *c, int lnum, int offs)
78 {
79 	struct ubifs_old_idx *old_idx, *o;
80 	struct rb_node **p, *parent = NULL;
81 
82 	old_idx = kmalloc(sizeof(struct ubifs_old_idx), GFP_NOFS);
83 	if (unlikely(!old_idx))
84 		return -ENOMEM;
85 	old_idx->lnum = lnum;
86 	old_idx->offs = offs;
87 
88 	p = &c->old_idx.rb_node;
89 	while (*p) {
90 		parent = *p;
91 		o = rb_entry(parent, struct ubifs_old_idx, rb);
92 		if (lnum < o->lnum)
93 			p = &(*p)->rb_left;
94 		else if (lnum > o->lnum)
95 			p = &(*p)->rb_right;
96 		else if (offs < o->offs)
97 			p = &(*p)->rb_left;
98 		else if (offs > o->offs)
99 			p = &(*p)->rb_right;
100 		else {
101 			ubifs_err("old idx added twice!");
102 			kfree(old_idx);
103 			return 0;
104 		}
105 	}
106 	rb_link_node(&old_idx->rb, parent, p);
107 	rb_insert_color(&old_idx->rb, &c->old_idx);
108 	return 0;
109 }
110 
111 /**
112  * insert_old_idx_znode - record a znode obsoleted since last commit start.
113  * @c: UBIFS file-system description object
114  * @znode: znode of obsoleted index node
115  *
116  * Returns %0 on success, and a negative error code on failure.
117  */
118 int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode)
119 {
120 	if (znode->parent) {
121 		struct ubifs_zbranch *zbr;
122 
123 		zbr = &znode->parent->zbranch[znode->iip];
124 		if (zbr->len)
125 			return insert_old_idx(c, zbr->lnum, zbr->offs);
126 	} else
127 		if (c->zroot.len)
128 			return insert_old_idx(c, c->zroot.lnum,
129 					      c->zroot.offs);
130 	return 0;
131 }
132 
133 /**
134  * ins_clr_old_idx_znode - record a znode obsoleted since last commit start.
135  * @c: UBIFS file-system description object
136  * @znode: znode of obsoleted index node
137  *
138  * Returns %0 on success, and a negative error code on failure.
139  */
140 static int ins_clr_old_idx_znode(struct ubifs_info *c,
141 				 struct ubifs_znode *znode)
142 {
143 	int err;
144 
145 	if (znode->parent) {
146 		struct ubifs_zbranch *zbr;
147 
148 		zbr = &znode->parent->zbranch[znode->iip];
149 		if (zbr->len) {
150 			err = insert_old_idx(c, zbr->lnum, zbr->offs);
151 			if (err)
152 				return err;
153 			zbr->lnum = 0;
154 			zbr->offs = 0;
155 			zbr->len = 0;
156 		}
157 	} else
158 		if (c->zroot.len) {
159 			err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs);
160 			if (err)
161 				return err;
162 			c->zroot.lnum = 0;
163 			c->zroot.offs = 0;
164 			c->zroot.len = 0;
165 		}
166 	return 0;
167 }
168 
169 /**
170  * destroy_old_idx - destroy the old_idx RB-tree.
171  * @c: UBIFS file-system description object
172  *
173  * During start commit, the old_idx RB-tree is used to avoid overwriting index
174  * nodes that were in the index last commit but have since been deleted.  This
175  * is necessary for recovery i.e. the old index must be kept intact until the
176  * new index is successfully written.  The old-idx RB-tree is used for the
177  * in-the-gaps method of writing index nodes and is destroyed every commit.
178  */
179 void destroy_old_idx(struct ubifs_info *c)
180 {
181 	struct rb_node *this = c->old_idx.rb_node;
182 	struct ubifs_old_idx *old_idx;
183 
184 	while (this) {
185 		if (this->rb_left) {
186 			this = this->rb_left;
187 			continue;
188 		} else if (this->rb_right) {
189 			this = this->rb_right;
190 			continue;
191 		}
192 		old_idx = rb_entry(this, struct ubifs_old_idx, rb);
193 		this = rb_parent(this);
194 		if (this) {
195 			if (this->rb_left == &old_idx->rb)
196 				this->rb_left = NULL;
197 			else
198 				this->rb_right = NULL;
199 		}
200 		kfree(old_idx);
201 	}
202 	c->old_idx = RB_ROOT;
203 }
204 
205 /**
206  * copy_znode - copy a dirty znode.
207  * @c: UBIFS file-system description object
208  * @znode: znode to copy
209  *
210  * A dirty znode being committed may not be changed, so it is copied.
211  */
212 static struct ubifs_znode *copy_znode(struct ubifs_info *c,
213 				      struct ubifs_znode *znode)
214 {
215 	struct ubifs_znode *zn;
216 
217 	zn = kmalloc(c->max_znode_sz, GFP_NOFS);
218 	if (unlikely(!zn))
219 		return ERR_PTR(-ENOMEM);
220 
221 	memcpy(zn, znode, c->max_znode_sz);
222 	zn->cnext = NULL;
223 	__set_bit(DIRTY_ZNODE, &zn->flags);
224 	__clear_bit(COW_ZNODE, &zn->flags);
225 
226 	ubifs_assert(!test_bit(OBSOLETE_ZNODE, &znode->flags));
227 	__set_bit(OBSOLETE_ZNODE, &znode->flags);
228 
229 	if (znode->level != 0) {
230 		int i;
231 		const int n = zn->child_cnt;
232 
233 		/* The children now have new parent */
234 		for (i = 0; i < n; i++) {
235 			struct ubifs_zbranch *zbr = &zn->zbranch[i];
236 
237 			if (zbr->znode)
238 				zbr->znode->parent = zn;
239 		}
240 	}
241 
242 	atomic_long_inc(&c->dirty_zn_cnt);
243 	return zn;
244 }
245 
246 /**
247  * add_idx_dirt - add dirt due to a dirty znode.
248  * @c: UBIFS file-system description object
249  * @lnum: LEB number of index node
250  * @dirt: size of index node
251  *
252  * This function updates lprops dirty space and the new size of the index.
253  */
254 static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt)
255 {
256 	c->calc_idx_sz -= ALIGN(dirt, 8);
257 	return ubifs_add_dirt(c, lnum, dirt);
258 }
259 
260 /**
261  * dirty_cow_znode - ensure a znode is not being committed.
262  * @c: UBIFS file-system description object
263  * @zbr: branch of znode to check
264  *
265  * Returns dirtied znode on success or negative error code on failure.
266  */
267 static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c,
268 					   struct ubifs_zbranch *zbr)
269 {
270 	struct ubifs_znode *znode = zbr->znode;
271 	struct ubifs_znode *zn;
272 	int err;
273 
274 	if (!test_bit(COW_ZNODE, &znode->flags)) {
275 		/* znode is not being committed */
276 		if (!test_and_set_bit(DIRTY_ZNODE, &znode->flags)) {
277 			atomic_long_inc(&c->dirty_zn_cnt);
278 			atomic_long_dec(&c->clean_zn_cnt);
279 			atomic_long_dec(&ubifs_clean_zn_cnt);
280 			err = add_idx_dirt(c, zbr->lnum, zbr->len);
281 			if (unlikely(err))
282 				return ERR_PTR(err);
283 		}
284 		return znode;
285 	}
286 
287 	zn = copy_znode(c, znode);
288 	if (IS_ERR(zn))
289 		return zn;
290 
291 	if (zbr->len) {
292 		err = insert_old_idx(c, zbr->lnum, zbr->offs);
293 		if (unlikely(err))
294 			return ERR_PTR(err);
295 		err = add_idx_dirt(c, zbr->lnum, zbr->len);
296 	} else
297 		err = 0;
298 
299 	zbr->znode = zn;
300 	zbr->lnum = 0;
301 	zbr->offs = 0;
302 	zbr->len = 0;
303 
304 	if (unlikely(err))
305 		return ERR_PTR(err);
306 	return zn;
307 }
308 
309 /**
310  * lnc_add - add a leaf node to the leaf node cache.
311  * @c: UBIFS file-system description object
312  * @zbr: zbranch of leaf node
313  * @node: leaf node
314  *
315  * Leaf nodes are non-index nodes directory entry nodes or data nodes. The
316  * purpose of the leaf node cache is to save re-reading the same leaf node over
317  * and over again. Most things are cached by VFS, however the file system must
318  * cache directory entries for readdir and for resolving hash collisions. The
319  * present implementation of the leaf node cache is extremely simple, and
320  * allows for error returns that are not used but that may be needed if a more
321  * complex implementation is created.
322  *
323  * Note, this function does not add the @node object to LNC directly, but
324  * allocates a copy of the object and adds the copy to LNC. The reason for this
325  * is that @node has been allocated outside of the TNC subsystem and will be
326  * used with @c->tnc_mutex unlock upon return from the TNC subsystem. But LNC
327  * may be changed at any time, e.g. freed by the shrinker.
328  */
329 static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr,
330 		   const void *node)
331 {
332 	int err;
333 	void *lnc_node;
334 	const struct ubifs_dent_node *dent = node;
335 
336 	ubifs_assert(!zbr->leaf);
337 	ubifs_assert(zbr->len != 0);
338 	ubifs_assert(is_hash_key(c, &zbr->key));
339 
340 	err = ubifs_validate_entry(c, dent);
341 	if (err) {
342 		dbg_dump_stack();
343 		dbg_dump_node(c, dent);
344 		return err;
345 	}
346 
347 	lnc_node = kmalloc(zbr->len, GFP_NOFS);
348 	if (!lnc_node)
349 		/* We don't have to have the cache, so no error */
350 		return 0;
351 
352 	memcpy(lnc_node, node, zbr->len);
353 	zbr->leaf = lnc_node;
354 	return 0;
355 }
356 
357  /**
358  * lnc_add_directly - add a leaf node to the leaf-node-cache.
359  * @c: UBIFS file-system description object
360  * @zbr: zbranch of leaf node
361  * @node: leaf node
362  *
363  * This function is similar to 'lnc_add()', but it does not create a copy of
364  * @node but inserts @node to TNC directly.
365  */
366 static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr,
367 			    void *node)
368 {
369 	int err;
370 
371 	ubifs_assert(!zbr->leaf);
372 	ubifs_assert(zbr->len != 0);
373 
374 	err = ubifs_validate_entry(c, node);
375 	if (err) {
376 		dbg_dump_stack();
377 		dbg_dump_node(c, node);
378 		return err;
379 	}
380 
381 	zbr->leaf = node;
382 	return 0;
383 }
384 
385 /**
386  * lnc_free - remove a leaf node from the leaf node cache.
387  * @zbr: zbranch of leaf node
388  * @node: leaf node
389  */
390 static void lnc_free(struct ubifs_zbranch *zbr)
391 {
392 	if (!zbr->leaf)
393 		return;
394 	kfree(zbr->leaf);
395 	zbr->leaf = NULL;
396 }
397 
398 /**
399  * tnc_read_node_nm - read a "hashed" leaf node.
400  * @c: UBIFS file-system description object
401  * @zbr: key and position of the node
402  * @node: node is returned here
403  *
404  * This function reads a "hashed" node defined by @zbr from the leaf node cache
405  * (in it is there) or from the hash media, in which case the node is also
406  * added to LNC. Returns zero in case of success or a negative negative error
407  * code in case of failure.
408  */
409 static int tnc_read_node_nm(struct ubifs_info *c, struct ubifs_zbranch *zbr,
410 			    void *node)
411 {
412 	int err;
413 
414 	ubifs_assert(is_hash_key(c, &zbr->key));
415 
416 	if (zbr->leaf) {
417 		/* Read from the leaf node cache */
418 		ubifs_assert(zbr->len != 0);
419 		memcpy(node, zbr->leaf, zbr->len);
420 		return 0;
421 	}
422 
423 	err = ubifs_tnc_read_node(c, zbr, node);
424 	if (err)
425 		return err;
426 
427 	/* Add the node to the leaf node cache */
428 	err = lnc_add(c, zbr, node);
429 	return err;
430 }
431 
432 /**
433  * try_read_node - read a node if it is a node.
434  * @c: UBIFS file-system description object
435  * @buf: buffer to read to
436  * @type: node type
437  * @len: node length (not aligned)
438  * @lnum: LEB number of node to read
439  * @offs: offset of node to read
440  *
441  * This function tries to read a node of known type and length, checks it and
442  * stores it in @buf. This function returns %1 if a node is present and %0 if
443  * a node is not present. A negative error code is returned for I/O errors.
444  * This function performs that same function as ubifs_read_node except that
445  * it does not require that there is actually a node present and instead
446  * the return code indicates if a node was read.
447  *
448  * Note, this function does not check CRC of data nodes if @c->no_chk_data_crc
449  * is true (it is controlled by corresponding mount option). However, if
450  * @c->always_chk_crc is true, @c->no_chk_data_crc is ignored and CRC is always
451  * checked.
452  */
453 static int try_read_node(const struct ubifs_info *c, void *buf, int type,
454 			 int len, int lnum, int offs)
455 {
456 	int err, node_len;
457 	struct ubifs_ch *ch = buf;
458 	uint32_t crc, node_crc;
459 
460 	dbg_io("LEB %d:%d, %s, length %d", lnum, offs, dbg_ntype(type), len);
461 
462 	err = ubi_read(c->ubi, lnum, buf, offs, len);
463 	if (err) {
464 		ubifs_err("cannot read node type %d from LEB %d:%d, error %d",
465 			  type, lnum, offs, err);
466 		return err;
467 	}
468 
469 	if (le32_to_cpu(ch->magic) != UBIFS_NODE_MAGIC)
470 		return 0;
471 
472 	if (ch->node_type != type)
473 		return 0;
474 
475 	node_len = le32_to_cpu(ch->len);
476 	if (node_len != len)
477 		return 0;
478 
479 	if (type == UBIFS_DATA_NODE && !c->always_chk_crc && c->no_chk_data_crc)
480 		return 1;
481 
482 	crc = crc32(UBIFS_CRC32_INIT, buf + 8, node_len - 8);
483 	node_crc = le32_to_cpu(ch->crc);
484 	if (crc != node_crc)
485 		return 0;
486 
487 	return 1;
488 }
489 
490 /**
491  * fallible_read_node - try to read a leaf node.
492  * @c: UBIFS file-system description object
493  * @key:  key of node to read
494  * @zbr:  position of node
495  * @node: node returned
496  *
497  * This function tries to read a node and returns %1 if the node is read, %0
498  * if the node is not present, and a negative error code in the case of error.
499  */
500 static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
501 			      struct ubifs_zbranch *zbr, void *node)
502 {
503 	int ret;
504 
505 	dbg_tnc("LEB %d:%d, key %s", zbr->lnum, zbr->offs, DBGKEY(key));
506 
507 	ret = try_read_node(c, node, key_type(c, key), zbr->len, zbr->lnum,
508 			    zbr->offs);
509 	if (ret == 1) {
510 		union ubifs_key node_key;
511 		struct ubifs_dent_node *dent = node;
512 
513 		/* All nodes have key in the same place */
514 		key_read(c, &dent->key, &node_key);
515 		if (keys_cmp(c, key, &node_key) != 0)
516 			ret = 0;
517 	}
518 	if (ret == 0 && c->replaying)
519 		dbg_mnt("dangling branch LEB %d:%d len %d, key %s",
520 			zbr->lnum, zbr->offs, zbr->len, DBGKEY(key));
521 	return ret;
522 }
523 
524 /**
525  * matches_name - determine if a direntry or xattr entry matches a given name.
526  * @c: UBIFS file-system description object
527  * @zbr: zbranch of dent
528  * @nm: name to match
529  *
530  * This function checks if xentry/direntry referred by zbranch @zbr matches name
531  * @nm. Returns %NAME_MATCHES if it does, %NAME_LESS if the name referred by
532  * @zbr is less than @nm, and %NAME_GREATER if it is greater than @nm. In case
533  * of failure, a negative error code is returned.
534  */
535 static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr,
536 			const struct qstr *nm)
537 {
538 	struct ubifs_dent_node *dent;
539 	int nlen, err;
540 
541 	/* If possible, match against the dent in the leaf node cache */
542 	if (!zbr->leaf) {
543 		dent = kmalloc(zbr->len, GFP_NOFS);
544 		if (!dent)
545 			return -ENOMEM;
546 
547 		err = ubifs_tnc_read_node(c, zbr, dent);
548 		if (err)
549 			goto out_free;
550 
551 		/* Add the node to the leaf node cache */
552 		err = lnc_add_directly(c, zbr, dent);
553 		if (err)
554 			goto out_free;
555 	} else
556 		dent = zbr->leaf;
557 
558 	nlen = le16_to_cpu(dent->nlen);
559 	err = memcmp(dent->name, nm->name, min_t(int, nlen, nm->len));
560 	if (err == 0) {
561 		if (nlen == nm->len)
562 			return NAME_MATCHES;
563 		else if (nlen < nm->len)
564 			return NAME_LESS;
565 		else
566 			return NAME_GREATER;
567 	} else if (err < 0)
568 		return NAME_LESS;
569 	else
570 		return NAME_GREATER;
571 
572 out_free:
573 	kfree(dent);
574 	return err;
575 }
576 
577 /**
578  * get_znode - get a TNC znode that may not be loaded yet.
579  * @c: UBIFS file-system description object
580  * @znode: parent znode
581  * @n: znode branch slot number
582  *
583  * This function returns the znode or a negative error code.
584  */
585 static struct ubifs_znode *get_znode(struct ubifs_info *c,
586 				     struct ubifs_znode *znode, int n)
587 {
588 	struct ubifs_zbranch *zbr;
589 
590 	zbr = &znode->zbranch[n];
591 	if (zbr->znode)
592 		znode = zbr->znode;
593 	else
594 		znode = ubifs_load_znode(c, zbr, znode, n);
595 	return znode;
596 }
597 
598 /**
599  * tnc_next - find next TNC entry.
600  * @c: UBIFS file-system description object
601  * @zn: znode is passed and returned here
602  * @n: znode branch slot number is passed and returned here
603  *
604  * This function returns %0 if the next TNC entry is found, %-ENOENT if there is
605  * no next entry, or a negative error code otherwise.
606  */
607 static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n)
608 {
609 	struct ubifs_znode *znode = *zn;
610 	int nn = *n;
611 
612 	nn += 1;
613 	if (nn < znode->child_cnt) {
614 		*n = nn;
615 		return 0;
616 	}
617 	while (1) {
618 		struct ubifs_znode *zp;
619 
620 		zp = znode->parent;
621 		if (!zp)
622 			return -ENOENT;
623 		nn = znode->iip + 1;
624 		znode = zp;
625 		if (nn < znode->child_cnt) {
626 			znode = get_znode(c, znode, nn);
627 			if (IS_ERR(znode))
628 				return PTR_ERR(znode);
629 			while (znode->level != 0) {
630 				znode = get_znode(c, znode, 0);
631 				if (IS_ERR(znode))
632 					return PTR_ERR(znode);
633 			}
634 			nn = 0;
635 			break;
636 		}
637 	}
638 	*zn = znode;
639 	*n = nn;
640 	return 0;
641 }
642 
643 /**
644  * tnc_prev - find previous TNC entry.
645  * @c: UBIFS file-system description object
646  * @zn: znode is returned here
647  * @n: znode branch slot number is passed and returned here
648  *
649  * This function returns %0 if the previous TNC entry is found, %-ENOENT if
650  * there is no next entry, or a negative error code otherwise.
651  */
652 static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n)
653 {
654 	struct ubifs_znode *znode = *zn;
655 	int nn = *n;
656 
657 	if (nn > 0) {
658 		*n = nn - 1;
659 		return 0;
660 	}
661 	while (1) {
662 		struct ubifs_znode *zp;
663 
664 		zp = znode->parent;
665 		if (!zp)
666 			return -ENOENT;
667 		nn = znode->iip - 1;
668 		znode = zp;
669 		if (nn >= 0) {
670 			znode = get_znode(c, znode, nn);
671 			if (IS_ERR(znode))
672 				return PTR_ERR(znode);
673 			while (znode->level != 0) {
674 				nn = znode->child_cnt - 1;
675 				znode = get_znode(c, znode, nn);
676 				if (IS_ERR(znode))
677 					return PTR_ERR(znode);
678 			}
679 			nn = znode->child_cnt - 1;
680 			break;
681 		}
682 	}
683 	*zn = znode;
684 	*n = nn;
685 	return 0;
686 }
687 
688 /**
689  * resolve_collision - resolve a collision.
690  * @c: UBIFS file-system description object
691  * @key: key of a directory or extended attribute entry
692  * @zn: znode is returned here
693  * @n: zbranch number is passed and returned here
694  * @nm: name of the entry
695  *
696  * This function is called for "hashed" keys to make sure that the found key
697  * really corresponds to the looked up node (directory or extended attribute
698  * entry). It returns %1 and sets @zn and @n if the collision is resolved.
699  * %0 is returned if @nm is not found and @zn and @n are set to the previous
700  * entry, i.e. to the entry after which @nm could follow if it were in TNC.
701  * This means that @n may be set to %-1 if the leftmost key in @zn is the
702  * previous one. A negative error code is returned on failures.
703  */
704 static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key,
705 			     struct ubifs_znode **zn, int *n,
706 			     const struct qstr *nm)
707 {
708 	int err;
709 
710 	err = matches_name(c, &(*zn)->zbranch[*n], nm);
711 	if (unlikely(err < 0))
712 		return err;
713 	if (err == NAME_MATCHES)
714 		return 1;
715 
716 	if (err == NAME_GREATER) {
717 		/* Look left */
718 		while (1) {
719 			err = tnc_prev(c, zn, n);
720 			if (err == -ENOENT) {
721 				ubifs_assert(*n == 0);
722 				*n = -1;
723 				return 0;
724 			}
725 			if (err < 0)
726 				return err;
727 			if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
728 				/*
729 				 * We have found the branch after which we would
730 				 * like to insert, but inserting in this znode
731 				 * may still be wrong. Consider the following 3
732 				 * znodes, in the case where we are resolving a
733 				 * collision with Key2.
734 				 *
735 				 *                  znode zp
736 				 *            ----------------------
737 				 * level 1     |  Key0  |  Key1  |
738 				 *            -----------------------
739 				 *                 |            |
740 				 *       znode za  |            |  znode zb
741 				 *          ------------      ------------
742 				 * level 0  |  Key0  |        |  Key2  |
743 				 *          ------------      ------------
744 				 *
745 				 * The lookup finds Key2 in znode zb. Lets say
746 				 * there is no match and the name is greater so
747 				 * we look left. When we find Key0, we end up
748 				 * here. If we return now, we will insert into
749 				 * znode za at slot n = 1.  But that is invalid
750 				 * according to the parent's keys.  Key2 must
751 				 * be inserted into znode zb.
752 				 *
753 				 * Note, this problem is not relevant for the
754 				 * case when we go right, because
755 				 * 'tnc_insert()' would correct the parent key.
756 				 */
757 				if (*n == (*zn)->child_cnt - 1) {
758 					err = tnc_next(c, zn, n);
759 					if (err) {
760 						/* Should be impossible */
761 						ubifs_assert(0);
762 						if (err == -ENOENT)
763 							err = -EINVAL;
764 						return err;
765 					}
766 					ubifs_assert(*n == 0);
767 					*n = -1;
768 				}
769 				return 0;
770 			}
771 			err = matches_name(c, &(*zn)->zbranch[*n], nm);
772 			if (err < 0)
773 				return err;
774 			if (err == NAME_LESS)
775 				return 0;
776 			if (err == NAME_MATCHES)
777 				return 1;
778 			ubifs_assert(err == NAME_GREATER);
779 		}
780 	} else {
781 		int nn = *n;
782 		struct ubifs_znode *znode = *zn;
783 
784 		/* Look right */
785 		while (1) {
786 			err = tnc_next(c, &znode, &nn);
787 			if (err == -ENOENT)
788 				return 0;
789 			if (err < 0)
790 				return err;
791 			if (keys_cmp(c, &znode->zbranch[nn].key, key))
792 				return 0;
793 			err = matches_name(c, &znode->zbranch[nn], nm);
794 			if (err < 0)
795 				return err;
796 			if (err == NAME_GREATER)
797 				return 0;
798 			*zn = znode;
799 			*n = nn;
800 			if (err == NAME_MATCHES)
801 				return 1;
802 			ubifs_assert(err == NAME_LESS);
803 		}
804 	}
805 }
806 
807 /**
808  * fallible_matches_name - determine if a dent matches a given name.
809  * @c: UBIFS file-system description object
810  * @zbr: zbranch of dent
811  * @nm: name to match
812  *
813  * This is a "fallible" version of 'matches_name()' function which does not
814  * panic if the direntry/xentry referred by @zbr does not exist on the media.
815  *
816  * This function checks if xentry/direntry referred by zbranch @zbr matches name
817  * @nm. Returns %NAME_MATCHES it does, %NAME_LESS if the name referred by @zbr
818  * is less than @nm, %NAME_GREATER if it is greater than @nm, and @NOT_ON_MEDIA
819  * if xentry/direntry referred by @zbr does not exist on the media. A negative
820  * error code is returned in case of failure.
821  */
822 static int fallible_matches_name(struct ubifs_info *c,
823 				 struct ubifs_zbranch *zbr,
824 				 const struct qstr *nm)
825 {
826 	struct ubifs_dent_node *dent;
827 	int nlen, err;
828 
829 	/* If possible, match against the dent in the leaf node cache */
830 	if (!zbr->leaf) {
831 		dent = kmalloc(zbr->len, GFP_NOFS);
832 		if (!dent)
833 			return -ENOMEM;
834 
835 		err = fallible_read_node(c, &zbr->key, zbr, dent);
836 		if (err < 0)
837 			goto out_free;
838 		if (err == 0) {
839 			/* The node was not present */
840 			err = NOT_ON_MEDIA;
841 			goto out_free;
842 		}
843 		ubifs_assert(err == 1);
844 
845 		err = lnc_add_directly(c, zbr, dent);
846 		if (err)
847 			goto out_free;
848 	} else
849 		dent = zbr->leaf;
850 
851 	nlen = le16_to_cpu(dent->nlen);
852 	err = memcmp(dent->name, nm->name, min_t(int, nlen, nm->len));
853 	if (err == 0) {
854 		if (nlen == nm->len)
855 			return NAME_MATCHES;
856 		else if (nlen < nm->len)
857 			return NAME_LESS;
858 		else
859 			return NAME_GREATER;
860 	} else if (err < 0)
861 		return NAME_LESS;
862 	else
863 		return NAME_GREATER;
864 
865 out_free:
866 	kfree(dent);
867 	return err;
868 }
869 
870 /**
871  * fallible_resolve_collision - resolve a collision even if nodes are missing.
872  * @c: UBIFS file-system description object
873  * @key: key
874  * @zn: znode is returned here
875  * @n: branch number is passed and returned here
876  * @nm: name of directory entry
877  * @adding: indicates caller is adding a key to the TNC
878  *
879  * This is a "fallible" version of the 'resolve_collision()' function which
880  * does not panic if one of the nodes referred to by TNC does not exist on the
881  * media. This may happen when replaying the journal if a deleted node was
882  * Garbage-collected and the commit was not done. A branch that refers to a node
883  * that is not present is called a dangling branch. The following are the return
884  * codes for this function:
885  *  o if @nm was found, %1 is returned and @zn and @n are set to the found
886  *    branch;
887  *  o if we are @adding and @nm was not found, %0 is returned;
888  *  o if we are not @adding and @nm was not found, but a dangling branch was
889  *    found, then %1 is returned and @zn and @n are set to the dangling branch;
890  *  o a negative error code is returned in case of failure.
891  */
892 static int fallible_resolve_collision(struct ubifs_info *c,
893 				      const union ubifs_key *key,
894 				      struct ubifs_znode **zn, int *n,
895 				      const struct qstr *nm, int adding)
896 {
897 	struct ubifs_znode *o_znode = NULL, *znode = *zn;
898 	int uninitialized_var(o_n), err, cmp, unsure = 0, nn = *n;
899 
900 	cmp = fallible_matches_name(c, &znode->zbranch[nn], nm);
901 	if (unlikely(cmp < 0))
902 		return cmp;
903 	if (cmp == NAME_MATCHES)
904 		return 1;
905 	if (cmp == NOT_ON_MEDIA) {
906 		o_znode = znode;
907 		o_n = nn;
908 		/*
909 		 * We are unlucky and hit a dangling branch straight away.
910 		 * Now we do not really know where to go to find the needed
911 		 * branch - to the left or to the right. Well, let's try left.
912 		 */
913 		unsure = 1;
914 	} else if (!adding)
915 		unsure = 1; /* Remove a dangling branch wherever it is */
916 
917 	if (cmp == NAME_GREATER || unsure) {
918 		/* Look left */
919 		while (1) {
920 			err = tnc_prev(c, zn, n);
921 			if (err == -ENOENT) {
922 				ubifs_assert(*n == 0);
923 				*n = -1;
924 				break;
925 			}
926 			if (err < 0)
927 				return err;
928 			if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) {
929 				/* See comments in 'resolve_collision()' */
930 				if (*n == (*zn)->child_cnt - 1) {
931 					err = tnc_next(c, zn, n);
932 					if (err) {
933 						/* Should be impossible */
934 						ubifs_assert(0);
935 						if (err == -ENOENT)
936 							err = -EINVAL;
937 						return err;
938 					}
939 					ubifs_assert(*n == 0);
940 					*n = -1;
941 				}
942 				break;
943 			}
944 			err = fallible_matches_name(c, &(*zn)->zbranch[*n], nm);
945 			if (err < 0)
946 				return err;
947 			if (err == NAME_MATCHES)
948 				return 1;
949 			if (err == NOT_ON_MEDIA) {
950 				o_znode = *zn;
951 				o_n = *n;
952 				continue;
953 			}
954 			if (!adding)
955 				continue;
956 			if (err == NAME_LESS)
957 				break;
958 			else
959 				unsure = 0;
960 		}
961 	}
962 
963 	if (cmp == NAME_LESS || unsure) {
964 		/* Look right */
965 		*zn = znode;
966 		*n = nn;
967 		while (1) {
968 			err = tnc_next(c, &znode, &nn);
969 			if (err == -ENOENT)
970 				break;
971 			if (err < 0)
972 				return err;
973 			if (keys_cmp(c, &znode->zbranch[nn].key, key))
974 				break;
975 			err = fallible_matches_name(c, &znode->zbranch[nn], nm);
976 			if (err < 0)
977 				return err;
978 			if (err == NAME_GREATER)
979 				break;
980 			*zn = znode;
981 			*n = nn;
982 			if (err == NAME_MATCHES)
983 				return 1;
984 			if (err == NOT_ON_MEDIA) {
985 				o_znode = znode;
986 				o_n = nn;
987 			}
988 		}
989 	}
990 
991 	/* Never match a dangling branch when adding */
992 	if (adding || !o_znode)
993 		return 0;
994 
995 	dbg_mnt("dangling match LEB %d:%d len %d %s",
996 		o_znode->zbranch[o_n].lnum, o_znode->zbranch[o_n].offs,
997 		o_znode->zbranch[o_n].len, DBGKEY(key));
998 	*zn = o_znode;
999 	*n = o_n;
1000 	return 1;
1001 }
1002 
1003 /**
1004  * matches_position - determine if a zbranch matches a given position.
1005  * @zbr: zbranch of dent
1006  * @lnum: LEB number of dent to match
1007  * @offs: offset of dent to match
1008  *
1009  * This function returns %1 if @lnum:@offs matches, and %0 otherwise.
1010  */
1011 static int matches_position(struct ubifs_zbranch *zbr, int lnum, int offs)
1012 {
1013 	if (zbr->lnum == lnum && zbr->offs == offs)
1014 		return 1;
1015 	else
1016 		return 0;
1017 }
1018 
1019 /**
1020  * resolve_collision_directly - resolve a collision directly.
1021  * @c: UBIFS file-system description object
1022  * @key: key of directory entry
1023  * @zn: znode is passed and returned here
1024  * @n: zbranch number is passed and returned here
1025  * @lnum: LEB number of dent node to match
1026  * @offs: offset of dent node to match
1027  *
1028  * This function is used for "hashed" keys to make sure the found directory or
1029  * extended attribute entry node is what was looked for. It is used when the
1030  * flash address of the right node is known (@lnum:@offs) which makes it much
1031  * easier to resolve collisions (no need to read entries and match full
1032  * names). This function returns %1 and sets @zn and @n if the collision is
1033  * resolved, %0 if @lnum:@offs is not found and @zn and @n are set to the
1034  * previous directory entry. Otherwise a negative error code is returned.
1035  */
1036 static int resolve_collision_directly(struct ubifs_info *c,
1037 				      const union ubifs_key *key,
1038 				      struct ubifs_znode **zn, int *n,
1039 				      int lnum, int offs)
1040 {
1041 	struct ubifs_znode *znode;
1042 	int nn, err;
1043 
1044 	znode = *zn;
1045 	nn = *n;
1046 	if (matches_position(&znode->zbranch[nn], lnum, offs))
1047 		return 1;
1048 
1049 	/* Look left */
1050 	while (1) {
1051 		err = tnc_prev(c, &znode, &nn);
1052 		if (err == -ENOENT)
1053 			break;
1054 		if (err < 0)
1055 			return err;
1056 		if (keys_cmp(c, &znode->zbranch[nn].key, key))
1057 			break;
1058 		if (matches_position(&znode->zbranch[nn], lnum, offs)) {
1059 			*zn = znode;
1060 			*n = nn;
1061 			return 1;
1062 		}
1063 	}
1064 
1065 	/* Look right */
1066 	znode = *zn;
1067 	nn = *n;
1068 	while (1) {
1069 		err = tnc_next(c, &znode, &nn);
1070 		if (err == -ENOENT)
1071 			return 0;
1072 		if (err < 0)
1073 			return err;
1074 		if (keys_cmp(c, &znode->zbranch[nn].key, key))
1075 			return 0;
1076 		*zn = znode;
1077 		*n = nn;
1078 		if (matches_position(&znode->zbranch[nn], lnum, offs))
1079 			return 1;
1080 	}
1081 }
1082 
1083 /**
1084  * dirty_cow_bottom_up - dirty a znode and its ancestors.
1085  * @c: UBIFS file-system description object
1086  * @znode: znode to dirty
1087  *
1088  * If we do not have a unique key that resides in a znode, then we cannot
1089  * dirty that znode from the top down (i.e. by using lookup_level0_dirty)
1090  * This function records the path back to the last dirty ancestor, and then
1091  * dirties the znodes on that path.
1092  */
1093 static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c,
1094 					       struct ubifs_znode *znode)
1095 {
1096 	struct ubifs_znode *zp;
1097 	int *path = c->bottom_up_buf, p = 0;
1098 
1099 	ubifs_assert(c->zroot.znode);
1100 	ubifs_assert(znode);
1101 	if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) {
1102 		kfree(c->bottom_up_buf);
1103 		c->bottom_up_buf = kmalloc(c->zroot.znode->level * sizeof(int),
1104 					   GFP_NOFS);
1105 		if (!c->bottom_up_buf)
1106 			return ERR_PTR(-ENOMEM);
1107 		path = c->bottom_up_buf;
1108 	}
1109 	if (c->zroot.znode->level) {
1110 		/* Go up until parent is dirty */
1111 		while (1) {
1112 			int n;
1113 
1114 			zp = znode->parent;
1115 			if (!zp)
1116 				break;
1117 			n = znode->iip;
1118 			ubifs_assert(p < c->zroot.znode->level);
1119 			path[p++] = n;
1120 			if (!zp->cnext && ubifs_zn_dirty(znode))
1121 				break;
1122 			znode = zp;
1123 		}
1124 	}
1125 
1126 	/* Come back down, dirtying as we go */
1127 	while (1) {
1128 		struct ubifs_zbranch *zbr;
1129 
1130 		zp = znode->parent;
1131 		if (zp) {
1132 			ubifs_assert(path[p - 1] >= 0);
1133 			ubifs_assert(path[p - 1] < zp->child_cnt);
1134 			zbr = &zp->zbranch[path[--p]];
1135 			znode = dirty_cow_znode(c, zbr);
1136 		} else {
1137 			ubifs_assert(znode == c->zroot.znode);
1138 			znode = dirty_cow_znode(c, &c->zroot);
1139 		}
1140 		if (IS_ERR(znode) || !p)
1141 			break;
1142 		ubifs_assert(path[p - 1] >= 0);
1143 		ubifs_assert(path[p - 1] < znode->child_cnt);
1144 		znode = znode->zbranch[path[p - 1]].znode;
1145 	}
1146 
1147 	return znode;
1148 }
1149 
1150 /**
1151  * ubifs_lookup_level0 - search for zero-level znode.
1152  * @c: UBIFS file-system description object
1153  * @key:  key to lookup
1154  * @zn: znode is returned here
1155  * @n: znode branch slot number is returned here
1156  *
1157  * This function looks up the TNC tree and search for zero-level znode which
1158  * refers key @key. The found zero-level znode is returned in @zn. There are 3
1159  * cases:
1160  *   o exact match, i.e. the found zero-level znode contains key @key, then %1
1161  *     is returned and slot number of the matched branch is stored in @n;
1162  *   o not exact match, which means that zero-level znode does not contain
1163  *     @key, then %0 is returned and slot number of the closest branch is stored
1164  *     in @n;
1165  *   o @key is so small that it is even less than the lowest key of the
1166  *     leftmost zero-level node, then %0 is returned and %0 is stored in @n.
1167  *
1168  * Note, when the TNC tree is traversed, some znodes may be absent, then this
1169  * function reads corresponding indexing nodes and inserts them to TNC. In
1170  * case of failure, a negative error code is returned.
1171  */
1172 int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key,
1173 			struct ubifs_znode **zn, int *n)
1174 {
1175 	int err, exact;
1176 	struct ubifs_znode *znode;
1177 	unsigned long time = get_seconds();
1178 
1179 	dbg_tnc("search key %s", DBGKEY(key));
1180 	ubifs_assert(key_type(c, key) < UBIFS_INVALID_KEY);
1181 
1182 	znode = c->zroot.znode;
1183 	if (unlikely(!znode)) {
1184 		znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
1185 		if (IS_ERR(znode))
1186 			return PTR_ERR(znode);
1187 	}
1188 
1189 	znode->time = time;
1190 
1191 	while (1) {
1192 		struct ubifs_zbranch *zbr;
1193 
1194 		exact = ubifs_search_zbranch(c, znode, key, n);
1195 
1196 		if (znode->level == 0)
1197 			break;
1198 
1199 		if (*n < 0)
1200 			*n = 0;
1201 		zbr = &znode->zbranch[*n];
1202 
1203 		if (zbr->znode) {
1204 			znode->time = time;
1205 			znode = zbr->znode;
1206 			continue;
1207 		}
1208 
1209 		/* znode is not in TNC cache, load it from the media */
1210 		znode = ubifs_load_znode(c, zbr, znode, *n);
1211 		if (IS_ERR(znode))
1212 			return PTR_ERR(znode);
1213 	}
1214 
1215 	*zn = znode;
1216 	if (exact || !is_hash_key(c, key) || *n != -1) {
1217 		dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);
1218 		return exact;
1219 	}
1220 
1221 	/*
1222 	 * Here is a tricky place. We have not found the key and this is a
1223 	 * "hashed" key, which may collide. The rest of the code deals with
1224 	 * situations like this:
1225 	 *
1226 	 *                  | 3 | 5 |
1227 	 *                  /       \
1228 	 *          | 3 | 5 |      | 6 | 7 | (x)
1229 	 *
1230 	 * Or more a complex example:
1231 	 *
1232 	 *                | 1 | 5 |
1233 	 *                /       \
1234 	 *       | 1 | 3 |         | 5 | 8 |
1235 	 *              \           /
1236 	 *          | 5 | 5 |   | 6 | 7 | (x)
1237 	 *
1238 	 * In the examples, if we are looking for key "5", we may reach nodes
1239 	 * marked with "(x)". In this case what we have do is to look at the
1240 	 * left and see if there is "5" key there. If there is, we have to
1241 	 * return it.
1242 	 *
1243 	 * Note, this whole situation is possible because we allow to have
1244 	 * elements which are equivalent to the next key in the parent in the
1245 	 * children of current znode. For example, this happens if we split a
1246 	 * znode like this: | 3 | 5 | 5 | 6 | 7 |, which results in something
1247 	 * like this:
1248 	 *                      | 3 | 5 |
1249 	 *                       /     \
1250 	 *                | 3 | 5 |   | 5 | 6 | 7 |
1251 	 *                              ^
1252 	 * And this becomes what is at the first "picture" after key "5" marked
1253 	 * with "^" is removed. What could be done is we could prohibit
1254 	 * splitting in the middle of the colliding sequence. Also, when
1255 	 * removing the leftmost key, we would have to correct the key of the
1256 	 * parent node, which would introduce additional complications. Namely,
1257 	 * if we changed the leftmost key of the parent znode, the garbage
1258 	 * collector would be unable to find it (GC is doing this when GC'ing
1259 	 * indexing LEBs). Although we already have an additional RB-tree where
1260 	 * we save such changed znodes (see 'ins_clr_old_idx_znode()') until
1261 	 * after the commit. But anyway, this does not look easy to implement
1262 	 * so we did not try this.
1263 	 */
1264 	err = tnc_prev(c, &znode, n);
1265 	if (err == -ENOENT) {
1266 		dbg_tnc("found 0, lvl %d, n -1", znode->level);
1267 		*n = -1;
1268 		return 0;
1269 	}
1270 	if (unlikely(err < 0))
1271 		return err;
1272 	if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
1273 		dbg_tnc("found 0, lvl %d, n -1", znode->level);
1274 		*n = -1;
1275 		return 0;
1276 	}
1277 
1278 	dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);
1279 	*zn = znode;
1280 	return 1;
1281 }
1282 
1283 /**
1284  * lookup_level0_dirty - search for zero-level znode dirtying.
1285  * @c: UBIFS file-system description object
1286  * @key:  key to lookup
1287  * @zn: znode is returned here
1288  * @n: znode branch slot number is returned here
1289  *
1290  * This function looks up the TNC tree and search for zero-level znode which
1291  * refers key @key. The found zero-level znode is returned in @zn. There are 3
1292  * cases:
1293  *   o exact match, i.e. the found zero-level znode contains key @key, then %1
1294  *     is returned and slot number of the matched branch is stored in @n;
1295  *   o not exact match, which means that zero-level znode does not contain @key
1296  *     then %0 is returned and slot number of the closed branch is stored in
1297  *     @n;
1298  *   o @key is so small that it is even less than the lowest key of the
1299  *     leftmost zero-level node, then %0 is returned and %-1 is stored in @n.
1300  *
1301  * Additionally all znodes in the path from the root to the located zero-level
1302  * znode are marked as dirty.
1303  *
1304  * Note, when the TNC tree is traversed, some znodes may be absent, then this
1305  * function reads corresponding indexing nodes and inserts them to TNC. In
1306  * case of failure, a negative error code is returned.
1307  */
1308 static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key,
1309 			       struct ubifs_znode **zn, int *n)
1310 {
1311 	int err, exact;
1312 	struct ubifs_znode *znode;
1313 	unsigned long time = get_seconds();
1314 
1315 	dbg_tnc("search and dirty key %s", DBGKEY(key));
1316 
1317 	znode = c->zroot.znode;
1318 	if (unlikely(!znode)) {
1319 		znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
1320 		if (IS_ERR(znode))
1321 			return PTR_ERR(znode);
1322 	}
1323 
1324 	znode = dirty_cow_znode(c, &c->zroot);
1325 	if (IS_ERR(znode))
1326 		return PTR_ERR(znode);
1327 
1328 	znode->time = time;
1329 
1330 	while (1) {
1331 		struct ubifs_zbranch *zbr;
1332 
1333 		exact = ubifs_search_zbranch(c, znode, key, n);
1334 
1335 		if (znode->level == 0)
1336 			break;
1337 
1338 		if (*n < 0)
1339 			*n = 0;
1340 		zbr = &znode->zbranch[*n];
1341 
1342 		if (zbr->znode) {
1343 			znode->time = time;
1344 			znode = dirty_cow_znode(c, zbr);
1345 			if (IS_ERR(znode))
1346 				return PTR_ERR(znode);
1347 			continue;
1348 		}
1349 
1350 		/* znode is not in TNC cache, load it from the media */
1351 		znode = ubifs_load_znode(c, zbr, znode, *n);
1352 		if (IS_ERR(znode))
1353 			return PTR_ERR(znode);
1354 		znode = dirty_cow_znode(c, zbr);
1355 		if (IS_ERR(znode))
1356 			return PTR_ERR(znode);
1357 	}
1358 
1359 	*zn = znode;
1360 	if (exact || !is_hash_key(c, key) || *n != -1) {
1361 		dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n);
1362 		return exact;
1363 	}
1364 
1365 	/*
1366 	 * See huge comment at 'lookup_level0_dirty()' what is the rest of the
1367 	 * code.
1368 	 */
1369 	err = tnc_prev(c, &znode, n);
1370 	if (err == -ENOENT) {
1371 		*n = -1;
1372 		dbg_tnc("found 0, lvl %d, n -1", znode->level);
1373 		return 0;
1374 	}
1375 	if (unlikely(err < 0))
1376 		return err;
1377 	if (keys_cmp(c, key, &znode->zbranch[*n].key)) {
1378 		*n = -1;
1379 		dbg_tnc("found 0, lvl %d, n -1", znode->level);
1380 		return 0;
1381 	}
1382 
1383 	if (znode->cnext || !ubifs_zn_dirty(znode)) {
1384 		znode = dirty_cow_bottom_up(c, znode);
1385 		if (IS_ERR(znode))
1386 			return PTR_ERR(znode);
1387 	}
1388 
1389 	dbg_tnc("found 1, lvl %d, n %d", znode->level, *n);
1390 	*zn = znode;
1391 	return 1;
1392 }
1393 
1394 /**
1395  * maybe_leb_gced - determine if a LEB may have been garbage collected.
1396  * @c: UBIFS file-system description object
1397  * @lnum: LEB number
1398  * @gc_seq1: garbage collection sequence number
1399  *
1400  * This function determines if @lnum may have been garbage collected since
1401  * sequence number @gc_seq1. If it may have been then %1 is returned, otherwise
1402  * %0 is returned.
1403  */
1404 static int maybe_leb_gced(struct ubifs_info *c, int lnum, int gc_seq1)
1405 {
1406 	int gc_seq2, gced_lnum;
1407 
1408 	gced_lnum = c->gced_lnum;
1409 	smp_rmb();
1410 	gc_seq2 = c->gc_seq;
1411 	/* Same seq means no GC */
1412 	if (gc_seq1 == gc_seq2)
1413 		return 0;
1414 	/* Different by more than 1 means we don't know */
1415 	if (gc_seq1 + 1 != gc_seq2)
1416 		return 1;
1417 	/*
1418 	 * We have seen the sequence number has increased by 1. Now we need to
1419 	 * be sure we read the right LEB number, so read it again.
1420 	 */
1421 	smp_rmb();
1422 	if (gced_lnum != c->gced_lnum)
1423 		return 1;
1424 	/* Finally we can check lnum */
1425 	if (gced_lnum == lnum)
1426 		return 1;
1427 	return 0;
1428 }
1429 
1430 /**
1431  * ubifs_tnc_locate - look up a file-system node and return it and its location.
1432  * @c: UBIFS file-system description object
1433  * @key: node key to lookup
1434  * @node: the node is returned here
1435  * @lnum: LEB number is returned here
1436  * @offs: offset is returned here
1437  *
1438  * This function looks up and reads node with key @key. The caller has to make
1439  * sure the @node buffer is large enough to fit the node. Returns zero in case
1440  * of success, %-ENOENT if the node was not found, and a negative error code in
1441  * case of failure. The node location can be returned in @lnum and @offs.
1442  */
1443 int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key,
1444 		     void *node, int *lnum, int *offs)
1445 {
1446 	int found, n, err, safely = 0, gc_seq1;
1447 	struct ubifs_znode *znode;
1448 	struct ubifs_zbranch zbr, *zt;
1449 
1450 again:
1451 	mutex_lock(&c->tnc_mutex);
1452 	found = ubifs_lookup_level0(c, key, &znode, &n);
1453 	if (!found) {
1454 		err = -ENOENT;
1455 		goto out;
1456 	} else if (found < 0) {
1457 		err = found;
1458 		goto out;
1459 	}
1460 	zt = &znode->zbranch[n];
1461 	if (lnum) {
1462 		*lnum = zt->lnum;
1463 		*offs = zt->offs;
1464 	}
1465 	if (is_hash_key(c, key)) {
1466 		/*
1467 		 * In this case the leaf node cache gets used, so we pass the
1468 		 * address of the zbranch and keep the mutex locked
1469 		 */
1470 		err = tnc_read_node_nm(c, zt, node);
1471 		goto out;
1472 	}
1473 	if (safely) {
1474 		err = ubifs_tnc_read_node(c, zt, node);
1475 		goto out;
1476 	}
1477 	/* Drop the TNC mutex prematurely and race with garbage collection */
1478 	zbr = znode->zbranch[n];
1479 	gc_seq1 = c->gc_seq;
1480 	mutex_unlock(&c->tnc_mutex);
1481 
1482 	if (ubifs_get_wbuf(c, zbr.lnum)) {
1483 		/* We do not GC journal heads */
1484 		err = ubifs_tnc_read_node(c, &zbr, node);
1485 		return err;
1486 	}
1487 
1488 	err = fallible_read_node(c, key, &zbr, node);
1489 	if (err <= 0 || maybe_leb_gced(c, zbr.lnum, gc_seq1)) {
1490 		/*
1491 		 * The node may have been GC'ed out from under us so try again
1492 		 * while keeping the TNC mutex locked.
1493 		 */
1494 		safely = 1;
1495 		goto again;
1496 	}
1497 	return 0;
1498 
1499 out:
1500 	mutex_unlock(&c->tnc_mutex);
1501 	return err;
1502 }
1503 
1504 /**
1505  * ubifs_tnc_get_bu_keys - lookup keys for bulk-read.
1506  * @c: UBIFS file-system description object
1507  * @bu: bulk-read parameters and results
1508  *
1509  * Lookup consecutive data node keys for the same inode that reside
1510  * consecutively in the same LEB. This function returns zero in case of success
1511  * and a negative error code in case of failure.
1512  *
1513  * Note, if the bulk-read buffer length (@bu->buf_len) is known, this function
1514  * makes sure bulk-read nodes fit the buffer. Otherwise, this function prepares
1515  * maximum possible amount of nodes for bulk-read.
1516  */
1517 int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu)
1518 {
1519 	int n, err = 0, lnum = -1, uninitialized_var(offs);
1520 	int uninitialized_var(len);
1521 	unsigned int block = key_block(c, &bu->key);
1522 	struct ubifs_znode *znode;
1523 
1524 	bu->cnt = 0;
1525 	bu->blk_cnt = 0;
1526 	bu->eof = 0;
1527 
1528 	mutex_lock(&c->tnc_mutex);
1529 	/* Find first key */
1530 	err = ubifs_lookup_level0(c, &bu->key, &znode, &n);
1531 	if (err < 0)
1532 		goto out;
1533 	if (err) {
1534 		/* Key found */
1535 		len = znode->zbranch[n].len;
1536 		/* The buffer must be big enough for at least 1 node */
1537 		if (len > bu->buf_len) {
1538 			err = -EINVAL;
1539 			goto out;
1540 		}
1541 		/* Add this key */
1542 		bu->zbranch[bu->cnt++] = znode->zbranch[n];
1543 		bu->blk_cnt += 1;
1544 		lnum = znode->zbranch[n].lnum;
1545 		offs = ALIGN(znode->zbranch[n].offs + len, 8);
1546 	}
1547 	while (1) {
1548 		struct ubifs_zbranch *zbr;
1549 		union ubifs_key *key;
1550 		unsigned int next_block;
1551 
1552 		/* Find next key */
1553 		err = tnc_next(c, &znode, &n);
1554 		if (err)
1555 			goto out;
1556 		zbr = &znode->zbranch[n];
1557 		key = &zbr->key;
1558 		/* See if there is another data key for this file */
1559 		if (key_inum(c, key) != key_inum(c, &bu->key) ||
1560 		    key_type(c, key) != UBIFS_DATA_KEY) {
1561 			err = -ENOENT;
1562 			goto out;
1563 		}
1564 		if (lnum < 0) {
1565 			/* First key found */
1566 			lnum = zbr->lnum;
1567 			offs = ALIGN(zbr->offs + zbr->len, 8);
1568 			len = zbr->len;
1569 			if (len > bu->buf_len) {
1570 				err = -EINVAL;
1571 				goto out;
1572 			}
1573 		} else {
1574 			/*
1575 			 * The data nodes must be in consecutive positions in
1576 			 * the same LEB.
1577 			 */
1578 			if (zbr->lnum != lnum || zbr->offs != offs)
1579 				goto out;
1580 			offs += ALIGN(zbr->len, 8);
1581 			len = ALIGN(len, 8) + zbr->len;
1582 			/* Must not exceed buffer length */
1583 			if (len > bu->buf_len)
1584 				goto out;
1585 		}
1586 		/* Allow for holes */
1587 		next_block = key_block(c, key);
1588 		bu->blk_cnt += (next_block - block - 1);
1589 		if (bu->blk_cnt >= UBIFS_MAX_BULK_READ)
1590 			goto out;
1591 		block = next_block;
1592 		/* Add this key */
1593 		bu->zbranch[bu->cnt++] = *zbr;
1594 		bu->blk_cnt += 1;
1595 		/* See if we have room for more */
1596 		if (bu->cnt >= UBIFS_MAX_BULK_READ)
1597 			goto out;
1598 		if (bu->blk_cnt >= UBIFS_MAX_BULK_READ)
1599 			goto out;
1600 	}
1601 out:
1602 	if (err == -ENOENT) {
1603 		bu->eof = 1;
1604 		err = 0;
1605 	}
1606 	bu->gc_seq = c->gc_seq;
1607 	mutex_unlock(&c->tnc_mutex);
1608 	if (err)
1609 		return err;
1610 	/*
1611 	 * An enormous hole could cause bulk-read to encompass too many
1612 	 * page cache pages, so limit the number here.
1613 	 */
1614 	if (bu->blk_cnt > UBIFS_MAX_BULK_READ)
1615 		bu->blk_cnt = UBIFS_MAX_BULK_READ;
1616 	/*
1617 	 * Ensure that bulk-read covers a whole number of page cache
1618 	 * pages.
1619 	 */
1620 	if (UBIFS_BLOCKS_PER_PAGE == 1 ||
1621 	    !(bu->blk_cnt & (UBIFS_BLOCKS_PER_PAGE - 1)))
1622 		return 0;
1623 	if (bu->eof) {
1624 		/* At the end of file we can round up */
1625 		bu->blk_cnt += UBIFS_BLOCKS_PER_PAGE - 1;
1626 		return 0;
1627 	}
1628 	/* Exclude data nodes that do not make up a whole page cache page */
1629 	block = key_block(c, &bu->key) + bu->blk_cnt;
1630 	block &= ~(UBIFS_BLOCKS_PER_PAGE - 1);
1631 	while (bu->cnt) {
1632 		if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block)
1633 			break;
1634 		bu->cnt -= 1;
1635 	}
1636 	return 0;
1637 }
1638 
1639 /**
1640  * read_wbuf - bulk-read from a LEB with a wbuf.
1641  * @wbuf: wbuf that may overlap the read
1642  * @buf: buffer into which to read
1643  * @len: read length
1644  * @lnum: LEB number from which to read
1645  * @offs: offset from which to read
1646  *
1647  * This functions returns %0 on success or a negative error code on failure.
1648  */
1649 static int read_wbuf(struct ubifs_wbuf *wbuf, void *buf, int len, int lnum,
1650 		     int offs)
1651 {
1652 	const struct ubifs_info *c = wbuf->c;
1653 	int rlen, overlap;
1654 
1655 	dbg_io("LEB %d:%d, length %d", lnum, offs, len);
1656 	ubifs_assert(wbuf && lnum >= 0 && lnum < c->leb_cnt && offs >= 0);
1657 	ubifs_assert(!(offs & 7) && offs < c->leb_size);
1658 	ubifs_assert(offs + len <= c->leb_size);
1659 
1660 	spin_lock(&wbuf->lock);
1661 	overlap = (lnum == wbuf->lnum && offs + len > wbuf->offs);
1662 	if (!overlap) {
1663 		/* We may safely unlock the write-buffer and read the data */
1664 		spin_unlock(&wbuf->lock);
1665 		return ubi_read(c->ubi, lnum, buf, offs, len);
1666 	}
1667 
1668 	/* Don't read under wbuf */
1669 	rlen = wbuf->offs - offs;
1670 	if (rlen < 0)
1671 		rlen = 0;
1672 
1673 	/* Copy the rest from the write-buffer */
1674 	memcpy(buf + rlen, wbuf->buf + offs + rlen - wbuf->offs, len - rlen);
1675 	spin_unlock(&wbuf->lock);
1676 
1677 	if (rlen > 0)
1678 		/* Read everything that goes before write-buffer */
1679 		return ubi_read(c->ubi, lnum, buf, offs, rlen);
1680 
1681 	return 0;
1682 }
1683 
1684 /**
1685  * validate_data_node - validate data nodes for bulk-read.
1686  * @c: UBIFS file-system description object
1687  * @buf: buffer containing data node to validate
1688  * @zbr: zbranch of data node to validate
1689  *
1690  * This functions returns %0 on success or a negative error code on failure.
1691  */
1692 static int validate_data_node(struct ubifs_info *c, void *buf,
1693 			      struct ubifs_zbranch *zbr)
1694 {
1695 	union ubifs_key key1;
1696 	struct ubifs_ch *ch = buf;
1697 	int err, len;
1698 
1699 	if (ch->node_type != UBIFS_DATA_NODE) {
1700 		ubifs_err("bad node type (%d but expected %d)",
1701 			  ch->node_type, UBIFS_DATA_NODE);
1702 		goto out_err;
1703 	}
1704 
1705 	err = ubifs_check_node(c, buf, zbr->lnum, zbr->offs, 0, 0);
1706 	if (err) {
1707 		ubifs_err("expected node type %d", UBIFS_DATA_NODE);
1708 		goto out;
1709 	}
1710 
1711 	len = le32_to_cpu(ch->len);
1712 	if (len != zbr->len) {
1713 		ubifs_err("bad node length %d, expected %d", len, zbr->len);
1714 		goto out_err;
1715 	}
1716 
1717 	/* Make sure the key of the read node is correct */
1718 	key_read(c, buf + UBIFS_KEY_OFFSET, &key1);
1719 	if (!keys_eq(c, &zbr->key, &key1)) {
1720 		ubifs_err("bad key in node at LEB %d:%d",
1721 			  zbr->lnum, zbr->offs);
1722 		dbg_tnc("looked for key %s found node's key %s",
1723 			DBGKEY(&zbr->key), DBGKEY1(&key1));
1724 		goto out_err;
1725 	}
1726 
1727 	return 0;
1728 
1729 out_err:
1730 	err = -EINVAL;
1731 out:
1732 	ubifs_err("bad node at LEB %d:%d", zbr->lnum, zbr->offs);
1733 	dbg_dump_node(c, buf);
1734 	dbg_dump_stack();
1735 	return err;
1736 }
1737 
1738 /**
1739  * ubifs_tnc_bulk_read - read a number of data nodes in one go.
1740  * @c: UBIFS file-system description object
1741  * @bu: bulk-read parameters and results
1742  *
1743  * This functions reads and validates the data nodes that were identified by the
1744  * 'ubifs_tnc_get_bu_keys()' function. This functions returns %0 on success,
1745  * -EAGAIN to indicate a race with GC, or another negative error code on
1746  * failure.
1747  */
1748 int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu)
1749 {
1750 	int lnum = bu->zbranch[0].lnum, offs = bu->zbranch[0].offs, len, err, i;
1751 	struct ubifs_wbuf *wbuf;
1752 	void *buf;
1753 
1754 	len = bu->zbranch[bu->cnt - 1].offs;
1755 	len += bu->zbranch[bu->cnt - 1].len - offs;
1756 	if (len > bu->buf_len) {
1757 		ubifs_err("buffer too small %d vs %d", bu->buf_len, len);
1758 		return -EINVAL;
1759 	}
1760 
1761 	/* Do the read */
1762 	wbuf = ubifs_get_wbuf(c, lnum);
1763 	if (wbuf)
1764 		err = read_wbuf(wbuf, bu->buf, len, lnum, offs);
1765 	else
1766 		err = ubi_read(c->ubi, lnum, bu->buf, offs, len);
1767 
1768 	/* Check for a race with GC */
1769 	if (maybe_leb_gced(c, lnum, bu->gc_seq))
1770 		return -EAGAIN;
1771 
1772 	if (err && err != -EBADMSG) {
1773 		ubifs_err("failed to read from LEB %d:%d, error %d",
1774 			  lnum, offs, err);
1775 		dbg_dump_stack();
1776 		dbg_tnc("key %s", DBGKEY(&bu->key));
1777 		return err;
1778 	}
1779 
1780 	/* Validate the nodes read */
1781 	buf = bu->buf;
1782 	for (i = 0; i < bu->cnt; i++) {
1783 		err = validate_data_node(c, buf, &bu->zbranch[i]);
1784 		if (err)
1785 			return err;
1786 		buf = buf + ALIGN(bu->zbranch[i].len, 8);
1787 	}
1788 
1789 	return 0;
1790 }
1791 
1792 /**
1793  * do_lookup_nm- look up a "hashed" node.
1794  * @c: UBIFS file-system description object
1795  * @key: node key to lookup
1796  * @node: the node is returned here
1797  * @nm: node name
1798  *
1799  * This function look up and reads a node which contains name hash in the key.
1800  * Since the hash may have collisions, there may be many nodes with the same
1801  * key, so we have to sequentially look to all of them until the needed one is
1802  * found. This function returns zero in case of success, %-ENOENT if the node
1803  * was not found, and a negative error code in case of failure.
1804  */
1805 static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1806 			void *node, const struct qstr *nm)
1807 {
1808 	int found, n, err;
1809 	struct ubifs_znode *znode;
1810 
1811 	dbg_tnc("name '%.*s' key %s", nm->len, nm->name, DBGKEY(key));
1812 	mutex_lock(&c->tnc_mutex);
1813 	found = ubifs_lookup_level0(c, key, &znode, &n);
1814 	if (!found) {
1815 		err = -ENOENT;
1816 		goto out_unlock;
1817 	} else if (found < 0) {
1818 		err = found;
1819 		goto out_unlock;
1820 	}
1821 
1822 	ubifs_assert(n >= 0);
1823 
1824 	err = resolve_collision(c, key, &znode, &n, nm);
1825 	dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
1826 	if (unlikely(err < 0))
1827 		goto out_unlock;
1828 	if (err == 0) {
1829 		err = -ENOENT;
1830 		goto out_unlock;
1831 	}
1832 
1833 	err = tnc_read_node_nm(c, &znode->zbranch[n], node);
1834 
1835 out_unlock:
1836 	mutex_unlock(&c->tnc_mutex);
1837 	return err;
1838 }
1839 
1840 /**
1841  * ubifs_tnc_lookup_nm - look up a "hashed" node.
1842  * @c: UBIFS file-system description object
1843  * @key: node key to lookup
1844  * @node: the node is returned here
1845  * @nm: node name
1846  *
1847  * This function look up and reads a node which contains name hash in the key.
1848  * Since the hash may have collisions, there may be many nodes with the same
1849  * key, so we have to sequentially look to all of them until the needed one is
1850  * found. This function returns zero in case of success, %-ENOENT if the node
1851  * was not found, and a negative error code in case of failure.
1852  */
1853 int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1854 			void *node, const struct qstr *nm)
1855 {
1856 	int err, len;
1857 	const struct ubifs_dent_node *dent = node;
1858 
1859 	/*
1860 	 * We assume that in most of the cases there are no name collisions and
1861 	 * 'ubifs_tnc_lookup()' returns us the right direntry.
1862 	 */
1863 	err = ubifs_tnc_lookup(c, key, node);
1864 	if (err)
1865 		return err;
1866 
1867 	len = le16_to_cpu(dent->nlen);
1868 	if (nm->len == len && !memcmp(dent->name, nm->name, len))
1869 		return 0;
1870 
1871 	/*
1872 	 * Unluckily, there are hash collisions and we have to iterate over
1873 	 * them look at each direntry with colliding name hash sequentially.
1874 	 */
1875 	return do_lookup_nm(c, key, node, nm);
1876 }
1877 
1878 /**
1879  * correct_parent_keys - correct parent znodes' keys.
1880  * @c: UBIFS file-system description object
1881  * @znode: znode to correct parent znodes for
1882  *
1883  * This is a helper function for 'tnc_insert()'. When the key of the leftmost
1884  * zbranch changes, keys of parent znodes have to be corrected. This helper
1885  * function is called in such situations and corrects the keys if needed.
1886  */
1887 static void correct_parent_keys(const struct ubifs_info *c,
1888 				struct ubifs_znode *znode)
1889 {
1890 	union ubifs_key *key, *key1;
1891 
1892 	ubifs_assert(znode->parent);
1893 	ubifs_assert(znode->iip == 0);
1894 
1895 	key = &znode->zbranch[0].key;
1896 	key1 = &znode->parent->zbranch[0].key;
1897 
1898 	while (keys_cmp(c, key, key1) < 0) {
1899 		key_copy(c, key, key1);
1900 		znode = znode->parent;
1901 		znode->alt = 1;
1902 		if (!znode->parent || znode->iip)
1903 			break;
1904 		key1 = &znode->parent->zbranch[0].key;
1905 	}
1906 }
1907 
1908 /**
1909  * insert_zbranch - insert a zbranch into a znode.
1910  * @znode: znode into which to insert
1911  * @zbr: zbranch to insert
1912  * @n: slot number to insert to
1913  *
1914  * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in
1915  * znode's array of zbranches and keeps zbranches consolidated, so when a new
1916  * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th
1917  * slot, zbranches starting from @n have to be moved right.
1918  */
1919 static void insert_zbranch(struct ubifs_znode *znode,
1920 			   const struct ubifs_zbranch *zbr, int n)
1921 {
1922 	int i;
1923 
1924 	ubifs_assert(ubifs_zn_dirty(znode));
1925 
1926 	if (znode->level) {
1927 		for (i = znode->child_cnt; i > n; i--) {
1928 			znode->zbranch[i] = znode->zbranch[i - 1];
1929 			if (znode->zbranch[i].znode)
1930 				znode->zbranch[i].znode->iip = i;
1931 		}
1932 		if (zbr->znode)
1933 			zbr->znode->iip = n;
1934 	} else
1935 		for (i = znode->child_cnt; i > n; i--)
1936 			znode->zbranch[i] = znode->zbranch[i - 1];
1937 
1938 	znode->zbranch[n] = *zbr;
1939 	znode->child_cnt += 1;
1940 
1941 	/*
1942 	 * After inserting at slot zero, the lower bound of the key range of
1943 	 * this znode may have changed. If this znode is subsequently split
1944 	 * then the upper bound of the key range may change, and furthermore
1945 	 * it could change to be lower than the original lower bound. If that
1946 	 * happens, then it will no longer be possible to find this znode in the
1947 	 * TNC using the key from the index node on flash. That is bad because
1948 	 * if it is not found, we will assume it is obsolete and may overwrite
1949 	 * it. Then if there is an unclean unmount, we will start using the
1950 	 * old index which will be broken.
1951 	 *
1952 	 * So we first mark znodes that have insertions at slot zero, and then
1953 	 * if they are split we add their lnum/offs to the old_idx tree.
1954 	 */
1955 	if (n == 0)
1956 		znode->alt = 1;
1957 }
1958 
1959 /**
1960  * tnc_insert - insert a node into TNC.
1961  * @c: UBIFS file-system description object
1962  * @znode: znode to insert into
1963  * @zbr: branch to insert
1964  * @n: slot number to insert new zbranch to
1965  *
1966  * This function inserts a new node described by @zbr into znode @znode. If
1967  * znode does not have a free slot for new zbranch, it is split. Parent znodes
1968  * are splat as well if needed. Returns zero in case of success or a negative
1969  * error code in case of failure.
1970  */
1971 static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,
1972 		      struct ubifs_zbranch *zbr, int n)
1973 {
1974 	struct ubifs_znode *zn, *zi, *zp;
1975 	int i, keep, move, appending = 0;
1976 	union ubifs_key *key = &zbr->key, *key1;
1977 
1978 	ubifs_assert(n >= 0 && n <= c->fanout);
1979 
1980 	/* Implement naive insert for now */
1981 again:
1982 	zp = znode->parent;
1983 	if (znode->child_cnt < c->fanout) {
1984 		ubifs_assert(n != c->fanout);
1985 		dbg_tnc("inserted at %d level %d, key %s", n, znode->level,
1986 			DBGKEY(key));
1987 
1988 		insert_zbranch(znode, zbr, n);
1989 
1990 		/* Ensure parent's key is correct */
1991 		if (n == 0 && zp && znode->iip == 0)
1992 			correct_parent_keys(c, znode);
1993 
1994 		return 0;
1995 	}
1996 
1997 	/*
1998 	 * Unfortunately, @znode does not have more empty slots and we have to
1999 	 * split it.
2000 	 */
2001 	dbg_tnc("splitting level %d, key %s", znode->level, DBGKEY(key));
2002 
2003 	if (znode->alt)
2004 		/*
2005 		 * We can no longer be sure of finding this znode by key, so we
2006 		 * record it in the old_idx tree.
2007 		 */
2008 		ins_clr_old_idx_znode(c, znode);
2009 
2010 	zn = kzalloc(c->max_znode_sz, GFP_NOFS);
2011 	if (!zn)
2012 		return -ENOMEM;
2013 	zn->parent = zp;
2014 	zn->level = znode->level;
2015 
2016 	/* Decide where to split */
2017 	if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {
2018 		/* Try not to split consecutive data keys */
2019 		if (n == c->fanout) {
2020 			key1 = &znode->zbranch[n - 1].key;
2021 			if (key_inum(c, key1) == key_inum(c, key) &&
2022 			    key_type(c, key1) == UBIFS_DATA_KEY)
2023 				appending = 1;
2024 		} else
2025 			goto check_split;
2026 	} else if (appending && n != c->fanout) {
2027 		/* Try not to split consecutive data keys */
2028 		appending = 0;
2029 check_split:
2030 		if (n >= (c->fanout + 1) / 2) {
2031 			key1 = &znode->zbranch[0].key;
2032 			if (key_inum(c, key1) == key_inum(c, key) &&
2033 			    key_type(c, key1) == UBIFS_DATA_KEY) {
2034 				key1 = &znode->zbranch[n].key;
2035 				if (key_inum(c, key1) != key_inum(c, key) ||
2036 				    key_type(c, key1) != UBIFS_DATA_KEY) {
2037 					keep = n;
2038 					move = c->fanout - keep;
2039 					zi = znode;
2040 					goto do_split;
2041 				}
2042 			}
2043 		}
2044 	}
2045 
2046 	if (appending) {
2047 		keep = c->fanout;
2048 		move = 0;
2049 	} else {
2050 		keep = (c->fanout + 1) / 2;
2051 		move = c->fanout - keep;
2052 	}
2053 
2054 	/*
2055 	 * Although we don't at present, we could look at the neighbors and see
2056 	 * if we can move some zbranches there.
2057 	 */
2058 
2059 	if (n < keep) {
2060 		/* Insert into existing znode */
2061 		zi = znode;
2062 		move += 1;
2063 		keep -= 1;
2064 	} else {
2065 		/* Insert into new znode */
2066 		zi = zn;
2067 		n -= keep;
2068 		/* Re-parent */
2069 		if (zn->level != 0)
2070 			zbr->znode->parent = zn;
2071 	}
2072 
2073 do_split:
2074 
2075 	__set_bit(DIRTY_ZNODE, &zn->flags);
2076 	atomic_long_inc(&c->dirty_zn_cnt);
2077 
2078 	zn->child_cnt = move;
2079 	znode->child_cnt = keep;
2080 
2081 	dbg_tnc("moving %d, keeping %d", move, keep);
2082 
2083 	/* Move zbranch */
2084 	for (i = 0; i < move; i++) {
2085 		zn->zbranch[i] = znode->zbranch[keep + i];
2086 		/* Re-parent */
2087 		if (zn->level != 0)
2088 			if (zn->zbranch[i].znode) {
2089 				zn->zbranch[i].znode->parent = zn;
2090 				zn->zbranch[i].znode->iip = i;
2091 			}
2092 	}
2093 
2094 	/* Insert new key and branch */
2095 	dbg_tnc("inserting at %d level %d, key %s", n, zn->level, DBGKEY(key));
2096 
2097 	insert_zbranch(zi, zbr, n);
2098 
2099 	/* Insert new znode (produced by spitting) into the parent */
2100 	if (zp) {
2101 		if (n == 0 && zi == znode && znode->iip == 0)
2102 			correct_parent_keys(c, znode);
2103 
2104 		/* Locate insertion point */
2105 		n = znode->iip + 1;
2106 
2107 		/* Tail recursion */
2108 		zbr->key = zn->zbranch[0].key;
2109 		zbr->znode = zn;
2110 		zbr->lnum = 0;
2111 		zbr->offs = 0;
2112 		zbr->len = 0;
2113 		znode = zp;
2114 
2115 		goto again;
2116 	}
2117 
2118 	/* We have to split root znode */
2119 	dbg_tnc("creating new zroot at level %d", znode->level + 1);
2120 
2121 	zi = kzalloc(c->max_znode_sz, GFP_NOFS);
2122 	if (!zi)
2123 		return -ENOMEM;
2124 
2125 	zi->child_cnt = 2;
2126 	zi->level = znode->level + 1;
2127 
2128 	__set_bit(DIRTY_ZNODE, &zi->flags);
2129 	atomic_long_inc(&c->dirty_zn_cnt);
2130 
2131 	zi->zbranch[0].key = znode->zbranch[0].key;
2132 	zi->zbranch[0].znode = znode;
2133 	zi->zbranch[0].lnum = c->zroot.lnum;
2134 	zi->zbranch[0].offs = c->zroot.offs;
2135 	zi->zbranch[0].len = c->zroot.len;
2136 	zi->zbranch[1].key = zn->zbranch[0].key;
2137 	zi->zbranch[1].znode = zn;
2138 
2139 	c->zroot.lnum = 0;
2140 	c->zroot.offs = 0;
2141 	c->zroot.len = 0;
2142 	c->zroot.znode = zi;
2143 
2144 	zn->parent = zi;
2145 	zn->iip = 1;
2146 	znode->parent = zi;
2147 	znode->iip = 0;
2148 
2149 	return 0;
2150 }
2151 
2152 /**
2153  * ubifs_tnc_add - add a node to TNC.
2154  * @c: UBIFS file-system description object
2155  * @key: key to add
2156  * @lnum: LEB number of node
2157  * @offs: node offset
2158  * @len: node length
2159  *
2160  * This function adds a node with key @key to TNC. The node may be new or it may
2161  * obsolete some existing one. Returns %0 on success or negative error code on
2162  * failure.
2163  */
2164 int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,
2165 		  int offs, int len)
2166 {
2167 	int found, n, err = 0;
2168 	struct ubifs_znode *znode;
2169 
2170 	mutex_lock(&c->tnc_mutex);
2171 	dbg_tnc("%d:%d, len %d, key %s", lnum, offs, len, DBGKEY(key));
2172 	found = lookup_level0_dirty(c, key, &znode, &n);
2173 	if (!found) {
2174 		struct ubifs_zbranch zbr;
2175 
2176 		zbr.znode = NULL;
2177 		zbr.lnum = lnum;
2178 		zbr.offs = offs;
2179 		zbr.len = len;
2180 		key_copy(c, key, &zbr.key);
2181 		err = tnc_insert(c, znode, &zbr, n + 1);
2182 	} else if (found == 1) {
2183 		struct ubifs_zbranch *zbr = &znode->zbranch[n];
2184 
2185 		lnc_free(zbr);
2186 		err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2187 		zbr->lnum = lnum;
2188 		zbr->offs = offs;
2189 		zbr->len = len;
2190 	} else
2191 		err = found;
2192 	if (!err)
2193 		err = dbg_check_tnc(c, 0);
2194 	mutex_unlock(&c->tnc_mutex);
2195 
2196 	return err;
2197 }
2198 
2199 /**
2200  * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.
2201  * @c: UBIFS file-system description object
2202  * @key: key to add
2203  * @old_lnum: LEB number of old node
2204  * @old_offs: old node offset
2205  * @lnum: LEB number of node
2206  * @offs: node offset
2207  * @len: node length
2208  *
2209  * This function replaces a node with key @key in the TNC only if the old node
2210  * is found.  This function is called by garbage collection when node are moved.
2211  * Returns %0 on success or negative error code on failure.
2212  */
2213 int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,
2214 		      int old_lnum, int old_offs, int lnum, int offs, int len)
2215 {
2216 	int found, n, err = 0;
2217 	struct ubifs_znode *znode;
2218 
2219 	mutex_lock(&c->tnc_mutex);
2220 	dbg_tnc("old LEB %d:%d, new LEB %d:%d, len %d, key %s", old_lnum,
2221 		old_offs, lnum, offs, len, DBGKEY(key));
2222 	found = lookup_level0_dirty(c, key, &znode, &n);
2223 	if (found < 0) {
2224 		err = found;
2225 		goto out_unlock;
2226 	}
2227 
2228 	if (found == 1) {
2229 		struct ubifs_zbranch *zbr = &znode->zbranch[n];
2230 
2231 		found = 0;
2232 		if (zbr->lnum == old_lnum && zbr->offs == old_offs) {
2233 			lnc_free(zbr);
2234 			err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2235 			if (err)
2236 				goto out_unlock;
2237 			zbr->lnum = lnum;
2238 			zbr->offs = offs;
2239 			zbr->len = len;
2240 			found = 1;
2241 		} else if (is_hash_key(c, key)) {
2242 			found = resolve_collision_directly(c, key, &znode, &n,
2243 							   old_lnum, old_offs);
2244 			dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d",
2245 				found, znode, n, old_lnum, old_offs);
2246 			if (found < 0) {
2247 				err = found;
2248 				goto out_unlock;
2249 			}
2250 
2251 			if (found) {
2252 				/* Ensure the znode is dirtied */
2253 				if (znode->cnext || !ubifs_zn_dirty(znode)) {
2254 					znode = dirty_cow_bottom_up(c, znode);
2255 					if (IS_ERR(znode)) {
2256 						err = PTR_ERR(znode);
2257 						goto out_unlock;
2258 					}
2259 				}
2260 				zbr = &znode->zbranch[n];
2261 				lnc_free(zbr);
2262 				err = ubifs_add_dirt(c, zbr->lnum,
2263 						     zbr->len);
2264 				if (err)
2265 					goto out_unlock;
2266 				zbr->lnum = lnum;
2267 				zbr->offs = offs;
2268 				zbr->len = len;
2269 			}
2270 		}
2271 	}
2272 
2273 	if (!found)
2274 		err = ubifs_add_dirt(c, lnum, len);
2275 
2276 	if (!err)
2277 		err = dbg_check_tnc(c, 0);
2278 
2279 out_unlock:
2280 	mutex_unlock(&c->tnc_mutex);
2281 	return err;
2282 }
2283 
2284 /**
2285  * ubifs_tnc_add_nm - add a "hashed" node to TNC.
2286  * @c: UBIFS file-system description object
2287  * @key: key to add
2288  * @lnum: LEB number of node
2289  * @offs: node offset
2290  * @len: node length
2291  * @nm: node name
2292  *
2293  * This is the same as 'ubifs_tnc_add()' but it should be used with keys which
2294  * may have collisions, like directory entry keys.
2295  */
2296 int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,
2297 		     int lnum, int offs, int len, const struct qstr *nm)
2298 {
2299 	int found, n, err = 0;
2300 	struct ubifs_znode *znode;
2301 
2302 	mutex_lock(&c->tnc_mutex);
2303 	dbg_tnc("LEB %d:%d, name '%.*s', key %s", lnum, offs, nm->len, nm->name,
2304 		DBGKEY(key));
2305 	found = lookup_level0_dirty(c, key, &znode, &n);
2306 	if (found < 0) {
2307 		err = found;
2308 		goto out_unlock;
2309 	}
2310 
2311 	if (found == 1) {
2312 		if (c->replaying)
2313 			found = fallible_resolve_collision(c, key, &znode, &n,
2314 							   nm, 1);
2315 		else
2316 			found = resolve_collision(c, key, &znode, &n, nm);
2317 		dbg_tnc("rc returned %d, znode %p, n %d", found, znode, n);
2318 		if (found < 0) {
2319 			err = found;
2320 			goto out_unlock;
2321 		}
2322 
2323 		/* Ensure the znode is dirtied */
2324 		if (znode->cnext || !ubifs_zn_dirty(znode)) {
2325 			znode = dirty_cow_bottom_up(c, znode);
2326 			if (IS_ERR(znode)) {
2327 				err = PTR_ERR(znode);
2328 				goto out_unlock;
2329 			}
2330 		}
2331 
2332 		if (found == 1) {
2333 			struct ubifs_zbranch *zbr = &znode->zbranch[n];
2334 
2335 			lnc_free(zbr);
2336 			err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2337 			zbr->lnum = lnum;
2338 			zbr->offs = offs;
2339 			zbr->len = len;
2340 			goto out_unlock;
2341 		}
2342 	}
2343 
2344 	if (!found) {
2345 		struct ubifs_zbranch zbr;
2346 
2347 		zbr.znode = NULL;
2348 		zbr.lnum = lnum;
2349 		zbr.offs = offs;
2350 		zbr.len = len;
2351 		key_copy(c, key, &zbr.key);
2352 		err = tnc_insert(c, znode, &zbr, n + 1);
2353 		if (err)
2354 			goto out_unlock;
2355 		if (c->replaying) {
2356 			/*
2357 			 * We did not find it in the index so there may be a
2358 			 * dangling branch still in the index. So we remove it
2359 			 * by passing 'ubifs_tnc_remove_nm()' the same key but
2360 			 * an unmatchable name.
2361 			 */
2362 			struct qstr noname = { .len = 0, .name = "" };
2363 
2364 			err = dbg_check_tnc(c, 0);
2365 			mutex_unlock(&c->tnc_mutex);
2366 			if (err)
2367 				return err;
2368 			return ubifs_tnc_remove_nm(c, key, &noname);
2369 		}
2370 	}
2371 
2372 out_unlock:
2373 	if (!err)
2374 		err = dbg_check_tnc(c, 0);
2375 	mutex_unlock(&c->tnc_mutex);
2376 	return err;
2377 }
2378 
2379 /**
2380  * tnc_delete - delete a znode form TNC.
2381  * @c: UBIFS file-system description object
2382  * @znode: znode to delete from
2383  * @n: zbranch slot number to delete
2384  *
2385  * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
2386  * case of success and a negative error code in case of failure.
2387  */
2388 static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
2389 {
2390 	struct ubifs_zbranch *zbr;
2391 	struct ubifs_znode *zp;
2392 	int i, err;
2393 
2394 	/* Delete without merge for now */
2395 	ubifs_assert(znode->level == 0);
2396 	ubifs_assert(n >= 0 && n < c->fanout);
2397 	dbg_tnc("deleting %s", DBGKEY(&znode->zbranch[n].key));
2398 
2399 	zbr = &znode->zbranch[n];
2400 	lnc_free(zbr);
2401 
2402 	err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2403 	if (err) {
2404 		dbg_dump_znode(c, znode);
2405 		return err;
2406 	}
2407 
2408 	/* We do not "gap" zbranch slots */
2409 	for (i = n; i < znode->child_cnt - 1; i++)
2410 		znode->zbranch[i] = znode->zbranch[i + 1];
2411 	znode->child_cnt -= 1;
2412 
2413 	if (znode->child_cnt > 0)
2414 		return 0;
2415 
2416 	/*
2417 	 * This was the last zbranch, we have to delete this znode from the
2418 	 * parent.
2419 	 */
2420 
2421 	do {
2422 		ubifs_assert(!test_bit(OBSOLETE_ZNODE, &znode->flags));
2423 		ubifs_assert(ubifs_zn_dirty(znode));
2424 
2425 		zp = znode->parent;
2426 		n = znode->iip;
2427 
2428 		atomic_long_dec(&c->dirty_zn_cnt);
2429 
2430 		err = insert_old_idx_znode(c, znode);
2431 		if (err)
2432 			return err;
2433 
2434 		if (znode->cnext) {
2435 			__set_bit(OBSOLETE_ZNODE, &znode->flags);
2436 			atomic_long_inc(&c->clean_zn_cnt);
2437 			atomic_long_inc(&ubifs_clean_zn_cnt);
2438 		} else
2439 			kfree(znode);
2440 		znode = zp;
2441 	} while (znode->child_cnt == 1); /* while removing last child */
2442 
2443 	/* Remove from znode, entry n - 1 */
2444 	znode->child_cnt -= 1;
2445 	ubifs_assert(znode->level != 0);
2446 	for (i = n; i < znode->child_cnt; i++) {
2447 		znode->zbranch[i] = znode->zbranch[i + 1];
2448 		if (znode->zbranch[i].znode)
2449 			znode->zbranch[i].znode->iip = i;
2450 	}
2451 
2452 	/*
2453 	 * If this is the root and it has only 1 child then
2454 	 * collapse the tree.
2455 	 */
2456 	if (!znode->parent) {
2457 		while (znode->child_cnt == 1 && znode->level != 0) {
2458 			zp = znode;
2459 			zbr = &znode->zbranch[0];
2460 			znode = get_znode(c, znode, 0);
2461 			if (IS_ERR(znode))
2462 				return PTR_ERR(znode);
2463 			znode = dirty_cow_znode(c, zbr);
2464 			if (IS_ERR(znode))
2465 				return PTR_ERR(znode);
2466 			znode->parent = NULL;
2467 			znode->iip = 0;
2468 			if (c->zroot.len) {
2469 				err = insert_old_idx(c, c->zroot.lnum,
2470 						     c->zroot.offs);
2471 				if (err)
2472 					return err;
2473 			}
2474 			c->zroot.lnum = zbr->lnum;
2475 			c->zroot.offs = zbr->offs;
2476 			c->zroot.len = zbr->len;
2477 			c->zroot.znode = znode;
2478 			ubifs_assert(!test_bit(OBSOLETE_ZNODE,
2479 				     &zp->flags));
2480 			ubifs_assert(test_bit(DIRTY_ZNODE, &zp->flags));
2481 			atomic_long_dec(&c->dirty_zn_cnt);
2482 
2483 			if (zp->cnext) {
2484 				__set_bit(OBSOLETE_ZNODE, &zp->flags);
2485 				atomic_long_inc(&c->clean_zn_cnt);
2486 				atomic_long_inc(&ubifs_clean_zn_cnt);
2487 			} else
2488 				kfree(zp);
2489 		}
2490 	}
2491 
2492 	return 0;
2493 }
2494 
2495 /**
2496  * ubifs_tnc_remove - remove an index entry of a node.
2497  * @c: UBIFS file-system description object
2498  * @key: key of node
2499  *
2500  * Returns %0 on success or negative error code on failure.
2501  */
2502 int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)
2503 {
2504 	int found, n, err = 0;
2505 	struct ubifs_znode *znode;
2506 
2507 	mutex_lock(&c->tnc_mutex);
2508 	dbg_tnc("key %s", DBGKEY(key));
2509 	found = lookup_level0_dirty(c, key, &znode, &n);
2510 	if (found < 0) {
2511 		err = found;
2512 		goto out_unlock;
2513 	}
2514 	if (found == 1)
2515 		err = tnc_delete(c, znode, n);
2516 	if (!err)
2517 		err = dbg_check_tnc(c, 0);
2518 
2519 out_unlock:
2520 	mutex_unlock(&c->tnc_mutex);
2521 	return err;
2522 }
2523 
2524 /**
2525  * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.
2526  * @c: UBIFS file-system description object
2527  * @key: key of node
2528  * @nm: directory entry name
2529  *
2530  * Returns %0 on success or negative error code on failure.
2531  */
2532 int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,
2533 			const struct qstr *nm)
2534 {
2535 	int n, err;
2536 	struct ubifs_znode *znode;
2537 
2538 	mutex_lock(&c->tnc_mutex);
2539 	dbg_tnc("%.*s, key %s", nm->len, nm->name, DBGKEY(key));
2540 	err = lookup_level0_dirty(c, key, &znode, &n);
2541 	if (err < 0)
2542 		goto out_unlock;
2543 
2544 	if (err) {
2545 		if (c->replaying)
2546 			err = fallible_resolve_collision(c, key, &znode, &n,
2547 							 nm, 0);
2548 		else
2549 			err = resolve_collision(c, key, &znode, &n, nm);
2550 		dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
2551 		if (err < 0)
2552 			goto out_unlock;
2553 		if (err) {
2554 			/* Ensure the znode is dirtied */
2555 			if (znode->cnext || !ubifs_zn_dirty(znode)) {
2556 				    znode = dirty_cow_bottom_up(c, znode);
2557 				    if (IS_ERR(znode)) {
2558 					    err = PTR_ERR(znode);
2559 					    goto out_unlock;
2560 				    }
2561 			}
2562 			err = tnc_delete(c, znode, n);
2563 		}
2564 	}
2565 
2566 out_unlock:
2567 	if (!err)
2568 		err = dbg_check_tnc(c, 0);
2569 	mutex_unlock(&c->tnc_mutex);
2570 	return err;
2571 }
2572 
2573 /**
2574  * key_in_range - determine if a key falls within a range of keys.
2575  * @c: UBIFS file-system description object
2576  * @key: key to check
2577  * @from_key: lowest key in range
2578  * @to_key: highest key in range
2579  *
2580  * This function returns %1 if the key is in range and %0 otherwise.
2581  */
2582 static int key_in_range(struct ubifs_info *c, union ubifs_key *key,
2583 			union ubifs_key *from_key, union ubifs_key *to_key)
2584 {
2585 	if (keys_cmp(c, key, from_key) < 0)
2586 		return 0;
2587 	if (keys_cmp(c, key, to_key) > 0)
2588 		return 0;
2589 	return 1;
2590 }
2591 
2592 /**
2593  * ubifs_tnc_remove_range - remove index entries in range.
2594  * @c: UBIFS file-system description object
2595  * @from_key: lowest key to remove
2596  * @to_key: highest key to remove
2597  *
2598  * This function removes index entries starting at @from_key and ending at
2599  * @to_key.  This function returns zero in case of success and a negative error
2600  * code in case of failure.
2601  */
2602 int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key,
2603 			   union ubifs_key *to_key)
2604 {
2605 	int i, n, k, err = 0;
2606 	struct ubifs_znode *znode;
2607 	union ubifs_key *key;
2608 
2609 	mutex_lock(&c->tnc_mutex);
2610 	while (1) {
2611 		/* Find first level 0 znode that contains keys to remove */
2612 		err = ubifs_lookup_level0(c, from_key, &znode, &n);
2613 		if (err < 0)
2614 			goto out_unlock;
2615 
2616 		if (err)
2617 			key = from_key;
2618 		else {
2619 			err = tnc_next(c, &znode, &n);
2620 			if (err == -ENOENT) {
2621 				err = 0;
2622 				goto out_unlock;
2623 			}
2624 			if (err < 0)
2625 				goto out_unlock;
2626 			key = &znode->zbranch[n].key;
2627 			if (!key_in_range(c, key, from_key, to_key)) {
2628 				err = 0;
2629 				goto out_unlock;
2630 			}
2631 		}
2632 
2633 		/* Ensure the znode is dirtied */
2634 		if (znode->cnext || !ubifs_zn_dirty(znode)) {
2635 			znode = dirty_cow_bottom_up(c, znode);
2636 			if (IS_ERR(znode)) {
2637 				err = PTR_ERR(znode);
2638 				goto out_unlock;
2639 			}
2640 		}
2641 
2642 		/* Remove all keys in range except the first */
2643 		for (i = n + 1, k = 0; i < znode->child_cnt; i++, k++) {
2644 			key = &znode->zbranch[i].key;
2645 			if (!key_in_range(c, key, from_key, to_key))
2646 				break;
2647 			lnc_free(&znode->zbranch[i]);
2648 			err = ubifs_add_dirt(c, znode->zbranch[i].lnum,
2649 					     znode->zbranch[i].len);
2650 			if (err) {
2651 				dbg_dump_znode(c, znode);
2652 				goto out_unlock;
2653 			}
2654 			dbg_tnc("removing %s", DBGKEY(key));
2655 		}
2656 		if (k) {
2657 			for (i = n + 1 + k; i < znode->child_cnt; i++)
2658 				znode->zbranch[i - k] = znode->zbranch[i];
2659 			znode->child_cnt -= k;
2660 		}
2661 
2662 		/* Now delete the first */
2663 		err = tnc_delete(c, znode, n);
2664 		if (err)
2665 			goto out_unlock;
2666 	}
2667 
2668 out_unlock:
2669 	if (!err)
2670 		err = dbg_check_tnc(c, 0);
2671 	mutex_unlock(&c->tnc_mutex);
2672 	return err;
2673 }
2674 
2675 /**
2676  * ubifs_tnc_remove_ino - remove an inode from TNC.
2677  * @c: UBIFS file-system description object
2678  * @inum: inode number to remove
2679  *
2680  * This function remove inode @inum and all the extended attributes associated
2681  * with the anode from TNC and returns zero in case of success or a negative
2682  * error code in case of failure.
2683  */
2684 int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum)
2685 {
2686 	union ubifs_key key1, key2;
2687 	struct ubifs_dent_node *xent, *pxent = NULL;
2688 	struct qstr nm = { .name = NULL };
2689 
2690 	dbg_tnc("ino %lu", (unsigned long)inum);
2691 
2692 	/*
2693 	 * Walk all extended attribute entries and remove them together with
2694 	 * corresponding extended attribute inodes.
2695 	 */
2696 	lowest_xent_key(c, &key1, inum);
2697 	while (1) {
2698 		ino_t xattr_inum;
2699 		int err;
2700 
2701 		xent = ubifs_tnc_next_ent(c, &key1, &nm);
2702 		if (IS_ERR(xent)) {
2703 			err = PTR_ERR(xent);
2704 			if (err == -ENOENT)
2705 				break;
2706 			return err;
2707 		}
2708 
2709 		xattr_inum = le64_to_cpu(xent->inum);
2710 		dbg_tnc("xent '%s', ino %lu", xent->name,
2711 			(unsigned long)xattr_inum);
2712 
2713 		nm.name = xent->name;
2714 		nm.len = le16_to_cpu(xent->nlen);
2715 		err = ubifs_tnc_remove_nm(c, &key1, &nm);
2716 		if (err) {
2717 			kfree(xent);
2718 			return err;
2719 		}
2720 
2721 		lowest_ino_key(c, &key1, xattr_inum);
2722 		highest_ino_key(c, &key2, xattr_inum);
2723 		err = ubifs_tnc_remove_range(c, &key1, &key2);
2724 		if (err) {
2725 			kfree(xent);
2726 			return err;
2727 		}
2728 
2729 		kfree(pxent);
2730 		pxent = xent;
2731 		key_read(c, &xent->key, &key1);
2732 	}
2733 
2734 	kfree(pxent);
2735 	lowest_ino_key(c, &key1, inum);
2736 	highest_ino_key(c, &key2, inum);
2737 
2738 	return ubifs_tnc_remove_range(c, &key1, &key2);
2739 }
2740 
2741 /**
2742  * ubifs_tnc_next_ent - walk directory or extended attribute entries.
2743  * @c: UBIFS file-system description object
2744  * @key: key of last entry
2745  * @nm: name of last entry found or %NULL
2746  *
2747  * This function finds and reads the next directory or extended attribute entry
2748  * after the given key (@key) if there is one. @nm is used to resolve
2749  * collisions.
2750  *
2751  * If the name of the current entry is not known and only the key is known,
2752  * @nm->name has to be %NULL. In this case the semantics of this function is a
2753  * little bit different and it returns the entry corresponding to this key, not
2754  * the next one. If the key was not found, the closest "right" entry is
2755  * returned.
2756  *
2757  * If the fist entry has to be found, @key has to contain the lowest possible
2758  * key value for this inode and @name has to be %NULL.
2759  *
2760  * This function returns the found directory or extended attribute entry node
2761  * in case of success, %-ENOENT is returned if no entry was found, and a
2762  * negative error code is returned in case of failure.
2763  */
2764 struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c,
2765 					   union ubifs_key *key,
2766 					   const struct qstr *nm)
2767 {
2768 	int n, err, type = key_type(c, key);
2769 	struct ubifs_znode *znode;
2770 	struct ubifs_dent_node *dent;
2771 	struct ubifs_zbranch *zbr;
2772 	union ubifs_key *dkey;
2773 
2774 	dbg_tnc("%s %s", nm->name ? (char *)nm->name : "(lowest)", DBGKEY(key));
2775 	ubifs_assert(is_hash_key(c, key));
2776 
2777 	mutex_lock(&c->tnc_mutex);
2778 	err = ubifs_lookup_level0(c, key, &znode, &n);
2779 	if (unlikely(err < 0))
2780 		goto out_unlock;
2781 
2782 	if (nm->name) {
2783 		if (err) {
2784 			/* Handle collisions */
2785 			err = resolve_collision(c, key, &znode, &n, nm);
2786 			dbg_tnc("rc returned %d, znode %p, n %d",
2787 				err, znode, n);
2788 			if (unlikely(err < 0))
2789 				goto out_unlock;
2790 		}
2791 
2792 		/* Now find next entry */
2793 		err = tnc_next(c, &znode, &n);
2794 		if (unlikely(err))
2795 			goto out_unlock;
2796 	} else {
2797 		/*
2798 		 * The full name of the entry was not given, in which case the
2799 		 * behavior of this function is a little different and it
2800 		 * returns current entry, not the next one.
2801 		 */
2802 		if (!err) {
2803 			/*
2804 			 * However, the given key does not exist in the TNC
2805 			 * tree and @znode/@n variables contain the closest
2806 			 * "preceding" element. Switch to the next one.
2807 			 */
2808 			err = tnc_next(c, &znode, &n);
2809 			if (err)
2810 				goto out_unlock;
2811 		}
2812 	}
2813 
2814 	zbr = &znode->zbranch[n];
2815 	dent = kmalloc(zbr->len, GFP_NOFS);
2816 	if (unlikely(!dent)) {
2817 		err = -ENOMEM;
2818 		goto out_unlock;
2819 	}
2820 
2821 	/*
2822 	 * The above 'tnc_next()' call could lead us to the next inode, check
2823 	 * this.
2824 	 */
2825 	dkey = &zbr->key;
2826 	if (key_inum(c, dkey) != key_inum(c, key) ||
2827 	    key_type(c, dkey) != type) {
2828 		err = -ENOENT;
2829 		goto out_free;
2830 	}
2831 
2832 	err = tnc_read_node_nm(c, zbr, dent);
2833 	if (unlikely(err))
2834 		goto out_free;
2835 
2836 	mutex_unlock(&c->tnc_mutex);
2837 	return dent;
2838 
2839 out_free:
2840 	kfree(dent);
2841 out_unlock:
2842 	mutex_unlock(&c->tnc_mutex);
2843 	return ERR_PTR(err);
2844 }
2845 
2846 /**
2847  * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit.
2848  * @c: UBIFS file-system description object
2849  *
2850  * Destroy left-over obsolete znodes from a failed commit.
2851  */
2852 static void tnc_destroy_cnext(struct ubifs_info *c)
2853 {
2854 	struct ubifs_znode *cnext;
2855 
2856 	if (!c->cnext)
2857 		return;
2858 	ubifs_assert(c->cmt_state == COMMIT_BROKEN);
2859 	cnext = c->cnext;
2860 	do {
2861 		struct ubifs_znode *znode = cnext;
2862 
2863 		cnext = cnext->cnext;
2864 		if (test_bit(OBSOLETE_ZNODE, &znode->flags))
2865 			kfree(znode);
2866 	} while (cnext && cnext != c->cnext);
2867 }
2868 
2869 /**
2870  * ubifs_tnc_close - close TNC subsystem and free all related resources.
2871  * @c: UBIFS file-system description object
2872  */
2873 void ubifs_tnc_close(struct ubifs_info *c)
2874 {
2875 	long clean_freed;
2876 
2877 	tnc_destroy_cnext(c);
2878 	if (c->zroot.znode) {
2879 		clean_freed = ubifs_destroy_tnc_subtree(c->zroot.znode);
2880 		atomic_long_sub(clean_freed, &ubifs_clean_zn_cnt);
2881 	}
2882 	kfree(c->gap_lebs);
2883 	kfree(c->ilebs);
2884 	destroy_old_idx(c);
2885 }
2886 
2887 /**
2888  * left_znode - get the znode to the left.
2889  * @c: UBIFS file-system description object
2890  * @znode: znode
2891  *
2892  * This function returns a pointer to the znode to the left of @znode or NULL if
2893  * there is not one. A negative error code is returned on failure.
2894  */
2895 static struct ubifs_znode *left_znode(struct ubifs_info *c,
2896 				      struct ubifs_znode *znode)
2897 {
2898 	int level = znode->level;
2899 
2900 	while (1) {
2901 		int n = znode->iip - 1;
2902 
2903 		/* Go up until we can go left */
2904 		znode = znode->parent;
2905 		if (!znode)
2906 			return NULL;
2907 		if (n >= 0) {
2908 			/* Now go down the rightmost branch to 'level' */
2909 			znode = get_znode(c, znode, n);
2910 			if (IS_ERR(znode))
2911 				return znode;
2912 			while (znode->level != level) {
2913 				n = znode->child_cnt - 1;
2914 				znode = get_znode(c, znode, n);
2915 				if (IS_ERR(znode))
2916 					return znode;
2917 			}
2918 			break;
2919 		}
2920 	}
2921 	return znode;
2922 }
2923 
2924 /**
2925  * right_znode - get the znode to the right.
2926  * @c: UBIFS file-system description object
2927  * @znode: znode
2928  *
2929  * This function returns a pointer to the znode to the right of @znode or NULL
2930  * if there is not one. A negative error code is returned on failure.
2931  */
2932 static struct ubifs_znode *right_znode(struct ubifs_info *c,
2933 				       struct ubifs_znode *znode)
2934 {
2935 	int level = znode->level;
2936 
2937 	while (1) {
2938 		int n = znode->iip + 1;
2939 
2940 		/* Go up until we can go right */
2941 		znode = znode->parent;
2942 		if (!znode)
2943 			return NULL;
2944 		if (n < znode->child_cnt) {
2945 			/* Now go down the leftmost branch to 'level' */
2946 			znode = get_znode(c, znode, n);
2947 			if (IS_ERR(znode))
2948 				return znode;
2949 			while (znode->level != level) {
2950 				znode = get_znode(c, znode, 0);
2951 				if (IS_ERR(znode))
2952 					return znode;
2953 			}
2954 			break;
2955 		}
2956 	}
2957 	return znode;
2958 }
2959 
2960 /**
2961  * lookup_znode - find a particular indexing node from TNC.
2962  * @c: UBIFS file-system description object
2963  * @key: index node key to lookup
2964  * @level: index node level
2965  * @lnum: index node LEB number
2966  * @offs: index node offset
2967  *
2968  * This function searches an indexing node by its first key @key and its
2969  * address @lnum:@offs. It looks up the indexing tree by pulling all indexing
2970  * nodes it traverses to TNC. This function is called for indexing nodes which
2971  * were found on the media by scanning, for example when garbage-collecting or
2972  * when doing in-the-gaps commit. This means that the indexing node which is
2973  * looked for does not have to have exactly the same leftmost key @key, because
2974  * the leftmost key may have been changed, in which case TNC will contain a
2975  * dirty znode which still refers the same @lnum:@offs. This function is clever
2976  * enough to recognize such indexing nodes.
2977  *
2978  * Note, if a znode was deleted or changed too much, then this function will
2979  * not find it. For situations like this UBIFS has the old index RB-tree
2980  * (indexed by @lnum:@offs).
2981  *
2982  * This function returns a pointer to the znode found or %NULL if it is not
2983  * found. A negative error code is returned on failure.
2984  */
2985 static struct ubifs_znode *lookup_znode(struct ubifs_info *c,
2986 					union ubifs_key *key, int level,
2987 					int lnum, int offs)
2988 {
2989 	struct ubifs_znode *znode, *zn;
2990 	int n, nn;
2991 
2992 	ubifs_assert(key_type(c, key) < UBIFS_INVALID_KEY);
2993 
2994 	/*
2995 	 * The arguments have probably been read off flash, so don't assume
2996 	 * they are valid.
2997 	 */
2998 	if (level < 0)
2999 		return ERR_PTR(-EINVAL);
3000 
3001 	/* Get the root znode */
3002 	znode = c->zroot.znode;
3003 	if (!znode) {
3004 		znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
3005 		if (IS_ERR(znode))
3006 			return znode;
3007 	}
3008 	/* Check if it is the one we are looking for */
3009 	if (c->zroot.lnum == lnum && c->zroot.offs == offs)
3010 		return znode;
3011 	/* Descend to the parent level i.e. (level + 1) */
3012 	if (level >= znode->level)
3013 		return NULL;
3014 	while (1) {
3015 		ubifs_search_zbranch(c, znode, key, &n);
3016 		if (n < 0) {
3017 			/*
3018 			 * We reached a znode where the leftmost key is greater
3019 			 * than the key we are searching for. This is the same
3020 			 * situation as the one described in a huge comment at
3021 			 * the end of the 'ubifs_lookup_level0()' function. And
3022 			 * for exactly the same reasons we have to try to look
3023 			 * left before giving up.
3024 			 */
3025 			znode = left_znode(c, znode);
3026 			if (!znode)
3027 				return NULL;
3028 			if (IS_ERR(znode))
3029 				return znode;
3030 			ubifs_search_zbranch(c, znode, key, &n);
3031 			ubifs_assert(n >= 0);
3032 		}
3033 		if (znode->level == level + 1)
3034 			break;
3035 		znode = get_znode(c, znode, n);
3036 		if (IS_ERR(znode))
3037 			return znode;
3038 	}
3039 	/* Check if the child is the one we are looking for */
3040 	if (znode->zbranch[n].lnum == lnum && znode->zbranch[n].offs == offs)
3041 		return get_znode(c, znode, n);
3042 	/* If the key is unique, there is nowhere else to look */
3043 	if (!is_hash_key(c, key))
3044 		return NULL;
3045 	/*
3046 	 * The key is not unique and so may be also in the znodes to either
3047 	 * side.
3048 	 */
3049 	zn = znode;
3050 	nn = n;
3051 	/* Look left */
3052 	while (1) {
3053 		/* Move one branch to the left */
3054 		if (n)
3055 			n -= 1;
3056 		else {
3057 			znode = left_znode(c, znode);
3058 			if (!znode)
3059 				break;
3060 			if (IS_ERR(znode))
3061 				return znode;
3062 			n = znode->child_cnt - 1;
3063 		}
3064 		/* Check it */
3065 		if (znode->zbranch[n].lnum == lnum &&
3066 		    znode->zbranch[n].offs == offs)
3067 			return get_znode(c, znode, n);
3068 		/* Stop if the key is less than the one we are looking for */
3069 		if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)
3070 			break;
3071 	}
3072 	/* Back to the middle */
3073 	znode = zn;
3074 	n = nn;
3075 	/* Look right */
3076 	while (1) {
3077 		/* Move one branch to the right */
3078 		if (++n >= znode->child_cnt) {
3079 			znode = right_znode(c, znode);
3080 			if (!znode)
3081 				break;
3082 			if (IS_ERR(znode))
3083 				return znode;
3084 			n = 0;
3085 		}
3086 		/* Check it */
3087 		if (znode->zbranch[n].lnum == lnum &&
3088 		    znode->zbranch[n].offs == offs)
3089 			return get_znode(c, znode, n);
3090 		/* Stop if the key is greater than the one we are looking for */
3091 		if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)
3092 			break;
3093 	}
3094 	return NULL;
3095 }
3096 
3097 /**
3098  * is_idx_node_in_tnc - determine if an index node is in the TNC.
3099  * @c: UBIFS file-system description object
3100  * @key: key of index node
3101  * @level: index node level
3102  * @lnum: LEB number of index node
3103  * @offs: offset of index node
3104  *
3105  * This function returns %0 if the index node is not referred to in the TNC, %1
3106  * if the index node is referred to in the TNC and the corresponding znode is
3107  * dirty, %2 if an index node is referred to in the TNC and the corresponding
3108  * znode is clean, and a negative error code in case of failure.
3109  *
3110  * Note, the @key argument has to be the key of the first child. Also note,
3111  * this function relies on the fact that 0:0 is never a valid LEB number and
3112  * offset for a main-area node.
3113  */
3114 int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,
3115 		       int lnum, int offs)
3116 {
3117 	struct ubifs_znode *znode;
3118 
3119 	znode = lookup_znode(c, key, level, lnum, offs);
3120 	if (!znode)
3121 		return 0;
3122 	if (IS_ERR(znode))
3123 		return PTR_ERR(znode);
3124 
3125 	return ubifs_zn_dirty(znode) ? 1 : 2;
3126 }
3127 
3128 /**
3129  * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC.
3130  * @c: UBIFS file-system description object
3131  * @key: node key
3132  * @lnum: node LEB number
3133  * @offs: node offset
3134  *
3135  * This function returns %1 if the node is referred to in the TNC, %0 if it is
3136  * not, and a negative error code in case of failure.
3137  *
3138  * Note, this function relies on the fact that 0:0 is never a valid LEB number
3139  * and offset for a main-area node.
3140  */
3141 static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,
3142 			       int lnum, int offs)
3143 {
3144 	struct ubifs_zbranch *zbr;
3145 	struct ubifs_znode *znode, *zn;
3146 	int n, found, err, nn;
3147 	const int unique = !is_hash_key(c, key);
3148 
3149 	found = ubifs_lookup_level0(c, key, &znode, &n);
3150 	if (found < 0)
3151 		return found; /* Error code */
3152 	if (!found)
3153 		return 0;
3154 	zbr = &znode->zbranch[n];
3155 	if (lnum == zbr->lnum && offs == zbr->offs)
3156 		return 1; /* Found it */
3157 	if (unique)
3158 		return 0;
3159 	/*
3160 	 * Because the key is not unique, we have to look left
3161 	 * and right as well
3162 	 */
3163 	zn = znode;
3164 	nn = n;
3165 	/* Look left */
3166 	while (1) {
3167 		err = tnc_prev(c, &znode, &n);
3168 		if (err == -ENOENT)
3169 			break;
3170 		if (err)
3171 			return err;
3172 		if (keys_cmp(c, key, &znode->zbranch[n].key))
3173 			break;
3174 		zbr = &znode->zbranch[n];
3175 		if (lnum == zbr->lnum && offs == zbr->offs)
3176 			return 1; /* Found it */
3177 	}
3178 	/* Look right */
3179 	znode = zn;
3180 	n = nn;
3181 	while (1) {
3182 		err = tnc_next(c, &znode, &n);
3183 		if (err) {
3184 			if (err == -ENOENT)
3185 				return 0;
3186 			return err;
3187 		}
3188 		if (keys_cmp(c, key, &znode->zbranch[n].key))
3189 			break;
3190 		zbr = &znode->zbranch[n];
3191 		if (lnum == zbr->lnum && offs == zbr->offs)
3192 			return 1; /* Found it */
3193 	}
3194 	return 0;
3195 }
3196 
3197 /**
3198  * ubifs_tnc_has_node - determine whether a node is in the TNC.
3199  * @c: UBIFS file-system description object
3200  * @key: node key
3201  * @level: index node level (if it is an index node)
3202  * @lnum: node LEB number
3203  * @offs: node offset
3204  * @is_idx: non-zero if the node is an index node
3205  *
3206  * This function returns %1 if the node is in the TNC, %0 if it is not, and a
3207  * negative error code in case of failure. For index nodes, @key has to be the
3208  * key of the first child. An index node is considered to be in the TNC only if
3209  * the corresponding znode is clean or has not been loaded.
3210  */
3211 int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,
3212 		       int lnum, int offs, int is_idx)
3213 {
3214 	int err;
3215 
3216 	mutex_lock(&c->tnc_mutex);
3217 	if (is_idx) {
3218 		err = is_idx_node_in_tnc(c, key, level, lnum, offs);
3219 		if (err < 0)
3220 			goto out_unlock;
3221 		if (err == 1)
3222 			/* The index node was found but it was dirty */
3223 			err = 0;
3224 		else if (err == 2)
3225 			/* The index node was found and it was clean */
3226 			err = 1;
3227 		else
3228 			BUG_ON(err != 0);
3229 	} else
3230 		err = is_leaf_node_in_tnc(c, key, lnum, offs);
3231 
3232 out_unlock:
3233 	mutex_unlock(&c->tnc_mutex);
3234 	return err;
3235 }
3236 
3237 /**
3238  * ubifs_dirty_idx_node - dirty an index node.
3239  * @c: UBIFS file-system description object
3240  * @key: index node key
3241  * @level: index node level
3242  * @lnum: index node LEB number
3243  * @offs: index node offset
3244  *
3245  * This function loads and dirties an index node so that it can be garbage
3246  * collected. The @key argument has to be the key of the first child. This
3247  * function relies on the fact that 0:0 is never a valid LEB number and offset
3248  * for a main-area node. Returns %0 on success and a negative error code on
3249  * failure.
3250  */
3251 int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,
3252 			 int lnum, int offs)
3253 {
3254 	struct ubifs_znode *znode;
3255 	int err = 0;
3256 
3257 	mutex_lock(&c->tnc_mutex);
3258 	znode = lookup_znode(c, key, level, lnum, offs);
3259 	if (!znode)
3260 		goto out_unlock;
3261 	if (IS_ERR(znode)) {
3262 		err = PTR_ERR(znode);
3263 		goto out_unlock;
3264 	}
3265 	znode = dirty_cow_bottom_up(c, znode);
3266 	if (IS_ERR(znode)) {
3267 		err = PTR_ERR(znode);
3268 		goto out_unlock;
3269 	}
3270 
3271 out_unlock:
3272 	mutex_unlock(&c->tnc_mutex);
3273 	return err;
3274 }
3275 
3276 #ifdef CONFIG_UBIFS_FS_DEBUG
3277 
3278 /**
3279  * dbg_check_inode_size - check if inode size is correct.
3280  * @c: UBIFS file-system description object
3281  * @inum: inode number
3282  * @size: inode size
3283  *
3284  * This function makes sure that the inode size (@size) is correct and it does
3285  * not have any pages beyond @size. Returns zero if the inode is OK, %-EINVAL
3286  * if it has a data page beyond @size, and other negative error code in case of
3287  * other errors.
3288  */
3289 int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode,
3290 			 loff_t size)
3291 {
3292 	int err, n;
3293 	union ubifs_key from_key, to_key, *key;
3294 	struct ubifs_znode *znode;
3295 	unsigned int block;
3296 
3297 	if (!S_ISREG(inode->i_mode))
3298 		return 0;
3299 	if (!(ubifs_chk_flags & UBIFS_CHK_GEN))
3300 		return 0;
3301 
3302 	block = (size + UBIFS_BLOCK_SIZE - 1) >> UBIFS_BLOCK_SHIFT;
3303 	data_key_init(c, &from_key, inode->i_ino, block);
3304 	highest_data_key(c, &to_key, inode->i_ino);
3305 
3306 	mutex_lock(&c->tnc_mutex);
3307 	err = ubifs_lookup_level0(c, &from_key, &znode, &n);
3308 	if (err < 0)
3309 		goto out_unlock;
3310 
3311 	if (err) {
3312 		err = -EINVAL;
3313 		key = &from_key;
3314 		goto out_dump;
3315 	}
3316 
3317 	err = tnc_next(c, &znode, &n);
3318 	if (err == -ENOENT) {
3319 		err = 0;
3320 		goto out_unlock;
3321 	}
3322 	if (err < 0)
3323 		goto out_unlock;
3324 
3325 	ubifs_assert(err == 0);
3326 	key = &znode->zbranch[n].key;
3327 	if (!key_in_range(c, key, &from_key, &to_key))
3328 		goto out_unlock;
3329 
3330 out_dump:
3331 	block = key_block(c, key);
3332 	ubifs_err("inode %lu has size %lld, but there are data at offset %lld "
3333 		  "(data key %s)", (unsigned long)inode->i_ino, size,
3334 		  ((loff_t)block) << UBIFS_BLOCK_SHIFT, DBGKEY(key));
3335 	dbg_dump_inode(c, inode);
3336 	dbg_dump_stack();
3337 	err = -EINVAL;
3338 
3339 out_unlock:
3340 	mutex_unlock(&c->tnc_mutex);
3341 	return err;
3342 }
3343 
3344 #endif /* CONFIG_UBIFS_FS_DEBUG */
3345