Skip to contentSkip to conversation

net: sched: add Flow Queue PIE packet scheduler

PATCH Superseded [email protected] 4 participants 6 messages Jan 17, 2020 – Jan 20, 2020

Subsystems (3)

v4 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
#0 lore raw

v4 cover net: sched: add Flow Queue PIE packet scheduler

From: Gautam Ramakrishnan <[email protected]>

Flow Queue PIE packet scheduler

This patch series implements the Flow Queue Proportional Integral controller Enhanced (FQ-PIE) active queue Management algorithm. It is an enhancement over the PIE algorithm. It integrates the PIE aqm with a deficit round robin scheme.

FQ-PIE is implemented over the latest version of PIE which uses timestamps to calculate queue delay with an additional option of using average dequeue rate to calculate the queue delay. This patch also adds a memory limit of all the packets across all queues to a default value of 32Mb.

For more information:
https://tools.ietf.org/html/rfc8033

Changes from v3 to v4
- Used non deprecated version of nla_parse_nested
- Used SZ_32M macro
- Removed an unused variable
- Code cleanup
All suggested by Jakub and Toke.

Changes from v2 to v3
- Exported drop_early, pie_process_dequeue and calculate_probability functions from sch_pie as suggested by Stephen Hemminger.

Changes from v1 ( and RFC patch) to v2
- Added timestamp to calculate queue delay as recommended by Dave Taht
- Packet memory limit implemented as recommended by Toke.
- Added external classifier as recommended by Toke.
- Used NET_XMIT_CN instead of NET_XMIT_DROP as the return value in the fq_pie_qdisc_enqueue function.

Mohit P. Tahiliani (2):
net: sched: pie: refactor code
net: sched: add Flow Queue PIE packet scheduler

 include/net/pie.h              | 138 ++++++++
 include/uapi/linux/pkt_sched.h |  31 ++
 net/sched/Kconfig              |  13 +
 net/sched/Makefile             |   1 +
 net/sched/sch_fq_pie.c         | 559 +++++++++++++++++++++++++++++++++
 net/sched/sch_pie.c            | 302 +++++++-----------
 6 files changed, 854 insertions(+), 190 deletions(-)
 create mode 100644 include/net/pie.h
 create mode 100644 net/sched/sch_fq_pie.c
Signature · 1 line
2.17.1
#1 lore raw

PATCH v4 1/2 net: sched: pie: refactor code

From: "Mohit P. Tahiliani" <[email protected]>

This patch is a precursor for the addition of the Flow Queue Proportional Integral Controller Enhanced (FQ-PIE) qdisc. The patch removes structures and small inline functions common to both PIE and FQ-PIE and moves it to the header file include/net/pie.h. It also exports symbols from sch_pie.c that are to be reused in sch_fq_pie.c.

---
 include/net/pie.h   | 136 ++++++++++++++++++++
 net/sched/sch_pie.c | 302 ++++++++++++++++----------------------------
 2 files changed, 248 insertions(+), 190 deletions(-)
 create mode 100644 include/net/pie.h
