From 2612a4b935144accff34bc16e019c858677ada62 Mon Sep 17 00:00:00 2001 From: Julien Cretin Date: Mon, 12 May 2014 17:35:10 +0200 Subject: [PATCH] mem: remove redundant check in optimize_object_size 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 Acked-by: Thomas Monjalon --- 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 fdc1586b9e..8e6c86a95d 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; } -- 2.20.1