In clip_to_limit(), after memmove(&e820.map[i], &e820.map[i+1], ...),
the original
e820.map[i+1] become current e820.map[i] but the next loop count is i+1, so the
original
e820.map[i+1] will be skipped
Actually, e820 is sorted form low to high by sanitize_e820_map(), so we can
simply break
the loop if we meet the item which overrun "limit"
Signed-off-by: Xiao Guangrong <ericxiao.gr@gmail.com>
diff -r 93bc06dd1161 -r 5e06f2790d93 xen/arch/x86/e820.c
--- a/xen/arch/x86/e820.c Tue Nov 10 02:41:59 2009 +0800
+++ b/xen/arch/x86/e820.c Tue Nov 10 03:51:08 2009 +0800
@@ -389,6 +389,7 @@
(e820.nr_map - i - 1) * sizeof(struct e820entry));
e820.nr_map--;
}
+ break;
}
if ( old_limit )
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel
I think the ''break'' is in the wrong place. Actually also I think the case of successful change_range_type() is also wrong, as i=0 will be skipped on the next iteration of the loop. Overall I decided that modifying the e820 map inside the iterator loop was just bad and confusing, so I''ve rewritten it in response to your bug discovery. Please take a look at xen-unstable:20419 and let me know if you see any issues. Thanks, Keir On 09/11/2009 20:04, "Xiao Guangrong" <ericxiao.gr@gmail.com> wrote:> In clip_to_limit(), after memmove(&e820.map[i], &e820.map[i+1], ...), the > original > e820.map[i+1] become current e820.map[i] but the next loop count is i+1, so > the original > e820.map[i+1] will be skipped > > Actually, e820 is sorted form low to high by sanitize_e820_map(), so we can > simply break > the loop if we meet the item which overrun "limit" > > Signed-off-by: Xiao Guangrong <ericxiao.gr@gmail.com> > > diff -r 93bc06dd1161 -r 5e06f2790d93 xen/arch/x86/e820.c > --- a/xen/arch/x86/e820.c Tue Nov 10 02:41:59 2009 +0800 > +++ b/xen/arch/x86/e820.c Tue Nov 10 03:51:08 2009 +0800 > @@ -389,6 +389,7 @@ > (e820.nr_map - i - 1) * sizeof(struct e820entry)); > e820.nr_map--; > } > + break; > } > > if ( old_limit )_______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Hi Keir, Keir Fraser wrote:> I think the ''break'' is in the wrong place. Actually also I think the case ofWhy we can''t break the loop if we meet the "large" end address? what am i missed?> successful change_range_type() is also wrong, as i=0 will be skipped on the > next iteration of the loop. > > Overall I decided that modifying the e820 map inside the iterator loop was > just bad and confusing, so I''ve rewritten it in response to your bug > discovery. Please take a look at xen-unstable:20419 and let me know if you > see any issues.Your patch work well, IMHO, double loop is inefficient, we can decrease the loop counter if we need "memmove" it, like this: if ( e820.map[i].addr < limit ) { e820.map[i].size = limit - e820.map[i].addr; } else { memmove(&e820.map[i], &e820.map[i+1], (e820.nr_map - i - 1) * sizeof(struct e820entry)); e820.nr_map--; + i--; } Also in the original code: if ( e820_change_range_type(&e820, max(e820.map[i].addr, limit), old_limit, E820_RAM, E820_UNUSABLE) ) { /* Start again now e820 map must have changed. */ i = 0; } I think we don''t need reload loop hear, because e820_change_range_type() not touch front object(it may merge with e820.map[i+1], but it not hurt us). Thanks, Xiao> > On 09/11/2009 20:04, "Xiao Guangrong" <ericxiao.gr@gmail.com> wrote: > >> In clip_to_limit(), after memmove(&e820.map[i], &e820.map[i+1], ...), the >> original >> e820.map[i+1] become current e820.map[i] but the next loop count is i+1, so >> the original >> e820.map[i+1] will be skipped >> >> Actually, e820 is sorted form low to high by sanitize_e820_map(), so we can >> simply break >> the loop if we meet the item which overrun "limit" >> >> Signed-off-by: Xiao Guangrong <ericxiao.gr@gmail.com> >> >> diff -r 93bc06dd1161 -r 5e06f2790d93 xen/arch/x86/e820.c >> --- a/xen/arch/x86/e820.c Tue Nov 10 02:41:59 2009 +0800 >> +++ b/xen/arch/x86/e820.c Tue Nov 10 03:51:08 2009 +0800 >> @@ -389,6 +389,7 @@ >> (e820.nr_map - i - 1) * sizeof(struct e820entry)); >> e820.nr_map--; >> } >> + break; >> } >> >> if ( old_limit ) > > > >_______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
On 10/11/2009 02:13, "Xiao Guangrong" <xiaoguangrong@cn.fujitsu.com> wrote:> Hi Keir, > > Keir Fraser wrote: >> I think the ''break'' is in the wrong place. Actually also I think the case of > > Why we can''t break the loop if we meet the "large" end address? what am i > missed?Firstly, your ''break'' was not inside that if-else block; it was right at the end of the for loop. Secondly, just because we found one RAM region entirely beyond the end of the clip boundary, does not mean there isn''t another. We can''t just bail -- we have to iterate all the way to the end of the e820 map.> Your patch work well, IMHO, double loop is inefficientWell, possibly. But really a typical e820 map will not have more than a small handful of offending RAM regions, hence there should be very few iterations of the outer loop. Also we already re-set the loop variable in the e820_change_range_type() case, so we effectively had the same double loop there already (and change_range_type will be by far the common case when we find a e820 region to clip).> I think we don''t need reload loop hear, because e820_change_range_type() not > touch front object(it may merge with e820.map[i+1], but it not hurt us).It also does a full e820 merge operation at the end. I wouldn''t really like to make assumptions about how much that modifies e820. -- Keir> Thanks, > Xiao > >> >> On 09/11/2009 20:04, "Xiao Guangrong" <ericxiao.gr@gmail.com> wrote: >> >>> In clip_to_limit(), after memmove(&e820.map[i], &e820.map[i+1], ...), the >>> original >>> e820.map[i+1] become current e820.map[i] but the next loop count is i+1, so >>> the original >>> e820.map[i+1] will be skipped >>> >>> Actually, e820 is sorted form low to high by sanitize_e820_map(), so we can >>> simply break >>> the loop if we meet the item which overrun "limit" >>> >>> Signed-off-by: Xiao Guangrong <ericxiao.gr@gmail.com> >>> >>> diff -r 93bc06dd1161 -r 5e06f2790d93 xen/arch/x86/e820.c >>> --- a/xen/arch/x86/e820.c Tue Nov 10 02:41:59 2009 +0800 >>> +++ b/xen/arch/x86/e820.c Tue Nov 10 03:51:08 2009 +0800 >>> @@ -389,6 +389,7 @@ >>> (e820.nr_map - i - 1) * sizeof(struct e820entry)); >>> e820.nr_map--; >>> } >>> + break; >>> } >>> >>> if ( old_limit ) >> >> >> >>_______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Keir Fraser wrote:> On 10/11/2009 02:13, "Xiao Guangrong" <xiaoguangrong@cn.fujitsu.com> wrote: > >> Hi Keir, >> >> Keir Fraser wrote: >>> I think the ''break'' is in the wrong place. Actually also I think the case of >> Why we can''t break the loop if we meet the "large" end address? what am i >> missed? > > Firstly, your ''break'' was not inside that if-else block; it was right at the > end of the for loop. Secondly, just because we found one RAM region entirely > beyond the end of the clip boundary, does not mean there isn''t another. We > can''t just bail -- we have to iterate all the way to the end of the e820 > map. >I think that sanitize_e820_map() can sort e820 items from low address to high address, so, if we meet one e820 item beyond the end of the clip boundary, subsequent items also beyond it. Maybe I misunderstand sanitize_e820_map()? I''ll reread it :-)>> Your patch work well, IMHO, double loop is inefficient > > Well, possibly. But really a typical e820 map will not have more than a > small handful of offending RAM regions, hence there should be very few > iterations of the outer loop. Also we already re-set the loop variable in > the e820_change_range_type() case, so we effectively had the same double > loop there already (and change_range_type will be by far the common case > when we find a e820 region to clip). >Yeah, you are right, I missed it before :-) Thanks, Xiao>> I think we don''t need reload loop hear, because e820_change_range_type() not >> touch front object(it may merge with e820.map[i+1], but it not hurt us). > > It also does a full e820 merge operation at the end. I wouldn''t really like > to make assumptions about how much that modifies e820. >_______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
On 10/11/2009 08:19, "Xiao Guangrong" <xiaoguangrong@cn.fujitsu.com> wrote:>> Firstly, your ''break'' was not inside that if-else block; it was right at the >> end of the for loop. Secondly, just because we found one RAM region entirely >> beyond the end of the clip boundary, does not mean there isn''t another. We >> can''t just bail -- we have to iterate all the way to the end of the e820 >> map. >> > > I think that sanitize_e820_map() can sort e820 items from low address > to high address, so, if we meet one e820 item beyond the end of the clip > boundary, subsequent items also beyond it. > > Maybe I misunderstand sanitize_e820_map()? I''ll reread it :-)No, you understand it. And if we meet one e820 item beyond the end of the clip boundary, all subsequent items are also beyond it. But that doesn''t mean we shouldn''t handle them -- in fact we must handle them, as one of them could be E820_RAM. Right? -- Keir _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel
Keir Fraser wrote:> On 10/11/2009 08:19, "Xiao Guangrong" <xiaoguangrong@cn.fujitsu.com> wrote: > >>> Firstly, your ''break'' was not inside that if-else block; it was right at the >>> end of the for loop. Secondly, just because we found one RAM region entirely >>> beyond the end of the clip boundary, does not mean there isn''t another. We >>> can''t just bail -- we have to iterate all the way to the end of the e820 >>> map. >>> >> I think that sanitize_e820_map() can sort e820 items from low address >> to high address, so, if we meet one e820 item beyond the end of the clip >> boundary, subsequent items also beyond it. >> >> Maybe I misunderstand sanitize_e820_map()? I''ll reread it :-) > > No, you understand it. And if we meet one e820 item beyond the end of the > clip boundary, all subsequent items are also beyond it. But that doesn''t > mean we shouldn''t handle them -- in fact we must handle them, as one of them > could be E820_RAM. Right? >Yeah, It''s my mistake, Thanks very much, Keir! And I think find_max_pfn() can be optimized. like this: --- ../a/xen/arch/x86/e820.c 2009-08-06 21:57:27.000000000 +0800 +++ ../b/xen/arch/x86/e820.c 2009-10-25 17:31:42.762997342 +0800 @@ -312,8 +312,9 @@ static unsigned long __init find_max_pfn } #endif - for (i = 0; i < e820.nr_map; i++) { + for (i = e820.nr_map -1; i >= 0; i--) { unsigned long start, end; + /* RAM? */ if (e820.map[i].type != E820_RAM) continue; @@ -321,8 +322,8 @@ static unsigned long __init find_max_pfn end = PFN_DOWN(e820.map[i].addr + e820.map[i].size); if (start >= end) continue; - if (end > max_pfn) - max_pfn = end; + max_pfn = end; + break; } return max_pfn; Thanks, Xiao _______________________________________________ Xen-devel mailing list Xen-devel@lists.xensource.com http://lists.xensource.com/xen-devel