[linux.git] / fs / nilfs2 / alloc.c

/*
 * alloc.c - NILFS dat/inode allocator
 *
 * Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 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., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 *
 * Original code was written by Koji Sato <[email protected]>.
 * Two allocators were unified by Ryusuke Konishi <[email protected]>,
 *                                Amagai Yoshiji <[email protected]>.
 */

#include <linux/types.h>
#include <linux/buffer_head.h>
#include <linux/fs.h>
#include <linux/bitops.h>
#include "mdt.h"
#include "alloc.h"


static inline unsigned long
nilfs_palloc_groups_per_desc_block(const struct inode *inode)
{
	return (1UL << inode->i_blkbits) /
		sizeof(struct nilfs_palloc_group_desc);
}

static inline unsigned long
nilfs_palloc_groups_count(const struct inode *inode)
{
	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
}

int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size)
{
	struct nilfs_mdt_info *mi = NILFS_MDT(inode);

	mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS);
	if (!mi->mi_bgl)
		return -ENOMEM;

	bgl_lock_init(mi->mi_bgl);

	nilfs_mdt_set_entry_size(inode, entry_size, 0);

	mi->mi_blocks_per_group =
		DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode),
			     mi->mi_entries_per_block) + 1;
		/* Number of blocks in a group including entry blocks and
		   a bitmap block */
	mi->mi_blocks_per_desc_block =
		nilfs_palloc_groups_per_desc_block(inode) *
		mi->mi_blocks_per_group + 1;
		/* Number of blocks per descriptor including the
		   descriptor block */
	return 0;
}

static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr,
					unsigned long *offset)
{
	__u64 group = nr;

	*offset = do_div(group, nilfs_palloc_entries_per_group(inode));
	return group;
}

static unsigned long
nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group)
{
	unsigned long desc_block =
		group / nilfs_palloc_groups_per_desc_block(inode);
	return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block;
}

static unsigned long
nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group)
{
	unsigned long desc_offset =
		group % nilfs_palloc_groups_per_desc_block(inode);
	return nilfs_palloc_desc_blkoff(inode, group) + 1 +
		desc_offset * NILFS_MDT(inode)->mi_blocks_per_group;
}

static unsigned long
nilfs_palloc_group_desc_nfrees(struct inode *inode, unsigned long group,
			       const struct nilfs_palloc_group_desc *desc)
{
	unsigned long nfree;

	spin_lock(nilfs_mdt_bgl_lock(inode, group));
	nfree = le32_to_cpu(desc->pg_nfrees);
	spin_unlock(nilfs_mdt_bgl_lock(inode, group));
	return nfree;
}

static void
nilfs_palloc_group_desc_add_entries(struct inode *inode,
				    unsigned long group,
				    struct nilfs_palloc_group_desc *desc,
				    u32 n)
{
	spin_lock(nilfs_mdt_bgl_lock(inode, group));
	le32_add_cpu(&desc->pg_nfrees, n);
	spin_unlock(nilfs_mdt_bgl_lock(inode, group));
}

static unsigned long
nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr)
{
	unsigned long group, group_offset;

	group = nilfs_palloc_group(inode, nr, &group_offset);

	return nilfs_palloc_bitmap_blkoff(inode, group) + 1 +
		group_offset / NILFS_MDT(inode)->mi_entries_per_block;
}

static void nilfs_palloc_desc_block_init(struct inode *inode,
					 struct buffer_head *bh, void *kaddr)
{
	struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh);
	unsigned long n = nilfs_palloc_groups_per_desc_block(inode);
	__le32 nfrees;

	nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode));
	while (n-- > 0) {
		desc->pg_nfrees = nfrees;
		desc++;
	}
}

static int nilfs_palloc_get_desc_block(struct inode *inode,
				       unsigned long group,
				       int create, struct buffer_head **bhp)
{
	return nilfs_mdt_get_block(inode,
				   nilfs_palloc_desc_blkoff(inode, group),
				   create, nilfs_palloc_desc_block_init, bhp);
}

static int nilfs_palloc_get_bitmap_block(struct inode *inode,
					 unsigned long group,
					 int create, struct buffer_head **bhp)
{
	return nilfs_mdt_get_block(inode,
				   nilfs_palloc_bitmap_blkoff(inode, group),
				   create, NULL, bhp);
}

