Linux-2.6.12-rc2

Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.

Let it rip!

1 files changed, 1080 insertions, 0 deletions

diff --git a/fs/hpfs/dnode.c b/fs/hpfs/dnode.c
new file mode 100644
index 000000000000..1d21307730a8
--- /dev/null
+++ b/fs/hpfs/dnode.c
@@ -0,0 +1,1080 @@
+/*
+ *  linux/fs/hpfs/dnode.c
+ *
+ *  Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
+ *
+ *  handling directory dnode tree - adding, deleteing & searching for dirents
+ */
+
+#include "hpfs_fn.h"
+
+static loff_t get_pos(struct dnode *d, struct hpfs_dirent *fde)
+{
+	struct hpfs_dirent *de;
+	struct hpfs_dirent *de_end = dnode_end_de(d);
+	int i = 1;
+	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
+		if (de == fde) return ((loff_t) d->self << 4) | (loff_t)i;
+		i++;
+	}
+	printk("HPFS: get_pos: not_found\n");
+	return ((loff_t)d->self << 4) | (loff_t)1;
+}
+
+void hpfs_add_pos(struct inode *inode, loff_t *pos)
+{
+	struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
+	int i = 0;
+	loff_t **ppos;
+
+	if (hpfs_inode->i_rddir_off)
+		for (; hpfs_inode->i_rddir_off[i]; i++)
+			if (hpfs_inode->i_rddir_off[i] == pos) return;
+	if (!(i&0x0f)) {
+		if (!(ppos = kmalloc((i+0x11) * sizeof(loff_t*), GFP_NOFS))) {
+			printk("HPFS: out of memory for position list\n");
+			return;
+		}
+		if (hpfs_inode->i_rddir_off) {
+			memcpy(ppos, hpfs_inode->i_rddir_off, i * sizeof(loff_t));
+			kfree(hpfs_inode->i_rddir_off);
+		}
+		hpfs_inode->i_rddir_off = ppos;
+	}
+	hpfs_inode->i_rddir_off[i] = pos;
+	hpfs_inode->i_rddir_off[i + 1] = NULL;
+}
+
+void hpfs_del_pos(struct inode *inode, loff_t *pos)
+{
+	struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
+	loff_t **i, **j;
+
+	if (!hpfs_inode->i_rddir_off) goto not_f;
+	for (i = hpfs_inode->i_rddir_off; *i; i++) if (*i == pos) goto fnd;
+	goto not_f;
+	fnd:
+	for (j = i + 1; *j; j++) ;
+	*i = *(j - 1);
+	*(j - 1) = NULL;
+	if (j - 1 == hpfs_inode->i_rddir_off) {
+		kfree(hpfs_inode->i_rddir_off);
+		hpfs_inode->i_rddir_off = NULL;
+	}
+	return;
+	not_f:
+	/*printk("HPFS: warning: position pointer %p->%08x not found\n", pos, (int)*pos);*/
+	return;
+}
+
+static void for_all_poss(struct inode *inode, void (*f)(loff_t *, loff_t, loff_t),
+			 loff_t p1, loff_t p2)
+{
+	struct hpfs_inode_info *hpfs_inode = hpfs_i(inode);
+	loff_t **i;
+
+	if (!hpfs_inode->i_rddir_off) return;
+	for (i = hpfs_inode->i_rddir_off; *i; i++) (*f)(*i, p1, p2);
+	return;
+}
+
+static void hpfs_pos_subst(loff_t *p, loff_t f, loff_t t)
+{
+	if (*p == f) *p = t;
+}
+
+/*void hpfs_hpfs_pos_substd(loff_t *p, loff_t f, loff_t t)
+{
+	if ((*p & ~0x3f) == (f & ~0x3f)) *p = (t & ~0x3f) | (*p & 0x3f);
+}*/
+
+static void hpfs_pos_ins(loff_t *p, loff_t d, loff_t c)
+{
+	if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
+		int n = (*p & 0x3f) + c;
+		if (n > 0x3f) printk("HPFS: hpfs_pos_ins: %08x + %d\n", (int)*p, (int)c >> 8);
+		else *p = (*p & ~0x3f) | n;
+	}
+}
+
+static void hpfs_pos_del(loff_t *p, loff_t d, loff_t c)
+{
+	if ((*p & ~0x3f) == (d & ~0x3f) && (*p & 0x3f) >= (d & 0x3f)) {
+		int n = (*p & 0x3f) - c;
+		if (n < 1) printk("HPFS: hpfs_pos_ins: %08x - %d\n", (int)*p, (int)c >> 8);
+		else *p = (*p & ~0x3f) | n;
+	}
+}
+
+static struct hpfs_dirent *dnode_pre_last_de(struct dnode *d)
+{
+	struct hpfs_dirent *de, *de_end, *dee = NULL, *deee = NULL;
+	de_end = dnode_end_de(d);
+	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
+		deee = dee; dee = de;
+	}	
+	return deee;
+}
+
+static struct hpfs_dirent *dnode_last_de(struct dnode *d)
+{
+	struct hpfs_dirent *de, *de_end, *dee = NULL;
+	de_end = dnode_end_de(d);
+	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
+		dee = de;
+	}	
+	return dee;
+}
+
+static void set_last_pointer(struct super_block *s, struct dnode *d, dnode_secno ptr)
+{
+	struct hpfs_dirent *de;
+	if (!(de = dnode_last_de(d))) {
+		hpfs_error(s, "set_last_pointer: empty dnode %08x", d->self);
+		return;
+	}
+	if (hpfs_sb(s)->sb_chk) {
+		if (de->down) {
+			hpfs_error(s, "set_last_pointer: dnode %08x has already last pointer %08x",
+				d->self, de_down_pointer(de));
+			return;
+		}
+		if (de->length != 32) {
+			hpfs_error(s, "set_last_pointer: bad last dirent in dnode %08x", d->self);
+			return;
+		}
+	}
+	if (ptr) {
+		if ((d->first_free += 4) > 2048) {
+			hpfs_error(s,"set_last_pointer: too long dnode %08x", d->self);
+			d->first_free -= 4;
+			return;
+		}
+		de->length = 36;
+		de->down = 1;
+		*(dnode_secno *)((char *)de + 32) = ptr;
+	}
+}
+
+/* Add an entry to dnode and don't care if it grows over 2048 bytes */
+
+struct hpfs_dirent *hpfs_add_de(struct super_block *s, struct dnode *d, unsigned char *name,
+				unsigned namelen, secno down_ptr)
+{
+	struct hpfs_dirent *de;
+	struct hpfs_dirent *de_end = dnode_end_de(d);
+	unsigned d_size = de_size(namelen, down_ptr);
+	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
+		int c = hpfs_compare_names(s, name, namelen, de->name, de->namelen, de->last);
+		if (!c) {
+			hpfs_error(s, "name (%c,%d) already exists in dnode %08x", *name, namelen, d->self);
+			return NULL;
+		}
+		if (c < 0) break;
+	}
+	memmove((char *)de + d_size, de, (char *)de_end - (char *)de);
+	memset(de, 0, d_size);
+	if (down_ptr) {
+		*(int *)((char *)de + d_size - 4) = down_ptr;
+		de->down = 1;
+	}
+	de->length = d_size;
+	if (down_ptr) de->down = 1;
+	de->not_8x3 = hpfs_is_name_long(name, namelen);
+	de->namelen = namelen;
+	memcpy(de->name, name, namelen);
+	d->first_free += d_size;
+	return de;
+}
+
+/* Delete dirent and don't care about its subtree */
+
+static void hpfs_delete_de(struct super_block *s, struct dnode *d,
+			   struct hpfs_dirent *de)
+{
+	if (de->last) {
+		hpfs_error(s, "attempt to delete last dirent in dnode %08x", d->self);
+		return;
+	}
+	d->first_free -= de->length;
+	memmove(de, de_next_de(de), d->first_free + (char *)d - (char *)de);
+}
+
+static void fix_up_ptrs(struct super_block *s, struct dnode *d)
+{
+	struct hpfs_dirent *de;
+	struct hpfs_dirent *de_end = dnode_end_de(d);
+	dnode_secno dno = d->self;
+	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de))
+		if (de->down) {
+			struct quad_buffer_head qbh;
+			struct dnode *dd;
+			if ((dd = hpfs_map_dnode(s, de_down_pointer(de), &qbh))) {
+				if (dd->up != dno || dd->root_dnode) {
+					dd->up = dno;
+					dd->root_dnode = 0;
+					hpfs_mark_4buffers_dirty(&qbh);
+				}
+				hpfs_brelse4(&qbh);
+			}
+		}
+}
+
+/* Add an entry to dnode and do dnode splitting if required */
+
+static int hpfs_add_to_dnode(struct inode *i, dnode_secno dno,
+			     unsigned char *name, unsigned namelen,
+			     struct hpfs_dirent *new_de, dnode_secno down_ptr)
+{
+	struct quad_buffer_head qbh, qbh1, qbh2;
+	struct dnode *d, *ad, *rd, *nd = NULL;
+	dnode_secno adno, rdno;
+	struct hpfs_dirent *de;
+	struct hpfs_dirent nde;
+	char *nname;
+	int h;
+	int pos;
+	struct buffer_head *bh;
+	struct fnode *fnode;
+	int c1, c2 = 0;
+	if (!(nname = kmalloc(256, GFP_NOFS))) {
+		printk("HPFS: out of memory, can't add to dnode\n");
+		return 1;
+	}
+	go_up:
+	if (namelen >= 256) {
+		hpfs_error(i->i_sb, "hpfs_add_to_dnode: namelen == %d", namelen);
+		if (nd) kfree(nd);
+		kfree(nname);
+		return 1;
+	}
+	if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) {
+		if (nd) kfree(nd);
+		kfree(nname);
+		return 1;
+	}
+	go_up_a:
+	if (hpfs_sb(i->i_sb)->sb_chk)
+		if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_to_dnode")) {
+			hpfs_brelse4(&qbh);
+			if (nd) kfree(nd);
+			kfree(nname);
+			return 1;
+		}
+	if (d->first_free + de_size(namelen, down_ptr) <= 2048) {
+		loff_t t;
+		copy_de(de=hpfs_add_de(i->i_sb, d, name, namelen, down_ptr), new_de);
+		t = get_pos(d, de);
+		for_all_poss(i, hpfs_pos_ins, t, 1);
+		for_all_poss(i, hpfs_pos_subst, 4, t);
+		for_all_poss(i, hpfs_pos_subst, 5, t + 1);
+		hpfs_mark_4buffers_dirty(&qbh);
+		hpfs_brelse4(&qbh);
+		if (nd) kfree(nd);
+		kfree(nname);
+		return 0;
+	}
+	if (!nd) if (!(nd = kmalloc(0x924, GFP_NOFS))) {
+		/* 0x924 is a max size of dnode after adding a dirent with
+		   max name length. We alloc this only once. There must
+		   not be any error while splitting dnodes, otherwise the
+		   whole directory, not only file we're adding, would
+		   be lost. */
+		printk("HPFS: out of memory for dnode splitting\n");
+		hpfs_brelse4(&qbh);
+		kfree(nname);
+		return 1;
+	}	
+	memcpy(nd, d, d->first_free);
+	copy_de(de = hpfs_add_de(i->i_sb, nd, name, namelen, down_ptr), new_de);
+	for_all_poss(i, hpfs_pos_ins, get_pos(nd, de), 1);
+	h = ((char *)dnode_last_de(nd) - (char *)nd) / 2 + 10;
+	if (!(ad = hpfs_alloc_dnode(i->i_sb, d->up, &adno, &qbh1, 0))) {
+		hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
+		hpfs_brelse4(&qbh);
+		kfree(nd);
+		kfree(nname);
+		return 1;
+	}
+	i->i_size += 2048;
+	i->i_blocks += 4;
+	pos = 1;
+	for (de = dnode_first_de(nd); (char *)de_next_de(de) - (char *)nd < h; de = de_next_de(de)) {
+		copy_de(hpfs_add_de(i->i_sb, ad, de->name, de->namelen, de->down ? de_down_pointer(de) : 0), de);
+		for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, ((loff_t)adno << 4) | pos);
+		pos++;
+	}
+	copy_de(new_de = &nde, de);
+	memcpy(name = nname, de->name, namelen = de->namelen);
+	for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | pos, 4);
+	down_ptr = adno;
+	set_last_pointer(i->i_sb, ad, de->down ? de_down_pointer(de) : 0);
+	de = de_next_de(de);
+	memmove((char *)nd + 20, de, nd->first_free + (char *)nd - (char *)de);
+	nd->first_free -= (char *)de - (char *)nd - 20;
+	memcpy(d, nd, nd->first_free);
+	for_all_poss(i, hpfs_pos_del, (loff_t)dno << 4, pos);
+	fix_up_ptrs(i->i_sb, ad);
+	if (!d->root_dnode) {
+		dno = ad->up = d->up;
+		hpfs_mark_4buffers_dirty(&qbh);
+		hpfs_brelse4(&qbh);
+		hpfs_mark_4buffers_dirty(&qbh1);
+		hpfs_brelse4(&qbh1);
+		goto go_up;
+	}
+	if (!(rd = hpfs_alloc_dnode(i->i_sb, d->up, &rdno, &qbh2, 0))) {
+		hpfs_error(i->i_sb, "unable to alloc dnode - dnode tree will be corrupted");
+		hpfs_brelse4(&qbh);
+		hpfs_brelse4(&qbh1);
+		kfree(nd);
+		kfree(nname);
+		return 1;
+	}
+	i->i_size += 2048;
+	i->i_blocks += 4;
+	rd->root_dnode = 1;
+	rd->up = d->up;
+	if (!(fnode = hpfs_map_fnode(i->i_sb, d->up, &bh))) {
+		hpfs_free_dnode(i->i_sb, rdno);
+		hpfs_brelse4(&qbh);
+		hpfs_brelse4(&qbh1);
+		hpfs_brelse4(&qbh2);
+		kfree(nd);
+		kfree(nname);
+		return 1;
+	}
+	fnode->u.external[0].disk_secno = rdno;
+	mark_buffer_dirty(bh);
+	brelse(bh);
+	d->up = ad->up = hpfs_i(i)->i_dno = rdno;
+	d->root_dnode = ad->root_dnode = 0;
+	hpfs_mark_4buffers_dirty(&qbh);
+	hpfs_brelse4(&qbh);
+	hpfs_mark_4buffers_dirty(&qbh1);
+	hpfs_brelse4(&qbh1);
+	qbh = qbh2;
+	set_last_pointer(i->i_sb, rd, dno);
+	dno = rdno;
+	d = rd;
+	goto go_up_a;
+}
+
+/*
+ * Add an entry to directory btree.
+ * I hate such crazy directory structure.
+ * It's easy to read but terrible to write.
+ * I wrote this directory code 4 times.
+ * I hope, now it's finally bug-free.
+ */
+
+int hpfs_add_dirent(struct inode *i, unsigned char *name, unsigned namelen,
+		    struct hpfs_dirent *new_de, int cdepth)
+{
+	struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
+	struct dnode *d;
+	struct hpfs_dirent *de, *de_end;
+	struct quad_buffer_head qbh;
+	dnode_secno dno;
+	int c;
+	int c1, c2 = 0;
+	dno = hpfs_inode->i_dno;
+	down:
+	if (hpfs_sb(i->i_sb)->sb_chk)
+		if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "hpfs_add_dirent")) return 1;
+	if (!(d = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 1;
+	de_end = dnode_end_de(d);
+	for (de = dnode_first_de(d); de < de_end; de = de_next_de(de)) {
+		if (!(c = hpfs_compare_names(i->i_sb, name, namelen, de->name, de->namelen, de->last))) {
+			hpfs_brelse4(&qbh);
+			return -1;
+		}	
+		if (c < 0) {
+			if (de->down) {
+				dno = de_down_pointer(de);
+				hpfs_brelse4(&qbh);
+				goto down;
+			}
+			break;
+		}
+	}
+	hpfs_brelse4(&qbh);
+	if (!cdepth) hpfs_lock_creation(i->i_sb);
+	if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_ADD)) {
+		c = 1;
+		goto ret;
+	}	
+	i->i_version++;
+	c = hpfs_add_to_dnode(i, dno, name, namelen, new_de, 0);
+	ret:
+	if (!cdepth) hpfs_unlock_creation(i->i_sb);
+	return c;
+}
+
+/* 
+ * Find dirent with higher name in 'from' subtree and move it to 'to' dnode.
+ * Return the dnode we moved from (to be checked later if it's empty)
+ */
+
+static secno move_to_top(struct inode *i, dnode_secno from, dnode_secno to)
+{
+	dnode_secno dno, ddno;
+	dnode_secno chk_up = to;
+	struct dnode *dnode;
+	struct quad_buffer_head qbh;
+	struct hpfs_dirent *de, *nde;
+	int a;
+	loff_t t;
+	int c1, c2 = 0;
+	dno = from;
+	while (1) {
+		if (hpfs_sb(i->i_sb)->sb_chk)
+			if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "move_to_top"))
+				return 0;
+		if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return 0;
+		if (hpfs_sb(i->i_sb)->sb_chk) {
+			if (dnode->up != chk_up) {
+				hpfs_error(i->i_sb, "move_to_top: up pointer from %08x should be %08x, is %08x",
+					dno, chk_up, dnode->up);
+				hpfs_brelse4(&qbh);
+				return 0;
+			}
+			chk_up = dno;
+		}
+		if (!(de = dnode_last_de(dnode))) {
+			hpfs_error(i->i_sb, "move_to_top: dnode %08x has no last de", dno);
+			hpfs_brelse4(&qbh);
+			return 0;
+		}
+		if (!de->down) break;
+		dno = de_down_pointer(de);
+		hpfs_brelse4(&qbh);
+	}
+	while (!(de = dnode_pre_last_de(dnode))) {
+		dnode_secno up = dnode->up;
+		hpfs_brelse4(&qbh);
+		hpfs_free_dnode(i->i_sb, dno);
+		i->i_size -= 2048;
+		i->i_blocks -= 4;
+		for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, 5);
+		if (up == to) return to;
+		if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return 0;
+		if (dnode->root_dnode) {
+			hpfs_error(i->i_sb, "move_to_top: got to root_dnode while moving from %08x to %08x", from, to);
+			hpfs_brelse4(&qbh);
+			return 0;
+		}
+		de = dnode_last_de(dnode);
+		if (!de || !de->down) {
+			hpfs_error(i->i_sb, "move_to_top: dnode %08x doesn't point down to %08x", up, dno);
+			hpfs_brelse4(&qbh);
+			return 0;
+		}
+		dnode->first_free -= 4;
+		de->length -= 4;
+		de->down = 0;
+		hpfs_mark_4buffers_dirty(&qbh);
+		dno = up;
+	}
+	t = get_pos(dnode, de);
+	for_all_poss(i, hpfs_pos_subst, t, 4);
+	for_all_poss(i, hpfs_pos_subst, t + 1, 5);
+	if (!(nde = kmalloc(de->length, GFP_NOFS))) {
+		hpfs_error(i->i_sb, "out of memory for dirent - directory will be corrupted");
+		hpfs_brelse4(&qbh);
+		return 0;
+	}
+	memcpy(nde, de, de->length);
+	ddno = de->down ? de_down_pointer(de) : 0;
+	hpfs_delete_de(i->i_sb, dnode, de);
+	set_last_pointer(i->i_sb, dnode, ddno);
+	hpfs_mark_4buffers_dirty(&qbh);
+	hpfs_brelse4(&qbh);
+	a = hpfs_add_to_dnode(i, to, nde->name, nde->namelen, nde, from);
+	kfree(nde);
+	if (a) return 0;
+	return dno;
+}
+
+/* 
+ * Check if a dnode is empty and delete it from the tree
+ * (chkdsk doesn't like empty dnodes)
+ */
+
+static void delete_empty_dnode(struct inode *i, dnode_secno dno)
+{
+	struct hpfs_inode_info *hpfs_inode = hpfs_i(i);
+	struct quad_buffer_head qbh;
+	struct dnode *dnode;
+	dnode_secno down, up, ndown;
+	int p;
+	struct hpfs_dirent *de;
+	int c1, c2 = 0;
+	try_it_again:
+	if (hpfs_stop_cycles(i->i_sb, dno, &c1, &c2, "delete_empty_dnode")) return;
+	if (!(dnode = hpfs_map_dnode(i->i_sb, dno, &qbh))) return;
+	if (dnode->first_free > 56) goto end;
+	if (dnode->first_free == 52 || dnode->first_free == 56) {
+		struct hpfs_dirent *de_end;
+		int root = dnode->root_dnode;
+		up = dnode->up;
+		de = dnode_first_de(dnode);
+		down = de->down ? de_down_pointer(de) : 0;
+		if (hpfs_sb(i->i_sb)->sb_chk) if (root && !down) {
+			hpfs_error(i->i_sb, "delete_empty_dnode: root dnode %08x is empty", dno);
+			goto end;
+		}
+		hpfs_brelse4(&qbh);
+		hpfs_free_dnode(i->i_sb, dno);
+		i->i_size -= 2048;
+		i->i_blocks -= 4;
+		if (root) {
+			struct fnode *fnode;
+			struct buffer_head *bh;
+			struct dnode *d1;
+			struct quad_buffer_head qbh1;
+			if (hpfs_sb(i->i_sb)->sb_chk) if (up != i->i_ino) {
+				hpfs_error(i->i_sb, "bad pointer to fnode, dnode %08x, pointing to %08x, should be %08x", dno, up, i->i_ino);
+				return;
+			}
+			if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
+				d1->up = up;
+				d1->root_dnode = 1;
+				hpfs_mark_4buffers_dirty(&qbh1);
+				hpfs_brelse4(&qbh1);
+			}
+			if ((fnode = hpfs_map_fnode(i->i_sb, up, &bh))) {
+				fnode->u.external[0].disk_secno = down;
+				mark_buffer_dirty(bh);
+				brelse(bh);
+			}
+			hpfs_inode->i_dno = down;
+			for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, (loff_t) 12);
+			return;
+		}
+		if (!(dnode = hpfs_map_dnode(i->i_sb, up, &qbh))) return;
+		p = 1;
+		de_end = dnode_end_de(dnode);
+		for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de), p++)
+			if (de->down) if (de_down_pointer(de) == dno) goto fnd;
+		hpfs_error(i->i_sb, "delete_empty_dnode: pointer to dnode %08x not found in dnode %08x", dno, up);
+		goto end;
+		fnd:
+		for_all_poss(i, hpfs_pos_subst, ((loff_t)dno << 4) | 1, ((loff_t)up << 4) | p);
+		if (!down) {
+			de->down = 0;
+			de->length -= 4;
+			dnode->first_free -= 4;
+			memmove(de_next_de(de), (char *)de_next_de(de) + 4,
+				(char *)dnode + dnode->first_free - (char *)de_next_de(de));
+		} else {
+			struct dnode *d1;
+			struct quad_buffer_head qbh1;
+			*(dnode_secno *) ((void *) de + de->length - 4) = down;
+			if ((d1 = hpfs_map_dnode(i->i_sb, down, &qbh1))) {
+				d1->up = up;
+				hpfs_mark_4buffers_dirty(&qbh1);
+				hpfs_brelse4(&qbh1);
+			}
+		}
+	} else {
+		hpfs_error(i->i_sb, "delete_empty_dnode: dnode %08x, first_free == %03x", dno, dnode->first_free);
+		goto end;
+	}
+
+	if (!de->last) {
+		struct hpfs_dirent *de_next = de_next_de(de);
+		struct hpfs_dirent *de_cp;
+		struct dnode *d1;
+		struct quad_buffer_head qbh1;
+		if (!de_next->down) goto endm;
+		ndown = de_down_pointer(de_next);
+		if (!(de_cp = kmalloc(de->length, GFP_NOFS))) {
+			printk("HPFS: out of memory for dtree balancing\n");
+			goto endm;
+		}
+		memcpy(de_cp, de, de->length);
+		hpfs_delete_de(i->i_sb, dnode, de);
+		hpfs_mark_4buffers_dirty(&qbh);
+		hpfs_brelse4(&qbh);
+		for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, 4);
+		for_all_poss(i, hpfs_pos_del, ((loff_t)up << 4) | p, 1);
+		if (de_cp->down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de_cp), &qbh1))) {
+			d1->up = ndown;
+			hpfs_mark_4buffers_dirty(&qbh1);
+			hpfs_brelse4(&qbh1);
+		}
+		hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, de_cp->down ? de_down_pointer(de_cp) : 0);
+		/*printk("UP-TO-DNODE: %08x (ndown = %08x, down = %08x, dno = %08x)\n", up, ndown, down, dno);*/
+		dno = up;
+		kfree(de_cp);
+		goto try_it_again;
+	} else {
+		struct hpfs_dirent *de_prev = dnode_pre_last_de(dnode);
+		struct hpfs_dirent *de_cp;
+		struct dnode *d1;
+		struct quad_buffer_head qbh1;
+		dnode_secno dlp;
+		if (!de_prev) {
+			hpfs_error(i->i_sb, "delete_empty_dnode: empty dnode %08x", up);
+			hpfs_mark_4buffers_dirty(&qbh);
+			hpfs_brelse4(&qbh);
+			dno = up;
+			goto try_it_again;
+		}
+		if (!de_prev->down) goto endm;
+		ndown = de_down_pointer(de_prev);
+		if ((d1 = hpfs_map_dnode(i->i_sb, ndown, &qbh1))) {
+			struct hpfs_dirent *del = dnode_last_de(d1);
+			dlp = del->down ? de_down_pointer(del) : 0;
+			if (!dlp && down) {
+				if (d1->first_free > 2044) {
+					if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
+						printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
+						printk("HPFS: warning: terminating balancing operation\n");
+					}
+					hpfs_brelse4(&qbh1);
+					goto endm;
+				}
+				if (hpfs_sb(i->i_sb)->sb_chk >= 2) {
+					printk("HPFS: warning: unbalanced dnode tree, see hpfs.txt 4 more info\n");
+					printk("HPFS: warning: goin'on\n");
+				}
+				del->length += 4;
+				del->down = 1;
+				d1->first_free += 4;
+			}
+			if (dlp && !down) {
+				del->length -= 4;
+				del->down = 0;
+				d1->first_free -= 4;
+			} else if (down)
+				*(dnode_secno *) ((void *) del + del->length - 4) = down;
+		} else goto endm;
+		if (!(de_cp = kmalloc(de_prev->length, GFP_NOFS))) {
+			printk("HPFS: out of memory for dtree balancing\n");
+			hpfs_brelse4(&qbh1);
+			goto endm;
+		}
+		hpfs_mark_4buffers_dirty(&qbh1);
+		hpfs_brelse4(&qbh1);
+		memcpy(de_cp, de_prev, de_prev->length);
+		hpfs_delete_de(i->i_sb, dnode, de_prev);
+		if (!de_prev->down) {
+			de_prev->length += 4;
+			de_prev->down = 1;
+			dnode->first_free += 4;
+		}
+		*(dnode_secno *) ((void *) de_prev + de_prev->length - 4) = ndown;
+		hpfs_mark_4buffers_dirty(&qbh);
+		hpfs_brelse4(&qbh);
+		for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | (p - 1), 4);
+		for_all_poss(i, hpfs_pos_subst, ((loff_t)up << 4) | p, ((loff_t)up << 4) | (p - 1));
+		if (down) if ((d1 = hpfs_map_dnode(i->i_sb, de_down_pointer(de), &qbh1))) {
+			d1->up = ndown;
+			hpfs_mark_4buffers_dirty(&qbh1);
+			hpfs_brelse4(&qbh1);
+		}
+		hpfs_add_to_dnode(i, ndown, de_cp->name, de_cp->namelen, de_cp, dlp);
+		dno = up;
+		kfree(de_cp);
+		goto try_it_again;
+	}
+	endm:
+	hpfs_mark_4buffers_dirty(&qbh);
+	end:
+	hpfs_brelse4(&qbh);
+}
+
+
+/* Delete dirent from directory */
+
+int hpfs_remove_dirent(struct inode *i, dnode_secno dno, struct hpfs_dirent *de,
+		       struct quad_buffer_head *qbh, int depth)
+{
+	struct dnode *dnode = qbh->data;
+	dnode_secno down = 0;
+	int lock = 0;
+	loff_t t;
+	if (de->first || de->last) {
+		hpfs_error(i->i_sb, "hpfs_remove_dirent: attempt to delete first or last dirent in dnode %08x", dno);
+		hpfs_brelse4(qbh);
+		return 1;
+	}
+	if (de->down) down = de_down_pointer(de);
+	if (depth && (de->down || (de == dnode_first_de(dnode) && de_next_de(de)->last))) {
+		lock = 1;
+		hpfs_lock_creation(i->i_sb);
+		if (hpfs_check_free_dnodes(i->i_sb, FREE_DNODES_DEL)) {
+			hpfs_brelse4(qbh);
+			hpfs_unlock_creation(i->i_sb);
+			return 2;
+		}
+	}
+	i->i_version++;
+	for_all_poss(i, hpfs_pos_del, (t = get_pos(dnode, de)) + 1, 1);
+	hpfs_delete_de(i->i_sb, dnode, de);
+	hpfs_mark_4buffers_dirty(qbh);
+	hpfs_brelse4(qbh);
+	if (down) {
+		dnode_secno a = move_to_top(i, down, dno);
+		for_all_poss(i, hpfs_pos_subst, 5, t);
+		if (a) delete_empty_dnode(i, a);
+		if (lock) hpfs_unlock_creation(i->i_sb);
+		return !a;
+	}
+	delete_empty_dnode(i, dno);
+	if (lock) hpfs_unlock_creation(i->i_sb);
+	return 0;
+}
+
+void hpfs_count_dnodes(struct super_block *s, dnode_secno dno, int *n_dnodes,
+		       int *n_subdirs, int *n_items)
+{
+	struct dnode *dnode;
+	struct quad_buffer_head qbh;
+	struct hpfs_dirent *de;
+	dnode_secno ptr, odno = 0;
+	int c1, c2 = 0;
+	int d1, d2 = 0;
+	go_down:
+	if (n_dnodes) (*n_dnodes)++;
+	if (hpfs_sb(s)->sb_chk)
+		if (hpfs_stop_cycles(s, dno, &c1, &c2, "hpfs_count_dnodes #1")) return;
+	ptr = 0;
+	go_up:
+	if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
+	if (hpfs_sb(s)->sb_chk) if (odno && odno != -1 && dnode->up != odno)
+		hpfs_error(s, "hpfs_count_dnodes: bad up pointer; dnode %08x, down %08x points to %08x", odno, dno, dnode->up);
+	de = dnode_first_de(dnode);
+	if (ptr) while(1) {
+		if (de->down) if (de_down_pointer(de) == ptr) goto process_de;
+		if (de->last) {
+			hpfs_brelse4(&qbh);
+			hpfs_error(s, "hpfs_count_dnodes: pointer to dnode %08x not found in dnode %08x, got here from %08x",
+				ptr, dno, odno);
+			return;
+		}
+		de = de_next_de(de);
+	}
+	next_de:
+	if (de->down) {
+		odno = dno;
+		dno = de_down_pointer(de);
+		hpfs_brelse4(&qbh);
+		goto go_down;
+	}
+	process_de:
+	if (!de->first && !de->last && de->directory && n_subdirs) (*n_subdirs)++;
+	if (!de->first && !de->last && n_items) (*n_items)++;
+	if ((de = de_next_de(de)) < dnode_end_de(dnode)) goto next_de;
+	ptr = dno;
+	dno = dnode->up;
+	if (dnode->root_dnode) {
+		hpfs_brelse4(&qbh);
+		return;
+	}
+	hpfs_brelse4(&qbh);
+	if (hpfs_sb(s)->sb_chk)
+		if (hpfs_stop_cycles(s, ptr, &d1, &d2, "hpfs_count_dnodes #2")) return;
+	odno = -1;
+	goto go_up;
+}
+
+static struct hpfs_dirent *map_nth_dirent(struct super_block *s, dnode_secno dno, int n,
+					  struct quad_buffer_head *qbh, struct dnode **dn)
+{
+	int i;
+	struct hpfs_dirent *de, *de_end;
+	struct dnode *dnode;
+	dnode = hpfs_map_dnode(s, dno, qbh);
+	if (!dnode) return NULL;
+	if (dn) *dn=dnode;
+	de = dnode_first_de(dnode);
+	de_end = dnode_end_de(dnode);
+	for (i = 1; de < de_end; i++, de = de_next_de(de)) {
+		if (i == n) {
+			return de;
+		}	
+		if (de->last) break;
+	}
+	hpfs_brelse4(qbh);
+	hpfs_error(s, "map_nth_dirent: n too high; dnode = %08x, requested %08x", dno, n);
+	return NULL;
+}
+
+dnode_secno hpfs_de_as_down_as_possible(struct super_block *s, dnode_secno dno)
+{
+	struct quad_buffer_head qbh;
+	dnode_secno d = dno;
+	dnode_secno up = 0;
+	struct hpfs_dirent *de;
+	int c1, c2 = 0;
+
+	again:
+	if (hpfs_sb(s)->sb_chk)
+		if (hpfs_stop_cycles(s, d, &c1, &c2, "hpfs_de_as_down_as_possible"))
+			return d;
+	if (!(de = map_nth_dirent(s, d, 1, &qbh, NULL))) return dno;
+	if (hpfs_sb(s)->sb_chk)
+		if (up && ((struct dnode *)qbh.data)->up != up)
+			hpfs_error(s, "hpfs_de_as_down_as_possible: bad up pointer; dnode %08x, down %08x points to %08x", up, d, ((struct dnode *)qbh.data)->up);
+	if (!de->down) {
+		hpfs_brelse4(&qbh);
+		return d;
+	}
+	up = d;
+	d = de_down_pointer(de);
+	hpfs_brelse4(&qbh);
+	goto again;
+}
+
+struct hpfs_dirent *map_pos_dirent(struct inode *inode, loff_t *posp,
+				   struct quad_buffer_head *qbh)
+{
+	loff_t pos;
+	unsigned c;
+	dnode_secno dno;
+	struct hpfs_dirent *de, *d;
+	struct hpfs_dirent *up_de;
+	struct hpfs_dirent *end_up_de;
+	struct dnode *dnode;
+	struct dnode *up_dnode;
+	struct quad_buffer_head qbh0;
+
+	pos = *posp;
+	dno = pos >> 6 << 2;
+	pos &= 077;
+	if (!(de = map_nth_dirent(inode->i_sb, dno, pos, qbh, &dnode)))
+		goto bail;
+
+	/* Going to the next dirent */
+	if ((d = de_next_de(de)) < dnode_end_de(dnode)) {
+		if (!(++*posp & 077)) {
+			hpfs_error(inode->i_sb, "map_pos_dirent: pos crossed dnode boundary; pos = %08x", *posp);
+			goto bail;
+		}
+		/* We're going down the tree */
+		if (d->down) {
+			*posp = ((loff_t) hpfs_de_as_down_as_possible(inode->i_sb, de_down_pointer(d)) << 4) + 1;
+		}
+	
+		return de;
+	}
+
+	/* Going up */
+	if (dnode->root_dnode) goto bail;
+
+	if (!(up_dnode = hpfs_map_dnode(inode->i_sb, dnode->up, &qbh0)))
+		goto bail;
+
+	end_up_de = dnode_end_de(up_dnode);
+	c = 0;
+	for (up_de = dnode_first_de(up_dnode); up_de < end_up_de;
+	     up_de = de_next_de(up_de)) {
+		if (!(++c & 077)) hpfs_error(inode->i_sb,
+			"map_pos_dirent: pos crossed dnode boundary; dnode = %08x", dnode->up);
+		if (up_de->down && de_down_pointer(up_de) == dno) {
+			*posp = ((loff_t) dnode->up << 4) + c;
+			hpfs_brelse4(&qbh0);
+			return de;
+		}
+	}
+	
+	hpfs_error(inode->i_sb, "map_pos_dirent: pointer to dnode %08x not found in parent dnode %08x",
+		dno, dnode->up);
+	hpfs_brelse4(&qbh0);
+	
+	bail:
+	*posp = 12;
+	return de;
+}
+
+/* Find a dirent in tree */
+
+struct hpfs_dirent *map_dirent(struct inode *inode, dnode_secno dno, char *name, unsigned len,
+			       dnode_secno *dd, struct quad_buffer_head *qbh)
+{
+	struct dnode *dnode;
+	struct hpfs_dirent *de;
+	struct hpfs_dirent *de_end;
+	int c1, c2 = 0;
+
+	if (!S_ISDIR(inode->i_mode)) hpfs_error(inode->i_sb, "map_dirent: not a directory\n");
+	again:
+	if (hpfs_sb(inode->i_sb)->sb_chk)
+		if (hpfs_stop_cycles(inode->i_sb, dno, &c1, &c2, "map_dirent")) return NULL;
+	if (!(dnode = hpfs_map_dnode(inode->i_sb, dno, qbh))) return NULL;
+	
+	de_end = dnode_end_de(dnode);
+	for (de = dnode_first_de(dnode); de < de_end; de = de_next_de(de)) {
+		int t = hpfs_compare_names(inode->i_sb, name, len, de->name, de->namelen, de->last);
+		if (!t) {
+			if (dd) *dd = dno;
+			return de;
+		}
+		if (t < 0) {
+			if (de->down) {
+				dno = de_down_pointer(de);
+				hpfs_brelse4(qbh);
+				goto again;
+			}
+		break;
+		}
+	}
+	hpfs_brelse4(qbh);
+	return NULL;
+}
+
+/*
+ * Remove empty directory. In normal cases it is only one dnode with two
+ * entries, but we must handle also such obscure cases when it's a tree
+ * of empty dnodes.
+ */
+
+void hpfs_remove_dtree(struct super_block *s, dnode_secno dno)
+{
+	struct quad_buffer_head qbh;
+	struct dnode *dnode;
+	struct hpfs_dirent *de;
+	dnode_secno d1, d2, rdno = dno;
+	while (1) {
+		if (!(dnode = hpfs_map_dnode(s, dno, &qbh))) return;
+		de = dnode_first_de(dnode);
+		if (de->last) {
+			if (de->down) d1 = de_down_pointer(de);
+			else goto error;
+			hpfs_brelse4(&qbh);
+			hpfs_free_dnode(s, dno);
+			dno = d1;
+		} else break;
+	}
+	if (!de->first) goto error;
+	d1 = de->down ? de_down_pointer(de) : 0;
+	de = de_next_de(de);
+	if (!de->last) goto error;
+	d2 = de->down ? de_down_pointer(de) : 0;
+	hpfs_brelse4(&qbh);
+	hpfs_free_dnode(s, dno);
+	do {
+		while (d1) {
+			if (!(dnode = hpfs_map_dnode(s, dno = d1, &qbh))) return;
+			de = dnode_first_de(dnode);
+			if (!de->last) goto error;
+			d1 = de->down ? de_down_pointer(de) : 0;
+			hpfs_brelse4(&qbh);
+			hpfs_free_dnode(s, dno);
+		}
+		d1 = d2;
+		d2 = 0;
+	} while (d1);
+	return;
+	error:
+	hpfs_brelse4(&qbh);
+	hpfs_free_dnode(s, dno);
+	hpfs_error(s, "directory %08x is corrupted or not empty", rdno);
+}
+
+/* 
+ * Find dirent for specified fnode. Use truncated 15-char name in fnode as
+ * a help for searching.
+ */
+
+struct hpfs_dirent *map_fnode_dirent(struct super_block *s, fnode_secno fno,
+				     struct fnode *f, struct quad_buffer_head *qbh)
+{
+	char *name1;
+	char *name2;
+	int name1len, name2len;
+	struct dnode *d;
+	dnode_secno dno, downd;
+	struct fnode *upf;
+	struct buffer_head *bh;
+	struct hpfs_dirent *de, *de_end;
+	int c;
+	int c1, c2 = 0;
+	int d1, d2 = 0;
+	name1 = f->name;
+	if (!(name2 = kmalloc(256, GFP_NOFS))) {
+		printk("HPFS: out of memory, can't map dirent\n");
+		return NULL;
+	}
+	if (f->len <= 15)
+		memcpy(name2, name1, name1len = name2len = f->len);
+	else {
+		memcpy(name2, name1, 15);
+		memset(name2 + 15, 0xff, 256 - 15);
+		/*name2[15] = 0xff;*/
+		name1len = 15; name2len = 256;
+	}
+	if (!(upf = hpfs_map_fnode(s, f->up, &bh))) {
+		kfree(name2);
+		return NULL;
+	}	
+	if (!upf->dirflag) {
+		brelse(bh);
+		hpfs_error(s, "fnode %08x has non-directory parent %08x", fno, f->up);
+		kfree(name2);
+		return NULL;
+	}
+	dno = upf->u.external[0].disk_secno;
+	brelse(bh);
+	go_down:
+	downd = 0;
+	go_up:
+	if (!(d = hpfs_map_dnode(s, dno, qbh))) {
+		kfree(name2);
+		return NULL;
+	}
+	de_end = dnode_end_de(d);
+	de = dnode_first_de(d);
+	if (downd) {
+		while (de < de_end) {
+			if (de->down) if (de_down_pointer(de) == downd) goto f;
+			de = de_next_de(de);
+		}
+		hpfs_error(s, "pointer to dnode %08x not found in dnode %08x", downd, dno);
+		hpfs_brelse4(qbh);
+		kfree(name2);
+		return NULL;
+	}
+	next_de:
+	if (de->fnode == fno) {
+		kfree(name2);
+		return de;
+	}
+	c = hpfs_compare_names(s, name1, name1len, de->name, de->namelen, de->last);
+	if (c < 0 && de->down) {
+		dno = de_down_pointer(de);
+		hpfs_brelse4(qbh);
+		if (hpfs_sb(s)->sb_chk)
+			if (hpfs_stop_cycles(s, dno, &c1, &c2, "map_fnode_dirent #1")) {
+			kfree(name2);
+			return NULL;
+		}
+		goto go_down;
+	}
+	f:
+	if (de->fnode == fno) {
+		kfree(name2);
+		return de;
+	}
+	c = hpfs_compare_names(s, name2, name2len, de->name, de->namelen, de->last);
+	if (c < 0 && !de->last) goto not_found;
+	if ((de = de_next_de(de)) < de_end) goto next_de;
+	if (d->root_dnode) goto not_found;
+	downd = dno;
+	dno = d->up;
+	hpfs_brelse4(qbh);
+	if (hpfs_sb(s)->sb_chk)
+		if (hpfs_stop_cycles(s, downd, &d1, &d2, "map_fnode_dirent #2")) {
+			kfree(name2);
+			return NULL;
+		}
+	goto go_up;
+	not_found:
+	hpfs_brelse4(qbh);
+	hpfs_error(s, "dirent for fnode %08x not found", fno);
+	kfree(name2);
+	return NULL;
+}