fd.c

操作系统课程设计

/* fd.c */

#include "fd.h"

/* BLOCK COUNT PER BLOCK */
#define BCPB   (BLOCK_SIZE/sizeof(struct blk_index))
#define DIRECT (10 * BLOCK_SIZE)
#define SINGLE (DIRECT + BCPB * BLOCK_SIZE)
#define DOUBLE (SINGLE + BCPB * BCPB * BLOCK_SIZE)
#define TRIPLE (DOUBLE + BCPB * BCPB * BCPB * BLOCK_SIZE)

//根据inode号找到inode所在，返回inode
struct fs_inode find_inode( FILE *fp, int ind_no)
{
    struct fs_inode inode;
    fseek( fp, INODE_OFFSET(ind_no), SEEK_SET);
    fread( &inode, sizeof(inode), 1, fp);
    return inode;
}


//在inode号为dir_ind_no的目录下查找该目录的inode记录表，返回一个inode表项
struct fd_entry find_entry( FILE *fp, int dir_ind_no, int file_inode_no)
{
    int blk_no;
    long offset;
    struct fd_entry file_entry;
    struct fs_inode dir_inode = find_inode( fp, dir_ind_no);//得到该目录的inode

	//一个目录只是记录了该目录的inode记录表，遍历该目录直到找到为止
    for( offset=0; offset<dir_inode.size; offset+=sizeof(file_entry)){
	
	blk_no = blk_map(fp, dir_ind_no, offset);//这一句可不可以删？
	fseek( fp, (SEEK_BLK(blk_map(fp,dir_ind_no,offset%BLOCK_SIZE))+offset%BLOCK_SIZE), SEEK_SET);
	fread( &file_entry, sizeof(file_entry), 1, fp);

	if(file_entry.inode_no == file_inode_no) /* get it */
	    break;
    }
    return file_entry;
}

//查找结点号为dir_ind_no的目录下是否存在名file为的文件/目录
int fd_exist( FILE *fp, int dir_ind_no, const char *file)
{
    struct fs_inode inode = find_inode( fp, dir_ind_no);

    int blk_no;
    long fd_offset;		//在该目录下的偏移量
    struct fd_entry entry;

    /* check from entry 0, do not neglect '.' and '..' */
    for( fd_offset=0; fd_offset<inode.size; fd_offset+=sizeof(entry)){
	
	//比较该目录下每条表项的名
	blk_no = blk_map( fp, dir_ind_no, fd_offset); //表项所处块号
	fseek( fp, (SEEK_BLK(blk_no) + (fd_offset%BLOCK_SIZE)), SEEK_SET);//找到表项在整个文件系统中的地址
	fread( &entry, sizeof(entry), 1, fp);//读出该表项

	if(!strcmp( file, entry.name)) //如果找到
	    return entry.inode_no;
    }
    
    return -1;			//文件不存在
}



