[Cluster-devel] [PATCH 09/14] dlm: use idr_for_each_entry() in recover_idr_clear() error path

[Cluster-devel] [PATCH 09/14] dlm: use idr_for_each_entry() in recover_idr_clear() error path

[Tejun Heo]

Convert recover_idr_clear() to use idr_for_each_entry() instead of
idr_for_each().  It's somewhat less efficient this way but it
shouldn't matter in an error path.  This is to help with deprecation
of idr_remove_all().

Only compile tested.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Christine Caulfield <ccaulfie@redhat.com>
Cc: David Teigland <teigland@redhat.com>
Cc: cluster-devel at redhat.com
---
This patch depends on an earlier idr patch and I think it would be
best to route these together through -mm.  Christine, David, can you
please ack this?

Thanks.

 fs/dlm/recover.c | 23 ++++++++++-------------
 1 file changed, 10 insertions(+), 13 deletions(-)

diff --git a/fs/dlm/recover.c b/fs/dlm/recover.c
index aedea28..b2856e7 100644
--- a/fs/dlm/recover.c
+++ b/fs/dlm/recover.c
@@ -351,23 +351,20 @@ static struct dlm_rsb *recover_idr_find(struct dlm_ls *ls, uint64_t id)
 	return r;
 }
 
-static int recover_idr_clear_rsb(int id, void *p, void *data)
+static void recover_idr_clear(struct dlm_ls *ls)
 {
-	struct dlm_ls *ls = data;
-	struct dlm_rsb *r = p;
+	struct dlm_rsb *r;
+	int id;
 
-	r->res_id = 0;
-	r->res_recover_locks_count = 0;
-	ls->ls_recover_list_count--;
+	spin_lock(&ls->ls_recover_idr_lock);
 
-	dlm_put_rsb(r);
-	return 0;
-}
+	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
+		r->res_id = 0;
+		r->res_recover_locks_count = 0;
+		ls->ls_recover_list_count--;
 
