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