mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Vegard Nossum <vegard.nossum@oracle.com>
To: Akinobu Mita <akinobu.mita@gmail.com>,
	Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@redhat.com>
Cc: linux-kernel@vger.kernel.org, Vegard Nossum <vegard.nossum@oracle.com>
Subject: [PATCH 10/10] fault injection: inject faults in new/rare callchains
Date: Wed,  3 Aug 2016 17:05:55 +0200	[thread overview]
Message-ID: <1470236755-29844-10-git-send-email-vegard.nossum@oracle.com> (raw)
In-Reply-To: <1470236755-29844-1-git-send-email-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"
+	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

  parent reply	other threads:[~2016-08-03 15:11 UTC|newest]

Thread overview: 19+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2016-08-03 15:05 [PATCH 01/10] fault injection: fix a few documentation errors Vegard Nossum
2016-08-03 15:05 ` [PATCH 02/10] fault injection: fix Kconfig menu Vegard Nossum
2016-08-03 15:05 ` [PATCH 03/10] fault injection: allow FAULT_INJECTION_STACKTRACE_FILTER on X86_64 Vegard Nossum
2016-08-03 15:05 ` [PATCH 04/10] fault injection: prevent recursive fault injection Vegard Nossum
2016-08-03 15:05 ` [PATCH 05/10] fault injection: mutex_trylock() " Vegard Nossum
2016-08-03 16:07   ` kbuild test robot
2016-08-03 18:15   ` kbuild test robot
2016-08-03 15:05 ` [PATCH 06/10] fault injection: rt_mutex_trylock() " Vegard Nossum
2016-08-03 15:05 ` [PATCH 07/10] fault injection: down_trylock() " Vegard Nossum
2016-08-03 15:05 ` [PATCH 08/10] fault injection: down_{read,write}_trylock() " Vegard Nossum
2016-08-03 15:05 ` [PATCH 09/10] fault injection: spin_trylock() " Vegard Nossum
2016-08-03 22:02   ` kbuild test robot
2016-08-03 22:11   ` kbuild test robot
2016-08-03 15:05 ` Vegard Nossum [this message]
2016-08-08 13:54   ` [PATCH 10/10] fault injection: inject faults in new/rare callchains Akinobu Mita
2016-08-08 14:07     ` Vegard Nossum
2016-08-08 16:24       ` Akinobu Mita
2016-10-16 15:56 [PATCH 01/10] fault injection: fix a few documentation errors Vegard Nossum
2016-10-16 15:56 ` [PATCH 10/10] fault injection: inject faults in new/rare callchains Vegard Nossum
2016-10-21  0:32   ` Akinobu Mita

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=1470236755-29844-10-git-send-email-vegard.nossum@oracle.com \
    --to=vegard.nossum@oracle.com \
    --cc=akinobu.mita@gmail.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®