From patchwork Sun Apr 29 02:45:42 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Igor Stoppa X-Patchwork-Id: 10370457 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id A1DDD602DC for ; Sun, 29 Apr 2018 02:46:49 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 91EBD28BDF for ; Sun, 29 Apr 2018 02:46:49 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 85BBE28BE9; Sun, 29 Apr 2018 02:46:49 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-5.3 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 Received: from mother.openwall.net (mother.openwall.net [195.42.179.200]) by mail.wl.linuxfoundation.org (Postfix) with SMTP id C73FA28BDF for ; Sun, 29 Apr 2018 02:46:47 +0000 (UTC) Received: (qmail 7186 invoked by uid 550); 29 Apr 2018 02:46:31 -0000 Mailing-List: contact kernel-hardening-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Delivered-To: mailing list kernel-hardening@lists.openwall.com Received: (qmail 5980 invoked from network); 29 Apr 2018 02:46:28 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=from:to:cc:subject:date:message-id:in-reply-to:references; bh=5c/5rZYnz1wXQeTG0QOd8iGMshQm/mAdfXubAdVfw9s=; b=YnzZNg/tAep03hV6k8GCqsWw3fUYWOuYPRS4oSEpZlHaFnBzxqMNQdSb3fQW2TnMtB /Uu51pG/HDm4pgnvO8EYODDdztnkA7PqrKlIj06zX4xOhqDPWlWFMxfwtSDekRrPFHrX 6oTwQvxi4fSUoSNFx4KLIMDp3bWFX9FYt7JIxvRoeTWs3EikU+5Vqd6PdruxRrJlvHGe ODVNvHPmb4VHUrD1xirXMdwLapxvDfl86NJb0Q0pF7eEtdnJ44lb9bNBDxWF7WFgX3um XXX0CW5q5MkfEbRnDfZ8/8pFL9TaDePu8003sYt+urNl9UgK0ShhscF8tpVEHvt9ShhQ cN6w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=5c/5rZYnz1wXQeTG0QOd8iGMshQm/mAdfXubAdVfw9s=; b=XUtkSTWKlsmlbp4JEydKSql4sB4xgsIGT7U34+fMZUva7ed1VW5Hn+ZgsOgnonntWY 5stFbshzRj02uLkgHd2p/SWcKEUKO3bhuBSj3ST/CWTF71jC61KvP6565f3SfbdCjjBX ZsNXfVEP6wfNNEA20C/umiQyOApeCGFv1MEwObDrmhOW2kcVTiGHtpaBTSP/X7p7wuJ1 QqI7iB62teGUnE+4bN3NuRr9ueFOFeq+JbjSlk2l6Icvfu3a7wAMdRazZZMcW2ilwOGa YcnraURSh+OhMbQIH9XdWKniulCtMlBhyUsIn2pBHRd0OhYevIWVZcqYpeRaFeFq80B0 yc5A== X-Gm-Message-State: ALQs6tC9dgeo8fYQB55ilg6XwYX8Gq2+fUxaattPN2brqJPrm01JsB3i p9QtaajEAPOYrkVmM8zImr8= X-Google-Smtp-Source: AB8JxZoESpnV1X/QYI+yyMwKz/DstnUJDT6nm7BCdNoIz5AA8SwUPkYayRjMy5FhtTikbRMsDJyyww== X-Received: by 2002:a2e:1288:: with SMTP id 8-v6mr4874539ljs.137.1524969977076; Sat, 28 Apr 2018 19:46:17 -0700 (PDT) From: Igor Stoppa X-Google-Original-From: Igor Stoppa To: mhocko@kernel.org, akpm@linux-foundation.org, keescook@chromium.org, linux-mm@kvack.org, kernel-hardening@lists.openwall.com, linux-security-module@vger.kernel.org Cc: willy@infradead.org, labbott@redhat.com, linux-kernel@vger.kernel.org, igor.stoppa@huawei.com Subject: [PATCH 3/3] genalloc: selftest Date: Sun, 29 Apr 2018 06:45:42 +0400 Message-Id: <20180429024542.19475-4-igor.stoppa@huawei.com> X-Mailer: git-send-email 2.14.1 In-Reply-To: <20180429024542.19475-1-igor.stoppa@huawei.com> References: <20180429024542.19475-1-igor.stoppa@huawei.com> X-Virus-Scanned: ClamAV using ClamSMTP Introduce a set of macros for writing concise test cases for genalloc. The test cases are meant to provide regression testing, when working on new functionality for genalloc. Primarily they are meant to confirm that the various allocation strategy will continue to work as expected. The execution of the self testing is controlled through a Kconfig option. The testing takes place in the very early stages of main.c, to ensure that failures in genalloc are caught before they can cause unexplained erratic behavior in any of genalloc users. Therefore, it would not be advisable to implement it as module. Signed-off-by: Igor Stoppa --- init/main.c | 2 + lib/Kconfig | 15 ++ lib/Makefile | 1 + lib/test_genalloc.c | 410 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 428 insertions(+) create mode 100644 lib/test_genalloc.c diff --git a/init/main.c b/init/main.c index b795aa341a3a..b3b319d91b0e 100644 --- a/init/main.c +++ b/init/main.c @@ -91,6 +91,7 @@ #include #include #include +#include #include #include @@ -679,6 +680,7 @@ asmlinkage __visible void __init start_kernel(void) */ mem_encrypt_init(); + test_genalloc(); #ifdef CONFIG_BLK_DEV_INITRD if (initrd_start && !initrd_below_start_ok && page_to_pfn(virt_to_page((void *)initrd_start)) < min_low_pfn) { diff --git a/lib/Kconfig b/lib/Kconfig index 09565d779324..2bf89af50728 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -303,6 +303,21 @@ config DECOMPRESS_LZ4 config GENERIC_ALLOCATOR bool +config TEST_GENERIC_ALLOCATOR + bool "genalloc tester" + default n + select GENERIC_ALLOCATOR + help + Enable automated testing of the generic allocator. + The testing is primarily for the tracking of allocated space. + +config TEST_GENERIC_ALLOCATOR_VERBOSE + bool "make the genalloc tester more verbose" + default n + select TEST_GENERIC_ALLOCATOR + help + More information will be displayed during the self-testing. + # # reed solomon support is select'ed if needed # diff --git a/lib/Makefile b/lib/Makefile index 384713ff70d3..2c66346ab246 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -114,6 +114,7 @@ obj-$(CONFIG_LIBCRC32C) += libcrc32c.o obj-$(CONFIG_CRC8) += crc8.o obj-$(CONFIG_XXHASH) += xxhash.o obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o +obj-$(CONFIG_TEST_GENERIC_ALLOCATOR) += test_genalloc.o obj-$(CONFIG_842_COMPRESS) += 842/ obj-$(CONFIG_842_DECOMPRESS) += 842/ diff --git a/lib/test_genalloc.c b/lib/test_genalloc.c new file mode 100644 index 000000000000..ab9984861517 --- /dev/null +++ b/lib/test_genalloc.c @@ -0,0 +1,410 @@ +// SPDX-License-Identifier: GPL-2.0 +/* + * test_genalloc.c + * + * (C) Copyright 2017 Huawei Technologies Co. Ltd. + * Author: Igor Stoppa + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + + +/* + * In case of failure of any of these tests, memory corruption is almost + * guarranteed; allowing the boot to continue means risking to corrupt + * also any filesystem/block device accessed write mode. + * Therefore, BUG_ON() is used, when testing. + */ + + +/* + * Keep the bitmap small, while including case of cross-ulong mapping. + * For simplicity, the test cases use only 1 chunk of memory. + */ +#define BITMAP_SIZE_C 16 +#define ALLOC_ORDER 0 + +#define ULONG_SIZE (sizeof(unsigned long)) +#define BITMAP_SIZE_UL (BITMAP_SIZE_C / ULONG_SIZE) +#define MIN_ALLOC_SIZE (1 << ALLOC_ORDER) +#define ENTRIES (BITMAP_SIZE_C * 8) +#define CHUNK_SIZE (MIN_ALLOC_SIZE * ENTRIES) + +#ifndef CONFIG_TEST_GENERIC_ALLOCATOR_VERBOSE + +static inline void print_first_chunk_bitmap(struct gen_pool *pool) {} + +#else + +static void print_first_chunk_bitmap(struct gen_pool *pool) +{ + struct gen_pool_chunk *chunk; + char bitmap[BITMAP_SIZE_C * 2 + 1]; + unsigned long i; + char *bm = bitmap; + char *entry; + + if (unlikely(pool == NULL || pool->chunks.next == NULL)) + return; + + chunk = container_of(pool->chunks.next, struct gen_pool_chunk, + next_chunk); + entry = (void *)chunk->entries; + for (i = 1; i <= BITMAP_SIZE_C; i++) + bm += snprintf(bm, 3, "%02hhx", entry[BITMAP_SIZE_C - i]); + *bm = '\0'; + pr_notice("chunk: %p bitmap: 0x%s\n", chunk, bitmap); + +} + +#endif + +enum test_commands { + CMD_ALLOCATOR, + CMD_ALLOCATE, + CMD_FLUSH, + CMD_FREE, + CMD_NUMBER, + CMD_END = CMD_NUMBER, +}; + +struct null_struct { + void *null; +}; + +struct test_allocator { + genpool_algo_t algo; + union { + struct genpool_data_align align; + struct genpool_data_fixed offset; + struct null_struct null; + } data; +}; + +struct test_action { + unsigned int location; + char pattern[BITMAP_SIZE_C]; + unsigned int size; +}; + + +struct test_command { + enum test_commands command; + union { + struct test_allocator allocator; + struct test_action action; + }; +}; + + +/* + * To pass an array literal as parameter to a macro, it must go through + * this one, first. + */ +#define ARR(...) __VA_ARGS__ + +#define SET_DATA(parameter, value) \ + .parameter = { \ + .parameter = value, \ + } \ + +#define SET_ALLOCATOR(alloc, parameter, value) \ +{ \ + .command = CMD_ALLOCATOR, \ + .allocator = { \ + .algo = (alloc), \ + .data = { \ + SET_DATA(parameter, value), \ + }, \ + } \ +} + +#define ACTION_MEM(act, mem_size, mem_loc, match) \ +{ \ + .command = act, \ + .action = { \ + .size = (mem_size), \ + .location = (mem_loc), \ + .pattern = match, \ + }, \ +} + +#define ALLOCATE_MEM(mem_size, mem_loc, match) \ + ACTION_MEM(CMD_ALLOCATE, mem_size, mem_loc, ARR(match)) + +#define FREE_MEM(mem_size, mem_loc, match) \ + ACTION_MEM(CMD_FREE, mem_size, mem_loc, ARR(match)) + +#define FLUSH_MEM() \ +{ \ + .command = CMD_FLUSH, \ +} + +#define END() \ +{ \ + .command = CMD_END, \ +} + +static inline int compare_bitmaps(const struct gen_pool *pool, + const char *reference) +{ + struct gen_pool_chunk *chunk; + char *bitmap; + unsigned int i; + + chunk = container_of(pool->chunks.next, struct gen_pool_chunk, + next_chunk); + bitmap = (char *)chunk->entries; + + for (i = 0; i < BITMAP_SIZE_C; i++) + if (bitmap[i] != reference[i]) + return -1; + return 0; +} + +static void callback_set_allocator(struct gen_pool *pool, + const struct test_command *cmd, + unsigned long *locations) +{ + gen_pool_set_algo(pool, cmd->allocator.algo, + (void *)&cmd->allocator.data); +} + +static void callback_allocate(struct gen_pool *pool, + const struct test_command *cmd, + unsigned long *locations) +{ + const struct test_action *action = &cmd->action; + + locations[action->location] = gen_pool_alloc(pool, action->size); + BUG_ON(!locations[action->location]); + print_first_chunk_bitmap(pool); + BUG_ON(compare_bitmaps(pool, action->pattern)); +} + +static void callback_flush(struct gen_pool *pool, + const struct test_command *cmd, + unsigned long *locations) +{ + unsigned int i; + + for (i = 0; i < ENTRIES; i++) + if (locations[i]) { + gen_pool_free(pool, locations[i], 0); + locations[i] = 0; + } +} + +static void callback_free(struct gen_pool *pool, + const struct test_command *cmd, + unsigned long *locations) +{ + const struct test_action *action = &cmd->action; + + gen_pool_free(pool, locations[action->location], 0); + locations[action->location] = 0; + print_first_chunk_bitmap(pool); + BUG_ON(compare_bitmaps(pool, action->pattern)); +} + +static void (* const callbacks[CMD_NUMBER])(struct gen_pool *, + const struct test_command *, + unsigned long *) = { + [CMD_ALLOCATOR] = callback_set_allocator, + [CMD_ALLOCATE] = callback_allocate, + [CMD_FREE] = callback_free, + [CMD_FLUSH] = callback_flush, +}; + +static const struct test_command test_first_fit[] = { + SET_ALLOCATOR(gen_pool_first_fit, null, NULL), + ALLOCATE_MEM(3, 0, ARR({0x2b})), + ALLOCATE_MEM(2, 1, ARR({0xeb, 0x02})), + ALLOCATE_MEM(5, 2, ARR({0xeb, 0xae, 0x0a})), + FREE_MEM(2, 1, ARR({0x2b, 0xac, 0x0a})), + ALLOCATE_MEM(1, 1, ARR({0xeb, 0xac, 0x0a})), + FREE_MEM(0, 2, ARR({0xeb})), + FREE_MEM(0, 0, ARR({0xc0})), + FREE_MEM(0, 1, ARR({0x00})), + END(), +}; + +/* + * To make the test work for both 32bit and 64bit ulong sizes, + * allocate (8 / 2 * 4 - 1) = 15 bytes bytes, then 16, then 2. + * The first allocation prepares for the crossing of the 32bit ulong + * threshold. The following crosses the 32bit threshold and prepares for + * crossing the 64bit thresholds. The last is large enough (2 bytes) to + * cross the 64bit threshold. + * Then free the allocations in the order: 2nd, 1st, 3rd. + */ +static const struct test_command test_ulong_span[] = { + SET_ALLOCATOR(gen_pool_first_fit, null, NULL), + ALLOCATE_MEM(15, 0, ARR({0xab, 0xaa, 0xaa, 0x2a})), + ALLOCATE_MEM(16, 1, ARR({0xab, 0xaa, 0xaa, 0xea, + 0xaa, 0xaa, 0xaa, 0x2a})), + ALLOCATE_MEM(2, 2, ARR({0xab, 0xaa, 0xaa, 0xea, + 0xaa, 0xaa, 0xaa, 0xea, + 0x02})), + FREE_MEM(0, 1, ARR({0xab, 0xaa, 0xaa, 0x2a, + 0x00, 0x00, 0x00, 0xc0, + 0x02})), + FREE_MEM(0, 0, ARR({0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0xc0, + 0x02})), + FREE_MEM(0, 2, ARR({0x00})), + END(), +}; + +/* + * Create progressively smaller allocations A B C D E. + * then free B and D. + * Then create new allocation that would fit in both of the gaps left by + * B and D. Verify that it uses the gap from B. + */ +static const struct test_command test_first_fit_gaps[] = { + SET_ALLOCATOR(gen_pool_first_fit, null, NULL), + ALLOCATE_MEM(10, 0, ARR({0xab, 0xaa, 0x0a})), + ALLOCATE_MEM(8, 1, ARR({0xab, 0xaa, 0xba, 0xaa, + 0x0a})), + ALLOCATE_MEM(6, 2, ARR({0xab, 0xaa, 0xba, 0xaa, + 0xba, 0xaa})), + ALLOCATE_MEM(4, 3, ARR({0xab, 0xaa, 0xba, 0xaa, + 0xba, 0xaa, 0xab})), + ALLOCATE_MEM(2, 4, ARR({0xab, 0xaa, 0xba, 0xaa, + 0xba, 0xaa, 0xab, 0x0b})), + FREE_MEM(0, 1, ARR({0xab, 0xaa, 0x0a, 0x00, + 0xb0, 0xaa, 0xab, 0x0b})), + FREE_MEM(0, 3, ARR({0xab, 0xaa, 0x0a, 0x00, + 0xb0, 0xaa, 0x00, 0x0b})), + ALLOCATE_MEM(3, 3, ARR({0xab, 0xaa, 0xba, 0x02, + 0xb0, 0xaa, 0x00, 0x0b})), + FLUSH_MEM(), + END(), +}; + +/* Test first fit align */ +static const struct test_command test_first_fit_align[] = { + SET_ALLOCATOR(gen_pool_first_fit_align, align, 4), + ALLOCATE_MEM(5, 0, ARR({0xab, 0x02})), + ALLOCATE_MEM(3, 1, ARR({0xab, 0x02, 0x2b})), + ALLOCATE_MEM(2, 2, ARR({0xab, 0x02, 0x2b, 0x0b})), + ALLOCATE_MEM(1, 3, ARR({0xab, 0x02, 0x2b, 0x0b, 0x03})), + FREE_MEM(0, 0, ARR({0x00, 0x00, 0x2b, 0x0b, 0x03})), + FREE_MEM(0, 2, ARR({0x00, 0x00, 0x2b, 0x00, 0x03})), + ALLOCATE_MEM(2, 0, ARR({0x0b, 0x00, 0x2b, 0x00, 0x03})), + FLUSH_MEM(), + END(), +}; + + +/* Test fixed alloc */ +static const struct test_command test_fixed_data[] = { + SET_ALLOCATOR(gen_pool_fixed_alloc, offset, 1), + ALLOCATE_MEM(5, 0, ARR({0xac, 0x0a})), + SET_ALLOCATOR(gen_pool_fixed_alloc, offset, 8), + ALLOCATE_MEM(3, 1, ARR({0xac, 0x0a, 0x2b})), + SET_ALLOCATOR(gen_pool_fixed_alloc, offset, 6), + ALLOCATE_MEM(2, 2, ARR({0xac, 0xba, 0x2b})), + SET_ALLOCATOR(gen_pool_fixed_alloc, offset, 30), + ALLOCATE_MEM(40, 3, ARR({0xac, 0xba, 0x2b, 0x00, + 0x00, 0x00, 0x00, 0xb0, + 0xaa, 0xaa, 0xaa, 0xaa, + 0xaa, 0xaa, 0xaa, 0xaa})), + FLUSH_MEM(), + END(), +}; + + +/* Test first fit order align */ +static const struct test_command test_first_fit_order_align[] = { + SET_ALLOCATOR(gen_pool_first_fit_order_align, null, NULL), + ALLOCATE_MEM(5, 0, ARR({0xab, 0x02})), + ALLOCATE_MEM(3, 1, ARR({0xab, 0x02, 0x2b})), + ALLOCATE_MEM(2, 2, ARR({0xab, 0xb2, 0x2b})), + ALLOCATE_MEM(1, 3, ARR({0xab, 0xbe, 0x2b})), + ALLOCATE_MEM(1, 4, ARR({0xab, 0xbe, 0xeb})), + ALLOCATE_MEM(2, 5, ARR({0xab, 0xbe, 0xeb, 0x0b})), + FLUSH_MEM(), + END(), +}; + + +/* 007 Test best fit */ +static const struct test_command test_best_fit[] = { + SET_ALLOCATOR(gen_pool_best_fit, null, NULL), + ALLOCATE_MEM(5, 0, ARR({0xab, 0x02})), + ALLOCATE_MEM(3, 1, ARR({0xab, 0xae})), + ALLOCATE_MEM(3, 2, ARR({0xab, 0xae, 0x2b})), + ALLOCATE_MEM(1, 3, ARR({0xab, 0xae, 0xeb})), + FREE_MEM(0, 0, ARR({0x00, 0xac, 0xeb})), + FREE_MEM(0, 2, ARR({0x00, 0xac, 0xc0})), + ALLOCATE_MEM(2, 0, ARR({0x00, 0xac, 0xcb})), + FLUSH_MEM(), + END(), +}; + + +enum test_cases_indexes { + TEST_CASE_FIRST_FIT, + TEST_CASE_ULONG_SPAN, + TEST_CASE_FIRST_FIT_GAPS, + TEST_CASE_FIRST_FIT_ALIGN, + TEST_CASE_FIXED_DATA, + TEST_CASE_FIRST_FIT_ORDER_ALIGN, + TEST_CASE_BEST_FIT, + TEST_CASES_NUM, +}; + +static const struct test_command *test_cases[TEST_CASES_NUM] = { + [TEST_CASE_FIRST_FIT] = test_first_fit, + [TEST_CASE_ULONG_SPAN] = test_ulong_span, + [TEST_CASE_FIRST_FIT_GAPS] = test_first_fit_gaps, + [TEST_CASE_FIRST_FIT_ALIGN] = test_first_fit_align, + [TEST_CASE_FIXED_DATA] = test_fixed_data, + [TEST_CASE_FIRST_FIT_ORDER_ALIGN] = test_first_fit_order_align, + [TEST_CASE_BEST_FIT] = test_best_fit, +}; + + +void test_genalloc(void) +{ + static struct gen_pool *pool; + unsigned long locations[ENTRIES]; + char chunk[CHUNK_SIZE]; + int retval; + unsigned int i; + const struct test_command *cmd; + + pool = gen_pool_create(ALLOC_ORDER, -1); + if (unlikely(!pool)) { + pr_err("genalloc-selftest: no memory for pool."); + return; + } + + retval = gen_pool_add_virt(pool, (unsigned long)chunk, 0, + CHUNK_SIZE, -1); + if (unlikely(retval)) { + pr_err("genalloc-selftest: could not register chunk."); + goto destroy_pool; + } + + memset(locations, 0, ENTRIES * sizeof(unsigned long)); + for (i = 0; i < TEST_CASES_NUM; i++) + for (cmd = test_cases[i]; cmd->command < CMD_END; cmd++) + callbacks[cmd->command](pool, cmd, locations); + pr_notice("genalloc-selftest: executed successfully %d tests", + TEST_CASES_NUM); + +destroy_pool: + gen_pool_destroy(pool); +}