/*static char *SCCSID = "@(#)xlist.c	6.4 92/01/15";*/
#define SCCSID "@(#)xlist.c	6.4 92/01/15"
/*
 *	IBM/Microsoft Confidential
 *
 *	Copyright (c) IBM Corporation 1987, 1989
 *	Copyright (c) Microsoft Corporation 1987, 1989
 *
 *	All Rights Reserved
 *
 */

/*  NAME :  XLIST.C
 *
 *
 *  DESCRIPTION
 *
 *      This file contains functions which examine a sector list in the
 *      cache.
 *
 *
 *  FUNCTIONS DEFINED
 *
 *      FindExistBuf () --  Search a sector list for a particular sector.
 *      ResearchList () --  Examine and possibly add headers for a later
 *                          read.
 *      PendWait ()     --  Wait for a pending read to return from the disk.
 *
 *
 *  REVISION HISTORY (in reverse chronological order)
 *  -----------------------------------------------------------------------
 *  5/3/90      Brian Andrew        Modified 'ResearchList' to prevent
 *                                  pointing to header which may be
 *                                  preempted.
 *
 *                                  'FindExistBuf' will remember a header
 *                                  which will not be preempted.
 *
 *  4/10/90     Brian Andrew        Initial version of 'FindExistBuf'.
 *                                  Initial version of 'ResearchList'.
 *                                  Initial version of 'PendWait'.
 *
 *  TO DO
 *  -------------------------------------------------------------------------
 */

#define INCL_DOSERRORS
#define INCL_NOPMAPI

#include <os2.h>
#include <fsh.h>

#include "cdfs.h"
#include "sem.h"
#include "path.h"
#include "vol.h"
#include "heap.h"
#include "mem.h"
#include "buffer.h"

#ifdef STATS_H
#include "stats.h"
#endif

#include "message.h"
#include "fsdata.h"
#include "cache.h"

#ifdef DEBUG
#include "pr_debug.h"
#endif

#include "pr_cache.h"
#include "pr_memin.h"


/***    FindExistBuf () --  Search a sector list for a particular sector.
 *
 *  DESCRIPTION
 *
 *      This function traverses a list of sectors, searching for a
 *      particular sector.  If the sector is found, a pointer to it
 *      is returned and the buffer is locked.  Its position on the LRU
 *      list is also modified.  If the sector is not found, the return
 *      pointer is set to the owning structure that the target sector
 *      should be attached to.  This owning structure is then locked
 *      pending attachment of a buffer.  If there is no buffer attached
 *      to the previous sector header, that header isn't locked since
 *      headers are never preempted.
 *
 *      The purpose of this function is simply to ascertain whether the
 *      desired sector is in the cache.
 *
 *
 *  ENTRY   (Arguements passed to function)
 *
 *      The following fields in 'pfblVars' are used.
 *
 *      pbBufChain      --  Pointer to buffer if found.
 *      pblPrevHdr      --  Pointer to previous header if buffer not found.
 *      snStartSector   --  Sector number to search for.
 *      fBLOwns         --  Flag indicating if this is a BUF_LIST list.
 *      fLocked         --  Flag indicating if previous sector is locked.
 *
 *
 *  GLOBAL  (Global variables accessed by this function)
 *
 *      NONE.
 *
 *
 *  GOTO    (Jump targets)
 *
 *      NONE.
 *
 *
 *  RETURN  (Value returned by this function)
 *
 *      TRUE if sector in cache.  ppblFound points to correct sector.
 *      FALSE otherwise.  ppblFound is sector to attach target sector to.
 *
 *
 *  EXIT    (Changes to variables seen outside this function)
 *
 *      The following fields in 'pfblVars' are modified as appropriate.
 *      pbBufChain      --  Pointer to BUF for single sector reads.
 *      pblPrevHdr      --  Pointer to header to attach the new header to.
 *      fLocked         --  Indicates if a buffer is locked.
 *
 *
 *  LOCAL   (Variables declared within this function)
 *
 *      fRet        --  Boolean return value.
 *      pblStart    --  Pointer to sector owner to begin search at.
 *      pblNext     --  Pointer to the next sector in the chain.
 */