int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
				 int create, struct buffer_head **bhp)
{
	return nilfs_mdt_get_block(inode, nilfs_palloc_entry_blkoff(inode, nr),
				   create, NULL, bhp);
}

static struct nilfs_palloc_group_desc *
nilfs_palloc_block_get_group_desc(const struct inode *inode,
				  unsigned long group,
				  const struct buffer_head *bh, void *kaddr)
{
	return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
		group % nilfs_palloc_groups_per_desc_block(inode);
}

void *nilfs_palloc_block_get_entry(const struct inode *inode, __u64 nr,
				   const struct buffer_head *bh, void *kaddr)
{
	unsigned long entry_offset, group_offset;

	nilfs_palloc_group(inode, nr, &group_offset);
	entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;

	return kaddr + bh_offset(bh) +
		entry_offset * NILFS_MDT(inode)->mi_entry_size;
}

static int nilfs_palloc_find_available_slot(struct inode *inode,
					    unsigned long group,
					    unsigned long target,
					    unsigned char *bitmap,
					    int bsize)  /* size in bits */
{
	int curr, pos, end, i;

	if (target > 0) {
		end = (target + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1);
		if (end > bsize)
			end = bsize;
		pos = nilfs_find_next_zero_bit(bitmap, end, target);
		if (pos < end &&
		    !nilfs_set_bit_atomic(
			    nilfs_mdt_bgl_lock(inode, group), pos, bitmap))
			return pos;
	} else
		end = 0;

	for (i = 0, curr = end;
	     i < bsize;
	     i += BITS_PER_LONG, curr += BITS_PER_LONG) {
		/* wrap around */
		if (curr >= bsize)
			curr = 0;
		while (*((unsigned long *)bitmap + curr / BITS_PER_LONG)
		       != ~0UL) {
			end = curr + BITS_PER_LONG;
			if (end > bsize)
				end = bsize;
			pos = nilfs_find_next_zero_bit(bitmap, end, curr);
			if ((pos < end) &&
			    !nilfs_set_bit_atomic(
				    nilfs_mdt_bgl_lock(inode, group), pos,
				    bitmap))
				return pos;
		}
	}
	return -ENOSPC;
}

static unsigned long
nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
				       unsigned long curr, unsigned long max)
{
	return min_t(unsigned long,
		     nilfs_palloc_groups_per_desc_block(inode) -
		     curr % nilfs_palloc_groups_per_desc_block(inode),
		     max - curr + 1);
}

int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
				     struct nilfs_palloc_req *req)
{
	struct buffer_head *desc_bh, *bitmap_bh;
	struct nilfs_palloc_group_desc *desc;
	unsigned char *bitmap;
	void *desc_kaddr, *bitmap_kaddr;
	unsigned long group, maxgroup, ngroups;
	unsigned long group_offset, maxgroup_offset;
	unsigned long n, entries_per_group, groups_per_desc_block;
	unsigned long i, j;
	int pos, ret;

	ngroups = nilfs_palloc_groups_count(inode);
	maxgroup = ngroups - 1;
	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	entries_per_group = nilfs_palloc_entries_per_group(inode);
	groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode);

	for (i = 0; i < ngroups; i += n) {
		if (group >= ngroups) {
			/* wrap around */
			group = 0;
			maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
						      &maxgroup_offset) - 1;
		}
		ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
		if (ret < 0)
			return ret;
		desc_kaddr = kmap(desc_bh->b_page);
		desc = nilfs_palloc_block_get_group_desc(
			inode, group, desc_bh, desc_kaddr);
		n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
							   maxgroup);
		for (j = 0; j < n; j++, desc++, group++) {
			if (nilfs_palloc_group_desc_nfrees(inode, group, desc)
			    > 0) {
				ret = nilfs_palloc_get_bitmap_block(
					inode, group, 1, &bitmap_bh);
				if (ret < 0)
					goto out_desc;
				bitmap_kaddr = kmap(bitmap_bh->b_page);
				bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
				pos = nilfs_palloc_find_available_slot(
					inode, group, group_offset, bitmap,
					entries_per_group);
				if (pos >= 0) {
					/* found a free entry */
					nilfs_palloc_group_desc_add_entries(
						inode, group, desc, -1);
					req->pr_entry_nr =
						entries_per_group * group + pos;
					kunmap(desc_bh->b_page);
					kunmap(bitmap_bh->b_page);

					req->pr_desc_bh = desc_bh;
					req->pr_bitmap_bh = bitmap_bh;
					return 0;
				}
				kunmap(bitmap_bh->b_page);
				brelse(bitmap_bh);
			}

			group_offset = 0;
		}

		kunmap(desc_bh->b_page);
		brelse(desc_bh);
	}

	/* no entries left */
	return -ENOSPC;

 out_desc:
	kunmap(desc_bh->b_page);
	brelse(desc_bh);
	return ret;
}

