ALIGN MACRO understanding

[Mandeep Sandhu]

On Fri, Nov 8, 2013 at 1:53 PM, anish singh <anish198519851985 at gmail.com> wrote:
> 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.

I think this is a good point that I did NOT stress enough upon in my
last mail, i.e setting the last 'n' bits to 0 makes the resulting
number a multiple of 2^n.

Now the only thing that the addition further does is that it ensures
that the resulting number is greater than the number we asked the
alignment for BUT less than the next higher multiple of 'n'. So this
basically sets the MSB in the correct position.

>
> If anyone thinks otherwise I would appreciate to add more.

Good explanation!

-mandeep