haiku.git

/*
 * Copyright 2005, Axel Dörfler, axeld@pinc-software.de. All rights reserved.
 * Distributed under the terms of the MIT License.
 */

/** This module applies rules that were learned by another component by
 *	evaluating the cache log files.
 *
 *	Note: this module is using private kernel API and is definitely not
 *		meant to be an example on how to write modules.
 */


#include <KernelExport.h>
#include <Node.h>

#include <util/kernel_cpp.h>
#include <util/AutoLock.h>
#include <thread.h>
#include <team.h>
#include <file_cache.h>
#include <generic_syscall.h>
#include <syscalls.h>

#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include <ctype.h>


#define TRACE_CACHE_MODULE
#ifdef TRACE_CACHE_MODULE
#	define TRACE(x) dprintf x
#else
#	define TRACE(x) ;
#endif


extern dev_t gBootDevice;


enum match_type {
	NO_MATCH,
	CONTINUE_MATCHING,
	MATCH,
};

enum rule_type {
	LAUNCH_TYPE		= 0x1,
	OPEN_FILE_TYPE	= 0x2,
	ARGUMENTS_TYPE	= 0x4,
	ALL_TYPES		= 0xff,
};

struct head {
	head();

	struct list_link	link;
	mount_id			device;
	vnode_id			parent;
	vnode_id			node;
	char				name[B_FILE_NAME_LENGTH];
	int32				confidence;
	bigtime_t			timestamp;
	int32				used_count;
};

struct body {
	struct list_link	link;
};

class Rule {
	public:
		Rule(rule_type type);
		~Rule();

		status_t InitCheck();
		rule_type Type() const { return fType; }

		void AddHead(struct head *head);
		void AddBody(struct body *body);

		struct head *FindHead(mount_id device, vnode_id node);
		match_type Match(int32 state, mount_id device, vnode_id parent,
			const char *name);
		void Apply();

		void KnownFileOpened() { fKnownFileOpened++; }
		void UnknownFileOpened() { fUnknownFileOpened++; }

		void Dump();

		Rule *&Next() { return fNext; }

		static uint32 NextOffset() { return offsetof(Rule, fNext); }
		static status_t LoadRules();

	private:
		Rule		*fNext;
		rule_type	fType;
		struct list	fHeads;
		struct list	fBodies;
		int32		fHeadCount;
		int32		fBodyCount;
		int32		fConfidence;
		int32		fAppliedCount;
		int32		fKnownFileOpened;
		int32		fUnknownFileOpened;
};

struct rule_state {
	list_link	link;
	Rule		*rule;
	int32		state;
};

struct rules {
	rules		*next;
	char		name[B_FILE_NAME_LENGTH];
	Rule		*first;
};

struct team_rules {
	~team_rules();

	team_rules	*next;
	team_id		team;
	struct list	states;
	struct list	applied;
	bigtime_t	timestamp;
};

class RuleMatcher {
	public:
		RuleMatcher(team_id team, const char *name = NULL);
		~RuleMatcher();

		void GotFile(mount_id device, vnode_id node);
		void GotArguments(int32 argCount, char * const *args);

	private:
		void _CollectRules(const char *name);
		void _MatchFile(mount_id device, vnode_id parent, const char *name);
		void _MatchArguments(int32 argCount, char * const *args);

		team_rules	*fRules;
};


struct RuleHash {
		typedef char*		KeyType;
		typedef	rules		ValueType;

		size_t HashKey(KeyType key) const
		{
			return hash_hash_string(key);
		}

		size_t Hash(ValueType* value) const
		{
			return HashKey(value->name);
		}

		bool Compare(KeyType key, ValueType* rules) const
		{
			return strcmp(rules->name, key) == 0;
		}

		ValueType*& GetLink(ValueType* value) const
		{
			return value->fNext;
		}
};


struct TeamHash {
		typedef team_id		KeyType;
		typedef	team_rules	ValueType;

		size_t HashKey(KeyType key) const
		{
			return key;
		}

		size_t Hash(ValueType* value) const
		{
			return value->team;
		}

		bool Compare(KeyType key, ValueType* value) const
		{
			return value->team == key;
		}

		ValueType*& GetLink(ValueType* value) const
		{
			return value->fNext;
		}
};


typedef BOpenHashTable<RuleHash> RuleTable;
typedef BOpenHashTable<TeamHash> TeamTable;

static RuleTable *sRulesHash;
static TeamTable *sTeamHash;
static recursive_lock sLock;
int32 sMinConfidence = 5000;


