/*      $NetBSD: rf_stripelocks.c,v 1.35 2021/07/23 00:54:45 oster Exp $        */
/*
* Copyright (c) 1995 Carnegie-Mellon University.
* All rights reserved.
*
* Authors: Mark Holland, Jim Zelenka
*
* Permission to use, copy, modify and distribute this software and
* its documentation is hereby granted, provided that both the copyright
* notice and this permission notice appear in all copies of the
* software, derivative works or modified versions, and any portions
* thereof, and that both notices appear in supporting documentation.
*
* CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
* CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
* FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
*
* Carnegie Mellon requests users of this software to return to
*
*  Software Distribution Coordinator  or  [email protected]
*  School of Computer Science
*  Carnegie Mellon University
*  Pittsburgh PA 15213-3890
*
* any improvements or extensions that they make and grant Carnegie the
* rights to redistribute these changes.
*/

/*
* stripelocks.c -- code to lock stripes for read and write access
*
* The code distinguishes between read locks and write locks. There can be
* as many readers to given stripe as desired. When a write request comes
* in, no further readers are allowed to enter, and all subsequent requests
* are queued in FIFO order. When a the number of readers goes to zero, the
* writer is given the lock. When a writer releases the lock, the list of
* queued requests is scanned, and all readersq up to the next writer are
* given the lock.
*
* The lock table size must be one less than a power of two, but HASH_STRIPEID
* is the only function that requires this.
*
* The code now supports "range locks". When you ask to lock a stripe, you
* specify a range of addresses in that stripe that you want to lock. When
* you acquire the lock, you've locked only this range of addresses, and
* other threads can concurrently read/write any non-overlapping portions
* of the stripe. The "addresses" that you lock are abstract in that you
* can pass in anything you like.  The expectation is that you'll pass in
* the range of physical disk offsets of the parity bits you're planning
* to update. The idea behind this, of course, is to allow sub-stripe
* locking. The implementation is perhaps not the best imaginable; in the
* worst case a lock release is O(n^2) in the total number of outstanding
* requests to a given stripe.  Note that if you're striping with a
* stripe unit size equal to an entire disk (i.e. not striping), there will
* be only one stripe and you may spend some significant number of cycles
* searching through stripe lock descriptors.
*/

#include <sys/cdefs.h>
__KERNEL_RCSID(0, "$NetBSD: rf_stripelocks.c,v 1.35 2021/07/23 00:54:45 oster Exp $");

#include <dev/raidframe/raidframevar.h>

#include "rf_raid.h"
#include "rf_stripelocks.h"
#include "rf_alloclist.h"
#include "rf_debugprint.h"
#include "rf_general.h"
#include "rf_driver.h"
#include "rf_shutdown.h"

#ifdef DEBUG

#define Dprintf1(s,a)         rf_debug_printf(s,(void *)((unsigned long)a),NULL,NULL,NULL,NULL,NULL,NULL,NULL)
#define Dprintf2(s,a,b)       rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),NULL,NULL,NULL,NULL,NULL,NULL)
#define Dprintf3(s,a,b,c)     rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),NULL,NULL,NULL,NULL,NULL)
#define Dprintf4(s,a,b,c,d)   rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),NULL,NULL,NULL,NULL)
#define Dprintf5(s,a,b,c,d,e) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),NULL,NULL,NULL)
#define Dprintf6(s,a,b,c,d,e,f) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),(void *)((unsigned long)f),NULL,NULL)
#define Dprintf7(s,a,b,c,d,e,f,g) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),(void *)((unsigned long)f),(void *)((unsigned long)g),NULL)
#define Dprintf8(s,a,b,c,d,e,f,g,h) rf_debug_printf(s,(void *)((unsigned long)a),(void *)((unsigned long)b),(void *)((unsigned long)c),(void *)((unsigned long)d),(void *)((unsigned long)e),(void *)((unsigned long)f),(void *)((unsigned long)g),(void *)((unsigned long)h))

#else /* DEBUG */

