linux-kernel - Re: [PATCH] module: Use the binary search for symbols resolution

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 for Android: free password hash cracker in your pocket

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

Message-ID: <87aafwceop.fsf@rustcorp.com.au>
Date:	Tue, 12 Apr 2011 13:18:54 +0930
From:	Rusty Russell <rusty@...tcorp.com.au>
To:	Alessio Igor Bogani <abogani@...nel.org>
Cc:	LKML <linux-kernel@...r.kernel.org>,
	Tim Bird <tim.bird@...sony.com>,
	Alessio Igor Bogani <abogani@...nel.org>,
	Tim Abbott <tabbott@...lice.com>
Subject: Re: [PATCH] module: Use the binary search for symbols resolution

On Tue,  5 Apr 2011 19:22:26 +0200, Alessio Igor Bogani <abogani@...nel.org> wrote:
> Let the linker sort the exported symbols and use the binary search for
> locate them.

OK, but why is this optional?

Also note that each_symbol() has an out-of-tree user in ksplice, so
changing the semantics to always search for a particular name might
break them.

Assuming they need it, we could rename it (so they can easily detect the
change) to search_symbol() and make it take a comparitor fn and a
"found" function.

So we want this as three patches, I think:
1) Change each_symbol() to search_symbol() as detailed above.
2) Change symbol tables to be sorted.
3) Change module code to do binary search.

That means we can tell exactly *what* breaks things in linux-next :)

Also:
>  	for (j = 0; j < arrsize; j++) {
> -		for (i = 0; i < arr[j].stop - arr[j].start; i++)
> -			if (fn(&arr[j], owner, i, data))
> +#ifdef CONFIG_SYMBOLS_BSEARCH
> +		num = arr[j].stop - arr[j].start;
> +		start = 0, end = num - 1, mid, result;
> +		while (start <= end) {
> +			mid = (start + end) / 2;
> +			result = strcmp(fsa->name, arr[j].start[mid].name);
> +			if (result < 0)
> +				end = mid - 1;
> +			else if (result > 0)
> +				start = mid + 1;
> +			else
> +				if (fn(&arr[j], owner, mid, data))
> +					return true;
> +		}
> +#else

This will loop forever if rn() returns false!  You want

     return fn(&arr[j], owner, mid, data)

I think.

But very neat work!
Rusty.
--
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/