[PATCH 0/3] sched: patches for 2.2

[PATCH 0/3] sched: patches for 2.2

[Stephen Hemminger]

This is the last round of sched updates for 2.2. It is based
on code changes (extensively) tested by QA and used in the vRouter.

Stephen Hemminger (3):
  rte_sched: keep track of RED drops
  rte_sched: introduce reciprocal divide
  rte_sched: eliminate floating point in calculating byte clock

 lib/librte_sched/Makefile         |  6 ++--
 lib/librte_sched/rte_reciprocal.c | 72 +++++++++++++++++++++++++++++++++++++++
 lib/librte_sched/rte_reciprocal.h | 39 +++++++++++++++++++++
 lib/librte_sched/rte_sched.c      | 43 ++++++++++++++++++-----
 lib/librte_sched/rte_sched.h      |  8 +++++
 5 files changed, 157 insertions(+), 11 deletions(-)
 create mode 100644 lib/librte_sched/rte_reciprocal.c
 create mode 100644 lib/librte_sched/rte_reciprocal.h

-- 
2.1.4

[PATCH 1/3] rte_sched: keep track of RED drops

[Stephen Hemminger]

Add new statistic to keep track of drops due to RED.

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
 lib/librte_sched/rte_sched.c | 20 ++++++++++++++++----
 lib/librte_sched/rte_sched.h |  8 ++++++++
 2 files changed, 24 insertions(+), 4 deletions(-)

diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
index d47cfc2..16acd6b 100644
--- a/lib/librte_sched/rte_sched.c
+++ b/lib/librte_sched/rte_sched.c
@@ -1071,7 +1071,9 @@ rte_sched_port_update_subport_stats(struct rte_sched_port *port, uint32_t qindex
 }
 
 static inline void
-rte_sched_port_update_subport_stats_on_drop(struct rte_sched_port *port, uint32_t qindex, struct rte_mbuf *pkt)
+rte_sched_port_update_subport_stats_on_drop(struct rte_sched_port *port,
+					    uint32_t qindex,
+					    struct rte_mbuf *pkt, uint32_t red)
 {
 	struct rte_sched_subport *s = port->subport + (qindex / rte_sched_port_queues_per_subport(port));
 	uint32_t tc_index = (qindex >> 2) & 0x3;
@@ -1079,6 +1081,9 @@ rte_sched_port_update_subport_stats_on_drop(struct rte_sched_port *port, uint32_
 
 	s->stats.n_pkts_tc_dropped[tc_index] += 1;
 	s->stats.n_bytes_tc_dropped[tc_index] += pkt_len;
+#ifdef RTE_SCHED_RED
+	s->stats.n_pkts_red_dropped[tc_index] += red;
+#endif
 }
 
 static inline void
@@ -1092,13 +1097,18 @@ rte_sched_port_update_queue_stats(struct rte_sched_port *port, uint32_t qindex,
 }
 
 static inline void
-rte_sched_port_update_queue_stats_on_drop(struct rte_sched_port *port, uint32_t qindex, struct rte_mbuf *pkt)
+rte_sched_port_update_queue_stats_on_drop(struct rte_sched_port *port,
+					  uint32_t qindex,
+					  struct rte_mbuf *pkt, uint32_t red)
 {
 	struct rte_sched_queue_extra *qe = port->queue_extra + qindex;
 	uint32_t pkt_len = pkt->pkt_len;
 
 	qe->stats.n_pkts_dropped += 1;
 	qe->stats.n_bytes_dropped += pkt_len;
+#ifdef RTE_SCHED_RED
+	qe->stats.n_pkts_red_dropped += red;
+#endif
 }
 
 #endif /* RTE_SCHED_COLLECT_STATS */
@@ -1229,8 +1239,10 @@ rte_sched_port_enqueue_qwa(struct rte_sched_port *port, uint32_t qindex,
 		     (qlen >= qsize))) {
 		rte_pktmbuf_free(pkt);
 #ifdef RTE_SCHED_COLLECT_STATS
-		rte_sched_port_update_subport_stats_on_drop(port, qindex, pkt);
-		rte_sched_port_update_queue_stats_on_drop(port, qindex, pkt);
+		rte_sched_port_update_subport_stats_on_drop(port, qindex, pkt,
+							    qlen < qsize);
+		rte_sched_port_update_queue_stats_on_drop(port, qindex, pkt,
+							  qlen < qsize);
 #endif
 		return 0;
 	}
diff --git a/lib/librte_sched/rte_sched.h b/lib/librte_sched/rte_sched.h
index c0f4ad3..e9c2817 100644
--- a/lib/librte_sched/rte_sched.h
+++ b/lib/librte_sched/rte_sched.h
@@ -162,6 +162,11 @@ struct rte_sched_subport_stats {
 	/**< Number of bytes successfully written for each traffic class */
 	uint32_t n_bytes_tc_dropped[RTE_SCHED_TRAFFIC_CLASSES_PER_PIPE];
 	/**< Number of bytes dropped for each traffic class */
+
+#ifdef RTE_SCHED_RED
+	uint32_t n_pkts_red_dropped[RTE_SCHED_TRAFFIC_CLASSES_PER_PIPE];
+	/**< Number of packets dropped by red */
+#endif
 };
 
 /*
@@ -196,6 +201,9 @@ struct rte_sched_queue_stats {
 	/* Packets */
 	uint32_t n_pkts;                 /**< Packets successfully written */
 	uint32_t n_pkts_dropped;         /**< Packets dropped */
+#ifdef RTE_SCHED_RED
+	uint32_t n_pkts_red_dropped;	 /**< Packets dropped by RED */
+#endif
 
 	/* Bytes */
 	uint32_t n_bytes;                /**< Bytes successfully written */
-- 
2.1.4

[PATCH 2/3] rte_sched: introduce reciprocal divide

[Stephen Hemminger]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=yes, Size: 5368 bytes --]

This adds (with permission of the original author)
reciprocal divide based on algorithm in Linux.

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
---
 lib/librte_sched/Makefile         |  6 ++--
 lib/librte_sched/rte_reciprocal.c | 72 +++++++++++++++++++++++++++++++++++++++
 lib/librte_sched/rte_reciprocal.h | 39 +++++++++++++++++++++
 3 files changed, 115 insertions(+), 2 deletions(-)
 create mode 100644 lib/librte_sched/rte_reciprocal.c
 create mode 100644 lib/librte_sched/rte_reciprocal.h

diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
index b1cb285..e0a2c6d 100644
--- a/lib/librte_sched/Makefile
+++ b/lib/librte_sched/Makefile
@@ -48,10 +48,12 @@ LIBABIVER := 1
 #
 # all source are stored in SRCS-y
 #
-SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c
+SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c \
+	rte_reciprocal.c
 
 # install includes
-SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h rte_bitmap.h \
+	rte_sched_common.h rte_red.h rte_approx.h rte_reciprocal.h
 
 # this lib depends upon:
 DEPDIRS-$(CONFIG_RTE_LIBRTE_SCHED) += lib/librte_mempool lib/librte_mbuf
