Lines Matching refs:c
25 static int try_read_node(const struct ubifs_info *c, void *buf, int type,
27 static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key,
70 static int insert_old_idx(struct ubifs_info *c, int lnum, int offs) in insert_old_idx() argument
81 p = &c->old_idx.rb_node; in insert_old_idx()
94 ubifs_err(c, "old idx added twice!"); in insert_old_idx()
100 rb_insert_color(&old_idx->rb, &c->old_idx); in insert_old_idx()
111 int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) in insert_old_idx_znode() argument
118 return insert_old_idx(c, zbr->lnum, zbr->offs); in insert_old_idx_znode()
120 if (c->zroot.len) in insert_old_idx_znode()
121 return insert_old_idx(c, c->zroot.lnum, in insert_old_idx_znode()
122 c->zroot.offs); in insert_old_idx_znode()
133 static int ins_clr_old_idx_znode(struct ubifs_info *c, in ins_clr_old_idx_znode() argument
143 err = insert_old_idx(c, zbr->lnum, zbr->offs); in ins_clr_old_idx_znode()
151 if (c->zroot.len) { in ins_clr_old_idx_znode()
152 err = insert_old_idx(c, c->zroot.lnum, c->zroot.offs); in ins_clr_old_idx_znode()
155 c->zroot.lnum = 0; in ins_clr_old_idx_znode()
156 c->zroot.offs = 0; in ins_clr_old_idx_znode()
157 c->zroot.len = 0; in ins_clr_old_idx_znode()
172 void destroy_old_idx(struct ubifs_info *c) in destroy_old_idx() argument
176 rbtree_postorder_for_each_entry_safe(old_idx, n, &c->old_idx, rb) in destroy_old_idx()
179 c->old_idx = RB_ROOT; in destroy_old_idx()
189 static struct ubifs_znode *copy_znode(struct ubifs_info *c, in copy_znode() argument
194 zn = kmemdup(znode, c->max_znode_sz, GFP_NOFS); in copy_znode()
202 ubifs_assert(c, !ubifs_zn_obsolete(znode)); in copy_znode()
218 atomic_long_inc(&c->dirty_zn_cnt); in copy_znode()
230 static int add_idx_dirt(struct ubifs_info *c, int lnum, int dirt) in add_idx_dirt() argument
232 c->calc_idx_sz -= ALIGN(dirt, 8); in add_idx_dirt()
233 return ubifs_add_dirt(c, lnum, dirt); in add_idx_dirt()
243 static struct ubifs_znode *dirty_cow_znode(struct ubifs_info *c, in dirty_cow_znode() argument
253 atomic_long_inc(&c->dirty_zn_cnt); in dirty_cow_znode()
254 atomic_long_dec(&c->clean_zn_cnt); in dirty_cow_znode()
256 err = add_idx_dirt(c, zbr->lnum, zbr->len); in dirty_cow_znode()
263 zn = copy_znode(c, znode); in dirty_cow_znode()
268 err = insert_old_idx(c, zbr->lnum, zbr->offs); in dirty_cow_znode()
271 err = add_idx_dirt(c, zbr->lnum, zbr->len); in dirty_cow_znode()
305 static int lnc_add(struct ubifs_info *c, struct ubifs_zbranch *zbr, in lnc_add() argument
312 ubifs_assert(c, !zbr->leaf); in lnc_add()
313 ubifs_assert(c, zbr->len != 0); in lnc_add()
314 ubifs_assert(c, is_hash_key(c, &zbr->key)); in lnc_add()
316 err = ubifs_validate_entry(c, dent); in lnc_add()
319 ubifs_dump_node(c, dent); in lnc_add()
341 static int lnc_add_directly(struct ubifs_info *c, struct ubifs_zbranch *zbr, in lnc_add_directly() argument
346 ubifs_assert(c, !zbr->leaf); in lnc_add_directly()
347 ubifs_assert(c, zbr->len != 0); in lnc_add_directly()
349 err = ubifs_validate_entry(c, node); in lnc_add_directly()
352 ubifs_dump_node(c, node); in lnc_add_directly()
384 static int tnc_read_hashed_node(struct ubifs_info *c, struct ubifs_zbranch *zbr, in tnc_read_hashed_node() argument
389 ubifs_assert(c, is_hash_key(c, &zbr->key)); in tnc_read_hashed_node()
393 ubifs_assert(c, zbr->len != 0); in tnc_read_hashed_node()
398 if (c->replaying) { in tnc_read_hashed_node()
399 err = fallible_read_node(c, &zbr->key, zbr, node); in tnc_read_hashed_node()
409 err = ubifs_tnc_read_node(c, zbr, node); in tnc_read_hashed_node()
415 err = lnc_add(c, zbr, node); in tnc_read_hashed_node()
441 static int try_read_node(const struct ubifs_info *c, void *buf, int type, in try_read_node() argument
453 err = ubifs_leb_read(c, lnum, buf, offs, len, 1); in try_read_node()
455 ubifs_err(c, "cannot read node type %d from LEB %d:%d, error %d", in try_read_node()
470 if (type != UBIFS_DATA_NODE || !c->no_chk_data_crc || c->mounting || in try_read_node()
471 c->remounting_rw) { in try_read_node()
478 err = ubifs_node_check_hash(c, buf, zbr->hash); in try_read_node()
480 ubifs_bad_hash(c, buf, zbr->hash, lnum, offs); in try_read_node()
497 static int fallible_read_node(struct ubifs_info *c, const union ubifs_key *key, in fallible_read_node() argument
504 ret = try_read_node(c, node, key_type(c, key), zbr); in fallible_read_node()
510 key_read(c, &dent->key, &node_key); in fallible_read_node()
511 if (keys_cmp(c, key, &node_key) != 0) in fallible_read_node()
514 if (ret == 0 && c->replaying) in fallible_read_node()
531 static int matches_name(struct ubifs_info *c, struct ubifs_zbranch *zbr, in matches_name() argument
543 err = ubifs_tnc_read_node(c, zbr, dent); in matches_name()
548 err = lnc_add_directly(c, zbr, dent); in matches_name()
581 static struct ubifs_znode *get_znode(struct ubifs_info *c, in get_znode() argument
590 znode = ubifs_load_znode(c, zbr, znode, n); in get_znode()
603 static int tnc_next(struct ubifs_info *c, struct ubifs_znode **zn, int *n) in tnc_next() argument
622 znode = get_znode(c, znode, nn); in tnc_next()
626 znode = get_znode(c, znode, 0); in tnc_next()
648 static int tnc_prev(struct ubifs_info *c, struct ubifs_znode **zn, int *n) in tnc_prev() argument
666 znode = get_znode(c, znode, nn); in tnc_prev()
671 znode = get_znode(c, znode, nn); in tnc_prev()
700 static int resolve_collision(struct ubifs_info *c, const union ubifs_key *key, in resolve_collision() argument
706 err = matches_name(c, &(*zn)->zbranch[*n], nm); in resolve_collision()
715 err = tnc_prev(c, zn, n); in resolve_collision()
717 ubifs_assert(c, *n == 0); in resolve_collision()
723 if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) { in resolve_collision()
754 err = tnc_next(c, zn, n); in resolve_collision()
757 ubifs_assert(c, 0); in resolve_collision()
762 ubifs_assert(c, *n == 0); in resolve_collision()
767 err = matches_name(c, &(*zn)->zbranch[*n], nm); in resolve_collision()
774 ubifs_assert(c, err == NAME_GREATER); in resolve_collision()
782 err = tnc_next(c, &znode, &nn); in resolve_collision()
787 if (keys_cmp(c, &znode->zbranch[nn].key, key)) in resolve_collision()
789 err = matches_name(c, &znode->zbranch[nn], nm); in resolve_collision()
798 ubifs_assert(c, err == NAME_LESS); in resolve_collision()
818 static int fallible_matches_name(struct ubifs_info *c, in fallible_matches_name() argument
831 err = fallible_read_node(c, &zbr->key, zbr, dent); in fallible_matches_name()
839 ubifs_assert(c, err == 1); in fallible_matches_name()
841 err = lnc_add_directly(c, zbr, dent); in fallible_matches_name()
888 static int fallible_resolve_collision(struct ubifs_info *c, in fallible_resolve_collision() argument
897 cmp = fallible_matches_name(c, &znode->zbranch[nn], nm); in fallible_resolve_collision()
917 err = tnc_prev(c, zn, n); in fallible_resolve_collision()
919 ubifs_assert(c, *n == 0); in fallible_resolve_collision()
925 if (keys_cmp(c, &(*zn)->zbranch[*n].key, key)) { in fallible_resolve_collision()
928 err = tnc_next(c, zn, n); in fallible_resolve_collision()
931 ubifs_assert(c, 0); in fallible_resolve_collision()
936 ubifs_assert(c, *n == 0); in fallible_resolve_collision()
941 err = fallible_matches_name(c, &(*zn)->zbranch[*n], nm); in fallible_resolve_collision()
965 err = tnc_next(c, &znode, &nn); in fallible_resolve_collision()
970 if (keys_cmp(c, &znode->zbranch[nn].key, key)) in fallible_resolve_collision()
972 err = fallible_matches_name(c, &znode->zbranch[nn], nm); in fallible_resolve_collision()
1033 static int resolve_collision_directly(struct ubifs_info *c, in resolve_collision_directly() argument
1048 err = tnc_prev(c, &znode, &nn); in resolve_collision_directly()
1053 if (keys_cmp(c, &znode->zbranch[nn].key, key)) in resolve_collision_directly()
1066 err = tnc_next(c, &znode, &nn); in resolve_collision_directly()
1071 if (keys_cmp(c, &znode->zbranch[nn].key, key)) in resolve_collision_directly()
1090 static struct ubifs_znode *dirty_cow_bottom_up(struct ubifs_info *c, in dirty_cow_bottom_up() argument
1094 int *path = c->bottom_up_buf, p = 0; in dirty_cow_bottom_up()
1096 ubifs_assert(c, c->zroot.znode); in dirty_cow_bottom_up()
1097 ubifs_assert(c, znode); in dirty_cow_bottom_up()
1098 if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) { in dirty_cow_bottom_up()
1099 kfree(c->bottom_up_buf); in dirty_cow_bottom_up()
1100 c->bottom_up_buf = kmalloc_array(c->zroot.znode->level, in dirty_cow_bottom_up()
1103 if (!c->bottom_up_buf) in dirty_cow_bottom_up()
1105 path = c->bottom_up_buf; in dirty_cow_bottom_up()
1107 if (c->zroot.znode->level) { in dirty_cow_bottom_up()
1116 ubifs_assert(c, p < c->zroot.znode->level); in dirty_cow_bottom_up()
1130 ubifs_assert(c, path[p - 1] >= 0); in dirty_cow_bottom_up()
1131 ubifs_assert(c, path[p - 1] < zp->child_cnt); in dirty_cow_bottom_up()
1133 znode = dirty_cow_znode(c, zbr); in dirty_cow_bottom_up()
1135 ubifs_assert(c, znode == c->zroot.znode); in dirty_cow_bottom_up()
1136 znode = dirty_cow_znode(c, &c->zroot); in dirty_cow_bottom_up()
1140 ubifs_assert(c, path[p - 1] >= 0); in dirty_cow_bottom_up()
1141 ubifs_assert(c, path[p - 1] < znode->child_cnt); in dirty_cow_bottom_up()
1170 int ubifs_lookup_level0(struct ubifs_info *c, const union ubifs_key *key, in ubifs_lookup_level0() argument
1178 ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY); in ubifs_lookup_level0()
1180 znode = c->zroot.znode; in ubifs_lookup_level0()
1182 znode = ubifs_load_znode(c, &c->zroot, NULL, 0); in ubifs_lookup_level0()
1192 exact = ubifs_search_zbranch(c, znode, key, n); in ubifs_lookup_level0()
1208 znode = ubifs_load_znode(c, zbr, znode, *n); in ubifs_lookup_level0()
1214 if (exact || !is_hash_key(c, key) || *n != -1) { in ubifs_lookup_level0()
1262 err = tnc_prev(c, &znode, n); in ubifs_lookup_level0()
1270 if (keys_cmp(c, key, &znode->zbranch[*n].key)) { in ubifs_lookup_level0()
1306 static int lookup_level0_dirty(struct ubifs_info *c, const union ubifs_key *key, in lookup_level0_dirty() argument
1315 znode = c->zroot.znode; in lookup_level0_dirty()
1317 znode = ubifs_load_znode(c, &c->zroot, NULL, 0); in lookup_level0_dirty()
1322 znode = dirty_cow_znode(c, &c->zroot); in lookup_level0_dirty()
1331 exact = ubifs_search_zbranch(c, znode, key, n); in lookup_level0_dirty()
1342 znode = dirty_cow_znode(c, zbr); in lookup_level0_dirty()
1349 znode = ubifs_load_znode(c, zbr, znode, *n); in lookup_level0_dirty()
1352 znode = dirty_cow_znode(c, zbr); in lookup_level0_dirty()
1358 if (exact || !is_hash_key(c, key) || *n != -1) { in lookup_level0_dirty()
1367 err = tnc_prev(c, &znode, n); in lookup_level0_dirty()
1375 if (keys_cmp(c, key, &znode->zbranch[*n].key)) { in lookup_level0_dirty()
1382 znode = dirty_cow_bottom_up(c, znode); in lookup_level0_dirty()
1402 static int maybe_leb_gced(struct ubifs_info *c, int lnum, int gc_seq1) in maybe_leb_gced() argument
1406 gced_lnum = c->gced_lnum; in maybe_leb_gced()
1408 gc_seq2 = c->gc_seq; in maybe_leb_gced()
1420 if (gced_lnum != c->gced_lnum) in maybe_leb_gced()
1441 int ubifs_tnc_locate(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_locate() argument
1449 mutex_lock(&c->tnc_mutex); in ubifs_tnc_locate()
1450 found = ubifs_lookup_level0(c, key, &znode, &n); in ubifs_tnc_locate()
1463 if (is_hash_key(c, key)) { in ubifs_tnc_locate()
1468 err = tnc_read_hashed_node(c, zt, node); in ubifs_tnc_locate()
1472 err = ubifs_tnc_read_node(c, zt, node); in ubifs_tnc_locate()
1477 gc_seq1 = c->gc_seq; in ubifs_tnc_locate()
1478 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_locate()
1480 if (ubifs_get_wbuf(c, zbr.lnum)) { in ubifs_tnc_locate()
1482 err = ubifs_tnc_read_node(c, &zbr, node); in ubifs_tnc_locate()
1486 err = fallible_read_node(c, key, &zbr, node); in ubifs_tnc_locate()
1487 if (err <= 0 || maybe_leb_gced(c, zbr.lnum, gc_seq1)) { in ubifs_tnc_locate()
1498 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_locate()
1515 int ubifs_tnc_get_bu_keys(struct ubifs_info *c, struct bu_info *bu) in ubifs_tnc_get_bu_keys() argument
1519 unsigned int block = key_block(c, &bu->key); in ubifs_tnc_get_bu_keys()
1526 mutex_lock(&c->tnc_mutex); in ubifs_tnc_get_bu_keys()
1528 err = ubifs_lookup_level0(c, &bu->key, &znode, &n); in ubifs_tnc_get_bu_keys()
1551 err = tnc_next(c, &znode, &n); in ubifs_tnc_get_bu_keys()
1557 if (key_inum(c, key) != key_inum(c, &bu->key) || in ubifs_tnc_get_bu_keys()
1558 key_type(c, key) != UBIFS_DATA_KEY) { in ubifs_tnc_get_bu_keys()
1585 next_block = key_block(c, key); in ubifs_tnc_get_bu_keys()
1604 bu->gc_seq = c->gc_seq; in ubifs_tnc_get_bu_keys()
1605 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_get_bu_keys()
1627 block = key_block(c, &bu->key) + bu->blk_cnt; in ubifs_tnc_get_bu_keys()
1630 if (key_block(c, &bu->zbranch[bu->cnt - 1].key) < block) in ubifs_tnc_get_bu_keys()
1650 const struct ubifs_info *c = wbuf->c; in read_wbuf() local
1654 ubifs_assert(c, wbuf && lnum >= 0 && lnum < c->leb_cnt && offs >= 0); in read_wbuf()
1655 ubifs_assert(c, !(offs & 7) && offs < c->leb_size); in read_wbuf()
1656 ubifs_assert(c, offs + len <= c->leb_size); in read_wbuf()
1663 return ubifs_leb_read(c, lnum, buf, offs, len, 0); in read_wbuf()
1677 return ubifs_leb_read(c, lnum, buf, offs, rlen, 0); in read_wbuf()
1690 static int validate_data_node(struct ubifs_info *c, void *buf, in validate_data_node() argument
1698 ubifs_err(c, "bad node type (%d but expected %d)", in validate_data_node()
1703 err = ubifs_check_node(c, buf, zbr->lnum, zbr->offs, 0, 0); in validate_data_node()
1705 ubifs_err(c, "expected node type %d", UBIFS_DATA_NODE); in validate_data_node()
1709 err = ubifs_node_check_hash(c, buf, zbr->hash); in validate_data_node()
1711 ubifs_bad_hash(c, buf, zbr->hash, zbr->lnum, zbr->offs); in validate_data_node()
1717 ubifs_err(c, "bad node length %d, expected %d", len, zbr->len); in validate_data_node()
1722 key_read(c, buf + UBIFS_KEY_OFFSET, &key1); in validate_data_node()
1723 if (!keys_eq(c, &zbr->key, &key1)) { in validate_data_node()
1724 ubifs_err(c, "bad key in node at LEB %d:%d", in validate_data_node()
1736 ubifs_err(c, "bad node at LEB %d:%d", zbr->lnum, zbr->offs); in validate_data_node()
1737 ubifs_dump_node(c, buf); in validate_data_node()
1752 int ubifs_tnc_bulk_read(struct ubifs_info *c, struct bu_info *bu) in ubifs_tnc_bulk_read() argument
1761 ubifs_err(c, "buffer too small %d vs %d", bu->buf_len, len); in ubifs_tnc_bulk_read()
1766 wbuf = ubifs_get_wbuf(c, lnum); in ubifs_tnc_bulk_read()
1770 err = ubifs_leb_read(c, lnum, bu->buf, offs, len, 0); in ubifs_tnc_bulk_read()
1773 if (maybe_leb_gced(c, lnum, bu->gc_seq)) in ubifs_tnc_bulk_read()
1777 ubifs_err(c, "failed to read from LEB %d:%d, error %d", in ubifs_tnc_bulk_read()
1787 err = validate_data_node(c, buf, &bu->zbranch[i]); in ubifs_tnc_bulk_read()
1809 static int do_lookup_nm(struct ubifs_info *c, const union ubifs_key *key, in do_lookup_nm() argument
1816 mutex_lock(&c->tnc_mutex); in do_lookup_nm()
1817 found = ubifs_lookup_level0(c, key, &znode, &n); in do_lookup_nm()
1826 ubifs_assert(c, n >= 0); in do_lookup_nm()
1828 err = resolve_collision(c, key, &znode, &n, nm); in do_lookup_nm()
1837 err = tnc_read_hashed_node(c, &znode->zbranch[n], node); in do_lookup_nm()
1840 mutex_unlock(&c->tnc_mutex); in do_lookup_nm()
1857 int ubifs_tnc_lookup_nm(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_lookup_nm() argument
1867 err = ubifs_tnc_lookup(c, key, node); in ubifs_tnc_lookup_nm()
1880 return do_lookup_nm(c, key, node, nm); in ubifs_tnc_lookup_nm()
1883 static int search_dh_cookie(struct ubifs_info *c, const union ubifs_key *key, in search_dh_cookie() argument
1893 err = tnc_next(c, &znode, n); in search_dh_cookie()
1902 if (key_inum(c, dkey) != key_inum(c, key) || in search_dh_cookie()
1903 key_type(c, dkey) != key_type(c, key)) { in search_dh_cookie()
1907 err = tnc_read_hashed_node(c, zbr, dent); in search_dh_cookie()
1911 if (key_hash(c, key) == key_hash(c, dkey) && in search_dh_cookie()
1917 err = tnc_next(c, &znode, n); in search_dh_cookie()
1923 static int do_lookup_dh(struct ubifs_info *c, const union ubifs_key *key, in do_lookup_dh() argument
1930 ubifs_assert(c, is_hash_key(c, key)); in do_lookup_dh()
1932 lowest_dent_key(c, &start_key, key_inum(c, key)); in do_lookup_dh()
1934 mutex_lock(&c->tnc_mutex); in do_lookup_dh()
1935 err = ubifs_lookup_level0(c, &start_key, &znode, &n); in do_lookup_dh()
1939 err = search_dh_cookie(c, key, dent, cookie, &znode, &n, err); in do_lookup_dh()
1942 mutex_unlock(&c->tnc_mutex); in do_lookup_dh()
1960 int ubifs_tnc_lookup_dh(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_lookup_dh() argument
1966 if (!c->double_hash) in ubifs_tnc_lookup_dh()
1973 err = ubifs_tnc_lookup(c, key, node); in ubifs_tnc_lookup_dh()
1984 return do_lookup_dh(c, key, node, cookie); in ubifs_tnc_lookup_dh()
1996 static void correct_parent_keys(const struct ubifs_info *c, in correct_parent_keys() argument
2001 ubifs_assert(c, znode->parent); in correct_parent_keys()
2002 ubifs_assert(c, znode->iip == 0); in correct_parent_keys()
2007 while (keys_cmp(c, key, key1) < 0) { in correct_parent_keys()
2008 key_copy(c, key, key1); in correct_parent_keys()
2029 static void insert_zbranch(struct ubifs_info *c, struct ubifs_znode *znode, in insert_zbranch() argument
2034 ubifs_assert(c, ubifs_zn_dirty(znode)); in insert_zbranch()
2081 static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode, in tnc_insert() argument
2088 ubifs_assert(c, n >= 0 && n <= c->fanout); in tnc_insert()
2093 if (znode->child_cnt < c->fanout) { in tnc_insert()
2094 ubifs_assert(c, n != c->fanout); in tnc_insert()
2097 insert_zbranch(c, znode, zbr, n); in tnc_insert()
2101 correct_parent_keys(c, znode); in tnc_insert()
2117 ins_clr_old_idx_znode(c, znode); in tnc_insert()
2119 zn = kzalloc(c->max_znode_sz, GFP_NOFS); in tnc_insert()
2126 if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) { in tnc_insert()
2128 if (n == c->fanout) { in tnc_insert()
2130 if (key_inum(c, key1) == key_inum(c, key) && in tnc_insert()
2131 key_type(c, key1) == UBIFS_DATA_KEY) in tnc_insert()
2135 } else if (appending && n != c->fanout) { in tnc_insert()
2139 if (n >= (c->fanout + 1) / 2) { in tnc_insert()
2141 if (key_inum(c, key1) == key_inum(c, key) && in tnc_insert()
2142 key_type(c, key1) == UBIFS_DATA_KEY) { in tnc_insert()
2144 if (key_inum(c, key1) != key_inum(c, key) || in tnc_insert()
2145 key_type(c, key1) != UBIFS_DATA_KEY) { in tnc_insert()
2147 move = c->fanout - keep; in tnc_insert()
2156 keep = c->fanout; in tnc_insert()
2159 keep = (c->fanout + 1) / 2; in tnc_insert()
2160 move = c->fanout - keep; in tnc_insert()
2185 atomic_long_inc(&c->dirty_zn_cnt); in tnc_insert()
2206 insert_zbranch(c, zi, zbr, n); in tnc_insert()
2211 correct_parent_keys(c, znode); in tnc_insert()
2230 zi = kzalloc(c->max_znode_sz, GFP_NOFS); in tnc_insert()
2238 atomic_long_inc(&c->dirty_zn_cnt); in tnc_insert()
2242 zi->zbranch[0].lnum = c->zroot.lnum; in tnc_insert()
2243 zi->zbranch[0].offs = c->zroot.offs; in tnc_insert()
2244 zi->zbranch[0].len = c->zroot.len; in tnc_insert()
2248 c->zroot.lnum = 0; in tnc_insert()
2249 c->zroot.offs = 0; in tnc_insert()
2250 c->zroot.len = 0; in tnc_insert()
2251 c->zroot.znode = zi; in tnc_insert()
2274 int ubifs_tnc_add(struct ubifs_info *c, const union ubifs_key *key, int lnum, in ubifs_tnc_add() argument
2280 mutex_lock(&c->tnc_mutex); in ubifs_tnc_add()
2282 found = lookup_level0_dirty(c, key, &znode, &n); in ubifs_tnc_add()
2290 ubifs_copy_hash(c, hash, zbr.hash); in ubifs_tnc_add()
2291 key_copy(c, key, &zbr.key); in ubifs_tnc_add()
2292 err = tnc_insert(c, znode, &zbr, n + 1); in ubifs_tnc_add()
2297 err = ubifs_add_dirt(c, zbr->lnum, zbr->len); in ubifs_tnc_add()
2301 ubifs_copy_hash(c, hash, zbr->hash); in ubifs_tnc_add()
2305 err = dbg_check_tnc(c, 0); in ubifs_tnc_add()
2306 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_add()
2325 int ubifs_tnc_replace(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_replace() argument
2331 mutex_lock(&c->tnc_mutex); in ubifs_tnc_replace()
2334 found = lookup_level0_dirty(c, key, &znode, &n); in ubifs_tnc_replace()
2346 err = ubifs_add_dirt(c, zbr->lnum, zbr->len); in ubifs_tnc_replace()
2353 } else if (is_hash_key(c, key)) { in ubifs_tnc_replace()
2354 found = resolve_collision_directly(c, key, &znode, &n, in ubifs_tnc_replace()
2366 znode = dirty_cow_bottom_up(c, znode); in ubifs_tnc_replace()
2374 err = ubifs_add_dirt(c, zbr->lnum, in ubifs_tnc_replace()
2386 err = ubifs_add_dirt(c, lnum, len); in ubifs_tnc_replace()
2389 err = dbg_check_tnc(c, 0); in ubifs_tnc_replace()
2392 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_replace()
2409 int ubifs_tnc_add_nm(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_add_nm() argument
2416 mutex_lock(&c->tnc_mutex); in ubifs_tnc_add_nm()
2418 found = lookup_level0_dirty(c, key, &znode, &n); in ubifs_tnc_add_nm()
2425 if (c->replaying) in ubifs_tnc_add_nm()
2426 found = fallible_resolve_collision(c, key, &znode, &n, in ubifs_tnc_add_nm()
2429 found = resolve_collision(c, key, &znode, &n, nm); in ubifs_tnc_add_nm()
2438 znode = dirty_cow_bottom_up(c, znode); in ubifs_tnc_add_nm()
2449 err = ubifs_add_dirt(c, zbr->lnum, zbr->len); in ubifs_tnc_add_nm()
2453 ubifs_copy_hash(c, hash, zbr->hash); in ubifs_tnc_add_nm()
2465 ubifs_copy_hash(c, hash, zbr.hash); in ubifs_tnc_add_nm()
2466 key_copy(c, key, &zbr.key); in ubifs_tnc_add_nm()
2467 err = tnc_insert(c, znode, &zbr, n + 1); in ubifs_tnc_add_nm()
2470 if (c->replaying) { in ubifs_tnc_add_nm()
2479 err = dbg_check_tnc(c, 0); in ubifs_tnc_add_nm()
2480 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_add_nm()
2483 return ubifs_tnc_remove_nm(c, key, &noname); in ubifs_tnc_add_nm()
2489 err = dbg_check_tnc(c, 0); in ubifs_tnc_add_nm()
2490 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_add_nm()
2503 static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n) in tnc_delete() argument
2510 ubifs_assert(c, znode->level == 0); in tnc_delete()
2511 ubifs_assert(c, n >= 0 && n < c->fanout); in tnc_delete()
2517 err = ubifs_add_dirt(c, zbr->lnum, zbr->len); in tnc_delete()
2519 ubifs_dump_znode(c, znode); in tnc_delete()
2537 ubifs_assert(c, !ubifs_zn_obsolete(znode)); in tnc_delete()
2538 ubifs_assert(c, ubifs_zn_dirty(znode)); in tnc_delete()
2543 atomic_long_dec(&c->dirty_zn_cnt); in tnc_delete()
2545 err = insert_old_idx_znode(c, znode); in tnc_delete()
2551 atomic_long_inc(&c->clean_zn_cnt); in tnc_delete()
2560 ubifs_assert(c, znode->level != 0); in tnc_delete()
2575 znode = get_znode(c, znode, 0); in tnc_delete()
2578 znode = dirty_cow_znode(c, zbr); in tnc_delete()
2583 if (c->zroot.len) { in tnc_delete()
2584 err = insert_old_idx(c, c->zroot.lnum, in tnc_delete()
2585 c->zroot.offs); in tnc_delete()
2589 c->zroot.lnum = zbr->lnum; in tnc_delete()
2590 c->zroot.offs = zbr->offs; in tnc_delete()
2591 c->zroot.len = zbr->len; in tnc_delete()
2592 c->zroot.znode = znode; in tnc_delete()
2593 ubifs_assert(c, !ubifs_zn_obsolete(zp)); in tnc_delete()
2594 ubifs_assert(c, ubifs_zn_dirty(zp)); in tnc_delete()
2595 atomic_long_dec(&c->dirty_zn_cnt); in tnc_delete()
2599 atomic_long_inc(&c->clean_zn_cnt); in tnc_delete()
2616 int ubifs_tnc_remove(struct ubifs_info *c, const union ubifs_key *key) in ubifs_tnc_remove() argument
2621 mutex_lock(&c->tnc_mutex); in ubifs_tnc_remove()
2623 found = lookup_level0_dirty(c, key, &znode, &n); in ubifs_tnc_remove()
2629 err = tnc_delete(c, znode, n); in ubifs_tnc_remove()
2631 err = dbg_check_tnc(c, 0); in ubifs_tnc_remove()
2634 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_remove()
2646 int ubifs_tnc_remove_nm(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_remove_nm() argument
2652 mutex_lock(&c->tnc_mutex); in ubifs_tnc_remove_nm()
2654 err = lookup_level0_dirty(c, key, &znode, &n); in ubifs_tnc_remove_nm()
2659 if (c->replaying) in ubifs_tnc_remove_nm()
2660 err = fallible_resolve_collision(c, key, &znode, &n, in ubifs_tnc_remove_nm()
2663 err = resolve_collision(c, key, &znode, &n, nm); in ubifs_tnc_remove_nm()
2670 znode = dirty_cow_bottom_up(c, znode); in ubifs_tnc_remove_nm()
2676 err = tnc_delete(c, znode, n); in ubifs_tnc_remove_nm()
2682 err = dbg_check_tnc(c, 0); in ubifs_tnc_remove_nm()
2683 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_remove_nm()
2695 int ubifs_tnc_remove_dh(struct ubifs_info *c, const union ubifs_key *key, in ubifs_tnc_remove_dh() argument
2703 if (!c->double_hash) in ubifs_tnc_remove_dh()
2706 mutex_lock(&c->tnc_mutex); in ubifs_tnc_remove_dh()
2707 err = lookup_level0_dirty(c, key, &znode, &n); in ubifs_tnc_remove_dh()
2718 err = tnc_read_hashed_node(c, zbr, dent); in ubifs_tnc_remove_dh()
2726 lowest_dent_key(c, &start_key, key_inum(c, key)); in ubifs_tnc_remove_dh()
2728 err = ubifs_lookup_level0(c, &start_key, &znode, &n); in ubifs_tnc_remove_dh()
2732 err = search_dh_cookie(c, key, dent, cookie, &znode, &n, err); in ubifs_tnc_remove_dh()
2738 znode = dirty_cow_bottom_up(c, znode); in ubifs_tnc_remove_dh()
2744 err = tnc_delete(c, znode, n); in ubifs_tnc_remove_dh()
2750 err = dbg_check_tnc(c, 0); in ubifs_tnc_remove_dh()
2751 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_remove_dh()
2764 static int key_in_range(struct ubifs_info *c, union ubifs_key *key, in key_in_range() argument
2767 if (keys_cmp(c, key, from_key) < 0) in key_in_range()
2769 if (keys_cmp(c, key, to_key) > 0) in key_in_range()
2784 int ubifs_tnc_remove_range(struct ubifs_info *c, union ubifs_key *from_key, in ubifs_tnc_remove_range() argument
2791 mutex_lock(&c->tnc_mutex); in ubifs_tnc_remove_range()
2794 err = ubifs_lookup_level0(c, from_key, &znode, &n); in ubifs_tnc_remove_range()
2801 err = tnc_next(c, &znode, &n); in ubifs_tnc_remove_range()
2809 if (!key_in_range(c, key, from_key, to_key)) { in ubifs_tnc_remove_range()
2817 znode = dirty_cow_bottom_up(c, znode); in ubifs_tnc_remove_range()
2827 if (!key_in_range(c, key, from_key, to_key)) in ubifs_tnc_remove_range()
2830 err = ubifs_add_dirt(c, znode->zbranch[i].lnum, in ubifs_tnc_remove_range()
2833 ubifs_dump_znode(c, znode); in ubifs_tnc_remove_range()
2845 err = tnc_delete(c, znode, n); in ubifs_tnc_remove_range()
2852 err = dbg_check_tnc(c, 0); in ubifs_tnc_remove_range()
2853 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_remove_range()
2866 int ubifs_tnc_remove_ino(struct ubifs_info *c, ino_t inum) in ubifs_tnc_remove_ino() argument
2878 lowest_xent_key(c, &key1, inum); in ubifs_tnc_remove_ino()
2883 xent = ubifs_tnc_next_ent(c, &key1, &nm); in ubifs_tnc_remove_ino()
2895 ubifs_evict_xattr_inode(c, xattr_inum); in ubifs_tnc_remove_ino()
2899 err = ubifs_tnc_remove_nm(c, &key1, &nm); in ubifs_tnc_remove_ino()
2905 lowest_ino_key(c, &key1, xattr_inum); in ubifs_tnc_remove_ino()
2906 highest_ino_key(c, &key2, xattr_inum); in ubifs_tnc_remove_ino()
2907 err = ubifs_tnc_remove_range(c, &key1, &key2); in ubifs_tnc_remove_ino()
2915 key_read(c, &xent->key, &key1); in ubifs_tnc_remove_ino()
2919 lowest_ino_key(c, &key1, inum); in ubifs_tnc_remove_ino()
2920 highest_ino_key(c, &key2, inum); in ubifs_tnc_remove_ino()
2922 return ubifs_tnc_remove_range(c, &key1, &key2); in ubifs_tnc_remove_ino()
2948 struct ubifs_dent_node *ubifs_tnc_next_ent(struct ubifs_info *c, in ubifs_tnc_next_ent() argument
2952 int n, err, type = key_type(c, key); in ubifs_tnc_next_ent()
2959 ubifs_assert(c, is_hash_key(c, key)); in ubifs_tnc_next_ent()
2961 mutex_lock(&c->tnc_mutex); in ubifs_tnc_next_ent()
2962 err = ubifs_lookup_level0(c, key, &znode, &n); in ubifs_tnc_next_ent()
2969 if (c->replaying) in ubifs_tnc_next_ent()
2970 err = fallible_resolve_collision(c, key, &znode, &n, in ubifs_tnc_next_ent()
2973 err = resolve_collision(c, key, &znode, &n, nm); in ubifs_tnc_next_ent()
2981 err = tnc_next(c, &znode, &n); in ubifs_tnc_next_ent()
2996 err = tnc_next(c, &znode, &n); in ubifs_tnc_next_ent()
3014 if (key_inum(c, dkey) != key_inum(c, key) || in ubifs_tnc_next_ent()
3015 key_type(c, dkey) != type) { in ubifs_tnc_next_ent()
3020 err = tnc_read_hashed_node(c, zbr, dent); in ubifs_tnc_next_ent()
3024 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_next_ent()
3030 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_next_ent()
3040 static void tnc_destroy_cnext(struct ubifs_info *c) in tnc_destroy_cnext() argument
3044 if (!c->cnext) in tnc_destroy_cnext()
3046 ubifs_assert(c, c->cmt_state == COMMIT_BROKEN); in tnc_destroy_cnext()
3047 cnext = c->cnext; in tnc_destroy_cnext()
3054 } while (cnext && cnext != c->cnext); in tnc_destroy_cnext()
3061 void ubifs_tnc_close(struct ubifs_info *c) in ubifs_tnc_close() argument
3063 tnc_destroy_cnext(c); in ubifs_tnc_close()
3064 if (c->zroot.znode) { in ubifs_tnc_close()
3067 n = atomic_long_read(&c->clean_zn_cnt); in ubifs_tnc_close()
3068 freed = ubifs_destroy_tnc_subtree(c, c->zroot.znode); in ubifs_tnc_close()
3069 ubifs_assert(c, freed == n); in ubifs_tnc_close()
3072 kfree(c->gap_lebs); in ubifs_tnc_close()
3073 kfree(c->ilebs); in ubifs_tnc_close()
3074 destroy_old_idx(c); in ubifs_tnc_close()
3085 static struct ubifs_znode *left_znode(struct ubifs_info *c, in left_znode() argument
3099 znode = get_znode(c, znode, n); in left_znode()
3104 znode = get_znode(c, znode, n); in left_znode()
3122 static struct ubifs_znode *right_znode(struct ubifs_info *c, in right_znode() argument
3136 znode = get_znode(c, znode, n); in right_znode()
3140 znode = get_znode(c, znode, 0); in right_znode()
3175 static struct ubifs_znode *lookup_znode(struct ubifs_info *c, in lookup_znode() argument
3182 ubifs_assert(c, key_type(c, key) < UBIFS_INVALID_KEY); in lookup_znode()
3192 znode = c->zroot.znode; in lookup_znode()
3194 znode = ubifs_load_znode(c, &c->zroot, NULL, 0); in lookup_znode()
3199 if (c->zroot.lnum == lnum && c->zroot.offs == offs) in lookup_znode()
3205 ubifs_search_zbranch(c, znode, key, &n); in lookup_znode()
3215 znode = left_znode(c, znode); in lookup_znode()
3220 ubifs_search_zbranch(c, znode, key, &n); in lookup_znode()
3221 ubifs_assert(c, n >= 0); in lookup_znode()
3225 znode = get_znode(c, znode, n); in lookup_znode()
3231 return get_znode(c, znode, n); in lookup_znode()
3233 if (!is_hash_key(c, key)) in lookup_znode()
3247 znode = left_znode(c, znode); in lookup_znode()
3257 return get_znode(c, znode, n); in lookup_znode()
3259 if (keys_cmp(c, &znode->zbranch[n].key, key) < 0) in lookup_znode()
3269 znode = right_znode(c, znode); in lookup_znode()
3279 return get_znode(c, znode, n); in lookup_znode()
3281 if (keys_cmp(c, &znode->zbranch[n].key, key) > 0) in lookup_znode()
3304 int is_idx_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, int level, in is_idx_node_in_tnc() argument
3309 znode = lookup_znode(c, key, level, lnum, offs); in is_idx_node_in_tnc()
3331 static int is_leaf_node_in_tnc(struct ubifs_info *c, union ubifs_key *key, in is_leaf_node_in_tnc() argument
3337 const int unique = !is_hash_key(c, key); in is_leaf_node_in_tnc()
3339 found = ubifs_lookup_level0(c, key, &znode, &n); in is_leaf_node_in_tnc()
3357 err = tnc_prev(c, &znode, &n); in is_leaf_node_in_tnc()
3362 if (keys_cmp(c, key, &znode->zbranch[n].key)) in is_leaf_node_in_tnc()
3372 err = tnc_next(c, &znode, &n); in is_leaf_node_in_tnc()
3378 if (keys_cmp(c, key, &znode->zbranch[n].key)) in is_leaf_node_in_tnc()
3401 int ubifs_tnc_has_node(struct ubifs_info *c, union ubifs_key *key, int level, in ubifs_tnc_has_node() argument
3406 mutex_lock(&c->tnc_mutex); in ubifs_tnc_has_node()
3408 err = is_idx_node_in_tnc(c, key, level, lnum, offs); in ubifs_tnc_has_node()
3420 err = is_leaf_node_in_tnc(c, key, lnum, offs); in ubifs_tnc_has_node()
3423 mutex_unlock(&c->tnc_mutex); in ubifs_tnc_has_node()
3441 int ubifs_dirty_idx_node(struct ubifs_info *c, union ubifs_key *key, int level, in ubifs_dirty_idx_node() argument
3447 mutex_lock(&c->tnc_mutex); in ubifs_dirty_idx_node()
3448 znode = lookup_znode(c, key, level, lnum, offs); in ubifs_dirty_idx_node()
3455 znode = dirty_cow_bottom_up(c, znode); in ubifs_dirty_idx_node()
3462 mutex_unlock(&c->tnc_mutex); in ubifs_dirty_idx_node()
3477 int dbg_check_inode_size(struct ubifs_info *c, const struct inode *inode, in dbg_check_inode_size() argument
3487 if (!dbg_is_chk_gen(c)) in dbg_check_inode_size()
3491 data_key_init(c, &from_key, inode->i_ino, block); in dbg_check_inode_size()
3492 highest_data_key(c, &to_key, inode->i_ino); in dbg_check_inode_size()
3494 mutex_lock(&c->tnc_mutex); in dbg_check_inode_size()
3495 err = ubifs_lookup_level0(c, &from_key, &znode, &n); in dbg_check_inode_size()
3504 err = tnc_next(c, &znode, &n); in dbg_check_inode_size()
3512 ubifs_assert(c, err == 0); in dbg_check_inode_size()
3514 if (!key_in_range(c, key, &from_key, &to_key)) in dbg_check_inode_size()
3518 block = key_block(c, key); in dbg_check_inode_size()
3519 ubifs_err(c, "inode %lu has size %lld, but there are data at offset %lld", in dbg_check_inode_size()
3522 mutex_unlock(&c->tnc_mutex); in dbg_check_inode_size()
3523 ubifs_dump_inode(c, inode); in dbg_check_inode_size()
3528 mutex_unlock(&c->tnc_mutex); in dbg_check_inode_size()