From patchwork Sun Feb 8 16:51:14 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 44503 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-we0-f197.google.com (mail-we0-f197.google.com [74.125.82.197]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 1257D2153F for ; Sun, 8 Feb 2015 16:52:14 +0000 (UTC) Received: by mail-we0-f197.google.com with SMTP id l61sf15900132wev.0 for ; Sun, 08 Feb 2015 08:52:13 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:delivered-to:from:to:date:message-id:in-reply-to :references:subject:precedence:reply-to:list-id:list-unsubscribe :list-archive:list-post:list-help:list-subscribe:mime-version :content-type:content-transfer-encoding:errors-to:x-original-sender :x-original-authentication-results:mailing-list; bh=pnpquOAyYLP5wwUobzaKAlKaxn0dQnhPrdJEc0KOdHM=; b=Uo9GR47KkMiMy2peQCAVqbkERfoZ5DkTELhSwwCImuQ/bJj5WXdbBsI+jDRR6Zoo2/ 41Y2BAUhmfsVWd4yhA4/bu1RAMvLWu9PpggXGS1wI7WNQ22qgjtBoJ+X+mryWncF881P VC//Z9UqN6vxUe7q4xaJjoTDnz8U9LCN0r796A6vLU4fiMIevslx/Hkj5BnYp5j/ORbj 9ShHe60P5CYQOAbEkMCFxEufKd5yx8Ze4nXlKm8qd52KLSZ2CzeCfLLuAdxE4M9U/4Ux YoPuJrlfduF0I7a5AUMX3zxT9xQ6/gqTHQmB4K8M9Q5LZ3zd+GILroGqTiyh7OVR7mqP l5Ug== X-Gm-Message-State: ALoCoQlPEqxNJUqyWjZ8fNPgeDqImwC6VphKVctJI4mgH8mHsaGknGRbW4bFnwJua0v80iat8gZC X-Received: by 10.112.154.233 with SMTP id vr9mr1498872lbb.9.1423414333274; Sun, 08 Feb 2015 08:52:13 -0800 (PST) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.206.37 with SMTP id ll5ls495884lac.53.gmail; Sun, 08 Feb 2015 08:52:13 -0800 (PST) X-Received: by 10.112.72.132 with SMTP id d4mr2084086lbv.70.1423414333059; Sun, 08 Feb 2015 08:52:13 -0800 (PST) Received: from mail-la0-f53.google.com (mail-la0-f53.google.com. [209.85.215.53]) by mx.google.com with ESMTPS id dv9si6957658lbc.63.2015.02.08.08.52.12 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 08 Feb 2015 08:52:12 -0800 (PST) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.53 as permitted sender) client-ip=209.85.215.53; Received: by labge10 with SMTP id ge10so9259175lab.12 for ; Sun, 08 Feb 2015 08:52:12 -0800 (PST) X-Received: by 10.112.26.110 with SMTP id k14mr12465973lbg.29.1423414332566; Sun, 08 Feb 2015 08:52:12 -0800 (PST) X-Forwarded-To: patchwork-forward@linaro.org X-Forwarded-For: patch@linaro.org patchwork-forward@linaro.org Delivered-To: patch@linaro.org Received: by 10.112.35.133 with SMTP id h5csp2925294lbj; Sun, 8 Feb 2015 08:52:11 -0800 (PST) X-Received: by 10.107.9.138 with SMTP id 10mr21496706ioj.83.1423414331064; Sun, 08 Feb 2015 08:52:11 -0800 (PST) Received: from lists.sourceforge.net (lists.sourceforge.net. [216.34.181.88]) by mx.google.com with ESMTPS id u1si5966847icq.76.2015.02.08.08.52.10 (version=TLSv1 cipher=RC4-SHA bits=128/128); Sun, 08 Feb 2015 08:52:11 -0800 (PST) Received-SPF: pass (google.com: domain of edk2-devel-bounces@lists.sourceforge.net designates 216.34.181.88 as permitted sender) client-ip=216.34.181.88; Received: from localhost ([127.0.0.1] helo=sfs-ml-4.v29.ch3.sourceforge.com) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YKV5P-0003cM-Cl; Sun, 08 Feb 2015 16:51:55 +0000 Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YKV5N-0003cD-Do for edk2-devel@lists.sourceforge.net; Sun, 08 Feb 2015 16:51:53 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of linaro.org designates 209.85.220.54 as permitted sender) client-ip=209.85.220.54; envelope-from=ard.biesheuvel@linaro.org; helo=mail-pa0-f54.google.com; Received: from mail-pa0-f54.google.com ([209.85.220.54]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1YKV5M-0006rt-Ib for edk2-devel@lists.sourceforge.net; Sun, 08 Feb 2015 16:51:53 +0000 Received: by mail-pa0-f54.google.com with SMTP id kx10so13271313pab.13 for ; Sun, 08 Feb 2015 08:51:46 -0800 (PST) X-Received: by 10.66.255.33 with SMTP id an1mr21970368pad.42.1423414306896; Sun, 08 Feb 2015 08:51:46 -0800 (PST) Received: from ards-macbook-pro.local ([113.28.134.59]) by mx.google.com with ESMTPSA id di5sm759152pbc.36.2015.02.08.08.51.44 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 08 Feb 2015 08:51:46 -0800 (PST) From: Ard Biesheuvel To: edk2-devel@lists.sourceforge.net, lersek@redhat.com, olivier.martin@arm.com, roy.franz@linaro.org, leif.lindholm@linaro.org, jordan.l.justen@intel.com, feng.tian@intel.com Date: Mon, 9 Feb 2015 00:51:14 +0800 Message-Id: <1423414278-8455-3-git-send-email-ard.biesheuvel@linaro.org> X-Mailer: git-send-email 1.8.3.2 In-Reply-To: <1423414278-8455-1-git-send-email-ard.biesheuvel@linaro.org> References: <1423414278-8455-1-git-send-email-ard.biesheuvel@linaro.org> X-Spam-Score: -1.5 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1YKV5M-0006rt-Ib Subject: [edk2] [PATCH 2/6] MdeModulePkg: improve scalability of memory pools X-BeenThere: edk2-devel@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list Reply-To: edk2-devel@lists.sourceforge.net List-Id: List-Unsubscribe: , List-Archive: List-Post: , List-Help: , List-Subscribe: , MIME-Version: 1.0 Errors-To: edk2-devel-bounces@lists.sourceforge.net X-Removed-Original-Auth: Dkim didn't pass. X-Original-Sender: ard.biesheuvel@linaro.org X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.215.53 as permitted sender) smtp.mail=patch+caf_=patchwork-forward=linaro.org@linaro.org Mailing-list: list patchwork-forward@linaro.org; contact patchwork-forward+owners@linaro.org X-Google-Group-Id: 836684582541 The existing linear mapping between allocation size and pool index does not scale when moving to a 64 KB granularity or beyond. With a granularity of 64 KB, 2048 (!) bins will be created for each memory type, each differing 32 bytes in size with the next one. Instead, introduce an exponential scheme where each bin size is the sum of the two previous ones. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Ard Biesheuvel --- MdeModulePkg/Core/Dxe/Mem/Pool.c | 36 ++++++++++++++++++++++++++++-------- 1 file changed, 28 insertions(+), 8 deletions(-) diff --git a/MdeModulePkg/Core/Dxe/Mem/Pool.c b/MdeModulePkg/Core/Dxe/Mem/Pool.c index f99293da5c51..c7998e80cce6 100644 --- a/MdeModulePkg/Core/Dxe/Mem/Pool.c +++ b/MdeModulePkg/Core/Dxe/Mem/Pool.c @@ -41,19 +41,24 @@ typedef struct { UINTN Size; } POOL_TAIL; - -#define POOL_SHIFT 7 - #define POOL_OVERHEAD (SIZE_OF_POOL_HEAD + sizeof(POOL_TAIL)) #define HEAD_TO_TAIL(a) \ ((POOL_TAIL *) (((CHAR8 *) (a)) + (a)->Size - sizeof(POOL_TAIL))); +// +// Each element is the sum of the 2 previous ones: this allows us to migrate +// blocks between bins by splitting them up, while not wasting too much memory +// as we would in a strict power-of-2 sequence +// +STATIC CONST UINT16 mPoolSizeTable[] = { + 64, 128, 192, 320, 512, 832, 1344, 2176, 3520, 5696, 9216, 14912, 24128 +}; -#define SIZE_TO_LIST(a) ((a) >> POOL_SHIFT) -#define LIST_TO_SIZE(a) ((a+1) << POOL_SHIFT) +#define SIZE_TO_LIST(a) (GetPoolIndexFromSize (a)) +#define LIST_TO_SIZE(a) (mPoolSizeTable [a]) -#define MAX_POOL_LIST SIZE_TO_LIST(DEFAULT_PAGE_ALLOCATION) +#define MAX_POOL_LIST (sizeof (mPoolSizeTable) / sizeof (mPoolSizeTable[0])) #define MAX_POOL_SIZE (MAX_ADDRESS - POOL_OVERHEAD) @@ -80,6 +85,21 @@ POOL mPoolHead[EfiMaxMemoryType]; // LIST_ENTRY mPoolHeadList = INITIALIZE_LIST_HEAD_VARIABLE (mPoolHeadList); +STATIC +UINTN +GetPoolIndexFromSize ( + UINTN Size + ) +{ + UINTN Index; + + for (Index = 0; Index < MAX_POOL_LIST; Index++) { + if (mPoolSizeTable [Index] >= Size) { + return Index; + } + } + return MAX_POOL_LIST; +} /** Called to initialize the pool. @@ -311,7 +331,7 @@ CoreAllocatePoolI ( // If allocation is over max size, just allocate pages for the request // (slow) // - if (Index >= MAX_POOL_LIST) { + if (Index >= SIZE_TO_LIST (Granularity)) { NoPages = EFI_SIZE_TO_PAGES(Size) + EFI_SIZE_TO_PAGES (Granularity) - 1; NoPages &= ~(UINTN)(EFI_SIZE_TO_PAGES (Granularity) - 1); Head = CoreAllocatePoolPages (PoolType, NoPages, Granularity); @@ -539,7 +559,7 @@ CoreFreePoolI ( // // If it's not on the list, it must be pool pages // - if (Index >= MAX_POOL_LIST) { + if (Index >= SIZE_TO_LIST (Granularity)) { // // Return the memory pages back to free memory