9 Commits

Author SHA1 Message Date
Will Norris
3ec5be3f51 all: remove AUTHORS file and references to it
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>
2026-01-23 15:49:45 -08:00
Alex Chan
c2e474e729 all: rename variables with lowercase-l/uppercase-I
See http://go/no-ell

Signed-off-by: Alex Chan <alexc@tailscale.com>

Updates #cleanup

Change-Id: I8c976b51ce7a60f06315048b1920516129cc1d5d
2025-11-18 09:12:34 +00:00
Brad Fitzpatrick
7c1d6e35a5 all: use Go 1.22 range-over-int
Updates #11058

Change-Id: I35e7ef9b90e83cac04ca93fd964ad00ed5b48430
Signed-off-by: Brad Fitzpatrick <bradfitz@tailscale.com>
2024-04-16 15:32:38 -07:00
Andrew Lytvynov
2716250ee8
all: cleanup unused code, part 2 (#10670)
And enable U1000 check in staticcheck.

Updates #cleanup

Signed-off-by: Andrew Lytvynov <awly@tailscale.com>
2023-12-21 17:40:03 -08:00
David Anderson
e92adfe5e4 net/art: allow non-pointers as values
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-17 10:43:18 -07:00
David Anderson
ac657caaf1 net/art: add debug hooks to strideTable
Updates #7781

Signed-off-by: David Anderson <danderson@tailscale.com>
2023-07-24 13:33:48 -07:00
David Anderson
486195edf0 net/art: make each strideTable track the IP prefix it represents
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-24 13:33:48 -07:00
David Anderson
a7c910e361 net/art: implement the Table type, a multi-level art route table.
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-13 09:04:17 -07:00
David Anderson
4d1b3bc26f net/art: implement the stride table building block of ART
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>
2023-04-04 09:00:24 -07:00