Lines Matching refs:tb
51 static void create_virtual_node(struct tree_balance *tb, int h)
54 struct virtual_node *vn = tb->tb_vn;
56 struct buffer_head *Sh; /* this comes from tb->S[h] */
58 Sh = PATH_H_PBUFFER(tb->tb_path, h);
62 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
76 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
115 op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
116 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
117 reiserfs_panic(tb->tb_sb, "vs-8030",
125 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
137 vi->vi_item_len = tb->insert_size[0];
143 tb->insert_size[0]);
150 if (tb->CFR[0]) {
153 key = internal_key(tb->CFR[0], tb->rkey[0]);
178 reiserfs_panic(tb->tb_sb, "vs-8045",
194 static void check_left(struct tree_balance *tb, int h, int cur_free)
197 struct virtual_node *vn = tb->tb_vn;
205 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
213 tb->lnum[h] = 0;
214 tb->lbytes = -1;
218 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
230 tb->lnum[0] = vn->vn_nr_item;
231 tb->lbytes = -1;
241 tb->lnum[0] = 0;
248 tb->lnum[0]++;
260 tb->lbytes = -1;
265 tb->lbytes = op_check_left(vi, cur_free, 0, 0);
266 if (tb->lbytes != -1)
268 tb->lnum[0]++;
280 static void check_right(struct tree_balance *tb, int h, int cur_free)
283 struct virtual_node *vn = tb->tb_vn;
291 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
299 tb->rnum[h] = 0;
300 tb->rbytes = -1;
304 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
316 tb->rnum[h] = vn->vn_nr_item;
317 tb->rbytes = -1;
327 tb->rnum[0] = 0;
334 tb->rnum[0]++;
345 tb->rbytes = -1;
355 tb->rbytes = op_check_right(vi, cur_free);
356 if (tb->rbytes != -1)
358 tb->rnum[0]++;
374 static int get_num_ver(int mode, struct tree_balance *tb, int h,
380 struct virtual_node *vn = tb->tb_vn;
417 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
420 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
532 reiserfs_warning(tb->tb_sb, "vs-8111",
571 reiserfs_warning(tb->tb_sb, "vs-8115",
604 * Performs write of results of analysis of balancing into structure tb,
607 * tb tree_balance structure;
621 static void set_parameters(struct tree_balance *tb, int h, int lnum,
625 tb->lnum[h] = lnum;
626 tb->rnum[h] = rnum;
627 tb->blknum[h] = blk_num;
632 tb->s0num = *s012++;
633 tb->snum[0] = *s012++;
634 tb->snum[1] = *s012++;
635 tb->sbytes[0] = *s012++;
636 tb->sbytes[1] = *s012;
638 tb->lbytes = lb;
639 tb->rbytes = rb;
641 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
642 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
644 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
645 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
649 * check if node disappears if we shift tb->lnum[0] items to left
650 * neighbor and tb->rnum[0] to the right one.
652 static int is_leaf_removable(struct tree_balance *tb)
654 struct virtual_node *vn = tb->tb_vn;
663 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
664 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
672 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
678 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
686 if (tb->lbytes + tb->rbytes >= size) {
687 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
688 tb->lbytes, -1);
696 static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
698 struct virtual_node *vn = tb->tb_vn;
702 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
721 if (tb->CFR[0]
723 internal_key(tb->CFR[0],
724 tb->rkey[0])))
749 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
750 PROC_INFO_INC(tb->tb_sb, leaves_removable);
766 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
771 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
772 tb->lbytes, -1);\
774 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
785 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
790 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
791 -1, tb->rbytes);\
793 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
797 static void free_buffers_in_tb(struct tree_balance *tb)
801 pathrelse(tb->tb_path);
804 brelse(tb->L[i]);
805 brelse(tb->R[i]);
806 brelse(tb->FL[i]);
807 brelse(tb->FR[i]);
808 brelse(tb->CFL[i]);
809 brelse(tb->CFR[i]);
811 tb->L[i] = NULL;
812 tb->R[i] = NULL;
813 tb->FL[i] = NULL;
814 tb->FR[i] = NULL;
815 tb->CFL[i] = NULL;
816 tb->CFR[i] = NULL;
827 static int get_empty_nodes(struct tree_balance *tb, int h)
829 struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);
834 struct super_block *sb = tb->tb_sb;
840 * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule
857 for (counter = 0, number_of_freeblk = tb->cur_blknum;
860 (tb->blknum[counter]) ? (tb->blknum[counter] -
865 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
879 if (reiserfs_new_form_blocknrs(tb, blocknrs,
898 RFALSE(tb->FEB[tb->cur_blknum],
902 tb->FEB[tb->cur_blknum++] = new_bh;
905 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
915 static int get_lfree(struct tree_balance *tb, int h)
920 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
921 (l = tb->FL[h]) == NULL)
925 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
938 static int get_rfree(struct tree_balance *tb, int h)
943 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
944 (r = tb->FR[h]) == NULL)
948 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
959 static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
962 struct super_block *sb = tb->tb_sb;
967 if (!tb->FL[h])
971 father = PATH_H_PBUFFER(tb->tb_path, h + 1);
975 !B_IS_IN_TREE(tb->FL[h]) ||
977 !buffer_uptodate(tb->FL[h]),
979 father, tb->FL[h]);
985 left_neighbor_position = (father == tb->FL[h]) ?
986 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
989 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
1023 static int get_far_parent(struct tree_balance *tb,
1030 struct treepath *path = tb->tb_path;
1092 (tb->tb_path,
1094 SB_ROOT_BLOCK(tb->tb_sb)) {
1110 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
1112 reiserfs_write_lock_nested(tb->tb_sb, depth);
1113 if (FILESYSTEM_CHANGED_TB(tb)) {
1129 LEFT_PARENTS) ? (tb->lkey[h - 1] =
1131 1) : (tb->rkey[h -
1139 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1144 if (FILESYSTEM_CHANGED_TB(tb)) {
1172 static int get_parents(struct tree_balance *tb, int h)
1174 struct treepath *path = tb->tb_path;
1177 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
1187 brelse(tb->FL[h]);
1188 brelse(tb->CFL[h]);
1189 brelse(tb->FR[h]);
1190 brelse(tb->CFR[h]);
1191 tb->FL[h] = NULL;
1192 tb->CFL[h] = NULL;
1193 tb->FR[h] = NULL;
1194 tb->CFR[h] = NULL;
1206 tb->lkey[h] = position - 1;
1216 if ((ret = get_far_parent(tb, h + 1, &curf,
1222 brelse(tb->FL[h]);
1223 tb->FL[h] = curf; /* New initialization of FL[h]. */
1224 brelse(tb->CFL[h]);
1225 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */
1242 get_far_parent(tb, h + 1, &curf, &curcf,
1251 tb->rkey[h] = position;
1254 brelse(tb->FR[h]);
1256 tb->FR[h] = curf;
1258 brelse(tb->CFR[h]);
1260 tb->CFR[h] = curcf;
1274 struct tree_balance *tb, int h)
1276 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
1277 int levbytes = tb->insert_size[h];
1282 if (tb->CFR[h])
1283 r_key = internal_key(tb->CFR[h], tb->rkey[h]);
1298 tb->s0num =
1301 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1305 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
1314 * tb tree_balance structure;
1324 static int ip_check_balance(struct tree_balance *tb, int h)
1326 struct virtual_node *vn = tb->tb_vn;
1373 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1374 levbytes = tb->insert_size[h];
1379 reiserfs_panic(tb->tb_sb, "vs-8210",
1381 switch (ret = get_empty_nodes(tb, h)) {
1384 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1391 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1397 ret = get_parents(tb, h);
1404 rfree = get_rfree(tb, h);
1405 lfree = get_lfree(tb, h);
1408 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1412 create_virtual_node(tb, h);
1416 * neighbor (in tb structure) and the maximal number of bytes
1420 check_left(tb, h, lfree);
1424 * neighbor (in tb structure) and the maximal number of bytes
1428 check_right(tb, h, rfree);
1434 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
1446 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1448 tb->rnum[h]);
1449 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1459 (tb->lnum[h] >= vn->vn_nr_item + 1 ||
1460 tb->rnum[h] >= vn->vn_nr_item + 1),
1462 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
1463 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
1470 if (!h && is_leaf_removable(tb))
1483 tb->s0num = vn->vn_nr_item;
1484 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1512 lpar = tb->lnum[h];
1513 rpar = tb->rnum[h];
1523 nver = get_num_ver(vn->vn_mode, tb, h,
1534 nver1 = get_num_ver(vn->vn_mode, tb, h,
1550 lnver = get_num_ver(vn->vn_mode, tb, h,
1551 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1557 lnver1 = get_num_ver(vn->vn_mode, tb, h,
1559 ((tb->lbytes != -1) ? 1 : 0),
1560 tb->lbytes, 0, -1,
1575 rnver = get_num_ver(vn->vn_mode, tb, h,
1578 ((tb->
1586 rnver1 = get_num_ver(vn->vn_mode, tb, h,
1589 ((tb->rbytes != -1) ? 1 : 0)),
1590 tb->rbytes,
1605 lrnver = get_num_ver(vn->vn_mode, tb, h,
1606 lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1609 ((tb->
1617 lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1619 ((tb->lbytes != -1) ? 1 : 0),
1620 tb->lbytes,
1622 ((tb->rbytes != -1) ? 1 : 0)),
1623 tb->rbytes,
1639 (tb->lnum[h] != 1 ||
1640 tb->rnum[h] != 1 ||
1644 set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1646 tb->lbytes, tb->rbytes);
1648 set_parameters(tb, h,
1649 tb->lnum[h] -
1650 ((tb->lbytes == -1) ? 0 : 1),
1651 tb->rnum[h] -
1652 ((tb->rbytes == -1) ? 0 : 1),
1663 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1695 if (is_left_neighbor_in_cache(tb, h)) {
1714 * tb tree_balance structure;
1726 static int dc_check_balance_internal(struct tree_balance *tb, int h)
1728 struct virtual_node *vn = tb->tb_vn;
1738 Sh = PATH_H_PBUFFER(tb->tb_path, h);
1739 Fh = PATH_H_PPARENT(tb->tb_path, h);
1742 * using tb->insert_size[h], which is negative in this case,
1747 create_virtual_node(tb, h);
1752 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1760 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
1764 if ((ret = get_parents(tb, h)) != CARRY_ON)
1768 rfree = get_rfree(tb, h);
1769 lfree = get_lfree(tb, h);
1772 check_left(tb, h, lfree);
1773 check_right(tb, h, rfree);
1786 if (tb->lnum[h] >= vn->vn_nr_item + 1) {
1792 PATH_H_B_ITEM_ORDER(tb->tb_path,
1794 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1795 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1797 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1803 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1809 PATH_H_B_ITEM_ORDER(tb->tb_path,
1812 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1814 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1824 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1828 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1829 tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
1830 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1831 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1837 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1846 if (tb->lnum[h] >= vn->vn_nr_item + 1)
1847 if (is_left_neighbor_in_cache(tb, h)
1848 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
1854 PATH_H_B_ITEM_ORDER(tb->tb_path,
1856 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1857 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1859 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
1864 if (tb->rnum[h] >= vn->vn_nr_item + 1) {
1870 PATH_H_B_ITEM_ORDER(tb->tb_path,
1872 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1874 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
1879 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
1883 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1885 tb->rnum[h]);
1886 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1892 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
1895 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
1899 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1901 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
1905 set_parameters(tb, h, 0,
1906 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1916 * tb tree_balance structure;
1925 static int dc_check_balance_leaf(struct tree_balance *tb, int h)
1927 struct virtual_node *vn = tb->tb_vn;
1947 S0 = PATH_H_PBUFFER(tb->tb_path, 0);
1948 F0 = PATH_H_PPARENT(tb->tb_path, 0);
1950 levbytes = tb->insert_size[h];
1959 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1963 if ((ret = get_parents(tb, h)) != CARRY_ON)
1967 rfree = get_rfree(tb, h);
1968 lfree = get_lfree(tb, h);
1970 create_virtual_node(tb, h);
1973 if (are_leaves_removable(tb, lfree, rfree))
1982 check_left(tb, h, lfree);
1983 check_right(tb, h, rfree);
1986 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1987 if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_item) || /* S can not be merged with R */
1988 !tb->FR[h]) {
1990 RFALSE(!tb->FL[h],
1994 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
1999 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
2000 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
2008 if (is_leaf_removable(tb))
2012 tb->s0num = vn->vn_nr_item;
2013 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
2022 * tb tree_balance structure;
2031 static int dc_check_balance(struct tree_balance *tb, int h)
2033 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
2037 return dc_check_balance_internal(tb, h);
2039 return dc_check_balance_leaf(tb, h);
2047 * tb tree_balance structure:
2049 * tb is a large structure that must be read about in the header
2062 struct tree_balance *tb,
2070 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
2071 vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
2082 if (tb->insert_size[h] > 0)
2083 return ip_check_balance(tb, h);
2086 return dc_check_balance(tb, h);
2090 static int get_direct_parent(struct tree_balance *tb, int h)
2093 struct treepath *path = tb->tb_path;
2095 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
2104 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
2130 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2132 reiserfs_write_lock_nested(tb->tb_sb, depth);
2133 if (FILESYSTEM_CHANGED_TB(tb))
2151 static int get_neighbors(struct tree_balance *tb, int h)
2154 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
2156 struct super_block *sb = tb->tb_sb;
2162 if (tb->lnum[h]) {
2165 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
2167 RFALSE(bh == tb->FL[h] &&
2168 !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
2173 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
2175 son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
2176 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2178 reiserfs_write_lock_nested(tb->tb_sb, depth);
2181 if (FILESYSTEM_CHANGED_TB(tb)) {
2187 RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
2188 child_position > B_NR_ITEMS(tb->FL[h]) ||
2189 B_N_CHILD_NUM(tb->FL[h], child_position) !=
2195 dc_size(B_N_CHILD(tb->FL[0], child_position)),
2198 brelse(tb->L[h]);
2199 tb->L[h] = bh;
2203 if (tb->rnum[h]) {
2205 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
2207 RFALSE(bh == tb->FR[h] &&
2208 PATH_OFFSET_POSITION(tb->tb_path,
2214 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
2215 son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
2216 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2218 reiserfs_write_lock_nested(tb->tb_sb, depth);
2221 if (FILESYSTEM_CHANGED_TB(tb)) {
2226 brelse(tb->R[h]);
2227 tb->R[h] = bh;
2232 dc_size(B_N_CHILD(tb->FR[0], child_position)),
2235 dc_size(B_N_CHILD(tb->FR[0], child_position)));
2265 static int get_mem_for_virtual_node(struct tree_balance *tb)
2271 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
2274 if (size > tb->vn_buf_size) {
2275 if (tb->vn_buf) {
2277 kfree(tb->vn_buf);
2283 tb->vn_buf_size = size;
2294 free_buffers_in_tb(tb);
2297 tb->vn_buf_size = 0;
2299 tb->vn_buf = buf;
2304 tb->vn_buf = buf;
2307 if (check_fs && FILESYSTEM_CHANGED_TB(tb))
2364 static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
2376 for (i = tb->tb_path->path_length;
2378 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
2385 if (PATH_PLAST_BUFFER(tb->tb_path) ==
2386 PATH_OFFSET_PBUFFER(tb->tb_path, i))
2387 tb_buffer_sanity_check(tb->tb_sb,
2389 (tb->tb_path,
2391 tb->tb_path->
2394 if (!clear_all_dirty_bits(tb->tb_sb,
2396 (tb->tb_path,
2399 PATH_OFFSET_PBUFFER(tb->tb_path,
2405 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
2408 if (tb->lnum[i]) {
2410 if (tb->L[i]) {
2411 tb_buffer_sanity_check(tb->tb_sb,
2412 tb->L[i],
2415 (tb->tb_sb, tb->L[i]))
2416 locked = tb->L[i];
2419 if (!locked && tb->FL[i]) {
2420 tb_buffer_sanity_check(tb->tb_sb,
2421 tb->FL[i],
2424 (tb->tb_sb, tb->FL[i]))
2425 locked = tb->FL[i];
2428 if (!locked && tb->CFL[i]) {
2429 tb_buffer_sanity_check(tb->tb_sb,
2430 tb->CFL[i],
2433 (tb->tb_sb, tb->CFL[i]))
2434 locked = tb->CFL[i];
2439 if (!locked && (tb->rnum[i])) {
2441 if (tb->R[i]) {
2442 tb_buffer_sanity_check(tb->tb_sb,
2443 tb->R[i],
2446 (tb->tb_sb, tb->R[i]))
2447 locked = tb->R[i];
2450 if (!locked && tb->FR[i]) {
2451 tb_buffer_sanity_check(tb->tb_sb,
2452 tb->FR[i],
2455 (tb->tb_sb, tb->FR[i]))
2456 locked = tb->FR[i];
2459 if (!locked && tb->CFR[i]) {
2460 tb_buffer_sanity_check(tb->tb_sb,
2461 tb->CFR[i],
2464 (tb->tb_sb, tb->CFR[i]))
2465 locked = tb->CFR[i];
2480 if (tb->FEB[i]) {
2482 (tb->tb_sb, tb->FEB[i]))
2483 locked = tb->FEB[i];
2492 reiserfs_warning(tb->tb_sb, "reiserfs-8200",
2499 return (FILESYSTEM_CHANGED_TB(tb)) ?
2503 depth = reiserfs_write_unlock_nested(tb->tb_sb);
2505 reiserfs_write_lock_nested(tb->tb_sb, depth);
2506 if (FILESYSTEM_CHANGED_TB(tb))
2536 * tb tree_balance structure;
2546 int fix_nodes(int op_mode, struct tree_balance *tb,
2549 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2557 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
2559 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
2561 pos_in_item = tb->tb_path->pos_in_item;
2563 tb->fs_gen = get_generation(tb->tb_sb);
2571 reiserfs_prepare_for_journal(tb->tb_sb,
2572 SB_BUFFER_WITH_SB(tb->tb_sb), 1);
2573 journal_mark_dirty(tb->transaction_handle,
2574 SB_BUFFER_WITH_SB(tb->tb_sb));
2575 if (FILESYSTEM_CHANGED_TB(tb))
2580 int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2582 reiserfs_write_lock_nested(tb->tb_sb, depth);
2583 if (FILESYSTEM_CHANGED_TB(tb))
2587 if (REISERFS_SB(tb->tb_sb)->cur_tb) {
2589 reiserfs_panic(tb->tb_sb, "PAP-8305",
2594 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2603 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
2613 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
2617 tb->insert_size[0]);
2621 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
2626 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
2627 /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
2631 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2632 ret = get_direct_parent(tb, h);
2636 ret = check_balance(op_mode, tb, h, item_num,
2641 ret = get_neighbors(tb, h);
2645 tb->insert_size[h + 1] = 0;
2655 ret = get_neighbors(tb, h);
2663 ret = get_empty_nodes(tb, h);
2671 if (!PATH_H_PBUFFER(tb->tb_path, h)) {
2673 RFALSE(tb->blknum[h] != 1,
2677 tb->insert_size[h + 1] = 0;
2678 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2685 if (tb->blknum[h] > 1) {
2690 tb->insert_size[h + 1] =
2692 KEY_SIZE) * (tb->blknum[h] - 1) +
2695 tb->insert_size[h + 1] = 0;
2697 tb->insert_size[h + 1] =
2698 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
2701 ret = wait_tb_buffers_until_unlocked(tb);
2703 if (FILESYSTEM_CHANGED_TB(tb)) {
2728 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2730 pathrelse(tb->tb_path);
2735 reiserfs_restore_prepared_buffer(tb->tb_sb,
2736 tb->L[i]);
2737 reiserfs_restore_prepared_buffer(tb->tb_sb,
2738 tb->R[i]);
2739 reiserfs_restore_prepared_buffer(tb->tb_sb,
2740 tb->FL[i]);
2741 reiserfs_restore_prepared_buffer(tb->tb_sb,
2742 tb->FR[i]);
2743 reiserfs_restore_prepared_buffer(tb->tb_sb,
2744 tb->
2746 reiserfs_restore_prepared_buffer(tb->tb_sb,
2747 tb->
2751 brelse(tb->L[i]);
2752 brelse(tb->R[i]);
2753 brelse(tb->FL[i]);
2754 brelse(tb->FR[i]);
2755 brelse(tb->CFL[i]);
2756 brelse(tb->CFR[i]);
2758 tb->L[i] = NULL;
2759 tb->R[i] = NULL;
2760 tb->FL[i] = NULL;
2761 tb->FR[i] = NULL;
2762 tb->CFL[i] = NULL;
2763 tb->CFR[i] = NULL;
2768 if (tb->FEB[i])
2770 (tb->tb_sb, tb->FEB[i]);
2778 void unfix_nodes(struct tree_balance *tb)
2783 pathrelse_and_restore(tb->tb_sb, tb->tb_path);
2787 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
2788 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
2789 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
2790 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
2791 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
2792 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
2794 brelse(tb->L[i]);
2795 brelse(tb->R[i]);
2796 brelse(tb->FL[i]);
2797 brelse(tb->FR[i]);
2798 brelse(tb->CFL[i]);
2799 brelse(tb->CFR[i]);
2804 if (tb->FEB[i]) {
2805 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2810 brelse(tb->FEB[i]);
2811 reiserfs_free_block(tb->transaction_handle, NULL,
2814 if (tb->used[i]) {
2816 brelse(tb->used[i]);
2820 kfree(tb->vn_buf);