Rev 3 | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
2 | pj | 1 | /* |
2 | * Project: HARTIK (HA-rd R-eal TI-me K-ernel) |
||
3 | * |
||
4 | * Coordinators: Giorgio Buttazzo <giorgio@sssup.it> |
||
5 | * Gerardo Lamastra <gerardo@sssup.it> |
||
6 | * |
||
7 | * Authors : Massimiliano Giorgi <massy@hartik.sssup.it> |
||
8 | * (see authors.txt for full list of hartik's authors) |
||
9 | * |
||
10 | * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy) |
||
11 | * |
||
12 | * http://www.sssup.it |
||
13 | * http://retis.sssup.it |
||
14 | * http://hartik.sssup.it |
||
15 | */ |
||
16 | |||
17 | /* |
||
18 | * Copyright (C) 1999 Massimiliano Giorgi |
||
19 | * |
||
20 | * This program is free software; you can redistribute it and/or modify |
||
21 | * it under the terms of the GNU General Public License as published by |
||
22 | * the Free Software Foundation; either version 2 of the License, or |
||
23 | * (at your option) any later version. |
||
24 | * |
||
25 | * This program is distributed in the hope that it will be useful, |
||
26 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
27 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
28 | * GNU General Public License for more details. |
||
29 | * |
||
30 | * You should have received a copy of the GNU General Public License |
||
31 | * along with this program; if not, write to the Free Software |
||
32 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
||
33 | * |
||
34 | */ |
||
35 | |||
36 | /* |
||
108 | pj | 37 | * CVS : $Id: dcache.c,v 1.2 2003-03-24 11:19:56 pj Exp $ |
2 | pj | 38 | * |
39 | * File: $File$ |
||
108 | pj | 40 | * Revision: $Revision: 1.2 $ |
41 | * Last update: $Date: 2003-03-24 11:19:56 $ |
||
2 | pj | 42 | */ |
43 | |||
44 | #include <fs/util.h> |
||
45 | #include <fs/assert.h> |
||
46 | #include <fs/bdev.h> |
||
47 | #include <fs/magic.h> |
||
48 | #include <fs/major.h> |
||
49 | #include <fs/sysmacro.h> |
||
50 | #include "dcache.h" |
||
51 | #include "mutex.h" |
||
52 | #include "semaph.h" |
||
53 | #include "rwlock.h" |
||
54 | |||
55 | #include "debug.h" |
||
56 | |||
57 | /* |
||
58 | * To do: |
||
59 | * - separate the "buffer" field of a cache entry by the entry itself |
||
60 | * allowing a better memory management and a variable cache block size |
||
61 | * without wasting space. |
||
62 | * - improve the purging algorithm (the algorithm that remove entries from |
||
63 | * the cache). |
||
64 | * - implement a server to mantains an x% of cache buffers free and to write |
||
65 | * dirty cache entries to disk during idle periods. |
||
66 | */ |
||
67 | |||
68 | /* |
||
69 | * How the cache is implemented: |
||
70 | * copy-back algorithm or write-throught |
||
71 | * (define only one of this) |
||
72 | */ |
||
73 | |||
74 | #define COPYBACK |
||
75 | //#define WRITETHROUGHT |
||
76 | |||
77 | /* |
||
78 | * if a write throught policy is chosen for the cache if this |
||
79 | * is defined the 'skipwt' bits into the dcache_t structure is honoured |
||
80 | * (ie. if 'skipwt' is set the cache entry use a copyback policy and |
||
81 | * not a write throught policy). |
||
82 | */ |
||
83 | |||
84 | //#define HONOURSKIPWTFLAG |
||
85 | |||
86 | /* |
||
87 | * Data structures: |
||
88 | * |
||
89 | * We have two table: |
||
90 | * "dcache" contains cache entries |
||
91 | * "dhash" contains the index of the first entry of the hash list. |
||
92 | * Every cache entries has two fields used to concatenates the entries |
||
93 | * into lists. |
||
94 | * There is the list of free entries: "freeindex" is an index into "dcache" |
||
95 | * of the first free entries, every entry has a "next" field that points |
||
96 | * to the next free entry. |
||
97 | * Every entry into "dhash" is a pointer to the first cache entry that is |
||
98 | * into a hash bucket; every hash bucket is organized like a double linked |
||
99 | * list using the "next" and "prev" fields of the cache entry. |
||
100 | * |
||
101 | * DANGER: |
||
102 | * - to prevent dead-lock locking of "freemutex" MUST be done always |
||
103 | * after a lock of "hashmutex". |
||
104 | * - the functions that begins with "__????" do not lock/unlock |
||
105 | * the mutex. |
||
106 | */ |
||
107 | |||
108 | /*+ number of hash buckets +*/ |
||
109 | #define MAXHASH 64 |
||
110 | /*+ and-mask to obtain a number between 0 and MAXHASH-1 +*/ |
||
111 | #define MAXHASHMASK 0x3f |
||
112 | |||
113 | /*+ hash buckets +*/ |
||
114 | static int dhash[MAXHASH]; |
||
115 | /*+ mutex to operate on "dhash" +*/ |
||
116 | static __fs_mutex_t hashmutex; |
||
117 | |||
118 | /*+ number of cache entries +*/ |
||
119 | #define MAXCACHESIZE (8192*4) |
||
120 | /*+ cache entries table +*/ |
||
121 | static dcache_t dcache[MAXCACHESIZE]; |
||
122 | |||
123 | /*+ mutex to operate with the "free list" +*/ |
||
124 | static __fs_mutex_t freemutex; |
||
125 | /*+ index of first free cache entry +*/ |
||
126 | static int freeindex=0; |
||
127 | |||
128 | static __dev_t blocked_device=makedev(MAJOR_B_NULL,0); |
||
129 | |||
130 | /*++++++++++++++++++++++++++++++++++++++ |
||
131 | |||
132 | Hash function. |
||
133 | |||
134 | int hash_fun |
||
135 | return a number between 0 and MAXHASH-1. |
||
136 | |||
137 | __dev_t ldisk |
||
138 | block device. |
||
139 | |||
140 | __blkcnt_t lsector |
||
141 | block number. |
||
142 | ++++++++++++++++++++++++++++++++++++++*/ |
||
143 | |||
144 | static int hash_fun(__dev_t dev, __blkcnt_t lsector) |
||
145 | { |
||
146 | static __uint32_t table[8]={3,5,7,11,13,17,19,23}; |
||
147 | return (table[dev&0x07]*(lsector+1))&MAXHASHMASK; |
||
148 | } |
||
149 | |||
150 | /* |
||
151 | * |
||
152 | * INITIALIZATION/TERMINATION FUNCTIONS |
||
153 | * |
||
154 | */ |
||
155 | |||
156 | /*++++++++++++++++++++++++++++++++++++++ |
||
157 | |||
158 | Dump into the system logs the cache status. |
||
159 | |||
160 | ++++++++++++++++++++++++++++++++++++++*/ |
||
161 | |||
162 | void dcache_stats(void) |
||
163 | { |
||
164 | int i,c,d,l,j,r,lc; |
||
165 | long x,f; |
||
166 | |||
167 | /* acquire all mutex */ |
||
168 | __fs_mutex_lock(&hashmutex); |
||
169 | __fs_mutex_lock(&freemutex); |
||
170 | |||
171 | /* count free entries */ |
||
172 | c=0; |
||
173 | i=freeindex; |
||
174 | while (i!=NIL) { |
||
175 | c++; |
||
176 | i=dcache[i].next; |
||
177 | } |
||
178 | |||
179 | /* dump informations */ |
||
180 | printk(KERN_INFO "max dcache entries: %4i",MAXCACHESIZE); |
||
181 | printk(KERN_INFO " free entries: %4i",c); |
||
182 | |||
183 | /* count used entries */ |
||
184 | for (i=0,c=0,d=0,l=0,r=0;i<MAXHASH;i++) { |
||
185 | j=dhash[i]; |
||
186 | while (j!=NIL) { |
||
187 | c++; |
||
188 | if (dcache[j].used!=0) l++; |
||
189 | if (dcache[j].dirty) d++; |
||
190 | if (!dcache[j].ready) r++; |
||
191 | j=dcache[j].next; |
||
192 | } |
||
193 | } |
||
194 | |||
195 | /* dump informations */ |
||
196 | printk(KERN_INFO " cached entries: %4i",c); |
||
197 | printk(KERN_INFO " used entries: %4i",l); |
||
198 | printk(KERN_INFO " dirty entries: %4i",d); |
||
199 | printk(KERN_INFO " not ready entries: %4i",r); |
||
200 | |||
201 | /* compute hash function quality factor */ |
||
202 | for (i=0,x=0;i<MAXHASH;i++) { |
||
203 | j=dhash[i]; |
||
204 | lc=0; |
||
205 | while (j!=NIL) { |
||
206 | lc++; |
||
207 | j=dcache[j].next; |
||
208 | } |
||
209 | f=((long)lc*MAXHASH-c); |
||
210 | x+=f*f/(MAXHASH*2); |
||
211 | } |
||
212 | |||
213 | /* dump informations */ |
||
214 | printk(KERN_INFO "hash quality: %6li",x); |
||
215 | |||
216 | /* release all mutex */ |
||
217 | __fs_mutex_unlock(&freemutex); |
||
218 | __fs_mutex_unlock(&hashmutex); |
||
219 | } |
||
220 | |||
221 | /*++++++++++++++++++++++++++++++++++++++ |
||
222 | |||
223 | Module initialization; must be called prior to other functions. |
||
224 | |||
225 | int dcache_init |
||
226 | return 0 on success, other values on failure. |
||
227 | ++++++++++++++++++++++++++++++++++++++*/ |
||
228 | |||
229 | int dcache_init(void) |
||
230 | { |
||
231 | int i; |
||
232 | |||
233 | /* mutex initialization */ |
||
234 | __fs_mutex_init(&freemutex); |
||
235 | __fs_mutex_init(&hashmutex); |
||
236 | |||
237 | /* free list and cache table initialization */ |
||
238 | freeindex=0; |
||
239 | for (i=0;i<MAXCACHESIZE;i++) { |
||
240 | magic_set(dcache[i].magic,DCACHE_MAGIC); |
||
241 | dcache[i].next=i+1; |
||
242 | dcache[i].prev=NIL; |
||
243 | dcache[i].device=NULLDEV; |
||
244 | dcache[i].lsector=0; |
||
245 | dcache[i].used=-1; |
||
246 | dcache[i].dirty=0; |
||
247 | dcache[i].ready=0; |
||
248 | dcache[i].numblocked=0; |
||
249 | dcache[i].esyncreq=0; |
||
250 | dcache[i].skipwt=0; |
||
251 | __fs_sem_init(&dcache[i].sync,0); |
||
252 | __fs_sem_init(&dcache[i].esync,0); |
||
253 | __rwlock_init(&dcache[i].rwlock); |
||
254 | } |
||
255 | dcache[MAXCACHESIZE-1].next=NIL; |
||
256 | |||
257 | /* hash buckets initialization */ |
||
258 | for (i=0;i<MAXHASH;i++) |
||
259 | dhash[i]=NIL; |
||
260 | |||
261 | return 0; |
||
262 | } |
||
263 | |||
264 | /*++++++++++++++++++++++++++++++++++++++ |
||
265 | |||
266 | Terminate the cache flushing all dirty blocks and prevent |
||
267 | other request to be made to the cache module; the only function |
||
268 | that can be called after this is __dcache_flush(). |
||
269 | |||
270 | int dcache_end |
||
271 | return 0 on success other values on failure |
||
272 | |||
273 | int flag |
||
274 | if set aquire exclusive use of all cache entries |
||
275 | before ending |
||
276 | ++++++++++++++++++++++++++++++++++++++*/ |
||
277 | |||
278 | int dcache_end(int flag) |
||
279 | { |
||
280 | int __dcache_flush(int flag); |
||
281 | |||
282 | /* if a lock on all cache entries is required... */ |
||
283 | if (flag) { |
||
284 | int i,k; |
||
285 | __fs_mutex_lock(&hashmutex); |
||
286 | |||
287 | /* lock every request of other cache entries*/ |
||
288 | __fs_mutex_lock(&freemutex); |
||
289 | |||
290 | /* scan all hash bucket locking all cache entries */ |
||
291 | for (k=0;k<MAXHASH;k++) { |
||
292 | i=dhash[k]; |
||
293 | while (i!=NIL) { |
||
294 | /* so cache entry can not be removed! */ |
||
295 | dcache[i].used++; |
||
296 | __fs_mutex_unlock(&hashmutex); |
||
297 | |||
298 | /* exclusive lock */ |
||
299 | __rwlock_wrlock(&dcache[i].rwlock); |
||
300 | |||
301 | __fs_mutex_lock(&hashmutex); |
||
302 | dcache[i].used=1; |
||
303 | i=dcache[i].next; |
||
304 | } |
||
305 | } |
||
306 | __fs_mutex_unlock(&hashmutex); |
||
307 | } |
||
308 | |||
309 | /* this mutex is not released to prevent other modules use of this module */ |
||
310 | __fs_mutex_lock(&hashmutex); |
||
311 | /* flush the cache */ |
||
312 | return __dcache_flush(flag); |
||
313 | } |
||
314 | |||
315 | /* |
||
316 | * |
||
317 | * GET/FREE cache entries FUNCTIONS |
||
318 | * |
||
319 | */ |
||
320 | |||
321 | |||
322 | /*++++++++++++++++++++++++++++++++++++++ |
||
323 | |||
324 | Get a cache entry from the free list. |
||
325 | |||
326 | int get_dcache |
||
327 | return NIL on failure, an index into "dcache" on success. |
||
328 | ++++++++++++++++++++++++++++++++++++++*/ |
||
329 | |||
330 | static int get_dcache(void) |
||
331 | { |
||
332 | int ret; |
||
333 | |||
334 | /* remove the head of a list (if present) */ |
||
335 | |||
336 | __fs_mutex_lock(&freemutex); |
||
337 | ret=freeindex; |
||
338 | if (ret!=NIL) { |
||
339 | freeindex=dcache[ret].next; |
||
340 | _assert(dcache[ret].used==-1); |
||
341 | dcache[ret].used=0; |
||
342 | dcache[ret].skipwt=0; |
||
343 | magic_assert(dcache[ret].magic,DCACHE_MAGIC, |
||
344 | "dcache: get_dcache(): cache_entry[%i] overwritten", |
||
345 | ret); |
||
346 | } |
||
347 | __fs_mutex_unlock(&freemutex); |
||
348 | |||
349 | return ret; |
||
350 | } |
||
351 | |||
352 | |||
353 | /*++++++++++++++++++++++++++++++++++++++ |
||
354 | |||
355 | Insert a free cache entry into the free list. |
||
356 | |||
357 | int index |
||
358 | Index of the "dcache" entry to free. |
||
359 | ++++++++++++++++++++++++++++++++++++++*/ |
||
360 | |||
361 | static void free_dcache(int index) |
||
362 | { |
||
363 | /* insert an element into a list */ |
||
364 | |||
365 | _assert(index>=0&&index<MAXCACHESIZE); |
||
366 | _assert(dcache[index].used==0); |
||
367 | |||
368 | dcache[index].used=-1; |
||
369 | |||
370 | magic_assert(dcache[index].magic,DCACHE_MAGIC, |
||
371 | "dcache: free_dcache(): cache_entry[%i] overwritten", |
||
372 | index); |
||
373 | |||
374 | __fs_mutex_lock(&freemutex); |
||
375 | dcache[index].next=freeindex; |
||
376 | freeindex=index; |
||
377 | __fs_mutex_unlock(&freemutex); |
||
378 | } |
||
379 | |||
380 | /* |
||
381 | * |
||
382 | * HASH BUCKETS MANAGEMENT FUNCTIONS |
||
383 | * |
||
384 | */ |
||
385 | |||
386 | /*++++++++++++++++++++++++++++++++++++++ |
||
387 | |||
388 | Insert a cache entry into an hash bucket. |
||
389 | |||
390 | int index |
||
391 | Entry to insert. |
||
392 | ++++++++++++++++++++++++++++++++++++++*/ |
||
393 | |||
394 | static void __insert_dcache(int index) |
||
395 | { |
||
396 | int h; |
||
397 | |||
398 | /* insert an element into a double linked list */ |
||
399 | |||
400 | _assert(index>=0&&index<MAXCACHESIZE); |
||
401 | _assert(dcache[index].used==1); |
||
402 | |||
403 | magic_assert(dcache[index].magic,DCACHE_MAGIC, |
||
404 | "dcache: insert_dcache(): cache_entry[%i] overwritten", |
||
405 | index); |
||
406 | |||
407 | h=hash_fun(dcache[index].device,dcache[index].lsector); |
||
408 | |||
409 | dcache[index].prev=NIL; |
||
410 | dcache[index].hash=h; |
||
411 | |||
412 | dcache[index].next=dhash[h]; |
||
413 | |||
414 | if (dhash[h]!=NIL) dcache[dhash[h]].prev=index; |
||
415 | |||
416 | dhash[h]=index; |
||
417 | } |
||
418 | |||
419 | |||
420 | /*++++++++++++++++++++++++++++++++++++++ |
||
421 | |||
422 | Remove a cache entry from an hash bucket. |
||
423 | |||
424 | int index |
||
425 | Entry to remove. |
||
426 | ++++++++++++++++++++++++++++++++++++++*/ |
||
427 | |||
428 | static void __remove_dcache(int index) |
||
429 | { |
||
430 | /* remove an element from a double linked list */ |
||
431 | |||
432 | _assert(index>=0&&index<MAXCACHESIZE); |
||
433 | _assert(dcache[index].used==0); |
||
434 | |||
435 | magic_assert(dcache[index].magic,DCACHE_MAGIC, |
||
436 | "dcache: remove_dcache(): cache_entry[%i] overwritten", |
||
437 | index); |
||
438 | |||
439 | if (dcache[index].prev!=NIL) |
||
440 | dcache[dcache[index].prev].next=dcache[index].next; |
||
441 | else { |
||
442 | dhash[dcache[index].hash]=dcache[index].next; |
||
443 | } |
||
444 | if (dcache[index].next!=NIL) |
||
445 | dcache[dcache[index].next].prev=dcache[index].prev; |
||
446 | } |
||
447 | |||
448 | /*++++++++++++++++++++++++++++++++++++++ |
||
449 | |||
450 | Find an entry into an hash bucket to free. |
||
451 | |||
452 | int __purge_dcache |
||
453 | NIL on failure, an index of a free cache entry on success |
||
454 | ++++++++++++++++++++++++++++++++++++++*/ |
||
455 | |||
456 | static int __purge_dcache(void) |
||
457 | { |
||
458 | int i,k; |
||
459 | int flag; |
||
460 | int ind; |
||
461 | int res; |
||
462 | __time_t t; |
||
463 | |||
464 | /* TO IMPROVE!!! */ |
||
465 | |||
466 | /* algoritmo brutale ed inefficiente per rimuovere un'entry |
||
467 | * in cache: |
||
468 | * -- si scorrono sempre (sigh) tutte le entry |
||
469 | * -- viene trovata la entry non in uso, non sporca, piu' vecchia |
||
470 | * -- altrimenti quella non in uso, piu' vecchia |
||
471 | * -- altrimenti NIL (non rimuove niente) |
||
472 | */ |
||
473 | |||
474 | /* |
||
475 | * search an entry to purge |
||
476 | */ |
||
477 | |||
478 | flag=1; |
||
479 | ind=NIL; |
||
480 | t=0xffffffff; |
||
481 | |||
482 | for (k=0;k<MAXHASH;k++) { |
||
483 | i=dhash[k]; |
||
484 | while (i!=NIL) { |
||
485 | if (dcache[i].used==0) { |
||
486 | if (dcache[i].dirty==0) { |
||
487 | flag=0; |
||
488 | if (dcache[i].time<t||(ind!=NIL&&dcache[ind].dirty==1)) { |
||
489 | ind=i; |
||
490 | t=dcache[i].time; |
||
491 | } |
||
492 | } else if (flag) { |
||
493 | if (dcache[i].time<t) { |
||
494 | ind=i; |
||
495 | t=dcache[i].time; |
||
496 | } |
||
497 | } |
||
498 | } |
||
499 | i=dcache[i].next; |
||
500 | } |
||
501 | } |
||
502 | |||
503 | /* |
||
504 | * purging the entry |
||
505 | */ |
||
506 | |||
507 | /* if an entry is found... */ |
||
508 | if (ind!=NIL) { |
||
509 | /* if it is dirty... */ |
||
510 | if (dcache[ind].dirty) { |
||
511 | |||
512 | /* the entry is dirty... try to write to disk!*/ |
||
513 | |||
514 | /* update reference count */ |
||
515 | dcache[ind].used++; |
||
516 | /* set not ready flags */ |
||
517 | dcache[ind].ready=0; |
||
518 | /* safety stuff */ |
||
519 | _assert(dcache[ind].used==1); |
||
520 | /* release mutex */ |
||
521 | __fs_mutex_unlock(&hashmutex); |
||
522 | |||
523 | /* try to write... */ |
||
524 | /* there is no need to acquire the entry for writing... it is not used */ |
||
525 | res=bdev_write(dcache[ind].device,dcache[ind].lsector, |
||
526 | dcache[ind].buffer); |
||
527 | |||
528 | /* aquire the mutex */ |
||
529 | __fs_mutex_lock(&hashmutex); |
||
530 | |||
531 | /* if error while writing... */ |
||
532 | if (res!=0) { |
||
533 | /* restore old fields value */ |
||
534 | dcache[ind].used--; |
||
535 | dcache[ind].ready=1; |
||
536 | } |
||
537 | |||
538 | /* set flag if some thread has been blocked waiting for "ready" field */ |
||
539 | flag=(dcache[ind].numblocked>0); |
||
540 | |||
541 | /* wake up all thread waiting for synchronization */ |
||
542 | while (dcache[ind].numblocked>0) { |
||
543 | __fs_sem_signal(&dcache[ind].sync); |
||
544 | dcache[ind].numblocked--; |
||
545 | } |
||
546 | |||
547 | /* if error while writing... return NIL*/ |
||
548 | if (res!=0) return NIL; |
||
549 | |||
550 | /* to be ensure that no other treads can be blocked on this entry */ |
||
551 | dcache[ind].device=NULLDEV; |
||
552 | |||
553 | /* if some thread have been waked up... */ |
||
554 | if (flag) { |
||
555 | /* we must wait that all waked up thread had made the error test... */ |
||
556 | /* request error synchronization */ |
||
557 | dcache[ind].esyncreq=1; |
||
558 | /* release mutex */ |
||
559 | __fs_mutex_unlock(&hashmutex); |
||
560 | |||
561 | /* wait for synchronization */ |
||
562 | __fs_sem_wait(&dcache[ind].esync); |
||
563 | |||
564 | /* reacquire mutex */ |
||
565 | __fs_mutex_lock(&hashmutex); |
||
566 | /* safety stuff */ |
||
567 | /*_assert(dcache[ind].used==1);*/ |
||
568 | } |
||
569 | |||
570 | /* restore old value */ |
||
571 | dcache[ind].used--; |
||
572 | /* safety stuff */ |
||
573 | _assert(dcache[ind].used==0); |
||
574 | } |
||
575 | |||
576 | /* remove the entry from the hasb bucket*/ |
||
577 | __remove_dcache(ind); |
||
578 | } |
||
579 | |||
580 | return ind; |
||
581 | } |
||
582 | |||
583 | /*++++++++++++++++++++++++++++++++++++++ |
||
584 | |||
585 | Called when a cache entry has been modificated (AFTER has been |
||
586 | modified not before). |
||
587 | |||
588 | WARNING: this function CAN be called only by the task what has |
||
589 | aquired (for exclusive use) the cache entry. |
||
590 | |||
591 | void dcache_dirty |
||
592 | nothing to return |
||
593 | |||
594 | dcache_t *d |
||
595 | entry that must be marked dirty |
||
596 | ++++++++++++++++++++++++++++++++++++++*/ |
||
597 | |||
598 | #ifdef COPYBACK |
||
599 | |||
600 | void dcache_dirty(dcache_t *d) |
||
601 | { |
||
602 | /* safety stuff */ |
||
603 | _assert(d->used==1); |
||
604 | /* we use copy back so only set the flag */ |
||
605 | d->dirty=1; |
||
606 | } |
||
607 | |||
608 | /* used internally when we want flush a cache entry during |
||
609 | * generic unlock functions |
||
610 | */ |
||
611 | |||
612 | static __inline__ void __flush_cache(dcache_t *d) |
||
613 | { |
||
614 | /* nothing to do */ |
||
615 | return; |
||
616 | } |
||
617 | |||
618 | |||
619 | #endif |
||
620 | |||
621 | #ifdef WRITETHROUGHT |
||
622 | |||
623 | void dcache_dirty(dcache_t *d) |
||
624 | { |
||
625 | /* safety stuff */ |
||
626 | _assert(d->used==1); |
||
627 | /* we only set the flag */ |
||
628 | d->dirty=1; |
||
629 | } |
||
630 | |||
631 | /* used internally when we want flush a cache entry during |
||
632 | * generic unlock functions |
||
633 | */ |
||
634 | static __inline__ void __flush_cache(dcache_t *d) |
||
635 | { |
||
636 | int res; |
||
637 | |||
638 | #ifdef HONOURSKIPWTFLAG |
||
639 | if (d->skipwt) return; |
||
640 | #endif |
||
641 | |||
642 | if (d->dirty) { |
||
643 | /* safety stuff */ |
||
644 | _assert(d->used==1); |
||
645 | _assert(d-dcache>=0&&d-dcache<MAXCACHESIZE); |
||
646 | |||
647 | /* try to write... */ |
||
648 | /* there is no need to modify/lock the entry (see the warning!) */ |
||
649 | res=bdev_write(d->device,d->lsector,d->buffer); |
||
650 | |||
651 | /* if write OK... */ |
||
652 | if (res==0) d->dirty=0; |
||
653 | } |
||
654 | } |
||
655 | |||
656 | #endif |
||
657 | |||
658 | /*++++++++++++++++++++++++++++++++++++++ |
||
659 | |||
660 | Find a free cache entry to use. |
||
661 | |||
662 | int __catch_dcache |
||
663 | NIL on failure, a index of a free cache entry on success. |
||
664 | ++++++++++++++++++++++++++++++++++++++*/ |
||
665 | |||
666 | static __inline__ int __catch_dcache(void) |
||
667 | { |
||
668 | int ind; |
||
669 | |||
670 | ind=get_dcache(); |
||
671 | if (ind==NIL) ind=__purge_dcache(); |
||
672 | return ind; |
||
673 | } |
||
674 | |||
675 | /* |
||
676 | * |
||
677 | * FLUSHING FUNCTIONS |
||
678 | * |
||
679 | */ |
||
680 | |||
681 | /*++++++++++++++++++++++++++++++++++++++ |
||
682 | |||
683 | Flush all cache entries to disk; this function does not acquire the |
||
684 | "hashmutex" mutex so it can be called only during system shut down (with |
||
685 | no runnig thread) or after a call to dcache_end(). |
||
686 | The function dcache_end() call this function before ending. |
||
687 | |||
688 | int __dcache_flush |
||
689 | return 0 on success, other values on failure |
||
690 | |||
691 | inf flag |
||
692 | if set mean that we do have exclusive access to cache memory; if |
||
693 | we have exclusive access the "used" field must be 1 else must be 0. |
||
694 | ++++++++++++++++++++++++++++++++++++++*/ |
||
695 | |||
696 | int __dcache_flush(int flag) |
||
697 | { |
||
698 | int i,k,ret,res; |
||
699 | |||
700 | ret=0; |
||
701 | /* for every hash buckets... */ |
||
702 | for (k=0;k<MAXHASH;k++) { |
||
703 | i=dhash[k]; |
||
704 | /* scan all entries... */ |
||
705 | while (i!=NIL) { |
||
706 | _assert(dcache[i].used==(flag?1:0)); |
||
707 | /* for every dirty entry... */ |
||
708 | if (dcache[i].dirty) { |
||
709 | res=bdev_write(dcache[i].device,dcache[i].lsector,dcache[i].buffer); |
||
710 | if (res==0) |
||
711 | dcache[i].dirty=0; |
||
712 | else |
||
713 | ret=-1; |
||
714 | } |
||
715 | /* go to next entry */ |
||
716 | i=dcache[i].next; |
||
717 | } |
||
718 | } |
||
719 | |||
720 | return ret; |
||
721 | } |
||
722 | |||
723 | |||
724 | /*++++++++++++++++++++++++++++++++++++++ |
||
725 | |||
726 | Purge a device from the cache; remove every reference to the device |
||
727 | from the cache. |
||
728 | |||
729 | int dcache_purgedevice |
||
730 | |||
731 | |||
732 | __dev_t dev |
||
733 | device to purge |
||
734 | |||
735 | int cont |
||
736 | if setted continue on disk write error |
||
737 | ++++++++++++++++++++++++++++++++++++++*/ |
||
738 | |||
739 | int dcache_purgedevice(__dev_t dev, int cont) |
||
740 | { |
||
741 | int retvalue=0; |
||
742 | int i,k,inext; |
||
743 | int res; |
||
744 | |||
745 | printka("dcache_purgedevice() START for device(%08lx)",(long)dev); |
||
746 | |||
747 | __fs_mutex_lock(&hashmutex); |
||
748 | |||
749 | /* prevent other thread to cache this device*/ |
||
750 | blocked_device=dev; |
||
751 | |||
752 | for (k=0;k<MAXHASH;k++) { |
||
753 | i=dhash[k]; |
||
754 | /* scan all entries... */ |
||
755 | while (i!=NIL) { |
||
756 | |||
757 | /* remember next entry */ |
||
758 | inext=dcache[i].next; |
||
759 | |||
760 | if (dcache[i].device==dev) { |
||
761 | /* an entry to purge is found... */ |
||
762 | //printka(" found %li",dcache[i].lsector); |
||
763 | |||
764 | _assert(dcache[i].used!=-1); |
||
765 | while (dcache[i].used!=0) { |
||
766 | /* someone is using this entry... we must wait! */ |
||
767 | |||
768 | dcache[i].used++; |
||
769 | __fs_mutex_unlock(&hashmutex); |
||
770 | |||
771 | __rwlock_wrlock(&dcache[i].rwlock); |
||
772 | __rwlock_wrunlock(&dcache[i].rwlock); |
||
773 | |||
774 | __fs_mutex_lock(&hashmutex); |
||
775 | dcache[i].used--; |
||
776 | |||
777 | /* we must loop because, in general, we do not know how */ |
||
778 | /* the __rwlock queues are managed; the loop must quit because */ |
||
779 | /* we prevent other threads to be inserted into this queues */ |
||
780 | |||
781 | /* we must update 'inext' */ |
||
782 | inext=dcache[i].next; |
||
783 | } |
||
784 | |||
785 | if (dcache[i].dirty!=0) { |
||
786 | /* the cache entry is dirty... we must write to disk */ |
||
787 | printka(" dirty %li",dcache[i].lsector); |
||
788 | |||
789 | dcache[i].used++; |
||
790 | __fs_mutex_unlock(&hashmutex); |
||
791 | |||
792 | res=bdev_write(dcache[i].device,dcache[i].lsector,dcache[i].buffer); |
||
793 | |||
794 | __fs_mutex_lock(&hashmutex); |
||
795 | dcache[i].used--; |
||
796 | |||
797 | /* we must update 'inext' */ |
||
798 | inext=dcache[i].next; |
||
799 | |||
800 | if (res!=0) { |
||
801 | /* an error! */ |
||
802 | retvalue=-1; |
||
803 | if (!cont) { |
||
804 | /* ...we can not continue! */ |
||
805 | blocked_device=makedev(MAJOR_B_NULL,0); |
||
806 | __fs_mutex_unlock(&hashmutex); |
||
807 | return -1; |
||
808 | } |
||
809 | } |
||
810 | |||
811 | } |
||
812 | |||
813 | /* now we can purge the entry */ |
||
814 | __remove_dcache(i); |
||
815 | |||
816 | } |
||
817 | |||
818 | /* go to next entry */ |
||
819 | i=inext; |
||
820 | } |
||
821 | } |
||
822 | |||
823 | blocked_device=makedev(MAJOR_B_NULL,0); |
||
824 | __fs_mutex_unlock(&hashmutex); |
||
825 | |||
826 | printka("dcache_purgedevice() END"); |
||
827 | |||
828 | return retvalue; |
||
829 | } |
||
830 | |||
831 | /*++++++++++++++++++++++++++++++++++++++ |
||
832 | |||
833 | Flush all the cache to disk; it can be called always but it does not |
||
834 | assure that there are no more dirty cache entries when it return. |
||
835 | |||
836 | int dcache_flush |
||
837 | return 0 on success, other value on failure. |
||
838 | ++++++++++++++++++++++++++++++++++++++*/ |
||
839 | |||
840 | int dcache_flush(void) |
||
841 | { |
||
842 | int i,k,ret,res; |
||
843 | |||
844 | __fs_mutex_lock(&hashmutex); |
||
845 | ret=0; |
||
846 | for (k=0;k<MAXHASH;k++) { |
||
847 | i=dhash[k]; |
||
848 | /* for every dirty cache entries...*/ |
||
849 | while (i!=NIL) { |
||
850 | |||
851 | magic_assert(dcache[i].magic,DCACHE_MAGIC, |
||
852 | "dcache: dcache_flush(): cache_entry[%i] overwritten", |
||
853 | i); |
||
854 | |||
855 | if (dcache[i].dirty) { |
||
856 | /* to prevent purging the cache entry */ |
||
857 | dcache[i].used++; |
||
858 | __fs_mutex_unlock(&hashmutex); |
||
859 | |||
860 | /* aquire a "read lock" (we do not modify cache) to write to disk */ |
||
861 | __rwlock_rdlock(&dcache[i].rwlock); |
||
862 | /* write to disk */ |
||
863 | res=bdev_write(dcache[i].device,dcache[i].lsector,dcache[i].buffer); |
||
864 | /* release "read lock" */ |
||
865 | __rwlock_rdunlock(&dcache[i].rwlock); |
||
866 | |||
867 | __fs_mutex_lock(&hashmutex); |
||
868 | dcache[i].used--; |
||
869 | if (res==0) |
||
870 | dcache[i].dirty=0; |
||
871 | else |
||
872 | ret=-1; |
||
873 | } |
||
874 | i=dcache[i].next; |
||
875 | } |
||
876 | } |
||
877 | __fs_mutex_unlock(&hashmutex); |
||
878 | |||
879 | return ret; |
||
880 | } |
||
881 | |||
882 | /* |
||
883 | * |
||
884 | * LOCKING/UNLOCKING FUNCTIONS |
||
885 | * |
||
886 | * |
||
887 | * the external modules are responsable for nested lock; they can cause |
||
888 | * a dead lock of some threads if they lock blocks nesting the locks without |
||
889 | * a "locking protocol" |
||
890 | */ |
||
891 | |||
892 | |||
893 | /*++++++++++++++++++++++++++++++++++++++ |
||
894 | |||
895 | Lock (for read or write) a cache entry. |
||
896 | |||
897 | static __inline__ dcacdhe_t *dcache_genlock |
||
898 | return a pointer to the locked cache entry or NULL in case of error. |
||
899 | |||
900 | __dev_t device |
||
901 | device where there is the block to lock. |
||
902 | |||
903 | __blkcnt_t lsector |
||
904 | block to lock. |
||
905 | |||
906 | void (*lockfunc)(__rwlock_t*) |
||
907 | function used to lock; must be __rwlock_rdlock (for read) or |
||
908 | __rwlock_wrlock (for write). |
||
909 | ++++++++++++++++++++++++++++++++++++++*/ |
||
910 | |||
911 | static __inline__ dcache_t *dcache_genlock(__dev_t device, |
||
912 | __blkcnt_t lsector, |
||
913 | void (*lockfunc)(__rwlock_t*)) |
||
914 | { |
||
915 | int h,i; |
||
916 | int res; |
||
917 | |||
918 | /* compute hash value */ |
||
919 | h=hash_fun(device,lsector); |
||
920 | |||
921 | /* acquire the mutex */ |
||
922 | __fs_mutex_lock(&hashmutex); |
||
923 | |||
924 | /* |
||
925 | * STAGE 1: search into hash list |
||
926 | */ |
||
927 | |||
928 | /* get first entry */ |
||
929 | i=dhash[h]; |
||
930 | /* while there are other cache entries... */ |
||
931 | while (i!=NIL) { |
||
932 | if (dcache[i].device==device&&dcache[i].lsector==lsector) { |
||
933 | /* found... */ |
||
934 | /* safety stuff */ |
||
935 | _assert(dcache[i].used>=0); |
||
936 | /* update "used" count */ |
||
937 | dcache[i].used++; |
||
938 | /* but is ready? */ |
||
939 | if (!dcache[i].ready) { |
||
940 | /* not ready! */ |
||
941 | /* someone has already done this request but the cache is not ready */ |
||
942 | dcache[i].numblocked++; |
||
943 | /* release the mutex */ |
||
944 | __fs_mutex_unlock(&hashmutex); |
||
945 | /* wait for syncronization */ |
||
946 | __fs_sem_wait(&dcache[i].sync); |
||
947 | /* sync is arrived but ready? */ |
||
948 | if (!dcache[i].ready) { |
||
949 | /* not ready! an error has occured */ |
||
950 | /* reaquire mutex */ |
||
951 | __fs_mutex_lock(&hashmutex); |
||
952 | /* safety stuff */ |
||
953 | _assert(dcache[i].used>0); |
||
954 | /* update "used" count */ |
||
955 | dcache[i].used--; |
||
956 | /* if request for error syncronization... */ |
||
957 | if (dcache[i].esyncreq) { |
||
958 | /* request sync */ |
||
959 | /* if it is the last thread (other than the waiting tread)... */ |
||
960 | if (dcache[i].used==1) |
||
961 | /* signal error syncronization */ |
||
962 | __fs_sem_signal(&dcache[i].esync); |
||
963 | } else { |
||
964 | /* if there are not other threads... */ |
||
965 | if (dcache[i].used==0) { |
||
966 | /* free this entry */ |
||
967 | __remove_dcache(i); |
||
968 | free_dcache(i); |
||
969 | } |
||
970 | } |
||
971 | /* release mutex */ |
||
972 | __fs_mutex_unlock(&hashmutex); |
||
973 | /* nothing to return */ |
||
974 | return NULL; |
||
975 | } |
||
976 | /* aquire the "rwlock" */ |
||
977 | (*lockfunc)(&dcache[i].rwlock); |
||
978 | /* return the cache entry */ |
||
979 | return dcache+i; |
||
980 | } |
||
981 | /* ready! */ |
||
982 | /* release the mutex */ |
||
983 | __fs_mutex_unlock(&hashmutex); |
||
984 | /* aquire the "rwlock" */ |
||
985 | (*lockfunc)(&dcache[i].rwlock); |
||
986 | /* safety stuff */ |
||
987 | magic_assert(dcache[i].magic,DCACHE_MAGIC, |
||
988 | "dcache: dcache_genlock() 1: cache_entry[%i] overwritten", |
||
989 | i); |
||
990 | /* return the cache entry */ |
||
991 | return dcache+i; |
||
992 | } |
||
993 | /* get next entry */ |
||
994 | i=dcache[i].next; |
||
995 | } |
||
996 | |||
997 | /* |
||
998 | * STAGE 2: create a new dcache entry |
||
999 | */ |
||
1000 | |||
1001 | /* PS: if __catch_dcache() calls __purge_dcache() there is a great overhead |
||
1002 | * => to improve efficency a server that mantains x% of cache free is |
||
1003 | * required |
||
1004 | */ |
||
1005 | i=__catch_dcache(); |
||
1006 | if (i==NIL) { |
||
1007 | /* there is not space for new dcache entry...*/ |
||
1008 | __fs_mutex_unlock(&hashmutex); |
||
1009 | return NULL; |
||
1010 | } |
||
1011 | |||
1012 | /* found a free dcache entry... fill the entry */ |
||
1013 | dcache[i].used=1; |
||
1014 | dcache[i].dirty=0; |
||
1015 | dcache[i].device=device; |
||
1016 | dcache[i].lsector=lsector; |
||
1017 | dcache[i].ready=0; |
||
1018 | dcache[i].numblocked=0; |
||
1019 | dcache[i].esyncreq=0; |
||
1020 | |||
1021 | /* insert the entry intro the cache data structure */ |
||
1022 | __insert_dcache(i); |
||
1023 | |||
1024 | /* release the mutex */ |
||
1025 | __fs_mutex_unlock(&hashmutex); |
||
1026 | |||
1027 | /* the read is done after the hashmutex has been unlocked to allow */ |
||
1028 | /* thread cuncurrency */ |
||
1029 | res=bdev_read(device,lsector,dcache[i].buffer); |
||
1030 | |||
1031 | /* acquire the mutex */ |
||
1032 | __fs_mutex_lock(&hashmutex); |
||
1033 | |||
1034 | /* safety stuff */ |
||
1035 | _assert(dcache[i].used>0); |
||
1036 | _assert(dcache[i].ready==0); |
||
1037 | |||
1038 | /* if the read is OK... */ |
||
1039 | if (res==0) { |
||
1040 | /* cache ready */ |
||
1041 | dcache[i].ready=1; |
||
1042 | /* aquire the rwlock */ |
||
1043 | (*lockfunc)(&dcache[i].rwlock); |
||
1044 | } |
||
1045 | |||
1046 | /* wake up all thread waiting for synchronization */ |
||
1047 | while (dcache[i].numblocked>0) { |
||
1048 | __fs_sem_signal(&dcache[i].sync); |
||
1049 | dcache[i].numblocked--; |
||
1050 | } |
||
1051 | |||
1052 | /* if the read is not OK... */ |
||
1053 | if (res!=0) { |
||
1054 | /* to prevent other thread to take this cache entry */ |
||
1055 | dcache[i].device=NULLDEV; |
||
1056 | /* update cache "thread" count */ |
||
1057 | dcache[i].used--; |
||
1058 | /* if there are not other threads... */ |
||
1059 | if (dcache[i].used==0) { |
||
1060 | /* free this entry */ |
||
1061 | __remove_dcache(i); |
||
1062 | free_dcache(i); |
||
1063 | } |
||
1064 | /* release mutex */ |
||
1065 | __fs_mutex_unlock(&hashmutex); |
||
1066 | /* nothing to return */ |
||
1067 | return NULL; |
||
1068 | } |
||
1069 | |||
1070 | magic_assert(dcache[i].magic,DCACHE_MAGIC, |
||
1071 | "dcache: dcache_genlock() 2: cache_entry[%i] overwritten", |
||
1072 | i); |
||
1073 | |||
1074 | __fs_mutex_unlock(&hashmutex); |
||
1075 | return dcache+i; |
||
1076 | } |
||
1077 | |||
1078 | /*++++++++++++++++++++++++++++++++++++++ |
||
1079 | |||
1080 | Unlock a previously locked cache entry. |
||
1081 | |||
1082 | dcache_t *ptr |
||
1083 | cache enry to unlock. |
||
1084 | |||
1085 | void (*unlockfunc)(__rwlock_t*) |
||
1086 | unlocking function; must be __rwlock_rdunlock (for read) or |
||
1087 | __rwlock_wrunlock (for write). |
||
1088 | ++++++++++++++++++++++++++++++++++++++*/ |
||
1089 | |||
1090 | static __inline__ void dcache_genunlock(dcache_t *ptr, |
||
1091 | void (*unlockfunc)(__rwlock_t*)) |
||
1092 | { |
||
1093 | /* safety stuff */ |
||
1094 | _assert(ptr>=dcache&&ptr<dcache+MAXCACHESIZE); |
||
1095 | /* try to flush the cache if is dirty */ |
||
1096 | /* (this function depends of write thought/copy back) */ |
||
1097 | __flush_cache(ptr); |
||
1098 | /* acquire the mutex */ |
||
1099 | __fs_mutex_lock(&hashmutex); |
||
1100 | /* safety stuff */ |
||
1101 | _assert(ptr->used>0); |
||
1102 | /* update some fields */ |
||
1103 | ptr->used--; |
||
1104 | ptr->time=gettimek(); |
||
1105 | /* DANGER!!! I hope this work */ |
||
1106 | /* unlock the cache entry */ |
||
1107 | (*unlockfunc)(&ptr->rwlock); |
||
1108 | /* release the mutex */ |
||
1109 | __fs_mutex_unlock(&hashmutex); |
||
1110 | } |
||
1111 | |||
1112 | /*++++++++++++++++++++++++++++++++++++++ |
||
1113 | |||
1114 | Lock a cache entry used for READING. |
||
1115 | |||
1116 | dcacdhe_t *dcache_lock |
||
1117 | return a locked cache entry or NULL in case of error. |
||
1118 | |||
1119 | __dev_t device |
||
1120 | device where there is the block to lock. |
||
1121 | |||
1122 | __blkcnt_t lsector |
||
1123 | block to lock. |
||
1124 | ++++++++++++++++++++++++++++++++++++++*/ |
||
1125 | |||
1126 | dcache_t *dcache_lock(__dev_t device, __blkcnt_t lsector) |
||
1127 | { |
||
1128 | printk8("LOCK read request for (%04x,%li)",device,(long)lsector); |
||
1129 | if (device==blocked_device) return NULL; |
||
1130 | return dcache_genlock(device,lsector,__rwlock_rdlock); |
||
1131 | } |
||
1132 | |||
1133 | /*++++++++++++++++++++++++++++++++++++++ |
||
1134 | |||
1135 | Unlock a cache entry used for READING. |
||
1136 | |||
1137 | dcache_t *ptr |
||
1138 | pointer to the cache entry to unlock. |
||
1139 | ++++++++++++++++++++++++++++++++++++++*/ |
||
1140 | |||
1141 | void dcache_unlock(dcache_t *ptr) |
||
1142 | { |
||
1143 | printk8("LOCK read release for (%04x,%li)",ptr->device,(long)ptr->lsector); |
||
1144 | return dcache_genunlock(ptr,__rwlock_rdunlock); |
||
1145 | } |
||
1146 | |||
1147 | /*++++++++++++++++++++++++++++++++++++++ |
||
1148 | |||
1149 | Lock a cache entry used for WRITING (ie. acquire for exclusive use). |
||
1150 | If we write into cache we MUST call dcache_dirty(). |
||
1151 | |||
1152 | dcacdhe_t *dcache_acquire |
||
1153 | |||
1154 | __dev_t device |
||
1155 | device where there is the block to lock. |
||
1156 | |||
1157 | __blkcnt_t lsector |
||
1158 | block to lock. |
||
1159 | ++++++++++++++++++++++++++++++++++++++*/ |
||
1160 | |||
1161 | dcache_t *dcache_acquire(__dev_t device, __blkcnt_t lsector) |
||
1162 | { |
||
1163 | printk8("LOCK write request for (%04x,%li)",device,(long)lsector); |
||
1164 | if (device==blocked_device) return NULL; |
||
1165 | return dcache_genlock(device,lsector,__rwlock_wrlock); |
||
1166 | } |
||
1167 | |||
1168 | /*++++++++++++++++++++++++++++++++++++++ |
||
1169 | |||
1170 | Unlock a cache entry used for WRITING (ie. acquired for exclusive use). |
||
1171 | |||
1172 | dcache_t *ptr |
||
1173 | pointer to the cache entry to unlock. |
||
1174 | ++++++++++++++++++++++++++++++++++++++*/ |
||
1175 | |||
1176 | void dcache_release(dcache_t *ptr) |
||
1177 | { |
||
1178 | printk8("LOCK write released for (%04x,%li)",ptr->device,(long)ptr->lsector); |
||
1179 | return dcache_genunlock(ptr,__rwlock_wrunlock); |
||
1180 | } |
||
1181 |