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. If contains is set we will return
72 * the free space that contains the given offset. If contains is not set we
73 * will return the free space that starts at or after the given offset and is
74 * at least bytes long.
76 static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
77 u64 offset, u64 bytes,
80 struct rb_node *n = root->rb_node;
81 struct btrfs_free_space *entry, *ret = NULL;
84 entry = rb_entry(n, struct btrfs_free_space, offset_index);
86 if (offset < entry->offset) {
88 (!ret || entry->offset < ret->offset) &&
89 (bytes <= entry->bytes))
92 } else if (offset > entry->offset) {
93 if ((entry->offset + entry->bytes - 1) >= offset &&
94 bytes <= entry->bytes) {
100 if (bytes > entry->bytes) {
113 * return a chunk at least bytes size, as close to offset that we can get.
115 static struct btrfs_free_space *tree_search_bytes(struct rb_root *root,
116 u64 offset, u64 bytes)
118 struct rb_node *n = root->rb_node;
119 struct btrfs_free_space *entry, *ret = NULL;
122 entry = rb_entry(n, struct btrfs_free_space, bytes_index);
124 if (bytes < entry->bytes) {
126 * We prefer to get a hole size as close to the size we
127 * are asking for so we don't take small slivers out of
128 * huge holes, but we also want to get as close to the
129 * offset as possible so we don't have a whole lot of
132 if (offset <= entry->offset) {
135 else if (entry->bytes < ret->bytes)
137 else if (entry->offset < ret->offset)
141 } else if (bytes > entry->bytes) {
145 * Ok we may have multiple chunks of the wanted size,
146 * so we don't want to take the first one we find, we
147 * want to take the one closest to our given offset, so
148 * keep searching just in case theres a better match.
151 if (offset > entry->offset)
153 else if (!ret || entry->offset < ret->offset)
161 static void unlink_free_space(struct btrfs_block_group_cache *block_group,
162 struct btrfs_free_space *info)
164 rb_erase(&info->offset_index, &block_group->free_space_offset);
165 rb_erase(&info->bytes_index, &block_group->free_space_bytes);
168 static int link_free_space(struct btrfs_block_group_cache *block_group,
169 struct btrfs_free_space *info)
174 ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
175 &info->offset_index);
179 ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
187 int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
188 u64 offset, u64 bytes)
190 struct btrfs_free_space *right_info;
191 struct btrfs_free_space *left_info;
192 struct btrfs_free_space *info = NULL;
193 struct btrfs_free_space *alloc_info;
196 alloc_info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
201 * first we want to see if there is free space adjacent to the range we
202 * are adding, if there is remove that struct and add a new one to
203 * cover the entire range
205 spin_lock(&block_group->lock);
207 right_info = tree_search_offset(&block_group->free_space_offset,
209 left_info = tree_search_offset(&block_group->free_space_offset,
212 if (right_info && right_info->offset == offset+bytes) {
213 unlink_free_space(block_group, right_info);
215 info->offset = offset;
216 info->bytes += bytes;
217 } else if (right_info && right_info->offset != offset+bytes) {
218 printk(KERN_ERR "adding space in the middle of an existing "
219 "free space area. existing: offset=%Lu, bytes=%Lu. "
220 "new: offset=%Lu, bytes=%Lu\n", right_info->offset,
221 right_info->bytes, offset, bytes);
226 unlink_free_space(block_group, left_info);
228 if (unlikely((left_info->offset + left_info->bytes) !=
230 printk(KERN_ERR "free space to the left of new free "
231 "space isn't quite right. existing: offset=%Lu,"
232 " bytes=%Lu. new: offset=%Lu, bytes=%Lu\n",
233 left_info->offset, left_info->bytes, offset,
239 info->offset = left_info->offset;
240 info->bytes += left_info->bytes;
244 info->bytes += bytes;
249 ret = link_free_space(block_group, info);
257 info->offset = offset;
260 ret = link_free_space(block_group, info);
264 spin_unlock(&block_group->lock);
266 printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
277 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
278 u64 offset, u64 bytes)
280 struct btrfs_free_space *info;
283 spin_lock(&block_group->lock);
284 info = tree_search_offset(&block_group->free_space_offset, offset, 0,
287 if (info && info->offset == offset) {
288 if (info->bytes < bytes) {
289 printk(KERN_ERR "Found free space at %Lu, size %Lu,"
290 "trying to use %Lu\n",
291 info->offset, info->bytes, bytes);
297 unlink_free_space(block_group, info);
299 if (info->bytes == bytes) {
304 info->offset += bytes;
305 info->bytes -= bytes;
307 ret = link_free_space(block_group, info);
309 } else if (info && info->offset < offset &&
310 info->offset + info->bytes >= offset + bytes) {
311 u64 old_start = info->offset;
313 * we're freeing space in the middle of the info,
314 * this can happen during tree log replay
316 * first unlink the old info and then
317 * insert it again after the hole we're creating
319 unlink_free_space(block_group, info);
320 if (offset + bytes < info->offset + info->bytes) {
321 u64 old_end = info->offset + info->bytes;
323 info->offset = offset + bytes;
324 info->bytes = old_end - info->offset;
325 ret = link_free_space(block_group, info);
328 /* the hole we're creating ends at the end
329 * of the info struct, just free the info
334 /* step two, insert a new info struct to cover anything
337 spin_unlock(&block_group->lock);
338 ret = btrfs_add_free_space(block_group, old_start,
346 spin_unlock(&block_group->lock);
351 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
354 struct btrfs_free_space *info;
358 for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
359 info = rb_entry(n, struct btrfs_free_space, offset_index);
360 if (info->bytes >= bytes)
362 //printk(KERN_INFO "offset=%Lu, bytes=%Lu\n", info->offset,
365 printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
369 u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
371 struct btrfs_free_space *info;
375 for (n = rb_first(&block_group->free_space_offset); n;
377 info = rb_entry(n, struct btrfs_free_space, offset_index);
384 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
386 struct btrfs_free_space *info;
387 struct rb_node *node;
389 spin_lock(&block_group->lock);
390 while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
391 info = rb_entry(node, struct btrfs_free_space, bytes_index);
392 unlink_free_space(block_group, info);
394 if (need_resched()) {
395 spin_unlock(&block_group->lock);
397 spin_lock(&block_group->lock);
400 spin_unlock(&block_group->lock);
403 struct btrfs_free_space *btrfs_find_free_space_offset(struct
404 btrfs_block_group_cache
405 *block_group, u64 offset,
408 struct btrfs_free_space *ret;
410 spin_lock(&block_group->lock);
411 ret = tree_search_offset(&block_group->free_space_offset, offset,
413 spin_unlock(&block_group->lock);
418 struct btrfs_free_space *btrfs_find_free_space_bytes(struct
419 btrfs_block_group_cache
420 *block_group, u64 offset,
423 struct btrfs_free_space *ret;
425 spin_lock(&block_group->lock);
427 ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
428 spin_unlock(&block_group->lock);
433 struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
434 *block_group, u64 offset,
437 struct btrfs_free_space *ret;
439 spin_lock(&block_group->lock);
440 ret = tree_search_offset(&block_group->free_space_offset, offset,
443 ret = tree_search_bytes(&block_group->free_space_bytes,
446 spin_unlock(&block_group->lock);