|
#1
03-10-2006, 09:06 AM
|
||||
|
||||
Have some user space spinlock code...
Well its been a WEEK with no work... and I am VERY VERY bored...
To pass the time I was fooling around trying to get a program to run on an ancient machine with only basic POSIX support... and lo and behold... even though the program required them the system didn't provide spinlocks... So I had some old code ( from an old version of my pthread faq thingy ) that emulates them... and used that... After doing a bit of code clean-up and reformatting to fit into 72 char lines... and I was thinking... why not post it here cause I have had emails about this in the past... and who knows... maybe it will help generate a bit more traffic in this section of the forum... A couple of warnings... 1) There MAY be bugs in the code... as I have never fully tested all the functionality... so if you find one let me know... 2) The formatting is strange BUT that is so that it will fit into the pthreads doc which in text format has lines of 72 characters maximum... so if you don't like it um... sorry but thats just the way it is... Next message will contain the code... Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) 
|
|
#2
03-10-2006, 09:07 AM
|
||||
|
||||
|
User space spinlocks - Pt 2
Code:
/**********************************************************************
BETA User Space spinlocks for POSIX systems lacking this functionality.
Copyright (C) 2003-2006 Michael M. Lampkin
Contact at michael.lampkin<at>ieee.org
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License version 2 as
published by the Free Software Foundation.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
version 2 along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
**********************************************************************/
#define _POSIX_C_SOURCE 200112L
#define _XOPEN_SOURCE 600
#define SPINLOCK_SPIN_MAX 50
#include <errno.h>
#include <pthread.h>
#include <sched.h>
#include <string.h>
#include <unistd.h>
/**
Need this "unique" value that we can use to take any spinlock
that has been initialized and identify attempts to call init
multiple times without corresponding calls to destroy. A hard
coded value should be fine though still a 1 in 4 billion chance
of collision with random data in un-inited spinlock.
**/
static long int spin_magic = 0x2FCD51F9L;
/**
The spinlock structure which should NEVER be manipulated
by user code.
owner:
a pthread_t var indicating the current owner of the
spinlock or filled with 0's if not owned
mutex:
the primary mutex that any incoming threads will spin on
and attempt to obtain.
magic:
a field to hold a sentinel value indicating if the spinlock
is initialized.
**/
typedef struct
{
pthread_t owner;
pthread_mutex_t mutex;
long int magic;
}
spinlock;
/**
Function: spinlock_init
Description:
Initializes and allocates system resources to a
spinlock structure.
Parameters:
spin - a pointer to the spinlock structure to
be initialized.
pshared - either PTHREAD_PROCESS_PRIVATE or
PTHREAD_PROCESS_SHARED. If the system does not
support process shared mutexes or an unknown value
is given then defaults internally to a private type
with no error.
**/
int spinlock_init( spinlock * spin, int pshared )
{
int result;
pthread_mutexattr_t attr;
/* If already inited... race condition with destroy */
if ( NULL == spin )
{
return EINVAL;
}
if ( spin_magic == spin->magic )
{
return EBUSY;
}
( void ) memset( & spin->owner, 0, sizeof( pthread_t ) );
/* Set our process sharing attribute - default to PRIVATE */
result = pthread_mutexattr_init( & attr );
if ( 0 == result )
{
if ( 0 < sysconf( _SC_THREAD_PROCESS_SHARED ) )
{
if( PTHREAD_PROCESS_SHARED == pshared )
{
result = pthread_mutexattr_setpshared( & attr, pshared );
}
else
{
result = pthread_mutexattr_setpshared( & attr, PTHREAD_PROCESS_PRIVATE );
}
}
}
/* Need to add this to prevent recursive mutex default on some sys */
if ( 0 == result )
{
result = pthread_mutexattr_settype( & attr, PTHREAD_MUTEX_ERRORCHECK );
}
/* The following is a race against simultaneous calls to init */
if ( 0 == result )
{
result = pthread_mutex_init( & spin->mutex, & attr );
}
if ( 0 == result )
{
spin->magic = spin_magic;
}
( void ) pthread_mutexattr_destroy( & attr );
return result;
}
/**
Function: spinlock_destroy
Description:
Releases system resources allocated to a spinlock
structure during initializion.
Parameters:
spin - a pointer to a previously initialized but
not destroyed spinlock.
**/
int spinlock_destroy( spinlock * spin )
{
int result;
if ( NULL == spin || spin_magic != spin->magic )
{
return EINVAL;
}
if ( 0 != ( result = pthread_mutex_destroy( & spin->mutex ) ) )
{
return result;
}
( void ) memset( & spin->owner, 0, sizeof( pthread_t ) );
/**
A return of EINVAL on destroy means another thread is
also destroying. Ignore it.
**/
spin->magic = 0;
return 0;
}
/**
Function: spinlock_lock
Description:
Attempts to acquire exclusive access to the specified
spinlock. If the spinlock is already owned then begin
spinning until ownership is obtained.
Parameters:
spin - a pointer to an initialized spinlock.
**/
int spinlock_lock( spinlock * spin )
{
pthread_t self;
int result;
int spin_count;
if ( NULL == spin || spin_magic != spin->magic )
{
return EINVAL;
}
self = pthread_self( );
if ( 0 == memcmp( & spin->owner, & self, sizeof( pthread_t ) ) )
{
return EDEADLK;
}
for ( ; 0 != ( result = pthread_mutex_trylock( & spin->mutex ) ) ; )
{
if ( EBUSY == result )
{
++ spin_count;
if ( SPINLOCK_SPIN_MAX == spin_count )
{
( void ) sched_yield( );
spin_count = 0;
}
}
else
{
/* Destroy occurred on us... */
return EINVAL;
}
}
( void ) memcpy( & spin->owner, & self, sizeof( pthread_t ) );
return result;
}
/**
Function: spinlock_trylock
Description:
Attempts to acquire exclusive access to the specified
spinlock. If the spinlock is already owned by another
thread then return immediately.
Parameters:
spin - a pointer to an initialized spinlock.
**/
int spinlock_trylock( spinlock * spin )
{
int result;
if ( NULL == spin || spin_magic != spin->magic )
{
return EINVAL;
}
if ( 0 == ( result = pthread_mutex_trylock( & spin->mutex ) ) )
{
( void ) memcpy( & spin->owner, & self, sizeof( pthread_t ) );
}
return result;
}
/**
Function: spinlock_unlock
Description:
Releases exclusive ownership of the specified
spinlock.
Parameters:
spin - a pointer to an initialized spinlock.
**/
int spinlock_unlock( spinlock * spin )
{
int result;
if ( NULL == spin || spin_magic != spin->magic )
{
return EINVAL;
}
( void ) memset( & spin->owner, 0, sizeof( pthread_t ) );
return pthread_mutex_unlock( & spin->mutex );
}
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-12-2006 at 05:18 AM.
|
|
#3
03-10-2006, 09:08 AM
|
||||
|
||||
|
User space spinlocks - Pt 3
Code:
/* All code squishied into previous post */
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-11-2006 at 11:46 AM.
|
|
#4
03-10-2006, 02:18 PM
|
|||
|
|||
|
Could you explain when this spinlock implementation would be preferred above normal mutexes?
1) I didn't test it, but I didn't spot any bugs either. It looks like it could be done simpler, with less mutexes, though perhaps with less runtime information. Especially the global lock looks reduntant, isn't pthread_mutex_init() already atomic? If not, why should spinlock_init() be? Same for mutex_destroy(). It looks like code which does call that function multiple times on the same unitialized spinlock will be very strange, such situation should be very easy to avoid. Why slowdown runtime spinlock code to avoid silly compiletime bugs? If people want to do it anyway they can always add the global locking themselves. 2) I think the formatting is a bit strange because it uses so much spaces, both vertical and horizontal ones. I would condense it much more, making it easier to get an overview of the code.
|
|
#5
03-10-2006, 07:34 PM
|
||||
|
||||
|
There are many times to use a spinlock...
If the thread requires the quickest acquisition of the lock, then without spinlocks you are stuck dealing with setting / unsetting different priorites for the threads... and hoping it happens... With a spinlock you are saying "I NEED IT NOW"... you go cpu bound and keep trying to grab it... for a single cpu system it may not make sense... but for modern multi-processor and multi-core computers it can mean MUCH faster acquisition... Along the lines of network programming... an example might be forcing access to accept calls by a particular thread... so the client side doesn't think you are dead or unresponsive... That is of course a simplified explanation and example... You have multiple questions under you #2 question... So starting from the top... my rational... a) The global lock is a simple lock... therefore it DOES use a simple default static init... I could have used a "once" type call but was trying to simplify things... to stop whining... b) "Especially the global lock looks reduntant, isn't pthread_mutex_init() already atomic?" The spinlock is a complex structure... heck, its a structure... even using system dependent stuff there is no way to do this easily... look at the kernel spinlock code for linux ( or bsd... or solaris ... or um, whatever )... HOW does one achieve doing an init of a complex structure by calling pthread_mutex_init?! Sorry but... don't understand the issue here... c) Without the global lock during creation and destruction... what is to prevent BOTH from being called by different threads to init / destroyed at the same time? THAT is why there is a global lock... that is why there is a counter... so locks that gain access, state they are trying to acquire the lock then are suspended by the scheduler can be reliably detected... While there IS overhead, under good programming practices, the program should any hits at startup and shutdown... or at the very least infrequently during runtime... d) "Why slowdown runtime spinlock code to avoid silly compiletime bugs?" Eh?! What compile time bugs? There is one ifdef which depends on process sharing being available... and I think ( hope ) the behavior emulates POSIX... i.e. invalid value or private then private... shared and shared available then shared... the rest are potential runtime errors ( same as the POSIX spinlocks )... e) "It looks like code which does call that function multiple times on the same unitialized spinlock will be very strange" - Um... unless I missed something... they will always return EINVAL... thanks to the global lock... if we didn't have that then yes, we could potentially try to init 1+n and leak or destroy 1+n and core out... f) This is meant as a simple "drop in place" for systems that don't support the realtime options of pthreads... including spinlocks... I did not consider that saying "Oh, there is no global locking so you have to do it yourself or everything might just randomly explode" was a viable options... yes... I could have left it out... but then again... I could have just left the title of the message and the GNU doc and no code... and said "HERE IT IS"... lol. Answer to question #2... from my original post... 3a) The formatting is strange BUT that is so that it will fit into the pthreads doc which in text format has lines of 72 characters maximum... so if you don't like it um... sorry but thats just the way it is... Sorry but 72 characters has been the standard for docs for more than 2 to 3 decades... I could do it a number of different ways... BUT this is the way it is done... Besides... with the code formatting on this board... did you notice that almost none ( possibly none ) of it wraps... and MOST of it is readable in the standard code window without scrolling left and right... thats the point... so newbies can read line by line... 3b) ALSO - ALL of the return errors are intented to emulate those given by the various pthread_spinlock_* functions... If I could just return an EINVAL or similar for EVERYTHING then a LOT of the code would be remove... but again - it is an attempt to emulate the POSIX stuff... not just give random errors... If there is a problem with this... um... as I stated previously "sorry but thats just the way it is..."... Last but certainly not least... and again... ;-) If you can show me a BETTER way that is not platform independent... hey... do it... I will welcome it... If you find a bug... give it to me... post it here... it will be added... like I said I was bored and this was a fast entertainment re-write of old code... I'm sure there is a bug or more in there... I could do this "faster" on linux using either futexes or atomic_t types... but this is USER SPACE CODE that is meant to compile on MOST platforms... not a specific OS or version of an OS... And... no more nonsense about the formatting since it has now been explained twice... Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-10-2006 at 08:20 PM.
|
|
#6
03-10-2006, 07:47 PM
|
||||
|
||||
|
Oh almost forgot...
Btw, and again... the code was meant to avoid system specific peculiarities and quirks... so futexes, atomic_t types, assembly code and so forth... not acceptable... As always, I welcome enlightenment... :-) Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-10-2006 at 08:22 PM.
|
|
#7
03-10-2006, 08:50 PM
|
|||
|
|||
|
You're right that the global lock sort of simplifies things, because everything is allowed and it will all go well. But what I meant is that it shouldn't be needed because synchronizing all spinlock initializations and destroys is a bit overkill for something which can be avoid easily by the programmer using the spinlocks. If they want to initialize and/or destroy the same spinlock in parallel then they can provide their own synchronisation, it should be a rare case. What I'm saying is that you made the api totally idiot proof in all cases, while it doesn't have to be, because protecting against rare cornercases should be done by the person who uses the spinlock api in strange ways (I do consider multiple threads trying to initialize or destroy the same spinlock strange). The compile time bug I meant was calling multiple spinlock_inits on the same spinlock without synchronization if that synchronization isn't done by the spinlock code. I think that the price paid for a totally safe spinlock_init/destroy is too high, that's all...
That global lock guarantees that the spinlock state is consistent. But if pthread_mutex_init is atomic then I don't see the need for a global lock, as you can use the just initialized mutex to handle parallel spinlock_init() calls. I'm not sure what you're on by your 3ab reply, I was talking about whitespaces and newlines, not return values or column width... You mentioned formatting, so I said what the strange part was in my opinion, which isn't the 72 char width or anything else you said. I know you could make a very fast spinlock or mutex with OS and platform dependent code, I did recognize the attempt to be totally independent of those. But to be honest, if I have the choice between just using a normal mutex and the above spinlock, I don't see why I should use that spinlock. Sure, you track count of waiting threads, but what use is that? Nice for debugging info perhaps, but I don't see the practical usefulness of it. Maybe I'm blind as a bat and miss something, but it seems like threads can be starved easily by this spinlock implementation, as they just go back in the queue and hope they'll get it next time. If there are a lot of threads wanting that spinlock then it will be quite crowded in that queue. Lots of unnecessary context switches and cpu usage (it all adds up), while I thought the main advantage of a spinlock was to avoid context switches for speed reasons. And if we do a context switch anyway, then why not use a normal mutex? Then the OS can wake up the thread when the mutex is free, and avoid starvation in their mutex implementation. Compared with networking code it's like using non-blocking sockets and to just spin all the time, recalling whatever syscall. This either eats cpu time a lot, or if you use yield() it can add unnecessary high latencies. That last thing because if the thread was sleeping instead and new data arrived, or the lock becomes free, the scheduler could give the thread priority above other threads and processes. Calling yield all the time quarantees that this can't be done and the thread will at average get the mean scheduling time, which can be dozens of milliseconds if there are many threads or processes. So I don't see at all how exactly you say that you need the lock "right now", it seems more like "I want to have it after all the others did their thing and maybe stole it before my nose". Of course it may be slightly faster if the thread is the only thing running on the cpu, but that doesn't quite look like the situation which does have the highest perfomance constraints to me. I've a strange feeling that I'm missing something obvious, care to enlighten me what that is?
|
|
#8
03-10-2006, 09:41 PM
|
||||
|
||||
|
The pthread_mutex_init function is NOT guaranteed to be atomic... though there is static initialization...
/** edit **/ I think I missed the question... Yes... mutex inits aren't explicitly required to be atomic... but for POSIX they do define errors or EBUSY ( in use ), EINVAL and others... some of this behaviour is optional... Since the posted code is NOT intended for commercial use... and is meant as an example... I thought and continue to think that providing such optional behaviour in my code was prudent. /** end **/ The POSIX standard defines spin locks as part of the REALTIME option... some systems do not supply this option at the user level though they are a common and well known construct... this code attempts to implement them for those systems which do not have them in user space... As for the formatting... the compilers don't mind so why are you making a fuss? Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-10-2006 at 10:31 PM.
|
|
#9
03-11-2006, 06:38 AM
|
||||
|
||||
|
Ack!
The point concerning the yield is well taken... but it was included because some older pthread impls will just thrash forever without doing that somewhere...
If the impl is good then much less of a need... so its sort of a bug fix... Um... On the same note... I just realized something... there is a define and counter check missing from the code I posted... in the area around the yield... its supposed to attempt N times to get the lock then do the yield if it fails... I may have pasted in the editor backup copy the first time around or something... oh well... the posted source is ( mostly ) fixed now... :-/ What I mean by mostly fixed is that I just noticed there are two other loops missing... and the lock and unlock functions should only be using trylock in a loop instead of lock for the counter spinlock counter... I'll post the change later... I guess I should have 2x checked the code after posting... oops again... lol Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-11-2006 at 07:10 AM.
|
|
#10
03-11-2006, 11:44 AM
|
||||
|
||||
|
By popular demand... :-P
I removed all synchronization on init and destruction of the spinlocks... so things can go BOOM if you make a mistake but this version is faster...
I removed the counter for threads spinning on the lock but which have not yet acquired it.. I removed calls to pthread_equal and replaced with a memcmp when testing to see who owns the lock... which let me drop the extra ptr in for temp holding of the owner variable... and worries about passing in an invalid pthread_t object to pthread_equals... The removal of the last two items means that the secondary mutex and locking required could be removed... The removal of the last item means that in addition to potential collision with the magic number which indicates initialization... there is now also a potential collision if for some strange reason a system defines a valid pthread_t type as being zero or filled with all zeros... I don't believe you will ever see that type of collision but nothing in the spec says it cannot happen... Total end result is that if you don't conform to good programming practices... and do things like calling init or destroy on the same spinlock simultaneously from multiple threads... then you may see very strange errors or crashes... if you don't do stuff like that then everything should be ok... and you should see a potential 2x speed increase... not that there was anything wrong with the speed of the previous version ;-) Also... I removed the extra vertical spacing... for those who had their code format sensibilities hurt... ;-) Forgot... there may now be one or two inconsistencies for function return values when compared to their equivalent POSIX functions... not certain though... will go over the code later to 2x check for that and any other issues... Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-11-2006 at 11:53 AM.
|
|
#11
03-11-2006, 01:00 PM
|
|||
|
|||
|
This code looks much better, and it actually spins now.
As this is meant to be a drop-in replacement for posix spinlocks, why not name them the same: pthread_spin_init, pthread_spin_lock and so on? If posix doesn't require pthread_mutex_init to be atomic, I guess it also doesn't require pthread_spin_init to be atomic. You seem to forget to set the owner field in the lock and trylock functions, and to clear it in the unlock function. You could also get rid of the field altogether, which wouldn't be a problem as far as I can tell.
|
|
#12
03-11-2006, 06:17 PM
|
||||
|
||||
|
Perhaps...
You are right... I edited it out by accident... and removed the part where the unlock zeroed out the id...
Now I remember the other reason for two locks ( this code is many years old )... There is now a third chance for collision... A thread can start to clear... which means it has to set the id to all zeroes... it holds the lock while it does this... But to catch deadlock... during lock and trylock attempts... since a trylock may ( or may NOT ) give a EBUSY ... it may in fact just deadlock... so we have to check the ownership prior to trying to attempt either of those calls... So now there is a 3rd chance for a random collision... that is, unlock is doing a memset to zero of the owner data while holding the lock... and a call to lock could potentially match this in transit... since to detect deadlock it is REQUIRED to do the comparison prior to owning the lock... "BANG"... Again... its a small chance... 3 out of about 4 billion... but ... I hate that... Maybe I should put the code back the way it was... but without the init and destroy locking... I know two locks may not be welcome... but was it really that bad... and it worked without these issues... ;-) Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989) Last edited by mlampkin; 03-11-2006 at 06:36 PM.
|
|
#13
03-11-2006, 08:14 PM
|
|||
|
|||
|
I'm not sure which revision of the code I'm seeing, but a lot of the above comments
don't seem to apply... However, I do spot one bug (I think): Code:
int spinlock_lock( spinlock * spin )
{
/* ... */
for ( ; 0 != ( result = pthread_mutex_trylock( & spin->mutex ) ) ; )
{
/* ... */
else
{
/* Destroy occurred on us... */
result = EINVAL;
break;
}
}
( void ) memcpy( & spin->owner, & self, sizeof( pthread_t ) );
return result;
}
(And, that's an interesting abuse of a for() loop, when a while() would suffice... ;-) But, I too am partial to for(), and try to use it over while() whenever I can...)
|
|
#14
03-11-2006, 08:34 PM
|
|||
|
|||
|
I think you're seeing the third revision Rob, at least of the code posted here.
Michael, you're using PTHREAD_MUTEX_ERRORCHECK, which already does the deadlock detection, so you can get rid of the owner field without losing functionality it seems.
|
|
#15
03-12-2006, 05:16 AM
|
||||
|
||||
|
Yeah I can jump out earlier... I was just figuring that if someone called a destroy while trying to lock then they were already in an invalid state... so who cares... lol.
I'll change it though... ;-) As for catching deadlock... even using a PTHREAD_MUTEX_ERRORCHECK mutex, a call to pthread_mutex_lock will return an EDEADLK on a recursive call but pthread_mutex_trylock is only required to return an EBUSY... That unfortunately means there has to be an external means of detection... Of course the POSIX spec does say that the spinlock lock function "may" return EDEADLK... which means it doesn't have to and could just give an "undefined results"... Also, if I keep removing optional POSIX functionality, pretty soon it will almost be down to a simple typedef'ing mutex to the name spinlock... and a simple while loop in the lock function... In fact its almost to that point already... lol :-( Actually perhaps I should take the original version... and block it out with ifdefs... have levels of say: DEFAULT - mostly just a loop wrapper on the inner mutex locks and no tracking on ownership POSIX_OPTIONAL - DEFAULT plus doing things like detecting deadlock etc. conditions... MICHAEL_OPTIONAL - POSIX_OPTIONAL plus the global init / destroy locks so it is impossible for a user to do anything inappropriate... i.e. the original code... Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989)
|
|
#16
03-12-2006, 10:43 AM
|
|||
|
|||
|
Quote:
I find it strange that POSIX is so loose in its requirements and definitions, what use is a standard if the behaviour still depends so much on the implementation? Maybe they wanted to make it as uncontroversial as possible so no one would mind complying. pthread_spin_trylock also only may return EDEADLK, so if your implementation is as good as pthread_mutex_trylock then it's still POSIX compliant. Also the behaviour is unspecified if one of the functions is called on an unitialized spinlock, so you can get rid of that spin_magic too. Yes, having multiple implementations, multiplexed with ifdefs or not, may be a good idea.
|
|
#17
03-13-2006, 12:11 PM
|
||||
|
||||
|
I am stilling trying to ifdef out the original version with all the safety nets so anyone can turn them on or off as they like during compilation...
I got bored with it for right now though... and so see the newest post by me... below this one until someone else comments... and I know there WILL be comments... lol It contains more code... some basic util functions I moved over from some C++ templates of mine... The code is on my site so it won't make the forums or users choke... :-P Michael
__________________
"The only difference between me and a madman is that I'm not mad." Salvador Dali (1904-1989)
|
 |
| Thread Tools | |
| Display Modes | |
|
|
Linear Mode
