Hi Paul,
I'm just wondering what are your latest thoughts about this patch
(http://patchwork.ozlabs.org/linuxppc/patch?id=14707).
Cheers,
Emil.
> -Original Message-
> From: Medve Emilian
> Sent: Tuesday, November 13, 2007 10:24 AM
> To: [EMAIL PROTECTED]; [EMAIL PROTECTED]; [EMAIL PROTECTED];
> [EMAIL PROTECTED]; [EMAIL PROTECTED];
> [EMAIL PROTECTED]; [EMAIL PROTECTED];
> linuxppc-embedded@ozlabs.org
> Cc: Medve Emilian
> Subject: [PATCH v2] [POWERPC] Optimize counting distinct
> entries in the relocation sections
>
> When a module has relocation sections with tens of thousands
> worth of entries,
> counting the distinct/unique entries only (i.e. no
> duplicates) at load time can
> take tens of seconds and up to minutes. The sore point is the
> count_relocs()
> function which is called as part of the architecture specific
> module loading
> processing path:
>
> -> load_module()generic
> -> module_frob_arch_sections() arch specific
> -> get_plt_size() 32-bit
> -> get_stubs_size() 64-bit
>-> count_relocs()
>
> (Not sure why the relocation tables could contain lots of
> duplicates and why
> they are not trimmed at compile time by the linker. In some
> test cases, out of
> 35K relocation entries only 1.5K were distinct/unique)
>
> The previous counting algorithm was having O(n^2) complexity.
> Basically two
> solutions were proposed on the e-mail list: a hash based
> approach and a sort
> based approach
>
> The hash based approach is the fastest (O(n)) but the has it
> needs additional
> memory and for certain corner cases it could take lots of
> memory due to the
> degeneration of the hash. One such proposal was submitted here:
>
> http://ozlabs.org/pipermail/linuxppc-dev/2007-June/037641.html
>
> In this proposal, the symbol + addendum are hashed to
> generate a key and a
> pointer to the relocation entry will be stored in it. The
> hash is implemented as
> a linked list of memory pages with PAGE_SIZE /
> sizeof(Elfxx_Rela *) entries. In
> case of collisions in all the existing pages, a new page is
> added to the list to
> accommodate the new distinct relocation entry
>
> For 32-bit PowerPCs with 4K pages, a page can accommodate 1K
> worth of pointers
> to relocation entries. In the 35K entries scenario, as
> much/little of six (6)
> pages could be allocated using 24K of extra memory during the
> module load
>
> The sort based approach is slower (O(n * log n + n)) but if
> the sorting is done
> "in place" it doesn't need additional memory. A proposal was
> submitted here:
>
> http://ozlabs.org/pipermail/linuxppc-dev/2007-November/045854.html
> (http://patchwork.ozlabs.org/linuxppc/patch?filter=default&id=14573)
>
> In this proposal an array of pointers to the relocation
> entries is built and
> then is sorted using the kernel sort() utility function. This
> is basically a heap
> sort algorithm with a stable O(n * log n) complexity. With
> this counting the
> distinct/unique entries is just linear (O(n)) complexity. The
> problem is the
> extra memory needed in this proposal, which in the 35K
> relocation entries test
> case it can be as much as 140K (for 32-bit PowerPCs; double
> for 64-bit). This is
> much more then the memory needed by the hash based approach described
> above/earlier but it doesn't hide potential degenerative corner cases
>
> The current patch is a happy compromise between the two
> proposals above:
> O(n + n * log n) performance with no additional memory
> requirements due to
> sorting in place the relocation table itself
>
> Signed-off-by: Emil Medve <[EMAIL PROTECTED]>
> ---
>
> This patch only tries to address counting the distinct
> R_PPC_REL24 entries for
> the purpose of sizing the PLT. This operation was/can be
> detected by the proper
> kernel logic as a soft lockup for large relocation tables
>
> A related optimization (that could cause rewriting the this
> patch) is to
> optimize the PLT search from do_plt_call() but that doesn't
> seem to be a
> problem right now
>
> The errors below are false positives due to the fact that
> Elfxx_Rela are
> falsely assumed to be variables/operands instead of types:
>
> linux-2.6> scripts/checkpatch.pl
> 0001-POWERPC-Optimize-counting-distinct-entries-in-the.patch
> ERROR: need consistent spacing around '*' (ctx:WxV)
> #116: FILE: arch/powerpc/kernel/module_32.c:78:
> + const Elf32_Rela *x, *y;
> ^
>
> ERROR: need consistent spacing around '*' (ctx:WxV)
> #228: FILE: arch/powerpc/kernel/module_64.c:122:
> + const Elf64_Rela *x, *y;
> ^
>
> total: 2 errors, 0 warnings, 218 lines checked
> Your patch has style problems, please review. If any of these errors
> are false positives report them to the maintainer, see
> CHECKPATCH in MAINTAINERS.
>
> arch/powerpc/kernel/module_32.c | 77
> +
