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

Issue

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

• 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?

Answered By - phuclv

Answer Checked By - Marilyn (WPSolving Volunteer)