Orion

/*
 * This file handles the VFS cache.  This includes the VFS tree cache and all
 * the functions for managing the associated structures.  One such structure
 * is the Inode's list of Directory Entries.  Every DirEntry has a name, but
 * also has a hash.  This is for fast comparisons - when iterating the list to
 * search for a name, first check if the hash matches.  This saves a lot of time
 * rather than actually comparing the names.  Entries with hash collisions are
 * placed adjacent in the list.
 */

#include <stdint.h>
#include <string.h>
#include "vfs.h"
#include "inode.h"
#include "cache.h"
#include "../mem/heap.h"
#include "../mem/paging.h"
#include "../mem/frame.h"
#include "../task/task.h"

/* Hash a file name */
static uint32_t
name_hash(const char *name)
{
	uint32_t digest = 5381;
	int c;
	while (c = *name++)
		digest = ((digest << 5) + digest) ^ c; /* digest*33 ^ c */
	return digest;
}

/* Reap any unused branches of the cache tree */
void
cache_reaper(void)
{
	/*
	 * The Cache Reaper attempts to release all the directory entries
	 * belonging to the root of the current task's file system context.
	 * This will in theory release all the associated inodes.  If those
	 * inodes are only held in the cache (not in use, and therefore not
	 * referenced by anything else), they'll be freed and will in turn have
	 * their directory entries released.  This recursive process will prune
	 * most of the VFS cache, leaving only in-use inodes.
	 */
	if (!current)
		return;
	if (!current->fs)
		return;
	if (!current->fs->root)
		return;
	entry_clean(current->fs->root);
	current->fs->root->dirEntries = NULL;
}

/* Get a DirEntry */
DirEntry *
entry_get(DirEntry *entry)
{
	entry->usage++;
	return entry;
}

/* Put a DirEntry */
void
entry_put(DirEntry *entry)
{
	if (--entry->usage)
		return;
	if (entry->inode)
		inode_put(entry->inode);
	kfree(entry);
}

/* Search for a Directory Entry in a list by name */
DirEntry *
entry_find(Inode *inode, const char *name)
{
	if (!inode)
		return NULL;
	acquire(&inode->lock);
	uint32_t search = name_hash(name);
	DirEntry *item = inode->dirEntries;
	/* Look for matching hash */
	while (item) {
		if (item->hash == search)
			break;
		item = item->next;
	}
	if (!item) {
		release(&inode->lock);
		return NULL;
	}
	/* Check all collisions */
	while (item && item->hash == search) {
		if (!strcmp(item->name, name))
			break;
		item = item->next;
	}
	release(&inode->lock);
	if (!item || item->hash != search)
		return NULL;
	return item;
}

/* Add a Directory Entry to a list */
void
entry_add(Inode *inode, DirEntry *insert)
{
	if (!inode)
		return;
	acquire(&inode->lock);
	insert->hash = name_hash(insert->name);
	if (!inode->dirEntries) {
		inode->dirEntries = entry_get(insert);
		release(&inode->lock);
		return;
	}

	/* Try to find a collision */
	DirEntry *collision = inode->dirEntries;
	while (collision->next) {
		if (collision->hash == insert->hash)
			break;
		collision = collision->next;
	}
	/* Add into list */
	insert->next = collision->next;
	collision->next = entry_get(insert);
	release(&inode->lock);
}

/* Remove a Directory Entry from a list */
void
entry_remove(Inode *inode, const char *name)
{
	if (!inode)
		return;
	acquire(&inode->lock);
	uint32_t search = name_hash(name);
	DirEntry *item = inode->dirEntries, *prev = NULL;
	/* Look for matching hash */
	while (item) {
		if (item->hash == search)
			break;
		prev = item;
		item = item->next;
	}
	if (!item) {
		release(&inode->lock);
		return;
	}
	/* Check all collisions */
	while (item && item->hash == search) {
		if (!strcmp(item->name, name))
			break;
		prev = item;
		item = item->next;
	}
	if (!item || item->hash != search) {
		release(&inode->lock);
		return;
	}

	/* Link over item */
	if (prev)
		prev->next = item->next;
	else
		inode->dirEntries = item;
	entry_put(item);
	release(&inode->lock);
}

/* Clean a list of Directory Entries */
void
entry_clean(Inode *inode)
{
	if (!inode)
		return;
	if (!inode->dirEntries)
		return;
	acquire(&inode->lock);
	DirEntry *de, *den;
	for (de = inode->dirEntries; de; de = den) {
		den = de->next;
		entry_put(de);
	}
	release(&inode->lock);
}

/* Get a Page */
Page *
page_get(Page *page)
{
	page->usage++;
	return page;
}

/* Put a Page */
void
page_put(Page *page)
{
	if (--page->usage)
		return;
	free_frame(PG_ADDR(page->frame));
	kfree(page);
}

/* Find a Page by offset */
Page *
page_find(Inode *inode, off_t offset)
{
	if (!inode)
		return NULL;
	acquire(&inode->lock);
	PageCache *cache;
	for (cache = inode->pages; cache; cache = cache->next)
		if (cache->page->offset == PG_ADDR(offset))
			break;
	release(&inode->lock);
	if (!cache)
		return NULL;
	return cache->page;
}

/* Add a page to a list */
void
page_add(Inode *inode, Page *page)
{
	if (!inode)
		return;
	acquire(&inode->lock);
	PageCache *cache;
	if (!inode->pages) {
		inode->pages = kmalloc(sizeof(PageCache));
		cache = inode->pages;
	} else {
		for (cache = inode->pages; cache->next; cache = cache->next);
		cache->next = kmalloc(sizeof(PageCache));
		cache = cache->next;
	}
	cache->page = page_get(page);
	release(&inode->lock);
}

/* Create and add a Page to a list */
Page *
page_create(Inode *inode, page_t frame, off_t offset)
{
	if (!inode)
		return NULL;
	acquire(&inode->lock);
	Page *prev, *page = kmalloc(sizeof(Page));
	page->frame = PG_ADDR(frame);
	page->offset = PG_ADDR(offset);
	page_add(inode, page);
	release(&inode->lock);
	return page;
}

/* Remove a Page from a list */
void
page_remove(Inode *inode, Page *page)
{
	if (!inode)
		return;
	if (!inode->pages)
		return;
	acquire(&inode->lock);

	PageCache *cache, *item;
	if (inode->pages->page == page) {
		item = inode->pages;
		inode->pages = item->next;
	} else {
		for (cache = inode->pages;
		     cache->next; cache = cache->next)
			if (cache->next->page == page)
				break;
		if (!cache->next) {
			release(&inode->lock);
			return;
		}
		item = cache->next;
		cache->next = item->next;
	}
	page_put(page);
	kfree(item);
	release(&inode->lock);
}

/* Clean a list of Pages */
void
page_clean(Inode *inode)
{
	if (!inode)
		return;
	if (!inode->pages)
		return;
	acquire(&inode->lock);
	PageCache *c, *cn;
	for (c = inode->pages; c; c = cn) {
		page_put(c->page);
		cn = c->next;
		kfree(c);
	}
	release(&inode->lock);
}