| History log of /src/sys/kern/subr_thmap.c |
| Revision | | Date | Author | Comments |
| 1.15 |
| 17-Oct-2023 |
riastradh | thmap(9): Preallocate GC list storage for thmap_del.
thmap_del can't fail, and it is used in places in npf where sleeping
is forbidden, so it can't rely on allocating memory either.
Instead of having thmap_del allocate memory on the fly for each
object to defer freeing until thmap_gc, arrange to have thmap(9)
preallocate the same storage when allocating all the objects in the
first place, with a GC header.
This is suboptimal for memory usage, especially on insertion- and
lookup-heavy but deletion-light workloads, but it's not clear rmind's
alternative (https://github.com/rmind/thmap/tree/thmap_del_mem_fail)
is ready to use yet, so we'll go with this for correctness.
PR kern/57208
https://github.com/rmind/npf/issues/129
XXX pullup-10
XXX pullup-9
|
| 1.14 |
| 17-Oct-2023 |
riastradh | thmap(9): Test alloc failure, not THMAP_GETPTR failure.
THMAP_GETPTR may return nonnull even though alloc returned zero.
Note that this failure branch is not actually appropriate;
thmap_create should not fail. We really need to pass KM_SLEEP
through in this call site even though there are other call sites for
which KM_NOSLEEP is appropriate.
Adapted from: https://github.com/rmind/thmap/pull/14
PR kern/57666
https://github.com/rmind/thmap/issues/13
XXX pullup-10
XXX pullup-9
|
| 1.13 |
| 11-Apr-2023 |
riastradh | thmap(9): kmem_zalloc(KM_SLEEP) never fails. Prune dead branch.
|
| 1.12 |
| 09-Apr-2022 |
riastradh | branches: 1.12.4;
thmap(9): Convert membar_exit to membar_release.
|
| 1.11 |
| 01-Apr-2022 |
riastradh | thmap(9): Handle memory allocation failure in root_try_put.
Reported-by: syzbot+8ded6e17a394e39d6291@syzkaller.appspotmail.com
|
| 1.10 |
| 13-Feb-2022 |
riastradh | thmap(9): Omit needless fences and use membar_exit for release fence.
It is the caller's responsibility to arrange that thmap_create, and,
if THMAP_SETROOT is set, thmap_root, happen before any use of the
thmap. No need for them to issue fences internally.
|
| 1.9 |
| 08-Feb-2022 |
riastradh | kern: Mark some functions __diagused to pacify clang.
These functions are called only in KASSERT. This shouldn't be a
problem since the recent change to make KASSERT compile (but not run)
the expression, via sizeof, so the functions are referenced -- which
I did in order to avoid having #ifdefs and regular build breakage
because someone forgot to build with or without DIAGNOSTIC. But
apparently clang decided to make it a problem.
Maybe we should just set -Wno-unneeded-internal-declaration -- not
clear it flags any real problems, but it takes effort to research
because apparently clang has no documentation about what else it does
or why anyone decided this is objectionable enough to turn it on by
default. (The only documentation it seems to have, two example
warning messages with no elaboration at
<https://releases.llvm.org/13.0.0/tools/clang/docs/DiagnosticsReference.html#wunneeded-internal-declaration>,
seems to indicate it is mixed up with warning about static non-inline
functions in header files.)
|
| 1.8 |
| 31-Dec-2021 |
riastradh | libkern: Make KASSERT verify expression is valid if !DIAGNOSTIC.
This way it is no longer necessary to mark variables __diagused if
they are used in KASSERT conditions.
Fix fallout from this by removing now-unnecessary and `#ifdef
DIAGNOSTIC'.
Don't do the same for KDASSERT if !DEBUG -- unlike KASSERT and
DIAGNOSTIC, variables needed by KDASSERT and DEBUG are likely to be
expensive to compute (and potentially difficult for a compiler to
prove flushable), so we don't want to require them under !DEBUG.
|
| 1.7 |
| 31-Aug-2020 |
riastradh | thmap: Use keyed BLAKE2s for second-level hash and beyond.
This thwarts hash-flooding, but pays the cost only for those keys
that collide under the cheaper murmurhash2.
|
| 1.6 |
| 23-May-2020 |
rmind | thmap(9): merge changes from the upstream -- primarily, switch to the
C11-style memory fences and atomic primitives; in NetBSD, this translates
to using the atomic_loadstore(9) primitives.
To be pulled up (just in case).
|
| 1.5 |
| 04-Feb-2019 |
mrg | branches: 1.5.4; 1.5.6;
pass a pointer to atomic_cas_ptr_p(), not an (equiv) integer.
|
| 1.4 |
| 19-Jan-2019 |
rmind | thmap: use KM_NOSLEEP for now; might revisit later.
|
| 1.3 |
| 22-Dec-2018 |
christos | branches: 1.3.2;
add missing quotes 7
|
| 1.2 |
| 22-Dec-2018 |
christos | - add rcsid
- don't define DEBUG
- protect function used in KASSERT with DIAGNOSTIC not DEBUG
|
| 1.1 |
| 16-Dec-2018 |
rmind | Import thmap -- a concurrent trie-hash map, combining the elements of
hashing and radix trie. It supports lock-free lookups and concurrent
inserts/deletes. It is designed to be optimal as a general purpose
*concurrent* associative array.
Upstream: https://github.com/rmind/thmap
Discussed on tech-kern@
|
| 1.3.2.3 |
| 26-Jan-2019 |
pgoyette | Sync with HEAD
|
| 1.3.2.2 |
| 26-Dec-2018 |
pgoyette | Sync with HEAD, resolve a few conflicts
|
| 1.3.2.1 |
| 22-Dec-2018 |
pgoyette | file subr_thmap.c was added on branch pgoyette-compat on 2018-12-26 14:02:04 +0000
|
| 1.5.6.2 |
| 18-Oct-2023 |
martin | Pull up following revision(s) (requested by riastradh in ticket #1755):
sys/kern/subr_thmap.c: revision 1.14
sys/kern/subr_thmap.c: revision 1.15
thmap(9): Test alloc failure, not THMAP_GETPTR failure.
THMAP_GETPTR may return nonnull even though alloc returned zero.
Note that this failure branch is not actually appropriate;
thmap_create should not fail. We really need to pass KM_SLEEP
through in this call site even though there are other call sites for
which KM_NOSLEEP is appropriate.
Adapted from: https://github.com/rmind/thmap/pull/14
PR kern/57666
https://github.com/rmind/thmap/issues/13
thmap(9): Preallocate GC list storage for thmap_del.
thmap_del can't fail, and it is used in places in npf where sleeping
is forbidden, so it can't rely on allocating memory either.
Instead of having thmap_del allocate memory on the fly for each
object to defer freeing until thmap_gc, arrange to have thmap(9)
preallocate the same storage when allocating all the objects in the
first place, with a GC header.
This is suboptimal for memory usage, especially on insertion- and
lookup-heavy but deletion-light workloads, but it's not clear rmind's
alternative (https://github.com/rmind/thmap/tree/thmap_del_mem_fail)
is ready to use yet, so we'll go with this for correctness.
PR kern/57208
https://github.com/rmind/npf/issues/129
|
| 1.5.6.1 |
| 25-May-2020 |
martin | Pull up following revision(s) (requested by rmind in ticket #929):
sys/kern/subr_thmap.c: revision 1.6
thmap(9): merge changes from the upstream -- primarily, switch to the
C11-style memory fences and atomic primitives; in NetBSD, this translates
to using the atomic_loadstore(9) primitives.
To be pulled up (just in case).
|
| 1.5.4.2 |
| 10-Jun-2019 |
christos | Sync with HEAD
|
| 1.5.4.1 |
| 04-Feb-2019 |
christos | file subr_thmap.c was added on branch phil-wifi on 2019-06-10 22:09:03 +0000
|
| 1.12.4.1 |
| 18-Oct-2023 |
martin | Pull up following revision(s) (requested by riastradh in ticket #423):
sys/kern/subr_thmap.c: revision 1.14
sys/kern/subr_thmap.c: revision 1.15
thmap(9): Test alloc failure, not THMAP_GETPTR failure.
THMAP_GETPTR may return nonnull even though alloc returned zero.
Note that this failure branch is not actually appropriate;
thmap_create should not fail. We really need to pass KM_SLEEP
through in this call site even though there are other call sites for
which KM_NOSLEEP is appropriate.
Adapted from: https://github.com/rmind/thmap/pull/14
PR kern/57666
https://github.com/rmind/thmap/issues/13
thmap(9): Preallocate GC list storage for thmap_del.
thmap_del can't fail, and it is used in places in npf where sleeping
is forbidden, so it can't rely on allocating memory either.
Instead of having thmap_del allocate memory on the fly for each
object to defer freeing until thmap_gc, arrange to have thmap(9)
preallocate the same storage when allocating all the objects in the
first place, with a GC header.
This is suboptimal for memory usage, especially on insertion- and
lookup-heavy but deletion-light workloads, but it's not clear rmind's
alternative (https://github.com/rmind/thmap/tree/thmap_del_mem_fail)
is ready to use yet, so we'll go with this for correctness.
PR kern/57208
https://github.com/rmind/npf/issues/129
|
