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

[PATCH v4 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
---
Changes since v2:
 * Implement the same semantics as list_for_each_safe, using type *
   instead of rb_node * as the temporary cursor.
---
 drivers/block/xen-blkback/blkback.c |   23 ++++++++++++++---------
 1 files changed, 14 insertions(+), 9 deletions(-)

diff --git a/drivers/block/xen-blkback/blkback.c b/drivers/block/xen-blkback/blkback.c
index 74374fb..8808028 100644
--- a/drivers/block/xen-blkback/blkback.c
+++ b/drivers/block/xen-blkback/blkback.c
@@ -161,10 +161,14 @@ 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); \
-	     &(pos)->node != NULL; \
-	     (pos) = container_of(rb_next(&(pos)->node), typeof(*(pos)), node))
+#define foreach_grant_safe(pos, n, rbtree, node) \
+	for ((pos) = container_of(rb_first((rbtree)), typeof(*(pos)), node),\
+	     (n) = container_of(((&(pos)->node != NULL) ? 		\
+	         rb_next(&(pos)->node) : NULL), typeof(*(pos)), node);	\
+	     &(pos)->node != NULL;					\
+	     (pos) = n,							\
+	     (n) = container_of(((&(pos)->node != NULL) ?		\
+	         rb_next(&(pos)->node) : NULL), typeof(*(pos)), node))
 
 
 static void add_persistent_gnt(struct rb_root *root,
@@ -216,11 +220,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 persistent_gnt *persistent_gnt, *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 +234,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 +242,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 v4 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>
---
Changes since v3:
 * Change n to use type *, to keep the same semantics as
   list_for_each_entry_safe.
Changes since v2:
 * Allow to pass a NULL node as the first entry of deleted list
   entries.
---
 include/linux/llist.h |   29 +++++++++++++++++++++++++++++
 1 files changed, 29 insertions(+), 0 deletions(-)

diff --git a/include/linux/llist.h b/include/linux/llist.h
index a5199f6..f551ac4 100644
--- a/include/linux/llist.h
+++ b/include/linux/llist.h
@@ -125,6 +125,35 @@ 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:		another type * to use as temporary storage
+ * @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) = llist_entry(((&(pos)->member != NULL) ?		\
+	         (pos)->member.next : NULL), typeof(*(pos)), member);	\
+	     &(pos)->member != NULL;					\
+	     (pos) = n,							\
+	     (n) = llist_entry(((&(pos)->member != NULL) ?		\
+	         (pos)->member.next : NULL), typeof(*(pos)), member))
+
+/**
  * llist_empty - tests whether a lock-less list is empty
  * @head:	the list to test
  *
-- 
1.7.7.5 (Apple Git-26)

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

[Huang Ying]

On Thu, 2012-12-13 at 11:39 +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>

Reviewed-by: Huang Ying <ying.huang@intel.com>

> ---
> Changes since v3:
>  * Change n to use type *, to keep the same semantics as
>    list_for_each_entry_safe.
> Changes since v2:
>  * Allow to pass a NULL node as the first entry of deleted list
>    entries.
> ---
>  include/linux/llist.h |   29 +++++++++++++++++++++++++++++
>  1 files changed, 29 insertions(+), 0 deletions(-)
> 
> diff --git a/include/linux/llist.h b/include/linux/llist.h
> index a5199f6..f551ac4 100644
> --- a/include/linux/llist.h
> +++ b/include/linux/llist.h
> @@ -125,6 +125,35 @@ 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:		another type * to use as temporary storage
> + * @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) = llist_entry(((&(pos)->member != NULL) ?		\
> +	         (pos)->member.next : NULL), typeof(*(pos)), member);	\
> +	     &(pos)->member != NULL;					\
> +	     (pos) = n,							\
> +	     (n) = llist_entry(((&(pos)->member != NULL) ?		\
> +	         (pos)->member.next : NULL), typeof(*(pos)), member))
> +
> +/**
>   * llist_empty - tests whether a lock-less list is empty
>   * @head:	the list to test
>   *

[PATCH v4 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 |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/drivers/block/xen-blkfront.c b/drivers/block/xen-blkfront.c
index 96e9b00..8ae8062 100644
--- a/drivers/block/xen-blkfront.c
+++ b/drivers/block/xen-blkfront.c
@@ -791,7 +791,7 @@ static void blkif_restart_queue(struct work_struct *work)
 static void blkif_free(struct blkfront_info *info, int suspend)
 {
 	struct llist_node *all_gnts;
-	struct grant *persistent_gnt;
+	struct grant *persistent_gnt, *n;
 
 	/* Prevent new requests being issued until we fix things up. */
 	spin_lock_irq(&info->io_lock);
@@ -804,7 +804,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)