From ffe3ec811ef5028426dfbeb3b2927d1216f4b2f5 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger Date: Sun, 29 Nov 2015 10:46:48 -0800 Subject: [PATCH] sched: introduce reciprocal divide This adds (with permission of the original author) reciprocal divide based on algorithm in Linux. Signed-off-by: Stephen Hemminger Signed-off-by: Hannes Frederic Sowa --- lib/librte_sched/Makefile | 2 + lib/librte_sched/rte_reciprocal.c | 72 +++++++++++++++++++++++++++++++ lib/librte_sched/rte_reciprocal.h | 39 +++++++++++++++++ 3 files changed, 113 insertions(+) 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 4d631f6a0d..a782cd1aad 100644 --- a/lib/librte_sched/Makefile +++ b/lib/librte_sched/Makefile @@ -52,9 +52,11 @@ 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_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_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 0000000000..652f0237aa --- /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 +#include + +#include + +#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 0000000000..abd15251d0 --- /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.20.1