aboutsummaryrefslogtreecommitdiffstats
path: root/fs/nilfs2/btree.c
diff options
context:
space:
mode:
authorRyusuke Konishi <konishi.ryusuke@lab.ntt.co.jp>2010-07-13 10:33:52 -0400
committerRyusuke Konishi <konishi.ryusuke@lab.ntt.co.jp>2010-07-22 21:02:14 -0400
commitea64ab87cdba9e1172392d247e6526359e301f12 (patch)
tree644b2af0f1c20e79375d226c167c0b4f4d3a0ade /fs/nilfs2/btree.c
parent364ec2d700223b965620ff4d5031a3665d195873 (diff)
nilfs2: optimize calculation of min/max number of btree node children
nilfs_btree_node_nchildren_max() and nilfs_btree_node_nchildren_min() functions switch return value depending on whether target node is the root or a node block. In most uses of these functions, however, the node type is fixed, and moreover the same calculation is repeatedly performed in loop. This unfold these functions depending on context and move them outside loops wherever possible. Signed-off-by: Ryusuke Konishi <konishi.ryusuke@lab.ntt.co.jp>
Diffstat (limited to 'fs/nilfs2/btree.c')
-rw-r--r--fs/nilfs2/btree.c36
1 files changed, 18 insertions, 18 deletions
diff --git a/fs/nilfs2/btree.c b/fs/nilfs2/btree.c
index 18bb965c66b5..c0266f7f0b26 100644
--- a/fs/nilfs2/btree.c
+++ b/fs/nilfs2/btree.c
@@ -473,7 +473,7 @@ static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
473{ 473{
474 struct nilfs_btree_node *node; 474 struct nilfs_btree_node *node;
475 __u64 ptr; 475 __u64 ptr;
476 int level, index, found, ret; 476 int level, index, found, ncmax, ret;
477 477
478 node = nilfs_btree_get_root(btree); 478 node = nilfs_btree_get_root(btree);
479 level = nilfs_btree_node_get_level(node); 479 level = nilfs_btree_node_get_level(node);
@@ -485,6 +485,8 @@ static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
485 path[level].bp_bh = NULL; 485 path[level].bp_bh = NULL;
486 path[level].bp_index = index; 486 path[level].bp_index = index;
487 487
488 ncmax = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree));
489
488 for (level--; level >= minlevel; level--) { 490 for (level--; level >= minlevel; level--) {
489 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh); 491 ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
490 if (ret < 0) 492 if (ret < 0)
@@ -496,9 +498,9 @@ static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
496 found = nilfs_btree_node_lookup(node, key, &index); 498 found = nilfs_btree_node_lookup(node, key, &index);
497 else 499 else
498 index = 0; 500 index = 0;
499 if (index < nilfs_btree_node_nchildren_max(node, btree)) 501 if (index < ncmax) {
500 ptr = nilfs_btree_node_get_ptr(btree, node, index); 502 ptr = nilfs_btree_node_get_ptr(btree, node, index);
501 else { 503 } else {
502 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN); 504 WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
503 /* insert */ 505 /* insert */
504 ptr = NILFS_BMAP_INVALID_PTR; 506 ptr = NILFS_BMAP_INVALID_PTR;
@@ -921,7 +923,7 @@ static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
921 struct buffer_head *bh; 923 struct buffer_head *bh;
922 struct nilfs_btree_node *node, *parent, *sib; 924 struct nilfs_btree_node *node, *parent, *sib;
923 __u64 sibptr; 925 __u64 sibptr;
924 int pindex, level, ret; 926 int pindex, level, ncmax, ret;
925 struct inode *dat = NULL; 927 struct inode *dat = NULL;
926 928
927 stats->bs_nblocks = 0; 929 stats->bs_nblocks = 0;
@@ -938,12 +940,13 @@ static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
938 if (ret < 0) 940 if (ret < 0)
939 goto err_out_data; 941 goto err_out_data;
940 942
943 ncmax = NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(btree));
944
941 for (level = NILFS_BTREE_LEVEL_NODE_MIN; 945 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
942 level < nilfs_btree_height(btree) - 1; 946 level < nilfs_btree_height(btree) - 1;
943 level++) { 947 level++) {
944 node = nilfs_btree_get_nonroot_node(path, level); 948 node = nilfs_btree_get_nonroot_node(path, level);
945 if (nilfs_btree_node_get_nchildren(node) < 949 if (nilfs_btree_node_get_nchildren(node) < ncmax) {
946 nilfs_btree_node_nchildren_max(node, btree)) {
947 path[level].bp_op = nilfs_btree_do_insert; 950 path[level].bp_op = nilfs_btree_do_insert;
948 stats->bs_nblocks++; 951 stats->bs_nblocks++;
949 goto out; 952 goto out;
@@ -960,8 +963,7 @@ static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
960 if (ret < 0) 963 if (ret < 0)
961 goto err_out_child_node; 964 goto err_out_child_node;
962 sib = (struct nilfs_btree_node *)bh->b_data; 965 sib = (struct nilfs_btree_node *)bh->b_data;
963 if (nilfs_btree_node_get_nchildren(sib) < 966 if (nilfs_btree_node_get_nchildren(sib) < ncmax) {
964 nilfs_btree_node_nchildren_max(sib, btree)) {
965 path[level].bp_sib_bh = bh; 967 path[level].bp_sib_bh = bh;
966 path[level].bp_op = nilfs_btree_carry_left; 968 path[level].bp_op = nilfs_btree_carry_left;
967 stats->bs_nblocks++; 969 stats->bs_nblocks++;
@@ -979,8 +981,7 @@ static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
979 if (ret < 0) 981 if (ret < 0)
980 goto err_out_child_node; 982 goto err_out_child_node;
981 sib = (struct nilfs_btree_node *)bh->b_data; 983 sib = (struct nilfs_btree_node *)bh->b_data;
982 if (nilfs_btree_node_get_nchildren(sib) < 984 if (nilfs_btree_node_get_nchildren(sib) < ncmax) {
983 nilfs_btree_node_nchildren_max(sib, btree)) {
984 path[level].bp_sib_bh = bh; 985 path[level].bp_sib_bh = bh;
985 path[level].bp_op = nilfs_btree_carry_right; 986 path[level].bp_op = nilfs_btree_carry_right;
986 stats->bs_nblocks++; 987 stats->bs_nblocks++;
@@ -1014,7 +1015,7 @@ static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
1014 /* root */ 1015 /* root */
1015 node = nilfs_btree_get_root(btree); 1016 node = nilfs_btree_get_root(btree);
1016 if (nilfs_btree_node_get_nchildren(node) < 1017 if (nilfs_btree_node_get_nchildren(node) <
1017 nilfs_btree_node_nchildren_max(node, btree)) { 1018 NILFS_BTREE_ROOT_NCHILDREN_MAX) {
1018 path[level].bp_op = nilfs_btree_do_insert; 1019 path[level].bp_op = nilfs_btree_do_insert;
1019 stats->bs_nblocks++; 1020 stats->bs_nblocks++;
1020 goto out; 1021 goto out;
@@ -1281,10 +1282,12 @@ static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1281 struct buffer_head *bh; 1282 struct buffer_head *bh;
1282 struct nilfs_btree_node *node, *parent, *sib; 1283 struct nilfs_btree_node *node, *parent, *sib;
1283 __u64 sibptr; 1284 __u64 sibptr;
1284 int pindex, level, ret; 1285 int pindex, level, ncmin, ret;
1285 1286
1286 ret = 0; 1287 ret = 0;
1287 stats->bs_nblocks = 0; 1288 stats->bs_nblocks = 0;
1289 ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
1290
1288 for (level = NILFS_BTREE_LEVEL_NODE_MIN; 1291 for (level = NILFS_BTREE_LEVEL_NODE_MIN;
1289 level < nilfs_btree_height(btree) - 1; 1292 level < nilfs_btree_height(btree) - 1;
1290 level++) { 1293 level++) {
@@ -1297,8 +1300,7 @@ static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1297 if (ret < 0) 1300 if (ret < 0)
1298 goto err_out_child_node; 1301 goto err_out_child_node;
1299 1302
1300 if (nilfs_btree_node_get_nchildren(node) > 1303 if (nilfs_btree_node_get_nchildren(node) > ncmin) {
1301 nilfs_btree_node_nchildren_min(node, btree)) {
1302 path[level].bp_op = nilfs_btree_do_delete; 1304 path[level].bp_op = nilfs_btree_do_delete;
1303 stats->bs_nblocks++; 1305 stats->bs_nblocks++;
1304 goto out; 1306 goto out;
@@ -1315,8 +1317,7 @@ static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1315 if (ret < 0) 1317 if (ret < 0)
1316 goto err_out_curr_node; 1318 goto err_out_curr_node;
1317 sib = (struct nilfs_btree_node *)bh->b_data; 1319 sib = (struct nilfs_btree_node *)bh->b_data;
1318 if (nilfs_btree_node_get_nchildren(sib) > 1320 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
1319 nilfs_btree_node_nchildren_min(sib, btree)) {
1320 path[level].bp_sib_bh = bh; 1321 path[level].bp_sib_bh = bh;
1321 path[level].bp_op = nilfs_btree_borrow_left; 1322 path[level].bp_op = nilfs_btree_borrow_left;
1322 stats->bs_nblocks++; 1323 stats->bs_nblocks++;
@@ -1336,8 +1337,7 @@ static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
1336 if (ret < 0) 1337 if (ret < 0)
1337 goto err_out_curr_node; 1338 goto err_out_curr_node;
1338 sib = (struct nilfs_btree_node *)bh->b_data; 1339 sib = (struct nilfs_btree_node *)bh->b_data;
1339 if (nilfs_btree_node_get_nchildren(sib) > 1340 if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
1340 nilfs_btree_node_nchildren_min(sib, btree)) {
1341 path[level].bp_sib_bh = bh; 1341 path[level].bp_sib_bh = bh;
1342 path[level].bp_op = nilfs_btree_borrow_right; 1342 path[level].bp_op = nilfs_btree_borrow_right;
1343 stats->bs_nblocks++; 1343 stats->bs_nblocks++;