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