SAFE public projects git trees. - safe/jmp/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.  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 }