#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 "cache.h"
#define CACHE_DEBUG 0
void *CacheAllocBlock (Cache_t *cache);
static int
CacheFreeBlock( Cache_t *cache, Tag_t *tag );
int CacheLookup (Cache_t *cache, uint64_t off, Tag_t **tag);
int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf);
int CacheRawWrite (Cache_t *cache, uint64_t off, uint32_t len, void *buf);
static int LRUInit (LRU_t *lru);
static int LRUDestroy (LRU_t *lru);
static int LRUHit (LRU_t *lru, LRUNode_t *node, int age);
static int LRUEvict (LRU_t *lru, LRUNode_t *node);
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;
cache->Hash = (Tag_t **) calloc( 1, (sizeof (Tag_t *) * hashSize) );
cache->HashSize = hashSize;
cache->BlockSize = cacheBlockSize;
cache->FreeHead = mmap (NULL,
cacheSize * cacheBlockSize,
PROT_READ | PROT_WRITE,
MAP_ANON | MAP_PRIVATE,
-1,
0);
if (cache->FreeHead == NULL) return (ENOMEM);
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));
}
int CacheDestroy (Cache_t *cache)
{
CacheFlush( cache );
#if CACHE_DEBUG
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
LRUDestroy (&cache->LRU);
return (EOK);
}
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;
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;
}
if ((buf = cache->FreeBufs) == NULL) {
#if CACHE_DEBUG
printf ("ERROR: CacheRead: no more bufs!\n");
#endif
return (ENOBUFS);
}
cache->FreeBufs = buf->Next;
*bufp = buf;
buf->Next = NULL;
buf->Prev = NULL;
buf->Flags = 0;
buf->Offset = off;
buf->Length = len;
buf->Buffer = NULL;
if ((cblk / cache->BlockSize) != ((off + len - 1) / cache->BlockSize)) {
buf->Flags |= BUF_SPAN;
}
error = CacheLookup (cache, cblk, &tag);
if (error != EOK) {
#if CACHE_DEBUG
printf ("ERROR: CacheRead: CacheLookup error\n");
#endif
return (error);
}
if (!(buf->Flags & BUF_SPAN)) {
buf->Buffer = tag->Buffer + coff;
tag->Refs++;
LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);
} else {
uint32_t boff;
uint32_t blen;
uint32_t temp;
buf->Buffer = (void *)malloc (len);
if (buf->Buffer == NULL) {
#if CACHE_DEBUG
printf ("ERROR: CacheRead: No Memory\n");
#endif
return (ENOMEM);
}
boff = cache->BlockSize - coff;
blen = len - boff;
memcpy (buf->Buffer, tag->Buffer + coff, boff);
tag->Refs++;
LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);
cblk += cache->BlockSize;
while (blen) {
error = CacheLookup (cache, cblk, &tag);
if (error != EOK) {
free (buf->Buffer);
buf->Buffer = NULL;
cblk -= cache->BlockSize;
while (!boff) {
if (CacheLookup (cache, cblk, &tag) != EOK) {
fprintf (stderr, "CacheRead: Unrecoverable error\n");
exit (-1);
}
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);
}
return (error);
}
temp = ((blen > cache->BlockSize) ? cache->BlockSize : blen);
memcpy (buf->Buffer + boff,
tag->Buffer,
temp);
boff += temp;
blen -= temp;
tag->Refs++;
LRUHit (&cache->LRU, (LRUNode_t *)tag, 0);
}
cache->Span++;
}
if (cache->ActiveBufs != NULL) {
buf->Next = cache->ActiveBufs;
buf->Prev = NULL;
cache->ActiveBufs->Prev = buf;
} else {
cache->ActiveBufs = buf;
}
cache->ReqRead++;
return (EOK);
}
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;
error = CacheLookup (cache, cblk, &tag);
if (error != EOK) return (error);
if (!(buf->Flags & BUF_SPAN)) {
if ( (writeOptions & kLazyWrite) != 0 )
{
tag->Flags |= kLazyWrite;
}
else
{
error = CacheRawWrite (cache,
tag->Offset,
cache->BlockSize,
tag->Buffer);
if (error != EOK) return (error);
}
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
} else {
uint32_t boff;
uint32_t blen;
uint32_t temp;
boff = cache->BlockSize - coff;
blen = buf->Length - boff;
memcpy (tag->Buffer + coff, buf->Buffer, boff);
if ( (writeOptions & kLazyWrite) != 0 )
{
tag->Flags |= kLazyWrite;
}
else
{
error = CacheRawWrite (cache,
tag->Offset,
cache->BlockSize,
tag->Buffer);
if (error != EOK) return (error);
}
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
cblk += cache->BlockSize;
while (blen) {
error = CacheLookup (cache, cblk, &tag);
temp = ((blen > cache->BlockSize) ? cache->BlockSize : blen);
memcpy (tag->Buffer,
buf->Buffer + boff,
temp);
if ( (writeOptions & kLazyWrite) != 0 )
{
tag->Flags |= kLazyWrite;
}
else
{
error = CacheRawWrite (cache,
tag->Offset,
cache->BlockSize,
tag->Buffer);
if (error != EOK) return (error);
}
boff += temp;
blen -= temp;
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
}
free (buf->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;
memset (buf, 0x00, sizeof (Buf_t));
buf->Next = cache->FreeBufs;
cache->FreeBufs = buf;
cache->ReqWrite++;
return (EOK);
}
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;
error = CacheLookup (cache, cblk, &tag);
if (error != EOK) {
#if CACHE_DEBUG
printf ("ERROR: CacheRelease: CacheLookup error\n");
#endif
return (error);
}
if (!(buf->Flags & BUF_SPAN)) {
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
} else {
uint32_t blen;
blen = buf->Length - cache->BlockSize + coff;
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
cblk += cache->BlockSize;
while (blen) {
error = CacheLookup (cache, cblk, &tag);
blen -= ((blen > cache->BlockSize) ? cache->BlockSize : blen);
tag->Refs--;
LRUHit (&cache->LRU, (LRUNode_t *)tag, age);
}
free (buf->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;
memset (buf, 0x00, sizeof (Buf_t));
buf->Next = cache->FreeBufs;
cache->FreeBufs = buf;
return (EOK);
}
int CacheRemove (Cache_t *cache, Tag_t *tag)
{
int error;
if (tag->Refs) return (EBUSY);
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;
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
}
if (tag->Buffer != NULL)
{
error = CacheFreeBlock (cache, tag);
if ( EOK != error )
return( error );
}
memset (tag, 0x00, sizeof (Tag_t));
free (tag);
return (EOK);
}
int CacheEvict (Cache_t *cache, Tag_t *tag)
{
int error;
if (tag->Refs) return (EBUSY);
if (tag->Buffer != NULL)
{
error = CacheFreeBlock (cache, tag);
if ( EOK != error )
return( error );
}
tag->Buffer = NULL;
return (EOK);
}
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);
}
static int
CacheFreeBlock( Cache_t *cache, Tag_t *tag )
{
int error;
if ( (tag->Flags & kLazyWrite) != 0 )
{
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 );
}
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 )
{
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;
}
}
return( EOK );
}
int CacheLookup (Cache_t *cache, uint64_t off, Tag_t **tag)
{
Tag_t * temp;
uint32_t hash = off % cache->HashSize;
int error;
*tag = NULL;
error = 0;
temp = cache->Hash[hash];
while (temp != NULL) {
if (temp->Offset == off) break;
temp = temp->Next;
}
if (temp != NULL) {
if (cache->Hash[hash] != temp) {
if (temp->Next != NULL)
temp->Next->Prev = temp->Prev;
temp->Prev->Next = temp->Next;
}
} else {
temp = (Tag_t *)calloc (sizeof (Tag_t), 1);
temp->Offset = off;
}
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;
}
if (temp->Buffer == NULL) {
temp->Buffer = CacheAllocBlock (cache);
if (temp->Buffer == NULL) {
error = LRUEvict (&cache->LRU, (LRUNode_t *)temp);
if (error != EOK) return (error);
temp->Buffer = CacheAllocBlock (cache);
if (temp->Buffer == NULL) return (ENOMEM);
}
error = CacheRawRead (cache, off, cache->BlockSize, temp->Buffer);
if (error != EOK) return (error);
}
*tag = temp;
return (EOK);
}
int CacheRawRead (Cache_t *cache, uint64_t off, uint32_t len, void *buf)
{
uint64_t result;
if (off % cache->DevBlockSize) return (EINVAL);
if (len % cache->DevBlockSize) return (EINVAL);
result = lseek (cache->FD_R, off, SEEK_SET);
if (result < 0) return (errno);
if (result != off) return (ENXIO);
result = read (cache->FD_R, buf, len);
if (result < 0) return (errno);
if (result == 0) return (ENXIO);
cache->DiskRead++;
return (EOK);
}
int CacheRawWrite (Cache_t *cache, uint64_t off, uint32_t len, void *buf)
{
uint64_t result;
if (off % cache->DevBlockSize) return (EINVAL);
if (len % cache->DevBlockSize) return (EINVAL);
result = lseek (cache->FD_W, off, SEEK_SET);
if (result < 0) return (errno);
if (result != off) return (ENXIO);
result = write (cache->FD_W, buf, len);
if (result < 0) return (errno);
if (result == 0) return (ENXIO);
cache->DiskWrite++;
return (EOK);
}
static int LRUInit (LRU_t *lru)
{
lru->Head.Next = &lru->Head;
lru->Head.Prev = &lru->Head;
lru->Busy.Next = &lru->Busy;
lru->Busy.Prev = &lru->Busy;
return (EOK);
}
static int LRUDestroy (LRU_t *lru)
{
return (EOK);
}
static int LRUHit (LRU_t *lru, LRUNode_t *node, int age)
{
if ((node->Next != NULL) && (node->Prev != NULL)) {
node->Next->Prev = node->Prev;
node->Prev->Next = node->Next;
}
if (((Tag_t *)node)->Refs) {
node->Next = lru->Busy.Next;
node->Prev = &lru->Busy;
} else if (age) {
node->Next = &lru->Head;
node->Prev = lru->Head.Prev;
} else {
node->Next = lru->Head.Next;
node->Prev = &lru->Head;
}
node->Next->Prev = node;
node->Prev->Next = node;
return (EOK);
}
static int LRUEvict (LRU_t *lru, LRUNode_t *node)
{
LRUNode_t * temp;
while (1) {
temp = lru->Head.Prev;
if (temp == &lru->Head) return (ENOMEM);
temp->Next->Prev = temp->Prev;
temp->Prev->Next = temp->Next;
if (!((Tag_t *)temp)->Refs) break;
temp->Next = lru->Busy.Next;
temp->Prev = &lru->Busy;
temp->Next->Prev = temp;
temp->Prev->Next = temp;
}
CacheRemove ((Cache_t *)lru, (Tag_t *)temp);
return (EOK);
}