1/*
2 * Copyright 2005, Axel D��rfler, axeld@pinc-software.de. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 */
5
6/** This module applies rules that were learned by another component by
7 *	evaluating the cache log files.
8 *
9 *	Note: this module is using private kernel API and is definitely not
10 *		meant to be an example on how to write modules.
11 */
12
13
14#include <KernelExport.h>
15#include <Node.h>
16
17#include <util/kernel_cpp.h>
18#include <util/AutoLock.h>
19#include <thread.h>
20#include <team.h>
21#include <file_cache.h>
22#include <generic_syscall.h>
23#include <syscalls.h>
24
25#include <unistd.h>
26#include <stdlib.h>
27#include <string.h>
28#include <stdio.h>
29#include <errno.h>
30#include <ctype.h>
31
32
33#define TRACE_CACHE_MODULE
34#ifdef TRACE_CACHE_MODULE
35#	define TRACE(x) dprintf x
36#else
37#	define TRACE(x) ;
38#endif
39
40
41extern dev_t gBootDevice;
42
43
44enum match_type {
45	NO_MATCH,
46	CONTINUE_MATCHING,
47	MATCH,
48};
49
50enum rule_type {
51	LAUNCH_TYPE		= 0x1,
52	OPEN_FILE_TYPE	= 0x2,
53	ARGUMENTS_TYPE	= 0x4,
54	ALL_TYPES		= 0xff,
55};
56
57struct head {
58	head();
59
60	struct list_link	link;
61	mount_id			device;
62	vnode_id			parent;
63	vnode_id			node;
64	char				name[B_FILE_NAME_LENGTH];
65	int32				confidence;
66	bigtime_t			timestamp;
67	int32				used_count;
68};
69
70struct body {
71	struct list_link	link;
72};
73
74class Rule {
75	public:
76		Rule(rule_type type);
77		~Rule();
78
79		status_t InitCheck();
80		rule_type Type() const { return fType; }
81
82		void AddHead(struct head *head);
83		void AddBody(struct body *body);
84
85		struct head *FindHead(mount_id device, vnode_id node);
86		match_type Match(int32 state, mount_id device, vnode_id parent,
87			const char *name);
88		void Apply();
89
90		void KnownFileOpened() { fKnownFileOpened++; }
91		void UnknownFileOpened() { fUnknownFileOpened++; }
92
93		void Dump();
94
95		Rule *&Next() { return fNext; }
96
97		static uint32 NextOffset() { return offsetof(Rule, fNext); }
98		static status_t LoadRules();
99
100	private:
101		Rule		*fNext;
102		rule_type	fType;
103		struct list	fHeads;
104		struct list	fBodies;
105		int32		fHeadCount;
106		int32		fBodyCount;
107		int32		fConfidence;
108		int32		fAppliedCount;
109		int32		fKnownFileOpened;
110		int32		fUnknownFileOpened;
111};
112
113struct rule_state {
114	list_link	link;
115	Rule		*rule;
116	int32		state;
117};
118
119struct rules {
120	rules		*next;
121	char		name[B_FILE_NAME_LENGTH];
122	Rule		*first;
123};
124
125struct team_rules {
126	~team_rules();
127
128	team_rules	*next;
129	team_id		team;
130	struct list	states;
131	struct list	applied;
132	bigtime_t	timestamp;
133};
134
135class RuleMatcher {
136	public:
137		RuleMatcher(team_id team, const char *name = NULL);
138		~RuleMatcher();
139
140		void GotFile(mount_id device, vnode_id node);
141		void GotArguments(int32 argCount, char * const *args);
142
143	private:
144		void _CollectRules(const char *name);
145		void _MatchFile(mount_id device, vnode_id parent, const char *name);
146		void _MatchArguments(int32 argCount, char * const *args);
147
148		team_rules	*fRules;
149};
150
151
152struct RuleHash {
153		typedef char*		KeyType;
154		typedef	rules		ValueType;
155
156		size_t HashKey(KeyType key) const
157		{
158			return hash_hash_string(key);
159		}
160
161		size_t Hash(ValueType* value) const
162		{
163			return HashKey(value->name);
164		}
165
166		bool Compare(KeyType key, ValueType* rules) const
167		{
168			return strcmp(rules->name, key) == 0;
169		}
170
171		ValueType*& GetLink(ValueType* value) const
172		{
173			return value->fNext;
174		}
175};
176
177
178struct TeamHash {
179		typedef team_id		KeyType;
180		typedef	team_rules	ValueType;
181
182		size_t HashKey(KeyType key) const
183		{
184			return key;
185		}
186
187		size_t Hash(ValueType* value) const
188		{
189			return value->team;
190		}
191
192		bool Compare(KeyType key, ValueType* value) const
193		{
194			return value->team == key;
195		}
196
197		ValueType*& GetLink(ValueType* value) const
198		{
199			return value->fNext;
200		}
201};
202
203
204typedef BOpenHashTable<RuleHash> RuleTable;
205typedef BOpenHashTable<TeamHash> TeamTable;
206
207static RuleTable *sRulesHash;
208static TeamTable *sTeamHash;
209static recursive_lock sLock;
210int32 sMinConfidence = 5000;
211
212
213static void
214team_gone(team_id team, void *_rules)
215{
216	team_rules *rules = (team_rules *)_rules;
217
218	recursive_lock_lock(&sLock);
219	sTeamHash->Remove(rules);
220	recursive_lock_unlock(&sLock);
221
222	delete rules;
223}
224
225
226team_rules::~team_rules()
227{
228	// free rule states
229
230	rule_state *state;
231	while ((state = (rule_state *)list_remove_head_item(&states)) != NULL) {
232		delete state;
233	}
234	while ((state = (rule_state *)list_remove_head_item(&applied)) != NULL) {
235		delete state;
236	}
237
238	stop_watching_team(team, team_gone, this);
239}
240
241
242//	#pragma mark -
243
244
245head::head()
246{
247	device = -1;
248	parent = -1;
249	node = -1;
250	name[0] = '\0';
251	confidence = -1;
252	timestamp = 0;
253	used_count = 0;
254}
255
256
257static inline rules *
258find_rules(const char *name)
259{
260	return sRulesHash->Lookup(name);
261}
262
263
264/**	Finds the rule matching to the criteria (name and type).
265 *	If there is no matching rule yet, it will create one.
266 *	It will only return NULL in out of memory conditions.
267 */
268
269static Rule *
270get_rule(const char *name, rule_type type)
271{
272	struct rules *rules = find_rules(name);
273	if (rules == NULL) {
274		// add new rules
275		rules = new ::rules;
276		if (rules == NULL)
277			return NULL;
278
279		strlcpy(rules->name, name, B_FILE_NAME_LENGTH);
280		rules->first = NULL;
281		sRulesHash->Insert(rules);
282	}
283
284	// search for matching rule type
285
286	Rule *rule = rules->first;
287	while (rule && rule->Type() != type) {
288		rule = rule->Next();
289	}
290
291	if (rule == NULL) {
292		TRACE(("create new rule for \"%s\", type %d\n", name, type));
293		// there is no rule yet, create one
294		rule = new Rule(type);
295		if (rule == NULL)
296			return NULL;
297
298		rule->Next() = rules->first;
299		rules->first = rule;
300	}
301
302	return rule;
303}
304
305
306static void
307eat_spaces(char *&line)
308{
309	// eat starting white space
310	while (isspace(line[0]))
311		line++;
312}
313
314
315static bool
316parse_ref(const char *string, mount_id &device, vnode_id &node, char **_end = NULL)
317{
318	// parse node ref
319	char *end;
320	device = strtol(string, &end, 0);
321	if (end == NULL || device == 0 || end[0] != ':')
322		return false;
323
324	node = strtoull(end + 1, &end, 0);
325	if (end == NULL || end[0] != ':')
326		return false;
327
328	if (_end)
329		*_end = end + 1;
330	return true;
331}
332
333
334static void
335ignore_line(char *&line)
336{
337	while (line[0] && line[0] != '\n')
338		line++;
339}
340
341
342static const char *
343get_name(char *&line)
344{
345	if (line[0] != '"')
346		return NULL;
347
348	const char *name = ++line;
349
350	while (line[0] && line[0] != '"') {
351		if (line[0] == '\\')
352			line++;
353		line++;
354	}
355
356	line[0] = '\0';
357	line++;
358
359	return name;
360}
361
362
363static status_t
364load_rules()
365{
366	int fd = open("/etc/cache_rules", O_RDONLY);
367	if (fd < B_OK)
368		return fd;
369
370	struct stat stat;
371	if (fstat(fd, &stat) != 0) {
372		close(fd);
373		return errno;
374	}
375
376	if (stat.st_size > 32767) {
377		// for safety reasons
378		// ToDo: make a bit larger later
379		close(fd);
380		return B_BAD_DATA;
381	}
382
383	char *buffer = (char *)malloc(stat.st_size + 1);
384	if (buffer == NULL) {
385		close(fd);
386		return B_NO_MEMORY;
387	}
388
389	if (read(fd, buffer, stat.st_size) < stat.st_size) {
390		free(buffer);
391		close(fd);
392		return B_ERROR;
393	}
394
395	buffer[stat.st_size] = '\0';
396
397	char *line = buffer;
398	while (line[0]) {
399		switch (line[0]) {
400			case 'c':
401			{
402				mount_id device;
403				vnode_id node;
404
405				// direct "command opens file" rule
406				line += 2;
407				if (parse_ref(line, device, node, &line)) {
408					const char *fileName = get_name(line);
409					if (fileName != NULL) {
410						eat_spaces(line);
411						const char *name = get_name(line);
412						if (name != NULL) {
413							eat_spaces(line);
414							int32 confidence = strtoul(line, &line, 10);
415							TRACE(("c %ld:%Ld:%s %s %ld\n", device, node, fileName, name, confidence));
416
417							struct head *head = new ::head;
418							head->device = device;
419							head->parent = node;
420							strlcpy(head->name, fileName, B_FILE_NAME_LENGTH);
421							head->confidence = confidence;
422
423							Rule *rule = get_rule(name, LAUNCH_TYPE);
424							if (rule != NULL)
425								rule->AddHead(head);
426							break;
427						}
428					}
429				}
430				ignore_line(line);
431				break;
432			}
433			default:
434				// unknown rule - ignore line
435				ignore_line(line);
436				break;
437		}
438		line++;
439	}
440
441	free(buffer);
442	close(fd);
443	return B_OK;
444}
445
446
447//	#pragma mark -
448
449
450Rule::Rule(rule_type type)
451	:
452	fType(type),
453	fHeadCount(0),
454	fBodyCount(0),
455	fAppliedCount(0),
456	fKnownFileOpened(0),
457	fUnknownFileOpened(0)
458{
459	list_init(&fHeads);
460	list_init(&fBodies);
461}
462
463
464Rule::~Rule()
465{
466	struct head *head;
467	while ((head = (struct head *)list_remove_head_item(&fHeads)) != NULL) {
468		delete head;
469	}
470
471	struct body *body;
472	while ((body = (struct body *)list_remove_head_item(&fBodies)) != NULL) {
473		delete body;
474	}
475}
476
477
478void
479Rule::AddHead(struct head *head)
480{
481	list_add_item(&fHeads, head);
482	fHeadCount++;
483}
484
485
486void
487Rule::AddBody(struct body *body)
488{
489	list_add_item(&fBodies, body);
490	fBodyCount++;
491}
492
493
494void
495Rule::Apply()
496{
497	TRACE(("Apply rule %p", this));
498
499	struct head *head = NULL;
500	while ((head = (struct head *)list_get_next_item(&fHeads, head)) != NULL) {
501		if (head->confidence < sMinConfidence)
502			continue;
503
504		// prefetch node
505		void *vnode;
506		if (vfs_entry_ref_to_vnode(head->device, head->parent, head->name, &vnode) == B_OK) {
507			vfs_vnode_to_node_ref(vnode, &head->device, &head->node);
508
509			TRACE(("prefetch: %ld:%Ld:%s\n", head->device, head->parent, head->name));
510			cache_prefetch(head->device, head->node, 0, ~0UL);
511
512			// ToDo: put head into a hash so that some statistics can be backpropagated quickly
513		} else {
514			// node doesn't exist anymore
515			head->confidence = -1;
516		}
517	}
518
519	fAppliedCount++;
520}
521
522
523struct head *
524Rule::FindHead(mount_id device, vnode_id node)
525{
526	// ToDo: use a hash for this!
527
528	struct head *head = NULL;
529	while ((head = (struct head *)list_get_next_item(&fHeads, head)) != NULL) {
530		if (head->node == node && head->device == device)
531			return head;
532	}
533
534	return NULL;
535}
536
537
538void
539Rule::Dump()
540{
541	dprintf("  applied: %ld, known: %ld, unknown: %ld\n",
542		fAppliedCount, fKnownFileOpened, fUnknownFileOpened);
543
544	struct head *head = NULL;
545	while ((head = (struct head *)list_get_next_item(&fHeads, head)) != NULL) {
546		dprintf("  %ld:%Ld:\"%s\", ", head->device, head->parent, head->name);
547		if (head->confidence < sMinConfidence)
548			dprintf("-\n");
549		else
550			dprintf("%ld (%ld), %Ld us\n", head->used_count,
551				head->used_count - fAppliedCount, head->timestamp);
552	}
553}
554
555
556//	#pragma mark -
557
558
559RuleMatcher::RuleMatcher(team_id team, const char *name)
560	:
561	fRules(NULL)
562{
563	recursive_lock_lock(&sLock);
564
565	if (name == NULL)
566		return;
567
568	fRules = sTeamHash->Lookup(team);
569	if (fRules != NULL)
570		return;
571
572	fRules = new team_rules;
573	if (fRules == NULL)
574		return;
575
576	fRules->team = team;
577	list_init(&fRules->states);
578	list_init(&fRules->applied);
579
580dprintf("new rules for \"%s\"\n", name);
581	_CollectRules(name);
582
583	sTeamHash->Insert(fRules);
584	start_watching_team(team, team_gone, fRules);
585
586	fRules->timestamp = system_time();
587}
588
589
590RuleMatcher::~RuleMatcher()
591{
592	recursive_lock_unlock(&sLock);
593}
594
595
596void
597RuleMatcher::_CollectRules(const char *name)
598{
599	struct rules *rules = sRulesHash->Lookup(name);
600	if (rules == NULL) {
601		// there are no rules for this command
602		return;
603	}
604
605	// allocate states for all rules found
606
607	for (Rule *rule = rules->first; rule != NULL; rule = rule->Next()) {
608		rule_state *state = new rule_state;
609		if (state == NULL)
610			continue;
611
612		TRACE(("found rule %p for \"%s\"\n", rule, rules->name));
613		state->rule = rule;
614		state->state = 0;
615
616		if (rule->Type() == LAUNCH_TYPE) {
617			// we can already prefetch the simplest of all rules here
618			// (it's fulfilled as soon as the command is launched)
619			rule->Apply();
620			list_add_item(&fRules->applied, state);
621		} else
622			list_add_item(&fRules->states, state);
623	}
624}
625
626
627void
628RuleMatcher::GotFile(mount_id device, vnode_id node)
629{
630	if (fRules == NULL)
631		return;
632
633	// try to match the file with all open rules
634
635	rule_state *state = NULL;
636	while ((state = (rule_state *)list_get_next_item(&fRules->states, state)) != NULL) {
637		if ((state->rule->Type() & OPEN_FILE_TYPE) == 0)
638			continue;
639
640		// ToDo
641	}
642
643	bigtime_t diff = system_time() - fRules->timestamp;
644
645	// propagate the usage of this file back to the applied rules
646
647	while ((state = (rule_state *)list_get_next_item(&fRules->applied, state)) != NULL) {
648		struct head *head = state->rule->FindHead(device, node);
649		if (head != NULL) {
650			// grow confidence
651			state->rule->KnownFileOpened();
652			head->used_count++;
653			if (head->used_count > 1)
654				head->timestamp = (head->timestamp * (head->used_count - 1) + diff) / head->used_count;
655		} else
656			state->rule->UnknownFileOpened();
657	}
658}
659
660
661void
662RuleMatcher::GotArguments(int32 argCount, char * const *args)
663{
664	if (fRules == NULL)
665		return;
666
667	// try to match the arguments with all open rules
668
669	rule_state *state = NULL;
670	while ((state = (rule_state *)list_get_next_item(&fRules->states, state)) != NULL) {
671		if ((state->rule->Type() & ARGUMENTS_TYPE) == 0)
672			continue;
673
674		// ToDo
675	}
676}
677
678
679//	#pragma mark -
680
681
682static void
683node_opened(struct vnode *vnode, int32 fdType, dev_t device, vnode_id parent,
684	vnode_id node, const char *name, off_t size)
685{
686	if (device < gBootDevice) {
687		// we ignore any access to rootfs, pipefs, and devfs
688		// ToDo: if we can ever move the boot device on the fly, this will break
689		return;
690	}
691
692	// ToDo: this is only needed if there is no rule for this team yet - ideally,
693	//	it would be handled by the log module, so that the vnode ID is sufficient
694	//	to recognize a rule
695	char buffer[B_FILE_NAME_LENGTH];
696	if (name == NULL
697		&& vfs_get_vnode_name(vnode, buffer, sizeof(buffer)) == B_OK)
698		name = buffer;
699
700	//dprintf("opened: %ld:%Ld:%Ld:%s (%s)\n", device, parent, node, name, thread_get_current_thread()->name);
701	RuleMatcher matcher(team_get_current_team_id(), name);
702	matcher.GotFile(device, node);
703}
704
705
706static void
707node_launched(size_t argCount, char * const *args)
708{
709	//dprintf("launched: %s (%s)\n", args[0], thread_get_current_thread()->name);
710	RuleMatcher matcher(team_get_current_team_id());
711	matcher.GotArguments(argCount, args);
712}
713
714
715static void
716uninit()
717{
718	recursive_lock_lock(&sLock);
719
720	// free all sessions from the hashes
721
722	team_rules *teamRules = sTeamHash->Clear(true);
723	while (teamRules != NULL) {
724		team_rules *next = teamRules->next;
725		delete teamRules;
726		teamRules = next;
727	}
728
729	struct rules *rules = sRulesHash->Clear(true);
730	while (rules != NULL) {
731		Rule *rule = rules->first;
732		while (rule) {
733			Rule *next = rule->Next();
734
735			dprintf("Rule %p \"%s\"\n", rule, rules->name);
736			rule->Dump();
737
738			delete rule;
739			rule = next;
740		}
741
742		struct rules *next = rules->next;
743		delete rules;
744		rules = next;
745	}
746
747	delete sTeamHash;
748	delete sRulesHash;
749	recursive_lock_destroy(&sLock);
750}
751
752
753static status_t
754init()
755{
756	sTeamHash = new(std::nothrow) TeamTable();
757	if (sTeamHash == NULL || sTeamHash->Init(64) != B_OK)
758		return B_NO_MEMORY;
759
760	status_t status;
761
762	sRulesHash = new(std::nothrow) RuleTable();
763	if (sRulesHash == NULL || sRulesHash->Init(64) != B_OK) {
764		delete sTeamHash;
765		return B_NO_MEMORY;
766	}
767
768	recursive_lock_init(&sLock, "rule based prefetcher");
769
770	load_rules();
771	return B_OK;
772}
773
774
775static status_t
776std_ops(int32 op, ...)
777{
778	switch (op) {
779		case B_MODULE_INIT:
780			return init();
781
782		case B_MODULE_UNINIT:
783			uninit();
784			return B_OK;
785
786		default:
787			return B_ERROR;
788	}
789}
790
791
792static struct cache_module_info sRuleBasedPrefetcherModule = {
793	{
794		CACHE_MODULES_NAME "/rule_based_prefetcher/v1",
795		0,
796		std_ops,
797	},
798	node_opened,
799	NULL,
800	node_launched,
801};
802
803
804module_info *modules[] = {
805	(module_info *)&sRuleBasedPrefetcherModule,
806	NULL
807};
808