BOOL FindExistBuf (pfblVars)
PFIND_BUF_LOC   pfblVars;
{
	/* Local variables */
	PBUF_LIST       pblStart;
	PBUF_LIST       pblNext;
	BOOL            fRet;

	/* Point to the start of the list */
	pblStart = pfblVars->pblPrevHdr;

	/* Walk through until next sector is target or should be */
	while ( (pblNext = pblStart->pblNext) &&
			pfblVars->snStartSector > pblNext->snSectNum)
	{
		pblStart = pblNext;
      /*FSH_YIELD();*/        /* ptr b728795 */
	}

	/* If it is the target and buffer is present */
	if (pblNext &&
		pfblVars->snStartSector == pblNext->snSectNum &&
		pblNext->pbBuf)
	{
		/* Remember this sector and lock the buffer */
		(pfblVars->pbBufChain = pblNext->pbBuf)->cUsers++;

#ifdef DEBUG
		/* Check for successful with buffer locked */
		if (!((pfblVars->pbBufChain)->cUsers))
		{
			dprintf ("\tFindExist: Buffer not locked\n");
			Int3();

		}
#endif

		/* Remove from the LRU list */
		/* Check if BUF_LIST structure */
		if (pfblVars->fBLOwns)
		{
			RemoveListSec (pfblVars->pbBufChain);

		}

		/* Else PATH_TABLE structure */
		else
		{
			RemovePTSec (pfblVars->pbBufChain);

		}

		/* Move to the top of the LRU list */
		AddBufChain (   pfblVars->pbBufChain, pfblVars->pbBufChain,
						pfblVars->fBLOwns);

		/* Return value is TRUE */
		fRet = TRUE;

	} /* end if it is the target */

	/* Else lock a sector before it (which will not be preempted) */
	else
	{
		/* Check if this is a BUF_LIST or PATH_TABLE */
		if (pfblVars->fBLOwns)
		{
			/* Walk backwards stopping at NULL header or header with BUF */
			while ( !pblStart->pbBuf &&
					pblStart->pblPrev)
			{
				pblStart = pblStart->pblPrev;
                FSH_YIELD();          /* ptr b728795 */
			}
		}

		/* Remember the previous sector */
		pfblVars->pblPrevHdr = pblStart;

		/* Lock the previous buffer (if it has one) */
		if (pblStart->pbBuf)
		{
			((PBUF) pblStart->pbBuf)->cUsers++;

			/* Remember it has been locked */
			pfblVars->fLocked = TRUE;

		}

		/* Else buffer has not been locked */
		else
		{
			pfblVars->fLocked = FALSE;

		}

		/* Return value is FALSE */
		fRet = FALSE;

	}

	/* Return whether buffer found */
	return fRet;

} /* end FindExistBuf */


/***    ResearchList () --  Examine and possibly add headers for a later
 *                          read.
 *
 *  DESCRIPTION
 *
 *      This function is called when the preliminary sector list search
 *      indicated that the desired sector is missing.  The position from
 *      the previous search is available as a starting point.  It's
 *      possible that the desired sector may have been added while
 *      this thread achieved write status, so we check again for that
 *      sector being present.
 *
 *      The second possibility is that the desired thread is being
 *      searched for now.  In that case we register as a pending reader
 *      and wait on the header semaphore.  There are two possible return
 *      codes in this case.  First the read completed successfully, secondly
 *      the read did not complete.  In the latter case, this thread will
 *      attempt to read directly from the disk by adding the headers now.
 *
 *      The final case occurs when this thread will perform the read from
 *      the disk.  A header is added for each sector to be read (calling
 *      'AddHdrs').
 *
 *      On entry to this function, this thread has exclusive access into
 *      this list and has possibly locked down the previous sector to the
 *      target in 'FindExistBuf'.  This thread will give up the exclusive
 *      access if it waits on a pending read but then gains it again if
 *      the pending read fails.
 *
 *      On exit, this thread has given up exclusive access.
 *
 *      There are three possible return values for this function.
 *
 *          BUF_FOUND   Buffer is found and pointer to buffer is stored
 *                      is stored in 'pbSingleBuf'.
 *
 *          ADDED_HDRS  The target is missing and this thread will attempt
 *                      to read from the disk.
 *
 *          ADD_ERROR   A fatal error occurred during 'AddHdrs', the error
 *                      is stored in 'ErrCode'
 *
 *
 *  ENTRY   (Arguements passed to function)
 *
 *      The following fields in 'pfblVars' are used.
 *
 *      fLocked         --  Indicates if a buffer is locked.
 *      pblPrevHdr      --  Pointer to header to attach the new header to.
 *      usErrCode       --  Error code passed through 'ResearchList'.
 *
 *
 *  GLOBAL  (Global variables accessed by this function)
 *
 *      NONE.
 *
 *
 *  GOTO    (Jump targets)
 *
 *      ResearchList_AddHdrs    --  Common point to add headers to the list.
 *
 *
 *  RETURN  (Value returned by this function)
 *
 *      BUF_FOUND   if buffer is found in the list.
 *      ADDED_HDRS  if headers were added in anticipation of read.
 *      ADD_ERROR   if error occurred while adding headers.
 *
 *
 *  EXIT    (Changes to variables seen outside this function)
 *
 *      Changes to 'pfblVars' occur in functions called here.
 *
 *
 *  LOCAL   (Variables declared within this function)
 *
 *      usRet       --  Return code for this function.
 *      pblThisBL   --  Pointer to current position in list.
 */

