Lightweight userspace semaphores...

Hi all,

There are several lightweight userspace semaphore patches
flying around, and I'll really like to meld into one good solution we can include in 2.5.

This version uses wli's multiplicitive hashing. And it has
these yummy properties:

1) Interface is: open /dev/usem, pread, pwrite.
2) No initialization required: just tell the kernel "this is a
semaphore: down/up it".
3) No in-kernel arch-specific code.
4) Locks in mmaped are persistent (including across reboots!).

Modifications for tdb to use this interface were pretty trivial (too bad it proved no faster than fcntl locks, more investigation needed).

User library and kernel patch attached,
Rusty.
PS. map_usem() is ugly: is there a better way to pin pages? --
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/drivers/char/Config.help working-2.5.5-usem/drivers/char/Config.help
@@ -1153,3 +1153,9 @@
 
   Not sure? It's safe to say N.
 
+CONFIG_USERSEM
+  Say Y here to have support for fast userspace semaphores, or M to
+  compile it as a module called usersem.o.
+
+  If unsure, say Y: everyone else will and you wouldn't want to miss
+  out.

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/drivers/char/Config.in working-2.5.5-usem/drivers/char/Config.in
@@ -227,4 +227,5 @@
    tristate 'ACP Modem (Mwave) support' CONFIG_MWAVE
 fi
 
+dep_tristate 'Fast userspace semaphore support (EXPERIMENTAL)' CONFIG_USERSEM $CONFIG_EXPERIMENTAL
 endmenu

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/drivers/char/Makefile working-2.5.5-usem/drivers/char/Makefile
@@ -229,6 +229,7 @@
 obj-$(CONFIG_SH_WDT) += shwdt.o
 obj-$(CONFIG_EUROTECH_WDT) += eurotechwdt.o
 obj-$(CONFIG_SOFT_WATCHDOG) += softdog.o
+obj-$(CONFIG_USERSEM) += usersem.o
 
 subdir-$(CONFIG_MWAVE) += mwave
 ifeq ($(CONFIG_MWAVE),y)

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/include/linux/mmzone.h working-2.5.5-usem/include/linux/mmzone.h
@@ -51,8 +51,7 @@
 	/*
 	 * wait_table		-- the array holding the hash table
 	 * wait_table_size	-- the size of the hash table array
-	 * wait_table_shift	-- wait_table_size
-	 * 				== BITS_PER_LONG (1 << wait_table_bits)
+	 * wait_table_bits	-- wait_table_size == (1 << wait_table_bits)
 	 *
 	 * The purpose of all these is to keep track of the people
 	 * waiting for a page to become available and make them

@@ -75,7 +74,7 @@
 	 */
 	wait_queue_head_t	* wait_table;
 	unsigned long		wait_table_size;
-	unsigned long		wait_table_shift;
+	unsigned long		wait_table_bits;
 
 	/*
 	 * Discontig memory support fields.

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/kernel/ksyms.c working-2.5.5-usem/kernel/ksyms.c
@@ -86,6 +86,7 @@
 EXPORT_SYMBOL(do_munmap);
 EXPORT_SYMBOL(do_brk);
 EXPORT_SYMBOL(exit_mm);
+EXPORT_SYMBOL(get_user_pages);
 
 /* internal kernel memory management */
 EXPORT_SYMBOL(_alloc_pages);

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/mm/filemap.c working-2.5.5-usem/mm/filemap.c
@@ -25,6 +25,7 @@
 #include <linux/iobuf.h>
 #include <linux/compiler.h>
 #include <linux/fs.h>
+#include <linux/hash.h>
 
 #include <asm/pgalloc.h>
 #include <asm/uaccess.h>

@@ -773,32 +774,8 @@
 static inline wait_queue_head_t *page_waitqueue(struct page *page)
 {
 	const zone_t *zone = page_zone(page);
-	wait_queue_head_t *wait = zone->wait_table;
-	unsigned long hash = (unsigned long)page;
 
-#if BITS_PER_LONG == 64
-	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
-	unsigned long n = hash;
-	n <<= 18;
-	hash -= n;
-	n <<= 33;
-	hash -= n;
-	n <<= 3;
-	hash += n;
-	n <<= 3;
-	hash -= n;
-	n <<= 4;
-	hash += n;
-	n <<= 2;
-	hash += n;
-#else
-	/* On some cpus multiply is faster, on others gcc will do shifts */
-	hash *= GOLDEN_RATIO_PRIME;
-#endif
-
-	hash >>= zone->wait_table_shift;
-
-	return &wait[hash];
+	return &zone->wait_table[hash_ptr(page, zone->wait_table_bits)];
 }
 
 /* 

diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/mm/page_alloc.c working-2.5.5-usem/mm/page_alloc.c
@@ -776,8 +776,8 @@
 		 * per zone.
 		 */
 		zone->wait_table_size = wait_table_size(size);
-		zone->wait_table_shift =
-			BITS_PER_LONG - wait_table_bits(zone->wait_table_size);
+		zone->wait_table_bits =
+			wait_table_bits(zone->wait_table_size);
 		zone->wait_table = (wait_queue_head_t *)
 			alloc_bootmem_node(pgdat, zone->wait_table_size
 						* sizeof(wait_queue_head_t));

i like the patch, but the interface is ugly IMO. Why not new syscalls? I think these lightweight semaphores will become an important part of Linux, so having their own syscall entries is the most correct interface, something like:

sys_sem_create()
sys_sem_destroy()
sys_sem_down()
sys_sem_up()

/dev/usem is such an ... ioctl()-ish approach. It's a scalability problem as well: read()/write() has (or can have) some implicit locking that is imposed on the usem interface as well. It's a usage robustness issue as
well: chroot() environments that have no /dev directory will suddenly lose a functionality of Linux. There is absolutely no problem with adding new syscalls for things like this.

Plus sys_sem_create() should do some proper resource limit management, pinning down an unlimited number of pages is bad.

Ingo

I agree - I dislike magic device files a whole lot more than just abotu every alternative.

Also, one thing possibly worth looking into is to just put the actual semaphore contents into a regular file backed setup.

Linus

Exactly. SMP gives you coherent memory and test-and-set or some other atomic operation. Why not use it?

---
Larry McVoy            	 lm at bitmover.com           http://www.bitmover.com/lm 

the userspace library side does it. The kernel patch is the slowpath, the fast path (no contention) happens in user-space, using SMP-atomic instructions. It's all very nice and lightweight.

also as far as i can see, this implementation enables semaphores to live anywhere within the VM, the /dev/usem is just a hack to communicate this VM address to the kernel-space code. So i think the patch's concepts are really nice, except the interface cleanliness issue which shouldnt be too hard to fix - adding new syscalls is pleasant work anyway :-)

Ingo

Coherent memory on some platforms, locks on some platforms. Fortunately both on several important architectures. It needs a much cleaner API but in user space to wrap the user mode/kernel mode mixed locks. You need the kernel side for sleeping cases

In message <[email protected]> you write:

There is no create and destroy (init is purely userspace). There is "this is a semapore: up it". This is a feature.

Agreed with implicit locking: good catch. Disagree with neatness: I like finding out in advance that there's no fast semaphore support.

Since pages are pinned "on demand" and a process can only do one syscall at a time, the maximum number of pinned pages per process ==
2. Which is fine.

Will do syscall version, and see if I can actually get it to beat fcntl locking on reasonable benchmarks (ie. tdbtorture).

Cheers!
Rusty.
PS. Nomenclature: my fiance suggested FUS (Fast Userspace
Semaphores), and I am legally obliged to agree.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

No, that's a bug.

You have to realize that there are architectures that need special initialization and page allocation for semaphores: they need special flags in the TLB for "careful access", for example (sometimes the careful access ends up being non-cached).

You can't just put semaphores anywhere and tell the kernel to try to fix up whatever happened.

Linus

In message <[email protected]> you wr ite:

Bugger. How about:

sys_sem_area(void *pagestart, size_t len) sys_unsem_area(void *pagestart, size_t len)

Is that sufficient? Is sys_unsem_area required at all?

TDB has an arbitrary number of semaphores in the mmap file... Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

The above is sufficient, but I would personally actually prefer an interface more like

	fd = sem_initialize();
	mmap(fd, ...)
	..
	munmap(..)

which gives you a handle for the semaphore.

Note that getting a file descriptor is really quite useful - it means that you can pass the file descriptor around through unix domain sockets, for example, and allow sharing of the semaphore across unrelated processes that way.

Also, the fd thus acts as an "anchor" for any in-kernel data structures that the semaphore implementation may (or may not) want to use. Think of it as your /dev/usem, except with a more explicit interface.

And make the initial mmap() only do a limited number of pages, so that people don't start trying to allocate tons of memory this way.-

Linus

	fd = open("/dev/shm/sem....");
	mmap(fd, ...)

	munmap(..)

That lets the kernel decide what it wants to do and provide as the back end. It allows you to think about things like mremap and growing/shrinking the object. And finally /dev/sem looks suspiciously like a quick tweak to /dev/shm..

