projects / linux-2.6-block.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Btrfs: Start btree concurrency work.
[linux-2.6-block.git] / fs / btrfs / extent-tree.c
CommitLineData
6cbd5570
CM		 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,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
ec6b910f 18#include <linux/sched.h>
edbd8d4e 19#include <linux/pagemap.h>
ec44a35c 20#include <linux/writeback.h>
74493f7a 21#include "hash.h"
a5eb62e3 22#include "crc32c.h"
fec577fb
CM		 23#include "ctree.h"
24#include "disk-io.h"
25#include "print-tree.h"
e089f05c 26#include "transaction.h"
0b86a832 27#include "volumes.h"
925baedd 28#include "locking.h"
fec577fb 29
0b86a832 30#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
96b5179d 31#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
0b86a832
CM		 32#define BLOCK_GROUP_SYSTEM EXTENT_NEW
33
96b5179d
CM		 34#define BLOCK_GROUP_DIRTY EXTENT_DIRTY
35
e089f05c
CM		 36static int finish_current_insert(struct btrfs_trans_handle *trans, struct
37 btrfs_root *extent_root);
e20d96d6
CM		 38static int del_pending_extents(struct btrfs_trans_handle *trans, struct
39 btrfs_root *extent_root);
925baedd
CM		 40static struct btrfs_block_group_cache *
41__btrfs_find_block_group(struct btrfs_root *root,
42 struct btrfs_block_group_cache *hint,
43 u64 search_start, int data, int owner);
d548ee51 44
925baedd
CM		 45void maybe_lock_mutex(struct btrfs_root *root)
46{
47 if (root != root->fs_info->extent_root &&
48 root != root->fs_info->chunk_root &&
49 root != root->fs_info->dev_root) {
50 mutex_lock(&root->fs_info->alloc_mutex);
51 }
52}
53
54void maybe_unlock_mutex(struct btrfs_root *root)
55{
56 if (root != root->fs_info->extent_root &&
57 root != root->fs_info->chunk_root &&
58 root != root->fs_info->dev_root) {
59 mutex_unlock(&root->fs_info->alloc_mutex);
60 }
61}
fec577fb 62
e37c9e69
CM		 63static int cache_block_group(struct btrfs_root *root,
64 struct btrfs_block_group_cache *block_group)
65{
66 struct btrfs_path *path;
67 int ret;
68 struct btrfs_key key;
5f39d397 69 struct extent_buffer *leaf;
d1310b2e 70 struct extent_io_tree *free_space_cache;
e37c9e69 71 int slot;
e37c9e69
CM		 72 u64 last = 0;
73 u64 hole_size;
7d7d6068 74 u64 first_free;
e37c9e69
CM		 75 int found = 0;
76
00f5c795
CM		 77 if (!block_group)
78 return 0;
79
e37c9e69 80 root = root->fs_info->extent_root;
f510cfec 81 free_space_cache = &root->fs_info->free_space_cache;
e37c9e69
CM		 82
83 if (block_group->cached)
84 return 0;
f510cfec 85
e37c9e69
CM		 86 path = btrfs_alloc_path();
87 if (!path)
88 return -ENOMEM;
7d7d6068 89
2cc58cf2 90 path->reada = 2;
925baedd 91 path->skip_locking = 1;
7d7d6068 92 first_free = block_group->key.objectid;
e37c9e69 93 key.objectid = block_group->key.objectid;
e37c9e69
CM		 94 key.offset = 0;
95 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
96 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
97 if (ret < 0)
98 return ret;
0b86a832 99 ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
d548ee51
Y		 100 if (ret < 0)
101 return ret;
102 if (ret == 0) {
103 leaf = path->nodes[0];
104 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
105 if (key.objectid + key.offset > first_free)
106 first_free = key.objectid + key.offset;
107 }
e37c9e69 108 while(1) {
5f39d397 109 leaf = path->nodes[0];
e37c9e69 110 slot = path->slots[0];
5f39d397 111 if (slot >= btrfs_header_nritems(leaf)) {
e37c9e69 112 ret = btrfs_next_leaf(root, path);
54aa1f4d
CM		 113 if (ret < 0)
114 goto err;
de428b63 115 if (ret == 0) {
e37c9e69 116 continue;
de428b63 117 } else {
e37c9e69
CM		 118 break;
119 }
120 }
5f39d397 121 btrfs_item_key_to_cpu(leaf, &key, slot);
7d7d6068 122 if (key.objectid < block_group->key.objectid) {
7d7d6068
Y		 123 goto next;
124 }
e37c9e69
CM		 125 if (key.objectid >= block_group->key.objectid +
126 block_group->key.offset) {
e37c9e69
CM		 127 break;
128 }
7d7d6068 129
e37c9e69
CM		 130 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
131 if (!found) {
7d7d6068 132 last = first_free;
e37c9e69 133 found = 1;
e37c9e69 134 }
f510cfec
CM		 135 if (key.objectid > last) {
136 hole_size = key.objectid - last;
137 set_extent_dirty(free_space_cache, last,
138 last + hole_size - 1,
139 GFP_NOFS);
7d7d6068
Y		 140 }
141 last = key.objectid + key.offset;
e37c9e69 142 }
7d7d6068 143next:
e37c9e69
CM		 144 path->slots[0]++;
145 }
146
7d7d6068
Y		 147 if (!found)
148 last = first_free;
149 if (block_group->key.objectid +
150 block_group->key.offset > last) {
151 hole_size = block_group->key.objectid +
152 block_group->key.offset - last;
f510cfec
CM		 153 set_extent_dirty(free_space_cache, last,
154 last + hole_size - 1, GFP_NOFS);
7d7d6068 155 }
e37c9e69 156 block_group->cached = 1;
54aa1f4d 157err:
e37c9e69
CM		 158 btrfs_free_path(path);
159 return 0;
160}
161
0ef3e66b
CM		 162struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
163 btrfs_fs_info *info,
164 u64 bytenr)
165{
166 struct extent_io_tree *block_group_cache;
167 struct btrfs_block_group_cache *block_group = NULL;
168 u64 ptr;
169 u64 start;
170 u64 end;
171 int ret;
172
173 bytenr = max_t(u64, bytenr,
174 BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
175 block_group_cache = &info->block_group_cache;
176 ret = find_first_extent_bit(block_group_cache,
177 bytenr, &start, &end,
178 BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
179 BLOCK_GROUP_SYSTEM);
180 if (ret) {
181 return NULL;
182 }
183 ret = get_state_private(block_group_cache, start, &ptr);
184 if (ret)
185 return NULL;
186
187 block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
188 return block_group;
189}
190
5276aeda
CM		 191struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
192 btrfs_fs_info *info,
db94535d 193 u64 bytenr)
be744175 194{
d1310b2e 195 struct extent_io_tree *block_group_cache;
96b5179d
CM		 196 struct btrfs_block_group_cache *block_group = NULL;
197 u64 ptr;
198 u64 start;
199 u64 end;
be744175
CM		 200 int ret;
201
a061fc8d
CM		 202 bytenr = max_t(u64, bytenr,
203 BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
96b5179d
CM		 204 block_group_cache = &info->block_group_cache;
205 ret = find_first_extent_bit(block_group_cache,
db94535d 206 bytenr, &start, &end,
0b86a832
CM		 207 BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
208 BLOCK_GROUP_SYSTEM);
be744175 209 if (ret) {
96b5179d 210 return NULL;
be744175 211 }
96b5179d
CM		 212 ret = get_state_private(block_group_cache, start, &ptr);
213 if (ret)
214 return NULL;
215
ae2f5411 216 block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
5cf66426 217 if (block_group->key.objectid <= bytenr && bytenr <
96b5179d
CM		 218 block_group->key.objectid + block_group->key.offset)
219 return block_group;
be744175
CM		 220 return NULL;
221}
0b86a832
CM		 222
223static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
224{
593060d7 225 return (cache->flags & bits) == bits;
0b86a832
CM		 226}
227
228static int noinline find_search_start(struct btrfs_root *root,
98ed5174 229 struct btrfs_block_group_cache **cache_ret,
0ef3e66b 230 u64 *start_ret, u64 num, int data)
e37c9e69 231{
e37c9e69
CM		 232 int ret;
233 struct btrfs_block_group_cache *cache = *cache_ret;
d7fc640e 234 struct extent_io_tree *free_space_cache;
7d1660d4 235 struct extent_state *state;
e19caa5f 236 u64 last;
f510cfec 237 u64 start = 0;
257d0ce3 238 u64 cache_miss = 0;
c31f8830 239 u64 total_fs_bytes;
0b86a832 240 u64 search_start = *start_ret;
f84a8b36 241 int wrapped = 0;
e37c9e69 242
c31f8830 243 total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
d7fc640e
CM		 244 free_space_cache = &root->fs_info->free_space_cache;
245
0ef3e66b
CM		 246 if (!cache)
247 goto out;
248
e37c9e69 249again:
54aa1f4d 250 ret = cache_block_group(root, cache);
0ef3e66b 251 if (ret) {
54aa1f4d 252 goto out;
0ef3e66b 253 }
f84a8b36 254
e19caa5f 255 last = max(search_start, cache->key.objectid);
0ef3e66b 256 if (!block_group_bits(cache, data) || cache->ro)
0b86a832 257 goto new_group;
e19caa5f 258
7d1660d4
CM		 259 spin_lock_irq(&free_space_cache->lock);
260 state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
e37c9e69 261 while(1) {
7d1660d4 262 if (!state) {
257d0ce3
CM		 263 if (!cache_miss)
264 cache_miss = last;
7d1660d4 265 spin_unlock_irq(&free_space_cache->lock);
e19caa5f
CM		 266 goto new_group;
267 }
f510cfec 268
7d1660d4
CM		 269 start = max(last, state->start);
270 last = state->end + 1;
257d0ce3 271 if (last - start < num) {
7d1660d4
CM		 272 do {
273 state = extent_state_next(state);
274 } while(state && !(state->state & EXTENT_DIRTY));
f510cfec 275 continue;
257d0ce3 276 }
7d1660d4 277 spin_unlock_irq(&free_space_cache->lock);
0ef3e66b 278 if (cache->ro) {
8f18cf13 279 goto new_group;
0ef3e66b 280 }
0b86a832 281 if (start + num > cache->key.objectid + cache->key.offset)
e37c9e69 282 goto new_group;
8790d502 283 if (!block_group_bits(cache, data)) {
611f0e00 284 printk("block group bits don't match %Lu %d\n", cache->flags, data);
8790d502 285 }
0b86a832
CM		 286 *start_ret = start;
287 return 0;
8790d502
CM		 288 }
289out:
1a2b2ac7
CM		 290 cache = btrfs_lookup_block_group(root->fs_info, search_start);
291 if (!cache) {
0b86a832 292 printk("Unable to find block group for %Lu\n", search_start);
1a2b2ac7 293 WARN_ON(1);
1a2b2ac7 294 }
0b86a832 295 return -ENOSPC;
e37c9e69
CM		 296
297new_group:
e19caa5f 298 last = cache->key.objectid + cache->key.offset;
f84a8b36 299wrapped:
0ef3e66b 300 cache = btrfs_lookup_first_block_group(root->fs_info, last);
c31f8830 301 if (!cache || cache->key.objectid >= total_fs_bytes) {
0e4de584 302no_cache:
f84a8b36
CM		 303 if (!wrapped) {
304 wrapped = 1;
305 last = search_start;
f84a8b36
CM		 306 goto wrapped;
307 }
1a2b2ac7 308 goto out;
e37c9e69 309 }
257d0ce3
CM		 310 if (cache_miss && !cache->cached) {
311 cache_block_group(root, cache);
312 last = cache_miss;
0ef3e66b 313 cache = btrfs_lookup_first_block_group(root->fs_info, last);
257d0ce3 314 }
0ef3e66b 315 cache_miss = 0;
925baedd 316 cache = __btrfs_find_block_group(root, cache, last, data, 0);
0e4de584
CM		 317 if (!cache)
318 goto no_cache;
e37c9e69
CM		 319 *cache_ret = cache;
320 goto again;
321}
322
84f54cfa
CM		 323static u64 div_factor(u64 num, int factor)
324{
257d0ce3
CM		 325 if (factor == 10)
326 return num;
84f54cfa
CM		 327 num *= factor;
328 do_div(num, 10);
329 return num;
330}
331
6324fbf3
CM		 332static int block_group_state_bits(u64 flags)
333{
334 int bits = 0;
335 if (flags & BTRFS_BLOCK_GROUP_DATA)
336 bits |= BLOCK_GROUP_DATA;
337 if (flags & BTRFS_BLOCK_GROUP_METADATA)
338 bits |= BLOCK_GROUP_METADATA;
339 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
340 bits |= BLOCK_GROUP_SYSTEM;
341 return bits;
342}
343
925baedd
CM		 344static struct btrfs_block_group_cache *
345__btrfs_find_block_group(struct btrfs_root *root,
346 struct btrfs_block_group_cache *hint,
347 u64 search_start, int data, int owner)
cd1bc465 348{
96b5179d 349 struct btrfs_block_group_cache *cache;
d1310b2e 350 struct extent_io_tree *block_group_cache;
31f3c99b 351 struct btrfs_block_group_cache *found_group = NULL;
cd1bc465
CM		 352 struct btrfs_fs_info *info = root->fs_info;
353 u64 used;
31f3c99b 354 u64 last = 0;
96b5179d
CM		 355 u64 start;
356 u64 end;
357 u64 free_check;
358 u64 ptr;
359 int bit;
cd1bc465 360 int ret;
31f3c99b 361 int full_search = 0;
bce4eae9 362 int factor = 10;
0ef3e66b 363 int wrapped = 0;
de428b63 364
96b5179d
CM		 365 block_group_cache = &info->block_group_cache;
366
a236aed1
CM		 367 if (data & BTRFS_BLOCK_GROUP_METADATA)
368 factor = 9;
be744175 369
6324fbf3 370 bit = block_group_state_bits(data);
be744175 371
0ef3e66b 372 if (search_start) {
be744175 373 struct btrfs_block_group_cache *shint;
0ef3e66b 374 shint = btrfs_lookup_first_block_group(info, search_start);
8f18cf13 375 if (shint && block_group_bits(shint, data) && !shint->ro) {
be744175 376 used = btrfs_block_group_used(&shint->item);
324ae4df
Y		 377 if (used + shint->pinned <
378 div_factor(shint->key.offset, factor)) {
be744175
CM		 379 return shint;
380 }
381 }
382 }
0ef3e66b 383 if (hint && !hint->ro && block_group_bits(hint, data)) {
31f3c99b 384 used = btrfs_block_group_used(&hint->item);
324ae4df
Y		 385 if (used + hint->pinned <
386 div_factor(hint->key.offset, factor)) {
31f3c99b
CM		 387 return hint;
388 }
e19caa5f 389 last = hint->key.objectid + hint->key.offset;
31f3c99b 390 } else {
e37c9e69 391 if (hint)
0ef3e66b 392 last = max(hint->key.objectid, search_start);
e37c9e69 393 else
0ef3e66b 394 last = search_start;
31f3c99b 395 }
31f3c99b 396again:
cd1bc465 397 while(1) {
96b5179d
CM		 398 ret = find_first_extent_bit(block_group_cache, last,
399 &start, &end, bit);
400 if (ret)
cd1bc465 401 break;
96b5179d
CM		 402
403 ret = get_state_private(block_group_cache, start, &ptr);
0ef3e66b
CM		 404 if (ret) {
405 last = end + 1;
406 continue;
407 }
96b5179d 408
ae2f5411 409 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
96b5179d
CM		 410 last = cache->key.objectid + cache->key.offset;
411 used = btrfs_block_group_used(&cache->item);
412
8f18cf13 413 if (!cache->ro && block_group_bits(cache, data)) {
0ef3e66b 414 free_check = div_factor(cache->key.offset, factor);
8790d502
CM		 415 if (used + cache->pinned < free_check) {
416 found_group = cache;
417 goto found;
418 }
6324fbf3 419 }
de428b63 420 cond_resched();
cd1bc465 421 }
0ef3e66b
CM		 422 if (!wrapped) {
423 last = search_start;
424 wrapped = 1;
425 goto again;
426 }
427 if (!full_search && factor < 10) {
be744175 428 last = search_start;
31f3c99b 429 full_search = 1;
0ef3e66b 430 factor = 10;
31f3c99b
CM		 431 goto again;
432 }
be744175 433found:
31f3c99b 434 return found_group;
cd1bc465
CM		 435}
436
925baedd
CM		 437struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
438 struct btrfs_block_group_cache
439 *hint, u64 search_start,
440 int data, int owner)
441{
442
443 struct btrfs_block_group_cache *ret;
444 mutex_lock(&root->fs_info->alloc_mutex);
445 ret = __btrfs_find_block_group(root, hint, search_start, data, owner);
446 mutex_unlock(&root->fs_info->alloc_mutex);
447 return ret;
448}
7bb86316 449static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
74493f7a
CM		 450 u64 owner, u64 owner_offset)
451{
452 u32 high_crc = ~(u32)0;
453 u32 low_crc = ~(u32)0;
454 __le64 lenum;
74493f7a 455 lenum = cpu_to_le64(root_objectid);
a5eb62e3 456 high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
7bb86316 457 lenum = cpu_to_le64(ref_generation);
a5eb62e3 458 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
21a4989d
CM		 459 if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
460 lenum = cpu_to_le64(owner);
a5eb62e3 461 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
21a4989d 462 lenum = cpu_to_le64(owner_offset);
a5eb62e3 463 low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
21a4989d 464 }
74493f7a
CM		 465 return ((u64)high_crc << 32) | (u64)low_crc;
466}
467
7bb86316
CM		 468static int match_extent_ref(struct extent_buffer *leaf,
469 struct btrfs_extent_ref *disk_ref,
470 struct btrfs_extent_ref *cpu_ref)
471{
472 int ret;
473 int len;
474
475 if (cpu_ref->objectid)
476 len = sizeof(*cpu_ref);
477 else
478 len = 2 * sizeof(u64);
479 ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
480 len);
481 return ret == 0;
482}
483
98ed5174
CM		 484static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
485 struct btrfs_root *root,
486 struct btrfs_path *path, u64 bytenr,
487 u64 root_objectid,
488 u64 ref_generation, u64 owner,
489 u64 owner_offset, int del)
74493f7a
CM		 490{
491 u64 hash;
492 struct btrfs_key key;
7bb86316 493 struct btrfs_key found_key;
74493f7a 494 struct btrfs_extent_ref ref;
7bb86316
CM		 495 struct extent_buffer *leaf;
496 struct btrfs_extent_ref *disk_ref;
497 int ret;
498 int ret2;
499
500 btrfs_set_stack_ref_root(&ref, root_objectid);
501 btrfs_set_stack_ref_generation(&ref, ref_generation);
502 btrfs_set_stack_ref_objectid(&ref, owner);
503 btrfs_set_stack_ref_offset(&ref, owner_offset);
504
505 hash = hash_extent_ref(root_objectid, ref_generation, owner,
506 owner_offset);
507 key.offset = hash;
508 key.objectid = bytenr;
509 key.type = BTRFS_EXTENT_REF_KEY;
510
511 while (1) {
512 ret = btrfs_search_slot(trans, root, &key, path,
513 del ? -1 : 0, del);
514 if (ret < 0)
515 goto out;
516 leaf = path->nodes[0];
517 if (ret != 0) {
518 u32 nritems = btrfs_header_nritems(leaf);
519 if (path->slots[0] >= nritems) {
520 ret2 = btrfs_next_leaf(root, path);
521 if (ret2)
522 goto out;
523 leaf = path->nodes[0];
524 }
525 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
526 if (found_key.objectid != bytenr ||
527 found_key.type != BTRFS_EXTENT_REF_KEY)
528 goto out;
529 key.offset = found_key.offset;
530 if (del) {
531 btrfs_release_path(root, path);
532 continue;
533 }
534 }
535 disk_ref = btrfs_item_ptr(path->nodes[0],
536 path->slots[0],
537 struct btrfs_extent_ref);
538 if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
539 ret = 0;
540 goto out;
541 }
542 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
543 key.offset = found_key.offset + 1;
544 btrfs_release_path(root, path);
545 }
546out:
547 return ret;
548}
549
d8d5f3e1
CM		 550/*
551 * Back reference rules. Back refs have three main goals:
552 *
553 * 1) differentiate between all holders of references to an extent so that
554 * when a reference is dropped we can make sure it was a valid reference
555 * before freeing the extent.
556 *
557 * 2) Provide enough information to quickly find the holders of an extent
558 * if we notice a given block is corrupted or bad.
559 *
560 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
561 * maintenance. This is actually the same as #2, but with a slightly
562 * different use case.
563 *
564 * File extents can be referenced by:
565 *
566 * - multiple snapshots, subvolumes, or different generations in one subvol
567 * - different files inside a single subvolume (in theory, not implemented yet)
568 * - different offsets inside a file (bookend extents in file.c)
569 *
570 * The extent ref structure has fields for:
571 *
572 * - Objectid of the subvolume root
573 * - Generation number of the tree holding the reference
574 * - objectid of the file holding the reference
575 * - offset in the file corresponding to the key holding the reference
576 *
577 * When a file extent is allocated the fields are filled in:
578 * (root_key.objectid, trans->transid, inode objectid, offset in file)
579 *
580 * When a leaf is cow'd new references are added for every file extent found
581 * in the leaf. It looks the same as the create case, but trans->transid
582 * will be different when the block is cow'd.
583 *
584 * (root_key.objectid, trans->transid, inode objectid, offset in file)
585 *
586 * When a file extent is removed either during snapshot deletion or file
587 * truncation, the corresponding back reference is found
588 * by searching for:
589 *
590 * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
591 * inode objectid, offset in file)
592 *
593 * Btree extents can be referenced by:
594 *
595 * - Different subvolumes
596 * - Different generations of the same subvolume
597 *
598 * Storing sufficient information for a full reverse mapping of a btree
599 * block would require storing the lowest key of the block in the backref,
600 * and it would require updating that lowest key either before write out or
601 * every time it changed. Instead, the objectid of the lowest key is stored
602 * along with the level of the tree block. This provides a hint
603 * about where in the btree the block can be found. Searches through the
604 * btree only need to look for a pointer to that block, so they stop one
605 * level higher than the level recorded in the backref.
606 *
607 * Some btrees do not do reference counting on their extents. These
608 * include the extent tree and the tree of tree roots. Backrefs for these
609 * trees always have a generation of zero.
610 *
611 * When a tree block is created, back references are inserted:
612 *
f6dbff55 613 * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
d8d5f3e1
CM		 614 *
615 * When a tree block is cow'd in a reference counted root,
616 * new back references are added for all the blocks it points to.
617 * These are of the form (trans->transid will have increased since creation):
618 *
f6dbff55 619 * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
d8d5f3e1
CM		 620 *
621 * Because the lowest_key_objectid and the level are just hints
622 * they are not used when backrefs are deleted. When a backref is deleted:
623 *
624 * if backref was for a tree root:
625 * root_objectid = root->root_key.objectid
626 * else
627 * root_objectid = btrfs_header_owner(parent)
628 *
629 * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
630 *
631 * Back Reference Key hashing:
632 *
633 * Back references have four fields, each 64 bits long. Unfortunately,
634 * This is hashed into a single 64 bit number and placed into the key offset.
635 * The key objectid corresponds to the first byte in the extent, and the
636 * key type is set to BTRFS_EXTENT_REF_KEY
637 */
7bb86316
CM		 638int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
639 struct btrfs_root *root,
640 struct btrfs_path *path, u64 bytenr,
641 u64 root_objectid, u64 ref_generation,
642 u64 owner, u64 owner_offset)
643{
644 u64 hash;
645 struct btrfs_key key;
646 struct btrfs_extent_ref ref;
647 struct btrfs_extent_ref *disk_ref;
74493f7a
CM		 648 int ret;
649
650 btrfs_set_stack_ref_root(&ref, root_objectid);
7bb86316 651 btrfs_set_stack_ref_generation(&ref, ref_generation);
74493f7a
CM		 652 btrfs_set_stack_ref_objectid(&ref, owner);
653 btrfs_set_stack_ref_offset(&ref, owner_offset);
654
7bb86316
CM		 655 hash = hash_extent_ref(root_objectid, ref_generation, owner,
656 owner_offset);
74493f7a
CM		 657 key.offset = hash;
658 key.objectid = bytenr;
659 key.type = BTRFS_EXTENT_REF_KEY;
660
661 ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
662 while (ret == -EEXIST) {
7bb86316
CM		 663 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
664 struct btrfs_extent_ref);
665 if (match_extent_ref(path->nodes[0], disk_ref, &ref))
666 goto out;
667 key.offset++;
668 btrfs_release_path(root, path);
669 ret = btrfs_insert_empty_item(trans, root, path, &key,
670 sizeof(ref));
74493f7a 671 }
7bb86316
CM		 672 if (ret)
673 goto out;
674 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
675 struct btrfs_extent_ref);
676 write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
677 sizeof(ref));
678 btrfs_mark_buffer_dirty(path->nodes[0]);
679out:
680 btrfs_release_path(root, path);
681 return ret;
74493f7a
CM		 682}
683
925baedd 684static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
b18c6685 685 struct btrfs_root *root,
74493f7a 686 u64 bytenr, u64 num_bytes,
7bb86316 687 u64 root_objectid, u64 ref_generation,
74493f7a 688 u64 owner, u64 owner_offset)
02217ed2 689{
5caf2a00 690 struct btrfs_path *path;
02217ed2 691 int ret;
e2fa7227 692 struct btrfs_key key;
5f39d397 693 struct extent_buffer *l;
234b63a0 694 struct btrfs_extent_item *item;
cf27e1ee 695 u32 refs;
037e6390 696
db94535d 697 WARN_ON(num_bytes < root->sectorsize);
5caf2a00 698 path = btrfs_alloc_path();
54aa1f4d
CM		 699 if (!path)
700 return -ENOMEM;
26b8003f 701
3c12ac72 702 path->reada = 1;
db94535d 703 key.objectid = bytenr;
62e2749e 704 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
db94535d 705 key.offset = num_bytes;
5caf2a00 706 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
9f5fae2f 707 0, 1);
54aa1f4d
CM		 708 if (ret < 0)
709 return ret;
a429e513 710 if (ret != 0) {
a28ec197 711 BUG();
a429e513 712 }
02217ed2 713 BUG_ON(ret != 0);
5f39d397 714 l = path->nodes[0];
5caf2a00 715 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
5f39d397
CM		 716 refs = btrfs_extent_refs(l, item);
717 btrfs_set_extent_refs(l, item, refs + 1);
5caf2a00 718 btrfs_mark_buffer_dirty(path->nodes[0]);
a28ec197 719
5caf2a00 720 btrfs_release_path(root->fs_info->extent_root, path);
7bb86316 721
3c12ac72 722 path->reada = 1;
7bb86316
CM		 723 ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
724 path, bytenr, root_objectid,
725 ref_generation, owner, owner_offset);
726 BUG_ON(ret);
9f5fae2f 727 finish_current_insert(trans, root->fs_info->extent_root);
e20d96d6 728 del_pending_extents(trans, root->fs_info->extent_root);
74493f7a
CM		 729
730 btrfs_free_path(path);
02217ed2
CM		 731 return 0;
732}
733
925baedd
CM		 734int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
735 struct btrfs_root *root,
736 u64 bytenr, u64 num_bytes,
737 u64 root_objectid, u64 ref_generation,
738 u64 owner, u64 owner_offset)
739{
740 int ret;
741
742 mutex_lock(&root->fs_info->alloc_mutex);
743 ret = __btrfs_inc_extent_ref(trans, root, bytenr, num_bytes,
744 root_objectid, ref_generation,
745 owner, owner_offset);
746 mutex_unlock(&root->fs_info->alloc_mutex);
747 return ret;
748}
749
e9d0b13b
CM		 750int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
751 struct btrfs_root *root)
752{
753 finish_current_insert(trans, root->fs_info->extent_root);
754 del_pending_extents(trans, root->fs_info->extent_root);
755 return 0;
756}
757
b18c6685 758static int lookup_extent_ref(struct btrfs_trans_handle *trans,
db94535d
CM		 759 struct btrfs_root *root, u64 bytenr,
760 u64 num_bytes, u32 *refs)
a28ec197 761{
5caf2a00 762 struct btrfs_path *path;
a28ec197 763 int ret;
e2fa7227 764 struct btrfs_key key;
5f39d397 765 struct extent_buffer *l;
234b63a0 766 struct btrfs_extent_item *item;
5caf2a00 767
db94535d 768 WARN_ON(num_bytes < root->sectorsize);
5caf2a00 769 path = btrfs_alloc_path();
3c12ac72 770 path->reada = 1;
db94535d
CM		 771 key.objectid = bytenr;
772 key.offset = num_bytes;
62e2749e 773 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
5caf2a00 774 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
9f5fae2f 775 0, 0);
54aa1f4d
CM		 776 if (ret < 0)
777 goto out;
5f39d397
CM		 778 if (ret != 0) {
779 btrfs_print_leaf(root, path->nodes[0]);
db94535d 780 printk("failed to find block number %Lu\n", bytenr);
a28ec197 781 BUG();
5f39d397
CM		 782 }
783 l = path->nodes[0];
5caf2a00 784 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
5f39d397 785 *refs = btrfs_extent_refs(l, item);
54aa1f4d 786out:
5caf2a00 787 btrfs_free_path(path);
a28ec197
CM		 788 return 0;
789}
790
be20aa9d
CM		 791u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
792 struct btrfs_path *count_path,
a68d5933 793 u64 expected_owner,
be20aa9d
CM		 794 u64 first_extent)
795{
796 struct btrfs_root *extent_root = root->fs_info->extent_root;
797 struct btrfs_path *path;
798 u64 bytenr;
799 u64 found_objectid;
a68d5933 800 u64 found_owner;
56b453c9 801 u64 root_objectid = root->root_key.objectid;
be20aa9d 802 u32 total_count = 0;
bbaf549e 803 u32 extent_refs;
be20aa9d 804 u32 cur_count;
be20aa9d
CM		 805 u32 nritems;
806 int ret;
807 struct btrfs_key key;
808 struct btrfs_key found_key;
809 struct extent_buffer *l;
810 struct btrfs_extent_item *item;
811 struct btrfs_extent_ref *ref_item;
812 int level = -1;
813
925baedd
CM		 814 /* FIXME, needs locking */
815 BUG();
816
817 mutex_lock(&root->fs_info->alloc_mutex);
be20aa9d
CM		 818 path = btrfs_alloc_path();
819again:
820 if (level == -1)
821 bytenr = first_extent;
822 else
823 bytenr = count_path->nodes[level]->start;
824
825 cur_count = 0;
826 key.objectid = bytenr;
827 key.offset = 0;
828
829 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
830 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
831 if (ret < 0)
832 goto out;
833 BUG_ON(ret == 0);
834
835 l = path->nodes[0];
836 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
837
838 if (found_key.objectid != bytenr ||
839 found_key.type != BTRFS_EXTENT_ITEM_KEY) {
840 goto out;
841 }
842
843 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
bbaf549e 844 extent_refs = btrfs_extent_refs(l, item);
be20aa9d 845 while (1) {
bd09835d 846 l = path->nodes[0];
be20aa9d
CM		 847 nritems = btrfs_header_nritems(l);
848 if (path->slots[0] >= nritems) {
849 ret = btrfs_next_leaf(extent_root, path);
850 if (ret == 0)
851 continue;
852 break;
853 }
854 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
855 if (found_key.objectid != bytenr)
856 break;
bd09835d 857
be20aa9d
CM		 858 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
859 path->slots[0]++;
860 continue;
861 }
862
863 cur_count++;
864 ref_item = btrfs_item_ptr(l, path->slots[0],
865 struct btrfs_extent_ref);
866 found_objectid = btrfs_ref_root(l, ref_item);
867
56b453c9
CM		 868 if (found_objectid != root_objectid) {
869 total_count = 2;
4313b399 870 goto out;
56b453c9 871 }
a68d5933
CM		 872 if (level == -1) {
873 found_owner = btrfs_ref_objectid(l, ref_item);
874 if (found_owner != expected_owner) {
875 total_count = 2;
876 goto out;
877 }
bbaf549e
CM		 878 /*
879 * nasty. we don't count a reference held by
880 * the running transaction. This allows nodatacow
881 * to avoid cow most of the time
882 */
883 if (found_owner >= BTRFS_FIRST_FREE_OBJECTID &&
884 btrfs_ref_generation(l, ref_item) ==
885 root->fs_info->generation) {
886 extent_refs--;
887 }
a68d5933 888 }
56b453c9 889 total_count = 1;
be20aa9d
CM		 890 path->slots[0]++;
891 }
bbaf549e
CM		 892 /*
893 * if there is more than one reference against a data extent,
894 * we have to assume the other ref is another snapshot
895 */
896 if (level == -1 && extent_refs > 1) {
897 total_count = 2;
898 goto out;
899 }
be20aa9d
CM		 900 if (cur_count == 0) {
901 total_count = 0;
902 goto out;
903 }
be20aa9d
CM		 904 if (level >= 0 && root->node == count_path->nodes[level])
905 goto out;
906 level++;
907 btrfs_release_path(root, path);
908 goto again;
909
910out:
911 btrfs_free_path(path);
925baedd 912 mutex_unlock(&root->fs_info->alloc_mutex);
be20aa9d 913 return total_count;
be20aa9d 914}
c5739bba 915
e089f05c 916int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
5f39d397 917 struct extent_buffer *buf)
02217ed2 918{
db94535d 919 u64 bytenr;
5f39d397
CM		 920 u32 nritems;
921 struct btrfs_key key;
6407bf6d 922 struct btrfs_file_extent_item *fi;
02217ed2 923 int i;
db94535d 924 int level;
6407bf6d 925 int ret;
54aa1f4d 926 int faili;
a28ec197 927
3768f368 928 if (!root->ref_cows)
a28ec197 929 return 0;
5f39d397 930
925baedd 931 mutex_lock(&root->fs_info->alloc_mutex);
db94535d 932 level = btrfs_header_level(buf);
5f39d397
CM		 933 nritems = btrfs_header_nritems(buf);
934 for (i = 0; i < nritems; i++) {
db94535d
CM		 935 if (level == 0) {
936 u64 disk_bytenr;
5f39d397
CM		 937 btrfs_item_key_to_cpu(buf, &key, i);
938 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
6407bf6d 939 continue;
5f39d397 940 fi = btrfs_item_ptr(buf, i,
6407bf6d 941 struct btrfs_file_extent_item);
5f39d397 942 if (btrfs_file_extent_type(buf, fi) ==
236454df
CM		 943 BTRFS_FILE_EXTENT_INLINE)
944 continue;
db94535d
CM		 945 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
946 if (disk_bytenr == 0)
3a686375 947 continue;
925baedd 948 ret = __btrfs_inc_extent_ref(trans, root, disk_bytenr,
7bb86316
CM		 949 btrfs_file_extent_disk_num_bytes(buf, fi),
950 root->root_key.objectid, trans->transid,
951 key.objectid, key.offset);
54aa1f4d
CM		 952 if (ret) {
953 faili = i;
954 goto fail;
955 }
6407bf6d 956 } else {
db94535d 957 bytenr = btrfs_node_blockptr(buf, i);
6caab489 958 btrfs_node_key_to_cpu(buf, &key, i);
925baedd 959 ret = __btrfs_inc_extent_ref(trans, root, bytenr,
7bb86316
CM		 960 btrfs_level_size(root, level - 1),
961 root->root_key.objectid,
f6dbff55
CM		 962 trans->transid,
963 level - 1, key.objectid);
54aa1f4d
CM		 964 if (ret) {
965 faili = i;
966 goto fail;
967 }
6407bf6d 968 }
02217ed2 969 }
925baedd 970 mutex_unlock(&root->fs_info->alloc_mutex);
02217ed2 971 return 0;
54aa1f4d 972fail:
ccd467d6 973 WARN_ON(1);
7bb86316 974#if 0
54aa1f4d 975 for (i =0; i < faili; i++) {
db94535d
CM		 976 if (level == 0) {
977 u64 disk_bytenr;
5f39d397
CM		 978 btrfs_item_key_to_cpu(buf, &key, i);
979 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
54aa1f4d 980 continue;
5f39d397 981 fi = btrfs_item_ptr(buf, i,
54aa1f4d 982 struct btrfs_file_extent_item);
5f39d397 983 if (btrfs_file_extent_type(buf, fi) ==
54aa1f4d
CM		 984 BTRFS_FILE_EXTENT_INLINE)
985 continue;
db94535d
CM		 986 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
987 if (disk_bytenr == 0)
54aa1f4d 988 continue;
db94535d
CM		 989 err = btrfs_free_extent(trans, root, disk_bytenr,
990 btrfs_file_extent_disk_num_bytes(buf,
5f39d397 991 fi), 0);
54aa1f4d
CM		 992 BUG_ON(err);
993 } else {
db94535d
CM		 994 bytenr = btrfs_node_blockptr(buf, i);
995 err = btrfs_free_extent(trans, root, bytenr,
996 btrfs_level_size(root, level - 1), 0);
54aa1f4d
CM		 997 BUG_ON(err);
998 }
999 }
7bb86316 1000#endif
925baedd 1001 mutex_unlock(&root->fs_info->alloc_mutex);
54aa1f4d 1002 return ret;
02217ed2
CM		 1003}
1004
9078a3e1
CM		 1005static int write_one_cache_group(struct btrfs_trans_handle *trans,
1006 struct btrfs_root *root,
1007 struct btrfs_path *path,
1008 struct btrfs_block_group_cache *cache)
1009{
1010 int ret;
1011 int pending_ret;
1012 struct btrfs_root *extent_root = root->fs_info->extent_root;
5f39d397
CM		 1013 unsigned long bi;
1014 struct extent_buffer *leaf;
9078a3e1 1015
9078a3e1 1016 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
54aa1f4d
CM		 1017 if (ret < 0)
1018 goto fail;
9078a3e1 1019 BUG_ON(ret);
5f39d397
CM		 1020
1021 leaf = path->nodes[0];
1022 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1023 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1024 btrfs_mark_buffer_dirty(leaf);
9078a3e1 1025 btrfs_release_path(extent_root, path);
54aa1f4d 1026fail:
9078a3e1
CM		 1027 finish_current_insert(trans, extent_root);
1028 pending_ret = del_pending_extents(trans, extent_root);
1029 if (ret)
1030 return ret;
1031 if (pending_ret)
1032 return pending_ret;
1033 return 0;
1034
1035}
1036
96b5179d
CM		 1037int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1038 struct btrfs_root *root)
9078a3e1 1039{
d1310b2e 1040 struct extent_io_tree *block_group_cache;
96b5179d 1041 struct btrfs_block_group_cache *cache;
9078a3e1
CM		 1042 int ret;
1043 int err = 0;
1044 int werr = 0;
9078a3e1 1045 struct btrfs_path *path;
96b5179d
CM		 1046 u64 last = 0;
1047 u64 start;
1048 u64 end;
1049 u64 ptr;
9078a3e1 1050
96b5179d 1051 block_group_cache = &root->fs_info->block_group_cache;
9078a3e1
CM		 1052 path = btrfs_alloc_path();
1053 if (!path)
1054 return -ENOMEM;
1055
925baedd 1056 mutex_lock(&root->fs_info->alloc_mutex);
9078a3e1 1057 while(1) {
96b5179d
CM		 1058 ret = find_first_extent_bit(block_group_cache, last,
1059 &start, &end, BLOCK_GROUP_DIRTY);
1060 if (ret)
9078a3e1 1061 break;
54aa1f4d 1062
96b5179d
CM		 1063 last = end + 1;
1064 ret = get_state_private(block_group_cache, start, &ptr);
1065 if (ret)
1066 break;
ae2f5411 1067 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
96b5179d
CM		 1068 err = write_one_cache_group(trans, root,
1069 path, cache);
1070 /*
1071 * if we fail to write the cache group, we want
1072 * to keep it marked dirty in hopes that a later
1073 * write will work
1074 */
1075 if (err) {
1076 werr = err;
1077 continue;
9078a3e1 1078 }
96b5179d
CM		 1079 clear_extent_bits(block_group_cache, start, end,
1080 BLOCK_GROUP_DIRTY, GFP_NOFS);
9078a3e1
CM		 1081 }
1082 btrfs_free_path(path);
925baedd 1083 mutex_unlock(&root->fs_info->alloc_mutex);
9078a3e1
CM		 1084 return werr;
1085}
1086
6324fbf3
CM		 1087static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
1088 u64 flags)
1089{
1090 struct list_head *head = &info->space_info;
1091 struct list_head *cur;
1092 struct btrfs_space_info *found;
1093 list_for_each(cur, head) {
1094 found = list_entry(cur, struct btrfs_space_info, list);
1095 if (found->flags == flags)
1096 return found;
1097 }
1098 return NULL;
1099
1100}
1101
593060d7
CM		 1102static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1103 u64 total_bytes, u64 bytes_used,
1104 struct btrfs_space_info **space_info)
1105{
1106 struct btrfs_space_info *found;
1107
1108 found = __find_space_info(info, flags);
1109 if (found) {
1110 found->total_bytes += total_bytes;
1111 found->bytes_used += bytes_used;
8f18cf13 1112 found->full = 0;
593060d7
CM		 1113 WARN_ON(found->total_bytes < found->bytes_used);
1114 *space_info = found;
1115 return 0;
1116 }
1117 found = kmalloc(sizeof(*found), GFP_NOFS);
1118 if (!found)
1119 return -ENOMEM;
1120
1121 list_add(&found->list, &info->space_info);
1122 found->flags = flags;
1123 found->total_bytes = total_bytes;
1124 found->bytes_used = bytes_used;
1125 found->bytes_pinned = 0;
1126 found->full = 0;
0ef3e66b 1127 found->force_alloc = 0;
593060d7
CM		 1128 *space_info = found;
1129 return 0;
1130}
1131
8790d502
CM		 1132static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1133{
1134 u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
611f0e00 1135 BTRFS_BLOCK_GROUP_RAID1 |
321aecc6 1136 BTRFS_BLOCK_GROUP_RAID10 |
611f0e00 1137 BTRFS_BLOCK_GROUP_DUP);
8790d502
CM		 1138 if (extra_flags) {
1139 if (flags & BTRFS_BLOCK_GROUP_DATA)
1140 fs_info->avail_data_alloc_bits |= extra_flags;
1141 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1142 fs_info->avail_metadata_alloc_bits |= extra_flags;
1143 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1144 fs_info->avail_system_alloc_bits |= extra_flags;
1145 }
1146}
593060d7 1147
a061fc8d 1148static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
ec44a35c 1149{
a061fc8d
CM		 1150 u64 num_devices = root->fs_info->fs_devices->num_devices;
1151
1152 if (num_devices == 1)
1153 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
1154 if (num_devices < 4)
1155 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
1156
ec44a35c
CM		 1157 if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
1158 (flags & (BTRFS_BLOCK_GROUP_RAID1 |
a061fc8d 1159 BTRFS_BLOCK_GROUP_RAID10))) {
ec44a35c 1160 flags &= ~BTRFS_BLOCK_GROUP_DUP;
a061fc8d 1161 }
ec44a35c
CM		 1162
1163 if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
a061fc8d 1164 (flags & BTRFS_BLOCK_GROUP_RAID10)) {
ec44a35c 1165 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
a061fc8d 1166 }
ec44a35c
CM		 1167
1168 if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
1169 ((flags & BTRFS_BLOCK_GROUP_RAID1) |
1170 (flags & BTRFS_BLOCK_GROUP_RAID10) |
1171 (flags & BTRFS_BLOCK_GROUP_DUP)))
1172 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
1173 return flags;
1174}
1175
6324fbf3
CM		 1176static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1177 struct btrfs_root *extent_root, u64 alloc_bytes,
0ef3e66b 1178 u64 flags, int force)
6324fbf3
CM		 1179{
1180 struct btrfs_space_info *space_info;
1181 u64 thresh;
1182 u64 start;
1183 u64 num_bytes;
1184 int ret;
1185
a061fc8d 1186 flags = reduce_alloc_profile(extent_root, flags);
ec44a35c 1187
6324fbf3 1188 space_info = __find_space_info(extent_root->fs_info, flags);
593060d7
CM		 1189 if (!space_info) {
1190 ret = update_space_info(extent_root->fs_info, flags,
1191 0, 0, &space_info);
1192 BUG_ON(ret);
1193 }
6324fbf3
CM		 1194 BUG_ON(!space_info);
1195
0ef3e66b
CM		 1196 if (space_info->force_alloc) {
1197 force = 1;
1198 space_info->force_alloc = 0;
1199 }
6324fbf3 1200 if (space_info->full)
925baedd 1201 goto out;
6324fbf3 1202
8790d502 1203 thresh = div_factor(space_info->total_bytes, 6);
0ef3e66b
CM		 1204 if (!force &&
1205 (space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
6324fbf3 1206 thresh)
925baedd 1207 goto out;
6324fbf3 1208
925baedd 1209 mutex_lock(&extent_root->fs_info->chunk_mutex);
6324fbf3
CM		 1210 ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1211 if (ret == -ENOSPC) {
1212printk("space info full %Lu\n", flags);
1213 space_info->full = 1;
925baedd 1214 goto out;
6324fbf3 1215 }
6324fbf3
CM		 1216 BUG_ON(ret);
1217
1218 ret = btrfs_make_block_group(trans, extent_root, 0, flags,
e17cade2 1219 BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
6324fbf3 1220 BUG_ON(ret);
925baedd
CM		 1221 mutex_unlock(&extent_root->fs_info->chunk_mutex);
1222out:
6324fbf3
CM		 1223 return 0;
1224}
1225
9078a3e1
CM		 1226static int update_block_group(struct btrfs_trans_handle *trans,
1227 struct btrfs_root *root,
db94535d 1228 u64 bytenr, u64 num_bytes, int alloc,
0b86a832 1229 int mark_free)
9078a3e1
CM		 1230{
1231 struct btrfs_block_group_cache *cache;
1232 struct btrfs_fs_info *info = root->fs_info;
db94535d 1233 u64 total = num_bytes;
9078a3e1 1234 u64 old_val;
db94535d 1235 u64 byte_in_group;
96b5179d
CM		 1236 u64 start;
1237 u64 end;
3e1ad54f 1238
9078a3e1 1239 while(total) {
db94535d 1240 cache = btrfs_lookup_block_group(info, bytenr);
3e1ad54f 1241 if (!cache) {
9078a3e1 1242 return -1;
cd1bc465 1243 }
db94535d
CM		 1244 byte_in_group = bytenr - cache->key.objectid;
1245 WARN_ON(byte_in_group > cache->key.offset);
96b5179d
CM		 1246 start = cache->key.objectid;
1247 end = start + cache->key.offset - 1;
1248 set_extent_bits(&info->block_group_cache, start, end,
1249 BLOCK_GROUP_DIRTY, GFP_NOFS);
9078a3e1
CM		 1250
1251 old_val = btrfs_block_group_used(&cache->item);
db94535d 1252 num_bytes = min(total, cache->key.offset - byte_in_group);
cd1bc465 1253 if (alloc) {
db94535d 1254 old_val += num_bytes;
6324fbf3 1255 cache->space_info->bytes_used += num_bytes;
cd1bc465 1256 } else {
db94535d 1257 old_val -= num_bytes;
6324fbf3 1258 cache->space_info->bytes_used -= num_bytes;
f510cfec
CM		 1259 if (mark_free) {
1260 set_extent_dirty(&info->free_space_cache,
db94535d 1261 bytenr, bytenr + num_bytes - 1,
f510cfec 1262 GFP_NOFS);
e37c9e69 1263 }
cd1bc465 1264 }
9078a3e1 1265 btrfs_set_block_group_used(&cache->item, old_val);
db94535d
CM		 1266 total -= num_bytes;
1267 bytenr += num_bytes;
9078a3e1
CM		 1268 }
1269 return 0;
1270}
6324fbf3 1271
a061fc8d
CM		 1272static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
1273{
1274 u64 start;
1275 u64 end;
1276 int ret;
1277 ret = find_first_extent_bit(&root->fs_info->block_group_cache,
1278 search_start, &start, &end,
1279 BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
1280 BLOCK_GROUP_SYSTEM);
1281 if (ret)
1282 return 0;
1283 return start;
1284}
1285
1286
324ae4df
Y		 1287static int update_pinned_extents(struct btrfs_root *root,
1288 u64 bytenr, u64 num, int pin)
1289{
1290 u64 len;
1291 struct btrfs_block_group_cache *cache;
1292 struct btrfs_fs_info *fs_info = root->fs_info;
1293
1294 if (pin) {
1295 set_extent_dirty(&fs_info->pinned_extents,
1296 bytenr, bytenr + num - 1, GFP_NOFS);
1297 } else {
1298 clear_extent_dirty(&fs_info->pinned_extents,
1299 bytenr, bytenr + num - 1, GFP_NOFS);
1300 }
1301 while (num > 0) {
1302 cache = btrfs_lookup_block_group(fs_info, bytenr);
a061fc8d
CM		 1303 if (!cache) {
1304 u64 first = first_logical_byte(root, bytenr);
1305 WARN_ON(first < bytenr);
1306 len = min(first - bytenr, num);
1307 } else {
1308 len = min(num, cache->key.offset -
1309 (bytenr - cache->key.objectid));
1310 }
324ae4df 1311 if (pin) {
a061fc8d
CM		 1312 if (cache) {
1313 cache->pinned += len;
1314 cache->space_info->bytes_pinned += len;
1315 }
324ae4df
Y		 1316 fs_info->total_pinned += len;
1317 } else {
a061fc8d
CM		 1318 if (cache) {
1319 cache->pinned -= len;
1320 cache->space_info->bytes_pinned -= len;
1321 }
324ae4df
Y		 1322 fs_info->total_pinned -= len;
1323 }
1324 bytenr += len;
1325 num -= len;
1326 }
1327 return 0;
1328}
9078a3e1 1329
d1310b2e 1330int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
ccd467d6 1331{
ccd467d6 1332 u64 last = 0;
1a5bc167
CM		 1333 u64 start;
1334 u64 end;
d1310b2e 1335 struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
ccd467d6 1336 int ret;
ccd467d6
CM		 1337
1338 while(1) {
1a5bc167
CM		 1339 ret = find_first_extent_bit(pinned_extents, last,
1340 &start, &end, EXTENT_DIRTY);
1341 if (ret)
ccd467d6 1342 break;
1a5bc167
CM		 1343 set_extent_dirty(copy, start, end, GFP_NOFS);
1344 last = end + 1;
ccd467d6
CM		 1345 }
1346 return 0;
1347}
1348
1349int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1350 struct btrfs_root *root,
d1310b2e 1351 struct extent_io_tree *unpin)
a28ec197 1352{
1a5bc167
CM		 1353 u64 start;
1354 u64 end;
a28ec197 1355 int ret;
d1310b2e 1356 struct extent_io_tree *free_space_cache;
f510cfec 1357 free_space_cache = &root->fs_info->free_space_cache;
a28ec197 1358
925baedd 1359 mutex_lock(&root->fs_info->alloc_mutex);
a28ec197 1360 while(1) {
1a5bc167
CM		 1361 ret = find_first_extent_bit(unpin, 0, &start, &end,
1362 EXTENT_DIRTY);
1363 if (ret)
a28ec197 1364 break;
324ae4df 1365 update_pinned_extents(root, start, end + 1 - start, 0);
1a5bc167
CM		 1366 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1367 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
a28ec197 1368 }
925baedd 1369 mutex_unlock(&root->fs_info->alloc_mutex);
a28ec197
CM		 1370 return 0;
1371}
1372
98ed5174
CM		 1373static int finish_current_insert(struct btrfs_trans_handle *trans,
1374 struct btrfs_root *extent_root)
037e6390 1375{
7bb86316
CM		 1376 u64 start;
1377 u64 end;
1378 struct btrfs_fs_info *info = extent_root->fs_info;
d8d5f3e1 1379 struct extent_buffer *eb;
7bb86316 1380 struct btrfs_path *path;
e2fa7227 1381 struct btrfs_key ins;
d8d5f3e1 1382 struct btrfs_disk_key first;
234b63a0 1383 struct btrfs_extent_item extent_item;
037e6390 1384 int ret;
d8d5f3e1 1385 int level;
1a5bc167 1386 int err = 0;
037e6390 1387
5f39d397 1388 btrfs_set_stack_extent_refs(&extent_item, 1);
62e2749e 1389 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
7bb86316 1390 path = btrfs_alloc_path();
037e6390 1391
26b8003f 1392 while(1) {
1a5bc167
CM		 1393 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1394 &end, EXTENT_LOCKED);
1395 if (ret)
26b8003f
CM		 1396 break;
1397
1a5bc167
CM		 1398 ins.objectid = start;
1399 ins.offset = end + 1 - start;
1400 err = btrfs_insert_item(trans, extent_root, &ins,
1401 &extent_item, sizeof(extent_item));
1402 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1403 GFP_NOFS);
ca7a79ad
CM		 1404 eb = read_tree_block(extent_root, ins.objectid, ins.offset,
1405 trans->transid);
925baedd 1406 btrfs_tree_lock(eb);
d8d5f3e1
CM		 1407 level = btrfs_header_level(eb);
1408 if (level == 0) {
1409 btrfs_item_key(eb, &first, 0);
1410 } else {
1411 btrfs_node_key(eb, &first, 0);
1412 }
925baedd
CM		 1413 btrfs_tree_unlock(eb);
1414 free_extent_buffer(eb);
1415 /*
1416 * the first key is just a hint, so the race we've created
1417 * against reading it is fine
1418 */
7bb86316
CM		 1419 err = btrfs_insert_extent_backref(trans, extent_root, path,
1420 start, extent_root->root_key.objectid,
f6dbff55
CM		 1421 0, level,
1422 btrfs_disk_key_objectid(&first));
7bb86316 1423 BUG_ON(err);
037e6390 1424 }
7bb86316 1425 btrfs_free_path(path);
037e6390
CM		 1426 return 0;
1427}
1428
db94535d
CM		 1429static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1430 int pending)
e20d96d6 1431{
1a5bc167 1432 int err = 0;
8ef97622 1433
f4b9aa8d 1434 if (!pending) {
925baedd
CM		 1435#if 0
1436 struct extent_buffer *buf;
db94535d 1437 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
5f39d397 1438 if (buf) {
925baedd
CM		 1439 if (!btrfs_try_tree_lock(buf) &&
1440 btrfs_buffer_uptodate(buf, 0)) {
2c90e5d6
CM		 1441 u64 transid =
1442 root->fs_info->running_transaction->transid;
dc17ff8f
CM		 1443 u64 header_transid =
1444 btrfs_header_generation(buf);
6bc34676
CM		 1445 if (header_transid == transid &&
1446 !btrfs_header_flag(buf,
1447 BTRFS_HEADER_FLAG_WRITTEN)) {
55c69072 1448 clean_tree_block(NULL, root, buf);
925baedd 1449 btrfs_tree_unlock(buf);
5f39d397 1450 free_extent_buffer(buf);
c549228f 1451 return 1;
2c90e5d6 1452 }
925baedd 1453 btrfs_tree_unlock(buf);
f4b9aa8d 1454 }
5f39d397 1455 free_extent_buffer(buf);
8ef97622 1456 }
925baedd 1457#endif
324ae4df 1458 update_pinned_extents(root, bytenr, num_bytes, 1);
f4b9aa8d 1459 } else {
1a5bc167 1460 set_extent_bits(&root->fs_info->pending_del,
db94535d
CM		 1461 bytenr, bytenr + num_bytes - 1,
1462 EXTENT_LOCKED, GFP_NOFS);
f4b9aa8d 1463 }
be744175 1464 BUG_ON(err < 0);
e20d96d6
CM		 1465 return 0;
1466}
1467
fec577fb 1468/*
a28ec197 1469 * remove an extent from the root, returns 0 on success
fec577fb 1470 */
e089f05c 1471static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
7bb86316
CM		 1472 *root, u64 bytenr, u64 num_bytes,
1473 u64 root_objectid, u64 ref_generation,
1474 u64 owner_objectid, u64 owner_offset, int pin,
e37c9e69 1475 int mark_free)
a28ec197 1476{
5caf2a00 1477 struct btrfs_path *path;
e2fa7227 1478 struct btrfs_key key;
1261ec42
CM		 1479 struct btrfs_fs_info *info = root->fs_info;
1480 struct btrfs_root *extent_root = info->extent_root;
5f39d397 1481 struct extent_buffer *leaf;
a28ec197 1482 int ret;
952fccac
CM		 1483 int extent_slot = 0;
1484 int found_extent = 0;
1485 int num_to_del = 1;
234b63a0 1486 struct btrfs_extent_item *ei;
cf27e1ee 1487 u32 refs;
037e6390 1488
db94535d 1489 key.objectid = bytenr;
62e2749e 1490 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
db94535d 1491 key.offset = num_bytes;
5caf2a00 1492 path = btrfs_alloc_path();
54aa1f4d
CM		 1493 if (!path)
1494 return -ENOMEM;
5f26f772 1495
3c12ac72 1496 path->reada = 1;
7bb86316
CM		 1497 ret = lookup_extent_backref(trans, extent_root, path,
1498 bytenr, root_objectid,
1499 ref_generation,
1500 owner_objectid, owner_offset, 1);
1501 if (ret == 0) {
952fccac
CM		 1502 struct btrfs_key found_key;
1503 extent_slot = path->slots[0];
1504 while(extent_slot > 0) {
1505 extent_slot--;
1506 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1507 extent_slot);
1508 if (found_key.objectid != bytenr)
1509 break;
1510 if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1511 found_key.offset == num_bytes) {
1512 found_extent = 1;
1513 break;
1514 }
1515 if (path->slots[0] - extent_slot > 5)
1516 break;
1517 }
1518 if (!found_extent)
1519 ret = btrfs_del_item(trans, extent_root, path);
7bb86316
CM		 1520 } else {
1521 btrfs_print_leaf(extent_root, path->nodes[0]);
1522 WARN_ON(1);
1523 printk("Unable to find ref byte nr %Lu root %Lu "
1524 " gen %Lu owner %Lu offset %Lu\n", bytenr,
1525 root_objectid, ref_generation, owner_objectid,
1526 owner_offset);
1527 }
952fccac
CM		 1528 if (!found_extent) {
1529 btrfs_release_path(extent_root, path);
1530 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1531 if (ret < 0)
1532 return ret;
1533 BUG_ON(ret);
1534 extent_slot = path->slots[0];
1535 }
5f39d397
CM		 1536
1537 leaf = path->nodes[0];
952fccac 1538 ei = btrfs_item_ptr(leaf, extent_slot,
123abc88 1539 struct btrfs_extent_item);
5f39d397
CM		 1540 refs = btrfs_extent_refs(leaf, ei);
1541 BUG_ON(refs == 0);
1542 refs -= 1;
1543 btrfs_set_extent_refs(leaf, ei, refs);
952fccac 1544
5f39d397
CM		 1545 btrfs_mark_buffer_dirty(leaf);
1546
952fccac
CM		 1547 if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1548 /* if the back ref and the extent are next to each other
1549 * they get deleted below in one shot
1550 */
1551 path->slots[0] = extent_slot;
1552 num_to_del = 2;
1553 } else if (found_extent) {
1554 /* otherwise delete the extent back ref */
1555 ret = btrfs_del_item(trans, extent_root, path);
1556 BUG_ON(ret);
1557 /* if refs are 0, we need to setup the path for deletion */
1558 if (refs == 0) {
1559 btrfs_release_path(extent_root, path);
1560 ret = btrfs_search_slot(trans, extent_root, &key, path,
1561 -1, 1);
1562 if (ret < 0)
1563 return ret;
1564 BUG_ON(ret);
1565 }
1566 }
1567
cf27e1ee 1568 if (refs == 0) {
db94535d
CM		 1569 u64 super_used;
1570 u64 root_used;
78fae27e
CM		 1571
1572 if (pin) {
db94535d 1573 ret = pin_down_bytes(root, bytenr, num_bytes, 0);
c549228f
Y		 1574 if (ret > 0)
1575 mark_free = 1;
1576 BUG_ON(ret < 0);
78fae27e
CM		 1577 }
1578
58176a96 1579 /* block accounting for super block */
db94535d
CM		 1580 super_used = btrfs_super_bytes_used(&info->super_copy);
1581 btrfs_set_super_bytes_used(&info->super_copy,
1582 super_used - num_bytes);
58176a96
JB		 1583
1584 /* block accounting for root item */
db94535d 1585 root_used = btrfs_root_used(&root->root_item);
5f39d397 1586 btrfs_set_root_used(&root->root_item,
db94535d 1587 root_used - num_bytes);
952fccac
CM		 1588 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
1589 num_to_del);
54aa1f4d
CM		 1590 if (ret) {
1591 return ret;
1592 }
db94535d 1593 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
0b86a832 1594 mark_free);
9078a3e1 1595 BUG_ON(ret);
a28ec197 1596 }
5caf2a00 1597 btrfs_free_path(path);
e089f05c 1598 finish_current_insert(trans, extent_root);
a28ec197
CM		 1599 return ret;
1600}
1601
a28ec197
CM		 1602/*
1603 * find all the blocks marked as pending in the radix tree and remove
1604 * them from the extent map
1605 */
e089f05c
CM		 1606static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1607 btrfs_root *extent_root)
a28ec197
CM		 1608{
1609 int ret;
e20d96d6 1610 int err = 0;
1a5bc167
CM		 1611 u64 start;
1612 u64 end;
d1310b2e
CM		 1613 struct extent_io_tree *pending_del;
1614 struct extent_io_tree *pinned_extents;
8ef97622 1615
1a5bc167
CM		 1616 pending_del = &extent_root->fs_info->pending_del;
1617 pinned_extents = &extent_root->fs_info->pinned_extents;
a28ec197
CM		 1618
1619 while(1) {
1a5bc167
CM		 1620 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1621 EXTENT_LOCKED);
1622 if (ret)
a28ec197 1623 break;
324ae4df 1624 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1a5bc167
CM		 1625 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1626 GFP_NOFS);
1627 ret = __free_extent(trans, extent_root,
7bb86316
CM		 1628 start, end + 1 - start,
1629 extent_root->root_key.objectid,
1630 0, 0, 0, 0, 0);
1a5bc167
CM		 1631 if (ret)
1632 err = ret;
fec577fb 1633 }
e20d96d6 1634 return err;
fec577fb
CM		 1635}
1636
1637/*
1638 * remove an extent from the root, returns 0 on success
1639 */
925baedd
CM		 1640static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
1641 struct btrfs_root *root, u64 bytenr,
1642 u64 num_bytes, u64 root_objectid,
1643 u64 ref_generation, u64 owner_objectid,
1644 u64 owner_offset, int pin)
fec577fb 1645{
9f5fae2f 1646 struct btrfs_root *extent_root = root->fs_info->extent_root;
fec577fb
CM		 1647 int pending_ret;
1648 int ret;
a28ec197 1649
db94535d 1650 WARN_ON(num_bytes < root->sectorsize);
7bb86316
CM		 1651 if (!root->ref_cows)
1652 ref_generation = 0;
1653
fec577fb 1654 if (root == extent_root) {
db94535d 1655 pin_down_bytes(root, bytenr, num_bytes, 1);
fec577fb
CM		 1656 return 0;
1657 }
7bb86316
CM		 1658 ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1659 ref_generation, owner_objectid, owner_offset,
1660 pin, pin == 0);
e20d96d6 1661 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
fec577fb
CM		 1662 return ret ? ret : pending_ret;
1663}
1664
925baedd
CM		 1665int btrfs_free_extent(struct btrfs_trans_handle *trans,
1666 struct btrfs_root *root, u64 bytenr,
1667 u64 num_bytes, u64 root_objectid,
1668 u64 ref_generation, u64 owner_objectid,
1669 u64 owner_offset, int pin)
1670{
1671 int ret;
1672
1673 maybe_lock_mutex(root);
1674 ret = __btrfs_free_extent(trans, root, bytenr, num_bytes,
1675 root_objectid, ref_generation,
1676 owner_objectid, owner_offset, pin);
1677 maybe_unlock_mutex(root);
1678 return ret;
1679}
1680
87ee04eb
CM		 1681static u64 stripe_align(struct btrfs_root *root, u64 val)
1682{
1683 u64 mask = ((u64)root->stripesize - 1);
1684 u64 ret = (val + mask) & ~mask;
1685 return ret;
1686}
1687
fec577fb
CM		 1688/*
1689 * walks the btree of allocated extents and find a hole of a given size.
1690 * The key ins is changed to record the hole:
1691 * ins->objectid == block start
62e2749e 1692 * ins->flags = BTRFS_EXTENT_ITEM_KEY
fec577fb
CM		 1693 * ins->offset == number of blocks
1694 * Any available blocks before search_start are skipped.
1695 */
98ed5174
CM		 1696static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1697 struct btrfs_root *orig_root,
1698 u64 num_bytes, u64 empty_size,
1699 u64 search_start, u64 search_end,
1700 u64 hint_byte, struct btrfs_key *ins,
1701 u64 exclude_start, u64 exclude_nr,
1702 int data)
fec577fb 1703{
87ee04eb 1704 int ret;
a061fc8d 1705 u64 orig_search_start;
9f5fae2f 1706 struct btrfs_root * root = orig_root->fs_info->extent_root;
f2458e1d 1707 struct btrfs_fs_info *info = root->fs_info;
db94535d 1708 u64 total_needed = num_bytes;
239b14b3 1709 u64 *last_ptr = NULL;
be08c1b9 1710 struct btrfs_block_group_cache *block_group;
be744175 1711 int full_scan = 0;
fbdc762b 1712 int wrapped = 0;
0ef3e66b 1713 int chunk_alloc_done = 0;
239b14b3 1714 int empty_cluster = 2 * 1024 * 1024;
0ef3e66b 1715 int allowed_chunk_alloc = 0;
fec577fb 1716
db94535d 1717 WARN_ON(num_bytes < root->sectorsize);
b1a4d965
CM		 1718 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1719
0ef3e66b
CM		 1720 if (orig_root->ref_cows || empty_size)
1721 allowed_chunk_alloc = 1;
1722
239b14b3
CM		 1723 if (data & BTRFS_BLOCK_GROUP_METADATA) {
1724 last_ptr = &root->fs_info->last_alloc;
8790d502 1725 empty_cluster = 256 * 1024;
239b14b3
CM		 1726 }
1727
1728 if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
1729 last_ptr = &root->fs_info->last_data_alloc;
1730 }
1731
1732 if (last_ptr) {
1733 if (*last_ptr)
1734 hint_byte = *last_ptr;
1735 else {
1736 empty_size += empty_cluster;
1737 }
1738 }
1739
a061fc8d
CM		 1740 search_start = max(search_start, first_logical_byte(root, 0));
1741 orig_search_start = search_start;
1742
7f93bf8d
CM		 1743 if (search_end == (u64)-1)
1744 search_end = btrfs_super_total_bytes(&info->super_copy);
0b86a832 1745
db94535d 1746 if (hint_byte) {
0ef3e66b 1747 block_group = btrfs_lookup_first_block_group(info, hint_byte);
1a2b2ac7
CM		 1748 if (!block_group)
1749 hint_byte = search_start;
925baedd 1750 block_group = __btrfs_find_block_group(root, block_group,
db94535d 1751 hint_byte, data, 1);
239b14b3
CM		 1752 if (last_ptr && *last_ptr == 0 && block_group)
1753 hint_byte = block_group->key.objectid;
be744175 1754 } else {
925baedd 1755 block_group = __btrfs_find_block_group(root,
1a2b2ac7
CM		 1756 trans->block_group,
1757 search_start, data, 1);
be744175 1758 }
239b14b3 1759 search_start = max(search_start, hint_byte);
be744175 1760
6702ed49 1761 total_needed += empty_size;
0b86a832 1762
be744175 1763check_failed:
70b043f0 1764 if (!block_group) {
0ef3e66b
CM		 1765 block_group = btrfs_lookup_first_block_group(info,
1766 search_start);
70b043f0 1767 if (!block_group)
0ef3e66b 1768 block_group = btrfs_lookup_first_block_group(info,
70b043f0
CM		 1769 orig_search_start);
1770 }
0ef3e66b
CM		 1771 if (full_scan && !chunk_alloc_done) {
1772 if (allowed_chunk_alloc) {
1773 do_chunk_alloc(trans, root,
1774 num_bytes + 2 * 1024 * 1024, data, 1);
1775 allowed_chunk_alloc = 0;
1776 } else if (block_group && block_group_bits(block_group, data)) {
1777 block_group->space_info->force_alloc = 1;
1778 }
1779 chunk_alloc_done = 1;
1780 }
0b86a832
CM		 1781 ret = find_search_start(root, &block_group, &search_start,
1782 total_needed, data);
239b14b3
CM		 1783 if (ret == -ENOSPC && last_ptr && *last_ptr) {
1784 *last_ptr = 0;
0ef3e66b
CM		 1785 block_group = btrfs_lookup_first_block_group(info,
1786 orig_search_start);
239b14b3
CM		 1787 search_start = orig_search_start;
1788 ret = find_search_start(root, &block_group, &search_start,
1789 total_needed, data);
1790 }
1791 if (ret == -ENOSPC)
1792 goto enospc;
0b86a832 1793 if (ret)
d548ee51 1794 goto error;
e19caa5f 1795
239b14b3
CM		 1796 if (last_ptr && *last_ptr && search_start != *last_ptr) {
1797 *last_ptr = 0;
1798 if (!empty_size) {
1799 empty_size += empty_cluster;
1800 total_needed += empty_size;
1801 }
0ef3e66b 1802 block_group = btrfs_lookup_first_block_group(info,
239b14b3
CM		 1803 orig_search_start);
1804 search_start = orig_search_start;
1805 ret = find_search_start(root, &block_group,
1806 &search_start, total_needed, data);
1807 if (ret == -ENOSPC)
1808 goto enospc;
1809 if (ret)
1810 goto error;
1811 }
1812
0b86a832
CM		 1813 search_start = stripe_align(root, search_start);
1814 ins->objectid = search_start;
1815 ins->offset = num_bytes;
e37c9e69 1816
db94535d 1817 if (ins->objectid + num_bytes >= search_end)
cf67582b 1818 goto enospc;
0b86a832
CM		 1819
1820 if (ins->objectid + num_bytes >
1821 block_group->key.objectid + block_group->key.offset) {
e19caa5f
CM		 1822 search_start = block_group->key.objectid +
1823 block_group->key.offset;
1824 goto new_group;
1825 }
0b86a832 1826
1a5bc167 1827 if (test_range_bit(&info->extent_ins, ins->objectid,
db94535d
CM		 1828 ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1829 search_start = ins->objectid + num_bytes;
1a5bc167
CM		 1830 goto new_group;
1831 }
0b86a832 1832
1a5bc167 1833 if (test_range_bit(&info->pinned_extents, ins->objectid,
db94535d
CM		 1834 ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1835 search_start = ins->objectid + num_bytes;
1a5bc167 1836 goto new_group;
fec577fb 1837 }
0b86a832 1838
db94535d 1839 if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
f2654de4
CM		 1840 ins->objectid < exclude_start + exclude_nr)) {
1841 search_start = exclude_start + exclude_nr;
1842 goto new_group;
1843 }
0b86a832 1844
6324fbf3 1845 if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
5276aeda 1846 block_group = btrfs_lookup_block_group(info, ins->objectid);
26b8003f
CM		 1847 if (block_group)
1848 trans->block_group = block_group;
f2458e1d 1849 }
db94535d 1850 ins->offset = num_bytes;
239b14b3
CM		 1851 if (last_ptr) {
1852 *last_ptr = ins->objectid + ins->offset;
1853 if (*last_ptr ==
1854 btrfs_super_total_bytes(&root->fs_info->super_copy)) {
1855 *last_ptr = 0;
1856 }
1857 }
fec577fb 1858 return 0;
be744175
CM		 1859
1860new_group:
db94535d 1861 if (search_start + num_bytes >= search_end) {
cf67582b 1862enospc:
be744175 1863 search_start = orig_search_start;
fbdc762b
CM		 1864 if (full_scan) {
1865 ret = -ENOSPC;
1866 goto error;
1867 }
6702ed49
CM		 1868 if (wrapped) {
1869 if (!full_scan)
1870 total_needed -= empty_size;
fbdc762b 1871 full_scan = 1;
6702ed49 1872 } else
fbdc762b 1873 wrapped = 1;
be744175 1874 }
0ef3e66b 1875 block_group = btrfs_lookup_first_block_group(info, search_start);
fbdc762b 1876 cond_resched();
925baedd 1877 block_group = __btrfs_find_block_group(root, block_group,
1a2b2ac7 1878 search_start, data, 0);
be744175
CM		 1879 goto check_failed;
1880
0f70abe2 1881error:
0f70abe2 1882 return ret;
fec577fb 1883}
ec44a35c 1884
fec577fb
CM		 1885/*
1886 * finds a free extent and does all the dirty work required for allocation
1887 * returns the key for the extent through ins, and a tree buffer for
1888 * the first block of the extent through buf.
1889 *
1890 * returns 0 if everything worked, non-zero otherwise.
1891 */
4d775673 1892int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
7bb86316 1893 struct btrfs_root *root,
98d20f67
CM		 1894 u64 num_bytes, u64 min_alloc_size,
1895 u64 root_objectid, u64 ref_generation,
7bb86316
CM		 1896 u64 owner, u64 owner_offset,
1897 u64 empty_size, u64 hint_byte,
ec44a35c 1898 u64 search_end, struct btrfs_key *ins, u64 data)
fec577fb
CM		 1899{
1900 int ret;
1901 int pending_ret;
c31f8830
CM		 1902 u64 super_used;
1903 u64 root_used;
fbdc762b 1904 u64 search_start = 0;
8790d502 1905 u64 alloc_profile;
47e4bb98 1906 u32 sizes[2];
1261ec42
CM		 1907 struct btrfs_fs_info *info = root->fs_info;
1908 struct btrfs_root *extent_root = info->extent_root;
47e4bb98
CM		 1909 struct btrfs_extent_item *extent_item;
1910 struct btrfs_extent_ref *ref;
7bb86316 1911 struct btrfs_path *path;
47e4bb98 1912 struct btrfs_key keys[2];
8f662a76 1913
925baedd
CM		 1914 maybe_lock_mutex(root);
1915
6324fbf3 1916 if (data) {
8790d502
CM		 1917 alloc_profile = info->avail_data_alloc_bits &
1918 info->data_alloc_profile;
1919 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
6324fbf3 1920 } else if (root == root->fs_info->chunk_root) {
8790d502
CM		 1921 alloc_profile = info->avail_system_alloc_bits &
1922 info->system_alloc_profile;
1923 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
6324fbf3 1924 } else {
8790d502
CM		 1925 alloc_profile = info->avail_metadata_alloc_bits &
1926 info->metadata_alloc_profile;
1927 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
6324fbf3 1928 }
98d20f67 1929again:
a061fc8d 1930 data = reduce_alloc_profile(root, data);
0ef3e66b
CM		 1931 /*
1932 * the only place that sets empty_size is btrfs_realloc_node, which
1933 * is not called recursively on allocations
1934 */
1935 if (empty_size || root->ref_cows) {
593060d7 1936 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
6324fbf3 1937 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
0ef3e66b
CM		 1938 2 * 1024 * 1024,
1939 BTRFS_BLOCK_GROUP_METADATA |
1940 (info->metadata_alloc_profile &
1941 info->avail_metadata_alloc_bits), 0);
6324fbf3
CM		 1942 BUG_ON(ret);
1943 }
1944 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
0ef3e66b 1945 num_bytes + 2 * 1024 * 1024, data, 0);
6324fbf3
CM		 1946 BUG_ON(ret);
1947 }
0b86a832 1948
db94535d
CM		 1949 WARN_ON(num_bytes < root->sectorsize);
1950 ret = find_free_extent(trans, root, num_bytes, empty_size,
1951 search_start, search_end, hint_byte, ins,
26b8003f
CM		 1952 trans->alloc_exclude_start,
1953 trans->alloc_exclude_nr, data);
3b951516 1954
98d20f67
CM		 1955 if (ret == -ENOSPC && num_bytes > min_alloc_size) {
1956 num_bytes = num_bytes >> 1;
1957 num_bytes = max(num_bytes, min_alloc_size);
0ef3e66b
CM		 1958 do_chunk_alloc(trans, root->fs_info->extent_root,
1959 num_bytes, data, 1);
98d20f67
CM		 1960 goto again;
1961 }
ec44a35c
CM		 1962 if (ret) {
1963 printk("allocation failed flags %Lu\n", data);
1964 }
925baedd
CM		 1965 if (ret) {
1966 BUG();
1967 goto out;
1968 }
fec577fb 1969
58176a96 1970 /* block accounting for super block */
db94535d
CM		 1971 super_used = btrfs_super_bytes_used(&info->super_copy);
1972 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
26b8003f 1973
58176a96 1974 /* block accounting for root item */
db94535d
CM		 1975 root_used = btrfs_root_used(&root->root_item);
1976 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
58176a96 1977
f510cfec
CM		 1978 clear_extent_dirty(&root->fs_info->free_space_cache,
1979 ins->objectid, ins->objectid + ins->offset - 1,
1980 GFP_NOFS);
1981
26b8003f 1982 if (root == extent_root) {
1a5bc167
CM		 1983 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1984 ins->objectid + ins->offset - 1,
1985 EXTENT_LOCKED, GFP_NOFS);
26b8003f
CM		 1986 goto update_block;
1987 }
1988
1989 WARN_ON(trans->alloc_exclude_nr);
1990 trans->alloc_exclude_start = ins->objectid;
1991 trans->alloc_exclude_nr = ins->offset;
037e6390 1992
47e4bb98
CM		 1993 memcpy(&keys[0], ins, sizeof(*ins));
1994 keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
1995 owner, owner_offset);
1996 keys[1].objectid = ins->objectid;
1997 keys[1].type = BTRFS_EXTENT_REF_KEY;
1998 sizes[0] = sizeof(*extent_item);
1999 sizes[1] = sizeof(*ref);
7bb86316
CM		 2000
2001 path = btrfs_alloc_path();
2002 BUG_ON(!path);
47e4bb98
CM		 2003
2004 ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
2005 sizes, 2);
26b8003f 2006
ccd467d6 2007 BUG_ON(ret);
47e4bb98
CM		 2008 extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2009 struct btrfs_extent_item);
2010 btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
2011 ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
2012 struct btrfs_extent_ref);
2013
2014 btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
2015 btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
2016 btrfs_set_ref_objectid(path->nodes[0], ref, owner);
2017 btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
2018
2019 btrfs_mark_buffer_dirty(path->nodes[0]);
2020
2021 trans->alloc_exclude_start = 0;
2022 trans->alloc_exclude_nr = 0;
7bb86316 2023 btrfs_free_path(path);
e089f05c 2024 finish_current_insert(trans, extent_root);
e20d96d6 2025 pending_ret = del_pending_extents(trans, extent_root);
f510cfec 2026
925baedd
CM		 2027 if (ret)
2028 goto out;
e37c9e69 2029 if (pending_ret) {
925baedd
CM		 2030 ret = pending_ret;
2031 goto out;
e37c9e69 2032 }
26b8003f
CM		 2033
2034update_block:
0b86a832 2035 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
f5947066
CM		 2036 if (ret) {
2037 printk("update block group failed for %Lu %Lu\n",
2038 ins->objectid, ins->offset);
2039 BUG();
2040 }
925baedd
CM		 2041out:
2042 maybe_unlock_mutex(root);
2043 return ret;
fec577fb 2044}
fec577fb
CM		 2045/*
2046 * helper function to allocate a block for a given tree
2047 * returns the tree buffer or NULL.
2048 */
5f39d397 2049struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
7bb86316
CM		 2050 struct btrfs_root *root,
2051 u32 blocksize,
2052 u64 root_objectid,
2053 u64 ref_generation,
2054 u64 first_objectid,
2055 int level,
2056 u64 hint,
5f39d397 2057 u64 empty_size)
fec577fb 2058{
e2fa7227 2059 struct btrfs_key ins;
fec577fb 2060 int ret;
5f39d397 2061 struct extent_buffer *buf;
fec577fb 2062
98d20f67 2063 ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
7bb86316 2064 root_objectid, ref_generation,
f6dbff55 2065 level, first_objectid, empty_size, hint,
db94535d 2066 (u64)-1, &ins, 0);
fec577fb 2067 if (ret) {
54aa1f4d
CM		 2068 BUG_ON(ret > 0);
2069 return ERR_PTR(ret);
fec577fb 2070 }
db94535d 2071 buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
54aa1f4d 2072 if (!buf) {
7bb86316
CM		 2073 btrfs_free_extent(trans, root, ins.objectid, blocksize,
2074 root->root_key.objectid, ref_generation,
2075 0, 0, 0);
54aa1f4d
CM		 2076 return ERR_PTR(-ENOMEM);
2077 }
55c69072 2078 btrfs_set_header_generation(buf, trans->transid);
925baedd 2079 btrfs_tree_lock(buf);
55c69072 2080 clean_tree_block(trans, root, buf);
5f39d397 2081 btrfs_set_buffer_uptodate(buf);
55c69072
CM		 2082
2083 if (PageDirty(buf->first_page)) {
2084 printk("page %lu dirty\n", buf->first_page->index);
2085 WARN_ON(1);
2086 }
2087
5f39d397
CM		 2088 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
2089 buf->start + buf->len - 1, GFP_NOFS);
9afbb0b7
CM		 2090 if (!btrfs_test_opt(root, SSD))
2091 btrfs_set_buffer_defrag(buf);
d3c2fdcf 2092 trans->blocks_used++;
fec577fb
CM		 2093 return buf;
2094}
a28ec197 2095
98ed5174
CM		 2096static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
2097 struct btrfs_root *root,
2098 struct extent_buffer *leaf)
6407bf6d 2099{
7bb86316
CM		 2100 u64 leaf_owner;
2101 u64 leaf_generation;
5f39d397 2102 struct btrfs_key key;
6407bf6d
CM		 2103 struct btrfs_file_extent_item *fi;
2104 int i;
2105 int nritems;
2106 int ret;
2107
5f39d397
CM		 2108 BUG_ON(!btrfs_is_leaf(leaf));
2109 nritems = btrfs_header_nritems(leaf);
7bb86316
CM		 2110 leaf_owner = btrfs_header_owner(leaf);
2111 leaf_generation = btrfs_header_generation(leaf);
2112
6407bf6d 2113 for (i = 0; i < nritems; i++) {
db94535d 2114 u64 disk_bytenr;
5f39d397
CM		 2115
2116 btrfs_item_key_to_cpu(leaf, &key, i);
2117 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
6407bf6d
CM		 2118 continue;
2119 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
5f39d397
CM		 2120 if (btrfs_file_extent_type(leaf, fi) ==
2121 BTRFS_FILE_EXTENT_INLINE)
236454df 2122 continue;
6407bf6d
CM		 2123 /*
2124 * FIXME make sure to insert a trans record that
2125 * repeats the snapshot del on crash
2126 */
db94535d
CM		 2127 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2128 if (disk_bytenr == 0)
3a686375 2129 continue;
925baedd 2130 ret = __btrfs_free_extent(trans, root, disk_bytenr,
7bb86316
CM		 2131 btrfs_file_extent_disk_num_bytes(leaf, fi),
2132 leaf_owner, leaf_generation,
2133 key.objectid, key.offset, 0);
6407bf6d
CM		 2134 BUG_ON(ret);
2135 }
2136 return 0;
2137}
2138
98ed5174 2139static void noinline reada_walk_down(struct btrfs_root *root,
bea495e5
CM		 2140 struct extent_buffer *node,
2141 int slot)
e011599b 2142{
db94535d 2143 u64 bytenr;
bea495e5
CM		 2144 u64 last = 0;
2145 u32 nritems;
e011599b 2146 u32 refs;
db94535d 2147 u32 blocksize;
bea495e5
CM		 2148 int ret;
2149 int i;
2150 int level;
2151 int skipped = 0;
e011599b 2152
5f39d397 2153 nritems = btrfs_header_nritems(node);
db94535d 2154 level = btrfs_header_level(node);
bea495e5
CM		 2155 if (level)
2156 return;
2157
2158 for (i = slot; i < nritems && skipped < 32; i++) {
db94535d 2159 bytenr = btrfs_node_blockptr(node, i);
bea495e5
CM		 2160 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
2161 (last > bytenr && last - bytenr > 32 * 1024))) {
2162 skipped++;
e011599b 2163 continue;
bea495e5
CM		 2164 }
2165 blocksize = btrfs_level_size(root, level - 1);
2166 if (i != slot) {
2167 ret = lookup_extent_ref(NULL, root, bytenr,
2168 blocksize, &refs);
2169 BUG_ON(ret);
2170 if (refs != 1) {
2171 skipped++;
2172 continue;
2173 }
2174 }
409eb95d 2175 mutex_unlock(&root->fs_info->fs_mutex);
ca7a79ad
CM		 2176 ret = readahead_tree_block(root, bytenr, blocksize,
2177 btrfs_node_ptr_generation(node, i));
bea495e5 2178 last = bytenr + blocksize;
409eb95d
CM		 2179 cond_resched();
2180 mutex_lock(&root->fs_info->fs_mutex);
e011599b
CM		 2181 if (ret)
2182 break;
2183 }
2184}
2185
9aca1d51
CM		 2186/*
2187 * helper function for drop_snapshot, this walks down the tree dropping ref
2188 * counts as it goes.
2189 */
98ed5174
CM		 2190static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2191 struct btrfs_root *root,
2192 struct btrfs_path *path, int *level)
20524f02 2193{
7bb86316
CM		 2194 u64 root_owner;
2195 u64 root_gen;
2196 u64 bytenr;
ca7a79ad 2197 u64 ptr_gen;
5f39d397
CM		 2198 struct extent_buffer *next;
2199 struct extent_buffer *cur;
7bb86316 2200 struct extent_buffer *parent;
db94535d 2201 u32 blocksize;
20524f02
CM		 2202 int ret;
2203 u32 refs;
2204
925baedd
CM		 2205 mutex_lock(&root->fs_info->alloc_mutex);
2206
5caf2a00
CM		 2207 WARN_ON(*level < 0);
2208 WARN_ON(*level >= BTRFS_MAX_LEVEL);
5f39d397 2209 ret = lookup_extent_ref(trans, root,
db94535d
CM		 2210 path->nodes[*level]->start,
2211 path->nodes[*level]->len, &refs);
20524f02
CM		 2212 BUG_ON(ret);
2213 if (refs > 1)
2214 goto out;
e011599b 2215
9aca1d51
CM		 2216 /*
2217 * walk down to the last node level and free all the leaves
2218 */
6407bf6d 2219 while(*level >= 0) {
5caf2a00
CM		 2220 WARN_ON(*level < 0);
2221 WARN_ON(*level >= BTRFS_MAX_LEVEL);
20524f02 2222 cur = path->nodes[*level];
e011599b 2223
5f39d397 2224 if (btrfs_header_level(cur) != *level)
2c90e5d6 2225 WARN_ON(1);
e011599b 2226
7518a238 2227 if (path->slots[*level] >=
5f39d397 2228 btrfs_header_nritems(cur))
20524f02 2229 break;
6407bf6d
CM		 2230 if (*level == 0) {
2231 ret = drop_leaf_ref(trans, root, cur);
2232 BUG_ON(ret);
2233 break;
2234 }
db94535d 2235 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
ca7a79ad 2236 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
db94535d 2237 blocksize = btrfs_level_size(root, *level - 1);
925baedd 2238
db94535d 2239 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
6407bf6d
CM		 2240 BUG_ON(ret);
2241 if (refs != 1) {
7bb86316
CM		 2242 parent = path->nodes[*level];
2243 root_owner = btrfs_header_owner(parent);
2244 root_gen = btrfs_header_generation(parent);
20524f02 2245 path->slots[*level]++;
925baedd 2246 ret = __btrfs_free_extent(trans, root, bytenr,
7bb86316
CM		 2247 blocksize, root_owner,
2248 root_gen, 0, 0, 1);
20524f02
CM		 2249 BUG_ON(ret);
2250 continue;
2251 }
db94535d 2252 next = btrfs_find_tree_block(root, bytenr, blocksize);
1259ab75 2253 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
5f39d397 2254 free_extent_buffer(next);
bea495e5 2255 reada_walk_down(root, cur, path->slots[*level]);
8790d502
CM		 2256
2257 mutex_unlock(&root->fs_info->fs_mutex);
925baedd 2258 mutex_unlock(&root->fs_info->alloc_mutex);
ca7a79ad
CM		 2259 next = read_tree_block(root, bytenr, blocksize,
2260 ptr_gen);
8790d502 2261 mutex_lock(&root->fs_info->fs_mutex);
925baedd 2262 mutex_lock(&root->fs_info->alloc_mutex);
e9d0b13b 2263
8790d502 2264 /* we've dropped the lock, double check */
db94535d
CM		 2265 ret = lookup_extent_ref(trans, root, bytenr,
2266 blocksize, &refs);
e9d0b13b
CM		 2267 BUG_ON(ret);
2268 if (refs != 1) {
7bb86316
CM		 2269 parent = path->nodes[*level];
2270 root_owner = btrfs_header_owner(parent);
2271 root_gen = btrfs_header_generation(parent);
2272
e9d0b13b 2273 path->slots[*level]++;
5f39d397 2274 free_extent_buffer(next);
925baedd 2275 ret = __btrfs_free_extent(trans, root, bytenr,
7bb86316
CM		 2276 blocksize,
2277 root_owner,
2278 root_gen, 0, 0, 1);
e9d0b13b
CM		 2279 BUG_ON(ret);
2280 continue;
2281 }
2282 }
5caf2a00 2283 WARN_ON(*level <= 0);
83e15a28 2284 if (path->nodes[*level-1])
5f39d397 2285 free_extent_buffer(path->nodes[*level-1]);
20524f02 2286 path->nodes[*level-1] = next;
5f39d397 2287 *level = btrfs_header_level(next);
20524f02
CM		 2288 path->slots[*level] = 0;
2289 }
2290out:
5caf2a00
CM		 2291 WARN_ON(*level < 0);
2292 WARN_ON(*level >= BTRFS_MAX_LEVEL);
7bb86316
CM		 2293
2294 if (path->nodes[*level] == root->node) {
2295 root_owner = root->root_key.objectid;
2296 parent = path->nodes[*level];
2297 } else {
2298 parent = path->nodes[*level + 1];
2299 root_owner = btrfs_header_owner(parent);
2300 }
2301
2302 root_gen = btrfs_header_generation(parent);
925baedd 2303 ret = __btrfs_free_extent(trans, root, path->nodes[*level]->start,
7bb86316
CM		 2304 path->nodes[*level]->len,
2305 root_owner, root_gen, 0, 0, 1);
5f39d397 2306 free_extent_buffer(path->nodes[*level]);
20524f02
CM		 2307 path->nodes[*level] = NULL;
2308 *level += 1;
2309 BUG_ON(ret);
925baedd 2310 mutex_unlock(&root->fs_info->alloc_mutex);
20524f02
CM		 2311 return 0;
2312}
2313
9aca1d51
CM		 2314/*
2315 * helper for dropping snapshots. This walks back up the tree in the path
2316 * to find the first node higher up where we haven't yet gone through
2317 * all the slots
2318 */
98ed5174
CM		 2319static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2320 struct btrfs_root *root,
2321 struct btrfs_path *path, int *level)
20524f02 2322{
7bb86316
CM		 2323 u64 root_owner;
2324 u64 root_gen;
2325 struct btrfs_root_item *root_item = &root->root_item;
20524f02
CM		 2326 int i;
2327 int slot;
2328 int ret;
9f3a7427 2329
234b63a0 2330 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
20524f02 2331 slot = path->slots[i];
5f39d397
CM		 2332 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2333 struct extent_buffer *node;
2334 struct btrfs_disk_key disk_key;
2335 node = path->nodes[i];
20524f02
CM		 2336 path->slots[i]++;
2337 *level = i;
9f3a7427 2338 WARN_ON(*level == 0);
5f39d397 2339 btrfs_node_key(node, &disk_key, path->slots[i]);
9f3a7427 2340 memcpy(&root_item->drop_progress,
5f39d397 2341 &disk_key, sizeof(disk_key));
9f3a7427 2342 root_item->drop_level = i;
20524f02
CM		 2343 return 0;
2344 } else {
7bb86316
CM		 2345 if (path->nodes[*level] == root->node) {
2346 root_owner = root->root_key.objectid;
2347 root_gen =
2348 btrfs_header_generation(path->nodes[*level]);
2349 } else {
2350 struct extent_buffer *node;
2351 node = path->nodes[*level + 1];
2352 root_owner = btrfs_header_owner(node);
2353 root_gen = btrfs_header_generation(node);
2354 }
e089f05c 2355 ret = btrfs_free_extent(trans, root,
db94535d 2356 path->nodes[*level]->start,
7bb86316
CM		 2357 path->nodes[*level]->len,
2358 root_owner, root_gen, 0, 0, 1);
6407bf6d 2359 BUG_ON(ret);
5f39d397 2360 free_extent_buffer(path->nodes[*level]);
83e15a28 2361 path->nodes[*level] = NULL;
20524f02 2362 *level = i + 1;
20524f02
CM		 2363 }
2364 }
2365 return 1;
2366}
2367
9aca1d51
CM		 2368/*
2369 * drop the reference count on the tree rooted at 'snap'. This traverses
2370 * the tree freeing any blocks that have a ref count of zero after being
2371 * decremented.
2372 */
e089f05c 2373int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
9f3a7427 2374 *root)
20524f02 2375{
3768f368 2376 int ret = 0;
9aca1d51 2377 int wret;
20524f02 2378 int level;
5caf2a00 2379 struct btrfs_path *path;
20524f02
CM		 2380 int i;
2381 int orig_level;
9f3a7427 2382 struct btrfs_root_item *root_item = &root->root_item;
20524f02 2383
5caf2a00
CM		 2384 path = btrfs_alloc_path();
2385 BUG_ON(!path);
20524f02 2386
5f39d397 2387 level = btrfs_header_level(root->node);
20524f02 2388 orig_level = level;
9f3a7427
CM		 2389 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2390 path->nodes[level] = root->node;
f510cfec 2391 extent_buffer_get(root->node);
9f3a7427
CM		 2392 path->slots[level] = 0;
2393 } else {
2394 struct btrfs_key key;
5f39d397
CM		 2395 struct btrfs_disk_key found_key;
2396 struct extent_buffer *node;
6702ed49 2397
9f3a7427 2398 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
6702ed49
CM		 2399 level = root_item->drop_level;
2400 path->lowest_level = level;
9f3a7427 2401 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6702ed49 2402 if (wret < 0) {
9f3a7427
CM		 2403 ret = wret;
2404 goto out;
2405 }
5f39d397
CM		 2406 node = path->nodes[level];
2407 btrfs_node_key(node, &found_key, path->slots[level]);
2408 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2409 sizeof(found_key)));
925baedd
CM		 2410 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
2411 if (path->nodes[i] && path->locks[i]) {
2412 path->locks[i] = 0;
2413 btrfs_tree_unlock(path->nodes[i]);
2414 }
2415 }
9f3a7427 2416 }
20524f02 2417 while(1) {
5caf2a00 2418 wret = walk_down_tree(trans, root, path, &level);
9aca1d51 2419 if (wret > 0)
20524f02 2420 break;
9aca1d51
CM		 2421 if (wret < 0)
2422 ret = wret;
2423
5caf2a00 2424 wret = walk_up_tree(trans, root, path, &level);
9aca1d51 2425 if (wret > 0)
20524f02 2426 break;
9aca1d51
CM		 2427 if (wret < 0)
2428 ret = wret;
409eb95d 2429 ret = -EAGAIN;
409eb95d 2430 break;
20524f02 2431 }
83e15a28 2432 for (i = 0; i <= orig_level; i++) {
5caf2a00 2433 if (path->nodes[i]) {
5f39d397 2434 free_extent_buffer(path->nodes[i]);
0f82731f 2435 path->nodes[i] = NULL;
83e15a28 2436 }
20524f02 2437 }
9f3a7427 2438out:
5caf2a00 2439 btrfs_free_path(path);
9aca1d51 2440 return ret;
20524f02 2441}
9078a3e1 2442
96b5179d 2443int btrfs_free_block_groups(struct btrfs_fs_info *info)
9078a3e1 2444{
96b5179d
CM		 2445 u64 start;
2446 u64 end;
b97f9203 2447 u64 ptr;
9078a3e1 2448 int ret;
925baedd
CM		 2449
2450 mutex_lock(&info->alloc_mutex);
9078a3e1 2451 while(1) {
96b5179d
CM		 2452 ret = find_first_extent_bit(&info->block_group_cache, 0,
2453 &start, &end, (unsigned int)-1);
2454 if (ret)
9078a3e1 2455 break;
b97f9203
Y		 2456 ret = get_state_private(&info->block_group_cache, start, &ptr);
2457 if (!ret)
2458 kfree((void *)(unsigned long)ptr);
96b5179d
CM		 2459 clear_extent_bits(&info->block_group_cache, start,
2460 end, (unsigned int)-1, GFP_NOFS);
9078a3e1 2461 }
e37c9e69 2462 while(1) {
f510cfec
CM		 2463 ret = find_first_extent_bit(&info->free_space_cache, 0,
2464 &start, &end, EXTENT_DIRTY);
2465 if (ret)
e37c9e69 2466 break;
f510cfec
CM		 2467 clear_extent_dirty(&info->free_space_cache, start,
2468 end, GFP_NOFS);
e37c9e69 2469 }
925baedd 2470 mutex_unlock(&info->alloc_mutex);
be744175
CM		 2471 return 0;
2472}
2473
8e7bf94f
CM		 2474static unsigned long calc_ra(unsigned long start, unsigned long last,
2475 unsigned long nr)
2476{
2477 return min(last, start + nr - 1);
2478}
2479
98ed5174
CM		 2480static int noinline relocate_inode_pages(struct inode *inode, u64 start,
2481 u64 len)
edbd8d4e
CM		 2482{
2483 u64 page_start;
2484 u64 page_end;
edbd8d4e 2485 unsigned long last_index;
edbd8d4e
CM		 2486 unsigned long i;
2487 struct page *page;
d1310b2e 2488 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
4313b399 2489 struct file_ra_state *ra;
8e7bf94f
CM		 2490 unsigned long total_read = 0;
2491 unsigned long ra_pages;
a061fc8d 2492 struct btrfs_trans_handle *trans;
4313b399
CM		 2493
2494 ra = kzalloc(sizeof(*ra), GFP_NOFS);
edbd8d4e
CM		 2495
2496 mutex_lock(&inode->i_mutex);
4313b399 2497 i = start >> PAGE_CACHE_SHIFT;
edbd8d4e
CM		 2498 last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
2499
8e7bf94f
CM		 2500 ra_pages = BTRFS_I(inode)->root->fs_info->bdi.ra_pages;
2501
4313b399 2502 file_ra_state_init(ra, inode->i_mapping);
edbd8d4e 2503
4313b399 2504 for (; i <= last_index; i++) {
8e7bf94f
CM		 2505 if (total_read % ra_pages == 0) {
2506 btrfs_force_ra(inode->i_mapping, ra, NULL, i,
2507 calc_ra(i, last_index, ra_pages));
2508 }
2509 total_read++;
a061fc8d
CM		 2510 if (((u64)i << PAGE_CACHE_SHIFT) > inode->i_size)
2511 goto truncate_racing;
2512
edbd8d4e 2513 page = grab_cache_page(inode->i_mapping, i);
a061fc8d 2514 if (!page) {
edbd8d4e 2515 goto out_unlock;
a061fc8d 2516 }
edbd8d4e
CM		 2517 if (!PageUptodate(page)) {
2518 btrfs_readpage(NULL, page);
2519 lock_page(page);
2520 if (!PageUptodate(page)) {
2521 unlock_page(page);
2522 page_cache_release(page);
2523 goto out_unlock;
2524 }
2525 }
ec44a35c
CM		 2526#if LINUX_VERSION_CODE <= KERNEL_VERSION(2,6,18)
2527 ClearPageDirty(page);
2528#else
2529 cancel_dirty_page(page, PAGE_CACHE_SIZE);
2530#endif
2531 wait_on_page_writeback(page);
2532 set_page_extent_mapped(page);
edbd8d4e
CM		 2533 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
2534 page_end = page_start + PAGE_CACHE_SIZE - 1;
2535
d1310b2e 2536 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
edbd8d4e 2537
d1310b2e 2538 set_extent_delalloc(io_tree, page_start,
edbd8d4e 2539 page_end, GFP_NOFS);
a061fc8d 2540 set_page_dirty(page);
edbd8d4e 2541
d1310b2e 2542 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
edbd8d4e
CM		 2543 unlock_page(page);
2544 page_cache_release(page);
2545 }
a061fc8d
CM		 2546 balance_dirty_pages_ratelimited_nr(inode->i_mapping,
2547 total_read);
edbd8d4e
CM		 2548
2549out_unlock:
ec44a35c 2550 kfree(ra);
a061fc8d
CM		 2551 trans = btrfs_start_transaction(BTRFS_I(inode)->root, 1);
2552 if (trans) {
2553 btrfs_add_ordered_inode(inode);
2554 btrfs_end_transaction(trans, BTRFS_I(inode)->root);
2555 mark_inode_dirty(inode);
2556 }
edbd8d4e
CM		 2557 mutex_unlock(&inode->i_mutex);
2558 return 0;
a061fc8d
CM		 2559
2560truncate_racing:
2561 vmtruncate(inode, inode->i_size);
2562 balance_dirty_pages_ratelimited_nr(inode->i_mapping,
2563 total_read);
2564 goto out_unlock;
edbd8d4e
CM		 2565}
2566
bf4ef679
CM		 2567/*
2568 * The back references tell us which tree holds a ref on a block,
2569 * but it is possible for the tree root field in the reference to
2570 * reflect the original root before a snapshot was made. In this
2571 * case we should search through all the children of a given root
2572 * to find potential holders of references on a block.
2573 *
2574 * Instead, we do something a little less fancy and just search
2575 * all the roots for a given key/block combination.
2576 */
2577static int find_root_for_ref(struct btrfs_root *root,
2578 struct btrfs_path *path,
2579 struct btrfs_key *key0,
2580 int level,
2581 int file_key,
2582 struct btrfs_root **found_root,
2583 u64 bytenr)
2584{
2585 struct btrfs_key root_location;
2586 struct btrfs_root *cur_root = *found_root;
2587 struct btrfs_file_extent_item *file_extent;
2588 u64 root_search_start = BTRFS_FS_TREE_OBJECTID;
2589 u64 found_bytenr;
2590 int ret;
2591 int i;
2592
2593 root_location.offset = (u64)-1;
2594 root_location.type = BTRFS_ROOT_ITEM_KEY;
2595 path->lowest_level = level;
2596 path->reada = 0;
2597 while(1) {
2598 ret = btrfs_search_slot(NULL, cur_root, key0, path, 0, 0);
2599 found_bytenr = 0;
2600 if (ret == 0 && file_key) {
2601 struct extent_buffer *leaf = path->nodes[0];
2602 file_extent = btrfs_item_ptr(leaf, path->slots[0],
2603 struct btrfs_file_extent_item);
2604 if (btrfs_file_extent_type(leaf, file_extent) ==
2605 BTRFS_FILE_EXTENT_REG) {
2606 found_bytenr =
2607 btrfs_file_extent_disk_bytenr(leaf,
2608 file_extent);
2609 }
323da79c 2610 } else if (!file_key) {
bf4ef679
CM		 2611 if (path->nodes[level])
2612 found_bytenr = path->nodes[level]->start;
2613 }
2614
2615 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2616 if (!path->nodes[i])
2617 break;
2618 free_extent_buffer(path->nodes[i]);
2619 path->nodes[i] = NULL;
2620 }
2621 btrfs_release_path(cur_root, path);
2622
2623 if (found_bytenr == bytenr) {
2624 *found_root = cur_root;
2625 ret = 0;
2626 goto out;
2627 }
2628 ret = btrfs_search_root(root->fs_info->tree_root,
2629 root_search_start, &root_search_start);
2630 if (ret)
2631 break;
2632
2633 root_location.objectid = root_search_start;
2634 cur_root = btrfs_read_fs_root_no_name(root->fs_info,
2635 &root_location);
2636 if (!cur_root) {
2637 ret = 1;
2638 break;
2639 }
2640 }
2641out:
2642 path->lowest_level = 0;
2643 return ret;
2644}
2645
4313b399
CM		 2646/*
2647 * note, this releases the path
2648 */
98ed5174 2649static int noinline relocate_one_reference(struct btrfs_root *extent_root,
edbd8d4e 2650 struct btrfs_path *path,
0ef3e66b
CM		 2651 struct btrfs_key *extent_key,
2652 u64 *last_file_objectid,
2653 u64 *last_file_offset,
2654 u64 *last_file_root,
2655 u64 last_extent)
edbd8d4e
CM		 2656{
2657 struct inode *inode;
2658 struct btrfs_root *found_root;
bf4ef679
CM		 2659 struct btrfs_key root_location;
2660 struct btrfs_key found_key;
4313b399
CM		 2661 struct btrfs_extent_ref *ref;
2662 u64 ref_root;
2663 u64 ref_gen;
2664 u64 ref_objectid;
2665 u64 ref_offset;
edbd8d4e 2666 int ret;
bf4ef679 2667 int level;
edbd8d4e 2668
4313b399
CM		 2669 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
2670 struct btrfs_extent_ref);
2671 ref_root = btrfs_ref_root(path->nodes[0], ref);
2672 ref_gen = btrfs_ref_generation(path->nodes[0], ref);
2673 ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
2674 ref_offset = btrfs_ref_offset(path->nodes[0], ref);
2675 btrfs_release_path(extent_root, path);
2676
bf4ef679 2677 root_location.objectid = ref_root;
edbd8d4e 2678 if (ref_gen == 0)
bf4ef679 2679 root_location.offset = 0;
edbd8d4e 2680 else
bf4ef679
CM		 2681 root_location.offset = (u64)-1;
2682 root_location.type = BTRFS_ROOT_ITEM_KEY;
edbd8d4e
CM		 2683
2684 found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
bf4ef679 2685 &root_location);
edbd8d4e
CM		 2686 BUG_ON(!found_root);
2687
2688 if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
bf4ef679
CM		 2689 found_key.objectid = ref_objectid;
2690 found_key.type = BTRFS_EXTENT_DATA_KEY;
2691 found_key.offset = ref_offset;
2692 level = 0;
2693
0ef3e66b
CM		 2694 if (last_extent == extent_key->objectid &&
2695 *last_file_objectid == ref_objectid &&
2696 *last_file_offset == ref_offset &&
2697 *last_file_root == ref_root)
2698 goto out;
2699
bf4ef679
CM		 2700 ret = find_root_for_ref(extent_root, path, &found_key,
2701 level, 1, &found_root,
2702 extent_key->objectid);
2703
2704 if (ret)
2705 goto out;
2706
0ef3e66b
CM		 2707 if (last_extent == extent_key->objectid &&
2708 *last_file_objectid == ref_objectid &&
2709 *last_file_offset == ref_offset &&
2710 *last_file_root == ref_root)
2711 goto out;
2712
edbd8d4e
CM		 2713 mutex_unlock(&extent_root->fs_info->fs_mutex);
2714 inode = btrfs_iget_locked(extent_root->fs_info->sb,
2715 ref_objectid, found_root);
2716 if (inode->i_state & I_NEW) {
2717 /* the inode and parent dir are two different roots */
2718 BTRFS_I(inode)->root = found_root;
2719 BTRFS_I(inode)->location.objectid = ref_objectid;
2720 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
2721 BTRFS_I(inode)->location.offset = 0;
2722 btrfs_read_locked_inode(inode);
2723 unlock_new_inode(inode);
2724
2725 }
2726 /* this can happen if the reference is not against
2727 * the latest version of the tree root
2728 */
2729 if (is_bad_inode(inode)) {
2730 mutex_lock(&extent_root->fs_info->fs_mutex);
2731 goto out;
2732 }
0ef3e66b
CM		 2733 *last_file_objectid = inode->i_ino;
2734 *last_file_root = found_root->root_key.objectid;
2735 *last_file_offset = ref_offset;
2736
edbd8d4e 2737 relocate_inode_pages(inode, ref_offset, extent_key->offset);
edbd8d4e
CM		 2738 iput(inode);
2739 mutex_lock(&extent_root->fs_info->fs_mutex);
2740 } else {
2741 struct btrfs_trans_handle *trans;
edbd8d4e 2742 struct extent_buffer *eb;
edbd8d4e
CM		 2743 int i;
2744
edbd8d4e 2745 eb = read_tree_block(found_root, extent_key->objectid,
ca7a79ad 2746 extent_key->offset, 0);
925baedd 2747 btrfs_tree_lock(eb);
edbd8d4e
CM		 2748 level = btrfs_header_level(eb);
2749
2750 if (level == 0)
2751 btrfs_item_key_to_cpu(eb, &found_key, 0);
2752 else
2753 btrfs_node_key_to_cpu(eb, &found_key, 0);
2754
925baedd 2755 btrfs_tree_unlock(eb);
edbd8d4e
CM		 2756 free_extent_buffer(eb);
2757
bf4ef679
CM		 2758 ret = find_root_for_ref(extent_root, path, &found_key,
2759 level, 0, &found_root,
2760 extent_key->objectid);
2761
2762 if (ret)
2763 goto out;
2764
2765 trans = btrfs_start_transaction(found_root, 1);
2766
edbd8d4e 2767 path->lowest_level = level;
8f662a76 2768 path->reada = 2;
edbd8d4e
CM		 2769 ret = btrfs_search_slot(trans, found_root, &found_key, path,
2770 0, 1);
2771 path->lowest_level = 0;
2772 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2773 if (!path->nodes[i])
2774 break;
2775 free_extent_buffer(path->nodes[i]);
2776 path->nodes[i] = NULL;
2777 }
2778 btrfs_release_path(found_root, path);
0ef3e66b
CM		 2779 if (found_root == found_root->fs_info->extent_root)
2780 btrfs_extent_post_op(trans, found_root);
edbd8d4e
CM		 2781 btrfs_end_transaction(trans, found_root);
2782 }
2783
2784out:
2785 return 0;
2786}
2787
a061fc8d
CM		 2788static int noinline del_extent_zero(struct btrfs_root *extent_root,
2789 struct btrfs_path *path,
2790 struct btrfs_key *extent_key)
2791{
2792 int ret;
2793 struct btrfs_trans_handle *trans;
2794
2795 trans = btrfs_start_transaction(extent_root, 1);
2796 ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
2797 if (ret > 0) {
2798 ret = -EIO;
2799 goto out;
2800 }
2801 if (ret < 0)
2802 goto out;
2803 ret = btrfs_del_item(trans, extent_root, path);
2804out:
2805 btrfs_end_transaction(trans, extent_root);
2806 return ret;
2807}
2808
98ed5174
CM		 2809static int noinline relocate_one_extent(struct btrfs_root *extent_root,
2810 struct btrfs_path *path,
2811 struct btrfs_key *extent_key)
edbd8d4e
CM		 2812{
2813 struct btrfs_key key;
2814 struct btrfs_key found_key;
edbd8d4e 2815 struct extent_buffer *leaf;
0ef3e66b
CM		 2816 u64 last_file_objectid = 0;
2817 u64 last_file_root = 0;
2818 u64 last_file_offset = (u64)-1;
2819 u64 last_extent = 0;
edbd8d4e
CM		 2820 u32 nritems;
2821 u32 item_size;
2822 int ret = 0;
2823
a061fc8d
CM		 2824 if (extent_key->objectid == 0) {
2825 ret = del_extent_zero(extent_root, path, extent_key);
2826 goto out;
2827 }
edbd8d4e
CM		 2828 key.objectid = extent_key->objectid;
2829 key.type = BTRFS_EXTENT_REF_KEY;
2830 key.offset = 0;
2831
2832 while(1) {
2833 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2834
edbd8d4e
CM		 2835 if (ret < 0)
2836 goto out;
2837
2838 ret = 0;
2839 leaf = path->nodes[0];
2840 nritems = btrfs_header_nritems(leaf);
a061fc8d
CM		 2841 if (path->slots[0] == nritems) {
2842 ret = btrfs_next_leaf(extent_root, path);
2843 if (ret > 0) {
2844 ret = 0;
2845 goto out;
2846 }
2847 if (ret < 0)
2848 goto out;
bf4ef679 2849 leaf = path->nodes[0];
a061fc8d 2850 }
edbd8d4e
CM		 2851
2852 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
a061fc8d 2853 if (found_key.objectid != extent_key->objectid) {
edbd8d4e 2854 break;
a061fc8d 2855 }
edbd8d4e 2856
a061fc8d 2857 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
edbd8d4e 2858 break;
a061fc8d 2859 }
edbd8d4e
CM		 2860
2861 key.offset = found_key.offset + 1;
2862 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2863
0ef3e66b
CM		 2864 ret = relocate_one_reference(extent_root, path, extent_key,
2865 &last_file_objectid,
2866 &last_file_offset,
2867 &last_file_root, last_extent);
edbd8d4e
CM		 2868 if (ret)
2869 goto out;
0ef3e66b 2870 last_extent = extent_key->objectid;
edbd8d4e
CM		 2871 }
2872 ret = 0;
2873out:
2874 btrfs_release_path(extent_root, path);
2875 return ret;
2876}
2877
ec44a35c
CM		 2878static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
2879{
2880 u64 num_devices;
2881 u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
2882 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
2883
a061fc8d 2884 num_devices = root->fs_info->fs_devices->num_devices;
ec44a35c
CM		 2885 if (num_devices == 1) {
2886 stripped |= BTRFS_BLOCK_GROUP_DUP;
2887 stripped = flags & ~stripped;
2888
2889 /* turn raid0 into single device chunks */
2890 if (flags & BTRFS_BLOCK_GROUP_RAID0)
2891 return stripped;
2892
2893 /* turn mirroring into duplication */
2894 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
2895 BTRFS_BLOCK_GROUP_RAID10))
2896 return stripped | BTRFS_BLOCK_GROUP_DUP;
2897 return flags;
2898 } else {
2899 /* they already had raid on here, just return */
ec44a35c
CM		 2900 if (flags & stripped)
2901 return flags;
2902
2903 stripped |= BTRFS_BLOCK_GROUP_DUP;
2904 stripped = flags & ~stripped;
2905
2906 /* switch duplicated blocks with raid1 */
2907 if (flags & BTRFS_BLOCK_GROUP_DUP)
2908 return stripped | BTRFS_BLOCK_GROUP_RAID1;
2909
2910 /* turn single device chunks into raid0 */
2911 return stripped | BTRFS_BLOCK_GROUP_RAID0;
2912 }
2913 return flags;
2914}
2915
0ef3e66b
CM		 2916int __alloc_chunk_for_shrink(struct btrfs_root *root,
2917 struct btrfs_block_group_cache *shrink_block_group,
2918 int force)
2919{
2920 struct btrfs_trans_handle *trans;
2921 u64 new_alloc_flags;
2922 u64 calc;
2923
2924 if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
2925
2926 trans = btrfs_start_transaction(root, 1);
2927 new_alloc_flags = update_block_group_flags(root,
2928 shrink_block_group->flags);
2929 if (new_alloc_flags != shrink_block_group->flags) {
2930 calc =
2931 btrfs_block_group_used(&shrink_block_group->item);
2932 } else {
2933 calc = shrink_block_group->key.offset;
2934 }
2935 do_chunk_alloc(trans, root->fs_info->extent_root,
2936 calc + 2 * 1024 * 1024, new_alloc_flags, force);
2937 btrfs_end_transaction(trans, root);
2938 }
2939 return 0;
2940}
2941
8f18cf13 2942int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 shrink_start)
edbd8d4e
CM		 2943{
2944 struct btrfs_trans_handle *trans;
2945 struct btrfs_root *tree_root = root->fs_info->tree_root;
2946 struct btrfs_path *path;
2947 u64 cur_byte;
2948 u64 total_found;
8f18cf13
CM		 2949 u64 shrink_last_byte;
2950 struct btrfs_block_group_cache *shrink_block_group;
edbd8d4e 2951 struct btrfs_fs_info *info = root->fs_info;
edbd8d4e 2952 struct btrfs_key key;
73e48b27 2953 struct btrfs_key found_key;
edbd8d4e
CM		 2954 struct extent_buffer *leaf;
2955 u32 nritems;
2956 int ret;
a061fc8d 2957 int progress;
edbd8d4e 2958
925baedd 2959 mutex_lock(&root->fs_info->alloc_mutex);
8f18cf13
CM		 2960 shrink_block_group = btrfs_lookup_block_group(root->fs_info,
2961 shrink_start);
2962 BUG_ON(!shrink_block_group);
2963
0ef3e66b
CM		 2964 shrink_last_byte = shrink_block_group->key.objectid +
2965 shrink_block_group->key.offset;
8f18cf13
CM		 2966
2967 shrink_block_group->space_info->total_bytes -=
2968 shrink_block_group->key.offset;
edbd8d4e
CM		 2969 path = btrfs_alloc_path();
2970 root = root->fs_info->extent_root;
8f662a76 2971 path->reada = 2;
edbd8d4e 2972
323da79c
CM		 2973 printk("btrfs relocating block group %llu flags %llu\n",
2974 (unsigned long long)shrink_start,
2975 (unsigned long long)shrink_block_group->flags);
2976
0ef3e66b
CM		 2977 __alloc_chunk_for_shrink(root, shrink_block_group, 1);
2978
edbd8d4e 2979again:
323da79c 2980
8f18cf13
CM		 2981 shrink_block_group->ro = 1;
2982
edbd8d4e 2983 total_found = 0;
a061fc8d 2984 progress = 0;
8f18cf13 2985 key.objectid = shrink_start;
edbd8d4e
CM		 2986 key.offset = 0;
2987 key.type = 0;
73e48b27 2988 cur_byte = key.objectid;
4313b399 2989
73e48b27
Y		 2990 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2991 if (ret < 0)
2992 goto out;
2993
0b86a832 2994 ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
73e48b27
Y		 2995 if (ret < 0)
2996 goto out;
8f18cf13 2997
73e48b27
Y		 2998 if (ret == 0) {
2999 leaf = path->nodes[0];
3000 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
8f18cf13
CM		 3001 if (found_key.objectid + found_key.offset > shrink_start &&
3002 found_key.objectid < shrink_last_byte) {
73e48b27
Y		 3003 cur_byte = found_key.objectid;
3004 key.objectid = cur_byte;
3005 }
3006 }
3007 btrfs_release_path(root, path);
3008
3009 while(1) {
edbd8d4e
CM		 3010 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3011 if (ret < 0)
3012 goto out;
73e48b27 3013
edbd8d4e 3014 leaf = path->nodes[0];
73e48b27
Y		 3015 nritems = btrfs_header_nritems(leaf);
3016next:
3017 if (path->slots[0] >= nritems) {
3018 ret = btrfs_next_leaf(root, path);
3019 if (ret < 0)
3020 goto out;
3021 if (ret == 1) {
3022 ret = 0;
3023 break;
edbd8d4e 3024 }
73e48b27
Y		 3025 leaf = path->nodes[0];
3026 nritems = btrfs_header_nritems(leaf);
edbd8d4e 3027 }
73e48b27
Y		 3028
3029 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
725c8463 3030
8f18cf13
CM		 3031 if (found_key.objectid >= shrink_last_byte)
3032 break;
3033
725c8463
CM		 3034 if (progress && need_resched()) {
3035 memcpy(&key, &found_key, sizeof(key));
3036 mutex_unlock(&root->fs_info->fs_mutex);
3037 cond_resched();
3038 mutex_lock(&root->fs_info->fs_mutex);
3039 btrfs_release_path(root, path);
3040 btrfs_search_slot(NULL, root, &key, path, 0, 0);
3041 progress = 0;
3042 goto next;
3043 }
3044 progress = 1;
3045
73e48b27
Y		 3046 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
3047 found_key.objectid + found_key.offset <= cur_byte) {
0ef3e66b
CM		 3048 memcpy(&key, &found_key, sizeof(key));
3049 key.offset++;
edbd8d4e 3050 path->slots[0]++;
edbd8d4e
CM		 3051 goto next;
3052 }
73e48b27 3053
edbd8d4e
CM		 3054 total_found++;
3055 cur_byte = found_key.objectid + found_key.offset;
3056 key.objectid = cur_byte;
3057 btrfs_release_path(root, path);
3058 ret = relocate_one_extent(root, path, &found_key);
0ef3e66b 3059 __alloc_chunk_for_shrink(root, shrink_block_group, 0);
edbd8d4e
CM		 3060 }
3061
3062 btrfs_release_path(root, path);
3063
3064 if (total_found > 0) {
323da79c
CM		 3065 printk("btrfs relocate found %llu last extent was %llu\n",
3066 (unsigned long long)total_found,
3067 (unsigned long long)found_key.objectid);
edbd8d4e
CM		 3068 trans = btrfs_start_transaction(tree_root, 1);
3069 btrfs_commit_transaction(trans, tree_root);
3070
3071 mutex_unlock(&root->fs_info->fs_mutex);
3072 btrfs_clean_old_snapshots(tree_root);
3073 mutex_lock(&root->fs_info->fs_mutex);
3074
3075 trans = btrfs_start_transaction(tree_root, 1);
3076 btrfs_commit_transaction(trans, tree_root);
3077 goto again;
3078 }
3079
8f18cf13
CM		 3080 /*
3081 * we've freed all the extents, now remove the block
3082 * group item from the tree
3083 */
edbd8d4e 3084 trans = btrfs_start_transaction(root, 1);
8f18cf13 3085 memcpy(&key, &shrink_block_group->key, sizeof(key));
1372f8e6 3086
8f18cf13
CM		 3087 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3088 if (ret > 0)
3089 ret = -EIO;
3090 if (ret < 0)
3091 goto out;
73e48b27 3092
0ef3e66b
CM		 3093 clear_extent_bits(&info->block_group_cache, key.objectid,
3094 key.objectid + key.offset - 1,
8f18cf13 3095 (unsigned int)-1, GFP_NOFS);
edbd8d4e 3096
0ef3e66b
CM		 3097
3098 clear_extent_bits(&info->free_space_cache,
3099 key.objectid, key.objectid + key.offset - 1,
3100 (unsigned int)-1, GFP_NOFS);
3101
3102 memset(shrink_block_group, 0, sizeof(*shrink_block_group));
3103 kfree(shrink_block_group);
3104
8f18cf13 3105 btrfs_del_item(trans, root, path);
edbd8d4e 3106 btrfs_commit_transaction(trans, root);
0ef3e66b
CM		 3107
3108 /* the code to unpin extents might set a few bits in the free
3109 * space cache for this range again
3110 */
3111 clear_extent_bits(&info->free_space_cache,
3112 key.objectid, key.objectid + key.offset - 1,
3113 (unsigned int)-1, GFP_NOFS);
edbd8d4e
CM		 3114out:
3115 btrfs_free_path(path);
925baedd 3116 mutex_unlock(&root->fs_info->alloc_mutex);
edbd8d4e
CM		 3117 return ret;
3118}
3119
0b86a832
CM		 3120int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
3121 struct btrfs_key *key)
3122{
925baedd 3123 int ret = 0;
0b86a832
CM		 3124 struct btrfs_key found_key;
3125 struct extent_buffer *leaf;
3126 int slot;
edbd8d4e 3127
0b86a832
CM		 3128 ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
3129 if (ret < 0)
925baedd
CM		 3130 goto out;
3131
0b86a832
CM		 3132 while(1) {
3133 slot = path->slots[0];
edbd8d4e 3134 leaf = path->nodes[0];
0b86a832
CM		 3135 if (slot >= btrfs_header_nritems(leaf)) {
3136 ret = btrfs_next_leaf(root, path);
3137 if (ret == 0)
3138 continue;
3139 if (ret < 0)
925baedd 3140 goto out;
0b86a832 3141 break;
edbd8d4e 3142 }
0b86a832 3143 btrfs_item_key_to_cpu(leaf, &found_key, slot);
edbd8d4e 3144
0b86a832 3145 if (found_key.objectid >= key->objectid &&
925baedd
CM		 3146 found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
3147 ret = 0;
3148 goto out;
3149 }
0b86a832 3150 path->slots[0]++;
edbd8d4e 3151 }
0b86a832 3152 ret = -ENOENT;
925baedd 3153out:
0b86a832 3154 return ret;
edbd8d4e
CM		 3155}
3156
9078a3e1
CM		 3157int btrfs_read_block_groups(struct btrfs_root *root)
3158{
3159 struct btrfs_path *path;
3160 int ret;
96b5179d 3161 int bit;
9078a3e1 3162 struct btrfs_block_group_cache *cache;
be744175 3163 struct btrfs_fs_info *info = root->fs_info;
6324fbf3 3164 struct btrfs_space_info *space_info;
d1310b2e 3165 struct extent_io_tree *block_group_cache;
9078a3e1
CM		 3166 struct btrfs_key key;
3167 struct btrfs_key found_key;
5f39d397 3168 struct extent_buffer *leaf;
96b5179d
CM		 3169
3170 block_group_cache = &info->block_group_cache;
be744175 3171 root = info->extent_root;
9078a3e1 3172 key.objectid = 0;
0b86a832 3173 key.offset = 0;
9078a3e1 3174 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
9078a3e1
CM		 3175 path = btrfs_alloc_path();
3176 if (!path)
3177 return -ENOMEM;
3178
925baedd 3179 mutex_lock(&root->fs_info->alloc_mutex);
9078a3e1 3180 while(1) {
0b86a832
CM		 3181 ret = find_first_block_group(root, path, &key);
3182 if (ret > 0) {
3183 ret = 0;
3184 goto error;
9078a3e1 3185 }
0b86a832
CM		 3186 if (ret != 0)
3187 goto error;
3188
5f39d397
CM		 3189 leaf = path->nodes[0];
3190 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
8f18cf13 3191 cache = kzalloc(sizeof(*cache), GFP_NOFS);
9078a3e1 3192 if (!cache) {
0b86a832 3193 ret = -ENOMEM;
9078a3e1
CM		 3194 break;
3195 }
3e1ad54f 3196
5f39d397
CM		 3197 read_extent_buffer(leaf, &cache->item,
3198 btrfs_item_ptr_offset(leaf, path->slots[0]),
3199 sizeof(cache->item));
9078a3e1 3200 memcpy(&cache->key, &found_key, sizeof(found_key));
0b86a832 3201
9078a3e1
CM		 3202 key.objectid = found_key.objectid + found_key.offset;
3203 btrfs_release_path(root, path);
0b86a832
CM		 3204 cache->flags = btrfs_block_group_flags(&cache->item);
3205 bit = 0;
3206 if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
96b5179d 3207 bit = BLOCK_GROUP_DATA;
0b86a832
CM		 3208 } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
3209 bit = BLOCK_GROUP_SYSTEM;
3210 } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
96b5179d 3211 bit = BLOCK_GROUP_METADATA;
31f3c99b 3212 }
8790d502 3213 set_avail_alloc_bits(info, cache->flags);
96b5179d 3214
6324fbf3
CM		 3215 ret = update_space_info(info, cache->flags, found_key.offset,
3216 btrfs_block_group_used(&cache->item),
3217 &space_info);
3218 BUG_ON(ret);
3219 cache->space_info = space_info;
3220
96b5179d
CM		 3221 /* use EXTENT_LOCKED to prevent merging */
3222 set_extent_bits(block_group_cache, found_key.objectid,
3223 found_key.objectid + found_key.offset - 1,
3224 bit | EXTENT_LOCKED, GFP_NOFS);
3225 set_state_private(block_group_cache, found_key.objectid,
ae2f5411 3226 (unsigned long)cache);
96b5179d 3227
9078a3e1 3228 if (key.objectid >=
db94535d 3229 btrfs_super_total_bytes(&info->super_copy))
9078a3e1
CM		 3230 break;
3231 }
0b86a832
CM		 3232 ret = 0;
3233error:
9078a3e1 3234 btrfs_free_path(path);
925baedd 3235 mutex_unlock(&root->fs_info->alloc_mutex);
0b86a832 3236 return ret;
9078a3e1 3237}
6324fbf3
CM		 3238
3239int btrfs_make_block_group(struct btrfs_trans_handle *trans,
3240 struct btrfs_root *root, u64 bytes_used,
e17cade2 3241 u64 type, u64 chunk_objectid, u64 chunk_offset,
6324fbf3
CM		 3242 u64 size)
3243{
3244 int ret;
3245 int bit = 0;
3246 struct btrfs_root *extent_root;
3247 struct btrfs_block_group_cache *cache;
3248 struct extent_io_tree *block_group_cache;
3249
3250 extent_root = root->fs_info->extent_root;
3251 block_group_cache = &root->fs_info->block_group_cache;
3252
8f18cf13 3253 cache = kzalloc(sizeof(*cache), GFP_NOFS);
6324fbf3 3254 BUG_ON(!cache);
e17cade2 3255 cache->key.objectid = chunk_offset;
6324fbf3 3256 cache->key.offset = size;
6324fbf3 3257 btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
0ef3e66b 3258
6324fbf3 3259 btrfs_set_block_group_used(&cache->item, bytes_used);
6324fbf3
CM		 3260 btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
3261 cache->flags = type;
3262 btrfs_set_block_group_flags(&cache->item, type);
3263
3264 ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
3265 &cache->space_info);
3266 BUG_ON(ret);
3267
d18a2c44 3268 bit = block_group_state_bits(type);
e17cade2
CM		 3269 set_extent_bits(block_group_cache, chunk_offset,
3270 chunk_offset + size - 1,
6324fbf3 3271 bit | EXTENT_LOCKED, GFP_NOFS);
6324fbf3 3272
e17cade2
CM		 3273 set_state_private(block_group_cache, chunk_offset,
3274 (unsigned long)cache);
6324fbf3
CM		 3275 ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
3276 sizeof(cache->item));
3277 BUG_ON(ret);
3278
3279 finish_current_insert(trans, extent_root);
3280 ret = del_pending_extents(trans, extent_root);
3281 BUG_ON(ret);
d18a2c44 3282 set_avail_alloc_bits(extent_root->fs_info, type);
925baedd 3283
6324fbf3
CM		 3284 return 0;
3285}
Linux 6.x block layer and io_uring tree(s)