#define Dprintf1(s,a) {}
#define Dprintf2(s,a,b) {}
#define Dprintf3(s,a,b,c) {}
#define Dprintf4(s,a,b,c,d) {}
#define Dprintf5(s,a,b,c,d,e) {}
#define Dprintf6(s,a,b,c,d,e,f) {}
#define Dprintf7(s,a,b,c,d,e,f,g) {}
#define Dprintf8(s,a,b,c,d,e,f,g,h) {}

#endif /* DEBUG */

#define FLUSH

#define HASH_STRIPEID(_sid_)  ( (_sid_) & (rf_lockTableSize-1) )

static void AddToWaitersQueue(RF_StripeLockDesc_t * lockDesc,
                             RF_LockReqDesc_t * lockReqDesc);
static RF_StripeLockDesc_t *AllocStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeNum_t stripeID);
static void FreeStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeLockDesc_t * p);
static RF_LockTableEntry_t *rf_MakeLockTable(void);
#if RF_DEBUG_STRIPELOCK
static void PrintLockedStripes(RF_LockTableEntry_t * lockTable);
#endif

/* determines if two ranges overlap.  always yields false if either
  start value is negative */
#define SINGLE_RANGE_OVERLAP(_strt1, _stop1, _strt2, _stop2)              \
       ( (_strt1 >= 0) && (_strt2 >= 0) &&                               \
         (RF_MAX(_strt1, _strt2) <= RF_MIN(_stop1, _stop2)) )

/* determines if any of the ranges specified in the two lock
  descriptors overlap each other */

#define RANGE_OVERLAP(_cand, _pred)                                       \
 ( SINGLE_RANGE_OVERLAP((_cand)->start,  (_cand)->stop,                  \
                        (_pred)->start,  (_pred)->stop ) ||              \
   SINGLE_RANGE_OVERLAP((_cand)->start2, (_cand)->stop2,                 \
                        (_pred)->start,  (_pred)->stop ) ||              \
   SINGLE_RANGE_OVERLAP((_cand)->start,  (_cand)->stop,                  \
                        (_pred)->start2, (_pred)->stop2) ||              \
   SINGLE_RANGE_OVERLAP((_cand)->start2, (_cand)->stop2,                 \
                        (_pred)->start2, (_pred)->stop2) )

/* Determines if a candidate lock request conflicts with a predecessor
* lock req.  Note that the arguments are not interchangeable.
*
* The rules are:
*
*      a candidate read conflicts with a predecessor write if any
*      ranges overlap
*
*      a candidate write conflicts with a predecessor read if any
*      ranges overlap
*
*      a candidate write conflicts with a predecessor write if any
*      ranges overlap */

#define STRIPELOCK_CONFLICT(_cand, _pred)                                 \
       RANGE_OVERLAP((_cand), (_pred)) &&                                \
       ( ( (((_cand)->type == RF_IO_TYPE_READ) &&                        \
            ((_pred)->type == RF_IO_TYPE_WRITE)) ||                      \
           (((_cand)->type == RF_IO_TYPE_WRITE) &&                       \
            ((_pred)->type == RF_IO_TYPE_READ)) ||                       \
           (((_cand)->type == RF_IO_TYPE_WRITE) &&                       \
            ((_pred)->type == RF_IO_TYPE_WRITE))                         \
         )                                                               \
       )

#define RF_MAX_FREE_STRIPELOCK 128
#define RF_MIN_FREE_STRIPELOCK  32

static void rf_ShutdownStripeLocks(RF_LockTableEntry_t * lockTable);
static void rf_ShutdownStripeLockFreeList(void *);
static void rf_RaidShutdownStripeLocks(void *);

static void
rf_ShutdownStripeLockFreeList(void *arg)
{
       RF_Raid_t *raidPtr;

       raidPtr = (RF_Raid_t *) arg;

       pool_destroy(&raidPtr->pools.stripelock);
}

