[deliverable/linux.git] / drivers / staging / lustre / lustre / ldlm / ldlm_extent.c

/*
 * GPL HEADER START
 *
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 only,
 * 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 version 2 for more details (a copy is included
 * in the LICENSE file that accompanied this code).
 *
 * You should have received a copy of the GNU General Public License
 * version 2 along with this program; If not, see
 * http://www.gnu.org/licenses/gpl-2.0.html
 *
 * GPL HEADER END
 */
/*
 * Copyright (c) 2002, 2010, Oracle and/or its affiliates. All rights reserved.
 * Use is subject to license terms.
 *
 * Copyright (c) 2010, 2012, Intel Corporation.
 */
/*
 * This file is part of Lustre, http://www.lustre.org/
 * Lustre is a trademark of Sun Microsystems, Inc.
 *
 * lustre/ldlm/ldlm_extent.c
 *
 * Author: Peter Braam <braam@clusterfs.com>
 * Author: Phil Schwan <phil@clusterfs.com>
 */

/**
 * This file contains implementation of EXTENT lock type
 *
 * EXTENT lock type is for locking a contiguous range of values, represented
 * by 64-bit starting and ending offsets (inclusive). There are several extent
 * lock modes, some of which may be mutually incompatible. Extent locks are
 * considered incompatible if their modes are incompatible and their extents
 * intersect.  See the lock mode compatibility matrix in lustre_dlm.h.
 */

#define DEBUG_SUBSYSTEM S_LDLM
#include "../../include/linux/libcfs/libcfs.h"
#include "../include/lustre_dlm.h"
#include "../include/obd_support.h"
#include "../include/obd.h"
#include "../include/obd_class.h"
#include "../include/lustre_lib.h"
#include "ldlm_internal.h"

/* When a lock is cancelled by a client, the KMS may undergo change if this
 * is the "highest lock".  This function returns the new KMS value.
 * Caller must hold lr_lock already.
 *
 * NB: A lock on [x,y] protects a KMS of up to y + 1 bytes!
 */
__u64 ldlm_extent_shift_kms(struct ldlm_lock *lock, __u64 old_kms)
{
	struct ldlm_resource *res = lock->l_resource;
	struct list_head *tmp;
	struct ldlm_lock *lck;
	__u64 kms = 0;

	/* don't let another thread in ldlm_extent_shift_kms race in
	 * just after we finish and take our lock into account in its
	 * calculation of the kms
	 */
	ldlm_set_kms_ignore(lock);

	list_for_each(tmp, &res->lr_granted) {
		lck = list_entry(tmp, struct ldlm_lock, l_res_link);

		if (ldlm_is_kms_ignore(lck))
			continue;

		if (lck->l_policy_data.l_extent.end >= old_kms)
			return old_kms;

		/* This extent _has_ to be smaller than old_kms (checked above)
		 * so kms can only ever be smaller or the same as old_kms.
		 */
		if (lck->l_policy_data.l_extent.end + 1 > kms)
			kms = lck->l_policy_data.l_extent.end + 1;
	}
	LASSERTF(kms <= old_kms, "kms %llu old_kms %llu\n", kms, old_kms);

	return kms;
}
EXPORT_SYMBOL(ldlm_extent_shift_kms);

struct kmem_cache *ldlm_interval_slab;

/* interval tree, for LDLM_EXTENT. */
static void ldlm_interval_attach(struct ldlm_interval *n, struct ldlm_lock *l)
{
	LASSERT(!l->l_tree_node);
	LASSERT(l->l_resource->lr_type == LDLM_EXTENT);

	list_add_tail(&l->l_sl_policy, &n->li_group);
	l->l_tree_node = n;
}

struct ldlm_interval *ldlm_interval_alloc(struct ldlm_lock *lock)
{
	struct ldlm_interval *node;

