LKML Archive on lore.kernel.org
help / color / mirror / Atom feed
From: Hans Westgaard Ry <hans.westgaard.ry@oracle.com>
To: Doug Ledford <dledford@redhat.com>,
	Jason Gunthorpe <jgg@ziepe.ca>,
	Hakon Bugge <haakon.bugge@oracle.com>,
	Parav Pandit <parav@mellanox.com>,
	Jack Morgenstein <jackm@dev.mellanox.co.il>,
	Pravin Shedge <pravin.shedge4linux@gmail.com>,
	Matthew Wilcox <mawilcox@microsoft.com>,
	Andrew Morton <akpm@linux-foundation.org>,
	Jeff Layton <jlayton@kernel.org>, Wei Wang <wei.w.wang@intel.com>,
	Chris Mi <chrism@mellanox.com>,
	Eric Biggers <ebiggers@google.com>,
	Rasmus Villemoes <linux@rasmusvillemoes.dk>,
	Mel Gorman <mgorman@techsingularity.net>,
	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	[thread overview]
Message-ID: <20180607105208.16332-2-hans.westgaard.ry@oracle.com> (raw)
In-Reply-To: <20180607105208.16332-1-hans.westgaard.ry@oracle.com>

Orabug: 25571450

Signed-off-by: Hans Westgaard Ry <hans.westgaard.ry@oracle.com>
---
 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

  reply	other threads:[~2018-06-07 10:53 UTC|newest]

Thread overview: 24+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-05-29  7:38 [PATCH] IB/mad: Use ID allocator routines to allocate agent number Hans Westgaard Ry
2018-05-29  8:54 ` Leon Romanovsky
2018-05-29  9:54   ` Leon Romanovsky
2018-05-30  8:18     ` jackm
2018-05-29 15:49 ` Jason Gunthorpe
2018-05-29 16:16   ` Håkon Bugge
2018-05-29 16:40     ` Jason Gunthorpe
2018-05-30  7:32       ` Håkon Bugge
2018-05-30 15:15         ` Jason Gunthorpe
2018-05-30  8:02       ` jackm
2018-05-30 12:22         ` Hans Westgaard Ry
2018-05-30 15:10           ` Jason Gunthorpe
2018-05-30 20:07             ` Håkon Bugge
2018-05-30 22:09               ` Jason Gunthorpe
2018-05-31 19:54                 ` Håkon Bugge
2018-06-07 10:52 ` [PATCH v2 0/2] IB:mad " Hans Westgaard Ry
2018-06-07 10:52   ` Hans Westgaard Ry [this message]
2018-06-07 10:52   ` [PATCH v2 2/2] IB/mad: " Hans Westgaard Ry
2018-06-07 11:14 ` [PATCH v3 0/2] IB:mad " Hans Westgaard Ry
2018-06-07 11:14   ` [PATCH v3 1/2] idr: Add ida_simple_get_cyclic Hans Westgaard Ry
2018-06-07 18:50     ` Jason Gunthorpe
2018-06-07 11:14   ` [PATCH v3 2/2] IB/mad: Use ID allocator routines to allocate agent number Hans Westgaard Ry
2018-06-07 15:37     ` Matthew Wilcox
2018-06-07 17:59       ` Håkon Bugge

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180607105208.16332-2-hans.westgaard.ry@oracle.com \
    --to=hans.westgaard.ry@oracle.com \
    --cc=akpm@linux-foundation.org \
    --cc=chrism@mellanox.com \
    --cc=dledford@redhat.com \
    --cc=ebiggers@google.com \
    --cc=haakon.bugge@oracle.com \
    --cc=jackm@dev.mellanox.co.il \
    --cc=jgg@ziepe.ca \
    --cc=jlayton@kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-rdma@vger.kernel.org \
    --cc=linux@rasmusvillemoes.dk \
    --cc=mawilcox@microsoft.com \
    --cc=mgorman@techsingularity.net \
    --cc=parav@mellanox.com \
    --cc=pravin.shedge4linux@gmail.com \
    --cc=wei.w.wang@intel.com \
    --subject='Re: [PATCH v2 1/2] idr: Add ida_simple_get_cyclic' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).