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

Question

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!

Answer 1

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

• Fast ceiling of an integer division in C / C++
• Rounding integer division (instead of truncating)
• Dividing two integers and rounding up the result, without using floating point
• What's the right way to implement integer division-rounding-up?

Answer 2

This is rounding up. You add (PAGE_SIZE - 1) to nbytes so in case you have an exact number of PAGE_SIZE nbytes then you get the minimum number of pages you need, and if you pass it by one, then you get a new page to give space for the extra byte.

Answer 3

There is another way to make it with the log2 of the page size. In the Linux kernel source, it is PAGE_SHIFT. For example, if PAGE_SIZE is 4096 = 2^12 bytes, PAGE_SHIFT is 12 (i.e. log2(2^12)). So, to get the number of pages for a given size, the following formula is often used:

pages = (size + PAGE_SIZE - 1) >> PAGE_SHIFT

By the way, the page size is often defined as:

#define PAGE_SIZE (1 << PAGE_SHIFT)