linux-kernel - Re: [PATCH 1/1] ARM: unwind - optimise linked-list searches for modules

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Fri, 25 Jun 2010 18:18:43 +0100
From:	Catalin Marinas <catalin.marinas@....com>
To:	Phil Carmody <ext-phil.2.carmody@...ia.com>
Cc:	linux@....linux.org.uk, linux-arm-kernel@...ts.infradead.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 1/1] ARM: unwind - optimise linked-list searches for
 modules

On Tue, 2010-06-15 at 13:46 +0100, Phil Carmody wrote:
> With several sections per module, and dozens of modules, the
> searches down the linked list would dominate the lookup time,
> dwarfing any savings from the binary search within the section.
> 
> A simple move-to-front optimisation exploits the commonality
> of the code paths taken, and in simple real-world tests reduces
> the number of steps in the search to barely more than 1.
> 
> Signed-off-by: Phil Carmody <ext-phil.2.carmody@...ia.com>
> ---
>  arch/arm/kernel/unwind.c |    2 ++
>  1 files changed, 2 insertions(+), 0 deletions(-)
> 
> diff --git a/arch/arm/kernel/unwind.c b/arch/arm/kernel/unwind.c
> index dd81a91..2e88abf 100644
> --- a/arch/arm/kernel/unwind.c
> +++ b/arch/arm/kernel/unwind.c
> @@ -146,6 +146,8 @@ static struct unwind_idx *unwind_find_idx(unsigned long addr)
>                             addr < table->end_addr) {
>                                 idx = search_index(addr, table->start,
>                                                    table->stop - 1);
> +                               /* MTF with 50 modules: 80 steps becomes ~1 */
> +                               list_move(&table->list, &unwind_tables);

That's a good optimisation. Could you please expand the "MTF" comment in
the code a bit more? Otherwise,

Acked-by: Catalin Marinas <catalin.marinas@....com>

-- 
Catalin

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/