Skip to contentSkip to conversation

netfilter: ipvs: Divide estimators into groups

RFC PATCH In review Jiri Wiesner 2 participants 4 messages Aug 12, 2022 – Aug 25, 2022

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 netfilter: ipvs: Divide estimators into groups

The calculation of rate estimates for IPVS services and destinations will cause an increase in scheduling latency to hundreds of milliseconds when the number of estimators reaches tens of thousands or more. This issue has been reported upstream [1]. Design changes to the algorithm to compute the estimates were proposed in the same email thread.

By implementing some of the proposed design changes, this patch seeks to address the latency issue by dividing the estimators into groups for which estimates are calculated in a 2-second interval (same as before). Each of the groups is processed once in each 2-second interval. Instead of allocating an array of lists, groups are identified by their group_id, which has the advantage that estimators can stay in the same list to which they have been added by ip_vs_start_estimator(). The implementation of estimator grouping is able to scale up with an increasing number of estimators as well as scale down when estimators are being removed.
The changes to group size can be monitored with dynamic debugging:
echo 'file net/netfilter/ipvs/ip_vs_est.c +pfl' >> /sys/kernel/debug/dynamic_debug/control

Rebalacing of estimator groups is implemented and can be triggered only after all the calculations for a 2-second interval have finished. After a limit is exceeded, adding or removing estimators will triger rebalacing, which will cause estimates to be inaccurate in the next 2-second interval. For example, removing estimators that results in the removal of an entire group will shorten the time interval used for computing rates, which will lead to the rates being underestimated in the next 2-second interval.

Testing was carried out on a 2-socket machine with Intel Xeon Gold 6326 CPUs (64 logical CPUs). Tests with up to 600,000 estimators were successfully completed. The expectation is that, given the current default limits, the implementation can handle 150,000 estimators on most machines in use today. In a test with 100,000 estimators, the default group size of 1024 estimators resulted in the processing time for one group to be circa 2.3 milliseconds and a timer period of 5 jiffies. Despite estimators being added or removed throughout most of the test, the overhead of ip_vs_estimator_rebalance() was less than 10% of the overhead of
estimation_timer():

     7.66%        124093  swapper          [kernel.kallsyms]         [k] intel_idle
     2.86%         14296  ipvsadm          [kernel.kallsyms]         [k] native_queued_spin_lock_slowpath
     2.64%         16827  ipvsadm          [kernel.kallsyms]         [k] ip_vs_genl_parse_service
     2.15%         18457  ipvsadm          libc-2.31.so              [.] _dl_addr
     2.08%          4562  ipvsadm          [kernel.kallsyms]         [k] ip_vs_genl_dump_services
     2.06%         18326  ipvsadm          ld-2.31.so                [.] do_lookup_x
     1.78%         17251  swapper          [kernel.kallsyms]         [k] estimation_timer

...
0.14% 855 swapper [kernel.kallsyms] [k] ip_vs_estimator_rebalance

The intention is to develop this RFC patch into a short series addressing the design changes proposed in [1]. Also, after moving the rate estimation out of softirq context, the whole estimator list could be processed concurrently - more than one work item would be used.

[1] https://lore.kernel.org/netdev/[email protected]

---
 include/net/ip_vs.h            |  15 ++++
 net/netfilter/ipvs/ip_vs_est.c | 132 +++++++++++++++++++++++++++++++--
 2 files changed, 140 insertions(+), 7 deletions(-)
include/net/ip_vs.h +15 -0
index ff1804a0c469..386d3cca1fc4 100644
@@ -349,6 +349,14 @@ struct ip_vs_seq {
 						 * before last resized pkt */
 };
 
