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) {
94 (entry->offset + entry->bytes - 1) >= offset) {
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);
313 spin_unlock(&block_group->lock);
317 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
320 struct btrfs_free_space *info;
324 for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
325 info = rb_entry(n, struct btrfs_free_space, offset_index);
326 if (info->bytes >= bytes)
328 //printk(KERN_INFO "offset=%Lu, bytes=%Lu\n", info->offset,
331 printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
335 u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
337 struct btrfs_free_space *info;
341 for (n = rb_first(&block_group->free_space_offset); n;
343 info = rb_entry(n, struct btrfs_free_space, offset_index);
350 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
352 struct btrfs_free_space *info;
353 struct rb_node *node;
355 spin_lock(&block_group->lock);
356 while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
357 info = rb_entry(node, struct btrfs_free_space, bytes_index);
358 unlink_free_space(block_group, info);
360 if (need_resched()) {
361 spin_unlock(&block_group->lock);
363 spin_lock(&block_group->lock);
366 spin_unlock(&block_group->lock);
369 struct btrfs_free_space *btrfs_find_free_space_offset(struct
370 btrfs_block_group_cache
371 *block_group, u64 offset,
374 struct btrfs_free_space *ret;
376 spin_lock(&block_group->lock);
377 ret = tree_search_offset(&block_group->free_space_offset, offset,
379 spin_unlock(&block_group->lock);
384 struct btrfs_free_space *btrfs_find_free_space_bytes(struct
385 btrfs_block_group_cache
386 *block_group, u64 offset,
389 struct btrfs_free_space *ret;
391 spin_lock(&block_group->lock);
393 ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
394 spin_unlock(&block_group->lock);
399 struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
400 *block_group, u64 offset,
403 struct btrfs_free_space *ret;
405 spin_lock(&block_group->lock);
406 ret = tree_search_offset(&block_group->free_space_offset, offset,
409 ret = tree_search_bytes(&block_group->free_space_bytes,
412 spin_unlock(&block_group->lock);