fs/btrfs/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 <linux/sched.h>
  19 #include <linux/bio.h>
  20 #include <linux/slab.h>
  21 #include <linux/buffer_head.h>
  22 #include <linux/blkdev.h>
  23 #include <linux/random.h>
  24 #include <linux/iocontext.h>
  25 #include <linux/capability.h>
  26 #include <linux/ratelimit.h>
  27 #include <linux/kthread.h>
  28 #include <linux/raid/pq.h>
  29 #include <linux/semaphore.h>
  30 #include <asm/div64.h>
  31 #include "compat.h"
  32 #include "ctree.h"
  33 #include "extent_map.h"
  34 #include "disk-io.h"
  35 #include "transaction.h"
  36 #include "print-tree.h"
  37 #include "volumes.h"
  38 #include "raid56.h"
  39 #include "async-thread.h"
  40 #include "check-integrity.h"
  41 #include "rcu-string.h"
  42 #include "math.h"
  43 #include "dev-replace.h"
  44
  45 static int init_first_rw_device(struct btrfs_trans_handle *trans,
  46                                 struct btrfs_root *root,
  47                                 struct btrfs_device *device);
  48 static int btrfs_relocate_sys_chunks(struct btrfs_root *root);
  49 static void __btrfs_reset_dev_stats(struct btrfs_device *dev);
  50 static void btrfs_dev_stat_print_on_error(struct btrfs_device *dev);
  51 static void btrfs_dev_stat_print_on_load(struct btrfs_device *device);
  52
  53 static DEFINE_MUTEX(uuid_mutex);
  54 static LIST_HEAD(fs_uuids);
  55
  56 static void lock_chunks(struct btrfs_root *root)
  57 {
  58         mutex_lock(&root->fs_info->chunk_mutex);
  59 }
  60
  61 static void unlock_chunks(struct btrfs_root *root)
  62 {
  63         mutex_unlock(&root->fs_info->chunk_mutex);
  64 }
  65
  66 static void free_fs_devices(struct btrfs_fs_devices *fs_devices)
  67 {
  68         struct btrfs_device *device;
  69         WARN_ON(fs_devices->opened);
  70         while (!list_empty(&fs_devices->devices)) {
  71                 device = list_entry(fs_devices->devices.next,
  72                                     struct btrfs_device, dev_list);
  73                 list_del(&device->dev_list);
  74                 rcu_string_free(device->name);
  75                 kfree(device);
  76         }
  77         kfree(fs_devices);
  78 }
  79
  80 static void btrfs_kobject_uevent(struct block_device *bdev,
  81                                  enum kobject_action action)
  82 {
  83         int ret;
  84
  85         ret = kobject_uevent(&disk_to_dev(bdev->bd_disk)->kobj, action);
  86         if (ret)
  87                 pr_warn("Sending event '%d' to kobject: '%s' (%p): failed\n",
  88                         action,
  89                         kobject_name(&disk_to_dev(bdev->bd_disk)->kobj),
  90                         &disk_to_dev(bdev->bd_disk)->kobj);
  91 }
  92
  93 void btrfs_cleanup_fs_uuids(void)
  94 {
  95         struct btrfs_fs_devices *fs_devices;
  96
  97         while (!list_empty(&fs_uuids)) {
  98                 fs_devices = list_entry(fs_uuids.next,
  99                                         struct btrfs_fs_devices, list);
 100                 list_del(&fs_devices->list);
 101                 free_fs_devices(fs_devices);
 102         }
 103 }
 104
 105 static struct btrfs_device *__alloc_device(void)
 106 {
 107         struct btrfs_device *dev;
 108
 109         dev = kzalloc(sizeof(*dev), GFP_NOFS);
 110         if (!dev)
 111                 return ERR_PTR(-ENOMEM);
 112
 113         INIT_LIST_HEAD(&dev->dev_list);
 114         INIT_LIST_HEAD(&dev->dev_alloc_list);
 115
 116         spin_lock_init(&dev->io_lock);
 117
 118         spin_lock_init(&dev->reada_lock);
 119         atomic_set(&dev->reada_in_flight, 0);
 120         INIT_RADIX_TREE(&dev->reada_zones, GFP_NOFS & ~__GFP_WAIT);
 121         INIT_RADIX_TREE(&dev->reada_extents, GFP_NOFS & ~__GFP_WAIT);
 122
 123         return dev;
 124 }
 125
 126 static noinline struct btrfs_device *__find_device(struct list_head *head,
 127                                                    u64 devid, u8 *uuid)
 128 {
 129         struct btrfs_device *dev;
 130
 131         list_for_each_entry(dev, head, dev_list) {
 132                 if (dev->devid == devid &&
 133                     (!uuid || !memcmp(dev->uuid, uuid, BTRFS_UUID_SIZE))) {
 134                         return dev;
 135                 }
 136         }
 137         return NULL;
 138 }
 139
 140 static noinline struct btrfs_fs_devices *find_fsid(u8 *fsid)
 141 {
 142         struct btrfs_fs_devices *fs_devices;
 143
 144         list_for_each_entry(fs_devices, &fs_uuids, list) {
 145                 if (memcmp(fsid, fs_devices->fsid, BTRFS_FSID_SIZE) == 0)
 146                         return fs_devices;
 147         }
 148         return NULL;
 149 }
 150
 151 static int
 152 btrfs_get_bdev_and_sb(const char *device_path, fmode_t flags, void *holder,
 153                       int flush, struct block_device **bdev,
 154                       struct buffer_head **bh)
 155 {
 156         int ret;
 157
 158         *bdev = blkdev_get_by_path(device_path, flags, holder);
 159
 160         if (IS_ERR(*bdev)) {
 161                 ret = PTR_ERR(*bdev);
 162                 printk(KERN_INFO "btrfs: open %s failed\n", device_path);
 163                 goto error;
 164         }
 165
 166         if (flush)
 167                 filemap_write_and_wait((*bdev)->bd_inode->i_mapping);
 168         ret = set_blocksize(*bdev, 4096);
 169         if (ret) {
 170                 blkdev_put(*bdev, flags);
 171                 goto error;
 172         }
 173         invalidate_bdev(*bdev);
 174         *bh = btrfs_read_dev_super(*bdev);
 175         if (!*bh) {
 176                 ret = -EINVAL;
 177                 blkdev_put(*bdev, flags);
 178                 goto error;
 179         }
 180
 181         return 0;
 182
 183 error:
 184         *bdev = NULL;
 185         *bh = NULL;
 186         return ret;
 187 }
 188
 189 static void requeue_list(struct btrfs_pending_bios *pending_bios,
 190                         struct bio *head, struct bio *tail)
 191 {
 192
 193         struct bio *old_head;
 194
 195         old_head = pending_bios->head;
 196         pending_bios->head = head;
 197         if (pending_bios->tail)
 198                 tail->bi_next = old_head;
 199         else
 200                 pending_bios->tail = tail;
 201 }
 202
 203 /*
 204  * we try to collect pending bios for a device so we don't get a large
 205  * number of procs sending bios down to the same device.  This greatly
 206  * improves the schedulers ability to collect and merge the bios.
 207  *
 208  * But, it also turns into a long list of bios to process and that is sure
 209  * to eventually make the worker thread block.  The solution here is to
 210  * make some progress and then put this work struct back at the end of
 211  * the list if the block device is congested.  This way, multiple devices
 212  * can make progress from a single worker thread.
 213  */
 214 static noinline void run_scheduled_bios(struct btrfs_device *device)
 215 {
 216         struct bio *pending;
 217         struct backing_dev_info *bdi;
 218         struct btrfs_fs_info *fs_info;
 219         struct btrfs_pending_bios *pending_bios;
 220         struct bio *tail;
 221         struct bio *cur;
 222         int again = 0;
 223         unsigned long num_run;
 224         unsigned long batch_run = 0;
 225         unsigned long limit;
 226         unsigned long last_waited = 0;
 227         int force_reg = 0;
 228         int sync_pending = 0;
 229         struct blk_plug plug;
 230
 231         /*
 232          * this function runs all the bios we've collected for
 233          * a particular device.  We don't want to wander off to
 234          * another device without first sending all of these down.
 235          * So, setup a plug here and finish it off before we return
 236          */
 237         blk_start_plug(&plug);
 238
 239         bdi = blk_get_backing_dev_info(device->bdev);
 240         fs_info = device->dev_root->fs_info;
 241         limit = btrfs_async_submit_limit(fs_info);
 242         limit = limit * 2 / 3;
 243
 244 loop:
 245         spin_lock(&device->io_lock);
 246
 247 loop_lock:
 248         num_run = 0;
 249
 250         /* take all the bios off the list at once and process them
 251          * later on (without the lock held).  But, remember the
 252          * tail and other pointers so the bios can be properly reinserted
 253          * into the list if we hit congestion
 254          */
 255         if (!force_reg && device->pending_sync_bios.head) {
 256                 pending_bios = &device->pending_sync_bios;
 257                 force_reg = 1;
 258         } else {
 259                 pending_bios = &device->pending_bios;
 260                 force_reg = 0;
 261         }
 262
 263         pending = pending_bios->head;
 264         tail = pending_bios->tail;
 265         WARN_ON(pending && !tail);
 266
 267         /*
 268          * if pending was null this time around, no bios need processing
 269          * at all and we can stop.  Otherwise it'll loop back up again
 270          * and do an additional check so no bios are missed.
 271          *
 272          * device->running_pending is used to synchronize with the
 273          * schedule_bio code.
 274          */
 275         if (device->pending_sync_bios.head == NULL &&
 276             device->pending_bios.head == NULL) {
 277                 again = 0;
 278                 device->running_pending = 0;
 279         } else {
 280                 again = 1;
 281                 device->running_pending = 1;
 282         }
 283
 284         pending_bios->head = NULL;
 285         pending_bios->tail = NULL;
 286
 287         spin_unlock(&device->io_lock);
 288
 289         while (pending) {
 290
 291                 rmb();
 292                 /* we want to work on both lists, but do more bios on the
 293                  * sync list than the regular list
 294                  */
 295                 if ((num_run > 32 &&
 296                     pending_bios != &device->pending_sync_bios &&
 297                     device->pending_sync_bios.head) ||
 298                    (num_run > 64 && pending_bios == &device->pending_sync_bios &&
 299                     device->pending_bios.head)) {
 300                         spin_lock(&device->io_lock);
 301                         requeue_list(pending_bios, pending, tail);
 302                         goto loop_lock;
 303                 }
 304
 305                 cur = pending;
 306                 pending = pending->bi_next;
 307                 cur->bi_next = NULL;
 308
 309                 if (atomic_dec_return(&fs_info->nr_async_bios) < limit &&
 310                     waitqueue_active(&fs_info->async_submit_wait))
 311                         wake_up(&fs_info->async_submit_wait);
 312
 313                 BUG_ON(atomic_read(&cur->bi_cnt) == 0);
 314
 315                 /*
 316                  * if we're doing the sync list, record that our
 317                  * plug has some sync requests on it
 318                  *
 319                  * If we're doing the regular list and there are
 320                  * sync requests sitting around, unplug before
 321                  * we add more
 322                  */
 323                 if (pending_bios == &device->pending_sync_bios) {
 324                         sync_pending = 1;
 325                 } else if (sync_pending) {
 326                         blk_finish_plug(&plug);
 327                         blk_start_plug(&plug);
 328                         sync_pending = 0;
 329                 }
 330
 331                 btrfsic_submit_bio(cur->bi_rw, cur);
 332                 num_run++;
 333                 batch_run++;
 334                 if (need_resched())
 335                         cond_resched();
 336
 337                 /*
 338                  * we made progress, there is more work to do and the bdi
 339                  * is now congested.  Back off and let other work structs
 340                  * run instead
 341                  */
 342                 if (pending && bdi_write_congested(bdi) && batch_run > 8 &&
 343                     fs_info->fs_devices->open_devices > 1) {
 344                         struct io_context *ioc;
 345
 346                         ioc = current->io_context;
 347
 348                         /*
 349                          * the main goal here is that we don't want to
 350                          * block if we're going to be able to submit
 351                          * more requests without blocking.
 352                          *
 353                          * This code does two great things, it pokes into
 354                          * the elevator code from a filesystem _and_
 355                          * it makes assumptions about how batching works.
 356                          */
 357                         if (ioc && ioc->nr_batch_requests > 0 &&
 358                             time_before(jiffies, ioc->last_waited + HZ/50UL) &&
 359                             (last_waited == 0 ||
 360                              ioc->last_waited == last_waited)) {
 361                                 /*
 362                                  * we want to go through our batch of
 363                                  * requests and stop.  So, we copy out
 364                                  * the ioc->last_waited time and test
 365                                  * against it before looping
 366                                  */
 367                                 last_waited = ioc->last_waited;
 368                                 if (need_resched())
 369                                         cond_resched();
 370                                 continue;
 371                         }
 372                         spin_lock(&device->io_lock);
 373                         requeue_list(pending_bios, pending, tail);
 374                         device->running_pending = 1;
 375
 376                         spin_unlock(&device->io_lock);
 377                         btrfs_requeue_work(&device->work);
 378                         goto done;
 379                 }
 380                 /* unplug every 64 requests just for good measure */
 381                 if (batch_run % 64 == 0) {
 382                         blk_finish_plug(&plug);
 383                         blk_start_plug(&plug);
 384                         sync_pending = 0;
 385                 }
 386         }
 387
 388         cond_resched();
 389         if (again)
 390                 goto loop;
 391
 392         spin_lock(&device->io_lock);
 393         if (device->pending_bios.head || device->pending_sync_bios.head)
 394                 goto loop_lock;
 395         spin_unlock(&device->io_lock);
 396
 397 done:
 398         blk_finish_plug(&plug);
 399 }
 400
 401 static void pending_bios_fn(struct btrfs_work *work)
 402 {
 403         struct btrfs_device *device;
 404
 405         device = container_of(work, struct btrfs_device, work);
 406         run_scheduled_bios(device);
 407 }
 408
 409 static noinline int device_list_add(const char *path,
 410                            struct btrfs_super_block *disk_super,
 411                            u64 devid, struct btrfs_fs_devices **fs_devices_ret)
 412 {
 413         struct btrfs_device *device;
 414         struct btrfs_fs_devices *fs_devices;
 415         struct rcu_string *name;
 416         u64 found_transid = btrfs_super_generation(disk_super);
 417
 418         fs_devices = find_fsid(disk_super->fsid);
 419         if (!fs_devices) {
 420                 fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
 421                 if (!fs_devices)
 422                         return -ENOMEM;
 423                 INIT_LIST_HEAD(&fs_devices->devices);
 424                 INIT_LIST_HEAD(&fs_devices->alloc_list);
 425                 list_add(&fs_devices->list, &fs_uuids);
 426                 memcpy(fs_devices->fsid, disk_super->fsid, BTRFS_FSID_SIZE);
 427                 fs_devices->latest_devid = devid;
 428                 fs_devices->latest_trans = found_transid;
 429                 mutex_init(&fs_devices->device_list_mutex);
 430                 device = NULL;
 431         } else {
 432                 device = __find_device(&fs_devices->devices, devid,
 433                                        disk_super->dev_item.uuid);
 434         }
 435         if (!device) {
 436                 if (fs_devices->opened)
 437                         return -EBUSY;
 438
 439                 device = btrfs_alloc_device(NULL, &devid,
 440                                             disk_super->dev_item.uuid);
 441                 if (IS_ERR(device)) {
 442                         /* we can safely leave the fs_devices entry around */
 443                         return PTR_ERR(device);
 444                 }
 445
 446                 name = rcu_string_strdup(path, GFP_NOFS);
 447                 if (!name) {
 448                         kfree(device);
 449                         return -ENOMEM;
 450                 }
 451                 rcu_assign_pointer(device->name, name);
 452
 453                 mutex_lock(&fs_devices->device_list_mutex);
 454                 list_add_rcu(&device->dev_list, &fs_devices->devices);
 455                 mutex_unlock(&fs_devices->device_list_mutex);
 456
 457                 device->fs_devices = fs_devices;
 458                 fs_devices->num_devices++;
 459         } else if (!device->name || strcmp(device->name->str, path)) {
 460                 name = rcu_string_strdup(path, GFP_NOFS);
 461                 if (!name)
 462                         return -ENOMEM;
 463                 rcu_string_free(device->name);
 464                 rcu_assign_pointer(device->name, name);
 465                 if (device->missing) {
 466                         fs_devices->missing_devices--;
 467                         device->missing = 0;
 468                 }
 469         }
 470
 471         if (found_transid > fs_devices->latest_trans) {
 472                 fs_devices->latest_devid = devid;
 473                 fs_devices->latest_trans = found_transid;
 474         }
 475         *fs_devices_ret = fs_devices;
 476         return 0;
 477 }
 478
 479 static struct btrfs_fs_devices *clone_fs_devices(struct btrfs_fs_devices *orig)
 480 {
 481         struct btrfs_fs_devices *fs_devices;
 482         struct btrfs_device *device;
 483         struct btrfs_device *orig_dev;
 484
 485         fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
 486         if (!fs_devices)
 487                 return ERR_PTR(-ENOMEM);
 488
 489         INIT_LIST_HEAD(&fs_devices->devices);
 490         INIT_LIST_HEAD(&fs_devices->alloc_list);
 491         INIT_LIST_HEAD(&fs_devices->list);
 492         mutex_init(&fs_devices->device_list_mutex);
 493         fs_devices->latest_devid = orig->latest_devid;
 494         fs_devices->latest_trans = orig->latest_trans;
 495         fs_devices->total_devices = orig->total_devices;
 496         memcpy(fs_devices->fsid, orig->fsid, sizeof(fs_devices->fsid));
 497
 498         /* We have held the volume lock, it is safe to get the devices. */
 499         list_for_each_entry(orig_dev, &orig->devices, dev_list) {
 500                 struct rcu_string *name;
 501
 502                 device = btrfs_alloc_device(NULL, &orig_dev->devid,
 503                                             orig_dev->uuid);
 504                 if (IS_ERR(device))
 505                         goto error;
 506
 507                 /*
 508                  * This is ok to do without rcu read locked because we hold the
 509                  * uuid mutex so nothing we touch in here is going to disappear.
 510                  */
 511                 name = rcu_string_strdup(orig_dev->name->str, GFP_NOFS);
 512                 if (!name) {
 513                         kfree(device);
 514                         goto error;
 515                 }
 516                 rcu_assign_pointer(device->name, name);
 517
 518                 list_add(&device->dev_list, &fs_devices->devices);
 519                 device->fs_devices = fs_devices;
 520                 fs_devices->num_devices++;
 521         }
 522         return fs_devices;
 523 error:
 524         free_fs_devices(fs_devices);
 525         return ERR_PTR(-ENOMEM);
 526 }
 527
 528 void btrfs_close_extra_devices(struct btrfs_fs_info *fs_info,
 529                                struct btrfs_fs_devices *fs_devices, int step)
 530 {
 531         struct btrfs_device *device, *next;
 532
 533         struct block_device *latest_bdev = NULL;
 534         u64 latest_devid = 0;
 535         u64 latest_transid = 0;
 536
 537         mutex_lock(&uuid_mutex);
 538 again:
 539         /* This is the initialized path, it is safe to release the devices. */
 540         list_for_each_entry_safe(device, next, &fs_devices->devices, dev_list) {
 541                 if (device->in_fs_metadata) {
 542                         if (!device->is_tgtdev_for_dev_replace &&
 543                             (!latest_transid ||
 544                              device->generation > latest_transid)) {
 545                                 latest_devid = device->devid;
 546                                 latest_transid = device->generation;
 547                                 latest_bdev = device->bdev;
 548                         }
 549                         continue;
 550                 }
 551
 552                 if (device->devid == BTRFS_DEV_REPLACE_DEVID) {
 553                         /*
 554                          * In the first step, keep the device which has
 555                          * the correct fsid and the devid that is used
 556                          * for the dev_replace procedure.
 557                          * In the second step, the dev_replace state is
 558                          * read from the device tree and it is known
 559                          * whether the procedure is really active or
 560                          * not, which means whether this device is
 561                          * used or whether it should be removed.
 562                          */
 563                         if (step == 0 || device->is_tgtdev_for_dev_replace) {
 564                                 continue;
 565                         }
 566                 }
 567                 if (device->bdev) {
 568                         blkdev_put(device->bdev, device->mode);
 569                         device->bdev = NULL;
 570                         fs_devices->open_devices--;
 571                 }
 572                 if (device->writeable) {
 573                         list_del_init(&device->dev_alloc_list);
 574                         device->writeable = 0;
 575                         if (!device->is_tgtdev_for_dev_replace)
 576                                 fs_devices->rw_devices--;
 577                 }
 578                 list_del_init(&device->dev_list);
 579                 fs_devices->num_devices--;
 580                 rcu_string_free(device->name);
 581                 kfree(device);
 582         }
 583
 584         if (fs_devices->seed) {
 585                 fs_devices = fs_devices->seed;
 586                 goto again;
 587         }
 588
 589         fs_devices->latest_bdev = latest_bdev;
 590         fs_devices->latest_devid = latest_devid;
 591         fs_devices->latest_trans = latest_transid;
 592
 593         mutex_unlock(&uuid_mutex);
 594 }
 595
 596 static void __free_device(struct work_struct *work)
 597 {
 598         struct btrfs_device *device;
 599
 600         device = container_of(work, struct btrfs_device, rcu_work);
 601
 602         if (device->bdev)
 603                 blkdev_put(device->bdev, device->mode);
 604
 605         rcu_string_free(device->name);
 606         kfree(device);
 607 }
 608
 609 static void free_device(struct rcu_head *head)
 610 {
 611         struct btrfs_device *device;
 612
 613         device = container_of(head, struct btrfs_device, rcu);
 614
 615         INIT_WORK(&device->rcu_work, __free_device);
 616         schedule_work(&device->rcu_work);
 617 }
 618
 619 static int __btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 620 {
 621         struct btrfs_device *device;
 622
 623         if (--fs_devices->opened > 0)
 624                 return 0;
 625
 626         mutex_lock(&fs_devices->device_list_mutex);
 627         list_for_each_entry(device, &fs_devices->devices, dev_list) {
 628                 struct btrfs_device *new_device;
 629                 struct rcu_string *name;
 630
 631                 if (device->bdev)
 632                         fs_devices->open_devices--;
 633
 634                 if (device->writeable && !device->is_tgtdev_for_dev_replace) {
 635                         list_del_init(&device->dev_alloc_list);
 636                         fs_devices->rw_devices--;
 637                 }
 638
 639                 if (device->can_discard)
 640                         fs_devices->num_can_discard--;
 641
 642                 new_device = kmalloc(sizeof(*new_device), GFP_NOFS);
 643                 BUG_ON(!new_device); /* -ENOMEM */
 644                 memcpy(new_device, device, sizeof(*new_device));
 645
 646                 /* Safe because we are under uuid_mutex */
 647                 if (device->name) {
 648                         name = rcu_string_strdup(device->name->str, GFP_NOFS);
 649                         BUG_ON(device->name && !name); /* -ENOMEM */
 650                         rcu_assign_pointer(new_device->name, name);
 651                 }
 652                 new_device->bdev = NULL;
 653                 new_device->writeable = 0;
 654                 new_device->in_fs_metadata = 0;
 655                 new_device->can_discard = 0;
 656                 spin_lock_init(&new_device->io_lock);
 657                 list_replace_rcu(&device->dev_list, &new_device->dev_list);
 658
 659                 call_rcu(&device->rcu, free_device);
 660         }
 661         mutex_unlock(&fs_devices->device_list_mutex);
 662
 663         WARN_ON(fs_devices->open_devices);
 664         WARN_ON(fs_devices->rw_devices);
 665         fs_devices->opened = 0;
 666         fs_devices->seeding = 0;
 667
 668         return 0;
 669 }
 670
 671 int btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 672 {
 673         struct btrfs_fs_devices *seed_devices = NULL;
 674         int ret;
 675
 676         mutex_lock(&uuid_mutex);
 677         ret = __btrfs_close_devices(fs_devices);
 678         if (!fs_devices->opened) {
 679                 seed_devices = fs_devices->seed;
 680                 fs_devices->seed = NULL;
 681         }
 682         mutex_unlock(&uuid_mutex);
 683
 684         while (seed_devices) {
 685                 fs_devices = seed_devices;
 686                 seed_devices = fs_devices->seed;
 687                 __btrfs_close_devices(fs_devices);
 688                 free_fs_devices(fs_devices);
 689         }
 690         /*
 691          * Wait for rcu kworkers under __btrfs_close_devices
 692          * to finish all blkdev_puts so device is really
 693          * free when umount is done.
 694          */
 695         rcu_barrier();
 696         return ret;
 697 }
 698
 699 static int __btrfs_open_devices(struct btrfs_fs_devices *fs_devices,
 700                                 fmode_t flags, void *holder)
 701 {
 702         struct request_queue *q;
 703         struct block_device *bdev;
 704         struct list_head *head = &fs_devices->devices;
 705         struct btrfs_device *device;
 706         struct block_device *latest_bdev = NULL;
 707         struct buffer_head *bh;
 708         struct btrfs_super_block *disk_super;
 709         u64 latest_devid = 0;
 710         u64 latest_transid = 0;
 711         u64 devid;
 712         int seeding = 1;
 713         int ret = 0;
 714
 715         flags |= FMODE_EXCL;
 716
 717         list_for_each_entry(device, head, dev_list) {
 718                 if (device->bdev)
 719                         continue;
 720                 if (!device->name)
 721                         continue;
 722
 723                 /* Just open everything we can; ignore failures here */
 724                 if (btrfs_get_bdev_and_sb(device->name->str, flags, holder, 1,
 725                                             &bdev, &bh))
 726                         continue;
 727
 728                 disk_super = (struct btrfs_super_block *)bh->b_data;
 729                 devid = btrfs_stack_device_id(&disk_super->dev_item);
 730                 if (devid != device->devid)
 731                         goto error_brelse;
 732
 733                 if (memcmp(device->uuid, disk_super->dev_item.uuid,
 734                            BTRFS_UUID_SIZE))
 735                         goto error_brelse;
 736
 737                 device->generation = btrfs_super_generation(disk_super);
 738                 if (!latest_transid || device->generation > latest_transid) {
 739                         latest_devid = devid;
 740                         latest_transid = device->generation;
 741                         latest_bdev = bdev;
 742                 }
 743
 744                 if (btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_SEEDING) {
 745                         device->writeable = 0;
 746                 } else {
 747                         device->writeable = !bdev_read_only(bdev);
 748                         seeding = 0;
 749                 }
 750
 751                 q = bdev_get_queue(bdev);
 752                 if (blk_queue_discard(q)) {
 753                         device->can_discard = 1;
 754                         fs_devices->num_can_discard++;
 755                 }
 756
 757                 device->bdev = bdev;
 758                 device->in_fs_metadata = 0;
 759                 device->mode = flags;
 760
 761                 if (!blk_queue_nonrot(bdev_get_queue(bdev)))
 762                         fs_devices->rotating = 1;
 763
 764                 fs_devices->open_devices++;
 765                 if (device->writeable && !device->is_tgtdev_for_dev_replace) {
 766                         fs_devices->rw_devices++;
 767                         list_add(&device->dev_alloc_list,
 768                                  &fs_devices->alloc_list);
 769                 }
 770                 brelse(bh);
 771                 continue;
 772
 773 error_brelse:
 774                 brelse(bh);
 775                 blkdev_put(bdev, flags);
 776                 continue;
 777         }
 778         if (fs_devices->open_devices == 0) {
 779                 ret = -EINVAL;
 780                 goto out;
 781         }
 782         fs_devices->seeding = seeding;
 783         fs_devices->opened = 1;
 784         fs_devices->latest_bdev = latest_bdev;
 785         fs_devices->latest_devid = latest_devid;
 786         fs_devices->latest_trans = latest_transid;
 787         fs_devices->total_rw_bytes = 0;
 788 out:
 789         return ret;
 790 }
 791
 792 int btrfs_open_devices(struct btrfs_fs_devices *fs_devices,
 793                        fmode_t flags, void *holder)
 794 {
 795         int ret;
 796
 797         mutex_lock(&uuid_mutex);
 798         if (fs_devices->opened) {
 799                 fs_devices->opened++;
 800                 ret = 0;
 801         } else {
 802                 ret = __btrfs_open_devices(fs_devices, flags, holder);
 803         }
 804         mutex_unlock(&uuid_mutex);
 805         return ret;
 806 }
 807
 808 /*
 809  * Look for a btrfs signature on a device. This may be called out of the mount path
 810  * and we are not allowed to call set_blocksize during the scan. The superblock
 811  * is read via pagecache
 812  */
 813 int btrfs_scan_one_device(const char *path, fmode_t flags, void *holder,
 814                           struct btrfs_fs_devices **fs_devices_ret)
 815 {
 816         struct btrfs_super_block *disk_super;
 817         struct block_device *bdev;
 818         struct page *page;
 819         void *p;
 820         int ret = -EINVAL;
 821         u64 devid;
 822         u64 transid;
 823         u64 total_devices;
 824         u64 bytenr;
 825         pgoff_t index;
 826
 827         /*
 828          * we would like to check all the supers, but that would make
 829          * a btrfs mount succeed after a mkfs from a different FS.
 830          * So, we need to add a special mount option to scan for
 831          * later supers, using BTRFS_SUPER_MIRROR_MAX instead
 832          */
 833         bytenr = btrfs_sb_offset(0);
 834         flags |= FMODE_EXCL;
 835         mutex_lock(&uuid_mutex);
 836
 837         bdev = blkdev_get_by_path(path, flags, holder);
 838
 839         if (IS_ERR(bdev)) {
 840                 ret = PTR_ERR(bdev);
 841                 goto error;
 842         }
 843
 844         /* make sure our super fits in the device */
 845         if (bytenr + PAGE_CACHE_SIZE >= i_size_read(bdev->bd_inode))
 846                 goto error_bdev_put;
 847
 848         /* make sure our super fits in the page */
 849         if (sizeof(*disk_super) > PAGE_CACHE_SIZE)
 850                 goto error_bdev_put;
 851
 852         /* make sure our super doesn't straddle pages on disk */
 853         index = bytenr >> PAGE_CACHE_SHIFT;
 854         if ((bytenr + sizeof(*disk_super) - 1) >> PAGE_CACHE_SHIFT != index)
 855                 goto error_bdev_put;
 856
 857         /* pull in the page with our super */
 858         page = read_cache_page_gfp(bdev->bd_inode->i_mapping,
 859                                    index, GFP_NOFS);
 860
 861         if (IS_ERR_OR_NULL(page))
 862                 goto error_bdev_put;
 863
 864         p = kmap(page);
 865
 866         /* align our pointer to the offset of the super block */
 867         disk_super = p + (bytenr & ~PAGE_CACHE_MASK);
 868
 869         if (btrfs_super_bytenr(disk_super) != bytenr ||
 870             btrfs_super_magic(disk_super) != BTRFS_MAGIC)
 871                 goto error_unmap;
 872
 873         devid = btrfs_stack_device_id(&disk_super->dev_item);
 874         transid = btrfs_super_generation(disk_super);
 875         total_devices = btrfs_super_num_devices(disk_super);
 876
 877         if (disk_super->label[0]) {
 878                 if (disk_super->label[BTRFS_LABEL_SIZE - 1])
 879                         disk_super->label[BTRFS_LABEL_SIZE - 1] = '\0';
 880                 printk(KERN_INFO "device label %s ", disk_super->label);
 881         } else {
 882                 printk(KERN_INFO "device fsid %pU ", disk_super->fsid);
 883         }
 884
 885         printk(KERN_CONT "devid %llu transid %llu %s\n",
 886                (unsigned long long)devid, (unsigned long long)transid, path);
 887
 888         ret = device_list_add(path, disk_super, devid, fs_devices_ret);
 889         if (!ret && fs_devices_ret)
 890                 (*fs_devices_ret)->total_devices = total_devices;
 891
 892 error_unmap:
 893         kunmap(page);
 894         page_cache_release(page);
 895
 896 error_bdev_put:
 897         blkdev_put(bdev, flags);
 898 error:
 899         mutex_unlock(&uuid_mutex);
 900         return ret;
 901 }
 902
 903 /* helper to account the used device space in the range */
 904 int btrfs_account_dev_extents_size(struct btrfs_device *device, u64 start,
 905                                    u64 end, u64 *length)
 906 {
 907         struct btrfs_key key;
 908         struct btrfs_root *root = device->dev_root;
 909         struct btrfs_dev_extent *dev_extent;
 910         struct btrfs_path *path;
 911         u64 extent_end;
 912         int ret;
 913         int slot;
 914         struct extent_buffer *l;
 915
 916         *length = 0;
 917
 918         if (start >= device->total_bytes || device->is_tgtdev_for_dev_replace)
 919                 return 0;
 920
 921         path = btrfs_alloc_path();
 922         if (!path)
 923                 return -ENOMEM;
 924         path->reada = 2;
 925
 926         key.objectid = device->devid;
 927         key.offset = start;
 928         key.type = BTRFS_DEV_EXTENT_KEY;
 929
 930         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 931         if (ret < 0)
 932                 goto out;
 933         if (ret > 0) {
 934                 ret = btrfs_previous_item(root, path, key.objectid, key.type);
 935                 if (ret < 0)
 936                         goto out;
 937         }
 938
 939         while (1) {
 940                 l = path->nodes[0];
 941                 slot = path->slots[0];
 942                 if (slot >= btrfs_header_nritems(l)) {
 943                         ret = btrfs_next_leaf(root, path);
 944                         if (ret == 0)
 945                                 continue;
 946                         if (ret < 0)
 947                                 goto out;
 948
 949                         break;
 950                 }
 951                 btrfs_item_key_to_cpu(l, &key, slot);
 952
 953                 if (key.objectid < device->devid)
 954                         goto next;
 955
 956                 if (key.objectid > device->devid)
 957                         break;
 958
 959                 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
 960                         goto next;
 961
 962                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 963                 extent_end = key.offset + btrfs_dev_extent_length(l,
 964                                                                   dev_extent);
 965                 if (key.offset <= start && extent_end > end) {
 966                         *length = end - start + 1;
 967                         break;
 968                 } else if (key.offset <= start && extent_end > start)
 969                         *length += extent_end - start;
 970                 else if (key.offset > start && extent_end <= end)
 971                         *length += extent_end - key.offset;
 972                 else if (key.offset > start && key.offset <= end) {
 973                         *length += end - key.offset + 1;
 974                         break;
 975                 } else if (key.offset > end)
 976                         break;
 977
 978 next:
 979                 path->slots[0]++;
 980         }
 981         ret = 0;
 982 out:
 983         btrfs_free_path(path);
 984         return ret;
 985 }
 986
 987 static int contains_pending_extent(struct btrfs_trans_handle *trans,
 988                                    struct btrfs_device *device,
 989                                    u64 *start, u64 len)
 990 {
 991         struct extent_map *em;
 992         int ret = 0;
 993
 994         list_for_each_entry(em, &trans->transaction->pending_chunks, list) {
 995                 struct map_lookup *map;
 996                 int i;
 997
 998                 map = (struct map_lookup *)em->bdev;
 999                 for (i = 0; i < map->num_stripes; i++) {
1000                         if (map->stripes[i].dev != device)
1001                                 continue;
1002                         if (map->stripes[i].physical >= *start + len ||
1003                             map->stripes[i].physical + em->orig_block_len <=
1004                             *start)
1005                                 continue;
1006                         *start = map->stripes[i].physical +
1007                                 em->orig_block_len;
1008                         ret = 1;
1009                 }
1010         }
1011
1012         return ret;
1013 }
1014
1015
1016 /*
1017  * find_free_dev_extent - find free space in the specified device
1018  * @device:     the device which we search the free space in
1019  * @num_bytes:  the size of the free space that we need
1020  * @start:      store the start of the free space.
1021  * @len:        the size of the free space. that we find, or the size of the max
1022  *              free space if we don't find suitable free space
1023  *
1024  * this uses a pretty simple search, the expectation is that it is
1025  * called very infrequently and that a given device has a small number
1026  * of extents
1027  *
1028  * @start is used to store the start of the free space if we find. But if we
1029  * don't find suitable free space, it will be used to store the start position
1030  * of the max free space.
1031  *
1032  * @len is used to store the size of the free space that we find.
1033  * But if we don't find suitable free space, it is used to store the size of
1034  * the max free space.
1035  */
1036 int find_free_dev_extent(struct btrfs_trans_handle *trans,
1037                          struct btrfs_device *device, u64 num_bytes,
1038                          u64 *start, u64 *len)
1039 {
1040         struct btrfs_key key;
1041         struct btrfs_root *root = device->dev_root;
1042         struct btrfs_dev_extent *dev_extent;
1043         struct btrfs_path *path;
1044         u64 hole_size;
1045         u64 max_hole_start;
1046         u64 max_hole_size;
1047         u64 extent_end;
1048         u64 search_start;
1049         u64 search_end = device->total_bytes;
1050         int ret;
1051         int slot;
1052         struct extent_buffer *l;
1053
1054         /* FIXME use last free of some kind */
1055
1056         /* we don't want to overwrite the superblock on the drive,
1057          * so we make sure to start at an offset of at least 1MB
1058          */
1059         search_start = max(root->fs_info->alloc_start, 1024ull * 1024);
1060
1061         path = btrfs_alloc_path();
1062         if (!path)
1063                 return -ENOMEM;
1064 again:
1065         max_hole_start = search_start;
1066         max_hole_size = 0;
1067         hole_size = 0;
1068
1069         if (search_start >= search_end || device->is_tgtdev_for_dev_replace) {
1070                 ret = -ENOSPC;
1071                 goto out;
1072         }
1073
1074         path->reada = 2;
1075         path->search_commit_root = 1;
1076         path->skip_locking = 1;
1077
1078         key.objectid = device->devid;
1079         key.offset = search_start;
1080         key.type = BTRFS_DEV_EXTENT_KEY;
1081
1082         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1083         if (ret < 0)
1084                 goto out;
1085         if (ret > 0) {
1086                 ret = btrfs_previous_item(root, path, key.objectid, key.type);
1087                 if (ret < 0)
1088                         goto out;
1089         }
1090
1091         while (1) {
1092                 l = path->nodes[0];
1093                 slot = path->slots[0];
1094                 if (slot >= btrfs_header_nritems(l)) {
1095                         ret = btrfs_next_leaf(root, path);
1096                         if (ret == 0)
1097                                 continue;
1098                         if (ret < 0)
1099                                 goto out;
1100
1101                         break;
1102                 }
1103                 btrfs_item_key_to_cpu(l, &key, slot);
1104
1105                 if (key.objectid < device->devid)
1106                         goto next;
1107
1108                 if (key.objectid > device->devid)
1109                         break;
1110
1111                 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
1112                         goto next;
1113
1114                 if (key.offset > search_start) {
1115                         hole_size = key.offset - search_start;
1116
1117                         /*
1118                          * Have to check before we set max_hole_start, otherwise
1119                          * we could end up sending back this offset anyway.
1120                          */
1121                         if (contains_pending_extent(trans, device,
1122                                                     &search_start,
1123                                                     hole_size))
1124                                 hole_size = 0;
1125
1126                         if (hole_size > max_hole_size) {
1127                                 max_hole_start = search_start;
1128                                 max_hole_size = hole_size;
1129                         }
1130
1131                         /*
1132                          * If this free space is greater than which we need,
1133                          * it must be the max free space that we have found
1134                          * until now, so max_hole_start must point to the start
1135                          * of this free space and the length of this free space
1136                          * is stored in max_hole_size. Thus, we return
1137                          * max_hole_start and max_hole_size and go back to the
1138                          * caller.
1139                          */
1140                         if (hole_size >= num_bytes) {
1141                                 ret = 0;
1142                                 goto out;
1143                         }
1144                 }
1145
1146                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
1147                 extent_end = key.offset + btrfs_dev_extent_length(l,
1148                                                                   dev_extent);
1149                 if (extent_end > search_start)
1150                         search_start = extent_end;
1151 next:
1152                 path->slots[0]++;
1153                 cond_resched();
1154         }
1155
1156         /*
1157          * At this point, search_start should be the end of
1158          * allocated dev extents, and when shrinking the device,
1159          * search_end may be smaller than search_start.
1160          */
1161         if (search_end > search_start)
1162                 hole_size = search_end - search_start;
1163
1164         if (hole_size > max_hole_size) {
1165                 max_hole_start = search_start;
1166                 max_hole_size = hole_size;
1167         }
1168
1169         if (contains_pending_extent(trans, device, &search_start, hole_size)) {
1170                 btrfs_release_path(path);
1171                 goto again;
1172         }
1173
1174         /* See above. */
1175         if (hole_size < num_bytes)
1176                 ret = -ENOSPC;
1177         else
1178                 ret = 0;
1179
1180 out:
1181         btrfs_free_path(path);
1182         *start = max_hole_start;
1183         if (len)
1184                 *len = max_hole_size;
1185         return ret;
1186 }
1187
1188 static int btrfs_free_dev_extent(struct btrfs_trans_handle *trans,
1189                           struct btrfs_device *device,
1190                           u64 start)
1191 {
1192         int ret;
1193         struct btrfs_path *path;
1194         struct btrfs_root *root = device->dev_root;
1195         struct btrfs_key key;
1196         struct btrfs_key found_key;
1197         struct extent_buffer *leaf = NULL;
1198         struct btrfs_dev_extent *extent = NULL;
1199
1200         path = btrfs_alloc_path();
1201         if (!path)
1202                 return -ENOMEM;
1203
1204         key.objectid = device->devid;
1205         key.offset = start;
1206         key.type = BTRFS_DEV_EXTENT_KEY;
1207 again:
1208         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1209         if (ret > 0) {
1210                 ret = btrfs_previous_item(root, path, key.objectid,
1211                                           BTRFS_DEV_EXTENT_KEY);
1212                 if (ret)
1213                         goto out;
1214                 leaf = path->nodes[0];
1215                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1216                 extent = btrfs_item_ptr(leaf, path->slots[0],
1217                                         struct btrfs_dev_extent);
1218                 BUG_ON(found_key.offset > start || found_key.offset +
1219                        btrfs_dev_extent_length(leaf, extent) < start);
1220                 key = found_key;
1221                 btrfs_release_path(path);
1222                 goto again;
1223         } else if (ret == 0) {
1224                 leaf = path->nodes[0];
1225                 extent = btrfs_item_ptr(leaf, path->slots[0],
1226                                         struct btrfs_dev_extent);
1227         } else {
1228                 btrfs_error(root->fs_info, ret, "Slot search failed");
1229                 goto out;
1230         }
1231
1232         if (device->bytes_used > 0) {
1233                 u64 len = btrfs_dev_extent_length(leaf, extent);
1234                 device->bytes_used -= len;
1235                 spin_lock(&root->fs_info->free_chunk_lock);
1236                 root->fs_info->free_chunk_space += len;
1237                 spin_unlock(&root->fs_info->free_chunk_lock);
1238         }
1239         ret = btrfs_del_item(trans, root, path);
1240         if (ret) {
1241                 btrfs_error(root->fs_info, ret,
1242                             "Failed to remove dev extent item");
1243         }
1244 out:
1245         btrfs_free_path(path);
1246         return ret;
1247 }
1248
1249 static int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
1250                                   struct btrfs_device *device,
1251                                   u64 chunk_tree, u64 chunk_objectid,
1252                                   u64 chunk_offset, u64 start, u64 num_bytes)
1253 {
1254         int ret;
1255         struct btrfs_path *path;
1256         struct btrfs_root *root = device->dev_root;
1257         struct btrfs_dev_extent *extent;
1258         struct extent_buffer *leaf;
1259         struct btrfs_key key;
1260
1261         WARN_ON(!device->in_fs_metadata);
1262         WARN_ON(device->is_tgtdev_for_dev_replace);
1263         path = btrfs_alloc_path();
1264         if (!path)
1265                 return -ENOMEM;
1266
1267         key.objectid = device->devid;
1268         key.offset = start;
1269         key.type = BTRFS_DEV_EXTENT_KEY;
1270         ret = btrfs_insert_empty_item(trans, root, path, &key,
1271                                       sizeof(*extent));
1272         if (ret)
1273                 goto out;
1274
1275         leaf = path->nodes[0];
1276         extent = btrfs_item_ptr(leaf, path->slots[0],
1277                                 struct btrfs_dev_extent);
1278         btrfs_set_dev_extent_chunk_tree(leaf, extent, chunk_tree);
1279         btrfs_set_dev_extent_chunk_objectid(leaf, extent, chunk_objectid);
1280         btrfs_set_dev_extent_chunk_offset(leaf, extent, chunk_offset);
1281
1282         write_extent_buffer(leaf, root->fs_info->chunk_tree_uuid,
1283                     (unsigned long)btrfs_dev_extent_chunk_tree_uuid(extent),
1284                     BTRFS_UUID_SIZE);
1285
1286         btrfs_set_dev_extent_length(leaf, extent, num_bytes);
1287         btrfs_mark_buffer_dirty(leaf);
1288 out:
1289         btrfs_free_path(path);
1290         return ret;
1291 }
1292
1293 static u64 find_next_chunk(struct btrfs_fs_info *fs_info)
1294 {
1295         struct extent_map_tree *em_tree;
1296         struct extent_map *em;
1297         struct rb_node *n;
1298         u64 ret = 0;
1299
1300         em_tree = &fs_info->mapping_tree.map_tree;
1301         read_lock(&em_tree->lock);
1302         n = rb_last(&em_tree->map);
1303         if (n) {
1304                 em = rb_entry(n, struct extent_map, rb_node);
1305                 ret = em->start + em->len;
1306         }
1307         read_unlock(&em_tree->lock);
1308
1309         return ret;
1310 }
1311
1312 static noinline int find_next_devid(struct btrfs_fs_info *fs_info,
1313                                     u64 *devid_ret)
1314 {
1315         int ret;
1316         struct btrfs_key key;
1317         struct btrfs_key found_key;
1318         struct btrfs_path *path;
1319
1320         path = btrfs_alloc_path();
1321         if (!path)
1322                 return -ENOMEM;
1323
1324         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1325         key.type = BTRFS_DEV_ITEM_KEY;
1326         key.offset = (u64)-1;
1327
1328         ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, path, 0, 0);
1329         if (ret < 0)
1330                 goto error;
1331
1332         BUG_ON(ret == 0); /* Corruption */
1333
1334         ret = btrfs_previous_item(fs_info->chunk_root, path,
1335                                   BTRFS_DEV_ITEMS_OBJECTID,
1336                                   BTRFS_DEV_ITEM_KEY);
1337         if (ret) {
1338                 *devid_ret = 1;
1339         } else {
1340                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1341                                       path->slots[0]);
1342                 *devid_ret = found_key.offset + 1;
1343         }
1344         ret = 0;
1345 error:
1346         btrfs_free_path(path);
1347         return ret;
1348 }
1349
1350 /*
1351  * the device information is stored in the chunk root
1352  * the btrfs_device struct should be fully filled in
1353  */
1354 static int btrfs_add_device(struct btrfs_trans_handle *trans,
1355                             struct btrfs_root *root,
1356                             struct btrfs_device *device)
1357 {
1358         int ret;
1359         struct btrfs_path *path;
1360         struct btrfs_dev_item *dev_item;
1361         struct extent_buffer *leaf;
1362         struct btrfs_key key;
1363         unsigned long ptr;
1364
1365         root = root->fs_info->chunk_root;
1366
1367         path = btrfs_alloc_path();
1368         if (!path)
1369                 return -ENOMEM;
1370
1371         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1372         key.type = BTRFS_DEV_ITEM_KEY;
1373         key.offset = device->devid;
1374
1375         ret = btrfs_insert_empty_item(trans, root, path, &key,
1376                                       sizeof(*dev_item));
1377         if (ret)
1378                 goto out;
1379
1380         leaf = path->nodes[0];
1381         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
1382
1383         btrfs_set_device_id(leaf, dev_item, device->devid);
1384         btrfs_set_device_generation(leaf, dev_item, 0);
1385         btrfs_set_device_type(leaf, dev_item, device->type);
1386         btrfs_set_device_io_align(leaf, dev_item, device->io_align);
1387         btrfs_set_device_io_width(leaf, dev_item, device->io_width);
1388         btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
1389         btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
1390         btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
1391         btrfs_set_device_group(leaf, dev_item, 0);
1392         btrfs_set_device_seek_speed(leaf, dev_item, 0);
1393         btrfs_set_device_bandwidth(leaf, dev_item, 0);
1394         btrfs_set_device_start_offset(leaf, dev_item, 0);
1395
1396         ptr = (unsigned long)btrfs_device_uuid(dev_item);
1397         write_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
1398         ptr = (unsigned long)btrfs_device_fsid(dev_item);
1399         write_extent_buffer(leaf, root->fs_info->fsid, ptr, BTRFS_UUID_SIZE);
1400         btrfs_mark_buffer_dirty(leaf);
1401
1402         ret = 0;
1403 out:
1404         btrfs_free_path(path);
1405         return ret;
1406 }
1407
1408 static int btrfs_rm_dev_item(struct btrfs_root *root,
1409                              struct btrfs_device *device)
1410 {
1411         int ret;
1412         struct btrfs_path *path;
1413         struct btrfs_key key;
1414         struct btrfs_trans_handle *trans;
1415
1416         root = root->fs_info->chunk_root;
1417
1418         path = btrfs_alloc_path();
1419         if (!path)
1420                 return -ENOMEM;
1421
1422         trans = btrfs_start_transaction(root, 0);
1423         if (IS_ERR(trans)) {
1424                 btrfs_free_path(path);
1425                 return PTR_ERR(trans);
1426         }
1427         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1428         key.type = BTRFS_DEV_ITEM_KEY;
1429         key.offset = device->devid;
1430         lock_chunks(root);
1431
1432         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1433         if (ret < 0)
1434                 goto out;
1435
1436         if (ret > 0) {
1437                 ret = -ENOENT;
1438                 goto out;
1439         }
1440
1441         ret = btrfs_del_item(trans, root, path);
1442         if (ret)
1443                 goto out;
1444 out:
1445         btrfs_free_path(path);
1446         unlock_chunks(root);
1447         btrfs_commit_transaction(trans, root);
1448         return ret;
1449 }
1450
1451 int btrfs_rm_device(struct btrfs_root *root, char *device_path)
1452 {
1453         struct btrfs_device *device;
1454         struct btrfs_device *next_device;
1455         struct block_device *bdev;
1456         struct buffer_head *bh = NULL;
1457         struct btrfs_super_block *disk_super;
1458         struct btrfs_fs_devices *cur_devices;
1459         u64 all_avail;
1460         u64 devid;
1461         u64 num_devices;
1462         u8 *dev_uuid;
1463         unsigned seq;
1464         int ret = 0;
1465         bool clear_super = false;
1466
1467         mutex_lock(&uuid_mutex);
1468
1469         do {
1470                 seq = read_seqbegin(&root->fs_info->profiles_lock);
1471
1472                 all_avail = root->fs_info->avail_data_alloc_bits |
1473                             root->fs_info->avail_system_alloc_bits |
1474                             root->fs_info->avail_metadata_alloc_bits;
1475         } while (read_seqretry(&root->fs_info->profiles_lock, seq));
1476
1477         num_devices = root->fs_info->fs_devices->num_devices;
1478         btrfs_dev_replace_lock(&root->fs_info->dev_replace);
1479         if (btrfs_dev_replace_is_ongoing(&root->fs_info->dev_replace)) {
1480                 WARN_ON(num_devices < 1);
1481                 num_devices--;
1482         }
1483         btrfs_dev_replace_unlock(&root->fs_info->dev_replace);
1484
1485         if ((all_avail & BTRFS_BLOCK_GROUP_RAID10) && num_devices <= 4) {
1486                 ret = BTRFS_ERROR_DEV_RAID10_MIN_NOT_MET;
1487                 goto out;
1488         }
1489
1490         if ((all_avail & BTRFS_BLOCK_GROUP_RAID1) && num_devices <= 2) {
1491                 ret = BTRFS_ERROR_DEV_RAID1_MIN_NOT_MET;
1492                 goto out;
1493         }
1494
1495         if ((all_avail & BTRFS_BLOCK_GROUP_RAID5) &&
1496             root->fs_info->fs_devices->rw_devices <= 2) {
1497                 ret = BTRFS_ERROR_DEV_RAID5_MIN_NOT_MET;
1498                 goto out;
1499         }
1500         if ((all_avail & BTRFS_BLOCK_GROUP_RAID6) &&
1501             root->fs_info->fs_devices->rw_devices <= 3) {
1502                 ret = BTRFS_ERROR_DEV_RAID6_MIN_NOT_MET;
1503                 goto out;
1504         }
1505
1506         if (strcmp(device_path, "missing") == 0) {
1507                 struct list_head *devices;
1508                 struct btrfs_device *tmp;
1509
1510                 device = NULL;
1511                 devices = &root->fs_info->fs_devices->devices;
1512                 /*
1513                  * It is safe to read the devices since the volume_mutex
1514                  * is held.
1515                  */
1516                 list_for_each_entry(tmp, devices, dev_list) {
1517                         if (tmp->in_fs_metadata &&
1518                             !tmp->is_tgtdev_for_dev_replace &&
1519                             !tmp->bdev) {
1520                                 device = tmp;
1521                                 break;
1522                         }
1523                 }
1524                 bdev = NULL;
1525                 bh = NULL;
1526                 disk_super = NULL;
1527                 if (!device) {
1528                         ret = BTRFS_ERROR_DEV_MISSING_NOT_FOUND;
1529                         goto out;
1530                 }
1531         } else {
1532                 ret = btrfs_get_bdev_and_sb(device_path,
1533                                             FMODE_WRITE | FMODE_EXCL,
1534                                             root->fs_info->bdev_holder, 0,
1535                                             &bdev, &bh);
1536                 if (ret)
1537                         goto out;
1538                 disk_super = (struct btrfs_super_block *)bh->b_data;
1539                 devid = btrfs_stack_device_id(&disk_super->dev_item);
1540                 dev_uuid = disk_super->dev_item.uuid;
1541                 device = btrfs_find_device(root->fs_info, devid, dev_uuid,
1542                                            disk_super->fsid);
1543                 if (!device) {
1544                         ret = -ENOENT;
1545                         goto error_brelse;
1546                 }
1547         }
1548
1549         if (device->is_tgtdev_for_dev_replace) {
1550                 ret = BTRFS_ERROR_DEV_TGT_REPLACE;
1551                 goto error_brelse;
1552         }
1553
1554         if (device->writeable && root->fs_info->fs_devices->rw_devices == 1) {
1555                 ret = BTRFS_ERROR_DEV_ONLY_WRITABLE;
1556                 goto error_brelse;
1557         }
1558
1559         if (device->writeable) {
1560                 lock_chunks(root);
1561                 list_del_init(&device->dev_alloc_list);
1562                 unlock_chunks(root);
1563                 root->fs_info->fs_devices->rw_devices--;
1564                 clear_super = true;
1565         }
1566
1567         mutex_unlock(&uuid_mutex);
1568         ret = btrfs_shrink_device(device, 0);
1569         mutex_lock(&uuid_mutex);
1570         if (ret)
1571                 goto error_undo;
1572
1573         /*
1574          * TODO: the superblock still includes this device in its num_devices
1575          * counter although write_all_supers() is not locked out. This
1576          * could give a filesystem state which requires a degraded mount.
1577          */
1578         ret = btrfs_rm_dev_item(root->fs_info->chunk_root, device);
1579         if (ret)
1580                 goto error_undo;
1581
1582         spin_lock(&root->fs_info->free_chunk_lock);
1583         root->fs_info->free_chunk_space = device->total_bytes -
1584                 device->bytes_used;
1585         spin_unlock(&root->fs_info->free_chunk_lock);
1586
1587         device->in_fs_metadata = 0;
1588         btrfs_scrub_cancel_dev(root->fs_info, device);
1589
1590         /*
1591          * the device list mutex makes sure that we don't change
1592          * the device list while someone else is writing out all
1593          * the device supers.
1594          */
1595
1596         cur_devices = device->fs_devices;
1597         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
1598         list_del_rcu(&device->dev_list);
1599
1600         device->fs_devices->num_devices--;
1601         device->fs_devices->total_devices--;
1602
1603         if (device->missing)
1604                 root->fs_info->fs_devices->missing_devices--;
1605
1606         next_device = list_entry(root->fs_info->fs_devices->devices.next,
1607                                  struct btrfs_device, dev_list);
1608         if (device->bdev == root->fs_info->sb->s_bdev)
1609                 root->fs_info->sb->s_bdev = next_device->bdev;
1610         if (device->bdev == root->fs_info->fs_devices->latest_bdev)
1611                 root->fs_info->fs_devices->latest_bdev = next_device->bdev;
1612
1613         if (device->bdev)
1614                 device->fs_devices->open_devices--;
1615
1616         call_rcu(&device->rcu, free_device);
1617         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
1618
1619         num_devices = btrfs_super_num_devices(root->fs_info->super_copy) - 1;
1620         btrfs_set_super_num_devices(root->fs_info->super_copy, num_devices);
1621
1622         if (cur_devices->open_devices == 0) {
1623                 struct btrfs_fs_devices *fs_devices;
1624                 fs_devices = root->fs_info->fs_devices;
1625                 while (fs_devices) {
1626                         if (fs_devices->seed == cur_devices)
1627                                 break;
1628                         fs_devices = fs_devices->seed;
1629                 }
1630                 fs_devices->seed = cur_devices->seed;
1631                 cur_devices->seed = NULL;
1632                 lock_chunks(root);
1633                 __btrfs_close_devices(cur_devices);
1634                 unlock_chunks(root);
1635                 free_fs_devices(cur_devices);
1636         }
1637
1638         root->fs_info->num_tolerated_disk_barrier_failures =
1639                 btrfs_calc_num_tolerated_disk_barrier_failures(root->fs_info);
1640
1641         /*
1642          * at this point, the device is zero sized.  We want to
1643          * remove it from the devices list and zero out the old super
1644          */
1645         if (clear_super && disk_super) {
1646                 /* make sure this device isn't detected as part of
1647                  * the FS anymore
1648                  */
1649                 memset(&disk_super->magic, 0, sizeof(disk_super->magic));
1650                 set_buffer_dirty(bh);
1651                 sync_dirty_buffer(bh);
1652         }
1653
1654         ret = 0;
1655
1656         /* Notify udev that device has changed */
1657         if (bdev)
1658                 btrfs_kobject_uevent(bdev, KOBJ_CHANGE);
1659
1660 error_brelse:
1661         brelse(bh);
1662         if (bdev)
1663                 blkdev_put(bdev, FMODE_READ | FMODE_EXCL);
1664 out:
1665         mutex_unlock(&uuid_mutex);
1666         return ret;
1667 error_undo:
1668         if (device->writeable) {
1669                 lock_chunks(root);
1670                 list_add(&device->dev_alloc_list,
1671                          &root->fs_info->fs_devices->alloc_list);
1672                 unlock_chunks(root);
1673                 root->fs_info->fs_devices->rw_devices++;
1674         }
1675         goto error_brelse;
1676 }
1677
1678 void btrfs_rm_dev_replace_srcdev(struct btrfs_fs_info *fs_info,
1679                                  struct btrfs_device *srcdev)
1680 {
1681         WARN_ON(!mutex_is_locked(&fs_info->fs_devices->device_list_mutex));
1682         list_del_rcu(&srcdev->dev_list);
1683         list_del_rcu(&srcdev->dev_alloc_list);
1684         fs_info->fs_devices->num_devices--;
1685         if (srcdev->missing) {
1686                 fs_info->fs_devices->missing_devices--;
1687                 fs_info->fs_devices->rw_devices++;
1688         }
1689         if (srcdev->can_discard)
1690                 fs_info->fs_devices->num_can_discard--;
1691         if (srcdev->bdev)
1692                 fs_info->fs_devices->open_devices--;
1693
1694         call_rcu(&srcdev->rcu, free_device);
1695 }
1696
1697 void btrfs_destroy_dev_replace_tgtdev(struct btrfs_fs_info *fs_info,
1698                                       struct btrfs_device *tgtdev)
1699 {
1700         struct btrfs_device *next_device;
1701
1702         WARN_ON(!tgtdev);
1703         mutex_lock(&fs_info->fs_devices->device_list_mutex);
1704         if (tgtdev->bdev) {
1705                 btrfs_scratch_superblock(tgtdev);
1706                 fs_info->fs_devices->open_devices--;
1707         }
1708         fs_info->fs_devices->num_devices--;
1709         if (tgtdev->can_discard)
1710                 fs_info->fs_devices->num_can_discard++;
1711
1712         next_device = list_entry(fs_info->fs_devices->devices.next,
1713                                  struct btrfs_device, dev_list);
1714         if (tgtdev->bdev == fs_info->sb->s_bdev)
1715                 fs_info->sb->s_bdev = next_device->bdev;
1716         if (tgtdev->bdev == fs_info->fs_devices->latest_bdev)
1717                 fs_info->fs_devices->latest_bdev = next_device->bdev;
1718         list_del_rcu(&tgtdev->dev_list);
1719
1720         call_rcu(&tgtdev->rcu, free_device);
1721
1722         mutex_unlock(&fs_info->fs_devices->device_list_mutex);
1723 }
1724
1725 static int btrfs_find_device_by_path(struct btrfs_root *root, char *device_path,
1726                                      struct btrfs_device **device)
1727 {
1728         int ret = 0;
1729         struct btrfs_super_block *disk_super;
1730         u64 devid;
1731         u8 *dev_uuid;
1732         struct block_device *bdev;
1733         struct buffer_head *bh;
1734
1735         *device = NULL;
1736         ret = btrfs_get_bdev_and_sb(device_path, FMODE_READ,
1737                                     root->fs_info->bdev_holder, 0, &bdev, &bh);
1738         if (ret)
1739                 return ret;
1740         disk_super = (struct btrfs_super_block *)bh->b_data;
1741         devid = btrfs_stack_device_id(&disk_super->dev_item);
1742         dev_uuid = disk_super->dev_item.uuid;
1743         *device = btrfs_find_device(root->fs_info, devid, dev_uuid,
1744                                     disk_super->fsid);
1745         brelse(bh);
1746         if (!*device)
1747                 ret = -ENOENT;
1748         blkdev_put(bdev, FMODE_READ);
1749         return ret;
1750 }
1751
1752 int btrfs_find_device_missing_or_by_path(struct btrfs_root *root,
1753                                          char *device_path,
1754                                          struct btrfs_device **device)
1755 {
1756         *device = NULL;
1757         if (strcmp(device_path, "missing") == 0) {
1758                 struct list_head *devices;
1759                 struct btrfs_device *tmp;
1760
1761                 devices = &root->fs_info->fs_devices->devices;
1762                 /*
1763                  * It is safe to read the devices since the volume_mutex
1764                  * is held by the caller.
1765                  */
1766                 list_for_each_entry(tmp, devices, dev_list) {
1767                         if (tmp->in_fs_metadata && !tmp->bdev) {
1768                                 *device = tmp;
1769                                 break;
1770                         }
1771                 }
1772
1773                 if (!*device) {
1774                         pr_err("btrfs: no missing device found\n");
1775                         return -ENOENT;
1776                 }
1777
1778                 return 0;
1779         } else {
1780                 return btrfs_find_device_by_path(root, device_path, device);
1781         }
1782 }
1783
1784 /*
1785  * does all the dirty work required for changing file system's UUID.
1786  */
1787 static int btrfs_prepare_sprout(struct btrfs_root *root)
1788 {
1789         struct btrfs_fs_devices *fs_devices = root->fs_info->fs_devices;
1790         struct btrfs_fs_devices *old_devices;
1791         struct btrfs_fs_devices *seed_devices;
1792         struct btrfs_super_block *disk_super = root->fs_info->super_copy;
1793         struct btrfs_device *device;
1794         u64 super_flags;
1795
1796         BUG_ON(!mutex_is_locked(&uuid_mutex));
1797         if (!fs_devices->seeding)
1798                 return -EINVAL;
1799
1800         seed_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
1801         if (!seed_devices)
1802                 return -ENOMEM;
1803
1804         old_devices = clone_fs_devices(fs_devices);
1805         if (IS_ERR(old_devices)) {
1806                 kfree(seed_devices);
1807                 return PTR_ERR(old_devices);
1808         }
1809
1810         list_add(&old_devices->list, &fs_uuids);
1811
1812         memcpy(seed_devices, fs_devices, sizeof(*seed_devices));
1813         seed_devices->opened = 1;
1814         INIT_LIST_HEAD(&seed_devices->devices);
1815         INIT_LIST_HEAD(&seed_devices->alloc_list);
1816         mutex_init(&seed_devices->device_list_mutex);
1817
1818         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
1819         list_splice_init_rcu(&fs_devices->devices, &seed_devices->devices,
1820                               synchronize_rcu);
1821         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
1822
1823         list_splice_init(&fs_devices->alloc_list, &seed_devices->alloc_list);
1824         list_for_each_entry(device, &seed_devices->devices, dev_list) {
1825                 device->fs_devices = seed_devices;
1826         }
1827
1828         fs_devices->seeding = 0;
1829         fs_devices->num_devices = 0;
1830         fs_devices->open_devices = 0;
1831         fs_devices->total_devices = 0;
1832         fs_devices->seed = seed_devices;
1833
1834         generate_random_uuid(fs_devices->fsid);
1835         memcpy(root->fs_info->fsid, fs_devices->fsid, BTRFS_FSID_SIZE);
1836         memcpy(disk_super->fsid, fs_devices->fsid, BTRFS_FSID_SIZE);
1837         super_flags = btrfs_super_flags(disk_super) &
1838                       ~BTRFS_SUPER_FLAG_SEEDING;
1839         btrfs_set_super_flags(disk_super, super_flags);
1840
1841         return 0;
1842 }
1843
1844 /*
1845  * strore the expected generation for seed devices in device items.
1846  */
1847 static int btrfs_finish_sprout(struct btrfs_trans_handle *trans,
1848                                struct btrfs_root *root)
1849 {
1850         struct btrfs_path *path;
1851         struct extent_buffer *leaf;
1852         struct btrfs_dev_item *dev_item;
1853         struct btrfs_device *device;
1854         struct btrfs_key key;
1855         u8 fs_uuid[BTRFS_UUID_SIZE];
1856         u8 dev_uuid[BTRFS_UUID_SIZE];
1857         u64 devid;
1858         int ret;
1859
1860         path = btrfs_alloc_path();
1861         if (!path)
1862                 return -ENOMEM;
1863
1864         root = root->fs_info->chunk_root;
1865         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1866         key.offset = 0;
1867         key.type = BTRFS_DEV_ITEM_KEY;
1868
1869         while (1) {
1870                 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1871                 if (ret < 0)
1872                         goto error;
1873
1874                 leaf = path->nodes[0];
1875 next_slot:
1876                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
1877                         ret = btrfs_next_leaf(root, path);
1878                         if (ret > 0)
1879                                 break;
1880                         if (ret < 0)
1881                                 goto error;
1882                         leaf = path->nodes[0];
1883                         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1884                         btrfs_release_path(path);
1885                         continue;
1886                 }
1887
1888                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1889                 if (key.objectid != BTRFS_DEV_ITEMS_OBJECTID ||
1890                     key.type != BTRFS_DEV_ITEM_KEY)
1891                         break;
1892
1893                 dev_item = btrfs_item_ptr(leaf, path->slots[0],
1894                                           struct btrfs_dev_item);
1895                 devid = btrfs_device_id(leaf, dev_item);
1896                 read_extent_buffer(leaf, dev_uuid,
1897                                    (unsigned long)btrfs_device_uuid(dev_item),
1898                                    BTRFS_UUID_SIZE);
1899                 read_extent_buffer(leaf, fs_uuid,
1900                                    (unsigned long)btrfs_device_fsid(dev_item),
1901                                    BTRFS_UUID_SIZE);
1902                 device = btrfs_find_device(root->fs_info, devid, dev_uuid,
1903                                            fs_uuid);
1904                 BUG_ON(!device); /* Logic error */
1905
1906                 if (device->fs_devices->seeding) {
1907                         btrfs_set_device_generation(leaf, dev_item,
1908                                                     device->generation);
1909                         btrfs_mark_buffer_dirty(leaf);
1910                 }
1911
1912                 path->slots[0]++;
1913                 goto next_slot;
1914         }
1915         ret = 0;
1916 error:
1917         btrfs_free_path(path);
1918         return ret;
1919 }
1920
1921 int btrfs_init_new_device(struct btrfs_root *root, char *device_path)
1922 {
1923         struct request_queue *q;
1924         struct btrfs_trans_handle *trans;
1925         struct btrfs_device *device;
1926         struct block_device *bdev;
1927         struct list_head *devices;
1928         struct super_block *sb = root->fs_info->sb;
1929         struct rcu_string *name;
1930         u64 total_bytes;
1931         int seeding_dev = 0;
1932         int ret = 0;
1933
1934         if ((sb->s_flags & MS_RDONLY) && !root->fs_info->fs_devices->seeding)
1935                 return -EROFS;
1936
1937         bdev = blkdev_get_by_path(device_path, FMODE_WRITE | FMODE_EXCL,
1938                                   root->fs_info->bdev_holder);
1939         if (IS_ERR(bdev))
1940                 return PTR_ERR(bdev);
1941
1942         if (root->fs_info->fs_devices->seeding) {
1943                 seeding_dev = 1;
1944                 down_write(&sb->s_umount);
1945                 mutex_lock(&uuid_mutex);
1946         }
1947
1948         filemap_write_and_wait(bdev->bd_inode->i_mapping);
1949
1950         devices = &root->fs_info->fs_devices->devices;
1951
1952         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
1953         list_for_each_entry(device, devices, dev_list) {
1954                 if (device->bdev == bdev) {
1955                         ret = -EEXIST;
1956                         mutex_unlock(
1957                                 &root->fs_info->fs_devices->device_list_mutex);
1958                         goto error;
1959                 }
1960         }
1961         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
1962
1963         device = btrfs_alloc_device(root->fs_info, NULL, NULL);
1964         if (IS_ERR(device)) {
1965                 /* we can safely leave the fs_devices entry around */
1966                 ret = PTR_ERR(device);
1967                 goto error;
1968         }
1969
1970         name = rcu_string_strdup(device_path, GFP_NOFS);
1971         if (!name) {
1972                 kfree(device);
1973                 ret = -ENOMEM;
1974                 goto error;
1975         }
1976         rcu_assign_pointer(device->name, name);
1977
1978         trans = btrfs_start_transaction(root, 0);
1979         if (IS_ERR(trans)) {
1980                 rcu_string_free(device->name);
1981                 kfree(device);
1982                 ret = PTR_ERR(trans);
1983                 goto error;
1984         }
1985
1986         lock_chunks(root);
1987
1988         q = bdev_get_queue(bdev);
1989         if (blk_queue_discard(q))
1990                 device->can_discard = 1;
1991         device->writeable = 1;
1992         device->generation = trans->transid;
1993         device->io_width = root->sectorsize;
1994         device->io_align = root->sectorsize;
1995         device->sector_size = root->sectorsize;
1996         device->total_bytes = i_size_read(bdev->bd_inode);
1997         device->disk_total_bytes = device->total_bytes;
1998         device->dev_root = root->fs_info->dev_root;
1999         device->bdev = bdev;
2000         device->in_fs_metadata = 1;
2001         device->is_tgtdev_for_dev_replace = 0;
2002         device->mode = FMODE_EXCL;
2003         set_blocksize(device->bdev, 4096);
2004
2005         if (seeding_dev) {
2006                 sb->s_flags &= ~MS_RDONLY;
2007                 ret = btrfs_prepare_sprout(root);
2008                 BUG_ON(ret); /* -ENOMEM */
2009         }
2010
2011         device->fs_devices = root->fs_info->fs_devices;
2012
2013         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
2014         list_add_rcu(&device->dev_list, &root->fs_info->fs_devices->devices);
2015         list_add(&device->dev_alloc_list,
2016                  &root->fs_info->fs_devices->alloc_list);
2017         root->fs_info->fs_devices->num_devices++;
2018         root->fs_info->fs_devices->open_devices++;
2019         root->fs_info->fs_devices->rw_devices++;
2020         root->fs_info->fs_devices->total_devices++;
2021         if (device->can_discard)
2022                 root->fs_info->fs_devices->num_can_discard++;
2023         root->fs_info->fs_devices->total_rw_bytes += device->total_bytes;
2024
2025         spin_lock(&root->fs_info->free_chunk_lock);
2026         root->fs_info->free_chunk_space += device->total_bytes;
2027         spin_unlock(&root->fs_info->free_chunk_lock);
2028
2029         if (!blk_queue_nonrot(bdev_get_queue(bdev)))
2030                 root->fs_info->fs_devices->rotating = 1;
2031
2032         total_bytes = btrfs_super_total_bytes(root->fs_info->super_copy);
2033         btrfs_set_super_total_bytes(root->fs_info->super_copy,
2034                                     total_bytes + device->total_bytes);
2035
2036         total_bytes = btrfs_super_num_devices(root->fs_info->super_copy);
2037         btrfs_set_super_num_devices(root->fs_info->super_copy,
2038                                     total_bytes + 1);
2039         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
2040
2041         if (seeding_dev) {
2042                 ret = init_first_rw_device(trans, root, device);
2043                 if (ret) {
2044                         btrfs_abort_transaction(trans, root, ret);
2045                         goto error_trans;
2046                 }
2047                 ret = btrfs_finish_sprout(trans, root);
2048                 if (ret) {
2049                         btrfs_abort_transaction(trans, root, ret);
2050                         goto error_trans;
2051                 }
2052         } else {
2053                 ret = btrfs_add_device(trans, root, device);
2054                 if (ret) {
2055                         btrfs_abort_transaction(trans, root, ret);
2056                         goto error_trans;
2057                 }
2058         }
2059
2060         /*
2061          * we've got more storage, clear any full flags on the space
2062          * infos
2063          */
2064         btrfs_clear_space_info_full(root->fs_info);
2065
2066         unlock_chunks(root);
2067         root->fs_info->num_tolerated_disk_barrier_failures =
2068                 btrfs_calc_num_tolerated_disk_barrier_failures(root->fs_info);
2069         ret = btrfs_commit_transaction(trans, root);
2070
2071         if (seeding_dev) {
2072                 mutex_unlock(&uuid_mutex);
2073                 up_write(&sb->s_umount);
2074
2075                 if (ret) /* transaction commit */
2076                         return ret;
2077
2078                 ret = btrfs_relocate_sys_chunks(root);
2079                 if (ret < 0)
2080                         btrfs_error(root->fs_info, ret,
2081                                     "Failed to relocate sys chunks after "
2082                                     "device initialization. This can be fixed "
2083                                     "using the \"btrfs balance\" command.");
2084                 trans = btrfs_attach_transaction(root);
2085                 if (IS_ERR(trans)) {
2086                         if (PTR_ERR(trans) == -ENOENT)
2087                                 return 0;
2088                         return PTR_ERR(trans);
2089                 }
2090                 ret = btrfs_commit_transaction(trans, root);
2091         }
2092
2093         return ret;
2094
2095 error_trans:
2096         unlock_chunks(root);
2097         btrfs_end_transaction(trans, root);
2098         rcu_string_free(device->name);
2099         kfree(device);
2100 error:
2101         blkdev_put(bdev, FMODE_EXCL);
2102         if (seeding_dev) {
2103                 mutex_unlock(&uuid_mutex);
2104                 up_write(&sb->s_umount);
2105         }
2106         return ret;
2107 }
2108
2109 int btrfs_init_dev_replace_tgtdev(struct btrfs_root *root, char *device_path,
2110                                   struct btrfs_device **device_out)
2111 {
2112         struct request_queue *q;
2113         struct btrfs_device *device;
2114         struct block_device *bdev;
2115         struct btrfs_fs_info *fs_info = root->fs_info;
2116         struct list_head *devices;
2117         struct rcu_string *name;
2118         u64 devid = BTRFS_DEV_REPLACE_DEVID;
2119         int ret = 0;
2120
2121         *device_out = NULL;
2122         if (fs_info->fs_devices->seeding)
2123                 return -EINVAL;
2124
2125         bdev = blkdev_get_by_path(device_path, FMODE_WRITE | FMODE_EXCL,
2126                                   fs_info->bdev_holder);
2127         if (IS_ERR(bdev))
2128                 return PTR_ERR(bdev);
2129
2130         filemap_write_and_wait(bdev->bd_inode->i_mapping);
2131
2132         devices = &fs_info->fs_devices->devices;
2133         list_for_each_entry(device, devices, dev_list) {
2134                 if (device->bdev == bdev) {
2135                         ret = -EEXIST;
2136                         goto error;
2137                 }
2138         }
2139
2140         device = btrfs_alloc_device(NULL, &devid, NULL);
2141         if (IS_ERR(device)) {
2142                 ret = PTR_ERR(device);
2143                 goto error;
2144         }
2145
2146         name = rcu_string_strdup(device_path, GFP_NOFS);
2147         if (!name) {
2148                 kfree(device);
2149                 ret = -ENOMEM;
2150                 goto error;
2151         }
2152         rcu_assign_pointer(device->name, name);
2153
2154         q = bdev_get_queue(bdev);
2155         if (blk_queue_discard(q))
2156                 device->can_discard = 1;
2157         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
2158         device->writeable = 1;
2159         device->generation = 0;
2160         device->io_width = root->sectorsize;
2161         device->io_align = root->sectorsize;
2162         device->sector_size = root->sectorsize;
2163         device->total_bytes = i_size_read(bdev->bd_inode);
2164         device->disk_total_bytes = device->total_bytes;
2165         device->dev_root = fs_info->dev_root;
2166         device->bdev = bdev;
2167         device->in_fs_metadata = 1;
2168         device->is_tgtdev_for_dev_replace = 1;
2169         device->mode = FMODE_EXCL;
2170         set_blocksize(device->bdev, 4096);
2171         device->fs_devices = fs_info->fs_devices;
2172         list_add(&device->dev_list, &fs_info->fs_devices->devices);
2173         fs_info->fs_devices->num_devices++;
2174         fs_info->fs_devices->open_devices++;
2175         if (device->can_discard)
2176                 fs_info->fs_devices->num_can_discard++;
2177         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
2178
2179         *device_out = device;
2180         return ret;
2181
2182 error:
2183         blkdev_put(bdev, FMODE_EXCL);
2184         return ret;
2185 }
2186
2187 void btrfs_init_dev_replace_tgtdev_for_resume(struct btrfs_fs_info *fs_info,
2188                                               struct btrfs_device *tgtdev)
2189 {
2190         WARN_ON(fs_info->fs_devices->rw_devices == 0);
2191         tgtdev->io_width = fs_info->dev_root->sectorsize;
2192         tgtdev->io_align = fs_info->dev_root->sectorsize;
2193         tgtdev->sector_size = fs_info->dev_root->sectorsize;
2194         tgtdev->dev_root = fs_info->dev_root;
2195         tgtdev->in_fs_metadata = 1;
2196 }
2197
2198 static noinline int btrfs_update_device(struct btrfs_trans_handle *trans,
2199                                         struct btrfs_device *device)
2200 {
2201         int ret;
2202         struct btrfs_path *path;
2203         struct btrfs_root *root;
2204         struct btrfs_dev_item *dev_item;
2205         struct extent_buffer *leaf;
2206         struct btrfs_key key;
2207
2208         root = device->dev_root->fs_info->chunk_root;
2209
2210         path = btrfs_alloc_path();
2211         if (!path)
2212                 return -ENOMEM;
2213
2214         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
2215         key.type = BTRFS_DEV_ITEM_KEY;
2216         key.offset = device->devid;
2217
2218         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
2219         if (ret < 0)
2220                 goto out;
2221
2222         if (ret > 0) {
2223                 ret = -ENOENT;
2224                 goto out;
2225         }
2226
2227         leaf = path->nodes[0];
2228         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
2229
2230         btrfs_set_device_id(leaf, dev_item, device->devid);
2231         btrfs_set_device_type(leaf, dev_item, device->type);
2232         btrfs_set_device_io_align(leaf, dev_item, device->io_align);
2233         btrfs_set_device_io_width(leaf, dev_item, device->io_width);
2234         btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
2235         btrfs_set_device_total_bytes(leaf, dev_item, device->disk_total_bytes);
2236         btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
2237         btrfs_mark_buffer_dirty(leaf);
2238
2239 out:
2240         btrfs_free_path(path);
2241         return ret;
2242 }
2243
2244 static int __btrfs_grow_device(struct btrfs_trans_handle *trans,
2245                       struct btrfs_device *device, u64 new_size)
2246 {
2247         struct btrfs_super_block *super_copy =
2248                 device->dev_root->fs_info->super_copy;
2249         u64 old_total = btrfs_super_total_bytes(super_copy);
2250         u64 diff = new_size - device->total_bytes;
2251
2252         if (!device->writeable)
2253                 return -EACCES;
2254         if (new_size <= device->total_bytes ||
2255             device->is_tgtdev_for_dev_replace)
2256                 return -EINVAL;
2257
2258         btrfs_set_super_total_bytes(super_copy, old_total + diff);
2259         device->fs_devices->total_rw_bytes += diff;
2260
2261         device->total_bytes = new_size;
2262         device->disk_total_bytes = new_size;
2263         btrfs_clear_space_info_full(device->dev_root->fs_info);
2264
2265         return btrfs_update_device(trans, device);
2266 }
2267
2268 int btrfs_grow_device(struct btrfs_trans_handle *trans,
2269                       struct btrfs_device *device, u64 new_size)
2270 {
2271         int ret;
2272         lock_chunks(device->dev_root);
2273         ret = __btrfs_grow_device(trans, device, new_size);
2274         unlock_chunks(device->dev_root);
2275         return ret;
2276 }
2277
2278 static int btrfs_free_chunk(struct btrfs_trans_handle *trans,
2279                             struct btrfs_root *root,
2280                             u64 chunk_tree, u64 chunk_objectid,
2281                             u64 chunk_offset)
2282 {
2283         int ret;
2284         struct btrfs_path *path;
2285         struct btrfs_key key;
2286
2287         root = root->fs_info->chunk_root;
2288         path = btrfs_alloc_path();
2289         if (!path)
2290                 return -ENOMEM;
2291
2292         key.objectid = chunk_objectid;
2293         key.offset = chunk_offset;
2294         key.type = BTRFS_CHUNK_ITEM_KEY;
2295
2296         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
2297         if (ret < 0)
2298                 goto out;
2299         else if (ret > 0) { /* Logic error or corruption */
2300                 btrfs_error(root->fs_info, -ENOENT,
2301                             "Failed lookup while freeing chunk.");
2302                 ret = -ENOENT;
2303                 goto out;
2304         }
2305
2306         ret = btrfs_del_item(trans, root, path);
2307         if (ret < 0)
2308                 btrfs_error(root->fs_info, ret,
2309                             "Failed to delete chunk item.");
2310 out:
2311         btrfs_free_path(path);
2312         return ret;
2313 }
2314
2315 static int btrfs_del_sys_chunk(struct btrfs_root *root, u64 chunk_objectid, u64
2316                         chunk_offset)
2317 {
2318         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
2319         struct btrfs_disk_key *disk_key;
2320         struct btrfs_chunk *chunk;
2321         u8 *ptr;
2322         int ret = 0;
2323         u32 num_stripes;
2324         u32 array_size;
2325         u32 len = 0;
2326         u32 cur;
2327         struct btrfs_key key;
2328
2329         array_size = btrfs_super_sys_array_size(super_copy);
2330
2331         ptr = super_copy->sys_chunk_array;
2332         cur = 0;
2333
2334         while (cur < array_size) {
2335                 disk_key = (struct btrfs_disk_key *)ptr;
2336                 btrfs_disk_key_to_cpu(&key, disk_key);
2337
2338                 len = sizeof(*disk_key);
2339
2340                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
2341                         chunk = (struct btrfs_chunk *)(ptr + len);
2342                         num_stripes = btrfs_stack_chunk_num_stripes(chunk);
2343                         len += btrfs_chunk_item_size(num_stripes);
2344                 } else {
2345                         ret = -EIO;
2346                         break;
2347                 }
2348                 if (key.objectid == chunk_objectid &&
2349                     key.offset == chunk_offset) {
2350                         memmove(ptr, ptr + len, array_size - (cur + len));
2351                         array_size -= len;
2352                         btrfs_set_super_sys_array_size(super_copy, array_size);
2353                 } else {
2354                         ptr += len;
2355                         cur += len;
2356                 }
2357         }
2358         return ret;
2359 }
2360
2361 static int btrfs_relocate_chunk(struct btrfs_root *root,
2362                          u64 chunk_tree, u64 chunk_objectid,
2363                          u64 chunk_offset)
2364 {
2365         struct extent_map_tree *em_tree;
2366         struct btrfs_root *extent_root;
2367         struct btrfs_trans_handle *trans;
2368         struct extent_map *em;
2369         struct map_lookup *map;
2370         int ret;
2371         int i;
2372
2373         root = root->fs_info->chunk_root;
2374         extent_root = root->fs_info->extent_root;
2375         em_tree = &root->fs_info->mapping_tree.map_tree;
2376
2377         ret = btrfs_can_relocate(extent_root, chunk_offset);
2378         if (ret)
2379                 return -ENOSPC;
2380
2381         /* step one, relocate all the extents inside this chunk */
2382         ret = btrfs_relocate_block_group(extent_root, chunk_offset);
2383         if (ret)
2384                 return ret;
2385
2386         trans = btrfs_start_transaction(root, 0);
2387         if (IS_ERR(trans)) {
2388                 ret = PTR_ERR(trans);
2389                 btrfs_std_error(root->fs_info, ret);
2390                 return ret;
2391         }
2392
2393         lock_chunks(root);
2394
2395         /*
2396          * step two, delete the device extents and the
2397          * chunk tree entries
2398          */
2399         read_lock(&em_tree->lock);
2400         em = lookup_extent_mapping(em_tree, chunk_offset, 1);
2401         read_unlock(&em_tree->lock);
2402
2403         BUG_ON(!em || em->start > chunk_offset ||
2404                em->start + em->len < chunk_offset);
2405         map = (struct map_lookup *)em->bdev;
2406
2407         for (i = 0; i < map->num_stripes; i++) {
2408                 ret = btrfs_free_dev_extent(trans, map->stripes[i].dev,
2409                                             map->stripes[i].physical);
2410                 BUG_ON(ret);
2411
2412                 if (map->stripes[i].dev) {
2413                         ret = btrfs_update_device(trans, map->stripes[i].dev);
2414                         BUG_ON(ret);
2415                 }
2416         }
2417         ret = btrfs_free_chunk(trans, root, chunk_tree, chunk_objectid,
2418                                chunk_offset);
2419
2420         BUG_ON(ret);
2421
2422         trace_btrfs_chunk_free(root, map, chunk_offset, em->len);
2423
2424         if (map->type & BTRFS_BLOCK_GROUP_SYSTEM) {
2425                 ret = btrfs_del_sys_chunk(root, chunk_objectid, chunk_offset);
2426                 BUG_ON(ret);
2427         }
2428
2429         ret = btrfs_remove_block_group(trans, extent_root, chunk_offset);
2430         BUG_ON(ret);
2431
2432         write_lock(&em_tree->lock);
2433         remove_extent_mapping(em_tree, em);
2434         write_unlock(&em_tree->lock);
2435
2436         kfree(map);
2437         em->bdev = NULL;
2438
2439         /* once for the tree */
2440         free_extent_map(em);
2441         /* once for us */
2442         free_extent_map(em);
2443
2444         unlock_chunks(root);
2445         btrfs_end_transaction(trans, root);
2446         return 0;
2447 }
2448
2449 static int btrfs_relocate_sys_chunks(struct btrfs_root *root)
2450 {
2451         struct btrfs_root *chunk_root = root->fs_info->chunk_root;
2452         struct btrfs_path *path;
2453         struct extent_buffer *leaf;
2454         struct btrfs_chunk *chunk;
2455         struct btrfs_key key;
2456         struct btrfs_key found_key;
2457         u64 chunk_tree = chunk_root->root_key.objectid;
2458         u64 chunk_type;
2459         bool retried = false;
2460         int failed = 0;
2461         int ret;
2462
2463         path = btrfs_alloc_path();
2464         if (!path)
2465                 return -ENOMEM;
2466
2467 again:
2468         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2469         key.offset = (u64)-1;
2470         key.type = BTRFS_CHUNK_ITEM_KEY;
2471
2472         while (1) {
2473                 ret = btrfs_search_slot(NULL, chunk_root, &key, path, 0, 0);
2474                 if (ret < 0)
2475                         goto error;
2476                 BUG_ON(ret == 0); /* Corruption */
2477
2478                 ret = btrfs_previous_item(chunk_root, path, key.objectid,
2479                                           key.type);
2480                 if (ret < 0)
2481                         goto error;
2482                 if (ret > 0)
2483                         break;
2484
2485                 leaf = path->nodes[0];
2486                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2487
2488                 chunk = btrfs_item_ptr(leaf, path->slots[0],
2489                                        struct btrfs_chunk);
2490                 chunk_type = btrfs_chunk_type(leaf, chunk);
2491                 btrfs_release_path(path);
2492
2493                 if (chunk_type & BTRFS_BLOCK_GROUP_SYSTEM) {
2494                         ret = btrfs_relocate_chunk(chunk_root, chunk_tree,
2495                                                    found_key.objectid,
2496                                                    found_key.offset);
2497                         if (ret == -ENOSPC)
2498                                 failed++;
2499                         else if (ret)
2500                                 BUG();
2501                 }
2502
2503                 if (found_key.offset == 0)
2504                         break;
2505                 key.offset = found_key.offset - 1;
2506         }
2507         ret = 0;
2508         if (failed && !retried) {
2509                 failed = 0;
2510                 retried = true;
2511                 goto again;
2512         } else if (failed && retried) {
2513                 WARN_ON(1);
2514                 ret = -ENOSPC;
2515         }
2516 error:
2517         btrfs_free_path(path);
2518         return ret;
2519 }
2520
2521 static int insert_balance_item(struct btrfs_root *root,
2522                                struct btrfs_balance_control *bctl)
2523 {
2524         struct btrfs_trans_handle *trans;
2525         struct btrfs_balance_item *item;
2526         struct btrfs_disk_balance_args disk_bargs;
2527         struct btrfs_path *path;
2528         struct extent_buffer *leaf;
2529         struct btrfs_key key;
2530         int ret, err;
2531
2532         path = btrfs_alloc_path();
2533         if (!path)
2534                 return -ENOMEM;
2535
2536         trans = btrfs_start_transaction(root, 0);
2537         if (IS_ERR(trans)) {
2538                 btrfs_free_path(path);
2539                 return PTR_ERR(trans);
2540         }
2541
2542         key.objectid = BTRFS_BALANCE_OBJECTID;
2543         key.type = BTRFS_BALANCE_ITEM_KEY;
2544         key.offset = 0;
2545
2546         ret = btrfs_insert_empty_item(trans, root, path, &key,
2547                                       sizeof(*item));
2548         if (ret)
2549                 goto out;
2550
2551         leaf = path->nodes[0];
2552         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_balance_item);
2553
2554         memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
2555
2556         btrfs_cpu_balance_args_to_disk(&disk_bargs, &bctl->data);
2557         btrfs_set_balance_data(leaf, item, &disk_bargs);
2558         btrfs_cpu_balance_args_to_disk(&disk_bargs, &bctl->meta);
2559         btrfs_set_balance_meta(leaf, item, &disk_bargs);
2560         btrfs_cpu_balance_args_to_disk(&disk_bargs, &bctl->sys);
2561         btrfs_set_balance_sys(leaf, item, &disk_bargs);
2562
2563         btrfs_set_balance_flags(leaf, item, bctl->flags);
2564
2565         btrfs_mark_buffer_dirty(leaf);
2566 out:
2567         btrfs_free_path(path);
2568         err = btrfs_commit_transaction(trans, root);
2569         if (err && !ret)
2570                 ret = err;
2571         return ret;
2572 }
2573
2574 static int del_balance_item(struct btrfs_root *root)
2575 {
2576         struct btrfs_trans_handle *trans;
2577         struct btrfs_path *path;
2578         struct btrfs_key key;
2579         int ret, err;
2580
2581         path = btrfs_alloc_path();
2582         if (!path)
2583                 return -ENOMEM;
2584
2585         trans = btrfs_start_transaction(root, 0);
2586         if (IS_ERR(trans)) {
2587                 btrfs_free_path(path);
2588                 return PTR_ERR(trans);
2589         }
2590
2591         key.objectid = BTRFS_BALANCE_OBJECTID;
2592         key.type = BTRFS_BALANCE_ITEM_KEY;
2593         key.offset = 0;
2594
2595         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
2596         if (ret < 0)
2597                 goto out;
2598         if (ret > 0) {
2599                 ret = -ENOENT;
2600                 goto out;
2601         }
2602
2603         ret = btrfs_del_item(trans, root, path);
2604 out:
2605         btrfs_free_path(path);
2606         err = btrfs_commit_transaction(trans, root);
2607         if (err && !ret)
2608                 ret = err;
2609         return ret;
2610 }
2611
2612 /*
2613  * This is a heuristic used to reduce the number of chunks balanced on
2614  * resume after balance was interrupted.
2615  */
2616 static void update_balance_args(struct btrfs_balance_control *bctl)
2617 {
2618         /*
2619          * Turn on soft mode for chunk types that were being converted.
2620          */
2621         if (bctl->data.flags & BTRFS_BALANCE_ARGS_CONVERT)
2622                 bctl->data.flags |= BTRFS_BALANCE_ARGS_SOFT;
2623         if (bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT)
2624                 bctl->sys.flags |= BTRFS_BALANCE_ARGS_SOFT;
2625         if (bctl->meta.flags & BTRFS_BALANCE_ARGS_CONVERT)
2626                 bctl->meta.flags |= BTRFS_BALANCE_ARGS_SOFT;
2627
2628         /*
2629          * Turn on usage filter if is not already used.  The idea is
2630          * that chunks that we have already balanced should be
2631          * reasonably full.  Don't do it for chunks that are being
2632          * converted - that will keep us from relocating unconverted
2633          * (albeit full) chunks.
2634          */
2635         if (!(bctl->data.flags & BTRFS_BALANCE_ARGS_USAGE) &&
2636             !(bctl->data.flags & BTRFS_BALANCE_ARGS_CONVERT)) {
2637                 bctl->data.flags |= BTRFS_BALANCE_ARGS_USAGE;
2638                 bctl->data.usage = 90;
2639         }
2640         if (!(bctl->sys.flags & BTRFS_BALANCE_ARGS_USAGE) &&
2641             !(bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT)) {
2642                 bctl->sys.flags |= BTRFS_BALANCE_ARGS_USAGE;
2643                 bctl->sys.usage = 90;
2644         }
2645         if (!(bctl->meta.flags & BTRFS_BALANCE_ARGS_USAGE) &&
2646             !(bctl->meta.flags & BTRFS_BALANCE_ARGS_CONVERT)) {
2647                 bctl->meta.flags |= BTRFS_BALANCE_ARGS_USAGE;
2648                 bctl->meta.usage = 90;
2649         }
2650 }
2651
2652 /*
2653  * Should be called with both balance and volume mutexes held to
2654  * serialize other volume operations (add_dev/rm_dev/resize) with
2655  * restriper.  Same goes for unset_balance_control.
2656  */
2657 static void set_balance_control(struct btrfs_balance_control *bctl)
2658 {
2659         struct btrfs_fs_info *fs_info = bctl->fs_info;
2660
2661         BUG_ON(fs_info->balance_ctl);
2662
2663         spin_lock(&fs_info->balance_lock);
2664         fs_info->balance_ctl = bctl;
2665         spin_unlock(&fs_info->balance_lock);
2666 }
2667
2668 static void unset_balance_control(struct btrfs_fs_info *fs_info)
2669 {
2670         struct btrfs_balance_control *bctl = fs_info->balance_ctl;
2671
2672         BUG_ON(!fs_info->balance_ctl);
2673
2674         spin_lock(&fs_info->balance_lock);
2675         fs_info->balance_ctl = NULL;
2676         spin_unlock(&fs_info->balance_lock);
2677
2678         kfree(bctl);
2679 }
2680
2681 /*
2682  * Balance filters.  Return 1 if chunk should be filtered out
2683  * (should not be balanced).
2684  */
2685 static int chunk_profiles_filter(u64 chunk_type,
2686                                  struct btrfs_balance_args *bargs)
2687 {
2688         chunk_type = chunk_to_extended(chunk_type) &
2689                                 BTRFS_EXTENDED_PROFILE_MASK;
2690
2691         if (bargs->profiles & chunk_type)
2692                 return 0;
2693
2694         return 1;
2695 }
2696
2697 static int chunk_usage_filter(struct btrfs_fs_info *fs_info, u64 chunk_offset,
2698                               struct btrfs_balance_args *bargs)
2699 {
2700         struct btrfs_block_group_cache *cache;
2701         u64 chunk_used, user_thresh;
2702         int ret = 1;
2703
2704         cache = btrfs_lookup_block_group(fs_info, chunk_offset);
2705         chunk_used = btrfs_block_group_used(&cache->item);
2706
2707         if (bargs->usage == 0)
2708                 user_thresh = 1;
2709         else if (bargs->usage > 100)
2710                 user_thresh = cache->key.offset;
2711         else
2712                 user_thresh = div_factor_fine(cache->key.offset,
2713                                               bargs->usage);
2714
2715         if (chunk_used < user_thresh)
2716                 ret = 0;
2717
2718         btrfs_put_block_group(cache);
2719         return ret;
2720 }
2721
2722 static int chunk_devid_filter(struct extent_buffer *leaf,
2723                               struct btrfs_chunk *chunk,
2724                               struct btrfs_balance_args *bargs)
2725 {
2726         struct btrfs_stripe *stripe;
2727         int num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
2728         int i;
2729
2730         for (i = 0; i < num_stripes; i++) {
2731                 stripe = btrfs_stripe_nr(chunk, i);
2732                 if (btrfs_stripe_devid(leaf, stripe) == bargs->devid)
2733                         return 0;
2734         }
2735
2736         return 1;
2737 }
2738
2739 /* [pstart, pend) */
2740 static int chunk_drange_filter(struct extent_buffer *leaf,
2741                                struct btrfs_chunk *chunk,
2742                                u64 chunk_offset,
2743                                struct btrfs_balance_args *bargs)
2744 {
2745         struct btrfs_stripe *stripe;
2746         int num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
2747         u64 stripe_offset;
2748         u64 stripe_length;
2749         int factor;
2750         int i;
2751
2752         if (!(bargs->flags & BTRFS_BALANCE_ARGS_DEVID))
2753                 return 0;
2754
2755         if (btrfs_chunk_type(leaf, chunk) & (BTRFS_BLOCK_GROUP_DUP |
2756              BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10)) {
2757                 factor = num_stripes / 2;
2758         } else if (btrfs_chunk_type(leaf, chunk) & BTRFS_BLOCK_GROUP_RAID5) {
2759                 factor = num_stripes - 1;
2760         } else if (btrfs_chunk_type(leaf, chunk) & BTRFS_BLOCK_GROUP_RAID6) {
2761                 factor = num_stripes - 2;
2762         } else {
2763                 factor = num_stripes;
2764         }
2765
2766         for (i = 0; i < num_stripes; i++) {
2767                 stripe = btrfs_stripe_nr(chunk, i);
2768                 if (btrfs_stripe_devid(leaf, stripe) != bargs->devid)
2769                         continue;
2770
2771                 stripe_offset = btrfs_stripe_offset(leaf, stripe);
2772                 stripe_length = btrfs_chunk_length(leaf, chunk);
2773                 do_div(stripe_length, factor);
2774
2775                 if (stripe_offset < bargs->pend &&
2776                     stripe_offset + stripe_length > bargs->pstart)
2777                         return 0;
2778         }
2779
2780         return 1;
2781 }
2782
2783 /* [vstart, vend) */
2784 static int chunk_vrange_filter(struct extent_buffer *leaf,
2785                                struct btrfs_chunk *chunk,
2786                                u64 chunk_offset,
2787                                struct btrfs_balance_args *bargs)
2788 {
2789         if (chunk_offset < bargs->vend &&
2790             chunk_offset + btrfs_chunk_length(leaf, chunk) > bargs->vstart)
2791                 /* at least part of the chunk is inside this vrange */
2792                 return 0;
2793
2794         return 1;
2795 }
2796
2797 static int chunk_soft_convert_filter(u64 chunk_type,
2798                                      struct btrfs_balance_args *bargs)
2799 {
2800         if (!(bargs->flags & BTRFS_BALANCE_ARGS_CONVERT))
2801                 return 0;
2802
2803         chunk_type = chunk_to_extended(chunk_type) &
2804                                 BTRFS_EXTENDED_PROFILE_MASK;
2805
2806         if (bargs->target == chunk_type)
2807                 return 1;
2808
2809         return 0;
2810 }
2811
2812 static int should_balance_chunk(struct btrfs_root *root,
2813                                 struct extent_buffer *leaf,
2814                                 struct btrfs_chunk *chunk, u64 chunk_offset)
2815 {
2816         struct btrfs_balance_control *bctl = root->fs_info->balance_ctl;
2817         struct btrfs_balance_args *bargs = NULL;
2818         u64 chunk_type = btrfs_chunk_type(leaf, chunk);
2819
2820         /* type filter */
2821         if (!((chunk_type & BTRFS_BLOCK_GROUP_TYPE_MASK) &
2822               (bctl->flags & BTRFS_BALANCE_TYPE_MASK))) {
2823                 return 0;
2824         }
2825
2826         if (chunk_type & BTRFS_BLOCK_GROUP_DATA)
2827                 bargs = &bctl->data;
2828         else if (chunk_type & BTRFS_BLOCK_GROUP_SYSTEM)
2829                 bargs = &bctl->sys;
2830         else if (chunk_type & BTRFS_BLOCK_GROUP_METADATA)
2831                 bargs = &bctl->meta;
2832
2833         /* profiles filter */
2834         if ((bargs->flags & BTRFS_BALANCE_ARGS_PROFILES) &&
2835             chunk_profiles_filter(chunk_type, bargs)) {
2836                 return 0;
2837         }
2838
2839         /* usage filter */
2840         if ((bargs->flags & BTRFS_BALANCE_ARGS_USAGE) &&
2841             chunk_usage_filter(bctl->fs_info, chunk_offset, bargs)) {
2842                 return 0;
2843         }
2844
2845         /* devid filter */
2846         if ((bargs->flags & BTRFS_BALANCE_ARGS_DEVID) &&
2847             chunk_devid_filter(leaf, chunk, bargs)) {
2848                 return 0;
2849         }
2850
2851         /* drange filter, makes sense only with devid filter */
2852         if ((bargs->flags & BTRFS_BALANCE_ARGS_DRANGE) &&
2853             chunk_drange_filter(leaf, chunk, chunk_offset, bargs)) {
2854                 return 0;
2855         }
2856
2857         /* vrange filter */
2858         if ((bargs->flags & BTRFS_BALANCE_ARGS_VRANGE) &&
2859             chunk_vrange_filter(leaf, chunk, chunk_offset, bargs)) {
2860                 return 0;
2861         }
2862
2863         /* soft profile changing mode */
2864         if ((bargs->flags & BTRFS_BALANCE_ARGS_SOFT) &&
2865             chunk_soft_convert_filter(chunk_type, bargs)) {
2866                 return 0;
2867         }
2868
2869         return 1;
2870 }
2871
2872 static int __btrfs_balance(struct btrfs_fs_info *fs_info)
2873 {
2874         struct btrfs_balance_control *bctl = fs_info->balance_ctl;
2875         struct btrfs_root *chunk_root = fs_info->chunk_root;
2876         struct btrfs_root *dev_root = fs_info->dev_root;
2877         struct list_head *devices;
2878         struct btrfs_device *device;
2879         u64 old_size;
2880         u64 size_to_free;
2881         struct btrfs_chunk *chunk;
2882         struct btrfs_path *path;
2883         struct btrfs_key key;
2884         struct btrfs_key found_key;
2885         struct btrfs_trans_handle *trans;
2886         struct extent_buffer *leaf;
2887         int slot;
2888         int ret;
2889         int enospc_errors = 0;
2890         bool counting = true;
2891
2892         /* step one make some room on all the devices */
2893         devices = &fs_info->fs_devices->devices;
2894         list_for_each_entry(device, devices, dev_list) {
2895                 old_size = device->total_bytes;
2896                 size_to_free = div_factor(old_size, 1);
2897                 size_to_free = min(size_to_free, (u64)1 * 1024 * 1024);
2898                 if (!device->writeable ||
2899                     device->total_bytes - device->bytes_used > size_to_free ||
2900                     device->is_tgtdev_for_dev_replace)
2901                         continue;
2902
2903                 ret = btrfs_shrink_device(device, old_size - size_to_free);
2904                 if (ret == -ENOSPC)
2905                         break;
2906                 BUG_ON(ret);
2907
2908                 trans = btrfs_start_transaction(dev_root, 0);
2909                 BUG_ON(IS_ERR(trans));
2910
2911                 ret = btrfs_grow_device(trans, device, old_size);
2912                 BUG_ON(ret);
2913
2914                 btrfs_end_transaction(trans, dev_root);
2915         }
2916
2917         /* step two, relocate all the chunks */
2918         path = btrfs_alloc_path();
2919         if (!path) {
2920                 ret = -ENOMEM;
2921                 goto error;
2922         }
2923
2924         /* zero out stat counters */
2925         spin_lock(&fs_info->balance_lock);
2926         memset(&bctl->stat, 0, sizeof(bctl->stat));
2927         spin_unlock(&fs_info->balance_lock);
2928 again:
2929         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2930         key.offset = (u64)-1;
2931         key.type = BTRFS_CHUNK_ITEM_KEY;
2932
2933         while (1) {
2934                 if ((!counting && atomic_read(&fs_info->balance_pause_req)) ||
2935                     atomic_read(&fs_info->balance_cancel_req)) {
2936                         ret = -ECANCELED;
2937                         goto error;
2938                 }
2939
2940                 ret = btrfs_search_slot(NULL, chunk_root, &key, path, 0, 0);
2941                 if (ret < 0)
2942                         goto error;
2943
2944                 /*
2945                  * this shouldn't happen, it means the last relocate
2946                  * failed
2947                  */
2948                 if (ret == 0)
2949                         BUG(); /* FIXME break ? */
2950
2951                 ret = btrfs_previous_item(chunk_root, path, 0,
2952                                           BTRFS_CHUNK_ITEM_KEY);
2953                 if (ret) {
2954                         ret = 0;
2955                         break;
2956                 }
2957
2958                 leaf = path->nodes[0];
2959                 slot = path->slots[0];
2960                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
2961
2962                 if (found_key.objectid != key.objectid)
2963                         break;
2964
2965                 /* chunk zero is special */
2966                 if (found_key.offset == 0)
2967                         break;
2968
2969                 chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
2970
2971                 if (!counting) {
2972                         spin_lock(&fs_info->balance_lock);
2973                         bctl->stat.considered++;
2974                         spin_unlock(&fs_info->balance_lock);
2975                 }
2976
2977                 ret = should_balance_chunk(chunk_root, leaf, chunk,
2978                                            found_key.offset);
2979                 btrfs_release_path(path);
2980                 if (!ret)
2981                         goto loop;
2982
2983                 if (counting) {
2984                         spin_lock(&fs_info->balance_lock);
2985                         bctl->stat.expected++;
2986                         spin_unlock(&fs_info->balance_lock);
2987                         goto loop;
2988                 }
2989
2990                 ret = btrfs_relocate_chunk(chunk_root,
2991                                            chunk_root->root_key.objectid,
2992                                            found_key.objectid,
2993                                            found_key.offset);
2994                 if (ret && ret != -ENOSPC)
2995                         goto error;
2996                 if (ret == -ENOSPC) {
2997                         enospc_errors++;
2998                 } else {
2999                         spin_lock(&fs_info->balance_lock);
3000                         bctl->stat.completed++;
3001                         spin_unlock(&fs_info->balance_lock);
3002                 }
3003 loop:
3004                 key.offset = found_key.offset - 1;
3005         }
3006
3007         if (counting) {
3008                 btrfs_release_path(path);
3009                 counting = false;
3010                 goto again;
3011         }
3012 error:
3013         btrfs_free_path(path);
3014         if (enospc_errors) {
3015                 printk(KERN_INFO "btrfs: %d enospc errors during balance\n",
3016                        enospc_errors);
3017                 if (!ret)
3018                         ret = -ENOSPC;
3019         }
3020
3021         return ret;
3022 }
3023
3024 /**
3025  * alloc_profile_is_valid - see if a given profile is valid and reduced
3026  * @flags: profile to validate
3027  * @extended: if true @flags is treated as an extended profile
3028  */
3029 static int alloc_profile_is_valid(u64 flags, int extended)
3030 {
3031         u64 mask = (extended ? BTRFS_EXTENDED_PROFILE_MASK :
3032                                BTRFS_BLOCK_GROUP_PROFILE_MASK);
3033
3034         flags &= ~BTRFS_BLOCK_GROUP_TYPE_MASK;
3035
3036         /* 1) check that all other bits are zeroed */
3037         if (flags & ~mask)
3038                 return 0;
3039
3040         /* 2) see if profile is reduced */
3041         if (flags == 0)
3042                 return !extended; /* "0" is valid for usual profiles */
3043
3044         /* true if exactly one bit set */
3045         return (flags & (flags - 1)) == 0;
3046 }
3047
3048 static inline int balance_need_close(struct btrfs_fs_info *fs_info)
3049 {
3050         /* cancel requested || normal exit path */
3051         return atomic_read(&fs_info->balance_cancel_req) ||
3052                 (atomic_read(&fs_info->balance_pause_req) == 0 &&
3053                  atomic_read(&fs_info->balance_cancel_req) == 0);
3054 }
3055
3056 static void __cancel_balance(struct btrfs_fs_info *fs_info)
3057 {
3058         int ret;
3059
3060         unset_balance_control(fs_info);
3061         ret = del_balance_item(fs_info->tree_root);
3062         if (ret)
3063                 btrfs_std_error(fs_info, ret);
3064
3065         atomic_set(&fs_info->mutually_exclusive_operation_running, 0);
3066 }
3067
3068 /*
3069  * Should be called with both balance and volume mutexes held
3070  */
3071 int btrfs_balance(struct btrfs_balance_control *bctl,
3072                   struct btrfs_ioctl_balance_args *bargs)
3073 {
3074         struct btrfs_fs_info *fs_info = bctl->fs_info;
3075         u64 allowed;
3076         int mixed = 0;
3077         int ret;
3078         u64 num_devices;
3079         unsigned seq;
3080
3081         if (btrfs_fs_closing(fs_info) ||
3082             atomic_read(&fs_info->balance_pause_req) ||
3083             atomic_read(&fs_info->balance_cancel_req)) {
3084                 ret = -EINVAL;
3085                 goto out;
3086         }
3087
3088         allowed = btrfs_super_incompat_flags(fs_info->super_copy);
3089         if (allowed & BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)
3090                 mixed = 1;
3091
3092         /*
3093          * In case of mixed groups both data and meta should be picked,
3094          * and identical options should be given for both of them.
3095          */
3096         allowed = BTRFS_BALANCE_DATA | BTRFS_BALANCE_METADATA;
3097         if (mixed && (bctl->flags & allowed)) {
3098                 if (!(bctl->flags & BTRFS_BALANCE_DATA) ||
3099                     !(bctl->flags & BTRFS_BALANCE_METADATA) ||
3100                     memcmp(&bctl->data, &bctl->meta, sizeof(bctl->data))) {
3101                         printk(KERN_ERR "btrfs: with mixed groups data and "
3102                                "metadata balance options must be the same\n");
3103                         ret = -EINVAL;
3104                         goto out;
3105                 }
3106         }
3107
3108         num_devices = fs_info->fs_devices->num_devices;
3109         btrfs_dev_replace_lock(&fs_info->dev_replace);
3110         if (btrfs_dev_replace_is_ongoing(&fs_info->dev_replace)) {
3111                 BUG_ON(num_devices < 1);
3112                 num_devices--;
3113         }
3114         btrfs_dev_replace_unlock(&fs_info->dev_replace);
3115         allowed = BTRFS_AVAIL_ALLOC_BIT_SINGLE;
3116         if (num_devices == 1)
3117                 allowed |= BTRFS_BLOCK_GROUP_DUP;
3118         else if (num_devices > 1)
3119                 allowed |= (BTRFS_BLOCK_GROUP_RAID0 | BTRFS_BLOCK_GROUP_RAID1);
3120         if (num_devices > 2)
3121                 allowed |= BTRFS_BLOCK_GROUP_RAID5;
3122         if (num_devices > 3)
3123                 allowed |= (BTRFS_BLOCK_GROUP_RAID10 |
3124                             BTRFS_BLOCK_GROUP_RAID6);
3125         if ((bctl->data.flags & BTRFS_BALANCE_ARGS_CONVERT) &&
3126             (!alloc_profile_is_valid(bctl->data.target, 1) ||
3127              (bctl->data.target & ~allowed))) {
3128                 printk(KERN_ERR "btrfs: unable to start balance with target "
3129                        "data profile %llu\n",
3130                        (unsigned long long)bctl->data.target);
3131                 ret = -EINVAL;
3132                 goto out;
3133         }
3134         if ((bctl->meta.flags & BTRFS_BALANCE_ARGS_CONVERT) &&
3135             (!alloc_profile_is_valid(bctl->meta.target, 1) ||
3136              (bctl->meta.target & ~allowed))) {
3137                 printk(KERN_ERR "btrfs: unable to start balance with target "
3138                        "metadata profile %llu\n",
3139                        (unsigned long long)bctl->meta.target);
3140                 ret = -EINVAL;
3141                 goto out;
3142         }
3143         if ((bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT) &&
3144             (!alloc_profile_is_valid(bctl->sys.target, 1) ||
3145              (bctl->sys.target & ~allowed))) {
3146                 printk(KERN_ERR "btrfs: unable to start balance with target "
3147                        "system profile %llu\n",
3148                        (unsigned long long)bctl->sys.target);
3149                 ret = -EINVAL;
3150                 goto out;
3151         }
3152
3153         /* allow dup'ed data chunks only in mixed mode */
3154         if (!mixed && (bctl->data.flags & BTRFS_BALANCE_ARGS_CONVERT) &&
3155             (bctl->data.target & BTRFS_BLOCK_GROUP_DUP)) {
3156                 printk(KERN_ERR "btrfs: dup for data is not allowed\n");
3157                 ret = -EINVAL;
3158                 goto out;
3159         }
3160
3161         /* allow to reduce meta or sys integrity only if force set */
3162         allowed = BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID1 |
3163                         BTRFS_BLOCK_GROUP_RAID10 |
3164                         BTRFS_BLOCK_GROUP_RAID5 |
3165                         BTRFS_BLOCK_GROUP_RAID6;
3166         do {
3167                 seq = read_seqbegin(&fs_info->profiles_lock);
3168
3169                 if (((bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT) &&
3170                      (fs_info->avail_system_alloc_bits & allowed) &&
3171                      !(bctl->sys.target & allowed)) ||
3172                     ((bctl->meta.flags & BTRFS_BALANCE_ARGS_CONVERT) &&
3173                      (fs_info->avail_metadata_alloc_bits & allowed) &&
3174                      !(bctl->meta.target & allowed))) {
3175                         if (bctl->flags & BTRFS_BALANCE_FORCE) {
3176                                 printk(KERN_INFO "btrfs: force reducing metadata "
3177                                        "integrity\n");
3178                         } else {
3179                                 printk(KERN_ERR "btrfs: balance will reduce metadata "
3180                                        "integrity, use force if you want this\n");
3181                                 ret = -EINVAL;
3182                                 goto out;
3183                         }
3184                 }
3185         } while (read_seqretry(&fs_info->profiles_lock, seq));
3186
3187         if (bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT) {
3188                 int num_tolerated_disk_barrier_failures;
3189                 u64 target = bctl->sys.target;
3190
3191                 num_tolerated_disk_barrier_failures =
3192                         btrfs_calc_num_tolerated_disk_barrier_failures(fs_info);
3193                 if (num_tolerated_disk_barrier_failures > 0 &&
3194                     (target &
3195                      (BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID0 |
3196                       BTRFS_AVAIL_ALLOC_BIT_SINGLE)))
3197                         num_tolerated_disk_barrier_failures = 0;
3198                 else if (num_tolerated_disk_barrier_failures > 1 &&
3199                          (target &
3200                           (BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10)))
3201                         num_tolerated_disk_barrier_failures = 1;
3202
3203                 fs_info->num_tolerated_disk_barrier_failures =
3204                         num_tolerated_disk_barrier_failures;
3205         }
3206
3207         ret = insert_balance_item(fs_info->tree_root, bctl);
3208         if (ret && ret != -EEXIST)
3209                 goto out;
3210
3211         if (!(bctl->flags & BTRFS_BALANCE_RESUME)) {
3212                 BUG_ON(ret == -EEXIST);
3213                 set_balance_control(bctl);
3214         } else {
3215                 BUG_ON(ret != -EEXIST);
3216                 spin_lock(&fs_info->balance_lock);
3217                 update_balance_args(bctl);
3218                 spin_unlock(&fs_info->balance_lock);
3219         }
3220
3221         atomic_inc(&fs_info->balance_running);
3222         mutex_unlock(&fs_info->balance_mutex);
3223
3224         ret = __btrfs_balance(fs_info);
3225
3226         mutex_lock(&fs_info->balance_mutex);
3227         atomic_dec(&fs_info->balance_running);
3228
3229         if (bctl->sys.flags & BTRFS_BALANCE_ARGS_CONVERT) {
3230                 fs_info->num_tolerated_disk_barrier_failures =
3231                         btrfs_calc_num_tolerated_disk_barrier_failures(fs_info);
3232         }
3233
3234         if (bargs) {
3235                 memset(bargs, 0, sizeof(*bargs));
3236                 update_ioctl_balance_args(fs_info, 0, bargs);
3237         }
3238
3239         if ((ret && ret != -ECANCELED && ret != -ENOSPC) ||
3240             balance_need_close(fs_info)) {
3241                 __cancel_balance(fs_info);
3242         }
3243
3244         wake_up(&fs_info->balance_wait_q);
3245
3246         return ret;
3247 out:
3248         if (bctl->flags & BTRFS_BALANCE_RESUME)
3249                 __cancel_balance(fs_info);
3250         else {
3251                 kfree(bctl);
3252                 atomic_set(&fs_info->mutually_exclusive_operation_running, 0);
3253         }
3254         return ret;
3255 }
3256
3257 static int balance_kthread(void *data)
3258 {
3259         struct btrfs_fs_info *fs_info = data;
3260         int ret = 0;
3261
3262         mutex_lock(&fs_info->volume_mutex);
3263         mutex_lock(&fs_info->balance_mutex);
3264
3265         if (fs_info->balance_ctl) {
3266                 printk(KERN_INFO "btrfs: continuing balance\n");
3267                 ret = btrfs_balance(fs_info->balance_ctl, NULL);
3268         }
3269
3270         mutex_unlock(&fs_info->balance_mutex);
3271         mutex_unlock(&fs_info->volume_mutex);
3272
3273         return ret;
3274 }
3275
3276 int btrfs_resume_balance_async(struct btrfs_fs_info *fs_info)
3277 {
3278         struct task_struct *tsk;
3279
3280         spin_lock(&fs_info->balance_lock);
3281         if (!fs_info->balance_ctl) {
3282                 spin_unlock(&fs_info->balance_lock);
3283                 return 0;
3284         }
3285         spin_unlock(&fs_info->balance_lock);
3286
3287         if (btrfs_test_opt(fs_info->tree_root, SKIP_BALANCE)) {
3288                 printk(KERN_INFO "btrfs: force skipping balance\n");
3289                 return 0;
3290         }
3291
3292         tsk = kthread_run(balance_kthread, fs_info, "btrfs-balance");
3293         return PTR_RET(tsk);
3294 }
3295
3296 int btrfs_recover_balance(struct btrfs_fs_info *fs_info)
3297 {
3298         struct btrfs_balance_control *bctl;
3299         struct btrfs_balance_item *item;
3300         struct btrfs_disk_balance_args disk_bargs;
3301         struct btrfs_path *path;
3302         struct extent_buffer *leaf;
3303         struct btrfs_key key;
3304         int ret;
3305
3306         path = btrfs_alloc_path();
3307         if (!path)
3308                 return -ENOMEM;
3309
3310         key.objectid = BTRFS_BALANCE_OBJECTID;
3311         key.type = BTRFS_BALANCE_ITEM_KEY;
3312         key.offset = 0;
3313
3314         ret = btrfs_search_slot(NULL, fs_info->tree_root, &key, path, 0, 0);
3315         if (ret < 0)
3316                 goto out;
3317         if (ret > 0) { /* ret = -ENOENT; */
3318                 ret = 0;
3319                 goto out;
3320         }
3321
3322         bctl = kzalloc(sizeof(*bctl), GFP_NOFS);
3323         if (!bctl) {
3324                 ret = -ENOMEM;
3325                 goto out;
3326         }
3327
3328         leaf = path->nodes[0];
3329         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_balance_item);
3330
3331         bctl->fs_info = fs_info;
3332         bctl->flags = btrfs_balance_flags(leaf, item);
3333         bctl->flags |= BTRFS_BALANCE_RESUME;
3334
3335         btrfs_balance_data(leaf, item, &disk_bargs);
3336         btrfs_disk_balance_args_to_cpu(&bctl->data, &disk_bargs);
3337         btrfs_balance_meta(leaf, item, &disk_bargs);
3338         btrfs_disk_balance_args_to_cpu(&bctl->meta, &disk_bargs);
3339         btrfs_balance_sys(leaf, item, &disk_bargs);
3340         btrfs_disk_balance_args_to_cpu(&bctl->sys, &disk_bargs);
3341
3342         WARN_ON(atomic_xchg(&fs_info->mutually_exclusive_operation_running, 1));
3343
3344         mutex_lock(&fs_info->volume_mutex);
3345         mutex_lock(&fs_info->balance_mutex);
3346
3347         set_balance_control(bctl);
3348
3349         mutex_unlock(&fs_info->balance_mutex);
3350         mutex_unlock(&fs_info->volume_mutex);
3351 out:
3352         btrfs_free_path(path);
3353         return ret;
3354 }
3355
3356 int btrfs_pause_balance(struct btrfs_fs_info *fs_info)
3357 {
3358         int ret = 0;
3359
3360         mutex_lock(&fs_info->balance_mutex);
3361         if (!fs_info->balance_ctl) {
3362                 mutex_unlock(&fs_info->balance_mutex);
3363                 return -ENOTCONN;
3364         }
3365
3366         if (atomic_read(&fs_info->balance_running)) {
3367                 atomic_inc(&fs_info->balance_pause_req);
3368                 mutex_unlock(&fs_info->balance_mutex);
3369
3370                 wait_event(fs_info->balance_wait_q,
3371                            atomic_read(&fs_info->balance_running) == 0);
3372
3373                 mutex_lock(&fs_info->balance_mutex);
3374                 /* we are good with balance_ctl ripped off from under us */
3375                 BUG_ON(atomic_read(&fs_info->balance_running));
3376                 atomic_dec(&fs_info->balance_pause_req);
3377         } else {
3378                 ret = -ENOTCONN;
3379         }
3380
3381         mutex_unlock(&fs_info->balance_mutex);
3382         return ret;
3383 }
3384
3385 int btrfs_cancel_balance(struct btrfs_fs_info *fs_info)
3386 {
3387         mutex_lock(&fs_info->balance_mutex);
3388         if (!fs_info->balance_ctl) {
3389                 mutex_unlock(&fs_info->balance_mutex);
3390                 return -ENOTCONN;
3391         }
3392
3393         atomic_inc(&fs_info->balance_cancel_req);
3394         /*
3395          * if we are running just wait and return, balance item is
3396          * deleted in btrfs_balance in this case
3397          */
3398         if (atomic_read(&fs_info->balance_running)) {
3399                 mutex_unlock(&fs_info->balance_mutex);
3400                 wait_event(fs_info->balance_wait_q,
3401                            atomic_read(&fs_info->balance_running) == 0);
3402                 mutex_lock(&fs_info->balance_mutex);
3403         } else {
3404                 /* __cancel_balance needs volume_mutex */
3405                 mutex_unlock(&fs_info->balance_mutex);
3406                 mutex_lock(&fs_info->volume_mutex);
3407                 mutex_lock(&fs_info->balance_mutex);
3408
3409                 if (fs_info->balance_ctl)
3410                         __cancel_balance(fs_info);
3411
3412                 mutex_unlock(&fs_info->volume_mutex);
3413         }
3414
3415         BUG_ON(fs_info->balance_ctl || atomic_read(&fs_info->balance_running));
3416         atomic_dec(&fs_info->balance_cancel_req);
3417         mutex_unlock(&fs_info->balance_mutex);
3418         return 0;
3419 }
3420
3421 static int btrfs_uuid_scan_kthread(void *data)
3422 {
3423         struct btrfs_fs_info *fs_info = data;
3424         struct btrfs_root *root = fs_info->tree_root;
3425         struct btrfs_key key;
3426         struct btrfs_key max_key;
3427         struct btrfs_path *path = NULL;
3428         int ret = 0;
3429         struct extent_buffer *eb;
3430         int slot;
3431         struct btrfs_root_item root_item;
3432         u32 item_size;
3433         struct btrfs_trans_handle *trans;
3434
3435         path = btrfs_alloc_path();
3436         if (!path) {
3437                 ret = -ENOMEM;
3438                 goto out;
3439         }
3440
3441         key.objectid = 0;
3442         key.type = BTRFS_ROOT_ITEM_KEY;
3443         key.offset = 0;
3444
3445         max_key.objectid = (u64)-1;
3446         max_key.type = BTRFS_ROOT_ITEM_KEY;
3447         max_key.offset = (u64)-1;
3448
3449         path->keep_locks = 1;
3450
3451         while (1) {
3452                 ret = btrfs_search_forward(root, &key, &max_key, path, 0);
3453                 if (ret) {
3454                         if (ret > 0)
3455                                 ret = 0;
3456                         break;
3457                 }
3458
3459                 if (key.type != BTRFS_ROOT_ITEM_KEY ||
3460                     (key.objectid < BTRFS_FIRST_FREE_OBJECTID &&
3461                      key.objectid != BTRFS_FS_TREE_OBJECTID) ||
3462                     key.objectid > BTRFS_LAST_FREE_OBJECTID)
3463                         goto skip;
3464
3465                 eb = path->nodes[0];
3466                 slot = path->slots[0];
3467                 item_size = btrfs_item_size_nr(eb, slot);
3468                 if (item_size < sizeof(root_item))
3469                         goto skip;
3470
3471                 trans = NULL;
3472                 read_extent_buffer(eb, &root_item,
3473                                    btrfs_item_ptr_offset(eb, slot),
3474                                    (int)sizeof(root_item));
3475                 if (btrfs_root_refs(&root_item) == 0)
3476                         goto skip;
3477                 if (!btrfs_is_empty_uuid(root_item.uuid)) {
3478                         /*
3479                          * 1 - subvol uuid item
3480                          * 1 - received_subvol uuid item
3481                          */
3482                         trans = btrfs_start_transaction(fs_info->uuid_root, 2);
3483                         if (IS_ERR(trans)) {
3484                                 ret = PTR_ERR(trans);
3485                                 break;
3486                         }
3487                         ret = btrfs_uuid_tree_add(trans, fs_info->uuid_root,
3488                                                   root_item.uuid,
3489                                                   BTRFS_UUID_KEY_SUBVOL,
3490                                                   key.objectid);
3491                         if (ret < 0) {
3492                                 pr_warn("btrfs: uuid_tree_add failed %d\n",
3493                                         ret);
3494                                 btrfs_end_transaction(trans,
3495                                                       fs_info->uuid_root);
3496                                 break;
3497                         }
3498                 }
3499
3500                 if (!btrfs_is_empty_uuid(root_item.received_uuid)) {
3501                         if (!trans) {
3502                                 /* 1 - received_subvol uuid item */
3503                                 trans = btrfs_start_transaction(
3504                                                 fs_info->uuid_root, 1);
3505                                 if (IS_ERR(trans)) {
3506                                         ret = PTR_ERR(trans);
3507                                         break;
3508                                 }
3509                         }
3510                         ret = btrfs_uuid_tree_add(trans, fs_info->uuid_root,
3511                                                   root_item.received_uuid,
3512                                                  BTRFS_UUID_KEY_RECEIVED_SUBVOL,
3513                                                   key.objectid);
3514                         if (ret < 0) {
3515                                 pr_warn("btrfs: uuid_tree_add failed %d\n",
3516                                         ret);
3517                                 btrfs_end_transaction(trans,
3518                                                       fs_info->uuid_root);
3519                                 break;
3520                         }
3521                 }
3522
3523                 if (trans) {
3524                         ret = btrfs_end_transaction(trans, fs_info->uuid_root);
3525                         if (ret)
3526                                 break;
3527                 }
3528
3529 skip:
3530                 btrfs_release_path(path);
3531                 if (key.offset < (u64)-1) {
3532                         key.offset++;
3533                 } else if (key.type < BTRFS_ROOT_ITEM_KEY) {
3534                         key.offset = 0;
3535                         key.type = BTRFS_ROOT_ITEM_KEY;
3536                 } else if (key.objectid < (u64)-1) {
3537                         key.offset = 0;
3538                         key.type = BTRFS_ROOT_ITEM_KEY;
3539                         key.objectid++;
3540                 } else {
3541                         break;
3542                 }
3543                 cond_resched();
3544         }
3545
3546 out:
3547         btrfs_free_path(path);
3548         if (ret)
3549                 pr_warn("btrfs: btrfs_uuid_scan_kthread failed %d\n", ret);
3550         else
3551                 fs_info->update_uuid_tree_gen = 1;
3552         up(&fs_info->uuid_tree_rescan_sem);
3553         return 0;
3554 }
3555
3556 /*
3557  * Callback for btrfs_uuid_tree_iterate().
3558  * returns:
3559  * 0    check succeeded, the entry is not outdated.
3560  * < 0  if an error occured.
3561  * > 0  if the check failed, which means the caller shall remove the entry.
3562  */
3563 static int btrfs_check_uuid_tree_entry(struct btrfs_fs_info *fs_info,
3564                                        u8 *uuid, u8 type, u64 subid)
3565 {
3566         struct btrfs_key key;
3567         int ret = 0;
3568         struct btrfs_root *subvol_root;
3569
3570         if (type != BTRFS_UUID_KEY_SUBVOL &&
3571             type != BTRFS_UUID_KEY_RECEIVED_SUBVOL)
3572                 goto out;
3573
3574         key.objectid = subid;
3575         key.type = BTRFS_ROOT_ITEM_KEY;
3576         key.offset = (u64)-1;
3577         subvol_root = btrfs_read_fs_root_no_name(fs_info, &key);
3578         if (IS_ERR(subvol_root)) {
3579                 ret = PTR_ERR(subvol_root);
3580                 if (ret == -ENOENT)
3581                         ret = 1;
3582                 goto out;
3583         }
3584
3585         switch (type) {
3586         case BTRFS_UUID_KEY_SUBVOL:
3587                 if (memcmp(uuid, subvol_root->root_item.uuid, BTRFS_UUID_SIZE))
3588                         ret = 1;
3589                 break;
3590         case BTRFS_UUID_KEY_RECEIVED_SUBVOL:
3591                 if (memcmp(uuid, subvol_root->root_item.received_uuid,
3592                            BTRFS_UUID_SIZE))
3593                         ret = 1;
3594                 break;
3595         }
3596
3597 out:
3598         return ret;
3599 }
3600
3601 static int btrfs_uuid_rescan_kthread(void *data)
3602 {
3603         struct btrfs_fs_info *fs_info = (struct btrfs_fs_info *)data;
3604         int ret;
3605
3606         /*
3607          * 1st step is to iterate through the existing UUID tree and
3608          * to delete all entries that contain outdated data.
3609          * 2nd step is to add all missing entries to the UUID tree.
3610          */
3611         ret = btrfs_uuid_tree_iterate(fs_info, btrfs_check_uuid_tree_entry);
3612         if (ret < 0) {
3613                 pr_warn("btrfs: iterating uuid_tree failed %d\n", ret);
3614                 up(&fs_info->uuid_tree_rescan_sem);
3615                 return ret;
3616         }
3617         return btrfs_uuid_scan_kthread(data);
3618 }
3619
3620 int btrfs_create_uuid_tree(struct btrfs_fs_info *fs_info)
3621 {
3622         struct btrfs_trans_handle *trans;
3623         struct btrfs_root *tree_root = fs_info->tree_root;
3624         struct btrfs_root *uuid_root;
3625         struct task_struct *task;
3626         int ret;
3627
3628         /*
3629          * 1 - root node
3630          * 1 - root item
3631          */
3632         trans = btrfs_start_transaction(tree_root, 2);
3633         if (IS_ERR(trans))
3634                 return PTR_ERR(trans);
3635
3636         uuid_root = btrfs_create_tree(trans, fs_info,
3637                                       BTRFS_UUID_TREE_OBJECTID);
3638         if (IS_ERR(uuid_root)) {
3639                 btrfs_abort_transaction(trans, tree_root,
3640                                         PTR_ERR(uuid_root));
3641                 return PTR_ERR(uuid_root);
3642         }
3643
3644         fs_info->uuid_root = uuid_root;
3645
3646         ret = btrfs_commit_transaction(trans, tree_root);
3647         if (ret)
3648                 return ret;
3649
3650         down(&fs_info->uuid_tree_rescan_sem);
3651         task = kthread_run(btrfs_uuid_scan_kthread, fs_info, "btrfs-uuid");
3652         if (IS_ERR(task)) {
3653                 /* fs_info->update_uuid_tree_gen remains 0 in all error case */
3654                 pr_warn("btrfs: failed to start uuid_scan task\n");
3655                 up(&fs_info->uuid_tree_rescan_sem);
3656                 return PTR_ERR(task);
3657         }
3658
3659         return 0;
3660 }
3661
3662 int btrfs_check_uuid_tree(struct btrfs_fs_info *fs_info)
3663 {
3664         struct task_struct *task;
3665
3666         down(&fs_info->uuid_tree_rescan_sem);
3667         task = kthread_run(btrfs_uuid_rescan_kthread, fs_info, "btrfs-uuid");
3668         if (IS_ERR(task)) {
3669                 /* fs_info->update_uuid_tree_gen remains 0 in all error case */
3670                 pr_warn("btrfs: failed to start uuid_rescan task\n");
3671                 up(&fs_info->uuid_tree_rescan_sem);
3672                 return PTR_ERR(task);
3673         }
3674
3675         return 0;
3676 }
3677
3678 /*
3679  * shrinking a device means finding all of the device extents past
3680  * the new size, and then following the back refs to the chunks.
3681  * The chunk relocation code actually frees the device extent
3682  */
3683 int btrfs_shrink_device(struct btrfs_device *device, u64 new_size)
3684 {
3685         struct btrfs_trans_handle *trans;
3686         struct btrfs_root *root = device->dev_root;
3687         struct btrfs_dev_extent *dev_extent = NULL;
3688         struct btrfs_path *path;
3689         u64 length;
3690         u64 chunk_tree;
3691         u64 chunk_objectid;
3692         u64 chunk_offset;
3693         int ret;
3694         int slot;
3695         int failed = 0;
3696         bool retried = false;
3697         struct extent_buffer *l;
3698         struct btrfs_key key;
3699         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
3700         u64 old_total = btrfs_super_total_bytes(super_copy);
3701         u64 old_size = device->total_bytes;
3702         u64 diff = device->total_bytes - new_size;
3703
3704         if (device->is_tgtdev_for_dev_replace)
3705                 return -EINVAL;
3706
3707         path = btrfs_alloc_path();
3708         if (!path)
3709                 return -ENOMEM;
3710
3711         path->reada = 2;
3712
3713         lock_chunks(root);
3714
3715         device->total_bytes = new_size;
3716         if (device->writeable) {
3717                 device->fs_devices->total_rw_bytes -= diff;
3718                 spin_lock(&root->fs_info->free_chunk_lock);
3719                 root->fs_info->free_chunk_space -= diff;
3720                 spin_unlock(&root->fs_info->free_chunk_lock);
3721         }
3722         unlock_chunks(root);
3723
3724 again:
3725         key.objectid = device->devid;
3726         key.offset = (u64)-1;
3727         key.type = BTRFS_DEV_EXTENT_KEY;
3728
3729         do {
3730                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3731                 if (ret < 0)
3732                         goto done;
3733
3734                 ret = btrfs_previous_item(root, path, 0, key.type);
3735                 if (ret < 0)
3736                         goto done;
3737                 if (ret) {
3738                         ret = 0;
3739                         btrfs_release_path(path);
3740                         break;
3741                 }
3742
3743                 l = path->nodes[0];
3744                 slot = path->slots[0];
3745                 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
3746
3747                 if (key.objectid != device->devid) {
3748                         btrfs_release_path(path);
3749                         break;
3750                 }
3751
3752                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
3753                 length = btrfs_dev_extent_length(l, dev_extent);
3754
3755                 if (key.offset + length <= new_size) {
3756                         btrfs_release_path(path);
3757                         break;
3758                 }
3759
3760                 chunk_tree = btrfs_dev_extent_chunk_tree(l, dev_extent);
3761                 chunk_objectid = btrfs_dev_extent_chunk_objectid(l, dev_extent);
3762                 chunk_offset = btrfs_dev_extent_chunk_offset(l, dev_extent);
3763                 btrfs_release_path(path);
3764
3765                 ret = btrfs_relocate_chunk(root, chunk_tree, chunk_objectid,
3766                                            chunk_offset);
3767                 if (ret && ret != -ENOSPC)
3768                         goto done;
3769                 if (ret == -ENOSPC)
3770                         failed++;
3771         } while (key.offset-- > 0);
3772
3773         if (failed && !retried) {
3774                 failed = 0;
3775                 retried = true;
3776                 goto again;
3777         } else if (failed && retried) {
3778                 ret = -ENOSPC;
3779                 lock_chunks(root);
3780
3781                 device->total_bytes = old_size;
3782                 if (device->writeable)
3783                         device->fs_devices->total_rw_bytes += diff;
3784                 spin_lock(&root->fs_info->free_chunk_lock);
3785                 root->fs_info->free_chunk_space += diff;
3786                 spin_unlock(&root->fs_info->free_chunk_lock);
3787                 unlock_chunks(root);
3788                 goto done;
3789         }
3790
3791         /* Shrinking succeeded, else we would be at "done". */
3792         trans = btrfs_start_transaction(root, 0);
3793         if (IS_ERR(trans)) {
3794                 ret = PTR_ERR(trans);
3795                 goto done;
3796         }
3797
3798         lock_chunks(root);
3799
3800         device->disk_total_bytes = new_size;
3801         /* Now btrfs_update_device() will change the on-disk size. */
3802         ret = btrfs_update_device(trans, device);
3803         if (ret) {
3804                 unlock_chunks(root);
3805                 btrfs_end_transaction(trans, root);
3806                 goto done;
3807         }
3808         WARN_ON(diff > old_total);
3809         btrfs_set_super_total_bytes(super_copy, old_total - diff);
3810         unlock_chunks(root);
3811         btrfs_end_transaction(trans, root);
3812 done:
3813         btrfs_free_path(path);
3814         return ret;
3815 }
3816
3817 static int btrfs_add_system_chunk(struct btrfs_root *root,
3818                            struct btrfs_key *key,
3819                            struct btrfs_chunk *chunk, int item_size)
3820 {
3821         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
3822         struct btrfs_disk_key disk_key;
3823         u32 array_size;
3824         u8 *ptr;
3825
3826         array_size = btrfs_super_sys_array_size(super_copy);
3827         if (array_size + item_size > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE)
3828                 return -EFBIG;
3829
3830         ptr = super_copy->sys_chunk_array + array_size;
3831         btrfs_cpu_key_to_disk(&disk_key, key);
3832         memcpy(ptr, &disk_key, sizeof(disk_key));
3833         ptr += sizeof(disk_key);
3834         memcpy(ptr, chunk, item_size);
3835         item_size += sizeof(disk_key);
3836         btrfs_set_super_sys_array_size(super_copy, array_size + item_size);
3837         return 0;
3838 }
3839
3840 /*
3841  * sort the devices in descending order by max_avail, total_avail
3842  */
3843 static int btrfs_cmp_device_info(const void *a, const void *b)
3844 {
3845         const struct btrfs_device_info *di_a = a;
3846         const struct btrfs_device_info *di_b = b;
3847
3848         if (di_a->max_avail > di_b->max_avail)
3849                 return -1;
3850         if (di_a->max_avail < di_b->max_avail)
3851                 return 1;
3852         if (di_a->total_avail > di_b->total_avail)
3853                 return -1;
3854         if (di_a->total_avail < di_b->total_avail)
3855                 return 1;
3856         return 0;
3857 }
3858
3859 static struct btrfs_raid_attr btrfs_raid_array[BTRFS_NR_RAID_TYPES] = {
3860         [BTRFS_RAID_RAID10] = {
3861                 .sub_stripes    = 2,
3862                 .dev_stripes    = 1,
3863                 .devs_max       = 0,    /* 0 == as many as possible */
3864                 .devs_min       = 4,
3865                 .devs_increment = 2,
3866                 .ncopies        = 2,
3867         },
3868         [BTRFS_RAID_RAID1] = {
3869                 .sub_stripes    = 1,
3870                 .dev_stripes    = 1,
3871                 .devs_max       = 2,
3872                 .devs_min       = 2,
3873                 .devs_increment = 2,
3874                 .ncopies        = 2,
3875         },
3876         [BTRFS_RAID_DUP] = {
3877                 .sub_stripes    = 1,
3878                 .dev_stripes    = 2,
3879                 .devs_max       = 1,
3880                 .devs_min       = 1,
3881                 .devs_increment = 1,
3882                 .ncopies        = 2,
3883         },
3884         [BTRFS_RAID_RAID0] = {
3885                 .sub_stripes    = 1,
3886                 .dev_stripes    = 1,
3887                 .devs_max       = 0,
3888                 .devs_min       = 2,
3889                 .devs_increment = 1,
3890                 .ncopies        = 1,
3891         },
3892         [BTRFS_RAID_SINGLE] = {
3893                 .sub_stripes    = 1,
3894                 .dev_stripes    = 1,
3895                 .devs_max       = 1,
3896                 .devs_min       = 1,
3897                 .devs_increment = 1,
3898                 .ncopies        = 1,
3899         },
3900         [BTRFS_RAID_RAID5] = {
3901                 .sub_stripes    = 1,
3902                 .dev_stripes    = 1,
3903                 .devs_max       = 0,
3904                 .devs_min       = 2,
3905                 .devs_increment = 1,
3906                 .ncopies        = 2,
3907         },
3908         [BTRFS_RAID_RAID6] = {
3909                 .sub_stripes    = 1,
3910                 .dev_stripes    = 1,
3911                 .devs_max       = 0,
3912                 .devs_min       = 3,
3913                 .devs_increment = 1,
3914                 .ncopies        = 3,
3915         },
3916 };
3917
3918 static u32 find_raid56_stripe_len(u32 data_devices, u32 dev_stripe_target)
3919 {
3920         /* TODO allow them to set a preferred stripe size */
3921         return 64 * 1024;
3922 }
3923
3924 static void check_raid56_incompat_flag(struct btrfs_fs_info *info, u64 type)
3925 {
3926         if (!(type & (BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6)))
3927                 return;
3928
3929         btrfs_set_fs_incompat(info, RAID56);
3930 }
3931
3932 static int __btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
3933                                struct btrfs_root *extent_root, u64 start,
3934                                u64 type)
3935 {
3936         struct btrfs_fs_info *info = extent_root->fs_info;
3937         struct btrfs_fs_devices *fs_devices = info->fs_devices;
3938         struct list_head *cur;
3939         struct map_lookup *map = NULL;
3940         struct extent_map_tree *em_tree;
3941         struct extent_map *em;
3942         struct btrfs_device_info *devices_info = NULL;
3943         u64 total_avail;
3944         int num_stripes;        /* total number of stripes to allocate */
3945         int data_stripes;       /* number of stripes that count for
3946                                    block group size */
3947         int sub_stripes;        /* sub_stripes info for map */
3948         int dev_stripes;        /* stripes per dev */
3949         int devs_max;           /* max devs to use */
3950         int devs_min;           /* min devs needed */
3951         int devs_increment;     /* ndevs has to be a multiple of this */
3952         int ncopies;            /* how many copies to data has */
3953         int ret;
3954         u64 max_stripe_size;
3955         u64 max_chunk_size;
3956         u64 stripe_size;
3957         u64 num_bytes;
3958         u64 raid_stripe_len = BTRFS_STRIPE_LEN;
3959         int ndevs;
3960         int i;
3961         int j;
3962         int index;
3963
3964         BUG_ON(!alloc_profile_is_valid(type, 0));
3965
3966         if (list_empty(&fs_devices->alloc_list))
3967                 return -ENOSPC;
3968
3969         index = __get_raid_index(type);
3970
3971         sub_stripes = btrfs_raid_array[index].sub_stripes;
3972         dev_stripes = btrfs_raid_array[index].dev_stripes;
3973         devs_max = btrfs_raid_array[index].devs_max;
3974         devs_min = btrfs_raid_array[index].devs_min;
3975         devs_increment = btrfs_raid_array[index].devs_increment;
3976         ncopies = btrfs_raid_array[index].ncopies;
3977
3978         if (type & BTRFS_BLOCK_GROUP_DATA) {
3979                 max_stripe_size = 1024 * 1024 * 1024;
3980                 max_chunk_size = 10 * max_stripe_size;
3981         } else if (type & BTRFS_BLOCK_GROUP_METADATA) {
3982                 /* for larger filesystems, use larger metadata chunks */
3983                 if (fs_devices->total_rw_bytes > 50ULL * 1024 * 1024 * 1024)
3984                         max_stripe_size = 1024 * 1024 * 1024;
3985                 else
3986                         max_stripe_size = 256 * 1024 * 1024;
3987                 max_chunk_size = max_stripe_size;
3988         } else if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
3989                 max_stripe_size = 32 * 1024 * 1024;
3990                 max_chunk_size = 2 * max_stripe_size;
3991         } else {
3992                 printk(KERN_ERR "btrfs: invalid chunk type 0x%llx requested\n",
3993                        type);
3994                 BUG_ON(1);
3995         }
3996
3997         /* we don't want a chunk larger than 10% of writeable space */
3998         max_chunk_size = min(div_factor(fs_devices->total_rw_bytes, 1),
3999                              max_chunk_size);
4000
4001         devices_info = kzalloc(sizeof(*devices_info) * fs_devices->rw_devices,
4002                                GFP_NOFS);
4003         if (!devices_info)
4004                 return -ENOMEM;
4005
4006         cur = fs_devices->alloc_list.next;
4007
4008         /*
4009          * in the first pass through the devices list, we gather information
4010          * about the available holes on each device.
4011          */
4012         ndevs = 0;
4013         while (cur != &fs_devices->alloc_list) {
4014                 struct btrfs_device *device;
4015                 u64 max_avail;
4016                 u64 dev_offset;
4017
4018                 device = list_entry(cur, struct btrfs_device, dev_alloc_list);
4019
4020                 cur = cur->next;
4021
4022                 if (!device->writeable) {
4023                         WARN(1, KERN_ERR
4024                                "btrfs: read-only device in alloc_list\n");
4025                         continue;
4026                 }
4027
4028                 if (!device->in_fs_metadata ||
4029                     device->is_tgtdev_for_dev_replace)
4030                         continue;
4031
4032                 if (device->total_bytes > device->bytes_used)
4033                         total_avail = device->total_bytes - device->bytes_used;
4034                 else
4035                         total_avail = 0;
4036
4037                 /* If there is no space on this device, skip it. */
4038                 if (total_avail == 0)
4039                         continue;
4040
4041                 ret = find_free_dev_extent(trans, device,
4042                                            max_stripe_size * dev_stripes,
4043                                            &dev_offset, &max_avail);
4044                 if (ret && ret != -ENOSPC)
4045                         goto error;
4046
4047                 if (ret == 0)
4048                         max_avail = max_stripe_size * dev_stripes;
4049
4050                 if (max_avail < BTRFS_STRIPE_LEN * dev_stripes)
4051                         continue;
4052
4053                 if (ndevs == fs_devices->rw_devices) {
4054                         WARN(1, "%s: found more than %llu devices\n",
4055                              __func__, fs_devices->rw_devices);
4056                         break;
4057                 }
4058                 devices_info[ndevs].dev_offset = dev_offset;
4059                 devices_info[ndevs].max_avail = max_avail;
4060                 devices_info[ndevs].total_avail = total_avail;
4061                 devices_info[ndevs].dev = device;
4062                 ++ndevs;
4063         }
4064
4065         /*
4066          * now sort the devices by hole size / available space
4067          */
4068         sort(devices_info, ndevs, sizeof(struct btrfs_device_info),
4069              btrfs_cmp_device_info, NULL);
4070
4071         /* round down to number of usable stripes */
4072         ndevs -= ndevs % devs_increment;
4073
4074         if (ndevs < devs_increment * sub_stripes || ndevs < devs_min) {
4075                 ret = -ENOSPC;
4076                 goto error;
4077         }
4078
4079         if (devs_max && ndevs > devs_max)
4080                 ndevs = devs_max;
4081         /*
4082          * the primary goal is to maximize the number of stripes, so use as many
4083          * devices as possible, even if the stripes are not maximum sized.
4084          */
4085         stripe_size = devices_info[ndevs-1].max_avail;
4086         num_stripes = ndevs * dev_stripes;
4087
4088         /*
4089          * this will have to be fixed for RAID1 and RAID10 over
4090          * more drives
4091          */
4092         data_stripes = num_stripes / ncopies;
4093
4094         if (type & BTRFS_BLOCK_GROUP_RAID5) {
4095                 raid_stripe_len = find_raid56_stripe_len(ndevs - 1,
4096                                  btrfs_super_stripesize(info->super_copy));
4097                 data_stripes = num_stripes - 1;
4098         }
4099         if (type & BTRFS_BLOCK_GROUP_RAID6) {
4100                 raid_stripe_len = find_raid56_stripe_len(ndevs - 2,
4101                                  btrfs_super_stripesize(info->super_copy));
4102                 data_stripes = num_stripes - 2;
4103         }
4104
4105         /*
4106          * Use the number of data stripes to figure out how big this chunk
4107          * is really going to be in terms of logical address space,
4108          * and compare that answer with the max chunk size
4109          */
4110         if (stripe_size * data_stripes > max_chunk_size) {
4111                 u64 mask = (1ULL << 24) - 1;
4112                 stripe_size = max_chunk_size;
4113                 do_div(stripe_size, data_stripes);
4114
4115                 /* bump the answer up to a 16MB boundary */
4116                 stripe_size = (stripe_size + mask) & ~mask;
4117
4118                 /* but don't go higher than the limits we found
4119                  * while searching for free extents
4120                  */
4121                 if (stripe_size > devices_info[ndevs-1].max_avail)
4122                         stripe_size = devices_info[ndevs-1].max_avail;
4123         }
4124
4125         do_div(stripe_size, dev_stripes);
4126
4127         /* align to BTRFS_STRIPE_LEN */
4128         do_div(stripe_size, raid_stripe_len);
4129         stripe_size *= raid_stripe_len;
4130
4131         map = kmalloc(map_lookup_size(num_stripes), GFP_NOFS);
4132         if (!map) {
4133                 ret = -ENOMEM;
4134                 goto error;
4135         }
4136         map->num_stripes = num_stripes;
4137
4138         for (i = 0; i < ndevs; ++i) {
4139                 for (j = 0; j < dev_stripes; ++j) {
4140                         int s = i * dev_stripes + j;
4141                         map->stripes[s].dev = devices_info[i].dev;
4142                         map->stripes[s].physical = devices_info[i].dev_offset +
4143                                                    j * stripe_size;
4144                 }
4145         }
4146         map->sector_size = extent_root->sectorsize;
4147         map->stripe_len = raid_stripe_len;
4148         map->io_align = raid_stripe_len;
4149         map->io_width = raid_stripe_len;
4150         map->type = type;
4151         map->sub_stripes = sub_stripes;
4152
4153         num_bytes = stripe_size * data_stripes;
4154
4155         trace_btrfs_chunk_alloc(info->chunk_root, map, start, num_bytes);
4156
4157         em = alloc_extent_map();
4158         if (!em) {
4159                 ret = -ENOMEM;
4160                 goto error;
4161         }
4162         em->bdev = (struct block_device *)map;
4163         em->start = start;
4164         em->len = num_bytes;
4165         em->block_start = 0;
4166         em->block_len = em->len;
4167         em->orig_block_len = stripe_size;
4168
4169         em_tree = &extent_root->fs_info->mapping_tree.map_tree;
4170         write_lock(&em_tree->lock);
4171         ret = add_extent_mapping(em_tree, em, 0);
4172         if (!ret) {
4173                 list_add_tail(&em->list, &trans->transaction->pending_chunks);
4174                 atomic_inc(&em->refs);
4175         }
4176         write_unlock(&em_tree->lock);
4177         if (ret) {
4178                 free_extent_map(em);
4179                 goto error;
4180         }
4181
4182         ret = btrfs_make_block_group(trans, extent_root, 0, type,
4183                                      BTRFS_FIRST_CHUNK_TREE_OBJECTID,
4184                                      start, num_bytes);
4185         if (ret)
4186                 goto error_del_extent;
4187
4188         free_extent_map(em);
4189         check_raid56_incompat_flag(extent_root->fs_info, type);
4190
4191         kfree(devices_info);
4192         return 0;
4193
4194 error_del_extent:
4195         write_lock(&em_tree->lock);
4196         remove_extent_mapping(em_tree, em);
4197         write_unlock(&em_tree->lock);
4198
4199         /* One for our allocation */
4200         free_extent_map(em);
4201         /* One for the tree reference */
4202         free_extent_map(em);
4203 error:
4204         kfree(map);
4205         kfree(devices_info);
4206         return ret;
4207 }
4208
4209 int btrfs_finish_chunk_alloc(struct btrfs_trans_handle *trans,
4210                                 struct btrfs_root *extent_root,
4211                                 u64 chunk_offset, u64 chunk_size)
4212 {
4213         struct btrfs_key key;
4214         struct btrfs_root *chunk_root = extent_root->fs_info->chunk_root;
4215         struct btrfs_device *device;
4216         struct btrfs_chunk *chunk;
4217         struct btrfs_stripe *stripe;
4218         struct extent_map_tree *em_tree;
4219         struct extent_map *em;
4220         struct map_lookup *map;
4221         size_t item_size;
4222         u64 dev_offset;
4223         u64 stripe_size;
4224         int i = 0;
4225         int ret;
4226
4227         em_tree = &extent_root->fs_info->mapping_tree.map_tree;
4228         read_lock(&em_tree->lock);
4229         em = lookup_extent_mapping(em_tree, chunk_offset, chunk_size);
4230         read_unlock(&em_tree->lock);
4231
4232         if (!em) {
4233                 btrfs_crit(extent_root->fs_info, "unable to find logical "
4234                            "%Lu len %Lu", chunk_offset, chunk_size);
4235                 return -EINVAL;
4236         }
4237
4238         if (em->start != chunk_offset || em->len != chunk_size) {
4239                 btrfs_crit(extent_root->fs_info, "found a bad mapping, wanted"
4240                           " %Lu-%Lu, found %Lu-%Lu\n", chunk_offset,
4241                           chunk_size, em->start, em->len);
4242                 free_extent_map(em);
4243                 return -EINVAL;
4244         }
4245
4246         map = (struct map_lookup *)em->bdev;
4247         item_size = btrfs_chunk_item_size(map->num_stripes);
4248         stripe_size = em->orig_block_len;
4249
4250         chunk = kzalloc(item_size, GFP_NOFS);
4251         if (!chunk) {
4252                 ret = -ENOMEM;
4253                 goto out;
4254         }
4255
4256         for (i = 0; i < map->num_stripes; i++) {
4257                 device = map->stripes[i].dev;
4258                 dev_offset = map->stripes[i].physical;
4259
4260                 device->bytes_used += stripe_size;
4261                 ret = btrfs_update_device(trans, device);
4262                 if (ret)
4263                         goto out;
4264                 ret = btrfs_alloc_dev_extent(trans, device,
4265                                              chunk_root->root_key.objectid,
4266                                              BTRFS_FIRST_CHUNK_TREE_OBJECTID,
4267                                              chunk_offset, dev_offset,
4268                                              stripe_size);
4269                 if (ret)
4270                         goto out;
4271         }
4272
4273         spin_lock(&extent_root->fs_info->free_chunk_lock);
4274         extent_root->fs_info->free_chunk_space -= (stripe_size *
4275                                                    map->num_stripes);
4276         spin_unlock(&extent_root->fs_info->free_chunk_lock);
4277
4278         stripe = &chunk->stripe;
4279         for (i = 0; i < map->num_stripes; i++) {
4280                 device = map->stripes[i].dev;
4281                 dev_offset = map->stripes[i].physical;
4282
4283                 btrfs_set_stack_stripe_devid(stripe, device->devid);
4284                 btrfs_set_stack_stripe_offset(stripe, dev_offset);
4285                 memcpy(stripe->dev_uuid, device->uuid, BTRFS_UUID_SIZE);
4286                 stripe++;
4287         }
4288
4289         btrfs_set_stack_chunk_length(chunk, chunk_size);
4290         btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
4291         btrfs_set_stack_chunk_stripe_len(chunk, map->stripe_len);
4292         btrfs_set_stack_chunk_type(chunk, map->type);
4293         btrfs_set_stack_chunk_num_stripes(chunk, map->num_stripes);
4294         btrfs_set_stack_chunk_io_align(chunk, map->stripe_len);
4295         btrfs_set_stack_chunk_io_width(chunk, map->stripe_len);
4296         btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
4297         btrfs_set_stack_chunk_sub_stripes(chunk, map->sub_stripes);
4298
4299         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
4300         key.type = BTRFS_CHUNK_ITEM_KEY;
4301         key.offset = chunk_offset;
4302
4303         ret = btrfs_insert_item(trans, chunk_root, &key, chunk, item_size);
4304         if (ret == 0 && map->type & BTRFS_BLOCK_GROUP_SYSTEM) {
4305                 /*
4306                  * TODO: Cleanup of inserted chunk root in case of
4307                  * failure.
4308                  */
4309                 ret = btrfs_add_system_chunk(chunk_root, &key, chunk,
4310                                              item_size);
4311         }
4312
4313 out:
4314         kfree(chunk);
4315         free_extent_map(em);
4316         return ret;
4317 }
4318
4319 /*
4320  * Chunk allocation falls into two parts. The first part does works
4321  * that make the new allocated chunk useable, but not do any operation
4322  * that modifies the chunk tree. The second part does the works that
4323  * require modifying the chunk tree. This division is important for the
4324  * bootstrap process of adding storage to a seed btrfs.
4325  */
4326 int btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
4327                       struct btrfs_root *extent_root, u64 type)
4328 {
4329         u64 chunk_offset;
4330
4331         chunk_offset = find_next_chunk(extent_root->fs_info);
4332         return __btrfs_alloc_chunk(trans, extent_root, chunk_offset, type);
4333 }
4334
4335 static noinline int init_first_rw_device(struct btrfs_trans_handle *trans,
4336                                          struct btrfs_root *root,
4337                                          struct btrfs_device *device)
4338 {
4339         u64 chunk_offset;
4340         u64 sys_chunk_offset;
4341         u64 alloc_profile;
4342         struct btrfs_fs_info *fs_info = root->fs_info;
4343         struct btrfs_root *extent_root = fs_info->extent_root;
4344         int ret;
4345
4346         chunk_offset = find_next_chunk(fs_info);
4347         alloc_profile = btrfs_get_alloc_profile(extent_root, 0);
4348         ret = __btrfs_alloc_chunk(trans, extent_root, chunk_offset,
4349                                   alloc_profile);
4350         if (ret)
4351                 return ret;
4352
4353         sys_chunk_offset = find_next_chunk(root->fs_info);
4354         alloc_profile = btrfs_get_alloc_profile(fs_info->chunk_root, 0);
4355         ret = __btrfs_alloc_chunk(trans, extent_root, sys_chunk_offset,
4356                                   alloc_profile);
4357         if (ret) {
4358                 btrfs_abort_transaction(trans, root, ret);
4359                 goto out;
4360         }
4361
4362         ret = btrfs_add_device(trans, fs_info->chunk_root, device);
4363         if (ret)
4364                 btrfs_abort_transaction(trans, root, ret);
4365 out:
4366         return ret;
4367 }
4368
4369 int btrfs_chunk_readonly(struct btrfs_root *root, u64 chunk_offset)
4370 {
4371         struct extent_map *em;
4372         struct map_lookup *map;
4373         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
4374         int readonly = 0;
4375         int i;
4376
4377         read_lock(&map_tree->map_tree.lock);
4378         em = lookup_extent_mapping(&map_tree->map_tree, chunk_offset, 1);
4379         read_unlock(&map_tree->map_tree.lock);
4380         if (!em)
4381                 return 1;
4382
4383         if (btrfs_test_opt(root, DEGRADED)) {
4384                 free_extent_map(em);
4385                 return 0;
4386         }
4387
4388         map = (struct map_lookup *)em->bdev;
4389         for (i = 0; i < map->num_stripes; i++) {
4390                 if (!map->stripes[i].dev->writeable) {
4391                         readonly = 1;
4392                         break;
4393                 }
4394         }
4395         free_extent_map(em);
4396         return readonly;
4397 }
4398
4399 void btrfs_mapping_init(struct btrfs_mapping_tree *tree)
4400 {
4401         extent_map_tree_init(&tree->map_tree);
4402 }
4403
4404 void btrfs_mapping_tree_free(struct btrfs_mapping_tree *tree)
4405 {
4406         struct extent_map *em;
4407
4408         while (1) {
4409                 write_lock(&tree->map_tree.lock);
4410                 em = lookup_extent_mapping(&tree->map_tree, 0, (u64)-1);
4411                 if (em)
4412                         remove_extent_mapping(&tree->map_tree, em);
4413                 write_unlock(&tree->map_tree.lock);
4414                 if (!em)
4415                         break;
4416                 kfree(em->bdev);
4417                 /* once for us */
4418                 free_extent_map(em);
4419                 /* once for the tree */
4420                 free_extent_map(em);
4421         }
4422 }
4423
4424 int btrfs_num_copies(struct btrfs_fs_info *fs_info, u64 logical, u64 len)
4425 {
4426         struct btrfs_mapping_tree *map_tree = &fs_info->mapping_tree;
4427         struct extent_map *em;
4428         struct map_lookup *map;
4429         struct extent_map_tree *em_tree = &map_tree->map_tree;
4430         int ret;
4431
4432         read_lock(&em_tree->lock);
4433         em = lookup_extent_mapping(em_tree, logical, len);
4434         read_unlock(&em_tree->lock);
4435
4436         /*
4437          * We could return errors for these cases, but that could get ugly and
4438          * we'd probably do the same thing which is just not do anything else
4439          * and exit, so return 1 so the callers don't try to use other copies.
4440          */
4441         if (!em) {
4442                 btrfs_crit(fs_info, "No mapping for %Lu-%Lu\n", logical,
4443                             logical+len);
4444                 return 1;
4445         }
4446
4447         if (em->start > logical || em->start + em->len < logical) {
4448                 btrfs_crit(fs_info, "Invalid mapping for %Lu-%Lu, got "
4449                             "%Lu-%Lu\n", logical, logical+len, em->start,
4450                             em->start + em->len);
4451                 return 1;
4452         }
4453
4454         map = (struct map_lookup *)em->bdev;
4455         if (map->type & (BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID1))
4456                 ret = map->num_stripes;
4457         else if (map->type & BTRFS_BLOCK_GROUP_RAID10)
4458                 ret = map->sub_stripes;
4459         else if (map->type & BTRFS_BLOCK_GROUP_RAID5)
4460                 ret = 2;
4461         else if (map->type & BTRFS_BLOCK_GROUP_RAID6)
4462                 ret = 3;
4463         else
4464                 ret = 1;
4465         free_extent_map(em);
4466
4467         btrfs_dev_replace_lock(&fs_info->dev_replace);
4468         if (btrfs_dev_replace_is_ongoing(&fs_info->dev_replace))
4469                 ret++;
4470         btrfs_dev_replace_unlock(&fs_info->dev_replace);
4471
4472         return ret;
4473 }
4474
4475 unsigned long btrfs_full_stripe_len(struct btrfs_root *root,
4476                                     struct btrfs_mapping_tree *map_tree,
4477                                     u64 logical)
4478 {
4479         struct extent_map *em;
4480         struct map_lookup *map;
4481         struct extent_map_tree *em_tree = &map_tree->map_tree;
4482         unsigned long len = root->sectorsize;
4483
4484         read_lock(&em_tree->lock);
4485         em = lookup_extent_mapping(em_tree, logical, len);
4486         read_unlock(&em_tree->lock);
4487         BUG_ON(!em);
4488
4489         BUG_ON(em->start > logical || em->start + em->len < logical);
4490         map = (struct map_lookup *)em->bdev;
4491         if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
4492                          BTRFS_BLOCK_GROUP_RAID6)) {
4493                 len = map->stripe_len * nr_data_stripes(map);
4494         }
4495         free_extent_map(em);
4496         return len;
4497 }
4498
4499 int btrfs_is_parity_mirror(struct btrfs_mapping_tree *map_tree,
4500                            u64 logical, u64 len, int mirror_num)
4501 {
4502         struct extent_map *em;
4503         struct map_lookup *map;
4504         struct extent_map_tree *em_tree = &map_tree->map_tree;
4505         int ret = 0;
4506
4507         read_lock(&em_tree->lock);
4508         em = lookup_extent_mapping(em_tree, logical, len);
4509         read_unlock(&em_tree->lock);
4510         BUG_ON(!em);
4511
4512         BUG_ON(em->start > logical || em->start + em->len < logical);
4513         map = (struct map_lookup *)em->bdev;
4514         if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
4515                          BTRFS_BLOCK_GROUP_RAID6))
4516                 ret = 1;
4517         free_extent_map(em);
4518         return ret;
4519 }
4520
4521 static int find_live_mirror(struct btrfs_fs_info *fs_info,
4522                             struct map_lookup *map, int first, int num,
4523                             int optimal, int dev_replace_is_ongoing)
4524 {
4525         int i;
4526         int tolerance;
4527         struct btrfs_device *srcdev;
4528
4529         if (dev_replace_is_ongoing &&
4530             fs_info->dev_replace.cont_reading_from_srcdev_mode ==
4531              BTRFS_DEV_REPLACE_ITEM_CONT_READING_FROM_SRCDEV_MODE_AVOID)
4532                 srcdev = fs_info->dev_replace.srcdev;
4533         else
4534                 srcdev = NULL;
4535
4536         /*
4537          * try to avoid the drive that is the source drive for a
4538          * dev-replace procedure, only choose it if no other non-missing
4539          * mirror is available
4540          */
4541         for (tolerance = 0; tolerance < 2; tolerance++) {
4542                 if (map->stripes[optimal].dev->bdev &&
4543                     (tolerance || map->stripes[optimal].dev != srcdev))
4544                         return optimal;
4545                 for (i = first; i < first + num; i++) {
4546                         if (map->stripes[i].dev->bdev &&
4547                             (tolerance || map->stripes[i].dev != srcdev))
4548                                 return i;
4549                 }
4550         }
4551
4552         /* we couldn't find one that doesn't fail.  Just return something
4553          * and the io error handling code will clean up eventually
4554          */
4555         return optimal;
4556 }
4557
4558 static inline int parity_smaller(u64 a, u64 b)
4559 {
4560         return a > b;
4561 }
4562
4563 /* Bubble-sort the stripe set to put the parity/syndrome stripes last */
4564 static void sort_parity_stripes(struct btrfs_bio *bbio, u64 *raid_map)
4565 {
4566         struct btrfs_bio_stripe s;
4567         int i;
4568         u64 l;
4569         int again = 1;
4570
4571         while (again) {
4572                 again = 0;
4573                 for (i = 0; i < bbio->num_stripes - 1; i++) {
4574                         if (parity_smaller(raid_map[i], raid_map[i+1])) {
4575                                 s = bbio->stripes[i];
4576                                 l = raid_map[i];
4577                                 bbio->stripes[i] = bbio->stripes[i+1];
4578                                 raid_map[i] = raid_map[i+1];
4579                                 bbio->stripes[i+1] = s;
4580                                 raid_map[i+1] = l;
4581                                 again = 1;
4582                         }
4583                 }
4584         }
4585 }
4586
4587 static int __btrfs_map_block(struct btrfs_fs_info *fs_info, int rw,
4588                              u64 logical, u64 *length,
4589                              struct btrfs_bio **bbio_ret,
4590                              int mirror_num, u64 **raid_map_ret)
4591 {
4592         struct extent_map *em;
4593         struct map_lookup *map;
4594         struct btrfs_mapping_tree *map_tree = &fs_info->mapping_tree;
4595         struct extent_map_tree *em_tree = &map_tree->map_tree;
4596         u64 offset;
4597         u64 stripe_offset;
4598         u64 stripe_end_offset;
4599         u64 stripe_nr;
4600         u64 stripe_nr_orig;
4601         u64 stripe_nr_end;
4602         u64 stripe_len;
4603         u64 *raid_map = NULL;
4604         int stripe_index;
4605         int i;
4606         int ret = 0;
4607         int num_stripes;
4608         int max_errors = 0;
4609         struct btrfs_bio *bbio = NULL;
4610         struct btrfs_dev_replace *dev_replace = &fs_info->dev_replace;
4611         int dev_replace_is_ongoing = 0;
4612         int num_alloc_stripes;
4613         int patch_the_first_stripe_for_dev_replace = 0;
4614         u64 physical_to_patch_in_first_stripe = 0;
4615         u64 raid56_full_stripe_start = (u64)-1;
4616
4617         read_lock(&em_tree->lock);
4618         em = lookup_extent_mapping(em_tree, logical, *length);
4619         read_unlock(&em_tree->lock);
4620
4621         if (!em) {
4622                 btrfs_crit(fs_info, "unable to find logical %llu len %llu",
4623                         (unsigned long long)logical,
4624                         (unsigned long long)*length);
4625                 return -EINVAL;
4626         }
4627
4628         if (em->start > logical || em->start + em->len < logical) {
4629                 btrfs_crit(fs_info, "found a bad mapping, wanted %Lu, "
4630                            "found %Lu-%Lu\n", logical, em->start,
4631                            em->start + em->len);
4632                 return -EINVAL;
4633         }
4634
4635         map = (struct map_lookup *)em->bdev;
4636         offset = logical - em->start;
4637
4638         stripe_len = map->stripe_len;
4639         stripe_nr = offset;
4640         /*
4641          * stripe_nr counts the total number of stripes we have to stride
4642          * to get to this block
4643          */
4644         do_div(stripe_nr, stripe_len);
4645
4646         stripe_offset = stripe_nr * stripe_len;
4647         BUG_ON(offset < stripe_offset);
4648
4649         /* stripe_offset is the offset of this block in its stripe*/
4650         stripe_offset = offset - stripe_offset;
4651
4652         /* if we're here for raid56, we need to know the stripe aligned start */
4653         if (map->type & (BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6)) {
4654                 unsigned long full_stripe_len = stripe_len * nr_data_stripes(map);
4655                 raid56_full_stripe_start = offset;
4656
4657                 /* allow a write of a full stripe, but make sure we don't
4658                  * allow straddling of stripes
4659                  */
4660                 do_div(raid56_full_stripe_start, full_stripe_len);
4661                 raid56_full_stripe_start *= full_stripe_len;
4662         }
4663
4664         if (rw & REQ_DISCARD) {
4665                 /* we don't discard raid56 yet */
4666                 if (map->type &
4667                     (BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6)) {
4668                         ret = -EOPNOTSUPP;
4669                         goto out;
4670                 }
4671                 *length = min_t(u64, em->len - offset, *length);
4672         } else if (map->type & BTRFS_BLOCK_GROUP_PROFILE_MASK) {
4673                 u64 max_len;
4674                 /* For writes to RAID[56], allow a full stripeset across all disks.
4675                    For other RAID types and for RAID[56] reads, just allow a single
4676                    stripe (on a single disk). */
4677                 if (map->type & (BTRFS_BLOCK_GROUP_RAID5 | BTRFS_BLOCK_GROUP_RAID6) &&
4678                     (rw & REQ_WRITE)) {
4679                         max_len = stripe_len * nr_data_stripes(map) -
4680                                 (offset - raid56_full_stripe_start);
4681                 } else {
4682                         /* we limit the length of each bio to what fits in a stripe */
4683                         max_len = stripe_len - stripe_offset;
4684                 }
4685                 *length = min_t(u64, em->len - offset, max_len);
4686         } else {
4687                 *length = em->len - offset;
4688         }
4689
4690         /* This is for when we're called from btrfs_merge_bio_hook() and all
4691            it cares about is the length */
4692         if (!bbio_ret)
4693                 goto out;
4694
4695         btrfs_dev_replace_lock(dev_replace);
4696         dev_replace_is_ongoing = btrfs_dev_replace_is_ongoing(dev_replace);
4697         if (!dev_replace_is_ongoing)
4698                 btrfs_dev_replace_unlock(dev_replace);
4699
4700         if (dev_replace_is_ongoing && mirror_num == map->num_stripes + 1 &&
4701             !(rw & (REQ_WRITE | REQ_DISCARD | REQ_GET_READ_MIRRORS)) &&
4702             dev_replace->tgtdev != NULL) {
4703                 /*
4704                  * in dev-replace case, for repair case (that's the only
4705                  * case where the mirror is selected explicitly when
4706                  * calling btrfs_map_block), blocks left of the left cursor
4707                  * can also be read from the target drive.
4708                  * For REQ_GET_READ_MIRRORS, the target drive is added as
4709                  * the last one to the array of stripes. For READ, it also
4710                  * needs to be supported using the same mirror number.
4711                  * If the requested block is not left of the left cursor,
4712                  * EIO is returned. This can happen because btrfs_num_copies()
4713                  * returns one more in the dev-replace case.
4714                  */
4715                 u64 tmp_length = *length;
4716                 struct btrfs_bio *tmp_bbio = NULL;
4717                 int tmp_num_stripes;
4718                 u64 srcdev_devid = dev_replace->srcdev->devid;
4719                 int index_srcdev = 0;
4720                 int found = 0;
4721                 u64 physical_of_found = 0;
4722
4723                 ret = __btrfs_map_block(fs_info, REQ_GET_READ_MIRRORS,
4724                              logical, &tmp_length, &tmp_bbio, 0, NULL);
4725                 if (ret) {
4726                         WARN_ON(tmp_bbio != NULL);
4727                         goto out;
4728                 }
4729
4730                 tmp_num_stripes = tmp_bbio->num_stripes;
4731                 if (mirror_num > tmp_num_stripes) {
4732                         /*
4733                          * REQ_GET_READ_MIRRORS does not contain this
4734                          * mirror, that means that the requested area
4735                          * is not left of the left cursor
4736                          */
4737                         ret = -EIO;
4738                         kfree(tmp_bbio);
4739                         goto out;
4740                 }
4741
4742                 /*
4743                  * process the rest of the function using the mirror_num
4744                  * of the source drive. Therefore look it up first.
4745                  * At the end, patch the device pointer to the one of the
4746                  * target drive.
4747                  */
4748                 for (i = 0; i < tmp_num_stripes; i++) {
4749                         if (tmp_bbio->stripes[i].dev->devid == srcdev_devid) {
4750                                 /*
4751                                  * In case of DUP, in order to keep it
4752                                  * simple, only add the mirror with the
4753                                  * lowest physical address
4754                                  */
4755                                 if (found &&
4756                                     physical_of_found <=
4757                                      tmp_bbio->stripes[i].physical)
4758                                         continue;
4759                                 index_srcdev = i;
4760                                 found = 1;
4761                                 physical_of_found =
4762                                         tmp_bbio->stripes[i].physical;
4763                         }
4764                 }
4765
4766                 if (found) {
4767                         mirror_num = index_srcdev + 1;
4768                         patch_the_first_stripe_for_dev_replace = 1;
4769                         physical_to_patch_in_first_stripe = physical_of_found;
4770                 } else {
4771                         WARN_ON(1);
4772                         ret = -EIO;
4773                         kfree(tmp_bbio);
4774                         goto out;
4775                 }
4776
4777                 kfree(tmp_bbio);
4778         } else if (mirror_num > map->num_stripes) {
4779                 mirror_num = 0;
4780         }
4781
4782         num_stripes = 1;
4783         stripe_index = 0;
4784         stripe_nr_orig = stripe_nr;
4785         stripe_nr_end = ALIGN(offset + *length, map->stripe_len);
4786         do_div(stripe_nr_end, map->stripe_len);
4787         stripe_end_offset = stripe_nr_end * map->stripe_len -
4788                             (offset + *length);
4789
4790         if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
4791                 if (rw & REQ_DISCARD)
4792                         num_stripes = min_t(u64, map->num_stripes,
4793                                             stripe_nr_end - stripe_nr_orig);
4794                 stripe_index = do_div(stripe_nr, map->num_stripes);
4795         } else if (map->type & BTRFS_BLOCK_GROUP_RAID1) {
4796                 if (rw & (REQ_WRITE | REQ_DISCARD | REQ_GET_READ_MIRRORS))
4797                         num_stripes = map->num_stripes;
4798                 else if (mirror_num)
4799                         stripe_index = mirror_num - 1;
4800                 else {
4801                         stripe_index = find_live_mirror(fs_info, map, 0,
4802                                             map->num_stripes,
4803                                             current->pid % map->num_stripes,
4804                                             dev_replace_is_ongoing);
4805                         mirror_num = stripe_index + 1;
4806                 }
4807
4808         } else if (map->type & BTRFS_BLOCK_GROUP_DUP) {
4809                 if (rw & (REQ_WRITE | REQ_DISCARD | REQ_GET_READ_MIRRORS)) {
4810                         num_stripes = map->num_stripes;
4811                 } else if (mirror_num) {
4812                         stripe_index = mirror_num - 1;
4813                 } else {
4814                         mirror_num = 1;
4815                 }
4816
4817         } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
4818                 int factor = map->num_stripes / map->sub_stripes;
4819
4820                 stripe_index = do_div(stripe_nr, factor);
4821                 stripe_index *= map->sub_stripes;
4822
4823                 if (rw & (REQ_WRITE | REQ_GET_READ_MIRRORS))
4824                         num_stripes = map->sub_stripes;
4825                 else if (rw & REQ_DISCARD)
4826                         num_stripes = min_t(u64, map->sub_stripes *
4827                                             (stripe_nr_end - stripe_nr_orig),
4828                                             map->num_stripes);
4829                 else if (mirror_num)
4830                         stripe_index += mirror_num - 1;
4831                 else {
4832                         int old_stripe_index = stripe_index;
4833                         stripe_index = find_live_mirror(fs_info, map,
4834                                               stripe_index,
4835                                               map->sub_stripes, stripe_index +
4836                                               current->pid % map->sub_stripes,
4837                                               dev_replace_is_ongoing);
4838                         mirror_num = stripe_index - old_stripe_index + 1;
4839                 }
4840
4841         } else if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
4842                                 BTRFS_BLOCK_GROUP_RAID6)) {
4843                 u64 tmp;
4844
4845                 if (bbio_ret && ((rw & REQ_WRITE) || mirror_num > 1)
4846                     && raid_map_ret) {
4847                         int i, rot;
4848
4849                         /* push stripe_nr back to the start of the full stripe */
4850                         stripe_nr = raid56_full_stripe_start;
4851                         do_div(stripe_nr, stripe_len);
4852
4853                         stripe_index = do_div(stripe_nr, nr_data_stripes(map));
4854
4855                         /* RAID[56] write or recovery. Return all stripes */
4856                         num_stripes = map->num_stripes;
4857                         max_errors = nr_parity_stripes(map);
4858
4859                         raid_map = kmalloc(sizeof(u64) * num_stripes,
4860                                            GFP_NOFS);
4861                         if (!raid_map) {
4862                                 ret = -ENOMEM;
4863                                 goto out;
4864                         }
4865
4866                         /* Work out the disk rotation on this stripe-set */
4867                         tmp = stripe_nr;
4868                         rot = do_div(tmp, num_stripes);
4869
4870                         /* Fill in the logical address of each stripe */
4871                         tmp = stripe_nr * nr_data_stripes(map);
4872                         for (i = 0; i < nr_data_stripes(map); i++)
4873                                 raid_map[(i+rot) % num_stripes] =
4874                                         em->start + (tmp + i) * map->stripe_len;
4875
4876                         raid_map[(i+rot) % map->num_stripes] = RAID5_P_STRIPE;
4877                         if (map->type & BTRFS_BLOCK_GROUP_RAID6)
4878                                 raid_map[(i+rot+1) % num_stripes] =
4879                                         RAID6_Q_STRIPE;
4880
4881                         *length = map->stripe_len;
4882                         stripe_index = 0;
4883                         stripe_offset = 0;
4884                 } else {
4885                         /*
4886                          * Mirror #0 or #1 means the original data block.
4887                          * Mirror #2 is RAID5 parity block.
4888                          * Mirror #3 is RAID6 Q block.
4889                          */
4890                         stripe_index = do_div(stripe_nr, nr_data_stripes(map));
4891                         if (mirror_num > 1)
4892                                 stripe_index = nr_data_stripes(map) +
4893                                                 mirror_num - 2;
4894
4895                         /* We distribute the parity blocks across stripes */
4896                         tmp = stripe_nr + stripe_index;
4897                         stripe_index = do_div(tmp, map->num_stripes);
4898                 }
4899         } else {
4900                 /*
4901                  * after this do_div call, stripe_nr is the number of stripes
4902                  * on this device we have to walk to find the data, and
4903                  * stripe_index is the number of our device in the stripe array
4904                  */
4905                 stripe_index = do_div(stripe_nr, map->num_stripes);
4906                 mirror_num = stripe_index + 1;
4907         }
4908         BUG_ON(stripe_index >= map->num_stripes);
4909
4910         num_alloc_stripes = num_stripes;
4911         if (dev_replace_is_ongoing) {
4912                 if (rw & (REQ_WRITE | REQ_DISCARD))
4913                         num_alloc_stripes <<= 1;
4914                 if (rw & REQ_GET_READ_MIRRORS)
4915                         num_alloc_stripes++;
4916         }
4917         bbio = kzalloc(btrfs_bio_size(num_alloc_stripes), GFP_NOFS);
4918         if (!bbio) {
4919                 kfree(raid_map);
4920                 ret = -ENOMEM;
4921                 goto out;
4922         }
4923         atomic_set(&bbio->error, 0);
4924
4925         if (rw & REQ_DISCARD) {
4926                 int factor = 0;
4927                 int sub_stripes = 0;
4928                 u64 stripes_per_dev = 0;
4929                 u32 remaining_stripes = 0;
4930                 u32 last_stripe = 0;
4931
4932                 if (map->type &
4933                     (BTRFS_BLOCK_GROUP_RAID0 | BTRFS_BLOCK_GROUP_RAID10)) {
4934                         if (map->type & BTRFS_BLOCK_GROUP_RAID0)
4935                                 sub_stripes = 1;
4936                         else
4937                                 sub_stripes = map->sub_stripes;
4938
4939                         factor = map->num_stripes / sub_stripes;
4940                         stripes_per_dev = div_u64_rem(stripe_nr_end -
4941                                                       stripe_nr_orig,
4942                                                       factor,
4943                                                       &remaining_stripes);
4944                         div_u64_rem(stripe_nr_end - 1, factor, &last_stripe);
4945                         last_stripe *= sub_stripes;
4946                 }
4947
4948                 for (i = 0; i < num_stripes; i++) {
4949                         bbio->stripes[i].physical =
4950                                 map->stripes[stripe_index].physical +
4951                                 stripe_offset + stripe_nr * map->stripe_len;
4952                         bbio->stripes[i].dev = map->stripes[stripe_index].dev;
4953
4954                         if (map->type & (BTRFS_BLOCK_GROUP_RAID0 |
4955                                          BTRFS_BLOCK_GROUP_RAID10)) {
4956                                 bbio->stripes[i].length = stripes_per_dev *
4957                                                           map->stripe_len;
4958
4959                                 if (i / sub_stripes < remaining_stripes)
4960                                         bbio->stripes[i].length +=
4961                                                 map->stripe_len;
4962
4963                                 /*
4964                                  * Special for the first stripe and
4965                                  * the last stripe:
4966                                  *
4967                                  * |-------|...|-------|
4968                                  *     |----------|
4969                                  *    off     end_off
4970                                  */
4971                                 if (i < sub_stripes)
4972                                         bbio->stripes[i].length -=
4973                                                 stripe_offset;
4974
4975                                 if (stripe_index >= last_stripe &&
4976                                     stripe_index <= (last_stripe +
4977                                                      sub_stripes - 1))
4978                                         bbio->stripes[i].length -=
4979                                                 stripe_end_offset;
4980
4981                                 if (i == sub_stripes - 1)
4982                                         stripe_offset = 0;
4983                         } else
4984                                 bbio->stripes[i].length = *length;
4985
4986                         stripe_index++;
4987                         if (stripe_index == map->num_stripes) {
4988                                 /* This could only happen for RAID0/10 */
4989                                 stripe_index = 0;
4990                                 stripe_nr++;
4991                         }
4992                 }
4993         } else {
4994                 for (i = 0; i < num_stripes; i++) {
4995                         bbio->stripes[i].physical =
4996                                 map->stripes[stripe_index].physical +
4997                                 stripe_offset +
4998                                 stripe_nr * map->stripe_len;
4999                         bbio->stripes[i].dev =
5000                                 map->stripes[stripe_index].dev;
5001                         stripe_index++;
5002                 }
5003         }
5004
5005         if (rw & (REQ_WRITE | REQ_GET_READ_MIRRORS)) {
5006                 if (map->type & (BTRFS_BLOCK_GROUP_RAID1 |
5007                                  BTRFS_BLOCK_GROUP_RAID10 |
5008                                  BTRFS_BLOCK_GROUP_RAID5 |
5009                                  BTRFS_BLOCK_GROUP_DUP)) {
5010                         max_errors = 1;
5011                 } else if (map->type & BTRFS_BLOCK_GROUP_RAID6) {
5012                         max_errors = 2;
5013                 }
5014         }
5015
5016         if (dev_replace_is_ongoing && (rw & (REQ_WRITE | REQ_DISCARD)) &&
5017             dev_replace->tgtdev != NULL) {
5018                 int index_where_to_add;
5019                 u64 srcdev_devid = dev_replace->srcdev->devid;
5020
5021                 /*
5022                  * duplicate the write operations while the dev replace
5023                  * procedure is running. Since the copying of the old disk
5024                  * to the new disk takes place at run time while the
5025                  * filesystem is mounted writable, the regular write
5026                  * operations to the old disk have to be duplicated to go
5027                  * to the new disk as well.
5028                  * Note that device->missing is handled by the caller, and
5029                  * that the write to the old disk is already set up in the
5030                  * stripes array.
5031                  */
5032                 index_where_to_add = num_stripes;
5033                 for (i = 0; i < num_stripes; i++) {
5034                         if (bbio->stripes[i].dev->devid == srcdev_devid) {
5035                                 /* write to new disk, too */
5036                                 struct btrfs_bio_stripe *new =
5037                                         bbio->stripes + index_where_to_add;
5038                                 struct btrfs_bio_stripe *old =
5039                                         bbio->stripes + i;
5040
5041                                 new->physical = old->physical;
5042                                 new->length = old->length;
5043                                 new->dev = dev_replace->tgtdev;
5044                                 index_where_to_add++;
5045                                 max_errors++;
5046                         }
5047                 }
5048                 num_stripes = index_where_to_add;
5049         } else if (dev_replace_is_ongoing && (rw & REQ_GET_READ_MIRRORS) &&
5050                    dev_replace->tgtdev != NULL) {
5051                 u64 srcdev_devid = dev_replace->srcdev->devid;
5052                 int index_srcdev = 0;
5053                 int found = 0;
5054                 u64 physical_of_found = 0;
5055
5056                 /*
5057                  * During the dev-replace procedure, the target drive can
5058                  * also be used to read data in case it is needed to repair
5059                  * a corrupt block elsewhere. This is possible if the
5060                  * requested area is left of the left cursor. In this area,
5061                  * the target drive is a full copy of the source drive.
5062                  */
5063                 for (i = 0; i < num_stripes; i++) {
5064                         if (bbio->stripes[i].dev->devid == srcdev_devid) {
5065                                 /*
5066                                  * In case of DUP, in order to keep it
5067                                  * simple, only add the mirror with the
5068                                  * lowest physical address
5069                                  */
5070                                 if (found &&
5071                                     physical_of_found <=
5072                                      bbio->stripes[i].physical)
5073                                         continue;
5074                                 index_srcdev = i;
5075                                 found = 1;
5076                                 physical_of_found = bbio->stripes[i].physical;
5077                         }
5078                 }
5079                 if (found) {
5080                         u64 length = map->stripe_len;
5081
5082                         if (physical_of_found + length <=
5083                             dev_replace->cursor_left) {
5084                                 struct btrfs_bio_stripe *tgtdev_stripe =
5085                                         bbio->stripes + num_stripes;
5086
5087                                 tgtdev_stripe->physical = physical_of_found;
5088                                 tgtdev_stripe->length =
5089                                         bbio->stripes[index_srcdev].length;
5090                                 tgtdev_stripe->dev = dev_replace->tgtdev;
5091
5092                                 num_stripes++;
5093                         }
5094                 }
5095         }
5096
5097         *bbio_ret = bbio;
5098         bbio->num_stripes = num_stripes;
5099         bbio->max_errors = max_errors;
5100         bbio->mirror_num = mirror_num;
5101
5102         /*
5103          * this is the case that REQ_READ && dev_replace_is_ongoing &&
5104          * mirror_num == num_stripes + 1 && dev_replace target drive is
5105          * available as a mirror
5106          */
5107         if (patch_the_first_stripe_for_dev_replace && num_stripes > 0) {
5108                 WARN_ON(num_stripes > 1);
5109                 bbio->stripes[0].dev = dev_replace->tgtdev;
5110                 bbio->stripes[0].physical = physical_to_patch_in_first_stripe;
5111                 bbio->mirror_num = map->num_stripes + 1;
5112         }
5113         if (raid_map) {
5114                 sort_parity_stripes(bbio, raid_map);
5115                 *raid_map_ret = raid_map;
5116         }
5117 out:
5118         if (dev_replace_is_ongoing)
5119                 btrfs_dev_replace_unlock(dev_replace);
5120         free_extent_map(em);
5121         return ret;
5122 }
5123
5124 int btrfs_map_block(struct btrfs_fs_info *fs_info, int rw,
5125                       u64 logical, u64 *length,
5126                       struct btrfs_bio **bbio_ret, int mirror_num)
5127 {
5128         return __btrfs_map_block(fs_info, rw, logical, length, bbio_ret,
5129                                  mirror_num, NULL);
5130 }
5131
5132 int btrfs_rmap_block(struct btrfs_mapping_tree *map_tree,
5133                      u64 chunk_start, u64 physical, u64 devid,
5134                      u64 **logical, int *naddrs, int *stripe_len)
5135 {
5136         struct extent_map_tree *em_tree = &map_tree->map_tree;
5137         struct extent_map *em;
5138         struct map_lookup *map;
5139         u64 *buf;
5140         u64 bytenr;
5141         u64 length;
5142         u64 stripe_nr;
5143         u64 rmap_len;
5144         int i, j, nr = 0;
5145
5146         read_lock(&em_tree->lock);
5147         em = lookup_extent_mapping(em_tree, chunk_start, 1);
5148         read_unlock(&em_tree->lock);
5149
5150         if (!em) {
5151                 printk(KERN_ERR "btrfs: couldn't find em for chunk %Lu\n",
5152                        chunk_start);
5153                 return -EIO;
5154         }
5155
5156         if (em->start != chunk_start) {
5157                 printk(KERN_ERR "btrfs: bad chunk start, em=%Lu, wanted=%Lu\n",
5158                        em->start, chunk_start);
5159                 free_extent_map(em);
5160                 return -EIO;
5161         }
5162         map = (struct map_lookup *)em->bdev;
5163
5164         length = em->len;
5165         rmap_len = map->stripe_len;
5166
5167         if (map->type & BTRFS_BLOCK_GROUP_RAID10)
5168                 do_div(length, map->num_stripes / map->sub_stripes);
5169         else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
5170                 do_div(length, map->num_stripes);
5171         else if (map->type & (BTRFS_BLOCK_GROUP_RAID5 |
5172                               BTRFS_BLOCK_GROUP_RAID6)) {
5173                 do_div(length, nr_data_stripes(map));
5174                 rmap_len = map->stripe_len * nr_data_stripes(map);
5175         }
5176
5177         buf = kzalloc(sizeof(u64) * map->num_stripes, GFP_NOFS);
5178         BUG_ON(!buf); /* -ENOMEM */
5179
5180         for (i = 0; i < map->num_stripes; i++) {
5181                 if (devid && map->stripes[i].dev->devid != devid)
5182                         continue;
5183                 if (map->stripes[i].physical > physical ||
5184                     map->stripes[i].physical + length <= physical)
5185                         continue;
5186
5187                 stripe_nr = physical - map->stripes[i].physical;
5188                 do_div(stripe_nr, map->stripe_len);
5189
5190                 if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
5191                         stripe_nr = stripe_nr * map->num_stripes + i;
5192                         do_div(stripe_nr, map->sub_stripes);
5193                 } else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
5194                         stripe_nr = stripe_nr * map->num_stripes + i;
5195                 } /* else if RAID[56], multiply by nr_data_stripes().
5196                    * Alternatively, just use rmap_len below instead of
5197                    * map->stripe_len */
5198
5199                 bytenr = chunk_start + stripe_nr * rmap_len;
5200                 WARN_ON(nr >= map->num_stripes);
5201                 for (j = 0; j < nr; j++) {
5202                         if (buf[j] == bytenr)
5203                                 break;
5204                 }
5205                 if (j == nr) {
5206                         WARN_ON(nr >= map->num_stripes);
5207                         buf[nr++] = bytenr;
5208                 }
5209         }
5210
5211         *logical = buf;
5212         *naddrs = nr;
5213         *stripe_len = rmap_len;
5214
5215         free_extent_map(em);
5216         return 0;
5217 }
5218
5219 static void btrfs_end_bio(struct bio *bio, int err)
5220 {
5221         struct btrfs_bio *bbio = bio->bi_private;
5222         int is_orig_bio = 0;
5223
5224         if (err) {
5225                 atomic_inc(&bbio->error);
5226                 if (err == -EIO || err == -EREMOTEIO) {
5227                         unsigned int stripe_index =
5228                                 btrfs_io_bio(bio)->stripe_index;
5229                         struct btrfs_device *dev;
5230
5231                         BUG_ON(stripe_index >= bbio->num_stripes);
5232                         dev = bbio->stripes[stripe_index].dev;
5233                         if (dev->bdev) {
5234                                 if (bio->bi_rw & WRITE)
5235                                         btrfs_dev_stat_inc(dev,
5236                                                 BTRFS_DEV_STAT_WRITE_ERRS);
5237                                 else
5238                                         btrfs_dev_stat_inc(dev,
5239                                                 BTRFS_DEV_STAT_READ_ERRS);
5240                                 if ((bio->bi_rw & WRITE_FLUSH) == WRITE_FLUSH)
5241                                         btrfs_dev_stat_inc(dev,
5242                                                 BTRFS_DEV_STAT_FLUSH_ERRS);
5243                                 btrfs_dev_stat_print_on_error(dev);
5244                         }
5245                 }
5246         }
5247
5248         if (bio == bbio->orig_bio)
5249                 is_orig_bio = 1;
5250
5251         if (atomic_dec_and_test(&bbio->stripes_pending)) {
5252                 if (!is_orig_bio) {
5253                         bio_put(bio);
5254                         bio = bbio->orig_bio;
5255                 }
5256                 bio->bi_private = bbio->private;
5257                 bio->bi_end_io = bbio->end_io;
5258                 btrfs_io_bio(bio)->mirror_num = bbio->mirror_num;
5259                 /* only send an error to the higher layers if it is
5260                  * beyond the tolerance of the btrfs bio
5261                  */
5262                 if (atomic_read(&bbio->error) > bbio->max_errors) {
5263                         err = -EIO;
5264                 } else {
5265                         /*
5266                          * this bio is actually up to date, we didn't
5267                          * go over the max number of errors
5268                          */
5269                         set_bit(BIO_UPTODATE, &bio->bi_flags);
5270                         err = 0;
5271                 }
5272                 kfree(bbio);
5273
5274                 bio_endio(bio, err);
5275         } else if (!is_orig_bio) {
5276                 bio_put(bio);
5277         }
5278 }
5279
5280 struct async_sched {
5281         struct bio *bio;
5282         int rw;
5283         struct btrfs_fs_info *info;
5284         struct btrfs_work work;
5285 };
5286
5287 /*
5288  * see run_scheduled_bios for a description of why bios are collected for
5289  * async submit.
5290  *
5291  * This will add one bio to the pending list for a device and make sure
5292  * the work struct is scheduled.
5293  */
5294 static noinline void btrfs_schedule_bio(struct btrfs_root *root,
5295                                         struct btrfs_device *device,
5296                                         int rw, struct bio *bio)
5297 {
5298         int should_queue = 1;
5299         struct btrfs_pending_bios *pending_bios;
5300
5301         if (device->missing || !device->bdev) {
5302                 bio_endio(bio, -EIO);
5303                 return;
5304         }
5305
5306         /* don't bother with additional async steps for reads, right now */
5307         if (!(rw & REQ_WRITE)) {
5308                 bio_get(bio);
5309                 btrfsic_submit_bio(rw, bio);
5310                 bio_put(bio);
5311                 return;
5312         }
5313
5314         /*
5315          * nr_async_bios allows us to reliably return congestion to the
5316          * higher layers.  Otherwise, the async bio makes it appear we have
5317          * made progress against dirty pages when we've really just put it
5318          * on a queue for later
5319          */
5320         atomic_inc(&root->fs_info->nr_async_bios);
5321         WARN_ON(bio->bi_next);
5322         bio->bi_next = NULL;
5323         bio->bi_rw |= rw;
5324
5325         spin_lock(&device->io_lock);
5326         if (bio->bi_rw & REQ_SYNC)
5327                 pending_bios = &device->pending_sync_bios;
5328         else
5329                 pending_bios = &device->pending_bios;
5330
5331         if (pending_bios->tail)
5332                 pending_bios->tail->bi_next = bio;
5333
5334         pending_bios->tail = bio;
5335         if (!pending_bios->head)
5336                 pending_bios->head = bio;
5337         if (device->running_pending)
5338                 should_queue = 0;
5339
5340         spin_unlock(&device->io_lock);
5341
5342         if (should_queue)
5343                 btrfs_queue_worker(&root->fs_info->submit_workers,
5344                                    &device->work);
5345 }
5346
5347 static int bio_size_ok(struct block_device *bdev, struct bio *bio,
5348                        sector_t sector)
5349 {
5350         struct bio_vec *prev;
5351         struct request_queue *q = bdev_get_queue(bdev);
5352         unsigned short max_sectors = queue_max_sectors(q);
5353         struct bvec_merge_data bvm = {
5354                 .bi_bdev = bdev,
5355                 .bi_sector = sector,
5356                 .bi_rw = bio->bi_rw,
5357         };
5358
5359         if (bio->bi_vcnt == 0) {
5360                 WARN_ON(1);
5361                 return 1;
5362         }
5363
5364         prev = &bio->bi_io_vec[bio->bi_vcnt - 1];
5365         if (bio_sectors(bio) > max_sectors)
5366                 return 0;
5367
5368         if (!q->merge_bvec_fn)
5369                 return 1;
5370
5371         bvm.bi_size = bio->bi_size - prev->bv_len;
5372         if (q->merge_bvec_fn(q, &bvm, prev) < prev->bv_len)
5373                 return 0;
5374         return 1;
5375 }
5376
5377 static void submit_stripe_bio(struct btrfs_root *root, struct btrfs_bio *bbio,
5378                               struct bio *bio, u64 physical, int dev_nr,
5379                               int rw, int async)
5380 {
5381         struct btrfs_device *dev = bbio->stripes[dev_nr].dev;
5382
5383         bio->bi_private = bbio;
5384         btrfs_io_bio(bio)->stripe_index = dev_nr;
5385         bio->bi_end_io = btrfs_end_bio;
5386         bio->bi_sector = physical >> 9;
5387 #ifdef DEBUG
5388         {
5389                 struct rcu_string *name;
5390
5391                 rcu_read_lock();
5392                 name = rcu_dereference(dev->name);
5393                 pr_debug("btrfs_map_bio: rw %d, sector=%llu, dev=%lu "
5394                          "(%s id %llu), size=%u\n", rw,
5395                          (u64)bio->bi_sector, (u_long)dev->bdev->bd_dev,
5396                          name->str, dev->devid, bio->bi_size);
5397                 rcu_read_unlock();
5398         }
5399 #endif
5400         bio->bi_bdev = dev->bdev;
5401         if (async)
5402                 btrfs_schedule_bio(root, dev, rw, bio);
5403         else
5404                 btrfsic_submit_bio(rw, bio);
5405 }
5406
5407 static int breakup_stripe_bio(struct btrfs_root *root, struct btrfs_bio *bbio,
5408                               struct bio *first_bio, struct btrfs_device *dev,
5409                               int dev_nr, int rw, int async)
5410 {
5411         struct bio_vec *bvec = first_bio->bi_io_vec;
5412         struct bio *bio;
5413         int nr_vecs = bio_get_nr_vecs(dev->bdev);
5414         u64 physical = bbio->stripes[dev_nr].physical;
5415
5416 again:
5417         bio = btrfs_bio_alloc(dev->bdev, physical >> 9, nr_vecs, GFP_NOFS);
5418         if (!bio)
5419                 return -ENOMEM;
5420
5421         while (bvec <= (first_bio->bi_io_vec + first_bio->bi_vcnt - 1)) {
5422                 if (bio_add_page(bio, bvec->bv_page, bvec->bv_len,
5423                                  bvec->bv_offset) < bvec->bv_len) {
5424                         u64 len = bio->bi_size;
5425
5426                         atomic_inc(&bbio->stripes_pending);
5427                         submit_stripe_bio(root, bbio, bio, physical, dev_nr,
5428                                           rw, async);
5429                         physical += len;
5430                         goto again;
5431                 }
5432                 bvec++;
5433         }
5434
5435         submit_stripe_bio(root, bbio, bio, physical, dev_nr, rw, async);
5436         return 0;
5437 }
5438
5439 static void bbio_error(struct btrfs_bio *bbio, struct bio *bio, u64 logical)
5440 {
5441         atomic_inc(&bbio->error);
5442         if (atomic_dec_and_test(&bbio->stripes_pending)) {
5443                 bio->bi_private = bbio->private;
5444                 bio->bi_end_io = bbio->end_io;
5445                 btrfs_io_bio(bio)->mirror_num = bbio->mirror_num;
5446                 bio->bi_sector = logical >> 9;
5447                 kfree(bbio);
5448                 bio_endio(bio, -EIO);
5449         }
5450 }
5451
5452 int btrfs_map_bio(struct btrfs_root *root, int rw, struct bio *bio,
5453                   int mirror_num, int async_submit)
5454 {
5455         struct btrfs_device *dev;
5456         struct bio *first_bio = bio;
5457         u64 logical = (u64)bio->bi_sector << 9;
5458         u64 length = 0;
5459         u64 map_length;
5460         u64 *raid_map = NULL;
5461         int ret;
5462         int dev_nr = 0;
5463         int total_devs = 1;
5464         struct btrfs_bio *bbio = NULL;
5465
5466         length = bio->bi_size;
5467         map_length = length;
5468
5469         ret = __btrfs_map_block(root->fs_info, rw, logical, &map_length, &bbio,
5470                               mirror_num, &raid_map);
5471         if (ret) /* -ENOMEM */
5472                 return ret;
5473
5474         total_devs = bbio->num_stripes;
5475         bbio->orig_bio = first_bio;
5476         bbio->private = first_bio->bi_private;
5477         bbio->end_io = first_bio->bi_end_io;
5478         atomic_set(&bbio->stripes_pending, bbio->num_stripes);
5479
5480         if (raid_map) {
5481                 /* In this case, map_length has been set to the length of
5482                    a single stripe; not the whole write */
5483                 if (rw & WRITE) {
5484                         return raid56_parity_write(root, bio, bbio,
5485                                                    raid_map, map_length);
5486                 } else {
5487                         return raid56_parity_recover(root, bio, bbio,
5488                                                      raid_map, map_length,
5489                                                      mirror_num);
5490                 }
5491         }
5492
5493         if (map_length < length) {
5494                 btrfs_crit(root->fs_info, "mapping failed logical %llu bio len %llu len %llu",
5495                         (unsigned long long)logical,
5496                         (unsigned long long)length,
5497                         (unsigned long long)map_length);
5498                 BUG();
5499         }
5500
5501         while (dev_nr < total_devs) {
5502                 dev = bbio->stripes[dev_nr].dev;
5503                 if (!dev || !dev->bdev || (rw & WRITE && !dev->writeable)) {
5504                         bbio_error(bbio, first_bio, logical);
5505                         dev_nr++;
5506                         continue;
5507                 }
5508
5509                 /*
5510                  * Check and see if we're ok with this bio based on it's size
5511                  * and offset with the given device.
5512                  */
5513                 if (!bio_size_ok(dev->bdev, first_bio,
5514                                  bbio->stripes[dev_nr].physical >> 9)) {
5515                         ret = breakup_stripe_bio(root, bbio, first_bio, dev,
5516                                                  dev_nr, rw, async_submit);
5517                         BUG_ON(ret);
5518                         dev_nr++;
5519                         continue;
5520                 }
5521
5522                 if (dev_nr < total_devs - 1) {
5523                         bio = btrfs_bio_clone(first_bio, GFP_NOFS);
5524                         BUG_ON(!bio); /* -ENOMEM */
5525                 } else {
5526                         bio = first_bio;
5527                 }
5528
5529                 submit_stripe_bio(root, bbio, bio,
5530                                   bbio->stripes[dev_nr].physical, dev_nr, rw,
5531                                   async_submit);
5532                 dev_nr++;
5533         }
5534         return 0;
5535 }
5536
5537 struct btrfs_device *btrfs_find_device(struct btrfs_fs_info *fs_info, u64 devid,
5538                                        u8 *uuid, u8 *fsid)
5539 {
5540         struct btrfs_device *device;
5541         struct btrfs_fs_devices *cur_devices;
5542
5543         cur_devices = fs_info->fs_devices;
5544         while (cur_devices) {
5545                 if (!fsid ||
5546                     !memcmp(cur_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
5547                         device = __find_device(&cur_devices->devices,
5548                                                devid, uuid);
5549                         if (device)
5550                                 return device;
5551                 }
5552                 cur_devices = cur_devices->seed;
5553         }
5554         return NULL;
5555 }
5556
5557 static struct btrfs_device *add_missing_dev(struct btrfs_root *root,
5558                                             u64 devid, u8 *dev_uuid)
5559 {
5560         struct btrfs_device *device;
5561         struct btrfs_fs_devices *fs_devices = root->fs_info->fs_devices;
5562
5563         device = btrfs_alloc_device(NULL, &devid, dev_uuid);
5564         if (IS_ERR(device))
5565                 return NULL;
5566
5567         list_add(&device->dev_list, &fs_devices->devices);
5568         device->fs_devices = fs_devices;
5569         fs_devices->num_devices++;
5570
5571         device->missing = 1;
5572         fs_devices->missing_devices++;
5573
5574         return device;
5575 }
5576
5577 /**
5578  * btrfs_alloc_device - allocate struct btrfs_device
5579  * @fs_info:    used only for generating a new devid, can be NULL if
5580  *              devid is provided (i.e. @devid != NULL).
5581  * @devid:      a pointer to devid for this device.  If NULL a new devid
5582  *              is generated.
5583  * @uuid:       a pointer to UUID for this device.  If NULL a new UUID
5584  *              is generated.
5585  *
5586  * Return: a pointer to a new &struct btrfs_device on success; ERR_PTR()
5587  * on error.  Returned struct is not linked onto any lists and can be
5588  * destroyed with kfree() right away.
5589  */
5590 struct btrfs_device *btrfs_alloc_device(struct btrfs_fs_info *fs_info,
5591                                         const u64 *devid,
5592                                         const u8 *uuid)
5593 {
5594         struct btrfs_device *dev;
5595         u64 tmp;
5596
5597         if (!devid && !fs_info) {
5598                 WARN_ON(1);
5599                 return ERR_PTR(-EINVAL);
5600         }
5601
5602         dev = __alloc_device();
5603         if (IS_ERR(dev))
5604                 return dev;
5605
5606         if (devid)
5607                 tmp = *devid;
5608         else {
5609                 int ret;
5610
5611                 ret = find_next_devid(fs_info, &tmp);
5612                 if (ret) {
5613                         kfree(dev);
5614                         return ERR_PTR(ret);
5615                 }
5616         }
5617         dev->devid = tmp;
5618
5619         if (uuid)
5620                 memcpy(dev->uuid, uuid, BTRFS_UUID_SIZE);
5621         else
5622                 generate_random_uuid(dev->uuid);
5623
5624         dev->work.func = pending_bios_fn;
5625
5626         return dev;
5627 }
5628
5629 static int read_one_chunk(struct btrfs_root *root, struct btrfs_key *key,
5630                           struct extent_buffer *leaf,
5631                           struct btrfs_chunk *chunk)
5632 {
5633         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
5634         struct map_lookup *map;
5635         struct extent_map *em;
5636         u64 logical;
5637         u64 length;
5638         u64 devid;
5639         u8 uuid[BTRFS_UUID_SIZE];
5640         int num_stripes;
5641         int ret;
5642         int i;
5643
5644         logical = key->offset;
5645         length = btrfs_chunk_length(leaf, chunk);
5646
5647         read_lock(&map_tree->map_tree.lock);
5648         em = lookup_extent_mapping(&map_tree->map_tree, logical, 1);
5649         read_unlock(&map_tree->map_tree.lock);
5650
5651         /* already mapped? */
5652         if (em && em->start <= logical && em->start + em->len > logical) {
5653                 free_extent_map(em);
5654                 return 0;
5655         } else if (em) {
5656                 free_extent_map(em);
5657         }
5658
5659         em = alloc_extent_map();
5660         if (!em)
5661                 return -ENOMEM;
5662         num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
5663         map = kmalloc(map_lookup_size(num_stripes), GFP_NOFS);
5664         if (!map) {
5665                 free_extent_map(em);
5666                 return -ENOMEM;
5667         }
5668
5669         em->bdev = (struct block_device *)map;
5670         em->start = logical;
5671         em->len = length;
5672         em->orig_start = 0;
5673         em->block_start = 0;
5674         em->block_len = em->len;
5675
5676         map->num_stripes = num_stripes;
5677         map->io_width = btrfs_chunk_io_width(leaf, chunk);
5678         map->io_align = btrfs_chunk_io_align(leaf, chunk);
5679         map->sector_size = btrfs_chunk_sector_size(leaf, chunk);
5680         map->stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
5681         map->type = btrfs_chunk_type(leaf, chunk);
5682         map->sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
5683         for (i = 0; i < num_stripes; i++) {
5684                 map->stripes[i].physical =
5685                         btrfs_stripe_offset_nr(leaf, chunk, i);
5686                 devid = btrfs_stripe_devid_nr(leaf, chunk, i);
5687                 read_extent_buffer(leaf, uuid, (unsigned long)
5688                                    btrfs_stripe_dev_uuid_nr(chunk, i),
5689                                    BTRFS_UUID_SIZE);
5690                 map->stripes[i].dev = btrfs_find_device(root->fs_info, devid,
5691                                                         uuid, NULL);
5692                 if (!map->stripes[i].dev && !btrfs_test_opt(root, DEGRADED)) {
5693                         kfree(map);
5694                         free_extent_map(em);
5695                         return -EIO;
5696                 }
5697                 if (!map->stripes[i].dev) {
5698                         map->stripes[i].dev =
5699                                 add_missing_dev(root, devid, uuid);
5700                         if (!map->stripes[i].dev) {
5701                                 kfree(map);
5702                                 free_extent_map(em);
5703                                 return -EIO;
5704                         }
5705                 }
5706                 map->stripes[i].dev->in_fs_metadata = 1;
5707         }
5708
5709         write_lock(&map_tree->map_tree.lock);
5710         ret = add_extent_mapping(&map_tree->map_tree, em, 0);
5711         write_unlock(&map_tree->map_tree.lock);
5712         BUG_ON(ret); /* Tree corruption */
5713         free_extent_map(em);
5714
5715         return 0;
5716 }
5717
5718 static void fill_device_from_item(struct extent_buffer *leaf,
5719                                  struct btrfs_dev_item *dev_item,
5720                                  struct btrfs_device *device)
5721 {
5722         unsigned long ptr;
5723
5724         device->devid = btrfs_device_id(leaf, dev_item);
5725         device->disk_total_bytes = btrfs_device_total_bytes(leaf, dev_item);
5726         device->total_bytes = device->disk_total_bytes;
5727         device->bytes_used = btrfs_device_bytes_used(leaf, dev_item);
5728         device->type = btrfs_device_type(leaf, dev_item);
5729         device->io_align = btrfs_device_io_align(leaf, dev_item);
5730         device->io_width = btrfs_device_io_width(leaf, dev_item);
5731         device->sector_size = btrfs_device_sector_size(leaf, dev_item);
5732         WARN_ON(device->devid == BTRFS_DEV_REPLACE_DEVID);
5733         device->is_tgtdev_for_dev_replace = 0;
5734
5735         ptr = (unsigned long)btrfs_device_uuid(dev_item);
5736         read_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
5737 }
5738
5739 static int open_seed_devices(struct btrfs_root *root, u8 *fsid)
5740 {
5741         struct btrfs_fs_devices *fs_devices;
5742         int ret;
5743
5744         BUG_ON(!mutex_is_locked(&uuid_mutex));
5745
5746         fs_devices = root->fs_info->fs_devices->seed;
5747         while (fs_devices) {
5748                 if (!memcmp(fs_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
5749                         ret = 0;
5750                         goto out;
5751                 }
5752                 fs_devices = fs_devices->seed;
5753         }
5754
5755         fs_devices = find_fsid(fsid);
5756         if (!fs_devices) {
5757                 ret = -ENOENT;
5758                 goto out;
5759         }
5760
5761         fs_devices = clone_fs_devices(fs_devices);
5762         if (IS_ERR(fs_devices)) {
5763                 ret = PTR_ERR(fs_devices);
5764                 goto out;
5765         }
5766
5767         ret = __btrfs_open_devices(fs_devices, FMODE_READ,
5768                                    root->fs_info->bdev_holder);
5769         if (ret) {
5770                 free_fs_devices(fs_devices);
5771                 goto out;
5772         }
5773
5774         if (!fs_devices->seeding) {
5775                 __btrfs_close_devices(fs_devices);
5776                 free_fs_devices(fs_devices);
5777                 ret = -EINVAL;
5778                 goto out;
5779         }
5780
5781         fs_devices->seed = root->fs_info->fs_devices->seed;
5782         root->fs_info->fs_devices->seed = fs_devices;
5783 out:
5784         return ret;
5785 }
5786
5787 static int read_one_dev(struct btrfs_root *root,
5788                         struct extent_buffer *leaf,
5789                         struct btrfs_dev_item *dev_item)
5790 {
5791         struct btrfs_device *device;
5792         u64 devid;
5793         int ret;
5794         u8 fs_uuid[BTRFS_UUID_SIZE];
5795         u8 dev_uuid[BTRFS_UUID_SIZE];
5796
5797         devid = btrfs_device_id(leaf, dev_item);
5798         read_extent_buffer(leaf, dev_uuid,
5799                            (unsigned long)btrfs_device_uuid(dev_item),
5800                            BTRFS_UUID_SIZE);
5801         read_extent_buffer(leaf, fs_uuid,
5802                            (unsigned long)btrfs_device_fsid(dev_item),
5803                            BTRFS_UUID_SIZE);
5804
5805         if (memcmp(fs_uuid, root->fs_info->fsid, BTRFS_UUID_SIZE)) {
5806                 ret = open_seed_devices(root, fs_uuid);
5807                 if (ret && !btrfs_test_opt(root, DEGRADED))
5808                         return ret;
5809         }
5810
5811         device = btrfs_find_device(root->fs_info, devid, dev_uuid, fs_uuid);
5812         if (!device || !device->bdev) {
5813                 if (!btrfs_test_opt(root, DEGRADED))
5814                         return -EIO;
5815
5816                 if (!device) {
5817                         btrfs_warn(root->fs_info, "devid %llu missing",
5818                                 (unsigned long long)devid);
5819                         device = add_missing_dev(root, devid, dev_uuid);
5820                         if (!device)
5821                                 return -ENOMEM;
5822                 } else if (!device->missing) {
5823                         /*
5824                          * this happens when a device that was properly setup
5825                          * in the device info lists suddenly goes bad.
5826                          * device->bdev is NULL, and so we have to set
5827                          * device->missing to one here
5828                          */
5829                         root->fs_info->fs_devices->missing_devices++;
5830                         device->missing = 1;
5831                 }
5832         }
5833
5834         if (device->fs_devices != root->fs_info->fs_devices) {
5835                 BUG_ON(device->writeable);
5836                 if (device->generation !=
5837                     btrfs_device_generation(leaf, dev_item))
5838                         return -EINVAL;
5839         }
5840
5841         fill_device_from_item(leaf, dev_item, device);
5842         device->in_fs_metadata = 1;
5843         if (device->writeable && !device->is_tgtdev_for_dev_replace) {
5844                 device->fs_devices->total_rw_bytes += device->total_bytes;
5845                 spin_lock(&root->fs_info->free_chunk_lock);
5846                 root->fs_info->free_chunk_space += device->total_bytes -
5847                         device->bytes_used;
5848                 spin_unlock(&root->fs_info->free_chunk_lock);
5849         }
5850         ret = 0;
5851         return ret;
5852 }
5853
5854 int btrfs_read_sys_array(struct btrfs_root *root)
5855 {
5856         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
5857         struct extent_buffer *sb;
5858         struct btrfs_disk_key *disk_key;
5859         struct btrfs_chunk *chunk;
5860         u8 *ptr;
5861         unsigned long sb_ptr;
5862         int ret = 0;
5863         u32 num_stripes;
5864         u32 array_size;
5865         u32 len = 0;
5866         u32 cur;
5867         struct btrfs_key key;
5868
5869         sb = btrfs_find_create_tree_block(root, BTRFS_SUPER_INFO_OFFSET,
5870                                           BTRFS_SUPER_INFO_SIZE);
5871         if (!sb)
5872                 return -ENOMEM;
5873         btrfs_set_buffer_uptodate(sb);
5874         btrfs_set_buffer_lockdep_class(root->root_key.objectid, sb, 0);
5875         /*
5876          * The sb extent buffer is artifical and just used to read the system array.
5877          * btrfs_set_buffer_uptodate() call does not properly mark all it's
5878          * pages up-to-date when the page is larger: extent does not cover the
5879          * whole page and consequently check_page_uptodate does not find all
5880          * the page's extents up-to-date (the hole beyond sb),
5881          * write_extent_buffer then triggers a WARN_ON.
5882          *
5883          * Regular short extents go through mark_extent_buffer_dirty/writeback cycle,
5884          * but sb spans only this function. Add an explicit SetPageUptodate call
5885          * to silence the warning eg. on PowerPC 64.
5886          */
5887         if (PAGE_CACHE_SIZE > BTRFS_SUPER_INFO_SIZE)
5888                 SetPageUptodate(sb->pages[0]);
5889
5890         write_extent_buffer(sb, super_copy, 0, BTRFS_SUPER_INFO_SIZE);
5891         array_size = btrfs_super_sys_array_size(super_copy);
5892
5893         ptr = super_copy->sys_chunk_array;
5894         sb_ptr = offsetof(struct btrfs_super_block, sys_chunk_array);
5895         cur = 0;
5896
5897         while (cur < array_size) {
5898                 disk_key = (struct btrfs_disk_key *)ptr;
5899                 btrfs_disk_key_to_cpu(&key, disk_key);
5900
5901                 len = sizeof(*disk_key); ptr += len;
5902                 sb_ptr += len;
5903                 cur += len;
5904
5905                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
5906                         chunk = (struct btrfs_chunk *)sb_ptr;
5907                         ret = read_one_chunk(root, &key, sb, chunk);
5908                         if (ret)
5909                                 break;
5910                         num_stripes = btrfs_chunk_num_stripes(sb, chunk);
5911                         len = btrfs_chunk_item_size(num_stripes);
5912                 } else {
5913                         ret = -EIO;
5914                         break;
5915                 }
5916                 ptr += len;
5917                 sb_ptr += len;
5918                 cur += len;
5919         }
5920         free_extent_buffer(sb);
5921         return ret;
5922 }
5923
5924 int btrfs_read_chunk_tree(struct btrfs_root *root)
5925 {
5926         struct btrfs_path *path;
5927         struct extent_buffer *leaf;
5928         struct btrfs_key key;
5929         struct btrfs_key found_key;
5930         int ret;
5931         int slot;
5932
5933         root = root->fs_info->chunk_root;
5934
5935         path = btrfs_alloc_path();
5936         if (!path)
5937                 return -ENOMEM;
5938
5939         mutex_lock(&uuid_mutex);
5940         lock_chunks(root);
5941
5942         /*
5943          * Read all device items, and then all the chunk items. All
5944          * device items are found before any chunk item (their object id
5945          * is smaller than the lowest possible object id for a chunk
5946          * item - BTRFS_FIRST_CHUNK_TREE_OBJECTID).
5947          */
5948         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
5949         key.offset = 0;
5950         key.type = 0;
5951         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5952         if (ret < 0)
5953                 goto error;
5954         while (1) {
5955                 leaf = path->nodes[0];
5956                 slot = path->slots[0];
5957                 if (slot >= btrfs_header_nritems(leaf)) {
5958                         ret = btrfs_next_leaf(root, path);
5959                         if (ret == 0)
5960                                 continue;
5961                         if (ret < 0)
5962                                 goto error;
5963                         break;
5964                 }
5965                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
5966                 if (found_key.type == BTRFS_DEV_ITEM_KEY) {
5967                         struct btrfs_dev_item *dev_item;
5968                         dev_item = btrfs_item_ptr(leaf, slot,
5969                                                   struct btrfs_dev_item);
5970                         ret = read_one_dev(root, leaf, dev_item);
5971                         if (ret)
5972                                 goto error;
5973                 } else if (found_key.type == BTRFS_CHUNK_ITEM_KEY) {
5974                         struct btrfs_chunk *chunk;
5975                         chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
5976                         ret = read_one_chunk(root, &found_key, leaf, chunk);
5977                         if (ret)
5978                                 goto error;
5979                 }
5980                 path->slots[0]++;
5981         }
5982         ret = 0;
5983 error:
5984         unlock_chunks(root);
5985         mutex_unlock(&uuid_mutex);
5986
5987         btrfs_free_path(path);
5988         return ret;
5989 }
5990
5991 void btrfs_init_devices_late(struct btrfs_fs_info *fs_info)
5992 {
5993         struct btrfs_fs_devices *fs_devices = fs_info->fs_devices;
5994         struct btrfs_device *device;
5995
5996         mutex_lock(&fs_devices->device_list_mutex);
5997         list_for_each_entry(device, &fs_devices->devices, dev_list)
5998                 device->dev_root = fs_info->dev_root;
5999         mutex_unlock(&fs_devices->device_list_mutex);
6000 }
6001
6002 static void __btrfs_reset_dev_stats(struct btrfs_device *dev)
6003 {
6004         int i;
6005
6006         for (i = 0; i < BTRFS_DEV_STAT_VALUES_MAX; i++)
6007                 btrfs_dev_stat_reset(dev, i);
6008 }
6009
6010 int btrfs_init_dev_stats(struct btrfs_fs_info *fs_info)
6011 {
6012         struct btrfs_key key;
6013         struct btrfs_key found_key;
6014         struct btrfs_root *dev_root = fs_info->dev_root;
6015         struct btrfs_fs_devices *fs_devices = fs_info->fs_devices;
6016         struct extent_buffer *eb;
6017         int slot;
6018         int ret = 0;
6019         struct btrfs_device *device;
6020         struct btrfs_path *path = NULL;
6021         int i;
6022
6023         path = btrfs_alloc_path();
6024         if (!path) {
6025                 ret = -ENOMEM;
6026                 goto out;
6027         }
6028
6029         mutex_lock(&fs_devices->device_list_mutex);
6030         list_for_each_entry(device, &fs_devices->devices, dev_list) {
6031                 int item_size;
6032                 struct btrfs_dev_stats_item *ptr;
6033
6034                 key.objectid = 0;
6035                 key.type = BTRFS_DEV_STATS_KEY;
6036                 key.offset = device->devid;
6037                 ret = btrfs_search_slot(NULL, dev_root, &key, path, 0, 0);
6038                 if (ret) {
6039                         __btrfs_reset_dev_stats(device);
6040                         device->dev_stats_valid = 1;
6041                         btrfs_release_path(path);
6042                         continue;
6043                 }
6044                 slot = path->slots[0];
6045                 eb = path->nodes[0];
6046                 btrfs_item_key_to_cpu(eb, &found_key, slot);
6047                 item_size = btrfs_item_size_nr(eb, slot);
6048
6049                 ptr = btrfs_item_ptr(eb, slot,
6050                                      struct btrfs_dev_stats_item);
6051
6052                 for (i = 0; i < BTRFS_DEV_STAT_VALUES_MAX; i++) {
6053                         if (item_size >= (1 + i) * sizeof(__le64))
6054                                 btrfs_dev_stat_set(device, i,
6055                                         btrfs_dev_stats_value(eb, ptr, i));
6056                         else
6057                                 btrfs_dev_stat_reset(device, i);
6058                 }
6059
6060                 device->dev_stats_valid = 1;
6061                 btrfs_dev_stat_print_on_load(device);
6062                 btrfs_release_path(path);
6063         }
6064         mutex_unlock(&fs_devices->device_list_mutex);
6065
6066 out:
6067         btrfs_free_path(path);
6068         return ret < 0 ? ret : 0;
6069 }
6070
6071 static int update_dev_stat_item(struct btrfs_trans_handle *trans,
6072                                 struct btrfs_root *dev_root,
6073                                 struct btrfs_device *device)
6074 {
6075         struct btrfs_path *path;
6076         struct btrfs_key key;
6077         struct extent_buffer *eb;
6078         struct btrfs_dev_stats_item *ptr;
6079         int ret;
6080         int i;
6081
6082         key.objectid = 0;
6083         key.type = BTRFS_DEV_STATS_KEY;
6084         key.offset = device->devid;
6085
6086         path = btrfs_alloc_path();
6087         BUG_ON(!path);
6088         ret = btrfs_search_slot(trans, dev_root, &key, path, -1, 1);
6089         if (ret < 0) {
6090                 printk_in_rcu(KERN_WARNING "btrfs: error %d while searching for dev_stats item for device %s!\n",
6091                               ret, rcu_str_deref(device->name));
6092                 goto out;
6093         }
6094
6095         if (ret == 0 &&
6096             btrfs_item_size_nr(path->nodes[0], path->slots[0]) < sizeof(*ptr)) {
6097                 /* need to delete old one and insert a new one */
6098                 ret = btrfs_del_item(trans, dev_root, path);
6099                 if (ret != 0) {
6100                         printk_in_rcu(KERN_WARNING "btrfs: delete too small dev_stats item for device %s failed %d!\n",
6101                                       rcu_str_deref(device->name), ret);
6102                         goto out;
6103                 }
6104                 ret = 1;
6105         }
6106
6107         if (ret == 1) {
6108                 /* need to insert a new item */
6109                 btrfs_release_path(path);
6110                 ret = btrfs_insert_empty_item(trans, dev_root, path,
6111                                               &key, sizeof(*ptr));
6112                 if (ret < 0) {
6113                         printk_in_rcu(KERN_WARNING "btrfs: insert dev_stats item for device %s failed %d!\n",
6114                                       rcu_str_deref(device->name), ret);
6115                         goto out;
6116                 }
6117         }
6118
6119         eb = path->nodes[0];
6120         ptr = btrfs_item_ptr(eb, path->slots[0], struct btrfs_dev_stats_item);
6121         for (i = 0; i < BTRFS_DEV_STAT_VALUES_MAX; i++)
6122                 btrfs_set_dev_stats_value(eb, ptr, i,
6123                                           btrfs_dev_stat_read(device, i));
6124         btrfs_mark_buffer_dirty(eb);
6125
6126 out:
6127         btrfs_free_path(path);
6128         return ret;
6129 }
6130
6131 /*
6132  * called from commit_transaction. Writes all changed device stats to disk.
6133  */
6134 int btrfs_run_dev_stats(struct btrfs_trans_handle *trans,
6135                         struct btrfs_fs_info *fs_info)
6136 {
6137         struct btrfs_root *dev_root = fs_info->dev_root;
6138         struct btrfs_fs_devices *fs_devices = fs_info->fs_devices;
6139         struct btrfs_device *device;
6140         int ret = 0;
6141
6142         mutex_lock(&fs_devices->device_list_mutex);
6143         list_for_each_entry(device, &fs_devices->devices, dev_list) {
6144                 if (!device->dev_stats_valid || !device->dev_stats_dirty)
6145                         continue;
6146
6147                 ret = update_dev_stat_item(trans, dev_root, device);
6148                 if (!ret)
6149                         device->dev_stats_dirty = 0;
6150         }
6151         mutex_unlock(&fs_devices->device_list_mutex);
6152
6153         return ret;
6154 }
6155
6156 void btrfs_dev_stat_inc_and_print(struct btrfs_device *dev, int index)
6157 {
6158         btrfs_dev_stat_inc(dev, index);
6159         btrfs_dev_stat_print_on_error(dev);
6160 }
6161
6162 static void btrfs_dev_stat_print_on_error(struct btrfs_device *dev)
6163 {
6164         if (!dev->dev_stats_valid)
6165                 return;
6166         printk_ratelimited_in_rcu(KERN_ERR
6167                            "btrfs: bdev %s errs: wr %u, rd %u, flush %u, corrupt %u, gen %u\n",
6168                            rcu_str_deref(dev->name),
6169                            btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_WRITE_ERRS),
6170                            btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_READ_ERRS),
6171                            btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_FLUSH_ERRS),
6172                            btrfs_dev_stat_read(dev,
6173                                                BTRFS_DEV_STAT_CORRUPTION_ERRS),
6174                            btrfs_dev_stat_read(dev,
6175                                                BTRFS_DEV_STAT_GENERATION_ERRS));
6176 }
6177
6178 static void btrfs_dev_stat_print_on_load(struct btrfs_device *dev)
6179 {
6180         int i;
6181
6182         for (i = 0; i < BTRFS_DEV_STAT_VALUES_MAX; i++)
6183                 if (btrfs_dev_stat_read(dev, i) != 0)
6184                         break;
6185         if (i == BTRFS_DEV_STAT_VALUES_MAX)
6186                 return; /* all values == 0, suppress message */
6187
6188         printk_in_rcu(KERN_INFO "btrfs: bdev %s errs: wr %u, rd %u, flush %u, corrupt %u, gen %u\n",
6189                rcu_str_deref(dev->name),
6190                btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_WRITE_ERRS),
6191                btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_READ_ERRS),
6192                btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_FLUSH_ERRS),
6193                btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_CORRUPTION_ERRS),
6194                btrfs_dev_stat_read(dev, BTRFS_DEV_STAT_GENERATION_ERRS));
6195 }
6196
6197 int btrfs_get_dev_stats(struct btrfs_root *root,
6198                         struct btrfs_ioctl_get_dev_stats *stats)
6199 {
6200         struct btrfs_device *dev;
6201         struct btrfs_fs_devices *fs_devices = root->fs_info->fs_devices;
6202         int i;
6203
6204         mutex_lock(&fs_devices->device_list_mutex);
6205         dev = btrfs_find_device(root->fs_info, stats->devid, NULL, NULL);
6206         mutex_unlock(&fs_devices->device_list_mutex);
6207
6208         if (!dev) {
6209                 printk(KERN_WARNING
6210                        "btrfs: get dev_stats failed, device not found\n");
6211                 return -ENODEV;
6212         } else if (!dev->dev_stats_valid) {
6213                 printk(KERN_WARNING
6214                        "btrfs: get dev_stats failed, not yet valid\n");
6215                 return -ENODEV;
6216         } else if (stats->flags & BTRFS_DEV_STATS_RESET) {
6217                 for (i = 0; i < BTRFS_DEV_STAT_VALUES_MAX; i++) {
6218                         if (stats->nr_items > i)
6219                                 stats->values[i] =
6220                                         btrfs_dev_stat_read_and_reset(dev, i);
6221                         else
6222                                 btrfs_dev_stat_reset(dev, i);
6223                 }
6224         } else {
6225                 for (i = 0; i < BTRFS_DEV_STAT_VALUES_MAX; i++)
6226                         if (stats->nr_items > i)
6227                                 stats->values[i] = btrfs_dev_stat_read(dev, i);
6228         }
6229         if (stats->nr_items > BTRFS_DEV_STAT_VALUES_MAX)
6230                 stats->nr_items = BTRFS_DEV_STAT_VALUES_MAX;
6231         return 0;
6232 }
6233
6234 int btrfs_scratch_superblock(struct btrfs_device *device)
6235 {
6236         struct buffer_head *bh;
6237         struct btrfs_super_block *disk_super;
6238
6239         bh = btrfs_read_dev_super(device->bdev);
6240         if (!bh)
6241                 return -EINVAL;
6242         disk_super = (struct btrfs_super_block *)bh->b_data;
6243
6244         memset(&disk_super->magic, 0, sizeof(disk_super->magic));
6245         set_buffer_dirty(bh);
6246         sync_dirty_buffer(bh);
6247         brelse(bh);
6248
6249         return 0;
6250 }