linux-kernel - Re: [PATCH RFC 1/5] scripts: Add sortextable to sort the kernel's exception table.

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <4ECA9D9A.5040006@gmail.com>
Date:	Mon, 21 Nov 2011 10:51:06 -0800
From:	David Daney <ddaney.cavm@...il.com>
To:	"H. Peter Anvin" <hpa@...nel.org>
CC:	linux-mips@...ux-mips.org, ralf@...ux-mips.org,
	linux-kernel@...r.kernel.org, linux-arch@...r.kernel.org,
	linux-embedded@...r.kernel.org, x86@...nel.org,
	David Daney <david.daney@...ium.com>
Subject: Re: [PATCH RFC 1/5] scripts: Add sortextable to sort the kernel's
 exception table.

On 11/20/2011 03:26 PM, H. Peter Anvin wrote:
> On 11/18/2011 11:37 AM, David Daney wrote:
>> From: David Daney<david.daney@...ium.com>
>>
>> Using this build-time sort saves time booting as we don't have to burn
>> cycles sorting the exception table.
>>
>
> If we're going to do this at build time, I would suggest using a
> collisionless hash instead.  The lookup time for those are O(1), but
> they definitely need to be done at build time.
>

It is my understanding that such a hash table would be sparsely 
populated, so space would have to be reserved for the empty buckets. 
The current patch, which works in-place on the fully linked vmlinux, 
doesn't have to worry about finding enough space for the table.

If we were to do the collisionless hash, we would somehow have to 
reserve space for the empty buckets.

On my test kernel, there were only 1453 entries in the exception table, 
So doing the binary search takes a maximum of 11 loads.

So, I guess I am not strongly opposed to using a collisionless hash, but 
I think it may not be worth the extra effort.

David Daney
--
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/