Locks and memory pointer

[aehparta]

Hi,

I have a newbie question: Would it be wise or even possible to add locking to memory pointer to ease parallel programming? I mean that you could do like lock(ptr) and unlock(ptr) with any malloc()ed pointer and OS would provide locking for that pointer. As I have understood, that would only take one integer more to be stored for that pointer.

[JamesM]

Hi,

This is completely possible; Java does this (the "synchronized" keyword implicitly takes a lock in every java.lang.Object). However it is slightly wasteful - it's optimistic in the extreme to think that every object in the system will require locking at some point.

The more pessimistic approach is to assume that most object won't need to be locked, then only provide locks for those that do (creating mutex objects). That is the way most OSes do this.

Does this answer your question?

James

[aehparta]

Yes and no. I'm currently programming for many different platforms and devices. Sometimes multithreading is used and locks are needed, sometimes not. Basically, what I understood, at low level OS keeps track of allocated memory and has somekind of struct for that(?). So why not include simple atomic variable in that struct and add couple simple funcs for accessing it like memlock(ptr) and memunlock(ptr) (ofcourse I would need some efficient way of searching trough all allocated pointers when these functions are called. maybe the overhead is too much compared to specifically allocated lock). The programmer would have to use those functions to lock the memory when needed, it would not be automatic. The reason for this question is that I get quite frustrated often because you need to define and initialize different locks for different places by yourself (almost always for allocated memory shared between threads). It would be so nice to have those already there

But well, this was only theoretical question, since I was going to try writing small OS as a hobby project after getting very annoyed by things that do not work, things like symbian/qt/etc which actually have nothing to do with this (back to the roots, wish z80 would still be in general use ).. When I do things myself and there isn't anybode elses code, I can punch myself when things go wrong. (sry, offtopic)

edit: Oh, thanks for the reply

[JamesM]

Hi,

So as I said, it's perfectly possible; the only reason why it's not readily done is that you'd waste a sizeof(lock) for every pointer you allocate in your system.

James

[Velko]

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.

[rdos]

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.

[aehparta]

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.

That is very true. This idea was just simplify things in threaded system for the simplest cases. Ofcourse OS would need separate locks and etc for different and more complex cases.

[JamesM]

Hi,

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]

Hi,

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).

[JamesM]

Hi,

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).

Ah, apologies - I misunderstood how this bit would be stored. Assuming I have understood correctly and the lock bit is stored in the address of the object (in redundant alignment bits), you have two more problems:

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

[Combuster]

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)

[JamesM]

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)

You can tell I'm not an assembler programmer!

[Combuster]

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]

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);

Yes yes yes, I wasn't thinking properly and in fact have that exact same algorithm in pseudocode in my emacs *scratch* buffer, where I wrote it out to prove to myself I was wrong.

[aehparta]

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

My first idea was that memlock(ptr) etc functions would have to search the record for that pointer, it would be costly ofcourse. But that way it would work in the case you presented.