fs/nfs/blocklayout/extent_tree.c - kernel/msm-4.9 - Gitiles

 /*
  * Copyright (c) 2014 Christoph Hellwig.
  */

 #include <linux/vmalloc.h>

 #include "blocklayout.h"

 #define NFSDBG_FACILITY		NFSDBG_PNFS_LD

 static inline struct pnfs_block_extent *
 ext_node(struct rb_node *node)
 {
 	return rb_entry(node, struct pnfs_block_extent, be_node);
 }

 static struct pnfs_block_extent *
 ext_tree_first(struct rb_root *root)
 {
 	struct rb_node *node = rb_first(root);
 	return node ? ext_node(node) : NULL;
 }

 static struct pnfs_block_extent *
 ext_tree_prev(struct pnfs_block_extent *be)
 {
 	struct rb_node *node = rb_prev(&be->be_node);
 	return node ? ext_node(node) : NULL;
 }

 static struct pnfs_block_extent *
 ext_tree_next(struct pnfs_block_extent *be)
 {
 	struct rb_node *node = rb_next(&be->be_node);
 	return node ? ext_node(node) : NULL;
 }

 static inline sector_t
 ext_f_end(struct pnfs_block_extent *be)
 {
 	return be->be_f_offset + be->be_length;
 }

 static struct pnfs_block_extent *
 __ext_tree_search(struct rb_root *root, sector_t start)
 {
 	struct rb_node *node = root->rb_node;
 	struct pnfs_block_extent *be = NULL;

 	while (node) {
 		be = ext_node(node);
 		if (start < be->be_f_offset)
 			node = node->rb_left;
 		else if (start >= ext_f_end(be))
 			node = node->rb_right;
 		else
 			return be;
 	}

 	if (be) {
 		if (start < be->be_f_offset)
 			return be;

 		if (start >= ext_f_end(be))
 			return ext_tree_next(be);
 	}

 	return NULL;
 }

 static bool
 ext_can_merge(struct pnfs_block_extent *be1, struct pnfs_block_extent *be2)
 {
 	if (be1->be_state != be2->be_state)
 		return false;
 	if (be1->be_device != be2->be_device)
 		return false;

 	if (be1->be_f_offset + be1->be_length != be2->be_f_offset)
 		return false;

 	if (be1->be_state != PNFS_BLOCK_NONE_DATA &&
 	    (be1->be_v_offset + be1->be_length != be2->be_v_offset))
 		return false;

 	if (be1->be_state == PNFS_BLOCK_INVALID_DATA &&
 	    be1->be_tag != be2->be_tag)
 		return false;

 	return true;
 }

 static struct pnfs_block_extent *
 ext_try_to_merge_left(struct rb_root *root, struct pnfs_block_extent *be)
 {
 	struct pnfs_block_extent *left = ext_tree_prev(be);

 	if (left && ext_can_merge(left, be)) {
 		left->be_length += be->be_length;
 		rb_erase(&be->be_node, root);
 		nfs4_put_deviceid_node(be->be_device);
 		kfree(be);
 		return left;
 	}

 	return be;
 }

 static struct pnfs_block_extent *
 ext_try_to_merge_right(struct rb_root *root, struct pnfs_block_extent *be)
 {
 	struct pnfs_block_extent *right = ext_tree_next(be);

 	if (right && ext_can_merge(be, right)) {
 		be->be_length += right->be_length;
 		rb_erase(&right->be_node, root);
 		nfs4_put_deviceid_node(right->be_device);
 		kfree(right);
 	}

 	return be;
 }

 static void
 __ext_tree_insert(struct rb_root *root,
 		struct pnfs_block_extent *new, bool merge_ok)
 {
 	struct rb_node **p = &root->rb_node, *parent = NULL;
 	struct pnfs_block_extent *be;

 	while (*p) {
 		parent = *p;
 		be = ext_node(parent);

 		if (new->be_f_offset < be->be_f_offset) {
 			if (merge_ok && ext_can_merge(new, be)) {
 				be->be_f_offset = new->be_f_offset;
 				if (be->be_state != PNFS_BLOCK_NONE_DATA)
 					be->be_v_offset = new->be_v_offset;
 				be->be_length += new->be_length;
 				be = ext_try_to_merge_left(root, be);
 				goto free_new;
 			}
 			p = &(*p)->rb_left;
 		} else if (new->be_f_offset >= ext_f_end(be)) {
 			if (merge_ok && ext_can_merge(be, new)) {
 				be->be_length += new->be_length;
 				be = ext_try_to_merge_right(root, be);
 				goto free_new;
 			}
 			p = &(*p)->rb_right;
 		} else {
 			BUG();
 		}
 	}

 	rb_link_node(&new->be_node, parent, p);
 	rb_insert_color(&new->be_node, root);
 	return;
 free_new:
 	nfs4_put_deviceid_node(new->be_device);
 	kfree(new);
 }

 static int
 __ext_tree_remove(struct rb_root *root, sector_t start, sector_t end)
 {
 	struct pnfs_block_extent *be;
 	sector_t len1 = 0, len2 = 0;
 	sector_t orig_v_offset;
 	sector_t orig_len;

 	be = __ext_tree_search(root, start);
 	if (!be)
 		return 0;
 	if (be->be_f_offset >= end)
 		return 0;

 	orig_v_offset = be->be_v_offset;
 	orig_len = be->be_length;

 	if (start > be->be_f_offset)
 		len1 = start - be->be_f_offset;
 	if (ext_f_end(be) > end)
 		len2 = ext_f_end(be) - end;

 	if (len2 > 0) {
 		if (len1 > 0) {
 			struct pnfs_block_extent *new;

 			new = kzalloc(sizeof(*new), GFP_ATOMIC);
 			if (!new)
 				return -ENOMEM;

 			be->be_length = len1;

 			new->be_f_offset = end;
 			if (be->be_state != PNFS_BLOCK_NONE_DATA) {
 				new->be_v_offset =
 					orig_v_offset + orig_len - len2;
 			}
 			new->be_length = len2;
 			new->be_state = be->be_state;
 			new->be_tag = be->be_tag;
 			new->be_device = nfs4_get_deviceid(be->be_device);

 			__ext_tree_insert(root, new, true);
 		} else {
 			be->be_f_offset = end;
 			if (be->be_state != PNFS_BLOCK_NONE_DATA) {
 				be->be_v_offset =
 					orig_v_offset + orig_len - len2;
 			}
 			be->be_length = len2;
 		}
 	} else {
 		if (len1 > 0) {
 			be->be_length = len1;
 			be = ext_tree_next(be);
 		}

 		while (be && ext_f_end(be) <= end) {
 			struct pnfs_block_extent *next = ext_tree_next(be);

 			rb_erase(&be->be_node, root);
 			nfs4_put_deviceid_node(be->be_device);
 			kfree(be);
 			be = next;
 		}

 		if (be && be->be_f_offset < end) {
 			len1 = ext_f_end(be) - end;
 			be->be_f_offset = end;
 			if (be->be_state != PNFS_BLOCK_NONE_DATA)
 				be->be_v_offset += be->be_length - len1;
 			be->be_length = len1;
 		}
 	}

 	return 0;
 }

 int
 ext_tree_insert(struct pnfs_block_layout *bl, struct pnfs_block_extent *new)
 {
 	struct pnfs_block_extent *be;
 	struct rb_root *root;
 	int err = 0;

 	switch (new->be_state) {
 	case PNFS_BLOCK_READWRITE_DATA:
 	case PNFS_BLOCK_INVALID_DATA:
 		root = &bl->bl_ext_rw;
 		break;
 	case PNFS_BLOCK_READ_DATA:
 	case PNFS_BLOCK_NONE_DATA:
 		root = &bl->bl_ext_ro;
 		break;
 	default:
 		dprintk("invalid extent type\n");
 		return -EINVAL;
 	}

 	spin_lock(&bl->bl_ext_lock);
 retry:
 	be = __ext_tree_search(root, new->be_f_offset);
 	if (!be || be->be_f_offset >= ext_f_end(new)) {
 		__ext_tree_insert(root, new, true);
 	} else if (new->be_f_offset >= be->be_f_offset) {
 		if (ext_f_end(new) <= ext_f_end(be)) {
 			nfs4_put_deviceid_node(new->be_device);
 			kfree(new);
 		} else {
 			sector_t new_len = ext_f_end(new) - ext_f_end(be);
 			sector_t diff = new->be_length - new_len;

 			new->be_f_offset += diff;
 			new->be_v_offset += diff;
 			new->be_length = new_len;
 			goto retry;
 		}
 	} else if (ext_f_end(new) <= ext_f_end(be)) {
 		new->be_length = be->be_f_offset - new->be_f_offset;
 		__ext_tree_insert(root, new, true);
 	} else {
 		struct pnfs_block_extent *split;
 		sector_t new_len = ext_f_end(new) - ext_f_end(be);
 		sector_t diff = new->be_length - new_len;

 		split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
 		if (!split) {
 			err = -EINVAL;
 			goto out;
 		}

 		split->be_length = be->be_f_offset - split->be_f_offset;
 		split->be_device = nfs4_get_deviceid(new->be_device);
 		__ext_tree_insert(root, split, true);

 		new->be_f_offset += diff;
 		new->be_v_offset += diff;
 		new->be_length = new_len;
 		goto retry;
 	}
 out:
 	spin_unlock(&bl->bl_ext_lock);
 	return err;
 }

 static bool
 __ext_tree_lookup(struct rb_root *root, sector_t isect,
 		struct pnfs_block_extent *ret)
 {
 	struct rb_node *node;
 	struct pnfs_block_extent *be;

 	node = root->rb_node;
 	while (node) {
 		be = ext_node(node);
 		if (isect < be->be_f_offset)
 			node = node->rb_left;
 		else if (isect >= ext_f_end(be))
 			node = node->rb_right;
 		else {
 			*ret = *be;
 			return true;
 		}
 	}

 	return false;
 }

 bool
 ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
 	    struct pnfs_block_extent *ret, bool rw)
 {
 	bool found = false;

 	spin_lock(&bl->bl_ext_lock);
 	if (!rw)
 		found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
 	if (!found)
 		found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
 	spin_unlock(&bl->bl_ext_lock);

 	return found;
 }

 int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
 		sector_t start, sector_t end)
 {
 	int err, err2;

 	spin_lock(&bl->bl_ext_lock);
 	err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
 	if (rw) {
 		err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end);
 		if (!err)
 			err = err2;
 	}
 	spin_unlock(&bl->bl_ext_lock);

 	return err;
 }

 static int
 ext_tree_split(struct rb_root *root, struct pnfs_block_extent *be,
 		sector_t split)
 {
 	struct pnfs_block_extent *new;
 	sector_t orig_len = be->be_length;

 	new = kzalloc(sizeof(*new), GFP_ATOMIC);
 	if (!new)
 		return -ENOMEM;

 	be->be_length = split - be->be_f_offset;

 	new->be_f_offset = split;
 	if (be->be_state != PNFS_BLOCK_NONE_DATA)
 		new->be_v_offset = be->be_v_offset + be->be_length;
 	new->be_length = orig_len - be->be_length;
 	new->be_state = be->be_state;
 	new->be_tag = be->be_tag;
 	new->be_device = nfs4_get_deviceid(be->be_device);

 	__ext_tree_insert(root, new, false);
 	return 0;
 }

 int
 ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
 		sector_t len)
 {
 	struct rb_root *root = &bl->bl_ext_rw;
 	sector_t end = start + len;
 	struct pnfs_block_extent *be;
 	int err = 0;

 	spin_lock(&bl->bl_ext_lock);
 	/*
 	 * First remove all COW extents or holes from written to range.
 	 */
 	err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
 	if (err)
 		goto out;

 	/*
 	 * Then mark all invalid extents in the range as written to.
 	 */
 	for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
 		if (be->be_f_offset >= end)
 			break;

 		if (be->be_state != PNFS_BLOCK_INVALID_DATA || be->be_tag)
 			continue;

 		if (be->be_f_offset < start) {
 			struct pnfs_block_extent *left = ext_tree_prev(be);

 			if (left && ext_can_merge(left, be)) {
 				sector_t diff = start - be->be_f_offset;

 				left->be_length += diff;

 				be->be_f_offset += diff;
 				be->be_v_offset += diff;
 				be->be_length -= diff;
 			} else {
 				err = ext_tree_split(root, be, start);
 				if (err)
 					goto out;
 			}
 		}

 		if (ext_f_end(be) > end) {
 			struct pnfs_block_extent *right = ext_tree_next(be);

 			if (right && ext_can_merge(be, right)) {
 				sector_t diff = end - be->be_f_offset;

 				be->be_length -= diff;

 				right->be_f_offset -= diff;
 				right->be_v_offset -= diff;
 				right->be_length += diff;
 			} else {
 				err = ext_tree_split(root, be, end);
 				if (err)
 					goto out;
 			}
 		}

 		if (be->be_f_offset >= start && ext_f_end(be) <= end) {
 			be->be_tag = EXTENT_WRITTEN;
 			be = ext_try_to_merge_left(root, be);
 			be = ext_try_to_merge_right(root, be);
 		}
 	}
 out:
 	spin_unlock(&bl->bl_ext_lock);
 	return err;
 }

 static void ext_tree_free_commitdata(struct nfs4_layoutcommit_args *arg,
 		size_t buffer_size)
 {
 	if (arg->layoutupdate_pages != &arg->layoutupdate_page) {
 		int nr_pages = DIV_ROUND_UP(buffer_size, PAGE_SIZE), i;

 		for (i = 0; i < nr_pages; i++)
 			put_page(arg->layoutupdate_pages[i]);
 		kfree(arg->layoutupdate_pages);
 	} else {
 		put_page(arg->layoutupdate_page);
 	}
 }

 static int ext_tree_encode_commit(struct pnfs_block_layout *bl, __be32 *p,
 		size_t buffer_size, size_t *count)
 {
 	struct pnfs_block_extent *be;
 	int ret = 0;

 	spin_lock(&bl->bl_ext_lock);
 	for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
 		if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
 		    be->be_tag != EXTENT_WRITTEN)
 			continue;

 		(*count)++;
 		if (*count * BL_EXTENT_SIZE > buffer_size) {
 			/* keep counting.. */
 			ret = -ENOSPC;
 			continue;
 		}

 		p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
 				NFS4_DEVICEID4_SIZE);
 		p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
 		p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
 		p = xdr_encode_hyper(p, 0LL);
 		*p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);

 		be->be_tag = EXTENT_COMMITTING;
 	}
 	spin_unlock(&bl->bl_ext_lock);

 	return ret;
 }

 int
 ext_tree_prepare_commit(struct nfs4_layoutcommit_args *arg)
 {
 	struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
 	size_t count = 0, buffer_size = PAGE_SIZE;
 	__be32 *start_p;
 	int ret;

 	dprintk("%s enter\n", __func__);

 	arg->layoutupdate_page = alloc_page(GFP_NOFS);
 	if (!arg->layoutupdate_page)
 		return -ENOMEM;
 	start_p = page_address(arg->layoutupdate_page);
 	arg->layoutupdate_pages = &arg->layoutupdate_page;

 retry:
 	ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count);
 	if (unlikely(ret)) {
 		ext_tree_free_commitdata(arg, buffer_size);

 		buffer_size = sizeof(__be32) + BL_EXTENT_SIZE * count;
 		count = 0;

 		arg->layoutupdate_pages =
 			kcalloc(DIV_ROUND_UP(buffer_size, PAGE_SIZE),
 				sizeof(struct page *), GFP_NOFS);
 		if (!arg->layoutupdate_pages)
 			return -ENOMEM;

 		start_p = __vmalloc(buffer_size, GFP_NOFS, PAGE_KERNEL);
 		if (!start_p) {
 			kfree(arg->layoutupdate_pages);
 			return -ENOMEM;
 		}

 		goto retry;
 	}

 	*start_p = cpu_to_be32(count);
 	arg->layoutupdate_len = sizeof(__be32) + BL_EXTENT_SIZE * count;

 	if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) {
 		__be32 *p = start_p;
 		int i = 0;

 		for (p = start_p;
 		     p < start_p + arg->layoutupdate_len;
 		     p += PAGE_SIZE) {
 			arg->layoutupdate_pages[i++] = vmalloc_to_page(p);
 		}
 	}

 	dprintk("%s found %zu ranges\n", __func__, count);
 	return 0;
 }

 void
 ext_tree_mark_committed(struct nfs4_layoutcommit_args *arg, int status)
 {
 	struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
 	struct rb_root *root = &bl->bl_ext_rw;
 	struct pnfs_block_extent *be;

 	dprintk("%s status %d\n", __func__, status);

 	ext_tree_free_commitdata(arg, arg->layoutupdate_len);

 	spin_lock(&bl->bl_ext_lock);
 	for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
 		if (be->be_state != PNFS_BLOCK_INVALID_DATA ||
 		    be->be_tag != EXTENT_COMMITTING)
 			continue;

 		if (status) {
 			/*
 			 * Mark as written and try again.
 			 *
 			 * XXX: some real error handling here wouldn't hurt..
 			 */
 			be->be_tag = EXTENT_WRITTEN;
 		} else {
 			be->be_state = PNFS_BLOCK_READWRITE_DATA;
 			be->be_tag = 0;
 		}

 		be = ext_try_to_merge_left(root, be);
 		be = ext_try_to_merge_right(root, be);
 	}
 	spin_unlock(&bl->bl_ext_lock);
 }
	/*
	* Copyright (c) 2014 Christoph Hellwig.
	*/

	#include <linux/vmalloc.h>

	#include "blocklayout.h"

	#define NFSDBG_FACILITY NFSDBG_PNFS_LD

	static inline struct pnfs_block_extent *
	ext_node(struct rb_node *node)
	{
	return rb_entry(node, struct pnfs_block_extent, be_node);
	}

	static struct pnfs_block_extent *
	ext_tree_first(struct rb_root *root)
	{
	struct rb_node *node = rb_first(root);
	return node ? ext_node(node) : NULL;
	}

	static struct pnfs_block_extent *
	ext_tree_prev(struct pnfs_block_extent *be)
	{
	struct rb_node *node = rb_prev(&be->be_node);
	return node ? ext_node(node) : NULL;
	}

	static struct pnfs_block_extent *
	ext_tree_next(struct pnfs_block_extent *be)
	{
	struct rb_node *node = rb_next(&be->be_node);
	return node ? ext_node(node) : NULL;
	}

	static inline sector_t
	ext_f_end(struct pnfs_block_extent *be)
	{
	return be->be_f_offset + be->be_length;
	}

	static struct pnfs_block_extent *
	__ext_tree_search(struct rb_root *root, sector_t start)
	{
	struct rb_node *node = root->rb_node;
	struct pnfs_block_extent *be = NULL;

	while (node) {
	be = ext_node(node);
	if (start < be->be_f_offset)
	node = node->rb_left;
	else if (start >= ext_f_end(be))
	node = node->rb_right;
	else
	return be;
	}

	if (be) {
	if (start < be->be_f_offset)
	return be;

	if (start >= ext_f_end(be))
	return ext_tree_next(be);
	}

	return NULL;
	}

	static bool
	ext_can_merge(struct pnfs_block_extent be1, struct pnfs_block_extent be2)
	{
	if (be1->be_state != be2->be_state)
	return false;
	if (be1->be_device != be2->be_device)
	return false;

	if (be1->be_f_offset + be1->be_length != be2->be_f_offset)
	return false;

	if (be1->be_state != PNFS_BLOCK_NONE_DATA &&
	(be1->be_v_offset + be1->be_length != be2->be_v_offset))
	return false;

	if (be1->be_state == PNFS_BLOCK_INVALID_DATA &&
	be1->be_tag != be2->be_tag)
	return false;

	return true;
	}

	static struct pnfs_block_extent *
	ext_try_to_merge_left(struct rb_root root, struct pnfs_block_extent be)
	{
	struct pnfs_block_extent *left = ext_tree_prev(be);

	if (left && ext_can_merge(left, be)) {
	left->be_length += be->be_length;
	rb_erase(&be->be_node, root);
	nfs4_put_deviceid_node(be->be_device);
	kfree(be);
	return left;
	}

	return be;
	}

	static struct pnfs_block_extent *
	ext_try_to_merge_right(struct rb_root root, struct pnfs_block_extent be)
	{
	struct pnfs_block_extent *right = ext_tree_next(be);

	if (right && ext_can_merge(be, right)) {
	be->be_length += right->be_length;
	rb_erase(&right->be_node, root);
	nfs4_put_deviceid_node(right->be_device);
	kfree(right);
	}

	return be;
	}

	static void
	__ext_tree_insert(struct rb_root *root,
	struct pnfs_block_extent *new, bool merge_ok)
	{
	struct rb_node *p = &root->rb_node, parent = NULL;
	struct pnfs_block_extent *be;

	while (*p) {
	parent = *p;
	be = ext_node(parent);

	if (new->be_f_offset < be->be_f_offset) {
	if (merge_ok && ext_can_merge(new, be)) {
	be->be_f_offset = new->be_f_offset;
	if (be->be_state != PNFS_BLOCK_NONE_DATA)
	be->be_v_offset = new->be_v_offset;
	be->be_length += new->be_length;
	be = ext_try_to_merge_left(root, be);
	goto free_new;
	}
	p = &(*p)->rb_left;
	} else if (new->be_f_offset >= ext_f_end(be)) {
	if (merge_ok && ext_can_merge(be, new)) {
	be->be_length += new->be_length;
	be = ext_try_to_merge_right(root, be);
	goto free_new;
	}
	p = &(*p)->rb_right;
	} else {
	BUG();
	}
	}

	rb_link_node(&new->be_node, parent, p);
	rb_insert_color(&new->be_node, root);
	return;
	free_new:
	nfs4_put_deviceid_node(new->be_device);
	kfree(new);
	}

	static int
	__ext_tree_remove(struct rb_root *root, sector_t start, sector_t end)
	{
	struct pnfs_block_extent *be;
	sector_t len1 = 0, len2 = 0;
	sector_t orig_v_offset;
	sector_t orig_len;

	be = __ext_tree_search(root, start);
	if (!be)
	return 0;
	if (be->be_f_offset >= end)
	return 0;

	orig_v_offset = be->be_v_offset;
	orig_len = be->be_length;

	if (start > be->be_f_offset)
	len1 = start - be->be_f_offset;
	if (ext_f_end(be) > end)
	len2 = ext_f_end(be) - end;

	if (len2 > 0) {
	if (len1 > 0) {
	struct pnfs_block_extent *new;

	new = kzalloc(sizeof(*new), GFP_ATOMIC);
	if (!new)
	return -ENOMEM;

	be->be_length = len1;

	new->be_f_offset = end;
	if (be->be_state != PNFS_BLOCK_NONE_DATA) {
	new->be_v_offset =
	orig_v_offset + orig_len - len2;
	}
	new->be_length = len2;
	new->be_state = be->be_state;
	new->be_tag = be->be_tag;
	new->be_device = nfs4_get_deviceid(be->be_device);

	__ext_tree_insert(root, new, true);
	} else {
	be->be_f_offset = end;
	if (be->be_state != PNFS_BLOCK_NONE_DATA) {
	be->be_v_offset =
	orig_v_offset + orig_len - len2;
	}
	be->be_length = len2;
	}
	} else {
	if (len1 > 0) {
	be->be_length = len1;
	be = ext_tree_next(be);
	}

	while (be && ext_f_end(be) <= end) {
	struct pnfs_block_extent *next = ext_tree_next(be);

	rb_erase(&be->be_node, root);
	nfs4_put_deviceid_node(be->be_device);
	kfree(be);
	be = next;
	}

	if (be && be->be_f_offset < end) {
	len1 = ext_f_end(be) - end;
	be->be_f_offset = end;
	if (be->be_state != PNFS_BLOCK_NONE_DATA)
	be->be_v_offset += be->be_length - len1;
	be->be_length = len1;
	}
	}

	return 0;
	}

	int
	ext_tree_insert(struct pnfs_block_layout bl, struct pnfs_block_extent new)
	{
	struct pnfs_block_extent *be;
	struct rb_root *root;
	int err = 0;

	switch (new->be_state) {
	case PNFS_BLOCK_READWRITE_DATA:
	case PNFS_BLOCK_INVALID_DATA:
	root = &bl->bl_ext_rw;
	break;
	case PNFS_BLOCK_READ_DATA:
	case PNFS_BLOCK_NONE_DATA:
	root = &bl->bl_ext_ro;
	break;
	default:
	dprintk("invalid extent type\n");
	return -EINVAL;
	}

	spin_lock(&bl->bl_ext_lock);
	retry:
	be = __ext_tree_search(root, new->be_f_offset);
	if (!be \|\| be->be_f_offset >= ext_f_end(new)) {
	__ext_tree_insert(root, new, true);
	} else if (new->be_f_offset >= be->be_f_offset) {
	if (ext_f_end(new) <= ext_f_end(be)) {
	nfs4_put_deviceid_node(new->be_device);
	kfree(new);
	} else {
	sector_t new_len = ext_f_end(new) - ext_f_end(be);
	sector_t diff = new->be_length - new_len;

	new->be_f_offset += diff;
	new->be_v_offset += diff;
	new->be_length = new_len;
	goto retry;
	}
	} else if (ext_f_end(new) <= ext_f_end(be)) {
	new->be_length = be->be_f_offset - new->be_f_offset;
	__ext_tree_insert(root, new, true);
	} else {
	struct pnfs_block_extent *split;
	sector_t new_len = ext_f_end(new) - ext_f_end(be);
	sector_t diff = new->be_length - new_len;

	split = kmemdup(new, sizeof(*new), GFP_ATOMIC);
	if (!split) {
	err = -EINVAL;
	goto out;
	}

	split->be_length = be->be_f_offset - split->be_f_offset;
	split->be_device = nfs4_get_deviceid(new->be_device);
	__ext_tree_insert(root, split, true);

	new->be_f_offset += diff;
	new->be_v_offset += diff;
	new->be_length = new_len;
	goto retry;
	}
	out:
	spin_unlock(&bl->bl_ext_lock);
	return err;
	}

	static bool
	__ext_tree_lookup(struct rb_root *root, sector_t isect,
	struct pnfs_block_extent *ret)
	{
	struct rb_node *node;
	struct pnfs_block_extent *be;

	node = root->rb_node;
	while (node) {
	be = ext_node(node);
	if (isect < be->be_f_offset)
	node = node->rb_left;
	else if (isect >= ext_f_end(be))
	node = node->rb_right;
	else {
	ret = be;
	return true;
	}
	}

	return false;
	}

	bool
	ext_tree_lookup(struct pnfs_block_layout *bl, sector_t isect,
	struct pnfs_block_extent *ret, bool rw)
	{
	bool found = false;

	spin_lock(&bl->bl_ext_lock);
	if (!rw)
	found = __ext_tree_lookup(&bl->bl_ext_ro, isect, ret);
	if (!found)
	found = __ext_tree_lookup(&bl->bl_ext_rw, isect, ret);
	spin_unlock(&bl->bl_ext_lock);

	return found;
	}

	int ext_tree_remove(struct pnfs_block_layout *bl, bool rw,
	sector_t start, sector_t end)
	{
	int err, err2;

	spin_lock(&bl->bl_ext_lock);
	err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
	if (rw) {
	err2 = __ext_tree_remove(&bl->bl_ext_rw, start, end);
	if (!err)
	err = err2;
	}
	spin_unlock(&bl->bl_ext_lock);

	return err;
	}

	static int
	ext_tree_split(struct rb_root root, struct pnfs_block_extent be,
	sector_t split)
	{
	struct pnfs_block_extent *new;
	sector_t orig_len = be->be_length;

	new = kzalloc(sizeof(*new), GFP_ATOMIC);
	if (!new)
	return -ENOMEM;

	be->be_length = split - be->be_f_offset;

	new->be_f_offset = split;
	if (be->be_state != PNFS_BLOCK_NONE_DATA)
	new->be_v_offset = be->be_v_offset + be->be_length;
	new->be_length = orig_len - be->be_length;
	new->be_state = be->be_state;
	new->be_tag = be->be_tag;
	new->be_device = nfs4_get_deviceid(be->be_device);

	__ext_tree_insert(root, new, false);
	return 0;
	}

	int
	ext_tree_mark_written(struct pnfs_block_layout *bl, sector_t start,
	sector_t len)
	{
	struct rb_root *root = &bl->bl_ext_rw;
	sector_t end = start + len;
	struct pnfs_block_extent *be;
	int err = 0;

	spin_lock(&bl->bl_ext_lock);
	/*
	* First remove all COW extents or holes from written to range.
	*/
	err = __ext_tree_remove(&bl->bl_ext_ro, start, end);
	if (err)
	goto out;

	/*
	* Then mark all invalid extents in the range as written to.
	*/
	for (be = __ext_tree_search(root, start); be; be = ext_tree_next(be)) {
	if (be->be_f_offset >= end)
	break;

	if (be->be_state != PNFS_BLOCK_INVALID_DATA \|\| be->be_tag)
	continue;

	if (be->be_f_offset < start) {
	struct pnfs_block_extent *left = ext_tree_prev(be);

	if (left && ext_can_merge(left, be)) {
	sector_t diff = start - be->be_f_offset;

	left->be_length += diff;

	be->be_f_offset += diff;
	be->be_v_offset += diff;
	be->be_length -= diff;
	} else {
	err = ext_tree_split(root, be, start);
	if (err)
	goto out;
	}
	}

	if (ext_f_end(be) > end) {
	struct pnfs_block_extent *right = ext_tree_next(be);

	if (right && ext_can_merge(be, right)) {
	sector_t diff = end - be->be_f_offset;

	be->be_length -= diff;

	right->be_f_offset -= diff;
	right->be_v_offset -= diff;
	right->be_length += diff;
	} else {
	err = ext_tree_split(root, be, end);
	if (err)
	goto out;
	}
	}

	if (be->be_f_offset >= start && ext_f_end(be) <= end) {
	be->be_tag = EXTENT_WRITTEN;
	be = ext_try_to_merge_left(root, be);
	be = ext_try_to_merge_right(root, be);
	}
	}
	out:
	spin_unlock(&bl->bl_ext_lock);
	return err;
	}

	static void ext_tree_free_commitdata(struct nfs4_layoutcommit_args *arg,
	size_t buffer_size)
	{
	if (arg->layoutupdate_pages != &arg->layoutupdate_page) {
	int nr_pages = DIV_ROUND_UP(buffer_size, PAGE_SIZE), i;

	for (i = 0; i < nr_pages; i++)
	put_page(arg->layoutupdate_pages[i]);
	kfree(arg->layoutupdate_pages);
	} else {
	put_page(arg->layoutupdate_page);
	}
	}

	static int ext_tree_encode_commit(struct pnfs_block_layout bl, __be32 p,
	size_t buffer_size, size_t *count)
	{
	struct pnfs_block_extent *be;
	int ret = 0;

	spin_lock(&bl->bl_ext_lock);
	for (be = ext_tree_first(&bl->bl_ext_rw); be; be = ext_tree_next(be)) {
	if (be->be_state != PNFS_BLOCK_INVALID_DATA \|\|
	be->be_tag != EXTENT_WRITTEN)
	continue;

	(*count)++;
	if (count BL_EXTENT_SIZE > buffer_size) {
	/* keep counting.. */
	ret = -ENOSPC;
	continue;
	}

	p = xdr_encode_opaque_fixed(p, be->be_device->deviceid.data,
	NFS4_DEVICEID4_SIZE);
	p = xdr_encode_hyper(p, be->be_f_offset << SECTOR_SHIFT);
	p = xdr_encode_hyper(p, be->be_length << SECTOR_SHIFT);
	p = xdr_encode_hyper(p, 0LL);
	*p++ = cpu_to_be32(PNFS_BLOCK_READWRITE_DATA);

	be->be_tag = EXTENT_COMMITTING;
	}
	spin_unlock(&bl->bl_ext_lock);

	return ret;
	}

	int
	ext_tree_prepare_commit(struct nfs4_layoutcommit_args *arg)
	{
	struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
	size_t count = 0, buffer_size = PAGE_SIZE;
	__be32 *start_p;
	int ret;

	dprintk("%s enter\n", __func__);

	arg->layoutupdate_page = alloc_page(GFP_NOFS);
	if (!arg->layoutupdate_page)
	return -ENOMEM;
	start_p = page_address(arg->layoutupdate_page);
	arg->layoutupdate_pages = &arg->layoutupdate_page;

	retry:
	ret = ext_tree_encode_commit(bl, start_p + 1, buffer_size, &count);
	if (unlikely(ret)) {
	ext_tree_free_commitdata(arg, buffer_size);

	buffer_size = sizeof(__be32) + BL_EXTENT_SIZE * count;
	count = 0;

	arg->layoutupdate_pages =
	kcalloc(DIV_ROUND_UP(buffer_size, PAGE_SIZE),
	sizeof(struct page *), GFP_NOFS);
	if (!arg->layoutupdate_pages)
	return -ENOMEM;

	start_p = __vmalloc(buffer_size, GFP_NOFS, PAGE_KERNEL);
	if (!start_p) {
	kfree(arg->layoutupdate_pages);
	return -ENOMEM;
	}

	goto retry;
	}

	*start_p = cpu_to_be32(count);
	arg->layoutupdate_len = sizeof(__be32) + BL_EXTENT_SIZE * count;

	if (unlikely(arg->layoutupdate_pages != &arg->layoutupdate_page)) {
	__be32 *p = start_p;
	int i = 0;

	for (p = start_p;
	p < start_p + arg->layoutupdate_len;
	p += PAGE_SIZE) {
	arg->layoutupdate_pages[i++] = vmalloc_to_page(p);
	}
	}

	dprintk("%s found %zu ranges\n", __func__, count);
	return 0;
	}

	void
	ext_tree_mark_committed(struct nfs4_layoutcommit_args *arg, int status)
	{
	struct pnfs_block_layout *bl = BLK_LO2EXT(NFS_I(arg->inode)->layout);
	struct rb_root *root = &bl->bl_ext_rw;
	struct pnfs_block_extent *be;

	dprintk("%s status %d\n", __func__, status);

	ext_tree_free_commitdata(arg, arg->layoutupdate_len);

	spin_lock(&bl->bl_ext_lock);
	for (be = ext_tree_first(root); be; be = ext_tree_next(be)) {
	if (be->be_state != PNFS_BLOCK_INVALID_DATA \|\|
	be->be_tag != EXTENT_COMMITTING)
	continue;

	if (status) {
	/*
	* Mark as written and try again.
	*
	* XXX: some real error handling here wouldn't hurt..
	*/
	be->be_tag = EXTENT_WRITTEN;
	} else {
	be->be_state = PNFS_BLOCK_READWRITE_DATA;
	be->be_tag = 0;
	}

	be = ext_try_to_merge_left(root, be);
	be = ext_try_to_merge_right(root, be);
	}
	spin_unlock(&bl->bl_ext_lock);
	}