From patchwork Mon Feb 28 14:46:45 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Karolina Drobnik X-Patchwork-Id: 12763432 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id B96F6C433F5 for ; Mon, 28 Feb 2022 14:47:23 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 541968D0006; Mon, 28 Feb 2022 09:47:23 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 4CA5C8D0001; Mon, 28 Feb 2022 09:47:23 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 36B008D0006; Mon, 28 Feb 2022 09:47:23 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (relay.hostedemail.com [64.99.140.27]) by kanga.kvack.org (Postfix) with ESMTP id 294D38D0001 for ; Mon, 28 Feb 2022 09:47:23 -0500 (EST) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay09.hostedemail.com (Postfix) with ESMTP id D774722B31 for ; Mon, 28 Feb 2022 14:47:22 +0000 (UTC) X-FDA: 79192466724.03.9028DB0 Received: from mail-lf1-f43.google.com (mail-lf1-f43.google.com [209.85.167.43]) by imf08.hostedemail.com (Postfix) with ESMTP id 57D7D160008 for ; Mon, 28 Feb 2022 14:47:22 +0000 (UTC) Received: by mail-lf1-f43.google.com with SMTP id f37so21719133lfv.8 for ; Mon, 28 Feb 2022 06:47:22 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=from:to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-transfer-encoding; bh=vzfSYgDZmcLeTAJSdBrD8HdMLVfupA/uWZ0BQLISLR0=; b=dqj69tyhozNfuLUxXstfRi2s4MOmnG9bazMi/B6UdY0PNjYSV2vqOBHoV+HqcxX1mK 82Fzi1Ja+ts6f53QLz0F2B+jiXy3pu4ghMEM81dbzr+aF3uulXB/MrE2kBR5ujeoCy0H 7roSD3VP+yBcJpCssAM1Z2Bt2kZ6X/Dv85HL+90/e7TRsxU3BbicHfrTLh0iQ7nDzwfe lpLwAcEykQOFieJ7fhD/nMlV5rk7vXWLB67x6KuxCbanaV/84KxGiz0q207/91x6mSj3 LX/0KEJpyCNpsiUc6ipU/4D7eARtZ/rdgl07dZZEYqCQwr+Sq1vW/a3cWPYBf7wqfijQ BH8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=vzfSYgDZmcLeTAJSdBrD8HdMLVfupA/uWZ0BQLISLR0=; b=6mgRy6adC252UIDVIZIuTfZhG8KQ1NOAQE4kMSGEx0Hle8C9tyITC2pIyoFDgEShWB MiA3oO7JQOYIp3EwMfWO/wTh6R7WJybaPaA6Tk0fuCzE58akX4y6NjfDqiCeNVc6/QGQ RCY6Ih6fDt0n++LaKTAHwvpekeqVzHO6v/jGRwBdOdhv5aMj4tOmhgzp881z2GkdT21d 7Mz1KtLZxC7rxa0FKuSCCh+X85TpbyFAgDylCZmtM/cpZamDanBTEe9vUnrL32xCcLcj /cuWOVhBytpnXY6JKw++i9ylpM32WKEsIaHkbQqKFrnG+j2X8Dg/ZDFGfgO6eoL2lb85 8/3A== X-Gm-Message-State: AOAM531qLdrTEva7w6ALwQLr+nuyvbQ24+QyymhBoxn5v4f5RHgPlDUT AT0ECStP3aOfDwI3MPPjWS3yLCpB4h4= X-Google-Smtp-Source: ABdhPJyXYAjS6kWzrQ9btsFG3XYiC61Xd5kmGREFGnRjGySFBqwYVVWxebHYFFqFkz9w3/xDTJJWGQ== X-Received: by 2002:ac2:5cc8:0:b0:443:770f:a7 with SMTP id f8-20020ac25cc8000000b00443770f00a7mr12427748lfq.18.1646059640785; Mon, 28 Feb 2022 06:47:20 -0800 (PST) Received: from elysium.toya.net.pl (staticline-31-183-165-244.toya.net.pl. [31.183.165.244]) by smtp.gmail.com with ESMTPSA id r14-20020ac252ae000000b00443f3cbc03asm993996lfm.6.2022.02.28.06.47.19 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Mon, 28 Feb 2022 06:47:20 -0800 (PST) From: Karolina Drobnik To: linux-mm@kvack.org Cc: rppt@kernel.org, akpm@linux-foundation.org, linux-kernel@vger.kernel.org, Karolina Drobnik Subject: [PATCH 3/9] memblock tests: Add memblock_alloc tests for top down Date: Mon, 28 Feb 2022 15:46:45 +0100 Message-Id: <26ccf409b8ff0394559d38d792b2afb24b55887c.1646055639.git.karolinadrobnik@gmail.com> X-Mailer: git-send-email 2.30.2 In-Reply-To: References: MIME-Version: 1.0 X-Rspamd-Queue-Id: 57D7D160008 X-Stat-Signature: 195tx4x6ezqafx4936mrbwow1ktgugk4 X-Rspam-User: Authentication-Results: imf08.hostedemail.com; dkim=pass header.d=gmail.com header.s=20210112 header.b=dqj69tyh; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf08.hostedemail.com: domain of karolinadrobnik@gmail.com designates 209.85.167.43 as permitted sender) smtp.mailfrom=karolinadrobnik@gmail.com X-Rspamd-Server: rspam03 X-HE-Tag: 1646059642-112958 X-Bogosity: Ham, tests=bogofilter, spamicity=0.000101, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: Add checks for memblock_alloc for top down allocation direction. The tested scenarios are: - Region can be allocated on the first fit (with and without region merging) - Region can be allocated on the second fit (with and without region merging) Add checks for both allocation directions: - Region can be allocated between two already existing entries - Limited memory available - All memory is reserved - No available memory registered with memblock Signed-off-by: Karolina Drobnik --- tools/testing/memblock/Makefile | 2 +- tools/testing/memblock/main.c | 3 + tools/testing/memblock/tests/alloc_api.c | 428 +++++++++++++++++++++++ tools/testing/memblock/tests/alloc_api.h | 9 + 4 files changed, 441 insertions(+), 1 deletion(-) create mode 100644 tools/testing/memblock/tests/alloc_api.c create mode 100644 tools/testing/memblock/tests/alloc_api.h diff --git a/tools/testing/memblock/Makefile b/tools/testing/memblock/Makefile index 29715327a2d3..5b01cfd808d0 100644 --- a/tools/testing/memblock/Makefile +++ b/tools/testing/memblock/Makefile @@ -6,7 +6,7 @@ CFLAGS += -I. -I../../include -Wall -O2 -fsanitize=address \ -fsanitize=undefined -D CONFIG_PHYS_ADDR_T_64BIT LDFLAGS += -fsanitize=address -fsanitize=undefined TARGETS = main -TEST_OFILES = tests/basic_api.o tests/common.o +TEST_OFILES = tests/alloc_api.o tests/basic_api.o tests/common.o DEP_OFILES = memblock.o lib/slab.o mmzone.o slab.o OFILES = main.o $(DEP_OFILES) $(TEST_OFILES) EXTR_SRC = ../../../mm/memblock.c diff --git a/tools/testing/memblock/main.c b/tools/testing/memblock/main.c index da65b0adee91..e7cc45dc06d4 100644 --- a/tools/testing/memblock/main.c +++ b/tools/testing/memblock/main.c @@ -1,8 +1,11 @@ // SPDX-License-Identifier: GPL-2.0-or-later #include "tests/basic_api.h" +#include "tests/alloc_api.h" int main(int argc, char **argv) { memblock_basic_checks(); + memblock_alloc_checks(); + return 0; } diff --git a/tools/testing/memblock/tests/alloc_api.c b/tools/testing/memblock/tests/alloc_api.c new file mode 100644 index 000000000000..22ba9a2b4eaf --- /dev/null +++ b/tools/testing/memblock/tests/alloc_api.c @@ -0,0 +1,428 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +#include "alloc_api.h" + +/* + * A simple test that tries to allocate a small memory region. + * Expect to allocate an aligned region near the end of the available memory. + */ +static int alloc_top_down_simple_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + void *allocated_ptr = NULL; + + phys_addr_t size = SZ_2; + phys_addr_t expected_start; + + setup_memblock(); + + expected_start = memblock_end_of_DRAM() - SMP_CACHE_BYTES; + + allocated_ptr = memblock_alloc(size, SMP_CACHE_BYTES); + + assert(allocated_ptr); + assert(rgn->size == size); + assert(rgn->base == expected_start); + + assert(memblock.reserved.cnt == 1); + assert(memblock.reserved.total_size == size); + + return 0; +} + +/* + * A test that tries to allocate memory next to a reserved region that starts at + * the misaligned address. Expect to create two separate entries, with the new + * entry aligned to the provided alignment: + * + * + + * | +--------+ +--------| + * | | rgn2 | | rgn1 | + * +------------+--------+---------+--------+ + * ^ + * | + * Aligned address boundary + * + * The allocation direction is top-down and region arrays are sorted from lower + * to higher addresses, so the new region will be the first entry in + * memory.reserved array. The previously reserved region does not get modified. + * Region counter and total size get updated. + */ +static int alloc_top_down_disjoint_check(void) +{ + /* After allocation, this will point to the "old" region */ + struct memblock_region *rgn1 = &memblock.reserved.regions[1]; + struct memblock_region *rgn2 = &memblock.reserved.regions[0]; + struct region r1; + void *allocated_ptr = NULL; + + phys_addr_t r2_size = SZ_16; + /* Use custom alignment */ + phys_addr_t alignment = SMP_CACHE_BYTES * 2; + phys_addr_t total_size; + phys_addr_t expected_start; + + setup_memblock(); + + r1.base = memblock_end_of_DRAM() - SZ_2; + r1.size = SZ_2; + + total_size = r1.size + r2_size; + expected_start = memblock_end_of_DRAM() - alignment; + + memblock_reserve(r1.base, r1.size); + + allocated_ptr = memblock_alloc(r2_size, alignment); + + assert(allocated_ptr); + assert(rgn1->size == r1.size); + assert(rgn1->base == r1.base); + + assert(rgn2->size == r2_size); + assert(rgn2->base == expected_start); + + assert(memblock.reserved.cnt == 2); + assert(memblock.reserved.total_size == total_size); + + return 0; +} + +/* + * A test that tries to allocate memory when there is enough space at the end + * of the previously reserved block (i.e. first fit): + * + * | +--------+--------------| + * | | r1 | r2 | + * +--------------+--------+--------------+ + * + * Expect a merge of both regions. Only the region size gets updated. + */ +static int alloc_top_down_before_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + void *allocated_ptr = NULL; + + /* The first region ends at the aligned address to test region merging */ + phys_addr_t r1_size = SMP_CACHE_BYTES; + phys_addr_t r2_size = SZ_512; + phys_addr_t total_size = r1_size + r2_size; + + setup_memblock(); + + memblock_reserve(memblock_end_of_DRAM() - total_size, r1_size); + + allocated_ptr = memblock_alloc(r2_size, SMP_CACHE_BYTES); + + assert(allocated_ptr); + assert(rgn->size == total_size); + assert(rgn->base == memblock_end_of_DRAM() - total_size); + + assert(memblock.reserved.cnt == 1); + assert(memblock.reserved.total_size == total_size); + + return 0; +} + +/* + * A test that tries to allocate memory when there is not enough space at the + * end of the previously reserved block (i.e. second fit): + * + * | +-----------+------+ | + * | | r2 | r1 | | + * +------------+-----------+------+-----+ + * + * Expect a merge of both regions. Both the base address and size of the region + * get updated. + */ +static int alloc_top_down_after_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + struct region r1; + void *allocated_ptr = NULL; + + phys_addr_t r2_size = SZ_512; + phys_addr_t total_size; + + setup_memblock(); + + /* The first region starts at the aligned address to test region merging */ + r1.base = memblock_end_of_DRAM() - SMP_CACHE_BYTES; + r1.size = SZ_8; + + total_size = r1.size + r2_size; + + memblock_reserve(r1.base, r1.size); + + allocated_ptr = memblock_alloc(r2_size, SMP_CACHE_BYTES); + + assert(allocated_ptr); + assert(rgn->size == total_size); + assert(rgn->base == r1.base - r2_size); + + assert(memblock.reserved.cnt == 1); + assert(memblock.reserved.total_size == total_size); + + return 0; +} + +/* + * A test that tries to allocate memory when there are two reserved regions with + * a gap too small to fit the new region: + * + * | +--------+----------+ +------| + * | | r3 | r2 | | r1 | + * +-------+--------+----------+---+------+ + * + * Expect to allocate a region before the one that starts at the lower address, + * and merge them into one. The region counter and total size fields get + * updated. + */ +static int alloc_top_down_second_fit_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + struct region r1, r2; + void *allocated_ptr = NULL; + + phys_addr_t r3_size = SZ_1K; + phys_addr_t total_size; + + setup_memblock(); + + r1.base = memblock_end_of_DRAM() - SZ_512; + r1.size = SZ_512; + + r2.base = r1.base - SZ_512; + r2.size = SZ_256; + + total_size = r1.size + r2.size + r3_size; + + memblock_reserve(r1.base, r1.size); + memblock_reserve(r2.base, r2.size); + + allocated_ptr = memblock_alloc(r3_size, SMP_CACHE_BYTES); + + assert(allocated_ptr); + assert(rgn->size == r2.size + r3_size); + assert(rgn->base == r2.base - r3_size); + + assert(memblock.reserved.cnt == 2); + assert(memblock.reserved.total_size == total_size); + + return 0; +} + +/* + * A test that tries to allocate memory when there are two reserved regions with + * a gap big enough to accommodate the new region: + * + * | +--------+--------+--------+ | + * | | r2 | r3 | r1 | | + * +-----+--------+--------+--------+-----+ + * + * Expect to merge all of them, creating one big entry in memblock.reserved + * array. The region counter and total size fields get updated. + */ +static int alloc_in_between_generic_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + struct region r1, r2; + void *allocated_ptr = NULL; + + phys_addr_t gap_size = SMP_CACHE_BYTES; + phys_addr_t r3_size = SZ_64; + /* Calculate regions size so there's just enough space for the new entry */ + phys_addr_t rgn_size = (MEM_SIZE - (2 * gap_size + r3_size)) / 2; + phys_addr_t total_size; + + setup_memblock(); + + r1.size = rgn_size; + r1.base = memblock_end_of_DRAM() - (gap_size + rgn_size); + + r2.size = rgn_size; + r2.base = memblock_start_of_DRAM() + gap_size; + + total_size = r1.size + r2.size + r3_size; + + memblock_reserve(r1.base, r1.size); + memblock_reserve(r2.base, r2.size); + + allocated_ptr = memblock_alloc(r3_size, SMP_CACHE_BYTES); + + assert(allocated_ptr); + assert(rgn->size == total_size); + assert(rgn->base == r1.base - r2.size - r3_size); + + assert(memblock.reserved.cnt == 1); + assert(memblock.reserved.total_size == total_size); + + return 0; +} + +/* + * A test that tries to allocate memory when the memory is filled with reserved + * regions with memory gaps too small to fit the new region: + * + * +-------+ + * | new | + * +--+----+ + * | +-----+ +-----+ +-----+ | + * | | res | | res | | res | | + * +----+-----+----+-----+----+-----+----+ + * + * Expect no allocation to happen. + */ +static int alloc_small_gaps_generic_check(void) +{ + void *allocated_ptr = NULL; + + phys_addr_t region_size = SZ_1K; + phys_addr_t gap_size = SZ_256; + phys_addr_t region_end; + + setup_memblock(); + + region_end = memblock_start_of_DRAM(); + + while (region_end < memblock_end_of_DRAM()) { + memblock_reserve(region_end + gap_size, region_size); + region_end += gap_size + region_size; + } + + allocated_ptr = memblock_alloc(region_size, SMP_CACHE_BYTES); + + assert(!allocated_ptr); + + return 0; +} + +/* + * A test that tries to allocate memory when all memory is reserved. + * Expect no allocation to happen. + */ +static int alloc_all_reserved_generic_check(void) +{ + void *allocated_ptr = NULL; + + setup_memblock(); + + /* Simulate full memory */ + memblock_reserve(memblock_start_of_DRAM(), MEM_SIZE); + + allocated_ptr = memblock_alloc(SZ_256, SMP_CACHE_BYTES); + + assert(!allocated_ptr); + + return 0; +} + +/* + * A test that tries to allocate memory when the memory is almost full, + * with not enough space left for the new region: + * + * +-------+ + * | new | + * +-------+ + * |-----------------------------+ | + * | reserved | | + * +-----------------------------+---+ + * + * Expect no allocation to happen. + */ +static int alloc_no_space_generic_check(void) +{ + void *allocated_ptr = NULL; + + setup_memblock(); + + phys_addr_t available_size = SZ_256; + phys_addr_t reserved_size = MEM_SIZE - available_size; + + /* Simulate almost-full memory */ + memblock_reserve(memblock_start_of_DRAM(), reserved_size); + + allocated_ptr = memblock_alloc(SZ_1K, SMP_CACHE_BYTES); + + assert(!allocated_ptr); + + return 0; +} + +/* + * A test that tries to allocate memory when the memory is almost full, + * but there is just enough space left: + * + * |---------------------------+---------| + * | reserved | new | + * +---------------------------+---------+ + * + * Expect to allocate memory and merge all the regions. The total size field + * gets updated. + */ +static int alloc_limited_space_generic_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + void *allocated_ptr = NULL; + + phys_addr_t available_size = SZ_256; + phys_addr_t reserved_size = MEM_SIZE - available_size; + + setup_memblock(); + + /* Simulate almost-full memory */ + memblock_reserve(memblock_start_of_DRAM(), reserved_size); + + allocated_ptr = memblock_alloc(available_size, SMP_CACHE_BYTES); + + assert(allocated_ptr); + assert(rgn->size == MEM_SIZE); + assert(rgn->base == memblock_start_of_DRAM()); + + assert(memblock.reserved.cnt == 1); + assert(memblock.reserved.total_size == MEM_SIZE); + + return 0; +} + +/* + * A test that tries to allocate memory when there is no available memory + * registered (i.e. memblock.memory has only a dummy entry). + * Expect no allocation to happen. + */ +static int alloc_no_memory_generic_check(void) +{ + struct memblock_region *rgn = &memblock.reserved.regions[0]; + void *allocated_ptr = NULL; + + reset_memblock_regions(); + + allocated_ptr = memblock_alloc(SZ_1K, SMP_CACHE_BYTES); + + assert(!allocated_ptr); + assert(rgn->size == 0); + assert(rgn->base == 0); + assert(memblock.reserved.total_size == 0); + + return 0; +} + +int memblock_alloc_checks(void) +{ + reset_memblock_attributes(); + dummy_physical_memory_init(); + + alloc_top_down_simple_check(); + alloc_top_down_disjoint_check(); + alloc_top_down_before_check(); + alloc_top_down_after_check(); + alloc_top_down_second_fit_check(); + alloc_in_between_generic_check(); + alloc_small_gaps_generic_check(); + alloc_all_reserved_generic_check(); + alloc_no_space_generic_check(); + alloc_limited_space_generic_check(); + alloc_no_memory_generic_check(); + + dummy_physical_memory_cleanup(); + + return 0; +} diff --git a/tools/testing/memblock/tests/alloc_api.h b/tools/testing/memblock/tests/alloc_api.h new file mode 100644 index 000000000000..585b085baf21 --- /dev/null +++ b/tools/testing/memblock/tests/alloc_api.h @@ -0,0 +1,9 @@ +/* SPDX-License-Identifier: GPL-2.0-or-later */ +#ifndef _MEMBLOCK_ALLOCS_H +#define _MEMBLOCK_ALLOCS_H + +#include "common.h" + +int memblock_alloc_checks(void); + +#endif