volumes.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <sys/types.h>
  21 #include <sys/stat.h>
  22 #include <uuid/uuid.h>
  23 #include <fcntl.h>
  24 #include <unistd.h>
  25 #include "ctree.h"
  26 #include "disk-io.h"
  27 #include "transaction.h"
  28 #include "print-tree.h"
  29 #include "volumes.h"
  30 #include "utils.h"
  31
  32 struct stripe {
  33         struct btrfs_device *dev;
  34         u64 physical;
  35 };
  36
  37 static inline int nr_parity_stripes(struct map_lookup *map)
  38 {
  39         if (map->type & BTRFS_BLOCK_GROUP_RAID5)
  40                 return 1;
  41         else if (map->type & BTRFS_BLOCK_GROUP_RAID6)
  42                 return 2;
  43         else
  44                 return 0;
  45 }
  46
  47 static inline int nr_data_stripes(struct map_lookup *map)
  48 {
  49         return map->num_stripes - nr_parity_stripes(map);
  50 }
  51
  52 #define is_parity_stripe(x) ( ((x) == BTRFS_RAID5_P_STRIPE) || ((x) == BTRFS_RAID6_Q_STRIPE) )
  53
  54 static LIST_HEAD(fs_uuids);
  55
  56 static struct btrfs_device *__find_device(struct list_head *head, u64 devid,
  57                                           u8 *uuid)
  58 {
  59         struct btrfs_device *dev;
  60         struct list_head *cur;
  61
  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)) {
  66                         return dev;
  67                 }
  68         }
  69         return NULL;
  70 }
  71
  72 static struct btrfs_fs_devices *find_fsid(u8 *fsid)
  73 {
  74         struct list_head *cur;
  75         struct btrfs_fs_devices *fs_devices;
  76
  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)
  80                         return fs_devices;
  81         }
  82         return NULL;
  83 }
  84
  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)
  88 {
  89         struct btrfs_device *device;
  90         struct btrfs_fs_devices *fs_devices;
  91         u64 found_transid = btrfs_super_generation(disk_super);
  92
  93         fs_devices = find_fsid(disk_super->fsid);
  94         if (!fs_devices) {
  95                 fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
  96                 if (!fs_devices)
  97                         return -ENOMEM;
  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;
 104                 device = NULL;
 105         } else {
 106                 device = __find_device(&fs_devices->devices, devid,
 107                                        disk_super->dev_item.uuid);
 108         }
 109         if (!device) {
 110                 device = kzalloc(sizeof(*device), GFP_NOFS);
 111                 if (!device) {
 112                         /* we can safely leave the fs_devices entry around */
 113                         return -ENOMEM;
 114                 }
 115                 device->fd = -1;
 116                 device->devid = devid;
 117                 device->generation = found_transid;
 118                 memcpy(device->uuid, disk_super->dev_item.uuid,
 119                        BTRFS_UUID_SIZE);
 120                 device->name = kstrdup(path, GFP_NOFS);
 121                 if (!device->name) {
 122                         kfree(device);
 123                         return -ENOMEM;
 124                 }
 125                 device->label = kstrdup(disk_super->label, GFP_NOFS);
 126                 if (!device->label) {
 127                         kfree(device->name);
 128                         kfree(device);
 129                         return -ENOMEM;
 130                 }
 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);
 135                 device->bytes_used =
 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);
 141                 if (!name)
 142                         return -ENOMEM;
 143                 kfree(device->name);
 144                 device->name = name;
 145         }
 146
 147
 148         if (found_transid > fs_devices->latest_trans) {
 149                 fs_devices->latest_devid = devid;
 150                 fs_devices->latest_trans = found_transid;
 151         }
 152         if (fs_devices->lowest_devid > devid) {
 153                 fs_devices->lowest_devid = devid;
 154         }
 155         *fs_devices_ret = fs_devices;
 156         return 0;
 157 }
 158
 159 int btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 160 {
 161         struct btrfs_fs_devices *seed_devices;
 162         struct btrfs_device *device;
 163
 164 again:
 165         if (!fs_devices)
 166                 return 0;
 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) {
 171                         fsync(device->fd);
 172                         if (posix_fadvise(device->fd, 0, 0, POSIX_FADV_DONTNEED))
 173                                 fprintf(stderr, "Warning, could not drop caches\n");
 174                         close(device->fd);
 175                         device->fd = -1;
 176                 }
 177                 device->writeable = 0;
 178                 list_del(&device->dev_list);
 179                 /* free the memory */
 180                 free(device->name);
 181                 free(device->label);
 182                 free(device);
 183         }
 184
 185         seed_devices = fs_devices->seed;
 186         fs_devices->seed = NULL;
 187         if (seed_devices) {
 188                 struct btrfs_fs_devices *orig;
 189
 190                 orig = fs_devices;
 191                 fs_devices = seed_devices;
 192                 list_del(&orig->list);
 193                 free(orig);
 194                 goto again;
 195         } else {
 196                 list_del(&fs_devices->list);
 197                 free(fs_devices);
 198         }
 199
 200         return 0;
 201 }
 202
 203 void btrfs_close_all_devices(void)
 204 {
 205         struct btrfs_fs_devices *fs_devices;
 206
 207         while (!list_empty(&fs_uuids)) {
 208                 fs_devices = list_entry(fs_uuids.next, struct btrfs_fs_devices,
 209                                         list);
 210                 btrfs_close_devices(fs_devices);
 211         }
 212 }
 213
 214 int btrfs_open_devices(struct btrfs_fs_devices *fs_devices, int flags)
 215 {
 216         int fd;
 217         struct list_head *head = &fs_devices->devices;
 218         struct list_head *cur;
 219         struct btrfs_device *device;
 220         int ret;
 221
 222         list_for_each(cur, head) {
 223                 device = list_entry(cur, struct btrfs_device, dev_list);
 224                 if (!device->name) {
 225                         printk("no name for device %llu, skip it now\n", device->devid);
 226                         continue;
 227                 }
 228
 229                 fd = open(device->name, flags);
 230                 if (fd < 0) {
 231                         ret = -errno;
 232                         error("cannot open device '%s': %s", device->name,
 233                                         strerror(errno));
 234                         goto fail;
 235                 }
 236
 237                 if (posix_fadvise(fd, 0, 0, POSIX_FADV_DONTNEED))
 238                         fprintf(stderr, "Warning, could not drop caches\n");
 239
 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;
 244                 device->fd = fd;
 245                 if (flags & O_RDWR)
 246                         device->writeable = 1;
 247         }
 248         return 0;
 249 fail:
 250         btrfs_close_devices(fs_devices);
 251         return ret;
 252 }
 253
 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)
 257 {
 258         struct btrfs_super_block *disk_super;
 259         char buf[BTRFS_SUPER_INFO_SIZE];
 260         int ret;
 261         u64 devid;
 262
 263         disk_super = (struct btrfs_super_block *)buf;
 264         ret = btrfs_read_dev_super(fd, disk_super, super_offset, sbflags);
 265         if (ret < 0)
 266                 return -EIO;
 267         devid = btrfs_stack_device_id(&disk_super->dev_item);
 268         if (btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_METADUMP)
 269                 *total_devs = 1;
 270         else
 271                 *total_devs = btrfs_super_num_devices(disk_super);
 272
 273         ret = device_list_add(path, disk_super, devid, fs_devices_ret);
 274
 275         return ret;
 276 }
 277
 278 /*
 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
 286  *
 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
 289  * of extents
 290  *
 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.
 294  *
 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.
 298  */
 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)
 302 {
 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;
 307         u64 hole_size;
 308         u64 max_hole_start;
 309         u64 max_hole_size;
 310         u64 extent_end;
 311         u64 search_end = device->total_bytes;
 312         int ret;
 313         int slot;
 314         struct extent_buffer *l;
 315         u64 min_search_start;
 316
 317         /*
 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.
 321          */
 322         min_search_start = max(root->fs_info->alloc_start, (u64)SZ_1M);
 323         search_start = max(search_start, min_search_start);
 324
 325         path = btrfs_alloc_path();
 326         if (!path)
 327                 return -ENOMEM;
 328
 329         max_hole_start = search_start;
 330         max_hole_size = 0;
 331
 332         if (search_start >= search_end) {
 333                 ret = -ENOSPC;
 334                 goto out;
 335         }
 336
 337         path->reada = 2;
 338
 339         key.objectid = device->devid;
 340         key.offset = search_start;
 341         key.type = BTRFS_DEV_EXTENT_KEY;
 342
 343         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 344         if (ret < 0)
 345                 goto out;
 346         if (ret > 0) {
 347                 ret = btrfs_previous_item(root, path, key.objectid, key.type);
 348                 if (ret < 0)
 349                         goto out;
 350         }
 351
 352         while (1) {
 353                 l = path->nodes[0];
 354                 slot = path->slots[0];
 355                 if (slot >= btrfs_header_nritems(l)) {
 356                         ret = btrfs_next_leaf(root, path);
 357                         if (ret == 0)
 358                                 continue;
 359                         if (ret < 0)
 360                                 goto out;
 361
 362                         break;
 363                 }
 364                 btrfs_item_key_to_cpu(l, &key, slot);
 365
 366                 if (key.objectid < device->devid)
 367                         goto next;
 368
 369                 if (key.objectid > device->devid)
 370                         break;
 371
 372                 if (key.type != BTRFS_DEV_EXTENT_KEY)
 373                         goto next;
 374
 375                 if (key.offset > search_start) {
 376                         hole_size = key.offset - search_start;
 377
 378                         /*
 379                          * Have to check before we set max_hole_start, otherwise
 380                          * we could end up sending back this offset anyway.
 381                          */
 382                         if (hole_size > max_hole_size) {
 383                                 max_hole_start = search_start;
 384                                 max_hole_size = hole_size;
 385                         }
 386
 387                         /*
 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
 394                          * caller.
 395                          */
 396                         if (hole_size >= num_bytes) {
 397                                 ret = 0;
 398                                 goto out;
 399                         }
 400                 }
 401
 402                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 403                 extent_end = key.offset + btrfs_dev_extent_length(l,
 404                                                                   dev_extent);
 405                 if (extent_end > search_start)
 406                         search_start = extent_end;
 407 next:
 408                 path->slots[0]++;
 409                 cond_resched();
 410         }
 411
 412         /*
 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.
 416          */
 417         if (search_end > search_start) {
 418                 hole_size = search_end - search_start;
 419
 420                 if (hole_size > max_hole_size) {
 421                         max_hole_start = search_start;
 422                         max_hole_size = hole_size;
 423                 }
 424         }
 425
 426         /* See above. */
 427         if (max_hole_size < num_bytes)
 428                 ret = -ENOSPC;
 429         else
 430                 ret = 0;
 431
 432 out:
 433         btrfs_free_path(path);
 434         *start = max_hole_start;
 435         if (len)
 436                 *len = max_hole_size;
 437         return ret;
 438 }
 439
 440 int find_free_dev_extent(struct btrfs_trans_handle *trans,
 441                          struct btrfs_device *device, u64 num_bytes,
 442                          u64 *start)
 443 {
 444         /* FIXME use last free of some kind */
 445         return find_free_dev_extent_start(trans, device,
 446                                           num_bytes, 0, start, NULL);
 447 }
 448
 449 static int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
 450                                   struct btrfs_device *device,
 451                                   u64 chunk_tree, u64 chunk_objectid,
 452                                   u64 chunk_offset,
 453                                   u64 num_bytes, u64 *start, int convert)
 454 {
 455         int ret;
 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;
 461
 462         path = btrfs_alloc_path();
 463         if (!path)
 464                 return -ENOMEM;
 465
 466         /*
 467          * For convert case, just skip search free dev_extent, as caller
 468          * is responsible to make sure it's free.
 469          */
 470         if (!convert) {
 471                 ret = find_free_dev_extent(trans, device, num_bytes,
 472                                            start);
 473                 if (ret)
 474                         goto err;
 475         }
 476
 477         key.objectid = device->devid;
 478         key.offset = *start;
 479         key.type = BTRFS_DEV_EXTENT_KEY;
 480         ret = btrfs_insert_empty_item(trans, root, path, &key,
 481                                       sizeof(*extent));
 482         BUG_ON(ret);
 483
 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);
 490
 491         write_extent_buffer(leaf, root->fs_info->chunk_tree_uuid,
 492                     (unsigned long)btrfs_dev_extent_chunk_tree_uuid(extent),
 493                     BTRFS_UUID_SIZE);
 494
 495         btrfs_set_dev_extent_length(leaf, extent, num_bytes);
 496         btrfs_mark_buffer_dirty(leaf);
 497 err:
 498         btrfs_free_path(path);
 499         return ret;
 500 }
 501
 502 static int find_next_chunk(struct btrfs_root *root, u64 objectid, u64 *offset)
 503 {
 504         struct btrfs_path *path;
 505         int ret;
 506         struct btrfs_key key;
 507         struct btrfs_chunk *chunk;
 508         struct btrfs_key found_key;
 509
 510         path = btrfs_alloc_path();
 511         if (!path)
 512                 return -ENOMEM;
 513
 514         key.objectid = objectid;
 515         key.offset = (u64)-1;
 516         key.type = BTRFS_CHUNK_ITEM_KEY;
 517
 518         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 519         if (ret < 0)
 520                 goto error;
 521
 522         BUG_ON(ret == 0);
 523
 524         ret = btrfs_previous_item(root, path, 0, BTRFS_CHUNK_ITEM_KEY);
 525         if (ret) {
 526                 *offset = 0;
 527         } else {
 528                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
 529                                       path->slots[0]);
 530                 if (found_key.objectid != objectid)
 531                         *offset = 0;
 532                 else {
 533                         chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
 534                                                struct btrfs_chunk);
 535                         *offset = found_key.offset +
 536                                 btrfs_chunk_length(path->nodes[0], chunk);
 537                 }
 538         }
 539         ret = 0;
 540 error:
 541         btrfs_free_path(path);
 542         return ret;
 543 }
 544
 545 static int find_next_devid(struct btrfs_root *root, struct btrfs_path *path,
 546                            u64 *objectid)
 547 {
 548         int ret;
 549         struct btrfs_key key;
 550         struct btrfs_key found_key;
 551
 552         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 553         key.type = BTRFS_DEV_ITEM_KEY;
 554         key.offset = (u64)-1;
 555
 556         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 557         if (ret < 0)
 558                 goto error;
 559
 560         BUG_ON(ret == 0);
 561
 562         ret = btrfs_previous_item(root, path, BTRFS_DEV_ITEMS_OBJECTID,
 563                                   BTRFS_DEV_ITEM_KEY);
 564         if (ret) {
 565                 *objectid = 1;
 566         } else {
 567                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
 568                                       path->slots[0]);
 569                 *objectid = found_key.offset + 1;
 570         }
 571         ret = 0;
 572 error:
 573         btrfs_release_path(path);
 574         return ret;
 575 }
 576
 577 /*
 578  * the device information is stored in the chunk root
 579  * the btrfs_device struct should be fully filled in
 580  */
 581 int btrfs_add_device(struct btrfs_trans_handle *trans,
 582                      struct btrfs_root *root,
 583                      struct btrfs_device *device)
 584 {
 585         int ret;
 586         struct btrfs_path *path;
 587         struct btrfs_dev_item *dev_item;
 588         struct extent_buffer *leaf;
 589         struct btrfs_key key;
 590         unsigned long ptr;
 591         u64 free_devid = 0;
 592
 593         root = root->fs_info->chunk_root;
 594
 595         path = btrfs_alloc_path();
 596         if (!path)
 597                 return -ENOMEM;
 598
 599         ret = find_next_devid(root, path, &free_devid);
 600         if (ret)
 601                 goto out;
 602
 603         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 604         key.type = BTRFS_DEV_ITEM_KEY;
 605         key.offset = free_devid;
 606
 607         ret = btrfs_insert_empty_item(trans, root, path, &key,
 608                                       sizeof(*dev_item));
 609         if (ret)
 610                 goto out;
 611
 612         leaf = path->nodes[0];
 613         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
 614
 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);
 628
 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);
 634         ret = 0;
 635
 636 out:
 637         btrfs_free_path(path);
 638         return ret;
 639 }
 640
 641 int btrfs_update_device(struct btrfs_trans_handle *trans,
 642                         struct btrfs_device *device)
 643 {
 644         int ret;
 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;
 650
 651         root = device->dev_root->fs_info->chunk_root;
 652
 653         path = btrfs_alloc_path();
 654         if (!path)
 655                 return -ENOMEM;
 656
 657         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 658         key.type = BTRFS_DEV_ITEM_KEY;
 659         key.offset = device->devid;
 660
 661         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 662         if (ret < 0)
 663                 goto out;
 664
 665         if (ret > 0) {
 666                 ret = -ENOENT;
 667                 goto out;
 668         }
 669
 670         leaf = path->nodes[0];
 671         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
 672
 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);
 681
 682 out:
 683         btrfs_free_path(path);
 684         return ret;
 685 }
 686
 687 int btrfs_add_system_chunk(struct btrfs_trans_handle *trans,
 688                            struct btrfs_root *root,
 689                            struct btrfs_key *key,
 690                            struct btrfs_chunk *chunk, int item_size)
 691 {
 692         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
 693         struct btrfs_disk_key disk_key;
 694         u32 array_size;
 695         u8 *ptr;
 696
 697         array_size = btrfs_super_sys_array_size(super_copy);
 698         if (array_size + item_size + sizeof(disk_key)
 699                         > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE)
 700                 return -EFBIG;
 701
 702         ptr = super_copy->sys_chunk_array + array_size;
 703         btrfs_cpu_key_to_disk(&disk_key, key);
 704         memcpy(ptr, &disk_key, sizeof(disk_key));
 705         ptr += sizeof(disk_key);
 706         memcpy(ptr, chunk, item_size);
 707         item_size += sizeof(disk_key);
 708         btrfs_set_super_sys_array_size(super_copy, array_size + item_size);
 709         return 0;
 710 }
 711
 712 static u64 chunk_bytes_by_type(u64 type, u64 calc_size, int num_stripes,
 713                                int sub_stripes)
 714 {
 715         if (type & (BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_DUP))
 716                 return calc_size;
 717         else if (type & BTRFS_BLOCK_GROUP_RAID10)
 718                 return calc_size * (num_stripes / sub_stripes);
 719         else if (type & BTRFS_BLOCK_GROUP_RAID5)
 720                 return calc_size * (num_stripes - 1);
 721         else if (type & BTRFS_BLOCK_GROUP_RAID6)
 722                 return calc_size * (num_stripes - 2);
 723         else
 724                 return calc_size * num_stripes;
 725 }
 726
 727
 728 static u32 find_raid56_stripe_len(u32 data_devices, u32 dev_stripe_target)
 729 {
 730         /* TODO, add a way to store the preferred stripe size */
 731         return BTRFS_STRIPE_LEN;
 732 }
 733
 734 /*
 735  * btrfs_device_avail_bytes - count bytes available for alloc_chunk
 736  *
 737  * It is not equal to "device->total_bytes - device->bytes_used".
 738  * We do not allocate any chunk in 1M at beginning of device, and not
 739  * allowed to allocate any chunk before alloc_start if it is specified.
 740  * So search holes from max(1M, alloc_start) to device->total_bytes.
 741  */
 742 static int btrfs_device_avail_bytes(struct btrfs_trans_handle *trans,
 743                                     struct btrfs_device *device,
 744                                     u64 *avail_bytes)
 745 {
 746         struct btrfs_path *path;
 747         struct btrfs_root *root = device->dev_root;
 748         struct btrfs_key key;
 749         struct btrfs_dev_extent *dev_extent = NULL;
 750         struct extent_buffer *l;
 751         u64 search_start = root->fs_info->alloc_start;
 752         u64 search_end = device->total_bytes;
 753         u64 extent_end = 0;
 754         u64 free_bytes = 0;
 755         int ret;
 756         int slot = 0;
 757
 758         search_start = max(BTRFS_BLOCK_RESERVED_1M_FOR_SUPER, search_start);
 759
 760         path = btrfs_alloc_path();
 761         if (!path)
 762                 return -ENOMEM;
 763
 764         key.objectid = device->devid;
 765         key.offset = root->fs_info->alloc_start;
 766         key.type = BTRFS_DEV_EXTENT_KEY;
 767
 768         path->reada = 2;
 769         ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
 770         if (ret < 0)
 771                 goto error;
 772         ret = btrfs_previous_item(root, path, 0, key.type);
 773         if (ret < 0)
 774                 goto error;
 775
 776         while (1) {
 777                 l = path->nodes[0];
 778                 slot = path->slots[0];
 779                 if (slot >= btrfs_header_nritems(l)) {
 780                         ret = btrfs_next_leaf(root, path);
 781                         if (ret == 0)
 782                                 continue;
 783                         if (ret < 0)
 784                                 goto error;
 785                         break;
 786                 }
 787                 btrfs_item_key_to_cpu(l, &key, slot);
 788
 789                 if (key.objectid < device->devid)
 790                         goto next;
 791                 if (key.objectid > device->devid)
 792                         break;
 793                 if (key.type != BTRFS_DEV_EXTENT_KEY)
 794                         goto next;
 795                 if (key.offset > search_end)
 796                         break;
 797                 if (key.offset > search_start)
 798                         free_bytes += key.offset - search_start;
 799
 800                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 801                 extent_end = key.offset + btrfs_dev_extent_length(l,
 802                                                                   dev_extent);
 803                 if (extent_end > search_start)
 804                         search_start = extent_end;
 805                 if (search_start > search_end)
 806                         break;
 807 next:
 808                 path->slots[0]++;
 809                 cond_resched();
 810         }
 811
 812         if (search_start < search_end)
 813                 free_bytes += search_end - search_start;
 814
 815         *avail_bytes = free_bytes;
 816         ret = 0;
 817 error:
 818         btrfs_free_path(path);
 819         return ret;
 820 }
 821
 822 #define BTRFS_MAX_DEVS(r) ((BTRFS_LEAF_DATA_SIZE(r)             \
 823                         - sizeof(struct btrfs_item)             \
 824                         - sizeof(struct btrfs_chunk))           \
 825                         / sizeof(struct btrfs_stripe) + 1)
 826
 827 #define BTRFS_MAX_DEVS_SYS_CHUNK ((BTRFS_SYSTEM_CHUNK_ARRAY_SIZE        \
 828                                 - 2 * sizeof(struct btrfs_disk_key)     \
 829                                 - 2 * sizeof(struct btrfs_chunk))       \
 830                                 / sizeof(struct btrfs_stripe) + 1)
 831
 832 int btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
 833                       struct btrfs_root *extent_root, u64 *start,
 834                       u64 *num_bytes, u64 type)
 835 {
 836         u64 dev_offset;
 837         struct btrfs_fs_info *info = extent_root->fs_info;
 838         struct btrfs_root *chunk_root = info->chunk_root;
 839         struct btrfs_stripe *stripes;
 840         struct btrfs_device *device = NULL;
 841         struct btrfs_chunk *chunk;
 842         struct list_head private_devs;
 843         struct list_head *dev_list = &info->fs_devices->devices;
 844         struct list_head *cur;
 845         struct map_lookup *map;
 846         int min_stripe_size = SZ_1M;
 847         u64 calc_size = SZ_8M;
 848         u64 min_free;
 849         u64 max_chunk_size = 4 * calc_size;
 850         u64 avail = 0;
 851         u64 max_avail = 0;
 852         u64 percent_max;
 853         int num_stripes = 1;
 854         int max_stripes = 0;
 855         int min_stripes = 1;
 856         int sub_stripes = 0;
 857         int looped = 0;
 858         int ret;
 859         int index;
 860         int stripe_len = BTRFS_STRIPE_LEN;
 861         struct btrfs_key key;
 862         u64 offset;
 863
 864         if (list_empty(dev_list)) {
 865                 return -ENOSPC;
 866         }
 867
 868         if (type & (BTRFS_BLOCK_GROUP_RAID0 | BTRFS_BLOCK_GROUP_RAID1 |
 869                     BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6 |
 870                     BTRFS_BLOCK_GROUP_RAID10 |
 871                     BTRFS_BLOCK_GROUP_DUP)) {
 872                 if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
 873                         calc_size = SZ_8M;
 874                         max_chunk_size = calc_size * 2;
 875                         min_stripe_size = SZ_1M;
 876                         max_stripes = BTRFS_MAX_DEVS_SYS_CHUNK;
 877                 } else if (type & BTRFS_BLOCK_GROUP_DATA) {
 878                         calc_size = SZ_1G;
 879                         max_chunk_size = 10 * calc_size;
 880                         min_stripe_size = SZ_64M;
 881                         max_stripes = BTRFS_MAX_DEVS(chunk_root);
 882                 } else if (type & BTRFS_BLOCK_GROUP_METADATA) {
 883                         calc_size = SZ_1G;
 884                         max_chunk_size = 4 * calc_size;
 885                         min_stripe_size = SZ_32M;
 886                         max_stripes = BTRFS_MAX_DEVS(chunk_root);
 887                 }
 888         }
 889         if (type & BTRFS_BLOCK_GROUP_RAID1) {
 890                 num_stripes = min_t(u64, 2,
 891                                   btrfs_super_num_devices(info->super_copy));
 892                 if (num_stripes < 2)
 893                         return -ENOSPC;
 894                 min_stripes = 2;
 895         }
 896         if (type & BTRFS_BLOCK_GROUP_DUP) {
 897                 num_stripes = 2;
 898                 min_stripes = 2;
 899         }
 900         if (type & (BTRFS_BLOCK_GROUP_RAID0)) {
 901                 num_stripes = btrfs_super_num_devices(info->super_copy);
 902                 if (num_stripes > max_stripes)
 903                         num_stripes = max_stripes;
 904                 min_stripes = 2;
 905         }
 906         if (type & (BTRFS_BLOCK_GROUP_RAID10)) {
 907                 num_stripes = btrfs_super_num_devices(info->super_copy);
 908                 if (num_stripes > max_stripes)
 909                         num_stripes = max_stripes;
 910                 if (num_stripes < 4)
 911                         return -ENOSPC;
 912                 num_stripes &= ~(u32)1;
 913                 sub_stripes = 2;
 914                 min_stripes = 4;
 915         }
 916         if (type & (BTRFS_BLOCK_GROUP_RAID5)) {
 917                 num_stripes = btrfs_super_num_devices(info->super_copy);
 918                 if (num_stripes > max_stripes)
 919                         num_stripes = max_stripes;
 920                 if (num_stripes < 2)
 921                         return -ENOSPC;
 922                 min_stripes = 2;
 923                 stripe_len = find_raid56_stripe_len(num_stripes - 1,
 924                                     btrfs_super_stripesize(info->super_copy));
 925         }
 926         if (type & (BTRFS_BLOCK_GROUP_RAID6)) {
 927                 num_stripes = btrfs_super_num_devices(info->super_copy);
 928                 if (num_stripes > max_stripes)
 929                         num_stripes = max_stripes;
 930                 if (num_stripes < 3)
 931                         return -ENOSPC;
 932                 min_stripes = 3;
 933                 stripe_len = find_raid56_stripe_len(num_stripes - 2,
 934                                     btrfs_super_stripesize(info->super_copy));
 935         }
 936
 937         /* we don't want a chunk larger than 10% of the FS */
 938         percent_max = div_factor(btrfs_super_total_bytes(info->super_copy), 1);
 939         max_chunk_size = min(percent_max, max_chunk_size);
 940
 941 again:
 942         if (chunk_bytes_by_type(type, calc_size, num_stripes, sub_stripes) >
 943             max_chunk_size) {
 944                 calc_size = max_chunk_size;
 945                 calc_size /= num_stripes;
 946                 calc_size /= stripe_len;
 947                 calc_size *= stripe_len;
 948         }
 949         /* we don't want tiny stripes */
 950         calc_size = max_t(u64, calc_size, min_stripe_size);
 951
 952         calc_size /= stripe_len;
 953         calc_size *= stripe_len;
 954         INIT_LIST_HEAD(&private_devs);
 955         cur = dev_list->next;
 956         index = 0;
 957
 958         if (type & BTRFS_BLOCK_GROUP_DUP)
 959                 min_free = calc_size * 2;
 960         else
 961                 min_free = calc_size;
 962
 963         /* build a private list of devices we will allocate from */
 964         while(index < num_stripes) {
 965                 device = list_entry(cur, struct btrfs_device, dev_list);
 966                 ret = btrfs_device_avail_bytes(trans, device, &avail);
 967                 if (ret)
 968                         return ret;
 969                 cur = cur->next;
 970                 if (avail >= min_free) {
 971                         list_move_tail(&device->dev_list, &private_devs);
 972                         index++;
 973                         if (type & BTRFS_BLOCK_GROUP_DUP)
 974                                 index++;
 975                 } else if (avail > max_avail)
 976                         max_avail = avail;
 977                 if (cur == dev_list)
 978                         break;
 979         }
 980         if (index < num_stripes) {
 981                 list_splice(&private_devs, dev_list);
 982                 if (index >= min_stripes) {
 983                         num_stripes = index;
 984                         if (type & (BTRFS_BLOCK_GROUP_RAID10)) {
 985                                 num_stripes /= sub_stripes;
 986                                 num_stripes *= sub_stripes;
 987                         }
 988                         looped = 1;
 989                         goto again;
 990                 }
 991                 if (!looped && max_avail > 0) {
 992                         looped = 1;
 993                         calc_size = max_avail;
 994                         goto again;
 995                 }
 996                 return -ENOSPC;
 997         }
 998         ret = find_next_chunk(chunk_root, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
 999                               &offset);
