Re: [PATCH] Lightweight userspace semaphores...

[Hubertus Franke]

On Wed, Feb 27, 2002 at 11:24:17AM +1100, Rusty Russell wrote:
> OK.  New implementation.  Compiles (PPC), but due to personal reasons,
> UNTESTED.  Thanks especially to Hubertus for his prior work and
> feedback.
>
> 1) Turned into syscalls.
> 2) Added arch-specific sys_futex_region() to enable mutexes on region,
>    and give a chance to detect lack of support via -ENOSYS.
> 3) Just a single atomic_t variable for mutex (thanks Paul M).
> - This means -ENOSYS on SMP 386s, as we need cmpxchg.

> - We can no longer do generic semaphores: mutexes only.
> - Requires arch __update_count atomic op.

    I don't see that, you can use atomic_inc on 386s ..

> 4) Current valid args to sys_futex are -1 and +1: we can implement
>    other lock types by using other values later (eg. rw locks).
>

  (seem below) 

> Size of futex.c dropped from 244 to 161 lines, so it's clearly 40%
> better!
>
> Get your complaints in now...

  (plenty below :-)

> Rusty.
> --
>   Anyone who quotes me in their sig is an idiot. -- Rusty Russell.
>

Rusty, as indicated I think there is quite some merit to this solution
and it certainly cuts down on some of the complexity that is inherent in
what I submitted.
First, what I like is the fact that by pinning the page down you avoid the
extra indirection that I went through with the kulock_ref_t objects.

There are some limitations to your approach however.

(a) the hashing is to simple. As a consequence there are two limitations
     -  the total number of locks that can be waited for is 
        (1<< USEM_HASHBITS).
        that is way not enough (as you pointed out).
     - this has to be bumped up to roughly the number of tasks in the
       system.
       since each wait_queue_head_t element has 3 words, MAX_PID = 32K
       this would end up with about 400K of memory for this. This would be
       the worst case scenario, namely that every task in the system is 
       waiting on a different lock (hey shit happens).

more seriously though is the following.
(b) there is no provision to what to do when there is a hash collision?
      this seems too rudimentary that I assume I am missing something, 
      in case not:
      if <page1,offset1> and <page2,offset2> both result in the same
      hash value then they will be both waiting on the same wait queue, 
      which is incorrect.

     A solution to this would be to introduce hash chaining as I have done
     through my access vector cache and allocate the waitqueue objects from 
     the cachep object and link them through it. An alternative solution is
     to provide a sufficiently large queue as described in (a) and on collision
     go for a secondary hash function and if that fails search for an empty 
     bucket. In the current situation, I think the second solution might be
     more appropriate.

(c) your implementation could be easily expanded to include Ben's
    suggestion of multiple queues (which I already implement in my 
    submission), by including the queue index into the hashing mechanism.
    Since you are rewriting the wait routine, the problem can be circumvented
    if we can settle for mutex, semaphores, and rwlocks only. Ben what's your
    take. In rwlocks you signal continuation of the next class of holders.
    Then you wake up one writer or the next set of readers, or based on 
    some other parameter, if the first candidate you find is a reader you
    walk the entire list to wake up all readers. Lot's of stuff that can be
    done here. What you need then is to expand your wait structure in this
    case to indicate why you are sleeping, waiting for read or waiting for
    write.   What do you think.

(d) If (b) is magically solved, then I have no take yet regarding cleanup.
    If not, then given (b), your cleanup will become expensive and you 
    will end up in a similar solution as I have it, namely a callback on 
    vmarea destruction and some ref counting. 

(e) In your solution you use throughout cmpxchg, which limits you from 
    utilizing atomic_inc/dec functions on i386.
    I have based my mutex implementation in user space on atomic_inc
    Spinning versions require cmpxchg though.
    Maybe it might be useful to differentiate these cases and provide at
    least non spinning versions for i386.

(f) Why get away from semaphores and only stick to mutexes. Isn't there
    some value to provide counting semaphores ? Effectively, mutexes are
    a subclass of semaphores with a max-count of 1.

(g) I don't understand the business of rechecking in the kernel. In your
    case it comes cheap as you pinned the page already. In general that's 
    true, since the page was just touched the pinning itself is reasonable
    cheap. Nevertheless, I am concerned that now you need intrinsic knowledge
    how the lock word is used in user space. For instance, I use it in 
    different fashions, dependent whether its a semaphore or rwlock.
    Why can't we keep that separated from the kernel function of waiting
    on an event that is signaled along the lock word, the content of the lock 
    word should not come into play in the kernel. 
    If you want this, you use spinning locks.

(h) how do you deal with signals ? E.g. SIGIO or something like it.

Overall, pinning down the page (assuming that not a lot of tasks are
waiting on a large number of queues at the same time) is acceptable, 
and it cuts out one additional level of indirection that is present 
in my submission.

-- Hubertus Franke ([e-mail])