Re: [PATCH] Lightweight userspace semaphores...

[Hubertus Franke]

On Wed, Feb 27, 2002 at 07:38:34PM +0300, Joshua MacDonald wrote:
> Hi Hubertus,
> 
> I have a question for you about these semaphores.  I took a glance at
> <linux/ulocks.h> to try and find out how large an object the
> user-space lock is.  I see that you have it written like this:
> 
> typedef struct ulock_t {
> 	unsigned long  status;
> 	unsigned long  type;
> 	unsigned long  counters[ULOCK_STAT_COUNTERS];
> 	char           pad[SMP_CACHE_BYTES - 
> 			   (ULOCK_STAT_COUNTERS+2)*sizeof(unsigned long)];
> } ulock_t ____cacheline_aligned;
> 
> I would like to suggest that you offer a version of the ulock_t that
> is as small as possible so that the user can make use of the entire
> cacheline rather than waste it on padding.
> 
> The reason I'm interested is that I have written a concurrent,
> cache-optimized skip list and I did all of my testing using the
> standard Linux spinlocks.  Those are 4 bytes per lock.  I use one lock
> per cacheline-sized node of the data structure.  If you can get your
> locks down to one or two words that would be really interesting, since
> spinlocks don't work terribly well in user-space.  I would really like
> to be able to use this data structure outside of the kernel, and your
> locks might just solve my problem, but only if they are small enough.
> 
> Do you see my point?  You can find my latest skiplist code at:

I have seen the light. Seriously, I initially had it as you said, but
Linus was strongly recommending cacheline size objects to 
avoid false sharing other than on the lock word
However, there should be no problem whatsoever to bring that back
to 2 words.

> typedef struct ulock_t {
>       unsigned long  status;
>       unsigned long  qcount;   /* this will change instead of type */
> }

Counters are only there for lock statistics.
padding is only there for filling the cacheline (might be obsolute anyway.
What can be done is to make the ____cacheline_aligned a configuration
option. Nothing in the system relies on this. I'll see how I'll
do this.

Also, this can be brought down to one word, if we don't have
demand based kernel object allocation and/or multiple queue requirements
as requested by BenLeHaise.

Rusty, how would your pin based approach be effected by this ?

Comments ?

-- Hubertus

> 
>     http://sourceforge.net/projects/skiplist
> 
> I have put test results up on that site as well, but those tests were
> made using spinlocks at user-level!  In otherwords, I don't really
> believe my results are meaningful.
> 
> (And let me warn you that there's a bug and haven't uploaded the
> latest version yet...)
> 
> -josh