Sunday, October 10, 2010

1 day in sentosa (圣淘沙一日游)

其实只是第二次到圣淘沙岛,回首在新加坡的一年

Siloso Beach - Sentosa - Singapore - 2010.10


Tuesday, August 17, 2010

编译无需initrd能自启动之Linux内核:要点

使用 initrd (or initramfs) 固然有很多优点,但无可置疑地拖慢了启动速度,这方面编译内核的文档虽多,但我发现还是有不少人因曾经编译失败不能启动的体验而被吓住了,或者因保守起见编译了太多本机不需要的驱动程序,这样拖慢了编译内核的速度 (而且不管是模块形式还是内核形式,都是要么浪费了硬盘空间、要么就浪费了内存);
这方面记录几个要点,保证所生成的内核一定能够自启动。如果还不能启动请联系我。

1. 硬盘驱动程序 (或曰主板驱动?)
怎样找到正确的硬盘驱动程序?有人的经验谈是确保选中 ahci, 其实这只是一种流行的选择,当然不能代表所有。发现正确驱动程序的方法是顺着 sysfs 找,这里面提供了非常丰富的信息:
    $ ls -lU /sys/block/sda
lrwxrwxrwx 1 root root 0 2010-08-17 21:03 /sys/block/sda -> ../devices/pci0000:00/0000:00:14.1/host4/target4:0:0/4:0:0:0/block/sda
发现了它在 /devices 下的真正节点是 "/devices/pci0000:00/0000:00:14.1" (而不在 host4 下,想想), 这时再一次访问
    $ ls -lU /sys/devices/pci0000:00/0000:00:14.1
其下 driver -> ../../../bus/pci/drivers/pata_atiixp 因此,此机器上正确的驱动程序是 pata_atiixp,
  找到了正确的驱动程序之后还有一个任务是在 menuconfig 阶段如何找到其对应哪一个菜单项?这个需要在源代码中搜索:
    $ find drivers/ -name Makefile |xargs grep -nw pata_atiixp
drivers/ata/Makefile:28:obj-$(CONFIG_PATA_ATIIXP)    += pata_atiixp.o
  不知道在内核哪个子目录的话就在根目录 find, 一般来说大概知道是在 drivers/ 子目录,省点时间, 搜索所有 Makefile 将结果传给 xargs grep -nw 搜索单词 pata_atiixp, 得到唯一的一个结果 是 CONFIG_PATA_ATIIXP, 这个也许你猜到了结果其实就是小写变大写,但实际中有很多驱动的模块名称与 CONFIG 配置项名称是不一样的。所以 find 搜索能保证一定能找到了 menuconfig 配置项;
  最后一步就是在 menuconfig 过程中,使用 "/" 键,调出搜索界面,输入 PATA_ATIIXP 搜索之,一般来说,就找到了准确的 pata_atiixp 驱动所在菜单项的位置。把它设置为内联编译 (inlined compiling)就可以了。
以当前硬件流行驱动一般都是SATA或者PATA,都在 Device Drivers \ SerialATA and Parallel ATA 目录,而且一般来说一个机器只需要一个此类驱动就足够了 (同时使用两种SATA硬件的还没见过),因此选上 pata_atiixp 之后, 其它选项皆禁用之。
2. 根文件系统
  大概调查一下 (df -Th), 判断一下 根文件系统的类型,是 ext4 还是 btrfs, 与上同理,也把它设置为内联编译。为了常用U盘可以加上FAT支持,其它文件系统皆禁用之。
(注意不要选内核NTFS, 真正要读写NTFS分区可以使用 ntfs-3g 项目全用户层 code 解决)

有了这两点根本上就足够自启动了,以此为出发也可以继续把网卡驱动找出来,
3. 从 /sys/class/net/... 出发,找到 eth0 的真正驱动程序,在源代码搜索 Makefile 找到配置项名称,在 menuconfig 找到菜单项,设为内联编译;其它无关网卡驱动皆清除之。