//分配一个磁盘块，并返回磁盘块号
int alc_blk( FILE *fp, int ind_no)
{
    struct fs_inode inode = find_inode( fp, ind_no);//每次分配磁盘块后inode的信息都会变化，重新读出文件已分配空间的大小 
    if(inode.size + BLOCK_SIZE > TRIPLE) //文件太大，分配失败，最大只能分配TRIPLE个字节
		return -1;
	
    if(inode.size == 0){//分配第一块磁盘块
		inode.addr[0] = get_blk(fp);//首个磁盘块在文件系统中是第几个磁盘块，即记录第一个磁盘块的块号
		inode.size += BLOCK_SIZE;
		update_ind( fp, ind_no, inode);
		return inode.addr[0];
    }
	
	//先假设分配一块，看是否需要间接索引块
    inode.size += BLOCK_SIZE;
    update_ind( fp, ind_no, inode);
	
    int i, tmp_size=inode.size-1;
    if(tmp_size <= DIRECT){
		
		i = tmp_size / BLOCK_SIZE;//实际分配的第i块对应addr[i-1]（addr从0开始），所以才有tmp_size=inode.size-1，这样
								//i = tmp_size / BLOCK_SIZE得到的i就比实际分配的块号少1.
		if(inode.addr[i] == -1)	/* if the addr was 'blank' */
			inode.addr[i] = get_blk(fp);//获得磁盘块号
		update_ind( fp, ind_no, inode);
		
		return inode.addr[i];
    }
    else if(tmp_size <= SINGLE){
		
		if(inode.addr[10] == -1){ /* if first time through DIRECT */
			inode.addr[10] = get_blk(fp);
			update_ind( fp, ind_no, inode);
		}
		
		tmp_size -= DIRECT;
		i = tmp_size / BLOCK_SIZE;
		
		struct blk_index entry;
		entry.blk_no = get_blk(fp);//记住获得的磁盘块号作索引
		
		fseek( fp, (SEEK_BLK(inode.addr[10])+i*sizeof(entry)), SEEK_SET);
		fwrite( &entry, sizeof(entry), 1, fp);
		
		return entry.blk_no;
    }
    else if(tmp_size <= DOUBLE){
		
		if(inode.addr[11] == -1){ /* if first time through SINGLE */
			inode.addr[11] == get_blk(fp);
			update_ind( fp, ind_no, inode);
		}
		
		tmp_size = tmp_size - DIRECT - SINGLE;
		i = tmp_size / (BCPB * BLOCK_SIZE); //二次间接中在一级表的索引编号，即第几个磁盘块地址记录
		
		int double_blk_no;
		struct blk_index entry;
		if((tmp_size / BLOCK_SIZE) % BCPB == 1){ /* need new block to store blocks */
			
			entry.blk_no = get_blk(fp);
			fseek( fp, (SEEK_BLK(inode.addr[11])+i*sizeof(entry)), SEEK_SET);
			fwrite( &entry, sizeof(entry), 1, fp);//写一个二级表在一级表中的过索引
			
			double_blk_no = entry.blk_no;//二级表所在的磁盘块号
		}
		else{
			fseek( fp, (SEEK_BLK(inode.addr[11])+i*sizeof(entry)), SEEK_SET);
			fread( &entry, sizeof(entry), 1, fp);//读一个二级表在一级表中的索引
			double_blk_no = entry.blk_no;//二级表所在的磁盘块号
		}
		
		entry.blk_no = get_blk(fp);	    //在这里分配新块，即是文件的新块
		i = (tmp_size / BLOCK_SIZE) % BCPB; //在二级表中是第几个记录
		fseek( fp, (SEEK_BLK(double_blk_no)+i*sizeof(entry)), SEEK_SET);
		fwrite( &entry, sizeof(entry), 1, fp);//记住分配新块的地址
		
		return entry.blk_no;
    }
    else{			/* TRIPLE */
		
		if(inode.addr[12] == -1){ /* if first tiem through DOUBLE */
			inode.addr[12] = get_blk(fp);
			update_ind( fp, ind_no, inode);
		}
		
		tmp_size = tmp_size - DIRECT - SINGLE - DOUBLE;
		i = tmp_size / ((int)pow( BCPB, 2) * BLOCK_SIZE); /* get triple indirect block index */
		
		int double_blk_no;
		struct blk_index entry;
		if((tmp_size / BLOCK_SIZE) % (int)pow( BCPB, 2) == 1){ /* need new block to store blocks */
			
			entry.blk_no = get_blk(fp);
			fseek( fp, (SEEK_BLK(inode.addr[12])+i*sizeof(entry)), SEEK_SET);
			fwrite( &entry, sizeof(entry), 1, fp);
			
			double_blk_no = entry.blk_no;
		}
		else{			/* get the triple block number */
			fseek( fp, (SEEK_BLK(inode.addr[11])+i*sizeof(entry)), SEEK_SET);
			fread( &entry, sizeof(entry), 1, fp);
			double_blk_no = entry.blk_no;
		}
		
		tmp_size %= ( double_blk_no * (int)pow( BCPB, 2) * BLOCK_SIZE);
		i = (tmp_size / BLOCK_SIZE) % (int)pow( BCPB, 2);
		
		int single_blk_no;
		if((tmp_size / BLOCK_SIZE) % BCPB == 1){ /* need new block to store blocks */
			
			entry.blk_no = get_blk(fp);
			fseek( fp, (SEEK_BLK(double_blk_no)+i*sizeof(entry)), SEEK_SET);
			fwrite( &entry, sizeof(entry), 1, fp);
			
			single_blk_no = entry.blk_no;
		}
		else{
			fseek( fp, (SEEK_BLK(double_blk_no)+i*sizeof(entry)), SEEK_SET);
			fread( &entry, sizeof(entry), 1, fp);
			single_blk_no = entry.blk_no;
		}
		
		entry.blk_no = get_blk(fp);
		i = (tmp_size / BLOCK_SIZE) % BCPB;
		fseek( fp, (SEEK_BLK(single_blk_no)+i*sizeof(entry)), SEEK_SET);
		fwrite( &entry, sizeof(entry), 1, fp);
		
		return entry.blk_no;
    }
}


