~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/ubifs/tnc.c

Version: ~ [ linux-5.12-rc1 ] ~ [ linux-5.11.2 ] ~ [ linux-5.10.19 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.101 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.177 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.222 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.258 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.258 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.18.140 ] ~ [ linux-3.16.85 ] ~ [ linux-3.14.79 ] ~ [ linux-3.12.74 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp