Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

double-word-cas on x86-64

60 views

Skip to first unread message

Dmitriy Vyukov

unread,

May 11, 2007, 4:14:15 PM5/11/07

We can emulate double-word-cas on x86-64 with the next trick.
Trick is Windows specific, I am not sure whether it is portable to
Linux, my Linux folks say nothing definite... (if you are really Linux
folk, you just can write kernel extension for this :) )

Here is the trick:

1. Reserve big memory region in address space of a process. We can
reserve up to 4Gb, because memory doesn't actually allocated, just
reserved in address space:

void* base_addr = VirtualAlloc(0, 2^32, MEM_RESERVE, PAGE_READWRITE);

2. Commit/decommit memory for your data structure as you need:

void* addr = VirtualAlloc(base_addr + offset, 4096, MEM_COMMIT,
PAGE_READWRITE);
VirtualFree(base_addr + offset, 4096, MEM_DECOMMIT);

3. Use as pointer only low 32 bits address, and high 32 bits is
constant. And other 32 bits of word can be used for ABA counter or
second pointer.

Thus we get 32 bit pointers on 64 bit machine w/o the need to actually
preallocate very big piece of memory. Cool! So we get DWCAS on x86 and
on x86-64 too. So we can use some algorithms that use DWCAS on modern
x86.

And I think this trick can be used on 32 bit machines to get some more
stolen bits from pointer. For example if we bound memory limit for
data structure to 128Mb, we get additional 5 bits... but address space
on 32 bit machines is so valuable...

Any comments?

Dmitriy V'jukov