git.oblomov.eu Git - linux-2.6/blob - fs/btrfs/free-space-cache.c

   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.
  72  *
  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.
  81  *
  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
  84  * return NULL.
  85  */
  86 static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
  87                                                    u64 offset, u64 bytes,
  88                                                    int fuzzy)
  89 {
  90         struct rb_node *n = root->rb_node;
  91         struct btrfs_free_space *entry, *ret = NULL;
  92
  93         while (n) {
  94                 entry = rb_entry(n, struct btrfs_free_space, offset_index);
  95
  96                 if (offset < entry->offset) {
  97                         if (fuzzy &&
  98                             (!ret || entry->offset < ret->offset) &&
  99                             (bytes <= entry->bytes))
 100                                 ret = entry;
 101                         n = n->rb_left;
 102                 } else if (offset > entry->offset) {
 103                         if (fuzzy &&
 104                             (entry->offset + entry->bytes - 1) >= offset &&
 105                             bytes <= entry->bytes) {
 106                                 ret = entry;
 107                                 break;
 108                         }
 109                         n = n->rb_right;
 110                 } else {
 111                         if (bytes > entry->bytes) {
 112                                 n = n->rb_right;
 113                                 continue;
 114                         }
 115                         ret = entry;
 116                         break;
 117                 }
 118         }
 119
 120         return ret;
 121 }
 122
 123 /*
 124  * return a chunk at least bytes size, as close to offset that we can get.
 125  */
 126 static struct btrfs_free_space *tree_search_bytes(struct rb_root *root,
 127                                                   u64 offset, u64 bytes)
 128 {
 129         struct rb_node *n = root->rb_node;
 130         struct btrfs_free_space *entry, *ret = NULL;
 131
 132         while (n) {
 133                 entry = rb_entry(n, struct btrfs_free_space, bytes_index);
 134
 135                 if (bytes < entry->bytes) {
 136                         /*
 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
 141                          * fragmentation.
 142                          */
 143                         if (offset <= entry->offset) {
 144                                 if (!ret)
 145                                         ret = entry;
 146                                 else if (entry->bytes < ret->bytes)
 147                                         ret = entry;
 148                                 else if (entry->offset < ret->offset)
 149                                         ret = entry;
 150                         }
 151                         n = n->rb_left;
 152                 } else if (bytes > entry->bytes) {
 153                         n = n->rb_right;
 154                 } else {
 155                         /*
 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.
 160                          */
 161                         n = n->rb_right;
 162                         if (offset > entry->offset)
 163                                 continue;
 164                         else if (!ret || entry->offset < ret->offset)
 165                                 ret = entry;
 166                 }
 167         }
 168
 169         return ret;
 170 }
 171
 172 static void unlink_free_space(struct btrfs_block_group_cache *block_group,
 173                               struct btrfs_free_space *info)
 174 {
 175         rb_erase(&info->offset_index, &block_group->free_space_offset);
 176         rb_erase(&info->bytes_index, &block_group->free_space_bytes);
 177 }
 178
 179 static int link_free_space(struct btrfs_block_group_cache *block_group,
 180                            struct btrfs_free_space *info)
 181 {
 182         int ret = 0;
 183
 184
 185         ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
 186                                  &info->offset_index);
 187         if (ret)
 188                 return ret;
 189
 190         ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
 191                                 &info->bytes_index);
 192         if (ret)
 193                 return ret;
 194
 195         return ret;
 196 }
 197
 198 static int __btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
 199                                   u64 offset, u64 bytes)
 200 {
 201         struct btrfs_free_space *right_info;
 202         struct btrfs_free_space *left_info;
 203         struct btrfs_free_space *info = NULL;
 204         int ret = 0;
 205
 206         /*
 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
 210          */
 211         right_info = tree_search_offset(&block_group->free_space_offset,
 212                                         offset+bytes, 0, 0);
 213         left_info = tree_search_offset(&block_group->free_space_offset,
 214                                        offset-1, 0, 1);
 215
 216         if (right_info) {
 217                 unlink_free_space(block_group, right_info);
 218                 info = right_info;
 219                 info->offset = offset;
 220                 info->bytes += bytes;
 221         }
 222
 223         if (left_info && left_info->offset + left_info->bytes == offset) {
 224                 unlink_free_space(block_group, left_info);
 225
 226                 if (info) {
 227                         info->offset = left_info->offset;
 228                         info->bytes += left_info->bytes;
 229                         kfree(left_info);
 230                 } else {
 231                         info = left_info;
 232                         info->bytes += bytes;
 233                 }
 234         }
 235
 236         if (info) {
 237                 ret = link_free_space(block_group, info);
 238                 if (ret)
 239                         kfree(info);
 240                 goto out;
 241         }
 242
 243         info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
 244         if (!info)
 245                 return -ENOMEM;
 246
 247         info->offset = offset;
 248         info->bytes = bytes;
 249
 250         ret = link_free_space(block_group, info);
 251         if (ret)
 252                 kfree(info);
 253 out:
 254         if (ret) {
 255                 printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
 256                 if (ret == -EEXIST)
 257                         BUG();
 258         }
 259
 260         return ret;
 261 }
 262
 263 static int
 264 __btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
 265                           u64 offset, u64 bytes)
 266 {
 267         struct btrfs_free_space *info;
 268         int ret = 0;
 269
 270         BUG_ON(!block_group->cached);
 271         info = tree_search_offset(&block_group->free_space_offset, offset, 0,
 272                                   1);
 273
 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);
 281                         WARN_ON(1);
 282                         ret = -EINVAL;
 283                         goto out;
 284                 }
 285                 unlink_free_space(block_group, info);
 286
 287                 if (info->bytes == bytes) {
 288                         kfree(info);
 289                         goto out;
 290                 }
 291
 292                 info->offset += bytes;
 293                 info->bytes -= bytes;
 294
 295                 ret = link_free_space(block_group, info);
 296                 BUG_ON(ret);
 297         } else if (info && info->offset < offset &&
 298                    info->offset + info->bytes >= offset + bytes) {
 299                 u64 old_start = info->offset;
 300                 /*
 301                  * we're freeing space in the middle of the info,
 302                  * this can happen during tree log replay
 303                  *
 304                  * first unlink the old info and then
 305                  * insert it again after the hole we're creating
 306                  */
 307                 unlink_free_space(block_group, info);
 308                 if (offset + bytes < info->offset + info->bytes) {
 309                         u64 old_end = info->offset + info->bytes;
 310
 311                         info->offset = offset + bytes;
 312                         info->bytes = old_end - info->offset;
 313                         ret = link_free_space(block_group, info);
 314                         BUG_ON(ret);
 315                 } else {
 316                         /* the hole we're creating ends at the end
 317                          * of the info struct, just free the info
 318                          */
 319                         kfree(info);
 320                 }
 321
 322                 /* step two, insert a new info struct to cover anything
 323                  * before the hole
 324                  */
 325                 ret = __btrfs_add_free_space(block_group, old_start,
 326                                              offset - old_start);
 327                 BUG_ON(ret);
 328         } else {
 329                 if (!info) {
 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);
 336                 } else if (info) {
 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);
 340                 }
 341                 WARN_ON(1);
 342         }
 343 out:
 344         return ret;
 345 }
 346
 347 int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
 348                          u64 offset, u64 bytes)
 349 {
 350         int ret;
 351
 352         mutex_lock(&block_group->alloc_mutex);
 353         ret = __btrfs_add_free_space(block_group, offset, bytes);
 354         mutex_unlock(&block_group->alloc_mutex);
 355
 356         return ret;
 357 }
 358
 359 int btrfs_add_free_space_lock(struct btrfs_block_group_cache *block_group,
 360                               u64 offset, u64 bytes)
 361 {
 362         int ret;
 363
 364         ret = __btrfs_add_free_space(block_group, offset, bytes);
 365
 366         return ret;
 367 }
 368
 369 int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
 370                             u64 offset, u64 bytes)
 371 {
 372         int ret = 0;
 373
 374         mutex_lock(&block_group->alloc_mutex);
 375         ret = __btrfs_remove_free_space(block_group, offset, bytes);
 376         mutex_unlock(&block_group->alloc_mutex);
 377
 378         return ret;
 379 }
 380
 381 int btrfs_remove_free_space_lock(struct btrfs_block_group_cache *block_group,
 382                                  u64 offset, u64 bytes)
 383 {
 384         int ret;
 385
 386         ret = __btrfs_remove_free_space(block_group, offset, bytes);
 387
 388         return ret;
 389 }
 390
 391 void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
 392                            u64 bytes)
 393 {
 394         struct btrfs_free_space *info;
 395         struct rb_node *n;
 396         int count = 0;
 397
 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)
 401                         count++;
 402                 printk(KERN_ERR "entry offset %llu, bytes %llu\n", info->offset,
 403                        info->bytes);
 404         }
 405         printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
 406                "\n", count);
 407 }
 408
 409 u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
 410 {
 411         struct btrfs_free_space *info;
 412         struct rb_node *n;
 413         u64 ret = 0;
 414
 415         for (n = rb_first(&block_group->free_space_offset); n;
 416              n = rb_next(n)) {
 417                 info = rb_entry(n, struct btrfs_free_space, offset_index);
 418                 ret += info->bytes;
 419         }
 420
 421         return ret;
 422 }
 423
 424 void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
 425 {
 426         struct btrfs_free_space *info;
 427         struct rb_node *node;
 428
 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);
 433                 kfree(info);
 434                 if (need_resched()) {
 435                         mutex_unlock(&block_group->alloc_mutex);
 436                         cond_resched();
 437                         mutex_lock(&block_group->alloc_mutex);
 438                 }
 439         }
 440         mutex_unlock(&block_group->alloc_mutex);
 441 }
 442
 443 #if 0
 444 static struct btrfs_free_space *btrfs_find_free_space_offset(struct
 445                                                       btrfs_block_group_cache
 446                                                       *block_group, u64 offset,
 447                                                       u64 bytes)
 448 {
 449         struct btrfs_free_space *ret;
 450
 451         mutex_lock(&block_group->alloc_mutex);
 452         ret = tree_search_offset(&block_group->free_space_offset, offset,
 453                                  bytes, 0);
 454         mutex_unlock(&block_group->alloc_mutex);
 455
 456         return ret;
 457 }
 458
 459 static struct btrfs_free_space *btrfs_find_free_space_bytes(struct
 460                                                      btrfs_block_group_cache
 461                                                      *block_group, u64 offset,
 462                                                      u64 bytes)
 463 {
 464         struct btrfs_free_space *ret;
 465
 466         mutex_lock(&block_group->alloc_mutex);
 467
 468         ret = tree_search_bytes(&block_group->free_space_bytes, offset, bytes);
 469         mutex_unlock(&block_group->alloc_mutex);
 470
 471         return ret;
 472 }
 473 #endif
 474
 475 struct btrfs_free_space *btrfs_find_free_space(struct btrfs_block_group_cache
 476                                                *block_group, u64 offset,
 477                                                u64 bytes)
 478 {
 479         struct btrfs_free_space *ret = NULL;
 480
 481         ret = tree_search_offset(&block_group->free_space_offset, offset,
 482                                  bytes, 1);
 483         if (!ret)
 484                 ret = tree_search_bytes(&block_group->free_space_bytes,
 485                                         offset, bytes);
 486
 487         return ret;
 488 }