From patchwork Fri Dec 11 05:06:50 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yinghai Lu X-Patchwork-Id: 7824751 X-Patchwork-Delegate: bhelgaas@google.com Return-Path: X-Original-To: patchwork-linux-pci@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 495FA9F1C2 for ; Fri, 11 Dec 2015 05:12:01 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 3F38B20570 for ; Fri, 11 Dec 2015 05:11:59 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 1011D20524 for ; Fri, 11 Dec 2015 05:11:58 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752760AbbLKFK2 (ORCPT ); Fri, 11 Dec 2015 00:10:28 -0500 Received: from aserp1040.oracle.com ([141.146.126.69]:47441 "EHLO aserp1040.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754360AbbLKFKW (ORCPT ); Fri, 11 Dec 2015 00:10:22 -0500 Received: from userv0022.oracle.com (userv0022.oracle.com [156.151.31.74]) by aserp1040.oracle.com (Sentrion-MTA-4.3.2/Sentrion-MTA-4.3.2) with ESMTP id tBB586BT007756 (version=TLSv1 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK); Fri, 11 Dec 2015 05:08:07 GMT Received: from userv0122.oracle.com (userv0122.oracle.com [156.151.31.75]) by userv0022.oracle.com (8.13.8/8.13.8) with ESMTP id tBB586oa007021 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL); Fri, 11 Dec 2015 05:08:06 GMT Received: from abhmp0011.oracle.com (abhmp0011.oracle.com [141.146.116.17]) by userv0122.oracle.com (8.13.8/8.13.8) with ESMTP id tBB586j5032565; Fri, 11 Dec 2015 05:08:06 GMT Received: from linux-siqj.site (/69.181.250.163) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Thu, 10 Dec 2015 21:08:06 -0800 From: Yinghai Lu To: Bjorn Helgaas , David Miller , Benjamin Herrenschmidt , Wei Yang , TJ , Yijing Wang , Khalid Aziz Cc: linux-pci@vger.kernel.org, linux-kernel@vger.kernel.org, Yinghai Lu Subject: [PATCH v9 54/60] resources: Make allocate_resource() return best fit resource Date: Thu, 10 Dec 2015 21:06:50 -0800 Message-Id: <1449810416-2950-55-git-send-email-yinghai@kernel.org> X-Mailer: git-send-email 1.8.4.5 In-Reply-To: <1449810416-2950-1-git-send-email-yinghai@kernel.org> References: <1449810416-2950-1-git-send-email-yinghai@kernel.org> X-Source-IP: userv0022.oracle.com [156.151.31.74] Sender: linux-pci-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-pci@vger.kernel.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Current code just allocate from first avail window. We can find all suitable empty slots and pick one with smallest size, so we could save the big slot for needed ones later when we have several pci bridges under parent bridge and some bridges get assigned from bios and we need to assign others in kernel. For examples: we have window [0xc0000000, 0xd0000000), and [0xe0000000,0xe1000000) and we try allocate 0x200000 size resource. in this patch will reserve [0xc0000000, 0xd0000000) and [0xe0000000,0xe1000000) at first, then pick [0xe0000000,0xe1000000) to allocate 0x200000 size. -v2: updated after __allocate_resource change, and add field in constraint instead of passing it directly. -v3: Use best fit instead of just fit according to Bjorn. Signed-off-by: Yinghai Lu --- kernel/resource.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 68 insertions(+), 13 deletions(-) diff --git a/kernel/resource.c b/kernel/resource.c index 62321b0..c468875 100644 --- a/kernel/resource.c +++ b/kernel/resource.c @@ -48,6 +48,7 @@ struct resource_constraint { resource_size_t (*alignf)(void *, const struct resource *, resource_size_t, resource_size_t); void *alignf_data; + bool fit; }; static DEFINE_RWLOCK(resource_lock); @@ -589,12 +590,15 @@ static void resource_clip(struct resource *res, resource_size_t min, * alignment constraints */ static int __find_resource(struct resource *root, struct resource *old, - struct resource *new, + struct resource *new, struct resource *avail, resource_size_t size, struct resource_constraint *constraint) { struct resource *this = root->child; - struct resource tmp = *new, avail, alloc; + struct resource tmp = *new, availx, alloc; + + if (!avail || avail == new) + avail = &availx; tmp.start = root->start; /* @@ -618,15 +622,16 @@ static int __find_resource(struct resource *root, struct resource *old, arch_remove_reservations(&tmp); /* Check for overflow after ALIGN() */ - avail.start = ALIGN(tmp.start, constraint->align); - avail.end = tmp.end; - avail.flags = new->flags & ~IORESOURCE_UNSET; - if (avail.start >= tmp.start) { - alloc.flags = avail.flags; - alloc.start = constraint->alignf(constraint->alignf_data, &avail, + avail->start = ALIGN(tmp.start, constraint->align); + avail->end = tmp.end; + avail->flags = new->flags & ~IORESOURCE_UNSET; + if (avail->start >= tmp.start) { + alloc.flags = avail->flags; + alloc.start = constraint->alignf( + constraint->alignf_data, avail, size, constraint->align); alloc.end = alloc.start + size - 1; - if (resource_contains(&avail, &alloc)) { + if (resource_contains(avail, &alloc)) { new->start = alloc.start; new->end = alloc.end; return 0; @@ -643,6 +648,11 @@ next: if (!this || this->end == root->end) return -EBUSY; } +struct good_resource { + struct list_head list; + struct resource avail; + struct resource new; +}; /* * Find empty slot in the resource tree given range and alignment. */ @@ -650,7 +660,49 @@ static int find_resource(struct resource *root, struct resource *new, resource_size_t size, struct resource_constraint *constraint) { - return __find_resource(root, NULL, new, size, constraint); + int ret = -1; + LIST_HEAD(head); + struct good_resource *good, *tmp; + resource_size_t avail_size = (resource_size_t)-1ULL; + + if (!constraint->fit) + return __find_resource(root, NULL, new, NULL, size, + constraint); + + /* find all suitable ones and add to the list */ + for (;;) { + good = kzalloc(sizeof(*good), GFP_KERNEL); + if (!good) + break; + + good->new.start = new->start; + good->new.end = new->end; + good->new.flags = new->flags; + ret = __find_resource(root, NULL, &good->new, &good->avail, + size, constraint); + if (ret || __request_resource(root, &good->avail)) { + ret = -EBUSY; + kfree(good); + break; + } + + list_add(&good->list, &head); + } + + /* pick up the smallest one and delete the list */ + list_for_each_entry_safe(good, tmp, &head, list) { + if (resource_size(&good->avail) < avail_size) { + avail_size = resource_size(&good->avail); + new->start = good->new.start; + new->end = good->new.end; + ret = 0; + } + list_del(&good->list); + __release_resource(&good->avail); + kfree(good); + } + + return ret; } /** @@ -671,7 +723,8 @@ static int __reallocate_resource(struct resource *root, struct resource *old, struct resource new = *old; struct resource *conflict; - if ((err = __find_resource(root, old, &new, newsize, constraint))) + err = __find_resource(root, old, &new, NULL, newsize, constraint); + if (err) goto out; if (resource_contains(&new, old)) { @@ -710,6 +763,7 @@ out: * @align: alignment requested, in bytes * @alignf: alignment function, optional, called if not NULL * @alignf_data: arbitrary data to pass to the @alignf function + * @fit: only allocate fit range. * * Caller need to hold resource_lock if needed. */ @@ -720,7 +774,7 @@ static int __allocate_resource(struct resource *root, struct resource *new, const struct resource *, resource_size_t, resource_size_t), - void *alignf_data) + void *alignf_data, bool fit) { int err; struct resource_constraint constraint; @@ -733,6 +787,7 @@ static int __allocate_resource(struct resource *root, struct resource *new, constraint.align = align; constraint.alignf = alignf; constraint.alignf_data = alignf_data; + constraint.fit = fit; if (new->parent) { /* resource is already allocated, try reallocating with @@ -773,7 +828,7 @@ int allocate_resource(struct resource *root, struct resource *new, write_lock(&resource_lock); ret = __allocate_resource(root, new, size, min, max, align, - alignf, alignf_data); + alignf, alignf_data, true); write_unlock(&resource_lock); return ret;