USHORT ResearchList (pfblVars)
PFIND_BUF_LOC   pfblVars;
{
	/* Local variables */
	USHORT      usRet;
	PBUF_LIST   pblThisBL;

	/* Do forever until buffer found or error occurs */
	for (;;)
	{
		/* If previous sector locked, then release it */
		if (pfblVars->fLocked)
		{
#ifdef DEBUG
			/* Check for successful with buffer locked */
			if (!(((PBUF) pfblVars->pblPrevHdr->pbBuf)->cUsers))
			{
				dprintf ("\tResearchList2: Buffer not locked\n");
				Int3();

			}
#endif

			((PBUF) pfblVars->pblPrevHdr->pbBuf)->cUsers--;
		}

		/* Call 'FindExistBuf' to confirm sector has not been added */
		if (!FindExistBuf (pfblVars))
		{
			/* Walk to the header which would precede the target header */
			pblThisBL = pfblVars->pblPrevHdr;

			while ( pblThisBL->pblNext &&
					pfblVars->snStartSector > pblThisBL->pblNext->snSectNum)
			{
				pblThisBL = pblThisBL->pblNext;
			}

			/* Remember the next sector */
			/* Check if following sector is the correct header */
			if (pblThisBL->pblNext &&
				pblThisBL->pblNext->snSectNum == pfblVars->snStartSector)
			{
				/* Check if following header has a pending read */
				if (pblThisBL->pblNext->usCountPend)
				{
					/* Check if pending read is unsuccessful */
					if (! PendWait (pfblVars, pblThisBL->pblNext))
					{
						/* Become a writer and start at the top of the loop */
						BecomeWriter (pfblVars->plsbThisSemBlk);

						continue;
					}

					/* Else pending read successful */
					else
					{
						/* Unlock the prevHdr buffer if locked */
						if (pfblVars->fLocked)
						{
#ifdef DEBUG
							/* Check for successful with buffer locked */
							if (!(((PBUF) pfblVars->pblPrevHdr->pbBuf)->cUsers))
							{
								dprintf ("\tResearchList2: Buffer not locked\n");
								Int3();

							}
#endif

							((PBUF) pfblVars->pblPrevHdr->pbBuf)->cUsers--;
						}


						usRet = BUF_FOUND;

					}

				} /* end if pending read */

				/* Else jump to code to call 'AddHdrs' */
				else
				{
					goto ResearchList_AddHdrs;

				}

			} /* end if following header is correct header */

			/* Else header is missing call 'AddHdrs' */
			else
			{
/* Common point for adding headers */
ResearchList_AddHdrs:

				/* If previous sector locked, release it */
				if (pfblVars->fLocked)
				{
#ifdef DEBUG
					/* Check for successful with buffer locked */
					if (!(((PBUF) pfblVars->pblPrevHdr->pbBuf)->cUsers))
					{
						dprintf ("\tResearchList2: Buffer not locked\n");
						Int3();

					}
#endif

					((PBUF) pfblVars->pblPrevHdr->pbBuf)->cUsers--;
				}
	
				/* Use pblThisBL as the previous header */
				pfblVars->pblPrevHdr = pblThisBL;

				/* Check if 'AddHdrs' is successful */
				if (!(pfblVars->usErrCode = AddHdrs (pfblVars)))
				{
					/* Indicate headers were added */
					usRet = ADDED_HDRS;

				} /* end if 'AddHdrs' successful */

				/* Else return failure */
				else
				{
					usRet = ADD_ERROR;

				} /* end else total failure */

				/* Give up writer status */
				DepartWriter (pfblVars->plsbThisSemBlk);

			} /* end else header is missing */

		} /* end if sector is not present */

		/* Else search is complete, buffer is in 'pfblVars->pbBufChain' */
		else
		{

			/* Give up writer status */
			DepartWriter (pfblVars->plsbThisSemBlk);

			usRet = BUF_FOUND;

		} /* end else existing buffer found */

		/* Break out of the loop at this point */
		break;

	} /* end forever */

	/* Return usRet */
	return usRet;

} /* end ResearchList */


