initial commitHEADmaster

8 files changed, 651 insertions, 0 deletions

diff --git a/bfs/bfs.ha b/bfs/bfs.ha
new file mode 100644
index 0000000..bff6ee1
--- /dev/null
+++ b/bfs/bfs.ha
@@ -0,0 +1,284 @@
+use io;
+
+// BFS state
+export type bfs = struct {
+	device: io::handle,
+	bootsector: *bootsector,
+};
+
+// Open a BFS from a device
+export fn open(device: io::handle) (*bfs | error | io::error) = {
+	// Allocate bootsector object
+	const bootsector = alloc(bootsector {
+		...
+	});
+
+	// Allocate BFS object
+	const bfs = alloc(bfs {
+		device = device,
+		bootsector = bootsector,
+	});
+
+	// Pull the data
+	match (pull(bfs)) {
+	case let e: io::error =>
+		free(bootsector);
+		free(bfs);
+		return e;
+	case => void;
+	};
+
+	return bfs;
+};
+
+// Pull the bootsector from the device
+export fn pull(filesystem: *bfs) (void | io::error) = {
+	pread(filesystem.device, filesystem.bootsector: *[512]u8, 0)?;
+};
+
+// Commit the bootsector to the device
+export fn commit(filesystem: *bfs) (void | io::error) = {
+	pwrite(filesystem.device, filesystem.bootsector: *[512]u8, 0)?;
+};
+
+// Close the BFS
+export fn close(filesystem: *bfs) (void | io::error) = {
+	// Commit before closing
+	commit(filesystem)?;
+
+	// Freeing the underlying objects
+	free(filesystem.bootsector);
+	free(filesystem);
+};
+
+// Allocate a block
+export fn allocblock(self: *bfs) (u64 | io::error) = {
+	if (self.bootsector.lastblock == 0) {
+		const blockid = self.bootsector.freeblock;
+
+		self.bootsector.freeblock += 1;
+		commit(self)?;
+
+		return blockid;
+	};
+
+	const blockid = self.bootsector.lastblock;
+
+	let freeblock = free_block { ... };
+	getfreeblock(self, blockid, &freeblock)?;
+
+	if (freeblock.prevblock == 0)
+		self.bootsector.nextblock = 0;
+	self.bootsector.lastblock = freeblock.prevblock;
+
+	commit(self)?;
+
+	return blockid;
+};
+
+// Free a block given a block ID
+export fn freeblock(self: *bfs, blockid: u64) (void | io::error) = {
+	if (self.bootsector.nextblock != 0) {
+		const freeblock = free_block {
+			prevblock = blockid,
+		};
+
+		setfreeblock(self, self.bootsector.nextblock, &freeblock)?;
+	} else
+		self.bootsector.lastblock = blockid;
+
+	const freeblock = free_block { ... };
+	setfreeblock(self, blockid, &freeblock)?;
+	self.bootsector.nextblock = blockid;
+	commit(self)?;
+};
+
+// Clears an inode
+fn zeroinode(self: *bfs, inid: u64) (void | io::error) = {
+	const in = inode { ... };
+	setinode(self, inid, &in)?;
+};
+
+// Allocate a new inode
+export fn allocinode(self: *bfs) (u64 | io::error) = {
+	// If no currently free inode block,
+	if (self.bootsector.nextinblk == 0) {
+		// Allocate new inode block
+		const inblockid = allocblock(self)?;
+
+		// Initialize it
+		const inid = (inblockid << self.bootsector.blocksize) / size(inode): u64 + 1;
+		const inblock = inode_block {
+			freeinode = inid + 1,
+			freecount = (1: u64 << self.bootsector.blocksize) / size(inode): u64 - 2,
+			...
+		};
+
+		// Insert it
+		insert_inodeblock(self, inblockid, &inblock)?;
+
+		// Write to it
+		setinblock(self, inblockid, &inblock)?;
+
+		// Zero the inode
+		zeroinode(self, inid)?;
+
+		return inid;
+	};
+
+	const inblockid = self.bootsector.nextinblk;
+
+	// Get inode block
+	let inblock = inode_block { ... };
+	getinblock(self, inblockid, &inblock)?;
+
+	// Check if inode in inode freelist
+	let inid = inblock.nextinode;
+	if (inblock.nextinode == 0) {
+		// No inode in freelist, bump freeinode
+		inid = inblock.freeinode;
+		inblock.freeinode += 1;
+	} else {
+		// Get the free inode's next inode (stored in block field)
+		let in = inode { ... };
+		getinode(self, inblock.nextinode, &in)?;
+
+		// Update the inode block first inode to it
+		inblock.nextinode = in.block;
+	};
+
+	// Decrement the inode block's freecount
+	inblock.freecount -= 1;
+
+	// If no free inode in the inode block, remove the inode block
+	// from the freelist
+	if (inblock.freecount == 0)
+		remove_inodeblock(self, inblockid, &inblock)?;
+
+	// Finally, set the block and zero the inode
+	setinblock(self, inblockid, &inblock)?;
+	zeroinode(self, inid)?;
+
+	return inid;
+};
+
+// Free an inode given its inode ID
+export fn freeinode(self: *bfs, inid: u64) (void | io::error) = {
+	const inblockid = inid >> (self.bootsector.blocksize - 6);
+
+	let inblock = inode_block { ... };
+	getinblock(self, inblockid, &inblock)?;
+
+	let in = inode { ... };
+	getinode(self, inid, &in)?;
+
+	in.block = inblock.nextinode;
+	inblock.nextinode = inid;
+	inblock.freecount += 1;
+
+	if (inblock.freecount == ((1: u64 << self.bootsector.blocksize) / size(inode): u64 - 1)) {
+		remove_inodeblock(self, inblockid, &inblock)?;
+		freeblock(self, inblockid)?;
+		return;
+	};
+
+	if (inblock.freecount == 1)
+		insert_inodeblock(self, inblockid, &inblock)?;
+
+	setinode(self, inid, &in)?;
+	setinblock(self, inblockid, &inblock)?;
+};
+
+fn insert_inodeblock(self: *bfs, inblockid: u64, inblock: *inode_block) (void | io::error) = {
+	inblock.prevblock = 0;
+
+	if (self.bootsector.nextinblk != 0) {
+		let nextinblock = inode_block { ... };
+		getinblock(self, self.bootsector.nextinblk, &nextinblock)?;
+
+		nextinblock.prevblock = inblockid;
+
+		setinblock(self, self.bootsector.nextinblk, &nextinblock)?;
+	};
+
+	inblock.nextblock = self.bootsector.nextinblk;
+	self.bootsector.nextinblk = inblockid;
+	commit(self)?;
+};
+
+fn remove_inodeblock(self: *bfs, inblockid: u64, inblock: *inode_block) (void | io::error) = {
+	if (inblock.prevblock != 0) {
+		let previnblock = inode_block { ... };
+		getinblock(self, inblock.prevblock, &previnblock)?;
+		previnblock.nextblock = inblock.nextblock;
+		setinblock(self, inblock.prevblock, &previnblock)?;
+	} else {
+		self.bootsector.nextinblk = inblock.nextblock;
+		commit(self)?;
+	};
+
+	if (inblock.nextblock != 0) {
+		let nextinblock = inode_block { ... };
+		getinblock(self, inblock.nextblock, &nextinblock)?;
+		nextinblock.prevblock = inblock.prevblock;
+		setinblock(self, inblock.nextblock, &nextinblock)?;
+	};
+
+	inblock.prevblock = 0;
+	inblock.nextblock = 0;
+};
+
+export fn open_file(self: *bfs, inid: u64) (*file | io::error) = {
+	let in = alloc(inode { ... });
+
+	match (getinode(self, inid, in)) {
+	case let e: io::error =>
+		free(in);
+		return e;
+	case => void;
+	};
+
+	return alloc(file {
+		stream_trait = &file_impl,
+		fs = self,
+		inid = inid,
+		in = in,
+		...
+	});
+};
+
+export fn create_file(self: *bfs) (*file | io::error) = {
+	const inid = allocinode(self)?;
+
+	let file = match (open_file(self, inid)) {
+	case let e: io::error =>
+		freeinode(self, inid)!;
+		return e;
+	case let f: *file =>
+		yield f;
+	};
+
+	file.in.block = match (allocblock(self)) {
+	case let e: io::error =>
+		io::close(file)!;
+		freeinode(self, inid)!;
+		return e;
+	case let b: u64 =>
+		yield b;
+	};
+
+	return file;
+};
+
+export fn root(self: *bfs) (*file | io::error) = {
+	if (self.bootsector.rootinode == 0) {
+		const file = create_file(self)?;
+
+		self.bootsector.rootinode == file.inid;
+		commit(self)!;
+
+		return file;
+	};
+
+	return open_file(self, self.bootsector.rootinode)?;
+};
diff --git a/bfs/blocks.ha b/bfs/blocks.ha
new file mode 100644
index 0000000..ec88e70
--- /dev/null
+++ b/bfs/blocks.ha
@@ -0,0 +1,58 @@
+use io;
+
+fn getblockdata(filesystem: *bfs, blockid: u64, data: []u8) (void | io::error) = {
+	const blockaddr = (blockid << filesystem.bootsector.blocksize): io::off;
+
+	pread(filesystem.device, data, blockaddr)?;
+};
+
+fn setblockdata(filesystem: *bfs, blockid: u64, data: []u8) (void | io::error) = {
+	const blockaddr = (blockid << filesystem.bootsector.blocksize): io::off;
+
+	pwrite(filesystem.device, data, blockaddr)?;
+};
+
+// Inode block: a block used to store
+// inodes
+export type inode_block = struct {
+	// Previous inode block containing
+	// free inodes, or 0
+	@offset(0) prevblock: u64,
+
+	// Next inode block containing
+	// free inodes, or 0
+	@offset(8) nextblock: u64,
+
+	// Next free inode in the block
+	@offset(16) nextinode: u64,
+
+	// Lowest yet to be allocated inode
+	@offset(24) freeinode: u64,
+
+	// Count of free inodes in block
+	@offset(32) freecount: u64,
+};
+
+export fn getinblock(filesystem: *bfs, blockid: u64, inblock: *inode_block) (void | io::error) = {
+	getblockdata(filesystem, blockid, inblock: *[size(inode_block)]u8)?;
+};
+
+export fn setinblock(filesystem: *bfs, blockid: u64, inblock: *inode_block) (void | io::error) = {
+	setblockdata(filesystem, blockid, inblock: *[size(inode_block)]u8)?;
+};
+
+// Free block: a block that has been
+// previously freed
+export type free_block = struct {
+	// Previous freeblock in freelist
+	// or 0
+	@offset(0) prevblock: u64,
+};
+
+export fn getfreeblock(filesystem: *bfs, blockid: u64, freeblock: *free_block) (void | io::error) = {
+	getblockdata(filesystem, blockid, freeblock: *[size(free_block)]u8)?;
+};
+
+export fn setfreeblock(filesystem: *bfs, blockid: u64, freeblock: *free_block) (void | io::error) = {
+	setblockdata(filesystem, blockid, freeblock: *[size(free_block)]u8)?;
+};
diff --git a/bfs/bootsector.ha b/bfs/bootsector.ha
new file mode 100644
index 0000000..dcf33dd
--- /dev/null
+++ b/bfs/bootsector.ha
@@ -0,0 +1,41 @@
+// BFS bootsector, first 512 bytes of a block device
+export type bootsector = struct {
+	// Signature of BFS, 0xCAAA
+	@offset(446) signature: u16,
+
+	// LBA of lowest yet unallocated
+	// free block
+	@offset(448) freeblock: u64,
+
+	// LBA of next block in block
+	// freelist
+	@offset(456) nextblock: u64,
+	@offset(464) lastblock: u64,
+
+	// Inode ID of next free inode block
+	@offset(472) nextinblk: u64,
+	@offset(480) lastinblk: u64,
+
+	// Inode ID of root directory
+	@offset(488) rootinode: u64,
+
+	// Log2 of size of blocks on filesystem 
+	@offset(496) blocksize: u8,
+};
+
+// Fill a bootsector with everything necessary for it to be valid
+export fn bootsector_make(self: *bootsector, rsvdblocks: u64) void = {
+	self.signature = 0xCAAA;
+	self.freeblock = rsvdblocks + 1;
+	self.nextblock = 0;
+	self.lastblock = 0;
+	self.nextinblk = 0;
+	self.lastinblk = 0;
+	self.rootinode = 0;
+	self.blocksize = 12;
+};
+
+// Return whether the bootsector is valid
+export fn bootsector_validate(self: *bootsector) bool = {
+	return self.signature == 0xCAAA;
+};
diff --git a/bfs/errors.ha b/bfs/errors.ha
new file mode 100644
index 0000000..fa5efed
--- /dev/null
+++ b/bfs/errors.ha
@@ -0,0 +1,6 @@
+// Device has no BFS bootsector signature
+export type nosignature = !void;
+
+export type filehole = !void;
+
+export type error = !(nosignature | filehole);
diff --git a/bfs/file.ha b/bfs/file.ha
new file mode 100644
index 0000000..b8f91cb
--- /dev/null
+++ b/bfs/file.ha
@@ -0,0 +1,172 @@
+use io;
+
+// BFS file's implementation of stream
+const file_impl: io::vtable = io::vtable {
+	writer = &file_write,
+	reader = &file_read,
+	...
+};
+
+// BFS file
+export type file = struct {
+	// File implements stream trait
+	stream_trait: io::stream,
+
+	// Filesystem that underlies the file
+	fs: *bfs,
+
+	// Inode ID associated with file
+	inid: u64,
+	
+	// Inode associated with file (owned)
+	in: *inode,
+
+	// Seeking offset in BFS file
+	off: io::off,
+
+	// Block IDs of the successive pages leading to
+	// the resolution of the file content at specified index
+	page_addrs: [16]u64,
+
+	// Indices of entry in each of the successive pages
+	page_idxs: [16]u64
+};
+
+fn file_read(s: *io::stream, buf: []u8) (size | io::EOF | io::error) = {
+	return io::EOF;
+};
+
+fn file_write(s: *io::stream, buf: const []u8) (size | io::error) = {
+	return 0z;
+};
+
+fn file_seek(s: *io::stream, off: io::off, w: io::whence) (io::off | io::error) = {
+	let file = s: *file;
+
+	switch (w) {
+	case io::whence::SET =>
+		file.off = off;
+	case io::whence::CUR =>
+		file.off += off;
+	case io::whence::END =>
+		file.off = file.in.length: io::off + off;
+	};
+
+	return file.off;
+};
+
+// Builds the indices to reach an address
+export fn file_mkindices(self: *file, off: u64) size = {
+	const endshift = self.fs.bootsector.blocksize;
+	const pageshift = endshift - 3;
+
+	const endmask = masklsb(pageshift);
+	const pagemask = endmask >> pageshift;
+
+        self.page_idxs[0] = off & endmask;
+	off >>= endshift;
+
+	let different = 0z;
+
+	for (let i = 1z; i < len(self.page_idxs); i += 1) {
+		const idx = off & pagemask;
+		off >> pageshift;
+
+		if (self.page_idxs[i] != idx)
+			different = i;
+	};
+
+	return different;
+};
+
+// Translate a file offset into a device offset
+export fn file_translate(self: *file, off: u64) (u64 | error | io::error) = {
+	// Calculate the indices
+	const different = file_mkindices(self, off);
+
+	// Calculate the level implied by given address
+	let level = 0u8;
+	for (let i = 0u8; i < 16; i += 1)
+		if (self.page_idxs[i] != 0)
+			level = i;
+
+	// If it is higher than map level of inode, miss
+	if (level > self.in.map_levels)
+		return filehole;
+
+	// Set the level address to be the base
+	self.page_addrs[self.in.map_levels] = self.in.block;
+
+	// DEBUG:
+	const different = self.in.map_levels;
+
+	// Resolve every successive page from
+	// the highest changed index in the address
+	const sz = exp2(self.fs.bootsector.blocksize);
+	let next = self.page_addrs[different];
+	
+	for (let i = different; i > 0; i -= 1) {
+		self.page_addrs[i] = next;
+
+		const loc = next * sz + self.page_idxs[i]*8;
+		pread(self.fs.device, &next: *[8]u8, loc: io::off)?;
+
+		if (next == 0)
+			return filehole;
+	};
+
+	if (next == 0)
+		return filehole;
+
+	// Set the block id of final page
+	self.page_addrs[0] = next;
+
+	// Finally, return the offset in terms of physical
+	// address
+	return next * sz + self.page_idxs[0];
+};
+
+export fn file_map(self: *file, off: u64) (void | error | io::error) = {
+	file_mkindices(self, off);
+	let level = 0u8;
+	for (let i = 0u8; i < 16; i += 1)
+		if (self.page_idxs[i] != 0)
+			level = i;
+
+	// Add as many paging levels as necessary
+	for (let i = level; i < self.in.map_levels; i += 1)
+		file_levelup(self)!;
+};
+
+// Increment the level of pages used to address
+// file contents by one
+export fn file_levelup(self: *file) (void | io::error) = {
+	// Allocate new base block
+	const base = allocblock(self.fs)?;
+
+	// Write the address of previous base
+	// as first entry of new base block
+	const sz = exp2(self.fs.bootsector.blocksize);
+	pwrite(self.fs.device, &self.page_addrs[self.in.map_levels]: *[8]u8, (base * sz): io::off)!;
+	
+	// Update inode
+	self.in.block = base;
+	self.in.map_levels += 1;
+	setinode(self.fs, self.inid, self.in)!;
+};
+
+// Decrement the amount of pages used to address
+// file contents by one
+export fn file_leveldown(self: *file) (void | io::error) = {
+	return;	
+};
+
+// Return 1 << n
+fn exp2(n: uint) uint = {
+	return 1u << n;
+};
+
+// Create a mask with the n least significant bits on
+fn masklsb(n: u64) u64 = {
+	return ~(-1i64 << n: i64): u64;
+};
diff --git a/bfs/inode.ha b/bfs/inode.ha
new file mode 100644
index 0000000..cdd3a80
--- /dev/null
+++ b/bfs/inode.ha
@@ -0,0 +1,49 @@
+use io;
+
+// BFS inode: structure that stores metadata about
+// resources in the filesystem
+export type inode = struct {
+	// Root block of the file content
+	@offset(0) block: u64,
+
+	// Length of file
+	@offset(8) length: u64,
+
+	// Timestamp of last modification
+	@offset(16) last_modified: u64,
+
+	// Owning user name
+	@offset(24) owner: [17]u8,
+
+	// Owning group name
+	@offset(41) group: [17]u8,
+
+	// Number of references of the inode
+	@offset(58) references: u16,
+
+	// Permission flags
+	@offset(60) permissions: u8,
+
+	// Attribute flags
+	@offset(61) attributes: u8,
+
+	// Levels of mapping for file content
+	@offset(62) map_levels: u8,
+
+	// Reserved
+	@offset(63) reserved0: u8
+};
+
+// Get an inode from the filesystem given inode ID
+export fn getinode(filesystem: *bfs, inid: u64, in: *inode) (void | io::error) = {
+	const inaddr = (inid << 6): io::off;
+
+	pread(filesystem.device, in: *[size(inode)]u8, inaddr)?;
+};
+
+// Sets an inode in the filesystem given inode ID
+export fn setinode(filesystem: *bfs, inid: u64, in: *inode) (void | io::error) = {
+	const inaddr = (inid << 6): io::off;
+
+	pwrite(filesystem.device, in: *[size(inode)]u8, inaddr)?;
+};
diff --git a/bfs/pio.ha b/bfs/pio.ha
new file mode 100644
index 0000000..c333d3d
--- /dev/null
+++ b/bfs/pio.ha
@@ -0,0 +1,13 @@
+use io;
+
+// Reads from a stream into a buffer at specified offset
+fn pread(s: io::handle, buf: []u8, off: io::off) (size | io::EOF | io::error) = {
+	io::seek(s, off, io::whence::SET)?;
+	return io::read(s, buf)?;
+};
+
+// Writes into a stream from a buffer at specified offset
+fn pwrite(s: io::handle, buf: const []u8, off: io::off) (size | io::error) = {
+	io::seek(s, off, io::whence::SET)?;
+	return io::write(s, buf)?;
+};
diff --git a/main.ha b/main.ha
new file mode 100644
index 0000000..c9e82c3
--- /dev/null
+++ b/main.ha
@@ -0,0 +1,28 @@
+use fmt;
+use bfs;
+use io;
+use fs;
+use os;
+
+export fn main() void = {
+	//const file = os::open("fs.img", fs::flags::RDWR)!;
+	//defer io::close(file)!;
+	//const filesystem = bfs::open(file)!;
+	//defer bfs::close(filesystem)!;
+
+	//for (let i = 150; i <= 190; i += 1)
+	//	bfs::freeinode(filesystem, i: u64)!;
+	//bfs::freeinode(filesystem, 1484)!;
+	//bfs::freeinode(filesystem, 1485)!;
+	//bfs::freeinode(filesystem, 1486)!;
+	//bfs::freeinode(filesystem, 1487)!;
+	//const inid = bfs::allocinode(filesystem)!;
+	//const blockid = bfs::allocblock(filesystem)!;
+	//bfs::bootsector_make(filesystem.bootsector, 1);
+	//fmt::println(inid)!;
+	//bfs::allocblock(filesystem)!;
+	// bfs::freeblock(filesystem, 8)!;
+	// bfs::freeblock(filesystem, 9)!;
+	// bfs::freeblock(filesystem, 10)!;
+	return;
+};