If it uses the /dev/shm world then anyone running a kernel with the new patches for resource accounting is still safe, and anyone else is still simply going to find their shm areas hitting swap under extreme load (which is ideal)

Hmm.. Yes. Except I would allow a NULL backing store name for the normal(?) case of just wanting private anonymous memory.

At the same time, I have to admit that I like the notion that Rusty had of libraries being able to just put their semaphores anywhere (on the stack etc), as it does work for many architectures. Ugh.

Linus

unlink()

_alloca
mmap

Still fits on the stack 8)

Sure, but that, together with making up a unique temporary name etc just adds extra overhead for no actual gain.

.. but is slow as hell.

Linus

As opposed to adding special cases to the kernel which are unswappable and stand to tangle up bits of the generic vfs - eg we would have a vma with a vm_file but that file would not be in the dcache ?

Is it really worth it. For temporary files unix has never adopted a tmpfile() syscall because nobody has ever found mkstemp() a paticularly critical path that justified it

Why should they be unswappable?

It's the same thing as giving a -1 to mmap. That doesn't make it unswappable.

Linus

Any kernel special cases it adds will be unswappable because they are in kernel space (not the semaphores here - we want them to be swappable and they can be)

When you create a shared mapping by passing -1 to mmap we do

        } else if (flags & MAP_SHARED) {
                error = shmem_zero_setup(vma);

shmem_zero_setup does

        file = shmem_file_setup("dev/zero", size);
        if (IS_ERR(file))
                return PTR_ERR(file);

        if (vma->vm_file)
                fput (vma->vm_file);
        vma->vm_file = file;
        vma->vm_ops = &shmem_vm_ops;

and we are back creating file names. Basically because a shared mmap in Linux needs vma->vm_file, and vma->vm_file needs all the rest of the logic behind it

Thats why I am saying that magic name picking is something that user space might as well do for unnamed objects. We end up with names and vm_file however we do it

Alan, wake up!

I'm talking about anonymous semaphores, the kernel implementation can just map a normal anonymous page there.

On 99.9% of all machines out there, you can have semaphores in perfectly normal memory.

Why are you talking about shared mappings?

The most common case for any fast semaphores are for _threaded_ applications. No shared memory, no nothing.

Linus

Ok I see where you are coming from now -- that makes sense for a few cases. POSIX thread locks have to be able to work interprocess not just between threads though, so a full posix lock implementation couldn't be done without being able to put these things on shared pages (hence I was coming from the using shmfs as backing store angle). Using a subset of shmfs also got me resource management which happens to be nice.

The other user of these kind of fast locks is databases. Oracle for example seems not to be a single mm threaded application.

If we are talking about being able to say "make this page semaphores" then I agree - the namespace is a seperate problem and up to whoever allocated the backing store in the first place, and may well not involve a naming at all.

Note that the "few cases" in question imply _all_ of the current broken library spinlocks, for example.

Don't think "POSIX semaphores", but think "fast locking" in the general case. I will bet you $1 in small change that most normal locking by far is for the kind of thread-safe stuff libc does right now.

Linus

This looks like another piece of the equation needed to make Larry's smp cluster concept come true. So...

Daniel

Well, but most threaded applications should actually take care of this without having to ditch into the kernel.

With respect to global POSIX locks:
I talked to Bill Abt of the NGPT team and we planned of introducing an asynchronous mechanism to the user level lock package that I submitted some 2 weeks ago. The problem here is that in NGPT like packages the underlying kernel thread can not be blocked on a wait call, because it constitutes a virtual CPU on which multiple user level threads are run. So what we were thinking of is on a wait call to the kernel a datastructure is put in place on which to wait rather than blocking on the calling thread. On wakeup, the initial process will be signaled that one of the locks is available again. The user level thread scheduler can then pick up the lock (many mechanism possible) and continue the user level thread waiting on it.

What I implemented is what Linus recommended, namely indicate whether a memory region is capable of being utilized for user level locks. We need this for cleanup, i.e., when a process exits or dies, and the vma area is closed/removed, we know when to call back the kernel subsystem holding the kernel locks associated with user level locks and clean up lingering objets.

This works quite nice. I did this in my implementation and it requires basically 4 line changes in the kernel.
The flag MAP_SEMAPHORE is to be introduced for mmap and shmat. One problem is that libc seems to mask out any flags that is currently not exposed by the kernel.

-- Hubertus

Hello!

Most importantly this patch is making ide.c use the
new automagic for module initialization lists and further preparing the rest of the code in question here for proper module separation. Despite this the CMOS probe has been removed as well... *Iff*, which I don't expect, this breaks anything it can be reintroduced easely. During this effort an actual bug in the initialization of the main module has been uncovered as well. a quite serious BUG has been tagged in ide-scsi.c as well, but as far as now I just didn't get along to actually fixing it. (The patch is big enough as it is).

Details follow:

- Kill *unused* ide_media_verbose() funciton.

- Remove the unnecessary media and supports_dma fields from ide_driver_t.

- Remove the global name field from ide_driver_t struct by pushing it down to the places where it's actually used.

- Remove the unused hwif_data field from ide_hwif_t.

- Push the supports_dsc_overlap condition up to the level where it
belongs: disk type as well.

- Make the initialization of ide main ide.c work with the new module initialization auto-magic instead of calling it explicitly in ll_rw_block.c This prevents the ide_init() from being called twice. We have BTW. renamed it to ata_module_init(), since ata is more adequate then ide and xxx_module_init corresponds better to the naming conventions used elsewhere throughout the kernel.

This BUG was there before any ide-clean. It was worked around by a magic variable preventing the second call to succeed. We have removed this variable in one of the previous patches and thus uncovered it.

- Kill proc_ide_read_driver() and proc_ide_write_driver(). The drivers already report on syslog which drives they have taken care of. (Or at least they should). In esp. the proc_ide_write_driver() was just too offending for me. Beleve it or not the purpose of it was to *request a particular* driver for a device, by echoing some magic values to a magic file...
More importantly this "back door" was getting in the way of a properly done modularization of the IDE stuff.

- Made some not externally used functions static or not EXPORT-ed.

- Provide the start of a proper modularization between the main module and drivers for particular device types. Changing the name-space polluting DRIVER() macro to ata_ops() showed how inconsistently the busy (read: module busy!) field from ide_driver_t
is currently used across the different device type modules.
This has to be fixed soon.

- Make the ide code use the similar device type ID numbers as the SCSI code :-). This is just tedious, but it will help in a distant feature. It helps reading the code anyway.

- Mark repettitive code with /* ATA-PATTERN */ comments for later consolidation at places where we did came across it.

- Various comments and notes added where some explanations was missing.

diff -ur linux-2.5.5/drivers/block/ll_rw_blk.c linux/drivers/block/ll_rw_blk.c
@@ -1697,9 +1697,6 @@
 	blk_max_low_pfn = max_low_pfn;
 	blk_max_pfn = max_pfn;
 
-#if defined(CONFIG_IDE) && defined(CONFIG_BLK_DEV_IDE)
-	ide_init();		/* this MUST precede hd_init */
-#endif
 #if defined(CONFIG_IDE) && defined(CONFIG_BLK_DEV_HD)
 	hd_init();
 #endif

