见到了 Dawn Song 和 周杰伦
http://www.tektalk.org/2008/04/21/海外学人–宋晓东（dawn-song）/
晚餐在 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/天河计划/
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 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-----------------------------
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 Renquancrquan在gmail.com
星期二 五月 11 14:17:48 CST 2010
- 上一条消息 如何在内核中添加kdb？
- 信息排序方式:
[ 日期 ]
[ 线索 ]
[ 主题 ]
[ 作者 ]
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
- 上一条消息 如何在内核中添加kdb？
- 信息排序方式:
[ 日期 ]
[ 线索 ]
[ 主题 ]
[ 作者 ]
关于邮件列表 Linux-kernel 的更多信息
From http://zh-kernel.org/pipermail/linux-kernel/2010-May/014526.html, http://groups.google.com.sg/group/szlug/msg/928bf660dd5b3f3a
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"
只要能理解它的原理就可以了，演示的时候可以为了减少无关干扰项，可以使用 -fno-stack-protector 把它关闭。
检查了一下 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, 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/
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 中有一个 >>> 是针对无符号数的运算符，可以写得更简便：
二叉搜索的实现，如其所料，大部分人写的实现都有这个整数溢出问题。
--
Cheng Renquan (程任全), from Singapore
对于已排序对象的查找，二叉搜索算法是一个常见的优化算法，时间复杂度是 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
Wednesday, December 23, 2009
compare the evolution of hard irq implementation, you will find that hard irq numbers has shifted from 0x20~0x2f to 0x30~0x3f, but why someone need this change?
http://lxr.linux.no/#linux+v2.6.26/include/asm-x86/mach-default/irq_vectors.h
http://lxr.linux.no/#linux+v2.6.32/arch/x86/include/asm/irq_vectors.h
from oldlinux such as v0.11, as analyzed version as Doctor Zhao Jiong did, an old version just use it for the hardware limit, in the old 8259 interrupt controller days, the hardware 8259 is cascaded by 2 chips, and its real capability is only to handle 8 hard interrupt, by cascading style of implementation, there's another number is occupied by cascade, so there's only 7+8 = 15 interrupt numbers, every PC operating systems just re-program the 8259 IC, except for the intact PC standard, its 0x8~0xf for the first, and 0x78~0x7f for the second cascaded one, that can work well under 8086 Intel real mode, the DOS operating system keep it unchanged, and use int 0x21 as the system call service, then Linux re-program it as in the protected programming mode, for CPU internal usage, it reserved 0x0~0x1f 32 interrupt numbers; for the sake of x86 instruction encoding style, "int 0x80" is encoded as "0xcd 0x80", the interrupt number is just occupying one byte, so the CPU hardware limit is 256 int numbers, minus 32 reserved for CPU internal usage, it's 224 left, also as stated in the v2.6.26 irq_vectors.h comments said; Linux just use 0x80 as the system call interface, and shift/re-program 8259 to 0x20~0x27 and 0x28~0x2f; so the other range 0x30~0x7f, and 0x81~0xff are all unused; SMP architect is still strange, it generates special interrupts btween 0xee~0xff (238 ... 255); according to some recent secret unleashed, microsoft windows utilized 0x2e as the interrupt number, so the Linux int numbers changes just kept an reserved space for the unified kernel project; maybe it should be merged into mainstream someday;
http://www.oldlinux.org/
http://lxr.linux.no/#linux+v2.6.26/include/asm-x86/mach-default/irq_vectors.h
http://lxr.linux.no/#linux+v2.6.32/arch/x86/include/asm/irq_vectors.h
from oldlinux such as v0.11, as analyzed version as Doctor Zhao Jiong did, an old version just use it for the hardware limit, in the old 8259 interrupt controller days, the hardware 8259 is cascaded by 2 chips, and its real capability is only to handle 8 hard interrupt, by cascading style of implementation, there's another number is occupied by cascade, so there's only 7+8 = 15 interrupt numbers, every PC operating systems just re-program the 8259 IC, except for the intact PC standard, its 0x8~0xf for the first, and 0x78~0x7f for the second cascaded one, that can work well under 8086 Intel real mode, the DOS operating system keep it unchanged, and use int 0x21 as the system call service, then Linux re-program it as in the protected programming mode, for CPU internal usage, it reserved 0x0~0x1f 32 interrupt numbers; for the sake of x86 instruction encoding style, "int 0x80" is encoded as "0xcd 0x80", the interrupt number is just occupying one byte, so the CPU hardware limit is 256 int numbers, minus 32 reserved for CPU internal usage, it's 224 left, also as stated in the v2.6.26 irq_vectors.h comments said; Linux just use 0x80 as the system call interface, and shift/re-program 8259 to 0x20~0x27 and 0x28~0x2f; so the other range 0x30~0x7f, and 0x81~0xff are all unused; SMP architect is still strange, it generates special interrupts btween 0xee~0xff (238 ... 255); according to some recent secret unleashed, microsoft windows utilized 0x2e as the interrupt number, so the Linux int numbers changes just kept an reserved space for the unified kernel project; maybe it should be merged into mainstream someday;
15 * 16 * Vectors 0 ... 31 : system traps and exceptions - hardcoded events 17 * Vectors 32 ... 127 : device interrupts 18 * Vector 128 : legacy int80 syscall interface 19 * Vectors 129 ... 237 : device interrupts 20 * Vectors 238 ... 255 : special interrupts 21 *
http://www.oldlinux.org/
Subscribe to:
Posts (Atom)
http://webblaze.cs.berkeley.edu/