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

/*
 *  linux/fs/hpfs/alloc.c
 *
 *  Mikulas Patocka ([email protected]), 1998-1999
 *
 *  HPFS bitmap operations
 */

#include "hpfs_fn.h"

/*
 * Check if a sector is allocated in bitmap
 * This is really slow. Turned on only if chk==2
 */

static int chk_if_allocated(struct super_block *s, secno sec, char *msg)
{
	struct quad_buffer_head qbh;
	u32 *bmp;
	if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "chk"))) goto fail;
	if ((cpu_to_le32(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f)) & 1) {
		hpfs_error(s, "sector '%s' - %08x not allocated in bitmap", msg, sec);
		goto fail1;
	}
	hpfs_brelse4(&qbh);
	if (sec >= hpfs_sb(s)->sb_dirband_start && sec < hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
		unsigned ssec = (sec - hpfs_sb(s)->sb_dirband_start) / 4;
		if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto fail;
		if ((le32_to_cpu(bmp[ssec >> 5]) >> (ssec & 0x1f)) & 1) {
			hpfs_error(s, "sector '%s' - %08x not allocated in directory bitmap", msg, sec);
			goto fail1;
		}
		hpfs_brelse4(&qbh);
	}
	return 0;
	fail1:
	hpfs_brelse4(&qbh);
	fail:
	return 1;
}

/*
 * Check if sector(s) have proper number and additionally check if they're
 * allocated in bitmap.
 */
	
int hpfs_chk_sectors(struct super_block *s, secno start, int len, char *msg)
{
	if (start + len < start || start < 0x12 ||
	    start + len > hpfs_sb(s)->sb_fs_size) {
	    	hpfs_error(s, "sector(s) '%s' badly placed at %08x", msg, start);
		return 1;
	}
	if (hpfs_sb(s)->sb_chk>=2) {
		int i;
		for (i = 0; i < len; i++)
			if (chk_if_allocated(s, start + i, msg)) return 1;
	}
	return 0;
}

static secno alloc_in_bmp(struct super_block *s, secno near, unsigned n, unsigned forward)
{
	struct quad_buffer_head qbh;
	unsigned *bmp;
	unsigned bs = near & ~0x3fff;
	unsigned nr = (near & 0x3fff) & ~(n - 1);
	/*unsigned mnr;*/
	unsigned i, q;
	int a, b;
	secno ret = 0;
	if (n != 1 && n != 4) {
		hpfs_error(s, "Bad allocation size: %d", n);
		return 0;
	}
	if (bs != ~0x3fff) {
		if (!(bmp = hpfs_map_bitmap(s, near >> 14, &qbh, "aib"))) goto uls;
	} else {
		if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto uls;
	}
	if (!tstbits(bmp, nr, n + forward)) {
		ret = bs + nr;
		goto rt;
	}
	q = nr + n; b = 0;
	while ((a = tstbits(bmp, q, n + forward)) != 0) {
		q += a;
		if (n != 1) q = ((q-1)&~(n-1))+n;
		if (!b) {
			if (q>>5 != nr>>5) {
				b = 1;
				q = nr & 0x1f;
			}
		} else if (q > nr) break;
	}
	if (!a) {
		ret = bs + q;
		goto rt;
	}
	nr >>= 5;
	/*for (i = nr + 1; i != nr; i++, i &= 0x1ff) */
	i = nr;
	do {
		if (!le32_to_cpu(bmp[i])) goto cont;
		if (n + forward >= 0x3f && le32_to_cpu(bmp[i]) != 0xffffffff) goto cont;
		q = i<<5;
		if (i > 0) {
			unsigned k = le32_to_cpu(bmp[i-1]);
			while (k & 0x80000000) {
				q--; k <<= 1;
			}
		}
		if (n != 1) q = ((q-1)&~(n-1))+n;
		while ((a = tstbits(bmp, q, n + forward)) != 0) {
			q += a;
			if (n != 1) q = ((q-1)&~(n-1))+n;
			if (q>>5 > i) break;
		}
		if (!a) {
			ret = bs + q;
			goto rt;
		}
		cont:
		i++, i &= 0x1ff;
	} while (i != nr);
	rt:
	if (ret) {
		if (hpfs_sb(s)->sb_chk && ((ret >> 14) != (bs >> 14) || (le32_to_cpu(bmp[(ret & 0x3fff) >> 5]) | ~(((1 << n) - 1) << (ret & 0x1f))) != 0xffffffff)) {
			hpfs_error(s, "Allocation doesn't work! Wanted %d, allocated at %08x", n, ret);
			ret = 0;
			goto b;
		}
		bmp[(ret & 0x3fff) >> 5] &= cpu_to_le32(~(((1 << n) - 1) << (ret & 0x1f)));
		hpfs_mark_4buffers_dirty(&qbh);
	}
	b:
	hpfs_brelse4(&qbh);
	uls:
	return ret;
}

/*
 * Allocation strategy:	1) search place near the sector specified
 *			2) search bitmap where free sectors last found
 *			3) search all bitmaps
 *			4) search all bitmaps ignoring number of pre-allocated
 *				sectors
 */

secno hpfs_alloc_sector(struct super_block *s, secno near, unsigned n, int forward)
{
	secno sec;
	int i;
	unsigned n_bmps;
	struct hpfs_sb_info *sbi = hpfs_sb(s);
	int f_p = 0;
	int near_bmp;
	if (forward < 0) {
		forward = -forward;
		f_p = 1;
	}
	n_bmps = (sbi->sb_fs_size + 0x4000 - 1) >> 14;
	if (near && near < sbi->sb_fs_size) {
		if ((sec = alloc_in_bmp(s, near, n, f_p ? forward : forward/4))) goto ret;
		near_bmp = near >> 14;
	} else near_bmp = n_bmps / 2;
	/*
	if (b != -1) {
		if ((sec = alloc_in_bmp(s, b<<14, n, f_p ? forward : forward/2))) {
			b &= 0x0fffffff;
			goto ret;
		}
		if (b > 0x10000000) if ((sec = alloc_in_bmp(s, (b&0xfffffff)<<14, n, f_p ? forward : 0))) goto ret;
	*/
	if (!f_p) if (forward > sbi->sb_max_fwd_alloc) forward = sbi->sb_max_fwd_alloc;
	less_fwd:
	for (i = 0; i < n_bmps; i++) {
		if (near_bmp+i < n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i) << 14, n, forward)))) {
			sbi->sb_c_bitmap = near_bmp+i;
			goto ret;
		}	
		if (!forward) {
			if (near_bmp-i-1 >= 0 && ((sec = alloc_in_bmp(s, (near_bmp-i-1) << 14, n, forward)))) {
				sbi->sb_c_bitmap = near_bmp-i-1;
				goto ret;
			}
		} else {
			if (near_bmp+i >= n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i-n_bmps) << 14, n, forward)))) {
				sbi->sb_c_bitmap = near_bmp+i-n_bmps;
				goto ret;
			}
		}
		if (i == 1 && sbi->sb_c_bitmap != -1 && ((sec = alloc_in_bmp(s, (sbi->sb_c_bitmap) << 14, n, forward)))) {
			goto ret;
		}
	}
	if (!f_p) {
		if (forward) {
			sbi->sb_max_fwd_alloc = forward * 3 / 4;
			forward /= 2;
			goto less_fwd;
		}
	}
	sec = 0;
	ret:
	if (sec && f_p) {
		for (i = 0; i < forward; i++) {
			if (!hpfs_alloc_if_possible(s, sec + i + 1)) {
				hpfs_error(s, "Prealloc doesn't work! Wanted %d, allocated at %08x, can't allocate %d", forward, sec, i);
				sec = 0;
				break;
			}
		}
	}
	return sec;
}

static secno alloc_in_dirband(struct super_block *s, secno near)
{
	unsigned nr = near;
	secno sec;
	struct hpfs_sb_info *sbi = hpfs_sb(s);
	if (nr < sbi->sb_dirband_start)
		nr = sbi->sb_dirband_start;
	if (nr >= sbi->sb_dirband_start + sbi->sb_dirband_size)
		nr = sbi->sb_dirband_start + sbi->sb_dirband_size - 4;
	nr -= sbi->sb_dirband_start;
	nr >>= 2;
	sec = alloc_in_bmp(s, (~0x3fff) | nr, 1, 0);
	if (!sec) return 0;
	return ((sec & 0x3fff) << 2) + sbi->sb_dirband_start;
}

/* Alloc sector if it's free */

int hpfs_alloc_if_possible(struct super_block *s, secno sec)
{
	struct quad_buffer_head qbh;
	u32 *bmp;
	if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "aip"))) goto end;
	if (le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) & (1 << (sec & 0x1f))) {
		bmp[(sec & 0x3fff) >> 5] &= cpu_to_le32(~(1 << (sec & 0x1f)));
		hpfs_mark_4buffers_dirty(&qbh);
		hpfs_brelse4(&qbh);
		return 1;
	}
	hpfs_brelse4(&qbh);
	end:
	return 0;
}

/* Free sectors in bitmaps */

void hpfs_free_sectors(struct super_block *s, secno sec, unsigned n)
{
	struct quad_buffer_head qbh;
	u32 *bmp;
	struct hpfs_sb_info *sbi = hpfs_sb(s);
	/*printk("2 - ");*/
	if (!n) return;
	if (sec < 0x12) {
		hpfs_error(s, "Trying to free reserved sector %08x", sec);
		return;
	}
	sbi->sb_max_fwd_alloc += n > 0xffff ? 0xffff : n;
	if (sbi->sb_max_fwd_alloc > 0xffffff) sbi->sb_max_fwd_alloc = 0xffffff;
	new_map:
	if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "free"))) {
		return;
	}	
	new_tst:
	if ((le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f) & 1)) {
		hpfs_error(s, "sector %08x not allocated", sec);
		hpfs_brelse4(&qbh);
		return;
	}
	bmp[(sec & 0x3fff) >> 5] |= cpu_to_le32(1 << (sec & 0x1f));
	if (!--n) {
		hpfs_mark_4buffers_dirty(&qbh);
		hpfs_brelse4(&qbh);
		return;
	}	
	if (!(++sec & 0x3fff)) {
		hpfs_mark_4buffers_dirty(&qbh);
		hpfs_brelse4(&qbh);
		goto new_map;
	}
	goto new_tst;
}

/*
 * Check if there are at least n free dnodes on the filesystem.
 * Called before adding to dnode. If we run out of space while
 * splitting dnodes, it would corrupt dnode tree.
 */

int hpfs_check_free_dnodes(struct super_block *s, int n)
{
	int n_bmps = (hpfs_sb(s)->sb_fs_size + 0x4000 - 1) >> 14;
	int b = hpfs_sb(s)->sb_c_bitmap & 0x0fffffff;
	int i, j;
	u32 *bmp;
	struct quad_buffer_head qbh;
	if ((bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
		for (j = 0; j < 512; j++) {
			unsigned k;
			if (!le32_to_cpu(bmp[j])) continue;
			for (k = le32_to_cpu(bmp[j]); k; k >>= 1) if (k & 1) if (!--n) {
				hpfs_brelse4(&qbh);
				return 0;
			}
		}
	}
	hpfs_brelse4(&qbh);
	i = 0;
	if (hpfs_sb(s)->sb_c_bitmap != -1) {
		bmp = hpfs_map_bitmap(s, b, &qbh, "chkdn1");
		goto chk_bmp;
	}
	chk_next:
	if (i == b) i++;
	if (i >= n_bmps) return 1;
	bmp = hpfs_map_bitmap(s, i, &qbh, "chkdn2");
	chk_bmp:
	if (bmp) {
		for (j = 0; j < 512; j++) {
			u32 k;
			if (!le32_to_cpu(bmp[j])) continue;
			for (k = 0xf; k; k <<= 4)
				if ((le32_to_cpu(bmp[j]) & k) == k) {
					if (!--n) {
						hpfs_brelse4(&qbh);
						return 0;
					}
				}
		}
		hpfs_brelse4(&qbh);
	}
	i++;
	goto chk_next;
}

void hpfs_free_dnode(struct super_block *s, dnode_secno dno)
{
	if (hpfs_sb(s)->sb_chk) if (dno & 3) {
		hpfs_error(s, "hpfs_free_dnode: dnode %08x not aligned", dno);
		return;
	}
	if (dno < hpfs_sb(s)->sb_dirband_start ||
	    dno >= hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
		hpfs_free_sectors(s, dno, 4);
	} else {
		struct quad_buffer_head qbh;
		u32 *bmp;
		unsigned ssec = (dno - hpfs_sb(s)->sb_dirband_start) / 4;
		if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
			return;
		}
		bmp[ssec >> 5] |= cpu_to_le32(1 << (ssec & 0x1f));
		hpfs_mark_4buffers_dirty(&qbh);
		hpfs_brelse4(&qbh);
	}
}

struct dnode *hpfs_alloc_dnode(struct super_block *s, secno near,
			 dnode_secno *dno, struct quad_buffer_head *qbh)
{
	struct dnode *d;
	if (hpfs_count_one_bitmap(s, hpfs_sb(s)->sb_dmap) > FREE_DNODES_ADD) {
		if (!(*dno = alloc_in_dirband(s, near)))
			if (!(*dno = hpfs_alloc_sector(s, near, 4, 0))) return NULL;
	} else {
		if (!(*dno = hpfs_alloc_sector(s, near, 4, 0)))
			if (!(*dno = alloc_in_dirband(s, near))) return NULL;
	}
	if (!(d = hpfs_get_4sectors(s, *dno, qbh))) {
		hpfs_free_dnode(s, *dno);
		return NULL;
	}
	memset(d, 0, 2048);
	d->magic = cpu_to_le32(DNODE_MAGIC);
	d->first_free = cpu_to_le32(52);
	d->dirent[0] = 32;
	d->dirent[2] = 8;
	d->dirent[30] = 1;
	d->dirent[31] = 255;
	d->self = cpu_to_le32(*dno);
	return d;
}

struct fnode *hpfs_alloc_fnode(struct super_block *s, secno near, fnode_secno *fno,
			  struct buffer_head **bh)
{
	struct fnode *f;
	if (!(*fno = hpfs_alloc_sector(s, near, 1, FNODE_ALLOC_FWD))) return NULL;
	if (!(f = hpfs_get_sector(s, *fno, bh))) {
		hpfs_free_sectors(s, *fno, 1);
		return NULL;
	}	
	memset(f, 0, 512);
	f->magic = cpu_to_le32(FNODE_MAGIC);
	f->ea_offs = cpu_to_le16(0xc4);
	f->btree.n_free_nodes = 8;
	f->btree.first_free = cpu_to_le16(8);
	return f;
}

struct anode *hpfs_alloc_anode(struct super_block *s, secno near, anode_secno *ano,
			  struct buffer_head **bh)
{
	struct anode *a;
	if (!(*ano = hpfs_alloc_sector(s, near, 1, ANODE_ALLOC_FWD))) return NULL;
	if (!(a = hpfs_get_sector(s, *ano, bh))) {
		hpfs_free_sectors(s, *ano, 1);
		return NULL;
	}
	memset(a, 0, 512);
	a->magic = cpu_to_le32(ANODE_MAGIC);
	a->self = cpu_to_le32(*ano);
	a->btree.n_free_nodes = 40;
	a->btree.n_used_nodes = 0;
	a->btree.first_free = cpu_to_le16(8);
	return a;
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/hpfs/alloc.c
	3	*
	4	* Mikulas Patocka ([email protected]), 1998-1999
	5	*
	6	* HPFS bitmap operations
	7	*/
	8
	9	#include "hpfs_fn.h"
	10
1da177e4 LT	11	/*
	12	* Check if a sector is allocated in bitmap
	13	* This is really slow. Turned on only if chk==2
	14	*/
	15
	16	static int chk_if_allocated(struct super_block s, secno sec, char msg)
	17	{
	18	struct quad_buffer_head qbh;
0b69760b	19	u32 *bmp;
1da177e4	20	if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "chk"))) goto fail;
0b69760b	21	if ((cpu_to_le32(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f)) & 1) {
1da177e4 LT	22	hpfs_error(s, "sector '%s' - %08x not allocated in bitmap", msg, sec);
	23	goto fail1;
	24	}
	25	hpfs_brelse4(&qbh);
	26	if (sec >= hpfs_sb(s)->sb_dirband_start && sec < hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
	27	unsigned ssec = (sec - hpfs_sb(s)->sb_dirband_start) / 4;
	28	if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto fail;
0b69760b	29	if ((le32_to_cpu(bmp[ssec >> 5]) >> (ssec & 0x1f)) & 1) {
1da177e4 LT	30	hpfs_error(s, "sector '%s' - %08x not allocated in directory bitmap", msg, sec);
	31	goto fail1;
	32	}
	33	hpfs_brelse4(&qbh);
	34	}
	35	return 0;
	36	fail1:
	37	hpfs_brelse4(&qbh);
	38	fail:
	39	return 1;
	40	}
	41
	42	/*
	43	* Check if sector(s) have proper number and additionally check if they're
	44	* allocated in bitmap.
	45	*/
	46
	47	int hpfs_chk_sectors(struct super_block s, secno start, int len, char msg)
	48	{
	49	if (start + len < start \|\| start < 0x12 \|\|
	50	start + len > hpfs_sb(s)->sb_fs_size) {
	51	hpfs_error(s, "sector(s) '%s' badly placed at %08x", msg, start);
	52	return 1;
	53	}
	54	if (hpfs_sb(s)->sb_chk>=2) {
	55	int i;
	56	for (i = 0; i < len; i++)
	57	if (chk_if_allocated(s, start + i, msg)) return 1;
	58	}
	59	return 0;
	60	}
	61
	62	static secno alloc_in_bmp(struct super_block *s, secno near, unsigned n, unsigned forward)
	63	{
	64	struct quad_buffer_head qbh;
	65	unsigned *bmp;
	66	unsigned bs = near & ~0x3fff;
	67	unsigned nr = (near & 0x3fff) & ~(n - 1);
	68	/unsigned mnr;/
	69	unsigned i, q;
	70	int a, b;
	71	secno ret = 0;
	72	if (n != 1 && n != 4) {
	73	hpfs_error(s, "Bad allocation size: %d", n);
	74	return 0;
	75	}
1da177e4 LT	76	if (bs != ~0x3fff) {
	77	if (!(bmp = hpfs_map_bitmap(s, near >> 14, &qbh, "aib"))) goto uls;
	78	} else {
	79	if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto uls;
	80	}
	81	if (!tstbits(bmp, nr, n + forward)) {
	82	ret = bs + nr;
	83	goto rt;
	84	}
1da177e4 LT	85	q = nr + n; b = 0;
	86	while ((a = tstbits(bmp, q, n + forward)) != 0) {
	87	q += a;
	88	if (n != 1) q = ((q-1)&~(n-1))+n;
	89	if (!b) {
	90	if (q>>5 != nr>>5) {
	91	b = 1;
	92	q = nr & 0x1f;
	93	}
	94	} else if (q > nr) break;
	95	}
	96	if (!a) {
	97	ret = bs + q;
	98	goto rt;
	99	}
	100	nr >>= 5;
0b69760b	101	/for (i = nr + 1; i != nr; i++, i &= 0x1ff) /
1da177e4 LT	102	i = nr;
1da177e4 LT	103	do {
0b69760b MP	104	if (!le32_to_cpu(bmp[i])) goto cont;
0b69760b MP	105	if (n + forward >= 0x3f && le32_to_cpu(bmp[i]) != 0xffffffff) goto cont;
1da177e4 LT	106	q = i<<5;
1da177e4 LT	107	if (i > 0) {
0b69760b	108	unsigned k = le32_to_cpu(bmp[i-1]);
1da177e4 LT	109	while (k & 0x80000000) {
	110	q--; k <<= 1;
	111	}
	112	}
	113	if (n != 1) q = ((q-1)&~(n-1))+n;
	114	while ((a = tstbits(bmp, q, n + forward)) != 0) {
	115	q += a;
	116	if (n != 1) q = ((q-1)&~(n-1))+n;
	117	if (q>>5 > i) break;
	118	}
	119	if (!a) {
	120	ret = bs + q;
	121	goto rt;
	122	}
	123	cont:
	124	i++, i &= 0x1ff;
	125	} while (i != nr);
	126	rt:
	127	if (ret) {
0b69760b	128	if (hpfs_sb(s)->sb_chk && ((ret >> 14) != (bs >> 14) \|\| (le32_to_cpu(bmp[(ret & 0x3fff) >> 5]) \| ~(((1 << n) - 1) << (ret & 0x1f))) != 0xffffffff)) {
1da177e4 LT	129	hpfs_error(s, "Allocation doesn't work! Wanted %d, allocated at %08x", n, ret);
	130	ret = 0;
	131	goto b;
	132	}
0b69760b	133	bmp[(ret & 0x3fff) >> 5] &= cpu_to_le32(~(((1 << n) - 1) << (ret & 0x1f)));
1da177e4 LT	134	hpfs_mark_4buffers_dirty(&qbh);
	135	}
	136	b:
	137	hpfs_brelse4(&qbh);
	138	uls:
1da177e4 LT	139	return ret;
	140	}
	141
	142	/*
	143	* Allocation strategy: 1) search place near the sector specified
	144	* 2) search bitmap where free sectors last found
	145	* 3) search all bitmaps
	146	* 4) search all bitmaps ignoring number of pre-allocated
	147	* sectors
	148	*/
	149
7d23ce36	150	secno hpfs_alloc_sector(struct super_block *s, secno near, unsigned n, int forward)
1da177e4 LT	151	{
	152	secno sec;
	153	int i;
	154	unsigned n_bmps;
	155	struct hpfs_sb_info *sbi = hpfs_sb(s);
	156	int f_p = 0;
	157	int near_bmp;
	158	if (forward < 0) {
	159	forward = -forward;
	160	f_p = 1;
	161	}
1da177e4 LT	162	n_bmps = (sbi->sb_fs_size + 0x4000 - 1) >> 14;
	163	if (near && near < sbi->sb_fs_size) {
	164	if ((sec = alloc_in_bmp(s, near, n, f_p ? forward : forward/4))) goto ret;
	165	near_bmp = near >> 14;
	166	} else near_bmp = n_bmps / 2;
	167	/*
	168	if (b != -1) {
	169	if ((sec = alloc_in_bmp(s, b<<14, n, f_p ? forward : forward/2))) {
	170	b &= 0x0fffffff;
	171	goto ret;
	172	}
	173	if (b > 0x10000000) if ((sec = alloc_in_bmp(s, (b&0xfffffff)<<14, n, f_p ? forward : 0))) goto ret;
	174	*/
	175	if (!f_p) if (forward > sbi->sb_max_fwd_alloc) forward = sbi->sb_max_fwd_alloc;
	176	less_fwd:
	177	for (i = 0; i < n_bmps; i++) {
	178	if (near_bmp+i < n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i) << 14, n, forward)))) {
	179	sbi->sb_c_bitmap = near_bmp+i;
	180	goto ret;
	181	}
	182	if (!forward) {
	183	if (near_bmp-i-1 >= 0 && ((sec = alloc_in_bmp(s, (near_bmp-i-1) << 14, n, forward)))) {
	184	sbi->sb_c_bitmap = near_bmp-i-1;
	185	goto ret;
	186	}
	187	} else {
	188	if (near_bmp+i >= n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i-n_bmps) << 14, n, forward)))) {
	189	sbi->sb_c_bitmap = near_bmp+i-n_bmps;
	190	goto ret;
	191	}
	192	}
	193	if (i == 1 && sbi->sb_c_bitmap != -1 && ((sec = alloc_in_bmp(s, (sbi->sb_c_bitmap) << 14, n, forward)))) {
	194	goto ret;
	195	}
	196	}
	197	if (!f_p) {
	198	if (forward) {
	199	sbi->sb_max_fwd_alloc = forward * 3 / 4;
	200	forward /= 2;
	201	goto less_fwd;
	202	}
	203	}
	204	sec = 0;
	205	ret:
	206	if (sec && f_p) {
	207	for (i = 0; i < forward; i++) {
7d23ce36	208	if (!hpfs_alloc_if_possible(s, sec + i + 1)) {
1da177e4 LT	209	hpfs_error(s, "Prealloc doesn't work! Wanted %d, allocated at %08x, can't allocate %d", forward, sec, i);
	210	sec = 0;
	211	break;
	212	}
	213	}
	214	}
1da177e4 LT	215	return sec;
	216	}
	217
7d23ce36	218	static secno alloc_in_dirband(struct super_block *s, secno near)
1da177e4 LT	219	{
	220	unsigned nr = near;
	221	secno sec;
	222	struct hpfs_sb_info *sbi = hpfs_sb(s);
	223	if (nr < sbi->sb_dirband_start)
	224	nr = sbi->sb_dirband_start;
	225	if (nr >= sbi->sb_dirband_start + sbi->sb_dirband_size)
	226	nr = sbi->sb_dirband_start + sbi->sb_dirband_size - 4;
	227	nr -= sbi->sb_dirband_start;
	228	nr >>= 2;
1da177e4	229	sec = alloc_in_bmp(s, (~0x3fff) \| nr, 1, 0);
1da177e4 LT	230	if (!sec) return 0;
	231	return ((sec & 0x3fff) << 2) + sbi->sb_dirband_start;
	232	}
	233
	234	/* Alloc sector if it's free */
	235
7d23ce36	236	int hpfs_alloc_if_possible(struct super_block *s, secno sec)
1da177e4 LT	237	{
1da177e4 LT	238	struct quad_buffer_head qbh;
0b69760b	239	u32 *bmp;
1da177e4	240	if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "aip"))) goto end;
0b69760b MP	241	if (le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) & (1 << (sec & 0x1f))) {
0b69760b MP	242	bmp[(sec & 0x3fff) >> 5] &= cpu_to_le32(~(1 << (sec & 0x1f)));
1da177e4 LT	243	hpfs_mark_4buffers_dirty(&qbh);
1da177e4 LT	244	hpfs_brelse4(&qbh);
1da177e4 LT	245	return 1;
	246	}
	247	hpfs_brelse4(&qbh);
	248	end:
1da177e4 LT	249	return 0;
	250	}
	251
1da177e4 LT	252	/* Free sectors in bitmaps */
	253
	254	void hpfs_free_sectors(struct super_block *s, secno sec, unsigned n)
	255	{
	256	struct quad_buffer_head qbh;
0b69760b	257	u32 *bmp;
1da177e4 LT	258	struct hpfs_sb_info *sbi = hpfs_sb(s);
	259	/printk("2 - ");/
	260	if (!n) return;
	261	if (sec < 0x12) {
	262	hpfs_error(s, "Trying to free reserved sector %08x", sec);
	263	return;
	264	}
1da177e4 LT	265	sbi->sb_max_fwd_alloc += n > 0xffff ? 0xffff : n;
	266	if (sbi->sb_max_fwd_alloc > 0xffffff) sbi->sb_max_fwd_alloc = 0xffffff;
	267	new_map:
	268	if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "free"))) {
1da177e4 LT	269	return;
	270	}
	271	new_tst:
0b69760b	272	if ((le32_to_cpu(bmp[(sec & 0x3fff) >> 5]) >> (sec & 0x1f) & 1)) {
1da177e4 LT	273	hpfs_error(s, "sector %08x not allocated", sec);
1da177e4 LT	274	hpfs_brelse4(&qbh);
1da177e4 LT	275	return;
1da177e4 LT	276	}
0b69760b	277	bmp[(sec & 0x3fff) >> 5] \|= cpu_to_le32(1 << (sec & 0x1f));
1da177e4 LT	278	if (!--n) {
	279	hpfs_mark_4buffers_dirty(&qbh);
	280	hpfs_brelse4(&qbh);
1da177e4 LT	281	return;
	282	}
	283	if (!(++sec & 0x3fff)) {
	284	hpfs_mark_4buffers_dirty(&qbh);
	285	hpfs_brelse4(&qbh);
	286	goto new_map;
	287	}
	288	goto new_tst;
	289	}
	290
	291	/*
	292	* Check if there are at least n free dnodes on the filesystem.
	293	* Called before adding to dnode. If we run out of space while
	294	* splitting dnodes, it would corrupt dnode tree.
	295	*/
	296
	297	int hpfs_check_free_dnodes(struct super_block *s, int n)
	298	{
	299	int n_bmps = (hpfs_sb(s)->sb_fs_size + 0x4000 - 1) >> 14;
	300	int b = hpfs_sb(s)->sb_c_bitmap & 0x0fffffff;
	301	int i, j;
0b69760b	302	u32 *bmp;
1da177e4 LT	303	struct quad_buffer_head qbh;
	304	if ((bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
	305	for (j = 0; j < 512; j++) {
	306	unsigned k;
0b69760b MP	307	if (!le32_to_cpu(bmp[j])) continue;
0b69760b MP	308	for (k = le32_to_cpu(bmp[j]); k; k >>= 1) if (k & 1) if (!--n) {
1da177e4 LT	309	hpfs_brelse4(&qbh);
	310	return 0;
	311	}
	312	}
	313	}
	314	hpfs_brelse4(&qbh);
	315	i = 0;
	316	if (hpfs_sb(s)->sb_c_bitmap != -1) {
	317	bmp = hpfs_map_bitmap(s, b, &qbh, "chkdn1");
	318	goto chk_bmp;
	319	}
	320	chk_next:
	321	if (i == b) i++;
	322	if (i >= n_bmps) return 1;
	323	bmp = hpfs_map_bitmap(s, i, &qbh, "chkdn2");
	324	chk_bmp:
	325	if (bmp) {
	326	for (j = 0; j < 512; j++) {
0b69760b MP	327	u32 k;
0b69760b MP	328	if (!le32_to_cpu(bmp[j])) continue;
1da177e4	329	for (k = 0xf; k; k <<= 4)
0b69760b	330	if ((le32_to_cpu(bmp[j]) & k) == k) {
1da177e4 LT	331	if (!--n) {
	332	hpfs_brelse4(&qbh);
	333	return 0;
	334	}
	335	}
	336	}
	337	hpfs_brelse4(&qbh);
	338	}
	339	i++;
	340	goto chk_next;
	341	}
	342
	343	void hpfs_free_dnode(struct super_block *s, dnode_secno dno)
	344	{
	345	if (hpfs_sb(s)->sb_chk) if (dno & 3) {
	346	hpfs_error(s, "hpfs_free_dnode: dnode %08x not aligned", dno);
	347	return;
	348	}
	349	if (dno < hpfs_sb(s)->sb_dirband_start \|\|
	350	dno >= hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
	351	hpfs_free_sectors(s, dno, 4);
	352	} else {
	353	struct quad_buffer_head qbh;
0b69760b	354	u32 *bmp;
1da177e4	355	unsigned ssec = (dno - hpfs_sb(s)->sb_dirband_start) / 4;
1da177e4	356	if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
1da177e4 LT	357	return;
1da177e4 LT	358	}
0b69760b	359	bmp[ssec >> 5] \|= cpu_to_le32(1 << (ssec & 0x1f));
1da177e4 LT	360	hpfs_mark_4buffers_dirty(&qbh);
1da177e4 LT	361	hpfs_brelse4(&qbh);
1da177e4 LT	362	}
	363	}
	364
	365	struct dnode hpfs_alloc_dnode(struct super_block s, secno near,
7d23ce36	366	dnode_secno dno, struct quad_buffer_head qbh)
1da177e4 LT	367	{
	368	struct dnode *d;
	369	if (hpfs_count_one_bitmap(s, hpfs_sb(s)->sb_dmap) > FREE_DNODES_ADD) {
7d23ce36 MP	370	if (!(*dno = alloc_in_dirband(s, near)))
7d23ce36 MP	371	if (!(*dno = hpfs_alloc_sector(s, near, 4, 0))) return NULL;
1da177e4	372	} else {
7d23ce36 MP	373	if (!(*dno = hpfs_alloc_sector(s, near, 4, 0)))
7d23ce36 MP	374	if (!(*dno = alloc_in_dirband(s, near))) return NULL;
1da177e4 LT	375	}
	376	if (!(d = hpfs_get_4sectors(s, *dno, qbh))) {
	377	hpfs_free_dnode(s, *dno);
	378	return NULL;
	379	}
	380	memset(d, 0, 2048);
0b69760b MP	381	d->magic = cpu_to_le32(DNODE_MAGIC);
0b69760b MP	382	d->first_free = cpu_to_le32(52);
1da177e4 LT	383	d->dirent[0] = 32;
	384	d->dirent[2] = 8;
	385	d->dirent[30] = 1;
	386	d->dirent[31] = 255;
0b69760b	387	d->self = cpu_to_le32(*dno);
1da177e4 LT	388	return d;
	389	}
	390
	391	struct fnode hpfs_alloc_fnode(struct super_block s, secno near, fnode_secno *fno,
	392	struct buffer_head **bh)
	393	{
	394	struct fnode *f;
7d23ce36	395	if (!(*fno = hpfs_alloc_sector(s, near, 1, FNODE_ALLOC_FWD))) return NULL;
1da177e4 LT	396	if (!(f = hpfs_get_sector(s, *fno, bh))) {
	397	hpfs_free_sectors(s, *fno, 1);
	398	return NULL;
	399	}
	400	memset(f, 0, 512);
0b69760b MP	401	f->magic = cpu_to_le32(FNODE_MAGIC);
0b69760b MP	402	f->ea_offs = cpu_to_le16(0xc4);
1da177e4	403	f->btree.n_free_nodes = 8;
0b69760b	404	f->btree.first_free = cpu_to_le16(8);
1da177e4 LT	405	return f;
	406	}
	407
	408	struct anode hpfs_alloc_anode(struct super_block s, secno near, anode_secno *ano,
	409	struct buffer_head **bh)
	410	{
	411	struct anode *a;
7d23ce36	412	if (!(*ano = hpfs_alloc_sector(s, near, 1, ANODE_ALLOC_FWD))) return NULL;
1da177e4 LT	413	if (!(a = hpfs_get_sector(s, *ano, bh))) {
	414	hpfs_free_sectors(s, *ano, 1);
	415	return NULL;
	416	}
	417	memset(a, 0, 512);
0b69760b MP	418	a->magic = cpu_to_le32(ANODE_MAGIC);
0b69760b MP	419	a->self = cpu_to_le32(*ano);
1da177e4 LT	420	a->btree.n_free_nodes = 40;
1da177e4 LT	421	a->btree.n_used_nodes = 0;
0b69760b	422	a->btree.first_free = cpu_to_le16(8);
1da177e4 LT	423	return a;
1da177e4 LT	424	}