2 * Copyright (C) 2008 Red Hat. All rights reserved.
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.
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.
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.
19 #include <linux/sched.h>
22 static int tree_insert_offset(struct rb_root *root, u64 offset,
25 struct rb_node **p = &root->rb_node;
26 struct rb_node *parent = NULL;
27 struct btrfs_free_space *info;
31 info = rb_entry(parent, struct btrfs_free_space, offset_index);
33 if (offset < info->offset)
35 else if (offset > info->offset)
41 rb_link_node(node, parent, p);
42 rb_insert_color(node, root);
47 static int tree_insert_bytes(struct rb_root *root, u64 bytes,
50 struct rb_node **p = &root->rb_node;
51 struct rb_node *parent = NULL;
52 struct btrfs_free_space *info;
56 info = rb_entry(parent, struct btrfs_free_space, bytes_index);
58 if (bytes < info->bytes)
64 rb_link_node(node, parent, p);
65 rb_insert_color(node, root);
71 * searches the tree for the given offset.
73 * fuzzy == 1: this is used for allocations where we are given a hint of where
74 * to look for free space. Because the hint may not be completely on an offset
75 * mark, or the hint may no longer point to free space we need to fudge our
76 * results a bit. So we look for free space starting at or after offset with at
77 * least bytes size. We prefer to find as close to the given offset as we can.
78 * Also if the offset is within a free space range, then we will return the free
79 * space that contains the given offset, which means we can return a free space
80 * chunk with an offset before the provided offset.
82 * fuzzy == 0: this is just a normal tree search. Give us the free space that
83 * starts at the given offset which is at least bytes size, and if its not there
86 static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
87 u64 offset, u64 bytes,
90 struct rb_node *n = root->rb_node;
91 struct btrfs_free_space *entry, *ret = NULL;
94 entry = rb_entry(n, struct btrfs_free_space, offset_index);
96 if (offset < entry->offset) {
98 (!ret || entry->offset < ret->offset) &&
99 (bytes <= entry->bytes))
102 } else if (offset > entry->offset) {
104 (entry->offset + entry->bytes - 1) >= offset &&
105 bytes <= entry->bytes) {
111 if (bytes > entry->bytes) {
124 * return a chunk at least bytes size, as close to offset that we can get.
126 static struct btrfs_free_space *tree_search_bytes(struct rb_root *root,
127 u64 offset, u64 bytes)
129 struct rb_node *n = root->rb_node;
130 struct btrfs_free_space *entry, *ret = NULL;
133 entry = rb_entry(n, struct btrfs_free_space, bytes_index);
135 if (bytes < entry->bytes) {
137 * We prefer to get a hole size as close to the size we
138 * are asking for so we don't take small slivers out of
139 * huge holes, but we also want to get as close to the
140 * offset as possible so we don't have a whole lot of
143 if (offset <= entry->offset) {
146 else if (entry->bytes < ret->bytes)
148 else if (entry->offset < ret->offset)
152 } else if (bytes > entry->bytes) {
156 * Ok we may have multiple chunks of the wanted size,
157 * so we don't want to take the first one we find, we
158 * want to take the one closest to our given offset, so
159 * keep searching just in case theres a better match.
162 if (offset > entry->offset)
164 else if (!ret || entry->offset < ret->offset)
172 static void unlink_free_space(struct btrfs_block_group_cache *block_group,
173 struct btrfs_free_space *info)
175 rb_erase(&info->offset_index, &block_group->free_space_offset);
176 rb_erase(&info->bytes_index, &block_group->free_space_bytes);
179 static int link_free_space(struct btrfs_block_group_cache *block_group,
180 struct btrfs_free_space *info)
185 ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
186 &info->offset_index);
190 ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
198 static int __btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
199 u64 offset, u64 bytes)
201 struct btrfs_free_space *right_info;
202 struct btrfs_free_space *left_info;
203 struct btrfs_free_space *info = NULL;
207 * first we want to see if there is free space adjacent to the range we
208 * are adding, if there is remove that struct and add a new one to
209 * cover the entire range
211 right_info = tree_search_offset(&block_group->free_space_offset,
213 left_info = tree_search_offset(&block_group->free_space_offset,
217 unlink_free_space(block_group, right_info);
219 info->offset = offset;
220 info->bytes += bytes;
223 if (left_info && left_info->offset + left_info->bytes == offset) {
224 unlink_free_space(block_group, left_info);
227 info->offset = left_info->offset;
228 info->bytes += left_info->bytes;
232 info->bytes += bytes;
237 ret = link_free_space(block_group, info);
243 info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
247 info->offset = offset;
250 ret = link_free_space(block_group, info);
255 printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
264 __btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
265 u64 offset, u64 bytes)
267 struct btrfs_free_space *info;
270 BUG_ON(!block_group->cached);
271 info = tree_search_offset(&block_group->free_space_offset, offset, 0,
274 if (info && info->offset == offset) {
275 if (info->bytes < bytes) {
276 printk(KERN_ERR "Found free space at %llu, size %llu,"
277 "trying to use %llu\n",
278 (unsigned long long)info->offset,
279 (unsigned long long)info->bytes,
280 (unsigned long long)bytes);
285 unlink_free_space(block_group, info);
287 if (info->bytes == bytes) {
292 info->offset += bytes;
293 info->bytes -= bytes;
295 ret = link_free_space(block_group, info);
297 } else if (info && info->offset < offset &&
298 info->offset + info->bytes >= offset + bytes) {
299 u64 old_start = info->offset;
301 * we're freeing space in the middle of the info,
302 * this can happen during tree log replay
304 * first unlink the old info and then
305 * insert it again after the hole we're creating
307 unlink_free_space(block_group, info);
308 if (offset + bytes < info->offset + info->bytes) {
309 u64 old_end = info->offset + info->bytes;
311 info->offset = offset + bytes;
312 info->bytes = old_end - info->offset;
313 ret = link_free_space(block_group, info);
316 /* the hole we're creating ends at the end
317 * of the info struct, just free the info
322 /* step two, insert a new info struct to cover anything
325 ret = __btrfs_add_free_space(block_group, old_start,
330 printk(KERN_ERR "couldn't find space %llu to free\n",
331 (unsigned long long)offset);
332 printk(KERN_ERR "cached is %d, offset %llu bytes %llu\n",
333 block_group->cached, block_group->key.objectid,
334 block_group->key.offset);
335 btrfs_dump_free_space(block_group, bytes);
337 printk(KERN_ERR "hmm, found offset=%llu bytes=%llu, "
338 "but wanted offset=%llu bytes=%llu\n",
339 info->offset, info->bytes, offset, bytes);
347 int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
348 u64 offset, u64 bytes)
352 mutex_lock(&block_group->alloc_mutex);
353 ret = __btrfs_add_free_space(block_group, offset, bytes);
354 mutex_unlock(&block_group->alloc_mutex);
359 int btrfs_add_free_space_lock(struct btrfs_block_group_cache *block_group,
360 u64 offset, u64 bytes)
364 ret = __btrfs_add_free_space(block_group, offset, bytes);
369 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
370 u64 offset, u64 bytes)
374 mutex_lock(&block_group->alloc_mutex);
375 ret = __btrfs_remove_free_space(block_group, offset, bytes);
376 mutex_unlock(&block_group->alloc_mutex);
381 int btrfs_remove_free_space_lock(struct btrfs_block_group_cache *block_group,
382 u64 offset, u64 bytes)
386 ret = __btrfs_remove_free_space(block_group, offset, bytes);
391 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
394 struct btrfs_free_space *info;
398 for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
399 info = rb_entry(n, struct btrfs_free_space, offset_index);
400 if (info->bytes >= bytes)
402 printk(KERN_ERR "entry offset %llu, bytes %llu\n", info->offset,
405 printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
409 u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
411 struct btrfs_free_space *info;
415 for (n = rb_first(&block_group->free_space_offset); n;
417 info = rb_entry(n, struct btrfs_free_space, offset_index);
424 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
426 struct btrfs_free_space *info;
427 struct rb_node *node;
429 mutex_lock(&block_group->alloc_mutex);
430 while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
431 info = rb_entry(node, struct btrfs_free_space, bytes_index);
432 unlink_free_space(block_group, info);
434 if (need_resched()) {
435 mutex_unlock(&block_group->alloc_mutex);
437 mutex_lock(&block_group->alloc_mutex);
440 mutex_unlock(&block_group->alloc_mutex);
444 static struct btrfs_free_space *btrfs_find_free_space_offset(struct
445 btrfs_block_group_cache
446 *block_group, u64 offset,
449 struct btrfs_free_space *ret;
451 mutex_lock(&block_group->alloc_mutex);
452 ret = tree_search_offset(&block_group->free_space_offset, offset,
454 mutex_unlock(&block_group->alloc_mutex);
459 static struct btrfs_free_space *btrfs_find_free_space_bytes(struct
460 btrfs_block_group_cache
461 *block_group, u64 offset,
464 struct btrfs_free_space *ret;
466 mutex_lock(&block_group->alloc_mutex);
468 ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
469 mutex_unlock(&block_group->alloc_mutex);
475 struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
476 *block_group, u64 offset,
479 struct btrfs_free_space *ret = NULL;
481 ret = tree_search_offset(&block_group->free_space_offset, offset,
484 ret = tree_search_bytes(&block_group->free_space_bytes,