看understanding linux kernel的一点笔记：
页表
通常32位cpu使用2级页表机制就已足够，但到64位时代，2级页表会使页表的项急剧增加，所以通常会使用更多的页表级数。
ia64/ppc64/alpha使用3级页表，x86_64使用到4级页表。为兼容这些模型，2.6.11之后使用了统一的4级页表模型
Global Directory
Upper Directory
Middle Directory
Page Table
针对不同的架构，设置每一级不同的地址位数，0的话就是不使用这一级页表机制。
cache
多cpu环境中，每个cpu有自己的cache，对cache的更新有硬件机制保证通知其他的cpu进行同步。(真的吗?)
tlb
用来cache页表，加速地址的转换速度。每个cpu有自己的tlb，但不需要同步，因为地址转换和进程相关。
posted @
2008-11-01 08:27 白色天堂 阅读(137) |
评论 (0) |
编辑 收藏
LinuxThreads:
旧的pthread实现，基于process实现pthread。主要问题是signal不符合规范，stack size固定???
NPTL:
2.6后加入的新实现，redhat as中2.4就可以支持。更符合pthread的规范。用户线程和内核线程采取1:1模式，支持floating stack。
posted @
2008-09-09 22:56 白色天堂 阅读(189) |
评论 (0) |
编辑 收藏
今天花了一点时间作了个x86上hotspot vm的disassembler，这样可以看出jvm生成的本地代码了。
代码比较简单，主要是用了udis86的库，这个可以在sf上下载到，它的接口还是比较简单的。
简单的例子，hotspot解析模式中iconst_0的对应汇编代码：
iconst_0 3 iconst_0 [0xb4d98120, 0xb4d98160] 64 bytes
0xb4d98120: sub esp, 0x4
0xb4d98123: fstp dword [esp]
0xb4d98126: jmp 0x1e
0xb4d9812b: sub esp, 0x8
0xb4d9812e: fstp qword [esp]
0xb4d98131: jmp 0x13
0xb4d98136: push edx
0xb4d98137: push eax
0xb4d98138: jmp 0xc
0xb4d9813d: push eax
0xb4d9813e: jmp 0x6
0xb4d98143: push eax
0xb4d98144: xor eax, eax
0xb4d98146: movzx ebx, byte [esi+0x1]
0xb4d9814a: inc esi
0xb4d9814b: jmp dword near [ebx*4+0x6900680]
posted @
2008-08-24 00:28 白色天堂 阅读(178) |
评论 (0) |
编辑 收藏
对soft reference，比较容易理解它的用处。它天生就是为实现cache来设计的。关于weak reference，好像很少有人说的清楚。有的和soft reference混在一起谈，有的就是简单翻译java doc中的说明，看得出翻译的人自己也不是很理解，所以只能一笔带过。
我也一直不是很清楚它的实际用途，今天我突然想到WeakReference可能的设计目的。
从java的内存泄漏说起，以前说到java也会内存泄漏的时候往往会举这样的例子，对象保存在一个全局表中，造成无法回收。一般的解决方法是不要使用全局表或者记得更新。但在实际开发中，有时必须要使用全局表，但无法明确知道该对象是否可销毁，因为对象可能被多个线程共享访问，所以程序不能确切的更新表中的引用。这时候weak reference就有用武之地，用WeakHashMap构造全局表，key和value之间是weak reference，这样的话程序员就不用考虑更新该表了，只要该对象没有强引用指向它，gc就可以回收它了。
回头去找一个实际的例子对照看看，记得在JDK中，weak reference还是用的很频繁的。
posted @
2008-07-25 22:51 白色天堂 阅读(606) |
评论 (0) |
编辑 收藏
以前用redhat的时候使用rpm管理软件包，因为不能解决软件的依赖关系后来转到debian。apt确实方便了很多，但一直怀念rpm的一个功能，rpm可以查询一个文件具体属于哪个包，用apt一直没有找到对应的命令。
今天想在64位ubuntu上编译32位程序的时候发现没有/usr/include/gnu/stub-32.h，在网上搜索时突然发现apt也可以根据文件来搜索包。命令是apt-file(缺省是没有安装的)。
先安装apt-file
使用apt-file update同步安装包内部的文件，它会到你定义的source去获取这些信息，运行会比较慢，而且没有什么提示，不知道今后会不会都是这样。
然后就可以用apt-file find xxx 去查询了。
－每天进步一点点， :)
posted @
2008-05-21 23:04 白色天堂 阅读(343) |
评论 (1) |
编辑 收藏
代码生成一般采用tree rewriting的方式，先将源代码转换成语法树的形式，通过模式匹配将子树替换成叶结点，同时生成代码指令，当树全部替换完后代码即生成了。采用这种方式主要关心匹配规则，甚至可以使用lex/yacc之类的工具生成code generator generator，也便于实现可移植的编译器。
dynamic programing
前面的算法如果只是从左往右依次匹配的话生成的代码质量不高，DP就是要考虑指令的代价，生成质量较优的代码。
自底向上为每个节点计算一系列值存入数组C[]，其中index代表使用的register数目，存储的是相应的代价(要考虑可能增加的store/load指令代价），计算某个节点的C[]时，先找到可能的匹配模式，根据匹配模式选择可能的寄存器数目组合，计算代价后选择最小值。这样遍历整个树后可以得到最小代价生成方式。
posted @
2008-05-07 05:14 白色天堂 阅读(261) |
评论 (0) |
编辑 收藏
最近看代码时看到Tarjan算法，搜索了一下，是个经典的求LCA（Least Common Ancestor)算法。奇怪的是，网上一般的介绍只会给出伪码，而且有关集合的实现都没有。为理解它还想了半天。目前有些细节还没有完全想清楚(主要和wikipedia上给出的伪码实现并不完全一致)，但根据我的理解，我的实现应该是可以完成功能。
基本描述：
本身是一个从根开始的深度优先搜索
1 为输入节点构建一个单节点的树 // MAKE_SET
2 对每个子节点，递归调用该算法完成子树内所有查询，
再将子节点的ancester指向本节点，归并结果树 // UNION
3 处理完所有子节点后，将本节点标为checked
4 遍历查询集中和该节点有关的查询，检查另一个节点是否已标为checked，如果是的话说明
1） 该节点在本节点的子树
2） 该节点和本节点在另一节点的子树中，而且该节点已被查询
无论哪种情况，检查该节点所在树的根就是这两个节点的LCA节点
如果没有标识checked，只需简单跳过，当遍历到该节点时就可以完成查询了
下面是java的实现代码和简单测试
import java.util.*;
public class Tarjan{
static void lca( Node p, ArrayList<Query> q ){
MAKE_SET(p);
//FIND(p).ancester=p;
for( Node i : p.childs){
lca( i, q );
UNION( p, i );
FIND(p).ancester=p;
}
p.checked=true;
for( Query query : q ){
if( query.p1==p ){
if( query.p2.checked ){
query.result=FIND(query.p2);
}
}else if( query.p2==p ){
if( query.p1.checked ){
query.result=FIND(query.p1);
}
}else{
continue;
}
}
}
static void MAKE_SET( Node p ){
p.ancester = p;
}
static Node FIND( Node p ){
Node r=p;
for( ; r.ancester!=r; r=r.ancester );
return r;
}
static void UNION( Node p, Node q ){
q.ancester=p;
}
public static void main( String args[] ){
// create tree
Node p[]=new Node[24];
p[0]=new Node(0,null); // root
p[1]=new Node(1,p[0]);
p[2]=new Node(2,p[0]);
p[3]=new Node(3,p[0]);
p[4]=new Node(4,p[1]);
p[5]=new Node(5,p[1]);
p[6]=new Node(6,p[1]);
p[7]=new Node(7,p[2]);
p[8]=new Node(8,p[2]);
p[9]=new Node(9,p[3]);
p[10]=new Node(10,p[3]);
p[11]=new Node(11,p[3]);
p[12]=new Node(12,p[4]);
p[13]=new Node(13,p[4]);
p[14]=new Node(14,p[6]);
p[15]=new Node(15,p[8]);
p[16]=new Node(16,p[10]);
p[17]=new Node(17,p[10]);
p[18]=new Node(18,p[14]);
p[19]=new Node(19,p[14]);
p[20]=new Node(20,p[17]);
p[21]=new Node(21,p[17]);
p[22]=new Node(22,p[17]);
p[23]=new Node(23,p[11]);
// make lca query
ArrayList< Query > q= new ArrayList<Query>();
q.add( new Query(p[15], p[19]));
q.add( new Query(p[21], p[16]));
q.add( new Query(p[14], p[14]));
q.add( new Query(p[4], p[23]));
q.add( new Query(p[23], p[16]));
// lca
lca( p[0], q );
// dump results
for( Query item : q ){
System.out.println( item.p1+":"+item.p2+": result is:"+item.result );
}
}
}
class Node{
public Node( int id, Node parent ){
this.id=id;
if( parent != null ){
parent.childs.add(this);
}else{
assert this.id==0;
}
this.checked=false;
this.ancester=null;
this.childs=new ArrayList<Node>();
}
int id;
ArrayList<Node> childs;
public String toString(){
return "Node:<"+id+">";
}
Node ancester; // used for lca search
boolean checked; // used for lca search
}
class Query{
public Query( Node p1, Node p2 ){
assert p1!=null && p2!=null;
this.p1=p1;
this.p2=p2;
this.result=null;
}
Node p1;
Node p2;
Node result;
}
测试使用的树：
0
+--------------+--------------------+
| | |
1 2 3
+-----+------+ +---+ +-------+---------+
| | | | | | | |
4 5 6 7 8 9 10 11
+---+ + + +--+------+ |
| | | | | | 23
12 13 14 15 16 17
+--------+ +----+----+
| | | | |
18 19 20 21 22
PS，差点忘了，祝lp生日快乐
posted @
2008-01-07 23:15 白色天堂 阅读(2232) |
评论 (0) |
编辑 收藏