//提供inode号和偏移量，找到inode对应的文件里偏移量为fd_offset所在的磁盘块号
int blk_map( FILE *fp, int ind_no, long fd_offset)
{
    struct fs_inode inode = find_inode( fp, ind_no);

    int i;
    if(fd_offset > inode.size){
	fprintf( stderr, "offset overflow!\n");
	return -1;
    }

    if(fd_offset <= DIRECT){	/* direct */

	i = fd_offset / BLOCK_SIZE;
	return inode.addr[i];//磁盘块i的地址
    }
    else if(fd_offset <= SINGLE){ //偏移量处在一次间接块中的情况
	struct blk_index index;

	fd_offset -= DIRECT;
	i = fd_offset / BLOCK_SIZE; /* get single indirect addr */

	fseek( fp, (SEEK_BLK(inode.addr[10]) + i*sizeof(index)), SEEK_SET);
	fread( &index, sizeof(index), 1, fp); /* get actual blk_no */
	return index.blk_no;
    }
    else if(fd_offset <= DOUBLE){ /* double indirect, addr[11] */
	struct blk_index index;
	
	fd_offset = fd_offset - DIRECT - SINGLE;
	i = fd_offset / (BCPB * BLOCK_SIZE); //一张二级表有BCPB个磁盘块号，一个磁盘块号对应一个磁盘块，一个磁盘块有BLOCK—SIZE的空间
											//BCPC*BLOCK—SIZE可以算出一张二级表分配到的对应的空间大小
											//这里得到的i是二级表在一级表中的索引，即这是第几个二级表
	fseek( fp, (SEEK_BLK(inode.addr[11]) + i*sizeof(index)), SEEK_SET);
	fread( &index, sizeof(index), 1, fp);

	fd_offset %= BCPB * BLOCK_SIZE;
	i = fd_offset / BLOCK_SIZE; //找到磁盘块号在二级表中的索引

	fseek( fp, (SEEK_BLK(index.blk_no) + i*sizeof(index)), SEEK_SET);
	fread( &index, sizeof(index), 1, fp); /* get actual addr */
	return index.blk_no;
    }
    else if(fd_offset <= TRIPLE){ /* triple indirect, addr[12] */
	struct blk_index index;

	fd_offset = fd_offset - DIRECT - SINGLE - DOUBLE;
	i = fd_offset / ((int)pow( BCPB, 2) * BLOCK_SIZE); /* get triple indirect addr */

	fseek( fp, (SEEK_BLK(inode.addr[12]) + i*sizeof(index)), SEEK_SET);
	fread( &index, sizeof(index), 1, fp);

	fd_offset %= ((int)pow( BCPB, 2) * BLOCK_SIZE);
	i = fd_offset / (BCPB * BLOCK_SIZE); /* get double indirect addr */

	fseek( fp, (SEEK_BLK(index.blk_no) + i*sizeof(index)), SEEK_SET);
	fread( &index, sizeof(index), 1, fp);

	fd_offset %= (BCPB * BLOCK_SIZE);
	i = fd_offset / (BCPB * BLOCK_SIZE); /* get single indirect addr */

	fseek( fp, (SEEK_BLK(index.blk_no) + i*sizeof(index)), SEEK_SET);
	fread( &index, sizeof(index), 1, fp); /* get actual addr */
	return index.blk_no;
    }

    return -2;			/* will never reach here */
}

//创建文件/目录
int create_fd( FILE *fp, int dir_ind_no, const char *file, const char given_type, const char *f_size)
{
    int file_size;
    if(file == NULL){
	fprintf( stderr, "invalid command, please see help in detail.\n");
	return -1;
    }
    else if(fd_exist( fp, dir_ind_no, file) != -1){ /* file have existed */
	fprintf( stderr, "file have existed!\n");
	return -1;
    }
    else if(strlen(file) > NAME_LEN){
	fprintf( stderr, "file name too long!\n");
	return -1;
    }
    else if(f_size == NULL)
	file_size = 0;
    else
	file_size = atoi(f_size);

    /* first to construct the file entry */
    struct fs_inode dir_inode = find_inode( fp, dir_ind_no);//找到目录结点
    struct fd_entry file_entry;//结点表项
    strcpy( file_entry.name, file);
    file_entry.inode_no = get_ind(fp);//分配inode号

    /* second to update the current dir */
	//当前目录的inode记录表加入该结点表项（目录文件的内容就是维护一张结点表项）
    fseek( fp, (SEEK_BLK(blk_map( fp, dir_ind_no, dir_inode.size))+dir_inode.size%BLOCK_SIZE), SEEK_SET);
    fwrite( &file_entry, sizeof(file_entry), 1, fp);
    
    dir_inode.size += sizeof(file_entry);
    update_ind( fp, dir_ind_no, dir_inode);

    /* third to update file inode's information */
    struct fs_inode file_inode = find_inode( fp, file_entry.inode_no);//找到新分配inode号对应的inode
    strcpy( file_inode.user, dir_inode.user);
    file_inode.type    = given_type;
    file_inode.links   = 1;
    file_inode.size    = 0;	//初始化大小为0
    int i;
    for( i=0; i<13; i++)	//初始化文件的所有磁盘块号
	file_inode.addr[i] = -1;
    update_ind( fp, file_entry.inode_no, file_inode);//到inodes表里更新第file_entry.inode_no个inode，即把新的inode写入覆盖原来的空白inode

    for( i=0; i<=file_size; i+=BLOCK_SIZE) //一次分配一个磁盘块
	alc_blk( fp, file_entry.inode_no);

    file_inode = find_inode( fp, file_entry.inode_no);
    file_inode.size = file_size;//更新目录/文件的大小
    update_ind( fp, file_entry.inode_no, file_inode);//替换掉刚才加入的inode

    //如果是创建目录
    if(given_type == 'd'){
	char *self=".", *parent="..";
	struct fd_entry dir_tmp_entry;

	file_inode.size += 2*sizeof(dir_tmp_entry); //新建的目录大小要加入两条inode表项即'.'和'..'
	update_ind( fp, file_entry.inode_no, file_inode);

	strcpy( dir_tmp_entry.name, self);
	dir_tmp_entry.inode_no = file_entry.inode_no;

	fseek( fp, SEEK_BLK(file_inode.addr[0]), SEEK_SET);
	fwrite( &dir_tmp_entry, sizeof(dir_tmp_entry), 1, fp);

	strcpy( dir_tmp_entry.name, parent);
	dir_tmp_entry.inode_no = dir_ind_no; /* parent inode number */
	fwrite( &dir_tmp_entry, sizeof(dir_tmp_entry), 1, fp);
    }

    return file_entry.inode_no;
}

