Btrfs: rework allocation clustering

[linux-2.6/btrfs-unstable.git] / fs / btrfs / free-space-cache.c

/*
 * Copyright (C) 2008 Red Hat.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License v2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 021110-1307, USA.
 */

#include <linux/sched.h>
#include "ctree.h"
#include "free-space-cache.h"
#include "transaction.h"

struct btrfs_free_space {
        struct rb_node bytes_index;
        struct rb_node offset_index;
        u64 offset;
        u64 bytes;
};

static int tree_insert_offset(struct rb_root *root, u64 offset,
                              struct rb_node *node)
{
        struct rb_node **p = &root->rb_node;
        struct rb_node *parent = NULL;
        struct btrfs_free_space *info;

        while (*p) {
                parent = *p;
                info = rb_entry(parent, struct btrfs_free_space, offset_index);

                if (offset < info->offset)
                        p = &(*p)->rb_left;
                else if (offset > info->offset)
                        p = &(*p)->rb_right;
                else
                        return -EEXIST;
        }

        rb_link_node(node, parent, p);
        rb_insert_color(node, root);

        return 0;
}

static int tree_insert_bytes(struct rb_root *root, u64 bytes,
                             struct rb_node *node)
{
        struct rb_node **p = &root->rb_node;
        struct rb_node *parent = NULL;
        struct btrfs_free_space *info;

        while (*p) {
                parent = *p;
                info = rb_entry(parent, struct btrfs_free_space, bytes_index);

                if (bytes < info->bytes)
                        p = &(*p)->rb_left;
                else
                        p = &(*p)->rb_right;
        }

        rb_link_node(node, parent, p);
        rb_insert_color(node, root);

        return 0;
}

/*
 * searches the tree for the given offset.
 *
 * fuzzy == 1: this is used for allocations where we are given a hint of where
 * to look for free space.  Because the hint may not be completely on an offset
 * mark, or the hint may no longer point to free space we need to fudge our
 * results a bit.  So we look for free space starting at or after offset with at
 * least bytes size.  We prefer to find as close to the given offset as we can.
 * Also if the offset is within a free space range, then we will return the free
 * space that contains the given offset, which means we can return a free space
 * chunk with an offset before the provided offset.
 *
 * fuzzy == 0: this is just a normal tree search.  Give us the free space that
 * starts at the given offset which is at least bytes size, and if its not there
 * return NULL.
 */
static struct btrfs_free_space *tree_search_offset(struct rb_root *root,
                                                   u64 offset, u64 bytes,
                                                   int fuzzy)
{
        struct rb_node *n = root->rb_node;
        struct btrfs_free_space *entry, *ret = NULL;

        while (n) {
                entry = rb_entry(n, struct btrfs_free_space, offset_index);

                if (offset < entry->offset) {
                        if (fuzzy &&
                            (!ret || entry->offset < ret->offset) &&
                            (bytes <= entry->bytes))
                                ret = entry;
                        n = n->rb_left;
                } else if (offset > entry->offset) {
                        if (fuzzy &&
                            (entry->offset + entry->bytes - 1) >= offset &&
                            bytes <= entry->bytes) {
                                ret = entry;
                                break;
                        }
                        n = n->rb_right;
                } else {
                        if (bytes > entry->bytes) {
                                n = n->rb_right;
                                continue;
                        }
                        ret = entry;
                        break;
                }
        }

        return ret;
}

/*
 * return a chunk at least bytes size, as close to offset that we can get.
 */
