| Message ID | 1438039809-24957-34-git-send-email-yinghai@kernel.org |
|---|---|
| State | Superseded |
| Headers | show |
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 <yinghai@kernel.org> > --- > 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-pci" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Aug 17, 2015 at 9:21 PM, Bjorn Helgaas <bhelgaas@google.com> wrote: > 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. Sure. Thanks for dig that URL out. > > I couldn't quite parse the PCIe switch stuff here. How is that relevant to > this change? That is most use cases. One parent have several child bridges, and BIOS does poor jobs and only resources to some child bridges. Kernel need to assign for others. so before kernel start, parent resource window already have several blank slots instead of one big chunk. then we need to make sure first come only take best fit and leave big one for possible late comer. > > 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? We need to reserve the all avail windows before pick up one window. for examples: we have window [0xc0000000, 0xd0000000), and [0xe0000000,0xe1000000) and we try allocate 0x200000 size resources. in this patch will reserve [0xc0000000, 0xd0000000) and [0xe0000000,0xe1000000) at first, then pick [0xe0000000,0xe1000000) -- To unsubscribe from this list: send the line "unsubscribe linux-pci" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
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); + } + + /* 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;
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. Signed-off-by: Yinghai Lu <yinghai@kernel.org> --- kernel/resource.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 68 insertions(+), 13 deletions(-)