static void
team_gone(team_id team, void *_rules)
{
	team_rules *rules = (team_rules *)_rules;

	recursive_lock_lock(&sLock);
	sTeamHash->Remove(rules);
	recursive_lock_unlock(&sLock);

	delete rules;
}


team_rules::~team_rules()
{
	// free rule states

	rule_state *state;
	while ((state = (rule_state *)list_remove_head_item(&states)) != NULL) {
		delete state;
	}
	while ((state = (rule_state *)list_remove_head_item(&applied)) != NULL) {
		delete state;
	}

	stop_watching_team(team, team_gone, this);
}


//	#pragma mark -


head::head()
{
	device = -1;
	parent = -1;
	node = -1;
	name[0] = '\0';
	confidence = -1;
	timestamp = 0;
	used_count = 0;
}


static inline rules *
find_rules(const char *name)
{
	return sRulesHash->Lookup(name);
}


/**	Finds the rule matching to the criteria (name and type).
 *	If there is no matching rule yet, it will create one.
 *	It will only return NULL in out of memory conditions.
 */

static Rule *
get_rule(const char *name, rule_type type)
{
	struct rules *rules = find_rules(name);
	if (rules == NULL) {
		// add new rules
		rules = new ::rules;
		if (rules == NULL)
			return NULL;

		strlcpy(rules->name, name, B_FILE_NAME_LENGTH);
		rules->first = NULL;
		sRulesHash->Insert(rules);
	}

	// search for matching rule type

	Rule *rule = rules->first;
	while (rule && rule->Type() != type) {
		rule = rule->Next();
	}

	if (rule == NULL) {
		TRACE(("create new rule for \"%s\", type %d\n", name, type));
		// there is no rule yet, create one
		rule = new Rule(type);
		if (rule == NULL)
			return NULL;

		rule->Next() = rules->first;
		rules->first = rule;
	}

	return rule;
}


static void
eat_spaces(char *&line)
{
	// eat starting white space
	while (isspace(line[0]))
		line++;
}


static bool
parse_ref(const char *string, mount_id &device, vnode_id &node, char **_end = NULL)
{
	// parse node ref
	char *end;
	device = strtol(string, &end, 0);
	if (end == NULL || device == 0 || end[0] != ':')
		return false;

	node = strtoull(end + 1, &end, 0);
	if (end == NULL || end[0] != ':')
		return false;

	if (_end)
		*_end = end + 1;
	return true;
}


static void
ignore_line(char *&line)
{
	while (line[0] && line[0] != '\n')
		line++;
}


static const char *
get_name(char *&line)
{
	if (line[0] != '"')
		return NULL;

	const char *name = ++line;

	while (line[0] && line[0] != '"') {
		if (line[0] == '\\')
			line++;
		line++;
	}

	line[0] = '\0';
	line++;

	return name;
}


static status_t
load_rules()
{
	int fd = open("/etc/cache_rules", O_RDONLY);
	if (fd < B_OK)
		return fd;

	struct stat stat;
	if (fstat(fd, &stat) != 0) {
		close(fd);
		return errno;
	}

	if (stat.st_size > 32767) {
		// for safety reasons
		// ToDo: make a bit larger later
		close(fd);
		return B_BAD_DATA;
	}

	char *buffer = (char *)malloc(stat.st_size + 1);
	if (buffer == NULL) {
		close(fd);
		return B_NO_MEMORY;
	}

	if (read(fd, buffer, stat.st_size) < stat.st_size) {
		free(buffer);
		close(fd);
		return B_ERROR;
	}

	buffer[stat.st_size] = '\0';

	char *line = buffer;
	while (line[0]) {
		switch (line[0]) {
			case 'c':
			{
				mount_id device;
				vnode_id node;

				// direct "command opens file" rule
				line += 2;
				if (parse_ref(line, device, node, &line)) {
					const char *fileName = get_name(line);
					if (fileName != NULL) {
						eat_spaces(line);
						const char *name = get_name(line);
						if (name != NULL) {
							eat_spaces(line);
							int32 confidence = strtoul(line, &line, 10);
							TRACE(("c %ld:%lld:%s %s %ld\n", device, node, fileName, name, confidence));

							struct head *head = new ::head;
							head->device = device;
							head->parent = node;
							strlcpy(head->name, fileName, B_FILE_NAME_LENGTH);
							head->confidence = confidence;

							Rule *rule = get_rule(name, LAUNCH_TYPE);
							if (rule != NULL)
								rule->AddHead(head);
							break;
						}
					}
				}
				ignore_line(line);
				break;
			}
			default:
				// unknown rule - ignore line
				ignore_line(line);
				break;
		}
		line++;
	}

	free(buffer);
	close(fd);
	return B_OK;
}


