2 * Copyright (C) 2007 Oracle. All rights reserved.
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.
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.
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.
18 #define _XOPEN_SOURCE 600
22 #include <sys/types.h>
24 #include <uuid/uuid.h>
29 #include "transaction.h"
30 #include "print-tree.h"
35 struct btrfs_device
*dev
;
39 static inline int nr_parity_stripes(struct map_lookup
*map
)
41 if (map
->type
& BTRFS_BLOCK_GROUP_RAID5
)
43 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID6
)
49 static inline int nr_data_stripes(struct map_lookup
*map
)
51 return map
->num_stripes
- nr_parity_stripes(map
);
54 #define is_parity_stripe(x) ( ((x) == BTRFS_RAID5_P_STRIPE) || ((x) == BTRFS_RAID6_Q_STRIPE) )
56 static LIST_HEAD(fs_uuids
);
58 static struct btrfs_device
*__find_device(struct list_head
*head
, u64 devid
,
61 struct btrfs_device
*dev
;
62 struct list_head
*cur
;
64 list_for_each(cur
, head
) {
65 dev
= list_entry(cur
, struct btrfs_device
, dev_list
);
66 if (dev
->devid
== devid
&&
67 !memcmp(dev
->uuid
, uuid
, BTRFS_UUID_SIZE
)) {
74 static struct btrfs_fs_devices
*find_fsid(u8
*fsid
)
76 struct list_head
*cur
;
77 struct btrfs_fs_devices
*fs_devices
;
79 list_for_each(cur
, &fs_uuids
) {
80 fs_devices
= list_entry(cur
, struct btrfs_fs_devices
, list
);
81 if (memcmp(fsid
, fs_devices
->fsid
, BTRFS_FSID_SIZE
) == 0)
87 static int device_list_add(const char *path
,
88 struct btrfs_super_block
*disk_super
,
89 u64 devid
, struct btrfs_fs_devices
**fs_devices_ret
)
91 struct btrfs_device
*device
;
92 struct btrfs_fs_devices
*fs_devices
;
93 u64 found_transid
= btrfs_super_generation(disk_super
);
95 fs_devices
= find_fsid(disk_super
->fsid
);
97 fs_devices
= kzalloc(sizeof(*fs_devices
), GFP_NOFS
);
100 INIT_LIST_HEAD(&fs_devices
->devices
);
101 list_add(&fs_devices
->list
, &fs_uuids
);
102 memcpy(fs_devices
->fsid
, disk_super
->fsid
, BTRFS_FSID_SIZE
);
103 fs_devices
->latest_devid
= devid
;
104 fs_devices
->latest_trans
= found_transid
;
105 fs_devices
->lowest_devid
= (u64
)-1;
108 device
= __find_device(&fs_devices
->devices
, devid
,
109 disk_super
->dev_item
.uuid
);
112 device
= kzalloc(sizeof(*device
), GFP_NOFS
);
114 /* we can safely leave the fs_devices entry around */
118 device
->devid
= devid
;
119 memcpy(device
->uuid
, disk_super
->dev_item
.uuid
,
121 device
->name
= kstrdup(path
, GFP_NOFS
);
126 device
->label
= kstrdup(disk_super
->label
, GFP_NOFS
);
127 if (!device
->label
) {
132 device
->total_devs
= btrfs_super_num_devices(disk_super
);
133 device
->super_bytes_used
= btrfs_super_bytes_used(disk_super
);
134 device
->total_bytes
=
135 btrfs_stack_device_total_bytes(&disk_super
->dev_item
);
137 btrfs_stack_device_bytes_used(&disk_super
->dev_item
);
138 list_add(&device
->dev_list
, &fs_devices
->devices
);
139 device
->fs_devices
= fs_devices
;
140 } else if (!device
->name
|| strcmp(device
->name
, path
)) {
141 char *name
= strdup(path
);
149 if (found_transid
> fs_devices
->latest_trans
) {
150 fs_devices
->latest_devid
= devid
;
151 fs_devices
->latest_trans
= found_transid
;
153 if (fs_devices
->lowest_devid
> devid
) {
154 fs_devices
->lowest_devid
= devid
;
156 *fs_devices_ret
= fs_devices
;
160 int btrfs_close_devices(struct btrfs_fs_devices
*fs_devices
)
162 struct btrfs_fs_devices
*seed_devices
;
163 struct btrfs_device
*device
;
166 while (!list_empty(&fs_devices
->devices
)) {
167 device
= list_entry(fs_devices
->devices
.next
,
168 struct btrfs_device
, dev_list
);
169 if (device
->fd
!= -1) {
171 if (posix_fadvise(device
->fd
, 0, 0, POSIX_FADV_DONTNEED
))
172 fprintf(stderr
, "Warning, could not drop caches\n");
176 device
->writeable
= 0;
177 list_del(&device
->dev_list
);
178 /* free the memory */
184 seed_devices
= fs_devices
->seed
;
185 fs_devices
->seed
= NULL
;
187 fs_devices
= seed_devices
;
195 int btrfs_open_devices(struct btrfs_fs_devices
*fs_devices
, int flags
)
198 struct list_head
*head
= &fs_devices
->devices
;
199 struct list_head
*cur
;
200 struct btrfs_device
*device
;
203 list_for_each(cur
, head
) {
204 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
206 printk("no name for device %llu, skip it now\n", device
->devid
);
210 fd
= open(device
->name
, flags
);
216 if (posix_fadvise(fd
, 0, 0, POSIX_FADV_DONTNEED
))
217 fprintf(stderr
, "Warning, could not drop caches\n");
219 if (device
->devid
== fs_devices
->latest_devid
)
220 fs_devices
->latest_bdev
= fd
;
221 if (device
->devid
== fs_devices
->lowest_devid
)
222 fs_devices
->lowest_bdev
= fd
;
225 device
->writeable
= 1;
229 btrfs_close_devices(fs_devices
);
233 int btrfs_scan_one_device(int fd
, const char *path
,
234 struct btrfs_fs_devices
**fs_devices_ret
,
235 u64
*total_devs
, u64 super_offset
)
237 struct btrfs_super_block
*disk_super
;
247 disk_super
= (struct btrfs_super_block
*)buf
;
248 ret
= btrfs_read_dev_super(fd
, disk_super
, super_offset
);
253 devid
= btrfs_stack_device_id(&disk_super
->dev_item
);
254 if (btrfs_super_flags(disk_super
) & BTRFS_SUPER_FLAG_METADUMP
)
257 *total_devs
= btrfs_super_num_devices(disk_super
);
259 ret
= device_list_add(path
, disk_super
, devid
, fs_devices_ret
);
268 * this uses a pretty simple search, the expectation is that it is
269 * called very infrequently and that a given device has a small number
272 static int find_free_dev_extent(struct btrfs_trans_handle
*trans
,
273 struct btrfs_device
*device
,
274 struct btrfs_path
*path
,
275 u64 num_bytes
, u64
*start
)
277 struct btrfs_key key
;
278 struct btrfs_root
*root
= device
->dev_root
;
279 struct btrfs_dev_extent
*dev_extent
= NULL
;
282 u64 search_start
= root
->fs_info
->alloc_start
;
283 u64 search_end
= device
->total_bytes
;
287 struct extent_buffer
*l
;
292 /* FIXME use last free of some kind */
294 /* we don't want to overwrite the superblock on the drive,
295 * so we make sure to start at an offset of at least 1MB
297 search_start
= max(BTRFS_BLOCK_RESERVED_1M_FOR_SUPER
, search_start
);
299 if (search_start
>= search_end
) {
304 key
.objectid
= device
->devid
;
305 key
.offset
= search_start
;
306 key
.type
= BTRFS_DEV_EXTENT_KEY
;
307 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 0);
310 ret
= btrfs_previous_item(root
, path
, 0, key
.type
);
314 btrfs_item_key_to_cpu(l
, &key
, path
->slots
[0]);
317 slot
= path
->slots
[0];
318 if (slot
>= btrfs_header_nritems(l
)) {
319 ret
= btrfs_next_leaf(root
, path
);
326 if (search_start
>= search_end
) {
330 *start
= search_start
;
334 *start
= last_byte
> search_start
?
335 last_byte
: search_start
;
336 if (search_end
<= *start
) {
342 btrfs_item_key_to_cpu(l
, &key
, slot
);
344 if (key
.objectid
< device
->devid
)
347 if (key
.objectid
> device
->devid
)
350 if (key
.offset
>= search_start
&& key
.offset
> last_byte
&&
352 if (last_byte
< search_start
)
353 last_byte
= search_start
;
354 hole_size
= key
.offset
- last_byte
;
355 if (key
.offset
> last_byte
&&
356 hole_size
>= num_bytes
) {
361 if (btrfs_key_type(&key
) != BTRFS_DEV_EXTENT_KEY
) {
366 dev_extent
= btrfs_item_ptr(l
, slot
, struct btrfs_dev_extent
);
367 last_byte
= key
.offset
+ btrfs_dev_extent_length(l
, dev_extent
);
373 /* we have to make sure we didn't find an extent that has already
374 * been allocated by the map tree or the original allocation
376 btrfs_release_path(path
);
377 BUG_ON(*start
< search_start
);
379 if (*start
+ num_bytes
> search_end
) {
383 /* check for pending inserts here */
387 btrfs_release_path(path
);
391 static int btrfs_alloc_dev_extent(struct btrfs_trans_handle
*trans
,
392 struct btrfs_device
*device
,
393 u64 chunk_tree
, u64 chunk_objectid
,
395 u64 num_bytes
, u64
*start
)
398 struct btrfs_path
*path
;
399 struct btrfs_root
*root
= device
->dev_root
;
400 struct btrfs_dev_extent
*extent
;
401 struct extent_buffer
*leaf
;
402 struct btrfs_key key
;
404 path
= btrfs_alloc_path();
408 ret
= find_free_dev_extent(trans
, device
, path
, num_bytes
, start
);
413 key
.objectid
= device
->devid
;
415 key
.type
= BTRFS_DEV_EXTENT_KEY
;
416 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
420 leaf
= path
->nodes
[0];
421 extent
= btrfs_item_ptr(leaf
, path
->slots
[0],
422 struct btrfs_dev_extent
);
423 btrfs_set_dev_extent_chunk_tree(leaf
, extent
, chunk_tree
);
424 btrfs_set_dev_extent_chunk_objectid(leaf
, extent
, chunk_objectid
);
425 btrfs_set_dev_extent_chunk_offset(leaf
, extent
, chunk_offset
);
427 write_extent_buffer(leaf
, root
->fs_info
->chunk_tree_uuid
,
428 (unsigned long)btrfs_dev_extent_chunk_tree_uuid(extent
),
431 btrfs_set_dev_extent_length(leaf
, extent
, num_bytes
);
432 btrfs_mark_buffer_dirty(leaf
);
434 btrfs_free_path(path
);
438 static int find_next_chunk(struct btrfs_root
*root
, u64 objectid
, u64
*offset
)
440 struct btrfs_path
*path
;
442 struct btrfs_key key
;
443 struct btrfs_chunk
*chunk
;
444 struct btrfs_key found_key
;
446 path
= btrfs_alloc_path();
449 key
.objectid
= objectid
;
450 key
.offset
= (u64
)-1;
451 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
453 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
459 ret
= btrfs_previous_item(root
, path
, 0, BTRFS_CHUNK_ITEM_KEY
);
463 btrfs_item_key_to_cpu(path
->nodes
[0], &found_key
,
465 if (found_key
.objectid
!= objectid
)
468 chunk
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
470 *offset
= found_key
.offset
+
471 btrfs_chunk_length(path
->nodes
[0], chunk
);
476 btrfs_free_path(path
);
480 static int find_next_devid(struct btrfs_root
*root
, struct btrfs_path
*path
,
484 struct btrfs_key key
;
485 struct btrfs_key found_key
;
487 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
488 key
.type
= BTRFS_DEV_ITEM_KEY
;
489 key
.offset
= (u64
)-1;
491 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
497 ret
= btrfs_previous_item(root
, path
, BTRFS_DEV_ITEMS_OBJECTID
,
502 btrfs_item_key_to_cpu(path
->nodes
[0], &found_key
,
504 *objectid
= found_key
.offset
+ 1;
508 btrfs_release_path(path
);
513 * the device information is stored in the chunk root
514 * the btrfs_device struct should be fully filled in
516 int btrfs_add_device(struct btrfs_trans_handle
*trans
,
517 struct btrfs_root
*root
,
518 struct btrfs_device
*device
)
521 struct btrfs_path
*path
;
522 struct btrfs_dev_item
*dev_item
;
523 struct extent_buffer
*leaf
;
524 struct btrfs_key key
;
528 root
= root
->fs_info
->chunk_root
;
530 path
= btrfs_alloc_path();
534 ret
= find_next_devid(root
, path
, &free_devid
);
538 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
539 key
.type
= BTRFS_DEV_ITEM_KEY
;
540 key
.offset
= free_devid
;
542 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
547 leaf
= path
->nodes
[0];
548 dev_item
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_dev_item
);
550 device
->devid
= free_devid
;
551 btrfs_set_device_id(leaf
, dev_item
, device
->devid
);
552 btrfs_set_device_generation(leaf
, dev_item
, 0);
553 btrfs_set_device_type(leaf
, dev_item
, device
->type
);
554 btrfs_set_device_io_align(leaf
, dev_item
, device
->io_align
);
555 btrfs_set_device_io_width(leaf
, dev_item
, device
->io_width
);
556 btrfs_set_device_sector_size(leaf
, dev_item
, device
->sector_size
);
557 btrfs_set_device_total_bytes(leaf
, dev_item
, device
->total_bytes
);
558 btrfs_set_device_bytes_used(leaf
, dev_item
, device
->bytes_used
);
559 btrfs_set_device_group(leaf
, dev_item
, 0);
560 btrfs_set_device_seek_speed(leaf
, dev_item
, 0);
561 btrfs_set_device_bandwidth(leaf
, dev_item
, 0);
562 btrfs_set_device_start_offset(leaf
, dev_item
, 0);
564 ptr
= (unsigned long)btrfs_device_uuid(dev_item
);
565 write_extent_buffer(leaf
, device
->uuid
, ptr
, BTRFS_UUID_SIZE
);
566 ptr
= (unsigned long)btrfs_device_fsid(dev_item
);
567 write_extent_buffer(leaf
, root
->fs_info
->fsid
, ptr
, BTRFS_UUID_SIZE
);
568 btrfs_mark_buffer_dirty(leaf
);
572 btrfs_free_path(path
);
576 int btrfs_update_device(struct btrfs_trans_handle
*trans
,
577 struct btrfs_device
*device
)
580 struct btrfs_path
*path
;
581 struct btrfs_root
*root
;
582 struct btrfs_dev_item
*dev_item
;
583 struct extent_buffer
*leaf
;
584 struct btrfs_key key
;
586 root
= device
->dev_root
->fs_info
->chunk_root
;
588 path
= btrfs_alloc_path();
592 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
593 key
.type
= BTRFS_DEV_ITEM_KEY
;
594 key
.offset
= device
->devid
;
596 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
605 leaf
= path
->nodes
[0];
606 dev_item
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_dev_item
);
608 btrfs_set_device_id(leaf
, dev_item
, device
->devid
);
609 btrfs_set_device_type(leaf
, dev_item
, device
->type
);
610 btrfs_set_device_io_align(leaf
, dev_item
, device
->io_align
);
611 btrfs_set_device_io_width(leaf
, dev_item
, device
->io_width
);
612 btrfs_set_device_sector_size(leaf
, dev_item
, device
->sector_size
);
613 btrfs_set_device_total_bytes(leaf
, dev_item
, device
->total_bytes
);
614 btrfs_set_device_bytes_used(leaf
, dev_item
, device
->bytes_used
);
615 btrfs_mark_buffer_dirty(leaf
);
618 btrfs_free_path(path
);
622 int btrfs_add_system_chunk(struct btrfs_trans_handle
*trans
,
623 struct btrfs_root
*root
,
624 struct btrfs_key
*key
,
625 struct btrfs_chunk
*chunk
, int item_size
)
627 struct btrfs_super_block
*super_copy
= root
->fs_info
->super_copy
;
628 struct btrfs_disk_key disk_key
;
632 array_size
= btrfs_super_sys_array_size(super_copy
);
633 if (array_size
+ item_size
> BTRFS_SYSTEM_CHUNK_ARRAY_SIZE
)
636 ptr
= super_copy
->sys_chunk_array
+ array_size
;
637 btrfs_cpu_key_to_disk(&disk_key
, key
);
638 memcpy(ptr
, &disk_key
, sizeof(disk_key
));
639 ptr
+= sizeof(disk_key
);
640 memcpy(ptr
, chunk
, item_size
);
641 item_size
+= sizeof(disk_key
);
642 btrfs_set_super_sys_array_size(super_copy
, array_size
+ item_size
);
646 static u64
chunk_bytes_by_type(u64 type
, u64 calc_size
, int num_stripes
,
649 if (type
& (BTRFS_BLOCK_GROUP_RAID1
| BTRFS_BLOCK_GROUP_DUP
))
651 else if (type
& BTRFS_BLOCK_GROUP_RAID10
)
652 return calc_size
* (num_stripes
/ sub_stripes
);
653 else if (type
& BTRFS_BLOCK_GROUP_RAID5
)
654 return calc_size
* (num_stripes
- 1);
655 else if (type
& BTRFS_BLOCK_GROUP_RAID6
)
656 return calc_size
* (num_stripes
- 2);
658 return calc_size
* num_stripes
;
662 static u32
find_raid56_stripe_len(u32 data_devices
, u32 dev_stripe_target
)
664 /* TODO, add a way to store the preferred stripe size */
665 return BTRFS_STRIPE_LEN
;
669 * btrfs_device_avail_bytes - count bytes available for alloc_chunk
671 * It is not equal to "device->total_bytes - device->bytes_used".
672 * We do not allocate any chunk in 1M at beginning of device, and not
673 * allowed to allocate any chunk before alloc_start if it is specified.
674 * So search holes from max(1M, alloc_start) to device->total_bytes.
676 static int btrfs_device_avail_bytes(struct btrfs_trans_handle
*trans
,
677 struct btrfs_device
*device
,
680 struct btrfs_path
*path
;
681 struct btrfs_root
*root
= device
->dev_root
;
682 struct btrfs_key key
;
683 struct btrfs_dev_extent
*dev_extent
= NULL
;
684 struct extent_buffer
*l
;
685 u64 search_start
= root
->fs_info
->alloc_start
;
686 u64 search_end
= device
->total_bytes
;
692 search_start
= max(BTRFS_BLOCK_RESERVED_1M_FOR_SUPER
, search_start
);
694 path
= btrfs_alloc_path();
698 key
.objectid
= device
->devid
;
699 key
.offset
= root
->fs_info
->alloc_start
;
700 key
.type
= BTRFS_DEV_EXTENT_KEY
;
703 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 0);
706 ret
= btrfs_previous_item(root
, path
, 0, key
.type
);
712 slot
= path
->slots
[0];
713 if (slot
>= btrfs_header_nritems(l
)) {
714 ret
= btrfs_next_leaf(root
, path
);
721 btrfs_item_key_to_cpu(l
, &key
, slot
);
723 if (key
.objectid
< device
->devid
)
725 if (key
.objectid
> device
->devid
)
727 if (btrfs_key_type(&key
) != BTRFS_DEV_EXTENT_KEY
)
729 if (key
.offset
> search_end
)
731 if (key
.offset
> search_start
)
732 free_bytes
+= key
.offset
- search_start
;
734 dev_extent
= btrfs_item_ptr(l
, slot
, struct btrfs_dev_extent
);
735 extent_end
= key
.offset
+ btrfs_dev_extent_length(l
,
737 if (extent_end
> search_start
)
738 search_start
= extent_end
;
739 if (search_start
> search_end
)
746 if (search_start
< search_end
)
747 free_bytes
+= search_end
- search_start
;
749 *avail_bytes
= free_bytes
;
752 btrfs_free_path(path
);
756 int btrfs_alloc_chunk(struct btrfs_trans_handle
*trans
,
757 struct btrfs_root
*extent_root
, u64
*start
,
758 u64
*num_bytes
, u64 type
)
761 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
762 struct btrfs_root
*chunk_root
= info
->chunk_root
;
763 struct btrfs_stripe
*stripes
;
764 struct btrfs_device
*device
= NULL
;
765 struct btrfs_chunk
*chunk
;
766 struct list_head private_devs
;
767 struct list_head
*dev_list
= &info
->fs_devices
->devices
;
768 struct list_head
*cur
;
769 struct map_lookup
*map
;
770 int min_stripe_size
= 1 * 1024 * 1024;
771 u64 calc_size
= 8 * 1024 * 1024;
773 u64 max_chunk_size
= 4 * calc_size
;
783 int stripe_len
= BTRFS_STRIPE_LEN
;
784 struct btrfs_key key
;
787 if (list_empty(dev_list
)) {
791 if (type
& (BTRFS_BLOCK_GROUP_RAID0
| BTRFS_BLOCK_GROUP_RAID1
|
792 BTRFS_BLOCK_GROUP_RAID5
| BTRFS_BLOCK_GROUP_RAID6
|
793 BTRFS_BLOCK_GROUP_RAID10
|
794 BTRFS_BLOCK_GROUP_DUP
)) {
795 if (type
& BTRFS_BLOCK_GROUP_SYSTEM
) {
796 calc_size
= 8 * 1024 * 1024;
797 max_chunk_size
= calc_size
* 2;
798 min_stripe_size
= 1 * 1024 * 1024;
799 } else if (type
& BTRFS_BLOCK_GROUP_DATA
) {
800 calc_size
= 1024 * 1024 * 1024;
801 max_chunk_size
= 10 * calc_size
;
802 min_stripe_size
= 64 * 1024 * 1024;
803 } else if (type
& BTRFS_BLOCK_GROUP_METADATA
) {
804 calc_size
= 1024 * 1024 * 1024;
805 max_chunk_size
= 4 * calc_size
;
806 min_stripe_size
= 32 * 1024 * 1024;
809 if (type
& BTRFS_BLOCK_GROUP_RAID1
) {
810 num_stripes
= min_t(u64
, 2,
811 btrfs_super_num_devices(info
->super_copy
));
816 if (type
& BTRFS_BLOCK_GROUP_DUP
) {
820 if (type
& (BTRFS_BLOCK_GROUP_RAID0
)) {
821 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
824 if (type
& (BTRFS_BLOCK_GROUP_RAID10
)) {
825 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
828 num_stripes
&= ~(u32
)1;
832 if (type
& (BTRFS_BLOCK_GROUP_RAID5
)) {
833 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
837 stripe_len
= find_raid56_stripe_len(num_stripes
- 1,
838 btrfs_super_stripesize(info
->super_copy
));
840 if (type
& (BTRFS_BLOCK_GROUP_RAID6
)) {
841 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
845 stripe_len
= find_raid56_stripe_len(num_stripes
- 2,
846 btrfs_super_stripesize(info
->super_copy
));
849 /* we don't want a chunk larger than 10% of the FS */
850 percent_max
= div_factor(btrfs_super_total_bytes(info
->super_copy
), 1);
851 max_chunk_size
= min(percent_max
, max_chunk_size
);
854 if (chunk_bytes_by_type(type
, calc_size
, num_stripes
, sub_stripes
) >
856 calc_size
= max_chunk_size
;
857 calc_size
/= num_stripes
;
858 calc_size
/= stripe_len
;
859 calc_size
*= stripe_len
;
861 /* we don't want tiny stripes */
862 calc_size
= max_t(u64
, calc_size
, min_stripe_size
);
864 calc_size
/= stripe_len
;
865 calc_size
*= stripe_len
;
866 INIT_LIST_HEAD(&private_devs
);
867 cur
= dev_list
->next
;
870 if (type
& BTRFS_BLOCK_GROUP_DUP
)
871 min_free
= calc_size
* 2;
873 min_free
= calc_size
;
875 /* build a private list of devices we will allocate from */
876 while(index
< num_stripes
) {
877 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
878 ret
= btrfs_device_avail_bytes(trans
, device
, &avail
);
882 if (avail
>= min_free
) {
883 list_move_tail(&device
->dev_list
, &private_devs
);
885 if (type
& BTRFS_BLOCK_GROUP_DUP
)
887 } else if (avail
> max_avail
)
892 if (index
< num_stripes
) {
893 list_splice(&private_devs
, dev_list
);
894 if (index
>= min_stripes
) {
896 if (type
& (BTRFS_BLOCK_GROUP_RAID10
)) {
897 num_stripes
/= sub_stripes
;
898 num_stripes
*= sub_stripes
;
903 if (!looped
&& max_avail
> 0) {
905 calc_size
= max_avail
;
910 ret
= find_next_chunk(chunk_root
, BTRFS_FIRST_CHUNK_TREE_OBJECTID
,
914 key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
915 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
918 chunk
= kmalloc(btrfs_chunk_item_size(num_stripes
), GFP_NOFS
);
922 map
= kmalloc(btrfs_map_lookup_size(num_stripes
), GFP_NOFS
);
928 stripes
= &chunk
->stripe
;
929 *num_bytes
= chunk_bytes_by_type(type
, calc_size
,
930 num_stripes
, sub_stripes
);
932 while(index
< num_stripes
) {
933 struct btrfs_stripe
*stripe
;
934 BUG_ON(list_empty(&private_devs
));
935 cur
= private_devs
.next
;
936 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
938 /* loop over this device again if we're doing a dup group */
939 if (!(type
& BTRFS_BLOCK_GROUP_DUP
) ||
940 (index
== num_stripes
- 1))
941 list_move_tail(&device
->dev_list
, dev_list
);
943 ret
= btrfs_alloc_dev_extent(trans
, device
,
944 info
->chunk_root
->root_key
.objectid
,
945 BTRFS_FIRST_CHUNK_TREE_OBJECTID
, key
.offset
,
946 calc_size
, &dev_offset
);
949 device
->bytes_used
+= calc_size
;
950 ret
= btrfs_update_device(trans
, device
);
953 map
->stripes
[index
].dev
= device
;
954 map
->stripes
[index
].physical
= dev_offset
;
955 stripe
= stripes
+ index
;
956 btrfs_set_stack_stripe_devid(stripe
, device
->devid
);
957 btrfs_set_stack_stripe_offset(stripe
, dev_offset
);
958 memcpy(stripe
->dev_uuid
, device
->uuid
, BTRFS_UUID_SIZE
);
961 BUG_ON(!list_empty(&private_devs
));
963 /* key was set above */
964 btrfs_set_stack_chunk_length(chunk
, *num_bytes
);
965 btrfs_set_stack_chunk_owner(chunk
, extent_root
->root_key
.objectid
);
966 btrfs_set_stack_chunk_stripe_len(chunk
, stripe_len
);
967 btrfs_set_stack_chunk_type(chunk
, type
);
968 btrfs_set_stack_chunk_num_stripes(chunk
, num_stripes
);
969 btrfs_set_stack_chunk_io_align(chunk
, stripe_len
);
970 btrfs_set_stack_chunk_io_width(chunk
, stripe_len
);
971 btrfs_set_stack_chunk_sector_size(chunk
, extent_root
->sectorsize
);
972 btrfs_set_stack_chunk_sub_stripes(chunk
, sub_stripes
);
973 map
->sector_size
= extent_root
->sectorsize
;
974 map
->stripe_len
= stripe_len
;
975 map
->io_align
= stripe_len
;
976 map
->io_width
= stripe_len
;
978 map
->num_stripes
= num_stripes
;
979 map
->sub_stripes
= sub_stripes
;
981 ret
= btrfs_insert_item(trans
, chunk_root
, &key
, chunk
,
982 btrfs_chunk_item_size(num_stripes
));
984 *start
= key
.offset
;;
986 map
->ce
.start
= key
.offset
;
987 map
->ce
.size
= *num_bytes
;
989 ret
= insert_cache_extent(&info
->mapping_tree
.cache_tree
, &map
->ce
);
992 if (type
& BTRFS_BLOCK_GROUP_SYSTEM
) {
993 ret
= btrfs_add_system_chunk(trans
, chunk_root
, &key
,
994 chunk
, btrfs_chunk_item_size(num_stripes
));
1002 int btrfs_alloc_data_chunk(struct btrfs_trans_handle
*trans
,
1003 struct btrfs_root
*extent_root
, u64
*start
,
1004 u64 num_bytes
, u64 type
)
1007 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
1008 struct btrfs_root
*chunk_root
= info
->chunk_root
;
1009 struct btrfs_stripe
*stripes
;
1010 struct btrfs_device
*device
= NULL
;
1011 struct btrfs_chunk
*chunk
;
1012 struct list_head
*dev_list
= &info
->fs_devices
->devices
;
1013 struct list_head
*cur
;
1014 struct map_lookup
*map
;
1015 u64 calc_size
= 8 * 1024 * 1024;
1016 int num_stripes
= 1;
1017 int sub_stripes
= 0;
1020 int stripe_len
= BTRFS_STRIPE_LEN
;
1021 struct btrfs_key key
;
1023 key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
1024 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
1025 ret
= find_next_chunk(chunk_root
, BTRFS_FIRST_CHUNK_TREE_OBJECTID
,
1030 chunk
= kmalloc(btrfs_chunk_item_size(num_stripes
), GFP_NOFS
);
1034 map
= kmalloc(btrfs_map_lookup_size(num_stripes
), GFP_NOFS
);
1040 stripes
= &chunk
->stripe
;
1041 calc_size
= num_bytes
;
1044 cur
= dev_list
->next
;
1045 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
1047 while (index
< num_stripes
) {
1048 struct btrfs_stripe
*stripe
;
1050 ret
= btrfs_alloc_dev_extent(trans
, device
,
1051 info
->chunk_root
->root_key
.objectid
,
1052 BTRFS_FIRST_CHUNK_TREE_OBJECTID
, key
.offset
,
1053 calc_size
, &dev_offset
);
1056 device
->bytes_used
+= calc_size
;
1057 ret
= btrfs_update_device(trans
, device
);
1060 map
->stripes
[index
].dev
= device
;
1061 map
->stripes
[index
].physical
= dev_offset
;
1062 stripe
= stripes
+ index
;
1063 btrfs_set_stack_stripe_devid(stripe
, device
->devid
);
1064 btrfs_set_stack_stripe_offset(stripe
, dev_offset
);
1065 memcpy(stripe
->dev_uuid
, device
->uuid
, BTRFS_UUID_SIZE
);
1069 /* key was set above */
1070 btrfs_set_stack_chunk_length(chunk
, num_bytes
);
1071 btrfs_set_stack_chunk_owner(chunk
, extent_root
->root_key
.objectid
);
1072 btrfs_set_stack_chunk_stripe_len(chunk
, stripe_len
);
1073 btrfs_set_stack_chunk_type(chunk
, type
);
1074 btrfs_set_stack_chunk_num_stripes(chunk
, num_stripes
);
1075 btrfs_set_stack_chunk_io_align(chunk
, stripe_len
);
1076 btrfs_set_stack_chunk_io_width(chunk
, stripe_len
);
1077 btrfs_set_stack_chunk_sector_size(chunk
, extent_root
->sectorsize
);
1078 btrfs_set_stack_chunk_sub_stripes(chunk
, sub_stripes
);
1079 map
->sector_size
= extent_root
->sectorsize
;
1080 map
->stripe_len
= stripe_len
;
1081 map
->io_align
= stripe_len
;
1082 map
->io_width
= stripe_len
;
1084 map
->num_stripes
= num_stripes
;
1085 map
->sub_stripes
= sub_stripes
;
1087 ret
= btrfs_insert_item(trans
, chunk_root
, &key
, chunk
,
1088 btrfs_chunk_item_size(num_stripes
));
1090 *start
= key
.offset
;
1092 map
->ce
.start
= key
.offset
;
1093 map
->ce
.size
= num_bytes
;
1095 ret
= insert_cache_extent(&info
->mapping_tree
.cache_tree
, &map
->ce
);
1102 int btrfs_num_copies(struct btrfs_mapping_tree
*map_tree
, u64 logical
, u64 len
)
1104 struct cache_extent
*ce
;
1105 struct map_lookup
*map
;
1108 ce
= search_cache_extent(&map_tree
->cache_tree
, logical
);
1110 BUG_ON(ce
->start
> logical
|| ce
->start
+ ce
->size
< logical
);
1111 map
= container_of(ce
, struct map_lookup
, ce
);
1113 if (map
->type
& (BTRFS_BLOCK_GROUP_DUP
| BTRFS_BLOCK_GROUP_RAID1
))
1114 ret
= map
->num_stripes
;
1115 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
)
1116 ret
= map
->sub_stripes
;
1117 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID5
)
1119 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID6
)
1126 int btrfs_next_metadata(struct btrfs_mapping_tree
*map_tree
, u64
*logical
,
1129 struct cache_extent
*ce
;
1130 struct map_lookup
*map
;
1132 ce
= search_cache_extent(&map_tree
->cache_tree
, *logical
);
1135 ce
= next_cache_extent(ce
);
1139 map
= container_of(ce
, struct map_lookup
, ce
);
1140 if (map
->type
& BTRFS_BLOCK_GROUP_METADATA
) {
1141 *logical
= ce
->start
;
1150 int btrfs_rmap_block(struct btrfs_mapping_tree
*map_tree
,
1151 u64 chunk_start
, u64 physical
, u64 devid
,
1152 u64
**logical
, int *naddrs
, int *stripe_len
)
1154 struct cache_extent
*ce
;
1155 struct map_lookup
*map
;
1163 ce
= search_cache_extent(&map_tree
->cache_tree
, chunk_start
);
1165 map
= container_of(ce
, struct map_lookup
, ce
);
1168 rmap_len
= map
->stripe_len
;
1169 if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
)
1170 length
= ce
->size
/ (map
->num_stripes
/ map
->sub_stripes
);
1171 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID0
)
1172 length
= ce
->size
/ map
->num_stripes
;
1173 else if (map
->type
& (BTRFS_BLOCK_GROUP_RAID5
|
1174 BTRFS_BLOCK_GROUP_RAID6
)) {
1175 length
= ce
->size
/ nr_data_stripes(map
);
1176 rmap_len
= map
->stripe_len
* nr_data_stripes(map
);
1179 buf
= kzalloc(sizeof(u64
) * map
->num_stripes
, GFP_NOFS
);
1181 for (i
= 0; i
< map
->num_stripes
; i
++) {
1182 if (devid
&& map
->stripes
[i
].dev
->devid
!= devid
)
1184 if (map
->stripes
[i
].physical
> physical
||
1185 map
->stripes
[i
].physical
+ length
<= physical
)
1188 stripe_nr
= (physical
- map
->stripes
[i
].physical
) /
1191 if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
) {
1192 stripe_nr
= (stripe_nr
* map
->num_stripes
+ i
) /
1194 } else if (map
->type
& BTRFS_BLOCK_GROUP_RAID0
) {
1195 stripe_nr
= stripe_nr
* map
->num_stripes
+ i
;
1196 } /* else if RAID[56], multiply by nr_data_stripes().
1197 * Alternatively, just use rmap_len below instead of
1198 * map->stripe_len */
1200 bytenr
= ce
->start
+ stripe_nr
* rmap_len
;
1201 for (j
= 0; j
< nr
; j
++) {
1202 if (buf
[j
] == bytenr
)
1211 *stripe_len
= rmap_len
;
1216 static inline int parity_smaller(u64 a
, u64 b
)
1221 /* Bubble-sort the stripe set to put the parity/syndrome stripes last */
1222 static void sort_parity_stripes(struct btrfs_multi_bio
*bbio
, u64
*raid_map
)
1224 struct btrfs_bio_stripe s
;
1231 for (i
= 0; i
< bbio
->num_stripes
- 1; i
++) {
1232 if (parity_smaller(raid_map
[i
], raid_map
[i
+1])) {
1233 s
= bbio
->stripes
[i
];
1235 bbio
->stripes
[i
] = bbio
->stripes
[i
+1];
1236 raid_map
[i
] = raid_map
[i
+1];
1237 bbio
->stripes
[i
+1] = s
;
1245 int btrfs_map_block(struct btrfs_mapping_tree
*map_tree
, int rw
,
1246 u64 logical
, u64
*length
,
1247 struct btrfs_multi_bio
**multi_ret
, int mirror_num
,
1250 return __btrfs_map_block(map_tree
, rw
, logical
, length
, NULL
,
1251 multi_ret
, mirror_num
, raid_map_ret
);
1254 int __btrfs_map_block(struct btrfs_mapping_tree
*map_tree
, int rw
,
1255 u64 logical
, u64
*length
, u64
*type
,
1256 struct btrfs_multi_bio
**multi_ret
, int mirror_num
,
1259 struct cache_extent
*ce
;
1260 struct map_lookup
*map
;
1264 u64
*raid_map
= NULL
;
1265 int stripes_allocated
= 8;
1266 int stripes_required
= 1;
1269 struct btrfs_multi_bio
*multi
= NULL
;
1271 if (multi_ret
&& rw
== READ
) {
1272 stripes_allocated
= 1;
1275 ce
= search_cache_extent(&map_tree
->cache_tree
, logical
);
1280 if (ce
->start
> logical
|| ce
->start
+ ce
->size
< logical
) {
1286 multi
= kzalloc(btrfs_multi_bio_size(stripes_allocated
),
1291 map
= container_of(ce
, struct map_lookup
, ce
);
1292 offset
= logical
- ce
->start
;
1295 if (map
->type
& (BTRFS_BLOCK_GROUP_RAID1
|
1296 BTRFS_BLOCK_GROUP_DUP
)) {
1297 stripes_required
= map
->num_stripes
;
1298 } else if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
) {
1299 stripes_required
= map
->sub_stripes
;
1302 if (map
->type
& (BTRFS_BLOCK_GROUP_RAID5
| BTRFS_BLOCK_GROUP_RAID6
)
1303 && multi_ret
&& ((rw
& WRITE
) || mirror_num
> 1) && raid_map_ret
) {
1304 /* RAID[56] write or recovery. Return all stripes */
1305 stripes_required
= map
->num_stripes
;
1307 /* Only allocate the map if we've already got a large enough multi_ret */
1308 if (stripes_allocated
>= stripes_required
) {
1309 raid_map
= kmalloc(sizeof(u64
) * map
->num_stripes
, GFP_NOFS
);
1317 /* if our multi bio struct is too small, back off and try again */
1318 if (multi_ret
&& stripes_allocated
< stripes_required
) {
1319 stripes_allocated
= stripes_required
;
1326 * stripe_nr counts the total number of stripes we have to stride
1327 * to get to this block
1329 stripe_nr
= stripe_nr
/ map
->stripe_len
;
1331 stripe_offset
= stripe_nr
* map
->stripe_len
;
1332 BUG_ON(offset
< stripe_offset
);
1334 /* stripe_offset is the offset of this block in its stripe*/
1335 stripe_offset
= offset
- stripe_offset
;
1337 if (map
->type
& (BTRFS_BLOCK_GROUP_RAID0
| BTRFS_BLOCK_GROUP_RAID1
|
1338 BTRFS_BLOCK_GROUP_RAID5
| BTRFS_BLOCK_GROUP_RAID6
|
1339 BTRFS_BLOCK_GROUP_RAID10
|
1340 BTRFS_BLOCK_GROUP_DUP
)) {
1341 /* we limit the length of each bio to what fits in a stripe */
1342 *length
= min_t(u64
, ce
->size
- offset
,
1343 map
->stripe_len
- stripe_offset
);
1345 *length
= ce
->size
- offset
;
1351 multi
->num_stripes
= 1;
1353 if (map
->type
& BTRFS_BLOCK_GROUP_RAID1
) {
1355 multi
->num_stripes
= map
->num_stripes
;
1356 else if (mirror_num
)
1357 stripe_index
= mirror_num
- 1;
1359 stripe_index
= stripe_nr
% map
->num_stripes
;
1360 } else if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
) {
1361 int factor
= map
->num_stripes
/ map
->sub_stripes
;
1363 stripe_index
= stripe_nr
% factor
;
1364 stripe_index
*= map
->sub_stripes
;
1367 multi
->num_stripes
= map
->sub_stripes
;
1368 else if (mirror_num
)
1369 stripe_index
+= mirror_num
- 1;
1371 stripe_nr
= stripe_nr
/ factor
;
1372 } else if (map
->type
& BTRFS_BLOCK_GROUP_DUP
) {
1374 multi
->num_stripes
= map
->num_stripes
;
1375 else if (mirror_num
)
1376 stripe_index
= mirror_num
- 1;
1377 } else if (map
->type
& (BTRFS_BLOCK_GROUP_RAID5
|
1378 BTRFS_BLOCK_GROUP_RAID6
)) {
1383 u64 raid56_full_stripe_start
;
1384 u64 full_stripe_len
= nr_data_stripes(map
) * map
->stripe_len
;
1387 * align the start of our data stripe in the logical
1390 raid56_full_stripe_start
= offset
/ full_stripe_len
;
1391 raid56_full_stripe_start
*= full_stripe_len
;
1393 /* get the data stripe number */
1394 stripe_nr
= raid56_full_stripe_start
/ map
->stripe_len
;
1395 stripe_nr
= stripe_nr
/ nr_data_stripes(map
);
1397 /* Work out the disk rotation on this stripe-set */
1398 rot
= stripe_nr
% map
->num_stripes
;
1400 /* Fill in the logical address of each stripe */
1401 tmp
= stripe_nr
* nr_data_stripes(map
);
1403 for (i
= 0; i
< nr_data_stripes(map
); i
++)
1404 raid_map
[(i
+rot
) % map
->num_stripes
] =
1405 ce
->start
+ (tmp
+ i
) * map
->stripe_len
;
1407 raid_map
[(i
+rot
) % map
->num_stripes
] = BTRFS_RAID5_P_STRIPE
;
1408 if (map
->type
& BTRFS_BLOCK_GROUP_RAID6
)
1409 raid_map
[(i
+rot
+1) % map
->num_stripes
] = BTRFS_RAID6_Q_STRIPE
;
1411 *length
= map
->stripe_len
;
1414 multi
->num_stripes
= map
->num_stripes
;
1416 stripe_index
= stripe_nr
% nr_data_stripes(map
);
1417 stripe_nr
= stripe_nr
/ nr_data_stripes(map
);
1420 * Mirror #0 or #1 means the original data block.
1421 * Mirror #2 is RAID5 parity block.
1422 * Mirror #3 is RAID6 Q block.
1425 stripe_index
= nr_data_stripes(map
) + mirror_num
- 2;
1427 /* We distribute the parity blocks across stripes */
1428 stripe_index
= (stripe_nr
+ stripe_index
) % map
->num_stripes
;
1432 * after this do_div call, stripe_nr is the number of stripes
1433 * on this device we have to walk to find the data, and
1434 * stripe_index is the number of our device in the stripe array
1436 stripe_index
= stripe_nr
% map
->num_stripes
;
1437 stripe_nr
= stripe_nr
/ map
->num_stripes
;
1439 BUG_ON(stripe_index
>= map
->num_stripes
);
1441 for (i
= 0; i
< multi
->num_stripes
; i
++) {
1442 multi
->stripes
[i
].physical
=
1443 map
->stripes
[stripe_index
].physical
+ stripe_offset
+
1444 stripe_nr
* map
->stripe_len
;
1445 multi
->stripes
[i
].dev
= map
->stripes
[stripe_index
].dev
;
1454 sort_parity_stripes(multi
, raid_map
);
1455 *raid_map_ret
= raid_map
;
1461 struct btrfs_device
*btrfs_find_device(struct btrfs_root
*root
, u64 devid
,
1464 struct btrfs_device
*device
;
1465 struct btrfs_fs_devices
*cur_devices
;
1467 cur_devices
= root
->fs_info
->fs_devices
;
1468 while (cur_devices
) {
1470 !memcmp(cur_devices
->fsid
, fsid
, BTRFS_UUID_SIZE
)) {
1471 device
= __find_device(&cur_devices
->devices
,
1476 cur_devices
= cur_devices
->seed
;
1481 struct btrfs_device
*
1482 btrfs_find_device_by_devid(struct btrfs_fs_devices
*fs_devices
,
1483 u64 devid
, int instance
)
1485 struct list_head
*head
= &fs_devices
->devices
;
1486 struct btrfs_device
*dev
;
1489 list_for_each_entry(dev
, head
, dev_list
) {
1490 if (dev
->devid
== devid
&& num_found
++ == instance
)
1496 int btrfs_chunk_readonly(struct btrfs_root
*root
, u64 chunk_offset
)
1498 struct cache_extent
*ce
;
1499 struct map_lookup
*map
;
1500 struct btrfs_mapping_tree
*map_tree
= &root
->fs_info
->mapping_tree
;
1505 * During chunk recovering, we may fail to find block group's
1506 * corresponding chunk, we will rebuild it later
1508 ce
= search_cache_extent(&map_tree
->cache_tree
, chunk_offset
);
1509 if (!root
->fs_info
->is_chunk_recover
)
1514 map
= container_of(ce
, struct map_lookup
, ce
);
1515 for (i
= 0; i
< map
->num_stripes
; i
++) {
1516 if (!map
->stripes
[i
].dev
->writeable
) {
1525 static struct btrfs_device
*fill_missing_device(u64 devid
)
1527 struct btrfs_device
*device
;
1529 device
= kzalloc(sizeof(*device
), GFP_NOFS
);
1530 device
->devid
= devid
;
1535 static int read_one_chunk(struct btrfs_root
*root
, struct btrfs_key
*key
,
1536 struct extent_buffer
*leaf
,
1537 struct btrfs_chunk
*chunk
)
1539 struct btrfs_mapping_tree
*map_tree
= &root
->fs_info
->mapping_tree
;
1540 struct map_lookup
*map
;
1541 struct cache_extent
*ce
;
1545 u8 uuid
[BTRFS_UUID_SIZE
];
1550 logical
= key
->offset
;
1551 length
= btrfs_chunk_length(leaf
, chunk
);
1553 ce
= search_cache_extent(&map_tree
->cache_tree
, logical
);
1555 /* already mapped? */
1556 if (ce
&& ce
->start
<= logical
&& ce
->start
+ ce
->size
> logical
) {
1560 num_stripes
= btrfs_chunk_num_stripes(leaf
, chunk
);
1561 map
= kmalloc(btrfs_map_lookup_size(num_stripes
), GFP_NOFS
);
1565 map
->ce
.start
= logical
;
1566 map
->ce
.size
= length
;
1567 map
->num_stripes
= num_stripes
;
1568 map
->io_width
= btrfs_chunk_io_width(leaf
, chunk
);
1569 map
->io_align
= btrfs_chunk_io_align(leaf
, chunk
);
1570 map
->sector_size
= btrfs_chunk_sector_size(leaf
, chunk
);
1571 map
->stripe_len
= btrfs_chunk_stripe_len(leaf
, chunk
);
1572 map
->type
= btrfs_chunk_type(leaf
, chunk
);
1573 map
->sub_stripes
= btrfs_chunk_sub_stripes(leaf
, chunk
);
1575 for (i
= 0; i
< num_stripes
; i
++) {
1576 map
->stripes
[i
].physical
=
1577 btrfs_stripe_offset_nr(leaf
, chunk
, i
);
1578 devid
= btrfs_stripe_devid_nr(leaf
, chunk
, i
);
1579 read_extent_buffer(leaf
, uuid
, (unsigned long)
1580 btrfs_stripe_dev_uuid_nr(chunk
, i
),
1582 map
->stripes
[i
].dev
= btrfs_find_device(root
, devid
, uuid
,
1584 if (!map
->stripes
[i
].dev
) {
1585 map
->stripes
[i
].dev
= fill_missing_device(devid
);
1586 printf("warning, device %llu is missing\n",
1587 (unsigned long long)devid
);
1591 ret
= insert_cache_extent(&map_tree
->cache_tree
, &map
->ce
);
1597 static int fill_device_from_item(struct extent_buffer
*leaf
,
1598 struct btrfs_dev_item
*dev_item
,
1599 struct btrfs_device
*device
)
1603 device
->devid
= btrfs_device_id(leaf
, dev_item
);
1604 device
->total_bytes
= btrfs_device_total_bytes(leaf
, dev_item
);
1605 device
->bytes_used
= btrfs_device_bytes_used(leaf
, dev_item
);
1606 device
->type
= btrfs_device_type(leaf
, dev_item
);
1607 device
->io_align
= btrfs_device_io_align(leaf
, dev_item
);
1608 device
->io_width
= btrfs_device_io_width(leaf
, dev_item
);
1609 device
->sector_size
= btrfs_device_sector_size(leaf
, dev_item
);
1611 ptr
= (unsigned long)btrfs_device_uuid(dev_item
);
1612 read_extent_buffer(leaf
, device
->uuid
, ptr
, BTRFS_UUID_SIZE
);
1617 static int open_seed_devices(struct btrfs_root
*root
, u8
*fsid
)
1619 struct btrfs_fs_devices
*fs_devices
;
1622 fs_devices
= root
->fs_info
->fs_devices
->seed
;
1623 while (fs_devices
) {
1624 if (!memcmp(fs_devices
->fsid
, fsid
, BTRFS_UUID_SIZE
)) {
1628 fs_devices
= fs_devices
->seed
;
1631 fs_devices
= find_fsid(fsid
);
1637 ret
= btrfs_open_devices(fs_devices
, O_RDONLY
);
1641 fs_devices
->seed
= root
->fs_info
->fs_devices
->seed
;
1642 root
->fs_info
->fs_devices
->seed
= fs_devices
;
1647 static int read_one_dev(struct btrfs_root
*root
,
1648 struct extent_buffer
*leaf
,
1649 struct btrfs_dev_item
*dev_item
)
1651 struct btrfs_device
*device
;
1654 u8 fs_uuid
[BTRFS_UUID_SIZE
];
1655 u8 dev_uuid
[BTRFS_UUID_SIZE
];
1657 devid
= btrfs_device_id(leaf
, dev_item
);
1658 read_extent_buffer(leaf
, dev_uuid
,
1659 (unsigned long)btrfs_device_uuid(dev_item
),
1661 read_extent_buffer(leaf
, fs_uuid
,
1662 (unsigned long)btrfs_device_fsid(dev_item
),
1665 if (memcmp(fs_uuid
, root
->fs_info
->fsid
, BTRFS_UUID_SIZE
)) {
1666 ret
= open_seed_devices(root
, fs_uuid
);
1671 device
= btrfs_find_device(root
, devid
, dev_uuid
, fs_uuid
);
1673 printk("warning devid %llu not found already\n",
1674 (unsigned long long)devid
);
1675 device
= kzalloc(sizeof(*device
), GFP_NOFS
);
1679 list_add(&device
->dev_list
,
1680 &root
->fs_info
->fs_devices
->devices
);
1683 fill_device_from_item(leaf
, dev_item
, device
);
1684 device
->dev_root
= root
->fs_info
->dev_root
;
1688 int btrfs_read_sys_array(struct btrfs_root
*root
)
1690 struct btrfs_super_block
*super_copy
= root
->fs_info
->super_copy
;
1691 struct extent_buffer
*sb
;
1692 struct btrfs_disk_key
*disk_key
;
1693 struct btrfs_chunk
*chunk
;
1694 struct btrfs_key key
;
1701 sb
= btrfs_find_create_tree_block(root
, BTRFS_SUPER_INFO_OFFSET
,
1702 BTRFS_SUPER_INFO_SIZE
);
1705 btrfs_set_buffer_uptodate(sb
);
1706 write_extent_buffer(sb
, super_copy
, 0, sizeof(*super_copy
));
1707 array_end
= ((u8
*)super_copy
->sys_chunk_array
) +
1708 btrfs_super_sys_array_size(super_copy
);
1711 * we do this loop twice, once for the device items and
1712 * once for all of the chunks. This way there are device
1713 * structs filled in for every chunk
1715 ptr
= super_copy
->sys_chunk_array
;
1717 while (ptr
< array_end
) {
1718 disk_key
= (struct btrfs_disk_key
*)ptr
;
1719 btrfs_disk_key_to_cpu(&key
, disk_key
);
1721 len
= sizeof(*disk_key
);
1724 if (key
.type
== BTRFS_CHUNK_ITEM_KEY
) {
1725 chunk
= (struct btrfs_chunk
*)(ptr
- (u8
*)super_copy
);
1726 ret
= read_one_chunk(root
, &key
, sb
, chunk
);
1729 num_stripes
= btrfs_chunk_num_stripes(sb
, chunk
);
1730 len
= btrfs_chunk_item_size(num_stripes
);
1736 free_extent_buffer(sb
);
1740 int btrfs_read_chunk_tree(struct btrfs_root
*root
)
1742 struct btrfs_path
*path
;
1743 struct extent_buffer
*leaf
;
1744 struct btrfs_key key
;
1745 struct btrfs_key found_key
;
1749 root
= root
->fs_info
->chunk_root
;
1751 path
= btrfs_alloc_path();
1756 * Read all device items, and then all the chunk items. All
1757 * device items are found before any chunk item (their object id
1758 * is smaller than the lowest possible object id for a chunk
1759 * item - BTRFS_FIRST_CHUNK_TREE_OBJECTID).
1761 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
1764 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
1768 leaf
= path
->nodes
[0];
1769 slot
= path
->slots
[0];
1770 if (slot
>= btrfs_header_nritems(leaf
)) {
1771 ret
= btrfs_next_leaf(root
, path
);
1778 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
1779 if (found_key
.type
== BTRFS_DEV_ITEM_KEY
) {
1780 struct btrfs_dev_item
*dev_item
;
1781 dev_item
= btrfs_item_ptr(leaf
, slot
,
1782 struct btrfs_dev_item
);
1783 ret
= read_one_dev(root
, leaf
, dev_item
);
1785 } else if (found_key
.type
== BTRFS_CHUNK_ITEM_KEY
) {
1786 struct btrfs_chunk
*chunk
;
1787 chunk
= btrfs_item_ptr(leaf
, slot
, struct btrfs_chunk
);
1788 ret
= read_one_chunk(root
, &found_key
, leaf
, chunk
);
1796 btrfs_free_path(path
);
1800 struct list_head
*btrfs_scanned_uuids(void)
1805 static int rmw_eb(struct btrfs_fs_info
*info
,
1806 struct extent_buffer
*eb
, struct extent_buffer
*orig_eb
)
1809 unsigned long orig_off
= 0;
1810 unsigned long dest_off
= 0;
1811 unsigned long copy_len
= eb
->len
;
1813 ret
= read_whole_eb(info
, eb
, 0);
1817 if (eb
->start
+ eb
->len
<= orig_eb
->start
||
1818 eb
->start
>= orig_eb
->start
+ orig_eb
->len
)
1821 * | ----- orig_eb ------- |
1822 * | ----- stripe ------- |
1823 * | ----- orig_eb ------- |
1824 * | ----- orig_eb ------- |
1826 if (eb
->start
> orig_eb
->start
)
1827 orig_off
= eb
->start
- orig_eb
->start
;
1828 if (orig_eb
->start
> eb
->start
)
1829 dest_off
= orig_eb
->start
- eb
->start
;
1831 if (copy_len
> orig_eb
->len
- orig_off
)
1832 copy_len
= orig_eb
->len
- orig_off
;
1833 if (copy_len
> eb
->len
- dest_off
)
1834 copy_len
= eb
->len
- dest_off
;
1836 memcpy(eb
->data
+ dest_off
, orig_eb
->data
+ orig_off
, copy_len
);
1840 static void split_eb_for_raid56(struct btrfs_fs_info
*info
,
1841 struct extent_buffer
*orig_eb
,
1842 struct extent_buffer
**ebs
,
1843 u64 stripe_len
, u64
*raid_map
,
1846 struct extent_buffer
*eb
;
1847 u64 start
= orig_eb
->start
;
1852 for (i
= 0; i
< num_stripes
; i
++) {
1853 if (raid_map
[i
] >= BTRFS_RAID5_P_STRIPE
)
1856 eb
= malloc(sizeof(struct extent_buffer
) + stripe_len
);
1859 memset(eb
, 0, sizeof(struct extent_buffer
) + stripe_len
);
1861 eb
->start
= raid_map
[i
];
1862 eb
->len
= stripe_len
;
1866 eb
->dev_bytenr
= (u64
)-1;
1868 this_eb_start
= raid_map
[i
];
1870 if (start
> this_eb_start
||
1871 start
+ orig_eb
->len
< this_eb_start
+ stripe_len
) {
1872 ret
= rmw_eb(info
, eb
, orig_eb
);
1875 memcpy(eb
->data
, orig_eb
->data
+ eb
->start
- start
, stripe_len
);
1881 int write_raid56_with_parity(struct btrfs_fs_info
*info
,
1882 struct extent_buffer
*eb
,
1883 struct btrfs_multi_bio
*multi
,
1884 u64 stripe_len
, u64
*raid_map
)
1886 struct extent_buffer
**ebs
, *p_eb
= NULL
, *q_eb
= NULL
;
1890 int alloc_size
= eb
->len
;
1892 ebs
= kmalloc(sizeof(*ebs
) * multi
->num_stripes
, GFP_NOFS
);
1895 if (stripe_len
> alloc_size
)
1896 alloc_size
= stripe_len
;
1898 split_eb_for_raid56(info
, eb
, ebs
, stripe_len
, raid_map
,
1899 multi
->num_stripes
);
1901 for (i
= 0; i
< multi
->num_stripes
; i
++) {
1902 struct extent_buffer
*new_eb
;
1903 if (raid_map
[i
] < BTRFS_RAID5_P_STRIPE
) {
1904 ebs
[i
]->dev_bytenr
= multi
->stripes
[i
].physical
;
1905 ebs
[i
]->fd
= multi
->stripes
[i
].dev
->fd
;
1906 multi
->stripes
[i
].dev
->total_ios
++;
1907 BUG_ON(ebs
[i
]->start
!= raid_map
[i
]);
1910 new_eb
= kmalloc(sizeof(*eb
) + alloc_size
, GFP_NOFS
);
1912 new_eb
->dev_bytenr
= multi
->stripes
[i
].physical
;
1913 new_eb
->fd
= multi
->stripes
[i
].dev
->fd
;
1914 multi
->stripes
[i
].dev
->total_ios
++;
1915 new_eb
->len
= stripe_len
;
1917 if (raid_map
[i
] == BTRFS_RAID5_P_STRIPE
)
1919 else if (raid_map
[i
] == BTRFS_RAID6_Q_STRIPE
)
1925 pointers
= kmalloc(sizeof(*pointers
) * multi
->num_stripes
,
1929 ebs
[multi
->num_stripes
- 2] = p_eb
;
1930 ebs
[multi
->num_stripes
- 1] = q_eb
;
1932 for (i
= 0; i
< multi
->num_stripes
; i
++)
1933 pointers
[i
] = ebs
[i
]->data
;
1935 raid6_gen_syndrome(multi
->num_stripes
, stripe_len
, pointers
);
1938 ebs
[multi
->num_stripes
- 1] = p_eb
;
1939 memcpy(p_eb
->data
, ebs
[0]->data
, stripe_len
);
1940 for (j
= 1; j
< multi
->num_stripes
- 1; j
++) {
1941 for (i
= 0; i
< stripe_len
; i
+= sizeof(unsigned long)) {
1942 *(unsigned long *)(p_eb
->data
+ i
) ^=
1943 *(unsigned long *)(ebs
[j
]->data
+ i
);
1948 for (i
= 0; i
< multi
->num_stripes
; i
++) {
1949 ret
= write_extent_to_disk(ebs
[i
]);