Store an address and a bool in one word for lock-free doubly linked list

Question

I am reading some paper for lock-free doubly linked list. In these papers, they store an address to next and prev node and a flag in one word(int).

Is it because in 32-bit architectures all addresses are aligned in 4 byte boundaries so all address are multiple of 4?

and if the reason is what i say is this code ok?

const int dMask = 1;
const int pMask = ~dMask;

int store(void* pPointer, bool pDel)
{
    return reinterpret_cast<int>(pPointer) | (int)pDel;
}

void load(int pData, void** pPointer, bool* pDel)
{
    *pPointer = reinterpret_cast<void*>(pData & pMask);
    *pDel = pData & dMask;
}

And another question: Do in other platforms such as Android mobile devices, above idea is correct?

He

If the paper has the authors email address email them too and see what they say. And send them this link if you get any good answers. – Rexanna

Answer 1

You're more or less correct. It's a common space optimization in very low level code. It is not portable. (You could make it slightly more portable by using intptr_t instead of int.)

Also, of course, the alignment only holds for pointers to more complex types; a char* won't necessarily be aligned. (The only times I've seen this used is in the implementation of memory management, where all of the blocks involved are required to be aligned sufficiently for any type.)

Finally, I'm not sure what the authors' of the paper are trying to do, but the code you post cannot be used in a multithreaded environment, at least on modern machines. To ensure that a modification in one thread is seen in another thread, you need to use atomic types, or some sort of fence or membar.

Foldaway

The idea is, because addresses are 4-byte aligned, so in all addresses first two bits are zero. so we can store a flag in these two bit and we can check two data(address and our flag) with one CAS operation. I test it for char and alignment is still 4-byte. What is difference between a void* pointer and an intptr_t? i read that intptr_t is guaranteed to be able to hold pointers. so what is difference between them?(by both we can hold pointers) – He

@MohammadRB An intptr_t is an integral type, whose size is sufficient to hold a pointer. You need an integral type for the or'ing and and'ing. – Foldaway

@MohammadRB As for the thread safety, it is only assured if all accesses to the data in question are somehow protected. – Foldaway

Answer 2

Addresses in most 32-bit architectures are not stored in 4-byte boundaries, but 1-byte. They are read from memory at 4-byte (the typical word size) increments. Without seeing the code for this doubly linked list, it sounds like they are enforcing some rules for how the container will store data.

Correct

Pointers in most 32 bit architectures are aligned on 4-byte boundaries. Not doing so will either trigger a hardware trap when accessing them, or slow the access down considerably. – Foldaway

Some where i read all allocations in 64-bit systems are 16-byte aligned (i am not sure completely ;) but also i think in xbox360 allocations are 16-byte aligned – He

@JamesKanze Agreed, but the point was not how they are aligned, but how to address them. The addresses are still 1-byte apart. – Correct

@MohammadRB It is completely depending on the architecture. For example: software.intel.com/en-us/articles/… – Correct

@ZacHowland It depends on what you are addressing. He mentionned linked lists; the addresses of the nodes in a linked list are aligned with the alignment required by a pointer (at least), since each node contains a pointer. That means, on a typical machine, 4 or 8 bytes. Since the pointers themselves can address individual bytes, this means that there are 2 or 3 low order bits which must be 0. So you use one as a flag (making sure to mask it out when dereferencing). As I said, it's a common space optimization in very low level software. – Foldaway