<br><br><div class="gmail_quote">On Wed, Dec 3, 2008 at 7:46 AM, Myles Watson <span dir="ltr"><<a href="mailto:mylesgw@gmail.com">mylesgw@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d"><br>
<br>
> -----Original Message-----<br>
> From: Marc Jones [mailto:<a href="mailto:marcj303@gmail.com">marcj303@gmail.com</a>]<br>
> Sent: Tuesday, December 02, 2008 7:52 PM<br>
> To: Myles Watson<br>
</div><div><div></div><div class="Wj3C7c">> Cc: ron minnich; Rudolf Marek; Coreboot<br>
> Subject: Re: [coreboot] Resource Allocation discussion<br>
><br>
> On Tue, Dec 2, 2008 at 3:23 PM, Myles Watson <<a href="mailto:mylesgw@gmail.com">mylesgw@gmail.com</a>> wrote:<br>
> ><br>
> ><br>
> >> -----Original Message-----<br>
> >> From: ron minnich [mailto:<a href="mailto:rminnich@gmail.com">rminnich@gmail.com</a>]<br>
> >> Sent: Tuesday, December 02, 2008 2:51 PM<br>
> >> To: Myles Watson<br>
> >> Cc: Marc Jones; Rudolf Marek; Coreboot<br>
> >> Subject: Re: [coreboot] Resource Allocation discussion<br>
> >><br>
> >> On Tue, Dec 2, 2008 at 11:33 AM, Myles Watson <<a href="mailto:mylesgw@gmail.com">mylesgw@gmail.com</a>><br>
> wrote:<br>
> >><br>
> >> > Do we want to take fixed resources into account in the allocator?<br>
> >><br>
> >> I would think so.<br>
> ><br>
> > I would too, but v2 didn't and did pretty well. I'm interested to see<br>
> an<br>
> > idea for the resource allocation algorithm that allocates from largest<br>
> to<br>
> > smallest resource, except when it's skipping fixed resources.<br>
> ><br>
> > I think it's doable, but nothing like what we have.<br>
><br>
> That surprises me. I thought it does, which is how/why you can get rid<br>
> of DEVICE_MEM_HIGH. Otherwise you would clobber the ROM and the APIC.<br>
<br>
</div></div>You're right. I think it's broken. That's why right now I'm setting the<br>
base to 0xfc000000 manually. Thanks for pointing it out.<br>
<br>
I'd assumed that resource_max took fixed resources into account, but it<br>
doesn't. All resource_max does is align the resource based on its limit.<br>
<br>
So maybe we need to traverse the tree looking for fixed spaces, and<br>
constrain the domain's resource limit and base. That wouldn't be too hard.<br>
What I was saying would be hard is interleaving fixed resources with movable<br>
resources. In other words, if we put the VGA ROM between the two APIC<br>
allocations to save space. I think that's too ugly.<br>
<br>
I'll add a traversal to the tree that doesn't ignore fixed resources.<font color="#888888"><br>
</font></blockquote></div><br>A question before the code:<br>1. Can anyone enumerate all the fixed resources that should be included in QEMU?<br>Currently I have:<br>- DRAM (first 640K and 0xc0000-TOP-768K) Is this necessary?<br>
- I/O first 0x400 in southbridge<br>- VGA 0xa0000-0xc0000<br>- APIC at 0xfec00000 and 0xfee00000<br>- ROM at 0xfff80000<br><br>Side note: Only the lowest and highest fixed addresses matter in my code. The others get ignored. I think it's too much pain to try to interleave them to use the space between 0xfee00000 and 0xfff80000, for example.<br>
<br>All right. I've added code that traverses each domain looking for fixed resources. Here's the pseudo code:<br><br>For each domain:<br> call avoid_fixed_resources(domain_dev)<br><br>avoid_fixed_resources(dev)<br>
initialize limits to maximum size<br> initialize the limits to dev's resources limits<br> call constrain_resources(dev, limits)<br> update dev's resources<br><br>constrain_resources(dev, limits)<br>
for each child<br> call constrain_resources(child, limits)<br> for each fixed resource<br> if limits contain resource<br> update limits to exclude resource (largest space possible)<br>
<br>And here's the code. It's not a diff because it's all new.<br>struct constraints {<br> struct resource pref, io, mem;<br>};<br><br>static void constrain_resources(struct device *dev, struct constraints* limits)<br>
{<br> struct device *child;<br> struct resource *res;<br> struct resource *lim;<br> int i;<br><br>#ifdef CONFIG_PCI_64BIT_PREF_MEM<br> #define MEM_MASK (IORESOURCE_PREFETCH | IORESOURCE_MEM)<br>#else<br> #define MEM_MASK (IORESOURCE_MEM)<br>
#endif<br>#define IO_MASK (IORESOURCE_IO)<br>#define PREF_TYPE (IORESOURCE_PREFETCH | IORESOURCE_MEM)<br>#define MEM_TYPE (IORESOURCE_MEM)<br>#define IO_TYPE (IORESOURCE_IO)<br><br> /* Descend into every child and look for fixed resources. */<br>
for (child=dev->link[0].children; child; child = child->sibling) {<br> constrain_resources(child, limits);<br> for (i = 0; i<child->resources; i++) {<br> res = &child->resource[i];<br>
if (!(res->flags & IORESOURCE_FIXED))<br> continue;<br> /* Choose larger space: above or below fixed resources. */<br><br> /* PREFETCH */<br> if ((res->flags & MEM_MASK) == PREF_TYPE) {<br>
lim = &limits->pref;<br> /* Is it already outside the limits? */<br> if ((res->base + res->size -1) < lim->base ||<br> res->base > lim->limit)<br>
continue;<br> /* Is the space above larger? */<br> if ((lim->limit - (res->base + res->size -1)) ><br> (res->base - lim->base))<br> lim->base = res->base + res->size;<br>
else<br> lim->limit = res->base -1;<br> }<br><br> /* MEM */<br> if ((res->flags & MEM_MASK) == MEM_TYPE) {<br> lim = &limits->mem;<br>
/* Is it already outside the limits? */<br> if ((res->base + res->size -1) < lim->base ||<br> res->base > lim->limit)<br> continue;<br>
/* Is the space above larger? */<br> if ((lim->limit - (res->base + res->size -1)) ><br> (res->base - lim->base))<br> lim->base = res->base + res->size;<br>
else<br> lim->limit = res->base -1;<br> }<br><br> /* I/O */<br> if ((res->flags & IO_MASK) == IO_TYPE) {<br> lim = &limits->io;<br>
/* Is it already outside the limits? */<br> if ((res->base + res->size -1) < lim->base ||<br> res->base > lim->limit)<br> continue;<br>
/* Is the space above larger? */<br> if ((lim->limit - (res->base + res->size -1)) ><br> (res->base - lim->base))<br> lim->base = res->base + res->size;<br>
else<br> lim->limit = res->base -1;<br> }<br> }<br> }<br>}<br><br>static void avoid_fixed_resources(struct device *dev)<br>{<br> struct constraints limits;<br>
struct resource *res;<br> int i;<br><br> /* Initialize constraints to maximum size. */<br><br> limits.pref.base = 0;<br> limits.pref.limit = 0xfffffffffffffffULL;<br> limits.io.base = 0;<br> limits.io.limit = 0xfffffffffffffffULL;<br>
limits.mem.base = 0;<br> limits.mem.limit = 0xfffffffffffffffULL;<br><br> /* Initialize the limits from the device's resources. */<br> for (i = 0; i<dev->resources; i++) {<br> res = &dev->resource[i];<br>
<br> /* PREFETCH */<br> if ((res->flags & MEM_MASK) == PREF_TYPE &&<br> res->limit < limits.pref.limit )<br> limits.pref.limit = res->limit;<br> /* MEM */<br>
if ((res->flags & MEM_MASK) == MEM_TYPE &&<br> res->limit < limits.mem.limit )<br> limits.mem.limit = res->limit;<br> /* I/O */<br> if ((res->flags & IO_MASK) == IO_TYPE &&<br>
res->limit < limits.io.limit )<br> limits.io.limit = res->limit;<br> }<br><br> constrain_resources(dev, &limits);<br><br> for (i = 0; i<dev->resources; i++) {<br> res = &dev->resource[i];<br>
/* Update the device's resources with new limits. */<br><br> /* PREFETCH */<br> if ((res->flags & MEM_MASK) == PREF_TYPE) {<br> /* Is the resource outside the limits? */<br> if ( limits.pref.base > res->base )<br>
res->base = limits.pref.base;<br> if ( res->limit > limits.pref.limit )<br> res->limit = limits.pref.limit;<br> }<br><br> /* MEM */<br> if ((res->flags & MEM_MASK) == MEM_TYPE) {<br>
/* Is the resource outside the limits? */<br> if ( limits.mem.base > res->base )<br> res->base = limits.mem.base;<br> if ( res->limit > limits.mem.limit )<br>
res->limit = limits.mem.limit;<br> }<br><br> /* I/O */<br> if ((res->flags & IO_MASK) == IO_TYPE) {<br> /* Is the resource outside the limits? */<br> if ( limits.io.base > res->base )<br>
res->base = limits.io.base;<br> if ( res->limit > limits.io.limit )<br> res->limit = limits.io.limit;<br> }<br> }<br>}<br><br>Thanks,<br>Myles<br><br> <br>