Re: spinaphore conceptual draft (was discussion of RT patch)

[Kyle Moffett <mrmacman_g4@mac.com>]

On May 27, 2005, at 18:31:38, David Nicol wrote:
> On 5/26/05, john cooper <john.cooper@timesys.com> wrote:
>
>> given design.  Clearly we aren't buying anything to trade off
>> a spinlock protecting the update of a single pointer with a
>> blocking lock and associated context switching.
>
> On contention, and only on contention, we are faced with the  
> question of what
> to do.  Do we wait, or do we go away and come back later?  What  
> information is
> available to us to base the decision on?  We can't gather any more  
> information,
> because that would take longer than spin-waiting.  If the  
> "spinaphore" told us,
> on acquisition failure, how many other threads were asking for it, we
> could implement
> a tunable lock, that surrenders context when there are more than N
> threads waiting for
> the resource, and that otherwise waits its turn, or its chance,  as  
> a compromise
> and synthesis.

Here is an example naive implementation which could perhaps be  
optimized further
for architectures based on memory and synchronization requirements.

A quick summary:
Each time the lock is taken and released, a "hold_time" is updated  
which indicates
the average time that the lock is held.  During contention, each CPU  
checks the
current average hold time and the number of CPUs waiting against a  
predefined
"context switch + useful work" time, and goes to sleep if it thinks  
it has enough
time to spare.

Problems:
You can't nest these.  You also can't take a normal semaphore inside  
one.  The
only useable locking order for these is:
..., semaphore, semaphore, spinaphore, spinlock, spinlock, ...

Possible Solution:
If you had a reliable way of determining when it is safe to sleep,  
you could call
a "cond_resched_if_nonatomic()" function instead of cond_resched()  
and allow
nesting of spinaphores within each other and within spinlocks.  I  
_do_ implement a
spinaphore_lock_atomic which is guaranteed not to sleep and could be  
used within
other locks instead.

struct spinaphore {
     atomic_t queued;
     atomic_t hold_time;
     spinlock_t spinlock;
     unsigned long acquire_time;
};

void spinaphore_lock (struct spinaphore *sph) {
     unsigned long start_time = fast_monotonic_count();
     int queue_me = 1;
     until (likely(spin_trylock(&sph->spinlock))) {

         /* Get the queue count (And ensure we're queued in the  
process) */
         unsigned int queued = queue_me ?
                 atomic_inc_return(&sph->queued) :
                 queued = atomic_get(&sph->queued);
         queue_me = 0;

         /* Figure out if we should switch away */
         if (unlikely(CONFIG_SPINAPHORE_CONTEXT_SWITCH <
                 ( queued*atomic_get(&sph->hold_time) -
                   fast_monotonic_count() - start_time
                 ))) {
             /* Remove ourselves from the wait pool (remember to re- 
add later) */
             atomic_dec(&sph->queued);
             queue_me = 1;

             /* Go to sleep */
             cond_resched();
         }
     }

     /* Dequeue ourselves and update the acquire time */
     atomic_dec(&sph->queued);
     sph->acquire_time = fast_monotonic_count();
}

void spinaphore_lock_atomic (struct spinaphore *sph) {
     /* Let the other processes know what we're doing */
     atomic_inc(&sph->queued);

     /* Just get the lock the old fashioned way */
     spin_lock(&sph->spinlock);

     /* Dequeue ourselves and update the acquire time */
     atomic_dec(&sph->queued);
     sph->acquire_time = fast_monotonic_count();
}

int spinaphore_trylock (struct spinaphore *sph) {
     /* Try to get the lock, and if so, update the acquire time */
     if (spin_trylock(&sph->spinlock)) {
         sph->acquire_time = fast_monotonic_count();
}

void spinaphore_unlock (struct spinaphore *sph) {
     /* Update the running average hold time */
     atomic_set(&sph->hold_time, (4*atomic_get(&sph->hold_time) +
             (fast_monotonic_count() - sph->acquire_time))/5);

     /* Actually unlock the spinlock */
     spin_unlock(&sph->spinlock);
}

Cheers,
Kyle Moffett

-----BEGIN GEEK CODE BLOCK-----
Version: 3.12
GCM/CS/IT/U d- s++: a18 C++++>$ UB/L/X/*++++(+)>$ P+++(++++)>$
L++++(+++) E W++(+) N+++(++) o? K? w--- O? M++ V? PS+() PE+(-) Y+
PGP+++ t+(+++) 5 X R? tv-(--) b++++(++) DI+ D+ G e->++++$ h!*()>++$  
r  !y?(-)
------END GEEK CODE BLOCK------