Unix Buffer Cache management

The following program is a partial implementation to understand getblk,bread,brelse,breada,bwrite system calls of UNIX

#include
#include
#define MAXSIZE 40
#define HASHQSIZE 4


/*
 *
 */

struct buffer_block
    {
        int blockNo;
        struct buffer_block * next_HQ;
        struct buffer_block * prev_HQ;
        struct buffer_block * prev_FreeList;
        struct buffer_block * next_FreeList;
        int lock;
        int valid;
        int delayedWrite;
    };
   
typedef struct buffer_block * BufferCache;
   
BufferCache hashQueue[MAXSIZE];
BufferCache freeListHeader;



void initializeBuffer(BufferCache);
void addToHashQueue(BufferCache);
void addToFreeList(BufferCache,int);
void removeFromFreeList(BufferCache);
void removeFromHashQueue(BufferCache);
BufferCache searchHashQueue(int);
BufferCache newBuffer();
BufferCache getblk(int);
void brelse(BufferCache);
BufferCache bread(int);
BufferCache breada(int,int);
void bwrite(BufferCache,int);
void printHashQueue();
void printFreeList();



void addToHashQueue(BufferCache buf)
{
    int hash;
    hash = buf->blockNo % HASHQSIZE;
   
    if(hashQueue[hash]==NULL)
    {
        hashQueue[hash]=buf;
        buf->prev_HQ=NULL;
        buf->next_HQ=NULL;
    }
    else
    {
        buf->next_HQ=hashQueue[hash];
        buf->prev_HQ=NULL;
        hashQueue[hash]=buf;
    }
   
}



void removeFromHashQueue(BufferCache buf)
{
    int hash;
    hash = buf->blockNo % HASHQSIZE;
   
    if(buf->prev_HQ==NULL)
    {
        hashQueue[hash]=buf->next_HQ;
    }
    else
    {
        buf->prev_HQ->next_HQ=buf->next_HQ;
        if(buf->next_HQ!=NULL)
        {
            buf->next_HQ->prev_HQ=buf->prev_HQ;
        }
    }
}

void addToFreeList(BufferCache buf,int pos)
{
    if(freeListHeader->next_FreeList==freeListHeader)
    {
        freeListHeader->next_FreeList=buf;
        freeListHeader->prev_FreeList=buf;
        buf->next_FreeList=freeListHeader;
        buf->prev_FreeList=freeListHeader;
    }
    else
    {
        if(pos==1)/*Front of the list*/
        {
            buf->next_FreeList=freeListHeader->next_FreeList;
            buf->prev_FreeList=freeListHeader;
            freeListHeader->next_FreeList->prev_FreeList=buf;
            freeListHeader->next_FreeList=buf;
        }
        else /* Back of the list */
        {
            buf->prev_FreeList=freeListHeader->prev_FreeList;
            buf->next_FreeList=freeListHeader;
            freeListHeader->prev_FreeList->next_FreeList=buf;
            freeListHeader->prev_FreeList=buf;
        }
    }
}

void removeFromFreeList(BufferCache buf)
{
    if(buf==freeListHeader->next_FreeList)
    {
       
        buf->next_FreeList->prev_FreeList=freeListHeader;
        freeListHeader->next_FreeList=buf->next_FreeList;
        return;
    }
    if(buf==freeListHeader->prev_FreeList)
    {
       
        buf->prev_FreeList->next_FreeList=freeListHeader;
        freeListHeader->prev_FreeList=buf->prev_FreeList;
        return;
    }
   
   buf->next_FreeList->prev_FreeList=buf->prev_FreeList;
   buf->prev_FreeList->next_FreeList=buf->next_FreeList;
}


