#
1.34 |
|
04-May-2024 |
chs |
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.
|
Revision tags: thorpej-ifq-base thorpej-altq-separation-base
|
#
1.33 |
|
23-Sep-2023 |
ad |
kmem_free() -> kmem_intr_free(). Spotted by rin@.
|
#
1.32 |
|
23-Sep-2023 |
ad |
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.
|
#
1.31 |
|
12-Sep-2023 |
ad |
Back out recent change to replace pool_cache with then general allocator. Will return to this when I have time again.
|
#
1.30 |
|
10-Sep-2023 |
ad |
- 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.
|
#
1.29 |
|
06-Mar-2023 |
andvar |
fix few typos in comments and log messages.
|
Revision tags: netbsd-10-0-RELEASE netbsd-10-0-RC6 netbsd-10-0-RC5 netbsd-10-0-RC4 netbsd-10-0-RC3 netbsd-10-0-RC2 netbsd-10-0-RC1 netbsd-10-base
|
#
1.28 |
|
24-May-2022 |
andvar |
fix various typos in comment, documentation and log messages.
|
Revision tags: cjep_sun2x-base1 cjep_sun2x-base cjep_staticlib_x-base1 cjep_staticlib_x-base
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-8-3-RELEASE netbsd-9-4-RELEASE netbsd-9-3-RELEASE netbsd-9-2-RELEASE netbsd-9-1-RELEASE netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.33 |
|
23-Sep-2023 |
ad |
kmem_free() -> kmem_intr_free(). Spotted by rin@.
|
#
1.32 |
|
23-Sep-2023 |
ad |
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.
|
#
1.31 |
|
12-Sep-2023 |
ad |
Back out recent change to replace pool_cache with then general allocator. Will return to this when I have time again.
|
#
1.30 |
|
10-Sep-2023 |
ad |
- 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.
|
#
1.29 |
|
06-Mar-2023 |
andvar |
fix few typos in comments and log messages.
|
Revision tags: netbsd-10-base
|
#
1.28 |
|
24-May-2022 |
andvar |
fix various typos in comment, documentation and log messages.
|
Revision tags: cjep_sun2x-base1 cjep_sun2x-base cjep_staticlib_x-base1 cjep_staticlib_x-base
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-3-RELEASE netbsd-9-2-RELEASE netbsd-9-1-RELEASE netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.31 |
|
12-Sep-2023 |
ad |
Back out recent change to replace pool_cache with then general allocator. Will return to this when I have time again.
|
#
1.30 |
|
10-Sep-2023 |
ad |
- 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.
|
#
1.29 |
|
06-Mar-2023 |
andvar |
fix few typos in comments and log messages.
|
Revision tags: netbsd-10-base
|
#
1.28 |
|
24-May-2022 |
andvar |
fix various typos in comment, documentation and log messages.
|
Revision tags: cjep_sun2x-base1 cjep_sun2x-base cjep_staticlib_x-base1 cjep_staticlib_x-base
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-3-RELEASE netbsd-9-2-RELEASE netbsd-9-1-RELEASE netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.31 |
|
12-Sep-2023 |
ad |
Back out recent change to replace pool_cache with then general allocator. Will return to this when I have time again.
|
#
1.30 |
|
10-Sep-2023 |
ad |
- 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.
|
#
1.29 |
|
06-Mar-2023 |
andvar |
fix few typos in comments and log messages.
|
Revision tags: netbsd-10-base
|
#
1.28 |
|
24-May-2022 |
andvar |
fix various typos in comment, documentation and log messages.
|
Revision tags: cjep_sun2x-base1 cjep_sun2x-base cjep_staticlib_x-base1 cjep_staticlib_x-base
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-3-RELEASE netbsd-9-2-RELEASE netbsd-9-1-RELEASE netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.29 |
|
06-Mar-2023 |
andvar |
fix few typos in comments and log messages.
|
Revision tags: netbsd-10-base
|
#
1.28 |
|
24-May-2022 |
andvar |
fix various typos in comment, documentation and log messages.
|
Revision tags: cjep_sun2x-base1 cjep_sun2x-base cjep_staticlib_x-base1 cjep_staticlib_x-base
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-3-RELEASE netbsd-9-2-RELEASE netbsd-9-1-RELEASE netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.28 |
|
24-May-2022 |
andvar |
fix various typos in comment, documentation and log messages.
|
Revision tags: cjep_sun2x-base1 cjep_sun2x-base cjep_staticlib_x-base1 cjep_staticlib_x-base
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-2-RELEASE netbsd-9-1-RELEASE netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.27 |
|
14-May-2020 |
msaitoh |
Remove extra semicolon.
|
Revision tags: bouyer-xenpvh-base2 phil-wifi-20200421 bouyer-xenpvh-base1 bouyer-xenpvh-base phil-wifi-20200411
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.26 |
|
11-Apr-2020 |
ad |
Match the naming convention in the file.
|
#
1.25 |
|
10-Apr-2020 |
ad |
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.
|
#
1.24 |
|
10-Apr-2020 |
ad |
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.
|
Revision tags: is-mlppp-base phil-wifi-20200406 ad-namecache-base3
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
branches: 1.20.2; Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-8-2-RELEASE netbsd-9-0-RELEASE netbsd-9-0-RC2 netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; 1.17.44; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.23 |
|
28-Jan-2020 |
ad |
gang_lookup_scan(): if a dense scan and the first sibling doesn't match, the scan is finished.
|
#
1.22 |
|
28-Jan-2020 |
ad |
Add a radix_tree_await_memory(), for kernel use.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.21 |
|
12-Jan-2020 |
para |
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
|
Revision tags: ad-namecache-base
|
#
1.20 |
|
05-Dec-2019 |
ad |
Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.20 |
|
05-Dec-2019 |
ad |
Fix warning that appears when compiling in kernel.
|
#
1.19 |
|
05-Dec-2019 |
ad |
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.
|
#
1.18 |
|
05-Dec-2019 |
ad |
Merge radixtree changes from yamt-pagecache.
|
Revision tags: netbsd-9-0-RC1 phil-wifi-20191119 netbsd-9-base phil-wifi-20190609 netbsd-8-1-RELEASE netbsd-8-1-RC1 pgoyette-compat-merge-20190127 pgoyette-compat-20190127 pgoyette-compat-20190118 pgoyette-compat-1226 pgoyette-compat-1126 pgoyette-compat-1020 pgoyette-compat-0930 pgoyette-compat-0906 netbsd-7-2-RELEASE pgoyette-compat-0728 netbsd-8-0-RELEASE phil-wifi-base pgoyette-compat-0625 netbsd-8-0-RC2 pgoyette-compat-0521 pgoyette-compat-0502 pgoyette-compat-0422 netbsd-8-0-RC1 pgoyette-compat-0415 pgoyette-compat-0407 pgoyette-compat-0330 pgoyette-compat-0322 pgoyette-compat-0315 netbsd-7-1-2-RELEASE pgoyette-compat-base netbsd-7-1-1-RELEASE tls-maxphys-20171202 matt-nb8-mediatek-base perseant-stdc-iso10646-base netbsd-8-base prg-localcount2-base3 prg-localcount2-base2 prg-localcount2-base1 prg-localcount2-base pgoyette-localcount-20170426 bouyer-socketcan-base1 pgoyette-localcount-20170320 netbsd-7-1-RELEASE netbsd-7-1-RC2 netbsd-7-nhusb-base-20170116 bouyer-socketcan-base pgoyette-localcount-20170107 netbsd-7-1-RC1 pgoyette-localcount-20161104 netbsd-7-0-2-RELEASE localcount-20160914 netbsd-7-nhusb-base pgoyette-localcount-20160806 pgoyette-localcount-20160726 pgoyette-localcount-base netbsd-7-0-1-RELEASE netbsd-7-0-RELEASE netbsd-7-0-RC3 netbsd-7-0-RC2 netbsd-7-0-RC1 netbsd-6-0-6-RELEASE netbsd-6-1-5-RELEASE netbsd-7-base yamt-pagecache-base9 netbsd-6-1-4-RELEASE netbsd-6-0-5-RELEASE tls-earlyentropy-base riastradh-xf86-video-intel-2-7-1-pre-2-21-15 riastradh-drm2-base3 netbsd-6-1-3-RELEASE netbsd-6-0-4-RELEASE netbsd-6-1-2-RELEASE netbsd-6-0-3-RELEASE rmind-smpnet-nbase netbsd-6-1-1-RELEASE riastradh-drm2-base2 riastradh-drm2-base1 riastradh-drm2-base rmind-smpnet-base netbsd-6-0-2-RELEASE netbsd-6-1-RELEASE netbsd-6-1-RC4 netbsd-6-1-RC3 agc-symver-base netbsd-6-1-RC2 netbsd-6-1-RC1 yamt-pagecache-base8 netbsd-6-0-1-RELEASE yamt-pagecache-base7 matt-nb6-plus-nbase yamt-pagecache-base6 netbsd-6-0-RELEASE netbsd-6-0-RC2 tls-maxphys-base matt-nb6-plus-base netbsd-6-0-RC1 yamt-pagecache-base5 yamt-pagecache-base4 netbsd-6-base yamt-pagecache-base3 yamt-pagecache-base2 yamt-pagecache-base
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
14-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
14-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
14-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
Revision tags: cherry-xenmp-base
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
Revision tags: bouyer-quota2-nbase
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.17 |
|
02-Nov-2011 |
yamt |
branches: 1.17.2; comments
|
#
1.16 |
|
25-Oct-2011 |
yamt |
add radix_tree_empty_tagged_tree_p, a "tagged" variant of radix_tree_empty_tree_p.
|
#
1.15 |
|
14-Oct-2011 |
yamt |
- 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
|
#
1.14 |
|
13-Oct-2011 |
yamt |
unwarp a short line
|
#
1.13 |
|
13-Oct-2011 |
yamt |
constify
|
#
1.12 |
|
13-Oct-2011 |
yamt |
fix "get_tag" result of unittest
|
#
1.11 |
|
14-Oct-2011 |
yamt |
make the output of unittest a little machine-readable
|
#
1.10 |
|
14-Oct-2011 |
yamt |
int -> unsigned int where appropriate
|
#
1.9 |
|
14-Oct-2011 |
yamt |
add a function to check if a tree is empty.
|
#
1.8 |
|
14-Oct-2011 |
yamt |
include string.h for memset
|
#
1.7 |
|
19-May-2011 |
yamt |
radix_tree_clear_tag: - fix a bug which errornously clears tags on intermediate nodes. - add comments.
|
#
1.6 |
|
19-May-2011 |
yamt |
radixtree: assertions
|
#
1.5 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.4 |
|
19-May-2011 |
yamt |
radixtree: comments
|
#
1.3 |
|
26-Apr-2011 |
yamt |
fix _STANDALONE build
|
#
1.2 |
|
14-Apr-2011 |
yamt |
- fix _STANDALONE build. - use __CTASSERT instead of CTASSERT. enable it for userland. - __read_mostly.
|
#
1.1 |
|
22-Feb-2011 |
yamt |
branches: 1.1.2; an implementation of radix tree. the idea from linux.
|
#
1.1.2.2 |
|
05-Mar-2011 |
bouyer |
Sync with HEAD
|
#
1.1.2.1 |
|
22-Feb-2011 |
bouyer |
file radixtree.c was added on branch bouyer-quota2 on 2011-03-05 15:08:32 +0000
|
#
1.17.2.6 |
|
22-May-2014 |
yamt |
suppress gcc warnings
|
#
1.17.2.5 |
|
24-Mar-2014 |
yamt |
comments. some ascii arts to explain memory consumption.
|
#
1.17.2.4 |
|
01-Aug-2012 |
yamt |
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.
|
#
1.17.2.3 |
|
13-Jun-2012 |
yamt |
comment
|
#
1.17.2.2 |
|
17-Feb-2012 |
yamt |
comments
|
#
1.17.2.1 |
|
25-Nov-2011 |
yamt |
radix_tree_gang_lookup_node and its variants: add a option to stop on a hole.
|