rf_paritylog.c

RAIDFrame是个非常好的磁盘阵列RAID仿真工具

static void RequeueParityLogData(
  RF_ParityLogData_t   *data,
  RF_ParityLogData_t  **head,
  RF_ParityLogData_t  **tail)
{
  RF_Raid_t *raidPtr;

  /* Insert an in-core parity log (*data) into the tail of
     a disk queue (*head, *tail).
     NON-BLOCKING */

  raidPtr = data->common->raidPtr;
  RF_ASSERT(data);
  if (rf_parityLogDebug)
    printf("[requeueing parity log data, region %d, raidAddress %d, numSector %d]\n",data->regionID,data->diskAddress.raidAddress, data->diskAddress.numSector);
  RF_LOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
  if (*tail)
    {
      /* append to tail of list */
      data->prev = *tail;
      data->next = NULL;
      (*tail)->next = data;
      *tail = data;
    }
  else
    {
      /* inserting into an empty list */
      *head = data;
      *tail = data;
      (*head)->prev = NULL;
      (*tail)->next = NULL;
    }
  RF_ASSERT((*head)->prev == NULL);
  RF_ASSERT((*tail)->next == NULL);
  RF_UNLOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
}

RF_ParityLogData_t *rf_CreateParityLogData(
  RF_ParityRecordType_t    operation,
  RF_PhysDiskAddr_t       *pda,
  caddr_t                  bufPtr,
  RF_Raid_t               *raidPtr,
  int                    (*wakeFunc)(),
  void                    *wakeArg,
  RF_AccTraceEntry_t      *tracerec,
  RF_Etimer_t              startTime)
{
  RF_ParityLogData_t *data, *resultHead = NULL, *resultTail = NULL;
  RF_CommonLogData_t *common;
  RF_PhysDiskAddr_t *diskAddress;
  int boundary, offset = 0;

  /* Return an initialized struct of info to be logged.
     Build one item per physical disk address, one item per region.

     NON-BLOCKING */

  diskAddress = pda;
  common = AllocParityLogCommonData(raidPtr);
  RF_ASSERT(common);

  common->operation = operation;
  common->bufPtr = bufPtr;
  common->raidPtr = raidPtr;
  common->wakeFunc = wakeFunc;
  common->wakeArg = wakeArg;
  common->tracerec = tracerec;
  common->startTime = startTime;
  common->cnt = 0;

  if (rf_parityLogDebug)
    printf("[entering CreateParityLogData]\n");
  while (diskAddress)
    {
      common->cnt++;
      data = AllocParityLogData(raidPtr);
      RF_ASSERT(data);
      data->common = common;
      data->next = NULL;
      data->prev = NULL;
      data->regionID = rf_MapRegionIDParityLogging(raidPtr, diskAddress->startSector);
      if (data->regionID == rf_MapRegionIDParityLogging(raidPtr, diskAddress->startSector + diskAddress->numSector - 1))
	{
	  /* disk address does not cross a region boundary */
	  data->diskAddress = *diskAddress;
	  data->bufOffset = offset;
	  offset = offset + diskAddress->numSector;
	  EnqueueParityLogData(data, &resultHead, &resultTail);
	  /* adjust disk address */
	  diskAddress = diskAddress->next;
	}
      else
	{
	  /* disk address crosses a region boundary */
	  /* find address where region is crossed */
	  boundary = 0;
	  while (data->regionID == rf_MapRegionIDParityLogging(raidPtr, diskAddress->startSector + boundary))
	    boundary++;

	  /* enter data before the boundary */
	  data->diskAddress = *diskAddress;
	  data->diskAddress.numSector = boundary;
	  data->bufOffset = offset;
	  offset += boundary;
	  EnqueueParityLogData(data, &resultHead, &resultTail);
	  /* adjust disk address */
	  diskAddress->startSector += boundary;
	  diskAddress->numSector -= boundary;
	}
    }
  if (rf_parityLogDebug)
    printf("[leaving CreateParityLogData]\n");
  return(resultHead);
}


RF_ParityLogData_t *rf_SearchAndDequeueParityLogData(
  RF_Raid_t            *raidPtr,
  int                   regionID,
  RF_ParityLogData_t  **head,
  RF_ParityLogData_t  **tail,
  int                   ignoreLocks)
{
  RF_ParityLogData_t *w;

  /* Remove and return an in-core parity log from a specified region (regionID).
     If a matching log is not found, return NULL.

     NON-BLOCKING.
     */

  /* walk backward through a list, looking for an entry with a matching region ID */
  if (!ignoreLocks)
    RF_LOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
  w = (*tail);
  while (w)
    {
      if (w->regionID == regionID)
	{
	  /* remove an element from the list */
	  if (w == *tail)
	    {
	      if (*head == *tail)
		{
		  /* removing only element in the list */
		  *head = NULL;
		  *tail = NULL;
		}
	      else
		{
		  /* removing last item in the list */
		  *tail = (*tail)->prev;
		  (*tail)->next = NULL;
		  RF_ASSERT((*head)->prev == NULL);
		  RF_ASSERT((*tail)->next == NULL);
		}
	    }
	  else
	    {
	      if (w == *head)
		{
		  /* removing first item in the list */
		  *head = (*head)->next;
		  (*head)->prev = NULL;
		  RF_ASSERT((*head)->prev == NULL);
		  RF_ASSERT((*tail)->next == NULL);
		}
	      else
		{
		  /* removing an item from the middle of the list */
		  w->prev->next = w->next;
		  w->next->prev = w->prev;
		  RF_ASSERT((*head)->prev == NULL);
		  RF_ASSERT((*tail)->next == NULL);
		}
	    }
	  w->prev = NULL;
	  w->next = NULL;
	  if (rf_parityLogDebug)
	    printf("[dequeueing parity log data, region %d, raidAddress %d, numSector %d]\n",w->regionID,w->diskAddress.raidAddress, w->diskAddress.numSector);
	  return(w);
	}
      else
	w = w->prev;
    }
  if (!ignoreLocks)
    RF_UNLOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
  return(NULL);
}

static RF_ParityLogData_t *DequeueMatchingLogData(
  RF_Raid_t            *raidPtr,
  RF_ParityLogData_t  **head,
  RF_ParityLogData_t  **tail)
{
  RF_ParityLogData_t *logDataList, *logData;
  int regionID;

  /* Remove and return an in-core parity log from the tail of
     a disk queue (*head, *tail).  Then remove all matching
     (identical regionIDs) logData and return as a linked list.

     NON-BLOCKING
     */

  logDataList = DequeueParityLogData(raidPtr, head, tail, RF_TRUE);
  if (logDataList)
    {
      regionID = logDataList->regionID;
      logData = logDataList;
      logData->next = rf_SearchAndDequeueParityLogData(raidPtr, regionID, head, tail, RF_TRUE);
      while (logData->next)
	{
	  logData = logData->next;
	  logData->next = rf_SearchAndDequeueParityLogData(raidPtr, regionID, head, tail, RF_TRUE);
	}
    }
  return(logDataList);
}


static RF_ParityLog_t *AcquireParityLog(
  RF_ParityLogData_t  *logData,
  int                  finish)
{
  RF_ParityLog_t *log = NULL;
  RF_Raid_t *raidPtr;

  /* Grab a log buffer from the pool and return it.
     If no buffers are available, return NULL.
     NON-BLOCKING
     */
  raidPtr = logData->common->raidPtr;
  RF_LOCK_MUTEX(raidPtr->parityLogPool.mutex);
  if (raidPtr->parityLogPool.parityLogs)
    {
      log = raidPtr->parityLogPool.parityLogs;
      raidPtr->parityLogPool.parityLogs = raidPtr->parityLogPool.parityLogs->next;
      log->regionID = logData->regionID;
      log->numRecords = 0;
      log->next = NULL;
      raidPtr->logsInUse++;
      RF_ASSERT(raidPtr->logsInUse >= 0 && raidPtr->logsInUse <= raidPtr->numParityLogs);
    }
  else
    {
      /* no logs available, so place ourselves on the queue of work waiting on log buffers
	 this is done while parityLogPool.mutex is held, to ensure synchronization
	 with ReleaseParityLogs.
	 */
      if (rf_parityLogDebug)
	printf("[blocked on log, region %d, finish %d]\n", logData->regionID, finish);
      if (finish)
	RequeueParityLogData(logData, &raidPtr->parityLogDiskQueue.logBlockHead, &raidPtr->parityLogDiskQueue.logBlockTail);
      else
	EnqueueParityLogData(logData, &raidPtr->parityLogDiskQueue.logBlockHead, &raidPtr->parityLogDiskQueue.logBlockTail);
    }
  RF_UNLOCK_MUTEX(raidPtr->parityLogPool.mutex);
  return(log);
}

