Re: trivial fix for pmemrange
Applied, thanks for spotting the issue, and sorry for the delay. Miod > Index: uvm/uvm_pmemrange.c > === > RCS file: /cvs/src/sys/uvm/uvm_pmemrange.c,v > retrieving revision 1.37 > diff -p -u -r1.37 uvm_pmemrange.c > --- uvm/uvm_pmemrange.c 6 Feb 2014 16:40:40 - 1.37 > +++ uvm/uvm_pmemrange.c 13 Feb 2014 22:28:29 - > @@ -1647,7 +1647,7 @@ uvm_pmr_rootupdate(struct uvm_pmemrange >* Cache the lower page, so we can page-walk later. >*/ > low = root; > - low_next = RB_RIGHT(low, objt); > + low_next = RB_LEFT(low, objt); > while (low_next != NULL && PMR_INTERSECTS_WITH( > atop(VM_PAGE_TO_PHYS(low_next)), > atop(VM_PAGE_TO_PHYS(low_next)) + low_next->fpgsz, > @@ -1655,8 +1655,11 @@ uvm_pmr_rootupdate(struct uvm_pmemrange > low = low_next; > if (uvm_pmr_pg_to_memtype(low) == memtype) > return low; > - low_next = RB_RIGHT(low, objt); > + low_next = RB_LEFT(low, objt); > } > + > + if (low == high) > + return NULL; > > /* >* Ack, no hits. Walk the address tree until to find something usable. >
Re: trivial fix for pmemrange
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 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
Re: trivial fix for pmemrange
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. On Feb 17, 2014, at 5:14 PM, Mike Larkin wrote: > > Probably get a better response if you explained what this diff does > and/or fixes… i just think this bug is a little too obvious
Re: trivial fix for pmemrange
On Mon, Feb 17, 2014 at 05:02:34PM +0800, Kieran Devlin wrote: > Probably get a better response if you explained what this diff does and/or fixes... -ml > Index: uvm/uvm_pmemrange.c > === > RCS file: /cvs/src/sys/uvm/uvm_pmemrange.c,v > retrieving revision 1.37 > diff -p -u -r1.37 uvm_pmemrange.c > --- uvm/uvm_pmemrange.c 6 Feb 2014 16:40:40 - 1.37 > +++ uvm/uvm_pmemrange.c 13 Feb 2014 22:28:29 - > @@ -1647,7 +1647,7 @@ uvm_pmr_rootupdate(struct uvm_pmemrange >* Cache the lower page, so we can page-walk later. >*/ > low = root; > - low_next = RB_RIGHT(low, objt); > + low_next = RB_LEFT(low, objt); > while (low_next != NULL && PMR_INTERSECTS_WITH( > atop(VM_PAGE_TO_PHYS(low_next)), > atop(VM_PAGE_TO_PHYS(low_next)) + low_next->fpgsz, > @@ -1655,8 +1655,11 @@ uvm_pmr_rootupdate(struct uvm_pmemrange > low = low_next; > if (uvm_pmr_pg_to_memtype(low) == memtype) > return low; > - low_next = RB_RIGHT(low, objt); > + low_next = RB_LEFT(low, objt); > } > + > + if (low == high) > + return NULL; > > /* >* Ack, no hits. Walk the address tree until to find something usable. >
trivial fix for pmemrange
Index: uvm/uvm_pmemrange.c === RCS file: /cvs/src/sys/uvm/uvm_pmemrange.c,v retrieving revision 1.37 diff -p -u -r1.37 uvm_pmemrange.c --- uvm/uvm_pmemrange.c 6 Feb 2014 16:40:40 - 1.37 +++ uvm/uvm_pmemrange.c 13 Feb 2014 22:28:29 - @@ -1647,7 +1647,7 @@ uvm_pmr_rootupdate(struct uvm_pmemrange * Cache the lower page, so we can page-walk later. */ low = root; - low_next = RB_RIGHT(low, objt); + low_next = RB_LEFT(low, objt); while (low_next != NULL && PMR_INTERSECTS_WITH( atop(VM_PAGE_TO_PHYS(low_next)), atop(VM_PAGE_TO_PHYS(low_next)) + low_next->fpgsz, @@ -1655,8 +1655,11 @@ uvm_pmr_rootupdate(struct uvm_pmemrange low = low_next; if (uvm_pmr_pg_to_memtype(low) == memtype) return low; - low_next = RB_RIGHT(low, objt); + low_next = RB_LEFT(low, objt); } + + if (low == high) + return NULL; /* * Ack, no hits. Walk the address tree until to find something usable.