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