How can I know how many free bits are there in a pointer?

Question

Edit: The reason I am asking

I think I have to clarity that the platform I am using and the reason I am asking to make it easier for you to answer this question: I am using a x86_64 machine with gcc and Ubuntu and I am working on some interpreter of some toy language and I think tagged pointer is a neat trick can be used. I know Apple is using it. So I just want to try it out.

---

I was reading something about tagged pointer and I was wondering, how can I know how many free bits are there in a pointer on a particular machine.

For now my understanding is that if I am using a 64 bit machine, then when accessing memory the CPU will always access memory address that are multiple of 8 bytes. So it leaves 2 bits in the end of a pointer always set to 0. Also, if on a x86_64 machine, the first 14 bits will be always 0 right? Since they are never used by the CPU. malloc will make sure that the pointers it gives back will always be aligned. But how about other memory locations? Say variables on the stack?

How can I confirm this?

Somebody in the comments suggested that 2 bits I mentioned in the above is not right, indicating I am a bad programmer. I do not deny that I am not a very professional programmer, but I think I shall explain a bit a bout why I said 2 instead of 3.

I wrote a very simple program like this:

 #include <stdio.h>
 #include <stdlib.h>
 int main() {
    int a = 0;
    printf("%p\n", &a);
    int *p = malloc(sizeof(int));
    printf("%p\n", p);
 }

And I compiled it with gcc and run it over 10000 iteration on a 64 bit machine with Ubuntu. I discovered that &a always end up with last 4 bits as 1100 and p always end up with 0000, so I want to be conservative about how many bits are actually unused by the compiler. That's why I said 2 instead of 3.

Also if you can help me explain what I have been observed (&a ends up with 1100, which only has 2 bits set to 0), I would deeply appreciate it.

Answer 1

Many recommend against using tag bits in the pointers (and so do I).

If you insist on doing that, use only the two (or perhaps three) lowest bits of pointers, and preferably write your own malloc-like allocator to ensure it.

On modern x86-64 processors most pointers (e.g. those to malloc-ed zones, or those to word-aligned data) are generally word-aligned, and that mean they are multiple of 8 (since a 64 bit word has 8 bytes).

^{Actually it is not only processor, but also ABI specific. Some ABIs mandate a 16 byte aligned stack pointer (to help SSE or AVX), others require only 8 byte alignment.}

Don't expect the high bits of addresses to be fixed. Indeed they usually are, but this is processor specific (could be slightly different on a high-end Intel Xeon and on a low-end FS1b AMD processor, and could be different in the near-future processors).

BTW, this is OS (and processor) specific. And take ASLR & VDSO into account.

Look e.g. inside the source code of bigloo, file runtime/Include/bigloo.h for an example of tagging.

If implementing your own interpreter, a related issue is the garbage collector. I would suggest to use Boehm's conservative GC; it is probably not the fastest or the best, but it is good enough (and thread-friendly). By experience (e.g. in MELT), debugging a GC is time-consuming.

Also, today, the memory is much more important than the tag computation. Be aware of the CPU cache, ...

If on Linux, look into /proc/self/maps or /proc/$$/maps (see proc(5))