一个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，看来付出代价了。
Wednesday, April 6, 2011
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)