cache.c

一个简单的操作系统minix的核心代码

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
				src/fs/cache.c	 	 
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

21000	/* The file system maintains a buffer cache to reduce the number of disk
21001	 * accesses needed.  Whenever a read or write to the disk is done, a check is
21002	 * first made to see if the block is in the cache.  This file manages the
21003	 * cache.
21004	 *
21005	 * The entry points into this file are:
21006	 *   get_block:   request to fetch a block for reading or writing from cache
21007	 *   put_block:   return a block previously requested with get_block
21008	 *   alloc_zone:  allocate a new zone (to increase the length of a file)
21009	 *   free_zone:   release a zone (when a file is removed)
21010	 *   rw_block:    read or write a block from the disk itself
21011	 *   invalidate:  remove all the cache blocks on some device
21012	 */
21013	
21014	#include "fs.h"
21015	#include <minix/com.h>
21016	#include <minix/boot.h>
21017	#include "buf.h"
21018	#include "file.h"
21019	#include "fproc.h"
21020	#include "super.h"
21021	
21022	FORWARD _PROTOTYPE( void rm_lru, (struct buf *bp) );
21023	
21024	/*===========================================================================*
21025	 *                              get_block                                    *
21026	 *===========================================================================*/
21027	PUBLIC struct buf *get_block(dev, block, only_search)
21028	register dev_t dev;             /* on which device is the block? */
21029	register block_t block;         /* which block is wanted? */
21030	int only_search;                /* if NO_READ, don't read, else act normal */
21031	{
21032	/* Check to see if the requested block is in the block cache.  If so, return
21033	 * a pointer to it.  If not, evict some other block and fetch it (unless
21034	 * 'only_search' is 1).  All the blocks in the cache that are not in use
21035	 * are linked together in a chain, with 'front' pointing to the least recently
21036	 * used block and 'rear' to the most recently used block.  If 'only_search' is
21037	 * 1, the block being requested will be overwritten in its entirety, so it is
21038	 * only necessary to see if it is in the cache; if it is not, any free buffer
21039	 * will do.  It is not necessary to actually read the block in from disk.
21040	 * If 'only_search' is PREFETCH, the block need not be read from the disk,
21041	 * and the device is not to be marked on the block, so callers can tell if
21042	 * the block returned is valid.
21043	 * In addition to the LRU chain, there is also a hash chain to link together
21044	 * blocks whose block numbers end with the same bit strings, for fast lookup.
21045	 */
21046	
21047	  int b;
21048	  register struct buf *bp, *prev_ptr;
21049	
21050	  /* Search the hash chain for (dev, block). Do_read() can use 
21051	   * get_block(NO_DEV ...) to get an unnamed block to fill with zeros when
21052	   * someone wants to read from a hole in a file, in which case this search
21053	   * is skipped
21054	   */
21055	  if (dev != NO_DEV) {
21056	        b = (int) block & HASH_MASK;
21057	        bp = buf_hash[b];
21058	        while (bp != NIL_BUF) {
21059	                if (bp->b_blocknr == block && bp->b_dev == dev) {
21060	                        /* Block needed has been found. */
21061	                        if (bp->b_count == 0) rm_lru(bp);
21062	                        bp->b_count++;  /* record that block is in use */
21063	                        return(bp);
21064	                } else {
21065	                        /* This block is not the one sought. */
21066	                        bp = bp->b_hash; /* move to next block on hash chain */
21067	                }
21068	        }
21069	  }
21070	
21071	  /* Desired block is not on available chain.  Take oldest block ('front'). */
21072	  if ((bp = front) == NIL_BUF) panic("all buffers in use", NR_BUFS);
21073	  rm_lru(bp);
21074	
21075	  /* Remove the block that was just taken from its hash chain. */
21076	  b = (int) bp->b_blocknr & HASH_MASK;
21077	  prev_ptr = buf_hash[b];
21078	  if (prev_ptr == bp) {
21079	        buf_hash[b] = bp->b_hash;
21080	  } else {
21081	        /* The block just taken is not on the front of its hash chain. */
21082	        while (prev_ptr->b_hash != NIL_BUF)
21083	                if (prev_ptr->b_hash == bp) {
21084	                        prev_ptr->b_hash = bp->b_hash;  /* found it */
21085	                        break;
21086	                } else {
21087	                        prev_ptr = prev_ptr->b_hash;    /* keep looking */
21088	                }
21089	  }
21090	
21091	  /* If the block taken is dirty, make it clean by writing it to the disk.
21092	   * Avoid hysteresis by flushing all other dirty blocks for the same device.
21093	   */
21094	  if (bp->b_dev != NO_DEV) {
21095	        if (bp->b_dirt == DIRTY) flushall(bp->b_dev);
21096	  }
21097	
21098	  /* Fill in block's parameters and add it to the hash chain where it goes. */
21099	  bp->b_dev = dev;              /* fill in device number */
21100	  bp->b_blocknr = block;        /* fill in block number */
21101	  bp->b_count++;                /* record that block is being used */
21102	  b = (int) bp->b_blocknr & HASH_MASK;
21103	  bp->b_hash = buf_hash[b];
21104	  buf_hash[b] = bp;             /* add to hash list */
21105	
21106	  /* Go get the requested block unless searching or prefetching. */
21107	  if (dev != NO_DEV) {
21108	        if (only_search == PREFETCH) bp->b_dev = NO_DEV;
21109	        else
21110	        if (only_search == NORMAL) rw_block(bp, READING);
21111	  }
21112	  return(bp);                   /* return the newly acquired block */
21113	}
	
	
21116	/*===========================================================================*
21117	 *                              put_block                                    *
21118	 *===========================================================================*/
21119	PUBLIC void put_block(bp, block_type)
21120	register struct buf *bp;        /* pointer to the buffer to be released */
21121	int block_type;                 /* INODE_BLOCK, DIRECTORY_BLOCK, or whatever */
21122	{
21123	/* Return a block to the list of available blocks.   Depending on 'block_type'
21124	 * it may be put on the front or rear of the LRU chain.  Blocks that are
21125	 * expected to be needed again shortly (e.g., partially full data blocks)
21126	 * go on the rear; blocks that are unlikely to be needed again shortly
21127	 * (e.g., full data blocks) go on the front.  Blocks whose loss can hurt
21128	 * the integrity of the file system (e.g., inode blocks) are written to
21129	 * disk immediately if they are dirty.
21130	 */
21131	
21132	  if (bp == NIL_BUF) return;    /* it is easier to check here than in caller */
21133	
21134	  bp->b_count--;                /* there is one use fewer now */
21135	  if (bp->b_count != 0) return; /* block is still in use */
21136	
21137	  bufs_in_use--;                /* one fewer block buffers in use */
21138	
21139	  /* Put this block back on the LRU chain.  If the ONE_SHOT bit is set in
21140	   * 'block_type', the block is not likely to be needed again shortly, so put
21141	   * it on the front of the LRU chain where it will be the first one to be
21142	   * taken when a free buffer is needed later.
21143	   */
21144	  if (block_type & ONE_SHOT) {
21145	        /* Block probably won't be needed quickly. Put it on front of chain.
21146	         * It will be the next block to be evicted from the cache.
21147	         */
21148	        bp->b_prev = NIL_BUF;
21149	        bp->b_next = front;
21150	        if (front == NIL_BUF)
21151	                rear = bp;      /* LRU chain was empty */
21152	        else
21153	                front->b_prev = bp;
21154	        front = bp;
21155	  } else {
21156	        /* Block probably will be needed quickly.  Put it on rear of chain.
21157	         * It will not be evicted from the cache for a long time.
21158	         */
21159	        bp->b_prev = rear;
21160	        bp->b_next = NIL_BUF;
21161	        if (rear == NIL_BUF)
21162	                front = bp;
21163	        else
21164	                rear->b_next = bp;
21165	        rear = bp;
21166	  }
21167	
21168	  /* Some blocks are so important (e.g., inodes, indirect blocks) that they
21169	   * should be written to the disk immediately to avoid messing up the file
21170	   * system in the event of a crash.
21171	   */
21172	  if ((block_type & WRITE_IMMED) && bp->b_dirt==DIRTY && bp->b_dev != NO_DEV)
21173	        rw_block(bp, WRITING);
21174	}
	
	
21177	/*===========================================================================*
21178	 *                              alloc_zone                                   *
21179	 *===========================================================================*/
21180	PUBLIC zone_t alloc_zone(dev, z)
21181	dev_t dev;                      /* device where zone wanted */
21182	zone_t z;                       /* try to allocate new zone near this one */
21183	{
21184	/* Allocate a new zone on the indicated device and return its number. */
21185	
21186	  int major, minor;
21187	  bit_t b, bit;
21188	  struct super_block *sp;
21189	
21190	  /* Note that the routine alloc_bit() returns 1 for the lowest possible
21191	   * zone, which corresponds to sp->s_firstdatazone.  To convert a value
21192	   * between the bit number, 'b', used by alloc_bit() and the zone number, 'z',
21193	   * stored in the inode, use the formula:
21194	   *     z = b + sp->s_firstdatazone - 1
21195	   * Alloc_bit() never returns 0, since this is used for NO_BIT (failure).
21196	   */
21197	  sp = get_super(dev);          /* find the super_block for this device */
21198	
21199	  /* If z is 0, skip initial part of the map known to be fully in use. */
21200	  if (z == sp->s_firstdatazone) {
21201	        bit = sp->s_zsearch;