lkml.org 
[lkml]   [2013]   [Aug]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH] idr: Document ida tree sections
On Wed, Aug 07, 2013 at 04:22:01PM -0400, Tejun Heo wrote:
> Hello, Kent.
>
> On Wed, Aug 07, 2013 at 10:34:58AM -0700, Kent Overstreet wrote:
> > + * So for 1 mb of memory (and allocating more than that should be fine with
> > + * CONFIG_COMPACTION) you get slightly under 8 million IDs.
>
> Nothing seems to explain the section thing. This is broken up now,
> right? Where's the documentation?

Whoops, yes. As usual with the documentation...

Here's a fixup patch for that:

From c24de588c5f31fa77fb8fcbf4c457b32062fee0c Mon Sep 17 00:00:00 2001
From: Kent Overstreet <kmo@daterainc.com>
Date: Wed, 7 Aug 2013 13:50:42 -0700
Subject: [PATCH] idr: Document ida tree sections


diff --git a/lib/idr.c b/lib/idr.c
index 320ffea..02a221c 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -72,18 +72,37 @@ static void *kgalloc(size_t size, gfp_t gfp)
* the bit for id i is bit id % BITS_PER_LONG in ida->tree[ida->first_leaf + i /
* BITS_PER_LONG].
*
- * Note that the number of ids we can allocate is limited by the amount of
- * memory we can contiguously allocate. The amount of memory used for the bitmap
- * tree is only slightly more than a flat bitmap would use - about 1 / TREE_ARY
- * * (sizeof flat bitmap).
+ * That last line of code is a lie - logically, the data structure is one flat
+ * array - but to avoid giant contiguous allocations we use an array of arrays -
+ * ida_index_to_node() replaces the array lookup in the above example.
*
- * So for 1 mb of memory (and allocating more than that should be fine with
- * CONFIG_COMPACTION) you get slightly under 8 million IDs.
+ * So ida->tree is an array of pointers to sections, where the sections are
+ * different segments of the array the bitmap tree lives in.
+ *
+ * If there's a single section, it's only as big as we need it to be, and we
+ * grow the bitmap tree by doubling the size of the allocation.
+ *
+ * Once the tree is big enough that we start using multiple sections, the
+ * sections are always the same size - the max section size - and we grow the
+ * tree by appending new sections.
+ *
+ * The maximum size of the bitmap tree is when we've allocated all the way up to
+ * INT_MAX ids; we need (INT_MAX / 8) bytes of memory for the leaves, plus a
+ * couple percent for the parent nodes (since TREE_ARY == BITS_PER_LONG the
+ * parent nodes only add around 2%).
+ *
+ * So that's ~256 mb of memory max; we pick the max section size such that the
+ * max size of the array of pointers to sections isn't any bigger than the max
+ * section size.
+ *
+ * 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.
*/

#define IDA_TREE_ARY BITS_PER_LONG
-#define IDA_ALLOC_ORDER_MAX 4
-#define IDA_SECTION_SIZE (PAGE_SIZE << IDA_ALLOC_ORDER_MAX)
+#define IDA_SECTION_SIZE (64UL << 10)
#define IDA_NODES_PER_SECTION (IDA_SECTION_SIZE / sizeof(unsigned long))

static inline unsigned long *ida_index_to_node(struct ida *ida, unsigned node)

\
 
 \ /
  Last update: 2013-08-08 00:21    [W:0.091 / U:0.172 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site