1 #include "stdinc.h"
2 #include "dat.h"
3 #include "fns.h"
4 
5 typedef struct DCache	DCache;
6 
7 enum
8 {
9 	HashLog		= 9,
10 	HashSize	= 1<<HashLog,
11 	HashMask	= HashSize - 1,
12 };
13 
14 struct DCache
15 {
16 	QLock		lock;
17 	Rendez		full;
18 	DBlock		*free;			/* list of available lumps */
19 	u32int		now;			/* ticks for usage timestamps */
20 	int		size;			/* max. size of any block; allocated to each block */
21 	DBlock		**heads;		/* hash table for finding address */
22 	int		nheap;			/* number of available victims */
23 	DBlock		**heap;			/* heap for locating victims */
24 	int		nblocks;		/* number of blocks allocated */
25 	DBlock		*blocks;		/* array of block descriptors */
26 	u8int		*mem;			/* memory for all block descriptors */
27 };
28 
29 static DCache	dcache;
30 
31 static int	downheap(int i, DBlock *b);
32 static int	upheap(int i, DBlock *b);
33 static DBlock	*bumpdblock(void);
34 static void	delheap(DBlock *db);
35 static void	fixheap(int i, DBlock *b);
36 
37 void
38 initdcache(u32int mem)
39 {
40 	DBlock *b, *last;
41 	u32int nblocks, blocksize;
42 	int i;
43 
44 	if(mem < maxblocksize * 2)
45 		sysfatal("need at least %d bytes for the disk cache", maxblocksize * 2);
46 	if(maxblocksize == 0)
47 		sysfatal("no max. block size given for disk cache");
48 	blocksize = maxblocksize;
49 	nblocks = mem / blocksize;
50 	if(0)
51 		fprint(2, "initialize disk cache with %d blocks of %d bytes\n", nblocks, blocksize);
52 	dcache.full.l = &dcache.lock;
53 	dcache.nblocks = nblocks;
54 	dcache.size = blocksize;
55 	dcache.heads = MKNZ(DBlock*, HashSize);
56 	dcache.heap = MKNZ(DBlock*, nblocks);
57 	dcache.blocks = MKNZ(DBlock, nblocks);
58 	dcache.mem = MKNZ(u8int, nblocks * blocksize);
59 
60 	last = nil;
61 	for(i = 0; i < nblocks; i++){
62 		b = &dcache.blocks[i];
63 		b->data = &dcache.mem[i * blocksize];
64 		b->heap = TWID32;
65 		b->next = last;
66 		last = b;
67 	}
68 	dcache.free = last;
69 	dcache.nheap = 0;
70 }
71 
72 static u32int
73 pbhash(u64int addr)
74 {
75 	u32int h;
76 
77 #define hashit(c)	((((c) * 0x6b43a9b5) >> (32 - HashLog)) & HashMask)
78 	h = (addr >> 32) ^ addr;
79 	return hashit(h);
80 }
81 
82 DBlock*
83 getdblock(Part *part, u64int addr, int read)
84 {
85 	DBlock *b;
86 	u32int h, size;
87 
88 	size = part->blocksize;
89 	if(size > dcache.size){
90 		seterr(EAdmin, "block size %d too big for cache", size);
91 		return nil;
92 	}
93 	h = pbhash(addr);
94 
95 	/*
96 	 * look for the block in the cache
97 	 */
98 //checkdcache();
99 	qlock(&dcache.lock);
100 again:
101 	for(b = dcache.heads[h]; b != nil; b = b->next){
102 		if(b->part == part && b->addr == addr){
103 			qlock(&stats.lock);
104 			stats.pchit++;
105 			qunlock(&stats.lock);
106 			goto found;
107 		}
108 	}
109 	qlock(&stats.lock);
110 	stats.pcmiss++;
111 	qunlock(&stats.lock);
112 
113 	/*
114 	 * missed: locate the block with the oldest second to last use.
115 	 * remove it from the heap, and fix up the heap.
116 	 */
117 	b = bumpdblock();
118 	if(b == nil){
119 		logerr(EAdmin, "all disk cache blocks in use");
120 		rsleep(&dcache.full);
121 		goto again;
122 	}
123 
124 	/*
125 	 * the new block has no last use, so assume it happens sometime in the middle
126 ZZZ this is not reasonable
127 	 */
128 	b->used = (b->used2 + dcache.now) / 2;
129 
130 	/*
131 	 * rechain the block on the correct hash chain
132 	 */
133 	b->next = dcache.heads[h];
134 	dcache.heads[h] = b;
135 	if(b->next != nil)
136 		b->next->prev = b;
137 	b->prev = nil;
138 
139 	b->addr = addr;
140 	b->part = part;
141 	b->size = 0;
142 
143 found:
144 	b->ref++;
145 	b->used2 = b->used;
146 	b->used = dcache.now++;
147 	if(b->heap != TWID32)
148 		fixheap(b->heap, b);
149 
150 	qunlock(&dcache.lock);
151 //checkdcache();
152 
153 	qlock(&b->lock);
154 	if(b->size != size){
155 		if(b->size < size){
156 			if(!read)
157 				memset(&b->data[b->size], 0, size - b->size);
158 			else{
159 				if(readpart(part, addr + b->size, &b->data[b->size], size - b->size) < 0){
160 					putdblock(b);
161 					return nil;
162 				}
163 				qlock(&stats.lock);
164 				stats.pcreads++;
165 				stats.pcbreads += size - b->size;
166 				qunlock(&stats.lock);
167 			}
168 		}
169 		b->size = size;
170 	}
171 
172 	return b;
173 }
174 
175 void
176 putdblock(DBlock *b)
177 {
178 	if(b == nil)
179 		return;
180 
181 	qunlock(&b->lock);
182 //checkdcache();
183 	qlock(&dcache.lock);
184 	if(--b->ref == 0){
185 		if(b->heap == TWID32)
186 			upheap(dcache.nheap++, b);
187 		rwakeup(&dcache.full);
188 	}
189 
190 	qunlock(&dcache.lock);
191 //checkdcache();
192 }
193 
194 /*
195  * remove some block from use and update the free list and counters
196  */
197 static DBlock*
198 bumpdblock(void)
199 {
200 	DBlock *b;
201 	ulong h;
202 
203 	b = dcache.free;
204 	if(b != nil){
205 		dcache.free = b->next;
206 		return b;
207 	}
208 
209 	/*
210 	 * remove blocks until we find one that is unused
211 	 * referenced blocks are left in the heap even though
212 	 * they can't be scavenged; this is simple a speed optimization
213 	 */
214 	for(;;){
215 		if(dcache.nheap == 0)
216 			return nil;
217 		b = dcache.heap[0];
218 		delheap(b);
219 		if(!b->ref)
220 			break;
221 	}
222 
223 	/*
224 	 * unchain the block
225 	 */
226 	if(b->prev == nil){
227 		h = pbhash(b->addr);
228 		if(dcache.heads[h] != b)
229 			sysfatal("bad hash chains in disk cache");
230 		dcache.heads[h] = b->next;
231 	}else
232 		b->prev->next = b->next;
233 	if(b->next != nil)
234 		b->next->prev = b->prev;
235 
236 	return b;
237 }
238 
239 /*
240  * delete an arbitrary block from the heap
241  */
242 static void
243 delheap(DBlock *db)
244 {
245 	fixheap(db->heap, dcache.heap[--dcache.nheap]);
246 	db->heap = TWID32;
247 }
248 
249 /*
250  * push an element up or down to it's correct new location
251  */
252 static void
253 fixheap(int i, DBlock *b)
254 {
255 	if(upheap(i, b) == i)
256 		downheap(i, b);
257 }
258 
259 static int
260 upheap(int i, DBlock *b)
261 {
262 	DBlock *bb;
263 	u32int now;
264 	int p;
265 
266 	now = dcache.now;
267 	for(; i != 0; i = p){
268 		p = (i - 1) >> 1;
269 		bb = dcache.heap[p];
270 		if(b->used2 - now >= bb->used2 - now)
271 			break;
272 		dcache.heap[i] = bb;
273 		bb->heap = i;
274 	}
275 
276 	dcache.heap[i] = b;
277 	b->heap = i;
278 	return i;
279 }
280 
281 static int
282 downheap(int i, DBlock *b)
283 {
284 	DBlock *bb;
285 	u32int now;
286 	int k;
287 
288 	now = dcache.now;
289 	for(; ; i = k){
290 		k = (i << 1) + 1;
291 		if(k >= dcache.nheap)
292 			break;
293 		if(k + 1 < dcache.nheap && dcache.heap[k]->used2 - now > dcache.heap[k + 1]->used2 - now)
294 			k++;
295 		bb = dcache.heap[k];
296 		if(b->used2 - now <= bb->used2 - now)
297 			break;
298 		dcache.heap[i] = bb;
299 		bb->heap = i;
300 	}
301 
302 	dcache.heap[i] = b;
303 	b->heap = i;
304 	return i;
305 }
306 
307 static void
308 findblock(DBlock *bb)
309 {
310 	DBlock *b, *last;
311 	int h;
312 
313 	last = nil;
314 	h = pbhash(bb->addr);
315 	for(b = dcache.heads[h]; b != nil; b = b->next){
316 		if(last != b->prev)
317 			sysfatal("bad prev link");
318 		if(b == bb)
319 			return;
320 		last = b;
321 	}
322 	sysfatal("block missing from hash table");
323 }
324 
325 void
326 checkdcache(void)
327 {
328 	DBlock *b;
329 	u32int size, now;
330 	int i, k, refed, nfree;
331 
332 	qlock(&dcache.lock);
333 	size = dcache.size;
334 	now = dcache.now;
335 	for(i = 0; i < dcache.nheap; i++){
336 		if(dcache.heap[i]->heap != i)
337 			sysfatal("dc: mis-heaped at %d: %d", i, dcache.heap[i]->heap);
338 		if(i > 0 && dcache.heap[(i - 1) >> 1]->used2 - now > dcache.heap[i]->used2 - now)
339 			sysfatal("dc: bad heap ordering");
340 		k = (i << 1) + 1;
341 		if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
342 			sysfatal("dc: bad heap ordering");
343 		k++;
344 		if(k < dcache.nheap && dcache.heap[i]->used2 - now > dcache.heap[k]->used2 - now)
345 			sysfatal("dc: bad heap ordering");
346 	}
347 
348 	refed = 0;
349 	for(i = 0; i < dcache.nblocks; i++){
350 		b = &dcache.blocks[i];
351 		if(b->data != &dcache.mem[i * size])
352 			sysfatal("dc: mis-blocked at %d", i);
353 		if(b->ref && b->heap == TWID32)
354 			refed++;
355 		if(b->addr)
356 			findblock(b);
357 		if(b->heap != TWID32
358 		&& dcache.heap[b->heap] != b)
359 			sysfatal("dc: spurious heap value");
360 	}
361 
362 	nfree = 0;
363 	for(b = dcache.free; b != nil; b = b->next){
364 		if(b->addr != 0 || b->heap != TWID32)
365 			sysfatal("dc: bad free list");
366 		nfree++;
367 	}
368 
369 	if(dcache.nheap + nfree + refed != dcache.nblocks)
370 		sysfatal("dc: missing blocks: %d %d %d", dcache.nheap, refed, dcache.nblocks);
371 	qunlock(&dcache.lock);
372 }