Search code examples
memory-managementlinux-kernelroundingdivisioncounting

Why do memory managers use (size + PAGE_SIZE-1) / PAGE_SIZE to calculate the number of pages to allocate?

I have met such a formula multiple times in various places (e.g.; Linux kernel and glibc). Why do they use this formula instead of simply:

pages = (size / PAGE_SIZE) + 1;

As a guess, I think the problem with the formula above is when the size is PAGE_SIZE aligned (a multiple of PAGE_SIZE) because, in such a case, it reports one more page than needed, thus we have to also do:

pages = (size / PAGE_SIZE) + 1;
if (!(size & (PAGE_SIZE-1))) /* is size a multiple of PAGE_SIZE? */
    pages--;

which is obviously more code than just (size + PAGE_SIZE-1) / PAGE_SIZE!

Solution

  • Yes, it's used to get the ceiling of the division result, i.e. rounding the quotient up

    The problem with

    pages = (size / PAGE_SIZE) + 1;
if (!(size & (PAGE_SIZE-1))) /* is size a multiple of PAGE_SIZE? */
    pages--;

    is not only a lot more code but also the fact that

    • it has worse performance due to the branch
    • it only works for powers of 2

    Of course page size in a binary computer is always a power of 2, but (size + PAGE_SIZE-1) / PAGE_SIZE works for any value of the divisor

    See also