blob: d6c03f7f136b359c534668a38f9e9a72d299eb66 [file] [log] [blame]
Josef Bacik0f9dd462008-09-23 13:14:11 -04001/*
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
Josef Bacik96303082009-07-13 21:29:25 -040019#include <linux/pagemap.h>
Josef Bacik0f9dd462008-09-23 13:14:11 -040020#include <linux/sched.h>
Tejun Heo5a0e3ad2010-03-24 17:04:11 +090021#include <linux/slab.h>
Josef Bacik96303082009-07-13 21:29:25 -040022#include <linux/math64.h>
Josef Bacik6ab60602011-08-08 08:24:46 -040023#include <linux/ratelimit.h>
Josef Bacik0f9dd462008-09-23 13:14:11 -040024#include "ctree.h"
Chris Masonfa9c0d792009-04-03 09:47:43 -040025#include "free-space-cache.h"
26#include "transaction.h"
Josef Bacik0af3d002010-06-21 14:48:16 -040027#include "disk-io.h"
Josef Bacik43be2142011-04-01 14:55:00 +000028#include "extent_io.h"
Li Zefan581bb052011-04-20 10:06:11 +080029#include "inode-map.h"
Filipe Manana04216822014-11-27 21:14:15 +000030#include "volumes.h"
Chris Masonfa9c0d792009-04-03 09:47:43 -040031
Josef Bacik96303082009-07-13 21:29:25 -040032#define BITS_PER_BITMAP (PAGE_CACHE_SIZE * 8)
33#define MAX_CACHE_BYTES_PER_GIG (32 * 1024)
34
Filipe Manana55507ce2014-12-01 17:04:09 +000035struct btrfs_trim_range {
36 u64 start;
37 u64 bytes;
38 struct list_head list;
39};
40
Li Zefan34d52cb2011-03-29 13:46:06 +080041static int link_free_space(struct btrfs_free_space_ctl *ctl,
Josef Bacik0cb59c92010-07-02 12:14:14 -040042 struct btrfs_free_space *info);
Josef Bacikcd023e72012-05-14 10:06:40 -040043static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
44 struct btrfs_free_space *info);
Josef Bacik0cb59c92010-07-02 12:14:14 -040045
Li Zefan0414efa2011-04-20 10:20:14 +080046static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
47 struct btrfs_path *path,
48 u64 offset)
Josef Bacik0af3d002010-06-21 14:48:16 -040049{
50 struct btrfs_key key;
51 struct btrfs_key location;
52 struct btrfs_disk_key disk_key;
53 struct btrfs_free_space_header *header;
54 struct extent_buffer *leaf;
55 struct inode *inode = NULL;
56 int ret;
57
Josef Bacik0af3d002010-06-21 14:48:16 -040058 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
Li Zefan0414efa2011-04-20 10:20:14 +080059 key.offset = offset;
Josef Bacik0af3d002010-06-21 14:48:16 -040060 key.type = 0;
61
62 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
63 if (ret < 0)
64 return ERR_PTR(ret);
65 if (ret > 0) {
David Sterbab3b4aa72011-04-21 01:20:15 +020066 btrfs_release_path(path);
Josef Bacik0af3d002010-06-21 14:48:16 -040067 return ERR_PTR(-ENOENT);
68 }
69
70 leaf = path->nodes[0];
71 header = btrfs_item_ptr(leaf, path->slots[0],
72 struct btrfs_free_space_header);
73 btrfs_free_space_key(leaf, header, &disk_key);
74 btrfs_disk_key_to_cpu(&location, &disk_key);
David Sterbab3b4aa72011-04-21 01:20:15 +020075 btrfs_release_path(path);
Josef Bacik0af3d002010-06-21 14:48:16 -040076
77 inode = btrfs_iget(root->fs_info->sb, &location, root, NULL);
78 if (!inode)
79 return ERR_PTR(-ENOENT);
80 if (IS_ERR(inode))
81 return inode;
82 if (is_bad_inode(inode)) {
83 iput(inode);
84 return ERR_PTR(-ENOENT);
85 }
86
Al Viro528c0322012-04-13 11:03:55 -040087 mapping_set_gfp_mask(inode->i_mapping,
88 mapping_gfp_mask(inode->i_mapping) & ~__GFP_FS);
Miao Xieadae52b2011-03-31 09:43:23 +000089
Li Zefan0414efa2011-04-20 10:20:14 +080090 return inode;
91}
92
93struct inode *lookup_free_space_inode(struct btrfs_root *root,
94 struct btrfs_block_group_cache
95 *block_group, struct btrfs_path *path)
96{
97 struct inode *inode = NULL;
Josef Bacik5b0e95b2011-10-06 08:58:24 -040098 u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
Li Zefan0414efa2011-04-20 10:20:14 +080099
100 spin_lock(&block_group->lock);
101 if (block_group->inode)
102 inode = igrab(block_group->inode);
103 spin_unlock(&block_group->lock);
104 if (inode)
105 return inode;
106
107 inode = __lookup_free_space_inode(root, path,
108 block_group->key.objectid);
109 if (IS_ERR(inode))
110 return inode;
111
Josef Bacik0af3d002010-06-21 14:48:16 -0400112 spin_lock(&block_group->lock);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400113 if (!((BTRFS_I(inode)->flags & flags) == flags)) {
Simon Kirbyc2cf52e2013-03-19 22:41:23 +0000114 btrfs_info(root->fs_info,
115 "Old style space inode found, converting.");
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400116 BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
117 BTRFS_INODE_NODATACOW;
Josef Bacik2f356122011-06-10 15:31:13 -0400118 block_group->disk_cache_state = BTRFS_DC_CLEAR;
119 }
120
Josef Bacik300e4f82011-08-29 14:06:00 -0400121 if (!block_group->iref) {
Josef Bacik0af3d002010-06-21 14:48:16 -0400122 block_group->inode = igrab(inode);
123 block_group->iref = 1;
124 }
125 spin_unlock(&block_group->lock);
126
127 return inode;
128}
129
Eric Sandeen48a3b632013-04-25 20:41:01 +0000130static int __create_free_space_inode(struct btrfs_root *root,
131 struct btrfs_trans_handle *trans,
132 struct btrfs_path *path,
133 u64 ino, u64 offset)
Josef Bacik0af3d002010-06-21 14:48:16 -0400134{
135 struct btrfs_key key;
136 struct btrfs_disk_key disk_key;
137 struct btrfs_free_space_header *header;
138 struct btrfs_inode_item *inode_item;
139 struct extent_buffer *leaf;
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400140 u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;
Josef Bacik0af3d002010-06-21 14:48:16 -0400141 int ret;
142
Li Zefan0414efa2011-04-20 10:20:14 +0800143 ret = btrfs_insert_empty_inode(trans, root, path, ino);
Josef Bacik0af3d002010-06-21 14:48:16 -0400144 if (ret)
145 return ret;
146
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400147 /* We inline crc's for the free disk space cache */
148 if (ino != BTRFS_FREE_INO_OBJECTID)
149 flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
150
Josef Bacik0af3d002010-06-21 14:48:16 -0400151 leaf = path->nodes[0];
152 inode_item = btrfs_item_ptr(leaf, path->slots[0],
153 struct btrfs_inode_item);
154 btrfs_item_key(leaf, &disk_key, path->slots[0]);
155 memset_extent_buffer(leaf, 0, (unsigned long)inode_item,
156 sizeof(*inode_item));
157 btrfs_set_inode_generation(leaf, inode_item, trans->transid);
158 btrfs_set_inode_size(leaf, inode_item, 0);
159 btrfs_set_inode_nbytes(leaf, inode_item, 0);
160 btrfs_set_inode_uid(leaf, inode_item, 0);
161 btrfs_set_inode_gid(leaf, inode_item, 0);
162 btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400163 btrfs_set_inode_flags(leaf, inode_item, flags);
Josef Bacik0af3d002010-06-21 14:48:16 -0400164 btrfs_set_inode_nlink(leaf, inode_item, 1);
165 btrfs_set_inode_transid(leaf, inode_item, trans->transid);
Li Zefan0414efa2011-04-20 10:20:14 +0800166 btrfs_set_inode_block_group(leaf, inode_item, offset);
Josef Bacik0af3d002010-06-21 14:48:16 -0400167 btrfs_mark_buffer_dirty(leaf);
David Sterbab3b4aa72011-04-21 01:20:15 +0200168 btrfs_release_path(path);
Josef Bacik0af3d002010-06-21 14:48:16 -0400169
170 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
Li Zefan0414efa2011-04-20 10:20:14 +0800171 key.offset = offset;
Josef Bacik0af3d002010-06-21 14:48:16 -0400172 key.type = 0;
173
174 ret = btrfs_insert_empty_item(trans, root, path, &key,
175 sizeof(struct btrfs_free_space_header));
176 if (ret < 0) {
David Sterbab3b4aa72011-04-21 01:20:15 +0200177 btrfs_release_path(path);
Josef Bacik0af3d002010-06-21 14:48:16 -0400178 return ret;
179 }
180 leaf = path->nodes[0];
181 header = btrfs_item_ptr(leaf, path->slots[0],
182 struct btrfs_free_space_header);
183 memset_extent_buffer(leaf, 0, (unsigned long)header, sizeof(*header));
184 btrfs_set_free_space_key(leaf, header, &disk_key);
185 btrfs_mark_buffer_dirty(leaf);
David Sterbab3b4aa72011-04-21 01:20:15 +0200186 btrfs_release_path(path);
Josef Bacik0af3d002010-06-21 14:48:16 -0400187
188 return 0;
189}
190
Li Zefan0414efa2011-04-20 10:20:14 +0800191int create_free_space_inode(struct btrfs_root *root,
192 struct btrfs_trans_handle *trans,
193 struct btrfs_block_group_cache *block_group,
194 struct btrfs_path *path)
195{
196 int ret;
197 u64 ino;
198
199 ret = btrfs_find_free_objectid(root, &ino);
200 if (ret < 0)
201 return ret;
202
203 return __create_free_space_inode(root, trans, path, ino,
204 block_group->key.objectid);
205}
206
Miao Xie7b61cd92013-05-13 13:55:09 +0000207int btrfs_check_trunc_cache_free_space(struct btrfs_root *root,
208 struct btrfs_block_rsv *rsv)
Josef Bacik0af3d002010-06-21 14:48:16 -0400209{
Josef Bacikc8174312011-11-02 09:29:35 -0400210 u64 needed_bytes;
Miao Xie7b61cd92013-05-13 13:55:09 +0000211 int ret;
Josef Bacikc8174312011-11-02 09:29:35 -0400212
213 /* 1 for slack space, 1 for updating the inode */
214 needed_bytes = btrfs_calc_trunc_metadata_size(root, 1) +
215 btrfs_calc_trans_metadata_size(root, 1);
216
Miao Xie7b61cd92013-05-13 13:55:09 +0000217 spin_lock(&rsv->lock);
218 if (rsv->reserved < needed_bytes)
219 ret = -ENOSPC;
220 else
221 ret = 0;
222 spin_unlock(&rsv->lock);
Wei Yongjun4b286cd2013-05-21 02:39:21 +0000223 return ret;
Miao Xie7b61cd92013-05-13 13:55:09 +0000224}
225
226int btrfs_truncate_free_space_cache(struct btrfs_root *root,
227 struct btrfs_trans_handle *trans,
Miao Xie7b61cd92013-05-13 13:55:09 +0000228 struct inode *inode)
229{
Miao Xie7b61cd92013-05-13 13:55:09 +0000230 int ret = 0;
Josef Bacik0af3d002010-06-21 14:48:16 -0400231
Josef Bacik0af3d002010-06-21 14:48:16 -0400232 btrfs_i_size_write(inode, 0);
Kirill A. Shutemov7caef262013-09-12 15:13:56 -0700233 truncate_pagecache(inode, 0);
Josef Bacik0af3d002010-06-21 14:48:16 -0400234
235 /*
236 * We don't need an orphan item because truncating the free space cache
237 * will never be split across transactions.
238 */
239 ret = btrfs_truncate_inode_items(trans, root, inode,
240 0, BTRFS_EXTENT_DATA_KEY);
241 if (ret) {
Jeff Mahoney79787ea2012-03-12 16:03:00 +0100242 btrfs_abort_transaction(trans, root, ret);
Josef Bacik0af3d002010-06-21 14:48:16 -0400243 return ret;
244 }
245
Li Zefan82d59022011-04-20 10:33:24 +0800246 ret = btrfs_update_inode(trans, root, inode);
Jeff Mahoney79787ea2012-03-12 16:03:00 +0100247 if (ret)
248 btrfs_abort_transaction(trans, root, ret);
Josef Bacikc8174312011-11-02 09:29:35 -0400249
Li Zefan82d59022011-04-20 10:33:24 +0800250 return ret;
Josef Bacik0af3d002010-06-21 14:48:16 -0400251}
252
Josef Bacik9d66e232010-08-25 16:54:15 -0400253static int readahead_cache(struct inode *inode)
254{
255 struct file_ra_state *ra;
256 unsigned long last_index;
257
258 ra = kzalloc(sizeof(*ra), GFP_NOFS);
259 if (!ra)
260 return -ENOMEM;
261
262 file_ra_state_init(ra, inode->i_mapping);
263 last_index = (i_size_read(inode) - 1) >> PAGE_CACHE_SHIFT;
264
265 page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);
266
267 kfree(ra);
268
269 return 0;
270}
271
Josef Bacika67509c2011-10-05 15:18:58 -0400272struct io_ctl {
273 void *cur, *orig;
274 struct page *page;
275 struct page **pages;
276 struct btrfs_root *root;
277 unsigned long size;
278 int index;
279 int num_pages;
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400280 unsigned check_crcs:1;
Josef Bacika67509c2011-10-05 15:18:58 -0400281};
282
283static int io_ctl_init(struct io_ctl *io_ctl, struct inode *inode,
Miao Xie5349d6c2014-06-19 10:42:49 +0800284 struct btrfs_root *root, int write)
Josef Bacika67509c2011-10-05 15:18:58 -0400285{
Miao Xie5349d6c2014-06-19 10:42:49 +0800286 int num_pages;
287 int check_crcs = 0;
288
David Sterbaed6078f2014-06-05 01:59:57 +0200289 num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_CACHE_SIZE);
Miao Xie5349d6c2014-06-19 10:42:49 +0800290
291 if (btrfs_ino(inode) != BTRFS_FREE_INO_OBJECTID)
292 check_crcs = 1;
293
294 /* Make sure we can fit our crcs into the first page */
295 if (write && check_crcs &&
296 (num_pages * sizeof(u32)) >= PAGE_CACHE_SIZE)
297 return -ENOSPC;
298
Josef Bacika67509c2011-10-05 15:18:58 -0400299 memset(io_ctl, 0, sizeof(struct io_ctl));
Miao Xie5349d6c2014-06-19 10:42:49 +0800300
301 io_ctl->pages = kzalloc(sizeof(struct page *) * num_pages, GFP_NOFS);
Josef Bacika67509c2011-10-05 15:18:58 -0400302 if (!io_ctl->pages)
303 return -ENOMEM;
Miao Xie5349d6c2014-06-19 10:42:49 +0800304
305 io_ctl->num_pages = num_pages;
Josef Bacika67509c2011-10-05 15:18:58 -0400306 io_ctl->root = root;
Miao Xie5349d6c2014-06-19 10:42:49 +0800307 io_ctl->check_crcs = check_crcs;
308
Josef Bacika67509c2011-10-05 15:18:58 -0400309 return 0;
310}
311
312static void io_ctl_free(struct io_ctl *io_ctl)
313{
314 kfree(io_ctl->pages);
315}
316
317static void io_ctl_unmap_page(struct io_ctl *io_ctl)
318{
319 if (io_ctl->cur) {
320 kunmap(io_ctl->page);
321 io_ctl->cur = NULL;
322 io_ctl->orig = NULL;
323 }
324}
325
326static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
327{
Josef Bacikb12d6862013-08-26 17:14:08 -0400328 ASSERT(io_ctl->index < io_ctl->num_pages);
Josef Bacika67509c2011-10-05 15:18:58 -0400329 io_ctl->page = io_ctl->pages[io_ctl->index++];
330 io_ctl->cur = kmap(io_ctl->page);
331 io_ctl->orig = io_ctl->cur;
332 io_ctl->size = PAGE_CACHE_SIZE;
333 if (clear)
334 memset(io_ctl->cur, 0, PAGE_CACHE_SIZE);
335}
336
337static void io_ctl_drop_pages(struct io_ctl *io_ctl)
338{
339 int i;
340
341 io_ctl_unmap_page(io_ctl);
342
343 for (i = 0; i < io_ctl->num_pages; i++) {
Li Zefana1ee5a42012-01-09 14:27:42 +0800344 if (io_ctl->pages[i]) {
345 ClearPageChecked(io_ctl->pages[i]);
346 unlock_page(io_ctl->pages[i]);
347 page_cache_release(io_ctl->pages[i]);
348 }
Josef Bacika67509c2011-10-05 15:18:58 -0400349 }
350}
351
352static int io_ctl_prepare_pages(struct io_ctl *io_ctl, struct inode *inode,
353 int uptodate)
354{
355 struct page *page;
356 gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
357 int i;
358
359 for (i = 0; i < io_ctl->num_pages; i++) {
360 page = find_or_create_page(inode->i_mapping, i, mask);
361 if (!page) {
362 io_ctl_drop_pages(io_ctl);
363 return -ENOMEM;
364 }
365 io_ctl->pages[i] = page;
366 if (uptodate && !PageUptodate(page)) {
367 btrfs_readpage(NULL, page);
368 lock_page(page);
369 if (!PageUptodate(page)) {
Frank Holtonefe120a2013-12-20 11:37:06 -0500370 btrfs_err(BTRFS_I(inode)->root->fs_info,
371 "error reading free space cache");
Josef Bacika67509c2011-10-05 15:18:58 -0400372 io_ctl_drop_pages(io_ctl);
373 return -EIO;
374 }
375 }
376 }
377
Josef Bacikf7d61dc2011-11-15 09:31:24 -0500378 for (i = 0; i < io_ctl->num_pages; i++) {
379 clear_page_dirty_for_io(io_ctl->pages[i]);
380 set_page_extent_mapped(io_ctl->pages[i]);
381 }
382
Josef Bacika67509c2011-10-05 15:18:58 -0400383 return 0;
384}
385
386static void io_ctl_set_generation(struct io_ctl *io_ctl, u64 generation)
387{
Al Viro528c0322012-04-13 11:03:55 -0400388 __le64 *val;
Josef Bacika67509c2011-10-05 15:18:58 -0400389
390 io_ctl_map_page(io_ctl, 1);
391
392 /*
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400393 * Skip the csum areas. If we don't check crcs then we just have a
394 * 64bit chunk at the front of the first page.
Josef Bacika67509c2011-10-05 15:18:58 -0400395 */
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400396 if (io_ctl->check_crcs) {
397 io_ctl->cur += (sizeof(u32) * io_ctl->num_pages);
398 io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);
399 } else {
400 io_ctl->cur += sizeof(u64);
401 io_ctl->size -= sizeof(u64) * 2;
402 }
Josef Bacika67509c2011-10-05 15:18:58 -0400403
404 val = io_ctl->cur;
405 *val = cpu_to_le64(generation);
406 io_ctl->cur += sizeof(u64);
Josef Bacika67509c2011-10-05 15:18:58 -0400407}
408
409static int io_ctl_check_generation(struct io_ctl *io_ctl, u64 generation)
410{
Al Viro528c0322012-04-13 11:03:55 -0400411 __le64 *gen;
Josef Bacika67509c2011-10-05 15:18:58 -0400412
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400413 /*
414 * Skip the crc area. If we don't check crcs then we just have a 64bit
415 * chunk at the front of the first page.
416 */
417 if (io_ctl->check_crcs) {
418 io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
419 io_ctl->size -= sizeof(u64) +
420 (sizeof(u32) * io_ctl->num_pages);
421 } else {
422 io_ctl->cur += sizeof(u64);
423 io_ctl->size -= sizeof(u64) * 2;
424 }
Josef Bacika67509c2011-10-05 15:18:58 -0400425
Josef Bacika67509c2011-10-05 15:18:58 -0400426 gen = io_ctl->cur;
427 if (le64_to_cpu(*gen) != generation) {
Frank Holtonefe120a2013-12-20 11:37:06 -0500428 printk_ratelimited(KERN_ERR "BTRFS: space cache generation "
Josef Bacika67509c2011-10-05 15:18:58 -0400429 "(%Lu) does not match inode (%Lu)\n", *gen,
430 generation);
431 io_ctl_unmap_page(io_ctl);
432 return -EIO;
433 }
434 io_ctl->cur += sizeof(u64);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400435 return 0;
436}
437
438static void io_ctl_set_crc(struct io_ctl *io_ctl, int index)
439{
440 u32 *tmp;
441 u32 crc = ~(u32)0;
442 unsigned offset = 0;
443
444 if (!io_ctl->check_crcs) {
445 io_ctl_unmap_page(io_ctl);
446 return;
447 }
448
449 if (index == 0)
Justin P. Mattockcb54f252011-11-21 08:43:28 -0800450 offset = sizeof(u32) * io_ctl->num_pages;
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400451
Liu Bob0496682013-03-14 14:57:45 +0000452 crc = btrfs_csum_data(io_ctl->orig + offset, crc,
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400453 PAGE_CACHE_SIZE - offset);
454 btrfs_csum_final(crc, (char *)&crc);
455 io_ctl_unmap_page(io_ctl);
456 tmp = kmap(io_ctl->pages[0]);
457 tmp += index;
458 *tmp = crc;
459 kunmap(io_ctl->pages[0]);
460}
461
462static int io_ctl_check_crc(struct io_ctl *io_ctl, int index)
463{
464 u32 *tmp, val;
465 u32 crc = ~(u32)0;
466 unsigned offset = 0;
467
468 if (!io_ctl->check_crcs) {
469 io_ctl_map_page(io_ctl, 0);
470 return 0;
471 }
472
473 if (index == 0)
474 offset = sizeof(u32) * io_ctl->num_pages;
475
476 tmp = kmap(io_ctl->pages[0]);
477 tmp += index;
478 val = *tmp;
479 kunmap(io_ctl->pages[0]);
480
481 io_ctl_map_page(io_ctl, 0);
Liu Bob0496682013-03-14 14:57:45 +0000482 crc = btrfs_csum_data(io_ctl->orig + offset, crc,
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400483 PAGE_CACHE_SIZE - offset);
484 btrfs_csum_final(crc, (char *)&crc);
485 if (val != crc) {
Frank Holtonefe120a2013-12-20 11:37:06 -0500486 printk_ratelimited(KERN_ERR "BTRFS: csum mismatch on free "
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400487 "space cache\n");
488 io_ctl_unmap_page(io_ctl);
489 return -EIO;
490 }
491
Josef Bacika67509c2011-10-05 15:18:58 -0400492 return 0;
493}
494
495static int io_ctl_add_entry(struct io_ctl *io_ctl, u64 offset, u64 bytes,
496 void *bitmap)
497{
498 struct btrfs_free_space_entry *entry;
499
500 if (!io_ctl->cur)
501 return -ENOSPC;
502
503 entry = io_ctl->cur;
504 entry->offset = cpu_to_le64(offset);
505 entry->bytes = cpu_to_le64(bytes);
506 entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :
507 BTRFS_FREE_SPACE_EXTENT;
508 io_ctl->cur += sizeof(struct btrfs_free_space_entry);
509 io_ctl->size -= sizeof(struct btrfs_free_space_entry);
510
511 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
512 return 0;
513
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400514 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
Josef Bacika67509c2011-10-05 15:18:58 -0400515
516 /* No more pages to map */
517 if (io_ctl->index >= io_ctl->num_pages)
518 return 0;
519
520 /* map the next page */
521 io_ctl_map_page(io_ctl, 1);
522 return 0;
523}
524
525static int io_ctl_add_bitmap(struct io_ctl *io_ctl, void *bitmap)
526{
527 if (!io_ctl->cur)
528 return -ENOSPC;
529
530 /*
531 * If we aren't at the start of the current page, unmap this one and
532 * map the next one if there is any left.
533 */
534 if (io_ctl->cur != io_ctl->orig) {
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400535 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
Josef Bacika67509c2011-10-05 15:18:58 -0400536 if (io_ctl->index >= io_ctl->num_pages)
537 return -ENOSPC;
538 io_ctl_map_page(io_ctl, 0);
539 }
540
541 memcpy(io_ctl->cur, bitmap, PAGE_CACHE_SIZE);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400542 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
Josef Bacika67509c2011-10-05 15:18:58 -0400543 if (io_ctl->index < io_ctl->num_pages)
544 io_ctl_map_page(io_ctl, 0);
545 return 0;
546}
547
548static void io_ctl_zero_remaining_pages(struct io_ctl *io_ctl)
549{
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400550 /*
551 * If we're not on the boundary we know we've modified the page and we
552 * need to crc the page.
553 */
554 if (io_ctl->cur != io_ctl->orig)
555 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
556 else
557 io_ctl_unmap_page(io_ctl);
Josef Bacika67509c2011-10-05 15:18:58 -0400558
559 while (io_ctl->index < io_ctl->num_pages) {
560 io_ctl_map_page(io_ctl, 1);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400561 io_ctl_set_crc(io_ctl, io_ctl->index - 1);
Josef Bacika67509c2011-10-05 15:18:58 -0400562 }
563}
564
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400565static int io_ctl_read_entry(struct io_ctl *io_ctl,
566 struct btrfs_free_space *entry, u8 *type)
Josef Bacika67509c2011-10-05 15:18:58 -0400567{
568 struct btrfs_free_space_entry *e;
Josef Bacik2f120c02011-11-10 20:45:05 -0500569 int ret;
570
571 if (!io_ctl->cur) {
572 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
573 if (ret)
574 return ret;
575 }
Josef Bacika67509c2011-10-05 15:18:58 -0400576
577 e = io_ctl->cur;
578 entry->offset = le64_to_cpu(e->offset);
579 entry->bytes = le64_to_cpu(e->bytes);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400580 *type = e->type;
Josef Bacika67509c2011-10-05 15:18:58 -0400581 io_ctl->cur += sizeof(struct btrfs_free_space_entry);
582 io_ctl->size -= sizeof(struct btrfs_free_space_entry);
583
584 if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400585 return 0;
Josef Bacika67509c2011-10-05 15:18:58 -0400586
587 io_ctl_unmap_page(io_ctl);
588
Josef Bacik2f120c02011-11-10 20:45:05 -0500589 return 0;
Josef Bacika67509c2011-10-05 15:18:58 -0400590}
591
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400592static int io_ctl_read_bitmap(struct io_ctl *io_ctl,
593 struct btrfs_free_space *entry)
Josef Bacika67509c2011-10-05 15:18:58 -0400594{
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400595 int ret;
596
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400597 ret = io_ctl_check_crc(io_ctl, io_ctl->index);
598 if (ret)
599 return ret;
600
Josef Bacika67509c2011-10-05 15:18:58 -0400601 memcpy(entry->bitmap, io_ctl->cur, PAGE_CACHE_SIZE);
602 io_ctl_unmap_page(io_ctl);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400603
604 return 0;
Josef Bacika67509c2011-10-05 15:18:58 -0400605}
606
Josef Bacikcd023e72012-05-14 10:06:40 -0400607/*
608 * Since we attach pinned extents after the fact we can have contiguous sections
609 * of free space that are split up in entries. This poses a problem with the
610 * tree logging stuff since it could have allocated across what appears to be 2
611 * entries since we would have merged the entries when adding the pinned extents
612 * back to the free space cache. So run through the space cache that we just
613 * loaded and merge contiguous entries. This will make the log replay stuff not
614 * blow up and it will make for nicer allocator behavior.
615 */
616static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
617{
618 struct btrfs_free_space *e, *prev = NULL;
619 struct rb_node *n;
620
621again:
622 spin_lock(&ctl->tree_lock);
623 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
624 e = rb_entry(n, struct btrfs_free_space, offset_index);
625 if (!prev)
626 goto next;
627 if (e->bitmap || prev->bitmap)
628 goto next;
629 if (prev->offset + prev->bytes == e->offset) {
630 unlink_free_space(ctl, prev);
631 unlink_free_space(ctl, e);
632 prev->bytes += e->bytes;
633 kmem_cache_free(btrfs_free_space_cachep, e);
634 link_free_space(ctl, prev);
635 prev = NULL;
636 spin_unlock(&ctl->tree_lock);
637 goto again;
638 }
639next:
640 prev = e;
641 }
642 spin_unlock(&ctl->tree_lock);
643}
644
Eric Sandeen48a3b632013-04-25 20:41:01 +0000645static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
646 struct btrfs_free_space_ctl *ctl,
647 struct btrfs_path *path, u64 offset)
Josef Bacik9d66e232010-08-25 16:54:15 -0400648{
Josef Bacik9d66e232010-08-25 16:54:15 -0400649 struct btrfs_free_space_header *header;
650 struct extent_buffer *leaf;
Josef Bacika67509c2011-10-05 15:18:58 -0400651 struct io_ctl io_ctl;
Josef Bacik9d66e232010-08-25 16:54:15 -0400652 struct btrfs_key key;
Josef Bacika67509c2011-10-05 15:18:58 -0400653 struct btrfs_free_space *e, *n;
Josef Bacik9d66e232010-08-25 16:54:15 -0400654 struct list_head bitmaps;
655 u64 num_entries;
656 u64 num_bitmaps;
657 u64 generation;
Josef Bacika67509c2011-10-05 15:18:58 -0400658 u8 type;
Josef Bacikf6a39822011-06-06 10:50:35 -0400659 int ret = 0;
Josef Bacik9d66e232010-08-25 16:54:15 -0400660
661 INIT_LIST_HEAD(&bitmaps);
662
Josef Bacik9d66e232010-08-25 16:54:15 -0400663 /* Nothing in the space cache, goodbye */
Li Zefan0414efa2011-04-20 10:20:14 +0800664 if (!i_size_read(inode))
Josef Bacika67509c2011-10-05 15:18:58 -0400665 return 0;
Josef Bacik9d66e232010-08-25 16:54:15 -0400666
667 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
Li Zefan0414efa2011-04-20 10:20:14 +0800668 key.offset = offset;
Josef Bacik9d66e232010-08-25 16:54:15 -0400669 key.type = 0;
670
671 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
Li Zefan0414efa2011-04-20 10:20:14 +0800672 if (ret < 0)
Josef Bacika67509c2011-10-05 15:18:58 -0400673 return 0;
Li Zefan0414efa2011-04-20 10:20:14 +0800674 else if (ret > 0) {
Chris Mason945d8962011-05-22 12:33:42 -0400675 btrfs_release_path(path);
Josef Bacika67509c2011-10-05 15:18:58 -0400676 return 0;
Josef Bacik9d66e232010-08-25 16:54:15 -0400677 }
678
Li Zefan0414efa2011-04-20 10:20:14 +0800679 ret = -1;
680
Josef Bacik9d66e232010-08-25 16:54:15 -0400681 leaf = path->nodes[0];
682 header = btrfs_item_ptr(leaf, path->slots[0],
683 struct btrfs_free_space_header);
684 num_entries = btrfs_free_space_entries(leaf, header);
685 num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
686 generation = btrfs_free_space_generation(leaf, header);
Chris Mason945d8962011-05-22 12:33:42 -0400687 btrfs_release_path(path);
Josef Bacik9d66e232010-08-25 16:54:15 -0400688
Miao Xiee570fd22014-06-19 10:42:50 +0800689 if (!BTRFS_I(inode)->generation) {
690 btrfs_info(root->fs_info,
691 "The free space cache file (%llu) is invalid. skip it\n",
692 offset);
693 return 0;
694 }
695
Josef Bacik9d66e232010-08-25 16:54:15 -0400696 if (BTRFS_I(inode)->generation != generation) {
Simon Kirbyc2cf52e2013-03-19 22:41:23 +0000697 btrfs_err(root->fs_info,
698 "free space inode generation (%llu) "
699 "did not match free space cache generation (%llu)",
Geert Uytterhoevenc1c9ff72013-08-20 13:20:07 +0200700 BTRFS_I(inode)->generation, generation);
Josef Bacika67509c2011-10-05 15:18:58 -0400701 return 0;
Josef Bacik9d66e232010-08-25 16:54:15 -0400702 }
703
704 if (!num_entries)
Josef Bacika67509c2011-10-05 15:18:58 -0400705 return 0;
Josef Bacik9d66e232010-08-25 16:54:15 -0400706
Miao Xie5349d6c2014-06-19 10:42:49 +0800707 ret = io_ctl_init(&io_ctl, inode, root, 0);
Li Zefan706efc62012-01-09 14:36:28 +0800708 if (ret)
709 return ret;
710
Josef Bacik9d66e232010-08-25 16:54:15 -0400711 ret = readahead_cache(inode);
Li Zefan0414efa2011-04-20 10:20:14 +0800712 if (ret)
Josef Bacik9d66e232010-08-25 16:54:15 -0400713 goto out;
Josef Bacik9d66e232010-08-25 16:54:15 -0400714
Josef Bacika67509c2011-10-05 15:18:58 -0400715 ret = io_ctl_prepare_pages(&io_ctl, inode, 1);
716 if (ret)
717 goto out;
Josef Bacik9d66e232010-08-25 16:54:15 -0400718
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400719 ret = io_ctl_check_crc(&io_ctl, 0);
720 if (ret)
721 goto free_cache;
722
Josef Bacika67509c2011-10-05 15:18:58 -0400723 ret = io_ctl_check_generation(&io_ctl, generation);
724 if (ret)
725 goto free_cache;
Josef Bacik9d66e232010-08-25 16:54:15 -0400726
Josef Bacika67509c2011-10-05 15:18:58 -0400727 while (num_entries) {
728 e = kmem_cache_zalloc(btrfs_free_space_cachep,
729 GFP_NOFS);
730 if (!e)
Josef Bacik9d66e232010-08-25 16:54:15 -0400731 goto free_cache;
Josef Bacik9d66e232010-08-25 16:54:15 -0400732
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400733 ret = io_ctl_read_entry(&io_ctl, e, &type);
734 if (ret) {
735 kmem_cache_free(btrfs_free_space_cachep, e);
736 goto free_cache;
737 }
738
Josef Bacika67509c2011-10-05 15:18:58 -0400739 if (!e->bytes) {
740 kmem_cache_free(btrfs_free_space_cachep, e);
741 goto free_cache;
Josef Bacik9d66e232010-08-25 16:54:15 -0400742 }
Josef Bacik9d66e232010-08-25 16:54:15 -0400743
Josef Bacika67509c2011-10-05 15:18:58 -0400744 if (type == BTRFS_FREE_SPACE_EXTENT) {
745 spin_lock(&ctl->tree_lock);
746 ret = link_free_space(ctl, e);
747 spin_unlock(&ctl->tree_lock);
748 if (ret) {
Simon Kirbyc2cf52e2013-03-19 22:41:23 +0000749 btrfs_err(root->fs_info,
750 "Duplicate entries in free space cache, dumping");
Josef Bacikdc89e982011-01-28 17:05:48 -0500751 kmem_cache_free(btrfs_free_space_cachep, e);
Josef Bacik9d66e232010-08-25 16:54:15 -0400752 goto free_cache;
753 }
Josef Bacika67509c2011-10-05 15:18:58 -0400754 } else {
Josef Bacikb12d6862013-08-26 17:14:08 -0400755 ASSERT(num_bitmaps);
Josef Bacika67509c2011-10-05 15:18:58 -0400756 num_bitmaps--;
757 e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
758 if (!e->bitmap) {
759 kmem_cache_free(
760 btrfs_free_space_cachep, e);
761 goto free_cache;
Josef Bacik9d66e232010-08-25 16:54:15 -0400762 }
Josef Bacika67509c2011-10-05 15:18:58 -0400763 spin_lock(&ctl->tree_lock);
764 ret = link_free_space(ctl, e);
765 ctl->total_bitmaps++;
766 ctl->op->recalc_thresholds(ctl);
767 spin_unlock(&ctl->tree_lock);
768 if (ret) {
Simon Kirbyc2cf52e2013-03-19 22:41:23 +0000769 btrfs_err(root->fs_info,
770 "Duplicate entries in free space cache, dumping");
Josef Bacika67509c2011-10-05 15:18:58 -0400771 kmem_cache_free(btrfs_free_space_cachep, e);
772 goto free_cache;
773 }
774 list_add_tail(&e->list, &bitmaps);
Josef Bacik9d66e232010-08-25 16:54:15 -0400775 }
776
Josef Bacika67509c2011-10-05 15:18:58 -0400777 num_entries--;
Josef Bacik9d66e232010-08-25 16:54:15 -0400778 }
779
Josef Bacik2f120c02011-11-10 20:45:05 -0500780 io_ctl_unmap_page(&io_ctl);
781
Josef Bacika67509c2011-10-05 15:18:58 -0400782 /*
783 * We add the bitmaps at the end of the entries in order that
784 * the bitmap entries are added to the cache.
785 */
786 list_for_each_entry_safe(e, n, &bitmaps, list) {
787 list_del_init(&e->list);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400788 ret = io_ctl_read_bitmap(&io_ctl, e);
789 if (ret)
790 goto free_cache;
Josef Bacika67509c2011-10-05 15:18:58 -0400791 }
792
793 io_ctl_drop_pages(&io_ctl);
Josef Bacikcd023e72012-05-14 10:06:40 -0400794 merge_space_tree(ctl);
Josef Bacik9d66e232010-08-25 16:54:15 -0400795 ret = 1;
796out:
Josef Bacika67509c2011-10-05 15:18:58 -0400797 io_ctl_free(&io_ctl);
Josef Bacik9d66e232010-08-25 16:54:15 -0400798 return ret;
Josef Bacik9d66e232010-08-25 16:54:15 -0400799free_cache:
Josef Bacika67509c2011-10-05 15:18:58 -0400800 io_ctl_drop_pages(&io_ctl);
Li Zefan0414efa2011-04-20 10:20:14 +0800801 __btrfs_remove_free_space_cache(ctl);
Josef Bacik9d66e232010-08-25 16:54:15 -0400802 goto out;
803}
804
Li Zefan0414efa2011-04-20 10:20:14 +0800805int load_free_space_cache(struct btrfs_fs_info *fs_info,
806 struct btrfs_block_group_cache *block_group)
Josef Bacik0cb59c92010-07-02 12:14:14 -0400807{
Li Zefan34d52cb2011-03-29 13:46:06 +0800808 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Li Zefan0414efa2011-04-20 10:20:14 +0800809 struct btrfs_root *root = fs_info->tree_root;
810 struct inode *inode;
811 struct btrfs_path *path;
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400812 int ret = 0;
Li Zefan0414efa2011-04-20 10:20:14 +0800813 bool matched;
814 u64 used = btrfs_block_group_used(&block_group->item);
815
816 /*
Li Zefan0414efa2011-04-20 10:20:14 +0800817 * If this block group has been marked to be cleared for one reason or
818 * another then we can't trust the on disk cache, so just return.
819 */
820 spin_lock(&block_group->lock);
821 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
822 spin_unlock(&block_group->lock);
823 return 0;
824 }
825 spin_unlock(&block_group->lock);
826
827 path = btrfs_alloc_path();
828 if (!path)
829 return 0;
Josef Bacikd53ba472012-04-12 16:03:57 -0400830 path->search_commit_root = 1;
831 path->skip_locking = 1;
Li Zefan0414efa2011-04-20 10:20:14 +0800832
833 inode = lookup_free_space_inode(root, block_group, path);
834 if (IS_ERR(inode)) {
835 btrfs_free_path(path);
836 return 0;
837 }
838
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400839 /* We may have converted the inode and made the cache invalid. */
840 spin_lock(&block_group->lock);
841 if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
842 spin_unlock(&block_group->lock);
Tsutomu Itoha7e221e2012-02-14 17:12:23 +0900843 btrfs_free_path(path);
Josef Bacik5b0e95b2011-10-06 08:58:24 -0400844 goto out;
845 }
846 spin_unlock(&block_group->lock);
847
Li Zefan0414efa2011-04-20 10:20:14 +0800848 ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
849 path, block_group->key.objectid);
850 btrfs_free_path(path);
851 if (ret <= 0)
852 goto out;
853
854 spin_lock(&ctl->tree_lock);
855 matched = (ctl->free_space == (block_group->key.offset - used -
856 block_group->bytes_super));
857 spin_unlock(&ctl->tree_lock);
858
859 if (!matched) {
860 __btrfs_remove_free_space_cache(ctl);
Miao Xie32d6b472014-04-24 13:31:55 +0800861 btrfs_warn(fs_info, "block group %llu has wrong amount of free space",
Simon Kirbyc2cf52e2013-03-19 22:41:23 +0000862 block_group->key.objectid);
Li Zefan0414efa2011-04-20 10:20:14 +0800863 ret = -1;
864 }
865out:
866 if (ret < 0) {
867 /* This cache is bogus, make sure it gets cleared */
868 spin_lock(&block_group->lock);
869 block_group->disk_cache_state = BTRFS_DC_CLEAR;
870 spin_unlock(&block_group->lock);
Li Zefan82d59022011-04-20 10:33:24 +0800871 ret = 0;
Li Zefan0414efa2011-04-20 10:20:14 +0800872
Miao Xie32d6b472014-04-24 13:31:55 +0800873 btrfs_warn(fs_info, "failed to load free space cache for block group %llu, rebuild it now",
Simon Kirbyc2cf52e2013-03-19 22:41:23 +0000874 block_group->key.objectid);
Li Zefan0414efa2011-04-20 10:20:14 +0800875 }
876
877 iput(inode);
878 return ret;
879}
880
Chris Masond4452bc2014-05-19 20:47:56 -0700881static noinline_for_stack
882int write_cache_extent_entries(struct io_ctl *io_ctl,
883 struct btrfs_free_space_ctl *ctl,
884 struct btrfs_block_group_cache *block_group,
885 int *entries, int *bitmaps,
886 struct list_head *bitmap_list)
Josef Bacik0cb59c92010-07-02 12:14:14 -0400887{
Josef Bacikc09544e2011-08-30 10:19:10 -0400888 int ret;
Chris Masond4452bc2014-05-19 20:47:56 -0700889 struct btrfs_free_cluster *cluster = NULL;
890 struct rb_node *node = rb_first(&ctl->free_space_offset);
Filipe Manana55507ce2014-12-01 17:04:09 +0000891 struct btrfs_trim_range *trim_entry;
Josef Bacikbe1a12a2011-04-06 13:05:22 -0400892
Josef Bacik43be2142011-04-01 14:55:00 +0000893 /* Get the cluster for this block_group if it exists */
Chris Masond4452bc2014-05-19 20:47:56 -0700894 if (block_group && !list_empty(&block_group->cluster_list)) {
Josef Bacik43be2142011-04-01 14:55:00 +0000895 cluster = list_entry(block_group->cluster_list.next,
896 struct btrfs_free_cluster,
897 block_group_list);
Chris Masond4452bc2014-05-19 20:47:56 -0700898 }
Josef Bacik43be2142011-04-01 14:55:00 +0000899
Josef Bacikf75b1302011-10-05 10:00:18 -0400900 if (!node && cluster) {
901 node = rb_first(&cluster->root);
902 cluster = NULL;
903 }
904
Josef Bacik0cb59c92010-07-02 12:14:14 -0400905 /* Write out the extent entries */
Josef Bacika67509c2011-10-05 15:18:58 -0400906 while (node) {
907 struct btrfs_free_space *e;
Josef Bacik0cb59c92010-07-02 12:14:14 -0400908
Josef Bacika67509c2011-10-05 15:18:58 -0400909 e = rb_entry(node, struct btrfs_free_space, offset_index);
Chris Masond4452bc2014-05-19 20:47:56 -0700910 *entries += 1;
Josef Bacik43be2142011-04-01 14:55:00 +0000911
Chris Masond4452bc2014-05-19 20:47:56 -0700912 ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes,
Josef Bacika67509c2011-10-05 15:18:58 -0400913 e->bitmap);
914 if (ret)
Chris Masond4452bc2014-05-19 20:47:56 -0700915 goto fail;
Josef Bacika67509c2011-10-05 15:18:58 -0400916
917 if (e->bitmap) {
Chris Masond4452bc2014-05-19 20:47:56 -0700918 list_add_tail(&e->list, bitmap_list);
919 *bitmaps += 1;
Josef Bacika67509c2011-10-05 15:18:58 -0400920 }
921 node = rb_next(node);
922 if (!node && cluster) {
923 node = rb_first(&cluster->root);
924 cluster = NULL;
925 }
926 }
Filipe Manana55507ce2014-12-01 17:04:09 +0000927
928 /*
929 * Make sure we don't miss any range that was removed from our rbtree
930 * because trimming is running. Otherwise after a umount+mount (or crash
931 * after committing the transaction) we would leak free space and get
932 * an inconsistent free space cache report from fsck.
933 */
934 list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {
935 ret = io_ctl_add_entry(io_ctl, trim_entry->start,
936 trim_entry->bytes, NULL);
937 if (ret)
938 goto fail;
939 *entries += 1;
940 }
941
Chris Masond4452bc2014-05-19 20:47:56 -0700942 return 0;
943fail:
944 return -ENOSPC;
945}
946
947static noinline_for_stack int
948update_cache_item(struct btrfs_trans_handle *trans,
949 struct btrfs_root *root,
950 struct inode *inode,
951 struct btrfs_path *path, u64 offset,
952 int entries, int bitmaps)
953{
954 struct btrfs_key key;
955 struct btrfs_free_space_header *header;
956 struct extent_buffer *leaf;
957 int ret;
958
959 key.objectid = BTRFS_FREE_SPACE_OBJECTID;
960 key.offset = offset;
961 key.type = 0;
962
963 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
964 if (ret < 0) {
965 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
966 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
967 GFP_NOFS);
968 goto fail;
969 }
970 leaf = path->nodes[0];
971 if (ret > 0) {
972 struct btrfs_key found_key;
973 ASSERT(path->slots[0]);
974 path->slots[0]--;
975 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
976 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
977 found_key.offset != offset) {
978 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,
979 inode->i_size - 1,
980 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0,
981 NULL, GFP_NOFS);
982 btrfs_release_path(path);
983 goto fail;
984 }
985 }
986
987 BTRFS_I(inode)->generation = trans->transid;
988 header = btrfs_item_ptr(leaf, path->slots[0],
989 struct btrfs_free_space_header);
990 btrfs_set_free_space_entries(leaf, header, entries);
991 btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
992 btrfs_set_free_space_generation(leaf, header, trans->transid);
993 btrfs_mark_buffer_dirty(leaf);
994 btrfs_release_path(path);
995
996 return 0;
997
998fail:
999 return -1;
1000}
1001
1002static noinline_for_stack int
Miao Xie5349d6c2014-06-19 10:42:49 +08001003write_pinned_extent_entries(struct btrfs_root *root,
1004 struct btrfs_block_group_cache *block_group,
1005 struct io_ctl *io_ctl,
1006 int *entries)
Chris Masond4452bc2014-05-19 20:47:56 -07001007{
1008 u64 start, extent_start, extent_end, len;
Chris Masond4452bc2014-05-19 20:47:56 -07001009 struct extent_io_tree *unpin = NULL;
1010 int ret;
Josef Bacika67509c2011-10-05 15:18:58 -04001011
Miao Xie5349d6c2014-06-19 10:42:49 +08001012 if (!block_group)
1013 return 0;
1014
Josef Bacika67509c2011-10-05 15:18:58 -04001015 /*
1016 * We want to add any pinned extents to our free space cache
1017 * so we don't leak the space
Chris Masond4452bc2014-05-19 20:47:56 -07001018 *
Li Zefandb804f22012-01-10 16:41:01 +08001019 * We shouldn't have switched the pinned extents yet so this is the
1020 * right one
1021 */
1022 unpin = root->fs_info->pinned_extents;
1023
Miao Xie5349d6c2014-06-19 10:42:49 +08001024 start = block_group->key.objectid;
Li Zefandb804f22012-01-10 16:41:01 +08001025
Miao Xie5349d6c2014-06-19 10:42:49 +08001026 while (start < block_group->key.objectid + block_group->key.offset) {
Li Zefandb804f22012-01-10 16:41:01 +08001027 ret = find_first_extent_bit(unpin, start,
1028 &extent_start, &extent_end,
Josef Bacike6138872012-09-27 17:07:30 -04001029 EXTENT_DIRTY, NULL);
Miao Xie5349d6c2014-06-19 10:42:49 +08001030 if (ret)
1031 return 0;
Josef Bacikbe1a12a2011-04-06 13:05:22 -04001032
Josef Bacika67509c2011-10-05 15:18:58 -04001033 /* This pinned extent is out of our range */
Li Zefandb804f22012-01-10 16:41:01 +08001034 if (extent_start >= block_group->key.objectid +
Josef Bacika67509c2011-10-05 15:18:58 -04001035 block_group->key.offset)
Miao Xie5349d6c2014-06-19 10:42:49 +08001036 return 0;
Josef Bacik0cb59c92010-07-02 12:14:14 -04001037
Li Zefandb804f22012-01-10 16:41:01 +08001038 extent_start = max(extent_start, start);
1039 extent_end = min(block_group->key.objectid +
1040 block_group->key.offset, extent_end + 1);
1041 len = extent_end - extent_start;
Josef Bacik0cb59c92010-07-02 12:14:14 -04001042
Chris Masond4452bc2014-05-19 20:47:56 -07001043 *entries += 1;
1044 ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);
Josef Bacika67509c2011-10-05 15:18:58 -04001045 if (ret)
Miao Xie5349d6c2014-06-19 10:42:49 +08001046 return -ENOSPC;
Josef Bacik2f356122011-06-10 15:31:13 -04001047
Li Zefandb804f22012-01-10 16:41:01 +08001048 start = extent_end;
Josef Bacika67509c2011-10-05 15:18:58 -04001049 }
Josef Bacik0cb59c92010-07-02 12:14:14 -04001050
Miao Xie5349d6c2014-06-19 10:42:49 +08001051 return 0;
1052}
1053
1054static noinline_for_stack int
1055write_bitmap_entries(struct io_ctl *io_ctl, struct list_head *bitmap_list)
1056{
1057 struct list_head *pos, *n;
1058 int ret;
1059
Josef Bacik0cb59c92010-07-02 12:14:14 -04001060 /* Write out the bitmaps */
Chris Masond4452bc2014-05-19 20:47:56 -07001061 list_for_each_safe(pos, n, bitmap_list) {
Josef Bacik0cb59c92010-07-02 12:14:14 -04001062 struct btrfs_free_space *entry =
1063 list_entry(pos, struct btrfs_free_space, list);
1064
Chris Masond4452bc2014-05-19 20:47:56 -07001065 ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);
Josef Bacika67509c2011-10-05 15:18:58 -04001066 if (ret)
Miao Xie5349d6c2014-06-19 10:42:49 +08001067 return -ENOSPC;
Josef Bacik0cb59c92010-07-02 12:14:14 -04001068 list_del_init(&entry->list);
Josef Bacikbe1a12a2011-04-06 13:05:22 -04001069 }
1070
Miao Xie5349d6c2014-06-19 10:42:49 +08001071 return 0;
1072}
Josef Bacik0cb59c92010-07-02 12:14:14 -04001073
Miao Xie5349d6c2014-06-19 10:42:49 +08001074static int flush_dirty_cache(struct inode *inode)
1075{
1076 int ret;
Josef Bacikbe1a12a2011-04-06 13:05:22 -04001077
Josef Bacik0ef8b722013-10-25 16:13:35 -04001078 ret = btrfs_wait_ordered_range(inode, 0, (u64)-1);
Miao Xie5349d6c2014-06-19 10:42:49 +08001079 if (ret)
Josef Bacik0ef8b722013-10-25 16:13:35 -04001080 clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
1081 EXTENT_DIRTY | EXTENT_DELALLOC, 0, 0, NULL,
1082 GFP_NOFS);
Chris Masond4452bc2014-05-19 20:47:56 -07001083
Miao Xie5349d6c2014-06-19 10:42:49 +08001084 return ret;
Chris Masond4452bc2014-05-19 20:47:56 -07001085}
1086
1087static void noinline_for_stack
1088cleanup_write_cache_enospc(struct inode *inode,
1089 struct io_ctl *io_ctl,
1090 struct extent_state **cached_state,
1091 struct list_head *bitmap_list)
1092{
1093 struct list_head *pos, *n;
Miao Xie5349d6c2014-06-19 10:42:49 +08001094
Chris Masond4452bc2014-05-19 20:47:56 -07001095 list_for_each_safe(pos, n, bitmap_list) {
1096 struct btrfs_free_space *entry =
1097 list_entry(pos, struct btrfs_free_space, list);
1098 list_del_init(&entry->list);
1099 }
1100 io_ctl_drop_pages(io_ctl);
1101 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
1102 i_size_read(inode) - 1, cached_state,
1103 GFP_NOFS);
1104}
1105
1106/**
1107 * __btrfs_write_out_cache - write out cached info to an inode
1108 * @root - the root the inode belongs to
1109 * @ctl - the free space cache we are going to write out
1110 * @block_group - the block_group for this cache if it belongs to a block_group
1111 * @trans - the trans handle
1112 * @path - the path to use
1113 * @offset - the offset for the key we'll insert
1114 *
1115 * This function writes out a free space cache struct to disk for quick recovery
1116 * on mount. This will return 0 if it was successfull in writing the cache out,
1117 * and -1 if it was not.
1118 */
1119static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
1120 struct btrfs_free_space_ctl *ctl,
1121 struct btrfs_block_group_cache *block_group,
1122 struct btrfs_trans_handle *trans,
1123 struct btrfs_path *path, u64 offset)
1124{
1125 struct extent_state *cached_state = NULL;
1126 struct io_ctl io_ctl;
Miao Xie5349d6c2014-06-19 10:42:49 +08001127 LIST_HEAD(bitmap_list);
Chris Masond4452bc2014-05-19 20:47:56 -07001128 int entries = 0;
1129 int bitmaps = 0;
1130 int ret;
Chris Masond4452bc2014-05-19 20:47:56 -07001131
1132 if (!i_size_read(inode))
1133 return -1;
1134
Miao Xie5349d6c2014-06-19 10:42:49 +08001135 ret = io_ctl_init(&io_ctl, inode, root, 1);
Chris Masond4452bc2014-05-19 20:47:56 -07001136 if (ret)
1137 return -1;
1138
Miao Xiee570fd22014-06-19 10:42:50 +08001139 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) {
1140 down_write(&block_group->data_rwsem);
1141 spin_lock(&block_group->lock);
1142 if (block_group->delalloc_bytes) {
1143 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
1144 spin_unlock(&block_group->lock);
1145 up_write(&block_group->data_rwsem);
1146 BTRFS_I(inode)->generation = 0;
1147 ret = 0;
1148 goto out;
1149 }
1150 spin_unlock(&block_group->lock);
1151 }
1152
Chris Masond4452bc2014-05-19 20:47:56 -07001153 /* Lock all pages first so we can lock the extent safely. */
1154 io_ctl_prepare_pages(&io_ctl, inode, 0);
1155
1156 lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
1157 0, &cached_state);
1158
Chris Masond4452bc2014-05-19 20:47:56 -07001159 io_ctl_set_generation(&io_ctl, trans->transid);
1160
Filipe Manana55507ce2014-12-01 17:04:09 +00001161 mutex_lock(&ctl->cache_writeout_mutex);
Miao Xie5349d6c2014-06-19 10:42:49 +08001162 /* Write out the extent entries in the free space cache */
Chris Masond4452bc2014-05-19 20:47:56 -07001163 ret = write_cache_extent_entries(&io_ctl, ctl,
1164 block_group, &entries, &bitmaps,
1165 &bitmap_list);
Filipe Manana55507ce2014-12-01 17:04:09 +00001166 if (ret) {
1167 mutex_unlock(&ctl->cache_writeout_mutex);
Chris Masond4452bc2014-05-19 20:47:56 -07001168 goto out_nospc;
Filipe Manana55507ce2014-12-01 17:04:09 +00001169 }
Chris Masond4452bc2014-05-19 20:47:56 -07001170
Miao Xie5349d6c2014-06-19 10:42:49 +08001171 /*
1172 * Some spaces that are freed in the current transaction are pinned,
1173 * they will be added into free space cache after the transaction is
1174 * committed, we shouldn't lose them.
1175 */
1176 ret = write_pinned_extent_entries(root, block_group, &io_ctl, &entries);
Filipe Manana55507ce2014-12-01 17:04:09 +00001177 if (ret) {
1178 mutex_unlock(&ctl->cache_writeout_mutex);
Chris Masond4452bc2014-05-19 20:47:56 -07001179 goto out_nospc;
Filipe Manana55507ce2014-12-01 17:04:09 +00001180 }
Miao Xie5349d6c2014-06-19 10:42:49 +08001181
Filipe Manana55507ce2014-12-01 17:04:09 +00001182 /*
1183 * At last, we write out all the bitmaps and keep cache_writeout_mutex
1184 * locked while doing it because a concurrent trim can be manipulating
1185 * or freeing the bitmap.
1186 */
Miao Xie5349d6c2014-06-19 10:42:49 +08001187 ret = write_bitmap_entries(&io_ctl, &bitmap_list);
Filipe Manana55507ce2014-12-01 17:04:09 +00001188 mutex_unlock(&ctl->cache_writeout_mutex);
Miao Xie5349d6c2014-06-19 10:42:49 +08001189 if (ret)
1190 goto out_nospc;
1191
1192 /* Zero out the rest of the pages just to make sure */
1193 io_ctl_zero_remaining_pages(&io_ctl);
1194
1195 /* Everything is written out, now we dirty the pages in the file. */
1196 ret = btrfs_dirty_pages(root, inode, io_ctl.pages, io_ctl.num_pages,
1197 0, i_size_read(inode), &cached_state);
1198 if (ret)
1199 goto out_nospc;
1200
Miao Xiee570fd22014-06-19 10:42:50 +08001201 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
1202 up_write(&block_group->data_rwsem);
Miao Xie5349d6c2014-06-19 10:42:49 +08001203 /*
1204 * Release the pages and unlock the extent, we will flush
1205 * them out later
1206 */
1207 io_ctl_drop_pages(&io_ctl);
1208
1209 unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
1210 i_size_read(inode) - 1, &cached_state, GFP_NOFS);
1211
1212 /* Flush the dirty pages in the cache file. */
1213 ret = flush_dirty_cache(inode);
1214 if (ret)
Josef Bacik0ef8b722013-10-25 16:13:35 -04001215 goto out;
Josef Bacik0cb59c92010-07-02 12:14:14 -04001216
Miao Xie5349d6c2014-06-19 10:42:49 +08001217 /* Update the cache item to tell everyone this cache file is valid. */
1218 ret = update_cache_item(trans, root, inode, path, offset,
Chris Masond4452bc2014-05-19 20:47:56 -07001219 entries, bitmaps);
Josef Bacik2f356122011-06-10 15:31:13 -04001220out:
Josef Bacika67509c2011-10-05 15:18:58 -04001221 io_ctl_free(&io_ctl);
Miao Xie5349d6c2014-06-19 10:42:49 +08001222 if (ret) {
Josef Bacika67509c2011-10-05 15:18:58 -04001223 invalidate_inode_pages2(inode->i_mapping);
Josef Bacik0cb59c92010-07-02 12:14:14 -04001224 BTRFS_I(inode)->generation = 0;
1225 }
Josef Bacik0cb59c92010-07-02 12:14:14 -04001226 btrfs_update_inode(trans, root, inode);
Miao Xie5349d6c2014-06-19 10:42:49 +08001227 return ret;
Josef Bacika67509c2011-10-05 15:18:58 -04001228
1229out_nospc:
Chris Masond4452bc2014-05-19 20:47:56 -07001230 cleanup_write_cache_enospc(inode, &io_ctl, &cached_state, &bitmap_list);
Miao Xiee570fd22014-06-19 10:42:50 +08001231
1232 if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
1233 up_write(&block_group->data_rwsem);
1234
Josef Bacika67509c2011-10-05 15:18:58 -04001235 goto out;
Li Zefan0414efa2011-04-20 10:20:14 +08001236}
1237
1238int btrfs_write_out_cache(struct btrfs_root *root,
1239 struct btrfs_trans_handle *trans,
1240 struct btrfs_block_group_cache *block_group,
1241 struct btrfs_path *path)
1242{
1243 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
1244 struct inode *inode;
1245 int ret = 0;
1246
1247 root = root->fs_info->tree_root;
1248
1249 spin_lock(&block_group->lock);
1250 if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
1251 spin_unlock(&block_group->lock);
1252 return 0;
1253 }
Miao Xiee570fd22014-06-19 10:42:50 +08001254
1255 if (block_group->delalloc_bytes) {
1256 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
1257 spin_unlock(&block_group->lock);
1258 return 0;
1259 }
Li Zefan0414efa2011-04-20 10:20:14 +08001260 spin_unlock(&block_group->lock);
1261
1262 inode = lookup_free_space_inode(root, block_group, path);
1263 if (IS_ERR(inode))
1264 return 0;
1265
1266 ret = __btrfs_write_out_cache(root, inode, ctl, block_group, trans,
1267 path, block_group->key.objectid);
Josef Bacikc09544e2011-08-30 10:19:10 -04001268 if (ret) {
Li Zefan0414efa2011-04-20 10:20:14 +08001269 spin_lock(&block_group->lock);
1270 block_group->disk_cache_state = BTRFS_DC_ERROR;
1271 spin_unlock(&block_group->lock);
Li Zefan82d59022011-04-20 10:33:24 +08001272 ret = 0;
Josef Bacikc09544e2011-08-30 10:19:10 -04001273#ifdef DEBUG
Simon Kirbyc2cf52e2013-03-19 22:41:23 +00001274 btrfs_err(root->fs_info,
1275 "failed to write free space cache for block group %llu",
1276 block_group->key.objectid);
Josef Bacikc09544e2011-08-30 10:19:10 -04001277#endif
Li Zefan0414efa2011-04-20 10:20:14 +08001278 }
1279
Josef Bacik0cb59c92010-07-02 12:14:14 -04001280 iput(inode);
1281 return ret;
1282}
1283
Li Zefan34d52cb2011-03-29 13:46:06 +08001284static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
Josef Bacik96303082009-07-13 21:29:25 -04001285 u64 offset)
1286{
Josef Bacikb12d6862013-08-26 17:14:08 -04001287 ASSERT(offset >= bitmap_start);
Josef Bacik96303082009-07-13 21:29:25 -04001288 offset -= bitmap_start;
Li Zefan34d52cb2011-03-29 13:46:06 +08001289 return (unsigned long)(div_u64(offset, unit));
Josef Bacik96303082009-07-13 21:29:25 -04001290}
1291
Li Zefan34d52cb2011-03-29 13:46:06 +08001292static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
Josef Bacik96303082009-07-13 21:29:25 -04001293{
Li Zefan34d52cb2011-03-29 13:46:06 +08001294 return (unsigned long)(div_u64(bytes, unit));
Josef Bacik96303082009-07-13 21:29:25 -04001295}
1296
Li Zefan34d52cb2011-03-29 13:46:06 +08001297static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
Josef Bacik96303082009-07-13 21:29:25 -04001298 u64 offset)
1299{
1300 u64 bitmap_start;
1301 u64 bytes_per_bitmap;
1302
Li Zefan34d52cb2011-03-29 13:46:06 +08001303 bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
1304 bitmap_start = offset - ctl->start;
Josef Bacik96303082009-07-13 21:29:25 -04001305 bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
1306 bitmap_start *= bytes_per_bitmap;
Li Zefan34d52cb2011-03-29 13:46:06 +08001307 bitmap_start += ctl->start;
Josef Bacik96303082009-07-13 21:29:25 -04001308
1309 return bitmap_start;
1310}
Josef Bacik0f9dd462008-09-23 13:14:11 -04001311
1312static int tree_insert_offset(struct rb_root *root, u64 offset,
Josef Bacik96303082009-07-13 21:29:25 -04001313 struct rb_node *node, int bitmap)
Josef Bacik0f9dd462008-09-23 13:14:11 -04001314{
1315 struct rb_node **p = &root->rb_node;
1316 struct rb_node *parent = NULL;
1317 struct btrfs_free_space *info;
1318
1319 while (*p) {
1320 parent = *p;
1321 info = rb_entry(parent, struct btrfs_free_space, offset_index);
1322
Josef Bacik96303082009-07-13 21:29:25 -04001323 if (offset < info->offset) {
Josef Bacik0f9dd462008-09-23 13:14:11 -04001324 p = &(*p)->rb_left;
Josef Bacik96303082009-07-13 21:29:25 -04001325 } else if (offset > info->offset) {
Josef Bacik0f9dd462008-09-23 13:14:11 -04001326 p = &(*p)->rb_right;
Josef Bacik96303082009-07-13 21:29:25 -04001327 } else {
1328 /*
1329 * we could have a bitmap entry and an extent entry
1330 * share the same offset. If this is the case, we want
1331 * the extent entry to always be found first if we do a
1332 * linear search through the tree, since we want to have
1333 * the quickest allocation time, and allocating from an
1334 * extent is faster than allocating from a bitmap. So
1335 * if we're inserting a bitmap and we find an entry at
1336 * this offset, we want to go right, or after this entry
1337 * logically. If we are inserting an extent and we've
1338 * found a bitmap, we want to go left, or before
1339 * logically.
1340 */
1341 if (bitmap) {
Josef Bacik207dde82011-05-13 14:49:23 -04001342 if (info->bitmap) {
1343 WARN_ON_ONCE(1);
1344 return -EEXIST;
1345 }
Josef Bacik96303082009-07-13 21:29:25 -04001346 p = &(*p)->rb_right;
1347 } else {
Josef Bacik207dde82011-05-13 14:49:23 -04001348 if (!info->bitmap) {
1349 WARN_ON_ONCE(1);
1350 return -EEXIST;
1351 }
Josef Bacik96303082009-07-13 21:29:25 -04001352 p = &(*p)->rb_left;
1353 }
1354 }
Josef Bacik0f9dd462008-09-23 13:14:11 -04001355 }
1356
1357 rb_link_node(node, parent, p);
1358 rb_insert_color(node, root);
1359
1360 return 0;
1361}
1362
1363/*
Josef Bacik70cb0742009-04-03 10:14:19 -04001364 * searches the tree for the given offset.
1365 *
Josef Bacik96303082009-07-13 21:29:25 -04001366 * fuzzy - If this is set, then we are trying to make an allocation, and we just
1367 * want a section that has at least bytes size and comes at or after the given
1368 * offset.
Josef Bacik0f9dd462008-09-23 13:14:11 -04001369 */
Josef Bacik96303082009-07-13 21:29:25 -04001370static struct btrfs_free_space *
Li Zefan34d52cb2011-03-29 13:46:06 +08001371tree_search_offset(struct btrfs_free_space_ctl *ctl,
Josef Bacik96303082009-07-13 21:29:25 -04001372 u64 offset, int bitmap_only, int fuzzy)
Josef Bacik0f9dd462008-09-23 13:14:11 -04001373{
Li Zefan34d52cb2011-03-29 13:46:06 +08001374 struct rb_node *n = ctl->free_space_offset.rb_node;
Josef Bacik96303082009-07-13 21:29:25 -04001375 struct btrfs_free_space *entry, *prev = NULL;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001376
Josef Bacik96303082009-07-13 21:29:25 -04001377 /* find entry that is closest to the 'offset' */
1378 while (1) {
1379 if (!n) {
1380 entry = NULL;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001381 break;
1382 }
Josef Bacik96303082009-07-13 21:29:25 -04001383
1384 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1385 prev = entry;
1386
1387 if (offset < entry->offset)
1388 n = n->rb_left;
1389 else if (offset > entry->offset)
1390 n = n->rb_right;
1391 else
1392 break;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001393 }
1394
Josef Bacik96303082009-07-13 21:29:25 -04001395 if (bitmap_only) {
1396 if (!entry)
1397 return NULL;
1398 if (entry->bitmap)
1399 return entry;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001400
Josef Bacik96303082009-07-13 21:29:25 -04001401 /*
1402 * bitmap entry and extent entry may share same offset,
1403 * in that case, bitmap entry comes after extent entry.
1404 */
1405 n = rb_next(n);
1406 if (!n)
1407 return NULL;
1408 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1409 if (entry->offset != offset)
1410 return NULL;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001411
Josef Bacik96303082009-07-13 21:29:25 -04001412 WARN_ON(!entry->bitmap);
1413 return entry;
1414 } else if (entry) {
1415 if (entry->bitmap) {
Josef Bacik0f9dd462008-09-23 13:14:11 -04001416 /*
Josef Bacik96303082009-07-13 21:29:25 -04001417 * if previous extent entry covers the offset,
1418 * we should return it instead of the bitmap entry
Josef Bacik0f9dd462008-09-23 13:14:11 -04001419 */
Miao Xiede6c4112012-10-18 08:18:01 +00001420 n = rb_prev(&entry->offset_index);
1421 if (n) {
Josef Bacik96303082009-07-13 21:29:25 -04001422 prev = rb_entry(n, struct btrfs_free_space,
1423 offset_index);
Miao Xiede6c4112012-10-18 08:18:01 +00001424 if (!prev->bitmap &&
1425 prev->offset + prev->bytes > offset)
1426 entry = prev;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001427 }
Josef Bacik96303082009-07-13 21:29:25 -04001428 }
1429 return entry;
1430 }
1431
1432 if (!prev)
1433 return NULL;
1434
1435 /* find last entry before the 'offset' */
1436 entry = prev;
1437 if (entry->offset > offset) {
1438 n = rb_prev(&entry->offset_index);
1439 if (n) {
1440 entry = rb_entry(n, struct btrfs_free_space,
1441 offset_index);
Josef Bacikb12d6862013-08-26 17:14:08 -04001442 ASSERT(entry->offset <= offset);
Josef Bacik0f9dd462008-09-23 13:14:11 -04001443 } else {
Josef Bacik96303082009-07-13 21:29:25 -04001444 if (fuzzy)
1445 return entry;
1446 else
1447 return NULL;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001448 }
1449 }
1450
Josef Bacik96303082009-07-13 21:29:25 -04001451 if (entry->bitmap) {
Miao Xiede6c4112012-10-18 08:18:01 +00001452 n = rb_prev(&entry->offset_index);
1453 if (n) {
Josef Bacik96303082009-07-13 21:29:25 -04001454 prev = rb_entry(n, struct btrfs_free_space,
1455 offset_index);
Miao Xiede6c4112012-10-18 08:18:01 +00001456 if (!prev->bitmap &&
1457 prev->offset + prev->bytes > offset)
1458 return prev;
Josef Bacik96303082009-07-13 21:29:25 -04001459 }
Li Zefan34d52cb2011-03-29 13:46:06 +08001460 if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
Josef Bacik96303082009-07-13 21:29:25 -04001461 return entry;
1462 } else if (entry->offset + entry->bytes > offset)
1463 return entry;
1464
1465 if (!fuzzy)
1466 return NULL;
1467
1468 while (1) {
1469 if (entry->bitmap) {
1470 if (entry->offset + BITS_PER_BITMAP *
Li Zefan34d52cb2011-03-29 13:46:06 +08001471 ctl->unit > offset)
Josef Bacik96303082009-07-13 21:29:25 -04001472 break;
1473 } else {
1474 if (entry->offset + entry->bytes > offset)
1475 break;
1476 }
1477
1478 n = rb_next(&entry->offset_index);
1479 if (!n)
1480 return NULL;
1481 entry = rb_entry(n, struct btrfs_free_space, offset_index);
1482 }
1483 return entry;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001484}
1485
Li Zefanf333adb2010-11-09 14:57:39 +08001486static inline void
Li Zefan34d52cb2011-03-29 13:46:06 +08001487__unlink_free_space(struct btrfs_free_space_ctl *ctl,
Li Zefanf333adb2010-11-09 14:57:39 +08001488 struct btrfs_free_space *info)
Josef Bacik0f9dd462008-09-23 13:14:11 -04001489{
Li Zefan34d52cb2011-03-29 13:46:06 +08001490 rb_erase(&info->offset_index, &ctl->free_space_offset);
1491 ctl->free_extents--;
Li Zefanf333adb2010-11-09 14:57:39 +08001492}
1493
Li Zefan34d52cb2011-03-29 13:46:06 +08001494static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
Li Zefanf333adb2010-11-09 14:57:39 +08001495 struct btrfs_free_space *info)
1496{
Li Zefan34d52cb2011-03-29 13:46:06 +08001497 __unlink_free_space(ctl, info);
1498 ctl->free_space -= info->bytes;
Josef Bacik0f9dd462008-09-23 13:14:11 -04001499}
1500
Li Zefan34d52cb2011-03-29 13:46:06 +08001501static int link_free_space(struct btrfs_free_space_ctl *ctl,
Josef Bacik0f9dd462008-09-23 13:14:11 -04001502 struct btrfs_free_space *info)
1503{
1504 int ret = 0;
1505
Josef Bacikb12d6862013-08-26 17:14:08 -04001506 ASSERT(info->bytes || info->bitmap);
Li Zefan34d52cb2011-03-29 13:46:06 +08001507 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
Josef Bacik96303082009-07-13 21:29:25 -04001508 &info->offset_index, (info->bitmap != NULL));
Josef Bacik0f9dd462008-09-23 13:14:11 -04001509 if (ret)
1510 return ret;
1511
Li Zefan34d52cb2011-03-29 13:46:06 +08001512 ctl->free_space += info->bytes;
1513 ctl->free_extents++;
Josef Bacik96303082009-07-13 21:29:25 -04001514 return ret;
1515}
1516
Li Zefan34d52cb2011-03-29 13:46:06 +08001517static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
Josef Bacik96303082009-07-13 21:29:25 -04001518{
Li Zefan34d52cb2011-03-29 13:46:06 +08001519 struct btrfs_block_group_cache *block_group = ctl->private;
Josef Bacik25891f72009-09-11 16:11:20 -04001520 u64 max_bytes;
1521 u64 bitmap_bytes;
1522 u64 extent_bytes;
Li Zefan8eb2d822010-11-09 14:48:01 +08001523 u64 size = block_group->key.offset;
Wang Sheng-Hui96009762012-11-30 06:30:14 +00001524 u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
Li Zefan34d52cb2011-03-29 13:46:06 +08001525 int max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
1526
Josef Bacikdde57402013-02-12 14:07:51 -05001527 max_bitmaps = max(max_bitmaps, 1);
1528
Josef Bacikb12d6862013-08-26 17:14:08 -04001529 ASSERT(ctl->total_bitmaps <= max_bitmaps);
Josef Bacik96303082009-07-13 21:29:25 -04001530
1531 /*
1532 * The goal is to keep the total amount of memory used per 1gb of space
1533 * at or below 32k, so we need to adjust how much memory we allow to be
1534 * used by extent based free space tracking
1535 */
Li Zefan8eb2d822010-11-09 14:48:01 +08001536 if (size < 1024 * 1024 * 1024)
1537 max_bytes = MAX_CACHE_BYTES_PER_GIG;
1538 else
1539 max_bytes = MAX_CACHE_BYTES_PER_GIG *
1540 div64_u64(size, 1024 * 1024 * 1024);
Josef Bacik96303082009-07-13 21:29:25 -04001541
Josef Bacik25891f72009-09-11 16:11:20 -04001542 /*
1543 * we want to account for 1 more bitmap than what we have so we can make
1544 * sure we don't go over our overall goal of MAX_CACHE_BYTES_PER_GIG as
1545 * we add more bitmaps.
1546 */
Li Zefan34d52cb2011-03-29 13:46:06 +08001547 bitmap_bytes = (ctl->total_bitmaps + 1) * PAGE_CACHE_SIZE;
Josef Bacik96303082009-07-13 21:29:25 -04001548
Josef Bacik25891f72009-09-11 16:11:20 -04001549 if (bitmap_bytes >= max_bytes) {
Li Zefan34d52cb2011-03-29 13:46:06 +08001550 ctl->extents_thresh = 0;
Josef Bacik25891f72009-09-11 16:11:20 -04001551 return;
Josef Bacik96303082009-07-13 21:29:25 -04001552 }
Josef Bacik25891f72009-09-11 16:11:20 -04001553
1554 /*
1555 * we want the extent entry threshold to always be at most 1/2 the maxw
1556 * bytes we can have, or whatever is less than that.
1557 */
1558 extent_bytes = max_bytes - bitmap_bytes;
1559 extent_bytes = min_t(u64, extent_bytes, div64_u64(max_bytes, 2));
1560
Li Zefan34d52cb2011-03-29 13:46:06 +08001561 ctl->extents_thresh =
Josef Bacik25891f72009-09-11 16:11:20 -04001562 div64_u64(extent_bytes, (sizeof(struct btrfs_free_space)));
Josef Bacik96303082009-07-13 21:29:25 -04001563}
1564
Miao Xiebb3ac5a2011-08-05 09:32:35 +00001565static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1566 struct btrfs_free_space *info,
1567 u64 offset, u64 bytes)
Josef Bacik96303082009-07-13 21:29:25 -04001568{
Li Zefanf38b6e72011-03-14 13:40:51 +08001569 unsigned long start, count;
Josef Bacik96303082009-07-13 21:29:25 -04001570
Li Zefan34d52cb2011-03-29 13:46:06 +08001571 start = offset_to_bit(info->offset, ctl->unit, offset);
1572 count = bytes_to_bits(bytes, ctl->unit);
Josef Bacikb12d6862013-08-26 17:14:08 -04001573 ASSERT(start + count <= BITS_PER_BITMAP);
Josef Bacik96303082009-07-13 21:29:25 -04001574
Li Zefanf38b6e72011-03-14 13:40:51 +08001575 bitmap_clear(info->bitmap, start, count);
Josef Bacik96303082009-07-13 21:29:25 -04001576
1577 info->bytes -= bytes;
Miao Xiebb3ac5a2011-08-05 09:32:35 +00001578}
1579
1580static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1581 struct btrfs_free_space *info, u64 offset,
1582 u64 bytes)
1583{
1584 __bitmap_clear_bits(ctl, info, offset, bytes);
Li Zefan34d52cb2011-03-29 13:46:06 +08001585 ctl->free_space -= bytes;
Josef Bacik96303082009-07-13 21:29:25 -04001586}
1587
Li Zefan34d52cb2011-03-29 13:46:06 +08001588static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
Josef Bacik817d52f2009-07-13 21:29:25 -04001589 struct btrfs_free_space *info, u64 offset,
1590 u64 bytes)
Josef Bacik96303082009-07-13 21:29:25 -04001591{
Li Zefanf38b6e72011-03-14 13:40:51 +08001592 unsigned long start, count;
Josef Bacik96303082009-07-13 21:29:25 -04001593
Li Zefan34d52cb2011-03-29 13:46:06 +08001594 start = offset_to_bit(info->offset, ctl->unit, offset);
1595 count = bytes_to_bits(bytes, ctl->unit);
Josef Bacikb12d6862013-08-26 17:14:08 -04001596 ASSERT(start + count <= BITS_PER_BITMAP);
Josef Bacik96303082009-07-13 21:29:25 -04001597
Li Zefanf38b6e72011-03-14 13:40:51 +08001598 bitmap_set(info->bitmap, start, count);
Josef Bacik96303082009-07-13 21:29:25 -04001599
1600 info->bytes += bytes;
Li Zefan34d52cb2011-03-29 13:46:06 +08001601 ctl->free_space += bytes;
Josef Bacik96303082009-07-13 21:29:25 -04001602}
1603
Miao Xiea4820392013-09-09 13:19:42 +08001604/*
1605 * If we can not find suitable extent, we will use bytes to record
1606 * the size of the max extent.
1607 */
Li Zefan34d52cb2011-03-29 13:46:06 +08001608static int search_bitmap(struct btrfs_free_space_ctl *ctl,
Josef Bacik96303082009-07-13 21:29:25 -04001609 struct btrfs_free_space *bitmap_info, u64 *offset,
1610 u64 *bytes)
1611{
1612 unsigned long found_bits = 0;
Miao Xiea4820392013-09-09 13:19:42 +08001613 unsigned long max_bits = 0;
Josef Bacik96303082009-07-13 21:29:25 -04001614 unsigned long bits, i;
1615 unsigned long next_zero;
Miao Xiea4820392013-09-09 13:19:42 +08001616 unsigned long extent_bits;
Josef Bacik96303082009-07-13 21:29:25 -04001617
Li Zefan34d52cb2011-03-29 13:46:06 +08001618 i = offset_to_bit(bitmap_info->offset, ctl->unit,
Josef Bacik96303082009-07-13 21:29:25 -04001619 max_t(u64, *offset, bitmap_info->offset));
Li Zefan34d52cb2011-03-29 13:46:06 +08001620 bits = bytes_to_bits(*bytes, ctl->unit);
Josef Bacik96303082009-07-13 21:29:25 -04001621
Wei Yongjunebb3dad2012-09-13 20:29:02 -06001622 for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
Josef Bacik96303082009-07-13 21:29:25 -04001623 next_zero = find_next_zero_bit(bitmap_info->bitmap,
1624 BITS_PER_BITMAP, i);
Miao Xiea4820392013-09-09 13:19:42 +08001625 extent_bits = next_zero - i;
1626 if (extent_bits >= bits) {
1627 found_bits = extent_bits;
Josef Bacik96303082009-07-13 21:29:25 -04001628 break;
Miao Xiea4820392013-09-09 13:19:42 +08001629 } else if (extent_bits > max_bits) {
1630 max_bits = extent_bits;
Josef Bacik96303082009-07-13 21:29:25 -04001631 }
1632 i = next_zero;
1633 }
1634
1635 if (found_bits) {
Li Zefan34d52cb2011-03-29 13:46:06 +08001636 *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
1637 *bytes = (u64)(found_bits) * ctl->unit;
Josef Bacik96303082009-07-13 21:29:25 -04001638 return 0;
1639 }
1640
Miao Xiea4820392013-09-09 13:19:42 +08001641 *bytes = (u64)(max_bits) * ctl->unit;
Josef Bacik96303082009-07-13 21:29:25 -04001642 return -1;
1643}
1644
Miao Xiea4820392013-09-09 13:19:42 +08001645/* Cache the size of the max extent in bytes */
Li Zefan34d52cb2011-03-29 13:46:06 +08001646static struct btrfs_free_space *
David Woodhouse53b381b2013-01-29 18:40:14 -05001647find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
Miao Xiea4820392013-09-09 13:19:42 +08001648 unsigned long align, u64 *max_extent_size)
Josef Bacik96303082009-07-13 21:29:25 -04001649{
1650 struct btrfs_free_space *entry;
1651 struct rb_node *node;
David Woodhouse53b381b2013-01-29 18:40:14 -05001652 u64 tmp;
1653 u64 align_off;
Josef Bacik96303082009-07-13 21:29:25 -04001654 int ret;
1655
Li Zefan34d52cb2011-03-29 13:46:06 +08001656 if (!ctl->free_space_offset.rb_node)
Miao Xiea4820392013-09-09 13:19:42 +08001657 goto out;
Josef Bacik96303082009-07-13 21:29:25 -04001658
Li Zefan34d52cb2011-03-29 13:46:06 +08001659 entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
Josef Bacik96303082009-07-13 21:29:25 -04001660 if (!entry)
Miao Xiea4820392013-09-09 13:19:42 +08001661 goto out;
Josef Bacik96303082009-07-13 21:29:25 -04001662
1663 for (node = &entry->offset_index; node; node = rb_next(node)) {
1664 entry = rb_entry(node, struct btrfs_free_space, offset_index);
Miao Xiea4820392013-09-09 13:19:42 +08001665 if (entry->bytes < *bytes) {
1666 if (entry->bytes > *max_extent_size)
1667 *max_extent_size = entry->bytes;
Josef Bacik96303082009-07-13 21:29:25 -04001668 continue;
Miao Xiea4820392013-09-09 13:19:42 +08001669 }
Josef Bacik96303082009-07-13 21:29:25 -04001670
David Woodhouse53b381b2013-01-29 18:40:14 -05001671 /* make sure the space returned is big enough
1672 * to match our requested alignment
1673 */
1674 if (*bytes >= align) {
Miao Xiea4820392013-09-09 13:19:42 +08001675 tmp = entry->offset - ctl->start + align - 1;
David Woodhouse53b381b2013-01-29 18:40:14 -05001676 do_div(tmp, align);
1677 tmp = tmp * align + ctl->start;
1678 align_off = tmp - entry->offset;
1679 } else {
1680 align_off = 0;
1681 tmp = entry->offset;
1682 }
1683
Miao Xiea4820392013-09-09 13:19:42 +08001684 if (entry->bytes < *bytes + align_off) {
1685 if (entry->bytes > *max_extent_size)
1686 *max_extent_size = entry->bytes;
David Woodhouse53b381b2013-01-29 18:40:14 -05001687 continue;
Miao Xiea4820392013-09-09 13:19:42 +08001688 }
David Woodhouse53b381b2013-01-29 18:40:14 -05001689
Josef Bacik96303082009-07-13 21:29:25 -04001690 if (entry->bitmap) {
Miao Xiea4820392013-09-09 13:19:42 +08001691 u64 size = *bytes;
1692
1693 ret = search_bitmap(ctl, entry, &tmp, &size);
David Woodhouse53b381b2013-01-29 18:40:14 -05001694 if (!ret) {
1695 *offset = tmp;
Miao Xiea4820392013-09-09 13:19:42 +08001696 *bytes = size;
Josef Bacik96303082009-07-13 21:29:25 -04001697 return entry;
Miao Xiea4820392013-09-09 13:19:42 +08001698 } else if (size > *max_extent_size) {
1699 *max_extent_size = size;
David Woodhouse53b381b2013-01-29 18:40:14 -05001700 }
Josef Bacik96303082009-07-13 21:29:25 -04001701 continue;
1702 }
1703
David Woodhouse53b381b2013-01-29 18:40:14 -05001704 *offset = tmp;
1705 *bytes = entry->bytes - align_off;
Josef Bacik96303082009-07-13 21:29:25 -04001706 return entry;
1707 }
Miao Xiea4820392013-09-09 13:19:42 +08001708out:
Josef Bacik96303082009-07-13 21:29:25 -04001709 return NULL;
1710}
1711
Li Zefan34d52cb2011-03-29 13:46:06 +08001712static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
Josef Bacik96303082009-07-13 21:29:25 -04001713 struct btrfs_free_space *info, u64 offset)
1714{
Li Zefan34d52cb2011-03-29 13:46:06 +08001715 info->offset = offset_to_bitmap(ctl, offset);
Josef Bacikf019f422009-09-11 16:11:20 -04001716 info->bytes = 0;
Alexandre Olivaf2d0f672011-11-28 12:04:43 -02001717 INIT_LIST_HEAD(&info->list);
Li Zefan34d52cb2011-03-29 13:46:06 +08001718 link_free_space(ctl, info);
1719 ctl->total_bitmaps++;
Josef Bacik96303082009-07-13 21:29:25 -04001720
Li Zefan34d52cb2011-03-29 13:46:06 +08001721 ctl->op->recalc_thresholds(ctl);
Josef Bacik96303082009-07-13 21:29:25 -04001722}
1723
Li Zefan34d52cb2011-03-29 13:46:06 +08001724static void free_bitmap(struct btrfs_free_space_ctl *ctl,
Li Zefanedf6e2d2010-11-09 14:50:07 +08001725 struct btrfs_free_space *bitmap_info)
1726{
Li Zefan34d52cb2011-03-29 13:46:06 +08001727 unlink_free_space(ctl, bitmap_info);
Li Zefanedf6e2d2010-11-09 14:50:07 +08001728 kfree(bitmap_info->bitmap);
Josef Bacikdc89e982011-01-28 17:05:48 -05001729 kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
Li Zefan34d52cb2011-03-29 13:46:06 +08001730 ctl->total_bitmaps--;
1731 ctl->op->recalc_thresholds(ctl);
Li Zefanedf6e2d2010-11-09 14:50:07 +08001732}
1733
Li Zefan34d52cb2011-03-29 13:46:06 +08001734static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
Josef Bacik96303082009-07-13 21:29:25 -04001735 struct btrfs_free_space *bitmap_info,
1736 u64 *offset, u64 *bytes)
1737{
1738 u64 end;
Josef Bacik6606bb92009-07-31 11:03:58 -04001739 u64 search_start, search_bytes;
1740 int ret;
Josef Bacik96303082009-07-13 21:29:25 -04001741
1742again:
Li Zefan34d52cb2011-03-29 13:46:06 +08001743 end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
Josef Bacik96303082009-07-13 21:29:25 -04001744
Josef Bacik6606bb92009-07-31 11:03:58 -04001745 /*
Josef Bacikbdb7d302012-06-27 15:10:56 -04001746 * We need to search for bits in this bitmap. We could only cover some
1747 * of the extent in this bitmap thanks to how we add space, so we need
1748 * to search for as much as it as we can and clear that amount, and then
1749 * go searching for the next bit.
Josef Bacik6606bb92009-07-31 11:03:58 -04001750 */
1751 search_start = *offset;
Josef Bacikbdb7d302012-06-27 15:10:56 -04001752 search_bytes = ctl->unit;
Josef Bacik13dbc082011-02-03 02:39:52 +00001753 search_bytes = min(search_bytes, end - search_start + 1);
Li Zefan34d52cb2011-03-29 13:46:06 +08001754 ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes);
Josef Bacikb50c6e22013-04-25 15:55:30 -04001755 if (ret < 0 || search_start != *offset)
1756 return -EINVAL;
Josef Bacik6606bb92009-07-31 11:03:58 -04001757
Josef Bacikbdb7d302012-06-27 15:10:56 -04001758 /* We may have found more bits than what we need */
1759 search_bytes = min(search_bytes, *bytes);
1760
1761 /* Cannot clear past the end of the bitmap */
1762 search_bytes = min(search_bytes, end - search_start + 1);
1763
1764 bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes);
1765 *offset += search_bytes;
1766 *bytes -= search_bytes;
Josef Bacik96303082009-07-13 21:29:25 -04001767
1768 if (*bytes) {
Josef Bacik6606bb92009-07-31 11:03:58 -04001769 struct rb_node *next = rb_next(&bitmap_info->offset_index);
Li Zefanedf6e2d2010-11-09 14:50:07 +08001770 if (!bitmap_info->bytes)
Li Zefan34d52cb2011-03-29 13:46:06 +08001771 free_bitmap(ctl, bitmap_info);
Josef Bacik96303082009-07-13 21:29:25 -04001772
Josef Bacik6606bb92009-07-31 11:03:58 -04001773 /*
1774 * no entry after this bitmap, but we still have bytes to
1775 * remove, so something has gone wrong.
1776 */
1777 if (!next)
Josef Bacik96303082009-07-13 21:29:25 -04001778 return -EINVAL;
1779
Josef Bacik6606bb92009-07-31 11:03:58 -04001780 bitmap_info = rb_entry(next, struct btrfs_free_space,
1781 offset_index);
1782
1783 /*
1784 * if the next entry isn't a bitmap we need to return to let the
1785 * extent stuff do its work.
1786 */
Josef Bacik96303082009-07-13 21:29:25 -04001787 if (!bitmap_info->bitmap)
1788 return -EAGAIN;
1789
Josef Bacik6606bb92009-07-31 11:03:58 -04001790 /*
1791 * Ok the next item is a bitmap, but it may not actually hold
1792 * the information for the rest of this free space stuff, so
1793 * look for it, and if we don't find it return so we can try
1794 * everything over again.
1795 */
1796 search_start = *offset;
Josef Bacikbdb7d302012-06-27 15:10:56 -04001797 search_bytes = ctl->unit;
Li Zefan34d52cb2011-03-29 13:46:06 +08001798 ret = search_bitmap(ctl, bitmap_info, &search_start,
Josef Bacik6606bb92009-07-31 11:03:58 -04001799 &search_bytes);
1800 if (ret < 0 || search_start != *offset)
1801 return -EAGAIN;
1802
Josef Bacik96303082009-07-13 21:29:25 -04001803 goto again;
Li Zefanedf6e2d2010-11-09 14:50:07 +08001804 } else if (!bitmap_info->bytes)
Li Zefan34d52cb2011-03-29 13:46:06 +08001805 free_bitmap(ctl, bitmap_info);
Josef Bacik96303082009-07-13 21:29:25 -04001806
1807 return 0;
1808}
1809
Josef Bacik2cdc3422011-05-27 14:07:49 -04001810static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
1811 struct btrfs_free_space *info, u64 offset,
1812 u64 bytes)
1813{
1814 u64 bytes_to_set = 0;
1815 u64 end;
1816
1817 end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
1818
1819 bytes_to_set = min(end - offset, bytes);
1820
1821 bitmap_set_bits(ctl, info, offset, bytes_to_set);
1822
1823 return bytes_to_set;
1824
1825}
1826
Li Zefan34d52cb2011-03-29 13:46:06 +08001827static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
1828 struct btrfs_free_space *info)
Josef Bacik96303082009-07-13 21:29:25 -04001829{
Li Zefan34d52cb2011-03-29 13:46:06 +08001830 struct btrfs_block_group_cache *block_group = ctl->private;
Josef Bacik96303082009-07-13 21:29:25 -04001831
1832 /*
1833 * If we are below the extents threshold then we can add this as an
1834 * extent, and don't have to deal with the bitmap
1835 */
Li Zefan34d52cb2011-03-29 13:46:06 +08001836 if (ctl->free_extents < ctl->extents_thresh) {
Josef Bacik32cb0842011-03-18 16:16:21 -04001837 /*
1838 * If this block group has some small extents we don't want to
1839 * use up all of our free slots in the cache with them, we want
1840 * to reserve them to larger extents, however if we have plent
1841 * of cache left then go ahead an dadd them, no sense in adding
1842 * the overhead of a bitmap if we don't have to.
1843 */
1844 if (info->bytes <= block_group->sectorsize * 4) {
Li Zefan34d52cb2011-03-29 13:46:06 +08001845 if (ctl->free_extents * 2 <= ctl->extents_thresh)
1846 return false;
Josef Bacik32cb0842011-03-18 16:16:21 -04001847 } else {
Li Zefan34d52cb2011-03-29 13:46:06 +08001848 return false;
Josef Bacik32cb0842011-03-18 16:16:21 -04001849 }
1850 }
Josef Bacik96303082009-07-13 21:29:25 -04001851
1852 /*
Josef Bacikdde57402013-02-12 14:07:51 -05001853 * The original block groups from mkfs can be really small, like 8
1854 * megabytes, so don't bother with a bitmap for those entries. However
1855 * some block groups can be smaller than what a bitmap would cover but
1856 * are still large enough that they could overflow the 32k memory limit,
1857 * so allow those block groups to still be allowed to have a bitmap
1858 * entry.
Josef Bacik96303082009-07-13 21:29:25 -04001859 */
Josef Bacikdde57402013-02-12 14:07:51 -05001860 if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->key.offset)
Li Zefan34d52cb2011-03-29 13:46:06 +08001861 return false;
1862
1863 return true;
1864}
1865
Josef Bacik2cdc3422011-05-27 14:07:49 -04001866static struct btrfs_free_space_op free_space_op = {
1867 .recalc_thresholds = recalculate_thresholds,
1868 .use_bitmap = use_bitmap,
1869};
1870
Li Zefan34d52cb2011-03-29 13:46:06 +08001871static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
1872 struct btrfs_free_space *info)
1873{
1874 struct btrfs_free_space *bitmap_info;
Josef Bacik2cdc3422011-05-27 14:07:49 -04001875 struct btrfs_block_group_cache *block_group = NULL;
Li Zefan34d52cb2011-03-29 13:46:06 +08001876 int added = 0;
Josef Bacik2cdc3422011-05-27 14:07:49 -04001877 u64 bytes, offset, bytes_added;
Li Zefan34d52cb2011-03-29 13:46:06 +08001878 int ret;
Josef Bacik96303082009-07-13 21:29:25 -04001879
1880 bytes = info->bytes;
1881 offset = info->offset;
1882
Li Zefan34d52cb2011-03-29 13:46:06 +08001883 if (!ctl->op->use_bitmap(ctl, info))
1884 return 0;
1885
Josef Bacik2cdc3422011-05-27 14:07:49 -04001886 if (ctl->op == &free_space_op)
1887 block_group = ctl->private;
Chris Mason38e87882011-06-10 16:36:57 -04001888again:
Josef Bacik2cdc3422011-05-27 14:07:49 -04001889 /*
1890 * Since we link bitmaps right into the cluster we need to see if we
1891 * have a cluster here, and if so and it has our bitmap we need to add
1892 * the free space to that bitmap.
1893 */
1894 if (block_group && !list_empty(&block_group->cluster_list)) {
1895 struct btrfs_free_cluster *cluster;
1896 struct rb_node *node;
1897 struct btrfs_free_space *entry;
1898
1899 cluster = list_entry(block_group->cluster_list.next,
1900 struct btrfs_free_cluster,
1901 block_group_list);
1902 spin_lock(&cluster->lock);
1903 node = rb_first(&cluster->root);
1904 if (!node) {
1905 spin_unlock(&cluster->lock);
Chris Mason38e87882011-06-10 16:36:57 -04001906 goto no_cluster_bitmap;
Josef Bacik2cdc3422011-05-27 14:07:49 -04001907 }
1908
1909 entry = rb_entry(node, struct btrfs_free_space, offset_index);
1910 if (!entry->bitmap) {
1911 spin_unlock(&cluster->lock);
Chris Mason38e87882011-06-10 16:36:57 -04001912 goto no_cluster_bitmap;
Josef Bacik2cdc3422011-05-27 14:07:49 -04001913 }
1914
1915 if (entry->offset == offset_to_bitmap(ctl, offset)) {
1916 bytes_added = add_bytes_to_bitmap(ctl, entry,
1917 offset, bytes);
1918 bytes -= bytes_added;
1919 offset += bytes_added;
1920 }
1921 spin_unlock(&cluster->lock);
1922 if (!bytes) {
1923 ret = 1;
1924 goto out;
1925 }
1926 }
Chris Mason38e87882011-06-10 16:36:57 -04001927
1928no_cluster_bitmap:
Li Zefan34d52cb2011-03-29 13:46:06 +08001929 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
Josef Bacik96303082009-07-13 21:29:25 -04001930 1, 0);
1931 if (!bitmap_info) {
Josef Bacikb12d6862013-08-26 17:14:08 -04001932 ASSERT(added == 0);
Josef Bacik96303082009-07-13 21:29:25 -04001933 goto new_bitmap;
1934 }
1935
Josef Bacik2cdc3422011-05-27 14:07:49 -04001936 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
1937 bytes -= bytes_added;
1938 offset += bytes_added;
1939 added = 0;
Josef Bacik96303082009-07-13 21:29:25 -04001940
1941 if (!bytes) {
1942 ret = 1;
1943 goto out;
1944 } else
1945 goto again;
1946
1947new_bitmap:
1948 if (info && info->bitmap) {
Li Zefan34d52cb2011-03-29 13:46:06 +08001949 add_new_bitmap(ctl, info, offset);
Josef Bacik96303082009-07-13 21:29:25 -04001950 added = 1;
1951 info = NULL;
1952 goto again;
1953 } else {
Li Zefan34d52cb2011-03-29 13:46:06 +08001954 spin_unlock(&ctl->tree_lock);
Josef Bacik96303082009-07-13 21:29:25 -04001955
1956 /* no pre-allocated info, allocate a new one */
1957 if (!info) {
Josef Bacikdc89e982011-01-28 17:05:48 -05001958 info = kmem_cache_zalloc(btrfs_free_space_cachep,
1959 GFP_NOFS);
Josef Bacik96303082009-07-13 21:29:25 -04001960 if (!info) {
Li Zefan34d52cb2011-03-29 13:46:06 +08001961 spin_lock(&ctl->tree_lock);
Josef Bacik96303082009-07-13 21:29:25 -04001962 ret = -ENOMEM;
1963 goto out;
1964 }
1965 }
1966
1967 /* allocate the bitmap */
1968 info->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
Li Zefan34d52cb2011-03-29 13:46:06 +08001969 spin_lock(&ctl->tree_lock);
Josef Bacik96303082009-07-13 21:29:25 -04001970 if (!info->bitmap) {
1971 ret = -ENOMEM;
1972 goto out;
1973 }
1974 goto again;
1975 }
1976
1977out:
1978 if (info) {
1979 if (info->bitmap)
1980 kfree(info->bitmap);
Josef Bacikdc89e982011-01-28 17:05:48 -05001981 kmem_cache_free(btrfs_free_space_cachep, info);
Josef Bacik96303082009-07-13 21:29:25 -04001982 }
Josef Bacik0f9dd462008-09-23 13:14:11 -04001983
1984 return ret;
1985}
1986
Chris Mason945d8962011-05-22 12:33:42 -04001987static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
Li Zefanf333adb2010-11-09 14:57:39 +08001988 struct btrfs_free_space *info, bool update_stat)
Josef Bacik0f9dd462008-09-23 13:14:11 -04001989{
Li Zefan120d66e2010-11-09 14:56:50 +08001990 struct btrfs_free_space *left_info;
1991 struct btrfs_free_space *right_info;
1992 bool merged = false;
1993 u64 offset = info->offset;
1994 u64 bytes = info->bytes;
Josef Bacik6226cb0a2009-04-03 10:14:18 -04001995
Josef Bacik0f9dd462008-09-23 13:14:11 -04001996 /*
1997 * first we want to see if there is free space adjacent to the range we
1998 * are adding, if there is remove that struct and add a new one to
1999 * cover the entire range
2000 */
Li Zefan34d52cb2011-03-29 13:46:06 +08002001 right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
Josef Bacik96303082009-07-13 21:29:25 -04002002 if (right_info && rb_prev(&right_info->offset_index))
2003 left_info = rb_entry(rb_prev(&right_info->offset_index),
2004 struct btrfs_free_space, offset_index);
2005 else
Li Zefan34d52cb2011-03-29 13:46:06 +08002006 left_info = tree_search_offset(ctl, offset - 1, 0, 0);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002007
Josef Bacik96303082009-07-13 21:29:25 -04002008 if (right_info && !right_info->bitmap) {
Li Zefanf333adb2010-11-09 14:57:39 +08002009 if (update_stat)
Li Zefan34d52cb2011-03-29 13:46:06 +08002010 unlink_free_space(ctl, right_info);
Li Zefanf333adb2010-11-09 14:57:39 +08002011 else
Li Zefan34d52cb2011-03-29 13:46:06 +08002012 __unlink_free_space(ctl, right_info);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002013 info->bytes += right_info->bytes;
Josef Bacikdc89e982011-01-28 17:05:48 -05002014 kmem_cache_free(btrfs_free_space_cachep, right_info);
Li Zefan120d66e2010-11-09 14:56:50 +08002015 merged = true;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002016 }
2017
Josef Bacik96303082009-07-13 21:29:25 -04002018 if (left_info && !left_info->bitmap &&
2019 left_info->offset + left_info->bytes == offset) {
Li Zefanf333adb2010-11-09 14:57:39 +08002020 if (update_stat)
Li Zefan34d52cb2011-03-29 13:46:06 +08002021 unlink_free_space(ctl, left_info);
Li Zefanf333adb2010-11-09 14:57:39 +08002022 else
Li Zefan34d52cb2011-03-29 13:46:06 +08002023 __unlink_free_space(ctl, left_info);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002024 info->offset = left_info->offset;
2025 info->bytes += left_info->bytes;
Josef Bacikdc89e982011-01-28 17:05:48 -05002026 kmem_cache_free(btrfs_free_space_cachep, left_info);
Li Zefan120d66e2010-11-09 14:56:50 +08002027 merged = true;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002028 }
2029
Li Zefan120d66e2010-11-09 14:56:50 +08002030 return merged;
2031}
2032
Filipe Manana20005522014-08-29 13:35:13 +01002033static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
2034 struct btrfs_free_space *info,
2035 bool update_stat)
2036{
2037 struct btrfs_free_space *bitmap;
2038 unsigned long i;
2039 unsigned long j;
2040 const u64 end = info->offset + info->bytes;
2041 const u64 bitmap_offset = offset_to_bitmap(ctl, end);
2042 u64 bytes;
2043
2044 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2045 if (!bitmap)
2046 return false;
2047
2048 i = offset_to_bit(bitmap->offset, ctl->unit, end);
2049 j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
2050 if (j == i)
2051 return false;
2052 bytes = (j - i) * ctl->unit;
2053 info->bytes += bytes;
2054
2055 if (update_stat)
2056 bitmap_clear_bits(ctl, bitmap, end, bytes);
2057 else
2058 __bitmap_clear_bits(ctl, bitmap, end, bytes);
2059
2060 if (!bitmap->bytes)
2061 free_bitmap(ctl, bitmap);
2062
2063 return true;
2064}
2065
2066static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
2067 struct btrfs_free_space *info,
2068 bool update_stat)
2069{
2070 struct btrfs_free_space *bitmap;
2071 u64 bitmap_offset;
2072 unsigned long i;
2073 unsigned long j;
2074 unsigned long prev_j;
2075 u64 bytes;
2076
2077 bitmap_offset = offset_to_bitmap(ctl, info->offset);
2078 /* If we're on a boundary, try the previous logical bitmap. */
2079 if (bitmap_offset == info->offset) {
2080 if (info->offset == 0)
2081 return false;
2082 bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
2083 }
2084
2085 bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
2086 if (!bitmap)
2087 return false;
2088
2089 i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
2090 j = 0;
2091 prev_j = (unsigned long)-1;
2092 for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
2093 if (j > i)
2094 break;
2095 prev_j = j;
2096 }
2097 if (prev_j == i)
2098 return false;
2099
2100 if (prev_j == (unsigned long)-1)
2101 bytes = (i + 1) * ctl->unit;
2102 else
2103 bytes = (i - prev_j) * ctl->unit;
2104
2105 info->offset -= bytes;
2106 info->bytes += bytes;
2107
2108 if (update_stat)
2109 bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
2110 else
2111 __bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
2112
2113 if (!bitmap->bytes)
2114 free_bitmap(ctl, bitmap);
2115
2116 return true;
2117}
2118
2119/*
2120 * We prefer always to allocate from extent entries, both for clustered and
2121 * non-clustered allocation requests. So when attempting to add a new extent
2122 * entry, try to see if there's adjacent free space in bitmap entries, and if
2123 * there is, migrate that space from the bitmaps to the extent.
2124 * Like this we get better chances of satisfying space allocation requests
2125 * because we attempt to satisfy them based on a single cache entry, and never
2126 * on 2 or more entries - even if the entries represent a contiguous free space
2127 * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry
2128 * ends).
2129 */
2130static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
2131 struct btrfs_free_space *info,
2132 bool update_stat)
2133{
2134 /*
2135 * Only work with disconnected entries, as we can change their offset,
2136 * and must be extent entries.
2137 */
2138 ASSERT(!info->bitmap);
2139 ASSERT(RB_EMPTY_NODE(&info->offset_index));
2140
2141 if (ctl->total_bitmaps > 0) {
2142 bool stole_end;
2143 bool stole_front = false;
2144
2145 stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
2146 if (ctl->total_bitmaps > 0)
2147 stole_front = steal_from_bitmap_to_front(ctl, info,
2148 update_stat);
2149
2150 if (stole_end || stole_front)
2151 try_merge_free_space(ctl, info, update_stat);
2152 }
2153}
2154
Li Zefan581bb052011-04-20 10:06:11 +08002155int __btrfs_add_free_space(struct btrfs_free_space_ctl *ctl,
2156 u64 offset, u64 bytes)
Li Zefan120d66e2010-11-09 14:56:50 +08002157{
2158 struct btrfs_free_space *info;
2159 int ret = 0;
2160
Josef Bacikdc89e982011-01-28 17:05:48 -05002161 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
Li Zefan120d66e2010-11-09 14:56:50 +08002162 if (!info)
2163 return -ENOMEM;
2164
2165 info->offset = offset;
2166 info->bytes = bytes;
Filipe Manana20005522014-08-29 13:35:13 +01002167 RB_CLEAR_NODE(&info->offset_index);
Li Zefan120d66e2010-11-09 14:56:50 +08002168
Li Zefan34d52cb2011-03-29 13:46:06 +08002169 spin_lock(&ctl->tree_lock);
Li Zefan120d66e2010-11-09 14:56:50 +08002170
Li Zefan34d52cb2011-03-29 13:46:06 +08002171 if (try_merge_free_space(ctl, info, true))
Li Zefan120d66e2010-11-09 14:56:50 +08002172 goto link;
2173
2174 /*
2175 * There was no extent directly to the left or right of this new
2176 * extent then we know we're going to have to allocate a new extent, so
2177 * before we do that see if we need to drop this into a bitmap
2178 */
Li Zefan34d52cb2011-03-29 13:46:06 +08002179 ret = insert_into_bitmap(ctl, info);
Li Zefan120d66e2010-11-09 14:56:50 +08002180 if (ret < 0) {
2181 goto out;
2182 } else if (ret) {
2183 ret = 0;
2184 goto out;
2185 }
2186link:
Filipe Manana20005522014-08-29 13:35:13 +01002187 /*
2188 * Only steal free space from adjacent bitmaps if we're sure we're not
2189 * going to add the new free space to existing bitmap entries - because
2190 * that would mean unnecessary work that would be reverted. Therefore
2191 * attempt to steal space from bitmaps if we're adding an extent entry.
2192 */
2193 steal_from_bitmap(ctl, info, true);
2194
Li Zefan34d52cb2011-03-29 13:46:06 +08002195 ret = link_free_space(ctl, info);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002196 if (ret)
Josef Bacikdc89e982011-01-28 17:05:48 -05002197 kmem_cache_free(btrfs_free_space_cachep, info);
Josef Bacik96303082009-07-13 21:29:25 -04002198out:
Li Zefan34d52cb2011-03-29 13:46:06 +08002199 spin_unlock(&ctl->tree_lock);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002200
Josef Bacik0f9dd462008-09-23 13:14:11 -04002201 if (ret) {
Frank Holtonefe120a2013-12-20 11:37:06 -05002202 printk(KERN_CRIT "BTRFS: unable to add free space :%d\n", ret);
Josef Bacikb12d6862013-08-26 17:14:08 -04002203 ASSERT(ret != -EEXIST);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002204 }
2205
Josef Bacik0f9dd462008-09-23 13:14:11 -04002206 return ret;
2207}
2208
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002209int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
2210 u64 offset, u64 bytes)
Josef Bacik0f9dd462008-09-23 13:14:11 -04002211{
Li Zefan34d52cb2011-03-29 13:46:06 +08002212 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002213 struct btrfs_free_space *info;
Josef Bacikb0175112012-12-18 11:39:19 -05002214 int ret;
2215 bool re_search = false;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002216
Li Zefan34d52cb2011-03-29 13:46:06 +08002217 spin_lock(&ctl->tree_lock);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002218
Josef Bacik96303082009-07-13 21:29:25 -04002219again:
Josef Bacikb0175112012-12-18 11:39:19 -05002220 ret = 0;
Josef Bacikbdb7d302012-06-27 15:10:56 -04002221 if (!bytes)
2222 goto out_lock;
2223
Li Zefan34d52cb2011-03-29 13:46:06 +08002224 info = tree_search_offset(ctl, offset, 0, 0);
Josef Bacik96303082009-07-13 21:29:25 -04002225 if (!info) {
Josef Bacik6606bb92009-07-31 11:03:58 -04002226 /*
2227 * oops didn't find an extent that matched the space we wanted
2228 * to remove, look for a bitmap instead
2229 */
Li Zefan34d52cb2011-03-29 13:46:06 +08002230 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
Josef Bacik6606bb92009-07-31 11:03:58 -04002231 1, 0);
2232 if (!info) {
Josef Bacikb0175112012-12-18 11:39:19 -05002233 /*
2234 * If we found a partial bit of our free space in a
2235 * bitmap but then couldn't find the other part this may
2236 * be a problem, so WARN about it.
Chris Mason24a70312011-11-21 09:39:11 -05002237 */
Josef Bacikb0175112012-12-18 11:39:19 -05002238 WARN_ON(re_search);
Josef Bacik6606bb92009-07-31 11:03:58 -04002239 goto out_lock;
2240 }
Josef Bacik96303082009-07-13 21:29:25 -04002241 }
2242
Josef Bacikb0175112012-12-18 11:39:19 -05002243 re_search = false;
Josef Bacikbdb7d302012-06-27 15:10:56 -04002244 if (!info->bitmap) {
Li Zefan34d52cb2011-03-29 13:46:06 +08002245 unlink_free_space(ctl, info);
Josef Bacikbdb7d302012-06-27 15:10:56 -04002246 if (offset == info->offset) {
2247 u64 to_free = min(bytes, info->bytes);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002248
Josef Bacikbdb7d302012-06-27 15:10:56 -04002249 info->bytes -= to_free;
2250 info->offset += to_free;
2251 if (info->bytes) {
2252 ret = link_free_space(ctl, info);
2253 WARN_ON(ret);
2254 } else {
2255 kmem_cache_free(btrfs_free_space_cachep, info);
2256 }
Josef Bacik0f9dd462008-09-23 13:14:11 -04002257
Josef Bacikbdb7d302012-06-27 15:10:56 -04002258 offset += to_free;
2259 bytes -= to_free;
2260 goto again;
2261 } else {
2262 u64 old_end = info->bytes + info->offset;
Chris Mason9b49c9b2008-09-24 11:23:25 -04002263
Josef Bacikbdb7d302012-06-27 15:10:56 -04002264 info->bytes = offset - info->offset;
Li Zefan34d52cb2011-03-29 13:46:06 +08002265 ret = link_free_space(ctl, info);
Josef Bacik96303082009-07-13 21:29:25 -04002266 WARN_ON(ret);
2267 if (ret)
2268 goto out_lock;
Josef Bacik96303082009-07-13 21:29:25 -04002269
Josef Bacikbdb7d302012-06-27 15:10:56 -04002270 /* Not enough bytes in this entry to satisfy us */
2271 if (old_end < offset + bytes) {
2272 bytes -= old_end - offset;
2273 offset = old_end;
2274 goto again;
2275 } else if (old_end == offset + bytes) {
2276 /* all done */
2277 goto out_lock;
2278 }
2279 spin_unlock(&ctl->tree_lock);
2280
2281 ret = btrfs_add_free_space(block_group, offset + bytes,
2282 old_end - (offset + bytes));
2283 WARN_ON(ret);
2284 goto out;
2285 }
Josef Bacik0f9dd462008-09-23 13:14:11 -04002286 }
Josef Bacik96303082009-07-13 21:29:25 -04002287
Li Zefan34d52cb2011-03-29 13:46:06 +08002288 ret = remove_from_bitmap(ctl, info, &offset, &bytes);
Josef Bacikb0175112012-12-18 11:39:19 -05002289 if (ret == -EAGAIN) {
2290 re_search = true;
Josef Bacik96303082009-07-13 21:29:25 -04002291 goto again;
Josef Bacikb0175112012-12-18 11:39:19 -05002292 }
Josef Bacik96303082009-07-13 21:29:25 -04002293out_lock:
Li Zefan34d52cb2011-03-29 13:46:06 +08002294 spin_unlock(&ctl->tree_lock);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002295out:
Josef Bacik25179202008-10-29 14:49:05 -04002296 return ret;
2297}
2298
Josef Bacik0f9dd462008-09-23 13:14:11 -04002299void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
2300 u64 bytes)
2301{
Li Zefan34d52cb2011-03-29 13:46:06 +08002302 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002303 struct btrfs_free_space *info;
2304 struct rb_node *n;
2305 int count = 0;
2306
Li Zefan34d52cb2011-03-29 13:46:06 +08002307 for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
Josef Bacik0f9dd462008-09-23 13:14:11 -04002308 info = rb_entry(n, struct btrfs_free_space, offset_index);
Liu Bof6175ef2012-07-06 03:31:36 -06002309 if (info->bytes >= bytes && !block_group->ro)
Josef Bacik0f9dd462008-09-23 13:14:11 -04002310 count++;
Frank Holtonefe120a2013-12-20 11:37:06 -05002311 btrfs_crit(block_group->fs_info,
2312 "entry offset %llu, bytes %llu, bitmap %s",
2313 info->offset, info->bytes,
Josef Bacik96303082009-07-13 21:29:25 -04002314 (info->bitmap) ? "yes" : "no");
Josef Bacik0f9dd462008-09-23 13:14:11 -04002315 }
Frank Holtonefe120a2013-12-20 11:37:06 -05002316 btrfs_info(block_group->fs_info, "block group has cluster?: %s",
Josef Bacik96303082009-07-13 21:29:25 -04002317 list_empty(&block_group->cluster_list) ? "no" : "yes");
Frank Holtonefe120a2013-12-20 11:37:06 -05002318 btrfs_info(block_group->fs_info,
2319 "%d blocks of free space at or bigger than bytes is", count);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002320}
2321
Li Zefan34d52cb2011-03-29 13:46:06 +08002322void btrfs_init_free_space_ctl(struct btrfs_block_group_cache *block_group)
Josef Bacik0f9dd462008-09-23 13:14:11 -04002323{
Li Zefan34d52cb2011-03-29 13:46:06 +08002324 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002325
Li Zefan34d52cb2011-03-29 13:46:06 +08002326 spin_lock_init(&ctl->tree_lock);
2327 ctl->unit = block_group->sectorsize;
2328 ctl->start = block_group->key.objectid;
2329 ctl->private = block_group;
2330 ctl->op = &free_space_op;
Filipe Manana55507ce2014-12-01 17:04:09 +00002331 INIT_LIST_HEAD(&ctl->trimming_ranges);
2332 mutex_init(&ctl->cache_writeout_mutex);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002333
Li Zefan34d52cb2011-03-29 13:46:06 +08002334 /*
2335 * we only want to have 32k of ram per block group for keeping
2336 * track of free space, and if we pass 1/2 of that we want to
2337 * start converting things over to using bitmaps
2338 */
2339 ctl->extents_thresh = ((1024 * 32) / 2) /
2340 sizeof(struct btrfs_free_space);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002341}
2342
Chris Masonfa9c0d792009-04-03 09:47:43 -04002343/*
2344 * for a given cluster, put all of its extents back into the free
2345 * space cache. If the block group passed doesn't match the block group
2346 * pointed to by the cluster, someone else raced in and freed the
2347 * cluster already. In that case, we just return without changing anything
2348 */
2349static int
2350__btrfs_return_cluster_to_free_space(
2351 struct btrfs_block_group_cache *block_group,
2352 struct btrfs_free_cluster *cluster)
2353{
Li Zefan34d52cb2011-03-29 13:46:06 +08002354 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002355 struct btrfs_free_space *entry;
2356 struct rb_node *node;
2357
2358 spin_lock(&cluster->lock);
2359 if (cluster->block_group != block_group)
2360 goto out;
2361
Josef Bacik96303082009-07-13 21:29:25 -04002362 cluster->block_group = NULL;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002363 cluster->window_start = 0;
Josef Bacik96303082009-07-13 21:29:25 -04002364 list_del_init(&cluster->block_group_list);
Josef Bacik96303082009-07-13 21:29:25 -04002365
Chris Masonfa9c0d792009-04-03 09:47:43 -04002366 node = rb_first(&cluster->root);
Josef Bacik96303082009-07-13 21:29:25 -04002367 while (node) {
Josef Bacik4e69b592011-03-21 10:11:24 -04002368 bool bitmap;
2369
Chris Masonfa9c0d792009-04-03 09:47:43 -04002370 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2371 node = rb_next(&entry->offset_index);
2372 rb_erase(&entry->offset_index, &cluster->root);
Filipe Manana20005522014-08-29 13:35:13 +01002373 RB_CLEAR_NODE(&entry->offset_index);
Josef Bacik4e69b592011-03-21 10:11:24 -04002374
2375 bitmap = (entry->bitmap != NULL);
Filipe Manana20005522014-08-29 13:35:13 +01002376 if (!bitmap) {
Li Zefan34d52cb2011-03-29 13:46:06 +08002377 try_merge_free_space(ctl, entry, false);
Filipe Manana20005522014-08-29 13:35:13 +01002378 steal_from_bitmap(ctl, entry, false);
2379 }
Li Zefan34d52cb2011-03-29 13:46:06 +08002380 tree_insert_offset(&ctl->free_space_offset,
Josef Bacik4e69b592011-03-21 10:11:24 -04002381 entry->offset, &entry->offset_index, bitmap);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002382 }
Eric Paris6bef4d32010-02-23 19:43:04 +00002383 cluster->root = RB_ROOT;
Josef Bacik96303082009-07-13 21:29:25 -04002384
Chris Masonfa9c0d792009-04-03 09:47:43 -04002385out:
2386 spin_unlock(&cluster->lock);
Josef Bacik96303082009-07-13 21:29:25 -04002387 btrfs_put_block_group(block_group);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002388 return 0;
2389}
2390
Eric Sandeen48a3b632013-04-25 20:41:01 +00002391static void __btrfs_remove_free_space_cache_locked(
2392 struct btrfs_free_space_ctl *ctl)
Josef Bacik0f9dd462008-09-23 13:14:11 -04002393{
2394 struct btrfs_free_space *info;
2395 struct rb_node *node;
Li Zefan581bb052011-04-20 10:06:11 +08002396
Li Zefan581bb052011-04-20 10:06:11 +08002397 while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
2398 info = rb_entry(node, struct btrfs_free_space, offset_index);
Josef Bacik9b90f512011-06-24 16:02:51 +00002399 if (!info->bitmap) {
2400 unlink_free_space(ctl, info);
2401 kmem_cache_free(btrfs_free_space_cachep, info);
2402 } else {
2403 free_bitmap(ctl, info);
2404 }
Li Zefan581bb052011-04-20 10:06:11 +08002405 if (need_resched()) {
2406 spin_unlock(&ctl->tree_lock);
2407 cond_resched();
2408 spin_lock(&ctl->tree_lock);
2409 }
2410 }
Chris Mason09655372011-05-21 09:27:38 -04002411}
2412
2413void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
2414{
2415 spin_lock(&ctl->tree_lock);
2416 __btrfs_remove_free_space_cache_locked(ctl);
Li Zefan581bb052011-04-20 10:06:11 +08002417 spin_unlock(&ctl->tree_lock);
2418}
2419
Josef Bacik0f9dd462008-09-23 13:14:11 -04002420void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
2421{
Li Zefan34d52cb2011-03-29 13:46:06 +08002422 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002423 struct btrfs_free_cluster *cluster;
Josef Bacik96303082009-07-13 21:29:25 -04002424 struct list_head *head;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002425
Li Zefan34d52cb2011-03-29 13:46:06 +08002426 spin_lock(&ctl->tree_lock);
Josef Bacik96303082009-07-13 21:29:25 -04002427 while ((head = block_group->cluster_list.next) !=
2428 &block_group->cluster_list) {
2429 cluster = list_entry(head, struct btrfs_free_cluster,
2430 block_group_list);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002431
2432 WARN_ON(cluster->block_group != block_group);
2433 __btrfs_return_cluster_to_free_space(block_group, cluster);
Josef Bacik96303082009-07-13 21:29:25 -04002434 if (need_resched()) {
Li Zefan34d52cb2011-03-29 13:46:06 +08002435 spin_unlock(&ctl->tree_lock);
Josef Bacik96303082009-07-13 21:29:25 -04002436 cond_resched();
Li Zefan34d52cb2011-03-29 13:46:06 +08002437 spin_lock(&ctl->tree_lock);
Josef Bacik96303082009-07-13 21:29:25 -04002438 }
Chris Masonfa9c0d792009-04-03 09:47:43 -04002439 }
Chris Mason09655372011-05-21 09:27:38 -04002440 __btrfs_remove_free_space_cache_locked(ctl);
Li Zefan34d52cb2011-03-29 13:46:06 +08002441 spin_unlock(&ctl->tree_lock);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002442
Josef Bacik0f9dd462008-09-23 13:14:11 -04002443}
2444
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002445u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
Miao Xiea4820392013-09-09 13:19:42 +08002446 u64 offset, u64 bytes, u64 empty_size,
2447 u64 *max_extent_size)
Josef Bacik0f9dd462008-09-23 13:14:11 -04002448{
Li Zefan34d52cb2011-03-29 13:46:06 +08002449 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002450 struct btrfs_free_space *entry = NULL;
Josef Bacik96303082009-07-13 21:29:25 -04002451 u64 bytes_search = bytes + empty_size;
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002452 u64 ret = 0;
David Woodhouse53b381b2013-01-29 18:40:14 -05002453 u64 align_gap = 0;
2454 u64 align_gap_len = 0;
Josef Bacik0f9dd462008-09-23 13:14:11 -04002455
Li Zefan34d52cb2011-03-29 13:46:06 +08002456 spin_lock(&ctl->tree_lock);
David Woodhouse53b381b2013-01-29 18:40:14 -05002457 entry = find_free_space(ctl, &offset, &bytes_search,
Miao Xiea4820392013-09-09 13:19:42 +08002458 block_group->full_stripe_len, max_extent_size);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002459 if (!entry)
Josef Bacik96303082009-07-13 21:29:25 -04002460 goto out;
2461
2462 ret = offset;
2463 if (entry->bitmap) {
Li Zefan34d52cb2011-03-29 13:46:06 +08002464 bitmap_clear_bits(ctl, entry, offset, bytes);
Li Zefanedf6e2d2010-11-09 14:50:07 +08002465 if (!entry->bytes)
Li Zefan34d52cb2011-03-29 13:46:06 +08002466 free_bitmap(ctl, entry);
Josef Bacik96303082009-07-13 21:29:25 -04002467 } else {
Li Zefan34d52cb2011-03-29 13:46:06 +08002468 unlink_free_space(ctl, entry);
David Woodhouse53b381b2013-01-29 18:40:14 -05002469 align_gap_len = offset - entry->offset;
2470 align_gap = entry->offset;
2471
2472 entry->offset = offset + bytes;
2473 WARN_ON(entry->bytes < bytes + align_gap_len);
2474
2475 entry->bytes -= bytes + align_gap_len;
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002476 if (!entry->bytes)
Josef Bacikdc89e982011-01-28 17:05:48 -05002477 kmem_cache_free(btrfs_free_space_cachep, entry);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002478 else
Li Zefan34d52cb2011-03-29 13:46:06 +08002479 link_free_space(ctl, entry);
Josef Bacik6226cb0a2009-04-03 10:14:18 -04002480 }
Josef Bacik96303082009-07-13 21:29:25 -04002481out:
Li Zefan34d52cb2011-03-29 13:46:06 +08002482 spin_unlock(&ctl->tree_lock);
Josef Bacik817d52f2009-07-13 21:29:25 -04002483
David Woodhouse53b381b2013-01-29 18:40:14 -05002484 if (align_gap_len)
2485 __btrfs_add_free_space(ctl, align_gap, align_gap_len);
Josef Bacik0f9dd462008-09-23 13:14:11 -04002486 return ret;
2487}
Chris Masonfa9c0d792009-04-03 09:47:43 -04002488
2489/*
2490 * given a cluster, put all of its extents back into the free space
2491 * cache. If a block group is passed, this function will only free
2492 * a cluster that belongs to the passed block group.
2493 *
2494 * Otherwise, it'll get a reference on the block group pointed to by the
2495 * cluster and remove the cluster from it.
2496 */
2497int btrfs_return_cluster_to_free_space(
2498 struct btrfs_block_group_cache *block_group,
2499 struct btrfs_free_cluster *cluster)
2500{
Li Zefan34d52cb2011-03-29 13:46:06 +08002501 struct btrfs_free_space_ctl *ctl;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002502 int ret;
2503
2504 /* first, get a safe pointer to the block group */
2505 spin_lock(&cluster->lock);
2506 if (!block_group) {
2507 block_group = cluster->block_group;
2508 if (!block_group) {
2509 spin_unlock(&cluster->lock);
2510 return 0;
2511 }
2512 } else if (cluster->block_group != block_group) {
2513 /* someone else has already freed it don't redo their work */
2514 spin_unlock(&cluster->lock);
2515 return 0;
2516 }
2517 atomic_inc(&block_group->count);
2518 spin_unlock(&cluster->lock);
2519
Li Zefan34d52cb2011-03-29 13:46:06 +08002520 ctl = block_group->free_space_ctl;
2521
Chris Masonfa9c0d792009-04-03 09:47:43 -04002522 /* now return any extents the cluster had on it */
Li Zefan34d52cb2011-03-29 13:46:06 +08002523 spin_lock(&ctl->tree_lock);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002524 ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
Li Zefan34d52cb2011-03-29 13:46:06 +08002525 spin_unlock(&ctl->tree_lock);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002526
2527 /* finally drop our ref */
2528 btrfs_put_block_group(block_group);
2529 return ret;
2530}
2531
Josef Bacik96303082009-07-13 21:29:25 -04002532static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group_cache *block_group,
2533 struct btrfs_free_cluster *cluster,
Josef Bacik4e69b592011-03-21 10:11:24 -04002534 struct btrfs_free_space *entry,
Miao Xiea4820392013-09-09 13:19:42 +08002535 u64 bytes, u64 min_start,
2536 u64 *max_extent_size)
Josef Bacik96303082009-07-13 21:29:25 -04002537{
Li Zefan34d52cb2011-03-29 13:46:06 +08002538 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik96303082009-07-13 21:29:25 -04002539 int err;
2540 u64 search_start = cluster->window_start;
2541 u64 search_bytes = bytes;
2542 u64 ret = 0;
2543
Josef Bacik96303082009-07-13 21:29:25 -04002544 search_start = min_start;
2545 search_bytes = bytes;
2546
Li Zefan34d52cb2011-03-29 13:46:06 +08002547 err = search_bitmap(ctl, entry, &search_start, &search_bytes);
Miao Xiea4820392013-09-09 13:19:42 +08002548 if (err) {
2549 if (search_bytes > *max_extent_size)
2550 *max_extent_size = search_bytes;
Josef Bacik4e69b592011-03-21 10:11:24 -04002551 return 0;
Miao Xiea4820392013-09-09 13:19:42 +08002552 }
Josef Bacik96303082009-07-13 21:29:25 -04002553
2554 ret = search_start;
Miao Xiebb3ac5a2011-08-05 09:32:35 +00002555 __bitmap_clear_bits(ctl, entry, ret, bytes);
Josef Bacik96303082009-07-13 21:29:25 -04002556
2557 return ret;
2558}
2559
Chris Masonfa9c0d792009-04-03 09:47:43 -04002560/*
2561 * given a cluster, try to allocate 'bytes' from it, returns 0
2562 * if it couldn't find anything suitably large, or a logical disk offset
2563 * if things worked out
2564 */
2565u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
2566 struct btrfs_free_cluster *cluster, u64 bytes,
Miao Xiea4820392013-09-09 13:19:42 +08002567 u64 min_start, u64 *max_extent_size)
Chris Masonfa9c0d792009-04-03 09:47:43 -04002568{
Li Zefan34d52cb2011-03-29 13:46:06 +08002569 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002570 struct btrfs_free_space *entry = NULL;
2571 struct rb_node *node;
2572 u64 ret = 0;
2573
2574 spin_lock(&cluster->lock);
2575 if (bytes > cluster->max_size)
2576 goto out;
2577
2578 if (cluster->block_group != block_group)
2579 goto out;
2580
2581 node = rb_first(&cluster->root);
2582 if (!node)
2583 goto out;
2584
2585 entry = rb_entry(node, struct btrfs_free_space, offset_index);
Dulshani Gunawardhana67871252013-10-31 10:33:04 +05302586 while (1) {
Miao Xiea4820392013-09-09 13:19:42 +08002587 if (entry->bytes < bytes && entry->bytes > *max_extent_size)
2588 *max_extent_size = entry->bytes;
2589
Josef Bacik4e69b592011-03-21 10:11:24 -04002590 if (entry->bytes < bytes ||
2591 (!entry->bitmap && entry->offset < min_start)) {
Chris Masonfa9c0d792009-04-03 09:47:43 -04002592 node = rb_next(&entry->offset_index);
2593 if (!node)
2594 break;
2595 entry = rb_entry(node, struct btrfs_free_space,
2596 offset_index);
2597 continue;
2598 }
Chris Masonfa9c0d792009-04-03 09:47:43 -04002599
Josef Bacik4e69b592011-03-21 10:11:24 -04002600 if (entry->bitmap) {
2601 ret = btrfs_alloc_from_bitmap(block_group,
2602 cluster, entry, bytes,
Miao Xiea4820392013-09-09 13:19:42 +08002603 cluster->window_start,
2604 max_extent_size);
Josef Bacik4e69b592011-03-21 10:11:24 -04002605 if (ret == 0) {
Josef Bacik4e69b592011-03-21 10:11:24 -04002606 node = rb_next(&entry->offset_index);
2607 if (!node)
2608 break;
2609 entry = rb_entry(node, struct btrfs_free_space,
2610 offset_index);
2611 continue;
2612 }
Josef Bacik9b230622012-01-26 15:01:12 -05002613 cluster->window_start += bytes;
Josef Bacik4e69b592011-03-21 10:11:24 -04002614 } else {
Josef Bacik4e69b592011-03-21 10:11:24 -04002615 ret = entry->offset;
2616
2617 entry->offset += bytes;
2618 entry->bytes -= bytes;
2619 }
Chris Masonfa9c0d792009-04-03 09:47:43 -04002620
Li Zefan5e71b5d2010-11-09 14:55:34 +08002621 if (entry->bytes == 0)
Chris Masonfa9c0d792009-04-03 09:47:43 -04002622 rb_erase(&entry->offset_index, &cluster->root);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002623 break;
2624 }
2625out:
2626 spin_unlock(&cluster->lock);
Josef Bacik96303082009-07-13 21:29:25 -04002627
Li Zefan5e71b5d2010-11-09 14:55:34 +08002628 if (!ret)
2629 return 0;
2630
Li Zefan34d52cb2011-03-29 13:46:06 +08002631 spin_lock(&ctl->tree_lock);
Li Zefan5e71b5d2010-11-09 14:55:34 +08002632
Li Zefan34d52cb2011-03-29 13:46:06 +08002633 ctl->free_space -= bytes;
Li Zefan5e71b5d2010-11-09 14:55:34 +08002634 if (entry->bytes == 0) {
Li Zefan34d52cb2011-03-29 13:46:06 +08002635 ctl->free_extents--;
Josef Bacik4e69b592011-03-21 10:11:24 -04002636 if (entry->bitmap) {
2637 kfree(entry->bitmap);
Li Zefan34d52cb2011-03-29 13:46:06 +08002638 ctl->total_bitmaps--;
2639 ctl->op->recalc_thresholds(ctl);
Josef Bacik4e69b592011-03-21 10:11:24 -04002640 }
Josef Bacikdc89e982011-01-28 17:05:48 -05002641 kmem_cache_free(btrfs_free_space_cachep, entry);
Li Zefan5e71b5d2010-11-09 14:55:34 +08002642 }
2643
Li Zefan34d52cb2011-03-29 13:46:06 +08002644 spin_unlock(&ctl->tree_lock);
Li Zefan5e71b5d2010-11-09 14:55:34 +08002645
Chris Masonfa9c0d792009-04-03 09:47:43 -04002646 return ret;
2647}
2648
Josef Bacik96303082009-07-13 21:29:25 -04002649static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group,
2650 struct btrfs_free_space *entry,
2651 struct btrfs_free_cluster *cluster,
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002652 u64 offset, u64 bytes,
2653 u64 cont1_bytes, u64 min_bytes)
Josef Bacik96303082009-07-13 21:29:25 -04002654{
Li Zefan34d52cb2011-03-29 13:46:06 +08002655 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik96303082009-07-13 21:29:25 -04002656 unsigned long next_zero;
2657 unsigned long i;
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002658 unsigned long want_bits;
2659 unsigned long min_bits;
Josef Bacik96303082009-07-13 21:29:25 -04002660 unsigned long found_bits;
2661 unsigned long start = 0;
2662 unsigned long total_found = 0;
Josef Bacik4e69b592011-03-21 10:11:24 -04002663 int ret;
Josef Bacik96303082009-07-13 21:29:25 -04002664
Wang Sheng-Hui96009762012-11-30 06:30:14 +00002665 i = offset_to_bit(entry->offset, ctl->unit,
Josef Bacik96303082009-07-13 21:29:25 -04002666 max_t(u64, offset, entry->offset));
Wang Sheng-Hui96009762012-11-30 06:30:14 +00002667 want_bits = bytes_to_bits(bytes, ctl->unit);
2668 min_bits = bytes_to_bits(min_bytes, ctl->unit);
Josef Bacik96303082009-07-13 21:29:25 -04002669
2670again:
2671 found_bits = 0;
Wei Yongjunebb3dad2012-09-13 20:29:02 -06002672 for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
Josef Bacik96303082009-07-13 21:29:25 -04002673 next_zero = find_next_zero_bit(entry->bitmap,
2674 BITS_PER_BITMAP, i);
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002675 if (next_zero - i >= min_bits) {
Josef Bacik96303082009-07-13 21:29:25 -04002676 found_bits = next_zero - i;
2677 break;
2678 }
2679 i = next_zero;
2680 }
2681
2682 if (!found_bits)
Josef Bacik4e69b592011-03-21 10:11:24 -04002683 return -ENOSPC;
Josef Bacik96303082009-07-13 21:29:25 -04002684
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002685 if (!total_found) {
Josef Bacik96303082009-07-13 21:29:25 -04002686 start = i;
Alexandre Olivab78d09b2011-11-30 13:43:00 -05002687 cluster->max_size = 0;
Josef Bacik96303082009-07-13 21:29:25 -04002688 }
2689
2690 total_found += found_bits;
2691
Wang Sheng-Hui96009762012-11-30 06:30:14 +00002692 if (cluster->max_size < found_bits * ctl->unit)
2693 cluster->max_size = found_bits * ctl->unit;
Josef Bacik96303082009-07-13 21:29:25 -04002694
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002695 if (total_found < want_bits || cluster->max_size < cont1_bytes) {
2696 i = next_zero + 1;
Josef Bacik96303082009-07-13 21:29:25 -04002697 goto again;
2698 }
2699
Wang Sheng-Hui96009762012-11-30 06:30:14 +00002700 cluster->window_start = start * ctl->unit + entry->offset;
Li Zefan34d52cb2011-03-29 13:46:06 +08002701 rb_erase(&entry->offset_index, &ctl->free_space_offset);
Josef Bacik4e69b592011-03-21 10:11:24 -04002702 ret = tree_insert_offset(&cluster->root, entry->offset,
2703 &entry->offset_index, 1);
Josef Bacikb12d6862013-08-26 17:14:08 -04002704 ASSERT(!ret); /* -EEXIST; Logic error */
Josef Bacik96303082009-07-13 21:29:25 -04002705
Josef Bacik3f7de032011-11-10 08:29:20 -05002706 trace_btrfs_setup_cluster(block_group, cluster,
Wang Sheng-Hui96009762012-11-30 06:30:14 +00002707 total_found * ctl->unit, 1);
Josef Bacik96303082009-07-13 21:29:25 -04002708 return 0;
2709}
2710
Chris Masonfa9c0d792009-04-03 09:47:43 -04002711/*
Josef Bacik4e69b592011-03-21 10:11:24 -04002712 * This searches the block group for just extents to fill the cluster with.
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002713 * Try to find a cluster with at least bytes total bytes, at least one
2714 * extent of cont1_bytes, and other clusters of at least min_bytes.
Josef Bacik4e69b592011-03-21 10:11:24 -04002715 */
Josef Bacik3de85bb2011-05-25 13:07:37 -04002716static noinline int
2717setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group,
2718 struct btrfs_free_cluster *cluster,
2719 struct list_head *bitmaps, u64 offset, u64 bytes,
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002720 u64 cont1_bytes, u64 min_bytes)
Josef Bacik4e69b592011-03-21 10:11:24 -04002721{
Li Zefan34d52cb2011-03-29 13:46:06 +08002722 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik4e69b592011-03-21 10:11:24 -04002723 struct btrfs_free_space *first = NULL;
2724 struct btrfs_free_space *entry = NULL;
Josef Bacik4e69b592011-03-21 10:11:24 -04002725 struct btrfs_free_space *last;
2726 struct rb_node *node;
Josef Bacik4e69b592011-03-21 10:11:24 -04002727 u64 window_free;
2728 u64 max_extent;
Josef Bacik3f7de032011-11-10 08:29:20 -05002729 u64 total_size = 0;
Josef Bacik4e69b592011-03-21 10:11:24 -04002730
Li Zefan34d52cb2011-03-29 13:46:06 +08002731 entry = tree_search_offset(ctl, offset, 0, 1);
Josef Bacik4e69b592011-03-21 10:11:24 -04002732 if (!entry)
2733 return -ENOSPC;
2734
2735 /*
2736 * We don't want bitmaps, so just move along until we find a normal
2737 * extent entry.
2738 */
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002739 while (entry->bitmap || entry->bytes < min_bytes) {
2740 if (entry->bitmap && list_empty(&entry->list))
Josef Bacik86d4a772011-05-25 13:03:16 -04002741 list_add_tail(&entry->list, bitmaps);
Josef Bacik4e69b592011-03-21 10:11:24 -04002742 node = rb_next(&entry->offset_index);
2743 if (!node)
2744 return -ENOSPC;
2745 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2746 }
2747
Josef Bacik4e69b592011-03-21 10:11:24 -04002748 window_free = entry->bytes;
2749 max_extent = entry->bytes;
2750 first = entry;
2751 last = entry;
Josef Bacik4e69b592011-03-21 10:11:24 -04002752
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002753 for (node = rb_next(&entry->offset_index); node;
2754 node = rb_next(&entry->offset_index)) {
Josef Bacik4e69b592011-03-21 10:11:24 -04002755 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2756
Josef Bacik86d4a772011-05-25 13:03:16 -04002757 if (entry->bitmap) {
2758 if (list_empty(&entry->list))
2759 list_add_tail(&entry->list, bitmaps);
Josef Bacik4e69b592011-03-21 10:11:24 -04002760 continue;
Josef Bacik86d4a772011-05-25 13:03:16 -04002761 }
2762
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002763 if (entry->bytes < min_bytes)
2764 continue;
2765
2766 last = entry;
2767 window_free += entry->bytes;
2768 if (entry->bytes > max_extent)
Josef Bacik4e69b592011-03-21 10:11:24 -04002769 max_extent = entry->bytes;
Josef Bacik4e69b592011-03-21 10:11:24 -04002770 }
2771
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002772 if (window_free < bytes || max_extent < cont1_bytes)
2773 return -ENOSPC;
2774
Josef Bacik4e69b592011-03-21 10:11:24 -04002775 cluster->window_start = first->offset;
2776
2777 node = &first->offset_index;
2778
2779 /*
2780 * now we've found our entries, pull them out of the free space
2781 * cache and put them into the cluster rbtree
2782 */
2783 do {
2784 int ret;
2785
2786 entry = rb_entry(node, struct btrfs_free_space, offset_index);
2787 node = rb_next(&entry->offset_index);
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002788 if (entry->bitmap || entry->bytes < min_bytes)
Josef Bacik4e69b592011-03-21 10:11:24 -04002789 continue;
2790
Li Zefan34d52cb2011-03-29 13:46:06 +08002791 rb_erase(&entry->offset_index, &ctl->free_space_offset);
Josef Bacik4e69b592011-03-21 10:11:24 -04002792 ret = tree_insert_offset(&cluster->root, entry->offset,
2793 &entry->offset_index, 0);
Josef Bacik3f7de032011-11-10 08:29:20 -05002794 total_size += entry->bytes;
Josef Bacikb12d6862013-08-26 17:14:08 -04002795 ASSERT(!ret); /* -EEXIST; Logic error */
Josef Bacik4e69b592011-03-21 10:11:24 -04002796 } while (node && entry != last);
2797
2798 cluster->max_size = max_extent;
Josef Bacik3f7de032011-11-10 08:29:20 -05002799 trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
Josef Bacik4e69b592011-03-21 10:11:24 -04002800 return 0;
2801}
2802
2803/*
2804 * This specifically looks for bitmaps that may work in the cluster, we assume
2805 * that we have already failed to find extents that will work.
2806 */
Josef Bacik3de85bb2011-05-25 13:07:37 -04002807static noinline int
2808setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,
2809 struct btrfs_free_cluster *cluster,
2810 struct list_head *bitmaps, u64 offset, u64 bytes,
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002811 u64 cont1_bytes, u64 min_bytes)
Josef Bacik4e69b592011-03-21 10:11:24 -04002812{
Li Zefan34d52cb2011-03-29 13:46:06 +08002813 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik4e69b592011-03-21 10:11:24 -04002814 struct btrfs_free_space *entry;
Josef Bacik4e69b592011-03-21 10:11:24 -04002815 int ret = -ENOSPC;
Li Zefan0f0fbf12011-11-20 07:33:38 -05002816 u64 bitmap_offset = offset_to_bitmap(ctl, offset);
Josef Bacik4e69b592011-03-21 10:11:24 -04002817
Li Zefan34d52cb2011-03-29 13:46:06 +08002818 if (ctl->total_bitmaps == 0)
Josef Bacik4e69b592011-03-21 10:11:24 -04002819 return -ENOSPC;
2820
Josef Bacik86d4a772011-05-25 13:03:16 -04002821 /*
Li Zefan0f0fbf12011-11-20 07:33:38 -05002822 * The bitmap that covers offset won't be in the list unless offset
2823 * is just its start offset.
2824 */
2825 entry = list_first_entry(bitmaps, struct btrfs_free_space, list);
2826 if (entry->offset != bitmap_offset) {
2827 entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
2828 if (entry && list_empty(&entry->list))
2829 list_add(&entry->list, bitmaps);
2830 }
2831
Josef Bacik86d4a772011-05-25 13:03:16 -04002832 list_for_each_entry(entry, bitmaps, list) {
Josef Bacik357b9782012-01-26 15:01:11 -05002833 if (entry->bytes < bytes)
Josef Bacik86d4a772011-05-25 13:03:16 -04002834 continue;
2835 ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002836 bytes, cont1_bytes, min_bytes);
Josef Bacik86d4a772011-05-25 13:03:16 -04002837 if (!ret)
2838 return 0;
2839 }
2840
2841 /*
Li Zefan52621cb2011-11-20 07:33:38 -05002842 * The bitmaps list has all the bitmaps that record free space
2843 * starting after offset, so no more search is required.
Josef Bacik86d4a772011-05-25 13:03:16 -04002844 */
Li Zefan52621cb2011-11-20 07:33:38 -05002845 return -ENOSPC;
Josef Bacik4e69b592011-03-21 10:11:24 -04002846}
2847
2848/*
Chris Masonfa9c0d792009-04-03 09:47:43 -04002849 * here we try to find a cluster of blocks in a block group. The goal
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002850 * is to find at least bytes+empty_size.
Chris Masonfa9c0d792009-04-03 09:47:43 -04002851 * We might not find them all in one contiguous area.
2852 *
2853 * returns zero and sets up cluster if things worked out, otherwise
2854 * it returns -enospc
2855 */
Josef Bacik00361582013-08-14 14:02:47 -04002856int btrfs_find_space_cluster(struct btrfs_root *root,
Chris Masonfa9c0d792009-04-03 09:47:43 -04002857 struct btrfs_block_group_cache *block_group,
2858 struct btrfs_free_cluster *cluster,
2859 u64 offset, u64 bytes, u64 empty_size)
2860{
Li Zefan34d52cb2011-03-29 13:46:06 +08002861 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Josef Bacik86d4a772011-05-25 13:03:16 -04002862 struct btrfs_free_space *entry, *tmp;
Li Zefan52621cb2011-11-20 07:33:38 -05002863 LIST_HEAD(bitmaps);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002864 u64 min_bytes;
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002865 u64 cont1_bytes;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002866 int ret;
2867
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002868 /*
2869 * Choose the minimum extent size we'll require for this
2870 * cluster. For SSD_SPREAD, don't allow any fragmentation.
2871 * For metadata, allow allocates with smaller extents. For
2872 * data, keep it dense.
2873 */
Chris Mason451d7582009-06-09 20:28:34 -04002874 if (btrfs_test_opt(root, SSD_SPREAD)) {
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002875 cont1_bytes = min_bytes = bytes + empty_size;
Chris Mason451d7582009-06-09 20:28:34 -04002876 } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002877 cont1_bytes = bytes;
2878 min_bytes = block_group->sectorsize;
2879 } else {
2880 cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
2881 min_bytes = block_group->sectorsize;
2882 }
Chris Masonfa9c0d792009-04-03 09:47:43 -04002883
Li Zefan34d52cb2011-03-29 13:46:06 +08002884 spin_lock(&ctl->tree_lock);
Josef Bacik7d0d2e82011-03-18 15:13:42 -04002885
2886 /*
2887 * If we know we don't have enough space to make a cluster don't even
2888 * bother doing all the work to try and find one.
2889 */
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002890 if (ctl->free_space < bytes) {
Li Zefan34d52cb2011-03-29 13:46:06 +08002891 spin_unlock(&ctl->tree_lock);
Josef Bacik7d0d2e82011-03-18 15:13:42 -04002892 return -ENOSPC;
2893 }
2894
Chris Masonfa9c0d792009-04-03 09:47:43 -04002895 spin_lock(&cluster->lock);
2896
2897 /* someone already found a cluster, hooray */
2898 if (cluster->block_group) {
2899 ret = 0;
2900 goto out;
2901 }
Josef Bacik4e69b592011-03-21 10:11:24 -04002902
Josef Bacik3f7de032011-11-10 08:29:20 -05002903 trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
2904 min_bytes);
2905
2906 INIT_LIST_HEAD(&bitmaps);
Josef Bacik86d4a772011-05-25 13:03:16 -04002907 ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002908 bytes + empty_size,
2909 cont1_bytes, min_bytes);
Josef Bacik4e69b592011-03-21 10:11:24 -04002910 if (ret)
Josef Bacik86d4a772011-05-25 13:03:16 -04002911 ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
Alexandre Oliva1bb91902011-10-14 12:10:36 -03002912 offset, bytes + empty_size,
2913 cont1_bytes, min_bytes);
Josef Bacik86d4a772011-05-25 13:03:16 -04002914
2915 /* Clear our temporary list */
2916 list_for_each_entry_safe(entry, tmp, &bitmaps, list)
2917 list_del_init(&entry->list);
Josef Bacik4e69b592011-03-21 10:11:24 -04002918
2919 if (!ret) {
2920 atomic_inc(&block_group->count);
2921 list_add_tail(&cluster->block_group_list,
2922 &block_group->cluster_list);
2923 cluster->block_group = block_group;
Josef Bacik3f7de032011-11-10 08:29:20 -05002924 } else {
2925 trace_btrfs_failed_cluster_setup(block_group);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002926 }
Chris Masonfa9c0d792009-04-03 09:47:43 -04002927out:
2928 spin_unlock(&cluster->lock);
Li Zefan34d52cb2011-03-29 13:46:06 +08002929 spin_unlock(&ctl->tree_lock);
Chris Masonfa9c0d792009-04-03 09:47:43 -04002930
2931 return ret;
2932}
2933
2934/*
2935 * simple code to zero out a cluster
2936 */
2937void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
2938{
2939 spin_lock_init(&cluster->lock);
2940 spin_lock_init(&cluster->refill_lock);
Eric Paris6bef4d32010-02-23 19:43:04 +00002941 cluster->root = RB_ROOT;
Chris Masonfa9c0d792009-04-03 09:47:43 -04002942 cluster->max_size = 0;
2943 INIT_LIST_HEAD(&cluster->block_group_list);
2944 cluster->block_group = NULL;
2945}
2946
Li Zefan7fe1e642011-12-29 14:47:27 +08002947static int do_trimming(struct btrfs_block_group_cache *block_group,
2948 u64 *total_trimmed, u64 start, u64 bytes,
Filipe Manana55507ce2014-12-01 17:04:09 +00002949 u64 reserved_start, u64 reserved_bytes,
2950 struct btrfs_trim_range *trim_entry)
Li Zefan7fe1e642011-12-29 14:47:27 +08002951{
2952 struct btrfs_space_info *space_info = block_group->space_info;
2953 struct btrfs_fs_info *fs_info = block_group->fs_info;
Filipe Manana55507ce2014-12-01 17:04:09 +00002954 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Li Zefan7fe1e642011-12-29 14:47:27 +08002955 int ret;
2956 int update = 0;
2957 u64 trimmed = 0;
2958
2959 spin_lock(&space_info->lock);
2960 spin_lock(&block_group->lock);
2961 if (!block_group->ro) {
2962 block_group->reserved += reserved_bytes;
2963 space_info->bytes_reserved += reserved_bytes;
2964 update = 1;
2965 }
2966 spin_unlock(&block_group->lock);
2967 spin_unlock(&space_info->lock);
2968
Filipe Manana1edb647b2014-12-08 14:01:12 +00002969 ret = btrfs_discard_extent(fs_info->extent_root,
2970 start, bytes, &trimmed);
Li Zefan7fe1e642011-12-29 14:47:27 +08002971 if (!ret)
2972 *total_trimmed += trimmed;
2973
Filipe Manana55507ce2014-12-01 17:04:09 +00002974 mutex_lock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08002975 btrfs_add_free_space(block_group, reserved_start, reserved_bytes);
Filipe Manana55507ce2014-12-01 17:04:09 +00002976 list_del(&trim_entry->list);
2977 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08002978
2979 if (update) {
2980 spin_lock(&space_info->lock);
2981 spin_lock(&block_group->lock);
2982 if (block_group->ro)
2983 space_info->bytes_readonly += reserved_bytes;
2984 block_group->reserved -= reserved_bytes;
2985 space_info->bytes_reserved -= reserved_bytes;
2986 spin_unlock(&space_info->lock);
2987 spin_unlock(&block_group->lock);
2988 }
2989
2990 return ret;
2991}
2992
2993static int trim_no_bitmap(struct btrfs_block_group_cache *block_group,
2994 u64 *total_trimmed, u64 start, u64 end, u64 minlen)
Li Dongyangf7039b12011-03-24 10:24:28 +00002995{
Li Zefan34d52cb2011-03-29 13:46:06 +08002996 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
Li Zefan7fe1e642011-12-29 14:47:27 +08002997 struct btrfs_free_space *entry;
2998 struct rb_node *node;
Li Dongyangf7039b12011-03-24 10:24:28 +00002999 int ret = 0;
Li Zefan7fe1e642011-12-29 14:47:27 +08003000 u64 extent_start;
3001 u64 extent_bytes;
3002 u64 bytes;
Li Dongyangf7039b12011-03-24 10:24:28 +00003003
3004 while (start < end) {
Filipe Manana55507ce2014-12-01 17:04:09 +00003005 struct btrfs_trim_range trim_entry;
3006
3007 mutex_lock(&ctl->cache_writeout_mutex);
Li Zefan34d52cb2011-03-29 13:46:06 +08003008 spin_lock(&ctl->tree_lock);
Li Dongyangf7039b12011-03-24 10:24:28 +00003009
Li Zefan34d52cb2011-03-29 13:46:06 +08003010 if (ctl->free_space < minlen) {
3011 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003012 mutex_unlock(&ctl->cache_writeout_mutex);
Li Dongyangf7039b12011-03-24 10:24:28 +00003013 break;
3014 }
3015
Li Zefan34d52cb2011-03-29 13:46:06 +08003016 entry = tree_search_offset(ctl, start, 0, 1);
Li Zefan7fe1e642011-12-29 14:47:27 +08003017 if (!entry) {
Li Zefan34d52cb2011-03-29 13:46:06 +08003018 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003019 mutex_unlock(&ctl->cache_writeout_mutex);
Li Dongyangf7039b12011-03-24 10:24:28 +00003020 break;
3021 }
3022
Li Zefan7fe1e642011-12-29 14:47:27 +08003023 /* skip bitmaps */
3024 while (entry->bitmap) {
3025 node = rb_next(&entry->offset_index);
3026 if (!node) {
Li Zefan34d52cb2011-03-29 13:46:06 +08003027 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003028 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003029 goto out;
Li Dongyangf7039b12011-03-24 10:24:28 +00003030 }
Li Zefan7fe1e642011-12-29 14:47:27 +08003031 entry = rb_entry(node, struct btrfs_free_space,
3032 offset_index);
Li Dongyangf7039b12011-03-24 10:24:28 +00003033 }
3034
Li Zefan7fe1e642011-12-29 14:47:27 +08003035 if (entry->offset >= end) {
3036 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003037 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003038 break;
3039 }
3040
3041 extent_start = entry->offset;
3042 extent_bytes = entry->bytes;
3043 start = max(start, extent_start);
3044 bytes = min(extent_start + extent_bytes, end) - start;
3045 if (bytes < minlen) {
3046 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003047 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003048 goto next;
3049 }
3050
3051 unlink_free_space(ctl, entry);
3052 kmem_cache_free(btrfs_free_space_cachep, entry);
3053
Li Zefan34d52cb2011-03-29 13:46:06 +08003054 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003055 trim_entry.start = extent_start;
3056 trim_entry.bytes = extent_bytes;
3057 list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
3058 mutex_unlock(&ctl->cache_writeout_mutex);
Li Dongyangf7039b12011-03-24 10:24:28 +00003059
Li Zefan7fe1e642011-12-29 14:47:27 +08003060 ret = do_trimming(block_group, total_trimmed, start, bytes,
Filipe Manana55507ce2014-12-01 17:04:09 +00003061 extent_start, extent_bytes, &trim_entry);
Li Zefan7fe1e642011-12-29 14:47:27 +08003062 if (ret)
3063 break;
3064next:
Li Dongyangf7039b12011-03-24 10:24:28 +00003065 start += bytes;
Li Dongyangf7039b12011-03-24 10:24:28 +00003066
3067 if (fatal_signal_pending(current)) {
3068 ret = -ERESTARTSYS;
3069 break;
3070 }
3071
3072 cond_resched();
3073 }
Li Zefan7fe1e642011-12-29 14:47:27 +08003074out:
3075 return ret;
3076}
3077
3078static int trim_bitmaps(struct btrfs_block_group_cache *block_group,
3079 u64 *total_trimmed, u64 start, u64 end, u64 minlen)
3080{
3081 struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3082 struct btrfs_free_space *entry;
3083 int ret = 0;
3084 int ret2;
3085 u64 bytes;
3086 u64 offset = offset_to_bitmap(ctl, start);
3087
3088 while (offset < end) {
3089 bool next_bitmap = false;
Filipe Manana55507ce2014-12-01 17:04:09 +00003090 struct btrfs_trim_range trim_entry;
Li Zefan7fe1e642011-12-29 14:47:27 +08003091
Filipe Manana55507ce2014-12-01 17:04:09 +00003092 mutex_lock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003093 spin_lock(&ctl->tree_lock);
3094
3095 if (ctl->free_space < minlen) {
3096 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003097 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003098 break;
3099 }
3100
3101 entry = tree_search_offset(ctl, offset, 1, 0);
3102 if (!entry) {
3103 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003104 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003105 next_bitmap = true;
3106 goto next;
3107 }
3108
3109 bytes = minlen;
3110 ret2 = search_bitmap(ctl, entry, &start, &bytes);
3111 if (ret2 || start >= end) {
3112 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003113 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003114 next_bitmap = true;
3115 goto next;
3116 }
3117
3118 bytes = min(bytes, end - start);
3119 if (bytes < minlen) {
3120 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003121 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003122 goto next;
3123 }
3124
3125 bitmap_clear_bits(ctl, entry, start, bytes);
3126 if (entry->bytes == 0)
3127 free_bitmap(ctl, entry);
3128
3129 spin_unlock(&ctl->tree_lock);
Filipe Manana55507ce2014-12-01 17:04:09 +00003130 trim_entry.start = start;
3131 trim_entry.bytes = bytes;
3132 list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
3133 mutex_unlock(&ctl->cache_writeout_mutex);
Li Zefan7fe1e642011-12-29 14:47:27 +08003134
3135 ret = do_trimming(block_group, total_trimmed, start, bytes,
Filipe Manana55507ce2014-12-01 17:04:09 +00003136 start, bytes, &trim_entry);
Li Zefan7fe1e642011-12-29 14:47:27 +08003137 if (ret)
3138 break;
3139next:
3140 if (next_bitmap) {
3141 offset += BITS_PER_BITMAP * ctl->unit;
3142 } else {
3143 start += bytes;
3144 if (start >= offset + BITS_PER_BITMAP * ctl->unit)
3145 offset += BITS_PER_BITMAP * ctl->unit;
3146 }
3147
3148 if (fatal_signal_pending(current)) {
3149 ret = -ERESTARTSYS;
3150 break;
3151 }
3152
3153 cond_resched();
3154 }
3155
3156 return ret;
3157}
3158
3159int btrfs_trim_block_group(struct btrfs_block_group_cache *block_group,
3160 u64 *trimmed, u64 start, u64 end, u64 minlen)
3161{
3162 int ret;
3163
3164 *trimmed = 0;
3165
Filipe Manana04216822014-11-27 21:14:15 +00003166 spin_lock(&block_group->lock);
3167 if (block_group->removed) {
3168 spin_unlock(&block_group->lock);
3169 return 0;
3170 }
3171 atomic_inc(&block_group->trimming);
3172 spin_unlock(&block_group->lock);
3173
Li Zefan7fe1e642011-12-29 14:47:27 +08003174 ret = trim_no_bitmap(block_group, trimmed, start, end, minlen);
3175 if (ret)
Filipe Manana04216822014-11-27 21:14:15 +00003176 goto out;
Li Zefan7fe1e642011-12-29 14:47:27 +08003177
3178 ret = trim_bitmaps(block_group, trimmed, start, end, minlen);
Filipe Manana04216822014-11-27 21:14:15 +00003179out:
3180 spin_lock(&block_group->lock);
3181 if (atomic_dec_and_test(&block_group->trimming) &&
3182 block_group->removed) {
3183 struct extent_map_tree *em_tree;
3184 struct extent_map *em;
3185
3186 spin_unlock(&block_group->lock);
3187
Filipe Mananaa1e7e162014-12-04 15:31:01 +00003188 lock_chunks(block_group->fs_info->chunk_root);
Filipe Manana04216822014-11-27 21:14:15 +00003189 em_tree = &block_group->fs_info->mapping_tree.map_tree;
3190 write_lock(&em_tree->lock);
3191 em = lookup_extent_mapping(em_tree, block_group->key.objectid,
3192 1);
3193 BUG_ON(!em); /* logic error, can't happen */
Filipe Mananaa1e7e162014-12-04 15:31:01 +00003194 /*
3195 * remove_extent_mapping() will delete us from the pinned_chunks
3196 * list, which is protected by the chunk mutex.
3197 */
Filipe Manana04216822014-11-27 21:14:15 +00003198 remove_extent_mapping(em_tree, em);
3199 write_unlock(&em_tree->lock);
Filipe Manana04216822014-11-27 21:14:15 +00003200 unlock_chunks(block_group->fs_info->chunk_root);
3201
3202 /* once for us and once for the tree */
3203 free_extent_map(em);
3204 free_extent_map(em);
Filipe Manana946ddbe2014-12-01 17:04:40 +00003205
3206 /*
3207 * We've left one free space entry and other tasks trimming
3208 * this block group have left 1 entry each one. Free them.
3209 */
3210 __btrfs_remove_free_space_cache(block_group->free_space_ctl);
Filipe Manana04216822014-11-27 21:14:15 +00003211 } else {
3212 spin_unlock(&block_group->lock);
3213 }
Li Dongyangf7039b12011-03-24 10:24:28 +00003214
3215 return ret;
3216}
Li Zefan581bb052011-04-20 10:06:11 +08003217
3218/*
3219 * Find the left-most item in the cache tree, and then return the
3220 * smallest inode number in the item.
3221 *
3222 * Note: the returned inode number may not be the smallest one in
3223 * the tree, if the left-most item is a bitmap.
3224 */
3225u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
3226{
3227 struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
3228 struct btrfs_free_space *entry = NULL;
3229 u64 ino = 0;
3230
3231 spin_lock(&ctl->tree_lock);
3232
3233 if (RB_EMPTY_ROOT(&ctl->free_space_offset))
3234 goto out;
3235
3236 entry = rb_entry(rb_first(&ctl->free_space_offset),
3237 struct btrfs_free_space, offset_index);
3238
3239 if (!entry->bitmap) {
3240 ino = entry->offset;
3241
3242 unlink_free_space(ctl, entry);
3243 entry->offset++;
3244 entry->bytes--;
3245 if (!entry->bytes)
3246 kmem_cache_free(btrfs_free_space_cachep, entry);
3247 else
3248 link_free_space(ctl, entry);
3249 } else {
3250 u64 offset = 0;
3251 u64 count = 1;
3252 int ret;
3253
3254 ret = search_bitmap(ctl, entry, &offset, &count);
Jeff Mahoney79787ea2012-03-12 16:03:00 +01003255 /* Logic error; Should be empty if it can't find anything */
Josef Bacikb12d6862013-08-26 17:14:08 -04003256 ASSERT(!ret);
Li Zefan581bb052011-04-20 10:06:11 +08003257
3258 ino = offset;
3259 bitmap_clear_bits(ctl, entry, offset, 1);
3260 if (entry->bytes == 0)
3261 free_bitmap(ctl, entry);
3262 }
3263out:
3264 spin_unlock(&ctl->tree_lock);
3265
3266 return ino;
3267}
Li Zefan82d59022011-04-20 10:33:24 +08003268
3269struct inode *lookup_free_ino_inode(struct btrfs_root *root,
3270 struct btrfs_path *path)
3271{
3272 struct inode *inode = NULL;
3273
David Sterba57cdc8d2014-02-05 02:37:48 +01003274 spin_lock(&root->ino_cache_lock);
3275 if (root->ino_cache_inode)
3276 inode = igrab(root->ino_cache_inode);
3277 spin_unlock(&root->ino_cache_lock);
Li Zefan82d59022011-04-20 10:33:24 +08003278 if (inode)
3279 return inode;
3280
3281 inode = __lookup_free_space_inode(root, path, 0);
3282 if (IS_ERR(inode))
3283 return inode;
3284
David Sterba57cdc8d2014-02-05 02:37:48 +01003285 spin_lock(&root->ino_cache_lock);
David Sterba7841cb22011-05-31 18:07:27 +02003286 if (!btrfs_fs_closing(root->fs_info))
David Sterba57cdc8d2014-02-05 02:37:48 +01003287 root->ino_cache_inode = igrab(inode);
3288 spin_unlock(&root->ino_cache_lock);
Li Zefan82d59022011-04-20 10:33:24 +08003289
3290 return inode;
3291}
3292
3293int create_free_ino_inode(struct btrfs_root *root,
3294 struct btrfs_trans_handle *trans,
3295 struct btrfs_path *path)
3296{
3297 return __create_free_space_inode(root, trans, path,
3298 BTRFS_FREE_INO_OBJECTID, 0);
3299}
3300
3301int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
3302{
3303 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
3304 struct btrfs_path *path;
3305 struct inode *inode;
3306 int ret = 0;
3307 u64 root_gen = btrfs_root_generation(&root->root_item);
3308
Chris Mason4b9465c2011-06-03 09:36:29 -04003309 if (!btrfs_test_opt(root, INODE_MAP_CACHE))
3310 return 0;
3311
Li Zefan82d59022011-04-20 10:33:24 +08003312 /*
3313 * If we're unmounting then just return, since this does a search on the
3314 * normal root and not the commit root and we could deadlock.
3315 */
David Sterba7841cb22011-05-31 18:07:27 +02003316 if (btrfs_fs_closing(fs_info))
Li Zefan82d59022011-04-20 10:33:24 +08003317 return 0;
3318
3319 path = btrfs_alloc_path();
3320 if (!path)
3321 return 0;
3322
3323 inode = lookup_free_ino_inode(root, path);
3324 if (IS_ERR(inode))
3325 goto out;
3326
3327 if (root_gen != BTRFS_I(inode)->generation)
3328 goto out_put;
3329
3330 ret = __load_free_space_cache(root, inode, ctl, path, 0);
3331
3332 if (ret < 0)
Simon Kirbyc2cf52e2013-03-19 22:41:23 +00003333 btrfs_err(fs_info,
3334 "failed to load free ino cache for root %llu",
3335 root->root_key.objectid);
Li Zefan82d59022011-04-20 10:33:24 +08003336out_put:
3337 iput(inode);
3338out:
3339 btrfs_free_path(path);
3340 return ret;
3341}
3342
3343int btrfs_write_out_ino_cache(struct btrfs_root *root,
3344 struct btrfs_trans_handle *trans,
Filipe David Borba Manana53645a92013-09-20 14:43:28 +01003345 struct btrfs_path *path,
3346 struct inode *inode)
Li Zefan82d59022011-04-20 10:33:24 +08003347{
3348 struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
Li Zefan82d59022011-04-20 10:33:24 +08003349 int ret;
3350
Chris Mason4b9465c2011-06-03 09:36:29 -04003351 if (!btrfs_test_opt(root, INODE_MAP_CACHE))
3352 return 0;
3353
Li Zefan82d59022011-04-20 10:33:24 +08003354 ret = __btrfs_write_out_cache(root, inode, ctl, NULL, trans, path, 0);
Josef Bacikc09544e2011-08-30 10:19:10 -04003355 if (ret) {
3356 btrfs_delalloc_release_metadata(inode, inode->i_size);
3357#ifdef DEBUG
Simon Kirbyc2cf52e2013-03-19 22:41:23 +00003358 btrfs_err(root->fs_info,
3359 "failed to write free ino cache for root %llu",
3360 root->root_key.objectid);
Josef Bacikc09544e2011-08-30 10:19:10 -04003361#endif
3362 }
Li Zefan82d59022011-04-20 10:33:24 +08003363
Li Zefan82d59022011-04-20 10:33:24 +08003364 return ret;
3365}
Josef Bacik74255aa2013-03-15 09:47:08 -04003366
3367#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003368/*
3369 * Use this if you need to make a bitmap or extent entry specifically, it
3370 * doesn't do any of the merging that add_free_space does, this acts a lot like
3371 * how the free space cache loading stuff works, so you can get really weird
3372 * configurations.
3373 */
3374int test_add_free_space_entry(struct btrfs_block_group_cache *cache,
3375 u64 offset, u64 bytes, bool bitmap)
Josef Bacik74255aa2013-03-15 09:47:08 -04003376{
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003377 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3378 struct btrfs_free_space *info = NULL, *bitmap_info;
3379 void *map = NULL;
3380 u64 bytes_added;
3381 int ret;
Josef Bacik74255aa2013-03-15 09:47:08 -04003382
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003383again:
3384 if (!info) {
3385 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
3386 if (!info)
3387 return -ENOMEM;
Josef Bacik74255aa2013-03-15 09:47:08 -04003388 }
3389
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003390 if (!bitmap) {
3391 spin_lock(&ctl->tree_lock);
3392 info->offset = offset;
3393 info->bytes = bytes;
3394 ret = link_free_space(ctl, info);
3395 spin_unlock(&ctl->tree_lock);
3396 if (ret)
3397 kmem_cache_free(btrfs_free_space_cachep, info);
3398 return ret;
3399 }
Josef Bacik74255aa2013-03-15 09:47:08 -04003400
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003401 if (!map) {
3402 map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
3403 if (!map) {
3404 kmem_cache_free(btrfs_free_space_cachep, info);
3405 return -ENOMEM;
3406 }
3407 }
Josef Bacik74255aa2013-03-15 09:47:08 -04003408
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003409 spin_lock(&ctl->tree_lock);
3410 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3411 1, 0);
3412 if (!bitmap_info) {
3413 info->bitmap = map;
3414 map = NULL;
3415 add_new_bitmap(ctl, info, offset);
3416 bitmap_info = info;
Filipe Manana20005522014-08-29 13:35:13 +01003417 info = NULL;
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003418 }
Josef Bacik74255aa2013-03-15 09:47:08 -04003419
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003420 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3421 bytes -= bytes_added;
3422 offset += bytes_added;
3423 spin_unlock(&ctl->tree_lock);
3424
3425 if (bytes)
3426 goto again;
3427
Filipe Manana20005522014-08-29 13:35:13 +01003428 if (info)
3429 kmem_cache_free(btrfs_free_space_cachep, info);
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003430 if (map)
3431 kfree(map);
3432 return 0;
Josef Bacik74255aa2013-03-15 09:47:08 -04003433}
3434
3435/*
3436 * Checks to see if the given range is in the free space cache. This is really
3437 * just used to check the absence of space, so if there is free space in the
3438 * range at all we will return 1.
3439 */
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003440int test_check_exists(struct btrfs_block_group_cache *cache,
3441 u64 offset, u64 bytes)
Josef Bacik74255aa2013-03-15 09:47:08 -04003442{
3443 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3444 struct btrfs_free_space *info;
3445 int ret = 0;
3446
3447 spin_lock(&ctl->tree_lock);
3448 info = tree_search_offset(ctl, offset, 0, 0);
3449 if (!info) {
3450 info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3451 1, 0);
3452 if (!info)
3453 goto out;
3454 }
3455
3456have_info:
3457 if (info->bitmap) {
3458 u64 bit_off, bit_bytes;
3459 struct rb_node *n;
3460 struct btrfs_free_space *tmp;
3461
3462 bit_off = offset;
3463 bit_bytes = ctl->unit;
3464 ret = search_bitmap(ctl, info, &bit_off, &bit_bytes);
3465 if (!ret) {
3466 if (bit_off == offset) {
3467 ret = 1;
3468 goto out;
3469 } else if (bit_off > offset &&
3470 offset + bytes > bit_off) {
3471 ret = 1;
3472 goto out;
3473 }
3474 }
3475
3476 n = rb_prev(&info->offset_index);
3477 while (n) {
3478 tmp = rb_entry(n, struct btrfs_free_space,
3479 offset_index);
3480 if (tmp->offset + tmp->bytes < offset)
3481 break;
3482 if (offset + bytes < tmp->offset) {
3483 n = rb_prev(&info->offset_index);
3484 continue;
3485 }
3486 info = tmp;
3487 goto have_info;
3488 }
3489
3490 n = rb_next(&info->offset_index);
3491 while (n) {
3492 tmp = rb_entry(n, struct btrfs_free_space,
3493 offset_index);
3494 if (offset + bytes < tmp->offset)
3495 break;
3496 if (tmp->offset + tmp->bytes < offset) {
3497 n = rb_next(&info->offset_index);
3498 continue;
3499 }
3500 info = tmp;
3501 goto have_info;
3502 }
3503
Filipe Manana20005522014-08-29 13:35:13 +01003504 ret = 0;
Josef Bacik74255aa2013-03-15 09:47:08 -04003505 goto out;
3506 }
3507
3508 if (info->offset == offset) {
3509 ret = 1;
3510 goto out;
3511 }
3512
3513 if (offset > info->offset && offset < info->offset + info->bytes)
3514 ret = 1;
3515out:
3516 spin_unlock(&ctl->tree_lock);
3517 return ret;
3518}
Josef Bacikdc11dd5d2013-08-14 15:05:12 -04003519#endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */