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

/*
 *  linux/fs/hpfs/anode.c
 *
 *  Mikulas Patocka ([email protected]), 1998-1999
 *
 *  handling HPFS anode tree that contains file allocation info
 */

#include "hpfs_fn.h"

/* Find a sector in allocation tree */

secno hpfs_bplus_lookup(struct super_block *s, struct inode *inode,
		   struct bplus_header *btree, unsigned sec,
		   struct buffer_head *bh)
{
	anode_secno a = -1;
	struct anode *anode;
	int i;
	int c1, c2 = 0;
	go_down:
	if (hpfs_sb(s)->sb_chk) if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_bplus_lookup")) return -1;
	if (btree->internal) {
		for (i = 0; i < btree->n_used_nodes; i++)
			if (btree->u.internal[i].file_secno > sec) {
				a = btree->u.internal[i].down;
				brelse(bh);
				if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
				btree = &anode->btree;
				goto go_down;
			}
		hpfs_error(s, "sector %08x not found in internal anode %08x", sec, a);
		brelse(bh);
		return -1;
	}
	for (i = 0; i < btree->n_used_nodes; i++)
		if (btree->u.external[i].file_secno <= sec &&
		    btree->u.external[i].file_secno + btree->u.external[i].length > sec) {
			a = btree->u.external[i].disk_secno + sec - btree->u.external[i].file_secno;
			if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, a, 1, "data")) {
				brelse(bh);
				return -1;
			}
			if (inode) {
				struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
				hpfs_inode->i_file_sec = btree->u.external[i].file_secno;
				hpfs_inode->i_disk_sec = btree->u.external[i].disk_secno;
				hpfs_inode->i_n_secs = btree->u.external[i].length;
			}
			brelse(bh);
			return a;
		}
	hpfs_error(s, "sector %08x not found in external anode %08x", sec, a);
	brelse(bh);
	return -1;
}

/* Add a sector to tree */

