get rid of the extent_item type field
[platform/upstream/btrfs-progs.git] / extent-tree.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "kerncompat.h"
4 #include "radix-tree.h"
5 #include "ctree.h"
6 #include "disk-io.h"
7 #include "print-tree.h"
8 #include "transaction.h"
9
10 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
11                             *orig_root, u64 num_blocks, u64 search_start, u64
12                             search_end, struct btrfs_key *ins);
13 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
14                                  btrfs_root *extent_root);
15 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
16                        *extent_root);
17
18 /*
19  * pending extents are blocks that we're trying to allocate in the extent
20  * map while trying to grow the map because of other allocations.  To avoid
21  * recursing, they are tagged in the radix tree and cleaned up after
22  * other allocations are done.  The pending tag is also used in the same
23  * manner for deletes.
24  */
25 #define CTREE_EXTENT_PENDING_DEL 0
26
27 static int inc_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
28                          *root, u64 blocknr)
29 {
30         struct btrfs_path path;
31         int ret;
32         struct btrfs_key key;
33         struct btrfs_leaf *l;
34         struct btrfs_extent_item *item;
35         struct btrfs_key ins;
36         u32 refs;
37
38         find_free_extent(trans, root->fs_info->extent_root, 0, 0, (u64)-1,
39                          &ins);
40         btrfs_init_path(&path);
41         key.objectid = blocknr;
42         key.flags = 0;
43         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
44         key.offset = 1;
45         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
46                                 0, 1);
47         if (ret != 0)
48                 BUG();
49         BUG_ON(ret != 0);
50         l = &path.nodes[0]->leaf;
51         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
52         refs = btrfs_extent_refs(item);
53         btrfs_set_extent_refs(item, refs + 1);
54
55         BUG_ON(list_empty(&path.nodes[0]->dirty));
56         btrfs_release_path(root->fs_info->extent_root, &path);
57         finish_current_insert(trans, root->fs_info->extent_root);
58         run_pending(trans, root->fs_info->extent_root);
59         return 0;
60 }
61
62 static int lookup_block_ref(struct btrfs_trans_handle *trans, struct btrfs_root
63                             *root, u64 blocknr, u32 *refs)
64 {
65         struct btrfs_path path;
66         int ret;
67         struct btrfs_key key;
68         struct btrfs_leaf *l;
69         struct btrfs_extent_item *item;
70         btrfs_init_path(&path);
71         key.objectid = blocknr;
72         key.offset = 1;
73         key.flags = 0;
74         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
75         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, &path,
76                                 0, 0);
77         if (ret != 0)
78                 BUG();
79         l = &path.nodes[0]->leaf;
80         item = btrfs_item_ptr(l, path.slots[0], struct btrfs_extent_item);
81         *refs = btrfs_extent_refs(item);
82         btrfs_release_path(root->fs_info->extent_root, &path);
83         return 0;
84 }
85
86 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
87                   struct btrfs_buffer *buf)
88 {
89         u64 blocknr;
90         int i;
91
92         if (!root->ref_cows)
93                 return 0;
94         if (btrfs_is_leaf(&buf->node))
95                 return 0;
96
97         for (i = 0; i < btrfs_header_nritems(&buf->node.header); i++) {
98                 blocknr = btrfs_node_blockptr(&buf->node, i);
99                 inc_block_ref(trans, root, blocknr);
100         }
101         return 0;
102 }
103
104 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans, struct
105                                btrfs_root *root)
106 {
107         unsigned long gang[8];
108         u64 first = 0;
109         int ret;
110         int i;
111
112         while(1) {
113                 ret = radix_tree_gang_lookup(&root->fs_info->pinned_radix,
114                                              (void **)gang, 0,
115                                              ARRAY_SIZE(gang));
116                 if (!ret)
117                         break;
118                 if (!first)
119                         first = gang[0];
120                 for (i = 0; i < ret; i++) {
121                         radix_tree_delete(&root->fs_info->pinned_radix,
122                                           gang[i]);
123                 }
124         }
125         root->fs_info->last_insert.objectid = first;
126         root->fs_info->last_insert.offset = 0;
127         return 0;
128 }
129
130 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
131                                  btrfs_root *extent_root)
132 {
133         struct btrfs_key ins;
134         struct btrfs_extent_item extent_item;
135         int i;
136         int ret;
137         u64 super_blocks_used;
138         struct btrfs_fs_info *info = extent_root->fs_info;
139
140         btrfs_set_extent_refs(&extent_item, 1);
141         btrfs_set_extent_owner(&extent_item, extent_root->root_key.objectid);
142         ins.offset = 1;
143         ins.flags = 0;
144         btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
145
146         for (i = 0; i < extent_root->fs_info->current_insert.flags; i++) {
147                 ins.objectid = extent_root->fs_info->current_insert.objectid +
148                                 i;
149                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
150                 btrfs_set_super_blocks_used(info->disk_super,
151                                             super_blocks_used + 1);
152                 ret = btrfs_insert_item(trans, extent_root, &ins, &extent_item,
153                                         sizeof(extent_item));
154                 BUG_ON(ret);
155         }
156         extent_root->fs_info->current_insert.offset = 0;
157         return 0;
158 }
159
160 /*
161  * remove an extent from the root, returns 0 on success
162  */
163 static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
164                          *root, u64 blocknr, u64 num_blocks, int pin)
165 {
166         struct btrfs_path path;
167         struct btrfs_key key;
168         struct btrfs_fs_info *info = root->fs_info;
169         struct btrfs_root *extent_root = info->extent_root;
170         int ret;
171         struct btrfs_extent_item *ei;
172         struct btrfs_key ins;
173         u32 refs;
174
175         BUG_ON(pin && num_blocks != 1);
176         key.objectid = blocknr;
177         key.flags = 0;
178         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
179         key.offset = num_blocks;
180
181         find_free_extent(trans, root, 0, 0, (u64)-1, &ins);
182         btrfs_init_path(&path);
183         ret = btrfs_search_slot(trans, extent_root, &key, &path, -1, 1);
184         if (ret) {
185                 printf("failed to find %Lu\n", key.objectid);
186                 btrfs_print_tree(extent_root, extent_root->node);
187                 printf("failed to find %Lu\n", key.objectid);
188                 BUG();
189         }
190         ei = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
191                             struct btrfs_extent_item);
192         BUG_ON(ei->refs == 0);
193         refs = btrfs_extent_refs(ei) - 1;
194         btrfs_set_extent_refs(ei, refs);
195         if (refs == 0) {
196                 u64 super_blocks_used;
197                 if (pin) {
198                         int err;
199                         radix_tree_preload(GFP_KERNEL);
200                         err = radix_tree_insert(&info->pinned_radix,
201                                                 blocknr, (void *)blocknr);
202                         BUG_ON(err);
203                         radix_tree_preload_end();
204                 }
205                 super_blocks_used = btrfs_super_blocks_used(info->disk_super);
206                 btrfs_set_super_blocks_used(info->disk_super,
207                                             super_blocks_used - num_blocks);
208                 ret = btrfs_del_item(trans, extent_root, &path);
209                 if (!pin && extent_root->fs_info->last_insert.objectid >
210                     blocknr)
211                         extent_root->fs_info->last_insert.objectid = blocknr;
212                 if (ret)
213                         BUG();
214         }
215         btrfs_release_path(extent_root, &path);
216         finish_current_insert(trans, extent_root);
217         return ret;
218 }
219
220 /*
221  * find all the blocks marked as pending in the radix tree and remove
222  * them from the extent map
223  */
224 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
225                                btrfs_root *extent_root)
226 {
227         int ret;
228         struct btrfs_buffer *gang[4];
229         int i;
230
231         while(1) {
232                 ret = radix_tree_gang_lookup_tag(
233                                         &extent_root->fs_info->cache_radix,
234                                         (void **)gang, 0,
235                                         ARRAY_SIZE(gang),
236                                         CTREE_EXTENT_PENDING_DEL);
237                 if (!ret)
238                         break;
239                 for (i = 0; i < ret; i++) {
240                         ret = __free_extent(trans, extent_root,
241                                             gang[i]->blocknr, 1, 1);
242                         radix_tree_tag_clear(&extent_root->fs_info->cache_radix,
243                                              gang[i]->blocknr,
244                                              CTREE_EXTENT_PENDING_DEL);
245                         btrfs_block_release(extent_root, gang[i]);
246                 }
247         }
248         return 0;
249 }
250
251 static int run_pending(struct btrfs_trans_handle *trans, struct btrfs_root
252                        *extent_root)
253 {
254         while(radix_tree_tagged(&extent_root->fs_info->cache_radix,
255                                 CTREE_EXTENT_PENDING_DEL))
256                 del_pending_extents(trans, extent_root);
257         return 0;
258 }
259
260
261 /*
262  * remove an extent from the root, returns 0 on success
263  */
264 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
265                       *root, u64 blocknr, u64 num_blocks, int pin)
266 {
267         struct btrfs_root *extent_root = root->fs_info->extent_root;
268         struct btrfs_buffer *t;
269         int pending_ret;
270         int ret;
271
272         if (root == extent_root) {
273                 t = find_tree_block(root, blocknr);
274                 radix_tree_tag_set(&root->fs_info->cache_radix, blocknr,
275                                    CTREE_EXTENT_PENDING_DEL);
276                 return 0;
277         }
278         ret = __free_extent(trans, root, blocknr, num_blocks, pin);
279         pending_ret = run_pending(trans, root->fs_info->extent_root);
280         return ret ? ret : pending_ret;
281 }
282
283 /*
284  * walks the btree of allocated extents and find a hole of a given size.
285  * The key ins is changed to record the hole:
286  * ins->objectid == block start
287  * ins->flags = BTRFS_EXTENT_ITEM_KEY
288  * ins->offset == number of blocks
289  * Any available blocks before search_start are skipped.
290  */
291 static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
292                             *orig_root, u64 num_blocks, u64 search_start, u64
293                             search_end, struct btrfs_key *ins)
294 {
295         struct btrfs_path path;
296         struct btrfs_key key;
297         int ret;
298         u64 hole_size = 0;
299         int slot = 0;
300         u64 last_block;
301         u64 test_block;
302         int start_found;
303         struct btrfs_leaf *l;
304         struct btrfs_root * root = orig_root->fs_info->extent_root;
305         int total_needed = num_blocks;
306
307         total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
308         if (root->fs_info->last_insert.objectid > search_start)
309                 search_start = root->fs_info->last_insert.objectid;
310
311         ins->flags = 0;
312         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
313
314 check_failed:
315         btrfs_init_path(&path);
316         ins->objectid = search_start;
317         ins->offset = 0;
318         start_found = 0;
319         ret = btrfs_search_slot(trans, root, ins, &path, 0, 0);
320         if (ret < 0)
321                 goto error;
322
323         if (path.slots[0] > 0)
324                 path.slots[0]--;
325
326         while (1) {
327                 l = &path.nodes[0]->leaf;
328                 slot = path.slots[0];
329                 if (slot >= btrfs_header_nritems(&l->header)) {
330                         ret = btrfs_next_leaf(root, &path);
331                         if (ret == 0)
332                                 continue;
333                         if (ret < 0)
334                                 goto error;
335                         if (!start_found) {
336                                 ins->objectid = search_start;
337                                 ins->offset = (u64)-1;
338                                 start_found = 1;
339                                 goto check_pending;
340                         }
341                         ins->objectid = last_block > search_start ?
342                                         last_block : search_start;
343                         ins->offset = (u64)-1;
344                         goto check_pending;
345                 }
346                 btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
347                 if (key.objectid >= search_start) {
348                         if (start_found) {
349                                 if (last_block < search_start)
350                                         last_block = search_start;
351                                 hole_size = key.objectid - last_block;
352                                 if (hole_size > total_needed) {
353                                         ins->objectid = last_block;
354                                         ins->offset = hole_size;
355                                         goto check_pending;
356                                 }
357                         }
358                 }
359                 start_found = 1;
360                 last_block = key.objectid + key.offset;
361                 path.slots[0]++;
362         }
363         // FIXME -ENOSPC
364 check_pending:
365         /* we have to make sure we didn't find an extent that has already
366          * been allocated by the map tree or the original allocation
367          */
368         btrfs_release_path(root, &path);
369         BUG_ON(ins->objectid < search_start);
370         for (test_block = ins->objectid;
371              test_block < ins->objectid + total_needed; test_block++) {
372                 if (radix_tree_lookup(&root->fs_info->pinned_radix,
373                                       test_block)) {
374                         search_start = test_block + 1;
375                         goto check_failed;
376                 }
377         }
378         BUG_ON(root->fs_info->current_insert.offset);
379         root->fs_info->current_insert.offset = total_needed - num_blocks;
380         root->fs_info->current_insert.objectid = ins->objectid + num_blocks;
381         root->fs_info->current_insert.flags = 0;
382         root->fs_info->last_insert.objectid = ins->objectid;
383         ins->offset = num_blocks;
384         return 0;
385 error:
386         btrfs_release_path(root, &path);
387         return ret;
388 }
389
390 /*
391  * finds a free extent and does all the dirty work required for allocation
392  * returns the key for the extent through ins, and a tree buffer for
393  * the first block of the extent through buf.
394  *
395  * returns 0 if everything worked, non-zero otherwise.
396  */
397 static int alloc_extent(struct btrfs_trans_handle *trans, struct btrfs_root
398                         *root, u64 owner, u64 num_blocks,
399                         u64 search_start, u64
400                         search_end, struct btrfs_key *ins)
401 {
402         int ret;
403         int pending_ret;
404         u64 super_blocks_used;
405         struct btrfs_fs_info *info = root->fs_info;
406         struct btrfs_root *extent_root = info->extent_root;
407         struct btrfs_extent_item extent_item;
408
409         btrfs_set_extent_refs(&extent_item, 1);
410         btrfs_set_extent_owner(&extent_item, owner);
411
412         if (root == extent_root) {
413                 BUG_ON(extent_root->fs_info->current_insert.offset == 0);
414                 BUG_ON(num_blocks != 1);
415                 BUG_ON(extent_root->fs_info->current_insert.flags ==
416                        extent_root->fs_info->current_insert.offset);
417                 ins->offset = 1;
418                 ins->objectid = extent_root->fs_info->current_insert.objectid +
419                                 extent_root->fs_info->current_insert.flags++;
420                 return 0;
421         }
422         ret = find_free_extent(trans, root, num_blocks, search_start,
423                                search_end, ins);
424         if (ret)
425                 return ret;
426
427         super_blocks_used = btrfs_super_blocks_used(info->disk_super);
428         btrfs_set_super_blocks_used(info->disk_super, super_blocks_used +
429                                     num_blocks);
430         ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
431                                 sizeof(extent_item));
432
433         finish_current_insert(trans, extent_root);
434         pending_ret = run_pending(trans, extent_root);
435         if (ret)
436                 return ret;
437         if (pending_ret)
438                 return pending_ret;
439         return 0;
440 }
441
442 /*
443  * helper function to allocate a block for a given tree
444  * returns the tree buffer or NULL.
445  */
446 struct btrfs_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
447                                             struct btrfs_root *root)
448 {
449         struct btrfs_key ins;
450         int ret;
451         struct btrfs_buffer *buf;
452
453         ret = alloc_extent(trans, root, root->root_key.objectid,
454                            1, 0, (unsigned long)-1, &ins);
455         if (ret) {
456                 BUG();
457                 return NULL;
458         }
459         buf = find_tree_block(root, ins.objectid);
460         dirty_tree_block(trans, root, buf);
461         btrfs_set_header_generation(&buf->node.header,
462                                     root->root_key.offset + 1);
463         memcpy(buf->node.header.fsid, root->fs_info->disk_super->fsid,
464                sizeof(buf->node.header.fsid));
465         return buf;
466 }
467
468 /*
469  * helper function for drop_snapshot, this walks down the tree dropping ref
470  * counts as it goes.
471  */
472 static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
473                           *root, struct btrfs_path *path, int *level)
474 {
475         struct btrfs_buffer *next;
476         struct btrfs_buffer *cur;
477         u64 blocknr;
478         int ret;
479         u32 refs;
480
481         ret = lookup_block_ref(trans, root, path->nodes[*level]->blocknr,
482                                &refs);
483         BUG_ON(ret);
484         if (refs > 1)
485                 goto out;
486         /*
487          * walk down to the last node level and free all the leaves
488          */
489         while(*level > 0) {
490                 cur = path->nodes[*level];
491                 if (path->slots[*level] >=
492                     btrfs_header_nritems(&cur->node.header))
493                         break;
494                 blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
495                 ret = lookup_block_ref(trans, root, blocknr, &refs);
496                 if (refs != 1 || *level == 1) {
497                         path->slots[*level]++;
498                         ret = btrfs_free_extent(trans, root, blocknr, 1, 1);
499                         BUG_ON(ret);
500                         continue;
501                 }
502                 BUG_ON(ret);
503                 next = read_tree_block(root, blocknr);
504                 if (path->nodes[*level-1])
505                         btrfs_block_release(root, path->nodes[*level-1]);
506                 path->nodes[*level-1] = next;
507                 *level = btrfs_header_level(&next->node.header);
508                 path->slots[*level] = 0;
509         }
510 out:
511         ret = btrfs_free_extent(trans, root, path->nodes[*level]->blocknr, 1,
512                                 1);
513         btrfs_block_release(root, path->nodes[*level]);
514         path->nodes[*level] = NULL;
515         *level += 1;
516         BUG_ON(ret);
517         return 0;
518 }
519
520 /*
521  * helper for dropping snapshots.  This walks back up the tree in the path
522  * to find the first node higher up where we haven't yet gone through
523  * all the slots
524  */
525 static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
526                         *root, struct btrfs_path *path, int *level)
527 {
528         int i;
529         int slot;
530         int ret;
531         for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
532                 slot = path->slots[i];
533                 if (slot <
534                     btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
535                         path->slots[i]++;
536                         *level = i;
537                         return 0;
538                 } else {
539                         ret = btrfs_free_extent(trans, root,
540                                                 path->nodes[*level]->blocknr,
541                                                 1, 1);
542                         btrfs_block_release(root, path->nodes[*level]);
543                         path->nodes[*level] = NULL;
544                         *level = i + 1;
545                         BUG_ON(ret);
546                 }
547         }
548         return 1;
549 }
550
551 /*
552  * drop the reference count on the tree rooted at 'snap'.  This traverses
553  * the tree freeing any blocks that have a ref count of zero after being
554  * decremented.
555  */
556 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
557                         *root, struct btrfs_buffer *snap)
558 {
559         int ret = 0;
560         int wret;
561         int level;
562         struct btrfs_path path;
563         int i;
564         int orig_level;
565
566         btrfs_init_path(&path);
567
568         level = btrfs_header_level(&snap->node.header);
569         orig_level = level;
570         path.nodes[level] = snap;
571         path.slots[level] = 0;
572         while(1) {
573                 wret = walk_down_tree(trans, root, &path, &level);
574                 if (wret > 0)
575                         break;
576                 if (wret < 0)
577                         ret = wret;
578
579                 wret = walk_up_tree(trans, root, &path, &level);
580                 if (wret > 0)
581                         break;
582                 if (wret < 0)
583                         ret = wret;
584         }
585         for (i = 0; i <= orig_level; i++) {
586                 if (path.nodes[i]) {
587                         btrfs_block_release(root, path.nodes[i]);
588                 }
589         }
590         return ret;
591 }