Logo Search packages:      
Sourcecode: hfsprogs version File versions  Download package

cache.c

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 *
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sys/uio.h>
#include <unistd.h>
#include <string.h>

#include "cache.h"


#define CACHE_DEBUG  0

/*
 * CacheAllocBlock
 *
 *  Allocate an unused cache block.
 */
void *CacheAllocBlock (Cache_t *cache);

/*
 * CacheFreeBlock
 *
 *  Release an active cache block.
 */
static int 
CacheFreeBlock( Cache_t *cache, Tag_t *tag );

/*
 * CacheLookup
 *
 *  Obtain a cache block. If one already exists, it is returned. Otherwise a
 *  new one is created and inserted into the cache.
 */
int CacheLookup (Cache_t *cache, uint64_t off, Tag_t **tag);

/*
 * CacheRawRead
 *
 *  Perform a direct read on the file.
 */
int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf);

/*
 * CacheRawWrite
 *
 *  Perform a direct write on the file.
 */
int CacheRawWrite (Cache_t *cache, uint64_t off, uint32_t len, void *buf);



/*
 * LRUInit
 *
 *  Initializes the LRU data structures.
 */
static int LRUInit (LRU_t *lru);

/*
 * LRUDestroy
 *
 *  Shutdown the LRU.
 *
 *  NOTE: This is typically a no-op, since the cache manager will be clearing
 *        all cache tags.
 */
static int LRUDestroy (LRU_t *lru);

/*
 * LRUHit
 *
 *  Registers data activity on the given node. If the node is already in the
 *  LRU, it is moved to the front. Otherwise, it is inserted at the front.
 *
 *  NOTE: If the node is not in the LRU, we assume that its pointers are NULL.
 */
static int LRUHit (LRU_t *lru, LRUNode_t *node, int age);

/*
 * LRUEvict
 *
 *  Chooses a buffer to release.
 *
 *  TODO: Under extreme conditions, it shoud be possible to release the buffer
 *        of an actively referenced cache buffer, leaving the tag behind as a
 *        placeholder. This would be required for implementing 2Q-LRU
 *        replacement.
 */
static int LRUEvict (LRU_t *lru, LRUNode_t *node);



/*
 * CacheInit
 *
 *  Initializes the cache for use.
 */
int CacheInit (Cache_t *cache, int fdRead, int fdWrite, uint32_t devBlockSize,
               uint32_t cacheBlockSize, uint32_t cacheSize, uint32_t hashSize)
{
      void **           temp;
      uint32_t    i;
      Buf_t *           buf;
      
      memset (cache, 0x00, sizeof (Cache_t));

      cache->FD_R = fdRead;
      cache->FD_W = fdWrite;
      cache->DevBlockSize = devBlockSize;
      /* CacheFlush requires cleared cache->Hash  */
      cache->Hash = (Tag_t **) calloc( 1, (sizeof (Tag_t *) * hashSize) );
      cache->HashSize = hashSize;
      cache->BlockSize = cacheBlockSize;

      /* Allocate the cache memory */
      cache->FreeHead = mmap (NULL,
                              cacheSize * cacheBlockSize,
                              PROT_READ | PROT_WRITE,
                              MAP_ANON | MAP_PRIVATE,
                              -1,
                              0);
      if (cache->FreeHead == NULL) return (ENOMEM);

      /* Initialize the cache memory free list */
      temp = cache->FreeHead;
      for (i = 0; i < cacheSize - 1; i++) {
            *temp = ((char *)temp + cacheBlockSize);
            temp  = (void **)((char *)temp + cacheBlockSize);
      }
      *temp = NULL;
      cache->FreeSize = cacheSize;

      buf = (Buf_t *)malloc(sizeof(Buf_t) * MAXBUFS);
      if (buf == NULL) return (ENOMEM);

      memset (&buf[0], 0x00, sizeof (Buf_t) * MAXBUFS);
      for (i = 1 ; i < MAXBUFS ; i++) {
            (&buf[i-1])->Next = &buf[i];
      }
      cache->FreeBufs = &buf[0];

#if CACHE_DEBUG
      printf( "%s - cacheSize %d cacheBlockSize %d hashSize %d \n", 
                  __FUNCTION__, cacheSize, cacheBlockSize, hashSize );
      printf( "%s - cache memory %d \n", __FUNCTION__, (cacheSize * cacheBlockSize) );
#endif  

      return (LRUInit (&cache->LRU));
}


