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
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, fmt: "old idx added twice!");
67	kfree(objp: old_idx);
68	return;
69	}
70	}
71	rb_link_node(node: &old_idx->rb, parent, rb_link: 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	*/
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(size: 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	*/
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, lnum: zbr->lnum, offs: zbr->offs);
127	} else
128	if (c->zroot.len)
129	return insert_old_idx(c, lnum: c->zroot.lnum,
130	offs: 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	*/
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, lnum: zbr->lnum, offs: 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, lnum: c->zroot.lnum, offs: 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	*/
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(objp: 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	*/
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(p: znode, size: c->max_znode_sz, GFP_NOFS);
203	if (unlikely(!zn))
204	return ERR_PTR(error: -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	*/
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, dirty: 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	*/
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(v: &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	*/
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(nr: DIRTY_ZNODE, addr: &znode->flags)) {
280	atomic_long_inc(v: &c->dirty_zn_cnt);
281	atomic_long_dec(v: &c->clean_zn_cnt);
282	atomic_long_dec(v: &ubifs_clean_zn_cnt);
283	err = add_idx_dirt(c, lnum: zbr->lnum, dirt: zbr->len);
284	if (unlikely(err))
285	return ERR_PTR(error: err);
286	}
287	return znode;
288	}
289
290	zn = copy_znode(c, znode);
291	if (IS_ERR(ptr: zn))
292	return zn;
293
294	if (zbr->len) {
295	struct ubifs_old_idx *old_idx;
296
297	old_idx = kmalloc(size: 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, lnum: zbr->lnum, dirt: zbr->len);
306	if (err) {
307	kfree(objp: old_idx);
308	goto out;
309	}
310
311	do_insert_old_idx(c, old_idx);
312	}
313
314	replace_znode(c, new_zn: zn, old_zn: znode, zbr);
315
316	return zn;
317
318	out:
319	kfree(objp: zn);
320	return ERR_PTR(error: 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	*/
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, node: dent, node_len: zbr->len);
358	return err;
359	}
360
361	lnc_node = kmemdup(p: node, size: 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	*/
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, dent: node);
388	if (err) {
389	dump_stack();
390	ubifs_dump_node(c, node, node_len: 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	*/
402	static void lnc_free(struct ubifs_zbranch *zbr)
403	{
404	if (!zbr->leaf)
405	return;
406	kfree(objp: 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	*/
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, key: &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	*/
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, even_ebadmsg: 1);
491	if (err) {
492	ubifs_err(c, fmt: "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, expected: zbr->hash);
516	if (err) {
517	ubifs_bad_hash(c, node: buf, hash: 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	*/
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, buf: node, type: 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, from: &dent->key, to: &node_key);
548	if (keys_cmp(c, key1: key, key2: &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	*/
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(size: zbr->len, GFP_NOFS);
577	if (!dent)
578	return -ENOMEM;
579
580	err = ubifs_tnc_read_node(c, zbr, node: 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, node: 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(p: 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(objp: 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	*/
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, parent: znode, iip: 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	*/
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, n: nn);
660	if (IS_ERR(ptr: znode))
661	return PTR_ERR(ptr: znode);
662	while (znode->level != 0) {
663	znode = get_znode(c, znode, n: 0);
664	if (IS_ERR(ptr: znode))
665	return PTR_ERR(ptr: 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	*/
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, n: nn);
704	if (IS_ERR(ptr: znode))
705	return PTR_ERR(ptr: znode);
706	while (znode->level != 0) {
707	nn = znode->child_cnt - 1;
708	znode = get_znode(c, znode, n: nn);
709	if (IS_ERR(ptr: znode))
710	return PTR_ERR(ptr: 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	*/
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, zbr: &(*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, key1: &(*zn)->zbranch[*n].key, key2: 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, zbr: &(*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, zn: &znode, n: &nn);
820	if (err == -ENOENT)
821	return 0;
822	if (err < 0)
823	return err;
824	if (keys_cmp(c, key1: &znode->zbranch[nn].key, key2: key))
825	return 0;
826	err = matches_name(c, zbr: &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	*/
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(size: zbr->len, GFP_NOFS);
865	if (!dent)
866	return -ENOMEM;
867
868	err = fallible_read_node(c, key: &zbr->key, zbr, node: 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, node: 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(p: 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(objp: 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	*/
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, zbr: &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, key1: &(*zn)->zbranch[*n].key, key2: 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, zbr: &(*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, zn: &znode, n: &nn);
1003	if (err == -ENOENT)
1004	break;
1005	if (err < 0)
1006	return err;
1007	if (keys_cmp(c, key1: &znode->zbranch[nn].key, key2: key))
1008	break;
1009	err = fallible_matches_name(c, zbr: &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	*/
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	*/
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(zbr: &znode->zbranch[nn], lnum, offs))
1081	return 1;
1082
1083	/* Look left */
1084	while (1) {
1085	err = tnc_prev(c, zn: &znode, n: &nn);
1086	if (err == -ENOENT)
1087	break;
1088	if (err < 0)
1089	return err;
1090	if (keys_cmp(c, key1: &znode->zbranch[nn].key, key2: key))
1091	break;
1092	if (matches_position(zbr: &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, zn: &znode, n: &nn);
1104	if (err == -ENOENT)
1105	return 0;
1106	if (err < 0)
1107	return err;
1108	if (keys_cmp(c, key1: &znode->zbranch[nn].key, key2: key))
1109	return 0;
1110	*zn = znode;
1111	*n = nn;
1112	if (matches_position(zbr: &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	*/
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(objp: c->bottom_up_buf);
1137	c->bottom_up_buf = kmalloc_array(n: c->zroot.znode->level,
1138	size: sizeof(int),
1139	GFP_NOFS);
1140	if (!c->bottom_up_buf)
1141	return ERR_PTR(error: -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, zbr: &c->zroot);
1174	}
1175	if (IS_ERR(ptr: 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	*/
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, zbr: &c->zroot, NULL, iip: 0);
1220	if (IS_ERR(ptr: znode))
1221	return PTR_ERR(ptr: 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, parent: znode, iip: *n);
1246	if (IS_ERR(ptr: znode))
1247	return PTR_ERR(ptr: 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, zn: &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, key1: key, key2: &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	*/
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, zbr: &c->zroot, NULL, iip: 0);
1355	if (IS_ERR(ptr: znode))
1356	return PTR_ERR(ptr: znode);
1357	}
1358
1359	znode = dirty_cow_znode(c, zbr: &c->zroot);
1360	if (IS_ERR(ptr: znode))
1361	return PTR_ERR(ptr: 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(ptr: znode))
1381	return PTR_ERR(ptr: znode);
1382	continue;
1383	}
1384
1385	/* znode is not in TNC cache, load it from the media */
1386	znode = ubifs_load_znode(c, zbr, parent: znode, iip: *n);
1387	if (IS_ERR(ptr: znode))
1388	return PTR_ERR(ptr: znode);
1389	znode = dirty_cow_znode(c, zbr);
1390	if (IS_ERR(ptr: znode))
1391	return PTR_ERR(ptr: 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, zn: &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, key1: key, key2: &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(ptr: znode))
1421	return PTR_ERR(ptr: 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	*/
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	*/
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, zn: &znode, n: &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, zbr: zt, node);
1506	goto out;
1507	}
1508	if (safely) {
1509	err = ubifs_tnc_read_node(c, zbr: 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(lock: &c->tnc_mutex);
1516
1517	if (ubifs_get_wbuf(c, lnum: zbr.lnum)) {
1518	/* We do not GC journal heads */
1519	err = ubifs_tnc_read_node(c, zbr: &zbr, node);
1520	return err;
1521	}
1522
1523	err = fallible_read_node(c, key, zbr: &zbr, node);
1524	if (err <= 0 || maybe_leb_gced(c, lnum: 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(lock: &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	*/
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, key: &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, key: &bu->key, zn: &znode, n: &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, zn: &znode, n: &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, k: key) != key_inum(c, k: &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(lock: &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, key: &bu->key) + bu->blk_cnt;
1665	block &= ~(UBIFS_BLOCKS_PER_PAGE - 1);
1666	while (bu->cnt) {
1667	if (key_block(c, key: &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	*/
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(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(lock: &wbuf->lock);
1700	return ubifs_leb_read(c, lnum, buf, offs, len, even_ebadmsg: 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(lock: &wbuf->lock);
1711
1712	if (rlen > 0)
1713	/* Read everything that goes before write-buffer */
1714	return ubifs_leb_read(c, lnum, buf, offs, len: rlen, even_ebadmsg: 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	*/
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, fmt: "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, len: zbr->len, lnum: zbr->lnum, offs: zbr->offs, quiet: 0, must_chk_crc: 0);
1741	if (err) {
1742	ubifs_err(c, fmt: "expected node type %d", UBIFS_DATA_NODE);
1743	goto out;
1744	}
1745
1746	err = ubifs_node_check_hash(c, buf, expected: zbr->hash);
1747	if (err) {
1748	ubifs_bad_hash(c, node: buf, hash: zbr->hash, lnum: zbr->lnum, offs: zbr->offs);
1749	return err;
1750	}
1751
1752	len = le32_to_cpu(ch->len);
1753	if (len != zbr->len) {
1754	ubifs_err(c, fmt: "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, from: buf + UBIFS_KEY_OFFSET, to: &key1);
1760	if (!keys_eq(c, key1: &zbr->key, key2: &key1)) {
1761	ubifs_err(c, fmt: "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, fmt: "bad node at LEB %d:%d", zbr->lnum, zbr->offs);
1774	ubifs_dump_node(c, node: buf, node_len: 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	*/
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, fmt: "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, buf: bu->buf, len, lnum, offs);
1806	else
1807	err = ubifs_leb_read(c, lnum, buf: bu->buf, offs, len, even_ebadmsg: 0);
1808
1809	/* Check for a race with GC */
1810	if (maybe_leb_gced(c, lnum, gc_seq1: bu->gc_seq))
1811	return -EAGAIN;
1812
1813	if (err && err != -EBADMSG) {
1814	ubifs_err(c, fmt: "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, zbr: &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	*/
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, zn: &znode, n: &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, zn: &znode, n: &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, zbr: &znode->zbranch[n], node);
1875
1876	out_unlock:
1877	mutex_unlock(lock: &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	*/
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(p: dent->name, fname_name(nm), size: 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
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, zn: &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, k: dkey) != key_inum(c, k: key) ||
1940	key_type(c, key: dkey) != key_type(c, key)) {
1941	return -ENOENT;
1942	}
1943
1944	err = tnc_read_hashed_node(c, zbr, node: dent);
1945	if (err)
1946	return err;
1947
1948	if (key_hash(c, key) == key_hash(c, key: dkey) &&
1949	le32_to_cpu(dent->cookie) == cookie) {
1950	*zn = znode;
1951	return 0;
1952	}
1953
1954	err = tnc_next(c, zn: &znode, n);
1955	if (err)
1956	return err;
1957	}
1958	}
1959
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, key: &start_key, inum: key_inum(c, k: key));
1970
1971	mutex_lock(&c->tnc_mutex);
1972	err = ubifs_lookup_level0(c, key: &start_key, zn: &znode, n: &n);
1973	if (unlikely(err < 0))
1974	goto out_unlock;
1975
1976	err = search_dh_cookie(c, key, dent, cookie, zn: &znode, n: &n, exact: err);
1977
1978	out_unlock:
1979	mutex_unlock(lock: &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	*/
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, dent: 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	*/
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, key1: key, key2: key1) < 0) {
2045	key_copy(c, from: key, to: 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	*/
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	*/
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(size: 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, k: key1) == key_inum(c, k: key) &&
2168	key_type(c, key: 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, k: key1) == key_inum(c, k: key) &&
2179	key_type(c, key: key1) == UBIFS_DATA_KEY) {
2180	key1 = &znode->zbranch[n].key;
2181	if (key_inum(c, k: key1) != key_inum(c, k: key) ||
2182	key_type(c, key: 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(v: &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, znode: 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(size: 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(v: &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	*/
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, zn: &znode, n: &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, from: hash, to: zbr.hash);
2328	key_copy(c, from: key, to: &zbr.key);
2329	err = tnc_insert(c, znode, zbr: &zbr, n: 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, lnum: zbr->lnum, dirty: zbr->len);
2335	zbr->lnum = lnum;
2336	zbr->offs = offs;
2337	zbr->len = len;
2338	ubifs_copy_hash(c, from: hash, to: zbr->hash);
2339	} else
2340	err = found;
2341	if (!err)
2342	err = dbg_check_tnc(c, extra: 0);
2343	mutex_unlock(lock: &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	*/
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, zn: &znode, n: &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, lnum: zbr->lnum, dirty: 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, zn: &znode, n: &n,
2392	lnum: old_lnum, offs: 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(ptr: znode)) {
2405	err = PTR_ERR(ptr: znode);
2406	goto out_unlock;
2407	}
2408	}
2409	zbr = &znode->zbranch[n];
2410	lnc_free(zbr);
2411	err = ubifs_add_dirt(c, lnum: zbr->lnum,
2412	dirty: 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, dirty: len);
2424
2425	if (!err)
2426	err = dbg_check_tnc(c, extra: 0);
2427
2428	out_unlock:
2429	mutex_unlock(lock: &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	*/
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, zn: &znode, n: &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, zn: &znode, n: &n,
2464	nm, adding: 1);
2465	else
2466	found = resolve_collision(c, key, zn: &znode, n: &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(ptr: znode)) {
2477	err = PTR_ERR(ptr: 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, lnum: zbr->lnum, dirty: zbr->len);
2487	zbr->lnum = lnum;
2488	zbr->offs = offs;
2489	zbr->len = len;
2490	ubifs_copy_hash(c, from: hash, to: 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, from: hash, to: zbr.hash);
2503	key_copy(c, from: key, to: &zbr.key);
2504	err = tnc_insert(c, znode, zbr: &zbr, n: 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, extra: 0);
2517	mutex_unlock(lock: &c->tnc_mutex);
2518	if (err)
2519	return err;
2520	return ubifs_tnc_remove_nm(c, key, nm: &noname);
2521	}
2522	}
2523
2524	out_unlock:
2525	if (!err)
2526	err = dbg_check_tnc(c, extra: 0);
2527	mutex_unlock(lock: &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	*/
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, lnum: zbr->lnum, dirty: 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(v: &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(v: &c->clean_zn_cnt);
2589	atomic_long_inc(v: &ubifs_clean_zn_cnt);
2590	} else
2591	kfree(objp: 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, n: 0);
2613	if (IS_ERR(ptr: znode))
2614	return PTR_ERR(ptr: znode);
2615	znode = dirty_cow_znode(c, zbr);
2616	if (IS_ERR(ptr: znode))
2617	return PTR_ERR(ptr: znode);
2618	znode->parent = NULL;
2619	znode->iip = 0;
2620	if (c->zroot.len) {
2621	err = insert_old_idx(c, lnum: c->zroot.lnum,
2622	offs: 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(v: &c->dirty_zn_cnt);
2633
2634	if (zp->cnext) {
2635	__set_bit(OBSOLETE_ZNODE, &zp->flags);
2636	atomic_long_inc(v: &c->clean_zn_cnt);
2637	atomic_long_inc(v: &ubifs_clean_zn_cnt);
2638	} else
2639	kfree(objp: 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	*/
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, zn: &znode, n: &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, extra: 0);
2669
2670	out_unlock:
2671	mutex_unlock(lock: &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	*/
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, zn: &znode, n: &n);
2692	if (err < 0)
2693	goto out_unlock;
2694
2695	if (err) {
2696	if (c->replaying)
2697	err = fallible_resolve_collision(c, key, zn: &znode, n: &n,
2698	nm, adding: 0);
2699	else
2700	err = resolve_collision(c, key, zn: &znode, n: &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(ptr: znode)) {
2709	err = PTR_ERR(ptr: 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, extra: 0);
2720	mutex_unlock(lock: &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	*/
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, zn: &znode, n: &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, node: 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, key: &start_key, inum: key_inum(c, k: key));
2764
2765	err = ubifs_lookup_level0(c, key: &start_key, zn: &znode, n: &n);
2766	if (unlikely(err < 0))
2767	goto out_free;
2768
2769	err = search_dh_cookie(c, key, dent, cookie, zn: &znode, n: &n, exact: 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(ptr: znode)) {
2777	err = PTR_ERR(ptr: znode);
2778	goto out_free;
2779	}
2780	}
2781	err = tnc_delete(c, znode, n);
2782
2783	out_free:
2784	kfree(objp: dent);
2785	out_unlock:
2786	if (!err)
2787	err = dbg_check_tnc(c, extra: 0);
2788	mutex_unlock(lock: &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	*/
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, key1: key, key2: from_key) < 0)
2805	return 0;
2806	if (keys_cmp(c, key1: key, key2: 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	*/
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, key: from_key, zn: &znode, n: &n);
2832	if (err < 0)
2833	goto out_unlock;
2834
2835	if (err)
2836	key = from_key;
2837	else {
2838	err = tnc_next(c, zn: &znode, n: &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(ptr: znode)) {
2856	err = PTR_ERR(ptr: 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(zbr: &znode->zbranch[i]);
2867	err = ubifs_add_dirt(c, lnum: znode->zbranch[i].lnum,
2868	dirty: 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, extra: 0);
2890	mutex_unlock(lock: &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	*/
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, key: &key1, inum);
2916	while (1) {
2917	ino_t xattr_inum;
2918	int err;
2919
2920	xent = ubifs_tnc_next_ent(c, key: &key1, nm: &nm);
2921	if (IS_ERR(ptr: xent)) {
2922	err = PTR_ERR(ptr: xent);
2923	if (err == -ENOENT)
2924	break;
2925	kfree(objp: 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, key: &key1, nm: &nm);
2938	if (err) {
2939	kfree(objp: pxent);
2940	kfree(objp: xent);
2941	return err;
2942	}
2943
2944	lowest_ino_key(c, key: &key1, inum: xattr_inum);
2945	highest_ino_key(c, key: &key2, inum: xattr_inum);
2946	err = ubifs_tnc_remove_range(c, from_key: &key1, to_key: &key2);
2947	if (err) {
2948	kfree(objp: pxent);
2949	kfree(objp: xent);
2950	return err;
2951	}
2952
2953	kfree(objp: pxent);
2954	pxent = xent;
2955	key_read(c, from: &xent->key, to: &key1);
2956	}
2957
2958	kfree(objp: pxent);
2959	lowest_ino_key(c, key: &key1, inum);
2960	highest_ino_key(c, key: &key2, inum);
2961
2962	return ubifs_tnc_remove_range(c, from_key: &key1, to_key: &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	*/
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, zn: &znode, n: &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, zn: &znode, n: &n,
3011	nm, adding: 0);
3012	else
3013	err = resolve_collision(c, key, zn: &znode, n: &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, zn: &znode, n: &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, zn: &znode, n: &n);
3037	if (err)
3038	goto out_unlock;
3039	}
3040	}
3041
3042	zbr = &znode->zbranch[n];
3043	dent = kmalloc(size: 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, k: dkey) != key_inum(c, k: key) ||
3055	key_type(c, key: dkey) != type) {
3056	err = -ENOENT;
3057	goto out_free;
3058	}
3059
3060	err = tnc_read_hashed_node(c, zbr, node: dent);
3061	if (unlikely(err))
3062	goto out_free;
3063
3064	mutex_unlock(lock: &c->tnc_mutex);
3065	return dent;
3066
3067	out_free:
3068	kfree(objp: dent);
3069	out_unlock:
3070	mutex_unlock(lock: &c->tnc_mutex);
3071	return ERR_PTR(error: 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	*/
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(objp: 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(v: &c->clean_zn_cnt);
3107	atomic_long_inc(v: &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	*/
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(v: &c->clean_zn_cnt);
3123	freed = ubifs_destroy_tnc_subtree(c, zr: c->zroot.znode);
3124	ubifs_assert(c, freed == n);
3125	atomic_long_sub(i: n, v: &ubifs_clean_zn_cnt);
3126	}
3127	kfree(objp: c->gap_lebs);
3128	kfree(objp: 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	*/
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(ptr: 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(ptr: 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	*/
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(ptr: znode))
3193	return znode;
3194	while (znode->level != level) {
3195	znode = get_znode(c, znode, n: 0);
3196	if (IS_ERR(ptr: 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	*/
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(error: -EINVAL);
3245
3246	/* Get the root znode */
3247	znode = c->zroot.znode;
3248	if (!znode) {
3249	znode = ubifs_load_znode(c, zbr: &c->zroot, NULL, iip: 0);
3250	if (IS_ERR(ptr: 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: &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(ptr: znode))
3274	return znode;
3275	ubifs_search_zbranch(c, znode, key, n: &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(ptr: 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(ptr: 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, key1: &znode->zbranch[n].key, key2: 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(ptr: 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, key1: &znode->zbranch[n].key, key2: 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	*/
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(ptr: znode))
3368	return PTR_ERR(ptr: 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	*/
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, zn: &znode, n: &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, zn: &znode, n: &n);
3413	if (err == -ENOENT)
3414	break;
3415	if (err)
3416	return err;
3417	if (keys_cmp(c, key1: key, key2: &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, zn: &znode, n: &n);
3428	if (err) {
3429	if (err == -ENOENT)
3430	return 0;
3431	return err;
3432	}
3433	if (keys_cmp(c, key1: key, key2: &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	*/
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(lock: &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	*/
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(ptr: znode)) {
3507	err = PTR_ERR(ptr: znode);
3508	goto out_unlock;
3509	}
3510	znode = dirty_cow_bottom_up(c, znode);
3511	if (IS_ERR(ptr: znode)) {
3512	err = PTR_ERR(ptr: znode);
3513	goto out_unlock;
3514	}
3515
3516	out_unlock:
3517	mutex_unlock(lock: &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	*/
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, key: &from_key, inum: inode->i_ino, block);
3547	highest_data_key(c, key: &to_key, inum: inode->i_ino);
3548
3549	mutex_lock(&c->tnc_mutex);
3550	err = ubifs_lookup_level0(c, key: &from_key, zn: &znode, n: &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, zn: &znode, n: &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: &from_key, to_key: &to_key))
3570	goto out_unlock;
3571
3572	out_dump:
3573	block = key_block(c, key);
3574	ubifs_err(c, fmt: "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(lock: &c->tnc_mutex);
3578	ubifs_dump_inode(c, inode);
3579	dump_stack();
3580	return -EINVAL;
3581
3582	out_unlock:
3583	mutex_unlock(lock: &c->tnc_mutex);
3584	return err;
3585	}
3586