From mboxrd@z Thu Jan 1 00:00:00 1970
Return-Path: <julien.cretin@trust-in-soft.com>
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 <dev@dpdk.org>; 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 <julien.cretin@trust-in-soft.com>
To: <dev@dpdk.org>
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 <dev.dpdk.org>
List-Unsubscribe: <http://dpdk.org/ml/options/dev>,
<mailto:dev-request@dpdk.org?subject=unsubscribe>
List-Archive: <http://dpdk.org/ml/archives/dev/>
List-Post: <mailto:dev@dpdk.org>
List-Help: <mailto:dev-request@dpdk.org?subject=help>
List-Subscribe: <http://dpdk.org/ml/listinfo/dev>,
<mailto:dev-request@dpdk.org?subject=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 <julien.cretin@trust-in-soft.com>
---
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