blob: f7e36f5455275e3e125b551b49b32448dd6f9188 [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
Artem Bityutskiy6c0c42c2008-11-18 20:20:05 +02001504 * consecutively in the same LEB. This function returns zero in case of success
1505 * and a negative error code in case of failure.
1506 *
1507 * Note, if the bulk-read buffer length (@bu->buf_len) is known, this function
1508 * makes sure bulk-read nodes fit the buffer. Otherwise, this function prepares
1509 * maxumum possible amount of nodes for bulk-read.
Adrian Hunter4793e7c2008-09-02 16:29:46 +03001510 */
1511int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu)
1512{
1513 int n, err = 0, lnum = -1, uninitialized_var(offs);
1514 int uninitialized_var(len);
1515 unsigned int block = key_block(c, &bu->key);
1516 struct ubifs_znode *znode;
1517
1518 bu->cnt = 0;
1519 bu->blk_cnt = 0;
1520 bu->eof = 0;
1521
1522 mutex_lock(&c->tnc_mutex);
1523 /* Find first key */
1524 err = ubifs_lookup_level0(c, &bu->key, &znode, &n);
1525 if (err < 0)
1526 goto out;
1527 if (err) {
1528 /* Key found */
1529 len = znode->zbranch[n].len;
1530 /* The buffer must be big enough for at least 1 node */
1531 if (len > bu->buf_len) {
1532 err = -EINVAL;
1533 goto out;
1534 }
1535 /* Add this key */
1536 bu->zbranch[bu->cnt++] = znode->zbranch[n];
1537 bu->blk_cnt += 1;
1538 lnum = znode->zbranch[n].lnum;
1539 offs = ALIGN(znode->zbranch[n].offs + len, 8);
1540 }
1541 while (1) {
1542 struct ubifs_zbranch *zbr;
1543 union ubifs_key *key;
1544 unsigned int next_block;
1545
1546 /* Find next key */
1547 err = tnc_next(c, &znode, &n);
1548 if (err)
1549 goto out;
1550 zbr = &znode->zbranch[n];
1551 key = &zbr->key;
1552 /* See if there is another data key for this file */
1553 if (key_inum(c, key) != key_inum(c, &bu->key) ||
1554 key_type(c, key) != UBIFS_DATA_KEY) {
1555 err = -ENOENT;
1556 goto out;
1557 }
1558 if (lnum < 0) {
1559 /* First key found */
1560 lnum = zbr->lnum;
1561 offs = ALIGN(zbr->offs + zbr->len, 8);
1562 len = zbr->len;
1563 if (len > bu->buf_len) {
1564 err = -EINVAL;
1565 goto out;
1566 }
1567 } else {
1568 /*
1569 * The data nodes must be in consecutive positions in
1570 * the same LEB.
1571 */
1572 if (zbr->lnum != lnum || zbr->offs != offs)
1573 goto out;
1574 offs += ALIGN(zbr->len, 8);
1575 len = ALIGN(len, 8) + zbr->len;
1576 /* Must not exceed buffer length */
1577 if (len > bu->buf_len)
1578 goto out;
1579 }
1580 /* Allow for holes */
1581 next_block = key_block(c, key);
1582 bu->blk_cnt += (next_block - block - 1);
1583 if (bu->blk_cnt >= UBIFS_MAX_BULK_READ)
1584 goto out;
1585 block = next_block;
1586 /* Add this key */
1587 bu->zbranch[bu->cnt++] = *zbr;
1588 bu->blk_cnt += 1;
1589 /* See if we have room for more */
1590 if (bu->cnt >= UBIFS_MAX_BULK_READ)
1591 goto out;
1592 if (bu->blk_cnt >= UBIFS_MAX_BULK_READ)
1593 goto out;
1594 }
1595out:
1596 if (err == -ENOENT) {
1597 bu->eof = 1;
1598 err = 0;
1599 }
1600 bu->gc_seq = c->gc_seq;
1601 mutex_unlock(&c->tnc_mutex);
1602 if (err)
1603 return err;
1604 /*
1605 * An enormous hole could cause bulk-read to encompass too many
1606 * page cache pages, so limit the number here.
1607 */
Adrian Hunter63c300b2008-09-17 12:11:13 +03001608 if (bu->blk_cnt > UBIFS_MAX_BULK_READ)
Adrian Hunter4793e7c2008-09-02 16:29:46 +03001609 bu->blk_cnt = UBIFS_MAX_BULK_READ;
1610 /*
1611 * Ensure that bulk-read covers a whole number of page cache
1612 * pages.
1613 */
1614 if (UBIFS_BLOCKS_PER_PAGE == 1 ||
1615 !(bu->blk_cnt & (UBIFS_BLOCKS_PER_PAGE - 1)))
1616 return 0;
1617 if (bu->eof) {
1618 /* At the end of file we can round up */
1619 bu->blk_cnt += UBIFS_BLOCKS_PER_PAGE - 1;
1620 return 0;
1621 }
1622 /* Exclude data nodes that do not make up a whole page cache page */
1623 block = key_block(c, &bu->key) + bu->blk_cnt;
1624 block &= ~(UBIFS_BLOCKS_PER_PAGE - 1);
1625 while (bu->cnt) {
1626 if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block)
1627 break;
1628 bu->cnt -= 1;
1629 }
1630 return 0;
1631}
1632
1633/**
1634 * read_wbuf - bulk-read from a LEB with a wbuf.
1635 * @wbuf: wbuf that may overlap the read
1636 * @buf: buffer into which to read
1637 * @len: read length
1638 * @lnum: LEB number from which to read
1639 * @offs: offset from which to read
1640 *
1641 * This functions returns %0 on success or a negative error code on failure.
1642 */
1643static int read_wbuf(struct ubifs_wbuf *wbuf, void *buf, int len, int lnum,
1644 int offs)
1645{
1646 const struct ubifs_info *c = wbuf->c;
1647 int rlen, overlap;
1648
1649 dbg_io("LEB %d:%d, length %d", lnum, offs, len);
1650 ubifs_assert(wbuf && lnum >= 0 && lnum < c->leb_cnt && offs >= 0);
1651 ubifs_assert(!(offs & 7) && offs < c->leb_size);
1652 ubifs_assert(offs + len <= c->leb_size);
1653
1654 spin_lock(&wbuf->lock);
1655 overlap = (lnum == wbuf->lnum && offs + len > wbuf->offs);
1656 if (!overlap) {
1657 /* We may safely unlock the write-buffer and read the data */
1658 spin_unlock(&wbuf->lock);
1659 return ubi_read(c->ubi, lnum, buf, offs, len);
1660 }
1661
1662 /* Don't read under wbuf */
1663 rlen = wbuf->offs - offs;
1664 if (rlen < 0)
1665 rlen = 0;
1666
1667 /* Copy the rest from the write-buffer */
1668 memcpy(buf + rlen, wbuf->buf + offs + rlen - wbuf->offs, len - rlen);
1669 spin_unlock(&wbuf->lock);
1670
1671 if (rlen > 0)
1672 /* Read everything that goes before write-buffer */
1673 return ubi_read(c->ubi, lnum, buf, offs, rlen);
1674
1675 return 0;
1676}
1677
1678/**
1679 * validate_data_node - validate data nodes for bulk-read.
1680 * @c: UBIFS file-system description object
1681 * @buf: buffer containing data node to validate
1682 * @zbr: zbranch of data node to validate
1683 *
1684 * This functions returns %0 on success or a negative error code on failure.
1685 */
1686static int validate_data_node(struct ubifs_info *c, void *buf,
1687 struct ubifs_zbranch *zbr)
1688{
1689 union ubifs_key key1;
1690 struct ubifs_ch *ch = buf;
1691 int err, len;
1692
1693 if (ch->node_type != UBIFS_DATA_NODE) {
1694 ubifs_err("bad node type (%d but expected %d)",
1695 ch->node_type, UBIFS_DATA_NODE);
1696 goto out_err;
1697 }
1698
Adrian Hunter2953e732008-09-04 16:26:00 +03001699 err = ubifs_check_node(c, buf, zbr->lnum, zbr->offs, 0, 0);
Adrian Hunter4793e7c2008-09-02 16:29:46 +03001700 if (err) {
1701 ubifs_err("expected node type %d", UBIFS_DATA_NODE);
1702 goto out;
1703 }
1704
1705 len = le32_to_cpu(ch->len);
1706 if (len != zbr->len) {
1707 ubifs_err("bad node length %d, expected %d", len, zbr->len);
1708 goto out_err;
1709 }
1710
1711 /* Make sure the key of the read node is correct */
1712 key_read(c, buf + UBIFS_KEY_OFFSET, &key1);
1713 if (!keys_eq(c, &zbr->key, &key1)) {
1714 ubifs_err("bad key in node at LEB %d:%d",
1715 zbr->lnum, zbr->offs);
1716 dbg_tnc("looked for key %s found node's key %s",
1717 DBGKEY(&zbr->key), DBGKEY1(&key1));
1718 goto out_err;
1719 }
1720
1721 return 0;
1722
1723out_err:
1724 err = -EINVAL;
1725out:
1726 ubifs_err("bad node at LEB %d:%d", zbr->lnum, zbr->offs);
1727 dbg_dump_node(c, buf);
1728 dbg_dump_stack();
1729 return err;
1730}
1731
1732/**
1733 * ubifs_tnc_bulk_read - read a number of data nodes in one go.
1734 * @c: UBIFS file-system description object
1735 * @bu: bulk-read parameters and results
1736 *
1737 * This functions reads and validates the data nodes that were identified by the
1738 * 'ubifs_tnc_get_bu_keys()' function. This functions returns %0 on success,
1739 * -EAGAIN to indicate a race with GC, or another negative error code on
1740 * failure.
1741 */
1742int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu)
1743{
1744 int lnum = bu->zbranch[0].lnum, offs = bu->zbranch[0].offs, len, err, i;
1745 struct ubifs_wbuf *wbuf;
1746 void *buf;
1747
1748 len = bu->zbranch[bu->cnt - 1].offs;
1749 len += bu->zbranch[bu->cnt - 1].len - offs;
1750 if (len > bu->buf_len) {
1751 ubifs_err("buffer too small %d vs %d", bu->buf_len, len);
1752 return -EINVAL;
1753 }
1754
1755 /* Do the read */
1756 wbuf = ubifs_get_wbuf(c, lnum);
1757 if (wbuf)
1758 err = read_wbuf(wbuf, bu->buf, len, lnum, offs);
1759 else
1760 err = ubi_read(c->ubi, lnum, bu->buf, offs, len);
1761
1762 /* Check for a race with GC */
1763 if (maybe_leb_gced(c, lnum, bu->gc_seq))
1764 return -EAGAIN;
1765
1766 if (err && err != -EBADMSG) {
1767 ubifs_err("failed to read from LEB %d:%d, error %d",
1768 lnum, offs, err);
1769 dbg_dump_stack();
1770 dbg_tnc("key %s", DBGKEY(&bu->key));
1771 return err;
1772 }
1773
1774 /* Validate the nodes read */
1775 buf = bu->buf;
1776 for (i = 0; i < bu->cnt; i++) {
1777 err = validate_data_node(c, buf, &bu->zbranch[i]);
1778 if (err)
1779 return err;
1780 buf = buf + ALIGN(bu->zbranch[i].len, 8);
1781 }
1782
1783 return 0;
1784}
1785
1786/**
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001787 * do_lookup_nm- look up a "hashed" node.
1788 * @c: UBIFS file-system description object
1789 * @key: node key to lookup
1790 * @node: the node is returned here
1791 * @nm: node name
1792 *
1793 * This function look up and reads a node which contains name hash in the key.
1794 * Since the hash may have collisions, there may be many nodes with the same
1795 * key, so we have to sequentially look to all of them until the needed one is
1796 * found. This function returns zero in case of success, %-ENOENT if the node
1797 * was not found, and a negative error code in case of failure.
1798 */
1799static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1800 void *node, const struct qstr *nm)
1801{
1802 int found, n, err;
1803 struct ubifs_znode *znode;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001804
1805 dbg_tnc("name '%.*s' key %s", nm->len, nm->name, DBGKEY(key));
1806 mutex_lock(&c->tnc_mutex);
1807 found = ubifs_lookup_level0(c, key, &znode, &n);
1808 if (!found) {
1809 err = -ENOENT;
1810 goto out_unlock;
1811 } else if (found < 0) {
1812 err = found;
1813 goto out_unlock;
1814 }
1815
1816 ubifs_assert(n >= 0);
1817
1818 err = resolve_collision(c, key, &znode, &n, nm);
1819 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
1820 if (unlikely(err < 0))
1821 goto out_unlock;
1822 if (err == 0) {
1823 err = -ENOENT;
1824 goto out_unlock;
1825 }
1826
Adrian Hunter761e29f2008-08-20 16:32:40 +03001827 err = tnc_read_node_nm(c, &znode->zbranch[n], node);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001828
1829out_unlock:
1830 mutex_unlock(&c->tnc_mutex);
1831 return err;
1832}
1833
1834/**
1835 * ubifs_tnc_lookup_nm - look up a "hashed" node.
1836 * @c: UBIFS file-system description object
1837 * @key: node key to lookup
1838 * @node: the node is returned here
1839 * @nm: node name
1840 *
1841 * This function look up and reads a node which contains name hash in the key.
1842 * Since the hash may have collisions, there may be many nodes with the same
1843 * key, so we have to sequentially look to all of them until the needed one is
1844 * found. This function returns zero in case of success, %-ENOENT if the node
1845 * was not found, and a negative error code in case of failure.
1846 */
1847int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key,
1848 void *node, const struct qstr *nm)
1849{
1850 int err, len;
1851 const struct ubifs_dent_node *dent = node;
1852
1853 /*
1854 * We assume that in most of the cases there are no name collisions and
1855 * 'ubifs_tnc_lookup()' returns us the right direntry.
1856 */
1857 err = ubifs_tnc_lookup(c, key, node);
1858 if (err)
1859 return err;
1860
1861 len = le16_to_cpu(dent->nlen);
1862 if (nm->len == len && !memcmp(dent->name, nm->name, len))
1863 return 0;
1864
1865 /*
1866 * Unluckily, there are hash collisions and we have to iterate over
1867 * them look at each direntry with colliding name hash sequentially.
1868 */
1869 return do_lookup_nm(c, key, node, nm);
1870}
1871
1872/**
1873 * correct_parent_keys - correct parent znodes' keys.
1874 * @c: UBIFS file-system description object
1875 * @znode: znode to correct parent znodes for
1876 *
1877 * This is a helper function for 'tnc_insert()'. When the key of the leftmost
1878 * zbranch changes, keys of parent znodes have to be corrected. This helper
1879 * function is called in such situations and corrects the keys if needed.
1880 */
1881static void correct_parent_keys(const struct ubifs_info *c,
1882 struct ubifs_znode *znode)
1883{
1884 union ubifs_key *key, *key1;
1885
1886 ubifs_assert(znode->parent);
1887 ubifs_assert(znode->iip == 0);
1888
1889 key = &znode->zbranch[0].key;
1890 key1 = &znode->parent->zbranch[0].key;
1891
1892 while (keys_cmp(c, key, key1) < 0) {
1893 key_copy(c, key, key1);
1894 znode = znode->parent;
1895 znode->alt = 1;
1896 if (!znode->parent || znode->iip)
1897 break;
1898 key1 = &znode->parent->zbranch[0].key;
1899 }
1900}
1901
1902/**
1903 * insert_zbranch - insert a zbranch into a znode.
1904 * @znode: znode into which to insert
1905 * @zbr: zbranch to insert
1906 * @n: slot number to insert to
1907 *
1908 * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in
1909 * znode's array of zbranches and keeps zbranches consolidated, so when a new
1910 * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th
1911 * slot, zbranches starting from @n have to be moved right.
1912 */
1913static void insert_zbranch(struct ubifs_znode *znode,
1914 const struct ubifs_zbranch *zbr, int n)
1915{
1916 int i;
1917
1918 ubifs_assert(ubifs_zn_dirty(znode));
1919
1920 if (znode->level) {
1921 for (i = znode->child_cnt; i > n; i--) {
1922 znode->zbranch[i] = znode->zbranch[i - 1];
1923 if (znode->zbranch[i].znode)
1924 znode->zbranch[i].znode->iip = i;
1925 }
1926 if (zbr->znode)
1927 zbr->znode->iip = n;
1928 } else
1929 for (i = znode->child_cnt; i > n; i--)
1930 znode->zbranch[i] = znode->zbranch[i - 1];
1931
1932 znode->zbranch[n] = *zbr;
1933 znode->child_cnt += 1;
1934
1935 /*
1936 * After inserting at slot zero, the lower bound of the key range of
1937 * this znode may have changed. If this znode is subsequently split
1938 * then the upper bound of the key range may change, and furthermore
1939 * it could change to be lower than the original lower bound. If that
1940 * happens, then it will no longer be possible to find this znode in the
1941 * TNC using the key from the index node on flash. That is bad because
1942 * if it is not found, we will assume it is obsolete and may overwrite
1943 * it. Then if there is an unclean unmount, we will start using the
1944 * old index which will be broken.
1945 *
1946 * So we first mark znodes that have insertions at slot zero, and then
1947 * if they are split we add their lnum/offs to the old_idx tree.
1948 */
1949 if (n == 0)
1950 znode->alt = 1;
1951}
1952
1953/**
1954 * tnc_insert - insert a node into TNC.
1955 * @c: UBIFS file-system description object
1956 * @znode: znode to insert into
1957 * @zbr: branch to insert
1958 * @n: slot number to insert new zbranch to
1959 *
1960 * This function inserts a new node described by @zbr into znode @znode. If
1961 * znode does not have a free slot for new zbranch, it is split. Parent znodes
1962 * are splat as well if needed. Returns zero in case of success or a negative
1963 * error code in case of failure.
1964 */
1965static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode,
1966 struct ubifs_zbranch *zbr, int n)
1967{
1968 struct ubifs_znode *zn, *zi, *zp;
1969 int i, keep, move, appending = 0;
Adrian Hunter2242c682008-09-05 11:56:05 +03001970 union ubifs_key *key = &zbr->key, *key1;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03001971
1972 ubifs_assert(n >= 0 && n <= c->fanout);
1973
1974 /* Implement naive insert for now */
1975again:
1976 zp = znode->parent;
1977 if (znode->child_cnt < c->fanout) {
1978 ubifs_assert(n != c->fanout);
1979 dbg_tnc("inserted at %d level %d, key %s", n, znode->level,
1980 DBGKEY(key));
1981
1982 insert_zbranch(znode, zbr, n);
1983
1984 /* Ensure parent's key is correct */
1985 if (n == 0 && zp && znode->iip == 0)
1986 correct_parent_keys(c, znode);
1987
1988 return 0;
1989 }
1990
1991 /*
1992 * Unfortunately, @znode does not have more empty slots and we have to
1993 * split it.
1994 */
1995 dbg_tnc("splitting level %d, key %s", znode->level, DBGKEY(key));
1996
1997 if (znode->alt)
1998 /*
1999 * We can no longer be sure of finding this znode by key, so we
2000 * record it in the old_idx tree.
2001 */
2002 ins_clr_old_idx_znode(c, znode);
2003
2004 zn = kzalloc(c->max_znode_sz, GFP_NOFS);
2005 if (!zn)
2006 return -ENOMEM;
2007 zn->parent = zp;
2008 zn->level = znode->level;
2009
2010 /* Decide where to split */
Adrian Hunter2242c682008-09-05 11:56:05 +03002011 if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) {
2012 /* Try not to split consecutive data keys */
2013 if (n == c->fanout) {
2014 key1 = &znode->zbranch[n - 1].key;
2015 if (key_inum(c, key1) == key_inum(c, key) &&
2016 key_type(c, key1) == UBIFS_DATA_KEY)
2017 appending = 1;
2018 } else
2019 goto check_split;
2020 } else if (appending && n != c->fanout) {
2021 /* Try not to split consecutive data keys */
2022 appending = 0;
2023check_split:
2024 if (n >= (c->fanout + 1) / 2) {
2025 key1 = &znode->zbranch[0].key;
2026 if (key_inum(c, key1) == key_inum(c, key) &&
2027 key_type(c, key1) == UBIFS_DATA_KEY) {
2028 key1 = &znode->zbranch[n].key;
2029 if (key_inum(c, key1) != key_inum(c, key) ||
2030 key_type(c, key1) != UBIFS_DATA_KEY) {
2031 keep = n;
2032 move = c->fanout - keep;
2033 zi = znode;
2034 goto do_split;
2035 }
2036 }
2037 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002038 }
2039
2040 if (appending) {
2041 keep = c->fanout;
2042 move = 0;
2043 } else {
2044 keep = (c->fanout + 1) / 2;
2045 move = c->fanout - keep;
2046 }
2047
2048 /*
2049 * Although we don't at present, we could look at the neighbors and see
2050 * if we can move some zbranches there.
2051 */
2052
2053 if (n < keep) {
2054 /* Insert into existing znode */
2055 zi = znode;
2056 move += 1;
2057 keep -= 1;
2058 } else {
2059 /* Insert into new znode */
2060 zi = zn;
2061 n -= keep;
2062 /* Re-parent */
2063 if (zn->level != 0)
2064 zbr->znode->parent = zn;
2065 }
2066
Adrian Hunter2242c682008-09-05 11:56:05 +03002067do_split:
2068
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002069 __set_bit(DIRTY_ZNODE, &zn->flags);
2070 atomic_long_inc(&c->dirty_zn_cnt);
2071
2072 zn->child_cnt = move;
2073 znode->child_cnt = keep;
2074
2075 dbg_tnc("moving %d, keeping %d", move, keep);
2076
2077 /* Move zbranch */
2078 for (i = 0; i < move; i++) {
2079 zn->zbranch[i] = znode->zbranch[keep + i];
2080 /* Re-parent */
2081 if (zn->level != 0)
2082 if (zn->zbranch[i].znode) {
2083 zn->zbranch[i].znode->parent = zn;
2084 zn->zbranch[i].znode->iip = i;
2085 }
2086 }
2087
2088 /* Insert new key and branch */
2089 dbg_tnc("inserting at %d level %d, key %s", n, zn->level, DBGKEY(key));
2090
2091 insert_zbranch(zi, zbr, n);
2092
2093 /* Insert new znode (produced by spitting) into the parent */
2094 if (zp) {
Adrian Hunter2242c682008-09-05 11:56:05 +03002095 if (n == 0 && zi == znode && znode->iip == 0)
2096 correct_parent_keys(c, znode);
2097
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002098 /* Locate insertion point */
2099 n = znode->iip + 1;
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002100
2101 /* Tail recursion */
2102 zbr->key = zn->zbranch[0].key;
2103 zbr->znode = zn;
2104 zbr->lnum = 0;
2105 zbr->offs = 0;
2106 zbr->len = 0;
2107 znode = zp;
2108
2109 goto again;
2110 }
2111
2112 /* We have to split root znode */
2113 dbg_tnc("creating new zroot at level %d", znode->level + 1);
2114
2115 zi = kzalloc(c->max_znode_sz, GFP_NOFS);
2116 if (!zi)
2117 return -ENOMEM;
2118
2119 zi->child_cnt = 2;
2120 zi->level = znode->level + 1;
2121
2122 __set_bit(DIRTY_ZNODE, &zi->flags);
2123 atomic_long_inc(&c->dirty_zn_cnt);
2124
2125 zi->zbranch[0].key = znode->zbranch[0].key;
2126 zi->zbranch[0].znode = znode;
2127 zi->zbranch[0].lnum = c->zroot.lnum;
2128 zi->zbranch[0].offs = c->zroot.offs;
2129 zi->zbranch[0].len = c->zroot.len;
2130 zi->zbranch[1].key = zn->zbranch[0].key;
2131 zi->zbranch[1].znode = zn;
2132
2133 c->zroot.lnum = 0;
2134 c->zroot.offs = 0;
2135 c->zroot.len = 0;
2136 c->zroot.znode = zi;
2137
2138 zn->parent = zi;
2139 zn->iip = 1;
2140 znode->parent = zi;
2141 znode->iip = 0;
2142
2143 return 0;
2144}
2145
2146/**
2147 * ubifs_tnc_add - add a node to TNC.
2148 * @c: UBIFS file-system description object
2149 * @key: key to add
2150 * @lnum: LEB number of node
2151 * @offs: node offset
2152 * @len: node length
2153 *
2154 * This function adds a node with key @key to TNC. The node may be new or it may
2155 * obsolete some existing one. Returns %0 on success or negative error code on
2156 * failure.
2157 */
2158int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum,
2159 int offs, int len)
2160{
2161 int found, n, err = 0;
2162 struct ubifs_znode *znode;
2163
2164 mutex_lock(&c->tnc_mutex);
2165 dbg_tnc("%d:%d, len %d, key %s", lnum, offs, len, DBGKEY(key));
2166 found = lookup_level0_dirty(c, key, &znode, &n);
2167 if (!found) {
2168 struct ubifs_zbranch zbr;
2169
2170 zbr.znode = NULL;
2171 zbr.lnum = lnum;
2172 zbr.offs = offs;
2173 zbr.len = len;
2174 key_copy(c, key, &zbr.key);
2175 err = tnc_insert(c, znode, &zbr, n + 1);
2176 } else if (found == 1) {
2177 struct ubifs_zbranch *zbr = &znode->zbranch[n];
2178
2179 lnc_free(zbr);
2180 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2181 zbr->lnum = lnum;
2182 zbr->offs = offs;
2183 zbr->len = len;
2184 } else
2185 err = found;
2186 if (!err)
2187 err = dbg_check_tnc(c, 0);
2188 mutex_unlock(&c->tnc_mutex);
2189
2190 return err;
2191}
2192
2193/**
2194 * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.
2195 * @c: UBIFS file-system description object
2196 * @key: key to add
2197 * @old_lnum: LEB number of old node
2198 * @old_offs: old node offset
2199 * @lnum: LEB number of node
2200 * @offs: node offset
2201 * @len: node length
2202 *
2203 * This function replaces a node with key @key in the TNC only if the old node
2204 * is found. This function is called by garbage collection when node are moved.
2205 * Returns %0 on success or negative error code on failure.
2206 */
2207int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key,
2208 int old_lnum, int old_offs, int lnum, int offs, int len)
2209{
2210 int found, n, err = 0;
2211 struct ubifs_znode *znode;
2212
2213 mutex_lock(&c->tnc_mutex);
2214 dbg_tnc("old LEB %d:%d, new LEB %d:%d, len %d, key %s", old_lnum,
2215 old_offs, lnum, offs, len, DBGKEY(key));
2216 found = lookup_level0_dirty(c, key, &znode, &n);
2217 if (found < 0) {
2218 err = found;
2219 goto out_unlock;
2220 }
2221
2222 if (found == 1) {
2223 struct ubifs_zbranch *zbr = &znode->zbranch[n];
2224
2225 found = 0;
2226 if (zbr->lnum == old_lnum && zbr->offs == old_offs) {
2227 lnc_free(zbr);
2228 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2229 if (err)
2230 goto out_unlock;
2231 zbr->lnum = lnum;
2232 zbr->offs = offs;
2233 zbr->len = len;
2234 found = 1;
2235 } else if (is_hash_key(c, key)) {
2236 found = resolve_collision_directly(c, key, &znode, &n,
2237 old_lnum, old_offs);
2238 dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d",
2239 found, znode, n, old_lnum, old_offs);
2240 if (found < 0) {
2241 err = found;
2242 goto out_unlock;
2243 }
2244
2245 if (found) {
2246 /* Ensure the znode is dirtied */
2247 if (znode->cnext || !ubifs_zn_dirty(znode)) {
Artem Bityutskiyf92b9822008-12-28 11:34:26 +02002248 znode = dirty_cow_bottom_up(c, znode);
2249 if (IS_ERR(znode)) {
2250 err = PTR_ERR(znode);
2251 goto out_unlock;
2252 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002253 }
2254 zbr = &znode->zbranch[n];
2255 lnc_free(zbr);
2256 err = ubifs_add_dirt(c, zbr->lnum,
2257 zbr->len);
2258 if (err)
2259 goto out_unlock;
2260 zbr->lnum = lnum;
2261 zbr->offs = offs;
2262 zbr->len = len;
2263 }
2264 }
2265 }
2266
2267 if (!found)
2268 err = ubifs_add_dirt(c, lnum, len);
2269
2270 if (!err)
2271 err = dbg_check_tnc(c, 0);
2272
2273out_unlock:
2274 mutex_unlock(&c->tnc_mutex);
2275 return err;
2276}
2277
2278/**
2279 * ubifs_tnc_add_nm - add a "hashed" node to TNC.
2280 * @c: UBIFS file-system description object
2281 * @key: key to add
2282 * @lnum: LEB number of node
2283 * @offs: node offset
2284 * @len: node length
2285 * @nm: node name
2286 *
2287 * This is the same as 'ubifs_tnc_add()' but it should be used with keys which
2288 * may have collisions, like directory entry keys.
2289 */
2290int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key,
2291 int lnum, int offs, int len, const struct qstr *nm)
2292{
2293 int found, n, err = 0;
2294 struct ubifs_znode *znode;
2295
2296 mutex_lock(&c->tnc_mutex);
2297 dbg_tnc("LEB %d:%d, name '%.*s', key %s", lnum, offs, nm->len, nm->name,
2298 DBGKEY(key));
2299 found = lookup_level0_dirty(c, key, &znode, &n);
2300 if (found < 0) {
2301 err = found;
2302 goto out_unlock;
2303 }
2304
2305 if (found == 1) {
2306 if (c->replaying)
2307 found = fallible_resolve_collision(c, key, &znode, &n,
2308 nm, 1);
2309 else
2310 found = resolve_collision(c, key, &znode, &n, nm);
2311 dbg_tnc("rc returned %d, znode %p, n %d", found, znode, n);
2312 if (found < 0) {
2313 err = found;
2314 goto out_unlock;
2315 }
2316
2317 /* Ensure the znode is dirtied */
2318 if (znode->cnext || !ubifs_zn_dirty(znode)) {
Artem Bityutskiyf92b9822008-12-28 11:34:26 +02002319 znode = dirty_cow_bottom_up(c, znode);
2320 if (IS_ERR(znode)) {
2321 err = PTR_ERR(znode);
2322 goto out_unlock;
2323 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002324 }
2325
2326 if (found == 1) {
2327 struct ubifs_zbranch *zbr = &znode->zbranch[n];
2328
2329 lnc_free(zbr);
2330 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2331 zbr->lnum = lnum;
2332 zbr->offs = offs;
2333 zbr->len = len;
2334 goto out_unlock;
2335 }
2336 }
2337
2338 if (!found) {
2339 struct ubifs_zbranch zbr;
2340
2341 zbr.znode = NULL;
2342 zbr.lnum = lnum;
2343 zbr.offs = offs;
2344 zbr.len = len;
2345 key_copy(c, key, &zbr.key);
2346 err = tnc_insert(c, znode, &zbr, n + 1);
2347 if (err)
2348 goto out_unlock;
2349 if (c->replaying) {
2350 /*
2351 * We did not find it in the index so there may be a
2352 * dangling branch still in the index. So we remove it
2353 * by passing 'ubifs_tnc_remove_nm()' the same key but
2354 * an unmatchable name.
2355 */
2356 struct qstr noname = { .len = 0, .name = "" };
2357
2358 err = dbg_check_tnc(c, 0);
2359 mutex_unlock(&c->tnc_mutex);
2360 if (err)
2361 return err;
2362 return ubifs_tnc_remove_nm(c, key, &noname);
2363 }
2364 }
2365
2366out_unlock:
2367 if (!err)
2368 err = dbg_check_tnc(c, 0);
2369 mutex_unlock(&c->tnc_mutex);
2370 return err;
2371}
2372
2373/**
2374 * tnc_delete - delete a znode form TNC.
2375 * @c: UBIFS file-system description object
2376 * @znode: znode to delete from
2377 * @n: zbranch slot number to delete
2378 *
2379 * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
2380 * case of success and a negative error code in case of failure.
2381 */
2382static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n)
2383{
2384 struct ubifs_zbranch *zbr;
2385 struct ubifs_znode *zp;
2386 int i, err;
2387
2388 /* Delete without merge for now */
2389 ubifs_assert(znode->level == 0);
2390 ubifs_assert(n >= 0 && n < c->fanout);
2391 dbg_tnc("deleting %s", DBGKEY(&znode->zbranch[n].key));
2392
2393 zbr = &znode->zbranch[n];
2394 lnc_free(zbr);
2395
2396 err = ubifs_add_dirt(c, zbr->lnum, zbr->len);
2397 if (err) {
2398 dbg_dump_znode(c, znode);
2399 return err;
2400 }
2401
2402 /* We do not "gap" zbranch slots */
2403 for (i = n; i < znode->child_cnt - 1; i++)
2404 znode->zbranch[i] = znode->zbranch[i + 1];
2405 znode->child_cnt -= 1;
2406
2407 if (znode->child_cnt > 0)
2408 return 0;
2409
2410 /*
2411 * This was the last zbranch, we have to delete this znode from the
2412 * parent.
2413 */
2414
2415 do {
2416 ubifs_assert(!test_bit(OBSOLETE_ZNODE, &znode->flags));
2417 ubifs_assert(ubifs_zn_dirty(znode));
2418
2419 zp = znode->parent;
2420 n = znode->iip;
2421
2422 atomic_long_dec(&c->dirty_zn_cnt);
2423
2424 err = insert_old_idx_znode(c, znode);
2425 if (err)
2426 return err;
2427
2428 if (znode->cnext) {
2429 __set_bit(OBSOLETE_ZNODE, &znode->flags);
2430 atomic_long_inc(&c->clean_zn_cnt);
2431 atomic_long_inc(&ubifs_clean_zn_cnt);
2432 } else
2433 kfree(znode);
2434 znode = zp;
2435 } while (znode->child_cnt == 1); /* while removing last child */
2436
2437 /* Remove from znode, entry n - 1 */
2438 znode->child_cnt -= 1;
2439 ubifs_assert(znode->level != 0);
2440 for (i = n; i < znode->child_cnt; i++) {
2441 znode->zbranch[i] = znode->zbranch[i + 1];
2442 if (znode->zbranch[i].znode)
2443 znode->zbranch[i].znode->iip = i;
2444 }
2445
2446 /*
2447 * If this is the root and it has only 1 child then
2448 * collapse the tree.
2449 */
2450 if (!znode->parent) {
2451 while (znode->child_cnt == 1 && znode->level != 0) {
2452 zp = znode;
2453 zbr = &znode->zbranch[0];
2454 znode = get_znode(c, znode, 0);
2455 if (IS_ERR(znode))
2456 return PTR_ERR(znode);
2457 znode = dirty_cow_znode(c, zbr);
2458 if (IS_ERR(znode))
2459 return PTR_ERR(znode);
2460 znode->parent = NULL;
2461 znode->iip = 0;
2462 if (c->zroot.len) {
2463 err = insert_old_idx(c, c->zroot.lnum,
2464 c->zroot.offs);
2465 if (err)
2466 return err;
2467 }
2468 c->zroot.lnum = zbr->lnum;
2469 c->zroot.offs = zbr->offs;
2470 c->zroot.len = zbr->len;
2471 c->zroot.znode = znode;
2472 ubifs_assert(!test_bit(OBSOLETE_ZNODE,
2473 &zp->flags));
2474 ubifs_assert(test_bit(DIRTY_ZNODE, &zp->flags));
2475 atomic_long_dec(&c->dirty_zn_cnt);
2476
2477 if (zp->cnext) {
2478 __set_bit(OBSOLETE_ZNODE, &zp->flags);
2479 atomic_long_inc(&c->clean_zn_cnt);
2480 atomic_long_inc(&ubifs_clean_zn_cnt);
2481 } else
2482 kfree(zp);
2483 }
2484 }
2485
2486 return 0;
2487}
2488
2489/**
2490 * ubifs_tnc_remove - remove an index entry of a node.
2491 * @c: UBIFS file-system description object
2492 * @key: key of node
2493 *
2494 * Returns %0 on success or negative error code on failure.
2495 */
2496int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key)
2497{
2498 int found, n, err = 0;
2499 struct ubifs_znode *znode;
2500
2501 mutex_lock(&c->tnc_mutex);
2502 dbg_tnc("key %s", DBGKEY(key));
2503 found = lookup_level0_dirty(c, key, &znode, &n);
2504 if (found < 0) {
2505 err = found;
2506 goto out_unlock;
2507 }
2508 if (found == 1)
2509 err = tnc_delete(c, znode, n);
2510 if (!err)
2511 err = dbg_check_tnc(c, 0);
2512
2513out_unlock:
2514 mutex_unlock(&c->tnc_mutex);
2515 return err;
2516}
2517
2518/**
2519 * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.
2520 * @c: UBIFS file-system description object
2521 * @key: key of node
2522 * @nm: directory entry name
2523 *
2524 * Returns %0 on success or negative error code on failure.
2525 */
2526int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key,
2527 const struct qstr *nm)
2528{
2529 int n, err;
2530 struct ubifs_znode *znode;
2531
2532 mutex_lock(&c->tnc_mutex);
2533 dbg_tnc("%.*s, key %s", nm->len, nm->name, DBGKEY(key));
2534 err = lookup_level0_dirty(c, key, &znode, &n);
2535 if (err < 0)
2536 goto out_unlock;
2537
2538 if (err) {
2539 if (c->replaying)
2540 err = fallible_resolve_collision(c, key, &znode, &n,
2541 nm, 0);
2542 else
2543 err = resolve_collision(c, key, &znode, &n, nm);
2544 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n);
2545 if (err < 0)
2546 goto out_unlock;
2547 if (err) {
2548 /* Ensure the znode is dirtied */
2549 if (znode->cnext || !ubifs_zn_dirty(znode)) {
2550 znode = dirty_cow_bottom_up(c, znode);
2551 if (IS_ERR(znode)) {
2552 err = PTR_ERR(znode);
2553 goto out_unlock;
2554 }
2555 }
2556 err = tnc_delete(c, znode, n);
2557 }
2558 }
2559
2560out_unlock:
2561 if (!err)
2562 err = dbg_check_tnc(c, 0);
2563 mutex_unlock(&c->tnc_mutex);
2564 return err;
2565}
2566
2567/**
2568 * key_in_range - determine if a key falls within a range of keys.
2569 * @c: UBIFS file-system description object
2570 * @key: key to check
2571 * @from_key: lowest key in range
2572 * @to_key: highest key in range
2573 *
2574 * This function returns %1 if the key is in range and %0 otherwise.
2575 */
2576static int key_in_range(struct ubifs_info *c, union ubifs_key *key,
2577 union ubifs_key *from_key, union ubifs_key *to_key)
2578{
2579 if (keys_cmp(c, key, from_key) < 0)
2580 return 0;
2581 if (keys_cmp(c, key, to_key) > 0)
2582 return 0;
2583 return 1;
2584}
2585
2586/**
2587 * ubifs_tnc_remove_range - remove index entries in range.
2588 * @c: UBIFS file-system description object
2589 * @from_key: lowest key to remove
2590 * @to_key: highest key to remove
2591 *
2592 * This function removes index entries starting at @from_key and ending at
2593 * @to_key. This function returns zero in case of success and a negative error
2594 * code in case of failure.
2595 */
2596int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key,
2597 union ubifs_key *to_key)
2598{
2599 int i, n, k, err = 0;
2600 struct ubifs_znode *znode;
2601 union ubifs_key *key;
2602
2603 mutex_lock(&c->tnc_mutex);
2604 while (1) {
2605 /* Find first level 0 znode that contains keys to remove */
2606 err = ubifs_lookup_level0(c, from_key, &znode, &n);
2607 if (err < 0)
2608 goto out_unlock;
2609
2610 if (err)
2611 key = from_key;
2612 else {
2613 err = tnc_next(c, &znode, &n);
2614 if (err == -ENOENT) {
2615 err = 0;
2616 goto out_unlock;
2617 }
2618 if (err < 0)
2619 goto out_unlock;
2620 key = &znode->zbranch[n].key;
2621 if (!key_in_range(c, key, from_key, to_key)) {
2622 err = 0;
2623 goto out_unlock;
2624 }
2625 }
2626
2627 /* Ensure the znode is dirtied */
2628 if (znode->cnext || !ubifs_zn_dirty(znode)) {
Artem Bityutskiyf92b9822008-12-28 11:34:26 +02002629 znode = dirty_cow_bottom_up(c, znode);
2630 if (IS_ERR(znode)) {
2631 err = PTR_ERR(znode);
2632 goto out_unlock;
2633 }
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002634 }
2635
2636 /* Remove all keys in range except the first */
2637 for (i = n + 1, k = 0; i < znode->child_cnt; i++, k++) {
2638 key = &znode->zbranch[i].key;
2639 if (!key_in_range(c, key, from_key, to_key))
2640 break;
2641 lnc_free(&znode->zbranch[i]);
2642 err = ubifs_add_dirt(c, znode->zbranch[i].lnum,
2643 znode->zbranch[i].len);
2644 if (err) {
2645 dbg_dump_znode(c, znode);
2646 goto out_unlock;
2647 }
2648 dbg_tnc("removing %s", DBGKEY(key));
2649 }
2650 if (k) {
2651 for (i = n + 1 + k; i < znode->child_cnt; i++)
2652 znode->zbranch[i - k] = znode->zbranch[i];
2653 znode->child_cnt -= k;
2654 }
2655
2656 /* Now delete the first */
2657 err = tnc_delete(c, znode, n);
2658 if (err)
2659 goto out_unlock;
2660 }
2661
2662out_unlock:
2663 if (!err)
2664 err = dbg_check_tnc(c, 0);
2665 mutex_unlock(&c->tnc_mutex);
2666 return err;
2667}
2668
2669/**
2670 * ubifs_tnc_remove_ino - remove an inode from TNC.
2671 * @c: UBIFS file-system description object
2672 * @inum: inode number to remove
2673 *
2674 * This function remove inode @inum and all the extended attributes associated
2675 * with the anode from TNC and returns zero in case of success or a negative
2676 * error code in case of failure.
2677 */
2678int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum)
2679{
2680 union ubifs_key key1, key2;
2681 struct ubifs_dent_node *xent, *pxent = NULL;
2682 struct qstr nm = { .name = NULL };
2683
Artem Bityutskiye84461a2008-10-29 12:08:43 +02002684 dbg_tnc("ino %lu", (unsigned long)inum);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002685
2686 /*
2687 * Walk all extended attribute entries and remove them together with
2688 * corresponding extended attribute inodes.
2689 */
2690 lowest_xent_key(c, &key1, inum);
2691 while (1) {
2692 ino_t xattr_inum;
2693 int err;
2694
2695 xent = ubifs_tnc_next_ent(c, &key1, &nm);
2696 if (IS_ERR(xent)) {
2697 err = PTR_ERR(xent);
2698 if (err == -ENOENT)
2699 break;
2700 return err;
2701 }
2702
2703 xattr_inum = le64_to_cpu(xent->inum);
Artem Bityutskiye84461a2008-10-29 12:08:43 +02002704 dbg_tnc("xent '%s', ino %lu", xent->name,
2705 (unsigned long)xattr_inum);
Artem Bityutskiy1e517642008-07-14 19:08:37 +03002706
2707 nm.name = xent->name;
2708 nm.len = le16_to_cpu(xent->nlen);
2709 err = ubifs_tnc_remove_nm(c, &key1, &nm);
2710 if (err) {
2711 kfree(xent);
2712 return err;
2713 }
2714
2715 lowest_ino_key(c, &key1, xattr_inum);
2716 highest_ino_key(c, &key2, xattr_inum);
2717 err = ubifs_tnc_remove_range(c, &key1, &key2);
2718 if (err) {
2719 kfree(xent);
2720 return err;
2721 }
2722
2723 kfree(pxent);
2724 pxent = xent;
2725 key_read(c, &xent->key, &key1);
2726 }
2727
2728 kfree(pxent);
2729 lowest_ino_key(c, &key1, inum);
2730 highest_ino_key(c, &key2, inum);
2731
2732 return ubifs_tnc_remove_range(c, &key1, &key2);
2733}
2734
2735/**
2736 * ubifs_tnc_next_ent - walk directory or extended attribute entries.
2737 * @c: UBIFS file-system description object
2738 * @key: key of last entry
2739 * @nm: name of last entry found or %NULL
2740 *
2741 * This function finds and reads the next directory or extended attribute entry
2742 * after the given key (@key) if there is one. @nm is used to resolve
2743 * collisions.
2744 *
2745 * If the name of the current entry is not known and only the key is known,
2746 * @nm->name has to be %NULL. In this case the semantics of this function is a
2747 * little bit different and it returns the entry corresponding to this key, not
2748 * the next one. If the key was not found, the closest "right" entry is
2749 * returned.
2750 *
2751 * If the fist entry has to be found, @key has to contain the lowest possible
2752 * key value for this inode and @name has to be %NULL.
2753 *
2754 * This function returns the found directory or extended attribute entry node
2755 * in case of success, %-ENOENT is returned if no entry was found, and a
2756 * negative error code is returned in case of failure.
2757 */
2758struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c,
2759 union ubifs_key *key,
2760 const struct qstr *nm)
2761{
2762 int n, err, type = key_type(c, key);
2763 struct ubifs_znode *znode;
2764 struct ubifs_dent_node *dent;
2765 struct ubifs_zbranch *zbr;
2766 union ubifs_key *dkey;
2767
2768 dbg_tnc("%s %s", nm->name ? (char *)nm->name : "(lowest)", DBGKEY(key));
2769 ubifs_assert(is_hash_key(c, key));
2770
2771 mutex_lock(&c->tnc_mutex);
2772 err = ubifs_lookup_level0(c, key, &znode, &n);
2773 if (unlikely(err < 0))
2774 goto out_unlock;
2775
2776 if (nm->name) {
2777 if (err) {
2778 /* Handle collisions */
2779 err = resolve_collision(c, key, &znode, &n, nm);
2780 dbg_tnc("rc returned %d, znode %p, n %d",
2781 err, znode, n);
2782 if (unlikely(err < 0))
2783 goto out_unlock;
2784 }
2785
2786 /* Now find next entry */
2787 err = tnc_next(c, &znode, &n);
2788 if (unlikely(err))
2789 goto out_unlock;
2790 } else {
2791 /*
2792 * The full name of the entry was not given, in which case the
2793 * behavior of this function is a little different and it
2794 * returns current entry, not the next one.
2795 */
2796 if (!err) {
2797 /*
2798 * However, the given key does not exist in the TNC
2799 * tree and @znode/@n variables contain the closest
2800 * "preceding" element. Switch to the next one.
2801 */
2802 err = tnc_next(c, &znode, &n);
2803 if (err)
2804 goto out_unlock;
2805 }
2806 }
2807
2808 zbr = &znode->zbranch[n];
2809 dent = kmalloc(zbr->len, GFP_NOFS);
2810 if (unlikely(!dent)) {
2811 err = -ENOMEM;
2812 goto out_unlock;
2813 }
2814
2815 /*
2816 * The above 'tnc_next()' call could lead us to the next inode, check
2817 * this.
2818 */
2819 dkey = &zbr->key;
2820 if (key_inum(c, dkey) != key_inum(c, key) ||
2821 key_type(c, dkey) != type) {
2822 err = -ENOENT;
2823 goto out_free;
2824 }
2825
2826 err = tnc_read_node_nm(c, zbr, dent);
2827 if (unlikely(err))
2828 goto out_free;
2829
2830 mutex_unlock(&c->tnc_mutex);
2831 return dent;
2832
2833out_free:
2834 kfree(dent);
2835out_unlock:
2836 mutex_unlock(&c->tnc_mutex);
2837 return ERR_PTR(err);
2838}
2839
2840/**
2841 * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit.
2842 * @c: UBIFS file-system description object
2843 *
2844 * Destroy left-over obsolete znodes from a failed commit.
2845 */
2846static void tnc_destroy_cnext(struct ubifs_info *c)
2847{
2848 struct ubifs_znode *cnext;
2849
2850 if (!c->cnext)
2851 return;
2852 ubifs_assert(c->cmt_state == COMMIT_BROKEN);
2853 cnext = c->cnext;
2854 do {
2855 struct ubifs_znode *znode = cnext;
2856
2857 cnext = cnext->cnext;
2858 if (test_bit(OBSOLETE_ZNODE, &znode->flags))
2859 kfree(znode);
2860 } while (cnext && cnext != c->cnext);
2861}
2862
2863/**
2864 * ubifs_tnc_close - close TNC subsystem and free all related resources.
2865 * @c: UBIFS file-system description object
2866 */
2867void ubifs_tnc_close(struct ubifs_info *c)
2868{
2869 long clean_freed;
2870
2871 tnc_destroy_cnext(c);
2872 if (c->zroot.znode) {
2873 clean_freed = ubifs_destroy_tnc_subtree(c->zroot.znode);
2874 atomic_long_sub(clean_freed, &ubifs_clean_zn_cnt);
2875 }
2876 kfree(c->gap_lebs);
2877 kfree(c->ilebs);
2878 destroy_old_idx(c);
2879}
2880
2881/**
2882 * left_znode - get the znode to the left.
2883 * @c: UBIFS file-system description object
2884 * @znode: znode
2885 *
2886 * This function returns a pointer to the znode to the left of @znode or NULL if
2887 * there is not one. A negative error code is returned on failure.
2888 */
2889static struct ubifs_znode *left_znode(struct ubifs_info *c,
2890 struct ubifs_znode *znode)
2891{
2892 int level = znode->level;
2893
2894 while (1) {
2895 int n = znode->iip - 1;
2896
2897 /* Go up until we can go left */
2898 znode = znode->parent;
2899 if (!znode)
2900 return NULL;
2901 if (n >= 0) {
2902 /* Now go down the rightmost branch to 'level' */
2903 znode = get_znode(c, znode, n);
2904 if (IS_ERR(znode))
2905 return znode;
2906 while (znode->level != level) {
2907 n = znode->child_cnt - 1;
2908 znode = get_znode(c, znode, n);
2909 if (IS_ERR(znode))
2910 return znode;
2911 }
2912 break;
2913 }
2914 }
2915 return znode;
2916}
2917
2918/**
2919 * right_znode - get the znode to the right.
2920 * @c: UBIFS file-system description object
2921 * @znode: znode
2922 *
2923 * This function returns a pointer to the znode to the right of @znode or NULL
2924 * if there is not one. A negative error code is returned on failure.
2925 */
2926static struct ubifs_znode *right_znode(struct ubifs_info *c,
2927 struct ubifs_znode *znode)
2928{
2929 int level = znode->level;
2930
2931 while (1) {
2932 int n = znode->iip + 1;
2933
2934 /* Go up until we can go right */
2935 znode = znode->parent;
2936 if (!znode)
2937 return NULL;
2938 if (n < znode->child_cnt) {
2939 /* Now go down the leftmost branch to 'level' */
2940 znode = get_znode(c, znode, n);
2941 if (IS_ERR(znode))
2942 return znode;
2943 while (znode->level != level) {
2944 znode = get_znode(c, znode, 0);
2945 if (IS_ERR(znode))
2946 return znode;
2947 }
2948 break;
2949 }
2950 }
2951 return znode;
2952}
2953
2954/**
2955 * lookup_znode - find a particular indexing node from TNC.
2956 * @c: UBIFS file-system description object
2957 * @key: index node key to lookup
2958 * @level: index node level
2959 * @lnum: index node LEB number
2960 * @offs: index node offset
2961 *
2962 * This function searches an indexing node by its first key @key and its
2963 * address @lnum:@offs. It looks up the indexing tree by pulling all indexing
2964 * nodes it traverses to TNC. This function is called fro indexing nodes which
2965 * were found on the media by scanning, for example when garbage-collecting or
2966 * when doing in-the-gaps commit. This means that the indexing node which is
2967 * looked for does not have to have exactly the same leftmost key @key, because
2968 * the leftmost key may have been changed, in which case TNC will contain a
2969 * dirty znode which still refers the same @lnum:@offs. This function is clever
2970 * enough to recognize such indexing nodes.
2971 *
2972 * Note, if a znode was deleted or changed too much, then this function will
2973 * not find it. For situations like this UBIFS has the old index RB-tree
2974 * (indexed by @lnum:@offs).
2975 *
2976 * This function returns a pointer to the znode found or %NULL if it is not
2977 * found. A negative error code is returned on failure.
2978 */
2979static struct ubifs_znode *lookup_znode(struct ubifs_info *c,
2980 union ubifs_key *key, int level,
2981 int lnum, int offs)
2982{
2983 struct ubifs_znode *znode, *zn;
2984 int n, nn;
2985
2986 /*
2987 * The arguments have probably been read off flash, so don't assume
2988 * they are valid.
2989 */
2990 if (level < 0)
2991 return ERR_PTR(-EINVAL);
2992
2993 /* Get the root znode */
2994 znode = c->zroot.znode;
2995 if (!znode) {
2996 znode = ubifs_load_znode(c, &c->zroot, NULL, 0);
2997 if (IS_ERR(znode))
2998 return znode;
2999 }
3000 /* Check if it is the one we are looking for */
3001 if (c->zroot.lnum == lnum && c->zroot.offs == offs)
3002 return znode;
3003 /* Descend to the parent level i.e. (level + 1) */
3004 if (level >= znode->level)
3005 return NULL;
3006 while (1) {
3007 ubifs_search_zbranch(c, znode, key, &n);
3008 if (n < 0) {
3009 /*
3010 * We reached a znode where the leftmost key is greater
3011 * than the key we are searching for. This is the same
3012 * situation as the one described in a huge comment at
3013 * the end of the 'ubifs_lookup_level0()' function. And
3014 * for exactly the same reasons we have to try to look
3015 * left before giving up.
3016 */
3017 znode = left_znode(c, znode);
3018 if (!znode)
3019 return NULL;
3020 if (IS_ERR(znode))
3021 return znode;
3022 ubifs_search_zbranch(c, znode, key, &n);
3023 ubifs_assert(n >= 0);
3024 }
3025 if (znode->level == level + 1)
3026 break;
3027 znode = get_znode(c, znode, n);
3028 if (IS_ERR(znode))
3029 return znode;
3030 }
3031 /* Check if the child is the one we are looking for */
3032 if (znode->zbranch[n].lnum == lnum && znode->zbranch[n].offs == offs)
3033 return get_znode(c, znode, n);
3034 /* If the key is unique, there is nowhere else to look */
3035 if (!is_hash_key(c, key))
3036 return NULL;
3037 /*
3038 * The key is not unique and so may be also in the znodes to either
3039 * side.
3040 */
3041 zn = znode;
3042 nn = n;
3043 /* Look left */
3044 while (1) {
3045 /* Move one branch to the left */
3046 if (n)
3047 n -= 1;
3048 else {
3049 znode = left_znode(c, znode);
3050 if (!znode)
3051 break;
3052 if (IS_ERR(znode))
3053 return znode;
3054 n = znode->child_cnt - 1;
3055 }
3056 /* Check it */
3057 if (znode->zbranch[n].lnum == lnum &&
3058 znode->zbranch[n].offs == offs)
3059 return get_znode(c, znode, n);
3060 /* Stop if the key is less than the one we are looking for */
3061 if (keys_cmp(c, &znode->zbranch[n].key, key) < 0)
3062 break;
3063 }
3064 /* Back to the middle */
3065 znode = zn;
3066 n = nn;
3067 /* Look right */
3068 while (1) {
3069 /* Move one branch to the right */
3070 if (++n >= znode->child_cnt) {
3071 znode = right_znode(c, znode);
3072 if (!znode)
3073 break;
3074 if (IS_ERR(znode))
3075 return znode;
3076 n = 0;
3077 }
3078 /* Check it */
3079 if (znode->zbranch[n].lnum == lnum &&
3080 znode->zbranch[n].offs == offs)
3081 return get_znode(c, znode, n);
3082 /* Stop if the key is greater than the one we are looking for */
3083 if (keys_cmp(c, &znode->zbranch[n].key, key) > 0)
3084 break;
3085 }
3086 return NULL;
3087}
3088
3089/**
3090 * is_idx_node_in_tnc - determine if an index node is in the TNC.
3091 * @c: UBIFS file-system description object
3092 * @key: key of index node
3093 * @level: index node level
3094 * @lnum: LEB number of index node
3095 * @offs: offset of index node
3096 *
3097 * This function returns %0 if the index node is not referred to in the TNC, %1
3098 * if the index node is referred to in the TNC and the corresponding znode is
3099 * dirty, %2 if an index node is referred to in the TNC and the corresponding
3100 * znode is clean, and a negative error code in case of failure.
3101 *
3102 * Note, the @key argument has to be the key of the first child. Also note,
3103 * this function relies on the fact that 0:0 is never a valid LEB number and
3104 * offset for a main-area node.
3105 */
3106int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level,
3107 int lnum, int offs)
3108{
3109 struct ubifs_znode *znode;
3110
3111 znode = lookup_znode(c, key, level, lnum, offs);
3112 if (!znode)
3113 return 0;
3114 if (IS_ERR(znode))
3115 return PTR_ERR(znode);
3116
3117 return ubifs_zn_dirty(znode) ? 1 : 2;
3118}
3119
3120/**
3121 * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC.
3122 * @c: UBIFS file-system description object
3123 * @key: node key
3124 * @lnum: node LEB number
3125 * @offs: node offset
3126 *
3127 * This function returns %1 if the node is referred to in the TNC, %0 if it is
3128 * not, and a negative error code in case of failure.
3129 *
3130 * Note, this function relies on the fact that 0:0 is never a valid LEB number
3131 * and offset for a main-area node.
3132 */
3133static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key,
3134 int lnum, int offs)
3135{
3136 struct ubifs_zbranch *zbr;
3137 struct ubifs_znode *znode, *zn;
3138 int n, found, err, nn;
3139 const int unique = !is_hash_key(c, key);
3140
3141 found = ubifs_lookup_level0(c, key, &znode, &n);
3142 if (found < 0)
3143 return found; /* Error code */
3144 if (!found)
3145 return 0;
3146 zbr = &znode->zbranch[n];
3147 if (lnum == zbr->lnum && offs == zbr->offs)
3148 return 1; /* Found it */
3149 if (unique)
3150 return 0;
3151 /*
3152 * Because the key is not unique, we have to look left
3153 * and right as well
3154 */
3155 zn = znode;
3156 nn = n;
3157 /* Look left */
3158 while (1) {
3159 err = tnc_prev(c, &znode, &n);
3160 if (err == -ENOENT)
3161 break;
3162 if (err)
3163 return err;
3164 if (keys_cmp(c, key, &znode->zbranch[n].key))
3165 break;
3166 zbr = &znode->zbranch[n];
3167 if (lnum == zbr->lnum && offs == zbr->offs)
3168 return 1; /* Found it */
3169 }
3170 /* Look right */
3171 znode = zn;
3172 n = nn;
3173 while (1) {
3174 err = tnc_next(c, &znode, &n);
3175 if (err) {
3176 if (err == -ENOENT)
3177 return 0;
3178 return err;
3179 }
3180 if (keys_cmp(c, key, &znode->zbranch[n].key))
3181 break;
3182 zbr = &znode->zbranch[n];
3183 if (lnum == zbr->lnum && offs == zbr->offs)
3184 return 1; /* Found it */
3185 }
3186 return 0;
3187}
3188
3189/**
3190 * ubifs_tnc_has_node - determine whether a node is in the TNC.
3191 * @c: UBIFS file-system description object
3192 * @key: node key
3193 * @level: index node level (if it is an index node)
3194 * @lnum: node LEB number
3195 * @offs: node offset
3196 * @is_idx: non-zero if the node is an index node
3197 *
3198 * This function returns %1 if the node is in the TNC, %0 if it is not, and a
3199 * negative error code in case of failure. For index nodes, @key has to be the
3200 * key of the first child. An index node is considered to be in the TNC only if
3201 * the corresponding znode is clean or has not been loaded.
3202 */
3203int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level,
3204 int lnum, int offs, int is_idx)
3205{
3206 int err;
3207
3208 mutex_lock(&c->tnc_mutex);
3209 if (is_idx) {
3210 err = is_idx_node_in_tnc(c, key, level, lnum, offs);
3211 if (err < 0)
3212 goto out_unlock;
3213 if (err == 1)
3214 /* The index node was found but it was dirty */
3215 err = 0;
3216 else if (err == 2)
3217 /* The index node was found and it was clean */
3218 err = 1;
3219 else
3220 BUG_ON(err != 0);
3221 } else
3222 err = is_leaf_node_in_tnc(c, key, lnum, offs);
3223
3224out_unlock:
3225 mutex_unlock(&c->tnc_mutex);
3226 return err;
3227}
3228
3229/**
3230 * ubifs_dirty_idx_node - dirty an index node.
3231 * @c: UBIFS file-system description object
3232 * @key: index node key
3233 * @level: index node level
3234 * @lnum: index node LEB number
3235 * @offs: index node offset
3236 *
3237 * This function loads and dirties an index node so that it can be garbage
3238 * collected. The @key argument has to be the key of the first child. This
3239 * function relies on the fact that 0:0 is never a valid LEB number and offset
3240 * for a main-area node. Returns %0 on success and a negative error code on
3241 * failure.
3242 */
3243int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level,
3244 int lnum, int offs)
3245{
3246 struct ubifs_znode *znode;
3247 int err = 0;
3248
3249 mutex_lock(&c->tnc_mutex);
3250 znode = lookup_znode(c, key, level, lnum, offs);
3251 if (!znode)
3252 goto out_unlock;
3253 if (IS_ERR(znode)) {
3254 err = PTR_ERR(znode);
3255 goto out_unlock;
3256 }
3257 znode = dirty_cow_bottom_up(c, znode);
3258 if (IS_ERR(znode)) {
3259 err = PTR_ERR(znode);
3260 goto out_unlock;
3261 }
3262
3263out_unlock:
3264 mutex_unlock(&c->tnc_mutex);
3265 return err;
3266}