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 page rounding macros assume that `PAGE_SIZE is a power of two, such as:

0x0400    -- 1 KiB
0x0800    -- 2 KiB`
0x1000    -- 4 KiB

The value of PAGE_SIZE - 1, therefore, is all one bits:

0x03FF
0x07FF
0x0FFF

Therefore, if integers were 16 bits (instead of 32 or 64 - it saves me some typing), then the value of ~(PAGE_SIZE-1) is:

0xFC00
0xFE00
0xF000

When you take the value of x (assuming, implausibly for real life, but sufficient for the purposes of exposition, that ULONG_PTR is an unsigned 16-bit integer) is 0xBFAB, then

PAGE_SIZE         PAGE_ROUND_DN(0xBFAB)   PAGE_ROUND_UP(0xBFAB)

0x0400     -->    0xBC00                  0xC000
0x0800     -->    0xB800                  0xC000
0x1000     -->    0xB000                  0xC000

The macros round down and up to the nearest multiple of a page size. The last five bits would only be zeroed out if PAGE_SIZE == 0x20 (or 32).

Answer 2

Using integer arithmetic, dividing always rounds down. To fix that, you add the largest possible number that won't affect the result if the original number was evenly divisible. For the number S, that largest possible number is S-1.

Rounding to a power of 2 is special, because you can do it with bit operations. A multiple of 2 will aways have a zero in the bottom bit, a multiple of 4 will always have zero in the bottom two bits, etc. The binary representation of a power of 2 is a single bit followed by a bunch of zeros; subtracting 1 will clear that bit, and set all the bits to the right. Inverting that value creates a bit mask with zeros in the places that need to be cleared. The & operator will clear those bits in your value, thus rounding the value down. The same trick of adding (PAGE_SIZE-1) to the original value causes it to round up instead of down.

Answer 3

The & makes it so.. well ok, lets take some binary numbers.

(with 1000 being page size)
PAGE_ROUND_UP(01101b)=
01101b+1000b-1b & ~(1000b-1b) =
01101b+111b & ~(111b) =
01101b+111b & ...11000b = (the ... means 1's continuing for size of ULONG)
10100b & 11000b=
10000b

So, as you can see(hopefully) This rounds up by adding PAGE_SIZE to x and then ANDing so it cancels out the bottom bits of PAGE_SIZE that are not set

Answer 4

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!

Answer 5

Based on the current draft standard (C99) this macro is not entirely correct however, note that for negative values of N the result will almost certainly be incorrect.

The formula:

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

Makes use of the fact that integer division rounds down for non-negative integers and uses the S - 1 part to force it to round up instead.

However, integer division rounds towards zero (C99, Section 6.5.5. Multiplicative operators, item 6). For negative N, the correct way to 'round up' is: 'N / S', nothing more, nothing less.

It gets even more involved if S is also allowed to be a negative value, but let's not even go there... (see: How can I ensure that a division of integers is always rounded up? for a more detailed discussion of various wrong and one or two right solutions)