static struct btrfs_free_space *tree_search_bytes(struct rb_root *root,
                                                  u64 offset, u64 bytes)
{
        struct rb_node *n = root->rb_node;
        struct btrfs_free_space *entry, *ret = NULL;

        while (n) {
                entry = rb_entry(n, struct btrfs_free_space, bytes_index);

                if (bytes < entry->bytes) {
                        /*
                         * We prefer to get a hole size as close to the size we
                         * are asking for so we don't take small slivers out of
                         * huge holes, but we also want to get as close to the
                         * offset as possible so we don't have a whole lot of
                         * fragmentation.
                         */
                        if (offset <= entry->offset) {
                                if (!ret)
                                        ret = entry;
                                else if (entry->bytes < ret->bytes)
                                        ret = entry;
                                else if (entry->offset < ret->offset)
                                        ret = entry;
                        }
                        n = n->rb_left;
                } else if (bytes > entry->bytes) {
                        n = n->rb_right;
                } else {
                        /*
                         * Ok we may have multiple chunks of the wanted size,
                         * so we don't want to take the first one we find, we
                         * want to take the one closest to our given offset, so
                         * keep searching just in case theres a better match.
                         */
                        n = n->rb_right;
                        if (offset > entry->offset)
                                continue;
                        else if (!ret || entry->offset < ret->offset)
                                ret = entry;
                }
        }

        return ret;
}

static void unlink_free_space(struct btrfs_block_group_cache *block_group,
                              struct btrfs_free_space *info)
{
        rb_erase(&info->offset_index, &block_group->free_space_offset);
        rb_erase(&info->bytes_index, &block_group->free_space_bytes);
}

static int link_free_space(struct btrfs_block_group_cache *block_group,
                           struct btrfs_free_space *info)
{
        int ret = 0;


        BUG_ON(!info->bytes);
        ret = tree_insert_offset(&block_group->free_space_offset, info->offset,
                                 &info->offset_index);
        if (ret)
                return ret;

        ret = tree_insert_bytes(&block_group->free_space_bytes, info->bytes,
                                &info->bytes_index);
        if (ret)
                return ret;

        return ret;
}

int btrfs_add_free_space(struct btrfs_block_group_cache *block_group,
                         u64 offset, u64 bytes)
{
        struct btrfs_free_space *right_info;
        struct btrfs_free_space *left_info;
        struct btrfs_free_space *info = NULL;
        int ret = 0;

        info = kzalloc(sizeof(struct btrfs_free_space), GFP_NOFS);
        if (!info)
                return -ENOMEM;

        info->offset = offset;
        info->bytes = bytes;

        spin_lock(&block_group->tree_lock);

        /*
         * first we want to see if there is free space adjacent to the range we
         * are adding, if there is remove that struct and add a new one to
         * cover the entire range
         */
        right_info = tree_search_offset(&block_group->free_space_offset,
                                        offset+bytes, 0, 0);
        left_info = tree_search_offset(&block_group->free_space_offset,
                                       offset-1, 0, 1);

        if (right_info) {
                unlink_free_space(block_group, right_info);
                info->bytes += right_info->bytes;
                kfree(right_info);
        }

        if (left_info && left_info->offset + left_info->bytes == offset) {
                unlink_free_space(block_group, left_info);
                info->offset = left_info->offset;
                info->bytes += left_info->bytes;
                kfree(left_info);
        }

        ret = link_free_space(block_group, info);
        if (ret)
                kfree(info);

        spin_unlock(&block_group->tree_lock);

        if (ret) {
                printk(KERN_ERR "btrfs: unable to add free space :%d\n", ret);
                if (ret == -EEXIST)
                        BUG();
        }

        return ret;
}

int btrfs_remove_free_space(struct btrfs_block_group_cache *block_group,
                            u64 offset, u64 bytes)
{
        struct btrfs_free_space *info;
        int ret = 0;

        spin_lock(&block_group->tree_lock);

        info = tree_search_offset(&block_group->free_space_offset, offset, 0,
                                  1);
        if (info && info->offset == offset) {
                if (info->bytes < bytes) {
                        printk(KERN_ERR "Found free space at %llu, size %llu,"
                               "trying to use %llu\n",
                               (unsigned long long)info->offset,
                               (unsigned long long)info->bytes,
                               (unsigned long long)bytes);
                        WARN_ON(1);
                        ret = -EINVAL;
                        spin_unlock(&block_group->tree_lock);
                        goto out;
                }
                unlink_free_space(block_group, info);

                if (info->bytes == bytes) {
                        kfree(info);
                        spin_unlock(&block_group->tree_lock);
                        goto out;
                }

                info->offset += bytes;
                info->bytes -= bytes;

                ret = link_free_space(block_group, info);
                spin_unlock(&block_group->tree_lock);
                BUG_ON(ret);
        } else if (info && info->offset < offset &&
                   info->offset + info->bytes >= offset + bytes) {
                u64 old_start = info->offset;
                /*
                 * we're freeing space in the middle of the info,
                 * this can happen during tree log replay
                 *
                 * first unlink the old info and then
                 * insert it again after the hole we're creating
                 */
                unlink_free_space(block_group, info);
                if (offset + bytes < info->offset + info->bytes) {
                        u64 old_end = info->offset + info->bytes;

                        info->offset = offset + bytes;
                        info->bytes = old_end - info->offset;
                        ret = link_free_space(block_group, info);
                        BUG_ON(ret);
                } else {
                        /* the hole we're creating ends at the end
                         * of the info struct, just free the info
                         */
                        kfree(info);
                }
                spin_unlock(&block_group->tree_lock);
                /* step two, insert a new info struct to cover anything
                 * before the hole
                 */
                ret = btrfs_add_free_space(block_group, old_start,
                                           offset - old_start);
                BUG_ON(ret);
        } else {
                spin_unlock(&block_group->tree_lock);
                if (!info) {
                        printk(KERN_ERR "couldn't find space %llu to free\n",
                               (unsigned long long)offset);
                        printk(KERN_ERR "cached is %d, offset %llu bytes %llu\n",
                               block_group->cached, block_group->key.objectid,
                               block_group->key.offset);
                        btrfs_dump_free_space(block_group, bytes);
                } else if (info) {
                        printk(KERN_ERR "hmm, found offset=%llu bytes=%llu, "
                               "but wanted offset=%llu bytes=%llu\n",
                               info->offset, info->bytes, offset, bytes);
                }
                WARN_ON(1);
        }
out:
        return ret;
}

void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
                           u64 bytes)
{
        struct btrfs_free_space *info;
        struct rb_node *n;
        int count = 0;

        for (n = rb_first(&block_group->free_space_offset); n; n = rb_next(n)) {
                info = rb_entry(n, struct btrfs_free_space, offset_index);
                if (info->bytes >= bytes)
                        count++;
                printk(KERN_ERR "entry offset %llu, bytes %llu\n", info->offset,
                       info->bytes);
        }
        printk(KERN_INFO "%d blocks of free space at or bigger than bytes is"
               "\n", count);
}

u64 btrfs_block_group_free_space(struct btrfs_block_group_cache *block_group)
{
        struct btrfs_free_space *info;
        struct rb_node *n;
        u64 ret = 0;

        for (n = rb_first(&block_group->free_space_offset); n;
             n = rb_next(n)) {
                info = rb_entry(n, struct btrfs_free_space, offset_index);
                ret += info->bytes;
        }

        return ret;
}

/*
 * for a given cluster, put all of its extents back into the free
 * space cache.  If the block group passed doesn't match the block group
 * pointed to by the cluster, someone else raced in and freed the
 * cluster already.  In that case, we just return without changing anything
 */
static int
__btrfs_return_cluster_to_free_space(
                             struct btrfs_block_group_cache *block_group,
                             struct btrfs_free_cluster *cluster)
{
        struct btrfs_free_space *entry;
        struct rb_node *node;

        spin_lock(&cluster->lock);
        if (cluster->block_group != block_group)
                goto out;

        cluster->window_start = 0;
        node = rb_first(&cluster->root);
        while(node) {
                entry = rb_entry(node, struct btrfs_free_space, offset_index);
                node = rb_next(&entry->offset_index);
                rb_erase(&entry->offset_index, &cluster->root);
                link_free_space(block_group, entry);
        }
        list_del_init(&cluster->block_group_list);

        btrfs_put_block_group(cluster->block_group);
        cluster->block_group = NULL;
        cluster->root.rb_node = NULL;
out:
        spin_unlock(&cluster->lock);
        return 0;
}