-static void recover_idr_clear(struct dlm_ls *ls)
-{
-	spin_lock(&ls->ls_recover_idr_lock);
-	idr_for_each(&ls->ls_recover_idr, recover_idr_clear_rsb, ls);
+		dlm_put_rsb(r);
+	}
 	idr_remove_all(&ls->ls_recover_idr);
 
 	if (ls->ls_recover_list_count != 0) {
-- 
1.8.1

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

idr_destroy() can destroy idr by itself and idr_remove_all() is being
deprecated.

The conversion isn't completely trivial for recover_idr_clear() as
it's the only place in kernel which makes legitimate use of
idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
inside idr_for_each_entry() loop.  It goes on top so that it matches
the operation order in recover_idr_del().

Only compile tested.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Christine Caulfield <ccaulfie@redhat.com>
Cc: David Teigland <teigland@redhat.com>
Cc: cluster-devel at redhat.com
---
This patch depends on an earlier idr patch and given the trivial
nature of the patch, I think it would be best to route these together
through -mm.  Please holler if there's any objection.

Thanks.

 fs/dlm/lockspace.c | 1 -
 fs/dlm/recover.c   | 2 +-
 2 files changed, 1 insertion(+), 2 deletions(-)

diff --git a/fs/dlm/lockspace.c b/fs/dlm/lockspace.c
index 2e99fb0..3ca79d3 100644
--- a/fs/dlm/lockspace.c
+++ b/fs/dlm/lockspace.c
@@ -796,7 +796,6 @@ static int release_lockspace(struct dlm_ls *ls, int force)
 	 */
 
 	idr_for_each(&ls->ls_lkbidr, lkb_idr_free, ls);
-	idr_remove_all(&ls->ls_lkbidr);
 	idr_destroy(&ls->ls_lkbidr);
 
 	/*
diff --git a/fs/dlm/recover.c b/fs/dlm/recover.c
index b2856e7..236d108 100644
--- a/fs/dlm/recover.c
+++ b/fs/dlm/recover.c
@@ -359,13 +359,13 @@ static void recover_idr_clear(struct dlm_ls *ls)
 	spin_lock(&ls->ls_recover_idr_lock);
 
 	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
+		idr_remove(&ls->ls_recover_idr, id);
 		r->res_id = 0;
 		r->res_recover_locks_count = 0;
 		ls->ls_recover_list_count--;
 
 		dlm_put_rsb(r);
 	}
-	idr_remove_all(&ls->ls_recover_idr);
 
 	if (ls->ls_recover_list_count != 0) {
 		log_error(ls, "warning: recover_list_count %d",
-- 
1.8.1

[Cluster-devel] [PATCH 09/14] dlm: use idr_for_each_entry() in recover_idr_clear() error path

[David Teigland]

On Fri, Jan 25, 2013 at 05:31:07PM -0800, Tejun Heo wrote:
> Convert recover_idr_clear() to use idr_for_each_entry() instead of
> idr_for_each().  It's somewhat less efficient this way but it
> shouldn't matter in an error path.  This is to help with deprecation
> of idr_remove_all().
> 
> Only compile tested.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Christine Caulfield <ccaulfie@redhat.com>
> Cc: David Teigland <teigland@redhat.com>
> Cc: cluster-devel at redhat.com
> ---
> This patch depends on an earlier idr patch and I think it would be
> best to route these together through -mm.  Christine, David, can you
> please ack this?

Ack

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Fri, Jan 25, 2013 at 05:31:08PM -0800, Tejun Heo wrote:
> idr_destroy() can destroy idr by itself and idr_remove_all() is being
> deprecated.
> 
> The conversion isn't completely trivial for recover_idr_clear() as
> it's the only place in kernel which makes legitimate use of
> idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
> inside idr_for_each_entry() loop.  It goes on top so that it matches
> the operation order in recover_idr_del().
> 
> Only compile tested.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Christine Caulfield <ccaulfie@redhat.com>
> Cc: David Teigland <teigland@redhat.com>
> Cc: cluster-devel at redhat.com
> ---
> This patch depends on an earlier idr patch and given the trivial
> nature of the patch, I think it would be best to route these together
> through -mm.  Please holler if there's any objection.

Yes, that's good for me.  I'll grab the set and test the dlm bits.

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Mon, Jan 28, 2013 at 10:57:23AM -0500, David Teigland wrote:
> On Fri, Jan 25, 2013 at 05:31:08PM -0800, Tejun Heo wrote:
> > idr_destroy() can destroy idr by itself and idr_remove_all() is being
> > deprecated.
> > 
> > The conversion isn't completely trivial for recover_idr_clear() as
> > it's the only place in kernel which makes legitimate use of
> > idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
> > inside idr_for_each_entry() loop.  It goes on top so that it matches
> > the operation order in recover_idr_del().
> > 
> > Only compile tested.
> > 
> > Signed-off-by: Tejun Heo <tj@kernel.org>
> > Cc: Christine Caulfield <ccaulfie@redhat.com>
> > Cc: David Teigland <teigland@redhat.com>
> > Cc: cluster-devel at redhat.com
> > ---
> > This patch depends on an earlier idr patch and given the trivial
> > nature of the patch, I think it would be best to route these together
> > through -mm.  Please holler if there's any objection.
> 
> Yes, that's good for me.  I'll grab the set and test the dlm bits.

Hi Tejun,
Unfortunately, the list_for_each_entry doesn't seem to be clearing
everything.  I've seen "warning: recover_list_count 39" at the end of that
function.
Dave

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Tue, Jan 29, 2013 at 10:13:17AM -0500, David Teigland wrote:
> On Mon, Jan 28, 2013 at 10:57:23AM -0500, David Teigland wrote:
> > On Fri, Jan 25, 2013 at 05:31:08PM -0800, Tejun Heo wrote:
> > > idr_destroy() can destroy idr by itself and idr_remove_all() is being
> > > deprecated.
> > > 
> > > The conversion isn't completely trivial for recover_idr_clear() as
> > > it's the only place in kernel which makes legitimate use of
> > > idr_remove_all() w/o idr_destroy().  Replace it with idr_remove() call
> > > inside idr_for_each_entry() loop.  It goes on top so that it matches
> > > the operation order in recover_idr_del().
> > > 
> > > Only compile tested.
> > > 
> > > Signed-off-by: Tejun Heo <tj@kernel.org>
> > > Cc: Christine Caulfield <ccaulfie@redhat.com>
> > > Cc: David Teigland <teigland@redhat.com>
> > > Cc: cluster-devel at redhat.com
> > > ---
> > > This patch depends on an earlier idr patch and given the trivial
> > > nature of the patch, I think it would be best to route these together
> > > through -mm.  Please holler if there's any objection.
> > 
> > Yes, that's good for me.  I'll grab the set and test the dlm bits.
> 
> Hi Tejun,
> Unfortunately, the list_for_each_entry doesn't seem to be clearing
> everything.  I've seen "warning: recover_list_count 39" at the end of that
> function.

I don't want to pretend to understand the internals of this idr code, but
it's not clear that idr_for_each is equivalent to idr_for_each_entry when
iterating through all id values.  The "++id" in idr_for_each_entry looks
like it could lead to some missed entries?  The comment about idr_get_next
returning the "next number to given id" sounds like an entry with an id of
"++id" would be missed.

Dave

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

Hello, David.

Sorry about the delay.

On Wed, Jan 30, 2013 at 04:24:18PM -0500, David Teigland wrote:
> > Unfortunately, the list_for_each_entry doesn't seem to be clearing
> > everything.  I've seen "warning: recover_list_count 39" at the end of that
> > function.
> 
> I don't want to pretend to understand the internals of this idr code, but
> it's not clear that idr_for_each is equivalent to idr_for_each_entry when
> iterating through all id values.  The "++id" in idr_for_each_entry looks
> like it could lead to some missed entries?  The comment about idr_get_next
> returning the "next number to given id" sounds like an entry with an id of
> "++id" would be missed.

The function description is misleading.  The function does search
inclusive range and needs explicit cursor increment to make progress.
Weird that it doesn't work.  Looking into it.  I'll write when I know
more.

Thanks!

-- 
tejun

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

Hello, David.

On Thu, Jan 31, 2013 at 03:53:20PM -0800, Tejun Heo wrote:
> The function description is misleading.  The function does search
> inclusive range and needs explicit cursor increment to make progress.
> Weird that it doesn't work.  Looking into it.  I'll write when I know
> more.

It looks a bit weird to me that ls->ls_recover_list_count is also
incremented by recover_list_add().  The two code paths don't seem to
be interlocke at least upon my very shallow glance.  Is it that only
either the list or idr is in use?

Anyways, can you please apply the following patch and see which IDs
are leaking from the iteration?  The patch too is only compile tested
so I might have done something stupid but it hopefully shouldn't be
too difficult to make it work.

Thanks!
---
 fs/dlm/recover.c |   12 ++++++++++++
 1 file changed, 12 insertions(+)

--- a/fs/dlm/recover.c
+++ b/fs/dlm/recover.c
@@ -351,6 +351,12 @@ static struct dlm_rsb *recover_idr_find(
 	return r;
 }
 
+static int dlm_dump_idr(int id, void *p, void *data)
+{
+	pr_cont(" %d", id);
+	return 0;
+}
+
 static void recover_idr_clear(struct dlm_ls *ls)
 {
 	struct dlm_rsb *r;
@@ -358,7 +364,9 @@ static void recover_idr_clear(struct dlm
 
 	spin_lock(&ls->ls_recover_idr_lock);
 
+	pr_info("XXX clearing:");
 	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
+		pr_cont(" %d", id);
 		idr_remove(&ls->ls_recover_idr, id);
 		r->res_id = 0;
 		r->res_recover_locks_count = 0;
@@ -366,10 +374,14 @@ static void recover_idr_clear(struct dlm
 
 		dlm_put_rsb(r);
 	}
+	pr_cont("\n");
 
 	if (ls->ls_recover_list_count != 0) {
 		log_error(ls, "warning: recover_list_count %d",
 			  ls->ls_recover_list_count);
+		pr_info("XXX leftovers: ");
+		idr_for_each(&ls->ls_recover_idr, dlm_dump_idr, NULL);
+		pr_cont("\n");
 		ls->ls_recover_list_count = 0;
 	}
 	spin_unlock(&ls->ls_recover_idr_lock);

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[David Teigland]

On Thu, Jan 31, 2013 at 04:18:41PM -0800, Tejun Heo wrote:
> It looks a bit weird to me that ls->ls_recover_list_count is also
> incremented by recover_list_add().  The two code paths don't seem to
> be interlocke at least upon my very shallow glance.  Is it that only
> either the list or idr is in use?

Yes, that's correct.

> Anyways, can you please apply the following patch and see which IDs
> are leaking from the iteration?  The patch too is only compile tested
> so I might have done something stupid but it hopefully shouldn't be
> too difficult to make it work.

I'm trying your patch now, I don't have a test optimized to hit this code
so it may take a while.

>  static void recover_idr_clear(struct dlm_ls *ls)
>  {
>  	struct dlm_rsb *r;
> @@ -358,7 +364,9 @@ static void recover_idr_clear(struct dlm
>  
>  	spin_lock(&ls->ls_recover_idr_lock);
>  
> +	pr_info("XXX clearing:");
>  	idr_for_each_entry(&ls->ls_recover_idr, r, id) {
> +		pr_cont(" %d", id);

It will often be clearing hundreds of thousands of entries, so this will
probably be excessive.

>  	if (ls->ls_recover_list_count != 0) {
>  		log_error(ls, "warning: recover_list_count %d",
>  			  ls->ls_recover_list_count);
> +		pr_info("XXX leftovers: ");
> +		idr_for_each(&ls->ls_recover_idr, dlm_dump_idr, NULL);
> +		pr_cont("\n");

I already tried my own version of this, but used idr_for_each_entry a
second time.  Unfortunately, the number it found and printed did not match
recover_list_count.

warning: recover_list_count 566

It printed 304 ids:

41218 41222 41223 41224 41226 41228 41229 41230 41231 41232 41234 41235
41236 41237 41239 41241 41242 41243 41244 41245 41246 41249 41252 41253
41254 41255 41256 41257 41259 41260 41261 41263 41264 41266 41271 41272
41273 41274 41277 41278 41475 41480 41483 41524 41525 41526 41655 41731
41741 41745 41749 41767 41768 41769 41772 41773 41782 42113 42114 42115
42121 42122 42124 42128 42132 42136 42138 42139 42141 42165 42375 42381
42385 42388 42390 42392 42399 42401 42404 42407 42409 42411 42416 42422
42694 42699 42712 42717 42727 42866 43009 43042 43044 43046 43049 43051
43058 43059 43064 43065 43066 43067 43330 43332 43337 43338 43339 43343
43348 43349 43351 43354 43355 43356 43361 43362 43368 43369 43370 43375
43376 43377 43378 43379 43381 43575 43576 43577 43677 43678 43680 43683
43684 43685 43689 43690 43819 43820 43823 43824 43825 43826 43827 43828
43829 43831 43905 43907 43908 43912 43929 43930 43955 43956 43960 43962
43965 44288 44289 44291 44296 44298 44300 44310 44311 44313 44314 44316
44318 44321 44323 44325 44454 44456 44457 44458 44544 44547 44548 44550
44555 44557 44560 44562 44564 44567 44573 44575 44576 44578 44579 44581
44582 44583 44584 44585 44589 44592 44595 44596 44726 44728 44729 44732
44734 44866 44867 44873 44876 44878 44879 44912 44914 44916 44920 44923
44924 45053 45186 45189 45190 45195 45197 45199 45200 45201 45203 45204
45208 45209 45212 45213 45216 45220 45223 45224 45225 45227 45228 45231
45234 45440 45441 45444 45448 45450 45452 45454 45456 45457 45458 45459
45460 45461 45464 45466 45467 45472 45475 45477 45484 45485 45488 45492
45494 45495 45496 45497 45498 45499 45628 45630 45698 45699 45700 45703
45707 45708 45710 45713 45715 45717 45720 45722 45723 45724 45725 45727
45729 45730 45731 45733 45734 45737 45739 45741 45742 45746 45748 45750
45755 47292 47293 47294

[Cluster-devel] [PATCH 10/14] dlm: don't use idr_remove_all()

[Tejun Heo]

Hello, David.

On Fri, Feb 01, 2013 at 12:44:43PM -0500, David Teigland wrote:
> I already tried my own version of this, but used idr_for_each_entry a
> second time.  Unfortunately, the number it found and printed did not match
> recover_list_count.
> 
> warning: recover_list_count 566
> 
> It printed 304 ids:

Heh, that's really weird.  Maybe idr_get_next() is buggy above certain
number or at certain boundaries?  If you find something, please let me
know.  I'll see if I can reproduce it in some minimal way.

Thanks!

-- 
tejun

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

The iteration logic of idr_get_next() is borrowed mostly verbatim from
idr_for_each().  It walks down the tree looking for the slot matching
the current ID.  If the matching slot is not found, the ID is
incremented by the distance of single slot at the given level and
repeats.

The implementation assumes that during the whole iteration id is
aligned to the layer boundaries of the level closest to the leaf,
which is true for all iterations starting from zero or an existing
element and thus is fine for idr_for_each().

However, idr_get_next() may be given any point and if the starting id
hits in the middle of a non-existent layer, increment to the next
layer will end up skipping the same offset into it.  For example, an
IDR with IDs filled between [64, 127] would look like the following.

          [  0  64 ... ]
       /----/   |
       |        |
      NULL    [ 64 ... 127 ]

If idr_get_next() is called with 63 as the starting point, it will try
to follow down the pointer from 0.  As it is NULL, it will then try to
proceed to the next slot in the same level by adding the slot distance
at that level which is 64 - making the next try 127.  It goes around
the loop and finds and returns 127 skipping [64, 126].

Note that this bug also triggers in idr_for_each_entry() loop which
deletes during iteration as deletions can make layers go away leaving
the iteration with unaligned ID into missing layers.

Fix it by ensuring proceeding to the next slot doesn't carry over the
unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
id += slot_distance.

Signed-off-by: Tejun Heo <tj@kernel.org>
Reported-by: David Teigland <teigland@redhat.com>
Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
---
 lib/idr.c |    9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/lib/idr.c b/lib/idr.c
index 6482390..ca5aa00 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -625,7 +625,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
 			return p;
 		}
 
-		id += 1 << n;
+		/*
+		 * Proceed to the next layer at the current level.  Unlike
+		 * idr_for_each(), @id isn't guaranteed to be aligned to
+		 * layer boundary@this point and adding 1 << n may
+		 * incorrectly skip IDs.  Make sure we jump to the
+		 * beginning of the next layer using round_up().
+		 */
+		id = round_up(id + 1, 1 << n);
 		while (n < fls(id)) {
 			n += IDR_BITS;
 			p = *--paa;

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
> Fix it by ensuring proceeding to the next slot doesn't carry over the
> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> id += slot_distance.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Reported-by: David Teigland <teigland@redhat.com>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>

David, can you please test whether the patch makes the skipped
deletion bug go away?

Thanks!

-- 
tejun

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[Randy Dunlap]

On 02/02/13 15:11, Tejun Heo wrote:
> On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
>> Fix it by ensuring proceeding to the next slot doesn't carry over the
>> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
>> id += slot_distance.
>>
>> Signed-off-by: Tejun Heo <tj@kernel.org>
>> Reported-by: David Teigland <teigland@redhat.com>
>> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> 
> David, can you please test whether the patch makes the skipped
> deletion bug go away?
> 
> Thanks!

Hugh, did you update the idr test suite or the radix-tree test suite?

Is there an idr test suite or module?  I have a kernel module source file
named idr_test.c by Eric Paris.

thanks,

-- 
~Randy

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[Hugh Dickins]

On Sat, 2 Feb 2013, Randy Dunlap wrote:
> On 02/02/13 15:11, Tejun Heo wrote:
> > On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
> >> Fix it by ensuring proceeding to the next slot doesn't carry over the
> >> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> >> id += slot_distance.
> >>
> >> Signed-off-by: Tejun Heo <tj@kernel.org>
> >> Reported-by: David Teigland <teigland@redhat.com>
> >> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> > 
> > David, can you please test whether the patch makes the skipped
> > deletion bug go away?
> > 
> > Thanks!
> 
> Hugh, did you update the idr test suite or the radix-tree test suite?

Sorry, not the answer you want: it was the radix-tree test harness, rtth,
that I updated a year ago (but then lib/radix-tree.c changed again).

Hugh

> 
> Is there an idr test suite or module?  I have a kernel module source file
> named idr_test.c by Eric Paris.
> 
> thanks,
> 
> -- 
> ~Randy

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[Li Zefan]

On 2013/2/3 7:10, Tejun Heo wrote:
> The iteration logic of idr_get_next() is borrowed mostly verbatim from
> idr_for_each().  It walks down the tree looking for the slot matching
> the current ID.  If the matching slot is not found, the ID is
> incremented by the distance of single slot at the given level and
> repeats.
> 
> The implementation assumes that during the whole iteration id is
> aligned to the layer boundaries of the level closest to the leaf,
> which is true for all iterations starting from zero or an existing
> element and thus is fine for idr_for_each().
> 
> However, idr_get_next() may be given any point and if the starting id
> hits in the middle of a non-existent layer, increment to the next
> layer will end up skipping the same offset into it.  For example, an
> IDR with IDs filled between [64, 127] would look like the following.
> 
>           [  0  64 ... ]
>        /----/   |
>        |        |
>       NULL    [ 64 ... 127 ]
> 
> If idr_get_next() is called with 63 as the starting point, it will try
> to follow down the pointer from 0.  As it is NULL, it will then try to
> proceed to the next slot in the same level by adding the slot distance
> at that level which is 64 - making the next try 127.  It goes around
> the loop and finds and returns 127 skipping [64, 126].
> 
> Note that this bug also triggers in idr_for_each_entry() loop which
> deletes during iteration as deletions can make layers go away leaving
> the iteration with unaligned ID into missing layers.
> 
> Fix it by ensuring proceeding to the next slot doesn't carry over the
> unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> id += slot_distance.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>

Don't we need to cc stable?

> Reported-by: David Teigland <teigland@redhat.com>
> Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> ---
>  lib/idr.c |    9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/idr.c b/lib/idr.c
> index 6482390..ca5aa00 100644
> --- a/lib/idr.c
> +++ b/lib/idr.c
> @@ -625,7 +625,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
>  			return p;
>  		}
>  
> -		id += 1 << n;
> +		/*
> +		 * Proceed to the next layer at the current level.  Unlike
> +		 * idr_for_each(), @id isn't guaranteed to be aligned to
> +		 * layer boundary at this point and adding 1 << n may
> +		 * incorrectly skip IDs.  Make sure we jump to the
> +		 * beginning of the next layer using round_up().
> +		 */
> +		id = round_up(id + 1, 1 << n);
>  		while (n < fls(id)) {
>  			n += IDR_BITS;
>  			p = *--paa;
> --

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

Hey, Li.

On Mon, Feb 04, 2013 at 11:39:50AM +0800, Li Zefan wrote:
> > Fix it by ensuring proceeding to the next slot doesn't carry over the
> > unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> > id += slot_distance.
> > 
> > Signed-off-by: Tejun Heo <tj@kernel.org>
> 
> Don't we need to cc stable?

I thought we didn't have idr_remove() inside idr_for_each_entry() in
kernel, which isn't true.  drbd already does that, so yeah, we need to
cc stable.

Thanks.

-- 
tejun

[Cluster-devel] [PATCH] idr: fix a subtle bug in idr_get_next()

[David Teigland]

On Sat, Feb 02, 2013 at 03:11:35PM -0800, Tejun Heo wrote:
> On Sat, Feb 02, 2013 at 03:10:48PM -0800, Tejun Heo wrote:
> > Fix it by ensuring proceeding to the next slot doesn't carry over the
> > unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
> > id += slot_distance.
> > 
> > Signed-off-by: Tejun Heo <tj@kernel.org>
> > Reported-by: David Teigland <teigland@redhat.com>
> > Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
> 
> David, can you please test whether the patch makes the skipped
> deletion bug go away?

Yes, I've tested, and it works fine now.
Thanks,
Dave