tcache.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tcache.c (5487B)
---
1 #include <u.h>
2 #include <libc.h>
3 #include <diskfs.h>
4
5 /*
6 * Disk cache. Caches by offset, so higher levels have
7 * to deal with alignment issues (if we get asked for the
8 * blocks at offsets 0 and 1, we'll do two reads).
9 */
10
11 typedef struct DiskCache DiskCache;
12 typedef struct DiskCacheBlock DiskCacheBlock;
13
14 struct DiskCache
15 {
16 Disk disk;
17 Disk *subdisk;
18 DiskCacheBlock **h;
19 DiskCacheBlock *lruhead;
20 DiskCacheBlock *lrutail;
21 int nhash;
22 int blocksize;
23 Lock lk;
24 };
25
26 struct DiskCacheBlock
27 {
28 Block block;
29 Block *subblock;
30 Lock lk;
31 int ref;
32 DiskCache *dc;
33 DiskCacheBlock *next;
34 DiskCacheBlock *lrunext;
35 DiskCacheBlock *lruprev;
36 u64int offset;
37 };
38
39 static void
40 addtohash(DiskCache *d, DiskCacheBlock *b, u64int offset)
41 {
42 int h;
43
44 if(b->offset != ~(u64int)0){
45 fprint(2, "bad offset in addtohash\n");
46 return;
47 }
48 b->offset = offset;
49 h = offset % d->nhash;
50 b->next = d->h[h];
51 d->h[h] = b;
52 }
53
54 static void
55 delfromhash(DiskCache *d, DiskCacheBlock *b)
56 {
57 int h;
58 DiskCacheBlock **l;
59
60 if(b->offset == ~(u64int)0)
61 return;
62
63 h = b->offset % d->nhash;
64 for(l=&d->h[h]; *l; l=&(*l)->next)
65 if(*l == b){
66 *l = b->next;
67 b->offset = ~(u64int)0;
68 return;
69 }
70 fprint(2, "delfromhash: didn't find in hash table\n");
71 return;
72 }
73
74 static void
75 putmru(DiskCache *d, DiskCacheBlock *b)
76 {
77 b->lruprev = nil;
78 b->lrunext = d->lruhead;
79 d->lruhead = b;
80 if(b->lrunext == nil)
81 d->lrutail = b;
82 else
83 b->lrunext->lruprev = b;
84 }
85
86 static void
87 putlru(DiskCache *d, DiskCacheBlock *b)
88 {
89 b->lruprev = d->lrutail;
90 b->lrunext = nil;
91 d->lrutail = b;
92 if(b->lruprev == nil)
93 d->lruhead = b;
94 else
95 b->lruprev->lrunext = b;
96 }
97
98 static void
99 delfromlru(DiskCache *d, DiskCacheBlock *b)
100 {
101 if(b->lruprev)
102 b->lruprev->lrunext = b->lrunext;
103 else
104 d->lruhead = b->lrunext;
105 if(b->lrunext)
106 b->lrunext->lruprev = b->lruprev;
107 else
108 d->lrutail = b->lruprev;
109 }
110
111 static DiskCacheBlock*
112 getlru(DiskCache *d)
113 {
114 DiskCacheBlock *b;
115
116 b = d->lrutail;
117 if(b){
118 delfromlru(d, b);
119 delfromhash(d, b);
120 blockput(b->subblock);
121 b->subblock = nil;
122 }
123 return b;
124 }
125
126 static DiskCacheBlock*
127 findblock(DiskCache *d, u64int offset)
128 {
129 int h;
130 DiskCacheBlock *b;
131
132 h = offset % d->nhash;
133 for(b=d->h[h]; b; b=b->next)
134 if(b->offset == offset)
135 return b;
136 return nil;
137 }
138
139 static DiskCacheBlock*
140 diskcachereadbig(DiskCache *d, u64int offset)
141 {
142 Block *b;
143 DiskCacheBlock *dcb;
144
145 lock(&d->lk);
146 dcb = findblock(d, offset);
147 if(dcb){
148 /*fprint(2, "found %llud in cache %p\n", (uvlong)offset, dcb);*/
149 if(dcb->ref++ == 0)
150 delfromlru(d, dcb);
151 unlock(&d->lk);
152 return dcb;
153 }
154
155 dcb = getlru(d);
156 unlock(&d->lk);
157 if(dcb == nil){
158 fprint(2, "diskcacheread: all blocks in use\n");
159 return nil;
160 }
161
162 b = diskread(d->subdisk, d->blocksize, offset);
163 lock(&d->lk);
164 if(b == nil){
165 putlru(d, dcb);
166 dcb = nil;
167 }else{
168 /*fprint(2, "read %llud from disk %p\n", (uvlong)offset, dcb); */
169 dcb->subblock = b;
170 dcb->ref++;
171 addtohash(d, dcb, offset);
172 }
173 unlock(&d->lk);
174 return dcb;
175 }
176
177 static void
178 diskcacheblockclose(Block *bb)
179 {
180 DiskCacheBlock *b = bb->priv;
181
182 lock(&b->dc->lk);
183 if(--b->ref == 0)
184 putmru(b->dc, b);
185 unlock(&b->dc->lk);
186 free(bb);
187 }
188
189 static Block*
190 diskcacheread(Disk *dd, u32int len, u64int offset)
191 {
192 int frag, dlen;
193 DiskCache *d = (DiskCache*)dd;
194 DiskCacheBlock *dcb;
195 Block *b;
196
197 if(offset/d->blocksize != (offset+len-1)/d->blocksize){
198 fprint(2, "diskBigRead: request for block crossing big block boundary\n");
199 return nil;
200 }
201
202 b = mallocz(sizeof(Block), 1);
203 if(b == nil)
204 return nil;
205
206 frag = offset%d->blocksize;
207
208 dcb = diskcachereadbig(d, offset-frag);
209 if(dcb == nil){
210 free(b);
211 return nil;
212 }
213 b->priv = dcb;
214 b->_close = diskcacheblockclose;
215 b->data = dcb->subblock->data+frag;
216
217 dlen = dcb->subblock->len;
218 if(frag+len >= dlen){
219 if(frag >= dlen){
220 blockput(b);
221 return nil;
222 }
223 len = dlen-frag;
224 }
225 b->len = len;
226 /*fprint(2, "offset %llud at pointer %p %lux\n", (uvlong)offset, b->data, *(ulong*)(b->data+4)); */
227 return b;
228 }
229
230 /*
231 * It's okay to remove these from the hash table.
232 * Either the block is in use by someone or it is on
233 * the lru list. If it's in use it will get put on the lru
234 * list once the refs go away.
235 */
236 static int
237 diskcachesync(Disk *dd)
238 {
239 DiskCache *d = (DiskCache*)dd;
240 DiskCacheBlock *b, *nextb;
241 int i;
242
243 lock(&d->lk);
244 for(i=0; i<d->nhash; i++){
245 for(b=d->h[i]; b; b=nextb){
246 nextb = b->next;
247 b->next = nil;
248 b->offset = ~(u64int)0;
249 }
250 d->h[i] = nil;
251 }
252 unlock(&d->lk);
253 return disksync(d->subdisk);
254 }
255
256 static void
257 diskcacheclose(Disk *dd)
258 {
259 DiskCacheBlock *b;
260 DiskCache *d = (DiskCache*)dd;
261
262 diskclose(d->subdisk);
263 for(b=d->lruhead; b; b=b->lrunext)
264 blockput(b->subblock);
265 free(d);
266 }
267
268 /* needn't be fast */
269 static int
270 isprime(int n)
271 {
272 int i;
273
274 for(i=2; i*i<=n; i++)
275 if(n%i == 0)
276 return 0;
277 return 1;
278 }
279
280 Disk*
281 diskcache(Disk *subdisk, uint blocksize, uint ncache)
282 {
283 int nhash, i;
284 DiskCache *d;
285 DiskCacheBlock *b;
286
287 nhash = ncache;
288 while(nhash > 1 && !isprime(nhash))
289 nhash--;
290 d = mallocz(sizeof(DiskCache)+ncache*sizeof(DiskCacheBlock)+nhash*sizeof(DiskCacheBlock*), 1);
291 if(d == nil)
292 return nil;
293
294 b = (DiskCacheBlock*)&d[1];
295 d->h = (DiskCacheBlock**)&b[ncache];
296 d->nhash = nhash;
297 d->blocksize = blocksize;
298 d->subdisk = subdisk;
299 d->disk._read = diskcacheread;
300 d->disk._sync = diskcachesync;
301 d->disk._close = diskcacheclose;
302
303 for(i=0; i<ncache; i++){
304 b[i].block._close = diskcacheblockclose;
305 b[i].offset = ~(u64int)0;
306 b[i].dc = d;
307 putlru(d, &b[i]);
308 }
309
310 return &d->disk;
311 }