[PATCH] x86-64: improve e820_search_gap()

[PATCH] x86-64: improve e820_search_gap()

[Jan Beulich]

Impact: bug fix

Blindly putting the gap close after max_pfn is in conflict with that
same memory range potentially being used by hotplugged memory.

Also, make the function static to ensure there are no other users that
could depend on the previous behavior regarding the way start_addr gets
specified.

Signed-off-by: Jan Beulich <jbeulich@novell.com>

---
 arch/x86/include/asm/e820.h |    2 --
 arch/x86/kernel/e820.c      |   11 +++++++++--
 2 files changed, 9 insertions(+), 4 deletions(-)

--- linux-2.6.30-rc4/arch/x86/include/asm/e820.h	2009-04-30 09:42:42.000000000 +0200
+++ 2.6.30-rc4-x86_64-e820-setup-gap/arch/x86/include/asm/e820.h	2009-04-27 12:03:48.000000000 +0200
@@ -79,8 +79,6 @@ extern u64 e820_remove_range(u64 start, 
 			     int checktype);
 extern void update_e820(void);
 extern void e820_setup_gap(void);
-extern int e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
-			unsigned long start_addr, unsigned long long end_addr);
 struct setup_data;
 extern void parse_e820_ext(struct setup_data *data, unsigned long pa_data);
 
--- linux-2.6.30-rc4/arch/x86/kernel/e820.c	2009-04-30 09:42:42.000000000 +0200
+++ 2.6.30-rc4-x86_64-e820-setup-gap/arch/x86/kernel/e820.c	2009-04-27 12:03:48.000000000 +0200
@@ -574,13 +574,19 @@ static void __init update_e820_saved(voi
 /*
  * Search for a gap in the e820 memory space from start_addr to end_addr.
  */
-__init int e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
+static int __init
+e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
 		unsigned long start_addr, unsigned long long end_addr)
 {
 	unsigned long long last;
 	int i = e820.nr_map;
 	int found = 0;
 
+#ifdef CONFIG_X86_64
+	if (start_addr >= MAX_GAP_END)
+		last = end_addr ?: (1UL << boot_cpu_data.x86_phys_bits);
+	else
+#endif
 	last = (end_addr && end_addr < MAX_GAP_END) ? end_addr : MAX_GAP_END;
 
 	while (--i >= 0) {
@@ -626,11 +632,12 @@ __init void e820_setup_gap(void)
 
 #ifdef CONFIG_X86_64
 	if (!found) {
-		gapstart = (max_pfn << PAGE_SHIFT) + 1024*1024;
 		printk(KERN_ERR "PCI: Warning: Cannot find a gap in the 32bit "
 		       "address range\n"
 		       KERN_ERR "PCI: Unassigned devices with 32bit resource "
 		       "registers may break!\n");
+		found = e820_search_gap(&gapstart, &gapsize, MAX_GAP_END, 0);
+		WARN_ON(!found);
 	}
 #endif
 

Re: [PATCH] x86-64: improve e820_search_gap()

[H. Peter Anvin]

Jan Beulich wrote:
> Impact: bug fix
> 
> Blindly putting the gap close after max_pfn is in conflict with that
> same memory range potentially being used by hotplugged memory.
> 
> Also, make the function static to ensure there are no other users that
> could depend on the previous behavior regarding the way start_addr gets
> specified.
> 
> Signed-off-by: Jan Beulich <jbeulich@novell.com>
> 

So blindly locate it somewhere else?  How is that inherently better?
Wouldn't a machine with hotplug memory (which doesn't bother advertising
that fact so we can reserve the address space) be just as likely to use
a sparse memory space, since one can hardly expect the hardware to pack
the space (packing in hardware is why PCs generally have a
mostly-contiguous RAM space) when the memory is hotplugged?

I think I'm missing something fundamental...

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Re: [PATCH] x86-64: improve e820_search_gap()

[Jan Beulich]

>>> "H. Peter Anvin" <hpa@zytor.com> 08.05.09 06:59 >>>
>Jan Beulich wrote:
>> Impact: bug fix
>> 
>> Blindly putting the gap close after max_pfn is in conflict with that
>> same memory range potentially being used by hotplugged memory.
>> 
>> Also, make the function static to ensure there are no other users that
>> could depend on the previous behavior regarding the way start_addr gets
>> specified.
>> 
>> Signed-off-by: Jan Beulich <jbeulich@novell.com>
>> 
>
>So blindly locate it somewhere else?  How is that inherently better?
>Wouldn't a machine with hotplug memory (which doesn't bother advertising
>that fact so we can reserve the address space) be just as likely to use
>a sparse memory space, since one can hardly expect the hardware to pack
>the space (packing in hardware is why PCs generally have a
>mostly-contiguous RAM space) when the memory is hotplugged?

