GNU Linux-libre 4.9.308-gnu1
[releases.git] / fs / btrfs / free-space-tree.c
1 /*
2  * Copyright (C) 2015 Facebook.  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
19 #include <linux/kernel.h>
20 #include <linux/vmalloc.h>
21 #include "ctree.h"
22 #include "disk-io.h"
23 #include "locking.h"
24 #include "free-space-tree.h"
25 #include "transaction.h"
26
27 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
28                                         struct btrfs_fs_info *fs_info,
29                                         struct btrfs_block_group_cache *block_group,
30                                         struct btrfs_path *path);
31
32 void set_free_space_tree_thresholds(struct btrfs_block_group_cache *cache)
33 {
34         u32 bitmap_range;
35         size_t bitmap_size;
36         u64 num_bitmaps, total_bitmap_size;
37
38         /*
39          * We convert to bitmaps when the disk space required for using extents
40          * exceeds that required for using bitmaps.
41          */
42         bitmap_range = cache->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
43         num_bitmaps = div_u64(cache->key.offset + bitmap_range - 1,
44                               bitmap_range);
45         bitmap_size = sizeof(struct btrfs_item) + BTRFS_FREE_SPACE_BITMAP_SIZE;
46         total_bitmap_size = num_bitmaps * bitmap_size;
47         cache->bitmap_high_thresh = div_u64(total_bitmap_size,
48                                             sizeof(struct btrfs_item));
49
50         /*
51          * We allow for a small buffer between the high threshold and low
52          * threshold to avoid thrashing back and forth between the two formats.
53          */
54         if (cache->bitmap_high_thresh > 100)
55                 cache->bitmap_low_thresh = cache->bitmap_high_thresh - 100;
56         else
57                 cache->bitmap_low_thresh = 0;
58 }
59
60 static int add_new_free_space_info(struct btrfs_trans_handle *trans,
61                                    struct btrfs_fs_info *fs_info,
62                                    struct btrfs_block_group_cache *block_group,
63                                    struct btrfs_path *path)
64 {
65         struct btrfs_root *root = fs_info->free_space_root;
66         struct btrfs_free_space_info *info;
67         struct btrfs_key key;
68         struct extent_buffer *leaf;
69         int ret;
70
71         key.objectid = block_group->key.objectid;
72         key.type = BTRFS_FREE_SPACE_INFO_KEY;
73         key.offset = block_group->key.offset;
74
75         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*info));
76         if (ret)
77                 goto out;
78
79         leaf = path->nodes[0];
80         info = btrfs_item_ptr(leaf, path->slots[0],
81                               struct btrfs_free_space_info);
82         btrfs_set_free_space_extent_count(leaf, info, 0);
83         btrfs_set_free_space_flags(leaf, info, 0);
84         btrfs_mark_buffer_dirty(leaf);
85
86         ret = 0;
87 out:
88         btrfs_release_path(path);
89         return ret;
90 }
91
92 struct btrfs_free_space_info *
93 search_free_space_info(struct btrfs_trans_handle *trans,
94                        struct btrfs_fs_info *fs_info,
95                        struct btrfs_block_group_cache *block_group,
96                        struct btrfs_path *path, int cow)
97 {
98         struct btrfs_root *root = fs_info->free_space_root;
99         struct btrfs_key key;
100         int ret;
101
102         key.objectid = block_group->key.objectid;
103         key.type = BTRFS_FREE_SPACE_INFO_KEY;
104         key.offset = block_group->key.offset;
105
106         ret = btrfs_search_slot(trans, root, &key, path, 0, cow);
107         if (ret < 0)
108                 return ERR_PTR(ret);
109         if (ret != 0) {
110                 btrfs_warn(fs_info, "missing free space info for %llu",
111                            block_group->key.objectid);
112                 ASSERT(0);
113                 return ERR_PTR(-ENOENT);
114         }
115
116         return btrfs_item_ptr(path->nodes[0], path->slots[0],
117                               struct btrfs_free_space_info);
118 }
119
120 /*
121  * btrfs_search_slot() but we're looking for the greatest key less than the
122  * passed key.
123  */
124 static int btrfs_search_prev_slot(struct btrfs_trans_handle *trans,
125                                   struct btrfs_root *root,
126                                   struct btrfs_key *key, struct btrfs_path *p,
127                                   int ins_len, int cow)
128 {
129         int ret;
130
131         ret = btrfs_search_slot(trans, root, key, p, ins_len, cow);
132         if (ret < 0)
133                 return ret;
134
135         if (ret == 0) {
136                 ASSERT(0);
137                 return -EIO;
138         }
139
140         if (p->slots[0] == 0) {
141                 ASSERT(0);
142                 return -EIO;
143         }
144         p->slots[0]--;
145
146         return 0;
147 }
148
149 static inline u32 free_space_bitmap_size(u64 size, u32 sectorsize)
150 {
151         return DIV_ROUND_UP((u32)div_u64(size, sectorsize), BITS_PER_BYTE);
152 }
153
154 static u8 *alloc_bitmap(u32 bitmap_size)
155 {
156         void *mem;
157
158         /*
159          * The allocation size varies, observed numbers were < 4K up to 16K.
160          * Using vmalloc unconditionally would be too heavy, we'll try
161          * contiguous allocations first.
162          */
163         if  (bitmap_size <= PAGE_SIZE)
164                 return kzalloc(bitmap_size, GFP_NOFS);
165
166         mem = kzalloc(bitmap_size, GFP_NOFS | __GFP_NOWARN);
167         if (mem)
168                 return mem;
169
170         return __vmalloc(bitmap_size, GFP_NOFS | __GFP_HIGHMEM | __GFP_ZERO,
171                          PAGE_KERNEL);
172 }
173
174 int convert_free_space_to_bitmaps(struct btrfs_trans_handle *trans,
175                                   struct btrfs_fs_info *fs_info,
176                                   struct btrfs_block_group_cache *block_group,
177                                   struct btrfs_path *path)
178 {
179         struct btrfs_root *root = fs_info->free_space_root;
180         struct btrfs_free_space_info *info;
181         struct btrfs_key key, found_key;
182         struct extent_buffer *leaf;
183         u8 *bitmap, *bitmap_cursor;
184         u64 start, end;
185         u64 bitmap_range, i;
186         u32 bitmap_size, flags, expected_extent_count;
187         u32 extent_count = 0;
188         int done = 0, nr;
189         int ret;
190
191         bitmap_size = free_space_bitmap_size(block_group->key.offset,
192                                              block_group->sectorsize);
193         bitmap = alloc_bitmap(bitmap_size);
194         if (!bitmap) {
195                 ret = -ENOMEM;
196                 goto out;
197         }
198
199         start = block_group->key.objectid;
200         end = block_group->key.objectid + block_group->key.offset;
201
202         key.objectid = end - 1;
203         key.type = (u8)-1;
204         key.offset = (u64)-1;
205
206         while (!done) {
207                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
208                 if (ret)
209                         goto out;
210
211                 leaf = path->nodes[0];
212                 nr = 0;
213                 path->slots[0]++;
214                 while (path->slots[0] > 0) {
215                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
216
217                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
218                                 ASSERT(found_key.objectid == block_group->key.objectid);
219                                 ASSERT(found_key.offset == block_group->key.offset);
220                                 done = 1;
221                                 break;
222                         } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
223                                 u64 first, last;
224
225                                 ASSERT(found_key.objectid >= start);
226                                 ASSERT(found_key.objectid < end);
227                                 ASSERT(found_key.objectid + found_key.offset <= end);
228
229                                 first = div_u64(found_key.objectid - start,
230                                                 block_group->sectorsize);
231                                 last = div_u64(found_key.objectid + found_key.offset - start,
232                                                block_group->sectorsize);
233                                 le_bitmap_set(bitmap, first, last - first);
234
235                                 extent_count++;
236                                 nr++;
237                                 path->slots[0]--;
238                         } else {
239                                 ASSERT(0);
240                         }
241                 }
242
243                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
244                 if (ret)
245                         goto out;
246                 btrfs_release_path(path);
247         }
248
249         info = search_free_space_info(trans, fs_info, block_group, path, 1);
250         if (IS_ERR(info)) {
251                 ret = PTR_ERR(info);
252                 goto out;
253         }
254         leaf = path->nodes[0];
255         flags = btrfs_free_space_flags(leaf, info);
256         flags |= BTRFS_FREE_SPACE_USING_BITMAPS;
257         btrfs_set_free_space_flags(leaf, info, flags);
258         expected_extent_count = btrfs_free_space_extent_count(leaf, info);
259         btrfs_mark_buffer_dirty(leaf);
260         btrfs_release_path(path);
261
262         if (extent_count != expected_extent_count) {
263                 btrfs_err(fs_info,
264                           "incorrect extent count for %llu; counted %u, expected %u",
265                           block_group->key.objectid, extent_count,
266                           expected_extent_count);
267                 ASSERT(0);
268                 ret = -EIO;
269                 goto out;
270         }
271
272         bitmap_cursor = bitmap;
273         bitmap_range = block_group->sectorsize * BTRFS_FREE_SPACE_BITMAP_BITS;
274         i = start;
275         while (i < end) {
276                 unsigned long ptr;
277                 u64 extent_size;
278                 u32 data_size;
279
280                 extent_size = min(end - i, bitmap_range);
281                 data_size = free_space_bitmap_size(extent_size,
282                                                    block_group->sectorsize);
283
284                 key.objectid = i;
285                 key.type = BTRFS_FREE_SPACE_BITMAP_KEY;
286                 key.offset = extent_size;
287
288                 ret = btrfs_insert_empty_item(trans, root, path, &key,
289                                               data_size);
290                 if (ret)
291                         goto out;
292
293                 leaf = path->nodes[0];
294                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
295                 write_extent_buffer(leaf, bitmap_cursor, ptr,
296                                     data_size);
297                 btrfs_mark_buffer_dirty(leaf);
298                 btrfs_release_path(path);
299
300                 i += extent_size;
301                 bitmap_cursor += data_size;
302         }
303
304         ret = 0;
305 out:
306         kvfree(bitmap);
307         if (ret)
308                 btrfs_abort_transaction(trans, ret);
309         return ret;
310 }
311
312 int convert_free_space_to_extents(struct btrfs_trans_handle *trans,
313                                   struct btrfs_fs_info *fs_info,
314                                   struct btrfs_block_group_cache *block_group,
315                                   struct btrfs_path *path)
316 {
317         struct btrfs_root *root = fs_info->free_space_root;
318         struct btrfs_free_space_info *info;
319         struct btrfs_key key, found_key;
320         struct extent_buffer *leaf;
321         u8 *bitmap;
322         u64 start, end;
323         /* Initialize to silence GCC. */
324         u64 extent_start = 0;
325         u64 offset;
326         u32 bitmap_size, flags, expected_extent_count;
327         int prev_bit = 0, bit, bitnr;
328         u32 extent_count = 0;
329         int done = 0, nr;
330         int ret;
331
332         bitmap_size = free_space_bitmap_size(block_group->key.offset,
333                                              block_group->sectorsize);
334         bitmap = alloc_bitmap(bitmap_size);
335         if (!bitmap) {
336                 ret = -ENOMEM;
337                 goto out;
338         }
339
340         start = block_group->key.objectid;
341         end = block_group->key.objectid + block_group->key.offset;
342
343         key.objectid = end - 1;
344         key.type = (u8)-1;
345         key.offset = (u64)-1;
346
347         while (!done) {
348                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
349                 if (ret)
350                         goto out;
351
352                 leaf = path->nodes[0];
353                 nr = 0;
354                 path->slots[0]++;
355                 while (path->slots[0] > 0) {
356                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
357
358                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
359                                 ASSERT(found_key.objectid == block_group->key.objectid);
360                                 ASSERT(found_key.offset == block_group->key.offset);
361                                 done = 1;
362                                 break;
363                         } else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
364                                 unsigned long ptr;
365                                 u8 *bitmap_cursor;
366                                 u32 bitmap_pos, data_size;
367
368                                 ASSERT(found_key.objectid >= start);
369                                 ASSERT(found_key.objectid < end);
370                                 ASSERT(found_key.objectid + found_key.offset <= end);
371
372                                 bitmap_pos = div_u64(found_key.objectid - start,
373                                                      block_group->sectorsize *
374                                                      BITS_PER_BYTE);
375                                 bitmap_cursor = bitmap + bitmap_pos;
376                                 data_size = free_space_bitmap_size(found_key.offset,
377                                                                    block_group->sectorsize);
378
379                                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0] - 1);
380                                 read_extent_buffer(leaf, bitmap_cursor, ptr,
381                                                    data_size);
382
383                                 nr++;
384                                 path->slots[0]--;
385                         } else {
386                                 ASSERT(0);
387                         }
388                 }
389
390                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
391                 if (ret)
392                         goto out;
393                 btrfs_release_path(path);
394         }
395
396         info = search_free_space_info(trans, fs_info, block_group, path, 1);
397         if (IS_ERR(info)) {
398                 ret = PTR_ERR(info);
399                 goto out;
400         }
401         leaf = path->nodes[0];
402         flags = btrfs_free_space_flags(leaf, info);
403         flags &= ~BTRFS_FREE_SPACE_USING_BITMAPS;
404         btrfs_set_free_space_flags(leaf, info, flags);
405         expected_extent_count = btrfs_free_space_extent_count(leaf, info);
406         btrfs_mark_buffer_dirty(leaf);
407         btrfs_release_path(path);
408
409         offset = start;
410         bitnr = 0;
411         while (offset < end) {
412                 bit = !!le_test_bit(bitnr, bitmap);
413                 if (prev_bit == 0 && bit == 1) {
414                         extent_start = offset;
415                 } else if (prev_bit == 1 && bit == 0) {
416                         key.objectid = extent_start;
417                         key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
418                         key.offset = offset - extent_start;
419
420                         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
421                         if (ret)
422                                 goto out;
423                         btrfs_release_path(path);
424
425                         extent_count++;
426                 }
427                 prev_bit = bit;
428                 offset += block_group->sectorsize;
429                 bitnr++;
430         }
431         if (prev_bit == 1) {
432                 key.objectid = extent_start;
433                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
434                 key.offset = end - extent_start;
435
436                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
437                 if (ret)
438                         goto out;
439                 btrfs_release_path(path);
440
441                 extent_count++;
442         }
443
444         if (extent_count != expected_extent_count) {
445                 btrfs_err(fs_info,
446                           "incorrect extent count for %llu; counted %u, expected %u",
447                           block_group->key.objectid, extent_count,
448                           expected_extent_count);
449                 ASSERT(0);
450                 ret = -EIO;
451                 goto out;
452         }
453
454         ret = 0;
455 out:
456         kvfree(bitmap);
457         if (ret)
458                 btrfs_abort_transaction(trans, ret);
459         return ret;
460 }
461
462 static int update_free_space_extent_count(struct btrfs_trans_handle *trans,
463                                           struct btrfs_fs_info *fs_info,
464                                           struct btrfs_block_group_cache *block_group,
465                                           struct btrfs_path *path,
466                                           int new_extents)
467 {
468         struct btrfs_free_space_info *info;
469         u32 flags;
470         u32 extent_count;
471         int ret = 0;
472
473         if (new_extents == 0)
474                 return 0;
475
476         info = search_free_space_info(trans, fs_info, block_group, path, 1);
477         if (IS_ERR(info)) {
478                 ret = PTR_ERR(info);
479                 goto out;
480         }
481         flags = btrfs_free_space_flags(path->nodes[0], info);
482         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
483
484         extent_count += new_extents;
485         btrfs_set_free_space_extent_count(path->nodes[0], info, extent_count);
486         btrfs_mark_buffer_dirty(path->nodes[0]);
487         btrfs_release_path(path);
488
489         if (!(flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
490             extent_count > block_group->bitmap_high_thresh) {
491                 ret = convert_free_space_to_bitmaps(trans, fs_info, block_group,
492                                                     path);
493         } else if ((flags & BTRFS_FREE_SPACE_USING_BITMAPS) &&
494                    extent_count < block_group->bitmap_low_thresh) {
495                 ret = convert_free_space_to_extents(trans, fs_info, block_group,
496                                                     path);
497         }
498
499 out:
500         return ret;
501 }
502
503 int free_space_test_bit(struct btrfs_block_group_cache *block_group,
504                         struct btrfs_path *path, u64 offset)
505 {
506         struct extent_buffer *leaf;
507         struct btrfs_key key;
508         u64 found_start, found_end;
509         unsigned long ptr, i;
510
511         leaf = path->nodes[0];
512         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
513         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
514
515         found_start = key.objectid;
516         found_end = key.objectid + key.offset;
517         ASSERT(offset >= found_start && offset < found_end);
518
519         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
520         i = div_u64(offset - found_start, block_group->sectorsize);
521         return !!extent_buffer_test_bit(leaf, ptr, i);
522 }
523
524 static void free_space_set_bits(struct btrfs_block_group_cache *block_group,
525                                 struct btrfs_path *path, u64 *start, u64 *size,
526                                 int bit)
527 {
528         struct extent_buffer *leaf;
529         struct btrfs_key key;
530         u64 end = *start + *size;
531         u64 found_start, found_end;
532         unsigned long ptr, first, last;
533
534         leaf = path->nodes[0];
535         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
536         ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
537
538         found_start = key.objectid;
539         found_end = key.objectid + key.offset;
540         ASSERT(*start >= found_start && *start < found_end);
541         ASSERT(end > found_start);
542
543         if (end > found_end)
544                 end = found_end;
545
546         ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
547         first = div_u64(*start - found_start, block_group->sectorsize);
548         last = div_u64(end - found_start, block_group->sectorsize);
549         if (bit)
550                 extent_buffer_bitmap_set(leaf, ptr, first, last - first);
551         else
552                 extent_buffer_bitmap_clear(leaf, ptr, first, last - first);
553         btrfs_mark_buffer_dirty(leaf);
554
555         *size -= end - *start;
556         *start = end;
557 }
558
559 /*
560  * We can't use btrfs_next_item() in modify_free_space_bitmap() because
561  * btrfs_next_leaf() doesn't get the path for writing. We can forgo the fancy
562  * tree walking in btrfs_next_leaf() anyways because we know exactly what we're
563  * looking for.
564  */
565 static int free_space_next_bitmap(struct btrfs_trans_handle *trans,
566                                   struct btrfs_root *root, struct btrfs_path *p)
567 {
568         struct btrfs_key key;
569
570         if (p->slots[0] + 1 < btrfs_header_nritems(p->nodes[0])) {
571                 p->slots[0]++;
572                 return 0;
573         }
574
575         btrfs_item_key_to_cpu(p->nodes[0], &key, p->slots[0]);
576         btrfs_release_path(p);
577
578         key.objectid += key.offset;
579         key.type = (u8)-1;
580         key.offset = (u64)-1;
581
582         return btrfs_search_prev_slot(trans, root, &key, p, 0, 1);
583 }
584
585 /*
586  * If remove is 1, then we are removing free space, thus clearing bits in the
587  * bitmap. If remove is 0, then we are adding free space, thus setting bits in
588  * the bitmap.
589  */
590 static int modify_free_space_bitmap(struct btrfs_trans_handle *trans,
591                                     struct btrfs_fs_info *fs_info,
592                                     struct btrfs_block_group_cache *block_group,
593                                     struct btrfs_path *path,
594                                     u64 start, u64 size, int remove)
595 {
596         struct btrfs_root *root = fs_info->free_space_root;
597         struct btrfs_key key;
598         u64 end = start + size;
599         u64 cur_start, cur_size;
600         int prev_bit, next_bit;
601         int new_extents;
602         int ret;
603
604         /*
605          * Read the bit for the block immediately before the extent of space if
606          * that block is within the block group.
607          */
608         if (start > block_group->key.objectid) {
609                 u64 prev_block = start - block_group->sectorsize;
610
611                 key.objectid = prev_block;
612                 key.type = (u8)-1;
613                 key.offset = (u64)-1;
614
615                 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
616                 if (ret)
617                         goto out;
618
619                 prev_bit = free_space_test_bit(block_group, path, prev_block);
620
621                 /* The previous block may have been in the previous bitmap. */
622                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
623                 if (start >= key.objectid + key.offset) {
624                         ret = free_space_next_bitmap(trans, root, path);
625                         if (ret)
626                                 goto out;
627                 }
628         } else {
629                 key.objectid = start;
630                 key.type = (u8)-1;
631                 key.offset = (u64)-1;
632
633                 ret = btrfs_search_prev_slot(trans, root, &key, path, 0, 1);
634                 if (ret)
635                         goto out;
636
637                 prev_bit = -1;
638         }
639
640         /*
641          * Iterate over all of the bitmaps overlapped by the extent of space,
642          * clearing/setting bits as required.
643          */
644         cur_start = start;
645         cur_size = size;
646         while (1) {
647                 free_space_set_bits(block_group, path, &cur_start, &cur_size,
648                                     !remove);
649                 if (cur_size == 0)
650                         break;
651                 ret = free_space_next_bitmap(trans, root, path);
652                 if (ret)
653                         goto out;
654         }
655
656         /*
657          * Read the bit for the block immediately after the extent of space if
658          * that block is within the block group.
659          */
660         if (end < block_group->key.objectid + block_group->key.offset) {
661                 /* The next block may be in the next bitmap. */
662                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
663                 if (end >= key.objectid + key.offset) {
664                         ret = free_space_next_bitmap(trans, root, path);
665                         if (ret)
666                                 goto out;
667                 }
668
669                 next_bit = free_space_test_bit(block_group, path, end);
670         } else {
671                 next_bit = -1;
672         }
673
674         if (remove) {
675                 new_extents = -1;
676                 if (prev_bit == 1) {
677                         /* Leftover on the left. */
678                         new_extents++;
679                 }
680                 if (next_bit == 1) {
681                         /* Leftover on the right. */
682                         new_extents++;
683                 }
684         } else {
685                 new_extents = 1;
686                 if (prev_bit == 1) {
687                         /* Merging with neighbor on the left. */
688                         new_extents--;
689                 }
690                 if (next_bit == 1) {
691                         /* Merging with neighbor on the right. */
692                         new_extents--;
693                 }
694         }
695
696         btrfs_release_path(path);
697         ret = update_free_space_extent_count(trans, fs_info, block_group, path,
698                                              new_extents);
699
700 out:
701         return ret;
702 }
703
704 static int remove_free_space_extent(struct btrfs_trans_handle *trans,
705                                     struct btrfs_fs_info *fs_info,
706                                     struct btrfs_block_group_cache *block_group,
707                                     struct btrfs_path *path,
708                                     u64 start, u64 size)
709 {
710         struct btrfs_root *root = fs_info->free_space_root;
711         struct btrfs_key key;
712         u64 found_start, found_end;
713         u64 end = start + size;
714         int new_extents = -1;
715         int ret;
716
717         key.objectid = start;
718         key.type = (u8)-1;
719         key.offset = (u64)-1;
720
721         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
722         if (ret)
723                 goto out;
724
725         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
726
727         ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
728
729         found_start = key.objectid;
730         found_end = key.objectid + key.offset;
731         ASSERT(start >= found_start && end <= found_end);
732
733         /*
734          * Okay, now that we've found the free space extent which contains the
735          * free space that we are removing, there are four cases:
736          *
737          * 1. We're using the whole extent: delete the key we found and
738          * decrement the free space extent count.
739          * 2. We are using part of the extent starting at the beginning: delete
740          * the key we found and insert a new key representing the leftover at
741          * the end. There is no net change in the number of extents.
742          * 3. We are using part of the extent ending at the end: delete the key
743          * we found and insert a new key representing the leftover at the
744          * beginning. There is no net change in the number of extents.
745          * 4. We are using part of the extent in the middle: delete the key we
746          * found and insert two new keys representing the leftovers on each
747          * side. Where we used to have one extent, we now have two, so increment
748          * the extent count. We may need to convert the block group to bitmaps
749          * as a result.
750          */
751
752         /* Delete the existing key (cases 1-4). */
753         ret = btrfs_del_item(trans, root, path);
754         if (ret)
755                 goto out;
756
757         /* Add a key for leftovers at the beginning (cases 3 and 4). */
758         if (start > found_start) {
759                 key.objectid = found_start;
760                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
761                 key.offset = start - found_start;
762
763                 btrfs_release_path(path);
764                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
765                 if (ret)
766                         goto out;
767                 new_extents++;
768         }
769
770         /* Add a key for leftovers at the end (cases 2 and 4). */
771         if (end < found_end) {
772                 key.objectid = end;
773                 key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
774                 key.offset = found_end - end;
775
776                 btrfs_release_path(path);
777                 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
778                 if (ret)
779                         goto out;
780                 new_extents++;
781         }
782
783         btrfs_release_path(path);
784         ret = update_free_space_extent_count(trans, fs_info, block_group, path,
785                                              new_extents);
786
787 out:
788         return ret;
789 }
790
791 int __remove_from_free_space_tree(struct btrfs_trans_handle *trans,
792                                   struct btrfs_fs_info *fs_info,
793                                   struct btrfs_block_group_cache *block_group,
794                                   struct btrfs_path *path, u64 start, u64 size)
795 {
796         struct btrfs_free_space_info *info;
797         u32 flags;
798         int ret;
799
800         if (block_group->needs_free_space) {
801                 ret = __add_block_group_free_space(trans, fs_info, block_group,
802                                                    path);
803                 if (ret)
804                         return ret;
805         }
806
807         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
808         if (IS_ERR(info))
809                 return PTR_ERR(info);
810         flags = btrfs_free_space_flags(path->nodes[0], info);
811         btrfs_release_path(path);
812
813         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
814                 return modify_free_space_bitmap(trans, fs_info, block_group,
815                                                 path, start, size, 1);
816         } else {
817                 return remove_free_space_extent(trans, fs_info, block_group,
818                                                 path, start, size);
819         }
820 }
821
822 int remove_from_free_space_tree(struct btrfs_trans_handle *trans,
823                                 struct btrfs_fs_info *fs_info,
824                                 u64 start, u64 size)
825 {
826         struct btrfs_block_group_cache *block_group;
827         struct btrfs_path *path;
828         int ret;
829
830         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
831                 return 0;
832
833         path = btrfs_alloc_path();
834         if (!path) {
835                 ret = -ENOMEM;
836                 goto out;
837         }
838
839         block_group = btrfs_lookup_block_group(fs_info, start);
840         if (!block_group) {
841                 ASSERT(0);
842                 ret = -ENOENT;
843                 goto out;
844         }
845
846         mutex_lock(&block_group->free_space_lock);
847         ret = __remove_from_free_space_tree(trans, fs_info, block_group, path,
848                                             start, size);
849         mutex_unlock(&block_group->free_space_lock);
850
851         btrfs_put_block_group(block_group);
852 out:
853         btrfs_free_path(path);
854         if (ret)
855                 btrfs_abort_transaction(trans, ret);
856         return ret;
857 }
858
859 static int add_free_space_extent(struct btrfs_trans_handle *trans,
860                                  struct btrfs_fs_info *fs_info,
861                                  struct btrfs_block_group_cache *block_group,
862                                  struct btrfs_path *path,
863                                  u64 start, u64 size)
864 {
865         struct btrfs_root *root = fs_info->free_space_root;
866         struct btrfs_key key, new_key;
867         u64 found_start, found_end;
868         u64 end = start + size;
869         int new_extents = 1;
870         int ret;
871
872         /*
873          * We are adding a new extent of free space, but we need to merge
874          * extents. There are four cases here:
875          *
876          * 1. The new extent does not have any immediate neighbors to merge
877          * with: add the new key and increment the free space extent count. We
878          * may need to convert the block group to bitmaps as a result.
879          * 2. The new extent has an immediate neighbor before it: remove the
880          * previous key and insert a new key combining both of them. There is no
881          * net change in the number of extents.
882          * 3. The new extent has an immediate neighbor after it: remove the next
883          * key and insert a new key combining both of them. There is no net
884          * change in the number of extents.
885          * 4. The new extent has immediate neighbors on both sides: remove both
886          * of the keys and insert a new key combining all of them. Where we used
887          * to have two extents, we now have one, so decrement the extent count.
888          */
889
890         new_key.objectid = start;
891         new_key.type = BTRFS_FREE_SPACE_EXTENT_KEY;
892         new_key.offset = size;
893
894         /* Search for a neighbor on the left. */
895         if (start == block_group->key.objectid)
896                 goto right;
897         key.objectid = start - 1;
898         key.type = (u8)-1;
899         key.offset = (u64)-1;
900
901         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
902         if (ret)
903                 goto out;
904
905         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
906
907         if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
908                 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
909                 btrfs_release_path(path);
910                 goto right;
911         }
912
913         found_start = key.objectid;
914         found_end = key.objectid + key.offset;
915         ASSERT(found_start >= block_group->key.objectid &&
916                found_end > block_group->key.objectid);
917         ASSERT(found_start < start && found_end <= start);
918
919         /*
920          * Delete the neighbor on the left and absorb it into the new key (cases
921          * 2 and 4).
922          */
923         if (found_end == start) {
924                 ret = btrfs_del_item(trans, root, path);
925                 if (ret)
926                         goto out;
927                 new_key.objectid = found_start;
928                 new_key.offset += key.offset;
929                 new_extents--;
930         }
931         btrfs_release_path(path);
932
933 right:
934         /* Search for a neighbor on the right. */
935         if (end == block_group->key.objectid + block_group->key.offset)
936                 goto insert;
937         key.objectid = end;
938         key.type = (u8)-1;
939         key.offset = (u64)-1;
940
941         ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
942         if (ret)
943                 goto out;
944
945         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
946
947         if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY) {
948                 ASSERT(key.type == BTRFS_FREE_SPACE_INFO_KEY);
949                 btrfs_release_path(path);
950                 goto insert;
951         }
952
953         found_start = key.objectid;
954         found_end = key.objectid + key.offset;
955         ASSERT(found_start >= block_group->key.objectid &&
956                found_end > block_group->key.objectid);
957         ASSERT((found_start < start && found_end <= start) ||
958                (found_start >= end && found_end > end));
959
960         /*
961          * Delete the neighbor on the right and absorb it into the new key
962          * (cases 3 and 4).
963          */
964         if (found_start == end) {
965                 ret = btrfs_del_item(trans, root, path);
966                 if (ret)
967                         goto out;
968                 new_key.offset += key.offset;
969                 new_extents--;
970         }
971         btrfs_release_path(path);
972
973 insert:
974         /* Insert the new key (cases 1-4). */
975         ret = btrfs_insert_empty_item(trans, root, path, &new_key, 0);
976         if (ret)
977                 goto out;
978
979         btrfs_release_path(path);
980         ret = update_free_space_extent_count(trans, fs_info, block_group, path,
981                                              new_extents);
982
983 out:
984         return ret;
985 }
986
987 int __add_to_free_space_tree(struct btrfs_trans_handle *trans,
988                              struct btrfs_fs_info *fs_info,
989                              struct btrfs_block_group_cache *block_group,
990                              struct btrfs_path *path, u64 start, u64 size)
991 {
992         struct btrfs_free_space_info *info;
993         u32 flags;
994         int ret;
995
996         if (block_group->needs_free_space) {
997                 ret = __add_block_group_free_space(trans, fs_info, block_group,
998                                                    path);
999                 if (ret)
1000                         return ret;
1001         }
1002
1003         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
1004         if (IS_ERR(info))
1005                 return PTR_ERR(info);
1006         flags = btrfs_free_space_flags(path->nodes[0], info);
1007         btrfs_release_path(path);
1008
1009         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
1010                 return modify_free_space_bitmap(trans, fs_info, block_group,
1011                                                 path, start, size, 0);
1012         } else {
1013                 return add_free_space_extent(trans, fs_info, block_group, path,
1014                                              start, size);
1015         }
1016 }
1017
1018 int add_to_free_space_tree(struct btrfs_trans_handle *trans,
1019                            struct btrfs_fs_info *fs_info,
1020                            u64 start, u64 size)
1021 {
1022         struct btrfs_block_group_cache *block_group;
1023         struct btrfs_path *path;
1024         int ret;
1025
1026         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1027                 return 0;
1028
1029         path = btrfs_alloc_path();
1030         if (!path) {
1031                 ret = -ENOMEM;
1032                 goto out;
1033         }
1034
1035         block_group = btrfs_lookup_block_group(fs_info, start);
1036         if (!block_group) {
1037                 ASSERT(0);
1038                 ret = -ENOENT;
1039                 goto out;
1040         }
1041
1042         mutex_lock(&block_group->free_space_lock);
1043         ret = __add_to_free_space_tree(trans, fs_info, block_group, path, start,
1044                                        size);
1045         mutex_unlock(&block_group->free_space_lock);
1046
1047         btrfs_put_block_group(block_group);
1048 out:
1049         btrfs_free_path(path);
1050         if (ret)
1051                 btrfs_abort_transaction(trans, ret);
1052         return ret;
1053 }
1054
1055 /*
1056  * Populate the free space tree by walking the extent tree. Operations on the
1057  * extent tree that happen as a result of writes to the free space tree will go
1058  * through the normal add/remove hooks.
1059  */
1060 static int populate_free_space_tree(struct btrfs_trans_handle *trans,
1061                                     struct btrfs_fs_info *fs_info,
1062                                     struct btrfs_block_group_cache *block_group)
1063 {
1064         struct btrfs_root *extent_root = fs_info->extent_root;
1065         struct btrfs_path *path, *path2;
1066         struct btrfs_key key;
1067         u64 start, end;
1068         int ret;
1069
1070         path = btrfs_alloc_path();
1071         if (!path)
1072                 return -ENOMEM;
1073         path->reada = 1;
1074
1075         path2 = btrfs_alloc_path();
1076         if (!path2) {
1077                 btrfs_free_path(path);
1078                 return -ENOMEM;
1079         }
1080
1081         ret = add_new_free_space_info(trans, fs_info, block_group, path2);
1082         if (ret)
1083                 goto out;
1084
1085         mutex_lock(&block_group->free_space_lock);
1086
1087         /*
1088          * Iterate through all of the extent and metadata items in this block
1089          * group, adding the free space between them and the free space at the
1090          * end. Note that EXTENT_ITEM and METADATA_ITEM are less than
1091          * BLOCK_GROUP_ITEM, so an extent may precede the block group that it's
1092          * contained in.
1093          */
1094         key.objectid = block_group->key.objectid;
1095         key.type = BTRFS_EXTENT_ITEM_KEY;
1096         key.offset = 0;
1097
1098         ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
1099         if (ret < 0)
1100                 goto out_locked;
1101         ASSERT(ret == 0);
1102
1103         start = block_group->key.objectid;
1104         end = block_group->key.objectid + block_group->key.offset;
1105         while (1) {
1106                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1107
1108                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1109                     key.type == BTRFS_METADATA_ITEM_KEY) {
1110                         if (key.objectid >= end)
1111                                 break;
1112
1113                         if (start < key.objectid) {
1114                                 ret = __add_to_free_space_tree(trans, fs_info,
1115                                                                block_group,
1116                                                                path2, start,
1117                                                                key.objectid -
1118                                                                start);
1119                                 if (ret)
1120                                         goto out_locked;
1121                         }
1122                         start = key.objectid;
1123                         if (key.type == BTRFS_METADATA_ITEM_KEY)
1124                                 start += fs_info->tree_root->nodesize;
1125                         else
1126                                 start += key.offset;
1127                 } else if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1128                         if (key.objectid != block_group->key.objectid)
1129                                 break;
1130                 }
1131
1132                 ret = btrfs_next_item(extent_root, path);
1133                 if (ret < 0)
1134                         goto out_locked;
1135                 if (ret)
1136                         break;
1137         }
1138         if (start < end) {
1139                 ret = __add_to_free_space_tree(trans, fs_info, block_group,
1140                                                path2, start, end - start);
1141                 if (ret)
1142                         goto out_locked;
1143         }
1144
1145         ret = 0;
1146 out_locked:
1147         mutex_unlock(&block_group->free_space_lock);
1148 out:
1149         btrfs_free_path(path2);
1150         btrfs_free_path(path);
1151         return ret;
1152 }
1153
1154 int btrfs_create_free_space_tree(struct btrfs_fs_info *fs_info)
1155 {
1156         struct btrfs_trans_handle *trans;
1157         struct btrfs_root *tree_root = fs_info->tree_root;
1158         struct btrfs_root *free_space_root;
1159         struct btrfs_block_group_cache *block_group;
1160         struct rb_node *node;
1161         int ret;
1162
1163         trans = btrfs_start_transaction(tree_root, 0);
1164         if (IS_ERR(trans))
1165                 return PTR_ERR(trans);
1166
1167         set_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1168         free_space_root = btrfs_create_tree(trans, fs_info,
1169                                             BTRFS_FREE_SPACE_TREE_OBJECTID);
1170         if (IS_ERR(free_space_root)) {
1171                 ret = PTR_ERR(free_space_root);
1172                 goto abort;
1173         }
1174         fs_info->free_space_root = free_space_root;
1175
1176         node = rb_first(&fs_info->block_group_cache_tree);
1177         while (node) {
1178                 block_group = rb_entry(node, struct btrfs_block_group_cache,
1179                                        cache_node);
1180                 ret = populate_free_space_tree(trans, fs_info, block_group);
1181                 if (ret)
1182                         goto abort;
1183                 node = rb_next(node);
1184         }
1185
1186         btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1187         btrfs_set_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1188         clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1189
1190         ret = btrfs_commit_transaction(trans, tree_root);
1191         if (ret)
1192                 return ret;
1193
1194         return 0;
1195
1196 abort:
1197         clear_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags);
1198         btrfs_abort_transaction(trans, ret);
1199         btrfs_end_transaction(trans, tree_root);
1200         return ret;
1201 }
1202
1203 static int clear_free_space_tree(struct btrfs_trans_handle *trans,
1204                                  struct btrfs_root *root)
1205 {
1206         struct btrfs_path *path;
1207         struct btrfs_key key;
1208         int nr;
1209         int ret;
1210
1211         path = btrfs_alloc_path();
1212         if (!path)
1213                 return -ENOMEM;
1214
1215         path->leave_spinning = 1;
1216
1217         key.objectid = 0;
1218         key.type = 0;
1219         key.offset = 0;
1220
1221         while (1) {
1222                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1223                 if (ret < 0)
1224                         goto out;
1225
1226                 nr = btrfs_header_nritems(path->nodes[0]);
1227                 if (!nr)
1228                         break;
1229
1230                 path->slots[0] = 0;
1231                 ret = btrfs_del_items(trans, root, path, 0, nr);
1232                 if (ret)
1233                         goto out;
1234
1235                 btrfs_release_path(path);
1236         }
1237
1238         ret = 0;
1239 out:
1240         btrfs_free_path(path);
1241         return ret;
1242 }
1243
1244 int btrfs_clear_free_space_tree(struct btrfs_fs_info *fs_info)
1245 {
1246         struct btrfs_trans_handle *trans;
1247         struct btrfs_root *tree_root = fs_info->tree_root;
1248         struct btrfs_root *free_space_root = fs_info->free_space_root;
1249         int ret;
1250
1251         trans = btrfs_start_transaction(tree_root, 0);
1252         if (IS_ERR(trans))
1253                 return PTR_ERR(trans);
1254
1255         btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE);
1256         btrfs_clear_fs_compat_ro(fs_info, FREE_SPACE_TREE_VALID);
1257         fs_info->free_space_root = NULL;
1258
1259         ret = clear_free_space_tree(trans, free_space_root);
1260         if (ret)
1261                 goto abort;
1262
1263         ret = btrfs_del_root(trans, tree_root, &free_space_root->root_key);
1264         if (ret)
1265                 goto abort;
1266
1267         list_del(&free_space_root->dirty_list);
1268
1269         btrfs_tree_lock(free_space_root->node);
1270         clean_tree_block(trans, tree_root->fs_info, free_space_root->node);
1271         btrfs_tree_unlock(free_space_root->node);
1272         btrfs_free_tree_block(trans, free_space_root, free_space_root->node,
1273                               0, 1);
1274
1275         free_extent_buffer(free_space_root->node);
1276         free_extent_buffer(free_space_root->commit_root);
1277         kfree(free_space_root);
1278
1279         ret = btrfs_commit_transaction(trans, tree_root);
1280         if (ret)
1281                 return ret;
1282
1283         return 0;
1284
1285 abort:
1286         btrfs_abort_transaction(trans, ret);
1287         btrfs_end_transaction(trans, tree_root);
1288         return ret;
1289 }
1290
1291 static int __add_block_group_free_space(struct btrfs_trans_handle *trans,
1292                                         struct btrfs_fs_info *fs_info,
1293                                         struct btrfs_block_group_cache *block_group,
1294                                         struct btrfs_path *path)
1295 {
1296         u64 start, end;
1297         int ret;
1298
1299         start = block_group->key.objectid;
1300         end = block_group->key.objectid + block_group->key.offset;
1301
1302         block_group->needs_free_space = 0;
1303
1304         ret = add_new_free_space_info(trans, fs_info, block_group, path);
1305         if (ret)
1306                 return ret;
1307
1308         return __add_to_free_space_tree(trans, fs_info, block_group, path,
1309                                         block_group->key.objectid,
1310                                         block_group->key.offset);
1311 }
1312
1313 int add_block_group_free_space(struct btrfs_trans_handle *trans,
1314                                struct btrfs_fs_info *fs_info,
1315                                struct btrfs_block_group_cache *block_group)
1316 {
1317         struct btrfs_path *path = NULL;
1318         int ret = 0;
1319
1320         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1321                 return 0;
1322
1323         mutex_lock(&block_group->free_space_lock);
1324         if (!block_group->needs_free_space)
1325                 goto out;
1326
1327         path = btrfs_alloc_path();
1328         if (!path) {
1329                 ret = -ENOMEM;
1330                 goto out;
1331         }
1332
1333         ret = __add_block_group_free_space(trans, fs_info, block_group, path);
1334
1335 out:
1336         btrfs_free_path(path);
1337         mutex_unlock(&block_group->free_space_lock);
1338         if (ret)
1339                 btrfs_abort_transaction(trans, ret);
1340         return ret;
1341 }
1342
1343 int remove_block_group_free_space(struct btrfs_trans_handle *trans,
1344                                   struct btrfs_fs_info *fs_info,
1345                                   struct btrfs_block_group_cache *block_group)
1346 {
1347         struct btrfs_root *root = fs_info->free_space_root;
1348         struct btrfs_path *path;
1349         struct btrfs_key key, found_key;
1350         struct extent_buffer *leaf;
1351         u64 start, end;
1352         int done = 0, nr;
1353         int ret;
1354
1355         if (!btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
1356                 return 0;
1357
1358         if (block_group->needs_free_space) {
1359                 /* We never added this block group to the free space tree. */
1360                 return 0;
1361         }
1362
1363         path = btrfs_alloc_path();
1364         if (!path) {
1365                 ret = -ENOMEM;
1366                 goto out;
1367         }
1368
1369         start = block_group->key.objectid;
1370         end = block_group->key.objectid + block_group->key.offset;
1371
1372         key.objectid = end - 1;
1373         key.type = (u8)-1;
1374         key.offset = (u64)-1;
1375
1376         while (!done) {
1377                 ret = btrfs_search_prev_slot(trans, root, &key, path, -1, 1);
1378                 if (ret)
1379                         goto out;
1380
1381                 leaf = path->nodes[0];
1382                 nr = 0;
1383                 path->slots[0]++;
1384                 while (path->slots[0] > 0) {
1385                         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0] - 1);
1386
1387                         if (found_key.type == BTRFS_FREE_SPACE_INFO_KEY) {
1388                                 ASSERT(found_key.objectid == block_group->key.objectid);
1389                                 ASSERT(found_key.offset == block_group->key.offset);
1390                                 done = 1;
1391                                 nr++;
1392                                 path->slots[0]--;
1393                                 break;
1394                         } else if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY ||
1395                                    found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
1396                                 ASSERT(found_key.objectid >= start);
1397                                 ASSERT(found_key.objectid < end);
1398                                 ASSERT(found_key.objectid + found_key.offset <= end);
1399                                 nr++;
1400                                 path->slots[0]--;
1401                         } else {
1402                                 ASSERT(0);
1403                         }
1404                 }
1405
1406                 ret = btrfs_del_items(trans, root, path, path->slots[0], nr);
1407                 if (ret)
1408                         goto out;
1409                 btrfs_release_path(path);
1410         }
1411
1412         ret = 0;
1413 out:
1414         btrfs_free_path(path);
1415         if (ret)
1416                 btrfs_abort_transaction(trans, ret);
1417         return ret;
1418 }
1419
1420 static int load_free_space_bitmaps(struct btrfs_caching_control *caching_ctl,
1421                                    struct btrfs_path *path,
1422                                    u32 expected_extent_count)
1423 {
1424         struct btrfs_block_group_cache *block_group;
1425         struct btrfs_fs_info *fs_info;
1426         struct btrfs_root *root;
1427         struct btrfs_key key;
1428         int prev_bit = 0, bit;
1429         /* Initialize to silence GCC. */
1430         u64 extent_start = 0;
1431         u64 end, offset;
1432         u64 total_found = 0;
1433         u32 extent_count = 0;
1434         int ret;
1435
1436         block_group = caching_ctl->block_group;
1437         fs_info = block_group->fs_info;
1438         root = fs_info->free_space_root;
1439
1440         end = block_group->key.objectid + block_group->key.offset;
1441
1442         while (1) {
1443                 ret = btrfs_next_item(root, path);
1444                 if (ret < 0)
1445                         goto out;
1446                 if (ret)
1447                         break;
1448
1449                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1450
1451                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1452                         break;
1453
1454                 ASSERT(key.type == BTRFS_FREE_SPACE_BITMAP_KEY);
1455                 ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1456
1457                 caching_ctl->progress = key.objectid;
1458
1459                 offset = key.objectid;
1460                 while (offset < key.objectid + key.offset) {
1461                         bit = free_space_test_bit(block_group, path, offset);
1462                         if (prev_bit == 0 && bit == 1) {
1463                                 extent_start = offset;
1464                         } else if (prev_bit == 1 && bit == 0) {
1465                                 total_found += add_new_free_space(block_group,
1466                                                                   fs_info,
1467                                                                   extent_start,
1468                                                                   offset);
1469                                 if (total_found > CACHING_CTL_WAKE_UP) {
1470                                         total_found = 0;
1471                                         wake_up(&caching_ctl->wait);
1472                                 }
1473                                 extent_count++;
1474                         }
1475                         prev_bit = bit;
1476                         offset += block_group->sectorsize;
1477                 }
1478         }
1479         if (prev_bit == 1) {
1480                 total_found += add_new_free_space(block_group, fs_info,
1481                                                   extent_start, end);
1482                 extent_count++;
1483         }
1484
1485         if (extent_count != expected_extent_count) {
1486                 btrfs_err(fs_info,
1487                           "incorrect extent count for %llu; counted %u, expected %u",
1488                           block_group->key.objectid, extent_count,
1489                           expected_extent_count);
1490                 ASSERT(0);
1491                 ret = -EIO;
1492                 goto out;
1493         }
1494
1495         caching_ctl->progress = (u64)-1;
1496
1497         ret = 0;
1498 out:
1499         return ret;
1500 }
1501
1502 static int load_free_space_extents(struct btrfs_caching_control *caching_ctl,
1503                                    struct btrfs_path *path,
1504                                    u32 expected_extent_count)
1505 {
1506         struct btrfs_block_group_cache *block_group;
1507         struct btrfs_fs_info *fs_info;
1508         struct btrfs_root *root;
1509         struct btrfs_key key;
1510         u64 end;
1511         u64 total_found = 0;
1512         u32 extent_count = 0;
1513         int ret;
1514
1515         block_group = caching_ctl->block_group;
1516         fs_info = block_group->fs_info;
1517         root = fs_info->free_space_root;
1518
1519         end = block_group->key.objectid + block_group->key.offset;
1520
1521         while (1) {
1522                 ret = btrfs_next_item(root, path);
1523                 if (ret < 0)
1524                         goto out;
1525                 if (ret)
1526                         break;
1527
1528                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1529
1530                 if (key.type == BTRFS_FREE_SPACE_INFO_KEY)
1531                         break;
1532
1533                 ASSERT(key.type == BTRFS_FREE_SPACE_EXTENT_KEY);
1534                 ASSERT(key.objectid < end && key.objectid + key.offset <= end);
1535
1536                 caching_ctl->progress = key.objectid;
1537
1538                 total_found += add_new_free_space(block_group, fs_info,
1539                                                   key.objectid,
1540                                                   key.objectid + key.offset);
1541                 if (total_found > CACHING_CTL_WAKE_UP) {
1542                         total_found = 0;
1543                         wake_up(&caching_ctl->wait);
1544                 }
1545                 extent_count++;
1546         }
1547
1548         if (extent_count != expected_extent_count) {
1549                 btrfs_err(fs_info,
1550                           "incorrect extent count for %llu; counted %u, expected %u",
1551                           block_group->key.objectid, extent_count,
1552                           expected_extent_count);
1553                 ASSERT(0);
1554                 ret = -EIO;
1555                 goto out;
1556         }
1557
1558         caching_ctl->progress = (u64)-1;
1559
1560         ret = 0;
1561 out:
1562         return ret;
1563 }
1564
1565 int load_free_space_tree(struct btrfs_caching_control *caching_ctl)
1566 {
1567         struct btrfs_block_group_cache *block_group;
1568         struct btrfs_fs_info *fs_info;
1569         struct btrfs_free_space_info *info;
1570         struct btrfs_path *path;
1571         u32 extent_count, flags;
1572         int ret;
1573
1574         block_group = caching_ctl->block_group;
1575         fs_info = block_group->fs_info;
1576
1577         path = btrfs_alloc_path();
1578         if (!path)
1579                 return -ENOMEM;
1580
1581         /*
1582          * Just like caching_thread() doesn't want to deadlock on the extent
1583          * tree, we don't want to deadlock on the free space tree.
1584          */
1585         path->skip_locking = 1;
1586         path->search_commit_root = 1;
1587         path->reada = 1;
1588
1589         info = search_free_space_info(NULL, fs_info, block_group, path, 0);
1590         if (IS_ERR(info)) {
1591                 ret = PTR_ERR(info);
1592                 goto out;
1593         }
1594         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
1595         flags = btrfs_free_space_flags(path->nodes[0], info);
1596
1597         /*
1598          * We left path pointing to the free space info item, so now
1599          * load_free_space_foo can just iterate through the free space tree from
1600          * there.
1601          */
1602         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS)
1603                 ret = load_free_space_bitmaps(caching_ctl, path, extent_count);
1604         else
1605                 ret = load_free_space_extents(caching_ctl, path, extent_count);
1606
1607 out:
1608         btrfs_free_path(path);
1609         return ret;
1610 }