1 #include "u.h" 2 #include "../port/lib.h" 3 #include "mem.h" 4 #include "dat.h" 5 #include "fns.h" 6 #include "../port/error.h" 7 8 enum 9 { 10 NHASH = 128, 11 MAXCACHE = 1024*1024, 12 NFILE = 4096, 13 NEXTENT = 200, /* extent allocation size */ 14 }; 15 16 typedef struct Extent Extent; 17 struct Extent 18 { 19 int bid; 20 ulong start; 21 int len; 22 Page *cache; 23 Extent *next; 24 }; 25 26 typedef struct Mntcache Mntcache; 27 struct Mntcache 28 { 29 Qid qid; 30 int dev; 31 int type; 32 QLock; 33 Extent *list; 34 Mntcache *hash; 35 Mntcache *prev; 36 Mntcache *next; 37 }; 38 39 typedef struct Cache Cache; 40 struct Cache 41 { 42 Lock; 43 int pgno; 44 Mntcache *head; 45 Mntcache *tail; 46 Mntcache *hash[NHASH]; 47 }; 48 49 typedef struct Ecache Ecache; 50 struct Ecache 51 { 52 Lock; 53 int total; 54 int free; 55 Extent* head; 56 }; 57 58 static Image fscache; 59 static Cache cache; 60 static Ecache ecache; 61 static int maxcache = MAXCACHE; 62 63 static void 64 extentfree(Extent* e) 65 { 66 lock(&ecache); 67 e->next = ecache.head; 68 ecache.head = e; 69 ecache.free++; 70 unlock(&ecache); 71 } 72 73 static Extent* 74 extentalloc(void) 75 { 76 Extent *e; 77 int i; 78 79 lock(&ecache); 80 if(ecache.head == nil){ 81 e = xalloc(NEXTENT*sizeof(Extent)); 82 if(e == nil){ 83 unlock(&ecache); 84 return nil; 85 } 86 for(i = 0; i < NEXTENT; i++){ 87 e->next = ecache.head; 88 ecache.head = e; 89 e++; 90 } 91 ecache.free += NEXTENT; 92 ecache.total += NEXTENT; 93 } 94 95 e = ecache.head; 96 ecache.head = e->next; 97 memset(e, 0, sizeof(Extent)); 98 ecache.free--; 99 unlock(&ecache); 100 101 return e; 102 } 103 104 void 105 cinit(void) 106 { 107 int i; 108 Mntcache *m; 109 110 cache.head = xalloc(sizeof(Mntcache)*NFILE); 111 m = cache.head; 112 if (m == nil) 113 panic("cinit: no memory"); 114 115 /* a better algorithm would be nice */ 116 // if(conf.npage*BY2PG > 200*MB) 117 // maxcache = 10*MAXCACHE; 118 // if(conf.npage*BY2PG > 400*MB) 119 // maxcache = 50*MAXCACHE; 120 121 for(i = 0; i < NFILE-1; i++) { 122 m->next = m+1; 123 m->prev = m-1; 124 m++; 125 } 126 127 cache.tail = m; 128 cache.tail->next = 0; 129 cache.head->prev = 0; 130 131 fscache.notext = 1; 132 } 133 134 void 135 cprint(Chan *c, Mntcache *m, char *s) 136 { 137 ulong o; 138 int nb, ct; 139 Extent *e; 140 141 nb = 0; 142 ct = 1; 143 o = 0; 144 if(m->list) 145 o = m->list->start; 146 for(e = m->list; e; e = e->next) { 147 nb += e->len; 148 if(o != e->start) 149 ct = 0; 150 o = e->start+e->len; 151 } 152 pprint("%s: %#llux.%#lux %d %d %s (%d %c)\n", 153 s, m->qid.path, m->qid.vers, m->type, m->dev, c->path->s, nb, ct ? 'C' : 'N'); 154 155 for(e = m->list; e; e = e->next) { 156 pprint("\t%4d %5lud %4d %#p\n", 157 e->bid, e->start, e->len, e->cache); 158 } 159 } 160 161 Page* 162 cpage(Extent *e) 163 { 164 /* Easy consistency check */ 165 if(e->cache->daddr != e->bid) 166 return 0; 167 168 return lookpage(&fscache, e->bid); 169 } 170 171 void 172 cnodata(Mntcache *m) 173 { 174 Extent *e, *n; 175 176 /* 177 * Invalidate all extent data 178 * Image lru will waste the pages 179 */ 180 for(e = m->list; e; e = n) { 181 n = e->next; 182 extentfree(e); 183 } 184 m->list = 0; 185 } 186 187 void 188 ctail(Mntcache *m) 189 { 190 /* Unlink and send to the tail */ 191 if(m->prev) 192 m->prev->next = m->next; 193 else 194 cache.head = m->next; 195 if(m->next) 196 m->next->prev = m->prev; 197 else 198 cache.tail = m->prev; 199 200 if(cache.tail) { 201 m->prev = cache.tail; 202 cache.tail->next = m; 203 m->next = 0; 204 cache.tail = m; 205 } 206 else { 207 cache.head = m; 208 cache.tail = m; 209 m->prev = 0; 210 m->next = 0; 211 } 212 } 213 214 void 215 copen(Chan *c) 216 { 217 int h; 218 Extent *e, *next; 219 Mntcache *m, *f, **l; 220 221 /* directories aren't cacheable and append-only files confuse us */ 222 if(c->qid.type&(QTDIR|QTAPPEND)) 223 return; 224 225 h = c->qid.path%NHASH; 226 lock(&cache); 227 for(m = cache.hash[h]; m; m = m->hash) { 228 if(m->qid.path == c->qid.path) 229 if(m->qid.type == c->qid.type) 230 if(m->dev == c->dev && m->type == c->type) { 231 c->mcp = m; 232 ctail(m); 233 unlock(&cache); 234 235 /* File was updated, invalidate cache */ 236 if(m->qid.vers != c->qid.vers) { 237 m->qid.vers = c->qid.vers; 238 qlock(m); 239 cnodata(m); 240 qunlock(m); 241 } 242 return; 243 } 244 } 245 246 /* LRU the cache headers */ 247 m = cache.head; 248 l = &cache.hash[m->qid.path%NHASH]; 249 for(f = *l; f; f = f->hash) { 250 if(f == m) { 251 *l = m->hash; 252 break; 253 } 254 l = &f->hash; 255 } 256 257 m->qid = c->qid; 258 m->dev = c->dev; 259 m->type = c->type; 260 261 l = &cache.hash[h]; 262 m->hash = *l; 263 *l = m; 264 ctail(m); 265 266 qlock(m); 267 c->mcp = m; 268 e = m->list; 269 m->list = 0; 270 unlock(&cache); 271 272 while(e) { 273 next = e->next; 274 extentfree(e); 275 e = next; 276 } 277 qunlock(m); 278 } 279 280 static int 281 cdev(Mntcache *m, Chan *c) 282 { 283 if(m->qid.path != c->qid.path) 284 return 0; 285 if(m->qid.type != c->qid.type) 286 return 0; 287 if(m->dev != c->dev) 288 return 0; 289 if(m->type != c->type) 290 return 0; 291 if(m->qid.vers != c->qid.vers) 292 return 0; 293 return 1; 294 } 295 296 int 297 cread(Chan *c, uchar *buf, int len, vlong off) 298 { 299 KMap *k; 300 Page *p; 301 Mntcache *m; 302 Extent *e, **t; 303 int o, l, total; 304 ulong offset; 305 306 if(off+len > maxcache) 307 return 0; 308 309 m = c->mcp; 310 if(m == 0) 311 return 0; 312 313 qlock(m); 314 if(cdev(m, c) == 0) { 315 qunlock(m); 316 return 0; 317 } 318 319 offset = off; 320 t = &m->list; 321 for(e = *t; e; e = e->next) { 322 if(offset >= e->start && offset < e->start+e->len) 323 break; 324 t = &e->next; 325 } 326 327 if(e == 0) { 328 qunlock(m); 329 return 0; 330 } 331 332 total = 0; 333 while(len) { 334 p = cpage(e); 335 if(p == 0) { 336 *t = e->next; 337 extentfree(e); 338 qunlock(m); 339 return total; 340 } 341 342 o = offset - e->start; 343 l = len; 344 if(l > e->len-o) 345 l = e->len-o; 346 347 k = kmap(p); 348 if(waserror()) { 349 kunmap(k); 350 putpage(p); 351 qunlock(m); 352 nexterror(); 353 } 354 355 memmove(buf, (uchar*)VA(k) + o, l); 356 357 poperror(); 358 kunmap(k); 359 360 putpage(p); 361 362 buf += l; 363 len -= l; 364 offset += l; 365 total += l; 366 t = &e->next; 367 e = e->next; 368 if(e == 0 || e->start != offset) 369 break; 370 } 371 372 qunlock(m); 373 return total; 374 } 375 376 Extent* 377 cchain(uchar *buf, ulong offset, int len, Extent **tail) 378 { 379 int l; 380 Page *p; 381 KMap *k; 382 Extent *e, *start, **t; 383 384 start = 0; 385 *tail = 0; 386 t = &start; 387 while(len) { 388 e = extentalloc(); 389 if(e == 0) 390 break; 391 392 p = auxpage(); 393 if(p == 0) { 394 extentfree(e); 395 break; 396 } 397 l = len; 398 if(l > BY2PG) 399 l = BY2PG; 400 401 e->cache = p; 402 e->start = offset; 403 e->len = l; 404 405 lock(&cache); 406 e->bid = cache.pgno; 407 cache.pgno += BY2PG; 408 /* wrap the counter; low bits are unused by pghash but checked by lookpage */ 409 if((cache.pgno & ~(BY2PG-1)) == 0){ 410 if(cache.pgno == BY2PG-1){ 411 print("cache wrapped\n"); 412 cache.pgno = 0; 413 }else 414 cache.pgno++; 415 } 416 unlock(&cache); 417 418 p->daddr = e->bid; 419 k = kmap(p); 420 if(waserror()) { /* buf may be virtual */ 421 kunmap(k); 422 nexterror(); 423 } 424 memmove((void*)VA(k), buf, l); 425 poperror(); 426 kunmap(k); 427 428 cachepage(p, &fscache); 429 putpage(p); 430 431 buf += l; 432 offset += l; 433 len -= l; 434 435 *t = e; 436 *tail = e; 437 t = &e->next; 438 } 439 440 return start; 441 } 442 443 int 444 cpgmove(Extent *e, uchar *buf, int boff, int len) 445 { 446 Page *p; 447 KMap *k; 448 449 p = cpage(e); 450 if(p == 0) 451 return 0; 452 453 k = kmap(p); 454 if(waserror()) { /* Since buf may be virtual */ 455 kunmap(k); 456 nexterror(); 457 } 458 459 memmove((uchar*)VA(k)+boff, buf, len); 460 461 poperror(); 462 kunmap(k); 463 putpage(p); 464 465 return 1; 466 } 467 468 void 469 cupdate(Chan *c, uchar *buf, int len, vlong off) 470 { 471 Mntcache *m; 472 Extent *tail; 473 Extent *e, *f, *p; 474 int o, ee, eblock; 475 ulong offset; 476 477 if(off > maxcache || len == 0) 478 return; 479 480 m = c->mcp; 481 if(m == 0) 482 return; 483 qlock(m); 484 if(cdev(m, c) == 0) { 485 qunlock(m); 486 return; 487 } 488 489 /* 490 * Find the insertion point 491 */ 492 offset = off; 493 p = 0; 494 for(f = m->list; f; f = f->next) { 495 if(f->start > offset) 496 break; 497 p = f; 498 } 499 500 /* trim if there is a successor */ 501 eblock = offset+len; 502 if(f != 0 && eblock > f->start) { 503 len -= (eblock - f->start); 504 if(len <= 0) { 505 qunlock(m); 506 return; 507 } 508 } 509 510 if(p == 0) { /* at the head */ 511 e = cchain(buf, offset, len, &tail); 512 if(e != 0) { 513 m->list = e; 514 tail->next = f; 515 } 516 qunlock(m); 517 return; 518 } 519 520 /* trim to the predecessor */ 521 ee = p->start+p->len; 522 if(offset < ee) { 523 o = ee - offset; 524 len -= o; 525 if(len <= 0) { 526 qunlock(m); 527 return; 528 } 529 buf += o; 530 offset += o; 531 } 532 533 /* try and pack data into the predecessor */ 534 if(offset == ee && p->len < BY2PG) { 535 o = len; 536 if(o > BY2PG - p->len) 537 o = BY2PG - p->len; 538 if(cpgmove(p, buf, p->len, o)) { 539 p->len += o; 540 buf += o; 541 len -= o; 542 offset += o; 543 if(len <= 0) { 544 if(f && p->start + p->len > f->start) print("CACHE: p->start=%uld p->len=%d f->start=%uld\n", p->start, p->len, f->start); 545 qunlock(m); 546 return; 547 } 548 } 549 } 550 551 e = cchain(buf, offset, len, &tail); 552 if(e != 0) { 553 p->next = e; 554 tail->next = f; 555 } 556 qunlock(m); 557 } 558 559 void 560 cwrite(Chan* c, uchar *buf, int len, vlong off) 561 { 562 int o, eo; 563 Mntcache *m; 564 ulong eblock, ee; 565 Extent *p, *f, *e, *tail; 566 ulong offset; 567 568 if(off > maxcache || len == 0) 569 return; 570 571 m = c->mcp; 572 if(m == 0) 573 return; 574 575 qlock(m); 576 if(cdev(m, c) == 0) { 577 qunlock(m); 578 return; 579 } 580 581 offset = off; 582 m->qid.vers++; 583 c->qid.vers++; 584 585 p = 0; 586 for(f = m->list; f; f = f->next) { 587 if(f->start >= offset) 588 break; 589 p = f; 590 } 591 592 if(p != 0) { 593 ee = p->start+p->len; 594 eo = offset - p->start; 595 /* pack in predecessor if there is space */ 596 if(offset <= ee && eo < BY2PG) { 597 o = len; 598 if(o > BY2PG - eo) 599 o = BY2PG - eo; 600 if(cpgmove(p, buf, eo, o)) { 601 if(eo+o > p->len) 602 p->len = eo+o; 603 buf += o; 604 len -= o; 605 offset += o; 606 } 607 } 608 } 609 610 /* free the overlap -- it's a rare case */ 611 eblock = offset+len; 612 while(f && f->start < eblock) { 613 e = f->next; 614 extentfree(f); 615 f = e; 616 } 617 618 /* link the block (if any) into the middle */ 619 e = cchain(buf, offset, len, &tail); 620 if(e != 0) { 621 tail->next = f; 622 f = e; 623 } 624 625 if(p == 0) 626 m->list = f; 627 else 628 p->next = f; 629 qunlock(m); 630 } 631