diff mbox series

[7/9] ida: introduce ida_max() to return the maximum allocated ID

Message ID 20210428094949.43579-8-songmuchun@bytedance.com (mailing list archive)
State New, archived
Headers show
Series Shrink the list lru size on memory cgroup removal | expand

Commit Message

Muchun Song April 28, 2021, 9:49 a.m. UTC 
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(+)

Comments

Christoph Hellwig April 29, 2021, 6:47 a.m. UTC | #1 
On Wed, Apr 28, 2021 at 05:49:47PM +0800, Muchun Song wrote:
> Introduce ida_max() to return the maximum allocated ID. This will be
> used by memory cgroup in the later patch.

Please also add a lower-level xa_max as this funcationalty would also
come in handy at the xarray level in a few places.
Muchun Song April 29, 2021, 7:36 a.m. UTC | #2 
On Thu, Apr 29, 2021 at 2:49 PM Christoph Hellwig <hch@infradead.org> wrote:
>
> On Wed, Apr 28, 2021 at 05:49:47PM +0800, Muchun Song wrote:
> > Introduce ida_max() to return the maximum allocated ID. This will be
> > used by memory cgroup in the later patch.
>
> Please also add a lower-level xa_max as this funcationalty would also
> come in handy at the xarray level in a few places.

Good suggestion. This way is also efficient. Thanks.
diff mbox series

Patch

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)