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