Question about round_up macro

Question

#define ROUND_UP(N, S) ((((N) + (S) - 1) / (S)) * (S))

With the above macro, could someone please help me on understanding the "(s)-1" part, why's that?

and also macros like:

#define PAGE_ROUND_DOWN(x) (((ULONG_PTR)(x)) & (~(PAGE_SIZE-1)))
#define PAGE_ROUND_UP(x) ( (((ULONG_PTR)(x)) + PAGE_SIZE-1)  & (~(PAGE_SIZE-1)) ) 

I know the "(~(PAGE_SIZE-1)))" part will zero out the last five bits, but other than that I'm clueless, especially the role '&' operator plays.

Thanks,

Answer 1

The ROUND_UP macro is relying on integer division to get the job done. It will only work if both parameters are integers. I'm assuming that N is the number to be rounded and S is the interval on which it should be rounded. That is, ROUND_UP(12, 5) should return 15, since 15 is the first interval of 5 larger than 12.

Imagine we were rounding down instead of up. In that case, the macro would simply be:

#define ROUND_DOWN(N,S) ((N / S) * S)

ROUND_DOWN(12,5) would return 10, because (12/5) in integer division is 2, and 2*5 is 10. But we're not doing ROUND_DOWN, we're doing ROUND_UP. So before we do the integer division, we want to add as much as we can without losing accuracy. If we added S, it would work in almost every case; ROUND_UP(11,5) would become (((11+5) / 5) * 5), and since 16/5 in integer division is 3, we'd get 15.

The problem comes when we pass a number that's already rounded to the multiple specified. ROUND_UP(10, 5) would return 15, and that's wrong. So instead of adding S, we add S-1. This guarantees that we'll never push something up to the next "bucket" unnecessarily.

The PAGE_ macros have to do with binary math. We'll pretend we're dealing with 8-bit values for simplicity's sake. Let's assume that PAGE_SIZE is 0b00100000. PAGE_SIZE-1 is thus 0b00011111. ~(PAGE_SIZE-1) is then 0b11100000.

A binary & will line up two binary numbers and leave a 1 anywhere that both numbers had a 1. Thus, if x was 0b01100111, the operation would go like this:

  0b01100111  (x)
& 0b11100000  (~(PAGE_SIZE-1))
------------
  0b01100000

You'll note that the operation really only zeroed-out the last 5 bits. That's all. But that was exactly that operation needed to round down to the nearest interval of PAGE_SIZE. Note that this only worked because PAGE_SIZE was exactly a power of 2. It's a bit like saying that for any arbitrary decimal number, you can round down to the nearest 100 simply by zeroing-out the last two digits. It works perfectly, and is really easy to do, but wouldn't work at all if you were trying to round to the nearest multiple of 76.

PAGE_ROUND_UP does the same thing, but it adds as much as it can to the page before cutting it off. It's kinda like how I can round up to the nearest multiple of 100 by adding 99 to any number and then zeroing-out the last two digits. (We add PAGE_SIZE-1 for the same reason we added S-1 above.)

Good luck with your virtual memory!