//	#pragma mark -


Rule::Rule(rule_type type)
	:
	fType(type),
	fHeadCount(0),
	fBodyCount(0),
	fAppliedCount(0),
	fKnownFileOpened(0),
	fUnknownFileOpened(0)
{
	list_init(&fHeads);
	list_init(&fBodies);
}


Rule::~Rule()
{
	struct head *head;
	while ((head = (struct head *)list_remove_head_item(&fHeads)) != NULL) {
		delete head;
	}

	struct body *body;
	while ((body = (struct body *)list_remove_head_item(&fBodies)) != NULL) {
		delete body;
	}
}


void
Rule::AddHead(struct head *head)
{
	list_add_item(&fHeads, head);
	fHeadCount++;
}


void
Rule::AddBody(struct body *body)
{
	list_add_item(&fBodies, body);
	fBodyCount++;
}


void
Rule::Apply()
{
	TRACE(("Apply rule %p", this));

	struct head *head = NULL;
	while ((head = (struct head *)list_get_next_item(&fHeads, head)) != NULL) {
		if (head->confidence < sMinConfidence)
			continue;

		// prefetch node
		void *vnode;
		if (vfs_entry_ref_to_vnode(head->device, head->parent, head->name, &vnode) == B_OK) {
			vfs_vnode_to_node_ref(vnode, &head->device, &head->node);

			TRACE(("prefetch: %ld:%lld:%s\n", head->device, head->parent, head->name));
			cache_prefetch(head->device, head->node, 0, ~0UL);

			// ToDo: put head into a hash so that some statistics can be backpropagated quickly
		} else {
			// node doesn't exist anymore
			head->confidence = -1;
		}
	}

	fAppliedCount++;
}


struct head *
Rule::FindHead(mount_id device, vnode_id node)
{
	// ToDo: use a hash for this!

	struct head *head = NULL;
	while ((head = (struct head *)list_get_next_item(&fHeads, head)) != NULL) {
		if (head->node == node && head->device == device)
			return head;
	}

	return NULL;
}


void
Rule::Dump()
{
	dprintf("  applied: %ld, known: %ld, unknown: %ld\n",
		fAppliedCount, fKnownFileOpened, fUnknownFileOpened);

	struct head *head = NULL;
	while ((head = (struct head *)list_get_next_item(&fHeads, head)) != NULL) {
		dprintf("  %ld:%lld:\"%s\", ", head->device, head->parent, head->name);
		if (head->confidence < sMinConfidence)
			dprintf("-\n");
		else
			dprintf("%ld (%ld), %lld us\n", head->used_count,
				head->used_count - fAppliedCount, head->timestamp);
	}
}


//	#pragma mark -


RuleMatcher::RuleMatcher(team_id team, const char *name)
	:
	fRules(NULL)
{
	recursive_lock_lock(&sLock);

	if (name == NULL)
		return;

	fRules = sTeamHash->Lookup(team);
	if (fRules != NULL)
		return;

	fRules = new team_rules;
	if (fRules == NULL)
		return;

	fRules->team = team;
	list_init(&fRules->states);
	list_init(&fRules->applied);

dprintf("new rules for \"%s\"\n", name);
	_CollectRules(name);

	sTeamHash->Insert(fRules);
	start_watching_team(team, team_gone, fRules);

	fRules->timestamp = system_time();
}


RuleMatcher::~RuleMatcher()
{
	recursive_lock_unlock(&sLock);
}


void
RuleMatcher::_CollectRules(const char *name)
{
	struct rules *rules = sRulesHash->Lookup(name);
	if (rules == NULL) {
		// there are no rules for this command
		return;
	}

	// allocate states for all rules found

	for (Rule *rule = rules->first; rule != NULL; rule = rule->Next()) {
		rule_state *state = new rule_state;
		if (state == NULL)
			continue;

		TRACE(("found rule %p for \"%s\"\n", rule, rules->name));
		state->rule = rule;
		state->state = 0;

		if (rule->Type() == LAUNCH_TYPE) {
			// we can already prefetch the simplest of all rules here
			// (it's fulfilled as soon as the command is launched)
			rule->Apply();
			list_add_item(&fRules->applied, state);
		} else
			list_add_item(&fRules->states, state);
	}
}


