]>
git.ipfire.org Git - thirdparty/u-boot.git/blob - fs/ubifs/tnc.c
1 // SPDX-License-Identifier: GPL-2.0+
3 * This file is part of UBIFS.
5 * Copyright (C) 2006-2008 Nokia Corporation.
7 * Authors: Adrian Hunter
8 * Artem Bityutskiy (Битюцкий Артём)
12 * This file implements TNC (Tree Node Cache) which caches indexing nodes of
15 * At the moment the locking rules of the TNC tree are quite simple and
16 * straightforward. We just have a mutex and lock it when we traverse the
17 * tree. If a znode is not in memory, we read it from flash while still having
22 #include <linux/crc32.h>
23 #include <linux/slab.h>
25 #include <linux/compat.h>
26 #include <linux/err.h>
27 #include <linux/stat.h>
32 * Returned codes of 'matches_name()' and 'fallible_matches_name()' functions.
33 * @NAME_LESS: name corresponding to the first argument is less than second
34 * @NAME_MATCHES: names match
35 * @NAME_GREATER: name corresponding to the second argument is greater than
37 * @NOT_ON_MEDIA: node referred by zbranch does not exist on the media
39 * These constants were introduce to improve readability.
49 * insert_old_idx - record an index node obsoleted since the last commit start.
50 * @c: UBIFS file-system description object
51 * @lnum: LEB number of obsoleted index node
52 * @offs: offset of obsoleted index node
54 * Returns %0 on success, and a negative error code on failure.
56 * For recovery, there must always be a complete intact version of the index on
57 * flash at all times. That is called the "old index". It is the index as at the
58 * time of the last successful commit. Many of the index nodes in the old index
59 * may be dirty, but they must not be erased until the next successful commit
60 * (at which point that index becomes the old index).
62 * That means that the garbage collection and the in-the-gaps method of
63 * committing must be able to determine if an index node is in the old index.
64 * Most of the old index nodes can be found by looking up the TNC using the
65 * 'lookup_znode()' function. However, some of the old index nodes may have
66 * been deleted from the current index or may have been changed so much that
67 * they cannot be easily found. In those cases, an entry is added to an RB-tree.
68 * That is what this function does. The RB-tree is ordered by LEB number and
69 * offset because they uniquely identify the old index node.
71 static int insert_old_idx(struct ubifs_info
*c
, int lnum
, int offs
)
73 struct ubifs_old_idx
*old_idx
, *o
;
74 struct rb_node
**p
, *parent
= NULL
;
76 old_idx
= kmalloc(sizeof(struct ubifs_old_idx
), GFP_NOFS
);
77 if (unlikely(!old_idx
))
82 p
= &c
->old_idx
.rb_node
;
85 o
= rb_entry(parent
, struct ubifs_old_idx
, rb
);
88 else if (lnum
> o
->lnum
)
90 else if (offs
< o
->offs
)
92 else if (offs
> o
->offs
)
95 ubifs_err(c
, "old idx added twice!");
100 rb_link_node(&old_idx
->rb
, parent
, p
);
101 rb_insert_color(&old_idx
->rb
, &c
->old_idx
);
106 * insert_old_idx_znode - record a znode obsoleted since last commit start.
107 * @c: UBIFS file-system description object
108 * @znode: znode of obsoleted index node
110 * Returns %0 on success, and a negative error code on failure.
112 int insert_old_idx_znode(struct ubifs_info
*c
, struct ubifs_znode
*znode
)
115 struct ubifs_zbranch
*zbr
;
117 zbr
= &znode
->parent
->zbranch
[znode
->iip
];
119 return insert_old_idx(c
, zbr
->lnum
, zbr
->offs
);
122 return insert_old_idx(c
, c
->zroot
.lnum
,
128 * ins_clr_old_idx_znode - record a znode obsoleted since last commit start.
129 * @c: UBIFS file-system description object
130 * @znode: znode of obsoleted index node
132 * Returns %0 on success, and a negative error code on failure.
134 static int ins_clr_old_idx_znode(struct ubifs_info
*c
,
135 struct ubifs_znode
*znode
)
140 struct ubifs_zbranch
*zbr
;
142 zbr
= &znode
->parent
->zbranch
[znode
->iip
];
144 err
= insert_old_idx(c
, zbr
->lnum
, zbr
->offs
);
153 err
= insert_old_idx(c
, c
->zroot
.lnum
, c
->zroot
.offs
);
164 * destroy_old_idx - destroy the old_idx RB-tree.
165 * @c: UBIFS file-system description object
167 * During start commit, the old_idx RB-tree is used to avoid overwriting index
168 * nodes that were in the index last commit but have since been deleted. This
169 * is necessary for recovery i.e. the old index must be kept intact until the
170 * new index is successfully written. The old-idx RB-tree is used for the
171 * in-the-gaps method of writing index nodes and is destroyed every commit.
173 void destroy_old_idx(struct ubifs_info
*c
)
175 struct ubifs_old_idx
*old_idx
, *n
;
177 rbtree_postorder_for_each_entry_safe(old_idx
, n
, &c
->old_idx
, rb
)
180 c
->old_idx
= RB_ROOT
;
184 * copy_znode - copy a dirty znode.
185 * @c: UBIFS file-system description object
186 * @znode: znode to copy
188 * A dirty znode being committed may not be changed, so it is copied.
190 static struct ubifs_znode
*copy_znode(struct ubifs_info
*c
,
191 struct ubifs_znode
*znode
)
193 struct ubifs_znode
*zn
;
195 zn
= kmalloc(c
->max_znode_sz
, GFP_NOFS
);
197 return ERR_PTR(-ENOMEM
);
199 memcpy(zn
, znode
, c
->max_znode_sz
);
201 __set_bit(DIRTY_ZNODE
, &zn
->flags
);
202 __clear_bit(COW_ZNODE
, &zn
->flags
);
204 ubifs_assert(!ubifs_zn_obsolete(znode
));
205 __set_bit(OBSOLETE_ZNODE
, &znode
->flags
);
207 if (znode
->level
!= 0) {
209 const int n
= zn
->child_cnt
;
211 /* The children now have new parent */
212 for (i
= 0; i
< n
; i
++) {
213 struct ubifs_zbranch
*zbr
= &zn
->zbranch
[i
];
216 zbr
->znode
->parent
= zn
;
220 atomic_long_inc(&c
->dirty_zn_cnt
);
225 * add_idx_dirt - add dirt due to a dirty znode.
226 * @c: UBIFS file-system description object
227 * @lnum: LEB number of index node
228 * @dirt: size of index node
230 * This function updates lprops dirty space and the new size of the index.
232 static int add_idx_dirt(struct ubifs_info
*c
, int lnum
, int dirt
)
234 c
->calc_idx_sz
-= ALIGN(dirt
, 8);
235 return ubifs_add_dirt(c
, lnum
, dirt
);
239 * dirty_cow_znode - ensure a znode is not being committed.
240 * @c: UBIFS file-system description object
241 * @zbr: branch of znode to check
243 * Returns dirtied znode on success or negative error code on failure.
245 static struct ubifs_znode
*dirty_cow_znode(struct ubifs_info
*c
,
246 struct ubifs_zbranch
*zbr
)
248 struct ubifs_znode
*znode
= zbr
->znode
;
249 struct ubifs_znode
*zn
;
252 if (!ubifs_zn_cow(znode
)) {
253 /* znode is not being committed */
254 if (!test_and_set_bit(DIRTY_ZNODE
, &znode
->flags
)) {
255 atomic_long_inc(&c
->dirty_zn_cnt
);
256 atomic_long_dec(&c
->clean_zn_cnt
);
257 atomic_long_dec(&ubifs_clean_zn_cnt
);
258 err
= add_idx_dirt(c
, zbr
->lnum
, zbr
->len
);
265 zn
= copy_znode(c
, znode
);
270 err
= insert_old_idx(c
, zbr
->lnum
, zbr
->offs
);
273 err
= add_idx_dirt(c
, zbr
->lnum
, zbr
->len
);
288 * lnc_add - add a leaf node to the leaf node cache.
289 * @c: UBIFS file-system description object
290 * @zbr: zbranch of leaf node
293 * Leaf nodes are non-index nodes directory entry nodes or data nodes. The
294 * purpose of the leaf node cache is to save re-reading the same leaf node over
295 * and over again. Most things are cached by VFS, however the file system must
296 * cache directory entries for readdir and for resolving hash collisions. The
297 * present implementation of the leaf node cache is extremely simple, and
298 * allows for error returns that are not used but that may be needed if a more
299 * complex implementation is created.
301 * Note, this function does not add the @node object to LNC directly, but
302 * allocates a copy of the object and adds the copy to LNC. The reason for this
303 * is that @node has been allocated outside of the TNC subsystem and will be
304 * used with @c->tnc_mutex unlock upon return from the TNC subsystem. But LNC
305 * may be changed at any time, e.g. freed by the shrinker.
307 static int lnc_add(struct ubifs_info
*c
, struct ubifs_zbranch
*zbr
,
312 const struct ubifs_dent_node
*dent
= node
;
314 ubifs_assert(!zbr
->leaf
);
315 ubifs_assert(zbr
->len
!= 0);
316 ubifs_assert(is_hash_key(c
, &zbr
->key
));
318 err
= ubifs_validate_entry(c
, dent
);
321 ubifs_dump_node(c
, dent
);
325 lnc_node
= kmemdup(node
, zbr
->len
, GFP_NOFS
);
327 /* We don't have to have the cache, so no error */
330 zbr
->leaf
= lnc_node
;
335 * lnc_add_directly - add a leaf node to the leaf-node-cache.
336 * @c: UBIFS file-system description object
337 * @zbr: zbranch of leaf node
340 * This function is similar to 'lnc_add()', but it does not create a copy of
341 * @node but inserts @node to TNC directly.
343 static int lnc_add_directly(struct ubifs_info
*c
, struct ubifs_zbranch
*zbr
,
348 ubifs_assert(!zbr
->leaf
);
349 ubifs_assert(zbr
->len
!= 0);
351 err
= ubifs_validate_entry(c
, node
);
354 ubifs_dump_node(c
, node
);
363 * lnc_free - remove a leaf node from the leaf node cache.
364 * @zbr: zbranch of leaf node
367 static void lnc_free(struct ubifs_zbranch
*zbr
)
376 * tnc_read_node_nm - read a "hashed" leaf node.
377 * @c: UBIFS file-system description object
378 * @zbr: key and position of the node
379 * @node: node is returned here
381 * This function reads a "hashed" node defined by @zbr from the leaf node cache
382 * (in it is there) or from the hash media, in which case the node is also
383 * added to LNC. Returns zero in case of success or a negative negative error
384 * code in case of failure.
386 static int tnc_read_node_nm(struct ubifs_info
*c
, struct ubifs_zbranch
*zbr
,
391 ubifs_assert(is_hash_key(c
, &zbr
->key
));
394 /* Read from the leaf node cache */
395 ubifs_assert(zbr
->len
!= 0);
396 memcpy(node
, zbr
->leaf
, zbr
->len
);
400 err
= ubifs_tnc_read_node(c
, zbr
, node
);
404 /* Add the node to the leaf node cache */
405 err
= lnc_add(c
, zbr
, node
);
410 * try_read_node - read a node if it is a node.
411 * @c: UBIFS file-system description object
412 * @buf: buffer to read to
414 * @len: node length (not aligned)
415 * @lnum: LEB number of node to read
416 * @offs: offset of node to read
418 * This function tries to read a node of known type and length, checks it and
419 * stores it in @buf. This function returns %1 if a node is present and %0 if
420 * a node is not present. A negative error code is returned for I/O errors.
421 * This function performs that same function as ubifs_read_node except that
422 * it does not require that there is actually a node present and instead
423 * the return code indicates if a node was read.
425 * Note, this function does not check CRC of data nodes if @c->no_chk_data_crc
426 * is true (it is controlled by corresponding mount option). However, if
427 * @c->mounting or @c->remounting_rw is true (we are mounting or re-mounting to
428 * R/W mode), @c->no_chk_data_crc is ignored and CRC is checked. This is
429 * because during mounting or re-mounting from R/O mode to R/W mode we may read
430 * journal nodes (when replying the journal or doing the recovery) and the
431 * journal nodes may potentially be corrupted, so checking is required.
433 static int try_read_node(const struct ubifs_info
*c
, void *buf
, int type
,
434 int len
, int lnum
, int offs
)
437 struct ubifs_ch
*ch
= buf
;
438 uint32_t crc
, node_crc
;
440 dbg_io("LEB %d:%d, %s, length %d", lnum
, offs
, dbg_ntype(type
), len
);
442 err
= ubifs_leb_read(c
, lnum
, buf
, offs
, len
, 1);
444 ubifs_err(c
, "cannot read node type %d from LEB %d:%d, error %d",
445 type
, lnum
, offs
, err
);
449 if (le32_to_cpu(ch
->magic
) != UBIFS_NODE_MAGIC
)
452 if (ch
->node_type
!= type
)
455 node_len
= le32_to_cpu(ch
->len
);
459 if (type
== UBIFS_DATA_NODE
&& c
->no_chk_data_crc
&& !c
->mounting
&&
463 crc
= crc32(UBIFS_CRC32_INIT
, buf
+ 8, node_len
- 8);
464 node_crc
= le32_to_cpu(ch
->crc
);
472 * fallible_read_node - try to read a leaf node.
473 * @c: UBIFS file-system description object
474 * @key: key of node to read
475 * @zbr: position of node
476 * @node: node returned
478 * This function tries to read a node and returns %1 if the node is read, %0
479 * if the node is not present, and a negative error code in the case of error.
481 static int fallible_read_node(struct ubifs_info
*c
, const union ubifs_key
*key
,
482 struct ubifs_zbranch
*zbr
, void *node
)
486 dbg_tnck(key
, "LEB %d:%d, key ", zbr
->lnum
, zbr
->offs
);
488 ret
= try_read_node(c
, node
, key_type(c
, key
), zbr
->len
, zbr
->lnum
,
491 union ubifs_key node_key
;
492 struct ubifs_dent_node
*dent
= node
;
494 /* All nodes have key in the same place */
495 key_read(c
, &dent
->key
, &node_key
);
496 if (keys_cmp(c
, key
, &node_key
) != 0)
499 if (ret
== 0 && c
->replaying
)
500 dbg_mntk(key
, "dangling branch LEB %d:%d len %d, key ",
501 zbr
->lnum
, zbr
->offs
, zbr
->len
);
506 * matches_name - determine if a direntry or xattr entry matches a given name.
507 * @c: UBIFS file-system description object
508 * @zbr: zbranch of dent
511 * This function checks if xentry/direntry referred by zbranch @zbr matches name
512 * @nm. Returns %NAME_MATCHES if it does, %NAME_LESS if the name referred by
513 * @zbr is less than @nm, and %NAME_GREATER if it is greater than @nm. In case
514 * of failure, a negative error code is returned.
516 static int matches_name(struct ubifs_info
*c
, struct ubifs_zbranch
*zbr
,
517 const struct qstr
*nm
)
519 struct ubifs_dent_node
*dent
;
522 /* If possible, match against the dent in the leaf node cache */
524 dent
= kmalloc(zbr
->len
, GFP_NOFS
);
528 err
= ubifs_tnc_read_node(c
, zbr
, dent
);
532 /* Add the node to the leaf node cache */
533 err
= lnc_add_directly(c
, zbr
, dent
);
539 nlen
= le16_to_cpu(dent
->nlen
);
540 err
= memcmp(dent
->name
, nm
->name
, min_t(int, nlen
, nm
->len
));
544 else if (nlen
< nm
->len
)
559 * get_znode - get a TNC znode that may not be loaded yet.
560 * @c: UBIFS file-system description object
561 * @znode: parent znode
562 * @n: znode branch slot number
564 * This function returns the znode or a negative error code.
566 static struct ubifs_znode
*get_znode(struct ubifs_info
*c
,
567 struct ubifs_znode
*znode
, int n
)
569 struct ubifs_zbranch
*zbr
;
571 zbr
= &znode
->zbranch
[n
];
575 znode
= ubifs_load_znode(c
, zbr
, znode
, n
);
580 * tnc_next - find next TNC entry.
581 * @c: UBIFS file-system description object
582 * @zn: znode is passed and returned here
583 * @n: znode branch slot number is passed and returned here
585 * This function returns %0 if the next TNC entry is found, %-ENOENT if there is
586 * no next entry, or a negative error code otherwise.
588 static int tnc_next(struct ubifs_info
*c
, struct ubifs_znode
**zn
, int *n
)
590 struct ubifs_znode
*znode
= *zn
;
594 if (nn
< znode
->child_cnt
) {
599 struct ubifs_znode
*zp
;
606 if (nn
< znode
->child_cnt
) {
607 znode
= get_znode(c
, znode
, nn
);
609 return PTR_ERR(znode
);
610 while (znode
->level
!= 0) {
611 znode
= get_znode(c
, znode
, 0);
613 return PTR_ERR(znode
);
625 * tnc_prev - find previous TNC entry.
626 * @c: UBIFS file-system description object
627 * @zn: znode is returned here
628 * @n: znode branch slot number is passed and returned here
630 * This function returns %0 if the previous TNC entry is found, %-ENOENT if
631 * there is no next entry, or a negative error code otherwise.
633 static int tnc_prev(struct ubifs_info
*c
, struct ubifs_znode
**zn
, int *n
)
635 struct ubifs_znode
*znode
= *zn
;
643 struct ubifs_znode
*zp
;
651 znode
= get_znode(c
, znode
, nn
);
653 return PTR_ERR(znode
);
654 while (znode
->level
!= 0) {
655 nn
= znode
->child_cnt
- 1;
656 znode
= get_znode(c
, znode
, nn
);
658 return PTR_ERR(znode
);
660 nn
= znode
->child_cnt
- 1;
670 * resolve_collision - resolve a collision.
671 * @c: UBIFS file-system description object
672 * @key: key of a directory or extended attribute entry
673 * @zn: znode is returned here
674 * @n: zbranch number is passed and returned here
675 * @nm: name of the entry
677 * This function is called for "hashed" keys to make sure that the found key
678 * really corresponds to the looked up node (directory or extended attribute
679 * entry). It returns %1 and sets @zn and @n if the collision is resolved.
680 * %0 is returned if @nm is not found and @zn and @n are set to the previous
681 * entry, i.e. to the entry after which @nm could follow if it were in TNC.
682 * This means that @n may be set to %-1 if the leftmost key in @zn is the
683 * previous one. A negative error code is returned on failures.
685 static int resolve_collision(struct ubifs_info
*c
, const union ubifs_key
*key
,
686 struct ubifs_znode
**zn
, int *n
,
687 const struct qstr
*nm
)
691 err
= matches_name(c
, &(*zn
)->zbranch
[*n
], nm
);
692 if (unlikely(err
< 0))
694 if (err
== NAME_MATCHES
)
697 if (err
== NAME_GREATER
) {
700 err
= tnc_prev(c
, zn
, n
);
701 if (err
== -ENOENT
) {
702 ubifs_assert(*n
== 0);
708 if (keys_cmp(c
, &(*zn
)->zbranch
[*n
].key
, key
)) {
710 * We have found the branch after which we would
711 * like to insert, but inserting in this znode
712 * may still be wrong. Consider the following 3
713 * znodes, in the case where we are resolving a
714 * collision with Key2.
717 * ----------------------
718 * level 1 | Key0 | Key1 |
719 * -----------------------
721 * znode za | | znode zb
722 * ------------ ------------
723 * level 0 | Key0 | | Key2 |
724 * ------------ ------------
726 * The lookup finds Key2 in znode zb. Lets say
727 * there is no match and the name is greater so
728 * we look left. When we find Key0, we end up
729 * here. If we return now, we will insert into
730 * znode za at slot n = 1. But that is invalid
731 * according to the parent's keys. Key2 must
732 * be inserted into znode zb.
734 * Note, this problem is not relevant for the
735 * case when we go right, because
736 * 'tnc_insert()' would correct the parent key.
738 if (*n
== (*zn
)->child_cnt
- 1) {
739 err
= tnc_next(c
, zn
, n
);
741 /* Should be impossible */
747 ubifs_assert(*n
== 0);
752 err
= matches_name(c
, &(*zn
)->zbranch
[*n
], nm
);
755 if (err
== NAME_LESS
)
757 if (err
== NAME_MATCHES
)
759 ubifs_assert(err
== NAME_GREATER
);
763 struct ubifs_znode
*znode
= *zn
;
767 err
= tnc_next(c
, &znode
, &nn
);
772 if (keys_cmp(c
, &znode
->zbranch
[nn
].key
, key
))
774 err
= matches_name(c
, &znode
->zbranch
[nn
], nm
);
777 if (err
== NAME_GREATER
)
781 if (err
== NAME_MATCHES
)
783 ubifs_assert(err
== NAME_LESS
);
789 * fallible_matches_name - determine if a dent matches a given name.
790 * @c: UBIFS file-system description object
791 * @zbr: zbranch of dent
794 * This is a "fallible" version of 'matches_name()' function which does not
795 * panic if the direntry/xentry referred by @zbr does not exist on the media.
797 * This function checks if xentry/direntry referred by zbranch @zbr matches name
798 * @nm. Returns %NAME_MATCHES it does, %NAME_LESS if the name referred by @zbr
799 * is less than @nm, %NAME_GREATER if it is greater than @nm, and @NOT_ON_MEDIA
800 * if xentry/direntry referred by @zbr does not exist on the media. A negative
801 * error code is returned in case of failure.
803 static int fallible_matches_name(struct ubifs_info
*c
,
804 struct ubifs_zbranch
*zbr
,
805 const struct qstr
*nm
)
807 struct ubifs_dent_node
*dent
;
810 /* If possible, match against the dent in the leaf node cache */
812 dent
= kmalloc(zbr
->len
, GFP_NOFS
);
816 err
= fallible_read_node(c
, &zbr
->key
, zbr
, dent
);
820 /* The node was not present */
824 ubifs_assert(err
== 1);
826 err
= lnc_add_directly(c
, zbr
, dent
);
832 nlen
= le16_to_cpu(dent
->nlen
);
833 err
= memcmp(dent
->name
, nm
->name
, min_t(int, nlen
, nm
->len
));
837 else if (nlen
< nm
->len
)
852 * fallible_resolve_collision - resolve a collision even if nodes are missing.
853 * @c: UBIFS file-system description object
855 * @zn: znode is returned here
856 * @n: branch number is passed and returned here
857 * @nm: name of directory entry
858 * @adding: indicates caller is adding a key to the TNC
860 * This is a "fallible" version of the 'resolve_collision()' function which
861 * does not panic if one of the nodes referred to by TNC does not exist on the
862 * media. This may happen when replaying the journal if a deleted node was
863 * Garbage-collected and the commit was not done. A branch that refers to a node
864 * that is not present is called a dangling branch. The following are the return
865 * codes for this function:
866 * o if @nm was found, %1 is returned and @zn and @n are set to the found
868 * o if we are @adding and @nm was not found, %0 is returned;
869 * o if we are not @adding and @nm was not found, but a dangling branch was
870 * found, then %1 is returned and @zn and @n are set to the dangling branch;
871 * o a negative error code is returned in case of failure.
873 static int fallible_resolve_collision(struct ubifs_info
*c
,
874 const union ubifs_key
*key
,
875 struct ubifs_znode
**zn
, int *n
,
876 const struct qstr
*nm
, int adding
)
878 struct ubifs_znode
*o_znode
= NULL
, *znode
= *zn
;
879 int uninitialized_var(o_n
), err
, cmp
, unsure
= 0, nn
= *n
;
881 cmp
= fallible_matches_name(c
, &znode
->zbranch
[nn
], nm
);
882 if (unlikely(cmp
< 0))
884 if (cmp
== NAME_MATCHES
)
886 if (cmp
== NOT_ON_MEDIA
) {
890 * We are unlucky and hit a dangling branch straight away.
891 * Now we do not really know where to go to find the needed
892 * branch - to the left or to the right. Well, let's try left.
896 unsure
= 1; /* Remove a dangling branch wherever it is */
898 if (cmp
== NAME_GREATER
|| unsure
) {
901 err
= tnc_prev(c
, zn
, n
);
902 if (err
== -ENOENT
) {
903 ubifs_assert(*n
== 0);
909 if (keys_cmp(c
, &(*zn
)->zbranch
[*n
].key
, key
)) {
910 /* See comments in 'resolve_collision()' */
911 if (*n
== (*zn
)->child_cnt
- 1) {
912 err
= tnc_next(c
, zn
, n
);
914 /* Should be impossible */
920 ubifs_assert(*n
== 0);
925 err
= fallible_matches_name(c
, &(*zn
)->zbranch
[*n
], nm
);
928 if (err
== NAME_MATCHES
)
930 if (err
== NOT_ON_MEDIA
) {
937 if (err
== NAME_LESS
)
944 if (cmp
== NAME_LESS
|| unsure
) {
949 err
= tnc_next(c
, &znode
, &nn
);
954 if (keys_cmp(c
, &znode
->zbranch
[nn
].key
, key
))
956 err
= fallible_matches_name(c
, &znode
->zbranch
[nn
], nm
);
959 if (err
== NAME_GREATER
)
963 if (err
== NAME_MATCHES
)
965 if (err
== NOT_ON_MEDIA
) {
972 /* Never match a dangling branch when adding */
973 if (adding
|| !o_znode
)
976 dbg_mntk(key
, "dangling match LEB %d:%d len %d key ",
977 o_znode
->zbranch
[o_n
].lnum
, o_znode
->zbranch
[o_n
].offs
,
978 o_znode
->zbranch
[o_n
].len
);
985 * matches_position - determine if a zbranch matches a given position.
986 * @zbr: zbranch of dent
987 * @lnum: LEB number of dent to match
988 * @offs: offset of dent to match
990 * This function returns %1 if @lnum:@offs matches, and %0 otherwise.
992 static int matches_position(struct ubifs_zbranch
*zbr
, int lnum
, int offs
)
994 if (zbr
->lnum
== lnum
&& zbr
->offs
== offs
)
1001 * resolve_collision_directly - resolve a collision directly.
1002 * @c: UBIFS file-system description object
1003 * @key: key of directory entry
1004 * @zn: znode is passed and returned here
1005 * @n: zbranch number is passed and returned here
1006 * @lnum: LEB number of dent node to match
1007 * @offs: offset of dent node to match
1009 * This function is used for "hashed" keys to make sure the found directory or
1010 * extended attribute entry node is what was looked for. It is used when the
1011 * flash address of the right node is known (@lnum:@offs) which makes it much
1012 * easier to resolve collisions (no need to read entries and match full
1013 * names). This function returns %1 and sets @zn and @n if the collision is
1014 * resolved, %0 if @lnum:@offs is not found and @zn and @n are set to the
1015 * previous directory entry. Otherwise a negative error code is returned.
1017 static int resolve_collision_directly(struct ubifs_info
*c
,
1018 const union ubifs_key
*key
,
1019 struct ubifs_znode
**zn
, int *n
,
1022 struct ubifs_znode
*znode
;
1027 if (matches_position(&znode
->zbranch
[nn
], lnum
, offs
))
1032 err
= tnc_prev(c
, &znode
, &nn
);
1037 if (keys_cmp(c
, &znode
->zbranch
[nn
].key
, key
))
1039 if (matches_position(&znode
->zbranch
[nn
], lnum
, offs
)) {
1050 err
= tnc_next(c
, &znode
, &nn
);
1055 if (keys_cmp(c
, &znode
->zbranch
[nn
].key
, key
))
1059 if (matches_position(&znode
->zbranch
[nn
], lnum
, offs
))
1065 * dirty_cow_bottom_up - dirty a znode and its ancestors.
1066 * @c: UBIFS file-system description object
1067 * @znode: znode to dirty
1069 * If we do not have a unique key that resides in a znode, then we cannot
1070 * dirty that znode from the top down (i.e. by using lookup_level0_dirty)
1071 * This function records the path back to the last dirty ancestor, and then
1072 * dirties the znodes on that path.
1074 static struct ubifs_znode
*dirty_cow_bottom_up(struct ubifs_info
*c
,
1075 struct ubifs_znode
*znode
)
1077 struct ubifs_znode
*zp
;
1078 int *path
= c
->bottom_up_buf
, p
= 0;
1080 ubifs_assert(c
->zroot
.znode
);
1081 ubifs_assert(znode
);
1082 if (c
->zroot
.znode
->level
> BOTTOM_UP_HEIGHT
) {
1083 kfree(c
->bottom_up_buf
);
1084 c
->bottom_up_buf
= kmalloc(c
->zroot
.znode
->level
* sizeof(int),
1086 if (!c
->bottom_up_buf
)
1087 return ERR_PTR(-ENOMEM
);
1088 path
= c
->bottom_up_buf
;
1090 if (c
->zroot
.znode
->level
) {
1091 /* Go up until parent is dirty */
1099 ubifs_assert(p
< c
->zroot
.znode
->level
);
1101 if (!zp
->cnext
&& ubifs_zn_dirty(znode
))
1107 /* Come back down, dirtying as we go */
1109 struct ubifs_zbranch
*zbr
;
1113 ubifs_assert(path
[p
- 1] >= 0);
1114 ubifs_assert(path
[p
- 1] < zp
->child_cnt
);
1115 zbr
= &zp
->zbranch
[path
[--p
]];
1116 znode
= dirty_cow_znode(c
, zbr
);
1118 ubifs_assert(znode
== c
->zroot
.znode
);
1119 znode
= dirty_cow_znode(c
, &c
->zroot
);
1121 if (IS_ERR(znode
) || !p
)
1123 ubifs_assert(path
[p
- 1] >= 0);
1124 ubifs_assert(path
[p
- 1] < znode
->child_cnt
);
1125 znode
= znode
->zbranch
[path
[p
- 1]].znode
;
1132 * ubifs_lookup_level0 - search for zero-level znode.
1133 * @c: UBIFS file-system description object
1134 * @key: key to lookup
1135 * @zn: znode is returned here
1136 * @n: znode branch slot number is returned here
1138 * This function looks up the TNC tree and search for zero-level znode which
1139 * refers key @key. The found zero-level znode is returned in @zn. There are 3
1141 * o exact match, i.e. the found zero-level znode contains key @key, then %1
1142 * is returned and slot number of the matched branch is stored in @n;
1143 * o not exact match, which means that zero-level znode does not contain
1144 * @key, then %0 is returned and slot number of the closest branch is stored
1146 * o @key is so small that it is even less than the lowest key of the
1147 * leftmost zero-level node, then %0 is returned and %0 is stored in @n.
1149 * Note, when the TNC tree is traversed, some znodes may be absent, then this
1150 * function reads corresponding indexing nodes and inserts them to TNC. In
1151 * case of failure, a negative error code is returned.
1153 int ubifs_lookup_level0(struct ubifs_info
*c
, const union ubifs_key
*key
,
1154 struct ubifs_znode
**zn
, int *n
)
1157 struct ubifs_znode
*znode
;
1158 unsigned long time
= get_seconds();
1160 dbg_tnck(key
, "search key ");
1161 ubifs_assert(key_type(c
, key
) < UBIFS_INVALID_KEY
);
1163 znode
= c
->zroot
.znode
;
1164 if (unlikely(!znode
)) {
1165 znode
= ubifs_load_znode(c
, &c
->zroot
, NULL
, 0);
1167 return PTR_ERR(znode
);
1173 struct ubifs_zbranch
*zbr
;
1175 exact
= ubifs_search_zbranch(c
, znode
, key
, n
);
1177 if (znode
->level
== 0)
1182 zbr
= &znode
->zbranch
[*n
];
1190 /* znode is not in TNC cache, load it from the media */
1191 znode
= ubifs_load_znode(c
, zbr
, znode
, *n
);
1193 return PTR_ERR(znode
);
1197 if (exact
|| !is_hash_key(c
, key
) || *n
!= -1) {
1198 dbg_tnc("found %d, lvl %d, n %d", exact
, znode
->level
, *n
);
1203 * Here is a tricky place. We have not found the key and this is a
1204 * "hashed" key, which may collide. The rest of the code deals with
1205 * situations like this:
1209 * | 3 | 5 | | 6 | 7 | (x)
1211 * Or more a complex example:
1215 * | 1 | 3 | | 5 | 8 |
1217 * | 5 | 5 | | 6 | 7 | (x)
1219 * In the examples, if we are looking for key "5", we may reach nodes
1220 * marked with "(x)". In this case what we have do is to look at the
1221 * left and see if there is "5" key there. If there is, we have to
1224 * Note, this whole situation is possible because we allow to have
1225 * elements which are equivalent to the next key in the parent in the
1226 * children of current znode. For example, this happens if we split a
1227 * znode like this: | 3 | 5 | 5 | 6 | 7 |, which results in something
1231 * | 3 | 5 | | 5 | 6 | 7 |
1233 * And this becomes what is at the first "picture" after key "5" marked
1234 * with "^" is removed. What could be done is we could prohibit
1235 * splitting in the middle of the colliding sequence. Also, when
1236 * removing the leftmost key, we would have to correct the key of the
1237 * parent node, which would introduce additional complications. Namely,
1238 * if we changed the leftmost key of the parent znode, the garbage
1239 * collector would be unable to find it (GC is doing this when GC'ing
1240 * indexing LEBs). Although we already have an additional RB-tree where
1241 * we save such changed znodes (see 'ins_clr_old_idx_znode()') until
1242 * after the commit. But anyway, this does not look easy to implement
1243 * so we did not try this.
1245 err
= tnc_prev(c
, &znode
, n
);
1246 if (err
== -ENOENT
) {
1247 dbg_tnc("found 0, lvl %d, n -1", znode
->level
);
1251 if (unlikely(err
< 0))
1253 if (keys_cmp(c
, key
, &znode
->zbranch
[*n
].key
)) {
1254 dbg_tnc("found 0, lvl %d, n -1", znode
->level
);
1259 dbg_tnc("found 1, lvl %d, n %d", znode
->level
, *n
);
1265 * lookup_level0_dirty - search for zero-level znode dirtying.
1266 * @c: UBIFS file-system description object
1267 * @key: key to lookup
1268 * @zn: znode is returned here
1269 * @n: znode branch slot number is returned here
1271 * This function looks up the TNC tree and search for zero-level znode which
1272 * refers key @key. The found zero-level znode is returned in @zn. There are 3
1274 * o exact match, i.e. the found zero-level znode contains key @key, then %1
1275 * is returned and slot number of the matched branch is stored in @n;
1276 * o not exact match, which means that zero-level znode does not contain @key
1277 * then %0 is returned and slot number of the closed branch is stored in
1279 * o @key is so small that it is even less than the lowest key of the
1280 * leftmost zero-level node, then %0 is returned and %-1 is stored in @n.
1282 * Additionally all znodes in the path from the root to the located zero-level
1283 * znode are marked as dirty.
1285 * Note, when the TNC tree is traversed, some znodes may be absent, then this
1286 * function reads corresponding indexing nodes and inserts them to TNC. In
1287 * case of failure, a negative error code is returned.
1289 static int lookup_level0_dirty(struct ubifs_info
*c
, const union ubifs_key
*key
,
1290 struct ubifs_znode
**zn
, int *n
)
1293 struct ubifs_znode
*znode
;
1294 unsigned long time
= get_seconds();
1296 dbg_tnck(key
, "search and dirty key ");
1298 znode
= c
->zroot
.znode
;
1299 if (unlikely(!znode
)) {
1300 znode
= ubifs_load_znode(c
, &c
->zroot
, NULL
, 0);
1302 return PTR_ERR(znode
);
1305 znode
= dirty_cow_znode(c
, &c
->zroot
);
1307 return PTR_ERR(znode
);
1312 struct ubifs_zbranch
*zbr
;
1314 exact
= ubifs_search_zbranch(c
, znode
, key
, n
);
1316 if (znode
->level
== 0)
1321 zbr
= &znode
->zbranch
[*n
];
1325 znode
= dirty_cow_znode(c
, zbr
);
1327 return PTR_ERR(znode
);
1331 /* znode is not in TNC cache, load it from the media */
1332 znode
= ubifs_load_znode(c
, zbr
, znode
, *n
);
1334 return PTR_ERR(znode
);
1335 znode
= dirty_cow_znode(c
, zbr
);
1337 return PTR_ERR(znode
);
1341 if (exact
|| !is_hash_key(c
, key
) || *n
!= -1) {
1342 dbg_tnc("found %d, lvl %d, n %d", exact
, znode
->level
, *n
);
1347 * See huge comment at 'lookup_level0_dirty()' what is the rest of the
1350 err
= tnc_prev(c
, &znode
, n
);
1351 if (err
== -ENOENT
) {
1353 dbg_tnc("found 0, lvl %d, n -1", znode
->level
);
1356 if (unlikely(err
< 0))
1358 if (keys_cmp(c
, key
, &znode
->zbranch
[*n
].key
)) {
1360 dbg_tnc("found 0, lvl %d, n -1", znode
->level
);
1364 if (znode
->cnext
|| !ubifs_zn_dirty(znode
)) {
1365 znode
= dirty_cow_bottom_up(c
, znode
);
1367 return PTR_ERR(znode
);
1370 dbg_tnc("found 1, lvl %d, n %d", znode
->level
, *n
);
1376 * maybe_leb_gced - determine if a LEB may have been garbage collected.
1377 * @c: UBIFS file-system description object
1379 * @gc_seq1: garbage collection sequence number
1381 * This function determines if @lnum may have been garbage collected since
1382 * sequence number @gc_seq1. If it may have been then %1 is returned, otherwise
1385 static int maybe_leb_gced(struct ubifs_info
*c
, int lnum
, int gc_seq1
)
1388 int gc_seq2
, gced_lnum
;
1390 gced_lnum
= c
->gced_lnum
;
1392 gc_seq2
= c
->gc_seq
;
1393 /* Same seq means no GC */
1394 if (gc_seq1
== gc_seq2
)
1396 /* Different by more than 1 means we don't know */
1397 if (gc_seq1
+ 1 != gc_seq2
)
1400 * We have seen the sequence number has increased by 1. Now we need to
1401 * be sure we read the right LEB number, so read it again.
1404 if (gced_lnum
!= c
->gced_lnum
)
1406 /* Finally we can check lnum */
1407 if (gced_lnum
== lnum
)
1410 /* No garbage collection in the read-only U-Boot implementation */
1416 * ubifs_tnc_locate - look up a file-system node and return it and its location.
1417 * @c: UBIFS file-system description object
1418 * @key: node key to lookup
1419 * @node: the node is returned here
1420 * @lnum: LEB number is returned here
1421 * @offs: offset is returned here
1423 * This function looks up and reads node with key @key. The caller has to make
1424 * sure the @node buffer is large enough to fit the node. Returns zero in case
1425 * of success, %-ENOENT if the node was not found, and a negative error code in
1426 * case of failure. The node location can be returned in @lnum and @offs.
1428 int ubifs_tnc_locate(struct ubifs_info
*c
, const union ubifs_key
*key
,
1429 void *node
, int *lnum
, int *offs
)
1431 int found
, n
, err
, safely
= 0, gc_seq1
;
1432 struct ubifs_znode
*znode
;
1433 struct ubifs_zbranch zbr
, *zt
;
1436 mutex_lock(&c
->tnc_mutex
);
1437 found
= ubifs_lookup_level0(c
, key
, &znode
, &n
);
1441 } else if (found
< 0) {
1445 zt
= &znode
->zbranch
[n
];
1450 if (is_hash_key(c
, key
)) {
1452 * In this case the leaf node cache gets used, so we pass the
1453 * address of the zbranch and keep the mutex locked
1455 err
= tnc_read_node_nm(c
, zt
, node
);
1459 err
= ubifs_tnc_read_node(c
, zt
, node
);
1462 /* Drop the TNC mutex prematurely and race with garbage collection */
1463 zbr
= znode
->zbranch
[n
];
1464 gc_seq1
= c
->gc_seq
;
1465 mutex_unlock(&c
->tnc_mutex
);
1467 if (ubifs_get_wbuf(c
, zbr
.lnum
)) {
1468 /* We do not GC journal heads */
1469 err
= ubifs_tnc_read_node(c
, &zbr
, node
);
1473 err
= fallible_read_node(c
, key
, &zbr
, node
);
1474 if (err
<= 0 || maybe_leb_gced(c
, zbr
.lnum
, gc_seq1
)) {
1476 * The node may have been GC'ed out from under us so try again
1477 * while keeping the TNC mutex locked.
1485 mutex_unlock(&c
->tnc_mutex
);
1490 * ubifs_tnc_get_bu_keys - lookup keys for bulk-read.
1491 * @c: UBIFS file-system description object
1492 * @bu: bulk-read parameters and results
1494 * Lookup consecutive data node keys for the same inode that reside
1495 * consecutively in the same LEB. This function returns zero in case of success
1496 * and a negative error code in case of failure.
1498 * Note, if the bulk-read buffer length (@bu->buf_len) is known, this function
1499 * makes sure bulk-read nodes fit the buffer. Otherwise, this function prepares
1500 * maximum possible amount of nodes for bulk-read.
1502 int ubifs_tnc_get_bu_keys(struct ubifs_info
*c
, struct bu_info
*bu
)
1504 int n
, err
= 0, lnum
= -1, uninitialized_var(offs
);
1505 int uninitialized_var(len
);
1506 unsigned int block
= key_block(c
, &bu
->key
);
1507 struct ubifs_znode
*znode
;
1513 mutex_lock(&c
->tnc_mutex
);
1514 /* Find first key */
1515 err
= ubifs_lookup_level0(c
, &bu
->key
, &znode
, &n
);
1520 len
= znode
->zbranch
[n
].len
;
1521 /* The buffer must be big enough for at least 1 node */
1522 if (len
> bu
->buf_len
) {
1527 bu
->zbranch
[bu
->cnt
++] = znode
->zbranch
[n
];
1529 lnum
= znode
->zbranch
[n
].lnum
;
1530 offs
= ALIGN(znode
->zbranch
[n
].offs
+ len
, 8);
1533 struct ubifs_zbranch
*zbr
;
1534 union ubifs_key
*key
;
1535 unsigned int next_block
;
1538 err
= tnc_next(c
, &znode
, &n
);
1541 zbr
= &znode
->zbranch
[n
];
1543 /* See if there is another data key for this file */
1544 if (key_inum(c
, key
) != key_inum(c
, &bu
->key
) ||
1545 key_type(c
, key
) != UBIFS_DATA_KEY
) {
1550 /* First key found */
1552 offs
= ALIGN(zbr
->offs
+ zbr
->len
, 8);
1554 if (len
> bu
->buf_len
) {
1560 * The data nodes must be in consecutive positions in
1563 if (zbr
->lnum
!= lnum
|| zbr
->offs
!= offs
)
1565 offs
+= ALIGN(zbr
->len
, 8);
1566 len
= ALIGN(len
, 8) + zbr
->len
;
1567 /* Must not exceed buffer length */
1568 if (len
> bu
->buf_len
)
1571 /* Allow for holes */
1572 next_block
= key_block(c
, key
);
1573 bu
->blk_cnt
+= (next_block
- block
- 1);
1574 if (bu
->blk_cnt
>= UBIFS_MAX_BULK_READ
)
1578 bu
->zbranch
[bu
->cnt
++] = *zbr
;
1580 /* See if we have room for more */
1581 if (bu
->cnt
>= UBIFS_MAX_BULK_READ
)
1583 if (bu
->blk_cnt
>= UBIFS_MAX_BULK_READ
)
1587 if (err
== -ENOENT
) {
1591 bu
->gc_seq
= c
->gc_seq
;
1592 mutex_unlock(&c
->tnc_mutex
);
1596 * An enormous hole could cause bulk-read to encompass too many
1597 * page cache pages, so limit the number here.
1599 if (bu
->blk_cnt
> UBIFS_MAX_BULK_READ
)
1600 bu
->blk_cnt
= UBIFS_MAX_BULK_READ
;
1602 * Ensure that bulk-read covers a whole number of page cache
1605 if (UBIFS_BLOCKS_PER_PAGE
== 1 ||
1606 !(bu
->blk_cnt
& (UBIFS_BLOCKS_PER_PAGE
- 1)))
1609 /* At the end of file we can round up */
1610 bu
->blk_cnt
+= UBIFS_BLOCKS_PER_PAGE
- 1;
1613 /* Exclude data nodes that do not make up a whole page cache page */
1614 block
= key_block(c
, &bu
->key
) + bu
->blk_cnt
;
1615 block
&= ~(UBIFS_BLOCKS_PER_PAGE
- 1);
1617 if (key_block(c
, &bu
->zbranch
[bu
->cnt
- 1].key
) < block
)
1625 * read_wbuf - bulk-read from a LEB with a wbuf.
1626 * @wbuf: wbuf that may overlap the read
1627 * @buf: buffer into which to read
1629 * @lnum: LEB number from which to read
1630 * @offs: offset from which to read
1632 * This functions returns %0 on success or a negative error code on failure.
1634 static int read_wbuf(struct ubifs_wbuf
*wbuf
, void *buf
, int len
, int lnum
,
1637 const struct ubifs_info
*c
= wbuf
->c
;
1640 dbg_io("LEB %d:%d, length %d", lnum
, offs
, len
);
1641 ubifs_assert(wbuf
&& lnum
>= 0 && lnum
< c
->leb_cnt
&& offs
>= 0);
1642 ubifs_assert(!(offs
& 7) && offs
< c
->leb_size
);
1643 ubifs_assert(offs
+ len
<= c
->leb_size
);
1645 spin_lock(&wbuf
->lock
);
1646 overlap
= (lnum
== wbuf
->lnum
&& offs
+ len
> wbuf
->offs
);
1648 /* We may safely unlock the write-buffer and read the data */
1649 spin_unlock(&wbuf
->lock
);
1650 return ubifs_leb_read(c
, lnum
, buf
, offs
, len
, 0);
1653 /* Don't read under wbuf */
1654 rlen
= wbuf
->offs
- offs
;
1658 /* Copy the rest from the write-buffer */
1659 memcpy(buf
+ rlen
, wbuf
->buf
+ offs
+ rlen
- wbuf
->offs
, len
- rlen
);
1660 spin_unlock(&wbuf
->lock
);
1663 /* Read everything that goes before write-buffer */
1664 return ubifs_leb_read(c
, lnum
, buf
, offs
, rlen
, 0);
1670 * validate_data_node - validate data nodes for bulk-read.
1671 * @c: UBIFS file-system description object
1672 * @buf: buffer containing data node to validate
1673 * @zbr: zbranch of data node to validate
1675 * This functions returns %0 on success or a negative error code on failure.
1677 static int validate_data_node(struct ubifs_info
*c
, void *buf
,
1678 struct ubifs_zbranch
*zbr
)
1680 union ubifs_key key1
;
1681 struct ubifs_ch
*ch
= buf
;
1684 if (ch
->node_type
!= UBIFS_DATA_NODE
) {
1685 ubifs_err(c
, "bad node type (%d but expected %d)",
1686 ch
->node_type
, UBIFS_DATA_NODE
);
1690 err
= ubifs_check_node(c
, buf
, zbr
->lnum
, zbr
->offs
, 0, 0);
1692 ubifs_err(c
, "expected node type %d", UBIFS_DATA_NODE
);
1696 len
= le32_to_cpu(ch
->len
);
1697 if (len
!= zbr
->len
) {
1698 ubifs_err(c
, "bad node length %d, expected %d", len
, zbr
->len
);
1702 /* Make sure the key of the read node is correct */
1703 key_read(c
, buf
+ UBIFS_KEY_OFFSET
, &key1
);
1704 if (!keys_eq(c
, &zbr
->key
, &key1
)) {
1705 ubifs_err(c
, "bad key in node at LEB %d:%d",
1706 zbr
->lnum
, zbr
->offs
);
1707 dbg_tnck(&zbr
->key
, "looked for key ");
1708 dbg_tnck(&key1
, "found node's key ");
1717 ubifs_err(c
, "bad node at LEB %d:%d", zbr
->lnum
, zbr
->offs
);
1718 ubifs_dump_node(c
, buf
);
1724 * ubifs_tnc_bulk_read - read a number of data nodes in one go.
1725 * @c: UBIFS file-system description object
1726 * @bu: bulk-read parameters and results
1728 * This functions reads and validates the data nodes that were identified by the
1729 * 'ubifs_tnc_get_bu_keys()' function. This functions returns %0 on success,
1730 * -EAGAIN to indicate a race with GC, or another negative error code on
1733 int ubifs_tnc_bulk_read(struct ubifs_info
*c
, struct bu_info
*bu
)
1735 int lnum
= bu
->zbranch
[0].lnum
, offs
= bu
->zbranch
[0].offs
, len
, err
, i
;
1736 struct ubifs_wbuf
*wbuf
;
1739 len
= bu
->zbranch
[bu
->cnt
- 1].offs
;
1740 len
+= bu
->zbranch
[bu
->cnt
- 1].len
- offs
;
1741 if (len
> bu
->buf_len
) {
1742 ubifs_err(c
, "buffer too small %d vs %d", bu
->buf_len
, len
);
1747 wbuf
= ubifs_get_wbuf(c
, lnum
);
1749 err
= read_wbuf(wbuf
, bu
->buf
, len
, lnum
, offs
);
1751 err
= ubifs_leb_read(c
, lnum
, bu
->buf
, offs
, len
, 0);
1753 /* Check for a race with GC */
1754 if (maybe_leb_gced(c
, lnum
, bu
->gc_seq
))
1757 if (err
&& err
!= -EBADMSG
) {
1758 ubifs_err(c
, "failed to read from LEB %d:%d, error %d",
1761 dbg_tnck(&bu
->key
, "key ");
1765 /* Validate the nodes read */
1767 for (i
= 0; i
< bu
->cnt
; i
++) {
1768 err
= validate_data_node(c
, buf
, &bu
->zbranch
[i
]);
1771 buf
= buf
+ ALIGN(bu
->zbranch
[i
].len
, 8);
1778 * do_lookup_nm- look up a "hashed" node.
1779 * @c: UBIFS file-system description object
1780 * @key: node key to lookup
1781 * @node: the node is returned here
1784 * This function look up and reads a node which contains name hash in the key.
1785 * Since the hash may have collisions, there may be many nodes with the same
1786 * key, so we have to sequentially look to all of them until the needed one is
1787 * found. This function returns zero in case of success, %-ENOENT if the node
1788 * was not found, and a negative error code in case of failure.
1790 static int do_lookup_nm(struct ubifs_info
*c
, const union ubifs_key
*key
,
1791 void *node
, const struct qstr
*nm
)
1794 struct ubifs_znode
*znode
;
1796 dbg_tnck(key
, "name '%.*s' key ", nm
->len
, nm
->name
);
1797 mutex_lock(&c
->tnc_mutex
);
1798 found
= ubifs_lookup_level0(c
, key
, &znode
, &n
);
1802 } else if (found
< 0) {
1807 ubifs_assert(n
>= 0);
1809 err
= resolve_collision(c
, key
, &znode
, &n
, nm
);
1810 dbg_tnc("rc returned %d, znode %p, n %d", err
, znode
, n
);
1811 if (unlikely(err
< 0))
1818 err
= tnc_read_node_nm(c
, &znode
->zbranch
[n
], node
);
1821 mutex_unlock(&c
->tnc_mutex
);
1826 * ubifs_tnc_lookup_nm - look up a "hashed" node.
1827 * @c: UBIFS file-system description object
1828 * @key: node key to lookup
1829 * @node: the node is returned here
1832 * This function look up and reads a node which contains name hash in the key.
1833 * Since the hash may have collisions, there may be many nodes with the same
1834 * key, so we have to sequentially look to all of them until the needed one is
1835 * found. This function returns zero in case of success, %-ENOENT if the node
1836 * was not found, and a negative error code in case of failure.
1838 int ubifs_tnc_lookup_nm(struct ubifs_info
*c
, const union ubifs_key
*key
,
1839 void *node
, const struct qstr
*nm
)
1842 const struct ubifs_dent_node
*dent
= node
;
1845 * We assume that in most of the cases there are no name collisions and
1846 * 'ubifs_tnc_lookup()' returns us the right direntry.
1848 err
= ubifs_tnc_lookup(c
, key
, node
);
1852 len
= le16_to_cpu(dent
->nlen
);
1853 if (nm
->len
== len
&& !memcmp(dent
->name
, nm
->name
, len
))
1857 * Unluckily, there are hash collisions and we have to iterate over
1858 * them look at each direntry with colliding name hash sequentially.
1860 return do_lookup_nm(c
, key
, node
, nm
);
1864 * correct_parent_keys - correct parent znodes' keys.
1865 * @c: UBIFS file-system description object
1866 * @znode: znode to correct parent znodes for
1868 * This is a helper function for 'tnc_insert()'. When the key of the leftmost
1869 * zbranch changes, keys of parent znodes have to be corrected. This helper
1870 * function is called in such situations and corrects the keys if needed.
1872 static void correct_parent_keys(const struct ubifs_info
*c
,
1873 struct ubifs_znode
*znode
)
1875 union ubifs_key
*key
, *key1
;
1877 ubifs_assert(znode
->parent
);
1878 ubifs_assert(znode
->iip
== 0);
1880 key
= &znode
->zbranch
[0].key
;
1881 key1
= &znode
->parent
->zbranch
[0].key
;
1883 while (keys_cmp(c
, key
, key1
) < 0) {
1884 key_copy(c
, key
, key1
);
1885 znode
= znode
->parent
;
1887 if (!znode
->parent
|| znode
->iip
)
1889 key1
= &znode
->parent
->zbranch
[0].key
;
1894 * insert_zbranch - insert a zbranch into a znode.
1895 * @znode: znode into which to insert
1896 * @zbr: zbranch to insert
1897 * @n: slot number to insert to
1899 * This is a helper function for 'tnc_insert()'. UBIFS does not allow "gaps" in
1900 * znode's array of zbranches and keeps zbranches consolidated, so when a new
1901 * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th
1902 * slot, zbranches starting from @n have to be moved right.
1904 static void insert_zbranch(struct ubifs_znode
*znode
,
1905 const struct ubifs_zbranch
*zbr
, int n
)
1909 ubifs_assert(ubifs_zn_dirty(znode
));
1912 for (i
= znode
->child_cnt
; i
> n
; i
--) {
1913 znode
->zbranch
[i
] = znode
->zbranch
[i
- 1];
1914 if (znode
->zbranch
[i
].znode
)
1915 znode
->zbranch
[i
].znode
->iip
= i
;
1918 zbr
->znode
->iip
= n
;
1920 for (i
= znode
->child_cnt
; i
> n
; i
--)
1921 znode
->zbranch
[i
] = znode
->zbranch
[i
- 1];
1923 znode
->zbranch
[n
] = *zbr
;
1924 znode
->child_cnt
+= 1;
1927 * After inserting at slot zero, the lower bound of the key range of
1928 * this znode may have changed. If this znode is subsequently split
1929 * then the upper bound of the key range may change, and furthermore
1930 * it could change to be lower than the original lower bound. If that
1931 * happens, then it will no longer be possible to find this znode in the
1932 * TNC using the key from the index node on flash. That is bad because
1933 * if it is not found, we will assume it is obsolete and may overwrite
1934 * it. Then if there is an unclean unmount, we will start using the
1935 * old index which will be broken.
1937 * So we first mark znodes that have insertions at slot zero, and then
1938 * if they are split we add their lnum/offs to the old_idx tree.
1945 * tnc_insert - insert a node into TNC.
1946 * @c: UBIFS file-system description object
1947 * @znode: znode to insert into
1948 * @zbr: branch to insert
1949 * @n: slot number to insert new zbranch to
1951 * This function inserts a new node described by @zbr into znode @znode. If
1952 * znode does not have a free slot for new zbranch, it is split. Parent znodes
1953 * are splat as well if needed. Returns zero in case of success or a negative
1954 * error code in case of failure.
1956 static int tnc_insert(struct ubifs_info
*c
, struct ubifs_znode
*znode
,
1957 struct ubifs_zbranch
*zbr
, int n
)
1959 struct ubifs_znode
*zn
, *zi
, *zp
;
1960 int i
, keep
, move
, appending
= 0;
1961 union ubifs_key
*key
= &zbr
->key
, *key1
;
1963 ubifs_assert(n
>= 0 && n
<= c
->fanout
);
1965 /* Implement naive insert for now */
1968 if (znode
->child_cnt
< c
->fanout
) {
1969 ubifs_assert(n
!= c
->fanout
);
1970 dbg_tnck(key
, "inserted at %d level %d, key ", n
, znode
->level
);
1972 insert_zbranch(znode
, zbr
, n
);
1974 /* Ensure parent's key is correct */
1975 if (n
== 0 && zp
&& znode
->iip
== 0)
1976 correct_parent_keys(c
, znode
);
1982 * Unfortunately, @znode does not have more empty slots and we have to
1985 dbg_tnck(key
, "splitting level %d, key ", znode
->level
);
1989 * We can no longer be sure of finding this znode by key, so we
1990 * record it in the old_idx tree.
1992 ins_clr_old_idx_znode(c
, znode
);
1994 zn
= kzalloc(c
->max_znode_sz
, GFP_NOFS
);
1998 zn
->level
= znode
->level
;
2000 /* Decide where to split */
2001 if (znode
->level
== 0 && key_type(c
, key
) == UBIFS_DATA_KEY
) {
2002 /* Try not to split consecutive data keys */
2003 if (n
== c
->fanout
) {
2004 key1
= &znode
->zbranch
[n
- 1].key
;
2005 if (key_inum(c
, key1
) == key_inum(c
, key
) &&
2006 key_type(c
, key1
) == UBIFS_DATA_KEY
)
2010 } else if (appending
&& n
!= c
->fanout
) {
2011 /* Try not to split consecutive data keys */
2014 if (n
>= (c
->fanout
+ 1) / 2) {
2015 key1
= &znode
->zbranch
[0].key
;
2016 if (key_inum(c
, key1
) == key_inum(c
, key
) &&
2017 key_type(c
, key1
) == UBIFS_DATA_KEY
) {
2018 key1
= &znode
->zbranch
[n
].key
;
2019 if (key_inum(c
, key1
) != key_inum(c
, key
) ||
2020 key_type(c
, key1
) != UBIFS_DATA_KEY
) {
2022 move
= c
->fanout
- keep
;
2034 keep
= (c
->fanout
+ 1) / 2;
2035 move
= c
->fanout
- keep
;
2039 * Although we don't at present, we could look at the neighbors and see
2040 * if we can move some zbranches there.
2044 /* Insert into existing znode */
2049 /* Insert into new znode */
2054 zbr
->znode
->parent
= zn
;
2059 __set_bit(DIRTY_ZNODE
, &zn
->flags
);
2060 atomic_long_inc(&c
->dirty_zn_cnt
);
2062 zn
->child_cnt
= move
;
2063 znode
->child_cnt
= keep
;
2065 dbg_tnc("moving %d, keeping %d", move
, keep
);
2068 for (i
= 0; i
< move
; i
++) {
2069 zn
->zbranch
[i
] = znode
->zbranch
[keep
+ i
];
2072 if (zn
->zbranch
[i
].znode
) {
2073 zn
->zbranch
[i
].znode
->parent
= zn
;
2074 zn
->zbranch
[i
].znode
->iip
= i
;
2078 /* Insert new key and branch */
2079 dbg_tnck(key
, "inserting at %d level %d, key ", n
, zn
->level
);
2081 insert_zbranch(zi
, zbr
, n
);
2083 /* Insert new znode (produced by spitting) into the parent */
2085 if (n
== 0 && zi
== znode
&& znode
->iip
== 0)
2086 correct_parent_keys(c
, znode
);
2088 /* Locate insertion point */
2091 /* Tail recursion */
2092 zbr
->key
= zn
->zbranch
[0].key
;
2102 /* We have to split root znode */
2103 dbg_tnc("creating new zroot at level %d", znode
->level
+ 1);
2105 zi
= kzalloc(c
->max_znode_sz
, GFP_NOFS
);
2110 zi
->level
= znode
->level
+ 1;
2112 __set_bit(DIRTY_ZNODE
, &zi
->flags
);
2113 atomic_long_inc(&c
->dirty_zn_cnt
);
2115 zi
->zbranch
[0].key
= znode
->zbranch
[0].key
;
2116 zi
->zbranch
[0].znode
= znode
;
2117 zi
->zbranch
[0].lnum
= c
->zroot
.lnum
;
2118 zi
->zbranch
[0].offs
= c
->zroot
.offs
;
2119 zi
->zbranch
[0].len
= c
->zroot
.len
;
2120 zi
->zbranch
[1].key
= zn
->zbranch
[0].key
;
2121 zi
->zbranch
[1].znode
= zn
;
2126 c
->zroot
.znode
= zi
;
2137 * ubifs_tnc_add - add a node to TNC.
2138 * @c: UBIFS file-system description object
2140 * @lnum: LEB number of node
2141 * @offs: node offset
2144 * This function adds a node with key @key to TNC. The node may be new or it may
2145 * obsolete some existing one. Returns %0 on success or negative error code on
2148 int ubifs_tnc_add(struct ubifs_info
*c
, const union ubifs_key
*key
, int lnum
,
2151 int found
, n
, err
= 0;
2152 struct ubifs_znode
*znode
;
2154 mutex_lock(&c
->tnc_mutex
);
2155 dbg_tnck(key
, "%d:%d, len %d, key ", lnum
, offs
, len
);
2156 found
= lookup_level0_dirty(c
, key
, &znode
, &n
);
2158 struct ubifs_zbranch zbr
;
2164 key_copy(c
, key
, &zbr
.key
);
2165 err
= tnc_insert(c
, znode
, &zbr
, n
+ 1);
2166 } else if (found
== 1) {
2167 struct ubifs_zbranch
*zbr
= &znode
->zbranch
[n
];
2170 err
= ubifs_add_dirt(c
, zbr
->lnum
, zbr
->len
);
2177 err
= dbg_check_tnc(c
, 0);
2178 mutex_unlock(&c
->tnc_mutex
);
2184 * ubifs_tnc_replace - replace a node in the TNC only if the old node is found.
2185 * @c: UBIFS file-system description object
2187 * @old_lnum: LEB number of old node
2188 * @old_offs: old node offset
2189 * @lnum: LEB number of node
2190 * @offs: node offset
2193 * This function replaces a node with key @key in the TNC only if the old node
2194 * is found. This function is called by garbage collection when node are moved.
2195 * Returns %0 on success or negative error code on failure.
2197 int ubifs_tnc_replace(struct ubifs_info
*c
, const union ubifs_key
*key
,
2198 int old_lnum
, int old_offs
, int lnum
, int offs
, int len
)
2200 int found
, n
, err
= 0;
2201 struct ubifs_znode
*znode
;
2203 mutex_lock(&c
->tnc_mutex
);
2204 dbg_tnck(key
, "old LEB %d:%d, new LEB %d:%d, len %d, key ", old_lnum
,
2205 old_offs
, lnum
, offs
, len
);
2206 found
= lookup_level0_dirty(c
, key
, &znode
, &n
);
2213 struct ubifs_zbranch
*zbr
= &znode
->zbranch
[n
];
2216 if (zbr
->lnum
== old_lnum
&& zbr
->offs
== old_offs
) {
2218 err
= ubifs_add_dirt(c
, zbr
->lnum
, zbr
->len
);
2225 } else if (is_hash_key(c
, key
)) {
2226 found
= resolve_collision_directly(c
, key
, &znode
, &n
,
2227 old_lnum
, old_offs
);
2228 dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d",
2229 found
, znode
, n
, old_lnum
, old_offs
);
2236 /* Ensure the znode is dirtied */
2237 if (znode
->cnext
|| !ubifs_zn_dirty(znode
)) {
2238 znode
= dirty_cow_bottom_up(c
, znode
);
2239 if (IS_ERR(znode
)) {
2240 err
= PTR_ERR(znode
);
2244 zbr
= &znode
->zbranch
[n
];
2246 err
= ubifs_add_dirt(c
, zbr
->lnum
,
2258 err
= ubifs_add_dirt(c
, lnum
, len
);
2261 err
= dbg_check_tnc(c
, 0);
2264 mutex_unlock(&c
->tnc_mutex
);
2269 * ubifs_tnc_add_nm - add a "hashed" node to TNC.
2270 * @c: UBIFS file-system description object
2272 * @lnum: LEB number of node
2273 * @offs: node offset
2277 * This is the same as 'ubifs_tnc_add()' but it should be used with keys which
2278 * may have collisions, like directory entry keys.
2280 int ubifs_tnc_add_nm(struct ubifs_info
*c
, const union ubifs_key
*key
,
2281 int lnum
, int offs
, int len
, const struct qstr
*nm
)
2283 int found
, n
, err
= 0;
2284 struct ubifs_znode
*znode
;
2286 mutex_lock(&c
->tnc_mutex
);
2287 dbg_tnck(key
, "LEB %d:%d, name '%.*s', key ",
2288 lnum
, offs
, nm
->len
, nm
->name
);
2289 found
= lookup_level0_dirty(c
, key
, &znode
, &n
);
2297 found
= fallible_resolve_collision(c
, key
, &znode
, &n
,
2300 found
= resolve_collision(c
, key
, &znode
, &n
, nm
);
2301 dbg_tnc("rc returned %d, znode %p, n %d", found
, znode
, n
);
2307 /* Ensure the znode is dirtied */
2308 if (znode
->cnext
|| !ubifs_zn_dirty(znode
)) {
2309 znode
= dirty_cow_bottom_up(c
, znode
);
2310 if (IS_ERR(znode
)) {
2311 err
= PTR_ERR(znode
);
2317 struct ubifs_zbranch
*zbr
= &znode
->zbranch
[n
];
2320 err
= ubifs_add_dirt(c
, zbr
->lnum
, zbr
->len
);
2329 struct ubifs_zbranch zbr
;
2335 key_copy(c
, key
, &zbr
.key
);
2336 err
= tnc_insert(c
, znode
, &zbr
, n
+ 1);
2341 * We did not find it in the index so there may be a
2342 * dangling branch still in the index. So we remove it
2343 * by passing 'ubifs_tnc_remove_nm()' the same key but
2344 * an unmatchable name.
2346 struct qstr noname
= { .name
= "" };
2348 err
= dbg_check_tnc(c
, 0);
2349 mutex_unlock(&c
->tnc_mutex
);
2352 return ubifs_tnc_remove_nm(c
, key
, &noname
);
2358 err
= dbg_check_tnc(c
, 0);
2359 mutex_unlock(&c
->tnc_mutex
);
2364 * tnc_delete - delete a znode form TNC.
2365 * @c: UBIFS file-system description object
2366 * @znode: znode to delete from
2367 * @n: zbranch slot number to delete
2369 * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
2370 * case of success and a negative error code in case of failure.
2372 static int tnc_delete(struct ubifs_info
*c
, struct ubifs_znode
*znode
, int n
)
2374 struct ubifs_zbranch
*zbr
;
2375 struct ubifs_znode
*zp
;
2378 /* Delete without merge for now */
2379 ubifs_assert(znode
->level
== 0);
2380 ubifs_assert(n
>= 0 && n
< c
->fanout
);
2381 dbg_tnck(&znode
->zbranch
[n
].key
, "deleting key ");
2383 zbr
= &znode
->zbranch
[n
];
2386 err
= ubifs_add_dirt(c
, zbr
->lnum
, zbr
->len
);
2388 ubifs_dump_znode(c
, znode
);
2392 /* We do not "gap" zbranch slots */
2393 for (i
= n
; i
< znode
->child_cnt
- 1; i
++)
2394 znode
->zbranch
[i
] = znode
->zbranch
[i
+ 1];
2395 znode
->child_cnt
-= 1;
2397 if (znode
->child_cnt
> 0)
2401 * This was the last zbranch, we have to delete this znode from the
2406 ubifs_assert(!ubifs_zn_obsolete(znode
));
2407 ubifs_assert(ubifs_zn_dirty(znode
));
2412 atomic_long_dec(&c
->dirty_zn_cnt
);
2414 err
= insert_old_idx_znode(c
, znode
);
2419 __set_bit(OBSOLETE_ZNODE
, &znode
->flags
);
2420 atomic_long_inc(&c
->clean_zn_cnt
);
2421 atomic_long_inc(&ubifs_clean_zn_cnt
);
2425 } while (znode
->child_cnt
== 1); /* while removing last child */
2427 /* Remove from znode, entry n - 1 */
2428 znode
->child_cnt
-= 1;
2429 ubifs_assert(znode
->level
!= 0);
2430 for (i
= n
; i
< znode
->child_cnt
; i
++) {
2431 znode
->zbranch
[i
] = znode
->zbranch
[i
+ 1];
2432 if (znode
->zbranch
[i
].znode
)
2433 znode
->zbranch
[i
].znode
->iip
= i
;
2437 * If this is the root and it has only 1 child then
2438 * collapse the tree.
2440 if (!znode
->parent
) {
2441 while (znode
->child_cnt
== 1 && znode
->level
!= 0) {
2443 zbr
= &znode
->zbranch
[0];
2444 znode
= get_znode(c
, znode
, 0);
2446 return PTR_ERR(znode
);
2447 znode
= dirty_cow_znode(c
, zbr
);
2449 return PTR_ERR(znode
);
2450 znode
->parent
= NULL
;
2453 err
= insert_old_idx(c
, c
->zroot
.lnum
,
2458 c
->zroot
.lnum
= zbr
->lnum
;
2459 c
->zroot
.offs
= zbr
->offs
;
2460 c
->zroot
.len
= zbr
->len
;
2461 c
->zroot
.znode
= znode
;
2462 ubifs_assert(!ubifs_zn_obsolete(zp
));
2463 ubifs_assert(ubifs_zn_dirty(zp
));
2464 atomic_long_dec(&c
->dirty_zn_cnt
);
2467 __set_bit(OBSOLETE_ZNODE
, &zp
->flags
);
2468 atomic_long_inc(&c
->clean_zn_cnt
);
2469 atomic_long_inc(&ubifs_clean_zn_cnt
);
2479 * ubifs_tnc_remove - remove an index entry of a node.
2480 * @c: UBIFS file-system description object
2483 * Returns %0 on success or negative error code on failure.
2485 int ubifs_tnc_remove(struct ubifs_info
*c
, const union ubifs_key
*key
)
2487 int found
, n
, err
= 0;
2488 struct ubifs_znode
*znode
;
2490 mutex_lock(&c
->tnc_mutex
);
2491 dbg_tnck(key
, "key ");
2492 found
= lookup_level0_dirty(c
, key
, &znode
, &n
);
2498 err
= tnc_delete(c
, znode
, n
);
2500 err
= dbg_check_tnc(c
, 0);
2503 mutex_unlock(&c
->tnc_mutex
);
2508 * ubifs_tnc_remove_nm - remove an index entry for a "hashed" node.
2509 * @c: UBIFS file-system description object
2511 * @nm: directory entry name
2513 * Returns %0 on success or negative error code on failure.
2515 int ubifs_tnc_remove_nm(struct ubifs_info
*c
, const union ubifs_key
*key
,
2516 const struct qstr
*nm
)
2519 struct ubifs_znode
*znode
;
2521 mutex_lock(&c
->tnc_mutex
);
2522 dbg_tnck(key
, "%.*s, key ", nm
->len
, nm
->name
);
2523 err
= lookup_level0_dirty(c
, key
, &znode
, &n
);
2529 err
= fallible_resolve_collision(c
, key
, &znode
, &n
,
2532 err
= resolve_collision(c
, key
, &znode
, &n
, nm
);
2533 dbg_tnc("rc returned %d, znode %p, n %d", err
, znode
, n
);
2537 /* Ensure the znode is dirtied */
2538 if (znode
->cnext
|| !ubifs_zn_dirty(znode
)) {
2539 znode
= dirty_cow_bottom_up(c
, znode
);
2540 if (IS_ERR(znode
)) {
2541 err
= PTR_ERR(znode
);
2545 err
= tnc_delete(c
, znode
, n
);
2551 err
= dbg_check_tnc(c
, 0);
2552 mutex_unlock(&c
->tnc_mutex
);
2557 * key_in_range - determine if a key falls within a range of keys.
2558 * @c: UBIFS file-system description object
2559 * @key: key to check
2560 * @from_key: lowest key in range
2561 * @to_key: highest key in range
2563 * This function returns %1 if the key is in range and %0 otherwise.
2565 static int key_in_range(struct ubifs_info
*c
, union ubifs_key
*key
,
2566 union ubifs_key
*from_key
, union ubifs_key
*to_key
)
2568 if (keys_cmp(c
, key
, from_key
) < 0)
2570 if (keys_cmp(c
, key
, to_key
) > 0)
2576 * ubifs_tnc_remove_range - remove index entries in range.
2577 * @c: UBIFS file-system description object
2578 * @from_key: lowest key to remove
2579 * @to_key: highest key to remove
2581 * This function removes index entries starting at @from_key and ending at
2582 * @to_key. This function returns zero in case of success and a negative error
2583 * code in case of failure.
2585 int ubifs_tnc_remove_range(struct ubifs_info
*c
, union ubifs_key
*from_key
,
2586 union ubifs_key
*to_key
)
2588 int i
, n
, k
, err
= 0;
2589 struct ubifs_znode
*znode
;
2590 union ubifs_key
*key
;
2592 mutex_lock(&c
->tnc_mutex
);
2594 /* Find first level 0 znode that contains keys to remove */
2595 err
= ubifs_lookup_level0(c
, from_key
, &znode
, &n
);
2602 err
= tnc_next(c
, &znode
, &n
);
2603 if (err
== -ENOENT
) {
2609 key
= &znode
->zbranch
[n
].key
;
2610 if (!key_in_range(c
, key
, from_key
, to_key
)) {
2616 /* Ensure the znode is dirtied */
2617 if (znode
->cnext
|| !ubifs_zn_dirty(znode
)) {
2618 znode
= dirty_cow_bottom_up(c
, znode
);
2619 if (IS_ERR(znode
)) {
2620 err
= PTR_ERR(znode
);
2625 /* Remove all keys in range except the first */
2626 for (i
= n
+ 1, k
= 0; i
< znode
->child_cnt
; i
++, k
++) {
2627 key
= &znode
->zbranch
[i
].key
;
2628 if (!key_in_range(c
, key
, from_key
, to_key
))
2630 lnc_free(&znode
->zbranch
[i
]);
2631 err
= ubifs_add_dirt(c
, znode
->zbranch
[i
].lnum
,
2632 znode
->zbranch
[i
].len
);
2634 ubifs_dump_znode(c
, znode
);
2637 dbg_tnck(key
, "removing key ");
2640 for (i
= n
+ 1 + k
; i
< znode
->child_cnt
; i
++)
2641 znode
->zbranch
[i
- k
] = znode
->zbranch
[i
];
2642 znode
->child_cnt
-= k
;
2645 /* Now delete the first */
2646 err
= tnc_delete(c
, znode
, n
);
2653 err
= dbg_check_tnc(c
, 0);
2654 mutex_unlock(&c
->tnc_mutex
);
2659 * ubifs_tnc_remove_ino - remove an inode from TNC.
2660 * @c: UBIFS file-system description object
2661 * @inum: inode number to remove
2663 * This function remove inode @inum and all the extended attributes associated
2664 * with the anode from TNC and returns zero in case of success or a negative
2665 * error code in case of failure.
2667 int ubifs_tnc_remove_ino(struct ubifs_info
*c
, ino_t inum
)
2669 union ubifs_key key1
, key2
;
2670 struct ubifs_dent_node
*xent
, *pxent
= NULL
;
2671 struct qstr nm
= { .name
= NULL
};
2673 dbg_tnc("ino %lu", (unsigned long)inum
);
2676 * Walk all extended attribute entries and remove them together with
2677 * corresponding extended attribute inodes.
2679 lowest_xent_key(c
, &key1
, inum
);
2684 xent
= ubifs_tnc_next_ent(c
, &key1
, &nm
);
2686 err
= PTR_ERR(xent
);
2692 xattr_inum
= le64_to_cpu(xent
->inum
);
2693 dbg_tnc("xent '%s', ino %lu", xent
->name
,
2694 (unsigned long)xattr_inum
);
2696 nm
.name
= xent
->name
;
2697 nm
.len
= le16_to_cpu(xent
->nlen
);
2698 err
= ubifs_tnc_remove_nm(c
, &key1
, &nm
);
2704 lowest_ino_key(c
, &key1
, xattr_inum
);
2705 highest_ino_key(c
, &key2
, xattr_inum
);
2706 err
= ubifs_tnc_remove_range(c
, &key1
, &key2
);
2714 key_read(c
, &xent
->key
, &key1
);
2718 lowest_ino_key(c
, &key1
, inum
);
2719 highest_ino_key(c
, &key2
, inum
);
2721 return ubifs_tnc_remove_range(c
, &key1
, &key2
);
2725 * ubifs_tnc_next_ent - walk directory or extended attribute entries.
2726 * @c: UBIFS file-system description object
2727 * @key: key of last entry
2728 * @nm: name of last entry found or %NULL
2730 * This function finds and reads the next directory or extended attribute entry
2731 * after the given key (@key) if there is one. @nm is used to resolve
2734 * If the name of the current entry is not known and only the key is known,
2735 * @nm->name has to be %NULL. In this case the semantics of this function is a
2736 * little bit different and it returns the entry corresponding to this key, not
2737 * the next one. If the key was not found, the closest "right" entry is
2740 * If the fist entry has to be found, @key has to contain the lowest possible
2741 * key value for this inode and @name has to be %NULL.
2743 * This function returns the found directory or extended attribute entry node
2744 * in case of success, %-ENOENT is returned if no entry was found, and a
2745 * negative error code is returned in case of failure.
2747 struct ubifs_dent_node
*ubifs_tnc_next_ent(struct ubifs_info
*c
,
2748 union ubifs_key
*key
,
2749 const struct qstr
*nm
)
2751 int n
, err
, type
= key_type(c
, key
);
2752 struct ubifs_znode
*znode
;
2753 struct ubifs_dent_node
*dent
;
2754 struct ubifs_zbranch
*zbr
;
2755 union ubifs_key
*dkey
;
2757 dbg_tnck(key
, "%s ", nm
->name
? (char *)nm
->name
: "(lowest)");
2758 ubifs_assert(is_hash_key(c
, key
));
2760 mutex_lock(&c
->tnc_mutex
);
2761 err
= ubifs_lookup_level0(c
, key
, &znode
, &n
);
2762 if (unlikely(err
< 0))
2767 /* Handle collisions */
2768 err
= resolve_collision(c
, key
, &znode
, &n
, nm
);
2769 dbg_tnc("rc returned %d, znode %p, n %d",
2771 if (unlikely(err
< 0))
2775 /* Now find next entry */
2776 err
= tnc_next(c
, &znode
, &n
);
2781 * The full name of the entry was not given, in which case the
2782 * behavior of this function is a little different and it
2783 * returns current entry, not the next one.
2787 * However, the given key does not exist in the TNC
2788 * tree and @znode/@n variables contain the closest
2789 * "preceding" element. Switch to the next one.
2791 err
= tnc_next(c
, &znode
, &n
);
2797 zbr
= &znode
->zbranch
[n
];
2798 dent
= kmalloc(zbr
->len
, GFP_NOFS
);
2799 if (unlikely(!dent
)) {
2805 * The above 'tnc_next()' call could lead us to the next inode, check
2809 if (key_inum(c
, dkey
) != key_inum(c
, key
) ||
2810 key_type(c
, dkey
) != type
) {
2815 err
= tnc_read_node_nm(c
, zbr
, dent
);
2819 mutex_unlock(&c
->tnc_mutex
);
2825 mutex_unlock(&c
->tnc_mutex
);
2826 return ERR_PTR(err
);
2830 * tnc_destroy_cnext - destroy left-over obsolete znodes from a failed commit.
2831 * @c: UBIFS file-system description object
2833 * Destroy left-over obsolete znodes from a failed commit.
2835 static void tnc_destroy_cnext(struct ubifs_info
*c
)
2837 struct ubifs_znode
*cnext
;
2841 ubifs_assert(c
->cmt_state
== COMMIT_BROKEN
);
2844 struct ubifs_znode
*znode
= cnext
;
2846 cnext
= cnext
->cnext
;
2847 if (ubifs_zn_obsolete(znode
))
2849 } while (cnext
&& cnext
!= c
->cnext
);
2853 * ubifs_tnc_close - close TNC subsystem and free all related resources.
2854 * @c: UBIFS file-system description object
2856 void ubifs_tnc_close(struct ubifs_info
*c
)
2858 tnc_destroy_cnext(c
);
2859 if (c
->zroot
.znode
) {
2862 n
= atomic_long_read(&c
->clean_zn_cnt
);
2863 freed
= ubifs_destroy_tnc_subtree(c
->zroot
.znode
);
2864 ubifs_assert(freed
== n
);
2865 atomic_long_sub(n
, &ubifs_clean_zn_cnt
);
2873 * left_znode - get the znode to the left.
2874 * @c: UBIFS file-system description object
2877 * This function returns a pointer to the znode to the left of @znode or NULL if
2878 * there is not one. A negative error code is returned on failure.
2880 static struct ubifs_znode
*left_znode(struct ubifs_info
*c
,
2881 struct ubifs_znode
*znode
)
2883 int level
= znode
->level
;
2886 int n
= znode
->iip
- 1;
2888 /* Go up until we can go left */
2889 znode
= znode
->parent
;
2893 /* Now go down the rightmost branch to 'level' */
2894 znode
= get_znode(c
, znode
, n
);
2897 while (znode
->level
!= level
) {
2898 n
= znode
->child_cnt
- 1;
2899 znode
= get_znode(c
, znode
, n
);
2910 * right_znode - get the znode to the right.
2911 * @c: UBIFS file-system description object
2914 * This function returns a pointer to the znode to the right of @znode or NULL
2915 * if there is not one. A negative error code is returned on failure.
2917 static struct ubifs_znode
*right_znode(struct ubifs_info
*c
,
2918 struct ubifs_znode
*znode
)
2920 int level
= znode
->level
;
2923 int n
= znode
->iip
+ 1;
2925 /* Go up until we can go right */
2926 znode
= znode
->parent
;
2929 if (n
< znode
->child_cnt
) {
2930 /* Now go down the leftmost branch to 'level' */
2931 znode
= get_znode(c
, znode
, n
);
2934 while (znode
->level
!= level
) {
2935 znode
= get_znode(c
, znode
, 0);
2946 * lookup_znode - find a particular indexing node from TNC.
2947 * @c: UBIFS file-system description object
2948 * @key: index node key to lookup
2949 * @level: index node level
2950 * @lnum: index node LEB number
2951 * @offs: index node offset
2953 * This function searches an indexing node by its first key @key and its
2954 * address @lnum:@offs. It looks up the indexing tree by pulling all indexing
2955 * nodes it traverses to TNC. This function is called for indexing nodes which
2956 * were found on the media by scanning, for example when garbage-collecting or
2957 * when doing in-the-gaps commit. This means that the indexing node which is
2958 * looked for does not have to have exactly the same leftmost key @key, because
2959 * the leftmost key may have been changed, in which case TNC will contain a
2960 * dirty znode which still refers the same @lnum:@offs. This function is clever
2961 * enough to recognize such indexing nodes.
2963 * Note, if a znode was deleted or changed too much, then this function will
2964 * not find it. For situations like this UBIFS has the old index RB-tree
2965 * (indexed by @lnum:@offs).
2967 * This function returns a pointer to the znode found or %NULL if it is not
2968 * found. A negative error code is returned on failure.
2970 static struct ubifs_znode
*lookup_znode(struct ubifs_info
*c
,
2971 union ubifs_key
*key
, int level
,
2974 struct ubifs_znode
*znode
, *zn
;
2977 ubifs_assert(key_type(c
, key
) < UBIFS_INVALID_KEY
);
2980 * The arguments have probably been read off flash, so don't assume
2984 return ERR_PTR(-EINVAL
);
2986 /* Get the root znode */
2987 znode
= c
->zroot
.znode
;
2989 znode
= ubifs_load_znode(c
, &c
->zroot
, NULL
, 0);
2993 /* Check if it is the one we are looking for */
2994 if (c
->zroot
.lnum
== lnum
&& c
->zroot
.offs
== offs
)
2996 /* Descend to the parent level i.e. (level + 1) */
2997 if (level
>= znode
->level
)
3000 ubifs_search_zbranch(c
, znode
, key
, &n
);
3003 * We reached a znode where the leftmost key is greater
3004 * than the key we are searching for. This is the same
3005 * situation as the one described in a huge comment at
3006 * the end of the 'ubifs_lookup_level0()' function. And
3007 * for exactly the same reasons we have to try to look
3008 * left before giving up.
3010 znode
= left_znode(c
, znode
);
3015 ubifs_search_zbranch(c
, znode
, key
, &n
);
3016 ubifs_assert(n
>= 0);
3018 if (znode
->level
== level
+ 1)
3020 znode
= get_znode(c
, znode
, n
);
3024 /* Check if the child is the one we are looking for */
3025 if (znode
->zbranch
[n
].lnum
== lnum
&& znode
->zbranch
[n
].offs
== offs
)
3026 return get_znode(c
, znode
, n
);
3027 /* If the key is unique, there is nowhere else to look */
3028 if (!is_hash_key(c
, key
))
3031 * The key is not unique and so may be also in the znodes to either
3038 /* Move one branch to the left */
3042 znode
= left_znode(c
, znode
);
3047 n
= znode
->child_cnt
- 1;
3050 if (znode
->zbranch
[n
].lnum
== lnum
&&
3051 znode
->zbranch
[n
].offs
== offs
)
3052 return get_znode(c
, znode
, n
);
3053 /* Stop if the key is less than the one we are looking for */
3054 if (keys_cmp(c
, &znode
->zbranch
[n
].key
, key
) < 0)
3057 /* Back to the middle */
3062 /* Move one branch to the right */
3063 if (++n
>= znode
->child_cnt
) {
3064 znode
= right_znode(c
, znode
);
3072 if (znode
->zbranch
[n
].lnum
== lnum
&&
3073 znode
->zbranch
[n
].offs
== offs
)
3074 return get_znode(c
, znode
, n
);
3075 /* Stop if the key is greater than the one we are looking for */
3076 if (keys_cmp(c
, &znode
->zbranch
[n
].key
, key
) > 0)
3083 * is_idx_node_in_tnc - determine if an index node is in the TNC.
3084 * @c: UBIFS file-system description object
3085 * @key: key of index node
3086 * @level: index node level
3087 * @lnum: LEB number of index node
3088 * @offs: offset of index node
3090 * This function returns %0 if the index node is not referred to in the TNC, %1
3091 * if the index node is referred to in the TNC and the corresponding znode is
3092 * dirty, %2 if an index node is referred to in the TNC and the corresponding
3093 * znode is clean, and a negative error code in case of failure.
3095 * Note, the @key argument has to be the key of the first child. Also note,
3096 * this function relies on the fact that 0:0 is never a valid LEB number and
3097 * offset for a main-area node.
3099 int is_idx_node_in_tnc(struct ubifs_info
*c
, union ubifs_key
*key
, int level
,
3102 struct ubifs_znode
*znode
;
3104 znode
= lookup_znode(c
, key
, level
, lnum
, offs
);
3108 return PTR_ERR(znode
);
3110 return ubifs_zn_dirty(znode
) ? 1 : 2;
3114 * is_leaf_node_in_tnc - determine if a non-indexing not is in the TNC.
3115 * @c: UBIFS file-system description object
3117 * @lnum: node LEB number
3118 * @offs: node offset
3120 * This function returns %1 if the node is referred to in the TNC, %0 if it is
3121 * not, and a negative error code in case of failure.
3123 * Note, this function relies on the fact that 0:0 is never a valid LEB number
3124 * and offset for a main-area node.
3126 static int is_leaf_node_in_tnc(struct ubifs_info
*c
, union ubifs_key
*key
,
3129 struct ubifs_zbranch
*zbr
;
3130 struct ubifs_znode
*znode
, *zn
;
3131 int n
, found
, err
, nn
;
3132 const int unique
= !is_hash_key(c
, key
);
3134 found
= ubifs_lookup_level0(c
, key
, &znode
, &n
);
3136 return found
; /* Error code */
3139 zbr
= &znode
->zbranch
[n
];
3140 if (lnum
== zbr
->lnum
&& offs
== zbr
->offs
)
3141 return 1; /* Found it */
3145 * Because the key is not unique, we have to look left
3152 err
= tnc_prev(c
, &znode
, &n
);
3157 if (keys_cmp(c
, key
, &znode
->zbranch
[n
].key
))
3159 zbr
= &znode
->zbranch
[n
];
3160 if (lnum
== zbr
->lnum
&& offs
== zbr
->offs
)
3161 return 1; /* Found it */
3167 err
= tnc_next(c
, &znode
, &n
);
3173 if (keys_cmp(c
, key
, &znode
->zbranch
[n
].key
))
3175 zbr
= &znode
->zbranch
[n
];
3176 if (lnum
== zbr
->lnum
&& offs
== zbr
->offs
)
3177 return 1; /* Found it */
3183 * ubifs_tnc_has_node - determine whether a node is in the TNC.
3184 * @c: UBIFS file-system description object
3186 * @level: index node level (if it is an index node)
3187 * @lnum: node LEB number
3188 * @offs: node offset
3189 * @is_idx: non-zero if the node is an index node
3191 * This function returns %1 if the node is in the TNC, %0 if it is not, and a
3192 * negative error code in case of failure. For index nodes, @key has to be the
3193 * key of the first child. An index node is considered to be in the TNC only if
3194 * the corresponding znode is clean or has not been loaded.
3196 int ubifs_tnc_has_node(struct ubifs_info
*c
, union ubifs_key
*key
, int level
,
3197 int lnum
, int offs
, int is_idx
)
3201 mutex_lock(&c
->tnc_mutex
);
3203 err
= is_idx_node_in_tnc(c
, key
, level
, lnum
, offs
);
3207 /* The index node was found but it was dirty */
3210 /* The index node was found and it was clean */
3215 err
= is_leaf_node_in_tnc(c
, key
, lnum
, offs
);
3218 mutex_unlock(&c
->tnc_mutex
);
3223 * ubifs_dirty_idx_node - dirty an index node.
3224 * @c: UBIFS file-system description object
3225 * @key: index node key
3226 * @level: index node level
3227 * @lnum: index node LEB number
3228 * @offs: index node offset
3230 * This function loads and dirties an index node so that it can be garbage
3231 * collected. The @key argument has to be the key of the first child. This
3232 * function relies on the fact that 0:0 is never a valid LEB number and offset
3233 * for a main-area node. Returns %0 on success and a negative error code on
3236 int ubifs_dirty_idx_node(struct ubifs_info
*c
, union ubifs_key
*key
, int level
,
3239 struct ubifs_znode
*znode
;
3242 mutex_lock(&c
->tnc_mutex
);
3243 znode
= lookup_znode(c
, key
, level
, lnum
, offs
);
3246 if (IS_ERR(znode
)) {
3247 err
= PTR_ERR(znode
);
3250 znode
= dirty_cow_bottom_up(c
, znode
);
3251 if (IS_ERR(znode
)) {
3252 err
= PTR_ERR(znode
);
3257 mutex_unlock(&c
->tnc_mutex
);
3262 * dbg_check_inode_size - check if inode size is correct.
3263 * @c: UBIFS file-system description object
3264 * @inum: inode number
3267 * This function makes sure that the inode size (@size) is correct and it does
3268 * not have any pages beyond @size. Returns zero if the inode is OK, %-EINVAL
3269 * if it has a data page beyond @size, and other negative error code in case of
3272 int dbg_check_inode_size(struct ubifs_info
*c
, const struct inode
*inode
,
3276 union ubifs_key from_key
, to_key
, *key
;
3277 struct ubifs_znode
*znode
;
3280 if (!S_ISREG(inode
->i_mode
))
3282 if (!dbg_is_chk_gen(c
))
3285 block
= (size
+ UBIFS_BLOCK_SIZE
- 1) >> UBIFS_BLOCK_SHIFT
;
3286 data_key_init(c
, &from_key
, inode
->i_ino
, block
);
3287 highest_data_key(c
, &to_key
, inode
->i_ino
);
3289 mutex_lock(&c
->tnc_mutex
);
3290 err
= ubifs_lookup_level0(c
, &from_key
, &znode
, &n
);
3299 err
= tnc_next(c
, &znode
, &n
);
3300 if (err
== -ENOENT
) {
3307 ubifs_assert(err
== 0);
3308 key
= &znode
->zbranch
[n
].key
;
3309 if (!key_in_range(c
, key
, &from_key
, &to_key
))
3313 block
= key_block(c
, key
);
3314 ubifs_err(c
, "inode %lu has size %lld, but there are data at offset %lld",
3315 (unsigned long)inode
->i_ino
, size
,
3316 ((loff_t
)block
) << UBIFS_BLOCK_SHIFT
);
3317 mutex_unlock(&c
->tnc_mutex
);
3318 ubifs_dump_inode(c
, inode
);
3323 mutex_unlock(&c
->tnc_mutex
);