radixtree: allocate memory with KM_NOSLEEP to prevent pagedaemon hangs

Revert the part of rev 1.32 (reapplying "Do away with separate pool_cache
for some kernel objects") that changed the memory all

radixtree: allocate memory with KM_NOSLEEP to prevent pagedaemon hangs

Revert the part of rev 1.32 (reapplying "Do away with separate pool_cache
for some kernel objects") that changed the memory allocation for radixtree
nodes from PR_NOWAIT to KM_SLEEP as part of changing from a pool to kmem.
uvm_pageinsert_tree() calls into the radixtree code while holding
the object's vmobjlock, but that same lock is taken by the pagedaemon
in the process of reclaiming pages, and if the pagedaemon happens to
choose the same object to reclaim from that uvm_pageinsert_tree()
is being called on, then these two threads will deadlock.
The previous code already handled memory allocation failures
in uvm_pageinsert_tree() so we can simply change it back to nosleep.

Fixes a hang reported by simonb@, and the fix was also tested by him.

show more ...

kmem_free() -> kmem_intr_free(). Spotted by rin@.

Repply this change with a couple of bugs fixed:

- Do away with separate pool_cache for some kernel objects that have no special
requirements and use the general purpose allocator instead. On one o

Repply this change with a couple of bugs fixed:

- Do away with separate pool_cache for some kernel objects that have no special
requirements and use the general purpose allocator instead. On one of my
test systems this makes for a small (~1%) but repeatable reduction in system
time during builds presumably because it decreases the kernel's cache /
memory bandwidth footprint a little.
- vfs_lockf: cache a pointer to the uidinfo and put mutex in the data segment.

show more ...

Back out recent change to replace pool_cache with then general allocator.
Will return to this when I have time again.

- Do away with separate pool_cache for some kernel objects that have no special
requirements and use the general purpose allocator instead. On one of my
test systems this makes for a small (~1%)

- Do away with separate pool_cache for some kernel objects that have no special
requirements and use the general purpose allocator instead. On one of my
test systems this makes for a small (~1%) but repeatable reduction in system
time during builds presumably because it decreases the kernel's cache /
memory bandwidth footprint a little.
- vfs_lockf: cache a pointer to the uidinfo and put mutex in the data segment.

show more ...

fix few typos in comments and log messages.

fix various typos in comment, documentation and log messages.

Remove extra semicolon.

Match the naming convention in the file.

PR kern/54979 (radixtree might misbehave if ENOMEM)

- radix_tree_insert_node(): if the insert failed due to ENOMEM, roll back
any updates made to the tree.

- radix_tree_grow(): either succeed or

PR kern/54979 (radixtree might misbehave if ENOMEM)

- radix_tree_insert_node(): if the insert failed due to ENOMEM, roll back
any updates made to the tree.

- radix_tree_grow(): either succeed or fail, never make partial adjustments
to the tree.

- radix_tree_await_memory(): allocate & free the maximum possible number of
nodes required by any insertion.

show more ...

Rename radix_tree_node_clean_p() to radix_tree_node_sum() and have it return
the computed sum. Use to replace any_children_tagmask(). Simpler & faster.

gang_lookup_scan(): if a dense scan and the first sibling doesn't match,
the scan is finished.

Add a radix_tree_await_memory(), for kernel use.

initialize radix_tree_node_cache with PR_LARGECACHE

this increases the cache groups from 15 to 63 items in order
to reduce traffic between pool cache layers
this is the same as for other highly freq

initialize radix_tree_node_cache with PR_LARGECACHE

this increases the cache groups from 15 to 63 items in order
to reduce traffic between pool cache layers
this is the same as for other highly frequented pool caches as the pvpool and anonpool

show more ...

Fix warning that appears when compiling in kernel.

Delete the counter from "struct radix_tree_node", and in the one place we
need a non-zero check, substitute with a deterministic bitwise OR of all
values in the node. The structure then becomes cach

Delete the counter from "struct radix_tree_node", and in the one place we
need a non-zero check, substitute with a deterministic bitwise OR of all
values in the node. The structure then becomes cache line aligned.

For each node we now need only touch 2 cache lines instead of 3, which makes
all the operations faster (measured), amortises the cost of not having a
counter, and will avoid intra-pool-page false sharing on MP.

show more ...

Merge radixtree changes from yamt-pagecache.

comments

add radix_tree_empty_tagged_tree_p, a "tagged" variant of
radix_tree_empty_tree_p.

- add functions to scan the tree in the reverse order
(i wonder if it's the longest function name in the tree)
- assertions
- comments
- fix and update unittest

unwarp a short line

constify

fix "get_tag" result of unittest

make the output of unittest a little machine-readable

int -> unsigned int where appropriate