1 /* 2 * Copyright (C) 2008 Red Hat. All rights reserved. 3 * 4 * This program is free software; you can redistribute it and/or 5 * modify it under the terms of the GNU General Public 6 * License v2 as published by the Free Software Foundation. 7 * 8 * This program is distributed in the hope that it will be useful, 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 11 * General Public License for more details. 12 * 13 * You should have received a copy of the GNU General Public 14 * License along with this program; if not, write to the 15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330, 16 * Boston, MA 021110-1307, USA. 17 */ 18 19 #include <linux/sched.h> 20 #include "ctree.h" 21 22 static int tree_insert_offset(struct rb_root *root, u64 offset, 23 struct rb_node *node) 24 { 25 struct rb_node **p = &root->rb_node; 26 struct rb_node *parent = NULL; 27 struct btrfs_free_space *info; 28 29 while (*p) { 30 parent = *p; 31 info = rb_entry(parent, struct btrfs_free_space, offset_index); 32 33 if (offset < info->offset) 34 p = &(*p)->rb_left; 35 else if (offset > info->offset) 36 p = &(*p)->rb_right; 37 else 38 return -EEXIST; 39 } 40 41 rb_link_node(node, parent, p); 42 rb_insert_color(node, root); 43 44 return 0; 45 } 46 47 static int tree_insert_bytes(struct rb_root *root, u64 bytes, 48 struct rb_node *node) 49 { 50 struct rb_node **p = &root->rb_node; 51 struct rb_node *parent = NULL; 52 struct btrfs_free_space *info; 53 54 while (*p) { 55 parent = *p; 56 info = rb_entry(parent, struct btrfs_free_space, bytes_index); 57 58 if (bytes < info->bytes) 59 p = &(*p)->rb_left; 60 else 61 p = &(*p)->rb_right; 62 } 63 64 rb_link_node(node, parent, p); 65 rb_insert_color(node, root); 66 67 return 0; 68 } 69 70 /* 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. 75 */ 76 static struct btrfs_free_space *tree_search_offset(struct rb_root *root, 77 u64 offset, u64 bytes, 78 int contains) 79 { 80 struct rb_node *n = root->rb_node; 81 struct btrfs_free_space *entry, *ret = NULL; 82 83 while (n) { 84 entry = rb_entry(n, struct btrfs_free_space, offset_index); 85 86 if (offset < entry->offset) { 87 if (!contains && 88 (!ret || entry->offset < ret->offset) && 89 (bytes <= entry->bytes)) 90 ret = entry; 91 n = n->rb_left; 92 } else if (offset > entry->offset) { 93 if ((entry->offset + entry->bytes - 1) >= offset && 94 bytes <= entry->bytes) { 95 ret = entry; 96 break; 97 } 98 n = n->rb_right; 99 } else { 100 if (bytes > entry->bytes) { 101 n = n->rb_right; 102 continue; 103 } 104 ret = entry; 105 break; 106 } 107 } 108 109 return ret; 110 } 111 112 /* 113 * return a chunk at least bytes size, as close to offset that we can get. 114 */ 115 static struct btrfs_free_space *tree_search_bytes(struct rb_root *root, 116 u64 offset, u64 bytes) 117 { 118 struct rb_node *n = root->rb_node; 119 struct btrfs_free_space *entry, *ret = NULL; 120 121 while (n) { 122 entry = rb_entry(n, struct btrfs_free_space, bytes_index); 123 124 if (bytes < entry->bytes) { 125 /* 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 130 * fragmentation. 131 */ 132 if (offset <= entry->offset) { 133 if (!ret) 134 ret = entry; 135 else if (entry->bytes < ret->bytes) 136 ret = entry; 137 else if (entry->offset < ret->offset) 138 ret = entry; 139 } 140 n = n->rb_left; 141 } else if (bytes > entry->bytes) { 142 n = n->rb_right; 143 } else { 144 /* 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. 149 */ 150 n = n->rb_right; 151 if (offset > entry->offset) 152 continue; 153 else if (!ret || entry->offset < ret->offset) 154 ret = entry; 155 } 156 } 157 158 return ret; 159 } 160 161 static void unlink_free_space(struct btrfs_block_group_cache *block_group, 162 struct btrfs_free_space *info) 163 { 164 rb_erase(&info->offset_index, &block_group->free_space_offset); 165 rb_erase(&info->bytes_index, &block_group->free_space_bytes); 166 } 167 168 static int link_free_space(struct btrfs_block_group_cache *block_group, 169 struct btrfs_free_space *info) 170 { 171 int ret = 0; 172 173 174 ret = tree_insert_offset(&block_group->free_space_offset, info->offset, 175 &info->offset_index); 176 if (ret) 177 return ret; 178 179 ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes, 180 &info->bytes_index); 181 if (ret) 182 return ret; 183 184 return ret; 185 } 186 187 static int __btrfs_add_free_space(struct btrfs_block_group_cache *block_group, 188 u64 offset, u64 bytes) 189 { 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; 194 int ret = 0; 195 196 alloc_info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS); 197 if (!alloc_info) 198 return -ENOMEM; 199 200 /* 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 204 */ 205 right_info = tree_search_offset(&block_group->free_space_offset, 206 offset+bytes, 0, 1); 207 left_info = tree_search_offset(&block_group->free_space_offset, 208 offset-1, 0, 1); 209 210 if (right_info && right_info->offset == offset+bytes) { 211 unlink_free_space(block_group, right_info); 212 info = right_info; 213 info->offset = offset; 214 info->bytes += bytes; 215 } else if (right_info && right_info->offset != offset+bytes) { 216 printk(KERN_ERR "btrfs adding space in the middle of an " 217 "existing free space area. existing: " 218 "offset=%llu, bytes=%llu. new: offset=%llu, " 219 "bytes=%llu\n", (unsigned long long)right_info->offset, 220 (unsigned long long)right_info->bytes, 221 (unsigned long long)offset, 222 (unsigned long long)bytes); 223 BUG(); 224 } 225 226 if (left_info) { 227 unlink_free_space(block_group, left_info); 228 229 if (unlikely((left_info->offset + left_info->bytes) != 230 offset)) { 231 printk(KERN_ERR "btrfs free space to the left " 232 "of new free space isn't " 233 "quite right. existing: offset=%llu, " 234 "bytes=%llu. new: offset=%llu, bytes=%llu\n", 235 (unsigned long long)left_info->offset, 236 (unsigned long long)left_info->bytes, 237 (unsigned long long)offset, 238 (unsigned long long)bytes); 239 BUG(); 240 } 241 242 if (info) { 243 info->offset = left_info->offset; 244 info->bytes += left_info->bytes; 245 kfree(left_info); 246 } else { 247 info = left_info; 248 info->bytes += bytes; 249 } 250 } 251 252 if (info) { 253 ret = link_free_space(block_group, info); 254 if (!ret) 255 info = NULL; 256 goto out; 257 } 258 259 info = alloc_info; 260 alloc_info = NULL; 261 info->offset = offset; 262 info->bytes = bytes; 263 264 ret = link_free_space(block_group, info); 265 if (ret) 266 kfree(info); 267 out: 268 if (ret) { 269 printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret); 270 if (ret == -EEXIST) 271 BUG(); 272 } 273 274 kfree(alloc_info); 275 276 return ret; 277 } 278 279 static int 280 __btrfs_remove_free_space(struct btrfs_block_group_cache *block_group, 281 u64 offset, u64 bytes) 282 { 283 struct btrfs_free_space *info; 284 int ret = 0; 285 286 info = tree_search_offset(&block_group->free_space_offset, offset, 0, 287 1); 288 289 if (info && info->offset == offset) { 290 if (info->bytes < bytes) { 291 printk(KERN_ERR "Found free space at %llu, size %llu," 292 "trying to use %llu\n", 293 (unsigned long long)info->offset, 294 (unsigned long long)info->bytes, 295 (unsigned long long)bytes); 296 WARN_ON(1); 297 ret = -EINVAL; 298 goto out; 299 } 300 unlink_free_space(block_group, info); 301 302 if (info->bytes == bytes) { 303 kfree(info); 304 goto out; 305 } 306 307 info->offset += bytes; 308 info->bytes -= bytes; 309 310 ret = link_free_space(block_group, info); 311 BUG_ON(ret); 312 } else if (info && info->offset < offset && 313 info->offset + info->bytes >= offset + bytes) { 314 u64 old_start = info->offset; 315 /* 316 * we're freeing space in the middle of the info, 317 * this can happen during tree log replay 318 * 319 * first unlink the old info and then 320 * insert it again after the hole we're creating 321 */ 322 unlink_free_space(block_group, info); 323 if (offset + bytes < info->offset + info->bytes) { 324 u64 old_end = info->offset + info->bytes; 325 326 info->offset = offset + bytes; 327 info->bytes = old_end - info->offset; 328 ret = link_free_space(block_group, info); 329 BUG_ON(ret); 330 } else { 331 /* the hole we're creating ends at the end 332 * of the info struct, just free the info 333 */ 334 kfree(info); 335 } 336 337 /* step two, insert a new info struct to cover anything 338 * before the hole 339 */ 340 ret = __btrfs_add_free_space(block_group, old_start, 341 offset - old_start); 342 BUG_ON(ret); 343 } else { 344 WARN_ON(1); 345 } 346 out: 347 return ret; 348 } 349 350 int btrfs_add_free_space(struct btrfs_block_group_cache *block_group, 351 u64 offset, u64 bytes) 352 { 353 int ret; 354 struct btrfs_free_space *sp; 355 356 mutex_lock(&block_group->alloc_mutex); 357 ret = __btrfs_add_free_space(block_group, offset, bytes); 358 sp = tree_search_offset(&block_group->free_space_offset, offset, 0, 1); 359 BUG_ON(!sp); 360 mutex_unlock(&block_group->alloc_mutex); 361 362 return ret; 363 } 364 365 int btrfs_add_free_space_lock(struct btrfs_block_group_cache *block_group, 366 u64 offset, u64 bytes) 367 { 368 int ret; 369 struct btrfs_free_space *sp; 370 371 ret = __btrfs_add_free_space(block_group, offset, bytes); 372 sp = tree_search_offset(&block_group->free_space_offset, offset, 0, 1); 373 BUG_ON(!sp); 374 375 return ret; 376 } 377 378 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group, 379 u64 offset, u64 bytes) 380 { 381 int ret = 0; 382 383 mutex_lock(&block_group->alloc_mutex); 384 ret = __btrfs_remove_free_space(block_group, offset, bytes); 385 mutex_unlock(&block_group->alloc_mutex); 386 387 return ret; 388 } 389 390 int btrfs_remove_free_space_lock(struct btrfs_block_group_cache *block_group, 391 u64 offset, u64 bytes) 392 { 393 int ret; 394 395 ret = __btrfs_remove_free_space(block_group, offset, bytes); 396 397 return ret; 398 } 399 400 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group, 401 u64 bytes) 402 { 403 struct btrfs_free_space *info; 404 struct rb_node *n; 405 int count = 0; 406 407 for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) { 408 info = rb_entry(n, struct btrfs_free_space, offset_index); 409 if (info->bytes >= bytes) 410 count++; 411 } 412 printk(KERN_INFO "%d blocks of free space at or bigger than bytes is" 413 "\n", count); 414 } 415 416 u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group) 417 { 418 struct btrfs_free_space *info; 419 struct rb_node *n; 420 u64 ret = 0; 421 422 for (n = rb_first(&block_group->free_space_offset); n; 423 n = rb_next(n)) { 424 info = rb_entry(n, struct btrfs_free_space, offset_index); 425 ret += info->bytes; 426 } 427 428 return ret; 429 } 430 431 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group) 432 { 433 struct btrfs_free_space *info; 434 struct rb_node *node; 435 436 mutex_lock(&block_group->alloc_mutex); 437 while ((node = rb_last(&block_group->free_space_bytes)) != NULL) { 438 info = rb_entry(node, struct btrfs_free_space, bytes_index); 439 unlink_free_space(block_group, info); 440 kfree(info); 441 if (need_resched()) { 442 mutex_unlock(&block_group->alloc_mutex); 443 cond_resched(); 444 mutex_lock(&block_group->alloc_mutex); 445 } 446 } 447 mutex_unlock(&block_group->alloc_mutex); 448 } 449 450 #if 0 451 static struct btrfs_free_space *btrfs_find_free_space_offset(struct 452 btrfs_block_group_cache 453 *block_group, u64 offset, 454 u64 bytes) 455 { 456 struct btrfs_free_space *ret; 457 458 mutex_lock(&block_group->alloc_mutex); 459 ret = tree_search_offset(&block_group->free_space_offset, offset, 460 bytes, 0); 461 mutex_unlock(&block_group->alloc_mutex); 462 463 return ret; 464 } 465 466 static struct btrfs_free_space *btrfs_find_free_space_bytes(struct 467 btrfs_block_group_cache 468 *block_group, u64 offset, 469 u64 bytes) 470 { 471 struct btrfs_free_space *ret; 472 473 mutex_lock(&block_group->alloc_mutex); 474 475 ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes); 476 mutex_unlock(&block_group->alloc_mutex); 477 478 return ret; 479 } 480 #endif 481 482 struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache 483 *block_group, u64 offset, 484 u64 bytes) 485 { 486 struct btrfs_free_space *ret = NULL; 487 488 ret = tree_search_offset(&block_group->free_space_offset, offset, 489 bytes, 0); 490 if (!ret) 491 ret = tree_search_bytes(&block_group->free_space_bytes, 492 offset, bytes); 493 494 return ret; 495 } 496