From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id DD05A37A6 for ; Wed, 2 Dec 2015 17:45:10 +0100 (CET) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga103.fm.intel.com with ESMTP; 02 Dec 2015 08:45:10 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.20,373,1444719600"; d="scan'208";a="611369974" Received: from irsmsx107.ger.corp.intel.com ([163.33.3.99]) by FMSMGA003.fm.intel.com with ESMTP; 02 Dec 2015 08:45:05 -0800 Received: from irsmsx112.ger.corp.intel.com (10.108.20.5) by IRSMSX107.ger.corp.intel.com (163.33.3.99) with Microsoft SMTP Server (TLS) id 14.3.248.2; Wed, 2 Dec 2015 16:45:03 +0000 Received: from irsmsx108.ger.corp.intel.com ([169.254.11.23]) by irsmsx112.ger.corp.intel.com ([169.254.1.8]) with mapi id 14.03.0248.002; Wed, 2 Dec 2015 16:45:03 +0000 From: "Dumitrescu, Cristian" To: Stephen Hemminger Thread-Topic: [PATCH 2/3] rte_sched: introduce reciprocal divide Thread-Index: AQHRKtZRQQcVWJ/o8UCARDl7qIvefJ6334/g Date: Wed, 2 Dec 2015 16:45:01 +0000 Message-ID: <3EB4FA525960D640B5BDFFD6A3D8912647925BB6@IRSMSX108.ger.corp.intel.com> References: <1448822809-8350-1-git-send-email-stephen@networkplumber.org> <1448822809-8350-3-git-send-email-stephen@networkplumber.org> In-Reply-To: <1448822809-8350-3-git-send-email-stephen@networkplumber.org> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-inteldataclassification: CTP_IC x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsIiwiaWQiOiI3NTkyZGM1Yy03ZDhlLTRlYzgtOGU3Ni1lZWI1OGUzZDZmMWUiLCJwcm9wcyI6W3sibiI6IkludGVsRGF0YUNsYXNzaWZpY2F0aW9uIiwidmFscyI6W3sidmFsdWUiOiJDVFBfSUMifV19XX0sIlN1YmplY3RMYWJlbHMiOltdLCJUTUNWZXJzaW9uIjoiMTUuNC4xMC4xOSIsIlRydXN0ZWRMYWJlbEhhc2giOiJoUmRmcVcybUQzR3FKeFBvXC8xME9MendPbFU3S0tMUzJxZ0tyUlRQQjZHWT0ifQ== x-originating-ip: [163.33.239.181] Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Cc: "dev@dpdk.org" Subject: Re: [dpdk-dev] [PATCH 2/3] rte_sched: introduce reciprocal divide X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 02 Dec 2015 16:45:11 -0000 > -----Original Message----- > From: Stephen Hemminger [mailto:stephen@networkplumber.org] > Sent: Sunday, November 29, 2015 8:47 PM > To: Dumitrescu, Cristian > Cc: dev@dpdk.org; Stephen Hemminger ; > Hannes Frederic Sowa > Subject: [PATCH 2/3] rte_sched: introduce reciprocal divide >=20 > This adds (with permission of the original author) > reciprocal divide based on algorithm in Linux. >=20 > 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 >=20 > 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_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 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 Why is Intel mentioned here, as according to this license header Intel is n= ot 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 > +#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_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=C3=B6rn 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 transf= er this structure by value rather than by reference (the function rte_recip= rocal_value() below returns an instance of this structure), I don't feel co= mfortable with the last 16 bits of the structure being left uninitialized, = we should probably add some explicit pad field and initialize this structur= e explicitly to zero at init time? > + > +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); 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 th= is 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 div= ision is 64-bit multiplication followed by right shift, any particular reas= on why this approach was not considered?