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

Groups > linux.kernel > #1455855 > unrolled thread

[PATCH 10/10] fault injection: inject faults in new/rare callchains

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 10/10] fault injection: inject faults in new/rare callchains Vegard Nossum <vegard.nossum@oracle.com> - 2016-08-03 17:20 +0200
    Re: [PATCH 10/10] fault injection: inject faults in new/rare callchains Akinobu Mita <akinobu.mita@gmail.com> - 2016-08-08 16:00 +0200
      Re: [PATCH 10/10] fault injection: inject faults in new/rare  callchains Vegard Nossum <vegard.nossum@oracle.com> - 2016-08-08 16:10 +0200
        Re: [PATCH 10/10] fault injection: inject faults in new/rare callchains Akinobu Mita <akinobu.mita@gmail.com> - 2016-08-08 18:30 +0200

#1455855 — [PATCH 10/10] fault injection: inject faults in new/rare callchains

Before this patch, fault injection uses a combination of randomness and
frequency to determine where to inject faults. The problem with this is
that code paths which are executed very rarely get proportional amounts
of faults injected.

A better heuristic is to look at the actual callchain leading up to the
possible failure point; if we see a callchain that we've never seen up
until this point, chances are it's a rare one and we should definitely
inject a fault here (since we might not get the chance again later).

This uses a probabilistic set structure (similar to a bloom filter) to
determine whether we have seen a particular callchain before by hashing
the stack trace and atomically testing/setting a bit corresponding to
the current callchain.

There is a possibility of false negatives (i.e. we think we have seen a
particular callchain before when in fact we haven't, therefore we don't
inject a fault where we should have). We might use some sort of random
seed here, but the additional complexity doesn't seem worth it to me.

This finds a lot more bugs than just plain fault injection.

Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
---
 lib/Kconfig.debug  | 29 +++++++++++++++++++++++++++++
 lib/fault-inject.c | 36 +++++++++++++++++++++++++++++++-----
 2 files changed, 60 insertions(+), 5 deletions(-)

diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 52f7e14..9e81720 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -1701,6 +1701,35 @@ config FAULT_INJECTION_STACKTRACE_FILTER
 	help
 	  Provide stacktrace filter for fault-injection capabilities
 
+config FAULT_INJECTION_AT_NEW_CALLSITES
+	bool "Inject fault the first time at a new callsite"
+	depends on FAULT_INJECTION_STACKTRACE_FILTER
+	help
+	  Without this, fault injection uses a combination of randomness
+	  and frequency to determine where to inject faults. The problem
+	  with this is that code paths which are executed very rarely get
+	  proportional amounts of faults injected.
+
+	  A better heuristic is to look at the actual callchain leading
+	  up to the possible failure point; if we see a callchain that
+	  we've never seen up until this point, chances are it's a rare
+	  one and we should definitely inject a fault here (since we
+	  might not get the chance again later).
+
+	  This uses a probabilistic set structure (similar to a bloom
+	  filter) to determine whether we have seen a particular
+	  callchain before by hashing the stack trace and atomically
+	  testing/setting a bit corresponding to the current callchain.
+
+	  There is a possibility of false negatives (i.e. we think we
+	  have seen a particular callchain before when in fact we
+	  haven't, therefore we don't inject a fault where we should
+	  have). We might use some sort of random seed here, but the
+	  additional complexity doesn't seem worth it to me.
+
+	  This finds a lot more bugs than just plain fault injection,
+	  but comes with a small additional overhead.
+
 config LATENCYTOP
 	bool "Latency measuring infrastructure"
 	depends on DEBUG_KERNEL
diff --git a/lib/fault-inject.c b/lib/fault-inject.c
index adba7c9..5ad11dd 100644
--- a/lib/fault-inject.c
+++ b/lib/fault-inject.c
@@ -63,7 +63,7 @@ static bool fail_task(struct fault_attr *attr, struct task_struct *task)
 
 #ifdef CONFIG_FAULT_INJECTION_STACKTRACE_FILTER
 
-static bool fail_stacktrace(struct fault_attr *attr)
+static bool fail_stacktrace(struct fault_attr *attr, unsigned int *hash)
 {
 	struct stack_trace trace;
 	int depth = attr->stacktrace_depth;
@@ -88,12 +88,20 @@ static bool fail_stacktrace(struct fault_attr *attr)
 			       entries[n] < attr->require_end)
 			found = true;
 	}
+
+	if (IS_ENABLED(CONFIG_FAULT_INJECTION_AT_NEW_CALLSITES)) {
+		const char *start = (const char *) &entries[0];
+		const char *end = (const char *) &entries[trace.nr_entries];
+
+		*hash = full_name_hash(0, start, end - start);
+	}
+
 	return found;
 }
 
 #else
 
-static inline bool fail_stacktrace(struct fault_attr *attr)
+static inline bool fail_stacktrace(struct fault_attr *attr, unsigned int *hash)
 {
 	return true;
 }
@@ -134,6 +142,8 @@ out:
 
 bool should_fail(struct fault_attr *attr, ssize_t size)
 {
+	unsigned int hash = 0;
+
 	/* No need to check any other properties if the probability is 0 */
 	if (attr->probability == 0)
 		return false;
@@ -149,6 +159,24 @@ bool should_fail(struct fault_attr *attr, ssize_t size)
 		return false;
 	}
 
