From patchwork Fri Feb 9 20:20:03 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chas Williams <3chas3@gmail.com> X-Patchwork-Id: 35103 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D40F71B89C; Fri, 9 Feb 2018 21:20:14 +0100 (CET) Received: from mail-qt0-f194.google.com (mail-qt0-f194.google.com [209.85.216.194]) by dpdk.org (Postfix) with ESMTP id AFEFC1B899 for ; Fri, 9 Feb 2018 21:20:12 +0100 (CET) Received: by mail-qt0-f194.google.com with SMTP id s27so12104524qts.4 for ; Fri, 09 Feb 2018 12:20:12 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=AlNSv44moF7Y5J048E0DdHCnfdknckp/yQqQTNQRVqc=; b=JAjt2HO5aFYEuGWzscWOoAmMG5Iqzdo7IYQcDoqyJSZk7upzVVBag+hacbgu7870qg MleEAG6PdgTsOHKu3xSR7yG/TXg7+jxyIMc6P+4muTJyG8Z+vKLqwN6Yp9hhWM9AHT3O q6zT0oUFl1mWPabnn1MlBT66Myez2vkv1hUnCE/woW9l/DCH6lTSmpY2cnBpbwghXA2Y 1ZTgxKGtqtC/ZHrS/1bRpTeZIPp3mbhI08wE+D0aGWZzG3JX3qDbwqad3FITUKdSrZYY UsqUh88qs51659KXYuWgbzb2vzserd9ZmqmnUH48ae+BEZFPoWElNUuMyFdE26lUC8px x7/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=AlNSv44moF7Y5J048E0DdHCnfdknckp/yQqQTNQRVqc=; b=n1c6o97osntdzkoAkk4EH3xklYp7BtaMEkYW997/kptYlN0mvFY41q2Psgj+hCT7qI mSsvVtL0JX3eUo0EAsBZY4oBg7+VYTFSodFsz7Nov4AFVYhTxlNN6Ic2t11Htzf4n1o7 18vJ+4jL65Y67kIrA6QrkFo6unuUf1JBcG/1sCpaChfNlHbKAH2SP5Ce9eoeqY1tB4BJ 8VsKe+wy4qhSfsNF5Rpin1IV4TlH79IXMfTSxMK1F7DW0J//Bw7NJMWLG5TM73iVaeCT kR9nnEGiNjDRlayIXsnc9R0fbkedqTy5dQZZNj09JEqj1zqUzRZkKo9yvfyjfsd7oXSA 7B+g== X-Gm-Message-State: APf1xPBKb1eeJkBLLFip0lwsBq+6rrtVEi7T6wLuHjSnDNZfUcVDc2K9 h9TI/0QvZZlLSoRpEBDXLA9kIQ== X-Google-Smtp-Source: AH8x227h1BR/nKOdj8CgC86QLlxDzsTdLhX4Kz9DTtYz84BS6ZKZfQGtXxB5Hc/DB9whL+dwccC2fw== X-Received: by 10.200.51.229 with SMTP id d34mr6384605qtb.338.1518207611898; Fri, 09 Feb 2018 12:20:11 -0800 (PST) Received: from monolith.home (pool-173-79-224-159.washdc.fios.verizon.net. [173.79.224.159]) by smtp.gmail.com with ESMTPSA id l36sm2421598qte.55.2018.02.09.12.20.10 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 09 Feb 2018 12:20:11 -0800 (PST) From: Chas Williams <3chas3@gmail.com> To: dev@dpdk.org Cc: cristian.dumitrescu@intel.com, "Charles (Chas) Williams" Date: Fri, 9 Feb 2018 15:20:03 -0500 Message-Id: <20180209202003.28546-2-3chas3@gmail.com> X-Mailer: git-send-email 2.9.5 In-Reply-To: <20180209202003.28546-1-3chas3@gmail.com> References: <20180209202003.28546-1-3chas3@gmail.com> Subject: [dpdk-dev] [PATCH 2/2] lib: fix bitmap scanning X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" From: "Charles (Chas) Williams" index2 is used inconsistently, both as an array offset and as a bit offset. Fix usage to be consistent as a bit offset. Additonally, offset1 needs to be shifted with the size of the array1 slab entries, not the cache line sizes. __rte_bitmap_scan_read() needs to examine the current array2 slab bit by bit to find the next set bit. The unit tests for rte_bitmap_scan() aren't correct. If a slab isn't empty, there is no reason to expect rte_bitmap_scan() to advance to the next slab. Change the slab magic values so that rte_bitmap_scan() will advance on reading a bit from each slab and verify it is the bit position we expect. Fixes: de3cfa2c9823a ("sched: initial import") Signed-off-by: Chas Williams --- lib/librte_eal/common/include/rte_bitmap.h | 31 +++++++++++++++--------------- test/test/test_bitmap.c | 12 ++++++------ 2 files changed, 22 insertions(+), 21 deletions(-) diff --git a/lib/librte_eal/common/include/rte_bitmap.h b/lib/librte_eal/common/include/rte_bitmap.h index 7d4935f..27084d9 100644 --- a/lib/librte_eal/common/include/rte_bitmap.h +++ b/lib/librte_eal/common/include/rte_bitmap.h @@ -94,7 +94,8 @@ __rte_bitmap_mask1_get(struct rte_bitmap *bmp) static inline void __rte_bitmap_index2_set(struct rte_bitmap *bmp) { - bmp->index2 = (((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + bmp->offset1) << RTE_BITMAP_CL_SLAB_SIZE_LOG2); + bmp->index2 = ((bmp->index1 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2) + + bmp->offset1) << RTE_BITMAP_SLAB_BIT_SIZE_LOG2; } #if RTE_BITMAP_OPTIMIZATIONS @@ -172,7 +173,6 @@ __rte_bitmap_scan_init(struct rte_bitmap *bmp) bmp->index1 = bmp->array1_size - 1; bmp->offset1 = RTE_BITMAP_SLAB_BIT_SIZE - 1; __rte_bitmap_index2_set(bmp); - bmp->index2 += RTE_BITMAP_CL_SLAB_SIZE; bmp->go2 = 0; } @@ -338,7 +338,8 @@ rte_bitmap_set(struct rte_bitmap *bmp, uint32_t pos) index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; offset2 = pos & RTE_BITMAP_SLAB_BIT_MASK; index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); - offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; + offset1 = (pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) & + RTE_BITMAP_SLAB_BIT_MASK; slab2 = bmp->array2 + index2; slab1 = bmp->array1 + index1; @@ -365,7 +366,8 @@ rte_bitmap_set_slab(struct rte_bitmap *bmp, uint32_t pos, uint64_t slab) /* Set bits in array2 slab and set bit in array1 slab */ index2 = pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2; index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); - offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; + offset1 = (pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) & + RTE_BITMAP_SLAB_BIT_MASK; slab2 = bmp->array2 + index2; slab1 = bmp->array1 + index1; @@ -422,7 +424,8 @@ rte_bitmap_clear(struct rte_bitmap *bmp, uint32_t pos) /* The array2 cache line is all-zeros, so clear bit in array1 slab */ index1 = pos >> (RTE_BITMAP_SLAB_BIT_SIZE_LOG2 + RTE_BITMAP_CL_BIT_SIZE_LOG2); - offset1 = (pos >> RTE_BITMAP_CL_BIT_SIZE_LOG2) & RTE_BITMAP_SLAB_BIT_MASK; + offset1 = (pos >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2) & + RTE_BITMAP_SLAB_BIT_MASK; slab1 = bmp->array1 + index1; *slab1 &= ~(1lu << offset1); @@ -471,15 +474,14 @@ __rte_bitmap_scan_read(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) { uint64_t *slab2; - slab2 = bmp->array2 + bmp->index2; - for ( ; bmp->go2 ; bmp->index2 ++, slab2 ++, bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK) { - if (*slab2) { - *pos = bmp->index2 << RTE_BITMAP_SLAB_BIT_SIZE_LOG2; - *slab = *slab2; + slab2 = bmp->array2 + (bmp->index2 >> RTE_BITMAP_SLAB_BIT_SIZE_LOG2); + for ( ; bmp->go2 ; bmp->index2++, + bmp->go2 = bmp->index2 & RTE_BITMAP_SLAB_BIT_MASK) { + uint32_t offset2 = bmp->index2 & RTE_BITMAP_SLAB_BIT_MASK; - bmp->index2 ++; - slab2 ++; - bmp->go2 = bmp->index2 & RTE_BITMAP_CL_SLAB_MASK; + if (*slab2 & (1lu << offset2)) { + *pos = bmp->index2++; + *slab = *slab2; return 1; } } @@ -518,8 +520,7 @@ rte_bitmap_scan(struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab) /* Look for non-empty array2 line */ if (__rte_bitmap_scan_search(bmp)) { __rte_bitmap_scan_read_init(bmp); - __rte_bitmap_scan_read(bmp, pos, slab); - return 1; + return __rte_bitmap_scan_read(bmp, pos, slab); } /* Empty bitmap */ diff --git a/test/test/test_bitmap.c b/test/test/test_bitmap.c index f498c02..ffbbc02 100644 --- a/test/test/test_bitmap.c +++ b/test/test/test_bitmap.c @@ -17,8 +17,8 @@ static int test_bitmap_scan_operations(struct rte_bitmap *bmp) { uint32_t pos = 0; - uint64_t slab1_magic = 0xBADC0FFEEBADF00D; - uint64_t slab2_magic = 0xFEEDDEADDEADF00D; + uint64_t slab1_magic = 0x80; /* pos = 7 */ + uint64_t slab2_magic = 0x08; /* pos = 67 */ uint64_t out_slab = 0; rte_bitmap_reset(bmp); @@ -26,7 +26,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) rte_bitmap_set_slab(bmp, pos, slab1_magic); rte_bitmap_set_slab(bmp, pos + RTE_BITMAP_SLAB_BIT_SIZE, slab2_magic); - if (!rte_bitmap_scan(bmp, &pos, &out_slab)) { + if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 7) { printf("Failed to get slab from bitmap.\n"); return TEST_FAILED; } @@ -36,7 +36,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) return TEST_FAILED; } - if (!rte_bitmap_scan(bmp, &pos, &out_slab)) { + if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 67) { printf("Failed to get slab from bitmap.\n"); return TEST_FAILED; } @@ -47,7 +47,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) } /* Wrap around */ - if (!rte_bitmap_scan(bmp, &pos, &out_slab)) { + if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 7) { printf("Failed to get slab from bitmap.\n"); return TEST_FAILED; } @@ -60,7 +60,7 @@ test_bitmap_scan_operations(struct rte_bitmap *bmp) /* Scan reset check. */ __rte_bitmap_scan_init(bmp); - if (!rte_bitmap_scan(bmp, &pos, &out_slab)) { + if (!rte_bitmap_scan(bmp, &pos, &out_slab) || pos != 7) { printf("Failed to get slab from bitmap.\n"); return TEST_FAILED; }