On Friday, November 05, 2010 09:52:55 am Linus Torvalds wrote:
> Hmm.. This resource comparison logic doesn't really appear to make any
> sense if the resources can overlap.
>
> And the fact that the resources can be identical implies that they can
> overlap...
The resource tree doesn't support overlapping resources at the same
level, so in general we avoid that. There's a bug [1] and a patch [2]
for PCI host bridge windows from _CRS that overlap (the patch coalesces
them to avoid the overlap).
The overlap case Borislav tripped over [3] is a subtractive-decode bridge
where a positive decode region from the base/limit registers happens
to be identical to one of the subtractively-decoded regions:
pci_root PNP0A08:00: host bridge window [mem 0xd0000000-0xd7ffffff]
pci 0000:00:14.4: bridge window [mem 0xd0000000-0xd7ffffff pref]
pci 0000:00:14.4: bridge window [mem 0xd0000000-0xd7ffffff] (subtractive decode)
In this case, they do overlap, but we don't put the subtractive decode
regions in the resource tree; we only use them in this PCI bus allocation
code.
> On Thu, Nov 4, 2010 at 7:36 PM, Bjorn Helgaas <bjorn.helgaas@xxxxxx> wrote:
> >
> > +static int resource_compare(struct resource *res1, struct resource *res2)
> > +{
> > + if (res1->end < res2->end)
> > + return -1;
> > +
> > + if (res1->end > res2->end)
> > + return 1;
> > +
> > + if (res1->start < res2->start)
> > + return -1;
> > +
> > + if (res1->start > res2->start)
> > + return 1;
>
> So think about the (non-exact) overlap case, and imagine that resource
> A has the same end as resource B. IOW, B is completely contained
> within A. What happens?
>
> Now, we return -1 if A starts before B.
>
> But now imagine having a slightly larger A, so that the end of A is
> larger than the end of B. It's a very similar situation to above: B is
> completely contained within A, and A clearly starts before B does (and
> and doesn't end before). But we return the _opposite_ comparison
> result: we would return 1.
>
> That makes no sense to me. In both cases, A completely contained B,
> and A was clearly "before" B in the resource hierarchy. And we
> returned different values.
>
> So what does the return value of "resource_compare()" actually _mean_
> from a semantic standpoint? It doesn't sound like it has a really
> valid meaning.
>
> Maybe the function is fine and everything works, but I'd really like
> for it to have some kind of semantic meaning, or explanation for why
> it compares things the way it does.
>
> I realize that with ranges, there may not _be_ any full ordering, but
> I suspect we have some constraints (like perhaps "there is no
> _partial_ overlap of ranges") that makes it possible to give it a
> well-defined semantic meaning.
>
> So maybe just a comment on why it does what it does.
>
> (But to make me happy, you could also say: if the end is the same,
> then an earlier start means that we consider the end to be _later_,
> because it means that the resource completely overlaps the other, and
> thus even though they have the same end, the end of the resource with
> the earlier start is "after" the resource with a later start. Do you
> see what I'm incoherently trying to say? So switching the -1/1 returns
> for the 'start' compare around would satisfy my "that makes no sense"
> comment)
My original intent was to prefer the resource containing a higher
address, then (if A & B had the same end) prefer the one with a higher
"center of gravity," i.e., the smaller one. Does that picture help?
One reason is that this sort of overlap probably involves a positive
decode region and a subtractive decode one, and it seems better to
prefer the positive decode one, which should be the smaller.
Assuming we really *do* want to prefer positive decode regions (and
I have no idea what Windows does here), I think it'd be better to do
that explicitly rather than relying on a size difference. I'll post
an updated patch for Borislav to test and you can see what you think.
Bjorn
[1] https://bugzilla.kernel.org/show_bug.cgi?id=17011#c7
[2] https://patchwork.kernel.org/patch/199952/
[3] https://bugzilla.kernel.org/show_bug.cgi?id=22062
--
To unsubscribe from this list: send the line "unsubscribe linux-pci" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
