fd.c

一个用C++写的模拟LINUX文件系统的程序

/* 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)

/* convert inode number to actually 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;
}

/* return the file entry in the dir_ind_no, function do not check whether the file 
   exist, you can use fd_exist() to check it, and also can use fd_exist() to convert 
   the file name to its file_inode_no. */
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);

    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;
}

/* match dir's entry, check whether the given file name exist, if YES
   return the matching entry's inode number, else return -1. */
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;		/* record the reading 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); /* map blk_no */
	fseek( fp, (SEEK_BLK(blk_no) + (fd_offset%BLOCK_SIZE)), SEEK_SET);
	fread( &entry, sizeof(entry), 1, fp);

	if(!strcmp( file, entry.name)) /* if find one */
	    return entry.inode_no;
    }
    
    return -1;			/* file doesn't exist */
}


/* base on the given file's file size, check whether to allocate more
   block to file's proper addr entry, if file size too large, print
   error and return -1, else check whether to add block to the inode
   addr entry, and return the block number. the alc_blk() allocate 
   one block every time. */
int alc_blk( FILE *fp, int ind_no)
{
    struct fs_inode inode = find_inode( fp, ind_no);
    if(inode.size + BLOCK_SIZE > TRIPLE) /* file size too large */
	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;

	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); /* get double indirect block index */
	
	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);	    /* allocate block */
	i = (tmp_size / BLOCK_SIZE) % BCPB; /* get the double indirect index */
	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;
    }
}

/* locate the given fd_offset in block's number, if fd_offset too
   large, print errors and return -1, else calculate it and return
   its block number and return another value but -1.
   (PASS: offset of block can be calculate from offset/BLOCK_SIZE) */
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];
    }
    else if(fd_offset <= SINGLE){ /* single indirect, addr[10] */
	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); /* get double indirect addr */

	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; /* 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;
    }
    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 */
}

/* check the file to be created whether EXISTS or the file name was too long, if 
   YES print error and return -1, else construct file entry, get file name and assign
   inode number to entry, then write the entry to the dir. if the creating one was a 
   dir, also need to insert '.' and '..' entry to its contents. after this, update the
   current dir's information. then return the created file's inode number. */
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);

    /* second to update the current dir */
    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);
    strcpy( file_inode.user, dir_inode.user);
    file_inode.type    = given_type;
    file_inode.links   = 1;
    file_inode.size    = 0;	/* for allocate blocks */
    int i;
    for( i=0; i<13; i++)	/* init the addr */
	file_inode.addr[i] = -1;
    update_ind( fp, file_entry.inode_no, file_inode);

    for( i=0; i<=file_size; i+=BLOCK_SIZE) /* allocate blocks */
	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);

    /* if creating file was a dir, insert more information */
    if(given_type == 'd'){
	char *self=".", *parent="..";
	struct fd_entry dir_tmp_entry;

	file_inode.size += 2*sizeof(dir_tmp_entry); /* enlarge the size */
	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;
}

/* BETA: DO NOT consider the recursive dir and file structure. check the
   file to be rm whether EXIST, if NOT print error and return -1, else get
   the dir's last entry, then locate the rm file, use the last entry to
   overwrite the rm one, if the rm file's links was 0, then free the rm
   file's blocks and inode, finally return another value but -1. */
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;
}