ALIGN MACRO understanding

[anish singh]

On Nov 6, 2013 10:38 PM, "Mandeep Sandhu" <mandeepsandhu.chd at gmail.com> wrote:
>
> On Thu, Nov 7, 2013 at 11:04 AM, sdptroy3 at gmail.com <sdptroy3 at gmail.com> wrote:
> > While going through kernel source , I came across this ALIGN macro
> >
> > #define ALIGN(x, a)             __ALIGN_KERNEL((x), (a))
> >
> > and
> >
> > #define __ALIGN_KERNEL(x, a)            __ALIGN_KERNEL_MASK(x,
> > (typeof(x))(a) - 1)
> >
> > #define __ALIGN_KERNEL_MASK(x, mask)    (((x) + (mask)) & ~(mask))
> >
> >
> > What does this macro do? I have read this article
> > http://stackoverflow.com/questions/13122846/align-macro-kernel but it was
> > not of much help.
>
> Try the above calculation for a small number, and align it to a 4 byte
> boundary. That'll clear things up as to how this macro is working.

#ALIGN MACRO EXPLANATION

So let me try it:
What we are looking for is a function or macro
which can give a aligned result when given any
input i.e. even if it is already aligned we want to
give the same number.

align(input_no, align_to)
align(120,4) = 120 not 124 ---> very important

One way of writing it is keep multiplying 4 repetively
until you get a number more than 120 i.e. brute force.

Effectively we are looking for next multiple of 4 which
is greater than the number given.

Second way is to use logic so that we don't need to
resort to brute force.
align(120, 4) = 120
align(121, 4) = 124
align(122, 4) = 124
align(123, 4) = 124

121+?(4) = 125
so we have 125 and from 125 we can somehow(explained below) get 124.
122+?(4) = 126
so we have 126 and from 126 we can somehow get 124
123+?(4) = 127
so we have 127 and from 127 we can somehow get 124
120+?(4) = 124
so here is the problem, we will return 124 in this case right?

So how do we take care of this condition?
120+3 will not crossover to 124 and we can somehow get 120 from 123.
121+3=124
122+3=125
123+3=126

So we are making sure that from one boundary i.e. 120 in this case,
we are not crossing over to another boundary i.e. 124 when input is 120.
And how are we doing that is by adding (n-1) and that is the reason
we don't add n.
Now the part come of anding with ~(n-1).As Mandeep explained that
all power of 2 numbers when subtracted with 1 gives the result where
all MSB bits are set to 1 & LSB set to 0(We use the same logic
to find out total bits set in a number^^) as below:
~(4-1) = 0xFC(11111100)
~(8-1) = 0xF8(11111000)
....
....

We know that any number which is a multiple of 4 should have last two
bits set to 0 right(4 itself is the first multiple of 4 which has last two bit
set to 0)? Take an example and it would become very clear
to you.Same thing applies to multiple of 8.

How do we achieve that?So here the comes the ANDING with ~(n-1) because
if you see {~(4-1) = 11111100} this then we have here last two bits set to 0.
And this is the reason we AND with ~(n-1) so that we can clear last two bits.

If anyone thinks otherwise I would appreciate to add more.
>
> So for example, lets align '6' to a '4' byte boundary. This should result in 8.
>
> ALIGN(6, 4) = __ALIGN_KERNEL((6), (4))
>
> __ALIGN_KERNEL(6, 4) =  __ALIGN_KERNEL_MASK(6, (typeof(6)) (4) - 1)
>
> typeof(6) is 'int' & 4 - 1 = 3.
>
> __ALIGN_KERNEL_MASK(6, (int) 3) = (((6) + (3)) & ~(3))
>
> Assuming only 4 bits for simplicity):
> 6 + 3 = 9 = 1001
> ~3 = 1100
>
> __ALIGN_KERNEL_MASK(6, (int) 3) = (((6) + (3)) & ~(3)) = 1001 & 1100 = 1000 = 8
>
> Since alignment is a power of 2, subtracting 1 from it sets all bits
> after the (original) MSB to 1 (eg: 4 = 100 & 3 = 011).
>
> Adding this 'mask' (3) ensures that the resulting number is at least
> larger than the next multiple of 'a' that is greater than x (so in our
> case 9 > 8, and 8 is a multiple of 4 which is > 6 (x)).
>
> Now bitwise AND-ing with the 1s compliment of mask ensures that all
> bits, except the MSB, will be set to 0, thus resulting in a number
> aligned at a multiple of 'a'. In our case, the MSB was set when we did
> the addition.
>
> Hope this makes it a little clear.
>
> -mandeep
>
>
>
>
> >
> >
> > _______________________________________________
> > Kernelnewbies mailing list
> > Kernelnewbies at kernelnewbies.org
> > http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
> >
>
> _______________________________________________
> Kernelnewbies mailing list
> Kernelnewbies at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies