1 /* 2 ext2_buffer.c -- ext2 buffer cache 3 Copyright (C) 1998-2000, 2007 Free Software Foundation, Inc. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17 */ 18 19 #include <config.h> 20 21 #ifndef DISCOVER_ONLY 22 23 #include <stdio.h> 24 #include <stdlib.h> 25 #include <string.h> 26 #include "ext2.h" 27 28 /* pseudo-header */ 29 30 static __inline__ int ext2_block_hash(blk_t block) 31 { 32 unsigned long x; 33 34 x = block ^ (block >> 8) ^ (block >> 16) ^ (block >> 24); 35 return x & ((1 << ext2_hash_bits) - 1); 36 } 37 38 static struct ext2_buffer_head *ext2_bh_alloc (struct ext2_buffer_cache *, blk_t); 39 static void ext2_bh_dealloc (struct ext2_buffer_head *); 40 static struct ext2_buffer_head *ext2_bh_find (struct ext2_buffer_cache *, blk_t); 41 static int ext2_bh_do_read (struct ext2_buffer_head *); 42 static int ext2_bh_do_write(struct ext2_buffer_head *); 43 static void ext2_bh_hash (struct ext2_buffer_head *); 44 static void ext2_bh_unhash (struct ext2_buffer_head *); 45 46 47 48 static int try_to_flush(struct ext2_buffer_cache *bc) 49 { 50 int i; 51 52 for (i=0;i<bc->size;i++) 53 { 54 struct ext2_buffer_head *bh; 55 56 bh = &bc->heads[i]; 57 58 if (bh->alloc && !bh->usecount && !bh->dirty) 59 { 60 ext2_bh_dealloc(bh); 61 return 1; 62 } 63 } 64 65 for (i=0;i<bc->size;i++) 66 { 67 struct ext2_buffer_head *bh; 68 69 bh = &bc->heads[i]; 70 71 if (bh->alloc && !bh->usecount && bh->dirty) 72 { 73 ext2_bh_do_write(bh); 74 ext2_bh_dealloc(bh); 75 return 1; 76 } 77 } 78 79 if (ped_exception_throw (PED_EXCEPTION_ERROR, 80 PED_EXCEPTION_IGNORE_CANCEL, 81 _("Couldn't flush buffer cache!")) 82 != PED_EXCEPTION_IGNORE) 83 return 0; 84 return 1; 85 } 86 87 88 89 90 91 static struct ext2_buffer_head *ext2_bh_alloc(struct ext2_buffer_cache *bc, blk_t block) 92 { 93 struct ext2_buffer_head *bh; 94 int i; 95 96 bh = NULL; 97 98 tryagain: 99 for (i=0;i<bc->size;i++) 100 { 101 bh = &bc->heads[i]; 102 103 if (!bh->alloc) 104 break; 105 } 106 107 if (i == bc->size) 108 { 109 try_to_flush(bc); 110 goto tryagain; 111 } 112 113 bh = &bc->heads[i]; 114 115 bh->next = NULL; 116 bh->prev = NULL; 117 bh->block = block; 118 bh->usecount = 0; 119 bh->dirty = 0; 120 bh->alloc = 1; 121 bc->numalloc++; 122 123 ext2_bh_hash(bh); 124 125 return bh; 126 } 127 128 static void ext2_bh_dealloc(struct ext2_buffer_head *bh) 129 { 130 if (bh->dirty) 131 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_IGNORE, 132 "deallocing() a dirty buffer! %i\n", bh->block); 133 134 ext2_bh_unhash(bh); 135 bh->alloc = 0; 136 bh->bc->numalloc--; 137 } 138 139 static struct ext2_buffer_head *ext2_bh_find(struct ext2_buffer_cache *bc, blk_t block) 140 { 141 struct ext2_buffer_head *a; 142 struct ext2_buffer_head *b; 143 int hash; 144 145 hash = ext2_block_hash(block); 146 a = bc->hash[hash]; 147 148 if (a != NULL) 149 { 150 b = a; 151 do 152 { 153 if (a->block == block) 154 return a; 155 156 a = a->next; 157 } while (a != b); 158 } 159 160 return NULL; 161 } 162 163 static int ext2_bh_do_read(struct ext2_buffer_head *bh) 164 { 165 return ext2_read_blocks(bh->bc->fs, bh->data, bh->block, 1); 166 } 167 168 static int ext2_bh_do_write(struct ext2_buffer_head *bh) 169 { 170 if (!bh->alloc) { 171 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_CANCEL, 172 "Attempt to write unallocated buffer."); 173 return 0; 174 } 175 176 ext2_write_blocks(bh->bc->fs, bh->data, bh->block, 1); 177 bh->dirty = 0; 178 return 1; 179 } 180 181 static void ext2_bh_hash(struct ext2_buffer_head *bh) 182 { 183 int hash; 184 185 hash = ext2_block_hash(bh->block); 186 if (bh->bc->hash[hash] != NULL) 187 { 188 bh->next = bh->bc->hash[hash]; 189 bh->prev = bh->next->prev; 190 bh->next->prev = bh; 191 bh->prev->next = bh; 192 return; 193 } 194 195 bh->bc->hash[hash] = bh; 196 bh->next = bh->prev = bh; 197 } 198 199 static void ext2_bh_unhash(struct ext2_buffer_head *bh) 200 { 201 int hash; 202 203 hash = ext2_block_hash(bh->block); 204 205 bh->prev->next = bh->next; 206 bh->next->prev = bh->prev; 207 208 if (bh->bc->hash[hash] == bh) 209 { 210 if (bh->next != bh) 211 bh->bc->hash[hash] = bh->next; 212 else 213 bh->bc->hash[hash] = NULL; 214 } 215 216 bh->next = NULL; 217 bh->prev = NULL; 218 } 219 220 221 222 223 224 225 226 static int breadimmhits = 0; 227 static int breadindhits = 0; 228 static int breadmisses = 0; 229 230 void ext2_bcache_deinit(struct ext2_fs *fs) 231 { 232 ext2_bcache_sync(fs); 233 ped_free(fs->bc->buffermem); 234 ped_free(fs->bc->hash); 235 ped_free(fs->bc->heads); 236 ped_free(fs->bc); 237 238 if (fs->opt_verbose) 239 fprintf(stderr, 240 "direct hits: %i, indirect hits: %i, misses: %i\n", 241 breadimmhits, 242 breadindhits, 243 breadmisses); 244 } 245 246 void ext2_bcache_dump(struct ext2_fs *fs) 247 { 248 int i; 249 250 fputs ("buffer cache dump:\n", stderr); 251 252 for (i=0;i<(1<<ext2_hash_bits);i++) 253 if (fs->bc->hash[i] != NULL) 254 { 255 struct ext2_buffer_head *a; 256 struct ext2_buffer_head *b; 257 258 fprintf(stderr, "%i: ", i); 259 260 a = b = fs->bc->hash[i]; 261 do 262 { 263 fprintf(stderr, "%i ", a->block); 264 a = a->next; 265 } while (a != b); 266 267 fputc ('\n', stderr); 268 } 269 } 270 271 int ext2_bcache_flush(struct ext2_fs *fs, blk_t block) 272 { 273 struct ext2_buffer_head *bh; 274 275 if ((bh = ext2_bh_find(fs->bc, block)) == NULL) 276 return 1; 277 278 if (bh->usecount) { 279 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_CANCEL, 280 "Attempt to flush a buffer that's in use! [%i,%i]", 281 bh->block, bh->usecount); 282 return 0; 283 } 284 285 if (bh->dirty) { 286 if (!ext2_bh_do_write(bh)) 287 return 0; 288 } 289 290 ext2_bh_dealloc(bh); 291 return 1; 292 } 293 294 int ext2_bcache_flush_range(struct ext2_fs *fs, blk_t block, blk_t num) 295 { 296 blk_t end = block + num; 297 298 for (; block < end; block++) { 299 if (!ext2_bcache_flush(fs, block)) 300 return 0; 301 } 302 return 1; 303 } 304 305 int ext2_bcache_init(struct ext2_fs *fs) 306 { 307 struct ext2_buffer_cache *bc; 308 int i; 309 int size; 310 311 size = ext2_buffer_cache_pool_size >> (fs->logsize - 10); 312 313 if ((bc = (struct ext2_buffer_cache *) ped_malloc(sizeof(struct ext2_buffer_cache))) == NULL) 314 return 0; 315 316 if ((bc->heads = (struct ext2_buffer_head *) ped_malloc(size * sizeof(struct ext2_buffer_head))) == NULL) 317 return 0; 318 319 if ((bc->hash = (struct ext2_buffer_head **) ped_malloc(sizeof(struct ext2_buffer_head *) << ext2_hash_bits)) == NULL) 320 { 321 ped_free(bc->heads); 322 ped_free(bc); 323 return 0; 324 } 325 326 if ((bc->buffermem = (unsigned char *) ped_malloc(ext2_buffer_cache_pool_size << 10)) == NULL) 327 { 328 ped_free(bc->hash); 329 ped_free(bc->heads); 330 ped_free(bc); 331 return 0; 332 } 333 334 bc->cache = &bc->heads[0]; 335 bc->fs = fs; 336 bc->size = size; 337 bc->numalloc = 0; 338 339 for (i=0;i<size;i++) 340 { 341 bc->heads[i].data = bc->buffermem + (i << fs->logsize); 342 bc->heads[i].bc = bc; 343 bc->heads[i].alloc = 0; 344 } 345 346 for (i=0;i<(1<<ext2_hash_bits);i++) 347 bc->hash[i] = NULL; 348 349 fs->bc = bc; 350 351 return 1; 352 } 353 354 int ext2_bcache_sync(struct ext2_fs *fs) 355 { 356 int i; 357 358 for (i=0;i<fs->bc->size;i++) 359 { 360 struct ext2_buffer_head *bh; 361 362 bh = &fs->bc->heads[i]; 363 364 if (bh->alloc && bh->dirty) { 365 if (!ext2_bh_do_write(bh)) 366 return 0; 367 } 368 } 369 return 1; 370 } 371 372 373 374 375 376 377 378 379 struct ext2_buffer_head *ext2_bcreate(struct ext2_fs *fs, blk_t block) 380 { 381 struct ext2_buffer_head *bh; 382 383 if ((bh = ext2_bh_find(fs->bc, block)) != NULL) 384 { 385 bh->usecount++; 386 } 387 else 388 { 389 bh = ext2_bh_alloc(fs->bc, block); 390 bh->usecount = 1; 391 } 392 393 memset(bh->data, 0, fs->blocksize); 394 bh->dirty = 1; 395 396 return bh; 397 } 398 399 struct ext2_buffer_head *ext2_bread(struct ext2_fs *fs, blk_t block) 400 { 401 struct ext2_buffer_head *bh; 402 403 if ((bh = fs->bc->cache)->block == block) 404 { 405 breadimmhits++; 406 bh->usecount++; 407 return bh; 408 } 409 410 if ((bh = ext2_bh_find(fs->bc, block)) != NULL) 411 { 412 fs->bc->cache = bh; 413 breadindhits++; 414 bh->usecount++; 415 return bh; 416 } 417 418 breadmisses++; 419 420 bh = ext2_bh_alloc(fs->bc, block); 421 fs->bc->cache = bh; 422 bh->usecount = 1; 423 if (!ext2_bh_do_read(bh)) { 424 ext2_bh_dealloc(bh); 425 return NULL; 426 } 427 428 return bh; 429 } 430 431 int ext2_brelse(struct ext2_buffer_head *bh, int forget) 432 { 433 if (bh->usecount-- == 1 && forget) 434 { 435 if (bh->dirty) { 436 if (!ext2_bh_do_write(bh)) 437 return 0; 438 } 439 440 ext2_bh_dealloc(bh); 441 } 442 return 1; 443 } 444 445 #endif /* !DISCOVER_ONLY */ 446