+	if (!fail_stacktrace(attr, &hash))
+		return false;
+
+	if (IS_ENABLED(CONFIG_FAULT_INJECTION_AT_NEW_CALLSITES)) {
+		static unsigned long seen_hashtable[4 * 1024];
+
+		hash &= 8 * sizeof(seen_hashtable) - 1;
+		if (!test_and_set_bit(hash & (BITS_PER_LONG - 1),
+			&seen_hashtable[hash / BITS_PER_LONG]))
+		{
+			/*
+			 * If it's the first time we see this stacktrace, fail it
+			 * without a second thought.
+			 */
+			goto fail;
+		}
+	}
+
 	if (attr->interval > 1) {
 		attr->count++;
 		if (attr->count % attr->interval)
@@ -158,9 +186,7 @@ bool should_fail(struct fault_attr *attr, ssize_t size)
 	if (attr->probability <= prandom_u32() % 100)
 		return false;
 
-	if (!fail_stacktrace(attr))
-		return false;
-
+fail:
 	return __fail(attr);
 }
 EXPORT_SYMBOL_GPL(should_fail);
-- 
1.9.1

[toc] | [next] | [standalone]

#1457817

2016-08-04 0:05 GMT+09:00 Vegard Nossum <vegard.nossum@oracle.com>:
> Before this patch, fault injection uses a combination of randomness and
> frequency to determine where to inject faults. The problem with this is
> that code paths which are executed very rarely get proportional amounts
> of faults injected.
>
> A better heuristic is to look at the actual callchain leading up to the
> possible failure point; if we see a callchain that we've never seen up
> until this point, chances are it's a rare one and we should definitely
> inject a fault here (since we might not get the chance again later).
>
> This uses a probabilistic set structure (similar to a bloom filter) to
> determine whether we have seen a particular callchain before by hashing
> the stack trace and atomically testing/setting a bit corresponding to
> the current callchain.
>
> There is a possibility of false negatives (i.e. we think we have seen a
> particular callchain before when in fact we haven't, therefore we don't
> inject a fault where we should have). We might use some sort of random
> seed here, but the additional complexity doesn't seem worth it to me.
>
> This finds a lot more bugs than just plain fault injection.
>
> Signed-off-by: Vegard Nossum <vegard.nossum@oracle.com>
> ---
>  lib/Kconfig.debug  | 29 +++++++++++++++++++++++++++++
>  lib/fault-inject.c | 36 +++++++++++++++++++++++++++++++-----
>  2 files changed, 60 insertions(+), 5 deletions(-)
>
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index 52f7e14..9e81720 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1701,6 +1701,35 @@ config FAULT_INJECTION_STACKTRACE_FILTER
>         help
>           Provide stacktrace filter for fault-injection capabilities
>
> +config FAULT_INJECTION_AT_NEW_CALLSITES
> +       bool "Inject fault the first time at a new callsite"

Isn't it better to make a run time configurable option instead of the
build option?

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

#1457826 — Re: [PATCH 10/10] fault injection: inject faults in new/rare callchains

Hi,

On 08/08/2016 03:54 PM, Akinobu Mita wrote:
> 2016-08-04 0:05 GMT+09:00 Vegard Nossum <vegard.nossum@oracle.com>:
>> Before this patch, fault injection uses a combination of randomness and
>> frequency to determine where to inject faults. The problem with this is
>> that code paths which are executed very rarely get proportional amounts
>> of faults injected.
>>
>> A better heuristic is to look at the actual callchain leading up to the
>> possible failure point; if we see a callchain that we've never seen up
>> until this point, chances are it's a rare one and we should definitely
>> inject a fault here (since we might not get the chance again later).
>>
>> This uses a probabilistic set structure (similar to a bloom filter) to
>> determine whether we have seen a particular callchain before by hashing
>> the stack trace and atomically testing/setting a bit corresponding to
>> the current callchain.
[...]

>> +config FAULT_INJECTION_AT_NEW_CALLSITES
>> +       bool "Inject fault the first time at a new callsite"
>
> Isn't it better to make a run time configurable option instead of the
> build option?

I prefer a build option personally since it keeps the code simple (you
don't have to dynamically allocate the bitmap of known callchains, for
example). I figured most people using fault injection would enable the
new option while still allowing others to keep the current behaviour
if they really want to.

If you prefer a run-time option I can submit a new version.

Thanks,


Vegard

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

#1457899

2016-08-08 23:07 GMT+09:00 Vegard Nossum <vegard.nossum@oracle.com>:
> Hi,
>
> On 08/08/2016 03:54 PM, Akinobu Mita wrote:
>>
>> 2016-08-04 0:05 GMT+09:00 Vegard Nossum <vegard.nossum@oracle.com>:
>>>
>>> Before this patch, fault injection uses a combination of randomness and
>>> frequency to determine where to inject faults. The problem with this is
>>> that code paths which are executed very rarely get proportional amounts
>>> of faults injected.
>>>
>>> A better heuristic is to look at the actual callchain leading up to the
>>> possible failure point; if we see a callchain that we've never seen up
>>> until this point, chances are it's a rare one and we should definitely
>>> inject a fault here (since we might not get the chance again later).
>>>
>>> This uses a probabilistic set structure (similar to a bloom filter) to
>>> determine whether we have seen a particular callchain before by hashing
>>> the stack trace and atomically testing/setting a bit corresponding to
>>> the current callchain.
>
> [...]
>
>>> +config FAULT_INJECTION_AT_NEW_CALLSITES
>>> +       bool "Inject fault the first time at a new callsite"
>>
>>
>> Isn't it better to make a run time configurable option instead of the
>> build option?
>
>
> I prefer a build option personally since it keeps the code simple (you
> don't have to dynamically allocate the bitmap of known callchains, for
> example). I figured most people using fault injection would enable the
> new option while still allowing others to keep the current behaviour
> if they really want to.
>
> If you prefer a run-time option I can submit a new version.
>

I prefer run-time tunable like
"/sys/kernel/debug/fail*/inject-at-new-callsites" in order to turn
on or off this feature for each fault injection type.  I think this
doesn't add too much complexity if the bitmap can be put into
struct fault_attr.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web