Lightweight user-level semaphores
Quoted 3 lines
Actually, the more I look at Linus's original idea, the more sense it seems to make (and the more I regret scrapping my almost-complete implementation of it for the fd idea :)
Do you have a plan how to implement the no-contention case entirely in userspace?
That would make them really fast, not just saving 50 or 100 cycles through a special syscall and bypassing VFS.
--
Manfred
Quoted 8 lines · Manfred Spraul
Quoted 3 lines
Actually, the more I look at Linus's original idea, the more sense it seems to make (and the more I regret scrapping my almost-complete implementation of it for the fd idea :)
Do you have a plan how to implement the no-contention case entirely in userspace?
That would make them really fast, not just saving 50 or 100 cycles through a special syscall and bypassing VFS.
Yep, it was really easy. Following Linus' design[0] it was a really easy hack[1].
I'd like these things to be really easily shareable, and that's harder to do when you need to communicate a mapped area and a file descriptor.
But without an obvious handle, it's hard to collect unreferenced locks.
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.
Matthew.
[0] http://lwn.net/2001/0419/a/lt-semaphores.php3
[1] Kernel patch: http://hairy.beasts.org/usersem-2.4.17.diff
(I have a more complete patch on a machine which isn't up right now.)
Userspace bit: http://hairy.beasts.org/ust.tar.gz
Quoted 4 lines
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.
Alan
Quoted 5 lines · Alan Cox
Quoted 4 lines
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.
Quoted 7 lines
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.
Quoted 6 lines · Matthew Kirkwood
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.
pread(), use the file pointer.
Quoted 5 lines
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.
I'd start with file descriptor+pread(), and then check how much faster your could get without any protection at all (i.e. just trust user space). If the difference is small, then use the file descriptor.
--
Manfred
Quoted 3 lines
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.
If I have to have 2000 pages and 2000 file handles for 2000 locks I've kind of lost interest. read/write syscalls take offsets. I can pread/pwrite a lock in a set of locks. The only reason for using an fd I can see is so you can poll on a lock. All the other neatness issues are wrapped in the library support code anyway.
Quoted 3 lines
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.
Read my old mail you need neither a hash table or a tree. You just need the required shadow object
offset = addr - vma->vm_start; offset /= sizeof(struct user_lock); lock = ((struct lock *)vma->vm_private_data)[offset];
Alan
Quoted 9 lines · On Sun, 13 Jan 2002 15:13:30 +0000 (GMT) Alan Cox <[email protected]>…
Quoted 3 lines
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.
If I have to have 2000 pages and 2000 file handles for 2000 locks I've kind of lost interest. read/write syscalls take offsets. I can pread/pwrite a lock in a set of locks. The only reason for using an fd I can see is so you can poll on a lock. All the other neatness issues are wrapped in the library support code anyway.
My interest in this is for TDB (Trivial Database: see sourceforge). TDB requires a lock per hash chain (ie. arbitrary number of locks), a number which does not change. With an extended version of the fd code (ie. first mmap controls size of map, and offset control which semaphore you are referring to, and semaphores created on demand), this requires:
Each TDB would have an associated ".locks" unix domain socket so you can read the fd from the "master". This must be atomically created by the first process to open the TDB, and must be asynchronously serviced by a process at all times (ie. when the "master" exits, someone else takes over).
Without even mentioning the impossibility of creating a Unix domain socket with an arbitrary path name (can't chdir, might not be able to chdir back), or the problem of cleaning up the socket when noone is using the tdb, or the horror which is fd passing under Unix, I think it's clear that the fd solutions are vastly inferior to the "magic cookie" approach.
Still, it was cute hack.
Rusty.
Signature · 1 line
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.