+#define	IP_VS_EST_GROUP_SIZE		1024u
+#define	IP_VS_EST_MIN_GROUP_SIZE	64u
+#define	IP_VS_EST_TIME_INTERVAL		(2 * HZ)
+/* This limit comes from MAX_SOFTIRQ_TIME - it should not be longer */
+#define	IP_VS_EST_MAX_TIME		msecs_to_jiffies(2)
+#define	IP_VS_EST_MIN_PERIOD		(IP_VS_EST_MAX_TIME + 1)
+#define	IP_VS_EST_NORM_PERIOD		(4 * IP_VS_EST_MIN_PERIOD)
+
 /* counters per cpu */
 struct ip_vs_counters {
 	__u64		conns;		/* connections scheduled */
@@ -366,6 +374,7 @@ struct ip_vs_cpu_stats {
 /* IPVS statistics objects */
 struct ip_vs_estimator {
 	struct list_head	list;
+	int			group_id;
 
 	u64			last_inbytes;
 	u64			last_outbytes;
@@ -943,6 +952,12 @@ struct netns_ipvs {
 	struct ctl_table	*lblcr_ctl_table;
 	/* ip_vs_est */
 	struct list_head	est_list;	/* estimator list */
+	struct list_head	*est_next;
+	unsigned		est_group_size;
+	unsigned		est_min_grp_size;
+	unsigned		est_period;
+	unsigned		est_last_period;
+	unsigned		est_num_changed;
 	spinlock_t		est_lock;
 	struct timer_list	est_timer;	/* Estimation timer */
 	/* ip_vs_sync */
net/netfilter/ipvs/ip_vs_est.c +125 -7

180 lines not on this page · raw message

Signature · 1 line
2.35.3
maintainer
#1 lore raw

Hello,

Quoted 46 lines · Jiri Wiesner

The calculation of rate estimates for IPVS services and destinations will cause an increase in scheduling latency to hundreds of milliseconds when the number of estimators reaches tens of thousands or more. This issue has been reported upstream [1]. Design changes to the algorithm to compute the estimates were proposed in the same email thread.

By implementing some of the proposed design changes, this patch seeks to address the latency issue by dividing the estimators into groups for which estimates are calculated in a 2-second interval (same as before). Each of the groups is processed once in each 2-second interval. Instead of allocating an array of lists, groups are identified by their group_id, which has the advantage that estimators can stay in the same list to which they have been added by ip_vs_start_estimator(). The implementation of estimator grouping is able to scale up with an increasing number of estimators as well as scale down when estimators are being removed.
The changes to group size can be monitored with dynamic debugging:
echo 'file net/netfilter/ipvs/ip_vs_est.c +pfl' >> /sys/kernel/debug/dynamic_debug/control

Rebalacing of estimator groups is implemented and can be triggered only after all the calculations for a 2-second interval have finished. After a limit is exceeded, adding or removing estimators will triger rebalacing, which will cause estimates to be inaccurate in the next 2-second interval. For example, removing estimators that results in the removal of an entire group will shorten the time interval used for computing rates, which will lead to the rates being underestimated in the next 2-second interval.

Testing was carried out on a 2-socket machine with Intel Xeon Gold 6326 CPUs (64 logical CPUs). Tests with up to 600,000 estimators were successfully completed. The expectation is that, given the current default limits, the implementation can handle 150,000 estimators on most machines in use today. In a test with 100,000 estimators, the default group size of 1024 estimators resulted in the processing time for one group to be circa 2.3 milliseconds and a timer period of 5 jiffies. Despite estimators being added or removed throughout most of the test, the overhead of ip_vs_estimator_rebalance() was less than 10% of the overhead of
estimation_timer():

     7.66%        124093  swapper          [kernel.kallsyms]         [k] intel_idle
     2.86%         14296  ipvsadm          [kernel.kallsyms]         [k] native_queued_spin_lock_slowpath
     2.64%         16827  ipvsadm          [kernel.kallsyms]         [k] ip_vs_genl_parse_service
     2.15%         18457  ipvsadm          libc-2.31.so              [.] _dl_addr
     2.08%          4562  ipvsadm          [kernel.kallsyms]         [k] ip_vs_genl_dump_services
     2.06%         18326  ipvsadm          ld-2.31.so                [.] do_lookup_x
     1.78%         17251  swapper          [kernel.kallsyms]         [k] estimation_timer

...
0.14% 855 swapper [kernel.kallsyms] [k] ip_vs_estimator_rebalance

Quoted 8 lines

The intention is to develop this RFC patch into a short series addressing the design changes proposed in [1]. Also, after moving the rate estimation out of softirq context, the whole estimator list could be processed concurrently - more than one work item would be used.

[1] https://lore.kernel.org/netdev/[email protected]

Other developers tried solutions with workqueues
but so far we don't see any results. Give me some days, may be I can come up with solution that uses kthread(s) to allow later nice/cpumask cfg tuning and to avoid overload of the system workqueues.

Regards

--
Julian Anastasov <[email protected]>

#2 lore raw
Quoted 10 lines · Julian Anastasov
Quoted 4 lines

The intention is to develop this RFC patch into a short series addressing the design changes proposed in [1]. Also, after moving the rate estimation out of softirq context, the whole estimator list could be processed concurrently - more than one work item would be used.

Other developers tried solutions with workqueues
but so far we don't see any results. Give me some days, may be I can come up with solution that uses kthread(s) to allow later nice/cpumask cfg tuning and to avoid overload of the system workqueues.

The RFC patch already resolves the issue despite having the code still run in softirq context. Even if estimators were processed in groups, moving the rate estimation out of softirq context is a good idea. I am interested in implementing this. An alternative approach would be moving the rate estimation out of softirq context and reworking locking so that cond_resched() could be used to let other processes run as the scheduler sees fit. I would be willing to try to implement this alternative approach as well. Jiri Wiesner
SUSE Labs

maintainer
#3 lore raw

Hello,

Quoted 6 lines · Jiri Wiesner
Quoted 5 lines · Julian Anastasov
Quoted 4 lines

The intention is to develop this RFC patch into a short series addressing the design changes proposed in [1]. Also, after moving the rate estimation out of softirq context, the whole estimator list could be processed concurrently - more than one work item would be used.

Quoted 7 lines
Quoted 5 lines

Other developers tried solutions with workqueues
but so far we don't see any results. Give me some days, may be I can come up with solution that uses kthread(s) to allow later nice/cpumask cfg tuning and to avoid overload of the system workqueues.

The RFC patch already resolves the issue despite having the code still run in softirq context. Even if estimators were processed in groups, moving the rate estimation out of softirq context is a good idea. I am interested in implementing this. An alternative approach would be moving the rate estimation out of softirq context and reworking locking so that cond_resched() could be used to let other processes run as the scheduler sees fit. I would be willing to try to implement this alternative approach as well.

I started reworking the estimation code. I think,
I'll have results in few days. I'm using kthreads, the locking is ready, just finishing the cpumask/nice configuration and will do simple tests. When a RFC patch is ready we can comment what should be the final version.

Regards

--
Julian Anastasov <[email protected]>