/*
 * CacheDestroy
 * 
 *  Shutdown the cache.
 */
int CacheDestroy (Cache_t *cache)
{
      CacheFlush( cache );

#if CACHE_DEBUG
      /* Print cache report */
      printf ("Cache Report:\n");
      printf ("\tRead Requests:  %d\n", cache->ReqRead);
      printf ("\tWrite Requests: %d\n", cache->ReqWrite);
      printf ("\tDisk Reads:     %d\n", cache->DiskRead);
      printf ("\tDisk Writes:    %d\n", cache->DiskWrite);
      printf ("\tSpans:          %d\n", cache->Span);
#endif      
      /* Shutdown the LRU */
      LRUDestroy (&cache->LRU);
      
      /* I'm lazy, I'll come back to it :P */
      return (EOK);
}

/*
 * CacheRead
 *
 *  Reads a range of bytes from the cache, returning a pointer to a buffer
 *  containing the requested bytes.
 *
 *  NOTE: The returned buffer may directly refer to a cache block, or an
 *        anonymous buffer. Do not make any assumptions about the nature of
 *        the returned buffer, except that it is contiguous.
 */
int CacheRead (Cache_t *cache, uint64_t off, uint32_t len, Buf_t **bufp)
{
      Tag_t *           tag;
      Buf_t *           searchBuf;
      Buf_t *           buf;
      uint32_t    coff = (off % cache->BlockSize);
      uint64_t    cblk = (off - coff);
      int               error;

      /* Check for conflicts with other bufs */
      searchBuf = cache->ActiveBufs;
      while (searchBuf != NULL) {
            if ((searchBuf->Offset >= off) && (searchBuf->Offset < off + len)) {
#if CACHE_DEBUG
                  printf ("ERROR: CacheRead: Deadlock\n");
#endif
                  return (EDEADLK);
            }
            
            searchBuf = searchBuf->Next;
      }
      
      /* get a free buffer */
      if ((buf = cache->FreeBufs) == NULL) {
#if CACHE_DEBUG
            printf ("ERROR: CacheRead: no more bufs!\n");
#endif
            return (ENOBUFS);
      }
      cache->FreeBufs = buf->Next; 
      *bufp = buf;

      /* Clear the buf structure */
      buf->Next   = NULL;
      buf->Prev   = NULL;
      buf->Flags  = 0;
      buf->Offset = off;
      buf->Length = len;
      buf->Buffer = NULL;
      
      /* If this is unaligned or spans multiple cache blocks */
      if ((cblk / cache->BlockSize) != ((off + len - 1) / cache->BlockSize)) {
            buf->Flags |= BUF_SPAN;
      }
      /* Fetch the first cache block */
      error = CacheLookup (cache, cblk, &tag);
      if (error != EOK) {
#if CACHE_DEBUG
            printf ("ERROR: CacheRead: CacheLookup error\n");
#endif
            return (error);
      }

      /* If we live nicely inside a cache block */
      if (!(buf->Flags & BUF_SPAN)) {
            /* Offset the buffer into the cache block */
            buf->Buffer = tag->Buffer + coff;

            /* Bump the cache block's reference count */
            tag->Refs++;
            
            /* Kick the node into the right queue */
            LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);

      /* Otherwise, things get ugly */
      } else {
            uint32_t    boff; /* Offset into the buffer */
            uint32_t    blen; /* Space to fill in the buffer */
            uint32_t    temp;

            /* Allocate a temp buffer */
            buf->Buffer = (void *)malloc (len);
            if (buf->Buffer == NULL) {
#if CACHE_DEBUG
                  printf ("ERROR: CacheRead: No Memory\n");
#endif
                  return (ENOMEM);
            }

            /* Blit the first chunk into the buffer */
            boff = cache->BlockSize - coff;
            blen = len - boff;
            memcpy (buf->Buffer, tag->Buffer + coff, boff);
            
            /* Bump the cache block's reference count */
            tag->Refs++;

            /* Kick the node into the right queue */
            LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);

            /* Next cache block */
            cblk += cache->BlockSize;
            
            /* Read data a cache block at a time */
            while (blen) {
                  /* Fetch the next cache block */
                  error = CacheLookup (cache, cblk, &tag);
                  if (error != EOK) {
                        /* Free the allocated buffer */
                        free (buf->Buffer);
                        buf->Buffer = NULL;

                        /* Release all the held tags */
                        cblk -= cache->BlockSize;
                        while (!boff) {
                              if (CacheLookup (cache, cblk, &tag) != EOK) {
                                    fprintf (stderr, "CacheRead: Unrecoverable error\n");
                                    exit (-1);
                              }
                              tag->Refs--;
                              
                              /* Kick the node into the right queue */
                              LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);
                        }

                        return (error);
                  }

                  /* Blit the cache block into the buffer */
                  temp = ((blen > cache->BlockSize) ? cache->BlockSize : blen);
                  memcpy (buf->Buffer + boff,
                          tag->Buffer,
                              temp);

                  /* Update counters */
                  boff += temp;
                  blen -= temp;
                  tag->Refs++;

                  /* Kick the node into the right queue */
                  LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);
            }

            /* Count the spanned access */
            cache->Span++;
      }

      /* Attach to head of active buffers list */
      if (cache->ActiveBufs != NULL) {
            buf->Next = cache->ActiveBufs;
            buf->Prev = NULL;

            cache->ActiveBufs->Prev = buf;

      } else {
            cache->ActiveBufs = buf;
      }

      /* Update counters */
      cache->ReqRead++;
      return (EOK);
}

