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 QLock;
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
extentfree(Extent * e)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*
extentalloc(void)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
cinit(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 > 400*MB)
117 maxcache = 20*MAXCACHE;
118 else if(conf.npage*BY2PG > 200*MB)
119 maxcache = 10*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
cprint(Chan * c,Mntcache * m,char * s)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*
cpage(Extent * e)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
cnodata(Mntcache * m)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
ctail(Mntcache * m)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
copen(Chan * c)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 qlock(&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 qunlock(&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 qunlock(&cache);
271
272 while(e) {
273 next = e->next;
274 extentfree(e);
275 e = next;
276 }
277 qunlock(m);
278 }
279
280 static int
cdev(Mntcache * m,Chan * c)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
cread(Chan * c,uchar * buf,int len,vlong off)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*
cchain(uchar * buf,ulong offset,int len,Extent ** tail)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 qlock(&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 qunlock(&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
cpgmove(Extent * e,uchar * buf,int boff,int len)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
cupdate(Chan * c,uchar * buf,int len,vlong off)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
cwrite(Chan * c,uchar * buf,int len,vlong off)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