On Mon, Feb 04, 2013 at 09:11:28AM -0800, Tejun Heo wrote:
> On Mon, Feb 04, 2013 at 09:10:31AM -0800, Tejun Heo wrote:
> > Yeah, that should be easily convertable to the new interface. How
> > should we route these changes? Your patch can go through the usual
> > nfs channel and the conversion and deprecation patches can be held off
> > until after -rc1. Does that sound okay?
>
> Ooh, BTW, the cyclic allocation is broken. It's prone to -ENOSPC
> after the first wraparound. There are several cyclic users in the
> kernel and I think it probably would be best to implement cyclic
> support in idr.
Are you looking at this, by the way, or do you have any suggestions?
Wondering if it's something I should try to fix or if I should look into
converting to some other data structure here.
--b.
Hello,
On Thu, Mar 21, 2013 at 10:06:18AM -0400, J. Bruce Fields wrote:
> > Ooh, BTW, the cyclic allocation is broken. It's prone to -ENOSPC
> > after the first wraparound. There are several cyclic users in the
> > kernel and I think it probably would be best to implement cyclic
> > support in idr.
>
> Are you looking at this, by the way, or do you have any suggestions?
>
> Wondering if it's something I should try to fix or if I should look into
> converting to some other data structure here.
I am not working on it at the moment but I think the logical thing to
do would be implementing cyclic support in idr and enabling it with,
say, a different initializer - IDR_CYCLIC_INIT() or something. If you
wanna fix it, please go ahead. :)
Thanks.
--
tejun
On Thu, 21 Mar 2013 11:35:13 -0700
Tejun Heo <[email protected]> wrote:
> Hello,
>
> On Thu, Mar 21, 2013 at 10:06:18AM -0400, J. Bruce Fields wrote:
> > > Ooh, BTW, the cyclic allocation is broken. It's prone to -ENOSPC
> > > after the first wraparound. There are several cyclic users in the
> > > kernel and I think it probably would be best to implement cyclic
> > > support in idr.
> >
> > Are you looking at this, by the way, or do you have any suggestions?
> >
> > Wondering if it's something I should try to fix or if I should look into
> > converting to some other data structure here.
>
> I am not working on it at the moment but I think the logical thing to
> do would be implementing cyclic support in idr and enabling it with,
> say, a different initializer - IDR_CYCLIC_INIT() or something. If you
> wanna fix it, please go ahead. :)
>
> Thanks.
>
So, here's a first (very rough, completely untested) pass at fixing
this for cyclic allocations. This looks like it'll probably fix the
ENOSPC errors when the counter wraps.
I'm not sure this is really what's needed though.
Suppose we have a situation where most of the currently allocated IDs
are clustered near the top of the range. When the counter wraps and we
call idr_alloc with a low start value, won't it prefer to allocate from
an existing layer instead of creating a new one?
If so, then means that after the counter wraps, it can skip over all of
the low values and reuse a more recently used high value. Is that OK
for the existing cyclic users? Or do we need to do something more
elaborate to make it prefer IDs at the low ranges after the counter
wraps?
-------------------[snip]--------------------
[PATCH] idr: introduce idr_alloc_cyclic
Thus spake Tejun Heo:
Ooh, BTW, the cyclic allocation is broken. It's prone to -ENOSPC
after the first wraparound. There are several cyclic users in the
kernel and I think it probably would be best to implement cyclic
support in idr.
This patch does that by adding new idr_alloc_cyclic function that
such users in the kernel can use. The idea here is that the caller will
keep a static counter of some sort that we can use to track where
the next "start" value should be on the next allocation.
Signed-off-by: Jeff Layton <[email protected]>
---
include/linux/idr.h | 1 +
lib/idr.c | 27 +++++++++++++++++++++++++++
2 files changed, 28 insertions(+)
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 2640c7e..c6ac330 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -75,6 +75,7 @@ struct idr {
void *idr_find_slowpath(struct idr *idp, int id);
void idr_preload(gfp_t gfp_mask);
int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
+int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, int *cur, gfp_t gfp_mask);
int idr_for_each(struct idr *idp,
int (*fn)(int id, void *p, void *data), void *data);
void *idr_get_next(struct idr *idp, int *nextid);
diff --git a/lib/idr.c b/lib/idr.c
index 322e281..d835dba 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -495,6 +495,33 @@ int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
}
EXPORT_SYMBOL_GPL(idr_alloc);
+/**
+ * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion
+ * @idr: the (initialized) idr
+ * @ptr: pointer to be associated with the new id
+ * @start: the minimum id (inclusive)
+ * @end: the maximum id (exclusive, <= 0 for max)
+ * @cur: ptr to current position in the range (typically, last allocated + 1)
+ * @gfp_mask: memory allocation flags
+ *
+ * Essentially the same as idr_alloc, but prefers to allocate progressively
+ * higher ids if it can. If the "cur" counter wraps, then it will start again
+ * at the "start" end of the range and allocate one that has already been used.
+ */
+int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, int *cur,
+ gfp_t gfp_mask)
+{
+ int id;
+
+ id = idr_alloc(idr, ptr, *cur, end, gfp_mask);
+ if (id == -ENOSPC)
+ id = idr_alloc(idr, ptr, start, end, gfp_mask);
+
+ if (likely(id >= 0))
+ *cur = id + 1;
+ return id;
+}
+
static void idr_remove_warning(int id)
{
printk(KERN_WARNING
--
1.7.11.7
Hello, Jeff.
On Tue, Mar 26, 2013 at 11:19:36AM -0400, Jeff Layton wrote:
> +/**
> + * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion
> + * @idr: the (initialized) idr
> + * @ptr: pointer to be associated with the new id
> + * @start: the minimum id (inclusive)
> + * @end: the maximum id (exclusive, <= 0 for max)
> + * @cur: ptr to current position in the range (typically, last allocated + 1)
> + * @gfp_mask: memory allocation flags
> + *
> + * Essentially the same as idr_alloc, but prefers to allocate progressively
> + * higher ids if it can. If the "cur" counter wraps, then it will start again
> + * at the "start" end of the range and allocate one that has already been used.
> + */
> +int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, int *cur,
> + gfp_t gfp_mask)
> +{
> + int id;
> +
> + id = idr_alloc(idr, ptr, *cur, end, gfp_mask);
> + if (id == -ENOSPC)
> + id = idr_alloc(idr, ptr, start, end, gfp_mask);
> +
> + if (likely(id >= 0))
> + *cur = id + 1;
> + return id;
> +}
Wouldn't it be better if idr itself could remember the last position?
Also, @start/@end should always be honored even if, say, @start moves
above the last position. Other than that, yeah.
Thanks.
--
tejun
On Tue, Mar 26, 2013 at 08:26:53AM -0700, Tejun Heo wrote:
> Hello, Jeff.
>
> On Tue, Mar 26, 2013 at 11:19:36AM -0400, Jeff Layton wrote:
> > +/**
> > + * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion
> > + * @idr: the (initialized) idr
> > + * @ptr: pointer to be associated with the new id
> > + * @start: the minimum id (inclusive)
> > + * @end: the maximum id (exclusive, <= 0 for max)
> > + * @cur: ptr to current position in the range (typically, last allocated + 1)
> > + * @gfp_mask: memory allocation flags
> > + *
> > + * Essentially the same as idr_alloc, but prefers to allocate progressively
> > + * higher ids if it can. If the "cur" counter wraps, then it will start again
> > + * at the "start" end of the range and allocate one that has already been used.
> > + */
> > +int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, int *cur,
> > + gfp_t gfp_mask)
> > +{
> > + int id;
> > +
> > + id = idr_alloc(idr, ptr, *cur, end, gfp_mask);
> > + if (id == -ENOSPC)
> > + id = idr_alloc(idr, ptr, start, end, gfp_mask);
> > +
> > + if (likely(id >= 0))
> > + *cur = id + 1;
> > + return id;
> > +}
>
> Wouldn't it be better if idr itself could remember the last position?
> Also, @start/@end should always be honored even if, say, @start moves
> above the last position. Other than that, yeah.
The old nfsd stateid code just generated stateid's from a counter,
something like:
static u32 counter;
return counter++;
and then stuck them in a hash table. Which had the obvious bug with
(very unlikely, absent malice) collisions on wraparound.
I probably should have ignored idr and just made the obvious fix:
static u32 counter;
while (!id_exists_in_hash(counter))
counter++;
return counter;
So maybe we should just go back to that. And possibly choose some
better data structure.
The only requirements are that at a given moment in time id's should be
unique, and that we should make some effort to avoid reusing them
immediately.
I don't know what other "cyclic" idr users need.
--b.
Hello,
On Tue, Mar 26, 2013 at 12:30:11PM -0400, J. Bruce Fields wrote:
> The only requirements are that at a given moment in time id's should be
> unique, and that we should make some effort to avoid reusing them
> immediately.
>
> I don't know what other "cyclic" idr users need.
We already have other users and idr would at least behave better
(ie. fail faster) under extreme conditions, so sticking with idr might
not be too bad. The optimal would be bitmap + hashtable, I suppose.
Thanks.
--
tejun
On Tue, Mar 26, 2013 at 09:33:51AM -0700, Tejun Heo wrote:
> not be too bad. The optimal would be bitmap + hashtable, I suppose.
Oops, with more restricted (or at least dynamically adjusted) ID
space, that is.
The problem with idr is that it can get pretty wasteful if the IDs
become very scattered - the worst case being one ID per each idr_layer
(the internal allocation block). That said, even cyclic allocation
should yield somewhat clustered IDs, so I don't think it'd be too bad.
Thanks.
--
tejun
On Tue, 26 Mar 2013 09:36:35 -0700
Tejun Heo <[email protected]> wrote:
> On Tue, Mar 26, 2013 at 09:33:51AM -0700, Tejun Heo wrote:
> > not be too bad. The optimal would be bitmap + hashtable, I suppose.
>
> Oops, with more restricted (or at least dynamically adjusted) ID
> space, that is.
>
> The problem with idr is that it can get pretty wasteful if the IDs
> become very scattered - the worst case being one ID per each idr_layer
> (the internal allocation block). That said, even cyclic allocation
> should yield somewhat clustered IDs, so I don't think it'd be too bad.
>
Right, that's a (minor) concern too...
While we can assume that cyclic allocations will probably give you
clustered IDs, we're somewhat at the mercy of the clients when it comes
to freeing them.
So, one could imagine a hostile client that attempts to DoS the server
by creating new stateids and releasing all but one in each idr_layer as
it goes.
Of course there are probably better ways to bring down the NFS
server :).
--
Jeff Layton <[email protected]>