/* 
 * CacheWrite
 *
 *  Writes a buffer through the cache.
 */
int CacheWrite ( Cache_t *cache, Buf_t *buf, int age, uint32_t writeOptions )
{
      Tag_t *           tag;
      uint32_t    coff = (buf->Offset % cache->BlockSize);
      uint64_t    cblk = (buf->Offset - coff);
      int               error;

      /* Fetch the first cache block */
      error = CacheLookup (cache, cblk, &tag);
      if (error != EOK) return (error);
      
      /* If the buffer was a direct reference */
      if (!(buf->Flags & BUF_SPAN)) {
            /* Commit the dirty block */
            if ( (writeOptions & kLazyWrite) != 0 ) 
            {
                  /* flag this for lazy write */
                  tag->Flags |= kLazyWrite;
            }
            else
            {
                  error = CacheRawWrite (cache,
                                                   tag->Offset,
                                                   cache->BlockSize,
                                                   tag->Buffer);
                  if (error != EOK) return (error);
            }
            
            /* Release the reference */
            tag->Refs--;

            /* Kick the node into the right queue */
            LRUHit (&cache->LRU, (LRUNode_t *)tag, age);

      /* Otherwise, we do the ugly thing again */
      } else {
            uint32_t    boff; /* Offset into the buffer */
            uint32_t    blen; /* Space to fill in the buffer */
            uint32_t    temp;

            /* Blit the first chunk back into the cache */
            boff = cache->BlockSize - coff;
            blen = buf->Length - boff;
            memcpy (tag->Buffer + coff, buf->Buffer, boff);
            
            /* Commit the dirty block */
            if ( (writeOptions & kLazyWrite) != 0 ) 
            {
                  /* flag this for lazy write */
                  tag->Flags |= kLazyWrite;
            }
            else
            {
                  error = CacheRawWrite (cache,
                                                   tag->Offset,
                                                   cache->BlockSize,
                                                   tag->Buffer);
                  if (error != EOK) return (error);
            }
            
            /* Release the cache block reference */
            tag->Refs--;

            /* Kick the node into the right queue */
            LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
                  
            /* Next cache block */
            cblk += cache->BlockSize;
            
            /* Write data a cache block at a time */
            while (blen) {
                  /* Fetch the next cache block */
                  error = CacheLookup (cache, cblk, &tag);
                  /* We must go through with the write regardless */

                  /* Blit the next buffer chunk back into the cache */
                  temp = ((blen > cache->BlockSize) ? cache->BlockSize : blen);
                  memcpy (tag->Buffer,
                              buf->Buffer + boff,
                              temp);

                  /* Commit the dirty block */
                  if ( (writeOptions & kLazyWrite) != 0 ) 
                  {
                        /* flag this for lazy write */
                        tag->Flags |= kLazyWrite;
                  }
                  else
                  {
                        error = CacheRawWrite (cache,
                                                         tag->Offset,
                                                         cache->BlockSize,
                                                         tag->Buffer);
                        if (error != EOK) return (error);
                  }

                  /* Update counters */
                  boff += temp;
                  blen -= temp;
                  tag->Refs--;

                  /* Kick the node into the right queue */
                  LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
            }

            /* Release the anonymous buffer */
            free (buf->Buffer);
      }

      /* Detach the buffer */
      if (buf->Next != NULL)
            buf->Next->Prev = buf->Prev;
      if (buf->Prev != NULL)
            buf->Prev->Next = buf->Next;
      if (cache->ActiveBufs == buf)
            cache->ActiveBufs = buf->Next;

      /* Clear the buffer and put it back on free list */
      memset (buf, 0x00, sizeof (Buf_t));
      buf->Next = cache->FreeBufs; 
      cache->FreeBufs = buf;        

      /* Update counters */
      cache->ReqWrite++;

      return (EOK);
}

