ext2subs.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

		addr = *(((uint *)buf->iobuf) + block);
		putbuf(buf);
		putbuf(ibuf);
		return addr;	
	}
	block -= addr_per_block;
	
	/* double indirect blocks */
	if(block < (1 << (addr_per_block_bits * 2))) {
		addr = inode->i_block[EXT2_DIND_BLOCK];
		if (!addr) goto error;
		buf = getbuf(xf, addr);
		if( !buf ) goto error;
		addr = *(((uint *)buf->iobuf) + (block >> addr_per_block_bits));
		putbuf(buf);
		buf = getbuf(xf, addr);
		if( !buf ) goto error;
		addr = *(((uint *)buf->iobuf) + (block & (addr_per_block - 1)));
		putbuf(buf);
		putbuf(ibuf);
		return addr;
	}
	block -= (1 << (addr_per_block_bits * 2));

	/* triple indirect blocks */
	addr = inode->i_block[EXT2_TIND_BLOCK];
	if(!addr) goto error;
	buf = getbuf(xf, addr);
	if( !buf ) goto error;
	addr = *(((uint *)buf->iobuf) + (block >> (addr_per_block_bits * 2)));
	putbuf(buf);
	if(!addr) goto error;
	buf = getbuf(xf, addr);
	if( !buf ) goto error;
	addr = *(((uint *)buf->iobuf) +
			((block >> addr_per_block_bits) & (addr_per_block - 1)));
	putbuf(buf);
	if(!addr) goto error;
	buf = getbuf(xf, addr);
	if( !buf ) goto error;
	addr = *(((uint *)buf->iobuf) + (block & (addr_per_block - 1)));
	putbuf(buf);
	putbuf(ibuf);
	return addr;
