Re: [PATCH] idr: fix a subtle bug in idr_get_next()
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 > > Reported-by: David Teigland > > Cc: KAMEZAWA Hiroyuki > > 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 -- 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] idr: fix a subtle bug in idr_get_next()
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 t...@kernel.org Reported-by: David Teigland teigl...@redhat.com Cc: KAMEZAWA Hiroyuki kamezawa.hir...@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 -- 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] idr: fix a subtle bug in idr_get_next()
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 > > 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 -- 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] idr: fix a subtle bug in idr_get_next()
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 t...@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 -- 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] idr: fix a subtle bug in idr_get_next()
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
Don't we need to cc stable?
> Reported-by: David Teigland
> Cc: KAMEZAWA Hiroyuki
> ---
> 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;
> --
--
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] idr: fix a subtle bug in idr_get_next()
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 > >> Reported-by: David Teigland > >> Cc: KAMEZAWA Hiroyuki > > > > 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 -- 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] idr: fix a subtle bug in idr_get_next()
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 t...@kernel.org
Don't we need to cc stable?
Reported-by: David Teigland teigl...@redhat.com
Cc: KAMEZAWA Hiroyuki kamezawa.hir...@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;
--
--
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] idr: fix a subtle bug in idr_get_next()
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 t...@kernel.org Reported-by: David Teigland teigl...@redhat.com Cc: KAMEZAWA Hiroyuki kamezawa.hir...@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 -- 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] idr: fix a subtle bug in idr_get_next()
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 >> Reported-by: David Teigland >> Cc: KAMEZAWA Hiroyuki > > 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 -- 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] idr: fix a subtle bug in idr_get_next()
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 > Reported-by: David Teigland > Cc: KAMEZAWA Hiroyuki David, can you please test whether the patch makes the skipped deletion bug go away? 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] idr: fix a subtle bug in idr_get_next()
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
Reported-by: David Teigland
Cc: KAMEZAWA Hiroyuki
---
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;
--
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] idr: fix a subtle bug in idr_get_next()
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 t...@kernel.org
Reported-by: David Teigland teigl...@redhat.com
Cc: KAMEZAWA Hiroyuki kamezawa.hir...@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;
--
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] idr: fix a subtle bug in idr_get_next()
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 t...@kernel.org Reported-by: David Teigland teigl...@redhat.com Cc: KAMEZAWA Hiroyuki kamezawa.hir...@jp.fujitsu.com David, can you please test whether the patch makes the skipped deletion bug go away? 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/
Re: [PATCH] idr: fix a subtle bug in idr_get_next()
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 t...@kernel.org Reported-by: David Teigland teigl...@redhat.com Cc: KAMEZAWA Hiroyuki kamezawa.hir...@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 -- 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/
