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