cache.c 9.1 KB

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