| H A D | tnc.c | 29 * tree. If a znode is not in memory, we read it from flash while still having
112 * insert_old_idx_znode - record a znode obsoleted since last commit start.
114 * @znode: znode of obsoleted index node
118 int insert_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) insert_old_idx_znode() argument
120 if (znode->parent) { insert_old_idx_znode()
123 zbr = &znode->parent->zbranch[znode->iip]; insert_old_idx_znode()
134 * ins_clr_old_idx_znode - record a znode obsoleted since last commit start.
136 * @znode: znode of obsoleted index node
141 struct ubifs_znode *znode) ins_clr_old_idx_znode()
145 if (znode->parent) { ins_clr_old_idx_znode()
148 zbr = &znode->parent->zbranch[znode->iip]; ins_clr_old_idx_znode()
190 * copy_znode - copy a dirty znode.
192 * @znode: znode to copy
194 * A dirty znode being committed may not be changed, so it is copied.
197 struct ubifs_znode *znode) copy_znode()
201 zn = kmemdup(znode, c->max_znode_sz, GFP_NOFS); copy_znode()
209 ubifs_assert(!ubifs_zn_obsolete(znode)); copy_znode()
210 __set_bit(OBSOLETE_ZNODE, &znode->flags); copy_znode()
212 if (znode->level != 0) { copy_znode()
220 if (zbr->znode) copy_znode()
221 zbr->znode->parent = zn; copy_znode()
230 * add_idx_dirt - add dirt due to a dirty znode.
244 * dirty_cow_znode - ensure a znode is not being committed.
246 * @zbr: branch of znode to check
248 * Returns dirtied znode on success or negative error code on failure.
253 struct ubifs_znode *znode = zbr->znode; dirty_cow_znode() local
257 if (!ubifs_zn_cow(znode)) { dirty_cow_znode()
258 /* znode is not being committed */ dirty_cow_znode()
259 if (!test_and_set_bit(DIRTY_ZNODE, &znode->flags)) { dirty_cow_znode()
267 return znode; dirty_cow_znode()
270 zn = copy_znode(c, znode); dirty_cow_znode()
282 zbr->znode = zn; dirty_cow_znode()
564 * get_znode - get a TNC znode that may not be loaded yet.
566 * @znode: parent znode
567 * @n: znode branch slot number
569 * This function returns the znode or a negative error code.
572 struct ubifs_znode *znode, int n) get_znode()
576 zbr = &znode->zbranch[n]; get_znode()
577 if (zbr->znode) get_znode()
578 znode = zbr->znode; get_znode()
580 znode = ubifs_load_znode(c, zbr, znode, n); get_znode()
581 return znode; get_znode()
587 * @zn: znode is passed and returned here
588 * @n: znode branch slot number is passed and returned here
595 struct ubifs_znode *znode = *zn; tnc_next() local
599 if (nn < znode->child_cnt) { tnc_next()
606 zp = znode->parent; tnc_next()
609 nn = znode->iip + 1; tnc_next()
610 znode = zp; tnc_next()
611 if (nn < znode->child_cnt) { tnc_next()
612 znode = get_znode(c, znode, nn); tnc_next()
613 if (IS_ERR(znode)) tnc_next()
614 return PTR_ERR(znode); tnc_next()
615 while (znode->level != 0) { tnc_next()
616 znode = get_znode(c, znode, 0); tnc_next()
617 if (IS_ERR(znode)) tnc_next()
618 return PTR_ERR(znode); tnc_next()
624 *zn = znode; tnc_next()
632 * @zn: znode is returned here
633 * @n: znode branch slot number is passed and returned here
640 struct ubifs_znode *znode = *zn; tnc_prev() local
650 zp = znode->parent; tnc_prev()
653 nn = znode->iip - 1; tnc_prev()
654 znode = zp; tnc_prev()
656 znode = get_znode(c, znode, nn); tnc_prev()
657 if (IS_ERR(znode)) tnc_prev()
658 return PTR_ERR(znode); tnc_prev()
659 while (znode->level != 0) { tnc_prev()
660 nn = znode->child_cnt - 1; tnc_prev()
661 znode = get_znode(c, znode, nn); tnc_prev()
662 if (IS_ERR(znode)) tnc_prev()
663 return PTR_ERR(znode); tnc_prev()
665 nn = znode->child_cnt - 1; tnc_prev()
669 *zn = znode; tnc_prev()
678 * @zn: znode is returned here
716 * like to insert, but inserting in this znode resolve_collision()
721 * znode zp resolve_collision()
726 * znode za | | znode zb resolve_collision()
731 * The lookup finds Key2 in znode zb. Lets say resolve_collision()
735 * znode za at slot n = 1. But that is invalid resolve_collision()
737 * be inserted into znode zb. resolve_collision()
768 struct ubifs_znode *znode = *zn; resolve_collision() local
772 err = tnc_next(c, &znode, &nn); resolve_collision()
777 if (keys_cmp(c, &znode->zbranch[nn].key, key)) resolve_collision()
779 err = matches_name(c, &znode->zbranch[nn], nm); resolve_collision()
784 *zn = znode; resolve_collision()
860 * @zn: znode is returned here
883 struct ubifs_znode *o_znode = NULL, *znode = *zn; fallible_resolve_collision() local
886 cmp = fallible_matches_name(c, &znode->zbranch[nn], nm); fallible_resolve_collision()
892 o_znode = znode; fallible_resolve_collision()
951 *zn = znode; fallible_resolve_collision()
954 err = tnc_next(c, &znode, &nn); fallible_resolve_collision()
959 if (keys_cmp(c, &znode->zbranch[nn].key, key)) fallible_resolve_collision()
961 err = fallible_matches_name(c, &znode->zbranch[nn], nm); fallible_resolve_collision()
966 *zn = znode; fallible_resolve_collision()
971 o_znode = znode; fallible_resolve_collision()
1009 * @zn: znode is passed and returned here
1027 struct ubifs_znode *znode; resolve_collision_directly() local
1030 znode = *zn; resolve_collision_directly()
1032 if (matches_position(&znode->zbranch[nn], lnum, offs)) resolve_collision_directly()
1037 err = tnc_prev(c, &znode, &nn); resolve_collision_directly()
1042 if (keys_cmp(c, &znode->zbranch[nn].key, key)) resolve_collision_directly()
1044 if (matches_position(&znode->zbranch[nn], lnum, offs)) { resolve_collision_directly()
1045 *zn = znode; resolve_collision_directly()
1052 znode = *zn; resolve_collision_directly()
1055 err = tnc_next(c, &znode, &nn); resolve_collision_directly()
1060 if (keys_cmp(c, &znode->zbranch[nn].key, key)) resolve_collision_directly()
1062 *zn = znode; resolve_collision_directly()
1064 if (matches_position(&znode->zbranch[nn], lnum, offs)) resolve_collision_directly()
1070 * dirty_cow_bottom_up - dirty a znode and its ancestors.
1072 * @znode: znode to dirty
1074 * If we do not have a unique key that resides in a znode, then we cannot
1075 * dirty that znode from the top down (i.e. by using lookup_level0_dirty)
1080 struct ubifs_znode *znode) dirty_cow_bottom_up()
1085 ubifs_assert(c->zroot.znode); dirty_cow_bottom_up()
1086 ubifs_assert(znode); dirty_cow_bottom_up()
1087 if (c->zroot.znode->level > BOTTOM_UP_HEIGHT) { dirty_cow_bottom_up()
1089 c->bottom_up_buf = kmalloc(c->zroot.znode->level * sizeof(int), dirty_cow_bottom_up()
1095 if (c->zroot.znode->level) { dirty_cow_bottom_up()
1100 zp = znode->parent; dirty_cow_bottom_up()
1103 n = znode->iip; dirty_cow_bottom_up()
1104 ubifs_assert(p < c->zroot.znode->level); dirty_cow_bottom_up()
1106 if (!zp->cnext && ubifs_zn_dirty(znode)) dirty_cow_bottom_up()
1108 znode = zp; dirty_cow_bottom_up()
1116 zp = znode->parent; dirty_cow_bottom_up()
1121 znode = dirty_cow_znode(c, zbr); dirty_cow_bottom_up()
1123 ubifs_assert(znode == c->zroot.znode); dirty_cow_bottom_up()
1124 znode = dirty_cow_znode(c, &c->zroot); dirty_cow_bottom_up()
1126 if (IS_ERR(znode) || !p) dirty_cow_bottom_up()
1129 ubifs_assert(path[p - 1] < znode->child_cnt); dirty_cow_bottom_up()
1130 znode = znode->zbranch[path[p - 1]].znode; dirty_cow_bottom_up()
1133 return znode; dirty_cow_bottom_up()
1137 * ubifs_lookup_level0 - search for zero-level znode.
1140 * @zn: znode is returned here
1141 * @n: znode branch slot number is returned here
1143 * This function looks up the TNC tree and search for zero-level znode which
1144 * refers key @key. The found zero-level znode is returned in @zn. There are 3
1146 * o exact match, i.e. the found zero-level znode contains key @key, then %1
1148 * o not exact match, which means that zero-level znode does not contain
1162 struct ubifs_znode *znode; ubifs_lookup_level0() local
1168 znode = c->zroot.znode; ubifs_lookup_level0()
1169 if (unlikely(!znode)) { ubifs_lookup_level0()
1170 znode = ubifs_load_znode(c, &c->zroot, NULL, 0); ubifs_lookup_level0()
1171 if (IS_ERR(znode)) ubifs_lookup_level0()
1172 return PTR_ERR(znode); ubifs_lookup_level0()
1175 znode->time = time; ubifs_lookup_level0()
1180 exact = ubifs_search_zbranch(c, znode, key, n); ubifs_lookup_level0()
1182 if (znode->level == 0) ubifs_lookup_level0()
1187 zbr = &znode->zbranch[*n]; ubifs_lookup_level0()
1189 if (zbr->znode) { ubifs_lookup_level0()
1190 znode->time = time; ubifs_lookup_level0()
1191 znode = zbr->znode; ubifs_lookup_level0()
1195 /* znode is not in TNC cache, load it from the media */ ubifs_lookup_level0()
1196 znode = ubifs_load_znode(c, zbr, znode, *n); ubifs_lookup_level0()
1197 if (IS_ERR(znode)) ubifs_lookup_level0()
1198 return PTR_ERR(znode); ubifs_lookup_level0()
1201 *zn = znode; ubifs_lookup_level0()
1203 dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n); ubifs_lookup_level0()
1231 * children of current znode. For example, this happens if we split a ubifs_lookup_level0()
1232 * znode like this: | 3 | 5 | 5 | 6 | 7 |, which results in something ubifs_lookup_level0()
1243 * if we changed the leftmost key of the parent znode, the garbage ubifs_lookup_level0()
1250 err = tnc_prev(c, &znode, n); ubifs_lookup_level0()
1252 dbg_tnc("found 0, lvl %d, n -1", znode->level); ubifs_lookup_level0()
1258 if (keys_cmp(c, key, &znode->zbranch[*n].key)) { ubifs_lookup_level0()
1259 dbg_tnc("found 0, lvl %d, n -1", znode->level); ubifs_lookup_level0()
1264 dbg_tnc("found 1, lvl %d, n %d", znode->level, *n); ubifs_lookup_level0()
1265 *zn = znode; ubifs_lookup_level0()
1270 * lookup_level0_dirty - search for zero-level znode dirtying.
1273 * @zn: znode is returned here
1274 * @n: znode branch slot number is returned here
1276 * This function looks up the TNC tree and search for zero-level znode which
1277 * refers key @key. The found zero-level znode is returned in @zn. There are 3
1279 * o exact match, i.e. the found zero-level znode contains key @key, then %1
1281 * o not exact match, which means that zero-level znode does not contain @key
1288 * znode are marked as dirty.
1298 struct ubifs_znode *znode; lookup_level0_dirty() local
1303 znode = c->zroot.znode; lookup_level0_dirty()
1304 if (unlikely(!znode)) { lookup_level0_dirty()
1305 znode = ubifs_load_znode(c, &c->zroot, NULL, 0); lookup_level0_dirty()
1306 if (IS_ERR(znode)) lookup_level0_dirty()
1307 return PTR_ERR(znode); lookup_level0_dirty()
1310 znode = dirty_cow_znode(c, &c->zroot); lookup_level0_dirty()
1311 if (IS_ERR(znode)) lookup_level0_dirty()
1312 return PTR_ERR(znode); lookup_level0_dirty()
1314 znode->time = time; lookup_level0_dirty()
1319 exact = ubifs_search_zbranch(c, znode, key, n); lookup_level0_dirty()
1321 if (znode->level == 0) lookup_level0_dirty()
1326 zbr = &znode->zbranch[*n]; lookup_level0_dirty()
1328 if (zbr->znode) { lookup_level0_dirty()
1329 znode->time = time; lookup_level0_dirty()
1330 znode = dirty_cow_znode(c, zbr); lookup_level0_dirty()
1331 if (IS_ERR(znode)) lookup_level0_dirty()
1332 return PTR_ERR(znode); lookup_level0_dirty()
1336 /* znode is not in TNC cache, load it from the media */ lookup_level0_dirty()
1337 znode = ubifs_load_znode(c, zbr, znode, *n); lookup_level0_dirty()
1338 if (IS_ERR(znode)) lookup_level0_dirty()
1339 return PTR_ERR(znode); lookup_level0_dirty()
1340 znode = dirty_cow_znode(c, zbr); lookup_level0_dirty()
1341 if (IS_ERR(znode)) lookup_level0_dirty()
1342 return PTR_ERR(znode); lookup_level0_dirty()
1345 *zn = znode; lookup_level0_dirty()
1347 dbg_tnc("found %d, lvl %d, n %d", exact, znode->level, *n); lookup_level0_dirty()
1355 err = tnc_prev(c, &znode, n); lookup_level0_dirty()
1358 dbg_tnc("found 0, lvl %d, n -1", znode->level); lookup_level0_dirty()
1363 if (keys_cmp(c, key, &znode->zbranch[*n].key)) { lookup_level0_dirty()
1365 dbg_tnc("found 0, lvl %d, n -1", znode->level); lookup_level0_dirty()
1369 if (znode->cnext || !ubifs_zn_dirty(znode)) { lookup_level0_dirty()
1370 znode = dirty_cow_bottom_up(c, znode); lookup_level0_dirty()
1371 if (IS_ERR(znode)) lookup_level0_dirty()
1372 return PTR_ERR(znode); lookup_level0_dirty()
1375 dbg_tnc("found 1, lvl %d, n %d", znode->level, *n); lookup_level0_dirty()
1376 *zn = znode; lookup_level0_dirty()
1433 struct ubifs_znode *znode; ubifs_tnc_locate() local
1438 found = ubifs_lookup_level0(c, key, &znode, &n); ubifs_tnc_locate()
1446 zt = &znode->zbranch[n]; ubifs_tnc_locate()
1464 zbr = znode->zbranch[n]; ubifs_tnc_locate()
1508 struct ubifs_znode *znode; ubifs_tnc_get_bu_keys() local
1516 err = ubifs_lookup_level0(c, &bu->key, &znode, &n); ubifs_tnc_get_bu_keys()
1521 len = znode->zbranch[n].len; ubifs_tnc_get_bu_keys()
1528 bu->zbranch[bu->cnt++] = znode->zbranch[n]; ubifs_tnc_get_bu_keys()
1530 lnum = znode->zbranch[n].lnum; ubifs_tnc_get_bu_keys()
1531 offs = ALIGN(znode->zbranch[n].offs + len, 8); ubifs_tnc_get_bu_keys()
1539 err = tnc_next(c, &znode, &n); ubifs_tnc_get_bu_keys()
1542 zbr = &znode->zbranch[n]; ubifs_tnc_get_bu_keys()
1795 struct ubifs_znode *znode; do_lookup_nm() local
1799 found = ubifs_lookup_level0(c, key, &znode, &n); do_lookup_nm()
1810 err = resolve_collision(c, key, &znode, &n, nm); do_lookup_nm()
1811 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n); do_lookup_nm()
1819 err = tnc_read_node_nm(c, &znode->zbranch[n], node); do_lookup_nm()
1867 * @znode: znode to correct parent znodes for
1874 struct ubifs_znode *znode) correct_parent_keys()
1878 ubifs_assert(znode->parent); correct_parent_keys()
1879 ubifs_assert(znode->iip == 0); correct_parent_keys()
1881 key = &znode->zbranch[0].key; correct_parent_keys()
1882 key1 = &znode->parent->zbranch[0].key; correct_parent_keys()
1886 znode = znode->parent; correct_parent_keys()
1887 znode->alt = 1; correct_parent_keys()
1888 if (!znode->parent || znode->iip) correct_parent_keys()
1890 key1 = &znode->parent->zbranch[0].key; correct_parent_keys()
1895 * insert_zbranch - insert a zbranch into a znode.
1896 * @znode: znode into which to insert
1901 * znode's array of zbranches and keeps zbranches consolidated, so when a new
1902 * zbranch has to be inserted to the @znode->zbranches[]' array at the @n-th
1905 static void insert_zbranch(struct ubifs_znode *znode, insert_zbranch() argument
1910 ubifs_assert(ubifs_zn_dirty(znode)); insert_zbranch()
1912 if (znode->level) { insert_zbranch()
1913 for (i = znode->child_cnt; i > n; i--) { insert_zbranch()
1914 znode->zbranch[i] = znode->zbranch[i - 1]; insert_zbranch()
1915 if (znode->zbranch[i].znode) insert_zbranch()
1916 znode->zbranch[i].znode->iip = i; insert_zbranch()
1918 if (zbr->znode) insert_zbranch()
1919 zbr->znode->iip = n; insert_zbranch()
1921 for (i = znode->child_cnt; i > n; i--) insert_zbranch()
1922 znode->zbranch[i] = znode->zbranch[i - 1]; insert_zbranch()
1924 znode->zbranch[n] = *zbr; insert_zbranch()
1925 znode->child_cnt += 1; insert_zbranch()
1929 * this znode may have changed. If this znode is subsequently split insert_zbranch()
1932 * happens, then it will no longer be possible to find this znode in the insert_zbranch()
1942 znode->alt = 1; insert_zbranch()
1948 * @znode: znode to insert into
1952 * This function inserts a new node described by @zbr into znode @znode. If
1953 * znode does not have a free slot for new zbranch, it is split. Parent znodes
1957 static int tnc_insert(struct ubifs_info *c, struct ubifs_znode *znode, tnc_insert() argument
1968 zp = znode->parent; tnc_insert()
1969 if (znode->child_cnt < c->fanout) { tnc_insert()
1971 dbg_tnck(key, "inserted at %d level %d, key ", n, znode->level); tnc_insert()
1973 insert_zbranch(znode, zbr, n); tnc_insert()
1976 if (n == 0 && zp && znode->iip == 0) tnc_insert()
1977 correct_parent_keys(c, znode); tnc_insert()
1983 * Unfortunately, @znode does not have more empty slots and we have to tnc_insert()
1986 dbg_tnck(key, "splitting level %d, key ", znode->level); tnc_insert()
1988 if (znode->alt) tnc_insert()
1990 * We can no longer be sure of finding this znode by key, so we tnc_insert()
1993 ins_clr_old_idx_znode(c, znode); tnc_insert()
1999 zn->level = znode->level; tnc_insert()
2002 if (znode->level == 0 && key_type(c, key) == UBIFS_DATA_KEY) { tnc_insert()
2005 key1 = &znode->zbranch[n - 1].key; tnc_insert()
2016 key1 = &znode->zbranch[0].key; tnc_insert()
2019 key1 = &znode->zbranch[n].key; tnc_insert()
2024 zi = znode; tnc_insert()
2045 /* Insert into existing znode */ tnc_insert()
2046 zi = znode; tnc_insert()
2050 /* Insert into new znode */ tnc_insert()
2055 zbr->znode->parent = zn; tnc_insert()
2064 znode->child_cnt = keep; tnc_insert()
2070 zn->zbranch[i] = znode->zbranch[keep + i]; tnc_insert()
2073 if (zn->zbranch[i].znode) { tnc_insert()
2074 zn->zbranch[i].znode->parent = zn; tnc_insert()
2075 zn->zbranch[i].znode->iip = i; tnc_insert()
2084 /* Insert new znode (produced by spitting) into the parent */ tnc_insert()
2086 if (n == 0 && zi == znode && znode->iip == 0) tnc_insert()
2087 correct_parent_keys(c, znode); tnc_insert()
2090 n = znode->iip + 1; tnc_insert()
2094 zbr->znode = zn; tnc_insert()
2098 znode = zp; tnc_insert()
2103 /* We have to split root znode */ tnc_insert()
2104 dbg_tnc("creating new zroot at level %d", znode->level + 1); tnc_insert()
2111 zi->level = znode->level + 1; tnc_insert()
2116 zi->zbranch[0].key = znode->zbranch[0].key; tnc_insert()
2117 zi->zbranch[0].znode = znode; tnc_insert()
2122 zi->zbranch[1].znode = zn; tnc_insert()
2127 c->zroot.znode = zi; tnc_insert()
2131 znode->parent = zi; tnc_insert()
2132 znode->iip = 0; tnc_insert()
2153 struct ubifs_znode *znode; ubifs_tnc_add() local
2157 found = lookup_level0_dirty(c, key, &znode, &n); ubifs_tnc_add()
2161 zbr.znode = NULL; ubifs_tnc_add()
2166 err = tnc_insert(c, znode, &zbr, n + 1); ubifs_tnc_add()
2168 struct ubifs_zbranch *zbr = &znode->zbranch[n]; ubifs_tnc_add()
2202 struct ubifs_znode *znode; ubifs_tnc_replace() local
2207 found = lookup_level0_dirty(c, key, &znode, &n); ubifs_tnc_replace()
2214 struct ubifs_zbranch *zbr = &znode->zbranch[n]; ubifs_tnc_replace()
2227 found = resolve_collision_directly(c, key, &znode, &n, ubifs_tnc_replace()
2229 dbg_tnc("rc returned %d, znode %p, n %d, LEB %d:%d", ubifs_tnc_replace()
2230 found, znode, n, old_lnum, old_offs); ubifs_tnc_replace()
2237 /* Ensure the znode is dirtied */ ubifs_tnc_replace()
2238 if (znode->cnext || !ubifs_zn_dirty(znode)) { ubifs_tnc_replace()
2239 znode = dirty_cow_bottom_up(c, znode); ubifs_tnc_replace()
2240 if (IS_ERR(znode)) { ubifs_tnc_replace()
2241 err = PTR_ERR(znode); ubifs_tnc_replace()
2245 zbr = &znode->zbranch[n]; ubifs_tnc_replace()
2285 struct ubifs_znode *znode; ubifs_tnc_add_nm() local
2290 found = lookup_level0_dirty(c, key, &znode, &n); ubifs_tnc_add_nm()
2298 found = fallible_resolve_collision(c, key, &znode, &n, ubifs_tnc_add_nm()
2301 found = resolve_collision(c, key, &znode, &n, nm); ubifs_tnc_add_nm()
2302 dbg_tnc("rc returned %d, znode %p, n %d", found, znode, n); ubifs_tnc_add_nm()
2308 /* Ensure the znode is dirtied */ ubifs_tnc_add_nm()
2309 if (znode->cnext || !ubifs_zn_dirty(znode)) { ubifs_tnc_add_nm()
2310 znode = dirty_cow_bottom_up(c, znode); ubifs_tnc_add_nm()
2311 if (IS_ERR(znode)) { ubifs_tnc_add_nm()
2312 err = PTR_ERR(znode); ubifs_tnc_add_nm()
2318 struct ubifs_zbranch *zbr = &znode->zbranch[n]; ubifs_tnc_add_nm()
2332 zbr.znode = NULL; ubifs_tnc_add_nm()
2337 err = tnc_insert(c, znode, &zbr, n + 1); ubifs_tnc_add_nm()
2365 * tnc_delete - delete a znode form TNC.
2367 * @znode: znode to delete from
2370 * This function deletes a leaf node from @n-th slot of @znode. Returns zero in
2373 static int tnc_delete(struct ubifs_info *c, struct ubifs_znode *znode, int n) tnc_delete() argument
2380 ubifs_assert(znode->level == 0); tnc_delete()
2382 dbg_tnck(&znode->zbranch[n].key, "deleting key "); tnc_delete()
2384 zbr = &znode->zbranch[n]; tnc_delete()
2389 ubifs_dump_znode(c, znode); tnc_delete()
2394 for (i = n; i < znode->child_cnt - 1; i++) tnc_delete()
2395 znode->zbranch[i] = znode->zbranch[i + 1]; tnc_delete()
2396 znode->child_cnt -= 1; tnc_delete()
2398 if (znode->child_cnt > 0) tnc_delete()
2402 * This was the last zbranch, we have to delete this znode from the tnc_delete()
2407 ubifs_assert(!ubifs_zn_obsolete(znode)); tnc_delete()
2408 ubifs_assert(ubifs_zn_dirty(znode)); tnc_delete()
2410 zp = znode->parent; tnc_delete()
2411 n = znode->iip; tnc_delete()
2415 err = insert_old_idx_znode(c, znode); tnc_delete()
2419 if (znode->cnext) { tnc_delete()
2420 __set_bit(OBSOLETE_ZNODE, &znode->flags); tnc_delete()
2424 kfree(znode); tnc_delete()
2425 znode = zp; tnc_delete()
2426 } while (znode->child_cnt == 1); /* while removing last child */ tnc_delete()
2428 /* Remove from znode, entry n - 1 */ tnc_delete()
2429 znode->child_cnt -= 1; tnc_delete()
2430 ubifs_assert(znode->level != 0); tnc_delete()
2431 for (i = n; i < znode->child_cnt; i++) { tnc_delete()
2432 znode->zbranch[i] = znode->zbranch[i + 1]; tnc_delete()
2433 if (znode->zbranch[i].znode) tnc_delete()
2434 znode->zbranch[i].znode->iip = i; tnc_delete()
2441 if (!znode->parent) { tnc_delete()
2442 while (znode->child_cnt == 1 && znode->level != 0) { tnc_delete()
2443 zp = znode; tnc_delete()
2444 zbr = &znode->zbranch[0]; tnc_delete()
2445 znode = get_znode(c, znode, 0); tnc_delete()
2446 if (IS_ERR(znode)) tnc_delete()
2447 return PTR_ERR(znode); tnc_delete()
2448 znode = dirty_cow_znode(c, zbr); tnc_delete()
2449 if (IS_ERR(znode)) tnc_delete()
2450 return PTR_ERR(znode); tnc_delete()
2451 znode->parent = NULL; tnc_delete()
2452 znode->iip = 0; tnc_delete()
2462 c->zroot.znode = znode; tnc_delete()
2489 struct ubifs_znode *znode; ubifs_tnc_remove() local
2493 found = lookup_level0_dirty(c, key, &znode, &n); ubifs_tnc_remove()
2499 err = tnc_delete(c, znode, n); ubifs_tnc_remove()
2520 struct ubifs_znode *znode; ubifs_tnc_remove_nm() local
2524 err = lookup_level0_dirty(c, key, &znode, &n); ubifs_tnc_remove_nm()
2530 err = fallible_resolve_collision(c, key, &znode, &n, ubifs_tnc_remove_nm()
2533 err = resolve_collision(c, key, &znode, &n, nm); ubifs_tnc_remove_nm()
2534 dbg_tnc("rc returned %d, znode %p, n %d", err, znode, n); ubifs_tnc_remove_nm()
2538 /* Ensure the znode is dirtied */ ubifs_tnc_remove_nm()
2539 if (znode->cnext || !ubifs_zn_dirty(znode)) { ubifs_tnc_remove_nm()
2540 znode = dirty_cow_bottom_up(c, znode); ubifs_tnc_remove_nm()
2541 if (IS_ERR(znode)) { ubifs_tnc_remove_nm()
2542 err = PTR_ERR(znode); ubifs_tnc_remove_nm()
2546 err = tnc_delete(c, znode, n); ubifs_tnc_remove_nm()
2590 struct ubifs_znode *znode; ubifs_tnc_remove_range() local
2595 /* Find first level 0 znode that contains keys to remove */ ubifs_tnc_remove_range()
2596 err = ubifs_lookup_level0(c, from_key, &znode, &n); ubifs_tnc_remove_range()
2603 err = tnc_next(c, &znode, &n); ubifs_tnc_remove_range()
2610 key = &znode->zbranch[n].key; ubifs_tnc_remove_range()
2617 /* Ensure the znode is dirtied */ ubifs_tnc_remove_range()
2618 if (znode->cnext || !ubifs_zn_dirty(znode)) { ubifs_tnc_remove_range()
2619 znode = dirty_cow_bottom_up(c, znode); ubifs_tnc_remove_range()
2620 if (IS_ERR(znode)) { ubifs_tnc_remove_range()
2621 err = PTR_ERR(znode); ubifs_tnc_remove_range()
2627 for (i = n + 1, k = 0; i < znode->child_cnt; i++, k++) { ubifs_tnc_remove_range()
2628 key = &znode->zbranch[i].key; ubifs_tnc_remove_range()
2631 lnc_free(&znode->zbranch[i]); ubifs_tnc_remove_range()
2632 err = ubifs_add_dirt(c, znode->zbranch[i].lnum, ubifs_tnc_remove_range()
2633 znode->zbranch[i].len); ubifs_tnc_remove_range()
2635 ubifs_dump_znode(c, znode); ubifs_tnc_remove_range()
2641 for (i = n + 1 + k; i < znode->child_cnt; i++) ubifs_tnc_remove_range()
2642 znode->zbranch[i - k] = znode->zbranch[i]; ubifs_tnc_remove_range()
2643 znode->child_cnt -= k; ubifs_tnc_remove_range()
2647 err = tnc_delete(c, znode, n); ubifs_tnc_remove_range()
2753 struct ubifs_znode *znode; ubifs_tnc_next_ent() local
2762 err = ubifs_lookup_level0(c, key, &znode, &n); ubifs_tnc_next_ent()
2769 err = resolve_collision(c, key, &znode, &n, nm); ubifs_tnc_next_ent()
2770 dbg_tnc("rc returned %d, znode %p, n %d", ubifs_tnc_next_ent()
2771 err, znode, n); ubifs_tnc_next_ent()
2777 err = tnc_next(c, &znode, &n); ubifs_tnc_next_ent()
2789 * tree and @znode/@n variables contain the closest ubifs_tnc_next_ent()
2792 err = tnc_next(c, &znode, &n); ubifs_tnc_next_ent()
2798 zbr = &znode->zbranch[n]; ubifs_tnc_next_ent()
2845 struct ubifs_znode *znode = cnext; tnc_destroy_cnext() local
2848 if (ubifs_zn_obsolete(znode)) tnc_destroy_cnext()
2849 kfree(znode); tnc_destroy_cnext()
2860 if (c->zroot.znode) { ubifs_tnc_close()
2864 freed = ubifs_destroy_tnc_subtree(c->zroot.znode); ubifs_tnc_close()
2874 * left_znode - get the znode to the left.
2876 * @znode: znode
2878 * This function returns a pointer to the znode to the left of @znode or NULL if
2882 struct ubifs_znode *znode) left_znode()
2884 int level = znode->level; left_znode()
2887 int n = znode->iip - 1; left_znode()
2890 znode = znode->parent; left_znode()
2891 if (!znode) left_znode()
2895 znode = get_znode(c, znode, n); left_znode()
2896 if (IS_ERR(znode)) left_znode()
2897 return znode; left_znode()
2898 while (znode->level != level) { left_znode()
2899 n = znode->child_cnt - 1; left_znode()
2900 znode = get_znode(c, znode, n); left_znode()
2901 if (IS_ERR(znode)) left_znode()
2902 return znode; left_znode()
2907 return znode; left_znode()
2911 * right_znode - get the znode to the right.
2913 * @znode: znode
2915 * This function returns a pointer to the znode to the right of @znode or NULL
2919 struct ubifs_znode *znode) right_znode()
2921 int level = znode->level; right_znode()
2924 int n = znode->iip + 1; right_znode()
2927 znode = znode->parent; right_znode()
2928 if (!znode) right_znode()
2930 if (n < znode->child_cnt) { right_znode()
2932 znode = get_znode(c, znode, n); right_znode()
2933 if (IS_ERR(znode)) right_znode()
2934 return znode; right_znode()
2935 while (znode->level != level) { right_znode()
2936 znode = get_znode(c, znode, 0); right_znode()
2937 if (IS_ERR(znode)) right_znode()
2938 return znode; right_znode()
2943 return znode; right_znode()
2961 * dirty znode which still refers the same @lnum:@offs. This function is clever
2964 * Note, if a znode was deleted or changed too much, then this function will
2968 * This function returns a pointer to the znode found or %NULL if it is not
2975 struct ubifs_znode *znode, *zn; lookup_znode() local
2987 /* Get the root znode */ lookup_znode()
2988 znode = c->zroot.znode; lookup_znode()
2989 if (!znode) { lookup_znode()
2990 znode = ubifs_load_znode(c, &c->zroot, NULL, 0); lookup_znode()
2991 if (IS_ERR(znode)) lookup_znode()
2992 return znode; lookup_znode()
2996 return znode; lookup_znode()
2998 if (level >= znode->level) lookup_znode()
3001 ubifs_search_zbranch(c, znode, key, &n); lookup_znode()
3004 * We reached a znode where the leftmost key is greater lookup_znode()
3011 znode = left_znode(c, znode); lookup_znode()
3012 if (!znode) lookup_znode()
3014 if (IS_ERR(znode)) lookup_znode()
3015 return znode; lookup_znode()
3016 ubifs_search_zbranch(c, znode, key, &n); lookup_znode()
3019 if (znode->level == level + 1) lookup_znode()
3021 znode = get_znode(c, znode, n); lookup_znode()
3022 if (IS_ERR(znode)) lookup_znode()
3023 return znode; lookup_znode()
3026 if (znode->zbranch[n].lnum == lnum && znode->zbranch[n].offs == offs) lookup_znode()
3027 return get_znode(c, znode, n); lookup_znode()
3035 zn = znode; lookup_znode()
3043 znode = left_znode(c, znode); lookup_znode()
3044 if (!znode) lookup_znode()
3046 if (IS_ERR(znode)) lookup_znode()
3047 return znode; lookup_znode()
3048 n = znode->child_cnt - 1; lookup_znode()
3051 if (znode->zbranch[n].lnum == lnum && lookup_znode()
3052 znode->zbranch[n].offs == offs) lookup_znode()
3053 return get_znode(c, znode, n); lookup_znode()
3055 if (keys_cmp(c, &znode->zbranch[n].key, key) < 0) lookup_znode()
3059 znode = zn; lookup_znode()
3064 if (++n >= znode->child_cnt) { lookup_znode()
3065 znode = right_znode(c, znode); lookup_znode()
3066 if (!znode) lookup_znode()
3068 if (IS_ERR(znode)) lookup_znode()
3069 return znode; lookup_znode()
3073 if (znode->zbranch[n].lnum == lnum && lookup_znode()
3074 znode->zbranch[n].offs == offs) lookup_znode()
3075 return get_znode(c, znode, n); lookup_znode()
3077 if (keys_cmp(c, &znode->zbranch[n].key, key) > 0) lookup_znode()
3092 * if the index node is referred to in the TNC and the corresponding znode is
3094 * znode is clean, and a negative error code in case of failure.
3103 struct ubifs_znode *znode; is_idx_node_in_tnc() local
3105 znode = lookup_znode(c, key, level, lnum, offs); is_idx_node_in_tnc()
3106 if (!znode) is_idx_node_in_tnc()
3108 if (IS_ERR(znode)) is_idx_node_in_tnc()
3109 return PTR_ERR(znode); is_idx_node_in_tnc()
3111 return ubifs_zn_dirty(znode) ? 1 : 2; is_idx_node_in_tnc()
3131 struct ubifs_znode *znode, *zn; is_leaf_node_in_tnc() local
3135 found = ubifs_lookup_level0(c, key, &znode, &n); is_leaf_node_in_tnc()
3140 zbr = &znode->zbranch[n]; is_leaf_node_in_tnc()
3149 zn = znode; is_leaf_node_in_tnc()
3153 err = tnc_prev(c, &znode, &n); is_leaf_node_in_tnc()
3158 if (keys_cmp(c, key, &znode->zbranch[n].key)) is_leaf_node_in_tnc()
3160 zbr = &znode->zbranch[n]; is_leaf_node_in_tnc()
3165 znode = zn; is_leaf_node_in_tnc()
3168 err = tnc_next(c, &znode, &n); is_leaf_node_in_tnc()
3174 if (keys_cmp(c, key, &znode->zbranch[n].key)) is_leaf_node_in_tnc()
3176 zbr = &znode->zbranch[n]; is_leaf_node_in_tnc()
3195 * the corresponding znode is clean or has not been loaded.
3240 struct ubifs_znode *znode; ubifs_dirty_idx_node() local
3244 znode = lookup_znode(c, key, level, lnum, offs); ubifs_dirty_idx_node()
3245 if (!znode) ubifs_dirty_idx_node()
3247 if (IS_ERR(znode)) { ubifs_dirty_idx_node()
3248 err = PTR_ERR(znode); ubifs_dirty_idx_node()
3251 znode = dirty_cow_bottom_up(c, znode); ubifs_dirty_idx_node()
3252 if (IS_ERR(znode)) { ubifs_dirty_idx_node()
3253 err = PTR_ERR(znode); ubifs_dirty_idx_node()
3278 struct ubifs_znode *znode; dbg_check_inode_size() local
3291 err = ubifs_lookup_level0(c, &from_key, &znode, &n); dbg_check_inode_size()
3300 err = tnc_next(c, &znode, &n); dbg_check_inode_size()
3309 key = &znode->zbranch[n].key; dbg_check_inode_size()
140 ins_clr_old_idx_znode(struct ubifs_info *c, struct ubifs_znode *znode) ins_clr_old_idx_znode() argument
196 copy_znode(struct ubifs_info *c, struct ubifs_znode *znode) copy_znode() argument
571 get_znode(struct ubifs_info *c, struct ubifs_znode *znode, int n) get_znode() argument
1079 dirty_cow_bottom_up(struct ubifs_info *c, struct ubifs_znode *znode) dirty_cow_bottom_up() argument
1873 correct_parent_keys(const struct ubifs_info *c, struct ubifs_znode *znode) correct_parent_keys() argument
2881 left_znode(struct ubifs_info *c, struct ubifs_znode *znode) left_znode() argument
2918 right_znode(struct ubifs_info *c, struct ubifs_znode *znode) right_znode() argument
|