Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   Muchun Song <songmuchun@bytedance.com>
To:     willy@infradead.org, akpm@linux-foundation.org, hannes@cmpxchg.org,
        mhocko@kernel.org, vdavydov.dev@gmail.com, shakeelb@google.com,
        guro@fb.com, shy828301@gmail.com, alexs@kernel.org,
        alexander.h.duyck@linux.intel.com, richard.weiyang@gmail.com
Cc:     linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
        linux-mm@kvack.org, Muchun Song <songmuchun@bytedance.com>
Subject: [PATCH 7/9] ida: introduce ida_max() to return the maximum allocated ID
Date:   Wed, 28 Apr 2021 17:49:47 +0800
Message-Id: <20210428094949.43579-8-songmuchun@bytedance.com>
In-Reply-To: <20210428094949.43579-1-songmuchun@bytedance.com>
References: <20210428094949.43579-1-songmuchun@bytedance.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

Introduce ida_max() to return the maximum allocated ID. This will be
used by memory cgroup in the later patch.

Signed-off-by: Muchun Song <songmuchun@bytedance.com>
---
 include/linux/idr.h |  1 +
 lib/idr.c           | 40 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 41 insertions(+)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index a0dce14090a9..c3968a6348d1 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -255,6 +255,7 @@ struct ida {
 int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
 void ida_free(struct ida *, unsigned int id);
 void ida_destroy(struct ida *ida);
+int ida_max(struct ida *ida);
 
 /**
  * ida_alloc() - Allocate an unused ID.
diff --git a/lib/idr.c b/lib/idr.c
index f4ab4f4aa3c7..bcfcaae89aa7 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -553,6 +553,46 @@ void ida_destroy(struct ida *ida)
 }
 EXPORT_SYMBOL(ida_destroy);
 
+/**
+ * ida_max() - Return the maximum allocated ID.
+ * @ida: IDA handle.
+ *
+ * Context: Any context. It is safe to call this function without
+ * locking in your code.
+ *
+ * Return: The maximum allocated ID, or %-ENOSPC if the @ida is empty
+ */
+int ida_max(struct ida *ida)
+{
+	XA_STATE(xas, &ida->xa, 0);
+	struct ida_bitmap *curr, *prev;
+	unsigned long flags;
+	unsigned int bit, index;
+
+	xas_lock_irqsave(&xas, flags);
+	if (ida_is_empty(ida)) {
+		xas_unlock_irqrestore(&xas, flags);
+		return -ENOSPC;
+	}
+
+	xas_for_each(&xas, curr, ULONG_MAX) {
+		prev = curr;
+		index = xas.xa_index;
+	}
+
+	if (xa_is_value(prev)) {
+		unsigned long val = xa_to_value(prev);
+
+		bit = find_last_bit(&val, BITS_PER_XA_VALUE);
+	} else {
+		bit = find_last_bit(prev->bitmap, IDA_BITMAP_BITS);
+	}
+
+	xas_unlock_irqrestore(&xas, flags);
+
+	return index * IDA_BITMAP_BITS + bit;
+}
+
 #ifndef __KERNEL__
 extern void xa_dump_index(unsigned long index, unsigned int shift);
 #define IDA_CHUNK_SHIFT		ilog2(IDA_BITMAP_BITS)
-- 
2.11.0