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