History log of /freebsd/sys/kern/subr_pctrie.c (Results 26 – 47 of 47)
Revision (<<< Hide revision tags) (Show revision tags >>>) Date Author Comments
# 9cfed089 27-Jun-2023 Doug Moore <dougm@FreeBSD.org>

radix_trie: clean up overlong lines

This is purely a cosmetic change. vm_radix.c has lines that reach past
column 80 and this change cleans that up. The associated changes to
subr_pctrie.c are just

radix_trie: clean up overlong lines

This is purely a cosmetic change. vm_radix.c has lines that reach past
column 80 and this change cleans that up. The associated changes to
subr_pctrie.c are just to keep mirroring vm_radix.c.
Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D40764

show more ...


# 72c3a43b 27-Jun-2023 Doug Moore <dougm@FreeBSD.org>

radix_trie: skip compare in lookup_le, lookup_ge

In _lookup_ge, where a loop "looks for an available edge or val within
the current bisection node" (to quote the code comment), the value of
index ha

radix_trie: skip compare in lookup_le, lookup_ge

In _lookup_ge, where a loop "looks for an available edge or val within
the current bisection node" (to quote the code comment), the value of
index has already been modified to guarantee that it is the least
value than can be found in the non-NULL child node being
examined. Therefore, if the non-NULL child is a leaf, there's no need
to compare 'index' to anything, and the value can just be returned.

The same is true for _lookup_le with 'most' replacing 'least'.
Reviewed by: alc
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D40746

show more ...


# a42d8fe0 25-Jun-2023 Doug Moore <dougm@FreeBSD.org>

radix_trie: simplify trimkey functions

Replacing a branch and two shifts with a single masking operation saves 64 bytes the pair of functions lookup_le and lookup_ge on amd64. Refresh the associate

radix_trie: simplify trimkey functions

Replacing a branch and two shifts with a single masking operation saves 64 bytes the pair of functions lookup_le and lookup_ge on amd64. Refresh the associated comments.
Reviewed by: alc
Differential Revision: https://reviews.freebsd.org/D40722

show more ...


# e8efee29 24-Jun-2023 Doug Moore <dougm@FreeBSD.org>

radix_trie: avoid reloading radix node

In the vm_radix:remove loop that searches for the last child, load
that child once, without loading it again after the search is over.
Change KASSERTS from ind

radix_trie: avoid reloading radix node

In the vm_radix:remove loop that searches for the last child, load
that child once, without loading it again after the search is over.
Change KASSERTS from index check to NULL node check.
Reviewed by: alc
Differential Revision: https://reviews.freebsd.org/D40721

show more ...


# 05963ea4 20-Jun-2023 Doug Moore <dougm@FreeBSD.org>

radix_trie: eliminate iteration in keydiff

Use flsll(), instead of a loop, to find where two keys differ, and
then arithmetic to transform that to a trie level.
Approved by: alc, markj
Differential

radix_trie: eliminate iteration in keydiff

Use flsll(), instead of a loop, to find where two keys differ, and
then arithmetic to transform that to a trie level.
Approved by: alc, markj
Differential Revision: https://reviews.freebsd.org/D40585

show more ...


# 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

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

show more ...


Revision tags: release/13.2.0, release/12.4.0, release/13.1.0, release/12.3.0, release/13.0.0, release/12.2.0
# c7aa572c 31-Jul-2020 Glen Barber <gjb@FreeBSD.org>

MFH

Sponsored by: Rubicon Communications, LLC (netgate.com)


# 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 w

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

show more ...


Revision tags: release/11.4.0, release/12.1.0, release/11.3.0
# 7648bc9f 13-May-2019 Alan Somers <asomers@FreeBSD.org>

MFHead @347527

Sponsored by: The FreeBSD Foundation


# d1139b52 06-Apr-2019 Conrad Meyer <cem@FreeBSD.org>

kern/subr_pctrie: Fix mismatched signedness in assertion comparison

'tos' is an index into an array and never holds a negative value. Correct
its signedness to match PCTRIE_LIMIT, which it is compa

kern/subr_pctrie: Fix mismatched signedness in assertion comparison

'tos' is an index into an array and never holds a negative value. Correct
its signedness to match PCTRIE_LIMIT, which it is compared to in assertions.

No functional change (kills a warning).

show more ...


# 04f9afae 06-Apr-2019 Conrad Meyer <cem@FreeBSD.org>

kern/subr_pctrie: Convert old-style boolean_t to plain "bool"

No functional change.


Revision tags: release/12.0.0, release/11.2.0
# 8a36da99 27-Nov-2017 Pedro F. Giffuni <pfg@FreeBSD.org>

sys/kern: 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

sys/kern: 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.

show more ...


Revision tags: release/10.4.0
# 0275f9db 11-Aug-2017 Hans Petter Selasky <hselasky@FreeBSD.org>

Merge ^/head r321383 through r322397.


# 69ef36e3 01-Aug-2017 Enji Cooper <ngie@FreeBSD.org>

MFhead@r321829


# 0e34ba73 31-Jul-2017 Enji Cooper <ngie@FreeBSD.org>

MFhead@r321755


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

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

show more ...


Revision tags: release/11.1.0, release/11.0.1, release/11.0.0
# 55e0987a 26-Apr-2016 Pedro F. Giffuni <pfg@FreeBSD.org>

sys: extend use of the howmany() macro when available.

We have a howmany() macro in the <sys/param.h> header that is
convenient to re-use as it makes things easier to read.


Revision tags: release/10.3.0, release/10.2.0, release/10.1.0, release/9.3.0, release/10.0.0, release/9.2.0
# d1d01586 05-Sep-2013 Simon J. Gerraty <sjg@FreeBSD.org>

Merge from head


# 40f65a4d 07-Aug-2013 Peter Grehan <grehan@FreeBSD.org>

IFC @ r254014


# 552311f4 17-Jul-2013 Xin LI <delphij@FreeBSD.org>

IFC @253398


# cfe30d02 19-Jun-2013 Gleb Smirnoff <glebius@FreeBSD.org>

Merge fresh head.


Revision tags: release/8.4.0
# f2cc1285 12-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 s

- 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

show more ...


12