阅读内核：二叉搜索算法中一个常见的被很多人忽略的BUG
对于已排序对象的查找，二叉搜索算法是一个常见的优化算法，时间复杂度是 O(log(n)),
在 Linux 内核中关于符号表的运算中有对它的一个引用；在阅读这个文件的 git 历史中，
有一个变更看起来很让人费解：
$ PAGER= git show -p --stat 2fc9c4e18
commit 2fc9c4e18f94431e7eb77d97edb2a995b46fba55
Author: Vegard Nossum <vegard.nossum@gmail.com>
AuthorDate: Fri Jul 25 01:45:34 2008 -0700
Commit: Linus Torvalds <torvalds@linux-foundation.org>
CommitDate: Fri Jul 25 10:53:27 2008 -0700
kallsyms: fix potential overflow in binary search
This will probably never trigger... but it won't hurt to be careful.
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Signed-off-by: Vegard Nossum <vegard.nossum@gmail.com>
Cc: Joshua Bloch <jjb@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
kernel/kallsyms.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/kernel/kallsyms.c b/kernel/kallsyms.c
index 6fc0040..38fc10a 100644
--- a/kernel/kallsyms.c
+++ b/kernel/kallsyms.c
@@ -176,7 +176,7 @@ static unsigned long get_symbol_pos(unsigned long addr,
high = kallsyms_num_syms;
while (high - low > 1) {
- mid = (low + high) / 2;
+ mid = low + (high - low) / 2;
if (kallsyms_addresses[mid] <= addr)
low = mid;
else
这个 patch 中其实只有一行修改，就是对 get_symbol_pos 函数计算 mid 值的一次小小的修改，
可是，怎么看都不明白： 修改前后的两个算式 "(low + high) / 2" 与 "low + (high - low) / 2" 不是一样的么？
其作者给出 http://googleresearch.blogspot.com 上的一个链接，只有真正看过了才知道：
对于数学表达上看起来一样的式子在工程实践中有很大不同：
1) 数学是完美的符号表达；
2) 工程是要考虑计算机的实现构造：
当 (low+ligh) 超出了 signed int 的最大值 (2(^31) -1) 时，会变为负数，再接下来的下标引用中便会下溢出；
解决方法是修改为 "low + (high - low) / 2" 之类，或者先作无符号整数的强制转换：
6: mid = ((unsigned int)low + (unsigned int)high)) >> 1;
在 Java 中有一个 >>> 是针对无符号数的运算符，可以写得更简便：

6:             int mid = (low + high) >>> 1;

推荐阅读 作者给出的 blogspot 原文，其中提到作者自己的一个小故事: CMU 教授在1堂课上让每个人写出
二叉搜索的实现，如其所料，大部分人写的实现都有这个整数溢出问题。
--
Cheng Renquan (程任全), from Singapore