diff --git a/lib/librte_sched/rte_reciprocal.c b/lib/librte_sched/rte_reciprocal.c
new file mode 100644
index 0000000..652f023
--- /dev/null
+++ b/lib/librte_sched/rte_reciprocal.c
@@ -0,0 +1,72 @@
+/*-
+ *   BSD LICENSE
+ *
+ *   Copyright(c) Hannes Frederic Sowa
+ *   All rights reserved.
+ *
+ *   Redistribution and use in source and binary forms, with or without
+ *   modification, are permitted provided that the following conditions
+ *   are met:
+ *
+ *     * Redistributions of source code must retain the above copyright
+ *       notice, this list of conditions and the following disclaimer.
+ *     * Redistributions in binary form must reproduce the above copyright
+ *       notice, this list of conditions and the following disclaimer in
+ *       the documentation and/or other materials provided with the
+ *       distribution.
+ *     * Neither the name of Intel Corporation nor the names of its
+ *       contributors may be used to endorse or promote products derived
+ *       from this software without specific prior written permission.
+ *
+ *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+
+#include <rte_common.h>
+
+#include "rte_reciprocal.h"
+
+/* find largest set bit.
+ * portable and slow but does not matter for this usage.
+ */
+static inline int fls(uint32_t x)
+{
+	int b;
+
+	for (b = 31; b >= 0; --b) {
+		if (x & (1u << b))
+			return b + 1;
+	}
+
+	return 0;
+}
+
+struct rte_reciprocal rte_reciprocal_value(uint32_t d)
+{
+	struct rte_reciprocal R;
+	uint64_t m;
+	int l;
+
+	l = fls(d - 1);
+	m = ((1ULL << 32) * ((1ULL << l) - d));
+	m /= d;
+
+	++m;
+	R.m = m;
+	R.sh1 = RTE_MIN(l, 1);
+	R.sh2 = RTE_MAX(l - 1, 0);
+
+	return R;
+}
diff --git a/lib/librte_sched/rte_reciprocal.h b/lib/librte_sched/rte_reciprocal.h
new file mode 100644
index 0000000..abd1525
--- /dev/null
+++ b/lib/librte_sched/rte_reciprocal.h
@@ -0,0 +1,39 @@
+/*
+ * Reciprocal divide
+ *
+ * Used with permission from original authors
+ *  Hannes Frederic Sowa and Daniel Borkmann
+ *
+ * This algorithm is based on the paper "Division by Invariant
+ * Integers Using Multiplication" by Torbjörn Granlund and Peter
+ * L. Montgomery.
+ *
+ * The assembler implementation from Agner Fog, which this code is
+ * based on, can be found here:
+ * http://www.agner.org/optimize/asmlib.zip
+ *
+ * This optimization for A/B is helpful if the divisor B is mostly
+ * runtime invariant. The reciprocal of B is calculated in the
+ * slow-path with reciprocal_value(). The fast-path can then just use
+ * a much faster multiplication operation with a variable dividend A
+ * to calculate the division A/B.
+ */
+
+#ifndef _RTE_RECIPROCAL_H_
+#define _RTE_RECIPROCAL_H_
+
+struct rte_reciprocal {
+	uint32_t m;
+	uint8_t sh1, sh2;
+};
+
+static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal R)
+{
+	uint32_t t = (uint32_t)(((uint64_t)a * R.m) >> 32);
+
+	return (t + ((a - t) >> R.sh1)) >> R.sh2;
+}
+
+struct rte_reciprocal rte_reciprocal_value(uint32_t d);
+
+#endif /* _RTE_RECIPROCAL_H_ */
-- 
2.1.4

[PATCH 3/3] rte_sched: eliminate floating point in calculating byte clock

[Stephen Hemminger]

The old code was doing a floating point divide for each rte_dequeue()
which is very expensive. Change to using fixed point scaled inverse
multiply. To maintain equivalent precision, scaled math is used.
The application ABI is the same.

This improved performance from 5Gbit/sec to 10 Gbit/sec when configured
for 10 Gbit/sec rate.

There was some feedback from Cristian that he wanted a better
solution and was going to give one, but none was provided.
For 2.2 this is a better solution than existing code, if someone
has a better version I would love to see it.

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
 lib/librte_sched/rte_sched.c | 23 ++++++++++++++++++-----
 1 file changed, 18 insertions(+), 5 deletions(-)

diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
index 16acd6b..cfae136 100644
--- a/lib/librte_sched/rte_sched.c
+++ b/lib/librte_sched/rte_sched.c
@@ -47,6 +47,7 @@
 #include "rte_bitmap.h"
 #include "rte_sched_common.h"
 #include "rte_approx.h"
+#include "rte_reciprocal.h"
 
 #ifdef __INTEL_COMPILER
 #pragma warning(disable:2259) /* conversion may lose significant bits */
@@ -62,6 +63,11 @@
 #define RTE_SCHED_PIPE_INVALID                UINT32_MAX
 #define RTE_SCHED_BMP_POS_INVALID             UINT32_MAX
 
