ALIGN MACRO understanding
While going through kernel source , I came across this ALIGN macro #define ALIGN <http://lxr.free-electrons.com/ident?i=ALIGN>(x <http://lxr.free-electrons.com/ident?i=x>, a <http://lxr.free-electrons.com/ident?i=a>) __ALIGN_KERNEL <http://lxr.free-electrons.com/ident?i=__ALIGN_KERNEL>((x <http://lxr.free-electrons.com/ident?i=x>), (a <http://lxr.free-electrons.com/ident?i=a>)) and #define __ALIGN_KERNEL <http://lxr.free-electrons.com/ident?i=__ALIGN_KERNEL>(x <http://lxr.free-electrons.com/ident?i=x>, a <http://lxr.free-electrons.com/ident?i=a>) __ALIGN_KERNEL_MASK <http://lxr.free-electrons.com/ident?i=__ALIGN_KERNEL_MASK>(x <http://lxr.free-electrons.com/ident?i=x>, (typeof(x <http://lxr.free-electrons.com/ident?i=x>))(a <http://lxr.free-electrons.com/ident?i=a>) - 1) #define __ALIGN_KERNEL_MASK <http://lxr.free-electrons.com/ident?i=__ALIGN_KERNEL_MASK>(x <http://lxr.free-electrons.com/ident?i=x>, mask <http://lxr.free-electrons.com/ident?i=mask>) (((x <http://lxr.free-electrons.com/ident?i=x>) + (mask <http://lxr.free-electrons.com/ident?i=mask>)) & ~(mask <http://lxr.free-electrons.com/ident?i=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.
On Thu, Nov 7, 2013 at 11:04 AM, sdptroy3@gmail.com <sdptroy3@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. 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@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
On Nov 6, 2013 10:38 PM, "Mandeep Sandhu" <mandeepsandhu.chd@gmail.com> wrote:
On Thu, Nov 7, 2013 at 11:04 AM, sdptroy3@gmail.com <sdptroy3@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@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
_______________________________________________ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
On Fri, Nov 8, 2013 at 1:53 PM, anish singh <anish198519851985@gmail.com> wrote:
On Nov 6, 2013 10:38 PM, "Mandeep Sandhu" <mandeepsandhu.chd@gmail.com> wrote:
On Thu, Nov 7, 2013 at 11:04 AM, sdptroy3@gmail.com <sdptroy3@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
participants (3)
-
anish singh -
Mandeep Sandhu -
sdptroy3＠gmail.com