void btrfs_remove_free_space_cache(struct btrfs_block_group_cache *block_group)
{
        struct btrfs_free_space *info;
        struct rb_node *node;
        struct btrfs_free_cluster *cluster;
        struct btrfs_free_cluster *safe;

        spin_lock(&block_group->tree_lock);

        list_for_each_entry_safe(cluster, safe, &block_group->cluster_list,
                                 block_group_list) {

                WARN_ON(cluster->block_group != block_group);
                __btrfs_return_cluster_to_free_space(block_group, cluster);
        }

        while ((node = rb_last(&block_group->free_space_bytes)) != NULL) {
                info = rb_entry(node, struct btrfs_free_space, bytes_index);
                unlink_free_space(block_group, info);
                kfree(info);
                if (need_resched()) {
                        spin_unlock(&block_group->tree_lock);
                        cond_resched();
                        spin_lock(&block_group->tree_lock);
                }
        }
        spin_unlock(&block_group->tree_lock);
}

u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group,
                               u64 offset, u64 bytes, u64 empty_size)
{
        struct btrfs_free_space *entry = NULL;
        u64 ret = 0;

        spin_lock(&block_group->tree_lock);
        entry = tree_search_offset(&block_group->free_space_offset, offset,
                                   bytes + empty_size, 1);
        if (!entry)
                entry = tree_search_bytes(&block_group->free_space_bytes,
                                          offset, bytes + empty_size);
        if (entry) {
                unlink_free_space(block_group, entry);
                ret = entry->offset;
                entry->offset += bytes;
                entry->bytes -= bytes;

                if (!entry->bytes)
                        kfree(entry);
                else
                        link_free_space(block_group, entry);
        }
        spin_unlock(&block_group->tree_lock);

        return ret;
}

/*
 * given a cluster, put all of its extents back into the free space
 * cache.  If a block group is passed, this function will only free
 * a cluster that belongs to the passed block group.
 *
 * Otherwise, it'll get a reference on the block group pointed to by the
 * cluster and remove the cluster from it.
 */
int btrfs_return_cluster_to_free_space(
                               struct btrfs_block_group_cache *block_group,
                               struct btrfs_free_cluster *cluster)
{
        int ret;

        /* first, get a safe pointer to the block group */
        spin_lock(&cluster->lock);
        if (!block_group) {
                block_group = cluster->block_group;
                if (!block_group) {
                        spin_unlock(&cluster->lock);
                        return 0;
                }
        } else if (cluster->block_group != block_group) {
                /* someone else has already freed it don't redo their work */
                spin_unlock(&cluster->lock);
                return 0;
        }
        atomic_inc(&block_group->count);
        spin_unlock(&cluster->lock);

        /* now return any extents the cluster had on it */
        spin_lock(&block_group->tree_lock);
        ret = __btrfs_return_cluster_to_free_space(block_group, cluster);
        spin_unlock(&block_group->tree_lock);

        /* finally drop our ref */
        btrfs_put_block_group(block_group);
        return ret;
}

/*
 * given a cluster, try to allocate 'bytes' from it, returns 0
 * if it couldn't find anything suitably large, or a logical disk offset
 * if things worked out
 */
u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group,
                             struct btrfs_free_cluster *cluster, u64 bytes,
                             u64 min_start)
{
        struct btrfs_free_space *entry = NULL;
        struct rb_node *node;
        u64 ret = 0;

        spin_lock(&cluster->lock);
        if (bytes > cluster->max_size)
                goto out;

        if (cluster->block_group != block_group)
                goto out;

        node = rb_first(&cluster->root);
        if (!node)
                goto out;

        entry = rb_entry(node, struct btrfs_free_space, offset_index);

        while(1) {
                if (entry->bytes < bytes || entry->offset < min_start) {
                        struct rb_node *node;

                        node = rb_next(&entry->offset_index);
                        if (!node)
                                break;
                        entry = rb_entry(node, struct btrfs_free_space,
                                         offset_index);
                        continue;
                }
                ret = entry->offset;

                entry->offset += bytes;
                entry->bytes -= bytes;

                if (entry->bytes == 0) {
                        rb_erase(&entry->offset_index, &cluster->root);
                        kfree(entry);
                }
                break;
        }
out:
        spin_unlock(&cluster->lock);
        return ret;
}

/*
 * here we try to find a cluster of blocks in a block group.  The goal
 * is to find at least bytes free and up to empty_size + bytes free.
 * We might not find them all in one contiguous area.
 *
 * returns zero and sets up cluster if things worked out, otherwise
 * it returns -enospc
 */