secno hpfs_add_sector_to_btree(struct super_block *s, secno node, int fnod, unsigned fsecno)
{
	struct bplus_header *btree;
	struct anode *anode = NULL, *ranode = NULL;
	struct fnode *fnode;
	anode_secno a, na = -1, ra, up = -1;
	secno se;
	struct buffer_head *bh, *bh1, *bh2;
	int n;
	unsigned fs;
	int c1, c2 = 0;
	if (fnod) {
		if (!(fnode = hpfs_map_fnode(s, node, &bh))) return -1;
		btree = &fnode->btree;
	} else {
		if (!(anode = hpfs_map_anode(s, node, &bh))) return -1;
		btree = &anode->btree;
	}
	a = node;
	go_down:
	if ((n = btree->n_used_nodes - 1) < -!!fnod) {
		hpfs_error(s, "anode %08x has no entries", a);
		brelse(bh);
		return -1;
	}
	if (btree->internal) {
		a = btree->u.internal[n].down;
		btree->u.internal[n].file_secno = -1;
		mark_buffer_dirty(bh);
		brelse(bh);
		if (hpfs_sb(s)->sb_chk)
			if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_add_sector_to_btree #1")) return -1;
		if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
		btree = &anode->btree;
		goto go_down;
	}
	if (n >= 0) {
		if (btree->u.external[n].file_secno + btree->u.external[n].length != fsecno) {
			hpfs_error(s, "allocated size %08x, trying to add sector %08x, %cnode %08x",
				btree->u.external[n].file_secno + btree->u.external[n].length, fsecno,
				fnod?'f':'a', node);
			brelse(bh);
			return -1;
		}
		if (hpfs_alloc_if_possible(s, se = btree->u.external[n].disk_secno + btree->u.external[n].length)) {
			btree->u.external[n].length++;
			mark_buffer_dirty(bh);
			brelse(bh);
			return se;
		}
	} else {
		if (fsecno) {
			hpfs_error(s, "empty file %08x, trying to add sector %08x", node, fsecno);
			brelse(bh);
			return -1;
		}
		se = !fnod ? node : (node + 16384) & ~16383;
	}	
	if (!(se = hpfs_alloc_sector(s, se, 1, fsecno*ALLOC_M>ALLOC_FWD_MAX ? ALLOC_FWD_MAX : fsecno*ALLOC_M<ALLOC_FWD_MIN ? ALLOC_FWD_MIN : fsecno*ALLOC_M, 1))) {
		brelse(bh);
		return -1;
	}
	fs = n < 0 ? 0 : btree->u.external[n].file_secno + btree->u.external[n].length;
	if (!btree->n_free_nodes) {
		up = a != node ? anode->up : -1;
		if (!(anode = hpfs_alloc_anode(s, a, &na, &bh1))) {
			brelse(bh);
			hpfs_free_sectors(s, se, 1);
			return -1;
		}
		if (a == node && fnod) {
			anode->up = node;
			anode->btree.fnode_parent = 1;
			anode->btree.n_used_nodes = btree->n_used_nodes;
			anode->btree.first_free = btree->first_free;
			anode->btree.n_free_nodes = 40 - anode->btree.n_used_nodes;
			memcpy(&anode->u, &btree->u, btree->n_used_nodes * 12);
			btree->internal = 1;
			btree->n_free_nodes = 11;
			btree->n_used_nodes = 1;
			btree->first_free = (char *)&(btree->u.internal[1]) - (char *)btree;
			btree->u.internal[0].file_secno = -1;
			btree->u.internal[0].down = na;
			mark_buffer_dirty(bh);
		} else if (!(ranode = hpfs_alloc_anode(s, /*a*/0, &ra, &bh2))) {
			brelse(bh);
			brelse(bh1);
			hpfs_free_sectors(s, se, 1);
			hpfs_free_sectors(s, na, 1);
			return -1;
		}
		brelse(bh);
		bh = bh1;
		btree = &anode->btree;
	}
	btree->n_free_nodes--; n = btree->n_used_nodes++;
	btree->first_free += 12;
	btree->u.external[n].disk_secno = se;
	btree->u.external[n].file_secno = fs;
	btree->u.external[n].length = 1;
	mark_buffer_dirty(bh);
	brelse(bh);
	if ((a == node && fnod) || na == -1) return se;
	c2 = 0;
	while (up != -1) {
		struct anode *new_anode;
		if (hpfs_sb(s)->sb_chk)
			if (hpfs_stop_cycles(s, up, &c1, &c2, "hpfs_add_sector_to_btree #2")) return -1;
		if (up != node || !fnod) {
			if (!(anode = hpfs_map_anode(s, up, &bh))) return -1;
			btree = &anode->btree;
		} else {
			if (!(fnode = hpfs_map_fnode(s, up, &bh))) return -1;
			btree = &fnode->btree;
		}
		if (btree->n_free_nodes) {
			btree->n_free_nodes--; n = btree->n_used_nodes++;
			btree->first_free += 8;
			btree->u.internal[n].file_secno = -1;
			btree->u.internal[n].down = na;
			btree->u.internal[n-1].file_secno = fs;
			mark_buffer_dirty(bh);
			brelse(bh);
			brelse(bh2);
			hpfs_free_sectors(s, ra, 1);
			if ((anode = hpfs_map_anode(s, na, &bh))) {
				anode->up = up;
				anode->btree.fnode_parent = up == node && fnod;
				mark_buffer_dirty(bh);
				brelse(bh);
			}
			return se;
		}
		up = up != node ? anode->up : -1;
		btree->u.internal[btree->n_used_nodes - 1].file_secno = /*fs*/-1;
		mark_buffer_dirty(bh);
		brelse(bh);
		a = na;
		if ((new_anode = hpfs_alloc_anode(s, a, &na, &bh))) {
			anode = new_anode;
			/*anode->up = up != -1 ? up : ra;*/
			anode->btree.internal = 1;
			anode->btree.n_used_nodes = 1;
			anode->btree.n_free_nodes = 59;
			anode->btree.first_free = 16;
			anode->btree.u.internal[0].down = a;
			anode->btree.u.internal[0].file_secno = -1;
			mark_buffer_dirty(bh);
			brelse(bh);
			if ((anode = hpfs_map_anode(s, a, &bh))) {
				anode->up = na;
				mark_buffer_dirty(bh);
				brelse(bh);
			}
		} else na = a;
	}
	if ((anode = hpfs_map_anode(s, na, &bh))) {
		anode->up = node;
		if (fnod) anode->btree.fnode_parent = 1;
		mark_buffer_dirty(bh);
		brelse(bh);
	}
	if (!fnod) {
		if (!(anode = hpfs_map_anode(s, node, &bh))) {
			brelse(bh2);
			return -1;
		}
		btree = &anode->btree;
	} else {
		if (!(fnode = hpfs_map_fnode(s, node, &bh))) {
			brelse(bh2);
			return -1;
		}
		btree = &fnode->btree;
	}
	ranode->up = node;
	memcpy(&ranode->btree, btree, btree->first_free);
	if (fnod) ranode->btree.fnode_parent = 1;
	ranode->btree.n_free_nodes = (ranode->btree.internal ? 60 : 40) - ranode->btree.n_used_nodes;
	if (ranode->btree.internal) for (n = 0; n < ranode->btree.n_used_nodes; n++) {
		struct anode *unode;
		if ((unode = hpfs_map_anode(s, ranode->u.internal[n].down, &bh1))) {
			unode->up = ra;
			unode->btree.fnode_parent = 0;
			mark_buffer_dirty(bh1);
			brelse(bh1);
		}
	}
	btree->internal = 1;
	btree->n_free_nodes = fnod ? 10 : 58;
	btree->n_used_nodes = 2;
	btree->first_free = (char *)&btree->u.internal[2] - (char *)btree;
	btree->u.internal[0].file_secno = fs;
	btree->u.internal[0].down = ra;
	btree->u.internal[1].file_secno = -1;
	btree->u.internal[1].down = na;
	mark_buffer_dirty(bh);
	brelse(bh);
	mark_buffer_dirty(bh2);
	brelse(bh2);
	return se;
}

