projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Btrfs: Insert extent record and the first backref in a single balance
[deliverable/linux.git] / fs / btrfs / extent-tree.c
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
32 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
33 btrfs_root *extent_root);
34 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
35 btrfs_root *extent_root);
36 static 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
59 static 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 }
138 next:
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;
152 err:
153 btrfs_free_path(path);
154 return 0;
155 }
156
157 struct 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 }
185 static 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);
202 again:
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 }
232 out:
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
242 new_group:
243 last = cache->key.objectid + cache->key.offset;
244 wrapped:
245 cache = btrfs_lookup_block_group(root->fs_info, last);
246 if (!cache || cache->key.objectid >= total_fs_bytes) {
247 no_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
269 static 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
278 struct 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 }
346 again:
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 }
385 found:
386 return found_group;
387 }
388
389 static 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
410 static 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
426 static 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 }
488 out:
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 */
580 int 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]);
621 out:
622 btrfs_release_path(root, path);
623 return ret;
624 }
625
626 int 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
676 int 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
684 static 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);
712 out:
713 btrfs_free_path(path);
714 return 0;
715 }
716
717 u32 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();
738 again:
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
803 out:
804 btrfs_free_path(path);
805 return total_count;
806 }
807 int 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
833 int 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;
887 fail:
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
919 static 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);
940 fail:
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
951 int 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
1000 static 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 }
1078 static 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
1110 int 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
1129 int 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
1151 static 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
1200 static 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 */
1235 static 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 */
1325 static 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 */
1359 int 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
1383 static 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 */
1398 static 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();
1467 check_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 }
1574 next:
1575 path->slots[0]++;
1576 cond_resched();
1577 }
1578 check_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
1620 new_group:
1621 if (search_start + num_bytes >= search_end) {
1622 enospc:
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
1642 error:
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 */
1654 int 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 u32 sizes[2];
1668 struct btrfs_fs_info *info = root->fs_info;
1669 struct btrfs_root *extent_root = info->extent_root;
1670 struct btrfs_extent_item *extent_item;
1671 struct btrfs_extent_ref *ref;
1672 struct btrfs_path *path;
1673 struct btrfs_key keys[2];
1674
1675 new_hint = max(hint_byte, root->fs_info->alloc_start);
1676 if (new_hint < btrfs_super_total_bytes(&info->super_copy))
1677 hint_byte = new_hint;
1678
1679 WARN_ON(num_bytes < root->sectorsize);
1680 ret = find_free_extent(trans, root, num_bytes, empty_size,
1681 search_start, search_end, hint_byte, ins,
1682 trans->alloc_exclude_start,
1683 trans->alloc_exclude_nr, data);
1684 BUG_ON(ret);
1685 if (ret)
1686 return ret;
1687
1688 /* block accounting for super block */
1689 super_used = btrfs_super_bytes_used(&info->super_copy);
1690 btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
1691
1692 /* block accounting for root item */
1693 root_used = btrfs_root_used(&root->root_item);
1694 btrfs_set_root_used(&root->root_item, root_used + num_bytes);
1695
1696 clear_extent_dirty(&root->fs_info->free_space_cache,
1697 ins->objectid, ins->objectid + ins->offset - 1,
1698 GFP_NOFS);
1699
1700 if (root == extent_root) {
1701 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
1702 ins->objectid + ins->offset - 1,
1703 EXTENT_LOCKED, GFP_NOFS);
1704 WARN_ON(data == 1);
1705 goto update_block;
1706 }
1707
1708 WARN_ON(trans->alloc_exclude_nr);
1709 trans->alloc_exclude_start = ins->objectid;
1710 trans->alloc_exclude_nr = ins->offset;
1711
1712 memcpy(&keys[0], ins, sizeof(*ins));
1713 keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
1714 owner, owner_offset);
1715 keys[1].objectid = ins->objectid;
1716 keys[1].type = BTRFS_EXTENT_REF_KEY;
1717 sizes[0] = sizeof(*extent_item);
1718 sizes[1] = sizeof(*ref);
1719
1720 path = btrfs_alloc_path();
1721 BUG_ON(!path);
1722
1723 ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
1724 sizes, 2);
1725
1726 BUG_ON(ret);
1727 extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1728 struct btrfs_extent_item);
1729 btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
1730 ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
1731 struct btrfs_extent_ref);
1732
1733 btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
1734 btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
1735 btrfs_set_ref_objectid(path->nodes[0], ref, owner);
1736 btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
1737
1738 btrfs_mark_buffer_dirty(path->nodes[0]);
1739
1740 trans->alloc_exclude_start = 0;
1741 trans->alloc_exclude_nr = 0;
1742 btrfs_free_path(path);
1743 finish_current_insert(trans, extent_root);
1744 pending_ret = del_pending_extents(trans, extent_root);
1745
1746 if (ret) {
1747 return ret;
1748 }
1749 if (pending_ret) {
1750 return pending_ret;
1751 }
1752
1753 update_block:
1754 ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
1755 data);
1756 BUG_ON(ret);
1757 return 0;
1758 }
1759
1760 /*
1761 * helper function to allocate a block for a given tree
1762 * returns the tree buffer or NULL.
1763 */
1764 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1765 struct btrfs_root *root,
1766 u32 blocksize,
1767 u64 root_objectid, u64 hint,
1768 u64 empty_size)
1769 {
1770 u64 ref_generation;
1771
1772 if (root->ref_cows)
1773 ref_generation = trans->transid;
1774 else
1775 ref_generation = 0;
1776
1777
1778 return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
1779 ref_generation, 0, 0, hint, empty_size);
1780 }
1781
1782 /*
1783 * helper function to allocate a block for a given tree
1784 * returns the tree buffer or NULL.
1785 */
1786 struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
1787 struct btrfs_root *root,
1788 u32 blocksize,
1789 u64 root_objectid,
1790 u64 ref_generation,
1791 u64 first_objectid,
1792 int level,
1793 u64 hint,
1794 u64 empty_size)
1795 {
1796 struct btrfs_key ins;
1797 int ret;
1798 struct extent_buffer *buf;
1799
1800 ret = btrfs_alloc_extent(trans, root, blocksize,
1801 root_objectid, ref_generation,
1802 level, first_objectid, empty_size, hint,
1803 (u64)-1, &ins, 0);
1804 if (ret) {
1805 BUG_ON(ret > 0);
1806 return ERR_PTR(ret);
1807 }
1808 buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
1809 if (!buf) {
1810 btrfs_free_extent(trans, root, ins.objectid, blocksize,
1811 root->root_key.objectid, ref_generation,
1812 0, 0, 0);
1813 return ERR_PTR(-ENOMEM);
1814 }
1815 btrfs_set_header_generation(buf, trans->transid);
1816 clean_tree_block(trans, root, buf);
1817 wait_on_tree_block_writeback(root, buf);
1818 btrfs_set_buffer_uptodate(buf);
1819
1820 if (PageDirty(buf->first_page)) {
1821 printk("page %lu dirty\n", buf->first_page->index);
1822 WARN_ON(1);
1823 }
1824
1825 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
1826 buf->start + buf->len - 1, GFP_NOFS);
1827 set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->io_tree,
1828 buf->start, buf->start + buf->len - 1,
1829 EXTENT_CSUM, GFP_NOFS);
1830 buf->flags |= EXTENT_CSUM;
1831 if (!btrfs_test_opt(root, SSD))
1832 btrfs_set_buffer_defrag(buf);
1833 trans->blocks_used++;
1834 return buf;
1835 }
1836
1837 static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
1838 struct btrfs_root *root,
1839 struct extent_buffer *leaf)
1840 {
1841 u64 leaf_owner;
1842 u64 leaf_generation;
1843 struct btrfs_key key;
1844 struct btrfs_file_extent_item *fi;
1845 int i;
1846 int nritems;
1847 int ret;
1848
1849 BUG_ON(!btrfs_is_leaf(leaf));
1850 nritems = btrfs_header_nritems(leaf);
1851 leaf_owner = btrfs_header_owner(leaf);
1852 leaf_generation = btrfs_header_generation(leaf);
1853
1854 for (i = 0; i < nritems; i++) {
1855 u64 disk_bytenr;
1856
1857 btrfs_item_key_to_cpu(leaf, &key, i);
1858 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1859 continue;
1860 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1861 if (btrfs_file_extent_type(leaf, fi) ==
1862 BTRFS_FILE_EXTENT_INLINE)
1863 continue;
1864 /*
1865 * FIXME make sure to insert a trans record that
1866 * repeats the snapshot del on crash
1867 */
1868 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1869 if (disk_bytenr == 0)
1870 continue;
1871 ret = btrfs_free_extent(trans, root, disk_bytenr,
1872 btrfs_file_extent_disk_num_bytes(leaf, fi),
1873 leaf_owner, leaf_generation,
1874 key.objectid, key.offset, 0);
1875 BUG_ON(ret);
1876 }
1877 return 0;
1878 }
1879
1880 static void noinline reada_walk_down(struct btrfs_root *root,
1881 struct extent_buffer *node,
1882 int slot)
1883 {
1884 u64 bytenr;
1885 u64 last = 0;
1886 u32 nritems;
1887 u32 refs;
1888 u32 blocksize;
1889 int ret;
1890 int i;
1891 int level;
1892 int skipped = 0;
1893
1894 nritems = btrfs_header_nritems(node);
1895 level = btrfs_header_level(node);
1896 if (level)
1897 return;
1898
1899 for (i = slot; i < nritems && skipped < 32; i++) {
1900 bytenr = btrfs_node_blockptr(node, i);
1901 if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
1902 (last > bytenr && last - bytenr > 32 * 1024))) {
1903 skipped++;
1904 continue;
1905 }
1906 blocksize = btrfs_level_size(root, level - 1);
1907 if (i != slot) {
1908 ret = lookup_extent_ref(NULL, root, bytenr,
1909 blocksize, &refs);
1910 BUG_ON(ret);
1911 if (refs != 1) {
1912 skipped++;
1913 continue;
1914 }
1915 }
1916 mutex_unlock(&root->fs_info->fs_mutex);
1917 ret = readahead_tree_block(root, bytenr, blocksize);
1918 last = bytenr + blocksize;
1919 cond_resched();
1920 mutex_lock(&root->fs_info->fs_mutex);
1921 if (ret)
1922 break;
1923 }
1924 }
1925
1926 /*
1927 * helper function for drop_snapshot, this walks down the tree dropping ref
1928 * counts as it goes.
1929 */
1930 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
1931 struct btrfs_root *root,
1932 struct btrfs_path *path, int *level)
1933 {
1934 u64 root_owner;
1935 u64 root_gen;
1936 u64 bytenr;
1937 struct extent_buffer *next;
1938 struct extent_buffer *cur;
1939 struct extent_buffer *parent;
1940 u32 blocksize;
1941 int ret;
1942 u32 refs;
1943
1944 WARN_ON(*level < 0);
1945 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1946 ret = lookup_extent_ref(trans, root,
1947 path->nodes[*level]->start,
1948 path->nodes[*level]->len, &refs);
1949 BUG_ON(ret);
1950 if (refs > 1)
1951 goto out;
1952
1953 /*
1954 * walk down to the last node level and free all the leaves
1955 */
1956 while(*level >= 0) {
1957 WARN_ON(*level < 0);
1958 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1959 cur = path->nodes[*level];
1960
1961 if (btrfs_header_level(cur) != *level)
1962 WARN_ON(1);
1963
1964 if (path->slots[*level] >=
1965 btrfs_header_nritems(cur))
1966 break;
1967 if (*level == 0) {
1968 ret = drop_leaf_ref(trans, root, cur);
1969 BUG_ON(ret);
1970 break;
1971 }
1972 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1973 blocksize = btrfs_level_size(root, *level - 1);
1974 ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
1975 BUG_ON(ret);
1976 if (refs != 1) {
1977 parent = path->nodes[*level];
1978 root_owner = btrfs_header_owner(parent);
1979 root_gen = btrfs_header_generation(parent);
1980 path->slots[*level]++;
1981 ret = btrfs_free_extent(trans, root, bytenr,
1982 blocksize, root_owner,
1983 root_gen, 0, 0, 1);
1984 BUG_ON(ret);
1985 continue;
1986 }
1987 next = btrfs_find_tree_block(root, bytenr, blocksize);
1988 if (!next || !btrfs_buffer_uptodate(next)) {
1989 free_extent_buffer(next);
1990 reada_walk_down(root, cur, path->slots[*level]);
1991 mutex_unlock(&root->fs_info->fs_mutex);
1992 next = read_tree_block(root, bytenr, blocksize);
1993 mutex_lock(&root->fs_info->fs_mutex);
1994
1995 /* we dropped the lock, check one more time */
1996 ret = lookup_extent_ref(trans, root, bytenr,
1997 blocksize, &refs);
1998 BUG_ON(ret);
1999 if (refs != 1) {
2000 parent = path->nodes[*level];
2001 root_owner = btrfs_header_owner(parent);
2002 root_gen = btrfs_header_generation(parent);
2003
2004 path->slots[*level]++;
2005 free_extent_buffer(next);
2006 ret = btrfs_free_extent(trans, root, bytenr,
2007 blocksize,
2008 root_owner,
2009 root_gen, 0, 0, 1);
2010 BUG_ON(ret);
2011 continue;
2012 }
2013 }
2014 WARN_ON(*level <= 0);
2015 if (path->nodes[*level-1])
2016 free_extent_buffer(path->nodes[*level-1]);
2017 path->nodes[*level-1] = next;
2018 *level = btrfs_header_level(next);
2019 path->slots[*level] = 0;
2020 }
2021 out:
2022 WARN_ON(*level < 0);
2023 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2024
2025 if (path->nodes[*level] == root->node) {
2026 root_owner = root->root_key.objectid;
2027 parent = path->nodes[*level];
2028 } else {
2029 parent = path->nodes[*level + 1];
2030 root_owner = btrfs_header_owner(parent);
2031 }
2032
2033 root_gen = btrfs_header_generation(parent);
2034 ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
2035 path->nodes[*level]->len,
2036 root_owner, root_gen, 0, 0, 1);
2037 free_extent_buffer(path->nodes[*level]);
2038 path->nodes[*level] = NULL;
2039 *level += 1;
2040 BUG_ON(ret);
2041 return 0;
2042 }
2043
2044 /*
2045 * helper for dropping snapshots. This walks back up the tree in the path
2046 * to find the first node higher up where we haven't yet gone through
2047 * all the slots
2048 */
2049 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
2050 struct btrfs_root *root,
2051 struct btrfs_path *path, int *level)
2052 {
2053 u64 root_owner;
2054 u64 root_gen;
2055 struct btrfs_root_item *root_item = &root->root_item;
2056 int i;
2057 int slot;
2058 int ret;
2059
2060 for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2061 slot = path->slots[i];
2062 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
2063 struct extent_buffer *node;
2064 struct btrfs_disk_key disk_key;
2065 node = path->nodes[i];
2066 path->slots[i]++;
2067 *level = i;
2068 WARN_ON(*level == 0);
2069 btrfs_node_key(node, &disk_key, path->slots[i]);
2070 memcpy(&root_item->drop_progress,
2071 &disk_key, sizeof(disk_key));
2072 root_item->drop_level = i;
2073 return 0;
2074 } else {
2075 if (path->nodes[*level] == root->node) {
2076 root_owner = root->root_key.objectid;
2077 root_gen =
2078 btrfs_header_generation(path->nodes[*level]);
2079 } else {
2080 struct extent_buffer *node;
2081 node = path->nodes[*level + 1];
2082 root_owner = btrfs_header_owner(node);
2083 root_gen = btrfs_header_generation(node);
2084 }
2085 ret = btrfs_free_extent(trans, root,
2086 path->nodes[*level]->start,
2087 path->nodes[*level]->len,
2088 root_owner, root_gen, 0, 0, 1);
2089 BUG_ON(ret);
2090 free_extent_buffer(path->nodes[*level]);
2091 path->nodes[*level] = NULL;
2092 *level = i + 1;
2093 }
2094 }
2095 return 1;
2096 }
2097
2098 /*
2099 * drop the reference count on the tree rooted at 'snap'. This traverses
2100 * the tree freeing any blocks that have a ref count of zero after being
2101 * decremented.
2102 */
2103 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
2104 *root)
2105 {
2106 int ret = 0;
2107 int wret;
2108 int level;
2109 struct btrfs_path *path;
2110 int i;
2111 int orig_level;
2112 struct btrfs_root_item *root_item = &root->root_item;
2113
2114 path = btrfs_alloc_path();
2115 BUG_ON(!path);
2116
2117 level = btrfs_header_level(root->node);
2118 orig_level = level;
2119 if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2120 path->nodes[level] = root->node;
2121 extent_buffer_get(root->node);
2122 path->slots[level] = 0;
2123 } else {
2124 struct btrfs_key key;
2125 struct btrfs_disk_key found_key;
2126 struct extent_buffer *node;
2127
2128 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2129 level = root_item->drop_level;
2130 path->lowest_level = level;
2131 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2132 if (wret < 0) {
2133 ret = wret;
2134 goto out;
2135 }
2136 node = path->nodes[level];
2137 btrfs_node_key(node, &found_key, path->slots[level]);
2138 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2139 sizeof(found_key)));
2140 }
2141 while(1) {
2142 wret = walk_down_tree(trans, root, path, &level);
2143 if (wret > 0)
2144 break;
2145 if (wret < 0)
2146 ret = wret;
2147
2148 wret = walk_up_tree(trans, root, path, &level);
2149 if (wret > 0)
2150 break;
2151 if (wret < 0)
2152 ret = wret;
2153 ret = -EAGAIN;
2154 break;
2155 }
2156 for (i = 0; i <= orig_level; i++) {
2157 if (path->nodes[i]) {
2158 free_extent_buffer(path->nodes[i]);
2159 path->nodes[i] = NULL;
2160 }
2161 }
2162 out:
2163 btrfs_free_path(path);
2164 return ret;
2165 }
2166
2167 int btrfs_free_block_groups(struct btrfs_fs_info *info)
2168 {
2169 u64 start;
2170 u64 end;
2171 u64 ptr;
2172 int ret;
2173 while(1) {
2174 ret = find_first_extent_bit(&info->block_group_cache, 0,
2175 &start, &end, (unsigned int)-1);
2176 if (ret)
2177 break;
2178 ret = get_state_private(&info->block_group_cache, start, &ptr);
2179 if (!ret)
2180 kfree((void *)(unsigned long)ptr);
2181 clear_extent_bits(&info->block_group_cache, start,
2182 end, (unsigned int)-1, GFP_NOFS);
2183 }
2184 while(1) {
2185 ret = find_first_extent_bit(&info->free_space_cache, 0,
2186 &start, &end, EXTENT_DIRTY);
2187 if (ret)
2188 break;
2189 clear_extent_dirty(&info->free_space_cache, start,
2190 end, GFP_NOFS);
2191 }
2192 return 0;
2193 }
2194
2195 static int noinline relocate_inode_pages(struct inode *inode, u64 start,
2196 u64 len)
2197 {
2198 u64 page_start;
2199 u64 page_end;
2200 u64 delalloc_start;
2201 u64 existing_delalloc;
2202 unsigned long last_index;
2203 unsigned long i;
2204 struct page *page;
2205 struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
2206 struct file_ra_state *ra;
2207
2208 ra = kzalloc(sizeof(*ra), GFP_NOFS);
2209
2210 mutex_lock(&inode->i_mutex);
2211 i = start >> PAGE_CACHE_SHIFT;
2212 last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
2213
2214 file_ra_state_init(ra, inode->i_mapping);
2215 btrfs_force_ra(inode->i_mapping, ra, NULL, i, last_index);
2216 kfree(ra);
2217
2218 for (; i <= last_index; i++) {
2219 page = grab_cache_page(inode->i_mapping, i);
2220 if (!page)
2221 goto out_unlock;
2222 if (!PageUptodate(page)) {
2223 btrfs_readpage(NULL, page);
2224 lock_page(page);
2225 if (!PageUptodate(page)) {
2226 unlock_page(page);
2227 page_cache_release(page);
2228 goto out_unlock;
2229 }
2230 }
2231 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
2232 page_end = page_start + PAGE_CACHE_SIZE - 1;
2233
2234 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
2235
2236 delalloc_start = page_start;
2237 existing_delalloc = count_range_bits(io_tree,
2238 &delalloc_start, page_end,
2239 PAGE_CACHE_SIZE, EXTENT_DELALLOC);
2240
2241 set_extent_delalloc(io_tree, page_start,
2242 page_end, GFP_NOFS);
2243
2244 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
2245 set_page_dirty(page);
2246 unlock_page(page);
2247 page_cache_release(page);
2248 }
2249
2250 out_unlock:
2251 mutex_unlock(&inode->i_mutex);
2252 return 0;
2253 }
2254
2255 /*
2256 * note, this releases the path
2257 */
2258 static int noinline relocate_one_reference(struct btrfs_root *extent_root,
2259 struct btrfs_path *path,
2260 struct btrfs_key *extent_key)
2261 {
2262 struct inode *inode;
2263 struct btrfs_root *found_root;
2264 struct btrfs_key *root_location;
2265 struct btrfs_extent_ref *ref;
2266 u64 ref_root;
2267 u64 ref_gen;
2268 u64 ref_objectid;
2269 u64 ref_offset;
2270 int ret;
2271
2272 ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
2273 struct btrfs_extent_ref);
2274 ref_root = btrfs_ref_root(path->nodes[0], ref);
2275 ref_gen = btrfs_ref_generation(path->nodes[0], ref);
2276 ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
2277 ref_offset = btrfs_ref_offset(path->nodes[0], ref);
2278 btrfs_release_path(extent_root, path);
2279
2280 root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
2281 root_location->objectid = ref_root;
2282 if (ref_gen == 0)
2283 root_location->offset = 0;
2284 else
2285 root_location->offset = (u64)-1;
2286 root_location->type = BTRFS_ROOT_ITEM_KEY;
2287
2288 found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
2289 root_location);
2290 BUG_ON(!found_root);
2291 kfree(root_location);
2292
2293 if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
2294 mutex_unlock(&extent_root->fs_info->fs_mutex);
2295 inode = btrfs_iget_locked(extent_root->fs_info->sb,
2296 ref_objectid, found_root);
2297 if (inode->i_state & I_NEW) {
2298 /* the inode and parent dir are two different roots */
2299 BTRFS_I(inode)->root = found_root;
2300 BTRFS_I(inode)->location.objectid = ref_objectid;
2301 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
2302 BTRFS_I(inode)->location.offset = 0;
2303 btrfs_read_locked_inode(inode);
2304 unlock_new_inode(inode);
2305
2306 }
2307 /* this can happen if the reference is not against
2308 * the latest version of the tree root
2309 */
2310 if (is_bad_inode(inode)) {
2311 mutex_lock(&extent_root->fs_info->fs_mutex);
2312 goto out;
2313 }
2314 relocate_inode_pages(inode, ref_offset, extent_key->offset);
2315 /* FIXME, data=ordered will help get rid of this */
2316 filemap_fdatawrite(inode->i_mapping);
2317 iput(inode);
2318 mutex_lock(&extent_root->fs_info->fs_mutex);
2319 } else {
2320 struct btrfs_trans_handle *trans;
2321 struct btrfs_key found_key;
2322 struct extent_buffer *eb;
2323 int level;
2324 int i;
2325
2326 trans = btrfs_start_transaction(found_root, 1);
2327 eb = read_tree_block(found_root, extent_key->objectid,
2328 extent_key->offset);
2329 level = btrfs_header_level(eb);
2330
2331 if (level == 0)
2332 btrfs_item_key_to_cpu(eb, &found_key, 0);
2333 else
2334 btrfs_node_key_to_cpu(eb, &found_key, 0);
2335
2336 free_extent_buffer(eb);
2337
2338 path->lowest_level = level;
2339 path->reada = 2;
2340 ret = btrfs_search_slot(trans, found_root, &found_key, path,
2341 0, 1);
2342 path->lowest_level = 0;
2343 for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2344 if (!path->nodes[i])
2345 break;
2346 free_extent_buffer(path->nodes[i]);
2347 path->nodes[i] = NULL;
2348 }
2349 btrfs_release_path(found_root, path);
2350 btrfs_end_transaction(trans, found_root);
2351 }
2352
2353 out:
2354 return 0;
2355 }
2356
2357 static int noinline relocate_one_extent(struct btrfs_root *extent_root,
2358 struct btrfs_path *path,
2359 struct btrfs_key *extent_key)
2360 {
2361 struct btrfs_key key;
2362 struct btrfs_key found_key;
2363 struct extent_buffer *leaf;
2364 u32 nritems;
2365 u32 item_size;
2366 int ret = 0;
2367
2368 key.objectid = extent_key->objectid;
2369 key.type = BTRFS_EXTENT_REF_KEY;
2370 key.offset = 0;
2371
2372 while(1) {
2373 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2374
2375 if (ret < 0)
2376 goto out;
2377
2378 ret = 0;
2379 leaf = path->nodes[0];
2380 nritems = btrfs_header_nritems(leaf);
2381 if (path->slots[0] == nritems)
2382 goto out;
2383
2384 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2385 if (found_key.objectid != extent_key->objectid)
2386 break;
2387
2388 if (found_key.type != BTRFS_EXTENT_REF_KEY)
2389 break;
2390
2391 key.offset = found_key.offset + 1;
2392 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2393
2394 ret = relocate_one_reference(extent_root, path, extent_key);
2395 if (ret)
2396 goto out;
2397 }
2398 ret = 0;
2399 out:
2400 btrfs_release_path(extent_root, path);
2401 return ret;
2402 }
2403
2404 int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 new_size)
2405 {
2406 struct btrfs_trans_handle *trans;
2407 struct btrfs_root *tree_root = root->fs_info->tree_root;
2408 struct btrfs_path *path;
2409 u64 cur_byte;
2410 u64 total_found;
2411 struct btrfs_fs_info *info = root->fs_info;
2412 struct extent_io_tree *block_group_cache;
2413 struct btrfs_key key;
2414 struct btrfs_key found_key;
2415 struct extent_buffer *leaf;
2416 u32 nritems;
2417 int ret;
2418 int progress = 0;
2419
2420 btrfs_set_super_total_bytes(&info->super_copy, new_size);
2421 clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
2422 GFP_NOFS);
2423 block_group_cache = &info->block_group_cache;
2424 path = btrfs_alloc_path();
2425 root = root->fs_info->extent_root;
2426 path->reada = 2;
2427
2428 again:
2429 total_found = 0;
2430 key.objectid = new_size;
2431 key.offset = 0;
2432 key.type = 0;
2433 cur_byte = key.objectid;
2434
2435 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2436 if (ret < 0)
2437 goto out;
2438
2439 ret = find_previous_extent(root, path);
2440 if (ret < 0)
2441 goto out;
2442 if (ret == 0) {
2443 leaf = path->nodes[0];
2444 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2445 if (found_key.objectid + found_key.offset > new_size) {
2446 cur_byte = found_key.objectid;
2447 key.objectid = cur_byte;
2448 }
2449 }
2450 btrfs_release_path(root, path);
2451
2452 while(1) {
2453 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2454 if (ret < 0)
2455 goto out;
2456
2457 leaf = path->nodes[0];
2458 nritems = btrfs_header_nritems(leaf);
2459 next:
2460 if (path->slots[0] >= nritems) {
2461 ret = btrfs_next_leaf(root, path);
2462 if (ret < 0)
2463 goto out;
2464 if (ret == 1) {
2465 ret = 0;
2466 break;
2467 }
2468 leaf = path->nodes[0];
2469 nritems = btrfs_header_nritems(leaf);
2470 }
2471
2472 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2473
2474 if (progress && need_resched()) {
2475 memcpy(&key, &found_key, sizeof(key));
2476 mutex_unlock(&root->fs_info->fs_mutex);
2477 cond_resched();
2478 mutex_lock(&root->fs_info->fs_mutex);
2479 btrfs_release_path(root, path);
2480 btrfs_search_slot(NULL, root, &key, path, 0, 0);
2481 progress = 0;
2482 goto next;
2483 }
2484 progress = 1;
2485
2486 if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
2487 found_key.objectid + found_key.offset <= cur_byte) {
2488 path->slots[0]++;
2489 goto next;
2490 }
2491
2492 total_found++;
2493 cur_byte = found_key.objectid + found_key.offset;
2494 key.objectid = cur_byte;
2495 btrfs_release_path(root, path);
2496 ret = relocate_one_extent(root, path, &found_key);
2497 }
2498
2499 btrfs_release_path(root, path);
2500
2501 if (total_found > 0) {
2502 trans = btrfs_start_transaction(tree_root, 1);
2503 btrfs_commit_transaction(trans, tree_root);
2504
2505 mutex_unlock(&root->fs_info->fs_mutex);
2506 btrfs_clean_old_snapshots(tree_root);
2507 mutex_lock(&root->fs_info->fs_mutex);
2508
2509 trans = btrfs_start_transaction(tree_root, 1);
2510 btrfs_commit_transaction(trans, tree_root);
2511 goto again;
2512 }
2513
2514 trans = btrfs_start_transaction(root, 1);
2515 key.objectid = new_size;
2516 key.offset = 0;
2517 key.type = 0;
2518 while(1) {
2519 u64 ptr;
2520
2521 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
2522 if (ret < 0)
2523 goto out;
2524
2525 leaf = path->nodes[0];
2526 nritems = btrfs_header_nritems(leaf);
2527 bg_next:
2528 if (path->slots[0] >= nritems) {
2529 ret = btrfs_next_leaf(root, path);
2530 if (ret < 0)
2531 break;
2532 if (ret == 1) {
2533 ret = 0;
2534 break;
2535 }
2536 leaf = path->nodes[0];
2537 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2538
2539 /*
2540 * btrfs_next_leaf doesn't cow buffers, we have to
2541 * do the search again
2542 */
2543 memcpy(&key, &found_key, sizeof(key));
2544 btrfs_release_path(root, path);
2545 goto resched_check;
2546 }
2547
2548 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2549 if (btrfs_key_type(&found_key) != BTRFS_BLOCK_GROUP_ITEM_KEY) {
2550 printk("shrinker found key %Lu %u %Lu\n",
2551 found_key.objectid, found_key.type,
2552 found_key.offset);
2553 path->slots[0]++;
2554 goto bg_next;
2555 }
2556 ret = get_state_private(&info->block_group_cache,
2557 found_key.objectid, &ptr);
2558 if (!ret)
2559 kfree((void *)(unsigned long)ptr);
2560
2561 clear_extent_bits(&info->block_group_cache, found_key.objectid,
2562 found_key.objectid + found_key.offset - 1,
2563 (unsigned int)-1, GFP_NOFS);
2564
2565 key.objectid = found_key.objectid + 1;
2566 btrfs_del_item(trans, root, path);
2567 btrfs_release_path(root, path);
2568 resched_check:
2569 if (need_resched()) {
2570 mutex_unlock(&root->fs_info->fs_mutex);
2571 cond_resched();
2572 mutex_lock(&root->fs_info->fs_mutex);
2573 }
2574 }
2575 clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
2576 GFP_NOFS);
2577 btrfs_commit_transaction(trans, root);
2578 out:
2579 btrfs_free_path(path);
2580 return ret;
2581 }
2582
2583 int btrfs_grow_extent_tree(struct btrfs_trans_handle *trans,
2584 struct btrfs_root *root, u64 new_size)
2585 {
2586 struct btrfs_path *path;
2587 u64 nr = 0;
2588 u64 cur_byte;
2589 u64 old_size;
2590 unsigned long rem;
2591 struct btrfs_block_group_cache *cache;
2592 struct btrfs_block_group_item *item;
2593 struct btrfs_fs_info *info = root->fs_info;
2594 struct extent_io_tree *block_group_cache;
2595 struct btrfs_key key;
2596 struct extent_buffer *leaf;
2597 int ret;
2598 int bit;
2599
2600 old_size = btrfs_super_total_bytes(&info->super_copy);
2601 block_group_cache = &info->block_group_cache;
2602
2603 root = info->extent_root;
2604
2605 cache = btrfs_lookup_block_group(root->fs_info, old_size - 1);
2606
2607 cur_byte = cache->key.objectid + cache->key.offset;
2608 if (cur_byte >= new_size)
2609 goto set_size;
2610
2611 key.offset = BTRFS_BLOCK_GROUP_SIZE;
2612 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2613
2614 path = btrfs_alloc_path();
2615 if (!path)
2616 return -ENOMEM;
2617
2618 while(cur_byte < new_size) {
2619 key.objectid = cur_byte;
2620 ret = btrfs_insert_empty_item(trans, root, path, &key,
2621 sizeof(struct btrfs_block_group_item));
2622 BUG_ON(ret);
2623 leaf = path->nodes[0];
2624 item = btrfs_item_ptr(leaf, path->slots[0],
2625 struct btrfs_block_group_item);
2626
2627 btrfs_set_disk_block_group_used(leaf, item, 0);
2628 div_long_long_rem(nr, 3, &rem);
2629 if (rem) {
2630 btrfs_set_disk_block_group_flags(leaf, item,
2631 BTRFS_BLOCK_GROUP_DATA);
2632 } else {
2633 btrfs_set_disk_block_group_flags(leaf, item, 0);
2634 }
2635 nr++;
2636
2637 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2638 BUG_ON(!cache);
2639
2640 read_extent_buffer(leaf, &cache->item, (unsigned long)item,
2641 sizeof(cache->item));
2642
2643 memcpy(&cache->key, &key, sizeof(key));
2644 cache->cached = 0;
2645 cache->pinned = 0;
2646 cur_byte = key.objectid + key.offset;
2647 btrfs_release_path(root, path);
2648
2649 if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2650 bit = BLOCK_GROUP_DATA;
2651 cache->data = BTRFS_BLOCK_GROUP_DATA;
2652 } else {
2653 bit = BLOCK_GROUP_METADATA;
2654 cache->data = 0;
2655 }
2656
2657 /* use EXTENT_LOCKED to prevent merging */
2658 set_extent_bits(block_group_cache, key.objectid,
2659 key.objectid + key.offset - 1,
2660 bit | EXTENT_LOCKED, GFP_NOFS);
2661 set_state_private(block_group_cache, key.objectid,
2662 (unsigned long)cache);
2663 }
2664 btrfs_free_path(path);
2665 set_size:
2666 btrfs_set_super_total_bytes(&info->super_copy, new_size);
2667 return 0;
2668 }
2669
2670 int btrfs_read_block_groups(struct btrfs_root *root)
2671 {
2672 struct btrfs_path *path;
2673 int ret;
2674 int err = 0;
2675 int bit;
2676 struct btrfs_block_group_cache *cache;
2677 struct btrfs_fs_info *info = root->fs_info;
2678 struct extent_io_tree *block_group_cache;
2679 struct btrfs_key key;
2680 struct btrfs_key found_key;
2681 struct extent_buffer *leaf;
2682
2683 block_group_cache = &info->block_group_cache;
2684
2685 root = info->extent_root;
2686 key.objectid = 0;
2687 key.offset = BTRFS_BLOCK_GROUP_SIZE;
2688 btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
2689
2690 path = btrfs_alloc_path();
2691 if (!path)
2692 return -ENOMEM;
2693
2694 while(1) {
2695 ret = btrfs_search_slot(NULL, info->extent_root,
2696 &key, path, 0, 0);
2697 if (ret != 0) {
2698 err = ret;
2699 break;
2700 }
2701 leaf = path->nodes[0];
2702 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2703 cache = kmalloc(sizeof(*cache), GFP_NOFS);
2704 if (!cache) {
2705 err = -1;
2706 break;
2707 }
2708
2709 read_extent_buffer(leaf, &cache->item,
2710 btrfs_item_ptr_offset(leaf, path->slots[0]),
2711 sizeof(cache->item));
2712 memcpy(&cache->key, &found_key, sizeof(found_key));
2713 cache->cached = 0;
2714 cache->pinned = 0;
2715 key.objectid = found_key.objectid + found_key.offset;
2716 btrfs_release_path(root, path);
2717
2718 if (cache->item.flags & BTRFS_BLOCK_GROUP_MIXED) {
2719 bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
2720 cache->data = BTRFS_BLOCK_GROUP_MIXED;
2721 } else if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
2722 bit = BLOCK_GROUP_DATA;
2723 cache->data = BTRFS_BLOCK_GROUP_DATA;
2724 } else {
2725 bit = BLOCK_GROUP_METADATA;
2726 cache->data = 0;
2727 }
2728
2729 /* use EXTENT_LOCKED to prevent merging */
2730 set_extent_bits(block_group_cache, found_key.objectid,
2731 found_key.objectid + found_key.offset - 1,
2732 bit | EXTENT_LOCKED, GFP_NOFS);
2733 set_state_private(block_group_cache, found_key.objectid,
2734 (unsigned long)cache);
2735
2736 if (key.objectid >=
2737 btrfs_super_total_bytes(&info->super_copy))
2738 break;
2739 }
2740
2741 btrfs_free_path(path);
2742 return 0;
2743 }
Linux kernel - Deliverables
This page took 0.153671 seconds and 6 git commands to generate.