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 #define _XOPEN_SOURCE 600
  19 #define __USE_XOPEN2K
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <sys/types.h>
  23 #include <sys/stat.h>
  24 #include <uuid/uuid.h>
  25 #include <fcntl.h>
  26 #include <unistd.h>
  27 #include "ctree.h"
  28 #include "disk-io.h"
  29 #include "transaction.h"
  30 #include "print-tree.h"
  31 #include "volumes.h"
  32
  33 struct stripe {
  34         struct btrfs_device *dev;
  35         u64 physical;
  36 };
  37
  38 struct map_lookup {
  39         struct cache_extent ce;
  40         u64 type;
  41         int io_align;
  42         int io_width;
  43         int stripe_len;
  44         int sector_size;
  45         int num_stripes;
  46         struct stripe stripes[];
  47 };
  48
  49 #define map_lookup_size(n) (sizeof(struct map_lookup) + \
  50                             (sizeof(struct stripe) * (n)))
  51
  52 static LIST_HEAD(fs_uuids);
  53
  54 static struct btrfs_device *__find_device(struct list_head *head, u64 devid)
  55 {
  56         struct btrfs_device *dev;
  57         struct list_head *cur;
  58
  59         list_for_each(cur, head) {
  60                 dev = list_entry(cur, struct btrfs_device, dev_list);
  61                 if (dev->devid == devid)
  62                         return dev;
  63         }
  64         return NULL;
  65 }
  66
  67 static struct btrfs_fs_devices *find_fsid(u8 *fsid)
  68 {
  69         struct list_head *cur;
  70         struct btrfs_fs_devices *fs_devices;
  71
  72         list_for_each(cur, &fs_uuids) {
  73                 fs_devices = list_entry(cur, struct btrfs_fs_devices, list);
  74                 if (memcmp(fsid, fs_devices->fsid, BTRFS_FSID_SIZE) == 0)
  75                         return fs_devices;
  76         }
  77         return NULL;
  78 }
  79
  80 static int device_list_add(const char *path,
  81                            struct btrfs_super_block *disk_super,
  82                            u64 devid, struct btrfs_fs_devices **fs_devices_ret)
  83 {
  84         struct btrfs_device *device;
  85         struct btrfs_fs_devices *fs_devices;
  86         u64 found_transid = btrfs_super_generation(disk_super);
  87
  88         fs_devices = find_fsid(disk_super->fsid);
  89         if (!fs_devices) {
  90                 fs_devices = kmalloc(sizeof(*fs_devices), GFP_NOFS);
  91                 if (!fs_devices)
  92                         return -ENOMEM;
  93                 INIT_LIST_HEAD(&fs_devices->devices);
  94                 list_add(&fs_devices->list, &fs_uuids);
  95                 memcpy(fs_devices->fsid, disk_super->fsid, BTRFS_FSID_SIZE);
  96                 fs_devices->latest_devid = devid;
  97                 fs_devices->latest_trans = found_transid;
  98                 fs_devices->lowest_devid = (u64)-1;
  99                 device = NULL;
 100         } else {
 101                 device = __find_device(&fs_devices->devices, devid);
 102         }
 103         if (!device) {
 104                 device = kzalloc(sizeof(*device), GFP_NOFS);
 105                 if (!device) {
 106                         /* we can safely leave the fs_devices entry around */
 107                         return -ENOMEM;
 108                 }
 109                 device->devid = devid;
 110                 device->name = kstrdup(path, GFP_NOFS);
 111                 if (!device->name) {
 112                         kfree(device);
 113                         return -ENOMEM;
 114                 }
 115                 list_add(&device->dev_list, &fs_devices->devices);
 116         }
 117
 118         if (found_transid > fs_devices->latest_trans) {
 119                 fs_devices->latest_devid = devid;
 120                 fs_devices->latest_trans = found_transid;
 121         }
 122         if (fs_devices->lowest_devid > devid) {
 123                 fs_devices->lowest_devid = devid;
 124                 printk("lowest devid now %Lu\n", devid);
 125         }
 126         *fs_devices_ret = fs_devices;
 127         return 0;
 128 }
 129
 130 int btrfs_close_devices(struct btrfs_fs_devices *fs_devices)
 131 {
 132         struct list_head *head = &fs_devices->devices;
 133         struct list_head *cur;
 134         struct btrfs_device *device;
 135
 136         list_for_each(cur, head) {
 137                 device = list_entry(cur, struct btrfs_device, dev_list);
 138                 device->fd = 0;
 139         }
 140         return 0;
 141 }
 142
 143 int btrfs_open_devices(struct btrfs_fs_devices *fs_devices, int flags)
 144 {
 145         int fd;
 146         struct list_head *head = &fs_devices->devices;
 147         struct list_head *cur;
 148         struct btrfs_device *device;
 149         int ret;
 150
 151         list_for_each(cur, head) {
 152                 device = list_entry(cur, struct btrfs_device, dev_list);
 153                 fd = open(device->name, flags);
 154 printk("opening %s devid %Lu fd %d\n", device->name, device->devid, fd);
 155                 if (fd < 0) {
 156                         ret = -errno;
 157                         goto fail;
 158                 }
 159                 if (device->devid == fs_devices->latest_devid)
 160                         fs_devices->latest_bdev = fd;
 161                 if (device->devid == fs_devices->lowest_devid)
 162                         fs_devices->lowest_bdev = fd;
 163                 device->fd = fd;
 164         }
 165         return 0;
 166 fail:
 167         btrfs_close_devices(fs_devices);
 168         return ret;
 169 }
 170
 171 int btrfs_scan_one_device(int fd, const char *path,
 172                           struct btrfs_fs_devices **fs_devices_ret,
 173                           u64 *total_devs, u64 super_offset)
 174 {
 175         struct btrfs_super_block *disk_super;
 176         char *buf;
 177         int ret;
 178         u64 devid;
 179
 180         buf = malloc(4096);
 181         if (!buf) {
 182                 ret = -ENOMEM;
 183                 goto error;
 184         }
 185         ret = pread(fd, buf, 4096, super_offset);
 186         if (ret != 4096) {
 187                 ret = -EIO;
 188                 goto error;
 189         }
 190         disk_super = (struct btrfs_super_block *)buf;
 191         if (strncmp((char *)(&disk_super->magic), BTRFS_MAGIC,
 192             sizeof(disk_super->magic))) {
 193                 ret = -ENOENT;
 194                 goto error_brelse;
 195         }
 196         devid = le64_to_cpu(disk_super->dev_item.devid);
 197         *total_devs = btrfs_super_num_devices(disk_super);
 198         printk("found device %Lu on %s\n", devid, path);
 199         ret = device_list_add(path, disk_super, devid, fs_devices_ret);
 200
 201 error_brelse:
 202         free(buf);
 203 error:
 204         return ret;
 205 }
 206
 207 /*
 208  * this uses a pretty simple search, the expectation is that it is
 209  * called very infrequently and that a given device has a small number
 210  * of extents
 211  */
 212 static int find_free_dev_extent(struct btrfs_trans_handle *trans,
 213                                 struct btrfs_device *device,
 214                                 struct btrfs_path *path,
 215                                 u64 num_bytes, u64 *start)
 216 {
 217         struct btrfs_key key;
 218         struct btrfs_root *root = device->dev_root;
 219         struct btrfs_dev_extent *dev_extent = NULL;
 220         u64 hole_size = 0;
 221         u64 last_byte = 0;
 222         u64 search_start = 0;
 223         u64 search_end = device->total_bytes;
 224         int ret;
 225         int slot = 0;
 226         int start_found;
 227         struct extent_buffer *l;
 228
 229         start_found = 0;
 230         path->reada = 2;
 231
 232         /* FIXME use last free of some kind */
 233
 234         key.objectid = device->devid;
 235         key.offset = search_start;
 236         key.type = BTRFS_DEV_EXTENT_KEY;
 237         ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
 238         if (ret < 0)
 239                 goto error;
 240         ret = btrfs_previous_item(root, path, 0, key.type);
 241         if (ret < 0)
 242                 goto error;
 243         l = path->nodes[0];
 244         btrfs_item_key_to_cpu(l, &key, path->slots[0]);
 245         while (1) {
 246                 l = path->nodes[0];
 247                 slot = path->slots[0];
 248                 if (slot >= btrfs_header_nritems(l)) {
 249                         ret = btrfs_next_leaf(root, path);
 250                         if (ret == 0)
 251                                 continue;
 252                         if (ret < 0)
 253                                 goto error;
 254 no_more_items:
 255                         if (!start_found) {
 256                                 if (search_start >= search_end) {
 257                                         ret = -ENOSPC;
 258                                         goto error;
 259                                 }
 260                                 *start = search_start;
 261                                 start_found = 1;
 262                                 goto check_pending;
 263                         }
 264                         *start = last_byte > search_start ?
 265                                 last_byte : search_start;
 266                         if (search_end <= *start) {
 267                                 ret = -ENOSPC;
 268                                 goto error;
 269                         }
 270                         goto check_pending;
 271                 }
 272                 btrfs_item_key_to_cpu(l, &key, slot);
 273
 274                 if (key.objectid < device->devid)
 275                         goto next;
 276
 277                 if (key.objectid > device->devid)
 278                         goto no_more_items;
 279
 280                 if (key.offset >= search_start && key.offset > last_byte &&
 281                     start_found) {
 282                         if (last_byte < search_start)
 283                                 last_byte = search_start;
 284                         hole_size = key.offset - last_byte;
 285                         if (key.offset > last_byte &&
 286                             hole_size >= num_bytes) {
 287                                 *start = last_byte;
 288                                 goto check_pending;
 289                         }
 290                 }
 291                 if (btrfs_key_type(&key) != BTRFS_DEV_EXTENT_KEY) {
 292                         goto next;
 293                 }
 294
 295                 start_found = 1;
 296                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 297                 last_byte = key.offset + btrfs_dev_extent_length(l, dev_extent);
 298 next:
 299                 path->slots[0]++;
 300                 cond_resched();
 301         }
 302 check_pending:
 303         /* we have to make sure we didn't find an extent that has already
 304          * been allocated by the map tree or the original allocation
 305          */
 306         btrfs_release_path(root, path);
 307         BUG_ON(*start < search_start);
 308
 309         if (*start + num_bytes > search_end) {
 310                 ret = -ENOSPC;
 311                 goto error;
 312         }
 313         /* check for pending inserts here */
 314         return 0;
 315
 316 error:
 317         btrfs_release_path(root, path);
 318         return ret;
 319 }
 320
 321 int btrfs_alloc_dev_extent(struct btrfs_trans_handle *trans,
 322                            struct btrfs_device *device,
 323                            u64 owner, u64 num_bytes, u64 *start)
 324 {
 325         int ret;
 326         struct btrfs_path *path;
 327         struct btrfs_root *root = device->dev_root;
 328         struct btrfs_dev_extent *extent;
 329         struct extent_buffer *leaf;
 330         struct btrfs_key key;
 331
 332         path = btrfs_alloc_path();
 333         if (!path)
 334                 return -ENOMEM;
 335
 336         ret = find_free_dev_extent(trans, device, path, num_bytes, start);
 337         if (ret) {
 338                 goto err;
 339         }
 340
 341         key.objectid = device->devid;
 342         key.offset = *start;
 343         key.type = BTRFS_DEV_EXTENT_KEY;
 344         ret = btrfs_insert_empty_item(trans, root, path, &key,
 345                                       sizeof(*extent));
 346         BUG_ON(ret);
 347
 348         leaf = path->nodes[0];
 349         extent = btrfs_item_ptr(leaf, path->slots[0],
 350                                 struct btrfs_dev_extent);
 351         btrfs_set_dev_extent_owner(leaf, extent, owner);
 352         btrfs_set_dev_extent_length(leaf, extent, num_bytes);
 353         btrfs_mark_buffer_dirty(leaf);
 354 err:
 355         btrfs_free_path(path);
 356         return ret;
 357 }
 358
 359 static int find_next_chunk(struct btrfs_root *root, u64 *objectid)
 360 {
 361         struct btrfs_path *path;
 362         int ret;
 363         struct btrfs_key key;
 364         struct btrfs_key found_key;
 365
 366         path = btrfs_alloc_path();
 367         BUG_ON(!path);
 368
 369         key.objectid = (u64)-1;
 370         key.offset = (u64)-1;
 371         key.type = BTRFS_CHUNK_ITEM_KEY;
 372
 373         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 374         if (ret < 0)
 375                 goto error;
 376
 377         BUG_ON(ret == 0);
 378
 379         ret = btrfs_previous_item(root, path, 0, BTRFS_CHUNK_ITEM_KEY);
 380         if (ret) {
 381                 *objectid = 0;
 382         } else {
 383                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
 384                                       path->slots[0]);
 385                 *objectid = found_key.objectid + found_key.offset;
 386         }
 387         ret = 0;
 388 error:
 389         btrfs_free_path(path);
 390         return ret;
 391 }
 392
 393 static int find_next_devid(struct btrfs_root *root, struct btrfs_path *path,
 394                            u64 *objectid)
 395 {
 396         int ret;
 397         struct btrfs_key key;
 398         struct btrfs_key found_key;
 399
 400         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 401         key.type = BTRFS_DEV_ITEM_KEY;
 402         key.offset = (u64)-1;
 403
 404         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 405         if (ret < 0)
 406                 goto error;
 407
 408         BUG_ON(ret == 0);
 409
 410         ret = btrfs_previous_item(root, path, BTRFS_DEV_ITEMS_OBJECTID,
 411                                   BTRFS_DEV_ITEM_KEY);
 412         if (ret) {
 413                 *objectid = 1;
 414         } else {
 415                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
 416                                       path->slots[0]);
 417                 *objectid = found_key.offset + 1;
 418         }
 419         ret = 0;
 420 error:
 421         btrfs_release_path(root, path);
 422         return ret;
 423 }
 424
 425 /*
 426  * the device information is stored in the chunk root
 427  * the btrfs_device struct should be fully filled in
 428  */
 429 int btrfs_add_device(struct btrfs_trans_handle *trans,
 430                      struct btrfs_root *root,
 431                      struct btrfs_device *device)
 432 {
 433         int ret;
 434         struct btrfs_path *path;
 435         struct btrfs_dev_item *dev_item;
 436         struct extent_buffer *leaf;
 437         struct btrfs_key key;
 438         unsigned long ptr;
 439         u64 free_devid;
 440
 441         root = root->fs_info->chunk_root;
 442
 443         path = btrfs_alloc_path();
 444         if (!path)
 445                 return -ENOMEM;
 446
 447         ret = find_next_devid(root, path, &free_devid);
 448         if (ret)
 449                 goto out;
 450
 451         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 452         key.type = BTRFS_DEV_ITEM_KEY;
 453         key.offset = free_devid;
 454
 455         ret = btrfs_insert_empty_item(trans, root, path, &key,
 456                                       sizeof(*dev_item));
 457         if (ret)
 458                 goto out;
 459
 460         leaf = path->nodes[0];
 461         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
 462
 463         device->devid = free_devid;
 464         btrfs_set_device_id(leaf, dev_item, device->devid);
 465         btrfs_set_device_type(leaf, dev_item, device->type);
 466         btrfs_set_device_io_align(leaf, dev_item, device->io_align);
 467         btrfs_set_device_io_width(leaf, dev_item, device->io_width);
 468         btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
 469         btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
 470         btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
 471
 472         ptr = (unsigned long)btrfs_device_uuid(dev_item);
 473         write_extent_buffer(leaf, device->uuid, ptr, BTRFS_DEV_UUID_SIZE);
 474         btrfs_mark_buffer_dirty(leaf);
 475         ret = 0;
 476
 477 out:
 478         btrfs_free_path(path);
 479         return ret;
 480 }
 481
 482 int btrfs_update_device(struct btrfs_trans_handle *trans,
 483                         struct btrfs_device *device)
 484 {
 485         int ret;
 486         struct btrfs_path *path;
 487         struct btrfs_root *root;
 488         struct btrfs_dev_item *dev_item;
 489         struct extent_buffer *leaf;
 490         struct btrfs_key key;
 491
 492         root = device->dev_root->fs_info->chunk_root;
 493
 494         path = btrfs_alloc_path();
 495         if (!path)
 496                 return -ENOMEM;
 497
 498         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 499         key.type = BTRFS_DEV_ITEM_KEY;
 500         key.offset = device->devid;
 501
 502         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 503         if (ret < 0)
 504                 goto out;
 505
 506         if (ret > 0) {
 507                 ret = -ENOENT;
 508                 goto out;
 509         }
 510
 511         leaf = path->nodes[0];
 512         dev_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dev_item);
 513
 514         btrfs_set_device_id(leaf, dev_item, device->devid);
 515         btrfs_set_device_type(leaf, dev_item, device->type);
 516         btrfs_set_device_io_align(leaf, dev_item, device->io_align);
 517         btrfs_set_device_io_width(leaf, dev_item, device->io_width);
 518         btrfs_set_device_sector_size(leaf, dev_item, device->sector_size);
 519         btrfs_set_device_total_bytes(leaf, dev_item, device->total_bytes);
 520         btrfs_set_device_bytes_used(leaf, dev_item, device->bytes_used);
 521         btrfs_mark_buffer_dirty(leaf);
 522
 523 out:
 524         btrfs_free_path(path);
 525         return ret;
 526 }
 527
 528 int btrfs_add_system_chunk(struct btrfs_trans_handle *trans,
 529                            struct btrfs_root *root,
 530                            struct btrfs_key *key,
 531                            struct btrfs_chunk *chunk, int item_size)
 532 {
 533         struct btrfs_super_block *super_copy = &root->fs_info->super_copy;
 534         struct btrfs_disk_key disk_key;
 535         u32 array_size;
 536         u8 *ptr;
 537
 538         array_size = btrfs_super_sys_array_size(super_copy);
 539         if (array_size + item_size > BTRFS_SYSTEM_CHUNK_ARRAY_SIZE)
 540                 return -EFBIG;
 541
 542         ptr = super_copy->sys_chunk_array + array_size;
 543         btrfs_cpu_key_to_disk(&disk_key, key);
 544         memcpy(ptr, &disk_key, sizeof(disk_key));
 545         ptr += sizeof(disk_key);
 546         memcpy(ptr, chunk, item_size);
 547         item_size += sizeof(disk_key);
 548         btrfs_set_super_sys_array_size(super_copy, array_size + item_size);
 549         return 0;
 550 }
 551
 552 int btrfs_alloc_chunk(struct btrfs_trans_handle *trans,
 553                       struct btrfs_root *extent_root, u64 *start,
 554                       u64 *num_bytes, u64 type)
 555 {
 556         u64 dev_offset;
 557         struct btrfs_fs_info *info = extent_root->fs_info;
 558         struct btrfs_root *chunk_root = extent_root->fs_info->chunk_root;
 559         struct btrfs_stripe *stripes;
 560         struct btrfs_device *device = NULL;
 561         struct btrfs_chunk *chunk;
 562         struct list_head private_devs;
 563         struct list_head *dev_list = &extent_root->fs_info->fs_devices->devices;
 564         struct list_head *cur;
 565         struct map_lookup *map;
 566         u64 physical;
 567         u64 calc_size = 8 * 1024 * 1024;
 568         u64 avail;
 569         u64 max_avail = 0;
 570         int num_stripes = 1;
 571         int looped = 0;
 572         int ret;
 573         int index;
 574         int stripe_len = 64 * 1024;
 575         struct btrfs_key key;
 576
 577         if (list_empty(dev_list))
 578                 return -ENOSPC;
 579
 580         if (type & BTRFS_BLOCK_GROUP_RAID0)
 581                 num_stripes = btrfs_super_num_devices(&info->super_copy);
 582         if (type & BTRFS_BLOCK_GROUP_DATA)
 583                 stripe_len = 64 * 1024;
 584         if (type & (BTRFS_BLOCK_GROUP_METADATA | BTRFS_BLOCK_GROUP_SYSTEM))
 585                 stripe_len = 32 * 1024;
 586 again:
 587         INIT_LIST_HEAD(&private_devs);
 588         cur = dev_list->next;
 589         index = 0;
 590         /* build a private list of devices we will allocate from */
 591         while(index < num_stripes) {
 592                 device = list_entry(cur, struct btrfs_device, dev_list);
 593                 avail = device->total_bytes - device->bytes_used;
 594                 cur = cur->next;
 595                 if (avail > max_avail)
 596                         max_avail = avail;
 597                 if (avail >= calc_size) {
 598                         list_move_tail(&device->dev_list, &private_devs);
 599                         index++;
 600                 }
 601                 if (cur == dev_list)
 602                         break;
 603         }
 604         if (index < num_stripes) {
 605                 list_splice(&private_devs, dev_list);
 606                 if (!looped && max_avail > 0) {
 607                         looped = 1;
 608                         calc_size = max_avail;
 609                         goto again;
 610                 }
 611                 return -ENOSPC;
 612         }
 613
 614         ret = find_next_chunk(chunk_root, &key.objectid);
 615         if (ret)
 616                 return ret;
 617
 618         chunk = kmalloc(btrfs_chunk_item_size(num_stripes), GFP_NOFS);
 619         if (!chunk)
 620                 return -ENOMEM;
 621
 622         map = kmalloc(map_lookup_size(num_stripes), GFP_NOFS);
 623         if (!map) {
 624                 kfree(chunk);
 625                 return -ENOMEM;
 626         }
 627
 628         stripes = &chunk->stripe;
 629
 630         *num_bytes = calc_size * num_stripes;
 631         index = 0;
 632         while(index < num_stripes) {
 633                 BUG_ON(list_empty(&private_devs));
 634                 cur = private_devs.next;
 635                 device = list_entry(cur, struct btrfs_device, dev_list);
 636                 list_move_tail(&device->dev_list, dev_list);
 637
 638                 ret = btrfs_alloc_dev_extent(trans, device,
 639                                              key.objectid,
 640                                              calc_size, &dev_offset);
 641                 BUG_ON(ret);
 642 printk("alloc chunk size %Lu from dev %Lu\n", calc_size, device->devid);
 643                 device->bytes_used += calc_size;
 644                 ret = btrfs_update_device(trans, device);
 645                 BUG_ON(ret);
 646
 647                 map->stripes[index].dev = device;
 648                 map->stripes[index].physical = dev_offset;
 649                 btrfs_set_stack_stripe_devid(stripes + index, device->devid);
 650                 btrfs_set_stack_stripe_offset(stripes + index, dev_offset);
 651                 physical = dev_offset;
 652                 index++;
 653         }
 654         BUG_ON(!list_empty(&private_devs));
 655
 656         /* key.objectid was set above */
 657         key.offset = *num_bytes;
 658         key.type = BTRFS_CHUNK_ITEM_KEY;
 659         btrfs_set_stack_chunk_owner(chunk, extent_root->root_key.objectid);
 660         btrfs_set_stack_chunk_stripe_len(chunk, stripe_len);
 661         btrfs_set_stack_chunk_type(chunk, type);
 662         btrfs_set_stack_chunk_num_stripes(chunk, num_stripes);
 663         btrfs_set_stack_chunk_io_align(chunk, stripe_len);
 664         btrfs_set_stack_chunk_io_width(chunk, stripe_len);
 665         btrfs_set_stack_chunk_sector_size(chunk, extent_root->sectorsize);
 666         map->sector_size = extent_root->sectorsize;
 667         map->stripe_len = stripe_len;
 668         map->io_align = stripe_len;
 669         map->io_width = stripe_len;
 670         map->type = type;
 671         map->num_stripes = num_stripes;
 672
 673         ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
 674                                 btrfs_chunk_item_size(num_stripes));
 675         BUG_ON(ret);
 676         *start = key.objectid;
 677
 678         map->ce.start = key.objectid;
 679         map->ce.size = key.offset;
 680
 681         ret = insert_existing_cache_extent(
 682                            &extent_root->fs_info->mapping_tree.cache_tree,
 683                            &map->ce);
 684         BUG_ON(ret);
 685
 686         kfree(chunk);
 687         return ret;
 688 }
 689
 690 void btrfs_mapping_init(struct btrfs_mapping_tree *tree)
 691 {
 692         cache_tree_init(&tree->cache_tree);
 693 }
 694
 695 int btrfs_map_block(struct btrfs_mapping_tree *map_tree,
 696                     u64 logical, u64 *phys, u64 *length,
 697                     struct btrfs_device **dev)
 698 {
 699         struct cache_extent *ce;
 700         struct map_lookup *map;
 701         u64 offset;
 702         u64 stripe_offset;
 703         u64 stripe_nr;
 704         int stripe_index;
 705
 706         ce = find_first_cache_extent(&map_tree->cache_tree, logical);
 707         BUG_ON(!ce);
 708         BUG_ON(ce->start > logical || ce->start + ce->size < logical);
 709         map = container_of(ce, struct map_lookup, ce);
 710         offset = logical - ce->start;
 711
 712         stripe_nr = offset;
 713         /*
 714          * stripe_nr counts the total number of stripes we have to stride
 715          * to get to this block
 716          */
 717         stripe_nr = stripe_nr / map->stripe_len;
 718
 719         stripe_offset = stripe_nr * map->stripe_len;
 720         BUG_ON(offset < stripe_offset);
 721
 722         /* stripe_offset is the offset of this block in its stripe*/
 723         stripe_offset = offset - stripe_offset;
 724
 725         /*
 726          * after this do_div call, stripe_nr is the number of stripes
 727          * on this device we have to walk to find the data, and
 728          * stripe_index is the number of our device in the stripe array
 729          */
 730         stripe_index = stripe_nr % map->num_stripes;
 731         stripe_nr = stripe_nr / map->num_stripes;
 732
 733         BUG_ON(stripe_index >= map->num_stripes);
 734
 735         *phys = map->stripes[stripe_index].physical + stripe_offset +
 736                 stripe_nr * map->stripe_len;
 737
 738         if (map->type & BTRFS_BLOCK_GROUP_RAID0) {
 739                 /* we limit the length of each bio to what fits in a stripe */
 740                 *length = min_t(u64, ce->size - offset,
 741                               map->stripe_len - stripe_offset);
 742         } else {
 743                 *length = ce->size - offset;
 744         }
 745         *dev = map->stripes[stripe_index].dev;
 746         return 0;
 747 }
 748
 749 struct btrfs_device *btrfs_find_device(struct btrfs_root *root, u64 devid)
 750 {
 751         struct list_head *head = &root->fs_info->fs_devices->devices;
 752
 753         return __find_device(head, devid);
 754 }
 755
 756 static int read_one_chunk(struct btrfs_root *root, struct btrfs_key *key,
 757                           struct extent_buffer *leaf,
 758                           struct btrfs_chunk *chunk)
 759 {
 760         struct btrfs_mapping_tree *map_tree = &root->fs_info->mapping_tree;
 761         struct map_lookup *map;
 762         struct cache_extent *ce;
 763         u64 logical;
 764         u64 length;
 765         u64 devid;
 766         int num_stripes;
 767         int ret;
 768         int i;
 769
 770         logical = key->objectid;
 771         length = key->offset;
 772         ce = find_first_cache_extent(&map_tree->cache_tree, logical);
 773
 774         /* already mapped? */
 775         if (ce && ce->start <= logical && ce->start + ce->size > logical) {
 776                 return 0;
 777         }
 778
 779         num_stripes = btrfs_chunk_num_stripes(leaf, chunk);
 780         map = kmalloc(map_lookup_size(num_stripes), GFP_NOFS);
 781         if (!map)
 782                 return -ENOMEM;
 783
 784         map->ce.start = logical;
 785         map->ce.size = length;
 786
 787         map->num_stripes = num_stripes;
 788         map->io_width = btrfs_chunk_io_width(leaf, chunk);
 789         map->io_align = btrfs_chunk_io_align(leaf, chunk);
 790         map->sector_size = btrfs_chunk_sector_size(leaf, chunk);
 791         map->stripe_len = btrfs_chunk_stripe_len(leaf, chunk);
 792         map->type = btrfs_chunk_type(leaf, chunk);
 793         for (i = 0; i < num_stripes; i++) {
 794                 map->stripes[i].physical =
 795                         btrfs_stripe_offset_nr(leaf, chunk, i);
 796                 devid = btrfs_stripe_devid_nr(leaf, chunk, i);
 797                 map->stripes[i].dev = btrfs_find_device(root, devid);
 798                 if (!map->stripes[i].dev) {
 799                         kfree(map);
 800                         return -EIO;
 801                 }
 802
 803         }
 804         ret = insert_existing_cache_extent(&map_tree->cache_tree, &map->ce);
 805         BUG_ON(ret);
 806
 807         return 0;
 808 }
 809
 810 static int fill_device_from_item(struct extent_buffer *leaf,
 811                                  struct btrfs_dev_item *dev_item,
 812                                  struct btrfs_device *device)
 813 {
 814         unsigned long ptr;
 815
 816         device->devid = btrfs_device_id(leaf, dev_item);
 817         device->total_bytes = btrfs_device_total_bytes(leaf, dev_item);
 818         device->bytes_used = btrfs_device_bytes_used(leaf, dev_item);
 819         device->type = btrfs_device_type(leaf, dev_item);
 820         device->io_align = btrfs_device_io_align(leaf, dev_item);
 821         device->io_width = btrfs_device_io_width(leaf, dev_item);
 822         device->sector_size = btrfs_device_sector_size(leaf, dev_item);
 823
 824         ptr = (unsigned long)btrfs_device_uuid(dev_item);
 825         read_extent_buffer(leaf, device->uuid, ptr, BTRFS_DEV_UUID_SIZE);
 826
 827         return 0;
 828 }
 829
 830 static int read_one_dev(struct btrfs_root *root,
 831                         struct extent_buffer *leaf,
 832                         struct btrfs_dev_item *dev_item)
 833 {
 834         struct btrfs_device *device;
 835         u64 devid;
 836         int ret = 0;
 837
 838         devid = btrfs_device_id(leaf, dev_item);
 839         device = btrfs_find_device(root, devid);
 840         if (!device) {
 841                 printk("warning devid %Lu not found already\n", devid);
 842                 device = kmalloc(sizeof(*device), GFP_NOFS);
 843                 if (!device)
 844                         return -ENOMEM;
 845                 list_add(&device->dev_list,
 846                          &root->fs_info->fs_devices->devices);
 847         }
 848
 849         fill_device_from_item(leaf, dev_item, device);
 850         device->dev_root = root->fs_info->dev_root;
 851         return ret;
 852 }
 853
 854 int btrfs_read_super_device(struct btrfs_root *root, struct extent_buffer *buf)
 855 {
 856         struct btrfs_dev_item *dev_item;
 857
 858         dev_item = (struct btrfs_dev_item *)offsetof(struct btrfs_super_block,
 859                                                      dev_item);
 860         return read_one_dev(root, buf, dev_item);
 861 }
 862
 863 int btrfs_read_sys_array(struct btrfs_root *root)
 864 {
 865         struct btrfs_super_block *super_copy = &root->fs_info->super_copy;
 866         struct extent_buffer *sb = root->fs_info->sb_buffer;
 867         struct btrfs_disk_key *disk_key;
 868         struct btrfs_chunk *chunk;
 869         struct btrfs_key key;
 870         u32 num_stripes;
 871         u32 array_size;
 872         u32 len = 0;
 873         u8 *ptr;
 874         unsigned long sb_ptr;
 875         u32 cur;
 876         int ret;
 877
 878         array_size = btrfs_super_sys_array_size(super_copy);
 879
 880         /*
 881          * we do this loop twice, once for the device items and
 882          * once for all of the chunks.  This way there are device
 883          * structs filled in for every chunk
 884          */
 885         ptr = super_copy->sys_chunk_array;
 886         sb_ptr = offsetof(struct btrfs_super_block, sys_chunk_array);
 887         cur = 0;
 888
 889         while (cur < array_size) {
 890                 disk_key = (struct btrfs_disk_key *)ptr;
 891                 btrfs_disk_key_to_cpu(&key, disk_key);
 892
 893                 len = sizeof(*disk_key);
 894                 ptr += len;
 895                 sb_ptr += len;
 896                 cur += len;
 897
 898                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
 899                         chunk = (struct btrfs_chunk *)sb_ptr;
 900                         ret = read_one_chunk(root, &key, sb, chunk);
 901                         BUG_ON(ret);
 902                         num_stripes = btrfs_chunk_num_stripes(sb, chunk);
 903                         len = btrfs_chunk_item_size(num_stripes);
 904                 } else {
 905                         BUG();
 906                 }
 907                 ptr += len;
 908                 sb_ptr += len;
 909                 cur += len;
 910         }
 911         return 0;
 912 }
 913
 914 int btrfs_read_chunk_tree(struct btrfs_root *root)
 915 {
 916         struct btrfs_path *path;
 917         struct extent_buffer *leaf;
 918         struct btrfs_key key;
 919         struct btrfs_key found_key;
 920         int ret;
 921         int slot;
 922
 923         root = root->fs_info->chunk_root;
 924
 925         path = btrfs_alloc_path();
 926         if (!path)
 927                 return -ENOMEM;
 928
 929         /* first we search for all of the device items, and then we
 930          * read in all of the chunk items.  This way we can create chunk
 931          * mappings that reference all of the devices that are afound
 932          */
 933         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 934         key.offset = 0;
 935         key.type = 0;
 936 again:
 937         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 938         while(1) {
 939                 leaf = path->nodes[0];
 940                 slot = path->slots[0];
 941                 if (slot >= btrfs_header_nritems(leaf)) {
 942                         ret = btrfs_next_leaf(root, path);
 943                         if (ret == 0)
 944                                 continue;
 945                         if (ret < 0)
 946                                 goto error;
 947                         break;
 948                 }
 949                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
 950                 if (key.objectid == BTRFS_DEV_ITEMS_OBJECTID) {
 951                         if (found_key.objectid != BTRFS_DEV_ITEMS_OBJECTID)
 952                                 break;
 953                         if (found_key.type == BTRFS_DEV_ITEM_KEY) {
 954                                 struct btrfs_dev_item *dev_item;
 955                                 dev_item = btrfs_item_ptr(leaf, slot,
 956                                                   struct btrfs_dev_item);
 957                                 ret = read_one_dev(root, leaf, dev_item);
 958                                 BUG_ON(ret);
 959                         }
 960                 } else if (found_key.type == BTRFS_CHUNK_ITEM_KEY) {
 961                         struct btrfs_chunk *chunk;
 962                         chunk = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
 963                         ret = read_one_chunk(root, &found_key, leaf, chunk);
 964                 }
 965                 path->slots[0]++;
 966         }
 967         if (key.objectid == BTRFS_DEV_ITEMS_OBJECTID) {
 968                 key.objectid = 0;
 969                 btrfs_release_path(root, path);
 970                 goto again;
 971         }
 972
 973         btrfs_free_path(path);
 974         ret = 0;
 975 error:
 976         return ret;
 977 }
 978