+/* Scaling for cycles_per_byte calculation
+ * Chosen so that minimum rate is 480 bit/sec
+ */
+#define RTE_SCHED_TIME_SHIFT		      8
+
 struct rte_sched_subport {
 	/* Token bucket (TB) */
 	uint64_t tb_time; /* time of last update */
@@ -215,7 +221,7 @@ struct rte_sched_port {
 	uint64_t time_cpu_cycles;     /* Current CPU time measured in CPU cyles */
 	uint64_t time_cpu_bytes;      /* Current CPU time measured in bytes */
 	uint64_t time;                /* Current NIC TX time measured in bytes */
-	double cycles_per_byte;       /* CPU cycles per byte */
+	struct rte_reciprocal inv_cycles_per_byte; /* CPU cycles per byte */
 
 	/* Scheduling loop detection */
 	uint32_t pipe_loop;
@@ -610,7 +616,7 @@ struct rte_sched_port *
 rte_sched_port_config(struct rte_sched_port_params *params)
 {
 	struct rte_sched_port *port = NULL;
-	uint32_t mem_size, bmp_mem_size, n_queues_per_port, i;
+	uint32_t mem_size, bmp_mem_size, n_queues_per_port, i, cycles_per_byte;
 
 	/* Check user parameters. Determine the amount of memory to allocate */
 	mem_size = rte_sched_port_get_memory_footprint(params);
@@ -661,7 +667,10 @@ rte_sched_port_config(struct rte_sched_port_params *params)
 	port->time_cpu_cycles = rte_get_tsc_cycles();
 	port->time_cpu_bytes = 0;
 	port->time = 0;
-	port->cycles_per_byte = ((double) rte_get_tsc_hz()) / ((double) params->rate);
+
+	cycles_per_byte = (rte_get_tsc_hz() << RTE_SCHED_TIME_SHIFT)
+		/ params->rate;
+	port->inv_cycles_per_byte = rte_reciprocal_value(cycles_per_byte);
 
 	/* Scheduling loop detection */
 	port->pipe_loop = RTE_SCHED_PIPE_INVALID;
@@ -2088,11 +2097,15 @@ rte_sched_port_time_resync(struct rte_sched_port *port)
 {
 	uint64_t cycles = rte_get_tsc_cycles();
 	uint64_t cycles_diff = cycles - port->time_cpu_cycles;
-	double bytes_diff = ((double) cycles_diff) / port->cycles_per_byte;
+	uint64_t bytes_diff;
+
+	/* Compute elapsed time in bytes */
+	bytes_diff = rte_reciprocal_divide(cycles_diff << RTE_SCHED_TIME_SHIFT,
+					   port->inv_cycles_per_byte);
 
 	/* Advance port time */
 	port->time_cpu_cycles = cycles;
-	port->time_cpu_bytes += (uint64_t) bytes_diff;
+	port->time_cpu_bytes += bytes_diff;
 	if (port->time < port->time_cpu_bytes)
 		port->time = port->time_cpu_bytes;
 
-- 
2.1.4

Re: [PATCH 1/3] rte_sched: keep track of RED drops

[Thomas Monjalon]

2015-11-29 10:46, Stephen Hemminger:
> Add new statistic to keep track of drops due to RED.
> 
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> ---
>  lib/librte_sched/rte_sched.c | 20 ++++++++++++++++----
>  lib/librte_sched/rte_sched.h |  8 ++++++++
>  2 files changed, 24 insertions(+), 4 deletions(-)

You should update doc/guides/rel_notes/deprecation.rst at the same time
to remove the related deprecation notice.
Thanks

[PATCH] rte_sched: drop deprecation notice for RED statistics

[Stephen Hemminger]

The RED statistics are now added.

Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
---
 doc/guides/rel_notes/deprecation.rst | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/doc/guides/rel_notes/deprecation.rst b/doc/guides/rel_notes/deprecation.rst
index 1c7ab01..deed679 100644
--- a/doc/guides/rel_notes/deprecation.rst
+++ b/doc/guides/rel_notes/deprecation.rst
@@ -12,9 +12,6 @@ Deprecation Notices
   ibadcrc, ibadlen, imcasts, fdirmatch, fdirmiss,
   tx_pause_xon, rx_pause_xon, tx_pause_xoff, rx_pause_xoff
 
-* The scheduler statistics structure will change to allow keeping track of
-  RED actions.
-
 * librte_pipeline: The prototype for the pipeline input port, output port
   and table action handlers will be updated:
   the pipeline parameter will be added, the packets mask parameter will be
-- 
2.1.4

Re: [PATCH 2/3] rte_sched: introduce reciprocal divide

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Sunday, November 29, 2015 8:47 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: dev@dpdk.org; Stephen Hemminger <stephen@networkplumber.org>;
> Hannes Frederic Sowa <hannes@stressinduktion.org>
> Subject: [PATCH 2/3] rte_sched: introduce reciprocal divide
> 
> This adds (with permission of the original author)
> reciprocal divide based on algorithm in Linux.
> 
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
> ---
>  lib/librte_sched/Makefile         |  6 ++--
>  lib/librte_sched/rte_reciprocal.c | 72
> +++++++++++++++++++++++++++++++++++++++
>  lib/librte_sched/rte_reciprocal.h | 39 +++++++++++++++++++++
>  3 files changed, 115 insertions(+), 2 deletions(-)
>  create mode 100644 lib/librte_sched/rte_reciprocal.c
>  create mode 100644 lib/librte_sched/rte_reciprocal.h
> 
> diff --git a/lib/librte_sched/Makefile b/lib/librte_sched/Makefile
> index b1cb285..e0a2c6d 100644
> --- a/lib/librte_sched/Makefile
> +++ b/lib/librte_sched/Makefile
> @@ -48,10 +48,12 @@ LIBABIVER := 1
>  #
>  # all source are stored in SRCS-y
>  #
> -SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c rte_approx.c
> +SRCS-$(CONFIG_RTE_LIBRTE_SCHED) += rte_sched.c rte_red.c
> rte_approx.c \
> +	rte_reciprocal.c
> 
>  # install includes
> -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> rte_bitmap.h rte_sched_common.h rte_red.h rte_approx.h
> +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include := rte_sched.h
> rte_bitmap.h \
> +	rte_sched_common.h rte_red.h rte_approx.h rte_reciprocal.h
> 
>  # this lib depends upon:
>  DEPDIRS-$(CONFIG_RTE_LIBRTE_SCHED) += lib/librte_mempool
> lib/librte_mbuf
> diff --git a/lib/librte_sched/rte_reciprocal.c
> b/lib/librte_sched/rte_reciprocal.c
> new file mode 100644
> index 0000000..652f023
> --- /dev/null
> +++ b/lib/librte_sched/rte_reciprocal.c
> @@ -0,0 +1,72 @@
> +/*-
> + *   BSD LICENSE
> + *
> + *   Copyright(c) Hannes Frederic Sowa
> + *   All rights reserved.
> + *
> + *   Redistribution and use in source and binary forms, with or without
> + *   modification, are permitted provided that the following conditions
> + *   are met:
> + *
> + *     * Redistributions of source code must retain the above copyright
> + *       notice, this list of conditions and the following disclaimer.
> + *     * Redistributions in binary form must reproduce the above copyright
> + *       notice, this list of conditions and the following disclaimer in
> + *       the documentation and/or other materials provided with the
> + *       distribution.
> + *     * Neither the name of Intel Corporation nor the names of its

Why is Intel mentioned here, as according to this license header Intel is not the copyright holder?

> + *       contributors may be used to endorse or promote products derived
> + *       from this software without specific prior written permission.
> + *
> + *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
> CONTRIBUTORS
> + *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT
> NOT
> + *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
> FITNESS FOR
> + *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
> COPYRIGHT
> + *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
> INCIDENTAL,
> + *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
> NOT
> + *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
> OF USE,
> + *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
> AND ON ANY
> + *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
> TORT
> + *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF
> THE USE
> + *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
> DAMAGE.
> + */
> +
> +#include <stdio.h>
> +#include <stdint.h>
> +
> +#include <rte_common.h>
> +
> +#include "rte_reciprocal.h"
> +
> +/* find largest set bit.
> + * portable and slow but does not matter for this usage.
> + */
> +static inline int fls(uint32_t x)
> +{
> +	int b;
> +
> +	for (b = 31; b >= 0; --b) {
> +		if (x & (1u << b))
> +			return b + 1;
> +	}
> +
> +	return 0;
> +}
> +
> +struct rte_reciprocal rte_reciprocal_value(uint32_t d)
> +{
> +	struct rte_reciprocal R;
> +	uint64_t m;
> +	int l;
> +
> +	l = fls(d - 1);
> +	m = ((1ULL << 32) * ((1ULL << l) - d));
> +	m /= d;
> +
> +	++m;
> +	R.m = m;
> +	R.sh1 = RTE_MIN(l, 1);
> +	R.sh2 = RTE_MAX(l - 1, 0);
> +
> +	return R;
> +}
> diff --git a/lib/librte_sched/rte_reciprocal.h
> b/lib/librte_sched/rte_reciprocal.h
> new file mode 100644
> index 0000000..abd1525
> --- /dev/null
> +++ b/lib/librte_sched/rte_reciprocal.h
> @@ -0,0 +1,39 @@
> +/*
> + * Reciprocal divide
> + *
> + * Used with permission from original authors
> + *  Hannes Frederic Sowa and Daniel Borkmann
> + *
> + * This algorithm is based on the paper "Division by Invariant
> + * Integers Using Multiplication" by Torbjörn Granlund and Peter
> + * L. Montgomery.

Stephen, can you please provide a link to this paper?

> + *
> + * The assembler implementation from Agner Fog, which this code is
> + * based on, can be found here:
> + * http://www.agner.org/optimize/asmlib.zip
> + *
> + * This optimization for A/B is helpful if the divisor B is mostly
> + * runtime invariant. The reciprocal of B is calculated in the
> + * slow-path with reciprocal_value(). The fast-path can then just use
> + * a much faster multiplication operation with a variable dividend A
> + * to calculate the division A/B.
> + */
> +
> +#ifndef _RTE_RECIPROCAL_H_
> +#define _RTE_RECIPROCAL_H_
> +
> +struct rte_reciprocal {
> +	uint32_t m;
> +	uint8_t sh1, sh2;
> +};

The size of this structure is not a multiple of 32 bits. You seem to transfer this structure by value rather than by reference (the function rte_reciprocal_value() below returns an instance of this structure), I don't feel comfortable with the last 16 bits of the structure being left uninitialized, we should probably add some explicit pad field and initialize this structure explicitly to zero at init time?

> +
> +static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal
> R)
> +{
> +	uint32_t t = (uint32_t)(((uint64_t)a * R.m) >> 32);
> +
> +	return (t + ((a - t) >> R.sh1)) >> R.sh2;
> +}
> +
> +struct rte_reciprocal rte_reciprocal_value(uint32_t d);

Why 32-bit arithmetic? We had a lot of bugs in librte_sched library due to 32-bit arithmetic that were particularly difficult to track. Can we have this function rte_reciprocal_divide() return a 64-bit integer and replace any 32-bit arithmetic/conversion with 64-bit operations?

> +
> +#endif /* _RTE_RECIPROCAL_H_ */
> --
> 2.1.4

As previously discussed, a simpler/faster alternative to floating point division is 64-bit multiplication followed by right shift, any particular reason why this approach was not considered?

Re: [PATCH 3/3] rte_sched: eliminate floating point in calculating byte clock

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Sunday, November 29, 2015 8:47 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: dev@dpdk.org; Stephen Hemminger <stephen@networkplumber.org>
> Subject: [PATCH 3/3] rte_sched: eliminate floating point in calculating byte
> clock
> 
> The old code was doing a floating point divide for each rte_dequeue()
> which is very expensive. Change to using fixed point scaled inverse
> multiply. To maintain equivalent precision, scaled math is used.
> The application ABI is the same.
> 
> This improved performance from 5Gbit/sec to 10 Gbit/sec when configured
> for 10 Gbit/sec rate.
> 
> There was some feedback from Cristian that he wanted a better
> solution and was going to give one, but none was provided.
> For 2.2 this is a better solution than existing code, if someone
> has a better version I would love to see it.
> 
> Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> ---
>  lib/librte_sched/rte_sched.c | 23 ++++++++++++++++++-----
>  1 file changed, 18 insertions(+), 5 deletions(-)
> 
> diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
> index 16acd6b..cfae136 100644
> --- a/lib/librte_sched/rte_sched.c
> +++ b/lib/librte_sched/rte_sched.c
> @@ -47,6 +47,7 @@
>  #include "rte_bitmap.h"
>  #include "rte_sched_common.h"
>  #include "rte_approx.h"
> +#include "rte_reciprocal.h"
> 
>  #ifdef __INTEL_COMPILER
>  #pragma warning(disable:2259) /* conversion may lose significant bits */
> @@ -62,6 +63,11 @@
>  #define RTE_SCHED_PIPE_INVALID                UINT32_MAX
>  #define RTE_SCHED_BMP_POS_INVALID             UINT32_MAX
> 
> +/* Scaling for cycles_per_byte calculation
> + * Chosen so that minimum rate is 480 bit/sec
> + */
> +#define RTE_SCHED_TIME_SHIFT		      8

Stephen, can you please elaborate why we need to shift the dividend at all and why the shift value was picked as 8? Is 8 a hard constraint? How does this affect the scheduling precision/accuracy?

> +
>  struct rte_sched_subport {
>  	/* Token bucket (TB) */
>  	uint64_t tb_time; /* time of last update */
> @@ -215,7 +221,7 @@ struct rte_sched_port {
>  	uint64_t time_cpu_cycles;     /* Current CPU time measured in CPU
> cyles */
>  	uint64_t time_cpu_bytes;      /* Current CPU time measured in bytes
> */
>  	uint64_t time;                /* Current NIC TX time measured in bytes */
> -	double cycles_per_byte;       /* CPU cycles per byte */
> +	struct rte_reciprocal inv_cycles_per_byte; /* CPU cycles per byte */
> 
>  	/* Scheduling loop detection */
>  	uint32_t pipe_loop;
> @@ -610,7 +616,7 @@ struct rte_sched_port *
>  rte_sched_port_config(struct rte_sched_port_params *params)
>  {
>  	struct rte_sched_port *port = NULL;
> -	uint32_t mem_size, bmp_mem_size, n_queues_per_port, i;
> +	uint32_t mem_size, bmp_mem_size, n_queues_per_port, i,
> cycles_per_byte;
> 
>  	/* Check user parameters. Determine the amount of memory to
> allocate */
>  	mem_size = rte_sched_port_get_memory_footprint(params);
> @@ -661,7 +667,10 @@ rte_sched_port_config(struct
> rte_sched_port_params *params)
>  	port->time_cpu_cycles = rte_get_tsc_cycles();
>  	port->time_cpu_bytes = 0;
>  	port->time = 0;
> -	port->cycles_per_byte = ((double) rte_get_tsc_hz()) / ((double)
> params->rate);
> +
> +	cycles_per_byte = (rte_get_tsc_hz() << RTE_SCHED_TIME_SHIFT)
> +		/ params->rate;
> +	port->inv_cycles_per_byte = rte_reciprocal_value(cycles_per_byte);
> 
>  	/* Scheduling loop detection */
>  	port->pipe_loop = RTE_SCHED_PIPE_INVALID;
> @@ -2088,11 +2097,15 @@ rte_sched_port_time_resync(struct
> rte_sched_port *port)
>  {
>  	uint64_t cycles = rte_get_tsc_cycles();
>  	uint64_t cycles_diff = cycles - port->time_cpu_cycles;
> -	double bytes_diff = ((double) cycles_diff) / port->cycles_per_byte;
> +	uint64_t bytes_diff;
> +
> +	/* Compute elapsed time in bytes */
> +	bytes_diff = rte_reciprocal_divide(cycles_diff <<
> RTE_SCHED_TIME_SHIFT,
> +					   port->inv_cycles_per_byte);
> 
>  	/* Advance port time */
>  	port->time_cpu_cycles = cycles;
> -	port->time_cpu_bytes += (uint64_t) bytes_diff;
> +	port->time_cpu_bytes += bytes_diff;
>  	if (port->time < port->time_cpu_bytes)
>  		port->time = port->time_cpu_bytes;
> 
> --
> 2.1.4

Can you provide some insight into how you tested this code and the test vectors you used?

Re: [PATCH 2/3] rte_sched: introduce reciprocal divide

[Hannes Frederic Sowa]

Hello,

On Wed, Dec 2, 2015, at 17:45, Dumitrescu, Cristian wrote:
> > diff --git a/lib/librte_sched/rte_reciprocal.h
> > b/lib/librte_sched/rte_reciprocal.h
> > new file mode 100644
> > index 0000000..abd1525
> > --- /dev/null
> > +++ b/lib/librte_sched/rte_reciprocal.h
> > @@ -0,0 +1,39 @@
> > +/*
> > + * Reciprocal divide
> > + *
> > + * Used with permission from original authors
> > + *  Hannes Frederic Sowa and Daniel Borkmann
> > + *
> > + * This algorithm is based on the paper "Division by Invariant
> > + * Integers Using Multiplication" by Torbjörn Granlund and Peter
> > + * L. Montgomery.
> 
> Stephen, can you please provide a link to this paper?

<https://gmplib.org/~tege/divcnst-pldi94.pdf>

> > + *
> > + * The assembler implementation from Agner Fog, which this code is
> > + * based on, can be found here:
> > + * http://www.agner.org/optimize/asmlib.zip
> > + *
> > + * This optimization for A/B is helpful if the divisor B is mostly
> > + * runtime invariant. The reciprocal of B is calculated in the
> > + * slow-path with reciprocal_value(). The fast-path can then just use
> > + * a much faster multiplication operation with a variable dividend A
> > + * to calculate the division A/B.
> > + */
> > +
> > +#ifndef _RTE_RECIPROCAL_H_
> > +#define _RTE_RECIPROCAL_H_
> > +
> > +struct rte_reciprocal {
> > +	uint32_t m;
> > +	uint8_t sh1, sh2;
> > +};
> 
> The size of this structure is not a multiple of 32 bits. You seem to
> transfer this structure by value rather than by reference (the function
> rte_reciprocal_value() below returns an instance of this structure), I
> don't feel comfortable with the last 16 bits of the structure being left
> uninitialized, we should probably add some explicit pad field and
> initialize this structure explicitly to zero at init time?

Note, it is used by static inline functions in fast path which most
probably expands the code in question, thus no real argument passing
happens (at least this is what I saw in the linux kernel assembly). I
don't think you need to worry about padding. It happens very often
without noticing. ;)

> > +
> > +static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal
> > R)
> > +{
> > +	uint32_t t = (uint32_t)(((uint64_t)a * R.m) >> 32);
> > +
> > +	return (t + ((a - t) >> R.sh1)) >> R.sh2;
> > +}
> > +
> > +struct rte_reciprocal rte_reciprocal_value(uint32_t d);
> 
> Why 32-bit arithmetic? We had a lot of bugs in librte_sched library due
> to 32-bit arithmetic that were particularly difficult to track. Can we
> have this function rte_reciprocal_divide() return a 64-bit integer and
> replace any 32-bit arithmetic/conversion with 64-bit operations?

There was no use case at this time and I am actually not sure how easy
the move to 64 bit is, as it would require one multiplication operation
in an integer domain twice as large.

> > +
> > +#endif /* _RTE_RECIPROCAL_H_ */
> > --
> > 2.1.4
> 
> As previously discussed, a simpler/faster alternative to floating point
> division is 64-bit multiplication followed by right shift, any particular
> reason why this approach was not considered?

This is exact division. It depends on what you want. I am not sure if
you want to do array accesses with floating point division or simple 64
bit multiplication and shifting.

Bye,
Hannes

Re: [PATCH 2/3] rte_sched: introduce reciprocal divide

[Stephen Hemminger]

On Wed, 2 Dec 2015 16:45:01 +0000
"Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> + *     * Neither the name of Intel Corporation nor the names of its
> 
> Why is Intel mentioned here, as according to this license header Intel is not the copyright holder?

Copy/paste from other code.


> > +#ifndef _RTE_RECIPROCAL_H_
> > +#define _RTE_RECIPROCAL_H_
> > +
> > +struct rte_reciprocal {
> > +	uint32_t m;
> > +	uint8_t sh1, sh2;
> > +};
> 
> The size of this structure is not a multiple of 32 bits. You seem to transfer this structure by value rather than by reference (the function rte_reciprocal_value() below returns an instance of this structure), I don't feel comfortable with the last 16 bits of the structure being left uninitialized, we should probably add some explicit pad field and initialize this structure explicitly to zero at init time?

Shouldn't matter for inline at all.

> 
> > +
> > +static inline uint32_t rte_reciprocal_divide(uint32_t a, struct rte_reciprocal
> > R)
> > +{
> > +	uint32_t t = (uint32_t)(((uint64_t)a * R.m) >> 32);
> > +
> > +	return (t + ((a - t) >> R.sh1)) >> R.sh2;
> > +}
> > +
> > +struct rte_reciprocal rte_reciprocal_value(uint32_t d);
> 
> Why 32-bit arithmetic? We had a lot of bugs in librte_sched library due to 32-bit arithmetic that were particularly difficult to track. Can we have this function rte_reciprocal_divide() return a 64-bit integer and replace any 32-bit arithmetic/conversion with 64-bit operations?

Doing reciprocal divide by multiply requires a 2x temporary. So if it
used 64 bit math, it would require a 128 bit multiply. 


> > +
> > +#endif /* _RTE_RECIPROCAL_H_ */
> > --
> > 2.1.4
> 
> As previously discussed, a simpler/faster alternative to floating point division is 64-bit multiplication followed by right shift, any particular reason why this approach was not considered?

That is what this is. It is a 64 bit multiply (a * R.m) followed by a right shift.
The only other stuff is related to round off and scaling.

I chose to use known working algorithm rather than writing and having to
do mathematical validation of any new code.

Re: [PATCH 3/3] rte_sched: eliminate floating point in calculating byte clock

[Stephen Hemminger]

On Wed, 2 Dec 2015 16:48:17 +0000
"Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:

> 
> 
> > -----Original Message-----
> > From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> > Sent: Sunday, November 29, 2015 8:47 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Cc: dev@dpdk.org; Stephen Hemminger <stephen@networkplumber.org>
> > Subject: [PATCH 3/3] rte_sched: eliminate floating point in calculating byte
> > clock
> > 
> > The old code was doing a floating point divide for each rte_dequeue()
> > which is very expensive. Change to using fixed point scaled inverse
> > multiply. To maintain equivalent precision, scaled math is used.
> > The application ABI is the same.
> > 
> > This improved performance from 5Gbit/sec to 10 Gbit/sec when configured
> > for 10 Gbit/sec rate.
> > 
> > There was some feedback from Cristian that he wanted a better
> > solution and was going to give one, but none was provided.
> > For 2.2 this is a better solution than existing code, if someone
> > has a better version I would love to see it.
> > 
> > Signed-off-by: Stephen Hemminger <stephen@networkplumber.org>
> > ---
> >  lib/librte_sched/rte_sched.c | 23 ++++++++++++++++++-----
> >  1 file changed, 18 insertions(+), 5 deletions(-)
> > 
> > diff --git a/lib/librte_sched/rte_sched.c b/lib/librte_sched/rte_sched.c
> > index 16acd6b..cfae136 100644
> > --- a/lib/librte_sched/rte_sched.c
> > +++ b/lib/librte_sched/rte_sched.c
> > @@ -47,6 +47,7 @@
> >  #include "rte_bitmap.h"
> >  #include "rte_sched_common.h"
> >  #include "rte_approx.h"
> > +#include "rte_reciprocal.h"
> > 
> >  #ifdef __INTEL_COMPILER
> >  #pragma warning(disable:2259) /* conversion may lose significant bits */
> > @@ -62,6 +63,11 @@
> >  #define RTE_SCHED_PIPE_INVALID                UINT32_MAX
> >  #define RTE_SCHED_BMP_POS_INVALID             UINT32_MAX
> > 
> > +/* Scaling for cycles_per_byte calculation
> > + * Chosen so that minimum rate is 480 bit/sec
> > + */
> > +#define RTE_SCHED_TIME_SHIFT		      8
> 
> Stephen, can you please elaborate why we need to shift the dividend at all and why the shift value was picked as 8? Is 8 a hard constraint? How does this affect the scheduling precision/accuracy?

The shift value is a tradeoff for scaled math. The bigger the shift
the finer the resolution, but at the risk of overflow in the cycles_per_byte.
The value was chosen as a tradeoff based on current CPU clock rate (TSC)
and minimum rate.

> > +
> >  struct rte_sched_subport {
> >  	/* Token bucket (TB) */
> >  	uint64_t tb_time; /* time of last update */
> > @@ -215,7 +221,7 @@ struct rte_sched_port {
> >  	uint64_t time_cpu_cycles;     /* Current CPU time measured in CPU
> > cyles */
> >  	uint64_t time_cpu_bytes;      /* Current CPU time measured in bytes
> > */
> >  	uint64_t time;                /* Current NIC TX time measured in bytes */
> > -	double cycles_per_byte;       /* CPU cycles per byte */
> > +	struct rte_reciprocal inv_cycles_per_byte; /* CPU cycles per byte */
> > 
> >  	/* Scheduling loop detection */
> >  	uint32_t pipe_loop;
> > @@ -610,7 +616,7 @@ struct rte_sched_port *
> >  rte_sched_port_config(struct rte_sched_port_params *params)
> >  {
> >  	struct rte_sched_port *port = NULL;
> > -	uint32_t mem_size, bmp_mem_size, n_queues_per_port, i;
> > +	uint32_t mem_size, bmp_mem_size, n_queues_per_port, i,
> > cycles_per_byte;
> > 
> >  	/* Check user parameters. Determine the amount of memory to
> > allocate */
> >  	mem_size = rte_sched_port_get_memory_footprint(params);
> > @@ -661,7 +667,10 @@ rte_sched_port_config(struct
> > rte_sched_port_params *params)
> >  	port->time_cpu_cycles = rte_get_tsc_cycles();
> >  	port->time_cpu_bytes = 0;
> >  	port->time = 0;
> > -	port->cycles_per_byte = ((double) rte_get_tsc_hz()) / ((double)
> > params->rate);
> > +
> > +	cycles_per_byte = (rte_get_tsc_hz() << RTE_SCHED_TIME_SHIFT)
> > +		/ params->rate;
> > +	port->inv_cycles_per_byte = rte_reciprocal_value(cycles_per_byte);
> > 
> >  	/* Scheduling loop detection */
> >  	port->pipe_loop = RTE_SCHED_PIPE_INVALID;
> > @@ -2088,11 +2097,15 @@ rte_sched_port_time_resync(struct
> > rte_sched_port *port)
> >  {
> >  	uint64_t cycles = rte_get_tsc_cycles();
> >  	uint64_t cycles_diff = cycles - port->time_cpu_cycles;
> > -	double bytes_diff = ((double) cycles_diff) / port->cycles_per_byte;
> > +	uint64_t bytes_diff;
> > +
> > +	/* Compute elapsed time in bytes */
> > +	bytes_diff = rte_reciprocal_divide(cycles_diff <<
> > RTE_SCHED_TIME_SHIFT,
> > +					   port->inv_cycles_per_byte);
> > 
> >  	/* Advance port time */
> >  	port->time_cpu_cycles = cycles;
> > -	port->time_cpu_bytes += (uint64_t) bytes_diff;
> > +	port->time_cpu_bytes += bytes_diff;
> >  	if (port->time < port->time_cpu_bytes)
> >  		port->time = port->time_cpu_bytes;
> > 
> > --
> > 2.1.4
> 
> Can you provide some insight into how you tested this code and the test vectors you used?

We tested with 10 gbit link and range of rates from 10k bit up to 10 gbit.

Re: [PATCH 0/3] sched: patches for 2.2

[Thomas Monjalon]

2015-11-29 10:46, Stephen Hemminger:
> This is the last round of sched updates for 2.2. It is based
> on code changes (extensively) tested by QA and used in the vRouter.
> 
> Stephen Hemminger (3):
>   rte_sched: keep track of RED drops
>   rte_sched: introduce reciprocal divide
>   rte_sched: eliminate floating point in calculating byte clock

Cristian, what is the status of this series, please?

Re: [PATCH 0/3] sched: patches for 2.2

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Thomas Monjalon [mailto:thomas.monjalon@6wind.com]
> Sent: Friday, March 4, 2016 3:01 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: dev@dpdk.org; Stephen Hemminger <stephen@networkplumber.org>
> Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> 
> 2015-11-29 10:46, Stephen Hemminger:
> > This is the last round of sched updates for 2.2. It is based
> > on code changes (extensively) tested by QA and used in the vRouter.
> >
> > Stephen Hemminger (3):
> >   rte_sched: keep track of RED drops
> >   rte_sched: introduce reciprocal divide
> >   rte_sched: eliminate floating point in calculating byte clock
> 
> Cristian, what is the status of this series, please?

We are working on implementing an alternative solution based on 2x 64-bit multiplication, which is supported by CPUs and compilers for more than a decade now. The 32-bit solution proposed by Stephen requires truncation with some loss of precision, which can potentially lead to some corner cases which are difficult to predict, therefore I am not feeling 100% confident with it. The 32-bit arithmetic gave me a lot of headaches when developing QoS code, therefore I am very cautious of it.

I am not sure we are able to finalize implementation and testing for release 16.4, therefore it would be fair to accept Stephen's solution for release 16.4 and consider the new safer 2x 64-bit multiplication solution which does not involve any loss of precision once it becomes available.

Regarding Stephen's patches, I think there is a pending issue regarding the legal side of the Copyright, which is attributed to Intel, although Stephen's code is relicensed with BSD license by permission from the original code author (which also submitted the code to Linux kernel under GPL). This was already flagged. This is a legal issue and I do not feel comfortable with ack-ing this patch until the legal resolution on this is crystal clear.

I also think the new files called rte_reciprocal.[hc] implement an algorithm that is very generic and totally independent of the QoS code, therefore it should be placed into a different folder that is globally visible to other libraries (librte_eal/common ?) just in case other usages for this algorithm are identified in the future. I suggest we break the patch into two separate patches submitted independently: one introducing the rte_reciprocal.[hc] algorithm to librte_eal/common and the second containing just the librte_sched changes, which are small. I am thinking ahead here: once we have the 2x64-bit multiplication solution in place, we should not have rte_reciprocal.[hc] hanging in librte_sched folder without being used here, while it might be used by other parts of DPDK.

Thanks,
Cristian

Re: [PATCH 0/3] sched: patches for 2.2

[Stephen Hemminger]

On Tue, 8 Mar 2016 07:49:20 +0000
"Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:

> Regarding Stephen's patches, I think there is a pending issue regarding the legal side of the Copyright, which is attributed to Intel, although Stephen's code is relicensed with BSD license by permission from the original code author (which also submitted the code to Linux kernel under GPL). This was already flagged. This is a legal issue and I do not feel comfortable with ack-ing this patch until the legal resolution on this is crystal clear.


I got explicit permission from the author who holds the copyright to relicense it.

Re: [PATCH 0/3] sched: patches for 2.2

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Tuesday, March 8, 2016 4:33 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> 
> On Tue, 8 Mar 2016 07:49:20 +0000
> "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> 
> > Regarding Stephen's patches, I think there is a pending issue regarding the
> legal side of the Copyright, which is attributed to Intel, although Stephen's
> code is relicensed with BSD license by permission from the original code
> author (which also submitted the code to Linux kernel under GPL). This was
> already flagged. This is a legal issue and I do not feel comfortable with ack-ing
> this patch until the legal resolution on this is crystal clear.
> 
> 
> I got explicit permission from the author who holds the copyright to relicense
> it.

Did you get explicit permission from the author who holds the copyright to relicense it with BSD license that hands over the copyright to Intel?

Re: [PATCH 0/3] sched: patches for 2.2

[Stephen Hemminger]

On Tue, 8 Mar 2016 19:53:01 +0000
"Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:

> 
> 
> > -----Original Message-----
> > From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> > Sent: Tuesday, March 8, 2016 4:33 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
> > Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> > 
> > On Tue, 8 Mar 2016 07:49:20 +0000
> > "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> > 
> > > Regarding Stephen's patches, I think there is a pending issue regarding the
> > legal side of the Copyright, which is attributed to Intel, although Stephen's
> > code is relicensed with BSD license by permission from the original code
> > author (which also submitted the code to Linux kernel under GPL). This was
> > already flagged. This is a legal issue and I do not feel comfortable with ack-ing
> > this patch until the legal resolution on this is crystal clear.
> > 
> > 
> > I got explicit permission from the author who holds the copyright to relicense
> > it.
> 
> Did you get explicit permission from the author who holds the copyright to relicense it with BSD license that hands over the copyright to Intel?

I got explicit permission to relicense as BSD.


I believe DPDK does not require copyright assignment, and this is a standalone file.


On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> The kernel implementation of reciprocal divide is GPL licensed.
> Is there any chance of getting a BSD license version to allow using
> it in the DPDK?  

I absolutely don't have a problem to give my ack to make this
dual-license. Where do I need to sign? ;)

Bye,
Hannes

>> On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:  
>>> The kernel implementation of reciprocal divide is GPL licensed.
>>> Is there any chance of getting a BSD license version to allow using
>>> it in the DPDK?  
>>
>> I absolutely don't have a problem to give my ack to make this
>> dual-license. Where do I need to sign? ;)  

I have absolutely no problem with that. Feel free to add my
Signed-off-by to your DPDK submission.

Merry X-Mas & thanks for asking!

Daniel

Re: [PATCH 0/3] sched: patches for 2.2

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> Sent: Tuesday, March 8, 2016 8:41 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> 
> On Tue, 8 Mar 2016 19:53:01 +0000
> "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> 
> >
> >
> > > -----Original Message-----
> > > From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> > > Sent: Tuesday, March 8, 2016 4:33 PM
> > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
> > > Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> > >
> > > On Tue, 8 Mar 2016 07:49:20 +0000
> > > "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> > >
> > > > Regarding Stephen's patches, I think there is a pending issue regarding
> the
> > > legal side of the Copyright, which is attributed to Intel, although
> Stephen's
> > > code is relicensed with BSD license by permission from the original code
> > > author (which also submitted the code to Linux kernel under GPL). This
> was
> > > already flagged. This is a legal issue and I do not feel comfortable with
> ack-ing
> > > this patch until the legal resolution on this is crystal clear.
> > >
> > >
> > > I got explicit permission from the author who holds the copyright to
> relicense
> > > it.
> >
> > Did you get explicit permission from the author who holds the copyright to
> relicense it with BSD license that hands over the copyright to Intel?
> 
> I got explicit permission to relicense as BSD.
> 
> 
> I believe DPDK does not require copyright assignment, and this is a
> standalone file.
> 

Yes, I understand that you got permission from the author to relicense as BSD. What I am not sure of is whether it is OK to assign the copyright to Intel, maybe other people can comment on this as well.

As explained above, rte_reciprocal.[hc] is a standalone algorithm that is independent of librte_sched code. It can useful to any piece of code requiring division on data plane side, including any DPDK library or app, even those not using librte_sched library, therefor it really does not belong to librte_sched. My proposal is:
1. Please submit patch series 1 with rte_reciprocal.[hc] as new files to be added to librte_eal/common.
2. Please submit patch series 2 containing just changes to librte_sched, which are small.

Are you OK with this approach?

Thanks,
Cristian


> 
> On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> > The kernel implementation of reciprocal divide is GPL licensed.
> > Is there any chance of getting a BSD license version to allow using
> > it in the DPDK?
> 
> I absolutely don't have a problem to give my ack to make this
> dual-license. Where do I need to sign? ;)
> 
> Bye,
> Hannes
> 
> >> On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> >>> The kernel implementation of reciprocal divide is GPL licensed.
> >>> Is there any chance of getting a BSD license version to allow using
> >>> it in the DPDK?
> >>
> >> I absolutely don't have a problem to give my ack to make this
> >> dual-license. Where do I need to sign? ;)
> 
> I have absolutely no problem with that. Feel free to add my
> Signed-off-by to your DPDK submission.
> 
> Merry X-Mas & thanks for asking!
> 
> Daniel

Re: [PATCH 0/3] sched: patches for 2.2

[Stephen Hemminger]

Why does this need to be reassigned to Intel. That is not how the DPDK
works.
Please leave the original copyright holders on the file.

On Thu, Mar 10, 2016 at 10:41 AM, Dumitrescu, Cristian <
cristian.dumitrescu@intel.com> wrote:

>
>
> > -----Original Message-----
> > From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> > Sent: Tuesday, March 8, 2016 8:41 PM
> > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
> > Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> >
> > On Tue, 8 Mar 2016 19:53:01 +0000
> > "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> >
> > >
> > >
> > > > -----Original Message-----
> > > > From: Stephen Hemminger [mailto:stephen@networkplumber.org]
> > > > Sent: Tuesday, March 8, 2016 4:33 PM
> > > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
> > > > Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
> > > > Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> > > >
> > > > On Tue, 8 Mar 2016 07:49:20 +0000
> > > > "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com> wrote:
> > > >
> > > > > Regarding Stephen's patches, I think there is a pending issue
> regarding
> > the
> > > > legal side of the Copyright, which is attributed to Intel, although
> > Stephen's
> > > > code is relicensed with BSD license by permission from the original
> code
> > > > author (which also submitted the code to Linux kernel under GPL).
> This
> > was
> > > > already flagged. This is a legal issue and I do not feel comfortable
> with
> > ack-ing
> > > > this patch until the legal resolution on this is crystal clear.
> > > >
> > > >
> > > > I got explicit permission from the author who holds the copyright to
> > relicense
> > > > it.
> > >
> > > Did you get explicit permission from the author who holds the
> copyright to
> > relicense it with BSD license that hands over the copyright to Intel?
> >
> > I got explicit permission to relicense as BSD.
> >
> >
> > I believe DPDK does not require copyright assignment, and this is a
> > standalone file.
> >
>
> Yes, I understand that you got permission from the author to relicense as
> BSD. What I am not sure of is whether it is OK to assign the copyright to
> Intel, maybe other people can comment on this as well.
>
> As explained above, rte_reciprocal.[hc] is a standalone algorithm that is
> independent of librte_sched code. It can useful to any piece of code
> requiring division on data plane side, including any DPDK library or app,
> even those not using librte_sched library, therefor it really does not
> belong to librte_sched. My proposal is:
> 1. Please submit patch series 1 with rte_reciprocal.[hc] as new files to
> be added to librte_eal/common.
> 2. Please submit patch series 2 containing just changes to librte_sched,
> which are small.
>
> Are you OK with this approach?
>
> Thanks,
> Cristian
>
>
> >
> > On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> > > The kernel implementation of reciprocal divide is GPL licensed.
> > > Is there any chance of getting a BSD license version to allow using
> > > it in the DPDK?
> >
> > I absolutely don't have a problem to give my ack to make this
> > dual-license. Where do I need to sign? ;)
> >
> > Bye,
> > Hannes
> >
> > >> On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> > >>> The kernel implementation of reciprocal divide is GPL licensed.
> > >>> Is there any chance of getting a BSD license version to allow using
> > >>> it in the DPDK?
> > >>
> > >> I absolutely don't have a problem to give my ack to make this
> > >> dual-license. Where do I need to sign? ;)
> >
> > I have absolutely no problem with that. Feel free to add my
> > Signed-off-by to your DPDK submission.
> >
> > Merry X-Mas & thanks for asking!
> >
> > Daniel
>

Re: [PATCH 0/3] sched: patches for 2.2

[Dumitrescu, Cristian]

From: Stephen Hemminger [mailto:stephen@networkplumber.org]
Sent: Thursday, March 10, 2016 6:44 PM
To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>
Cc: Thomas Monjalon <thomas.monjalon@6wind.com>; dev@dpdk.org
Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2

Why does this need to be reassigned to Intel. That is not how the DPDK works.
Please leave the original copyright holders on the file.

I think you misunderstood my statement. My question is: why is Intel mentioned at all in the copyright header of rte_reciprocal.c in your initial patch submission (http://www.dpdk.org/ml/archives/dev/2015-November/029025.html)?

On Thu, Mar 10, 2016 at 10:41 AM, Dumitrescu, Cristian <cristian.dumitrescu@intel.com<mailto:cristian.dumitrescu@intel.com>> wrote:


> -----Original Message-----
> From: Stephen Hemminger [mailto:stephen@networkplumber.org<mailto:stephen@networkplumber.org>]
> Sent: Tuesday, March 8, 2016 8:41 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com<mailto:cristian.dumitrescu@intel.com>>
> Cc: Thomas Monjalon <thomas.monjalon@6wind.com<mailto:thomas.monjalon@6wind.com>>; dev@dpdk.org<mailto:dev@dpdk.org>
> Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
>
> On Tue, 8 Mar 2016 19:53:01 +0000
> "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com<mailto:cristian.dumitrescu@intel.com>> wrote:
>
> >
> >
> > > -----Original Message-----
> > > From: Stephen Hemminger [mailto:stephen@networkplumber.org<mailto:stephen@networkplumber.org>]
> > > Sent: Tuesday, March 8, 2016 4:33 PM
> > > To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com<mailto:cristian.dumitrescu@intel.com>>
> > > Cc: Thomas Monjalon <thomas.monjalon@6wind.com<mailto:thomas.monjalon@6wind.com>>; dev@dpdk.org<mailto:dev@dpdk.org>
> > > Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> > >
> > > On Tue, 8 Mar 2016 07:49:20 +0000
> > > "Dumitrescu, Cristian" <cristian.dumitrescu@intel.com<mailto:cristian.dumitrescu@intel.com>> wrote:
> > >
> > > > Regarding Stephen's patches, I think there is a pending issue regarding
> the
> > > legal side of the Copyright, which is attributed to Intel, although
> Stephen's
> > > code is relicensed with BSD license by permission from the original code
> > > author (which also submitted the code to Linux kernel under GPL). This
> was
> > > already flagged. This is a legal issue and I do not feel comfortable with
> ack-ing
> > > this patch until the legal resolution on this is crystal clear.
> > >
> > >
> > > I got explicit permission from the author who holds the copyright to
> relicense
> > > it.
> >
> > Did you get explicit permission from the author who holds the copyright to
> relicense it with BSD license that hands over the copyright to Intel?
>
> I got explicit permission to relicense as BSD.
>
>
> I believe DPDK does not require copyright assignment, and this is a
> standalone file.
>
Yes, I understand that you got permission from the author to relicense as BSD. What I am not sure of is whether it is OK to assign the copyright to Intel, maybe other people can comment on this as well.

As explained above, rte_reciprocal.[hc] is a standalone algorithm that is independent of librte_sched code. It can useful to any piece of code requiring division on data plane side, including any DPDK library or app, even those not using librte_sched library, therefor it really does not belong to librte_sched. My proposal is:
1. Please submit patch series 1 with rte_reciprocal.[hc] as new files to be added to librte_eal/common.
2. Please submit patch series 2 containing just changes to librte_sched, which are small.

Are you OK with this approach?

Thanks,
Cristian


>
> On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> > The kernel implementation of reciprocal divide is GPL licensed.
> > Is there any chance of getting a BSD license version to allow using
> > it in the DPDK?
>
> I absolutely don't have a problem to give my ack to make this
> dual-license. Where do I need to sign? ;)
>
> Bye,
> Hannes
>
> >> On Sat, Dec 20, 2014, at 01:24, Stephen Hemminger wrote:
> >>> The kernel implementation of reciprocal divide is GPL licensed.
> >>> Is there any chance of getting a BSD license version to allow using
> >>> it in the DPDK?
> >>
> >> I absolutely don't have a problem to give my ack to make this
> >> dual-license. Where do I need to sign? ;)
>
> I have absolutely no problem with that. Feel free to add my
> Signed-off-by to your DPDK submission.
>
> Merry X-Mas & thanks for asking!
>
> Daniel

Re: [PATCH 0/3] sched: patches for 2.2

[Thomas Monjalon]

2016-03-08 07:49, Dumitrescu, Cristian:
> We are working on implementing an alternative solution based on 2x 64-bit multiplication, which is supported by CPUs and compilers for more than a decade now. The 32-bit solution proposed by Stephen requires truncation with some loss of precision, which can potentially lead to some corner cases which are difficult to predict, therefore I am not feeling 100% confident with it. The 32-bit arithmetic gave me a lot of headaches when developing QoS code, therefore I am very cautious of it.
> 
> I am not sure we are able to finalize implementation and testing for release 16.4, therefore it would be fair to accept Stephen's solution for release 16.4 and consider the new safer 2x 64-bit multiplication solution which does not involve any loss of precision once it becomes available.
> 
> Regarding Stephen's patches, I think there is a pending issue regarding the legal side of the Copyright, which is attributed to Intel, although Stephen's code is relicensed with BSD license by permission from the original code author (which also submitted the code to Linux kernel under GPL). This was already flagged. This is a legal issue and I do not feel comfortable with ack-ing this patch until the legal resolution on this is crystal clear.
> 
> I also think the new files called rte_reciprocal.[hc] implement an algorithm that is very generic and totally independent of the QoS code, therefore it should be placed into a different folder that is globally visible to other libraries (librte_eal/common ?) just in case other usages for this algorithm are identified in the future. I suggest we break the patch into two separate patches submitted independently: one introducing the rte_reciprocal.[hc] algorithm to librte_eal/common and the second containing just the librte_sched changes, which are small. I am thinking ahead here: once we have the 2x64-bit multiplication solution in place, we should not have rte_reciprocal.[hc] hanging in librte_sched folder without being used here, while it might be used by other parts of DPDK.

Let's keep the improvement as-is to test it in the first release candidate.
We can move the code and/or fix the file header later.

Series applied, thanks.

Re: [PATCH 0/3] sched: patches for 2.2

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Thomas Monjalon [mailto:thomas.monjalon@6wind.com]
> Sent: Sunday, March 13, 2016 10:26 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Stephen
> Hemminger <stephen@networkplumber.org>
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> 
> 2016-03-08 07:49, Dumitrescu, Cristian:
> > We are working on implementing an alternative solution based on 2x 64-bit
> multiplication, which is supported by CPUs and compilers for more than a
> decade now. The 32-bit solution proposed by Stephen requires truncation
> with some loss of precision, which can potentially lead to some corner cases
> which are difficult to predict, therefore I am not feeling 100% confident with
> it. The 32-bit arithmetic gave me a lot of headaches when developing QoS
> code, therefore I am very cautious of it.
> >
> > I am not sure we are able to finalize implementation and testing for release
> 16.4, therefore it would be fair to accept Stephen's solution for release 16.4
> and consider the new safer 2x 64-bit multiplication solution which does not
> involve any loss of precision once it becomes available.
> >
> > Regarding Stephen's patches, I think there is a pending issue regarding the
> legal side of the Copyright, which is attributed to Intel, although Stephen's
> code is relicensed with BSD license by permission from the original code
> author (which also submitted the code to Linux kernel under GPL). This was
> already flagged. This is a legal issue and I do not feel comfortable with ack-ing
> this patch until the legal resolution on this is crystal clear.
> >
> > I also think the new files called rte_reciprocal.[hc] implement an algorithm
> that is very generic and totally independent of the QoS code, therefore it
> should be placed into a different folder that is globally visible to other
> libraries (librte_eal/common ?) just in case other usages for this algorithm
> are identified in the future. I suggest we break the patch into two separate
> patches submitted independently: one introducing the rte_reciprocal.[hc]
> algorithm to librte_eal/common and the second containing just the
> librte_sched changes, which are small. I am thinking ahead here: once we
> have the 2x64-bit multiplication solution in place, we should not have
> rte_reciprocal.[hc] hanging in librte_sched folder without being used here,
> while it might be used by other parts of DPDK.
> 
> Let's keep the improvement as-is to test it in the first release candidate.
> We can move the code and/or fix the file header later.
> 
> Series applied, thanks.

Hi Thomas,

I am OK with this, as long as Stephen commits to fix the copyright in the header file and move the rte_reciprocal.[hc] into a common area like librte_eal/common in time for the next release candidate.

Thanks,
Cristian

Re: [PATCH 0/3] sched: patches for 2.2

[Thomas Monjalon]

2016-03-13 22:47, Dumitrescu, Cristian:
> From: Thomas Monjalon [mailto:thomas.monjalon@6wind.com]
> > 2016-03-08 07:49, Dumitrescu, Cristian:
> > > Regarding Stephen's patches, I think there is a pending issue regarding the
> > legal side of the Copyright, which is attributed to Intel, although Stephen's
> > code is relicensed with BSD license by permission from the original code
> > author (which also submitted the code to Linux kernel under GPL). This was
> > already flagged. This is a legal issue and I do not feel comfortable with ack-ing
> > this patch until the legal resolution on this is crystal clear.
> > >
> > > I also think the new files called rte_reciprocal.[hc] implement an algorithm
> > that is very generic and totally independent of the QoS code, therefore it
> > should be placed into a different folder that is globally visible to other
> > libraries (librte_eal/common ?) just in case other usages for this algorithm
> > are identified in the future. I suggest we break the patch into two separate
> > patches submitted independently: one introducing the rte_reciprocal.[hc]
> > algorithm to librte_eal/common and the second containing just the
> > librte_sched changes, which are small. I am thinking ahead here: once we
> > have the 2x64-bit multiplication solution in place, we should not have
> > rte_reciprocal.[hc] hanging in librte_sched folder without being used here,
> > while it might be used by other parts of DPDK.
> > 
> > Let's keep the improvement as-is to test it in the first release candidate.
> > We can move the code and/or fix the file header later.
> > 
> > Series applied, thanks.
> 
> Hi Thomas,
> 
> I am OK with this, as long as Stephen commits to fix the copyright in the
> header file

There is no copyright issue. Just an Intel mention in the disclaimer.

> and move the rte_reciprocal.[hc] into a common area like
> librte_eal/common in time for the next release candidate.

If it is moved as a public API, it must be better documented.
If it stay here, it must be removed from SYMLINK-y-include.

Re: [PATCH 0/3] sched: patches for 2.2

[Dumitrescu, Cristian]

> -----Original Message-----
> From: Thomas Monjalon [mailto:thomas.monjalon@6wind.com]
> Sent: Sunday, March 13, 2016 11:09 PM
> To: Dumitrescu, Cristian <cristian.dumitrescu@intel.com>; Stephen
> Hemminger <stephen@networkplumber.org>
> Cc: dev@dpdk.org
> Subject: Re: [dpdk-dev] [PATCH 0/3] sched: patches for 2.2
> 
> 2016-03-13 22:47, Dumitrescu, Cristian:
> > From: Thomas Monjalon [mailto:thomas.monjalon@6wind.com]
> > > 2016-03-08 07:49, Dumitrescu, Cristian:
> > > > Regarding Stephen's patches, I think there is a pending issue regarding
> the
> > > legal side of the Copyright, which is attributed to Intel, although
> Stephen's
> > > code is relicensed with BSD license by permission from the original code
> > > author (which also submitted the code to Linux kernel under GPL). This
> was
> > > already flagged. This is a legal issue and I do not feel comfortable with
> ack-ing
> > > this patch until the legal resolution on this is crystal clear.
> > > >
> > > > I also think the new files called rte_reciprocal.[hc] implement an
> algorithm
> > > that is very generic and totally independent of the QoS code, therefore it
> > > should be placed into a different folder that is globally visible to other
> > > libraries (librte_eal/common ?) just in case other usages for this algorithm
> > > are identified in the future. I suggest we break the patch into two
> separate
> > > patches submitted independently: one introducing the
> rte_reciprocal.[hc]
> > > algorithm to librte_eal/common and the second containing just the
> > > librte_sched changes, which are small. I am thinking ahead here: once we
> > > have the 2x64-bit multiplication solution in place, we should not have
> > > rte_reciprocal.[hc] hanging in librte_sched folder without being used
> here,
> > > while it might be used by other parts of DPDK.
> > >
> > > Let's keep the improvement as-is to test it in the first release candidate.
> > > We can move the code and/or fix the file header later.
> > >
> > > Series applied, thanks.
> >
> > Hi Thomas,
> >
> > I am OK with this, as long as Stephen commits to fix the copyright in the
> > header file
> 
> There is no copyright issue. Just an Intel mention in the disclaimer.

Thanks, Thomas, for confirming this. My knowledge on copyright issues is limited, so I was not sure whether this is an issue or not.

> 
> > and move the rte_reciprocal.[hc] into a common area like
> > librte_eal/common in time for the next release candidate.
> 
> If it is moved as a public API, it must be better documented.
> If it stay here, it must be removed from SYMLINK-y-include.

My vote would go for making this a public API, moving it to a common place (like librte_eal/common) and better documenting it. I already see other libraries that would benefit from a faster implementation of division (e.g. librte_meter), there are probably others as well. I'd like to get Stephen's opinion on this.