filesystem.cpp

#include <string.h>
#include <cinttypes>
#include <cmath>

#define SECTOR_SIZE (512)
#define DATA_SIZE (508)

char disk[SECTOR_SIZE * 50];

enum class INodeType : uint32_t {
	NONE = 0,
	FLDR = 'RDLF', // folder inode
	FILE = 'ELIF', // file inode
	DATA = 'ATAD', // data block
};

struct PhysicalBlock {
	INodeType type;
	uint8_t data[SECTOR_SIZE - sizeof(INodeType)];
};

void disk_read(uint8_t* buffer, size_t sector) {
	for (int i = 0; i < SECTOR_SIZE; i++) {
		buffer[i]  = disk[sector * SECTOR_SIZE + i];
	}
}

void disk_write(uint8_t* buffer, size_t sector) {
	for (int i = 0; i < SECTOR_SIZE; i++) {
		disk[sector * SECTOR_SIZE + i] = buffer[i];
	}
}

class Block {
public:
	PhysicalBlock phys;
	size_t sector;

	Block() {

	}

	Block(size_t sector)
		: sector(sector)
	{
	}

	void Read() {
		disk_read((uint8_t*)(&phys), sector);
	}

	void Write() {
		disk_write((uint8_t*)(&phys), sector);
	}

	void Allocate() {
		phys.type = INodeType::DATA;
	}

	void Deallocate() {
		phys.type = INodeType::NONE;
	}

	bool IsAllocated() {
		return phys.type != INodeType::NONE;
	}

	uint8_t* GetPhys() {
		return (uint8_t*)&phys;
	}

	uint8_t* GetData() {
		return phys.data;
	}

};

struct PhysicalINode {
	INodeType type;
	uint8_t name[16];
	uint8_t owner[16];
	uint16_t ref_count;
	uint16_t size;
	uint32_t entries[(SECTOR_SIZE - sizeof(INodeType) - 16 - 16 - sizeof(uint32_t)) / sizeof(uint32_t)];
};

struct Header {
	uint32_t signature1 = 'amoT';
	uint32_t signature2 = 'SFot';
	uint32_t first_free_block;
	uint32_t root_folder;
	uint32_t allocated_count;
	char empty[SECTOR_SIZE - sizeof(uint32_t) * 4];
};

// Physical Block Manager
class PBM {
public:
	static Header* header;
	static Block headerBlock;

	static void Init() {
		headerBlock = Block(1);
		headerBlock.Read();
		header = (Header*)(headerBlock.GetPhys());
	}

	static size_t AllocateBlock(Block* ref = nullptr) {
		size_t block = header->first_free_block;
		for (;;) {
			header->first_free_block++;
			Block block(header->first_free_block);
			block.Read();
			if (block.IsAllocated()) {
				break;
			}
		}
		if (ref != nullptr) {
			ref->sector = block;
			ref->Allocate();
			ref->Write();
		}
		else {
			Block b(block);
			b.Allocate();
			b.Write();
		}
		header->allocated_count++;
		return block;
	}

	static void DeallocateBlock(size_t sector) {
		Block block(sector);
		block.Deallocate();
		block.Write();
		if (header->first_free_block > sector) {
			header->first_free_block = sector;
		}
		header->allocated_count--;
	}

	static void CommitHeader() {
		headerBlock.Write();
	}

};

Header* PBM::header;
Block PBM::headerBlock;

class INode {
public:
	PhysicalINode phys;
	size_t sector;

public:

	INode()
	{

	}

	INode(size_t sector)
		: sector(sector)
	{

	}

	void Read() {
		Block block(sector);
		block.Read();
		phys = *(PhysicalINode*)(block.GetPhys());
	}

	void Write() {
		Block block(sector);
		*(PhysicalINode*)(block.GetPhys()) = phys;
		block.Write();
	}

	void ReadData(uint8_t* buffer, int offset, int length) {
		int first_block = offset / DATA_SIZE;
		int last_block = ceil((offset + length) / (1.0 * DATA_SIZE));
		for (int i = first_block; i < last_block; i++) {
			Block block(phys.entries[i]);
			block.Read();
			if (i + 1 < last_block) {
				memcpy(buffer + i * DATA_SIZE, block.GetData(), DATA_SIZE);
			}
			else {
				memcpy(buffer + i * DATA_SIZE, block.GetData(), length % DATA_SIZE);
			}
		}
	}

	void WriteData(uint8_t* buffer, int offset, int length) {
		int first_block = offset / DATA_SIZE;
		int last_block = ceil((offset + length) / (1.0 * DATA_SIZE));
		for (int i = first_block; i < last_block; i++) {
			Block block(phys.entries[i]);
			if (i + 1 < last_block) {
				memcpy(block.GetData(), buffer + i * DATA_SIZE, DATA_SIZE);
			}
			else {
				memcpy(block.GetData(), buffer + i * DATA_SIZE, length % DATA_SIZE);
			}
			block.Write();
		}
	}

