Unlike many userland applications, there are large portions of the
kernel that need to do bit-level manipulations. These generally fall
into a few distinct areas:
The main low-level allocators in Solaris are
kmem handles your standard page-backed memory allocation, while
vmem handles the more abstract concept of allocating from spaces
of integers. kmem actually layers on top of vmem, but
the details are beyond the scope of this blog entry.
\* Macros for various sorts of alignment and rounding when the alignment
\* is known to be a power of 2.
#defineP2ALIGN(x, align)((x) & -(align))
#defineP2PHASE(x, align)((x) & ((align) - 1))
#defineP2NPHASE(x, align)(-(x) & ((align) - 1))
#defineP2ROUNDUP(x, align)(-(-(x) & -(align)))
#defineP2END(x, align)(-(~(x) & -(align)))
#defineP2PHASEUP(x, align, phase)((phase) - (((phase) - (x)) & -(align)))
#defineP2CROSS(x, y, align)(((x) \^ (y)) > (align) - 1)
\* Determine whether two numbers have the same high-order bit.
#defineP2SAMEHIGHBIT(x, y)(((x) \^ (y)) < ((x) & (y)))
-x = ~x + 1
x = ...xxxxx10000...
x-1 = ...xxxxx01111...
~x = ...XXXXX01111...
-x = ~x+1 = ...XXXXX10000...
|P2ALIGN||x & -align|
clears all bits below align, rounding x down to the
next lower multiple of align
|P2PHASE||x & (align - 1)|
clears all bits above or equal to align, getting(x % align), the phase of x with regards toalign
|P2NPHASE||(-x) & (align - 1)|
This is the first tricky formula. We negate x, and get
its phase. The result is the same as (align - P2PHASE(x,
align)) % align, but is much faster to compute.
|P2ROUNDUP||-((-x) & -align)|
This can be re-written as -P2ALIGN(-x, align), which shows how
the operation works; "negate, round down, negate" is the same as
So we round x up to the next align boundary.
|P2END||-((~x) & -align)||This can be re-written as-((-x-1) & -align) = P2ROUNDUP(x+1, align); round up(x+1) to the next align boundary. This gets|
the end address of the current align block.
((phase - x) &
This can be re-written as (phase + P2ROUNDUP(x - phase, align)).
So what we've done is rounded up x to have a specificphase with regards to align. (If you've got
some linear algebra under your belt, this is similar to
transforming f(y) = P2ROUNDUP(y, align) into a
coordinate system with x = y + phase)
|P2CROSS||(x \^ y) > (align-1)||(x \^ y) has bits set wherever x and y|
differ. This just tests to see if they differ in any position
above the alignment, which will only be the case if [x, y]
crosses an align boundary.
|P2SAMEHIGHBIT||(x \^ y) < (x & y)|
Similar to P2CROSS; here, we're checking that the first bit that
differs is less than the highest set bit the two have in common.