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 }