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