	/// this method does not auto commit the header, will need to do it after the call
	bool Delete(bool* deleted = nullptr) {
		if (sector == 0) {
			return false;
		}
		if (phys.type == INodeType::FILE || phys.type == INodeType::FLDR) {
			// if we have no more references delete all the nodes and free this one
			if (phys.ref_count == 0 || phys.ref_count - 1 == 0) {
				// for folder we need to remove all the child files
				if (phys.type == INodeType::FLDR) {
					for (int i = 0; i < phys.size; i++) {
						INode node(phys.entries[i]);
						node.Read();
						node.Delete();
					}
				}
				// for file we just need to remove all the data blocks
				else {
					int last_block = ceil(phys.size / (1.0 * DATA_SIZE));
					for (int i = 0; i < last_block; i++) {
						PBM::DeallocateBlock(phys.entries[i]);
					}
				}
				// free this node
				PBM::DeallocateBlock(sector);
				sector = 0;
				if (deleted != nullptr) *deleted = true;
			}
			else {
				// there are still references to this file, decrease the ref counter
				phys.ref_count--;
				Write();
				if (deleted != nullptr) *deleted = false;
			}
			return true;
		}
		return false;
	}

	bool Resize(size_t newsize) {
		if (phys.type != INodeType::FILE) return false;
		if (phys.size >= newsize) {
			// deallocate blocks
			int first_block = newsize / DATA_SIZE;
			int last_block = ceil(phys.size / (1.0 * DATA_SIZE));
			for (int i = first_block; i < last_block; i++) {				 
				PBM::DeallocateBlock(phys.entries[i]);
			}
		}
		else {
			// add more blocks
			int first_block = phys.size / DATA_SIZE;
			int last_block = ceil(newsize / (1.0 * DATA_SIZE));
			if (last_block >= sizeof(phys.entries) / sizeof(size_t)) {
				return false;
			}
			for (int i = first_block; i < last_block; i++) {
				size_t newBlock = PBM::AllocateBlock();
				phys.entries[i] = newBlock;
			}
		}
		PBM::CommitHeader();
		phys.size = newsize;
		return true;
	}

};

#include <fstream>

void CreateFilesystem() {
	Header header;
	header.first_free_block = 3;
	header.root_folder = 2;
	header.allocated_count = 1;

	INode root(2);
	root.phys.type = INodeType::FLDR;
	memcpy(root.phys.name, "<root>", sizeof("<root>"));
	memcpy(root.phys.owner, "root", sizeof("root"));
	root.phys.ref_count = 1;
	root.phys.size = 0;

	disk_write((uint8_t*)(&header), 1);
	disk_write((uint8_t*)(&root), 2);
}

size_t FindInFolder(size_t inode, char* name) {
	INode node(inode);
	node.Read();
	if (node.phys.type != INodeType::FLDR) {
		return 0;
	}
	for (uint32_t i = 0; i < node.phys.size; i++) {
		INode child(node.phys.entries[i]);
		child.Read();
		if (strcmp((char*)child.phys.name, name) == 0) {
			return node.phys.entries[i];
		}
	}
	return 0;
}

size_t Resolve(const char* path) {
	// this is kinda long just incase we will need it
	char* temp = new char[strlen(path)];
	char* temp_start = temp;
	
	size_t currentBlock = PBM::header->root_folder;
	while (*path) {
		if (*path == '/' || *path == '\\') {
			*temp = 0;
			temp = temp_start;
			currentBlock = FindInFolder(currentBlock, temp);
			if (currentBlock == 0) {
				delete[] temp;
				return 0;
			}
		}
		else {
			*temp = *path;
		}
		temp++;
		path++;
	}
	// resolve last block if any
	if (temp != temp_start) {
		*temp = 0;
		temp = temp_start;
		currentBlock = FindInFolder(currentBlock, temp);
		if (currentBlock == 0) {
			delete[] temp; // this delete fails
			return 0;
		}
	}

	temp = temp_start;
	delete[] temp;
	return currentBlock;
}

/// requirements:
/// path must be absolute
/// path must *not* start with / or \
/// path must *not* end with / or \
/// 
bool MakeDir(const char* path, const char* owner) {
	// check if exists
	if (Resolve(path) != 0) {
		return false;
	}

	// find last /
	char* ptr = (char*)strrchr(path, '/');
	char* ptr2 = (char*)strrchr(path, '\\');
	if (ptr2 > ptr) {
		ptr = ptr2;
	}
	*ptr = 0;
	char* name = ptr + 1;

	bool success = false;

	// resolve path to parent
	size_t resolved = Resolve(path);
	if (resolved != 0) {

		// allocate the new folder
		INode node;
		PBM::AllocateBlock((Block*)(&node));
		node.phys.type = INodeType::FLDR;
		memcpy(node.phys.name, name, strlen(name) + 1);
		memcpy(node.phys.owner, owner, strlen(owner) + 1);
		node.phys.ref_count = 1;
		node.phys.size = 0;
		node.Write();

		// put it in the parent
		INode parent(resolved);
		parent.Read();
		parent.phys.size++;
		parent.phys.entries[parent.phys.size] = node.sector;
		parent.Write();

		PBM::CommitHeader();
	}

	// restore string
	if (ptr == ptr2) {
		*ptr = '\\';
	}
	else {
		*ptr = '/';
	}

	return success;
}

#include <iostream>

int main() {
	CreateFilesystem();

	PBM::Init();

	MakeDir("test", "root");

	std::cout << "test" << std::endl;

	std::ofstream out("tomatofs.hdd");
	out.write(disk, sizeof(disk));
	out.flush();

	std::cin.get();
}