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