void nilfs_palloc_commit_alloc_entry(struct inode *inode,
				     struct nilfs_palloc_req *req)
{
	nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
	nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
	nilfs_mdt_mark_dirty(inode);

	brelse(req->pr_bitmap_bh);
	brelse(req->pr_desc_bh);
}

void nilfs_palloc_commit_free_entry(struct inode *inode,
				    struct nilfs_palloc_req *req)
{
	struct nilfs_palloc_group_desc *desc;
	unsigned long group, group_offset;
	unsigned char *bitmap;
	void *desc_kaddr, *bitmap_kaddr;

	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	desc_kaddr = kmap(req->pr_desc_bh->b_page);
	desc = nilfs_palloc_block_get_group_desc(inode, group,
						 req->pr_desc_bh, desc_kaddr);
	bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);

	if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
				    group_offset, bitmap))
		printk(KERN_WARNING "%s: entry number %llu already freed\n",
		       __func__, (unsigned long long)req->pr_entry_nr);

	nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);

	kunmap(req->pr_bitmap_bh->b_page);
	kunmap(req->pr_desc_bh->b_page);

	nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
	nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
	nilfs_mdt_mark_dirty(inode);

	brelse(req->pr_bitmap_bh);
	brelse(req->pr_desc_bh);
}

void nilfs_palloc_abort_alloc_entry(struct inode *inode,
				    struct nilfs_palloc_req *req)
{
	struct nilfs_palloc_group_desc *desc;
	void *desc_kaddr, *bitmap_kaddr;
	unsigned char *bitmap;
	unsigned long group, group_offset;

	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	desc_kaddr = kmap(req->pr_desc_bh->b_page);
	desc = nilfs_palloc_block_get_group_desc(inode, group,
						 req->pr_desc_bh, desc_kaddr);
	bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
	if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
				    group_offset, bitmap))
		printk(KERN_WARNING "%s: entry numer %llu already freed\n",
		       __func__, (unsigned long long)req->pr_entry_nr);

	nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);

	kunmap(req->pr_bitmap_bh->b_page);
	kunmap(req->pr_desc_bh->b_page);

	brelse(req->pr_bitmap_bh);
	brelse(req->pr_desc_bh);

	req->pr_entry_nr = 0;
	req->pr_bitmap_bh = NULL;
	req->pr_desc_bh = NULL;
}

int nilfs_palloc_prepare_free_entry(struct inode *inode,
				    struct nilfs_palloc_req *req)
{
	struct buffer_head *desc_bh, *bitmap_bh;
	unsigned long group, group_offset;
	int ret;

	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
	if (ret < 0)
		return ret;
	ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
	if (ret < 0) {
		brelse(desc_bh);
		return ret;
	}

	req->pr_desc_bh = desc_bh;
	req->pr_bitmap_bh = bitmap_bh;
	return 0;
}

void nilfs_palloc_abort_free_entry(struct inode *inode,
				   struct nilfs_palloc_req *req)
{
	brelse(req->pr_bitmap_bh);
	brelse(req->pr_desc_bh);

	req->pr_entry_nr = 0;
	req->pr_bitmap_bh = NULL;
	req->pr_desc_bh = NULL;
}

static int
nilfs_palloc_group_is_in(struct inode *inode, unsigned long group, __u64 nr)
{
	__u64 first, last;

	first = group * nilfs_palloc_entries_per_group(inode);
	last = first + nilfs_palloc_entries_per_group(inode) - 1;
	return (nr >= first) && (nr <= last);
}