error:
	putbuf(ibuf);
	return 0;
}
long
writefile(Xfile *f, void *vbuf, vlong offset, long count)
{
	Xfs *xf = f->xf;
	Inode *inode;
	Iobuf *buffer, *ibuf;
	long w;
	int len, o, cur_block, baddr;
	char *buf;

	buf = vbuf;

	ibuf = getbuf(xf, f->bufaddr);
	if( !ibuf )
		return -1;
	inode = ((Inode *)ibuf->iobuf) + f->bufoffset;

	chat("write block [ ");
	cur_block = offset / xf->block_size;
	o = offset % xf->block_size;
	w = 0;
	while( count > 0 ){
		baddr = getblk(f, cur_block++);
		if( baddr <= 0 )
			goto end;
		buffer = getbuf(xf, baddr);
		if( !buffer )
			goto end;
		chat("%d ", baddr);
		len = xf->block_size - o;
		if( len > count )
			len = count;
		memcpy(&buffer->iobuf[o], &buf[w], len);
		dirtybuf(buffer);
		w += len;
		count -= len;
		o = 0;
		putbuf(buffer);
	}
end:
	if( inode->i_size < offset + w )
		inode->i_size = offset + w;
	inode->i_atime = inode->i_mtime = time(0);
	dirtybuf(ibuf);
	putbuf(ibuf);
	chat("]...");
	if( errno )
		return -1;
	return w;
}
int 
new_block( Xfile *f, int goal )
{
	Xfs *xf= f->xf;
	int group, block, baddr, k, redo;
	ulong lmap;
	char *p, *r;
	Iobuf *buf;
	Ext2 ed, es, eb;
	
	es = getext2(xf, EXT2_SUPER, 0);
	redo = 0;
 
repeat:
	
	if( goal < es.u.sb->s_first_data_block || goal >= es.u.sb->s_blocks_count )
		goal = es.u.sb->s_first_data_block;
	group = (goal - es.u.sb->s_first_data_block) / xf->blocks_per_group;

	ed = getext2(xf, EXT2_DESC, group);
	eb = getext2(xf, EXT2_BBLOCK, group);

	/* 
	 * First, test if goal block is free
	 */
	if( ed.u.gd->bg_free_blocks_count > 0 ){
		block = (goal - es.u.sb->s_first_data_block) % xf->blocks_per_group;
		
		if( !test_bit(block, eb.u.bmp) )
			goto got_block;
		
		if( block ){
			/*
			 * goal wasn't free ; search foward for a free 
			 * block within the next 32 blocks
			*/
			
			lmap = (((ulong *)eb.u.bmp)[block>>5]) >>
					((block & 31) + 1);
			if( block < xf->blocks_per_group - 32 )
				lmap |= (((ulong *)eb.u.bmp)[(block>>5)+1]) <<
					( 31-(block & 31) );
			else
				lmap |= 0xffffffff << ( 31-(block & 31) );

			if( lmap != 0xffffffffl ){
				k = ffz(lmap) + 1;
				if( (block + k) < xf->blocks_per_group ){
					block += k;
					goto got_block;
				}
			}			
		}
		/*
		 * Search in the remaider of the group
		*/
		p = eb.u.bmp + (block>>3);
		r = memscan(p, 0, (xf->blocks_per_group - block + 7) >>3);
		k = ( r - eb.u.bmp )<<3;
		if( k < xf->blocks_per_group ){
			block = k;
			goto search_back;
		}
		k = find_next_zero_bit((unsigned long *)eb.u.bmp, 
						xf->blocks_per_group>>3, block);
		if( k < xf->blocks_per_group ){
			block = k;
			goto got_block;
		}
	}

	/*
	 * Search the rest of groups
	*/
	putext2(ed); putext2(eb);
	for(k=0 ; k < xf->ngroups ; k++){
		group++;
		if( group >= xf->ngroups )
			group = 0;
		ed = getext2(xf, EXT2_DESC, group);
		if( ed.u.gd->bg_free_blocks_count > 0 )
			break;
		putext2(ed);
	}
	if( redo && group == xf->ngroups-1 ){
		putext2(ed);
		goto full;
	}
	if( k >=xf->ngroups ){
		/*
		 * All groups are full or
		 * we have retry (because the last block) and all other
		 * groups are also full.
		*/
full:	
		chat("no free blocks ...");
	 	putext2(es); 
		errno = Enospace;
		return 0;
	}
	eb = getext2(xf, EXT2_BBLOCK, group);
	r = memscan(eb.u.bmp,  0, xf->blocks_per_group>>3);
	block = (r - eb.u.bmp) <<3;
	if( block < xf->blocks_per_group )
		goto search_back;
	else
		block = find_first_zero_bit((ulong *)eb.u.bmp,
								xf->blocks_per_group>>3);
	if( block >= xf->blocks_per_group ){
		chat("Free block count courupted for block group %d...", group);
		putext2(ed); putext2(eb); putext2(es);
		errno = Ecorrupt;
		return 0;
	}


search_back:
	/*
	 * A free byte was found in the block. Now search backwards up
	 * to 7 bits to find the start of this group of free block.
	*/
	for(k=0 ; k < 7 && block > 0 && 
		!test_bit(block-1, eb.u.bmp) ; k++, block--);

got_block:

	baddr = block + (group * xf->blocks_per_group) + 
				es.u.sb->s_first_data_block;
	
	if( baddr == ed.u.gd->bg_block_bitmap ||
	     baddr == ed.u.gd->bg_inode_bitmap ){
		chat("Allocating block in system zone...");
		putext2(ed); putext2(eb); putext2(es);
		errno = Eintern;
		return 0;
	}

	if( set_bit(block, eb.u.bmp) ){
		chat("bit already set (%d)...", block);
		putext2(ed); putext2(eb); putext2(es);
		errno = Ecorrupt;
		return 0;
	}
	dirtyext2(eb);
	
	if( baddr >= es.u.sb->s_blocks_count ){
		chat("block >= blocks count...");
		errno = Eintern;
error:
		clear_bit(block, eb.u.bmp);
		putext2(eb); putext2(ed); putext2(es);
		return 0;
	}
	
	buf = getbuf(xf, baddr);
	if( !buf ){
		if( !redo ){
			/*
			 * It's perhaps the last block of the disk and 
			 * it can't be acceded because the last sector.
			 * Therefore, we try one more time with goal at 0
			 * to force scanning all groups.
			*/
			clear_bit(block, eb.u.bmp);
			putext2(eb); putext2(ed);
			goal = 0; errno = 0; redo++;
			goto repeat;
		}
		goto error;
	}
	memset(&buf->iobuf[0], 0, xf->block_size);
	dirtybuf(buf);
	putbuf(buf);

	es.u.sb->s_free_blocks_count--;
	dirtyext2(es);
	ed.u.gd->bg_free_blocks_count--;
	dirtyext2(ed);

	putext2(eb);
	putext2(ed);
	putext2(es);
	chat("new ");
	return baddr;
}
int
getblk(Xfile *f, int block)
{
	Xfs *xf = f->xf;
	int baddr;
	int addr_per_block = xf->addr_per_block;

	if (block < 0) {
		chat("getblk() block < 0 ...");
		return 0;
	}
	if(block > EXT2_NDIR_BLOCKS + addr_per_block +
			addr_per_block * addr_per_block +
			addr_per_block * addr_per_block * addr_per_block ){
		chat("getblk() block > big...");
		errno = Eintern;
		return 0;
	}
	if( block < EXT2_NDIR_BLOCKS )
		return inode_getblk(f, block);
	block -= EXT2_NDIR_BLOCKS;	
	if( block < addr_per_block ){
		baddr = inode_getblk(f, EXT2_IND_BLOCK);
		baddr = block_getblk(f, baddr, block);
		return baddr;
	}
	block -= addr_per_block;
	if( block < addr_per_block * addr_per_block  ){
		baddr = inode_getblk(f, EXT2_DIND_BLOCK);
		baddr = block_getblk(f, baddr, block / addr_per_block);
		baddr = block_getblk(f, baddr, block & ( addr_per_block-1));
		return baddr; 
	}
	block -= addr_per_block * addr_per_block;
	baddr = inode_getblk(f, EXT2_TIND_BLOCK);
	baddr = block_getblk(f, baddr, block / (addr_per_block * addr_per_block));
	baddr = block_getblk(f, baddr, (block / addr_per_block) & ( addr_per_block-1));
	return block_getblk(f, baddr, block & ( addr_per_block-1));
}
int
block_getblk(Xfile *f, int rb, int nr)
{
	Xfs *xf = f->xf;
	Inode *inode;
	int tmp, goal = 0;
	int blocks = xf->block_size / 512;
	Iobuf *buf, *ibuf;
	uint *p;
	Ext2 es;

	if( !rb )
		return 0;

	buf = getbuf(xf, rb);
	if( !buf )
		return 0;
	p = (uint *)(buf->iobuf) + nr;
	if( *p ){
		tmp = *p;
		putbuf(buf);
		return tmp;
	}

	for(tmp=nr - 1 ; tmp >= 0 ; tmp--){
		if( ((uint *)(buf->iobuf))[tmp] ){
			goal = ((uint *)(buf->iobuf))[tmp];
			break;
		}
	}
	if( !goal ){
		es = getext2(xf, EXT2_SUPER, 0);
		goal = (((f->inbr -1) / xf->inodes_per_group) *
				xf->blocks_per_group) +
				es.u.sb->s_first_data_block;
		putext2(es);
	}
	
	tmp = new_block(f, goal);
	if( !tmp ){
		putbuf(buf);
		return 0;
	}

	*p = tmp;
	dirtybuf(buf);
	putbuf(buf);
	
	ibuf = getbuf(xf, f->bufaddr);
	if( !ibuf )
		return -1;
	inode = ((Inode *)ibuf->iobuf) + f->bufoffset;
	inode->i_blocks += blocks;
	dirtybuf(ibuf);
	putbuf(ibuf);

	return tmp;
}
int 
inode_getblk(Xfile *f, int block)
{
	Xfs *xf = f->xf;
	Inode *inode;
	Iobuf *ibuf;
	int tmp, goal = 0;
	int blocks = xf->block_size / 512;
	Ext2 es;

	ibuf = getbuf(xf, f->bufaddr);
	if( !ibuf )
		return -1;
	inode = ((Inode *)ibuf->iobuf) + f->bufoffset;


	if( inode->i_block[block] ){
		putbuf(ibuf);
		return inode->i_block[block];
	}

	for(tmp=block - 1 ; tmp >= 0 ; tmp--){
		if( inode->i_block[tmp] ){
			goal = inode->i_block[tmp];
			break;
		}
	}
	if( !goal ){
		es = getext2(xf, EXT2_SUPER, 0);
		goal = (((f->inbr -1) / xf->inodes_per_group) *
				xf->blocks_per_group) +
				es.u.sb->s_first_data_block;
		putext2(es);
	}

	tmp = new_block(f, goal);
	if( !tmp ){
		putbuf(ibuf);
		return 0;
	}

	inode->i_block[block] = tmp;
	inode->i_blocks += blocks;
	dirtybuf(ibuf);
	putbuf(ibuf);

	return tmp;
}
int 
new_inode(Xfile *f, int mode)
{
	Xfs *xf = f->xf;
	Inode *inode, *finode;
	Iobuf *buf, *ibuf;
	int ave,group, i, j;
	Ext2 ed, es, eb;

	group = -1;

	es = getext2(xf, EXT2_SUPER, 0);

	if( S_ISDIR(mode) ){	/* create directory inode */
		ave = es.u.sb->s_free_inodes_count / xf->ngroups;
		for(i=0 ; i < xf->ngroups ; i++){
			ed = getext2(xf, EXT2_DESC, i);
			if( ed.u.gd->bg_free_inodes_count &&
					ed.u.gd->bg_free_inodes_count >= ave ){
				if( group<0 || ed.u.gd->bg_free_inodes_count >
								ed.u.gd->bg_free_inodes_count )
					group = i;
			}
			putext2(ed);
		}

	}else{		/* create file inode */
		/* Try to put inode in its parent directory */
		i = (f->inbr -1) / xf->inodes_per_group;
		ed = getext2(xf, EXT2_DESC, i);
		if( ed.u.gd->bg_free_inodes_count ){
			group = i;
			putext2(ed);
		}else{
			/*
			 * Use a quadratic hash to find a group whith
			 * a free inode
			 */
			putext2(ed);
			for( j=1 ; j < xf->ngroups ; j <<= 1){
				i += j;
				if( i >= xf->ngroups )
					i -= xf->ngroups;
				ed = getext2(xf, EXT2_DESC, i);
				if( ed.u.gd->bg_free_inodes_count ){
					group = i;
					putext2(ed);
					break;
				}
				putext2(ed);
			}
		}
		if( group < 0 ){
			/* try a linear search */
			i = ((f->inbr -1) / xf->inodes_per_group) + 1;
			for(j=2 ; j < xf->ngroups ; j++){
				if( ++i >= xf->ngroups )
					i = 0;
				ed = getext2(xf, EXT2_DESC, i);
				if( ed.u.gd->bg_free_inodes_count ){
					group = i;
					putext2(ed);
					break;
				}
				putext2(ed);
			}
		}

	}
	if( group < 0 ){
		chat("group < 0...");
		putext2(es);
		return 0;
	}
	ed = getext2(xf, EXT2_DESC, group);
	eb = getext2(xf, EXT2_BINODE, group);
	if( (j = find_first_zero_bit(eb.u.bmp, 
			xf->inodes_per_group>>3)) < xf->inodes_per_group){
		if( set_bit(j, eb.u.bmp) ){
			chat("inode %d of group %d is already allocated...", j, group);
			putext2(ed); putext2(eb); putext2(es);
			errno = Ecorrupt;
			return 0;
		}
		dirtyext2(eb);
	}else if( ed.u.gd->bg_free_inodes_count != 0 ){
		chat("free inodes count corrupted for group %d...", group);
		putext2(ed); putext2(eb); putext2(es);
		errno = Ecorrupt;
		return 0;
	}
	i = j;
	j += group * xf->inodes_per_group + 1;
	if( j < EXT2_FIRST_INO || j >= es.u.sb->s_inodes_count ){
		chat("reserved inode or inode > inodes count...");
		errno = Ecorrupt;
error:
		clear_bit(i, eb.u.bmp);
		putext2(eb); putext2(ed); putext2(es);
		return 0;
	}
	
	buf = getbuf(xf, ed.u.gd->bg_inode_table +
			(((j-1) % xf->inodes_per_group) / 
			xf->inodes_per_block));
	if( !buf )
		goto error;
	inode = ((struct Inode *) buf->iobuf) + 
		((j-1) % xf->inodes_per_block);
	memset(inode, 0, sizeof(Inode));
	inode->i_mode = mode;
	inode->i_links_count = 1;
	inode->i_uid = DEFAULT_UID;
	inode->i_gid = DEFAULT_GID;
	inode->i_mtime = inode->i_atime = inode->i_ctime = time(0);
	dirtybuf(buf);

	ibuf = getbuf(xf, f->bufaddr);
	if( !ibuf ){
		putbuf(buf);
		goto error;
	}
	finode = ((Inode *)ibuf->iobuf) + f->bufoffset;
	inode->i_flags = finode->i_flags;
	inode->i_uid = finode->i_uid;
	inode->i_gid = finode->i_gid;
	dirtybuf(ibuf);
	putbuf(ibuf);

	putbuf(buf);

	ed.u.gd->bg_free_inodes_count--;
	if( S_ISDIR(mode) )
		ed.u.gd->bg_used_dirs_count++;
	dirtyext2(ed);

	es.u.sb->s_free_inodes_count--;
	dirtyext2(es);

	putext2(eb);
	putext2(ed);
	putext2(es);

	return j;
}
int
create_file(Xfile *fdir, char *name, int mode)
{
	int inr;

	inr = new_inode(fdir, mode);
	if( !inr ){
		chat("create one new inode failed...");
		return -1;
	}
	if( add_entry(fdir, name, inr) < 0 ){
		chat("add entry failed...");	
		free_inode(fdir->xf, inr);
		return -1;
	}

	return inr;
}
void
free_inode( Xfs *xf, int inr)
{
	Inode *inode;
	ulong b, bg;
	Iobuf *buf;
	Ext2 ed, es, eb;

	bg = (inr -1) / xf->inodes_per_group;
	b = (inr -1) % xf->inodes_per_group;

	ed = getext2(xf, EXT2_DESC, bg);
	buf = getbuf(xf, ed.u.gd->bg_inode_table +
			(b / xf->inodes_per_block));
	if( !buf ){
		putext2(ed);
		return;
	}
	inode = ((struct Inode *) buf->iobuf) + 
		((inr-1) % xf->inodes_per_block);

	if( S_ISDIR(inode->i_mode) )
		ed.u.gd->bg_used_dirs_count--;
	memset(inode, 0, sizeof(Inode));
	inode->i_dtime = time(0);
	dirtybuf(buf);
	putbuf(buf);

	ed.u.gd->bg_free_inodes_count++;
	dirtyext2(ed);
	putext2(ed);

	eb = getext2(xf, EXT2_BINODE, bg);