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.