[PATCH v2 1/3] xen-blkback: implement safe iterator for the list of persistent grants

[PATCH v2 1/3] xen-blkback: implement safe iterator for the list of persistent grants

[Roger Pau Monne]

Change foreach_grant iterator to a safe version, that allows freeing
the element while iterating. Also move the free code in
free_persistent_gnts to prevent freeing the element before the rb_next
call.

Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
Cc: xen-devel@lists.xen.org
---
 drivers/block/xen-blkback/blkback.c |   18 +++++++++++-------
 1 files changed, 11 insertions(+), 7 deletions(-)

diff --git a/drivers/block/xen-blkback/blkback.c b/drivers/block/xen-blkback/blkback.c
index 74374fb..5ac841f 100644
--- a/drivers/block/xen-blkback/blkback.c
+++ b/drivers/block/xen-blkback/blkback.c
@@ -161,10 +161,12 @@ static int dispatch_rw_block_io(struct xen_blkif *blkif,
 static void make_response(struct xen_blkif *blkif, u64 id,
 			  unsigned short op, int st);
 
-#define foreach_grant(pos, rbtree, node) \
-	for ((pos) = container_of(rb_first((rbtree)), typeof(*(pos)), node); \
+#define foreach_grant_safe(pos, n, rbtree, node) \
+	for ((pos) = container_of(rb_first((rbtree)), typeof(*(pos)), node), \
+	     (n) = rb_next(&(pos)->node); \
 	     &(pos)->node != NULL; \
-	     (pos) = container_of(rb_next(&(pos)->node), typeof(*(pos)), node))
+	     (pos) = container_of(n, typeof(*(pos)), node), \
+	     (n) = (&(pos)->node != NULL) ? rb_next(&(pos)->node) : NULL)
 
 
 static void add_persistent_gnt(struct rb_root *root,
@@ -217,10 +219,11 @@ static void free_persistent_gnts(struct rb_root *root, unsigned int num)
 	struct gnttab_unmap_grant_ref unmap[BLKIF_MAX_SEGMENTS_PER_REQUEST];
 	struct page *pages[BLKIF_MAX_SEGMENTS_PER_REQUEST];
 	struct persistent_gnt *persistent_gnt;
+	struct rb_node *n;
 	int ret = 0;
 	int segs_to_unmap = 0;
 
-	foreach_grant(persistent_gnt, root, node) {
+	foreach_grant_safe(persistent_gnt, n, root, node) {
 		BUG_ON(persistent_gnt->handle ==
 			BLKBACK_INVALID_HANDLE);
 		gnttab_set_unmap_op(&unmap[segs_to_unmap],
@@ -230,9 +233,6 @@ static void free_persistent_gnts(struct rb_root *root, unsigned int num)
 			persistent_gnt->handle);
 
 		pages[segs_to_unmap] = persistent_gnt->page;
-		rb_erase(&persistent_gnt->node, root);
-		kfree(persistent_gnt);
-		num--;
 
 		if (++segs_to_unmap == BLKIF_MAX_SEGMENTS_PER_REQUEST ||
 			!rb_next(&persistent_gnt->node)) {
@@ -241,6 +241,10 @@ static void free_persistent_gnts(struct rb_root *root, unsigned int num)
 			BUG_ON(ret);
 			segs_to_unmap = 0;
 		}
+
+		rb_erase(&persistent_gnt->node, root);
+		kfree(persistent_gnt);
+		num--;
 	}
 	BUG_ON(num != 0);
 }
-- 
1.7.7.5 (Apple Git-26)

[PATCH v2 2/3] llist: add a safe version of llist_for_each_entry

[Roger Pau Monne]

Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Cc: Huang Ying <ying.huang@intel.com>
Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
---
 include/linux/llist.h |   27 +++++++++++++++++++++++++++
 1 files changed, 27 insertions(+), 0 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index a5199f6..f611cd8 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -125,6 +125,33 @@ static inline void init_llist_head(struct llist_head *list)
 	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
 
 /**
+ * llist_for_each_entry_safe - safely iterate over some deleted entries of
+ *                             lock-less list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @n:		the &struct llist_node to use as a temporary loop cursor
+ * @node:	the fist entry of deleted list entries.
+ * @member:	the name of the llist_node with the struct.
+ *
+ * In general, some entries of the lock-less list can be traversed
+ * safely only after being removed from list, so start with an entry
+ * instead of list head.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ *
+ * n is used to store a reference to the next item llist_node, so
+ * pos can be freed while iterating.
+ */
+#define llist_for_each_entry_safe(pos, n, node, member)		\
+	for ((pos) = llist_entry((node), typeof(*(pos)), member),	\
+	     (n) = (pos)->member.next;					\
+	     &(pos)->member != NULL;					\
+	     (pos) = llist_entry(n, typeof(*(pos)), member),		\
+	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL)
+
+/**
  * llist_empty - tests whether a lock-less list is empty
  * @head:	the list to test
  *
-- 
1.7.7.5 (Apple Git-26)

[PATCH v2 3/3] xen-blkfront: transverse list of persistent grants safely

[Roger Pau Monne]

Use llist_for_each_entry_safe in blkif_free. Previously grants where
freed while iterating the list, which lead to dereferences when trying
to fetch the next item.

Reported-by: Dan Carpenter <dan.carpenter@oracle.com>
Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
Cc: xen-devel@lists.xen.org
---
 drivers/block/xen-blkfront.c |    3 ++-
 1 files changed, 2 insertions(+), 1 deletions(-)

diff --git a/drivers/block/xen-blkfront.c b/drivers/block/xen-blkfront.c
index 96e9b00..cfdb033 100644
--- a/drivers/block/xen-blkfront.c
+++ b/drivers/block/xen-blkfront.c
@@ -792,6 +792,7 @@ static void blkif_free(struct blkfront_info *info, int suspend)
 {
 	struct llist_node *all_gnts;
 	struct grant *persistent_gnt;
+	struct llist_node *n;
 
 	/* Prevent new requests being issued until we fix things up. */
 	spin_lock_irq(&info->io_lock);
@@ -804,7 +805,7 @@ static void blkif_free(struct blkfront_info *info, int suspend)
 	/* Remove all persistent grants */
 	if (info->persistent_gnts_c) {
 		all_gnts = llist_del_all(&info->persistent_gnts);
-		llist_for_each_entry(persistent_gnt, all_gnts, node) {
+		llist_for_each_entry_safe(persistent_gnt, n, all_gnts, node) {
 			gnttab_end_foreign_access(persistent_gnt->gref, 0, 0UL);
 			__free_page(pfn_to_page(persistent_gnt->pfn));
 			kfree(persistent_gnt);
-- 
1.7.7.5 (Apple Git-26)

Re: [PATCH v2 2/3] llist: add a safe version of llist_for_each_entry

[Huang Ying]

On Mon, 2012-12-10 at 18:24 +0100, Roger Pau Monne wrote:
> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
> Cc: Huang Ying <ying.huang@intel.com>
> Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
> ---
>  include/linux/llist.h |   27 +++++++++++++++++++++++++++
>  1 files changed, 27 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/llist.h b/include/linux/llist.h
> index a5199f6..f611cd8 100644
> --- a/include/linux/llist.h
> +++ b/include/linux/llist.h
> @@ -125,6 +125,33 @@ static inline void init_llist_head(struct llist_head *list)
>  	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
>  
>  /**
> + * llist_for_each_entry_safe - safely iterate over some deleted entries of
> + *                             lock-less list of given type
> + * @pos:	the type * to use as a loop cursor.
> + * @n:		the &struct llist_node to use as a temporary loop cursor
> + * @node:	the fist entry of deleted list entries.
> + * @member:	the name of the llist_node with the struct.
> + *
> + * In general, some entries of the lock-less list can be traversed
> + * safely only after being removed from list, so start with an entry
> + * instead of list head.
> + *
> + * If being used on entries deleted from lock-less list directly, the
> + * traverse order is from the newest to the oldest added entry.  If
> + * you want to traverse from the oldest to the newest, you must
> + * reverse the order by yourself before traversing.
> + *
> + * n is used to store a reference to the next item llist_node, so
> + * pos can be freed while iterating.
> + */
> +#define llist_for_each_entry_safe(pos, n, node, member)		\
> +	for ((pos) = llist_entry((node), typeof(*(pos)), member),	\
> +	     (n) = (pos)->member.next;					\

If node == NULL, (pos)->member.next will trigger NULL reference.

Best Regards,
Huang Ying

> +	     &(pos)->member != NULL;					\
> +	     (pos) = llist_entry(n, typeof(*(pos)), member),		\
> +	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL)
> +
> +/**
>   * llist_empty - tests whether a lock-less list is empty
>   * @head:	the list to test
>   *

[PATCH v3] llist: add a safe version of llist_for_each_entry

[Roger Pau Monne]

Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
Cc: Huang Ying <ying.huang@intel.com>
Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
---
Changes since v2:
 * Allow to pass a NULL node as the first entry of deleted list
   entries.
---
 include/linux/llist.h |   27 +++++++++++++++++++++++++++
 1 files changed, 27 insertions(+), 0 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index a5199f6..4e0aec1 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -125,6 +125,33 @@ static inline void init_llist_head(struct llist_head *list)
 	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
 
 /**
+ * llist_for_each_entry_safe - safely iterate over some deleted entries of
+ *                             lock-less list of given type
+ * @pos:	the type * to use as a loop cursor.
+ * @n:		the &struct llist_node to use as a temporary loop cursor
+ * @node:	the fist entry of deleted list entries.
+ * @member:	the name of the llist_node with the struct.
+ *
+ * In general, some entries of the lock-less list can be traversed
+ * safely only after being removed from list, so start with an entry
+ * instead of list head.
+ *
+ * If being used on entries deleted from lock-less list directly, the
+ * traverse order is from the newest to the oldest added entry.  If
+ * you want to traverse from the oldest to the newest, you must
+ * reverse the order by yourself before traversing.
+ *
+ * n is used to store a reference to the next item llist_node, so
+ * pos can be freed while iterating.
+ */
+#define llist_for_each_entry_safe(pos, n, node, member)		\
+	for ((pos) = llist_entry((node), typeof(*(pos)), member),	\
+	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL;\
+	     &(pos)->member != NULL;					\
+	     (pos) = llist_entry(n, typeof(*(pos)), member),		\
+	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL)
+
+/**
  * llist_empty - tests whether a lock-less list is empty
  * @head:	the list to test
  *
-- 
1.7.7.5 (Apple Git-26)

Re: [PATCH v3] llist: add a safe version of llist_for_each_entry

[Huang Ying]

On Tue, 2012-12-11 at 12:25 +0100, Roger Pau Monne wrote:
> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
> Cc: Huang Ying <ying.huang@intel.com>
> Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
> ---
> Changes since v2:
>  * Allow to pass a NULL node as the first entry of deleted list
>    entries.
> ---
>  include/linux/llist.h |   27 +++++++++++++++++++++++++++
>  1 files changed, 27 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/llist.h b/include/linux/llist.h
> index a5199f6..4e0aec1 100644
> --- a/include/linux/llist.h
> +++ b/include/linux/llist.h
> @@ -125,6 +125,33 @@ static inline void init_llist_head(struct llist_head *list)
>  	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
>  
>  /**
> + * llist_for_each_entry_safe - safely iterate over some deleted entries of
> + *                             lock-less list of given type
> + * @pos:	the type * to use as a loop cursor.
> + * @n:		the &struct llist_node to use as a temporary loop cursor

In list_for_each_entry_safe, n is type *, why not follow that?

Best Regards,
Huang Ying

> + * @node:	the fist entry of deleted list entries.
> + * @member:	the name of the llist_node with the struct.
> + *
> + * In general, some entries of the lock-less list can be traversed
> + * safely only after being removed from list, so start with an entry
> + * instead of list head.
> + *
> + * If being used on entries deleted from lock-less list directly, the
> + * traverse order is from the newest to the oldest added entry.  If
> + * you want to traverse from the oldest to the newest, you must
> + * reverse the order by yourself before traversing.
> + *
> + * n is used to store a reference to the next item llist_node, so
> + * pos can be freed while iterating.
> + */
> +#define llist_for_each_entry_safe(pos, n, node, member)		\
> +	for ((pos) = llist_entry((node), typeof(*(pos)), member),	\
> +	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL;\
> +	     &(pos)->member != NULL;					\
> +	     (pos) = llist_entry(n, typeof(*(pos)), member),		\
> +	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL)
> +
> +/**
>   * llist_empty - tests whether a lock-less list is empty
>   * @head:	the list to test
>   *

Re: [PATCH v3] llist: add a safe version of llist_for_each_entry

[Roger Pau Monné]

On 12/12/12 01:37, Huang Ying wrote:
> On Tue, 2012-12-11 at 12:25 +0100, Roger Pau Monne wrote:
>> Signed-off-by: Roger Pau Monné <roger.pau@citrix.com>
>> Cc: Huang Ying <ying.huang@intel.com>
>> Cc: Konrad Rzeszutek Wilk <konrad@kernel.org>
>> ---
>> Changes since v2:
>>  * Allow to pass a NULL node as the first entry of deleted list
>>    entries.
>> ---
>>  include/linux/llist.h |   27 +++++++++++++++++++++++++++
>>  1 files changed, 27 insertions(+), 0 deletions(-)
>>
>> diff --git a/include/linux/llist.h b/include/linux/llist.h
>> index a5199f6..4e0aec1 100644
>> --- a/include/linux/llist.h
>> +++ b/include/linux/llist.h
>> @@ -125,6 +125,33 @@ static inline void init_llist_head(struct llist_head *list)
>>  	     (pos) = llist_entry((pos)->member.next, typeof(*(pos)), member))
>>  
>>  /**
>> + * llist_for_each_entry_safe - safely iterate over some deleted entries of
>> + *                             lock-less list of given type
>> + * @pos:	the type * to use as a loop cursor.
>> + * @n:		the &struct llist_node to use as a temporary loop cursor
> 
> In list_for_each_entry_safe, n is type *, why not follow that?

Thanks for the review, yes I just saw it, I was using llist_node because
I didn't need a type *, but I agree that it's best to stick with
list_for_each_entry_safe interface. Will send v4....

> 
> Best Regards,
> Huang Ying
> 
>> + * @node:	the fist entry of deleted list entries.
>> + * @member:	the name of the llist_node with the struct.
>> + *
>> + * In general, some entries of the lock-less list can be traversed
>> + * safely only after being removed from list, so start with an entry
>> + * instead of list head.
>> + *
>> + * If being used on entries deleted from lock-less list directly, the
>> + * traverse order is from the newest to the oldest added entry.  If
>> + * you want to traverse from the oldest to the newest, you must
>> + * reverse the order by yourself before traversing.
>> + *
>> + * n is used to store a reference to the next item llist_node, so
>> + * pos can be freed while iterating.
>> + */
>> +#define llist_for_each_entry_safe(pos, n, node, member)		\
>> +	for ((pos) = llist_entry((node), typeof(*(pos)), member),	\
>> +	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL;\
>> +	     &(pos)->member != NULL;					\
>> +	     (pos) = llist_entry(n, typeof(*(pos)), member),		\
>> +	     (n) = (&(pos)->member != NULL) ? (pos)->member.next : NULL)
>> +
>> +/**
>>   * llist_empty - tests whether a lock-less list is empty
>>   * @head:	the list to test
>>   *
> 
>