/*
 * CacheRelease
 *
 *  Releases a clean buffer.
 *
 *  NOTE: We don't verify whether it's dirty or not.
 */
int CacheRelease (Cache_t *cache, Buf_t *buf, int age)
{
      Tag_t *           tag;
      uint32_t    coff = (buf->Offset % cache->BlockSize);
      uint64_t    cblk = (buf->Offset - coff);
      int               error;

      /* Fetch the first cache block */
      error = CacheLookup (cache, cblk, &tag);
      if (error != EOK) {
#if CACHE_DEBUG
            printf ("ERROR: CacheRelease: CacheLookup error\n");
#endif
            return (error);
      }
      
      /* If the buffer was a direct reference */
      if (!(buf->Flags & BUF_SPAN)) {
            /* Release the reference */
            tag->Refs--;

            /* Kick the node into the right queue */
            LRUHit (&cache->LRU, (LRUNode_t *)tag, age);

      /* Otherwise, we do the ugly thing again */
      } else {
            uint32_t    blen; /* Space to fill in the buffer */

            /* Blit the first chunk back into the cache */
            blen = buf->Length - cache->BlockSize + coff;
            
            /* Release the cache block reference */
            tag->Refs--;

            /* Kick the node into the right queue */
            LRUHit (&cache->LRU, (LRUNode_t *)tag, age);

            /* Next cache block */
            cblk += cache->BlockSize;
            
            /* Release cache blocks one at a time */
            while (blen) {
                  /* Fetch the next cache block */
                  error = CacheLookup (cache, cblk, &tag);
                  /* We must go through with the write regardless */

                  /* Update counters */
                  blen -= ((blen > cache->BlockSize) ? cache->BlockSize : blen);
                  tag->Refs--;

                  /* Kick the node into the right queue */
                  LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
            }

            /* Release the anonymous buffer */
            free (buf->Buffer);
      }

      /* Detach the buffer */
      if (buf->Next != NULL)
            buf->Next->Prev = buf->Prev;
      if (buf->Prev != NULL)
            buf->Prev->Next = buf->Next;
      if (cache->ActiveBufs == buf)
            cache->ActiveBufs = buf->Next;

      /* Clear the buffer and put it back on free list */
      memset (buf, 0x00, sizeof (Buf_t));
      buf->Next = cache->FreeBufs; 
      cache->FreeBufs = buf;        

      return (EOK);
}

/*
 * CacheRemove
 *
 *  Disposes of a particular buffer.
 */
int CacheRemove (Cache_t *cache, Tag_t *tag)
{
      int               error;

      /* Make sure it's not busy */
      if (tag->Refs) return (EBUSY);
      
      /* Detach the tag */
      if (tag->Next != NULL)
            tag->Next->Prev = tag->Prev;
      if (tag->Prev != NULL)
            tag->Prev->Next = tag->Next;
      else
            cache->Hash[tag->Offset % cache->HashSize] = tag->Next;
      
      /* Make sure the head node doesn't have a back pointer */
      if ((cache->Hash[tag->Offset % cache->HashSize] != NULL) &&
          (cache->Hash[tag->Offset % cache->HashSize]->Prev != NULL)) {
#if CACHE_DEBUG
            printf ("ERROR: CacheRemove: Corrupt hash chain\n");
#endif
      }
      
      /* Release it's buffer (if it has one) */
      if (tag->Buffer != NULL)
      {
            error = CacheFreeBlock (cache, tag);
            if ( EOK != error )
                  return( error );
      }

      /* Zero the tag (for easy debugging) */
      memset (tag, 0x00, sizeof (Tag_t));

      /* Free the tag */
      free (tag);

      return (EOK);
}

/*
 * CacheEvict
 *
 *  Only dispose of the buffer, leave the tag intact.
 */
int CacheEvict (Cache_t *cache, Tag_t *tag)
{
      int               error;

      /* Make sure it's not busy */
      if (tag->Refs) return (EBUSY);

      /* Release the buffer */
      if (tag->Buffer != NULL)
      {
            error = CacheFreeBlock (cache, tag);
            if ( EOK != error )
                  return( error );
      }
      tag->Buffer = NULL;

      return (EOK);
}

/*
 * CacheAllocBlock
 *
 *  Allocate an unused cache block.
 */
void *CacheAllocBlock (Cache_t *cache)
{
      void *      temp;
      
      if (cache->FreeHead == NULL)
            return (NULL);
      if (cache->FreeSize == 0)
            return (NULL);

      temp = cache->FreeHead;
      cache->FreeHead = *((void **)cache->FreeHead);
      cache->FreeSize--;

      return (temp);
}

/*
 * CacheFreeBlock
 *
 *  Release an active cache block.
 */
static int 
CacheFreeBlock( Cache_t *cache, Tag_t *tag )
{
      int               error;
      
      if ( (tag->Flags & kLazyWrite) != 0 )
      {
            /* this cache block has been marked for lazy write - do it now */
            error = CacheRawWrite( cache,
                                             tag->Offset,
                                             cache->BlockSize,
                                             tag->Buffer );
            if ( EOK != error ) 
            {
#if CACHE_DEBUG
                  printf( "%s - CacheRawWrite failed with error %d \n", __FUNCTION__, error );
#endif 
                  return ( error );
            }
            tag->Flags &= ~kLazyWrite;
      }

      *((void **)tag->Buffer) = cache->FreeHead;
      cache->FreeHead = (void **)tag->Buffer;
      cache->FreeSize++;
      
      return( EOK );
}


/*
 * CacheFlush
 *
 *  Write out any blocks that are marked for lazy write.
 */

int 
CacheFlush( Cache_t *cache )
{
      int               error;
      int               i;
      Tag_t *           myTagPtr;
      
      for ( i = 0; i < cache->HashSize; i++ )
      {
            myTagPtr = cache->Hash[ i ];
            
            while ( NULL != myTagPtr )
            {
                  if ( (myTagPtr->Flags & kLazyWrite) != 0 )
                  {
                        /* this cache block has been marked for lazy write - do it now */
                        error = CacheRawWrite( cache,
                                                         myTagPtr->Offset,
                                                         cache->BlockSize,
                                                         myTagPtr->Buffer );
                        if ( EOK != error ) 
                        {
#if CACHE_DEBUG
                              printf( "%s - CacheRawWrite failed with error %d \n", __FUNCTION__, error );
#endif 
                              return( error );
                        }
                        myTagPtr->Flags &= ~kLazyWrite;
                  }
                  myTagPtr = myTagPtr->Next; 
            } /* while */
      } /* for */

      return( EOK );
            
} /* CacheFlush */


/*
 * RangeIntersect
 *
 * Return true if the two given ranges intersect.
 *
 */
static int
RangeIntersect(uint64_t start1, uint64_t len1, uint64_t start2, uint64_t len2)
{
      uint64_t end1 = start1 + len1 - 1;
      uint64_t end2 = start2 + len2 - 1;
      
      if (end1 < start2 || start1 > end2)
            return 0;
      else
            return 1;
}


