Subversion Repositories shark

Rev

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