Re: [PATCH][RFC] Lightweight user-level semaphores

[Matthew Kirkwood]

On Fri, 11 Jan 2002, Alan Cox wrote:

> > Rusty's idea is nice (though I think it'd be better
> > with a filesystem than a device, so you can share
> > names rather than file descriptors) but the page per
> > lock seems like rather too much overhead.
>
> I don't think its a big problem. A page gets you 256 locks or whatever
> the number ends up as. For the case where you have many fine grained
> locks between a group of threads thats great. You just parcel them
> out. If its two processes just wanting a lock between them, well they
> get a page with room for 256 lock objects, but they only want one.
> That doesn't matter.  Its one page, if they need two or two hundred
> locks its stil one page.

Yep, that'd be fine.  However, you then lose the neatness
of "lock==file descriptor", and need something other than
read/write for down/up.

So I think that the original idea of storing an opaque
cookie which, it happens, we can lookup to a kernel address,
is the way forward.  Linus' design had:

	/*
	 * Verify that it might be a valid kernel pointer
	 * before we even try to dereference it
	 */
	if ((unsigned long) kfs & 7)
		goto bad_sem;
	if (kfs < TASK_SIZE)
		goto bad_sem;
	if (kfs > TASK_SIZE+640k && kfs < TASK_SIZE + 1M)
		goto bad_sem;
	if (kfs > high_mem)
		goto bad_sem;

which is a bit magic (and, no doubt, non-portable), but
doesn't look entirely unreasonable.

I guess the alternative is to store them in a hash table
or tree but I don't know what that would do to the
contended case.

Matthew.