/*
 * CacheFlushRange
 *
 * Flush, and optionally remove, all cache blocks that intersect
 * a given range.
 */
int
CacheFlushRange( Cache_t *cache, uint64_t start, uint64_t len, int remove)
{
      int error;
      int i;
      Tag_t *currentTag, *nextTag;
      
      for ( i = 0; i < cache->HashSize; i++ )
      {
            currentTag = cache->Hash[ i ];
            
            while ( NULL != currentTag )
            {
                  /* Keep track of the next block, in case we remove the current block */
                  nextTag = currentTag->Next;

                  if ( currentTag->Flags & kLazyWrite &&
                         RangeIntersect(currentTag->Offset, cache->BlockSize, start, len))
                  {
                        error = CacheRawWrite( cache,
                                                         currentTag->Offset,
                                                         cache->BlockSize,
                                                         currentTag->Buffer );
                        if ( EOK != error )
                        {
#if CACHE_DEBUG
                              printf( "%s - CacheRawWrite failed with error %d \n", __FUNCTION__, error );
#endif 
                              return error;
                        }
                        currentTag->Flags &= ~kLazyWrite;

                        if ( remove )
                              CacheRemove( cache, currentTag );
                  }
                  
                  currentTag = nextTag;
            } /* while */
      } /* for */
      
      return EOK;
} /* CacheFlushRange */


/*
 * CacheLookup
 *
 *  Obtain a cache block. If one already exists, it is returned. Otherwise a
 *  new one is created and inserted into the cache.
 */
int CacheLookup (Cache_t *cache, uint64_t off, Tag_t **tag)
{
      Tag_t *           temp;
      uint32_t    hash = off % cache->HashSize;
      int               error;

      *tag = NULL;
      
      /* Search the hash table */
      error = 0;
      temp = cache->Hash[hash];
      while (temp != NULL) {
            if (temp->Offset == off) break;
            temp = temp->Next;
      }

      /* If it's a hit */
      if (temp != NULL) {
            /* Perform MTF if necessary */
            if (cache->Hash[hash] != temp) {
                  /* Disconnect the tag */
                  if (temp->Next != NULL)
                        temp->Next->Prev = temp->Prev;
                  temp->Prev->Next = temp->Next;
            }
            
      /* Otherwise, it's a miss */
      } else {
            /* Allocate a new tag */
            temp = (Tag_t *)calloc (sizeof (Tag_t), 1);/* We really only need to zero the
                                                                               LRU portion though */
            temp->Offset = off;

            /* Kick the tag onto the LRU */
            //LRUHit (&cache->LRU, (LRUNode_t *)temp, 0);
      }

      /* Insert at the head (if it's not already there) */
      if (cache->Hash[hash] != temp) {
            temp->Prev = NULL;
            temp->Next = cache->Hash[hash];
            if (temp->Next != NULL)
                  temp->Next->Prev = temp;
            cache->Hash[hash] = temp;
      }

      /* Make sure there's a buffer */
      if (temp->Buffer == NULL) {
            /* Find a free buffer */
            temp->Buffer = CacheAllocBlock (cache);
            if (temp->Buffer == NULL) {
                  /* Try to evict a buffer */
                  error = LRUEvict (&cache->LRU, (LRUNode_t *)temp);
                  if (error != EOK) return (error);

                  /* Try again */
                  temp->Buffer = CacheAllocBlock (cache);
                  if (temp->Buffer == NULL) return (ENOMEM);
            }

            /* Load the block from disk */
            error = CacheRawRead (cache, off, cache->BlockSize, temp->Buffer);
            if (error != EOK) return (error);
      }

      *tag = temp;      
      return (EOK);
}

/*
 * CacheRawRead
 *
 *  Perform a direct read on the file.
 */
int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf)
{
      uint64_t    result;
            
      /* Both offset and length must be multiples of the device block size */
      if (off % cache->DevBlockSize) return (EINVAL);
      if (len % cache->DevBlockSize) return (EINVAL);
      
      /* Seek to the position */
      result = lseek (cache->FD_R, off, SEEK_SET);
      if (result < 0) return (errno);
      if (result != off) return (ENXIO);
      /* Read into the buffer */
      result = read (cache->FD_R, buf, len);
      if (result < 0) return (errno);
      if (result == 0) return (ENXIO);

      /* Update counters */
      cache->DiskRead++;
      
      return (EOK);
}

