ARM Linux的一些片段（一）

因为工作原因，对这个部分有接触。平时看代码和一些文档的细节感觉过段时间就忘记了。所以要做个记录。可能其中还有错误。吧一个对人很有启发的记录下来。不过这些内容很零散，平时也是需要才看。以下说的arm是支持mmu的arm9以上.

Linux支持三级页表，作为其默认的页表结构。ARM是两极页表。PGD和PTE。从pgtable.h里面可以可以看出一个work around的实现。PGD和PTE并不是直接对应ARM硬件的页表目录项。而是做了一些为了linux上层的要求的一个方案。首先，他把4096个pgd项变成2048个，物理上还是一个pgd指向一个256个pte项的数组的，这没办法改。但是pgd指针逻辑上合并成一个，各自指向的的pte数组也合并。并且是连续的。

   pgd             pte
 57  * |        |
 58  * +--------+ +0
 59  * |        |-----> +------------+ +0
 60  * +- - - - + +4    |  h/w pt 0  |
 61  * |        |-----> +------------+ +1024
 62  * +--------+ +8    |  h/w pt 1  |
 63  * |        |       +------------+ +2048
 64  * +- - - - +       | Linux pt 0 |
 65  * |        |       +------------+ +3072
 66  * +--------+       | Linux pt 1 |
 67  * |        |       +------------+ +4096

以上内容摘自Linux ARM pgtable.h, GPL.

这512个pte项合并起来，这个pte分配的页（一般linux需要一个pte表在一个页里，代码注释也写了）还剩下一半的内容，刚好可以存放arm不支持的一些标记（Linux pt 0, 1)，而这些标记是linux必须的，比如dirty。这个方案还非常具有可扩展性，不依赖arm本身的标记。dirty标记的实现是通过对arm支持的权限fault的中断来写这个标记。这样方式是相当于一种模拟。

对于不同cpu版本，set_pte的实现是用宏##拼的函数，这些函数不再arch/arm/kernel而是arch/arm/mm里面,找个v6的实现里面可以看到实现：(这段代码上面的一段注释不知道是不是写错了， ptep - pointer to level 2 translation table entry (hardware version is stored at -1024 bytes)，明明是2048个字节，代码也是，也许是我理解错）
这里就看到先偏移2048个字节找到“真的”pte做事。

ENTRY(cpu_v6_set_pte)
154         str     r1, [r0], #-2048                @ linux version
155 
156         bic     r2, r1, #0x000003f0
157         bic     r2, r2, #0x00000003
158         orr     r2, r2, #PTE_EXT_AP0 | 2
...
            tst     r1, #L_PTE_PRESENT
176         moveq   r2, #0
177 
178         str     r2, [r0]
179         mcr     p15, 0, r0, c7, c10, 1 @ flush_pte
180         mov     pc, lr

关于ARM的模式，arm本来有7个模式，而linux只有两个user和kernel。于是Linux的实现就把包括中断处理模式页转到同一个模式下做事，就是arm的所谓超级用户（svc）模式，实现这个的办法就是改写备份寄存器spsr为svc的模式，然后movs pc到svc模式，然后再调用处理函数，这样除了用户模式其他的模式执行环境都是同一个模式了。
感觉选择svc模式作为kernel也是很自然的，swi一看就是用来做系统调用的，直接进入svc模式。
这段代码是在宏里面，然后根据不同模式进行展开在头部。

