projects / linux-block.git / blame_incremental
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (non-incremental) | history | HEAD
Btrfs: Add a lookup cache to the extent state tree
[linux-block.git] / fs / btrfs / extent-tree.c
... / ...
CommitLineData
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 */
18
19#include <linux/sched.h>
20#include <linux/crc32c.h>
21#include <linux/pagemap.h>
22#include "hash.h"
23#include "ctree.h"
24#include "disk-io.h"
25#include "print-tree.h"
26#include "transaction.h"
27
28#define BLOCK_GROUP_DATA EXTENT_WRITEBACK
29#define BLOCK_GROUP_METADATA EXTENT_UPTODATE
30#define BLOCK_GROUP_DIRTY EXTENT_DIRTY
31
32static int finish_current_insert(struct btrfs_trans_handle *trans, struct
33 btrfs_root *extent_root);
34static int del_pending_extents(struct btrfs_trans_handle *trans, struct
35 btrfs_root *extent_root);
36static int find_previous_extent(struct btrfs_root *root,
37 struct btrfs_path *path)
38{
39 struct btrfs_key found_key;
40 struct extent_buffer *leaf;
41 int ret;
42
43 while(1) {
44 if (path->slots[0] == 0) {
45 ret = btrfs_prev_leaf(root, path);
46 if (ret != 0)
47 return ret;
48 } else {
49 path->slots[0]--;
50 }
51 leaf = path->nodes[0];
52 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
53 if (found_key.type == BTRFS_EXTENT_ITEM_KEY)
54 return 0;
55 }
56 return 1;
57}
58
59static int cache_block_group(struct btrfs_root *root,
60 struct btrfs_block_group_cache *block_group)
61{
62 struct btrfs_path *path;
63 int ret;
64 struct btrfs_key key;
65 struct extent_buffer *leaf;
66 struct extent_io_tree *free_space_cache;
67 int slot;
68 u64 last = 0;
69 u64 hole_size;
70 u64 first_free;
71 int found = 0;
72
73 if (!block_group)
74 return 0;
75
76 root = root->fs_info->extent_root;
77 free_space_cache = &root->fs_info->free_space_cache;
78
79 if (block_group->cached)
80 return 0;
81
82 path = btrfs_alloc_path();
83 if (!path)
84 return -ENOMEM;
85
86 path->reada = 2;
87 first_free = block_group->key.objectid;
88 key.objectid = block_group->key.objectid;
89 key.offset = 0;
90 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
91 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
92 if (ret < 0)
93 return ret;
94 ret = find_previous_extent(root, path);
95 if (ret < 0)
96 return ret;
97 if (ret == 0) {
98 leaf = path->nodes[0];
99 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
100 if (key.objectid + key.offset > first_free)
101 first_free = key.objectid + key.offset;
102 }
103 while(1) {
104 leaf = path->nodes[0];
105 slot = path->slots[0];
106 if (slot >= btrfs_header_nritems(leaf)) {
107 ret = btrfs_next_leaf(root, path);
108 if (ret < 0)
109 goto err;
110 if (ret == 0) {
111 continue;
112 } else {
113 break;
114 }
115 }
116 btrfs_item_key_to_cpu(leaf, &key, slot);
117 if (key.objectid < block_group->key.objectid) {
118 goto next;
119 }
120 if (key.objectid >= block_group->key.objectid +
121 block_group->key.offset) {
122 break;
123 }
124
125 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
126 if (!found) {
127 last = first_free;
128 found = 1;
129 }
130 if (key.objectid > last) {
131 hole_size = key.objectid - last;
132 set_extent_dirty(free_space_cache, last,
133 last + hole_size - 1,
134 GFP_NOFS);
135 }
136 last = key.objectid + key.offset;
137 }
138next:
139 path->slots[0]++;
140 }
141
142 if (!found)
143 last = first_free;
144 if (block_group->key.objectid +
145 block_group->key.offset > last) {
146 hole_size = block_group->key.objectid +
147 block_group->key.offset - last;
148 set_extent_dirty(free_space_cache, last,
149 last + hole_size - 1, GFP_NOFS);
150 }
151 block_group->cached = 1;
152err:
153 btrfs_free_path(path);
154 return 0;
155}
156
157struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
158 btrfs_fs_info *info,
159 u64 bytenr)
160{
161 struct extent_io_tree *block_group_cache;
162 struct btrfs_block_group_cache *block_group = NULL;
163 u64 ptr;
164 u64 start;
165 u64 end;
166 int ret;
167
168 block_group_cache = &info->block_group_cache;
169 ret = find_first_extent_bit(block_group_cache,
170 bytenr, &start, &end,
171 BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
172 if (ret) {
173 return NULL;
174 }
175 ret = get_state_private(block_group_cache, start, &ptr);
176 if (ret)
177 return NULL;
178
179 block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
180 if (block_group->key.objectid <= bytenr && bytenr <
181 block_group->key.objectid + block_group->key.offset)
182 return block_group;
183 return NULL;
184}
185static u64 noinline find_search_start(struct btrfs_root *root,
186 struct btrfs_block_group_cache **cache_ret,
187 u64 search_start, int num, int data)
188{
189 int ret;
190 struct btrfs_block_group_cache *cache = *cache_ret;
191 u64 last;
192 u64 start = 0;
193 u64 end = 0;
194 u64 cache_miss = 0;
195 u64 total_fs_bytes;
196 int wrapped = 0;
197
198 if (!cache) {
199 goto out;
200 }
201 total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
202again:
203 ret = cache_block_group(root, cache);
204 if (ret)
205 goto out;
206
207 last = max(search_start, cache->key.objectid);
208
209 while(1) {
210 ret = find_first_extent_bit(&root->fs_info->free_space_cache,
211 last, &start, &end, EXTENT_DIRTY);
212 if (ret) {
213 if (!cache_miss)
214 cache_miss = last;
215 goto new_group;
216 }
217
218 start = max(last, start);
219 last = end + 1;
220 if (last - start < num) {
221 if (last == cache->key.objectid + cache->key.offset)
222 cache_miss = start;
223 continue;
224 }
225 if (data != BTRFS_BLOCK_GROUP_MIXED &&
226 start + num > cache->key.objectid + cache->key.offset)
227 goto new_group;
228 if (start + num > total_fs_bytes)
229 goto new_group;
230 return start;
231 }
232out:
233 cache = btrfs_lookup_block_group(root->fs_info, search_start);
234 if (!cache) {
235 printk("Unable to find block group for %Lu\n",
236 search_start);
237 WARN_ON(1);
238 return search_start;
239 }
240 return search_start;
241
242new_group:
243 last = cache->key.objectid + cache->key.offset;
244wrapped:
245 cache = btrfs_lookup_block_group(root->fs_info, last);
246 if (!cache || cache->key.objectid >= total_fs_bytes) {
247no_cache:
248 if (!wrapped) {
249 wrapped = 1;
250 last = search_start;
251 data = BTRFS_BLOCK_GROUP_MIXED;
252 goto wrapped;
253 }
254 goto out;
255 }
256 if (cache_miss && !cache->cached) {
257 cache_block_group(root, cache);
258 last = cache_miss;
259 cache = btrfs_lookup_block_group(root->fs_info, last);
260 }
261 cache = btrfs_find_block_group(root, cache, last, data, 0);
262 if (!cache)
263 goto no_cache;
264 *cache_ret = cache;
265 cache_miss = 0;
266 goto again;
267}
268
269static u64 div_factor(u64 num, int factor)
270{
271 if (factor == 10)
272 return num;
273 num *= factor;
274 do_div(num, 10);
275 return num;
276}
277
278struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
279 struct btrfs_block_group_cache
280 *hint, u64 search_start,
281 int data, int owner)
282{
283 struct btrfs_block_group_cache *cache;
284 struct extent_io_tree *block_group_cache;
285 struct btrfs_block_group_cache *found_group = NULL;
286 struct btrfs_fs_info *info = root->fs_info;
287 u64 used;
288 u64 last = 0;
289 u64 hint_last;
290 u64 start;
291 u64 end;
292 u64 free_check;
293 u64 ptr;
294 u64 total_fs_bytes;
295 int bit;
296 int ret;
297 int full_search = 0;
298 int factor = 8;
299 int data_swap = 0;
300
301 block_group_cache = &info->block_group_cache;
302 total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
303
304 if (!owner)
305 factor = 8;
306
307 if (data == BTRFS_BLOCK_GROUP_MIXED) {
308 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
309 factor = 10;
310 } else if (data)
311 bit = BLOCK_GROUP_DATA;
312 else
313 bit = BLOCK_GROUP_METADATA;
314
315 if (search_start && search_start < total_fs_bytes) {
316 struct btrfs_block_group_cache *shint;
317 shint = btrfs_lookup_block_group(info, search_start);
318 if (shint && (shint->data == data ||
319 shint->data == BTRFS_BLOCK_GROUP_MIXED)) {
320 used = btrfs_block_group_used(&shint->item);
321 if (used + shint->pinned <
322 div_factor(shint->key.offset, factor)) {
323 return shint;
324 }
325 }
326 }
327 if (hint && hint->key.objectid < total_fs_bytes &&
328 (hint->data == data || hint->data == BTRFS_BLOCK_GROUP_MIXED)) {
329 used = btrfs_block_group_used(&hint->item);
330 if (used + hint->pinned <
331 div_factor(hint->key.offset, factor)) {
332 return hint;
333 }
334 last = hint->key.objectid + hint->key.offset;
335 hint_last = last;
336 } else {
337 if (hint)
338 hint_last = max(hint->key.objectid, search_start);
339 else
340 hint_last = search_start;
341
342 if (hint_last >= total_fs_bytes)
343 hint_last = search_start;
344 last = hint_last;
345 }
346again:
347 while(1) {
348 ret = find_first_extent_bit(block_group_cache, last,
349 &start, &end, bit);
350 if (ret)
351 break;
352
353 ret = get_state_private(block_group_cache, start, &ptr);
354 if (ret)
355 break;
356
357 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
358 last = cache->key.objectid + cache->key.offset;
359 used = btrfs_block_group_used(&cache->item);
360
361 if (cache->key.objectid > total_fs_bytes)
362 break;
363
364 if (full_search)
365 free_check = cache->key.offset;
366 else
367 free_check = div_factor(cache->key.offset, factor);
368 if (used + cache->pinned < free_check) {
369 found_group = cache;
370 goto found;
371 }
372 cond_resched();
373 }
374 if (!full_search) {
375 last = search_start;
376 full_search = 1;
377 goto again;
378 }
379 if (!data_swap) {
380 data_swap = 1;
381 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
382 last = search_start;
383 goto again;
384 }
385found:
386 return found_group;
387}
388
389static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
390 u64 owner, u64 owner_offset)
391{
392 u32 high_crc = ~(u32)0;
393 u32 low_crc = ~(u32)0;
394 __le64 lenum;
395
396 lenum = cpu_to_le64(root_objectid);
397 high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
398 lenum = cpu_to_le64(ref_generation);
399 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
400
401#if 0
402 lenum = cpu_to_le64(owner);
403 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
404 lenum = cpu_to_le64(owner_offset);
405 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
406#endif
407 return ((u64)high_crc << 32) | (u64)low_crc;
408}
409
410static int match_extent_ref(struct extent_buffer *leaf,
411 struct btrfs_extent_ref *disk_ref,
412 struct btrfs_extent_ref *cpu_ref)
413{
414 int ret;
415 int len;
416
417 if (cpu_ref->objectid)
418 len = sizeof(*cpu_ref);
419 else
420 len = 2 * sizeof(u64);
421 ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
422 len);
423 return ret == 0;
424}
425
426static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
427 struct btrfs_root *root,
428 struct btrfs_path *path, u64 bytenr,
429 u64 root_objectid,
430 u64 ref_generation, u64 owner,
431 u64 owner_offset, int del)
432{
433 u64 hash;
434 struct btrfs_key key;
435 struct btrfs_key found_key;
436 struct btrfs_extent_ref ref;
437 struct extent_buffer *leaf;
438 struct btrfs_extent_ref *disk_ref;
439 int ret;
440 int ret2;
441
442 btrfs_set_stack_ref_root(&ref, root_objectid);
443 btrfs_set_stack_ref_generation(&ref, ref_generation);
444 btrfs_set_stack_ref_objectid(&ref, owner);
445 btrfs_set_stack_ref_offset(&ref, owner_offset);
446
447 hash = hash_extent_ref(root_objectid, ref_generation, owner,
448 owner_offset);
449 key.offset = hash;
450 key.objectid = bytenr;
451 key.type = BTRFS_EXTENT_REF_KEY;
452
453 while (1) {
454 ret = btrfs_search_slot(trans, root, &key, path,
455 del ? -1 : 0, del);
456 if (ret < 0)
457 goto out;
458 leaf = path->nodes[0];
459 if (ret != 0) {
460 u32 nritems = btrfs_header_nritems(leaf);
461 if (path->slots[0] >= nritems) {
462 ret2 = btrfs_next_leaf(root, path);
463 if (ret2)
464 goto out;
465 leaf = path->nodes[0];
466 }
467 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
468 if (found_key.objectid != bytenr ||
469 found_key.type != BTRFS_EXTENT_REF_KEY)
470 goto out;
471 key.offset = found_key.offset;
472 if (del) {
473 btrfs_release_path(root, path);
474 continue;
475 }
476 }
477 disk_ref = btrfs_item_ptr(path->nodes[0],
478 path->slots[0],
479 struct btrfs_extent_ref);
480 if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
481 ret = 0;
482 goto out;
483 }
484 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
485 key.offset = found_key.offset + 1;
486 btrfs_release_path(root, path);
487 }
488out:
489 return ret;
490}
491
492/*
493 * Back reference rules. Back refs have three main goals:
494 *
495 * 1) differentiate between all holders of references to an extent so that
496 * when a reference is dropped we can make sure it was a valid reference
497 * before freeing the extent.
498 *
499 * 2) Provide enough information to quickly find the holders of an extent
500 * if we notice a given block is corrupted or bad.
501 *
502 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
503 * maintenance. This is actually the same as #2, but with a slightly
504 * different use case.
505 *
506 * File extents can be referenced by:
507 *
508 * - multiple snapshots, subvolumes, or different generations in one subvol
509 * - different files inside a single subvolume (in theory, not implemented yet)
510 * - different offsets inside a file (bookend extents in file.c)
511 *
512 * The extent ref structure has fields for:
513 *
514 * - Objectid of the subvolume root
515 * - Generation number of the tree holding the reference
516 * - objectid of the file holding the reference
517 * - offset in the file corresponding to the key holding the reference
518 *
519 * When a file extent is allocated the fields are filled in:
520 * (root_key.objectid, trans->transid, inode objectid, offset in file)
521 *
522 * When a leaf is cow'd new references are added for every file extent found
523 * in the leaf. It looks the same as the create case, but trans->transid
524 * will be different when the block is cow'd.
525 *
526 * (root_key.objectid, trans->transid, inode objectid, offset in file)
527 *
528 * When a file extent is removed either during snapshot deletion or file
529 * truncation, the corresponding back reference is found
530 * by searching for:
531 *
532 * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
533 * inode objectid, offset in file)
534 *
535 * Btree extents can be referenced by:
536 *
537 * - Different subvolumes
538 * - Different generations of the same subvolume
539 *
540 * Storing sufficient information for a full reverse mapping of a btree
541 * block would require storing the lowest key of the block in the backref,
542 * and it would require updating that lowest key either before write out or
543 * every time it changed. Instead, the objectid of the lowest key is stored
544 * along with the level of the tree block. This provides a hint
545 * about where in the btree the block can be found. Searches through the
546 * btree only need to look for a pointer to that block, so they stop one
547 * level higher than the level recorded in the backref.
548 *
549 * Some btrees do not do reference counting on their extents. These
550 * include the extent tree and the tree of tree roots. Backrefs for these
551 * trees always have a generation of zero.
552 *
553 * When a tree block is created, back references are inserted:
554 *
555 * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
556 *
557 * When a tree block is cow'd in a reference counted root,
558 * new back references are added for all the blocks it points to.
559 * These are of the form (trans->transid will have increased since creation):
560 *
561 * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
562 *
563 * Because the lowest_key_objectid and the level are just hints
564 * they are not used when backrefs are deleted. When a backref is deleted:
565 *
566 * if backref was for a tree root:
567 * root_objectid = root->root_key.objectid
568 * else
569 * root_objectid = btrfs_header_owner(parent)
570 *
571 * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
572 *
573 * Back Reference Key hashing:
574 *
575 * Back references have four fields, each 64 bits long. Unfortunately,
576 * This is hashed into a single 64 bit number and placed into the key offset.
577 * The key objectid corresponds to the first byte in the extent, and the
578 * key type is set to BTRFS_EXTENT_REF_KEY
579 */
580int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
581 struct btrfs_root *root,
582 struct btrfs_path *path, u64 bytenr,
583 u64 root_objectid, u64 ref_generation,
584 u64 owner, u64 owner_offset)
585{
586 u64 hash;
587 struct btrfs_key key;
588 struct btrfs_extent_ref ref;
589 struct btrfs_extent_ref *disk_ref;
590 int ret;
591
592 btrfs_set_stack_ref_root(&ref, root_objectid);
593 btrfs_set_stack_ref_generation(&ref, ref_generation);
594 btrfs_set_stack_ref_objectid(&ref, owner);
595 btrfs_set_stack_ref_offset(&ref, owner_offset);
596
597 hash = hash_extent_ref(root_objectid, ref_generation, owner,
598 owner_offset);
599 key.offset = hash;
600 key.objectid = bytenr;
601 key.type = BTRFS_EXTENT_REF_KEY;
602
603 ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
604 while (ret == -EEXIST) {
605 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
606 struct btrfs_extent_ref);
607 if (match_extent_ref(path->nodes[0], disk_ref, &ref))
608 goto out;
609 key.offset++;
610 btrfs_release_path(root, path);
611 ret = btrfs_insert_empty_item(trans, root, path, &key,
612 sizeof(ref));
613 }
614 if (ret)
615 goto out;
616 disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
617 struct btrfs_extent_ref);
618 write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
619 sizeof(ref));
620 btrfs_mark_buffer_dirty(path->nodes[0]);
621out:
622 btrfs_release_path(root, path);
623 return ret;
624}
625
626int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
627 struct btrfs_root *root,
628 u64 bytenr, u64 num_bytes,
629 u64 root_objectid, u64 ref_generation,
630 u64 owner, u64 owner_offset)
631{
632 struct btrfs_path *path;
633 int ret;
634 struct btrfs_key key;
635 struct extent_buffer *l;
636 struct btrfs_extent_item *item;
637 u32 refs;
638
639 WARN_ON(num_bytes < root->sectorsize);
640 path = btrfs_alloc_path();
641 if (!path)
642 return -ENOMEM;
643
644 path->reada = 0;
645 key.objectid = bytenr;
646 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
647 key.offset = num_bytes;
648 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
649 0, 1);
650 if (ret < 0)
651 return ret;
652 if (ret != 0) {
653 BUG();
654 }
655 BUG_ON(ret != 0);
656 l = path->nodes[0];
657 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
658 refs = btrfs_extent_refs(l, item);
659 btrfs_set_extent_refs(l, item, refs + 1);
660 btrfs_mark_buffer_dirty(path->nodes[0]);
661
662 btrfs_release_path(root->fs_info->extent_root, path);
663
664 path->reada = 0;
665 ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
666 path, bytenr, root_objectid,
667 ref_generation, owner, owner_offset);
668 BUG_ON(ret);
669 finish_current_insert(trans, root->fs_info->extent_root);
670 del_pending_extents(trans, root->fs_info->extent_root);
671
672 btrfs_free_path(path);
673 return 0;
674}
675
676int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
677 struct btrfs_root *root)
678{
679 finish_current_insert(trans, root->fs_info->extent_root);
680 del_pending_extents(trans, root->fs_info->extent_root);
681 return 0;
682}
683
684static int lookup_extent_ref(struct btrfs_trans_handle *trans,
685 struct btrfs_root *root, u64 bytenr,
686 u64 num_bytes, u32 *refs)
687{
688 struct btrfs_path *path;
689 int ret;
690 struct btrfs_key key;
691 struct extent_buffer *l;
692 struct btrfs_extent_item *item;
693
694 WARN_ON(num_bytes < root->sectorsize);
695 path = btrfs_alloc_path();
696 path->reada = 0;
697 key.objectid = bytenr;
698 key.offset = num_bytes;
699 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
700 ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
701 0, 0);
702 if (ret < 0)
703 goto out;
704 if (ret != 0) {
705 btrfs_print_leaf(root, path->nodes[0]);
706 printk("failed to find block number %Lu\n", bytenr);
707 BUG();
708 }
709 l = path->nodes[0];
710 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
711 *refs = btrfs_extent_refs(l, item);
712out:
713 btrfs_free_path(path);
714 return 0;
715}
716
717u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
718 struct btrfs_path *count_path,
719 u64 first_extent)
720{
721 struct btrfs_root *extent_root = root->fs_info->extent_root;
722 struct btrfs_path *path;
723 u64 bytenr;
724 u64 found_objectid;
725 u64 root_objectid = root->root_key.objectid;
726 u32 total_count = 0;
727 u32 cur_count;
728 u32 nritems;
729 int ret;
730 struct btrfs_key key;
731 struct btrfs_key found_key;
732 struct extent_buffer *l;
733 struct btrfs_extent_item *item;
734 struct btrfs_extent_ref *ref_item;
735 int level = -1;
736
737 path = btrfs_alloc_path();
738again:
739 if (level == -1)
740 bytenr = first_extent;
741 else
742 bytenr = count_path->nodes[level]->start;
743
744 cur_count = 0;
745 key.objectid = bytenr;
746 key.offset = 0;
747
748 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
749 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
750 if (ret < 0)
751 goto out;
752 BUG_ON(ret == 0);
753
754 l = path->nodes[0];
755 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
756
757 if (found_key.objectid != bytenr ||
758 found_key.type != BTRFS_EXTENT_ITEM_KEY) {
759 goto out;
760 }
761
762 item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
763 while (1) {
764 l = path->nodes[0];
765 nritems = btrfs_header_nritems(l);
766 if (path->slots[0] >= nritems) {
767 ret = btrfs_next_leaf(extent_root, path);
768 if (ret == 0)
769 continue;
770 break;
771 }
772 btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
773 if (found_key.objectid != bytenr)
774 break;
775
776 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
777 path->slots[0]++;
778 continue;
779 }
780
781 cur_count++;
782 ref_item = btrfs_item_ptr(l, path->slots[0],
783 struct btrfs_extent_ref);
784 found_objectid = btrfs_ref_root(l, ref_item);
785
786 if (found_objectid != root_objectid) {
787 total_count = 2;
788 goto out;
789 }
790 total_count = 1;
791 path->slots[0]++;
792 }
793 if (cur_count == 0) {
794 total_count = 0;
795 goto out;
796 }
797 if (level >= 0 && root->node == count_path->nodes[level])
798 goto out;
799 level++;
800 btrfs_release_path(root, path);
801 goto again;
802
803out:
804 btrfs_free_path(path);
805 return total_count;
806}
807int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
808 struct btrfs_root *root, u64 owner_objectid)
809{
810 u64 generation;
811 u64 key_objectid;
812 u64 level;
813 u32 nritems;
814 struct btrfs_disk_key disk_key;
815
816 level = btrfs_header_level(root->node);
817 generation = trans->transid;
818 nritems = btrfs_header_nritems(root->node);
819 if (nritems > 0) {
820 if (level == 0)
821 btrfs_item_key(root->node, &disk_key, 0);
822 else
823 btrfs_node_key(root->node, &disk_key, 0);
824 key_objectid = btrfs_disk_key_objectid(&disk_key);
825 } else {
826 key_objectid = 0;
827 }
828 return btrfs_inc_extent_ref(trans, root, root->node->start,
829 root->node->len, owner_objectid,
830 generation, level, key_objectid);
831}
832
833int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
834 struct extent_buffer *buf)
835{
836 u64 bytenr;
837 u32 nritems;
838 struct btrfs_key key;
839 struct btrfs_file_extent_item *fi;
840 int i;
841 int level;
842 int ret;
843 int faili;
844
845 if (!root->ref_cows)
846 return 0;
847
848 level = btrfs_header_level(buf);
849 nritems = btrfs_header_nritems(buf);
850 for (i = 0; i < nritems; i++) {
851 if (level == 0) {
852 u64 disk_bytenr;
853 btrfs_item_key_to_cpu(buf, &key, i);
854 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
855 continue;
856 fi = btrfs_item_ptr(buf, i,
857 struct btrfs_file_extent_item);
858 if (btrfs_file_extent_type(buf, fi) ==
859 BTRFS_FILE_EXTENT_INLINE)
860 continue;
861 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
862 if (disk_bytenr == 0)
863 continue;
864 ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
865 btrfs_file_extent_disk_num_bytes(buf, fi),
866 root->root_key.objectid, trans->transid,
867 key.objectid, key.offset);
868 if (ret) {
869 faili = i;
870 goto fail;
871 }
872 } else {
873 bytenr = btrfs_node_blockptr(buf, i);
874 btrfs_node_key_to_cpu(buf, &key, i);
875 ret = btrfs_inc_extent_ref(trans, root, bytenr,
876 btrfs_level_size(root, level - 1),
877 root->root_key.objectid,
878 trans->transid,
879 level - 1, key.objectid);
880 if (ret) {
881 faili = i;
882 goto fail;
883 }
884 }
885 }
886 return 0;
887fail:
888 WARN_ON(1);
889#if 0
890 for (i =0; i < faili; i++) {
891 if (level == 0) {
892 u64 disk_bytenr;
893 btrfs_item_key_to_cpu(buf, &key, i);
894 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
895 continue;
896 fi = btrfs_item_ptr(buf, i,
897 struct btrfs_file_extent_item);
898 if (btrfs_file_extent_type(buf, fi) ==
899 BTRFS_FILE_EXTENT_INLINE)
900 continue;
901 disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
902 if (disk_bytenr == 0)
903 continue;
904 err = btrfs_free_extent(trans, root, disk_bytenr,
905 btrfs_file_extent_disk_num_bytes(buf,
906 fi), 0);
907 BUG_ON(err);
908 } else {
909 bytenr = btrfs_node_blockptr(buf, i);
910 err = btrfs_free_extent(trans, root, bytenr,
911 btrfs_level_size(root, level - 1), 0);
912 BUG_ON(err);
913 }
914 }
915#endif
916 return ret;
917}
918
919static int write_one_cache_group(struct btrfs_trans_handle *trans,
920 struct btrfs_root *root,
921 struct btrfs_path *path,
922 struct btrfs_block_group_cache *cache)
923{
924 int ret;
925 int pending_ret;
926 struct btrfs_root *extent_root = root->fs_info->extent_root;
927 unsigned long bi;
928 struct extent_buffer *leaf;
929
930 ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
931 if (ret < 0)
932 goto fail;
933 BUG_ON(ret);
934
935 leaf = path->nodes[0];
936 bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
937 write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
938 btrfs_mark_buffer_dirty(leaf);
939 btrfs_release_path(extent_root, path);
940fail:
941 finish_current_insert(trans, extent_root);
942 pending_ret = del_pending_extents(trans, extent_root);
943 if (ret)
944 return ret;
945 if (pending_ret)
946 return pending_ret;
947 return 0;
948
949}
950
951int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
952 struct btrfs_root *root)
953{
954 struct extent_io_tree *block_group_cache;
955 struct btrfs_block_group_cache *cache;
956 int ret;
957 int err = 0;
958 int werr = 0;
959 struct btrfs_path *path;
960 u64 last = 0;
961 u64 start;
962 u64 end;
963 u64 ptr;
964
965 block_group_cache = &root->fs_info->block_group_cache;
966 path = btrfs_alloc_path();
967 if (!path)
968 return -ENOMEM;
969
970 while(1) {
971 ret = find_first_extent_bit(block_group_cache, last,
972 &start, &end, BLOCK_GROUP_DIRTY);
973 if (ret)
974 break;
975
976 last = end + 1;
977 ret = get_state_private(block_group_cache, start, &ptr);
978 if (ret)
979 break;
980
981 cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
982 err = write_one_cache_group(trans, root,
983 path, cache);
984 /*
985 * if we fail to write the cache group, we want
986 * to keep it marked dirty in hopes that a later
987 * write will work
988 */
989 if (err) {
990 werr = err;
991 continue;
992 }
993 clear_extent_bits(block_group_cache, start, end,
994 BLOCK_GROUP_DIRTY, GFP_NOFS);
995 }
996 btrfs_free_path(path);
997 return werr;
998}
999
1000static int update_block_group(struct btrfs_trans_handle *trans,
1001 struct btrfs_root *root,
1002 u64 bytenr, u64 num_bytes, int alloc,
1003 int mark_free, int data)
1004{
1005 struct btrfs_block_group_cache *cache;
1006 struct btrfs_fs_info *info = root->fs_info;
1007 u64 total = num_bytes;
1008 u64 old_val;
1009 u64 byte_in_group;
1010 u64 start;
1011 u64 end;
1012
1013 while(total) {
1014 cache = btrfs_lookup_block_group(info, bytenr);
1015 if (!cache) {
1016 return -1;
1017 }
1018 byte_in_group = bytenr - cache->key.objectid;
1019 WARN_ON(byte_in_group > cache->key.offset);
1020 start = cache->key.objectid;
1021 end = start + cache->key.offset - 1;
1022 set_extent_bits(&info->block_group_cache, start, end,
1023 BLOCK_GROUP_DIRTY, GFP_NOFS);
1024
1025 old_val = btrfs_block_group_used(&cache->item);
1026 num_bytes = min(total, cache->key.offset - byte_in_group);
1027 if (alloc) {
1028 if (cache->data != data &&
1029 old_val < (cache->key.offset >> 1)) {
1030 int bit_to_clear;
1031 int bit_to_set;
1032 cache->data = data;
1033 if (data) {
1034 bit_to_clear = BLOCK_GROUP_METADATA;
1035 bit_to_set = BLOCK_GROUP_DATA;
1036 cache->item.flags &=
1037 ~BTRFS_BLOCK_GROUP_MIXED;
1038 cache->item.flags |=
1039 BTRFS_BLOCK_GROUP_DATA;
1040 } else {
1041 bit_to_clear = BLOCK_GROUP_DATA;
1042 bit_to_set = BLOCK_GROUP_METADATA;
1043 cache->item.flags &=
1044 ~BTRFS_BLOCK_GROUP_MIXED;
1045 cache->item.flags &=
1046 ~BTRFS_BLOCK_GROUP_DATA;
1047 }
1048 clear_extent_bits(&info->block_group_cache,
1049 start, end, bit_to_clear,
1050 GFP_NOFS);
1051 set_extent_bits(&info->block_group_cache,
1052 start, end, bit_to_set,
1053 GFP_NOFS);
1054 } else if (cache->data != data &&
1055 cache->data != BTRFS_BLOCK_GROUP_MIXED) {
1056 cache->data = BTRFS_BLOCK_GROUP_MIXED;
1057 set_extent_bits(&info->block_group_cache,
1058 start, end,
1059 BLOCK_GROUP_DATA |
1060 BLOCK_GROUP_METADATA,
1061 GFP_NOFS);
1062 }
1063 old_val += num_bytes;
1064 } else {
1065 old_val -= num_bytes;
1066 if (mark_free) {
1067 set_extent_dirty(&info->free_space_cache,
1068 bytenr, bytenr + num_bytes - 1,
1069 GFP_NOFS);
1070 }
1071 }
1072 btrfs_set_block_group_used(&cache->item, old_val);
1073 total -= num_bytes;
1074 bytenr += num_bytes;
1075 }
1076 return 0;
1077}
1078static int update_pinned_extents(struct btrfs_root *root,
1079 u64 bytenr, u64 num, int pin)
1080{
1081 u64 len;
1082 struct btrfs_block_group_cache *cache;
1083 struct btrfs_fs_info *fs_info = root->fs_info;
1084
1085 if (pin) {
1086 set_extent_dirty(&fs_info->pinned_extents,
1087 bytenr, bytenr + num - 1, GFP_NOFS);
1088 } else {
1089 clear_extent_dirty(&fs_info->pinned_extents,
1090 bytenr, bytenr + num - 1, GFP_NOFS);
1091 }
1092 while (num > 0) {
1093 cache = btrfs_lookup_block_group(fs_info, bytenr);
1094 WARN_ON(!cache);
1095 len = min(num, cache->key.offset -
1096 (bytenr - cache->key.objectid));
1097 if (pin) {
1098 cache->pinned += len;
1099 fs_info->total_pinned += len;
1100 } else {
1101 cache->pinned -= len;
1102 fs_info->total_pinned -= len;
1103 }
1104 bytenr += len;
1105 num -= len;
1106 }
1107 return 0;
1108}
1109
1110int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1111{
1112 u64 last = 0;
1113 u64 start;
1114 u64 end;
1115 struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1116 int ret;
1117
1118 while(1) {
1119 ret = find_first_extent_bit(pinned_extents, last,
1120 &start, &end, EXTENT_DIRTY);
1121 if (ret)
1122 break;
1123 set_extent_dirty(copy, start, end, GFP_NOFS);
1124 last = end + 1;
1125 }
1126 return 0;
1127}
1128
1129int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1130 struct btrfs_root *root,
1131 struct extent_io_tree *unpin)
1132{
1133 u64 start;
1134 u64 end;
1135 int ret;
1136 struct extent_io_tree *free_space_cache;
1137 free_space_cache = &root->fs_info->free_space_cache;
1138
1139 while(1) {
1140 ret = find_first_extent_bit(unpin, 0, &start, &end,
1141 EXTENT_DIRTY);
1142 if (ret)
1143 break;
1144 update_pinned_extents(root, start, end + 1 - start, 0);
1145 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1146 set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
1147 }
1148 return 0;
1149}
1150
1151static int finish_current_insert(struct btrfs_trans_handle *trans,
1152 struct btrfs_root *extent_root)
1153{
1154 u64 start;
1155 u64 end;
1156 struct btrfs_fs_info *info = extent_root->fs_info;
1157 struct extent_buffer *eb;
1158 struct btrfs_path *path;
1159 struct btrfs_key ins;
1160 struct btrfs_disk_key first;
1161 struct btrfs_extent_item extent_item;
1162 int ret;
1163 int level;
1164 int err = 0;
1165
1166 btrfs_set_stack_extent_refs(&extent_item, 1);
1167 btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
1168 path = btrfs_alloc_path();
1169
1170 while(1) {
1171 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1172 &end, EXTENT_LOCKED);
1173 if (ret)
1174 break;
1175
1176 ins.objectid = start;
1177 ins.offset = end + 1 - start;
1178 err = btrfs_insert_item(trans, extent_root, &ins,
1179 &extent_item, sizeof(extent_item));
1180 clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
1181 GFP_NOFS);
1182 eb = read_tree_block(extent_root, ins.objectid, ins.offset);
1183 level = btrfs_header_level(eb);
1184 if (level == 0) {
1185 btrfs_item_key(eb, &first, 0);
1186 } else {
1187 btrfs_node_key(eb, &first, 0);
1188 }
1189 err = btrfs_insert_extent_backref(trans, extent_root, path,
1190 start, extent_root->root_key.objectid,
1191 0, level,
1192 btrfs_disk_key_objectid(&first));
1193 BUG_ON(err);
1194 free_extent_buffer(eb);
1195 }
1196 btrfs_free_path(path);
1197 return 0;
1198}
1199
1200static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
1201 int pending)
1202{
1203 int err = 0;
1204 struct extent_buffer *buf;
1205
1206 if (!pending) {
1207 buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1208 if (buf) {
1209 if (btrfs_buffer_uptodate(buf)) {
1210 u64 transid =
1211 root->fs_info->running_transaction->transid;
1212 u64 header_transid =
1213 btrfs_header_generation(buf);
1214 if (header_transid == transid) {
1215 clean_tree_block(NULL, root, buf);
1216 free_extent_buffer(buf);
1217 return 1;
1218 }
1219 }
1220 free_extent_buffer(buf);
1221 }
1222 update_pinned_extents(root, bytenr, num_bytes, 1);
1223 } else {
1224 set_extent_bits(&root->fs_info->pending_del,
1225 bytenr, bytenr + num_bytes - 1,
1226 EXTENT_LOCKED, GFP_NOFS);
1227 }
1228 BUG_ON(err < 0);
1229 return 0;
1230}
1231
1232/*
1233 * remove an extent from the root, returns 0 on success
1234 */
1235static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1236 *root, u64 bytenr, u64 num_bytes,
1237 u64 root_objectid, u64 ref_generation,
1238 u64 owner_objectid, u64 owner_offset, int pin,
1239 int mark_free)
1240{
1241 struct btrfs_path *path;
1242 struct btrfs_key key;
1243 struct btrfs_fs_info *info = root->fs_info;
1244 struct btrfs_root *extent_root = info->extent_root;
1245 struct extent_buffer *leaf;
1246 int ret;
1247 struct btrfs_extent_item *ei;
1248 u32 refs;
1249
1250 key.objectid = bytenr;
1251 btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1252 key.offset = num_bytes;
1253 path = btrfs_alloc_path();
1254 if (!path)
1255 return -ENOMEM;
1256
1257 path->reada = 0;
1258 ret = lookup_extent_backref(trans, extent_root, path,
1259 bytenr, root_objectid,
1260 ref_generation,
1261 owner_objectid, owner_offset, 1);
1262 if (ret == 0) {
1263 ret = btrfs_del_item(trans, extent_root, path);
1264 } else {
1265 btrfs_print_leaf(extent_root, path->nodes[0]);
1266 WARN_ON(1);
1267 printk("Unable to find ref byte nr %Lu root %Lu "
1268 " gen %Lu owner %Lu offset %Lu\n", bytenr,
1269 root_objectid, ref_generation, owner_objectid,
1270 owner_offset);
1271 }
1272 btrfs_release_path(extent_root, path);
1273 ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
1274 if (ret < 0)
1275 return ret;
1276 BUG_ON(ret);
1277
1278 leaf = path->nodes[0];
1279 ei = btrfs_item_ptr(leaf, path->slots[0],
1280 struct btrfs_extent_item);
1281 refs = btrfs_extent_refs(leaf, ei);
1282 BUG_ON(refs == 0);
1283 refs -= 1;
1284 btrfs_set_extent_refs(leaf, ei, refs);
1285 btrfs_mark_buffer_dirty(leaf);
1286
1287 if (refs == 0) {
1288 u64 super_used;
1289 u64 root_used;
1290
1291 if (pin) {
1292 ret = pin_down_bytes(root, bytenr, num_bytes, 0);
1293 if (ret > 0)
1294 mark_free = 1;
1295 BUG_ON(ret < 0);
1296 }
1297
1298 /* block accounting for super block */
1299 super_used = btrfs_super_bytes_used(&info->super_copy);
1300 btrfs_set_super_bytes_used(&info->super_copy,
1301 super_used - num_bytes);
1302
1303 /* block accounting for root item */
1304 root_used = btrfs_root_used(&root->root_item);
1305 btrfs_set_root_used(&root->root_item,
1306 root_used - num_bytes);
1307
1308 ret = btrfs_del_item(trans, extent_root, path);
1309 if (ret) {
1310 return ret;
1311 }
1312 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
1313 mark_free, 0);
1314 BUG_ON(ret);
1315 }
1316 btrfs_free_path(path);
1317 finish_current_insert(trans, extent_root);
1318 return ret;
1319}
1320
1321/*
1322 * find all the blocks marked as pending in the radix tree and remove
1323 * them from the extent map
1324 */
1325static int del_pending_extents(struct btrfs_trans_handle *trans, struct
1326 btrfs_root *extent_root)
1327{
1328 int ret;
1329 int err = 0;
1330 u64 start;
1331 u64 end;
1332 struct extent_io_tree *pending_del;
1333 struct extent_io_tree *pinned_extents;
1334
1335 pending_del = &extent_root->fs_info->pending_del;
1336 pinned_extents = &extent_root->fs_info->pinned_extents;
1337
1338 while(1) {
1339 ret = find_first_extent_bit(pending_del, 0, &start, &end,
1340 EXTENT_LOCKED);
1341 if (ret)
1342 break;
1343 update_pinned_extents(extent_root, start, end + 1 - start, 1);
1344 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
1345 GFP_NOFS);
1346 ret = __free_extent(trans, extent_root,
1347 start, end + 1 - start,
1348 extent_root->root_key.objectid,
1349 0, 0, 0, 0, 0);
1350 if (ret)
1351 err = ret;
1352 }
1353 return err;
1354}
1355
1356/*
1357 * remove an extent from the root, returns 0 on success
1358 */
1359int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
1360 *root, u64 bytenr, u64 num_bytes,
1361 u64 root_objectid, u64 ref_generation,
1362 u64 owner_objectid, u64 owner_offset, int pin)
1363{
1364 struct btrfs_root *extent_root = root->fs_info->extent_root;
1365 int pending_ret;
1366 int ret;
1367
1368 WARN_ON(num_bytes < root->sectorsize);
1369 if (!root->ref_cows)
1370 ref_generation = 0;
1371
1372 if (root == extent_root) {
1373 pin_down_bytes(root, bytenr, num_bytes, 1);
1374 return 0;
1375 }
1376 ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
1377 ref_generation, owner_objectid, owner_offset,
1378 pin, pin == 0);
1379 pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
1380 return ret ? ret : pending_ret;
1381}
1382
1383static u64 stripe_align(struct btrfs_root *root, u64 val)
1384{
1385 u64 mask = ((u64)root->stripesize - 1);
1386 u64 ret = (val + mask) & ~mask;
1387 return ret;
1388}
1389
1390/*
1391 * walks the btree of allocated extents and find a hole of a given size.
1392 * The key ins is changed to record the hole:
1393 * ins->objectid == block start
1394 * ins->flags = BTRFS_EXTENT_ITEM_KEY
1395 * ins->offset == number of blocks
1396 * Any available blocks before search_start are skipped.
1397 */
1398static int noinline find_free_extent(struct btrfs_trans_handle *trans,
1399 struct btrfs_root *orig_root,
1400 u64 num_bytes, u64 empty_size,
1401 u64 search_start, u64 search_end,
1402 u64 hint_byte, struct btrfs_key *ins,
1403 u64 exclude_start, u64 exclude_nr,
1404 int data)
1405{
1406 struct btrfs_path *path;
1407 struct btrfs_key key;
1408 u64 hole_size = 0;
1409 u64 aligned;
1410 int ret;
1411 int slot = 0;
1412 u64 last_byte = 0;
1413 u64 *last_ptr = NULL;
1414 u64 orig_search_start = search_start;
1415 int start_found;
1416 struct extent_buffer *l;
1417 struct btrfs_root * root = orig_root->fs_info->extent_root;
1418 struct btrfs_fs_info *info = root->fs_info;
1419 u64 total_needed = num_bytes;
1420 int level;
1421 struct btrfs_block_group_cache *block_group;
1422 int full_scan = 0;
1423 int wrapped = 0;
1424 u64 cached_start;
1425
1426 WARN_ON(num_bytes < root->sectorsize);
1427 btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
1428
1429 level = btrfs_header_level(root->node);
1430
1431 if (num_bytes >= 32 * 1024 * 1024 && hint_byte) {
1432 data = BTRFS_BLOCK_GROUP_MIXED;
1433 }
1434
1435 /* for SSD, cluster allocations together as much as possible */
1436 if (btrfs_test_opt(root, SSD)) {
1437 if (data)
1438 last_ptr = &root->fs_info->last_data_alloc;
1439 else
1440 last_ptr = &root->fs_info->last_alloc;
1441 if (*last_ptr) {
1442 hint_byte = *last_ptr;
1443 }
1444 else {
1445 hint_byte = hint_byte &
1446 ~((u64)BTRFS_BLOCK_GROUP_SIZE - 1);
1447 empty_size += 16 * 1024 * 1024;
1448 }
1449 }
1450
1451 search_end = min(search_end,
1452 btrfs_super_total_bytes(&info->super_copy));
1453 if (hint_byte) {
1454 block_group = btrfs_lookup_block_group(info, hint_byte);
1455 if (!block_group)
1456 hint_byte = search_start;
1457 block_group = btrfs_find_block_group(root, block_group,
1458 hint_byte, data, 1);
1459 } else {
1460 block_group = btrfs_find_block_group(root,
1461 trans->block_group,
1462 search_start, data, 1);
1463 }
1464
1465 total_needed += empty_size;
1466 path = btrfs_alloc_path();
1467check_failed:
1468 if (!block_group) {
1469 block_group = btrfs_lookup_block_group(info, search_start);
1470 if (!block_group)
1471 block_group = btrfs_lookup_block_group(info,
1472 orig_search_start);
1473 }
1474 search_start = find_search_start(root, &block_group, search_start,
1475 total_needed, data);
1476
1477 if (btrfs_test_opt(root, SSD) && *last_ptr &&
1478 search_start != *last_ptr) {
1479 info->last_alloc = 0;
1480 if (!empty_size) {
1481 empty_size += 16 * 1024 * 1024;
1482 total_needed += empty_size;
1483 }
1484 search_start = find_search_start(root, &block_group,
1485 search_start, total_needed,
1486 data);
1487 }
1488
1489 search_start = stripe_align(root, search_start);
1490 cached_start = search_start;
1491 btrfs_init_path(path);
1492 ins->objectid = search_start;
1493 ins->offset = 0;
1494 start_found = 0;
1495 path->reada = 2;
1496
1497 ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
1498 if (ret < 0)
1499 goto error;
1500 ret = find_previous_extent(root, path);
1501 if (ret < 0)
1502 goto error;
1503 l = path->nodes[0];
1504 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
1505 while (1) {
1506 l = path->nodes[0];
1507 slot = path->slots[0];
1508 if (slot >= btrfs_header_nritems(l)) {
1509 ret = btrfs_next_leaf(root, path);
1510 if (ret == 0)
1511 continue;
1512 if (ret < 0)
1513 goto error;
1514
1515 search_start = max(search_start,
1516 block_group->key.objectid);
1517 if (!start_found) {
1518 aligned = stripe_align(root, search_start);
1519 ins->objectid = aligned;
1520 if (aligned >= search_end) {
1521 ret = -ENOSPC;
1522 goto error;
1523 }
1524 ins->offset = search_end - aligned;
1525 start_found = 1;
1526 goto check_pending;
1527 }
1528 ins->objectid = stripe_align(root,
1529 last_byte > search_start ?
1530 last_byte : search_start);
1531 if (search_end <= ins->objectid) {
1532 ret = -ENOSPC;
1533 goto error;
1534 }
1535 ins->offset = search_end - ins->objectid;
1536 BUG_ON(ins->objectid >= search_end);
1537 goto check_pending;
1538 }
1539 btrfs_item_key_to_cpu(l, &key, slot);
1540
1541 if (key.objectid >= search_start && key.objectid > last_byte &&
1542 start_found) {
1543 if (last_byte < search_start)
1544 last_byte = search_start;
1545 aligned = stripe_align(root, last_byte);
1546 hole_size = key.objectid - aligned;
1547 if (key.objectid > aligned && hole_size >= num_bytes) {
1548 ins->objectid = aligned;
1549 ins->offset = hole_size;
1550 goto check_pending;
1551 }
1552 }
1553 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
1554 if (!start_found && btrfs_key_type(&key) ==
1555 BTRFS_BLOCK_GROUP_ITEM_KEY) {
1556 last_byte = key.objectid;
1557 start_found = 1;
1558 }
1559 goto next;
1560 }
1561
1562
1563 start_found = 1;
1564 last_byte = key.objectid + key.offset;
1565
1566 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1567 last_byte >= block_group->key.objectid +
1568 block_group->key.offset) {
1569 btrfs_release_path(root, path);
1570 search_start = block_group->key.objectid +
1571 block_group->key.offset;
1572 goto new_group;
1573 }
1574next:
1575 path->slots[0]++;
1576 cond_resched();
1577 }
1578check_pending:
1579 /* we have to make sure we didn't find an extent that has already
1580 * been allocated by the map tree or the original allocation
1581 */
1582 btrfs_release_path(root, path);
1583 BUG_ON(ins->objectid < search_start);
1584
1585 if (ins->objectid + num_bytes >= search_end)
1586 goto enospc;
1587 if (!full_scan && data != BTRFS_BLOCK_GROUP_MIXED &&
1588 ins->objectid + num_bytes > block_group->
1589 key.objectid + block_group->key.offset) {
1590 search_start = block_group->key.objectid +
1591 block_group->key.offset;
1592 goto new_group;
1593 }
1594 if (test_range_bit(&info->extent_ins, ins->objectid,
1595 ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
1596 search_start = ins->objectid + num_bytes;
1597 goto new_group;
1598 }
1599 if (test_range_bit(&info->pinned_extents, ins->objectid,
1600 ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
1601 search_start = ins->objectid + num_bytes;
1602 goto new_group;
1603 }
1604 if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
1605 ins->objectid < exclude_start + exclude_nr)) {
1606 search_start = exclude_start + exclude_nr;
1607 goto new_group;
1608 }
1609 if (!data) {
1610 block_group = btrfs_lookup_block_group(info, ins->objectid);
1611 if (block_group)
1612 trans->block_group = block_group;
1613 }
1614 ins->offset = num_bytes;
1615 btrfs_free_path(path);
1616 if (btrfs_test_opt(root, SSD))
1617 *last_ptr = ins->objectid + ins->offset;
1618 return 0;
1619
1620new_group:
1621 if (search_start + num_bytes >= search_end) {
1622enospc:
1623 search_start = orig_search_start;
1624 if (full_scan) {
1625 ret = -ENOSPC;
1626 goto error;
1627 }
1628 if (wrapped) {
1629 if (!full_scan)
1630 total_needed -= empty_size;
1631 full_scan = 1;
1632 data = BTRFS_BLOCK_GROUP_MIXED;
1633 } else
1634 wrapped = 1;
1635 }
1636 block_group = btrfs_lookup_block_group(info, search_start);
1637 cond_resched();
1638 block_group = btrfs_find_block_group(root, block_group,
1639 search_start, data, 0);
1640 goto check_failed;
1641
1642error:
1643 btrfs_release_path(root, path);
1644 btrfs_free_path(path);
1645 return ret;
1646}
1647/*
1648 * finds a free extent and does all the dirty work required for allocation
1649 * returns the key for the extent through ins, and a tree buffer for
1650 * the first block of the extent through buf.
1651 *
1652 * returns 0 if everything worked, non-zero otherwise.
1653 */
1654int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
1655 struct btrfs_root *root,
1656 u64 num_bytes, u64 root_objectid, u64 ref_generation,
1657 u64 owner, u64 owner_offset,
1658 u64 empty_size, u64 hint_byte,
1659 u64 search_end, struct btrfs_key *ins, int data)
1660{
1661 int ret;
1662 int pending_ret;
1663 u64 super_used;
1664 u64 root_used;
1665 u64 search_start = 0;
1666 u64 new_hint;
1667 struct btrfs_fs_info *info = root->fs_info;
1668 struct btrfs_root *extent_root = info->extent_root;
1669 struct btrfs_extent_item extent_item;
1670 struct btrfs_path *path;
1671
1672 btrfs_set_stack_extent_refs(&extent_item, 1);
1673
1674 new_hint = max(hint_byte, root->fs_info->alloc_start);
1675 if (new_hint < btrfs_super_total_bytes(&info->super_copy))
1676 hint_byte = new_hint;
1677
1678 WARN_ON(num_bytes < root->sectorsize);
1679 ret = find_free_extent(trans, root, num_bytes, empty_size,
1680 search_start, search_end, hint_byte, ins,
1681 trans->alloc_exclude_start,
1682 trans->alloc_exclude_nr, data);
1683 BUG_ON(ret);
1684 if (ret)
1685 return ret;
1686
1687 /* block accounting for super block */
1688 super_used = btrfs_super_bytes_used(&info->super_copy);
1689 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1690
1691 /* block accounting for root item */
1692 root_used = btrfs_root_used(&root->root_item);
1693 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1694
1695 clear_extent_dirty(&root->fs_info->free_space_cache,
1696 ins->objectid, ins->objectid + ins->offset - 1,
1697 GFP_NOFS);
1698
1699 if (root == extent_root) {
1700 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1701 ins->objectid + ins->offset - 1,
1702 EXTENT_LOCKED, GFP_NOFS);
1703 WARN_ON(data == 1);
1704 goto update_block;
1705 }
1706
1707 WARN_ON(trans->alloc_exclude_nr);
1708 trans->alloc_exclude_start = ins->objectid;
1709 trans->alloc_exclude_nr = ins->offset;
1710 ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
1711 sizeof(extent_item));
1712
1713 trans->alloc_exclude_start = 0;
1714 trans->alloc_exclude_nr = 0;
1715 BUG_ON(ret);
1716
1717 path = btrfs_alloc_path();
1718 BUG_ON(!path);
1719 ret = btrfs_insert_extent_backref(trans, extent_root, path,
1720 ins->objectid, root_objectid,
1721 ref_generation, owner, owner_offset);
1722
1723 BUG_ON(ret);
1724 btrfs_free_path(path);
1725 finish_current_insert(trans, extent_root);
1726 pending_ret = del_pending_extents(trans, extent_root);
1727
1728 if (ret) {
1729 return ret;
1730 }
1731 if (pending_ret) {
1732 return pending_ret;
1733 }
1734
1735update_block:
1736 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1737 data);
1738 BUG_ON(ret);
1739 return 0;
1740}
1741
1742/*
1743 * helper function to allocate a block for a given tree
1744 * returns the tree buffer or NULL.
1745 */
1746struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1747 struct btrfs_root *root,
1748 u32 blocksize,
1749 u64 root_objectid, u64 hint,
1750 u64 empty_size)
1751{
1752 u64 ref_generation;
1753
1754 if (root->ref_cows)
1755 ref_generation = trans->transid;
1756 else
1757 ref_generation = 0;
1758
1759
1760 return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1761 ref_generation, 0, 0, hint, empty_size);
1762}
1763
1764/*
1765 * helper function to allocate a block for a given tree
1766 * returns the tree buffer or NULL.
1767 */
1768struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1769 struct btrfs_root *root,
1770 u32 blocksize,
1771 u64 root_objectid,
1772 u64 ref_generation,
1773 u64 first_objectid,
1774 int level,
1775 u64 hint,
1776 u64 empty_size)
1777{
1778 struct btrfs_key ins;
1779 int ret;
1780 struct extent_buffer *buf;
1781
1782 ret = btrfs_alloc_extent(trans, root, blocksize,
1783 root_objectid, ref_generation,
1784 level, first_objectid, empty_size, hint,
1785 (u64)-1, &ins, 0);
1786 if (ret) {
1787 BUG_ON(ret > 0);
1788 return ERR_PTR(ret);
1789 }
1790 buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1791 if (!buf) {
1792 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1793 root->root_key.objectid, ref_generation,
1794 0, 0, 0);
1795 return ERR_PTR(-ENOMEM);
1796 }
1797 btrfs_set_header_generation(buf, trans->transid);
1798 clean_tree_block(trans, root, buf);
1799 wait_on_tree_block_writeback(root, buf);
1800 btrfs_set_buffer_uptodate(buf);
1801
1802 if (PageDirty(buf->first_page)) {
1803 printk("page %lu dirty\n", buf->first_page->index);
1804 WARN_ON(1);
1805 }
1806
1807 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1808 buf->start + buf->len - 1, GFP_NOFS);
1809 set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->io_tree,
1810 buf->start, buf->start + buf->len - 1,
1811 EXTENT_CSUM, GFP_NOFS);
1812 buf->flags |= EXTENT_CSUM;
1813 if (!btrfs_test_opt(root, SSD))
1814 btrfs_set_buffer_defrag(buf);
1815 trans->blocks_used++;
1816 return buf;
1817}
1818
1819static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1820 struct btrfs_root *root,
1821 struct extent_buffer *leaf)
1822{
1823 u64 leaf_owner;
1824 u64 leaf_generation;
1825 struct btrfs_key key;
1826 struct btrfs_file_extent_item *fi;
1827 int i;
1828 int nritems;
1829 int ret;
1830
1831 BUG_ON(!btrfs_is_leaf(leaf));
1832 nritems = btrfs_header_nritems(leaf);
1833 leaf_owner = btrfs_header_owner(leaf);
1834 leaf_generation = btrfs_header_generation(leaf);
1835
1836 for (i = 0; i < nritems; i++) {
1837 u64 disk_bytenr;
1838
1839 btrfs_item_key_to_cpu(leaf, &key, i);
1840 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1841 continue;
1842 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1843 if (btrfs_file_extent_type(leaf, fi) ==
1844 BTRFS_FILE_EXTENT_INLINE)
1845 continue;
1846 /*
1847 * FIXME make sure to insert a trans record that
1848 * repeats the snapshot del on crash
1849 */
1850 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1851 if (disk_bytenr == 0)
1852 continue;
1853 ret = btrfs_free_extent(trans, root, disk_bytenr,
1854 btrfs_file_extent_disk_num_bytes(leaf, fi),
1855 leaf_owner, leaf_generation,
1856 key.objectid, key.offset, 0);
1857 BUG_ON(ret);
1858 }
1859 return 0;
1860}
1861
1862static void noinline reada_walk_down(struct btrfs_root *root,
1863 struct extent_buffer *node,
1864 int slot)
1865{
1866 u64 bytenr;
1867 u64 last = 0;
1868 u32 nritems;
1869 u32 refs;
1870 u32 blocksize;
1871 int ret;
1872 int i;
1873 int level;
1874 int skipped = 0;
1875
1876 nritems = btrfs_header_nritems(node);
1877 level = btrfs_header_level(node);
1878 if (level)
1879 return;
1880
1881 for (i = slot; i < nritems && skipped < 32; i++) {
1882 bytenr = btrfs_node_blockptr(node, i);
1883 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
1884 (last > bytenr && last - bytenr > 32 * 1024))) {
1885 skipped++;
1886 continue;
1887 }
1888 blocksize = btrfs_level_size(root, level - 1);
1889 if (i != slot) {
1890 ret = lookup_extent_ref(NULL, root, bytenr,
1891 blocksize, &refs);
1892 BUG_ON(ret);
1893 if (refs != 1) {
1894 skipped++;
1895 continue;
1896 }
1897 }
1898 mutex_unlock(&root->fs_info->fs_mutex);
1899 ret = readahead_tree_block(root, bytenr, blocksize);
1900 last = bytenr + blocksize;
1901 cond_resched();
1902 mutex_lock(&root->fs_info->fs_mutex);
1903 if (ret)
1904 break;
1905 }
1906}
1907
1908/*
1909 * helper function for drop_snapshot, this walks down the tree dropping ref
1910 * counts as it goes.
1911 */
1912static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1913 struct btrfs_root *root,
1914 struct btrfs_path *path, int *level)
1915{
1916 u64 root_owner;
1917 u64 root_gen;
1918 u64 bytenr;
1919 struct extent_buffer *next;
1920 struct extent_buffer *cur;
1921 struct extent_buffer *parent;
1922 u32 blocksize;
1923 int ret;
1924 u32 refs;
1925
1926 WARN_ON(*level < 0);
1927 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1928 ret = lookup_extent_ref(trans, root,
1929 path->nodes[*level]->start,
1930 path->nodes[*level]->len, &refs);
1931 BUG_ON(ret);
1932 if (refs > 1)
1933 goto out;
1934
1935 /*
1936 * walk down to the last node level and free all the leaves
1937 */
1938 while(*level >= 0) {
1939 WARN_ON(*level < 0);
1940 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1941 cur = path->nodes[*level];
1942
1943 if (btrfs_header_level(cur) != *level)
1944 WARN_ON(1);
1945
1946 if (path->slots[*level] >=
1947 btrfs_header_nritems(cur))
1948 break;
1949 if (*level == 0) {
1950 ret = drop_leaf_ref(trans, root, cur);
1951 BUG_ON(ret);
1952 break;
1953 }
1954 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1955 blocksize = btrfs_level_size(root, *level - 1);
1956 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1957 BUG_ON(ret);
1958 if (refs != 1) {
1959 parent = path->nodes[*level];
1960 root_owner = btrfs_header_owner(parent);
1961 root_gen = btrfs_header_generation(parent);
1962 path->slots[*level]++;
1963 ret = btrfs_free_extent(trans, root, bytenr,
1964 blocksize, root_owner,
1965 root_gen, 0, 0, 1);
1966 BUG_ON(ret);
1967 continue;
1968 }
1969 next = btrfs_find_tree_block(root, bytenr, blocksize);
1970 if (!next || !btrfs_buffer_uptodate(next)) {
1971 free_extent_buffer(next);
1972 reada_walk_down(root, cur, path->slots[*level]);
1973 mutex_unlock(&root->fs_info->fs_mutex);
1974 next = read_tree_block(root, bytenr, blocksize);
1975 mutex_lock(&root->fs_info->fs_mutex);
1976
1977 /* we dropped the lock, check one more time */
1978 ret = lookup_extent_ref(trans, root, bytenr,
1979 blocksize, &refs);
1980 BUG_ON(ret);
1981 if (refs != 1) {
1982 parent = path->nodes[*level];
1983 root_owner = btrfs_header_owner(parent);
1984 root_gen = btrfs_header_generation(parent);
1985
1986 path->slots[*level]++;
1987 free_extent_buffer(next);
1988 ret = btrfs_free_extent(trans, root, bytenr,
1989 blocksize,
1990 root_owner,
1991 root_gen, 0, 0, 1);
1992 BUG_ON(ret);
1993 continue;
1994 }
1995 }
1996 WARN_ON(*level <= 0);
1997 if (path->nodes[*level-1])
1998 free_extent_buffer(path->nodes[*level-1]);
1999 path->nodes[*level-1] = next;
2000 *level = btrfs_header_level(next);
2001 path->slots[*level] = 0;
2002 }
2003out:
2004 WARN_ON(*level < 0);
2005 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2006
2007 if (path->nodes[*level] == root->node) {
2008 root_owner = root->root_key.objectid;
2009 parent = path->nodes[*level];
2010 } else {
2011 parent = path->nodes[*level + 1];
2012 root_owner = btrfs_header_owner(parent);
2013 }
2014
2015 root_gen = btrfs_header_generation(parent);
2016 ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
2017 path->nodes[*level]->len,
2018 root_owner, root_gen, 0, 0, 1);
2019 free_extent_buffer(path->nodes[*level]);
2020 path->nodes[*level] = NULL;
2021 *level += 1;
2022 BUG_ON(ret);
2023 return 0;
2024}
2025
2026/*
2027 * helper for dropping snapshots. This walks back up the tree in the path
2028 * to find the first node higher up where we haven't yet gone through
2029 * all the slots
2030 */
2031static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2032 struct btrfs_root *root,
2033 struct btrfs_path *path, int *level)
2034{
2035 u64 root_owner;
2036 u64 root_gen;
2037 struct btrfs_root_item *root_item = &root->root_item;
2038 int i;
2039 int slot;
2040 int ret;
2041
2042 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2043 slot = path->slots[i];
2044 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2045 struct extent_buffer *node;
2046 struct btrfs_disk_key disk_key;
2047 node = path->nodes[i];
2048 path->slots[i]++;
2049 *level = i;
2050 WARN_ON(*level == 0);
2051 btrfs_node_key(node, &disk_key, path->slots[i]);
2052 memcpy(&root_item->drop_progress,
2053 &disk_key, sizeof(disk_key));
2054 root_item->drop_level = i;
2055 return 0;
2056 } else {
2057 if (path->nodes[*level] == root->node) {
2058 root_owner = root->root_key.objectid;
2059 root_gen =
2060 btrfs_header_generation(path->nodes[*level]);
2061 } else {
2062 struct extent_buffer *node;
2063 node = path->nodes[*level + 1];
2064 root_owner = btrfs_header_owner(node);
2065 root_gen = btrfs_header_generation(node);
2066 }
2067 ret = btrfs_free_extent(trans, root,
2068 path->nodes[*level]->start,
2069 path->nodes[*level]->len,
2070 root_owner, root_gen, 0, 0, 1);
2071 BUG_ON(ret);
2072 free_extent_buffer(path->nodes[*level]);
2073 path->nodes[*level] = NULL;
2074 *level = i + 1;
2075 }
2076 }
2077 return 1;
2078}
2079
2080/*
2081 * drop the reference count on the tree rooted at 'snap'. This traverses
2082 * the tree freeing any blocks that have a ref count of zero after being
2083 * decremented.
2084 */
2085int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2086 *root)
2087{
2088 int ret = 0;
2089 int wret;
2090 int level;
2091 struct btrfs_path *path;
2092 int i;
2093 int orig_level;
2094 struct btrfs_root_item *root_item = &root->root_item;
2095
2096 path = btrfs_alloc_path();
2097 BUG_ON(!path);
2098
2099 level = btrfs_header_level(root->node);
2100 orig_level = level;
2101 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2102 path->nodes[level] = root->node;
2103 extent_buffer_get(root->node);
2104 path->slots[level] = 0;
2105 } else {
2106 struct btrfs_key key;
2107 struct btrfs_disk_key found_key;
2108 struct extent_buffer *node;
2109
2110 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2111 level = root_item->drop_level;
2112 path->lowest_level = level;
2113 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2114 if (wret < 0) {
2115 ret = wret;
2116 goto out;
2117 }
2118 node = path->nodes[level];
2119 btrfs_node_key(node, &found_key, path->slots[level]);
2120 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2121 sizeof(found_key)));
2122 }
2123 while(1) {
2124 wret = walk_down_tree(trans, root, path, &level);
2125 if (wret > 0)
2126 break;
2127 if (wret < 0)
2128 ret = wret;
2129
2130 wret = walk_up_tree(trans, root, path, &level);
2131 if (wret > 0)
2132 break;
2133 if (wret < 0)
2134 ret = wret;
2135 ret = -EAGAIN;
2136 break;
2137 }
2138 for (i = 0; i <= orig_level; i++) {
2139 if (path->nodes[i]) {
2140 free_extent_buffer(path->nodes[i]);
2141 path->nodes[i] = NULL;
2142 }
2143 }
2144out:
2145 btrfs_free_path(path);
2146 return ret;
2147}
2148
2149int btrfs_free_block_groups(struct btrfs_fs_info *info)
2150{
2151 u64 start;
2152 u64 end;
2153 u64 ptr;
2154 int ret;
2155 while(1) {
2156 ret = find_first_extent_bit(&info->block_group_cache, 0,
2157 &start, &end, (unsigned int)-1);
2158 if (ret)
2159 break;
2160 ret = get_state_private(&info->block_group_cache, start, &ptr);
2161 if (!ret)
2162 kfree((void *)(unsigned long)ptr);
2163 clear_extent_bits(&info->block_group_cache, start,
2164 end, (unsigned int)-1, GFP_NOFS);
2165 }
2166 while(1) {
2167 ret = find_first_extent_bit(&info->free_space_cache, 0,
2168 &start, &end, EXTENT_DIRTY);
2169 if (ret)
2170 break;
2171 clear_extent_dirty(&info->free_space_cache, start,
2172 end, GFP_NOFS);
2173 }
2174 return 0;
2175}
2176
2177static int noinline relocate_inode_pages(struct inode *inode, u64 start,
2178 u64 len)
2179{
2180 u64 page_start;
2181 u64 page_end;
2182 u64 delalloc_start;
2183 u64 existing_delalloc;
2184 unsigned long last_index;
2185 unsigned long i;
2186 struct page *page;
2187 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2188 struct file_ra_state *ra;
2189
2190 ra = kzalloc(sizeof(*ra), GFP_NOFS);
2191
2192 mutex_lock(&inode->i_mutex);
2193 i = start >> PAGE_CACHE_SHIFT;
2194 last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
2195
2196 file_ra_state_init(ra, inode->i_mapping);
2197 btrfs_force_ra(inode->i_mapping, ra, NULL, i, last_index);
2198 kfree(ra);
2199
2200 for (; i <= last_index; i++) {
2201 page = grab_cache_page(inode->i_mapping, i);
2202 if (!page)
2203 goto out_unlock;
2204 if (!PageUptodate(page)) {
2205 btrfs_readpage(NULL, page);
2206 lock_page(page);
2207 if (!PageUptodate(page)) {
2208 unlock_page(page);
2209 page_cache_release(page);
2210 goto out_unlock;
2211 }
2212 }
2213 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
2214 page_end = page_start + PAGE_CACHE_SIZE - 1;
2215
2216 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2217
2218 delalloc_start = page_start;
2219 existing_delalloc = count_range_bits(io_tree,
2220 &delalloc_start, page_end,
2221 PAGE_CACHE_SIZE, EXTENT_DELALLOC);
2222
2223 set_extent_delalloc(io_tree, page_start,
2224 page_end, GFP_NOFS);
2225
2226 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2227 set_page_dirty(page);
2228 unlock_page(page);
2229 page_cache_release(page);
2230 }
2231
2232out_unlock:
2233 mutex_unlock(&inode->i_mutex);
2234 return 0;
2235}
2236
2237/*
2238 * note, this releases the path
2239 */
2240static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2241 struct btrfs_path *path,
2242 struct btrfs_key *extent_key)
2243{
2244 struct inode *inode;
2245 struct btrfs_root *found_root;
2246 struct btrfs_key *root_location;
2247 struct btrfs_extent_ref *ref;
2248 u64 ref_root;
2249 u64 ref_gen;
2250 u64 ref_objectid;
2251 u64 ref_offset;
2252 int ret;
2253
2254 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
2255 struct btrfs_extent_ref);
2256 ref_root = btrfs_ref_root(path->nodes[0], ref);
2257 ref_gen = btrfs_ref_generation(path->nodes[0], ref);
2258 ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
2259 ref_offset = btrfs_ref_offset(path->nodes[0], ref);
2260 btrfs_release_path(extent_root, path);
2261
2262 root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
2263 root_location->objectid = ref_root;
2264 if (ref_gen == 0)
2265 root_location->offset = 0;
2266 else
2267 root_location->offset = (u64)-1;
2268 root_location->type = BTRFS_ROOT_ITEM_KEY;
2269
2270 found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2271 root_location);
2272 BUG_ON(!found_root);
2273 kfree(root_location);
2274
2275 if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2276 mutex_unlock(&extent_root->fs_info->fs_mutex);
2277 inode = btrfs_iget_locked(extent_root->fs_info->sb,
2278 ref_objectid, found_root);
2279 if (inode->i_state & I_NEW) {
2280 /* the inode and parent dir are two different roots */
2281 BTRFS_I(inode)->root = found_root;
2282 BTRFS_I(inode)->location.objectid = ref_objectid;
2283 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
2284 BTRFS_I(inode)->location.offset = 0;
2285 btrfs_read_locked_inode(inode);
2286 unlock_new_inode(inode);
2287
2288 }
2289 /* this can happen if the reference is not against
2290 * the latest version of the tree root
2291 */
2292 if (is_bad_inode(inode)) {
2293 mutex_lock(&extent_root->fs_info->fs_mutex);
2294 goto out;
2295 }
2296 relocate_inode_pages(inode, ref_offset, extent_key->offset);
2297 /* FIXME, data=ordered will help get rid of this */
2298 filemap_fdatawrite(inode->i_mapping);
2299 iput(inode);
2300 mutex_lock(&extent_root->fs_info->fs_mutex);
2301 } else {
2302 struct btrfs_trans_handle *trans;
2303 struct btrfs_key found_key;
2304 struct extent_buffer *eb;
2305 int level;
2306 int i;
2307
2308 trans = btrfs_start_transaction(found_root, 1);
2309 eb = read_tree_block(found_root, extent_key->objectid,
2310 extent_key->offset);
2311 level = btrfs_header_level(eb);
2312
2313 if (level == 0)
2314 btrfs_item_key_to_cpu(eb, &found_key, 0);
2315 else
2316 btrfs_node_key_to_cpu(eb, &found_key, 0);
2317
2318 free_extent_buffer(eb);
2319
2320 path->lowest_level = level;
2321 path->reada = 2;
2322 ret = btrfs_search_slot(trans, found_root, &found_key, path,
2323 0, 1);
2324 path->lowest_level = 0;
2325 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2326 if (!path->nodes[i])
2327 break;
2328 free_extent_buffer(path->nodes[i]);
2329 path->nodes[i] = NULL;
2330 }
2331 btrfs_release_path(found_root, path);
2332 btrfs_end_transaction(trans, found_root);
2333 }
2334
2335out:
2336 return 0;
2337}
2338
2339static int noinline relocate_one_extent(struct btrfs_root *extent_root,
2340 struct btrfs_path *path,
2341 struct btrfs_key *extent_key)
2342{
2343 struct btrfs_key key;
2344 struct btrfs_key found_key;
2345 struct extent_buffer *leaf;
2346 u32 nritems;
2347 u32 item_size;
2348 int ret = 0;
2349
2350 key.objectid = extent_key->objectid;
2351 key.type = BTRFS_EXTENT_REF_KEY;
2352 key.offset = 0;
2353
2354 while(1) {
2355 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2356
2357 if (ret < 0)
2358 goto out;
2359
2360 ret = 0;
2361 leaf = path->nodes[0];
2362 nritems = btrfs_header_nritems(leaf);
2363 if (path->slots[0] == nritems)
2364 goto out;
2365
2366 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2367 if (found_key.objectid != extent_key->objectid)
2368 break;
2369
2370 if (found_key.type != BTRFS_EXTENT_REF_KEY)
2371 break;
2372
2373 key.offset = found_key.offset + 1;
2374 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2375
2376 ret = relocate_one_reference(extent_root, path, extent_key);
2377 if (ret)
2378 goto out;
2379 }
2380 ret = 0;
2381out:
2382 btrfs_release_path(extent_root, path);
2383 return ret;
2384}
2385
2386int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 new_size)
2387{
2388 struct btrfs_trans_handle *trans;
2389 struct btrfs_root *tree_root = root->fs_info->tree_root;
2390 struct btrfs_path *path;
2391 u64 cur_byte;
2392 u64 total_found;
2393 struct btrfs_fs_info *info = root->fs_info;
2394 struct extent_io_tree *block_group_cache;
2395 struct btrfs_key key;
2396 struct btrfs_key found_key;
2397 struct extent_buffer *leaf;
2398 u32 nritems;
2399 int ret;
2400 int progress = 0;
2401
2402 btrfs_set_super_total_bytes(&info->super_copy, new_size);
2403 clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
2404 GFP_NOFS);
2405 block_group_cache = &info->block_group_cache;
2406 path = btrfs_alloc_path();
2407 root = root->fs_info->extent_root;
2408 path->reada = 2;
2409
2410again:
2411 total_found = 0;
2412 key.objectid = new_size;
2413 key.offset = 0;
2414 key.type = 0;
2415 cur_byte = key.objectid;
2416
2417 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2418 if (ret < 0)
2419 goto out;
2420
2421 ret = find_previous_extent(root, path);
2422 if (ret < 0)
2423 goto out;
2424 if (ret == 0) {
2425 leaf = path->nodes[0];
2426 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2427 if (found_key.objectid + found_key.offset > new_size) {
2428 cur_byte = found_key.objectid;
2429 key.objectid = cur_byte;
2430 }
2431 }
2432 btrfs_release_path(root, path);
2433
2434 while(1) {
2435 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2436 if (ret < 0)
2437 goto out;
2438
2439 leaf = path->nodes[0];
2440 nritems = btrfs_header_nritems(leaf);
2441next:
2442 if (path->slots[0] >= nritems) {
2443 ret = btrfs_next_leaf(root, path);
2444 if (ret < 0)
2445 goto out;
2446 if (ret == 1) {
2447 ret = 0;
2448 break;
2449 }
2450 leaf = path->nodes[0];
2451 nritems = btrfs_header_nritems(leaf);
2452 }
2453
2454 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2455
2456 if (progress && need_resched()) {
2457 memcpy(&key, &found_key, sizeof(key));
2458 mutex_unlock(&root->fs_info->fs_mutex);
2459 cond_resched();
2460 mutex_lock(&root->fs_info->fs_mutex);
2461 btrfs_release_path(root, path);
2462 btrfs_search_slot(NULL, root, &key, path, 0, 0);
2463 progress = 0;
2464 goto next;
2465 }
2466 progress = 1;
2467
2468 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
2469 found_key.objectid + found_key.offset <= cur_byte) {
2470 path->slots[0]++;
2471 goto next;
2472 }
2473
2474 total_found++;
2475 cur_byte = found_key.objectid + found_key.offset;
2476 key.objectid = cur_byte;
2477 btrfs_release_path(root, path);
2478 ret = relocate_one_extent(root, path, &found_key);
2479 }
2480
2481 btrfs_release_path(root, path);
2482
2483 if (total_found > 0) {
2484 trans = btrfs_start_transaction(tree_root, 1);
2485 btrfs_commit_transaction(trans, tree_root);
2486
2487 mutex_unlock(&root->fs_info->fs_mutex);
2488 btrfs_clean_old_snapshots(tree_root);
2489 mutex_lock(&root->fs_info->fs_mutex);
2490
2491 trans = btrfs_start_transaction(tree_root, 1);
2492 btrfs_commit_transaction(trans, tree_root);
2493 goto again;
2494 }
2495
2496 trans = btrfs_start_transaction(root, 1);
2497 key.objectid = new_size;
2498 key.offset = 0;
2499 key.type = 0;
2500 while(1) {
2501 u64 ptr;
2502
2503 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
2504 if (ret < 0)
2505 goto out;
2506
2507 leaf = path->nodes[0];
2508 nritems = btrfs_header_nritems(leaf);
2509bg_next:
2510 if (path->slots[0] >= nritems) {
2511 ret = btrfs_next_leaf(root, path);
2512 if (ret < 0)
2513 break;
2514 if (ret == 1) {
2515 ret = 0;
2516 break;
2517 }
2518 leaf = path->nodes[0];
2519 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2520
2521 /*
2522 * btrfs_next_leaf doesn't cow buffers, we have to
2523 * do the search again
2524 */
2525 memcpy(&key, &found_key, sizeof(key));
2526 btrfs_release_path(root, path);
2527 goto resched_check;
2528 }
2529
2530 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2531 if (btrfs_key_type(&found_key) != BTRFS_BLOCK_GROUP_ITEM_KEY) {
2532 printk("shrinker found key %Lu %u %Lu\n",
2533 found_key.objectid, found_key.type,
2534 found_key.offset);
2535 path->slots[0]++;
2536 goto bg_next;
2537 }
2538 ret = get_state_private(&info->block_group_cache,
2539 found_key.objectid, &ptr);
2540 if (!ret)
2541 kfree((void *)(unsigned long)ptr);
2542
2543 clear_extent_bits(&info->block_group_cache, found_key.objectid,
2544 found_key.objectid + found_key.offset - 1,
2545 (unsigned int)-1, GFP_NOFS);
2546
2547 key.objectid = found_key.objectid + 1;
2548 btrfs_del_item(trans, root, path);
2549 btrfs_release_path(root, path);
2550resched_check:
2551 if (need_resched()) {
2552 mutex_unlock(&root->fs_info->fs_mutex);
2553 cond_resched();
2554 mutex_lock(&root->fs_info->fs_mutex);
2555 }
2556 }
2557 clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
2558 GFP_NOFS);
2559 btrfs_commit_transaction(trans, root);
2560out:
2561 btrfs_free_path(path);
2562 return ret;
2563}
2564
2565int btrfs_grow_extent_tree(struct btrfs_trans_handle *trans,
2566 struct btrfs_root *root, u64 new_size)
2567{
2568 struct btrfs_path *path;
2569 u64 nr = 0;
2570 u64 cur_byte;
2571 u64 old_size;
2572 unsigned long rem;
2573 struct btrfs_block_group_cache *cache;
2574 struct btrfs_block_group_item *item;
2575 struct btrfs_fs_info *info = root->fs_info;
2576 struct extent_io_tree *block_group_cache;
2577 struct btrfs_key key;
2578 struct extent_buffer *leaf;
2579 int ret;
2580 int bit;
2581
2582 old_size = btrfs_super_total_bytes(&info->super_copy);
2583 block_group_cache = &info->block_group_cache;
2584
2585 root = info->extent_root;
2586
2587 cache = btrfs_lookup_block_group(root->fs_info, old_size - 1);
2588
2589 cur_byte = cache->key.objectid + cache->key.offset;
2590 if (cur_byte >= new_size)
2591 goto set_size;
2592
2593 key.offset = BTRFS_BLOCK_GROUP_SIZE;
2594 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2595
2596 path = btrfs_alloc_path();
2597 if (!path)
2598 return -ENOMEM;
2599
2600 while(cur_byte < new_size) {
2601 key.objectid = cur_byte;
2602 ret = btrfs_insert_empty_item(trans, root, path, &key,
2603 sizeof(struct btrfs_block_group_item));
2604 BUG_ON(ret);
2605 leaf = path->nodes[0];
2606 item = btrfs_item_ptr(leaf, path->slots[0],
2607 struct btrfs_block_group_item);
2608
2609 btrfs_set_disk_block_group_used(leaf, item, 0);
2610 div_long_long_rem(nr, 3, &rem);
2611 if (rem) {
2612 btrfs_set_disk_block_group_flags(leaf, item,
2613 BTRFS_BLOCK_GROUP_DATA);
2614 } else {
2615 btrfs_set_disk_block_group_flags(leaf, item, 0);
2616 }
2617 nr++;
2618
2619 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2620 BUG_ON(!cache);
2621
2622 read_extent_buffer(leaf, &cache->item, (unsigned long)item,
2623 sizeof(cache->item));
2624
2625 memcpy(&cache->key, &key, sizeof(key));
2626 cache->cached = 0;
2627 cache->pinned = 0;
2628 cur_byte = key.objectid + key.offset;
2629 btrfs_release_path(root, path);
2630
2631 if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2632 bit = BLOCK_GROUP_DATA;
2633 cache->data = BTRFS_BLOCK_GROUP_DATA;
2634 } else {
2635 bit = BLOCK_GROUP_METADATA;
2636 cache->data = 0;
2637 }
2638
2639 /* use EXTENT_LOCKED to prevent merging */
2640 set_extent_bits(block_group_cache, key.objectid,
2641 key.objectid + key.offset - 1,
2642 bit | EXTENT_LOCKED, GFP_NOFS);
2643 set_state_private(block_group_cache, key.objectid,
2644 (unsigned long)cache);
2645 }
2646 btrfs_free_path(path);
2647set_size:
2648 btrfs_set_super_total_bytes(&info->super_copy, new_size);
2649 return 0;
2650}
2651
2652int btrfs_read_block_groups(struct btrfs_root *root)
2653{
2654 struct btrfs_path *path;
2655 int ret;
2656 int err = 0;
2657 int bit;
2658 struct btrfs_block_group_cache *cache;
2659 struct btrfs_fs_info *info = root->fs_info;
2660 struct extent_io_tree *block_group_cache;
2661 struct btrfs_key key;
2662 struct btrfs_key found_key;
2663 struct extent_buffer *leaf;
2664
2665 block_group_cache = &info->block_group_cache;
2666
2667 root = info->extent_root;
2668 key.objectid = 0;
2669 key.offset = BTRFS_BLOCK_GROUP_SIZE;
2670 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2671
2672 path = btrfs_alloc_path();
2673 if (!path)
2674 return -ENOMEM;
2675
2676 while(1) {
2677 ret = btrfs_search_slot(NULL, info->extent_root,
2678 &key, path, 0, 0);
2679 if (ret != 0) {
2680 err = ret;
2681 break;
2682 }
2683 leaf = path->nodes[0];
2684 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2685 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2686 if (!cache) {
2687 err = -1;
2688 break;
2689 }
2690
2691 read_extent_buffer(leaf, &cache->item,
2692 btrfs_item_ptr_offset(leaf, path->slots[0]),
2693 sizeof(cache->item));
2694 memcpy(&cache->key, &found_key, sizeof(found_key));
2695 cache->cached = 0;
2696 cache->pinned = 0;
2697 key.objectid = found_key.objectid + found_key.offset;
2698 btrfs_release_path(root, path);
2699
2700 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
2701 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
2702 cache->data = BTRFS_BLOCK_GROUP_MIXED;
2703 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2704 bit = BLOCK_GROUP_DATA;
2705 cache->data = BTRFS_BLOCK_GROUP_DATA;
2706 } else {
2707 bit = BLOCK_GROUP_METADATA;
2708 cache->data = 0;
2709 }
2710
2711 /* use EXTENT_LOCKED to prevent merging */
2712 set_extent_bits(block_group_cache, found_key.objectid,
2713 found_key.objectid + found_key.offset - 1,
2714 bit | EXTENT_LOCKED, GFP_NOFS);
2715 set_state_private(block_group_cache, found_key.objectid,
2716 (unsigned long)cache);
2717
2718 if (key.objectid >=
2719 btrfs_super_total_bytes(&info->super_copy))
2720 break;
2721 }
2722
2723 btrfs_free_path(path);
2724 return 0;
2725}
Linux 6.x block layer and io_uring tree(s)