On 17/02/14 10:11, Kieran Devlin wrote:
the original implementation use identical logic for both ‘high’ & ‘low’,
which will cause ‘high’ & ‘low’ end up at same RB-tree node, instead of an
expected interval.
and finally, break ‘for’ loop logic
luckily all these conditions never meet in practice.
Hmm, it may hit when you have a device that requires 2-4GB memory in a
0-4GB memory range, which is not entirely unlikely... (just to give an
example).
On Feb 17, 2014, at 5:14 PM, Mike Larkin <mlar...@azathoth.net> wrote:
Probably get a better response if you explained what this diff does
and/or fixes…
I have to agree with Mike here. As someone who is rather familiar with
the code, I still required a fair amount of time to figure out what the
original code is doing and how the diff affects it.
Remember that not every developer is as familiar with the code as you
are. :)
i just think this bug is a little too obvious
Most bugs are, once you find them. Until that happens, they look
perfectly valid. I think the original body of code took something like
30+ revisions...
Anyway, to respond to the question that Mike asked:
--- Intended behaviour ---
The function in question, essentially looks for a page satisfying the
request condition:
[1] it must intersect with [low_addr - high_addr]
[2] it must be of a given memory type
It will return a pointer to any (arbitrary) range satisfying these
conditions.
The implementation is based on lower-bound and upper-bound lookup in a
tree. It first clamps the range such that the upper (high) and lower
(low) bounds are at or around [1] (i.e. traversing low - high would
cover the entirety of [1]).
As an optimization, if it finds a range that already satisfies the
request, it quickly returns it (this is why the loops contain return
statements).
As the last step, it traverses the entire range O(n log n) of pages in
the range low-high, returning the first match.
--- The fix ---
Kieran correctly notes that the code does the lower bound lookup is
incorrect. Instead of walking downward, it walks upward, essentially
performing the same traversal as the loop above (for variable 'high')
and ending up at the same position.
The final loop therefore traverses an empty range. Instead of using
RB_RIGHT, RB_LEFT should be used to select ever lower addresses, up to
falling out of the range.
--- Additional thoughts ---
I doubt that function actually does what it says in the comment, after
the fix is applied. I would recommend checking the logic in the last
loop as well, since from reading it back, I think it may still exhibit
false negatives. I doubt it will trigger false positives though.
--
Ariane