int nilfs_palloc_freev(struct inode *inode, __u64 *entry_nrs, size_t nitems)
{
	struct buffer_head *desc_bh, *bitmap_bh;
	struct nilfs_palloc_group_desc *desc;
	unsigned char *bitmap;
	void *desc_kaddr, *bitmap_kaddr;
	unsigned long group, group_offset;
	int i, j, n, ret;

	for (i = 0; i < nitems; i += n) {
		group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
		ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
		if (ret < 0)
			return ret;
		ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
						    &bitmap_bh);
		if (ret < 0) {
			brelse(desc_bh);
			return ret;
		}
		desc_kaddr = kmap(desc_bh->b_page);
		desc = nilfs_palloc_block_get_group_desc(
			inode, group, desc_bh, desc_kaddr);
		bitmap_kaddr = kmap(bitmap_bh->b_page);
		bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
		for (j = i, n = 0;
		     (j < nitems) && nilfs_palloc_group_is_in(inode, group,
							      entry_nrs[j]);
		     j++, n++) {
			nilfs_palloc_group(inode, entry_nrs[j], &group_offset);
			if (!nilfs_clear_bit_atomic(
				    nilfs_mdt_bgl_lock(inode, group),
				    group_offset, bitmap)) {
				printk(KERN_WARNING
				       "%s: entry number %llu already freed\n",
				       __func__,
				       (unsigned long long)entry_nrs[j]);
			}
		}
		nilfs_palloc_group_desc_add_entries(inode, group, desc, n);

		kunmap(bitmap_bh->b_page);
		kunmap(desc_bh->b_page);

		nilfs_mdt_mark_buffer_dirty(desc_bh);
		nilfs_mdt_mark_buffer_dirty(bitmap_bh);
		nilfs_mdt_mark_dirty(inode);

		brelse(bitmap_bh);
		brelse(desc_bh);
	}
	return 0;
}
Commit	Line	Data
5442680f RK	1	/*
	2	* alloc.c - NILFS dat/inode allocator
	3	*
	4	* Copyright (C) 2006-2008 Nippon Telegraph and Telephone Corporation.
	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 as published by
	8	* the Free Software Foundation; either version 2 of the License, or
	9	* (at your option) any later version.
	10	*
	11	* This program is distributed in the hope that it will be useful,
	12	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	13	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	14	* GNU General Public License for more details.
	15	*
	16	* You should have received a copy of the GNU General Public License
	17	* along with this program; if not, write to the Free Software
	18	* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
	19	*
	20	* Original code was written by Koji Sato <[email protected]>.
	21	* Two allocators were unified by Ryusuke Konishi <[email protected]>,
	22	* Amagai Yoshiji <[email protected]>.
	23	*/
	24
	25	#include <linux/types.h>
	26	#include <linux/buffer_head.h>
	27	#include <linux/fs.h>
	28	#include <linux/bitops.h>
	29	#include "mdt.h"
	30	#include "alloc.h"
	31
	32
	33	static inline unsigned long
	34	nilfs_palloc_groups_per_desc_block(const struct inode *inode)
	35	{
	36	return (1UL << inode->i_blkbits) /
	37	sizeof(struct nilfs_palloc_group_desc);
	38	}
	39
	40	static inline unsigned long
	41	nilfs_palloc_groups_count(const struct inode *inode)
	42	{
	43	return 1UL << (BITS_PER_LONG - (inode->i_blkbits + 3 /* log2(8) */));
	44	}
	45
	46	int nilfs_palloc_init_blockgroup(struct inode *inode, unsigned entry_size)
	47	{
	48	struct nilfs_mdt_info *mi = NILFS_MDT(inode);
	49
	50	mi->mi_bgl = kmalloc(sizeof(*mi->mi_bgl), GFP_NOFS);
	51	if (!mi->mi_bgl)
	52	return -ENOMEM;
	53
	54	bgl_lock_init(mi->mi_bgl);
	55
	56	nilfs_mdt_set_entry_size(inode, entry_size, 0);
	57
	58	mi->mi_blocks_per_group =
	59	DIV_ROUND_UP(nilfs_palloc_entries_per_group(inode),
	60	mi->mi_entries_per_block) + 1;
	61	/* Number of blocks in a group including entry blocks and
	62	a bitmap block */
	63	mi->mi_blocks_per_desc_block =
	64	nilfs_palloc_groups_per_desc_block(inode) *
65	mi->mi_blocks_per_group + 1;
66	/* Number of blocks per descriptor including the
67	descriptor block */
68	return 0;
69	}
70
71	static unsigned long nilfs_palloc_group(const struct inode *inode, __u64 nr,
72	unsigned long *offset)
73	{
74	__u64 group = nr;
75
76	*offset = do_div(group, nilfs_palloc_entries_per_group(inode));
77	return group;
78	}
79
80	static unsigned long
81	nilfs_palloc_desc_blkoff(const struct inode *inode, unsigned long group)
82	{
83	unsigned long desc_block =
84	group / nilfs_palloc_groups_per_desc_block(inode);
85	return desc_block * NILFS_MDT(inode)->mi_blocks_per_desc_block;
86	}
87
88	static unsigned long
89	nilfs_palloc_bitmap_blkoff(const struct inode *inode, unsigned long group)
90	{
91	unsigned long desc_offset =
92	group % nilfs_palloc_groups_per_desc_block(inode);
93	return nilfs_palloc_desc_blkoff(inode, group) + 1 +
94	desc_offset * NILFS_MDT(inode)->mi_blocks_per_group;
95	}
96
97	static unsigned long
98	nilfs_palloc_group_desc_nfrees(struct inode *inode, unsigned long group,
99	const struct nilfs_palloc_group_desc *desc)
100	{
101	unsigned long nfree;
102
103	spin_lock(nilfs_mdt_bgl_lock(inode, group));
104	nfree = le32_to_cpu(desc->pg_nfrees);
105	spin_unlock(nilfs_mdt_bgl_lock(inode, group));
106	return nfree;
107	}
108
109	static void
110	nilfs_palloc_group_desc_add_entries(struct inode *inode,
111	unsigned long group,
112	struct nilfs_palloc_group_desc *desc,
113	u32 n)
114	{
115	spin_lock(nilfs_mdt_bgl_lock(inode, group));
116	le32_add_cpu(&desc->pg_nfrees, n);
117	spin_unlock(nilfs_mdt_bgl_lock(inode, group));
118	}
119
120	static unsigned long
121	nilfs_palloc_entry_blkoff(const struct inode *inode, __u64 nr)
122	{
123	unsigned long group, group_offset;
124
125	group = nilfs_palloc_group(inode, nr, &group_offset);
126
127	return nilfs_palloc_bitmap_blkoff(inode, group) + 1 +
128	group_offset / NILFS_MDT(inode)->mi_entries_per_block;
129	}
130
131	static void nilfs_palloc_desc_block_init(struct inode *inode,
132	struct buffer_head bh, void kaddr)
133	{
134	struct nilfs_palloc_group_desc *desc = kaddr + bh_offset(bh);
135	unsigned long n = nilfs_palloc_groups_per_desc_block(inode);
136	__le32 nfrees;
137
138	nfrees = cpu_to_le32(nilfs_palloc_entries_per_group(inode));
139	while (n-- > 0) {
140	desc->pg_nfrees = nfrees;
141	desc++;
142	}
143	}
144
145	static int nilfs_palloc_get_desc_block(struct inode *inode,
146	unsigned long group,
147	int create, struct buffer_head **bhp)
148	{
149	return nilfs_mdt_get_block(inode,
150	nilfs_palloc_desc_blkoff(inode, group),
151	create, nilfs_palloc_desc_block_init, bhp);
152	}
153
154	static int nilfs_palloc_get_bitmap_block(struct inode *inode,
155	unsigned long group,
156	int create, struct buffer_head **bhp)
157	{
158	return nilfs_mdt_get_block(inode,
159	nilfs_palloc_bitmap_blkoff(inode, group),
160	create, NULL, bhp);
161	}
162
163	int nilfs_palloc_get_entry_block(struct inode *inode, __u64 nr,
164	int create, struct buffer_head **bhp)
165	{
166	return nilfs_mdt_get_block(inode, nilfs_palloc_entry_blkoff(inode, nr),
167	create, NULL, bhp);
168	}
169
170	static struct nilfs_palloc_group_desc *
171	nilfs_palloc_block_get_group_desc(const struct inode *inode,
172	unsigned long group,
173	const struct buffer_head bh, void kaddr)
174	{
175	return (struct nilfs_palloc_group_desc *)(kaddr + bh_offset(bh)) +
176	group % nilfs_palloc_groups_per_desc_block(inode);
177	}
178
5442680f RK	179	void nilfs_palloc_block_get_entry(const struct inode inode, __u64 nr,
	180	const struct buffer_head bh, void kaddr)
	181	{
	182	unsigned long entry_offset, group_offset;
	183
	184	nilfs_palloc_group(inode, nr, &group_offset);
	185	entry_offset = group_offset % NILFS_MDT(inode)->mi_entries_per_block;
	186
	187	return kaddr + bh_offset(bh) +
	188	entry_offset * NILFS_MDT(inode)->mi_entry_size;
	189	}
	190
	191	static int nilfs_palloc_find_available_slot(struct inode *inode,
	192	unsigned long group,
	193	unsigned long target,
	194	unsigned char *bitmap,
	195	int bsize) /* size in bits */
	196	{
	197	int curr, pos, end, i;
	198
	199	if (target > 0) {
	200	end = (target + BITS_PER_LONG - 1) & ~(BITS_PER_LONG - 1);
	201	if (end > bsize)
	202	end = bsize;
	203	pos = nilfs_find_next_zero_bit(bitmap, end, target);
	204	if (pos < end &&
	205	!nilfs_set_bit_atomic(
	206	nilfs_mdt_bgl_lock(inode, group), pos, bitmap))
	207	return pos;
	208	} else
	209	end = 0;
	210
	211	for (i = 0, curr = end;
	212	i < bsize;
	213	i += BITS_PER_LONG, curr += BITS_PER_LONG) {
	214	/* wrap around */
	215	if (curr >= bsize)
	216	curr = 0;
	217	while (((unsigned long )bitmap + curr / BITS_PER_LONG)
	218	!= ~0UL) {
	219	end = curr + BITS_PER_LONG;
	220	if (end > bsize)
	221	end = bsize;
	222	pos = nilfs_find_next_zero_bit(bitmap, end, curr);
	223	if ((pos < end) &&
	224	!nilfs_set_bit_atomic(
	225	nilfs_mdt_bgl_lock(inode, group), pos,
	226	bitmap))
	227	return pos;
	228	}
	229	}
	230	return -ENOSPC;
	231	}
	232
	233	static unsigned long
	234	nilfs_palloc_rest_groups_in_desc_block(const struct inode *inode,
	235	unsigned long curr, unsigned long max)
	236	{
	237	return min_t(unsigned long,
	238	nilfs_palloc_groups_per_desc_block(inode) -
	239	curr % nilfs_palloc_groups_per_desc_block(inode),
	240	max - curr + 1);
	241	}
	242
