nuclear@96: /* This code is used by the kernel AND by userspace filesystem-related tools. */
nuclear@97: 
nuclear@97: /* XXX convention:
nuclear@97:  * - functions that accept or return a struct inode, do not read/write it to disk
nuclear@97:  * - functions that accept or return an int ino, do read/write it to disk
nuclear@97:  * other kinds of blocks (data, indirect, etc) always hit the disk directly.
nuclear@97:  */
nuclear@97: 
nuclear@88: #include <stdio.h>
nuclear@89: #include <stdlib.h>
nuclear@94: #include <string.h>
nuclear@90: #include <errno.h>
nuclear@94: #include <assert.h>
nuclear@88: #include "fs.h"
nuclear@93: #include "bdev.h"
nuclear@96: #include "kdef.h"
nuclear@96: 
nuclear@96: /* number of inodes in a block */
nuclear@96: #define BLK_INODES		(BLKSZ / sizeof(struct inode))
nuclear@96: /* number of directory entries in a block */
nuclear@96: #define BLK_DIRENT		(BLKSZ / sizeof(struct dir_entry))
nuclear@96: 
nuclear@96: #define BLKBITS				(BLKSZ * 8)
nuclear@90: 
nuclear@95: #define BM_IDX(x)			((x) / 32)
nuclear@95: #define BM_BIT(x)			((x) & 0x1f)
nuclear@95: 
nuclear@95: #define BM_ISFREE(bm, x)	(((bm)[BM_IDX(x)] & (1 << BM_BIT(x))) == 0)
nuclear@95: #define BM_SET(bm, x)		((bm)[BM_IDX(x)] |= (1 << BM_BIT(x)))
nuclear@95: #define BM_CLR(bm, x)		((bm)[BM_IDX(x)] &= ~(1 << BM_BIT(x)))
nuclear@95: 
nuclear@89: 
nuclear@96: static struct inode *newdir(struct filesys *fs, struct inode *parent);
nuclear@96: static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name);
nuclear@94: static int read_superblock(struct filesys *fs);
nuclear@94: static int write_superblock(struct filesys *fs);
nuclear@94: static int get_inode(struct filesys *fs, int ino, struct inode *inode);
nuclear@94: static int put_inode(struct filesys *fs, struct inode *inode);
nuclear@96: static int find_free(uint32_t *bm, int sz);
nuclear@96: static int alloc_inode(struct filesys *fs);
nuclear@97: #define free_inode(fs, ino)		BM_CLR((fs)->sb->ibm, (ino))
nuclear@96: static int alloc_block(struct filesys *fs);
nuclear@97: #define free_block(fs, bno)		BM_CLR((fs)->sb->bm, (bno))
nuclear@97: #define zero_block(fs, bno) \
nuclear@97: 	do { \
nuclear@97: 		assert(bno > 0); \
nuclear@97: 		blk_write((fs)->bdev, (bno), 1, (fs)->zeroblock); \
nuclear@97: 	} while(0)
nuclear@97: 
nuclear@97: static int file_block(struct filesys *fs, struct inode *node, int boffs, int allocate);
nuclear@97: #define get_file_block(fs, node, boffs)		file_block(fs, node, boffs, 0)
nuclear@97: #define alloc_file_block(fs, node, boffs)	file_block(fs, node, boffs, 1)
nuclear@97: 
nuclear@90: 
nuclear@93: int openfs(struct filesys *fs, dev_t dev)
nuclear@93: {
nuclear@93: 	int res;
nuclear@93: 	struct block_device *bdev;
nuclear@94: 
nuclear@94: 	assert(BLKSZ % sizeof(struct inode) == 0);
nuclear@89: 
nuclear@93: 	if(!(bdev = blk_open(dev))) {
nuclear@93: 		return -ENOENT;
nuclear@90: 	}
nuclear@94: 	fs->bdev = bdev;
nuclear@90: 
nuclear@93: 	/* read the superblock */
nuclear@94: 	if(!(fs->sb = malloc(BLKSZ))) {
nuclear@96: 		blk_close(bdev);
nuclear@96: 		return -ENOMEM;
nuclear@93: 	}
nuclear@94: 	if((res = read_superblock(fs)) != 0) {
nuclear@96: 		blk_close(bdev);
nuclear@96: 		return res;
nuclear@93: 	}
nuclear@90: 
nuclear@97: 	/* allocate the zero-block buffer written to zero-out blocks */
nuclear@97: 	if(!(fs->zeroblock = malloc(fs->sb->blksize))) {
nuclear@97: 		blk_close(bdev);
nuclear@97: 		free(fs->sb->ibm);
nuclear@97: 		free(fs->sb->bm);
nuclear@97: 		free(fs->sb->root);
nuclear@97: 		return -ENOMEM;
nuclear@97: 	}
nuclear@97: 	memset(fs->zeroblock, 0xff, fs->sb->blksize);
nuclear@97: 
nuclear@96: 	return 0;
nuclear@96: }
nuclear@93: 
nuclear@96: int mkfs(struct filesys *fs, dev_t dev)
nuclear@96: {
nuclear@96: 	struct superblock *sb;
nuclear@96: 	struct block_device *bdev;
nuclear@96: 	int i, bcount;
nuclear@96: 
nuclear@96: 	if(!(bdev = blk_open(dev))) {
nuclear@96: 		return -1;
nuclear@96: 	}
nuclear@96: 	fs->bdev = bdev;
nuclear@96: 
nuclear@96: 	if(!(sb = malloc(BLKSZ))) {
nuclear@96: 		blk_close(bdev);
nuclear@96: 		return -1;
nuclear@96: 	}
nuclear@96: 	fs->sb = sb;
nuclear@96: 
nuclear@96: 	/* populate the superblock */
nuclear@96: 	sb->magic = MAGIC;
nuclear@96: 	sb->ver = FS_VER;
nuclear@96: 	sb->blksize = BLKSZ;
nuclear@96: 
nuclear@96: 	sb->num_blocks = bdev->size;
nuclear@96: 	sb->num_inodes = sb->num_blocks / 4;
nuclear@96: 
nuclear@96: 	/* inode bitmap just after the superblock */
nuclear@96: 	sb->ibm_start = 2;
nuclear@96: 	sb->ibm_count = (sb->num_inodes + BLKBITS - 1) / BLKBITS;
nuclear@96: 	/* also allocate and initialize in-memory inode bitmap */
nuclear@96: 	sb->ibm = malloc(sb->ibm_count * BLKSZ);
nuclear@96: 	assert(sb->ibm);
nuclear@96: 	memset(sb->ibm, 0, sb->ibm_count * BLKSZ);
nuclear@96: 
nuclear@96: 	/* XXX mark inode 0 as used always */
nuclear@96: 	BM_SET(sb->ibm, 0);
nuclear@96: 
nuclear@96: 	/* block bitmap just after the inode bitmap */
nuclear@96: 	sb->bm_start = sb->ibm_start + sb->ibm_count;
nuclear@96: 	sb->bm_count = (sb->num_blocks + BLKBITS - 1) / BLKBITS;
nuclear@96: 	/* also allocate and initialize in-memory block bitmap */
nuclear@96: 	sb->bm = malloc(sb->bm_count * BLKSZ);
nuclear@96: 	assert(sb->bm);
nuclear@96: 	memset(sb->bm, 0, sb->bm_count * BLKSZ);
nuclear@96: 
nuclear@96: 	/* inode table, just after the block bitmap */
nuclear@96: 	sb->itbl_start = sb->bm_start + sb->bm_count;
nuclear@96: 	sb->itbl_count = (sb->num_inodes * sizeof(struct inode) + BLKSZ - 1) / BLKSZ;
nuclear@96: 
nuclear@96: 	/* mark all used blocks as used */
nuclear@96: 	bcount = sb->itbl_start + sb->itbl_count;
nuclear@96: 	memset(sb->bm, 0xff, bcount / 8);
nuclear@96: 	for(i=0; i<bcount % 8; i++) {
nuclear@96: 		int bit = bcount / 8 + i;
nuclear@96: 		BM_SET(sb->bm, bit);
nuclear@96: 	}
nuclear@96: 
nuclear@96: 	/* create the root directory */
nuclear@96: 	sb->root = newdir(fs, 0);
nuclear@96: 	sb->root_ino = sb->root->ino;
nuclear@97: 	/* and write the inode to disk */
nuclear@97: 	put_inode(fs, sb->root);
nuclear@97: 
nuclear@97: 	return 0;
nuclear@90: }
nuclear@88: 
nuclear@96: static struct inode *newdir(struct filesys *fs, struct inode *parent)
nuclear@96: {
nuclear@96: 	struct inode *dirnode;
nuclear@96: 
nuclear@96: 	/* allocate and initialize inode */
nuclear@96: 	if(!(dirnode = malloc(sizeof *dirnode))) {
nuclear@96: 		return 0;
nuclear@96: 	}
nuclear@96: 	memset(dirnode, 0, sizeof *dirnode);
nuclear@96: 
nuclear@96: 	if((dirnode->ino = alloc_inode(fs)) == -1) {
nuclear@96: 		printf("failed to allocate inode for a new directory\n");
nuclear@96: 		free(dirnode);
nuclear@96: 		return 0;
nuclear@96: 	}
nuclear@96: 	dirnode->mode = S_IFDIR;
nuclear@96: 
nuclear@96: 	/* add . and .. links */
nuclear@96: 	addlink(fs, dirnode, dirnode, ".");
nuclear@96: 	addlink(fs, dirnode, parent ? parent : dirnode, "..");
nuclear@96: 
nuclear@96: 	return dirnode;
nuclear@96: }
nuclear@96: 
nuclear@96: static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name)
nuclear@96: {
nuclear@96: 	struct dir_entry ent, *data;
nuclear@97: 	int i, boffs, bidx, len;
nuclear@96: 
nuclear@96: 	if(!(target->mode & S_IFDIR)) {
nuclear@96: 		return -ENOTDIR;
nuclear@96: 	}
nuclear@96: 	if(node->mode & S_IFDIR) {
nuclear@96: 		return -EPERM;
nuclear@96: 	}
nuclear@96: 	/* TODO check that the link does not already exist (EEXIST) */
nuclear@96: 
nuclear@97: 	if((len = strlen(name)) > NAME_MAX) {
nuclear@96: 		return -ENAMETOOLONG;
nuclear@96: 	}
nuclear@97: 	ent.ino = node->ino;
nuclear@97: 	memcpy(ent.name, name, len + 1);
nuclear@96: 
nuclear@96: 	/* find a place to put it */
nuclear@96: 	if(!(data = malloc(BLKSZ))) {
nuclear@96: 		return -ENOMEM;
nuclear@96: 	}
nuclear@96: 
nuclear@96: 	boffs = 0;
nuclear@97: 	while((bidx = get_file_block(fs, target, boffs)) > 0) {
nuclear@96: 		/* read the block, and search for an empty entry */
nuclear@96: 		blk_read(fs->bdev, bidx, 1, data);
nuclear@96: 
nuclear@96: 		/* for all directory entries in this block... */
nuclear@96: 		for(i=0; i<BLK_DIRENT; i++) {
nuclear@96: 			if(data[i].ino == 0) {
nuclear@96: 				/* found empty */
nuclear@96: 				memcpy(data + i, &ent, sizeof ent);
nuclear@96: 				goto success;
nuclear@96: 			}
nuclear@96: 		}
nuclear@96: 		boffs++;
nuclear@96: 	}
nuclear@96: 
nuclear@96: 	/* didn't find any free entries amongst our blocks, allocate a new one */
nuclear@96: 	if(!(bidx = alloc_file_block(fs, target, boffs))) {
nuclear@96: 		free(data);
nuclear@96: 		return -ENOSPC;
nuclear@96: 	}
nuclear@96: 	/* zero-fill the new block and add the first entry */
nuclear@96: 	memset(data, 0, BLKSZ);
nuclear@96: 	*data = ent;
nuclear@96: 
nuclear@96: success:
nuclear@96: 	/* write to disk */
nuclear@96: 	blk_write(fs->bdev, bidx, 1, data);
nuclear@96: 	node->nlink++;	/* increase reference count */
nuclear@96: 
nuclear@96: 	free(data);
nuclear@96: 	return 0;
nuclear@96: }
nuclear@96: 
nuclear@96: 
nuclear@94: static int read_superblock(struct filesys *fs)
nuclear@88: {
nuclear@94: 	struct superblock *sb = fs->sb;
nuclear@94: 
nuclear@93: 	/* read superblock and verify */
nuclear@94: 	if(blk_read(fs->bdev, 1, 1, sb) == -1) {
nuclear@93: 		printf("failed to read superblock\n");
nuclear@93: 		return -EIO;
nuclear@93: 	}
nuclear@93: 	if(sb->magic != MAGIC) {
nuclear@93: 		printf("invalid magic\n");
nuclear@93: 		return -EINVAL;
nuclear@93: 	}
nuclear@93: 	if(sb->ver > FS_VER) {
nuclear@93: 		printf("invalid version: %d\n", sb->ver);
nuclear@93: 		return -EINVAL;
nuclear@93: 	}
nuclear@93: 	if(sb->blksize != BLKSZ) {
nuclear@93: 		printf("invalid block size: %d\n", sb->blksize);
nuclear@93: 		return -EINVAL;
nuclear@93: 	}
nuclear@89: 
nuclear@93: 	/* allocate and populate in-memory bitmaps */
nuclear@93: 	if(!(sb->ibm = malloc(sb->ibm_count * sb->blksize))) {
nuclear@93: 		return -ENOMEM;
nuclear@88: 	}
nuclear@94: 	if(blk_read(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {
nuclear@93: 		printf("failed to read inode bitmap\n");
nuclear@93: 		free(sb->ibm);
nuclear@93: 		return -EIO;
nuclear@93: 	}
nuclear@93: 	if(!(sb->bm = malloc(sb->bm_count * sb->blksize))) {
nuclear@93: 		free(sb->ibm);
nuclear@93: 		return -ENOMEM;
nuclear@93: 	}
nuclear@94: 	if(blk_read(fs->bdev, sb->bm_start, sb->bm_count, sb->bm) == -1) {
nuclear@93: 		printf("failed to read block bitmap\n");
nuclear@93: 		free(sb->ibm);
nuclear@93: 		free(sb->bm);
nuclear@93: 		return -EIO;
nuclear@93: 	}
nuclear@93: 
nuclear@94: 	/* read the root inode */
nuclear@94: 	if(!(sb->root = malloc(sizeof *sb->root))) {
nuclear@94: 		free(sb->ibm);
nuclear@94: 		free(sb->bm);
nuclear@94: 		return -ENOMEM;
nuclear@94: 	}
nuclear@94: 	if(get_inode(fs, sb->root_ino, sb->root) == -1) {
nuclear@94: 		printf("failed to read root inode\n");
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@94: 
nuclear@93: 	return 0;
nuclear@88: }
nuclear@94: 
nuclear@94: static int write_superblock(struct filesys *fs)
nuclear@94: {
nuclear@94: 	struct superblock *sb = fs->sb;
nuclear@94: 
nuclear@94: 	/* write back any changes in the root inode */
nuclear@94: 	if(put_inode(fs, sb->root) == -1) {
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@94: 	/* write back the block bitmap */
nuclear@94: 	if(blk_write(fs->bdev, sb->bm_start, sb->bm_count, sb->bm) == -1) {
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@94: 	/* write back the inode bitmap */
nuclear@94: 	if(blk_write(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@96: 	/* write the superblock itself */
nuclear@96: 	if(blk_write(fs->bdev, 1, 1, sb) == -1) {
nuclear@96: 		return -1;
nuclear@96: 	}
nuclear@94: 	return 0;
nuclear@94: }
nuclear@94: 
nuclear@94: /* copy the requested inode from the disk, into the buffer passed in the last arg */
nuclear@94: static int get_inode(struct filesys *fs, int ino, struct inode *inode)
nuclear@94: {
nuclear@94: 	struct inode *buf = malloc(BLKSZ);
nuclear@94: 	assert(buf);
nuclear@94: 
nuclear@94: 	if(blk_read(fs->bdev, fs->sb->itbl_start + ino / BLK_INODES, 1, buf) == -1) {
nuclear@94: 		free(buf);
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@94: 	memcpy(inode, buf + ino % BLK_INODES, sizeof *inode);
nuclear@94: 	free(buf);
nuclear@94: 	return 0;
nuclear@94: }
nuclear@94: 
nuclear@94: /* write the inode to the disk */
nuclear@94: static int put_inode(struct filesys *fs, struct inode *inode)
nuclear@94: {
nuclear@94: 	struct inode *buf = malloc(BLKSZ);
nuclear@94: 	assert(buf);
nuclear@94: 
nuclear@94: 	if(blk_read(fs->bdev, fs->sb->itbl_start + inode->ino / BLK_INODES, 1, buf) == -1) {
nuclear@94: 		free(buf);
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@94: 	memcpy(buf + inode->ino % BLK_INODES, inode, sizeof *inode);
nuclear@94: 
nuclear@94: 	if(blk_write(fs->bdev, fs->sb->itbl_start + inode->ino / BLK_INODES, 1, buf) == -1) {
nuclear@94: 		free(buf);
nuclear@94: 		return -1;
nuclear@94: 	}
nuclear@94: 	free(buf);
nuclear@94: 	return 0;
nuclear@94: }
nuclear@95: 
nuclear@96: /* find a free element in the bitmap and return its number */
nuclear@96: static int find_free(uint32_t *bm, int nbits)
nuclear@95: {
nuclear@96: 	int i, j, nwords = nbits / 32;
nuclear@96: 	uint32_t ent = 0;
nuclear@95: 
nuclear@96: 	for(i=0; i<=nwords; i++) {
nuclear@95: 		if(bm[i] != 0xffffffff) {
nuclear@95: 			for(j=0; j<32; j++) {
nuclear@95: 				if(BM_ISFREE(bm, ent)) {
nuclear@95: 					return ent;
nuclear@95: 				}
nuclear@96: 				ent++;
nuclear@95: 			}
nuclear@95: 
nuclear@95: 			panic("shouldn't happen (in find_free:fs.c)");
nuclear@96: 		} else {
nuclear@96: 			ent += 32;
nuclear@95: 		}
nuclear@95: 	}
nuclear@95: 
nuclear@95: 	return -1;
nuclear@95: }
nuclear@95: 
nuclear@95: static int alloc_inode(struct filesys *fs)
nuclear@95: {
nuclear@95: 	int ino;
nuclear@95: 
nuclear@96: 	if((ino = find_free(fs->sb->ibm, fs->sb->num_inodes)) == -1) {
nuclear@95: 		return -1;
nuclear@95: 	}
nuclear@96: 	BM_SET(fs->sb->ibm, ino);
nuclear@95: 	return 0;
nuclear@95: }
nuclear@96: 
nuclear@96: static int alloc_block(struct filesys *fs)
nuclear@96: {
nuclear@97: 	int bno;
nuclear@96: 
nuclear@97: 	if((bno = find_free(fs->sb->bm, fs->sb->num_blocks)) == -1) {
nuclear@96: 		return -1;
nuclear@96: 	}
nuclear@97: 	BM_SET(fs->sb->bm, bno);
nuclear@96: 	return 0;
nuclear@96: }
nuclear@96: 
nuclear@96: #define BLK_BLKID	(BLKSZ / sizeof(blkid))
nuclear@96: #define MAX_IND		(NDIRBLK + BLK_BLKID)
nuclear@96: #define MAX_DIND	(MAX_IND + BLK_BLKID * BLK_BLKID)
nuclear@96: 
nuclear@97: static int file_block(struct filesys *fs, struct inode *node, int boffs, int allocate)
nuclear@96: {
nuclear@97: 	int res, idx, node_dirty = 0;
nuclear@96: 	blkid *barr;
nuclear@96: 
nuclear@97: 	/* out of bounds */
nuclear@97: 	if(boffs < 0 || boffs >= MAX_DIND) {
nuclear@97: 		return 0;
nuclear@97: 	}
nuclear@97: 
nuclear@96: 	/* is it a direct block ? */
nuclear@96: 	if(boffs < NDIRBLK) {
nuclear@97: 		if(!(res = node->blk[boffs]) && allocate) {
nuclear@97: 			res = node->blk[boffs] = alloc_block(fs);
nuclear@97: 			if(res) {
nuclear@97: 				zero_block(fs, res);
nuclear@97: 				/* also write back the modified inode */
nuclear@97: 				put_inode(fs, node);
nuclear@97: 			}
nuclear@97: 		}
nuclear@97: 		return res;
nuclear@96: 	}
nuclear@96: 
nuclear@97: 	barr = malloc(fs->sb->blksize);
nuclear@96: 	assert(barr);
nuclear@96: 
nuclear@96: 	/* is it an indirect block ? */
nuclear@96: 	if(boffs < MAX_IND) {
nuclear@97: 		int ind_dirty = 0;
nuclear@97: 
nuclear@97: 		if(node->ind) {
nuclear@97: 			/* read the indirect block */
nuclear@97: 			blk_read(fs->bdev, node->ind, 1, barr);
nuclear@97: 		} else {
nuclear@97: 			/* does not exist... try to allocate if requested */
nuclear@97: 			if(!allocate || !(node->ind = alloc_block(fs))) {
nuclear@97: 				res = 0;
nuclear@97: 				goto end;
nuclear@97: 			}
nuclear@97: 
nuclear@97: 			/* allocated a block clear the buffer, and invalidate everything */
nuclear@97: 			memset(barr, 0, sizeof fs->sb->blksize);
nuclear@97: 			node_dirty = 1;
nuclear@97: 			ind_dirty = 1;
nuclear@96: 		}
nuclear@97: 
nuclear@97: 		idx = boffs - NDIRBLK;
nuclear@97: 
nuclear@97: 		if(!(res = barr[idx])) {
nuclear@97: 			if(allocate && (res = barr[idx] = alloc_block(fs))) {
nuclear@97: 				ind_dirty = 1;
nuclear@97: 			}
nuclear@97: 		}
nuclear@97: 
nuclear@97: 		/* write back the indirect block if needed */
nuclear@97: 		if(ind_dirty) {
nuclear@97: 			blk_write(fs->bdev, node->ind, 1, barr);
nuclear@97: 		}
nuclear@96: 		goto end;
nuclear@96: 	}
nuclear@96: 
nuclear@97: 	/* TODO check/rewrite this */
nuclear@97: #if 0
nuclear@96: 	/* is it a double-indirect block ? */
nuclear@96: 	if(boffs < MAX_DIND) {
nuclear@96: 		/* first read the dind block and find the index of the ind block */
nuclear@96: 		if(!node->dind) {
nuclear@97: 			if(allocate) {
nuclear@97: 				/* allocate and zero-out the double indirect block */
nuclear@97: 				res = node->dind = alloc_block(fs);
nuclear@97: 				if(res) {
nuclear@97: 					zero_block(fs, res);
nuclear@97: 				}
nuclear@97: 			} else {
nuclear@97: 				res = 0;
nuclear@97: 				goto end;
nuclear@97: 			}
nuclear@96: 		}
nuclear@96: 		blk_read(fd->bdev, node->dind, 1, barr);
nuclear@96: 		idx = (boffs - MAX_IND) / BLK_BLKID;
nuclear@96: 
nuclear@96: 		/* then read the ind block and find the index of the block */
nuclear@96: 		if(!barr[idx]) {
nuclear@96: 			res = 0;
nuclear@96: 			goto end;
nuclear@96: 		}
nuclear@96: 		blk_read(fd->bdev, barr[idx], 1, barr);
nuclear@96: 		res = barr[(boffs - MAX_IND) % BLK_BLKID];
nuclear@96: 	}
nuclear@97: #endif
nuclear@96: 
nuclear@96: end:
nuclear@97: 	if(node_dirty) {
nuclear@97: 		put_inode(fs, node);
nuclear@97: 	}
nuclear@96: 	free(barr);
nuclear@96: 	return res;
nuclear@96: }