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.
20 #include <sys/types.h>
22 #include <uuid/uuid.h>
27 #include "transaction.h"
28 #include "print-tree.h"
33 struct btrfs_device
*dev
;
37 static inline int nr_parity_stripes(struct map_lookup
*map
)
39 if (map
->type
& BTRFS_BLOCK_GROUP_RAID5
)
41 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID6
)
47 static inline int nr_data_stripes(struct map_lookup
*map
)
49 return map
->num_stripes
- nr_parity_stripes(map
);
52 #define is_parity_stripe(x) ( ((x) == BTRFS_RAID5_P_STRIPE) || ((x) == BTRFS_RAID6_Q_STRIPE) )
54 static LIST_HEAD(fs_uuids
);
56 static struct btrfs_device
*__find_device(struct list_head
*head
, u64 devid
,
59 struct btrfs_device
*dev
;
60 struct list_head
*cur
;
62 list_for_each(cur
, head
) {
63 dev
= list_entry(cur
, struct btrfs_device
, dev_list
);
64 if (dev
->devid
== devid
&&
65 !memcmp(dev
->uuid
, uuid
, BTRFS_UUID_SIZE
)) {
72 static struct btrfs_fs_devices
*find_fsid(u8
*fsid
)
74 struct list_head
*cur
;
75 struct btrfs_fs_devices
*fs_devices
;
77 list_for_each(cur
, &fs_uuids
) {
78 fs_devices
= list_entry(cur
, struct btrfs_fs_devices
, list
);
79 if (memcmp(fsid
, fs_devices
->fsid
, BTRFS_FSID_SIZE
) == 0)
85 static int device_list_add(const char *path
,
86 struct btrfs_super_block
*disk_super
,
87 u64 devid
, struct btrfs_fs_devices
**fs_devices_ret
)
89 struct btrfs_device
*device
;
90 struct btrfs_fs_devices
*fs_devices
;
91 u64 found_transid
= btrfs_super_generation(disk_super
);
93 fs_devices
= find_fsid(disk_super
->fsid
);
95 fs_devices
= kzalloc(sizeof(*fs_devices
), GFP_NOFS
);
98 INIT_LIST_HEAD(&fs_devices
->devices
);
99 list_add(&fs_devices
->list
, &fs_uuids
);
100 memcpy(fs_devices
->fsid
, disk_super
->fsid
, BTRFS_FSID_SIZE
);
101 fs_devices
->latest_devid
= devid
;
102 fs_devices
->latest_trans
= found_transid
;
103 fs_devices
->lowest_devid
= (u64
)-1;
106 device
= __find_device(&fs_devices
->devices
, devid
,
107 disk_super
->dev_item
.uuid
);
110 device
= kzalloc(sizeof(*device
), GFP_NOFS
);
112 /* we can safely leave the fs_devices entry around */
116 device
->devid
= devid
;
117 device
->generation
= found_transid
;
118 memcpy(device
->uuid
, disk_super
->dev_item
.uuid
,
120 device
->name
= kstrdup(path
, GFP_NOFS
);
125 device
->label
= kstrdup(disk_super
->label
, GFP_NOFS
);
126 if (!device
->label
) {
131 device
->total_devs
= btrfs_super_num_devices(disk_super
);
132 device
->super_bytes_used
= btrfs_super_bytes_used(disk_super
);
133 device
->total_bytes
=
134 btrfs_stack_device_total_bytes(&disk_super
->dev_item
);
136 btrfs_stack_device_bytes_used(&disk_super
->dev_item
);
137 list_add(&device
->dev_list
, &fs_devices
->devices
);
138 device
->fs_devices
= fs_devices
;
139 } else if (!device
->name
|| strcmp(device
->name
, path
)) {
140 char *name
= strdup(path
);
148 if (found_transid
> fs_devices
->latest_trans
) {
149 fs_devices
->latest_devid
= devid
;
150 fs_devices
->latest_trans
= found_transid
;
152 if (fs_devices
->lowest_devid
> devid
) {
153 fs_devices
->lowest_devid
= devid
;
155 *fs_devices_ret
= fs_devices
;
159 int btrfs_close_devices(struct btrfs_fs_devices
*fs_devices
)
161 struct btrfs_fs_devices
*seed_devices
;
162 struct btrfs_device
*device
;
167 while (!list_empty(&fs_devices
->devices
)) {
168 device
= list_entry(fs_devices
->devices
.next
,
169 struct btrfs_device
, dev_list
);
170 if (device
->fd
!= -1) {
172 if (posix_fadvise(device
->fd
, 0, 0, POSIX_FADV_DONTNEED
))
173 fprintf(stderr
, "Warning, could not drop caches\n");
177 device
->writeable
= 0;
178 list_del(&device
->dev_list
);
179 /* free the memory */
185 seed_devices
= fs_devices
->seed
;
186 fs_devices
->seed
= NULL
;
188 struct btrfs_fs_devices
*orig
;
191 fs_devices
= seed_devices
;
192 list_del(&orig
->list
);
196 list_del(&fs_devices
->list
);
203 void btrfs_close_all_devices(void)
205 struct btrfs_fs_devices
*fs_devices
;
207 while (!list_empty(&fs_uuids
)) {
208 fs_devices
= list_entry(fs_uuids
.next
, struct btrfs_fs_devices
,
210 btrfs_close_devices(fs_devices
);
214 int btrfs_open_devices(struct btrfs_fs_devices
*fs_devices
, int flags
)
217 struct list_head
*head
= &fs_devices
->devices
;
218 struct list_head
*cur
;
219 struct btrfs_device
*device
;
222 list_for_each(cur
, head
) {
223 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
225 printk("no name for device %llu, skip it now\n", device
->devid
);
229 fd
= open(device
->name
, flags
);
232 error("cannot open device '%s': %s", device
->name
,
237 if (posix_fadvise(fd
, 0, 0, POSIX_FADV_DONTNEED
))
238 fprintf(stderr
, "Warning, could not drop caches\n");
240 if (device
->devid
== fs_devices
->latest_devid
)
241 fs_devices
->latest_bdev
= fd
;
242 if (device
->devid
== fs_devices
->lowest_devid
)
243 fs_devices
->lowest_bdev
= fd
;
246 device
->writeable
= 1;
250 btrfs_close_devices(fs_devices
);
254 int btrfs_scan_one_device(int fd
, const char *path
,
255 struct btrfs_fs_devices
**fs_devices_ret
,
256 u64
*total_devs
, u64 super_offset
, unsigned sbflags
)
258 struct btrfs_super_block
*disk_super
;
259 char buf
[BTRFS_SUPER_INFO_SIZE
];
263 disk_super
= (struct btrfs_super_block
*)buf
;
264 ret
= btrfs_read_dev_super(fd
, disk_super
, super_offset
, sbflags
);
267 devid
= btrfs_stack_device_id(&disk_super
->dev_item
);
268 if (btrfs_super_flags(disk_super
) & BTRFS_SUPER_FLAG_METADUMP
)
271 *total_devs
= btrfs_super_num_devices(disk_super
);
273 ret
= device_list_add(path
, disk_super
, devid
, fs_devices_ret
);
279 * find_free_dev_extent_start - find free space in the specified device
280 * @device: the device which we search the free space in
281 * @num_bytes: the size of the free space that we need
282 * @search_start: the position from which to begin the search
283 * @start: store the start of the free space.
284 * @len: the size of the free space. that we find, or the size
285 * of the max free space if we don't find suitable free space
287 * this uses a pretty simple search, the expectation is that it is
288 * called very infrequently and that a given device has a small number
291 * @start is used to store the start of the free space if we find. But if we
292 * don't find suitable free space, it will be used to store the start position
293 * of the max free space.
295 * @len is used to store the size of the free space that we find.
296 * But if we don't find suitable free space, it is used to store the size of
297 * the max free space.
299 static int find_free_dev_extent_start(struct btrfs_trans_handle
*trans
,
300 struct btrfs_device
*device
, u64 num_bytes
,
301 u64 search_start
, u64
*start
, u64
*len
)
303 struct btrfs_key key
;
304 struct btrfs_root
*root
= device
->dev_root
;
305 struct btrfs_dev_extent
*dev_extent
;
306 struct btrfs_path
*path
;
311 u64 search_end
= device
->total_bytes
;
314 struct extent_buffer
*l
;
315 u64 min_search_start
;
318 * We don't want to overwrite the superblock on the drive nor any area
319 * used by the boot loader (grub for example), so we make sure to start
320 * at an offset of at least 1MB.
322 min_search_start
= max(root
->fs_info
->alloc_start
, (u64
)SZ_1M
);
323 search_start
= max(search_start
, min_search_start
);
325 path
= btrfs_alloc_path();
329 max_hole_start
= search_start
;
332 if (search_start
>= search_end
) {
339 key
.objectid
= device
->devid
;
340 key
.offset
= search_start
;
341 key
.type
= BTRFS_DEV_EXTENT_KEY
;
343 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
347 ret
= btrfs_previous_item(root
, path
, key
.objectid
, key
.type
);
354 slot
= path
->slots
[0];
355 if (slot
>= btrfs_header_nritems(l
)) {
356 ret
= btrfs_next_leaf(root
, path
);
364 btrfs_item_key_to_cpu(l
, &key
, slot
);
366 if (key
.objectid
< device
->devid
)
369 if (key
.objectid
> device
->devid
)
372 if (key
.type
!= BTRFS_DEV_EXTENT_KEY
)
375 if (key
.offset
> search_start
) {
376 hole_size
= key
.offset
- search_start
;
379 * Have to check before we set max_hole_start, otherwise
380 * we could end up sending back this offset anyway.
382 if (hole_size
> max_hole_size
) {
383 max_hole_start
= search_start
;
384 max_hole_size
= hole_size
;
388 * If this free space is greater than which we need,
389 * it must be the max free space that we have found
390 * until now, so max_hole_start must point to the start
391 * of this free space and the length of this free space
392 * is stored in max_hole_size. Thus, we return
393 * max_hole_start and max_hole_size and go back to the
396 if (hole_size
>= num_bytes
) {
402 dev_extent
= btrfs_item_ptr(l
, slot
, struct btrfs_dev_extent
);
403 extent_end
= key
.offset
+ btrfs_dev_extent_length(l
,
405 if (extent_end
> search_start
)
406 search_start
= extent_end
;
413 * At this point, search_start should be the end of
414 * allocated dev extents, and when shrinking the device,
415 * search_end may be smaller than search_start.
417 if (search_end
> search_start
) {
418 hole_size
= search_end
- search_start
;
420 if (hole_size
> max_hole_size
) {
421 max_hole_start
= search_start
;
422 max_hole_size
= hole_size
;
427 if (max_hole_size
< num_bytes
)
433 btrfs_free_path(path
);
434 *start
= max_hole_start
;
436 *len
= max_hole_size
;
440 int find_free_dev_extent(struct btrfs_trans_handle
*trans
,
441 struct btrfs_device
*device
, u64 num_bytes
,
444 /* FIXME use last free of some kind */
445 return find_free_dev_extent_start(trans
, device
,
446 num_bytes
, 0, start
, NULL
);
449 static int btrfs_alloc_dev_extent(struct btrfs_trans_handle
*trans
,
450 struct btrfs_device
*device
,
451 u64 chunk_tree
, u64 chunk_objectid
,
453 u64 num_bytes
, u64
*start
, int convert
)
456 struct btrfs_path
*path
;
457 struct btrfs_root
*root
= device
->dev_root
;
458 struct btrfs_dev_extent
*extent
;
459 struct extent_buffer
*leaf
;
460 struct btrfs_key key
;
462 path
= btrfs_alloc_path();
467 * For convert case, just skip search free dev_extent, as caller
468 * is responsible to make sure it's free.
471 ret
= find_free_dev_extent(trans
, device
, num_bytes
,
477 key
.objectid
= device
->devid
;
479 key
.type
= BTRFS_DEV_EXTENT_KEY
;
480 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
484 leaf
= path
->nodes
[0];
485 extent
= btrfs_item_ptr(leaf
, path
->slots
[0],
486 struct btrfs_dev_extent
);
487 btrfs_set_dev_extent_chunk_tree(leaf
, extent
, chunk_tree
);
488 btrfs_set_dev_extent_chunk_objectid(leaf
, extent
, chunk_objectid
);
489 btrfs_set_dev_extent_chunk_offset(leaf
, extent
, chunk_offset
);
491 write_extent_buffer(leaf
, root
->fs_info
->chunk_tree_uuid
,
492 (unsigned long)btrfs_dev_extent_chunk_tree_uuid(extent
),
495 btrfs_set_dev_extent_length(leaf
, extent
, num_bytes
);
496 btrfs_mark_buffer_dirty(leaf
);
498 btrfs_free_path(path
);
502 static int find_next_chunk(struct btrfs_root
*root
, u64 objectid
, u64
*offset
)
504 struct btrfs_path
*path
;
506 struct btrfs_key key
;
507 struct btrfs_chunk
*chunk
;
508 struct btrfs_key found_key
;
510 path
= btrfs_alloc_path();
514 key
.objectid
= objectid
;
515 key
.offset
= (u64
)-1;
516 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
518 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
524 ret
= btrfs_previous_item(root
, path
, 0, BTRFS_CHUNK_ITEM_KEY
);
528 btrfs_item_key_to_cpu(path
->nodes
[0], &found_key
,
530 if (found_key
.objectid
!= objectid
)
533 chunk
= btrfs_item_ptr(path
->nodes
[0], path
->slots
[0],
535 *offset
= found_key
.offset
+
536 btrfs_chunk_length(path
->nodes
[0], chunk
);
541 btrfs_free_path(path
);
545 static int find_next_devid(struct btrfs_root
*root
, struct btrfs_path
*path
,
549 struct btrfs_key key
;
550 struct btrfs_key found_key
;
552 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
553 key
.type
= BTRFS_DEV_ITEM_KEY
;
554 key
.offset
= (u64
)-1;
556 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
562 ret
= btrfs_previous_item(root
, path
, BTRFS_DEV_ITEMS_OBJECTID
,
567 btrfs_item_key_to_cpu(path
->nodes
[0], &found_key
,
569 *objectid
= found_key
.offset
+ 1;
573 btrfs_release_path(path
);
578 * the device information is stored in the chunk root
579 * the btrfs_device struct should be fully filled in
581 int btrfs_add_device(struct btrfs_trans_handle
*trans
,
582 struct btrfs_root
*root
,
583 struct btrfs_device
*device
)
586 struct btrfs_path
*path
;
587 struct btrfs_dev_item
*dev_item
;
588 struct extent_buffer
*leaf
;
589 struct btrfs_key key
;
593 root
= root
->fs_info
->chunk_root
;
595 path
= btrfs_alloc_path();
599 ret
= find_next_devid(root
, path
, &free_devid
);
603 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
604 key
.type
= BTRFS_DEV_ITEM_KEY
;
605 key
.offset
= free_devid
;
607 ret
= btrfs_insert_empty_item(trans
, root
, path
, &key
,
612 leaf
= path
->nodes
[0];
613 dev_item
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_dev_item
);
615 device
->devid
= free_devid
;
616 btrfs_set_device_id(leaf
, dev_item
, device
->devid
);
617 btrfs_set_device_generation(leaf
, dev_item
, 0);
618 btrfs_set_device_type(leaf
, dev_item
, device
->type
);
619 btrfs_set_device_io_align(leaf
, dev_item
, device
->io_align
);
620 btrfs_set_device_io_width(leaf
, dev_item
, device
->io_width
);
621 btrfs_set_device_sector_size(leaf
, dev_item
, device
->sector_size
);
622 btrfs_set_device_total_bytes(leaf
, dev_item
, device
->total_bytes
);
623 btrfs_set_device_bytes_used(leaf
, dev_item
, device
->bytes_used
);
624 btrfs_set_device_group(leaf
, dev_item
, 0);
625 btrfs_set_device_seek_speed(leaf
, dev_item
, 0);
626 btrfs_set_device_bandwidth(leaf
, dev_item
, 0);
627 btrfs_set_device_start_offset(leaf
, dev_item
, 0);
629 ptr
= (unsigned long)btrfs_device_uuid(dev_item
);
630 write_extent_buffer(leaf
, device
->uuid
, ptr
, BTRFS_UUID_SIZE
);
631 ptr
= (unsigned long)btrfs_device_fsid(dev_item
);
632 write_extent_buffer(leaf
, root
->fs_info
->fsid
, ptr
, BTRFS_UUID_SIZE
);
633 btrfs_mark_buffer_dirty(leaf
);
637 btrfs_free_path(path
);
641 int btrfs_update_device(struct btrfs_trans_handle
*trans
,
642 struct btrfs_device
*device
)
645 struct btrfs_path
*path
;
646 struct btrfs_root
*root
;
647 struct btrfs_dev_item
*dev_item
;
648 struct extent_buffer
*leaf
;
649 struct btrfs_key key
;
651 root
= device
->dev_root
->fs_info
->chunk_root
;
653 path
= btrfs_alloc_path();
657 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
658 key
.type
= BTRFS_DEV_ITEM_KEY
;
659 key
.offset
= device
->devid
;
661 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 1);
670 leaf
= path
->nodes
[0];
671 dev_item
= btrfs_item_ptr(leaf
, path
->slots
[0], struct btrfs_dev_item
);
673 btrfs_set_device_id(leaf
, dev_item
, device
->devid
);
674 btrfs_set_device_type(leaf
, dev_item
, device
->type
);
675 btrfs_set_device_io_align(leaf
, dev_item
, device
->io_align
);
676 btrfs_set_device_io_width(leaf
, dev_item
, device
->io_width
);
677 btrfs_set_device_sector_size(leaf
, dev_item
, device
->sector_size
);
678 btrfs_set_device_total_bytes(leaf
, dev_item
, device
->total_bytes
);
679 btrfs_set_device_bytes_used(leaf
, dev_item
, device
->bytes_used
);
680 btrfs_mark_buffer_dirty(leaf
);
683 btrfs_free_path(path
);
687 int btrfs_add_system_chunk(struct btrfs_root
*root
,
688 struct btrfs_key
*key
,
689 struct btrfs_chunk
*chunk
, int item_size
)
691 struct btrfs_super_block
*super_copy
= root
->fs_info
->super_copy
;
692 struct btrfs_disk_key disk_key
;
696 array_size
= btrfs_super_sys_array_size(super_copy
);
697 if (array_size
+ item_size
+ sizeof(disk_key
)
698 > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE
)
701 ptr
= super_copy
->sys_chunk_array
+ array_size
;
702 btrfs_cpu_key_to_disk(&disk_key
, key
);
703 memcpy(ptr
, &disk_key
, sizeof(disk_key
));
704 ptr
+= sizeof(disk_key
);
705 memcpy(ptr
, chunk
, item_size
);
706 item_size
+= sizeof(disk_key
);
707 btrfs_set_super_sys_array_size(super_copy
, array_size
+ item_size
);
711 static u64
chunk_bytes_by_type(u64 type
, u64 calc_size
, int num_stripes
,
714 if (type
& (BTRFS_BLOCK_GROUP_RAID1
| BTRFS_BLOCK_GROUP_DUP
))
716 else if (type
& BTRFS_BLOCK_GROUP_RAID10
)
717 return calc_size
* (num_stripes
/ sub_stripes
);
718 else if (type
& BTRFS_BLOCK_GROUP_RAID5
)
719 return calc_size
* (num_stripes
- 1);
720 else if (type
& BTRFS_BLOCK_GROUP_RAID6
)
721 return calc_size
* (num_stripes
- 2);
723 return calc_size
* num_stripes
;
727 static u32
find_raid56_stripe_len(u32 data_devices
, u32 dev_stripe_target
)
729 /* TODO, add a way to store the preferred stripe size */
730 return BTRFS_STRIPE_LEN
;
734 * btrfs_device_avail_bytes - count bytes available for alloc_chunk
736 * It is not equal to "device->total_bytes - device->bytes_used".
737 * We do not allocate any chunk in 1M at beginning of device, and not
738 * allowed to allocate any chunk before alloc_start if it is specified.
739 * So search holes from max(1M, alloc_start) to device->total_bytes.
741 static int btrfs_device_avail_bytes(struct btrfs_trans_handle
*trans
,
742 struct btrfs_device
*device
,
745 struct btrfs_path
*path
;
746 struct btrfs_root
*root
= device
->dev_root
;
747 struct btrfs_key key
;
748 struct btrfs_dev_extent
*dev_extent
= NULL
;
749 struct extent_buffer
*l
;
750 u64 search_start
= root
->fs_info
->alloc_start
;
751 u64 search_end
= device
->total_bytes
;
757 search_start
= max(BTRFS_BLOCK_RESERVED_1M_FOR_SUPER
, search_start
);
759 path
= btrfs_alloc_path();
763 key
.objectid
= device
->devid
;
764 key
.offset
= root
->fs_info
->alloc_start
;
765 key
.type
= BTRFS_DEV_EXTENT_KEY
;
768 ret
= btrfs_search_slot(trans
, root
, &key
, path
, 0, 0);
771 ret
= btrfs_previous_item(root
, path
, 0, key
.type
);
777 slot
= path
->slots
[0];
778 if (slot
>= btrfs_header_nritems(l
)) {
779 ret
= btrfs_next_leaf(root
, path
);
786 btrfs_item_key_to_cpu(l
, &key
, slot
);
788 if (key
.objectid
< device
->devid
)
790 if (key
.objectid
> device
->devid
)
792 if (key
.type
!= BTRFS_DEV_EXTENT_KEY
)
794 if (key
.offset
> search_end
)
796 if (key
.offset
> search_start
)
797 free_bytes
+= key
.offset
- search_start
;
799 dev_extent
= btrfs_item_ptr(l
, slot
, struct btrfs_dev_extent
);
800 extent_end
= key
.offset
+ btrfs_dev_extent_length(l
,
802 if (extent_end
> search_start
)
803 search_start
= extent_end
;
804 if (search_start
> search_end
)
811 if (search_start
< search_end
)
812 free_bytes
+= search_end
- search_start
;
814 *avail_bytes
= free_bytes
;
817 btrfs_free_path(path
);
821 #define BTRFS_MAX_DEVS(r) ((BTRFS_LEAF_DATA_SIZE(r) \
822 - sizeof(struct btrfs_item) \
823 - sizeof(struct btrfs_chunk)) \
824 / sizeof(struct btrfs_stripe) + 1)
826 #define BTRFS_MAX_DEVS_SYS_CHUNK ((BTRFS_SYSTEM_CHUNK_ARRAY_SIZE \
827 - 2 * sizeof(struct btrfs_disk_key) \
828 - 2 * sizeof(struct btrfs_chunk)) \
829 / sizeof(struct btrfs_stripe) + 1)
831 int btrfs_alloc_chunk(struct btrfs_trans_handle
*trans
,
832 struct btrfs_root
*extent_root
, u64
*start
,
833 u64
*num_bytes
, u64 type
)
836 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
837 struct btrfs_root
*chunk_root
= info
->chunk_root
;
838 struct btrfs_stripe
*stripes
;
839 struct btrfs_device
*device
= NULL
;
840 struct btrfs_chunk
*chunk
;
841 struct list_head private_devs
;
842 struct list_head
*dev_list
= &info
->fs_devices
->devices
;
843 struct list_head
*cur
;
844 struct map_lookup
*map
;
845 int min_stripe_size
= SZ_1M
;
846 u64 calc_size
= SZ_8M
;
848 u64 max_chunk_size
= 4 * calc_size
;
859 int stripe_len
= BTRFS_STRIPE_LEN
;
860 struct btrfs_key key
;
863 if (list_empty(dev_list
)) {
867 if (type
& (BTRFS_BLOCK_GROUP_RAID0
| BTRFS_BLOCK_GROUP_RAID1
|
868 BTRFS_BLOCK_GROUP_RAID5
| BTRFS_BLOCK_GROUP_RAID6
|
869 BTRFS_BLOCK_GROUP_RAID10
|
870 BTRFS_BLOCK_GROUP_DUP
)) {
871 if (type
& BTRFS_BLOCK_GROUP_SYSTEM
) {
873 max_chunk_size
= calc_size
* 2;
874 min_stripe_size
= SZ_1M
;
875 max_stripes
= BTRFS_MAX_DEVS_SYS_CHUNK
;
876 } else if (type
& BTRFS_BLOCK_GROUP_DATA
) {
878 max_chunk_size
= 10 * calc_size
;
879 min_stripe_size
= SZ_64M
;
880 max_stripes
= BTRFS_MAX_DEVS(chunk_root
);
881 } else if (type
& BTRFS_BLOCK_GROUP_METADATA
) {
883 max_chunk_size
= 4 * calc_size
;
884 min_stripe_size
= SZ_32M
;
885 max_stripes
= BTRFS_MAX_DEVS(chunk_root
);
888 if (type
& BTRFS_BLOCK_GROUP_RAID1
) {
889 num_stripes
= min_t(u64
, 2,
890 btrfs_super_num_devices(info
->super_copy
));
895 if (type
& BTRFS_BLOCK_GROUP_DUP
) {
899 if (type
& (BTRFS_BLOCK_GROUP_RAID0
)) {
900 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
901 if (num_stripes
> max_stripes
)
902 num_stripes
= max_stripes
;
905 if (type
& (BTRFS_BLOCK_GROUP_RAID10
)) {
906 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
907 if (num_stripes
> max_stripes
)
908 num_stripes
= max_stripes
;
911 num_stripes
&= ~(u32
)1;
915 if (type
& (BTRFS_BLOCK_GROUP_RAID5
)) {
916 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
917 if (num_stripes
> max_stripes
)
918 num_stripes
= max_stripes
;
922 stripe_len
= find_raid56_stripe_len(num_stripes
- 1,
923 btrfs_super_stripesize(info
->super_copy
));
925 if (type
& (BTRFS_BLOCK_GROUP_RAID6
)) {
926 num_stripes
= btrfs_super_num_devices(info
->super_copy
);
927 if (num_stripes
> max_stripes
)
928 num_stripes
= max_stripes
;
932 stripe_len
= find_raid56_stripe_len(num_stripes
- 2,
933 btrfs_super_stripesize(info
->super_copy
));
936 /* we don't want a chunk larger than 10% of the FS */
937 percent_max
= div_factor(btrfs_super_total_bytes(info
->super_copy
), 1);
938 max_chunk_size
= min(percent_max
, max_chunk_size
);
941 if (chunk_bytes_by_type(type
, calc_size
, num_stripes
, sub_stripes
) >
943 calc_size
= max_chunk_size
;
944 calc_size
/= num_stripes
;
945 calc_size
/= stripe_len
;
946 calc_size
*= stripe_len
;
948 /* we don't want tiny stripes */
949 calc_size
= max_t(u64
, calc_size
, min_stripe_size
);
951 calc_size
/= stripe_len
;
952 calc_size
*= stripe_len
;
953 INIT_LIST_HEAD(&private_devs
);
954 cur
= dev_list
->next
;
957 if (type
& BTRFS_BLOCK_GROUP_DUP
)
958 min_free
= calc_size
* 2;
960 min_free
= calc_size
;
962 /* build a private list of devices we will allocate from */
963 while(index
< num_stripes
) {
964 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
965 ret
= btrfs_device_avail_bytes(trans
, device
, &avail
);
969 if (avail
>= min_free
) {
970 list_move_tail(&device
->dev_list
, &private_devs
);
972 if (type
& BTRFS_BLOCK_GROUP_DUP
)
974 } else if (avail
> max_avail
)
979 if (index
< num_stripes
) {
980 list_splice(&private_devs
, dev_list
);
981 if (index
>= min_stripes
) {
983 if (type
& (BTRFS_BLOCK_GROUP_RAID10
)) {
984 num_stripes
/= sub_stripes
;
985 num_stripes
*= sub_stripes
;
990 if (!looped
&& max_avail
> 0) {
992 calc_size
= max_avail
;
997 ret
= find_next_chunk(chunk_root
, BTRFS_FIRST_CHUNK_TREE_OBJECTID
,
1001 key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
1002 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
1003 key
.offset
= offset
;
1005 chunk
= kmalloc(btrfs_chunk_item_size(num_stripes
), GFP_NOFS
);
1009 map
= kmalloc(btrfs_map_lookup_size(num_stripes
), GFP_NOFS
);
1015 stripes
= &chunk
->stripe
;
1016 *num_bytes
= chunk_bytes_by_type(type
, calc_size
,
1017 num_stripes
, sub_stripes
);
1019 while(index
< num_stripes
) {
1020 struct btrfs_stripe
*stripe
;
1021 BUG_ON(list_empty(&private_devs
));
1022 cur
= private_devs
.next
;
1023 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
1025 /* loop over this device again if we're doing a dup group */
1026 if (!(type
& BTRFS_BLOCK_GROUP_DUP
) ||
1027 (index
== num_stripes
- 1))
1028 list_move_tail(&device
->dev_list
, dev_list
);
1030 ret
= btrfs_alloc_dev_extent(trans
, device
,
1031 info
->chunk_root
->root_key
.objectid
,
1032 BTRFS_FIRST_CHUNK_TREE_OBJECTID
, key
.offset
,
1033 calc_size
, &dev_offset
, 0);
1036 device
->bytes_used
+= calc_size
;
1037 ret
= btrfs_update_device(trans
, device
);
1040 map
->stripes
[index
].dev
= device
;
1041 map
->stripes
[index
].physical
= dev_offset
;
1042 stripe
= stripes
+ index
;
1043 btrfs_set_stack_stripe_devid(stripe
, device
->devid
);
1044 btrfs_set_stack_stripe_offset(stripe
, dev_offset
);
1045 memcpy(stripe
->dev_uuid
, device
->uuid
, BTRFS_UUID_SIZE
);
1048 BUG_ON(!list_empty(&private_devs
));
1050 /* key was set above */
1051 btrfs_set_stack_chunk_length(chunk
, *num_bytes
);
1052 btrfs_set_stack_chunk_owner(chunk
, extent_root
->root_key
.objectid
);
1053 btrfs_set_stack_chunk_stripe_len(chunk
, stripe_len
);
1054 btrfs_set_stack_chunk_type(chunk
, type
);
1055 btrfs_set_stack_chunk_num_stripes(chunk
, num_stripes
);
1056 btrfs_set_stack_chunk_io_align(chunk
, stripe_len
);
1057 btrfs_set_stack_chunk_io_width(chunk
, stripe_len
);
1058 btrfs_set_stack_chunk_sector_size(chunk
, extent_root
->sectorsize
);
1059 btrfs_set_stack_chunk_sub_stripes(chunk
, sub_stripes
);
1060 map
->sector_size
= extent_root
->sectorsize
;
1061 map
->stripe_len
= stripe_len
;
1062 map
->io_align
= stripe_len
;
1063 map
->io_width
= stripe_len
;
1065 map
->num_stripes
= num_stripes
;
1066 map
->sub_stripes
= sub_stripes
;
1068 ret
= btrfs_insert_item(trans
, chunk_root
, &key
, chunk
,
1069 btrfs_chunk_item_size(num_stripes
));
1071 *start
= key
.offset
;;
1073 map
->ce
.start
= key
.offset
;
1074 map
->ce
.size
= *num_bytes
;
1076 ret
= insert_cache_extent(&info
->mapping_tree
.cache_tree
, &map
->ce
);
1079 if (type
& BTRFS_BLOCK_GROUP_SYSTEM
) {
1080 ret
= btrfs_add_system_chunk(chunk_root
, &key
,
1081 chunk
, btrfs_chunk_item_size(num_stripes
));
1090 * Alloc a DATA chunk with SINGLE profile.
1092 * If 'convert' is set, it will alloc a chunk with 1:1 mapping
1093 * (btrfs logical bytenr == on-disk bytenr)
1094 * For that case, caller must make sure the chunk and dev_extent are not
1097 int btrfs_alloc_data_chunk(struct btrfs_trans_handle
*trans
,
1098 struct btrfs_root
*extent_root
, u64
*start
,
1099 u64 num_bytes
, u64 type
, int convert
)
1102 struct btrfs_fs_info
*info
= extent_root
->fs_info
;
1103 struct btrfs_root
*chunk_root
= info
->chunk_root
;
1104 struct btrfs_stripe
*stripes
;
1105 struct btrfs_device
*device
= NULL
;
1106 struct btrfs_chunk
*chunk
;
1107 struct list_head
*dev_list
= &info
->fs_devices
->devices
;
1108 struct list_head
*cur
;
1109 struct map_lookup
*map
;
1110 u64 calc_size
= SZ_8M
;
1111 int num_stripes
= 1;
1112 int sub_stripes
= 0;
1115 int stripe_len
= BTRFS_STRIPE_LEN
;
1116 struct btrfs_key key
;
1118 key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
1119 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
1121 if (*start
!= round_down(*start
, extent_root
->sectorsize
)) {
1122 error("DATA chunk start not sectorsize aligned: %llu",
1123 (unsigned long long)*start
);
1126 key
.offset
= *start
;
1127 dev_offset
= *start
;
1131 ret
= find_next_chunk(chunk_root
,
1132 BTRFS_FIRST_CHUNK_TREE_OBJECTID
,
1139 chunk
= kmalloc(btrfs_chunk_item_size(num_stripes
), GFP_NOFS
);
1143 map
= kmalloc(btrfs_map_lookup_size(num_stripes
), GFP_NOFS
);
1149 stripes
= &chunk
->stripe
;
1150 calc_size
= num_bytes
;
1153 cur
= dev_list
->next
;
1154 device
= list_entry(cur
, struct btrfs_device
, dev_list
);
1156 while (index
< num_stripes
) {
1157 struct btrfs_stripe
*stripe
;
1159 ret
= btrfs_alloc_dev_extent(trans
, device
,
1160 info
->chunk_root
->root_key
.objectid
,
1161 BTRFS_FIRST_CHUNK_TREE_OBJECTID
, key
.offset
,
1162 calc_size
, &dev_offset
, convert
);
1165 device
->bytes_used
+= calc_size
;
1166 ret
= btrfs_update_device(trans
, device
);
1169 map
->stripes
[index
].dev
= device
;
1170 map
->stripes
[index
].physical
= dev_offset
;
1171 stripe
= stripes
+ index
;
1172 btrfs_set_stack_stripe_devid(stripe
, device
->devid
);
1173 btrfs_set_stack_stripe_offset(stripe
, dev_offset
);
1174 memcpy(stripe
->dev_uuid
, device
->uuid
, BTRFS_UUID_SIZE
);
1178 /* key was set above */
1179 btrfs_set_stack_chunk_length(chunk
, num_bytes
);
1180 btrfs_set_stack_chunk_owner(chunk
, extent_root
->root_key
.objectid
);
1181 btrfs_set_stack_chunk_stripe_len(chunk
, stripe_len
);
1182 btrfs_set_stack_chunk_type(chunk
, type
);
1183 btrfs_set_stack_chunk_num_stripes(chunk
, num_stripes
);
1184 btrfs_set_stack_chunk_io_align(chunk
, stripe_len
);
1185 btrfs_set_stack_chunk_io_width(chunk
, stripe_len
);
1186 btrfs_set_stack_chunk_sector_size(chunk
, extent_root
->sectorsize
);
1187 btrfs_set_stack_chunk_sub_stripes(chunk
, sub_stripes
);
1188 map
->sector_size
= extent_root
->sectorsize
;
1189 map
->stripe_len
= stripe_len
;
1190 map
->io_align
= stripe_len
;
1191 map
->io_width
= stripe_len
;
1193 map
->num_stripes
= num_stripes
;
1194 map
->sub_stripes
= sub_stripes
;
1196 ret
= btrfs_insert_item(trans
, chunk_root
, &key
, chunk
,
1197 btrfs_chunk_item_size(num_stripes
));
1200 *start
= key
.offset
;
1202 map
->ce
.start
= key
.offset
;
1203 map
->ce
.size
= num_bytes
;
1205 ret
= insert_cache_extent(&info
->mapping_tree
.cache_tree
, &map
->ce
);
1212 int btrfs_num_copies(struct btrfs_mapping_tree
*map_tree
, u64 logical
, u64 len
)
1214 struct cache_extent
*ce
;
1215 struct map_lookup
*map
;
1218 ce
= search_cache_extent(&map_tree
->cache_tree
, logical
);
1220 fprintf(stderr
, "No mapping for %llu-%llu\n",
1221 (unsigned long long)logical
,
1222 (unsigned long long)logical
+len
);
1225 if (ce
->start
> logical
|| ce
->start
+ ce
->size
< logical
) {
1226 fprintf(stderr
, "Invalid mapping for %llu-%llu, got "
1227 "%llu-%llu\n", (unsigned long long)logical
,
1228 (unsigned long long)logical
+len
,
1229 (unsigned long long)ce
->start
,
1230 (unsigned long long)ce
->start
+ ce
->size
);
1233 map
= container_of(ce
, struct map_lookup
, ce
);
1235 if (map
->type
& (BTRFS_BLOCK_GROUP_DUP
| BTRFS_BLOCK_GROUP_RAID1
))
1236 ret
= map
->num_stripes
;
1237 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
)
1238 ret
= map
->sub_stripes
;
1239 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID5
)
1241 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID6
)
1248 int btrfs_next_bg(struct btrfs_mapping_tree
*map_tree
, u64
*logical
,
1249 u64
*size
, u64 type
)
1251 struct cache_extent
*ce
;
1252 struct map_lookup
*map
;
1255 ce
= search_cache_extent(&map_tree
->cache_tree
, cur
);
1259 * only jump to next bg if our cur is not 0
1260 * As the initial logical for btrfs_next_bg() is 0, and
1261 * if we jump to next bg, we skipped a valid bg.
1264 ce
= next_cache_extent(ce
);
1270 map
= container_of(ce
, struct map_lookup
, ce
);
1271 if (map
->type
& type
) {
1272 *logical
= ce
->start
;
1281 int btrfs_rmap_block(struct btrfs_mapping_tree
*map_tree
,
1282 u64 chunk_start
, u64 physical
, u64 devid
,
1283 u64
**logical
, int *naddrs
, int *stripe_len
)
1285 struct cache_extent
*ce
;
1286 struct map_lookup
*map
;
1294 ce
= search_cache_extent(&map_tree
->cache_tree
, chunk_start
);
1296 map
= container_of(ce
, struct map_lookup
, ce
);
1299 rmap_len
= map
->stripe_len
;
1300 if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
)
1301 length
= ce
->size
/ (map
->num_stripes
/ map
->sub_stripes
);
1302 else if (map
->type
& BTRFS_BLOCK_GROUP_RAID0
)
1303 length
= ce
->size
/ map
->num_stripes
;
1304 else if (map
->type
& (BTRFS_BLOCK_GROUP_RAID5
|
1305 BTRFS_BLOCK_GROUP_RAID6
)) {
1306 length
= ce
->size
/ nr_data_stripes(map
);
1307 rmap_len
= map
->stripe_len
* nr_data_stripes(map
);
1310 buf
= kzalloc(sizeof(u64
) * map
->num_stripes
, GFP_NOFS
);
1312 for (i
= 0; i
< map
->num_stripes
; i
++) {
1313 if (devid
&& map
->stripes
[i
].dev
->devid
!= devid
)
1315 if (map
->stripes
[i
].physical
> physical
||
1316 map
->stripes
[i
].physical
+ length
<= physical
)
1319 stripe_nr
= (physical
- map
->stripes
[i
].physical
) /
1322 if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
) {
1323 stripe_nr
= (stripe_nr
* map
->num_stripes
+ i
) /
1325 } else if (map
->type
& BTRFS_BLOCK_GROUP_RAID0
) {
1326 stripe_nr
= stripe_nr
* map
->num_stripes
+ i
;
1327 } /* else if RAID[56], multiply by nr_data_stripes().
1328 * Alternatively, just use rmap_len below instead of
1329 * map->stripe_len */
1331 bytenr
= ce
->start
+ stripe_nr
* rmap_len
;
1332 for (j
= 0; j
< nr
; j
++) {
1333 if (buf
[j
] == bytenr
)
1342 *stripe_len
= rmap_len
;
1347 static inline int parity_smaller(u64 a
, u64 b
)
1352 /* Bubble-sort the stripe set to put the parity/syndrome stripes last */
1353 static void sort_parity_stripes(struct btrfs_multi_bio
*bbio
, u64
*raid_map
)
1355 struct btrfs_bio_stripe s
;
1362 for (i
= 0; i
< bbio
->num_stripes
- 1; i
++) {
1363 if (parity_smaller(raid_map
[i
], raid_map
[i
+1])) {
1364 s
= bbio
->stripes
[i
];
1366 bbio
->stripes
[i
] = bbio
->stripes
[i
+1];
1367 raid_map
[i
] = raid_map
[i
+1];
1368 bbio
->stripes
[i
+1] = s
;
1376 int btrfs_map_block(struct btrfs_mapping_tree
*map_tree
, int rw
,
1377 u64 logical
, u64
*length
,
1378 struct btrfs_multi_bio
**multi_ret
, int mirror_num
,
1381 return __btrfs_map_block(map_tree
, rw
, logical
, length
, NULL
,
1382 multi_ret
, mirror_num
, raid_map_ret
);
1385 int __btrfs_map_block(struct btrfs_mapping_tree
*map_tree
, int rw
,
1386 u64 logical
, u64
*length
, u64
*type
,
1387 struct btrfs_multi_bio
**multi_ret
, int mirror_num
,
1390 struct cache_extent
*ce
;
1391 struct map_lookup
*map
;
1395 u64
*raid_map
= NULL
;
1396 int stripes_allocated
= 8;
1397 int stripes_required
= 1;
1400 struct btrfs_multi_bio
*multi
= NULL
;
1402 if (multi_ret
&& rw
== READ
) {
1403 stripes_allocated
= 1;
1406 ce
= search_cache_extent(&map_tree
->cache_tree
, logical
);
1412 if (ce
->start
> logical
) {
1414 *length
= ce
->start
- logical
;
1419 multi
= kzalloc(btrfs_multi_bio_size(stripes_allocated
),
1424 map
= container_of(ce
, struct map_lookup
, ce
);
1425 offset
= logical
- ce
->start
;
1428 if (map
->type
& (BTRFS_BLOCK_GROUP_RAID1
|
1429 BTRFS_BLOCK_GROUP_DUP
)) {
1430 stripes_required
= map
->num_stripes
;
1431 } else if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
) {
1432 stripes_required
= map
->sub_stripes
;
1435 if (map
->type
& (BTRFS_BLOCK_GROUP_RAID5
| BTRFS_BLOCK_GROUP_RAID6
)
1436 && multi_ret
&& ((rw
& WRITE
) || mirror_num
> 1) && raid_map_ret
) {
1437 /* RAID[56] write or recovery. Return all stripes */
1438 stripes_required
= map
->num_stripes
;
1440 /* Only allocate the map if we've already got a large enough multi_ret */
1441 if (stripes_allocated
>= stripes_required
) {
1442 raid_map
= kmalloc(sizeof(u64
) * map
->num_stripes
, GFP_NOFS
);
1450 /* if our multi bio struct is too small, back off and try again */
1451 if (multi_ret
&& stripes_allocated
< stripes_required
) {
1452 stripes_allocated
= stripes_required
;
1459 * stripe_nr counts the total number of stripes we have to stride
1460 * to get to this block
1462 stripe_nr
= stripe_nr
/ map
->stripe_len
;
1464 stripe_offset
= stripe_nr
* map
->stripe_len
;
1465 BUG_ON(offset
< stripe_offset
);
1467 /* stripe_offset is the offset of this block in its stripe*/
1468 stripe_offset
= offset
- stripe_offset
;
1470 if (map
->type
& (BTRFS_BLOCK_GROUP_RAID0
| BTRFS_BLOCK_GROUP_RAID1
|
1471 BTRFS_BLOCK_GROUP_RAID5
| BTRFS_BLOCK_GROUP_RAID6
|
1472 BTRFS_BLOCK_GROUP_RAID10
|
1473 BTRFS_BLOCK_GROUP_DUP
)) {
1474 /* we limit the length of each bio to what fits in a stripe */
1475 *length
= min_t(u64
, ce
->size
- offset
,
1476 map
->stripe_len
- stripe_offset
);
1478 *length
= ce
->size
- offset
;
1484 multi
->num_stripes
= 1;
1486 if (map
->type
& BTRFS_BLOCK_GROUP_RAID1
) {
1488 multi
->num_stripes
= map
->num_stripes
;
1489 else if (mirror_num
)
1490 stripe_index
= mirror_num
- 1;
1492 stripe_index
= stripe_nr
% map
->num_stripes
;
1493 } else if (map
->type
& BTRFS_BLOCK_GROUP_RAID10
) {
1494 int factor
= map
->num_stripes
/ map
->sub_stripes
;
1496 stripe_index
= stripe_nr
% factor
;
1497 stripe_index
*= map
->sub_stripes
;
1500 multi
->num_stripes
= map
->sub_stripes
;
1501 else if (mirror_num
)
1502 stripe_index
+= mirror_num
- 1;
1504 stripe_nr
= stripe_nr
/ factor
;
1505 } else if (map
->type
& BTRFS_BLOCK_GROUP_DUP
) {
1507 multi
->num_stripes
= map
->num_stripes
;
1508 else if (mirror_num
)
1509 stripe_index
= mirror_num
- 1;
1510 } else if (map
->type
& (BTRFS_BLOCK_GROUP_RAID5
|
1511 BTRFS_BLOCK_GROUP_RAID6
)) {
1516 u64 raid56_full_stripe_start
;
1517 u64 full_stripe_len
= nr_data_stripes(map
) * map
->stripe_len
;
1520 * align the start of our data stripe in the logical
1523 raid56_full_stripe_start
= offset
/ full_stripe_len
;
1524 raid56_full_stripe_start
*= full_stripe_len
;
1526 /* get the data stripe number */
1527 stripe_nr
= raid56_full_stripe_start
/ map
->stripe_len
;
1528 stripe_nr
= stripe_nr
/ nr_data_stripes(map
);
1530 /* Work out the disk rotation on this stripe-set */
1531 rot
= stripe_nr
% map
->num_stripes
;
1533 /* Fill in the logical address of each stripe */
1534 tmp
= stripe_nr
* nr_data_stripes(map
);
1536 for (i
= 0; i
< nr_data_stripes(map
); i
++)
1537 raid_map
[(i
+rot
) % map
->num_stripes
] =
1538 ce
->start
+ (tmp
+ i
) * map
->stripe_len
;
1540 raid_map
[(i
+rot
) % map
->num_stripes
] = BTRFS_RAID5_P_STRIPE
;
1541 if (map
->type
& BTRFS_BLOCK_GROUP_RAID6
)
1542 raid_map
[(i
+rot
+1) % map
->num_stripes
] = BTRFS_RAID6_Q_STRIPE
;
1544 *length
= map
->stripe_len
;
1547 multi
->num_stripes
= map
->num_stripes
;
1549 stripe_index
= stripe_nr
% nr_data_stripes(map
);
1550 stripe_nr
= stripe_nr
/ nr_data_stripes(map
);
1553 * Mirror #0 or #1 means the original data block.
1554 * Mirror #2 is RAID5 parity block.
1555 * Mirror #3 is RAID6 Q block.
1558 stripe_index
= nr_data_stripes(map
) + mirror_num
- 2;
1560 /* We distribute the parity blocks across stripes */
1561 stripe_index
= (stripe_nr
+ stripe_index
) % map
->num_stripes
;
1565 * after this do_div call, stripe_nr is the number of stripes
1566 * on this device we have to walk to find the data, and
1567 * stripe_index is the number of our device in the stripe array
1569 stripe_index
= stripe_nr
% map
->num_stripes
;
1570 stripe_nr
= stripe_nr
/ map
->num_stripes
;
1572 BUG_ON(stripe_index
>= map
->num_stripes
);
1574 for (i
= 0; i
< multi
->num_stripes
; i
++) {
1575 multi
->stripes
[i
].physical
=
1576 map
->stripes
[stripe_index
].physical
+ stripe_offset
+
1577 stripe_nr
* map
->stripe_len
;
1578 multi
->stripes
[i
].dev
= map
->stripes
[stripe_index
].dev
;
1587 sort_parity_stripes(multi
, raid_map
);
1588 *raid_map_ret
= raid_map
;
1594 struct btrfs_device
*btrfs_find_device(struct btrfs_root
*root
, u64 devid
,
1597 struct btrfs_device
*device
;
1598 struct btrfs_fs_devices
*cur_devices
;
1600 cur_devices
= root
->fs_info
->fs_devices
;
1601 while (cur_devices
) {
1603 (!memcmp(cur_devices
->fsid
, fsid
, BTRFS_UUID_SIZE
) ||
1604 root
->fs_info
->ignore_fsid_mismatch
)) {
1605 device
= __find_device(&cur_devices
->devices
,
1610 cur_devices
= cur_devices
->seed
;
1615 struct btrfs_device
*
1616 btrfs_find_device_by_devid(struct btrfs_fs_devices
*fs_devices
,
1617 u64 devid
, int instance
)
1619 struct list_head
*head
= &fs_devices
->devices
;
1620 struct btrfs_device
*dev
;
1623 list_for_each_entry(dev
, head
, dev_list
) {
1624 if (dev
->devid
== devid
&& num_found
++ == instance
)
1630 int btrfs_chunk_readonly(struct btrfs_root
*root
, u64 chunk_offset
)
1632 struct cache_extent
*ce
;
1633 struct map_lookup
*map
;
1634 struct btrfs_mapping_tree
*map_tree
= &root
->fs_info
->mapping_tree
;
1639 * During chunk recovering, we may fail to find block group's
1640 * corresponding chunk, we will rebuild it later
1642 ce
= search_cache_extent(&map_tree
->cache_tree
, chunk_offset
);
1643 if (!root
->fs_info
->is_chunk_recover
)
1648 map
= container_of(ce
, struct map_lookup
, ce
);
1649 for (i
= 0; i
< map
->num_stripes
; i
++) {
1650 if (!map
->stripes
[i
].dev
->writeable
) {
1659 static struct btrfs_device
*fill_missing_device(u64 devid
)
1661 struct btrfs_device
*device
;
1663 device
= kzalloc(sizeof(*device
), GFP_NOFS
);
1664 device
->devid
= devid
;
1670 * slot == -1: SYSTEM chunk
1671 * return -EIO on error, otherwise return 0
1673 int btrfs_check_chunk_valid(struct btrfs_root
*root
,
1674 struct extent_buffer
*leaf
,
1675 struct btrfs_chunk
*chunk
,
1676 int slot
, u64 logical
)
1684 length
= btrfs_chunk_length(leaf
, chunk
);
1685 stripe_len
= btrfs_chunk_stripe_len(leaf
, chunk
);
1686 num_stripes
= btrfs_chunk_num_stripes(leaf
, chunk
);
1687 sub_stripes
= btrfs_chunk_sub_stripes(leaf
, chunk
);
1688 type
= btrfs_chunk_type(leaf
, chunk
);
1691 * These valid checks may be insufficient to cover every corner cases.
1693 if (!IS_ALIGNED(logical
, root
->sectorsize
)) {
1694 error("invalid chunk logical %llu", logical
);
1697 if (btrfs_chunk_sector_size(leaf
, chunk
) != root
->sectorsize
) {
1698 error("invalid chunk sectorsize %llu",
1699 (unsigned long long)btrfs_chunk_sector_size(leaf
, chunk
));
1702 if (!length
|| !IS_ALIGNED(length
, root
->sectorsize
)) {
1703 error("invalid chunk length %llu", length
);
1706 if (stripe_len
!= BTRFS_STRIPE_LEN
) {
1707 error("invalid chunk stripe length: %llu", stripe_len
);
1710 /* Check on chunk item type */
1711 if (slot
== -1 && (type
& BTRFS_BLOCK_GROUP_SYSTEM
) == 0) {
1712 error("invalid chunk type %llu", type
);
1715 if (type
& ~(BTRFS_BLOCK_GROUP_TYPE_MASK
|
1716 BTRFS_BLOCK_GROUP_PROFILE_MASK
)) {
1717 error("unrecognized chunk type: %llu",
1718 ~(BTRFS_BLOCK_GROUP_TYPE_MASK
|
1719 BTRFS_BLOCK_GROUP_PROFILE_MASK
) & type
);
1723 * Btrfs_chunk contains at least one stripe, and for sys_chunk
1724 * it can't exceed the system chunk array size
1725 * For normal chunk, it should match its chunk item size.
1727 if (num_stripes
< 1 ||
1728 (slot
== -1 && sizeof(struct btrfs_stripe
) * num_stripes
>
1729 BTRFS_SYSTEM_CHUNK_ARRAY_SIZE
) ||
1730 (slot
>= 0 && sizeof(struct btrfs_stripe
) * (num_stripes
- 1) >
1731 btrfs_item_size_nr(leaf
, slot
))) {
1732 error("invalid num_stripes: %u", num_stripes
);
1736 * Device number check against profile
1738 if ((type
& BTRFS_BLOCK_GROUP_RAID10
&& sub_stripes
== 0) ||
1739 (type
& BTRFS_BLOCK_GROUP_RAID1
&& num_stripes
< 1) ||
1740 (type
& BTRFS_BLOCK_GROUP_RAID5
&& num_stripes
< 2) ||
1741 (type
& BTRFS_BLOCK_GROUP_RAID6
&& num_stripes
< 3) ||
1742 (type
& BTRFS_BLOCK_GROUP_DUP
&& num_stripes
> 2) ||
1743 ((type
& BTRFS_BLOCK_GROUP_PROFILE_MASK
) == 0 &&
1744 num_stripes
!= 1)) {
1745 error("Invalid num_stripes:sub_stripes %u:%u for profile %llu",
1746 num_stripes
, sub_stripes
,
1747 type
& BTRFS_BLOCK_GROUP_PROFILE_MASK
);
1755 * Slot is used to verify the chunk item is valid
1757 * For sys chunk in superblock, pass -1 to indicate sys chunk.
1759 static int read_one_chunk(struct btrfs_root
*root
, struct btrfs_key
*key
,
1760 struct extent_buffer
*leaf
,
1761 struct btrfs_chunk
*chunk
, int slot
)
1763 struct btrfs_mapping_tree
*map_tree
= &root
->fs_info
->mapping_tree
;
1764 struct map_lookup
*map
;
1765 struct cache_extent
*ce
;
1769 u8 uuid
[BTRFS_UUID_SIZE
];
1774 logical
= key
->offset
;
1775 length
= btrfs_chunk_length(leaf
, chunk
);
1776 num_stripes
= btrfs_chunk_num_stripes(leaf
, chunk
);
1777 /* Validation check */
1778 ret
= btrfs_check_chunk_valid(root
, leaf
, chunk
, slot
, logical
);
1780 error("%s checksums match, but it has an invalid chunk, %s",
1781 (slot
== -1) ? "Superblock" : "Metadata",
1782 (slot
== -1) ? "try btrfsck --repair -s <superblock> ie, 0,1,2" : "");
1786 ce
= search_cache_extent(&map_tree
->cache_tree
, logical
);
1788 /* already mapped? */
1789 if (ce
&& ce
->start
<= logical
&& ce
->start
+ ce
->size
> logical
) {
1793 map
= kmalloc(btrfs_map_lookup_size(num_stripes
), GFP_NOFS
);
1797 map
->ce
.start
= logical
;
1798 map
->ce
.size
= length
;
1799 map
->num_stripes
= num_stripes
;
1800 map
->io_width
= btrfs_chunk_io_width(leaf
, chunk
);
1801 map
->io_align
= btrfs_chunk_io_align(leaf
, chunk
);
1802 map
->sector_size
= btrfs_chunk_sector_size(leaf
, chunk
);
1803 map
->stripe_len
= btrfs_chunk_stripe_len(leaf
, chunk
);
1804 map
->type
= btrfs_chunk_type(leaf
, chunk
);
1805 map
->sub_stripes
= btrfs_chunk_sub_stripes(leaf
, chunk
);
1807 for (i
= 0; i
< num_stripes
; i
++) {
1808 map
->stripes
[i
].physical
=
1809 btrfs_stripe_offset_nr(leaf
, chunk
, i
);
1810 devid
= btrfs_stripe_devid_nr(leaf
, chunk
, i
);
1811 read_extent_buffer(leaf
, uuid
, (unsigned long)
1812 btrfs_stripe_dev_uuid_nr(chunk
, i
),
1814 map
->stripes
[i
].dev
= btrfs_find_device(root
, devid
, uuid
,
1816 if (!map
->stripes
[i
].dev
) {
1817 map
->stripes
[i
].dev
= fill_missing_device(devid
);
1818 printf("warning, device %llu is missing\n",
1819 (unsigned long long)devid
);
1820 list_add(&map
->stripes
[i
].dev
->dev_list
,
1821 &root
->fs_info
->fs_devices
->devices
);
1825 ret
= insert_cache_extent(&map_tree
->cache_tree
, &map
->ce
);
1831 static int fill_device_from_item(struct extent_buffer
*leaf
,
1832 struct btrfs_dev_item
*dev_item
,
1833 struct btrfs_device
*device
)
1837 device
->devid
= btrfs_device_id(leaf
, dev_item
);
1838 device
->total_bytes
= btrfs_device_total_bytes(leaf
, dev_item
);
1839 device
->bytes_used
= btrfs_device_bytes_used(leaf
, dev_item
);
1840 device
->type
= btrfs_device_type(leaf
, dev_item
);
1841 device
->io_align
= btrfs_device_io_align(leaf
, dev_item
);
1842 device
->io_width
= btrfs_device_io_width(leaf
, dev_item
);
1843 device
->sector_size
= btrfs_device_sector_size(leaf
, dev_item
);
1845 ptr
= (unsigned long)btrfs_device_uuid(dev_item
);
1846 read_extent_buffer(leaf
, device
->uuid
, ptr
, BTRFS_UUID_SIZE
);
1851 static int open_seed_devices(struct btrfs_root
*root
, u8
*fsid
)
1853 struct btrfs_fs_devices
*fs_devices
;
1856 fs_devices
= root
->fs_info
->fs_devices
->seed
;
1857 while (fs_devices
) {
1858 if (!memcmp(fs_devices
->fsid
, fsid
, BTRFS_UUID_SIZE
)) {
1862 fs_devices
= fs_devices
->seed
;
1865 fs_devices
= find_fsid(fsid
);
1867 /* missing all seed devices */
1868 fs_devices
= kzalloc(sizeof(*fs_devices
), GFP_NOFS
);
1873 INIT_LIST_HEAD(&fs_devices
->devices
);
1874 list_add(&fs_devices
->list
, &fs_uuids
);
1875 memcpy(fs_devices
->fsid
, fsid
, BTRFS_FSID_SIZE
);
1878 ret
= btrfs_open_devices(fs_devices
, O_RDONLY
);
1882 fs_devices
->seed
= root
->fs_info
->fs_devices
->seed
;
1883 root
->fs_info
->fs_devices
->seed
= fs_devices
;
1888 static int read_one_dev(struct btrfs_root
*root
,
1889 struct extent_buffer
*leaf
,
1890 struct btrfs_dev_item
*dev_item
)
1892 struct btrfs_device
*device
;
1895 u8 fs_uuid
[BTRFS_UUID_SIZE
];
1896 u8 dev_uuid
[BTRFS_UUID_SIZE
];
1898 devid
= btrfs_device_id(leaf
, dev_item
);
1899 read_extent_buffer(leaf
, dev_uuid
,
1900 (unsigned long)btrfs_device_uuid(dev_item
),
1902 read_extent_buffer(leaf
, fs_uuid
,
1903 (unsigned long)btrfs_device_fsid(dev_item
),
1906 if (memcmp(fs_uuid
, root
->fs_info
->fsid
, BTRFS_UUID_SIZE
)) {
1907 ret
= open_seed_devices(root
, fs_uuid
);
1912 device
= btrfs_find_device(root
, devid
, dev_uuid
, fs_uuid
);
1914 device
= kzalloc(sizeof(*device
), GFP_NOFS
);
1918 list_add(&device
->dev_list
,
1919 &root
->fs_info
->fs_devices
->devices
);
1922 fill_device_from_item(leaf
, dev_item
, device
);
1923 device
->dev_root
= root
->fs_info
->dev_root
;
1927 int btrfs_read_sys_array(struct btrfs_root
*root
)
1929 struct btrfs_super_block
*super_copy
= root
->fs_info
->super_copy
;
1930 struct extent_buffer
*sb
;
1931 struct btrfs_disk_key
*disk_key
;
1932 struct btrfs_chunk
*chunk
;
1934 unsigned long sb_array_offset
;
1940 struct btrfs_key key
;
1942 sb
= btrfs_find_create_tree_block(root
->fs_info
,
1943 BTRFS_SUPER_INFO_OFFSET
,
1944 BTRFS_SUPER_INFO_SIZE
);
1947 btrfs_set_buffer_uptodate(sb
);
1948 write_extent_buffer(sb
, super_copy
, 0, sizeof(*super_copy
));
1949 array_size
= btrfs_super_sys_array_size(super_copy
);
1951 array_ptr
= super_copy
->sys_chunk_array
;
1952 sb_array_offset
= offsetof(struct btrfs_super_block
, sys_chunk_array
);
1955 while (cur_offset
< array_size
) {
1956 disk_key
= (struct btrfs_disk_key
*)array_ptr
;
1957 len
= sizeof(*disk_key
);
1958 if (cur_offset
+ len
> array_size
)
1959 goto out_short_read
;
1961 btrfs_disk_key_to_cpu(&key
, disk_key
);
1964 sb_array_offset
+= len
;
1967 if (key
.type
== BTRFS_CHUNK_ITEM_KEY
) {
1968 chunk
= (struct btrfs_chunk
*)sb_array_offset
;
1970 * At least one btrfs_chunk with one stripe must be
1971 * present, exact stripe count check comes afterwards
1973 len
= btrfs_chunk_item_size(1);
1974 if (cur_offset
+ len
> array_size
)
1975 goto out_short_read
;
1977 num_stripes
= btrfs_chunk_num_stripes(sb
, chunk
);
1980 "ERROR: invalid number of stripes %u in sys_array at offset %u\n",
1981 num_stripes
, cur_offset
);
1986 len
= btrfs_chunk_item_size(num_stripes
);
1987 if (cur_offset
+ len
> array_size
)
1988 goto out_short_read
;
1990 ret
= read_one_chunk(root
, &key
, sb
, chunk
, -1);
1995 "ERROR: unexpected item type %u in sys_array at offset %u\n",
1996 (u32
)key
.type
, cur_offset
);
2001 sb_array_offset
+= len
;
2004 free_extent_buffer(sb
);
2008 printk("ERROR: sys_array too short to read %u bytes at offset %u\n",
2010 free_extent_buffer(sb
);
2014 int btrfs_read_chunk_tree(struct btrfs_root
*root
)
2016 struct btrfs_path
*path
;
2017 struct extent_buffer
*leaf
;
2018 struct btrfs_key key
;
2019 struct btrfs_key found_key
;
2023 root
= root
->fs_info
->chunk_root
;
2025 path
= btrfs_alloc_path();
2030 * Read all device items, and then all the chunk items. All
2031 * device items are found before any chunk item (their object id
2032 * is smaller than the lowest possible object id for a chunk
2033 * item - BTRFS_FIRST_CHUNK_TREE_OBJECTID).
2035 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
2038 ret
= btrfs_search_slot(NULL
, root
, &key
, path
, 0, 0);
2042 leaf
= path
->nodes
[0];
2043 slot
= path
->slots
[0];
2044 if (slot
>= btrfs_header_nritems(leaf
)) {
2045 ret
= btrfs_next_leaf(root
, path
);
2052 btrfs_item_key_to_cpu(leaf
, &found_key
, slot
);
2053 if (found_key
.type
== BTRFS_DEV_ITEM_KEY
) {
2054 struct btrfs_dev_item
*dev_item
;
2055 dev_item
= btrfs_item_ptr(leaf
, slot
,
2056 struct btrfs_dev_item
);
2057 ret
= read_one_dev(root
, leaf
, dev_item
);
2059 } else if (found_key
.type
== BTRFS_CHUNK_ITEM_KEY
) {
2060 struct btrfs_chunk
*chunk
;
2061 chunk
= btrfs_item_ptr(leaf
, slot
, struct btrfs_chunk
);
2062 ret
= read_one_chunk(root
, &found_key
, leaf
, chunk
,
2071 btrfs_free_path(path
);
2075 struct list_head
*btrfs_scanned_uuids(void)
2080 static int rmw_eb(struct btrfs_fs_info
*info
,
2081 struct extent_buffer
*eb
, struct extent_buffer
*orig_eb
)
2084 unsigned long orig_off
= 0;
2085 unsigned long dest_off
= 0;
2086 unsigned long copy_len
= eb
->len
;
2088 ret
= read_whole_eb(info
, eb
, 0);
2092 if (eb
->start
+ eb
->len
<= orig_eb
->start
||
2093 eb
->start
>= orig_eb
->start
+ orig_eb
->len
)
2096 * | ----- orig_eb ------- |
2097 * | ----- stripe ------- |
2098 * | ----- orig_eb ------- |
2099 * | ----- orig_eb ------- |
2101 if (eb
->start
> orig_eb
->start
)
2102 orig_off
= eb
->start
- orig_eb
->start
;
2103 if (orig_eb
->start
> eb
->start
)
2104 dest_off
= orig_eb
->start
- eb
->start
;
2106 if (copy_len
> orig_eb
->len
- orig_off
)
2107 copy_len
= orig_eb
->len
- orig_off
;
2108 if (copy_len
> eb
->len
- dest_off
)
2109 copy_len
= eb
->len
- dest_off
;
2111 memcpy(eb
->data
+ dest_off
, orig_eb
->data
+ orig_off
, copy_len
);
2115 static int split_eb_for_raid56(struct btrfs_fs_info
*info
,
2116 struct extent_buffer
*orig_eb
,
2117 struct extent_buffer
**ebs
,
2118 u64 stripe_len
, u64
*raid_map
,
2121 struct extent_buffer
**tmp_ebs
;
2122 u64 start
= orig_eb
->start
;
2127 tmp_ebs
= calloc(num_stripes
, sizeof(*tmp_ebs
));
2131 /* Alloc memory in a row for data stripes */
2132 for (i
= 0; i
< num_stripes
; i
++) {
2133 if (raid_map
[i
] >= BTRFS_RAID5_P_STRIPE
)
2136 tmp_ebs
[i
] = calloc(1, sizeof(**tmp_ebs
) + stripe_len
);
2143 for (i
= 0; i
< num_stripes
; i
++) {
2144 struct extent_buffer
*eb
= tmp_ebs
[i
];
2146 if (raid_map
[i
] >= BTRFS_RAID5_P_STRIPE
)
2149 eb
->start
= raid_map
[i
];
2150 eb
->len
= stripe_len
;
2154 eb
->dev_bytenr
= (u64
)-1;
2156 this_eb_start
= raid_map
[i
];
2158 if (start
> this_eb_start
||
2159 start
+ orig_eb
->len
< this_eb_start
+ stripe_len
) {
2160 ret
= rmw_eb(info
, eb
, orig_eb
);
2164 memcpy(eb
->data
, orig_eb
->data
+ eb
->start
- start
,
2172 for (i
= 0; i
< num_stripes
; i
++)
2178 int write_raid56_with_parity(struct btrfs_fs_info
*info
,
2179 struct extent_buffer
*eb
,
2180 struct btrfs_multi_bio
*multi
,
2181 u64 stripe_len
, u64
*raid_map
)
2183 struct extent_buffer
**ebs
, *p_eb
= NULL
, *q_eb
= NULL
;
2186 int alloc_size
= eb
->len
;
2189 ebs
= malloc(sizeof(*ebs
) * multi
->num_stripes
);
2190 pointers
= malloc(sizeof(*pointers
) * multi
->num_stripes
);
2191 if (!ebs
|| !pointers
) {
2197 if (stripe_len
> alloc_size
)
2198 alloc_size
= stripe_len
;
2200 ret
= split_eb_for_raid56(info
, eb
, ebs
, stripe_len
, raid_map
,
2201 multi
->num_stripes
);
2205 for (i
= 0; i
< multi
->num_stripes
; i
++) {
2206 struct extent_buffer
*new_eb
;
2207 if (raid_map
[i
] < BTRFS_RAID5_P_STRIPE
) {
2208 ebs
[i
]->dev_bytenr
= multi
->stripes
[i
].physical
;
2209 ebs
[i
]->fd
= multi
->stripes
[i
].dev
->fd
;
2210 multi
->stripes
[i
].dev
->total_ios
++;
2211 if (ebs
[i
]->start
!= raid_map
[i
]) {
2213 goto out_free_split
;
2217 new_eb
= malloc(sizeof(*eb
) + alloc_size
);
2220 goto out_free_split
;
2222 new_eb
->dev_bytenr
= multi
->stripes
[i
].physical
;
2223 new_eb
->fd
= multi
->stripes
[i
].dev
->fd
;
2224 multi
->stripes
[i
].dev
->total_ios
++;
2225 new_eb
->len
= stripe_len
;
2227 if (raid_map
[i
] == BTRFS_RAID5_P_STRIPE
)
2229 else if (raid_map
[i
] == BTRFS_RAID6_Q_STRIPE
)
2233 ebs
[multi
->num_stripes
- 2] = p_eb
;
2234 ebs
[multi
->num_stripes
- 1] = q_eb
;
2236 for (i
= 0; i
< multi
->num_stripes
; i
++)
2237 pointers
[i
] = ebs
[i
]->data
;
2239 raid6_gen_syndrome(multi
->num_stripes
, stripe_len
, pointers
);
2241 ebs
[multi
->num_stripes
- 1] = p_eb
;
2242 for (i
= 0; i
< multi
->num_stripes
; i
++)
2243 pointers
[i
] = ebs
[i
]->data
;
2244 ret
= raid5_gen_result(multi
->num_stripes
, stripe_len
,
2245 multi
->num_stripes
- 1, pointers
);
2247 goto out_free_split
;
2250 for (i
= 0; i
< multi
->num_stripes
; i
++) {
2251 ret
= write_extent_to_disk(ebs
[i
]);
2253 goto out_free_split
;
2257 for (i
= 0; i
< multi
->num_stripes
; i
++) {