Why blindly? Aren't hotpluggable memory ranges supposed to be reserved
in the E820 map?

Jan

Re: [PATCH] x86-64: improve e820_search_gap()

[H. Peter Anvin]

Jan Beulich wrote:
>>>
>> So blindly locate it somewhere else?  How is that inherently better?
>> Wouldn't a machine with hotplug memory (which doesn't bother advertising
>> that fact so we can reserve the address space) be just as likely to use
>> a sparse memory space, since one can hardly expect the hardware to pack
>> the space (packing in hardware is why PCs generally have a
>> mostly-contiguous RAM space) when the memory is hotplugged?
> 
> Why blindly? Aren't hotpluggable memory ranges supposed to be reserved
> in the E820 map?
> 

That's was my reaction too... so I guess I'm misreading the patch.
Could you perhaps add a bit more to the description, specifically of
what policy your patch implements.

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Re: [PATCH] x86-64: improve e820_search_gap()

[Andi Kleen]

"Jan Beulich" <jbeulich@novell.com> writes:
>
> Why blindly? Aren't hotpluggable memory ranges supposed to be reserved
> in the E820 map?

They are supposed to be reserved in SRAT, but not in e820.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] x86-64: improve e820_search_gap()

[H. Peter Anvin]

Andi Kleen wrote:
> "Jan Beulich" <jbeulich@novell.com> writes:
>> Why blindly? Aren't hotpluggable memory ranges supposed to be reserved
>> in the E820 map?
> 
> They are supposed to be reserved in SRAT, but not in e820.

Ah, okay.  Perhaps we should fold this information into our internal 
"e820" map?  If so I guess the question is how soon we can do that.

	-hpa

Re: [PATCH] x86-64: improve e820_search_gap()

[Andi Kleen]

On Fri, May 08, 2009 at 01:15:38PM -0700, H. Peter Anvin wrote:
> Andi Kleen wrote:
> >"Jan Beulich" <jbeulich@novell.com> writes:
> >>Why blindly? Aren't hotpluggable memory ranges supposed to be reserved
> >>in the E820 map?
> >
> >They are supposed to be reserved in SRAT, but not in e820.
> 
> Ah, okay.  Perhaps we should fold this information into our internal 
> "e820" map?  If so I guess the question is how soon we can do that.

You could do that or just query SRAT too, but ...

The problem is really that there are still systems which have hidden
holes which are not reserved anywhere. When I last hacked on the gap algorithm
it triggered subtle bugs. So this will never be fully reliable.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] x86-64: improve e820_search_gap()

[H. Peter Anvin]

Andi Kleen wrote:
> On Fri, May 08, 2009 at 01:15:38PM -0700, H. Peter Anvin wrote:
>> Andi Kleen wrote:
>>> "Jan Beulich" <jbeulich@novell.com> writes:
>>>> Why blindly? Aren't hotpluggable memory ranges supposed to be reserved
>>>> in the E820 map?
>>> They are supposed to be reserved in SRAT, but not in e820.
>> Ah, okay.  Perhaps we should fold this information into our internal 
>> "e820" map?  If so I guess the question is how soon we can do that.
> 
> You could do that or just query SRAT too, but ...
> 
> The problem is really that there are still systems which have hidden
> holes which are not reserved anywhere. When I last hacked on the gap algorithm
> it triggered subtle bugs. So this will never be fully reliable.
> 

That's without a question.

However, as far as querying SRAT, I don't like the idea of spreading the 
knowledge of the system memory map out between a bunch of different 
places, each of which have a little piece of the puzzle.  It puts a huge 
onus on the user to know what mechanisms are actually available, and 
really makes a shitty interface.

	-hpa

