From 51e613c55ba87a57ca66d0dc37cb576f38882bf0 Mon Sep 17 00:00:00 2001 From: Zhihao Cheng Date: Mon, 11 Nov 2024 16:37:00 +0800 Subject: ubifs-utils: Adapt tnc subsystem in libubifs Adapt tnc subsystem(tnc.c,tnc_misc.c,tnc_commit.c) in libubifs, compared with linux kernel implementations: 1. Remove debug related functions(eg. dbg_check_inode_size), debug functions are not needed by fsck, because fsck will check fs in another way. 2. Remove some functions(eg. ubifs_tnc_bulk_read) which won't be used in fsck/mkfs. 3. Adapt tnc_delete and ubifs_search_zbranch to handle empty TNC case, which could happen in fsck. 4. Don't skip checking the length of non-leaf index node's branch in read_znode. 5. Adapt try_read_node to ignore %-EBADMSG, subsequent steps will check nodes carefully. Signed-off-by: Zhihao Cheng Signed-off-by: David Oberhollenzer --- ubifs-utils/libubifs/tnc.c | 590 +------------------------------------- ubifs-utils/libubifs/tnc_commit.c | 18 +- ubifs-utils/libubifs/tnc_misc.c | 108 ++----- 3 files changed, 43 insertions(+), 673 deletions(-) diff --git a/ubifs-utils/libubifs/tnc.c b/ubifs-utils/libubifs/tnc.c index 0fabecd..12c56e0 100644 --- a/ubifs-utils/libubifs/tnc.c +++ b/ubifs-utils/libubifs/tnc.c @@ -18,9 +18,15 @@ * the mutex locked. */ -#include -#include +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" +#include "crc32.h" #include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" static int try_read_node(const struct ubifs_info *c, void *buf, int type, struct ubifs_zbranch *zbr); @@ -488,7 +494,7 @@ static int try_read_node(const struct ubifs_info *c, void *buf, int type, dbg_io("LEB %d:%d, %s, length %d", lnum, offs, dbg_ntype(type), len); err = ubifs_leb_read(c, lnum, buf, offs, len, 1); - if (err) { + if (err && err != -EBADMSG) { ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d", type, lnum, offs, err); return err; @@ -929,7 +935,7 @@ static int fallible_resolve_collision(struct ubifs_info *c, int adding) { struct ubifs_znode *o_znode = NULL, *znode = *zn; - int o_n, err, cmp, unsure = 0, nn = *n; + int err, cmp, o_n = 0, unsure = 0, nn = *n; cmp = fallible_matches_name(c, &znode->zbranch[nn], nm); if (unlikely(cmp < 0)) @@ -1426,42 +1432,6 @@ static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key, return 1; } -/** - * maybe_leb_gced - determine if a LEB may have been garbage collected. - * @c: UBIFS file-system description object - * @lnum: LEB number - * @gc_seq1: garbage collection sequence number - * - * This function determines if @lnum may have been garbage collected since - * sequence number @gc_seq1. If it may have been then %1 is returned, otherwise - * %0 is returned. - */ -static int maybe_leb_gced(struct ubifs_info *c, int lnum, int gc_seq1) -{ - int gc_seq2, gced_lnum; - - gced_lnum = c->gced_lnum; - smp_rmb(); - gc_seq2 = c->gc_seq; - /* Same seq means no GC */ - if (gc_seq1 == gc_seq2) - return 0; - /* Different by more than 1 means we don't know */ - if (gc_seq1 + 1 != gc_seq2) - return 1; - /* - * We have seen the sequence number has increased by 1. Now we need to - * be sure we read the right LEB number, so read it again. - */ - smp_rmb(); - if (gced_lnum != c->gced_lnum) - return 1; - /* Finally we can check lnum */ - if (gced_lnum == lnum) - return 1; - return 0; -} - /** * ubifs_tnc_locate - look up a file-system node and return it and its location. * @c: UBIFS file-system description object @@ -1511,300 +1481,6 @@ out: return err; } -/** - * ubifs_tnc_get_bu_keys - lookup keys for bulk-read. - * @c: UBIFS file-system description object - * @bu: bulk-read parameters and results - * - * Lookup consecutive data node keys for the same inode that reside - * consecutively in the same LEB. This function returns zero in case of success - * and a negative error code in case of failure. - * - * Note, if the bulk-read buffer length (@bu->buf_len) is known, this function - * makes sure bulk-read nodes fit the buffer. Otherwise, this function prepares - * maximum possible amount of nodes for bulk-read. - */ -int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu) -{ - int n, err = 0, lnum = -1, offs; - int len; - unsigned int block = key_block(c, &bu->key); - struct ubifs_znode *znode; - - bu->cnt = 0; - bu->blk_cnt = 0; - bu->eof = 0; - - mutex_lock(&c->tnc_mutex); - /* Find first key */ - err = ubifs_lookup_level0(c, &bu->key, &znode, &n); - if (err < 0) - goto out; - if (err) { - /* Key found */ - len = znode->zbranch[n].len; - /* The buffer must be big enough for at least 1 node */ - if (len > bu->buf_len) { - err = -EINVAL; - goto out; - } - /* Add this key */ - bu->zbranch[bu->cnt++] = znode->zbranch[n]; - bu->blk_cnt += 1; - lnum = znode->zbranch[n].lnum; - offs = ALIGN(znode->zbranch[n].offs + len, 8); - } - while (1) { - struct ubifs_zbranch *zbr; - union ubifs_key *key; - unsigned int next_block; - - /* Find next key */ - err = tnc_next(c, &znode, &n); - if (err) - goto out; - zbr = &znode->zbranch[n]; - key = &zbr->key; - /* See if there is another data key for this file */ - if (key_inum(c, key) != key_inum(c, &bu->key) || - key_type(c, key) != UBIFS_DATA_KEY) { - err = -ENOENT; - goto out; - } - if (lnum < 0) { - /* First key found */ - lnum = zbr->lnum; - offs = ALIGN(zbr->offs + zbr->len, 8); - len = zbr->len; - if (len > bu->buf_len) { - err = -EINVAL; - goto out; - } - } else { - /* - * The data nodes must be in consecutive positions in - * the same LEB. - */ - if (zbr->lnum != lnum || zbr->offs != offs) - goto out; - offs += ALIGN(zbr->len, 8); - len = ALIGN(len, 8) + zbr->len; - /* Must not exceed buffer length */ - if (len > bu->buf_len) - goto out; - } - /* Allow for holes */ - next_block = key_block(c, key); - bu->blk_cnt += (next_block - block - 1); - if (bu->blk_cnt >= UBIFS_MAX_BULK_READ) - goto out; - block = next_block; - /* Add this key */ - bu->zbranch[bu->cnt++] = *zbr; - bu->blk_cnt += 1; - /* See if we have room for more */ - if (bu->cnt >= UBIFS_MAX_BULK_READ) - goto out; - if (bu->blk_cnt >= UBIFS_MAX_BULK_READ) - goto out; - } -out: - if (err == -ENOENT) { - bu->eof = 1; - err = 0; - } - bu->gc_seq = c->gc_seq; - mutex_unlock(&c->tnc_mutex); - if (err) - return err; - /* - * An enormous hole could cause bulk-read to encompass too many - * page cache pages, so limit the number here. - */ - if (bu->blk_cnt > UBIFS_MAX_BULK_READ) - bu->blk_cnt = UBIFS_MAX_BULK_READ; - /* - * Ensure that bulk-read covers a whole number of page cache - * pages. - */ - if (UBIFS_BLOCKS_PER_PAGE == 1 || - !(bu->blk_cnt & (UBIFS_BLOCKS_PER_PAGE - 1))) - return 0; - if (bu->eof) { - /* At the end of file we can round up */ - bu->blk_cnt += UBIFS_BLOCKS_PER_PAGE - 1; - return 0; - } - /* Exclude data nodes that do not make up a whole page cache page */ - block = key_block(c, &bu->key) + bu->blk_cnt; - block &= ~(UBIFS_BLOCKS_PER_PAGE - 1); - while (bu->cnt) { - if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block) - break; - bu->cnt -= 1; - } - return 0; -} - -/** - * read_wbuf - bulk-read from a LEB with a wbuf. - * @wbuf: wbuf that may overlap the read - * @buf: buffer into which to read - * @len: read length - * @lnum: LEB number from which to read - * @offs: offset from which to read - * - * This functions returns %0 on success or a negative error code on failure. - */ -static int read_wbuf(struct ubifs_wbuf *wbuf, void *buf, int len, int lnum, - int offs) -{ - const struct ubifs_info *c = wbuf->c; - int rlen, overlap; - - dbg_io("LEB %d:%d, length %d", lnum, offs, len); - ubifs_assert(c, wbuf && lnum >= 0 && lnum < c->leb_cnt && offs >= 0); - ubifs_assert(c, !(offs & 7) && offs < c->leb_size); - ubifs_assert(c, offs + len <= c->leb_size); - - spin_lock(&wbuf->lock); - overlap = (lnum == wbuf->lnum && offs + len > wbuf->offs); - if (!overlap) { - /* We may safely unlock the write-buffer and read the data */ - spin_unlock(&wbuf->lock); - return ubifs_leb_read(c, lnum, buf, offs, len, 0); - } - - /* Don't read under wbuf */ - rlen = wbuf->offs - offs; - if (rlen < 0) - rlen = 0; - - /* Copy the rest from the write-buffer */ - memcpy(buf + rlen, wbuf->buf + offs + rlen - wbuf->offs, len - rlen); - spin_unlock(&wbuf->lock); - - if (rlen > 0) - /* Read everything that goes before write-buffer */ - return ubifs_leb_read(c, lnum, buf, offs, rlen, 0); - - return 0; -} - -/** - * validate_data_node - validate data nodes for bulk-read. - * @c: UBIFS file-system description object - * @buf: buffer containing data node to validate - * @zbr: zbranch of data node to validate - * - * This functions returns %0 on success or a negative error code on failure. - */ -static int validate_data_node(struct ubifs_info *c, void *buf, - struct ubifs_zbranch *zbr) -{ - union ubifs_key key1; - struct ubifs_ch *ch = buf; - int err, len; - - if (ch->node_type != UBIFS_DATA_NODE) { - ubifs_err(c, "bad node type (%d but expected %d)", - ch->node_type, UBIFS_DATA_NODE); - goto out_err; - } - - err = ubifs_check_node(c, buf, zbr->len, zbr->lnum, zbr->offs, 0, 0); - if (err) { - ubifs_err(c, "expected node type %d", UBIFS_DATA_NODE); - goto out; - } - - err = ubifs_node_check_hash(c, buf, zbr->hash); - if (err) { - ubifs_bad_hash(c, buf, zbr->hash, zbr->lnum, zbr->offs); - return err; - } - - len = le32_to_cpu(ch->len); - if (len != zbr->len) { - ubifs_err(c, "bad node length %d, expected %d", len, zbr->len); - goto out_err; - } - - /* Make sure the key of the read node is correct */ - key_read(c, buf + UBIFS_KEY_OFFSET, &key1); - if (!keys_eq(c, &zbr->key, &key1)) { - ubifs_err(c, "bad key in node at LEB %d:%d", - zbr->lnum, zbr->offs); - dbg_tnck(&zbr->key, "looked for key "); - dbg_tnck(&key1, "found node's key "); - goto out_err; - } - - return 0; - -out_err: - err = -EINVAL; -out: - ubifs_err(c, "bad node at LEB %d:%d", zbr->lnum, zbr->offs); - ubifs_dump_node(c, buf, zbr->len); - dump_stack(); - return err; -} - -/** - * ubifs_tnc_bulk_read - read a number of data nodes in one go. - * @c: UBIFS file-system description object - * @bu: bulk-read parameters and results - * - * This functions reads and validates the data nodes that were identified by the - * 'ubifs_tnc_get_bu_keys()' function. This functions returns %0 on success, - * -EAGAIN to indicate a race with GC, or another negative error code on - * failure. - */ -int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu) -{ - int lnum = bu->zbranch[0].lnum, offs = bu->zbranch[0].offs, len, err, i; - struct ubifs_wbuf *wbuf; - void *buf; - - len = bu->zbranch[bu->cnt - 1].offs; - len += bu->zbranch[bu->cnt - 1].len - offs; - if (len > bu->buf_len) { - ubifs_err(c, "buffer too small %d vs %d", bu->buf_len, len); - return -EINVAL; - } - - /* Do the read */ - wbuf = ubifs_get_wbuf(c, lnum); - if (wbuf) - err = read_wbuf(wbuf, bu->buf, len, lnum, offs); - else - err = ubifs_leb_read(c, lnum, bu->buf, offs, len, 0); - - /* Check for a race with GC */ - if (maybe_leb_gced(c, lnum, bu->gc_seq)) - return -EAGAIN; - - if (err && err != -EBADMSG) { - ubifs_err(c, "failed to read from LEB %d:%d, error %d", - lnum, offs, err); - dump_stack(); - dbg_tnck(&bu->key, "key "); - return err; - } - - /* Validate the nodes read */ - buf = bu->buf; - for (i = 0; i < bu->cnt; i++) { - err = validate_data_node(c, buf, &bu->zbranch[i]); - if (err) - return err; - buf = buf + ALIGN(bu->zbranch[i].len, 8); - } - - return 0; -} - /** * do_lookup_nm- look up a "hashed" node. * @c: UBIFS file-system description object @@ -1892,110 +1568,6 @@ int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key, return do_lookup_nm(c, key, node, nm); } -static int search_dh_cookie(struct ubifs_info *c, const union ubifs_key *key, - struct ubifs_dent_node *dent, uint32_t cookie, - struct ubifs_znode **zn, int *n, int exact) -{ - int err; - struct ubifs_znode *znode = *zn; - struct ubifs_zbranch *zbr; - union ubifs_key *dkey; - - if (!exact) { - err = tnc_next(c, &znode, n); - if (err) - return err; - } - - for (;;) { - zbr = &znode->zbranch[*n]; - dkey = &zbr->key; - - if (key_inum(c, dkey) != key_inum(c, key) || - key_type(c, dkey) != key_type(c, key)) { - return -ENOENT; - } - - err = tnc_read_hashed_node(c, zbr, dent); - if (err) - return err; - - if (key_hash(c, key) == key_hash(c, dkey) && - le32_to_cpu(dent->cookie) == cookie) { - *zn = znode; - return 0; - } - - err = tnc_next(c, &znode, n); - if (err) - return err; - } -} - -static int do_lookup_dh(struct ubifs_info *c, const union ubifs_key *key, - struct ubifs_dent_node *dent, uint32_t cookie) -{ - int n, err; - struct ubifs_znode *znode; - union ubifs_key start_key; - - ubifs_assert(c, is_hash_key(c, key)); - - lowest_dent_key(c, &start_key, key_inum(c, key)); - - mutex_lock(&c->tnc_mutex); - err = ubifs_lookup_level0(c, &start_key, &znode, &n); - if (unlikely(err < 0)) - goto out_unlock; - - err = search_dh_cookie(c, key, dent, cookie, &znode, &n, err); - -out_unlock: - mutex_unlock(&c->tnc_mutex); - return err; -} - -/** - * ubifs_tnc_lookup_dh - look up a "double hashed" node. - * @c: UBIFS file-system description object - * @key: node key to lookup - * @node: the node is returned here - * @cookie: node cookie for collision resolution - * - * This function looks up and reads a node which contains name hash in the key. - * Since the hash may have collisions, there may be many nodes with the same - * key, so we have to sequentially look to all of them until the needed one - * with the same cookie value is found. - * This function returns zero in case of success, %-ENOENT if the node - * was not found, and a negative error code in case of failure. - */ -int ubifs_tnc_lookup_dh(struct ubifs_info *c, const union ubifs_key *key, - void *node, uint32_t cookie) -{ - int err; - const struct ubifs_dent_node *dent = node; - - if (!c->double_hash) - return -EOPNOTSUPP; - - /* - * We assume that in most of the cases there are no name collisions and - * 'ubifs_tnc_lookup()' returns us the right direntry. - */ - err = ubifs_tnc_lookup(c, key, node); - if (err) - return err; - - if (le32_to_cpu(dent->cookie) == cookie) - return 0; - - /* - * Unluckily, there are hash collisions and we have to iterate over - * them look at each direntry with colliding name hash sequentially. - */ - return do_lookup_dh(c, key, node, cookie); -} - /** * correct_parent_keys - correct parent znodes' keys. * @c: UBIFS file-system description object @@ -2540,6 +2112,10 @@ static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n) if (znode->child_cnt > 0) return 0; + /* Different with linux kernel, TNC could become empty. */ + if (!znode->parent) + return 0; + /* * This was the last zbranch, we have to delete this znode from the * parent. @@ -2696,74 +2272,6 @@ out_unlock: return err; } -/** - * ubifs_tnc_remove_dh - remove an index entry for a "double hashed" node. - * @c: UBIFS file-system description object - * @key: key of node - * @cookie: node cookie for collision resolution - * - * Returns %0 on success or negative error code on failure. - */ -int ubifs_tnc_remove_dh(struct ubifs_info *c, const union ubifs_key *key, - uint32_t cookie) -{ - int n, err; - struct ubifs_znode *znode; - struct ubifs_dent_node *dent; - struct ubifs_zbranch *zbr; - - if (!c->double_hash) - return -EOPNOTSUPP; - - mutex_lock(&c->tnc_mutex); - err = lookup_level0_dirty(c, key, &znode, &n); - if (err <= 0) - goto out_unlock; - - zbr = &znode->zbranch[n]; - dent = kmalloc(UBIFS_MAX_DENT_NODE_SZ, GFP_NOFS); - if (!dent) { - err = -ENOMEM; - goto out_unlock; - } - - err = tnc_read_hashed_node(c, zbr, dent); - if (err) - goto out_free; - - /* If the cookie does not match, we're facing a hash collision. */ - if (le32_to_cpu(dent->cookie) != cookie) { - union ubifs_key start_key; - - lowest_dent_key(c, &start_key, key_inum(c, key)); - - err = ubifs_lookup_level0(c, &start_key, &znode, &n); - if (unlikely(err < 0)) - goto out_free; - - err = search_dh_cookie(c, key, dent, cookie, &znode, &n, err); - if (err) - goto out_free; - } - - if (znode->cnext || !ubifs_zn_dirty(znode)) { - znode = dirty_cow_bottom_up(c, znode); - if (IS_ERR(znode)) { - err = PTR_ERR(znode); - goto out_free; - } - } - err = tnc_delete(c, znode, n); - -out_free: - kfree(dent); -out_unlock: - if (!err) - err = dbg_check_tnc(c, 0); - mutex_unlock(&c->tnc_mutex); - return err; -} - /** * key_in_range - determine if a key falls within a range of keys. * @c: UBIFS file-system description object @@ -2905,9 +2413,7 @@ int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum) dbg_tnc("xent '%s', ino %lu", xent->name, (unsigned long)xattr_inum); - ubifs_evict_xattr_inode(c, xattr_inum); - - fname_name(&nm) = xent->name; + fname_name(&nm) = (const char *)xent->name; fname_len(&nm) = le16_to_cpu(xent->nlen); err = ubifs_tnc_remove_nm(c, &key1, &nm); if (err) { @@ -3485,69 +2991,3 @@ out_unlock: mutex_unlock(&c->tnc_mutex); return err; } - -/** - * dbg_check_inode_size - check if inode size is correct. - * @c: UBIFS file-system description object - * @inode: inode to check - * @size: inode size - * - * This function makes sure that the inode size (@size) is correct and it does - * not have any pages beyond @size. Returns zero if the inode is OK, %-EINVAL - * if it has a data page beyond @size, and other negative error code in case of - * other errors. - */ -int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode, - loff_t size) -{ - int err, n; - union ubifs_key from_key, to_key, *key; - struct ubifs_znode *znode; - unsigned int block; - - if (!S_ISREG(inode->i_mode)) - return 0; - if (!dbg_is_chk_gen(c)) - return 0; - - block = (size + UBIFS_BLOCK_SIZE - 1) >> UBIFS_BLOCK_SHIFT; - data_key_init(c, &from_key, inode->i_ino, block); - highest_data_key(c, &to_key, inode->i_ino); - - mutex_lock(&c->tnc_mutex); - err = ubifs_lookup_level0(c, &from_key, &znode, &n); - if (err < 0) - goto out_unlock; - - if (err) { - key = &from_key; - goto out_dump; - } - - err = tnc_next(c, &znode, &n); - if (err == -ENOENT) { - err = 0; - goto out_unlock; - } - if (err < 0) - goto out_unlock; - - ubifs_assert(c, err == 0); - key = &znode->zbranch[n].key; - if (!key_in_range(c, key, &from_key, &to_key)) - goto out_unlock; - -out_dump: - block = key_block(c, key); - ubifs_err(c, "inode %lu has size %lld, but there are data at offset %lld", - (unsigned long)inode->i_ino, size, - ((loff_t)block) << UBIFS_BLOCK_SHIFT); - mutex_unlock(&c->tnc_mutex); - ubifs_dump_inode(c, inode); - dump_stack(); - return -EINVAL; - -out_unlock: - mutex_unlock(&c->tnc_mutex); - return err; -} diff --git a/ubifs-utils/libubifs/tnc_commit.c b/ubifs-utils/libubifs/tnc_commit.c index a55e048..d797006 100644 --- a/ubifs-utils/libubifs/tnc_commit.c +++ b/ubifs-utils/libubifs/tnc_commit.c @@ -10,8 +10,14 @@ /* This file implements TNC functions for committing */ -#include +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" #include "ubifs.h" +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" /** * make_idx_node - make an index node for fill-the-gaps method of TNC commit. @@ -546,8 +552,8 @@ static int layout_in_empty_space(struct ubifs_info *c) break; } - c->dbg->new_ihead_lnum = lnum; - c->dbg->new_ihead_offs = buf_offs; + c->new_ihead_lnum = lnum; + c->new_ihead_offs = buf_offs; return 0; } @@ -700,7 +706,7 @@ static int alloc_idx_lebs(struct ubifs_info *c, int cnt) c->ilebs[c->ileb_cnt++] = lnum; dbg_cmt("LEB %d", lnum); } - if (dbg_is_chk_index(c) && !get_random_u32_below(8)) + if (dbg_is_chk_index(c)) return -ENOSPC; return 0; } @@ -1011,8 +1017,8 @@ static int write_index(struct ubifs_info *c) break; } - if (lnum != c->dbg->new_ihead_lnum || - buf_offs != c->dbg->new_ihead_offs) { + if (lnum != c->new_ihead_lnum || + buf_offs != c->new_ihead_offs) { ubifs_err(c, "inconsistent ihead"); return -EINVAL; } diff --git a/ubifs-utils/libubifs/tnc_misc.c b/ubifs-utils/libubifs/tnc_misc.c index d3f8a6a..8c38f15 100644 --- a/ubifs-utils/libubifs/tnc_misc.c +++ b/ubifs-utils/libubifs/tnc_misc.c @@ -15,97 +15,14 @@ * putting it all in one file would make that file too big and unreadable. */ +#include "linux_err.h" +#include "bitops.h" +#include "kmem.h" #include "ubifs.h" - -/** - * ubifs_tnc_levelorder_next - next TNC tree element in levelorder traversal. - * @c: UBIFS file-system description object - * @zr: root of the subtree to traverse - * @znode: previous znode - * - * This function implements levelorder TNC traversal. The LNC is ignored. - * Returns the next element or %NULL if @znode is already the last one. - */ -struct ubifs_znode *ubifs_tnc_levelorder_next(const struct ubifs_info *c, - struct ubifs_znode *zr, - struct ubifs_znode *znode) -{ - int level, iip, level_search = 0; - struct ubifs_znode *zn; - - ubifs_assert(c, zr); - - if (unlikely(!znode)) - return zr; - - if (unlikely(znode == zr)) { - if (znode->level == 0) - return NULL; - return ubifs_tnc_find_child(zr, 0); - } - - level = znode->level; - - iip = znode->iip; - while (1) { - ubifs_assert(c, znode->level <= zr->level); - - /* - * First walk up until there is a znode with next branch to - * look at. - */ - while (znode->parent != zr && iip >= znode->parent->child_cnt) { - znode = znode->parent; - iip = znode->iip; - } - - if (unlikely(znode->parent == zr && - iip >= znode->parent->child_cnt)) { - /* This level is done, switch to the lower one */ - level -= 1; - if (level_search || level < 0) - /* - * We were already looking for znode at lower - * level ('level_search'). As we are here - * again, it just does not exist. Or all levels - * were finished ('level < 0'). - */ - return NULL; - - level_search = 1; - iip = -1; - znode = ubifs_tnc_find_child(zr, 0); - ubifs_assert(c, znode); - } - - /* Switch to the next index */ - zn = ubifs_tnc_find_child(znode->parent, iip + 1); - if (!zn) { - /* No more children to look at, we have walk up */ - iip = znode->parent->child_cnt; - continue; - } - - /* Walk back down to the level we came from ('level') */ - while (zn->level != level) { - znode = zn; - zn = ubifs_tnc_find_child(zn, 0); - if (!zn) { - /* - * This path is not too deep so it does not - * reach 'level'. Try next path. - */ - iip = znode->iip; - break; - } - } - - if (zn) { - ubifs_assert(c, zn->level >= 0); - return zn; - } - } -} +#include "defs.h" +#include "debug.h" +#include "key.h" +#include "misc.h" /** * ubifs_search_zbranch - search znode branch. @@ -130,6 +47,12 @@ int ubifs_search_zbranch(const struct ubifs_info *c, int cmp; const struct ubifs_zbranch *zbr = &znode->zbranch[0]; + if (!end) { + /* Different with linux kernel, TNC could become empty. */ + *n = -1; + return 0; + } + ubifs_assert(c, end > beg); while (end > beg) { @@ -360,9 +283,10 @@ static int read_znode(struct ubifs_info *c, struct ubifs_zbranch *zzbr, } if (znode->level) - continue; + type = UBIFS_IDX_NODE; + else + type = key_type(c, &zbr->key); - type = key_type(c, &zbr->key); if (c->ranges[type].max_len == 0) { if (zbr->len != c->ranges[type].len) { ubifs_err(c, "bad target node (type %d) length (%d)", -- cgit v1.2.3