include/net/pie.h new file +136 -0
new file mode 100644
index 000000000000..22bd680f4d37
@@ -0,0 +1,136 @@
+/* SPDX-License-Identifier: GPL-2.0-only */
+#ifndef __NET_SCHED_PIE_H
+#define __NET_SCHED_PIE_H
+
+#include <linux/ktime.h>
+#include <linux/skbuff.h>
+#include <linux/types.h>
+#include <net/inet_ecn.h>
+#include <net/pkt_sched.h>
+
+#define PIE_SCALE 8
+#define MAX_PROB U64_MAX
+#define DQCOUNT_INVALID -1
+#define DTIME_INVALID U64_MAX
+#define QUEUE_THRESHOLD (1 << 14)
+
+/**
+ * struct pie_params - contains pie parameters
+ * @target: target delay in pschedtime
+ * @tudpate: interval at which drop probability is calculated
+ * @limit: total number of packets that can be in the queue
+ * @alpha: parameter to control drop probability
+ * @beta: parameter to control drop probability
+ * @ecn: whether to enable ECN marking of packets
+ * @bytemode: whether to scale drop prob based on pkt size
+ * @dq_rate_estimator: whether to use little's law for qdelay calculation
+ */
+struct pie_params {
+	psched_time_t target;
+	u32 tupdate;
+	u32 limit;
+	u32 alpha;
+	u32 beta;
+	u8 ecn;
+	u8 bytemode;
+	u8 dq_rate_estimator;
+};
+
+/**
+ * struct pie_vars - contains pie variables
+ * @burst_time: burst time allowance
+ * @qdelay: current queue delay
+ * @qdelay_old: queue delay in previous qdelay calculation
+ * @dq_tstamp: last instance at which dq rate was calculated
+ * @prob: drop probability
+ * @dq_count: number of bytes dequeued in a measurement cycle
+ * @accu_prob: accumulated drop probability
+ * @avg_dq_rate: calculated average dq rate
+ * @qlen_old: queue length during previous qdelay calculation
+ * @accu_prob_overflow: whether accu_prob overflowed
+ */
+struct pie_vars {
+	psched_time_t burst_time;
+	psched_time_t qdelay;
+	psched_time_t qdelay_old;
+	psched_time_t dq_tstamp;
+	u64 prob;
+	u64 dq_count;
+	u64 accu_prob;
+	u32 avg_dq_rate;
+	u32 qlen_old;
+	u8 accu_prob_overflows;
+};
+
+/**
+ * struct pie_stats - contains pie stats
+ * @packets_in: total number of packets enqueued
+ * @dropped: packets dropped due to pie action
+ * @overlimit: packets dropped due to lack of space in queue
+ * @maxq: maximum queue size
+ * @ecn_mark: packets marked with ECN
+ */
+struct pie_stats {
+	u32 packets_in;
+	u32 dropped;
+	u32 overlimit;
+	u32 maxq;
+	u32 ecn_mark;
+};
+
+/**
+ * struct pie_skb_cb - contains private skb vars
+ * @enqueue_time: timestamp when the packet is enqueued
+ */
+struct pie_skb_cb {
+	psched_time_t enqueue_time;
+};
+
+static inline void pie_params_init(struct pie_params *params)
+{
+	params->target = PSCHED_NS2TICKS(15 * NSEC_PER_MSEC);	/* 15 ms */
+	params->tupdate = usecs_to_jiffies(15 * USEC_PER_MSEC);	/* 15 ms */
+	params->limit = 1000; /* in packets */
+	params->alpha = 2;
+	params->beta = 20;
+	params->ecn = false;
+	params->bytemode = false;
+	params->dq_rate_estimator = false;
+}
+
+static inline void pie_vars_init(struct pie_vars *vars)
+{
+	vars->burst_time = PSCHED_NS2TICKS(150 * NSEC_PER_MSEC); /* 150 ms */
+	vars->dq_count = DQCOUNT_INVALID;
+	vars->dq_tstamp = DTIME_INVALID;
+	vars->accu_prob = 0;
+	vars->avg_dq_rate = 0;
+	vars->accu_prob_overflows = 0;
+}
+
+static inline struct pie_skb_cb *get_pie_cb(const struct sk_buff *skb)
+{
+	qdisc_cb_private_validate(skb, sizeof(struct pie_skb_cb));
+	return (struct pie_skb_cb *)qdisc_skb_cb(skb)->data;
+}
+
+static inline psched_time_t pie_get_enqueue_time(const struct sk_buff *skb)
+{
+	return get_pie_cb(skb)->enqueue_time;
+}
+
+static inline void pie_set_enqueue_time(struct sk_buff *skb)
+{
+	get_pie_cb(skb)->enqueue_time = psched_get_time();
+}
+
+bool pie_drop_early(struct Qdisc *sch, struct pie_params *params,
+		    struct pie_vars *vars, u32 backlog, u32 packet_size);
+
+void pie_process_dequeue(struct sk_buff *skb, struct pie_params *params,
+			 struct pie_vars *vars, u32 backlog);
+
+void pie_calculate_probability(struct pie_params *params, struct pie_vars *vars,
+			       u32 backlog);
+
+#endif
net/sched/sch_pie.c +112 -190

508 lines not on this page · raw message

Signature · 1 line
2.17.1
#2 lore raw

Re: [PATCH net-next v4 1/2] net: sched: pie: refactor code

Quoted 7 lines · [email protected] writes:

From: "Mohit P. Tahiliani" <[email protected]>

