# HG changeset patch
# User John Tsiombikas <nuclear@member.fsf.org>
# Date 1323916740 -7200
# Node ID 07fe6a614185cbc5c7f5434688f02ccfa229a566
# Parent  ec62cbe00b556fce964f11a36e9479c506950319
filesystem

diff -r ec62cbe00b55 -r 07fe6a614185 include/kdef.h
--- a/include/kdef.h	Sun Dec 11 21:15:35 2011 +0200
+++ b/include/kdef.h	Thu Dec 15 04:39:00 2011 +0200
@@ -31,13 +31,16 @@
 #if defined(KERNEL) || defined(KDEF_ERRNO_H)
 #define EFOO		1 /* I just like to return -1 some times :) */
 
-#define EAGAIN		2
-#define EINVAL		3
-#define ECHILD		4
-#define EBUSY		5
-#define ENOMEM		6
-#define EIO			7
-#define ENOENT		8
+#define EAGAIN			2
+#define EINVAL			3
+#define ECHILD			4
+#define EBUSY			5
+#define ENOMEM			6
+#define EIO				7
+#define ENOENT			8
+#define ENAMETOOLONG	9
+#define ENOSPC			10
+#define EPERM			11
 
 #define EBUG		127	/* for missing features and known bugs */
 #endif	/* errno.h */
@@ -68,4 +71,36 @@
 
 #endif	/* syscall.h */
 
+/* --- defines for sys/stat.h */
+#if defined(KERNEL) || defined(STAT_H)
+
+#define S_IFMT		0170000	/* bit mask for the file type bit fields */
+#define S_IFSOCK	0140000	/* socket */
+#define S_IFLNK		0120000	/* symbolic link */
+#define S_IFREG		0100000	/* regular file */
+#define S_IFBLK		0060000	/* block device */
+#define S_IFDIR		0040000	/* directory */
+#define S_IFCHR		0020000	/* character device */
+#define S_IFIFO		0010000	/* FIFO */
+
+#define S_ISUID		0004000	/* set UID bit */
+#define S_ISGID		0002000	/* set-group-ID bit (see below) */
+#define S_ISVTX		0001000	/* sticky bit (see below) */
+
+#define S_IRWXU		00700	/* mask for file owner permissions */
+#define S_IRUSR		00400	/* owner has read permission */
+#define S_IWUSR		00200	/* owner has write permission */
+#define S_IXUSR		00100	/* owner has execute permission */
+#define S_IRWXG		00070	/* mask for group permissions */
+#define S_IRGRP		00040	/* group has read permission */
+#define S_IWGRP		00020	/* group has write permission */
+#define S_IXGRP		00010	/* group has execute permission */
+#define S_IRWXO		00007	/* mask for permissions for others (not in group) */
+#define S_IROTH		00004	/* others have read permission */
+#define S_IWOTH		00002	/* others have write permission */
+#define S_IXOTH		00001	/* others have execute permission */
+
+#endif	/* sys/stat.h */
+
+
 #endif	/* KERNEL_DEFS_H_ */
diff -r ec62cbe00b55 -r 07fe6a614185 src/fs.c
--- a/src/fs.c	Sun Dec 11 21:15:35 2011 +0200
+++ b/src/fs.c	Thu Dec 15 04:39:00 2011 +0200
@@ -1,7 +1,4 @@
-/* This code is used by the kernel AND by userspace filesystem-related tools.
- * The kernel-specific parts are conditionally compiled in #ifdef KERNEL blocks
- * the rest of the code should be independent.
- */
+/* This code is used by the kernel AND by userspace filesystem-related tools. */
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -9,6 +6,14 @@
 #include <assert.h>
 #include "fs.h"
 #include "bdev.h"
+#include "kdef.h"
+
+/* number of inodes in a block */
+#define BLK_INODES		(BLKSZ / sizeof(struct inode))
+/* number of directory entries in a block */
+#define BLK_DIRENT		(BLKSZ / sizeof(struct dir_entry))
+
+#define BLKBITS				(BLKSZ * 8)
 
 #define BM_IDX(x)			((x) / 32)
 #define BM_BIT(x)			((x) & 0x1f)
@@ -18,11 +23,18 @@
 #define BM_CLR(bm, x)		((bm)[BM_IDX(x)] &= ~(1 << BM_BIT(x)))
 
 