//删除文件/目录
int remove_fd( FILE *fp, int dir_ind_no, const char *file)
{
    int rm_ind_no;
    if(file==NULL || !strcmp(file,".") || !strcmp(file,"..")){
		fprintf( stderr, "invalid command, please see help in detail.\n");
		return -1;
    }
    else if((rm_ind_no=fd_exist( fp, dir_ind_no, file)) == -1){ /* file doesn't exist */
		fprintf( stderr, "file %s doesn't exist!\n", file);
		return -1;
    }
	
    struct fd_entry last_file_entry;
    struct fs_inode dir_inode = find_inode( fp, dir_ind_no);
	
    /* get the last entry */
    fseek( fp, ((SEEK_BLK(blk_map( fp, dir_ind_no, dir_inode.size)))
		+ dir_inode.size%BLOCK_SIZE - sizeof(last_file_entry)),
		SEEK_SET);
    fread( &last_file_entry, sizeof(last_file_entry), 1, fp);
	
    /* locate the rm file */
    int blk_no;
    long offset;
    struct fd_entry rm_file_entry;
    for( offset=0; offset<dir_inode.size; offset+=sizeof(rm_file_entry)){
		
		blk_no = blk_map( fp, dir_ind_no, offset);
		fseek( fp, (SEEK_BLK(blk_map( fp, dir_ind_no, offset%BLOCK_SIZE)) + offset%BLOCK_SIZE), SEEK_SET);
		fread( &rm_file_entry, sizeof(rm_file_entry), 1, fp);
		
		/* if locate the rm one, then overwrite it */	
		if(!strcmp( file, rm_file_entry.name)){
			fseek( fp, (SEEK_BLK(blk_map( fp, dir_ind_no, offset%BLOCK_SIZE)) + offset%BLOCK_SIZE), SEEK_SET);
			fwrite( &last_file_entry, sizeof(last_file_entry), 1, fp);
			break;
		}
    }
	
    dir_inode.size -= sizeof(rm_file_entry); /* update dir's inode */
    update_ind( fp, dir_ind_no, dir_inode);
	
    /* if the rm file's links was 0, free the rm file's blocks and inode */
    struct fs_inode rm_file_inode = find_inode( fp, rm_file_entry.inode_no);
    rm_file_inode.links--;
    if(rm_file_inode.links > 0){
		update_ind( fp, rm_file_entry.inode_no, rm_file_inode);
		return 0;
    }
    
    for( ; rm_file_inode.size>=0; rm_file_inode.size-=BLOCK_SIZE){
		
		blk_no = blk_map( fp, rm_file_entry.inode_no, rm_file_inode.size); /* locate the block */
		free_blk( fp, blk_no);
    }
	
    if(rm_file_inode.addr[12] != -1)
		free_blk( fp, rm_file_inode.addr[12]);
    if(rm_file_inode.addr[11] != -1)
		free_blk( fp, rm_file_inode.addr[11]);
    if(rm_file_inode.addr[10] != -1)
		free_blk( fp, rm_file_inode.addr[10]);
	
    free_ind( fp, rm_file_entry.inode_no);
	
    return 0;
}