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