Re: [PATCH] idr: Document ida tree sections

[Kent Overstreet <kmo@daterainc.com>]

On Fri, Aug 09, 2013 at 10:57:56AM -0400, Tejun Heo wrote:
> Hello,
> 
> On Wed, Aug 07, 2013 at 01:51:17PM -0700, Kent Overstreet wrote:
> > + * So if the max section size is 64k, that's ~4096 sections, with 8 byte
> > + * pointers that's a little over 32k for the pointers to sections.
> > + *
> > + * That means max size sections are order 4 page allocations.
> 
> Order 4 allocations for common data structure doesn't really sound
> like a good idea to me.  It's gonna work fine on relatively large
> machines but suck on mobile / small embedded devices, many of which
> are still struggling with 32bit address space and compaction may not
> be enabled.  It just doens't make sense to me to impose 64k
> allocations from low level library function like ida.

Would this be an acceptable solution?

>From 483cfa0c809b7dc3b0abad93407468f273416578 Mon Sep 17 00:00:00 2001
From: Kent Overstreet <kmo@daterainc.com>
Date: Tue, 13 Aug 2013 15:31:20 -0700
Subject: [PATCH] ida: Use order 2 allocations when COMPACTION=n

And fall back to vmalloc for the array of pointers to sections so we can
still allocate up to INT_MAX ids.

diff --git a/lib/idr.c b/lib/idr.c
index 02a221c..3bffb52 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -21,16 +21,20 @@
 #include <linux/export.h>
 #include <linux/idr.h>
 #include <linux/kernel.h>
+#include <linux/mm.h>
 #include <linux/percpu.h>
 #include <linux/rcupdate.h>
 #include <linux/sched.h>
 #include <linux/slab.h>
 #include <linux/string.h>
 #include <linux/spinlock.h>
+#include <linux/vmalloc.h>
 
 static void kgfree(void *ptr, size_t size)
 {
-	if (size < PAGE_SIZE)
+	if (is_vmalloc_addr(ptr))
+		vfree(ptr);
+	else if (size < PAGE_SIZE)
 		kfree(ptr);
 	else
 		free_pages((unsigned long) ptr, get_order(size));
@@ -102,7 +106,14 @@ static void *kgalloc(size_t size, gfp_t gfp)
  */
 
 #define IDA_TREE_ARY		BITS_PER_LONG
-#define IDA_SECTION_SIZE	(64UL << 10)
+
+/* Max section size, in bytes */
+#ifdef CONFIG_COMPACTION
+#define IDA_SECTION_SIZE	(64UL << 10) /* order 4 page allocation */
+#else
+#define IDA_SECTION_SIZE	(16UL << 10) /* order 2 */
+#endif
+
 #define IDA_NODES_PER_SECTION	(IDA_SECTION_SIZE / sizeof(unsigned long))
 
 static inline unsigned long *ida_index_to_node(struct ida *ida, unsigned node)
@@ -251,8 +262,15 @@ again:
 
 	if (ida->nodes >= IDA_NODES_PER_SECTION &&
 	    is_power_of_2(cur_sections)) {
-		sections = kgalloc(cur_sections * 2 * sizeof(unsigned long *),
-				   __GFP_ZERO|gfp);
+		size_t bytes = cur_sections * 2 * sizeof(unsigned long *);
+
+		if (bytes <= IDA_SECTION_SIZE)
+			sections = kgalloc(bytes, __GFP_ZERO|gfp);
+		else if (gfp & GFP_KERNEL)
+			sections = vzalloc(bytes);
+		else
+			sections = NULL;
+
 		if (!sections)
 			goto err;
 	}