-int openfs(struct filesys *fs, dev_t dev);
+static struct inode *newdir(struct filesys *fs, struct inode *parent);
+static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name);
 static int read_superblock(struct filesys *fs);
 static int write_superblock(struct filesys *fs);
 static int get_inode(struct filesys *fs, int ino, struct inode *inode);
 static int put_inode(struct filesys *fs, struct inode *inode);
+static int find_free(uint32_t *bm, int sz);
+static int alloc_inode(struct filesys *fs);
+static void free_inode(struct filesys *fs, int ino);
+static int alloc_block(struct filesys *fs);
+static void free_block(struct filesys *fs, int ino);
+static int file_block(struct filesys *fs, struct inode *node, int boffs);
 
 int openfs(struct filesys *fs, dev_t dev)
 {
@@ -38,19 +50,164 @@
 
 	/* read the superblock */
 	if(!(fs->sb = malloc(BLKSZ))) {
-		res = -ENOMEM;
-		goto done;
+		blk_close(bdev);
+		return -ENOMEM;
 	}
 	if((res = read_superblock(fs)) != 0) {
-		goto done;
+		blk_close(bdev);
+		return res;
 	}
 
+	return 0;
+}
 
-done:
-	blk_close(bdev);
-	return res;
+int mkfs(struct filesys *fs, dev_t dev)
+{
+	struct filesys *fs;
+	struct superblock *sb;
+	struct block_device *bdev;
+	int i, bcount;
+
+	if(!(bdev = blk_open(dev))) {
+		return -1;
+	}
+	fs->bdev = bdev;
+
+	if(!(sb = malloc(BLKSZ))) {
+		blk_close(bdev);
+		return -1;
+	}
+	fs->sb = sb;
+
+	/* populate the superblock */
+	sb->magic = MAGIC;
+	sb->ver = FS_VER;
+	sb->blksize = BLKSZ;
+
+	sb->num_blocks = bdev->size;
+	sb->num_inodes = sb->num_blocks / 4;
+
+	/* inode bitmap just after the superblock */
+	sb->ibm_start = 2;
+	sb->ibm_count = (sb->num_inodes + BLKBITS - 1) / BLKBITS;
+	/* also allocate and initialize in-memory inode bitmap */
+	sb->ibm = malloc(sb->ibm_count * BLKSZ);
+	assert(sb->ibm);
+	memset(sb->ibm, 0, sb->ibm_count * BLKSZ);
+
+	/* XXX mark inode 0 as used always */
+	BM_SET(sb->ibm, 0);
+
+	/* block bitmap just after the inode bitmap */
+	sb->bm_start = sb->ibm_start + sb->ibm_count;
+	sb->bm_count = (sb->num_blocks + BLKBITS - 1) / BLKBITS;
+	/* also allocate and initialize in-memory block bitmap */
+	sb->bm = malloc(sb->bm_count * BLKSZ);
+	assert(sb->bm);
+	memset(sb->bm, 0, sb->bm_count * BLKSZ);
+
+	/* inode table, just after the block bitmap */
+	sb->itbl_start = sb->bm_start + sb->bm_count;
+	sb->itbl_count = (sb->num_inodes * sizeof(struct inode) + BLKSZ - 1) / BLKSZ;
+
+	/* mark all used blocks as used */
+	bcount = sb->itbl_start + sb->itbl_count;
+	memset(sb->bm, 0xff, bcount / 8);
+	for(i=0; i<bcount % 8; i++) {
+		int bit = bcount / 8 + i;
+		BM_SET(sb->bm, bit);
+	}
+
+	/* create the root directory */
+	sb->root = newdir(fs, 0);
+	sb->root_ino = sb->root->ino;
 }
 
+static struct inode *newdir(struct filesys *fs, struct inode *parent)
+{
+	struct inode *dirnode;
+
+	/* allocate and initialize inode */
+	if(!(dirnode = malloc(sizeof *dirnode))) {
+		return 0;
+	}
+	memset(dirnode, 0, sizeof *dirnode);
+
+	if((dirnode->ino = alloc_inode(fs)) == -1) {
+		printf("failed to allocate inode for a new directory\n");
+		free(dirnode);
+		return 0;
+	}
+	dirnode->mode = S_IFDIR;
+
+	/* add . and .. links */
+	addlink(fs, dirnode, dirnode, ".");
+	addlink(fs, dirnode, parent ? parent : dirnode, "..");
+
+	/* and write the inode to disk */
+	put_inode(fs, dirnode);
+	return dirnode;
+}
+
+static int addlink(struct filesys *fs, struct inode *target, struct inode *node, const char *name)
+{
+	struct dir_entry ent, *data;
+	int boffs, bidx, len;
+
+	if(!(target->mode & S_IFDIR)) {
+		return -ENOTDIR;
+	}
+	if(node->mode & S_IFDIR) {
+		return -EPERM;
+	}
+	/* TODO check that the link does not already exist (EEXIST) */
+
+	if((len = strlen(name)) > MAX_FNAME) {
+		return -ENAMETOOLONG;
+	}
+	ent->ino = node->ino;
+	memcpy(newent->name, name, len + 1);
+
+	/* find a place to put it */
+	if(!(data = malloc(BLKSZ))) {
+		return -ENOMEM;
+	}
+
+	boffs = 0;
+	while((bidx = file_block(fs, target, boffs)) > 0) {
+		/* read the block, and search for an empty entry */
+		blk_read(fs->bdev, bidx, 1, data);
+
+		/* for all directory entries in this block... */
+		for(i=0; i<BLK_DIRENT; i++) {
+			if(data[i].ino == 0) {
+				/* found empty */
+				memcpy(data + i, &ent, sizeof ent);
+				goto success;
+			}
+		}
+		boffs++;
+	}
+
+	/* didn't find any free entries amongst our blocks, allocate a new one */
+	if(!(bidx = alloc_file_block(fs, target, boffs))) {
+		free(data);
+		return -ENOSPC;
+	}
+	/* zero-fill the new block and add the first entry */
+	memset(data, 0, BLKSZ);
+	*data = ent;
+
+success:
+	/* write to disk */
+	blk_write(fs->bdev, bidx, 1, data);
+	node->nlink++;	/* increase reference count */
+
+	free(data);
+	return 0;
+}
+
+
 static int read_superblock(struct filesys *fs)
 {
 	struct superblock *sb = fs->sb;
@@ -123,12 +280,13 @@
 	if(blk_write(fs->bdev, sb->ibm_start, sb->ibm_count, sb->ibm) == -1) {
 		return -1;
 	}
+	/* write the superblock itself */
+	if(blk_write(fs->bdev, 1, 1, sb) == -1) {
+		return -1;
+	}
 	return 0;
 }
 
-/* number of inodes in a block */
-#define BLK_INODES		(BLKSZ / sizeof(struct inode))
-
 /* copy the requested inode from the disk, into the buffer passed in the last arg */
 static int get_inode(struct filesys *fs, int ino, struct inode *inode)
 {
@@ -164,21 +322,24 @@
 	return 0;
 }
 