243	int nilfs_palloc_prepare_alloc_entry(struct inode *inode,
244	struct nilfs_palloc_req *req)
245	{
246	struct buffer_head desc_bh, bitmap_bh;
247	struct nilfs_palloc_group_desc *desc;
248	unsigned char *bitmap;
249	void desc_kaddr, bitmap_kaddr;
250	unsigned long group, maxgroup, ngroups;
251	unsigned long group_offset, maxgroup_offset;
252	unsigned long n, entries_per_group, groups_per_desc_block;
253	unsigned long i, j;
254	int pos, ret;
255
256	ngroups = nilfs_palloc_groups_count(inode);
257	maxgroup = ngroups - 1;
258	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
259	entries_per_group = nilfs_palloc_entries_per_group(inode);
260	groups_per_desc_block = nilfs_palloc_groups_per_desc_block(inode);
261
262	for (i = 0; i < ngroups; i += n) {
263	if (group >= ngroups) {
264	/* wrap around */
265	group = 0;
266	maxgroup = nilfs_palloc_group(inode, req->pr_entry_nr,
267	&maxgroup_offset) - 1;
268	}
269	ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
270	if (ret < 0)
271	return ret;
272	desc_kaddr = kmap(desc_bh->b_page);
273	desc = nilfs_palloc_block_get_group_desc(
274	inode, group, desc_bh, desc_kaddr);
275	n = nilfs_palloc_rest_groups_in_desc_block(inode, group,
276	maxgroup);
277	for (j = 0; j < n; j++, desc++, group++) {
278	if (nilfs_palloc_group_desc_nfrees(inode, group, desc)
279	> 0) {
280	ret = nilfs_palloc_get_bitmap_block(
281	inode, group, 1, &bitmap_bh);
282	if (ret < 0)
283	goto out_desc;
284	bitmap_kaddr = kmap(bitmap_bh->b_page);
141bbdba	285	bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
5442680f RK	286	pos = nilfs_palloc_find_available_slot(
	287	inode, group, group_offset, bitmap,
	288	entries_per_group);
	289	if (pos >= 0) {
	290	/* found a free entry */
	291	nilfs_palloc_group_desc_add_entries(
	292	inode, group, desc, -1);
	293	req->pr_entry_nr =
	294	entries_per_group * group + pos;
	295	kunmap(desc_bh->b_page);
	296	kunmap(bitmap_bh->b_page);
	297
	298	req->pr_desc_bh = desc_bh;
	299	req->pr_bitmap_bh = bitmap_bh;
	300	return 0;
	301	}
	302	kunmap(bitmap_bh->b_page);
	303	brelse(bitmap_bh);
	304	}
	305
	306	group_offset = 0;
	307	}
	308
	309	kunmap(desc_bh->b_page);
	310	brelse(desc_bh);
	311	}
	312
	313	/* no entries left */
	314	return -ENOSPC;
	315
	316	out_desc:
	317	kunmap(desc_bh->b_page);
	318	brelse(desc_bh);
	319	return ret;
	320	}
	321
	322	void nilfs_palloc_commit_alloc_entry(struct inode *inode,
	323	struct nilfs_palloc_req *req)
	324	{
	325	nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
	326	nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
	327	nilfs_mdt_mark_dirty(inode);
	328
	329	brelse(req->pr_bitmap_bh);
	330	brelse(req->pr_desc_bh);
	331	}
	332
	333	void nilfs_palloc_commit_free_entry(struct inode *inode,
	334	struct nilfs_palloc_req *req)
	335	{
	336	struct nilfs_palloc_group_desc *desc;
	337	unsigned long group, group_offset;
	338	unsigned char *bitmap;
	339	void desc_kaddr, bitmap_kaddr;
	340
	341	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	342	desc_kaddr = kmap(req->pr_desc_bh->b_page);
	343	desc = nilfs_palloc_block_get_group_desc(inode, group,
	344	req->pr_desc_bh, desc_kaddr);
	345	bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
141bbdba	346	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
5442680f RK	347
	348	if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
	349	group_offset, bitmap))
	350	printk(KERN_WARNING "%s: entry number %llu already freed\n",
	351	__func__, (unsigned long long)req->pr_entry_nr);
	352
	353	nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);
	354
	355	kunmap(req->pr_bitmap_bh->b_page);
	356	kunmap(req->pr_desc_bh->b_page);
	357
	358	nilfs_mdt_mark_buffer_dirty(req->pr_desc_bh);
	359	nilfs_mdt_mark_buffer_dirty(req->pr_bitmap_bh);
	360	nilfs_mdt_mark_dirty(inode);
	361
	362	brelse(req->pr_bitmap_bh);
	363	brelse(req->pr_desc_bh);
	364	}
	365
	366	void nilfs_palloc_abort_alloc_entry(struct inode *inode,
	367	struct nilfs_palloc_req *req)
	368	{
	369	struct nilfs_palloc_group_desc *desc;
	370	void desc_kaddr, bitmap_kaddr;
	371	unsigned char *bitmap;
	372	unsigned long group, group_offset;
	373
	374	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	375	desc_kaddr = kmap(req->pr_desc_bh->b_page);
	376	desc = nilfs_palloc_block_get_group_desc(inode, group,
	377	req->pr_desc_bh, desc_kaddr);
	378	bitmap_kaddr = kmap(req->pr_bitmap_bh->b_page);
141bbdba	379	bitmap = bitmap_kaddr + bh_offset(req->pr_bitmap_bh);
5442680f RK	380	if (!nilfs_clear_bit_atomic(nilfs_mdt_bgl_lock(inode, group),
	381	group_offset, bitmap))
	382	printk(KERN_WARNING "%s: entry numer %llu already freed\n",
	383	__func__, (unsigned long long)req->pr_entry_nr);
	384
	385	nilfs_palloc_group_desc_add_entries(inode, group, desc, 1);
	386
	387	kunmap(req->pr_bitmap_bh->b_page);
	388	kunmap(req->pr_desc_bh->b_page);
	389
	390	brelse(req->pr_bitmap_bh);
	391	brelse(req->pr_desc_bh);
	392
	393	req->pr_entry_nr = 0;
	394	req->pr_bitmap_bh = NULL;
	395	req->pr_desc_bh = NULL;
	396	}
	397
	398	int nilfs_palloc_prepare_free_entry(struct inode *inode,
	399	struct nilfs_palloc_req *req)
	400	{
	401	struct buffer_head desc_bh, bitmap_bh;
	402	unsigned long group, group_offset;
	403	int ret;
	404
	405	group = nilfs_palloc_group(inode, req->pr_entry_nr, &group_offset);
	406	ret = nilfs_palloc_get_desc_block(inode, group, 1, &desc_bh);
	407	if (ret < 0)
	408	return ret;
	409	ret = nilfs_palloc_get_bitmap_block(inode, group, 1, &bitmap_bh);
	410	if (ret < 0) {
	411	brelse(desc_bh);
	412	return ret;
	413	}
	414
	415	req->pr_desc_bh = desc_bh;
	416	req->pr_bitmap_bh = bitmap_bh;
	417	return 0;
	418	}
	419
	420	void nilfs_palloc_abort_free_entry(struct inode *inode,
	421	struct nilfs_palloc_req *req)
	422	{
	423	brelse(req->pr_bitmap_bh);
	424	brelse(req->pr_desc_bh);
	425
	426	req->pr_entry_nr = 0;
	427	req->pr_bitmap_bh = NULL;
	428	req->pr_desc_bh = NULL;
	429	}
	430
	431	static int
	432	nilfs_palloc_group_is_in(struct inode *inode, unsigned long group, __u64 nr)
	433	{
	434	__u64 first, last;
	435
	436	first = group * nilfs_palloc_entries_per_group(inode);
	437	last = first + nilfs_palloc_entries_per_group(inode) - 1;
	438	return (nr >= first) && (nr <= last);
	439	}
	440
	441	int nilfs_palloc_freev(struct inode inode, __u64 entry_nrs, size_t nitems)
	442	{
	443	struct buffer_head desc_bh, bitmap_bh;
444	struct nilfs_palloc_group_desc *desc;
445	unsigned char *bitmap;
446	void desc_kaddr, bitmap_kaddr;
447	unsigned long group, group_offset;
448	int i, j, n, ret;
449
450	for (i = 0; i < nitems; i += n) {
451	group = nilfs_palloc_group(inode, entry_nrs[i], &group_offset);
452	ret = nilfs_palloc_get_desc_block(inode, group, 0, &desc_bh);
453	if (ret < 0)
454	return ret;
455	ret = nilfs_palloc_get_bitmap_block(inode, group, 0,
456	&bitmap_bh);
457	if (ret < 0) {
458	brelse(desc_bh);
459	return ret;
460	}
461	desc_kaddr = kmap(desc_bh->b_page);
462	desc = nilfs_palloc_block_get_group_desc(
463	inode, group, desc_bh, desc_kaddr);
464	bitmap_kaddr = kmap(bitmap_bh->b_page);
141bbdba	465	bitmap = bitmap_kaddr + bh_offset(bitmap_bh);
5442680f RK	466	for (j = i, n = 0;
	467	(j < nitems) && nilfs_palloc_group_is_in(inode, group,
	468	entry_nrs[j]);
	469	j++, n++) {
	470	nilfs_palloc_group(inode, entry_nrs[j], &group_offset);
	471	if (!nilfs_clear_bit_atomic(
	472	nilfs_mdt_bgl_lock(inode, group),
	473	group_offset, bitmap)) {
	474	printk(KERN_WARNING
	475	"%s: entry number %llu already freed\n",
	476	__func__,
	477	(unsigned long long)entry_nrs[j]);
	478	}
	479	}
	480	nilfs_palloc_group_desc_add_entries(inode, group, desc, n);
	481
	482	kunmap(bitmap_bh->b_page);
	483	kunmap(desc_bh->b_page);
	484
	485	nilfs_mdt_mark_buffer_dirty(desc_bh);
	486	nilfs_mdt_mark_buffer_dirty(bitmap_bh);
	487	nilfs_mdt_mark_dirty(inode);
	488
	489	brelse(bitmap_bh);
	490	brelse(desc_bh);
	491	}
	492	return 0;
	493	}