Lightweight userspace semaphores...
A message that is not in the archive (sent off-list or not yet received): [email protected]
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_tthat 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
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_tthat 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_tvariable 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