int
rf_ConfigureStripeLockFreeList(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr,
                              RF_Config_t *cfgPtr)
{
       unsigned mask;

       rf_pool_init(raidPtr, raidPtr->poolNames.stripelock, &raidPtr->pools.stripelock, sizeof(RF_StripeLockDesc_t),
                    "strplock", RF_MIN_FREE_STRIPELOCK, RF_MAX_FREE_STRIPELOCK);
       rf_ShutdownCreate(listp, rf_ShutdownStripeLockFreeList, raidPtr);

       for (mask = 0x1; mask; mask <<= 1)
               if (rf_lockTableSize == mask)
                       break;
       if (!mask) {
               printf("[WARNING:  lock table size must be a power of two.  Setting to %d.]\n", RF_DEFAULT_LOCK_TABLE_SIZE);
               rf_lockTableSize = RF_DEFAULT_LOCK_TABLE_SIZE;
       }
       return (0);
}

static void
rf_DestroyLockTable(RF_LockTableEntry_t *lockTable)
{
       int     i;

       for (i = 0; i < rf_lockTableSize; i++) {
               rf_destroy_mutex2(lockTable[i].mutex);
       }
       RF_Free(lockTable, rf_lockTableSize * sizeof(RF_LockTableEntry_t));
}

static RF_LockTableEntry_t *
rf_MakeLockTable(void)
{
       RF_LockTableEntry_t *lockTable;
       int     i;

       lockTable = RF_Malloc(rf_lockTableSize * sizeof(*lockTable));
       if (lockTable == NULL)
               return (NULL);
       for (i = 0; i < rf_lockTableSize; i++) {
               rf_init_mutex2(lockTable[i].mutex, IPL_VM);
       }
       return (lockTable);
}

static void
rf_ShutdownStripeLocks(RF_LockTableEntry_t * lockTable)
{

#if RF_DEBUG_STRIPELOCK
       if (rf_stripeLockDebug) {
               PrintLockedStripes(lockTable);
       }
#endif
       rf_DestroyLockTable(lockTable);
}

static void
rf_RaidShutdownStripeLocks(void *arg)
{
       RF_Raid_t *raidPtr = (RF_Raid_t *) arg;
       rf_ShutdownStripeLocks(raidPtr->lockTable);
}

int
rf_ConfigureStripeLocks(RF_ShutdownList_t **listp, RF_Raid_t *raidPtr,
                       RF_Config_t *cfgPtr)
{

       raidPtr->lockTable = rf_MakeLockTable();
       if (raidPtr->lockTable == NULL)
               return (ENOMEM);
       rf_ShutdownCreate(listp, rf_RaidShutdownStripeLocks, raidPtr);

       return (0);
}
/* returns 0 if you've got the lock, and non-zero if you have to wait.
* if and only if you have to wait, we'll cause cbFunc to get invoked
* with cbArg when you are granted the lock.  We store a tag in
* *releaseTag that you need to give back to us when you release the
* lock.  */
int
rf_AcquireStripeLock(RF_Raid_t *raidPtr, RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID,
                    RF_LockReqDesc_t *lockReqDesc)
{
       RF_StripeLockDesc_t *lockDesc;
       RF_StripeLockDesc_t *newlockDesc;
       RF_LockReqDesc_t *p;
#if defined(DEBUG) && (RF_DEBUG_STRIPELOCK > 0)
       int     tid = 0;
#endif
       int     hashval = HASH_STRIPEID(stripeID);
       int     retcode = 0;

       RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type));

#if RF_DEBUG_STRIPELOCK
       if (rf_stripeLockDebug) {
               if (stripeID == -1) {
                       Dprintf1("[%d] Lock acquisition suppressed (stripeID == -1)\n", tid);
               } else {
                       Dprintf8("[%d] Trying to acquire stripe lock table 0x%lx SID %ld type %c range %ld-%ld, range2 %ld-%ld hashval %d\n",
                           tid, (unsigned long) lockTable, stripeID, lockReqDesc->type, lockReqDesc->start,
                           lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2);
                       Dprintf3("[%d] lock %ld hashval %d\n", tid, stripeID, hashval);
                       FLUSH;
               }
       }