/*
 * CacheRawWrite
 *
 *  Perform a direct write on the file.
 */
int CacheRawWrite (Cache_t *cache, uint64_t off, uint32_t len, void *buf)
{
      uint64_t    result;
      
      /* Both offset and length must be multiples of the device block size */
      if (off % cache->DevBlockSize) return (EINVAL);
      if (len % cache->DevBlockSize) return (EINVAL);
      
      /* Seek to the position */
      result = lseek (cache->FD_W, off, SEEK_SET);
      if (result < 0) return (errno);
      if (result != off) return (ENXIO);
      
      /* Write into the buffer */
      result = write (cache->FD_W, buf, len);
      if (result < 0) return (errno);
      if (result == 0) return (ENXIO);
      
      /* Update counters */
      cache->DiskWrite++;
      
      return (EOK);
}



/*
 * LRUInit
 *
 *  Initializes the LRU data structures.
 */
static int LRUInit (LRU_t *lru)
{
      /* Make the dummy nodes point to themselves */
      lru->Head.Next = &lru->Head;
      lru->Head.Prev = &lru->Head;

      lru->Busy.Next = &lru->Busy;
      lru->Busy.Prev = &lru->Busy;

      return (EOK);
}

/*
 * LRUDestroy
 *
 *  Shutdown the LRU.
 *
 *  NOTE: This is typically a no-op, since the cache manager will be clearing
 *        all cache tags.
 */
static int LRUDestroy (LRU_t *lru)
{
      /* Nothing to do */
      return (EOK);
}

/*
 * LRUHit
 *
 *  Registers data activity on the given node. If the node is already in the
 *  LRU, it is moved to the front. Otherwise, it is inserted at the front.
 *
 *  NOTE: If the node is not in the LRU, we assume that its pointers are NULL.
 */
static int LRUHit (LRU_t *lru, LRUNode_t *node, int age)
{
      /* Handle existing nodes */
      if ((node->Next != NULL) && (node->Prev != NULL)) {
            /* Detach the node */
            node->Next->Prev = node->Prev;
            node->Prev->Next = node->Next;
      }

      /* If it's busy (we can't evict it) */
      if (((Tag_t *)node)->Refs) {
            /* Insert at the head of the Busy queue */
            node->Next = lru->Busy.Next;
            node->Prev = &lru->Busy;

      } else if (age) {
            /* Insert at the head of the LRU */
            node->Next = &lru->Head;
            node->Prev = lru->Head.Prev;
            
      } else {
            /* Insert at the head of the LRU */
            node->Next = lru->Head.Next;
            node->Prev = &lru->Head;
      }

      node->Next->Prev = node;
      node->Prev->Next = node;

      return (EOK);
}

/*
 * LRUEvict
 *
 *  Chooses a buffer to release.
 *
 *  TODO: Under extreme conditions, it shoud be possible to release the buffer
 *        of an actively referenced cache buffer, leaving the tag behind as a
 *        placeholder. This would be required for implementing 2Q-LRU
 *        replacement.
 *
 *  NOTE: Make sure we never evict the node we're trying to find a buffer for!
 */
static int LRUEvict (LRU_t *lru, LRUNode_t *node)
{
      LRUNode_t * temp;

      /* Find a victim */
      while (1) {
            /* Grab the tail */
            temp = lru->Head.Prev;
            
            /* Stop if we're empty */
            if (temp == &lru->Head) return (ENOMEM);

            /* Detach the tail */
            temp->Next->Prev = temp->Prev;
            temp->Prev->Next = temp->Next;

            /* If it's not busy, we have a victim */
            if (!((Tag_t *)temp)->Refs) break;

            /* Insert at the head of the Busy queue */
            temp->Next = lru->Busy.Next;
            temp->Prev = &lru->Busy;
                        
            temp->Next->Prev = temp;
            temp->Prev->Next = temp;

            /* Try again */
      }

      /* Remove the tag */
      CacheRemove ((Cache_t *)lru, (Tag_t *)temp);

      return (EOK);
}


Generated by  Doxygen 1.6.0   Back to index