int btrfs_find_space_cluster(struct btrfs_trans_handle *trans,
                             struct btrfs_block_group_cache *block_group,
                             struct btrfs_free_cluster *cluster,
                             u64 offset, u64 bytes, u64 empty_size)
{
        struct btrfs_free_space *entry = NULL;
        struct rb_node *node;
        struct btrfs_free_space *next;
        struct btrfs_free_space *last;
        u64 min_bytes;
        u64 window_start;
        u64 window_free;
        u64 max_extent = 0;
        int total_retries = 0;
        int ret;

        /* for metadata, allow allocates with more holes */
        if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
                /*
                 * we want to do larger allocations when we are
                 * flushing out the delayed refs, it helps prevent
                 * making more work as we go along.
                 */
                if (trans->transaction->delayed_refs.flushing)
                        min_bytes = max(bytes, (bytes + empty_size) >> 1);
                else
                        min_bytes = max(bytes, (bytes + empty_size) >> 4);
        } else
                min_bytes = max(bytes, (bytes + empty_size) >> 2);

        spin_lock(&block_group->tree_lock);
        spin_lock(&cluster->lock);

        /* someone already found a cluster, hooray */
        if (cluster->block_group) {
                ret = 0;
                goto out;
        }
again:
        min_bytes = min(min_bytes, bytes + empty_size);
        entry = tree_search_bytes(&block_group->free_space_bytes,
                                  offset, min_bytes);
        if (!entry) {
                ret = -ENOSPC;
                goto out;
        }
        window_start = entry->offset;
        window_free = entry->bytes;
        last = entry;
        max_extent = entry->bytes;

        while(1) {
                /* out window is just right, lets fill it */
                if (window_free >= bytes + empty_size)
                        break;

                node = rb_next(&last->offset_index);
                if (!node) {
                        ret = -ENOSPC;
                        goto out;
                }
                next = rb_entry(node, struct btrfs_free_space, offset_index);

                /*
                 * we haven't filled the empty size and the window is
                 * very large.  reset and try again
                 */
                if (next->offset - window_start > (bytes + empty_size) * 2) {
                        entry = next;
                        window_start = entry->offset;
                        window_free = entry->bytes;
                        last = entry;
                        max_extent = 0;
                        total_retries++;
                        if (total_retries % 256 == 0) {
                                if (min_bytes >= (bytes + empty_size)) {
                                        ret = -ENOSPC;
                                        goto out;
                                }
                                /*
                                 * grow our allocation a bit, we're not having
                                 * much luck
                                 */
                                min_bytes *= 2;
                                goto again;
                        }
                } else {
                        last = next;
                        window_free += next->bytes;
                        if (entry->bytes > max_extent)
                                max_extent = entry->bytes;
                }
        }

        cluster->window_start = entry->offset;

        /*
         * now we've found our entries, pull them out of the free space
         * cache and put them into the cluster rbtree
         *
         * The cluster includes an rbtree, but only uses the offset index
         * of each free space cache entry.
         */
        while(1) {
                node = rb_next(&entry->offset_index);
                unlink_free_space(block_group, entry);
                ret = tree_insert_offset(&cluster->root, entry->offset,
                                         &entry->offset_index);
                BUG_ON(ret);

                if (!node || entry == last)
                        break;

                entry = rb_entry(node, struct btrfs_free_space, offset_index);
        }
        ret = 0;
        cluster->max_size = max_extent;
        atomic_inc(&block_group->count);
        list_add_tail(&cluster->block_group_list, &block_group->cluster_list);
        cluster->block_group = block_group;
out:
        spin_unlock(&cluster->lock);
        spin_unlock(&block_group->tree_lock);

        return ret;
}

/*
 * simple code to zero out a cluster
 */
void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
{
        spin_lock_init(&cluster->lock);
        spin_lock_init(&cluster->refill_lock);
        cluster->root.rb_node = NULL;
        cluster->max_size = 0;
        INIT_LIST_HEAD(&cluster->block_group_list);
        cluster->block_group = NULL;
}