1.1 --- a/src/fs.c	Sun Dec 11 21:15:35 2011 +0200
     1.2 +++ b/src/fs.c	Thu Dec 15 04:39:00 2011 +0200
     1.3 @@ -1,7 +1,4 @@
     1.4 -/* This code is used by the kernel AND by userspace filesystem-related tools.
     1.5 - * The kernel-specific parts are conditionally compiled in #ifdef KERNEL blocks
     1.6 - * the rest of the code should be independent.
     1.7 - */
     1.8 +/* This code is used by the kernel AND by userspace filesystem-related tools. */
     1.9  #include <stdio.h>
    1.10  #include <stdlib.h>
    1.11  #include <string.h>
    1.12 @@ -9,6 +6,14 @@
    1.13  #include <assert.h>
    1.14  #include "fs.h"
    1.15  #include "bdev.h"
    1.16 +#include "kdef.h"
    1.17 +
    1.18 +/* number of inodes in a block */
    1.19 +#define BLK_INODES		(BLKSZ / sizeof(struct inode))
    1.20 +/* number of directory entries in a block */
    1.21 +#define BLK_DIRENT		(BLKSZ / sizeof(struct dir_entry))
    1.22 +
    1.23 +#define BLKBITS				(BLKSZ * 8)
    1.24  
    1.25  #define BM_IDX(x)			((x) / 32)
    1.26  #define BM_BIT(x)			((x) & 0x1f)
    1.27 @@ -18,11 +23,18 @@
    1.28  #define BM_CLR(bm, x)		((bm)[BM_IDX(x)] &= ~(1 << BM_BIT(x)))
    1.29  
    1.30  
    1.31 -int openfs(struct filesys *fs, dev_t dev);
    1.32 +static struct inode *newdir(struct filesys *fs, struct inode *parent);
    1.33 +static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name);
    1.34  static int read_superblock(struct filesys *fs);
    1.35  static int write_superblock(struct filesys *fs);
    1.36  static int get_inode(struct filesys *fs, int ino, struct inode *inode);
    1.37  static int put_inode(struct filesys *fs, struct inode *inode);
    1.38 +static int find_free(uint32_t *bm, int sz);
    1.39 +static int alloc_inode(struct filesys *fs);
    1.40 +static void free_inode(struct filesys *fs, int ino);
    1.41 +static int alloc_block(struct filesys *fs);
    1.42 +static void free_block(struct filesys *fs, int ino);
    1.43 +static int file_block(struct filesys *fs, struct inode *node, int boffs);
    1.44  
    1.45  int openfs(struct filesys *fs, dev_t dev)
    1.46  {
    1.47 @@ -38,19 +50,164 @@
    1.48  
    1.49  	/* read the superblock */
    1.50  	if(!(fs->sb = malloc(BLKSZ))) {
    1.51 -		res = -ENOMEM;
    1.52 -		goto done;
    1.53 +		blk_close(bdev);
    1.54 +		return -ENOMEM;
    1.55  	}
    1.56  	if((res = read_superblock(fs)) != 0) {
    1.57 -		goto done;
    1.58 +		blk_close(bdev);
    1.59 +		return res;
    1.60  	}
    1.61  
    1.62 +	return 0;
    1.63 +}
    1.64  
    1.65 -done:
    1.66 -	blk_close(bdev);
    1.67 -	return res;
    1.68 +int mkfs(struct filesys *fs, dev_t dev)
    1.69 +{
    1.70 +	struct filesys *fs;
    1.71 +	struct superblock *sb;
    1.72 +	struct block_device *bdev;
    1.73 +	int i, bcount;
    1.74 +
    1.75 +	if(!(bdev = blk_open(dev))) {
    1.76 +		return -1;
    1.77 +	}
    1.78 +	fs->bdev = bdev;
    1.79 +
    1.80 +	if(!(sb = malloc(BLKSZ))) {
    1.81 +		blk_close(bdev);
    1.82 +		return -1;
    1.83 +	}
    1.84 +	fs->sb = sb;
    1.85 +
    1.86 +	/* populate the superblock */
    1.87 +	sb->magic = MAGIC;
    1.88 +	sb->ver = FS_VER;
    1.89 +	sb->blksize = BLKSZ;
    1.90 +
    1.91 +	sb->num_blocks = bdev->size;
    1.92 +	sb->num_inodes = sb->num_blocks / 4;
    1.93 +
    1.94 +	/* inode bitmap just after the superblock */
    1.95 +	sb->ibm_start = 2;
    1.96 +	sb->ibm_count = (sb->num_inodes + BLKBITS - 1) / BLKBITS;
    1.97 +	/* also allocate and initialize in-memory inode bitmap */
    1.98 +	sb->ibm = malloc(sb->ibm_count * BLKSZ);
    1.99 +	assert(sb->ibm);
   1.100 +	memset(sb->ibm, 0, sb->ibm_count * BLKSZ);
   1.101 +
   1.102 +	/* XXX mark inode 0 as used always */
   1.103 +	BM_SET(sb->ibm, 0);
   1.104 +
   1.105 +	/* block bitmap just after the inode bitmap */
   1.106 +	sb->bm_start = sb->ibm_start + sb->ibm_count;
   1.107 +	sb->bm_count = (sb->num_blocks + BLKBITS - 1) / BLKBITS;
   1.108 +	/* also allocate and initialize in-memory block bitmap */
   1.109 +	sb->bm = malloc(sb->bm_count * BLKSZ);
   1.110 +	assert(sb->bm);
   1.111 +	memset(sb->bm, 0, sb->bm_count * BLKSZ);
   1.112 +
   1.113 +	/* inode table, just after the block bitmap */
   1.114 +	sb->itbl_start = sb->bm_start + sb->bm_count;
   1.115 +	sb->itbl_count = (sb->num_inodes * sizeof(struct inode) + BLKSZ - 1) / BLKSZ;
   1.116 +
   1.117 +	/* mark all used blocks as used */
   1.118 +	bcount = sb->itbl_start + sb->itbl_count;
   1.119 +	memset(sb->bm, 0xff, bcount / 8);
   1.120 +	for(i=0; i<bcount % 8; i++) {
   1.121 +		int bit = bcount / 8 + i;
   1.122 +		BM_SET(sb->bm, bit);
   1.123 +	}
   1.124 +
   1.125 +	/* create the root directory */
   1.126 +	sb->root = newdir(fs, 0);
   1.127 +	sb->root_ino = sb->root->ino;
   1.128  }
   1.129  
   1.130 +static struct inode *newdir(struct filesys *fs, struct inode *parent)
   1.131 +{
   1.132 +	struct inode *dirnode;
   1.133 +
   1.134 +	/* allocate and initialize inode */
   1.135 +	if(!(dirnode = malloc(sizeof *dirnode))) {
   1.136 +		return 0;
   1.137 +	}
   1.138 +	memset(dirnode, 0, sizeof *dirnode);
   1.139 +
   1.140 +	if((dirnode->ino = alloc_inode(fs)) == -1) {
   1.141 +		printf("failed to allocate inode for a new directory\n");
   1.142 +		free(dirnode);
   1.143 +		return 0;
   1.144 +	}
   1.145 +	dirnode->mode = S_IFDIR;
   1.146 +
   1.147 +	/* add . and .. links */
   1.148 +	addlink(fs, dirnode, dirnode, ".");
   1.149 +	addlink(fs, dirnode, parent ? parent : dirnode, "..");
   1.150 +
   1.151 +	/* and write the inode to disk */
   1.152 +	put_inode(fs, dirnode);
   1.153 +	return dirnode;
   1.154 +}
   1.155 +
   1.156 +static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name)
   1.157 +{
   1.158 +	struct dir_entry ent, *data;
   1.159 +	int boffs, bidx, len;
   1.160 +
   1.161 +	if(!(target->mode & S_IFDIR)) {
   1.162 +		return -ENOTDIR;
   1.163 +	}
   1.164 +	if(node->mode & S_IFDIR) {
   1.165 +		return -EPERM;
   1.166 +	}
   1.167 +	/* TODO check that the link does not already exist (EEXIST) */
   1.168 +
   1.169 +	if((len = strlen(name)) > MAX_FNAME) {
   1.170 +		return -ENAMETOOLONG;
   1.171 +	}
   1.172 +	ent->ino = node->ino;
   1.173 +	memcpy(newent->name, name, len + 1);
   1.174 +
   1.175 +	/* find a place to put it */
   1.176 +	if(!(data = malloc(BLKSZ))) {
   1.177 +		return -ENOMEM;
   1.178 +	}
   1.179 +
   1.180 +	boffs = 0;
   1.181 +	while((bidx = file_block(fs, target, boffs)) > 0) {
   1.182 +		/* read the block, and search for an empty entry */
   1.183 +		blk_read(fs->bdev, bidx, 1, data);
   1.184 +
   1.185 +		/* for all directory entries in this block... */
   1.186 +		for(i=0; i<BLK_DIRENT; i++) {
   1.187 +			if(data[i].ino == 0) {
   1.188 +				/* found empty */
   1.189 +				memcpy(data + i, &ent, sizeof ent);
   1.190 +				goto success;
   1.191 +			}
   1.192 +		}
   1.193 +		boffs++;
   1.194 +	}
   1.195 +
   1.196 +	/* didn't find any free entries amongst our blocks, allocate a new one */
   1.197 +	if(!(bidx = alloc_file_block(fs, target, boffs))) {
   1.198 +		free(data);
   1.199 +		return -ENOSPC;
   1.200 +	}
   1.201 +	/* zero-fill the new block and add the first entry */
   1.202 +	memset(data, 0, BLKSZ);
   1.203 +	*data = ent;
   1.204 +
   1.205 +success:
   1.206 +	/* write to disk */
   1.207 +	blk_write(fs->bdev, bidx, 1, data);
   1.208 +	node->nlink++;	/* increase reference count */
   1.209 +
   1.210 +	free(data);
   1.211 +	return 0;
   1.212 +}
   1.213 +
   1.214 +
   1.215  static int read_superblock(struct filesys *fs)
   1.216  {
   1.217  	struct superblock *sb = fs->sb;
   1.218 @@ -123,12 +280,13 @@
   1.219  	if(blk_write(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {
   1.220  		return -1;
   1.221  	}
   1.222 +	/* write the superblock itself */
   1.223 +	if(blk_write(fs->bdev, 1, 1, sb) == -1) {
   1.224 +		return -1;
   1.225 +	}
   1.226  	return 0;
   1.227  }
   1.228  
   1.229 -/* number of inodes in a block */
   1.230 -#define BLK_INODES		(BLKSZ / sizeof(struct inode))
   1.231 -
   1.232  /* copy the requested inode from the disk, into the buffer passed in the last arg */
   1.233  static int get_inode(struct filesys *fs, int ino, struct inode *inode)
   1.234  {
   1.235 @@ -164,21 +322,24 @@
   1.236  	return 0;
   1.237  }
   1.238  
   1.239 -static int find_free(uint32_t *bm, int sz)
   1.240 +/* find a free element in the bitmap and return its number */
   1.241 +static int find_free(uint32_t *bm, int nbits)
   1.242  {
   1.243 -	int i;
   1.244 -	uint32_t ent;
   1.245 +	int i, j, nwords = nbits / 32;
   1.246 +	uint32_t ent = 0;
   1.247  
   1.248 -	for(i=0; i<=sz/32; i++) {
   1.249 +	for(i=0; i<=nwords; i++) {
   1.250  		if(bm[i] != 0xffffffff) {
   1.251 -			ent = i * 32;
   1.252  			for(j=0; j<32; j++) {
   1.253  				if(BM_ISFREE(bm, ent)) {
   1.254  					return ent;
   1.255  				}
   1.256 +				ent++;
   1.257  			}
   1.258  
   1.259  			panic("shouldn't happen (in find_free:fs.c)");
   1.260 +		} else {
   1.261 +			ent += 32;
   1.262  		}
   1.263  	}
   1.264  
   1.265 @@ -189,9 +350,82 @@
   1.266  {
   1.267  	int ino;
   1.268  
   1.269 -	if((ino = find_free(fs->ibm, fs->ibm_count)) == -1) {
   1.270 +	if((ino = find_free(fs->sb->ibm, fs->sb->num_inodes)) == -1) {
   1.271  		return -1;
   1.272  	}
   1.273 -	BM_SET(fs->ibm, ino);
   1.274 +	BM_SET(fs->sb->ibm, ino);
   1.275  	return 0;
   1.276  }
   1.277 +
   1.278 +static void free_inode(struct filesys *fs, int ino)
   1.279 +{
   1.280 +	BM_CLR(fs->sb->ibm, ino);
   1.281 +}
   1.282 +
   1.283 +static int alloc_block(struct filesys *fs)
   1.284 +{
   1.285 +	int ino;
   1.286 +
   1.287 +	if((ino = find_free(fs->sb->bm, fs->sb->num_blocks)) == -1) {
   1.288 +		return -1;
   1.289 +	}
   1.290 +	BM_SET(fs->sb->bm, ino);
   1.291 +	return 0;
   1.292 +}
   1.293 +
   1.294 +static void free_block(struct filesys *fs, int ino)
   1.295 +{
   1.296 +	BM_CLR(fs->sb->bm, ino);
   1.297 +}
   1.298 +
   1.299 +#define BLK_BLKID	(BLKSZ / sizeof(blkid))
   1.300 +#define MAX_IND		(NDIRBLK + BLK_BLKID)
   1.301 +#define MAX_DIND	(MAX_IND + BLK_BLKID * BLK_BLKID)
   1.302 +
   1.303 +static int file_block(struct filesys *fs, struct inode *node, int boffs)
   1.304 +{
   1.305 +	int res, idx;
   1.306 +	blkid *barr;
   1.307 +
   1.308 +	/* is it a direct block ? */
   1.309 +	if(boffs < NDIRBLK) {
   1.310 +		return node->blk[boffs];
   1.311 +	}
   1.312 +
   1.313 +	barr = malloc(BLKSZ);
   1.314 +	assert(barr);
   1.315 +
   1.316 +	/* is it an indirect block ? */
   1.317 +	if(boffs < MAX_IND) {
   1.318 +		if(!node->ind) {
   1.319 +			res = 0;
   1.320 +			goto end;
   1.321 +		}
   1.322 +		blk_read(fs->bdev, node->ind, 1, barr);
   1.323 +		res = barr[boffs - NDIRBLK];
   1.324 +		goto end;
   1.325 +	}
   1.326 +
   1.327 +	/* is it a double-indirect block ? */
   1.328 +	if(boffs < MAX_DIND) {
   1.329 +		/* first read the dind block and find the index of the ind block */
   1.330 +		if(!node->dind) {
   1.331 +			res = 0;
   1.332 +			goto end;
   1.333 +		}
   1.334 +		blk_read(fd->bdev, node->dind, 1, barr);
   1.335 +		idx = (boffs - MAX_IND) / BLK_BLKID;
   1.336 +
   1.337 +		/* then read the ind block and find the index of the block */
   1.338 +		if(!barr[idx]) {
   1.339 +			res = 0;
   1.340 +			goto end;
   1.341 +		}
   1.342 +		blk_read(fd->bdev, barr[idx], 1, barr);
   1.343 +		res = barr[(boffs - MAX_IND) % BLK_BLKID];
   1.344 +	}
   1.345 +
   1.346 +end:
   1.347 +	free(barr);
   1.348 +	return res;
   1.349 +}