Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1705144 > unrolled thread

[PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-07 09:20 +0200
    Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Peter Zijlstra <peterz@infradead.org> - 2017-08-09 16:20 +0200
      Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-10 03:40 +0200
        Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Peter Zijlstra <peterz@infradead.org> - 2017-08-10 11:30 +0200
      Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-10 12:40 +0200
    Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Boqun Feng <boqun.feng@gmail.com> - 2017-08-10 14:00 +0200
      RE: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite "Byungchul Park" <byungchul.park@lge.com> - 2017-08-10 14:30 +0200
        Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Boqun Feng <boqun.feng@gmail.com> - 2017-08-10 15:00 +0200
          Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Boqun Feng <boqun.feng@gmail.com> - 2017-08-10 15:20 +0200
            Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-11 02:50 +0200
            Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-11 05:50 +0200
              Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Boqun Feng <boqun.feng@gmail.com> - 2017-08-11 10:10 +0200
                Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-11 11:00 +0200
                  Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-11 11:50 +0200
                    Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite Byungchul Park <max.byungchul.park@gmail.com> - 2017-08-11 15:10 +0200
          Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Byungchul Park <byungchul.park@lge.com> - 2017-08-11 02:50 +0200
            Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring  buffer overwrite Boqun Feng <boqun.feng@gmail.com> - 2017-08-11 03:10 +0200
    [tip:locking/core] locking/lockdep: Detect and handle hist_lock  ring buffer overwrite tip-bot for Byungchul Park <tipbot@zytor.com> - 2017-08-10 14:30 +0200

#1705144 — [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

The ring buffer can be overwritten by hardirq/softirq/work contexts.
That cases must be considered on rollback or commit. For example,

          |<------ hist_lock ring buffer size ----->|
          ppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
wrapped > iiiiiiiiiiiiiiiiiiiiiii....................

          where 'p' represents an acquisition in process context,
          'i' represents an acquisition in irq context.

On irq exit, crossrelease tries to rollback idx to original position,
but it should not because the entry already has been invalid by
overwriting 'i'. Avoid rollback or commit for entries overwritten.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/lockdep.h  | 20 +++++++++++++++++++
 include/linux/sched.h    |  3 +++
 kernel/locking/lockdep.c | 52 +++++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 70 insertions(+), 5 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index 0c8a1b8..48c244c 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,6 +284,26 @@ struct held_lock {
  */
 struct hist_lock {
 	/*
+	 * Id for each entry in the ring buffer. This is used to
+	 * decide whether the ring buffer was overwritten or not.
+	 *
+	 * For example,
+	 *
+	 *           |<----------- hist_lock ring buffer size ------->|
+	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
+	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
+	 *
+	 *           where 'p' represents an acquisition in process
+	 *           context, 'i' represents an acquisition in irq
+	 *           context.
+	 *
+	 * In this example, the ring buffer was overwritten by
+	 * acquisitions in irq context, that should be detected on
+	 * rollback or commit.
+	 */
+	unsigned int hist_id;
+
+	/*
 	 * Seperate stack_trace data. This will be used at commit step.
 	 */
 	struct stack_trace	trace;
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5becef5..373466b 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -855,6 +855,9 @@ struct task_struct {
 	unsigned int xhlock_idx;
 	/* For restoring at history boundaries */
 	unsigned int xhlock_idx_hist[CONTEXT_NR];
+	unsigned int hist_id;
+	/* For overwrite check at each context exit */
+	unsigned int hist_id_save[CONTEXT_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index afd6e64..5168dac 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
 static atomic_t cross_gen_id; /* Can be wrapped */
 
 /*
+ * Make an entry of the ring buffer invalid.
+ */
+static inline void invalidate_xhlock(struct hist_lock *xhlock)
+{
+	/*
+	 * Normally, xhlock->hlock.instance must be !NULL.
+	 */
+	xhlock->hlock.instance = NULL;
+}
+
+/*
  * Lock history stacks; we have 3 nested lock history stacks:
  *
  *   Hard IRQ
@@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
  */
 void crossrelease_hist_start(enum context_t c)
 {
-	if (current->xhlocks)
-		current->xhlock_idx_hist[c] = current->xhlock_idx;
+	struct task_struct *cur = current;
+
+	if (cur->xhlocks) {
+		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
+		cur->hist_id_save[c] = cur->hist_id;
+	}
 }
 
 void crossrelease_hist_end(enum context_t c)
 {
-	if (current->xhlocks)
-		current->xhlock_idx = current->xhlock_idx_hist[c];
+	struct task_struct *cur = current;
+
+	if (cur->xhlocks) {
+		unsigned int idx = cur->xhlock_idx_hist[c];
+		struct hist_lock *h = &xhlock(idx);
+
+		cur->xhlock_idx = idx;
+
+		/* Check if the ring was overwritten. */
+		if (h->hist_id != cur->hist_id_save[c])
+			invalidate_xhlock(h);
+	}
 }
 
 static int cross_lock(struct lockdep_map *lock)
@@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
  * Check if the xhlock is valid, which would be false if,
  *
  *    1. Has not used after initializaion yet.
+ *    2. Got invalidated.
  *
  * Remind hist_lock is implemented as a ring buffer.
  */
@@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
 
 	/* Initialize hist_lock's members */
 	xhlock->hlock = *hlock;
+	xhlock->hist_id = current->hist_id++;
 
 	xhlock->trace.nr_entries = 0;
 	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -4995,6 +5022,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
 	unsigned int cur = current->xhlock_idx;
+	unsigned int prev_hist_id = xhlock(cur).hist_id;
 	unsigned int i;
 
 	if (!graph_lock())
@@ -5013,6 +5041,17 @@ static void commit_xhlocks(struct cross_lock *xlock)
 			break;
 
 		/*
+		 * Filter out the cases that the ring buffer was
+		 * overwritten and the previous entry has a bigger
+		 * hist_id than the following one, which is impossible
+		 * otherwise.
+		 */
+		if (unlikely(before(xhlock->hist_id, prev_hist_id)))
+			break;
+
+		prev_hist_id = xhlock->hist_id;
+
+		/*
 		 * commit_xhlock() returns 0 with graph_lock already
 		 * released if fail.
 		 */
@@ -5085,9 +5124,12 @@ void lockdep_init_task(struct task_struct *task)
 	int i;
 
 	task->xhlock_idx = UINT_MAX;
+	task->hist_id = 0;
 
-	for (i = 0; i < CONTEXT_NR; i++)
+	for (i = 0; i < CONTEXT_NR; i++) {
 		task->xhlock_idx_hist[i] = UINT_MAX;
+		task->hist_id_save[i] = 0;
+	}
 
 	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
 				GFP_KERNEL);
-- 
1.9.1

[toc] | [next] | [standalone]

#1707370 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
>   */
>  void crossrelease_hist_start(enum context_t c)
>  {
> -	if (current->xhlocks)
> -		current->xhlock_idx_hist[c] = current->xhlock_idx;
> +	struct task_struct *cur = current;
> +
> +	if (cur->xhlocks) {
> +		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> +		cur->hist_id_save[c] = cur->hist_id;
> +	}
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
> -	if (current->xhlocks)
> -		current->xhlock_idx = current->xhlock_idx_hist[c];
> +	struct task_struct *cur = current;
> +
> +	if (cur->xhlocks) {
> +		unsigned int idx = cur->xhlock_idx_hist[c];
> +		struct hist_lock *h = &xhlock(idx);
> +
> +		cur->xhlock_idx = idx;
> +
> +		/* Check if the ring was overwritten. */
> +		if (h->hist_id != cur->hist_id_save[c])
> +			invalidate_xhlock(h);
> +	}
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
>   * Check if the xhlock is valid, which would be false if,
>   *
>   *    1. Has not used after initializaion yet.
> + *    2. Got invalidated.
>   *
>   * Remind hist_lock is implemented as a ring buffer.
>   */
> @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>  	/* Initialize hist_lock's members */
>  	xhlock->hlock = *hlock;
> +	xhlock->hist_id = current->hist_id++;
>  
>  	xhlock->trace.nr_entries = 0;
>  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;


Hehe, _another_ scheme...

Yes I think this works.. but I had just sort of understood the last one.

How about I do this on top? That I think is a combination of what I
proposed last and your single invalidate thing. Combined they solve the
problem with the least amount of extra storage (a single int).


---
Subject: lockdep: Simplify xhlock ring buffer invalidation
From: Peter Zijlstra <peterz@infradead.org>
Date: Wed Aug 9 15:31:27 CEST 2017


Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 include/linux/lockdep.h  |   20 -----------
 include/linux/sched.h    |    4 --
 kernel/locking/lockdep.c |   82 ++++++++++++++++++++++++++++++-----------------
 3 files changed, 54 insertions(+), 52 deletions(-)

--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,26 +284,6 @@ struct held_lock {
  */
 struct hist_lock {
 	/*
-	 * Id for each entry in the ring buffer. This is used to
-	 * decide whether the ring buffer was overwritten or not.
-	 *
-	 * For example,
-	 *
-	 *           |<----------- hist_lock ring buffer size ------->|
-	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
-	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
-	 *
-	 *           where 'p' represents an acquisition in process
-	 *           context, 'i' represents an acquisition in irq
-	 *           context.
-	 *
-	 * In this example, the ring buffer was overwritten by
-	 * acquisitions in irq context, that should be detected on
-	 * rollback or commit.
-	 */
-	unsigned int hist_id;
-
-	/*
 	 * Seperate stack_trace data. This will be used at commit step.
 	 */
 	struct stack_trace	trace;
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -855,9 +855,7 @@ struct task_struct {
 	unsigned int xhlock_idx;
 	/* For restoring at history boundaries */
 	unsigned int xhlock_idx_hist[XHLOCK_NR];
-	unsigned int hist_id;
-	/* For overwrite check at each context exit */
-	unsigned int hist_id_save[XHLOCK_NR];
+	unsigned int xhlock_idx_max;
 #endif
 
 #ifdef CONFIG_UBSAN
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
 {
 	struct task_struct *cur = current;
 
-	if (cur->xhlocks) {
+	if (cur->xhlocks)
 		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
-		cur->hist_id_save[c] = cur->hist_id;
-	}
 }
 
 void crossrelease_hist_end(enum context_t c)
 {
 	struct task_struct *cur = current;
+	unsigned int idx;
 
-	if (cur->xhlocks) {
-		unsigned int idx = cur->xhlock_idx_hist[c];
-		struct hist_lock *h = &xhlock(idx);
-
-		cur->xhlock_idx = idx;
-
-		/* Check if the ring was overwritten. */
-		if (h->hist_id != cur->hist_id_save[c])
-			invalidate_xhlock(h);
-	}
+	if (!cur->xhlocks)
+		return;
+
+	idx = cur->xhlock_idx_hist[c];
+	cur->xhlock_idx = idx;
+
+	/*
+	 * A bit of magic here.. this deals with rewinding the (cyclic) history
+	 * array further than its size. IOW. looses the complete history.
+	 *
+	 * We detect this by tracking the previous oldest entry we've (over)
+	 * written in @xhlock_idx_max, this means the next entry is the oldest
+	 * entry still in the buffer, ie. its tail.
+	 *
+	 * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
+	 * older than @xhlock_idx_max we know we've just wiped the entire
+	 * history.
+	 */
+	if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
+		return;
+
+	/*
+	 * Now that we know the buffer is effectively empty, reset our state
+	 * such that it appears empty (without in fact clearing the entire
+	 * buffer).
+	 *
+	 * Pick @idx as the 'new' beginning, (re)set all save-points to not
+	 * rewind past it and reset the max. Then invalidate this idx such that
+	 * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
+	 * will return the _next_ entry, we'll not overwrite this invalid entry
+	 * until the entire buffer is full again.
+	 */
+	for (c = 0; c < XHLOCK_NR; c++)
+		cur->xhlock_idx_hist[c] = idx;
+	cur->xhlock_idx_max = idx;
+	invalidate_xhlock(&xhlock(idx));
+}
+
+static inline unsigned int xhlock_idx_inc(void)
+{
+	struct task_struct *cur = current;
+	unsigned int idx = ++cur->xhlock_idx;
+
+	/*
+	 * As per the requirement in crossrelease_hist_end(), track the tail.
+	 */
+	if ((int)(cur->xhlock_idx_max - idx) < 0)
+		cur->xhlock_idx_max = idx;
+
+	return idx;
 }
 
 static int cross_lock(struct lockdep_map *lock)
@@ -4902,7 +4941,7 @@ static inline int xhlock_valid(struct hi
  */
 static void add_xhlock(struct held_lock *hlock)
 {
-	unsigned int idx = ++current->xhlock_idx;
+	unsigned int idx = xhlock_idx_inc();
 	struct hist_lock *xhlock = &xhlock(idx);
 
 #ifdef CONFIG_DEBUG_LOCKDEP
@@ -4915,7 +4954,6 @@ static void add_xhlock(struct held_lock
 
 	/* Initialize hist_lock's members */
 	xhlock->hlock = *hlock;
-	xhlock->hist_id = current->hist_id++;
 
 	xhlock->trace.nr_entries = 0;
 	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -5071,7 +5109,6 @@ static int commit_xhlock(struct cross_lo
 static void commit_xhlocks(struct cross_lock *xlock)
 {
 	unsigned int cur = current->xhlock_idx;
-	unsigned int prev_hist_id = xhlock(cur).hist_id;
 	unsigned int i;
 
 	if (!graph_lock())
@@ -5091,17 +5128,6 @@ static void commit_xhlocks(struct cross_
 				break;
 
 			/*
-			 * Filter out the cases that the ring buffer was
-			 * overwritten and the previous entry has a bigger
-			 * hist_id than the following one, which is impossible
-			 * otherwise.
-			 */
-			if (unlikely(before(xhlock->hist_id, prev_hist_id)))
-				break;
-
-			prev_hist_id = xhlock->hist_id;
-
-			/*
 			 * commit_xhlock() returns 0 with graph_lock already
 			 * released if fail.
 			 */
@@ -5186,11 +5212,9 @@ void lockdep_init_task(struct task_struc
 	int i;
 
 	task->xhlock_idx = UINT_MAX;
-	task->hist_id = 0;
 
 	for (i = 0; i < XHLOCK_NR; i++) {
 		task->xhlock_idx_hist[i] = UINT_MAX;
-		task->hist_id_save[i] = 0;
 	}
 
 	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,

[toc] | [prev] | [next] | [standalone]

#1708130 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> Hehe, _another_ scheme...
> 
> Yes I think this works.. but I had just sort of understood the last one.
> 
> How about I do this on top? That I think is a combination of what I
> proposed last and your single invalidate thing. Combined they solve the
> problem with the least amount of extra storage (a single int).

I'm sorry for saying that.. I'm not sure if this works well.

> ---
> Subject: lockdep: Simplify xhlock ring buffer invalidation
> From: Peter Zijlstra <peterz@infradead.org>
> Date: Wed Aug 9 15:31:27 CEST 2017
> 
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  include/linux/lockdep.h  |   20 -----------
>  include/linux/sched.h    |    4 --
>  kernel/locking/lockdep.c |   82 ++++++++++++++++++++++++++++++-----------------
>  3 files changed, 54 insertions(+), 52 deletions(-)
> 
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,26 +284,6 @@ struct held_lock {
>   */
>  struct hist_lock {
>  	/*
> -	 * Id for each entry in the ring buffer. This is used to
> -	 * decide whether the ring buffer was overwritten or not.
> -	 *
> -	 * For example,
> -	 *
> -	 *           |<----------- hist_lock ring buffer size ------->|
> -	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> -	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
> -	 *
> -	 *           where 'p' represents an acquisition in process
> -	 *           context, 'i' represents an acquisition in irq
> -	 *           context.
> -	 *
> -	 * In this example, the ring buffer was overwritten by
> -	 * acquisitions in irq context, that should be detected on
> -	 * rollback or commit.
> -	 */
> -	unsigned int hist_id;
> -
> -	/*
>  	 * Seperate stack_trace data. This will be used at commit step.
>  	 */
>  	struct stack_trace	trace;
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,9 +855,7 @@ struct task_struct {
>  	unsigned int xhlock_idx;
>  	/* For restoring at history boundaries */
>  	unsigned int xhlock_idx_hist[XHLOCK_NR];
> -	unsigned int hist_id;
> -	/* For overwrite check at each context exit */
> -	unsigned int hist_id_save[XHLOCK_NR];
> +	unsigned int xhlock_idx_max;
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
>  {
>  	struct task_struct *cur = current;
>  
> -	if (cur->xhlocks) {
> +	if (cur->xhlocks)
>  		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> -		cur->hist_id_save[c] = cur->hist_id;
> -	}
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
>  	struct task_struct *cur = current;
> +	unsigned int idx;
>  
> -	if (cur->xhlocks) {
> -		unsigned int idx = cur->xhlock_idx_hist[c];
> -		struct hist_lock *h = &xhlock(idx);
> -
> -		cur->xhlock_idx = idx;
> -
> -		/* Check if the ring was overwritten. */
> -		if (h->hist_id != cur->hist_id_save[c])
> -			invalidate_xhlock(h);
> -	}
> +	if (!cur->xhlocks)
> +		return;
> +
> +	idx = cur->xhlock_idx_hist[c];
> +	cur->xhlock_idx = idx;
> +
> +	/*
> +	 * A bit of magic here.. this deals with rewinding the (cyclic) history
> +	 * array further than its size. IOW. looses the complete history.
> +	 *
> +	 * We detect this by tracking the previous oldest entry we've (over)
> +	 * written in @xhlock_idx_max, this means the next entry is the oldest
> +	 * entry still in the buffer, ie. its tail.
> +	 *
> +	 * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
> +	 * older than @xhlock_idx_max we know we've just wiped the entire
> +	 * history.
> +	 */
> +	if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
> +		return;
> +
> +	/*
> +	 * Now that we know the buffer is effectively empty, reset our state
> +	 * such that it appears empty (without in fact clearing the entire
> +	 * buffer).
> +	 *
> +	 * Pick @idx as the 'new' beginning, (re)set all save-points to not
> +	 * rewind past it and reset the max. Then invalidate this idx such that
> +	 * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
> +	 * will return the _next_ entry, we'll not overwrite this invalid entry
> +	 * until the entire buffer is full again.
> +	 */
> +	for (c = 0; c < XHLOCK_NR; c++)
> +		cur->xhlock_idx_hist[c] = idx;
> +	cur->xhlock_idx_max = idx;
> +	invalidate_xhlock(&xhlock(idx));
> +}
> +
> +static inline unsigned int xhlock_idx_inc(void)
> +{
> +	struct task_struct *cur = current;
> +	unsigned int idx = ++cur->xhlock_idx;
> +
> +	/*
> +	 * As per the requirement in crossrelease_hist_end(), track the tail.
> +	 */
> +	if ((int)(cur->xhlock_idx_max - idx) < 0)
> +		cur->xhlock_idx_max = idx;
> +
> +	return idx;
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4902,7 +4941,7 @@ static inline int xhlock_valid(struct hi
>   */
>  static void add_xhlock(struct held_lock *hlock)
>  {
> -	unsigned int idx = ++current->xhlock_idx;
> +	unsigned int idx = xhlock_idx_inc();
>  	struct hist_lock *xhlock = &xhlock(idx);
>  
>  #ifdef CONFIG_DEBUG_LOCKDEP
> @@ -4915,7 +4954,6 @@ static void add_xhlock(struct held_lock
>  
>  	/* Initialize hist_lock's members */
>  	xhlock->hlock = *hlock;
> -	xhlock->hist_id = current->hist_id++;
>  
>  	xhlock->trace.nr_entries = 0;
>  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5071,7 +5109,6 @@ static int commit_xhlock(struct cross_lo
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>  	unsigned int cur = current->xhlock_idx;
> -	unsigned int prev_hist_id = xhlock(cur).hist_id;
>  	unsigned int i;
>  
>  	if (!graph_lock())
> @@ -5091,17 +5128,6 @@ static void commit_xhlocks(struct cross_
>  				break;
>  
>  			/*
> -			 * Filter out the cases that the ring buffer was
> -			 * overwritten and the previous entry has a bigger
> -			 * hist_id than the following one, which is impossible
> -			 * otherwise.
> -			 */
> -			if (unlikely(before(xhlock->hist_id, prev_hist_id)))
> -				break;
> -
> -			prev_hist_id = xhlock->hist_id;
> -
> -			/*
>  			 * commit_xhlock() returns 0 with graph_lock already
>  			 * released if fail.
>  			 */
> @@ -5186,11 +5212,9 @@ void lockdep_init_task(struct task_struc
>  	int i;
>  
>  	task->xhlock_idx = UINT_MAX;
> -	task->hist_id = 0;
>  
>  	for (i = 0; i < XHLOCK_NR; i++) {
>  		task->xhlock_idx_hist[i] = UINT_MAX;
> -		task->hist_id_save[i] = 0;
>  	}
>  
>  	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,

[toc] | [prev] | [next] | [standalone]

#1708360 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Thu, Aug 10, 2017 at 10:32:16AM +0900, Byungchul Park wrote:
> On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> > Hehe, _another_ scheme...
> > 
> > Yes I think this works.. but I had just sort of understood the last one.
> > 
> > How about I do this on top? That I think is a combination of what I
> > proposed last and your single invalidate thing. Combined they solve the
> > problem with the least amount of extra storage (a single int).
> 
> I'm sorry for saying that.. I'm not sure if this works well.

OK, I'll sit on the patch a little while, if you could share your
concerns then maybe I can improve the comments ;-)

[toc] | [prev] | [next] | [standalone]

#1708403 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Wed, Aug 09, 2017 at 04:16:05PM +0200, Peter Zijlstra wrote:
> 
> Hehe, _another_ scheme...
> 
> Yes I think this works.. but I had just sort of understood the last one.
> 
> How about I do this on top? That I think is a combination of what I
> proposed last and your single invalidate thing. Combined they solve the
> problem with the least amount of extra storage (a single int).
> 

I like your trying because it looks like making code simple, but there are
some cases the patch does not cover.

          pppppppppppppppwwwwwwwwwwwwwwwwwwwwwwwwwiiiiiiiiiiiii
wrapped > iiiiiiiiiiiiiiiiiiiii................................

          where,
          p: process
          w: work
          i: irq

In this case, your patch cannot detect overwriting 'w' with 'i'. What do
you think about it?

> ---
> Subject: lockdep: Simplify xhlock ring buffer invalidation
> From: Peter Zijlstra <peterz@infradead.org>
> Date: Wed Aug 9 15:31:27 CEST 2017
> 
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  include/linux/lockdep.h  |   20 -----------
>  include/linux/sched.h    |    4 --
>  kernel/locking/lockdep.c |   82 ++++++++++++++++++++++++++++++-----------------
>  3 files changed, 54 insertions(+), 52 deletions(-)
> 
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,26 +284,6 @@ struct held_lock {
>   */
>  struct hist_lock {
>  	/*
> -	 * Id for each entry in the ring buffer. This is used to
> -	 * decide whether the ring buffer was overwritten or not.
> -	 *
> -	 * For example,
> -	 *
> -	 *           |<----------- hist_lock ring buffer size ------->|
> -	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> -	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
> -	 *
> -	 *           where 'p' represents an acquisition in process
> -	 *           context, 'i' represents an acquisition in irq
> -	 *           context.
> -	 *
> -	 * In this example, the ring buffer was overwritten by
> -	 * acquisitions in irq context, that should be detected on
> -	 * rollback or commit.
> -	 */
> -	unsigned int hist_id;
> -
> -	/*
>  	 * Seperate stack_trace data. This will be used at commit step.
>  	 */
>  	struct stack_trace	trace;
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,9 +855,7 @@ struct task_struct {
>  	unsigned int xhlock_idx;
>  	/* For restoring at history boundaries */
>  	unsigned int xhlock_idx_hist[XHLOCK_NR];
> -	unsigned int hist_id;
> -	/* For overwrite check at each context exit */
> -	unsigned int hist_id_save[XHLOCK_NR];
> +	unsigned int xhlock_idx_max;
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4818,26 +4818,65 @@ void crossrelease_hist_start(enum contex
>  {
>  	struct task_struct *cur = current;
>  
> -	if (cur->xhlocks) {
> +	if (cur->xhlocks)
>  		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> -		cur->hist_id_save[c] = cur->hist_id;
> -	}
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
>  	struct task_struct *cur = current;
> +	unsigned int idx;
>  
> -	if (cur->xhlocks) {
> -		unsigned int idx = cur->xhlock_idx_hist[c];
> -		struct hist_lock *h = &xhlock(idx);
> -
> -		cur->xhlock_idx = idx;
> -
> -		/* Check if the ring was overwritten. */
> -		if (h->hist_id != cur->hist_id_save[c])
> -			invalidate_xhlock(h);
> -	}
> +	if (!cur->xhlocks)
> +		return;
> +
> +	idx = cur->xhlock_idx_hist[c];
> +	cur->xhlock_idx = idx;
> +
> +	/*
> +	 * A bit of magic here.. this deals with rewinding the (cyclic) history
> +	 * array further than its size. IOW. looses the complete history.
> +	 *
> +	 * We detect this by tracking the previous oldest entry we've (over)
> +	 * written in @xhlock_idx_max, this means the next entry is the oldest
> +	 * entry still in the buffer, ie. its tail.
> +	 *
> +	 * So when we restore an @xhlock_idx that is at least MAX_XHLOCKS_NR
> +	 * older than @xhlock_idx_max we know we've just wiped the entire
> +	 * history.
> +	 */
> +	if ((cur->xhlock_idx_max - idx) < MAX_XHLOCKS_NR)
> +		return;
> +
> +	/*
> +	 * Now that we know the buffer is effectively empty, reset our state
> +	 * such that it appears empty (without in fact clearing the entire
> +	 * buffer).
> +	 *
> +	 * Pick @idx as the 'new' beginning, (re)set all save-points to not
> +	 * rewind past it and reset the max. Then invalidate this idx such that
> +	 * commit_xhlocks() will never rewind past it. Since xhlock_idx_inc()
> +	 * will return the _next_ entry, we'll not overwrite this invalid entry
> +	 * until the entire buffer is full again.
> +	 */
> +	for (c = 0; c < XHLOCK_NR; c++)
> +		cur->xhlock_idx_hist[c] = idx;
> +	cur->xhlock_idx_max = idx;
> +	invalidate_xhlock(&xhlock(idx));
> +}
> +
> +static inline unsigned int xhlock_idx_inc(void)
> +{
> +	struct task_struct *cur = current;
> +	unsigned int idx = ++cur->xhlock_idx;
> +
> +	/*
> +	 * As per the requirement in crossrelease_hist_end(), track the tail.
> +	 */
> +	if ((int)(cur->xhlock_idx_max - idx) < 0)
> +		cur->xhlock_idx_max = idx;
> +
> +	return idx;
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4902,7 +4941,7 @@ static inline int xhlock_valid(struct hi
>   */
>  static void add_xhlock(struct held_lock *hlock)
>  {
> -	unsigned int idx = ++current->xhlock_idx;
> +	unsigned int idx = xhlock_idx_inc();
>  	struct hist_lock *xhlock = &xhlock(idx);
>  
>  #ifdef CONFIG_DEBUG_LOCKDEP
> @@ -4915,7 +4954,6 @@ static void add_xhlock(struct held_lock
>  
>  	/* Initialize hist_lock's members */
>  	xhlock->hlock = *hlock;
> -	xhlock->hist_id = current->hist_id++;
>  
>  	xhlock->trace.nr_entries = 0;
>  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5071,7 +5109,6 @@ static int commit_xhlock(struct cross_lo
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>  	unsigned int cur = current->xhlock_idx;
> -	unsigned int prev_hist_id = xhlock(cur).hist_id;
>  	unsigned int i;
>  
>  	if (!graph_lock())
> @@ -5091,17 +5128,6 @@ static void commit_xhlocks(struct cross_
>  				break;
>  
>  			/*
> -			 * Filter out the cases that the ring buffer was
> -			 * overwritten and the previous entry has a bigger
> -			 * hist_id than the following one, which is impossible
> -			 * otherwise.
> -			 */
> -			if (unlikely(before(xhlock->hist_id, prev_hist_id)))
> -				break;
> -
> -			prev_hist_id = xhlock->hist_id;
> -
> -			/*
>  			 * commit_xhlock() returns 0 with graph_lock already
>  			 * released if fail.
>  			 */
> @@ -5186,11 +5212,9 @@ void lockdep_init_task(struct task_struc
>  	int i;
>  
>  	task->xhlock_idx = UINT_MAX;
> -	task->hist_id = 0;
>  
>  	for (i = 0; i < XHLOCK_NR; i++) {
>  		task->xhlock_idx_hist[i] = UINT_MAX;
> -		task->hist_id_save[i] = 0;
>  	}
>  
>  	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,

[toc] | [prev] | [next] | [standalone]

#1708488 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Multipart message — attachments visible in raw view] — view raw

On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> The ring buffer can be overwritten by hardirq/softirq/work contexts.
> That cases must be considered on rollback or commit. For example,
> 
>           |<------ hist_lock ring buffer size ----->|
>           ppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> wrapped > iiiiiiiiiiiiiiiiiiiiiii....................
> 
>           where 'p' represents an acquisition in process context,
>           'i' represents an acquisition in irq context.
> 
> On irq exit, crossrelease tries to rollback idx to original position,
> but it should not because the entry already has been invalid by
> overwriting 'i'. Avoid rollback or commit for entries overwritten.
> 
> Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> ---
>  include/linux/lockdep.h  | 20 +++++++++++++++++++
>  include/linux/sched.h    |  3 +++
>  kernel/locking/lockdep.c | 52 +++++++++++++++++++++++++++++++++++++++++++-----
>  3 files changed, 70 insertions(+), 5 deletions(-)
> 
> diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> index 0c8a1b8..48c244c 100644
> --- a/include/linux/lockdep.h
> +++ b/include/linux/lockdep.h
> @@ -284,6 +284,26 @@ struct held_lock {
>   */
>  struct hist_lock {
>  	/*
> +	 * Id for each entry in the ring buffer. This is used to
> +	 * decide whether the ring buffer was overwritten or not.
> +	 *
> +	 * For example,
> +	 *
> +	 *           |<----------- hist_lock ring buffer size ------->|
> +	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> +	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
> +	 *
> +	 *           where 'p' represents an acquisition in process
> +	 *           context, 'i' represents an acquisition in irq
> +	 *           context.
> +	 *
> +	 * In this example, the ring buffer was overwritten by
> +	 * acquisitions in irq context, that should be detected on
> +	 * rollback or commit.
> +	 */
> +	unsigned int hist_id;
> +
> +	/*
>  	 * Seperate stack_trace data. This will be used at commit step.
>  	 */
>  	struct stack_trace	trace;
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 5becef5..373466b 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -855,6 +855,9 @@ struct task_struct {
>  	unsigned int xhlock_idx;
>  	/* For restoring at history boundaries */
>  	unsigned int xhlock_idx_hist[CONTEXT_NR];
> +	unsigned int hist_id;
> +	/* For overwrite check at each context exit */
> +	unsigned int hist_id_save[CONTEXT_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index afd6e64..5168dac 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
>  static atomic_t cross_gen_id; /* Can be wrapped */
>  
>  /*
> + * Make an entry of the ring buffer invalid.
> + */
> +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> +{
> +	/*
> +	 * Normally, xhlock->hlock.instance must be !NULL.
> +	 */
> +	xhlock->hlock.instance = NULL;
> +}
> +
> +/*
>   * Lock history stacks; we have 3 nested lock history stacks:
>   *
>   *   Hard IRQ
> @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file, const int line, const char *s)
>   */
>  void crossrelease_hist_start(enum context_t c)
>  {
> -	if (current->xhlocks)
> -		current->xhlock_idx_hist[c] = current->xhlock_idx;
> +	struct task_struct *cur = current;
> +
> +	if (cur->xhlocks) {
> +		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> +		cur->hist_id_save[c] = cur->hist_id;
> +	}
>  }
>  
>  void crossrelease_hist_end(enum context_t c)
>  {
> -	if (current->xhlocks)
> -		current->xhlock_idx = current->xhlock_idx_hist[c];
> +	struct task_struct *cur = current;
> +
> +	if (cur->xhlocks) {
> +		unsigned int idx = cur->xhlock_idx_hist[c];
> +		struct hist_lock *h = &xhlock(idx);
> +
> +		cur->xhlock_idx = idx;
> +
> +		/* Check if the ring was overwritten. */
> +		if (h->hist_id != cur->hist_id_save[c])

Could we use:

		if (h->hist_id != idx)

here, and

> +			invalidate_xhlock(h);
> +	}
>  }
>  
>  static int cross_lock(struct lockdep_map *lock)
> @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock *hlock)
>   * Check if the xhlock is valid, which would be false if,
>   *
>   *    1. Has not used after initializaion yet.
> + *    2. Got invalidated.
>   *
>   * Remind hist_lock is implemented as a ring buffer.
>   */
> @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>  	/* Initialize hist_lock's members */
>  	xhlock->hlock = *hlock;
> +	xhlock->hist_id = current->hist_id++;

use:

	xhlock->hist_id = idx;

and,


>  
>  	xhlock->trace.nr_entries = 0;
>  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -4995,6 +5022,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>  	unsigned int cur = current->xhlock_idx;
> +	unsigned int prev_hist_id = xhlock(cur).hist_id;

use:
	unsigned int prev_hist_id = cur;

here.

Then we can get away with the added fields in task_struct at least.

Thought?

Regards,
Boqun

>  	unsigned int i;
>  
>  	if (!graph_lock())
> @@ -5013,6 +5041,17 @@ static void commit_xhlocks(struct cross_lock *xlock)
>  			break;
>  
>  		/*
> +		 * Filter out the cases that the ring buffer was
> +		 * overwritten and the previous entry has a bigger
> +		 * hist_id than the following one, which is impossible
> +		 * otherwise.
> +		 */
> +		if (unlikely(before(xhlock->hist_id, prev_hist_id)))
> +			break;
> +
> +		prev_hist_id = xhlock->hist_id;
> +
> +		/*
>  		 * commit_xhlock() returns 0 with graph_lock already
>  		 * released if fail.
>  		 */
> @@ -5085,9 +5124,12 @@ void lockdep_init_task(struct task_struct *task)
>  	int i;
>  
>  	task->xhlock_idx = UINT_MAX;
> +	task->hist_id = 0;
>  
> -	for (i = 0; i < CONTEXT_NR; i++)
> +	for (i = 0; i < CONTEXT_NR; i++) {
>  		task->xhlock_idx_hist[i] = UINT_MAX;
> +		task->hist_id_save[i] = 0;
> +	}
>  
>  	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
>  				GFP_KERNEL);
> -- 
> 1.9.1
> 

[toc] | [prev] | [next] | [standalone]

#1708568

> -----Original Message-----
> From: Boqun Feng [mailto:boqun.feng@gmail.com]
> Sent: Thursday, August 10, 2017 8:59 PM
> To: Byungchul Park
> Cc: peterz@infradead.org; mingo@kernel.org; tglx@linutronix.de;
> walken@google.com; kirill@shutemov.name; linux-kernel@vger.kernel.org;
> linux-mm@kvack.org; akpm@linux-foundation.org; willy@infradead.org;
> npiggin@gmail.com; kernel-team@lge.com
> Subject: Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring
> buffer overwrite
> 
> On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> > The ring buffer can be overwritten by hardirq/softirq/work contexts.
> > That cases must be considered on rollback or commit. For example,
> >
> >           |<------ hist_lock ring buffer size ----->|
> >           ppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> > wrapped > iiiiiiiiiiiiiiiiiiiiiii....................
> >
> >           where 'p' represents an acquisition in process context,
> >           'i' represents an acquisition in irq context.
> >
> > On irq exit, crossrelease tries to rollback idx to original position,
> > but it should not because the entry already has been invalid by
> > overwriting 'i'. Avoid rollback or commit for entries overwritten.
> >
> > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > ---
> >  include/linux/lockdep.h  | 20 +++++++++++++++++++
> >  include/linux/sched.h    |  3 +++
> >  kernel/locking/lockdep.c | 52
> +++++++++++++++++++++++++++++++++++++++++++-----
> >  3 files changed, 70 insertions(+), 5 deletions(-)
> >
> > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > index 0c8a1b8..48c244c 100644
> > --- a/include/linux/lockdep.h
> > +++ b/include/linux/lockdep.h
> > @@ -284,6 +284,26 @@ struct held_lock {
> >   */
> >  struct hist_lock {
> >  	/*
> > +	 * Id for each entry in the ring buffer. This is used to
> > +	 * decide whether the ring buffer was overwritten or not.
> > +	 *
> > +	 * For example,
> > +	 *
> > +	 *           |<----------- hist_lock ring buffer size ------->|
> > +	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> > +	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
> > +	 *
> > +	 *           where 'p' represents an acquisition in process
> > +	 *           context, 'i' represents an acquisition in irq
> > +	 *           context.
> > +	 *
> > +	 * In this example, the ring buffer was overwritten by
> > +	 * acquisitions in irq context, that should be detected on
> > +	 * rollback or commit.
> > +	 */
> > +	unsigned int hist_id;
> > +
> > +	/*
> >  	 * Seperate stack_trace data. This will be used at commit step.
> >  	 */
> >  	struct stack_trace	trace;
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 5becef5..373466b 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -855,6 +855,9 @@ struct task_struct {
> >  	unsigned int xhlock_idx;
> >  	/* For restoring at history boundaries */
> >  	unsigned int xhlock_idx_hist[CONTEXT_NR];
> > +	unsigned int hist_id;
> > +	/* For overwrite check at each context exit */
> > +	unsigned int hist_id_save[CONTEXT_NR];
> >  #endif
> >
> >  #ifdef CONFIG_UBSAN
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index afd6e64..5168dac 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file,
> const int line, const char *s)
> >  static atomic_t cross_gen_id; /* Can be wrapped */
> >
> >  /*
> > + * Make an entry of the ring buffer invalid.
> > + */
> > +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> > +{
> > +	/*
> > +	 * Normally, xhlock->hlock.instance must be !NULL.
> > +	 */
> > +	xhlock->hlock.instance = NULL;
> > +}
> > +
> > +/*
> >   * Lock history stacks; we have 3 nested lock history stacks:
> >   *
> >   *   Hard IRQ
> > @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file,
> const int line, const char *s)
> >   */
> >  void crossrelease_hist_start(enum context_t c)
> >  {
> > -	if (current->xhlocks)
> > -		current->xhlock_idx_hist[c] = current->xhlock_idx;
> > +	struct task_struct *cur = current;
> > +
> > +	if (cur->xhlocks) {
> > +		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> > +		cur->hist_id_save[c] = cur->hist_id;
> > +	}
> >  }
> >
> >  void crossrelease_hist_end(enum context_t c)
> >  {
> > -	if (current->xhlocks)
> > -		current->xhlock_idx = current->xhlock_idx_hist[c];
> > +	struct task_struct *cur = current;
> > +
> > +	if (cur->xhlocks) {
> > +		unsigned int idx = cur->xhlock_idx_hist[c];
> > +		struct hist_lock *h = &xhlock(idx);
> > +
> > +		cur->xhlock_idx = idx;
> > +
> > +		/* Check if the ring was overwritten. */
> > +		if (h->hist_id != cur->hist_id_save[c])
> 
> Could we use:
> 
> 		if (h->hist_id != idx)

No, we cannot.

hist_id is a kind of timestamp and used to detect overwriting
data into places of same indexes of the ring buffer. And idx is
just an index. :) IOW, they mean different things.

> 
> here, and
> 
> > +			invalidate_xhlock(h);
> > +	}
> >  }
> >
> >  static int cross_lock(struct lockdep_map *lock)
> > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> *hlock)
> >   * Check if the xhlock is valid, which would be false if,
> >   *
> >   *    1. Has not used after initializaion yet.
> > + *    2. Got invalidated.
> >   *
> >   * Remind hist_lock is implemented as a ring buffer.
> >   */
> > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> >
> >  	/* Initialize hist_lock's members */
> >  	xhlock->hlock = *hlock;
> > +	xhlock->hist_id = current->hist_id++;
> 
> use:
> 
> 	xhlock->hist_id = idx;
> 
> and,

Same.

> 
> 
> >
> >  	xhlock->trace.nr_entries = 0;
> >  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > @@ -4995,6 +5022,7 @@ static int commit_xhlock(struct cross_lock *xlock,
> struct hist_lock *xhlock)
> >  static void commit_xhlocks(struct cross_lock *xlock)
> >  {
> >  	unsigned int cur = current->xhlock_idx;
> > +	unsigned int prev_hist_id = xhlock(cur).hist_id;
> 
> use:
> 	unsigned int prev_hist_id = cur;
> 
> here.

Same.

[toc] | [prev] | [next] | [standalone]

#1708603 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Multipart message — attachments visible in raw view] — view raw

On Thu, Aug 10, 2017 at 09:11:32PM +0900, Byungchul Park wrote:
> > -----Original Message-----
> > From: Boqun Feng [mailto:boqun.feng@gmail.com]
> > Sent: Thursday, August 10, 2017 8:59 PM
> > To: Byungchul Park
> > Cc: peterz@infradead.org; mingo@kernel.org; tglx@linutronix.de;
> > walken@google.com; kirill@shutemov.name; linux-kernel@vger.kernel.org;
> > linux-mm@kvack.org; akpm@linux-foundation.org; willy@infradead.org;
> > npiggin@gmail.com; kernel-team@lge.com
> > Subject: Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring
> > buffer overwrite
> > 
> > On Mon, Aug 07, 2017 at 04:12:53PM +0900, Byungchul Park wrote:
> > > The ring buffer can be overwritten by hardirq/softirq/work contexts.
> > > That cases must be considered on rollback or commit. For example,
> > >
> > >           |<------ hist_lock ring buffer size ----->|
> > >           ppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> > > wrapped > iiiiiiiiiiiiiiiiiiiiiii....................
> > >
> > >           where 'p' represents an acquisition in process context,
> > >           'i' represents an acquisition in irq context.
> > >
> > > On irq exit, crossrelease tries to rollback idx to original position,
> > > but it should not because the entry already has been invalid by
> > > overwriting 'i'. Avoid rollback or commit for entries overwritten.
> > >
> > > Signed-off-by: Byungchul Park <byungchul.park@lge.com>
> > > ---
> > >  include/linux/lockdep.h  | 20 +++++++++++++++++++
> > >  include/linux/sched.h    |  3 +++
> > >  kernel/locking/lockdep.c | 52
> > +++++++++++++++++++++++++++++++++++++++++++-----
> > >  3 files changed, 70 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
> > > index 0c8a1b8..48c244c 100644
> > > --- a/include/linux/lockdep.h
> > > +++ b/include/linux/lockdep.h
> > > @@ -284,6 +284,26 @@ struct held_lock {
> > >   */
> > >  struct hist_lock {
> > >  	/*
> > > +	 * Id for each entry in the ring buffer. This is used to
> > > +	 * decide whether the ring buffer was overwritten or not.
> > > +	 *
> > > +	 * For example,
> > > +	 *
> > > +	 *           |<----------- hist_lock ring buffer size ------->|
> > > +	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
> > > +	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
> > > +	 *
> > > +	 *           where 'p' represents an acquisition in process
> > > +	 *           context, 'i' represents an acquisition in irq
> > > +	 *           context.
> > > +	 *
> > > +	 * In this example, the ring buffer was overwritten by
> > > +	 * acquisitions in irq context, that should be detected on
> > > +	 * rollback or commit.
> > > +	 */
> > > +	unsigned int hist_id;
> > > +
> > > +	/*
> > >  	 * Seperate stack_trace data. This will be used at commit step.
> > >  	 */
> > >  	struct stack_trace	trace;
> > > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > > index 5becef5..373466b 100644
> > > --- a/include/linux/sched.h
> > > +++ b/include/linux/sched.h
> > > @@ -855,6 +855,9 @@ struct task_struct {
> > >  	unsigned int xhlock_idx;
> > >  	/* For restoring at history boundaries */
> > >  	unsigned int xhlock_idx_hist[CONTEXT_NR];
> > > +	unsigned int hist_id;
> > > +	/* For overwrite check at each context exit */
> > > +	unsigned int hist_id_save[CONTEXT_NR];
> > >  #endif
> > >
> > >  #ifdef CONFIG_UBSAN
> > > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > > index afd6e64..5168dac 100644
> > > --- a/kernel/locking/lockdep.c
> > > +++ b/kernel/locking/lockdep.c
> > > @@ -4742,6 +4742,17 @@ void lockdep_rcu_suspicious(const char *file,
> > const int line, const char *s)
> > >  static atomic_t cross_gen_id; /* Can be wrapped */
> > >
> > >  /*
> > > + * Make an entry of the ring buffer invalid.
> > > + */
> > > +static inline void invalidate_xhlock(struct hist_lock *xhlock)
> > > +{
> > > +	/*
> > > +	 * Normally, xhlock->hlock.instance must be !NULL.
> > > +	 */
> > > +	xhlock->hlock.instance = NULL;
> > > +}
> > > +
> > > +/*
> > >   * Lock history stacks; we have 3 nested lock history stacks:
> > >   *
> > >   *   Hard IRQ
> > > @@ -4773,14 +4784,28 @@ void lockdep_rcu_suspicious(const char *file,
> > const int line, const char *s)
> > >   */
> > >  void crossrelease_hist_start(enum context_t c)
> > >  {
> > > -	if (current->xhlocks)
> > > -		current->xhlock_idx_hist[c] = current->xhlock_idx;
> > > +	struct task_struct *cur = current;
> > > +
> > > +	if (cur->xhlocks) {
> > > +		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> > > +		cur->hist_id_save[c] = cur->hist_id;
> > > +	}
> > >  }
> > >
> > >  void crossrelease_hist_end(enum context_t c)
> > >  {
> > > -	if (current->xhlocks)
> > > -		current->xhlock_idx = current->xhlock_idx_hist[c];
> > > +	struct task_struct *cur = current;
> > > +
> > > +	if (cur->xhlocks) {
> > > +		unsigned int idx = cur->xhlock_idx_hist[c];
> > > +		struct hist_lock *h = &xhlock(idx);
> > > +
> > > +		cur->xhlock_idx = idx;
> > > +
> > > +		/* Check if the ring was overwritten. */
> > > +		if (h->hist_id != cur->hist_id_save[c])
> > 
> > Could we use:
> > 
> > 		if (h->hist_id != idx)
> 
> No, we cannot.
> 

Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
are increased at the same place(in add_xhlock()), right?

And, yes, xhlock_idx will get decreased when we do ring-buffer
unwinding, but that's OK, because we need to throw away those recently
added items.

And xhlock_idx always points to the most recently added valid item,
right?  Any other item's idx must "before()" the most recently added
one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?

Maybe I'm missing something subtle, but could you show me an example,
that could end up being a problem if we use xhlock_idx as the hist_id?

> hist_id is a kind of timestamp and used to detect overwriting
> data into places of same indexes of the ring buffer. And idx is
> just an index. :) IOW, they mean different things.
> 
> > 
> > here, and
> > 
> > > +			invalidate_xhlock(h);
> > > +	}
> > >  }
> > >
> > >  static int cross_lock(struct lockdep_map *lock)
> > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > *hlock)
> > >   * Check if the xhlock is valid, which would be false if,
> > >   *
> > >   *    1. Has not used after initializaion yet.
> > > + *    2. Got invalidated.
> > >   *
> > >   * Remind hist_lock is implemented as a ring buffer.
> > >   */
> > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > >
> > >  	/* Initialize hist_lock's members */
> > >  	xhlock->hlock = *hlock;
> > > +	xhlock->hist_id = current->hist_id++;

Besides, is this code correct? Does this just make xhlock->hist_id
one-less-than the curr->hist_id, which cause the invalidation every time
you do ring buffer unwinding?

Regards,
Boqun

> > 
> > use:
> > 
> > 	xhlock->hist_id = idx;
> > 
> > and,
> 
> Same.
> 
> > 
> > 
> > >
> > >  	xhlock->trace.nr_entries = 0;
> > >  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > > @@ -4995,6 +5022,7 @@ static int commit_xhlock(struct cross_lock *xlock,
> > struct hist_lock *xhlock)
> > >  static void commit_xhlocks(struct cross_lock *xlock)
> > >  {
> > >  	unsigned int cur = current->xhlock_idx;
> > > +	unsigned int prev_hist_id = xhlock(cur).hist_id;
> > 
> > use:
> > 	unsigned int prev_hist_id = cur;
> > 
> > here.
> 
> Same.
> 
> 

[toc] | [prev] | [next] | [standalone]

#1708623 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
[...]
> > > > +		/* Check if the ring was overwritten. */
> > > > +		if (h->hist_id != cur->hist_id_save[c])
> > > 
> > > Could we use:
> > > 
> > > 		if (h->hist_id != idx)
> > 
> > No, we cannot.
> > 
> 
> Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> are increased at the same place(in add_xhlock()), right?
> 
> And, yes, xhlock_idx will get decreased when we do ring-buffer
> unwinding, but that's OK, because we need to throw away those recently
> added items.
> 
> And xhlock_idx always points to the most recently added valid item,
> right?  Any other item's idx must "before()" the most recently added
> one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?
> 
> Maybe I'm missing something subtle, but could you show me an example,
> that could end up being a problem if we use xhlock_idx as the hist_id?
> 
> > hist_id is a kind of timestamp and used to detect overwriting
> > data into places of same indexes of the ring buffer. And idx is
> > just an index. :) IOW, they mean different things.
> > 
> > > 
> > > here, and
> > > 
> > > > +			invalidate_xhlock(h);
> > > > +	}
> > > >  }
> > > >
> > > >  static int cross_lock(struct lockdep_map *lock)
> > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > *hlock)
> > > >   * Check if the xhlock is valid, which would be false if,
> > > >   *
> > > >   *    1. Has not used after initializaion yet.
> > > > + *    2. Got invalidated.
> > > >   *
> > > >   * Remind hist_lock is implemented as a ring buffer.
> > > >   */
> > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > >
> > > >  	/* Initialize hist_lock's members */
> > > >  	xhlock->hlock = *hlock;
> > > > +	xhlock->hist_id = current->hist_id++;
> 
> Besides, is this code correct? Does this just make xhlock->hist_id
> one-less-than the curr->hist_id, which cause the invalidation every time
> you do ring buffer unwinding?
> 
> Regards,
> Boqun
> 

So basically, I'm suggesting do this on top of your patch, there is also
a fix in commit_xhlocks(), which I think you should swap the parameters
in before(...), no matter using task_struct::hist_id or using
task_struct::xhlock_idx as the timestamp.

Hope this could make my point more clear, and if I do miss something,
please point it out, thanks ;-)

Regards,
Boqun
------------>8

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 074872f016f8..886ba79bfc38 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -854,9 +854,6 @@ struct task_struct {
 	unsigned int xhlock_idx;
 	/* For restoring at history boundaries */
 	unsigned int xhlock_idx_hist[XHLOCK_NR];
-	unsigned int hist_id;
-	/* For overwrite check at each context exit */
-	unsigned int hist_id_save[XHLOCK_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 699fbeab1920..04c6c8d68e18 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
 {
 	struct task_struct *cur = current;
 
-	if (cur->xhlocks) {
+	if (cur->xhlocks)
 		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
-		cur->hist_id_save[c] = cur->hist_id;
-	}
 }
 
 void crossrelease_hist_end(enum xhlock_context_t c)
@@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
 		cur->xhlock_idx = idx;
 
 		/* Check if the ring was overwritten. */
-		if (h->hist_id != cur->hist_id_save[c])
+		if (h->hist_id != idx)
 			invalidate_xhlock(h);
 	}
 }
@@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
 
 	/* Initialize hist_lock's members */
 	xhlock->hlock = *hlock;
-	xhlock->hist_id = current->hist_id++;
+	xhlock->hist_id = idx;
 
 	xhlock->trace.nr_entries = 0;
 	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
 	unsigned int cur = current->xhlock_idx;
-	unsigned int prev_hist_id = xhlock(cur).hist_id;
+	unsigned int prev_hist_id = cur + 1;
 	unsigned int i;
 
 	if (!graph_lock())
@@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
 			 * hist_id than the following one, which is impossible
 			 * otherwise.
 			 */
-			if (unlikely(before(xhlock->hist_id, prev_hist_id)))
+			if (unlikely(before(prev_hist_id, xhlock->hist_id)))
 				break;
 
 			prev_hist_id = xhlock->hist_id;
@@ -5120,12 +5118,9 @@ void lockdep_init_task(struct task_struct *task)
 	int i;
 
 	task->xhlock_idx = UINT_MAX;
-	task->hist_id = 0;
 
-	for (i = 0; i < XHLOCK_NR; i++) {
+	for (i = 0; i < XHLOCK_NR; i++)
 		task->xhlock_idx_hist[i] = UINT_MAX;
-		task->hist_id_save[i] = 0;
-	}
 
 	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
 				GFP_KERNEL);

[toc] | [prev] | [next] | [standalone]

#1709141 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> So basically, I'm suggesting do this on top of your patch, there is also
> a fix in commit_xhlocks(), which I think you should swap the parameters
> in before(...), no matter using task_struct::hist_id or using
> task_struct::xhlock_idx as the timestamp.
> 
> Hope this could make my point more clear, and if I do miss something,
> please point it out, thanks ;-)

I think I fully explained why we cannot use xhlock_idx as the timestamp
in another reply. Please let me know if it's not enough. :)

Thank you,
Byungchul

> Regards,
> Boqun
> ------------>8
> 
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 074872f016f8..886ba79bfc38 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -854,9 +854,6 @@ struct task_struct {
>  	unsigned int xhlock_idx;
>  	/* For restoring at history boundaries */
>  	unsigned int xhlock_idx_hist[XHLOCK_NR];
> -	unsigned int hist_id;
> -	/* For overwrite check at each context exit */
> -	unsigned int hist_id_save[XHLOCK_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 699fbeab1920..04c6c8d68e18 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
>  {
>  	struct task_struct *cur = current;
>  
> -	if (cur->xhlocks) {
> +	if (cur->xhlocks)
>  		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> -		cur->hist_id_save[c] = cur->hist_id;
> -	}
>  }
>  
>  void crossrelease_hist_end(enum xhlock_context_t c)
> @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
>  		cur->xhlock_idx = idx;
>  
>  		/* Check if the ring was overwritten. */
> -		if (h->hist_id != cur->hist_id_save[c])
> +		if (h->hist_id != idx)
>  			invalidate_xhlock(h);
>  	}
>  }
> @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>  	/* Initialize hist_lock's members */
>  	xhlock->hlock = *hlock;
> -	xhlock->hist_id = current->hist_id++;
> +	xhlock->hist_id = idx;
>  
>  	xhlock->trace.nr_entries = 0;
>  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>  	unsigned int cur = current->xhlock_idx;
> -	unsigned int prev_hist_id = xhlock(cur).hist_id;
> +	unsigned int prev_hist_id = cur + 1;
>  	unsigned int i;
>  
>  	if (!graph_lock())
> @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>  			 * hist_id than the following one, which is impossible
>  			 * otherwise.
>  			 */
> -			if (unlikely(before(xhlock->hist_id, prev_hist_id)))
> +			if (unlikely(before(prev_hist_id, xhlock->hist_id)))
>  				break;
>  
>  			prev_hist_id = xhlock->hist_id;
> @@ -5120,12 +5118,9 @@ void lockdep_init_task(struct task_struct *task)
>  	int i;
>  
>  	task->xhlock_idx = UINT_MAX;
> -	task->hist_id = 0;
>  
> -	for (i = 0; i < XHLOCK_NR; i++) {
> +	for (i = 0; i < XHLOCK_NR; i++)
>  		task->xhlock_idx_hist[i] = UINT_MAX;
> -		task->hist_id_save[i] = 0;
> -	}
>  
>  	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
>  				GFP_KERNEL);

[toc] | [prev] | [next] | [standalone]

#1709220 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > *hlock)
> > > > >   * Check if the xhlock is valid, which would be false if,
> > > > >   *
> > > > >   *    1. Has not used after initializaion yet.
> > > > > + *    2. Got invalidated.
> > > > >   *
> > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > >   */
> > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > >
> > > > >  	/* Initialize hist_lock's members */
> > > > >  	xhlock->hlock = *hlock;
> > > > > +	xhlock->hist_id = current->hist_id++;
> > 
> > Besides, is this code correct? Does this just make xhlock->hist_id
> > one-less-than the curr->hist_id, which cause the invalidation every time
> > you do ring buffer unwinding?
> > 
> > Regards,
> > Boqun
> > 
> 
> So basically, I'm suggesting do this on top of your patch, there is also
> a fix in commit_xhlocks(), which I think you should swap the parameters
> in before(...), no matter using task_struct::hist_id or using
> task_struct::xhlock_idx as the timestamp.
> 
> Hope this could make my point more clear, and if I do miss something,
> please point it out, thanks ;-)

Sorry for mis-understanding. I like your patch. I think it works.

Additionally.. See below..

> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 074872f016f8..886ba79bfc38 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -854,9 +854,6 @@ struct task_struct {
>  	unsigned int xhlock_idx;
>  	/* For restoring at history boundaries */
>  	unsigned int xhlock_idx_hist[XHLOCK_NR];
> -	unsigned int hist_id;
> -	/* For overwrite check at each context exit */
> -	unsigned int hist_id_save[XHLOCK_NR];
>  #endif
>  
>  #ifdef CONFIG_UBSAN
> diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> index 699fbeab1920..04c6c8d68e18 100644
> --- a/kernel/locking/lockdep.c
> +++ b/kernel/locking/lockdep.c
> @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
>  {
>  	struct task_struct *cur = current;
>  
> -	if (cur->xhlocks) {
> +	if (cur->xhlocks)
>  		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> -		cur->hist_id_save[c] = cur->hist_id;
> -	}
>  }
>  
>  void crossrelease_hist_end(enum xhlock_context_t c)
> @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
>  		cur->xhlock_idx = idx;
>  
>  		/* Check if the ring was overwritten. */
> -		if (h->hist_id != cur->hist_id_save[c])
> +		if (h->hist_id != idx)
>  			invalidate_xhlock(h);
>  	}
>  }
> @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
>  
>  	/* Initialize hist_lock's members */
>  	xhlock->hlock = *hlock;
> -	xhlock->hist_id = current->hist_id++;
> +	xhlock->hist_id = idx;
>  
>  	xhlock->trace.nr_entries = 0;
>  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
>  static void commit_xhlocks(struct cross_lock *xlock)
>  {
>  	unsigned int cur = current->xhlock_idx;
> -	unsigned int prev_hist_id = xhlock(cur).hist_id;
> +	unsigned int prev_hist_id = cur + 1;

I should have named it another. Could you suggest a better one?

>  	unsigned int i;
>  
>  	if (!graph_lock())
> @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>  			 * hist_id than the following one, which is impossible
>  			 * otherwise.

Or we need to modify the comment so that the word 'prev' does not make
readers confused. It was my mistake.

Thanks,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1709354 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Multipart message — attachments visible in raw view] — view raw

On Fri, Aug 11, 2017 at 12:43:28PM +0900, Byungchul Park wrote:
> On Thu, Aug 10, 2017 at 09:17:37PM +0800, Boqun Feng wrote:
> > > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > > *hlock)
> > > > > >   * Check if the xhlock is valid, which would be false if,
> > > > > >   *
> > > > > >   *    1. Has not used after initializaion yet.
> > > > > > + *    2. Got invalidated.
> > > > > >   *
> > > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > > >   */
> > > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > > >
> > > > > >  	/* Initialize hist_lock's members */
> > > > > >  	xhlock->hlock = *hlock;
> > > > > > +	xhlock->hist_id = current->hist_id++;
> > > 
> > > Besides, is this code correct? Does this just make xhlock->hist_id
> > > one-less-than the curr->hist_id, which cause the invalidation every time
> > > you do ring buffer unwinding?
> > > 
> > > Regards,
> > > Boqun
> > > 
> > 
> > So basically, I'm suggesting do this on top of your patch, there is also
> > a fix in commit_xhlocks(), which I think you should swap the parameters
> > in before(...), no matter using task_struct::hist_id or using
> > task_struct::xhlock_idx as the timestamp.
> > 
> > Hope this could make my point more clear, and if I do miss something,
> > please point it out, thanks ;-)
> 
> Sorry for mis-understanding. I like your patch. I think it works.
> 

Thanks for taking a look at it ;-)

> Additionally.. See below..
> 
> > diff --git a/include/linux/sched.h b/include/linux/sched.h
> > index 074872f016f8..886ba79bfc38 100644
> > --- a/include/linux/sched.h
> > +++ b/include/linux/sched.h
> > @@ -854,9 +854,6 @@ struct task_struct {
> >  	unsigned int xhlock_idx;
> >  	/* For restoring at history boundaries */
> >  	unsigned int xhlock_idx_hist[XHLOCK_NR];
> > -	unsigned int hist_id;
> > -	/* For overwrite check at each context exit */
> > -	unsigned int hist_id_save[XHLOCK_NR];
> >  #endif
> >  
> >  #ifdef CONFIG_UBSAN
> > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
> > index 699fbeab1920..04c6c8d68e18 100644
> > --- a/kernel/locking/lockdep.c
> > +++ b/kernel/locking/lockdep.c
> > @@ -4752,10 +4752,8 @@ void crossrelease_hist_start(enum xhlock_context_t c)
> >  {
> >  	struct task_struct *cur = current;
> >  
> > -	if (cur->xhlocks) {
> > +	if (cur->xhlocks)
> >  		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
> > -		cur->hist_id_save[c] = cur->hist_id;
> > -	}
> >  }
> >  
> >  void crossrelease_hist_end(enum xhlock_context_t c)
> > @@ -4769,7 +4767,7 @@ void crossrelease_hist_end(enum xhlock_context_t c)
> >  		cur->xhlock_idx = idx;
> >  
> >  		/* Check if the ring was overwritten. */
> > -		if (h->hist_id != cur->hist_id_save[c])
> > +		if (h->hist_id != idx)
> >  			invalidate_xhlock(h);
> >  	}
> >  }
> > @@ -4849,7 +4847,7 @@ static void add_xhlock(struct held_lock *hlock)
> >  
> >  	/* Initialize hist_lock's members */
> >  	xhlock->hlock = *hlock;
> > -	xhlock->hist_id = current->hist_id++;
> > +	xhlock->hist_id = idx;
> >  
> >  	xhlock->trace.nr_entries = 0;
> >  	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
> > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
> >  static void commit_xhlocks(struct cross_lock *xlock)
> >  {
> >  	unsigned int cur = current->xhlock_idx;
> > -	unsigned int prev_hist_id = xhlock(cur).hist_id;
> > +	unsigned int prev_hist_id = cur + 1;
> 
> I should have named it another. Could you suggest a better one?
> 

I think "prev" is fine, because I thought the "previous" means the
xhlock item we visit _previously_.

> >  	unsigned int i;
> >  
> >  	if (!graph_lock())
> > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> >  			 * hist_id than the following one, which is impossible
> >  			 * otherwise.
> 
> Or we need to modify the comment so that the word 'prev' does not make
> readers confused. It was my mistake.
> 

I think the comment needs some help, but before you do it, could you
have another look at what Peter proposed previously? Note you have a
same_context_xhlock() check in the commit_xhlocks(), so the your
previous overwrite case actually could be detected, I think.

However, one thing may not be detected is this case:

		ppppppppppppppppppppppppppppppppppwwwwwwww
wrapped >	wwwwwww

	where p: process and w: worker.

, because p and w are in the same task_irq_context(). I discussed this
with Peter yesterday, and he has a good idea: unconditionally do a reset
on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
Basically it means we empty the lock history whenever we finished a
worker function in a worker thread or we are about to return to
userspace after we finish the syscall. This could further save some
memory and so I think this may be better than my approach.

How does this sound to you?

Regards,
Boqun

> Thanks,
> Byungchul
> 

[toc] | [prev] | [next] | [standalone]

#1709383 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> Thanks for taking a look at it ;-)

I rather appriciate it.

> > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
> > >  static void commit_xhlocks(struct cross_lock *xlock)
> > >  {
> > >  	unsigned int cur = current->xhlock_idx;
> > > -	unsigned int prev_hist_id = xhlock(cur).hist_id;
> > > +	unsigned int prev_hist_id = cur + 1;
> > 
> > I should have named it another. Could you suggest a better one?
> > 
> 
> I think "prev" is fine, because I thought the "previous" means the
> xhlock item we visit _previously_.
> 
> > >  	unsigned int i;
> > >  
> > >  	if (!graph_lock())
> > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> > >  			 * hist_id than the following one, which is impossible
> > >  			 * otherwise.
> > 
> > Or we need to modify the comment so that the word 'prev' does not make
> > readers confused. It was my mistake.
> > 
> 
> I think the comment needs some help, but before you do it, could you
> have another look at what Peter proposed previously? Note you have a
> same_context_xhlock() check in the commit_xhlocks(), so the your
> previous overwrite case actually could be detected, I think.

What is the previous overwrite case?

ppppppppppwwwwwwwwwwwwiiiiiiiii
iiiiiiiiiiiiiii................

Do you mean this one? I missed the check of same_context_xhlock(). Yes,
peterz's suggestion also seems to work.

> However, one thing may not be detected is this case:
> 
> 		ppppppppppppppppppppppppppppppppppwwwwwwww
> wrapped >	wwwwwww

To be honest, I think your suggestion is more natual, with which this
case would be also covered.

> 
> 	where p: process and w: worker.
> 
> , because p and w are in the same task_irq_context(). I discussed this
> with Peter yesterday, and he has a good idea: unconditionally do a reset
> on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
> Basically it means we empty the lock history whenever we finished a
> worker function in a worker thread or we are about to return to
> userspace after we finish the syscall. This could further save some
> memory and so I think this may be better than my approach.

Do you mean reset _whenever_ hard irq exit, soft irq exit or work exit?
Why should we give up chances to check dependencies of remaining xhlocks
whenever each exit? Am I understanding correctly?

I am just curious. Does your approach have some problems?

Thanks,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1709418 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
> > Thanks for taking a look at it ;-)
> 
> I rather appriciate it.
> 
> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
> > > >  static void commit_xhlocks(struct cross_lock *xlock)
> > > >  {
> > > >  	unsigned int cur = current->xhlock_idx;
> > > > -	unsigned int prev_hist_id = xhlock(cur).hist_id;
> > > > +	unsigned int prev_hist_id = cur + 1;
> > > 
> > > I should have named it another. Could you suggest a better one?
> > > 
> > 
> > I think "prev" is fine, because I thought the "previous" means the
> > xhlock item we visit _previously_.
> > 
> > > >  	unsigned int i;
> > > >  
> > > >  	if (!graph_lock())
> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
> > > >  			 * hist_id than the following one, which is impossible
> > > >  			 * otherwise.
> > > 
> > > Or we need to modify the comment so that the word 'prev' does not make
> > > readers confused. It was my mistake.
> > > 
> > 
> > I think the comment needs some help, but before you do it, could you
> > have another look at what Peter proposed previously? Note you have a
> > same_context_xhlock() check in the commit_xhlocks(), so the your
> > previous overwrite case actually could be detected, I think.
> 
> What is the previous overwrite case?
> 
> ppppppppppwwwwwwwwwwwwiiiiiiiii
> iiiiiiiiiiiiiii................
> 
> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
> peterz's suggestion also seems to work.
> 
> > However, one thing may not be detected is this case:
> > 
> > 		ppppppppppppppppppppppppppppppppppwwwwwwww
> > wrapped >	wwwwwww
> 
> To be honest, I think your suggestion is more natual, with which this
> case would be also covered.
> 
> > 
> > 	where p: process and w: worker.
> > 
> > , because p and w are in the same task_irq_context(). I discussed this
> > with Peter yesterday, and he has a good idea: unconditionally do a reset
> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).

Ah, ok. You meant 'whenever _process_ context exit'.

I need more time to be sure, but anyway for now it seems to work with
giving up some chances for remaining xhlocks.

But, I am not sure if it's still true even in future and the code can be
maintained easily. I think your approach is natural and neat enough for
that purpose. What problem exists with yours?

> > Basically it means we empty the lock history whenever we finished a
> > worker function in a worker thread or we are about to return to
> > userspace after we finish the syscall. This could further save some
> > memory and so I think this may be better than my approach.
> 
> Do you mean reset _whenever_ hard irq exit, soft irq exit or work exit?
> Why should we give up chances to check dependencies of remaining xhlocks
> whenever each exit? Am I understanding correctly?
> 
> I am just curious. Does your approach have some problems?
> 
> Thanks,
> Byungchul

[toc] | [prev] | [next] | [standalone]

#1709585

On Fri, Aug 11, 2017 at 6:44 PM, Byungchul Park <byungchul.park@lge.com> wrote:
> On Fri, Aug 11, 2017 at 05:52:02PM +0900, Byungchul Park wrote:
>> On Fri, Aug 11, 2017 at 04:03:29PM +0800, Boqun Feng wrote:
>> > Thanks for taking a look at it ;-)
>>
>> I rather appriciate it.
>>
>> > > > @@ -5005,7 +5003,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
>> > > >  static void commit_xhlocks(struct cross_lock *xlock)
>> > > >  {
>> > > >         unsigned int cur = current->xhlock_idx;
>> > > > -       unsigned int prev_hist_id = xhlock(cur).hist_id;
>> > > > +       unsigned int prev_hist_id = cur + 1;
>> > >
>> > > I should have named it another. Could you suggest a better one?
>> > >
>> >
>> > I think "prev" is fine, because I thought the "previous" means the
>> > xhlock item we visit _previously_.
>> >
>> > > >         unsigned int i;
>> > > >
>> > > >         if (!graph_lock())
>> > > > @@ -5030,7 +5028,7 @@ static void commit_xhlocks(struct cross_lock *xlock)
>> > > >                          * hist_id than the following one, which is impossible
>> > > >                          * otherwise.
>> > >
>> > > Or we need to modify the comment so that the word 'prev' does not make
>> > > readers confused. It was my mistake.
>> > >
>> >
>> > I think the comment needs some help, but before you do it, could you
>> > have another look at what Peter proposed previously? Note you have a
>> > same_context_xhlock() check in the commit_xhlocks(), so the your
>> > previous overwrite case actually could be detected, I think.
>>
>> What is the previous overwrite case?
>>
>> ppppppppppwwwwwwwwwwwwiiiiiiiii
>> iiiiiiiiiiiiiii................
>>
>> Do you mean this one? I missed the check of same_context_xhlock(). Yes,
>> peterz's suggestion also seems to work.
>>
>> > However, one thing may not be detected is this case:
>> >
>> >             ppppppppppppppppppppppppppppppppppwwwwwwww
>> > wrapped >   wwwwwww
>>
>> To be honest, I think your suggestion is more natual, with which this
>> case would be also covered.
>>
>> >
>> >     where p: process and w: worker.
>> >
>> > , because p and w are in the same task_irq_context(). I discussed this
>> > with Peter yesterday, and he has a good idea: unconditionally do a reset
>> > on the ring buffer whenever we do a crossrelease_hist_end(XHLOCK_PROC).
>
> Ah, ok. You meant 'whenever _process_ context exit'.
>
> I need more time to be sure, but anyway for now it seems to work with
> giving up some chances for remaining xhlocks.
>
> But, I am not sure if it's still true even in future and the code can be
> maintained easily. I think your approach is natural and neat enough for
> that purpose. What problem exists with yours?

Let me list up the possible approaches:

0. Byungchul's approach
1. Boqun's approach
2. Peterz's approach
3. Reset on process exit

I like Boqun's approach most but, _whatever_. It's ok if it solves the problem.
The last one is not bad when it is used for syscall exit, but we have to give
up valid dependencies unnecessarily in other cases. And I think Peterz's
approach should be modified a bit to make it work neatly, like:

crossrelease_hist_end(...)
{
...
       invalidate_xhlock(&xhlock(cur->xhlock_idx_max));

       for (c = 0; c < XHLOCK_CXT_NR; c++)
              if ((cur->xhlock_idx_max - cur->xhlock_idx_hist[c]) >=
MAX_XHLOCKS_NR)
                     invalidate_xhlock(&xhlock(cur->xhlock_idx_hist[c]));
...
}

And then Peterz's approach can also work, I think.

---
Thanks,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1709142 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
> > > >  void crossrelease_hist_end(enum context_t c)
> > > >  {
> > > > -	if (current->xhlocks)
> > > > -		current->xhlock_idx = current->xhlock_idx_hist[c];
> > > > +	struct task_struct *cur = current;
> > > > +
> > > > +	if (cur->xhlocks) {
> > > > +		unsigned int idx = cur->xhlock_idx_hist[c];
> > > > +		struct hist_lock *h = &xhlock(idx);
> > > > +
> > > > +		cur->xhlock_idx = idx;
> > > > +
> > > > +		/* Check if the ring was overwritten. */
> > > > +		if (h->hist_id != cur->hist_id_save[c])
> > > 
> > > Could we use:
> > > 
> > > 		if (h->hist_id != idx)
> > 
> > No, we cannot.
> > 
> 
> Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> are increased at the same place(in add_xhlock()), right?

Right.

> And, yes, xhlock_idx will get decreased when we do ring-buffer

This is why we should keep both of them.

> unwinding, but that's OK, because we need to throw away those recently
> added items.
> 
> And xhlock_idx always points to the most recently added valid item,

No, it's not true in case that the ring buffer was wrapped like:

          ppppppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiii
wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii................
                                 ^
                     xhlock_idx points here after unwinding,
                     and it's not a valid one.

          where p represents an acquisition in process context,
          i represents an acquisition in irq context.

> right?  Any other item's idx must "before()" the most recently added
> one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?

Both of two answers are _no_.

> Maybe I'm missing something subtle, but could you show me an example,
> that could end up being a problem if we use xhlock_idx as the hist_id?

See the example above. We cannot detect whether it was wrapped or not using
xhlock_idx.

> 
> > hist_id is a kind of timestamp and used to detect overwriting
> > data into places of same indexes of the ring buffer. And idx is
> > just an index. :) IOW, they mean different things.
> > 
> > > 
> > > here, and
> > > 
> > > > +			invalidate_xhlock(h);
> > > > +	}
> > > >  }
> > > >
> > > >  static int cross_lock(struct lockdep_map *lock)
> > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > *hlock)
> > > >   * Check if the xhlock is valid, which would be false if,
> > > >   *
> > > >   *    1. Has not used after initializaion yet.
> > > > + *    2. Got invalidated.
> > > >   *
> > > >   * Remind hist_lock is implemented as a ring buffer.
> > > >   */
> > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > >
> > > >  	/* Initialize hist_lock's members */
> > > >  	xhlock->hlock = *hlock;
> > > > +	xhlock->hist_id = current->hist_id++;
> 
> Besides, is this code correct? Does this just make xhlock->hist_id
> one-less-than the curr->hist_id, which cause the invalidation every time
> you do ring buffer unwinding?

Right. "save = hist_id++" should be "save = ++hist_id". Could you fix it?

Thank you,
Byungchul

[toc] | [prev] | [next] | [standalone]

#1709150 — Re: [PATCH v8 06/14] lockdep: Detect and handle hist_lock ring buffer overwrite

[Multipart message — attachments visible in raw view] — view raw

On Fri, Aug 11, 2017 at 09:40:21AM +0900, Byungchul Park wrote:
> On Thu, Aug 10, 2017 at 08:51:33PM +0800, Boqun Feng wrote:
> > > > >  void crossrelease_hist_end(enum context_t c)
> > > > >  {
> > > > > -	if (current->xhlocks)
> > > > > -		current->xhlock_idx = current->xhlock_idx_hist[c];
> > > > > +	struct task_struct *cur = current;
> > > > > +
> > > > > +	if (cur->xhlocks) {
> > > > > +		unsigned int idx = cur->xhlock_idx_hist[c];
> > > > > +		struct hist_lock *h = &xhlock(idx);
> > > > > +
> > > > > +		cur->xhlock_idx = idx;
> > > > > +
> > > > > +		/* Check if the ring was overwritten. */
> > > > > +		if (h->hist_id != cur->hist_id_save[c])
> > > > 
> > > > Could we use:
> > > > 
> > > > 		if (h->hist_id != idx)
> > > 
> > > No, we cannot.
> > > 
> > 
> > Hey, I'm not buying it. task_struct::hist_id and task_struct::xhlock_idx
> > are increased at the same place(in add_xhlock()), right?
> 
> Right.
> 
> > And, yes, xhlock_idx will get decreased when we do ring-buffer
> 
> This is why we should keep both of them.
> 
> > unwinding, but that's OK, because we need to throw away those recently
> > added items.
> > 
> > And xhlock_idx always points to the most recently added valid item,
> 
> No, it's not true in case that the ring buffer was wrapped like:
> 
>           ppppppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiii
> wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii................
>                                  ^
>                      xhlock_idx points here after unwinding,
>                      and it's not a valid one.
> 
>           where p represents an acquisition in process context,
>           i represents an acquisition in irq context.
> 

Yeah, but we can detect this with comparison between the
hist_lock::hist_id and the task_struct::xhlock_idx in
commit_xhlocks()(see my patch), no?

Regards,
Boqun

> > right?  Any other item's idx must "before()" the most recently added
> > one's, right? So ::xhlock_idx acts just like a timestamp, doesn't it?
> 
> Both of two answers are _no_.
> 
> > Maybe I'm missing something subtle, but could you show me an example,
> > that could end up being a problem if we use xhlock_idx as the hist_id?
> 
> See the example above. We cannot detect whether it was wrapped or not using
> xhlock_idx.
> 
> > 
> > > hist_id is a kind of timestamp and used to detect overwriting
> > > data into places of same indexes of the ring buffer. And idx is
> > > just an index. :) IOW, they mean different things.
> > > 
> > > > 
> > > > here, and
> > > > 
> > > > > +			invalidate_xhlock(h);
> > > > > +	}
> > > > >  }
> > > > >
> > > > >  static int cross_lock(struct lockdep_map *lock)
> > > > > @@ -4826,6 +4851,7 @@ static inline int depend_after(struct held_lock
> > > > *hlock)
> > > > >   * Check if the xhlock is valid, which would be false if,
> > > > >   *
> > > > >   *    1. Has not used after initializaion yet.
> > > > > + *    2. Got invalidated.
> > > > >   *
> > > > >   * Remind hist_lock is implemented as a ring buffer.
> > > > >   */
> > > > > @@ -4857,6 +4883,7 @@ static void add_xhlock(struct held_lock *hlock)
> > > > >
> > > > >  	/* Initialize hist_lock's members */
> > > > >  	xhlock->hlock = *hlock;
> > > > > +	xhlock->hist_id = current->hist_id++;
> > 
> > Besides, is this code correct? Does this just make xhlock->hist_id
> > one-less-than the curr->hist_id, which cause the invalidation every time
> > you do ring buffer unwinding?
> 
> Right. "save = hist_id++" should be "save = ++hist_id". Could you fix it?
> 
> Thank you,
> Byungchul
> 

[toc] | [prev] | [next] | [standalone]

#1708555 — [tip:locking/core] locking/lockdep: Detect and handle hist_lock ring buffer overwrite

Commit-ID:  23f873d8f9526ed7e49a1a02a45f8afb9ae5fb84
Gitweb:     http://git.kernel.org/tip/23f873d8f9526ed7e49a1a02a45f8afb9ae5fb84
Author:     Byungchul Park <byungchul.park@lge.com>
AuthorDate: Mon, 7 Aug 2017 16:12:53 +0900
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Thu, 10 Aug 2017 12:29:08 +0200

locking/lockdep: Detect and handle hist_lock ring buffer overwrite

The ring buffer can be overwritten by hardirq/softirq/work contexts.
That cases must be considered on rollback or commit. For example,

          |<------ hist_lock ring buffer size ----->|
          ppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii
wrapped > iiiiiiiiiiiiiiiiiiiiiii....................

          where 'p' represents an acquisition in process context,
          'i' represents an acquisition in irq context.

On irq exit, crossrelease tries to rollback idx to original position,
but it should not because the entry already has been invalid by
overwriting 'i'. Avoid rollback or commit for entries overwritten.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: akpm@linux-foundation.org
Cc: boqun.feng@gmail.com
Cc: kernel-team@lge.com
Cc: kirill@shutemov.name
Cc: npiggin@gmail.com
Cc: walken@google.com
Cc: willy@infradead.org
Link: http://lkml.kernel.org/r/1502089981-21272-7-git-send-email-byungchul.park@lge.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 include/linux/lockdep.h  | 20 +++++++++++++++++++
 include/linux/sched.h    |  3 +++
 kernel/locking/lockdep.c | 52 +++++++++++++++++++++++++++++++++++++++++++-----
 3 files changed, 70 insertions(+), 5 deletions(-)

diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
index e1e0fcd..c75eedd 100644
--- a/include/linux/lockdep.h
+++ b/include/linux/lockdep.h
@@ -284,6 +284,26 @@ struct held_lock {
  */
 struct hist_lock {
 	/*
+	 * Id for each entry in the ring buffer. This is used to
+	 * decide whether the ring buffer was overwritten or not.
+	 *
+	 * For example,
+	 *
+	 *           |<----------- hist_lock ring buffer size ------->|
+	 *           pppppppppppppppppppppiiiiiiiiiiiiiiiiiiiiiiiiiiiii
+	 * wrapped > iiiiiiiiiiiiiiiiiiiiiiiiiii.......................
+	 *
+	 *           where 'p' represents an acquisition in process
+	 *           context, 'i' represents an acquisition in irq
+	 *           context.
+	 *
+	 * In this example, the ring buffer was overwritten by
+	 * acquisitions in irq context, that should be detected on
+	 * rollback or commit.
+	 */
+	unsigned int hist_id;
+
+	/*
 	 * Seperate stack_trace data. This will be used at commit step.
 	 */
 	struct stack_trace	trace;
diff --git a/include/linux/sched.h b/include/linux/sched.h
index 5235fba..772c5f6 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -854,6 +854,9 @@ struct task_struct {
 	unsigned int xhlock_idx;
 	/* For restoring at history boundaries */
 	unsigned int xhlock_idx_hist[XHLOCK_CTX_NR];
+	unsigned int hist_id;
+	/* For overwrite check at each context exit */
+	unsigned int hist_id_save[XHLOCK_CTX_NR];
 #endif
 
 #ifdef CONFIG_UBSAN
diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
index 56f69cc..eda8114 100644
--- a/kernel/locking/lockdep.c
+++ b/kernel/locking/lockdep.c
@@ -4681,6 +4681,17 @@ EXPORT_SYMBOL_GPL(lockdep_rcu_suspicious);
 static atomic_t cross_gen_id; /* Can be wrapped */
 
 /*
+ * Make an entry of the ring buffer invalid.
+ */
+static inline void invalidate_xhlock(struct hist_lock *xhlock)
+{
+	/*
+	 * Normally, xhlock->hlock.instance must be !NULL.
+	 */
+	xhlock->hlock.instance = NULL;
+}
+
+/*
  * Lock history stacks; we have 3 nested lock history stacks:
  *
  *   Hard IRQ
@@ -4712,14 +4723,28 @@ static atomic_t cross_gen_id; /* Can be wrapped */
  */
 void crossrelease_hist_start(enum xhlock_context_t c)
 {
-	if (current->xhlocks)
-		current->xhlock_idx_hist[c] = current->xhlock_idx;
+	struct task_struct *cur = current;
+
+	if (cur->xhlocks) {
+		cur->xhlock_idx_hist[c] = cur->xhlock_idx;
+		cur->hist_id_save[c] = cur->hist_id;
+	}
 }
 
 void crossrelease_hist_end(enum xhlock_context_t c)
 {
-	if (current->xhlocks)
-		current->xhlock_idx = current->xhlock_idx_hist[c];
+	struct task_struct *cur = current;
+
+	if (cur->xhlocks) {
+		unsigned int idx = cur->xhlock_idx_hist[c];
+		struct hist_lock *h = &xhlock(idx);
+
+		cur->xhlock_idx = idx;
+
+		/* Check if the ring was overwritten. */
+		if (h->hist_id != cur->hist_id_save[c])
+			invalidate_xhlock(h);
+	}
 }
 
 static int cross_lock(struct lockdep_map *lock)
@@ -4765,6 +4790,7 @@ static inline int depend_after(struct held_lock *hlock)
  * Check if the xhlock is valid, which would be false if,
  *
  *    1. Has not used after initializaion yet.
+ *    2. Got invalidated.
  *
  * Remind hist_lock is implemented as a ring buffer.
  */
@@ -4796,6 +4822,7 @@ static void add_xhlock(struct held_lock *hlock)
 
 	/* Initialize hist_lock's members */
 	xhlock->hlock = *hlock;
+	xhlock->hist_id = current->hist_id++;
 
 	xhlock->trace.nr_entries = 0;
 	xhlock->trace.max_entries = MAX_XHLOCK_TRACE_ENTRIES;
@@ -4934,6 +4961,7 @@ static int commit_xhlock(struct cross_lock *xlock, struct hist_lock *xhlock)
 static void commit_xhlocks(struct cross_lock *xlock)
 {
 	unsigned int cur = current->xhlock_idx;
+	unsigned int prev_hist_id = xhlock(cur).hist_id;
 	unsigned int i;
 
 	if (!graph_lock())
@@ -4952,6 +4980,17 @@ static void commit_xhlocks(struct cross_lock *xlock)
 			break;
 
 		/*
+		 * Filter out the cases that the ring buffer was
+		 * overwritten and the previous entry has a bigger
+		 * hist_id than the following one, which is impossible
+		 * otherwise.
+		 */
+		if (unlikely(before(xhlock->hist_id, prev_hist_id)))
+			break;
+
+		prev_hist_id = xhlock->hist_id;
+
+		/*
 		 * commit_xhlock() returns 0 with graph_lock already
 		 * released if fail.
 		 */
@@ -5024,9 +5063,12 @@ void lockdep_init_task(struct task_struct *task)
 	int i;
 
 	task->xhlock_idx = UINT_MAX;
+	task->hist_id = 0;
 
-	for (i = 0; i < XHLOCK_CTX_NR; i++)
+	for (i = 0; i < XHLOCK_CTX_NR; i++) {
 		task->xhlock_idx_hist[i] = UINT_MAX;
+		task->hist_id_save[i] = 0;
+	}
 
 	task->xhlocks = kzalloc(sizeof(struct hist_lock) * MAX_XHLOCKS_NR,
 				GFP_KERNEL);

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web