From mboxrd@z Thu Jan 1 00:00:00 1970 From: Stephen Hemminger Subject: [PATCH 2/3] rte_sched: introduce reciprocal divide Date: Sun, 29 Nov 2015 10:46:48 -0800 Message-ID: <1448822809-8350-3-git-send-email-stephen@networkplumber.org> References: <1448822809-8350-1-git-send-email-stephen@networkplumber.org> Mime-Version: 1.0 Content-Type: text/plain; charset=yes Content-Transfer-Encoding: quoted-printable Cc: dev@dpdk.org To: cristian.dumitrescu@intel.com Return-path: Received: from mail-pa0-f46.google.com (mail-pa0-f46.google.com [209.85.220.46]) by dpdk.org (Postfix) with ESMTP id 992788D39 for ; Sun, 29 Nov 2015 19:46:46 +0100 (CET) Received: by pacej9 with SMTP id ej9so160649866pac.2 for ; Sun, 29 Nov 2015 10:46:46 -0800 (PST) In-Reply-To: <1448822809-8350-1-git-send-email-stephen@networkplumber.org> List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" 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 | 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 :=3D 1 # # all source are stored in SRCS-y # -SRCS-$(CONFIG_RTE_LIBRTE_SCHED) +=3D rte_sched.c rte_red.c rte_approx.c +SRCS-$(CONFIG_RTE_LIBRTE_SCHED) +=3D rte_sched.c rte_red.c rte_approx.c = \ + rte_reciprocal.c =20 # install includes -SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include :=3D rte_sched.h rte_bitmap.h= rte_sched_common.h rte_red.h rte_approx.h +SYMLINK-$(CONFIG_RTE_LIBRTE_SCHED)-include :=3D rte_sched.h rte_bitmap.h= \ + rte_sched_common.h rte_red.h rte_approx.h rte_reciprocal.h =20 # this lib depends upon: DEPDIRS-$(CONFIG_RTE_LIBRTE_SCHED) +=3D lib/librte_mempool lib/librte_mb= uf diff --git a/lib/librte_sched/rte_reciprocal.c b/lib/librte_sched/rte_rec= iprocal.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 copyrig= ht + * 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 F= OR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGH= T + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTA= L, + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF US= E, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON A= NY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE U= SE + * 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 =3D 31; b >=3D 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 =3D fls(d - 1); + m =3D ((1ULL << 32) * ((1ULL << l) - d)); + m /=3D d; + + ++m; + R.m =3D m; + R.sh1 =3D RTE_MIN(l, 1); + R.sh2 =3D RTE_MAX(l - 1, 0); + + return R; +} diff --git a/lib/librte_sched/rte_reciprocal.h b/lib/librte_sched/rte_rec= iprocal.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=C3=B6rn 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_reci= procal R) +{ + uint32_t t =3D (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_ */ --=20 2.1.4