disksim_cachemem.c

disksim是一个非常优秀的磁盘仿真工具

/*
 * DiskSim Storage Subsystem Simulation Environment (Version 4.0)
 * Revision Authors: John Bucy, Greg Ganger
 * Contributors: John Griffin, Jiri Schindler, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 2001-2008.
 *
 * This software is being provided by the copyright holders under the
 * following license. By obtaining, using and/or copying this software,
 * you agree that you have read, understood, and will comply with the
 * following terms and conditions:
 *
 * Permission to reproduce, use, and prepare derivative works of this
 * software is granted provided the copyright and "No Warranty" statements
 * are included with all reproductions and derivative works and associated
 * documentation. This software may also be redistributed without charge
 * provided that the copyright and "No Warranty" statements are included
 * in all redistributions.
 *
 * NO WARRANTY. THIS SOFTWARE IS FURNISHED ON AN "AS IS" BASIS.
 * CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED AS TO THE MATTER INCLUDING, BUT NOT LIMITED
 * TO: WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY
 * OF RESULTS OR RESULTS OBTAINED FROM USE OF THIS SOFTWARE. CARNEGIE
 * MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT
 * TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.
 * COPYRIGHT HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE
 * OR DOCUMENTATION.
 *
 */



/*
 * DiskSim Storage Subsystem Simulation Environment (Version 2.0)
 * Revision Authors: Greg Ganger
 * Contributors: Ross Cohen, John Griffin, Steve Schlosser
 *
 * Copyright (c) of Carnegie Mellon University, 1999.
 *
 * Permission to reproduce, use, and prepare derivative works of
 * this software for internal use is granted provided the copyright
 * and "No Warranty" statements are included with all reproductions
 * and derivative works. This software may also be redistributed
 * without charge provided that the copyright and "No Warranty"
 * statements are included in all redistributions.
 *
 * NO WARRANTY. THIS SOFTWARE IS FURNISHED ON AN "AS IS" BASIS.
 * CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED AS TO THE MATTER INCLUDING, BUT NOT LIMITED
 * TO: WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY
 * OF RESULTS OR RESULTS OBTAINED FROM USE OF THIS SOFTWARE. CARNEGIE
 * MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT
 * TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT.
 */

/*
 * DiskSim Storage Subsystem Simulation Environment
 * Authors: Greg Ganger, Bruce Worthington, Yale Patt
 *
 * Copyright (C) 1993, 1995, 1997 The Regents of the University of Michigan 
 *
 * This software is being provided by the copyright holders under the
 * following license. By obtaining, using and/or copying this software,
 * you agree that you have read, understood, and will comply with the
 * following terms and conditions:
 *
 * Permission to use, copy, modify, distribute, and sell this software
 * and its documentation for any purpose and without fee or royalty is
 * hereby granted, provided that the full text of this NOTICE appears on
 * ALL copies of the software and documentation or portions thereof,
 * including modifications, that you make.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS," AND COPYRIGHT HOLDERS MAKE NO
 * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. BY WAY OF EXAMPLE,
 * BUT NOT LIMITATION, COPYRIGHT HOLDERS MAKE NO REPRESENTATIONS OR
 * WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY PARTICULAR PURPOSE OR
 * THAT THE USE OF THE SOFTWARE OR DOCUMENTATION WILL NOT INFRINGE ANY
 * THIRD PARTY PATENTS, COPYRIGHTS, TRADEMARKS OR OTHER RIGHTS. COPYRIGHT
 * HOLDERS WILL BEAR NO LIABILITY FOR ANY USE OF THIS SOFTWARE OR
 * DOCUMENTATION.
 *
 *  This software is provided AS IS, WITHOUT REPRESENTATION FROM THE
 * UNIVERSITY OF MICHIGAN AS TO ITS FITNESS FOR ANY PURPOSE, AND
 * WITHOUT WARRANTY BY THE UNIVERSITY OF MICHIGAN OF ANY KIND, EITHER
 * EXPRESSED OR IMPLIED, INCLUDING WITHOUT LIMITATION THE IMPLIED
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE REGENTS
 * OF THE UNIVERSITY OF MICHIGAN SHALL NOT BE LIABLE FOR ANY DAMAGES,
 * INCLUDING SPECIAL , INDIRECT, INCIDENTAL, OR CONSEQUENTIAL DAMAGES,
 * WITH RESPECT TO ANY CLAIM ARISING OUT OF OR IN CONNECTION WITH THE
 * USE OF OR IN CONNECTION WITH THE USE OF THE SOFTWARE, EVEN IF IT HAS
 * BEEN OR IS HEREAFTER ADVISED OF THE POSSIBILITY OF SUCH DAMAGES
 *
 * The names and trademarks of copyright holders or authors may NOT be
 * used in advertising or publicity pertaining to the software without
 * specific, written prior permission. Title to copyright in this software
 * and any associated documentation will at all times remain with copyright
 * holders.
 */

#define CACHE_MEMORY    1

#include "modules/modules.h"
#include "disksim_cachemem.h"


/* state components of atom */

#define CACHE_VALID		0x80000000
#define CACHE_DIRTY		0x40000000
#define CACHE_LOCKDOWN		0x20000000
#define CACHE_LOCKED		0x10000000
#define CACHE_ATOMFLUSH		0x08000000
#define CACHE_REALLOCATE_WRITE	0x04000000
#define CACHE_SEGNUM		0x000000FF		/* for S-LRU */

/* cache event flags */

#define CACHE_FLAG_WASBLOCKED		1
#define CACHE_FLAG_LINELOCKED_ALLOCATE	2

/* cache event types */

#define	CACHE_EVENT_IOREQ		0
#define CACHE_EVENT_ALLOCATE		1
#define CACHE_EVENT_READ		2
#define CACHE_EVENT_WRITE		3
#define CACHE_EVENT_SYNC		4
#define CACHE_EVENT_SYNCPART		5
#define CACHE_EVENT_READEXTRA		6
#define CACHE_EVENT_WRITEFILLEXTRA	7
#define CACHE_EVENT_IDLESYNC		8






/* internal prototypes */
static int cache_read_continue (struct cache_mem *cache, struct cache_mem_event *readdesc);
static int cache_write_continue (struct cache_mem *cache, struct cache_mem_event *writedesc);




int cachemem_get_maxreqsize (struct cache_if *c)
{
  struct cache_mem *cache = (struct cache_mem *)c;
  return cache->maxreqsize;
}


static void cache_empty_donefunc (void *doneparam, ioreq_event *req)
{
   addtoextraq((event *) req);
}


static int cache_concatok (void *concatokparam, int blkno1, int bcount1, int blkno2, int bcount2)
{
   struct cache_mem *cache = concatokparam;
   if ((cache->size) && (cache->maxscatgath != 0)) {
      int linesize = max(cache->linesize, 1);
      int lineno1 = blkno1 / linesize;
      int lineno2 = (blkno2 + bcount2 - 1) / linesize;
      int scatgathcnt = lineno2 - lineno1;
      if (scatgathcnt > cache->maxscatgath) {
	 return(0);
      }
   }
   return(1);
}


static void cache_waitfor_IO (struct cache_mem *cache, int waitcnt, struct cache_mem_event *cachereq, ioreq_event *ioacc)
{
   cachereq->next = cache->IOwaiters;
   cachereq->prev = NULL;
   if (cachereq->next) {
      cachereq->next->prev = cachereq;
   }
   cache->IOwaiters = cachereq;
/*
fprintf (outputfile, "IOwaiters %x, next %x, nextprev %x\n", cachereq, cachereq->next, ((cachereq->next) ? cachereq->next->prev : 0));
*/
   cachereq->accblkno = ioacc->blkno;
}


static void cache_insert_new_into_hash (struct cache_mem *cache, cache_atom *new)
{
   new->hash_next = cache->hash[(new->lbn & CACHE_HASHMASK)];
   cache->hash[(new->lbn & CACHE_HASHMASK)] = new;
   new->hash_prev = NULL;
   if (new->hash_next) {
      new->hash_next->hash_prev = new;
   }
}


static void cache_remove_entry_from_hash (struct cache_mem *cache, cache_atom *old)
{
	  /* Line must be in hash if to be removed! */
   ASSERT((old->hash_prev != NULL) || (old->hash_next != NULL) || (cache->hash[(old->lbn & CACHE_HASHMASK)] == old));

   if (old->hash_prev) {
      old->hash_prev->hash_next = old->hash_next;
   } else {
      cache->hash[(old->lbn & CACHE_HASHMASK)] = old->hash_next;
   }
   if (old->hash_next) {
      old->hash_next->hash_prev = old->hash_prev;
   }
   old->hash_next = NULL;
   old->hash_prev = NULL;
}


static int cache_count_dirty_atoms (struct cache_mem *cache)
{
   int i;
   int dirty = 0;

   for (i=0; i<CACHE_HASHMASK; i++) {
      cache_atom *tmp = cache->hash[i];
      while (tmp) {
         dirty += (tmp->state & CACHE_DIRTY) ? 1 : 0;
         tmp = tmp->hash_next;
      }
   }
   return(dirty);
}


static cache_atom * cache_find_atom (struct cache_mem *cache, int devno, int lbn)
{
   cache_atom *tmp = cache->hash[(lbn & CACHE_HASHMASK)];
/*
fprintf (outputfile, "Entered cache_find_atom: devno %d, lbn %d, CACHE_HASHMASK %x, setno %d\n", devno, lbn, CACHE_HASHMASK, (lbn & CACHE_HASHMASK));
*/
   while ((tmp) && ((tmp->lbn != lbn) || (tmp->devno != devno))) {
      tmp = tmp->hash_next;
   }
   return(tmp);
}


