OSDev.org

rdos wrote:Just one problem. There is no rule that locks are only related to allocated memory blocks. They could just as well protect lists of allocated memory, or there could be several locks for the same piece of memory.

Velko wrote:In fact you need not to waste anything. Lock requires only one bit. And malloc()ed pointers most likely are going to be at least DWORD aligned, so there are at least 2 lower bits to play with.

Of course it can interfere with pointer math, offsets into structs, etc. But that's a thing you'll have to keep in mind: lock first, then play with pointers, not other way around.

JamesM wrote:Hi,

Velko wrote:In fact you need not to waste anything. Lock requires only one bit. And malloc()ed pointers most likely are going to be at least DWORD aligned, so there are at least 2 lower bits to play with.

Of course it can interfere with pointer math, offsets into structs, etc. But that's a thing you'll have to keep in mind: lock first, then play with pointers, not other way around.

So find me a compare-and-swap operation on the x86 that only affects one bit? (It'd have to do a compare-and-swap-with-mask. Which doesn't exist )

Ready4Dis wrote:

JamesM wrote:Hi,

Velko wrote:In fact you need not to waste anything. Lock requires only one bit. And malloc()ed pointers most likely are going to be at least DWORD aligned, so there are at least 2 lower bits to play with.

Of course it can interfere with pointer math, offsets into structs, etc. But that's a thing you'll have to keep in mind: lock first, then play with pointers, not other way around.

So find me a compare-and-swap operation on the x86 that only affects one bit? (It'd have to do a compare-and-swap-with-mask. Which doesn't exist )

Why would it have to compare and swap one bit? Just compare and swap the entire thing... for example, if bit 1 set means it's locked, then simply store the pointer into a temp variable, check if bit is set.. if so, don't even bother, if not, set the bit in the temp var, then do a comp swap and see if it was still not set. If it was set before we xchanged, we missed our chance... otherwise, we got the lock. You could even have a functoin to lock pointer, that returns NULL if the lock fails, and the actual pointer if it suceeds. Of course, you may want to store some more info for something like that, or have other returns (like pointer destroyed, or something similar so you're not waiting on a lock to free, when in fact it's a bad pointer).

void *ptr = malloc(10);
void *ptr2 = ptr;
lock(ptr);

JamesM wrote:So find me a compare-and-swap operation on the x86 that only affects one bit?

Combuster wrote:

JamesM wrote:So find me a compare-and-swap operation on the x86 that only affects one bit?

BTS/BTC/BTR, 386+ instructions. (since compare-and-swap on 1 bit essentially does nothing beyond setting the bit in question to a certain value and telling you if it could be changed)

Combuster wrote:Even so, you could have figured out that a 1-bit CAS would degenerate into a TAS

That said, my favourite synchronisation opcode is the fetch-and-increment (XADD)

Also, to make the point completely moot

Code: Select all

int x = (*memaddr & ~mask) | bits_to_compare;
int y = (x & ~mask) | new_value_for_bits;
return CAS(memaddr, x, y);

JamesM wrote: a)

Code: Select all

void *ptr = malloc(10);
void *ptr2 = ptr;
lock(ptr);

What happens in this case? 'ptr' would have its LOCK bit set, ptr2 would not.

b) Every object dereference would have to include a mask. "*ptr" would become "*(ptr&~0x1)", semantically. This would be expensive.

James