path: root/fs/ocfs2/extent_map.c

/* -*- mode: c; c-basic-offset: 8; -*-
 * vim: noexpandtab sw=8 ts=8 sts=0:
 *
 * extent_map.c
 *
 * In-memory extent map for OCFS2.  Man, this code was prettier in
 * the library.
 *
 * Copyright (C) 2004 Oracle.  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, version 2,  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/fs.h>
#include <linux/init.h>
#include <linux/types.h>
#include <linux/slab.h>
#include <linux/rbtree.h>

#define MLOG_MASK_PREFIX ML_EXTENT_MAP
#include <cluster/masklog.h>

#include "ocfs2.h"

#include "extent_map.h"
#include "inode.h"
#include "super.h"

#include "buffer_head_io.h"


/*
 * SUCK SUCK SUCK
 * Our headers are so bad that struct ocfs2_extent_map is in ocfs.h
 */

struct ocfs2_extent_map_entry {
	struct rb_node e_node;
	int e_tree_depth;
	struct ocfs2_extent_rec e_rec;
};

struct ocfs2_em_insert_context {
	int need_left;
	int need_right;
	struct ocfs2_extent_map_entry *new_ent;
	struct ocfs2_extent_map_entry *old_ent;
	struct ocfs2_extent_map_entry *left_ent;
	struct ocfs2_extent_map_entry *right_ent;
};

static kmem_cache_t *ocfs2_em_ent_cachep = NULL;


static struct ocfs2_extent_map_entry *
ocfs2_extent_map_lookup(struct ocfs2_extent_map *em,
			u32 cpos, u32 clusters,
			struct rb_node ***ret_p,
			struct rb_node **ret_parent);
static int ocfs2_extent_map_insert(struct inode *inode,
				   struct ocfs2_extent_rec *rec,
				   int tree_depth);
static int ocfs2_extent_map_insert_entry(struct ocfs2_extent_map *em,
					 struct ocfs2_extent_map_entry *ent);
static int ocfs2_extent_map_find_leaf(struct inode *inode,
				      u32 cpos, u32 clusters,
				      struct ocfs2_extent_list *el);
static int ocfs2_extent_map_lookup_read(struct inode *inode,
					u32 cpos, u32 clusters,
					struct ocfs2_extent_map_entry **ret_ent);
static int ocfs2_extent_map_try_insert(struct inode *inode,
				       struct ocfs2_extent_rec *rec,
				       int tree_depth,
				       struct ocfs2_em_insert_context *ctxt);

/* returns 1 only if the rec contains all the given clusters -- that is that
 * rec's cpos is <= the cluster cpos and that the rec endpoint (cpos +
 * clusters) is >= the argument's endpoint */
static int ocfs2_extent_rec_contains_clusters(struct ocfs2_extent_rec *rec,
					      u32 cpos, u32 clusters)
{
	if (le32_to_cpu(rec->e_cpos) > cpos)
		return 0;
	if (cpos + clusters > le32_to_cpu(rec->e_cpos) + 
			      le32_to_cpu(rec->e_clusters))
		return 0;
	return 1;
}


/*
 * Find an entry in the tree that intersects the region passed in.
 * Note that this will find straddled intervals, it is up to the
 * callers to enforce any boundary conditions.
 *
 * Callers must hold ip_lock.  This lookup is not guaranteed to return
 * a tree_depth 0 match, and as such can race inserts if the lock
 * were not held.
 *
 * The rb_node garbage lets insertion share the search.  Trivial
 * callers pass NULL.
 */
static struct ocfs2_extent_map_entry *
ocfs2_extent_map_lookup(struct ocfs2_extent_map *em,
			u32 cpos, u32 clusters,
			struct rb_node ***ret_p,
			struct rb_node **ret_parent)
{
	struct rb_node **p = &em->em_extents.rb_node;
	struct rb_node *parent = NULL;
	struct ocfs2_extent_map_entry *ent = NULL;

	while (*p)
	{
		parent = *p;
		ent = rb_entry(parent, struct ocfs2_extent_map_entry,
			       e_node);
		if ((cpos + clusters) <= le32_to_cpu(ent->e_rec.e_cpos)) {
			p = &(*p)->rb_left;
			ent = NULL;
		} else if (cpos >= (le32_to_cpu(ent->e_rec.e_cpos) +
				    le32_to_cpu(ent->e_rec.e_clusters))) {
			p = &(*p)->rb_right;
			ent = NULL;
		} else
			break;
	}

	if (ret_p != NULL)
		*ret_p = p;
	if (ret_parent != NULL)
		*ret_parent = parent;
	return ent;
}

/*
 * Find the leaf containing the interval we want.  While we're on our
 * way down the tree, fill in every record we see at any depth, because
 * we might want it later.
 *
 * Note that this code is run without ip_lock.  That's because it
 * sleeps while reading.  If someone is also filling the extent list at
 * the same time we are, we might have to restart.
 */
static int ocfs2_extent_map_find_leaf(struct inode *inode,
				      u32 cpos, u32 clusters,
				      struct ocfs2_extent_list *el)
{
	int i, ret;
	struct buffer_head