How could one make a reasonably efficient, pointer-sized mutex?

Question

I have my own ideas about how a pointer-sized mutex could be made: The integer is used as a set of flags, counter, index, and a spinlock that guards an entry in a table of pre-allocated kernel objects given to mutexes only when threads are contending, and released afterward (only need at most N table entries for N threads).

Watching MS' SRWLOCK structure change leads me to believe they conditionally store the tail of an xor list (or a table index?) in the pointer when contested. The first 4 bits are flags of some kind.

To clarify

I was wondering if there were any other ideas about making a user mode mutex that is the size of a pointer and only requires the allocation of a kernel object if it is contested. My idea involves spinlocking, so I am hoping there exists something that does not.

• maple_shaft: Can you please elaborate on your specific issue and question? It is hard to tell what is being asked for here.
• InsertMemeNameHere: The language I'm specifically interested in is C++? I'm not really one to repeat a question's title in the explanation, so I thought I post some of my ideas instead.
• maple_shaft: So you post your ideas and what ... hope somebody is smart enough to understand what you are getting at and offer some potential solutions? All I am saying is that you may get better answers if you put some more effort into clarifying your question.
• InsertMemeNameHere: Perhaps this was another one of those moments I should have just gone to sleep. I've updated it with a bit of clarification.
• maple_shaft: Much better! BTW... the most brilliant ideas come after a good long night of sleep or during a hot shower ;-)

Answer 1

Is the mutex supposed to be reentrant? If so, you'll need a few bits to hold a recursion count. Also a thread/process ID. You might also want to keep a pointer or some kind of reference to a queue to hold IDs of threads waiting on the mutex, depends on whether you want threads to queue up or simply let them acquire the mutex based on their scheduling order. Your pointers are 64 bits, right? ;)

• InsertMemeNameHere: Yes, the pointers are 64-bit. I actually do have a working reader/writer lock implementation, but as I am uncertain about just how big a thread ID can be, I've opted to not make them reentrant (yes, thread Ids are generally only 32-bits or less, but that's too many bits to assume are nonzero in this particular case).