summaryrefslogtreecommitdiffhomepage
path: root/net/art
AgeCommit message (Collapse)AuthorFilesLines
2026-01-23all: remove AUTHORS file and references to itWill Norris5-5/+5
This file was never truly necessary and has never actually been used in the history of Tailscale's open source releases. A Brief History of AUTHORS files --- The AUTHORS file was a pattern developed at Google, originally for Chromium, then adopted by Go and a bunch of other projects. The problem was that Chromium originally had a copyright line only recognizing Google as the copyright holder. Because Google (and most open source projects) do not require copyright assignemnt for contributions, each contributor maintains their copyright. Some large corporate contributors then tried to add their own name to the copyright line in the LICENSE file or in file headers. This quickly becomes unwieldy, and puts a tremendous burden on anyone building on top of Chromium, since the license requires that they keep all copyright lines intact. The compromise was to create an AUTHORS file that would list all of the copyright holders. The LICENSE file and source file headers would then include that list by reference, listing the copyright holder as "The Chromium Authors". This also become cumbersome to simply keep the file up to date with a high rate of new contributors. Plus it's not always obvious who the copyright holder is. Sometimes it is the individual making the contribution, but many times it may be their employer. There is no way for the proejct maintainer to know. Eventually, Google changed their policy to no longer recommend trying to keep the AUTHORS file up to date proactively, and instead to only add to it when requested: https://opensource.google/docs/releasing/authors. They are also clear that: > Adding contributors to the AUTHORS file is entirely within the > project's discretion and has no implications for copyright ownership. It was primarily added to appease a small number of large contributors that insisted that they be recognized as copyright holders (which was entirely their right to do). But it's not truly necessary, and not even the most accurate way of identifying contributors and/or copyright holders. In practice, we've never added anyone to our AUTHORS file. It only lists Tailscale, so it's not really serving any purpose. It also causes confusion because Tailscalars put the "Tailscale Inc & AUTHORS" header in other open source repos which don't actually have an AUTHORS file, so it's ambiguous what that means. Instead, we just acknowledge that the contributors to Tailscale (whoever they are) are copyright holders for their individual contributions. We also have the benefit of using the DCO (developercertificate.org) which provides some additional certification of their right to make the contribution. The source file changes were purely mechanical with: git ls-files | xargs sed -i -e 's/\(Tailscale Inc &\) AUTHORS/\1 contributors/g' Updates #cleanup Change-Id: Ia101a4a3005adb9118051b3416f5a64a4a45987d Signed-off-by: Will Norris <will@tailscale.com>
2025-11-18all: rename variables with lowercase-l/uppercase-IAlex Chan2-8/+8
See http://go/no-ell Signed-off-by: Alex Chan <alexc@tailscale.com> Updates #cleanup Change-Id: I8c976b51ce7a60f06315048b1920516129cc1d5d
2024-08-22all: fix new lint warnings from bumping staticcheckBrad Fitzpatrick1-1/+1
In prep for updating to new staticcheck required for Go 1.23. Updates #12912 Change-Id: If77892a023b79c6fa798f936fc80428fd4ce0673 Signed-off-by: Brad Fitzpatrick <bradfitz@tailscale.com>
2024-04-16all: use Go 1.22 range-over-intBrad Fitzpatrick2-19/+19
Updates #11058 Change-Id: I35e7ef9b90e83cac04ca93fd964ad00ed5b48430 Signed-off-by: Brad Fitzpatrick <bradfitz@tailscale.com>
2023-12-21all: cleanup unused code, part 2 (#10670)Andrew Lytvynov3-52/+0
And enable U1000 check in staticcheck. Updates #cleanup Signed-off-by: Andrew Lytvynov <awly@tailscale.com>
2023-08-17net/art: allow non-pointers as valuesDavid Anderson4-220/+246
Values are still turned into pointers internally to maintain the invariants of strideTable, but from the user's perspective it's now possible to tbl.Insert(pfx, true) rather than tbl.Insert(pfx, ptr.To(true)). Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-08-16net/art: move child table pointers out of strideEntryDavid Anderson3-49/+50
In preparation for a different refactor, but incidentally also saves 10-25% memory on overall table size in benchmarks. Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: use more intelligible, go-ish state tracking in table.GetDavid Anderson1-10/+10
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: use encoding/binary for address bit twiddlingDavid Anderson1-4/+3
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: move slice closer to its useDavid Anderson1-3/+2
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: factor out picking the right strideTable for addr familyDavid Anderson1-18/+13
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: make Table.Get alloc-freeDavid Anderson1-2/+14
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: document return value of strideTable.deleteDavid Anderson1-1/+3
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: reword confusing function docstringDavid Anderson1-2/+2
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: use "index", not "idx" in function namesDavid Anderson2-8/+4
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: document valid values of strideTable.prefixDavid Anderson1-2/+5
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: fix comment typoDavid Anderson1-1/+1
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: fix slowPrefixTable bugs found by fuzzingDavid Anderson1-2/+4
One is a straight "I forgot how to Go" bug, the others are semantic mismatches with the main implementation around masking the prefixes passed to insert/delete. Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: add another consistency test for insert/deleteDavid Anderson1-0/+29
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: add more exhaustive table testingDavid Anderson1-12/+705
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: fix format of debug outputDavid Anderson1-1/+1
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: add debug hooks to strideTableDavid Anderson2-4/+17
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: implement path compression optimizationDavid Anderson2-72/+569
Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: make each strideTable track the IP prefix it representsDavid Anderson3-8/+59
This is a prerequisite for path compression, so that insert/delete can determine when compression occurred. Updates #7781 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24net/art: fix running tests outside of CIDavid Anderson1-0/+1
Updates #7866 Signed-off-by: David Anderson <danderson@tailscale.com>
2023-04-14net/art: skip tests on CI for nowBrad Fitzpatrick1-0/+19
To get the tree green again for other people. Updates #7866 Change-Id: Ibdad2e1408e5f0c97e49a148bfd77aad17c2c5e5 Signed-off-by: Brad Fitzpatrick <bradfitz@tailscale.com>
2023-04-13net/art: disable the IPv6 100k routes benchmark.David Anderson1-1/+9
At the current unoptimized memory utilization of the various data structures, 100k IPv6 routes consumes in the ballpark of 3-4GiB, which risks OOMing our 386 test machine. Until we have the optimizations to (drastically) reduce that consumption, skip the test that bloats too much for 32-bit machines. Signed-off-by: David Anderson <danderson@tailscale.com>
2023-04-13net/art: implement the Table type, a multi-level art route table.David Anderson4-6/+708
Updates #7781 │ sec/op │ TableInsertion/ipv4/10 1.562µ ± 2% TableInsertion/ipv4/100 2.398µ ± 5% TableInsertion/ipv4/1000 2.097µ ± 3% TableInsertion/ipv4/10000 2.756µ ± 4% TableInsertion/ipv4/100000 2.473µ ± 13% TableInsertion/ipv6/10 7.649µ ± 2% TableInsertion/ipv6/100 12.09µ ± 3% TableInsertion/ipv6/1000 14.84µ ± 5% TableInsertion/ipv6/10000 14.72µ ± 8% TableInsertion/ipv6/100000 13.23µ ± 41% TableDelete/ipv4/10 378.4n ± 5% TableDelete/ipv4/100 366.9n ± 3% TableDelete/ipv4/1000 418.6n ± 3% TableDelete/ipv4/10000 609.2n ± 11% TableDelete/ipv4/100000 679.2n ± 28% TableDelete/ipv6/10 504.2n ± 4% TableDelete/ipv6/100 959.5n ± 12% TableDelete/ipv6/1000 1.436µ ± 6% TableDelete/ipv6/10000 1.772µ ± 15% TableDelete/ipv6/100000 1.172µ ± 113% TableGet/ipv4/10 32.14n ± 11% TableGet/ipv4/100 38.58n ± 2% TableGet/ipv4/1000 45.03n ± 2% TableGet/ipv4/10000 52.90n ± 7% TableGet/ipv4/100000 135.2n ± 11% TableGet/ipv6/10 41.55n ± 1% TableGet/ipv6/100 44.78n ± 2% TableGet/ipv6/1000 49.03n ± 2% TableGet/ipv6/10000 65.38n ± 5% TableGet/ipv6/100000 525.0n ± 39% │ avg-B/op │ TableInsertion/ipv4/10 25.18Ki ± 0% TableInsertion/ipv4/100 17.63Ki ± 0% TableInsertion/ipv4/1000 14.14Ki ± 0% TableInsertion/ipv4/10000 12.92Ki ± 0% TableInsertion/ipv4/100000 11.13Ki ± 0% TableInsertion/ipv6/10 76.87Ki ± 0% TableInsertion/ipv6/100 98.33Ki ± 0% TableInsertion/ipv6/1000 91.44Ki ± 0% TableInsertion/ipv6/10000 90.39Ki ± 0% TableInsertion/ipv6/100000 87.19Ki ± 0% TableDelete/ipv4/10 3.230 ± 0% TableDelete/ipv4/100 4.020 ± 0% TableDelete/ipv4/1000 3.990 ± 0% TableDelete/ipv4/10000 4.000 ± 0% TableDelete/ipv4/100000 4.000 ± 0% TableDelete/ipv6/10 16.00 ± 0% TableDelete/ipv6/100 16.00 ± 0% TableDelete/ipv6/1000 16.00 ± 0% TableDelete/ipv6/10000 16.00 ± 0% TableDelete/ipv6/100000 16.00 ± 0% │ avg-allocs/op │ TableInsertion/ipv4/10 2.900 ± 0% TableInsertion/ipv4/100 2.330 ± 0% TableInsertion/ipv4/1000 2.070 ± 0% TableInsertion/ipv4/10000 1.980 ± 0% TableInsertion/ipv4/100000 1.840 ± 0% TableInsertion/ipv6/10 6.800 ± 0% TableInsertion/ipv6/100 8.420 ± 0% TableInsertion/ipv6/1000 7.900 ± 0% TableInsertion/ipv6/10000 7.820 ± 0% TableInsertion/ipv6/100000 7.580 ± 0% TableDelete/ipv4/10 1.000 ± 0% TableDelete/ipv4/100 1.000 ± 0% TableDelete/ipv4/1000 1.000 ± 0% TableDelete/ipv4/10000 1.000 ± 0% TableDelete/ipv4/100000 1.000 ± 0% TableDelete/ipv6/10 1.000 ± 0% TableDelete/ipv6/100 1.000 ± 0% TableDelete/ipv6/1000 1.000 ± 0% TableDelete/ipv6/10000 1.000 ± 0% TableDelete/ipv6/100000 1.000 ± 0% │ routes/s │ TableInsertion/ipv4/10 640.3k ± 2% TableInsertion/ipv4/100 417.1k ± 5% TableInsertion/ipv4/1000 477.0k ± 3% TableInsertion/ipv4/10000 362.8k ± 5% TableInsertion/ipv4/100000 404.5k ± 15% TableInsertion/ipv6/10 130.7k ± 1% TableInsertion/ipv6/100 82.69k ± 3% TableInsertion/ipv6/1000 67.37k ± 5% TableInsertion/ipv6/10000 67.93k ± 9% TableInsertion/ipv6/100000 75.63k ± 29% TableDelete/ipv4/10 2.642M ± 6% TableDelete/ipv4/100 2.726M ± 3% TableDelete/ipv4/1000 2.389M ± 3% TableDelete/ipv4/10000 1.641M ± 12% TableDelete/ipv4/100000 1.472M ± 27% TableDelete/ipv6/10 1.984M ± 4% TableDelete/ipv6/100 1.042M ± 11% TableDelete/ipv6/1000 696.5k ± 6% TableDelete/ipv6/10000 564.4k ± 13% TableDelete/ipv6/100000 853.6k ± 53% │ addrs/s │ TableGet/ipv4/10 31.11M ± 10% TableGet/ipv4/100 25.92M ± 2% TableGet/ipv4/1000 22.21M ± 2% TableGet/ipv4/10000 18.91M ± 8% TableGet/ipv4/100000 7.397M ± 12% TableGet/ipv6/10 24.07M ± 1% TableGet/ipv6/100 22.33M ± 2% TableGet/ipv6/1000 20.40M ± 2% TableGet/ipv6/10000 15.30M ± 5% TableGet/ipv6/100000 1.905M ± 28% │ B/op │ TableGet/ipv4/10 4.000 ± 0% TableGet/ipv4/100 4.000 ± 0% TableGet/ipv4/1000 4.000 ± 0% TableGet/ipv4/10000 4.000 ± 0% TableGet/ipv4/100000 4.000 ± 0% TableGet/ipv6/10 16.00 ± 0% TableGet/ipv6/100 16.00 ± 0% TableGet/ipv6/1000 16.00 ± 0% TableGet/ipv6/10000 16.00 ± 0% TableGet/ipv6/100000 16.00 ± 0% │ allocs/op │ TableGet/ipv4/10 1.000 ± 0% TableGet/ipv4/100 1.000 ± 0% TableGet/ipv4/1000 1.000 ± 0% TableGet/ipv4/10000 1.000 ± 0% TableGet/ipv4/100000 1.000 ± 0% TableGet/ipv6/10 1.000 ± 0% TableGet/ipv6/100 1.000 ± 0% TableGet/ipv6/1000 1.000 ± 0% TableGet/ipv6/10000 1.000 ± 0% TableGet/ipv6/100000 1.000 ± 0% Signed-off-by: David Anderson <danderson@tailscale.com>
2023-04-04net/art: implement the stride table building block of ARTDavid Anderson3-0/+617
A stride table is an 8-bit routing table implemented as an array binary tree, with a special tree updating function (allot) that enables lightning fast address lookups and reasonably fast insertion and deletion. Insertion, deletion and lookup are all allocation-free. Updates #7781 │ sec/op │ StrideTableInsertion/10/random_order 16.79n ± 2% StrideTableInsertion/10/largest_first 16.83n ± 1% StrideTableInsertion/10/smallest_first 16.83n ± 0% StrideTableInsertion/50/random_order 17.84n ± 1% StrideTableInsertion/50/largest_first 20.04n ± 1% StrideTableInsertion/50/smallest_first 16.39n ± 0% StrideTableInsertion/100/random_order 14.63n ± 0% StrideTableInsertion/100/largest_first 17.45n ± 4% StrideTableInsertion/100/smallest_first 12.98n ± 0% StrideTableInsertion/200/random_order 12.51n ± 4% StrideTableInsertion/200/largest_first 18.36n ± 3% StrideTableInsertion/200/smallest_first 9.609n ± 3% StrideTableDeletion/10/random_order 19.50n ± 1% StrideTableDeletion/10/largest_first 19.34n ± 0% StrideTableDeletion/10/smallest_first 19.43n ± 0% StrideTableDeletion/50/random_order 14.58n ± 1% StrideTableDeletion/50/largest_first 14.27n ± 2% StrideTableDeletion/50/smallest_first 15.51n ± 0% StrideTableDeletion/100/random_order 12.02n ± 3% StrideTableDeletion/100/largest_first 10.64n ± 0% StrideTableDeletion/100/smallest_first 13.21n ± 3% StrideTableDeletion/200/random_order 14.05n ± 4% StrideTableDeletion/200/largest_first 9.288n ± 5% StrideTableDeletion/200/smallest_first 18.51n ± 1% StrideTableGet 0.5010n ± 0% │ routes/s │ StrideTableInsertion/10/random_order 59.55M ± 2% StrideTableInsertion/10/largest_first 59.42M ± 1% StrideTableInsertion/10/smallest_first 59.43M ± 0% StrideTableInsertion/50/random_order 56.04M ± 1% StrideTableInsertion/50/largest_first 49.91M ± 1% StrideTableInsertion/50/smallest_first 61.00M ± 0% StrideTableInsertion/100/random_order 68.35M ± 0% StrideTableInsertion/100/largest_first 57.32M ± 3% StrideTableInsertion/100/smallest_first 77.06M ± 0% StrideTableInsertion/200/random_order 79.93M ± 4% StrideTableInsertion/200/largest_first 54.47M ± 3% StrideTableInsertion/200/smallest_first 104.1M ± 3% StrideTableDeletion/10/random_order 51.28M ± 1% StrideTableDeletion/10/largest_first 51.70M ± 0% StrideTableDeletion/10/smallest_first 51.48M ± 0% StrideTableDeletion/50/random_order 68.60M ± 1% StrideTableDeletion/50/largest_first 70.09M ± 2% StrideTableDeletion/50/smallest_first 64.45M ± 0% StrideTableDeletion/100/random_order 83.21M ± 3% StrideTableDeletion/100/largest_first 94.03M ± 0% StrideTableDeletion/100/smallest_first 75.69M ± 3% StrideTableDeletion/200/random_order 71.20M ± 5% StrideTableDeletion/200/largest_first 107.7M ± 5% StrideTableDeletion/200/smallest_first 54.02M ± 1% StrideTableGet 1.996G ± 0% Signed-off-by: David Anderson <danderson@tailscale.com>
Copyright © 2025 - 2026 Wayne Cole. WTFPL. Attribution appreciated. No warranty. Not liable for bodily damages.