.macro  vector_stub, name, mode, correction=0
885         .align  5
886 
887 vector_\name:
888         .if \correction
889         sub     lr, lr, #\correction
890         .endif
891 
892         @
893         @ Save r0, lr_ (parent PC) and spsr_
894         @ (parent CPSR)
895         @
896         stmia   sp, {r0, lr}            @ save r0, lr
897         mrs     lr, spsr
898         str     lr, [sp, #8]            @ save spsr
899 
900         @
901         @ Prepare for SVC32 mode.  IRQs remain disabled.
902         @
903         mrs     r0, cpsr
904         eor     r0, r0, #(\mode ^ SVC_MODE)
905         msr     spsr_cxsf, r0
906 
907         @
908         @ the branch table must immediately follow this code
909         @
910         and     lr, lr, #0x0f
911         mov     r0, sp
912         ldr     lr, [pc, lr, lsl #2]
913         movs    pc, lr                  @ branch to handler in SVC mode
914         .endm

另外,对于不支持高向量的arm，因为中断向量表从0开始，所以需要把第一页保留，不作为用户空间。

排列生成

继续读TAOCP笔记，上次就准备写，一直没写。上次到格雷码再往后就没看了，看了非2进制格雷码。然后就来看排列生成。平时没时间看，只有厕所的时候翻一下。

排列生成给的第一个基本算法是一个老算法，但是看上去却不是那么明显的一个算法。初始化的a[1] <= a[2] <=... <= a[n]，然后生成所有按字典序的排列。

  while(1)
  {
1   VISIT(a);

2   j = n - 1; 
    while(a[j] >= a[j+1] && j > 0)
      j--;
    if(j == 0)return;

3   l = n;
    if(a[j] >= a[l])
      l --;
    swap(a[l], a[j]);

4   k = j + 1; l = n;
    while(k < l)
    {
      swap(a[k], a[l]);
      k ++; 
      l --;
    }
  }

这算法看上去一点都不明显，除掉外面的大循环，里面就是每次按照当前的a得到下一个字典序的a。 书上解释了这个算法的几个大步和历史。不过这个笔记记录我当时另外的一个方式来理解。从一个比较蠢的算法开始，得到本质上一致的解释。 一个明显简单的算法是：

per(a, i)
{
  if(i > N)
  {
    VISIT(a);
    return;
  }
  a[i] = 0;
  while(1)
  {
    a[i] = alloc(a[i]);
    if(a[i] == -1)
    {
      return;
    }  
    per(a, i + 1);
    free(a[i]);     
  }
}  

这是个递归的算法，相当简单，从排列最原始的想法开始，递增的填一个数，然后拼接剩下的数的排列，。这里填数需要一个类似分配的方法，所以叫做alloc,就是当前过程中还没用上的数,并且大于传入的参数以获得递增的去拿这些数。alloc的实现可以非常蠢，比如，标记所有已经用过的，然后从头走到尾，得到一个没用过的并且大于参数的结果。

第一个算法从第一个排列开始，第二个算法在第一次回朔之前也会到达这个状态，OK,第一个排列成功产生。 对于算法过程中任何一次回朔，第二个算法的执行的规律是：free掉这个数，回到上一次，这时候free掉的数将会被分配器回收，然而，如果上次尝试去alloc下一个数的时候，必须刚才free的比他目前所用的大，否则，他还得乖乖的free他的数，再回到上一次，一直进行下去。这是显然的。于是，第一个算法的第2步得到解释：获取一个能增长的a[j]，他的条件很简单：a[j] < a[j + 1].

我们找到了a[j],我们要从那个愚蠢的分配器中alloc一个新的数，在上次的回朔中，除了找到a[j]，还得到一个结果,a[j + 1] >= a[j + 2] >= ... >= a[n].有序的。这些数都被free而回收在分配器中，那么a[j]去调用alloc的结果就是从这一批数中得到那个最小的但是比a[j]大的数，所以第一个算法的第3步得到解释。a[l]就是alloc的结果。

这时候，第2个算法又要继续增加递归的深度了，很显然，a[j]增长了，接下来a[j + 1]...a[n]将从分配器中alloc到新的结果,显然，他们会是从小到大的顺序被分配，第一个算法的第4步讲得到这个分配到下次回朔之前的结果，也就是得到下一个排列的结果。那么排序就是了，不过这时候不需要冒泡也不需要快排，因为刚刚free的a[j]和a[l]交换之前是有序的：并且：

  a[l + 1] < a[l] < a[l - 1] 
  a[l + 1] < a[j] < a[l]         a[l]需要是比a[j]大的最小的数
所以
  a[l + 1] < a[j] < a[j - 1]

这意味着交换后这个本来是单调降序的依然保持着这个降序。这样重新排序为升序就是不断交换前后，老大变老末，老2变老末2。

这样，一个蠢算法就是相当于行动上证明了一个好算法。

这是谣言

最近听说合肥ZF内部有开会说15-20号可能有5.5级以上DZ发生，目前只通知GWY之类的内部职员，做好准备。对LBX不公布。安全起见，删除内容若干。

一定是个谣言。但是我要记下来。

谣言止于智者，我不是智者，在中国，我们都是瞎子。
谣言始于智者，我不是智者，在中国，我们都是傻子。
谣言！！

2009年4月6日晚地震

 
今天凌晨1点半，收到表弟的短信说晚上可能余震，他一切都好，他们小区的人都跑出来了，问我怎么样。我当时迷糊了，难道地震了？原来10点的时候肥东发生3.5级地震，合肥都有明显感觉。。。囧！我一点都没感觉到。

方言，优越感与普通话

上海人为了上海话动肝火，以前就猜到如果将来如果有对方言与普通话的激烈斗争，肯定是在上海，广东这些发达地区产生“大声音”。汉族的方言种类估计是没法计算的，因为很多地方不到几里路就是完全不一样的方言（我老家就是）。方言除了表达之外，还给了各色人贴上标签，典型的中国地域标签。本来方言和普通话的问题是不存在的，那些多语言的国家tmd语法不一样，也可以交流。如果我们保护方言，那就不要丢弃他，去研究他，搜集他。如果跨地域交流有问题，大家都学普通话。这里根本不矛盾。只要我们不去不允许说方言。普通话又可以给我们跨地域交流。挺好的事儿。

问题就是那些优越感一族非要死磕着他们觉得具有优越感的方言。拒绝普通话，还打着保护方言的幌子。其实他们内心瞧不起别的方言，不屑说普通话，因为只有那个方言才能体现他的优越感而已。

卸载金山词霸

金山词霸彻底被我废了，根据TR的推荐，选择灵格斯。
容易崩溃，启动的时候老是死在IE载入上，让人心烦。你出广告也不要影响我正常使用啊。
总是用IE打开链接，从来不尊重的浏览器选择。

说道词典软件，我就想起我上学时候写的单词猎手，一个简单的词典软件，当时想法还挺好的呢。也是开放词库，txt格式的词典。不过那个时候根本没有那么多热心的人来做词典。在csdn上只见下载不见有人联系我说增加词库。不过词典的编译是运行时开始的，启动速度成问题。后来换用硬盘持久的的索引和词库，不过那个设计我后来觉得有问题。就干掉了。另外有版权问题，有点怕。只敢从网上拼凑一个6级不到的词库。囧！

SGI被收购

SGI终于结束了。sigh, OpenGL.

不能用Blogger自带的编辑器

这玩意自动插的br会和pre在iE6下发生奇特的BUg. 算了，以后还是全手工来吧。

线程上下文友好的RPC

最近工作需要，把系统重新构造为多个processes。以前的api调用有部分转换为RPC。因此需要做一个RPC的模块原型。RPC的基本实现一般操作系统上都有介绍，最简单的模型是（基于Message的同步RPC)

Client:                           
...                              
rpc_call(){                     
   send(api_id, args);          
   recv(ret);
   return ret; 
}

Server:
                          
while(...) {
   recv(api_id, args)
   ret = call(api_id, args);
   send(ret);
}

如果server只有一个线程，那么所有的RPC call都是同步的。一般不会这么简单的去使用，于是Server会创建线程来来处理，可能是为每个调用，也可能为每个连接。这也是目前看到一些流行RPC的做法，也是KISS的做法。可是，当你不是去做新东西的，而是为了改造以前的东西的时候，这些KISS的就不能方便的直接用了。 稍微复杂一点，双向的RPC调用的处理。普通函数调用经常也会有callback的情况。也就是说双方都会成为Server。如果对方发送callback的RPC调用到当前调用者，如何处理会比较好。简单的应用上面的模型，callback会在调用者进程某个处理RPC的线程内处理。如果在这个Callback内部又要调用到对方，也就是出现乒乓球一般的你来我往，那么每次跨越进程都会有新的线程产生。这的确不太好，而且还有一个问题，就是普通函数经常会有同步callback，而且这个callback的线程环境需要是和caller相同的环境。当有这样的假设时候，用户就可能在一些递归的锁上出问题，比如递归的Mutex.以前OK的code因为线程环境的更换而死锁。（不过，的确用户不应该做这样假设。） 新的简单的做法就是，调用者在发出调用请求后，并不是等待结果，而是进入和server类似的行为，就是和对方做回和，在调用者线程内处理对方的call。

Client:
...                              
rpc_call() { 
   send(api_id, args);

   while(...) {
      recv(msg);
      switch msg type:
          case ret: return ret;
          case call: call api from msg   
   }
   return ret;                       
}

在这里，server的RPC处理函数call内部可以rpc_call回到Client，产生互相的递归调用。同时借用的双方本地堆栈。（一开始我用SystemV的share memory和semaphore，就需要自己维护这个堆栈，稍微麻烦一点，里面的socket操作send和recv都需要用semaphore取代。不过感觉share memory的stack不安全，最后还是放弃了而是使用简单的socket，扩展更好，只是需要一些数据的拷贝开销）。这样，以前同步callback的代码专程RPC之后，线程上下文将保持一至，并且少了重新连接和新建线程的开销。 以上只是示意的伪代码，实际实现还需要不少要考虑的东西。不过我对这个找到这个简单的解法感到满意。程序员不是总是遇到可以随意发挥的时候，面对曾经的那些泥潭，憋屈的时候也能找到coding的乐趣。

一个悖论，两个我

有想过一个奇特的问题，就是记忆的复制，好像以前也想过，写下来吧。

假设我们的大脑，或者说我们的意识活动是某个层次上的粒子的活动表现。粒子并不是说一定是某个物理上的概念。比如，如果你的意识是一段程序，那么你的粒子是0和1的组合，定义这个层次是为了一个”可复制“性。这段程序，很显然是可以复制0和1的方式到另外的机器上，独立运行。我们也一定能在这个层次上复制相同的状态过来。也就是说，出现了两个意识，两个我。这两个意识开始同时演绎，将会得到什么呢？

我睡着,冻结意识，复制一份，然后醒过来，”我“将是谁？如果这是成功的，我出现在任何一个新的”我“上都是无法解释的。找一个第三观察者，可以定义真的源头的”我“，和复制出来的”我“。两个”我“醒来后，将对新的”刺激“生成记忆和动作。那么，一开始的论述，相对源头的”我“，将不复存在。就是有多个”我“，世界出现了多个。世界是相对我的，不是绝对的。我看到了另一个”我“，和当前相对我的世界。我的记忆中还有睡着之前的记忆，甚至可以知道我是”真我“，这不重要，重要的是，不是复制了”我“， 而是复制了一个"世界"。


或者，我们的意识不能这样的”确定“和”复制“的， 他是随机的，或者无法冻结,无论如何，无法细分到一个层次定义出可复制的意识。哪怕我们有分子复制，或原子复制机之类的东西。"我"就是独一无二的？