11da177e4SLinus Torvalds /*
21da177e4SLinus Torvalds * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
31da177e4SLinus Torvalds */
41da177e4SLinus Torvalds
51da177e4SLinus Torvalds #include <linux/time.h>
65a0e3ad6STejun Heo #include <linux/slab.h>
71da177e4SLinus Torvalds #include <linux/string.h>
8f466c6fdSAl Viro #include "reiserfs.h"
91da177e4SLinus Torvalds #include <linux/buffer_head.h>
101da177e4SLinus Torvalds
11098297b2SJeff Mahoney /*
12098297b2SJeff Mahoney * To make any changes in the tree we find a node that contains item
13098297b2SJeff Mahoney * to be changed/deleted or position in the node we insert a new item
14098297b2SJeff Mahoney * to. We call this node S. To do balancing we need to decide what we
15098297b2SJeff Mahoney * will shift to left/right neighbor, or to a new node, where new item
16098297b2SJeff Mahoney * will be etc. To make this analysis simpler we build virtual
17098297b2SJeff Mahoney * node. Virtual node is an array of items, that will replace items of
18098297b2SJeff Mahoney * node S. (For instance if we are going to delete an item, virtual
19098297b2SJeff Mahoney * node does not contain it). Virtual node keeps information about
20098297b2SJeff Mahoney * item sizes and types, mergeability of first and last items, sizes
21098297b2SJeff Mahoney * of all entries in directory item. We use this array of items when
22098297b2SJeff Mahoney * calculating what we can shift to neighbors and how many nodes we
23098297b2SJeff Mahoney * have to have if we do not any shiftings, if we shift to left/right
24098297b2SJeff Mahoney * neighbor or to both.
25098297b2SJeff Mahoney */
261da177e4SLinus Torvalds
27098297b2SJeff Mahoney /*
28098297b2SJeff Mahoney * Takes item number in virtual node, returns number of item
29098297b2SJeff Mahoney * that it has in source buffer
30098297b2SJeff Mahoney */
old_item_num(int new_num,int affected_item_num,int mode)311da177e4SLinus Torvalds static inline int old_item_num(int new_num, int affected_item_num, int mode)
321da177e4SLinus Torvalds {
331da177e4SLinus Torvalds if (mode == M_PASTE || mode == M_CUT || new_num < affected_item_num)
341da177e4SLinus Torvalds return new_num;
351da177e4SLinus Torvalds
361da177e4SLinus Torvalds if (mode == M_INSERT) {
371da177e4SLinus Torvalds
381da177e4SLinus Torvalds RFALSE(new_num == 0,
391da177e4SLinus Torvalds "vs-8005: for INSERT mode and item number of inserted item");
401da177e4SLinus Torvalds
411da177e4SLinus Torvalds return new_num - 1;
421da177e4SLinus Torvalds }
431da177e4SLinus Torvalds
441da177e4SLinus Torvalds RFALSE(mode != M_DELETE,
45bd4c625cSLinus Torvalds "vs-8010: old_item_num: mode must be M_DELETE (mode = \'%c\'",
46bd4c625cSLinus Torvalds mode);
471da177e4SLinus Torvalds /* delete mode */
481da177e4SLinus Torvalds return new_num + 1;
491da177e4SLinus Torvalds }
501da177e4SLinus Torvalds
create_virtual_node(struct tree_balance * tb,int h)511da177e4SLinus Torvalds static void create_virtual_node(struct tree_balance *tb, int h)
521da177e4SLinus Torvalds {
531da177e4SLinus Torvalds struct item_head *ih;
541da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
551da177e4SLinus Torvalds int new_num;
561da177e4SLinus Torvalds struct buffer_head *Sh; /* this comes from tb->S[h] */
571da177e4SLinus Torvalds
581da177e4SLinus Torvalds Sh = PATH_H_PBUFFER(tb->tb_path, h);
591da177e4SLinus Torvalds
601da177e4SLinus Torvalds /* size of changed node */
61bd4c625cSLinus Torvalds vn->vn_size =
62bd4c625cSLinus Torvalds MAX_CHILD_SIZE(Sh) - B_FREE_SPACE(Sh) + tb->insert_size[h];
631da177e4SLinus Torvalds
641da177e4SLinus Torvalds /* for internal nodes array if virtual items is not created */
651da177e4SLinus Torvalds if (h) {
661da177e4SLinus Torvalds vn->vn_nr_item = (vn->vn_size - DC_SIZE) / (DC_SIZE + KEY_SIZE);
671da177e4SLinus Torvalds return;
681da177e4SLinus Torvalds }
691da177e4SLinus Torvalds
701da177e4SLinus Torvalds /* number of items in virtual node */
71bd4c625cSLinus Torvalds vn->vn_nr_item =
72bd4c625cSLinus Torvalds B_NR_ITEMS(Sh) + ((vn->vn_mode == M_INSERT) ? 1 : 0) -
73bd4c625cSLinus Torvalds ((vn->vn_mode == M_DELETE) ? 1 : 0);
741da177e4SLinus Torvalds
751da177e4SLinus Torvalds /* first virtual item */
761da177e4SLinus Torvalds vn->vn_vi = (struct virtual_item *)(tb->tb_vn + 1);
771da177e4SLinus Torvalds memset(vn->vn_vi, 0, vn->vn_nr_item * sizeof(struct virtual_item));
781da177e4SLinus Torvalds vn->vn_free_ptr += vn->vn_nr_item * sizeof(struct virtual_item);
791da177e4SLinus Torvalds
801da177e4SLinus Torvalds /* first item in the node */
814cf5f7adSJeff Mahoney ih = item_head(Sh, 0);
821da177e4SLinus Torvalds
831da177e4SLinus Torvalds /* define the mergeability for 0-th item (if it is not being deleted) */
84a228bf8fSJeff Mahoney if (op_is_left_mergeable(&ih->ih_key, Sh->b_size)
85bd4c625cSLinus Torvalds && (vn->vn_mode != M_DELETE || vn->vn_affected_item_num))
861da177e4SLinus Torvalds vn->vn_vi[0].vi_type |= VI_TYPE_LEFT_MERGEABLE;
871da177e4SLinus Torvalds
88098297b2SJeff Mahoney /*
89098297b2SJeff Mahoney * go through all items that remain in the virtual
90098297b2SJeff Mahoney * node (except for the new (inserted) one)
91098297b2SJeff Mahoney */
921da177e4SLinus Torvalds for (new_num = 0; new_num < vn->vn_nr_item; new_num++) {
931da177e4SLinus Torvalds int j;
941da177e4SLinus Torvalds struct virtual_item *vi = vn->vn_vi + new_num;
95bd4c625cSLinus Torvalds int is_affected =
96bd4c625cSLinus Torvalds ((new_num != vn->vn_affected_item_num) ? 0 : 1);
971da177e4SLinus Torvalds
981da177e4SLinus Torvalds if (is_affected && vn->vn_mode == M_INSERT)
991da177e4SLinus Torvalds continue;
1001da177e4SLinus Torvalds
1011da177e4SLinus Torvalds /* get item number in source node */
102bd4c625cSLinus Torvalds j = old_item_num(new_num, vn->vn_affected_item_num,
103bd4c625cSLinus Torvalds vn->vn_mode);
1041da177e4SLinus Torvalds
1051da177e4SLinus Torvalds vi->vi_item_len += ih_item_len(ih + j) + IH_SIZE;
1061da177e4SLinus Torvalds vi->vi_ih = ih + j;
1074cf5f7adSJeff Mahoney vi->vi_item = ih_item_body(Sh, ih + j);
1081da177e4SLinus Torvalds vi->vi_uarea = vn->vn_free_ptr;
1091da177e4SLinus Torvalds
110098297b2SJeff Mahoney /*
111098297b2SJeff Mahoney * FIXME: there is no check that item operation did not
112098297b2SJeff Mahoney * consume too much memory
113098297b2SJeff Mahoney */
114bd4c625cSLinus Torvalds vn->vn_free_ptr +=
115bd4c625cSLinus Torvalds op_create_vi(vn, vi, is_affected, tb->insert_size[0]);
1161da177e4SLinus Torvalds if (tb->vn_buf + tb->vn_buf_size < vn->vn_free_ptr)
117c3a9c210SJeff Mahoney reiserfs_panic(tb->tb_sb, "vs-8030",
1181da177e4SLinus Torvalds "virtual node space consumed");
1191da177e4SLinus Torvalds
1201da177e4SLinus Torvalds if (!is_affected)
1211da177e4SLinus Torvalds /* this is not being changed */
1221da177e4SLinus Torvalds continue;
1231da177e4SLinus Torvalds
1241da177e4SLinus Torvalds if (vn->vn_mode == M_PASTE || vn->vn_mode == M_CUT) {
1251da177e4SLinus Torvalds vn->vn_vi[new_num].vi_item_len += tb->insert_size[0];
126098297b2SJeff Mahoney /* pointer to data which is going to be pasted */
127098297b2SJeff Mahoney vi->vi_new_data = vn->vn_data;
1281da177e4SLinus Torvalds }
1291da177e4SLinus Torvalds }
1301da177e4SLinus Torvalds
1311da177e4SLinus Torvalds /* virtual inserted item is not defined yet */
1321da177e4SLinus Torvalds if (vn->vn_mode == M_INSERT) {
1331da177e4SLinus Torvalds struct virtual_item *vi = vn->vn_vi + vn->vn_affected_item_num;
1341da177e4SLinus Torvalds
1359dce07f1SAl Viro RFALSE(vn->vn_ins_ih == NULL,
1361da177e4SLinus Torvalds "vs-8040: item header of inserted item is not specified");
1371da177e4SLinus Torvalds vi->vi_item_len = tb->insert_size[0];
1381da177e4SLinus Torvalds vi->vi_ih = vn->vn_ins_ih;
1391da177e4SLinus Torvalds vi->vi_item = vn->vn_data;
1401da177e4SLinus Torvalds vi->vi_uarea = vn->vn_free_ptr;
1411da177e4SLinus Torvalds
142bd4c625cSLinus Torvalds op_create_vi(vn, vi, 0 /*not pasted or cut */ ,
143bd4c625cSLinus Torvalds tb->insert_size[0]);
1441da177e4SLinus Torvalds }
1451da177e4SLinus Torvalds
146098297b2SJeff Mahoney /*
147098297b2SJeff Mahoney * set right merge flag we take right delimiting key and
148098297b2SJeff Mahoney * check whether it is a mergeable item
149098297b2SJeff Mahoney */
1501da177e4SLinus Torvalds if (tb->CFR[0]) {
1511da177e4SLinus Torvalds struct reiserfs_key *key;
1521da177e4SLinus Torvalds
1534cf5f7adSJeff Mahoney key = internal_key(tb->CFR[0], tb->rkey[0]);
154bd4c625cSLinus Torvalds if (op_is_left_mergeable(key, Sh->b_size)
155bd4c625cSLinus Torvalds && (vn->vn_mode != M_DELETE
156bd4c625cSLinus Torvalds || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1))
157bd4c625cSLinus Torvalds vn->vn_vi[vn->vn_nr_item - 1].vi_type |=
158bd4c625cSLinus Torvalds VI_TYPE_RIGHT_MERGEABLE;
1591da177e4SLinus Torvalds
1601da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK
1611da177e4SLinus Torvalds if (op_is_left_mergeable(key, Sh->b_size) &&
162bd4c625cSLinus Torvalds !(vn->vn_mode != M_DELETE
163bd4c625cSLinus Torvalds || vn->vn_affected_item_num != B_NR_ITEMS(Sh) - 1)) {
164098297b2SJeff Mahoney /*
165098297b2SJeff Mahoney * we delete last item and it could be merged
166098297b2SJeff Mahoney * with right neighbor's first item
167098297b2SJeff Mahoney */
168bd4c625cSLinus Torvalds if (!
169bd4c625cSLinus Torvalds (B_NR_ITEMS(Sh) == 1
1704cf5f7adSJeff Mahoney && is_direntry_le_ih(item_head(Sh, 0))
1714cf5f7adSJeff Mahoney && ih_entry_count(item_head(Sh, 0)) == 1)) {
172098297b2SJeff Mahoney /*
173098297b2SJeff Mahoney * node contains more than 1 item, or item
174098297b2SJeff Mahoney * is not directory item, or this item
175098297b2SJeff Mahoney * contains more than 1 entry
176098297b2SJeff Mahoney */
1771da177e4SLinus Torvalds print_block(Sh, 0, -1, -1);
178c3a9c210SJeff Mahoney reiserfs_panic(tb->tb_sb, "vs-8045",
179c3a9c210SJeff Mahoney "rdkey %k, affected item==%d "
180c3a9c210SJeff Mahoney "(mode==%c) Must be %c",
181bd4c625cSLinus Torvalds key, vn->vn_affected_item_num,
182bd4c625cSLinus Torvalds vn->vn_mode, M_DELETE);
183cd02b966SVladimir V. Saveliev }
1841da177e4SLinus Torvalds }
1851da177e4SLinus Torvalds #endif
1861da177e4SLinus Torvalds
1871da177e4SLinus Torvalds }
1881da177e4SLinus Torvalds }
1891da177e4SLinus Torvalds
190098297b2SJeff Mahoney /*
191098297b2SJeff Mahoney * Using virtual node check, how many items can be
192098297b2SJeff Mahoney * shifted to left neighbor
193098297b2SJeff Mahoney */
check_left(struct tree_balance * tb,int h,int cur_free)1941da177e4SLinus Torvalds static void check_left(struct tree_balance *tb, int h, int cur_free)
1951da177e4SLinus Torvalds {
1961da177e4SLinus Torvalds int i;
1971da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
1981da177e4SLinus Torvalds struct virtual_item *vi;
1991da177e4SLinus Torvalds int d_size, ih_size;
2001da177e4SLinus Torvalds
2011da177e4SLinus Torvalds RFALSE(cur_free < 0, "vs-8050: cur_free (%d) < 0", cur_free);
2021da177e4SLinus Torvalds
2031da177e4SLinus Torvalds /* internal level */
2041da177e4SLinus Torvalds if (h > 0) {
2051da177e4SLinus Torvalds tb->lnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
2061da177e4SLinus Torvalds return;
2071da177e4SLinus Torvalds }
2081da177e4SLinus Torvalds
2091da177e4SLinus Torvalds /* leaf level */
2101da177e4SLinus Torvalds
2111da177e4SLinus Torvalds if (!cur_free || !vn->vn_nr_item) {
2121da177e4SLinus Torvalds /* no free space or nothing to move */
2131da177e4SLinus Torvalds tb->lnum[h] = 0;
2141da177e4SLinus Torvalds tb->lbytes = -1;
2151da177e4SLinus Torvalds return;
2161da177e4SLinus Torvalds }
2171da177e4SLinus Torvalds
2181da177e4SLinus Torvalds RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
2191da177e4SLinus Torvalds "vs-8055: parent does not exist or invalid");
2201da177e4SLinus Torvalds
2211da177e4SLinus Torvalds vi = vn->vn_vi;
222bd4c625cSLinus Torvalds if ((unsigned int)cur_free >=
223bd4c625cSLinus Torvalds (vn->vn_size -
224bd4c625cSLinus Torvalds ((vi->vi_type & VI_TYPE_LEFT_MERGEABLE) ? IH_SIZE : 0))) {
2251da177e4SLinus Torvalds /* all contents of S[0] fits into L[0] */
2261da177e4SLinus Torvalds
2271da177e4SLinus Torvalds RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
2281da177e4SLinus Torvalds "vs-8055: invalid mode or balance condition failed");
2291da177e4SLinus Torvalds
2301da177e4SLinus Torvalds tb->lnum[0] = vn->vn_nr_item;
2311da177e4SLinus Torvalds tb->lbytes = -1;
2321da177e4SLinus Torvalds return;
2331da177e4SLinus Torvalds }
2341da177e4SLinus Torvalds
2351da177e4SLinus Torvalds d_size = 0, ih_size = IH_SIZE;
2361da177e4SLinus Torvalds
2371da177e4SLinus Torvalds /* first item may be merge with last item in left neighbor */
2381da177e4SLinus Torvalds if (vi->vi_type & VI_TYPE_LEFT_MERGEABLE)
2391da177e4SLinus Torvalds d_size = -((int)IH_SIZE), ih_size = 0;
2401da177e4SLinus Torvalds
2411da177e4SLinus Torvalds tb->lnum[0] = 0;
242bd4c625cSLinus Torvalds for (i = 0; i < vn->vn_nr_item;
243bd4c625cSLinus Torvalds i++, ih_size = IH_SIZE, d_size = 0, vi++) {
2441da177e4SLinus Torvalds d_size += vi->vi_item_len;
2451da177e4SLinus Torvalds if (cur_free >= d_size) {
2461da177e4SLinus Torvalds /* the item can be shifted entirely */
2471da177e4SLinus Torvalds cur_free -= d_size;
2481da177e4SLinus Torvalds tb->lnum[0]++;
2491da177e4SLinus Torvalds continue;
2501da177e4SLinus Torvalds }
2511da177e4SLinus Torvalds
2521da177e4SLinus Torvalds /* the item cannot be shifted entirely, try to split it */
253098297b2SJeff Mahoney /*
254098297b2SJeff Mahoney * check whether L[0] can hold ih and at least one byte
255098297b2SJeff Mahoney * of the item body
256098297b2SJeff Mahoney */
257098297b2SJeff Mahoney
2581da177e4SLinus Torvalds /* cannot shift even a part of the current item */
259098297b2SJeff Mahoney if (cur_free <= ih_size) {
2601da177e4SLinus Torvalds tb->lbytes = -1;
2611da177e4SLinus Torvalds return;
2621da177e4SLinus Torvalds }
2631da177e4SLinus Torvalds cur_free -= ih_size;
2641da177e4SLinus Torvalds
2651da177e4SLinus Torvalds tb->lbytes = op_check_left(vi, cur_free, 0, 0);
2661da177e4SLinus Torvalds if (tb->lbytes != -1)
2671da177e4SLinus Torvalds /* count partially shifted item */
2681da177e4SLinus Torvalds tb->lnum[0]++;
2691da177e4SLinus Torvalds
2701da177e4SLinus Torvalds break;
2711da177e4SLinus Torvalds }
2721da177e4SLinus Torvalds
2731da177e4SLinus Torvalds return;
2741da177e4SLinus Torvalds }
2751da177e4SLinus Torvalds
276098297b2SJeff Mahoney /*
277098297b2SJeff Mahoney * Using virtual node check, how many items can be
278098297b2SJeff Mahoney * shifted to right neighbor
279098297b2SJeff Mahoney */
check_right(struct tree_balance * tb,int h,int cur_free)2801da177e4SLinus Torvalds static void check_right(struct tree_balance *tb, int h, int cur_free)
2811da177e4SLinus Torvalds {
2821da177e4SLinus Torvalds int i;
2831da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
2841da177e4SLinus Torvalds struct virtual_item *vi;
2851da177e4SLinus Torvalds int d_size, ih_size;
2861da177e4SLinus Torvalds
2871da177e4SLinus Torvalds RFALSE(cur_free < 0, "vs-8070: cur_free < 0");
2881da177e4SLinus Torvalds
2891da177e4SLinus Torvalds /* internal level */
2901da177e4SLinus Torvalds if (h > 0) {
2911da177e4SLinus Torvalds tb->rnum[h] = cur_free / (DC_SIZE + KEY_SIZE);
2921da177e4SLinus Torvalds return;
2931da177e4SLinus Torvalds }
2941da177e4SLinus Torvalds
2951da177e4SLinus Torvalds /* leaf level */
2961da177e4SLinus Torvalds
2971da177e4SLinus Torvalds if (!cur_free || !vn->vn_nr_item) {
2981da177e4SLinus Torvalds /* no free space */
2991da177e4SLinus Torvalds tb->rnum[h] = 0;
3001da177e4SLinus Torvalds tb->rbytes = -1;
3011da177e4SLinus Torvalds return;
3021da177e4SLinus Torvalds }
3031da177e4SLinus Torvalds
3041da177e4SLinus Torvalds RFALSE(!PATH_H_PPARENT(tb->tb_path, 0),
3051da177e4SLinus Torvalds "vs-8075: parent does not exist or invalid");
3061da177e4SLinus Torvalds
3071da177e4SLinus Torvalds vi = vn->vn_vi + vn->vn_nr_item - 1;
308bd4c625cSLinus Torvalds if ((unsigned int)cur_free >=
309bd4c625cSLinus Torvalds (vn->vn_size -
310bd4c625cSLinus Torvalds ((vi->vi_type & VI_TYPE_RIGHT_MERGEABLE) ? IH_SIZE : 0))) {
3111da177e4SLinus Torvalds /* all contents of S[0] fits into R[0] */
3121da177e4SLinus Torvalds
3131da177e4SLinus Torvalds RFALSE(vn->vn_mode == M_INSERT || vn->vn_mode == M_PASTE,
3141da177e4SLinus Torvalds "vs-8080: invalid mode or balance condition failed");
3151da177e4SLinus Torvalds
3161da177e4SLinus Torvalds tb->rnum[h] = vn->vn_nr_item;
3171da177e4SLinus Torvalds tb->rbytes = -1;
3181da177e4SLinus Torvalds return;
3191da177e4SLinus Torvalds }
3201da177e4SLinus Torvalds
3211da177e4SLinus Torvalds d_size = 0, ih_size = IH_SIZE;
3221da177e4SLinus Torvalds
3231da177e4SLinus Torvalds /* last item may be merge with first item in right neighbor */
3241da177e4SLinus Torvalds if (vi->vi_type & VI_TYPE_RIGHT_MERGEABLE)
3251da177e4SLinus Torvalds d_size = -(int)IH_SIZE, ih_size = 0;
3261da177e4SLinus Torvalds
3271da177e4SLinus Torvalds tb->rnum[0] = 0;
328bd4c625cSLinus Torvalds for (i = vn->vn_nr_item - 1; i >= 0;
329bd4c625cSLinus Torvalds i--, d_size = 0, ih_size = IH_SIZE, vi--) {
3301da177e4SLinus Torvalds d_size += vi->vi_item_len;
3311da177e4SLinus Torvalds if (cur_free >= d_size) {
3321da177e4SLinus Torvalds /* the item can be shifted entirely */
3331da177e4SLinus Torvalds cur_free -= d_size;
3341da177e4SLinus Torvalds tb->rnum[0]++;
3351da177e4SLinus Torvalds continue;
3361da177e4SLinus Torvalds }
3371da177e4SLinus Torvalds
338098297b2SJeff Mahoney /*
339098297b2SJeff Mahoney * check whether R[0] can hold ih and at least one
340098297b2SJeff Mahoney * byte of the item body
341098297b2SJeff Mahoney */
342098297b2SJeff Mahoney
343098297b2SJeff Mahoney /* cannot shift even a part of the current item */
344098297b2SJeff Mahoney if (cur_free <= ih_size) {
3451da177e4SLinus Torvalds tb->rbytes = -1;
3461da177e4SLinus Torvalds return;
3471da177e4SLinus Torvalds }
3481da177e4SLinus Torvalds
349098297b2SJeff Mahoney /*
350098297b2SJeff Mahoney * R[0] can hold the header of the item and at least
351098297b2SJeff Mahoney * one byte of its body
352098297b2SJeff Mahoney */
3531da177e4SLinus Torvalds cur_free -= ih_size; /* cur_free is still > 0 */
3541da177e4SLinus Torvalds
3551da177e4SLinus Torvalds tb->rbytes = op_check_right(vi, cur_free);
3561da177e4SLinus Torvalds if (tb->rbytes != -1)
3571da177e4SLinus Torvalds /* count partially shifted item */
3581da177e4SLinus Torvalds tb->rnum[0]++;
3591da177e4SLinus Torvalds
3601da177e4SLinus Torvalds break;
3611da177e4SLinus Torvalds }
3621da177e4SLinus Torvalds
3631da177e4SLinus Torvalds return;
3641da177e4SLinus Torvalds }
3651da177e4SLinus Torvalds
3661da177e4SLinus Torvalds /*
3671da177e4SLinus Torvalds * from - number of items, which are shifted to left neighbor entirely
3681da177e4SLinus Torvalds * to - number of item, which are shifted to right neighbor entirely
369098297b2SJeff Mahoney * from_bytes - number of bytes of boundary item (or directory entries)
370098297b2SJeff Mahoney * which are shifted to left neighbor
371098297b2SJeff Mahoney * to_bytes - number of bytes of boundary item (or directory entries)
372098297b2SJeff Mahoney * which are shifted to right neighbor
373098297b2SJeff Mahoney */
get_num_ver(int mode,struct tree_balance * tb,int h,int from,int from_bytes,int to,int to_bytes,short * snum012,int flow)3741da177e4SLinus Torvalds static int get_num_ver(int mode, struct tree_balance *tb, int h,
3751da177e4SLinus Torvalds int from, int from_bytes,
376bd4c625cSLinus Torvalds int to, int to_bytes, short *snum012, int flow)
3771da177e4SLinus Torvalds {
3781da177e4SLinus Torvalds int i;
3791da177e4SLinus Torvalds int units;
3801da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
3811da177e4SLinus Torvalds int total_node_size, max_node_size, current_item_size;
3821da177e4SLinus Torvalds int needed_nodes;
383098297b2SJeff Mahoney
384098297b2SJeff Mahoney /* position of item we start filling node from */
385098297b2SJeff Mahoney int start_item;
386098297b2SJeff Mahoney
387098297b2SJeff Mahoney /* position of item we finish filling node by */
388098297b2SJeff Mahoney int end_item;
389098297b2SJeff Mahoney
390098297b2SJeff Mahoney /*
391098297b2SJeff Mahoney * number of first bytes (entries for directory) of start_item-th item
392098297b2SJeff Mahoney * we do not include into node that is being filled
393098297b2SJeff Mahoney */
394098297b2SJeff Mahoney int start_bytes;
395098297b2SJeff Mahoney
396098297b2SJeff Mahoney /*
397098297b2SJeff Mahoney * number of last bytes (entries for directory) of end_item-th item
398098297b2SJeff Mahoney * we do node include into node that is being filled
399098297b2SJeff Mahoney */
400098297b2SJeff Mahoney int end_bytes;
401098297b2SJeff Mahoney
402098297b2SJeff Mahoney /*
403098297b2SJeff Mahoney * these are positions in virtual item of items, that are split
404098297b2SJeff Mahoney * between S[0] and S1new and S1new and S2new
405098297b2SJeff Mahoney */
406098297b2SJeff Mahoney int split_item_positions[2];
4071da177e4SLinus Torvalds
4081da177e4SLinus Torvalds split_item_positions[0] = -1;
4091da177e4SLinus Torvalds split_item_positions[1] = -1;
4101da177e4SLinus Torvalds
411098297b2SJeff Mahoney /*
412098297b2SJeff Mahoney * We only create additional nodes if we are in insert or paste mode
413098297b2SJeff Mahoney * or we are in replace mode at the internal level. If h is 0 and
414098297b2SJeff Mahoney * the mode is M_REPLACE then in fix_nodes we change the mode to
415098297b2SJeff Mahoney * paste or insert before we get here in the code.
416098297b2SJeff Mahoney */
4171da177e4SLinus Torvalds RFALSE(tb->insert_size[h] < 0 || (mode != M_INSERT && mode != M_PASTE),
4181da177e4SLinus Torvalds "vs-8100: insert_size < 0 in overflow");
4191da177e4SLinus Torvalds
4201da177e4SLinus Torvalds max_node_size = MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, h));
4211da177e4SLinus Torvalds
422098297b2SJeff Mahoney /*
423098297b2SJeff Mahoney * snum012 [0-2] - number of items, that lay
424098297b2SJeff Mahoney * to S[0], first new node and second new node
425098297b2SJeff Mahoney */
4261da177e4SLinus Torvalds snum012[3] = -1; /* s1bytes */
4271da177e4SLinus Torvalds snum012[4] = -1; /* s2bytes */
4281da177e4SLinus Torvalds
4291da177e4SLinus Torvalds /* internal level */
4301da177e4SLinus Torvalds if (h > 0) {
4311da177e4SLinus Torvalds i = ((to - from) * (KEY_SIZE + DC_SIZE) + DC_SIZE);
4321da177e4SLinus Torvalds if (i == max_node_size)
4331da177e4SLinus Torvalds return 1;
4341da177e4SLinus Torvalds return (i / max_node_size + 1);
4351da177e4SLinus Torvalds }
4361da177e4SLinus Torvalds
4371da177e4SLinus Torvalds /* leaf level */
4381da177e4SLinus Torvalds needed_nodes = 1;
4391da177e4SLinus Torvalds total_node_size = 0;
4401da177e4SLinus Torvalds
441098297b2SJeff Mahoney /* start from 'from'-th item */
4421da177e4SLinus Torvalds start_item = from;
443098297b2SJeff Mahoney /* skip its first 'start_bytes' units */
4441da177e4SLinus Torvalds start_bytes = ((from_bytes != -1) ? from_bytes : 0);
4451da177e4SLinus Torvalds
446098297b2SJeff Mahoney /* last included item is the 'end_item'-th one */
4471da177e4SLinus Torvalds end_item = vn->vn_nr_item - to - 1;
448098297b2SJeff Mahoney /* do not count last 'end_bytes' units of 'end_item'-th item */
4491da177e4SLinus Torvalds end_bytes = (to_bytes != -1) ? to_bytes : 0;
4501da177e4SLinus Torvalds
451098297b2SJeff Mahoney /*
452098297b2SJeff Mahoney * go through all item beginning from the start_item-th item
453098297b2SJeff Mahoney * and ending by the end_item-th item. Do not count first
454098297b2SJeff Mahoney * 'start_bytes' units of 'start_item'-th item and last
455098297b2SJeff Mahoney * 'end_bytes' of 'end_item'-th item
456098297b2SJeff Mahoney */
4571da177e4SLinus Torvalds for (i = start_item; i <= end_item; i++) {
4581da177e4SLinus Torvalds struct virtual_item *vi = vn->vn_vi + i;
4591da177e4SLinus Torvalds int skip_from_end = ((i == end_item) ? end_bytes : 0);
4601da177e4SLinus Torvalds
4611da177e4SLinus Torvalds RFALSE(needed_nodes > 3, "vs-8105: too many nodes are needed");
4621da177e4SLinus Torvalds
4631da177e4SLinus Torvalds /* get size of current item */
4641da177e4SLinus Torvalds current_item_size = vi->vi_item_len;
4651da177e4SLinus Torvalds
466098297b2SJeff Mahoney /*
467098297b2SJeff Mahoney * do not take in calculation head part (from_bytes)
468098297b2SJeff Mahoney * of from-th item
469098297b2SJeff Mahoney */
470bd4c625cSLinus Torvalds current_item_size -=
471bd4c625cSLinus Torvalds op_part_size(vi, 0 /*from start */ , start_bytes);
4721da177e4SLinus Torvalds
4731da177e4SLinus Torvalds /* do not take in calculation tail part of last item */
474bd4c625cSLinus Torvalds current_item_size -=
475bd4c625cSLinus Torvalds op_part_size(vi, 1 /*from end */ , skip_from_end);
4761da177e4SLinus Torvalds
4771da177e4SLinus Torvalds /* if item fits into current node entierly */
4781da177e4SLinus Torvalds if (total_node_size + current_item_size <= max_node_size) {
4791da177e4SLinus Torvalds snum012[needed_nodes - 1]++;
4801da177e4SLinus Torvalds total_node_size += current_item_size;
4811da177e4SLinus Torvalds start_bytes = 0;
4821da177e4SLinus Torvalds continue;
4831da177e4SLinus Torvalds }
4841da177e4SLinus Torvalds
485098297b2SJeff Mahoney /*
486098297b2SJeff Mahoney * virtual item length is longer, than max size of item in
487098297b2SJeff Mahoney * a node. It is impossible for direct item
488098297b2SJeff Mahoney */
4891da177e4SLinus Torvalds if (current_item_size > max_node_size) {
4901da177e4SLinus Torvalds RFALSE(is_direct_le_ih(vi->vi_ih),
4911da177e4SLinus Torvalds "vs-8110: "
4921da177e4SLinus Torvalds "direct item length is %d. It can not be longer than %d",
4931da177e4SLinus Torvalds current_item_size, max_node_size);
4941da177e4SLinus Torvalds /* we will try to split it */
4951da177e4SLinus Torvalds flow = 1;
4961da177e4SLinus Torvalds }
4971da177e4SLinus Torvalds
4981da177e4SLinus Torvalds /* as we do not split items, take new node and continue */
499098297b2SJeff Mahoney if (!flow) {
500bd4c625cSLinus Torvalds needed_nodes++;
501bd4c625cSLinus Torvalds i--;
502bd4c625cSLinus Torvalds total_node_size = 0;
5031da177e4SLinus Torvalds continue;
5041da177e4SLinus Torvalds }
505098297b2SJeff Mahoney
506098297b2SJeff Mahoney /*
507098297b2SJeff Mahoney * calculate number of item units which fit into node being
508098297b2SJeff Mahoney * filled
509098297b2SJeff Mahoney */
5101da177e4SLinus Torvalds {
5111da177e4SLinus Torvalds int free_space;
5121da177e4SLinus Torvalds
5131da177e4SLinus Torvalds free_space = max_node_size - total_node_size - IH_SIZE;
514bd4c625cSLinus Torvalds units =
515bd4c625cSLinus Torvalds op_check_left(vi, free_space, start_bytes,
516bd4c625cSLinus Torvalds skip_from_end);
517098297b2SJeff Mahoney /*
518098297b2SJeff Mahoney * nothing fits into current node, take new
519098297b2SJeff Mahoney * node and continue
520098297b2SJeff Mahoney */
5211da177e4SLinus Torvalds if (units == -1) {
5221da177e4SLinus Torvalds needed_nodes++, i--, total_node_size = 0;
5231da177e4SLinus Torvalds continue;
5241da177e4SLinus Torvalds }
5251da177e4SLinus Torvalds }
5261da177e4SLinus Torvalds
5271da177e4SLinus Torvalds /* something fits into the current node */
5281da177e4SLinus Torvalds start_bytes += units;
5291da177e4SLinus Torvalds snum012[needed_nodes - 1 + 3] = units;
5301da177e4SLinus Torvalds
5311da177e4SLinus Torvalds if (needed_nodes > 2)
53245b03d5eSJeff Mahoney reiserfs_warning(tb->tb_sb, "vs-8111",
53345b03d5eSJeff Mahoney "split_item_position is out of range");
5341da177e4SLinus Torvalds snum012[needed_nodes - 1]++;
5351da177e4SLinus Torvalds split_item_positions[needed_nodes - 1] = i;
5361da177e4SLinus Torvalds needed_nodes++;
5371da177e4SLinus Torvalds /* continue from the same item with start_bytes != -1 */
5381da177e4SLinus Torvalds start_item = i;
5391da177e4SLinus Torvalds i--;
5401da177e4SLinus Torvalds total_node_size = 0;
5411da177e4SLinus Torvalds }
5421da177e4SLinus Torvalds
543098297b2SJeff Mahoney /*
544098297b2SJeff Mahoney * sum012[4] (if it is not -1) contains number of units of which
545098297b2SJeff Mahoney * are to be in S1new, snum012[3] - to be in S0. They are supposed
546098297b2SJeff Mahoney * to be S1bytes and S2bytes correspondingly, so recalculate
547098297b2SJeff Mahoney */
5481da177e4SLinus Torvalds if (snum012[4] > 0) {
5491da177e4SLinus Torvalds int split_item_num;
5501da177e4SLinus Torvalds int bytes_to_r, bytes_to_l;
5511da177e4SLinus Torvalds int bytes_to_S1new;
5521da177e4SLinus Torvalds
5531da177e4SLinus Torvalds split_item_num = split_item_positions[1];
554bd4c625cSLinus Torvalds bytes_to_l =
555bd4c625cSLinus Torvalds ((from == split_item_num
556bd4c625cSLinus Torvalds && from_bytes != -1) ? from_bytes : 0);
557bd4c625cSLinus Torvalds bytes_to_r =
558bd4c625cSLinus Torvalds ((end_item == split_item_num
559bd4c625cSLinus Torvalds && end_bytes != -1) ? end_bytes : 0);
560bd4c625cSLinus Torvalds bytes_to_S1new =
561bd4c625cSLinus Torvalds ((split_item_positions[0] ==
562bd4c625cSLinus Torvalds split_item_positions[1]) ? snum012[3] : 0);
5631da177e4SLinus Torvalds
564098297b2SJeff Mahoney /* s2bytes */
565bd4c625cSLinus Torvalds snum012[4] =
566bd4c625cSLinus Torvalds op_unit_num(&vn->vn_vi[split_item_num]) - snum012[4] -
567bd4c625cSLinus Torvalds bytes_to_r - bytes_to_l - bytes_to_S1new;
5681da177e4SLinus Torvalds
5691da177e4SLinus Torvalds if (vn->vn_vi[split_item_num].vi_index != TYPE_DIRENTRY &&
5701da177e4SLinus Torvalds vn->vn_vi[split_item_num].vi_index != TYPE_INDIRECT)
57145b03d5eSJeff Mahoney reiserfs_warning(tb->tb_sb, "vs-8115",
57245b03d5eSJeff Mahoney "not directory or indirect item");
5731da177e4SLinus Torvalds }
5741da177e4SLinus Torvalds
5751da177e4SLinus Torvalds /* now we know S2bytes, calculate S1bytes */
5761da177e4SLinus Torvalds if (snum012[3] > 0) {
5771da177e4SLinus Torvalds int split_item_num;
5781da177e4SLinus Torvalds int bytes_to_r, bytes_to_l;
5791da177e4SLinus Torvalds int bytes_to_S2new;
5801da177e4SLinus Torvalds
5811da177e4SLinus Torvalds split_item_num = split_item_positions[0];
582bd4c625cSLinus Torvalds bytes_to_l =
583bd4c625cSLinus Torvalds ((from == split_item_num
584bd4c625cSLinus Torvalds && from_bytes != -1) ? from_bytes : 0);
585bd4c625cSLinus Torvalds bytes_to_r =
586bd4c625cSLinus Torvalds ((end_item == split_item_num
587bd4c625cSLinus Torvalds && end_bytes != -1) ? end_bytes : 0);
588bd4c625cSLinus Torvalds bytes_to_S2new =
589bd4c625cSLinus Torvalds ((split_item_positions[0] == split_item_positions[1]
590bd4c625cSLinus Torvalds && snum012[4] != -1) ? snum012[4] : 0);
5911da177e4SLinus Torvalds
592098297b2SJeff Mahoney /* s1bytes */
593bd4c625cSLinus Torvalds snum012[3] =
594bd4c625cSLinus Torvalds op_unit_num(&vn->vn_vi[split_item_num]) - snum012[3] -
595bd4c625cSLinus Torvalds bytes_to_r - bytes_to_l - bytes_to_S2new;
5961da177e4SLinus Torvalds }
5971da177e4SLinus Torvalds
5981da177e4SLinus Torvalds return needed_nodes;
5991da177e4SLinus Torvalds }
6001da177e4SLinus Torvalds
6011da177e4SLinus Torvalds
602098297b2SJeff Mahoney /*
603098297b2SJeff Mahoney * Set parameters for balancing.
6041da177e4SLinus Torvalds * Performs write of results of analysis of balancing into structure tb,
6051da177e4SLinus Torvalds * where it will later be used by the functions that actually do the balancing.
6061da177e4SLinus Torvalds * Parameters:
6071da177e4SLinus Torvalds * tb tree_balance structure;
6081da177e4SLinus Torvalds * h current level of the node;
6091da177e4SLinus Torvalds * lnum number of items from S[h] that must be shifted to L[h];
6101da177e4SLinus Torvalds * rnum number of items from S[h] that must be shifted to R[h];
6111da177e4SLinus Torvalds * blk_num number of blocks that S[h] will be splitted into;
6121da177e4SLinus Torvalds * s012 number of items that fall into splitted nodes.
613098297b2SJeff Mahoney * lbytes number of bytes which flow to the left neighbor from the
6149436fb4dSRandy Dunlap * item that is not shifted entirely
615098297b2SJeff Mahoney * rbytes number of bytes which flow to the right neighbor from the
6169436fb4dSRandy Dunlap * item that is not shifted entirely
617098297b2SJeff Mahoney * s1bytes number of bytes which flow to the first new node when
618098297b2SJeff Mahoney * S[0] splits (this number is contained in s012 array)
6191da177e4SLinus Torvalds */
6201da177e4SLinus Torvalds
set_parameters(struct tree_balance * tb,int h,int lnum,int rnum,int blk_num,short * s012,int lb,int rb)6211da177e4SLinus Torvalds static void set_parameters(struct tree_balance *tb, int h, int lnum,
6221da177e4SLinus Torvalds int rnum, int blk_num, short *s012, int lb, int rb)
6231da177e4SLinus Torvalds {
6241da177e4SLinus Torvalds
6251da177e4SLinus Torvalds tb->lnum[h] = lnum;
6261da177e4SLinus Torvalds tb->rnum[h] = rnum;
6271da177e4SLinus Torvalds tb->blknum[h] = blk_num;
6281da177e4SLinus Torvalds
629098297b2SJeff Mahoney /* only for leaf level */
630098297b2SJeff Mahoney if (h == 0) {
631bd4c625cSLinus Torvalds if (s012 != NULL) {
632b49fb112SJeff Mahoney tb->s0num = *s012++;
633b49fb112SJeff Mahoney tb->snum[0] = *s012++;
634b49fb112SJeff Mahoney tb->snum[1] = *s012++;
635b49fb112SJeff Mahoney tb->sbytes[0] = *s012++;
636b49fb112SJeff Mahoney tb->sbytes[1] = *s012;
6371da177e4SLinus Torvalds }
6381da177e4SLinus Torvalds tb->lbytes = lb;
6391da177e4SLinus Torvalds tb->rbytes = rb;
6401da177e4SLinus Torvalds }
6411da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, lnum[h], lnum);
6421da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, rnum[h], rnum);
6431da177e4SLinus Torvalds
6441da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, lbytes[h], lb);
6451da177e4SLinus Torvalds PROC_INFO_ADD(tb->tb_sb, rbytes[h], rb);
6461da177e4SLinus Torvalds }
6471da177e4SLinus Torvalds
648098297b2SJeff Mahoney /*
649098297b2SJeff Mahoney * check if node disappears if we shift tb->lnum[0] items to left
650098297b2SJeff Mahoney * neighbor and tb->rnum[0] to the right one.
651098297b2SJeff Mahoney */
is_leaf_removable(struct tree_balance * tb)6521da177e4SLinus Torvalds static int is_leaf_removable(struct tree_balance *tb)
6531da177e4SLinus Torvalds {
6541da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
6551da177e4SLinus Torvalds int to_left, to_right;
6561da177e4SLinus Torvalds int size;
6571da177e4SLinus Torvalds int remain_items;
6581da177e4SLinus Torvalds
659098297b2SJeff Mahoney /*
660098297b2SJeff Mahoney * number of items that will be shifted to left (right) neighbor
661098297b2SJeff Mahoney * entirely
662098297b2SJeff Mahoney */
6631da177e4SLinus Torvalds to_left = tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0);
6641da177e4SLinus Torvalds to_right = tb->rnum[0] - ((tb->rbytes != -1) ? 1 : 0);
6651da177e4SLinus Torvalds remain_items = vn->vn_nr_item;
6661da177e4SLinus Torvalds
6671da177e4SLinus Torvalds /* how many items remain in S[0] after shiftings to neighbors */
6681da177e4SLinus Torvalds remain_items -= (to_left + to_right);
6691da177e4SLinus Torvalds
6701da177e4SLinus Torvalds /* all content of node can be shifted to neighbors */
671098297b2SJeff Mahoney if (remain_items < 1) {
672bd4c625cSLinus Torvalds set_parameters(tb, 0, to_left, vn->vn_nr_item - to_left, 0,
673bd4c625cSLinus Torvalds NULL, -1, -1);
6741da177e4SLinus Torvalds return 1;
6751da177e4SLinus Torvalds }
6761da177e4SLinus Torvalds
6771da177e4SLinus Torvalds /* S[0] is not removable */
678098297b2SJeff Mahoney if (remain_items > 1 || tb->lbytes == -1 || tb->rbytes == -1)
6791da177e4SLinus Torvalds return 0;
6801da177e4SLinus Torvalds
681098297b2SJeff Mahoney /* check whether we can divide 1 remaining item between neighbors */
6821da177e4SLinus Torvalds
6831da177e4SLinus Torvalds /* get size of remaining item (in item units) */
684a228bf8fSJeff Mahoney size = op_unit_num(&vn->vn_vi[to_left]);
6851da177e4SLinus Torvalds
6861da177e4SLinus Torvalds if (tb->lbytes + tb->rbytes >= size) {
687bd4c625cSLinus Torvalds set_parameters(tb, 0, to_left + 1, to_right + 1, 0, NULL,
688bd4c625cSLinus Torvalds tb->lbytes, -1);
6891da177e4SLinus Torvalds return 1;
6901da177e4SLinus Torvalds }
6911da177e4SLinus Torvalds
6921da177e4SLinus Torvalds return 0;
6931da177e4SLinus Torvalds }
6941da177e4SLinus Torvalds
6951da177e4SLinus Torvalds /* check whether L, S, R can be joined in one node */
are_leaves_removable(struct tree_balance * tb,int lfree,int rfree)6961da177e4SLinus Torvalds static int are_leaves_removable(struct tree_balance *tb, int lfree, int rfree)
6971da177e4SLinus Torvalds {
6981da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
6991da177e4SLinus Torvalds int ih_size;
7001da177e4SLinus Torvalds struct buffer_head *S0;
7011da177e4SLinus Torvalds
7021da177e4SLinus Torvalds S0 = PATH_H_PBUFFER(tb->tb_path, 0);
7031da177e4SLinus Torvalds
7041da177e4SLinus Torvalds ih_size = 0;
7051da177e4SLinus Torvalds if (vn->vn_nr_item) {
7061da177e4SLinus Torvalds if (vn->vn_vi[0].vi_type & VI_TYPE_LEFT_MERGEABLE)
7071da177e4SLinus Torvalds ih_size += IH_SIZE;
7081da177e4SLinus Torvalds
709bd4c625cSLinus Torvalds if (vn->vn_vi[vn->vn_nr_item - 1].
710bd4c625cSLinus Torvalds vi_type & VI_TYPE_RIGHT_MERGEABLE)
7111da177e4SLinus Torvalds ih_size += IH_SIZE;
7121da177e4SLinus Torvalds } else {
7131da177e4SLinus Torvalds /* there was only one item and it will be deleted */
7141da177e4SLinus Torvalds struct item_head *ih;
7151da177e4SLinus Torvalds
7161da177e4SLinus Torvalds RFALSE(B_NR_ITEMS(S0) != 1,
717bd4c625cSLinus Torvalds "vs-8125: item number must be 1: it is %d",
718bd4c625cSLinus Torvalds B_NR_ITEMS(S0));
7191da177e4SLinus Torvalds
7204cf5f7adSJeff Mahoney ih = item_head(S0, 0);
721bd4c625cSLinus Torvalds if (tb->CFR[0]
722a228bf8fSJeff Mahoney && !comp_short_le_keys(&ih->ih_key,
7234cf5f7adSJeff Mahoney internal_key(tb->CFR[0],
724bd4c625cSLinus Torvalds tb->rkey[0])))
725098297b2SJeff Mahoney /*
726098297b2SJeff Mahoney * Directory must be in correct state here: that is
727098297b2SJeff Mahoney * somewhere at the left side should exist first
728098297b2SJeff Mahoney * directory item. But the item being deleted can
729098297b2SJeff Mahoney * not be that first one because its right neighbor
730098297b2SJeff Mahoney * is item of the same directory. (But first item
731098297b2SJeff Mahoney * always gets deleted in last turn). So, neighbors
732098297b2SJeff Mahoney * of deleted item can be merged, so we can save
733098297b2SJeff Mahoney * ih_size
734098297b2SJeff Mahoney */
7351da177e4SLinus Torvalds if (is_direntry_le_ih(ih)) {
7361da177e4SLinus Torvalds ih_size = IH_SIZE;
7371da177e4SLinus Torvalds
738098297b2SJeff Mahoney /*
739098297b2SJeff Mahoney * we might check that left neighbor exists
740098297b2SJeff Mahoney * and is of the same directory
741098297b2SJeff Mahoney */
7421da177e4SLinus Torvalds RFALSE(le_ih_k_offset(ih) == DOT_OFFSET,
7431da177e4SLinus Torvalds "vs-8130: first directory item can not be removed until directory is not empty");
7441da177e4SLinus Torvalds }
7451da177e4SLinus Torvalds
7461da177e4SLinus Torvalds }
7471da177e4SLinus Torvalds
7481da177e4SLinus Torvalds if (MAX_CHILD_SIZE(S0) + vn->vn_size <= rfree + lfree + ih_size) {
7491da177e4SLinus Torvalds set_parameters(tb, 0, -1, -1, -1, NULL, -1, -1);
7501da177e4SLinus Torvalds PROC_INFO_INC(tb->tb_sb, leaves_removable);
7511da177e4SLinus Torvalds return 1;
7521da177e4SLinus Torvalds }
7531da177e4SLinus Torvalds return 0;
7541da177e4SLinus Torvalds
7551da177e4SLinus Torvalds }
7561da177e4SLinus Torvalds
7571da177e4SLinus Torvalds /* when we do not split item, lnum and rnum are numbers of entire items */
7581da177e4SLinus Torvalds #define SET_PAR_SHIFT_LEFT \
7591da177e4SLinus Torvalds if (h)\
7601da177e4SLinus Torvalds {\
7611da177e4SLinus Torvalds int to_l;\
7621da177e4SLinus Torvalds \
7631da177e4SLinus Torvalds to_l = (MAX_NR_KEY(Sh)+1 - lpar + vn->vn_nr_item + 1) / 2 -\
7641da177e4SLinus Torvalds (MAX_NR_KEY(Sh) + 1 - lpar);\
7651da177e4SLinus Torvalds \
7661da177e4SLinus Torvalds set_parameters (tb, h, to_l, 0, lnver, NULL, -1, -1);\
7671da177e4SLinus Torvalds }\
7681da177e4SLinus Torvalds else \
7691da177e4SLinus Torvalds {\
7701da177e4SLinus Torvalds if (lset==LEFT_SHIFT_FLOW)\
7711da177e4SLinus Torvalds set_parameters (tb, h, lpar, 0, lnver, snum012+lset,\
7721da177e4SLinus Torvalds tb->lbytes, -1);\
7731da177e4SLinus Torvalds else\
7741da177e4SLinus Torvalds set_parameters (tb, h, lpar - (tb->lbytes!=-1), 0, lnver, snum012+lset,\
7751da177e4SLinus Torvalds -1, -1);\
7761da177e4SLinus Torvalds }
7771da177e4SLinus Torvalds
7781da177e4SLinus Torvalds #define SET_PAR_SHIFT_RIGHT \
7791da177e4SLinus Torvalds if (h)\
7801da177e4SLinus Torvalds {\
7811da177e4SLinus Torvalds int to_r;\
7821da177e4SLinus Torvalds \
7831da177e4SLinus Torvalds to_r = (MAX_NR_KEY(Sh)+1 - rpar + vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 - rpar);\
7841da177e4SLinus Torvalds \
7851da177e4SLinus Torvalds set_parameters (tb, h, 0, to_r, rnver, NULL, -1, -1);\
7861da177e4SLinus Torvalds }\
7871da177e4SLinus Torvalds else \
7881da177e4SLinus Torvalds {\
7891da177e4SLinus Torvalds if (rset==RIGHT_SHIFT_FLOW)\
7901da177e4SLinus Torvalds set_parameters (tb, h, 0, rpar, rnver, snum012+rset,\
7911da177e4SLinus Torvalds -1, tb->rbytes);\
7921da177e4SLinus Torvalds else\
7931da177e4SLinus Torvalds set_parameters (tb, h, 0, rpar - (tb->rbytes!=-1), rnver, snum012+rset,\
7941da177e4SLinus Torvalds -1, -1);\
7951da177e4SLinus Torvalds }
7961da177e4SLinus Torvalds
free_buffers_in_tb(struct tree_balance * tb)797a063ae17SJeff Mahoney static void free_buffers_in_tb(struct tree_balance *tb)
798bd4c625cSLinus Torvalds {
799ee93961bSJeff Mahoney int i;
8001da177e4SLinus Torvalds
801a063ae17SJeff Mahoney pathrelse(tb->tb_path);
8021da177e4SLinus Torvalds
803ee93961bSJeff Mahoney for (i = 0; i < MAX_HEIGHT; i++) {
804ee93961bSJeff Mahoney brelse(tb->L[i]);
805ee93961bSJeff Mahoney brelse(tb->R[i]);
806ee93961bSJeff Mahoney brelse(tb->FL[i]);
807ee93961bSJeff Mahoney brelse(tb->FR[i]);
808ee93961bSJeff Mahoney brelse(tb->CFL[i]);
809ee93961bSJeff Mahoney brelse(tb->CFR[i]);
8103cd6dbe6SJeff Mahoney
811ee93961bSJeff Mahoney tb->L[i] = NULL;
812ee93961bSJeff Mahoney tb->R[i] = NULL;
813ee93961bSJeff Mahoney tb->FL[i] = NULL;
814ee93961bSJeff Mahoney tb->FR[i] = NULL;
815ee93961bSJeff Mahoney tb->CFL[i] = NULL;
816ee93961bSJeff Mahoney tb->CFR[i] = NULL;
8171da177e4SLinus Torvalds }
8181da177e4SLinus Torvalds }
8191da177e4SLinus Torvalds
820098297b2SJeff Mahoney /*
821098297b2SJeff Mahoney * Get new buffers for storing new nodes that are created while balancing.
8221da177e4SLinus Torvalds * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
8231da177e4SLinus Torvalds * CARRY_ON - schedule didn't occur while the function worked;
8241da177e4SLinus Torvalds * NO_DISK_SPACE - no disk space.
8251da177e4SLinus Torvalds */
8261da177e4SLinus Torvalds /* The function is NOT SCHEDULE-SAFE! */
get_empty_nodes(struct tree_balance * tb,int h)827ee93961bSJeff Mahoney static int get_empty_nodes(struct tree_balance *tb, int h)
828bd4c625cSLinus Torvalds {
829098297b2SJeff Mahoney struct buffer_head *new_bh, *Sh = PATH_H_PBUFFER(tb->tb_path, h);
830ee93961bSJeff Mahoney b_blocknr_t *blocknr, blocknrs[MAX_AMOUNT_NEEDED] = { 0, };
831098297b2SJeff Mahoney int counter, number_of_freeblk;
832098297b2SJeff Mahoney int amount_needed; /* number of needed empty blocks */
833098297b2SJeff Mahoney int retval = CARRY_ON;
834a063ae17SJeff Mahoney struct super_block *sb = tb->tb_sb;
8351da177e4SLinus Torvalds
836098297b2SJeff Mahoney /*
837098297b2SJeff Mahoney * number_of_freeblk is the number of empty blocks which have been
838098297b2SJeff Mahoney * acquired for use by the balancing algorithm minus the number of
839098297b2SJeff Mahoney * empty blocks used in the previous levels of the analysis,
840098297b2SJeff Mahoney * number_of_freeblk = tb->cur_blknum can be non-zero if a schedule
841098297b2SJeff Mahoney * occurs after empty blocks are acquired, and the balancing analysis
842098297b2SJeff Mahoney * is then restarted, amount_needed is the number needed by this
843098297b2SJeff Mahoney * level (h) of the balancing analysis.
844098297b2SJeff Mahoney *
845098297b2SJeff Mahoney * Note that for systems with many processes writing, it would be
846098297b2SJeff Mahoney * more layout optimal to calculate the total number needed by all
847098297b2SJeff Mahoney * levels and then to run reiserfs_new_blocks to get all of them at
848098297b2SJeff Mahoney * once.
849098297b2SJeff Mahoney */
8501da177e4SLinus Torvalds
851098297b2SJeff Mahoney /*
852098297b2SJeff Mahoney * Initiate number_of_freeblk to the amount acquired prior to the
853098297b2SJeff Mahoney * restart of the analysis or 0 if not restarted, then subtract the
854098297b2SJeff Mahoney * amount needed by all of the levels of the tree below h.
855098297b2SJeff Mahoney */
856ee93961bSJeff Mahoney /* blknum includes S[h], so we subtract 1 in this calculation */
857ee93961bSJeff Mahoney for (counter = 0, number_of_freeblk = tb->cur_blknum;
858ee93961bSJeff Mahoney counter < h; counter++)
859ee93961bSJeff Mahoney number_of_freeblk -=
860ee93961bSJeff Mahoney (tb->blknum[counter]) ? (tb->blknum[counter] -
861bd4c625cSLinus Torvalds 1) : 0;
8621da177e4SLinus Torvalds
8631da177e4SLinus Torvalds /* Allocate missing empty blocks. */
864d68caa95SJeff Mahoney /* if Sh == 0 then we are getting a new root */
865ee93961bSJeff Mahoney amount_needed = (Sh) ? (tb->blknum[h] - 1) : 1;
866098297b2SJeff Mahoney /*
867098297b2SJeff Mahoney * Amount_needed = the amount that we need more than the
868098297b2SJeff Mahoney * amount that we have.
869098297b2SJeff Mahoney */
870ee93961bSJeff Mahoney if (amount_needed > number_of_freeblk)
871ee93961bSJeff Mahoney amount_needed -= number_of_freeblk;
8721da177e4SLinus Torvalds else /* If we have enough already then there is nothing to do. */
8731da177e4SLinus Torvalds return CARRY_ON;
8741da177e4SLinus Torvalds
875098297b2SJeff Mahoney /*
876098297b2SJeff Mahoney * No need to check quota - is not allocated for blocks used
877098297b2SJeff Mahoney * for formatted nodes
878098297b2SJeff Mahoney */
879ee93961bSJeff Mahoney if (reiserfs_new_form_blocknrs(tb, blocknrs,
880ee93961bSJeff Mahoney amount_needed) == NO_DISK_SPACE)
8811da177e4SLinus Torvalds return NO_DISK_SPACE;
8821da177e4SLinus Torvalds
8831da177e4SLinus Torvalds /* for each blocknumber we just got, get a buffer and stick it on FEB */
884ee93961bSJeff Mahoney for (blocknr = blocknrs, counter = 0;
885ee93961bSJeff Mahoney counter < amount_needed; blocknr++, counter++) {
8861da177e4SLinus Torvalds
887d68caa95SJeff Mahoney RFALSE(!*blocknr,
8881da177e4SLinus Torvalds "PAP-8135: reiserfs_new_blocknrs failed when got new blocks");
8891da177e4SLinus Torvalds
890d68caa95SJeff Mahoney new_bh = sb_getblk(sb, *blocknr);
891d68caa95SJeff Mahoney RFALSE(buffer_dirty(new_bh) ||
892d68caa95SJeff Mahoney buffer_journaled(new_bh) ||
893d68caa95SJeff Mahoney buffer_journal_dirty(new_bh),
894febe29d9SAdam Buchbinder "PAP-8140: journaled or dirty buffer %b for the new block",
895d68caa95SJeff Mahoney new_bh);
8961da177e4SLinus Torvalds
8971da177e4SLinus Torvalds /* Put empty buffers into the array. */
898a063ae17SJeff Mahoney RFALSE(tb->FEB[tb->cur_blknum],
8991da177e4SLinus Torvalds "PAP-8141: busy slot for new buffer");
9001da177e4SLinus Torvalds
901d68caa95SJeff Mahoney set_buffer_journal_new(new_bh);
902d68caa95SJeff Mahoney tb->FEB[tb->cur_blknum++] = new_bh;
9031da177e4SLinus Torvalds }
9041da177e4SLinus Torvalds
905ee93961bSJeff Mahoney if (retval == CARRY_ON && FILESYSTEM_CHANGED_TB(tb))
906ee93961bSJeff Mahoney retval = REPEAT_SEARCH;
9071da177e4SLinus Torvalds
908ee93961bSJeff Mahoney return retval;
9091da177e4SLinus Torvalds }
9101da177e4SLinus Torvalds
911098297b2SJeff Mahoney /*
912098297b2SJeff Mahoney * Get free space of the left neighbor, which is stored in the parent
913098297b2SJeff Mahoney * node of the left neighbor.
914098297b2SJeff Mahoney */
get_lfree(struct tree_balance * tb,int h)9151da177e4SLinus Torvalds static int get_lfree(struct tree_balance *tb, int h)
9161da177e4SLinus Torvalds {
9171da177e4SLinus Torvalds struct buffer_head *l, *f;
9181da177e4SLinus Torvalds int order;
9191da177e4SLinus Torvalds
9209dce07f1SAl Viro if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
9219dce07f1SAl Viro (l = tb->FL[h]) == NULL)
9221da177e4SLinus Torvalds return 0;
9231da177e4SLinus Torvalds
9241da177e4SLinus Torvalds if (f == l)
9251da177e4SLinus Torvalds order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) - 1;
9261da177e4SLinus Torvalds else {
9271da177e4SLinus Torvalds order = B_NR_ITEMS(l);
9281da177e4SLinus Torvalds f = l;
9291da177e4SLinus Torvalds }
9301da177e4SLinus Torvalds
9311da177e4SLinus Torvalds return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
9321da177e4SLinus Torvalds }
9331da177e4SLinus Torvalds
934098297b2SJeff Mahoney /*
935098297b2SJeff Mahoney * Get free space of the right neighbor,
9361da177e4SLinus Torvalds * which is stored in the parent node of the right neighbor.
9371da177e4SLinus Torvalds */
get_rfree(struct tree_balance * tb,int h)9381da177e4SLinus Torvalds static int get_rfree(struct tree_balance *tb, int h)
9391da177e4SLinus Torvalds {
9401da177e4SLinus Torvalds struct buffer_head *r, *f;
9411da177e4SLinus Torvalds int order;
9421da177e4SLinus Torvalds
9439dce07f1SAl Viro if ((f = PATH_H_PPARENT(tb->tb_path, h)) == NULL ||
9449dce07f1SAl Viro (r = tb->FR[h]) == NULL)
9451da177e4SLinus Torvalds return 0;
9461da177e4SLinus Torvalds
9471da177e4SLinus Torvalds if (f == r)
9481da177e4SLinus Torvalds order = PATH_H_B_ITEM_ORDER(tb->tb_path, h) + 1;
9491da177e4SLinus Torvalds else {
9501da177e4SLinus Torvalds order = 0;
9511da177e4SLinus Torvalds f = r;
9521da177e4SLinus Torvalds }
9531da177e4SLinus Torvalds
9541da177e4SLinus Torvalds return (MAX_CHILD_SIZE(f) - dc_size(B_N_CHILD(f, order)));
9551da177e4SLinus Torvalds
9561da177e4SLinus Torvalds }
9571da177e4SLinus Torvalds
9581da177e4SLinus Torvalds /* Check whether left neighbor is in memory. */
is_left_neighbor_in_cache(struct tree_balance * tb,int h)959ee93961bSJeff Mahoney static int is_left_neighbor_in_cache(struct tree_balance *tb, int h)
960bd4c625cSLinus Torvalds {
961d68caa95SJeff Mahoney struct buffer_head *father, *left;
962a063ae17SJeff Mahoney struct super_block *sb = tb->tb_sb;
963ee93961bSJeff Mahoney b_blocknr_t left_neighbor_blocknr;
964ee93961bSJeff Mahoney int left_neighbor_position;
9651da177e4SLinus Torvalds
966a063ae17SJeff Mahoney /* Father of the left neighbor does not exist. */
967ee93961bSJeff Mahoney if (!tb->FL[h])
9681da177e4SLinus Torvalds return 0;
9691da177e4SLinus Torvalds
9701da177e4SLinus Torvalds /* Calculate father of the node to be balanced. */
971ee93961bSJeff Mahoney father = PATH_H_PBUFFER(tb->tb_path, h + 1);
9721da177e4SLinus Torvalds
973d68caa95SJeff Mahoney RFALSE(!father ||
974d68caa95SJeff Mahoney !B_IS_IN_TREE(father) ||
975ee93961bSJeff Mahoney !B_IS_IN_TREE(tb->FL[h]) ||
976d68caa95SJeff Mahoney !buffer_uptodate(father) ||
977ee93961bSJeff Mahoney !buffer_uptodate(tb->FL[h]),
9781da177e4SLinus Torvalds "vs-8165: F[h] (%b) or FL[h] (%b) is invalid",
979ee93961bSJeff Mahoney father, tb->FL[h]);
9801da177e4SLinus Torvalds
981098297b2SJeff Mahoney /*
982098297b2SJeff Mahoney * Get position of the pointer to the left neighbor
983098297b2SJeff Mahoney * into the left father.
984098297b2SJeff Mahoney */
985ee93961bSJeff Mahoney left_neighbor_position = (father == tb->FL[h]) ?
986ee93961bSJeff Mahoney tb->lkey[h] : B_NR_ITEMS(tb->FL[h]);
9871da177e4SLinus Torvalds /* Get left neighbor block number. */
988ee93961bSJeff Mahoney left_neighbor_blocknr =
989ee93961bSJeff Mahoney B_N_CHILD_NUM(tb->FL[h], left_neighbor_position);
9901da177e4SLinus Torvalds /* Look for the left neighbor in the cache. */
991ee93961bSJeff Mahoney if ((left = sb_find_get_block(sb, left_neighbor_blocknr))) {
9921da177e4SLinus Torvalds
9931da177e4SLinus Torvalds RFALSE(buffer_uptodate(left) && !B_IS_IN_TREE(left),
994bd4c625cSLinus Torvalds "vs-8170: left neighbor (%b %z) is not in the tree",
995bd4c625cSLinus Torvalds left, left);
9961da177e4SLinus Torvalds put_bh(left);
9971da177e4SLinus Torvalds return 1;
9981da177e4SLinus Torvalds }
9991da177e4SLinus Torvalds
10001da177e4SLinus Torvalds return 0;
10011da177e4SLinus Torvalds }
10021da177e4SLinus Torvalds
10031da177e4SLinus Torvalds #define LEFT_PARENTS 'l'
10041da177e4SLinus Torvalds #define RIGHT_PARENTS 'r'
10051da177e4SLinus Torvalds
decrement_key(struct cpu_key * key)1006d68caa95SJeff Mahoney static void decrement_key(struct cpu_key *key)
10071da177e4SLinus Torvalds {
1008098297b2SJeff Mahoney /* call item specific function for this key */
1009d68caa95SJeff Mahoney item_ops[cpu_key_k_type(key)]->decrement_key(key);
10101da177e4SLinus Torvalds }
10111da177e4SLinus Torvalds
1012098297b2SJeff Mahoney /*
1013098297b2SJeff Mahoney * Calculate far left/right parent of the left/right neighbor of the
1014098297b2SJeff Mahoney * current node, that is calculate the left/right (FL[h]/FR[h]) neighbor
1015098297b2SJeff Mahoney * of the parent F[h].
10161da177e4SLinus Torvalds * Calculate left/right common parent of the current node and L[h]/R[h].
10171da177e4SLinus Torvalds * Calculate left/right delimiting key position.
1018098297b2SJeff Mahoney * Returns: PATH_INCORRECT - path in the tree is not correct
1019098297b2SJeff Mahoney * SCHEDULE_OCCURRED - schedule occurred while the function worked
1020098297b2SJeff Mahoney * CARRY_ON - schedule didn't occur while the function
1021098297b2SJeff Mahoney * worked
10221da177e4SLinus Torvalds */
get_far_parent(struct tree_balance * tb,int h,struct buffer_head ** pfather,struct buffer_head ** pcom_father,char c_lr_par)1023a063ae17SJeff Mahoney static int get_far_parent(struct tree_balance *tb,
1024ee93961bSJeff Mahoney int h,
1025d68caa95SJeff Mahoney struct buffer_head **pfather,
1026d68caa95SJeff Mahoney struct buffer_head **pcom_father, char c_lr_par)
10271da177e4SLinus Torvalds {
1028d68caa95SJeff Mahoney struct buffer_head *parent;
10291da177e4SLinus Torvalds INITIALIZE_PATH(s_path_to_neighbor_father);
1030d68caa95SJeff Mahoney struct treepath *path = tb->tb_path;
10311da177e4SLinus Torvalds struct cpu_key s_lr_father_key;
1032ee93961bSJeff Mahoney int counter,
1033ee93961bSJeff Mahoney position = INT_MAX,
1034ee93961bSJeff Mahoney first_last_position = 0,
1035ee93961bSJeff Mahoney path_offset = PATH_H_PATH_OFFSET(path, h);
10361da177e4SLinus Torvalds
1037098297b2SJeff Mahoney /*
1038098297b2SJeff Mahoney * Starting from F[h] go upwards in the tree, and look for the common
1039098297b2SJeff Mahoney * ancestor of F[h], and its neighbor l/r, that should be obtained.
1040098297b2SJeff Mahoney */
10411da177e4SLinus Torvalds
1042ee93961bSJeff Mahoney counter = path_offset;
10431da177e4SLinus Torvalds
1044ee93961bSJeff Mahoney RFALSE(counter < FIRST_PATH_ELEMENT_OFFSET,
10451da177e4SLinus Torvalds "PAP-8180: invalid path length");
10461da177e4SLinus Torvalds
1047ee93961bSJeff Mahoney for (; counter > FIRST_PATH_ELEMENT_OFFSET; counter--) {
1048098297b2SJeff Mahoney /*
1049098297b2SJeff Mahoney * Check whether parent of the current buffer in the path
1050098297b2SJeff Mahoney * is really parent in the tree.
1051098297b2SJeff Mahoney */
1052bd4c625cSLinus Torvalds if (!B_IS_IN_TREE
1053ee93961bSJeff Mahoney (parent = PATH_OFFSET_PBUFFER(path, counter - 1)))
10541da177e4SLinus Torvalds return REPEAT_SEARCH;
1055098297b2SJeff Mahoney
10561da177e4SLinus Torvalds /* Check whether position in the parent is correct. */
1057ee93961bSJeff Mahoney if ((position =
1058d68caa95SJeff Mahoney PATH_OFFSET_POSITION(path,
1059ee93961bSJeff Mahoney counter - 1)) >
1060d68caa95SJeff Mahoney B_NR_ITEMS(parent))
10611da177e4SLinus Torvalds return REPEAT_SEARCH;
1062098297b2SJeff Mahoney
1063098297b2SJeff Mahoney /*
1064098297b2SJeff Mahoney * Check whether parent at the path really points
1065098297b2SJeff Mahoney * to the child.
1066098297b2SJeff Mahoney */
1067ee93961bSJeff Mahoney if (B_N_CHILD_NUM(parent, position) !=
1068ee93961bSJeff Mahoney PATH_OFFSET_PBUFFER(path, counter)->b_blocknr)
10691da177e4SLinus Torvalds return REPEAT_SEARCH;
1070098297b2SJeff Mahoney
1071098297b2SJeff Mahoney /*
1072098297b2SJeff Mahoney * Return delimiting key if position in the parent is not
1073098297b2SJeff Mahoney * equal to first/last one.
1074098297b2SJeff Mahoney */
10751da177e4SLinus Torvalds if (c_lr_par == RIGHT_PARENTS)
1076ee93961bSJeff Mahoney first_last_position = B_NR_ITEMS(parent);
1077ee93961bSJeff Mahoney if (position != first_last_position) {
1078d68caa95SJeff Mahoney *pcom_father = parent;
1079d68caa95SJeff Mahoney get_bh(*pcom_father);
1080d68caa95SJeff Mahoney /*(*pcom_father = parent)->b_count++; */
10811da177e4SLinus Torvalds break;
10821da177e4SLinus Torvalds }
10831da177e4SLinus Torvalds }
10841da177e4SLinus Torvalds
10851da177e4SLinus Torvalds /* if we are in the root of the tree, then there is no common father */
1086ee93961bSJeff Mahoney if (counter == FIRST_PATH_ELEMENT_OFFSET) {
1087098297b2SJeff Mahoney /*
1088098297b2SJeff Mahoney * Check whether first buffer in the path is the
1089098297b2SJeff Mahoney * root of the tree.
1090098297b2SJeff Mahoney */
1091bd4c625cSLinus Torvalds if (PATH_OFFSET_PBUFFER
1092a063ae17SJeff Mahoney (tb->tb_path,
1093bd4c625cSLinus Torvalds FIRST_PATH_ELEMENT_OFFSET)->b_blocknr ==
1094a063ae17SJeff Mahoney SB_ROOT_BLOCK(tb->tb_sb)) {
1095d68caa95SJeff Mahoney *pfather = *pcom_father = NULL;
10961da177e4SLinus Torvalds return CARRY_ON;
10971da177e4SLinus Torvalds }
10981da177e4SLinus Torvalds return REPEAT_SEARCH;
10991da177e4SLinus Torvalds }
11001da177e4SLinus Torvalds
1101d68caa95SJeff Mahoney RFALSE(B_LEVEL(*pcom_father) <= DISK_LEAF_NODE_LEVEL,
11021da177e4SLinus Torvalds "PAP-8185: (%b %z) level too small",
1103d68caa95SJeff Mahoney *pcom_father, *pcom_father);
11041da177e4SLinus Torvalds
11051da177e4SLinus Torvalds /* Check whether the common parent is locked. */
11061da177e4SLinus Torvalds
1107d68caa95SJeff Mahoney if (buffer_locked(*pcom_father)) {
11088ebc4232SFrederic Weisbecker
11098ebc4232SFrederic Weisbecker /* Release the write lock while the buffer is busy */
1110278f6679SJeff Mahoney int depth = reiserfs_write_unlock_nested(tb->tb_sb);
1111d68caa95SJeff Mahoney __wait_on_buffer(*pcom_father);
1112278f6679SJeff Mahoney reiserfs_write_lock_nested(tb->tb_sb, depth);
1113a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb)) {
1114d68caa95SJeff Mahoney brelse(*pcom_father);
11151da177e4SLinus Torvalds return REPEAT_SEARCH;
11161da177e4SLinus Torvalds }
11171da177e4SLinus Torvalds }
11181da177e4SLinus Torvalds
1119098297b2SJeff Mahoney /*
1120098297b2SJeff Mahoney * So, we got common parent of the current node and its
1121098297b2SJeff Mahoney * left/right neighbor. Now we are getting the parent of the
1122098297b2SJeff Mahoney * left/right neighbor.
1123098297b2SJeff Mahoney */
11241da177e4SLinus Torvalds
11251da177e4SLinus Torvalds /* Form key to get parent of the left/right neighbor. */
1126bd4c625cSLinus Torvalds le_key2cpu_key(&s_lr_father_key,
11274cf5f7adSJeff Mahoney internal_key(*pcom_father,
1128bd4c625cSLinus Torvalds (c_lr_par ==
1129ee93961bSJeff Mahoney LEFT_PARENTS) ? (tb->lkey[h - 1] =
1130ee93961bSJeff Mahoney position -
1131ee93961bSJeff Mahoney 1) : (tb->rkey[h -
1132bd4c625cSLinus Torvalds 1] =
1133ee93961bSJeff Mahoney position)));
11341da177e4SLinus Torvalds
11351da177e4SLinus Torvalds if (c_lr_par == LEFT_PARENTS)
11361da177e4SLinus Torvalds decrement_key(&s_lr_father_key);
11371da177e4SLinus Torvalds
1138bd4c625cSLinus Torvalds if (search_by_key
1139a063ae17SJeff Mahoney (tb->tb_sb, &s_lr_father_key, &s_path_to_neighbor_father,
1140ee93961bSJeff Mahoney h + 1) == IO_ERROR)
1141098297b2SJeff Mahoney /* path is released */
11421da177e4SLinus Torvalds return IO_ERROR;
11431da177e4SLinus Torvalds
1144a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb)) {
11453cd6dbe6SJeff Mahoney pathrelse(&s_path_to_neighbor_father);
1146d68caa95SJeff Mahoney brelse(*pcom_father);
11471da177e4SLinus Torvalds return REPEAT_SEARCH;
11481da177e4SLinus Torvalds }
11491da177e4SLinus Torvalds
1150d68caa95SJeff Mahoney *pfather = PATH_PLAST_BUFFER(&s_path_to_neighbor_father);
11511da177e4SLinus Torvalds
1152ee93961bSJeff Mahoney RFALSE(B_LEVEL(*pfather) != h + 1,
1153d68caa95SJeff Mahoney "PAP-8190: (%b %z) level too small", *pfather, *pfather);
1154bd4c625cSLinus Torvalds RFALSE(s_path_to_neighbor_father.path_length <
1155bd4c625cSLinus Torvalds FIRST_PATH_ELEMENT_OFFSET, "PAP-8192: path length is too small");
11561da177e4SLinus Torvalds
11571da177e4SLinus Torvalds s_path_to_neighbor_father.path_length--;
11583cd6dbe6SJeff Mahoney pathrelse(&s_path_to_neighbor_father);
11591da177e4SLinus Torvalds return CARRY_ON;
11601da177e4SLinus Torvalds }
11611da177e4SLinus Torvalds
1162098297b2SJeff Mahoney /*
1163098297b2SJeff Mahoney * Get parents of neighbors of node in the path(S[path_offset]) and
1164098297b2SJeff Mahoney * common parents of S[path_offset] and L[path_offset]/R[path_offset]:
1165098297b2SJeff Mahoney * F[path_offset], FL[path_offset], FR[path_offset], CFL[path_offset],
1166098297b2SJeff Mahoney * CFR[path_offset].
1167098297b2SJeff Mahoney * Calculate numbers of left and right delimiting keys position:
1168098297b2SJeff Mahoney * lkey[path_offset], rkey[path_offset].
1169098297b2SJeff Mahoney * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked
1170098297b2SJeff Mahoney * CARRY_ON - schedule didn't occur while the function worked
11711da177e4SLinus Torvalds */
get_parents(struct tree_balance * tb,int h)1172ee93961bSJeff Mahoney static int get_parents(struct tree_balance *tb, int h)
11731da177e4SLinus Torvalds {
1174d68caa95SJeff Mahoney struct treepath *path = tb->tb_path;
1175ee93961bSJeff Mahoney int position,
1176ee93961bSJeff Mahoney ret,
1177ee93961bSJeff Mahoney path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
1178d68caa95SJeff Mahoney struct buffer_head *curf, *curcf;
11791da177e4SLinus Torvalds
11801da177e4SLinus Torvalds /* Current node is the root of the tree or will be root of the tree */
1181ee93961bSJeff Mahoney if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
1182098297b2SJeff Mahoney /*
1183098297b2SJeff Mahoney * The root can not have parents.
1184098297b2SJeff Mahoney * Release nodes which previously were obtained as
1185098297b2SJeff Mahoney * parents of the current node neighbors.
1186098297b2SJeff Mahoney */
1187ee93961bSJeff Mahoney brelse(tb->FL[h]);
1188ee93961bSJeff Mahoney brelse(tb->CFL[h]);
1189ee93961bSJeff Mahoney brelse(tb->FR[h]);
1190ee93961bSJeff Mahoney brelse(tb->CFR[h]);
1191ee93961bSJeff Mahoney tb->FL[h] = NULL;
1192ee93961bSJeff Mahoney tb->CFL[h] = NULL;
1193ee93961bSJeff Mahoney tb->FR[h] = NULL;
1194ee93961bSJeff Mahoney tb->CFR[h] = NULL;
11951da177e4SLinus Torvalds return CARRY_ON;
11961da177e4SLinus Torvalds }
11971da177e4SLinus Torvalds
1198ee93961bSJeff Mahoney /* Get parent FL[path_offset] of L[path_offset]. */
1199ee93961bSJeff Mahoney position = PATH_OFFSET_POSITION(path, path_offset - 1);
1200ee93961bSJeff Mahoney if (position) {
12011da177e4SLinus Torvalds /* Current node is not the first child of its parent. */
1202ee93961bSJeff Mahoney curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1203ee93961bSJeff Mahoney curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1204d68caa95SJeff Mahoney get_bh(curf);
1205d68caa95SJeff Mahoney get_bh(curf);
1206ee93961bSJeff Mahoney tb->lkey[h] = position - 1;
1207bd4c625cSLinus Torvalds } else {
1208098297b2SJeff Mahoney /*
1209098297b2SJeff Mahoney * Calculate current parent of L[path_offset], which is the
1210098297b2SJeff Mahoney * left neighbor of the current node. Calculate current
1211098297b2SJeff Mahoney * common parent of L[path_offset] and the current node.
1212098297b2SJeff Mahoney * Note that CFL[path_offset] not equal FL[path_offset] and
1213098297b2SJeff Mahoney * CFL[path_offset] not equal F[path_offset].
1214098297b2SJeff Mahoney * Calculate lkey[path_offset].
1215098297b2SJeff Mahoney */
1216ee93961bSJeff Mahoney if ((ret = get_far_parent(tb, h + 1, &curf,
1217d68caa95SJeff Mahoney &curcf,
1218bd4c625cSLinus Torvalds LEFT_PARENTS)) != CARRY_ON)
1219ee93961bSJeff Mahoney return ret;
12201da177e4SLinus Torvalds }
12211da177e4SLinus Torvalds
1222ee93961bSJeff Mahoney brelse(tb->FL[h]);
1223ee93961bSJeff Mahoney tb->FL[h] = curf; /* New initialization of FL[h]. */
1224ee93961bSJeff Mahoney brelse(tb->CFL[h]);
1225ee93961bSJeff Mahoney tb->CFL[h] = curcf; /* New initialization of CFL[h]. */
12261da177e4SLinus Torvalds
1227d68caa95SJeff Mahoney RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1228d68caa95SJeff Mahoney (curcf && !B_IS_IN_TREE(curcf)),
1229d68caa95SJeff Mahoney "PAP-8195: FL (%b) or CFL (%b) is invalid", curf, curcf);
12301da177e4SLinus Torvalds
1231ee93961bSJeff Mahoney /* Get parent FR[h] of R[h]. */
12321da177e4SLinus Torvalds
1233ee93961bSJeff Mahoney /* Current node is the last child of F[h]. FR[h] != F[h]. */
1234ee93961bSJeff Mahoney if (position == B_NR_ITEMS(PATH_H_PBUFFER(path, h + 1))) {
1235098297b2SJeff Mahoney /*
1236098297b2SJeff Mahoney * Calculate current parent of R[h], which is the right
1237098297b2SJeff Mahoney * neighbor of F[h]. Calculate current common parent of
1238098297b2SJeff Mahoney * R[h] and current node. Note that CFR[h] not equal
1239098297b2SJeff Mahoney * FR[path_offset] and CFR[h] not equal F[h].
1240098297b2SJeff Mahoney */
1241ee93961bSJeff Mahoney if ((ret =
1242ee93961bSJeff Mahoney get_far_parent(tb, h + 1, &curf, &curcf,
1243bd4c625cSLinus Torvalds RIGHT_PARENTS)) != CARRY_ON)
1244ee93961bSJeff Mahoney return ret;
1245bd4c625cSLinus Torvalds } else {
1246ee93961bSJeff Mahoney /* Current node is not the last child of its parent F[h]. */
1247ee93961bSJeff Mahoney curf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1248ee93961bSJeff Mahoney curcf = PATH_OFFSET_PBUFFER(path, path_offset - 1);
1249d68caa95SJeff Mahoney get_bh(curf);
1250d68caa95SJeff Mahoney get_bh(curf);
1251ee93961bSJeff Mahoney tb->rkey[h] = position;
12521da177e4SLinus Torvalds }
12531da177e4SLinus Torvalds
1254ee93961bSJeff Mahoney brelse(tb->FR[h]);
1255ee93961bSJeff Mahoney /* New initialization of FR[path_offset]. */
1256ee93961bSJeff Mahoney tb->FR[h] = curf;
12571da177e4SLinus Torvalds
1258ee93961bSJeff Mahoney brelse(tb->CFR[h]);
1259ee93961bSJeff Mahoney /* New initialization of CFR[path_offset]. */
1260ee93961bSJeff Mahoney tb->CFR[h] = curcf;
12611da177e4SLinus Torvalds
1262d68caa95SJeff Mahoney RFALSE((curf && !B_IS_IN_TREE(curf)) ||
1263d68caa95SJeff Mahoney (curcf && !B_IS_IN_TREE(curcf)),
1264d68caa95SJeff Mahoney "PAP-8205: FR (%b) or CFR (%b) is invalid", curf, curcf);
12651da177e4SLinus Torvalds
12661da177e4SLinus Torvalds return CARRY_ON;
12671da177e4SLinus Torvalds }
12681da177e4SLinus Torvalds
1269098297b2SJeff Mahoney /*
1270098297b2SJeff Mahoney * it is possible to remove node as result of shiftings to
1271098297b2SJeff Mahoney * neighbors even when we insert or paste item.
1272098297b2SJeff Mahoney */
can_node_be_removed(int mode,int lfree,int sfree,int rfree,struct tree_balance * tb,int h)1273bd4c625cSLinus Torvalds static inline int can_node_be_removed(int mode, int lfree, int sfree, int rfree,
1274bd4c625cSLinus Torvalds struct tree_balance *tb, int h)
12751da177e4SLinus Torvalds {
12761da177e4SLinus Torvalds struct buffer_head *Sh = PATH_H_PBUFFER(tb->tb_path, h);
12771da177e4SLinus Torvalds int levbytes = tb->insert_size[h];
12781da177e4SLinus Torvalds struct item_head *ih;
12791da177e4SLinus Torvalds struct reiserfs_key *r_key = NULL;
12801da177e4SLinus Torvalds
12814cf5f7adSJeff Mahoney ih = item_head(Sh, 0);
12821da177e4SLinus Torvalds if (tb->CFR[h])
12834cf5f7adSJeff Mahoney r_key = internal_key(tb->CFR[h], tb->rkey[h]);
12841da177e4SLinus Torvalds
1285bd4c625cSLinus Torvalds if (lfree + rfree + sfree < MAX_CHILD_SIZE(Sh) + levbytes
12861da177e4SLinus Torvalds /* shifting may merge items which might save space */
1287bd4c625cSLinus Torvalds -
1288bd4c625cSLinus Torvalds ((!h
1289a228bf8fSJeff Mahoney && op_is_left_mergeable(&ih->ih_key, Sh->b_size)) ? IH_SIZE : 0)
1290bd4c625cSLinus Torvalds -
1291bd4c625cSLinus Torvalds ((!h && r_key
1292bd4c625cSLinus Torvalds && op_is_left_mergeable(r_key, Sh->b_size)) ? IH_SIZE : 0)
1293bd4c625cSLinus Torvalds + ((h) ? KEY_SIZE : 0)) {
12941da177e4SLinus Torvalds /* node can not be removed */
1295098297b2SJeff Mahoney if (sfree >= levbytes) {
1296098297b2SJeff Mahoney /* new item fits into node S[h] without any shifting */
12971da177e4SLinus Torvalds if (!h)
1298bd4c625cSLinus Torvalds tb->s0num =
1299bd4c625cSLinus Torvalds B_NR_ITEMS(Sh) +
1300bd4c625cSLinus Torvalds ((mode == M_INSERT) ? 1 : 0);
13011da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
13021da177e4SLinus Torvalds return NO_BALANCING_NEEDED;
13031da177e4SLinus Torvalds }
13041da177e4SLinus Torvalds }
13051da177e4SLinus Torvalds PROC_INFO_INC(tb->tb_sb, can_node_be_removed[h]);
13061da177e4SLinus Torvalds return !NO_BALANCING_NEEDED;
13071da177e4SLinus Torvalds }
13081da177e4SLinus Torvalds
1309098297b2SJeff Mahoney /*
1310098297b2SJeff Mahoney * Check whether current node S[h] is balanced when increasing its size by
13111da177e4SLinus Torvalds * Inserting or Pasting.
13121da177e4SLinus Torvalds * Calculate parameters for balancing for current level h.
13131da177e4SLinus Torvalds * Parameters:
13141da177e4SLinus Torvalds * tb tree_balance structure;
13151da177e4SLinus Torvalds * h current level of the node;
13161da177e4SLinus Torvalds * inum item number in S[h];
13171da177e4SLinus Torvalds * mode i - insert, p - paste;
13181da177e4SLinus Torvalds * Returns: 1 - schedule occurred;
13191da177e4SLinus Torvalds * 0 - balancing for higher levels needed;
13201da177e4SLinus Torvalds * -1 - no balancing for higher levels needed;
13211da177e4SLinus Torvalds * -2 - no disk space.
13221da177e4SLinus Torvalds */
13231da177e4SLinus Torvalds /* ip means Inserting or Pasting */
ip_check_balance(struct tree_balance * tb,int h)13241da177e4SLinus Torvalds static int ip_check_balance(struct tree_balance *tb, int h)
13251da177e4SLinus Torvalds {
13261da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
1327098297b2SJeff Mahoney /*
1328098297b2SJeff Mahoney * Number of bytes that must be inserted into (value is negative
1329098297b2SJeff Mahoney * if bytes are deleted) buffer which contains node being balanced.
1330098297b2SJeff Mahoney * The mnemonic is that the attempted change in node space used
1331098297b2SJeff Mahoney * level is levbytes bytes.
1332098297b2SJeff Mahoney */
1333098297b2SJeff Mahoney int levbytes;
1334098297b2SJeff Mahoney int ret;
13351da177e4SLinus Torvalds
13361da177e4SLinus Torvalds int lfree, sfree, rfree /* free space in L, S and R */ ;
13371da177e4SLinus Torvalds
1338098297b2SJeff Mahoney /*
1339098297b2SJeff Mahoney * nver is short for number of vertixes, and lnver is the number if
1340098297b2SJeff Mahoney * we shift to the left, rnver is the number if we shift to the
1341098297b2SJeff Mahoney * right, and lrnver is the number if we shift in both directions.
1342098297b2SJeff Mahoney * The goal is to minimize first the number of vertixes, and second,
1343098297b2SJeff Mahoney * the number of vertixes whose contents are changed by shifting,
1344098297b2SJeff Mahoney * and third the number of uncached vertixes whose contents are
1345098297b2SJeff Mahoney * changed by shifting and must be read from disk.
1346098297b2SJeff Mahoney */
13471da177e4SLinus Torvalds int nver, lnver, rnver, lrnver;
13481da177e4SLinus Torvalds
1349098297b2SJeff Mahoney /*
1350098297b2SJeff Mahoney * used at leaf level only, S0 = S[0] is the node being balanced,
1351098297b2SJeff Mahoney * sInum [ I = 0,1,2 ] is the number of items that will
1352098297b2SJeff Mahoney * remain in node SI after balancing. S1 and S2 are new
1353098297b2SJeff Mahoney * nodes that might be created.
1354098297b2SJeff Mahoney */
13551da177e4SLinus Torvalds
1356098297b2SJeff Mahoney /*
1357098297b2SJeff Mahoney * we perform 8 calls to get_num_ver(). For each call we
1358098297b2SJeff Mahoney * calculate five parameters. where 4th parameter is s1bytes
1359098297b2SJeff Mahoney * and 5th - s2bytes
1360098297b2SJeff Mahoney *
1361098297b2SJeff Mahoney * s0num, s1num, s2num for 8 cases
1362098297b2SJeff Mahoney * 0,1 - do not shift and do not shift but bottle
1363098297b2SJeff Mahoney * 2 - shift only whole item to left
1364098297b2SJeff Mahoney * 3 - shift to left and bottle as much as possible
1365098297b2SJeff Mahoney * 4,5 - shift to right (whole items and as much as possible
1366098297b2SJeff Mahoney * 6,7 - shift to both directions (whole items and as much as possible)
13671da177e4SLinus Torvalds */
1368098297b2SJeff Mahoney short snum012[40] = { 0, };
13691da177e4SLinus Torvalds
13701da177e4SLinus Torvalds /* Sh is the node whose balance is currently being checked */
13711da177e4SLinus Torvalds struct buffer_head *Sh;
13721da177e4SLinus Torvalds
13731da177e4SLinus Torvalds Sh = PATH_H_PBUFFER(tb->tb_path, h);
13741da177e4SLinus Torvalds levbytes = tb->insert_size[h];
13751da177e4SLinus Torvalds
13761da177e4SLinus Torvalds /* Calculate balance parameters for creating new root. */
13771da177e4SLinus Torvalds if (!Sh) {
13781da177e4SLinus Torvalds if (!h)
1379c3a9c210SJeff Mahoney reiserfs_panic(tb->tb_sb, "vs-8210",
1380c3a9c210SJeff Mahoney "S[0] can not be 0");
1381ee93961bSJeff Mahoney switch (ret = get_empty_nodes(tb, h)) {
1382098297b2SJeff Mahoney /* no balancing for higher levels needed */
13831da177e4SLinus Torvalds case CARRY_ON:
13841da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1385098297b2SJeff Mahoney return NO_BALANCING_NEEDED;
13861da177e4SLinus Torvalds
13871da177e4SLinus Torvalds case NO_DISK_SPACE:
13881da177e4SLinus Torvalds case REPEAT_SEARCH:
1389ee93961bSJeff Mahoney return ret;
13901da177e4SLinus Torvalds default:
1391c3a9c210SJeff Mahoney reiserfs_panic(tb->tb_sb, "vs-8215", "incorrect "
1392c3a9c210SJeff Mahoney "return value of get_empty_nodes");
13931da177e4SLinus Torvalds }
13941da177e4SLinus Torvalds }
13951da177e4SLinus Torvalds
1396098297b2SJeff Mahoney /* get parents of S[h] neighbors. */
1397098297b2SJeff Mahoney ret = get_parents(tb, h);
1398098297b2SJeff Mahoney if (ret != CARRY_ON)
1399ee93961bSJeff Mahoney return ret;
14001da177e4SLinus Torvalds
14011da177e4SLinus Torvalds sfree = B_FREE_SPACE(Sh);
14021da177e4SLinus Torvalds
14031da177e4SLinus Torvalds /* get free space of neighbors */
14041da177e4SLinus Torvalds rfree = get_rfree(tb, h);
14051da177e4SLinus Torvalds lfree = get_lfree(tb, h);
14061da177e4SLinus Torvalds
1407098297b2SJeff Mahoney /* and new item fits into node S[h] without any shifting */
1408bd4c625cSLinus Torvalds if (can_node_be_removed(vn->vn_mode, lfree, sfree, rfree, tb, h) ==
1409bd4c625cSLinus Torvalds NO_BALANCING_NEEDED)
14101da177e4SLinus Torvalds return NO_BALANCING_NEEDED;
14111da177e4SLinus Torvalds
14121da177e4SLinus Torvalds create_virtual_node(tb, h);
14131da177e4SLinus Torvalds
14141da177e4SLinus Torvalds /*
1415098297b2SJeff Mahoney * determine maximal number of items we can shift to the left
1416098297b2SJeff Mahoney * neighbor (in tb structure) and the maximal number of bytes
1417098297b2SJeff Mahoney * that can flow to the left neighbor from the left most liquid
1418098297b2SJeff Mahoney * item that cannot be shifted from S[0] entirely (returned value)
14191da177e4SLinus Torvalds */
14201da177e4SLinus Torvalds check_left(tb, h, lfree);
14211da177e4SLinus Torvalds
14221da177e4SLinus Torvalds /*
1423098297b2SJeff Mahoney * determine maximal number of items we can shift to the right
1424098297b2SJeff Mahoney * neighbor (in tb structure) and the maximal number of bytes
1425098297b2SJeff Mahoney * that can flow to the right neighbor from the right most liquid
1426098297b2SJeff Mahoney * item that cannot be shifted from S[0] entirely (returned value)
14271da177e4SLinus Torvalds */
14281da177e4SLinus Torvalds check_right(tb, h, rfree);
14291da177e4SLinus Torvalds
1430098297b2SJeff Mahoney /*
1431098297b2SJeff Mahoney * all contents of internal node S[h] can be moved into its
1432098297b2SJeff Mahoney * neighbors, S[h] will be removed after balancing
1433098297b2SJeff Mahoney */
14341da177e4SLinus Torvalds if (h && (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1)) {
14351da177e4SLinus Torvalds int to_r;
14361da177e4SLinus Torvalds
1437098297b2SJeff Mahoney /*
1438098297b2SJeff Mahoney * Since we are working on internal nodes, and our internal
1439098297b2SJeff Mahoney * nodes have fixed size entries, then we can balance by the
1440098297b2SJeff Mahoney * number of items rather than the space they consume. In this
1441098297b2SJeff Mahoney * routine we set the left node equal to the right node,
1442098297b2SJeff Mahoney * allowing a difference of less than or equal to 1 child
1443098297b2SJeff Mahoney * pointer.
1444098297b2SJeff Mahoney */
1445bd4c625cSLinus Torvalds to_r =
1446bd4c625cSLinus Torvalds ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1447bd4c625cSLinus Torvalds vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1448bd4c625cSLinus Torvalds tb->rnum[h]);
1449bd4c625cSLinus Torvalds set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1450bd4c625cSLinus Torvalds -1, -1);
14511da177e4SLinus Torvalds return CARRY_ON;
14521da177e4SLinus Torvalds }
14531da177e4SLinus Torvalds
1454098297b2SJeff Mahoney /*
1455098297b2SJeff Mahoney * this checks balance condition, that any two neighboring nodes
1456098297b2SJeff Mahoney * can not fit in one node
1457098297b2SJeff Mahoney */
14581da177e4SLinus Torvalds RFALSE(h &&
14591da177e4SLinus Torvalds (tb->lnum[h] >= vn->vn_nr_item + 1 ||
14601da177e4SLinus Torvalds tb->rnum[h] >= vn->vn_nr_item + 1),
14611da177e4SLinus Torvalds "vs-8220: tree is not balanced on internal level");
14621da177e4SLinus Torvalds RFALSE(!h && ((tb->lnum[h] >= vn->vn_nr_item && (tb->lbytes == -1)) ||
14631da177e4SLinus Torvalds (tb->rnum[h] >= vn->vn_nr_item && (tb->rbytes == -1))),
14641da177e4SLinus Torvalds "vs-8225: tree is not balanced on leaf level");
14651da177e4SLinus Torvalds
1466098297b2SJeff Mahoney /*
1467098297b2SJeff Mahoney * all contents of S[0] can be moved into its neighbors
1468098297b2SJeff Mahoney * S[0] will be removed after balancing.
1469098297b2SJeff Mahoney */
14701da177e4SLinus Torvalds if (!h && is_leaf_removable(tb))
14711da177e4SLinus Torvalds return CARRY_ON;
14721da177e4SLinus Torvalds
1473098297b2SJeff Mahoney /*
1474098297b2SJeff Mahoney * why do we perform this check here rather than earlier??
1475098297b2SJeff Mahoney * Answer: we can win 1 node in some cases above. Moreover we
1476098297b2SJeff Mahoney * checked it above, when we checked, that S[0] is not removable
1477098297b2SJeff Mahoney * in principle
1478098297b2SJeff Mahoney */
1479098297b2SJeff Mahoney
1480098297b2SJeff Mahoney /* new item fits into node S[h] without any shifting */
1481098297b2SJeff Mahoney if (sfree >= levbytes) {
14821da177e4SLinus Torvalds if (!h)
14831da177e4SLinus Torvalds tb->s0num = vn->vn_nr_item;
14841da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
14851da177e4SLinus Torvalds return NO_BALANCING_NEEDED;
14861da177e4SLinus Torvalds }
14871da177e4SLinus Torvalds
14881da177e4SLinus Torvalds {
14891da177e4SLinus Torvalds int lpar, rpar, nset, lset, rset, lrset;
1490098297b2SJeff Mahoney /* regular overflowing of the node */
14911da177e4SLinus Torvalds
1492098297b2SJeff Mahoney /*
1493098297b2SJeff Mahoney * get_num_ver works in 2 modes (FLOW & NO_FLOW)
1494098297b2SJeff Mahoney * lpar, rpar - number of items we can shift to left/right
1495098297b2SJeff Mahoney * neighbor (including splitting item)
1496098297b2SJeff Mahoney * nset, lset, rset, lrset - shows, whether flowing items
1497098297b2SJeff Mahoney * give better packing
14981da177e4SLinus Torvalds */
14991da177e4SLinus Torvalds #define FLOW 1
15001da177e4SLinus Torvalds #define NO_FLOW 0 /* do not any splitting */
15011da177e4SLinus Torvalds
1502098297b2SJeff Mahoney /* we choose one of the following */
15031da177e4SLinus Torvalds #define NOTHING_SHIFT_NO_FLOW 0
15041da177e4SLinus Torvalds #define NOTHING_SHIFT_FLOW 5
15051da177e4SLinus Torvalds #define LEFT_SHIFT_NO_FLOW 10
15061da177e4SLinus Torvalds #define LEFT_SHIFT_FLOW 15
15071da177e4SLinus Torvalds #define RIGHT_SHIFT_NO_FLOW 20
15081da177e4SLinus Torvalds #define RIGHT_SHIFT_FLOW 25
15091da177e4SLinus Torvalds #define LR_SHIFT_NO_FLOW 30
15101da177e4SLinus Torvalds #define LR_SHIFT_FLOW 35
15111da177e4SLinus Torvalds
15121da177e4SLinus Torvalds lpar = tb->lnum[h];
15131da177e4SLinus Torvalds rpar = tb->rnum[h];
15141da177e4SLinus Torvalds
1515098297b2SJeff Mahoney /*
1516098297b2SJeff Mahoney * calculate number of blocks S[h] must be split into when
1517098297b2SJeff Mahoney * nothing is shifted to the neighbors, as well as number of
1518098297b2SJeff Mahoney * items in each part of the split node (s012 numbers),
1519098297b2SJeff Mahoney * and number of bytes (s1bytes) of the shared drop which
1520098297b2SJeff Mahoney * flow to S1 if any
1521098297b2SJeff Mahoney */
15221da177e4SLinus Torvalds nset = NOTHING_SHIFT_NO_FLOW;
15231da177e4SLinus Torvalds nver = get_num_ver(vn->vn_mode, tb, h,
15241da177e4SLinus Torvalds 0, -1, h ? vn->vn_nr_item : 0, -1,
15251da177e4SLinus Torvalds snum012, NO_FLOW);
15261da177e4SLinus Torvalds
1527bd4c625cSLinus Torvalds if (!h) {
15281da177e4SLinus Torvalds int nver1;
15291da177e4SLinus Torvalds
1530098297b2SJeff Mahoney /*
1531098297b2SJeff Mahoney * note, that in this case we try to bottle
1532098297b2SJeff Mahoney * between S[0] and S1 (S1 - the first new node)
1533098297b2SJeff Mahoney */
15341da177e4SLinus Torvalds nver1 = get_num_ver(vn->vn_mode, tb, h,
15351da177e4SLinus Torvalds 0, -1, 0, -1,
15361da177e4SLinus Torvalds snum012 + NOTHING_SHIFT_FLOW, FLOW);
15371da177e4SLinus Torvalds if (nver > nver1)
15381da177e4SLinus Torvalds nset = NOTHING_SHIFT_FLOW, nver = nver1;
15391da177e4SLinus Torvalds }
15401da177e4SLinus Torvalds
1541098297b2SJeff Mahoney /*
1542098297b2SJeff Mahoney * calculate number of blocks S[h] must be split into when
1543098297b2SJeff Mahoney * l_shift_num first items and l_shift_bytes of the right
1544098297b2SJeff Mahoney * most liquid item to be shifted are shifted to the left
1545098297b2SJeff Mahoney * neighbor, as well as number of items in each part of the
1546098297b2SJeff Mahoney * splitted node (s012 numbers), and number of bytes
1547098297b2SJeff Mahoney * (s1bytes) of the shared drop which flow to S1 if any
15481da177e4SLinus Torvalds */
15491da177e4SLinus Torvalds lset = LEFT_SHIFT_NO_FLOW;
15501da177e4SLinus Torvalds lnver = get_num_ver(vn->vn_mode, tb, h,
1551bd4c625cSLinus Torvalds lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1552bd4c625cSLinus Torvalds -1, h ? vn->vn_nr_item : 0, -1,
15531da177e4SLinus Torvalds snum012 + LEFT_SHIFT_NO_FLOW, NO_FLOW);
1554bd4c625cSLinus Torvalds if (!h) {
15551da177e4SLinus Torvalds int lnver1;
15561da177e4SLinus Torvalds
15571da177e4SLinus Torvalds lnver1 = get_num_ver(vn->vn_mode, tb, h,
1558bd4c625cSLinus Torvalds lpar -
1559bd4c625cSLinus Torvalds ((tb->lbytes != -1) ? 1 : 0),
1560bd4c625cSLinus Torvalds tb->lbytes, 0, -1,
15611da177e4SLinus Torvalds snum012 + LEFT_SHIFT_FLOW, FLOW);
15621da177e4SLinus Torvalds if (lnver > lnver1)
15631da177e4SLinus Torvalds lset = LEFT_SHIFT_FLOW, lnver = lnver1;
15641da177e4SLinus Torvalds }
15651da177e4SLinus Torvalds
1566098297b2SJeff Mahoney /*
1567098297b2SJeff Mahoney * calculate number of blocks S[h] must be split into when
1568098297b2SJeff Mahoney * r_shift_num first items and r_shift_bytes of the left most
1569098297b2SJeff Mahoney * liquid item to be shifted are shifted to the right neighbor,
1570098297b2SJeff Mahoney * as well as number of items in each part of the splitted
1571098297b2SJeff Mahoney * node (s012 numbers), and number of bytes (s1bytes) of the
1572098297b2SJeff Mahoney * shared drop which flow to S1 if any
15731da177e4SLinus Torvalds */
15741da177e4SLinus Torvalds rset = RIGHT_SHIFT_NO_FLOW;
15751da177e4SLinus Torvalds rnver = get_num_ver(vn->vn_mode, tb, h,
1576bd4c625cSLinus Torvalds 0, -1,
1577bd4c625cSLinus Torvalds h ? (vn->vn_nr_item - rpar) : (rpar -
1578bd4c625cSLinus Torvalds ((tb->
1579bd4c625cSLinus Torvalds rbytes !=
1580bd4c625cSLinus Torvalds -1) ? 1 :
1581bd4c625cSLinus Torvalds 0)), -1,
15821da177e4SLinus Torvalds snum012 + RIGHT_SHIFT_NO_FLOW, NO_FLOW);
1583bd4c625cSLinus Torvalds if (!h) {
15841da177e4SLinus Torvalds int rnver1;
15851da177e4SLinus Torvalds
15861da177e4SLinus Torvalds rnver1 = get_num_ver(vn->vn_mode, tb, h,
1587bd4c625cSLinus Torvalds 0, -1,
1588bd4c625cSLinus Torvalds (rpar -
1589bd4c625cSLinus Torvalds ((tb->rbytes != -1) ? 1 : 0)),
1590bd4c625cSLinus Torvalds tb->rbytes,
15911da177e4SLinus Torvalds snum012 + RIGHT_SHIFT_FLOW, FLOW);
15921da177e4SLinus Torvalds
15931da177e4SLinus Torvalds if (rnver > rnver1)
15941da177e4SLinus Torvalds rset = RIGHT_SHIFT_FLOW, rnver = rnver1;
15951da177e4SLinus Torvalds }
15961da177e4SLinus Torvalds
1597098297b2SJeff Mahoney /*
1598098297b2SJeff Mahoney * calculate number of blocks S[h] must be split into when
1599098297b2SJeff Mahoney * items are shifted in both directions, as well as number
1600098297b2SJeff Mahoney * of items in each part of the splitted node (s012 numbers),
1601098297b2SJeff Mahoney * and number of bytes (s1bytes) of the shared drop which
1602098297b2SJeff Mahoney * flow to S1 if any
16031da177e4SLinus Torvalds */
16041da177e4SLinus Torvalds lrset = LR_SHIFT_NO_FLOW;
16051da177e4SLinus Torvalds lrnver = get_num_ver(vn->vn_mode, tb, h,
1606bd4c625cSLinus Torvalds lpar - ((h || tb->lbytes == -1) ? 0 : 1),
1607bd4c625cSLinus Torvalds -1,
1608bd4c625cSLinus Torvalds h ? (vn->vn_nr_item - rpar) : (rpar -
1609bd4c625cSLinus Torvalds ((tb->
1610bd4c625cSLinus Torvalds rbytes !=
1611bd4c625cSLinus Torvalds -1) ? 1 :
1612bd4c625cSLinus Torvalds 0)), -1,
16131da177e4SLinus Torvalds snum012 + LR_SHIFT_NO_FLOW, NO_FLOW);
1614bd4c625cSLinus Torvalds if (!h) {
16151da177e4SLinus Torvalds int lrnver1;
16161da177e4SLinus Torvalds
16171da177e4SLinus Torvalds lrnver1 = get_num_ver(vn->vn_mode, tb, h,
1618bd4c625cSLinus Torvalds lpar -
1619bd4c625cSLinus Torvalds ((tb->lbytes != -1) ? 1 : 0),
1620bd4c625cSLinus Torvalds tb->lbytes,
1621bd4c625cSLinus Torvalds (rpar -
1622bd4c625cSLinus Torvalds ((tb->rbytes != -1) ? 1 : 0)),
1623bd4c625cSLinus Torvalds tb->rbytes,
16241da177e4SLinus Torvalds snum012 + LR_SHIFT_FLOW, FLOW);
16251da177e4SLinus Torvalds if (lrnver > lrnver1)
16261da177e4SLinus Torvalds lrset = LR_SHIFT_FLOW, lrnver = lrnver1;
16271da177e4SLinus Torvalds }
16281da177e4SLinus Torvalds
1629098297b2SJeff Mahoney /*
1630098297b2SJeff Mahoney * Our general shifting strategy is:
1631098297b2SJeff Mahoney * 1) to minimized number of new nodes;
1632098297b2SJeff Mahoney * 2) to minimized number of neighbors involved in shifting;
1633098297b2SJeff Mahoney * 3) to minimized number of disk reads;
1634098297b2SJeff Mahoney */
16351da177e4SLinus Torvalds
16361da177e4SLinus Torvalds /* we can win TWO or ONE nodes by shifting in both directions */
1637bd4c625cSLinus Torvalds if (lrnver < lnver && lrnver < rnver) {
16381da177e4SLinus Torvalds RFALSE(h &&
16391da177e4SLinus Torvalds (tb->lnum[h] != 1 ||
16401da177e4SLinus Torvalds tb->rnum[h] != 1 ||
1641bd4c625cSLinus Torvalds lrnver != 1 || rnver != 2 || lnver != 2
1642bd4c625cSLinus Torvalds || h != 1), "vs-8230: bad h");
16431da177e4SLinus Torvalds if (lrset == LR_SHIFT_FLOW)
1644bd4c625cSLinus Torvalds set_parameters(tb, h, tb->lnum[h], tb->rnum[h],
1645bd4c625cSLinus Torvalds lrnver, snum012 + lrset,
16461da177e4SLinus Torvalds tb->lbytes, tb->rbytes);
16471da177e4SLinus Torvalds else
1648bd4c625cSLinus Torvalds set_parameters(tb, h,
1649bd4c625cSLinus Torvalds tb->lnum[h] -
1650bd4c625cSLinus Torvalds ((tb->lbytes == -1) ? 0 : 1),
1651bd4c625cSLinus Torvalds tb->rnum[h] -
1652bd4c625cSLinus Torvalds ((tb->rbytes == -1) ? 0 : 1),
1653bd4c625cSLinus Torvalds lrnver, snum012 + lrset, -1, -1);
16541da177e4SLinus Torvalds
16551da177e4SLinus Torvalds return CARRY_ON;
16561da177e4SLinus Torvalds }
16571da177e4SLinus Torvalds
1658098297b2SJeff Mahoney /*
1659098297b2SJeff Mahoney * if shifting doesn't lead to better packing
1660098297b2SJeff Mahoney * then don't shift
1661098297b2SJeff Mahoney */
1662bd4c625cSLinus Torvalds if (nver == lrnver) {
1663bd4c625cSLinus Torvalds set_parameters(tb, h, 0, 0, nver, snum012 + nset, -1,
1664bd4c625cSLinus Torvalds -1);
16651da177e4SLinus Torvalds return CARRY_ON;
16661da177e4SLinus Torvalds }
16671da177e4SLinus Torvalds
1668098297b2SJeff Mahoney /*
1669098297b2SJeff Mahoney * now we know that for better packing shifting in only one
1670098297b2SJeff Mahoney * direction either to the left or to the right is required
1671098297b2SJeff Mahoney */
16721da177e4SLinus Torvalds
1673098297b2SJeff Mahoney /*
1674098297b2SJeff Mahoney * if shifting to the left is better than
1675098297b2SJeff Mahoney * shifting to the right
1676098297b2SJeff Mahoney */
1677bd4c625cSLinus Torvalds if (lnver < rnver) {
16781da177e4SLinus Torvalds SET_PAR_SHIFT_LEFT;
16791da177e4SLinus Torvalds return CARRY_ON;
16801da177e4SLinus Torvalds }
16811da177e4SLinus Torvalds
1682098297b2SJeff Mahoney /*
1683098297b2SJeff Mahoney * if shifting to the right is better than
1684098297b2SJeff Mahoney * shifting to the left
1685098297b2SJeff Mahoney */
1686bd4c625cSLinus Torvalds if (lnver > rnver) {
16871da177e4SLinus Torvalds SET_PAR_SHIFT_RIGHT;
16881da177e4SLinus Torvalds return CARRY_ON;
16891da177e4SLinus Torvalds }
16901da177e4SLinus Torvalds
1691098297b2SJeff Mahoney /*
1692098297b2SJeff Mahoney * now shifting in either direction gives the same number
1693098297b2SJeff Mahoney * of nodes and we can make use of the cached neighbors
1694098297b2SJeff Mahoney */
1695bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h)) {
16961da177e4SLinus Torvalds SET_PAR_SHIFT_LEFT;
16971da177e4SLinus Torvalds return CARRY_ON;
16981da177e4SLinus Torvalds }
16991da177e4SLinus Torvalds
1700098297b2SJeff Mahoney /*
1701098297b2SJeff Mahoney * shift to the right independently on whether the
1702098297b2SJeff Mahoney * right neighbor in cache or not
1703098297b2SJeff Mahoney */
17041da177e4SLinus Torvalds SET_PAR_SHIFT_RIGHT;
17051da177e4SLinus Torvalds return CARRY_ON;
17061da177e4SLinus Torvalds }
17071da177e4SLinus Torvalds }
17081da177e4SLinus Torvalds
1709098297b2SJeff Mahoney /*
1710098297b2SJeff Mahoney * Check whether current node S[h] is balanced when Decreasing its size by
17111da177e4SLinus Torvalds * Deleting or Cutting for INTERNAL node of S+tree.
17121da177e4SLinus Torvalds * Calculate parameters for balancing for current level h.
17131da177e4SLinus Torvalds * Parameters:
17141da177e4SLinus Torvalds * tb tree_balance structure;
17151da177e4SLinus Torvalds * h current level of the node;
17161da177e4SLinus Torvalds * inum item number in S[h];
17171da177e4SLinus Torvalds * mode i - insert, p - paste;
17181da177e4SLinus Torvalds * Returns: 1 - schedule occurred;
17191da177e4SLinus Torvalds * 0 - balancing for higher levels needed;
17201da177e4SLinus Torvalds * -1 - no balancing for higher levels needed;
17211da177e4SLinus Torvalds * -2 - no disk space.
17221da177e4SLinus Torvalds *
17231da177e4SLinus Torvalds * Note: Items of internal nodes have fixed size, so the balance condition for
17241da177e4SLinus Torvalds * the internal part of S+tree is as for the B-trees.
17251da177e4SLinus Torvalds */
dc_check_balance_internal(struct tree_balance * tb,int h)17261da177e4SLinus Torvalds static int dc_check_balance_internal(struct tree_balance *tb, int h)
17271da177e4SLinus Torvalds {
17281da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
17291da177e4SLinus Torvalds
1730098297b2SJeff Mahoney /*
1731098297b2SJeff Mahoney * Sh is the node whose balance is currently being checked,
1732098297b2SJeff Mahoney * and Fh is its father.
1733098297b2SJeff Mahoney */
17341da177e4SLinus Torvalds struct buffer_head *Sh, *Fh;
17354fadcd1cSzhengbin int ret;
17361da177e4SLinus Torvalds int lfree, rfree /* free space in L and R */ ;
17371da177e4SLinus Torvalds
17381da177e4SLinus Torvalds Sh = PATH_H_PBUFFER(tb->tb_path, h);
17391da177e4SLinus Torvalds Fh = PATH_H_PPARENT(tb->tb_path, h);
17401da177e4SLinus Torvalds
1741098297b2SJeff Mahoney /*
1742098297b2SJeff Mahoney * using tb->insert_size[h], which is negative in this case,
1743098297b2SJeff Mahoney * create_virtual_node calculates:
1744098297b2SJeff Mahoney * new_nr_item = number of items node would have if operation is
1745098297b2SJeff Mahoney * performed without balancing (new_nr_item);
1746098297b2SJeff Mahoney */
17471da177e4SLinus Torvalds create_virtual_node(tb, h);
17481da177e4SLinus Torvalds
1749bd4c625cSLinus Torvalds if (!Fh) { /* S[h] is the root. */
1750098297b2SJeff Mahoney /* no balancing for higher levels needed */
1751bd4c625cSLinus Torvalds if (vn->vn_nr_item > 0) {
17521da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
1753098297b2SJeff Mahoney return NO_BALANCING_NEEDED;
17541da177e4SLinus Torvalds }
1755098297b2SJeff Mahoney /*
1756098297b2SJeff Mahoney * new_nr_item == 0.
17571da177e4SLinus Torvalds * Current root will be deleted resulting in
1758098297b2SJeff Mahoney * decrementing the tree height.
1759098297b2SJeff Mahoney */
17601da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 0, NULL, -1, -1);
17611da177e4SLinus Torvalds return CARRY_ON;
17621da177e4SLinus Torvalds }
17631da177e4SLinus Torvalds
1764ee93961bSJeff Mahoney if ((ret = get_parents(tb, h)) != CARRY_ON)
1765ee93961bSJeff Mahoney return ret;
17661da177e4SLinus Torvalds
17671da177e4SLinus Torvalds /* get free space of neighbors */
17681da177e4SLinus Torvalds rfree = get_rfree(tb, h);
17691da177e4SLinus Torvalds lfree = get_lfree(tb, h);
17701da177e4SLinus Torvalds
17711da177e4SLinus Torvalds /* determine maximal number of items we can fit into neighbors */
17721da177e4SLinus Torvalds check_left(tb, h, lfree);
17731da177e4SLinus Torvalds check_right(tb, h, rfree);
17741da177e4SLinus Torvalds
1775098297b2SJeff Mahoney /*
1776098297b2SJeff Mahoney * Balance condition for the internal node is valid.
1777098297b2SJeff Mahoney * In this case we balance only if it leads to better packing.
1778098297b2SJeff Mahoney */
1779098297b2SJeff Mahoney if (vn->vn_nr_item >= MIN_NR_KEY(Sh)) {
1780098297b2SJeff Mahoney /*
1781098297b2SJeff Mahoney * Here we join S[h] with one of its neighbors,
1782098297b2SJeff Mahoney * which is impossible with greater values of new_nr_item.
1783098297b2SJeff Mahoney */
1784098297b2SJeff Mahoney if (vn->vn_nr_item == MIN_NR_KEY(Sh)) {
17851da177e4SLinus Torvalds /* All contents of S[h] can be moved to L[h]. */
1786098297b2SJeff Mahoney if (tb->lnum[h] >= vn->vn_nr_item + 1) {
17871da177e4SLinus Torvalds int n;
17881da177e4SLinus Torvalds int order_L;
17891da177e4SLinus Torvalds
1790bd4c625cSLinus Torvalds order_L =
1791bd4c625cSLinus Torvalds ((n =
1792bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path,
1793bd4c625cSLinus Torvalds h)) ==
1794bd4c625cSLinus Torvalds 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1795bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FL[h], order_L)) /
1796bd4c625cSLinus Torvalds (DC_SIZE + KEY_SIZE);
1797bd4c625cSLinus Torvalds set_parameters(tb, h, -n - 1, 0, 0, NULL, -1,
1798bd4c625cSLinus Torvalds -1);
17991da177e4SLinus Torvalds return CARRY_ON;
18001da177e4SLinus Torvalds }
18011da177e4SLinus Torvalds
18021da177e4SLinus Torvalds /* All contents of S[h] can be moved to R[h]. */
1803098297b2SJeff Mahoney if (tb->rnum[h] >= vn->vn_nr_item + 1) {
18041da177e4SLinus Torvalds int n;
18051da177e4SLinus Torvalds int order_R;
18061da177e4SLinus Torvalds
1807bd4c625cSLinus Torvalds order_R =
1808bd4c625cSLinus Torvalds ((n =
1809bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path,
1810bd4c625cSLinus Torvalds h)) ==
1811bd4c625cSLinus Torvalds B_NR_ITEMS(Fh)) ? 0 : n + 1;
1812bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FR[h], order_R)) /
1813bd4c625cSLinus Torvalds (DC_SIZE + KEY_SIZE);
1814bd4c625cSLinus Torvalds set_parameters(tb, h, 0, -n - 1, 0, NULL, -1,
1815bd4c625cSLinus Torvalds -1);
18161da177e4SLinus Torvalds return CARRY_ON;
18171da177e4SLinus Torvalds }
18181da177e4SLinus Torvalds }
18191da177e4SLinus Torvalds
1820098297b2SJeff Mahoney /*
1821098297b2SJeff Mahoney * All contents of S[h] can be moved to the neighbors
1822098297b2SJeff Mahoney * (L[h] & R[h]).
1823098297b2SJeff Mahoney */
1824bd4c625cSLinus Torvalds if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
18251da177e4SLinus Torvalds int to_r;
18261da177e4SLinus Torvalds
1827bd4c625cSLinus Torvalds to_r =
1828bd4c625cSLinus Torvalds ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] -
1829bd4c625cSLinus Torvalds tb->rnum[h] + vn->vn_nr_item + 1) / 2 -
18301da177e4SLinus Torvalds (MAX_NR_KEY(Sh) + 1 - tb->rnum[h]);
1831bd4c625cSLinus Torvalds set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r,
1832bd4c625cSLinus Torvalds 0, NULL, -1, -1);
18331da177e4SLinus Torvalds return CARRY_ON;
18341da177e4SLinus Torvalds }
18351da177e4SLinus Torvalds
18361da177e4SLinus Torvalds /* Balancing does not lead to better packing. */
18371da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
18381da177e4SLinus Torvalds return NO_BALANCING_NEEDED;
18391da177e4SLinus Torvalds }
18401da177e4SLinus Torvalds
1841098297b2SJeff Mahoney /*
1842098297b2SJeff Mahoney * Current node contain insufficient number of items.
1843098297b2SJeff Mahoney * Balancing is required.
1844098297b2SJeff Mahoney */
18451da177e4SLinus Torvalds /* Check whether we can merge S[h] with left neighbor. */
18461da177e4SLinus Torvalds if (tb->lnum[h] >= vn->vn_nr_item + 1)
1847bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h)
1848bd4c625cSLinus Torvalds || tb->rnum[h] < vn->vn_nr_item + 1 || !tb->FR[h]) {
18491da177e4SLinus Torvalds int n;
18501da177e4SLinus Torvalds int order_L;
18511da177e4SLinus Torvalds
1852bd4c625cSLinus Torvalds order_L =
1853bd4c625cSLinus Torvalds ((n =
1854bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path,
1855bd4c625cSLinus Torvalds h)) ==
1856bd4c625cSLinus Torvalds 0) ? B_NR_ITEMS(tb->FL[h]) : n - 1;
1857bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FL[h], order_L)) / (DC_SIZE +
1858bd4c625cSLinus Torvalds KEY_SIZE);
18591da177e4SLinus Torvalds set_parameters(tb, h, -n - 1, 0, 0, NULL, -1, -1);
18601da177e4SLinus Torvalds return CARRY_ON;
18611da177e4SLinus Torvalds }
18621da177e4SLinus Torvalds
18631da177e4SLinus Torvalds /* Check whether we can merge S[h] with right neighbor. */
1864bd4c625cSLinus Torvalds if (tb->rnum[h] >= vn->vn_nr_item + 1) {
18651da177e4SLinus Torvalds int n;
18661da177e4SLinus Torvalds int order_R;
18671da177e4SLinus Torvalds
1868bd4c625cSLinus Torvalds order_R =
1869bd4c625cSLinus Torvalds ((n =
1870bd4c625cSLinus Torvalds PATH_H_B_ITEM_ORDER(tb->tb_path,
1871bd4c625cSLinus Torvalds h)) == B_NR_ITEMS(Fh)) ? 0 : (n + 1);
1872bd4c625cSLinus Torvalds n = dc_size(B_N_CHILD(tb->FR[h], order_R)) / (DC_SIZE +
1873bd4c625cSLinus Torvalds KEY_SIZE);
18741da177e4SLinus Torvalds set_parameters(tb, h, 0, -n - 1, 0, NULL, -1, -1);
18751da177e4SLinus Torvalds return CARRY_ON;
18761da177e4SLinus Torvalds }
18771da177e4SLinus Torvalds
18781da177e4SLinus Torvalds /* All contents of S[h] can be moved to the neighbors (L[h] & R[h]). */
1879bd4c625cSLinus Torvalds if (tb->rnum[h] + tb->lnum[h] >= vn->vn_nr_item + 1) {
18801da177e4SLinus Torvalds int to_r;
18811da177e4SLinus Torvalds
1882bd4c625cSLinus Torvalds to_r =
1883bd4c625cSLinus Torvalds ((MAX_NR_KEY(Sh) << 1) + 2 - tb->lnum[h] - tb->rnum[h] +
1884bd4c625cSLinus Torvalds vn->vn_nr_item + 1) / 2 - (MAX_NR_KEY(Sh) + 1 -
1885bd4c625cSLinus Torvalds tb->rnum[h]);
1886bd4c625cSLinus Torvalds set_parameters(tb, h, vn->vn_nr_item + 1 - to_r, to_r, 0, NULL,
1887bd4c625cSLinus Torvalds -1, -1);
18881da177e4SLinus Torvalds return CARRY_ON;
18891da177e4SLinus Torvalds }
18901da177e4SLinus Torvalds
18911da177e4SLinus Torvalds /* For internal nodes try to borrow item from a neighbor */
18921da177e4SLinus Torvalds RFALSE(!tb->FL[h] && !tb->FR[h], "vs-8235: trying to borrow for root");
18931da177e4SLinus Torvalds
18941da177e4SLinus Torvalds /* Borrow one or two items from caching neighbor */
1895bd4c625cSLinus Torvalds if (is_left_neighbor_in_cache(tb, h) || !tb->FR[h]) {
18961da177e4SLinus Torvalds int from_l;
18971da177e4SLinus Torvalds
1898bd4c625cSLinus Torvalds from_l =
1899bd4c625cSLinus Torvalds (MAX_NR_KEY(Sh) + 1 - tb->lnum[h] + vn->vn_nr_item +
1900bd4c625cSLinus Torvalds 1) / 2 - (vn->vn_nr_item + 1);
19011da177e4SLinus Torvalds set_parameters(tb, h, -from_l, 0, 1, NULL, -1, -1);
19021da177e4SLinus Torvalds return CARRY_ON;
19031da177e4SLinus Torvalds }
19041da177e4SLinus Torvalds
1905bd4c625cSLinus Torvalds set_parameters(tb, h, 0,
1906bd4c625cSLinus Torvalds -((MAX_NR_KEY(Sh) + 1 - tb->rnum[h] + vn->vn_nr_item +
1907bd4c625cSLinus Torvalds 1) / 2 - (vn->vn_nr_item + 1)), 1, NULL, -1, -1);
19081da177e4SLinus Torvalds return CARRY_ON;
19091da177e4SLinus Torvalds }
19101da177e4SLinus Torvalds
1911098297b2SJeff Mahoney /*
1912098297b2SJeff Mahoney * Check whether current node S[h] is balanced when Decreasing its size by
19131da177e4SLinus Torvalds * Deleting or Truncating for LEAF node of S+tree.
19141da177e4SLinus Torvalds * Calculate parameters for balancing for current level h.
19151da177e4SLinus Torvalds * Parameters:
19161da177e4SLinus Torvalds * tb tree_balance structure;
19171da177e4SLinus Torvalds * h current level of the node;
19181da177e4SLinus Torvalds * inum item number in S[h];
19191da177e4SLinus Torvalds * mode i - insert, p - paste;
19201da177e4SLinus Torvalds * Returns: 1 - schedule occurred;
19211da177e4SLinus Torvalds * 0 - balancing for higher levels needed;
19221da177e4SLinus Torvalds * -1 - no balancing for higher levels needed;
19231da177e4SLinus Torvalds * -2 - no disk space.
19241da177e4SLinus Torvalds */
dc_check_balance_leaf(struct tree_balance * tb,int h)19251da177e4SLinus Torvalds static int dc_check_balance_leaf(struct tree_balance *tb, int h)
19261da177e4SLinus Torvalds {
19271da177e4SLinus Torvalds struct virtual_node *vn = tb->tb_vn;
19281da177e4SLinus Torvalds
1929098297b2SJeff Mahoney /*
1930098297b2SJeff Mahoney * Number of bytes that must be deleted from
1931098297b2SJeff Mahoney * (value is negative if bytes are deleted) buffer which
1932098297b2SJeff Mahoney * contains node being balanced. The mnemonic is that the
1933098297b2SJeff Mahoney * attempted change in node space used level is levbytes bytes.
1934098297b2SJeff Mahoney */
19351da177e4SLinus Torvalds int levbytes;
1936098297b2SJeff Mahoney
19371da177e4SLinus Torvalds /* the maximal item size */
1938ee93961bSJeff Mahoney int maxsize, ret;
1939098297b2SJeff Mahoney
1940098297b2SJeff Mahoney /*
1941098297b2SJeff Mahoney * S0 is the node whose balance is currently being checked,
1942098297b2SJeff Mahoney * and F0 is its father.
1943098297b2SJeff Mahoney */
19441da177e4SLinus Torvalds struct buffer_head *S0, *F0;
19451da177e4SLinus Torvalds int lfree, rfree /* free space in L and R */ ;
19461da177e4SLinus Torvalds
19471da177e4SLinus Torvalds S0 = PATH_H_PBUFFER(tb->tb_path, 0);
19481da177e4SLinus Torvalds F0 = PATH_H_PPARENT(tb->tb_path, 0);
19491da177e4SLinus Torvalds
19501da177e4SLinus Torvalds levbytes = tb->insert_size[h];
19511da177e4SLinus Torvalds
19521da177e4SLinus Torvalds maxsize = MAX_CHILD_SIZE(S0); /* maximal possible size of an item */
19531da177e4SLinus Torvalds
1954bd4c625cSLinus Torvalds if (!F0) { /* S[0] is the root now. */
19551da177e4SLinus Torvalds
19561da177e4SLinus Torvalds RFALSE(-levbytes >= maxsize - B_FREE_SPACE(S0),
19571da177e4SLinus Torvalds "vs-8240: attempt to create empty buffer tree");
19581da177e4SLinus Torvalds
19591da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
19601da177e4SLinus Torvalds return NO_BALANCING_NEEDED;
19611da177e4SLinus Torvalds }
19621da177e4SLinus Torvalds
1963ee93961bSJeff Mahoney if ((ret = get_parents(tb, h)) != CARRY_ON)
1964ee93961bSJeff Mahoney return ret;
19651da177e4SLinus Torvalds
19661da177e4SLinus Torvalds /* get free space of neighbors */
19671da177e4SLinus Torvalds rfree = get_rfree(tb, h);
19681da177e4SLinus Torvalds lfree = get_lfree(tb, h);
19691da177e4SLinus Torvalds
19701da177e4SLinus Torvalds create_virtual_node(tb, h);
19711da177e4SLinus Torvalds
19721da177e4SLinus Torvalds /* if 3 leaves can be merge to one, set parameters and return */
19731da177e4SLinus Torvalds if (are_leaves_removable(tb, lfree, rfree))
19741da177e4SLinus Torvalds return CARRY_ON;
19751da177e4SLinus Torvalds
1976098297b2SJeff Mahoney /*
1977098297b2SJeff Mahoney * determine maximal number of items we can shift to the left/right
1978098297b2SJeff Mahoney * neighbor and the maximal number of bytes that can flow to the
1979098297b2SJeff Mahoney * left/right neighbor from the left/right most liquid item that
1980098297b2SJeff Mahoney * cannot be shifted from S[0] entirely
19811da177e4SLinus Torvalds */
19821da177e4SLinus Torvalds check_left(tb, h, lfree);
19831da177e4SLinus Torvalds check_right(tb, h, rfree);
19841da177e4SLinus Torvalds
19851da177e4SLinus Torvalds /* check whether we can merge S with left neighbor. */
19861da177e4SLinus Torvalds if (tb->lnum[0] >= vn->vn_nr_item && tb->lbytes == -1)
1987bd4c625cSLinus Torvalds 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 */
19881da177e4SLinus Torvalds !tb->FR[h]) {
19891da177e4SLinus Torvalds
1990bd4c625cSLinus Torvalds RFALSE(!tb->FL[h],
1991bd4c625cSLinus Torvalds "vs-8245: dc_check_balance_leaf: FL[h] must exist");
19921da177e4SLinus Torvalds
19931da177e4SLinus Torvalds /* set parameter to merge S[0] with its left neighbor */
19941da177e4SLinus Torvalds set_parameters(tb, h, -1, 0, 0, NULL, -1, -1);
19951da177e4SLinus Torvalds return CARRY_ON;
19961da177e4SLinus Torvalds }
19971da177e4SLinus Torvalds
19981da177e4SLinus Torvalds /* check whether we can merge S[0] with right neighbor. */
19991da177e4SLinus Torvalds if (tb->rnum[0] >= vn->vn_nr_item && tb->rbytes == -1) {
20001da177e4SLinus Torvalds set_parameters(tb, h, 0, -1, 0, NULL, -1, -1);
20011da177e4SLinus Torvalds return CARRY_ON;
20021da177e4SLinus Torvalds }
20031da177e4SLinus Torvalds
2004098297b2SJeff Mahoney /*
2005098297b2SJeff Mahoney * All contents of S[0] can be moved to the neighbors (L[0] & R[0]).
2006098297b2SJeff Mahoney * Set parameters and return
2007098297b2SJeff Mahoney */
20081da177e4SLinus Torvalds if (is_leaf_removable(tb))
20091da177e4SLinus Torvalds return CARRY_ON;
20101da177e4SLinus Torvalds
20111da177e4SLinus Torvalds /* Balancing is not required. */
20121da177e4SLinus Torvalds tb->s0num = vn->vn_nr_item;
20131da177e4SLinus Torvalds set_parameters(tb, h, 0, 0, 1, NULL, -1, -1);
20141da177e4SLinus Torvalds return NO_BALANCING_NEEDED;
20151da177e4SLinus Torvalds }
20161da177e4SLinus Torvalds
2017098297b2SJeff Mahoney /*
2018098297b2SJeff Mahoney * Check whether current node S[h] is balanced when Decreasing its size by
20191da177e4SLinus Torvalds * Deleting or Cutting.
20201da177e4SLinus Torvalds * Calculate parameters for balancing for current level h.
20211da177e4SLinus Torvalds * Parameters:
20221da177e4SLinus Torvalds * tb tree_balance structure;
20231da177e4SLinus Torvalds * h current level of the node;
20241da177e4SLinus Torvalds * inum item number in S[h];
20251da177e4SLinus Torvalds * mode d - delete, c - cut.
20261da177e4SLinus Torvalds * Returns: 1 - schedule occurred;
20271da177e4SLinus Torvalds * 0 - balancing for higher levels needed;
20281da177e4SLinus Torvalds * -1 - no balancing for higher levels needed;
20291da177e4SLinus Torvalds * -2 - no disk space.
20301da177e4SLinus Torvalds */
dc_check_balance(struct tree_balance * tb,int h)20311da177e4SLinus Torvalds static int dc_check_balance(struct tree_balance *tb, int h)
20321da177e4SLinus Torvalds {
2033bd4c625cSLinus Torvalds RFALSE(!(PATH_H_PBUFFER(tb->tb_path, h)),
2034bd4c625cSLinus Torvalds "vs-8250: S is not initialized");
20351da177e4SLinus Torvalds
20361da177e4SLinus Torvalds if (h)
20371da177e4SLinus Torvalds return dc_check_balance_internal(tb, h);
20381da177e4SLinus Torvalds else
20391da177e4SLinus Torvalds return dc_check_balance_leaf(tb, h);
20401da177e4SLinus Torvalds }
20411da177e4SLinus Torvalds
2042098297b2SJeff Mahoney /*
2043098297b2SJeff Mahoney * Check whether current node S[h] is balanced.
20441da177e4SLinus Torvalds * Calculate parameters for balancing for current level h.
20451da177e4SLinus Torvalds * Parameters:
20461da177e4SLinus Torvalds *
20471da177e4SLinus Torvalds * tb tree_balance structure:
20481da177e4SLinus Torvalds *
2049098297b2SJeff Mahoney * tb is a large structure that must be read about in the header
2050098297b2SJeff Mahoney * file at the same time as this procedure if the reader is
2051098297b2SJeff Mahoney * to successfully understand this procedure
20521da177e4SLinus Torvalds *
20531da177e4SLinus Torvalds * h current level of the node;
20541da177e4SLinus Torvalds * inum item number in S[h];
20551da177e4SLinus Torvalds * mode i - insert, p - paste, d - delete, c - cut.
20561da177e4SLinus Torvalds * Returns: 1 - schedule occurred;
20571da177e4SLinus Torvalds * 0 - balancing for higher levels needed;
20581da177e4SLinus Torvalds * -1 - no balancing for higher levels needed;
20591da177e4SLinus Torvalds * -2 - no disk space.
20601da177e4SLinus Torvalds */
check_balance(int mode,struct tree_balance * tb,int h,int inum,int pos_in_item,struct item_head * ins_ih,const void * data)20611da177e4SLinus Torvalds static int check_balance(int mode,
20621da177e4SLinus Torvalds struct tree_balance *tb,
20631da177e4SLinus Torvalds int h,
20641da177e4SLinus Torvalds int inum,
20651da177e4SLinus Torvalds int pos_in_item,
2066bd4c625cSLinus Torvalds struct item_head *ins_ih, const void *data)
20671da177e4SLinus Torvalds {
20681da177e4SLinus Torvalds struct virtual_node *vn;
20691da177e4SLinus Torvalds
20701da177e4SLinus Torvalds vn = tb->tb_vn = (struct virtual_node *)(tb->vn_buf);
20711da177e4SLinus Torvalds vn->vn_free_ptr = (char *)(tb->tb_vn + 1);
20721da177e4SLinus Torvalds vn->vn_mode = mode;
20731da177e4SLinus Torvalds vn->vn_affected_item_num = inum;
20741da177e4SLinus Torvalds vn->vn_pos_in_item = pos_in_item;
20751da177e4SLinus Torvalds vn->vn_ins_ih = ins_ih;
20761da177e4SLinus Torvalds vn->vn_data = data;
20771da177e4SLinus Torvalds
20781da177e4SLinus Torvalds RFALSE(mode == M_INSERT && !vn->vn_ins_ih,
20791da177e4SLinus Torvalds "vs-8255: ins_ih can not be 0 in insert mode");
20801da177e4SLinus Torvalds
20811da177e4SLinus Torvalds /* Calculate balance parameters when size of node is increasing. */
2082098297b2SJeff Mahoney if (tb->insert_size[h] > 0)
20831da177e4SLinus Torvalds return ip_check_balance(tb, h);
20841da177e4SLinus Torvalds
20851da177e4SLinus Torvalds /* Calculate balance parameters when size of node is decreasing. */
20861da177e4SLinus Torvalds return dc_check_balance(tb, h);
20871da177e4SLinus Torvalds }
20881da177e4SLinus Torvalds
20891da177e4SLinus Torvalds /* Check whether parent at the path is the really parent of the current node.*/
get_direct_parent(struct tree_balance * tb,int h)2090ee93961bSJeff Mahoney static int get_direct_parent(struct tree_balance *tb, int h)
2091bd4c625cSLinus Torvalds {
2092ad31a4fcSJeff Mahoney struct buffer_head *bh;
2093d68caa95SJeff Mahoney struct treepath *path = tb->tb_path;
2094ee93961bSJeff Mahoney int position,
2095ee93961bSJeff Mahoney path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h);
20961da177e4SLinus Torvalds
20971da177e4SLinus Torvalds /* We are in the root or in the new root. */
2098ee93961bSJeff Mahoney if (path_offset <= FIRST_PATH_ELEMENT_OFFSET) {
20991da177e4SLinus Torvalds
2100ee93961bSJeff Mahoney RFALSE(path_offset < FIRST_PATH_ELEMENT_OFFSET - 1,
21011da177e4SLinus Torvalds "PAP-8260: invalid offset in the path");
21021da177e4SLinus Torvalds
2103d68caa95SJeff Mahoney if (PATH_OFFSET_PBUFFER(path, FIRST_PATH_ELEMENT_OFFSET)->
2104a063ae17SJeff Mahoney b_blocknr == SB_ROOT_BLOCK(tb->tb_sb)) {
21051da177e4SLinus Torvalds /* Root is not changed. */
2106ee93961bSJeff Mahoney PATH_OFFSET_PBUFFER(path, path_offset - 1) = NULL;
2107ee93961bSJeff Mahoney PATH_OFFSET_POSITION(path, path_offset - 1) = 0;
21081da177e4SLinus Torvalds return CARRY_ON;
21091da177e4SLinus Torvalds }
2110098297b2SJeff Mahoney /* Root is changed and we must recalculate the path. */
2111098297b2SJeff Mahoney return REPEAT_SEARCH;
21121da177e4SLinus Torvalds }
21131da177e4SLinus Torvalds
2114098297b2SJeff Mahoney /* Parent in the path is not in the tree. */
2115bd4c625cSLinus Torvalds if (!B_IS_IN_TREE
2116ee93961bSJeff Mahoney (bh = PATH_OFFSET_PBUFFER(path, path_offset - 1)))
2117098297b2SJeff Mahoney return REPEAT_SEARCH;
21181da177e4SLinus Torvalds
2119ee93961bSJeff Mahoney if ((position =
2120d68caa95SJeff Mahoney PATH_OFFSET_POSITION(path,
2121ee93961bSJeff Mahoney path_offset - 1)) > B_NR_ITEMS(bh))
21221da177e4SLinus Torvalds return REPEAT_SEARCH;
21231da177e4SLinus Torvalds
2124098297b2SJeff Mahoney /* Parent in the path is not parent of the current node in the tree. */
2125ee93961bSJeff Mahoney if (B_N_CHILD_NUM(bh, position) !=
2126ee93961bSJeff Mahoney PATH_OFFSET_PBUFFER(path, path_offset)->b_blocknr)
21271da177e4SLinus Torvalds return REPEAT_SEARCH;
21281da177e4SLinus Torvalds
2129ad31a4fcSJeff Mahoney if (buffer_locked(bh)) {
2130278f6679SJeff Mahoney int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2131ad31a4fcSJeff Mahoney __wait_on_buffer(bh);
2132278f6679SJeff Mahoney reiserfs_write_lock_nested(tb->tb_sb, depth);
2133a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb))
21341da177e4SLinus Torvalds return REPEAT_SEARCH;
21351da177e4SLinus Torvalds }
21361da177e4SLinus Torvalds
2137098297b2SJeff Mahoney /*
2138098297b2SJeff Mahoney * Parent in the path is unlocked and really parent
2139098297b2SJeff Mahoney * of the current node.
2140098297b2SJeff Mahoney */
2141098297b2SJeff Mahoney return CARRY_ON;
21421da177e4SLinus Torvalds }
21431da177e4SLinus Torvalds
2144098297b2SJeff Mahoney /*
2145098297b2SJeff Mahoney * Using lnum[h] and rnum[h] we should determine what neighbors
2146ee93961bSJeff Mahoney * of S[h] we
2147ee93961bSJeff Mahoney * need in order to balance S[h], and get them if necessary.
21481da177e4SLinus Torvalds * Returns: SCHEDULE_OCCURRED - schedule occurred while the function worked;
21491da177e4SLinus Torvalds * CARRY_ON - schedule didn't occur while the function worked;
21501da177e4SLinus Torvalds */
get_neighbors(struct tree_balance * tb,int h)2151ee93961bSJeff Mahoney static int get_neighbors(struct tree_balance *tb, int h)
2152bd4c625cSLinus Torvalds {
2153ee93961bSJeff Mahoney int child_position,
2154ee93961bSJeff Mahoney path_offset = PATH_H_PATH_OFFSET(tb->tb_path, h + 1);
2155ee93961bSJeff Mahoney unsigned long son_number;
2156a063ae17SJeff Mahoney struct super_block *sb = tb->tb_sb;
2157ad31a4fcSJeff Mahoney struct buffer_head *bh;
2158278f6679SJeff Mahoney int depth;
21591da177e4SLinus Torvalds
2160ee93961bSJeff Mahoney PROC_INFO_INC(sb, get_neighbors[h]);
21611da177e4SLinus Torvalds
2162ee93961bSJeff Mahoney if (tb->lnum[h]) {
2163ee93961bSJeff Mahoney /* We need left neighbor to balance S[h]. */
2164ee93961bSJeff Mahoney PROC_INFO_INC(sb, need_l_neighbor[h]);
2165ee93961bSJeff Mahoney bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
21661da177e4SLinus Torvalds
2167ee93961bSJeff Mahoney RFALSE(bh == tb->FL[h] &&
2168ee93961bSJeff Mahoney !PATH_OFFSET_POSITION(tb->tb_path, path_offset),
21691da177e4SLinus Torvalds "PAP-8270: invalid position in the parent");
21701da177e4SLinus Torvalds
2171ee93961bSJeff Mahoney child_position =
2172ad31a4fcSJeff Mahoney (bh ==
2173ee93961bSJeff Mahoney tb->FL[h]) ? tb->lkey[h] : B_NR_ITEMS(tb->
2174ee93961bSJeff Mahoney FL[h]);
2175ee93961bSJeff Mahoney son_number = B_N_CHILD_NUM(tb->FL[h], child_position);
2176278f6679SJeff Mahoney depth = reiserfs_write_unlock_nested(tb->tb_sb);
2177ee93961bSJeff Mahoney bh = sb_bread(sb, son_number);
2178278f6679SJeff Mahoney reiserfs_write_lock_nested(tb->tb_sb, depth);
2179ad31a4fcSJeff Mahoney if (!bh)
21801da177e4SLinus Torvalds return IO_ERROR;
2181a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb)) {
2182ad31a4fcSJeff Mahoney brelse(bh);
2183ee93961bSJeff Mahoney PROC_INFO_INC(sb, get_neighbors_restart[h]);
21841da177e4SLinus Torvalds return REPEAT_SEARCH;
21851da177e4SLinus Torvalds }
21861da177e4SLinus Torvalds
2187ee93961bSJeff Mahoney RFALSE(!B_IS_IN_TREE(tb->FL[h]) ||
2188ee93961bSJeff Mahoney child_position > B_NR_ITEMS(tb->FL[h]) ||
2189ee93961bSJeff Mahoney B_N_CHILD_NUM(tb->FL[h], child_position) !=
2190ad31a4fcSJeff Mahoney bh->b_blocknr, "PAP-8275: invalid parent");
2191ad31a4fcSJeff Mahoney RFALSE(!B_IS_IN_TREE(bh), "PAP-8280: invalid child");
2192ee93961bSJeff Mahoney RFALSE(!h &&
2193ad31a4fcSJeff Mahoney B_FREE_SPACE(bh) !=
2194ad31a4fcSJeff Mahoney MAX_CHILD_SIZE(bh) -
2195ee93961bSJeff Mahoney dc_size(B_N_CHILD(tb->FL[0], child_position)),
21961da177e4SLinus Torvalds "PAP-8290: invalid child size of left neighbor");
21971da177e4SLinus Torvalds
2198ee93961bSJeff Mahoney brelse(tb->L[h]);
2199ee93961bSJeff Mahoney tb->L[h] = bh;
22001da177e4SLinus Torvalds }
22011da177e4SLinus Torvalds
2202ee93961bSJeff Mahoney /* We need right neighbor to balance S[path_offset]. */
2203098297b2SJeff Mahoney if (tb->rnum[h]) {
2204ee93961bSJeff Mahoney PROC_INFO_INC(sb, need_r_neighbor[h]);
2205ee93961bSJeff Mahoney bh = PATH_OFFSET_PBUFFER(tb->tb_path, path_offset);
22061da177e4SLinus Torvalds
2207ee93961bSJeff Mahoney RFALSE(bh == tb->FR[h] &&
2208a063ae17SJeff Mahoney PATH_OFFSET_POSITION(tb->tb_path,
2209ee93961bSJeff Mahoney path_offset) >=
2210ad31a4fcSJeff Mahoney B_NR_ITEMS(bh),
22111da177e4SLinus Torvalds "PAP-8295: invalid position in the parent");
22121da177e4SLinus Torvalds
2213ee93961bSJeff Mahoney child_position =
2214ee93961bSJeff Mahoney (bh == tb->FR[h]) ? tb->rkey[h] + 1 : 0;
2215ee93961bSJeff Mahoney son_number = B_N_CHILD_NUM(tb->FR[h], child_position);
2216278f6679SJeff Mahoney depth = reiserfs_write_unlock_nested(tb->tb_sb);
2217ee93961bSJeff Mahoney bh = sb_bread(sb, son_number);
2218278f6679SJeff Mahoney reiserfs_write_lock_nested(tb->tb_sb, depth);
2219ad31a4fcSJeff Mahoney if (!bh)
22201da177e4SLinus Torvalds return IO_ERROR;
2221a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb)) {
2222ad31a4fcSJeff Mahoney brelse(bh);
2223ee93961bSJeff Mahoney PROC_INFO_INC(sb, get_neighbors_restart[h]);
22241da177e4SLinus Torvalds return REPEAT_SEARCH;
22251da177e4SLinus Torvalds }
2226ee93961bSJeff Mahoney brelse(tb->R[h]);
2227ee93961bSJeff Mahoney tb->R[h] = bh;
22281da177e4SLinus Torvalds
2229ee93961bSJeff Mahoney RFALSE(!h
2230ad31a4fcSJeff Mahoney && B_FREE_SPACE(bh) !=
2231ad31a4fcSJeff Mahoney MAX_CHILD_SIZE(bh) -
2232ee93961bSJeff Mahoney dc_size(B_N_CHILD(tb->FR[0], child_position)),
22331da177e4SLinus Torvalds "PAP-8300: invalid child size of right neighbor (%d != %d - %d)",
2234ad31a4fcSJeff Mahoney B_FREE_SPACE(bh), MAX_CHILD_SIZE(bh),
2235ee93961bSJeff Mahoney dc_size(B_N_CHILD(tb->FR[0], child_position)));
22361da177e4SLinus Torvalds
22371da177e4SLinus Torvalds }
22381da177e4SLinus Torvalds return CARRY_ON;
22391da177e4SLinus Torvalds }
22401da177e4SLinus Torvalds
get_virtual_node_size(struct super_block * sb,struct buffer_head * bh)22411da177e4SLinus Torvalds static int get_virtual_node_size(struct super_block *sb, struct buffer_head *bh)
22421da177e4SLinus Torvalds {
22431da177e4SLinus Torvalds int max_num_of_items;
22441da177e4SLinus Torvalds int max_num_of_entries;
22451da177e4SLinus Torvalds unsigned long blocksize = sb->s_blocksize;
22461da177e4SLinus Torvalds
22471da177e4SLinus Torvalds #define MIN_NAME_LEN 1
22481da177e4SLinus Torvalds
22491da177e4SLinus Torvalds max_num_of_items = (blocksize - BLKH_SIZE) / (IH_SIZE + MIN_ITEM_LEN);
22501da177e4SLinus Torvalds max_num_of_entries = (blocksize - BLKH_SIZE - IH_SIZE) /
22511da177e4SLinus Torvalds (DEH_SIZE + MIN_NAME_LEN);
22521da177e4SLinus Torvalds
22531da177e4SLinus Torvalds return sizeof(struct virtual_node) +
22541da177e4SLinus Torvalds max(max_num_of_items * sizeof(struct virtual_item),
2255*76d2cedaSGustavo A. R. Silva sizeof(struct virtual_item) +
2256*76d2cedaSGustavo A. R. Silva struct_size_t(struct direntry_uarea, entry_sizes,
2257*76d2cedaSGustavo A. R. Silva max_num_of_entries));
22581da177e4SLinus Torvalds }
22591da177e4SLinus Torvalds
2260098297b2SJeff Mahoney /*
2261098297b2SJeff Mahoney * maybe we should fail balancing we are going to perform when kmalloc
2262098297b2SJeff Mahoney * fails several times. But now it will loop until kmalloc gets
2263098297b2SJeff Mahoney * required memory
2264098297b2SJeff Mahoney */
get_mem_for_virtual_node(struct tree_balance * tb)22651da177e4SLinus Torvalds static int get_mem_for_virtual_node(struct tree_balance *tb)
22661da177e4SLinus Torvalds {
22671da177e4SLinus Torvalds int check_fs = 0;
22681da177e4SLinus Torvalds int size;
22691da177e4SLinus Torvalds char *buf;
22701da177e4SLinus Torvalds
22711da177e4SLinus Torvalds size = get_virtual_node_size(tb->tb_sb, PATH_PLAST_BUFFER(tb->tb_path));
22721da177e4SLinus Torvalds
22731da177e4SLinus Torvalds /* we have to allocate more memory for virtual node */
2274098297b2SJeff Mahoney if (size > tb->vn_buf_size) {
22751da177e4SLinus Torvalds if (tb->vn_buf) {
22761da177e4SLinus Torvalds /* free memory allocated before */
2277d739b42bSPekka Enberg kfree(tb->vn_buf);
22781da177e4SLinus Torvalds /* this is not needed if kfree is atomic */
22791da177e4SLinus Torvalds check_fs = 1;
22801da177e4SLinus Torvalds }
22811da177e4SLinus Torvalds
22821da177e4SLinus Torvalds /* virtual node requires now more memory */
22831da177e4SLinus Torvalds tb->vn_buf_size = size;
22841da177e4SLinus Torvalds
22851da177e4SLinus Torvalds /* get memory for virtual item */
2286d739b42bSPekka Enberg buf = kmalloc(size, GFP_ATOMIC | __GFP_NOWARN);
22871da177e4SLinus Torvalds if (!buf) {
2288098297b2SJeff Mahoney /*
2289098297b2SJeff Mahoney * getting memory with GFP_KERNEL priority may involve
2290098297b2SJeff Mahoney * balancing now (due to indirect_to_direct conversion
2291098297b2SJeff Mahoney * on dcache shrinking). So, release path and collected
2292098297b2SJeff Mahoney * resources here
2293098297b2SJeff Mahoney */
22941da177e4SLinus Torvalds free_buffers_in_tb(tb);
2295d739b42bSPekka Enberg buf = kmalloc(size, GFP_NOFS);
22961da177e4SLinus Torvalds if (!buf) {
22971da177e4SLinus Torvalds tb->vn_buf_size = 0;
22981da177e4SLinus Torvalds }
22991da177e4SLinus Torvalds tb->vn_buf = buf;
23001da177e4SLinus Torvalds schedule();
23011da177e4SLinus Torvalds return REPEAT_SEARCH;
23021da177e4SLinus Torvalds }
23031da177e4SLinus Torvalds
23041da177e4SLinus Torvalds tb->vn_buf = buf;
23051da177e4SLinus Torvalds }
23061da177e4SLinus Torvalds
23071da177e4SLinus Torvalds if (check_fs && FILESYSTEM_CHANGED_TB(tb))
23081da177e4SLinus Torvalds return REPEAT_SEARCH;
23091da177e4SLinus Torvalds
23101da177e4SLinus Torvalds return CARRY_ON;
23111da177e4SLinus Torvalds }
23121da177e4SLinus Torvalds
23131da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK
tb_buffer_sanity_check(struct super_block * sb,struct buffer_head * bh,const char * descr,int level)2314a9dd3643SJeff Mahoney static void tb_buffer_sanity_check(struct super_block *sb,
2315ad31a4fcSJeff Mahoney struct buffer_head *bh,
2316bd4c625cSLinus Torvalds const char *descr, int level)
2317bd4c625cSLinus Torvalds {
2318ad31a4fcSJeff Mahoney if (bh) {
2319ad31a4fcSJeff Mahoney if (atomic_read(&(bh->b_count)) <= 0)
23201da177e4SLinus Torvalds
2321a9dd3643SJeff Mahoney reiserfs_panic(sb, "jmacd-1", "negative or zero "
2322c3a9c210SJeff Mahoney "reference counter for buffer %s[%d] "
2323ad31a4fcSJeff Mahoney "(%b)", descr, level, bh);
23241da177e4SLinus Torvalds
2325ad31a4fcSJeff Mahoney if (!buffer_uptodate(bh))
2326a9dd3643SJeff Mahoney reiserfs_panic(sb, "jmacd-2", "buffer is not up "
2327c3a9c210SJeff Mahoney "to date %s[%d] (%b)",
2328ad31a4fcSJeff Mahoney descr, level, bh);
23291da177e4SLinus Torvalds
2330ad31a4fcSJeff Mahoney if (!B_IS_IN_TREE(bh))
2331a9dd3643SJeff Mahoney reiserfs_panic(sb, "jmacd-3", "buffer is not "
2332c3a9c210SJeff Mahoney "in tree %s[%d] (%b)",
2333ad31a4fcSJeff Mahoney descr, level, bh);
23341da177e4SLinus Torvalds
2335ad31a4fcSJeff Mahoney if (bh->b_bdev != sb->s_bdev)
2336a9dd3643SJeff Mahoney reiserfs_panic(sb, "jmacd-4", "buffer has wrong "
2337c3a9c210SJeff Mahoney "device %s[%d] (%b)",
2338ad31a4fcSJeff Mahoney descr, level, bh);
23391da177e4SLinus Torvalds
2340ad31a4fcSJeff Mahoney if (bh->b_size != sb->s_blocksize)
2341a9dd3643SJeff Mahoney reiserfs_panic(sb, "jmacd-5", "buffer has wrong "
2342c3a9c210SJeff Mahoney "blocksize %s[%d] (%b)",
2343ad31a4fcSJeff Mahoney descr, level, bh);
23441da177e4SLinus Torvalds
2345ad31a4fcSJeff Mahoney if (bh->b_blocknr > SB_BLOCK_COUNT(sb))
2346a9dd3643SJeff Mahoney reiserfs_panic(sb, "jmacd-6", "buffer block "
2347c3a9c210SJeff Mahoney "number too high %s[%d] (%b)",
2348ad31a4fcSJeff Mahoney descr, level, bh);
23491da177e4SLinus Torvalds }
23501da177e4SLinus Torvalds }
23511da177e4SLinus Torvalds #else
tb_buffer_sanity_check(struct super_block * sb,struct buffer_head * bh,const char * descr,int level)2352a9dd3643SJeff Mahoney static void tb_buffer_sanity_check(struct super_block *sb,
2353ad31a4fcSJeff Mahoney struct buffer_head *bh,
23541da177e4SLinus Torvalds const char *descr, int level)
2355bd4c625cSLinus Torvalds {;
2356bd4c625cSLinus Torvalds }
23571da177e4SLinus Torvalds #endif
23581da177e4SLinus Torvalds
clear_all_dirty_bits(struct super_block * s,struct buffer_head * bh)2359bd4c625cSLinus Torvalds static int clear_all_dirty_bits(struct super_block *s, struct buffer_head *bh)
2360bd4c625cSLinus Torvalds {
23611da177e4SLinus Torvalds return reiserfs_prepare_for_journal(s, bh, 0);
23621da177e4SLinus Torvalds }
23631da177e4SLinus Torvalds
wait_tb_buffers_until_unlocked(struct tree_balance * tb)2364a063ae17SJeff Mahoney static int wait_tb_buffers_until_unlocked(struct tree_balance *tb)
23651da177e4SLinus Torvalds {
23661da177e4SLinus Torvalds struct buffer_head *locked;
23671da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK
23681da177e4SLinus Torvalds int repeat_counter = 0;
23691da177e4SLinus Torvalds #endif
23701da177e4SLinus Torvalds int i;
23711da177e4SLinus Torvalds
23721da177e4SLinus Torvalds do {
23731da177e4SLinus Torvalds
23741da177e4SLinus Torvalds locked = NULL;
23751da177e4SLinus Torvalds
2376a063ae17SJeff Mahoney for (i = tb->tb_path->path_length;
2377bd4c625cSLinus Torvalds !locked && i > ILLEGAL_PATH_ELEMENT_OFFSET; i--) {
2378a063ae17SJeff Mahoney if (PATH_OFFSET_PBUFFER(tb->tb_path, i)) {
2379098297b2SJeff Mahoney /*
2380098297b2SJeff Mahoney * if I understand correctly, we can only
2381098297b2SJeff Mahoney * be sure the last buffer in the path is
2382098297b2SJeff Mahoney * in the tree --clm
23831da177e4SLinus Torvalds */
23841da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK
2385a063ae17SJeff Mahoney if (PATH_PLAST_BUFFER(tb->tb_path) ==
2386a063ae17SJeff Mahoney PATH_OFFSET_PBUFFER(tb->tb_path, i))
2387a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2388bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER
2389a063ae17SJeff Mahoney (tb->tb_path,
2390bd4c625cSLinus Torvalds i), "S",
2391a063ae17SJeff Mahoney tb->tb_path->
2392bd4c625cSLinus Torvalds path_length - i);
23931da177e4SLinus Torvalds #endif
2394a063ae17SJeff Mahoney if (!clear_all_dirty_bits(tb->tb_sb,
2395bd4c625cSLinus Torvalds PATH_OFFSET_PBUFFER
2396a063ae17SJeff Mahoney (tb->tb_path,
2397bd4c625cSLinus Torvalds i))) {
2398bd4c625cSLinus Torvalds locked =
2399a063ae17SJeff Mahoney PATH_OFFSET_PBUFFER(tb->tb_path,
2400bd4c625cSLinus Torvalds i);
24011da177e4SLinus Torvalds }
24021da177e4SLinus Torvalds }
24031da177e4SLinus Torvalds }
24041da177e4SLinus Torvalds
2405a063ae17SJeff Mahoney for (i = 0; !locked && i < MAX_HEIGHT && tb->insert_size[i];
2406bd4c625cSLinus Torvalds i++) {
24071da177e4SLinus Torvalds
2408a063ae17SJeff Mahoney if (tb->lnum[i]) {
24091da177e4SLinus Torvalds
2410a063ae17SJeff Mahoney if (tb->L[i]) {
2411a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2412a063ae17SJeff Mahoney tb->L[i],
2413bd4c625cSLinus Torvalds "L", i);
2414bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2415a063ae17SJeff Mahoney (tb->tb_sb, tb->L[i]))
2416a063ae17SJeff Mahoney locked = tb->L[i];
24171da177e4SLinus Torvalds }
24181da177e4SLinus Torvalds
2419a063ae17SJeff Mahoney if (!locked && tb->FL[i]) {
2420a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2421a063ae17SJeff Mahoney tb->FL[i],
2422bd4c625cSLinus Torvalds "FL", i);
2423bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2424a063ae17SJeff Mahoney (tb->tb_sb, tb->FL[i]))
2425a063ae17SJeff Mahoney locked = tb->FL[i];
24261da177e4SLinus Torvalds }
24271da177e4SLinus Torvalds
2428a063ae17SJeff Mahoney if (!locked && tb->CFL[i]) {
2429a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2430a063ae17SJeff Mahoney tb->CFL[i],
2431bd4c625cSLinus Torvalds "CFL", i);
2432bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2433a063ae17SJeff Mahoney (tb->tb_sb, tb->CFL[i]))
2434a063ae17SJeff Mahoney locked = tb->CFL[i];
24351da177e4SLinus Torvalds }
24361da177e4SLinus Torvalds
24371da177e4SLinus Torvalds }
24381da177e4SLinus Torvalds
2439a063ae17SJeff Mahoney if (!locked && (tb->rnum[i])) {
24401da177e4SLinus Torvalds
2441a063ae17SJeff Mahoney if (tb->R[i]) {
2442a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2443a063ae17SJeff Mahoney tb->R[i],
2444bd4c625cSLinus Torvalds "R", i);
2445bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2446a063ae17SJeff Mahoney (tb->tb_sb, tb->R[i]))
2447a063ae17SJeff Mahoney locked = tb->R[i];
24481da177e4SLinus Torvalds }
24491da177e4SLinus Torvalds
2450a063ae17SJeff Mahoney if (!locked && tb->FR[i]) {
2451a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2452a063ae17SJeff Mahoney tb->FR[i],
2453bd4c625cSLinus Torvalds "FR", i);
2454bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2455a063ae17SJeff Mahoney (tb->tb_sb, tb->FR[i]))
2456a063ae17SJeff Mahoney locked = tb->FR[i];
24571da177e4SLinus Torvalds }
24581da177e4SLinus Torvalds
2459a063ae17SJeff Mahoney if (!locked && tb->CFR[i]) {
2460a063ae17SJeff Mahoney tb_buffer_sanity_check(tb->tb_sb,
2461a063ae17SJeff Mahoney tb->CFR[i],
2462bd4c625cSLinus Torvalds "CFR", i);
2463bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2464a063ae17SJeff Mahoney (tb->tb_sb, tb->CFR[i]))
2465a063ae17SJeff Mahoney locked = tb->CFR[i];
24661da177e4SLinus Torvalds }
24671da177e4SLinus Torvalds }
24681da177e4SLinus Torvalds }
2469098297b2SJeff Mahoney
2470098297b2SJeff Mahoney /*
2471098297b2SJeff Mahoney * as far as I can tell, this is not required. The FEB list
2472098297b2SJeff Mahoney * seems to be full of newly allocated nodes, which will
2473098297b2SJeff Mahoney * never be locked, dirty, or anything else.
2474098297b2SJeff Mahoney * To be safe, I'm putting in the checks and waits in.
2475098297b2SJeff Mahoney * For the moment, they are needed to keep the code in
2476098297b2SJeff Mahoney * journal.c from complaining about the buffer.
2477098297b2SJeff Mahoney * That code is inside CONFIG_REISERFS_CHECK as well. --clm
24781da177e4SLinus Torvalds */
24791da177e4SLinus Torvalds for (i = 0; !locked && i < MAX_FEB_SIZE; i++) {
2480a063ae17SJeff Mahoney if (tb->FEB[i]) {
2481bd4c625cSLinus Torvalds if (!clear_all_dirty_bits
2482a063ae17SJeff Mahoney (tb->tb_sb, tb->FEB[i]))
2483a063ae17SJeff Mahoney locked = tb->FEB[i];
24841da177e4SLinus Torvalds }
24851da177e4SLinus Torvalds }
24861da177e4SLinus Torvalds
24871da177e4SLinus Torvalds if (locked) {
2488278f6679SJeff Mahoney int depth;
24891da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK
24901da177e4SLinus Torvalds repeat_counter++;
24911da177e4SLinus Torvalds if ((repeat_counter % 10000) == 0) {
2492a063ae17SJeff Mahoney reiserfs_warning(tb->tb_sb, "reiserfs-8200",
249345b03d5eSJeff Mahoney "too many iterations waiting "
249445b03d5eSJeff Mahoney "for buffer to unlock "
24951da177e4SLinus Torvalds "(%b)", locked);
24961da177e4SLinus Torvalds
24971da177e4SLinus Torvalds /* Don't loop forever. Try to recover from possible error. */
24981da177e4SLinus Torvalds
2499a063ae17SJeff Mahoney return (FILESYSTEM_CHANGED_TB(tb)) ?
2500bd4c625cSLinus Torvalds REPEAT_SEARCH : CARRY_ON;
25011da177e4SLinus Torvalds }
25021da177e4SLinus Torvalds #endif
2503278f6679SJeff Mahoney depth = reiserfs_write_unlock_nested(tb->tb_sb);
25041da177e4SLinus Torvalds __wait_on_buffer(locked);
2505278f6679SJeff Mahoney reiserfs_write_lock_nested(tb->tb_sb, depth);
2506a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb))
25071da177e4SLinus Torvalds return REPEAT_SEARCH;
25081da177e4SLinus Torvalds }
25091da177e4SLinus Torvalds
25101da177e4SLinus Torvalds } while (locked);
25111da177e4SLinus Torvalds
25121da177e4SLinus Torvalds return CARRY_ON;
25131da177e4SLinus Torvalds }
25141da177e4SLinus Torvalds
2515098297b2SJeff Mahoney /*
2516098297b2SJeff Mahoney * Prepare for balancing, that is
25171da177e4SLinus Torvalds * get all necessary parents, and neighbors;
25181da177e4SLinus Torvalds * analyze what and where should be moved;
25191da177e4SLinus Torvalds * get sufficient number of new nodes;
25201da177e4SLinus Torvalds * Balancing will start only after all resources will be collected at a time.
25211da177e4SLinus Torvalds *
25221da177e4SLinus Torvalds * When ported to SMP kernels, only at the last moment after all needed nodes
25231da177e4SLinus Torvalds * are collected in cache, will the resources be locked using the usual
25241da177e4SLinus Torvalds * textbook ordered lock acquisition algorithms. Note that ensuring that
2525098297b2SJeff Mahoney * this code neither write locks what it does not need to write lock nor locks
2526098297b2SJeff Mahoney * out of order will be a pain in the butt that could have been avoided.
2527098297b2SJeff Mahoney * Grumble grumble. -Hans
25281da177e4SLinus Torvalds *
25291da177e4SLinus Torvalds * fix is meant in the sense of render unchanging
25301da177e4SLinus Torvalds *
2531098297b2SJeff Mahoney * Latency might be improved by first gathering a list of what buffers
2532098297b2SJeff Mahoney * are needed and then getting as many of them in parallel as possible? -Hans
25331da177e4SLinus Torvalds *
25341da177e4SLinus Torvalds * Parameters:
25351da177e4SLinus Torvalds * op_mode i - insert, d - delete, c - cut (truncate), p - paste (append)
25361da177e4SLinus Torvalds * tb tree_balance structure;
25371da177e4SLinus Torvalds * inum item number in S[h];
25381da177e4SLinus Torvalds * pos_in_item - comment this if you can
2539a063ae17SJeff Mahoney * ins_ih item head of item being inserted
2540a063ae17SJeff Mahoney * data inserted item or data to be pasted
25411da177e4SLinus Torvalds * Returns: 1 - schedule occurred while the function worked;
25421da177e4SLinus Torvalds * 0 - schedule didn't occur while the function worked;
25431da177e4SLinus Torvalds * -1 - if no_disk_space
25441da177e4SLinus Torvalds */
25451da177e4SLinus Torvalds
fix_nodes(int op_mode,struct tree_balance * tb,struct item_head * ins_ih,const void * data)2546ee93961bSJeff Mahoney int fix_nodes(int op_mode, struct tree_balance *tb,
2547d68caa95SJeff Mahoney struct item_head *ins_ih, const void *data)
2548bd4c625cSLinus Torvalds {
2549ee93961bSJeff Mahoney int ret, h, item_num = PATH_LAST_POSITION(tb->tb_path);
2550ee93961bSJeff Mahoney int pos_in_item;
25511da177e4SLinus Torvalds
2552098297b2SJeff Mahoney /*
2553098297b2SJeff Mahoney * we set wait_tb_buffers_run when we have to restore any dirty
2554098297b2SJeff Mahoney * bits cleared during wait_tb_buffers_run
25551da177e4SLinus Torvalds */
25561da177e4SLinus Torvalds int wait_tb_buffers_run = 0;
2557a063ae17SJeff Mahoney struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
25581da177e4SLinus Torvalds
2559a063ae17SJeff Mahoney ++REISERFS_SB(tb->tb_sb)->s_fix_nodes;
25601da177e4SLinus Torvalds
2561ee93961bSJeff Mahoney pos_in_item = tb->tb_path->pos_in_item;
25621da177e4SLinus Torvalds
2563a063ae17SJeff Mahoney tb->fs_gen = get_generation(tb->tb_sb);
25641da177e4SLinus Torvalds
2565098297b2SJeff Mahoney /*
2566098297b2SJeff Mahoney * we prepare and log the super here so it will already be in the
2567098297b2SJeff Mahoney * transaction when do_balance needs to change it.
2568098297b2SJeff Mahoney * This way do_balance won't have to schedule when trying to prepare
2569098297b2SJeff Mahoney * the super for logging
25701da177e4SLinus Torvalds */
2571a063ae17SJeff Mahoney reiserfs_prepare_for_journal(tb->tb_sb,
2572a063ae17SJeff Mahoney SB_BUFFER_WITH_SB(tb->tb_sb), 1);
257309f1b80bSJeff Mahoney journal_mark_dirty(tb->transaction_handle,
2574a063ae17SJeff Mahoney SB_BUFFER_WITH_SB(tb->tb_sb));
2575a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb))
25761da177e4SLinus Torvalds return REPEAT_SEARCH;
25771da177e4SLinus Torvalds
25781da177e4SLinus Torvalds /* if it possible in indirect_to_direct conversion */
2579a063ae17SJeff Mahoney if (buffer_locked(tbS0)) {
2580278f6679SJeff Mahoney int depth = reiserfs_write_unlock_nested(tb->tb_sb);
2581a063ae17SJeff Mahoney __wait_on_buffer(tbS0);
2582278f6679SJeff Mahoney reiserfs_write_lock_nested(tb->tb_sb, depth);
2583a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb))
25841da177e4SLinus Torvalds return REPEAT_SEARCH;
25851da177e4SLinus Torvalds }
25861da177e4SLinus Torvalds #ifdef CONFIG_REISERFS_CHECK
258708f14fc8SFrederic Weisbecker if (REISERFS_SB(tb->tb_sb)->cur_tb) {
25881da177e4SLinus Torvalds print_cur_tb("fix_nodes");
2589a063ae17SJeff Mahoney reiserfs_panic(tb->tb_sb, "PAP-8305",
2590c3a9c210SJeff Mahoney "there is pending do_balance");
25911da177e4SLinus Torvalds }
25921da177e4SLinus Torvalds
2593a063ae17SJeff Mahoney if (!buffer_uptodate(tbS0) || !B_IS_IN_TREE(tbS0))
2594a063ae17SJeff Mahoney reiserfs_panic(tb->tb_sb, "PAP-8320", "S[0] (%b %z) is "
2595c3a9c210SJeff Mahoney "not uptodate at the beginning of fix_nodes "
2596c3a9c210SJeff Mahoney "or not in tree (mode %c)",
2597ee93961bSJeff Mahoney tbS0, tbS0, op_mode);
25981da177e4SLinus Torvalds
25991da177e4SLinus Torvalds /* Check parameters. */
2600ee93961bSJeff Mahoney switch (op_mode) {
26011da177e4SLinus Torvalds case M_INSERT:
2602ee93961bSJeff Mahoney if (item_num <= 0 || item_num > B_NR_ITEMS(tbS0))
2603a063ae17SJeff Mahoney reiserfs_panic(tb->tb_sb, "PAP-8330", "Incorrect "
2604c3a9c210SJeff Mahoney "item number %d (in S0 - %d) in case "
2605ee93961bSJeff Mahoney "of insert", item_num,
2606a063ae17SJeff Mahoney B_NR_ITEMS(tbS0));
26071da177e4SLinus Torvalds break;
26081da177e4SLinus Torvalds case M_PASTE:
26091da177e4SLinus Torvalds case M_DELETE:
26101da177e4SLinus Torvalds case M_CUT:
2611ee93961bSJeff Mahoney if (item_num < 0 || item_num >= B_NR_ITEMS(tbS0)) {
2612a063ae17SJeff Mahoney print_block(tbS0, 0, -1, -1);
2613a063ae17SJeff Mahoney reiserfs_panic(tb->tb_sb, "PAP-8335", "Incorrect "
2614c3a9c210SJeff Mahoney "item number(%d); mode = %c "
2615c3a9c210SJeff Mahoney "insert_size = %d",
2616ee93961bSJeff Mahoney item_num, op_mode,
2617a063ae17SJeff Mahoney tb->insert_size[0]);
26181da177e4SLinus Torvalds }
26191da177e4SLinus Torvalds break;
26201da177e4SLinus Torvalds default:
2621a063ae17SJeff Mahoney reiserfs_panic(tb->tb_sb, "PAP-8340", "Incorrect mode "
2622c3a9c210SJeff Mahoney "of operation");
26231da177e4SLinus Torvalds }
26241da177e4SLinus Torvalds #endif
26251da177e4SLinus Torvalds
2626a063ae17SJeff Mahoney if (get_mem_for_virtual_node(tb) == REPEAT_SEARCH)
2627098297b2SJeff Mahoney /* FIXME: maybe -ENOMEM when tb->vn_buf == 0? Now just repeat */
26281da177e4SLinus Torvalds return REPEAT_SEARCH;
26291da177e4SLinus Torvalds
2630ee93961bSJeff Mahoney /* Starting from the leaf level; for all levels h of the tree. */
2631ee93961bSJeff Mahoney for (h = 0; h < MAX_HEIGHT && tb->insert_size[h]; h++) {
2632ee93961bSJeff Mahoney ret = get_direct_parent(tb, h);
2633ee93961bSJeff Mahoney if (ret != CARRY_ON)
26341da177e4SLinus Torvalds goto repeat;
26351da177e4SLinus Torvalds
2636ee93961bSJeff Mahoney ret = check_balance(op_mode, tb, h, item_num,
2637ee93961bSJeff Mahoney pos_in_item, ins_ih, data);
2638ee93961bSJeff Mahoney if (ret != CARRY_ON) {
2639ee93961bSJeff Mahoney if (ret == NO_BALANCING_NEEDED) {
26401da177e4SLinus Torvalds /* No balancing for higher levels needed. */
2641ee93961bSJeff Mahoney ret = get_neighbors(tb, h);
2642ee93961bSJeff Mahoney if (ret != CARRY_ON)
26431da177e4SLinus Torvalds goto repeat;
2644ee93961bSJeff Mahoney if (h != MAX_HEIGHT - 1)
2645ee93961bSJeff Mahoney tb->insert_size[h + 1] = 0;
2646098297b2SJeff Mahoney /*
2647098297b2SJeff Mahoney * ok, analysis and resource gathering
2648098297b2SJeff Mahoney * are complete
2649098297b2SJeff Mahoney */
26501da177e4SLinus Torvalds break;
26511da177e4SLinus Torvalds }
26521da177e4SLinus Torvalds goto repeat;
26531da177e4SLinus Torvalds }
26541da177e4SLinus Torvalds
2655ee93961bSJeff Mahoney ret = get_neighbors(tb, h);
2656ee93961bSJeff Mahoney if (ret != CARRY_ON)
26571da177e4SLinus Torvalds goto repeat;
26581da177e4SLinus Torvalds
2659098297b2SJeff Mahoney /*
2660098297b2SJeff Mahoney * No disk space, or schedule occurred and analysis may be
2661098297b2SJeff Mahoney * invalid and needs to be redone.
2662098297b2SJeff Mahoney */
2663ee93961bSJeff Mahoney ret = get_empty_nodes(tb, h);
2664ee93961bSJeff Mahoney if (ret != CARRY_ON)
2665a063ae17SJeff Mahoney goto repeat;
26661da177e4SLinus Torvalds
2667098297b2SJeff Mahoney /*
2668098297b2SJeff Mahoney * We have a positive insert size but no nodes exist on this
2669098297b2SJeff Mahoney * level, this means that we are creating a new root.
2670098297b2SJeff Mahoney */
2671ee93961bSJeff Mahoney if (!PATH_H_PBUFFER(tb->tb_path, h)) {
26721da177e4SLinus Torvalds
2673ee93961bSJeff Mahoney RFALSE(tb->blknum[h] != 1,
26741da177e4SLinus Torvalds "PAP-8350: creating new empty root");
26751da177e4SLinus Torvalds
2676ee93961bSJeff Mahoney if (h < MAX_HEIGHT - 1)
2677ee93961bSJeff Mahoney tb->insert_size[h + 1] = 0;
2678ee93961bSJeff Mahoney } else if (!PATH_H_PBUFFER(tb->tb_path, h + 1)) {
2679098297b2SJeff Mahoney /*
2680098297b2SJeff Mahoney * The tree needs to be grown, so this node S[h]
2681098297b2SJeff Mahoney * which is the root node is split into two nodes,
2682098297b2SJeff Mahoney * and a new node (S[h+1]) will be created to
2683098297b2SJeff Mahoney * become the root node.
2684098297b2SJeff Mahoney */
2685ee93961bSJeff Mahoney if (tb->blknum[h] > 1) {
26861da177e4SLinus Torvalds
2687ee93961bSJeff Mahoney RFALSE(h == MAX_HEIGHT - 1,
26881da177e4SLinus Torvalds "PAP-8355: attempt to create too high of a tree");
26891da177e4SLinus Torvalds
2690ee93961bSJeff Mahoney tb->insert_size[h + 1] =
2691bd4c625cSLinus Torvalds (DC_SIZE +
2692ee93961bSJeff Mahoney KEY_SIZE) * (tb->blknum[h] - 1) +
2693bd4c625cSLinus Torvalds DC_SIZE;
2694ee93961bSJeff Mahoney } else if (h < MAX_HEIGHT - 1)
2695ee93961bSJeff Mahoney tb->insert_size[h + 1] = 0;
2696bd4c625cSLinus Torvalds } else
2697ee93961bSJeff Mahoney tb->insert_size[h + 1] =
2698ee93961bSJeff Mahoney (DC_SIZE + KEY_SIZE) * (tb->blknum[h] - 1);
26991da177e4SLinus Torvalds }
27001da177e4SLinus Torvalds
2701ee93961bSJeff Mahoney ret = wait_tb_buffers_until_unlocked(tb);
2702ee93961bSJeff Mahoney if (ret == CARRY_ON) {
2703a063ae17SJeff Mahoney if (FILESYSTEM_CHANGED_TB(tb)) {
27041da177e4SLinus Torvalds wait_tb_buffers_run = 1;
2705ee93961bSJeff Mahoney ret = REPEAT_SEARCH;
27061da177e4SLinus Torvalds goto repeat;
27071da177e4SLinus Torvalds } else {
27081da177e4SLinus Torvalds return CARRY_ON;
27091da177e4SLinus Torvalds }
27101da177e4SLinus Torvalds } else {
27111da177e4SLinus Torvalds wait_tb_buffers_run = 1;
27121da177e4SLinus Torvalds goto repeat;
27131da177e4SLinus Torvalds }
27141da177e4SLinus Torvalds
27151da177e4SLinus Torvalds repeat:
2716098297b2SJeff Mahoney /*
2717098297b2SJeff Mahoney * fix_nodes was unable to perform its calculation due to
2718098297b2SJeff Mahoney * filesystem got changed under us, lack of free disk space or i/o
2719098297b2SJeff Mahoney * failure. If the first is the case - the search will be
2720098297b2SJeff Mahoney * repeated. For now - free all resources acquired so far except
2721098297b2SJeff Mahoney * for the new allocated nodes
2722098297b2SJeff Mahoney */
27231da177e4SLinus Torvalds {
27241da177e4SLinus Torvalds int i;
27251da177e4SLinus Torvalds
27261da177e4SLinus Torvalds /* Release path buffers. */
27271da177e4SLinus Torvalds if (wait_tb_buffers_run) {
2728a063ae17SJeff Mahoney pathrelse_and_restore(tb->tb_sb, tb->tb_path);
27291da177e4SLinus Torvalds } else {
2730a063ae17SJeff Mahoney pathrelse(tb->tb_path);
27311da177e4SLinus Torvalds }
27321da177e4SLinus Torvalds /* brelse all resources collected for balancing */
27331da177e4SLinus Torvalds for (i = 0; i < MAX_HEIGHT; i++) {
27341da177e4SLinus Torvalds if (wait_tb_buffers_run) {
2735a063ae17SJeff Mahoney reiserfs_restore_prepared_buffer(tb->tb_sb,
2736a063ae17SJeff Mahoney tb->L[i]);
2737a063ae17SJeff Mahoney reiserfs_restore_prepared_buffer(tb->tb_sb,
2738a063ae17SJeff Mahoney tb->R[i]);
2739a063ae17SJeff Mahoney reiserfs_restore_prepared_buffer(tb->tb_sb,
2740a063ae17SJeff Mahoney tb->FL[i]);
2741a063ae17SJeff Mahoney reiserfs_restore_prepared_buffer(tb->tb_sb,
2742a063ae17SJeff Mahoney tb->FR[i]);
2743a063ae17SJeff Mahoney reiserfs_restore_prepared_buffer(tb->tb_sb,
2744a063ae17SJeff Mahoney tb->
2745bd4c625cSLinus Torvalds CFL[i]);
2746a063ae17SJeff Mahoney reiserfs_restore_prepared_buffer(tb->tb_sb,
2747a063ae17SJeff Mahoney tb->
2748bd4c625cSLinus Torvalds CFR[i]);
27491da177e4SLinus Torvalds }
27501da177e4SLinus Torvalds
2751a063ae17SJeff Mahoney brelse(tb->L[i]);
2752a063ae17SJeff Mahoney brelse(tb->R[i]);
2753a063ae17SJeff Mahoney brelse(tb->FL[i]);
2754a063ae17SJeff Mahoney brelse(tb->FR[i]);
2755a063ae17SJeff Mahoney brelse(tb->CFL[i]);
2756a063ae17SJeff Mahoney brelse(tb->CFR[i]);
27573cd6dbe6SJeff Mahoney
2758a063ae17SJeff Mahoney tb->L[i] = NULL;
2759a063ae17SJeff Mahoney tb->R[i] = NULL;
2760a063ae17SJeff Mahoney tb->FL[i] = NULL;
2761a063ae17SJeff Mahoney tb->FR[i] = NULL;
2762a063ae17SJeff Mahoney tb->CFL[i] = NULL;
2763a063ae17SJeff Mahoney tb->CFR[i] = NULL;
27641da177e4SLinus Torvalds }
27651da177e4SLinus Torvalds
27661da177e4SLinus Torvalds if (wait_tb_buffers_run) {
27671da177e4SLinus Torvalds for (i = 0; i < MAX_FEB_SIZE; i++) {
2768a063ae17SJeff Mahoney if (tb->FEB[i])
2769bd4c625cSLinus Torvalds reiserfs_restore_prepared_buffer
2770a063ae17SJeff Mahoney (tb->tb_sb, tb->FEB[i]);
27711da177e4SLinus Torvalds }
27721da177e4SLinus Torvalds }
2773ee93961bSJeff Mahoney return ret;
27741da177e4SLinus Torvalds }
27751da177e4SLinus Torvalds
27761da177e4SLinus Torvalds }
27771da177e4SLinus Torvalds
unfix_nodes(struct tree_balance * tb)27781da177e4SLinus Torvalds void unfix_nodes(struct tree_balance *tb)
27791da177e4SLinus Torvalds {
27801da177e4SLinus Torvalds int i;
27811da177e4SLinus Torvalds
27821da177e4SLinus Torvalds /* Release path buffers. */
27831da177e4SLinus Torvalds pathrelse_and_restore(tb->tb_sb, tb->tb_path);
27841da177e4SLinus Torvalds
27851da177e4SLinus Torvalds /* brelse all resources collected for balancing */
27861da177e4SLinus Torvalds for (i = 0; i < MAX_HEIGHT; i++) {
27871da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->L[i]);
27881da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->R[i]);
27891da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FL[i]);
27901da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->FR[i]);
27911da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFL[i]);
27921da177e4SLinus Torvalds reiserfs_restore_prepared_buffer(tb->tb_sb, tb->CFR[i]);
27931da177e4SLinus Torvalds
27941da177e4SLinus Torvalds brelse(tb->L[i]);
27951da177e4SLinus Torvalds brelse(tb->R[i]);
27961da177e4SLinus Torvalds brelse(tb->FL[i]);
27971da177e4SLinus Torvalds brelse(tb->FR[i]);
27981da177e4SLinus Torvalds brelse(tb->CFL[i]);
27991da177e4SLinus Torvalds brelse(tb->CFR[i]);
28001da177e4SLinus Torvalds }
28011da177e4SLinus Torvalds
28021da177e4SLinus Torvalds /* deal with list of allocated (used and unused) nodes */
28031da177e4SLinus Torvalds for (i = 0; i < MAX_FEB_SIZE; i++) {
28041da177e4SLinus Torvalds if (tb->FEB[i]) {
28051da177e4SLinus Torvalds b_blocknr_t blocknr = tb->FEB[i]->b_blocknr;
2806098297b2SJeff Mahoney /*
2807098297b2SJeff Mahoney * de-allocated block which was not used by
2808098297b2SJeff Mahoney * balancing and bforget about buffer for it
2809098297b2SJeff Mahoney */
28101da177e4SLinus Torvalds brelse(tb->FEB[i]);
2811bd4c625cSLinus Torvalds reiserfs_free_block(tb->transaction_handle, NULL,
2812bd4c625cSLinus Torvalds blocknr, 0);
28131da177e4SLinus Torvalds }
28141da177e4SLinus Torvalds if (tb->used[i]) {
28151da177e4SLinus Torvalds /* release used as new nodes including a new root */
28161da177e4SLinus Torvalds brelse(tb->used[i]);
28171da177e4SLinus Torvalds }
28181da177e4SLinus Torvalds }
28191da177e4SLinus Torvalds
2820d739b42bSPekka Enberg kfree(tb->vn_buf);
28211da177e4SLinus Torvalds
28221da177e4SLinus Torvalds }
2823