1000         if (ret)
1001                 return ret;
1002         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1003         key.type = BTRFS_CHUNK_ITEM_KEY;
1004         key.offset = offset;
1005
1006         chunk = kmalloc(btrfs_chunk_item_size(num_stripes), GFP_NOFS);
1007         if (!chunk)
1008                 return -ENOMEM;
1009
1010         map = kmalloc(btrfs_map_lookup_size(num_stripes), GFP_NOFS);
1011         if (!map) {
1012                 kfree(chunk);
1013                 return -ENOMEM;
1014         }
1015
1016         stripes = &chunk->stripe;
1017         *num_bytes = chunk_bytes_by_type(type, calc_size,
1018                                          num_stripes, sub_stripes);
1019         index = 0;
1020         while(index < num_stripes) {
1021                 struct btrfs_stripe *stripe;
1022                 BUG_ON(list_empty(&private_devs));
1023                 cur = private_devs.next;
1024                 device = list_entry(cur, struct btrfs_device, dev_list);
1025
1026                 /* loop over this device again if we're doing a dup group */
1027                 if (!(type & BTRFS_BLOCK_GROUP_DUP) ||
1028                     (index == num_stripes - 1))
1029                         list_move_tail(&device->dev_list, dev_list);
1030
1031                 ret = btrfs_alloc_dev_extent(trans, device,
1032                              info->chunk_root->root_key.objectid,
1033                              BTRFS_FIRST_CHUNK_TREE_OBJECTID, key.offset,
1034                              calc_size, &dev_offset, 0);
1035                 BUG_ON(ret);
1036
1037                 device->bytes_used += calc_size;
1038                 ret = btrfs_update_device(trans, device);
1039                 BUG_ON(ret);
1040
1041                 map->stripes[index].dev = device;
1042                 map->stripes[index].physical = dev_offset;
1043                 stripe = stripes + index;
1044                 btrfs_set_stack_stripe_devid(stripe, device->devid);
1045                 btrfs_set_stack_stripe_offset(stripe, dev_offset);
1046                 memcpy(stripe->dev_uuid, device->uuid, BTRFS_UUID_SIZE);
1047                 index++;
1048         }
1049         BUG_ON(!list_empty(&private_devs));
1050
1051         /* key was set above */
1052         btrfs_set_stack_chunk_length(chunk, *num_bytes);
1053         btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
1054         btrfs_set_stack_chunk_stripe_len(chunk, stripe_len);
1055         btrfs_set_stack_chunk_type(chunk, type);
1056         btrfs_set_stack_chunk_num_stripes(chunk, num_stripes);
1057         btrfs_set_stack_chunk_io_align(chunk, stripe_len);
1058         btrfs_set_stack_chunk_io_width(chunk, stripe_len);
1059         btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
1060         btrfs_set_stack_chunk_sub_stripes(chunk, sub_stripes);
1061         map->sector_size = extent_root->sectorsize;
1062         map->stripe_len = stripe_len;
1063         map->io_align = stripe_len;
1064         map->io_width = stripe_len;
1065         map->type = type;
1066         map->num_stripes = num_stripes;
1067         map->sub_stripes = sub_stripes;
1068
1069         ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1070                                 btrfs_chunk_item_size(num_stripes));
1071         BUG_ON(ret);
1072         *start = key.offset;;
1073
1074         map->ce.start = key.offset;
1075         map->ce.size = *num_bytes;
1076
1077         ret = insert_cache_extent(&info->mapping_tree.cache_tree, &map->ce);
1078         BUG_ON(ret);
1079
1080         if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
1081                 ret = btrfs_add_system_chunk(trans, chunk_root, &key,
1082                                     chunk, btrfs_chunk_item_size(num_stripes));
1083                 BUG_ON(ret);
1084         }
1085
1086         kfree(chunk);
1087         return ret;
1088 }
1089
1090 /*
1091  * Alloc a DATA chunk with SINGLE profile.
1092  *
1093  * If 'convert' is set, it will alloc a chunk with 1:1 mapping
1094  * (btrfs logical bytenr == on-disk bytenr)
1095  * For that case, caller must make sure the chunk and dev_extent are not
1096  * occupied.
1097  */
1098 int btrfs_alloc_data_chunk(struct btrfs_trans_handle *trans,
1099                            struct btrfs_root *extent_root, u64 *start,
1100                            u64 num_bytes, u64 type, int convert)
1101 {
1102         u64 dev_offset;
1103         struct btrfs_fs_info *info = extent_root->fs_info;
1104         struct btrfs_root *chunk_root = info->chunk_root;
1105         struct btrfs_stripe *stripes;
1106         struct btrfs_device *device = NULL;
1107         struct btrfs_chunk *chunk;
1108         struct list_head *dev_list = &info->fs_devices->devices;
1109         struct list_head *cur;
1110         struct map_lookup *map;
1111         u64 calc_size = SZ_8M;
1112         int num_stripes = 1;
1113         int sub_stripes = 0;
1114         int ret;
1115         int index;
1116         int stripe_len = BTRFS_STRIPE_LEN;
1117         struct btrfs_key key;
1118
1119         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1120         key.type = BTRFS_CHUNK_ITEM_KEY;
1121         if (convert) {
1122                 if (*start != round_down(*start, extent_root->sectorsize)) {
1123                         error("DATA chunk start not sectorsize aligned: %llu",
1124                                         (unsigned long long)*start);
1125                         return -EINVAL;
1126                 }
1127                 key.offset = *start;
1128                 dev_offset = *start;
1129         } else {
1130                 u64 tmp;
1131
1132                 ret = find_next_chunk(chunk_root,
1133                                       BTRFS_FIRST_CHUNK_TREE_OBJECTID,
1134                                       &tmp);
1135                 key.offset = tmp;
1136                 if (ret)
1137                         return ret;
1138         }
1139
1140         chunk = kmalloc(btrfs_chunk_item_size(num_stripes), GFP_NOFS);
1141         if (!chunk)
1142                 return -ENOMEM;
1143
1144         map = kmalloc(btrfs_map_lookup_size(num_stripes), GFP_NOFS);
1145         if (!map) {
1146                 kfree(chunk);
1147                 return -ENOMEM;
1148         }
1149
1150         stripes = &chunk->stripe;
1151         calc_size = num_bytes;
1152
1153         index = 0;
1154         cur = dev_list->next;
1155         device = list_entry(cur, struct btrfs_device, dev_list);
1156
1157         while (index < num_stripes) {
1158                 struct btrfs_stripe *stripe;
1159
1160                 ret = btrfs_alloc_dev_extent(trans, device,
1161                              info->chunk_root->root_key.objectid,
1162                              BTRFS_FIRST_CHUNK_TREE_OBJECTID, key.offset,
1163                              calc_size, &dev_offset, convert);
1164                 BUG_ON(ret);
1165
1166                 device->bytes_used += calc_size;
1167                 ret = btrfs_update_device(trans, device);
1168                 BUG_ON(ret);
1169
1170                 map->stripes[index].dev = device;
1171                 map->stripes[index].physical = dev_offset;
1172                 stripe = stripes + index;
1173                 btrfs_set_stack_stripe_devid(stripe, device->devid);
1174                 btrfs_set_stack_stripe_offset(stripe, dev_offset);
1175                 memcpy(stripe->dev_uuid, device->uuid, BTRFS_UUID_SIZE);
1176                 index++;
1177         }
1178
1179         /* key was set above */
1180         btrfs_set_stack_chunk_length(chunk, num_bytes);
1181         btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
1182         btrfs_set_stack_chunk_stripe_len(chunk, stripe_len);
1183         btrfs_set_stack_chunk_type(chunk, type);
1184         btrfs_set_stack_chunk_num_stripes(chunk, num_stripes);
1185         btrfs_set_stack_chunk_io_align(chunk, stripe_len);
1186         btrfs_set_stack_chunk_io_width(chunk, stripe_len);
1187         btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
1188         btrfs_set_stack_chunk_sub_stripes(chunk, sub_stripes);
1189         map->sector_size = extent_root->sectorsize;
1190         map->stripe_len = stripe_len;
1191         map->io_align = stripe_len;
1192         map->io_width = stripe_len;
1193         map->type = type;
1194         map->num_stripes = num_stripes;
1195         map->sub_stripes = sub_stripes;
1196
1197         ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1198                                 btrfs_chunk_item_size(num_stripes));
1199         BUG_ON(ret);
1200         if (!convert)
1201                 *start = key.offset;
1202
1203         map->ce.start = key.offset;
1204         map->ce.size = num_bytes;
1205
1206         ret = insert_cache_extent(&info->mapping_tree.cache_tree, &map->ce);
1207         BUG_ON(ret);
1208
1209         kfree(chunk);
1210         return ret;
1211 }
1212
1213 int btrfs_num_copies(struct btrfs_mapping_tree *map_tree, u64 logical, u64 len)
1214 {
1215         struct cache_extent *ce;
1216         struct map_lookup *map;
1217         int ret;
1218
1219         ce = search_cache_extent(&map_tree->cache_tree, logical);
1220         if (!ce) {
1221                 fprintf(stderr, "No mapping for %llu-%llu\n",
1222                         (unsigned long long)logical,
1223                         (unsigned long long)logical+len);
1224                 return 1;
1225         }
1226         if (ce->start > logical || ce->start + ce->size < logical) {
1227                 fprintf(stderr, "Invalid mapping for %llu-%llu, got "
1228                         "%llu-%llu\n", (unsigned long long)logical,
1229                         (unsigned long long)logical+len,
1230                         (unsigned long long)ce->start,
1231                         (unsigned long long)ce->start + ce->size);
1232                 return 1;
1233         }
1234         map = container_of(ce, struct map_lookup, ce);
1235
1236         if (map->type & (BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID1))
1237                 ret = map->num_stripes;
1238         else if (map->type & BTRFS_BLOCK_GROUP_RAID10)
1239                 ret = map->sub_stripes;
1240         else if (map->type & BTRFS_BLOCK_GROUP_RAID5)
1241                 ret = 2;
1242         else if (map->type & BTRFS_BLOCK_GROUP_RAID6)
1243                 ret = 3;
1244         else
1245                 ret = 1;
1246         return ret;
1247 }
1248
1249 int btrfs_next_bg(struct btrfs_mapping_tree *map_tree, u64 *logical,
1250                      u64 *size, u64 type)
1251 {
1252         struct cache_extent *ce;
1253         struct map_lookup *map;
1254         u64 cur = *logical;
1255
1256         ce = search_cache_extent(&map_tree->cache_tree, cur);
1257
1258         while (ce) {
1259                 /*
1260                  * only jump to next bg if our cur is not 0
1261                  * As the initial logical for btrfs_next_bg() is 0, and
1262                  * if we jump to next bg, we skipped a valid bg.
1263                  */
1264                 if (cur) {
1265                         ce = next_cache_extent(ce);
1266                         if (!ce)
1267                                 return -ENOENT;
1268                 }
1269
1270                 cur = ce->start;
1271                 map = container_of(ce, struct map_lookup, ce);
1272                 if (map->type & type) {
1273                         *logical = ce->start;
1274                         *size = ce->size;
1275                         return 0;
1276                 }
1277         }
1278
1279         return -ENOENT;
1280 }
1281
1282 int btrfs_rmap_block(struct btrfs_mapping_tree *map_tree,
1283                      u64 chunk_start, u64 physical, u64 devid,
1284                      u64 **logical, int *naddrs, int *stripe_len)
1285 {
1286         struct cache_extent *ce;
1287         struct map_lookup *map;
1288         u64 *buf;
1289         u64 bytenr;
1290         u64 length;
1291         u64 stripe_nr;
1292         u64 rmap_len;
1293         int i, j, nr = 0;
1294
1295         ce = search_cache_extent(&map_tree->cache_tree, chunk_start);
1296         BUG_ON(!ce);
1297         map = container_of(ce, struct map_lookup, ce);
1298
1299         length = ce->size;
1300         rmap_len = map->stripe_len;
1301         if (map->type & BTRFS_BLOCK_GROUP_RAID10)
1302                 length = ce->size / (map->num_stripes / map->sub_stripes);
1303         else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
1304                 length = ce->size / map->num_stripes;
1305         else if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
1306                               BTRFS_BLOCK_GROUP_RAID6)) {
1307                 length = ce->size / nr_data_stripes(map);
1308                 rmap_len = map->stripe_len * nr_data_stripes(map);
1309         }
1310
1311         buf = kzalloc(sizeof(u64) * map->num_stripes, GFP_NOFS);
1312
1313         for (i = 0; i < map->num_stripes; i++) {
1314                 if (devid && map->stripes[i].dev->devid != devid)
1315                         continue;
1316                 if (map->stripes[i].physical > physical ||
1317                     map->stripes[i].physical + length <= physical)
1318                         continue;
1319
1320                 stripe_nr = (physical - map->stripes[i].physical) /
1321                             map->stripe_len;
1322
1323                 if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
1324                         stripe_nr = (stripe_nr * map->num_stripes + i) /
1325                                     map->sub_stripes;
1326                 } else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
1327                         stripe_nr = stripe_nr * map->num_stripes + i;
1328                 } /* else if RAID[56], multiply by nr_data_stripes().
1329                    * Alternatively, just use rmap_len below instead of
1330                    * map->stripe_len */
1331
1332                 bytenr = ce->start + stripe_nr * rmap_len;
1333                 for (j = 0; j < nr; j++) {
1334                         if (buf[j] == bytenr)
1335                                 break;
1336                 }
1337                 if (j == nr)
1338                         buf[nr++] = bytenr;
1339         }
1340
1341         *logical = buf;
1342         *naddrs = nr;
1343         *stripe_len = rmap_len;
1344
1345         return 0;
1346 }
1347
1348 static inline int parity_smaller(u64 a, u64 b)
1349 {
1350         return a > b;
1351 }
1352
1353 /* Bubble-sort the stripe set to put the parity/syndrome stripes last */
1354 static void sort_parity_stripes(struct btrfs_multi_bio *bbio, u64 *raid_map)
1355 {
1356         struct btrfs_bio_stripe s;
1357         int i;
1358         u64 l;
1359         int again = 1;
1360
1361         while (again) {
1362                 again = 0;
1363                 for (i = 0; i < bbio->num_stripes - 1; i++) {
1364                         if (parity_smaller(raid_map[i], raid_map[i+1])) {
1365                                 s = bbio->stripes[i];
1366                                 l = raid_map[i];
1367                                 bbio->stripes[i] = bbio->stripes[i+1];
1368                                 raid_map[i] = raid_map[i+1];
1369                                 bbio->stripes[i+1] = s;
1370                                 raid_map[i+1] = l;
1371                                 again = 1;
1372                         }
1373                 }
1374         }
1375 }
1376
1377 int btrfs_map_block(struct btrfs_mapping_tree *map_tree, int rw,
1378                     u64 logical, u64 *length,
1379                     struct btrfs_multi_bio **multi_ret, int mirror_num,
1380                     u64 **raid_map_ret)
1381 {
1382         return __btrfs_map_block(map_tree, rw, logical, length, NULL,
1383                                  multi_ret, mirror_num, raid_map_ret);
1384 }
1385
1386 int __btrfs_map_block(struct btrfs_mapping_tree *map_tree, int rw,
1387                     u64 logical, u64 *length, u64 *type,
1388                     struct btrfs_multi_bio **multi_ret, int mirror_num,
1389                     u64 **raid_map_ret)
1390 {
1391         struct cache_extent *ce;
1392         struct map_lookup *map;
1393         u64 offset;
1394         u64 stripe_offset;
1395         u64 stripe_nr;
1396         u64 *raid_map = NULL;
1397         int stripes_allocated = 8;
1398         int stripes_required = 1;
1399         int stripe_index;
1400         int i;
1401         struct btrfs_multi_bio *multi = NULL;
1402
1403         if (multi_ret && rw == READ) {
1404                 stripes_allocated = 1;
1405         }
1406 again:
1407         ce = search_cache_extent(&map_tree->cache_tree, logical);
1408         if (!ce) {
1409                 kfree(multi);
1410                 *length = (u64)-1;
1411                 return -ENOENT;
1412         }
1413         if (ce->start > logical) {
1414                 kfree(multi);
1415                 *length = ce->start - logical;
1416                 return -ENOENT;
1417         }
1418
1419         if (multi_ret) {
1420                 multi = kzalloc(btrfs_multi_bio_size(stripes_allocated),
1421                                 GFP_NOFS);
1422                 if (!multi)
1423                         return -ENOMEM;
1424         }
1425         map = container_of(ce, struct map_lookup, ce);
1426         offset = logical - ce->start;
1427
1428         if (rw == WRITE) {
1429                 if (map->type & (BTRFS_BLOCK_GROUP_RAID1 |
1430                                  BTRFS_BLOCK_GROUP_DUP)) {
1431                         stripes_required = map->num_stripes;
1432                 } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
1433                         stripes_required = map->sub_stripes;
1434                 }
1435         }
1436         if (map->type & (BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6)
1437             && multi_ret && ((rw & WRITE) || mirror_num > 1) && raid_map_ret) {
1438                     /* RAID[56] write or recovery. Return all stripes */
1439                     stripes_required = map->num_stripes;
1440
1441                     /* Only allocate the map if we've already got a large enough multi_ret */
1442                     if (stripes_allocated >= stripes_required) {
1443                             raid_map = kmalloc(sizeof(u64) * map->num_stripes, GFP_NOFS);
1444                             if (!raid_map) {
1445                                     kfree(multi);
1446                                     return -ENOMEM;
1447                             }
1448                     }
1449         }
1450
1451         /* if our multi bio struct is too small, back off and try again */
1452         if (multi_ret && stripes_allocated < stripes_required) {
1453                 stripes_allocated = stripes_required;
1454                 kfree(multi);
1455                 multi = NULL;
1456                 goto again;
1457         }
1458         stripe_nr = offset;
1459         /*
1460          * stripe_nr counts the total number of stripes we have to stride
1461          * to get to this block
1462          */
1463         stripe_nr = stripe_nr / map->stripe_len;
1464
1465         stripe_offset = stripe_nr * map->stripe_len;
1466         BUG_ON(offset < stripe_offset);
1467
1468         /* stripe_offset is the offset of this block in its stripe*/
1469         stripe_offset = offset - stripe_offset;
1470
1471         if (map->type & (BTRFS_BLOCK_GROUP_RAID0 | BTRFS_BLOCK_GROUP_RAID1 |
1472                          BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6 |
1473                          BTRFS_BLOCK_GROUP_RAID10 |
1474                          BTRFS_BLOCK_GROUP_DUP)) {
1475                 /* we limit the length of each bio to what fits in a stripe */
1476                 *length = min_t(u64, ce->size - offset,
1477                               map->stripe_len - stripe_offset);
1478         } else {
1479                 *length = ce->size - offset;
1480         }
1481
1482         if (!multi_ret)
1483                 goto out;
1484
1485         multi->num_stripes = 1;
1486         stripe_index = 0;
1487         if (map->type & BTRFS_BLOCK_GROUP_RAID1) {
1488                 if (rw == WRITE)
1489                         multi->num_stripes = map->num_stripes;
1490                 else if (mirror_num)
1491                         stripe_index = mirror_num - 1;
1492                 else
1493                         stripe_index = stripe_nr % map->num_stripes;
1494         } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
1495                 int factor = map->num_stripes / map->sub_stripes;
1496
1497                 stripe_index = stripe_nr % factor;
1498                 stripe_index *= map->sub_stripes;
1499
1500                 if (rw == WRITE)
1501                         multi->num_stripes = map->sub_stripes;
1502                 else if (mirror_num)
1503                         stripe_index += mirror_num - 1;
1504
1505                 stripe_nr = stripe_nr / factor;
1506         } else if (map->type & BTRFS_BLOCK_GROUP_DUP) {
1507                 if (rw == WRITE)
1508                         multi->num_stripes = map->num_stripes;
1509                 else if (mirror_num)
1510                         stripe_index = mirror_num - 1;
1511         } else if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
1512                                 BTRFS_BLOCK_GROUP_RAID6)) {
1513
1514                 if (raid_map) {
1515                         int rot;
1516                         u64 tmp;
1517                         u64 raid56_full_stripe_start;
1518                         u64 full_stripe_len = nr_data_stripes(map) * map->stripe_len;
1519
1520                         /*
1521                          * align the start of our data stripe in the logical
1522                          * address space
1523                          */
1524                         raid56_full_stripe_start = offset / full_stripe_len;
1525                         raid56_full_stripe_start *= full_stripe_len;
1526
1527                         /* get the data stripe number */
1528                         stripe_nr = raid56_full_stripe_start / map->stripe_len;
1529                         stripe_nr = stripe_nr / nr_data_stripes(map);
1530
1531                         /* Work out the disk rotation on this stripe-set */
1532                         rot = stripe_nr % map->num_stripes;
1533
1534                         /* Fill in the logical address of each stripe */
1535                         tmp = stripe_nr * nr_data_stripes(map);
1536
1537                         for (i = 0; i < nr_data_stripes(map); i++)
1538                                 raid_map[(i+rot) % map->num_stripes] =
1539                                         ce->start + (tmp + i) * map->stripe_len;
1540
1541                         raid_map[(i+rot) % map->num_stripes] = BTRFS_RAID5_P_STRIPE;
1542                         if (map->type & BTRFS_BLOCK_GROUP_RAID6)
1543                                 raid_map[(i+rot+1) % map->num_stripes] = BTRFS_RAID6_Q_STRIPE;
1544
1545                         *length = map->stripe_len;
1546                         stripe_index = 0;
1547                         stripe_offset = 0;
1548                         multi->num_stripes = map->num_stripes;
1549                 } else {
1550                         stripe_index = stripe_nr % nr_data_stripes(map);
1551                         stripe_nr = stripe_nr / nr_data_stripes(map);
1552
1553                         /*
1554                          * Mirror #0 or #1 means the original data block.
1555                          * Mirror #2 is RAID5 parity block.
1556                          * Mirror #3 is RAID6 Q block.
1557                          */
1558                         if (mirror_num > 1)
1559                                 stripe_index = nr_data_stripes(map) + mirror_num - 2;
1560
1561                         /* We distribute the parity blocks across stripes */
1562                         stripe_index = (stripe_nr + stripe_index) % map->num_stripes;
1563                 }
1564         } else {
1565                 /*
1566                  * after this do_div call, stripe_nr is the number of stripes
1567                  * on this device we have to walk to find the data, and
1568                  * stripe_index is the number of our device in the stripe array
1569                  */
1570                 stripe_index = stripe_nr % map->num_stripes;
1571                 stripe_nr = stripe_nr / map->num_stripes;
1572         }
1573         BUG_ON(stripe_index >= map->num_stripes);
1574
1575         for (i = 0; i < multi->num_stripes; i++) {
1576                 multi->stripes[i].physical =
1577                         map->stripes[stripe_index].physical + stripe_offset +
1578                         stripe_nr * map->stripe_len;
1579                 multi->stripes[i].dev = map->stripes[stripe_index].dev;
1580                 stripe_index++;
1581         }
1582         *multi_ret = multi;
1583
1584         if (type)
1585                 *type = map->type;
1586
1587         if (raid_map) {
1588                 sort_parity_stripes(multi, raid_map);
1589                 *raid_map_ret = raid_map;
1590         }
1591 out:
1592         return 0;
1593 }
1594
1595 struct btrfs_device *btrfs_find_device(struct btrfs_root *root, u64 devid,
1596                                        u8 *uuid, u8 *fsid)
1597 {
1598         struct btrfs_device *device;
1599         struct btrfs_fs_devices *cur_devices;
1600
1601         cur_devices = root->fs_info->fs_devices;
1602         while (cur_devices) {
1603                 if (!fsid ||
1604                     (!memcmp(cur_devices->fsid, fsid, BTRFS_UUID_SIZE) ||
1605                      root->fs_info->ignore_fsid_mismatch)) {
1606                         device = __find_device(&cur_devices->devices,
1607                                                devid, uuid);
1608                         if (device)
1609                                 return device;
1610                 }
1611                 cur_devices = cur_devices->seed;
1612         }
1613         return NULL;
1614 }
1615
1616 struct btrfs_device *
1617 btrfs_find_device_by_devid(struct btrfs_fs_devices *fs_devices,
1618                            u64 devid, int instance)
1619 {
1620         struct list_head *head = &fs_devices->devices;
1621         struct btrfs_device *dev;
1622         int num_found = 0;
1623
1624         list_for_each_entry(dev, head, dev_list) {
1625                 if (dev->devid == devid && num_found++ == instance)
1626                         return dev;
1627         }
1628         return NULL;
1629 }
1630
1631 int btrfs_chunk_readonly(struct btrfs_root *root, u64 chunk_offset)
1632 {
1633         struct cache_extent *ce;
1634         struct map_lookup *map;
1635         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
1636         int readonly = 0;
1637         int i;
1638
1639         /*
1640          * During chunk recovering, we may fail to find block group's
1641          * corresponding chunk, we will rebuild it later
1642          */
1643         ce = search_cache_extent(&map_tree->cache_tree, chunk_offset);
1644         if (!root->fs_info->is_chunk_recover)
1645                 BUG_ON(!ce);
1646         else
1647                 return 0;
1648
1649         map = container_of(ce, struct map_lookup, ce);
1650         for (i = 0; i < map->num_stripes; i++) {
1651                 if (!map->stripes[i].dev->writeable) {
1652                         readonly = 1;
1653                         break;
1654                 }
1655         }
1656
1657         return readonly;
1658 }
1659
1660 static struct btrfs_device *fill_missing_device(u64 devid)
1661 {
1662         struct btrfs_device *device;
1663
1664         device = kzalloc(sizeof(*device), GFP_NOFS);
1665         device->devid = devid;
1666         device->fd = -1;
1667         return device;
1668 }
1669
1670 /*
1671  * slot == -1: SYSTEM chunk
1672  * return -EIO on error, otherwise return 0
1673  */
1674 int btrfs_check_chunk_valid(struct btrfs_root *root,
1675                             struct extent_buffer *leaf,
1676                             struct btrfs_chunk *chunk,
1677                             int slot, u64 logical)
1678 {
1679         u64 length;
1680         u64 stripe_len;
1681         u16 num_stripes;
1682         u16 sub_stripes;
1683         u64 type;
1684
1685         length = btrfs_chunk_length(leaf, chunk);
1686         stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
1687         num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
1688         sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
1689         type = btrfs_chunk_type(leaf, chunk);
1690
1691         /*
1692          * These valid checks may be insufficient to cover every corner cases.
1693          */
1694         if (!IS_ALIGNED(logical, root->sectorsize)) {
1695                 error("invalid chunk logical %llu",  logical);
1696                 return -EIO;
1697         }
1698         if (btrfs_chunk_sector_size(leaf, chunk) != root->sectorsize) {
1699                 error("invalid chunk sectorsize %llu",
1700                       (unsigned long long)btrfs_chunk_sector_size(leaf, chunk));
1701                 return -EIO;
1702         }
1703         if (!length || !IS_ALIGNED(length, root->sectorsize)) {
1704                 error("invalid chunk length %llu",  length);
1705                 return -EIO;
1706         }
1707         if (stripe_len != BTRFS_STRIPE_LEN) {
1708                 error("invalid chunk stripe length: %llu", stripe_len);
1709                 return -EIO;
1710         }
1711         /* Check on chunk item type */
1712         if (slot == -1 && (type & BTRFS_BLOCK_GROUP_SYSTEM) == 0) {
1713                 error("invalid chunk type %llu", type);
1714                 return -EIO;
1715         }
1716         if (type & ~(BTRFS_BLOCK_GROUP_TYPE_MASK |
1717                      BTRFS_BLOCK_GROUP_PROFILE_MASK)) {
1718                 error("unrecognized chunk type: %llu",
1719                       ~(BTRFS_BLOCK_GROUP_TYPE_MASK |
1720                         BTRFS_BLOCK_GROUP_PROFILE_MASK) & type);
1721                 return -EIO;
1722         }
1723         /*
1724          * Btrfs_chunk contains at least one stripe, and for sys_chunk
1725          * it can't exceed the system chunk array size
1726          * For normal chunk, it should match its chunk item size.
1727          */
1728         if (num_stripes < 1 ||
1729             (slot == -1 && sizeof(struct btrfs_stripe) * num_stripes >
1730              BTRFS_SYSTEM_CHUNK_ARRAY_SIZE) ||
1731             (slot >= 0 && sizeof(struct btrfs_stripe) * (num_stripes - 1) >
1732              btrfs_item_size_nr(leaf, slot))) {
1733                 error("invalid num_stripes: %u", num_stripes);
1734                 return -EIO;
1735         }
1736         /*
1737          * Device number check against profile
1738          */
1739         if ((type & BTRFS_BLOCK_GROUP_RAID10 && sub_stripes == 0) ||
1740             (type & BTRFS_BLOCK_GROUP_RAID1 && num_stripes < 1) ||
1741             (type & BTRFS_BLOCK_GROUP_RAID5 && num_stripes < 2) ||
1742             (type & BTRFS_BLOCK_GROUP_RAID6 && num_stripes < 3) ||
1743             (type & BTRFS_BLOCK_GROUP_DUP && num_stripes > 2) ||
1744             ((type & BTRFS_BLOCK_GROUP_PROFILE_MASK) == 0 &&
1745              num_stripes != 1)) {
1746                 error("Invalid num_stripes:sub_stripes %u:%u for profile %llu",
1747                       num_stripes, sub_stripes,
1748                       type & BTRFS_BLOCK_GROUP_PROFILE_MASK);
1749                 return -EIO;
1750         }
1751
1752         return 0;
1753 }
1754
1755 /*
1756  * Slot is used to verify the chunk item is valid
1757  *
1758  * For sys chunk in superblock, pass -1 to indicate sys chunk.
1759  */
1760 static int read_one_chunk(struct btrfs_root *root, struct btrfs_key *key,
1761                           struct extent_buffer *leaf,
1762                           struct btrfs_chunk *chunk, int slot)
1763 {
1764         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
1765         struct map_lookup *map;
1766         struct cache_extent *ce;
1767         u64 logical;
1768         u64 length;
1769         u64 devid;
1770         u8 uuid[BTRFS_UUID_SIZE];
1771         int num_stripes;
1772         int ret;
1773         int i;
1774
1775         logical = key->offset;
1776         length = btrfs_chunk_length(leaf, chunk);
1777         num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
1778         /* Validation check */
1779         ret = btrfs_check_chunk_valid(root, leaf, chunk, slot, logical);
1780         if (ret) {
1781                 error("%s checksums match, but it has an invalid chunk, %s",
1782                       (slot == -1) ? "Superblock" : "Metadata",
1783                       (slot == -1) ? "try btrfsck --repair -s <superblock> ie, 0,1,2" : "");
1784                 return ret;
1785         }
1786
1787         ce = search_cache_extent(&map_tree->cache_tree, logical);
1788
1789         /* already mapped? */
1790         if (ce && ce->start <= logical && ce->start + ce->size > logical) {
1791                 return 0;
1792         }
1793
1794         map = kmalloc(btrfs_map_lookup_size(num_stripes), GFP_NOFS);
1795         if (!map)
1796                 return -ENOMEM;
1797
1798         map->ce.start = logical;
1799         map->ce.size = length;
1800         map->num_stripes = num_stripes;
1801         map->io_width = btrfs_chunk_io_width(leaf, chunk);
1802         map->io_align = btrfs_chunk_io_align(leaf, chunk);
1803         map->sector_size = btrfs_chunk_sector_size(leaf, chunk);
1804         map->stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
1805         map->type = btrfs_chunk_type(leaf, chunk);
1806         map->sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
1807
1808         for (i = 0; i < num_stripes; i++) {
1809                 map->stripes[i].physical =
1810                         btrfs_stripe_offset_nr(leaf, chunk, i);
1811                 devid = btrfs_stripe_devid_nr(leaf, chunk, i);
1812                 read_extent_buffer(leaf, uuid, (unsigned long)
1813                                    btrfs_stripe_dev_uuid_nr(chunk, i),
1814                                    BTRFS_UUID_SIZE);
1815                 map->stripes[i].dev = btrfs_find_device(root, devid, uuid,
1816                                                         NULL);
1817                 if (!map->stripes[i].dev) {
1818                         map->stripes[i].dev = fill_missing_device(devid);
1819                         printf("warning, device %llu is missing\n",
1820                                (unsigned long long)devid);
1821                         list_add(&map->stripes[i].dev->dev_list,
1822                                  &root->fs_info->fs_devices->devices);
1823                 }
1824
1825         }
1826         ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
1827         BUG_ON(ret);
1828
1829         return 0;
1830 }
1831
1832 static int fill_device_from_item(struct extent_buffer *leaf,
1833                                  struct btrfs_dev_item *dev_item,
1834                                  struct btrfs_device *device)
1835 {
1836         unsigned long ptr;
1837
1838         device->devid = btrfs_device_id(leaf, dev_item);
1839         device->total_bytes = btrfs_device_total_bytes(leaf, dev_item);
1840         device->bytes_used = btrfs_device_bytes_used(leaf, dev_item);
1841         device->type = btrfs_device_type(leaf, dev_item);
1842         device->io_align = btrfs_device_io_align(leaf, dev_item);
1843         device->io_width = btrfs_device_io_width(leaf, dev_item);
1844         device->sector_size = btrfs_device_sector_size(leaf, dev_item);
1845
1846         ptr = (unsigned long)btrfs_device_uuid(dev_item);
1847         read_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
1848
1849         return 0;
1850 }
1851
1852 static int open_seed_devices(struct btrfs_root *root, u8 *fsid)
1853 {
1854         struct btrfs_fs_devices *fs_devices;
1855         int ret;
1856
1857         fs_devices = root->fs_info->fs_devices->seed;
1858         while (fs_devices) {
1859                 if (!memcmp(fs_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
1860                         ret = 0;
1861                         goto out;
1862                 }
1863                 fs_devices = fs_devices->seed;
1864         }
1865
1866         fs_devices = find_fsid(fsid);
1867         if (!fs_devices) {
1868                 /* missing all seed devices */
1869                 fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
1870                 if (!fs_devices) {
1871                         ret = -ENOMEM;
1872                         goto out;
1873                 }
1874                 INIT_LIST_HEAD(&fs_devices->devices);
1875                 list_add(&fs_devices->list, &fs_uuids);
1876                 memcpy(fs_devices->fsid, fsid, BTRFS_FSID_SIZE);
1877         }
1878
1879         ret = btrfs_open_devices(fs_devices, O_RDONLY);
1880         if (ret)
1881                 goto out;
1882
1883         fs_devices->seed = root->fs_info->fs_devices->seed;
1884         root->fs_info->fs_devices->seed = fs_devices;
1885 out:
1886         return ret;
1887 }
1888
1889 static int read_one_dev(struct btrfs_root *root,
1890                         struct extent_buffer *leaf,
1891                         struct btrfs_dev_item *dev_item)
1892 {
1893         struct btrfs_device *device;
1894         u64 devid;
1895         int ret = 0;
1896         u8 fs_uuid[BTRFS_UUID_SIZE];
1897         u8 dev_uuid[BTRFS_UUID_SIZE];
1898
1899         devid = btrfs_device_id(leaf, dev_item);
1900         read_extent_buffer(leaf, dev_uuid,
1901                            (unsigned long)btrfs_device_uuid(dev_item),
1902                            BTRFS_UUID_SIZE);
1903         read_extent_buffer(leaf, fs_uuid,
1904                            (unsigned long)btrfs_device_fsid(dev_item),
1905                            BTRFS_UUID_SIZE);
1906
1907         if (memcmp(fs_uuid, root->fs_info->fsid, BTRFS_UUID_SIZE)) {
1908                 ret = open_seed_devices(root, fs_uuid);
1909                 if (ret)
1910                         return ret;
1911         }
1912
1913         device = btrfs_find_device(root, devid, dev_uuid, fs_uuid);
1914         if (!device) {
1915                 device = kzalloc(sizeof(*device), GFP_NOFS);
1916                 if (!device)
1917                         return -ENOMEM;
1918                 device->fd = -1;
1919                 list_add(&device->dev_list,
1920                          &root->fs_info->fs_devices->devices);
1921         }
1922
1923         fill_device_from_item(leaf, dev_item, device);
1924         device->dev_root = root->fs_info->dev_root;
1925         return ret;
1926 }
1927
1928 int btrfs_read_sys_array(struct btrfs_root *root)
1929 {
1930         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
1931         struct extent_buffer *sb;
1932         struct btrfs_disk_key *disk_key;
1933         struct btrfs_chunk *chunk;
1934         u8 *array_ptr;
1935         unsigned long sb_array_offset;
1936         int ret = 0;
1937         u32 num_stripes;
1938         u32 array_size;
1939         u32 len = 0;
1940         u32 cur_offset;
1941         struct btrfs_key key;
1942
1943         sb = btrfs_find_create_tree_block(root->fs_info,
1944                                           BTRFS_SUPER_INFO_OFFSET,
1945                                           BTRFS_SUPER_INFO_SIZE);
1946         if (!sb)
1947                 return -ENOMEM;
1948         btrfs_set_buffer_uptodate(sb);
1949         write_extent_buffer(sb, super_copy, 0, sizeof(*super_copy));
1950         array_size = btrfs_super_sys_array_size(super_copy);
1951
1952         array_ptr = super_copy->sys_chunk_array;
1953         sb_array_offset = offsetof(struct btrfs_super_block, sys_chunk_array);
1954         cur_offset = 0;
1955
1956         while (cur_offset < array_size) {
1957                 disk_key = (struct btrfs_disk_key *)array_ptr;
1958                 len = sizeof(*disk_key);
1959                 if (cur_offset + len > array_size)
1960                         goto out_short_read;
1961
1962                 btrfs_disk_key_to_cpu(&key, disk_key);
1963
1964                 array_ptr += len;
1965                 sb_array_offset += len;
1966                 cur_offset += len;
1967
1968                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
1969                         chunk = (struct btrfs_chunk *)sb_array_offset;
1970                         /*
1971                          * At least one btrfs_chunk with one stripe must be
1972                          * present, exact stripe count check comes afterwards
1973                          */
1974                         len = btrfs_chunk_item_size(1);
1975                         if (cur_offset + len > array_size)
1976                                 goto out_short_read;
1977
1978                         num_stripes = btrfs_chunk_num_stripes(sb, chunk);
1979                         if (!num_stripes) {
1980                                 printk(
1981             "ERROR: invalid number of stripes %u in sys_array at offset %u\n",
1982                                         num_stripes, cur_offset);
1983                                 ret = -EIO;
1984                                 break;
1985                         }
1986
1987                         len = btrfs_chunk_item_size(num_stripes);
1988                         if (cur_offset + len > array_size)
1989                                 goto out_short_read;
1990
1991                         ret = read_one_chunk(root, &key, sb, chunk, -1);
1992                         if (ret)
1993                                 break;
1994                 } else {
1995                         printk(
1996                 "ERROR: unexpected item type %u in sys_array at offset %u\n",
1997                                 (u32)key.type, cur_offset);
1998                         ret = -EIO;
1999                         break;
2000                 }
2001                 array_ptr += len;
2002                 sb_array_offset += len;
2003                 cur_offset += len;
2004         }
2005         free_extent_buffer(sb);
2006         return ret;
2007
2008 out_short_read:
2009         printk("ERROR: sys_array too short to read %u bytes at offset %u\n",
2010                         len, cur_offset);
2011         free_extent_buffer(sb);
2012         return -EIO;
2013 }
2014
2015 int btrfs_read_chunk_tree(struct btrfs_root *root)
2016 {
2017         struct btrfs_path *path;
2018         struct extent_buffer *leaf;
2019         struct btrfs_key key;
2020         struct btrfs_key found_key;
2021         int ret;
2022         int slot;
2023
2024         root = root->fs_info->chunk_root;
2025
2026         path = btrfs_alloc_path();
2027         if (!path)
2028                 return -ENOMEM;
2029
2030         /*
2031          * Read all device items, and then all the chunk items. All
2032          * device items are found before any chunk item (their object id
2033          * is smaller than the lowest possible object id for a chunk
2034          * item - BTRFS_FIRST_CHUNK_TREE_OBJECTID).
2035          */
2036         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
2037         key.offset = 0;
2038         key.type = 0;
2039         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2040         if (ret < 0)
2041                 goto error;
2042         while(1) {
2043                 leaf = path->nodes[0];
2044                 slot = path->slots[0];
2045                 if (slot >= btrfs_header_nritems(leaf)) {
2046                         ret = btrfs_next_leaf(root, path);
2047                         if (ret == 0)
2048                                 continue;
2049                         if (ret < 0)
2050                                 goto error;
2051                         break;
2052                 }
2053                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
2054                 if (found_key.type == BTRFS_DEV_ITEM_KEY) {
2055                         struct btrfs_dev_item *dev_item;
2056                         dev_item = btrfs_item_ptr(leaf, slot,
2057                                                   struct btrfs_dev_item);
2058                         ret = read_one_dev(root, leaf, dev_item);
2059                         BUG_ON(ret);
2060                 } else if (found_key.type == BTRFS_CHUNK_ITEM_KEY) {
2061                         struct btrfs_chunk *chunk;
2062                         chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
2063                         ret = read_one_chunk(root, &found_key, leaf, chunk,
2064                                              slot);
2065                         BUG_ON(ret);
2066                 }
2067                 path->slots[0]++;
2068         }
2069
2070         ret = 0;
2071 error:
2072         btrfs_free_path(path);
2073         return ret;
2074 }
2075
2076 struct list_head *btrfs_scanned_uuids(void)
2077 {
2078         return &fs_uuids;
2079 }
2080
2081 static int rmw_eb(struct btrfs_fs_info *info,
2082                   struct extent_buffer *eb, struct extent_buffer *orig_eb)
2083 {
2084         int ret;
2085         unsigned long orig_off = 0;
2086         unsigned long dest_off = 0;
2087         unsigned long copy_len = eb->len;
2088
2089         ret = read_whole_eb(info, eb, 0);
2090         if (ret)
2091                 return ret;
2092
2093         if (eb->start + eb->len <= orig_eb->start ||
2094             eb->start >= orig_eb->start + orig_eb->len)
2095                 return 0;
2096         /*
2097          * | ----- orig_eb ------- |
2098          *         | ----- stripe -------  |
2099          *         | ----- orig_eb ------- |
2100          *              | ----- orig_eb ------- |
2101          */
2102         if (eb->start > orig_eb->start)
2103                 orig_off = eb->start - orig_eb->start;
2104         if (orig_eb->start > eb->start)
2105                 dest_off = orig_eb->start - eb->start;
2106
2107         if (copy_len > orig_eb->len - orig_off)
2108                 copy_len = orig_eb->len - orig_off;
2109         if (copy_len > eb->len - dest_off)
2110                 copy_len = eb->len - dest_off;
2111
2112         memcpy(eb->data + dest_off, orig_eb->data + orig_off, copy_len);
2113         return 0;
2114 }
2115
2116 static int split_eb_for_raid56(struct btrfs_fs_info *info,
2117                                struct extent_buffer *orig_eb,
2118                                struct extent_buffer **ebs,
2119                                u64 stripe_len, u64 *raid_map,
2120                                int num_stripes)
2121 {
2122         struct extent_buffer **tmp_ebs;
2123         u64 start = orig_eb->start;
2124         u64 this_eb_start;
2125         int i;
2126         int ret = 0;
2127
2128         tmp_ebs = calloc(num_stripes, sizeof(*tmp_ebs));
2129         if (!tmp_ebs)
2130                 return -ENOMEM;
2131
2132         /* Alloc memory in a row for data stripes */
2133         for (i = 0; i < num_stripes; i++) {
2134                 if (raid_map[i] >= BTRFS_RAID5_P_STRIPE)
2135                         break;
2136
2137                 tmp_ebs[i] = calloc(1, sizeof(**tmp_ebs) + stripe_len);
2138                 if (!tmp_ebs[i]) {
2139                         ret = -ENOMEM;
2140                         goto clean_up;
2141                 }
2142         }
2143
2144         for (i = 0; i < num_stripes; i++) {
2145                 struct extent_buffer *eb = tmp_ebs[i];
2146
2147                 if (raid_map[i] >= BTRFS_RAID5_P_STRIPE)
2148                         break;
2149
2150                 eb->start = raid_map[i];
2151                 eb->len = stripe_len;
2152                 eb->refs = 1;
2153                 eb->flags = 0;
2154                 eb->fd = -1;
2155                 eb->dev_bytenr = (u64)-1;
2156
2157                 this_eb_start = raid_map[i];
2158
2159                 if (start > this_eb_start ||
2160                     start + orig_eb->len < this_eb_start + stripe_len) {
2161                         ret = rmw_eb(info, eb, orig_eb);
2162                         if (ret)
2163                                 goto clean_up;
2164                 } else {
2165                         memcpy(eb->data, orig_eb->data + eb->start - start,
2166                                stripe_len);
2167                 }
2168                 ebs[i] = eb;
2169         }
2170         free(tmp_ebs);
2171         return ret;
2172 clean_up:
2173         for (i = 0; i < num_stripes; i++)
2174                 free(tmp_ebs[i]);
2175         free(tmp_ebs);
2176         return ret;
2177 }
2178
2179 int write_raid56_with_parity(struct btrfs_fs_info *info,
2180                              struct extent_buffer *eb,
2181                              struct btrfs_multi_bio *multi,
2182                              u64 stripe_len, u64 *raid_map)
2183 {
2184         struct extent_buffer **ebs, *p_eb = NULL, *q_eb = NULL;
2185         int i;
2186         int ret;
2187         int alloc_size = eb->len;
2188         void **pointers;
2189
2190         ebs = malloc(sizeof(*ebs) * multi->num_stripes);
2191         pointers = malloc(sizeof(*pointers) * multi->num_stripes);
2192         if (!ebs || !pointers) {
2193                 free(ebs);
2194                 free(pointers);
2195                 return -ENOMEM;
2196         }
2197
2198         if (stripe_len > alloc_size)
2199                 alloc_size = stripe_len;
2200
2201         ret = split_eb_for_raid56(info, eb, ebs, stripe_len, raid_map,
2202                                   multi->num_stripes);
2203         if (ret)
2204                 goto out;
2205
2206         for (i = 0; i < multi->num_stripes; i++) {
2207                 struct extent_buffer *new_eb;
2208                 if (raid_map[i] < BTRFS_RAID5_P_STRIPE) {
2209                         ebs[i]->dev_bytenr = multi->stripes[i].physical;
2210                         ebs[i]->fd = multi->stripes[i].dev->fd;
2211                         multi->stripes[i].dev->total_ios++;
2212                         if (ebs[i]->start != raid_map[i]) {
2213                                 ret = -EINVAL;
2214                                 goto out_free_split;
2215                         }
2216                         continue;
2217                 }
2218                 new_eb = malloc(sizeof(*eb) + alloc_size);
2219                 if (!new_eb) {
2220                         ret = -ENOMEM;
2221                         goto out_free_split;
2222                 }
2223                 new_eb->dev_bytenr = multi->stripes[i].physical;
2224                 new_eb->fd = multi->stripes[i].dev->fd;
2225                 multi->stripes[i].dev->total_ios++;
2226                 new_eb->len = stripe_len;
2227
2228                 if (raid_map[i] == BTRFS_RAID5_P_STRIPE)
2229                         p_eb = new_eb;
2230                 else if (raid_map[i] == BTRFS_RAID6_Q_STRIPE)
2231                         q_eb = new_eb;
2232         }
2233         if (q_eb) {
2234                 ebs[multi->num_stripes - 2] = p_eb;
2235                 ebs[multi->num_stripes - 1] = q_eb;
2236
2237                 for (i = 0; i < multi->num_stripes; i++)
2238                         pointers[i] = ebs[i]->data;
2239
2240                 raid6_gen_syndrome(multi->num_stripes, stripe_len, pointers);
2241         } else {
2242                 ebs[multi->num_stripes - 1] = p_eb;
2243                 for (i = 0; i < multi->num_stripes; i++)
2244                         pointers[i] = ebs[i]->data;
2245                 ret = raid5_gen_result(multi->num_stripes, stripe_len,
2246                                        multi->num_stripes - 1, pointers);
2247                 if (ret < 0)
2248                         goto out_free_split;
2249         }
2250
2251         for (i = 0; i < multi->num_stripes; i++) {
2252                 ret = write_extent_to_disk(ebs[i]);
2253                 if (ret < 0)
2254                         goto out_free_split;
2255         }
2256
2257 out_free_split:
2258         for (i = 0; i < multi->num_stripes; i++) {
2259                 if (ebs[i] != eb)
2260                         free(ebs[i]);
2261         }
2262 out:
2263         free(ebs);
2264         free(pointers);
2265
2266         return ret;
2267 }