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