root/fs/buffer.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. wait_on_buffer
  2. sync_buffers
  3. sys_sync
  4. sync_dev
  5. invalidate_buffers
  6. check_disk_change
  7. remove_from_hash_queue
  8. remove_from_free_list
  9. remove_from_queues
  10. put_first_free
  11. put_last_free
  12. insert_into_queues
  13. find_buffer
  14. get_hash_table
  15. getblk
  16. brelse
  17. bread
  18. bread_page
  19. breada
  20. put_unused_buffer_head
  21. get_more_buffer_heads
  22. get_unused_buffer_head
  23. grow_buffers
  24. try_to_free
  25. shrink_buffers
  26. buffer_init

   1 /*
   2  *  linux/fs/buffer.c
   3  *
   4  *  Copyright (C) 1991, 1992  Linus Torvalds
   5  */
   6 
   7 /*
   8  *  'buffer.c' implements the buffer-cache functions. Race-conditions have
   9  * been avoided by NEVER letting a interrupt change a buffer (except for the
  10  * data, of course), but instead letting the caller do it. NOTE! As interrupts
  11  * can wake up a caller, some cli-sti sequences are needed to check for
  12  * sleep-on-calls. These should be extremely quick, though (I hope).
  13  */
  14 
  15 /*
  16  * NOTE! There is one discordant note here: checking floppies for
  17  * disk change. This is where it fits best, I think, as it should
  18  * invalidate changed floppy-disk-caches.
  19  */
  20 
  21 #include <stdarg.h>
  22  
  23 #include <linux/config.h>
  24 #include <linux/sched.h>
  25 #include <linux/kernel.h>
  26 #include <linux/string.h>
  27 
  28 #include <asm/system.h>
  29 #include <asm/io.h>
  30 
  31 #ifdef CONFIG_BLK_DEV_SR
  32 extern int check_cdrom_media_change(int, int);
  33 #endif
  34 
  35 static struct buffer_head * hash_table[NR_HASH];
  36 static struct buffer_head * free_list = NULL;
  37 static struct buffer_head * unused_list = NULL;
  38 static struct wait_queue * buffer_wait = NULL;
  39 
  40 int nr_buffers = 0;
  41 int nr_buffer_heads = 0;
  42 
  43 static inline void wait_on_buffer(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
  44 {
  45         cli();
  46         while (bh->b_lock)
  47                 sleep_on(&bh->b_wait);
  48         sti();
  49 }
  50 
  51 static void sync_buffers(int dev)
     /* [previous][next][first][last][top][bottom][index][help] */
  52 {
  53         int i;
  54         struct buffer_head * bh;
  55 
  56         bh = free_list;
  57         for (i = nr_buffers*2 ; i-- > 0 ; bh = bh->b_next_free) {
  58                 if (bh->b_lock)
  59                         continue;
  60                 if (!bh->b_dirt)
  61                         continue;
  62                 ll_rw_block(WRITE,bh);
  63         }
  64 }
  65 
  66 int sys_sync(void)
     /* [previous][next][first][last][top][bottom][index][help] */
  67 {
  68         int i;
  69 
  70         for (i=0 ; i<NR_SUPER ; i++)
  71                 if (super_block[i].s_dev
  72                     && super_block[i].s_op 
  73                     && super_block[i].s_op->write_super 
  74                     && super_block[i].s_dirt)
  75                         super_block[i].s_op->write_super(&super_block[i]);
  76         sync_inodes();          /* write out inodes into buffers */
  77         sync_buffers(0);
  78         return 0;
  79 }
  80 
  81 int sync_dev(int dev)
     /* [previous][next][first][last][top][bottom][index][help] */
  82 {
  83         struct super_block * sb;
  84 
  85         if (sb = get_super (dev))
  86                 if (sb->s_op && sb->s_op->write_super && sb->s_dirt)
  87                         sb->s_op->write_super (sb);
  88         sync_buffers(dev);
  89         sync_inodes();
  90         sync_buffers(dev);
  91         return 0;
  92 }
  93 
  94 void inline invalidate_buffers(int dev)
     /* [previous][next][first][last][top][bottom][index][help] */
  95 {
  96         int i;
  97         struct buffer_head * bh;
  98 
  99         bh = free_list;
 100         for (i = nr_buffers*2 ; --i > 0 ; bh = bh->b_next_free) {
 101                 if (bh->b_dev != dev)
 102                         continue;
 103                 wait_on_buffer(bh);
 104                 if (bh->b_dev == dev)
 105                         bh->b_uptodate = bh->b_dirt = 0;
 106         }
 107 }
 108 
 109 /*
 110  * This routine checks whether a floppy has been changed, and
 111  * invalidates all buffer-cache-entries in that case. This
 112  * is a relatively slow routine, so we have to try to minimize using
 113  * it. Thus it is called only upon a 'mount' or 'open'. This
 114  * is the best way of combining speed and utility, I think.
 115  * People changing diskettes in the middle of an operation deserve
 116  * to loose :-)
 117  *
 118  * NOTE! Although currently this is only for floppies, the idea is
 119  * that any additional removable block-device will use this routine,
 120  * and that mount/open needn't know that floppies/whatever are
 121  * special.
 122  */
 123 void check_disk_change(int dev)
     /* [previous][next][first][last][top][bottom][index][help] */
 124 {
 125         int i;
 126         struct buffer_head * bh;
 127 
 128         switch(MAJOR(dev)){
 129         case 2: /* floppy disc */
 130                 if (!(bh = getblk(dev,0,1024)))
 131                         return;
 132                 i = floppy_change(bh);
 133                 brelse(bh);
 134                 break;
 135 
 136 #ifdef CONFIG_BLK_DEV_SR
 137          case 11: /* CDROM */
 138                 i = check_cdrom_media_change(dev, 0);
 139                 if (i) printk("Flushing buffers and inodes for CDROM\n");
 140                 break;
 141 #endif
 142 
 143          default:
 144                 return;
 145         };
 146 
 147         if (!i) return;
 148 
 149         for (i=0 ; i<NR_SUPER ; i++)
 150                 if (super_block[i].s_dev == dev)
 151                         put_super(super_block[i].s_dev);
 152         invalidate_inodes(dev);
 153         invalidate_buffers(dev);
 154 }
 155 
 156 #define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
 157 #define hash(dev,block) hash_table[_hashfn(dev,block)]
 158 
 159 static inline void remove_from_hash_queue(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 160 {
 161         if (bh->b_next)
 162                 bh->b_next->b_prev = bh->b_prev;
 163         if (bh->b_prev)
 164                 bh->b_prev->b_next = bh->b_next;
 165         if (hash(bh->b_dev,bh->b_blocknr) == bh)
 166                 hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
 167         bh->b_next = bh->b_prev = NULL;
 168 }
 169 
 170 static inline void remove_from_free_list(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 171 {
 172         if (!(bh->b_prev_free) || !(bh->b_next_free))
 173                 panic("Free block list corrupted");
 174         bh->b_prev_free->b_next_free = bh->b_next_free;
 175         bh->b_next_free->b_prev_free = bh->b_prev_free;
 176         if (free_list == bh)
 177                 free_list = bh->b_next_free;
 178         bh->b_next_free = bh->b_prev_free = NULL;
 179 }
 180 
 181 static inline void remove_from_queues(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 182 {
 183         remove_from_hash_queue(bh);
 184         remove_from_free_list(bh);
 185 }
 186 
 187 static inline void put_first_free(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 188 {
 189         if (!bh || (bh == free_list))
 190                 return;
 191         remove_from_free_list(bh);
 192 /* add to front of free list */
 193         bh->b_next_free = free_list;
 194         bh->b_prev_free = free_list->b_prev_free;
 195         free_list->b_prev_free->b_next_free = bh;
 196         free_list->b_prev_free = bh;
 197         free_list = bh;
 198 }
 199 
 200 static inline void put_last_free(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 201 {
 202         if (!bh)
 203                 return;
 204         if (bh == free_list) {
 205                 free_list = bh->b_next_free;
 206                 return;
 207         }
 208         remove_from_free_list(bh);
 209 /* add to back of free list */
 210         bh->b_next_free = free_list;
 211         bh->b_prev_free = free_list->b_prev_free;
 212         free_list->b_prev_free->b_next_free = bh;
 213         free_list->b_prev_free = bh;
 214 }
 215 
 216 static inline void insert_into_queues(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 217 {
 218 /* put at end of free list */
 219         bh->b_next_free = free_list;
 220         bh->b_prev_free = free_list->b_prev_free;
 221         free_list->b_prev_free->b_next_free = bh;
 222         free_list->b_prev_free = bh;
 223 /* put the buffer in new hash-queue if it has a device */
 224         bh->b_prev = NULL;
 225         bh->b_next = NULL;
 226         if (!bh->b_dev)
 227                 return;
 228         bh->b_next = hash(bh->b_dev,bh->b_blocknr);
 229         hash(bh->b_dev,bh->b_blocknr) = bh;
 230         if (bh->b_next)
 231                 bh->b_next->b_prev = bh;
 232 }
 233 
 234 static struct buffer_head * find_buffer(int dev, int block, int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 235 {               
 236         struct buffer_head * tmp;
 237 
 238         for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
 239                 if (tmp->b_dev==dev && tmp->b_blocknr==block)
 240                         if (tmp->b_size == size)
 241                                 return tmp;
 242                         else {
 243                                 printk("wrong block-size on device %04x\n",dev);
 244                                 return NULL;
 245                         }
 246         return NULL;
 247 }
 248 
 249 /*
 250  * Why like this, I hear you say... The reason is race-conditions.
 251  * As we don't lock buffers (unless we are readint them, that is),
 252  * something might happen to it while we sleep (ie a read-error
 253  * will force it bad). This shouldn't really happen currently, but
 254  * the code is ready.
 255  */
 256 struct buffer_head * get_hash_table(int dev, int block, int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 257 {
 258         struct buffer_head * bh;
 259 
 260         for (;;) {
 261                 if (!(bh=find_buffer(dev,block,size)))
 262                         return NULL;
 263                 bh->b_count++;
 264                 wait_on_buffer(bh);
 265                 if (bh->b_dev == dev && bh->b_blocknr == block && bh->b_size == size) {
 266                         put_last_free(bh);
 267                         return bh;
 268                 }
 269                 bh->b_count--;
 270         }
 271 }
 272 
 273 /*
 274  * Ok, this is getblk, and it isn't very clear, again to hinder
 275  * race-conditions. Most of the code is seldom used, (ie repeating),
 276  * so it should be much more efficient than it looks.
 277  *
 278  * The algoritm is changed: hopefully better, and an elusive bug removed.
 279  *
 280  * 14.02.92: changed it to sync dirty buffers a bit: better performance
 281  * when the filesystem starts to get full of dirty blocks (I hope).
 282  */
 283 #define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
 284 struct buffer_head * getblk(int dev, int block, int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 285 {
 286         struct buffer_head * bh, * tmp;
 287         int buffers;
 288 
 289 repeat:
 290         if (bh = get_hash_table(dev, block, size))
 291                 return bh;
 292 
 293         if (nr_free_pages > 30)
 294                 grow_buffers(size);
 295 
 296         buffers = nr_buffers;
 297         bh = NULL;
 298 
 299         for (tmp = free_list; buffers-- > 0 ; tmp = tmp->b_next_free) {
 300                 if (tmp->b_count || tmp->b_size != size)
 301                         continue;
 302                 if (!bh || BADNESS(tmp)<BADNESS(bh)) {
 303                         bh = tmp;
 304                         if (!BADNESS(tmp))
 305                                 break;
 306                 }
 307 #if 0
 308                 if (tmp->b_dirt)
 309                         ll_rw_block(WRITEA,tmp);
 310 #endif
 311         }
 312 
 313         if (!bh && nr_free_pages > 5) {
 314                 grow_buffers(size);
 315                 goto repeat;
 316         }
 317         
 318 /* and repeat until we find something good */
 319         if (!bh) {
 320                 sleep_on(&buffer_wait);
 321                 goto repeat;
 322         }
 323         wait_on_buffer(bh);
 324         if (bh->b_count || bh->b_size != size)
 325                 goto repeat;
 326         if (bh->b_dirt) {
 327                 sync_buffers(bh->b_dev);
 328                 goto repeat;
 329         }
 330 /* NOTE!! While we slept waiting for this block, somebody else might */
 331 /* already have added "this" block to the cache. check it */
 332         if (find_buffer(dev,block,size))
 333                 goto repeat;
 334 /* OK, FINALLY we know that this buffer is the only one of it's kind, */
 335 /* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
 336         bh->b_count=1;
 337         bh->b_dirt=0;
 338         bh->b_uptodate=0;
 339         remove_from_queues(bh);
 340         bh->b_dev=dev;
 341         bh->b_blocknr=block;
 342         insert_into_queues(bh);
 343         return bh;
 344 }
 345 
 346 void brelse(struct buffer_head * buf)
     /* [previous][next][first][last][top][bottom][index][help] */
 347 {
 348         if (!buf)
 349                 return;
 350         wait_on_buffer(buf);
 351         if (!(buf->b_count--))
 352                 panic("Trying to free free buffer");
 353         wake_up(&buffer_wait);
 354 }
 355 
 356 /*
 357  * bread() reads a specified block and returns the buffer that contains
 358  * it. It returns NULL if the block was unreadable.
 359  */
 360 struct buffer_head * bread(int dev, int block, int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 361 {
 362         struct buffer_head * bh;
 363 
 364         if (!(bh = getblk(dev, block, size))) {
 365                 printk("bread: getblk returned NULL\n");
 366                 return NULL;
 367         }
 368         if (bh->b_uptodate)
 369                 return bh;
 370         ll_rw_block(READ,bh);
 371         wait_on_buffer(bh);
 372         if (bh->b_uptodate)
 373                 return bh;
 374         brelse(bh);
 375         return NULL;
 376 }
 377 
 378 #define COPYBLK(from,to) \
 379 __asm__("cld\n\t" \
 380         "rep\n\t" \
 381         "movsl\n\t" \
 382         ::"c" (BLOCK_SIZE/4),"S" (from),"D" (to) \
 383         :"cx","di","si")
 384 
 385 /*
 386  * bread_page reads four buffers into memory at the desired address. It's
 387  * a function of its own, as there is some speed to be got by reading them
 388  * all at the same time, not waiting for one to be read, and then another
 389  * etc.
 390  */
 391 void bread_page(unsigned long address,int dev,int b[4])
     /* [previous][next][first][last][top][bottom][index][help] */
 392 {
 393         struct buffer_head * bh[4];
 394         int i;
 395 
 396         for (i=0 ; i<4 ; i++)
 397                 if (b[i]) {
 398                         if (bh[i] = getblk(dev, b[i], 1024))
 399                                 if (!bh[i]->b_uptodate)
 400                                         ll_rw_block(READ,bh[i]);
 401                 } else
 402                         bh[i] = NULL;
 403         for (i=0 ; i<4 ; i++,address += BLOCK_SIZE)
 404                 if (bh[i]) {
 405                         wait_on_buffer(bh[i]);
 406                         if (bh[i]->b_uptodate)
 407                                 COPYBLK((unsigned long) bh[i]->b_data,address);
 408                         brelse(bh[i]);
 409                 }
 410 }
 411 
 412 /*
 413  * Ok, breada can be used as bread, but additionally to mark other
 414  * blocks for reading as well. End the argument list with a negative
 415  * number.
 416  */
 417 struct buffer_head * breada(int dev,int first, ...)
     /* [previous][next][first][last][top][bottom][index][help] */
 418 {
 419         va_list args;
 420         struct buffer_head * bh, *tmp;
 421 
 422         va_start(args,first);
 423         if (!(bh = getblk(dev, first, 1024))) {
 424                 printk("breada: getblk returned NULL\n");
 425                 return NULL;
 426         }
 427         if (!bh->b_uptodate)
 428                 ll_rw_block(READ,bh);
 429         while ((first=va_arg(args,int))>=0) {
 430                 tmp = getblk(dev, first, 1024);
 431                 if (tmp) {
 432                         if (!tmp->b_uptodate)
 433                                 ll_rw_block(READA,tmp);
 434                         tmp->b_count--;
 435                 }
 436         }
 437         va_end(args);
 438         wait_on_buffer(bh);
 439         if (bh->b_uptodate)
 440                 return bh;
 441         brelse(bh);
 442         return (NULL);
 443 }
 444 
 445 static void put_unused_buffer_head(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 446 {
 447         memset((void *) bh,0,sizeof(*bh));
 448         bh->b_next_free = unused_list;
 449         unused_list = bh;
 450 }
 451 
 452 static void get_more_buffer_heads(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 453 {
 454         unsigned long page;
 455         struct buffer_head * bh;
 456 
 457         if (unused_list)
 458                 return;
 459         page = get_free_page(GFP_KERNEL);
 460         if (!page)
 461                 return;
 462         bh = (struct buffer_head *) page;
 463         while ((unsigned long) (bh+1) <= page+4096) {
 464                 put_unused_buffer_head(bh);
 465                 bh++;
 466                 nr_buffer_heads++;
 467         }
 468 }
 469 
 470 static struct buffer_head * get_unused_buffer_head(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 471 {
 472         struct buffer_head * bh;
 473 
 474         get_more_buffer_heads();
 475         if (!unused_list)
 476                 return NULL;
 477         bh = unused_list;
 478         unused_list = bh->b_next_free;
 479         bh->b_next_free = NULL;
 480         bh->b_data = NULL;
 481         bh->b_size = 0;
 482         return bh;
 483 }
 484 
 485 /*
 486  * Try to increase the number of buffers available: the size argument
 487  * is used to determine what kind of buffers we want. Currently only
 488  * 1024-byte buffers are supported by the rest of the system, but I
 489  * think this will change eventually.
 490  */
 491 void grow_buffers(int size)
     /* [previous][next][first][last][top][bottom][index][help] */
 492 {
 493         unsigned long page;
 494         int i;
 495         struct buffer_head *bh, *tmp;
 496 
 497         if ((size & 511) || (size > 4096)) {
 498                 printk("grow_buffers: size = %d\n",size);
 499                 return;
 500         }
 501         page = get_free_page(GFP_BUFFER);
 502         if (!page)
 503                 return;
 504         tmp = NULL;
 505         i = 0;
 506         for (i = 0 ; i+size <= 4096 ; i += size) {
 507                 bh = get_unused_buffer_head();
 508                 if (!bh)
 509                         goto no_grow;
 510                 bh->b_this_page = tmp;
 511                 tmp = bh;
 512                 bh->b_data = (char * ) (page+i);
 513                 bh->b_size = size;
 514         }
 515         tmp = bh;
 516         while (1) {
 517                 if (free_list) {
 518                         tmp->b_next_free = free_list;
 519                         tmp->b_prev_free = free_list->b_prev_free;
 520                         free_list->b_prev_free->b_next_free = tmp;
 521                         free_list->b_prev_free = tmp;
 522                 } else {
 523                         tmp->b_prev_free = tmp;
 524                         tmp->b_next_free = tmp;
 525                 }
 526                 free_list = tmp;
 527                 ++nr_buffers;
 528                 if (tmp->b_this_page)
 529                         tmp = tmp->b_this_page;
 530                 else
 531                         break;
 532         }
 533         tmp->b_this_page = bh;
 534         return;
 535 /*
 536  * In case anything failed, we just free everything we got.
 537  */
 538 no_grow:
 539         bh = tmp;
 540         while (bh) {
 541                 tmp = bh;
 542                 bh = bh->b_this_page;
 543                 put_unused_buffer_head(tmp);
 544         }       
 545         free_page(page);
 546 }
 547 
 548 /*
 549  * try_to_free() checks if all the buffers on this particular page
 550  * are unused, and free's the page if so.
 551  */
 552 static int try_to_free(struct buffer_head * bh)
     /* [previous][next][first][last][top][bottom][index][help] */
 553 {
 554         unsigned long page;
 555         struct buffer_head * tmp, * p;
 556 
 557         tmp = bh;
 558         do {
 559                 if (!tmp)
 560                         return 0;
 561                 if (tmp->b_count || tmp->b_dirt || tmp->b_lock)
 562                         return 0;
 563                 tmp = tmp->b_this_page;
 564         } while (tmp != bh);
 565         page = (unsigned long) bh->b_data;
 566         page &= 0xfffff000;
 567         tmp = bh;
 568         do {
 569                 p = tmp;
 570                 tmp = tmp->b_this_page;
 571                 nr_buffers--;
 572                 remove_from_queues(p);
 573                 put_unused_buffer_head(p);
 574         } while (tmp != bh);
 575         free_page(page);
 576         return 1;
 577 }
 578 
 579 /*
 580  * Try to free up some pages by shrinking the buffer-cache
 581  *
 582  * Priority tells the routine how hard to try to shrink the
 583  * buffers: 3 means "don't bother too much", while a value
 584  * of 0 means "we'd better get some free pages now".
 585  */
 586 int shrink_buffers(unsigned int priority)
     /* [previous][next][first][last][top][bottom][index][help] */
 587 {
 588         struct buffer_head *bh;
 589         int i;
 590 
 591         if (priority < 2)
 592                 sync_buffers(0);
 593         bh = free_list;
 594         i = nr_buffers >> priority;
 595         for ( ; i-- > 0 ; bh = bh->b_next_free) {
 596                 if (bh->b_count || !bh->b_this_page)
 597                         continue;
 598                 if (bh->b_lock)
 599                         if (priority)
 600                                 continue;
 601                         else
 602                                 wait_on_buffer(bh);
 603                 if (bh->b_dirt) {
 604                         ll_rw_block(WRITEA,bh);
 605                         continue;
 606                 }
 607                 if (try_to_free(bh))
 608                         return 1;
 609         }
 610         return 0;
 611 }
 612 
 613 /*
 614  * This initializes the initial buffer free list.  nr_buffers is set
 615  * to one less the actual number of buffers, as a sop to backwards
 616  * compatibility --- the old code did this (I think unintentionally,
 617  * but I'm not sure), and programs in the ps package expect it.
 618  *                                      - TYT 8/30/92
 619  */
 620 void buffer_init(void)
     /* [previous][next][first][last][top][bottom][index][help] */
 621 {
 622         int i;
 623 
 624         for (i = 0 ; i < NR_HASH ; i++)
 625                 hash_table[i] = NULL;
 626         free_list = 0;
 627         grow_buffers(BLOCK_SIZE);
 628         if (!free_list)
 629                 panic("Unable to initialize buffer free list!");
 630         return;
 631 }

/* [previous][next][first][last][top][bottom][index][help] */