(最后,清除了若干驱动并且保证了可以自启动的内核,在当前双核系统上一般五分钟编译出来。)

Saturday, August 07, 2010

Latest Tweet: http://twitgoo.com/1gm3yp L: http://is.gd/e7hZJ Bencoolen Link N 1°18' 0'' / E 103°51' 0'' 萌古连商业中心 & 福禄寺 四面佛

新加坡:宗教的和平相处

福禄寺 四面佛
印度庙 Sri Krishnan Temple 正在举行大型庆祝140周年活动,对面观音堂佛祖庙固自门庭若市

此外,市区还有基督教(圣公会、卫理公会感恩堂、长老会、天主堂等若干分支)、马来回教、犹太教堂若干。

Thursday, July 22, 2010

见到了 Dawn Song 和 周杰伦

http://www.tektalk.org/2008/04/21/海外学人–宋晓东(dawn-song)/
  1. crquan 于 2010-07-21 4:52 pm
    今天到新加坡国大NUS算是亲眼见识了 Dawn Song 之 aggressive, 语速、以及思维转换之快皆非常人所能及也,在1个小时的Seminar里讲了三个普通Seminar的内容,其在UCBerkeley的最新研究是 webblaze, 在Web安全领域的最新Symbolic应用;并且相关 paper 又是其一贯的对security领域四大TOP1会议(IEEE S&P, Usenix security, ACM CCS, NDSS)皆灌水之
    http://webblaze.cs.berkeley.edu/

晚餐在 Bugis 才吃过, 得闻前方有一新加坡闻名小吃街,步行至与 Beach Road 有一条 Link 小径,两旁都是古式三层复式楼;只闻海南鸡饭、以及麻辣飘香、港汇茶点,食客都热情到自己帮忙把店家的桌子往外搬到行人街道,尚有余而不得座者;行间忽见不远处 Bugis 广场有排队长龙, 怕是又有什么大人物吧!走近看,竟然才知是周杰伦,排队者每人皆持两本唱片,黑皮不见其名,排队者约有上千人,等待上台亲笔签名;远处舞台之上有某人伏笔挥持;颇有神采;待良久,竟不能得见全貌;

Sunday, July 04, 2010

Latest Tweet: http://www.nudt.edu.cn/summerschool/chn/recruitinfo.html 今闻母校国防科大开设“天河计划”研究生国际暑期班(7月19日至8月6日),招生正式七十人、旁听四十人、由国际知名教授、全英文授课、云计算及无线前沿技术、费用全免、西部地区学校正式学员报销往返硬座火车票。报名截止7月10日。

1.课程教学:(每门课程为1个学分)
    1).云计算和虚拟化技术(Prof. Kai Hwang)
    2).无线和移动网络(Prof. WEI WAYNE LI)
    3).高级软件工程(Prof. Haibin Zhu )


找到了三位教授的背景分别是:

    1). Prof. Kai Hwang
毕业于1972年、加州大学伯克利分校博士、现任南加州大学教授、主研并行计算方向
Ph.D. in Electrical Engineering and Computer Science, 1972, UC, Berkeley, Berkeley, CA.  http://ee.usc.edu/faculty_staff/faculty_directory/hwang.htm

    2). Prof. WEI WAYNE LI
南德州大学计算机系教授,主研无线自适应网络方向;
http://engineering.tsu.edu/~wli/

    3).Prof. Haibin Zhu
加拿大尼普森大学计算机系教授,主研软件工程、人机交互;
http://www.nipissingu.ca/faculty/haibinz/

大学所需要的,正是这种不为名、不为利、的教学和科研精神;多一些踏实的研究、少一些银河麒麟般闹剧;希望母校夙愿“建设世界一流大学”有朝一日能够实现!

(同感于1help1@tektalk, 如能开放视频,做成类似于 MIT-Open-Web-Course, 就更精彩了!)
http://www.tektalk.org/2010/07/03/天河计划/

Tuesday, June 29, 2010


Unwired 2010, 05-27, SMU Administration Building, Conference Hall

Tuesday, June 15, 2010

File: make.info, Node: Double-Colon, Next: Automatic Prerequisites, Prev: Static Pattern, Up: Rules

4.13 Double-Colon Rules
=======================

"Double-colon" rules are rules written with `::' instead of `:' after
the target names. They are handled differently from ordinary rules
when the same target appears in more than one rule.

When a target appears in multiple rules, all the rules must be the
same type: all ordinary, or all double-colon. If they are
double-colon, each of them is independent of the others. Each
double-colon rule's commands are executed if the target is older than
any prerequisites of that rule. If there are no prerequisites for that
rule, its commands are always executed (even if the target already
exists). This can result in executing none, any, or all of the
double-colon rules.

Double-colon rules with the same target are in fact completely
separate from one another. Each double-colon rule is processed
individually, just as rules with different targets are processed.

The double-colon rules for a target are executed in the order they
appear in the makefile. However, the cases where double-colon rules
really make sense are those where the order of executing the commands
would not matter.

Double-colon rules are somewhat obscure and not often very useful;
they provide a mechanism for cases in which the method used to update a
target differs depending on which prerequisite files caused the update,
and such cases are rare.

Each double-colon rule should specify commands; if it does not, an
implicit rule will be used if one applies. *Note Using Implicit Rules:
Implicit Rules.




--zz-Info:(make.info.gz)Double-Colon,36 行 --All-- 子文件:make.info-1.gz-----------------------------

Monday, May 10, 2010

JVM, Longene in Linux Kernel [Was Re: 为什么不把JVM加入Kernel呢?(Why not add JVM into Kernel)]

Cheng Renquan
crquan在gmail.com


星期二 五月 11 14:17:48 CST 2010



2010/5/7 Liang Guo <bluestonechina at gmail.com>:
>
> 在 2010年5月7日 下午4:47,Avanpak <slevin.van at gmail.com>写道:

>>
>> Linux下有很多Java应用,如openoffice,
>> 为什么不把JVM加入Kernel,让这些应用跑起来更顺畅呢?
>>
>> There're many Java applications on Linux, such as openoffice.
>> Why not add JVM into Kernel, and let them run better.
>
> Why do you think JVM in kernel space is better in user space ?

我个人觉得:除了法律、GPL的要求之外,没有什么技术上的理由说 JVM 不可以放进内核,

我想真正唯一的理由是:谁去做它? 谁有能力、有需求的人士不妨可以去尝试,
但当前有没有谁想去接上这个活儿,这是个问题,

当时 03,04 年我们还在 linuxsir 的内核区讨论 “把 XWindow 移进内核让它像
运行Windows图形一样快, 如何?”, 支持和反对者辩论了很久,支持者认为会提高性能
让Linux图形和Windows一样快,反对者认为会引入BUG让Linux像Windows一样不稳定,
经常崩溃;这样的辩论在各 Linux 社区都时常可见,但都没什么结果,因为没有人真正
去做,全部都是空谈没有意义,
http://www.linuxsir.org/bbs/thread147361-1.html

我们当时确实没有能力去实现 内核态XWindow 这么一件大工程,现在来看,内核模式设定
 KMS 可以被 内核接受,被各Linux发行版引用,其本质就是把一部分 XWindow代码移进了
内核态运行 (Xorg 的显卡驱动的一部分,), 证实了这个方向确实是可行的,

@Avanpak, 你说的内核态JVM是目的让 内核态直接能运行 Java应用程序的class 文件?
这样以后运行 Eclipse 确实应该快些,

位于 杭州 - 浙大网新 - 毛德操老师引领的 Longene 项目与此目的倒是有些类似,
让 Linux内核直接运行Windows的PE格式exe可执行程序,
http://www.longene.org/

初期版本的方案是内核模式的wine, 但0.3版以后实现有改变?其git仓库还是没变化,Jack能否发布点文档?

