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