Re: [PATCH 03/10] idr: Rewrite ida
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? Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 03/10] idr: Rewrite ida
This is a new, from scratch implementation of ida that should be
simpler, faster and more space efficient.
Two primary reasons for the rewrite:
* A future patch will reimplement idr on top of this ida implementation +
radix trees. Once that's done, the end result will be ~1k fewer lines
of code, much simpler and easier to understand and it should be quite
a bit faster.
* The performance improvements and addition of ganged allocation should
make ida more suitable for use by a percpu id/tag allocator, which
would then act as a frontend to this allocator.
The old ida implementation was done with the idr data structures - this
was IMO backwards. I'll soon be reimplementing idr on top of this new
ida implementation and radix trees - using a separate dedicated data
structure for the free ID bitmap should actually make idr faster, and
the end result is _significantly_ less code.
This implementation conceptually isn't that different from the old one -
it's a tree of bitmaps, where one bit in a given node indicates whether
or not there are free bits in a child node.
The main difference (and advantage) over the old version is that the
tree isn't implemented with pointers - it's implemented in an array,
like how heaps are implemented, which both better space efficiency and
it'll be faster since there's no pointer chasing. (It's not one giant
contiguous array, it's an array of arrays but the algorithm treats it as
one big array)
Time to allocate 1 << 24 ids: 0m0.663s
Time to allocate 1 << 24 ids, old code: 0m28.604s
Time to allocate INT_MAX ids: 1m41.371s
Time to allocate INT_MAX ids, old code: Got bored of waiting for it to finish.
Signed-off-by: Kent Overstreet
Cc: Andrew Morton
Cc: Tejun Heo
Cc: Stephen Rothwell
Cc: Fengguang Wu
---
include/linux/idr.h | 122 ---
lib/idr.c | 897 +++-
2 files changed, 691 insertions(+), 328 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index c0e0c54..a310bb0 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -16,6 +16,92 @@
#include
#include
#include
+#include
+#include
+
+/* IDA */
+
+struct ida {
+ spinlock_t lock;
+
+ /*
+* cur_id and allocated_ids are for ida_alloc_cyclic. For cyclic
+* allocations we search for new ids to allocate starting from the last
+* id allocated - cur_id is the next id to try allocating.
+*
+* But we also don't want the allocated ids to be arbitrarily sparse -
+* the memory usage for the bitmap could be arbitrarily bad, and if
+* they're used as keys in a radix tree the memory overhead of the radix
+* tree could be quite bad as well. So we use allocated_ids to decide
+* when to restart cur_id from 0, and bound how sparse the bitmap can
+* be.
+*/
+ unsignedcur_id;
+ unsignedallocated_ids;
+
+ /* size of ida->tree */
+ unsignednodes;
+
+ /*
+* Index of first leaf node in ida->tree; equal to the number of non
+* leaf nodes, ida->nodes - ida->first_leaf == number of leaf nodes
+*/
+ unsignedfirst_leaf;
+ unsignedsections;
+
+ unsigned long **tree;
+ unsigned long *inline_section;
+ unsigned long inline_node;
+};
+
+#define IDA_INIT(name) \
+{ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+ .nodes = 1,\
+ .first_leaf = 0,\
+ .sections = 1,\
+ .tree = _section, \
+ .inline_section = _node,\
+}
+#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
+
+void ida_remove(struct ida *ida, unsigned id);
+int ida_alloc_range(struct ida *ida, unsigned int start,
+ unsigned int end, gfp_t gfp);
+int ida_alloc_cyclic(struct ida *ida, unsigned start, unsigned end, gfp_t gfp);
+void ida_destroy(struct ida *ida);
+int ida_init_prealloc(struct ida *ida, unsigned prealloc);
+
+/**
+ * ida_alloc_range - allocate a new id.
+ * @ida: the (initialized) ida.
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range [0, INT_MAX]. Returns -ENOSPC if no ids are
+ * available, or -ENOMEM on memory allocation failure.
+ *
+ * Returns the smallest available id
+ *
+ * Use ida_remove() to get rid of an id.
+ */
+static inline int ida_alloc(struct ida *ida, gfp_t gfp_mask)
+{
+ return ida_alloc_range(ida, 0, 0, gfp_mask);
+}
+
+/**
+ * ida_init - initialize ida handle
+ * @ida: ida handle
+ *
+ * This function is use to set up the handle (@ida) that you will
[PATCH 03/10] idr: Rewrite ida
This is a new, from scratch implementation of ida that should be
simpler, faster and more space efficient.
Two primary reasons for the rewrite:
* A future patch will reimplement idr on top of this ida implementation +
radix trees. Once that's done, the end result will be ~1k fewer lines
of code, much simpler and easier to understand and it should be quite
a bit faster.
* The performance improvements and addition of ganged allocation should
make ida more suitable for use by a percpu id/tag allocator, which
would then act as a frontend to this allocator.
The old ida implementation was done with the idr data structures - this
was IMO backwards. I'll soon be reimplementing idr on top of this new
ida implementation and radix trees - using a separate dedicated data
structure for the free ID bitmap should actually make idr faster, and
the end result is _significantly_ less code.
This implementation conceptually isn't that different from the old one -
it's a tree of bitmaps, where one bit in a given node indicates whether
or not there are free bits in a child node.
The main difference (and advantage) over the old version is that the
tree isn't implemented with pointers - it's implemented in an array,
like how heaps are implemented, which both better space efficiency and
it'll be faster since there's no pointer chasing. (It's not one giant
contiguous array, it's an array of arrays but the algorithm treats it as
one big array)
Time to allocate 1 24 ids: 0m0.663s
Time to allocate 1 24 ids, old code: 0m28.604s
Time to allocate INT_MAX ids: 1m41.371s
Time to allocate INT_MAX ids, old code: Got bored of waiting for it to finish.
Signed-off-by: Kent Overstreet k...@daterainc.com
Cc: Andrew Morton a...@linux-foundation.org
Cc: Tejun Heo t...@kernel.org
Cc: Stephen Rothwell s...@canb.auug.org.au
Cc: Fengguang Wu fengguang...@intel.com
---
include/linux/idr.h | 122 ---
lib/idr.c | 897 +++-
2 files changed, 691 insertions(+), 328 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index c0e0c54..a310bb0 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -16,6 +16,92 @@
#include linux/bitops.h
#include linux/init.h
#include linux/rcupdate.h
+#include linux/spinlock_types.h
+#include linux/wait.h
+
+/* IDA */
+
+struct ida {
+ spinlock_t lock;
+
+ /*
+* cur_id and allocated_ids are for ida_alloc_cyclic. For cyclic
+* allocations we search for new ids to allocate starting from the last
+* id allocated - cur_id is the next id to try allocating.
+*
+* But we also don't want the allocated ids to be arbitrarily sparse -
+* the memory usage for the bitmap could be arbitrarily bad, and if
+* they're used as keys in a radix tree the memory overhead of the radix
+* tree could be quite bad as well. So we use allocated_ids to decide
+* when to restart cur_id from 0, and bound how sparse the bitmap can
+* be.
+*/
+ unsignedcur_id;
+ unsignedallocated_ids;
+
+ /* size of ida-tree */
+ unsignednodes;
+
+ /*
+* Index of first leaf node in ida-tree; equal to the number of non
+* leaf nodes, ida-nodes - ida-first_leaf == number of leaf nodes
+*/
+ unsignedfirst_leaf;
+ unsignedsections;
+
+ unsigned long **tree;
+ unsigned long *inline_section;
+ unsigned long inline_node;
+};
+
+#define IDA_INIT(name) \
+{ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+ .nodes = 1,\
+ .first_leaf = 0,\
+ .sections = 1,\
+ .tree = name.inline_section, \
+ .inline_section = name.inline_node,\
+}
+#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
+
+void ida_remove(struct ida *ida, unsigned id);
+int ida_alloc_range(struct ida *ida, unsigned int start,
+ unsigned int end, gfp_t gfp);
+int ida_alloc_cyclic(struct ida *ida, unsigned start, unsigned end, gfp_t gfp);
+void ida_destroy(struct ida *ida);
+int ida_init_prealloc(struct ida *ida, unsigned prealloc);
+
+/**
+ * ida_alloc_range - allocate a new id.
+ * @ida: the (initialized) ida.
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range [0, INT_MAX]. Returns -ENOSPC if no ids are
+ * available, or -ENOMEM on memory allocation failure.
+ *
+ * Returns the smallest available id
+ *
+ * Use ida_remove() to get rid of an id.
+ */
+static inline int ida_alloc(struct ida *ida, gfp_t gfp_mask)
+{
+
Re: [PATCH 03/10] idr: Rewrite ida
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? Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 03/10] idr: Rewrite ida
From: Kent Overstreet
This is a new, from scratch implementation of ida that should be
simpler, faster and more space efficient.
Two primary reasons for the rewrite:
* A future patch will reimplement idr on top of this ida implementation +
radix trees. Once that's done, the end result will be ~1k fewer lines
of code, much simpler and easier to understand and it should be quite
a bit faster.
* The performance improvements and addition of ganged allocation should
make ida more suitable for use by a percpu id/tag allocator, which
would then act as a frontend to this allocator.
The old ida implementation was done with the idr data structures - this
was IMO backwards. I'll soon be reimplementing idr on top of this new
ida implementation and radix trees - using a separate dedicated data
structure for the free ID bitmap should actually make idr faster, and
the end result is _significantly_ less code.
This implementation conceptually isn't that different from the old one -
it's a tree of bitmaps, where one bit in a given node indicates whether
or not there are free bits in a child node.
The main difference (and advantage) over the old version is that the
tree isn't implemented with pointers - it's implemented in an array,
like how heaps are implemented, which both better space efficiency and
it'll be faster since there's no pointer chasing. (It's not one giant
contiguous array, it's an array of arrays but the algorithm treats it as
one big array)
Time to allocate 1 << 24 ids: 0m0.663s
Time to allocate 1 << 24 ids, old code: 0m28.604s
Time to allocate INT_MAX ids: 1m41.371s
Time to allocate INT_MAX ids, old code: Got bored of waiting for it to finish.
Signed-off-by: Kent Overstreet
Cc: Andrew Morton
Cc: Tejun Heo
Cc: Stephen Rothwell
Cc: Fengguang Wu
Signed-off-by: Kent Overstreet
---
include/linux/idr.h | 122 ---
lib/idr.c | 894 +++-
2 files changed, 687 insertions(+), 329 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index c0e0c54..a310bb0 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -16,6 +16,92 @@
#include
#include
#include
+#include
+#include
+
+/* IDA */
+
+struct ida {
+ spinlock_t lock;
+
+ /*
+* cur_id and allocated_ids are for ida_alloc_cyclic. For cyclic
+* allocations we search for new ids to allocate starting from the last
+* id allocated - cur_id is the next id to try allocating.
+*
+* But we also don't want the allocated ids to be arbitrarily sparse -
+* the memory usage for the bitmap could be arbitrarily bad, and if
+* they're used as keys in a radix tree the memory overhead of the radix
+* tree could be quite bad as well. So we use allocated_ids to decide
+* when to restart cur_id from 0, and bound how sparse the bitmap can
+* be.
+*/
+ unsignedcur_id;
+ unsignedallocated_ids;
+
+ /* size of ida->tree */
+ unsignednodes;
+
+ /*
+* Index of first leaf node in ida->tree; equal to the number of non
+* leaf nodes, ida->nodes - ida->first_leaf == number of leaf nodes
+*/
+ unsignedfirst_leaf;
+ unsignedsections;
+
+ unsigned long **tree;
+ unsigned long *inline_section;
+ unsigned long inline_node;
+};
+
+#define IDA_INIT(name) \
+{ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+ .nodes = 1,\
+ .first_leaf = 0,\
+ .sections = 1,\
+ .tree = _section, \
+ .inline_section = _node,\
+}
+#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
+
+void ida_remove(struct ida *ida, unsigned id);
+int ida_alloc_range(struct ida *ida, unsigned int start,
+ unsigned int end, gfp_t gfp);
+int ida_alloc_cyclic(struct ida *ida, unsigned start, unsigned end, gfp_t gfp);
+void ida_destroy(struct ida *ida);
+int ida_init_prealloc(struct ida *ida, unsigned prealloc);
+
+/**
+ * ida_alloc_range - allocate a new id.
+ * @ida: the (initialized) ida.
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range [0, INT_MAX]. Returns -ENOSPC if no ids are
+ * available, or -ENOMEM on memory allocation failure.
+ *
+ * Returns the smallest available id
+ *
+ * Use ida_remove() to get rid of an id.
+ */
+static inline int ida_alloc(struct ida *ida, gfp_t gfp_mask)
+{
+ return ida_alloc_range(ida, 0, 0, gfp_mask);
+}
+
+/**
+ * ida_init - initialize ida handle
+ * @ida: ida handle
+ *
+ * This
[PATCH 03/10] idr: Rewrite ida
From: Kent Overstreet koverstr...@google.com
This is a new, from scratch implementation of ida that should be
simpler, faster and more space efficient.
Two primary reasons for the rewrite:
* A future patch will reimplement idr on top of this ida implementation +
radix trees. Once that's done, the end result will be ~1k fewer lines
of code, much simpler and easier to understand and it should be quite
a bit faster.
* The performance improvements and addition of ganged allocation should
make ida more suitable for use by a percpu id/tag allocator, which
would then act as a frontend to this allocator.
The old ida implementation was done with the idr data structures - this
was IMO backwards. I'll soon be reimplementing idr on top of this new
ida implementation and radix trees - using a separate dedicated data
structure for the free ID bitmap should actually make idr faster, and
the end result is _significantly_ less code.
This implementation conceptually isn't that different from the old one -
it's a tree of bitmaps, where one bit in a given node indicates whether
or not there are free bits in a child node.
The main difference (and advantage) over the old version is that the
tree isn't implemented with pointers - it's implemented in an array,
like how heaps are implemented, which both better space efficiency and
it'll be faster since there's no pointer chasing. (It's not one giant
contiguous array, it's an array of arrays but the algorithm treats it as
one big array)
Time to allocate 1 24 ids: 0m0.663s
Time to allocate 1 24 ids, old code: 0m28.604s
Time to allocate INT_MAX ids: 1m41.371s
Time to allocate INT_MAX ids, old code: Got bored of waiting for it to finish.
Signed-off-by: Kent Overstreet koverstr...@google.com
Cc: Andrew Morton a...@linux-foundation.org
Cc: Tejun Heo t...@kernel.org
Cc: Stephen Rothwell s...@canb.auug.org.au
Cc: Fengguang Wu fengguang...@intel.com
Signed-off-by: Kent Overstreet k...@daterainc.com
---
include/linux/idr.h | 122 ---
lib/idr.c | 894 +++-
2 files changed, 687 insertions(+), 329 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index c0e0c54..a310bb0 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -16,6 +16,92 @@
#include linux/bitops.h
#include linux/init.h
#include linux/rcupdate.h
+#include linux/spinlock_types.h
+#include linux/wait.h
+
+/* IDA */
+
+struct ida {
+ spinlock_t lock;
+
+ /*
+* cur_id and allocated_ids are for ida_alloc_cyclic. For cyclic
+* allocations we search for new ids to allocate starting from the last
+* id allocated - cur_id is the next id to try allocating.
+*
+* But we also don't want the allocated ids to be arbitrarily sparse -
+* the memory usage for the bitmap could be arbitrarily bad, and if
+* they're used as keys in a radix tree the memory overhead of the radix
+* tree could be quite bad as well. So we use allocated_ids to decide
+* when to restart cur_id from 0, and bound how sparse the bitmap can
+* be.
+*/
+ unsignedcur_id;
+ unsignedallocated_ids;
+
+ /* size of ida-tree */
+ unsignednodes;
+
+ /*
+* Index of first leaf node in ida-tree; equal to the number of non
+* leaf nodes, ida-nodes - ida-first_leaf == number of leaf nodes
+*/
+ unsignedfirst_leaf;
+ unsignedsections;
+
+ unsigned long **tree;
+ unsigned long *inline_section;
+ unsigned long inline_node;
+};
+
+#define IDA_INIT(name) \
+{ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+ .nodes = 1,\
+ .first_leaf = 0,\
+ .sections = 1,\
+ .tree = name.inline_section, \
+ .inline_section = name.inline_node,\
+}
+#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
+
+void ida_remove(struct ida *ida, unsigned id);
+int ida_alloc_range(struct ida *ida, unsigned int start,
+ unsigned int end, gfp_t gfp);
+int ida_alloc_cyclic(struct ida *ida, unsigned start, unsigned end, gfp_t gfp);
+void ida_destroy(struct ida *ida);
+int ida_init_prealloc(struct ida *ida, unsigned prealloc);
+
+/**
+ * ida_alloc_range - allocate a new id.
+ * @ida: the (initialized) ida.
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range [0, INT_MAX]. Returns -ENOSPC if no ids are
+ * available, or -ENOMEM on memory allocation failure.
+ *
+ * Returns the smallest available id
+ *
+ * Use
Re: [PATCH 03/10] idr: Rewrite ida
On Wed, Jun 19, 2013 at 04:38:36PM -0700, Kent Overstreet wrote: > On Wed, Jun 19, 2013 at 10:40:22AM +0100, Steven Whitehouse wrote: > > Millions of IDs is something that is fairly normal for DLM, since there > > will be two DLM locks per cached inode with GFS2 and people tend to use > > it on pretty large servers with lots of memory, > > Thanks, I wasn't aware of that. Is the 31 bits for the id limitation an > issue for you? While I'm at changing ids to longs should be fairly > trivial. There is a dlm_lkb struct in memory for each id, so 31 bits will not be a problem. Dave -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] idr: Rewrite ida
On Wed, Jun 19, 2013 at 04:38:36PM -0700, Kent Overstreet wrote: On Wed, Jun 19, 2013 at 10:40:22AM +0100, Steven Whitehouse wrote: Millions of IDs is something that is fairly normal for DLM, since there will be two DLM locks per cached inode with GFS2 and people tend to use it on pretty large servers with lots of memory, Thanks, I wasn't aware of that. Is the 31 bits for the id limitation an issue for you? While I'm at changing ids to longs should be fairly trivial. There is a dlm_lkb struct in memory for each id, so 31 bits will not be a problem. Dave -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] idr: Rewrite ida
On Wed, Jun 19, 2013 at 10:40:22AM +0100, Steven Whitehouse wrote: > Hi, > > On Tue, 2013-06-18 at 17:02 -0700, Kent Overstreet wrote: > > This is a new, from scratch implementation of ida that should be > > simpler, faster and more space efficient. > > > [...] > > > > > This does mean that the entire bitmap is stored in one contiguous memory > > allocation - and as currently implemented we won't be able to allocate > > _quite_ as many ids as with the previous implementation. > > > > I don't expect this to be an issue in practice since anywhere this is > > used, an id corresponds to a struct allocation somewher else - we can't > > allocate an unbounded number of ids, we'll run out of memory somewhere > > else eventually, and I expect that to be the limiting factor in > > practice. > > > > If a user/use case does come up where this matters I can add some > > sharding (or perhaps add a separate big_ida implementation) - but the > > extra complexity would adversely affect performance for the users that > > don't need > millions of ids, so I intend to leave the implementation as > > is until if and when this becomes an issue. > > > > Millions of IDs is something that is fairly normal for DLM, since there > will be two DLM locks per cached inode with GFS2 and people tend to use > it on pretty large servers with lots of memory, Thanks, I wasn't aware of that. Is the 31 bits for the id limitation an issue for you? While I'm at changing ids to longs should be fairly trivial. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] idr: Rewrite ida
Hi, On Tue, 2013-06-18 at 17:02 -0700, Kent Overstreet wrote: > This is a new, from scratch implementation of ida that should be > simpler, faster and more space efficient. > [...] > > This does mean that the entire bitmap is stored in one contiguous memory > allocation - and as currently implemented we won't be able to allocate > _quite_ as many ids as with the previous implementation. > > I don't expect this to be an issue in practice since anywhere this is > used, an id corresponds to a struct allocation somewher else - we can't > allocate an unbounded number of ids, we'll run out of memory somewhere > else eventually, and I expect that to be the limiting factor in > practice. > > If a user/use case does come up where this matters I can add some > sharding (or perhaps add a separate big_ida implementation) - but the > extra complexity would adversely affect performance for the users that > don't need > millions of ids, so I intend to leave the implementation as > is until if and when this becomes an issue. > Millions of IDs is something that is fairly normal for DLM, since there will be two DLM locks per cached inode with GFS2 and people tend to use it on pretty large servers with lots of memory, Steve. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] idr: Rewrite ida
Hi, On Tue, 2013-06-18 at 17:02 -0700, Kent Overstreet wrote: This is a new, from scratch implementation of ida that should be simpler, faster and more space efficient. [...] This does mean that the entire bitmap is stored in one contiguous memory allocation - and as currently implemented we won't be able to allocate _quite_ as many ids as with the previous implementation. I don't expect this to be an issue in practice since anywhere this is used, an id corresponds to a struct allocation somewher else - we can't allocate an unbounded number of ids, we'll run out of memory somewhere else eventually, and I expect that to be the limiting factor in practice. If a user/use case does come up where this matters I can add some sharding (or perhaps add a separate big_ida implementation) - but the extra complexity would adversely affect performance for the users that don't need millions of ids, so I intend to leave the implementation as is until if and when this becomes an issue. Millions of IDs is something that is fairly normal for DLM, since there will be two DLM locks per cached inode with GFS2 and people tend to use it on pretty large servers with lots of memory, Steve. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 03/10] idr: Rewrite ida
On Wed, Jun 19, 2013 at 10:40:22AM +0100, Steven Whitehouse wrote: Hi, On Tue, 2013-06-18 at 17:02 -0700, Kent Overstreet wrote: This is a new, from scratch implementation of ida that should be simpler, faster and more space efficient. [...] This does mean that the entire bitmap is stored in one contiguous memory allocation - and as currently implemented we won't be able to allocate _quite_ as many ids as with the previous implementation. I don't expect this to be an issue in practice since anywhere this is used, an id corresponds to a struct allocation somewher else - we can't allocate an unbounded number of ids, we'll run out of memory somewhere else eventually, and I expect that to be the limiting factor in practice. If a user/use case does come up where this matters I can add some sharding (or perhaps add a separate big_ida implementation) - but the extra complexity would adversely affect performance for the users that don't need millions of ids, so I intend to leave the implementation as is until if and when this becomes an issue. Millions of IDs is something that is fairly normal for DLM, since there will be two DLM locks per cached inode with GFS2 and people tend to use it on pretty large servers with lots of memory, Thanks, I wasn't aware of that. Is the 31 bits for the id limitation an issue for you? While I'm at changing ids to longs should be fairly trivial. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 03/10] idr: Rewrite ida
This is a new, from scratch implementation of ida that should be
simpler, faster and more space efficient.
Two primary reasons for the rewrite:
* A future patch will reimplement idr on top of this ida implementation +
radix trees. Once that's done, the end result will be ~1k fewer lines
of code, much simpler and easier to understand and it should be quite
a bit faster.
* The performance improvements and addition of ganged allocation should
make ida more suitable for use by a percpu id/tag allocator, which
would then act as a frontend to this allocator.
The old ida implementation was done with the idr data structures - this
was IMO backwards. I'll soon be reimplementing idr on top of this new
ida implementation and radix trees - using a separate dedicated data
structure for the free ID bitmap should actually make idr faster, and
the end result is _significantly_ less code.
This implementation conceptually isn't that different from the old one -
it's a tree of bitmaps, where one bit in a given node indicates whether
or not there are free bits in a child node.
The main difference (and advantage) over the old version is that the
tree isn't implemented with pointers - it's implemented in an array,
like how heaps are implemented, which both better space efficiency and
it'll be faster since there's no pointer chasing.
This does mean that the entire bitmap is stored in one contiguous memory
allocation - and as currently implemented we won't be able to allocate
_quite_ as many ids as with the previous implementation.
I don't expect this to be an issue in practice since anywhere this is
used, an id corresponds to a struct allocation somewher else - we can't
allocate an unbounded number of ids, we'll run out of memory somewhere
else eventually, and I expect that to be the limiting factor in
practice.
If a user/use case does come up where this matters I can add some
sharding (or perhaps add a separate big_ida implementation) - but the
extra complexity would adversely affect performance for the users that
don't need > millions of ids, so I intend to leave the implementation as
is until if and when this becomes an issue.
Signed-off-by: Kent Overstreet
Cc: Andrew Morton
Cc: Tejun Heo
Cc: Stephen Rothwell
Cc: Fengguang Wu
---
include/linux/idr.h | 118 +---
lib/idr.c | 776 +---
2 files changed, 573 insertions(+), 321 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index c0e0c54..a78cf99 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -17,6 +17,88 @@
#include
#include
+/* IDA */
+
+#define IDA_INLINE_NODES 1
+
+struct ida {
+ spinlock_t lock;
+
+ /*
+* cur_id and allocated_ids are for ida_alloc_cyclic. For cyclic
+* allocations we search for new ids to allocate starting from the last
+* id allocated - cur_id is the next id to try allocating.
+*
+* But we also don't want the allocated ids to be arbitrarily sparse -
+* the memory usage for the bitmap could be arbitrarily bad, and if
+* they're used as keys in a radix tree the memory overhead of the radix
+* tree could be quite bad as well. So we use allocated_ids to decide
+* when to restart cur_id from 0, and bound how sparse the bitmap can
+* be.
+*/
+ unsignedcur_id;
+ unsignedallocated_ids;
+
+ /* size of ida->tree */
+ unsignednodes;
+
+ /*
+* Index of first leaf node in ida->tree; equal to the number of non
+* leaf nodes, ida->nodes - ida->first_leaf == number of leaf nodes
+*/
+ unsignedfirst_leaf;
+
+ unsigned long *tree;
+ unsigned long inline_nodes[IDA_INLINE_NODES];
+};
+
+#define IDA_INIT(name) \
+{ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+ .nodes = IDA_INLINE_NODES, \
+ .first_leaf = 1,\
+ .tree = name.inline_nodes,\
+}
+#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
+
+void ida_remove(struct ida *ida, unsigned id);
+int ida_alloc_range(struct ida *ida, unsigned int start,
+ unsigned int end, gfp_t gfp);
+int ida_alloc_cyclic(struct ida *ida, unsigned start, unsigned end, gfp_t gfp);
+void ida_destroy(struct ida *ida);
+int ida_init_prealloc(struct ida *ida, unsigned prealloc);
+
+/**
+ * ida_alloc_range - allocate a new id.
+ * @ida: the (initialized) ida.
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range [0, INT_MAX]. Returns -ENOSPC if no ids are
+ * available, or -ENOMEM on memory allocation failure.
+ *
+ * Returns the smallest available id
+ *
+ * Use
[PATCH 03/10] idr: Rewrite ida
This is a new, from scratch implementation of ida that should be
simpler, faster and more space efficient.
Two primary reasons for the rewrite:
* A future patch will reimplement idr on top of this ida implementation +
radix trees. Once that's done, the end result will be ~1k fewer lines
of code, much simpler and easier to understand and it should be quite
a bit faster.
* The performance improvements and addition of ganged allocation should
make ida more suitable for use by a percpu id/tag allocator, which
would then act as a frontend to this allocator.
The old ida implementation was done with the idr data structures - this
was IMO backwards. I'll soon be reimplementing idr on top of this new
ida implementation and radix trees - using a separate dedicated data
structure for the free ID bitmap should actually make idr faster, and
the end result is _significantly_ less code.
This implementation conceptually isn't that different from the old one -
it's a tree of bitmaps, where one bit in a given node indicates whether
or not there are free bits in a child node.
The main difference (and advantage) over the old version is that the
tree isn't implemented with pointers - it's implemented in an array,
like how heaps are implemented, which both better space efficiency and
it'll be faster since there's no pointer chasing.
This does mean that the entire bitmap is stored in one contiguous memory
allocation - and as currently implemented we won't be able to allocate
_quite_ as many ids as with the previous implementation.
I don't expect this to be an issue in practice since anywhere this is
used, an id corresponds to a struct allocation somewher else - we can't
allocate an unbounded number of ids, we'll run out of memory somewhere
else eventually, and I expect that to be the limiting factor in
practice.
If a user/use case does come up where this matters I can add some
sharding (or perhaps add a separate big_ida implementation) - but the
extra complexity would adversely affect performance for the users that
don't need millions of ids, so I intend to leave the implementation as
is until if and when this becomes an issue.
Signed-off-by: Kent Overstreet koverstr...@google.com
Cc: Andrew Morton a...@linux-foundation.org
Cc: Tejun Heo t...@kernel.org
Cc: Stephen Rothwell s...@canb.auug.org.au
Cc: Fengguang Wu fengguang...@intel.com
---
include/linux/idr.h | 118 +---
lib/idr.c | 776 +---
2 files changed, 573 insertions(+), 321 deletions(-)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index c0e0c54..a78cf99 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -17,6 +17,88 @@
#include linux/init.h
#include linux/rcupdate.h
+/* IDA */
+
+#define IDA_INLINE_NODES 1
+
+struct ida {
+ spinlock_t lock;
+
+ /*
+* cur_id and allocated_ids are for ida_alloc_cyclic. For cyclic
+* allocations we search for new ids to allocate starting from the last
+* id allocated - cur_id is the next id to try allocating.
+*
+* But we also don't want the allocated ids to be arbitrarily sparse -
+* the memory usage for the bitmap could be arbitrarily bad, and if
+* they're used as keys in a radix tree the memory overhead of the radix
+* tree could be quite bad as well. So we use allocated_ids to decide
+* when to restart cur_id from 0, and bound how sparse the bitmap can
+* be.
+*/
+ unsignedcur_id;
+ unsignedallocated_ids;
+
+ /* size of ida-tree */
+ unsignednodes;
+
+ /*
+* Index of first leaf node in ida-tree; equal to the number of non
+* leaf nodes, ida-nodes - ida-first_leaf == number of leaf nodes
+*/
+ unsignedfirst_leaf;
+
+ unsigned long *tree;
+ unsigned long inline_nodes[IDA_INLINE_NODES];
+};
+
+#define IDA_INIT(name) \
+{ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+ .nodes = IDA_INLINE_NODES, \
+ .first_leaf = 1,\
+ .tree = name.inline_nodes,\
+}
+#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
+
+void ida_remove(struct ida *ida, unsigned id);
+int ida_alloc_range(struct ida *ida, unsigned int start,
+ unsigned int end, gfp_t gfp);
+int ida_alloc_cyclic(struct ida *ida, unsigned start, unsigned end, gfp_t gfp);
+void ida_destroy(struct ida *ida);
+int ida_init_prealloc(struct ida *ida, unsigned prealloc);
+
+/**
+ * ida_alloc_range - allocate a new id.
+ * @ida: the (initialized) ida.
+ * @gfp_mask: memory allocation flags
+ *
+ * Allocates an id in the range [0, INT_MAX]. Returns
