net/radix: Various minor improvements and cleanups

- Change 'rn_bit' and 'rm_bit' from type 'short' to 'int', for
consistency with the other types. This doesn't change the structure
size becaus

net/radix: Various minor improvements and cleanups

- Change 'rn_bit' and 'rm_bit' from type 'short' to 'int', for
consistency with the other types. This doesn't change the structure
size because of the implicit padding. However, the userland netstat(1)
utility must be recompiled with the updated header.
- Rename variable 'b' to 'bit' for clarity.
- Adjust the parameter orders of rn_search_m() for consistency.
- Various style cleanups.

show more ...

net/radix: Add and update various function/structure comments

While there, adjust several parameter names to match the prototypes.

net/radix: Update parameter types to save callers from boring casts

Change the function parameters of key/address/mask from type
'const char *' to 'const void *', so the callers don't need to do bor

net/radix: Update parameter types to save callers from boring casts

Change the function parameters of key/address/mask from type
'const char *' to 'const void *', so the callers don't need to do boring
casts in passing them without causing any compilation warnings.

In addition, change rn_key/rn_mask/rmu_mask to 'const u_char *' type as
that makes more sense.

Referred to FreeBSD.

show more ...

net/radix: Update rn_inithead() parameter type to avoid boring casts

Change to use the proper 'struct radix_node_head **' instead of an
opaque 'void **'.

net/radix: Implement rn_flush() and rn_freehead()

rn_flush() flushes all nodes in the given radix tree and thus makes the
tree empty; rn_freehead() can then free the emptied tree.

The separation of

net/radix: Implement rn_flush() and rn_freehead()

rn_flush() flushes all nodes in the given radix tree and thus makes the
tree empty; rn_freehead() can then free the emptied tree.

The separation of flushing and freeing is required to support the use
case in ipfw2, which needs to flush a table without destroying it.

A mask tree is somewhat special, because its nodes are allocated inside
this radix code, so the rn_freemask() callback function is provided to
be used in rn_flush() to flush a mask tree and reclaim its memory.

These APIs can help the radix users to easily flush and free the radix
trees without rolling their own versions.

show more ...

net/radix: Clean up rn_newpair() for readability

- Add a brief description.
- Rename variables to read and understand better.

net/radix: Document rn_inithead() and change to use byte offset

The radix code only supports offset bit being multiple of bytes but not
any byte fraction, so it's clearer and better to just use byte

net/radix: Document rn_inithead() and change to use byte offset

The radix code only supports offset bit being multiple of bytes but not
any byte fraction, so it's clearer and better to just use byte offset
instead of bit offset. In addition, the caller can be easier to
determine this argument using offsetof().

On the other hand, ignore this off_bytes parameter and auto set it to
zero when to create a mask tree.

Also add a detailed description for rn_inithead().

show more ...

net/radix: Make this code also usable in userland

sbin/routed bundles its own radix implementation that is basically an
old copy of the kernel sys/net/radix code. Make this kernel version
also usab

net/radix: Make this code also usable in userland

sbin/routed bundles its own radix implementation that is basically an
old copy of the kernel sys/net/radix code. Make this kernel version
also usable in userland so that we can get rid of the duplicate version
in sbin/routed.

show more ...

net/radix: Add 'const' qualifier to rn_zeros/rn_ones globals

These two globals are no longer modified during the rn_init(), so just
add 'const' qualifier to them.

net/radix: Fix a 'sign-compare' compilation warning in rn_insert()

This compilation warning shows up in userland build, although not in
kernel build. Fix it for the forthcoming work to use this cod

net/radix: Fix a 'sign-compare' compilation warning in rn_insert()

This compilation warning shows up in userland build, although not in
kernel build. Fix it for the forthcoming work to use this code in
userland 'sbin/routed'.

show more ...

net/radix: Fix a subtle type cast error in rn_lexobetter()

