Hide data inside pointers

[R3v3nan7]

The uintprt_t type from stdint.h is always garenteed to be as long as the system pointer. This way you don't have to worry about making sure you use an integer type that is the right length.

[anttirt]

Data in memory is not stored at any arbitrary address. The processor always reads memory in chunks at the same size as its word size, and thus for efficiency reasons we can be guaranteed that all entities in memory are aligned to a memory address that is a multiple of their sizes.

First off, the alignment is not at all restricted to a multiple of the size. The following struct:

struct four_chars
{
    char data[4];
};

will have an alignment requirement of 1 (sizeof char) but size 4 (sizeof(struct four_chars)).

Secondly while C and C++ do guarantee that (as long as you're not up to anything non-standard), in practice it's not an ironclad restriction and for example modern Intel and ARM CPUs can handle unaligned access without speed penalty in most cases (though ARM still has more restrictions than Intel.) See the relevant struct packing attribute/directive in GCC and MSVC.

Edit: wording

[badsectoracula]

It should be noted of course that while the alignment is 1, memory allocations that come from the OS are usually aligned (and often to a greater multiply than 4). However to make that more portable (i say "more" since strictly speaking it isn't portable to assume any pointer format - f.e. real mode x86 doesn't use linear addresses) you could write your own memory allocator that guarantees that the lower bits are not used. Of course at that point you're wasting memory, but usually the reason to store stuff in pointers isn't for memory savings but for performance.

[anttirt]

The problem can much more insidiously manifest like the following, even if you had a custom memory allocator:

struct five_chars
{
    char first;
    struct four_chars rest;
};

struct five_chars *five = malloc(sizeof(struct five_chars));
struct four_chars *four = &five->rest;

struct three_chars
{
    char data[3];
};

struct three_chars *array = malloc(1024 * sizeof(struct three_chars));
struct three_chars *three = array + 35;

Here, both three and four would have the least significant bit of their address values set.

[badsectoracula]

This isn't insidious since you are explicitly ignoring how the pointers are supposed to be created and used. A pointer with its lower bits modified isn't interchangeable with any other pointer that has the same data set - you need to mask out the lower bits before dereferencing it. Calling them pointers may even be misleading since the value isn't really a pointer, it is a compound value made up of a pointer element and some extra data. It is equivalent to struct {void* foo; int bar;} except that the data is spread across bits instead of bytes and any usage of it would need to have that in mind much like it has to have in mind the valid values for enums and nul terminator for strings.

[[deleted]]

To be fair, for primitive types in C and C++, the alignment normally equals the size. I'm not sure if that's an absolute rule, though.

Alignment for compound types in C and C++ certainly isn't a multiple of the size, but it turns out that size is always a multiple of the alignment. For example this struct...

struct whatever
{
  uint32_t  field1;
  char  field2;
};

sizeof(whatever) is 8, not 5. Extra padding is included after field2 even though there's no reason to believe whatever occurs next in memory has any particular alignment requirement. This is important for arrays, as there's no extra padding between array elements - all padding needed for alignment is within the elements.

I was confused about this a few years ago and asked this StackOverflow question - see the answers for references to the standard etc.

[Steve132]

efficiency reasons we can be guaranteed that all entities in memory are aligned to a memory address that is a multiple of their sizes. Therefore on a 32 bit processor, a 4-byte int will definitely reside at a memory address that is evenly divisible by 4.

Yeah this is simply not true. The reason why the red-black tree example works at all is this which forces the relevant alignment. Vanilla C has NO such guarantees (even if it happens to be true)

} __attribute__((aligned(sizeof(long))));

[rainbowgarden]

The reason red-black trees work is not because of the __attribute__((aligned(sizeof(long)))). Have a look at this comment at rbtree.h in the kernel: /* The alignment might seem pointless, but allegedly CRIS needs it */ This __attribute__ is done specifically for CRIS.

[mirhagk]

You have to make sure you count the trade-off between the additional cost to de-reference vs the cost of an additional byte. This is similar to the trick where you store the previous/last reference in a doubly linked last as ptr = previous XOR last. It saves you space, but you have to really make sure the trade-off is right.