#
2a21cfe6 |
|
14-Jun-2024 |
Doug Moore <dougm@FreeBSD.org> |
pctrie: avoid typecast Have PCTRIE_RECLAIM_CALLBACK typecast one function pointer type to another, to relieve the writer of the call back function from having to cast its first argument from void* to member type. Reviewed by: rlibby Differential Revision: https://reviews.freebsd.org/D45586
|
#
c0d0bc2b |
|
13-Jun-2024 |
Doug Moore <dougm@FreeBSD.org> |
subr_pctrie: add leaf callbacks to pctrie_reclaim PCTRIE_RECLAIM frees all the interior nodes in a pctrie, but is little used because most trie-destroyers want to free leaves of the tree too. Add PCTRIE_RECLAIM_CALLBACK, with two extra arguments, a callback function and an auxiliary argument, that is invoked on every non-NULL leaf in the tree as the tree is destroyed. Reviewed by: rlibby, kib (previous version) Differential Revision: https://reviews.freebsd.org/D45565
|
#
bbf81f46 |
|
05-Jun-2024 |
Ryan Libby <rlibby@FreeBSD.org> |
pctrie: add combined insert/lookup operations In several places in code, we do a pctrie lookup followed by a pctrie insert. Provide a few flavors of combined lookup/insert. This may save a portion of the work from walking a large pctrie twice. The general idea is that while we walk the trie during insert, we also do the same kind of tracking work that we do during pctrie_lookup_ge or pctrie_lookup_le, and we pass out a pctrie node from where such a lookup may continue. Reviewed by: dougm (previous version), kib (previous version), markj Sponsored by: Dell EMC Isilon Differential Revision: https://reviews.freebsd.org/D45394
|
#
7f1012ff |
|
03-Jun-2024 |
Ryan Libby <rlibby@FreeBSD.org> |
pctrie: predict successful allocation Reviewed by: dougm Sponsored by: Dell EMC Isilon Differential Revision: https://reviews.freebsd.org/D45407
|
#
3b7ffacd |
|
20-Aug-2023 |
Doug Moore <dougm@FreeBSD.org> |
pctrie: change for vm_radix compatibility Restructure parts of pctrie code to make it more compatible with the needs of vm_radix code. 1. End passing function pointers for memory management. By breaking insertion into two functions, the call for allocating memory can happen at the top level and be inlined, rather than happening via an function pointer to a memory allocator. By changing the remove function slightly, freeing of memory, when necessary, can happen at the top level and be inlined. By turning the reclamation code into two functions, one for starting iteration over to-be-freed nodes and the other continuing it, all the freeing can happen at the top level and be inlined. 2. Offer a version of remove that does not panic and returns the freed value (or NULL). 3. Offer a 'replace' operation, to replace one leaf with another that has the same key. These are three of the roadblocks that prevent code sharing between pctrie and vm_radix code. Reviewed by: kib (previous version) Differential Revision: https://reviews.freebsd.org/D41396
|
#
95ee2897 |
|
16-Aug-2023 |
Warner Losh <imp@FreeBSD.org> |
sys: Remove $FreeBSD$: two-line .h pattern Remove /^\s*\*\n \*\s+\$FreeBSD\$$\n/
|
#
15047a65 |
|
09-Aug-2023 |
Doug Moore <dougm@FreeBSD.org> |
rangesets: use PCTRIE_DEFINE subr_rangeset.c is the only source file that calls functions like pctrie_insert and pctrie_remove directly; other users of pctries use the PCTRIE_DEFINE macro to define interfaces to pctrie that let them ignore issues of offsets within structs and uint64_t return values. Change subr_rangeset.c to use PCTRIE_DEFINE too. And change pctrie.h to mark the lookup function as unused, to avoid warnings when compiling files, like subr_rangeset.c, that don't invoke lookup(). Reviewed by: kib Differential Revision: https://reviews.freebsd.org/D41391
|
#
2d2bcba7 |
|
28-Jul-2023 |
Doug Moore <dougm@FreeBSD.org> |
Every path in a radix trie ends with a leaf or a NULL. By replacing NULL (non-leaf) pointers with NULL leaves, there is a NULL test removed from every iteration of an index-based search loop. This speeds up radix trie searches by few percent. If there are any radix tries that are not initialized with the init() function, but instead depend on zeroing everything being proper initialization, this will break those tries. Reviewed by: alc, kib Tested by: pho (as part of a larger change) Differential Revision: https://reviews.freebsd.org/D41171
|
#
4d846d26 |
|
10-May-2023 |
Warner Losh <imp@FreeBSD.org> |
spdx: The BSD-2-Clause-FreeBSD identifier is obsolete, drop -FreeBSD The SPDX folks have obsoleted the BSD-2-Clause-FreeBSD identifier. Catch up to that fact and revert to their recommended match of BSD-2-Clause. Discussed with: pfg MFC After: 3 days Sponsored by: Netflix
|
#
3c30b235 |
|
24-Jul-2020 |
Conrad Meyer <cem@FreeBSD.org> |
Use SMR to provide safe unlocked lookup for pctries from SMR zones Adapt r358130, for the almost identical vm_radix, to the pctrie subsystem. Like that change, the tree is kept correct for readers with store barriers and careful ordering. Existing locks serialize writers. Add a PCTRIE_DEFINE_SMR() wrapper that takes an additional smr_t parameter and instantiates a FOO_PCTRIE_LOOKUP_UNLOCKED() function, in addition to the usual definitions created by PCTRIE_DEFINE(). Interface consumers will be introduced in later commits. As future work, it might be nice to add vm_radix algorithms missing from generic pctrie to the pctrie interface, and then adapt vm_radix to use pctrie. Reported by: Attilio Reviewed by: markj Sponsored by: Isilon Differential Revision: https://reviews.freebsd.org/D25781
|
#
04f9afae |
|
06-Apr-2019 |
Conrad Meyer <cem@FreeBSD.org> |
kern/subr_pctrie: Convert old-style boolean_t to plain "bool" No functional change.
|
#
c4e20cad |
|
27-Nov-2017 |
Pedro F. Giffuni <pfg@FreeBSD.org> |
sys/sys: further adoption of SPDX licensing ID tags. Mainly focus on files that use BSD 2-Clause license, however the tool I was using misidentified many licenses so this was mostly a manual - error prone - task. The Software Package Data Exchange (SPDX) group provides a specification to make it easier for automated tools to detect and summarize well known opensource licenses. We are gradually adopting the specification, noting that the tags are considered only advisory and do not, in any way, superceed or replace the license texts.
|
#
0948519d |
|
27-Jul-2017 |
Konstantin Belousov <kib@FreeBSD.org> |
Make the number of children for pctrie node available outside subr_pctrie.c. Reviewed by: alc, markj Sponsored by: The FreeBSD Foundation MFC after: 1 week X-Differential revision: https://reviews.freebsd.org/D11435
|
#
bc557042 |
|
26-Jul-2017 |
Konstantin Belousov <kib@FreeBSD.org> |
Mark name_PCTRIE_LOOKUP_LE() generated function unused. The PCTRIE macro will be shortly applied in a situation where LOOKUP_LE is not needed. Reviewed by: alc, markj Sponsored by: The FreeBSD Foundation MFC after: 1 week X-Differential revision: https://reviews.freebsd.org/D11435
|
#
cd1241fb |
|
19-Jul-2017 |
Konstantin Belousov <kib@FreeBSD.org> |
Add pctrie_init() and vm_radix_init() to initialize generic pctrie and vm_radix trie. Existing vm_radix_init() function is renamed to vm_radix_zinit(). Inlines moved out of the _ headers. Reviewed by: alc, markj (previous version) Sponsored by: The FreeBSD Foundation MFC after: 1 week Differential revision: https://reviews.freebsd.org/D11661
|
#
c321b45e |
|
28-Dec-2013 |
Dimitry Andric <dim@FreeBSD.org> |
Mark unused static inline functions defined by the PCTRIE_DEFINE() macro as __unused, so warnings about them are avoided. MFC after: 3 days
|
#
3825b112 |
|
12-May-2013 |
Jeff Roberson <jeff@FreeBSD.org> |
- pctrie really only requires two byte alignment so that there is a single bit available for a flag in the pointer. However, it felt more correct to enforce natural alignment of the key pointer. Unfortunately on 32bit architectures 64bit integers are not always naturally aligned. Change the assert to enforce only 32bit alignment of the 64bit key for now to fix the build. A more correct fix would be to properly sort the struct buf fields which definitely suffer from bloat due to padding.
|
#
f2cc1285 |
|
11-May-2013 |
Jeff Roberson <jeff@FreeBSD.org> |
- Add a new general purpose path-compressed radix trie which can be used with any structure containing a uint64_t index. The tree code auto-generates type safe wrappers. - Eliminate the buf splay and replace it with pctrie. This is not only significantly faster with large files but also allows for the possibility of shared locking. Reviewed by: alc, attilio Sponsored by: EMC / Isilon Storage Division
|