Chris Mason | 2e635a2 | 2007-03-21 11:12:56 -0400 | [diff] [blame] | 1 | #include <linux/module.h> |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 2 | #include "ctree.h" |
| 3 | #include "disk-io.h" |
| 4 | #include "transaction.h" |
| 5 | |
| 6 | /* |
| 7 | * walks the btree of allocated inodes and find a hole. |
| 8 | */ |
| 9 | int btrfs_find_free_objectid(struct btrfs_trans_handle *trans, |
| 10 | struct btrfs_root *fs_root, |
| 11 | u64 dirid, u64 *objectid) |
| 12 | { |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 13 | struct btrfs_path *path; |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 14 | struct btrfs_key key; |
| 15 | int ret; |
| 16 | u64 hole_size = 0; |
| 17 | int slot = 0; |
Chris Mason | e20d96d | 2007-03-22 12:13:20 -0400 | [diff] [blame] | 18 | u64 last_ino = 0; |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 19 | int start_found; |
| 20 | struct btrfs_leaf *l; |
| 21 | struct btrfs_root *root = fs_root->fs_info->inode_root; |
| 22 | struct btrfs_key search_key; |
| 23 | u64 search_start = dirid; |
| 24 | |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 25 | path = btrfs_alloc_path(); |
| 26 | BUG_ON(!path); |
Chris Mason | b1a4d96 | 2007-04-04 15:27:52 -0400 | [diff] [blame^] | 27 | search_key.flags = 0; |
| 28 | btrfs_set_key_type(&search_key, BTRFS_INODE_MAP_ITEM_KEY); |
| 29 | |
| 30 | search_start = fs_root->fs_info->last_inode_alloc; |
| 31 | if (search_start == 0) { |
| 32 | struct btrfs_disk_key *last_key; |
| 33 | btrfs_init_path(path); |
| 34 | search_key.objectid = (u64)-1; |
| 35 | search_key.offset = (u64)-1; |
| 36 | ret = btrfs_search_slot(trans, root, &search_key, path, 0, 0); |
| 37 | if (ret < 0) |
| 38 | goto error; |
| 39 | BUG_ON(ret == 0); |
| 40 | if (path->slots[0] > 0) |
| 41 | path->slots[0]--; |
| 42 | l = btrfs_buffer_leaf(path->nodes[0]); |
| 43 | last_key = &l->items[path->slots[0]].key; |
| 44 | search_start = btrfs_disk_key_objectid(last_key); |
| 45 | } |
| 46 | search_start = max(search_start, BTRFS_FIRST_FREE_OBJECTID); |
| 47 | search_key.objectid = search_start; |
| 48 | search_key.offset = 0; |
| 49 | |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 50 | btrfs_init_path(path); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 51 | start_found = 0; |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 52 | ret = btrfs_search_slot(trans, root, &search_key, path, 0, 0); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 53 | if (ret < 0) |
| 54 | goto error; |
| 55 | |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 56 | if (path->slots[0] > 0) |
| 57 | path->slots[0]--; |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 58 | |
| 59 | while (1) { |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 60 | l = btrfs_buffer_leaf(path->nodes[0]); |
| 61 | slot = path->slots[0]; |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 62 | if (slot >= btrfs_header_nritems(&l->header)) { |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 63 | ret = btrfs_next_leaf(root, path); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 64 | if (ret == 0) |
| 65 | continue; |
| 66 | if (ret < 0) |
| 67 | goto error; |
| 68 | if (!start_found) { |
| 69 | *objectid = search_start; |
| 70 | start_found = 1; |
| 71 | goto found; |
| 72 | } |
| 73 | *objectid = last_ino > search_start ? |
| 74 | last_ino : search_start; |
| 75 | goto found; |
| 76 | } |
| 77 | btrfs_disk_key_to_cpu(&key, &l->items[slot].key); |
| 78 | if (key.objectid >= search_start) { |
| 79 | if (start_found) { |
| 80 | if (last_ino < search_start) |
| 81 | last_ino = search_start; |
| 82 | hole_size = key.objectid - last_ino; |
| 83 | if (hole_size > 0) { |
| 84 | *objectid = last_ino; |
| 85 | goto found; |
| 86 | } |
| 87 | } |
| 88 | } |
| 89 | start_found = 1; |
| 90 | last_ino = key.objectid + 1; |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 91 | path->slots[0]++; |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 92 | } |
| 93 | // FIXME -ENOSPC |
| 94 | found: |
| 95 | root->fs_info->last_inode_alloc = *objectid; |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 96 | btrfs_release_path(root, path); |
| 97 | btrfs_free_path(path); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 98 | BUG_ON(*objectid < search_start); |
| 99 | return 0; |
| 100 | error: |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 101 | btrfs_release_path(root, path); |
| 102 | btrfs_free_path(path); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 103 | return ret; |
| 104 | } |
| 105 | |
| 106 | int btrfs_insert_inode_map(struct btrfs_trans_handle *trans, |
| 107 | struct btrfs_root *fs_root, |
| 108 | u64 objectid, struct btrfs_key *location) |
| 109 | { |
| 110 | int ret = 0; |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 111 | struct btrfs_path *path; |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 112 | struct btrfs_inode_map_item *inode_item; |
| 113 | struct btrfs_key key; |
| 114 | struct btrfs_root *inode_root = fs_root->fs_info->inode_root; |
| 115 | |
| 116 | key.objectid = objectid; |
| 117 | key.flags = 0; |
| 118 | btrfs_set_key_type(&key, BTRFS_INODE_MAP_ITEM_KEY); |
| 119 | key.offset = 0; |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 120 | path = btrfs_alloc_path(); |
| 121 | BUG_ON(!path); |
| 122 | btrfs_init_path(path); |
| 123 | ret = btrfs_insert_empty_item(trans, inode_root, path, &key, |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 124 | sizeof(struct btrfs_inode_map_item)); |
| 125 | if (ret) |
| 126 | goto out; |
| 127 | |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 128 | inode_item = btrfs_item_ptr(btrfs_buffer_leaf(path->nodes[0]), |
| 129 | path->slots[0], struct btrfs_inode_map_item); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 130 | btrfs_cpu_key_to_disk(&inode_item->key, location); |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 131 | btrfs_mark_buffer_dirty(path->nodes[0]); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 132 | out: |
Chris Mason | 7cfcc17 | 2007-04-02 14:53:59 -0400 | [diff] [blame] | 133 | btrfs_release_path(inode_root, path); |
| 134 | btrfs_free_path(path); |
Chris Mason | 9f5fae2 | 2007-03-20 14:38:32 -0400 | [diff] [blame] | 135 | return ret; |
| 136 | } |
| 137 | |
| 138 | int btrfs_lookup_inode_map(struct btrfs_trans_handle *trans, |
| 139 | struct btrfs_root *fs_root, struct btrfs_path *path, |
| 140 | u64 objectid, int mod) |
| 141 | { |
| 142 | int ret; |
| 143 | struct btrfs_key key; |
| 144 | int ins_len = mod < 0 ? -1 : 0; |
| 145 | int cow = mod != 0; |
| 146 | struct btrfs_root *inode_root = fs_root->fs_info->inode_root; |
| 147 | |
| 148 | key.objectid = objectid; |
| 149 | key.flags = 0; |
| 150 | key.offset = 0; |
| 151 | btrfs_set_key_type(&key, BTRFS_INODE_MAP_ITEM_KEY); |
| 152 | ret = btrfs_search_slot(trans, inode_root, &key, path, ins_len, cow); |
| 153 | return ret; |
| 154 | } |
| 155 | |