void
RuleMatcher::GotFile(mount_id device, vnode_id node)
{
	if (fRules == NULL)
		return;

	// try to match the file with all open rules

	rule_state *state = NULL;
	while ((state = (rule_state *)list_get_next_item(&fRules->states, state)) != NULL) {
		if ((state->rule->Type() & OPEN_FILE_TYPE) == 0)
			continue;

		// ToDo
	}

	bigtime_t diff = system_time() - fRules->timestamp;

	// propagate the usage of this file back to the applied rules

	while ((state = (rule_state *)list_get_next_item(&fRules->applied, state)) != NULL) {
		struct head *head = state->rule->FindHead(device, node);
		if (head != NULL) {
			// grow confidence
			state->rule->KnownFileOpened();
			head->used_count++;
			if (head->used_count > 1)
				head->timestamp = (head->timestamp * (head->used_count - 1) + diff) / head->used_count;
		} else
			state->rule->UnknownFileOpened();
	}
}


void
RuleMatcher::GotArguments(int32 argCount, char * const *args)
{
	if (fRules == NULL)
		return;

	// try to match the arguments with all open rules

	rule_state *state = NULL;
	while ((state = (rule_state *)list_get_next_item(&fRules->states, state)) != NULL) {
		if ((state->rule->Type() & ARGUMENTS_TYPE) == 0)
			continue;

		// ToDo
	}
}


//	#pragma mark -


static void
node_opened(struct vnode *vnode, int32 fdType, dev_t device, vnode_id parent,
	vnode_id node, const char *name, off_t size)
{
	if (device < gBootDevice) {
		// we ignore any access to rootfs, pipefs, and devfs
		// ToDo: if we can ever move the boot device on the fly, this will break
		return;
	}

	// ToDo: this is only needed if there is no rule for this team yet - ideally,
	//	it would be handled by the log module, so that the vnode ID is sufficient
	//	to recognize a rule
	char buffer[B_FILE_NAME_LENGTH];
	if (name == NULL
		&& vfs_get_vnode_name(vnode, buffer, sizeof(buffer)) == B_OK)
		name = buffer;

	//dprintf("opened: %ld:%lld:%lld:%s (%s)\n", device, parent, node, name, thread_get_current_thread()->name);
	RuleMatcher matcher(team_get_current_team_id(), name);
	matcher.GotFile(device, node);
}


static void
node_launched(size_t argCount, char * const *args)
{
	//dprintf("launched: %s (%s)\n", args[0], thread_get_current_thread()->name);
	RuleMatcher matcher(team_get_current_team_id());
	matcher.GotArguments(argCount, args);
}


static void
uninit()
{
	recursive_lock_lock(&sLock);

	// free all sessions from the hashes

	team_rules *teamRules = sTeamHash->Clear(true);
	while (teamRules != NULL) {
		team_rules *next = teamRules->next;
		delete teamRules;
		teamRules = next;
	}

	struct rules *rules = sRulesHash->Clear(true);
	while (rules != NULL) {
		Rule *rule = rules->first;
		while (rule) {
			Rule *next = rule->Next();

			dprintf("Rule %p \"%s\"\n", rule, rules->name);
			rule->Dump();

			delete rule;
			rule = next;
		}

		struct rules *next = rules->next;
		delete rules;
		rules = next;
	}

	delete sTeamHash;
	delete sRulesHash;
	recursive_lock_destroy(&sLock);
}


static status_t
init()
{
	sTeamHash = new(std::nothrow) TeamTable();
	if (sTeamHash == NULL || sTeamHash->Init(64) != B_OK)
		return B_NO_MEMORY;

	status_t status;

	sRulesHash = new(std::nothrow) RuleTable();
	if (sRulesHash == NULL || sRulesHash->Init(64) != B_OK) {
		delete sTeamHash;
		return B_NO_MEMORY;
	}

	recursive_lock_init(&sLock, "rule based prefetcher");

	load_rules();
	return B_OK;
}


static status_t
std_ops(int32 op, ...)
{
	switch (op) {
		case B_MODULE_INIT:
			return init();

		case B_MODULE_UNINIT:
			uninit();
			return B_OK;

		default:
			return B_ERROR;
	}
}


static struct cache_module_info sRuleBasedPrefetcherModule = {
	{
		CACHE_MODULES_NAME "/rule_based_prefetcher/v1",
		0,
		std_ops,
	},
	node_opened,
	NULL,
	node_launched,
};


module_info *modules[] = {
	(module_info *)&sRuleBasedPrefetcherModule,
	NULL
};