CVS log for src/common/lib/libc/gen/radixtree.c

Up to [cvs.NetBSD.org] / src / common / lib / libc / gen

Request diff between arbitrary revisions

Keyword substitution: kv
Default branch: MAIN

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.

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 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.

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%) 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.

fix few typos in comments and log messages.

fix various typos in comment, documentation and log messages.

Remove extra semicolon.

Ooops, restore accidently removed files from merge mishap

Sync with HEAD

Mostly merge changes from HEAD upto 20200411

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 fail, never make partial adjustments
  to the tree.

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

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.

Merge changes from current as of 20200406

Sync with head.

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 frequented pool caches as the pvpool and anonpool

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 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.

Merge radixtree changes from yamt-pagecache.

suppress gcc warnings

comments.  some ascii arts to explain memory consumption.

make tag-variants of radix tree functions take and return a mask of tags
rather than tag ids so that they can deal with multiple tags at once.

comment

comments

radix_tree_gang_lookup_node and its variants: add a option to stop on a hole.

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

add a function to check if a tree is empty.

include string.h for memset

radix_tree_clear_tag:
- fix a bug which errornously clears tags on intermediate nodes.
- add comments.

radixtree: assertions

radixtree: comments

radixtree: comments

fix _STANDALONE build

- fix _STANDALONE build.
- use __CTASSERT instead of CTASSERT.  enable it for userland.
- __read_mostly.

Sync with HEAD

file radixtree.c was added on branch bouyer-quota2 on 2011-03-05 15:08:32 +0000

an implementation of radix tree.  the idea from linux.