The NetBSD Project

CVS log for src/sys/kern/subr_thmap.c

[BACK] Up to [cvs.NetBSD.org] / src / sys / kern

Request diff between arbitrary revisions


Default branch: MAIN


Revision 1.5.6.2 / (download) - annotate - [select for diffs], Wed Oct 18 15:07:06 2023 UTC (4 months, 1 week ago) by martin
Branch: netbsd-9
Changes since 1.5.6.1: +57 -22 lines
Diff to previous 1.5.6.1 (colored) to branchpoint 1.5 (colored) next main 1.6 (colored)

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

Revision 1.12.4.1 / (download) - annotate - [select for diffs], Wed Oct 18 15:03:12 2023 UTC (4 months, 1 week ago) by martin
Branch: netbsd-10
CVS Tags: netbsd-10-0-RC4, netbsd-10-0-RC3, netbsd-10-0-RC2, netbsd-10-0-RC1
Changes since 1.12: +57 -22 lines
Diff to previous 1.12 (colored) next main 1.13 (colored)

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

Revision 1.15 / (download) - annotate - [select for diffs], Tue Oct 17 11:57:20 2023 UTC (4 months, 1 week ago) by riastradh
Branch: MAIN
CVS Tags: thorpej-ifq-base, thorpej-ifq, thorpej-altq-separation-base, thorpej-altq-separation, HEAD
Changes since 1.14: +55 -20 lines
Diff to previous 1.14 (colored)

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

Revision 1.14 / (download) - annotate - [select for diffs], Tue Oct 17 11:55:28 2023 UTC (4 months, 1 week ago) by riastradh
Branch: MAIN
Changes since 1.13: +4 -4 lines
Diff to previous 1.13 (colored)

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

Revision 1.13 / (download) - annotate - [select for diffs], Tue Apr 11 13:06:21 2023 UTC (10 months, 2 weeks ago) by riastradh
Branch: MAIN
Changes since 1.12: +2 -5 lines
Diff to previous 1.12 (colored)

thmap(9): kmem_zalloc(KM_SLEEP) never fails.  Prune dead branch.

Revision 1.12 / (download) - annotate - [select for diffs], Sat Apr 9 23:51:57 2022 UTC (22 months, 2 weeks ago) by riastradh
Branch: MAIN
CVS Tags: netbsd-10-base, bouyer-sunxi-drm-base, bouyer-sunxi-drm
Branch point for: netbsd-10
Changes since 1.11: +3 -3 lines
Diff to previous 1.11 (colored)

thmap(9): Convert membar_exit to membar_release.

Revision 1.11 / (download) - annotate - [select for diffs], Fri Apr 1 00:16:40 2022 UTC (22 months, 3 weeks ago) by riastradh
Branch: MAIN
Changes since 1.10: +17 -7 lines
Diff to previous 1.10 (colored)

thmap(9): Handle memory allocation failure in root_try_put.

Reported-by: syzbot+8ded6e17a394e39d6291@syzkaller.appspotmail.com

Revision 1.10 / (download) - annotate - [select for diffs], Sun Feb 13 19:20:33 2022 UTC (2 years ago) by riastradh
Branch: MAIN
Changes since 1.9: +3 -5 lines
Diff to previous 1.9 (colored)

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.

Revision 1.9 / (download) - annotate - [select for diffs], Tue Feb 8 12:59:16 2022 UTC (2 years ago) by riastradh
Branch: MAIN
Changes since 1.8: +3 -3 lines
Diff to previous 1.8 (colored)

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

Revision 1.8 / (download) - annotate - [select for diffs], Fri Dec 31 14:19:57 2021 UTC (2 years, 1 month ago) by riastradh
Branch: MAIN
Changes since 1.7: +2 -4 lines
Diff to previous 1.7 (colored)

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.

Revision 1.7 / (download) - annotate - [select for diffs], Mon Aug 31 20:22:57 2020 UTC (3 years, 5 months ago) by riastradh
Branch: MAIN
CVS Tags: thorpej-i2c-spi-conf2-base, thorpej-i2c-spi-conf2, thorpej-i2c-spi-conf-base, thorpej-i2c-spi-conf, thorpej-futex2-base, thorpej-futex2, thorpej-futex-base, thorpej-futex, thorpej-cfargs2-base, thorpej-cfargs2, thorpej-cfargs-base, thorpej-cfargs, cjep_sun2x-base1, cjep_sun2x-base, cjep_sun2x, cjep_staticlib_x-base1, cjep_staticlib_x-base, cjep_staticlib_x
Changes since 1.6: +48 -9 lines
Diff to previous 1.6 (colored)

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.

Revision 1.5.6.1 / (download) - annotate - [select for diffs], Mon May 25 17:19:37 2020 UTC (3 years, 9 months ago) by martin
Branch: netbsd-9
CVS Tags: netbsd-9-3-RELEASE, netbsd-9-2-RELEASE, netbsd-9-1-RELEASE
Changes since 1.5: +138 -88 lines
Diff to previous 1.5 (colored)

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