void rf_ReleaseParityLogs(
  RF_Raid_t       *raidPtr,
  RF_ParityLog_t  *firstLog)
{
  RF_ParityLogData_t *logDataList;
  RF_ParityLog_t *log, *lastLog;
  int cnt;

  /* Insert a linked list of parity logs (firstLog) to 
     the free list (parityLogPool.parityLogPool)

     NON-BLOCKING.
     */

  RF_ASSERT(firstLog);

  /* Before returning logs to global free list, service all
     requests which are blocked on logs.  Holding mutexes for parityLogPool and parityLogDiskQueue
     forces synchronization with AcquireParityLog().
     */
  RF_LOCK_MUTEX(raidPtr->parityLogPool.mutex);
  RF_LOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
  logDataList = DequeueMatchingLogData(raidPtr, &raidPtr->parityLogDiskQueue.logBlockHead, &raidPtr->parityLogDiskQueue.logBlockTail);
  log = firstLog;
  if (firstLog)
    firstLog = firstLog->next;
  log->numRecords = 0;
  log->next = NULL;
  while (logDataList && log)
    {
      RF_UNLOCK_MUTEX(raidPtr->parityLogPool.mutex);
      RF_UNLOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
      rf_ParityLogAppend(logDataList, RF_TRUE, &log, RF_FALSE);
      if (rf_parityLogDebug)
	printf("[finishing up buf-blocked log data, region %d]\n", logDataList->regionID);
      if (log == NULL)
	{
	  log = firstLog;
	  if (firstLog)
	    {
	      firstLog = firstLog->next;
	      log->numRecords = 0;
	      log->next = NULL;
	    }
	}
      RF_LOCK_MUTEX(raidPtr->parityLogPool.mutex);
      RF_LOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);
      if (log)
	logDataList = DequeueMatchingLogData(raidPtr, &raidPtr->parityLogDiskQueue.logBlockHead, &raidPtr->parityLogDiskQueue.logBlockTail);
    }
  /* return remaining logs to pool */
  if (log)
    {
      log->next = firstLog;
      firstLog = log;
    }
  if (firstLog)
    {
      lastLog = firstLog;
      raidPtr->logsInUse--;
      RF_ASSERT(raidPtr->logsInUse >= 0 && raidPtr->logsInUse <= raidPtr->numParityLogs);
      while (lastLog->next)
	{
	  lastLog = lastLog->next;
	  raidPtr->logsInUse--;
	  RF_ASSERT(raidPtr->logsInUse >= 0 && raidPtr->logsInUse <= raidPtr->numParityLogs);
	}
      lastLog->next = raidPtr->parityLogPool.parityLogs;
      raidPtr->parityLogPool.parityLogs = firstLog;
      cnt = 0;
      log = raidPtr->parityLogPool.parityLogs;
      while (log)
	{
	  cnt++;
	  log = log->next;
	}
      RF_ASSERT(cnt + raidPtr->logsInUse == raidPtr->numParityLogs);
    }
  RF_UNLOCK_MUTEX(raidPtr->parityLogPool.mutex);
  RF_UNLOCK_MUTEX(raidPtr->parityLogDiskQueue.mutex);