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