Revision 1.6 / (download) - annotate - [select for diffs], Sat May 23 19:52:12 2020 UTC (3 years, 9 months ago) by rmind
Branch: MAIN
Changes since 1.5: +138 -88 lines
Diff to previous 1.5 (colored)

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

Revision 1.5.4.2 / (download) - annotate - [select for diffs], Mon Jun 10 22:09:03 2019 UTC (4 years, 8 months ago) by christos
Branch: phil-wifi
Changes since 1.5.4.1: +940 -0 lines
Diff to previous 1.5.4.1 (colored) to branchpoint 1.5 (colored) next main 1.6 (colored)

Sync with HEAD

Revision 1.5.4.1, Mon Feb 4 08:00:27 2019 UTC (5 years ago) by christos
Branch: phil-wifi
Changes since 1.5: +0 -940 lines
FILE REMOVED

file subr_thmap.c was added on branch phil-wifi on 2019-06-10 22:09:03 +0000

Revision 1.5 / (download) - annotate - [select for diffs], Mon Feb 4 08:00:27 2019 UTC (5 years ago) by mrg
Branch: MAIN
CVS Tags: phil-wifi-20200421, phil-wifi-20200411, phil-wifi-20200406, phil-wifi-20191119, phil-wifi-20190609, netbsd-9-base, netbsd-9-0-RELEASE, netbsd-9-0-RC2, netbsd-9-0-RC1, isaki-audio2-base, isaki-audio2, is-mlppp-base, is-mlppp, bouyer-xenpvh-base2, bouyer-xenpvh-base1, bouyer-xenpvh-base, bouyer-xenpvh, ad-namecache-base3, ad-namecache-base2, ad-namecache-base1, ad-namecache-base, ad-namecache
Branch point for: phil-wifi, netbsd-9
Changes since 1.4: +3 -3 lines
Diff to previous 1.4 (colored)

pass a pointer to atomic_cas_ptr_p(), not an (equiv) integer.

Revision 1.3.2.3 / (download) - annotate - [select for diffs], Sat Jan 26 22:00:36 2019 UTC (5 years, 1 month ago) by pgoyette
Branch: pgoyette-compat
CVS Tags: pgoyette-compat-merge-20190127
Changes since 1.3.2.2: +4 -4 lines
Diff to previous 1.3.2.2 (colored) to branchpoint 1.3 (colored) next main 1.4 (colored)

Sync with HEAD

Revision 1.4 / (download) - annotate - [select for diffs], Sat Jan 19 20:42:54 2019 UTC (5 years, 1 month ago) by rmind
Branch: MAIN
CVS Tags: pgoyette-compat-20190127
Changes since 1.3: +4 -4 lines
Diff to previous 1.3 (colored)

thmap: use KM_NOSLEEP for now; might revisit later.

Revision 1.3.2.2 / (download) - annotate - [select for diffs], Wed Dec 26 14:02:04 2018 UTC (5 years, 2 months ago) by pgoyette
Branch: pgoyette-compat
Changes since 1.3.2.1: +940 -0 lines
Diff to previous 1.3.2.1 (colored) to branchpoint 1.3 (colored)

Sync with HEAD, resolve a few conflicts

Revision 1.3.2.1, Sat Dec 22 21:53:06 2018 UTC (5 years, 2 months ago) by pgoyette
Branch: pgoyette-compat
Changes since 1.3: +0 -940 lines
FILE REMOVED

file subr_thmap.c was added on branch pgoyette-compat on 2018-12-26 14:02:04 +0000

Revision 1.3 / (download) - annotate - [select for diffs], Sat Dec 22 21:53:06 2018 UTC (5 years, 2 months ago) by christos
Branch: MAIN
CVS Tags: pgoyette-compat-20190118, pgoyette-compat-1226
Branch point for: pgoyette-compat
Changes since 1.2: +2 -2 lines
Diff to previous 1.2 (colored)

add missing quotes 7

Revision 1.2 / (download) - annotate - [select for diffs], Sat Dec 22 20:49:04 2018 UTC (5 years, 2 months ago) by christos
Branch: MAIN
Changes since 1.1: +8 -2 lines
Diff to previous 1.1 (colored)

- add rcsid
- don't define DEBUG
- protect function used in KASSERT with DIAGNOSTIC not DEBUG

Revision 1.1 / (download) - annotate - [select for diffs], Sun Dec 16 14:06:56 2018 UTC (5 years, 2 months ago) by rmind
Branch: MAIN

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@

This form allows you to request diff's between any two revisions of a file. You may select a symbolic revision name using the selection box or you may type in a numeric name using the type-in text box.




CVSweb <webmaster@jp.NetBSD.org>