/***    PendWait ()     --  Wait for a pending read from the disk.
 *
 *  DESCRIPTION
 *
 *      This function is called when a thread is waiting on a pending
 *      read for a particular buffer.  On entry the thread has exclusive
 *      access into the sector list.  It gives up this status and
 *      waits on the header semaphore.  If the read operation is
 *      successful, the header will have a buffer attached and the
 *      user's count will reflect this thread.  In that case a pointer
 *      to the buffer is stored in 'pfblVars' and TRUE is returned.
 *
 *      If a read error occurred the buffer will be missing and the
 *      header will have already been pulled off the sector list (if
 *      not a Path Table).  If this is the last pending reader, the
 *      header is returned to the free list (unless a path table header
 *      which is left behind).
 *
 *      If the read is successful the buffer has already been placed in
 *      the LRU list.
 *
 *
 *  ENTRY   (Arguements passed to function)
 *
 *      pblThisHdr      --  Pointer to the header in question.
 *
 *      The following fields in 'pfblVars' are used.
 *
 *      fBLOwns         --  Is this a BUF_LIST header.
 *      pbBufChain      --  Pointer to BUF for single sector reads.
 *
 *
 *  GLOBAL  (Global variables accessed by this function)
 *
 *      NONE.
 *
 *
 *  GOTO    (Jump targets)
 *
 *      NONE.
 *
 *
 *  RETURN  (Value returned by this function)
 *
 *      TRUE if sector read was successful.
 *      FALSE if unsuccessful.
 *
 *
 *  EXIT    (Changes to variables seen outside this function)
 *
 *      pfblVars->pbBufChain will point to the buffer if read successful.
 *
 *
 *  LOCAL   (Variables declared within this function)
 *
 *      fRet    --  Return value.
 */
BOOL PendWait (pfblVars, pblThisHdr)
PFIND_BUF_LOC   pfblVars;
PBUF_LIST       pblThisHdr;
{
	/* Local variables */
	BOOL        fRet;

	/* Assume operation was unsuccessful */
	fRet = FALSE;

	/* Register as a pending reader */
	pblThisHdr->usCountPend++;

	/* Give up writer status */
	DepartWriter (pblThisHdr->plsbSemBlk);

	/* Wait on the header semaphore */
	SEM_REQ (pblThisHdr->sHeaderSem);

	/* Check for existence of buffer */
	if (pfblVars->pbBufChain = pblThisHdr->pbBuf)
	{
		/* Return is success */
		fRet = TRUE;

		/* Decrement the pending readers */
		pblThisHdr->usCountPend--;

		/* Clear the header semaphore */
		SEM_CLEAR (pblThisHdr->sHeaderSem);

#ifdef DEBUG
		/* Check that buffer is locked */
		if (!pfblVars->pbBufChain->cUsers)
		{
			dprintf ("\tPendWait:  Buffer not locked down\n");
			Int3 ();
		}
#endif

	} /* end if buffer exists */

	/* Else check if last reader */
	else if (!(--pblThisHdr->usCountPend) && pfblVars->fBLOwns)
	{
		/* Clear the semaphore */
		SEM_CLEAR (pblThisHdr->sHeaderSem);
		
		/* Free the structure */
		FREE_BUF_LIST (pblThisHdr);

	} /* end else last reader */

	/* Else simply clear the semaphore */
	else
	{
		SEM_CLEAR (pblThisHdr->sHeaderSem);
	}

	/* Return fRet */
	return fRet;

} /* end PendWait */