/*
 * Remove allocation tree. Recursion would look much nicer but
 * I want to avoid it because it can cause stack overflow.
 */

void hpfs_remove_btree(struct super_block *s, struct bplus_header *btree)
{
	struct bplus_header *btree1 = btree;
	struct anode *anode = NULL;
	anode_secno ano = 0, oano;
	struct buffer_head *bh;
	int level = 0;
	int pos = 0;
	int i;
	int c1, c2 = 0;
	int d1, d2;
	go_down:
	d2 = 0;
	while (btree1->internal) {
		ano = btree1->u.internal[pos].down;
		if (level) brelse(bh);
		if (hpfs_sb(s)->sb_chk)
			if (hpfs_stop_cycles(s, ano, &d1, &d2, "hpfs_remove_btree #1"))
				return;
		if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
		btree1 = &anode->btree;
		level++;
		pos = 0;
	}
	for (i = 0; i < btree1->n_used_nodes; i++)
		hpfs_free_sectors(s, btree1->u.external[i].disk_secno, btree1->u.external[i].length);
	go_up:
	if (!level) return;
	brelse(bh);
	if (hpfs_sb(s)->sb_chk)
		if (hpfs_stop_cycles(s, ano, &c1, &c2, "hpfs_remove_btree #2")) return;
	hpfs_free_sectors(s, ano, 1);
	oano = ano;
	ano = anode->up;
	if (--level) {
		if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
		btree1 = &anode->btree;
	} else btree1 = btree;
	for (i = 0; i < btree1->n_used_nodes; i++) {
		if (btree1->u.internal[i].down == oano) {
			if ((pos = i + 1) < btree1->n_used_nodes)
				goto go_down;
			else
				goto go_up;
		}
	}
	hpfs_error(s,
		   "reference to anode %08x not found in anode %08x "
		   "(probably bad up pointer)",
		   oano, level ? ano : -1);
	if (level)
		brelse(bh);
}

/* Just a wrapper around hpfs_bplus_lookup .. used for reading eas */

static secno anode_lookup(struct super_block *s, anode_secno a, unsigned sec)
{
	struct anode *anode;
	struct buffer_head *bh;
	if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
	return hpfs_bplus_lookup(s, NULL, &anode->btree, sec, bh);
}

int hpfs_ea_read(struct super_block *s, secno a, int ano, unsigned pos,
	    unsigned len, char *buf)
{
	struct buffer_head *bh;
	char *data;
	secno sec;
	unsigned l;
	while (len) {
		if (ano) {
			if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
				return -1;
		} else sec = a + (pos >> 9);
		if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #1")) return -1;
		if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
			return -1;
		l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
		memcpy(buf, data + (pos & 0x1ff), l);
		brelse(bh);
		buf += l; pos += l; len -= l;
	}
	return 0;
}

int hpfs_ea_write(struct super_block *s, secno a, int ano, unsigned pos,
	     unsigned len, char *buf)
{
	struct buffer_head *bh;
	char *data;
	secno sec;
	unsigned l;
	while (len) {
		if (ano) {
			if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
				return -1;
		} else sec = a + (pos >> 9);
		if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #2")) return -1;
		if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
			return -1;
		l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
		memcpy(data + (pos & 0x1ff), buf, l);
		mark_buffer_dirty(bh);
		brelse(bh);
		buf += l; pos += l; len -= l;
	}
	return 0;
}

void hpfs_ea_remove(struct super_block *s, secno a, int ano, unsigned len)
{
	struct anode *anode;
	struct buffer_head *bh;
	if (ano) {
		if (!(anode = hpfs_map_anode(s, a, &bh))) return;
		hpfs_remove_btree(s, &anode->btree);
		brelse(bh);
		hpfs_free_sectors(s, a, 1);
	} else hpfs_free_sectors(s, a, (len + 511) >> 9);
}

/* Truncate allocation tree. Doesn't join anodes - I hope it doesn't matter */