	LASSERT(lock->l_resource->lr_type == LDLM_EXTENT);
	node = kmem_cache_zalloc(ldlm_interval_slab, GFP_NOFS);
	if (!node)
		return NULL;

	INIT_LIST_HEAD(&node->li_group);
	ldlm_interval_attach(node, lock);
	return node;
}

void ldlm_interval_free(struct ldlm_interval *node)
{
	if (node) {
		LASSERT(list_empty(&node->li_group));
		LASSERT(!interval_is_intree(&node->li_node));
		kmem_cache_free(ldlm_interval_slab, node);
	}
}

struct ldlm_interval *ldlm_interval_detach(struct ldlm_lock *l)
{
	struct ldlm_interval *n = l->l_tree_node;

	if (!n)
		return NULL;

	LASSERT(!list_empty(&n->li_group));
	l->l_tree_node = NULL;
	list_del_init(&l->l_sl_policy);

	return list_empty(&n->li_group) ? n : NULL;
}

static inline int lock_mode_to_index(enum ldlm_mode mode)
{
	int index;

	LASSERT(mode != 0);
	LASSERT(is_power_of_2(mode));
	for (index = -1; mode; index++)
		mode >>= 1;
	LASSERT(index < LCK_MODE_NUM);
	return index;
}

/** Add newly granted lock into interval tree for the resource. */
void ldlm_extent_add_lock(struct ldlm_resource *res,
			  struct ldlm_lock *lock)
{
	struct interval_node *found, **root;
	struct ldlm_interval *node;
	struct ldlm_extent *extent;
	int idx;

	LASSERT(lock->l_granted_mode == lock->l_req_mode);

	node = lock->l_tree_node;
	LASSERT(node);
	LASSERT(!interval_is_intree(&node->li_node));

	idx = lock_mode_to_index(lock->l_granted_mode);
	LASSERT(lock->l_granted_mode == 1 << idx);
	LASSERT(lock->l_granted_mode == res->lr_itree[idx].lit_mode);

	/* node extent initialize */
	extent = &lock->l_policy_data.l_extent;
	interval_set(&node->li_node, extent->start, extent->end);

	root = &res->lr_itree[idx].lit_root;
	found = interval_insert(&node->li_node, root);
	if (found) { /* The policy group found. */
		struct ldlm_interval *tmp;

		tmp = ldlm_interval_detach(lock);
		ldlm_interval_free(tmp);
		ldlm_interval_attach(to_ldlm_interval(found), lock);
	}
	res->lr_itree[idx].lit_size++;

	/* even though we use interval tree to manage the extent lock, we also
	 * add the locks into grant list, for debug purpose, ..
	 */
	ldlm_resource_add_lock(res, &res->lr_granted, lock);
}

/** Remove cancelled lock from resource interval tree. */
void ldlm_extent_unlink_lock(struct ldlm_lock *lock)
{
	struct ldlm_resource *res = lock->l_resource;
	struct ldlm_interval *node = lock->l_tree_node;
	struct ldlm_interval_tree *tree;
	int idx;

	if (!node || !interval_is_intree(&node->li_node)) /* duplicate unlink */
		return;

	idx = lock_mode_to_index(lock->l_granted_mode);
	LASSERT(lock->l_granted_mode == 1 << idx);
	tree = &res->lr_itree[idx];

	LASSERT(tree->lit_root); /* assure the tree is not null */

	tree->lit_size--;
	node = ldlm_interval_detach(lock);
	if (node) {
		interval_erase(&node->li_node, &tree->lit_root);
		ldlm_interval_free(node);
	}
}

void ldlm_extent_policy_wire_to_local(const ldlm_wire_policy_data_t *wpolicy,
				      ldlm_policy_data_t *lpolicy)
{
	memset(lpolicy, 0, sizeof(*lpolicy));
	lpolicy->l_extent.start = wpolicy->l_extent.start;
	lpolicy->l_extent.end = wpolicy->l_extent.end;
	lpolicy->l_extent.gid = wpolicy->l_extent.gid;
}

void ldlm_extent_policy_local_to_wire(const ldlm_policy_data_t *lpolicy,
				      ldlm_wire_policy_data_t *wpolicy)
{
	memset(wpolicy, 0, sizeof(*wpolicy));
	wpolicy->l_extent.start = lpolicy->l_extent.start;
	wpolicy->l_extent.end = lpolicy->l_extent.end;
	wpolicy->l_extent.gid = lpolicy->l_extent.gid;
}
Commit	Line	Data
d7e09d03 PT	1	/*
	2	* GPL HEADER START
	3	*
	4	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	5	*
	6	* This program is free software; you can redistribute it and/or modify
	7	* it under the terms of the GNU General Public License version 2 only,
	8	* as published by the Free Software Foundation.
	9	*
	10	* This program is distributed in the hope that it will be useful, but
	11	* WITHOUT ANY WARRANTY; without even the implied warranty of
	12	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	13	* General Public License version 2 for more details (a copy is included
	14	* in the LICENSE file that accompanied this code).
	15	*
	16	* You should have received a copy of the GNU General Public License
	17	* version 2 along with this program; If not, see
6a5b99a4	18	* http://www.gnu.org/licenses/gpl-2.0.html
d7e09d03	19	*
d7e09d03 PT	20	* GPL HEADER END
	21	*/
	22	/*
	23	* Copyright (c) 2002, 2010, Oracle and/or its affiliates. All rights reserved.
	24	* Use is subject to license terms.
	25	*
	26	* Copyright (c) 2010, 2012, Intel Corporation.
	27	*/
	28	/*
	29	* This file is part of Lustre, http://www.lustre.org/
	30	* Lustre is a trademark of Sun Microsystems, Inc.
	31	*
	32	* lustre/ldlm/ldlm_extent.c
	33	*
	34	* Author: Peter Braam <braam@clusterfs.com>
	35	* Author: Phil Schwan <phil@clusterfs.com>
	36	*/
	37
	38	/**
	39	* This file contains implementation of EXTENT lock type
	40	*
	41	* EXTENT lock type is for locking a contiguous range of values, represented
	42	* by 64-bit starting and ending offsets (inclusive). There are several extent
	43	* lock modes, some of which may be mutually incompatible. Extent locks are
	44	* considered incompatible if their modes are incompatible and their extents
	45	* intersect. See the lock mode compatibility matrix in lustre_dlm.h.
	46	*/
	47
	48	#define DEBUG_SUBSYSTEM S_LDLM
9fdaf8c0	49	#include "../../include/linux/libcfs/libcfs.h"
e27db149 GKH	50	#include "../include/lustre_dlm.h"
	51	#include "../include/obd_support.h"
	52	#include "../include/obd.h"
	53	#include "../include/obd_class.h"
	54	#include "../include/lustre_lib.h"