"longene-0.3初步定于5月底发布,新版本将去除wineserver,所有功能在内核模块中完成。敬请期待!"
"整体移植wineserver至模块中,所有发往wineserver的请求通过系统调用方式直接进入内核,
在wine中去掉wineserver进程。移植完成后,预计完成后性能会有较大地提高。"

http://www.longene.org/newslist.php
http://www.longene.org/forum/viewtopic.php?f=2&t=4159
http://www.longene.org/gitweb/?p=unifiedkernel.git

回到 JVM 和 Logene 问题本身,技术上没有什么不可以做的,有了需求,有了 motivation,
还要有人坚持不懈把它做出来才行,Avanpak 您愿意开始 内核JVM 工作吗?

>
> --
> Liang Guo
> http://bluestone.cublog.cn

--
Cheng Renquan






关于邮件列表 Linux-kernel 的更多信息

From http://zh-kernel.org/pipermail/linux-kernel/2010-May/014526.html, http://groups.google.com.sg/group/szlug/msg/928bf660dd5b3f3a

Tuesday, March 30, 2010

Monday, March 08, 2010

Friday, March 05, 2010

suseuser@linux-2.6.33-uk> PAGER= git log --no-merges --pretty="%h %s" v2.6.30..v2.6.33 -- kernel/fork.c
fabf318 sched: Fix fork vs hotplug vs cpuset namespaces
9cd80bb do_wait() optimization: do not place sub-threads on task_struct->children list
6580807 ptrace: copy_process() should disable stepping
569b846 memcg: coalesce uncharge during unmap/truncate
1d61548 sched: Convert pi_lock to raw_spinlock
b69f229 block: Fix io_context leak after failure of clone with CLONE_IO
0cf55e1 sched, cputime: Introduce thread_group_times()
d99ca3b sched, cputime: Cleanups related to task_times()
8e7cac7 core: Fix user return notifier on fork()
1d51075 Correct nr_processes() when CPUs have been unplugged
322a2c1 futex: Move exit_pi_state() call to release_mm()
fc6b177 futex: Nullify robust lists after cleanup
801460d task_struct cleanup: move binfmt field to mm_struct
858f099 aio: ifdef fields in mm_struct
123be07 fork(): disable CLONE_PARENT for init
d899bf7 procfs: provide stack information for threads
1f10206 getrusage: fill ru_maxrss value
28b83c5 oom: move oom_adj value from task_struct to signal_struct
1c2fb7a ksm: fix deadlock with munlock in exit_mmap
9ba6929 ksm: fix oom deadlock
f8af4da ksm: the mm interface to ksm
c6a7f57 mm: oom analysis: Show kernel stack usage in /proc/meminfo and OOM log output
cdd6c48 perf: Do the big rename: Performance Counters -> Performance Events
e0e8173 CRED: Add some configurable debugging [try #6]
4ab6c08 clone(): fix race between copy_process() and de_thread()
f41d911 rcu: Merge preemptable-RCU functionality into hierarchical RCU
0753ba0 mm: revert "oom: move oom_adj value"
9c8a822 execve: must clear current->clear_child_tid
42c4ab4 itimers: Merge ITIMER_VIRT and ITIMER_PROF
9f498cc perf_counter: Full task tracing
933b787 mm: copy over oom_adj value at fork time
ed900c0 perf_counter: Log vfork as a fork event
b43f3cb headers: mnt_namespace.h redux
72a1de3 copy_process(): remove the unneeded clear_tsk_thread_flag(TIF_SIGPENDING)
2dff440 kmemcheck: add mm functions
60313eb perf_counter: Add fork event
226f62f perf_counter: Add a comm hook for pure fork()s
f7e8b61 function-graph: move initialization of new tasks up in fork
bbbee90 perf_counter: Ammend cleanup in fork() fail
6ab423e perf_counter: Propagate inheritance failures down the fork() path
e4cbb4e perf_counter: Move child perfcounter init to after scheduler init
a63eaf3 perf_counter: Dynamically allocate tasks' perf_counter_context struct
ad8d75f tracing/events: move trace point headers into include/trace/events
a8d154b tracing: create automated trace defines
0f48140 x86, ptrace: add bts context unconditionally
0793a61 performance counters: core code

Tuesday, March 02, 2010

关于缓冲区溢出, lostyard 同学有一篇报道 gcc-4.4.1 上的最新进展, 就是 gcc 会产生 %gs:0x14 校验代码,新的攻击代码必须能注意到它的存在并合适绕过它才行,

检查了一下 gcc 手册,发现它是 -fstack-protector 生成的,这个 feature 手册上描述是在 -O1,2,... 各优化级别之外的,可能还有 bug 的额外优化选项, gentoo 上的 gcc 编译器也是遵照这个实现,不知 Ubuntu 为什么把它变成了缺省的,就是默认 enable 这个选项。

这个选项的原理就是在栈上额外分配 0,4,8,12,16 字节内存,使用 %gs:0x14 进行赋值,在函数结束时检查所赋值是否还存在,如果变化了说明栈可能遭受了溢出攻击,运行它会提示 "stack smashing"

$ ./a.out
0xffe80358, ffe80374
0xffe80354, 0
*** stack smashing detected ***: ./a.out terminated
======= Backtrace: =========
/lib32/libc.so.6(__fortify_fail+0x48)[0xf76dd228]
/lib32/libc.so.6(__fortify_fail+0x0)[0xf76dd1e0]
./a.out[0x80484fd]
[0x41414141]
======= Memory map: ========
08048000-08049000 r-xp 00000000 08:09 130818                             /home/gektop/tmp/test/a.out
08049000-0804a000 r--p 00000000 08:09 130818                             /home/gektop/tmp/test/a.out
0804a000-0804b000 rw-p 00001000 08:09 130818                             /home/gektop/tmp/test/a.out
085d1000-085f2000 rw-p 00000000 00:00 0                                  [heap]
f75f6000-f75f7000 rw-p 00000000 00:00 0 
f75f7000-f7734000 r-xp 00000000 08:0a 5808                               /lib32/libc-2.9.so
f7734000-f7736000 r--p 0013d000 08:0a 5808                               /lib32/libc-2.9.so
f7736000-f7737000 rw-p 0013f000 08:0a 5808                               /lib32/libc-2.9.so
f7737000-f773a000 rw-p 00000000 00:00 0 
f773e000-f774a000 r-xp 00000000 08:0a 5784                               /lib32/libgcc_s.so.1
f774a000-f774b000 r--p 0000b000 08:0a 5784                               /lib32/libgcc_s.so.1
f774b000-f774c000 rw-p 0000c000 08:0a 5784                               /lib32/libgcc_s.so.1
f774c000-f774e000 rw-p 00000000 00:00 0 
f774e000-f774f000 r-xp 00000000 00:00 0                                  [vdso]
f774f000-f776b000 r-xp 00000000 08:0a 5810                               /lib32/ld-2.9.so
f776b000-f776c000 r--p 0001c000 08:0a 5810                               /lib32/ld-2.9.so
f776c000-f776d000 rw-p 0001d000 08:0a 5810                               /lib32/ld-2.9.so
ffe6d000-ffe82000 rw-p 00000000 00:00 0                                  [stack]
Aborted


只要能理解它的原理就可以了,演示的时候可以为了减少无关干扰项,可以使用 -fno-stack-protector 把它关闭。

Thursday, February 18, 2010

Sunday, February 07, 2010

Thursday, January 28, 2010

www.sun.com: 301 Moved Permanently

$ curl -v www.sun.com
* About to connect() to www.sun.com port 80 (#0)
* Trying 72.5.124.61... connected
* Connected to www.sun.com (72.5.124.61) port 80 (#0)
> GET / HTTP/1.1
> User-Agent: curl/7.19.7 (i386-redhat-linux-gnu) libcurl/7.19.7 NSS/3.12.4.5 zlib/1.2.3 libidn/1.9 libssh2/1.2
> Host: www.sun.com
> Accept: */*
>
< HTTP/1.1 301 Moved Permanently

< Server: Sun-Java-System-Web-Server/7.0
< Date: Fri, 29 Jan 2010 05:38:56 GMT
< P3p: policyref="http://www.sun.com/p3p/Sun_P3P_Policy.xml", CP="CAO DSP COR CUR ADMa DEVa TAIa PSAa PSDa CONi TELi OUR SAMi PUBi IND PHY ONL PUR COM NAV INT DEM CNT STA POL PRE GOV"
< Location: http://www.oracle.com
< Content-length: 0
< Connection: Keep-Alive
< Age: 0
<
* Connection #0 to host www.sun.com left intact
* Closing connection #0

Tuesday, January 12, 2010

南洋随笔录之一: 纪念碑


日本占据时期死难人民纪念碑

 http://www.sccci.org.sg/index.cfm?GPID=1189

 位于市政厅(CityHall)与繁荣的现代商业城SuntecCity之间,是一片小型的广场,喷泉假山之间,中央便是这座庄严肃穆的纪念碑,碑文纪录相对简单,谨以此纪念日军占领期间死亡的新加坡人民;石碑正中呈四柱型,分别有中,英,马来,印度(Tamil)四种文字碑文,代表共同生活在这里的三个主要种族和使用的四种语言.暮色中石碑直指擎天,苍劲雄浑.与周围翠柏交相辉映.

其时1942年2月15日,日本攻陷新加坡,随后3年半至45年8月无条件投降,不完全统计有5万名新加坡华人遭杀害。日本占领时期死难人民纪念碑于1967年2月15日落成。此后,新加坡每年都要在纪念碑旁举行悼念活动。这里没有人民英雄纪念碑,本来没有英雄,战争所带来的,唯有苦难.

未知南京是否也有类似碑文,有机会当亲往拜访.

Friday, January 08, 2010

Samsung Developer Night

Samsung Developer Night, tonight, was really more like a social event, while some people there may be real developers, I've chatted with some of them, really exciting technology;

The first session is about SAMSUNG's own app store, while with this business model, I can say nothing about it, apple iphone has done it successfully, that does not mean every one can copy this model, SAMSUNG as a role of independent mobile phone producer, who can  predict its success, I have a lot of doubt, but inappropriate in event like this, especially sponsorred by samsung, i have enjoyed good drinks and a fairly good dinner here, so let's just skip this;

Our real focus is on the samsung's new smartphone os project, Bada system, as illustrated in speaker's slides, Bada has its own kernel (maybe linux or other real-time kernel?), and its own graphical interface(maybe recently sponsored project, enlightenment, or e17 ?), after the topics speach, I asked questions with samsung staff, got positive replies, so it's true; I recall the Linux-based mobile/netbook project, there are already Linux Mortorola, Android by Google, Moblin by Intel, Mameo by Nokia, and alread cancelled OpenMoko project, hope there will be more and more linux based mobile os, everyone has the potential development power can hold such a system, samsung is just one of them, almost all pre-existing samsung smartphone are win based, some other symbian, some other Android, it just want more control on source os level software, but unfortunately it's still controlled by others, so it's the intention of Bad;

Documents showed that first real Bada would be coming in Mobile World Congress 2010, Bacelona, who cares?

Some friend just heard this named it's bad a thing, pronounces badly, but in fact, accroding to its official explaination, Bada means ocean in Korean, which we know little about, right? So it's just a name, let's keep interests on what can be done through Bada;

http://www.e27.sg/2010/01/04/samsung-developer-night/
http://www.linux-magazine.com/Online/News/Samsung-Sponsors-Enlightenment-Development-New-Light-for-E17/
http://www.bada.com/developer/day/

Wednesday, January 06, 2010

阅读内核:二叉搜索算法中一个常见的被很多人忽略的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