This patch is a precursor for the addition of the Flow Queue Proportional Integral Controller Enhanced (FQ-PIE) qdisc. The patch removes structures and small inline functions common to both PIE and FQ-PIE and moves it to the header file include/net/pie.h. It also exports symbols from sch_pie.c that are to be reused in sch_fq_pie.c.

The way this is done means that sch_fq_pie.ko will end up with a module dependency on sch_pie.ko, right? I don't think we have any such dependencies already; not *necessarily* a blocker, but it does strike me as a bit odd. Stephen, is this what you had in mind?

-Toke

#3 lore raw

Re: [PATCH net-next v4 1/2] net: sched: pie: refactor code

Quoted 5 lines · Toke Høiland-Jørgensen
Quoted 2 lines · [email protected] writes:

From: "Mohit P. Tahiliani" <[email protected]>

Quoted 8 lines
Quoted 5 lines

This patch is a precursor for the addition of the Flow Queue Proportional Integral Controller Enhanced (FQ-PIE) qdisc. The patch removes structures and small inline functions common to both PIE and FQ-PIE and moves it to the header file include/net/pie.h. It also exports symbols from sch_pie.c that are to be reused in sch_fq_pie.c.

The way this is done means that sch_fq_pie.ko will end up with a module dependency on sch_pie.ko, right?

Yes, we did make sch_fq_pie.ko dependent on sch_pie.ko in this series. We thought of doing this when we started out, but later on decided to follow something similar to the codel - fq_codel implementation.

Quoted 3 lines

I don't think we have any such
dependencies already; not *necessarily* a blocker, but it does strike me as a bit odd.

Yes, no existing qdiscs have dependencies, except for sch_atm and sch_ingress.

Leslie

maintainer
#4 lore raw

Re: [PATCH net-next v4 1/2] net: sched: pie: refactor code

In reply to [email protected]

From: [email protected]
Date: Fri, 17 Jan 2020 15:39:20 +0530

Quoted 5 lines

This patch is a precursor for the addition of the Flow Queue Proportional Integral Controller Enhanced (FQ-PIE) qdisc. The patch removes structures and small inline functions common to both PIE and FQ-PIE and moves it to the header file include/net/pie.h. It also exports symbols from sch_pie.c that are to be reused in sch_fq_pie.c.

That's not all this patch is doing.

It's making coding style and indentation changes as well.

I also see it changing how values are tracked in local variables.

All of these things are separate logical commits.

#5 lore raw

PATCH v4 2/2 net: sched: add Flow Queue PIE packet scheduler

In reply to [email protected]

From: "Mohit P. Tahiliani" <[email protected]>

Principles:
- Packets are classified on flows.
- This is a Stochastic model (as we use a hash, several flows might be hashed to the same slot)
- Each flow has a PIE managed queue.
- Flows are linked onto two (Round Robin) lists,
so that new flows have priority on old ones.
- For a given flow, packets are not reordered.
- Drops during enqueue only.
- ECN capability is off by default.
- ECN threshold (if ECN is enabled) is at 10% by default.
- Uses timestamps to calculate queue delay by default.

Usage:
tc qdisc ... fq_pie [ limit PACKETS ] [ flows NUMBER ]
[ target TIME ] [ tupdate TIME ] [ alpha NUMBER ] [ beta NUMBER ] [ quantum BYTES ] [ memory_limit BYTES ] [ ecnprob PERCENTAGE ] [ [no]ecn ] [ [no]bytemode ] [ [no_]dq_rate_estimator ]

defaults:
limit: 10240 packets, flows: 1024
target: 15 ms, tupdate: 15 ms (in jiffies)
alpha: 1/8, beta : 5/4
quantum: device MTU, memory_limit: 32 Mb
ecnprob: 10%, ecn: off
bytemode: off, dq_rate_estimator: off

---
 include/net/pie.h              |   2 +
 include/uapi/linux/pkt_sched.h |  31 ++
 net/sched/Kconfig              |  13 +
 net/sched/Makefile             |   1 +
 net/sched/sch_fq_pie.c         | 559 +++++++++++++++++++++++++++++++++
 5 files changed, 606 insertions(+)
 create mode 100644 net/sched/sch_fq_pie.c
