by Shile Zhang

[permalink] [raw]

Subject: Re: [RFC PATCH v3 6/7] scripts/sorttable: Add ORC unwind tables sort concurrently

On 2019/11/16 01:24, Andy Lutomirski wrote:
>> On Nov 15, 2019, at 1:43 AM, Shile Zhang <[email protected]> wrote:
>>
>>
>>
>>> On 2019/11/15 17:07, Peter Zijlstra wrote:
>>>> On Fri, Nov 15, 2019 at 02:47:49PM +0800, Shile Zhang wrote:
>>>>
>>>> +#if defined(SORTTABLE_64) && defined(UNWINDER_ORC_ENABLED)
>>>> +/* ORC unwinder only support X86_64 */
>>>> +#include <errno.h>
>>>> +#include <pthread.h>
>>>> +#include <linux/types.h>
>>>> +
>>>> +#define ORC_REG_UNDEFINED 0
>>>> +#define ERRSTRING_MAXSZ 256
>>>> +
>>>> +struct orc_entry {
>>>> + s16 sp_offset;
>>>> + s16 bp_offset;
>>>> + unsigned sp_reg:4;
>>>> + unsigned bp_reg:4;
>>>> + unsigned type:2;
>>>> + unsigned end:1;
>>>> +} __attribute__((packed));
>>>> +
>>>> +struct orctable_info {
>>>> + size_t orc_size;
>>>> + size_t orc_ip_size;
>>>> +} orctable;
>>> There's ./arch/x86/include/asm/orc_types.h for this. Please don't
>>> duplicate. objtool uses that same header.
>> Good catch! Thanks for your kindly reminder! I'll remove it.
>>>> +/**
>>>> + * sort - sort an array of elements
>>>> + * @base: pointer to data to sort
>>>> + * @num: number of elements
>>>> + * @size: size of each element
>>>> + * @cmp_func: pointer to comparison function
>>>> + * @swap_func: pointer to swap function
>>>> + *
>>>> + * This function does a heapsort on the given array. You may provide a
>>>> + * swap_func function optimized to your element type.
>>>> + *
>>>> + * Sorting time is O(n log n) both on average and worst-case. While
>>>> + * qsort is about 20% faster on average, it suffers from exploitable
>>>> + * O(n*n) worst-case behavior and extra memory requirements that make
>>>> + * it less suitable for kernel use.
>>>> + *
>>>> + * This code token out of /lib/sort.c.
>>>> + */
>>>> +static void sort(void *base, size_t num, size_t size,
>>>> + int (*cmp_func)(const void *, const void *),
>>>> + void (*swap_func)(void *, void *, int size))
>>>> +{
>>>> + /* pre-scale counters for performance */
>>>> + int i = (num/2 - 1) * size, n = num * size, c, r;
>>>> +
>>>> + /* heapify */
>>>> + for ( ; i >= 0; i -= size) {
>>>> + for (r = i; r * 2 + size < n; r = c) {
>>>> + c = r * 2 + size;
>>>> + if (c < n - size &&
>>>> + cmp_func(base + c, base + c + size) < 0)
>>>> + c += size;
>>>> + if (cmp_func(base + r, base + c) >= 0)
>>>> + break;
>>>> + swap_func(base + r, base + c, size);
>>>> + }
>>>> + }
>>>> +
>>>> + /* sort */
>>>> + for (i = n - size; i > 0; i -= size) {
>>>> + swap_func(base, base + i, size);
>>>> + for (r = 0; r * 2 + size < i; r = c) {
>>>> + c = r * 2 + size;
>>>> + if (c >>> + cmp_func(base + c, base + c + size) < 0)
>>>> + c += size;
>>>> + if (cmp_func(base + r, base + c) >= 0)
>>>> + break;
>>>> + swap_func(base + r, base + c, size);
>>>> + }
>>>> + }
>>>> +}
>>> Do we really need to copy the heapsort implementation? That is, why not
>>> use libc's qsort() ? This is userspace after all.
>> Yes, I think qsort is better choice than copy-paste here. But qsort does not support customized swap func, which is needed for ORC unwind swap two tables together.
>> I think it's hard to do with qsort, so I used sort same with original orc unwind table sort.
> One solution is to make an array of indices 0, 1, 2, etc, and sort that using a comparison function that compares i,j by actually comparing source[i], source[j]. (Or use pointers, but indices are probably faster on a 64-bit machine if you can use 32-bit indices.) Then, after sorting, permute the original array using the now-sorted indices. In the case where swapping is expensive, this is actually faster, since it does exactly n moves instead of O(n log n).

Hi, Andy,

Thanks for your suggestion!
It's works, qsort is faster than heap sort, sort time down from 70ms to
20ms.

I'll update in next version.
Thanks again!

2019-11-18 14:43:41

by Josh Poimboeuf

[permalink] [raw]

Subject: Re: [RFC PATCH v3 7/7] x86/unwind/orc: remove run-time ORC unwind tables sort

On Mon, Nov 18, 2019 at 10:05:02AM +0000, David Laight wrote:
> From: Josh Poimboeuf <[email protected]>
> > 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.

--
Josh