[mirror_ubuntu-artful-kernel.git] / fs / ufs / ialloc.c

/*
 *  linux/fs/ufs/ialloc.c
 *
 * Copyright (c) 1998
 * Daniel Pirkl <daniel.pirkl@email.cz>
 * Charles University, Faculty of Mathematics and Physics
 *
 *  from
 *
 *  linux/fs/ext2/ialloc.c
 *
 * Copyright (C) 1992, 1993, 1994, 1995
 * Remy Card (card@masi.ibp.fr)
 * Laboratoire MASI - Institut Blaise Pascal
 * Universite Pierre et Marie Curie (Paris VI)
 *
 *  BSD ufs-inspired inode and directory allocation by 
 *  Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
 *  Big-endian to little-endian byte-swapping/bitmaps by
 *        David S. Miller (davem@caip.rutgers.edu), 1995
 */

#include <linux/fs.h>
#include <linux/ufs_fs.h>
#include <linux/time.h>
#include <linux/stat.h>
#include <linux/string.h>
#include <linux/quotaops.h>
#include <linux/buffer_head.h>
#include <linux/sched.h>
#include <linux/bitops.h>
#include <asm/byteorder.h>

#include "swab.h"
#include "util.h"

#undef UFS_IALLOC_DEBUG

#ifdef UFS_IALLOC_DEBUG
#define UFSD(x) printk("(%s, %d), %s: ", __FILE__, __LINE__, __FUNCTION__); printk x;
#else
#define UFSD(x)
#endif

/*
 * NOTE! When we get the inode, we're the only people
 * that have access to it, and as such there are no
 * race conditions we have to worry about. The inode
 * is not on the hash-lists, and it cannot be reached
 * through the filesystem because the directory entry
 * has been deleted earlier.
 *
 * HOWEVER: we must make sure that we get no aliases,
 * which means that we have to call "clear_inode()"
 * _before_ we mark the inode not in use in the inode
 * bitmaps. Otherwise a newly created file might use
 * the same inode number (not actually the same pointer
 * though), and then we'd have two inodes sharing the
 * same inode number and space on the harddisk.
 */
void ufs_free_inode (struct inode * inode)
{
	struct super_block * sb;
	struct ufs_sb_private_info * uspi;
	struct ufs_super_block_first * usb1;
	struct ufs_cg_private_info * ucpi;
	struct ufs_cylinder_group * ucg;
	int is_directory;
	unsigned ino, cg, bit;
	
	UFSD(("ENTER, ino %lu\n", inode->i_ino))

	sb = inode->i_sb;
	uspi = UFS_SB(sb)->s_uspi;
	usb1 = ubh_get_usb_first(USPI_UBH);
	
	ino = inode->i_ino;

	lock_super (sb);

	if (!((ino > 1) && (ino < (uspi->s_ncg * uspi->s_ipg )))) {
		ufs_warning(sb, "ufs_free_inode", "reserved inode or nonexistent inode %u\n", ino);
		unlock_super (sb);
		return;
	}
	
	cg = ufs_inotocg (ino);
	bit = ufs_inotocgoff (ino);
	ucpi = ufs_load_cylinder (sb, cg);
	if (!ucpi) {
		unlock_super (sb);
		return;
	}
	ucg = ubh_get_ucg(UCPI_UBH);
	if (!ufs_cg_chkmagic(sb, ucg))
		ufs_panic (sb, "ufs_free_fragments", "internal error, bad cg magic number");

	ucg->cg_time = cpu_to_fs32(sb, get_seconds());

	is_directory = S_ISDIR(inode->i_mode);

	DQUOT_FREE_INODE(inode);
	DQUOT_DROP(inode);

	clear_inode (inode);

	if (ubh_isclr (UCPI_UBH, ucpi->c_iusedoff, bit))
		ufs_error(sb, "ufs_free_inode", "bit already cleared for inode %u", ino);
	else {
		ubh_clrbit (UCPI_UBH, ucpi->c_iusedoff, bit);
		if (ino < ucpi->c_irotor)
			ucpi->c_irotor = ino;
		fs32_add(sb, &ucg->cg_cs.cs_nifree, 1);
		fs32_add(sb, &usb1->fs_cstotal.cs_nifree, 1);
		fs32_add(sb, &UFS_SB(sb)->fs_cs(cg).cs_nifree, 1);

		if (is_directory) {
			fs32_sub(sb, &ucg->cg_cs.cs_ndir, 1);
			fs32_sub(sb, &usb1->fs_cstotal.cs_ndir, 1);
			fs32_sub(sb, &UFS_SB(sb)->fs_cs(cg).cs_ndir, 1);
		}
	}

	ubh_mark_buffer_dirty (USPI_UBH);
	ubh_mark_buffer_dirty (UCPI_UBH);
	if (sb->s_flags & MS_SYNCHRONOUS) {
		ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **) &ucpi);
		ubh_wait_on_buffer (UCPI_UBH);
	}
	
	sb->s_dirt = 1;
	unlock_super (sb);
	UFSD(("EXIT\n"))
}

/*
 * There are two policies for allocating an inode.  If the new inode is
 * a directory, then a forward search is made for a block group with both
 * free space and a low directory-to-inode ratio; if that fails, then of
 * the groups with above-average free space, that group with the fewest
 * directories already is chosen.
 *
 * For other inodes, search forward from the parent directory's block
 * group to find a free inode.
 */
struct inode * ufs_new_inode(struct inode * dir, int mode)
{
	struct super_block * sb;
	struct ufs_sb_info * sbi;
	struct ufs_sb_private_info * uspi;
	struct ufs_super_block_first * usb1;
	struct ufs_cg_private_info * ucpi;
	struct ufs_cylinder_group * ucg;
	struct inode * inode;
	unsigned cg, bit, i, j, start;
	struct ufs_inode_info *ufsi;

	UFSD(("ENTER\n"))
	
	/* Cannot create files in a deleted directory */
	if (!dir || !dir->i_nlink)
		return ERR_PTR(-EPERM);
	sb = dir->i_sb;
	inode = new_inode(sb);
	if (!inode)
		return ERR_PTR(-ENOMEM);
	ufsi = UFS_I(inode);
	sbi = UFS_SB(sb);
	uspi = sbi->s_uspi;
	usb1 = ubh_get_usb_first(USPI_UBH);

	lock_super (sb);

	/*
	 * Try to place the inode in its parent directory
	 */
	i = ufs_inotocg(dir->i_ino);
	if (sbi->fs_cs(i).cs_nifree) {
		cg = i;
		goto cg_found;
	}

	/*
	 * Use a quadratic hash to find a group with a free inode
	 */
	for ( j = 1; j < uspi->s_ncg; j <<= 1 ) {
		i += j;
		if (i >= uspi->s_ncg)
			i -= uspi->s_ncg;
		if (sbi->fs_cs(i).cs_nifree) {
			cg = i;
			goto cg_found;
		}
	}

	/*
	 * That failed: try linear search for a free inode
	 */
	i = ufs_inotocg(dir->i_ino) + 1;
	for (j = 2; j < uspi->s_ncg; j++) {
		i++;
		if (i >= uspi->s_ncg)
			i = 0;
		if (sbi->fs_cs(i).cs_nifree) {
			cg = i;
			goto cg_found;
		}
	}
	
	goto failed;

cg_found:
	ucpi = ufs_load_cylinder (sb, cg);
	if (!ucpi)
		goto failed;
	ucg = ubh_get_ucg(UCPI_UBH);
	if (!ufs_cg_chkmagic(sb, ucg)) 
		ufs_panic (sb, "ufs_new_inode", "internal error, bad cg magic number");

	start = ucpi->c_irotor;
	bit = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_iusedoff, uspi->s_ipg, start);
	if (!(bit < uspi->s_ipg)) {
		bit = ubh_find_first_zero_bit (UCPI_UBH, ucpi->c_iusedoff, start);
		if (!(bit < start)) {
			ufs_error (sb, "ufs_new_inode",
			    "cylinder group %u corrupted - error in inode bitmap\n", cg);
			goto failed;
		}
	}
	UFSD(("start = %u, bit = %u, ipg = %u\n", start, bit, uspi->s_ipg))
	if (ubh_isclr (UCPI_UBH, ucpi->c_iusedoff, bit))
		ubh_setbit (UCPI_UBH, ucpi->c_iusedoff, bit);
	else {
		ufs_panic (sb, "ufs_new_inode", "internal error");
		goto failed;
	}
	
	fs32_sub(sb, &ucg->cg_cs.cs_nifree, 1);
	fs32_sub(sb, &usb1->fs_cstotal.cs_nifree, 1);
	fs32_sub(sb, &sbi->fs_cs(cg).cs_nifree, 1);
	
	if (S_ISDIR(mode)) {
		fs32_add(sb, &ucg->cg_cs.cs_ndir, 1);
		fs32_add(sb, &usb1->fs_cstotal.cs_ndir, 1);
		fs32_add(sb, &sbi->fs_cs(cg).cs_ndir, 1);
	}

	ubh_mark_buffer_dirty (USPI_UBH);
	ubh_mark_buffer_dirty (UCPI_UBH);
	if (sb->s_flags & MS_SYNCHRONOUS) {
		ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **) &ucpi);
		ubh_wait_on_buffer (UCPI_UBH);
	}
	sb->s_dirt = 1;

	inode->i_mode = mode;
	inode->i_uid = current->fsuid;
	if (dir->i_mode & S_ISGID) {
		inode->i_gid = dir->i_gid;
		if (S_ISDIR(mode))
			inode->i_mode |= S_ISGID;
	} else
		inode->i_gid = current->fsgid;

	inode->i_ino = cg * uspi->s_ipg + bit;
	inode->i_blksize = PAGE_SIZE;	/* This is the optimal IO size (for stat), not the fs block size */
	inode->i_blocks = 0;
	inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME_SEC;
	ufsi->i_flags = UFS_I(dir)->i_flags;
	ufsi->i_lastfrag = 0;
	ufsi->i_gen = 0;
	ufsi->i_shadow = 0;
	ufsi->i_osync = 0;
	ufsi->i_oeftflag = 0;
	memset(&ufsi->i_u1, 0, sizeof(ufsi->i_u1));

	insert_inode_hash(inode);
	mark_inode_dirty(inode);

	unlock_super (sb);

	if (DQUOT_ALLOC_INODE(inode)) {
		DQUOT_DROP(inode);
		inode->i_flags |= S_NOQUOTA;
		inode->i_nlink = 0;
		iput(inode);
		return ERR_PTR(-EDQUOT);
	}

	UFSD(("allocating inode %lu\n", inode->i_ino))
	UFSD(("EXIT\n"))
	return inode;

failed:
	unlock_super (sb);
	make_bad_inode(inode);
	iput (inode);
	UFSD(("EXIT (FAILED)\n"))
	return ERR_PTR(-ENOSPC);
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/ufs/ialloc.c
	3	*
	4	* Copyright (c) 1998
	5	* Daniel Pirkl <daniel.pirkl@email.cz>
	6	* Charles University, Faculty of Mathematics and Physics
	7	*
	8	* from
	9	*
	10	* linux/fs/ext2/ialloc.c
	11	*
	12	* Copyright (C) 1992, 1993, 1994, 1995
	13	* Remy Card (card@masi.ibp.fr)
	14	* Laboratoire MASI - Institut Blaise Pascal
	15	* Universite Pierre et Marie Curie (Paris VI)
	16	*
	17	* BSD ufs-inspired inode and directory allocation by
	18	* Stephen Tweedie (sct@dcs.ed.ac.uk), 1993
	19	* Big-endian to little-endian byte-swapping/bitmaps by
	20	* David S. Miller (davem@caip.rutgers.edu), 1995
	21	*/
	22
	23	#include <linux/fs.h>
	24	#include <linux/ufs_fs.h>
	25	#include <linux/time.h>
	26	#include <linux/stat.h>
	27	#include <linux/string.h>
	28	#include <linux/quotaops.h>
	29	#include <linux/buffer_head.h>
	30	#include <linux/sched.h>
	31	#include <linux/bitops.h>
	32	#include <asm/byteorder.h>
	33
	34	#include "swab.h"
	35	#include "util.h"
	36
	37	#undef UFS_IALLOC_DEBUG
	38
	39	#ifdef UFS_IALLOC_DEBUG
	40	#define UFSD(x) printk("(%s, %d), %s: ", __FILE__, __LINE__, __FUNCTION__); printk x;
	41	#else
	42	#define UFSD(x)
	43	#endif
	44
	45	/*
	46	* NOTE! When we get the inode, we're the only people
	47	* that have access to it, and as such there are no
	48	* race conditions we have to worry about. The inode
	49	* is not on the hash-lists, and it cannot be reached
	50	* through the filesystem because the directory entry
	51	* has been deleted earlier.
	52	*
	53	* HOWEVER: we must make sure that we get no aliases,
	54	* which means that we have to call "clear_inode()"
	55	* _before_ we mark the inode not in use in the inode
	56	* bitmaps. Otherwise a newly created file might use
	57	* the same inode number (not actually the same pointer
	58	* though), and then we'd have two inodes sharing the
	59	* same inode number and space on the harddisk.
	60	*/
	61	void ufs_free_inode (struct inode * inode)
	62	{
	63	struct super_block * sb;
	64	struct ufs_sb_private_info * uspi;
65	struct ufs_super_block_first * usb1;
66	struct ufs_cg_private_info * ucpi;
67	struct ufs_cylinder_group * ucg;
68	int is_directory;
69	unsigned ino, cg, bit;
70
71	UFSD(("ENTER, ino %lu\n", inode->i_ino))
72
73	sb = inode->i_sb;
74	uspi = UFS_SB(sb)->s_uspi;
75	usb1 = ubh_get_usb_first(USPI_UBH);
76
77	ino = inode->i_ino;
78
79	lock_super (sb);
80
81	if (!((ino > 1) && (ino < (uspi->s_ncg * uspi->s_ipg )))) {
82	ufs_warning(sb, "ufs_free_inode", "reserved inode or nonexistent inode %u\n", ino);
83	unlock_super (sb);
84	return;
85	}
86
87	cg = ufs_inotocg (ino);
88	bit = ufs_inotocgoff (ino);
89	ucpi = ufs_load_cylinder (sb, cg);
90	if (!ucpi) {
91	unlock_super (sb);
92	return;
93	}
94	ucg = ubh_get_ucg(UCPI_UBH);
95	if (!ufs_cg_chkmagic(sb, ucg))
96	ufs_panic (sb, "ufs_free_fragments", "internal error, bad cg magic number");
97
98	ucg->cg_time = cpu_to_fs32(sb, get_seconds());
99
100	is_directory = S_ISDIR(inode->i_mode);
101
102	DQUOT_FREE_INODE(inode);
103	DQUOT_DROP(inode);
104
105	clear_inode (inode);
106
107	if (ubh_isclr (UCPI_UBH, ucpi->c_iusedoff, bit))
108	ufs_error(sb, "ufs_free_inode", "bit already cleared for inode %u", ino);
109	else {
110	ubh_clrbit (UCPI_UBH, ucpi->c_iusedoff, bit);
111	if (ino < ucpi->c_irotor)
112	ucpi->c_irotor = ino;
113	fs32_add(sb, &ucg->cg_cs.cs_nifree, 1);
114	fs32_add(sb, &usb1->fs_cstotal.cs_nifree, 1);
115	fs32_add(sb, &UFS_SB(sb)->fs_cs(cg).cs_nifree, 1);
116
117	if (is_directory) {
118	fs32_sub(sb, &ucg->cg_cs.cs_ndir, 1);
119	fs32_sub(sb, &usb1->fs_cstotal.cs_ndir, 1);
120	fs32_sub(sb, &UFS_SB(sb)->fs_cs(cg).cs_ndir, 1);
121	}
122	}
123
124	ubh_mark_buffer_dirty (USPI_UBH);
125	ubh_mark_buffer_dirty (UCPI_UBH);
126	if (sb->s_flags & MS_SYNCHRONOUS) {
096125f3	127	ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **) &ucpi);
1da177e4 LT	128	ubh_wait_on_buffer (UCPI_UBH);
	129	}
	130
	131	sb->s_dirt = 1;
	132	unlock_super (sb);
	133	UFSD(("EXIT\n"))
	134	}
	135
	136	/*
	137	* There are two policies for allocating an inode. If the new inode is
	138	* a directory, then a forward search is made for a block group with both
	139	* free space and a low directory-to-inode ratio; if that fails, then of
	140	* the groups with above-average free space, that group with the fewest
	141	* directories already is chosen.
	142	*
	143	* For other inodes, search forward from the parent directory's block
	144	* group to find a free inode.
	145	*/
	146	struct inode * ufs_new_inode(struct inode * dir, int mode)
	147	{
	148	struct super_block * sb;
	149	struct ufs_sb_info * sbi;
	150	struct ufs_sb_private_info * uspi;
	151	struct ufs_super_block_first * usb1;
	152	struct ufs_cg_private_info * ucpi;
	153	struct ufs_cylinder_group * ucg;
	154	struct inode * inode;
	155	unsigned cg, bit, i, j, start;
	156	struct ufs_inode_info *ufsi;
	157
	158	UFSD(("ENTER\n"))
	159
	160	/* Cannot create files in a deleted directory */
	161	if (!dir \|\| !dir->i_nlink)
	162	return ERR_PTR(-EPERM);
	163	sb = dir->i_sb;
	164	inode = new_inode(sb);
	165	if (!inode)
	166	return ERR_PTR(-ENOMEM);
	167	ufsi = UFS_I(inode);
	168	sbi = UFS_SB(sb);
	169	uspi = sbi->s_uspi;
	170	usb1 = ubh_get_usb_first(USPI_UBH);
	171
	172	lock_super (sb);
	173
	174	/*
	175	* Try to place the inode in its parent directory
	176	*/
	177	i = ufs_inotocg(dir->i_ino);
	178	if (sbi->fs_cs(i).cs_nifree) {
	179	cg = i;
	180	goto cg_found;
	181	}
	182
	183	/*
	184	* Use a quadratic hash to find a group with a free inode
	185	*/
	186	for ( j = 1; j < uspi->s_ncg; j <<= 1 ) {
	187	i += j;
	188	if (i >= uspi->s_ncg)
	189	i -= uspi->s_ncg;
	190	if (sbi->fs_cs(i).cs_nifree) {
	191	cg = i;
192	goto cg_found;
193	}
194	}
195
196	/*
197	* That failed: try linear search for a free inode
198	*/
199	i = ufs_inotocg(dir->i_ino) + 1;
200	for (j = 2; j < uspi->s_ncg; j++) {
201	i++;
202	if (i >= uspi->s_ncg)
203	i = 0;
204	if (sbi->fs_cs(i).cs_nifree) {
205	cg = i;
206	goto cg_found;
207	}
208	}
209
210	goto failed;
211
212	cg_found:
213	ucpi = ufs_load_cylinder (sb, cg);
214	if (!ucpi)
215	goto failed;
216	ucg = ubh_get_ucg(UCPI_UBH);
217	if (!ufs_cg_chkmagic(sb, ucg))
218	ufs_panic (sb, "ufs_new_inode", "internal error, bad cg magic number");
219
220	start = ucpi->c_irotor;
221	bit = ubh_find_next_zero_bit (UCPI_UBH, ucpi->c_iusedoff, uspi->s_ipg, start);
222	if (!(bit < uspi->s_ipg)) {
223	bit = ubh_find_first_zero_bit (UCPI_UBH, ucpi->c_iusedoff, start);
224	if (!(bit < start)) {
225	ufs_error (sb, "ufs_new_inode",
226	"cylinder group %u corrupted - error in inode bitmap\n", cg);
227	goto failed;
228	}
229	}
230	UFSD(("start = %u, bit = %u, ipg = %u\n", start, bit, uspi->s_ipg))
231	if (ubh_isclr (UCPI_UBH, ucpi->c_iusedoff, bit))
232	ubh_setbit (UCPI_UBH, ucpi->c_iusedoff, bit);
233	else {
234	ufs_panic (sb, "ufs_new_inode", "internal error");
235	goto failed;
236	}
237
238	fs32_sub(sb, &ucg->cg_cs.cs_nifree, 1);
239	fs32_sub(sb, &usb1->fs_cstotal.cs_nifree, 1);
240	fs32_sub(sb, &sbi->fs_cs(cg).cs_nifree, 1);
241
242	if (S_ISDIR(mode)) {
243	fs32_add(sb, &ucg->cg_cs.cs_ndir, 1);
244	fs32_add(sb, &usb1->fs_cstotal.cs_ndir, 1);
245	fs32_add(sb, &sbi->fs_cs(cg).cs_ndir, 1);
246	}
247
248	ubh_mark_buffer_dirty (USPI_UBH);
249	ubh_mark_buffer_dirty (UCPI_UBH);
250	if (sb->s_flags & MS_SYNCHRONOUS) {
096125f3	251	ubh_ll_rw_block (SWRITE, 1, (struct ufs_buffer_head **) &ucpi);
1da177e4 LT	252	ubh_wait_on_buffer (UCPI_UBH);
	253	}
	254	sb->s_dirt = 1;
	255
	256	inode->i_mode = mode;
	257	inode->i_uid = current->fsuid;
	258	if (dir->i_mode & S_ISGID) {
	259	inode->i_gid = dir->i_gid;
	260	if (S_ISDIR(mode))
	261	inode->i_mode \|= S_ISGID;
	262	} else
	263	inode->i_gid = current->fsgid;
	264
	265	inode->i_ino = cg * uspi->s_ipg + bit;
	266	inode->i_blksize = PAGE_SIZE; /* This is the optimal IO size (for stat), not the fs block size */
	267	inode->i_blocks = 0;
	268	inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME_SEC;
	269	ufsi->i_flags = UFS_I(dir)->i_flags;
	270	ufsi->i_lastfrag = 0;
	271	ufsi->i_gen = 0;
	272	ufsi->i_shadow = 0;
	273	ufsi->i_osync = 0;
	274	ufsi->i_oeftflag = 0;
	275	memset(&ufsi->i_u1, 0, sizeof(ufsi->i_u1));
	276
	277	insert_inode_hash(inode);
	278	mark_inode_dirty(inode);
	279
	280	unlock_super (sb);
	281
	282	if (DQUOT_ALLOC_INODE(inode)) {
	283	DQUOT_DROP(inode);
	284	inode->i_flags \|= S_NOQUOTA;
	285	inode->i_nlink = 0;
	286	iput(inode);
	287	return ERR_PTR(-EDQUOT);
	288	}
	289
	290	UFSD(("allocating inode %lu\n", inode->i_ino))
	291	UFSD(("EXIT\n"))
	292	return inode;
	293
	294	failed:
	295	unlock_super (sb);
	296	make_bad_inode(inode);
	297	iput (inode);
	298	UFSD(("EXIT (FAILED)\n"))
	299	return ERR_PTR(-ENOSPC);
	300	}