ctree.c (a213501153fd66e2359e091b1612841305ba6551) ctree.c (051e1b9f748ae673b7325d3fc049bb838606cffa)
1/*
2 * Copyright (C) 2007 Oracle. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,

--- 49 unchanged lines hidden (view full) ---

58{
59 btrfs_release_path(NULL, p);
60 kmem_cache_free(btrfs_path_cachep, p);
61}
62
63void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
64{
65 int i;
1/*
2 * Copyright (C) 2007 Oracle. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,

--- 49 unchanged lines hidden (view full) ---

58{
59 btrfs_release_path(NULL, p);
60 kmem_cache_free(btrfs_path_cachep, p);
61}
62
63void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
64{
65 int i;
66 int skip = p->skip_locking;
67 int keep = p->keep_locks;
68
69 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
70 if (!p->nodes[i])
71 continue;
72 if (p->locks[i]) {
73 btrfs_tree_unlock(p->nodes[i]);
74 p->locks[i] = 0;
75 }
76 free_extent_buffer(p->nodes[i]);
77 }
78 memset(p, 0, sizeof(*p));
66 int keep = p->keep_locks;
67
68 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
69 if (!p->nodes[i])
70 continue;
71 if (p->locks[i]) {
72 btrfs_tree_unlock(p->nodes[i]);
73 p->locks[i] = 0;
74 }
75 free_extent_buffer(p->nodes[i]);
76 }
77 memset(p, 0, sizeof(*p));
79 p->skip_locking = skip;
80 p->keep_locks = keep;
81}
82
83struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
84{
85 struct extent_buffer *eb;
86 spin_lock(&root->node_lock);
87 eb = root->node;

--- 1044 unchanged lines hidden (view full) ---

1132
1133 if (level != 1)
1134 return;
1135
1136 if (!path->nodes[level])
1137 return;
1138
1139 node = path->nodes[level];
78 p->keep_locks = keep;
79}
80
81struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
82{
83 struct extent_buffer *eb;
84 spin_lock(&root->node_lock);
85 eb = root->node;

--- 1044 unchanged lines hidden (view full) ---

1130
1131 if (level != 1)
1132 return;
1133
1134 if (!path->nodes[level])
1135 return;
1136
1137 node = path->nodes[level];
1140 WARN_ON(!path->skip_locking && !btrfs_tree_locked(node));
1141
1142 search = btrfs_node_blockptr(node, slot);
1143 blocksize = btrfs_level_size(root, level - 1);
1144 eb = btrfs_find_tree_block(root, search, blocksize);
1145 if (eb) {
1146 free_extent_buffer(eb);
1147 return;
1148 }

--- 38 unchanged lines hidden (view full) ---

1187 highest_read = search;
1188 }
1189}
1190
1191static void unlock_up(struct btrfs_path *path, int level, int lowest_unlock)
1192{
1193 int i;
1194 int skip_level = level;
1138
1139 search = btrfs_node_blockptr(node, slot);
1140 blocksize = btrfs_level_size(root, level - 1);
1141 eb = btrfs_find_tree_block(root, search, blocksize);
1142 if (eb) {
1143 free_extent_buffer(eb);
1144 return;
1145 }

--- 38 unchanged lines hidden (view full) ---

1184 highest_read = search;
1185 }
1186}
1187
1188static void unlock_up(struct btrfs_path *path, int level, int lowest_unlock)
1189{
1190 int i;
1191 int skip_level = level;
1192 int no_skips = 0;
1195 struct extent_buffer *t;
1196
1197 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1198 if (!path->nodes[i])
1199 break;
1200 if (!path->locks[i])
1201 break;
1193 struct extent_buffer *t;
1194
1195 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1196 if (!path->nodes[i])
1197 break;
1198 if (!path->locks[i])
1199 break;
1202 if (path->slots[i] == 0) {
1200 if (!no_skips && path->slots[i] == 0) {
1203 skip_level = i + 1;
1204 continue;
1205 }
1201 skip_level = i + 1;
1202 continue;
1203 }
1206 if (path->keep_locks) {
1204 if (!no_skips && path->keep_locks) {
1207 u32 nritems;
1208 t = path->nodes[i];
1209 nritems = btrfs_header_nritems(t);
1205 u32 nritems;
1206 t = path->nodes[i];
1207 nritems = btrfs_header_nritems(t);
1210 if (nritems < 2 || path->slots[i] >= nritems - 2) {
1211if (path->keep_locks) {
1212//printk("path %p skip level now %d\n", path, skip_level);
1213}
1208 if (nritems < 1 || path->slots[i] >= nritems - 1) {
1214 skip_level = i + 1;
1215 continue;
1216 }
1217 }
1209 skip_level = i + 1;
1210 continue;
1211 }
1212 }
1213 if (skip_level < i && i >= lowest_unlock)
1214 no_skips = 1;
1215
1218 t = path->nodes[i];
1219 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1216 t = path->nodes[i];
1217 if (i >= lowest_unlock && i > skip_level && path->locks[i]) {
1220if (path->keep_locks) {
1221//printk("path %p unlocking level %d slot %d nritems %d skip_level %d\n", path, i, path->slots[i], btrfs_header_nritems(t), skip_level);
1222}
1223 btrfs_tree_unlock(t);
1224 path->locks[i] = 0;
1225 }
1226 }
1227}
1228
1229/*
1230 * look for key in the tree. path is filled in with nodes along the way

--- 8 unchanged lines hidden (view full) ---

1239 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1240 * possible)
1241 */
1242int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1243 *root, struct btrfs_key *key, struct btrfs_path *p, int
1244 ins_len, int cow)
1245{
1246 struct extent_buffer *b;
1218 btrfs_tree_unlock(t);
1219 path->locks[i] = 0;
1220 }
1221 }
1222}
1223
1224/*
1225 * look for key in the tree. path is filled in with nodes along the way

--- 8 unchanged lines hidden (view full) ---

1234 * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
1235 * possible)
1236 */
1237int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
1238 *root, struct btrfs_key *key, struct btrfs_path *p, int
1239 ins_len, int cow)
1240{
1241 struct extent_buffer *b;
1242 struct extent_buffer *tmp;
1247 int slot;
1248 int ret;
1249 int level;
1250 int should_reada = p->reada;
1251 int lowest_unlock = 1;
1252 u8 lowest_level = 0;
1253
1254 lowest_level = p->lowest_level;
1255 WARN_ON(lowest_level && ins_len);
1256 WARN_ON(p->nodes[0] != NULL);
1257 WARN_ON(root == root->fs_info->extent_root &&
1258 !mutex_is_locked(&root->fs_info->alloc_mutex));
1259 WARN_ON(root == root->fs_info->chunk_root &&
1260 !mutex_is_locked(&root->fs_info->chunk_mutex));
1261 WARN_ON(root == root->fs_info->dev_root &&
1262 !mutex_is_locked(&root->fs_info->chunk_mutex));
1263 if (ins_len < 0)
1264 lowest_unlock = 2;
1265again:
1243 int slot;
1244 int ret;
1245 int level;
1246 int should_reada = p->reada;
1247 int lowest_unlock = 1;
1248 u8 lowest_level = 0;
1249
1250 lowest_level = p->lowest_level;
1251 WARN_ON(lowest_level && ins_len);
1252 WARN_ON(p->nodes[0] != NULL);
1253 WARN_ON(root == root->fs_info->extent_root &&
1254 !mutex_is_locked(&root->fs_info->alloc_mutex));
1255 WARN_ON(root == root->fs_info->chunk_root &&
1256 !mutex_is_locked(&root->fs_info->chunk_mutex));
1257 WARN_ON(root == root->fs_info->dev_root &&
1258 !mutex_is_locked(&root->fs_info->chunk_mutex));
1259 if (ins_len < 0)
1260 lowest_unlock = 2;
1261again:
1266 if (!p->skip_locking)
1267 b = btrfs_lock_root_node(root);
1268 else
1269 b = btrfs_root_node(root);
1262 b = btrfs_lock_root_node(root);
1270
1271 while (b) {
1272 level = btrfs_header_level(b);
1273 if (cow) {
1274 int wret;
1275 wret = btrfs_cow_block(trans, root, b,
1276 p->nodes[level + 1],
1277 p->slots[level + 1],
1278 &b);
1279 if (wret) {
1280 free_extent_buffer(b);
1281 return wret;
1282 }
1283 }
1284 BUG_ON(!cow && ins_len);
1285 if (level != btrfs_header_level(b))
1286 WARN_ON(1);
1287 level = btrfs_header_level(b);
1288 p->nodes[level] = b;
1263
1264 while (b) {
1265 level = btrfs_header_level(b);
1266 if (cow) {
1267 int wret;
1268 wret = btrfs_cow_block(trans, root, b,
1269 p->nodes[level + 1],
1270 p->slots[level + 1],
1271 &b);
1272 if (wret) {
1273 free_extent_buffer(b);
1274 return wret;
1275 }
1276 }
1277 BUG_ON(!cow && ins_len);
1278 if (level != btrfs_header_level(b))
1279 WARN_ON(1);
1280 level = btrfs_header_level(b);
1281 p->nodes[level] = b;
1289 if (!p->skip_locking)
1290 p->locks[level] = 1;
1282 p->locks[level] = 1;
1291 ret = check_block(root, p, level);
1292 if (ret)
1293 return -1;
1294
1295 ret = bin_search(b, key, level, &slot);
1296 if (level != 0) {
1297 if (ret && slot > 0)
1298 slot -= 1;

--- 24 unchanged lines hidden (view full) ---

1323 unlock_up(p, level, lowest_unlock);
1324 break;
1325 }
1326
1327 if (should_reada)
1328 reada_for_search(root, p, level, slot,
1329 key->objectid);
1330
1283 ret = check_block(root, p, level);
1284 if (ret)
1285 return -1;
1286
1287 ret = bin_search(b, key, level, &slot);
1288 if (level != 0) {
1289 if (ret && slot > 0)
1290 slot -= 1;

--- 24 unchanged lines hidden (view full) ---

1315 unlock_up(p, level, lowest_unlock);
1316 break;
1317 }
1318
1319 if (should_reada)
1320 reada_for_search(root, p, level, slot,
1321 key->objectid);
1322
1331 b = read_node_slot(root, b, slot);
1332 if (!p->skip_locking)
1333 btrfs_tree_lock(b);
1334 unlock_up(p, level + 1, lowest_unlock);
1323 tmp = btrfs_find_tree_block(root,
1324 btrfs_node_blockptr(b, slot),
1325 btrfs_level_size(root, level - 1));
1326 if (tmp && btrfs_buffer_uptodate(tmp,
1327 btrfs_node_ptr_generation(b, slot))) {
1328 b = tmp;
1329 } else {
1330 /*
1331 * reduce lock contention at high levels
1332 * of the btree by dropping locks before
1333 * we read.
1334 */
1335 if (level > 1) {
1336 btrfs_release_path(NULL, p);
1337 if (tmp)
1338 free_extent_buffer(tmp);
1339 goto again;
1340 } else {
1341 b = read_node_slot(root, b, slot);
1342 }
1343 }
1344 btrfs_tree_lock(b);
1345 unlock_up(p, level, lowest_unlock);
1335 } else {
1336 p->slots[level] = slot;
1337 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1338 sizeof(struct btrfs_item) + ins_len) {
1339 int sret = split_leaf(trans, root, key,
1340 p, ins_len, ret == 0);
1341 BUG_ON(sret > 0);
1342 if (sret)

--- 1659 unchanged lines hidden (view full) ---

3002 btrfs_tree_unlock(next);
3003 free_extent_buffer(next);
3004 }
3005
3006 if (level == 1 && path->locks[1] && path->reada)
3007 reada_for_search(root, path, level, slot, 0);
3008
3009 next = read_node_slot(root, c, slot);
1346 } else {
1347 p->slots[level] = slot;
1348 if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
1349 sizeof(struct btrfs_item) + ins_len) {
1350 int sret = split_leaf(trans, root, key,
1351 p, ins_len, ret == 0);
1352 BUG_ON(sret > 0);
1353 if (sret)

--- 1659 unchanged lines hidden (view full) ---

3013 btrfs_tree_unlock(next);
3014 free_extent_buffer(next);
3015 }
3016
3017 if (level == 1 && path->locks[1] && path->reada)
3018 reada_for_search(root, path, level, slot, 0);
3019
3020 next = read_node_slot(root, c, slot);
3010 if (!path->skip_locking) {
3011 if (!btrfs_tree_locked(c)) {
3012 int i;
3013 WARN_ON(1);
3014printk("path %p no lock on level %d\n", path, level);
3015for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
3016printk("path %p level %d slot %d nritems %d\n", path, i, path->slots[i], btrfs_header_nritems(path->nodes[i]));
3017}
3018 }
3019 btrfs_tree_lock(next);
3020 }
3021 WARN_ON(!btrfs_tree_locked(c));
3022 btrfs_tree_lock(next);
3021 break;
3022 }
3023 path->slots[level] = slot;
3024 while(1) {
3025 level--;
3026 c = path->nodes[level];
3027 if (path->locks[level])
3028 btrfs_tree_unlock(c);
3029 free_extent_buffer(c);
3030 path->nodes[level] = next;
3031 path->slots[level] = 0;
3032 path->locks[level] = 1;
3033 if (!level)
3034 break;
3035 if (level == 1 && path->locks[1] && path->reada)
3036 reada_for_search(root, path, level, slot, 0);
3037 next = read_node_slot(root, next, 0);
3023 break;
3024 }
3025 path->slots[level] = slot;
3026 while(1) {
3027 level--;
3028 c = path->nodes[level];
3029 if (path->locks[level])
3030 btrfs_tree_unlock(c);
3031 free_extent_buffer(c);
3032 path->nodes[level] = next;
3033 path->slots[level] = 0;
3034 path->locks[level] = 1;
3035 if (!level)
3036 break;
3037 if (level == 1 && path->locks[1] && path->reada)
3038 reada_for_search(root, path, level, slot, 0);
3039 next = read_node_slot(root, next, 0);
3038 if (!path->skip_locking) {
3039 WARN_ON(!btrfs_tree_locked(path->nodes[level]));
3040 btrfs_tree_lock(next);
3041 }
3040 WARN_ON(!btrfs_tree_locked(path->nodes[level]));
3041 btrfs_tree_lock(next);
3042 }
3043done:
3044 unlock_up(path, 0, 1);
3045 return 0;
3046}
3047
3048int btrfs_previous_item(struct btrfs_root *root,
3049 struct btrfs_path *path, u64 min_objectid,

--- 22 unchanged lines hidden --- 		3042 }
3043done:
3044 unlock_up(path, 0, 1);
3045 return 0;
3046}
3047
3048int btrfs_previous_item(struct btrfs_root *root,
3049 struct btrfs_path *path, u64 min_objectid,

--- 22 unchanged lines hidden ---