d7e09d03 PT	55	#include "ldlm_internal.h"
d7e09d03 PT	56
d7e09d03 PT	57	/* When a lock is cancelled by a client, the KMS may undergo change if this
	58	* is the "highest lock". This function returns the new KMS value.
	59	* Caller must hold lr_lock already.
	60	*
6f789a6a OD	61	* NB: A lock on [x,y] protects a KMS of up to y + 1 bytes!
6f789a6a OD	62	*/
d7e09d03 PT	63	__u64 ldlm_extent_shift_kms(struct ldlm_lock *lock, __u64 old_kms)
	64	{
	65	struct ldlm_resource *res = lock->l_resource;
	66	struct list_head *tmp;
	67	struct ldlm_lock *lck;
	68	__u64 kms = 0;
d7e09d03 PT	69
	70	/* don't let another thread in ldlm_extent_shift_kms race in
	71	* just after we finish and take our lock into account in its
6f789a6a OD	72	* calculation of the kms
6f789a6a OD	73	*/
5a9a80ba	74	ldlm_set_kms_ignore(lock);
d7e09d03 PT	75
	76	list_for_each(tmp, &res->lr_granted) {
	77	lck = list_entry(tmp, struct ldlm_lock, l_res_link);
	78
5a9a80ba	79	if (ldlm_is_kms_ignore(lck))
d7e09d03 PT	80	continue;
	81
	82	if (lck->l_policy_data.l_extent.end >= old_kms)
0a3bdb00	83	return old_kms;
d7e09d03 PT	84
d7e09d03 PT	85	/* This extent _has_ to be smaller than old_kms (checked above)
6f789a6a OD	86	* so kms can only ever be smaller or the same as old_kms.
6f789a6a OD	87	*/
d7e09d03 PT	88	if (lck->l_policy_data.l_extent.end + 1 > kms)
	89	kms = lck->l_policy_data.l_extent.end + 1;
	90	}
b0f5aad5	91	LASSERTF(kms <= old_kms, "kms %llu old_kms %llu\n", kms, old_kms);
d7e09d03	92
0a3bdb00	93	return kms;
d7e09d03 PT	94	}
	95	EXPORT_SYMBOL(ldlm_extent_shift_kms);
	96
	97	struct kmem_cache *ldlm_interval_slab;
58c6d133 OD	98
	99	/* interval tree, for LDLM_EXTENT. */
	100	static void ldlm_interval_attach(struct ldlm_interval n, struct ldlm_lock l)
	101	{
	102	LASSERT(!l->l_tree_node);
	103	LASSERT(l->l_resource->lr_type == LDLM_EXTENT);
	104
	105	list_add_tail(&l->l_sl_policy, &n->li_group);
	106	l->l_tree_node = n;
	107	}
	108
d7e09d03 PT	109	struct ldlm_interval ldlm_interval_alloc(struct ldlm_lock lock)
	110	{
	111	struct ldlm_interval *node;
d7e09d03 PT	112
d7e09d03 PT	113	LASSERT(lock->l_resource->lr_type == LDLM_EXTENT);
3eed2d00	114	node = kmem_cache_zalloc(ldlm_interval_slab, GFP_NOFS);
44b53f18	115	if (!node)
0a3bdb00	116	return NULL;
d7e09d03 PT	117
	118	INIT_LIST_HEAD(&node->li_group);
	119	ldlm_interval_attach(node, lock);
0a3bdb00	120	return node;
d7e09d03 PT	121	}
	122
	123	void ldlm_interval_free(struct ldlm_interval *node)
	124	{
	125	if (node) {
	126	LASSERT(list_empty(&node->li_group));
	127	LASSERT(!interval_is_intree(&node->li_node));
5c4d8ed8	128	kmem_cache_free(ldlm_interval_slab, node);
d7e09d03 PT	129	}
	130	}
	131