void hpfs_truncate_btree(struct super_block *s, secno f, int fno, unsigned secs)
{
	struct fnode *fnode;
	struct anode *anode;
	struct buffer_head *bh;
	struct bplus_header *btree;
	anode_secno node = f;
	int i, j, nodes;
	int c1, c2 = 0;
	if (fno) {
		if (!(fnode = hpfs_map_fnode(s, f, &bh))) return;
		btree = &fnode->btree;
	} else {
		if (!(anode = hpfs_map_anode(s, f, &bh))) return;
		btree = &anode->btree;
	}
	if (!secs) {
		hpfs_remove_btree(s, btree);
		if (fno) {
			btree->n_free_nodes = 8;
			btree->n_used_nodes = 0;
			btree->first_free = 8;
			btree->internal = 0;
			mark_buffer_dirty(bh);
		} else hpfs_free_sectors(s, f, 1);
		brelse(bh);
		return;
	}
	while (btree->internal) {
		nodes = btree->n_used_nodes + btree->n_free_nodes;
		for (i = 0; i < btree->n_used_nodes; i++)
			if (btree->u.internal[i].file_secno >= secs) goto f;
		brelse(bh);
		hpfs_error(s, "internal btree %08x doesn't end with -1", node);
		return;
		f:
		for (j = i + 1; j < btree->n_used_nodes; j++)
			hpfs_ea_remove(s, btree->u.internal[j].down, 1, 0);
		btree->n_used_nodes = i + 1;
		btree->n_free_nodes = nodes - btree->n_used_nodes;
		btree->first_free = 8 + 8 * btree->n_used_nodes;
		mark_buffer_dirty(bh);
		if (btree->u.internal[i].file_secno == secs) {
			brelse(bh);
			return;
		}
		node = btree->u.internal[i].down;
		brelse(bh);
		if (hpfs_sb(s)->sb_chk)
			if (hpfs_stop_cycles(s, node, &c1, &c2, "hpfs_truncate_btree"))
				return;
		if (!(anode = hpfs_map_anode(s, node, &bh))) return;
		btree = &anode->btree;
	}	
	nodes = btree->n_used_nodes + btree->n_free_nodes;
	for (i = 0; i < btree->n_used_nodes; i++)
		if (btree->u.external[i].file_secno + btree->u.external[i].length >= secs) goto ff;
	brelse(bh);
	return;
	ff:
	if (secs <= btree->u.external[i].file_secno) {
		hpfs_error(s, "there is an allocation error in file %08x, sector %08x", f, secs);
		if (i) i--;
	}
	else if (btree->u.external[i].file_secno + btree->u.external[i].length > secs) {
		hpfs_free_sectors(s, btree->u.external[i].disk_secno + secs -
			btree->u.external[i].file_secno, btree->u.external[i].length
			- secs + btree->u.external[i].file_secno); /* I hope gcc optimizes this :-) */
		btree->u.external[i].length = secs - btree->u.external[i].file_secno;
	}
	for (j = i + 1; j < btree->n_used_nodes; j++)
		hpfs_free_sectors(s, btree->u.external[j].disk_secno, btree->u.external[j].length);
	btree->n_used_nodes = i + 1;
	btree->n_free_nodes = nodes - btree->n_used_nodes;
	btree->first_free = 8 + 12 * btree->n_used_nodes;
	mark_buffer_dirty(bh);
	brelse(bh);
}

/* Remove file or directory and it's eas - note that directory must
   be empty when this is called. */

