FRRouting
lib: Substitute poll APIs with epoll APIs in thread management routine
This pull request is encourged by comments in this issue. previously discarded PR
Problem overview
In all currently available FRR version, event.c and frrevent.h in libfrr used poll() function to poll file descriptors. We advise to substitute it with epoll() to enhance scalability.
Motivation
We are trying run BGP abnormal events simulation with FRR routers. In our scenario, we aim to run plenty of (hundreds/thousands of) FRR routers, which are mutually TCP connected to simulate BGP peer topology in reality, on a single COTS server.
Experiment
Currently we have not simulate BGP peer topology in reality yet. Rather, we configure a fullmesh BGP connection between all FRR routers for test purpose. Also we have not launch route announcement and withdrawal yet. Only BGP keepalive packets are sent between FRR BGP peers. Environment: AMD EPYC 7742 64-Core Processor(Only 16 cores used); 660GB RAM; CentOS7; Linux kernel version 5.17.3-1.el7.elrepo.x86_64; FRR version 8.0. FRR BGP Configuration: fullmesh connection; keepalive interval: 1s; holdtime: 3s.
Observation
We found poor scalability when deploying increasing number of FRR routers. As seen from figure below, CPU util increases quadratically at the early stage of scaling. After 250 peers deployed, the CPU util increasing slows down. However at this point FRR peers become stressful. Finally, disconnection between peers happens after 384 peers being deployed.
Analysis
We drew flamegraph of BGP threads of FRR, and found poll() function was the bottleneck. As shown below
poll() function scans all file descriptors every time it is called. In our case, these file descriptors are mostly TCP sockets established with BGP peers. As the number of peers deployed (denoted by n) increases, every poll() call consumes O(n) time, leading to O(n) CPU util for each peer. Multiplied by n(number of BGP threads doing poll()), the system-wide CPU util is O(n^2), matching the observation above. To comfirm that poll() introduces great overhead, we measured average running time of per poll() call. As shown below, the call time did increase linearly with peer number.
However, scanning all TCP sockets is a waste in this scenario, since keepalive interval (1s) is long. At most time, each TCP socket is not ready for reading. Therefore, substituting poll() with epoll APIs will help reduce CPU overhead significantly.
Solution (prototype)
We re-wrote thread.c and thread.h in libfrr with epoll APIs, and ran experiement again. As shown below, CPU overhead is greatly reduced (nearly 67%).
Code
The pull request modifies lib/thread.h and lib/thread.c in FRR version 8.4 and can be correctly compiled. However, we only ran aforementioned experiments using FRR version 8.0 (either poll-version or epoll-version). Therefore we also provide our epoll-version code here modified from FRR version 8.0.
Our code was just a prototype, since Vtysh command such as show_thread_poll_cmd was not implemented, and bugs may exist. If the community feels this issue important, we can complete the code.
epoll APIs are only available in Linux. I plan to rollback to poll() in OSes other than linux. I can achieve this by adding macroes for epoll APIs detection. Would that be fine?
This sounds okay to me ...
This pull request has conflicts, please resolve those before we can evaluate the pull request.
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
@ton31337 @eqvinox @riw777 I can't pass CI system topotest. Build logs of AddressSanitizer TopoTests and oridinary TopoTests are as follow, repectively:
28-Mar-2023 06:47:11 | Starting task 'Run Topotests with AddressSanitizer' of type 'com.atlassian.bamboo.plugins.scripttask:task.builder.command'
-- | --
28-Mar-2023 06:47:11 | Beginning to execute external process for build 'FRRouting - FRR-Pull-Requests - AddressSanitizer Topotests Part 0 #10409 (FRR-PULLREQ2-ASAN3-10409)' ... running command line: /bin/bash ci/topotests/asan/run_topotests.sh ... in: /root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-ASAN3
28-Mar-2023 06:47:11 | Running Topology Tests with Address Sanitizer on mininet2427.lab.netdef.org
28-Mar-2023 06:47:11 | Using ExaBGP 3.4.17 with test scripts on agent
28-Mar-2023 06:47:11 | Using py.test with python2 to run test scripts on agent
28-Mar-2023 06:47:11 | Detected Micronet. Using py.test-3 with python3 to run test scripts on agent
28-Mar-2023 06:47:11 | ============================= test session starts ==============================
28-Mar-2023 06:47:11 | platform linux -- Python 3.8.9, pytest-6.2.2, py-1.11.0, pluggy-0.13.1 -- /usr/local/bin/python3.8
28-Mar-2023 06:47:11 | cachedir: .pytest_cache
28-Mar-2023 06:47:11 | rootdir: /root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-ASAN3/topotests, configfile: pytest.ini
28-Mar-2023 06:47:11 | plugins: xdist-2.5.0, forked-1.4.0
28-Mar-2023 06:47:12 | collecting ...
28-Mar-2023 06:47:12 | ----------------------------- live log collection ------------------------------
28-Mar-2023 06:47:12 | 2023-03-28 13:47:12,947 WARNING: lib.micronet.commander.micronet: Commander(micronet): proc failed: rc 1 pid 8158
28-Mar-2023 06:47:12 | args: /root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-ASAN3/topotests/lib/grpc-query.py --check
28-Mar-2023 06:47:12 | stderr: ERROR:root:can't create proto definition modules No module named 'grpc'
28-Mar-2023 06:47:12 | Traceback (most recent call last):
28-Mar-2023 06:47:12 | File "/root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-ASAN3/topotests/lib/grpc-query.py", line 21, in <module>
28-Mar-2023 06:47:12 | import grpc
28-Mar-2023 06:47:12 | ModuleNotFoundError: No module named 'grpc':
28-Mar-2023 06:47:13 | collected 58 items / 1 skipped / 57 selected
28-Mar-2023 06:47:13 |
28-Mar-2023 06:47:13 | Test: babel_topo1/test_babel_topo1.py::test_converge_protocols
28-Mar-2023 08:03:35 | Force Stop build feature is enabled for current plan. Either Bamboo has detected the build has hung or it has been manually stopped.
28-Mar-2023 08:03:35 | Attempting to generate stack trace and terminate spawned sub-processes of process id: 12300
28-Mar-2023 08:03:35 | Found related process: pid: 8127 ppid: 12300 pgid: 848 %cpu: 0.0 %mem: 0.0 cmd: /bin/bash
28-Mar-2023 08:03:35 | Found related process: pid: 8140 ppid: 8127 pgid: 848 %cpu: 0.0 %mem: 0.2 cmd: python3
28-Mar-2023 08:03:35 | Found related process: pid: 8139 ppid: 8127 pgid: 848 %cpu: 0.0 %mem: 0.7 cmd: /usr/local/bin/python3.8
28-Mar-2023 08:03:35 | Found related process: pid: 8228 ppid: 8139 pgid: 8228 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 08:03:35 | Found related process: pid: 8215 ppid: 8139 pgid: 8215 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 08:03:35 | Found related process: pid: 8578 ppid: 8139 pgid: 848 %cpu: 0.0 %mem: 0.0 cmd: /bin/bash
28-Mar-2023 08:03:35 | Found related process: pid: 8293 ppid: 8139 pgid: 8293 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 08:03:35 | Found related process: pid: 8358 ppid: 8139 pgid: 8358 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 08:03:35 | Found related process: pid: 8579 ppid: 8578 pgid: 848 %cpu: 0.0 %mem: 1.2 cmd: vtysh
28-Mar-2023 08:03:35 | getStackTraceAndKillRelatedProcesses for 9 processes
28-Mar-2023 08:03:35 | Executing kill -3 8579
28-Mar-2023 08:03:35 | Executing kill -3 8358
28-Mar-2023 08:03:35 | Executing kill -3 8293
28-Mar-2023 08:03:35 | Executing kill -3 8578
28-Mar-2023 08:03:35 | Executing kill -3 8215
28-Mar-2023 08:03:35 | Executing kill -3 8228
28-Mar-2023 08:03:35 | Executing kill -3 8139
28-Mar-2023 08:03:35 | Executing kill -3 8140
28-Mar-2023 08:03:35 | Executing kill -3 8127
28-Mar-2023 08:03:40 | Killing: 8579
28-Mar-2023 08:03:40 | Executing kill 8579
28-Mar-2023 08:03:40 | Killing: 8358
28-Mar-2023 08:03:40 | Executing kill 8358
28-Mar-2023 08:03:40 | Killing: 8293
28-Mar-2023 08:03:40 | Executing kill 8293
28-Mar-2023 08:03:40 | Killing: 8578
28-Mar-2023 08:03:40 | Executing kill 8578
28-Mar-2023 08:03:40 | Killing: 8215
28-Mar-2023 08:03:40 | Executing kill 8215
28-Mar-2023 08:03:40 | Killing: 8228
28-Mar-2023 08:03:40 | Executing kill 8228
28-Mar-2023 08:03:40 | Killing: 8139
28-Mar-2023 08:03:40 | Executing kill 8139
28-Mar-2023 08:03:40 | Killing: 8140
28-Mar-2023 08:03:40 | Executing kill 8140
28-Mar-2023 08:03:40 | Killing: 8127
28-Mar-2023 08:03:40 | Executing kill 8127
28-Mar-2023 08:03:40 | done
28-Mar-2023 08:03:40 | ci/topotests/asan/run_topotests.sh: line 117: 8139 Terminated ${py_test_cmd} --junitxml ../topotests.xml -vv -s --tb=no 2>> /dev/null
28-Mar-2023 08:03:40 | Switching to default ExaBGP version
28-Mar-2023 08:03:40 | 8140 \| ../ci/topotests/topo_logfilter.py log_topotests.txt
28-Mar-2023 08:03:40 | Failing task since return code of [/bin/bash ci/topotests/asan/run_topotests.sh] was 143 while expected 0
28-Mar-2023 08:03:40 | Finished task 'Run Topotests with AddressSanitizer' with result: Failed
28-Mar-2023 06:43:51 | Starting task 'Run Topology Tests' of type 'com.atlassian.bamboo.plugins.scripttask:task.builder.command'
-- | --
28-Mar-2023 06:43:51 | Beginning to execute external process for build 'FRRouting - FRR-Pull-Requests - TopoTests Debian 10 amd64 Part 0 #10409 (FRR-PULLREQ2-TOPO0DEB10AMD64-10409)' ... running command line: /bin/bash ci/topotests/run_topotests.sh ... in: /root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-TOPO0DEB10AMD64
28-Mar-2023 06:43:51 | Running Topology Tests on mininet427.lab.netdef.org
28-Mar-2023 06:43:51 | Using ExaBGP 3.4.17 with test scripts on agent
28-Mar-2023 06:43:51 | Using py.test with python2 to run test scripts on agent
28-Mar-2023 06:43:51 | Detected Micronet. Using py.test-3 with python3 to run test scripts on agent
28-Mar-2023 06:43:52 | ============================= test session starts ==============================
28-Mar-2023 06:43:52 | platform linux -- Python 3.8.9, pytest-6.2.2, py-1.11.0, pluggy-0.13.1 -- /usr/local/bin/python3.8
28-Mar-2023 06:43:52 | cachedir: .pytest_cache
28-Mar-2023 06:43:52 | metadata: {'Python': '3.8.9', 'Platform': 'Linux-4.19.0-23-amd64-x86_64-with-glibc2.28', 'Packages': {'pytest': '6.2.2', 'pluggy': '0.13.1'}, 'Plugins': {'html': '3.2.0', 'metadata': '2.0.4', 'forked': '1.4.0', 'xdist': '2.5.0'}}
28-Mar-2023 06:43:52 | rootdir: /root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-TOPO0DEB10AMD64/topotests, configfile: pytest.ini
28-Mar-2023 06:43:52 | plugins: html-3.2.0, metadata-2.0.4, forked-1.4.0, xdist-2.5.0
28-Mar-2023 06:43:54 | collecting ...
28-Mar-2023 06:43:54 | ----------------------------- live log collection ------------------------------
28-Mar-2023 06:43:54 | 2023-03-28 13:43:54,864 WARNING: lib.micronet.commander.micronet: Commander(micronet): proc failed: rc 1 pid 3561
28-Mar-2023 06:43:54 | args: /root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-TOPO0DEB10AMD64/topotests/lib/grpc-query.py --check
28-Mar-2023 06:43:54 | stderr: ERROR:root:can't create proto definition modules No module named 'grpc'
28-Mar-2023 06:43:54 | Traceback (most recent call last):
28-Mar-2023 06:43:54 | File "/root/bamboo-agent-home/xml-data/build-dir/FRR-PULLREQ2-TOPO0DEB10AMD64/topotests/lib/grpc-query.py", line 21, in <module>
28-Mar-2023 06:43:54 | import grpc
28-Mar-2023 06:43:54 | ModuleNotFoundError: No module named 'grpc':
28-Mar-2023 06:43:55 | collected 58 items / 1 skipped / 57 selected
28-Mar-2023 06:43:55 |
28-Mar-2023 06:43:55 | Test: babel_topo1/test_babel_topo1.py::test_converge_protocols
28-Mar-2023 07:25:34 | Force Stop build feature is enabled for current plan. Either Bamboo has detected the build has hung or it has been manually stopped.
28-Mar-2023 07:25:34 | Attempting to generate stack trace and terminate spawned sub-processes of process id: 7584
28-Mar-2023 07:25:34 | Found related process: pid: 3531 ppid: 7584 pgid: 729 %cpu: 0.0 %mem: 0.0 cmd: /bin/bash
28-Mar-2023 07:25:34 | Found related process: pid: 3542 ppid: 3531 pgid: 729 %cpu: 0.1 %mem: 0.7 cmd: /usr/local/bin/python3.8
28-Mar-2023 07:25:34 | Found related process: pid: 3543 ppid: 3531 pgid: 729 %cpu: 0.0 %mem: 0.2 cmd: python3
28-Mar-2023 07:25:34 | Found related process: pid: 3622 ppid: 3542 pgid: 3622 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 07:25:34 | Found related process: pid: 3681 ppid: 3542 pgid: 3681 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 07:25:34 | Found related process: pid: 3609 ppid: 3542 pgid: 3609 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 07:25:34 | Found related process: pid: 3947 ppid: 3542 pgid: 729 %cpu: 0.0 %mem: 0.0 cmd: /bin/bash
28-Mar-2023 07:25:34 | Found related process: pid: 3747 ppid: 3542 pgid: 3747 %cpu: 0.0 %mem: 0.0 cmd: /bin/cat
28-Mar-2023 07:25:34 | Found related process: pid: 3948 ppid: 3947 pgid: 729 %cpu: 0.0 %mem: 0.7 cmd: vtysh
28-Mar-2023 07:25:34 | getStackTraceAndKillRelatedProcesses for 9 processes
28-Mar-2023 07:25:34 | Executing kill -3 3948
28-Mar-2023 07:25:34 | Executing kill -3 3747
28-Mar-2023 07:25:34 | Executing kill -3 3947
28-Mar-2023 07:25:34 | Executing kill -3 3609
28-Mar-2023 07:25:34 | Executing kill -3 3681
28-Mar-2023 07:25:34 | Executing kill -3 3622
28-Mar-2023 07:25:34 | Executing kill -3 3543
28-Mar-2023 07:25:34 | Executing kill -3 3542
28-Mar-2023 07:25:34 | Executing kill -3 3531
28-Mar-2023 07:25:39 | Killing: 3948
28-Mar-2023 07:25:39 | Executing kill 3948
28-Mar-2023 07:25:39 | Killing: 3747
28-Mar-2023 07:25:39 | Executing kill 3747
28-Mar-2023 07:25:39 | Killing: 3947
28-Mar-2023 07:25:39 | Executing kill 3947
28-Mar-2023 07:25:39 | Killing: 3609
28-Mar-2023 07:25:39 | Executing kill 3609
28-Mar-2023 07:25:39 | Killing: 3681
28-Mar-2023 07:25:39 | Executing kill 3681
28-Mar-2023 07:25:39 | Killing: 3622
28-Mar-2023 07:25:39 | Executing kill 3622
28-Mar-2023 07:25:39 | Killing: 3543
28-Mar-2023 07:25:39 | Executing kill 3543
28-Mar-2023 07:25:39 | Killing: 3542
28-Mar-2023 07:25:39 | Executing kill 3542
28-Mar-2023 07:25:39 | Killing: 3531
28-Mar-2023 07:25:39 | Executing kill 3531
28-Mar-2023 07:25:39 | Switching to default ExaBGP version
28-Mar-2023 07:25:39 | Terminated
28-Mar-2023 07:25:39 | Failing task since return code of [/bin/bash ci/topotests/run_topotests.sh] was 143 while expected 0
28-Mar-2023 07:25:39 | Finished task 'Run Topology Tests' with result: Failed
Each time I commit my code for test, Topotests take very long time (see timestamps around "import grpc" lines above) and finally killed by CI system. It seems that the tests failed because python in CI environment didn't contain grpc module, not because of bugs in my codes.
Code format is fixed.
I added a macro DISABLE_EPOLL in my code to determine which APIs (poll/epoll) are used. Users can roll back to using poll() APIs by providing DISABLE_EPOLL CFLAGS at configuration stage.
./configure CFLAGS="-DDISABLE_EPOLL" ...
Also, though all topotests ALWAYS pass on my local machine each time I execute them, some of them still MIGHT fail on CI system. I feel like it's more like CI's problem but not my code. In case of encountering bugs in future development, just use DISABLE_EPOLL to identify whether bugs are caused by epoll version libfrr.
This pull request has conflicts, please resolve those before we can evaluate the pull request.
I'm deleting all CI comments on this thread because I can't find where any of the human comments are.
About format checking, the error implies line 2645 below has indent problem:
However in current upstream master branch, the corresponding code got no difference (line 1732):
Confused about this...
Format problem solved. I "segmented" the do while loop into several parts with pre-compile conditions.
This pull request has conflicts, please resolve those before we can evaluate the pull request.
Hello, reviewers @eqvinox @qlyoung, Recently we are using FRRouting for routing system emulation as mentioned in this issue, and still observing high cpu usage of ppoll system call when the scale of emulated network is large:
This PR has been opened for 9 months and seems to be a little bit slow in terms of progressing. But I think it will help a lot for FRR to be used in more scenarios, such as network emulation, if we could continue with this PR to optimize the polling method. I'd really appreciate it if you could review the code soon.
This PR has been opened for 9 months and seems to be a little bit slow in terms of progressing.
Sorry about that. I am one of the people familiar with the event internals, but FRR is no longer my full time job, so I have limited time to review, and for a long time had github emails completely muted so I did not see this PR. Everyone else is very busy handling things their employers pay them to do, or working on things that interest them, so sometimes important PRs like this one slip through the cracks. I will try to help drive this one through.