-static int find_free(uint32_t *bm, int sz)
+/* find a free element in the bitmap and return its number */
+static int find_free(uint32_t *bm, int nbits)
 {
-	int i;
-	uint32_t ent;
+	int i, j, nwords = nbits / 32;
+	uint32_t ent = 0;
 
-	for(i=0; i<=sz/32; i++) {
+	for(i=0; i<=nwords; i++) {
 		if(bm[i] != 0xffffffff) {
-			ent = i * 32;
 			for(j=0; j<32; j++) {
 				if(BM_ISFREE(bm, ent)) {
 					return ent;
 				}
+				ent++;
 			}
 
 			panic("shouldn't happen (in find_free:fs.c)");
+		} else {
+			ent += 32;
 		}
 	}
 
@@ -189,9 +350,82 @@
 {
 	int ino;
 
-	if((ino = find_free(fs->ibm, fs->ibm_count)) == -1) {
+	if((ino = find_free(fs->sb->ibm, fs->sb->num_inodes)) == -1) {
 		return -1;
 	}
-	BM_SET(fs->ibm, ino);
+	BM_SET(fs->sb->ibm, ino);
 	return 0;
 }
+
+static void free_inode(struct filesys *fs, int ino)
+{
+	BM_CLR(fs->sb->ibm, ino);
+}
+
+static int alloc_block(struct filesys *fs)
+{
+	int ino;
+
+	if((ino = find_free(fs->sb->bm, fs->sb->num_blocks)) == -1) {
+		return -1;
+	}
+	BM_SET(fs->sb->bm, ino);
+	return 0;
+}
+
+static void free_block(struct filesys *fs, int ino)
+{
+	BM_CLR(fs->sb->bm, ino);
+}
+
+#define BLK_BLKID	(BLKSZ / sizeof(blkid))
+#define MAX_IND		(NDIRBLK + BLK_BLKID)
+#define MAX_DIND	(MAX_IND + BLK_BLKID * BLK_BLKID)
+
+static int file_block(struct filesys *fs, struct inode *node, int boffs)
+{
+	int res, idx;
+	blkid *barr;
+
+	/* is it a direct block ? */
+	if(boffs < NDIRBLK) {
+		return node->blk[boffs];
+	}
+
+	barr = malloc(BLKSZ);
+	assert(barr);
+
+	/* is it an indirect block ? */
+	if(boffs < MAX_IND) {
+		if(!node->ind) {
+			res = 0;
+			goto end;
+		}
+		blk_read(fs->bdev, node->ind, 1, barr);
+		res = barr[boffs - NDIRBLK];
+		goto end;
+	}
+
+	/* is it a double-indirect block ? */
+	if(boffs < MAX_DIND) {
+		/* first read the dind block and find the index of the ind block */
+		if(!node->dind) {
+			res = 0;
+			goto end;
+		}
+		blk_read(fd->bdev, node->dind, 1, barr);
+		idx = (boffs - MAX_IND) / BLK_BLKID;
+
+		/* then read the ind block and find the index of the block */
+		if(!barr[idx]) {
+			res = 0;
+			goto end;
+		}
+		blk_read(fd->bdev, barr[idx], 1, barr);
+		res = barr[(boffs - MAX_IND) % BLK_BLKID];
+	}
+
+end:
+	free(barr);
+	return res;
+}
diff -r ec62cbe00b55 -r 07fe6a614185 src/fs.h
--- a/src/fs.h	Sun Dec 11 21:15:35 2011 +0200
+++ b/src/fs.h	Thu Dec 15 04:39:00 2011 +0200
@@ -3,9 +3,12 @@
 
 #include <inttypes.h>
 
-#define MAGIC	0xccf5ccf5
-#define FS_VER	1
-#define BLKSZ	1024
+#define MAGIC		0xccf5ccf5
+#define FS_VER		1
+#define BLKSZ		1024
+
+#define NAME_MAX	27	/* +1 termin. +4 ino = 32 per dirent */
+#define PATH_MAX	256
 
 #define SECT_TO_BLK(x)	((x) / (BLKSZ / 512))
 
@@ -32,6 +35,10 @@
 	blkid dind;			/* double-indirect */
 } __attribute__((packed));
 
+struct dir_entry {
+	int ino;
+	char name[NAME_MAX + 1];
+} __attribute__((packed));
 
 struct superblock {
 	uint32_t magic;	/* magic number */
@@ -74,6 +81,7 @@
 
 /* defined in fs.c */
 int openfs(struct filesys *fs, dev_t dev);
+int mkfs(struct filesys *fs, dev_t dev);
 void closefs(struct filesys *fs);
 int find_inode(const char *path);
 
diff -r ec62cbe00b55 -r 07fe6a614185 src/proc.c
--- a/src/proc.c	Sun Dec 11 21:15:35 2011 +0200
+++ b/src/proc.c	Thu Dec 15 04:39:00 2011 +0200
@@ -77,6 +77,8 @@
 	p->id = 1;
 	p->parent = 0;	/* no parent for init */
 
+	p->umask = 022;
+
 	p->ticks_left = TIMESLICE_TICKS;
 	p->next = p->prev = 0;
 
@@ -168,6 +170,8 @@
 	/* copy file table */
 	memcpy(p->files, parent->files, sizeof p->files);
 
+	p->umask = parent->umask;
+
 	/* allocate a kernel stack for the new process */
 	if((p->kern_stack_pg = pgalloc(KERN_STACK_SIZE / PGSIZE, MEM_KERNEL)) == -1) {
 		return -EAGAIN;
diff -r ec62cbe00b55 -r 07fe6a614185 src/proc.h
--- a/src/proc.h	Sun Dec 11 21:15:35 2011 +0200
+++ b/src/proc.h	Thu Dec 15 04:39:00 2011 +0200
@@ -51,6 +51,8 @@
 	/* open files */
 	struct file files[MAX_FD];
 
+	unsigned int umask;
+
 	struct process *child_list;
 
 	struct process *next, *prev;	/* for the scheduler queues */