dnode.c

嵌入式系统设计与实例开发实验教材二源码 多线程应用程序设计 串行端口程序设计 AD接口实验 CAN总线通信实验 GPS通信实验 Linux内核移植与编译实验 IC卡读写实验 SD驱动使

				fnode->u.external[0].disk_secno = down;
				mark_buffer_dirty(bh);
				brelse(bh);
			}
			i->i_hpfs_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_KERNEL))) {
			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 (i->i_sb->s_hpfs_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 (i->i_sb->s_hpfs_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_KERNEL))) {
			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 = ++event;
	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 (s->s_hpfs_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 (s->s_hpfs_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 (s->s_hpfs_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 (s->s_hpfs_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 (s->s_hpfs_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 (inode->i_sb->s_hpfs_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_KERNEL))) {
		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 (s->s_hpfs_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 (s->s_hpfs_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;
}