main
15
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
|
|
25597ab3ef |
packet, fib, bench: framing helpers, one netlink reader, a mesh with named phases
A code-quality pass over the periphery. The packet crate frames a message with `begin_message` and `finish_message`, which the exporter's hand-written UPDATE header can use instead of a bare type code, and keeps the NLRI reader and writer together as a pair; the rule that the body's prefixes are IPv4 unicast lives once; a session with two-octet AS numbers no longer reserves the attributes' wire copy it never keeps. The TCP diagnostics read netlink with the netlink module's own attribute walk and helpers instead of copies of them. The kernel follower learns what the kernel has in one named step used at start and on relearning, keeps its batch buffers between wakes, and builds its task in a constructor. The mesh benchmark, which had grown six phases in one main, is a `Mesh` with named phases and a `Receiver`, with one report of the sessions for both deadlines; the collector capabilities, the KEEPALIVE bytes, the draining of a session and the printing of a table row are helpers shared by the benches, the examples and the integration tests. The MRT reader uses the packet crate's attribute splitter. Testing: a message framed by hand is the one `to_wire` writes; a short tcp_info from an old kernel leaves the later fields zero; the synthetic table is the same every run and every announcement decodes to itself. The packing example gives the same figures on the RIS dump before and after. The crates' tests, the integration tests, the kernel tests and every lab phase pass. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
c70a223d0d |
rib: a reader counts the table once a poll, not once a shard
A router with many peers has a reader of the table's journal for each session that is sent learned routes, seventy on ddln, and every change to the table wakes them all. Each pass of a reader went round every shard, and for each shard took a count on the table (an Arc clone) to hold it while the shard was read, and gave it back after: two atomic adds on one cache line, by seventy readers, 256 shards a pass. A profile of ddln taking a table from the other router had the reader's poll as the top function at two to three cores, and in the Linux VM with 64 such sessions half of all CPU time was in the two atomic add instructions. The sessions writing to the table waited behind it: the table came in at 58,000 routes a second. The count is now taken once a poll. And each journal keeps its latest sequence number in an atomic the table holds the other end of, so that a reader can tell a shard with nothing new for it from one with something without the shard's lock, and pass over it: on a quiet table, which is what the readers see most of the time, a pass is a load a shard and no lock. An exporter that is sent little of a table, as one to a peer at an exchange is, no longer makes a verdict of nothing for a prefix the peer does not hold, which cost a map insert and a lookup on the way out, and tells a route that came down or across (RFC 9234) from its attributes' bytes before parsing them. Testing: the mesh benchmark can have any number of collector sessions of the first router (BENCH_COLLECTORS): peers in the sense of RFC 9234, sent learned routes, with the feeders' routes marked as having come across from a peer, so that each has a reader following the table while it fills and passes nearly all of it over, as a router with many peers at exchanges has. In the Linux VM with 64 of them, three rounds alternating with the previous commit, the routers' exchange of their tables takes 11 s instead of 20 s, at 86 s of CPU time instead of 155 s; without them it is unchanged. The table's tests, the server tests, the integration tests, the kernel tests and every lab phase pass. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
a15efaa26c |
export: give the leave to gather back once the table is gathered
The last change held a session's leave to gather a table, of which there are four, until its table had gone out. A peer that reads at the pace of its receive window takes hours over a table, and two such peers held two of the four for that long, keeping other sessions from gathering theirs: they waited for a leave before their first UPDATE. The leave is for the memory a gather takes; what is still held once the table is gathered is let go of as it goes out, as it was before the gather was reworked. The mesh benchmark's new peer can also come once the first router has its own peers' routes and the other router's are still arriving (BENCH_RECEIVER_EARLY=2), as a router's sessions come up after a restart while its peers' tables arrive; the walk of a full table while the table fills costs the arriving routes nothing measurable in the VM. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
7425b101ed |
export: gather a table by attributes, then stream it
A table given out anew to a session, at its start or when the journal had let changes go, was gathered as a verdict for each prefix, each with the route dressed for the session, and sent once the table was all there. Dressing a route parses its attributes and encodes them for the session, so a table of five million routes took seconds before the first UPDATE went, on one worker thread without a yield. And the routes that share attributes went out in separate UPDATEs after all: they were grouped by the dressed form, of which only so many are kept, and the routes of a set are spread over the whole table, so by the time the next was reached the form had been let go of and made anew. The mesh benchmark's new peer got four million routes in 3.8 million UPDATEs; on a RIPE RIS table, grouped whole, a full table is 160,000 UPDATEs and 21 MB, and grouped in slices of 4,096 routes it is 845,000 UPDATEs and 72 MB, so slices are not the answer either. The table is now gathered by what dresses its routes: the attribute set as the table has it, who the route is from, and its IP version. Nothing is dressed while gathering, which is a map insert a route. Once the table is all there, each set is dressed once, with the thread lent to the other tasks every few thousand, and then the sets go out one after the other, each as few UPDATEs as its routes fit in, with the peer reading the first while the rest are sent. A prefix heard of again while the table is read supersedes what was heard before: each word on a prefix is numbered, and only the latest goes. Path identifiers are given at gathering, in the order the table has a prefix's routes, so that they are as before. What was announced before and not heard of again is withdrawn after the table, as before. The exporter never blocks the thread on a table: the steady state's batch is small, and the gathered table is gone through with yields. Testing: a new test gives a session a table of 300 routes sharing three sets of attributes, spread over the shards, and checks they go in three UPDATEs. The mesh benchmark has a new phase in which a peer takes the first router's table once the mesh is complete, timing the first UPDATE and the whole; its feeders now negotiate no hold timer, since they say nothing after their tables, and `BENCH_LOG` prints the routers' logs. A new example, packing, counts the UPDATEs and octets a RIS table takes grouped whole and in slices. The server tests, the integration tests, the kernel tests and every lab phase pass. In the Linux VM, three rounds alternating with the previous commit, the new peer's first UPDATE comes 2.9 s after its session is up instead of 5.3 s, and it has all four million routes in 4.0 s instead of 8.0 s, in 667,000 UPDATEs instead of 3.76 million; the whole run takes 22.4 s of CPU time instead of 26.2 s. The routers' exchange of their tables, which does not go through this path once their sessions are up, is unchanged within its noise. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
cbc1dc7e44 |
bench: two routers exchanging their tables with ADD-PATH
The full-table benchmark measures one router taking in tables from its peers. What two routers of one AS do with each other, each sending the other every path it has (ADD-PATH both ways with all_paths, as a mesh of routers that each hold the network's whole view is configured), was measured nowhere: the exporter following the table's journal while the sessions fill the table, at the size of the Internet. In production that exchange took 70 seconds for a table that arrives from the Internet in 20. A new benchmark, mesh, starts two servers in one AS with distinct router IDs, peers them over IPv6 loopback with ADD-PATH both ways and all_paths, and feeds the first from four synthetic peers and the second from two over IPv4 loopback (BENCH_PEERS, BENCH_PEERS_B, BENCH_SCALE_DOWN). It prints how long each router takes to hold its own peers' routes and then the other's, with the rate of the latter. BENCH_DEADLINE prints the sessions' state if a router is not there in time. The benchmarks now allocate with jemalloc, as the daemon does, except when memory is being counted: the C library's allocator put its own locks in the profiles. Two routers on one host have each other's addresses as next hops, loopback addresses, which the import check refuses as it refuses a next hop that is this machine; the permissive import policy, which only tests use and no configuration can ask for, now takes them. Testing: the next-hop test covers both policies; the benchmark runs on macOS and in the Linux VM under perf. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
ec5c9be454 |
export: advertise every route for a prefix with ADD-PATH (all_paths)
Before this change, a session on which ADD-PATH (RFC 7911) was
negotiated in the sending direction was sent path identifiers, but only
the best route for each prefix. A route collector such as bgp.tools
wants every route a router has accepted, from every neighbor, and from
one session: without this the collector saw one path per prefix, nearly
always the same neighbor's.
This change adds `all_paths` to the export policy. On a session with it,
and ADD-PATH send negotiated for a family, every accepted route for a
prefix of that family is advertised, each with a path identifier of its
own; for a family without ADD-PATH send the best route goes as before.
`all_paths` needs `learned_routes` (a configuration error otherwise) and
the peer's `add_path` to offer sending. The export policy, the role
rules, the well-known communities and the export limits apply to every
route alike, and the export limits count every route.
Implementation, in the advertiser:
* An exporter with `all_paths` follows the table's journal of all routes
(`RibTable::reader_of_all_routes`, until now unused) instead of the
best-route journal, and is given all the routes of a prefix whenever
one of them changes (`News::Routes`).
* What the peer holds is `Announced`: the set of prefixes for a
best-route session, as before; or for an all-paths session, for each
prefix the routes announced, keyed by the peer they came from and that
peer's own identifier, with the identifier they went out with and the
form they went out in. A route keeps its identifier for as long as it
is announced, goes out again only if it changed, and is withdrawn by
its identifier; a new route gets the lowest identifier not in use for
the prefix, from 1.
* Verdicts carry either kind (`Verdict::Best`, `Verdict::All`), and a
reset of the table puts what was announced in doubt until heard of
again, as before, with the same identifiers kept across the reset.
* The record for an all-paths session is about 50 bytes a route, some
tens of megabytes for a full table from several neighbors; the
best-route bookkeeping is unchanged in size.
Also, so that a collector session can be watched: the number of routes
advertised to each peer and not withdrawn since, every route counted
where several are sent for a prefix. The exporter keeps it in the
session's counters after every change; it is `advertised_routes` in
`/api/peers`, the "sent" column of the status page's neighbor table,
and the gauge `bgp_peer_advertised_routes{peer}`.
Documentation: a "Feeding a Route Collector" section in the guide to
passing routes on, with the configuration for a collector; `all_paths`
in the configuration reference; the ADD-PATH sections of the neighbor
guide and the standards reference; the limitation that was removed;
the new field, column and metric in the HTTP API, monitoring and
metrics references.
Testing: an integration test with two feeders and a collector that
negotiated ADD-PATH receive, which checks the two routes with their
identifiers, the withdrawal of one by its identifier, a changed route
keeping its identifier and a new route taking the free one; a
configuration test for `all_paths` without `learned_routes`; a new
`collector` phase of the interoperability lab in which FRR, as a route
collector, is told both of BIRD's routes for a prefix from BIRD's two
sessions and holds them apart, and loses one when its session is
disabled, with the advertised count checked at each step. The workspace tests, the kernel tests and every lab phase pass.
Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
|
||
|
|
48da8cc7d2 |
rib: size the routing table for the routes the peers are expected to send
The routing table's shards started empty and grew as routes came in, each growth moving every row of the shard into a table twice the size. In a profile of the daemon taking in a full table, the growth showed as up to a seventh of the session's time, and the daemon's resident memory had the old and the new table of each shard side by side for a moment. This change adds `RibTable::expect_prefixes`, which reserves room for that many prefixes spread over the shards, and has the server call it at startup with the largest `expected_routes` among the configured peers: the prefixes of several full tables are mostly the same ones. Without `expected_routes` nothing changes. The `full_table` benchmark does the same unless `BENCH_PRESIZE=0`. Measured, the saving in time is within the run-to-run noise: in the Linux VM one peer's table is in the routing table in 0.81 s instead of 0.89 s, and the kernel is in step at about the same time as before; three pairs of runs of the benchmark on a Mac average 0.33 s against 0.35 s. The profile's attribution to the growth was mostly sampling skid. The memory saving is real: 442 MiB resident with one peer's table in instead of 483 MiB, and 626 MiB instead of 632 MiB with four. Also: the profiling script printed nothing for the kernel's change counts because it asked `/metrics` for them; the endpoint is `/metricz`. With that fixed, a four-peer load shows 1.25 million installs for 1.23 million prefixes: the journal already gives the kernel task only the latest change of a prefix when it lags, so no further coalescing of installs is called for. Documentation: `expected_routes` in the configuration reference, the neighbor guide and the proto comment say that the table is sized by it; the testing guide's VM results are brought up to date. Testing: a table test checks that the room is there and is kept; the workspace tests pass. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
175a13d506 |
Hygiene: scripts, CI, docs and manifests
- scripts/in-namespace.sh set CARGO_TARGET_DIR to the empty string when it was unset, which cargo refuses, and dropped RUSTFLAGS, so the run in the namespace rebuilt what kernel-tests.sh had just built. Each is passed on only where set. - The README's list of unsupported features still had route reflection and graceful restart, both of which exist; the command-line reference lacked SIGUSR1 and exit status 75; the HTTP API reference did not say what errors look like. - The event stream said "missed 0 events" for the best-routes stream, which does not count what it missed; it leaves the count out now. - CI lints bgp-bench with its count-memory feature, which nothing built. - bgp-bench had two unused dev-dependencies; bgp-integration-tests had three dependencies that only its tests and examples use. - install.sh updates apt before installing; two-routers.sh loses an unused variable; small things in the web crate. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
b16227c51f |
Route reflection, with ourselves as next hop
A route learned from one router of our AS went to no other (RFC 4271 §9.2.1), so every router needed a session with every other. A router at the end of a single link, with one session to its neighbour inside the AS, heard only of what that neighbour learned itself, and nothing of what the neighbour had from the routers behind it. A peer in our own AS can now be made a route reflector client (`route_reflector_client`, RFC 4456). What a client sends goes to all our routers; what the others send goes to the clients. A reflected route gets ORIGINATOR_ID (where it started, if it does not say) and our cluster ID at the front of CLUSTER_LIST; it is not sent back to the router it started at, nor round to a cluster it has been through, and one that comes back anyway is refused as "route reflected back to us". The cluster ID is the router ID unless `cluster_id` says otherwise. The two attributes are now decoded as such rather than kept as bytes, and are never sent to other networks. Unlike a standard reflector, this one is the next hop of what it reflects, as it is of everything it announces: there is no resolving a next hop that is not a neighbour, so a client reaches what lies behind another router through the reflector. Only peers in our own AS can be clients; the configuration refuses the setting for any other. Nothing changes in what other networks are told: Only to Customer marks go along with reflected routes, and every receiving session keeps its own max_prefixes. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> |
||
|
|
1e2e8f2d86 |
Pass learned routes on to peers, with marks and control communities
What was to be scripted is configuration, done natively:
- import { add_communities, add_large_communities, remove_communities,
local_pref }: every route taken from a peer is marked (where it was
learned, say), with nobody else's word for our marks taken, and given
its preference, which selection goes by.
- export { add_communities, add_large_communities, remove_communities,
as_path_prepend, learned_routes }, for a peer or for all that have none
of their own.
- control_communities: the communities by which routes say which peers
they are passed on to, as exchanges' route servers have them (0:P, L:P,
0:L, and the large forms L:0:P, L:1:P, L:0:0), taken off as the route
goes on.
And what the last of these is for: with export.learned_routes a peer is
told the best route of every prefix the others announced. The rules are
BGP's and cannot be turned off: not back where it came from, not to a
peer whose AS is on the path, not between two internal peers, not past
NO_EXPORT or NO_ADVERTISE; our AS on the path and ourselves as next hop
to another network, LOCAL_PREF to our own; to a route server's client
the path, MED and next hop as they came (RFC 7947). Which routes go where
follows from the roles of RFC 9234: a route that came down or across goes
on down only, so that with roles on every peer this makes us transit for
our customers and nothing else. A peer without a role is told everything,
and the daemon says so at startup.
Each session follows the table's best routes with a reader and keeps the
prefixes it has announced, so that it can withdraw them. Routes that go
out alike go in one UPDATE: changes are gathered for 50 ms first, and a
table that is given out anew is gathered whole (at most four sessions at
a time; it is tens of megabytes). For that to work the table's journal
had to give out together what was written together: every change now
carries a time on a table-wide clock, a reader's pass reads every shard
up to one time, no further than the changes that are complete in every
shard, and a resync takes its places in the journals as of one time.
One peer sending 1.23 M routes over a session, another told of them:
in our table after 0.47 s, all heard after 2.1 s, four routes an UPDATE.
The lab has a phase, transit: FRR as our customer and BIRD as our
provider, routes each way with the right paths and marks, one kept back
by a community, and pings between their networks through us.
Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
|
||
|
|
9367c38907 |
Remove policy scripts
Rhai made a decision about a route cost one to three microseconds, some two hundred times what the same costs in Rust. That was bearable where a function is asked once for an UPDATE, and is not where every route is weighed against every peer, as it is when routes are passed on. What is wanted of a policy (mark routes by where they came from, mark what is announced, let communities say who is told what) needs no language; it is to be configuration, done natively. Kept from that work: route selection goes by a LOCAL_PREF that policy set on a route from an external peer, and the lab's configuration can be added to by a phase. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
cbf0df1eef |
Policy scripts: the operator's own rules for routes, in Rhai
A new crate, bgp-policy, runs functions of a script on routes: on their
way in, after the general checks of a peer's import and before the
checks that can change (RPKI, next hop reachability); and on their way
out to a peer. A function is given the route and the peer, may refuse
the route, and may change its communities, large communities,
LOCAL_PREF and MED, and on the way out prepend our AS:
fn from_peer(route, peer) {
if route.has_community("65535:666") { return false; }
route.add_community(LEARNED_FROM[peer.role]);
route.local_pref = PREFERENCE[peer.role];
true
}
Configuration: policy { path | source, import_function, export_function }
and, for a peer, import { function } and export { function }. The script
is compiled at startup; `bgp --check` reads it and says which function
is whose. A function that fails on a route has refused it. Scripts have
no files, network or clock, and are stopped after 200,000 steps.
Route selection now goes by a LOCAL_PREF on a route from an external
peer: the decoder never lets a peer's own through, so one that is there
was set by policy.
What it costs was measured before it was built on (benches/policy.rs):
a call that tests a few communities and changes two takes 1 to 3
microseconds, some two hundred times what Rust would. So a function is
asked once for the routes of an UPDATE, which share their attributes,
unless it asks for the prefix. One peer sending 1.23 M routes over a
session: 0.37 s without a function, 0.80 s with one that marks and
ranks every route, 3.4 s if it also looks at the prefix.
Export applies to what is announced, which today is what the daemon
originates; learned routes are not passed on yet.
Tested by unit tests of the crate, sessions end to end, a fuzz target on
the example script (testdata/policy.rhai), and a lab phase in which a
script changes which of FRR's and BIRD's route is chosen and what each
of them is told.
Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com>
|
||
|
|
fd2248feb5 |
Peer at link-local addresses: fe80::1%eth0
A peer's endpoint may be a link-local IPv6 address with the interface it is on. Such a peer is the address and the interface together, wherever peers are told apart: admission, collisions, hold-downs, the refusal log, the status page. The interface is looked up by name each time it is needed, so one that appears later or is made anew is found. Our routes go out with our link-local address in both places of MP_REACH_NLRI's next hop, as FRR sends its own. A peer's link-local next hop is taken alone, twice, or after "::" (BIRD), and resolved in the kernel on the interface of the session rather than by looking fe80::/64 up, which every interface has. The lab has a new phase, linklocal: sessions with FRR (by interface, with radvd beside the daemon) and BIRD over a LAN with link-local addresses only, both families, pings across, the interface down and up. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
e2b1979e38 |
Judge every route a peer announces: import policy, prefix limit, hold-down
A configured peer could announce any prefix with any path, in any number, and all of it was stored and could be chosen as best. Each peer now has an import policy, and every route goes through it before it reaches the routing table. Checks that hold for any peer unless turned off for it: - no prefixes that are not routed on the Internet (private, loopback, link-local, documentation, multicast, reserved; for IPv6, anything outside global unicast); - nothing longer than /24 or /48, no default route, nothing shorter than /8 or /16; - no reserved, private or documentation AS number in the path; - a path that begins with the peer's own AS (turned off for a route server), and of at most 64 AS numbers. Always: a route with our own AS number in its path is refused. RFC 4271 requires this loop check and it was missing. Per peer, if configured: the prefixes it may announce, each with an optional longest more-specific, and the AS numbers its routes may originate from. This is the list generated from the routing registries. max_prefixes limits how many routes a peer may have. One more ends the session with Cease / Maximum Number of Prefixes Reached, and the peer is kept down for hold_down_seconds (ten minutes unless set): its connections are not taken and it is not dialled. Refused routes do not count towards the limit. A refused route is withdrawn rather than ignored, so that it replaces whatever the peer had announced for it before. On a session with two-octet AS numbers the path is judged with its AS4_PATH merged in, so that the real AS numbers are what is checked. Peers that are not configured (accept_unconfigured_peers, for test networks) get a policy that takes everything but loops. Refusals are counted in bgp_routes_rejected_total by reason. The status page and /api/peers show, for each session, how many routes the peer has and how many were refused. The server warns at startup about peers with no limit. The prefix check costs about 4 ns a route with the default policy; the end-to-end benchmark is unchanged. Also: the benchmark's server AS is one that is in none of its generated paths, and a table test that depended on the hasher's seed is fixed. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |
||
|
|
630c175918 |
Rework the speaker: sans-I/O FSM, sharded table, RFC 7606, ADD-PATH
The work of the speaker-cleanup branch as one commit; the branch keeps the step-by-step history. Sessions - The state machine is a pure function from events to actions, driven by one task per connection. Idle, Connect and Active belong to a dialer that keeps configured peers up with backoff. - Capabilities are negotiated: address families, four-octet AS numbers with AS_TRANS and AS4_PATH, route refresh, ADD-PATH per family and direction. - Collision detection per RFC 4271 section 6.8, by address and identifier. - Connections are taken only from configured peers, a few per address. - A panic in a session is contained and answered with a Cease; a core task that stops shuts the server down with a Cease to every peer. - Writes that make no progress are given up (RFC 9687). Codec - Malformed UPDATEs are handled as RFC 7606 says: treat-as-withdraw, attribute discard, or session reset, with the NOTIFICATION to send. - Address families are open types; any can be named and ignored. - Prefixes are fixed-size values, normalised, with path identifiers. - Lengths are filled in after writing; one definition of each type code. - Property tests and fuzz targets for every decoder. Routing table - Adj-RIBs-In and Loc-RIB in one sharded table that sessions write to directly. Routes are sixteen bytes; attribute sets are interned in wire form. Best-path selection per RFC 4271 section 9.1.2.2 with deterministic MED. - A journal per shard lets followers read changes at their own pace; one that falls behind is resynchronised. - On a RIPE RIS dump of 148 peers and 39.3M routes: loaded in 2.0 s on 12 cores, about 52 bytes a route. Announcing - Originated routes come from the configuration. Each session has its own exporter with an Adj-RIB-Out, so a slow peer delays only itself. - Routes to a peer in our own AS have an empty path and a LOCAL_PREF. Operations - HTTP status page, JSON API, event stream and Prometheus metrics. - Benchmarks on synthetic and real tables. Co-Authored-By: Claude Fable 5.1 <noreply@anthropic.com> |