d7e09d03 PT	132	struct ldlm_interval ldlm_interval_detach(struct ldlm_lock l)
	133	{
	134	struct ldlm_interval *n = l->l_tree_node;
	135
44b53f18	136	if (!n)
d7e09d03 PT	137	return NULL;
	138
	139	LASSERT(!list_empty(&n->li_group));
	140	l->l_tree_node = NULL;
	141	list_del_init(&l->l_sl_policy);
	142
730ebc81	143	return list_empty(&n->li_group) ? n : NULL;
d7e09d03 PT	144	}
d7e09d03 PT	145
52ee0d20	146	static inline int lock_mode_to_index(enum ldlm_mode mode)
d7e09d03 PT	147	{
	148	int index;
	149
	150	LASSERT(mode != 0);
5f4179e0	151	LASSERT(is_power_of_2(mode));
40c6dccf HM	152	for (index = -1; mode; index++)
40c6dccf HM	153	mode >>= 1;
d7e09d03 PT	154	LASSERT(index < LCK_MODE_NUM);
	155	return index;
	156	}
	157
	158	/** Add newly granted lock into interval tree for the resource. */
	159	void ldlm_extent_add_lock(struct ldlm_resource *res,
	160	struct ldlm_lock *lock)
	161	{
	162	struct interval_node found, *root;
	163	struct ldlm_interval *node;
	164	struct ldlm_extent *extent;
	165	int idx;
	166
	167	LASSERT(lock->l_granted_mode == lock->l_req_mode);
	168
	169	node = lock->l_tree_node;
44b53f18	170	LASSERT(node);
d7e09d03 PT	171	LASSERT(!interval_is_intree(&node->li_node));
	172
	173	idx = lock_mode_to_index(lock->l_granted_mode);
	174	LASSERT(lock->l_granted_mode == 1 << idx);
	175	LASSERT(lock->l_granted_mode == res->lr_itree[idx].lit_mode);
	176
	177	/* node extent initialize */
	178	extent = &lock->l_policy_data.l_extent;
	179	interval_set(&node->li_node, extent->start, extent->end);
	180
	181	root = &res->lr_itree[idx].lit_root;
	182	found = interval_insert(&node->li_node, root);
	183	if (found) { /* The policy group found. */
902f3bb1 AR	184	struct ldlm_interval *tmp;
	185
	186	tmp = ldlm_interval_detach(lock);
d7e09d03 PT	187	ldlm_interval_free(tmp);
	188	ldlm_interval_attach(to_ldlm_interval(found), lock);
	189	}
	190	res->lr_itree[idx].lit_size++;
	191
	192	/* even though we use interval tree to manage the extent lock, we also
6f789a6a OD	193	* add the locks into grant list, for debug purpose, ..
6f789a6a OD	194	*/
d7e09d03 PT	195	ldlm_resource_add_lock(res, &res->lr_granted, lock);
	196	}
	197
	198	/** Remove cancelled lock from resource interval tree. */
	199	void ldlm_extent_unlink_lock(struct ldlm_lock *lock)
	200	{
	201	struct ldlm_resource *res = lock->l_resource;
	202	struct ldlm_interval *node = lock->l_tree_node;
	203	struct ldlm_interval_tree *tree;
	204	int idx;
	205
	206	if (!node \|\| !interval_is_intree(&node->li_node)) /* duplicate unlink */
	207	return;
	208
	209	idx = lock_mode_to_index(lock->l_granted_mode);
	210	LASSERT(lock->l_granted_mode == 1 << idx);
	211	tree = &res->lr_itree[idx];
	212
44b53f18	213	LASSERT(tree->lit_root); /* assure the tree is not null */
d7e09d03 PT	214
	215	tree->lit_size--;
	216	node = ldlm_interval_detach(lock);
	217	if (node) {
	218	interval_erase(&node->li_node, &tree->lit_root);
	219	ldlm_interval_free(node);
	220	}
	221	}
	222
	223	void ldlm_extent_policy_wire_to_local(const ldlm_wire_policy_data_t *wpolicy,
24c198e9	224	ldlm_policy_data_t *lpolicy)
d7e09d03 PT	225	{
	226	memset(lpolicy, 0, sizeof(*lpolicy));
	227	lpolicy->l_extent.start = wpolicy->l_extent.start;
	228	lpolicy->l_extent.end = wpolicy->l_extent.end;
	229	lpolicy->l_extent.gid = wpolicy->l_extent.gid;
	230	}
	231
	232	void ldlm_extent_policy_local_to_wire(const ldlm_policy_data_t *lpolicy,
24c198e9	233	ldlm_wire_policy_data_t *wpolicy)
d7e09d03 PT	234	{
	235	memset(wpolicy, 0, sizeof(*wpolicy));
	236	wpolicy->l_extent.start = lpolicy->l_extent.start;
	237	wpolicy->l_extent.end = lpolicy->l_extent.end;
	238	wpolicy->l_extent.gid = lpolicy->l_extent.gid;
	239	}