#endif
       if (stripeID == -1)
               return (0);
       lockReqDesc->next = NULL;       /* just to be sure */
       newlockDesc = AllocStripeLockDesc(raidPtr, stripeID);

       rf_lock_mutex2(lockTable[hashval].mutex);
       for (lockDesc = lockTable[hashval].descList; lockDesc;
            lockDesc = lockDesc->next) {
               if (lockDesc->stripeID == stripeID)
                       break;
       }

       if (!lockDesc) {
               /* no entry in table => no one reading or writing */
               lockDesc = newlockDesc;
               lockDesc->next = lockTable[hashval].descList;
               lockTable[hashval].descList = lockDesc;
               if (lockReqDesc->type == RF_IO_TYPE_WRITE)
                       lockDesc->nWriters++;
               lockDesc->granted = lockReqDesc;
#if RF_DEBUG_STRIPELOCK
               if (rf_stripeLockDebug) {
                       Dprintf7("[%d] no one waiting: lock %ld %c %ld-%ld %ld-%ld granted\n",
                           tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2);
                       FLUSH;
               }
#endif
       } else {
               /* we won't be needing newlockDesc after all.. pity.. */
               FreeStripeLockDesc(raidPtr, newlockDesc);

               if (lockReqDesc->type == RF_IO_TYPE_WRITE)
                       lockDesc->nWriters++;

               if (lockDesc->nWriters == 0) {
                       /* no need to search any lists if there are no
                        * writers anywhere */
                       lockReqDesc->next = lockDesc->granted;
                       lockDesc->granted = lockReqDesc;
#if RF_DEBUG_STRIPELOCK
                       if (rf_stripeLockDebug) {
                               Dprintf7("[%d] no writers: lock %ld %c %ld-%ld %ld-%ld granted\n",
                                   tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2);
                               FLUSH;
                       }
#endif
               } else {

                       /* search the granted & waiting lists for a
                        * conflict.  stop searching as soon as we
                        * find one */
                       retcode = 0;
                       for (p = lockDesc->granted; p; p = p->next)
                               if (STRIPELOCK_CONFLICT(lockReqDesc, p)) {
                                       retcode = 1;
                                       break;
                               }
                       if (!retcode)
                               for (p = lockDesc->waitersH; p; p = p->next)
                                       if (STRIPELOCK_CONFLICT(lockReqDesc, p)) {
                                               retcode = 2;
                                               break;
                                       }
                       if (!retcode) {
                               /* no conflicts found => grant lock */
                               lockReqDesc->next = lockDesc->granted;
                               lockDesc->granted = lockReqDesc;
#if RF_DEBUG_STRIPELOCK
                               if (rf_stripeLockDebug) {
                                       Dprintf7("[%d] no conflicts: lock %ld %c %ld-%ld %ld-%ld granted\n",
                                           tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop,
                                           lockReqDesc->start2, lockReqDesc->stop2);
                                       FLUSH;
                               }
#endif
                       } else {
#if RF_DEBUG_STRIPELOCK
                               if (rf_stripeLockDebug) {
                                       Dprintf6("[%d] conflict: lock %ld %c %ld-%ld hashval=%d not granted\n",
                                           tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop,
                                           hashval);
                                       Dprintf3("[%d] lock %ld retcode=%d\n", tid, stripeID, retcode);
                                       FLUSH;
                               }
#endif
                               AddToWaitersQueue(lockDesc, lockReqDesc);
                               /* conflict => the current access must wait */
                       }
               }
       }

       rf_unlock_mutex2(lockTable[hashval].mutex);
       return (retcode);
}