#if 0
static void cache_remove_lbn_from_hash (struct cache_mem *cache, int devno, int lbn)
{
   cache_atom *tmp;

   if ((tmp = cache_find_atom(cache, devno, lbn))) {
      cache_remove_entry_from_hash(cache, tmp);
   }
}
#endif


#if 0
static void cache_check_for_residence (struct cache_mem *cache, int devno, int lbn, int size, int *miss)
{
   cache_atom *line = NULL;
   int i;

   for (i=0; i<size; i++) {
      if (line == NULL) {
         line = cache_find_atom(cache, devno, (lbn + i));
      }
      if ((line == NULL) || ((line->state & CACHE_VALID) == 0)) {
         miss[(i & INV_BITS_PER_INT_MASK)] |= 1 << (i & BITS_PER_INT_MASK);
      }
      if (line) {
         line = line->line_next;
      }
   }
}
#endif


#if 0
/* Use for setting VALID, LOCKDOWN, DIRTY and other atom state bits */

static void cache_set_state (struct cache_mem *cache, int devno, int lbn, int size, int mask)
{
   cache_atom *line = NULL;
   int i;

   for (i=0; i<size; i++) {
      if (line == NULL) {
         line = cache_find_atom(cache, devno, (lbn + i));
      }
	       /* Can't change state of unallocated cache atoms */
      ASSERT(line != NULL);

      line->state |= mask;
      line = line->line_next;
   }
}
#endif


#if 0
/* Use for clearing VALID, LOCKDOWN, DIRTY and other atom state bits */

static void cache_reset_state (struct cache_mem *cache, int devno, int lbn, int size, int mask)
{
   cache_atom *line = NULL;
   int i;

   for (i=0; i<size; i++) {
      if (line == NULL) {
         line = cache_find_atom(cache, devno, (lbn + i));
      }
	       /* Can't change state of unallocated cache atoms */
      ASSERT(line != NULL);

      line->state &= ~mask;
      line = line->line_next;
   }
}
#endif


static void cache_add_to_lrulist (cache_mapentry *map, 
				  cache_atom *line, 
				  int segnum)
{
   cache_atom **head;

   if (segnum == CACHE_SEGNUM) {
      head = &map->freelist;
   } else {
      head = &map->lru[segnum];
      map->numactive[segnum]++;
   }
   line->state |= segnum;
   if (*head) {
      line->lru_next = *head;
      line->lru_prev = (*head)->lru_prev;
      (*head)->lru_prev = line;
      line->lru_prev->lru_next = line;
   } else {
      line->lru_next = line;
      line->lru_prev = line;
      *head = line;
   }
}


static void cache_remove_from_lrulist (cache_mapentry *map, cache_atom *line, int segnum)
{
   cache_atom **head;

   if (segnum == CACHE_SEGNUM) {
      head = &map->freelist;
   } else {
      head = &map->lru[segnum];
      map->numactive[segnum]--;
   }
   if (line->lru_next != line) {
      line->lru_prev->lru_next = line->lru_next;
      line->lru_next->lru_prev = line->lru_prev;
      if (*head == line) {
         *head = line->lru_next;
      }
   } else {
      *head = NULL;
   }
   line->state &= ~CACHE_SEGNUM;
   line->lru_next = NULL;
   line->lru_prev = NULL;
}


/* Reset state of LRU list given access to line */

static void cache_access (struct cache_mem *cache, cache_atom *line)
{
   int set;
   int segnum = 0;

   if (cache->replacepolicy != CACHE_REPLACE_SLRU) {
      return;
   }
   while (line->line_prev) {
      line = line->line_prev;
   }
   set = (cache->mapmask) ? (line->lbn % cache->mapmask) : 0;
   if (line->lru_next) {
      segnum = line->state & CACHE_SEGNUM;
      cache_remove_from_lrulist(&cache->map[set], line, segnum);
      if (segnum != (cache->numsegs-1)) {
         segnum = (segnum + 1) & CACHE_SEGNUM;
      }
   }
   cache_add_to_lrulist(&cache->map[set], line, segnum);
   while ((segnum) && 
	  (cache->map[set].numactive[segnum] == 
	   cache->map[set].maxactive[segnum])) 
     {
       line = cache->map[set].lru[segnum];
       cache_remove_from_lrulist(&cache->map[set], line, segnum);
       segnum--;
       cache_add_to_lrulist(&cache->map[set], line, segnum);
     }
}


static void cache_replace_waitforline (struct cache_mem *cache, struct cache_mem_event *allocdesc)
{
   // fprintf (outputfile, "entered cache_replace_waitforline: linelocked %d\n", (allocdesc->flags & CACHE_FLAG_LINELOCKED_ALLOCATE));

   if (cache->linewaiters) {
      allocdesc->next = cache->linewaiters->next;
      cache->linewaiters->next = allocdesc;