Received: by 2002:ac0:a5b6:0:0:0:0:0 with SMTP id m51-v6csp2047561imm; Thu, 7 Jun 2018 04:43:21 -0700 (PDT) X-Google-Smtp-Source: ADUXVKIVBO0toZzY8cohZi9MkAhFRpCbEht72+kcbxLrHr7x08NvB0ky44lsOZZDu9sulF/SEs9e X-Received: by 2002:a62:c00e:: with SMTP id x14-v6mr1477563pff.67.1528371801558; Thu, 07 Jun 2018 04:43:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1528371801; cv=none; d=google.com; s=arc-20160816; b=zzqWookOeeFsAiCPDinuYHb8sNXLCX3u5OzPnv+ZA5g8tV21eSgI7N/8w2x5Il7Xao fgSrC5gzXmbQxHTPBgRqgh2zR9BeI52gyXqyP/Od4gK6xku59EfA4pZ25pBF6KIkGw+e A7/2/06BjdWPZUCWXVg4EjmN32W+FyvX7U5SKTM0LwnDAqt+fwRR38eAQ08jBjxU/MsY 5BLurYitlwtRSOfY3KeSbqvgbvLlPt2ubMG47rIykQt1pmCa5V2OvL7I041SyTW2Qysa u4SWwadgDyOWz8R6d7U9fnu1rUsmcuGaqqfL9cHTlqfUDvU0gagZ90TinUwIBNpHhjg2 6/Xw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:references:in-reply-to:message-id:date :subject:to:from:dkim-signature:arc-authentication-results; bh=K9BtkV75JM22QTIiHxsHQDSrecEBDRNvGRKz6k6eGek=; b=FFErSCgDU8Q5Y5mIrIsJRUKejZYLK0lRe1vlg7Xbo1XOqWIYVfn1a7UpppC7Flzrgs UpqAhyUzFMIl7E23mX84kNRfoRG/jf8L+Ewltx06w3cVofQuMYFBNH28z7RaKoQ1paJ/ A3cbU/4P4XLGu6JpDCwEVJxYQOcE3u0spKO24p0PRKy3UrfuSGhHQXc/63gdEj/BFTAX G/WfH5MMKnXYV5SGJa/4eP+6QGqfMCjFpuN7w2Uj3O/WAF2TyRNG4EAReEwMW6skArko Pp3lshdc9hT3vSuLezPtS2Qz1bioQbrBhgatRtS7vaHM1D4P/lTW1bSw4o4unC59BsSC D0zg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@oracle.com header.s=corp-2017-10-26 header.b=B9I0fe+8; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=oracle.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id e11-v6si10376381pgt.63.2018.06.07.04.42.53; Thu, 07 Jun 2018 04:43:21 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; dkim=pass header.i=@oracle.com header.s=corp-2017-10-26 header.b=B9I0fe+8; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=oracle.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753188AbeFGKww (ORCPT + 99 others); Thu, 7 Jun 2018 06:52:52 -0400 Received: from aserp2120.oracle.com ([141.146.126.78]:46802 "EHLO aserp2120.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752960AbeFGKwu (ORCPT ); Thu, 7 Jun 2018 06:52:50 -0400 Received: from pps.filterd (aserp2120.oracle.com [127.0.0.1]) by aserp2120.oracle.com (8.16.0.22/8.16.0.22) with SMTP id w57AohXO025529; Thu, 7 Jun 2018 10:52:25 GMT DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=oracle.com; h=from : to : subject : date : message-id : in-reply-to : references; s=corp-2017-10-26; bh=K9BtkV75JM22QTIiHxsHQDSrecEBDRNvGRKz6k6eGek=; b=B9I0fe+8wbO3uBRqQj/DiAlX+IabyLfovVExDrcgnD4wm1hygRhPaUYWVFSlZIG2ndcK LAWW+dHetbbER8EppFyMWTCxczrIzOwNG1xEpgK4SEuO1q0V3MxTQRZW8i4Yj9mlLBvp kFiiC1XgPZ45LH/lfEPiwEG6SWEpGeogQsgfxxp08CGIHl7cok/pIclF62U1X8VpIlqg lg3Itbi/y/BNIe5DNDrtSEm9bPKYzdqOn4rcbiYl0GE6VvbDtgGBSJTn0iLN5yowM9Sj fmK8Qdlcl8IDsl4wV6BMFiQiuUOFqX7+3IG/YrKYiDO4fxobRS+KVN+8o1UkGLjb+3vx yw== Received: from userv0021.oracle.com (userv0021.oracle.com [156.151.31.71]) by aserp2120.oracle.com with ESMTP id 2jbvyprdpk-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 07 Jun 2018 10:52:25 +0000 Received: from userv0121.oracle.com (userv0121.oracle.com [156.151.31.72]) by userv0021.oracle.com (8.14.4/8.14.4) with ESMTP id w57AqO5k008067 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=OK); Thu, 7 Jun 2018 10:52:24 GMT Received: from abhmp0011.oracle.com (abhmp0011.oracle.com [141.146.116.17]) by userv0121.oracle.com (8.14.4/8.13.8) with ESMTP id w57AqN6w004813; Thu, 7 Jun 2018 10:52:23 GMT Received: from lab02.no.oracle.com (/10.172.144.56) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Thu, 07 Jun 2018 03:52:22 -0700 From: Hans Westgaard Ry To: Doug Ledford , Jason Gunthorpe , Hakon Bugge , Parav Pandit , Jack Morgenstein , Pravin Shedge , Matthew Wilcox , Andrew Morton , Jeff Layton , Wei Wang , Chris Mi , Eric Biggers , Rasmus Villemoes , Mel Gorman , linux-rdma@vger.kernel.org, linux-kernel@vger.kernel.org Subject: [PATCH v2 1/2] idr: Add ida_simple_get_cyclic Date: Thu, 7 Jun 2018 12:52:07 +0200 Message-Id: <20180607105208.16332-2-hans.westgaard.ry@oracle.com> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180607105208.16332-1-hans.westgaard.ry@oracle.com> References: <20180529073808.27735-1-hans.westgaard.ry@oracle.com> <20180607105208.16332-1-hans.westgaard.ry@oracle.com> X-Proofpoint-Virus-Version: vendor=nai engine=5900 definitions=8916 signatures=668702 X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=2 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=966 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1805220000 definitions=main-1806070128 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Orabug: 25571450 Signed-off-by: Hans Westgaard Ry --- include/linux/idr.h | 8 +++++-- lib/idr.c | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 72 insertions(+), 2 deletions(-) diff --git a/include/linux/idr.h b/include/linux/idr.h index e856f4e0ab35..f151ce89124a 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -218,10 +218,12 @@ DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap); struct ida { struct radix_tree_root ida_rt; + unsigned int ida_next; }; -#define IDA_INIT(name) { \ - .ida_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER | GFP_NOWAIT), \ +#define IDA_INIT(name) { \ + .ida_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER | GFP_NOWAIT), \ + .ida_next = 0, \ } #define DEFINE_IDA(name) struct ida name = IDA_INIT(name) @@ -232,6 +234,8 @@ void ida_destroy(struct ida *ida); int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, gfp_t gfp_mask); +int ida_simple_get_cyclic(struct ida *ida, unsigned int start, unsigned int end, + gfp_t gfp_mask); void ida_simple_remove(struct ida *ida, unsigned int id); static inline void ida_init(struct ida *ida) diff --git a/lib/idr.c b/lib/idr.c index 823b813f08f8..3374c3fa4027 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -599,6 +599,72 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, return ret; } EXPORT_SYMBOL(ida_simple_get); +/** + * ida_simple_get_cyclic - get a new id. + * @ida: the (initialized) ida. + * @start: the minimum id (inclusive, < 0x8000000) + * @end: the maximum id (exclusive, < 0x8000000 or 0) + * @gfp_mask: memory allocation flags + * + * Allocates an id in the range start <= id < end, or returns -ENOSPC. + * On memory allocation failure, returns -ENOMEM. + * The search for an unused id will start at the last id allocated and will + * wrap around to @start if no free ids are found before reaching @end. + * + * Compared to ida_get_new_above() this function does its own locking, and + * should be used unless there are special requirements. + * + * Use ida_simple_remove() to get rid of an id. + */ +int ida_simple_get_cyclic(struct ida *ida, unsigned int start, unsigned int end, + gfp_t gfp_mask) +{ + int ret, id, next; + unsigned int max; + unsigned long flags; + + WARN_ON((int)start < 0); + WARN_ON((int)end < 0); + + if (end == 0) { + max = 0x80000000; + } else { + WARN_ON(end < start); + max = end - 1; + } + +again: + if (!ida_pre_get(ida, gfp_mask)) + return -ENOMEM; + + spin_lock_irqsave(&simple_ida_lock, flags); + next = ida->ida_next; + if (next < start || next >= end) + next = start; + + ret = ida_get_new_above(ida, next, &id); + if (likely(!ret)) { + if (unlikely(id >= max)) { + ida_remove(ida, id); + if (next == start) { + ret = -ENOSPC; + } else { + ida->ida_next = start; + spin_unlock_irqrestore(&simple_ida_lock, flags); + goto again; + } + } else { + ida->ida_next = id + 1; + ret = id; + } + } + spin_unlock_irqrestore(&simple_ida_lock, flags); + + if (unlikely(ret == -EAGAIN)) + goto again; + return ret; +} +EXPORT_SYMBOL(ida_simple_get_cyclic); /** * ida_simple_remove - remove an allocated id. -- 2.14.3