void
rf_ReleaseStripeLock(RF_Raid_t *raidPtr, RF_LockTableEntry_t *lockTable, RF_StripeNum_t stripeID,
                    RF_LockReqDesc_t *lockReqDesc)
{
       RF_StripeLockDesc_t *lockDesc, *ld_t;
       RF_LockReqDesc_t *lr, *lr_t, *callbacklist, *t;
#if defined(DEBUG) && (RF_DEBUG_STRIPELOCK > 0)
       int     tid = 0;
#endif
       int     hashval = HASH_STRIPEID(stripeID);
       int     release_it, consider_it;
       RF_LockReqDesc_t *candidate, *candidate_t, *predecessor;

       RF_ASSERT(RF_IO_IS_R_OR_W(lockReqDesc->type));

#if RF_DEBUG_STRIPELOCK
       if (rf_stripeLockDebug) {
               if (stripeID == -1) {
                       Dprintf1("[%d] Lock release suppressed (stripeID == -1)\n", tid);
               } else {
                       Dprintf8("[%d] Releasing stripe lock on stripe ID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n",
                           tid, stripeID, lockReqDesc->type, lockReqDesc->start, lockReqDesc->stop, lockReqDesc->start2, lockReqDesc->stop2, lockTable);
                       FLUSH;
               }
       }
#endif
       if (stripeID == -1)
               return;

       rf_lock_mutex2(lockTable[hashval].mutex);

       /* find the stripe lock descriptor */
       for (ld_t = NULL, lockDesc = lockTable[hashval].descList;
            lockDesc; ld_t = lockDesc, lockDesc = lockDesc->next) {
               if (lockDesc->stripeID == stripeID)
                       break;
       }
       RF_ASSERT(lockDesc);    /* major error to release a lock that doesn't
                                * exist */

       /* find the stripe lock request descriptor & delete it from the list */
       for (lr_t = NULL, lr = lockDesc->granted; lr; lr_t = lr, lr = lr->next)
               if (lr == lockReqDesc)
                       break;

       RF_ASSERT(lr && (lr == lockReqDesc));   /* major error to release a
                                                * lock that hasn't been
                                                * granted */
       if (lr_t)
               lr_t->next = lr->next;
       else {
               RF_ASSERT(lr == lockDesc->granted);
               lockDesc->granted = lr->next;
       }
       lr->next = NULL;

       if (lockReqDesc->type == RF_IO_TYPE_WRITE)
               lockDesc->nWriters--;

       /* search through the waiters list to see if anyone needs to
        * be woken up. for each such descriptor in the wait list, we
        * check it against everything granted and against everything
        * _in front_ of it in the waiters queue.  If it conflicts
        * with none of these, we release it.
        *
        * DON'T TOUCH THE TEMPLINK POINTER OF ANYTHING IN THE GRANTED
        * LIST HERE.
        *
        * This will roach the case where the callback tries to
        * acquire a new lock in the same stripe.  There are some
        * asserts to try and detect this.
        *
        * We apply 2 performance optimizations: (1) if releasing this
        * lock results in no more writers to this stripe, we just
        * release everybody waiting, since we place no restrictions
        * on the number of concurrent reads. (2) we consider as
        * candidates for wakeup only those waiters that have a range
        * overlap with either the descriptor being woken up or with
        * something in the callbacklist (i.e.  something we've just
        * now woken up). This allows us to avoid the long evaluation
        * for some descriptors. */

       callbacklist = NULL;
       if (lockDesc->nWriters == 0) {  /* performance tweak (1) */
               while (lockDesc->waitersH) {
                       /* delete from waiters list */
                       lr = lockDesc->waitersH;
                       lockDesc->waitersH = lr->next;

                       RF_ASSERT(lr->type == RF_IO_TYPE_READ);

                       /* add to granted list */
                       lr->next = lockDesc->granted;
                       lockDesc->granted = lr;

                       RF_ASSERT(!lr->templink);
                       /* put on callback list so that we'll invoke
                          callback below */
                       lr->templink = callbacklist;
                       callbacklist = lr;
#if RF_DEBUG_STRIPELOCK
                       if (rf_stripeLockDebug) {
                               Dprintf8("[%d] No writers: granting lock stripe ID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n",
                                   tid, stripeID, lr->type, lr->start, lr->stop, lr->start2, lr->stop2, (unsigned long) lockTable);
                               FLUSH;
                       }
#endif
               }
               lockDesc->waitersT = NULL;
               /* we've purged the whole waiters list */

       } else
               for (candidate_t = NULL, candidate = lockDesc->waitersH;
                    candidate;) {

                       /* performance tweak (2) */
                       consider_it = 0;
                       if (RANGE_OVERLAP(lockReqDesc, candidate))
                               consider_it = 1;
                       else
                               for (t = callbacklist; t; t = t->templink)
                                       if (RANGE_OVERLAP(t, candidate)) {
                                               consider_it = 1;
                                               break;
                                       }
                       if (!consider_it) {
#if RF_DEBUG_STRIPELOCK
                               if (rf_stripeLockDebug) {
                                       Dprintf8("[%d] No overlap: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n",
                                           tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2,
                                           (unsigned long) lockTable);
                                       FLUSH;
                               }
#endif
                               candidate_t = candidate;
                               candidate = candidate->next;
                               continue;
                       }
                       /* we have a candidate for release.  check to
                        * make sure it is not blocked by any granted
                        * locks */
                       release_it = 1;
                       for (predecessor = lockDesc->granted; predecessor;
                            predecessor = predecessor->next) {
                               if (STRIPELOCK_CONFLICT(candidate,
                                                       predecessor)) {
#if RF_DEBUG_STRIPELOCK
                                       if (rf_stripeLockDebug) {
                                               Dprintf8("[%d] Conflicts with granted lock: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n",
                                                   tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2,
                                                   (unsigned long) lockTable);
                                               FLUSH;
                                       }
#endif
                                       release_it = 0;
                                       break;
                               }
                       }

                       /* now check to see if the candidate is
                        * blocked by any waiters that occur before it
                        * it the wait queue */
                       if (release_it)
                               for (predecessor = lockDesc->waitersH;
                                    predecessor != candidate;
                                    predecessor = predecessor->next) {
                                       if (STRIPELOCK_CONFLICT(candidate,
                                                               predecessor)) {
#if RF_DEBUG_STRIPELOCK
                                               if (rf_stripeLockDebug) {
                                                       Dprintf8("[%d] Conflicts with waiting lock: rejecting candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n",
                                                           tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2,
                                                           (unsigned long) lockTable);
                                                       FLUSH;
                                               }
#endif
                                               release_it = 0;
                                               break;
                                       }
                               }

                       /* release it if indicated */
                       if (release_it) {
#if RF_DEBUG_STRIPELOCK
                               if (rf_stripeLockDebug) {
                                       Dprintf8("[%d] Granting lock to candidate stripeID %ld, type %c range %ld-%ld %ld-%ld table 0x%lx\n",
                                           tid, stripeID, candidate->type, candidate->start, candidate->stop, candidate->start2, candidate->stop2,
                                           (unsigned long) lockTable);
                                       FLUSH;
                               }
#endif
                               if (candidate_t) {
                                       candidate_t->next = candidate->next;
                                       if (lockDesc->waitersT == candidate)
                                               lockDesc->waitersT = candidate_t;       /* cannot be waitersH since candidate_t is not NULL */
                               } else {
                                       RF_ASSERT(candidate == lockDesc->waitersH);
                                       lockDesc->waitersH = lockDesc->waitersH->next;
                                       if (!lockDesc->waitersH)
                                               lockDesc->waitersT = NULL;
                               }
                               /* move it to the granted list */
                               candidate->next = lockDesc->granted;
                               lockDesc->granted = candidate;

                               RF_ASSERT(!candidate->templink);
                               /* put it on the list of things to be
                                  called after we release the mutex */
                               candidate->templink = callbacklist;

                               callbacklist = candidate;

                               if (!candidate_t)
                                       candidate = lockDesc->waitersH;
                               else
                                       candidate = candidate_t->next;
                               /* continue with the rest of the list */
                       } else {
                               candidate_t = candidate;
                               /* continue with the rest of the list */
                               candidate = candidate->next;
                       }
               }

       /* delete the descriptor if no one is waiting or active */
       if (!lockDesc->granted && !lockDesc->waitersH) {
               RF_ASSERT(lockDesc->nWriters == 0);
#if RF_DEBUG_STRIPELOCK
               if (rf_stripeLockDebug) {
                       Dprintf3("[%d] Last lock released (table 0x%lx): deleting desc for stripeID %ld\n", tid, (unsigned long) lockTable, stripeID);
                       FLUSH;
               }
#endif
               if (ld_t)
                       ld_t->next = lockDesc->next;
               else {
                       RF_ASSERT(lockDesc == lockTable[hashval].descList);
                       lockTable[hashval].descList = lockDesc->next;
               }
               FreeStripeLockDesc(raidPtr, lockDesc);
               lockDesc = NULL;/* only for the ASSERT below */
       }
       rf_unlock_mutex2(lockTable[hashval].mutex);

       /* now that we've unlocked the mutex, invoke the callback on
        * all the descriptors in the list */

       /* if we deleted the descriptor, we should have no callbacks
        * to do */
       RF_ASSERT(!((callbacklist) && (!lockDesc)));
       for (candidate = callbacklist; candidate;) {
               t = candidate;
               candidate = candidate->templink;
               t->templink = NULL;
               (t->cbFunc) (t->cbArg);
       }
}
/* must have the indicated lock table mutex upon entry */
static void
AddToWaitersQueue(RF_StripeLockDesc_t *lockDesc, RF_LockReqDesc_t *lockReqDesc)
{
       if (!lockDesc->waitersH) {
               lockDesc->waitersH = lockDesc->waitersT = lockReqDesc;
       } else {
               lockDesc->waitersT->next = lockReqDesc;
               lockDesc->waitersT = lockReqDesc;
       }
}

