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