Re: [PATCH] x86-64: improve e820_search_gap()

[Andi Kleen]

> However, as far as querying SRAT, I don't like the idea of spreading the 
> knowledge of the system memory map out between a bunch of different 
> places, each of which have a little piece of the puzzle.  It puts a huge 
> onus on the user to know what mechanisms are actually available, and 
> really makes a shitty interface.

AFAIK another popular OS always combines mappings from all sources (e820,
SRAT, PCI, PNP, ACPI etc.) in the query before allocating anything.
Something like that might be a reasonable long term direction for Linux
too, but it's probably also a can of worms to handle the conflicts
between the various sources (e.g. e820 reserves a lot of things
in other sources too). It would be a rather large change.
Maybe that would handle the systems I thought of above.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] x86-64: improve e820_search_gap()

[H. Peter Anvin]

Andi Kleen wrote:
>> However, as far as querying SRAT, I don't like the idea of spreading the 
>> knowledge of the system memory map out between a bunch of different 
>> places, each of which have a little piece of the puzzle.  It puts a huge 
>> onus on the user to know what mechanisms are actually available, and 
>> really makes a shitty interface.
> 
> AFAIK another popular OS always combines mappings from all sources (e820,
> SRAT, PCI, PNP, ACPI etc.) in the query before allocating anything.
> Something like that might be a reasonable long term direction for Linux
> too, but it's probably also a can of worms to handle the conflicts
> between the various sources (e.g. e820 reserves a lot of things
> in other sources too). It would be a rather large change.
> Maybe that would handle the systems I thought of above.

You *always* have a conflict resolution policy... whether or not it is
explicit or accidental, and whether or not it is the result of merging
the data or just accessing multiple data sources is another matter.  It
might be hard to replicate an accidental policy in an explicit way, or
the accidental policy really might make no sense, which may mean
behavior changes.

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

Re: [PATCH] x86-64: improve e820_search_gap()

[Andi Kleen]

On Sat, May 09, 2009 at 11:43:26PM -0700, H. Peter Anvin wrote:
> Andi Kleen wrote:
> >> However, as far as querying SRAT, I don't like the idea of spreading the 
> >> knowledge of the system memory map out between a bunch of different 
> >> places, each of which have a little piece of the puzzle.  It puts a huge 
> >> onus on the user to know what mechanisms are actually available, and 
> >> really makes a shitty interface.
> > 
> > AFAIK another popular OS always combines mappings from all sources (e820,
> > SRAT, PCI, PNP, ACPI etc.) in the query before allocating anything.
> > Something like that might be a reasonable long term direction for Linux
> > too, but it's probably also a can of worms to handle the conflicts
> > between the various sources (e.g. e820 reserves a lot of things
> > in other sources too). It would be a rather large change.
> > Maybe that would handle the systems I thought of above.
> 
> You *always* have a conflict resolution policy... whether or not it is

Well right now we ignore ACPI/PNP data, sometimes ignore PCI data 
and only look in e820 and sometimes only use PCI/e820 and sometimes
only use SRAT (or at least it was like this at some point)

BTW SRAT hot range can be also wrong, some BIOS always had a full
512GB range even though they don't support hotplug.
However I haven't seen a system which supports hotplug (not that
there are very many of those) where the entry was not there, so at least
that one should be safe.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

Re: [PATCH] x86-64: improve e820_search_gap()

[H. Peter Anvin]

Andi Kleen wrote:
> 
> Well right now we ignore ACPI/PNP data, sometimes ignore PCI data 
> and only look in e820 and sometimes only use PCI/e820 and sometimes
> only use SRAT (or at least it was like this at some point)
> 

That *is* a conflict resolution policy.  Quite probably an accidental one.

	-hpa

-- 
H. Peter Anvin, Intel Open Source Technology Center
I work for Intel.  I don't speak on their behalf.

[PATCH] x86-64: improve e820_search_gap()

[Jan Beulich]