static RF_StripeLockDesc_t *
AllocStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeNum_t stripeID)
{
       RF_StripeLockDesc_t *p;

       p = pool_get(&raidPtr->pools.stripelock, PR_WAITOK);
       if (p) {
               p->stripeID = stripeID;
               p->granted = NULL;
               p->waitersH = NULL;
               p->waitersT = NULL;
               p->nWriters = 0;
               p->next = NULL;
       }
       return (p);
}

static void
FreeStripeLockDesc(RF_Raid_t *raidPtr, RF_StripeLockDesc_t *p)
{
       pool_put(&raidPtr->pools.stripelock, p);
}

#if RF_DEBUG_STRIPELOCK
static void
PrintLockedStripes(RF_LockTableEntry_t *lockTable)
{
       int     i, j, foundone = 0, did;
       RF_StripeLockDesc_t *p;
       RF_LockReqDesc_t *q;

       rf_lock_mutex2(rf_printf_mutex);
       printf("Locked stripes:\n");
       for (i = 0; i < rf_lockTableSize; i++)
               if (lockTable[i].descList) {
                       foundone = 1;
                       for (p = lockTable[i].descList; p; p = p->next) {
                               printf("Stripe ID 0x%lx (%d) nWriters %d\n",
                                   (long) p->stripeID, (int) p->stripeID,
                                      p->nWriters);

                               if (!(p->granted))
                                       printf("Granted: (none)\n");
                               else
                                       printf("Granted:\n");
                               for (did = 1, j = 0, q = p->granted; q;
                                    j++, q = q->next) {
                                       printf("  %c(%ld-%ld", q->type, (long) q->start, (long) q->stop);
                                       if (q->start2 != -1)
                                               printf(",%ld-%ld) ", (long) q->start2,
                                                   (long) q->stop2);
                                       else
                                               printf(") ");
                                       if (j && !(j % 4)) {
                                               printf("\n");
                                               did = 1;
                                       } else
                                               did = 0;
                               }
                               if (!did)
                                       printf("\n");

                               if (!(p->waitersH))
                                       printf("Waiting: (none)\n");
                               else
                                       printf("Waiting:\n");
                               for (did = 1, j = 0, q = p->waitersH; q;
                                    j++, q = q->next) {
                                       printf("%c(%ld-%ld", q->type, (long) q->start, (long) q->stop);
                                       if (q->start2 != -1)
                                               printf(",%ld-%ld) ", (long) q->start2, (long) q->stop2);
                                       else
                                               printf(") ");
                                       if (j && !(j % 4)) {
                                               printf("\n         ");
                                               did = 1;
                                       } else
                                               did = 0;
                               }
                               if (!did)
                                       printf("\n");
                       }
               }
       if (!foundone)
               printf("(none)\n");
       else
               printf("\n");
       rf_unlock_mutex2(rf_printf_mutex);
}
#endif

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.