Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
| projectsroutingproposal [2015/08/07 19:34] – AlexanderChernikov | projectsroutingproposal [2016/01/18 19:23] (current) – glebius | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| - | This article outlines some routing-related problems in our network stack and describes | + | This article outlines some generic |
| ==== Current problems ==== | ==== Current problems ==== | ||
| === Performance issues === | === Performance issues === | ||
| - | Many people considered routing lookups slow (and created various mechanisms of avoiding such lookups, like route caching in tunnels, or having per-flow hash record (FLOWTABLE%%))%%. | + | Many people considered routing lookups slow (and created various mechanisms of avoiding such lookups, like route caching in tunnels |
| + | or having per-flow hash record (FLOWTABLE%%))%%. | ||
| Typical packet processing (forwarding for router, or output for web server) path consists of: | Typical packet processing (forwarding for router, or output for web server) path consists of: | ||
| - | * doing routing lookup (radix read rwlock + rte mutex lock) | + | * doing routing lookup (radix read rwlock + routing entry (rte) mutex lock) |
| - | * (optionally) ifa atomic refcount acquire/ | + | * (optionally) |
| - | * doing LLE lookup (afdata read rwlock + llentry read (or write) lock) | + | * doing link level entry (lle, llentry) |
| - | Actually, given number of locks is roughly like having single Giant lock: single-cpu performance (600-1mpps) is very similar to the results you can get using modern dual-cpu system with 16/32 cores. The most expensive operation is acquiring //struct rtentry// mutex (think about default route delivering HUGE contention on single lock, which is also hold for plenty of time). However, other stuff do heavily impact processing path - we saw small (10-20%) performance increases while eliminating more and more locks. Removing last (non-batched) atomic-based lock from processing path gave us more than 2x improvement. | + | Actually, given number of locks is roughly like having single Giant lock: single-cpu performance (600-1mpps) is very similar to the results you can get |
| + | using modern dual-cpu system with 16/32 cores. The most expensive operation is acquiring //struct rtentry// mutex (think about default route delivering | ||
| + | HUGE contention on single lock, which is also hold for plenty of time). However, other locks do heavily impact processing path. | ||
| === Routing code itself === | === Routing code itself === | ||
| Dealing with performance issues revealed number of problems which also have to be dealt with: | Dealing with performance issues revealed number of problems which also have to be dealt with: | ||
| Line 25: | Line 28: | ||
| ==== Proposed solution ==== | ==== Proposed solution ==== | ||
| Most of the performance issues described in " | Most of the performance issues described in " | ||
| - | These changes permits us to scale close-to linear based on number of cores: we were able to reach close to 12MPPS for IPv6 forwarding (2xE2660, | + | We managed to remove rwlocks/ |
| - | It should also be noted, that, in general, (current) changes available in project/ | + | In fact, we were able to reach close to 12MPPS for IPv4 forwarding (2xE2660, |
| + | ==== Some benchmarks ==== | ||
| + | === Forwarding benchmark === | ||
| + | {{projectsroutingproposal/ | ||
| + | * " | ||
| + | * " | ||
| + | * " | ||
| + | * " | ||
| + | === Forwarding/ | ||
| + | {{projectsroutingproposal/ | ||
| + | * " | ||
| + | * " | ||
| + | * " | ||
| + | * " | ||
| + | * " | ||
| ==== High-level overview ==== | ==== High-level overview ==== | ||
| The key concept is hiding all routing internals and providing pre-computed easy-to-use result to all consumers with minimal locking. | The key concept is hiding all routing internals and providing pre-computed easy-to-use result to all consumers with minimal locking. | ||
| - | Additionally, | + | We provide separate functions for each address family (fib4/fib6/rib). |
| We also provide several different (in terms of returned info and relative overhead) methods of retrieving routing data. | We also provide several different (in terms of returned info and relative overhead) methods of retrieving routing data. | ||
| - | Typically, lookup result is copied to caller-provided 64-bytes nhop_* structure, with all necessary data _including_ the data that needs to be prepended to mbuf (currently - pre-computed L2 header). | + | Typically, lookup result is pre-computed next hop data, copied to caller-provided 64-bytes nhop_* structure, with (optionally) |
| - | + | ||
| - | New api/ | + | |
| - | + | ||
| - | It is worth noting that all API/ | + | |
| - | While it might have seen as a good " | + | |
| - | + | ||
| - | Another related change is avoiding IPv6 addresses with embedded scope: you could not be sure when the IP address has its scope embedded. Additionally, | + | |
| === Locking changes === | === Locking changes === | ||
| - | + | | |
| - | | + | |
| * rte mutexes are mostly unused leading to single rmlock necessary for L3 lookup | * rte mutexes are mostly unused leading to single rmlock necessary for L3 lookup | ||
| - | * LLE if_afdata lock uses the same dual-locking approach. | + | * LLE if_afdata lock uses the same dual-locking approach. |
| * Additionally, | * Additionally, | ||
| + | |||
| + | New api/ | ||
| === More details on routing === | === More details on routing === | ||
| Line 53: | Line 64: | ||
| - L4 level code (like TCP, trying to extract some useful info like MTU) Here we might need to provide things like MTU or some L4-specific data saved in given rtenry. | - L4 level code (like TCP, trying to extract some useful info like MTU) Here we might need to provide things like MTU or some L4-specific data saved in given rtenry. | ||
| - Forwarding code (_output() routines) Here again we need very basic info, so we can use optimised fib table lookups. | - Forwarding code (_output() routines) Here again we need very basic info, so we can use optimised fib table lookups. | ||
| + | - Control plane code (rtsock, address routines) Use slower rib-based procedures returning individual rtentries | ||
| === More details on LLE === | === More details on LLE === | ||
| * LLTABLE was changed to provide more callbacks (like add/ | * LLTABLE was changed to provide more callbacks (like add/ | ||
| * struct llentry is now basically split into 2 pieces: all fields within 64 bytes (amd64) are now protected by both ifdata lock AND lle lock e.g. you require both locks to be held exclusively for modification. All data necessary for fast path operations is kept here. other control-specific fields are protected by lle lock | * struct llentry is now basically split into 2 pieces: all fields within 64 bytes (amd64) are now protected by both ifdata lock AND lle lock e.g. you require both locks to be held exclusively for modification. All data necessary for fast path operations is kept here. other control-specific fields are protected by lle lock | ||
| - | | + | * simple state machine was added to ARP: in most cases (unless record is going to expire in several seconds) we can simply use lle without side effects. However, prior to expire time we have to get some sort of feedback from data path indicating if entry is really used. This is done by (mutex-locked) setting .r_skip_verify |
| - | | + | * ND state machine started to be more complex: same trick with .r_skip_verify |
| - | * ND state machine started to be more complex: same trick with .used field was applied there | + | |
| ==== Regressions ==== | ==== Regressions ==== | ||
| Line 67: | Line 78: | ||
| ==== Merge plan ==== | ==== Merge plan ==== | ||
| Basic plan looks like the following: | Basic plan looks like the following: | ||
| - | - Merge most of LLE changes not related to locking/ | + | - <del>Merge most of LLE changes not related to locking/ |
| - | - Discuss/ | + | - <del>Discuss/ |
| - | - Merge new routing lookup API | + | - Perform one-by-one conversion of non-critical |
| - | - Perform one-by-one conversion of route(4) consumers | + | - Discuss/ |
| + | - Discuss/ | ||
| - Discuss/ | - Discuss/ | ||
| - | === Considerations/ | + | ==== Status ==== |
| + | Current conversion status is available [[ProjectsRoutingProposal/ | ||
| + | ==== Considerations/ | ||
| - Wider use of rmlock in kernel. Rmlock has side effect of " | - Wider use of rmlock in kernel. Rmlock has side effect of " | ||
| - | - Is the current LLE datapath " | ||
| - Could we teach PFIL to start looking at mbuf starting from certain offset? (eliminate 2x LLE header copy) | - Could we teach PFIL to start looking at mbuf starting from certain offset? (eliminate 2x LLE header copy) | ||
| - " | - " | ||
| - Should be insert link-local routes into RIB? Typical routing lookup now looks like the following: "What is egress interface/ | - Should be insert link-local routes into RIB? Typical routing lookup now looks like the following: "What is egress interface/ | ||
| - | ==== Next steps ==== | + | ==== Future plans ==== |
| - | * Implement auto-growing array for per-radix nexthops | + | * Implement auto-growing array for per-fib-per-af |
| * Implement LLE tracking for nexthop calculations to be able to immediately provide all necessary info in single route lookup for gateway routes | * Implement LLE tracking for nexthop calculations to be able to immediately provide all necessary info in single route lookup for gateway routes | ||
| * Implement multipath support for rtsock | * Implement multipath support for rtsock | ||
| * Implement " | * Implement " | ||
| - | * Implement API for modular per-AF lookup (think about sorted array of addresses | + | * Implement API for modular per-AF |