1
2
3
4
5
6#include <linux/pagemap.h>
7#include <linux/sched.h>
8#include <linux/sched/signal.h>
9#include <linux/slab.h>
10#include <linux/math64.h>
11#include <linux/ratelimit.h>
12#include <linux/error-injection.h>
13#include <linux/sched/mm.h>
14#include "ctree.h"
15#include "free-space-cache.h"
16#include "transaction.h"
17#include "disk-io.h"
18#include "extent_io.h"
19#include "inode-map.h"
20#include "volumes.h"
21#include "space-info.h"
22#include "delalloc-space.h"
23#include "block-group.h"
24
25#define BITS_PER_BITMAP (PAGE_SIZE * 8UL)
26#define MAX_CACHE_BYTES_PER_GIG SZ_32K
27
28struct btrfs_trim_range {
29 u64 start;
30 u64 bytes;
31 struct list_head list;
32};
33
34static int link_free_space(struct btrfs_free_space_ctl *ctl,
35 struct btrfs_free_space *info);
36static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
37 struct btrfs_free_space *info);
38static int btrfs_wait_cache_io_root(struct btrfs_root *root,
39 struct btrfs_trans_handle *trans,
40 struct btrfs_io_ctl *io_ctl,
41 struct btrfs_path *path);
42
43static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
44 struct btrfs_path *path,
45 u64 offset)
46{
47 struct btrfs_fs_info *fs_info = root->fs_info;
48 struct btrfs_key key;
49 struct btrfs_key location;
50 struct btrfs_disk_key disk_key;
51 struct btrfs_free_space_header *header;
52 struct extent_buffer *leaf;
53 struct inode *inode = NULL;
54 unsigned nofs_flag;
55 int ret;
56
57 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
58 key.offset = offset;
59 key.type = 0;
60
61 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
62 if (ret < 0)
63 return ERR_PTR(ret);
64 if (ret > 0) {
65 btrfs_release_path(path);
66 return ERR_PTR(-ENOENT);
67 }
68
69 leaf = path->nodes[0];
70 header = btrfs_item_ptr(leaf, path->slots[0],
71 struct btrfs_free_space_header);
72 btrfs_free_space_key(leaf, header, &disk_key);
73 btrfs_disk_key_to_cpu(&location, &disk_key);
74 btrfs_release_path(path);
75
76
77
78
79
80 nofs_flag = memalloc_nofs_save();
81 inode = btrfs_iget_path(fs_info->sb, &location, root, path);
82 btrfs_release_path(path);
83 memalloc_nofs_restore(nofs_flag);
84 if (IS_ERR(inode))
85 return inode;
86
87 mapping_set_gfp_mask(inode->i_mapping,
88 mapping_gfp_constraint(inode->i_mapping,
89 ~(__GFP_FS | __GFP_HIGHMEM)));
90
91 return inode;
92}
93
94struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group,
95 struct btrfs_path *path)
96{
97 struct btrfs_fs_info *fs_info = block_group->fs_info;
98 struct inode *inode = NULL;
99 u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
100
101 spin_lock(&block_group->lock);
102 if (block_group->inode)
103 inode = igrab(block_group->inode);
104 spin_unlock(&block_group->lock);
105 if (inode)
106 return inode;
107
108 inode = __lookup_free_space_inode(fs_info->tree_root, path,
109 block_group->start);
110 if (IS_ERR(inode))
111 return inode;
112
113 spin_lock(&block_group->lock);
114 if (!((BTRFS_I(inode)->flags & flags) == flags)) {
115 btrfs_info(fs_info, "Old style space inode found, converting.");
116 BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
117 BTRFS_INODE_NODATACOW;
118 block_group->disk_cache_state = BTRFS_DC_CLEAR;
119 }
120
121 if (!block_group->iref) {
122 block_group->inode = igrab(inode);
123 block_group->iref = 1;
124 }
125 spin_unlock(&block_group->lock);
126
127 return inode;
128}
129
130static int __create_free_space_inode(struct btrfs_root *root,
131 struct btrfs_trans_handle *trans,
132 struct btrfs_path *path,
133 u64 ino, u64 offset)
134{
135 struct btrfs_key key;
136 struct btrfs_disk_key disk_key;
137 struct btrfs_free_space_header *header;
138 struct btrfs_inode_item *inode_item;
139 struct extent_buffer *leaf;
140 u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;
141 int ret;
142
143 ret = btrfs_insert_empty_inode(trans, root, path, ino);
144 if (ret)
145 return ret;
146
147
148 if (ino != BTRFS_FREE_INO_OBJECTID)
149 flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
150
151 leaf = path->nodes[0];
152 inode_item = btrfs_item_ptr(leaf, path->slots[0],
153 struct btrfs_inode_item);
154 btrfs_item_key(leaf, &disk_key, path->slots[0]);
155 memzero_extent_buffer(leaf, (unsigned long)inode_item,
156 sizeof(*inode_item));
157 btrfs_set_inode_generation(leaf, inode_item, trans->transid);
158 btrfs_set_inode_size(leaf, inode_item, 0);
159 btrfs_set_inode_nbytes(leaf, inode_item, 0);
160 btrfs_set_inode_uid(leaf, inode_item, 0);
161 btrfs_set_inode_gid(leaf, inode_item, 0);
162 btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
163 btrfs_set_inode_flags(leaf, inode_item, flags);
164 btrfs_set_inode_nlink(leaf, inode_item, 1);
165 btrfs_set_inode_transid(leaf, inode_item, trans->transid);
166 btrfs_set_inode_block_group(leaf, inode_item, offset);
167 btrfs_mark_buffer_dirty(leaf);
168 btrfs_release_path(path);
169
170 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
171 key.offset = offset;
172 key.type = 0;
173 ret = btrfs_insert_empty_item(trans, root, path, &key,
174 sizeof(struct btrfs_free_space_header));
175 if (ret < 0) {
176 btrfs_release_path(path);
177 return ret;
178 }
179
180 leaf = path->nodes[0];
181 header = btrfs_item_ptr(leaf, path->slots[0],
182 struct btrfs_free_space_header);
183 memzero_extent_buffer(leaf, (unsigned long)header, sizeof(*header));
184 btrfs_set_free_space_key(leaf, header, &disk_key);
185 btrfs_mark_buffer_dirty(leaf);
186 btrfs_release_path(path);
187
188 return 0;
189}
190
191int create_free_space_inode(struct btrfs_trans_handle *trans,
192 struct btrfs_block_group *block_group,
193 struct btrfs_path *path)
194{
195 int ret;
196 u64 ino;
197
198 ret = btrfs_find_free_objectid(trans->fs_info->tree_root, &ino);
199 if (ret < 0)
200 return ret;
201
202 return __create_free_space_inode(trans->fs_info->tree_root, trans, path,
203 ino, block_group->start);
204}
205
206int btrfs_check_trunc_cache_free_space(struct btrfs_fs_info *fs_info,
207 struct btrfs_block_rsv *rsv)
208{
209 u64 needed_bytes;
210 int ret;
211
212
213 needed_bytes = btrfs_calc_insert_metadata_size(fs_info, 1) +
214 btrfs_calc_metadata_size(fs_info, 1);
215
216 spin_lock(&rsv->lock);
217 if (rsv->reserved < needed_bytes)
218 ret = -ENOSPC;
219 else
220 ret = 0;
221 spin_unlock(&rsv->lock);
222 return ret;
223}
224
225int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans,
226 struct btrfs_block_group *block_group,
227 struct inode *inode)
228{
229 struct btrfs_root *root = BTRFS_I(inode)->root;
230 int ret = 0;
231 bool locked = false;
232
233 if (block_group) {
234 struct btrfs_path *path = btrfs_alloc_path();
235
236 if (!path) {
237 ret = -ENOMEM;
238 goto fail;
239 }
240 locked = true;
241 mutex_lock(&trans->transaction->cache_write_mutex);
242 if (!list_empty(&block_group->io_list)) {
243 list_del_init(&block_group->io_list);
244
245 btrfs_wait_cache_io(trans, block_group, path);
246 btrfs_put_block_group(block_group);
247 }
248
249
250
251
252
253 spin_lock(&block_group->lock);
254 block_group->disk_cache_state = BTRFS_DC_CLEAR;
255 spin_unlock(&block_group->lock);
256 btrfs_free_path(path);
257 }
258
259 btrfs_i_size_write(BTRFS_I(inode), 0);
260 truncate_pagecache(inode, 0);
261
262
263
264
265
266 ret = btrfs_truncate_inode_items(trans, root, inode,
267 0, BTRFS_EXTENT_DATA_KEY);
268 if (ret)
269 goto fail;
270
271 ret = btrfs_update_inode(trans, root, inode);
272
273fail:
274 if (locked)
275 mutex_unlock(&trans->transaction->cache_write_mutex);
276 if (ret)
277 btrfs_abort_transaction(trans, ret);
278
279 return ret;
280}
281
282static void readahead_cache(struct inode *inode)
283{
284 struct file_ra_state *ra;
285 unsigned long last_index;
286
287 ra = kzalloc(sizeof(*ra), GFP_NOFS);
288 if (!ra)
289 return;
290
291 file_ra_state_init(ra, inode->i_mapping);
292 last_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;
293
294 page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);
295
296 kfree(ra);
297}
298
299static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode,
300 int write)
301{
302 int num_pages;
303 int check_crcs = 0;
304
305 num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_SIZE);
306
307 if (btrfs_ino(BTRFS_I(inode)) != BTRFS_FREE_INO_OBJECTID)
308 check_crcs = 1;
309
310
311 if (write && check_crcs &&
312 (num_pages * sizeof(u32) + sizeof(u64)) > PAGE_SIZE)
313 return -ENOSPC;
314
315 memset(io_ctl, 0, sizeof(struct btrfs_io_ctl));
316
317 io_ctl->pages = kcalloc(num_pages, sizeof(struct page *), GFP_NOFS);
318 if (!io_ctl->pages)
319 return -ENOMEM;
320
321 io_ctl->num_pages = num_pages;
322 io_ctl->fs_info = btrfs_sb(inode->i_sb);
323 io_ctl->check_crcs = check_crcs;
324 io_ctl->inode = inode;
325
326 return 0;
327}
328ALLOW_ERROR_INJECTION(io_ctl_init, ERRNO);
329
330static void io_ctl_free(struct btrfs_io_ctl *io_ctl)
331{
332 kfree(io_ctl->pages);
333 io_ctl->pages = NULL;
334}
335
336static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl)
337{
338 if (io_ctl->cur) {
339 io_ctl->cur = NULL;
340 io_ctl->orig = NULL;
341 }
342}
343
344static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear)
345{
346 ASSERT(io_ctl->index < io_ctl->num_pages);
347 io_ctl->page = io_ctl->pages[io_ctl->index++];
348 io_ctl->cur = page_address(io_ctl->page);
349 io_ctl->orig = io_ctl->cur;
350 io_ctl->size = PAGE_SIZE;
351 if (clear)
352 clear_page(io_ctl->cur);
353}
354
355static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl)
356{
357 int i;
358
359 io_ctl_unmap_page(io_ctl);
360
361 for (i = 0; i < io_ctl->num_pages; i++) {
362 if (io_ctl->pages[i]) {
363 ClearPageChecked(io_ctl->pages[i]);
364 unlock_page(io_ctl->pages[i]);
365 put_page(io_ctl->pages[i]);
366 }
367 }
368}
369
370static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, struct inode *inode,
371 int uptodate)
372{
373 struct page *page;
374 gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
375 int i;
376
377 for (i = 0; i < io_ctl->num_pages; i++) {
378 page = find_or_create_page(inode->i_mapping, i, mask);
379 if (!page) {
380 io_ctl_drop_pages(io_ctl);
381 return -ENOMEM;
382 }
383 io_ctl->pages[i] = page;
384 if (uptodate && !PageUptodate(page)) {
385 btrfs_readpage(NULL, page);
386 lock_page(page);
387 if (page->mapping != inode->i_mapping) {
388 btrfs_err(BTRFS_I(inode)->root->fs_info,
389 "free space cache page truncated");
390 io_ctl_drop_pages(io_ctl);
391 return -EIO;
392 }
393 if (!PageUptodate(page)) {
394 btrfs_err(BTRFS_I(inode)->root->fs_info,
395 "error reading free space cache");
396 io_ctl_drop_pages(io_ctl);
397 return -EIO;
398 }
399 }
400 }
401
402 for (i = 0; i < io_ctl->num_pages; i++) {
403 clear_page_dirty_for_io(io_ctl->pages[i]);
404 set_page_extent_mapped(io_ctl->pages[i]);
405 }
406
407 return 0;
408}
409
410static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation)
411{
412 __le64 *val;
413
414 io_ctl_map_page(io_ctl, 1);
415
416
417
418
419
420 if (io_ctl->check_crcs) {
421 io_ctl->cur += (sizeof(u32) * io_ctl->num_pages);
422 io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);
423 } else {
424 io_ctl->cur += sizeof(u64);
425 io_ctl->size -= sizeof(u64) * 2;
426 }
427
428 val = io_ctl->cur;
429 *val = cpu_to_le64(generation);
430 io_ctl->cur += sizeof(u64);
431}
432
433static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation)
434{
435 __le64 *gen;
436
437
438
439
440
441 if (io_ctl->check_crcs) {
442 io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
443 io_ctl->size -= sizeof(u64) +
444 (sizeof(u32) * io_ctl->num_pages);
445 } else {
446 io_ctl->cur += sizeof(u64);
447 io_ctl->size -= sizeof(u64) * 2;
448 }
449
450 gen = io_ctl->cur;
451 if (le64_to_cpu(*gen) != generation) {
452 btrfs_err_rl(io_ctl->fs_info,
453 "space cache generation (%llu) does not match inode (%llu)",
454 *gen, generation);
455 io_ctl_unmap_page(io_ctl);
456 return -EIO;
457 }
458 io_ctl->cur += sizeof(u64);
459 return 0;
460}
461
462static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index)
463{
464 u32 *tmp;
465 u32 crc = ~(u32)0;
466 unsigned offset = 0;
467
468 if (!io_ctl->check_crcs) {
469 io_ctl_unmap_page(io_ctl);
470 return;
471 }
472
473 if (index == 0)
474 offset = sizeof(u32) * io_ctl->num_pages;
475
476 crc = btrfs_crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);
477 btrfs_crc32c_final(crc, (u8 *)&crc);
478 io_ctl_unmap_page(io_ctl);
479 tmp = page_address(io_ctl->pages[0]);
480 tmp += index;
481 *tmp = crc;
482}
483
484static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index)
485{
486 u32 *tmp, val;
487 u32 crc = ~(u32)0;
488 unsigned offset = 0;
489
490 if (!io_ctl->check_crcs) {
491 io_ctl_map_page(io_ctl, 0);
492 return 0;
493 }
494
495 if (index == 0)
496 offset = sizeof(u32) * io_ctl->num_pages;
497
498 tmp = page_address(io_ctl->pages[0]);
499 tmp += index;
500 val = *tmp;
501
502 io_ctl_map_page(io_ctl, 0);
503 crc = btrfs_crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);
504 btrfs_crc32c_final(crc, (u8 *)&crc);
505 if (val != crc) {
506 btrfs_err_rl(io_ctl->fs_info,
507 "csum mismatch on free space cache");
508 io_ctl_unmap_page(io_ctl);
509 return -EIO;
510 }
511
512 return 0;
513}
514
515static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes,
516 void *bitmap)
517{
518 struct btrfs_free_space_entry *entry;
519
520 if (!io_ctl->cur)
521 return -ENOSPC;
522
523 entry = io_ctl->cur;
524 entry->offset = cpu_to_le64(offset);
525 entry->bytes = cpu_to_le64(bytes);
526 entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :
527 BTRFS_FREE_SPACE_EXTENT;
528 io_ctl->cur += sizeof(struct btrfs_free_space_entry);
529 io_ctl->size -= sizeof(struct btrfs_free_space_entry);
530
531 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
532 return 0;
533
534 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
535
536
537 if (io_ctl->index >= io_ctl->num_pages)
538 return 0;
539
540
541 io_ctl_map_page(io_ctl, 1);
542 return 0;
543}
544
545static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap)
546{
547 if (!io_ctl->cur)
548 return -ENOSPC;
549
550
551
552
553
554 if (io_ctl->cur != io_ctl->orig) {
555 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
556 if (io_ctl->index >= io_ctl->num_pages)
557 return -ENOSPC;
558 io_ctl_map_page(io_ctl, 0);
559 }
560
561 copy_page(io_ctl->cur, bitmap);
562 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
563 if (io_ctl->index < io_ctl->num_pages)
564 io_ctl_map_page(io_ctl, 0);
565 return 0;
566}
567
568static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl)
569{
570
571
572
573
574 if (io_ctl->cur != io_ctl->orig)
575 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
576 else
577 io_ctl_unmap_page(io_ctl);
578
579 while (io_ctl->index < io_ctl->num_pages) {
580 io_ctl_map_page(io_ctl, 1);
581 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
582 }
583}
584
585static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl,
586 struct btrfs_free_space *entry, u8 *type)
587{
588 struct btrfs_free_space_entry *e;
589 int ret;
590
591 if (!io_ctl->cur) {
592 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
593 if (ret)
594 return ret;
595 }
596
597 e = io_ctl->cur;
598 entry->offset = le64_to_cpu(e->offset);
599 entry->bytes = le64_to_cpu(e->bytes);
600 *type = e->type;
601 io_ctl->cur += sizeof(struct btrfs_free_space_entry);
602 io_ctl->size -= sizeof(struct btrfs_free_space_entry);
603
604 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
605 return 0;
606
607 io_ctl_unmap_page(io_ctl);
608
609 return 0;
610}
611
612static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl,
613 struct btrfs_free_space *entry)
614{
615 int ret;
616
617 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
618 if (ret)
619 return ret;
620
621 copy_page(entry->bitmap, io_ctl->cur);
622 io_ctl_unmap_page(io_ctl);
623
624 return 0;
625}
626
627
628
629
630
631
632
633
634
635
636static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
637{
638 struct btrfs_free_space *e, *prev = NULL;
639 struct rb_node *n;
640
641again:
642 spin_lock(&ctl->tree_lock);
643 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
644 e = rb_entry(n, struct btrfs_free_space, offset_index);
645 if (!prev)
646 goto next;
647 if (e->bitmap || prev->bitmap)
648 goto next;
649 if (prev->offset + prev->bytes == e->offset) {
650 unlink_free_space(ctl, prev);
651 unlink_free_space(ctl, e);
652 prev->bytes += e->bytes;
653 kmem_cache_free(btrfs_free_space_cachep, e);
654 link_free_space(ctl, prev);
655 prev = NULL;
656 spin_unlock(&ctl->tree_lock);
657 goto again;
658 }
659next:
660 prev = e;
661 }
662 spin_unlock(&ctl->tree_lock);
663}
664
665static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
666 struct btrfs_free_space_ctl *ctl,
667 struct btrfs_path *path, u64 offset)
668{
669 struct btrfs_fs_info *fs_info = root->fs_info;
670 struct btrfs_free_space_header *header;
671 struct extent_buffer *leaf;
672 struct btrfs_io_ctl io_ctl;
673 struct btrfs_key key;
674 struct btrfs_free_space *e, *n;
675 LIST_HEAD(bitmaps);
676 u64 num_entries;
677 u64 num_bitmaps;
678 u64 generation;
679 u8 type;
680 int ret = 0;
681
682
683 if (!i_size_read(inode))
684 return 0;
685
686 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
687 key.offset = offset;
688 key.type = 0;
689
690 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
691 if (ret < 0)
692 return 0;
693 else if (ret > 0) {
694 btrfs_release_path(path);
695 return 0;
696 }
697
698 ret = -1;
699
700 leaf = path->nodes[0];
701 header = btrfs_item_ptr(leaf, path->slots[0],
702 struct btrfs_free_space_header);
703 num_entries = btrfs_free_space_entries(leaf, header);
704 num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
705 generation = btrfs_free_space_generation(leaf, header);
706 btrfs_release_path(path);
707
708 if (!BTRFS_I(inode)->generation) {
709 btrfs_info(fs_info,
710 "the free space cache file (%llu) is invalid, skip it",
711 offset);
712 return 0;
713 }
714
715 if (BTRFS_I(inode)->generation != generation) {
716 btrfs_err(fs_info,
717 "free space inode generation (%llu) did not match free space cache generation (%llu)",
718 BTRFS_I(inode)->generation, generation);
719 return 0;
720 }
721
722 if (!num_entries)
723 return 0;
724
725 ret = io_ctl_init(&io_ctl, inode, 0);
726 if (ret)
727 return ret;
728
729 readahead_cache(inode);
730
731 ret = io_ctl_prepare_pages(&io_ctl, inode, 1);
732 if (ret)
733 goto out;
734
735 ret = io_ctl_check_crc(&io_ctl, 0);
736 if (ret)
737 goto free_cache;
738
739 ret = io_ctl_check_generation(&io_ctl, generation);
740 if (ret)
741 goto free_cache;
742
743 while (num_entries) {
744 e = kmem_cache_zalloc(btrfs_free_space_cachep,
745 GFP_NOFS);
746 if (!e)
747 goto free_cache;
748
749 ret = io_ctl_read_entry(&io_ctl, e, &type);
750 if (ret) {
751 kmem_cache_free(btrfs_free_space_cachep, e);
752 goto free_cache;
753 }
754
755 if (!e->bytes) {
756 kmem_cache_free(btrfs_free_space_cachep, e);
757 goto free_cache;
758 }
759
760 if (type == BTRFS_FREE_SPACE_EXTENT) {
761 spin_lock(&ctl->tree_lock);
762 ret = link_free_space(ctl, e);
763 spin_unlock(&ctl->tree_lock);
764 if (ret) {
765 btrfs_err(fs_info,
766 "Duplicate entries in free space cache, dumping");
767 kmem_cache_free(btrfs_free_space_cachep, e);
768 goto free_cache;
769 }
770 } else {
771 ASSERT(num_bitmaps);
772 num_bitmaps--;
773 e->bitmap = kmem_cache_zalloc(
774 btrfs_free_space_bitmap_cachep, GFP_NOFS);
775 if (!e->bitmap) {
776 kmem_cache_free(
777 btrfs_free_space_cachep, e);
778 goto free_cache;
779 }
780 spin_lock(&ctl->tree_lock);
781 ret = link_free_space(ctl, e);
782 ctl->total_bitmaps++;
783 ctl->op->recalc_thresholds(ctl);
784 spin_unlock(&ctl->tree_lock);
785 if (ret) {
786 btrfs_err(fs_info,
787 "Duplicate entries in free space cache, dumping");
788 kmem_cache_free(btrfs_free_space_cachep, e);
789 goto free_cache;
790 }
791 list_add_tail(&e->list, &bitmaps);
792 }
793
794 num_entries--;
795 }
796
797 io_ctl_unmap_page(&io_ctl);
798
799
800
801
802
803 list_for_each_entry_safe(e, n, &bitmaps, list) {
804 list_del_init(&e->list);
805 ret = io_ctl_read_bitmap(&io_ctl, e);
806 if (ret)
807 goto free_cache;
808 }
809
810 io_ctl_drop_pages(&io_ctl);
811 merge_space_tree(ctl);
812 ret = 1;
813out:
814 io_ctl_free(&io_ctl);
815 return ret;
816free_cache:
817 io_ctl_drop_pages(&io_ctl);
818 __btrfs_remove_free_space_cache(ctl);
819 goto out;
820}
821
822int load_free_space_cache(struct btrfs_block_group *block_group)
823{
824 struct btrfs_fs_info *fs_info = block_group->fs_info;
825 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
826 struct inode *inode;
827 struct btrfs_path *path;
828 int ret = 0;
829 bool matched;
830 u64 used = block_group->used;
831
832
833
834
835
836 spin_lock(&block_group->lock);
837 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
838 spin_unlock(&block_group->lock);
839 return 0;
840 }
841 spin_unlock(&block_group->lock);
842
843 path = btrfs_alloc_path();
844 if (!path)
845 return 0;
846 path->search_commit_root = 1;
847 path->skip_locking = 1;
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868 inode = lookup_free_space_inode(block_group, path);
869 if (IS_ERR(inode)) {
870 btrfs_free_path(path);
871 return 0;
872 }
873
874
875 spin_lock(&block_group->lock);
876 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
877 spin_unlock(&block_group->lock);
878 btrfs_free_path(path);
879 goto out;
880 }
881 spin_unlock(&block_group->lock);
882
883 ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
884 path, block_group->start);
885 btrfs_free_path(path);
886 if (ret <= 0)
887 goto out;
888
889 spin_lock(&ctl->tree_lock);
890 matched = (ctl->free_space == (block_group->length - used -
891 block_group->bytes_super));
892 spin_unlock(&ctl->tree_lock);
893
894 if (!matched) {
895 __btrfs_remove_free_space_cache(ctl);
896 btrfs_warn(fs_info,
897 "block group %llu has wrong amount of free space",
898 block_group->start);
899 ret = -1;
900 }
901out:
902 if (ret < 0) {
903
904 spin_lock(&block_group->lock);
905 block_group->disk_cache_state = BTRFS_DC_CLEAR;
906 spin_unlock(&block_group->lock);
907 ret = 0;
908
909 btrfs_warn(fs_info,
910 "failed to load free space cache for block group %llu, rebuilding it now",
911 block_group->start);
912 }
913
914 iput(inode);
915 return ret;
916}
917
918static noinline_for_stack
919int write_cache_extent_entries(struct btrfs_io_ctl *io_ctl,
920 struct btrfs_free_space_ctl *ctl,
921 struct btrfs_block_group *block_group,
922 int *entries, int *bitmaps,
923 struct list_head *bitmap_list)
924{
925 int ret;
926 struct btrfs_free_cluster *cluster = NULL;
927 struct btrfs_free_cluster *cluster_locked = NULL;
928 struct rb_node *node = rb_first(&ctl->free_space_offset);
929 struct btrfs_trim_range *trim_entry;
930
931
932 if (block_group && !list_empty(&block_group->cluster_list)) {
933 cluster = list_entry(block_group->cluster_list.next,
934 struct btrfs_free_cluster,
935 block_group_list);
936 }
937
938 if (!node && cluster) {
939 cluster_locked = cluster;
940 spin_lock(&cluster_locked->lock);
941 node = rb_first(&cluster->root);
942 cluster = NULL;
943 }
944
945
946 while (node) {
947 struct btrfs_free_space *e;
948
949 e = rb_entry(node, struct btrfs_free_space, offset_index);
950 *entries += 1;
951
952 ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes,
953 e->bitmap);
954 if (ret)
955 goto fail;
956
957 if (e->bitmap) {
958 list_add_tail(&e->list, bitmap_list);
959 *bitmaps += 1;
960 }
961 node = rb_next(node);
962 if (!node && cluster) {
963 node = rb_first(&cluster->root);
964 cluster_locked = cluster;
965 spin_lock(&cluster_locked->lock);
966 cluster = NULL;
967 }
968 }
969 if (cluster_locked) {
970 spin_unlock(&cluster_locked->lock);
971 cluster_locked = NULL;
972 }
973
974
975
976
977
978
979
980 list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {
981 ret = io_ctl_add_entry(io_ctl, trim_entry->start,
982 trim_entry->bytes, NULL);
983 if (ret)
984 goto fail;
985 *entries += 1;
986 }
987
988 return 0;
989fail:
990 if (cluster_locked)
991 spin_unlock(&cluster_locked->lock);
992 return -ENOSPC;
993}
994
995static noinline_for_stack int
996update_cache_item(struct btrfs_trans_handle *trans,
997 struct btrfs_root *root,
998 struct inode *inode,
999 struct btrfs_path *path, u64 offset,
1000 int entries, int bitmaps)
1001{
1002 struct btrfs_key key;
1003 struct btrfs_free_space_header *header;
1004 struct extent_buffer *leaf;
1005 int ret;
1006
1007 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
1008 key.offset = offset;
1009 key.type = 0;
1010
1011 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1012 if (ret < 0) {
1013 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
1014 EXTENT_DELALLOC, 0, 0, NULL);
1015 goto fail;
1016 }
1017 leaf = path->nodes[0];
1018 if (ret > 0) {
1019 struct btrfs_key found_key;
1020 ASSERT(path->slots[0]);
1021 path->slots[0]--;
1022 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1023 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
1024 found_key.offset != offset) {
1025 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,
1026 inode->i_size - 1, EXTENT_DELALLOC, 0,
1027 0, NULL);
1028 btrfs_release_path(path);
1029 goto fail;
1030 }
1031 }
1032
1033 BTRFS_I(inode)->generation = trans->transid;
1034 header = btrfs_item_ptr(leaf, path->slots[0],
1035 struct btrfs_free_space_header);
1036 btrfs_set_free_space_entries(leaf, header, entries);
1037 btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
1038 btrfs_set_free_space_generation(leaf, header, trans->transid);
1039 btrfs_mark_buffer_dirty(leaf);
1040 btrfs_release_path(path);
1041
1042 return 0;
1043
1044fail:
1045 return -1;
1046}
1047
1048static noinline_for_stack int write_pinned_extent_entries(
1049 struct btrfs_block_group *block_group,
1050 struct btrfs_io_ctl *io_ctl,
1051 int *entries)
1052{
1053 u64 start, extent_start, extent_end, len;
1054 struct extent_io_tree *unpin = NULL;
1055 int ret;
1056
1057 if (!block_group)
1058 return 0;
1059
1060
1061
1062
1063
1064
1065
1066
1067 unpin = block_group->fs_info->pinned_extents;
1068
1069 start = block_group->start;
1070
1071 while (start < block_group->start + block_group->length) {
1072 ret = find_first_extent_bit(unpin, start,
1073 &extent_start, &extent_end,
1074 EXTENT_DIRTY, NULL);
1075 if (ret)
1076 return 0;
1077
1078
1079 if (extent_start >= block_group->start + block_group->length)
1080 return 0;
1081
1082 extent_start = max(extent_start, start);
1083 extent_end = min(block_group->start + block_group->length,
1084 extent_end + 1);
1085 len = extent_end - extent_start;
1086
1087 *entries += 1;
1088 ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);
1089 if (ret)
1090 return -ENOSPC;
1091
1092 start = extent_end;
1093 }
1094
1095 return 0;
1096}
1097
1098static noinline_for_stack int
1099write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list)
1100{
1101 struct btrfs_free_space *entry, *next;
1102 int ret;
1103
1104
1105 list_for_each_entry_safe(entry, next, bitmap_list, list) {
1106 ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);
1107 if (ret)
1108 return -ENOSPC;
1109 list_del_init(&entry->list);
1110 }
1111
1112 return 0;
1113}
1114
1115static int flush_dirty_cache(struct inode *inode)
1116{
1117 int ret;
1118
1119 ret = btrfs_wait_ordered_range(inode, 0, (u64)-1);
1120 if (ret)
1121 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
1122 EXTENT_DELALLOC, 0, 0, NULL);
1123
1124 return ret;
1125}
1126
1127static void noinline_for_stack
1128cleanup_bitmap_list(struct list_head *bitmap_list)
1129{
1130 struct btrfs_free_space *entry, *next;
1131
1132 list_for_each_entry_safe(entry, next, bitmap_list, list)
1133 list_del_init(&entry->list);
1134}
1135
1136static void noinline_for_stack
1137cleanup_write_cache_enospc(struct inode *inode,
1138 struct btrfs_io_ctl *io_ctl,
1139 struct extent_state **cached_state)
1140{
1141 io_ctl_drop_pages(io_ctl);
1142 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
1143 i_size_read(inode) - 1, cached_state);
1144}
1145
1146static int __btrfs_wait_cache_io(struct btrfs_root *root,
1147 struct btrfs_trans_handle *trans,
1148 struct btrfs_block_group *block_group,
1149 struct btrfs_io_ctl *io_ctl,
1150 struct btrfs_path *path, u64 offset)
1151{
1152 int ret;
1153 struct inode *inode = io_ctl->inode;
1154
1155 if (!inode)
1156 return 0;
1157
1158
1159 ret = flush_dirty_cache(inode);
1160 if (ret)
1161 goto out;
1162
1163
1164 ret = update_cache_item(trans, root, inode, path, offset,
1165 io_ctl->entries, io_ctl->bitmaps);
1166out:
1167 io_ctl_free(io_ctl);
1168 if (ret) {
1169 invalidate_inode_pages2(inode->i_mapping);
1170 BTRFS_I(inode)->generation = 0;
1171 if (block_group) {
1172#ifdef DEBUG
1173 btrfs_err(root->fs_info,
1174 "failed to write free space cache for block group %llu",
1175 block_group->start);
1176#endif
1177 }
1178 }
1179 btrfs_update_inode(trans, root, inode);
1180
1181 if (block_group) {
1182
1183 spin_lock(&trans->transaction->dirty_bgs_lock);
1184
1185
1186 spin_lock(&block_group->lock);
1187
1188
1189
1190
1191
1192
1193 if (!ret && list_empty(&block_group->dirty_list))
1194 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
1195 else if (ret)
1196 block_group->disk_cache_state = BTRFS_DC_ERROR;
1197
1198 spin_unlock(&block_group->lock);
1199 spin_unlock(&trans->transaction->dirty_bgs_lock);
1200 io_ctl->inode = NULL;
1201 iput(inode);
1202 }
1203
1204 return ret;
1205
1206}
1207
1208static int btrfs_wait_cache_io_root(struct btrfs_root *root,
1209 struct btrfs_trans_handle *trans,
1210 struct btrfs_io_ctl *io_ctl,
1211 struct btrfs_path *path)
1212{
1213 return __btrfs_wait_cache_io(root, trans, NULL, io_ctl, path, 0);
1214}
1215
1216int btrfs_wait_cache_io(struct btrfs_trans_handle *trans,
1217 struct btrfs_block_group *block_group,
1218 struct btrfs_path *path)
1219{
1220 return __btrfs_wait_cache_io(block_group->fs_info->tree_root, trans,
1221 block_group, &block_group->io_ctl,
1222 path, block_group->start);
1223}
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
1237 struct btrfs_free_space_ctl *ctl,
1238 struct btrfs_block_group *block_group,
1239 struct btrfs_io_ctl *io_ctl,
1240 struct btrfs_trans_handle *trans)
1241{
1242 struct extent_state *cached_state = NULL;
1243 LIST_HEAD(bitmap_list);
1244 int entries = 0;
1245 int bitmaps = 0;
1246 int ret;
1247 int must_iput = 0;
1248
1249 if (!i_size_read(inode))
1250 return -EIO;
1251
1252 WARN_ON(io_ctl->pages);
1253 ret = io_ctl_init(io_ctl, inode, 1);
1254 if (ret)
1255 return ret;
1256
1257 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) {
1258 down_write(&block_group->data_rwsem);
1259 spin_lock(&block_group->lock);
1260 if (block_group->delalloc_bytes) {
1261 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
1262 spin_unlock(&block_group->lock);
1263 up_write(&block_group->data_rwsem);
1264 BTRFS_I(inode)->generation = 0;
1265 ret = 0;
1266 must_iput = 1;
1267 goto out;
1268 }
1269 spin_unlock(&block_group->lock);
1270 }
1271
1272
1273 ret = io_ctl_prepare_pages(io_ctl, inode, 0);
1274 if (ret)
1275 goto out_unlock;
1276
1277 lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
1278 &cached_state);
1279
1280 io_ctl_set_generation(io_ctl, trans->transid);
1281
1282 mutex_lock(&ctl->cache_writeout_mutex);
1283
1284 spin_lock(&ctl->tree_lock);
1285 ret = write_cache_extent_entries(io_ctl, ctl,
1286 block_group, &entries, &bitmaps,
1287 &bitmap_list);
1288 if (ret)
1289 goto out_nospc_locked;
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299 ret = write_pinned_extent_entries(block_group, io_ctl, &entries);
1300 if (ret)
1301 goto out_nospc_locked;
1302
1303
1304
1305
1306
1307
1308 ret = write_bitmap_entries(io_ctl, &bitmap_list);
1309 spin_unlock(&ctl->tree_lock);
1310 mutex_unlock(&ctl->cache_writeout_mutex);
1311 if (ret)
1312 goto out_nospc;
1313
1314
1315 io_ctl_zero_remaining_pages(io_ctl);
1316
1317
1318 ret = btrfs_dirty_pages(inode, io_ctl->pages, io_ctl->num_pages, 0,
1319 i_size_read(inode), &cached_state);
1320 if (ret)
1321 goto out_nospc;
1322
1323 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
1324 up_write(&block_group->data_rwsem);
1325
1326
1327
1328
1329 io_ctl_drop_pages(io_ctl);
1330
1331 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
1332 i_size_read(inode) - 1, &cached_state);
1333
1334
1335
1336
1337
1338
1339 io_ctl->entries = entries;
1340 io_ctl->bitmaps = bitmaps;
1341
1342 ret = btrfs_fdatawrite_range(inode, 0, (u64)-1);
1343 if (ret)
1344 goto out;
1345
1346 return 0;
1347
1348out:
1349 io_ctl->inode = NULL;
1350 io_ctl_free(io_ctl);
1351 if (ret) {
1352 invalidate_inode_pages2(inode->i_mapping);
1353 BTRFS_I(inode)->generation = 0;
1354 }
1355 btrfs_update_inode(trans, root, inode);
1356 if (must_iput)
1357 iput(inode);
1358 return ret;
1359
1360out_nospc_locked:
1361 cleanup_bitmap_list(&bitmap_list);
1362 spin_unlock(&ctl->tree_lock);
1363 mutex_unlock(&ctl->cache_writeout_mutex);
1364
1365out_nospc:
1366 cleanup_write_cache_enospc(inode, io_ctl, &cached_state);
1367
1368out_unlock:
1369 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
1370 up_write(&block_group->data_rwsem);
1371
1372 goto out;
1373}
1374
1375int btrfs_write_out_cache(struct btrfs_trans_handle *trans,
1376 struct btrfs_block_group *block_group,
1377 struct btrfs_path *path)
1378{
1379 struct btrfs_fs_info *fs_info = trans->fs_info;
1380 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1381 struct inode *inode;
1382 int ret = 0;
1383
1384 spin_lock(&block_group->lock);
1385 if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
1386 spin_unlock(&block_group->lock);
1387 return 0;
1388 }
1389 spin_unlock(&block_group->lock);
1390
1391 inode = lookup_free_space_inode(block_group, path);
1392 if (IS_ERR(inode))
1393 return 0;
1394
1395 ret = __btrfs_write_out_cache(fs_info->tree_root, inode, ctl,
1396 block_group, &block_group->io_ctl, trans);
1397 if (ret) {
1398#ifdef DEBUG
1399 btrfs_err(fs_info,
1400 "failed to write free space cache for block group %llu",
1401 block_group->start);
1402#endif
1403 spin_lock(&block_group->lock);
1404 block_group->disk_cache_state = BTRFS_DC_ERROR;
1405 spin_unlock(&block_group->lock);
1406
1407 block_group->io_ctl.inode = NULL;
1408 iput(inode);
1409 }
1410
1411
1412
1413
1414
1415
1416 return ret;
1417}
1418
1419static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
1420 u64 offset)
1421{
1422 ASSERT(offset >= bitmap_start);
1423 offset -= bitmap_start;
1424 return (unsigned long)(div_u64(offset, unit));
1425}
1426
1427static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
1428{
1429 return (unsigned long)(div_u64(bytes, unit));
1430}
1431
1432static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
1433 u64 offset)
1434{
1435 u64 bitmap_start;
1436 u64 bytes_per_bitmap;
1437
1438 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
1439 bitmap_start = offset - ctl->start;
1440 bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
1441 bitmap_start *= bytes_per_bitmap;
1442 bitmap_start += ctl->start;
1443
1444 return bitmap_start;
1445}
1446
1447static int tree_insert_offset(struct rb_root *root, u64 offset,
1448 struct rb_node *node, int bitmap)
1449{
1450 struct rb_node **p = &root->rb_node;
1451 struct rb_node *parent = NULL;
1452 struct btrfs_free_space *info;
1453
1454 while (*p) {
1455 parent = *p;
1456 info = rb_entry(parent, struct btrfs_free_space, offset_index);
1457
1458 if (offset < info->offset) {
1459 p = &(*p)->rb_left;
1460 } else if (offset > info->offset) {
1461 p = &(*p)->rb_right;
1462 } else {
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476 if (bitmap) {
1477 if (info->bitmap) {
1478 WARN_ON_ONCE(1);
1479 return -EEXIST;
1480 }
1481 p = &(*p)->rb_right;
1482 } else {
1483 if (!info->bitmap) {
1484 WARN_ON_ONCE(1);
1485 return -EEXIST;
1486 }
1487 p = &(*p)->rb_left;
1488 }
1489 }
1490 }
1491
1492 rb_link_node(node, parent, p);
1493 rb_insert_color(node, root);
1494
1495 return 0;
1496}
1497
1498
1499
1500
1501
1502
1503
1504
1505static struct btrfs_free_space *
1506tree_search_offset(struct btrfs_free_space_ctl *ctl,
1507 u64 offset, int bitmap_only, int fuzzy)
1508{
1509 struct rb_node *n = ctl->free_space_offset.rb_node;
1510 struct btrfs_free_space *entry, *prev = NULL;
1511
1512
1513 while (1) {
1514 if (!n) {
1515 entry = NULL;
1516 break;
1517 }
1518
1519 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1520 prev = entry;
1521
1522 if (offset < entry->offset)
1523 n = n->rb_left;
1524 else if (offset > entry->offset)
1525 n = n->rb_right;
1526 else
1527 break;
1528 }
1529
1530 if (bitmap_only) {
1531 if (!entry)
1532 return NULL;
1533 if (entry->bitmap)
1534 return entry;
1535
1536
1537
1538
1539
1540 n = rb_next(n);
1541 if (!n)
1542 return NULL;
1543 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1544 if (entry->offset != offset)
1545 return NULL;
1546
1547 WARN_ON(!entry->bitmap);
1548 return entry;
1549 } else if (entry) {
1550 if (entry->bitmap) {
1551
1552
1553
1554
1555 n = rb_prev(&entry->offset_index);
1556 if (n) {
1557 prev = rb_entry(n, struct btrfs_free_space,
1558 offset_index);
1559 if (!prev->bitmap &&
1560 prev->offset + prev->bytes > offset)
1561 entry = prev;
1562 }
1563 }
1564 return entry;
1565 }
1566
1567 if (!prev)
1568 return NULL;
1569
1570
1571 entry = prev;
1572 if (entry->offset > offset) {
1573 n = rb_prev(&entry->offset_index);
1574 if (n) {
1575 entry = rb_entry(n, struct btrfs_free_space,
1576 offset_index);
1577 ASSERT(entry->offset <= offset);
1578 } else {
1579 if (fuzzy)
1580 return entry;
1581 else
1582 return NULL;
1583 }
1584 }
1585
1586 if (entry->bitmap) {
1587 n = rb_prev(&entry->offset_index);
1588 if (n) {
1589 prev = rb_entry(n, struct btrfs_free_space,
1590 offset_index);
1591 if (!prev->bitmap &&
1592 prev->offset + prev->bytes > offset)
1593 return prev;
1594 }
1595 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
1596 return entry;
1597 } else if (entry->offset + entry->bytes > offset)
1598 return entry;
1599
1600 if (!fuzzy)
1601 return NULL;
1602
1603 while (1) {
1604 if (entry->bitmap) {
1605 if (entry->offset + BITS_PER_BITMAP *
1606 ctl->unit > offset)
1607 break;
1608 } else {
1609 if (entry->offset + entry->bytes > offset)
1610 break;
1611 }
1612
1613 n = rb_next(&entry->offset_index);
1614 if (!n)
1615 return NULL;
1616 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1617 }
1618 return entry;
1619}
1620
1621static inline void
1622__unlink_free_space(struct btrfs_free_space_ctl *ctl,
1623 struct btrfs_free_space *info)
1624{
1625 rb_erase(&info->offset_index, &ctl->free_space_offset);
1626 ctl->free_extents--;
1627}
1628
1629static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
1630 struct btrfs_free_space *info)
1631{
1632 __unlink_free_space(ctl, info);
1633 ctl->free_space -= info->bytes;
1634}
1635
1636static int link_free_space(struct btrfs_free_space_ctl *ctl,
1637 struct btrfs_free_space *info)
1638{
1639 int ret = 0;
1640
1641 ASSERT(info->bytes || info->bitmap);
1642 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1643 &info->offset_index, (info->bitmap != NULL));
1644 if (ret)
1645 return ret;
1646
1647 ctl->free_space += info->bytes;
1648 ctl->free_extents++;
1649 return ret;
1650}
1651
1652static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1653{
1654 struct btrfs_block_group *block_group = ctl->private;
1655 u64 max_bytes;
1656 u64 bitmap_bytes;
1657 u64 extent_bytes;
1658 u64 size = block_group->length;
1659 u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
1660 u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
1661
1662 max_bitmaps = max_t(u64, max_bitmaps, 1);
1663
1664 ASSERT(ctl->total_bitmaps <= max_bitmaps);
1665
1666
1667
1668
1669
1670
1671 if (size < SZ_1G)
1672 max_bytes = MAX_CACHE_BYTES_PER_GIG;
1673 else
1674 max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G);
1675
1676
1677
1678
1679
1680
1681 bitmap_bytes = (ctl->total_bitmaps + 1) * ctl->unit;
1682
1683 if (bitmap_bytes >= max_bytes) {
1684 ctl->extents_thresh = 0;
1685 return;
1686 }
1687
1688
1689
1690
1691
1692 extent_bytes = max_bytes - bitmap_bytes;
1693 extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1);
1694
1695 ctl->extents_thresh =
1696 div_u64(extent_bytes, sizeof(struct btrfs_free_space));
1697}
1698
1699static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1700 struct btrfs_free_space *info,
1701 u64 offset, u64 bytes)
1702{
1703 unsigned long start, count;
1704
1705 start = offset_to_bit(info->offset, ctl->unit, offset);
1706 count = bytes_to_bits(bytes, ctl->unit);
1707 ASSERT(start + count <= BITS_PER_BITMAP);
1708
1709 bitmap_clear(info->bitmap, start, count);
1710
1711 info->bytes -= bytes;
1712 if (info->max_extent_size > ctl->unit)
1713 info->max_extent_size = 0;
1714}
1715
1716static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1717 struct btrfs_free_space *info, u64 offset,
1718 u64 bytes)
1719{
1720 __bitmap_clear_bits(ctl, info, offset, bytes);
1721 ctl->free_space -= bytes;
1722}
1723
1724static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
1725 struct btrfs_free_space *info, u64 offset,
1726 u64 bytes)
1727{
1728 unsigned long start, count;
1729
1730 start = offset_to_bit(info->offset, ctl->unit, offset);
1731 count = bytes_to_bits(bytes, ctl->unit);
1732 ASSERT(start + count <= BITS_PER_BITMAP);
1733
1734 bitmap_set(info->bitmap, start, count);
1735
1736 info->bytes += bytes;
1737 ctl->free_space += bytes;
1738}
1739
1740
1741
1742
1743
1744static int search_bitmap(struct btrfs_free_space_ctl *ctl,
1745 struct btrfs_free_space *bitmap_info, u64 *offset,
1746 u64 *bytes, bool for_alloc)
1747{
1748 unsigned long found_bits = 0;
1749 unsigned long max_bits = 0;
1750 unsigned long bits, i;
1751 unsigned long next_zero;
1752 unsigned long extent_bits;
1753
1754
1755
1756
1757
1758 if (for_alloc &&
1759 bitmap_info->max_extent_size &&
1760 bitmap_info->max_extent_size < *bytes) {
1761 *bytes = bitmap_info->max_extent_size;
1762 return -1;
1763 }
1764
1765 i = offset_to_bit(bitmap_info->offset, ctl->unit,
1766 max_t(u64, *offset, bitmap_info->offset));
1767 bits = bytes_to_bits(*bytes, ctl->unit);
1768
1769 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
1770 if (for_alloc && bits == 1) {
1771 found_bits = 1;
1772 break;
1773 }
1774 next_zero = find_next_zero_bit(bitmap_info->bitmap,
1775 BITS_PER_BITMAP, i);
1776 extent_bits = next_zero - i;
1777 if (extent_bits >= bits) {
1778 found_bits = extent_bits;
1779 break;
1780 } else if (extent_bits > max_bits) {
1781 max_bits = extent_bits;
1782 }
1783 i = next_zero;
1784 }
1785
1786 if (found_bits) {
1787 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
1788 *bytes = (u64)(found_bits) * ctl->unit;
1789 return 0;
1790 }
1791
1792 *bytes = (u64)(max_bits) * ctl->unit;
1793 bitmap_info->max_extent_size = *bytes;
1794 return -1;
1795}
1796
1797static inline u64 get_max_extent_size(struct btrfs_free_space *entry)
1798{
1799 if (entry->bitmap)
1800 return entry->max_extent_size;
1801 return entry->bytes;
1802}
1803
1804
1805static struct btrfs_free_space *
1806find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
1807 unsigned long align, u64 *max_extent_size)
1808{
1809 struct btrfs_free_space *entry;
1810 struct rb_node *node;
1811 u64 tmp;
1812 u64 align_off;
1813 int ret;
1814
1815 if (!ctl->free_space_offset.rb_node)
1816 goto out;
1817
1818 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
1819 if (!entry)
1820 goto out;
1821
1822 for (node = &entry->offset_index; node; node = rb_next(node)) {
1823 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1824 if (entry->bytes < *bytes) {
1825 *max_extent_size = max(get_max_extent_size(entry),
1826 *max_extent_size);
1827 continue;
1828 }
1829
1830
1831
1832
1833 if (*bytes >= align) {
1834 tmp = entry->offset - ctl->start + align - 1;
1835 tmp = div64_u64(tmp, align);
1836 tmp = tmp * align + ctl->start;
1837 align_off = tmp - entry->offset;
1838 } else {
1839 align_off = 0;
1840 tmp = entry->offset;
1841 }
1842
1843 if (entry->bytes < *bytes + align_off) {
1844 *max_extent_size = max(get_max_extent_size(entry),
1845 *max_extent_size);
1846 continue;
1847 }
1848
1849 if (entry->bitmap) {
1850 u64 size = *bytes;
1851
1852 ret = search_bitmap(ctl, entry, &tmp, &size, true);
1853 if (!ret) {
1854 *offset = tmp;
1855 *bytes = size;
1856 return entry;
1857 } else {
1858 *max_extent_size =
1859 max(get_max_extent_size(entry),
1860 *max_extent_size);
1861 }
1862 continue;
1863 }
1864
1865 *offset = tmp;
1866 *bytes = entry->bytes - align_off;
1867 return entry;
1868 }
1869out:
1870 return NULL;
1871}
1872
1873static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
1874 struct btrfs_free_space *info, u64 offset)
1875{
1876 info->offset = offset_to_bitmap(ctl, offset);
1877 info->bytes = 0;
1878 INIT_LIST_HEAD(&info->list);
1879 link_free_space(ctl, info);
1880 ctl->total_bitmaps++;
1881
1882 ctl->op->recalc_thresholds(ctl);
1883}
1884
1885static void free_bitmap(struct btrfs_free_space_ctl *ctl,
1886 struct btrfs_free_space *bitmap_info)
1887{
1888 unlink_free_space(ctl, bitmap_info);
1889 kmem_cache_free(btrfs_free_space_bitmap_cachep, bitmap_info->bitmap);
1890 kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
1891 ctl->total_bitmaps--;
1892 ctl->op->recalc_thresholds(ctl);
1893}
1894
1895static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
1896 struct btrfs_free_space *bitmap_info,
1897 u64 *offset, u64 *bytes)
1898{
1899 u64 end;
1900 u64 search_start, search_bytes;
1901 int ret;
1902
1903again:
1904 end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
1905
1906
1907
1908
1909
1910
1911
1912 search_start = *offset;
1913 search_bytes = ctl->unit;
1914 search_bytes = min(search_bytes, end - search_start + 1);
1915 ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,
1916 false);
1917 if (ret < 0 || search_start != *offset)
1918 return -EINVAL;
1919
1920
1921 search_bytes = min(search_bytes, *bytes);
1922
1923
1924 search_bytes = min(search_bytes, end - search_start + 1);
1925
1926 bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes);
1927 *offset += search_bytes;
1928 *bytes -= search_bytes;
1929
1930 if (*bytes) {
1931 struct rb_node *next = rb_next(&bitmap_info->offset_index);
1932 if (!bitmap_info->bytes)
1933 free_bitmap(ctl, bitmap_info);
1934
1935
1936
1937
1938
1939 if (!next)
1940 return -EINVAL;
1941
1942 bitmap_info = rb_entry(next, struct btrfs_free_space,
1943 offset_index);
1944
1945
1946
1947
1948
1949 if (!bitmap_info->bitmap)
1950 return -EAGAIN;
1951
1952
1953
1954
1955
1956
1957
1958 search_start = *offset;
1959 search_bytes = ctl->unit;
1960 ret = search_bitmap(ctl, bitmap_info, &search_start,
1961 &search_bytes, false);
1962 if (ret < 0 || search_start != *offset)
1963 return -EAGAIN;
1964
1965 goto again;
1966 } else if (!bitmap_info->bytes)
1967 free_bitmap(ctl, bitmap_info);
1968
1969 return 0;
1970}
1971
1972static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
1973 struct btrfs_free_space *info, u64 offset,
1974 u64 bytes)
1975{
1976 u64 bytes_to_set = 0;
1977 u64 end;
1978
1979 end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
1980
1981 bytes_to_set = min(end - offset, bytes);
1982
1983 bitmap_set_bits(ctl, info, offset, bytes_to_set);
1984
1985
1986
1987
1988
1989 info->max_extent_size = 0;
1990
1991 return bytes_to_set;
1992
1993}
1994
1995static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
1996 struct btrfs_free_space *info)
1997{
1998 struct btrfs_block_group *block_group = ctl->private;
1999 struct btrfs_fs_info *fs_info = block_group->fs_info;
2000 bool forced = false;
2001
2002#ifdef CONFIG_BTRFS_DEBUG
2003 if (btrfs_should_fragment_free_space(block_group))
2004 forced = true;
2005#endif
2006
2007
2008
2009
2010
2011 if (!forced && ctl->free_extents < ctl->extents_thresh) {
2012
2013
2014
2015
2016
2017
2018
2019 if (info->bytes <= fs_info->sectorsize * 4) {
2020 if (ctl->free_extents * 2 <= ctl->extents_thresh)
2021 return false;
2022 } else {
2023 return false;
2024 }
2025 }
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035 if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->length)
2036 return false;
2037
2038 return true;
2039}
2040
2041static const struct btrfs_free_space_op free_space_op = {
2042 .recalc_thresholds = recalculate_thresholds,
2043 .use_bitmap = use_bitmap,
2044};
2045
2046static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
2047 struct btrfs_free_space *info)
2048{
2049 struct btrfs_free_space *bitmap_info;
2050 struct btrfs_block_group *block_group = NULL;
2051 int added = 0;
2052 u64 bytes, offset, bytes_added;
2053 int ret;
2054
2055 bytes = info->bytes;
2056 offset = info->offset;
2057
2058 if (!ctl->op->use_bitmap(ctl, info))
2059 return 0;
2060
2061 if (ctl->op == &free_space_op)
2062 block_group = ctl->private;
2063again:
2064
2065
2066
2067
2068
2069 if (block_group && !list_empty(&block_group->cluster_list)) {
2070 struct btrfs_free_cluster *cluster;
2071 struct rb_node *node;
2072 struct btrfs_free_space *entry;
2073
2074 cluster = list_entry(block_group->cluster_list.next,
2075 struct btrfs_free_cluster,
2076 block_group_list);
2077 spin_lock(&cluster->lock);
2078 node = rb_first(&cluster->root);
2079 if (!node) {
2080 spin_unlock(&cluster->lock);
2081 goto no_cluster_bitmap;
2082 }
2083
2084 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2085 if (!entry->bitmap) {
2086 spin_unlock(&cluster->lock);
2087 goto no_cluster_bitmap;
2088 }
2089
2090 if (entry->offset == offset_to_bitmap(ctl, offset)) {
2091 bytes_added = add_bytes_to_bitmap(ctl, entry,
2092 offset, bytes);
2093 bytes -= bytes_added;
2094 offset += bytes_added;
2095 }
2096 spin_unlock(&cluster->lock);
2097 if (!bytes) {
2098 ret = 1;
2099 goto out;
2100 }
2101 }
2102
2103no_cluster_bitmap:
2104 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2105 1, 0);
2106 if (!bitmap_info) {
2107 ASSERT(added == 0);
2108 goto new_bitmap;
2109 }
2110
2111 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
2112 bytes -= bytes_added;
2113 offset += bytes_added;
2114 added = 0;
2115
2116 if (!bytes) {
2117 ret = 1;
2118 goto out;
2119 } else
2120 goto again;
2121
2122new_bitmap:
2123 if (info && info->bitmap) {
2124 add_new_bitmap(ctl, info, offset);
2125 added = 1;
2126 info = NULL;
2127 goto again;
2128 } else {
2129 spin_unlock(&ctl->tree_lock);
2130
2131
2132 if (!info) {
2133 info = kmem_cache_zalloc(btrfs_free_space_cachep,
2134 GFP_NOFS);
2135 if (!info) {
2136 spin_lock(&ctl->tree_lock);
2137 ret = -ENOMEM;
2138 goto out;
2139 }
2140 }
2141
2142
2143 info->bitmap = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep,
2144 GFP_NOFS);
2145 spin_lock(&ctl->tree_lock);
2146 if (!info->bitmap) {
2147 ret = -ENOMEM;
2148 goto out;
2149 }
2150 goto again;
2151 }
2152
2153out:
2154 if (info) {
2155 if (info->bitmap)
2156 kmem_cache_free(btrfs_free_space_bitmap_cachep,
2157 info->bitmap);
2158 kmem_cache_free(btrfs_free_space_cachep, info);
2159 }
2160
2161 return ret;
2162}
2163
2164static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
2165 struct btrfs_free_space *info, bool update_stat)
2166{
2167 struct btrfs_free_space *left_info;
2168 struct btrfs_free_space *right_info;
2169 bool merged = false;
2170 u64 offset = info->offset;
2171 u64 bytes = info->bytes;
2172
2173
2174
2175
2176
2177
2178 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
2179 if (right_info && rb_prev(&right_info->offset_index))
2180 left_info = rb_entry(rb_prev(&right_info->offset_index),
2181 struct btrfs_free_space, offset_index);
2182 else
2183 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
2184
2185 if (right_info && !right_info->bitmap) {
2186 if (update_stat)
2187 unlink_free_space(ctl, right_info);
2188 else
2189 __unlink_free_space(ctl, right_info);
2190 info->bytes += right_info->bytes;
2191 kmem_cache_free(btrfs_free_space_cachep, right_info);
2192 merged = true;
2193 }
2194
2195 if (left_info && !left_info->bitmap &&
2196 left_info->offset + left_info->bytes == offset) {
2197 if (update_stat)
2198 unlink_free_space(ctl, left_info);
2199 else
2200 __unlink_free_space(ctl, left_info);
2201 info->offset = left_info->offset;
2202 info->bytes += left_info->bytes;
2203 kmem_cache_free(btrfs_free_space_cachep, left_info);
2204 merged = true;
2205 }
2206
2207 return merged;
2208}
2209
2210static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
2211 struct btrfs_free_space *info,
2212 bool update_stat)
2213{
2214 struct btrfs_free_space *bitmap;
2215 unsigned long i;
2216 unsigned long j;
2217 const u64 end = info->offset + info->bytes;
2218 const u64 bitmap_offset = offset_to_bitmap(ctl, end);
2219 u64 bytes;
2220
2221 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2222 if (!bitmap)
2223 return false;
2224
2225 i = offset_to_bit(bitmap->offset, ctl->unit, end);
2226 j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
2227 if (j == i)
2228 return false;
2229 bytes = (j - i) * ctl->unit;
2230 info->bytes += bytes;
2231
2232 if (update_stat)
2233 bitmap_clear_bits(ctl, bitmap, end, bytes);
2234 else
2235 __bitmap_clear_bits(ctl, bitmap, end, bytes);
2236
2237 if (!bitmap->bytes)
2238 free_bitmap(ctl, bitmap);
2239
2240 return true;
2241}
2242
2243static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
2244 struct btrfs_free_space *info,
2245 bool update_stat)
2246{
2247 struct btrfs_free_space *bitmap;
2248 u64 bitmap_offset;
2249 unsigned long i;
2250 unsigned long j;
2251 unsigned long prev_j;
2252 u64 bytes;
2253
2254 bitmap_offset = offset_to_bitmap(ctl, info->offset);
2255
2256 if (bitmap_offset == info->offset) {
2257 if (info->offset == 0)
2258 return false;
2259 bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
2260 }
2261
2262 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2263 if (!bitmap)
2264 return false;
2265
2266 i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
2267 j = 0;
2268 prev_j = (unsigned long)-1;
2269 for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
2270 if (j > i)
2271 break;
2272 prev_j = j;
2273 }
2274 if (prev_j == i)
2275 return false;
2276
2277 if (prev_j == (unsigned long)-1)
2278 bytes = (i + 1) * ctl->unit;
2279 else
2280 bytes = (i - prev_j) * ctl->unit;
2281
2282 info->offset -= bytes;
2283 info->bytes += bytes;
2284
2285 if (update_stat)
2286 bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
2287 else
2288 __bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
2289
2290 if (!bitmap->bytes)
2291 free_bitmap(ctl, bitmap);
2292
2293 return true;
2294}
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
2308 struct btrfs_free_space *info,
2309 bool update_stat)
2310{
2311
2312
2313
2314
2315 ASSERT(!info->bitmap);
2316 ASSERT(RB_EMPTY_NODE(&info->offset_index));
2317
2318 if (ctl->total_bitmaps > 0) {
2319 bool stole_end;
2320 bool stole_front = false;
2321
2322 stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
2323 if (ctl->total_bitmaps > 0)
2324 stole_front = steal_from_bitmap_to_front(ctl, info,
2325 update_stat);
2326
2327 if (stole_end || stole_front)
2328 try_merge_free_space(ctl, info, update_stat);
2329 }
2330}
2331
2332int __btrfs_add_free_space(struct btrfs_fs_info *fs_info,
2333 struct btrfs_free_space_ctl *ctl,
2334 u64 offset, u64 bytes)
2335{
2336 struct btrfs_free_space *info;
2337 int ret = 0;
2338
2339 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
2340 if (!info)
2341 return -ENOMEM;
2342
2343 info->offset = offset;
2344 info->bytes = bytes;
2345 RB_CLEAR_NODE(&info->offset_index);
2346
2347 spin_lock(&ctl->tree_lock);
2348
2349 if (try_merge_free_space(ctl, info, true))
2350 goto link;
2351
2352
2353
2354
2355
2356
2357 ret = insert_into_bitmap(ctl, info);
2358 if (ret < 0) {
2359 goto out;
2360 } else if (ret) {
2361 ret = 0;
2362 goto out;
2363 }
2364link:
2365
2366
2367
2368
2369
2370
2371 steal_from_bitmap(ctl, info, true);
2372
2373 ret = link_free_space(ctl, info);
2374 if (ret)
2375 kmem_cache_free(btrfs_free_space_cachep, info);
2376out:
2377 spin_unlock(&ctl->tree_lock);
2378
2379 if (ret) {
2380 btrfs_crit(fs_info, "unable to add free space :%d", ret);
2381 ASSERT(ret != -EEXIST);
2382 }
2383
2384 return ret;
2385}
2386
2387int btrfs_add_free_space(struct btrfs_block_group *block_group,
2388 u64 bytenr, u64 size)
2389{
2390 return __btrfs_add_free_space(block_group->fs_info,
2391 block_group->free_space_ctl,
2392 bytenr, size);
2393}
2394
2395int btrfs_remove_free_space(struct btrfs_block_group *block_group,
2396 u64 offset, u64 bytes)
2397{
2398 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2399 struct btrfs_free_space *info;
2400 int ret;
2401 bool re_search = false;
2402
2403 spin_lock(&ctl->tree_lock);
2404
2405again:
2406 ret = 0;
2407 if (!bytes)
2408 goto out_lock;
2409
2410 info = tree_search_offset(ctl, offset, 0, 0);
2411 if (!info) {
2412
2413
2414
2415
2416 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
2417 1, 0);
2418 if (!info) {
2419
2420
2421
2422
2423
2424 WARN_ON(re_search);
2425 goto out_lock;
2426 }
2427 }
2428
2429 re_search = false;
2430 if (!info->bitmap) {
2431 unlink_free_space(ctl, info);
2432 if (offset == info->offset) {
2433 u64 to_free = min(bytes, info->bytes);
2434
2435 info->bytes -= to_free;
2436 info->offset += to_free;
2437 if (info->bytes) {
2438 ret = link_free_space(ctl, info);
2439 WARN_ON(ret);
2440 } else {
2441 kmem_cache_free(btrfs_free_space_cachep, info);
2442 }
2443
2444 offset += to_free;
2445 bytes -= to_free;
2446 goto again;
2447 } else {
2448 u64 old_end = info->bytes + info->offset;
2449
2450 info->bytes = offset - info->offset;
2451 ret = link_free_space(ctl, info);
2452 WARN_ON(ret);
2453 if (ret)
2454 goto out_lock;
2455
2456
2457 if (old_end < offset + bytes) {
2458 bytes -= old_end - offset;
2459 offset = old_end;
2460 goto again;
2461 } else if (old_end == offset + bytes) {
2462
2463 goto out_lock;
2464 }
2465 spin_unlock(&ctl->tree_lock);
2466
2467 ret = btrfs_add_free_space(block_group, offset + bytes,
2468 old_end - (offset + bytes));
2469 WARN_ON(ret);
2470 goto out;
2471 }
2472 }
2473
2474 ret = remove_from_bitmap(ctl, info, &offset, &bytes);
2475 if (ret == -EAGAIN) {
2476 re_search = true;
2477 goto again;
2478 }
2479out_lock:
2480 spin_unlock(&ctl->tree_lock);
2481out:
2482 return ret;
2483}
2484
2485void btrfs_dump_free_space(struct btrfs_block_group *block_group,
2486 u64 bytes)
2487{
2488 struct btrfs_fs_info *fs_info = block_group->fs_info;
2489 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2490 struct btrfs_free_space *info;
2491 struct rb_node *n;
2492 int count = 0;
2493
2494 spin_lock(&ctl->tree_lock);
2495 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
2496 info = rb_entry(n, struct btrfs_free_space, offset_index);
2497 if (info->bytes >= bytes && !block_group->ro)
2498 count++;
2499 btrfs_crit(fs_info, "entry offset %llu, bytes %llu, bitmap %s",
2500 info->offset, info->bytes,
2501 (info->bitmap) ? "yes" : "no");
2502 }
2503 spin_unlock(&ctl->tree_lock);
2504 btrfs_info(fs_info, "block group has cluster?: %s",
2505 list_empty(&block_group->cluster_list) ? "no" : "yes");
2506 btrfs_info(fs_info,
2507 "%d blocks of free space at or bigger than bytes is", count);
2508}
2509
2510void btrfs_init_free_space_ctl(struct btrfs_block_group *block_group)
2511{
2512 struct btrfs_fs_info *fs_info = block_group->fs_info;
2513 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2514
2515 spin_lock_init(&ctl->tree_lock);
2516 ctl->unit = fs_info->sectorsize;
2517 ctl->start = block_group->start;
2518 ctl->private = block_group;
2519 ctl->op = &free_space_op;
2520 INIT_LIST_HEAD(&ctl->trimming_ranges);
2521 mutex_init(&ctl->cache_writeout_mutex);
2522
2523
2524
2525
2526
2527
2528 ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);
2529}
2530
2531
2532
2533
2534
2535
2536
2537static int
2538__btrfs_return_cluster_to_free_space(
2539 struct btrfs_block_group *block_group,
2540 struct btrfs_free_cluster *cluster)
2541{
2542 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2543 struct btrfs_free_space *entry;
2544 struct rb_node *node;
2545
2546 spin_lock(&cluster->lock);
2547 if (cluster->block_group != block_group)
2548 goto out;
2549
2550 cluster->block_group = NULL;
2551 cluster->window_start = 0;
2552 list_del_init(&cluster->block_group_list);
2553
2554 node = rb_first(&cluster->root);
2555 while (node) {
2556 bool bitmap;
2557
2558 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2559 node = rb_next(&entry->offset_index);
2560 rb_erase(&entry->offset_index, &cluster->root);
2561 RB_CLEAR_NODE(&entry->offset_index);
2562
2563 bitmap = (entry->bitmap != NULL);
2564 if (!bitmap) {
2565 try_merge_free_space(ctl, entry, false);
2566 steal_from_bitmap(ctl, entry, false);
2567 }
2568 tree_insert_offset(&ctl->free_space_offset,
2569 entry->offset, &entry->offset_index, bitmap);
2570 }
2571 cluster->root = RB_ROOT;
2572
2573out:
2574 spin_unlock(&cluster->lock);
2575 btrfs_put_block_group(block_group);
2576 return 0;
2577}
2578
2579static void __btrfs_remove_free_space_cache_locked(
2580 struct btrfs_free_space_ctl *ctl)
2581{
2582 struct btrfs_free_space *info;
2583 struct rb_node *node;
2584
2585 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
2586 info = rb_entry(node, struct btrfs_free_space, offset_index);
2587 if (!info->bitmap) {
2588 unlink_free_space(ctl, info);
2589 kmem_cache_free(btrfs_free_space_cachep, info);
2590 } else {
2591 free_bitmap(ctl, info);
2592 }
2593
2594 cond_resched_lock(&ctl->tree_lock);
2595 }
2596}
2597
2598void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
2599{
2600 spin_lock(&ctl->tree_lock);
2601 __btrfs_remove_free_space_cache_locked(ctl);
2602 spin_unlock(&ctl->tree_lock);
2603}
2604
2605void btrfs_remove_free_space_cache(struct btrfs_block_group *block_group)
2606{
2607 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2608 struct btrfs_free_cluster *cluster;
2609 struct list_head *head;
2610
2611 spin_lock(&ctl->tree_lock);
2612 while ((head = block_group->cluster_list.next) !=
2613 &block_group->cluster_list) {
2614 cluster = list_entry(head, struct btrfs_free_cluster,
2615 block_group_list);
2616
2617 WARN_ON(cluster->block_group != block_group);
2618 __btrfs_return_cluster_to_free_space(block_group, cluster);
2619
2620 cond_resched_lock(&ctl->tree_lock);
2621 }
2622 __btrfs_remove_free_space_cache_locked(ctl);
2623 spin_unlock(&ctl->tree_lock);
2624
2625}
2626
2627u64 btrfs_find_space_for_alloc(struct btrfs_block_group *block_group,
2628 u64 offset, u64 bytes, u64 empty_size,
2629 u64 *max_extent_size)
2630{
2631 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2632 struct btrfs_free_space *entry = NULL;
2633 u64 bytes_search = bytes + empty_size;
2634 u64 ret = 0;
2635 u64 align_gap = 0;
2636 u64 align_gap_len = 0;
2637
2638 spin_lock(&ctl->tree_lock);
2639 entry = find_free_space(ctl, &offset, &bytes_search,
2640 block_group->full_stripe_len, max_extent_size);
2641 if (!entry)
2642 goto out;
2643
2644 ret = offset;
2645 if (entry->bitmap) {
2646 bitmap_clear_bits(ctl, entry, offset, bytes);
2647 if (!entry->bytes)
2648 free_bitmap(ctl, entry);
2649 } else {
2650 unlink_free_space(ctl, entry);
2651 align_gap_len = offset - entry->offset;
2652 align_gap = entry->offset;
2653
2654 entry->offset = offset + bytes;
2655 WARN_ON(entry->bytes < bytes + align_gap_len);
2656
2657 entry->bytes -= bytes + align_gap_len;
2658 if (!entry->bytes)
2659 kmem_cache_free(btrfs_free_space_cachep, entry);
2660 else
2661 link_free_space(ctl, entry);
2662 }
2663out:
2664 spin_unlock(&ctl->tree_lock);
2665
2666 if (align_gap_len)
2667 __btrfs_add_free_space(block_group->fs_info, ctl,
2668 align_gap, align_gap_len);
2669 return ret;
2670}
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680int btrfs_return_cluster_to_free_space(
2681 struct btrfs_block_group *block_group,
2682 struct btrfs_free_cluster *cluster)
2683{
2684 struct btrfs_free_space_ctl *ctl;
2685 int ret;
2686
2687
2688 spin_lock(&cluster->lock);
2689 if (!block_group) {
2690 block_group = cluster->block_group;
2691 if (!block_group) {
2692 spin_unlock(&cluster->lock);
2693 return 0;
2694 }
2695 } else if (cluster->block_group != block_group) {
2696
2697 spin_unlock(&cluster->lock);
2698 return 0;
2699 }
2700 atomic_inc(&block_group->count);
2701 spin_unlock(&cluster->lock);
2702
2703 ctl = block_group->free_space_ctl;
2704
2705
2706 spin_lock(&ctl->tree_lock);
2707 ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
2708 spin_unlock(&ctl->tree_lock);
2709
2710
2711 btrfs_put_block_group(block_group);
2712 return ret;
2713}
2714
2715static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group *block_group,
2716 struct btrfs_free_cluster *cluster,
2717 struct btrfs_free_space *entry,
2718 u64 bytes, u64 min_start,
2719 u64 *max_extent_size)
2720{
2721 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2722 int err;
2723 u64 search_start = cluster->window_start;
2724 u64 search_bytes = bytes;
2725 u64 ret = 0;
2726
2727 search_start = min_start;
2728 search_bytes = bytes;
2729
2730 err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);
2731 if (err) {
2732 *max_extent_size = max(get_max_extent_size(entry),
2733 *max_extent_size);
2734 return 0;
2735 }
2736
2737 ret = search_start;
2738 __bitmap_clear_bits(ctl, entry, ret, bytes);
2739
2740 return ret;
2741}
2742
2743
2744
2745
2746
2747
2748u64 btrfs_alloc_from_cluster(struct btrfs_block_group *block_group,
2749 struct btrfs_free_cluster *cluster, u64 bytes,
2750 u64 min_start, u64 *max_extent_size)
2751{
2752 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2753 struct btrfs_free_space *entry = NULL;
2754 struct rb_node *node;
2755 u64 ret = 0;
2756
2757 spin_lock(&cluster->lock);
2758 if (bytes > cluster->max_size)
2759 goto out;
2760
2761 if (cluster->block_group != block_group)
2762 goto out;
2763
2764 node = rb_first(&cluster->root);
2765 if (!node)
2766 goto out;
2767
2768 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2769 while (1) {
2770 if (entry->bytes < bytes)
2771 *max_extent_size = max(get_max_extent_size(entry),
2772 *max_extent_size);
2773
2774 if (entry->bytes < bytes ||
2775 (!entry->bitmap && entry->offset < min_start)) {
2776 node = rb_next(&entry->offset_index);
2777 if (!node)
2778 break;
2779 entry = rb_entry(node, struct btrfs_free_space,
2780 offset_index);
2781 continue;
2782 }
2783
2784 if (entry->bitmap) {
2785 ret = btrfs_alloc_from_bitmap(block_group,
2786 cluster, entry, bytes,
2787 cluster->window_start,
2788 max_extent_size);
2789 if (ret == 0) {
2790 node = rb_next(&entry->offset_index);
2791 if (!node)
2792 break;
2793 entry = rb_entry(node, struct btrfs_free_space,
2794 offset_index);
2795 continue;
2796 }
2797 cluster->window_start += bytes;
2798 } else {
2799 ret = entry->offset;
2800
2801 entry->offset += bytes;
2802 entry->bytes -= bytes;
2803 }
2804
2805 if (entry->bytes == 0)
2806 rb_erase(&entry->offset_index, &cluster->root);
2807 break;
2808 }
2809out:
2810 spin_unlock(&cluster->lock);
2811
2812 if (!ret)
2813 return 0;
2814
2815 spin_lock(&ctl->tree_lock);
2816
2817 ctl->free_space -= bytes;
2818 if (entry->bytes == 0) {
2819 ctl->free_extents--;
2820 if (entry->bitmap) {
2821 kmem_cache_free(btrfs_free_space_bitmap_cachep,
2822 entry->bitmap);
2823 ctl->total_bitmaps--;
2824 ctl->op->recalc_thresholds(ctl);
2825 }
2826 kmem_cache_free(btrfs_free_space_cachep, entry);
2827 }
2828
2829 spin_unlock(&ctl->tree_lock);
2830
2831 return ret;
2832}
2833
2834static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,
2835 struct btrfs_free_space *entry,
2836 struct btrfs_free_cluster *cluster,
2837 u64 offset, u64 bytes,
2838 u64 cont1_bytes, u64 min_bytes)
2839{
2840 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2841 unsigned long next_zero;
2842 unsigned long i;
2843 unsigned long want_bits;
2844 unsigned long min_bits;
2845 unsigned long found_bits;
2846 unsigned long max_bits = 0;
2847 unsigned long start = 0;
2848 unsigned long total_found = 0;
2849 int ret;
2850
2851 i = offset_to_bit(entry->offset, ctl->unit,
2852 max_t(u64, offset, entry->offset));
2853 want_bits = bytes_to_bits(bytes, ctl->unit);
2854 min_bits = bytes_to_bits(min_bytes, ctl->unit);
2855
2856
2857
2858
2859
2860 if (entry->max_extent_size &&
2861 entry->max_extent_size < cont1_bytes)
2862 return -ENOSPC;
2863again:
2864 found_bits = 0;
2865 for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
2866 next_zero = find_next_zero_bit(entry->bitmap,
2867 BITS_PER_BITMAP, i);
2868 if (next_zero - i >= min_bits) {
2869 found_bits = next_zero - i;
2870 if (found_bits > max_bits)
2871 max_bits = found_bits;
2872 break;
2873 }
2874 if (next_zero - i > max_bits)
2875 max_bits = next_zero - i;
2876 i = next_zero;
2877 }
2878
2879 if (!found_bits) {
2880 entry->max_extent_size = (u64)max_bits * ctl->unit;
2881 return -ENOSPC;
2882 }
2883
2884 if (!total_found) {
2885 start = i;
2886 cluster->max_size = 0;
2887 }
2888
2889 total_found += found_bits;
2890
2891 if (cluster->max_size < found_bits * ctl->unit)
2892 cluster->max_size = found_bits * ctl->unit;
2893
2894 if (total_found < want_bits || cluster->max_size < cont1_bytes) {
2895 i = next_zero + 1;
2896 goto again;
2897 }
2898
2899 cluster->window_start = start * ctl->unit + entry->offset;
2900 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2901 ret = tree_insert_offset(&cluster->root, entry->offset,
2902 &entry->offset_index, 1);
2903 ASSERT(!ret);
2904
2905 trace_btrfs_setup_cluster(block_group, cluster,
2906 total_found * ctl->unit, 1);
2907 return 0;
2908}
2909
2910
2911
2912
2913
2914
2915static noinline int
2916setup_cluster_no_bitmap(struct btrfs_block_group *block_group,
2917 struct btrfs_free_cluster *cluster,
2918 struct list_head *bitmaps, u64 offset, u64 bytes,
2919 u64 cont1_bytes, u64 min_bytes)
2920{
2921 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
2922 struct btrfs_free_space *first = NULL;
2923 struct btrfs_free_space *entry = NULL;
2924 struct btrfs_free_space *last;
2925 struct rb_node *node;
2926 u64 window_free;
2927 u64 max_extent;
2928 u64 total_size = 0;
2929
2930 entry = tree_search_offset(ctl, offset, 0, 1);
2931 if (!entry)
2932 return -ENOSPC;
2933
2934
2935
2936
2937
2938 while (entry->bitmap || entry->bytes < min_bytes) {
2939 if (entry->bitmap && list_empty(&entry->list))
2940 list_add_tail(&entry->list, bitmaps);
2941 node = rb_next(&entry->offset_index);
2942 if (!node)
2943 return -ENOSPC;
2944 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2945 }
2946
2947 window_free = entry->bytes;
2948 max_extent = entry->bytes;
2949 first = entry;
2950 last = entry;
2951
2952 for (node = rb_next(&entry->offset_index); node;
2953 node = rb_next(&entry->offset_index)) {
2954 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2955
2956 if (entry->bitmap) {
2957 if (list_empty(&entry->list))
2958 list_add_tail(&entry->list, bitmaps);
2959 continue;
2960 }
2961
2962 if (entry->bytes < min_bytes)
2963 continue;
2964
2965 last = entry;
2966 window_free += entry->bytes;
2967 if (entry->bytes > max_extent)
2968 max_extent = entry->bytes;
2969 }
2970
2971 if (window_free < bytes || max_extent < cont1_bytes)
2972 return -ENOSPC;
2973
2974 cluster->window_start = first->offset;
2975
2976 node = &first->offset_index;
2977
2978
2979
2980
2981
2982 do {
2983 int ret;
2984
2985 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2986 node = rb_next(&entry->offset_index);
2987 if (entry->bitmap || entry->bytes < min_bytes)
2988 continue;
2989
2990 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2991 ret = tree_insert_offset(&cluster->root, entry->offset,
2992 &entry->offset_index, 0);
2993 total_size += entry->bytes;
2994 ASSERT(!ret);
2995 } while (node && entry != last);
2996
2997 cluster->max_size = max_extent;
2998 trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
2999 return 0;
3000}
3001
3002
3003
3004
3005
3006static noinline int
3007setup_cluster_bitmap(struct btrfs_block_group *block_group,
3008 struct btrfs_free_cluster *cluster,
3009 struct list_head *bitmaps, u64 offset, u64 bytes,
3010 u64 cont1_bytes, u64 min_bytes)
3011{
3012 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3013 struct btrfs_free_space *entry = NULL;
3014 int ret = -ENOSPC;
3015 u64 bitmap_offset = offset_to_bitmap(ctl, offset);
3016
3017 if (ctl->total_bitmaps == 0)
3018 return -ENOSPC;
3019
3020
3021
3022
3023
3024 if (!list_empty(bitmaps))
3025 entry = list_first_entry(bitmaps, struct btrfs_free_space, list);
3026
3027 if (!entry || entry->offset != bitmap_offset) {
3028 entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
3029 if (entry && list_empty(&entry->list))
3030 list_add(&entry->list, bitmaps);
3031 }
3032
3033 list_for_each_entry(entry, bitmaps, list) {
3034 if (entry->bytes < bytes)
3035 continue;
3036 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
3037 bytes, cont1_bytes, min_bytes);
3038 if (!ret)
3039 return 0;
3040 }
3041
3042
3043
3044
3045
3046 return -ENOSPC;
3047}
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057int btrfs_find_space_cluster(struct btrfs_block_group *block_group,
3058 struct btrfs_free_cluster *cluster,
3059 u64 offset, u64 bytes, u64 empty_size)
3060{
3061 struct btrfs_fs_info *fs_info = block_group->fs_info;
3062 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3063 struct btrfs_free_space *entry, *tmp;
3064 LIST_HEAD(bitmaps);
3065 u64 min_bytes;
3066 u64 cont1_bytes;
3067 int ret;
3068
3069
3070
3071
3072
3073
3074
3075 if (btrfs_test_opt(fs_info, SSD_SPREAD)) {
3076 cont1_bytes = min_bytes = bytes + empty_size;
3077 } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
3078 cont1_bytes = bytes;
3079 min_bytes = fs_info->sectorsize;
3080 } else {
3081 cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
3082 min_bytes = fs_info->sectorsize;
3083 }
3084
3085 spin_lock(&ctl->tree_lock);
3086
3087
3088
3089
3090
3091 if (ctl->free_space < bytes) {
3092 spin_unlock(&ctl->tree_lock);
3093 return -ENOSPC;
3094 }
3095
3096 spin_lock(&cluster->lock);
3097
3098
3099 if (cluster->block_group) {
3100 ret = 0;
3101 goto out;
3102 }
3103
3104 trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
3105 min_bytes);
3106
3107 ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
3108 bytes + empty_size,
3109 cont1_bytes, min_bytes);
3110 if (ret)
3111 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
3112 offset, bytes + empty_size,
3113 cont1_bytes, min_bytes);
3114
3115
3116 list_for_each_entry_safe(entry, tmp, &bitmaps, list)
3117 list_del_init(&entry->list);
3118
3119 if (!ret) {
3120 atomic_inc(&block_group->count);
3121 list_add_tail(&cluster->block_group_list,
3122 &block_group->cluster_list);
3123 cluster->block_group = block_group;
3124 } else {
3125 trace_btrfs_failed_cluster_setup(block_group);
3126 }
3127out:
3128 spin_unlock(&cluster->lock);
3129 spin_unlock(&ctl->tree_lock);
3130
3131 return ret;
3132}
3133
3134
3135
3136
3137void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
3138{
3139 spin_lock_init(&cluster->lock);
3140 spin_lock_init(&cluster->refill_lock);
3141 cluster->root = RB_ROOT;
3142 cluster->max_size = 0;
3143 cluster->fragmented = false;
3144 INIT_LIST_HEAD(&cluster->block_group_list);
3145 cluster->block_group = NULL;
3146}
3147
3148static int do_trimming(struct btrfs_block_group *block_group,
3149 u64 *total_trimmed, u64 start, u64 bytes,
3150 u64 reserved_start, u64 reserved_bytes,
3151 struct btrfs_trim_range *trim_entry)
3152{
3153 struct btrfs_space_info *space_info = block_group->space_info;
3154 struct btrfs_fs_info *fs_info = block_group->fs_info;
3155 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3156 int ret;
3157 int update = 0;
3158 u64 trimmed = 0;
3159
3160 spin_lock(&space_info->lock);
3161 spin_lock(&block_group->lock);
3162 if (!block_group->ro) {
3163 block_group->reserved += reserved_bytes;
3164 space_info->bytes_reserved += reserved_bytes;
3165 update = 1;
3166 }
3167 spin_unlock(&block_group->lock);
3168 spin_unlock(&space_info->lock);
3169
3170 ret = btrfs_discard_extent(fs_info, start, bytes, &trimmed);
3171 if (!ret)
3172 *total_trimmed += trimmed;
3173
3174 mutex_lock(&ctl->cache_writeout_mutex);
3175 btrfs_add_free_space(block_group, reserved_start, reserved_bytes);
3176 list_del(&trim_entry->list);
3177 mutex_unlock(&ctl->cache_writeout_mutex);
3178
3179 if (update) {
3180 spin_lock(&space_info->lock);
3181 spin_lock(&block_group->lock);
3182 if (block_group->ro)
3183 space_info->bytes_readonly += reserved_bytes;
3184 block_group->reserved -= reserved_bytes;
3185 space_info->bytes_reserved -= reserved_bytes;
3186 spin_unlock(&block_group->lock);
3187 spin_unlock(&space_info->lock);
3188 }
3189
3190 return ret;
3191}
3192
3193static int trim_no_bitmap(struct btrfs_block_group *block_group,
3194 u64 *total_trimmed, u64 start, u64 end, u64 minlen)
3195{
3196 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3197 struct btrfs_free_space *entry;
3198 struct rb_node *node;
3199 int ret = 0;
3200 u64 extent_start;
3201 u64 extent_bytes;
3202 u64 bytes;
3203
3204 while (start < end) {
3205 struct btrfs_trim_range trim_entry;
3206
3207 mutex_lock(&ctl->cache_writeout_mutex);
3208 spin_lock(&ctl->tree_lock);
3209
3210 if (ctl->free_space < minlen) {
3211 spin_unlock(&ctl->tree_lock);
3212 mutex_unlock(&ctl->cache_writeout_mutex);
3213 break;
3214 }
3215
3216 entry = tree_search_offset(ctl, start, 0, 1);
3217 if (!entry) {
3218 spin_unlock(&ctl->tree_lock);
3219 mutex_unlock(&ctl->cache_writeout_mutex);
3220 break;
3221 }
3222
3223
3224 while (entry->bitmap) {
3225 node = rb_next(&entry->offset_index);
3226 if (!node) {
3227 spin_unlock(&ctl->tree_lock);
3228 mutex_unlock(&ctl->cache_writeout_mutex);
3229 goto out;
3230 }
3231 entry = rb_entry(node, struct btrfs_free_space,
3232 offset_index);
3233 }
3234
3235 if (entry->offset >= end) {
3236 spin_unlock(&ctl->tree_lock);
3237 mutex_unlock(&ctl->cache_writeout_mutex);
3238 break;
3239 }
3240
3241 extent_start = entry->offset;
3242 extent_bytes = entry->bytes;
3243 start = max(start, extent_start);
3244 bytes = min(extent_start + extent_bytes, end) - start;
3245 if (bytes < minlen) {
3246 spin_unlock(&ctl->tree_lock);
3247 mutex_unlock(&ctl->cache_writeout_mutex);
3248 goto next;
3249 }
3250
3251 unlink_free_space(ctl, entry);
3252 kmem_cache_free(btrfs_free_space_cachep, entry);
3253
3254 spin_unlock(&ctl->tree_lock);
3255 trim_entry.start = extent_start;
3256 trim_entry.bytes = extent_bytes;
3257 list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
3258 mutex_unlock(&ctl->cache_writeout_mutex);
3259
3260 ret = do_trimming(block_group, total_trimmed, start, bytes,
3261 extent_start, extent_bytes, &trim_entry);
3262 if (ret)
3263 break;
3264next:
3265 start += bytes;
3266
3267 if (fatal_signal_pending(current)) {
3268 ret = -ERESTARTSYS;
3269 break;
3270 }
3271
3272 cond_resched();
3273 }
3274out:
3275 return ret;
3276}
3277
3278static int trim_bitmaps(struct btrfs_block_group *block_group,
3279 u64 *total_trimmed, u64 start, u64 end, u64 minlen)
3280{
3281 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3282 struct btrfs_free_space *entry;
3283 int ret = 0;
3284 int ret2;
3285 u64 bytes;
3286 u64 offset = offset_to_bitmap(ctl, start);
3287
3288 while (offset < end) {
3289 bool next_bitmap = false;
3290 struct btrfs_trim_range trim_entry;
3291
3292 mutex_lock(&ctl->cache_writeout_mutex);
3293 spin_lock(&ctl->tree_lock);
3294
3295 if (ctl->free_space < minlen) {
3296 spin_unlock(&ctl->tree_lock);
3297 mutex_unlock(&ctl->cache_writeout_mutex);
3298 break;
3299 }
3300
3301 entry = tree_search_offset(ctl, offset, 1, 0);
3302 if (!entry) {
3303 spin_unlock(&ctl->tree_lock);
3304 mutex_unlock(&ctl->cache_writeout_mutex);
3305 next_bitmap = true;
3306 goto next;
3307 }
3308
3309 bytes = minlen;
3310 ret2 = search_bitmap(ctl, entry, &start, &bytes, false);
3311 if (ret2 || start >= end) {
3312 spin_unlock(&ctl->tree_lock);
3313 mutex_unlock(&ctl->cache_writeout_mutex);
3314 next_bitmap = true;
3315 goto next;
3316 }
3317
3318 bytes = min(bytes, end - start);
3319 if (bytes < minlen) {
3320 spin_unlock(&ctl->tree_lock);
3321 mutex_unlock(&ctl->cache_writeout_mutex);
3322 goto next;
3323 }
3324
3325 bitmap_clear_bits(ctl, entry, start, bytes);
3326 if (entry->bytes == 0)
3327 free_bitmap(ctl, entry);
3328
3329 spin_unlock(&ctl->tree_lock);
3330 trim_entry.start = start;
3331 trim_entry.bytes = bytes;
3332 list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
3333 mutex_unlock(&ctl->cache_writeout_mutex);
3334
3335 ret = do_trimming(block_group, total_trimmed, start, bytes,
3336 start, bytes, &trim_entry);
3337 if (ret)
3338 break;
3339next:
3340 if (next_bitmap) {
3341 offset += BITS_PER_BITMAP * ctl->unit;
3342 } else {
3343 start += bytes;
3344 if (start >= offset + BITS_PER_BITMAP * ctl->unit)
3345 offset += BITS_PER_BITMAP * ctl->unit;
3346 }
3347
3348 if (fatal_signal_pending(current)) {
3349 ret = -ERESTARTSYS;
3350 break;
3351 }
3352
3353 cond_resched();
3354 }
3355
3356 return ret;
3357}
3358
3359void btrfs_get_block_group_trimming(struct btrfs_block_group *cache)
3360{
3361 atomic_inc(&cache->trimming);
3362}
3363
3364void btrfs_put_block_group_trimming(struct btrfs_block_group *block_group)
3365{
3366 struct btrfs_fs_info *fs_info = block_group->fs_info;
3367 struct extent_map_tree *em_tree;
3368 struct extent_map *em;
3369 bool cleanup;
3370
3371 spin_lock(&block_group->lock);
3372 cleanup = (atomic_dec_and_test(&block_group->trimming) &&
3373 block_group->removed);
3374 spin_unlock(&block_group->lock);
3375
3376 if (cleanup) {
3377 mutex_lock(&fs_info->chunk_mutex);
3378 em_tree = &fs_info->mapping_tree;
3379 write_lock(&em_tree->lock);
3380 em = lookup_extent_mapping(em_tree, block_group->start,
3381 1);
3382 BUG_ON(!em);
3383 remove_extent_mapping(em_tree, em);
3384 write_unlock(&em_tree->lock);
3385 mutex_unlock(&fs_info->chunk_mutex);
3386
3387
3388 free_extent_map(em);
3389 free_extent_map(em);
3390
3391
3392
3393
3394
3395 __btrfs_remove_free_space_cache(block_group->free_space_ctl);
3396 }
3397}
3398
3399int btrfs_trim_block_group(struct btrfs_block_group *block_group,
3400 u64 *trimmed, u64 start, u64 end, u64 minlen)
3401{
3402 int ret;
3403
3404 *trimmed = 0;
3405
3406 spin_lock(&block_group->lock);
3407 if (block_group->removed) {
3408 spin_unlock(&block_group->lock);
3409 return 0;
3410 }
3411 btrfs_get_block_group_trimming(block_group);
3412 spin_unlock(&block_group->lock);
3413
3414 ret = trim_no_bitmap(block_group, trimmed, start, end, minlen);
3415 if (ret)
3416 goto out;
3417
3418 ret = trim_bitmaps(block_group, trimmed, start, end, minlen);
3419out:
3420 btrfs_put_block_group_trimming(block_group);
3421 return ret;
3422}
3423
3424
3425
3426
3427
3428
3429
3430
3431u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
3432{
3433 struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
3434 struct btrfs_free_space *entry = NULL;
3435 u64 ino = 0;
3436
3437 spin_lock(&ctl->tree_lock);
3438
3439 if (RB_EMPTY_ROOT(&ctl->free_space_offset))
3440 goto out;
3441
3442 entry = rb_entry(rb_first(&ctl->free_space_offset),
3443 struct btrfs_free_space, offset_index);
3444
3445 if (!entry->bitmap) {
3446 ino = entry->offset;
3447
3448 unlink_free_space(ctl, entry);
3449 entry->offset++;
3450 entry->bytes--;
3451 if (!entry->bytes)
3452 kmem_cache_free(btrfs_free_space_cachep, entry);
3453 else
3454 link_free_space(ctl, entry);
3455 } else {
3456 u64 offset = 0;
3457 u64 count = 1;
3458 int ret;
3459
3460 ret = search_bitmap(ctl, entry, &offset, &count, true);
3461
3462 ASSERT(!ret);
3463
3464 ino = offset;
3465 bitmap_clear_bits(ctl, entry, offset, 1);
3466 if (entry->bytes == 0)
3467 free_bitmap(ctl, entry);
3468 }
3469out:
3470 spin_unlock(&ctl->tree_lock);
3471
3472 return ino;
3473}
3474
3475struct inode *lookup_free_ino_inode(struct btrfs_root *root,
3476 struct btrfs_path *path)
3477{
3478 struct inode *inode = NULL;
3479
3480 spin_lock(&root->ino_cache_lock);
3481 if (root->ino_cache_inode)
3482 inode = igrab(root->ino_cache_inode);
3483 spin_unlock(&root->ino_cache_lock);
3484 if (inode)
3485 return inode;
3486
3487 inode = __lookup_free_space_inode(root, path, 0);
3488 if (IS_ERR(inode))
3489 return inode;
3490
3491 spin_lock(&root->ino_cache_lock);
3492 if (!btrfs_fs_closing(root->fs_info))
3493 root->ino_cache_inode = igrab(inode);
3494 spin_unlock(&root->ino_cache_lock);
3495
3496 return inode;
3497}
3498
3499int create_free_ino_inode(struct btrfs_root *root,
3500 struct btrfs_trans_handle *trans,
3501 struct btrfs_path *path)
3502{
3503 return __create_free_space_inode(root, trans, path,
3504 BTRFS_FREE_INO_OBJECTID, 0);
3505}
3506
3507int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
3508{
3509 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
3510 struct btrfs_path *path;
3511 struct inode *inode;
3512 int ret = 0;
3513 u64 root_gen = btrfs_root_generation(&root->root_item);
3514
3515 if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
3516 return 0;
3517
3518
3519
3520
3521
3522 if (btrfs_fs_closing(fs_info))
3523 return 0;
3524
3525 path = btrfs_alloc_path();
3526 if (!path)
3527 return 0;
3528
3529 inode = lookup_free_ino_inode(root, path);
3530 if (IS_ERR(inode))
3531 goto out;
3532
3533 if (root_gen != BTRFS_I(inode)->generation)
3534 goto out_put;
3535
3536 ret = __load_free_space_cache(root, inode, ctl, path, 0);
3537
3538 if (ret < 0)
3539 btrfs_err(fs_info,
3540 "failed to load free ino cache for root %llu",
3541 root->root_key.objectid);
3542out_put:
3543 iput(inode);
3544out:
3545 btrfs_free_path(path);
3546 return ret;
3547}
3548
3549int btrfs_write_out_ino_cache(struct btrfs_root *root,
3550 struct btrfs_trans_handle *trans,
3551 struct btrfs_path *path,
3552 struct inode *inode)
3553{
3554 struct btrfs_fs_info *fs_info = root->fs_info;
3555 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
3556 int ret;
3557 struct btrfs_io_ctl io_ctl;
3558 bool release_metadata = true;
3559
3560 if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
3561 return 0;
3562
3563 memset(&io_ctl, 0, sizeof(io_ctl));
3564 ret = __btrfs_write_out_cache(root, inode, ctl, NULL, &io_ctl, trans);
3565 if (!ret) {
3566
3567
3568
3569
3570
3571
3572 release_metadata = false;
3573 ret = btrfs_wait_cache_io_root(root, trans, &io_ctl, path);
3574 }
3575
3576 if (ret) {
3577 if (release_metadata)
3578 btrfs_delalloc_release_metadata(BTRFS_I(inode),
3579 inode->i_size, true);
3580#ifdef DEBUG
3581 btrfs_err(fs_info,
3582 "failed to write free ino cache for root %llu",
3583 root->root_key.objectid);
3584#endif
3585 }
3586
3587 return ret;
3588}
3589
3590#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
3591
3592
3593
3594
3595
3596
3597int test_add_free_space_entry(struct btrfs_block_group *cache,
3598 u64 offset, u64 bytes, bool bitmap)
3599{
3600 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3601 struct btrfs_free_space *info = NULL, *bitmap_info;
3602 void *map = NULL;
3603 u64 bytes_added;
3604 int ret;
3605
3606again:
3607 if (!info) {
3608 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
3609 if (!info)
3610 return -ENOMEM;
3611 }
3612
3613 if (!bitmap) {
3614 spin_lock(&ctl->tree_lock);
3615 info->offset = offset;
3616 info->bytes = bytes;
3617 info->max_extent_size = 0;
3618 ret = link_free_space(ctl, info);
3619 spin_unlock(&ctl->tree_lock);
3620 if (ret)
3621 kmem_cache_free(btrfs_free_space_cachep, info);
3622 return ret;
3623 }
3624
3625 if (!map) {
3626 map = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep, GFP_NOFS);
3627 if (!map) {
3628 kmem_cache_free(btrfs_free_space_cachep, info);
3629 return -ENOMEM;
3630 }
3631 }
3632
3633 spin_lock(&ctl->tree_lock);
3634 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3635 1, 0);
3636 if (!bitmap_info) {
3637 info->bitmap = map;
3638 map = NULL;
3639 add_new_bitmap(ctl, info, offset);
3640 bitmap_info = info;
3641 info = NULL;
3642 }
3643
3644 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3645
3646 bytes -= bytes_added;
3647 offset += bytes_added;
3648 spin_unlock(&ctl->tree_lock);
3649
3650 if (bytes)
3651 goto again;
3652
3653 if (info)
3654 kmem_cache_free(btrfs_free_space_cachep, info);
3655 if (map)
3656 kmem_cache_free(btrfs_free_space_bitmap_cachep, map);
3657 return 0;
3658}
3659
3660
3661
3662
3663
3664
3665int test_check_exists(struct btrfs_block_group *cache,
3666 u64 offset, u64 bytes)
3667{
3668 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3669 struct btrfs_free_space *info;
3670 int ret = 0;
3671
3672 spin_lock(&ctl->tree_lock);
3673 info = tree_search_offset(ctl, offset, 0, 0);
3674 if (!info) {
3675 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3676 1, 0);
3677 if (!info)
3678 goto out;
3679 }
3680
3681have_info:
3682 if (info->bitmap) {
3683 u64 bit_off, bit_bytes;
3684 struct rb_node *n;
3685 struct btrfs_free_space *tmp;
3686
3687 bit_off = offset;
3688 bit_bytes = ctl->unit;
3689 ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);
3690 if (!ret) {
3691 if (bit_off == offset) {
3692 ret = 1;
3693 goto out;
3694 } else if (bit_off > offset &&
3695 offset + bytes > bit_off) {
3696 ret = 1;
3697 goto out;
3698 }
3699 }
3700
3701 n = rb_prev(&info->offset_index);
3702 while (n) {
3703 tmp = rb_entry(n, struct btrfs_free_space,
3704 offset_index);
3705 if (tmp->offset + tmp->bytes < offset)
3706 break;
3707 if (offset + bytes < tmp->offset) {
3708 n = rb_prev(&tmp->offset_index);
3709 continue;
3710 }
3711 info = tmp;
3712 goto have_info;
3713 }
3714
3715 n = rb_next(&info->offset_index);
3716 while (n) {
3717 tmp = rb_entry(n, struct btrfs_free_space,
3718 offset_index);
3719 if (offset + bytes < tmp->offset)
3720 break;
3721 if (tmp->offset + tmp->bytes < offset) {
3722 n = rb_next(&tmp->offset_index);
3723 continue;
3724 }
3725 info = tmp;
3726 goto have_info;
3727 }
3728
3729 ret = 0;
3730 goto out;
3731 }
3732
3733 if (info->offset == offset) {
3734 ret = 1;
3735 goto out;
3736 }
3737
3738 if (offset > info->offset && offset < info->offset + info->bytes)
3739 ret = 1;
3740out:
3741 spin_unlock(&ctl->tree_lock);
3742 return ret;
3743}
3744#endif
3745