From patchwork Sun Feb 8 16:51:17 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ard Biesheuvel X-Patchwork-Id: 44507 Return-Path: X-Original-To: linaro@patches.linaro.org Delivered-To: linaro@patches.linaro.org Received: from mail-we0-f199.google.com (mail-we0-f199.google.com [74.125.82.199]) by ip-10-151-82-157.ec2.internal (Postfix) with ESMTPS id 4B1B52154B for ; Sun, 8 Feb 2015 16:52:21 +0000 (UTC) Received: by mail-we0-f199.google.com with SMTP id k11sf13270528wes.2 for ; Sun, 08 Feb 2015 08:52:20 -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=7pbmAD0TMgm2/0Lr6HusT5DTl2uIlfNcXErGSmfC4N0=; b=cXpwH9zfWnO6o46zQgMkcDABw3sZn/ZdqmqhMUK867YpdfFVZZJHWMq3+N8t079BGE gW1myId73KRxHuMxtHcNq2ukXRGTiEqp7FJGac9xceN1f2F2As5o8LR7EFA9wc36vUj1 7KdYRs2r0C6FEHn336eqwlGbDr01qaZNdBiBvHenM4JaE/AaNiEMuISwUwVEek+8ehmY sZIy/FWu85X4gr+lpVvf/1nRTcKfzi994w+NW4A3eg0RQUgzpgLXkYnw6rdCb2zt/MUW AOjacVe4pMGrvx+wvXqNA5g0b4UHzVOAngDHSU6XnCAuQsUwDlHrIZF2bRHk8g/RkIbl lV8A== X-Gm-Message-State: ALoCoQl+w3dVxLIHgrwCWImkLENYBFIG9J5RqbqcflDO2h+Gcn48pCPnalnpyjhUnbl1l3r8Pu5u X-Received: by 10.152.87.15 with SMTP id t15mr1446542laz.9.1423414340556; Sun, 08 Feb 2015 08:52:20 -0800 (PST) X-BeenThere: patchwork-forward@linaro.org Received: by 10.152.182.135 with SMTP id ee7ls4284lac.93.gmail; Sun, 08 Feb 2015 08:52:20 -0800 (PST) X-Received: by 10.112.92.204 with SMTP id co12mr12592967lbb.43.1423414340277; Sun, 08 Feb 2015 08:52:20 -0800 (PST) Received: from mail-lb0-f170.google.com (mail-lb0-f170.google.com. [209.85.217.170]) by mx.google.com with ESMTPS id a3si6920403lah.98.2015.02.08.08.52.20 for (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 08 Feb 2015 08:52:20 -0800 (PST) Received-SPF: pass (google.com: domain of patch+caf_=patchwork-forward=linaro.org@linaro.org designates 209.85.217.170 as permitted sender) client-ip=209.85.217.170; Received: by mail-lb0-f170.google.com with SMTP id u14so1672606lbd.1 for ; Sun, 08 Feb 2015 08:52:20 -0800 (PST) X-Received: by 10.152.28.227 with SMTP id e3mr12427410lah.117.1423414340187; Sun, 08 Feb 2015 08:52:20 -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 h5csp2925339lbj; Sun, 8 Feb 2015 08:52:19 -0800 (PST) X-Received: by 10.50.36.103 with SMTP id p7mr12763009igj.20.1423414338380; Sun, 08 Feb 2015 08:52:18 -0800 (PST) Received: from lists.sourceforge.net (lists.sourceforge.net. [216.34.181.88]) by mx.google.com with ESMTPS id n197si6017993ion.33.2015.02.08.08.52.17 (version=TLSv1 cipher=RC4-SHA bits=128/128); Sun, 08 Feb 2015 08:52:18 -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 1YKV5Y-0003dE-OG; Sun, 08 Feb 2015 16:52:04 +0000 Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YKV5W-0003cr-Jp for edk2-devel@lists.sourceforge.net; Sun, 08 Feb 2015 16:52:02 +0000 Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of linaro.org designates 209.85.220.41 as permitted sender) client-ip=209.85.220.41; envelope-from=ard.biesheuvel@linaro.org; helo=mail-pa0-f41.google.com; Received: from mail-pa0-f41.google.com ([209.85.220.41]) by sog-mx-1.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1YKV5V-0002HQ-LK for edk2-devel@lists.sourceforge.net; Sun, 08 Feb 2015 16:52:02 +0000 Received: by mail-pa0-f41.google.com with SMTP id kx10so4136594pab.0 for ; Sun, 08 Feb 2015 08:51:56 -0800 (PST) X-Received: by 10.70.100.73 with SMTP id ew9mr22042441pdb.95.1423414315950; Sun, 08 Feb 2015 08:51:55 -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.52 (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 08 Feb 2015 08:51:55 -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:17 +0800 Message-Id: <1423414278-8455-6-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: 1YKV5V-0002HQ-LK Subject: [edk2] [PATCH 5/6] MdeModulePkg: serve allocations from higher-up bins if current bin is empty 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.217.170 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 This patch changes the allocation logic for the pool allocator to only allocate additional pages if the requested allocation cannot be fulfilled from the current bin or any of the larger ones. If there are larger blocks available, they will be used to serve the allocation, and the remainder will be carved up into smaller blocks using the existing carving up logic. Note that all pool sizes are a multiple of the smallest pool size, so it is guaranteed that the remainder will be carved up without spilling. Due to the exponential nature of the pool sizes, the amount of work is logarithmic in the size of the available block. Contributed-under: TianoCore Contribution Agreement 1.0 Signed-off-by: Ard Biesheuvel --- MdeModulePkg/Core/Dxe/Mem/Pool.c | 29 ++++++++++++++++++++++------- 1 file changed, 22 insertions(+), 7 deletions(-) diff --git a/MdeModulePkg/Core/Dxe/Mem/Pool.c b/MdeModulePkg/Core/Dxe/Mem/Pool.c index 23409d35c428..fd9f065dafa2 100644 --- a/MdeModulePkg/Core/Dxe/Mem/Pool.c +++ b/MdeModulePkg/Core/Dxe/Mem/Pool.c @@ -292,7 +292,7 @@ CoreAllocatePoolI ( VOID *Buffer; UINTN Index; UINTN FSize; - UINTN Offset; + UINTN Offset, MaxOffset; UINTN NoPages; UINTN Granularity; @@ -343,6 +343,22 @@ CoreAllocatePoolI ( // if (IsListEmpty (&Pool->FreeList[Index])) { + Offset = LIST_TO_SIZE (Index); + MaxOffset = Granularity; + + // + // Check the bins holding larger blocks, and carve one up if needed + // + while (++Index < SIZE_TO_LIST (Granularity)) { + if (!IsListEmpty (&Pool->FreeList[Index])) { + Free = CR (Pool->FreeList[Index].ForwardLink, POOL_FREE, Link, POOL_FREE_SIGNATURE); + RemoveEntryList (&Free->Link); + NewPage = (VOID *) Free; + MaxOffset = LIST_TO_SIZE (Index); + goto Carve; + } + } + // // Get another page // @@ -354,29 +370,28 @@ CoreAllocatePoolI ( // // Serve the allocation request from the head of the allocated block // +Carve: Head = (POOL_HEAD *) NewPage; - Offset = LIST_TO_SIZE (Index); // // Carve up remaining space into free pool blocks // - Index = SIZE_TO_LIST (Granularity) - 1; - while (Offset < Granularity) { + Index--; + while (Offset < MaxOffset) { ASSERT (Index < MAX_POOL_LIST); FSize = LIST_TO_SIZE(Index); - while (Offset + FSize <= Granularity) { + while (Offset + FSize <= MaxOffset) { Free = (POOL_FREE *) &NewPage[Offset]; Free->Signature = POOL_FREE_SIGNATURE; Free->Index = (UINT32)Index; InsertHeadList (&Pool->FreeList[Index], &Free->Link); Offset += FSize; } - Index -= 1; } - ASSERT (Offset == Granularity); + ASSERT (Offset == MaxOffset); goto Done; }