都是贝贝拍的，儿子是个好帮手啊。
Saturday, November 19, 2011
Tuesday, November 15, 2011
double free is dangerous
Today, a double free of a pointer caused a crash in the program, which is hard to detect. One of my colleagues helped me pin down the problem and fixed it.
As we all know, if a block memory is allocated through malloc() or new(), we must remember to free() or delete() the pointer (pointing to the memory block allocated) later. And it is perfectly legal in C/C++ to free/delete a null pointer. So we usually don't bother to check whether the pointer is null before freeing it. And fewer programmers will set the pointer to null after the memory is freed.
Yet, this is a bad practice. Consider the following scenario:
---
char *p = (char *)malloc(1024);
... //some string operations involving p
free(p);
free(p);
---
Definitely, it will cause a core dump. Here is the reason: After the first free(), the memory pointed to by p is deallocated and reclaimed by the system. But p is not set to null yet. In this case, it is called a dangling pointer. What is points to is undetermined and unknown. When the second free() is run on the dangling pointer, the system is tring to free a block of memory not in use any more! The best result you can expect is a core dump.
The solution is simple. Just set the pointer to null after it is freed. Usually, we wrap it up in a macro.
---
#define SAFE_FREE(p) if ((p) != NULL) do {free((p)); (p) = NULL;} while (0)
---
It is a common practice to wrap up multiple statements of a macro into a do {...} while (0) loop, with no terminating semicolon.This allows the macro to be used like a single statement in any location, such as the body of an if statement, while still allowing a semicolon to be placed after the macro invocation without creating a null statement.
References:
http://stackoverflow.com/questions/2468853/freeing-memory-twice
http://en.wikibooks.org/wiki/C_Programming/Common_practices
As we all know, if a block memory is allocated through malloc() or new(), we must remember to free() or delete() the pointer (pointing to the memory block allocated) later. And it is perfectly legal in C/C++ to free/delete a null pointer. So we usually don't bother to check whether the pointer is null before freeing it. And fewer programmers will set the pointer to null after the memory is freed.
Yet, this is a bad practice. Consider the following scenario:
---
char *p = (char *)malloc(1024);
... //some string operations involving p
free(p);
free(p);
---
Definitely, it will cause a core dump. Here is the reason: After the first free(), the memory pointed to by p is deallocated and reclaimed by the system. But p is not set to null yet. In this case, it is called a dangling pointer. What is points to is undetermined and unknown. When the second free() is run on the dangling pointer, the system is tring to free a block of memory not in use any more! The best result you can expect is a core dump.
The solution is simple. Just set the pointer to null after it is freed. Usually, we wrap it up in a macro.
---
#define SAFE_FREE(p) if ((p) != NULL) do {free((p)); (p) = NULL;} while (0)
---
It is a common practice to wrap up multiple statements of a macro into a do {...} while (0) loop, with no terminating semicolon.This allows the macro to be used like a single statement in any location, such as the body of an if statement, while still allowing a semicolon to be placed after the macro invocation without creating a null statement.
References:
http://stackoverflow.com/questions/2468853/freeing-memory-twice
http://en.wikibooks.org/wiki/C_Programming/Common_practices
Monday, November 14, 2011
Thursday, November 10, 2011
Torture
早上给猴子和猴妈打电话，问猴子想不想爸爸，猴妈说猴子不想，原因是“爸爸太爱我了，总是亲我，torture我”（猴子的原话），一笑。
真想这个可爱的猴子啊。在这以前，可以说没有一天跟我分开过。
下面这两张照片，是在从北卡到肯州的路上拍的，估计是在田纳西境内的某个加油站。
真想这个可爱的猴子啊。在这以前，可以说没有一天跟我分开过。
下面这两张照片，是在从北卡到肯州的路上拍的，估计是在田纳西境内的某个加油站。
Saturday, November 5, 2011
童趣两则
1. 贝贝在玩笔记本电脑的时候，我过去把头靠着贝贝，问他：“贝贝，你离开爸爸，会难过吗？”，贝贝回答：“Easy过”，见我脸色迷惘，又补充说：“容易过”。
2. 给贝贝在YouTube上面找了一个U.S. Marine Corps的一次Combat Patrol的实拍录像，可是录像里面只见士兵们打枪，并没有见到他们的阿富汗对手。然后又见这些士兵们没完没了地说着什么，我和贝贝都没听明白，贝贝问他们为什么只talk不fight，我很赞同：“These sons of bitches should stop talking.” 猴子问：“What does bitch means?” 我回答：“female dog”，贝贝继续追问：“But there is no dog in the battle field.” 这下我彻底傻了。
2. 给贝贝在YouTube上面找了一个U.S. Marine Corps的一次Combat Patrol的实拍录像，可是录像里面只见士兵们打枪，并没有见到他们的阿富汗对手。然后又见这些士兵们没完没了地说着什么，我和贝贝都没听明白，贝贝问他们为什么只talk不fight，我很赞同：“These sons of bitches should stop talking.” 猴子问：“What does bitch means?” 我回答：“female dog”，贝贝继续追问：“But there is no dog in the battle field.” 这下我彻底傻了。
昨晚可真不应该
为了一点小事向猴子发火，把猴子给骂哭了。猴子一开始还忍着，明明想哭，却强作无事，妈妈逗猴子说“你哭、你哭”的时候还强作笑脸。忘记是什么原因了，突然忍不住了，小嘴一咧，哭得好伤心。这点挺像我的。遇到伤心事，我小时候也会尽量忍住泪水，但到最后（经常是见到父母后）仍然会情不自禁地哭泣。
猴子一哭，弄得我心里也挺不痛快。还是要自我检讨一下，其实猴子也没做什么大的错事，就是我在与奶奶用skype聊天的时候，用脚在摇笔记本下面的桌子。当时我正好在和奶奶谈到工作的事情，猴子这么一搞，弄得我没控制住自己的情绪。以前比这大得多的事情我都能容忍，为什么这次不能？事后回想，还是把工作中的浮躁情绪带到家里了，并发泄到猴子身上了。实在是不应该，尤其是过几天猴子和猴妈就要离开猴爸了，疼还来不及，怎么能对孩子发火？尤其是因无关痛痒的事情，更是觉得自己无可理喻。
有的时候，真的很厌恶自己，觉得自己像是一坨屎。
猴子一哭，弄得我心里也挺不痛快。还是要自我检讨一下，其实猴子也没做什么大的错事，就是我在与奶奶用skype聊天的时候，用脚在摇笔记本下面的桌子。当时我正好在和奶奶谈到工作的事情，猴子这么一搞，弄得我没控制住自己的情绪。以前比这大得多的事情我都能容忍，为什么这次不能？事后回想，还是把工作中的浮躁情绪带到家里了，并发泄到猴子身上了。实在是不应该，尤其是过几天猴子和猴妈就要离开猴爸了，疼还来不及，怎么能对孩子发火？尤其是因无关痛痒的事情，更是觉得自己无可理喻。
有的时候，真的很厌恶自己，觉得自己像是一坨屎。
Thursday, November 3, 2011
不知道为啥
在北卡的时候，虽然没有工作，但我心里一点也不痛苦（不知道是不是算没心没肺），感觉过得还是很快乐。快乐地带猴子、快乐地上网、快乐地读自己喜欢的书，过得很充实，从来也不会觉得无聊。虽然程锦偶尔发点脾气（因为我某件事做错了，老婆并不是不讲道理的人），也是过眼烟云，并不会放在心上很久。
但是不知为何，现在有工作了，却感到内心很软弱，也分不清楚是出于对工作的畏难情绪导致的，还是对即将离开的老婆孩子依依不舍，也许两者兼而有之吧。
人真是个奇怪的动物，有时候很坚强，另些时候又无比脆弱，真是矛盾的对立统一体。
喜欢读战争小说的我，对从战场上的老兵最珍惜家庭感到不解。总觉得经过了战争这个壮丽残酷的过程的人，怎么会对平淡的家庭生活那么感兴趣，那么看重？现在，我些许有点感悟。虽然我和一名战场上的老兵不可同日而语，但对于和亲人短暂的分别都感到难以忍受，就更不用说老兵了。士兵在战场上，每时每刻都有可能被流弹打死，对亲情的感觉就更为强烈，也必然更为珍惜。可能这也是电影Gladiator里面罗马皇帝Marcus Aurelius在大战结束之后问Maximus（Russel Crowe）想要什么样的奖赏，得到的回答却是“Home”。
陆游有句诗是这样的：“死去原知万事空，但悲不见九州同（下略）”。我的感想是：“死去原知万事空，但悲不见妻与子”。过于沉重了，其实也不到那个程度，只是感觉心里难受。
但是不知为何，现在有工作了，却感到内心很软弱，也分不清楚是出于对工作的畏难情绪导致的，还是对即将离开的老婆孩子依依不舍，也许两者兼而有之吧。
人真是个奇怪的动物，有时候很坚强，另些时候又无比脆弱，真是矛盾的对立统一体。
喜欢读战争小说的我，对从战场上的老兵最珍惜家庭感到不解。总觉得经过了战争这个壮丽残酷的过程的人，怎么会对平淡的家庭生活那么感兴趣，那么看重？现在，我些许有点感悟。虽然我和一名战场上的老兵不可同日而语，但对于和亲人短暂的分别都感到难以忍受，就更不用说老兵了。士兵在战场上，每时每刻都有可能被流弹打死，对亲情的感觉就更为强烈，也必然更为珍惜。可能这也是电影Gladiator里面罗马皇帝Marcus Aurelius在大战结束之后问Maximus（Russel Crowe）想要什么样的奖赏，得到的回答却是“Home”。
陆游有句诗是这样的：“死去原知万事空，但悲不见九州同（下略）”。我的感想是：“死去原知万事空，但悲不见妻与子”。过于沉重了，其实也不到那个程度，只是感觉心里难受。
第二天上班，还是难受
不舒服的感觉很强烈。我在新加坡工作的时候还有免费Milo以及Nestle Coffee喝，到这里屁的饮料都没有，只有自来水，操！
工作方面，还在摸索code的过程中，还是有些艰难，可能是许久没有写code的缘故导致的，要努力啊。
下午雷哥给我打了个电话问我的情况，说着说着鼻子就有些发酸，又想哭了。想念朋友的关怀，害怕即将失去的的老婆孩子热炕头。
今天中午，我的Recruiter Marc带我去Aerotek补办一些手续，中途问我是否喜欢Lexington，为了不扫他的兴致，我违心地说喜欢。其实还是咱北卡的农村好啊，一点都不喜欢Lexington，虽然它是个城市。
工作方面，还在摸索code的过程中，还是有些艰难，可能是许久没有写code的缘故导致的，要努力啊。
下午雷哥给我打了个电话问我的情况，说着说着鼻子就有些发酸，又想哭了。想念朋友的关怀，害怕即将失去的的老婆孩子热炕头。
今天中午，我的Recruiter Marc带我去Aerotek补办一些手续，中途问我是否喜欢Lexington，为了不扫他的兴致，我违心地说喜欢。其实还是咱北卡的农村好啊，一点都不喜欢Lexington，虽然它是个城市。
Wednesday, November 2, 2011
今天是在Lexmark工作的第一天
这个公司外表感觉很光鲜，但是似乎里面很烂，工作环境很差，刚开始很多东西不懂，也不知道是不是在家闲了太久的缘故，反正脑袋感觉用得不太得劲。不过，感觉Lexmark的code结构很乱，不如Xerox的code架构简明清晰。
上班上到下午，想到今后要孤孤单单一个人在这鬼不生蛋的地方生活，不禁悲从中来，有点想哭的感觉。老婆真不容易，以前总是不能理解的，总以为自己在新加坡带猴子更为辛苦，其实还是孤独最可怕，程锦能独自熬过三年，不简单。
庄子曾经说过：“子非鱼，安知鱼之乐？”同样，只有在有相同经历的基础上，才能有相似的痛苦。
上班第一天，就有想撂挑子，和老婆孩子一起回家、离开这鬼地方的冲动。唉……
上班上到下午，想到今后要孤孤单单一个人在这鬼不生蛋的地方生活，不禁悲从中来，有点想哭的感觉。老婆真不容易，以前总是不能理解的，总以为自己在新加坡带猴子更为辛苦，其实还是孤独最可怕，程锦能独自熬过三年，不简单。
庄子曾经说过：“子非鱼，安知鱼之乐？”同样，只有在有相同经历的基础上，才能有相似的痛苦。
上班第一天，就有想撂挑子，和老婆孩子一起回家、离开这鬼地方的冲动。唉……
Friday, June 10, 2011
EFI interview - 6
最后一个进来的是一个技术主管的Director，问了我几个理论问题，一个都没答上来。
1. TCP协议和UDP协议的区别？
还真不知道，以前做工作的时候是直接用网络工具WireShark捕捉网络传输的packet，WireShark上面会直接标出这个包是TCP的包还是UDP的包，所以从来没有关心过。后来面试官告诉我，TCP协议更严格一些，要求一个handshake的过程，比如一个request从client发到server上之后，必须得到server端发回来的acknowledgement才可以继续进行下去，否则就hang在那里等待，要么就timeout中止这个过程。作为对比，UDP就比较宽松一些，这个协议不要求server发回ack，可以继续把数据发向server端。然后他又问我UDP在现实中有哪些应用？也不知道。又是他告诉我说主要用于video的传输或者voice chat，因为这个过程中由于数据量大，delay很常见，无法很奢侈地等待每一个ack回来。
2. 加密算法，何谓symmetric，何谓assymmetric？我说不知道。面试官问我当一台机器让我敲了username和password之后，该怎样验证我的身份？我说它应该用与加密算法相逆的算法将密码还原，他说这样不好。就好象如果他注册了一个网站，结果忘记密码了，问网站要回密码。如果网站真的将他原来的密码找出来寄回给他，他反而会不高兴，因为这意味着网站的服务器有办法反编译他的密码，并有可能泄漏给第三方。相反，很多网站会reset他的密码之后给他寄一个新的密码，这样他登录之后可以立即修改，这样就很安全。
所谓asymmetric的方法，就是当一个密码被加密得到一个hash key之后，当你登录之后，把你敲进来的密码再用同样的算法加密，然后比较两次hash key的结果。
1. TCP协议和UDP协议的区别？
还真不知道，以前做工作的时候是直接用网络工具WireShark捕捉网络传输的packet，WireShark上面会直接标出这个包是TCP的包还是UDP的包，所以从来没有关心过。后来面试官告诉我，TCP协议更严格一些，要求一个handshake的过程，比如一个request从client发到server上之后，必须得到server端发回来的acknowledgement才可以继续进行下去，否则就hang在那里等待，要么就timeout中止这个过程。作为对比，UDP就比较宽松一些，这个协议不要求server发回ack，可以继续把数据发向server端。然后他又问我UDP在现实中有哪些应用？也不知道。又是他告诉我说主要用于video的传输或者voice chat，因为这个过程中由于数据量大，delay很常见，无法很奢侈地等待每一个ack回来。
2. 加密算法，何谓symmetric，何谓assymmetric？我说不知道。面试官问我当一台机器让我敲了username和password之后，该怎样验证我的身份？我说它应该用与加密算法相逆的算法将密码还原，他说这样不好。就好象如果他注册了一个网站，结果忘记密码了，问网站要回密码。如果网站真的将他原来的密码找出来寄回给他，他反而会不高兴，因为这意味着网站的服务器有办法反编译他的密码，并有可能泄漏给第三方。相反，很多网站会reset他的密码之后给他寄一个新的密码，这样他登录之后可以立即修改，这样就很安全。
所谓asymmetric的方法，就是当一个密码被加密得到一个hash key之后，当你登录之后，把你敲进来的密码再用同样的算法加密，然后比较两次hash key的结果。
EFI interview - 5
问题：怎样判断一个年份是否是闰年？
这个问题也栽了，当时对if-else的条件捣鼓了半天，还是没有捣鼓对。感觉上，面试官对判断闰年与否的条件给得不是很清楚，算是找个借口吧。
http://support.microsoft.com/kb/214019
In the Gregorian calendar, a normal year consists of 365 days. Because the actual length of a sidereal year (the time required for the Earth to revolve once about the Sun) is actually 365.25635 days, a "leap year" of 366 days is used once every four years to eliminate the error caused by three normal (but short) years. Any year that is evenly divisible by 4 is a leap year: for example, 1988, 1992, and 1996 are leap years.
However, there is still a small error that must be accounted for. To eliminate this error, the Gregorian calendar stipulates that a year that is evenly divisible by 100 (for example, 1900) is a leap year only if it is also evenly divisible by 400.
For this reason, the following years are not leap years: 1700, 1800, 1900, 2100, 2200, 2300, 2500, 2600. This is because they are evenly divisible by 100 but not by 400.
The following years are leap years: 1600, 2000, 2400. This is because they are evenly divisible by both 100 and 400.
To determine whether a year is a leap year, follow these steps:
1). If the year is evenly divisible by 4, go to step 2. Otherwise, go to step 5.
2). If the year is evenly divisible by 100, go to step 3. Otherwise, go to step 4.
3). If the year is evenly divisible by 400, go to step 4. Otherwise, go to step 5.
4). The year is a leap year (it has 366 days).
5). The year is not a leap year (it has 365 days).
这里的算法逻辑很清楚。
http://en.wikipedia.org/wiki/Leap_year
if year modulo 400 is 0
then is_leap_year
else if year modulo 100 is 0
then not_leap_year
else if year modulo 4 is 0
then is_leap_year
else
not_leap_year
这里的算法非常简洁。
这个问题也栽了，当时对if-else的条件捣鼓了半天，还是没有捣鼓对。感觉上，面试官对判断闰年与否的条件给得不是很清楚，算是找个借口吧。
http://support.microsoft.com/kb/214019
In the Gregorian calendar, a normal year consists of 365 days. Because the actual length of a sidereal year (the time required for the Earth to revolve once about the Sun) is actually 365.25635 days, a "leap year" of 366 days is used once every four years to eliminate the error caused by three normal (but short) years. Any year that is evenly divisible by 4 is a leap year: for example, 1988, 1992, and 1996 are leap years.
However, there is still a small error that must be accounted for. To eliminate this error, the Gregorian calendar stipulates that a year that is evenly divisible by 100 (for example, 1900) is a leap year only if it is also evenly divisible by 400.
For this reason, the following years are not leap years: 1700, 1800, 1900, 2100, 2200, 2300, 2500, 2600. This is because they are evenly divisible by 100 but not by 400.
The following years are leap years: 1600, 2000, 2400. This is because they are evenly divisible by both 100 and 400.
To determine whether a year is a leap year, follow these steps:
1). If the year is evenly divisible by 4, go to step 2. Otherwise, go to step 5.
2). If the year is evenly divisible by 100, go to step 3. Otherwise, go to step 4.
3). If the year is evenly divisible by 400, go to step 4. Otherwise, go to step 5.
4). The year is a leap year (it has 366 days).
5). The year is not a leap year (it has 365 days).
这里的算法逻辑很清楚。
http://en.wikipedia.org/wiki/Leap_year
if year modulo 400 is 0
then is_leap_year
else if year modulo 100 is 0
then not_leap_year
else if year modulo 4 is 0
then is_leap_year
else
not_leap_year
这里的算法非常简洁。
EFI interview - 4
这回是以前一个在Qualcomm面试中问过的问题，关于volatile关键字的作用。我跟面试官谈了一下，不过他说我说的原理是对的，但没有说出volatile的用法的intention所在，真是个傻逼。
再复习一下
－－－
在K&R的Bible的附录A.8.2里面，提到了这么一段：
The purpose of volatile is to force an implementation to suppress optimization that could otherwise occur. For example, for a machine with memory-mapped input/output, a pointer to a device register might be declared as a pointer to volatile, in order to prevent the compiler from removing apparently redundant references through the pointer.
另外，相关的资料也可参见下面的link：
http://en.wikibooks.org/wiki/Embedded_Systems/C_Programming
http://vault.embedded.com/story/OEG20010615S0107
http://publications.gbdirect.co.uk/c_book/chapter8/const_and_volatile.html
再复习一下
－－－
在K&R的Bible的附录A.8.2里面，提到了这么一段：
The purpose of volatile is to force an implementation to suppress optimization that could otherwise occur. For example, for a machine with memory-mapped input/output, a pointer to a device register might be declared as a pointer to volatile, in order to prevent the compiler from removing apparently redundant references through the pointer.
另外，相关的资料也可参见下面的link：
http://en.wikibooks.org/wiki/Embedded_Systems/C_Programming
http://vault.embedded.com/story/OEG20010615S0107
http://publications.gbdirect.co.uk/c_book/chapter8/const_and_volatile.html
EFI interview - 3
Problem: Two integers given, N and M. Suppose M = 10101 (binary system), write code to change N's 2nd to 6th bits to M. For example, N = 100001000, M = 10101, the result is expected to be 101010100.
当时瞎折腾了一通，并没有完全解出来。不过基本思路是有的，回到旅馆之后整理了一下思路，大致应该这么做：
M << 2 first, to move the binary numbers into bit 2~6. Then if we can clear bits 2~6 in N, say the cleared N is N1, then what left is to do N1 | M<<2.
But how to clear bits 2~6 in N? It seems N & ~1111100 can do it. So, could it be done with (N & (~1111100)) | M<<2?
不那么精巧，但似乎可以达成目标。MITBBS上有朋友提出了另外几种答案，不过我看不明白。比较典型的利用类似Bit Twiddling Hacks中的技巧的方法是MITBBS的FCer提出来的：(~k)&N | (M<<2)，where k = (1<<7)-(1<<2)。不过看不懂为什么k要这样计算。
当时瞎折腾了一通，并没有完全解出来。不过基本思路是有的，回到旅馆之后整理了一下思路，大致应该这么做：
M << 2 first, to move the binary numbers into bit 2~6. Then if we can clear bits 2~6 in N, say the cleared N is N1, then what left is to do N1 | M<<2.
But how to clear bits 2~6 in N? It seems N & ~1111100 can do it. So, could it be done with (N & (~1111100)) | M<<2?
不那么精巧，但似乎可以达成目标。MITBBS上有朋友提出了另外几种答案，不过我看不明白。比较典型的利用类似Bit Twiddling Hacks中的技巧的方法是MITBBS的FCer提出来的：(~k)&N | (M<<2)，where k = (1<<7)-(1<<2)。不过看不懂为什么k要这样计算。
EFI interview - 2
问题：什么是callback function？
这个还真的问到我的痛脚了。以前写code的时候倒是见过几个callback function，用过，但是自己没有写过。只是有印象它们是用函数指针（function pointer）实现的，经常用于对某种event或是signal的相应，有点类似于微软可视化编程里面的消息驱动机制。不过，说实话，怎样把某个event和某个function pointer联系起来，我还不是很清楚。以前在code里面看到要register一下，不过怎样register呢？细节还是有点模糊。
可以读一读下面这几篇文章：
http://stackoverflow.com/questions/142789/what-is-a-callback-in-c-and-how-are-they-implemented
http://stackoverflow.com/questions/2738463/implementing-callback-functions-in-c
http://www.cprogramming.com/tutorial/function-pointers.html
这个还真的问到我的痛脚了。以前写code的时候倒是见过几个callback function，用过，但是自己没有写过。只是有印象它们是用函数指针（function pointer）实现的，经常用于对某种event或是signal的相应，有点类似于微软可视化编程里面的消息驱动机制。不过，说实话，怎样把某个event和某个function pointer联系起来，我还不是很清楚。以前在code里面看到要register一下，不过怎样register呢？细节还是有点模糊。
可以读一读下面这几篇文章：
http://stackoverflow.com/questions/142789/what-is-a-callback-in-c-and-how-are-they-implemented
http://stackoverflow.com/questions/2738463/implementing-callback-functions-in-c
http://www.cprogramming.com/tutorial/function-pointers.html
EFI interview - 1
题目：打印一个Pascal's Triangle（也称杨辉三角）。
解开这个题目，至少有三种方法。前两个方法可以在Wikipedia上面得到启示：http://en.wikipedia.org/wiki/Pascal's_triangle
1. 利用二项式展开的方法，启示杨辉三角的每一个元素都是二项式(x+y)^n的系数，可以用下面的公式来计算：
值得注意的是，如果行数从0算起，那么杨辉三角每一行的列数都等于行数+1。
2. 任意一行的任意一个元素，其实都是其所在的行数、列数以及其前一个元素的某种组合（函数）。
This algorithm is an alternative to the standard method of calculating individual cells with factorials. Starting at the left, the first cell's value v0 is 1. For each cell after, the value is determined by multiplying the value to its left by a slowly changing fraction:
where r = row + 1, starting with 0 at the top, and c = the column, starting with 0 on the left. For example, to calculate row 5, r = 6. The first value is 1. The next value is 1 × 5/1 = 5. The numerator decreases by one, and the denominator increases by one with each step. So 5 × 4/2 = 10. Then 10 × 3/3 = 10. Then 10 × 2/4 = 5. Then 5 × 1/5 = 1. Notice that the last cell always equals 1, the final multiplication is included for completeness of the series.
3. 利用杨辉三角的一个重要性质：底下一个元素是其上一层两个元素之和。下面的代码是MITBBS的网友speeddy提供：
int p1[20];
memset(p1, 0, 20*4);
p1[0] = 1;
for(int i=0; i<10; i++) {
int next = 0;
int prev = 0;
for (int j = 0; j < i+1; j++) {
if (j == 0) {
p1[j] = 1;
prev = 1;
} else if (j == i) {
p1[j] = 1;
} else {
next = p1[j];
p1[j] += prev;
prev = next;
}
cout << p1[j] << " ";
}
cout << endl;
}
result:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
解开这个题目，至少有三种方法。前两个方法可以在Wikipedia上面得到启示：http://en.wikipedia.org/wiki/Pascal's_triangle
1. 利用二项式展开的方法，启示杨辉三角的每一个元素都是二项式(x+y)^n的系数，可以用下面的公式来计算：
值得注意的是，如果行数从0算起，那么杨辉三角每一行的列数都等于行数+1。
2. 任意一行的任意一个元素，其实都是其所在的行数、列数以及其前一个元素的某种组合（函数）。
This algorithm is an alternative to the standard method of calculating individual cells with factorials. Starting at the left, the first cell's value v0 is 1. For each cell after, the value is determined by multiplying the value to its left by a slowly changing fraction:
where r = row + 1, starting with 0 at the top, and c = the column, starting with 0 on the left. For example, to calculate row 5, r = 6. The first value is 1. The next value is 1 × 5/1 = 5. The numerator decreases by one, and the denominator increases by one with each step. So 5 × 4/2 = 10. Then 10 × 3/3 = 10. Then 10 × 2/4 = 5. Then 5 × 1/5 = 1. Notice that the last cell always equals 1, the final multiplication is included for completeness of the series.
3. 利用杨辉三角的一个重要性质：底下一个元素是其上一层两个元素之和。下面的代码是MITBBS的网友speeddy提供：
int p1[20];
memset(p1, 0, 20*4);
p1[0] = 1;
for(int i=0; i<10; i++) {
int next = 0;
int prev = 0;
for (int j = 0; j < i+1; j++) {
if (j == 0) {
p1[j] = 1;
prev = 1;
} else if (j == i) {
p1[j] = 1;
} else {
next = p1[j];
p1[j] += prev;
prev = next;
}
cout << p1[j] << " ";
}
cout << endl;
}
result:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
Wednesday, April 6, 2011
Qualcomm Onsite 之三
一个Interviewer问我以前的工作中code base有多大，我说大概有几万个文件，总共的size超过1GB。然后他又问我文件的大小是多少，我说从几百个字节到几千个字节不等。
接着，他又问我如果一个function超过一百行，会不会有问题？我说还行，我还见过更长的。话刚说完，我就有点知道他问的意思了。马上再补充说，这样的函数往往集合了太多的功能，developer最好应把它分解成几个sub-function，每个sub-function完成某项特定的任务，这样就可以实现较好的readibility。不过也有代价，就是stack的开销增加了，因为call每个sub-function都要把它们push进stack，执行完了再pop it up，也许会对performance有影响。Developers must balance between readibility and performance.
Interviewer接过话茬说，有没有一种方法，可以让我们enjoy the best of both worlds？我说很难。他提示说其实gcc的compiler提供了一种优化的方法可以做到不至于让多个sub-function影响performance, without using the keyword "inline". For example, gcc -O1/O2/O3
查了一下gcc的document，还真是如此：
http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags:
-fthread-jumps
-falign-functions -falign-jumps
-falign-loops -falign-labels
-fcaller-saves
-fcrossjumping
-fcse-follow-jumps -fcse-skip-blocks
-fdelete-null-pointer-checks
-fdevirtualize
-fexpensive-optimizations
-fgcse -fgcse-lm
-finline-small-functions
-findirect-inlining
-fipa-sra
-foptimize-sibling-calls
-fpartial-inlining
-fpeephole2
-fregmove
-freorder-blocks -freorder-functions
-frerun-cse-after-loop
-fsched-interblock -fsched-spec
-fschedule-insns -fschedule-insns2
-fstrict-aliasing -fstrict-overflow
-ftree-switch-conversion
-ftree-pre
-ftree-vrp
看样子，就是其中的-finline-small-functions这个开关起的作用了。以前在施乐写程序的时候，没太关注Makefile，看来付出代价了。
接着，他又问我如果一个function超过一百行，会不会有问题？我说还行，我还见过更长的。话刚说完，我就有点知道他问的意思了。马上再补充说，这样的函数往往集合了太多的功能，developer最好应把它分解成几个sub-function，每个sub-function完成某项特定的任务，这样就可以实现较好的readibility。不过也有代价，就是stack的开销增加了，因为call每个sub-function都要把它们push进stack，执行完了再pop it up，也许会对performance有影响。Developers must balance between readibility and performance.
Interviewer接过话茬说，有没有一种方法，可以让我们enjoy the best of both worlds？我说很难。他提示说其实gcc的compiler提供了一种优化的方法可以做到不至于让多个sub-function影响performance, without using the keyword "inline". For example, gcc -O1/O2/O3
查了一下gcc的document，还真是如此：
http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html
-O2 turns on all optimization flags specified by -O. It also turns on the following optimization flags:
-fthread-jumps
-falign-functions -falign-jumps
-falign-loops -falign-labels
-fcaller-saves
-fcrossjumping
-fcse-follow-jumps -fcse-skip-blocks
-fdelete-null-pointer-checks
-fdevirtualize
-fexpensive-optimizations
-fgcse -fgcse-lm
-finline-small-functions
-findirect-inlining
-fipa-sra
-foptimize-sibling-calls
-fpartial-inlining
-fpeephole2
-fregmove
-freorder-blocks -freorder-functions
-frerun-cse-after-loop
-fsched-interblock -fsched-spec
-fschedule-insns -fschedule-insns2
-fstrict-aliasing -fstrict-overflow
-ftree-switch-conversion
-ftree-pre
-ftree-vrp
看样子，就是其中的-finline-small-functions这个开关起的作用了。以前在施乐写程序的时候，没太关注Makefile，看来付出代价了。
Qualcomm Onsite 之二
发信人: johny (猴年马月), 信区: JobHunting
标 题: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:14:32 2011, 美东)
倒是没有问什么太难的算法和数据结构方面的题，大多是和实际工作相结合的题目，比如debug一段程序，等等，都不算难。
不过还是有个数据结构的问题把我问倒了：
具体问题的起源我也记不清了，反正就是要求我implement一个数据结构，要求access是O(1)量级的。
一开始我提了用数组，但是被否决，因为将要储存的数据量很大而且预先不知道终止条件，所以很难给定数组的range。
用list显然也不可行，因为list一般是unsorted的，要找一个数据，必须遍历一次，也就是O(n)的complexity。
接着我又提了Hash Table，隐约记得Hash Table的access是O(1)的量级，但大叔说如果Hash Table的row是M，而每个entry（key mapped via hash function）是个linked list（因为不同key的key-value pair经过hash function的运算后得出相同的index），假设linked list里面所含的元素是N，那么access的时间复杂度是O(N/M)。好了，再次被枪毙。
最后，我在大叔这里面试的时间到了，大叔一边把我送到下个interviewer那里，一边在路上叫我继续考虑这个问题。郁闷啊。
难道还有比Hash Table更快access的数据结构？难道是C++里面的map？但是map如果key有重复的话，value也是一个linked list（或者vector）吧？
而且，map的access复杂度似乎比Hash Table要差吧？不好意思，还没查到map的access复杂度是多少。
发信人: HanSolo7 (隼), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:22:48 2011, 美东)
Hash table with a really good hash function (if he really wanna constant time access). That's my answer.
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:25:13 2011, 美东)
一个很好的hash function是不是能把linked list的长度减到尽可能的低？反正我是想不出来还是什么更好的数据结构了。
顺便问一下，map的access复杂度是多少啊？
发信人: HanSolo7 (隼), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:38:21 2011, 美东)
是啊。map在c++里是红黑树实现的吧。那就是O(logn)吧。
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:56:13 2011, 美东)
对了，想起来当时因为大叔提出用数组range不好确定，我还提出了用vector，但是忘记是出于什么原因，也被否决了。
其实vector是个不错的选择，而且能实现O(1)的access，但为什么也不行呢？纳闷。
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 22:54:50 2011, 美东)
lz面的是experienced？为什么都是问工作的问题？
可以解释下access time是O(1)？具体的是要access每一个element都是O(1)，还是说只是说access最大或者最小是O(1)? 需要保持插入有序么，还是只要取出有序就可以了？
要取得所有的element的access time O(1)的话，应该是hash了。
BTW， std::map的实现是红黑树，时间是log(n)，但是std::tr1::unordered_map的可以达到O(1)access time，但是它的实现也适用到了hasher function, 所以不知道这是否符合要求呢？
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:00:11 2011, 美东)
谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意思应该是access每个元素的意思吧，他当时没提到最大或者最小。
另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
昨晚睡了一觉，又想起来一些当时的具体情节。
有个函数，void timeout_register(int time_out, void (*fprt)(float *), .../* parameter list to the function pointer */)
有个timer，每隔一秒钟就timeout一次，会call这个do_something()，要求是设计并实现一个数据结构，以达到当timeout时，找出当前的time_out值对应的function，跑一遍，再从数据结构里删除这个entry。
比如，time_out的值是3秒的时候，必须把这个数据结构里面3秒所对应的function调出来跑。
要求对找到这个function entry的search的时间复杂度是O(1)。
用hash table的话，如果key-value pair中value是一个很长的链表，确实效率不太高。为此，一般对string作key的hash table，会用一个特定的multiplier（通常是31）来multiply这个string中每个char的值生成一个index，再%sizeof(hash_table)以达到链表的长度最小。
但是对我这个问题，我想如果用time_out的值作为key的话，该用什么样的hash function才能尽量减小链表长度呢？
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:05:32 2011, 美东)
顺带说一下，如果可以用array的话，那么我把这个time_out的值作为这个array的index，也可以实现O(1)的search（实质上已经转换为array的index操作）。不过因为range不好事先确定，所以不能用。
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:35:49 2011, 美东)
我的想法是如果需要 time-out call对应的function的话，那么只要一个heap或者说priority_queue就可以了：一开始把所有time-out的时间推入，然后堆顶的元素就是下一个我们需要执行的函数的方程。
heap中的每个节点对应的是，每次堆顶的元素就是我们需要执行的函数了。
access的time是O(1).
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:06:50 2011, 美东)
大叔似乎说过time_out的排列是无序的，比如：5，3，1，10，……这种情况下，也可以把它们推进一个堆里吗？
另外问一下，http://www.cplusplus.com/里面没有找到heap的数据结构的解释和说明，还有什么地方可以参考吗？
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:41:04 2011, 美东)
在stl里面已经包含了heap的实现，见：http://www.cplusplus.com/reference/stl/priority_queue/
输入无序没有关系，heap可以自动调整（heapify），它可以保证推定的元素就是目前堆中最小的元素(min heap)，调整的时间是o(log n)，但是access time的话就是O(1)， 每次取堆顶就可以了。
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:59:38 2011, 美东)
－－－
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.
－－－
从这里看，好象堆顶的元素是最大的啊。怎样让它弹出最小元素呢？
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:10:45 2011, 美东)
check this: http://www.cplusplus.com/reference/stl/priority_queue/priority_queue/
All you need to do is to override the default comparator, so that you can pass your own one. In this case, you can put the smallest at the top.
Just try run the examples in the link, and see what you get.
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:37:30 2011, 美东)
谢谢，了解了。
顺便再问一下，如果我用vector来做，用time_out的值做index，是不是也可以做到O(1)的access呢？
发信人: speeddy (Wade), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:47:34 2011, 美东)
Look at freebsd source code. It seems in timer.h. Freebsd's author talk about this how he implenmenet the timer in his freebsd teaching videos.
The book is http://www.amazon.com/Design-Implementation-FreeBSD-Operating-System/dp/0201702452
标 题: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:14:32 2011, 美东)
倒是没有问什么太难的算法和数据结构方面的题，大多是和实际工作相结合的题目，比如debug一段程序，等等，都不算难。
不过还是有个数据结构的问题把我问倒了：
具体问题的起源我也记不清了，反正就是要求我implement一个数据结构，要求access是O(1)量级的。
一开始我提了用数组，但是被否决，因为将要储存的数据量很大而且预先不知道终止条件，所以很难给定数组的range。
用list显然也不可行，因为list一般是unsorted的，要找一个数据，必须遍历一次，也就是O(n)的complexity。
接着我又提了Hash Table，隐约记得Hash Table的access是O(1)的量级，但大叔说如果Hash Table的row是M，而每个entry（key mapped via hash function）是个linked list（因为不同key的key-value pair经过hash function的运算后得出相同的index），假设linked list里面所含的元素是N，那么access的时间复杂度是O(N/M)。好了，再次被枪毙。
最后，我在大叔这里面试的时间到了，大叔一边把我送到下个interviewer那里，一边在路上叫我继续考虑这个问题。郁闷啊。
难道还有比Hash Table更快access的数据结构？难道是C++里面的map？但是map如果key有重复的话，value也是一个linked list（或者vector）吧？
而且，map的access复杂度似乎比Hash Table要差吧？不好意思，还没查到map的access复杂度是多少。
发信人: HanSolo7 (隼), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:22:48 2011, 美东)
Hash table with a really good hash function (if he really wanna constant time access). That's my answer.
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:25:13 2011, 美东)
一个很好的hash function是不是能把linked list的长度减到尽可能的低？反正我是想不出来还是什么更好的数据结构了。
顺便问一下，map的access复杂度是多少啊？
发信人: HanSolo7 (隼), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:38:21 2011, 美东)
是啊。map在c++里是红黑树实现的吧。那就是O(logn)吧。
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 20:56:13 2011, 美东)
对了，想起来当时因为大叔提出用数组range不好确定，我还提出了用vector，但是忘记是出于什么原因，也被否决了。
其实vector是个不错的选择，而且能实现O(1)的access，但为什么也不行呢？纳闷。
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Mon Apr 4 22:54:50 2011, 美东)
lz面的是experienced？为什么都是问工作的问题？
可以解释下access time是O(1)？具体的是要access每一个element都是O(1)，还是说只是说access最大或者最小是O(1)? 需要保持插入有序么，还是只要取出有序就可以了？
要取得所有的element的access time O(1)的话，应该是hash了。
BTW， std::map的实现是红黑树，时间是log(n)，但是std::tr1::unordered_map的可以达到O(1)access time，但是它的实现也适用到了hasher function, 所以不知道这是否符合要求呢？
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:00:11 2011, 美东)
谢谢楼上的回复。对，我面的是experienced的职位。大叔说的acess time是O(1)的意思应该是access每个元素的意思吧，他当时没提到最大或者最小。
另外，vector的access time是不是O(1)啊？不晓得vector有什么劣势。
昨晚睡了一觉，又想起来一些当时的具体情节。
有个函数，void timeout_register(int time_out, void (*fprt)(float *), .../* parameter list to the function pointer */)
有个timer，每隔一秒钟就timeout一次，会call这个do_something()，要求是设计并实现一个数据结构，以达到当timeout时，找出当前的time_out值对应的function，跑一遍，再从数据结构里删除这个entry。
比如，time_out的值是3秒的时候，必须把这个数据结构里面3秒所对应的function调出来跑。
要求对找到这个function entry的search的时间复杂度是O(1)。
用hash table的话，如果key-value pair中value是一个很长的链表，确实效率不太高。为此，一般对string作key的hash table，会用一个特定的multiplier（通常是31）来multiply这个string中每个char的值生成一个index，再%sizeof(hash_table)以达到链表的长度最小。
但是对我这个问题，我想如果用time_out的值作为key的话，该用什么样的hash function才能尽量减小链表长度呢？
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:05:32 2011, 美东)
顺带说一下，如果可以用array的话，那么我把这个time_out的值作为这个array的index，也可以实现O(1)的search（实质上已经转换为array的index操作）。不过因为range不好事先确定，所以不能用。
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 09:35:49 2011, 美东)
我的想法是如果需要 time-out call对应的function的话，那么只要一个heap或者说priority_queue就可以了：一开始把所有time-out的时间推入，然后堆顶的元素就是下一个我们需要执行的函数的方程。
heap中的每个节点对应的是
access的time是O(1).
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:06:50 2011, 美东)
大叔似乎说过time_out的排列是无序的，比如：5，3，1，10，……这种情况下，也可以把它们推进一个堆里吗？
另外问一下，http://www.cplusplus.com/里面没有找到heap的数据结构的解释和说明，还有什么地方可以参考吗？
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:41:04 2011, 美东)
在stl里面已经包含了heap的实现，见：http://www.cplusplus.com/reference/stl/priority_queue/
输入无序没有关系，heap可以自动调整（heapify），它可以保证推定的元素就是目前堆中最小的元素(min heap)，调整的时间是o(log n)，但是access time的话就是O(1)， 每次取堆顶就可以了。
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 10:59:38 2011, 美东)
－－－
Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering condition.
－－－
从这里看，好象堆顶的元素是最大的啊。怎样让它弹出最小元素呢？
发信人: gzou (gzou), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:10:45 2011, 美东)
check this: http://www.cplusplus.com/reference/stl/priority_queue/priority_queue/
All you need to do is to override the default comparator, so that you can pass your own one. In this case, you can put the smallest at the top.
Just try run the examples in the link, and see what you get.
发信人: johny (猴年马月), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:37:30 2011, 美东)
谢谢，了解了。
顺便再问一下，如果我用vector来做，用time_out的值做index，是不是也可以做到O(1)的access呢？
发信人: speeddy (Wade), 信区: JobHunting
标 题: Re: Qualcomm的面经
发信站: BBS 未名空间站 (Tue Apr 5 11:47:34 2011, 美东)
Look at freebsd source code. It seems in timer.h. Freebsd's author talk about this how he implenmenet the timer in his freebsd teaching videos.
The book is http://www.amazon.com/Design-Implementation-FreeBSD-Operating-System/dp/0201702452
Monday, April 4, 2011
Qualcomm Onsite 之一
今天是来美国后的第一个onsite，但是感觉很多技术问题没有答上来。准备的很多算法方面的东西，比如bitwise operation都没有问。
提的问题大多是比较有实战意义的。比如第一个比较绕一点的技术题是这样的：
有一块physical memory area、DMA、ARM以及介于ARM和physical memory之间的cache，其中DMA是直接向physical memory里面写数据的，而ARM则是通过cache从memory里面读数据，再把读出来的数据传给DMA，如果传给DMA的数据和DMA写入的数据不相符合，那么上传数据的function会hang掉。另外：当DMA向memory里面写数据的时候，ARM上传的函数会被block住。只有当DMA完成写的动作，ARM才有可能把从cache/memory里面读出来的数据写上去。
流程图如下：
------------------------------------- DMA
| /\
| |
| |
\/ |
memory |
| |
| |
| |
-------------> cache ---------------> ARM
现在有这样一段程序：
void arm_send_data(char *mem_data)
{
char result = 0;
check_sync_dma_arm();
result = *mem_data;
send_data_to_dma_and_check(result);
...
check_sync_dma_arm();
result = *mem_data;
send_data_to_dma_and_check(result);
return;
}
其中check_sync_dma_arm()是个blocking function，知道DMA完成向内存的写操作才得以返回。
当时Interviewer跟我说了一下有反复作两到三次的必要，但没有解释为什么。在上面的代码中，就简化为两次好了。
问题来了：这段代码在实际运行的时候发现会hang在send_data_to_dma_and_check(result)这个函数；也就是说，从memory中读取再传回DMA的数据与DMA向memory写入的数据不匹配。问为什么会出现这种情况？
我问会不会有别的thread在此期间也写入内存，导致内存值被改动？Interviewer否定了这个可能，并且确认physical memory里面这个值只有DMA可以写，写操作也成功地完成了。
我绞尽脑汁，也没想出来是为什么。后来Interview提示光看code是看不出问题的，问题出在这个模块的架构上。因为ARM是通过cache从memory读取的，什么是cache呢？就是暂存前一次从memory里面读取的data的地方。如果memory没有改动，那么下一次读数据的时候，ARM就不需要去memory操作了，直接从cache拿可以了。这就是cache加速的原理。
导致上面的代码出现问题的原因在于，当blocking call跳出来的时候，说明memory的值已经被写入了，而这时候ARM上传的值却是从cache里面读取的，是旧的、在写入之前的值。
Debug，第一轮：
void arm_send_data(char *mem_data)
{
char result = 0;
check_sync_dma_arm();
cache_invalidated(); // fix
result = *mem_data;
send_data_to_dma_and_check(result);
...
check_sync_dma_arm();
cache_invalidated(); // fix
result = *mem_data;
send_data_to_dma_and_check(result);
return;
}
cache_invalidated()的作用是使得下一次从内存读数据的时候（result = *medm_data），ARM不再从cache里面读值，而直接去physical memory里面去拿，同时更新cache的内容。
OK，这个问题我想明白了，但是还没完。上面的代码中，读数据和传回给DMA的动作进行了两轮。但fix却只对第一轮起作用。第二轮的操作还是hang掉了。为什么呢？
还是想不出来，Interview再次给出答案：因为一模一样的result = *mem_data的语句出现了两次，所以在compiler作optimization的时候，把第二条赋值语句给省略了，没有编译。
我想了两个办法：
1. Turn off compiler's optimization －显然是不行的，不能因噎废食，对吗？
2. 再加一个变量的声明：char result1; 之后在第二次读取数据和传数据给DMA的时候，用result1 = *mem_data和send_data_to_dma_and_check(result1)就可以了。
第二个办法虽然可行，但显然比较麻烦，而且确实也没必要多开销一个变量。
其实最佳的解决办法很简单，就是对函数的形参mem_data做一个volatile的声明：
void arm_send_data(volatile char *mem_data)
在K&R的Bible的附录A.8.2里面，提到了这么一段：
The purpose of volatile is to force an implementation to suppress optimization that could otherwise occur. For example, for a machine with memory-mapped input/output, a pointer to a device register might be declared as a pointer to volatile, in order to prevent the compiler from removing apparently redundant references through the pointer.
另外，相关的资料也可参见下面的link：
http://en.wikibooks.org/wiki/Embedded_Systems/C_Programming
http://vault.embedded.com/story/OEG20010615S0107
http://publications.gbdirect.co.uk/c_book/chapter8/const_and_volatile.html
提的问题大多是比较有实战意义的。比如第一个比较绕一点的技术题是这样的：
有一块physical memory area、DMA、ARM以及介于ARM和physical memory之间的cache，其中DMA是直接向physical memory里面写数据的，而ARM则是通过cache从memory里面读数据，再把读出来的数据传给DMA，如果传给DMA的数据和DMA写入的数据不相符合，那么上传数据的function会hang掉。另外：当DMA向memory里面写数据的时候，ARM上传的函数会被block住。只有当DMA完成写的动作，ARM才有可能把从cache/memory里面读出来的数据写上去。
流程图如下：
------------------------------------- DMA
| /\
| |
| |
\/ |
memory |
| |
| |
| |
-------------> cache ---------------> ARM
现在有这样一段程序：
void arm_send_data(char *mem_data)
{
char result = 0;
check_sync_dma_arm();
result = *mem_data;
send_data_to_dma_and_check(result);
...
check_sync_dma_arm();
result = *mem_data;
send_data_to_dma_and_check(result);
return;
}
其中check_sync_dma_arm()是个blocking function，知道DMA完成向内存的写操作才得以返回。
当时Interviewer跟我说了一下有反复作两到三次的必要，但没有解释为什么。在上面的代码中，就简化为两次好了。
问题来了：这段代码在实际运行的时候发现会hang在send_data_to_dma_and_check(result)这个函数；也就是说，从memory中读取再传回DMA的数据与DMA向memory写入的数据不匹配。问为什么会出现这种情况？
我问会不会有别的thread在此期间也写入内存，导致内存值被改动？Interviewer否定了这个可能，并且确认physical memory里面这个值只有DMA可以写，写操作也成功地完成了。
我绞尽脑汁，也没想出来是为什么。后来Interview提示光看code是看不出问题的，问题出在这个模块的架构上。因为ARM是通过cache从memory读取的，什么是cache呢？就是暂存前一次从memory里面读取的data的地方。如果memory没有改动，那么下一次读数据的时候，ARM就不需要去memory操作了，直接从cache拿可以了。这就是cache加速的原理。
导致上面的代码出现问题的原因在于，当blocking call跳出来的时候，说明memory的值已经被写入了，而这时候ARM上传的值却是从cache里面读取的，是旧的、在写入之前的值。
Debug，第一轮：
void arm_send_data(char *mem_data)
{
char result = 0;
check_sync_dma_arm();
cache_invalidated(); // fix
result = *mem_data;
send_data_to_dma_and_check(result);
...
check_sync_dma_arm();
cache_invalidated(); // fix
result = *mem_data;
send_data_to_dma_and_check(result);
return;
}
cache_invalidated()的作用是使得下一次从内存读数据的时候（result = *medm_data），ARM不再从cache里面读值，而直接去physical memory里面去拿，同时更新cache的内容。
OK，这个问题我想明白了，但是还没完。上面的代码中，读数据和传回给DMA的动作进行了两轮。但fix却只对第一轮起作用。第二轮的操作还是hang掉了。为什么呢？
还是想不出来，Interview再次给出答案：因为一模一样的result = *mem_data的语句出现了两次，所以在compiler作optimization的时候，把第二条赋值语句给省略了，没有编译。
我想了两个办法：
1. Turn off compiler's optimization －显然是不行的，不能因噎废食，对吗？
2. 再加一个变量的声明：char result1; 之后在第二次读取数据和传数据给DMA的时候，用result1 = *mem_data和send_data_to_dma_and_check(result1)就可以了。
第二个办法虽然可行，但显然比较麻烦，而且确实也没必要多开销一个变量。
其实最佳的解决办法很简单，就是对函数的形参mem_data做一个volatile的声明：
void arm_send_data(volatile char *mem_data)
在K&R的Bible的附录A.8.2里面，提到了这么一段：
The purpose of volatile is to force an implementation to suppress optimization that could otherwise occur. For example, for a machine with memory-mapped input/output, a pointer to a device register might be declared as a pointer to volatile, in order to prevent the compiler from removing apparently redundant references through the pointer.
另外，相关的资料也可参见下面的link：
http://en.wikibooks.org/wiki/Embedded_Systems/C_Programming
http://vault.embedded.com/story/OEG20010615S0107
http://publications.gbdirect.co.uk/c_book/chapter8/const_and_volatile.html
Subscribe to:
Posts (Atom)