[RFC,v3,7/7] x86/unwind/orc: remove run-time ORC unwind tables sort
diff mbox series

Message ID 20191115064750.47888-8-shile.zhang@linux.alibaba.com
State New
Headers show
Series
  • Speed booting by sorting ORC unwind tables at build time
Related show

Commit Message

Shile Zhang Nov. 15, 2019, 6:47 a.m. UTC
The orc_unwind and orc_unwind_ip tables are sorted in vmlinux link phase
at build time, just remove the run-time sort.

Signed-off-by: Shile Zhang <shile.zhang@linux.alibaba.com>
---
 arch/x86/kernel/unwind_orc.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

Comments

David Laight Nov. 15, 2019, 4:51 p.m. UTC | #1
From: Shile Zhang
> Sent: 15 November 2019 06:48
...
>  arch/x86/kernel/unwind_orc.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
> 
> diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
> index 332ae6530fa8..280da6fa9922 100644
> --- a/arch/x86/kernel/unwind_orc.c
> +++ b/arch/x86/kernel/unwind_orc.c
> @@ -273,9 +273,11 @@ void __init unwind_init(void)
>  		return;
>  	}
> 
> -	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
> -	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
> -	     orc_sort_swap);
> +	/*
> +	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
> +	 * vmlinux link phase by sorttable tool at build time.
> +	 * Its ready for binary search now.
> +	 */

How fast is sort() if the table is sorted?
Relying on the kernel sources and build scripts always being in sync seems dangerous.
Probably better to leave the sort in for a release of two.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
Josh Poimboeuf Nov. 15, 2019, 5:46 p.m. UTC | #2
On Fri, Nov 15, 2019 at 04:51:24PM +0000, David Laight wrote:
> From: Shile Zhang
> > Sent: 15 November 2019 06:48
> ...
> >  arch/x86/kernel/unwind_orc.c | 8 +++++---
> >  1 file changed, 5 insertions(+), 3 deletions(-)
> > 
> > diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
> > index 332ae6530fa8..280da6fa9922 100644
> > --- a/arch/x86/kernel/unwind_orc.c
> > +++ b/arch/x86/kernel/unwind_orc.c
> > @@ -273,9 +273,11 @@ void __init unwind_init(void)
> >  		return;
> >  	}
> > 
> > -	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
> > -	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
> > -	     orc_sort_swap);
> > +	/*
> > +	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
> > +	 * vmlinux link phase by sorttable tool at build time.
> > +	 * Its ready for binary search now.
> > +	 */
> 
> How fast is sort() if the table is sorted?
> Relying on the kernel sources and build scripts always being in sync seems dangerous.
> Probably better to leave the sort in for a release of two.

This patch comes after the build script changes, so they'd be in sync.
What would the concern be?
David Laight Nov. 18, 2019, 10:05 a.m. UTC | #3
From: Josh Poimboeuf <jpoimboe@redhat.com>
> Sent: 15 November 2019 17:47
> On Fri, Nov 15, 2019 at 04:51:24PM +0000, David Laight wrote:
> > From: Shile Zhang
> > > Sent: 15 November 2019 06:48
> > ...
> > >  arch/x86/kernel/unwind_orc.c | 8 +++++---
> > >  1 file changed, 5 insertions(+), 3 deletions(-)
> > >
> > > diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
> > > index 332ae6530fa8..280da6fa9922 100644
> > > --- a/arch/x86/kernel/unwind_orc.c
> > > +++ b/arch/x86/kernel/unwind_orc.c
> > > @@ -273,9 +273,11 @@ void __init unwind_init(void)
> > >  		return;
> > >  	}
> > >
> > > -	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
> > > -	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
> > > -	     orc_sort_swap);
> > > +	/*
> > > +	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
> > > +	 * vmlinux link phase by sorttable tool at build time.
> > > +	 * Its ready for binary search now.
> > > +	 */
> >
> > How fast is sort() if the table is sorted?
> > Relying on the kernel sources and build scripts always being in sync seems dangerous.
> > Probably better to leave the sort in for a release of two.
> 
> This patch comes after the build script changes, so they'd be in sync.
> What would the concern be?

Mostly that if, for any reason, the build script changes are missing nothing
will detect the error - but the results will be very confusing.
If the sort is fast for sorted inputs (some algorithms aren't) then leaving
it in won't take that long.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
Shile Zhang Nov. 18, 2019, 10:50 a.m. UTC | #4
On 2019/11/18 18:05, David Laight wrote:
> From: Josh Poimboeuf <jpoimboe@redhat.com>
>> Sent: 15 November 2019 17:47
>> On Fri, Nov 15, 2019 at 04:51:24PM +0000, David Laight wrote:
>>> From: Shile Zhang
>>>> Sent: 15 November 2019 06:48
>>> ...
>>>>   arch/x86/kernel/unwind_orc.c | 8 +++++---
>>>>   1 file changed, 5 insertions(+), 3 deletions(-)
>>>>
>>>> diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
>>>> index 332ae6530fa8..280da6fa9922 100644
>>>> --- a/arch/x86/kernel/unwind_orc.c
>>>> +++ b/arch/x86/kernel/unwind_orc.c
>>>> @@ -273,9 +273,11 @@ void __init unwind_init(void)
>>>>   		return;
>>>>   	}
>>>>
>>>> -	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
>>>> -	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
>>>> -	     orc_sort_swap);
>>>> +	/*
>>>> +	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
>>>> +	 * vmlinux link phase by sorttable tool at build time.
>>>> +	 * Its ready for binary search now.
>>>> +	 */
>>> How fast is sort() if the table is sorted?
>>> Relying on the kernel sources and build scripts always being in sync seems dangerous.
>>> Probably better to leave the sort in for a release of two.
>> This patch comes after the build script changes, so they'd be in sync.
>> What would the concern be?
> Mostly that if, for any reason, the build script changes are missing nothing
> will detect the error - but the results will be very confusing.
> If the sort is fast for sorted inputs (some algorithms aren't) then leaving
> it in won't take that long.
>
> 	David

Hi, David,

Thanks for your review!
Due to the sort inside kernel is heap-sort, so it cost almost the same 
time for sorted inputs.
I wondered if we can add error handling in the link script, exit with 
error if sort encountered any errors.

Thanks!

> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
Josh Poimboeuf Nov. 18, 2019, 2:41 p.m. UTC | #5
On Mon, Nov 18, 2019 at 10:05:02AM +0000, David Laight wrote:
> From: Josh Poimboeuf <jpoimboe@redhat.com>
> > Sent: 15 November 2019 17:47
> > On Fri, Nov 15, 2019 at 04:51:24PM +0000, David Laight wrote:
> > > From: Shile Zhang
> > > > Sent: 15 November 2019 06:48
> > > ...
> > > >  arch/x86/kernel/unwind_orc.c | 8 +++++---
> > > >  1 file changed, 5 insertions(+), 3 deletions(-)
> > > >
> > > > diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
> > > > index 332ae6530fa8..280da6fa9922 100644
> > > > --- a/arch/x86/kernel/unwind_orc.c
> > > > +++ b/arch/x86/kernel/unwind_orc.c
> > > > @@ -273,9 +273,11 @@ void __init unwind_init(void)
> > > >  		return;
> > > >  	}
> > > >
> > > > -	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
> > > > -	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
> > > > -	     orc_sort_swap);
> > > > +	/*
> > > > +	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
> > > > +	 * vmlinux link phase by sorttable tool at build time.
> > > > +	 * Its ready for binary search now.
> > > > +	 */
> > >
> > > How fast is sort() if the table is sorted?
> > > Relying on the kernel sources and build scripts always being in sync seems dangerous.
> > > Probably better to leave the sort in for a release of two.
> > 
> > This patch comes after the build script changes, so they'd be in sync.
> > What would the concern be?
> 
> Mostly that if, for any reason, the build script changes are missing nothing
> will detect the error - but the results will be very confusing.
> If the sort is fast for sorted inputs (some algorithms aren't) then leaving
> it in won't take that long.

But why would the build script changes be missing...

And it should fail gracefully for oopses anyway: stack traces will just
have a bunch of question marks.

Patch
diff mbox series

diff --git a/arch/x86/kernel/unwind_orc.c b/arch/x86/kernel/unwind_orc.c
index 332ae6530fa8..280da6fa9922 100644
--- a/arch/x86/kernel/unwind_orc.c
+++ b/arch/x86/kernel/unwind_orc.c
@@ -273,9 +273,11 @@  void __init unwind_init(void)
 		return;
 	}
 
-	/* Sort the .orc_unwind and .orc_unwind_ip tables: */
-	sort(__start_orc_unwind_ip, num_entries, sizeof(int), orc_sort_cmp,
-	     orc_sort_swap);
+	/*
+	 * Note, orc_unwind and orc_unwind_ip tables has been sorted in
+	 * vmlinux link phase by sorttable tool at build time.
+	 * Its ready for binary search now.
+	 */
 
 	/* Initialize the fast lookup table: */
 	lookup_num_blocks = orc_lookup_end - orc_lookup;