Formula for memory alignment

Question

While browsing through some kernel code, I found a formula for memory alignment as

aligned = ((operand + (alignment - 1)) & ~(alignment - 1))

So then I even write a program for this:

#include <stdio.h>

int main(int argc, char** argv) {
    long long operand;
    long long alignment;
    if(argv[1]) {
        operand = atol(argv[1]);
    } else {
        printf("Enter value to be aligned!\n");
        return -1;
    }
    if(argv[2]) {
        alignment = strtol(argv[2],NULL,16);
    } else {
        printf("\nDefaulting to 1MB alignment\n");
        alignment = 0x100000;
    }
    long long aligned = ((operand + (alignment - 1)) & ~(alignment - 1));
    printf("Aligned memory is: 0x%.8llx [Hex] <--> %lld\n",aligned,aligned);
    return 0;
}

But I don't get this logic at all. How does this work?

Answer 1

Basically, the formula increase an integer operand (address) to a next address aligned to the alignment.

The expression

aligned = ((operand + (alignment - 1)) & ~(alignment - 1))

is basically the same as a bit easier to understand formula:

aligned = int((operand + (alignment - 1)) / alignment) * alignment

For example, having operand (address) 102 and alignment 10 we get:

aligned = int((102 + 9) / 10) * 10
aligned = int(111 / 10) * 10
aligned = 11 * 10
aligned = 110

First we add to the address 9 and get 111. Then, since our alignment is 10, basically we zero out the last digit, i.e. 111 / 10 * 10 = 110

Please note, that for each power of 10 alignment (i.e. 10, 100, 1000 etc) we basically zeroing out last digits.

On most CPUs, division and multiplication operations take much more time than bitwise operations, so let us get back to the original formula:

aligned = ((operand + (alignment - 1)) & ~(alignment - 1))

The second part of the formula makes sense only when alignment is a power of 2. For example:

... & ~(2 - 1) will zero last bit of address.
... & ~(64 - 1) will zero last 5 bits of address.
etc

Just like with zeroing out last few digits of an address for power of 10 alignments, we zeroing out last few bits for power of 2 alignments.

Hope it does make sense for you now.