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