Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751488AbbHREVn (ORCPT ); Tue, 18 Aug 2015 00:21:43 -0400 Received: from mail-pa0-f44.google.com ([209.85.220.44]:34439 "EHLO mail-pa0-f44.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750734AbbHREVl (ORCPT ); Tue, 18 Aug 2015 00:21:41 -0400 Date: Mon, 17 Aug 2015 23:21:35 -0500 From: Bjorn Helgaas To: Yinghai Lu Cc: David Miller , Benjamin Herrenschmidt , Wei Yang , TJ , Yijing Wang , Andrew Morton , linux-pci@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH v3 33/51] resources: Make allocate_resource return just fit resource Message-ID: <20150818042135.GZ26431@google.com> References: <1438039809-24957-1-git-send-email-yinghai@kernel.org> <1438039809-24957-34-git-send-email-yinghai@kernel.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1438039809-24957-34-git-send-email-yinghai@kernel.org> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 6513 Lines: 190 On Mon, Jul 27, 2015 at 04:29:51PM -0700, Yinghai Lu wrote: > Find all suitable empty slots and pick one just fit, so we could save > the big slot for needed ones later when we have several pcie switches > and some bridges get assigned bios and we need to assign others in kernel. By "just fit," do you mean "best fit"? "Best fit" is a well-known term, so if that's what you mean, let's use it. I couldn't quite parse the PCIe switch stuff here. How is that relevant to this change? > 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 67b58a5..697b8ca 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); > @@ -554,12 +555,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; > /* > @@ -583,15 +587,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; > @@ -608,6 +613,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. > */ > @@ -615,7 +625,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); > + } Allocating memory and building a list in a function that allocates space seems like a little bit of a hack. I think we're holding resource_lock anyway; can't we just find a candidate, reserve it, look for another one, reserve it, release the larger one, and repeat? > + /* 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; > } > > /** > @@ -636,7 +688,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)) { > @@ -675,6 +728,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. > */ > @@ -685,7 +739,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; > @@ -698,6 +752,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 > @@ -738,7 +793,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; > -- > 1.8.4.5 > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/