From patchwork Mon Aug 29 12:34:07 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tixy X-Patchwork-Id: 1107702 Received: from merlin.infradead.org (merlin.infradead.org [205.233.59.134]) by demeter2.kernel.org (8.14.4/8.14.4) with ESMTP id p7TCacR2018328 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO) for ; Mon, 29 Aug 2011 12:36:59 GMT Received: from canuck.infradead.org ([2001:4978:20e::1]) by merlin.infradead.org with esmtps (Exim 4.76 #1 (Red Hat Linux)) id 1Qy14a-00050L-M2; Mon, 29 Aug 2011 12:36:17 +0000 Received: from localhost ([127.0.0.1] helo=canuck.infradead.org) by canuck.infradead.org with esmtp (Exim 4.76 #1 (Red Hat Linux)) id 1Qy14Z-0000rp-Rr; Mon, 29 Aug 2011 12:36:15 +0000 Received: from smarthost04.mail.zen.net.uk ([212.23.3.143]) by canuck.infradead.org with esmtp (Exim 4.76 #1 (Red Hat Linux)) id 1Qy12g-0000fU-LF for linux-arm-kernel@lists.infradead.org; Mon, 29 Aug 2011 12:34:24 +0000 Received: from [82.69.122.217] (helo=plug1) by smarthost04.mail.zen.net.uk with esmtpsa (TLS1.0:RSA_AES_256_CBC_SHA1:32) (Exim 4.72) (envelope-from ) id 1Qy12g-0000Za-1a for linux-arm-kernel@lists.infradead.org; Mon, 29 Aug 2011 12:34:18 +0000 Received: from [192.168.2.20] (helo=computer2) by plug1 with esmtp (Exim 4.72) (envelope-from ) id 1Qy12e-0002pa-EZ for linux-arm-kernel@lists.infradead.org; Mon, 29 Aug 2011 13:34:16 +0100 Received: from tixy by computer2 with local (Exim 4.72) (envelope-from ) id 1Qy12e-0000GS-Aj for linux-arm-kernel@lists.infradead.org; Mon, 29 Aug 2011 13:34:16 +0100 From: Tixy To: linux-arm-kernel@lists.infradead.org Subject: [PATCH 08/10] ARM: kprobes: Add decoding table test coverage analysis Date: Mon, 29 Aug 2011 13:34:07 +0100 Message-Id: <1314621249-958-9-git-send-email-tixy@yxit.co.uk> X-Mailer: git-send-email 1.7.2.5 In-Reply-To: <1314621249-958-1-git-send-email-tixy@yxit.co.uk> References: <1314621249-958-1-git-send-email-tixy@yxit.co.uk> X-Originating-Smarthost04-IP: [82.69.122.217] X-CRM114-Version: 20090807-BlameThorstenAndJenny ( TRE 0.7.6 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20110829_083419_040022_95B136DA X-CRM114-Status: GOOD ( 27.21 ) X-Spam-Score: 0.0 (/) X-Spam-Report: SpamAssassin version 3.3.1 on canuck.infradead.org summary: Content analysis details: (0.0 points) pts rule name description ---- ---------------------- -------------------------------------------------- X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: linux-arm-kernel-bounces@lists.infradead.org Errors-To: linux-arm-kernel-bounces+patchwork-linux-arm=patchwork.kernel.org@lists.infradead.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter2.kernel.org [140.211.167.43]); Mon, 29 Aug 2011 12:36:59 +0000 (UTC) From: Jon Medhurst This is used to verify that all combinations of CPU instructions described by the kprobes decoding tables have a test case. Signed-off-by: Jon Medhurst --- arch/arm/kernel/kprobes-test.c | 261 ++++++++++++++++++++++++++++++++++++++++ 1 files changed, 261 insertions(+), 0 deletions(-) diff --git a/arch/arm/kernel/kprobes-test.c b/arch/arm/kernel/kprobes-test.c index 74a3a34..89758a8 100644 --- a/arch/arm/kernel/kprobes-test.c +++ b/arch/arm/kernel/kprobes-test.c @@ -178,6 +178,7 @@ #include #include +#include #include #include "kprobes.h" @@ -529,6 +530,250 @@ static int table_test(const union decode_item *table) /* + * Decoding table test coverage analysis + * + * coverage_start() builds a coverage_table which contains a list of + * coverage_entry's to match each entry in the specified kprobes instruction + * decoding table. + * + * When test cases are run, coverage_add() is called to process each case. + * This looks up the corresponding entry in the coverage_table and sets it as + * being matched, as well as clearing the regs flag appropriate for the test. + * + * After all test cases have been run, coverage_end() is called to check that + * all entries in coverage_table have been matched and that all regs flags are + * cleared. I.e. that all possible combinations of instructions described by + * the kprobes decoding tables have had a test case executed for them. + */ + +bool coverage_fail; + +#define MAX_COVERAGE_ENTRIES 256 + +struct coverage_entry { + const struct decode_header *header; + unsigned regs; + unsigned nesting; + char matched; +}; + +struct coverage_table { + struct coverage_entry *base; + unsigned num_entries; + unsigned nesting; +}; + +struct coverage_table coverage; + +#define COVERAGE_ANY_REG (1<<0) +#define COVERAGE_SP (1<<1) +#define COVERAGE_PC (1<<2) +#define COVERAGE_PCWB (1<<3) + +static const char coverage_register_lookup[16] = { + [REG_TYPE_ANY] = COVERAGE_ANY_REG | COVERAGE_SP | COVERAGE_PC, + [REG_TYPE_SAMEAS16] = COVERAGE_ANY_REG, + [REG_TYPE_SP] = COVERAGE_SP, + [REG_TYPE_PC] = COVERAGE_PC, + [REG_TYPE_NOSP] = COVERAGE_ANY_REG | COVERAGE_SP, + [REG_TYPE_NOSPPC] = COVERAGE_ANY_REG | COVERAGE_SP | COVERAGE_PC, + [REG_TYPE_NOPC] = COVERAGE_ANY_REG | COVERAGE_PC, + [REG_TYPE_NOPCWB] = COVERAGE_ANY_REG | COVERAGE_PC | COVERAGE_PCWB, + [REG_TYPE_NOPCX] = COVERAGE_ANY_REG, + [REG_TYPE_NOSPPCX] = COVERAGE_ANY_REG | COVERAGE_SP, +}; + +unsigned coverage_start_registers(const struct decode_header *h) +{ + unsigned regs = 0; + int i; + for (i = 0; i < 20; i += 4) { + int r = (h->type_regs.bits >> (DECODE_TYPE_BITS + i)) & 0xf; + regs |= coverage_register_lookup[r] << i; + } + return regs; +} + +static int coverage_start_fn(const struct decode_header *h, void *args) +{ + struct coverage_table *coverage = (struct coverage_table *)args; + enum decode_type type = h->type_regs.bits & DECODE_TYPE_MASK; + struct coverage_entry *entry = coverage->base + coverage->num_entries; + + if (coverage->num_entries == MAX_COVERAGE_ENTRIES - 1) { + pr_err("FAIL: Out of space for test coverage data"); + return -ENOMEM; + } + + ++coverage->num_entries; + + entry->header = h; + entry->regs = coverage_start_registers(h); + entry->nesting = coverage->nesting; + entry->matched = false; + + if (type == DECODE_TYPE_TABLE) { + struct decode_table *d = (struct decode_table *)h; + int ret; + ++coverage->nesting; + ret = table_iter(d->table.table, coverage_start_fn, coverage); + --coverage->nesting; + return ret; + } + + return 0; +} + +static int coverage_start(const union decode_item *table) +{ + coverage.base = kmalloc(MAX_COVERAGE_ENTRIES * + sizeof(struct coverage_entry), GFP_KERNEL); + coverage.num_entries = 0; + coverage.nesting = 0; + return table_iter(table, coverage_start_fn, &coverage); +} + +static void +coverage_add_registers(struct coverage_entry *entry, kprobe_opcode_t insn) +{ + int regs = entry->header->type_regs.bits >> DECODE_TYPE_BITS; + int i; + for (i = 0; i < 20; i += 4) { + enum decode_reg_type reg_type = (regs >> i) & 0xf; + int reg = (insn >> i) & 0xf; + int flag; + + if (!reg_type) + continue; + + if (reg == 13) + flag = COVERAGE_SP; + else if (reg == 15) + flag = COVERAGE_PC; + else + flag = COVERAGE_ANY_REG; + entry->regs &= ~(flag << i); + + switch (reg_type) { + + case REG_TYPE_NONE: + case REG_TYPE_ANY: + case REG_TYPE_SAMEAS16: + break; + + case REG_TYPE_SP: + if (reg != 13) + return; + break; + + case REG_TYPE_PC: + if (reg != 15) + return; + break; + + case REG_TYPE_NOSP: + if (reg == 13) + return; + break; + + case REG_TYPE_NOSPPC: + case REG_TYPE_NOSPPCX: + if (reg == 13 || reg == 15) + return; + break; + + case REG_TYPE_NOPCWB: + if (!is_writeback(insn)) + break; + if (reg == 15) { + entry->regs &= ~(COVERAGE_PCWB << i); + return; + } + break; + + case REG_TYPE_NOPC: + case REG_TYPE_NOPCX: + if (reg == 15) + return; + break; + } + + } +} + +static void coverage_add(kprobe_opcode_t insn) +{ + struct coverage_entry *entry = coverage.base; + struct coverage_entry *end = coverage.base + coverage.num_entries; + bool matched = false; + unsigned nesting = 0; + + for (; entry < end; ++entry) { + const struct decode_header *h = entry->header; + enum decode_type type = h->type_regs.bits & DECODE_TYPE_MASK; + + if (entry->nesting > nesting) + continue; /* Skip sub-table we didn't match */ + + if (entry->nesting < nesting) + break; /* End of sub-table we were scanning */ + + if (!matched) { + if ((insn & h->mask.bits) != h->value.bits) + continue; + entry->matched = true; + } + + switch (type) { + + case DECODE_TYPE_TABLE: + ++nesting; + break; + + case DECODE_TYPE_CUSTOM: + case DECODE_TYPE_SIMULATE: + case DECODE_TYPE_EMULATE: + coverage_add_registers(entry, insn); + return; + + case DECODE_TYPE_OR: + matched = true; + break; + + case DECODE_TYPE_REJECT: + default: + return; + } + + } +} + +static void coverage_end(void) +{ + struct coverage_entry *entry = coverage.base; + struct coverage_entry *end = coverage.base + coverage.num_entries; + + for (; entry < end; ++entry) { + u32 mask = entry->header->mask.bits; + u32 value = entry->header->value.bits; + + if (entry->regs) { + pr_err("FAIL: Register test coverage missing for %08x %08x (%05x)\n", + mask, value, entry->regs); + coverage_fail = true; + } + if (!entry->matched) { + pr_err("FAIL: Test coverage entry missing for %08x %08x\n", + mask, value); + coverage_fail = true; + } + } + + kfree(coverage.base); +} + + +/* * Framework for instruction set test cases */ @@ -1039,6 +1284,8 @@ static uintptr_t __used kprobes_test_case_start(const char *title, void *stack) } } + coverage_add(current_instruction); + if (end_arg->flags & ARG_FLAG_UNSUPPORTED) { if (register_test_probe(&test_case_probe) < 0) goto pass; @@ -1213,8 +1460,13 @@ static int run_test_cases(void (*tests)(void), const union decode_item *table) return ret; pr_info(" Run test cases\n"); + ret = coverage_start(table); + if (ret) + return ret; + tests(); + coverage_end(); return 0; } @@ -1274,6 +1526,15 @@ static int __init run_all_tests(void) goto out; } +#if __LINUX_ARM_ARCH__ >= 7 + /* We are able to run all test cases so coverage should be complete */ + if (coverage_fail) { + pr_err("FAIL: Test coverage checks failed\n"); + ret = -EINVAL; + goto out; + } +#endif + out: if (ret == 0) pr_info("Finished kprobe tests OK\n");