Lines Matching refs:tb
51 static void create_virtual_node(struct tree_balance *tb, int h) in create_virtual_node() argument
54 struct virtual_node *vn = tb->tb_vn; in create_virtual_node()
58 Sh = PATH_H_PBUFFER(tb->tb_path, h); in create_virtual_node()
62 MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h]; in create_virtual_node()
76 vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1); in create_virtual_node()
115 op_create_vi(vn, vi, is_affected, tb->insert_size[0]); in create_virtual_node()
116 if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr) in create_virtual_node()
117 reiserfs_panic(tb->tb_sb, "vs-8030", in create_virtual_node()
125 vn->vn_vi[new_num].vi_item_len += tb->insert_size[0]; in create_virtual_node()
137 vi->vi_item_len = tb->insert_size[0]; in create_virtual_node()
143 tb->insert_size[0]); in create_virtual_node()
150 if (tb->CFR[0]) { in create_virtual_node()
153 key = internal_key(tb->CFR[0], tb->rkey[0]); in create_virtual_node()
178 reiserfs_panic(tb->tb_sb, "vs-8045", in create_virtual_node()
194 static void check_left(struct tree_balance *tb, int h, int cur_free) in check_left() argument
197 struct virtual_node *vn = tb->tb_vn; in check_left()
205 tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_left()
213 tb->lnum[h] = 0; in check_left()
214 tb->lbytes = -1; in check_left()
218 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), in check_left()
230 tb->lnum[0] = vn->vn_nr_item; in check_left()
231 tb->lbytes = -1; in check_left()
241 tb->lnum[0] = 0; in check_left()
248 tb->lnum[0]++; in check_left()
260 tb->lbytes = -1; in check_left()
265 tb->lbytes = op_check_left(vi, cur_free, 0, 0); in check_left()
266 if (tb->lbytes != -1) in check_left()
268 tb->lnum[0]++; in check_left()
280 static void check_right(struct tree_balance *tb, int h, int cur_free) in check_right() argument
283 struct virtual_node *vn = tb->tb_vn; in check_right()
291 tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE); in check_right()
299 tb->rnum[h] = 0; in check_right()
300 tb->rbytes = -1; in check_right()
304 RFALSE(!PATH_H_PPARENT(tb->tb_path, 0), in check_right()
316 tb->rnum[h] = vn->vn_nr_item; in check_right()
317 tb->rbytes = -1; in check_right()
327 tb->rnum[0] = 0; in check_right()
334 tb->rnum[0]++; in check_right()
345 tb->rbytes = -1; in check_right()
355 tb->rbytes = op_check_right(vi, cur_free); in check_right()
356 if (tb->rbytes != -1) in check_right()
358 tb->rnum[0]++; in check_right()
374 static int get_num_ver(int mode, struct tree_balance *tb, int h, in get_num_ver() argument
381 struct virtual_node *vn = tb->tb_vn; in get_num_ver()
418 RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE), in get_num_ver()
421 max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h)); in get_num_ver()
534 reiserfs_warning(tb->tb_sb, "vs-8111", in get_num_ver()
573 reiserfs_warning(tb->tb_sb, "vs-8115", in get_num_ver()
623 static void set_parameters(struct tree_balance *tb, int h, int lnum, in set_parameters() argument
627 tb->lnum[h] = lnum; in set_parameters()
628 tb->rnum[h] = rnum; in set_parameters()
629 tb->blknum[h] = blk_num; in set_parameters()
634 tb->s0num = *s012++; in set_parameters()
635 tb->snum[0] = *s012++; in set_parameters()
636 tb->snum[1] = *s012++; in set_parameters()
637 tb->sbytes[0] = *s012++; in set_parameters()
638 tb->sbytes[1] = *s012; in set_parameters()
640 tb->lbytes = lb; in set_parameters()
641 tb->rbytes = rb; in set_parameters()
643 PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum); in set_parameters()
644 PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum); in set_parameters()
646 PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb); in set_parameters()
647 PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb); in set_parameters()
654 static int is_leaf_removable(struct tree_balance *tb) in is_leaf_removable() argument
656 struct virtual_node *vn = tb->tb_vn; in is_leaf_removable()
665 to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0); in is_leaf_removable()
666 to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0); in is_leaf_removable()
674 set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0, in is_leaf_removable()
680 if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1) in is_leaf_removable()
688 if (tb->lbytes + tb->rbytes >= size) { in is_leaf_removable()
689 set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL, in is_leaf_removable()
690 tb->lbytes, -1); in is_leaf_removable()
698 static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree) in are_leaves_removable() argument
700 struct virtual_node *vn = tb->tb_vn; in are_leaves_removable()
704 S0 = PATH_H_PBUFFER(tb->tb_path, 0); in are_leaves_removable()
723 if (tb->CFR[0] in are_leaves_removable()
725 internal_key(tb->CFR[0], in are_leaves_removable()
726 tb->rkey[0]))) in are_leaves_removable()
751 set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1); in are_leaves_removable()
752 PROC_INFO_INC(tb->tb_sb, leaves_removable); in are_leaves_removable()
768 set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
773 set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
774 tb->lbytes, -1);\
776 set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
787 set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
792 set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
793 -1, tb->rbytes);\
795 set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
799 static void free_buffers_in_tb(struct tree_balance *tb) in free_buffers_in_tb() argument
803 pathrelse(tb->tb_path); in free_buffers_in_tb()
806 brelse(tb->L[i]); in free_buffers_in_tb()
807 brelse(tb->R[i]); in free_buffers_in_tb()
808 brelse(tb->FL[i]); in free_buffers_in_tb()
809 brelse(tb->FR[i]); in free_buffers_in_tb()
810 brelse(tb->CFL[i]); in free_buffers_in_tb()
811 brelse(tb->CFR[i]); in free_buffers_in_tb()
813 tb->L[i] = NULL; in free_buffers_in_tb()
814 tb->R[i] = NULL; in free_buffers_in_tb()
815 tb->FL[i] = NULL; in free_buffers_in_tb()
816 tb->FR[i] = NULL; in free_buffers_in_tb()
817 tb->CFL[i] = NULL; in free_buffers_in_tb()
818 tb->CFR[i] = NULL; in free_buffers_in_tb()
829 static int get_empty_nodes(struct tree_balance *tb, int h) in get_empty_nodes() argument
831 struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h); in get_empty_nodes()
836 struct super_block *sb = tb->tb_sb; in get_empty_nodes()
859 for (counter = 0, number_of_freeblk = tb->cur_blknum; in get_empty_nodes()
862 (tb->blknum[counter]) ? (tb->blknum[counter] - in get_empty_nodes()
867 amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1; in get_empty_nodes()
881 if (reiserfs_new_form_blocknrs(tb, blocknrs, in get_empty_nodes()
900 RFALSE(tb->FEB[tb->cur_blknum], in get_empty_nodes()
904 tb->FEB[tb->cur_blknum++] = new_bh; in get_empty_nodes()
907 if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb)) in get_empty_nodes()
917 static int get_lfree(struct tree_balance *tb, int h) in get_lfree() argument
922 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_lfree()
923 (l = tb->FL[h]) == NULL) in get_lfree()
927 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1; in get_lfree()
940 static int get_rfree(struct tree_balance *tb, int h) in get_rfree() argument
945 if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL || in get_rfree()
946 (r = tb->FR[h]) == NULL) in get_rfree()
950 order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1; in get_rfree()
961 static int is_left_neighbor_in_cache(struct tree_balance *tb, int h) in is_left_neighbor_in_cache() argument
964 struct super_block *sb = tb->tb_sb; in is_left_neighbor_in_cache()
969 if (!tb->FL[h]) in is_left_neighbor_in_cache()
973 father = PATH_H_PBUFFER(tb->tb_path, h + 1); in is_left_neighbor_in_cache()
977 !B_IS_IN_TREE(tb->FL[h]) || in is_left_neighbor_in_cache()
979 !buffer_uptodate(tb->FL[h]), in is_left_neighbor_in_cache()
981 father, tb->FL[h]); in is_left_neighbor_in_cache()
987 left_neighbor_position = (father == tb->FL[h]) ? in is_left_neighbor_in_cache()
988 tb->lkey[h] : B_NR_ITEMS(tb->FL[h]); in is_left_neighbor_in_cache()
991 B_N_CHILD_NUM(tb->FL[h], left_neighbor_position); in is_left_neighbor_in_cache()
1025 static int get_far_parent(struct tree_balance *tb, in get_far_parent() argument
1032 struct treepath *path = tb->tb_path; in get_far_parent()
1094 (tb->tb_path, in get_far_parent()
1096 SB_ROOT_BLOCK(tb->tb_sb)) { in get_far_parent()
1112 int depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_far_parent()
1114 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_far_parent()
1115 if (FILESYSTEM_CHANGED_TB(tb)) { in get_far_parent()
1131 LEFT_PARENTS) ? (tb->lkey[h - 1] = in get_far_parent()
1133 1) : (tb->rkey[h - in get_far_parent()
1141 (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father, in get_far_parent()
1146 if (FILESYSTEM_CHANGED_TB(tb)) { in get_far_parent()
1174 static int get_parents(struct tree_balance *tb, int h) in get_parents() argument
1176 struct treepath *path = tb->tb_path; in get_parents()
1179 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); in get_parents()
1189 brelse(tb->FL[h]); in get_parents()
1190 brelse(tb->CFL[h]); in get_parents()
1191 brelse(tb->FR[h]); in get_parents()
1192 brelse(tb->CFR[h]); in get_parents()
1193 tb->FL[h] = NULL; in get_parents()
1194 tb->CFL[h] = NULL; in get_parents()
1195 tb->FR[h] = NULL; in get_parents()
1196 tb->CFR[h] = NULL; in get_parents()
1208 tb->lkey[h] = position - 1; in get_parents()
1218 if ((ret = get_far_parent(tb, h + 1, &curf, in get_parents()
1224 brelse(tb->FL[h]); in get_parents()
1225 tb->FL[h] = curf; /* New initialization of FL[h]. */ in get_parents()
1226 brelse(tb->CFL[h]); in get_parents()
1227 tb->CFL[h] = curcf; /* New initialization of CFL[h]. */ in get_parents()
1244 get_far_parent(tb, h + 1, &curf, &curcf, in get_parents()
1253 tb->rkey[h] = position; in get_parents()
1256 brelse(tb->FR[h]); in get_parents()
1258 tb->FR[h] = curf; in get_parents()
1260 brelse(tb->CFR[h]); in get_parents()
1262 tb->CFR[h] = curcf; in get_parents()
1276 struct tree_balance *tb, int h) in can_node_be_removed() argument
1278 struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h); in can_node_be_removed()
1279 int levbytes = tb->insert_size[h]; in can_node_be_removed()
1284 if (tb->CFR[h]) in can_node_be_removed()
1285 r_key = internal_key(tb->CFR[h], tb->rkey[h]); in can_node_be_removed()
1300 tb->s0num = in can_node_be_removed()
1303 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in can_node_be_removed()
1307 PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]); in can_node_be_removed()
1326 static int ip_check_balance(struct tree_balance *tb, int h) in ip_check_balance() argument
1328 struct virtual_node *vn = tb->tb_vn; in ip_check_balance()
1375 Sh = PATH_H_PBUFFER(tb->tb_path, h); in ip_check_balance()
1376 levbytes = tb->insert_size[h]; in ip_check_balance()
1381 reiserfs_panic(tb->tb_sb, "vs-8210", in ip_check_balance()
1383 switch (ret = get_empty_nodes(tb, h)) { in ip_check_balance()
1386 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1393 reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect " in ip_check_balance()
1399 ret = get_parents(tb, h); in ip_check_balance()
1406 rfree = get_rfree(tb, h); in ip_check_balance()
1407 lfree = get_lfree(tb, h); in ip_check_balance()
1410 if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) == in ip_check_balance()
1414 create_virtual_node(tb, h); in ip_check_balance()
1422 check_left(tb, h, lfree); in ip_check_balance()
1430 check_right(tb, h, rfree); in ip_check_balance()
1436 if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) { in ip_check_balance()
1448 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in ip_check_balance()
1450 tb->rnum[h]); in ip_check_balance()
1451 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in ip_check_balance()
1461 (tb->lnum[h] >= vn->vn_nr_item + 1 || in ip_check_balance()
1462 tb->rnum[h] >= vn->vn_nr_item + 1), in ip_check_balance()
1464 RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) || in ip_check_balance()
1465 (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))), in ip_check_balance()
1472 if (!h && is_leaf_removable(tb)) in ip_check_balance()
1485 tb->s0num = vn->vn_nr_item; in ip_check_balance()
1486 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in ip_check_balance()
1514 lpar = tb->lnum[h]; in ip_check_balance()
1515 rpar = tb->rnum[h]; in ip_check_balance()
1525 nver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1536 nver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1552 lnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1553 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1559 lnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1561 ((tb->lbytes != -1) ? 1 : 0), in ip_check_balance()
1562 tb->lbytes, 0, -1, in ip_check_balance()
1577 rnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1580 ((tb-> in ip_check_balance()
1588 rnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1591 ((tb->rbytes != -1) ? 1 : 0)), in ip_check_balance()
1592 tb->rbytes, in ip_check_balance()
1607 lrnver = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1608 lpar - ((h || tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1611 ((tb-> in ip_check_balance()
1619 lrnver1 = get_num_ver(vn->vn_mode, tb, h, in ip_check_balance()
1621 ((tb->lbytes != -1) ? 1 : 0), in ip_check_balance()
1622 tb->lbytes, in ip_check_balance()
1624 ((tb->rbytes != -1) ? 1 : 0)), in ip_check_balance()
1625 tb->rbytes, in ip_check_balance()
1641 (tb->lnum[h] != 1 || in ip_check_balance()
1642 tb->rnum[h] != 1 || in ip_check_balance()
1646 set_parameters(tb, h, tb->lnum[h], tb->rnum[h], in ip_check_balance()
1648 tb->lbytes, tb->rbytes); in ip_check_balance()
1650 set_parameters(tb, h, in ip_check_balance()
1651 tb->lnum[h] - in ip_check_balance()
1652 ((tb->lbytes == -1) ? 0 : 1), in ip_check_balance()
1653 tb->rnum[h] - in ip_check_balance()
1654 ((tb->rbytes == -1) ? 0 : 1), in ip_check_balance()
1665 set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1, in ip_check_balance()
1697 if (is_left_neighbor_in_cache(tb, h)) { in ip_check_balance()
1728 static int dc_check_balance_internal(struct tree_balance *tb, int h) in dc_check_balance_internal() argument
1730 struct virtual_node *vn = tb->tb_vn; in dc_check_balance_internal()
1740 Sh = PATH_H_PBUFFER(tb->tb_path, h); in dc_check_balance_internal()
1741 Fh = PATH_H_PPARENT(tb->tb_path, h); in dc_check_balance_internal()
1751 create_virtual_node(tb, h); in dc_check_balance_internal()
1756 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1764 set_parameters(tb, h, 0, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1768 if ((ret = get_parents(tb, h)) != CARRY_ON) in dc_check_balance_internal()
1772 rfree = get_rfree(tb, h); in dc_check_balance_internal()
1773 lfree = get_lfree(tb, h); in dc_check_balance_internal()
1776 check_left(tb, h, lfree); in dc_check_balance_internal()
1777 check_right(tb, h, rfree); in dc_check_balance_internal()
1790 if (tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1796 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1798 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1799 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / in dc_check_balance_internal()
1801 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, in dc_check_balance_internal()
1807 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1813 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1816 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / in dc_check_balance_internal()
1818 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, in dc_check_balance_internal()
1828 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1832 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - in dc_check_balance_internal()
1833 tb->rnum[h] + vn->vn_nr_item + 1) / 2 - in dc_check_balance_internal()
1834 (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]); in dc_check_balance_internal()
1835 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, in dc_check_balance_internal()
1841 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1850 if (tb->lnum[h] >= vn->vn_nr_item + 1) in dc_check_balance_internal()
1851 if (is_left_neighbor_in_cache(tb, h) in dc_check_balance_internal()
1852 || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) { in dc_check_balance_internal()
1858 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1860 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1; in dc_check_balance_internal()
1861 n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE + in dc_check_balance_internal()
1863 set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1); in dc_check_balance_internal()
1868 if (tb->rnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1874 PATH_H_B_ITEM_ORDER(tb->tb_path, in dc_check_balance_internal()
1876 n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE + in dc_check_balance_internal()
1878 set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1); in dc_check_balance_internal()
1883 if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) { in dc_check_balance_internal()
1887 ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] + in dc_check_balance_internal()
1889 tb->rnum[h]); in dc_check_balance_internal()
1890 set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL, in dc_check_balance_internal()
1896 RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root"); in dc_check_balance_internal()
1899 if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) { in dc_check_balance_internal()
1903 (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1905 set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1); in dc_check_balance_internal()
1909 set_parameters(tb, h, 0, in dc_check_balance_internal()
1910 -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item + in dc_check_balance_internal()
1929 static int dc_check_balance_leaf(struct tree_balance *tb, int h) in dc_check_balance_leaf() argument
1931 struct virtual_node *vn = tb->tb_vn; in dc_check_balance_leaf()
1951 S0 = PATH_H_PBUFFER(tb->tb_path, 0); in dc_check_balance_leaf()
1952 F0 = PATH_H_PPARENT(tb->tb_path, 0); in dc_check_balance_leaf()
1954 levbytes = tb->insert_size[h]; in dc_check_balance_leaf()
1963 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
1967 if ((ret = get_parents(tb, h)) != CARRY_ON) in dc_check_balance_leaf()
1971 rfree = get_rfree(tb, h); in dc_check_balance_leaf()
1972 lfree = get_lfree(tb, h); in dc_check_balance_leaf()
1974 create_virtual_node(tb, h); in dc_check_balance_leaf()
1977 if (are_leaves_removable(tb, lfree, rfree)) in dc_check_balance_leaf()
1986 check_left(tb, h, lfree); in dc_check_balance_leaf()
1987 check_right(tb, h, rfree); in dc_check_balance_leaf()
1990 if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1) in dc_check_balance_leaf()
1991 …if (is_left_neighbor_in_cache(tb, h) || ((tb->rnum[0] - ((tb->rbytes == -1) ? 0 : 1)) < vn->vn_nr_… in dc_check_balance_leaf()
1992 !tb->FR[h]) { in dc_check_balance_leaf()
1994 RFALSE(!tb->FL[h], in dc_check_balance_leaf()
1998 set_parameters(tb, h, -1, 0, 0, NULL, -1, -1); in dc_check_balance_leaf()
2003 if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) { in dc_check_balance_leaf()
2004 set_parameters(tb, h, 0, -1, 0, NULL, -1, -1); in dc_check_balance_leaf()
2012 if (is_leaf_removable(tb)) in dc_check_balance_leaf()
2016 tb->s0num = vn->vn_nr_item; in dc_check_balance_leaf()
2017 set_parameters(tb, h, 0, 0, 1, NULL, -1, -1); in dc_check_balance_leaf()
2035 static int dc_check_balance(struct tree_balance *tb, int h) in dc_check_balance() argument
2037 RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)), in dc_check_balance()
2041 return dc_check_balance_internal(tb, h); in dc_check_balance()
2043 return dc_check_balance_leaf(tb, h); in dc_check_balance()
2066 struct tree_balance *tb, in check_balance() argument
2074 vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf); in check_balance()
2075 vn->vn_free_ptr = (char *)(tb->tb_vn + 1); in check_balance()
2086 if (tb->insert_size[h] > 0) in check_balance()
2087 return ip_check_balance(tb, h); in check_balance()
2090 return dc_check_balance(tb, h); in check_balance()
2094 static int get_direct_parent(struct tree_balance *tb, int h) in get_direct_parent() argument
2097 struct treepath *path = tb->tb_path; in get_direct_parent()
2099 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h); in get_direct_parent()
2108 b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) { in get_direct_parent()
2134 int depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_direct_parent()
2136 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_direct_parent()
2137 if (FILESYSTEM_CHANGED_TB(tb)) in get_direct_parent()
2155 static int get_neighbors(struct tree_balance *tb, int h) in get_neighbors() argument
2158 path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1); in get_neighbors()
2160 struct super_block *sb = tb->tb_sb; in get_neighbors()
2166 if (tb->lnum[h]) { in get_neighbors()
2169 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset); in get_neighbors()
2171 RFALSE(bh == tb->FL[h] && in get_neighbors()
2172 !PATH_OFFSET_POSITION(tb->tb_path, path_offset), in get_neighbors()
2177 tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb-> in get_neighbors()
2179 son_number = B_N_CHILD_NUM(tb->FL[h], child_position); in get_neighbors()
2180 depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_neighbors()
2182 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_neighbors()
2185 if (FILESYSTEM_CHANGED_TB(tb)) { in get_neighbors()
2191 RFALSE(!B_IS_IN_TREE(tb->FL[h]) || in get_neighbors()
2192 child_position > B_NR_ITEMS(tb->FL[h]) || in get_neighbors()
2193 B_N_CHILD_NUM(tb->FL[h], child_position) != in get_neighbors()
2199 dc_size(B_N_CHILD(tb->FL[0], child_position)), in get_neighbors()
2202 brelse(tb->L[h]); in get_neighbors()
2203 tb->L[h] = bh; in get_neighbors()
2207 if (tb->rnum[h]) { in get_neighbors()
2209 bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset); in get_neighbors()
2211 RFALSE(bh == tb->FR[h] && in get_neighbors()
2212 PATH_OFFSET_POSITION(tb->tb_path, in get_neighbors()
2218 (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0; in get_neighbors()
2219 son_number = B_N_CHILD_NUM(tb->FR[h], child_position); in get_neighbors()
2220 depth = reiserfs_write_unlock_nested(tb->tb_sb); in get_neighbors()
2222 reiserfs_write_lock_nested(tb->tb_sb, depth); in get_neighbors()
2225 if (FILESYSTEM_CHANGED_TB(tb)) { in get_neighbors()
2230 brelse(tb->R[h]); in get_neighbors()
2231 tb->R[h] = bh; in get_neighbors()
2236 dc_size(B_N_CHILD(tb->FR[0], child_position)), in get_neighbors()
2239 dc_size(B_N_CHILD(tb->FR[0], child_position))); in get_neighbors()
2268 static int get_mem_for_virtual_node(struct tree_balance *tb) in get_mem_for_virtual_node() argument
2274 size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path)); in get_mem_for_virtual_node()
2277 if (size > tb->vn_buf_size) { in get_mem_for_virtual_node()
2278 if (tb->vn_buf) { in get_mem_for_virtual_node()
2280 kfree(tb->vn_buf); in get_mem_for_virtual_node()
2286 tb->vn_buf_size = size; in get_mem_for_virtual_node()
2297 free_buffers_in_tb(tb); in get_mem_for_virtual_node()
2300 tb->vn_buf_size = 0; in get_mem_for_virtual_node()
2302 tb->vn_buf = buf; in get_mem_for_virtual_node()
2307 tb->vn_buf = buf; in get_mem_for_virtual_node()
2310 if (check_fs && FILESYSTEM_CHANGED_TB(tb)) in get_mem_for_virtual_node()
2367 static int wait_tb_buffers_until_unlocked(struct tree_balance *tb) in wait_tb_buffers_until_unlocked() argument
2379 for (i = tb->tb_path->path_length; in wait_tb_buffers_until_unlocked()
2381 if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) { in wait_tb_buffers_until_unlocked()
2388 if (PATH_PLAST_BUFFER(tb->tb_path) == in wait_tb_buffers_until_unlocked()
2389 PATH_OFFSET_PBUFFER(tb->tb_path, i)) in wait_tb_buffers_until_unlocked()
2390 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2392 (tb->tb_path, in wait_tb_buffers_until_unlocked()
2394 tb->tb_path-> in wait_tb_buffers_until_unlocked()
2397 if (!clear_all_dirty_bits(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2399 (tb->tb_path, in wait_tb_buffers_until_unlocked()
2402 PATH_OFFSET_PBUFFER(tb->tb_path, in wait_tb_buffers_until_unlocked()
2408 for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i]; in wait_tb_buffers_until_unlocked()
2411 if (tb->lnum[i]) { in wait_tb_buffers_until_unlocked()
2413 if (tb->L[i]) { in wait_tb_buffers_until_unlocked()
2414 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2415 tb->L[i], in wait_tb_buffers_until_unlocked()
2418 (tb->tb_sb, tb->L[i])) in wait_tb_buffers_until_unlocked()
2419 locked = tb->L[i]; in wait_tb_buffers_until_unlocked()
2422 if (!locked && tb->FL[i]) { in wait_tb_buffers_until_unlocked()
2423 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2424 tb->FL[i], in wait_tb_buffers_until_unlocked()
2427 (tb->tb_sb, tb->FL[i])) in wait_tb_buffers_until_unlocked()
2428 locked = tb->FL[i]; in wait_tb_buffers_until_unlocked()
2431 if (!locked && tb->CFL[i]) { in wait_tb_buffers_until_unlocked()
2432 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2433 tb->CFL[i], in wait_tb_buffers_until_unlocked()
2436 (tb->tb_sb, tb->CFL[i])) in wait_tb_buffers_until_unlocked()
2437 locked = tb->CFL[i]; in wait_tb_buffers_until_unlocked()
2442 if (!locked && (tb->rnum[i])) { in wait_tb_buffers_until_unlocked()
2444 if (tb->R[i]) { in wait_tb_buffers_until_unlocked()
2445 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2446 tb->R[i], in wait_tb_buffers_until_unlocked()
2449 (tb->tb_sb, tb->R[i])) in wait_tb_buffers_until_unlocked()
2450 locked = tb->R[i]; in wait_tb_buffers_until_unlocked()
2453 if (!locked && tb->FR[i]) { in wait_tb_buffers_until_unlocked()
2454 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2455 tb->FR[i], in wait_tb_buffers_until_unlocked()
2458 (tb->tb_sb, tb->FR[i])) in wait_tb_buffers_until_unlocked()
2459 locked = tb->FR[i]; in wait_tb_buffers_until_unlocked()
2462 if (!locked && tb->CFR[i]) { in wait_tb_buffers_until_unlocked()
2463 tb_buffer_sanity_check(tb->tb_sb, in wait_tb_buffers_until_unlocked()
2464 tb->CFR[i], in wait_tb_buffers_until_unlocked()
2467 (tb->tb_sb, tb->CFR[i])) in wait_tb_buffers_until_unlocked()
2468 locked = tb->CFR[i]; in wait_tb_buffers_until_unlocked()
2483 if (tb->FEB[i]) { in wait_tb_buffers_until_unlocked()
2485 (tb->tb_sb, tb->FEB[i])) in wait_tb_buffers_until_unlocked()
2486 locked = tb->FEB[i]; in wait_tb_buffers_until_unlocked()
2495 reiserfs_warning(tb->tb_sb, "reiserfs-8200", in wait_tb_buffers_until_unlocked()
2502 return (FILESYSTEM_CHANGED_TB(tb)) ? in wait_tb_buffers_until_unlocked()
2506 depth = reiserfs_write_unlock_nested(tb->tb_sb); in wait_tb_buffers_until_unlocked()
2508 reiserfs_write_lock_nested(tb->tb_sb, depth); in wait_tb_buffers_until_unlocked()
2509 if (FILESYSTEM_CHANGED_TB(tb)) in wait_tb_buffers_until_unlocked()
2549 int fix_nodes(int op_mode, struct tree_balance *tb, in fix_nodes() argument
2552 int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path); in fix_nodes()
2560 struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path); in fix_nodes()
2562 ++REISERFS_SB(tb->tb_sb)->s_fix_nodes; in fix_nodes()
2564 pos_in_item = tb->tb_path->pos_in_item; in fix_nodes()
2566 tb->fs_gen = get_generation(tb->tb_sb); in fix_nodes()
2574 reiserfs_prepare_for_journal(tb->tb_sb, in fix_nodes()
2575 SB_BUFFER_WITH_SB(tb->tb_sb), 1); in fix_nodes()
2576 journal_mark_dirty(tb->transaction_handle, in fix_nodes()
2577 SB_BUFFER_WITH_SB(tb->tb_sb)); in fix_nodes()
2578 if (FILESYSTEM_CHANGED_TB(tb)) in fix_nodes()
2583 int depth = reiserfs_write_unlock_nested(tb->tb_sb); in fix_nodes()
2585 reiserfs_write_lock_nested(tb->tb_sb, depth); in fix_nodes()
2586 if (FILESYSTEM_CHANGED_TB(tb)) in fix_nodes()
2590 if (REISERFS_SB(tb->tb_sb)->cur_tb) { in fix_nodes()
2592 reiserfs_panic(tb->tb_sb, "PAP-8305", in fix_nodes()
2597 reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is " in fix_nodes()
2606 reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect " in fix_nodes()
2616 reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect " in fix_nodes()
2620 tb->insert_size[0]); in fix_nodes()
2624 reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode " in fix_nodes()
2629 if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH) in fix_nodes()
2634 for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) { in fix_nodes()
2635 ret = get_direct_parent(tb, h); in fix_nodes()
2639 ret = check_balance(op_mode, tb, h, item_num, in fix_nodes()
2644 ret = get_neighbors(tb, h); in fix_nodes()
2648 tb->insert_size[h + 1] = 0; in fix_nodes()
2658 ret = get_neighbors(tb, h); in fix_nodes()
2666 ret = get_empty_nodes(tb, h); in fix_nodes()
2674 if (!PATH_H_PBUFFER(tb->tb_path, h)) { in fix_nodes()
2676 RFALSE(tb->blknum[h] != 1, in fix_nodes()
2680 tb->insert_size[h + 1] = 0; in fix_nodes()
2681 } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) { in fix_nodes()
2688 if (tb->blknum[h] > 1) { in fix_nodes()
2693 tb->insert_size[h + 1] = in fix_nodes()
2695 KEY_SIZE) * (tb->blknum[h] - 1) + in fix_nodes()
2698 tb->insert_size[h + 1] = 0; in fix_nodes()
2700 tb->insert_size[h + 1] = in fix_nodes()
2701 (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1); in fix_nodes()
2704 ret = wait_tb_buffers_until_unlocked(tb); in fix_nodes()
2706 if (FILESYSTEM_CHANGED_TB(tb)) { in fix_nodes()
2731 pathrelse_and_restore(tb->tb_sb, tb->tb_path); in fix_nodes()
2733 pathrelse(tb->tb_path); in fix_nodes()
2738 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2739 tb->L[i]); in fix_nodes()
2740 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2741 tb->R[i]); in fix_nodes()
2742 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2743 tb->FL[i]); in fix_nodes()
2744 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2745 tb->FR[i]); in fix_nodes()
2746 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2747 tb-> in fix_nodes()
2749 reiserfs_restore_prepared_buffer(tb->tb_sb, in fix_nodes()
2750 tb-> in fix_nodes()
2754 brelse(tb->L[i]); in fix_nodes()
2755 brelse(tb->R[i]); in fix_nodes()
2756 brelse(tb->FL[i]); in fix_nodes()
2757 brelse(tb->FR[i]); in fix_nodes()
2758 brelse(tb->CFL[i]); in fix_nodes()
2759 brelse(tb->CFR[i]); in fix_nodes()
2761 tb->L[i] = NULL; in fix_nodes()
2762 tb->R[i] = NULL; in fix_nodes()
2763 tb->FL[i] = NULL; in fix_nodes()
2764 tb->FR[i] = NULL; in fix_nodes()
2765 tb->CFL[i] = NULL; in fix_nodes()
2766 tb->CFR[i] = NULL; in fix_nodes()
2771 if (tb->FEB[i]) in fix_nodes()
2773 (tb->tb_sb, tb->FEB[i]); in fix_nodes()
2781 void unfix_nodes(struct tree_balance *tb) in unfix_nodes() argument
2786 pathrelse_and_restore(tb->tb_sb, tb->tb_path); in unfix_nodes()
2790 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]); in unfix_nodes()
2791 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]); in unfix_nodes()
2792 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]); in unfix_nodes()
2793 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]); in unfix_nodes()
2794 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]); in unfix_nodes()
2795 reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]); in unfix_nodes()
2797 brelse(tb->L[i]); in unfix_nodes()
2798 brelse(tb->R[i]); in unfix_nodes()
2799 brelse(tb->FL[i]); in unfix_nodes()
2800 brelse(tb->FR[i]); in unfix_nodes()
2801 brelse(tb->CFL[i]); in unfix_nodes()
2802 brelse(tb->CFR[i]); in unfix_nodes()
2807 if (tb->FEB[i]) { in unfix_nodes()
2808 b_blocknr_t blocknr = tb->FEB[i]->b_blocknr; in unfix_nodes()
2813 brelse(tb->FEB[i]); in unfix_nodes()
2814 reiserfs_free_block(tb->transaction_handle, NULL, in unfix_nodes()
2817 if (tb->used[i]) { in unfix_nodes()
2819 brelse(tb->used[i]); in unfix_nodes()
2823 kfree(tb->vn_buf); in unfix_nodes()