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