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 <asm/div64.h>
  27 #include "compat.h"
  28 #include "ctree.h"
  29 #include "extent_map.h"
  30 #include "disk-io.h"
  31 #include "transaction.h"
  32 #include "print-tree.h"
  33 #include "volumes.h"
  34 #include "async-thread.h"
  35
  36 static int init_first_rw_device(struct btrfs_trans_handle *trans,
  37                                 struct btrfs_root *root,
  38                                 struct btrfs_device *device);
  39 static int btrfs_relocate_sys_chunks(struct btrfs_root *root);
  40
  41 static DEFINE_MUTEX(uuid_mutex);
  42 static LIST_HEAD(fs_uuids);
  43
  44 static void lock_chunks(struct btrfs_root *root)
  45 {
  46         mutex_lock(&root->fs_info->chunk_mutex);
  47 }
  48
  49 static void unlock_chunks(struct btrfs_root *root)
  50 {
  51         mutex_unlock(&root->fs_info->chunk_mutex);
  52 }
  53
  54 static void free_fs_devices(struct btrfs_fs_devices *fs_devices)
  55 {
  56         struct btrfs_device *device;
  57         WARN_ON(fs_devices->opened);
  58         while (!list_empty(&fs_devices->devices)) {
  59                 device = list_entry(fs_devices->devices.next,
  60                                     struct btrfs_device, dev_list);
  61                 list_del(&device->dev_list);
  62                 kfree(device->name);
  63                 kfree(device);
  64         }
  65         kfree(fs_devices);
  66 }
  67
  68 int btrfs_cleanup_fs_uuids(void)
  69 {
  70         struct btrfs_fs_devices *fs_devices;
  71
  72         while (!list_empty(&fs_uuids)) {
  73                 fs_devices = list_entry(fs_uuids.next,
  74                                         struct btrfs_fs_devices, list);
  75                 list_del(&fs_devices->list);
  76                 free_fs_devices(fs_devices);
  77         }
  78         return 0;
  79 }
  80
  81 static noinline struct btrfs_device *__find_device(struct list_head *head,
  82                                                    u64 devid, u8 *uuid)
  83 {
  84         struct btrfs_device *dev;
  85
  86         list_for_each_entry(dev, head, dev_list) {
  87                 if (dev->devid == devid &&
  88                     (!uuid || !memcmp(dev->uuid, uuid, BTRFS_UUID_SIZE))) {
  89                         return dev;
  90                 }
  91         }
  92         return NULL;
  93 }
  94
  95 static noinline struct btrfs_fs_devices *find_fsid(u8 *fsid)
  96 {
  97         struct btrfs_fs_devices *fs_devices;
  98
  99         list_for_each_entry(fs_devices, &fs_uuids, list) {
 100                 if (memcmp(fsid, fs_devices->fsid, BTRFS_FSID_SIZE) == 0)
 101                         return fs_devices;
 102         }
 103         return NULL;
 104 }
 105
 106 static void requeue_list(struct btrfs_pending_bios *pending_bios,
 107                         struct bio *head, struct bio *tail)
 108 {
 109
 110         struct bio *old_head;
 111
 112         old_head = pending_bios->head;
 113         pending_bios->head = head;
 114         if (pending_bios->tail)
 115                 tail->bi_next = old_head;
 116         else
 117                 pending_bios->tail = tail;
 118 }
 119
 120 /*
 121  * we try to collect pending bios for a device so we don't get a large
 122  * number of procs sending bios down to the same device.  This greatly
 123  * improves the schedulers ability to collect and merge the bios.
 124  *
 125  * But, it also turns into a long list of bios to process and that is sure
 126  * to eventually make the worker thread block.  The solution here is to
 127  * make some progress and then put this work struct back at the end of
 128  * the list if the block device is congested.  This way, multiple devices
 129  * can make progress from a single worker thread.
 130  */
 131 static noinline int run_scheduled_bios(struct btrfs_device *device)
 132 {
 133         struct bio *pending;
 134         struct backing_dev_info *bdi;
 135         struct btrfs_fs_info *fs_info;
 136         struct btrfs_pending_bios *pending_bios;
 137         struct bio *tail;
 138         struct bio *cur;
 139         int again = 0;
 140         unsigned long num_run;
 141         unsigned long batch_run = 0;
 142         unsigned long limit;
 143         unsigned long last_waited = 0;
 144         int force_reg = 0;
 145         int sync_pending = 0;
 146         struct blk_plug plug;
 147
 148         /*
 149          * this function runs all the bios we've collected for
 150          * a particular device.  We don't want to wander off to
 151          * another device without first sending all of these down.
 152          * So, setup a plug here and finish it off before we return
 153          */
 154         blk_start_plug(&plug);
 155
 156         bdi = blk_get_backing_dev_info(device->bdev);
 157         fs_info = device->dev_root->fs_info;
 158         limit = btrfs_async_submit_limit(fs_info);
 159         limit = limit * 2 / 3;
 160
 161 loop:
 162         spin_lock(&device->io_lock);
 163
 164 loop_lock:
 165         num_run = 0;
 166
 167         /* take all the bios off the list at once and process them
 168          * later on (without the lock held).  But, remember the
 169          * tail and other pointers so the bios can be properly reinserted
 170          * into the list if we hit congestion
 171          */
 172         if (!force_reg && device->pending_sync_bios.head) {
 173                 pending_bios = &device->pending_sync_bios;
 174                 force_reg = 1;
 175         } else {
 176                 pending_bios = &device->pending_bios;
 177                 force_reg = 0;
 178         }
 179
 180         pending = pending_bios->head;
 181         tail = pending_bios->tail;
 182         WARN_ON(pending && !tail);
 183
 184         /*
 185          * if pending was null this time around, no bios need processing
 186          * at all and we can stop.  Otherwise it'll loop back up again
 187          * and do an additional check so no bios are missed.
 188          *
 189          * device->running_pending is used to synchronize with the
 190          * schedule_bio code.
 191          */
 192         if (device->pending_sync_bios.head == NULL &&
 193             device->pending_bios.head == NULL) {
 194                 again = 0;
 195                 device->running_pending = 0;
 196         } else {
 197                 again = 1;
 198                 device->running_pending = 1;
 199         }
 200
 201         pending_bios->head = NULL;
 202         pending_bios->tail = NULL;
 203
 204         spin_unlock(&device->io_lock);
 205
 206         while (pending) {
 207
 208                 rmb();
 209                 /* we want to work on both lists, but do more bios on the
 210                  * sync list than the regular list
 211                  */
 212                 if ((num_run > 32 &&
 213                     pending_bios != &device->pending_sync_bios &&
 214                     device->pending_sync_bios.head) ||
 215                    (num_run > 64 && pending_bios == &device->pending_sync_bios &&
 216                     device->pending_bios.head)) {
 217                         spin_lock(&device->io_lock);
 218                         requeue_list(pending_bios, pending, tail);
 219                         goto loop_lock;
 220                 }
 221
 222                 cur = pending;
 223                 pending = pending->bi_next;
 224                 cur->bi_next = NULL;
 225                 atomic_dec(&fs_info->nr_async_bios);
 226
 227                 if (atomic_read(&fs_info->nr_async_bios) < limit &&
 228                     waitqueue_active(&fs_info->async_submit_wait))
 229                         wake_up(&fs_info->async_submit_wait);
 230
 231                 BUG_ON(atomic_read(&cur->bi_cnt) == 0);
 232
 233                 /*
 234                  * if we're doing the sync list, record that our
 235                  * plug has some sync requests on it
 236                  *
 237                  * If we're doing the regular list and there are
 238                  * sync requests sitting around, unplug before
 239                  * we add more
 240                  */
 241                 if (pending_bios == &device->pending_sync_bios) {
 242                         sync_pending = 1;
 243                 } else if (sync_pending) {
 244                         blk_finish_plug(&plug);
 245                         blk_start_plug(&plug);
 246                         sync_pending = 0;
 247                 }
 248
 249                 submit_bio(cur->bi_rw, cur);
 250                 num_run++;
 251                 batch_run++;
 252                 if (need_resched())
 253                         cond_resched();
 254
 255                 /*
 256                  * we made progress, there is more work to do and the bdi
 257                  * is now congested.  Back off and let other work structs
 258                  * run instead
 259                  */
 260                 if (pending && bdi_write_congested(bdi) && batch_run > 8 &&
 261                     fs_info->fs_devices->open_devices > 1) {
 262                         struct io_context *ioc;
 263
 264                         ioc = current->io_context;
 265
 266                         /*
 267                          * the main goal here is that we don't want to
 268                          * block if we're going to be able to submit
 269                          * more requests without blocking.
 270                          *
 271                          * This code does two great things, it pokes into
 272                          * the elevator code from a filesystem _and_
 273                          * it makes assumptions about how batching works.
 274                          */
 275                         if (ioc && ioc->nr_batch_requests > 0 &&
 276                             time_before(jiffies, ioc->last_waited + HZ/50UL) &&
 277                             (last_waited == 0 ||
 278                              ioc->last_waited == last_waited)) {
 279                                 /*
 280                                  * we want to go through our batch of
 281                                  * requests and stop.  So, we copy out
 282                                  * the ioc->last_waited time and test
 283                                  * against it before looping
 284                                  */
 285                                 last_waited = ioc->last_waited;
 286                                 if (need_resched())
 287                                         cond_resched();
 288                                 continue;
 289                         }
 290                         spin_lock(&device->io_lock);
 291                         requeue_list(pending_bios, pending, tail);
 292                         device->running_pending = 1;
 293
 294                         spin_unlock(&device->io_lock);
 295                         btrfs_requeue_work(&device->work);
 296                         goto done;
 297                 }
 298                 /* unplug every 64 requests just for good measure */
 299                 if (batch_run % 64 == 0) {
 300                         blk_finish_plug(&plug);
 301                         blk_start_plug(&plug);
 302                         sync_pending = 0;
 303                 }
 304         }
 305
 306         cond_resched();
 307         if (again)
 308                 goto loop;
 309
 310         spin_lock(&device->io_lock);
 311         if (device->pending_bios.head || device->pending_sync_bios.head)
 312                 goto loop_lock;
 313         spin_unlock(&device->io_lock);
 314
 315 done:
 316         blk_finish_plug(&plug);
 317         return 0;
 318 }
 319
 320 static void pending_bios_fn(struct btrfs_work *work)
 321 {
 322         struct btrfs_device *device;
 323
 324         device = container_of(work, struct btrfs_device, work);
 325         run_scheduled_bios(device);
 326 }
 327
 328 static noinline int device_list_add(const char *path,
 329                            struct btrfs_super_block *disk_super,
 330                            u64 devid, struct btrfs_fs_devices **fs_devices_ret)
 331 {
 332         struct btrfs_device *device;
 333         struct btrfs_fs_devices *fs_devices;
 334         u64 found_transid = btrfs_super_generation(disk_super);
 335         char *name;
 336
 337         fs_devices = find_fsid(disk_super->fsid);
 338         if (!fs_devices) {
 339                 fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
 340                 if (!fs_devices)
 341                         return -ENOMEM;
 342                 INIT_LIST_HEAD(&fs_devices->devices);
 343                 INIT_LIST_HEAD(&fs_devices->alloc_list);
 344                 list_add(&fs_devices->list, &fs_uuids);
 345                 memcpy(fs_devices->fsid, disk_super->fsid, BTRFS_FSID_SIZE);
 346                 fs_devices->latest_devid = devid;
 347                 fs_devices->latest_trans = found_transid;
 348                 mutex_init(&fs_devices->device_list_mutex);
 349                 device = NULL;
 350         } else {
 351                 device = __find_device(&fs_devices->devices, devid,
 352                                        disk_super->dev_item.uuid);
 353         }
 354         if (!device) {
 355                 if (fs_devices->opened)
 356                         return -EBUSY;
 357
 358                 device = kzalloc(sizeof(*device), GFP_NOFS);
 359                 if (!device) {
 360                         /* we can safely leave the fs_devices entry around */
 361                         return -ENOMEM;
 362                 }
 363                 device->devid = devid;
 364                 device->work.func = pending_bios_fn;
 365                 memcpy(device->uuid, disk_super->dev_item.uuid,
 366                        BTRFS_UUID_SIZE);
 367                 spin_lock_init(&device->io_lock);
 368                 device->name = kstrdup(path, GFP_NOFS);
 369                 if (!device->name) {
 370                         kfree(device);
 371                         return -ENOMEM;
 372                 }
 373                 INIT_LIST_HEAD(&device->dev_alloc_list);
 374
 375                 /* init readahead state */
 376                 spin_lock_init(&device->reada_lock);
 377                 device->reada_curr_zone = NULL;
 378                 atomic_set(&device->reada_in_flight, 0);
 379                 device->reada_next = 0;
 380                 INIT_RADIX_TREE(&device->reada_zones, GFP_NOFS & ~__GFP_WAIT);
 381                 INIT_RADIX_TREE(&device->reada_extents, GFP_NOFS & ~__GFP_WAIT);
 382
 383                 mutex_lock(&fs_devices->device_list_mutex);
 384                 list_add_rcu(&device->dev_list, &fs_devices->devices);
 385                 mutex_unlock(&fs_devices->device_list_mutex);
 386
 387                 device->fs_devices = fs_devices;
 388                 fs_devices->num_devices++;
 389         } else if (!device->name || strcmp(device->name, path)) {
 390                 name = kstrdup(path, GFP_NOFS);
 391                 if (!name)
 392                         return -ENOMEM;
 393                 kfree(device->name);
 394                 device->name = name;
 395                 if (device->missing) {
 396                         fs_devices->missing_devices--;
 397                         device->missing = 0;
 398                 }
 399         }
 400
 401         if (found_transid > fs_devices->latest_trans) {
 402                 fs_devices->latest_devid = devid;
 403                 fs_devices->latest_trans = found_transid;
 404         }
 405         *fs_devices_ret = fs_devices;
 406         return 0;
 407 }
 408
 409 static struct btrfs_fs_devices *clone_fs_devices(struct btrfs_fs_devices *orig)
 410 {
 411         struct btrfs_fs_devices *fs_devices;
 412         struct btrfs_device *device;
 413         struct btrfs_device *orig_dev;
 414
 415         fs_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
 416         if (!fs_devices)
 417                 return ERR_PTR(-ENOMEM);
 418
 419         INIT_LIST_HEAD(&fs_devices->devices);
 420         INIT_LIST_HEAD(&fs_devices->alloc_list);
 421         INIT_LIST_HEAD(&fs_devices->list);
 422         mutex_init(&fs_devices->device_list_mutex);
 423         fs_devices->latest_devid = orig->latest_devid;
 424         fs_devices->latest_trans = orig->latest_trans;
 425         memcpy(fs_devices->fsid, orig->fsid, sizeof(fs_devices->fsid));
 426
 427         /* We have held the volume lock, it is safe to get the devices. */
 428         list_for_each_entry(orig_dev, &orig->devices, dev_list) {
 429                 device = kzalloc(sizeof(*device), GFP_NOFS);
 430                 if (!device)
 431                         goto error;
 432
 433                 device->name = kstrdup(orig_dev->name, GFP_NOFS);
 434                 if (!device->name) {
 435                         kfree(device);
 436                         goto error;
 437                 }
 438
 439                 device->devid = orig_dev->devid;
 440                 device->work.func = pending_bios_fn;
 441                 memcpy(device->uuid, orig_dev->uuid, sizeof(device->uuid));
 442                 spin_lock_init(&device->io_lock);
 443                 INIT_LIST_HEAD(&device->dev_list);
 444                 INIT_LIST_HEAD(&device->dev_alloc_list);
 445
 446                 list_add(&device->dev_list, &fs_devices->devices);
 447                 device->fs_devices = fs_devices;
 448                 fs_devices->num_devices++;
 449         }
 450         return fs_devices;
 451 error:
 452         free_fs_devices(fs_devices);
 453         return ERR_PTR(-ENOMEM);
 454 }
 455
 456 int btrfs_close_extra_devices(struct btrfs_fs_devices *fs_devices)
 457 {
 458         struct btrfs_device *device, *next;
 459
 460         mutex_lock(&uuid_mutex);
 461 again:
 462         /* This is the initialized path, it is safe to release the devices. */
 463         list_for_each_entry_safe(device, next, &fs_devices->devices, dev_list) {
 464                 if (device->in_fs_metadata)
 465                         continue;
 466
 467                 if (device->bdev) {
 468                         blkdev_put(device->bdev, device->mode);
 469                         device->bdev = NULL;
 470                         fs_devices->open_devices--;
 471                 }
 472                 if (device->writeable) {
 473                         list_del_init(&device->dev_alloc_list);
 474                         device->writeable = 0;
 475                         fs_devices->rw_devices--;
 476                 }
 477                 list_del_init(&device->dev_list);
 478                 fs_devices->num_devices--;
 479                 kfree(device->name);
 480                 kfree(device);
 481         }
 482
 483         if (fs_devices->seed) {
 484                 fs_devices = fs_devices->seed;
 485                 goto again;
 486         }
 487
 488         mutex_unlock(&uuid_mutex);
 489         return 0;
 490 }
 491
 492 static void __free_device(struct work_struct *work)
 493 {
 494         struct btrfs_device *device;
 495
 496         device = container_of(work, struct btrfs_device, rcu_work);
 497
 498         if (device->bdev)
 499                 blkdev_put(device->bdev, device->mode);
 500
 501         kfree(device->name);
 502         kfree(device);
 503 }
 504
 505 static void free_device(struct rcu_head *head)
 506 {
 507         struct btrfs_device *device;
 508
 509         device = container_of(head, struct btrfs_device, rcu);
 510
 511         INIT_WORK(&device->rcu_work, __free_device);
 512         schedule_work(&device->rcu_work);
 513 }
 514
 515 static int __btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 516 {
 517         struct btrfs_device *device;
 518
 519         if (--fs_devices->opened > 0)
 520                 return 0;
 521
 522         mutex_lock(&fs_devices->device_list_mutex);
 523         list_for_each_entry(device, &fs_devices->devices, dev_list) {
 524                 struct btrfs_device *new_device;
 525
 526                 if (device->bdev)
 527                         fs_devices->open_devices--;
 528
 529                 if (device->writeable) {
 530                         list_del_init(&device->dev_alloc_list);
 531                         fs_devices->rw_devices--;
 532                 }
 533
 534                 if (device->can_discard)
 535                         fs_devices->num_can_discard--;
 536
 537                 new_device = kmalloc(sizeof(*new_device), GFP_NOFS);
 538                 BUG_ON(!new_device);
 539                 memcpy(new_device, device, sizeof(*new_device));
 540                 new_device->name = kstrdup(device->name, GFP_NOFS);
 541                 BUG_ON(device->name && !new_device->name);
 542                 new_device->bdev = NULL;
 543                 new_device->writeable = 0;
 544                 new_device->in_fs_metadata = 0;
 545                 new_device->can_discard = 0;
 546                 spin_lock_init(&new_device->io_lock);
 547                 list_replace_rcu(&device->dev_list, &new_device->dev_list);
 548
 549                 call_rcu(&device->rcu, free_device);
 550         }
 551         mutex_unlock(&fs_devices->device_list_mutex);
 552
 553         WARN_ON(fs_devices->open_devices);
 554         WARN_ON(fs_devices->rw_devices);
 555         fs_devices->opened = 0;
 556         fs_devices->seeding = 0;
 557
 558         return 0;
 559 }
 560
 561 int btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 562 {
 563         struct btrfs_fs_devices *seed_devices = NULL;
 564         int ret;
 565
 566         mutex_lock(&uuid_mutex);
 567         ret = __btrfs_close_devices(fs_devices);
 568         if (!fs_devices->opened) {
 569                 seed_devices = fs_devices->seed;
 570                 fs_devices->seed = NULL;
 571         }
 572         mutex_unlock(&uuid_mutex);
 573
 574         while (seed_devices) {
 575                 fs_devices = seed_devices;
 576                 seed_devices = fs_devices->seed;
 577                 __btrfs_close_devices(fs_devices);
 578                 free_fs_devices(fs_devices);
 579         }
 580         /*
 581          * Wait for rcu kworkers under __btrfs_close_devices
 582          * to finish all blkdev_puts so device is really
 583          * free when umount is done.
 584          */
 585         rcu_barrier();
 586         return ret;
 587 }
 588
 589 static int __btrfs_open_devices(struct btrfs_fs_devices *fs_devices,
 590                                 fmode_t flags, void *holder)
 591 {
 592         struct request_queue *q;
 593         struct block_device *bdev;
 594         struct list_head *head = &fs_devices->devices;
 595         struct btrfs_device *device;
 596         struct block_device *latest_bdev = NULL;
 597         struct buffer_head *bh;
 598         struct btrfs_super_block *disk_super;
 599         u64 latest_devid = 0;
 600         u64 latest_transid = 0;
 601         u64 devid;
 602         int seeding = 1;
 603         int ret = 0;
 604
 605         flags |= FMODE_EXCL;
 606
 607         list_for_each_entry(device, head, dev_list) {
 608                 if (device->bdev)
 609                         continue;
 610                 if (!device->name)
 611                         continue;
 612
 613                 bdev = blkdev_get_by_path(device->name, flags, holder);
 614                 if (IS_ERR(bdev)) {
 615                         printk(KERN_INFO "open %s failed\n", device->name);
 616                         goto error;
 617                 }
 618                 set_blocksize(bdev, 4096);
 619
 620                 bh = btrfs_read_dev_super(bdev);
 621                 if (!bh)
 622                         goto error_close;
 623
 624                 disk_super = (struct btrfs_super_block *)bh->b_data;
 625                 devid = btrfs_stack_device_id(&disk_super->dev_item);
 626                 if (devid != device->devid)
 627                         goto error_brelse;
 628
 629                 if (memcmp(device->uuid, disk_super->dev_item.uuid,
 630                            BTRFS_UUID_SIZE))
 631                         goto error_brelse;
 632
 633                 device->generation = btrfs_super_generation(disk_super);
 634                 if (!latest_transid || device->generation > latest_transid) {
 635                         latest_devid = devid;
 636                         latest_transid = device->generation;
 637                         latest_bdev = bdev;
 638                 }
 639
 640                 if (btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_SEEDING) {
 641                         device->writeable = 0;
 642                 } else {
 643                         device->writeable = !bdev_read_only(bdev);
 644                         seeding = 0;
 645                 }
 646
 647                 q = bdev_get_queue(bdev);
 648                 if (blk_queue_discard(q)) {
 649                         device->can_discard = 1;
 650                         fs_devices->num_can_discard++;
 651                 }
 652
 653                 device->bdev = bdev;
 654                 device->in_fs_metadata = 0;
 655                 device->mode = flags;
 656
 657                 if (!blk_queue_nonrot(bdev_get_queue(bdev)))
 658                         fs_devices->rotating = 1;
 659
 660                 fs_devices->open_devices++;
 661                 if (device->writeable) {
 662                         fs_devices->rw_devices++;
 663                         list_add(&device->dev_alloc_list,
 664                                  &fs_devices->alloc_list);
 665                 }
 666                 brelse(bh);
 667                 continue;
 668
 669 error_brelse:
 670                 brelse(bh);
 671 error_close:
 672                 blkdev_put(bdev, flags);
 673 error:
 674                 continue;
 675         }
 676         if (fs_devices->open_devices == 0) {
 677                 ret = -EINVAL;
 678                 goto out;
 679         }
 680         fs_devices->seeding = seeding;
 681         fs_devices->opened = 1;
 682         fs_devices->latest_bdev = latest_bdev;
 683         fs_devices->latest_devid = latest_devid;
 684         fs_devices->latest_trans = latest_transid;
 685         fs_devices->total_rw_bytes = 0;
 686 out:
 687         return ret;
 688 }
 689
 690 int btrfs_open_devices(struct btrfs_fs_devices *fs_devices,
 691                        fmode_t flags, void *holder)
 692 {
 693         int ret;
 694
 695         mutex_lock(&uuid_mutex);
 696         if (fs_devices->opened) {
 697                 fs_devices->opened++;
 698                 ret = 0;
 699         } else {
 700                 ret = __btrfs_open_devices(fs_devices, flags, holder);
 701         }
 702         mutex_unlock(&uuid_mutex);
 703         return ret;
 704 }
 705
 706 int btrfs_scan_one_device(const char *path, fmode_t flags, void *holder,
 707                           struct btrfs_fs_devices **fs_devices_ret)
 708 {
 709         struct btrfs_super_block *disk_super;
 710         struct block_device *bdev;
 711         struct buffer_head *bh;
 712         int ret;
 713         u64 devid;
 714         u64 transid;
 715
 716         mutex_lock(&uuid_mutex);
 717
 718         flags |= FMODE_EXCL;
 719         bdev = blkdev_get_by_path(path, flags, holder);
 720
 721         if (IS_ERR(bdev)) {
 722                 ret = PTR_ERR(bdev);
 723                 goto error;
 724         }
 725
 726         ret = set_blocksize(bdev, 4096);
 727         if (ret)
 728                 goto error_close;
 729         bh = btrfs_read_dev_super(bdev);
 730         if (!bh) {
 731                 ret = -EINVAL;
 732                 goto error_close;
 733         }
 734         disk_super = (struct btrfs_super_block *)bh->b_data;
 735         devid = btrfs_stack_device_id(&disk_super->dev_item);
 736         transid = btrfs_super_generation(disk_super);
 737         if (disk_super->label[0])
 738                 printk(KERN_INFO "device label %s ", disk_super->label);
 739         else
 740                 printk(KERN_INFO "device fsid %pU ", disk_super->fsid);
 741         printk(KERN_CONT "devid %llu transid %llu %s\n",
 742                (unsigned long long)devid, (unsigned long long)transid, path);
 743         ret = device_list_add(path, disk_super, devid, fs_devices_ret);
 744
 745         brelse(bh);
 746 error_close:
 747         blkdev_put(bdev, flags);
 748 error:
 749         mutex_unlock(&uuid_mutex);
 750         return ret;
 751 }
 752
 753 /* helper to account the used device space in the range */
 754 int btrfs_account_dev_extents_size(struct btrfs_device *device, u64 start,
 755                                    u64 end, u64 *length)
 756 {
 757         struct btrfs_key key;
 758         struct btrfs_root *root = device->dev_root;
 759         struct btrfs_dev_extent *dev_extent;
 760         struct btrfs_path *path;
 761         u64 extent_end;
 762         int ret;
 763         int slot;
 764         struct extent_buffer *l;
 765
 766         *length = 0;
 767
 768         if (start >= device->total_bytes)
 769                 return 0;
 770
 771         path = btrfs_alloc_path();
 772         if (!path)
 773                 return -ENOMEM;
 774         path->reada = 2;
 775
 776         key.objectid = device->devid;
 777         key.offset = start;
 778         key.type = BTRFS_DEV_EXTENT_KEY;
 779
 780         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 781         if (ret < 0)
 782                 goto out;
 783         if (ret > 0) {
 784                 ret = btrfs_previous_item(root, path, key.objectid, key.type);
 785                 if (ret < 0)
 786                         goto out;
 787         }
 788
 789         while (1) {
 790                 l = path->nodes[0];
 791                 slot = path->slots[0];
 792                 if (slot >= btrfs_header_nritems(l)) {
 793                         ret = btrfs_next_leaf(root, path);
 794                         if (ret == 0)
 795                                 continue;
 796                         if (ret < 0)
 797                                 goto out;
 798
 799                         break;
 800                 }
 801                 btrfs_item_key_to_cpu(l, &key, slot);
 802
 803                 if (key.objectid < device->devid)
 804                         goto next;
 805
 806                 if (key.objectid > device->devid)
 807                         break;
 808
 809                 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
 810                         goto next;
 811
 812                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 813                 extent_end = key.offset + btrfs_dev_extent_length(l,
 814                                                                   dev_extent);
 815                 if (key.offset <= start && extent_end > end) {
 816                         *length = end - start + 1;
 817                         break;
 818                 } else if (key.offset <= start && extent_end > start)
 819                         *length += extent_end - start;
 820                 else if (key.offset > start && extent_end <= end)
 821                         *length += extent_end - key.offset;
 822                 else if (key.offset > start && key.offset <= end) {
 823                         *length += end - key.offset + 1;
 824                         break;
 825                 } else if (key.offset > end)
 826                         break;
 827
 828 next:
 829                 path->slots[0]++;
 830         }
 831         ret = 0;
 832 out:
 833         btrfs_free_path(path);
 834         return ret;
 835 }
 836
 837 /*
 838  * find_free_dev_extent - find free space in the specified device
 839  * @trans:      transaction handler
 840  * @device:     the device which we search the free space in
 841  * @num_bytes:  the size of the free space that we need
 842  * @start:      store the start of the free space.
 843  * @len:        the size of the free space. that we find, or the size of the max
 844  *              free space if we don't find suitable free space
 845  *
 846  * this uses a pretty simple search, the expectation is that it is
 847  * called very infrequently and that a given device has a small number
 848  * of extents
 849  *
 850  * @start is used to store the start of the free space if we find. But if we
 851  * don't find suitable free space, it will be used to store the start position
 852  * of the max free space.
 853  *
 854  * @len is used to store the size of the free space that we find.
 855  * But if we don't find suitable free space, it is used to store the size of
 856  * the max free space.
 857  */
 858 int find_free_dev_extent(struct btrfs_trans_handle *trans,
 859                          struct btrfs_device *device, u64 num_bytes,
 860                          u64 *start, u64 *len)
 861 {
 862         struct btrfs_key key;
 863         struct btrfs_root *root = device->dev_root;
 864         struct btrfs_dev_extent *dev_extent;
 865         struct btrfs_path *path;
 866         u64 hole_size;
 867         u64 max_hole_start;
 868         u64 max_hole_size;
 869         u64 extent_end;
 870         u64 search_start;
 871         u64 search_end = device->total_bytes;
 872         int ret;
 873         int slot;
 874         struct extent_buffer *l;
 875
 876         /* FIXME use last free of some kind */
 877
 878         /* we don't want to overwrite the superblock on the drive,
 879          * so we make sure to start at an offset of at least 1MB
 880          */
 881         search_start = max(root->fs_info->alloc_start, 1024ull * 1024);
 882
 883         max_hole_start = search_start;
 884         max_hole_size = 0;
 885         hole_size = 0;
 886
 887         if (search_start >= search_end) {
 888                 ret = -ENOSPC;
 889                 goto error;
 890         }
 891
 892         path = btrfs_alloc_path();
 893         if (!path) {
 894                 ret = -ENOMEM;
 895                 goto error;
 896         }
 897         path->reada = 2;
 898
 899         key.objectid = device->devid;
 900         key.offset = search_start;
 901         key.type = BTRFS_DEV_EXTENT_KEY;
 902
 903         ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
 904         if (ret < 0)
 905                 goto out;
 906         if (ret > 0) {
 907                 ret = btrfs_previous_item(root, path, key.objectid, key.type);
 908                 if (ret < 0)
 909                         goto out;
 910         }
 911
 912         while (1) {
 913                 l = path->nodes[0];
 914                 slot = path->slots[0];
 915                 if (slot >= btrfs_header_nritems(l)) {
 916                         ret = btrfs_next_leaf(root, path);
 917                         if (ret == 0)
 918                                 continue;
 919                         if (ret < 0)
 920                                 goto out;
 921
 922                         break;
 923                 }
 924                 btrfs_item_key_to_cpu(l, &key, slot);
 925
 926                 if (key.objectid < device->devid)
 927                         goto next;
 928
 929                 if (key.objectid > device->devid)
 930                         break;
 931
 932                 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY)
 933                         goto next;
 934
 935                 if (key.offset > search_start) {
 936                         hole_size = key.offset - search_start;
 937
 938                         if (hole_size > max_hole_size) {
 939                                 max_hole_start = search_start;
 940                                 max_hole_size = hole_size;
 941                         }
 942
 943                         /*
 944                          * If this free space is greater than which we need,
 945                          * it must be the max free space that we have found
 946                          * until now, so max_hole_start must point to the start
 947                          * of this free space and the length of this free space
 948                          * is stored in max_hole_size. Thus, we return
 949                          * max_hole_start and max_hole_size and go back to the
 950                          * caller.
 951                          */
 952                         if (hole_size >= num_bytes) {
 953                                 ret = 0;
 954                                 goto out;
 955                         }
 956                 }
 957
 958                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 959                 extent_end = key.offset + btrfs_dev_extent_length(l,
 960                                                                   dev_extent);
 961                 if (extent_end > search_start)
 962                         search_start = extent_end;
 963 next:
 964                 path->slots[0]++;
 965                 cond_resched();
 966         }
 967
 968         /*
 969          * At this point, search_start should be the end of
 970          * allocated dev extents, and when shrinking the device,
 971          * search_end may be smaller than search_start.
 972          */
 973         if (search_end > search_start)
 974                 hole_size = search_end - search_start;
 975
 976         if (hole_size > max_hole_size) {
 977                 max_hole_start = search_start;
 978                 max_hole_size = hole_size;
 979         }
 980
 981         /* See above. */
 982         if (hole_size < num_bytes)
 983                 ret = -ENOSPC;
 984         else
 985                 ret = 0;
 986
 987 out:
 988         btrfs_free_path(path);
 989 error:
 990         *start = max_hole_start;
 991         if (len)
 992                 *len = max_hole_size;
 993         return ret;
 994 }
 995
 996 static int btrfs_free_dev_extent(struct btrfs_trans_handle *trans,
 997                           struct btrfs_device *device,
 998                           u64 start)
 999 {
1000         int ret;
1001         struct btrfs_path *path;
1002         struct btrfs_root *root = device->dev_root;
1003         struct btrfs_key key;
1004         struct btrfs_key found_key;
1005         struct extent_buffer *leaf = NULL;
1006         struct btrfs_dev_extent *extent = NULL;
1007
1008         path = btrfs_alloc_path();
1009         if (!path)
1010                 return -ENOMEM;
1011
1012         key.objectid = device->devid;
1013         key.offset = start;
1014         key.type = BTRFS_DEV_EXTENT_KEY;
1015 again:
1016         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1017         if (ret > 0) {
1018                 ret = btrfs_previous_item(root, path, key.objectid,
1019                                           BTRFS_DEV_EXTENT_KEY);
1020                 if (ret)
1021                         goto out;
1022                 leaf = path->nodes[0];
1023                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1024                 extent = btrfs_item_ptr(leaf, path->slots[0],
1025                                         struct btrfs_dev_extent);
1026                 BUG_ON(found_key.offset > start || found_key.offset +
1027                        btrfs_dev_extent_length(leaf, extent) < start);
1028                 key = found_key;
1029                 btrfs_release_path(path);
1030                 goto again;
1031         } else if (ret == 0) {
1032                 leaf = path->nodes[0];
1033                 extent = btrfs_item_ptr(leaf, path->slots[0],
1034                                         struct btrfs_dev_extent);
1035         }
1036         BUG_ON(ret);
1037
1038         if (device->bytes_used > 0) {
1039                 u64 len = btrfs_dev_extent_length(leaf, extent);
1040                 device->bytes_used -= len;
1041                 spin_lock(&root->fs_info->free_chunk_lock);
1042                 root->fs_info->free_chunk_space += len;
1043                 spin_unlock(&root->fs_info->free_chunk_lock);
1044         }
1045         ret = btrfs_del_item(trans, root, path);
1046
1047 out:
1048         btrfs_free_path(path);
1049         return ret;
1050 }
1051
1052 int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
1053                            struct btrfs_device *device,
1054                            u64 chunk_tree, u64 chunk_objectid,
1055                            u64 chunk_offset, u64 start, u64 num_bytes)
1056 {
1057         int ret;
1058         struct btrfs_path *path;
1059         struct btrfs_root *root = device->dev_root;
1060         struct btrfs_dev_extent *extent;
1061         struct extent_buffer *leaf;
1062         struct btrfs_key key;
1063
1064         WARN_ON(!device->in_fs_metadata);
1065         path = btrfs_alloc_path();
1066         if (!path)
1067                 return -ENOMEM;
1068
1069         key.objectid = device->devid;
1070         key.offset = start;
1071         key.type = BTRFS_DEV_EXTENT_KEY;
1072         ret = btrfs_insert_empty_item(trans, root, path, &key,
1073                                       sizeof(*extent));
1074         BUG_ON(ret);
1075
1076         leaf = path->nodes[0];
1077         extent = btrfs_item_ptr(leaf, path->slots[0],
1078                                 struct btrfs_dev_extent);
1079         btrfs_set_dev_extent_chunk_tree(leaf, extent, chunk_tree);
1080         btrfs_set_dev_extent_chunk_objectid(leaf, extent, chunk_objectid);
1081         btrfs_set_dev_extent_chunk_offset(leaf, extent, chunk_offset);
1082
1083         write_extent_buffer(leaf, root->fs_info->chunk_tree_uuid,
1084                     (unsigned long)btrfs_dev_extent_chunk_tree_uuid(extent),
1085                     BTRFS_UUID_SIZE);
1086
1087         btrfs_set_dev_extent_length(leaf, extent, num_bytes);
1088         btrfs_mark_buffer_dirty(leaf);
1089         btrfs_free_path(path);
1090         return ret;
1091 }
1092
1093 static noinline int find_next_chunk(struct btrfs_root *root,
1094                                     u64 objectid, u64 *offset)
1095 {
1096         struct btrfs_path *path;
1097         int ret;
1098         struct btrfs_key key;
1099         struct btrfs_chunk *chunk;
1100         struct btrfs_key found_key;
1101
1102         path = btrfs_alloc_path();
1103         if (!path)
1104                 return -ENOMEM;
1105
1106         key.objectid = objectid;
1107         key.offset = (u64)-1;
1108         key.type = BTRFS_CHUNK_ITEM_KEY;
1109
1110         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1111         if (ret < 0)
1112                 goto error;
1113
1114         BUG_ON(ret == 0);
1115
1116         ret = btrfs_previous_item(root, path, 0, BTRFS_CHUNK_ITEM_KEY);
1117         if (ret) {
1118                 *offset = 0;
1119         } else {
1120                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1121                                       path->slots[0]);
1122                 if (found_key.objectid != objectid)
1123                         *offset = 0;
1124                 else {
1125                         chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
1126                                                struct btrfs_chunk);
1127                         *offset = found_key.offset +
1128                                 btrfs_chunk_length(path->nodes[0], chunk);
1129                 }
1130         }
1131         ret = 0;
1132 error:
1133         btrfs_free_path(path);
1134         return ret;
1135 }
1136
1137 static noinline int find_next_devid(struct btrfs_root *root, u64 *objectid)
1138 {
1139         int ret;
1140         struct btrfs_key key;
1141         struct btrfs_key found_key;
1142         struct btrfs_path *path;
1143
1144         root = root->fs_info->chunk_root;
1145
1146         path = btrfs_alloc_path();
1147         if (!path)
1148                 return -ENOMEM;
1149
1150         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1151         key.type = BTRFS_DEV_ITEM_KEY;
1152         key.offset = (u64)-1;
1153
1154         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1155         if (ret < 0)
1156                 goto error;
1157
1158         BUG_ON(ret == 0);
1159
1160         ret = btrfs_previous_item(root, path, BTRFS_DEV_ITEMS_OBJECTID,
1161                                   BTRFS_DEV_ITEM_KEY);
1162         if (ret) {
1163                 *objectid = 1;
1164         } else {
1165                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1166                                       path->slots[0]);
1167                 *objectid = found_key.offset + 1;
1168         }
1169         ret = 0;
1170 error:
1171         btrfs_free_path(path);
1172         return ret;
1173 }
1174
1175 /*
1176  * the device information is stored in the chunk root
1177  * the btrfs_device struct should be fully filled in
1178  */
1179 int btrfs_add_device(struct btrfs_trans_handle *trans,
1180                      struct btrfs_root *root,
1181                      struct btrfs_device *device)
1182 {
1183         int ret;
1184         struct btrfs_path *path;
1185         struct btrfs_dev_item *dev_item;
1186         struct extent_buffer *leaf;
1187         struct btrfs_key key;
1188         unsigned long ptr;
1189
1190         root = root->fs_info->chunk_root;
1191
1192         path = btrfs_alloc_path();
1193         if (!path)
1194                 return -ENOMEM;
1195
1196         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1197         key.type = BTRFS_DEV_ITEM_KEY;
1198         key.offset = device->devid;
1199
1200         ret = btrfs_insert_empty_item(trans, root, path, &key,
1201                                       sizeof(*dev_item));
1202         if (ret)
1203                 goto out;
1204
1205         leaf = path->nodes[0];
1206         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
1207
1208         btrfs_set_device_id(leaf, dev_item, device->devid);
1209         btrfs_set_device_generation(leaf, dev_item, 0);
1210         btrfs_set_device_type(leaf, dev_item, device->type);
1211         btrfs_set_device_io_align(leaf, dev_item, device->io_align);
1212         btrfs_set_device_io_width(leaf, dev_item, device->io_width);
1213         btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
1214         btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
1215         btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
1216         btrfs_set_device_group(leaf, dev_item, 0);
1217         btrfs_set_device_seek_speed(leaf, dev_item, 0);
1218         btrfs_set_device_bandwidth(leaf, dev_item, 0);
1219         btrfs_set_device_start_offset(leaf, dev_item, 0);
1220
1221         ptr = (unsigned long)btrfs_device_uuid(dev_item);
1222         write_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
1223         ptr = (unsigned long)btrfs_device_fsid(dev_item);
1224         write_extent_buffer(leaf, root->fs_info->fsid, ptr, BTRFS_UUID_SIZE);
1225         btrfs_mark_buffer_dirty(leaf);
1226
1227         ret = 0;
1228 out:
1229         btrfs_free_path(path);
1230         return ret;
1231 }
1232
1233 static int btrfs_rm_dev_item(struct btrfs_root *root,
1234                              struct btrfs_device *device)
1235 {
1236         int ret;
1237         struct btrfs_path *path;
1238         struct btrfs_key key;
1239         struct btrfs_trans_handle *trans;
1240
1241         root = root->fs_info->chunk_root;
1242
1243         path = btrfs_alloc_path();
1244         if (!path)
1245                 return -ENOMEM;
1246
1247         trans = btrfs_start_transaction(root, 0);
1248         if (IS_ERR(trans)) {
1249                 btrfs_free_path(path);
1250                 return PTR_ERR(trans);
1251         }
1252         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1253         key.type = BTRFS_DEV_ITEM_KEY;
1254         key.offset = device->devid;
1255         lock_chunks(root);
1256
1257         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1258         if (ret < 0)
1259                 goto out;
1260
1261         if (ret > 0) {
1262                 ret = -ENOENT;
1263                 goto out;
1264         }
1265
1266         ret = btrfs_del_item(trans, root, path);
1267         if (ret)
1268                 goto out;
1269 out:
1270         btrfs_free_path(path);
1271         unlock_chunks(root);
1272         btrfs_commit_transaction(trans, root);
1273         return ret;
1274 }
1275
1276 int btrfs_rm_device(struct btrfs_root *root, char *device_path)
1277 {
1278         struct btrfs_device *device;
1279         struct btrfs_device *next_device;
1280         struct block_device *bdev;
1281         struct buffer_head *bh = NULL;
1282         struct btrfs_super_block *disk_super;
1283         struct btrfs_fs_devices *cur_devices;
1284         u64 all_avail;
1285         u64 devid;
1286         u64 num_devices;
1287         u8 *dev_uuid;
1288         int ret = 0;
1289         bool clear_super = false;
1290
1291         mutex_lock(&uuid_mutex);
1292         mutex_lock(&root->fs_info->volume_mutex);
1293
1294         all_avail = root->fs_info->avail_data_alloc_bits |
1295                 root->fs_info->avail_system_alloc_bits |
1296                 root->fs_info->avail_metadata_alloc_bits;
1297
1298         if ((all_avail & BTRFS_BLOCK_GROUP_RAID10) &&
1299             root->fs_info->fs_devices->num_devices <= 4) {
1300                 printk(KERN_ERR "btrfs: unable to go below four devices "
1301                        "on raid10\n");
1302                 ret = -EINVAL;
1303                 goto out;
1304         }
1305
1306         if ((all_avail & BTRFS_BLOCK_GROUP_RAID1) &&
1307             root->fs_info->fs_devices->num_devices <= 2) {
1308                 printk(KERN_ERR "btrfs: unable to go below two "
1309                        "devices on raid1\n");
1310                 ret = -EINVAL;
1311                 goto out;
1312         }
1313
1314         if (strcmp(device_path, "missing") == 0) {
1315                 struct list_head *devices;
1316                 struct btrfs_device *tmp;
1317
1318                 device = NULL;
1319                 devices = &root->fs_info->fs_devices->devices;
1320                 /*
1321                  * It is safe to read the devices since the volume_mutex
1322                  * is held.
1323                  */
1324                 list_for_each_entry(tmp, devices, dev_list) {
1325                         if (tmp->in_fs_metadata && !tmp->bdev) {
1326                                 device = tmp;
1327                                 break;
1328                         }
1329                 }
1330                 bdev = NULL;
1331                 bh = NULL;
1332                 disk_super = NULL;
1333                 if (!device) {
1334                         printk(KERN_ERR "btrfs: no missing devices found to "
1335                                "remove\n");
1336                         goto out;
1337                 }
1338         } else {
1339                 bdev = blkdev_get_by_path(device_path, FMODE_READ | FMODE_EXCL,
1340                                           root->fs_info->bdev_holder);
1341                 if (IS_ERR(bdev)) {
1342                         ret = PTR_ERR(bdev);
1343                         goto out;
1344                 }
1345
1346                 set_blocksize(bdev, 4096);
1347                 bh = btrfs_read_dev_super(bdev);
1348                 if (!bh) {
1349                         ret = -EINVAL;
1350                         goto error_close;
1351                 }
1352                 disk_super = (struct btrfs_super_block *)bh->b_data;
1353                 devid = btrfs_stack_device_id(&disk_super->dev_item);
1354                 dev_uuid = disk_super->dev_item.uuid;
1355                 device = btrfs_find_device(root, devid, dev_uuid,
1356                                            disk_super->fsid);
1357                 if (!device) {
1358                         ret = -ENOENT;
1359                         goto error_brelse;
1360                 }
1361         }
1362
1363         if (device->writeable && root->fs_info->fs_devices->rw_devices == 1) {
1364                 printk(KERN_ERR "btrfs: unable to remove the only writeable "
1365                        "device\n");
1366                 ret = -EINVAL;
1367                 goto error_brelse;
1368         }
1369
1370         if (device->writeable) {
1371                 lock_chunks(root);
1372                 list_del_init(&device->dev_alloc_list);
1373                 unlock_chunks(root);
1374                 root->fs_info->fs_devices->rw_devices--;
1375                 clear_super = true;
1376         }
1377
1378         ret = btrfs_shrink_device(device, 0);
1379         if (ret)
1380                 goto error_undo;
1381
1382         ret = btrfs_rm_dev_item(root->fs_info->chunk_root, device);
1383         if (ret)
1384                 goto error_undo;
1385
1386         spin_lock(&root->fs_info->free_chunk_lock);
1387         root->fs_info->free_chunk_space = device->total_bytes -
1388                 device->bytes_used;
1389         spin_unlock(&root->fs_info->free_chunk_lock);
1390
1391         device->in_fs_metadata = 0;
1392         btrfs_scrub_cancel_dev(root, device);
1393
1394         /*
1395          * the device list mutex makes sure that we don't change
1396          * the device list while someone else is writing out all
1397          * the device supers.
1398          */
1399
1400         cur_devices = device->fs_devices;
1401         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
1402         list_del_rcu(&device->dev_list);
1403
1404         device->fs_devices->num_devices--;
1405
1406         if (device->missing)
1407                 root->fs_info->fs_devices->missing_devices--;
1408
1409         next_device = list_entry(root->fs_info->fs_devices->devices.next,
1410                                  struct btrfs_device, dev_list);
1411         if (device->bdev == root->fs_info->sb->s_bdev)
1412                 root->fs_info->sb->s_bdev = next_device->bdev;
1413         if (device->bdev == root->fs_info->fs_devices->latest_bdev)
1414                 root->fs_info->fs_devices->latest_bdev = next_device->bdev;
1415
1416         if (device->bdev)
1417                 device->fs_devices->open_devices--;
1418
1419         call_rcu(&device->rcu, free_device);
1420         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
1421
1422         num_devices = btrfs_super_num_devices(root->fs_info->super_copy) - 1;
1423         btrfs_set_super_num_devices(root->fs_info->super_copy, num_devices);
1424
1425         if (cur_devices->open_devices == 0) {
1426                 struct btrfs_fs_devices *fs_devices;
1427                 fs_devices = root->fs_info->fs_devices;
1428                 while (fs_devices) {
1429                         if (fs_devices->seed == cur_devices)
1430                                 break;
1431                         fs_devices = fs_devices->seed;
1432                 }
1433                 fs_devices->seed = cur_devices->seed;
1434                 cur_devices->seed = NULL;
1435                 lock_chunks(root);
1436                 __btrfs_close_devices(cur_devices);
1437                 unlock_chunks(root);
1438                 free_fs_devices(cur_devices);
1439         }
1440
1441         /*
1442          * at this point, the device is zero sized.  We want to
1443          * remove it from the devices list and zero out the old super
1444          */
1445         if (clear_super) {
1446                 /* make sure this device isn't detected as part of
1447                  * the FS anymore
1448                  */
1449                 memset(&disk_super->magic, 0, sizeof(disk_super->magic));
1450                 set_buffer_dirty(bh);
1451                 sync_dirty_buffer(bh);
1452         }
1453
1454         ret = 0;
1455
1456 error_brelse:
1457         brelse(bh);
1458 error_close:
1459         if (bdev)
1460                 blkdev_put(bdev, FMODE_READ | FMODE_EXCL);
1461 out:
1462         mutex_unlock(&root->fs_info->volume_mutex);
1463         mutex_unlock(&uuid_mutex);
1464         return ret;
1465 error_undo:
1466         if (device->writeable) {
1467                 lock_chunks(root);
1468                 list_add(&device->dev_alloc_list,
1469                          &root->fs_info->fs_devices->alloc_list);
1470                 unlock_chunks(root);
1471                 root->fs_info->fs_devices->rw_devices++;
1472         }
1473         goto error_brelse;
1474 }
1475
1476 /*
1477  * does all the dirty work required for changing file system's UUID.
1478  */
1479 static int btrfs_prepare_sprout(struct btrfs_trans_handle *trans,
1480                                 struct btrfs_root *root)
1481 {
1482         struct btrfs_fs_devices *fs_devices = root->fs_info->fs_devices;
1483         struct btrfs_fs_devices *old_devices;
1484         struct btrfs_fs_devices *seed_devices;
1485         struct btrfs_super_block *disk_super = root->fs_info->super_copy;
1486         struct btrfs_device *device;
1487         u64 super_flags;
1488
1489         BUG_ON(!mutex_is_locked(&uuid_mutex));
1490         if (!fs_devices->seeding)
1491                 return -EINVAL;
1492
1493         seed_devices = kzalloc(sizeof(*fs_devices), GFP_NOFS);
1494         if (!seed_devices)
1495                 return -ENOMEM;
1496
1497         old_devices = clone_fs_devices(fs_devices);
1498         if (IS_ERR(old_devices)) {
1499                 kfree(seed_devices);
1500                 return PTR_ERR(old_devices);
1501         }
1502
1503         list_add(&old_devices->list, &fs_uuids);
1504
1505         memcpy(seed_devices, fs_devices, sizeof(*seed_devices));
1506         seed_devices->opened = 1;
1507         INIT_LIST_HEAD(&seed_devices->devices);
1508         INIT_LIST_HEAD(&seed_devices->alloc_list);
1509         mutex_init(&seed_devices->device_list_mutex);
1510
1511         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
1512         list_splice_init_rcu(&fs_devices->devices, &seed_devices->devices,
1513                               synchronize_rcu);
1514         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
1515
1516         list_splice_init(&fs_devices->alloc_list, &seed_devices->alloc_list);
1517         list_for_each_entry(device, &seed_devices->devices, dev_list) {
1518                 device->fs_devices = seed_devices;
1519         }
1520
1521         fs_devices->seeding = 0;
1522         fs_devices->num_devices = 0;
1523         fs_devices->open_devices = 0;
1524         fs_devices->seed = seed_devices;
1525
1526         generate_random_uuid(fs_devices->fsid);
1527         memcpy(root->fs_info->fsid, fs_devices->fsid, BTRFS_FSID_SIZE);
1528         memcpy(disk_super->fsid, fs_devices->fsid, BTRFS_FSID_SIZE);
1529         super_flags = btrfs_super_flags(disk_super) &
1530                       ~BTRFS_SUPER_FLAG_SEEDING;
1531         btrfs_set_super_flags(disk_super, super_flags);
1532
1533         return 0;
1534 }
1535
1536 /*
1537  * strore the expected generation for seed devices in device items.
1538  */
1539 static int btrfs_finish_sprout(struct btrfs_trans_handle *trans,
1540                                struct btrfs_root *root)
1541 {
1542         struct btrfs_path *path;
1543         struct extent_buffer *leaf;
1544         struct btrfs_dev_item *dev_item;
1545         struct btrfs_device *device;
1546         struct btrfs_key key;
1547         u8 fs_uuid[BTRFS_UUID_SIZE];
1548         u8 dev_uuid[BTRFS_UUID_SIZE];
1549         u64 devid;
1550         int ret;
1551
1552         path = btrfs_alloc_path();
1553         if (!path)
1554                 return -ENOMEM;
1555
1556         root = root->fs_info->chunk_root;
1557         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1558         key.offset = 0;
1559         key.type = BTRFS_DEV_ITEM_KEY;
1560
1561         while (1) {
1562                 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1563                 if (ret < 0)
1564                         goto error;
1565
1566                 leaf = path->nodes[0];
1567 next_slot:
1568                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
1569                         ret = btrfs_next_leaf(root, path);
1570                         if (ret > 0)
1571                                 break;
1572                         if (ret < 0)
1573                                 goto error;
1574                         leaf = path->nodes[0];
1575                         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1576                         btrfs_release_path(path);
1577                         continue;
1578                 }
1579
1580                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1581                 if (key.objectid != BTRFS_DEV_ITEMS_OBJECTID ||
1582                     key.type != BTRFS_DEV_ITEM_KEY)
1583                         break;
1584
1585                 dev_item = btrfs_item_ptr(leaf, path->slots[0],
1586                                           struct btrfs_dev_item);
1587                 devid = btrfs_device_id(leaf, dev_item);
1588                 read_extent_buffer(leaf, dev_uuid,
1589                                    (unsigned long)btrfs_device_uuid(dev_item),
1590                                    BTRFS_UUID_SIZE);
1591                 read_extent_buffer(leaf, fs_uuid,
1592                                    (unsigned long)btrfs_device_fsid(dev_item),
1593                                    BTRFS_UUID_SIZE);
1594                 device = btrfs_find_device(root, devid, dev_uuid, fs_uuid);
1595                 BUG_ON(!device);
1596
1597                 if (device->fs_devices->seeding) {
1598                         btrfs_set_device_generation(leaf, dev_item,
1599                                                     device->generation);
1600                         btrfs_mark_buffer_dirty(leaf);
1601                 }
1602
1603                 path->slots[0]++;
1604                 goto next_slot;
1605         }
1606         ret = 0;
1607 error:
1608         btrfs_free_path(path);
1609         return ret;
1610 }
1611
1612 int btrfs_init_new_device(struct btrfs_root *root, char *device_path)
1613 {
1614         struct request_queue *q;
1615         struct btrfs_trans_handle *trans;
1616         struct btrfs_device *device;
1617         struct block_device *bdev;
1618         struct list_head *devices;
1619         struct super_block *sb = root->fs_info->sb;
1620         u64 total_bytes;
1621         int seeding_dev = 0;
1622         int ret = 0;
1623
1624         if ((sb->s_flags & MS_RDONLY) && !root->fs_info->fs_devices->seeding)
1625                 return -EINVAL;
1626
1627         bdev = blkdev_get_by_path(device_path, FMODE_WRITE | FMODE_EXCL,
1628                                   root->fs_info->bdev_holder);
1629         if (IS_ERR(bdev))
1630                 return PTR_ERR(bdev);
1631
1632         if (root->fs_info->fs_devices->seeding) {
1633                 seeding_dev = 1;
1634                 down_write(&sb->s_umount);
1635                 mutex_lock(&uuid_mutex);
1636         }
1637
1638         filemap_write_and_wait(bdev->bd_inode->i_mapping);
1639         mutex_lock(&root->fs_info->volume_mutex);
1640
1641         devices = &root->fs_info->fs_devices->devices;
1642         /*
1643          * we have the volume lock, so we don't need the extra
1644          * device list mutex while reading the list here.
1645          */
1646         list_for_each_entry(device, devices, dev_list) {
1647                 if (device->bdev == bdev) {
1648                         ret = -EEXIST;
1649                         goto error;
1650                 }
1651         }
1652
1653         device = kzalloc(sizeof(*device), GFP_NOFS);
1654         if (!device) {
1655                 /* we can safely leave the fs_devices entry around */
1656                 ret = -ENOMEM;
1657                 goto error;
1658         }
1659
1660         device->name = kstrdup(device_path, GFP_NOFS);
1661         if (!device->name) {
1662                 kfree(device);
1663                 ret = -ENOMEM;
1664                 goto error;
1665         }
1666
1667         ret = find_next_devid(root, &device->devid);
1668         if (ret) {
1669                 kfree(device->name);
1670                 kfree(device);
1671                 goto error;
1672         }
1673
1674         trans = btrfs_start_transaction(root, 0);
1675         if (IS_ERR(trans)) {
1676                 kfree(device->name);
1677                 kfree(device);
1678                 ret = PTR_ERR(trans);
1679                 goto error;
1680         }
1681
1682         lock_chunks(root);
1683
1684         q = bdev_get_queue(bdev);
1685         if (blk_queue_discard(q))
1686                 device->can_discard = 1;
1687         device->writeable = 1;
1688         device->work.func = pending_bios_fn;
1689         generate_random_uuid(device->uuid);
1690         spin_lock_init(&device->io_lock);
1691         device->generation = trans->transid;
1692         device->io_width = root->sectorsize;
1693         device->io_align = root->sectorsize;
1694         device->sector_size = root->sectorsize;
1695         device->total_bytes = i_size_read(bdev->bd_inode);
1696         device->disk_total_bytes = device->total_bytes;
1697         device->dev_root = root->fs_info->dev_root;
1698         device->bdev = bdev;
1699         device->in_fs_metadata = 1;
1700         device->mode = FMODE_EXCL;
1701         set_blocksize(device->bdev, 4096);
1702
1703         if (seeding_dev) {
1704                 sb->s_flags &= ~MS_RDONLY;
1705                 ret = btrfs_prepare_sprout(trans, root);
1706                 BUG_ON(ret);
1707         }
1708
1709         device->fs_devices = root->fs_info->fs_devices;
1710
1711         /*
1712          * we don't want write_supers to jump in here with our device
1713          * half setup
1714          */
1715         mutex_lock(&root->fs_info->fs_devices->device_list_mutex);
1716         list_add_rcu(&device->dev_list, &root->fs_info->fs_devices->devices);
1717         list_add(&device->dev_alloc_list,
1718                  &root->fs_info->fs_devices->alloc_list);
1719         root->fs_info->fs_devices->num_devices++;
1720         root->fs_info->fs_devices->open_devices++;
1721         root->fs_info->fs_devices->rw_devices++;
1722         if (device->can_discard)
1723                 root->fs_info->fs_devices->num_can_discard++;
1724         root->fs_info->fs_devices->total_rw_bytes += device->total_bytes;
1725
1726         spin_lock(&root->fs_info->free_chunk_lock);
1727         root->fs_info->free_chunk_space += device->total_bytes;
1728         spin_unlock(&root->fs_info->free_chunk_lock);
1729
1730         if (!blk_queue_nonrot(bdev_get_queue(bdev)))
1731                 root->fs_info->fs_devices->rotating = 1;
1732
1733         total_bytes = btrfs_super_total_bytes(root->fs_info->super_copy);
1734         btrfs_set_super_total_bytes(root->fs_info->super_copy,
1735                                     total_bytes + device->total_bytes);
1736
1737         total_bytes = btrfs_super_num_devices(root->fs_info->super_copy);
1738         btrfs_set_super_num_devices(root->fs_info->super_copy,
1739                                     total_bytes + 1);
1740         mutex_unlock(&root->fs_info->fs_devices->device_list_mutex);
1741
1742         if (seeding_dev) {
1743                 ret = init_first_rw_device(trans, root, device);
1744                 BUG_ON(ret);
1745                 ret = btrfs_finish_sprout(trans, root);
1746                 BUG_ON(ret);
1747         } else {
1748                 ret = btrfs_add_device(trans, root, device);
1749         }
1750
1751         /*
1752          * we've got more storage, clear any full flags on the space
1753          * infos
1754          */
1755         btrfs_clear_space_info_full(root->fs_info);
1756
1757         unlock_chunks(root);
1758         btrfs_commit_transaction(trans, root);
1759
1760         if (seeding_dev) {
1761                 mutex_unlock(&uuid_mutex);
1762                 up_write(&sb->s_umount);
1763
1764                 ret = btrfs_relocate_sys_chunks(root);
1765                 BUG_ON(ret);
1766         }
1767 out:
1768         mutex_unlock(&root->fs_info->volume_mutex);
1769         return ret;
1770 error:
1771         blkdev_put(bdev, FMODE_EXCL);
1772         if (seeding_dev) {
1773                 mutex_unlock(&uuid_mutex);
1774                 up_write(&sb->s_umount);
1775         }
1776         goto out;
1777 }
1778
1779 static noinline int btrfs_update_device(struct btrfs_trans_handle *trans,
1780                                         struct btrfs_device *device)
1781 {
1782         int ret;
1783         struct btrfs_path *path;
1784         struct btrfs_root *root;
1785         struct btrfs_dev_item *dev_item;
1786         struct extent_buffer *leaf;
1787         struct btrfs_key key;
1788
1789         root = device->dev_root->fs_info->chunk_root;
1790
1791         path = btrfs_alloc_path();
1792         if (!path)
1793                 return -ENOMEM;
1794
1795         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1796         key.type = BTRFS_DEV_ITEM_KEY;
1797         key.offset = device->devid;
1798
1799         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1800         if (ret < 0)
1801                 goto out;
1802
1803         if (ret > 0) {
1804                 ret = -ENOENT;
1805                 goto out;
1806         }
1807
1808         leaf = path->nodes[0];
1809         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
1810
1811         btrfs_set_device_id(leaf, dev_item, device->devid);
1812         btrfs_set_device_type(leaf, dev_item, device->type);
1813         btrfs_set_device_io_align(leaf, dev_item, device->io_align);
1814         btrfs_set_device_io_width(leaf, dev_item, device->io_width);
1815         btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
1816         btrfs_set_device_total_bytes(leaf, dev_item, device->disk_total_bytes);
1817         btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
1818         btrfs_mark_buffer_dirty(leaf);
1819
1820 out:
1821         btrfs_free_path(path);
1822         return ret;
1823 }
1824
1825 static int __btrfs_grow_device(struct btrfs_trans_handle *trans,
1826                       struct btrfs_device *device, u64 new_size)
1827 {
1828         struct btrfs_super_block *super_copy =
1829                 device->dev_root->fs_info->super_copy;
1830         u64 old_total = btrfs_super_total_bytes(super_copy);
1831         u64 diff = new_size - device->total_bytes;
1832
1833         if (!device->writeable)
1834                 return -EACCES;
1835         if (new_size <= device->total_bytes)
1836                 return -EINVAL;
1837
1838         btrfs_set_super_total_bytes(super_copy, old_total + diff);
1839         device->fs_devices->total_rw_bytes += diff;
1840
1841         device->total_bytes = new_size;
1842         device->disk_total_bytes = new_size;
1843         btrfs_clear_space_info_full(device->dev_root->fs_info);
1844
1845         return btrfs_update_device(trans, device);
1846 }
1847
1848 int btrfs_grow_device(struct btrfs_trans_handle *trans,
1849                       struct btrfs_device *device, u64 new_size)
1850 {
1851         int ret;
1852         lock_chunks(device->dev_root);
1853         ret = __btrfs_grow_device(trans, device, new_size);
1854         unlock_chunks(device->dev_root);
1855         return ret;
1856 }
1857
1858 static int btrfs_free_chunk(struct btrfs_trans_handle *trans,
1859                             struct btrfs_root *root,
1860                             u64 chunk_tree, u64 chunk_objectid,
1861                             u64 chunk_offset)
1862 {
1863         int ret;
1864         struct btrfs_path *path;
1865         struct btrfs_key key;
1866
1867         root = root->fs_info->chunk_root;
1868         path = btrfs_alloc_path();
1869         if (!path)
1870                 return -ENOMEM;
1871
1872         key.objectid = chunk_objectid;
1873         key.offset = chunk_offset;
1874         key.type = BTRFS_CHUNK_ITEM_KEY;
1875
1876         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1877         BUG_ON(ret);
1878
1879         ret = btrfs_del_item(trans, root, path);
1880
1881         btrfs_free_path(path);
1882         return ret;
1883 }
1884
1885 static int btrfs_del_sys_chunk(struct btrfs_root *root, u64 chunk_objectid, u64
1886                         chunk_offset)
1887 {
1888         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
1889         struct btrfs_disk_key *disk_key;
1890         struct btrfs_chunk *chunk;
1891         u8 *ptr;
1892         int ret = 0;
1893         u32 num_stripes;
1894         u32 array_size;
1895         u32 len = 0;
1896         u32 cur;
1897         struct btrfs_key key;
1898
1899         array_size = btrfs_super_sys_array_size(super_copy);
1900
1901         ptr = super_copy->sys_chunk_array;
1902         cur = 0;
1903
1904         while (cur < array_size) {
1905                 disk_key = (struct btrfs_disk_key *)ptr;
1906                 btrfs_disk_key_to_cpu(&key, disk_key);
1907
1908                 len = sizeof(*disk_key);
1909
1910                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
1911                         chunk = (struct btrfs_chunk *)(ptr + len);
1912                         num_stripes = btrfs_stack_chunk_num_stripes(chunk);
1913                         len += btrfs_chunk_item_size(num_stripes);
1914                 } else {
1915                         ret = -EIO;
1916                         break;
1917                 }
1918                 if (key.objectid == chunk_objectid &&
1919                     key.offset == chunk_offset) {
1920                         memmove(ptr, ptr + len, array_size - (cur + len));
1921                         array_size -= len;
1922                         btrfs_set_super_sys_array_size(super_copy, array_size);
1923                 } else {
1924                         ptr += len;
1925                         cur += len;
1926                 }
1927         }
1928         return ret;
1929 }
1930
1931 static int btrfs_relocate_chunk(struct btrfs_root *root,
1932                          u64 chunk_tree, u64 chunk_objectid,
1933                          u64 chunk_offset)
1934 {
1935         struct extent_map_tree *em_tree;
1936         struct btrfs_root *extent_root;
1937         struct btrfs_trans_handle *trans;
1938         struct extent_map *em;
1939         struct map_lookup *map;
1940         int ret;
1941         int i;
1942
1943         root = root->fs_info->chunk_root;
1944         extent_root = root->fs_info->extent_root;
1945         em_tree = &root->fs_info->mapping_tree.map_tree;
1946
1947         ret = btrfs_can_relocate(extent_root, chunk_offset);
1948         if (ret)
1949                 return -ENOSPC;
1950
1951         /* step one, relocate all the extents inside this chunk */
1952         ret = btrfs_relocate_block_group(extent_root, chunk_offset);
1953         if (ret)
1954                 return ret;
1955
1956         trans = btrfs_start_transaction(root, 0);
1957         BUG_ON(IS_ERR(trans));
1958
1959         lock_chunks(root);
1960
1961         /*
1962          * step two, delete the device extents and the
1963          * chunk tree entries
1964          */
1965         read_lock(&em_tree->lock);
1966         em = lookup_extent_mapping(em_tree, chunk_offset, 1);
1967         read_unlock(&em_tree->lock);
1968
1969         BUG_ON(em->start > chunk_offset ||
1970                em->start + em->len < chunk_offset);
1971         map = (struct map_lookup *)em->bdev;
1972
1973         for (i = 0; i < map->num_stripes; i++) {
1974                 ret = btrfs_free_dev_extent(trans, map->stripes[i].dev,
1975                                             map->stripes[i].physical);
1976                 BUG_ON(ret);
1977
1978                 if (map->stripes[i].dev) {
1979                         ret = btrfs_update_device(trans, map->stripes[i].dev);
1980                         BUG_ON(ret);
1981                 }
1982         }
1983         ret = btrfs_free_chunk(trans, root, chunk_tree, chunk_objectid,
1984                                chunk_offset);
1985
1986         BUG_ON(ret);
1987
1988         trace_btrfs_chunk_free(root, map, chunk_offset, em->len);
1989
1990         if (map->type & BTRFS_BLOCK_GROUP_SYSTEM) {
1991                 ret = btrfs_del_sys_chunk(root, chunk_objectid, chunk_offset);
1992                 BUG_ON(ret);
1993         }
1994
1995         ret = btrfs_remove_block_group(trans, extent_root, chunk_offset);
1996         BUG_ON(ret);
1997
1998         write_lock(&em_tree->lock);
1999         remove_extent_mapping(em_tree, em);
2000         write_unlock(&em_tree->lock);
2001
2002         kfree(map);
2003         em->bdev = NULL;
2004
2005         /* once for the tree */
2006         free_extent_map(em);
2007         /* once for us */
2008         free_extent_map(em);
2009
2010         unlock_chunks(root);
2011         btrfs_end_transaction(trans, root);
2012         return 0;
2013 }
2014
2015 static int btrfs_relocate_sys_chunks(struct btrfs_root *root)
2016 {
2017         struct btrfs_root *chunk_root = root->fs_info->chunk_root;
2018         struct btrfs_path *path;
2019         struct extent_buffer *leaf;
2020         struct btrfs_chunk *chunk;
2021         struct btrfs_key key;
2022         struct btrfs_key found_key;
2023         u64 chunk_tree = chunk_root->root_key.objectid;
2024         u64 chunk_type;
2025         bool retried = false;
2026         int failed = 0;
2027         int ret;
2028
2029         path = btrfs_alloc_path();
2030         if (!path)
2031                 return -ENOMEM;
2032
2033 again:
2034         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2035         key.offset = (u64)-1;
2036         key.type = BTRFS_CHUNK_ITEM_KEY;
2037
2038         while (1) {
2039                 ret = btrfs_search_slot(NULL, chunk_root, &key, path, 0, 0);
2040                 if (ret < 0)
2041                         goto error;
2042                 BUG_ON(ret == 0);
2043
2044                 ret = btrfs_previous_item(chunk_root, path, key.objectid,
2045                                           key.type);
2046                 if (ret < 0)
2047                         goto error;
2048                 if (ret > 0)
2049                         break;
2050
2051                 leaf = path->nodes[0];
2052                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
2053
2054                 chunk = btrfs_item_ptr(leaf, path->slots[0],
2055                                        struct btrfs_chunk);
2056                 chunk_type = btrfs_chunk_type(leaf, chunk);
2057                 btrfs_release_path(path);
2058
2059                 if (chunk_type & BTRFS_BLOCK_GROUP_SYSTEM) {
2060                         ret = btrfs_relocate_chunk(chunk_root, chunk_tree,
2061                                                    found_key.objectid,
2062                                                    found_key.offset);
2063                         if (ret == -ENOSPC)
2064                                 failed++;
2065                         else if (ret)
2066                                 BUG();
2067                 }
2068
2069                 if (found_key.offset == 0)
2070                         break;
2071                 key.offset = found_key.offset - 1;
2072         }
2073         ret = 0;
2074         if (failed && !retried) {
2075                 failed = 0;
2076                 retried = true;
2077                 goto again;
2078         } else if (failed && retried) {
2079                 WARN_ON(1);
2080                 ret = -ENOSPC;
2081         }
2082 error:
2083         btrfs_free_path(path);
2084         return ret;
2085 }
2086
2087 static u64 div_factor(u64 num, int factor)
2088 {
2089         if (factor == 10)
2090                 return num;
2091         num *= factor;
2092         do_div(num, 10);
2093         return num;
2094 }
2095
2096 int btrfs_balance(struct btrfs_root *dev_root)
2097 {
2098         int ret;
2099         struct list_head *devices = &dev_root->fs_info->fs_devices->devices;
2100         struct btrfs_device *device;
2101         u64 old_size;
2102         u64 size_to_free;
2103         struct btrfs_path *path;
2104         struct btrfs_key key;
2105         struct btrfs_root *chunk_root = dev_root->fs_info->chunk_root;
2106         struct btrfs_trans_handle *trans;
2107         struct btrfs_key found_key;
2108
2109         if (dev_root->fs_info->sb->s_flags & MS_RDONLY)
2110                 return -EROFS;
2111
2112         if (!capable(CAP_SYS_ADMIN))
2113                 return -EPERM;
2114
2115         mutex_lock(&dev_root->fs_info->volume_mutex);
2116         dev_root = dev_root->fs_info->dev_root;
2117
2118         /* step one make some room on all the devices */
2119         list_for_each_entry(device, devices, dev_list) {
2120                 old_size = device->total_bytes;
2121                 size_to_free = div_factor(old_size, 1);
2122                 size_to_free = min(size_to_free, (u64)1 * 1024 * 1024);
2123                 if (!device->writeable ||
2124                     device->total_bytes - device->bytes_used > size_to_free)
2125                         continue;
2126
2127                 ret = btrfs_shrink_device(device, old_size - size_to_free);
2128                 if (ret == -ENOSPC)
2129                         break;
2130                 BUG_ON(ret);
2131
2132                 trans = btrfs_start_transaction(dev_root, 0);
2133                 BUG_ON(IS_ERR(trans));
2134
2135                 ret = btrfs_grow_device(trans, device, old_size);
2136                 BUG_ON(ret);
2137
2138                 btrfs_end_transaction(trans, dev_root);
2139         }
2140
2141         /* step two, relocate all the chunks */
2142         path = btrfs_alloc_path();
2143         if (!path) {
2144                 ret = -ENOMEM;
2145                 goto error;
2146         }
2147         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2148         key.offset = (u64)-1;
2149         key.type = BTRFS_CHUNK_ITEM_KEY;
2150
2151         while (1) {
2152                 ret = btrfs_search_slot(NULL, chunk_root, &key, path, 0, 0);
2153                 if (ret < 0)
2154                         goto error;
2155
2156                 /*
2157                  * this shouldn't happen, it means the last relocate
2158                  * failed
2159                  */
2160                 if (ret == 0)
2161                         break;
2162
2163                 ret = btrfs_previous_item(chunk_root, path, 0,
2164                                           BTRFS_CHUNK_ITEM_KEY);
2165                 if (ret)
2166                         break;
2167
2168                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2169                                       path->slots[0]);
2170                 if (found_key.objectid != key.objectid)
2171                         break;
2172
2173                 /* chunk zero is special */
2174                 if (found_key.offset == 0)
2175                         break;
2176
2177                 btrfs_release_path(path);
2178                 ret = btrfs_relocate_chunk(chunk_root,
2179                                            chunk_root->root_key.objectid,
2180                                            found_key.objectid,
2181                                            found_key.offset);
2182                 if (ret && ret != -ENOSPC)
2183                         goto error;
2184                 key.offset = found_key.offset - 1;
2185         }
2186         ret = 0;
2187 error:
2188         btrfs_free_path(path);
2189         mutex_unlock(&dev_root->fs_info->volume_mutex);
2190         return ret;
2191 }
2192
2193 /*
2194  * shrinking a device means finding all of the device extents past
2195  * the new size, and then following the back refs to the chunks.
2196  * The chunk relocation code actually frees the device extent
2197  */
2198 int btrfs_shrink_device(struct btrfs_device *device, u64 new_size)
2199 {
2200         struct btrfs_trans_handle *trans;
2201         struct btrfs_root *root = device->dev_root;
2202         struct btrfs_dev_extent *dev_extent = NULL;
2203         struct btrfs_path *path;
2204         u64 length;
2205         u64 chunk_tree;
2206         u64 chunk_objectid;
2207         u64 chunk_offset;
2208         int ret;
2209         int slot;
2210         int failed = 0;
2211         bool retried = false;
2212         struct extent_buffer *l;
2213         struct btrfs_key key;
2214         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
2215         u64 old_total = btrfs_super_total_bytes(super_copy);
2216         u64 old_size = device->total_bytes;
2217         u64 diff = device->total_bytes - new_size;
2218
2219         if (new_size >= device->total_bytes)
2220                 return -EINVAL;
2221
2222         path = btrfs_alloc_path();
2223         if (!path)
2224                 return -ENOMEM;
2225
2226         path->reada = 2;
2227
2228         lock_chunks(root);
2229
2230         device->total_bytes = new_size;
2231         if (device->writeable) {
2232                 device->fs_devices->total_rw_bytes -= diff;
2233                 spin_lock(&root->fs_info->free_chunk_lock);
2234                 root->fs_info->free_chunk_space -= diff;
2235                 spin_unlock(&root->fs_info->free_chunk_lock);
2236         }
2237         unlock_chunks(root);
2238
2239 again:
2240         key.objectid = device->devid;
2241         key.offset = (u64)-1;
2242         key.type = BTRFS_DEV_EXTENT_KEY;
2243
2244         while (1) {
2245                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2246                 if (ret < 0)
2247                         goto done;
2248
2249                 ret = btrfs_previous_item(root, path, 0, key.type);
2250                 if (ret < 0)
2251                         goto done;
2252                 if (ret) {
2253                         ret = 0;
2254                         btrfs_release_path(path);
2255                         break;
2256                 }
2257
2258                 l = path->nodes[0];
2259                 slot = path->slots[0];
2260                 btrfs_item_key_to_cpu(l, &key, path->slots[0]);
2261
2262                 if (key.objectid != device->devid) {
2263                         btrfs_release_path(path);
2264                         break;
2265                 }
2266
2267                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
2268                 length = btrfs_dev_extent_length(l, dev_extent);
2269
2270                 if (key.offset + length <= new_size) {
2271                         btrfs_release_path(path);
2272                         break;
2273                 }
2274
2275                 chunk_tree = btrfs_dev_extent_chunk_tree(l, dev_extent);
2276                 chunk_objectid = btrfs_dev_extent_chunk_objectid(l, dev_extent);
2277                 chunk_offset = btrfs_dev_extent_chunk_offset(l, dev_extent);
2278                 btrfs_release_path(path);
2279
2280                 ret = btrfs_relocate_chunk(root, chunk_tree, chunk_objectid,
2281                                            chunk_offset);
2282                 if (ret && ret != -ENOSPC)
2283                         goto done;
2284                 if (ret == -ENOSPC)
2285                         failed++;
2286                 key.offset -= 1;
2287         }
2288
2289         if (failed && !retried) {
2290                 failed = 0;
2291                 retried = true;
2292                 goto again;
2293         } else if (failed && retried) {
2294                 ret = -ENOSPC;
2295                 lock_chunks(root);
2296
2297                 device->total_bytes = old_size;
2298                 if (device->writeable)
2299                         device->fs_devices->total_rw_bytes += diff;
2300                 spin_lock(&root->fs_info->free_chunk_lock);
2301                 root->fs_info->free_chunk_space += diff;
2302                 spin_unlock(&root->fs_info->free_chunk_lock);
2303                 unlock_chunks(root);
2304                 goto done;
2305         }
2306
2307         /* Shrinking succeeded, else we would be at "done". */
2308         trans = btrfs_start_transaction(root, 0);
2309         if (IS_ERR(trans)) {
2310                 ret = PTR_ERR(trans);
2311                 goto done;
2312         }
2313
2314         lock_chunks(root);
2315
2316         device->disk_total_bytes = new_size;
2317         /* Now btrfs_update_device() will change the on-disk size. */
2318         ret = btrfs_update_device(trans, device);
2319         if (ret) {
2320                 unlock_chunks(root);
2321                 btrfs_end_transaction(trans, root);
2322                 goto done;
2323         }
2324         WARN_ON(diff > old_total);
2325         btrfs_set_super_total_bytes(super_copy, old_total - diff);
2326         unlock_chunks(root);
2327         btrfs_end_transaction(trans, root);
2328 done:
2329         btrfs_free_path(path);
2330         return ret;
2331 }
2332
2333 static int btrfs_add_system_chunk(struct btrfs_trans_handle *trans,
2334                            struct btrfs_root *root,
2335                            struct btrfs_key *key,
2336                            struct btrfs_chunk *chunk, int item_size)
2337 {
2338         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
2339         struct btrfs_disk_key disk_key;
2340         u32 array_size;
2341         u8 *ptr;
2342
2343         array_size = btrfs_super_sys_array_size(super_copy);
2344         if (array_size + item_size > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE)
2345                 return -EFBIG;
2346
2347         ptr = super_copy->sys_chunk_array + array_size;
2348         btrfs_cpu_key_to_disk(&disk_key, key);
2349         memcpy(ptr, &disk_key, sizeof(disk_key));
2350         ptr += sizeof(disk_key);
2351         memcpy(ptr, chunk, item_size);
2352         item_size += sizeof(disk_key);
2353         btrfs_set_super_sys_array_size(super_copy, array_size + item_size);
2354         return 0;
2355 }
2356
2357 /*
2358  * sort the devices in descending order by max_avail, total_avail
2359  */
2360 static int btrfs_cmp_device_info(const void *a, const void *b)
2361 {
2362         const struct btrfs_device_info *di_a = a;
2363         const struct btrfs_device_info *di_b = b;
2364
2365         if (di_a->max_avail > di_b->max_avail)
2366                 return -1;
2367         if (di_a->max_avail < di_b->max_avail)
2368                 return 1;
2369         if (di_a->total_avail > di_b->total_avail)
2370                 return -1;
2371         if (di_a->total_avail < di_b->total_avail)
2372                 return 1;
2373         return 0;
2374 }
2375
2376 static int __btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
2377                                struct btrfs_root *extent_root,
2378                                struct map_lookup **map_ret,
2379                                u64 *num_bytes_out, u64 *stripe_size_out,
2380                                u64 start, u64 type)
2381 {
2382         struct btrfs_fs_info *info = extent_root->fs_info;
2383         struct btrfs_fs_devices *fs_devices = info->fs_devices;
2384         struct list_head *cur;
2385         struct map_lookup *map = NULL;
2386         struct extent_map_tree *em_tree;
2387         struct extent_map *em;
2388         struct btrfs_device_info *devices_info = NULL;
2389         u64 total_avail;
2390         int num_stripes;        /* total number of stripes to allocate */
2391         int sub_stripes;        /* sub_stripes info for map */
2392         int dev_stripes;        /* stripes per dev */
2393         int devs_max;           /* max devs to use */
2394         int devs_min;           /* min devs needed */
2395         int devs_increment;     /* ndevs has to be a multiple of this */
2396         int ncopies;            /* how many copies to data has */
2397         int ret;
2398         u64 max_stripe_size;
2399         u64 max_chunk_size;
2400         u64 stripe_size;
2401         u64 num_bytes;
2402         int ndevs;
2403         int i;
2404         int j;
2405
2406         if ((type & BTRFS_BLOCK_GROUP_RAID1) &&
2407             (type & BTRFS_BLOCK_GROUP_DUP)) {
2408                 WARN_ON(1);
2409                 type &= ~BTRFS_BLOCK_GROUP_DUP;
2410         }
2411
2412         if (list_empty(&fs_devices->alloc_list))
2413                 return -ENOSPC;
2414
2415         sub_stripes = 1;
2416         dev_stripes = 1;
2417         devs_increment = 1;
2418         ncopies = 1;
2419         devs_max = 0;   /* 0 == as many as possible */
2420         devs_min = 1;
2421
2422         /*
2423          * define the properties of each RAID type.
2424          * FIXME: move this to a global table and use it in all RAID
2425          * calculation code
2426          */
2427         if (type & (BTRFS_BLOCK_GROUP_DUP)) {
2428                 dev_stripes = 2;
2429                 ncopies = 2;
2430                 devs_max = 1;
2431         } else if (type & (BTRFS_BLOCK_GROUP_RAID0)) {
2432                 devs_min = 2;
2433         } else if (type & (BTRFS_BLOCK_GROUP_RAID1)) {
2434                 devs_increment = 2;
2435                 ncopies = 2;
2436                 devs_max = 2;
2437                 devs_min = 2;
2438         } else if (type & (BTRFS_BLOCK_GROUP_RAID10)) {
2439                 sub_stripes = 2;
2440                 devs_increment = 2;
2441                 ncopies = 2;
2442                 devs_min = 4;
2443         } else {
2444                 devs_max = 1;
2445         }
2446
2447         if (type & BTRFS_BLOCK_GROUP_DATA) {
2448                 max_stripe_size = 1024 * 1024 * 1024;
2449                 max_chunk_size = 10 * max_stripe_size;
2450         } else if (type & BTRFS_BLOCK_GROUP_METADATA) {
2451                 max_stripe_size = 256 * 1024 * 1024;
2452                 max_chunk_size = max_stripe_size;
2453         } else if (type & BTRFS_BLOCK_GROUP_SYSTEM) {
2454                 max_stripe_size = 8 * 1024 * 1024;
2455                 max_chunk_size = 2 * max_stripe_size;
2456         } else {
2457                 printk(KERN_ERR "btrfs: invalid chunk type 0x%llx requested\n",
2458                        type);
2459                 BUG_ON(1);
2460         }
2461
2462         /* we don't want a chunk larger than 10% of writeable space */
2463         max_chunk_size = min(div_factor(fs_devices->total_rw_bytes, 1),
2464                              max_chunk_size);
2465
2466         devices_info = kzalloc(sizeof(*devices_info) * fs_devices->rw_devices,
2467                                GFP_NOFS);
2468         if (!devices_info)
2469                 return -ENOMEM;
2470
2471         cur = fs_devices->alloc_list.next;
2472
2473         /*
2474          * in the first pass through the devices list, we gather information
2475          * about the available holes on each device.
2476          */
2477         ndevs = 0;
2478         while (cur != &fs_devices->alloc_list) {
2479                 struct btrfs_device *device;
2480                 u64 max_avail;
2481                 u64 dev_offset;
2482
2483                 device = list_entry(cur, struct btrfs_device, dev_alloc_list);
2484
2485                 cur = cur->next;
2486
2487                 if (!device->writeable) {
2488                         printk(KERN_ERR
2489                                "btrfs: read-only device in alloc_list\n");
2490                         WARN_ON(1);
2491                         continue;
2492                 }
2493
2494                 if (!device->in_fs_metadata)
2495                         continue;
2496
2497                 if (device->total_bytes > device->bytes_used)
2498                         total_avail = device->total_bytes - device->bytes_used;
2499                 else
2500                         total_avail = 0;
2501
2502                 /* If there is no space on this device, skip it. */
2503                 if (total_avail == 0)
2504                         continue;
2505
2506                 ret = find_free_dev_extent(trans, device,
2507                                            max_stripe_size * dev_stripes,
2508                                            &dev_offset, &max_avail);
2509                 if (ret && ret != -ENOSPC)
2510                         goto error;
2511
2512                 if (ret == 0)
2513                         max_avail = max_stripe_size * dev_stripes;
2514
2515                 if (max_avail < BTRFS_STRIPE_LEN * dev_stripes)
2516                         continue;
2517
2518                 devices_info[ndevs].dev_offset = dev_offset;
2519                 devices_info[ndevs].max_avail = max_avail;
2520                 devices_info[ndevs].total_avail = total_avail;
2521                 devices_info[ndevs].dev = device;
2522                 ++ndevs;
2523         }
2524
2525         /*
2526          * now sort the devices by hole size / available space
2527          */
2528         sort(devices_info, ndevs, sizeof(struct btrfs_device_info),
2529              btrfs_cmp_device_info, NULL);
2530
2531         /* round down to number of usable stripes */
2532         ndevs -= ndevs % devs_increment;
2533
2534         if (ndevs < devs_increment * sub_stripes || ndevs < devs_min) {
2535                 ret = -ENOSPC;
2536                 goto error;
2537         }
2538
2539         if (devs_max && ndevs > devs_max)
2540                 ndevs = devs_max;
2541         /*
2542          * the primary goal is to maximize the number of stripes, so use as many
2543          * devices as possible, even if the stripes are not maximum sized.
2544          */
2545         stripe_size = devices_info[ndevs-1].max_avail;
2546         num_stripes = ndevs * dev_stripes;
2547
2548         if (stripe_size * num_stripes > max_chunk_size * ncopies) {
2549                 stripe_size = max_chunk_size * ncopies;
2550                 do_div(stripe_size, num_stripes);
2551         }
2552
2553         do_div(stripe_size, dev_stripes);
2554         do_div(stripe_size, BTRFS_STRIPE_LEN);
2555         stripe_size *= BTRFS_STRIPE_LEN;
2556
2557         map = kmalloc(map_lookup_size(num_stripes), GFP_NOFS);
2558         if (!map) {
2559                 ret = -ENOMEM;
2560                 goto error;
2561         }
2562         map->num_stripes = num_stripes;
2563
2564         for (i = 0; i < ndevs; ++i) {
2565                 for (j = 0; j < dev_stripes; ++j) {
2566                         int s = i * dev_stripes + j;
2567                         map->stripes[s].dev = devices_info[i].dev;
2568                         map->stripes[s].physical = devices_info[i].dev_offset +
2569                                                    j * stripe_size;
2570                 }
2571         }
2572         map->sector_size = extent_root->sectorsize;
2573         map->stripe_len = BTRFS_STRIPE_LEN;
2574         map->io_align = BTRFS_STRIPE_LEN;
2575         map->io_width = BTRFS_STRIPE_LEN;
2576         map->type = type;
2577         map->sub_stripes = sub_stripes;
2578
2579         *map_ret = map;
2580         num_bytes = stripe_size * (num_stripes / ncopies);
2581
2582         *stripe_size_out = stripe_size;
2583         *num_bytes_out = num_bytes;
2584
2585         trace_btrfs_chunk_alloc(info->chunk_root, map, start, num_bytes);
2586
2587         em = alloc_extent_map();
2588         if (!em) {
2589                 ret = -ENOMEM;
2590                 goto error;
2591         }
2592         em->bdev = (struct block_device *)map;
2593         em->start = start;
2594         em->len = num_bytes;
2595         em->block_start = 0;
2596         em->block_len = em->len;
2597
2598         em_tree = &extent_root->fs_info->mapping_tree.map_tree;
2599         write_lock(&em_tree->lock);
2600         ret = add_extent_mapping(em_tree, em);
2601         write_unlock(&em_tree->lock);
2602         BUG_ON(ret);
2603         free_extent_map(em);
2604
2605         ret = btrfs_make_block_group(trans, extent_root, 0, type,
2606                                      BTRFS_FIRST_CHUNK_TREE_OBJECTID,
2607                                      start, num_bytes);
2608         BUG_ON(ret);
2609
2610         for (i = 0; i < map->num_stripes; ++i) {
2611                 struct btrfs_device *device;
2612                 u64 dev_offset;
2613
2614                 device = map->stripes[i].dev;
2615                 dev_offset = map->stripes[i].physical;
2616
2617                 ret = btrfs_alloc_dev_extent(trans, device,
2618                                 info->chunk_root->root_key.objectid,
2619                                 BTRFS_FIRST_CHUNK_TREE_OBJECTID,
2620                                 start, dev_offset, stripe_size);
2621                 BUG_ON(ret);
2622         }
2623
2624         kfree(devices_info);
2625         return 0;
2626
2627 error:
2628         kfree(map);
2629         kfree(devices_info);
2630         return ret;
2631 }
2632
2633 static int __finish_chunk_alloc(struct btrfs_trans_handle *trans,
2634                                 struct btrfs_root *extent_root,
2635                                 struct map_lookup *map, u64 chunk_offset,
2636                                 u64 chunk_size, u64 stripe_size)
2637 {
2638         u64 dev_offset;
2639         struct btrfs_key key;
2640         struct btrfs_root *chunk_root = extent_root->fs_info->chunk_root;
2641         struct btrfs_device *device;
2642         struct btrfs_chunk *chunk;
2643         struct btrfs_stripe *stripe;
2644         size_t item_size = btrfs_chunk_item_size(map->num_stripes);
2645         int index = 0;
2646         int ret;
2647
2648         chunk = kzalloc(item_size, GFP_NOFS);
2649         if (!chunk)
2650                 return -ENOMEM;
2651
2652         index = 0;
2653         while (index < map->num_stripes) {
2654                 device = map->stripes[index].dev;
2655                 device->bytes_used += stripe_size;
2656                 ret = btrfs_update_device(trans, device);
2657                 BUG_ON(ret);
2658                 index++;
2659         }
2660
2661         spin_lock(&extent_root->fs_info->free_chunk_lock);
2662         extent_root->fs_info->free_chunk_space -= (stripe_size *
2663                                                    map->num_stripes);
2664         spin_unlock(&extent_root->fs_info->free_chunk_lock);
2665
2666         index = 0;
2667         stripe = &chunk->stripe;
2668         while (index < map->num_stripes) {
2669                 device = map->stripes[index].dev;
2670                 dev_offset = map->stripes[index].physical;
2671
2672                 btrfs_set_stack_stripe_devid(stripe, device->devid);
2673                 btrfs_set_stack_stripe_offset(stripe, dev_offset);
2674                 memcpy(stripe->dev_uuid, device->uuid, BTRFS_UUID_SIZE);
2675                 stripe++;
2676                 index++;
2677         }
2678
2679         btrfs_set_stack_chunk_length(chunk, chunk_size);
2680         btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
2681         btrfs_set_stack_chunk_stripe_len(chunk, map->stripe_len);
2682         btrfs_set_stack_chunk_type(chunk, map->type);
2683         btrfs_set_stack_chunk_num_stripes(chunk, map->num_stripes);
2684         btrfs_set_stack_chunk_io_align(chunk, map->stripe_len);
2685         btrfs_set_stack_chunk_io_width(chunk, map->stripe_len);
2686         btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
2687         btrfs_set_stack_chunk_sub_stripes(chunk, map->sub_stripes);
2688
2689         key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2690         key.type = BTRFS_CHUNK_ITEM_KEY;
2691         key.offset = chunk_offset;
2692
2693         ret = btrfs_insert_item(trans, chunk_root, &key, chunk, item_size);
2694         BUG_ON(ret);
2695
2696         if (map->type & BTRFS_BLOCK_GROUP_SYSTEM) {
2697                 ret = btrfs_add_system_chunk(trans, chunk_root, &key, chunk,
2698                                              item_size);
2699                 BUG_ON(ret);
2700         }
2701
2702         kfree(chunk);
2703         return 0;
2704 }
2705
2706 /*
2707  * Chunk allocation falls into two parts. The first part does works
2708  * that make the new allocated chunk useable, but not do any operation
2709  * that modifies the chunk tree. The second part does the works that
2710  * require modifying the chunk tree. This division is important for the
2711  * bootstrap process of adding storage to a seed btrfs.
2712  */
2713 int btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
2714                       struct btrfs_root *extent_root, u64 type)
2715 {
2716         u64 chunk_offset;
2717         u64 chunk_size;
2718         u64 stripe_size;
2719         struct map_lookup *map;
2720         struct btrfs_root *chunk_root = extent_root->fs_info->chunk_root;
2721         int ret;
2722
2723         ret = find_next_chunk(chunk_root, BTRFS_FIRST_CHUNK_TREE_OBJECTID,
2724                               &chunk_offset);
2725         if (ret)
2726                 return ret;
2727
2728         ret = __btrfs_alloc_chunk(trans, extent_root, &map, &chunk_size,
2729                                   &stripe_size, chunk_offset, type);
2730         if (ret)
2731                 return ret;
2732
2733         ret = __finish_chunk_alloc(trans, extent_root, map, chunk_offset,
2734                                    chunk_size, stripe_size);
2735         BUG_ON(ret);
2736         return 0;
2737 }
2738
2739 static noinline int init_first_rw_device(struct btrfs_trans_handle *trans,
2740                                          struct btrfs_root *root,
2741                                          struct btrfs_device *device)
2742 {
2743         u64 chunk_offset;
2744         u64 sys_chunk_offset;
2745         u64 chunk_size;
2746         u64 sys_chunk_size;
2747         u64 stripe_size;
2748         u64 sys_stripe_size;
2749         u64 alloc_profile;
2750         struct map_lookup *map;
2751         struct map_lookup *sys_map;
2752         struct btrfs_fs_info *fs_info = root->fs_info;
2753         struct btrfs_root *extent_root = fs_info->extent_root;
2754         int ret;
2755
2756         ret = find_next_chunk(fs_info->chunk_root,
2757                               BTRFS_FIRST_CHUNK_TREE_OBJECTID, &chunk_offset);
2758         if (ret)
2759                 return ret;
2760
2761         alloc_profile = BTRFS_BLOCK_GROUP_METADATA |
2762                         (fs_info->metadata_alloc_profile &
2763                          fs_info->avail_metadata_alloc_bits);
2764         alloc_profile = btrfs_reduce_alloc_profile(root, alloc_profile);
2765
2766         ret = __btrfs_alloc_chunk(trans, extent_root, &map, &chunk_size,
2767                                   &stripe_size, chunk_offset, alloc_profile);
2768         BUG_ON(ret);
2769
2770         sys_chunk_offset = chunk_offset + chunk_size;
2771
2772         alloc_profile = BTRFS_BLOCK_GROUP_SYSTEM |
2773                         (fs_info->system_alloc_profile &
2774                          fs_info->avail_system_alloc_bits);
2775         alloc_profile = btrfs_reduce_alloc_profile(root, alloc_profile);
2776
2777         ret = __btrfs_alloc_chunk(trans, extent_root, &sys_map,
2778                                   &sys_chunk_size, &sys_stripe_size,
2779                                   sys_chunk_offset, alloc_profile);
2780         BUG_ON(ret);
2781
2782         ret = btrfs_add_device(trans, fs_info->chunk_root, device);
2783         BUG_ON(ret);
2784
2785         /*
2786          * Modifying chunk tree needs allocating new blocks from both
2787          * system block group and metadata block group. So we only can
2788          * do operations require modifying the chunk tree after both
2789          * block groups were created.
2790          */
2791         ret = __finish_chunk_alloc(trans, extent_root, map, chunk_offset,
2792                                    chunk_size, stripe_size);
2793         BUG_ON(ret);
2794
2795         ret = __finish_chunk_alloc(trans, extent_root, sys_map,
2796                                    sys_chunk_offset, sys_chunk_size,
2797                                    sys_stripe_size);
2798         BUG_ON(ret);
2799         return 0;
2800 }
2801
2802 int btrfs_chunk_readonly(struct btrfs_root *root, u64 chunk_offset)
2803 {
2804         struct extent_map *em;
2805         struct map_lookup *map;
2806         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
2807         int readonly = 0;
2808         int i;
2809
2810         read_lock(&map_tree->map_tree.lock);
2811         em = lookup_extent_mapping(&map_tree->map_tree, chunk_offset, 1);
2812         read_unlock(&map_tree->map_tree.lock);
2813         if (!em)
2814                 return 1;
2815
2816         if (btrfs_test_opt(root, DEGRADED)) {
2817                 free_extent_map(em);
2818                 return 0;
2819         }
2820
2821         map = (struct map_lookup *)em->bdev;
2822         for (i = 0; i < map->num_stripes; i++) {
2823                 if (!map->stripes[i].dev->writeable) {
2824                         readonly = 1;
2825                         break;
2826                 }
2827         }
2828         free_extent_map(em);
2829         return readonly;
2830 }
2831
2832 void btrfs_mapping_init(struct btrfs_mapping_tree *tree)
2833 {
2834         extent_map_tree_init(&tree->map_tree);
2835 }
2836
2837 void btrfs_mapping_tree_free(struct btrfs_mapping_tree *tree)
2838 {
2839         struct extent_map *em;
2840
2841         while (1) {
2842                 write_lock(&tree->map_tree.lock);
2843                 em = lookup_extent_mapping(&tree->map_tree, 0, (u64)-1);
2844                 if (em)
2845                         remove_extent_mapping(&tree->map_tree, em);
2846                 write_unlock(&tree->map_tree.lock);
2847                 if (!em)
2848                         break;
2849                 kfree(em->bdev);
2850                 /* once for us */
2851                 free_extent_map(em);
2852                 /* once for the tree */
2853                 free_extent_map(em);
2854         }
2855 }
2856
2857 int btrfs_num_copies(struct btrfs_mapping_tree *map_tree, u64 logical, u64 len)
2858 {
2859         struct extent_map *em;
2860         struct map_lookup *map;
2861         struct extent_map_tree *em_tree = &map_tree->map_tree;
2862         int ret;
2863
2864         read_lock(&em_tree->lock);
2865         em = lookup_extent_mapping(em_tree, logical, len);
2866         read_unlock(&em_tree->lock);
2867         BUG_ON(!em);
2868
2869         BUG_ON(em->start > logical || em->start + em->len < logical);
2870         map = (struct map_lookup *)em->bdev;
2871         if (map->type & (BTRFS_BLOCK_GROUP_DUP | BTRFS_BLOCK_GROUP_RAID1))
2872                 ret = map->num_stripes;
2873         else if (map->type & BTRFS_BLOCK_GROUP_RAID10)
2874                 ret = map->sub_stripes;
2875         else
2876                 ret = 1;
2877         free_extent_map(em);
2878         return ret;
2879 }
2880
2881 static int find_live_mirror(struct map_lookup *map, int first, int num,
2882                             int optimal)
2883 {
2884         int i;
2885         if (map->stripes[optimal].dev->bdev)
2886                 return optimal;
2887         for (i = first; i < first + num; i++) {
2888                 if (map->stripes[i].dev->bdev)
2889                         return i;
2890         }
2891         /* we couldn't find one that doesn't fail.  Just return something
2892          * and the io error handling code will clean up eventually
2893          */
2894         return optimal;
2895 }
2896
2897 static int __btrfs_map_block(struct btrfs_mapping_tree *map_tree, int rw,
2898                              u64 logical, u64 *length,
2899                              struct btrfs_bio **bbio_ret,
2900                              int mirror_num)
2901 {
2902         struct extent_map *em;
2903         struct map_lookup *map;
2904         struct extent_map_tree *em_tree = &map_tree->map_tree;
2905         u64 offset;
2906         u64 stripe_offset;
2907         u64 stripe_end_offset;
2908         u64 stripe_nr;
2909         u64 stripe_nr_orig;
2910         u64 stripe_nr_end;
2911         int stripes_allocated = 8;
2912         int stripes_required = 1;
2913         int stripe_index;
2914         int i;
2915         int num_stripes;
2916         int max_errors = 0;
2917         struct btrfs_bio *bbio = NULL;
2918
2919         if (bbio_ret && !(rw & (REQ_WRITE | REQ_DISCARD)))
2920                 stripes_allocated = 1;
2921 again:
2922         if (bbio_ret) {
2923                 bbio = kzalloc(btrfs_bio_size(stripes_allocated),
2924                                 GFP_NOFS);
2925                 if (!bbio)
2926                         return -ENOMEM;
2927
2928                 atomic_set(&bbio->error, 0);
2929         }
2930
2931         read_lock(&em_tree->lock);
2932         em = lookup_extent_mapping(em_tree, logical, *length);
2933         read_unlock(&em_tree->lock);
2934
2935         if (!em) {
2936                 printk(KERN_CRIT "unable to find logical %llu len %llu\n",
2937                        (unsigned long long)logical,
2938                        (unsigned long long)*length);
2939                 BUG();
2940         }
2941
2942         BUG_ON(em->start > logical || em->start + em->len < logical);
2943         map = (struct map_lookup *)em->bdev;
2944         offset = logical - em->start;
2945
2946         if (mirror_num > map->num_stripes)
2947                 mirror_num = 0;
2948
2949         /* if our btrfs_bio struct is too small, back off and try again */
2950         if (rw & REQ_WRITE) {
2951                 if (map->type & (BTRFS_BLOCK_GROUP_RAID1 |
2952                                  BTRFS_BLOCK_GROUP_DUP)) {
2953                         stripes_required = map->num_stripes;
2954                         max_errors = 1;
2955                 } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
2956                         stripes_required = map->sub_stripes;
2957                         max_errors = 1;
2958                 }
2959         }
2960         if (rw & REQ_DISCARD) {
2961                 if (map->type & (BTRFS_BLOCK_GROUP_RAID0 |
2962                                  BTRFS_BLOCK_GROUP_RAID1 |
2963                                  BTRFS_BLOCK_GROUP_DUP |
2964                                  BTRFS_BLOCK_GROUP_RAID10)) {
2965                         stripes_required = map->num_stripes;
2966                 }
2967         }
2968         if (bbio_ret && (rw & (REQ_WRITE | REQ_DISCARD)) &&
2969             stripes_allocated < stripes_required) {
2970                 stripes_allocated = map->num_stripes;
2971                 free_extent_map(em);
2972                 kfree(bbio);
2973                 goto again;
2974         }
2975         stripe_nr = offset;
2976         /*
2977          * stripe_nr counts the total number of stripes we have to stride
2978          * to get to this block
2979          */
2980         do_div(stripe_nr, map->stripe_len);
2981
2982         stripe_offset = stripe_nr * map->stripe_len;
2983         BUG_ON(offset < stripe_offset);
2984
2985         /* stripe_offset is the offset of this block in its stripe*/
2986         stripe_offset = offset - stripe_offset;
2987
2988         if (rw & REQ_DISCARD)
2989                 *length = min_t(u64, em->len - offset, *length);
2990         else if (map->type & (BTRFS_BLOCK_GROUP_RAID0 |
2991                               BTRFS_BLOCK_GROUP_RAID1 |
2992                               BTRFS_BLOCK_GROUP_RAID10 |
2993                               BTRFS_BLOCK_GROUP_DUP)) {
2994                 /* we limit the length of each bio to what fits in a stripe */
2995                 *length = min_t(u64, em->len - offset,
2996                                 map->stripe_len - stripe_offset);
2997         } else {
2998                 *length = em->len - offset;
2999         }
3000
3001         if (!bbio_ret)
3002                 goto out;
3003
3004         num_stripes = 1;
3005         stripe_index = 0;
3006         stripe_nr_orig = stripe_nr;
3007         stripe_nr_end = (offset + *length + map->stripe_len - 1) &
3008                         (~(map->stripe_len - 1));
3009         do_div(stripe_nr_end, map->stripe_len);
3010         stripe_end_offset = stripe_nr_end * map->stripe_len -
3011                             (offset + *length);
3012         if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
3013                 if (rw & REQ_DISCARD)
3014                         num_stripes = min_t(u64, map->num_stripes,
3015                                             stripe_nr_end - stripe_nr_orig);
3016                 stripe_index = do_div(stripe_nr, map->num_stripes);
3017         } else if (map->type & BTRFS_BLOCK_GROUP_RAID1) {
3018                 if (rw & (REQ_WRITE | REQ_DISCARD))
3019                         num_stripes = map->num_stripes;
3020                 else if (mirror_num)
3021                         stripe_index = mirror_num - 1;
3022                 else {
3023                         stripe_index = find_live_mirror(map, 0,
3024                                             map->num_stripes,
3025                                             current->pid % map->num_stripes);
3026                         mirror_num = stripe_index + 1;
3027                 }
3028
3029         } else if (map->type & BTRFS_BLOCK_GROUP_DUP) {
3030                 if (rw & (REQ_WRITE | REQ_DISCARD)) {
3031                         num_stripes = map->num_stripes;
3032                 } else if (mirror_num) {
3033                         stripe_index = mirror_num - 1;
3034                 } else {
3035                         mirror_num = 1;
3036                 }
3037
3038         } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
3039                 int factor = map->num_stripes / map->sub_stripes;
3040
3041                 stripe_index = do_div(stripe_nr, factor);
3042                 stripe_index *= map->sub_stripes;
3043
3044                 if (rw & REQ_WRITE)
3045                         num_stripes = map->sub_stripes;
3046                 else if (rw & REQ_DISCARD)
3047                         num_stripes = min_t(u64, map->sub_stripes *
3048                                             (stripe_nr_end - stripe_nr_orig),
3049                                             map->num_stripes);
3050                 else if (mirror_num)
3051                         stripe_index += mirror_num - 1;
3052                 else {
3053                         stripe_index = find_live_mirror(map, stripe_index,
3054                                               map->sub_stripes, stripe_index +
3055                                               current->pid % map->sub_stripes);
3056                         mirror_num = stripe_index + 1;
3057                 }
3058         } else {
3059                 /*
3060                  * after this do_div call, stripe_nr is the number of stripes
3061                  * on this device we have to walk to find the data, and
3062                  * stripe_index is the number of our device in the stripe array
3063                  */
3064                 stripe_index = do_div(stripe_nr, map->num_stripes);
3065                 mirror_num = stripe_index + 1;
3066         }
3067         BUG_ON(stripe_index >= map->num_stripes);
3068
3069         if (rw & REQ_DISCARD) {
3070                 for (i = 0; i < num_stripes; i++) {
3071                         bbio->stripes[i].physical =
3072                                 map->stripes[stripe_index].physical +
3073                                 stripe_offset + stripe_nr * map->stripe_len;
3074                         bbio->stripes[i].dev = map->stripes[stripe_index].dev;
3075
3076                         if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
3077                                 u64 stripes;
3078                                 u32 last_stripe = 0;
3079                                 int j;
3080
3081                                 div_u64_rem(stripe_nr_end - 1,
3082                                             map->num_stripes,
3083                                             &last_stripe);
3084
3085                                 for (j = 0; j < map->num_stripes; j++) {
3086                                         u32 test;
3087
3088                                         div_u64_rem(stripe_nr_end - 1 - j,
3089                                                     map->num_stripes, &test);
3090                                         if (test == stripe_index)
3091                                                 break;
3092                                 }
3093                                 stripes = stripe_nr_end - 1 - j;
3094                                 do_div(stripes, map->num_stripes);
3095                                 bbio->stripes[i].length = map->stripe_len *
3096                                         (stripes - stripe_nr + 1);
3097
3098                                 if (i == 0) {
3099                                         bbio->stripes[i].length -=
3100                                                 stripe_offset;
3101                                         stripe_offset = 0;
3102                                 }
3103                                 if (stripe_index == last_stripe)
3104                                         bbio->stripes[i].length -=
3105                                                 stripe_end_offset;
3106                         } else if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
3107                                 u64 stripes;
3108                                 int j;
3109                                 int factor = map->num_stripes /
3110                                              map->sub_stripes;
3111                                 u32 last_stripe = 0;
3112
3113                                 div_u64_rem(stripe_nr_end - 1,
3114                                             factor, &last_stripe);
3115                                 last_stripe *= map->sub_stripes;
3116
3117                                 for (j = 0; j < factor; j++) {
3118                                         u32 test;
3119
3120                                         div_u64_rem(stripe_nr_end - 1 - j,
3121                                                     factor, &test);
3122
3123                                         if (test ==
3124                                             stripe_index / map->sub_stripes)
3125                                                 break;
3126                                 }
3127                                 stripes = stripe_nr_end - 1 - j;
3128                                 do_div(stripes, factor);
3129                                 bbio->stripes[i].length = map->stripe_len *
3130                                         (stripes - stripe_nr + 1);
3131
3132                                 if (i < map->sub_stripes) {
3133                                         bbio->stripes[i].length -=
3134                                                 stripe_offset;
3135                                         if (i == map->sub_stripes - 1)
3136                                                 stripe_offset = 0;
3137                                 }
3138                                 if (stripe_index >= last_stripe &&
3139                                     stripe_index <= (last_stripe +
3140                                                      map->sub_stripes - 1)) {
3141                                         bbio->stripes[i].length -=
3142                                                 stripe_end_offset;
3143                                 }
3144                         } else
3145                                 bbio->stripes[i].length = *length;
3146
3147                         stripe_index++;
3148                         if (stripe_index == map->num_stripes) {
3149                                 /* This could only happen for RAID0/10 */
3150                                 stripe_index = 0;
3151                                 stripe_nr++;
3152                         }
3153                 }
3154         } else {
3155                 for (i = 0; i < num_stripes; i++) {
3156                         bbio->stripes[i].physical =
3157                                 map->stripes[stripe_index].physical +
3158                                 stripe_offset +
3159                                 stripe_nr * map->stripe_len;
3160                         bbio->stripes[i].dev =
3161                                 map->stripes[stripe_index].dev;
3162                         stripe_index++;
3163                 }
3164         }
3165         if (bbio_ret) {
3166                 *bbio_ret = bbio;
3167                 bbio->num_stripes = num_stripes;
3168                 bbio->max_errors = max_errors;
3169                 bbio->mirror_num = mirror_num;
3170         }
3171 out:
3172         free_extent_map(em);
3173         return 0;
3174 }
3175
3176 int btrfs_map_block(struct btrfs_mapping_tree *map_tree, int rw,
3177                       u64 logical, u64 *length,
3178                       struct btrfs_bio **bbio_ret, int mirror_num)
3179 {
3180         return __btrfs_map_block(map_tree, rw, logical, length, bbio_ret,
3181                                  mirror_num);
3182 }
3183
3184 int btrfs_rmap_block(struct btrfs_mapping_tree *map_tree,
3185                      u64 chunk_start, u64 physical, u64 devid,
3186                      u64 **logical, int *naddrs, int *stripe_len)
3187 {
3188         struct extent_map_tree *em_tree = &map_tree->map_tree;
3189         struct extent_map *em;
3190         struct map_lookup *map;
3191         u64 *buf;
3192         u64 bytenr;
3193         u64 length;
3194         u64 stripe_nr;
3195         int i, j, nr = 0;
3196
3197         read_lock(&em_tree->lock);
3198         em = lookup_extent_mapping(em_tree, chunk_start, 1);
3199         read_unlock(&em_tree->lock);
3200
3201         BUG_ON(!em || em->start != chunk_start);
3202         map = (struct map_lookup *)em->bdev;
3203
3204         length = em->len;
3205         if (map->type & BTRFS_BLOCK_GROUP_RAID10)
3206                 do_div(length, map->num_stripes / map->sub_stripes);
3207         else if (map->type & BTRFS_BLOCK_GROUP_RAID0)
3208                 do_div(length, map->num_stripes);
3209
3210         buf = kzalloc(sizeof(u64) * map->num_stripes, GFP_NOFS);
3211         BUG_ON(!buf);
3212
3213         for (i = 0; i < map->num_stripes; i++) {
3214                 if (devid && map->stripes[i].dev->devid != devid)
3215                         continue;
3216                 if (map->stripes[i].physical > physical ||
3217                     map->stripes[i].physical + length <= physical)
3218                         continue;
3219
3220                 stripe_nr = physical - map->stripes[i].physical;
3221                 do_div(stripe_nr, map->stripe_len);
3222
3223                 if (map->type & BTRFS_BLOCK_GROUP_RAID10) {
3224                         stripe_nr = stripe_nr * map->num_stripes + i;
3225                         do_div(stripe_nr, map->sub_stripes);
3226                 } else if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
3227                         stripe_nr = stripe_nr * map->num_stripes + i;
3228                 }
3229                 bytenr = chunk_start + stripe_nr * map->stripe_len;
3230                 WARN_ON(nr >= map->num_stripes);
3231                 for (j = 0; j < nr; j++) {
3232                         if (buf[j] == bytenr)
3233                                 break;
3234                 }
3235                 if (j == nr) {
3236                         WARN_ON(nr >= map->num_stripes);
3237                         buf[nr++] = bytenr;
3238                 }
3239         }
3240
3241         *logical = buf;
3242         *naddrs = nr;
3243         *stripe_len = map->stripe_len;
3244
3245         free_extent_map(em);
3246         return 0;
3247 }
3248
3249 static void btrfs_end_bio(struct bio *bio, int err)
3250 {
3251         struct btrfs_bio *bbio = bio->bi_private;
3252         int is_orig_bio = 0;
3253
3254         if (err)
3255                 atomic_inc(&bbio->error);
3256
3257         if (bio == bbio->orig_bio)
3258                 is_orig_bio = 1;
3259
3260         if (atomic_dec_and_test(&bbio->stripes_pending)) {
3261                 if (!is_orig_bio) {
3262                         bio_put(bio);
3263                         bio = bbio->orig_bio;
3264                 }
3265                 bio->bi_private = bbio->private;
3266                 bio->bi_end_io = bbio->end_io;
3267                 bio->bi_bdev = (struct block_device *)
3268                                         (unsigned long)bbio->mirror_num;
3269                 /* only send an error to the higher layers if it is
3270                  * beyond the tolerance of the multi-bio
3271                  */
3272                 if (atomic_read(&bbio->error) > bbio->max_errors) {
3273                         err = -EIO;
3274                 } else {
3275                         /*
3276                          * this bio is actually up to date, we didn't
3277                          * go over the max number of errors
3278                          */
3279                         set_bit(BIO_UPTODATE, &bio->bi_flags);
3280                         err = 0;
3281                 }
3282                 kfree(bbio);
3283
3284                 bio_endio(bio, err);
3285         } else if (!is_orig_bio) {
3286                 bio_put(bio);
3287         }
3288 }
3289
3290 struct async_sched {
3291         struct bio *bio;
3292         int rw;
3293         struct btrfs_fs_info *info;
3294         struct btrfs_work work;
3295 };
3296
3297 /*
3298  * see run_scheduled_bios for a description of why bios are collected for
3299  * async submit.
3300  *
3301  * This will add one bio to the pending list for a device and make sure
3302  * the work struct is scheduled.
3303  */
3304 static noinline int schedule_bio(struct btrfs_root *root,
3305                                  struct btrfs_device *device,
3306                                  int rw, struct bio *bio)
3307 {
3308         int should_queue = 1;
3309         struct btrfs_pending_bios *pending_bios;
3310
3311         /* don't bother with additional async steps for reads, right now */
3312         if (!(rw & REQ_WRITE)) {
3313                 bio_get(bio);
3314                 submit_bio(rw, bio);
3315                 bio_put(bio);
3316                 return 0;
3317         }
3318
3319         /*
3320          * nr_async_bios allows us to reliably return congestion to the
3321          * higher layers.  Otherwise, the async bio makes it appear we have
3322          * made progress against dirty pages when we've really just put it
3323          * on a queue for later
3324          */
3325         atomic_inc(&root->fs_info->nr_async_bios);
3326         WARN_ON(bio->bi_next);
3327         bio->bi_next = NULL;
3328         bio->bi_rw |= rw;
3329
3330         spin_lock(&device->io_lock);
3331         if (bio->bi_rw & REQ_SYNC)
3332                 pending_bios = &device->pending_sync_bios;
3333         else
3334                 pending_bios = &device->pending_bios;
3335
3336         if (pending_bios->tail)
3337                 pending_bios->tail->bi_next = bio;
3338
3339         pending_bios->tail = bio;
3340         if (!pending_bios->head)
3341                 pending_bios->head = bio;
3342         if (device->running_pending)
3343                 should_queue = 0;
3344
3345         spin_unlock(&device->io_lock);
3346
3347         if (should_queue)
3348                 btrfs_queue_worker(&root->fs_info->submit_workers,
3349                                    &device->work);
3350         return 0;
3351 }
3352
3353 int btrfs_map_bio(struct btrfs_root *root, int rw, struct bio *bio,
3354                   int mirror_num, int async_submit)
3355 {
3356         struct btrfs_mapping_tree *map_tree;
3357         struct btrfs_device *dev;
3358         struct bio *first_bio = bio;
3359         u64 logical = (u64)bio->bi_sector << 9;
3360         u64 length = 0;
3361         u64 map_length;
3362         int ret;
3363         int dev_nr = 0;
3364         int total_devs = 1;
3365         struct btrfs_bio *bbio = NULL;
3366
3367         length = bio->bi_size;
3368         map_tree = &root->fs_info->mapping_tree;
3369         map_length = length;
3370
3371         ret = btrfs_map_block(map_tree, rw, logical, &map_length, &bbio,
3372                               mirror_num);
3373         BUG_ON(ret);
3374
3375         total_devs = bbio->num_stripes;
3376         if (map_length < length) {
3377                 printk(KERN_CRIT "mapping failed logical %llu bio len %llu "
3378                        "len %llu\n", (unsigned long long)logical,
3379                        (unsigned long long)length,
3380                        (unsigned long long)map_length);
3381                 BUG();
3382         }
3383
3384         bbio->orig_bio = first_bio;
3385         bbio->private = first_bio->bi_private;
3386         bbio->end_io = first_bio->bi_end_io;
3387         atomic_set(&bbio->stripes_pending, bbio->num_stripes);
3388
3389         while (dev_nr < total_devs) {
3390                 if (dev_nr < total_devs - 1) {
3391                         bio = bio_clone(first_bio, GFP_NOFS);
3392                         BUG_ON(!bio);
3393                 } else {
3394                         bio = first_bio;
3395                 }
3396                 bio->bi_private = bbio;
3397                 bio->bi_end_io = btrfs_end_bio;
3398                 bio->bi_sector = bbio->stripes[dev_nr].physical >> 9;
3399                 dev = bbio->stripes[dev_nr].dev;
3400                 if (dev && dev->bdev && (rw != WRITE || dev->writeable)) {
3401                         pr_debug("btrfs_map_bio: rw %d, secor=%llu, dev=%lu "
3402                                  "(%s id %llu), size=%u\n", rw,
3403                                  (u64)bio->bi_sector, (u_long)dev->bdev->bd_dev,
3404                                  dev->name, dev->devid, bio->bi_size);
3405                         bio->bi_bdev = dev->bdev;
3406                         if (async_submit)
3407                                 schedule_bio(root, dev, rw, bio);
3408                         else
3409                                 submit_bio(rw, bio);
3410                 } else {
3411                         bio->bi_bdev = root->fs_info->fs_devices->latest_bdev;
3412                         bio->bi_sector = logical >> 9;
3413                         bio_endio(bio, -EIO);
3414                 }
3415                 dev_nr++;
3416         }
3417         return 0;
3418 }
3419
3420 struct btrfs_device *btrfs_find_device(struct btrfs_root *root, u64 devid,
3421                                        u8 *uuid, u8 *fsid)
3422 {
3423         struct btrfs_device *device;
3424         struct btrfs_fs_devices *cur_devices;
3425
3426         cur_devices = root->fs_info->fs_devices;
3427         while (cur_devices) {
3428                 if (!fsid ||
3429                     !memcmp(cur_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
3430                         device = __find_device(&cur_devices->devices,
3431                                                devid, uuid);
3432                         if (device)
3433                                 return device;
3434                 }
3435                 cur_devices = cur_devices->seed;
3436         }
3437         return NULL;
3438 }
3439
3440 static struct btrfs_device *add_missing_dev(struct btrfs_root *root,
3441                                             u64 devid, u8 *dev_uuid)
3442 {
3443         struct btrfs_device *device;
3444         struct btrfs_fs_devices *fs_devices = root->fs_info->fs_devices;
3445
3446         device = kzalloc(sizeof(*device), GFP_NOFS);
3447         if (!device)
3448                 return NULL;
3449         list_add(&device->dev_list,
3450                  &fs_devices->devices);
3451         device->dev_root = root->fs_info->dev_root;
3452         device->devid = devid;
3453         device->work.func = pending_bios_fn;
3454         device->fs_devices = fs_devices;
3455         device->missing = 1;
3456         fs_devices->num_devices++;
3457         fs_devices->missing_devices++;
3458         spin_lock_init(&device->io_lock);
3459         INIT_LIST_HEAD(&device->dev_alloc_list);
3460         memcpy(device->uuid, dev_uuid, BTRFS_UUID_SIZE);
3461         return device;
3462 }
3463
3464 static int read_one_chunk(struct btrfs_root *root, struct btrfs_key *key,
3465                           struct extent_buffer *leaf,
3466                           struct btrfs_chunk *chunk)
3467 {
3468         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
3469         struct map_lookup *map;
3470         struct extent_map *em;
3471         u64 logical;
3472         u64 length;
3473         u64 devid;
3474         u8 uuid[BTRFS_UUID_SIZE];
3475         int num_stripes;
3476         int ret;
3477         int i;
3478
3479         logical = key->offset;
3480         length = btrfs_chunk_length(leaf, chunk);
3481
3482         read_lock(&map_tree->map_tree.lock);
3483         em = lookup_extent_mapping(&map_tree->map_tree, logical, 1);
3484         read_unlock(&map_tree->map_tree.lock);
3485
3486         /* already mapped? */
3487         if (em && em->start <= logical && em->start + em->len > logical) {
3488                 free_extent_map(em);
3489                 return 0;
3490         } else if (em) {
3491                 free_extent_map(em);
3492         }
3493
3494         em = alloc_extent_map();
3495         if (!em)
3496                 return -ENOMEM;
3497         num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
3498         map = kmalloc(map_lookup_size(num_stripes), GFP_NOFS);
3499         if (!map) {
3500                 free_extent_map(em);
3501                 return -ENOMEM;
3502         }
3503
3504         em->bdev = (struct block_device *)map;
3505         em->start = logical;
3506         em->len = length;
3507         em->block_start = 0;
3508         em->block_len = em->len;
3509
3510         map->num_stripes = num_stripes;
3511         map->io_width = btrfs_chunk_io_width(leaf, chunk);
3512         map->io_align = btrfs_chunk_io_align(leaf, chunk);
3513         map->sector_size = btrfs_chunk_sector_size(leaf, chunk);
3514         map->stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
3515         map->type = btrfs_chunk_type(leaf, chunk);
3516         map->sub_stripes = btrfs_chunk_sub_stripes(leaf, chunk);
3517         for (i = 0; i < num_stripes; i++) {
3518                 map->stripes[i].physical =
3519                         btrfs_stripe_offset_nr(leaf, chunk, i);
3520                 devid = btrfs_stripe_devid_nr(leaf, chunk, i);
3521                 read_extent_buffer(leaf, uuid, (unsigned long)
3522                                    btrfs_stripe_dev_uuid_nr(chunk, i),
3523                                    BTRFS_UUID_SIZE);
3524                 map->stripes[i].dev = btrfs_find_device(root, devid, uuid,
3525                                                         NULL);
3526                 if (!map->stripes[i].dev && !btrfs_test_opt(root, DEGRADED)) {
3527                         kfree(map);
3528                         free_extent_map(em);
3529                         return -EIO;
3530                 }
3531                 if (!map->stripes[i].dev) {
3532                         map->stripes[i].dev =
3533                                 add_missing_dev(root, devid, uuid);
3534                         if (!map->stripes[i].dev) {
3535                                 kfree(map);
3536                                 free_extent_map(em);
3537                                 return -EIO;
3538                         }
3539                 }
3540                 map->stripes[i].dev->in_fs_metadata = 1;
3541         }
3542
3543         write_lock(&map_tree->map_tree.lock);
3544         ret = add_extent_mapping(&map_tree->map_tree, em);
3545         write_unlock(&map_tree->map_tree.lock);
3546         BUG_ON(ret);
3547         free_extent_map(em);
3548
3549         return 0;
3550 }
3551
3552 static int fill_device_from_item(struct extent_buffer *leaf,
3553                                  struct btrfs_dev_item *dev_item,
3554                                  struct btrfs_device *device)
3555 {
3556         unsigned long ptr;
3557
3558         device->devid = btrfs_device_id(leaf, dev_item);
3559         device->disk_total_bytes = btrfs_device_total_bytes(leaf, dev_item);
3560         device->total_bytes = device->disk_total_bytes;
3561         device->bytes_used = btrfs_device_bytes_used(leaf, dev_item);
3562         device->type = btrfs_device_type(leaf, dev_item);
3563         device->io_align = btrfs_device_io_align(leaf, dev_item);
3564         device->io_width = btrfs_device_io_width(leaf, dev_item);
3565         device->sector_size = btrfs_device_sector_size(leaf, dev_item);
3566
3567         ptr = (unsigned long)btrfs_device_uuid(dev_item);
3568         read_extent_buffer(leaf, device->uuid, ptr, BTRFS_UUID_SIZE);
3569
3570         return 0;
3571 }
3572
3573 static int open_seed_devices(struct btrfs_root *root, u8 *fsid)
3574 {
3575         struct btrfs_fs_devices *fs_devices;
3576         int ret;
3577
3578         mutex_lock(&uuid_mutex);
3579
3580         fs_devices = root->fs_info->fs_devices->seed;
3581         while (fs_devices) {
3582                 if (!memcmp(fs_devices->fsid, fsid, BTRFS_UUID_SIZE)) {
3583                         ret = 0;
3584                         goto out;
3585                 }
3586                 fs_devices = fs_devices->seed;
3587         }
3588
3589         fs_devices = find_fsid(fsid);
3590         if (!fs_devices) {
3591                 ret = -ENOENT;
3592                 goto out;
3593         }
3594
3595         fs_devices = clone_fs_devices(fs_devices);
3596         if (IS_ERR(fs_devices)) {
3597                 ret = PTR_ERR(fs_devices);
3598                 goto out;
3599         }
3600
3601         ret = __btrfs_open_devices(fs_devices, FMODE_READ,
3602                                    root->fs_info->bdev_holder);
3603         if (ret)
3604                 goto out;
3605
3606         if (!fs_devices->seeding) {
3607                 __btrfs_close_devices(fs_devices);
3608                 free_fs_devices(fs_devices);
3609                 ret = -EINVAL;
3610                 goto out;
3611         }
3612
3613         fs_devices->seed = root->fs_info->fs_devices->seed;
3614         root->fs_info->fs_devices->seed = fs_devices;
3615 out:
3616         mutex_unlock(&uuid_mutex);
3617         return ret;
3618 }
3619
3620 static int read_one_dev(struct btrfs_root *root,
3621                         struct extent_buffer *leaf,
3622                         struct btrfs_dev_item *dev_item)
3623 {
3624         struct btrfs_device *device;
3625         u64 devid;
3626         int ret;
3627         u8 fs_uuid[BTRFS_UUID_SIZE];
3628         u8 dev_uuid[BTRFS_UUID_SIZE];
3629
3630         devid = btrfs_device_id(leaf, dev_item);
3631         read_extent_buffer(leaf, dev_uuid,
3632                            (unsigned long)btrfs_device_uuid(dev_item),
3633                            BTRFS_UUID_SIZE);
3634         read_extent_buffer(leaf, fs_uuid,
3635                            (unsigned long)btrfs_device_fsid(dev_item),
3636                            BTRFS_UUID_SIZE);
3637
3638         if (memcmp(fs_uuid, root->fs_info->fsid, BTRFS_UUID_SIZE)) {
3639                 ret = open_seed_devices(root, fs_uuid);
3640                 if (ret && !btrfs_test_opt(root, DEGRADED))
3641                         return ret;
3642         }
3643
3644         device = btrfs_find_device(root, devid, dev_uuid, fs_uuid);
3645         if (!device || !device->bdev) {
3646                 if (!btrfs_test_opt(root, DEGRADED))
3647                         return -EIO;
3648
3649                 if (!device) {
3650                         printk(KERN_WARNING "warning devid %llu missing\n",
3651                                (unsigned long long)devid);
3652                         device = add_missing_dev(root, devid, dev_uuid);
3653                         if (!device)
3654                                 return -ENOMEM;
3655                 } else if (!device->missing) {
3656                         /*
3657                          * this happens when a device that was properly setup
3658                          * in the device info lists suddenly goes bad.
3659                          * device->bdev is NULL, and so we have to set
3660                          * device->missing to one here
3661                          */
3662                         root->fs_info->fs_devices->missing_devices++;
3663                         device->missing = 1;
3664                 }
3665         }
3666
3667         if (device->fs_devices != root->fs_info->fs_devices) {
3668                 BUG_ON(device->writeable);
3669                 if (device->generation !=
3670                     btrfs_device_generation(leaf, dev_item))
3671                         return -EINVAL;
3672         }
3673
3674         fill_device_from_item(leaf, dev_item, device);
3675         device->dev_root = root->fs_info->dev_root;
3676         device->in_fs_metadata = 1;
3677         if (device->writeable) {
3678                 device->fs_devices->total_rw_bytes += device->total_bytes;
3679                 spin_lock(&root->fs_info->free_chunk_lock);
3680                 root->fs_info->free_chunk_space += device->total_bytes -
3681                         device->bytes_used;
3682                 spin_unlock(&root->fs_info->free_chunk_lock);
3683         }
3684         ret = 0;
3685         return ret;
3686 }
3687
3688 int btrfs_read_sys_array(struct btrfs_root *root)
3689 {
3690         struct btrfs_super_block *super_copy = root->fs_info->super_copy;
3691         struct extent_buffer *sb;
3692         struct btrfs_disk_key *disk_key;
3693         struct btrfs_chunk *chunk;
3694         u8 *ptr;
3695         unsigned long sb_ptr;
3696         int ret = 0;
3697         u32 num_stripes;
3698         u32 array_size;
3699         u32 len = 0;
3700         u32 cur;
3701         struct btrfs_key key;
3702
3703         sb = btrfs_find_create_tree_block(root, BTRFS_SUPER_INFO_OFFSET,
3704                                           BTRFS_SUPER_INFO_SIZE);
3705         if (!sb)
3706                 return -ENOMEM;
3707         btrfs_set_buffer_uptodate(sb);
3708         btrfs_set_buffer_lockdep_class(root->root_key.objectid, sb, 0);
3709
3710         write_extent_buffer(sb, super_copy, 0, BTRFS_SUPER_INFO_SIZE);
3711         array_size = btrfs_super_sys_array_size(super_copy);
3712
3713         ptr = super_copy->sys_chunk_array;
3714         sb_ptr = offsetof(struct btrfs_super_block, sys_chunk_array);
3715         cur = 0;
3716
3717         while (cur < array_size) {
3718                 disk_key = (struct btrfs_disk_key *)ptr;
3719                 btrfs_disk_key_to_cpu(&key, disk_key);
3720
3721                 len = sizeof(*disk_key); ptr += len;
3722                 sb_ptr += len;
3723                 cur += len;
3724
3725                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
3726                         chunk = (struct btrfs_chunk *)sb_ptr;
3727                         ret = read_one_chunk(root, &key, sb, chunk);
3728                         if (ret)
3729                                 break;
3730                         num_stripes = btrfs_chunk_num_stripes(sb, chunk);
3731                         len = btrfs_chunk_item_size(num_stripes);
3732                 } else {
3733                         ret = -EIO;
3734                         break;
3735                 }
3736                 ptr += len;
3737                 sb_ptr += len;
3738                 cur += len;
3739         }
3740         free_extent_buffer(sb);
3741         return ret;
3742 }
3743
3744 int btrfs_read_chunk_tree(struct btrfs_root *root)
3745 {
3746         struct btrfs_path *path;
3747         struct extent_buffer *leaf;
3748         struct btrfs_key key;
3749         struct btrfs_key found_key;
3750         int ret;
3751         int slot;
3752
3753         root = root->fs_info->chunk_root;
3754
3755         path = btrfs_alloc_path();
3756         if (!path)
3757                 return -ENOMEM;
3758
3759         /* first we search for all of the device items, and then we
3760          * read in all of the chunk items.  This way we can create chunk
3761          * mappings that reference all of the devices that are afound
3762          */
3763         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
3764         key.offset = 0;
3765         key.type = 0;
3766 again:
3767         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3768         if (ret < 0)
3769                 goto error;
3770         while (1) {
3771                 leaf = path->nodes[0];
3772                 slot = path->slots[0];
3773                 if (slot >= btrfs_header_nritems(leaf)) {
3774                         ret = btrfs_next_leaf(root, path);
3775                         if (ret == 0)
3776                                 continue;
3777                         if (ret < 0)
3778                                 goto error;
3779                         break;
3780                 }
3781                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
3782                 if (key.objectid == BTRFS_DEV_ITEMS_OBJECTID) {
3783                         if (found_key.objectid != BTRFS_DEV_ITEMS_OBJECTID)
3784                                 break;
3785                         if (found_key.type == BTRFS_DEV_ITEM_KEY) {
3786                                 struct btrfs_dev_item *dev_item;
3787                                 dev_item = btrfs_item_ptr(leaf, slot,
3788                                                   struct btrfs_dev_item);
3789                                 ret = read_one_dev(root, leaf, dev_item);
3790                                 if (ret)
3791                                         goto error;
3792                         }
3793                 } else if (found_key.type == BTRFS_CHUNK_ITEM_KEY) {
3794                         struct btrfs_chunk *chunk;
3795                         chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
3796                         ret = read_one_chunk(root, &found_key, leaf, chunk);
3797                         if (ret)
3798                                 goto error;
3799                 }
3800                 path->slots[0]++;
3801         }
3802         if (key.objectid == BTRFS_DEV_ITEMS_OBJECTID) {
3803                 key.objectid = 0;
3804                 btrfs_release_path(path);
3805                 goto again;
3806         }
3807         ret = 0;
3808 error:
3809         btrfs_free_path(path);
3810         return ret;
3811 }