void intializeBuffer()
{
    int i;
    BufferCache buf;
    freeListHeader=newBuffer();
   
    freeListHeader->prev_FreeList =freeListHeader;
    freeListHeader->next_FreeList =freeListHeader;
   
    for(i=0;i    {
        buf= newBuffer();
        buf->blockNo=i;
        addToHashQueue(buf);
        addToFreeList(buf,1);      
    }
   
}

BufferCache newBuffer()
{
    BufferCache buf = (BufferCache) malloc(sizeof (struct buffer_block));
    buf->valid = 0;
    buf->delayedWrite=0;
    buf->lock=0;
    return buf;
}

BufferCache searchHashQueue(int blockno)
{
    int hash;
    BufferCache buf;
    hash = blockno % HASHQSIZE;
    buf = hashQueue[hash];
    while(buf!=NULL)
    {
        if(buf->blockNo==blockno)
            return buf;
        buf=buf->next_HQ;
    }
    return NULL;  
}

BufferCache getblk(int blockno)
{
    int found=0;
    BufferCache buf;
    while(found==0)
    {
        buf = searchHashQueue(blockno);
        if(buf!=NULL)/*Block in Hash Queue */
        {
            if(buf->lock)
            {
                printf("\nbuffer busy Sleep till block become free \n");              
                /* workaround*/
                brelse(buf);
                /* end of workaround*/
                continue;              
            }
            buf->lock=1;
            removeFromFreeList(buf);
            return buf;
        }
        else
        {
            if(freeListHeader->next_FreeList==freeListHeader)
            {
                printf("\nFree list empty sleep till any buffer available\n");
                /* workaround*/
                brelse(hashQueue[0]);
                /* end of workaround*/
                continue;
            }
            buf=freeListHeader->next_FreeList;
            removeFromFreeList(buf);
            if(buf->delayedWrite)
            {
                printf("\nPerform asyncranous write of block %d\n",buf->blockNo);
                bwrite(buf,0);
                continue;
            }
            removeFromHashQueue(buf);
            buf->blockNo=blockno;
            addToHashQueue(buf);
            buf->valid=0;      
            buf->lock=1;
            return buf;
        }
    }
}

void brelse(BufferCache buf)
{
    printf("\nWakeup all process waiting for any buffer\n");
    printf("\nWakeup all process waiting for buffer with block %d\n",buf->blockNo);
    printf("\nRaise processor execution level to block interrupts\n");
    if(buf->valid)//also check If buffer is old
    {
        addToFreeList(buf,0);
    }
    else
    {
        addToFreeList(buf,1);
    }
    printf("\nlower processor execution level to allow interrupts\n");
    buf->lock=0;
}

BufferCache bread(int blockno)
{
    BufferCache buf;
    buf=getblk(blockno);
    if(buf->valid)
        return buf;
    printf("\nInitiate disk read of block %d\n",blockno);
    printf("\nSleep till disk read complete\n");
    return buf;
}

BufferCache breada(int imdBlockno,int asynBlockno)
{
    BufferCache buf1,buf2;
    int flag=0;
    buf1=searchHashQueue(imdBlockno);
    buf2=searchHashQueue(asynBlockno);
    if(buf1==NULL)
    {
        flag=1;
        buf1 = getblk(imdBlockno);
        if(buf1->valid==0)
            printf("\nInitiate disk read of block %d\n",imdBlockno);
    }
    if(buf2==NULL)
    {
        buf2=getblk(asynBlockno);
        if(buf2->valid)
            brelse(buf2);
        else
            printf("\nInitiate disk read of block %d\n",asynBlockno);
    }
    if(!flag)
    {
        buf1=bread(imdBlockno);
        return buf1;
    }
    printf("\nSleep till Cache contains valid data\n");
    return buf1;
}

void bwrite(BufferCache buf,int syn)
{
    printf("\nInitiate disk write\n");
    if(syn)
    {
        printf("\nSleep till IO complete\n");
        brelse(buf);
    }
    else
        if(buf->delayedWrite)
        {
            buf->delayedWrite=0;
            removeFromFreeList(buf);
            addToFreeList(buf,1);
        }
}

void printHashQueue()
{
    int i;
    BufferCache buf;
    for(i=0;i    {
        printf("\nElement with Hash value %d\n",i);
        buf=hashQueue[i];
        while(buf!=NULL)
        {
            printf("%d\t%d\t%d\t%d\n",buf->blockNo,buf->delayedWrite,buf->lock,buf->valid);
            buf=buf->next_HQ;
        }
    }
}
void printFreeList()
{
    BufferCache buf;
    buf= freeListHeader;
    printf("\nElement in Freelist\n");
    while(buf->next_FreeList!=freeListHeader)
    {
        buf=buf->next_FreeList;
        printf("%d\t%d\t%d\t%d\n",buf->blockNo,buf->delayedWrite,buf->lock,buf->valid);
    }
}

int main(int argc, char** argv) {

    intializeBuffer();
    BufferCache buf,buf1;
    //printHashQueue();
    //printFreeList();
    buf = getblk(5);    //block is in cache and available
    printf("\n%d block read\n",buf->blockNo);
    buf = getblk(55);   //block is not in cache and free list available
    printf("\n%d block read\n",buf->blockNo);
    buf = getblk(5);    //block is in cache and is in Use
    printf("\n%d block read\n",buf->blockNo);
    freeListHeader->next_FreeList->delayedWrite=1;
    buf = getblk(56);   //block is not in cache and free buffer marked delayed write
    printf("\n%d block read\n",buf->blockNo);
    while(freeListHeader->next_FreeList!=freeListHeader)
    {
        getblk(freeListHeader->next_FreeList->blockNo);
    }
   
    buf = getblk(60);
    printf("\n%d block read\n",buf->blockNo);
    brelse(buf);
   

    buf = getblk(60);
    printf("\n%d block read\n", buf->blockNo);
    buf->valid = 1;
    brelse(buf);
    printHashQueue();
    printFreeList();
    buf = bread(32);
   
    buf=breada(2,77);
    bwrite(buf,0);
   
    buf=bread(3);
    bwrite(buf,1);
    breada(2,36);
    printHashQueue();
    printFreeList();
    return 0;
}