fs/btrfs/volumes.c

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