The char byte comparison should be cast to 'unsigned'; otherwise, the
result is wrong in some special cases, e.g.,
rn_lexobetter(<255.255.0

net/radix: Fix a subtle type cast error in rn_lexobetter()

The char byte comparison should be cast to 'unsigned'; otherwise, the
result is wrong in some special cases, e.g.,
rn_lexobetter(<255.255.0.0>, <255.255.128.0>) was giving 'true' while
'false' is expected.

While there, add a brief function description and clean up a bit for
readability.

show more ...

net/radix: Clean up rn_refines() for readability

net/radix: Various minor style tweaks

net/radix: Add 'const' qualifier to input key/netmask

They're only referenced in the radix tree and wouldn't be modified, so
add 'const' qualifier to make it clear.

Adjust callers for this change a

net/radix: Add 'const' qualifier to input key/netmask

They're only referenced in the radix tree and wouldn't be modified, so
add 'const' qualifier to make it clear.

Adjust callers for this change accordingly.

Referred to FreeBSD.

show more ...

net/radix: Remove unnecessary prototype of local functions

Personally I think it looks cleaner without these prototypes. Meanwhile,
move the RN_DEBUG related static variables to the top part.

net/radix: Improve clen() macro by casting result to int

Obtained-from: FreeBSD

net/radix: Simplify mask manipulation in rn_addmask()

Since the max key length is known, so use an on-stack variable instead
of memory allocation for the 'addmask_key' variable. Therefore also get

net/radix: Simplify mask manipulation in rn_addmask()

Since the max key length is known, so use an on-stack variable instead
of memory allocation for the 'addmask_key' variable. Therefore also get
rid of the 'rnh_last_zeroed' member from 'radix_node_head' struct.
Rename 'rnh_last_zeroed' to its origin 'rnh_addrsize' instead of
removing it.

Referred-to: FreeBSD

show more ...

net/radix: Rename Free() to R_Free() to better align with R_Malloc()

Also reduces the chances of conflicting with other macros.

net/radix: Use the standard type 'bool' and true/false values

net/radix: Add 'const' qualifier for rn_refines()

net/radix: Fix rn_refines() and add the function description

After 'n++' called in the 'longer' assignment, the clen(n) becomes
invalid since the first byte is no longer the key length. This caused

net/radix: Fix rn_refines() and add the function description

After 'n++' called in the 'longer' assignment, the clen(n) becomes
invalid since the first byte is no longer the key length. This caused
the function to always return FALSE and could lead to out-of-bound
memory access.

Fix the bug, and describe the function's usage and return value.

The bug was introduced in commit 2e9572d in 2004.

Reported-by: dczheng

show more ...

route: Routes should only be accessed from the first netisr_ncpus netisrs.

Replicate routes to the first netisr_ncpus CPUs, instead of all CPUs.

rtsock: Make sysctl NET_RT_DUMP MPSAFE.

- Add rn_walktree_at(), which walks the radix tree from a target node,
if it could be found, or from the closest node of the target node.
- Allocate tempora

rtsock: Make sysctl NET_RT_DUMP MPSAFE.

- Add rn_walktree_at(), which walks the radix tree from a target node,
if it could be found, or from the closest node of the target node.
- Allocate temporary buffer for rtm batch, which should be large enough
for duplicated keys. We could consider reallocate it if there are
any real cases that this temporary buffer could not hold rtms for all
duplicated keys. In the current implementation, it just logs one
error and stop.
- Convert the rtentries to rtms in temporary buffer in netisr; unlike
what we do for inpcbs, routing table could be in inconsistent state
(due to blocking malloc), if we are not accessing the routing table
in netisr. If there is no more space in the temporary buffer, the
current rtentry's key and netmask are saved and we will start from it
next time. Since rn_walktree_at() only starts from the first node of
duplicated keys, we have to make sure that there is enough space for
all duplicated keys in the temoprary buffer.
- Once the temporary buffer can't hold more rtms, the rtms in it will
be delivered to userland. And we start converting the rtentries in
netisr from the last node again, until all rtentries are iterated.

show more ...

kernel: Fix some boolean_t vs. int confusion.

When boolean_t is defined to be _Bool instead of int (not part of this
commit), this is what gcc is sad about.

radix: Unshare radix mask tree resources

- Make free mask list per-cpu
- Embed mask last zeroed position into mask radix tree head