Blindly putting the gap close after max_pfn might be fine for native
(though even there I'm uncertain regarding memory hotplug), but will
certainly present a problem on Xen. And properly searching for a gap
above 4Gb shouldn't hurt native.

Also, make the function static to ensure there are no other users that
could depend on the previous behavior regarding the way start_addr gets
specified.

Signed-off-by: Jan Beulich <jbeulich@novell.com>
Cc: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

---
 arch/x86/include/asm/e820.h |    2 --
 arch/x86/kernel/e820.c      |   11 +++++++++--
 2 files changed, 9 insertions(+), 4 deletions(-)

--- linux-2.6.29-rc7/arch/x86/include/asm/e820.h	2009-03-11 17:52:10.000000000 +0100
+++ 2.6.29-rc7-x86_64-e820-setup-gap-64bit/arch/x86/include/asm/e820.h	2009-03-06 11:25:35.000000000 +0100
@@ -79,8 +79,6 @@ extern u64 e820_remove_range(u64 start, 
 			     int checktype);
 extern void update_e820(void);
 extern void e820_setup_gap(void);
-extern int e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
-			unsigned long start_addr, unsigned long long end_addr);
 struct setup_data;
 extern void parse_e820_ext(struct setup_data *data, unsigned long pa_data);
 
--- linux-2.6.29-rc7/arch/x86/kernel/e820.c	2009-03-11 17:52:10.000000000 +0100
+++ 2.6.29-rc7-x86_64-e820-setup-gap-64bit/arch/x86/kernel/e820.c	2009-03-06 11:24:34.000000000 +0100
@@ -533,13 +533,19 @@ static void __init update_e820_saved(voi
 /*
  * Search for a gap in the e820 memory space from start_addr to end_addr.
  */
-__init int e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
+static int __init
+e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
 		unsigned long start_addr, unsigned long long end_addr)
 {
 	unsigned long long last;
 	int i = e820.nr_map;
 	int found = 0;
 
+#ifdef CONFIG_X86_64
+	if (start_addr >= MAX_GAP_END)
+		last = end_addr ?: (1UL << boot_cpu_data.x86_phys_bits);
+	else
+#endif
 	last = (end_addr && end_addr < MAX_GAP_END) ? end_addr : MAX_GAP_END;
 
 	while (--i >= 0) {
@@ -585,11 +591,12 @@ __init void e820_setup_gap(void)
 
 #ifdef CONFIG_X86_64
 	if (!found) {
-		gapstart = (max_pfn << PAGE_SHIFT) + 1024*1024;
 		printk(KERN_ERR "PCI: Warning: Cannot find a gap in the 32bit "
 		       "address range\n"
 		       KERN_ERR "PCI: Unassigned devices with 32bit resource "
 		       "registers may break!\n");
+		found = e820_search_gap(&gapstart, &gapsize, MAX_GAP_END, 0);
+		BUG_ON(!found);
 	}
 #endif
 

Re: [PATCH] x86-64: improve e820_search_gap()

[Ingo Molnar]

* Jan Beulich <jbeulich@novell.com> wrote:

> Blindly putting the gap close after max_pfn might be fine for native
> (though even there I'm uncertain regarding memory hotplug), but will
> certainly present a problem on Xen. And properly searching for a gap
> above 4Gb shouldn't hurt native.
> 
> Also, make the function static to ensure there are no other users that
> could depend on the previous behavior regarding the way start_addr gets
> specified.
> 
> Signed-off-by: Jan Beulich <jbeulich@novell.com>
> Cc: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
> 
> ---
>  arch/x86/include/asm/e820.h |    2 --
>  arch/x86/kernel/e820.c      |   11 +++++++++--
>  2 files changed, 9 insertions(+), 4 deletions(-)
> 
> --- linux-2.6.29-rc7/arch/x86/include/asm/e820.h	2009-03-11 17:52:10.000000000 +0100
> +++ 2.6.29-rc7-x86_64-e820-setup-gap-64bit/arch/x86/include/asm/e820.h	2009-03-06 11:25:35.000000000 +0100
> @@ -79,8 +79,6 @@ extern u64 e820_remove_range(u64 start, 
>  			     int checktype);
>  extern void update_e820(void);
>  extern void e820_setup_gap(void);
> -extern int e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
> -			unsigned long start_addr, unsigned long long end_addr);
>  struct setup_data;
>  extern void parse_e820_ext(struct setup_data *data, unsigned long pa_data);
>  
> --- linux-2.6.29-rc7/arch/x86/kernel/e820.c	2009-03-11 17:52:10.000000000 +0100
> +++ 2.6.29-rc7-x86_64-e820-setup-gap-64bit/arch/x86/kernel/e820.c	2009-03-06 11:24:34.000000000 +0100
> @@ -533,13 +533,19 @@ static void __init update_e820_saved(voi
>  /*
>   * Search for a gap in the e820 memory space from start_addr to end_addr.
>   */
> -__init int e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
> +static int __init
> +e820_search_gap(unsigned long *gapstart, unsigned long *gapsize,
>  		unsigned long start_addr, unsigned long long end_addr)
>  {
>  	unsigned long long last;
>  	int i = e820.nr_map;
>  	int found = 0;
>  
> +#ifdef CONFIG_X86_64
> +	if (start_addr >= MAX_GAP_END)
> +		last = end_addr ?: (1UL << boot_cpu_data.x86_phys_bits);
> +	else
> +#endif
>  	last = (end_addr && end_addr < MAX_GAP_END) ? end_addr : MAX_GAP_END;

hm, this #ifdef block looks quite ugly and should be cleaned up. 
x86_phys_bits could be filled in on 32-bit too - and on 32-bit 
start_addr cannot be larger than 4GB anyway.

>  	while (--i >= 0) {
> @@ -585,11 +591,12 @@ __init void e820_setup_gap(void)
>  
>  #ifdef CONFIG_X86_64
>  	if (!found) {
> -		gapstart = (max_pfn << PAGE_SHIFT) + 1024*1024;
>  		printk(KERN_ERR "PCI: Warning: Cannot find a gap in the 32bit "
>  		       "address range\n"
>  		       KERN_ERR "PCI: Unassigned devices with 32bit resource "
>  		       "registers may break!\n");
> +		found = e820_search_gap(&gapstart, &gapsize, MAX_GAP_END, 0);
> +		BUG_ON(!found);

that BUG_ON() will be hard to debug - please use a WARN_ON 
instead.

	Ingo

Re: [PATCH] x86-64: improve e820_search_gap()

[Jan Beulich]

>>> Ingo Molnar <mingo@elte.hu> 12.03.09 12:02 >>>
>  
> +#ifdef CONFIG_X86_64
> +	if (start_addr >= MAX_GAP_END)
> +		last = end_addr ?: (1UL << boot_cpu_data.x86_phys_bits);
> +	else
> +#endif
>  	last = (end_addr && end_addr < MAX_GAP_END) ? end_addr : MAX_GAP_END;

>hm, this #ifdef block looks quite ugly and should be cleaned up. 
>x86_phys_bits could be filled in on 32-bit too - and on 32-bit 

I'm about to submit a patch to that effect. But I'm trying to keep patches
independent as much as possible.

>start_addr cannot be larger than 4GB anyway.

Correct, but I think the code would be less self-documenting if it relied
on that fact rather than making clear from the first glance that the
conditional is only being evaluated (and hence can only be true) on 64-bits.

>> @@ -585,11 +591,12 @@ __init void e820_setup_gap(void)
>>  
>>  #ifdef CONFIG_X86_64
>>  	if (!found) {
>> -		gapstart = (max_pfn << PAGE_SHIFT) + 1024*1024;
>>  		printk(KERN_ERR "PCI: Warning: Cannot find a gap in the 32bit "
>>  		       "address range\n"
>>  		       KERN_ERR "PCI: Unassigned devices with 32bit resource "
>>  		       "registers may break!\n");
>> +		found = e820_search_gap(&gapstart, &gapsize, MAX_GAP_END, 0);
>> +		BUG_ON(!found);
>
>that BUG_ON() will be hard to debug - please use a WARN_ON 
>instead.

Will do, but please clarify the above point before I re-submit.

Jan

Re: [PATCH] x86-64: improve e820_search_gap()

[Jeremy Fitzhardinge]

Jan Beulich wrote:
> Blindly putting the gap close after max_pfn might be fine for native
> (though even there I'm uncertain regarding memory hotplug), but will
> certainly present a problem on Xen. And properly searching for a gap
> above 4Gb shouldn't hurt native.
>   

What Xen-related issue are you thinking of?

When booting dom0 I reashape the guest memory to match the host E820 
map, and for domU my plan is to leave a hole at 3-4GB for pci 
passthrough resources.

    J