diff -ur linux-2.5.5/drivers/ide/aec62xx.c linux/drivers/ide/aec62xx.c
@@ -48,7 +48,6 @@
 
 static int aec62xx_get_info(char *, char **, off_t, int);
 extern int (*aec62xx_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int aec62xx_get_info (char *buffer, char **addr, off_t offset, int count)

@@ -310,8 +309,8 @@
 	unsigned long dma_base	= hwif->dma_base;
 	byte speed		= -1;
 
-	if (drive->media != ide_disk)
-		return ((int) ide_dma_off_quietly);
+	if (drive->type != ATA_DISK)
+		return ide_dma_off_quietly;
 
 	if (((id->dma_ultra & 0x0010) ||
 	     (id->dma_ultra & 0x0008) ||

@@ -356,7 +355,7 @@
 	byte speed		= -1;
 	byte ultra66		= eighty_ninty_three(drive);
 
-	if (drive->media != ide_disk)
+	if (drive->type != ATA_DISK)
 		return ((int) ide_dma_off_quietly);
 
 	if ((id->dma_ultra & 0x0010) && (ultra) && (ultra66)) {

diff -ur linux-2.5.5/drivers/ide/alim15x3.c linux/drivers/ide/alim15x3.c
@@ -278,7 +278,7 @@
 	 * PIO mode => ATA FIFO on, ATAPI FIFO off
 	 */
 	pci_read_config_byte(dev, portFIFO, &cd_dma_fifo);
-	if (drive->media==ide_disk) {
+	if (drive->type == ATA_DISK) {
 		if (hwif->index) {
 			pci_write_config_byte(dev, portFIFO, (cd_dma_fifo & 0x0F) | 0x50);
 		} else {

@@ -424,9 +424,9 @@
 	} else if ((m5229_revision < 0xC2) &&
 #ifndef CONFIG_WDC_ALI15X3
 		   ((chip_is_1543c_e && strstr(id->model, "WDC ")) ||
-		    (drive->media!=ide_disk))) {
+		    (drive->type != ATA_DISK))) {
 #else /* CONFIG_WDC_ALI15X3 */
-		   (drive->media!=ide_disk)) {
+		   (drive->type != ATA_DISK)) {
 #endif /* CONFIG_WDC_ALI15X3 */
 		return 0;
 	} else {

@@ -441,7 +441,7 @@
 	ide_dma_action_t dma_func	= ide_dma_on;
 	byte can_ultra_dma		= ali15x3_can_ultra(drive);
 
-	if ((m5229_revision<=0x20) && (drive->media!=ide_disk))
+	if ((m5229_revision<=0x20) && (drive->type != ATA_DISK))
 		return hwif->dmaproc(ide_dma_off_quietly, drive);
 
 	if ((id != NULL) && ((id->capability & 1) != 0) && hwif->autodma) {

@@ -494,7 +494,7 @@
 		case ide_dma_check:
 			return ali15x3_config_drive_for_dma(drive);
 		case ide_dma_write:
-			if ((m5229_revision < 0xC2) && (drive->media != ide_disk))
+			if ((m5229_revision < 0xC2) && (drive->type != ATA_DISK))
 				return 1;	/* try PIO instead of DMA */
 			break;
 		default:

diff -ur linux-2.5.5/drivers/ide/amd74xx.c linux/drivers/ide/amd74xx.c
@@ -34,7 +34,6 @@
 
 static int amd74xx_get_info(char *, char **, off_t, int);
 extern int (*amd74xx_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int amd74xx_get_info (char *buffer, char **addr, off_t offset, int count)

diff -ur linux-2.5.5/drivers/ide/cmd64x.c linux/drivers/ide/cmd64x.c
@@ -88,7 +88,6 @@
 static int cmd64x_get_info(char *, char **, off_t, int);
 static int cmd680_get_info(char *, char **, off_t, int);
 extern int (*cmd64x_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int cmd64x_get_info (char *buffer, char **addr, off_t offset, int count)

@@ -448,7 +447,8 @@
 	u8 regU			= 0;
 	u8 regD			= 0;
 
-	if ((drive->media != ide_disk) && (speed < XFER_SW_DMA_0))	return 1;
+	if ((drive->type != ATA_DISK) && (speed < XFER_SW_DMA_0))
+		return 1;
 
 	(void) pci_read_config_byte(dev, pciD, &regD);
 	(void) pci_read_config_byte(dev, pciU, &regU);

@@ -641,8 +641,8 @@
 			break;
 	}
 
-	if (drive->media != ide_disk) {
-		cmdprintk("CMD64X: drive->media != ide_disk at double check, inital check failed!!\n");
+	if (drive->type != ATA_DISK) {
+		cmdprintk("CMD64X: drive is not a disk at double check, inital check failed!!\n");
 		return ((int) ide_dma_off);
 	}
 

@@ -788,7 +788,7 @@
 	}
 
 	if ((id != NULL) && ((id->capability & 1) != 0) &&
-	    hwif->autodma && (drive->media == ide_disk)) {
+	    hwif->autodma && (drive->type == ATA_DISK)) {
 		/* Consult the list of known "bad" drives */
 		if (ide_dmaproc(ide_dma_bad_drive, drive)) {
 			dma_func = ide_dma_off;

diff -ur linux-2.5.5/drivers/ide/cs5530.c linux/drivers/ide/cs5530.c
@@ -37,7 +37,6 @@
 
 static int cs5530_get_info(char *, char **, off_t, int);
 extern int (*cs5530_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int cs5530_get_info (char *buffer, char **addr, off_t offset, int count)

diff -ur linux-2.5.5/drivers/ide/hpt34x.c linux/drivers/ide/hpt34x.c
@@ -56,7 +56,6 @@
 
 static int hpt34x_get_info(char *, char **, off_t, int);
 extern int (*hpt34x_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int hpt34x_get_info (char *buffer, char **addr, off_t offset, int count)

@@ -210,7 +209,7 @@
 	struct hd_driveid *id	= drive->id;
 	byte speed		= 0x00;
 
-	if (drive->media != ide_disk)
+	if (drive->type != ATA_DISK)
 		return ((int) ide_dma_off_quietly);
 
 	hpt34x_clear_chipset(drive);

@@ -333,7 +332,7 @@
 			outb(reading, dma_base);		/* specify r/w */
 			outb(inb(dma_base+2)|6, dma_base+2);	/* clear INTR & ERROR flags */
 			drive->waiting_for_dma = 1;
-			if (drive->media != ide_disk)
+			if (drive->type != ATA_DISK)
 				return 0;
 			ide_set_handler(drive, &ide_dma_intr, WAIT_CMD, NULL);	/* issue cmd to drive */
 			OUT_BYTE((reading == 9) ? WIN_READDMA : WIN_WRITEDMA, IDE_COMMAND_REG);

diff -ur linux-2.5.5/drivers/ide/hpt366.c linux/drivers/ide/hpt366.c
@@ -355,7 +355,6 @@
 #if defined(DISPLAY_HPT366_TIMINGS) && defined(CONFIG_PROC_FS)
 static int hpt366_get_info(char *, char **, off_t, int);
 extern int (*hpt366_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 
 static int hpt366_get_info (char *buffer, char **addr, off_t offset, int count)
 {

@@ -579,7 +578,7 @@
 
 static int hpt3xx_tune_chipset (ide_drive_t *drive, byte speed)
 {
-	if ((drive->media != ide_disk) && (speed < XFER_SW_DMA_0))
+	if ((drive->type != ATA_DISK) && (speed < XFER_SW_DMA_0))
 		return -1;
 
 	if (!drive->init_speed)

@@ -664,7 +663,7 @@
 	byte ultra66		= eighty_ninty_three(drive);
 	int  rval;
 
-	if ((drive->media != ide_disk) && (speed < XFER_SW_DMA_0))
+	if ((drive->type != ATA_DISK) && (speed < XFER_SW_DMA_0))
 		return ((int) ide_dma_off_quietly);
 
 	if ((id->dma_ultra & 0x0020) &&

diff -ur linux-2.5.5/drivers/ide/ht6560b.c linux/drivers/ide/ht6560b.c
@@ -143,7 +143,7 @@
 	if (select != current_select || timing != current_timing) {
 		current_select = select;
 		current_timing = timing;
-		if (drive->media != ide_disk || !drive->present)
+		if (drive->type != ATA_DISK || !drive->present)
 			select |= HT_PREFETCH_MODE;
 		(void) inb(HT_CONFIG_PORT);
 		(void) inb(HT_CONFIG_PORT);

diff -ur linux-2.5.5/drivers/ide/ide-cd.c linux/drivers/ide/ide-cd.c
@@ -2906,14 +2906,10 @@
 	return 0;
 }
 
-int ide_cdrom_reinit (ide_drive_t *drive);
+static int ide_cdrom_reinit (ide_drive_t *drive);
 
-static ide_driver_t ide_cdrom_driver = {
-	name:			"ide-cdrom",
-	media:			ide_cdrom,
-	busy:			0,
-	supports_dma:		1,
-	supports_dsc_overlap:	1,
+static struct ata_operations ide_cdrom_driver = {
+	owner:			THIS_MODULE,
 	cleanup:		ide_cdrom_cleanup,
 	standby:		NULL,
 	flushcache:		NULL,

@@ -2937,7 +2933,7 @@
 MODULE_PARM(ignore, "s");
 MODULE_DESCRIPTION("ATAPI CD-ROM Driver");
 
-int ide_cdrom_reinit (ide_drive_t *drive)
+static int ide_cdrom_reinit (ide_drive_t *drive)
 {
 	struct cdrom_info *info;
 	int failed = 0;

@@ -2955,14 +2951,17 @@
 	}
 	memset (info, 0, sizeof (struct cdrom_info));
 	drive->driver_data = info;
-	DRIVER(drive)->busy++;
+
+	/* ATA-PATTERN */
+	ata_ops(drive)->busy++;
 	if (ide_cdrom_setup (drive)) {
-		DRIVER(drive)->busy--;
+		ata_ops(drive)->busy--;
 		if (ide_cdrom_cleanup (drive))
 			printk ("%s: ide_cdrom_cleanup failed in ide_cdrom_init\n", drive->name);
 		return 1;
 	}
-	DRIVER(drive)->busy--;
+	ata_ops(drive)->busy--;
+
 	failed--;
 
 	revalidate_drives();

@@ -2975,7 +2974,7 @@
 	ide_drive_t *drive;
 	int failed = 0;
 
-	while ((drive = ide_scan_devices (ide_cdrom, ide_cdrom_driver.name, &ide_cdrom_driver, failed)) != NULL)
+	while ((drive = ide_scan_devices(ATA_ROM, "ide-cdrom", &ide_cdrom_driver, failed)) != NULL)
 		if (ide_cdrom_cleanup (drive)) {
 			printk ("%s: cleanup_module() called while still busy\n", drive->name);
 			failed++;

@@ -2989,7 +2988,7 @@
 	int failed = 0;
 
 	MOD_INC_USE_COUNT;
-	while ((drive = ide_scan_devices (ide_cdrom, ide_cdrom_driver.name, NULL, failed++)) != NULL) {
+	while ((drive = ide_scan_devices (ATA_ROM, "ide-cdrom", NULL, failed++)) != NULL) {
 		/* skip drives that we were told to ignore */
 		if (ignore != NULL) {
 			if (strstr(ignore, drive->name)) {

@@ -3013,14 +3012,17 @@
 		}
 		memset (info, 0, sizeof (struct cdrom_info));
 		drive->driver_data = info;
-		DRIVER(drive)->busy++;
+
+		/* ATA-PATTERN */
+		ata_ops(drive)->busy++;
 		if (ide_cdrom_setup (drive)) {
-			DRIVER(drive)->busy--;
+			ata_ops(drive)->busy--;
 			if (ide_cdrom_cleanup (drive))
 				printk ("%s: ide_cdrom_cleanup failed in ide_cdrom_init\n", drive->name);
 			continue;
 		}
-		DRIVER(drive)->busy--;
+		ata_ops(drive)->busy--;
+
 		failed--;
 	}
 	revalidate_drives();

diff -ur linux-2.5.5/drivers/ide/ide-disk.c linux/drivers/ide/ide-disk.c
@@ -1053,17 +1053,13 @@
 	return ide_unregister_subdriver(drive);
 }
 
-int idedisk_reinit(ide_drive_t *drive);
+static int idedisk_reinit(ide_drive_t *drive);
 
 /*
  *      IDE subdriver functions, registered with ide.c
  */
-static ide_driver_t idedisk_driver = {
-	name:			"ide-disk",
-	media:			ide_disk,
-	busy:			0,
-	supports_dma:		1,
-	supports_dsc_overlap:	0,
+static struct ata_operations idedisk_driver = {
+	owner:			THIS_MODULE,
 	cleanup:		idedisk_cleanup,
 	standby:		do_idedisk_standby,
 	flushcache:		do_idedisk_flushcache,

@@ -1083,7 +1079,7 @@
 
 MODULE_DESCRIPTION("ATA DISK Driver");
 
-int idedisk_reinit (ide_drive_t *drive)
+static int idedisk_reinit(ide_drive_t *drive)
 {
 	int failed = 0;
 

@@ -1093,15 +1089,16 @@
 		printk (KERN_ERR "ide-disk: %s: Failed to register the driver with ide.c\n", drive->name);
 		return 1;
 	}
-	DRIVER(drive)->busy++;
+
+	ata_ops(drive)->busy++;
 	idedisk_setup(drive);
 	if ((!drive->head || drive->head > 16) && !drive->select.b.lba) {
 		printk(KERN_ERR "%s: INVALID GEOMETRY: %d PHYSICAL HEADS?\n", drive->name, drive->head);
-		(void) idedisk_cleanup(drive);
-		DRIVER(drive)->busy--;
+		idedisk_cleanup(drive);
+		ata_ops(drive)->busy--;
 		return 1;
 	}
-	DRIVER(drive)->busy--;
+	ata_ops(drive)->busy--;
 	failed--;
 
 	revalidate_drives();

@@ -1114,7 +1111,7 @@
 	ide_drive_t *drive;
 	int failed = 0;
 
-	while ((drive = ide_scan_devices (ide_disk, idedisk_driver.name, &idedisk_driver, failed)) != NULL) {
+	while ((drive = ide_scan_devices(ATA_DISK, "ide-disk", &idedisk_driver, failed)) != NULL) {
 		if (idedisk_cleanup (drive)) {
 			printk (KERN_ERR "%s: cleanup_module() called while still busy\n", drive->name);
 			failed++;

@@ -1134,20 +1131,20 @@
 	int failed = 0;
 	
 	MOD_INC_USE_COUNT;
-	while ((drive = ide_scan_devices (ide_disk, idedisk_driver.name, NULL, failed++)) != NULL) {
+	while ((drive = ide_scan_devices(ATA_DISK, "ide-disk", NULL, failed++)) != NULL) {
 		if (ide_register_subdriver (drive, &idedisk_driver)) {
 			printk (KERN_ERR "ide-disk: %s: Failed to register the driver with ide.c\n", drive->name);
 			continue;
 		}
-		DRIVER(drive)->busy++;
+		ata_ops(drive)->busy++;
 		idedisk_setup(drive);
 		if ((!drive->head || drive->head > 16) && !drive->select.b.lba) {
 			printk(KERN_ERR "%s: INVALID GEOMETRY: %d PHYSICAL HEADS?\n", drive->name, drive->head);
-			(void) idedisk_cleanup(drive);
-			DRIVER(drive)->busy--;
+			idedisk_cleanup(drive);
+			ata_ops(drive)->busy--;
 			continue;
 		}
-		DRIVER(drive)->busy--;
+		ata_ops(drive)->busy--;
 		failed--;
 	}
 	revalidate_drives();

diff -ur linux-2.5.5/drivers/ide/ide-dma.c linux/drivers/ide/ide-dma.c
@@ -470,7 +470,7 @@
 	ide_hwif_t *hwif = HWIF(drive);
 
 #ifdef CONFIG_IDEDMA_ONLYDISK
-	if (drive->media != ide_disk)
+	if (drive->type != ATA_DISK)
 		config_allows_dma = 0;
 #endif
 

@@ -555,7 +555,7 @@
 {
 	u64 addr = BLK_BOUNCE_HIGH;
 
-	if (on && drive->media == ide_disk && HWIF(drive)->highmem) {
+	if (on && drive->type == ATA_DISK && HWIF(drive)->highmem) {
 		if (!PCI_DMA_BUS_IS_PHYS)
 			addr = BLK_BOUNCE_ANY;
 		else

@@ -613,7 +613,7 @@
 			outb(reading, dma_base);			/* specify r/w */
 			outb(inb(dma_base+2)|6, dma_base+2);		/* clear INTR & ERROR flags */
 			drive->waiting_for_dma = 1;
-			if (drive->media != ide_disk)
+			if (drive->type != ATA_DISK)
 				return 0;
 #ifdef CONFIG_BLK_DEV_IDEDMA_TIMEOUT
 			ide_set_handler(drive, &ide_dma_intr, 2*WAIT_CMD, NULL);	/* issue cmd to drive */

diff -ur linux-2.5.5/drivers/ide/ide-features.c linux/drivers/ide/ide-features.c
@@ -70,22 +70,6 @@
 }
 
 /*
- *
- */
-char *ide_media_verbose (ide_drive_t *drive)
-{
-	switch (drive->media) {
-		case ide_scsi:		return("scsi   ");
-		case ide_disk:		return("disk   ");
-		case ide_optical:	return("optical");
-		case ide_cdrom:		return("cdrom  ");
-		case ide_tape:		return("tape   ");
-		case ide_floppy:	return("floppy ");
-		default:		return("???????");
-	}
-}
-
-/*
  * A Verbose noise maker for debugging on the attempted dmaing calls.
  */
 char *ide_dmafunc_verbose (ide_dma_action_t dmafunc)

diff -ur linux-2.5.5/drivers/ide/ide-taskfile.c linux/drivers/ide/ide-taskfile.c
@@ -648,7 +648,7 @@
 
 	if (rq->errors >= ERROR_MAX) {
 		if (drive->driver != NULL)
-			DRIVER(drive)->end_request(0, HWGROUP(drive));
+			ata_ops(drive)->end_request(0, HWGROUP(drive));
 		else
 			ide_end_request(drive, 0);
 	} else {

diff -ur linux-2.5.5/drivers/ide/ns87415.c linux/drivers/ide/ns87415.c
@@ -103,7 +103,7 @@
 			ns87415_prepare_drive(drive, 0);	/* DMA failed: select PIO xfer */
 			return 1;
 		case ide_dma_check:
-			if (drive->media != ide_disk)
+			if (drive->type != ATA_DISK)
 				return ide_dmaproc(ide_dma_off_quietly, drive);
 			/* Fallthrough... */
 		default:

diff -ur linux-2.5.5/drivers/ide/pdc202xx.c linux/drivers/ide/pdc202xx.c
@@ -63,7 +63,6 @@
 
 static int pdc202xx_get_info(char *, char **, off_t, int);
 extern int (*pdc202xx_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 char *pdc202xx_pio_verbose (u32 drive_pci)

@@ -412,7 +411,8 @@
 		default: return -1;
 	}
 
-	if ((drive->media != ide_disk) && (speed < XFER_SW_DMA_0))	return -1;
+	if ((drive->type != ATA_DISK) && (speed < XFER_SW_DMA_0))
+		return -1;
 
 	pci_read_config_dword(dev, drive_pci, &drive_conf);
 	pci_read_config_byte(dev, (drive_pci), &AP);

@@ -820,7 +820,8 @@
 	}
 
 	if (jumpbit) {
-		if (drive->media != ide_disk)	return ide_dma_off_quietly;
+		if (drive->type != ATA_DISK)
+			return ide_dma_off_quietly;
 		if (id->capability & 4) {	/* IORDY_EN & PREFETCH_EN */
 			OUT_BYTE((iordy + adj), indexreg);
 			OUT_BYTE((IN_BYTE(datareg)|0x03), datareg);

@@ -869,13 +870,14 @@
 
 chipset_is_set:
 
-	if (drive->media != ide_disk)	return ide_dma_off_quietly;
+	if (drive->type != ATA_DISK)
+		return ide_dma_off_quietly;
 
 	pci_read_config_byte(dev, (drive_pci), &AP);
 	if (id->capability & 4)	/* IORDY_EN */
 		pci_write_config_byte(dev, (drive_pci), AP|IORDY_EN);
 	pci_read_config_byte(dev, (drive_pci), &AP);
-	if (drive->media == ide_disk)	/* PREFETCH_EN */
+	if (drive->type == ATA_DISK)	/* PREFETCH_EN */
 		pci_write_config_byte(dev, (drive_pci), AP|PREFETCH_EN);
 
 jumpbit_is_set:

diff -ur linux-2.5.5/drivers/ide/pdcadma.c linux/drivers/ide/pdcadma.c
@@ -34,7 +34,6 @@
 
 static int pdcadma_get_info(char *, char **, off_t, int);
 extern int (*pdcadma_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int pdcadma_get_info (char *buffer, char **addr, off_t offset, int count)

diff -ur linux-2.5.5/drivers/ide/piix.c linux/drivers/ide/piix.c
@@ -77,7 +77,6 @@
 
 static int piix_get_info(char *, char **, off_t, int);
 extern int (*piix_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int piix_get_info (char *buffer, char **addr, off_t offset, int count)

diff -ur linux-2.5.5/drivers/ide/qd65xx.c linux/drivers/ide/qd65xx.c
@@ -293,7 +293,7 @@
 		printk(KERN_INFO "%s: PIO mode%d\n",drive->name,pio);
 	}
 
-	if (!HWIF(drive)->channel && drive->media != ide_disk) {
+	if (!HWIF(drive)->channel && drive->type != ATA_DISK) {
 		qd_write_reg(0x5f,QD_CONTROL_PORT);
 		printk(KERN_WARNING "%s: ATAPI: disabled read-ahead FIFO and post-write buffer on %s.\n",drive->name,HWIF(drive)->name);
 	}

diff -ur linux-2.5.5/drivers/ide/serverworks.c linux/drivers/ide/serverworks.c
@@ -105,7 +105,6 @@
 
 static int svwks_get_info(char *, char **, off_t, int);
 extern int (*svwks_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 
 static int svwks_get_info (char *buffer, char **addr, off_t offset, int count)
 {

diff -ur linux-2.5.5/drivers/ide/sis5513.c linux/drivers/ide/sis5513.c
@@ -238,7 +238,7 @@
 	byte rw_prefetch	= (0x11 << drive->dn);
 
 	pci_read_config_byte(dev, 0x4b, &reg4bh);
-	if (drive->media != ide_disk)
+	if (drive->type != ATA_DISK)
 		return;
 	
 	if ((reg4bh & rw_prefetch) != rw_prefetch)

diff -ur linux-2.5.5/drivers/ide/slc90e66.c linux/drivers/ide/slc90e66.c
@@ -60,7 +60,6 @@
 
 static int slc90e66_get_info(char *, char **, off_t, int);
 extern int (*slc90e66_display_info)(char *, char **, off_t, int); /* ide-proc.c */
-extern char *ide_media_verbose(ide_drive_t *);
 static struct pci_dev *bmide_dev;
 
 static int slc90e66_get_info (char *buffer, char **addr, off_t offset, int count)

diff -ur linux-2.5.5/drivers/ide/trm290.c linux/drivers/ide/trm290.c
@@ -192,7 +192,7 @@
 			outl(hwif->dmatable_dma|reading|writing, hwif->dma_base);
 			drive->waiting_for_dma = 1;
 			outw((count * 2) - 1, hwif->dma_base+2); /* start DMA */
-			if (drive->media != ide_disk)
+			if (drive->type != ATA_DISK)
 				return 0;
 			ide_set_handler(drive, &ide_dma_intr, WAIT_CMD, NULL);
 			OUT_BYTE(reading ? WIN_READDMA : WIN_WRITEDMA, IDE_COMMAND_REG);

Martin, please fix your mailer on 195.63.194.11. It retries the send every minute which is far too fast. It is absolutely broken because it ignores 5xx response codes.

This is *not my* responsibility. The resposible admin in question already knows about it. OK?

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

The shared memory side of it has to be page sized. It doesn't mean you have to have 1 semaphore per page but it does mean you have to allocate in page sized chunks for mmu granularity

Unfortunately, no. You need to know what userspace is using them for so you can check to avoid the "add to waitqueue" race.

AFAICT a mutex is the simplest useful primitive that can be realistically exported.

Hope that helps,
Rusty.

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

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

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

Hmm. My preference is for something like mprotect(start, len, PROT_SEM | PROT_READ | PROT_WRITE);

And then
#ifdef PROT_SEM && PROT_SEM
mprotect ....
#else
/* This architecture needs not special support skip the mprotect... #endif

Ouch.

The common case for a decent lock is the uncontended case. In which case you only need kernel support on demand. What you suggest would create kernel data structures for all of the uncontended locks. That sounds heavy. Especially as the memory on most architectures is already safe to use for locks.

So if nothing else can we separate the two cases of having user space
memory safe for user space spin locks. And how to setup a wait queue
of user space waiters on when we need to wait?

Eric

Hi!

Your user part is arch-dependend, anyway. So it can just mmap(..., O_CAREFULL).

Pavel

Philips Velo 1: 1"x4"x8", 300gram, 60, 12MB, 40bogomips, linux, mutt,
details at http://atrey.karlin.mff.cuni.cz/~pavel/velo/index.html.

In the hope to be included into this discussion and keep this discussion active.

As previously reported, I wrote a user level locking or fast semaphore package, which resolves the uncontended case in shared memory and through atomic operations, while the contended case falls back into the kernel. Yesterday I layed out some of my assumptions/approach of my implementation.

download available under

	http://prdownloads.sourceforge.net/lse/ulocks-2.4.17.tar.bz2.

As of Linus's request to put the content into a regular file backe setup. I support that as well. I also support different virtual addresses in the various processes. It should simply be shared memory wether through shmat or mmap.

Currently I was fixated on semaphores/calocks/rwlocks which require at most two queues. Ben LeHaise yesterday more or less stated that any number of queues is desirable to implement whatever-you-like lock. I second that motion and will modify the code accordingly, should be a quick hack.

In the following I first describe again what my implementation provides I will follow with performance numbers, lock contention, retry rates, and fairness under various load conditions for a synthetic benchmark.

WHAT HAS BEEN IMPLEMENTED
=========================

(a) EXCLUSIVE LOCKS
(a1) SysV IPC semaphores: I need these to have a base for comparision. (FAIR)
(a2) usema: semaphore implementation. (FAIR)
(a3) usema_spin: same as above, however, I will spin for a period of time, called patience,before actually entering into the kernel on contention. (FAIR)
(a4) calock: convoy avoidance lock. This lock is not fair. On unlock operation, the lock is made available even if a waiting process has to be woken up. The woken process then must content for the lock again, which (a) is unfair and (b) can result into multiple reentrances into the kernel for waiting (NOT FAIR).
(a5) calock_spin: same as above, but we spin for a while.

Some notes here: all but for (a1,a2) all locks required compare_exchange functionality.

(b) SHARED LOCKS
(b1) rwlock: multiple reader/single writer. On wakeup preference is given to the readers, not the writers. (FAIR)

What has been tested and how?

I wrote a micro benchmark, that allows me to
(a) test the correctness of the locks (and believe me that helped, some obvious solutions particularly for the spinning just don't work) and
(b) measure the performance. I wrote a program, called ulockflex. It allows me to control the type of lock used, the number of children, the mean lock hold time and non-lock hold time, the patience.

In return it tells me a lot of things about the individual locks. I have integrated lock contention measurement right into the base lock routines.
They come extremely cheap, in most cases a single atomic increment or simple increment and don't really show up at the application level at all (sometimes even help due to the spinning affect).

The performance of the locks is measured by the cummulative throughput/sec of the children through the following loop.

for (;;) {
      run_lock_not_held(uniform(mean_non_locktime));
      lock();
      run_lock_held(uniform(mean_non_locktime));
      unlock();
}

uniform(x) gives me a uniformly distributed random value in the interval [ .5x .. 1.5x].
I also measure the fairness of the locks among children. A fair lock should give everybody the same number of loops over a meaningful execution time. small changes are due to the random distribution. This is measured as the coefficient of variance
which is a normalized value compared to the mean. 0.0 is fair, and the higher the value the less the fair it becomes.

So without further due, here is the output of my regression/performance test. I split it up with some comments and point out some irregularities. All tests run on a 2-way PIII 550MHZ machine.

PERFORMANCE
===========

Wed Feb 20 23:02:33 EST 2002: calibrated at 273
base arguments are <-t 10 -o 5 -m 8 -R 273 -P>

First the legend
c #number of children
a #number of locks
t #second of each run
i #number of iterations (if less than 7) we reached 95% confidence
interval. (1 warmup run)
otherwise the result is statistically not
significant. I don't have
the exact confidence number.
L locktype (capital letter means spinning version)
e ::= no locks
k ::= sysv ipc sem
f ::= usema
F ::= usema_spinning
c ::= calock
C ::= calock_spinning
s<x> ::= with <x> the percentage of read sharing lock requests

p patience of spinning if any
WC lock contention on write lock
RC read contention on read lock (for shared lock only)
R percentage of failed lock attempts resolved by spinning OR
average times in calock lock attempt that failed needed to go into the
kernel (1 min).
COV coefficient of variance between children (fairness)
ThPut Cummulative throughput achieved per second for all children

c a t i L p r x WC RC R COV ThPut

 1  1 10  5 e      0   0   0    0.00   0.00   0.00 0.000000  1398321  (A1)
 1  1 10  5 k      0   0   0    0.00   0.00   0.00 0.000000   309423
 1  1 10  5 f      0   0   0    0.00   0.00   0.00 0.000000  1157684
 1  1 10  5 F      0   0   0    0.00   0.00   0.00 0.000000  1136268
 1  1 10  5 F      3   0   0    0.00   0.00   0.00 0.000000  1136147
 1  1 10  5 c      0   0   0    0.00   0.00   0.00 0.000000  1115431
 1  1 10  5 C      0   0   0    0.00   0.00   0.00 0.000000  1150488
 1  1 10  5 C      3   0   0    0.00   0.00   0.00 0.000000  1150368

(A1) this is the base number without any locking. Every loop takes about 400 cycles
We can see that he sysv kernel implementation has high overhead just getting in and out of the kernel and inspecting the ipc object namely ~1400 cycles of overhead. The remainder are all very much the same, since there is no contention, neither spinning nor any kernel calls are issued, simply an atomic instruction.

 1  1 10  5 e      0   0  10    0.00   0.00   0.00 0.000000    93978
 1  1 10  5 k      0   0  10    0.00   0.00   0.00 0.000000    76133
 1  1 10  5 f      0   0  10    0.00   0.00   0.00 0.000000    93136
 1  1 10  5 F      0   0  10    0.00   0.00   0.00 0.000000    92945
 1  1 10  5 F      3   0  10    0.00   0.00   0.00 0.000000    92968
 1  1 10  5 c      0   0  10    0.00   0.00   0.00 0.000000    63579 (*)
 1  1 10  5 C      0   0  10    0.00   0.00   0.00 0.000000    92993
 1  1 10  5 C      3   0  10    0.00   0.00   0.00 0.000000    93018

 1  1 10  5 e      0   7   3    0.00   0.00   0.00 0.000000    93850
 1  1 10  5 k      0   7   3    0.00   0.00   0.00 0.000000    76055
 1  1 10  5 f      0   7   3    0.00   0.00   0.00 0.000000    70352 (*)
 1  1 10  5 F      0   7   3    0.00   0.00   0.00 0.000000    92848
 1  1 10  5 F      3   7   3    0.00   0.00   0.00 0.000000    92858
 1  1 10  5 c      0   7   3    0.00   0.00   0.00 0.000000    81495 (*)
 1  1 10  5 C      0   7   3    0.00   0.00   0.00 0.000000    92882
 1  1 10  5 C      3   7   3    0.00   0.00   0.00 0.000000    92900

 1  1 10  5 e      0   9   1    0.00   0.00   0.00 0.000000    93882
 1  1 10  5 k      0   9   1    0.00   0.00   0.00 0.000000    76137
 1  1 10  5 f      0   9   1    0.00   0.00   0.00 0.000000    65751 (*)
 1  1 10  5 F      0   9   1    0.00   0.00   0.00 0.000000    92844
 1  1 10  5 F      3   9   1    0.00   0.00   0.00 0.000000    92846
 1  1 10  5 c      0   9   1    0.00   0.00   0.00 0.000000    88650 (*)
 1  1 10  5 C      0   9   1    0.00   0.00   0.00 0.000000    92875
 1  1 10  5 C      3   9   1    0.00   0.00   0.00 0.000000    92877

Same case, no contention, but we increase the loop time to 10usecs, splitting it up into (0,10) (7,3) and (10,0) for (nonlock-time,lock time). This will serve as a base number again. Surprisingly (*) have subpar performance, this indicates some scheduler irregularities, since it doesn't really do anything different than in (A). This observation repeats itself several times and I'll try to hunt it down. I'll try the newest MQ scheduler. Nevertheless, the overhead of sysv-ipc is apparent.

Now let's turn to the real cases, 2 children with lock contention.

 2  1 10  5 e      0   0   0    0.00   0.00   0.00 0.003351  2696755
 2  1 10  5 k      0   0   0   99.44   0.00   0.00 0.000786   159238
 2  1 10  6 f      0   0   0   42.33   0.00   0.00 0.034375   391065
 2  1 10  5 F      0   0   0   71.06   0.00   4.41 0.004886   242038
 2  1 10  5 F      3   0   0   46.02   0.00  26.55 0.043065   254974
 2  1 10  5 c      0   0   0    7.58   0.00   0.18 0.007522   695978
 2  1 10  5 C      0   0   0    3.84   0.00   0.12 0.004054   713464
 2  1 10  5 C      3   0   0    6.22   0.00   0.00 0.007328   706955

In this tied race we can clearly see the superior performance that can be achieved with f and c locks. Note that most of the time is spent in the loop preparation of determining the random values etc. Its also astounding how little contention there exists in the calock.

Now looking at the 2 children 2 locks, there ofcourse is no contention and these numbers should be double the 1 child/1 lock case and they are. The strange cases (*) are pointed out again.

 2  2 10  5 e      0   0  10    0.00   0.00   0.00 0.002096   127205
 2  2 10  5 k      0   0  10    0.00   0.00   0.00 0.000616   145450
 2  2 10  5 f      0   0  10    0.00   0.00   0.00 0.002025   185794
 2  2 10  5 F      0   0  10    0.00   0.00   0.00 0.000511   185242
 2  2 10  5 F      3   0  10    0.00   0.00   0.00 0.000798   185239
 2  2 10  5 c      0   0  10    0.00   0.00   0.00 0.001097   126782 (*)
 2  2 10  5 C      0   0  10    0.00   0.00   0.00 0.000506   185478
 2  2 10  5 C      3   0  10    0.00   0.00   0.00 0.002143   185473

 2  2 10  5 e      0   7   3    0.00   0.00   0.00 0.002369   127126
 2  2 10  5 k      0   7   3    0.00   0.00   0.00 0.000970   143495
 2  2 10  5 f      0   7   3    0.00   0.00   0.00 0.000154   140287
 2  2 10  5 F      0   7   3    0.00   0.00   0.00 0.000251   185045
 2  2 10  5 F      3   7   3    0.00   0.00   0.00 0.000295   185046
 2  2 10  5 c      0   7   3    0.00   0.00   0.00 0.001159   162488 (*)
 2  2 10  5 C      0   7   3    0.00   0.00   0.00 0.001096   185233
 2  2 10  5 C      3   7   3    0.00   0.00   0.00 0.001196   185249

 2  2 10  5 e      0   9   1    0.00   0.00   0.00 0.000680   127125
 2  2 10  5 k      0   9   1    0.00   0.00   0.00 0.001323   144927
 2  2 10  5 f      0   9   1    0.00   0.00   0.00 0.000906   131147 (*)
 2  2 10  5 F      0   9   1    0.00   0.00   0.00 0.002069   185095
 2  2 10  5 F      3   9   1    0.00   0.00   0.00 0.000214   185082
 2  2 10  5 c      0   9   1    0.00   0.00   0.00 0.000668   176828 (*)
 2  2 10  5 C      0   9   1    0.00   0.00   0.00 0.003634   185237
 2  2 10  5 C      3   9   1    0.00   0.00   0.00 0.002531   185207

 2  1 10  5 k      0   0  10   99.92   0.00   0.00 0.039162    59885
 2  1 10  5 f      0   0  10   99.91   0.00   0.00 0.031926    59141
 2  1 10  5 F      0   0  10   99.90   0.00   0.00 0.058318    58287
 2  1 10  5 F      3   0  10   99.63   0.00   0.01 0.000769    49363 (C1)
 2  1 10  5 c      0   0  10    0.07   0.00 1365.3 0.010231    48821 (C2)
 2  1 10  5 C      0   0  10    1.89   0.00  52.95 0.274067    64882 (C3)
 2  1 10  5 C      3   0  10    2.43   0.00  41.12 0.227824    64425 (C4)

Above is a really interesting case, where the lock is 100% contended. In that case spinning (C1) doesn't pay. Interesting are the cases C2-C4, take a look at the R column, which tells me that on average a contended case (RW) needed to retry 1365, 52, 41 times respectively. Though the contention was minimal, this is high and results in unfair locking, which reflects itself in an extremely high COV value (22%).

 2  1 10  5 k      0   7   3   42.65   0.00   0.00 0.000456    92178
 2  1 10  5 f      0   7   3   20.55   0.00   0.00 0.001683   110963
 2  1 10  5 F      0   7   3   33.35   0.00   8.62 0.002107   121134
 2  1 10  5 F      3   7   3   21.84   0.00  49.51 0.002057   161271
 2  1 10  5 c      0   7   3   28.93   0.00   2.24 0.001609   132291
 2  1 10  5 C      0   7   3   22.22   0.00   1.72 0.001753   150395
 2  1 10  5 C      3   7   3   20.94   0.00   0.06 0.003021   147583

 2  1 10  5 k      0   9   1   18.30   0.00   0.00 0.000911   114569
 2  1 10  5 f      0   9   1    6.62   0.00   0.00 0.003179   121252
 2  1 10  5 F      0   9   1   10.48   0.00  23.20 0.002029   163215
 2  1 10  5 F      3   9   1    9.49   0.00  49.94 0.002685   172780
 2  1 10  5 c      0   9   1   12.82   0.00   1.01 0.002806   150094
 2  1 10  5 C      0   9   1    9.79   0.00   0.77 0.003529   157167
 2  1 10  5 C      3   9   1    9.19   0.00   0.03 0.003280   154746

 3  1 10  5 k      0   0  10   99.99   0.00   0.00 0.005466    59116
 3  1 10  5 f      0   0  10   99.99   0.00   0.00 0.071828    48826
 3  1 10  5 F      0   0  10   99.98   0.00   0.00 0.061724    49281
 3  1 10  5 F      3   0  10   99.96   0.00   0.00 0.030956    49393
 3  1 10  5 c      0   0  10    4.04   0.00  24.75 0.111655    47918
 3  1 10  5 C      0   0  10   14.32   0.00   6.98 0.050590    62455
 3  1 10  5 C      3   0  10   16.63   0.00   6.01 0.057665    63155

 3  1 10  5 k      0   7   3   97.59   0.00   0.00 0.004165    78487
 3  1 10  5 f      0   7   3   85.77   0.00   0.00 0.022811    98692
 3  1 10  5 F      0   7   3   96.15   0.00   0.20 0.013047   103924
 3  1 10  7 F      3   7   3   43.21   0.00  26.81 0.018630   124829
 3  1 10  5 c      0   7   3   29.11   0.00   3.43 0.002640   126916
 3  1 10  5 C      0   7   3   22.50   0.00   4.44 0.019857   138407
 3  1 10  7 C      3   7   3   20.95   0.00   4.76 0.014293   129526

 3  1 10  5 k      0   9   1   88.33   0.00   0.00 0.022545   110836
 3  1 10  5 f      0   9   1   73.99   0.00   0.00 0.007920   107787  (*)
 3  1 10  5 F      0   9   1   76.47   0.00   1.08 0.010588   135066
 3  1 10  5 F      3   9   1   11.39   0.00  44.85 0.011170   170034
 3  1 10  7 c      0   9   1   12.82   0.00   7.23 0.007448   134004
 3  1 10  7 C      0   9   1    9.78   0.00   6.90 0.014131   144045
 3  1 10  7 C      3   9   1    9.14   0.00   7.54 0.020201   138368

 4  1 10  5 k      0   0  10  100.00   0.00   0.00 0.065016    57854
 4  1 10  5 f      0   0  10  100.00   0.00   0.00 0.059136    49980
 4  1 10  5 F      0   0  10  100.00   0.00   0.00 0.084718    49467
 4  1 10  5 F      3   0  10  100.00   0.00   0.00 0.026923    48819
 4  1 10  5 c      0   0  10    3.12   0.00  32.05 0.267046    47519
 4  1 10  5 C      0   0  10   14.91   0.00   6.71 0.022086    61074
 4  1 10  5 C      3   0  10   18.18   0.00   5.50 0.039526    60815

 4  1 10  6 k      0   7   3   99.91   0.00   0.00 0.003822    85681
 4  1 10  5 f      0   7   3   94.27   0.00   0.00 0.010577    98893
 4  1 10  5 F      0   7   3   97.29   0.00   0.13 0.032502   107599
 4  1 10  5 F      3   7   3   69.03   0.00  11.04 0.032696   119276
 4  1 10  5 c      0   7   3   29.09   0.00   3.43 0.012937   126950
 4  1 10  5 C      0   7   3   22.42   0.00   4.43 0.011381   138405
 4  1 10  5 C      3   7   3   20.95   0.00   4.75 0.012371   129167

 4  1 10  5 k      0   9   1   97.52   0.00   0.00 0.008442   114210
 4  1 10  5 f      0   9   1   94.32   0.00   0.00 0.015333   104639
 4  1 10  5 F      0   9   1   93.78   0.00   0.23 0.007120   131777
 4  1 10  5 F      3   9   1   22.86   0.00  26.04 0.010409   161190
 4  1 10  5 c      0   9   1   12.84   0.00   7.77 0.017105   132406
 4  1 10  6 C      0   9   1    9.75   0.00  10.22 0.010480   137857
 4  1 10  7 C      3   9   1    9.23   0.00  10.46 0.029786   135441

To summarize the small process(children) case. Not counting the (*) cases we clearly see that the user level locks substantially outperform (+20%) the kernel implementation if lock contention does not hoover above 95%, a case we don't optimize for anyway.
Surprisingly, they are even reasonable fair in most cases, (c) in various cases had a high COV value, but that's what the lock is for. Spinning helps (sometimes).

Now let's turn our attention to the 100 process case.

100  1 10  5 k      0   0  10  100.00   0.00   0.00 0.756951    16866
100  1 10  5 f      0   0  10  100.00   0.00   0.00 0.536551    49233
100  1 10  5 F      0   0  10  100.00   0.00   0.00 0.516478    49096
100  1 10  5 F      3   0  10  100.00   0.00   0.00 0.592092    49216
100  1 10  5 c      0   0  10    5.19   0.00  19.27 0.324299    46064
100  1 10  7 C      0   0  10   15.17   0.00   6.59 0.071464    53429
100  1 10  7 C      3   0  10   16.96   0.00   5.90 0.075513    52285

not a lot of difference in the fully contended case. Striking again how often the lock acquisition in the calock succeeds even for this fully contended case. The fairness is totally down the drain even in the k and f lock, which indicates to me that the run time might not have been long enough.

100  1 10  7 k      0   7   3  100.00   0.00   0.00 0.028202    12168
100  1 10  5 f      0   7   3  100.00   0.00   0.00 0.082430    24693
100  1 10  5 F      0   7   3  100.00   0.00   0.00 0.083701    26918
100  1 10  5 F      3   7   3  100.00   0.00   0.00 0.084006    26489
100  1 10  5 c      0   7   3   29.10   0.00   3.43 0.253149   127234
100  1 10  5 C      0   7   3   22.23   0.00   4.49 0.198701   138257
100  1 10  5 C      3   7   3   20.81   0.00   4.79 0.235070   129320

100  1 10  7 k      0   9   1  100.00   0.00   0.00 0.014891    12297
100  1 10  5 f      0   9   1  100.00   0.00   0.00 0.079500    67188 (E1)
100  1 10  5 F      0   9   1  100.00   0.00   0.00 0.077384    25207 (E2)
100  1 10  5 F      3   9   1  100.00   0.00   0.00 0.077485    25148
100  1 10  5 c      0   9   1   12.73   0.00   7.81 0.194209   133376
100  1 10  5 C      0   9   1    9.71   0.00  10.28 0.153369   137555
100  1 10  5 C      3   9   1    8.85   0.00  11.24 0.163615   134339

The last two cases are SHOWTIME. Clearly we get superior behavior user level
locking. (E1)is very high as compared to (E2). I don't have any explanation for this.

Userlocks on VIAGRA: 1000 processes contending for a single lock.

1000  1 10  5 k      0   9   1  100.00   0.00   0.00 0.026477     1358
1000  1 10  7 f      0   9   1  100.00   0.00   0.00 0.544364     2640
1000  1 10  7 F      0   9   1   99.84   0.00   0.00 0.588966     2507
1000  1 10  7 F      3   9   1   99.45   0.00   0.03 0.362092     2245
1000  1 10  7 c      0   9   1    6.87   0.00  14.38 0.596546   104738
1000  1 10  6 C      0   9   1    9.22   0.00  10.78 0.696058   136075
1000  1 10  5 C      3   9   1    7.74   0.00  12.71 0.749075   134492

Note we did not get to statistically significant runs for f,F,c. The results speak for themselves!!!!

SHARED LOCKS
------------

Here I check how the shared locks work for (0,10) (10,0) case 2 processes. I increase the lock sharing from 0 to 100 %. As can be seen the performance increases with it. Interesting again is that the (0,10) case is faster than the the (10,0) case for 100% sharing ?

 2  1 10  5 s  0   0   0  10   99.90   0.00   0.00 0.020436    58331
 2  1 10  5 s 20   0   0  10   99.00  79.67   0.00 0.003076    55887
 2  1 10  5 s 40   0   0  10   97.08  59.75   0.00 0.001201    59823
 2  1 10  5 s 60   0   0  10   94.34  39.78   0.00 0.000268    71217
 2  1 10  5 s 80   0   0  10   91.42  19.91   0.00 0.001100    96733
 2  1 10  5 s100   0   0  10    0.00   0.00   0.00 0.001839   172432

 2  1 10  5 s  0   0  10   0    0.49   0.00   0.00 0.001672   121785
 2  1 10  5 s 20   0  10   0    0.51   0.58   0.00 0.000147   121616
 2  1 10  5 s 40   0  10   0    0.67   0.51   0.00 0.001209   121057
 2  1 10  5 s 60   0  10   0    0.88   0.41   0.00 0.001455   120407
 2  1 10  5 s 80   0  10   0    0.96   0.22   0.00 0.002061   120161
 2  1 10  5 s100   0  10   0    0.00   0.00   0.00 0.000782   120306

Comments particular to the questions previously posted and posted here again.

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)

-- Hubertus Franke

Rusty, since I supplied one of those packages available under lse.sourceforge.net let me make some comments.

(a) why do you need to pin. I simply use the user level address (vaddr) and hash with the <mm,vaddr> to obtain the internal object. This also gives me full protection through the general vmm mechanisms.
(b) I like the idea of mmap or shmat with special flags better than going through a device driver.
Let's make this a real extension rather than going through a device interface. i.e. expand the sys call interface
(c) creation can be done on demand, that's what I do. If you never have to synchronize through the kernel than you don't create the objects. There should be an option to force explicite creation if desired.
(d) The kernel should simply provide waiting and wakeup functionality and the bean counting should be done in user space. There is no need to pin or crossmap.
(e) I really like to see multiple reader/single writer locks as well. I implemented these
(f) I also implemented convoy avoidance locks, spinning versions of user semaphores. All over the same simple interface. ulocks_wait(read_or_write) and ulocks_signal(read_or_write, num_to_wake_up). Ofcourse to cut down on the interface a single system call is enough.
(g) I have an extensive test program and regression test <ulockflex> that exercises the hell out of the userlevel approach.

I pin while sleeping for convenience, so I can get a kernel address. It's only one page (maybe 2). I could look up the address every time, but then I need to swap the page back in anyway to look at it.

Me too, but I'd rather have people saying "make it a syscall" than "eww... not another special purpose syscall!" 8)

Absolutely, except there is no real "creation" event. Adding a "here be semaphores" syscall is sufficient and useful (and also makes it easy to detect that there is no FUS support in the kernel).

See above.

Hmmm... my current implementatino only allows down one and up one operations, but off the top of my head I don't see a no reason this couldn't
be generalized. Then:
1) Initialize at INT_MAX
2) down_read = down 1
3) down_write = down INT_MAX

Sufficient?

Interesting. Something like this might be needed for backwards compatibility anyway (spin & yield, at least).

Excellent. I shall grab it and take a look!

Thanks for the feedback,
Rusty.

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

As stated above, I allocate a kernel object <kulock_t> on demand and hash it. This way I don't have to pin any user address. What does everybody think about the merit of this approach versus the pinning approach? Most importantly I think the merit of both approaches stems from the fact that the access is purely through the userlevel address rather than through a handle. In your case, can the lock be allocated at different virtual addresses in the various address spaces.
How do you cleanup ? Do you search through the hashtable ? In other words what happens if you SIGTERM a process ?

One more syscall its all that needed like semop(). I multiplex all operations through this interface. Agree, its more scalable then a device driver as somebody pointed out that the device has locks associated with it.

That's what I have done. All internal objects are created on the fly. Somebody pointed out to me that RT programs might want to allocate the internal object apriori, in that case the forcing the creation would be required.

Yip, no state sharing required between kernel and user. I analyzed this vary carefully, particularly for spinning locks, I can show you sequences of events that get you in real trouble because the atomic update in user space and the waiting are non atomic. As far as I am concerned separation is imperative.

No, you effectively need two queues or you have to basically replicate the low level semaphore routines to walk the list and identify the sequence (R*W)* and only wake those up that are the same. There are many issues in the wakeup. Do I want to wakeup all readers waiting regardless of intermittent writers....

This is a must. I talked to database folks, they can see huge utilization out of these locks. I hence echo again Ben LaHaises opinion, the kernel mechanism must be flexible enough to support more complex locking stuff. I have added in my next update on lse download support for queues.

Indeed this is/was a lifesaver, it points out so many interesting things with respect to bugs and performance when the rubber hits the road.

Let's keep the sync going. At this point we need to figure out what is the right approach for the kernel. Is the explicite kernel object approach I have chosen better/worse/equal to the pinning approach ? Inputs from everyone please. We need to score against
codepath length,
cleanup,
memory requirements

Cheers.
-- Hubertus

Lookup is cheap. I integrated a <hit meter> into my hashing mechanism that reports the hits/misses and the average length of traversal down a hash chain, it's insignificant for the cases I tried, but again no big progam has be tried against any of these approaches.

I (think) I now also see the merit of your approach, in that you really don't need to allocate a kernel object. You actually allocate the object right into the shared user page and pin it down. Your argument is that you only need to pin while somebody is sleeping on the lock.
Is that correct? Very tricky.
Let me also point out some shortcomings of this. If indeed there is a shared page between user and kernel then how does the system react to buggy userlevel code, e.g wild write that corrupt the wait queue.

In my explicite kernel object approach, I won't have this problem.

I hope I am not missing something here.

-- Hubertus

[...]

I think this is a relatively important feature. It may not be possible to use the same virtual address in different processes.

r~

I think so too. However let me point that Linus's initial recommendation of a handle, comprised of a kernel pointer and a signature also has that property.
Just pointing out the merits of the various approaches.

-- Hubertus

Do:
if (page->mapping)

    hash(page->mapping, page->offset, vaddr & ~PAGE_MASK)

else
hash(mm, vaddr)
This handles the semaphores in shared memory case. So the semaphores will work across processes as well.

Which makes the uncontended (common) case fast.

Agreed.

Eric

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

(seem below)

(plenty below :-)

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 ([email protected])

__update_count needed to be able to do the decrement from 0 or the count, whichever was greater. I have eliminated this in the new patch (patch III).

OK. We dealt with hash collisions by sharing waitqueues. This works, but means we have to do wake-all. My new patch uses its own queues: we still share queues, but we only wake the first one waiting on our counter.

Hmmm.... it should be pretty easy to extend: the queues can be shared.

Yes, but counting semaphores need two variables, or cmpxchg. Mutexes do not need either (proof by implementation 8). While general counting semaphores may be useful, the fact that they are not implemented in the kernel suggests they are not worth paying extra for.

This is a definite advantage: my old fd-based code never looked at the userspace counter: it had a kernel sempahore to sleep on for each userspace lock. OTOH, this involves kernel allocation, with the complexity that brings.

They're interruptible, so you'll get -ERESTARTSYS. Should be fine.

I agree. While originally reluctant, when it's one page per sleeping process it's rather neat.

Cheers!
Rusty.

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

I am pretty much ready to support Rusty's latest patch. I think much of the stuff I mentioned as been addressed.
The hash collision elimination the biggest one.
The page pinning is a great idea and I see that to be a great advantage over what I tried to push.

Correct, should we bring that into the interface already. Expand the syscall with an additional parameter identifying the queue.

Not exactly, they need one atomic in user space and a semaphore in the kernel which as you stated uses (atomic and sleepers).

???, kernel allocation is only required in under contention. If you take a look at how I used the atomic word for semaphores and for rwlock_t, its different. If you recheck in the kernel you need to know how this is used.
In my approach I simply allocated two queues on demand.

I am OK with only supplying semaphores and rwlocks, if there is a general consent about it. Nevertheless, I think the multiqueue approach is somewhat more elegant and expandable.

That's what I did too, but some folks pointed out they might want to interrupt a waking task, so that it can get back into user space and fail with EAGAIN or so and do not automatically restart the syscall.

Yipp, most applications that will take advantage of this will allocate the locks anyway in a shared region, i.e. there will be more than one lock per page.

As I said above, I am favor for the general infrastructure that you have in place now. Can we hash out the rwlock issues again.
They can still be folded into a single queue (logical) and you wakeup eiher the next writer or set of readers, or all readers ....
We need a mean to bring that through the API. I think about it.

Great job Rusty, pulling all these issues together with a comprehensive patch. The few remaining issues are cravy :-)

-- Hubertus

Yes, but no allocation is even better than on-demand allocation, if you can get away with it.

Well, it's pretty easy to allow other values than -1/1 later as required. I don't think the switch() overhead will be measurable for the first dozen lock types 8).

Sorry, my bad. I use -EINTR, so they don't get restarted, for exactly that reason (eg. implementing timeouts on mutexes).

Cheers!
Rusty.

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