From patchwork Sun Jan 11 17:50:37 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Bill Fischofer X-Patchwork-Id: 42954 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-wi0-f198.google.com (mail-wi0-f198.google.com [209.85.212.198]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 56DF32055F for ; Sun, 11 Jan 2015 17:51:13 +0000 (UTC) Received: by mail-wi0-f198.google.com with SMTP id r20sf4701397wiv.1 for ; Sun, 11 Jan 2015 09:51:12 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:from:to:date:message-id:in-reply-to :references:subject:precedence:list-id:list-unsubscribe:list-archive :list-post:list-help:list-subscribe:mime-version:content-type :content-transfer-encoding:errors-to:sender:x-original-sender :x-original-authentication-results:mailing-list; bh=u7CjMeHnEroS1R9Mde+4gZ4EFm0vxKN29ed/IHN0qOs=; b=YtcmGxyCqtgfWfodpofaKNY1nHPGo92DLPpMQTcv9K7471wpqnM5qDapPVpwd/bf7Z UMjJ2eD7zx5At6idFecXGho4FFSyNd0U5q4baHot5E4LeuItVdtsqfHu5LT4pZaqkA9J qWIhtwLLgsspt13h2KDQxUdXFGNkyBq968TL2DkDdGYIG/zFvs5jk5mOmPpGDaBokk5o pNITTxuYQzMIemZI4ovUmZ94f+3N8JxaC8PG7ZKXko3AWDOix5B7A6hIBfeXDAMff+aw o7gwcFcOwlvZ09R6KdlGZpBeD+sqjRb/3BNP7mHUGqPQUZoNKb/NFpCh+/u/vmlHA6Lm BEWQ== X-Gm-Message-State: ALoCoQk83Cuo8NU7QmmZ9P0FvT3OJlA3Dmr0bQc/WUKnlaWcyVm57bavTTr5TsDewX1RVltr6a0i X-Received: by 10.180.77.167 with SMTP id t7mr1584201wiw.6.1420998672640; Sun, 11 Jan 2015 09:51:12 -0800 (PST) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.205.38 with SMTP id ld6ls601528lac.50.gmail; Sun, 11 Jan 2015 09:51:12 -0800 (PST) X-Received: by 10.152.45.65 with SMTP id k1mr32921435lam.14.1420998672483; Sun, 11 Jan 2015 09:51:12 -0800 (PST) Received: from mail-la0-f47.google.com (mail-la0-f47.google.com. [209.85.215.47]) by mx.google.com with ESMTPS id uo8si19141901lbb.96.2015.01.11.09.51.12 for (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 11 Jan 2015 09:51:12 -0800 (PST) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.47 as permitted sender) client-ip=209.85.215.47; Received: by mail-la0-f47.google.com with SMTP id hz20so21057896lab.6 for ; Sun, 11 Jan 2015 09:51:12 -0800 (PST) X-Received: by 10.152.115.146 with SMTP id jo18mr32958309lab.9.1420998672088; Sun, 11 Jan 2015 09:51:12 -0800 (PST) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.9.200 with SMTP id c8csp879568lbb; Sun, 11 Jan 2015 09:51:11 -0800 (PST) X-Received: by 10.140.93.139 with SMTP id d11mr40462493qge.101.1420998670695; Sun, 11 Jan 2015 09:51:10 -0800 (PST) Received: from ip-10-35-177-41.ec2.internal (lists.linaro.org. [54.225.227.206]) by mx.google.com with ESMTPS id t3si19627883qak.122.2015.01.11.09.51.09 (version=TLSv1 cipher=RC4-SHA bits=128/128); Sun, 11 Jan 2015 09:51:10 -0800 (PST) Received-SPF: none (google.com: lng-odp-bounces@lists.linaro.org does not designate permitted sender hosts) client-ip=54.225.227.206; Received: from localhost ([127.0.0.1] helo=ip-10-35-177-41.ec2.internal) by ip-10-35-177-41.ec2.internal with esmtp (Exim 4.76) (envelope-from ) id 1YAMfM-0006ZQ-7K; Sun, 11 Jan 2015 17:51:08 +0000 Received: from mail-ob0-f171.google.com ([209.85.214.171]) by ip-10-35-177-41.ec2.internal with esmtp (Exim 4.76) (envelope-from ) id 1YAMfA-0006Yf-Ap for lng-odp@lists.linaro.org; Sun, 11 Jan 2015 17:50:56 +0000 Received: by mail-ob0-f171.google.com with SMTP id uz6so19492206obc.2 for ; Sun, 11 Jan 2015 09:50:51 -0800 (PST) X-Received: by 10.183.24.162 with SMTP id ij2mr15364314obd.18.1420998651052; Sun, 11 Jan 2015 09:50:51 -0800 (PST) Received: from localhost.localdomain (cpe-24-28-70-239.austin.res.rr.com. [24.28.70.239]) by mx.google.com with ESMTPSA id dd17sm7868408obb.18.2015.01.11.09.50.50 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Sun, 11 Jan 2015 09:50:50 -0800 (PST) From: Bill Fischofer To: lng-odp@lists.linaro.org Date: Sun, 11 Jan 2015 11:50:37 -0600 Message-Id: <1420998638-23980-3-git-send-email-bill.fischofer@linaro.org> X-Mailer: git-send-email 2.1.0 In-Reply-To: <1420998638-23980-1-git-send-email-bill.fischofer@linaro.org> References: <1420998638-23980-1-git-send-email-bill.fischofer@linaro.org> X-Topics: patch Subject: [lng-odp] [PATCHv2 2/3] linux-generic: buffers: improve lockless allocator X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: lng-odp-bounces@lists.linaro.org Sender: lng-odp-bounces@lists.linaro.org X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: bill.fischofer@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.47 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 Improve lockless buffer allocation by using offsets to extend tag length to avoid ABA issues. This also resolves Bug 1051. Signed-off-by: Bill Fischofer --- .../include/odp_buffer_pool_internal.h | 89 ++++++++++++++-------- platform/linux-generic/odp_buffer_pool.c | 7 +- 2 files changed, 59 insertions(+), 37 deletions(-) diff --git a/platform/linux-generic/include/odp_buffer_pool_internal.h b/platform/linux-generic/include/odp_buffer_pool_internal.h index 2e48ac3..169e02d 100644 --- a/platform/linux-generic/include/odp_buffer_pool_internal.h +++ b/platform/linux-generic/include/odp_buffer_pool_internal.h @@ -107,8 +107,8 @@ struct pool_entry_s { size_t pool_size; uint32_t buf_align; uint32_t buf_stride; - _odp_atomic_ptr_t buf_freelist; - _odp_atomic_ptr_t blk_freelist; + odp_atomic_u64_t buf_freelist; + odp_atomic_u64_t blk_freelist; odp_atomic_u32_t bufcount; odp_atomic_u32_t blkcount; odp_atomic_u64_t bufallocs; @@ -142,57 +142,77 @@ extern void *pool_entry_ptr[]; #define pool_is_secure(pool) 0 #endif -#define TAG_ALIGN ((size_t)16) +#define OFFSET_BITS ODP_BITSIZE((uint64_t)ODP_BUFFER_MAX_BUFFERS * \ + (uint32_t)ODP_CONFIG_PACKET_BUF_LEN_MAX) + +#define MAX_OFFSET (1ULL << BUF_OFFSET_BITS) +#define TAG_BITS (64 - OFFSET_BITS) +#define TAG_ALIGN (1ULL << TAG_BITS) + +#define NULL_OFFSET (~0ULL) +#define NULL_DETAGGED_OFFSET ((~0ULL) >> TAG_BITS) #define odp_cs(ptr, old, new) \ - _odp_atomic_ptr_cmp_xchg_strong(&ptr, (void **)&old, (void *)new, \ - _ODP_MEMMODEL_SC, \ - _ODP_MEMMODEL_SC) + _odp_atomic_u64_cmp_xchg_strong_mm(&ptr, (uint64_t *)&old, \ + (uint64_t)new, \ + _ODP_MEMMODEL_SC, _ODP_MEMMODEL_SC) + +/* Helper functions for offset tagging to avoid ABA race conditions */ +#define odp_tag(offset) \ + (((uint64_t)offset) & (TAG_ALIGN - 1)) -/* Helper functions for pointer tagging to avoid ABA race conditions */ -#define odp_tag(ptr) \ - (((size_t)ptr) & (TAG_ALIGN - 1)) +#define off2ptr(offset, base) \ + ((void *)((size_t)base + ((size_t)((uint64_t)offset >> TAG_BITS)))) -#define odp_detag(ptr) \ - ((void *)(((size_t)ptr) & -TAG_ALIGN)) +#define odp_detag(offset, base) \ + (((uint64_t)offset >> TAG_BITS) == NULL_DETAGGED_OFFSET ? NULL : \ + off2ptr(offset, base)) -#define odp_retag(ptr, tag) \ - ((void *)(((size_t)ptr) | odp_tag(tag))) +#define ptr2off(ptr, base) \ + ((uint64_t)(ptr == NULL ? (NULL_DETAGGED_OFFSET << TAG_BITS) : \ + (((uint64_t)((size_t)ptr - (size_t)base)) << TAG_BITS))) + +#define odp_retag(ptr, base, tag) (ptr2off(ptr, base) | odp_tag(tag)) static inline void *get_blk(struct pool_entry_s *pool) { - void *oldhead, *myhead, *newhead; + uint64_t oldhead, newhead; + void *myhead; - oldhead = _odp_atomic_ptr_load(&pool->blk_freelist, _ODP_MEMMODEL_ACQ); + oldhead = odp_atomic_load_u64(&pool->blk_freelist); do { - size_t tag = odp_tag(oldhead); - myhead = odp_detag(oldhead); + uint64_t tag = odp_tag(oldhead); + myhead = odp_detag(oldhead, pool->pool_base_addr); if (odp_unlikely(myhead == NULL)) break; - newhead = odp_retag(((odp_buf_blk_t *)myhead)->next, tag + 1); + newhead = odp_retag(((odp_buf_blk_t *)myhead)->next, + pool->pool_base_addr, tag + 1); } while (odp_cs(pool->blk_freelist, oldhead, newhead) == 0); - if (odp_unlikely(myhead == NULL)) + if (odp_unlikely(myhead == NULL)) { odp_atomic_inc_u64(&pool->blkempty); - else + } else { + odp_atomic_inc_u64(&pool->blkallocs); odp_atomic_dec_u32(&pool->blkcount); + } - return (void *)myhead; + return myhead; } static inline void ret_blk(struct pool_entry_s *pool, void *block) { - void *oldhead, *myhead, *myblock; + uint64_t oldhead, myblock; + void *myhead; - oldhead = _odp_atomic_ptr_load(&pool->blk_freelist, _ODP_MEMMODEL_ACQ); + oldhead = odp_atomic_load_u64(&pool->blk_freelist); do { size_t tag = odp_tag(oldhead); - myhead = odp_detag(oldhead); + myhead = odp_detag(oldhead, pool->pool_base_addr); ((odp_buf_blk_t *)block)->next = myhead; - myblock = odp_retag(block, tag + 1); + myblock = odp_retag(block, pool->pool_base_addr, tag + 1); } while (odp_cs(pool->blk_freelist, oldhead, myblock) == 0); odp_atomic_inc_u32(&pool->blkcount); @@ -201,16 +221,18 @@ static inline void ret_blk(struct pool_entry_s *pool, void *block) static inline odp_buffer_hdr_t *get_buf(struct pool_entry_s *pool) { - odp_buffer_hdr_t *oldhead, *myhead, *newhead; + uint64_t oldhead, newhead; + odp_buffer_hdr_t *myhead; - oldhead = _odp_atomic_ptr_load(&pool->buf_freelist, _ODP_MEMMODEL_ACQ); + oldhead = odp_atomic_load_u64(&pool->buf_freelist); do { size_t tag = odp_tag(oldhead); - myhead = odp_detag(oldhead); + myhead = odp_detag(oldhead, pool->pool_mdata_addr); if (odp_unlikely(myhead == NULL)) break; - newhead = odp_retag(myhead->next, tag + 1); + newhead = odp_retag(myhead->next, pool->pool_mdata_addr, + tag + 1); } while (odp_cs(pool->buf_freelist, oldhead, newhead) == 0); if (odp_unlikely(myhead == NULL)) { @@ -235,7 +257,8 @@ static inline odp_buffer_hdr_t *get_buf(struct pool_entry_s *pool) static inline void ret_buf(struct pool_entry_s *pool, odp_buffer_hdr_t *buf) { - odp_buffer_hdr_t *oldhead, *myhead, *mybuf; + uint64_t oldhead, mybuf; + odp_buffer_hdr_t *myhead; buf->allocator = ODP_FREEBUF; /* Mark buffer free */ @@ -249,13 +272,13 @@ static inline void ret_buf(struct pool_entry_s *pool, odp_buffer_hdr_t *buf) buf->size = 0; } - oldhead = _odp_atomic_ptr_load(&pool->buf_freelist, _ODP_MEMMODEL_ACQ); + oldhead = odp_atomic_load_u64(&pool->buf_freelist); do { size_t tag = odp_tag(oldhead); - myhead = odp_detag(oldhead); + myhead = odp_detag(oldhead, pool->pool_mdata_addr); buf->next = myhead; - mybuf = odp_retag(buf, tag + 1); + mybuf = odp_retag(buf, pool->pool_mdata_addr, tag + 1); } while (odp_cs(pool->buf_freelist, oldhead, mybuf) == 0); uint64_t bufcount = odp_atomic_fetch_add_u32(&pool->bufcount, 1) + 1; diff --git a/platform/linux-generic/odp_buffer_pool.c b/platform/linux-generic/odp_buffer_pool.c index eedb380..5d181bb 100644 --- a/platform/linux-generic/odp_buffer_pool.c +++ b/platform/linux-generic/odp_buffer_pool.c @@ -286,10 +286,9 @@ odp_buffer_pool_t odp_buffer_pool_create(const char *name, pool->s.pool_mdata_addr = mdata_base_addr; pool->s.buf_stride = buf_stride; - _odp_atomic_ptr_store(&pool->s.buf_freelist, NULL, - _ODP_MEMMODEL_RLX); - _odp_atomic_ptr_store(&pool->s.blk_freelist, NULL, - _ODP_MEMMODEL_RLX); + + odp_atomic_store_u64(&pool->s.buf_freelist, NULL_OFFSET); + odp_atomic_store_u64(&pool->s.blk_freelist, NULL_OFFSET); /* Initialization will increment these to their target vals */ odp_atomic_store_u32(&pool->s.bufcount, 0);