include/net/pie.h +2 -0
index 22bd680f4d37..18a58f455762 100644
@@ -81,9 +81,11 @@ struct pie_stats {
 /**
  * struct pie_skb_cb - contains private skb vars
  * @enqueue_time: timestamp when the packet is enqueued
+ * @mem_usage: size of the skb during enqueue
  */
 struct pie_skb_cb {
 	psched_time_t enqueue_time;
+	u32 mem_usage;
 };
 
 static inline void pie_params_init(struct pie_params *params)
include/uapi/linux/pkt_sched.h +31 -0
index bf5a5b1dfb0b..bbe791b24168 100644
@@ -971,6 +971,37 @@ struct tc_pie_xstats {
 	__u32 ecn_mark;			/* packets marked with ecn*/
 };
 
+/* FQ PIE */
+enum {
+	TCA_FQ_PIE_UNSPEC,
+	TCA_FQ_PIE_LIMIT,
+	TCA_FQ_PIE_FLOWS,
+	TCA_FQ_PIE_TARGET,
+	TCA_FQ_PIE_TUPDATE,
+	TCA_FQ_PIE_ALPHA,
+	TCA_FQ_PIE_BETA,
+	TCA_FQ_PIE_QUANTUM,
+	TCA_FQ_PIE_MEMORY_LIMIT,
+	TCA_FQ_PIE_ECN_PROB,
+	TCA_FQ_PIE_ECN,
+	TCA_FQ_PIE_BYTEMODE,
+	TCA_FQ_PIE_DQ_RATE_ESTIMATOR,
+	__TCA_FQ_PIE_MAX
+};
+#define TCA_FQ_PIE_MAX   (__TCA_FQ_PIE_MAX - 1)
+
+struct tc_fq_pie_xstats {
+	__u32 packets_in;	/* total number of packets enqueued */
+	__u32 dropped;		/* packets dropped due to fq_pie_action */
+	__u32 overlimit;	/* dropped due to lack of space in queue */
+	__u32 overmemory;	/* dropped due to lack of memory in queue */
+	__u32 ecn_mark;		/* packets marked with ecn */
+	__u32 new_flow_count;	/* count of new flows created by packets */
+	__u32 new_flows_len;	/* count of flows in new list */
+	__u32 old_flows_len;	/* count of flows in old list */
+	__u32 memory_usage;	/* total memory across all queues */
+};
+
 /* CBS */
 struct tc_cbs_qopt {
 	__u8 offload;
net/sched/Kconfig +13 -0
index b1e7ec726958..edde0e519438 100644
@@ -366,6 +366,19 @@ config NET_SCH_PIE
 
 	  If unsure, say N.
 
+config NET_SCH_FQ_PIE
+	depends on NET_SCH_PIE
+	tristate "Flow Queue Proportional Integral controller Enhanced (FQ-PIE)"
+	help
+	  Say Y here if you want to use the Flow Queue Proportional Integral
+	  controller Enhanced (FQ-PIE) packet scheduling algorithm.
+	  For more information, please see https://tools.ietf.org/html/rfc8033
+
+	  To compile this driver as a module, choose M here: the module
+	  will be called sch_fq_pie.
+
+	  If unsure, say N.
+
 config NET_SCH_INGRESS
 	tristate "Ingress/classifier-action Qdisc"
 	depends on NET_CLS_ACT
net/sched/Makefile +1 -0
index bc8856b865ff..31c367a6cd09 100644
@@ -59,6 +59,7 @@ obj-$(CONFIG_NET_SCH_CAKE)	+= sch_cake.o
 obj-$(CONFIG_NET_SCH_FQ)	+= sch_fq.o
 obj-$(CONFIG_NET_SCH_HHF)	+= sch_hhf.o
 obj-$(CONFIG_NET_SCH_PIE)	+= sch_pie.o
+obj-$(CONFIG_NET_SCH_FQ_PIE)	+= sch_fq_pie.o
 obj-$(CONFIG_NET_SCH_CBS)	+= sch_cbs.o
 obj-$(CONFIG_NET_SCH_ETF)	+= sch_etf.o
 obj-$(CONFIG_NET_SCH_TAPRIO)	+= sch_taprio.o
net/sched/sch_fq_pie.c new file +559 -0

559 lines not on this page · raw message

Signature · 1 line
2.17.1