From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from ex.trust-in-soft.com (ex.trust-in-soft.com [188.165.147.96]) by dpdk.org (Postfix) with ESMTP id BFAE85933 for ; Mon, 12 May 2014 17:35:15 +0200 (CEST) Received: from localhost.localdomain (84.14.219.4) by S1688.EX1688.lan (2001:41d0:6b:b00::bca5:9360) with Microsoft SMTP Server (TLS) id 15.0.712.22; Mon, 12 May 2014 17:36:25 +0200 From: Julien Cretin To: Date: Mon, 12 May 2014 17:35:10 +0200 Message-ID: <1399908911-18829-3-git-send-email-julien.cretin@trust-in-soft.com> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1399908911-18829-1-git-send-email-julien.cretin@trust-in-soft.com> References: <1399908911-18829-1-git-send-email-julien.cretin@trust-in-soft.com> MIME-Version: 1.0 Content-Type: text/plain X-Originating-IP: [84.14.219.4] X-ClientProxiedBy: S1688.EX1688.lan (2001:41d0:6b:b00::bca5:9360) To S1688.EX1688.lan (2001:41d0:6b:b00::bca5:9360) Subject: [dpdk-dev] [PATCH 2/3] mem: remove redundant check in optimize_object_size 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: Mon, 12 May 2014 15:35:16 -0000 The second condition of this logical OR: (get_gcd(new_obj_size, nrank * nchan) != 1 || get_gcd(nchan, new_obj_size) != 1) is redundant with the first condition. We can show that the first condition is equivalent to its disjunction with the second condition using these two results: - R1: For all conditions A and B, if B implies A, then (A || B) is equivalent to A. - R2: (get_gcd(nchan, new_obj_size) != 1) implies (get_gcd(new_obj_size, nrank * nchan) != 1) We can show R1 with the following truth table (0 is false, 1 is true): +-----+-----++----------+-----+-------------+ | A | B || (A || B) | A | B implies A | +-----+-----++----------+-----+-------------+ | 0 | 0 || 0 | 0 | 1 | | 0 | 1 || 1 | 0 | 0 | | 1 | 0 || 1 | 1 | 1 | | 1 | 1 || 1 | 1 | 1 | +-----+-----++----------+-----+-------------+ Truth table of (A || B) and A We can show R2 by looking at the code of optimize_object_size and get_gcd. We see that: - S1: (nchan >= 1) and (nrank >= 1). - S2: get_gcd returns 0 only when both arguments are 0. Let: - X be get_gcd(new_obj_size, nrank * nchan). - Y be get_gcd(nchan, new_obj_size). Suppose: - H1: get_gcd returns the greatest common divisor of its arguments. - H2: (nrank * nchan) does not exceed UINT_MAX. We prove (Y != 1) implies (X != 1) with the following steps: - Suppose L0: (Y != 1). We have to show (X != 1). - By H1, Y is the greatest common divisor of nchan and new_obj_size. In particular, we have L1: Y divides nchan and new_obj_size. - By H2, we have L2: nchan divides (nrank * nchan) - By L1 and L2, we have L3: Y divides (nrank * nchan) and new_obj_size. - By H1 and L3, we have L4: (Y <= X). - By S1 and S2, we have L5: (Y != 0). - By L0 and L5, we have L6: (Y > 1). - By L4 and L6, we have (X > 1) and thus (X != 1), which concludes. R2 was also tested for all values of new_obj_size, nrank, and nchan between 0 and 2000. This redundant condition was found using TrustInSoft Analyzer. Signed-off-by: Julien Cretin --- lib/librte_mempool/rte_mempool.c | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) diff --git a/lib/librte_mempool/rte_mempool.c b/lib/librte_mempool/rte_mempool.c index fdc1586..8e6c86a 100644 --- a/lib/librte_mempool/rte_mempool.c +++ b/lib/librte_mempool/rte_mempool.c @@ -114,8 +114,7 @@ static unsigned optimize_object_size(unsigned obj_size) /* process new object size */ new_obj_size = (obj_size + CACHE_LINE_MASK) / CACHE_LINE_SIZE; - while (get_gcd(new_obj_size, nrank * nchan) != 1 || - get_gcd(nchan, new_obj_size) != 1) + while (get_gcd(new_obj_size, nrank * nchan) != 1) new_obj_size++; return new_obj_size * CACHE_LINE_SIZE; } -- 1.9.1