void hpfs_remove_fnode(struct super_block *s, fnode_secno fno)
{
	struct buffer_head *bh;
	struct fnode *fnode;
	struct extended_attribute *ea;
	struct extended_attribute *ea_end;
	if (!(fnode = hpfs_map_fnode(s, fno, &bh))) return;
	if (!fnode->dirflag) hpfs_remove_btree(s, &fnode->btree);
	else hpfs_remove_dtree(s, fnode->u.external[0].disk_secno);
	ea_end = fnode_end_ea(fnode);
	for (ea = fnode_ea(fnode); ea < ea_end; ea = next_ea(ea))
		if (ea->indirect)
			hpfs_ea_remove(s, ea_sec(ea), ea->anode, ea_len(ea));
	hpfs_ea_ext_remove(s, fnode->ea_secno, fnode->ea_anode, fnode->ea_size_l);
	brelse(bh);
	hpfs_free_sectors(s, fno, 1);
}
Commit	Line	Data
1da177e4 LT	1	/*
	2	* linux/fs/hpfs/anode.c
	3	*
	4	* Mikulas Patocka ([email protected]), 1998-1999
	5	*
	6	* handling HPFS anode tree that contains file allocation info
	7	*/
	8
	9	#include "hpfs_fn.h"
	10
	11	/* Find a sector in allocation tree */
	12
	13	secno hpfs_bplus_lookup(struct super_block s, struct inode inode,
	14	struct bplus_header *btree, unsigned sec,
	15	struct buffer_head *bh)
	16	{
	17	anode_secno a = -1;
	18	struct anode *anode;
	19	int i;
	20	int c1, c2 = 0;
	21	go_down:
	22	if (hpfs_sb(s)->sb_chk) if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_bplus_lookup")) return -1;
	23	if (btree->internal) {
	24	for (i = 0; i < btree->n_used_nodes; i++)
	25	if (btree->u.internal[i].file_secno > sec) {
	26	a = btree->u.internal[i].down;
	27	brelse(bh);
	28	if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
	29	btree = &anode->btree;
	30	goto go_down;
	31	}
	32	hpfs_error(s, "sector %08x not found in internal anode %08x", sec, a);
	33	brelse(bh);
	34	return -1;
	35	}
	36	for (i = 0; i < btree->n_used_nodes; i++)
	37	if (btree->u.external[i].file_secno <= sec &&
	38	btree->u.external[i].file_secno + btree->u.external[i].length > sec) {
	39	a = btree->u.external[i].disk_secno + sec - btree->u.external[i].file_secno;
	40	if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, a, 1, "data")) {
	41	brelse(bh);
	42	return -1;
	43	}
	44	if (inode) {
	45	struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
	46	hpfs_inode->i_file_sec = btree->u.external[i].file_secno;
	47	hpfs_inode->i_disk_sec = btree->u.external[i].disk_secno;
	48	hpfs_inode->i_n_secs = btree->u.external[i].length;
	49	}
	50	brelse(bh);
	51	return a;
	52	}
	53	hpfs_error(s, "sector %08x not found in external anode %08x", sec, a);
	54	brelse(bh);
	55	return -1;
	56	}
	57
	58	/* Add a sector to tree */
	59
	60	secno hpfs_add_sector_to_btree(struct super_block *s, secno node, int fnod, unsigned fsecno)
	61	{
	62	struct bplus_header *btree;
	63	struct anode anode = NULL, ranode = NULL;
	64	struct fnode *fnode;
65	anode_secno a, na = -1, ra, up = -1;
66	secno se;
67	struct buffer_head bh, bh1, *bh2;
68	int n;
69	unsigned fs;
70	int c1, c2 = 0;
71	if (fnod) {
72	if (!(fnode = hpfs_map_fnode(s, node, &bh))) return -1;
73	btree = &fnode->btree;
74	} else {
75	if (!(anode = hpfs_map_anode(s, node, &bh))) return -1;
76	btree = &anode->btree;
77	}
78	a = node;
79	go_down:
80	if ((n = btree->n_used_nodes - 1) < -!!fnod) {
81	hpfs_error(s, "anode %08x has no entries", a);
82	brelse(bh);
83	return -1;
84	}
85	if (btree->internal) {
86	a = btree->u.internal[n].down;
87	btree->u.internal[n].file_secno = -1;
88	mark_buffer_dirty(bh);
89	brelse(bh);
90	if (hpfs_sb(s)->sb_chk)
91	if (hpfs_stop_cycles(s, a, &c1, &c2, "hpfs_add_sector_to_btree #1")) return -1;
92	if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
93	btree = &anode->btree;
94	goto go_down;
95	}
96	if (n >= 0) {
97	if (btree->u.external[n].file_secno + btree->u.external[n].length != fsecno) {
98	hpfs_error(s, "allocated size %08x, trying to add sector %08x, %cnode %08x",
99	btree->u.external[n].file_secno + btree->u.external[n].length, fsecno,
100	fnod?'f':'a', node);
101	brelse(bh);
102	return -1;
103	}
104	if (hpfs_alloc_if_possible(s, se = btree->u.external[n].disk_secno + btree->u.external[n].length)) {
105	btree->u.external[n].length++;
106	mark_buffer_dirty(bh);
107	brelse(bh);
108	return se;
109	}
110	} else {
111	if (fsecno) {
112	hpfs_error(s, "empty file %08x, trying to add sector %08x", node, fsecno);
113	brelse(bh);
114	return -1;
115	}
116	se = !fnod ? node : (node + 16384) & ~16383;
117	}
118	if (!(se = hpfs_alloc_sector(s, se, 1, fsecnoALLOC_M>ALLOC_FWD_MAX ? ALLOC_FWD_MAX : fsecnoALLOC_M<ALLOC_FWD_MIN ? ALLOC_FWD_MIN : fsecno*ALLOC_M, 1))) {
119	brelse(bh);
120	return -1;
121	}
122	fs = n < 0 ? 0 : btree->u.external[n].file_secno + btree->u.external[n].length;
123	if (!btree->n_free_nodes) {
124	up = a != node ? anode->up : -1;
125	if (!(anode = hpfs_alloc_anode(s, a, &na, &bh1))) {
126	brelse(bh);
127	hpfs_free_sectors(s, se, 1);
128	return -1;
129	}
130	if (a == node && fnod) {
131	anode->up = node;
132	anode->btree.fnode_parent = 1;
133	anode->btree.n_used_nodes = btree->n_used_nodes;
134	anode->btree.first_free = btree->first_free;
135	anode->btree.n_free_nodes = 40 - anode->btree.n_used_nodes;
136	memcpy(&anode->u, &btree->u, btree->n_used_nodes * 12);
137	btree->internal = 1;
138	btree->n_free_nodes = 11;
139	btree->n_used_nodes = 1;
140	btree->first_free = (char )&(btree->u.internal[1]) - (char )btree;
141	btree->u.internal[0].file_secno = -1;
142	btree->u.internal[0].down = na;
143	mark_buffer_dirty(bh);
144	} else if (!(ranode = hpfs_alloc_anode(s, /a/0, &ra, &bh2))) {
145	brelse(bh);
146	brelse(bh1);
147	hpfs_free_sectors(s, se, 1);
148	hpfs_free_sectors(s, na, 1);
149	return -1;
150	}
151	brelse(bh);
152	bh = bh1;
153	btree = &anode->btree;
154	}
155	btree->n_free_nodes--; n = btree->n_used_nodes++;
156	btree->first_free += 12;
157	btree->u.external[n].disk_secno = se;
158	btree->u.external[n].file_secno = fs;
159	btree->u.external[n].length = 1;
160	mark_buffer_dirty(bh);
161	brelse(bh);
162	if ((a == node && fnod) \|\| na == -1) return se;
163	c2 = 0;
164	while (up != -1) {
165	struct anode *new_anode;
166	if (hpfs_sb(s)->sb_chk)
167	if (hpfs_stop_cycles(s, up, &c1, &c2, "hpfs_add_sector_to_btree #2")) return -1;
168	if (up != node \|\| !fnod) {
169	if (!(anode = hpfs_map_anode(s, up, &bh))) return -1;
170	btree = &anode->btree;
171	} else {
172	if (!(fnode = hpfs_map_fnode(s, up, &bh))) return -1;
173	btree = &fnode->btree;
174	}
175	if (btree->n_free_nodes) {
176	btree->n_free_nodes--; n = btree->n_used_nodes++;
177	btree->first_free += 8;
178	btree->u.internal[n].file_secno = -1;
179	btree->u.internal[n].down = na;
180	btree->u.internal[n-1].file_secno = fs;
181	mark_buffer_dirty(bh);
182	brelse(bh);
183	brelse(bh2);
184	hpfs_free_sectors(s, ra, 1);
185	if ((anode = hpfs_map_anode(s, na, &bh))) {
186	anode->up = up;
187	anode->btree.fnode_parent = up == node && fnod;
188	mark_buffer_dirty(bh);
189	brelse(bh);
190	}
191	return se;
192	}
193	up = up != node ? anode->up : -1;
194	btree->u.internal[btree->n_used_nodes - 1].file_secno = /fs/-1;
195	mark_buffer_dirty(bh);
196	brelse(bh);
197	a = na;
198	if ((new_anode = hpfs_alloc_anode(s, a, &na, &bh))) {
199	anode = new_anode;
200	/anode->up = up != -1 ? up : ra;/
201	anode->btree.internal = 1;
202	anode->btree.n_used_nodes = 1;
203	anode->btree.n_free_nodes = 59;
204	anode->btree.first_free = 16;
205	anode->btree.u.internal[0].down = a;
206	anode->btree.u.internal[0].file_secno = -1;
207	mark_buffer_dirty(bh);
208	brelse(bh);
209	if ((anode = hpfs_map_anode(s, a, &bh))) {
210	anode->up = na;
211	mark_buffer_dirty(bh);
212	brelse(bh);
213	}
214	} else na = a;
215	}
216	if ((anode = hpfs_map_anode(s, na, &bh))) {
217	anode->up = node;
218	if (fnod) anode->btree.fnode_parent = 1;
219	mark_buffer_dirty(bh);
220	brelse(bh);
221	}
222	if (!fnod) {
223	if (!(anode = hpfs_map_anode(s, node, &bh))) {
224	brelse(bh2);
225	return -1;
226	}
227	btree = &anode->btree;
228	} else {
229	if (!(fnode = hpfs_map_fnode(s, node, &bh))) {
230	brelse(bh2);
231	return -1;
232	}
233	btree = &fnode->btree;
234	}
235	ranode->up = node;
236	memcpy(&ranode->btree, btree, btree->first_free);
237	if (fnod) ranode->btree.fnode_parent = 1;
238	ranode->btree.n_free_nodes = (ranode->btree.internal ? 60 : 40) - ranode->btree.n_used_nodes;
239	if (ranode->btree.internal) for (n = 0; n < ranode->btree.n_used_nodes; n++) {
240	struct anode *unode;
241	if ((unode = hpfs_map_anode(s, ranode->u.internal[n].down, &bh1))) {
242	unode->up = ra;
243	unode->btree.fnode_parent = 0;
244	mark_buffer_dirty(bh1);
245	brelse(bh1);
246	}
247	}
248	btree->internal = 1;
249	btree->n_free_nodes = fnod ? 10 : 58;
250	btree->n_used_nodes = 2;
251	btree->first_free = (char )&btree->u.internal[2] - (char )btree;
252	btree->u.internal[0].file_secno = fs;
253	btree->u.internal[0].down = ra;
254	btree->u.internal[1].file_secno = -1;
255	btree->u.internal[1].down = na;
256	mark_buffer_dirty(bh);
257	brelse(bh);
258	mark_buffer_dirty(bh2);
259	brelse(bh2);
260	return se;
261	}
262
263	/*
264	* Remove allocation tree. Recursion would look much nicer but
265	* I want to avoid it because it can cause stack overflow.
266	*/
267
268	void hpfs_remove_btree(struct super_block s, struct bplus_header btree)
269	{
270	struct bplus_header *btree1 = btree;
271	struct anode *anode = NULL;
272	anode_secno ano = 0, oano;
273	struct buffer_head *bh;
274	int level = 0;
275	int pos = 0;
276	int i;
277	int c1, c2 = 0;
278	int d1, d2;
279	go_down:
280	d2 = 0;
281	while (btree1->internal) {
282	ano = btree1->u.internal[pos].down;
283	if (level) brelse(bh);
284	if (hpfs_sb(s)->sb_chk)
285	if (hpfs_stop_cycles(s, ano, &d1, &d2, "hpfs_remove_btree #1"))
286	return;
287	if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
288	btree1 = &anode->btree;
289	level++;
290	pos = 0;
291	}
292	for (i = 0; i < btree1->n_used_nodes; i++)
293	hpfs_free_sectors(s, btree1->u.external[i].disk_secno, btree1->u.external[i].length);
294	go_up:
295	if (!level) return;
296	brelse(bh);
297	if (hpfs_sb(s)->sb_chk)
298	if (hpfs_stop_cycles(s, ano, &c1, &c2, "hpfs_remove_btree #2")) return;
299	hpfs_free_sectors(s, ano, 1);
300	oano = ano;
301	ano = anode->up;
302	if (--level) {
303	if (!(anode = hpfs_map_anode(s, ano, &bh))) return;
304	btree1 = &anode->btree;
305	} else btree1 = btree;
306	for (i = 0; i < btree1->n_used_nodes; i++) {
307	if (btree1->u.internal[i].down == oano) {
308	if ((pos = i + 1) < btree1->n_used_nodes)
309	goto go_down;
310	else
311	goto go_up;
312	}
313	}
314	hpfs_error(s,
315	"reference to anode %08x not found in anode %08x "
316	"(probably bad up pointer)",
317	oano, level ? ano : -1);
318	if (level)
319	brelse(bh);
320	}
321
322	/* Just a wrapper around hpfs_bplus_lookup .. used for reading eas */
323
324	static secno anode_lookup(struct super_block *s, anode_secno a, unsigned sec)
325	{
326	struct anode *anode;
327	struct buffer_head *bh;
328	if (!(anode = hpfs_map_anode(s, a, &bh))) return -1;
329	return hpfs_bplus_lookup(s, NULL, &anode->btree, sec, bh);
330	}
331
332	int hpfs_ea_read(struct super_block *s, secno a, int ano, unsigned pos,
333	unsigned len, char *buf)
334	{
335	struct buffer_head *bh;
336	char *data;
337	secno sec;
338	unsigned l;
339	while (len) {
340	if (ano) {
341	if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
342	return -1;
343	} else sec = a + (pos >> 9);
344	if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #1")) return -1;
345	if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
346	return -1;
347	l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
348	memcpy(buf, data + (pos & 0x1ff), l);
349	brelse(bh);
350	buf += l; pos += l; len -= l;
351	}
352	return 0;
353	}
354
355	int hpfs_ea_write(struct super_block *s, secno a, int ano, unsigned pos,
356	unsigned len, char *buf)
357	{
358	struct buffer_head *bh;
359	char *data;
360	secno sec;
361	unsigned l;
362	while (len) {
363	if (ano) {
364	if ((sec = anode_lookup(s, a, pos >> 9)) == -1)
365	return -1;
366	} else sec = a + (pos >> 9);
367	if (hpfs_sb(s)->sb_chk) if (hpfs_chk_sectors(s, sec, 1, "ea #2")) return -1;
368	if (!(data = hpfs_map_sector(s, sec, &bh, (len - 1) >> 9)))
369	return -1;
370	l = 0x200 - (pos & 0x1ff); if (l > len) l = len;
371	memcpy(data + (pos & 0x1ff), buf, l);
372	mark_buffer_dirty(bh);
373	brelse(bh);
374	buf += l; pos += l; len -= l;
375	}
376	return 0;
377	}
378
379	void hpfs_ea_remove(struct super_block *s, secno a, int ano, unsigned len)
380	{
381	struct anode *anode;
382	struct buffer_head *bh;
383	if (ano) {
384	if (!(anode = hpfs_map_anode(s, a, &bh))) return;
385	hpfs_remove_btree(s, &anode->btree);
386	brelse(bh);
387	hpfs_free_sectors(s, a, 1);
388	} else hpfs_free_sectors(s, a, (len + 511) >> 9);
389	}
390
391	/* Truncate allocation tree. Doesn't join anodes - I hope it doesn't matter */
392
393	void hpfs_truncate_btree(struct super_block *s, secno f, int fno, unsigned secs)
394	{
395	struct fnode *fnode;
396	struct anode *anode;
397	struct buffer_head *bh;
398	struct bplus_header *btree;
399	anode_secno node = f;
400	int i, j, nodes;
401	int c1, c2 = 0;
402	if (fno) {
403	if (!(fnode = hpfs_map_fnode(s, f, &bh))) return;
404	btree = &fnode->btree;
405	} else {
406	if (!(anode = hpfs_map_anode(s, f, &bh))) return;
407	btree = &anode->btree;
408	}
409	if (!secs) {
410	hpfs_remove_btree(s, btree);
411	if (fno) {
412	btree->n_free_nodes = 8;
413	btree->n_used_nodes = 0;
414	btree->first_free = 8;
415	btree->internal = 0;
416	mark_buffer_dirty(bh);
417	} else hpfs_free_sectors(s, f, 1);
418	brelse(bh);
419	return;
420	}
421	while (btree->internal) {
422	nodes = btree->n_used_nodes + btree->n_free_nodes;
423	for (i = 0; i < btree->n_used_nodes; i++)
424	if (btree->u.internal[i].file_secno >= secs) goto f;
425	brelse(bh);
426	hpfs_error(s, "internal btree %08x doesn't end with -1", node);
427	return;
428	f:
429	for (j = i + 1; j < btree->n_used_nodes; j++)
430	hpfs_ea_remove(s, btree->u.internal[j].down, 1, 0);
431	btree->n_used_nodes = i + 1;
432	btree->n_free_nodes = nodes - btree->n_used_nodes;
433	btree->first_free = 8 + 8 * btree->n_used_nodes;
434	mark_buffer_dirty(bh);
435	if (btree->u.internal[i].file_secno == secs) {
436	brelse(bh);
437	return;
438	}
439	node = btree->u.internal[i].down;
440	brelse(bh);
441	if (hpfs_sb(s)->sb_chk)
442	if (hpfs_stop_cycles(s, node, &c1, &c2, "hpfs_truncate_btree"))
443	return;
444	if (!(anode = hpfs_map_anode(s, node, &bh))) return;
445	btree = &anode->btree;
446	}
447	nodes = btree->n_used_nodes + btree->n_free_nodes;
448	for (i = 0; i < btree->n_used_nodes; i++)
449	if (btree->u.external[i].file_secno + btree->u.external[i].length >= secs) goto ff;
450	brelse(bh);
451	return;
452	ff:
453	if (secs <= btree->u.external[i].file_secno) {
454	hpfs_error(s, "there is an allocation error in file %08x, sector %08x", f, secs);
455	if (i) i--;
456	}
457	else if (btree->u.external[i].file_secno + btree->u.external[i].length > secs) {
458	hpfs_free_sectors(s, btree->u.external[i].disk_secno + secs -
459	btree->u.external[i].file_secno, btree->u.external[i].length
460	- secs + btree->u.external[i].file_secno); /* I hope gcc optimizes this :-) */
461	btree->u.external[i].length = secs - btree->u.external[i].file_secno;
462	}
463	for (j = i + 1; j < btree->n_used_nodes; j++)
464	hpfs_free_sectors(s, btree->u.external[j].disk_secno, btree->u.external[j].length);
465	btree->n_used_nodes = i + 1;
466	btree->n_free_nodes = nodes - btree->n_used_nodes;
467	btree->first_free = 8 + 12 * btree->n_used_nodes;
468	mark_buffer_dirty(bh);
469	brelse(bh);
470	}
471
472	/* Remove file or directory and it's eas - note that directory must
473	be empty when this is called. */
474
475	void hpfs_remove_fnode(struct super_block *s, fnode_secno fno)
476	{
477	struct buffer_head *bh;
478	struct fnode *fnode;
479	struct extended_attribute *ea;
480	struct extended_attribute *ea_end;
481	if (!(fnode = hpfs_map_fnode(s, fno, &bh))) return;
482	if (!fnode->dirflag) hpfs_remove_btree(s, &fnode->btree);
483	else hpfs_remove_dtree(s, fnode->u.external[0].disk_secno);
484	ea_end = fnode_end_ea(fnode);
485	for (ea = fnode_ea(fnode); ea < ea_end; ea = next_ea(ea))
486	if (ea->indirect)
487	hpfs_ea_remove(s, ea_sec(ea), ea->anode, ea_len(ea));
488	hpfs_ea_ext_remove(s, fnode->ea_secno, fnode->ea_anode, fnode->ea_size_l);
489	brelse(bh);
490	hpfs_free_sectors(s, fno, 1);
491	}