Re: [PATCH] Lightweight userspace semaphores...

[Hubertus Franke <frankeh@watson.ibm.com>]

All, I uploaded my latest version on this to lse.sourceforge.net
you can get to by http://prdownloads.sourceforge.net/lse/ulocks-2.4.17.tar.bz2

Hope you find some time to look at it and respond to the questions
and positions I outlined in the message before.

-- Hubertus Franke

On Mon, Feb 25, 2002 at 01:23:35PM -0500, Hubertus Franke wrote:
> On Mon, Feb 25, 2002 at 11:32:40AM -0500, Benjamin LaHaise wrote:
> > On Mon, Feb 25, 2002 at 04:39:56PM +0000, Alan Cox wrote:
> > > _alloca
> > > mmap
> > > 
> > > Still fits on the stack 8)
> > 
> > Are we sure that forcing semaphore overhead to the size of a page is a 
> > good idea?  I'd much rather see a sleep/wakeup mechanism akin to wait 
> > queues be exported by the kernel so that userspace can implement a rich 
> > set of locking functions on top of that in whatever shared memory is 
> > being used.
> > 
> > 		-ben
> > -
> 
> Amen, I agree Ben. As I indicated in my previous note, one can
> implement various versions of spinning, starvation, non-starvation locks
> based on the appropriateness for a given app and scenario.
> For instance the multiple reader/single writer requires 2 queues.
> If as Ben stated something similar to the SysV implementation is desired
> where a single lock holds multiple waiting queues, that should be straight
> forward to implement. Waiting queues could be allocated on demand as well.
> 
> I'd like to see an implementation that facilitate that.
> My implementation separates the state to the user level and the 
> waiting to the kernel level. There are race conditions that need to 
> be resolved with respect to wakeup. They can be all encoded into
> the atomic word maintained in shared memory in user space.
> 
> For more complex locks I'd like to have compare_and_swap instructions.
> As I stated, I have implemented some of the more complicated locks
> (spinning, convoy avoidance, etc.) and they have all passed some rigorous
> stress test.
> 
> As for allocation on the stack. If indeed there are kernel objects
> associated with the address, they need to be cleared upon exit from
> the issueing subroutine (at least in my implementation).
> 
> 
> At this point, could be go through and delineate some of the requirements
> first.
> E.g.  (a) filedescriptors vs. vaddr
>       (b) explicit vs. implicite allocation  
>       (c) system call interface vs. device driver
>       (d) state management in user space only or in kernel as well
> 	        i.e. how many are waiting, how many are woken up.
>       (e) semaphores only or multiple queues
>       (f) protection through an exported handle with some MAGIC or
>           through virtual memory access rights
>       (g) persistence on mmap or not 
> 
> Here is my point of view:
> (a) vaddr 
> (b) implicite
> (c) syscall
> (d) user only
> (e) multiple queues
> (f) virtual memory access rights.
> (g) persistent  (if you don't want persistence you remove the underlying object)
> 	
> I requested some input on my original message a couple of weeks regarding 
> these points (but only got one on (b)).
> 
> Could everybody respond to (a)-(f) for a show of hands.
> Could we also consolidate some pointers of the various implementations
> that are out there and then see what the pluses and minuses of the various
> implementations are  and how they score against (a)-(f).
> 
> -- Hubertus Franke
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/