Re: trivial fix for pmemrange

2014-04-05 Thread Miod Vallat
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

2014-02-27 Thread Ariane van der Steldt

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

2014-02-17 Thread Kieran Devlin
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

2014-02-17 Thread Mike Larkin
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

2014-02-17 Thread Kieran Devlin

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.