Skip to contentSkip to conversation

Lightweight userspace semaphores...

PATCH Hubertus Franke 1 participant 2 messages Feb 27, 2002 1 message not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw
Quoted 27 lines · Joshua MacDonald

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.

Quoted 1 line

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.

Quoted 4 lines

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

Quoted 11 lines

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

#2 lore raw
In reply to a message not in the archive

To followup on this. I have posted the latest version of this under
http://prdownloads.sourceforge.net/lse/ulocks-2.4.17.tar.bz2

- I followed the suggestion below to minimize ulock_t datastructure to do so go to ./make.setup and comment out the -DLOCK_STATISTICS flag this will bring the ulockt_t down to 2 words, otherwise 28 bytes.
- The ulockflex program will irrespectively allocate all locks on cacheline boundaries regardless of size.
- I fixed a problem in ulockflex that was introduced in the last version.
- I have now number of queues instead of an explicite lock type. Hence the kernel only knows about number of queues to maintain.

-- Hubertus Franke

Quoted 47 lines · Joshua MacDonald
Quoted 28 lines · Hubertus Franke
Quoted 27 lines · Joshua MacDonald

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.

Quoted 7 lines
Quoted 1 line

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.

Sounds good. There is nothing to prevent the declaration of a ulock_t variable from using __cacheline_aligned, so I think Linus is off on this one.

I'd like to test this out sometime. The SLPC code uses a lots of CPP trickery to configure itself with various different read/write or exclusive locking packages, so its fairly easy to port to a new locking primitive.

-josh