新一代操作系统的构想

当一堆机器通过puppet、pssh这样的软件在管理的时候,你真想,如果它们共同运行一个操作系统,由那个操作系统统一替你协调这些机器该多好,而这个操作系统不能是openstack那种以机器(运行Linux、Windows这样的操作系统的环境)为单位的,而应该是以我的“程序”为单位的。软件架构,不能太过离散。

日志、定时器事件、用户、安装包……为什么不统一规划呢?以前的OS是面向单机的,现在的OS是面向群集的,这可能就是Elastos该出手的地方。

 | 281 views | 0 comments | 2 flags | 

[Pthread] Linux中的线程同步机制 — Futex

http://blog.csdn.net/Javadino/article/details/2891385

引子
在编译2.6内核的时候,你会在编译选项中看到[*] Enable futex support这一项,上网查,有的资料会告诉你”不选这个内核不一定能正确的运行使用glibc的程序”,那futex是什么?和glibc又有什么关系呢?

1. 什么是Futex
Futex是Fast Userspace muTexes的缩写,由Hubertus Franke, Matthew Kirkwood, Ingo Molnar and Rusty Russell共同设计完成。几位都是linux领域的专家,其中可能Ingo Molnar大家更熟悉一些,毕竟是O(1)调度器和CFS的实现者。

Futex按英文翻译过来就是快速用户空间互斥体。其设计思想其实不难理解,在传统的Unix系统中,System V IPC(inter process communication),如 semaphores, msgqueues, sockets还有文件锁机制(flock())等进程间同步机制都是对一个内核对象操作来完成的,这个内核对象对要同步的进程都是可见的,其提供了共享的状态信息和原子操作。当进程间要同步的时候必须要通过系统调用(如semop())在内核中完成。可是经研究发现,很多同步是无竞争的,即某个进程进入互斥区,到再从某个互斥区出来这段时间,常常是没有进程也要进这个互斥区或者请求同一同步变量的。但是在这种情况下,这个进程也要陷入内核去看看有没有人和它竞争,退出的时侯还要陷入内核去看看有没有进程等待在同一同步变量上。这些不必要的系统调用(或者说内核陷入)造成了大量的性能开销。为了解决这个问题,Futex就应运而生,Futex是一种用户态和内核态混合的同步机制。首先,同步的进程间通过mmap共享一段内存,futex变量就位于这段共享的内存中且操作是原子的,当进程尝试进入互斥区或者退出互斥区的时候,先去查看共享内存中的futex变量,如果没有竞争发生,则只修改futex,而不用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生,则还是得执行系统调用去完成相应的处理(wait 或者 wake up)。简单的说,futex就是通过在用户态的检查,如果了解到没有竞争就不用陷入内核了,大大提高了low-contention时候的效率。Linux从2.5.7开始支持Futex。

2. Futex系统调用
Futex是一种用户态和内核态混合机制,所以需要两个部分合作完成,linux上提供了sys_futex系统调用,对进程竞争情况下的同步处理提供支持。
其原型和系统调用号为
#include <linux/futex.h>
#include <sys/time.h>
int futex (int *uaddr, int op, int val, const struct timespec *timeout,int *uaddr2, int val3);
#define __NR_futex              240

虽然参数有点长,其实常用的就是前面三个,后面的timeout大家都能理解,其他的也常被ignore。
uaddr就是用户态下共享内存的地址,里面存放的是一个对齐的整型计数器。
op存放着操作类型。定义的有5中,这里我简单的介绍一下两种,剩下的感兴趣的自己去man futex
FUTEX_WAIT: 原子性的检查uaddr中计数器的值是否为val,如果是则让进程休眠,直到FUTEX_WAKE或者超时(time-out)。也就是把进程挂到uaddr相对应的等待队列上去。
FUTEX_WAKE: 最多唤醒val个等待在uaddr上进程。

可见FUTEX_WAIT和FUTEX_WAKE只是用来挂起或者唤醒进程,当然这部分工作也只能在内核态下完成。有些人尝试着直接使用futex系统调用来实现进程同步,并寄希望获得futex的性能优势,这是有问题的。应该区分futex同步机制和futex系统调用。futex同步机制还包括用户态下的操作,我们将在下节提到。

3. Futex同步机制
所有的futex同步操作都应该从用户空间开始,首先创建一个futex同步变量,也就是位于共享内存的一个整型计数器。
当进程尝试持有锁或者要进入互斥区的时候,对futex执行”down”操作,即原子性的给futex同步变量减1。如果同步变量变为0,则没有竞争发生,进程照常执行。如果同步变量是个负数,则意味着有竞争发生,需要调用futex系统调用的futex_wait操作休眠当前进程。
当进程释放锁或者要离开互斥区的时候,对futex进行”up”操作,即原子性的给futex同步变量加1。如果同步变量由0变成1,则没有竞争发生,进程照常执行。如果加之前同步变量是负数,则意味着有竞争发生,需要调用futex系统调用的futex_wake操作唤醒一个或者多个等待进程。

这里的原子性加减通常是用CAS(Compare and Swap)完成的,与平台相关。CAS的基本形式是:CAS(addr,old,new),当addr中存放的值等于old时,用new对其替换。在x86平台上有专门的一条指令来完成它: cmpxchg。

可见: futex是从用户态开始,由用户态和核心态协调完成的。

4. 进/线程利用futex同步
进程或者线程都可以利用futex来进行同步。
对于线程,情况比较简单,因为线程共享虚拟内存空间,虚拟地址就可以唯一的标识出futex变量,即线程用同样的虚拟地址来访问futex变量。
对于进程,情况相对复杂,因为进程有独立的虚拟内存空间,只有通过mmap()让它们共享一段地址空间来使用futex变量。每个进程用来访问futex的虚拟地址可以是不一样的,只要系统知道所有的这些虚拟地址都映射到同一个物理内存地址,并用物理内存地址来唯一标识futex变量。

小结:
1. Futex变量的特征:1)位于共享的用户空间中 2)是一个32位的整型 3)对它的操作是原子的
2. Futex在程序low-contention的时候能获得比传统同步机制更好的性能。
3. 不要直接使用Futex系统调用。
4. Futex同步机制可以用于进程间同步,也可以用于线程间同步。

那么应该如何使用Futex,它和glibc又有什么关系呢?下次继续。

在linux中进行多线程开发,同步是不可回避的一个问题。在POSIX标准中定义了三种线程同步机制: Mutexes(互斥量), Condition Variables(条件变量)和POSIX Semaphores(信号量)。NPTL基本上实现了POSIX,而glibc又使用NPTL作为自己的线程库。因此glibc中包含了这三种同步机制的实现(当然还包括其他的同步机制,如APUE里提到的读写锁)。

Glibc中常用的线程同步方式举例:

Semaphore:
变量定义:    sem_t sem;
初始化:      sem_init(&sem,0,1);
进入加锁:     sem_wait(&sem);
退出解锁:     sem_post(&sem);

Mutex:
变量定义:    pthread_mutex_t mut;
初始化:      pthread_mutex_init(&mut,NULL);
进入加锁:     pthread_mutex_lock(&mut);
退出解锁:     pthread_mutex_unlock(&mut);

这些用于同步的函数和futex有什么关系?下面让我们来看一看:
以Semaphores为例,
进入互斥区的时候,会执行sem_wait(sem_t *sem),sem_wait的实现如下:
int sem_wait (sem_t *sem)
{
int *futex = (int *) sem;
if (atomic_decrement_if_positive (futex) > 0)
return 0;
int   err = lll_futex_wait (futex, 0);
return -1;
)
atomic_decrement_if_positive()的语义就是如果传入参数是正数就将其原子性的减一并立即返回。如果信号量为正,在Semaphores的语义中意味着没有竞争发生,如果没有竞争,就给信号量减一后直接返回了。

如果传入参数不是正数,即意味着有竞争,调用lll_futex_wait(futex,0),lll_futex_wait是个宏,展开后为:
#define lll_futex_wait(futex, val) /
({                                          /

__asm __volatile (LLL_EBX_LOAD                          /
LLL_ENTER_KERNEL                          /
LLL_EBX_LOAD                          /
: “=a” (__status)                          /
: “0″ (SYS_futex), LLL_EBX_REG (futex), “S” (0),          /
“c” (FUTEX_WAIT), “d” (_val),                  /
“i” (offsetof (tcbhead_t, sysinfo))              /
: “memory”);                          /
…                                      /
})
可以看到当发生竞争的时候,sem_wait会调用SYS_futex系统调用,并在val=0的时候执行FUTEX_WAIT,让当前线程休眠。

从这个例子我们可以看出,在Semaphores的实现过程中使用了futex,不仅仅是说其使用了futex系统调用(再重申一遍只使用futex系统调用是不够的),而是整个建立在futex机制上,包括用户态下的操作和核心态下的操作。其实对于其他glibc的同步机制来说也是一样,都采纳了futex作为其基础。所以才会在futex的manual中说:对于大多数程序员不需要直接使用futexes,取而代之的是依靠建立在futex之上的系统库,如NPTL线程库(most programmers will in fact not be using futexes directly but instead rely on system libraries built on them, such as the NPTL pthreads implementation)。所以才会有如果在编译内核的时候不 Enable futex support,就”不一定能正确的运行使用Glibc的程序”。

小结:
1. Glibc中的所提供的线程同步方式,如大家所熟知的Mutex,Semaphore等,大多都构造于futex之上了,除了特殊情况,大家没必要再去实现自己的futex同步原语。
2. 大家要做的事情,似乎就是按futex的manual中所说得那样: 正确的使用Glibc所提供的同步方式,并在使用它们的过程中,意识到它们是利用futex机制和linux配合完成同步操作就可以了。

如果只是阅读理解,到这里也就够了,不过我们需要用实际行动印证一下,我们的理解是否正确。在实际使用过程中还遇到什么样的问题? 下次继续。

上回说到Glibc中(NPTL)的线程同步方式如Mutex,Semaphore等都使用了futex作为其基础。那么实际使用是什么样子,又会碰到什么问题呢?
先来看一个使用semaphore同步的例子。

sem_t sem_a;
void *task1();

int main(void){
int ret=0;
pthread_t thrd1;
sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL); //创建子线程
pthread_join(thrd1,NULL); //等待子线程结束
}

void *task1()
{
int sval = 0;
sem_wait(&sem_a); //持有信号量
sleep(5); //do_nothing
sem_getvalue(&sem_a,&sval);
printf(“sem value = %d/n”,sval);
sem_post(&sem_a); //释放信号量
}

程序很简单,我们在主线程(执行main的线程)中创建了一个线程,并用join等待其结束。在子线程中,先持有信号量,然后休息一会儿,再释放信号量,结束。
因为这段代码中只有一个线程使用信号量,也就是没有线程间竞争发生,按照futex的理论,因为没有竞争,所以所有的锁操作都将在用户态中完成,而不会执行系统调用而陷入内核。我们用strace来跟踪一下这段程序的执行过程中所发生的系统调用:

20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished …>
20534 futex(0×8049870, FUTEX_WAKE, 1)   = 0
20533 <… futex resumed> )             = 0

20533是main线程的id,20534是其子线程的id。出乎我们意料之外的是这段程序还是发生了两次futex系统调用,我们来分析一下这分别是什么原因造成的。

1. 出人意料的”sem_post()”
20534 futex(0×8049870, FUTEX_WAKE, 1)   = 0
子线程还是执行了FUTEX_WAKE的系统调用,就是在sem_post(&sem_a);的时候,请求内核唤醒一个等待在sem_a上的线程,其返回值是0,表示现在并没有线程等待在sem_a(这是当然的,因为就这么一个线程在使用sem_a),这次futex系统调用白做了。这似乎和futex的理论有些出入,我们再来看一下sem_post的实现。
int sem_post (sem_t *sem)
{
int *futex = (int *) sem;
int nr = atomic_increment_val (futex);
int err = lll_futex_wake (futex, nr);
return 0;
}
我们看到,Glibc在实现sem_post的时候给futex原子性的加上1后,不管futex的值是什么,都执行了lll_futex_wake(),即futex(FUTEX_WAKE)系统调用。
在第二部分中(见前文),我们分析了sem_wait的实现,当没有竞争的时候是不会有futex调用的,现在看来真的是这样,但是在sem_post的时候,无论有无竞争,都会调用sys_futex(),为什么会这样呢?我觉得应该结合semaphore的语义来理解。在semaphore的语义中,sem_wait()的意思是:”挂起当前进程,直到semaphore的值为非0,它会原子性的减少semaphore计数值。” 我们可以看到,semaphore中是通过0或者非0来判断阻塞或者非阻塞线程。即无论有多少线程在竞争这把锁,只要使用了semaphore,semaphore的值都会是0。这样,当线程推出互斥区,执行sem_post(),释放semaphore的时候,将其值由0改1,并不知道是否有线程阻塞在这个semaphore上,所以只好不管怎么样都执行futex(uaddr, FUTEX_WAKE, 1)尝试着唤醒一个进程。而相反的,当sem_wait(),如果semaphore由1变0,则意味着没有竞争发生,所以不必去执行futex系统调用。我们假设一下,如果抛开这个语义,如果允许semaphore值为负,则也可以在sem_post()的时候,实现futex机制。

2. 半路杀出的”pthread_join()”
那另一个futex系统调用是怎么造成的呢? 是因为pthread_join();
在Glibc中,pthread_join也是用futex系统调用实现的。程序中的pthread_join(thrd1,NULL); 就对应着
20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished …>
很好解释,主线程要等待子线程(id号20534上)结束的时候,调用futex(FUTEX_WAIT),并把var参数设置为要等待的子线程号(20534),然后等待在一个地址为0xb7db1be8的futex变量上。当子线程结束后,系统会负责把主线程唤醒。于是主线程就
20533 <… futex resumed> )             = 0
恢复运行了。
要注意的是,如果在执行pthread_join()的时候,要join的线程已经结束了,就不会再调用futex()阻塞当前进程了。

3. 更多的竞争。
我们把上面的程序稍微改改:
在main函数中:
int main(void){

sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL);
ret=pthread_create(&thrd2,NULL,task1,NULL);
ret=pthread_create(&thrd3,NULL,task1,NULL);
ret=pthread_create(&thrd4,NULL,task1,NULL);
pthread_join(thrd1,NULL);
pthread_join(thrd2,NULL);
pthread_join(thrd3,NULL);
pthread_join(thrd4,NULL);

}

这样就有更的线程参与sem_a的争夺了。我们来分析一下,这样的程序会发生多少次futex系统调用。
1) sem_wait()
第一个进入的线程不会调用futex,而其他的线程因为要阻塞而调用,因此sem_wait会造成3次futex(FUTEX_WAIT)调用。
2) sem_post()
所有线程都会在sem_post的时候调用futex, 因此会造成4次futex(FUTEX_WAKE)调用。
3) pthread_join()
别忘了还有pthread_join(),我们是按thread1, thread2, thread3, thread4这样来join的,但是线程的调度存在着随机性。如果thread1最后被调度,则只有thread1这一次futex调用,所以pthread_join()造成的futex调用在1-4次之间。(虽然不是必然的,但是4次更常见一些)
所以这段程序至多会造成3+4+4=11次futex系统调用,用strace跟踪,验证了我们的想法。
19710 futex(0xb7df1be8, FUTEX_WAIT, 19711, NULL <unfinished …>
19712 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19713 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19714 futex(0×8049910, FUTEX_WAIT, 0, NULL <unfinished …>
19711 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb75f0be8, FUTEX_WAIT, 19712, NULL <unfinished …>
19712 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb6defbe8, FUTEX_WAIT, 19713, NULL <unfinished …>
19713 futex(0×8049910, FUTEX_WAKE, 1 <unfinished …>
19710 futex(0xb65eebe8, FUTEX_WAIT, 19714, NULL <unfinished …>
19714 futex(0×8049910, FUTEX_WAKE, 1)   = 0
(19710是主线程,19711,19712,19713,19714是4个子线程)

4. 更多的问题
事情到这里就结束了吗? 如果我们把semaphore换成Mutex试试。你会发现当自始自终没有竞争的时候,mutex会完全符合futex机制,不管是lock还是unlock都不会调用futex系统调用。有竞争的时候,第一次pthread_mutex_lock的时候不会调用futex调用,看起来还正常。但是最后一次pthread_mutex_unlock的时候,虽然已经没有线程在等待mutex了,可还是会调用futex(FUTEX_WAKE)。这又是什么原因造成的呢?留给感兴趣的同学去分析吧。

小结:
1. 虽然semaphore,mutex等同步方式构建在futex同步机制之上。然而受其语义等的限制,并没有完全按futex最初的设计实现。
2. pthread_join()等函数也是调用futex来实现的。
3. 不同的同步方式都有其不同的语义,不同的性能特征,适合于不同的场景。我们在使用过程中要知道他们的共性,也得了解它们之间的差异。这样才能更好的理解多线程场景,写出更高质量的多线程程序。

至此futex的学习就告一段落了,希望对大家有所帮助。

 | 72 views | 0 comments | 0 flags | 

linux 内核的几种锁介绍

linux 内核的几种锁介绍

spinlock(自旋锁)、 mutex(互斥量)、 semaphore(信号量)、 critical section(临界区) 的作用与区别
Mutex是一把钥匙,一个人拿了就可进入一个房间,出来的时候把钥匙交给队列的第一个。一般的用法是用于串行化对critical section代码的访问,保证这段代码不会被并行的运行。
Semaphore是一件可以容纳N人的房间,如果人不满就可以进去,如果人满了,就要等待有人出来。对于N=1的情况,称为binary semaphore。一般的用法是,用于限制对于某一资源的同时访问。
Binary semaphore与Mutex的差异:
在有的系统中Binary semaphore与Mutex是没有差异的。在有的系统上,主要的差异是mutex一定要由获得锁的进程来释放。而semaphore可以由其它进程释放(这时的semaphore实际就是个原子的变量,大家可以加或减),因此semaphore可以用于进程间同步。Semaphore的同步功能是所有系统都支持的,而Mutex能否由其他进程释放则未定,因此建议mutex只用于保护critical section。而semaphore则用于保护某变量,或者同步。
另一个概念是spin lock,这是一个内核态概念。spin lock与semaphore的主要区别是spin lock是busy waiting,而semaphore是sleep。对于可以sleep的进程来说,busy waiting当然没有意义。对于单CPU的系统,busy waiting当然更没意义(没有CPU可以释放锁)。因此,只有多CPU的内核态非进程空间,才会用到spin lock。Linux kernel的spin lock在非SMP的情况下,只是关irq,没有别的操作,用于确保该段程序的运行不会被打断。其实也就是类似mutex的作用,串行化对 critical section的访问。但是mutex不能保护中断的打断,也不能在中断处理程序中被调用。而spin lock也一般没有必要用于可以sleep的进程空间。
———————————————————————————————
内核同步措施
为了避免并发,防止竞争。内核提供了一组同步方法来提供对共享数据的保护。我们的重点不是介绍这些方法的详细用法,而是强调为什么使用这些方法和它们之间的差别。
Linux 使用的同步机制可以说从2.0到2.6以来不断发展完善。从最初的原子操作,到后来的信号量,从大内核锁到今天的自旋锁。这些同步机制的发展伴随 Linux从单处理器到对称多处理器的过度;伴随着从非抢占内核到抢占内核的过度。锁机制越来越有效,也越来越复杂。目前来说内核中原子操作多用来做计数使用,其它情况最常用的是两种锁以及它们的变种:一个是自旋锁,另一个是信号量。我们下面就来着重介绍一下这两种锁机制。
自旋锁
自旋锁是专为防止多处理器并发而引入的一种锁,它在内核中大量应用于中断处理等部分(对于单处理器来说,防止中断处理中的并发可简单采用关闭中断的方式,不需要自旋锁)。
自旋锁最多只能被一个内核任务持有,如果一个内核任务试图请求一个已被争用(已经被持有)的自旋锁,那么这个任务就会一直进行忙循环——旋转——等待锁重新可用。要是锁未被争用,请求它的内核任务便能立刻得到它并且继续进行。自旋锁可以在任何时刻防止多于一个的内核任务同时进入临界区,因此这种锁可有效地避免多处理器上并发运行的内核任务竞争共享资源。
事实上,自旋锁的初衷就是:在短期间内进行轻量级的锁定。一个被争用的自旋锁使得请求它的线程在等待锁重新可用的期间进行自旋(特别浪费处理器时间),所以自旋锁不应该被持有时间过长。如果需要长时间锁定的话, 最好使用信号量。
自旋锁的基本形式如下:
spin_lock(&mr_lock);     //临界区
spin_unlock(&mr_lock);
因为自旋锁在同一时刻只能被最多一个内核任务持有,所以一个时刻只有一个线程允许存在于临界区中。这点很好地满足了对称多处理机器需要的锁定服务。在单处理器上,自旋锁仅仅当作一个设置内核抢占的开关。如果内核抢占也不存在,那么自旋锁会在编译时被完全剔除出内核。
简单的说,自旋锁在内核中主要用来防止多处理器中并发访问临界区,防止内核抢占造成的竞争。另外自旋锁不允许任务睡眠(持有自旋锁的任务睡眠会造成自死锁——因为睡眠有可能造成持有锁的内核任务被重新调度,而再次申请自己已持有的锁),它能够在中断上下文中使用。
死锁:假设有一个或多个内核任务和一个或多个资源,每个内核都在等待其中的一个资源,但所有的资源都已经被占用了。这便会发生所有内核任务都在相互等待,但它们永远不会释放已经占有的资源,于是任何内核任务都无法获得所需要的资源,无法继续运行,这便意味着死锁发生了。自死琐是说自己占有了某个资源,然后自己又申请自己已占有的资源,显然不可能再获得该资源,因此就自缚手脚了。
信号量
Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个已被持有的信号量时,信号量会将其推入等待队列,然后让其睡眠。这时处理器获得自由去执行其它代码。当持有信号量的进程将信号量释放后,在等待队列中的一个任务将被唤醒,从而便可以获得这个信号量。
信号量的睡眠特性,使得信号量适用于锁会被长时间持有的情况;只能在进程上下文中使用,因为中断上下文中是不能被调度的;另外当代码持有信号量时,不可以再持有自旋锁。
信号量基本使用形式为:
static DECLARE_MUTEX(mr_sem);//声明互斥信号量
if(down_interruptible(&mr_sem))
//可被中断的睡眠,当信号来到,睡眠的任务被唤醒
//临界区
up(&mr_sem);
信号量和自旋锁区别
虽然听起来两者之间的使用条件复杂,其实在实际使用中信号量和自旋锁并不易混淆。注意以下原则:
如果代码需要睡眠——这往往是发生在和用户空间同步时——使用信号量是唯一的选择。由于不受睡眠的限制,使用信号量通常来说更加简单一些。如果需要在自旋锁和信号量中作选择,应该取决于锁被持有的时间长短。理想情况是所有的锁都应该尽可能短的被持有,但是如果锁的持有时间较长的话,使用信号量是更好的选择。另外,信号量不同于自旋锁,它不会关闭内核抢占,所以持有信号量的代码可以被抢占。这意味者信号量不会对影响调度反应时间带来负面影响。
自旋锁对信号量
需求 建议的加锁方法
低开销加锁               优先使用自旋锁
短期锁定                 优先使用自旋锁
长期加锁                 优先使用信号量
中断上下文中加锁         使用自旋锁
持有锁是需要睡眠、调度   使用信号量
———————————————————————————————
临界区(Critical Section)
保证在某一时刻只有一个线程能访问数据的简便办法。在任意时刻只允许一个线程对共享资源进行访问。如果有多个线程试图同时访问临界区,那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起,并一直持续到进入临界区的线程离开。临界区在被释放后,其他线程可以继续抢占,并以此达到用原子方式操作共享资源的目的。
在使用临界区时,一般不允许其运行时间过长,只要进入临界区的线程还没有离开,其他所有试图进入此临界区的线程都会被挂起而进入到等待状态,并会在一定程度上影响。程序的运行性能。尤其需要注意的是不要将等待用户输入或是其他一些外界干预的操作包含到临界区。如果进入了临界区却一直没有释放,同样也会引起其他线程的长时间等待。虽然临界区同步速度很快,但却只能用来同步本进程内的线程,而不可用来同步多个进程中的线程。
互斥量(Mutex)
互斥(Mutex)是一种用途非常广泛的内核对象。能够保证多个线程对同一共享资源的互斥访问。同临界区有些类似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。与其他几种内核对象不同,互斥对象在操作系统中拥有特殊代码,并由操作系统来管理,操作系统甚至还允许其进行一些其他内核对象所不能进行的非常规操作。互斥量跟临界区很相似,只有拥有互斥对象的线程才具有访问资源的权限,由于互斥对象只有一个,因此就决定了任何情况下此共享资源都不会同时被多个线程所访问。当前占据资源的线程在任务处理完后应将拥有的互斥对象交出,以便其他线程在获得后得以访问资源。互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享,而且可以在不同应用程序的线程之间实现对资源的安全共享。

信号量(Semaphores)
信号量对象对线程的同步方式与前面几种方法不同,信号允许多个线程同时使用共享资源,这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程最大数目。它允许多个线程在同一时刻访问同一资源,但是需要限制在同一时刻访问此资源的最大线程数目。在用CreateSemaphore()创建信号量时即要同时指出允许的最大资源计数和当前可用资源计数。一般是将当前可用资源计数设置为最大资源计数,每增加一个线程对共享资源的访问,当前可用资源计数就会减1,只要当前可用资源计数是大于0的,就可以发出信号量信号。但是当前可用计数减小到0时则说明当前占用资源的线程数已经达到了所允许的最大数目,不能在允许其他线程的进入,此时的信号量信号将无法发出。线程在处理完共享资源后,应在离开的同时通过ReleaseSemaphore()函数将当前可用资源计数加1。在任何时候当前可用资源计数决不可能大于最大资源计数。信号量是通过计数来对线程访问资源进行控制的,而实际上信号量确实也被称作Dijkstra计数器。
PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数,S大于等于零时代表可供并发进程使用的资源实体数,但S小于零时则表示正在等待使用共享资源的进程数。
P操作申请资源:
(1)S减1;
(2)若S减1后仍大于等于零,则进程继续执行;
(3)若S减1后小于零,则该进程被阻塞后进入与该信号相对应的队列中,然后转入进程调度。
V操作释放资源:     (1)S加1;
(2)若相加结果大于零,则进程继续执行;
(3)若相加结果小于等于零,则从该信号的等待队列中唤醒一个等待进程,然后再返回原进程继续执行或转入进程调度。
信号量的使用特点使其更适用于对Socket(套接字)程序中线程的同步。例如,网络上的HTTP服务器要对同一时间内访问同一页面的用户数加以限制,这时可以为没一个用户对服务器的页面请求设置一个线程,而页面则是待保护的共享资源,通过使用信号量对线程的同步作用可以确保在任一时刻无论有多少用户对某一页面进行访问,只有不大于设定的最大用户数目的线程能够进行访问,而其他的访问企图则被挂起,只有在有用户退出对此页面的访问后才有可能进入。
总结:
1.互斥量与临界区的作用非常相似,但互斥量是可以命名的,也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多,所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建,就可以通过名字打开它。
2.互斥量(Mutex),信号灯(Semaphore)都可以被跨越进程使用来进行同步数据操作,而其他的对象与数据同步操作无关,但对于进程和线程来讲,如果进程和线程在运行状态则为无信号状态,在退出后为有信号状态。
3.通过互斥量可以指定资源被独占的方式使用,但如果有下面一种情况通过互斥量就无法处理,比如现在一位用户购买了一份三个并发访问许可的数据库系统,可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作,这时候如果利用互斥量就没有办法完成这个要求,信号灯对象可以说是一种资源计数器。

 | 40 views | 0 comments | 0 flags | 

【转】函数式思维和函数式编程

http://www.linuxeden.com/html/news/20140905/155374.html

作为一个对Hashell语言[1]彻头彻尾的新手,当第一次看到一个用这种语言编写的快速排序算法的优雅例子时,我立即对这种语言发生了浓厚的兴趣。下面就是这个例子:

quicksort :: Ord a => [a] -> [a]  
quicksort [] = []  
quicksort (p:xs) =  
    (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

我很困惑。如此的简单和漂亮,能是正确的吗?的确,这种写法并不是“完全正确”的最优快速排序实现。但是,我在这里并不想深入探讨性能上的问题 [2]。我想重点强调的是,纯函数式编程是一种思维上的改变,是一种完全不同的编程思维模式和方法,就相当于你要重新开始学习另外一种编程方式。

首先,让我先定义一个问题,然后用函数式的方式解决它。我们要做的基本上就是按升序排序一个数组。为了完成这个任务,我使用曾经改变了我们这个世界的快速排序算法[3],下面是它几个基本的排序规则:

  • 如果数组只有一个元素,返回这个数组
  • 多于一个元素时,随机选择一个基点元素P,把数组分成两组。使得第一组中的元素全部 <p,第二组中的全部元素 >p。然后对这两组数据递归的使用这种算法。

那么,如何用函数式的方式思考、函数式的方式编程实现?在这里,我将模拟同一个程序员的两个内心的对话,这两个内心的想法很不一样,一个使用命令式 的编程思维模式,这是这个程序员从最初学习编码就形成的思维模式。而第二个内心做了一些思想上的改造,清洗掉了所有以前形成的偏见:用函数式的方式思考。事实上,这程序员就是我,现在正在写这篇文章的我。你将会看到两个完全不同的我。没有半点假话。

让我们在这个简单例子上跟Java进行比较:

public class Quicksort  {  
  private int[] numbers;
  private int number;
  public void sort(int[] values) {
    if (values == null || values.length == 0){
      return;
    }
    this.numbers = values;
    number = values.length;
    quicksort(0, number - 1);
  }
  private void quicksort(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];
    while (i <= j) {
      while (numbers[i] < pivot) {
        i++;
      }
      while (numbers[j] > pivot) {
        j--;
      }
      if (i <= j) {
        swap(i, j);
        i++;
        j--;
      }
    }
    if (low < j)
      quicksort(low, j);
    if (i < high)
      quicksort(i, high);
  }
  private void swap(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
  }
}

哇塞。到处都是ij,这是干嘛呢?为什么Java代码跟Haskell代码比较起来如此的长?这就好像是30年前拿C语言和汇编语言进行比较!从某种角度看,这是同量级的差异。[4]

让我们俩继续两个”我”之间的对话。

JAVA:

好 ,我先开始定义Java程序需要的数据结构。一个类,里面含有一些属性来保存状态。我觉得应该使用一个整数数组作为主要数据对象,针对这个数组进行排序。还有一个方法叫做sort,它有一个参数,是用来传入两个整数做成的数组,sort方法就是用来对这两个数进行排序。

public class Quicksort {  
    private int[] numbers;
    public void sort(int[] values) {
    }
}

HASKELL:

好,这里不需要状态,不需要属性。我需要定义一个函数,用它来把一个list转变成另一个list。这两个list有相同 之处,它们都包含一样的元素,并有各自的顺序。我如何用统一的形式描述这两个list?啊哈!typeclass….我需要一个typeclass来实现 这个…对,Ord.

quicksort :: Ord a => [a] -> [a]

JAVA:

我要从简单的开始,如果是空数组,如果数组是空的,我应该返回这个数组。但是…该死的,当这个数组是null时,程序会崩溃。让我来在sort方法开始的地方加一个if语句,预防这种事情。

if (values.length == 0 || values == null) {  
    return;
}

HASKELL:

先简单的,一个空list。对于这种情况,需要使用模式匹配。我看看如何使用,好的,非常棒!

quicksort [] = []

JAVA:

好的,现在让我用递归来处理正常的情况。正常的情况下,需要记录sort方法参数状态。需要它的长度,所以,我还需要在Quicksort类里添加一个新属性。

public void sort(int[] values) {  
    if (values.length == 0 || values == null) {
        return;
    }
    this.numbers = values;
    this.length = values.length;
    quicksort(0, length - 1);
}

HASKELL:

这已经是递归了。不需要在再做任何事情。

No code. Nothing. Nada. That's good.

JAVA:

现在,我需要根据上面说明的规则实现快速排序的过程。我选择第一个元素作为基点元素,这不需要使用其它奇异方法。比较,递归。每次比较从两头同时遍历,一个从头至尾(i, 生成<p的list),一个从尾至头(j, 生成>p的list)。每次在i方向遍历中发现有比j方向遍历的当前值大时,交互它们的位置。当i的位置超过j时,停止比较,对形成的两个新队列继续递归调用。

private void quicksort(int low, int high) {  
    int i = low, j = high;
    int pivot = numbers[low];
    while (i <= j) {
        while (numbers[i] < pivot) {
           i++;
        }
        while (numbers[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(i, j);
            i++;
            j--;
        }
    }
    if (low < j)
        quicksort(low, j);
    if (i < high)
        quicksort(i, high);
}

交换位置的方法:

private void swap(int i, int j) {  
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

使用Haskell

我先定义一个lesser和一个greater作为每次迭代的两个队列。等一下!我们可以使用标准的headtail函数来获取第一个值作为基点数据。这样我们可以它的两个部分进行递归调用!

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)

非常好,这里我声明了lessergreater两个list,现在我将要用where——Haskell语言里一个十分强大的用来描述函数内部值(not 变量)的关键字——描述它们。我需要使用filter函数,因为我们已经得到除首元素之外的其它元素,我们可以调用(xs),就是这样:

    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

我试图用最详细的语言解释Java里用迭代+递归实现快速排序。但是,如果在java代码里,我们少写了一个i++,我们弄错了一个while循环条件,会怎样?好吧,这是一个相对简单的算法。但我们可以想象一下,如果我们整天写这样的代码,整天面对这样的程序,或者这个排序只是一个非常复杂的算法的第一步,将会出现什么情况。当然,它是可以用的,但难免会产生潜在的、内部的bug。

现在我们看一下关于状态的这些语句。如果出于某些原因,这个数组是空的,变成了null,当我们调用这个Java版的快速排序方法时会出现什么情况?还有性能上的同步执行问题,如果16个线程想同时访问Quicksort方法会怎样?我们就要需要监控它们,或者让每个线程拥有一个实例。越来越乱。

最终归结到编译器的问题。编译器应该足够聪明,能够“猜”出应该怎样做,怎样去优化[5]。程序员不应该去思考如何索引,如何处理数组。程序员应该 思考数据本身,如何按要求变换数据。也许你会认为函数式编程给思考算法和处理数据增添的复杂,但事实上不是这样。是编程界普遍流行的命令式编程的思维阻碍 了我们。

事实上,你完全没必要放弃使用你喜爱的命令式编程语言而改用Haskell编程。Haskell语言有其自身的缺陷[6]。只要你能够接受函数式编程思维,你就能写出更好的Java代码。你通过学习函数式编程能变成一个更优秀的程序员。

看看下面的这种Java代码?

public List<Comparable> sort(List<Comparable> elements) {  
    if (elements.size() == 0return elements;
    Stream<Comparable> lesser = elements.stream()
    .filter(x -> x.compareTo(pivot) < 0)
    .collect(Collectors.toList());
    Stream<Comparable> greater = elements.stream()
    .filter(x -> x.compareTo(pivot) >= 0)
    .collect(Collectors.toList());
    List<Comparable> sorted = new ArrayList<Comparable>();
    sorted.addAll(quicksort(lesser));
    sorted.add(pivot);
    sorted.addAll(quicksort(greater));
    return sorted;
}

是不是跟Haskell代码很相似?没错,也许你现在使用的Java版本无法正确的运行它,这里使用了lambda函数,Java8中引入的一种非常酷的语法[7]。看到没有,函数式语法不仅能让一个程序员变得更优秀,也会让一种编程语言更优秀。 :)

函数式编程是一种编程语言向更高抽象阶段发展的自然进化结果。就跟我们认为用C语言开发Web应用十分低效一样,这些年来,我们也认为命令式编程语言也是如此。使用这些语言是程序员在开发时间上的折中选择。为什么很多初创公司会选择Ruby开发他们的应用,而不是使用C++?因为它们能使开发周期更短。不要误会。我们可以把一个程序员跟一个云计算单元对比。一个程序员一小时的时间比一个高性能AWS集群服务器一小时的时间昂贵的多。通过让犯错误更难,让出现bug的几率更少,使用更高的抽象设计,我们能使程序员变得更高效、更具创造性和更有价值。

标注:

[1] Haskell from scratch courtesy of “Learn you a Haskell for Great Good!”

[2] This quicksort in Haskell that I am showing here is not in-place quicksort so it loses one of its properties, which is memory efficiency. The in-place version in Haskell would be more like:

import qualified Data.Vector.Generic as V  
import qualified Data.Vector.Generic.Mutable as M 
qsort :: (V.Vector v a, Ord a) => v a -> v a  
qsort = V.modify go where  
    go xs | M.length xs < 2 return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

Discussion here.

[3] This version of quicksort is simplified for illustration purposes. It’s always good looking at the source. Boldly go and read this piece of History (with a capital H) by C.A.R. Hoare, “Quicksort”.

[4] Taken from http://www.vogella.com/tutorials/JavaAlgorithmsQuicksort/article.html

[4] Will we consider uncontrolled state harmful the same way GOTO statement being considered harmful consolidated structured programming?

[5] This wiki has LOTS of architectural information about the amazing Glasgow Haskell Compiler, ghchttps://ghc.haskell.org/trac/ghc/wiki/Commentary

[6] A big question mark over time on functional programming languages has been the ability (or lack thereof) to effectively code User Interfaces. Don’t despair though! There’s this cool new thing called Functional Reactive Programming (FRP). Still performing babysteps, but there are already implementations out there. One that’s gaining lots of momentum is ReactJS/Om/ClojureScript web app stack. Guess that might be a good follow-up post :)

[7] See http://zeroturnaround.com/rebellabs/java-8-explained-applying-lambdas-to-java-collections/

[英文原文:Programming (and thinking) the functional way ]

转自 http://www.vaikan.com/programming-thinking-functional-way/

 | 56 views | 0 comments | 0 flags | 

【转】Go语言并发之美

http://qing.blog.sina.com.cn/2294942122/88ca09aa33002ele.html

简介
        多核处理器越来越普及,那有没有一种简单的办法,能够让我们写的软件释放多核的威力?答案是:Yes。随着Golang, Erlang, Scale等为并发设计的程序语言的兴起,新的并发模式逐渐清晰。正如过程式编程和面向对象一样,一个好的编程模式需要有一个极其简洁的内核,还有在此之上丰富的外延,可以解决现实世界中各种各样的问题。本文以GO语言为例,解释其中内核、外延。
并发模式之内核
        这种并发模式的内核只需要协程和通道就够了。其中协程负责执行代码,通道负责在协程之间传递事件。
Go语言并发之美
        并发编程一直以来都是个非常困难的工作。要想编写一个良好的并发程序,我们不得不了解线程,锁,semaphore,barrier甚至CPU更新高速缓存的方式,而且他们个个都有怪脾气,处处是陷阱。笔者除非万不得以,决不会自己操作这些底层并发元素。一个简洁的并发模式不需要这些复杂的底层元素,只需协程和通道就够了。
        协程是轻量级的线程。在过程式编程中,当调用一个过程的时候,需要等待其执行完才返回。而调用一个协程的时候,不需要等待其执行完,会立即返回。协程十分轻量,Go语言可以在一个进程中执行有数以十万计的协程,依旧保持高性能。而对于普通的平台,一个进程有数千个线程,其CPU会忙于上下文切换,性能急剧下降。随意创建线程可不是一个好主意,但是我们可以大量使用的协程。

        通道是协程之间的数据传输通道。通道可以在众多的协程之间传递数据,具体可以值也可以是个引用。通道有两种使用方式。

·  协程可以试图向通道放入数据,如果通道满了,会挂起协程,直到通道可以为他放入数据为止。

·  协程可以试图向通道索取数据,如果通道没有数据,会挂起协程,直到通道返回数据为止。

如此,通道就可以在传递数据的同时,控制协程的运行。有点像事件驱动,也有点像阻塞队列。这两个概念非常的简单,各个语言平台都会有相应的实现。在Java和C上也各有库可以实现两者。

Go语言并发之美
        只要有协程和通道,就可以优雅的解决并发的问题。不必使用其他和并发有关的概念。那如何用这两把利刃解决各式各样的实际问题呢?
并发模式之外延
        协程相较于线程,可以大量创建。打开这扇门,我们拓展出新的用法,可以做生成器,可以让函数返回“服务”,可以让循环并发执行,还能共享变量。但是出现新的用法的同时,也带来了新的棘手问题,协程也会泄漏,不恰当的使用会影响性能。下面会逐一介绍各种用法和问题。演示的代码用GO语言写成,因为其简洁明了,而且支持全部功能。
生成器
       有的时候,我们需要有一个函数能不断生成数据。比方说这个函数可以读文件,读网络,生成自增长序列,生成随机数。这些行为的特点就是,函数的已知一些变量,如文件路径。然后不断调用,返回新的数据。
Go语言并发之美

下面生成随机数为例,以让我们做一个会并发执行的随机数生成器。

非并发的做法是这样的:

// 函数rand_generator_1 ,返回 int

funcrand_generator_1() int {

return rand.Int()

}

        上面是一个函数,返回一个int。假如rand.Int()这个函数调用需要很长时间等待,那该函数的调用者也会因此而挂起。所以我们可以创建一个协程,专门执行rand.Int()。

// 函数rand_generator_2,返回通道(Channel)

funcrand_generator_2() chan int {

// 创建通道

out := make(chan int)

// 创建协程

go func() {

for {

//向通道内写入数据,如果无人读取会等待

out <- rand.Int()

}

}()

return out

}

funcmain() {

// 生成随机数作为一个服务

rand_service_handler :=rand_generator_2()

// 从服务中读取随机数并打印

fmt.Printf(“%d\n”,<-rand_service_handler)

}

上面的这段函数就可以并发执行了rand.Int()。有一点值得注意到函数的返回可以理解为一个“服务”。但我们需要获取随机数据时候,可以随时向这个服务取用,他已经为我们准备好了相应的数据,无需等待,随要随到。如果我们调用这个服务不是很频繁,一个协程足够满足我们的需求了。但如果我们需要大量访问,怎么办?我们可以用下面介绍的多路复用技术,启动若干生成器,再将其整合成一个大的服务。

调用生成器,可以返回一个“服务”。可以用在持续获取数据的场合。用途很广泛,读取数据,生成ID,甚至定时器。这是一种非常简洁的思路,将程序并发化。

多路复用

多路复用是让一次处理多个队列的技术。Apache使用处理每个连接都需要一个进程,所以其并发性能不是很好。而Nginx使用多路复用的技术,让一个进程处理多个连接,所以并发性能比较好。同样,在协程的场合,多路复用也是需要的,但又有所不同。多路复用可以将若干个相似的小服务整合成一个大服务。

 

Go语言并发之美

 

那么让我们用多路复用技术做一个更高并发的随机数生成器吧。

// 函数rand_generator_3 ,返回通道(Channel)

funcrand_generator_3() chan int {

// 创建两个随机数生成器服务

rand_generator_1 := rand_generator_2()

rand_generator_2 := rand_generator_2()

 

//创建通道

out := make(chan int)

 

//创建协程

go func() {

for {

//读取生成器1中的数据,整合

out <-<-rand_generator_1

}

}()

go func() {

for {

//读取生成器2中的数据,整合

out <-<-rand_generator_2

}

}()

return out

}        上面是使用了多路复用技术的高并发版的随机数生成器。通过整合两个随机数生成器,这个版本的能力是刚才的两倍。虽然协程可以大量创建,但是众多协程还是会争抢输出的通道。Go语言提供了Select关键字来解决,各家也有各家窍门。加大输出通道的缓冲大小是个通用的解决方法。

多路复用技术可以用来整合多个通道。提升性能和操作的便捷。配合其他的模式使用有很大的威力。

Future技术

Future是一个很有用的技术,我们常常使用Future来操作线程。我们可以在使用线程的时候,可以创建一个线程,返回Future,之后可以通过它等待结果。  但是在协程环境下的Future可以更加彻底,输入参数同样可以是Future的。

 

Go语言并发之美

 

调用一个函数的时候,往往是参数已经准备好了。调用协程的时候也同样如此。但是如果我们将传入的参数设为通道,这样我们就可以在不准备好参数的情况下调用函数。这样的设计可以提供很大的自由度和并发度。函数调用和函数参数准备这两个过程可以完全解耦。下面举一个用该技术访问数据库的例子。

//一个查询结构体

typequery struct {

//参数Channel

sql chan string

//结果Channel

result chan string

}

//执行Query

funcexecQuery(q query) {

//启动协程

go func() {

//获取输入

sql := <-q.sql

//访问数据库,输出结果通道

q.result <- “get” + sql

}()

}

funcmain() {

//初始化Query

q :=

query{make(chan string, 1),make(chan string, 1)}

//执行Query,注意执行的时候无需准备参数

execQuery(q)

 

//准备参数

q.sql <- “select * fromtable”

//获取结果

fmt.Println(<-q.result)

}

上面利用Future技术,不单让结果在Future获得,参数也是在Future获取。准备好参数后,自动执行。Future和生成器的区别在于,Future返回一个结果,而生成器可以重复调用。还有一个值得注意的地方,就是将参数Channel和结果Channel定义在一个结构体里面作为参数,而不是返回结果Channel。这样做可以增加聚合度,好处就是可以和多路复用技术结合起来使用。

Future技术可以和各个其他技术组合起来用。可以通过多路复用技术,监听多个结果Channel,当有结果后,自动返回。也可以和生成器组合使用,生成器不断生产数据,Future技术逐个处理数据。Future技术自身还可以首尾相连,形成一个并发的pipe filter。这个pipe filter可以用于读写数据流,操作数据流。

Future是一个非常强大的技术手段。可以在调用的时候不关心数据是否准备好,返回值是否计算好的问题。让程序中的组件在准备好数据的时候自动跑起来。

并发循环

循环往往是性能上的热点。如果性能瓶颈出现在CPU上的话,那么九成可能性热点是在一个循环体内部。所以如果能让循环体并发执行,那么性能就会提高很多。

 

Go语言并发之美

 

要并发循环很简单,只有在每个循环体内部启动协程。协程作为循环体可以并发执行。调用启动前设置一个计数器,每一个循环体执行完毕就在计数器上加一个元素,调用完成后通过监听计数器等待循环协程全部完成。

//建立计数器

sem :=make(chan int, N);

//FOR循环体

for i,xi:= range data {

//建立协程

go func (i int, xi float) {

doSomething(i,xi);

//计数

sem <- 0;

} (i, xi);

}

// 等待循环结束

for i := 0; i < N; ++i { <-sem }       上面是一个并发循环例子。通过计数器来等待循环全部完成。如果结合上面提到的Future技术的话,则不必等待。可以等到真正需要的结果的地方,再去检查数据是否完成。

通过并发循环可以提供性能,利用多核,解决CPU热点。正因为协程可以大量创建,才能在循环体中如此使用,如果是使用线程的话,就需要引入线程池之类的东西,防止创建过多线程,而协程则简单的多。

ChainFilter技术

前面提到了Future技术首尾相连,可以形成一个并发的pipe filter。这种方式可以做很多事情,如果每个Filter都由同一个函数组成,还可以有一种简单的办法把他们连起来。

 

Go语言并发之美

 

由于每个Filter协程都可以并发运行,这样的结构非常有利于多核环境。下面是一个例子,用这种模式来产生素数。

// Aconcurrent prime sieve

packagemain

 

// Sendthe sequence 2, 3, 4, … to channel ‘ch’.

funcGenerate(ch chan<- int) {

for i := 2; ; i++ {

ch<- i // Send ‘i’ to channel ‘ch’.

}

}

// Copythe values from channel ‘in’ to channel ‘out’,

//removing those divisible by ‘prime’.

funcFilter(in <-chan int, out chan<- int, prime int) {

for {

i := <-in // Receive valuefrom ‘in’.

if i%prime != 0 {

out <- i // Send’i’ to ‘out’.

}

}

}

// Theprime sieve: Daisy-chain Filter processes.

funcmain() {

ch := make(chan int) // Create a newchannel.

go Generate(ch)      // Launch Generate goroutine.

for i := 0; i < 10; i++ {

prime := <-ch

print(prime, “\n”)

ch1 := make(chan int)

go Filter(ch, ch1, prime)

ch = ch1

}

}

上面的程序创建了10个Filter,每个分别过滤一个素数,所以可以输出前10个素数。

Chain-Filter通过简单的代码创建并发的过滤器链。这种办法还有一个好处,就是每个通道只有两个协程会访问,就不会有激烈的竞争,性能会比较好。

共享变量

        协程之间的通信只能够通过通道。但是我们习惯于共享变量,而且很多时候使用共享变量能让代码更简洁。比如一个Server有两个状态开和关。其他仅仅希望获取或改变其状态,那又该如何做呢。可以将这个变量至于0通道中,并使用一个协程来维护。

 

Go语言并发之美


下面的例子描述如何用这个方式,实现一个共享变量。

//共享变量有一个读通道和一个写通道组成

typesharded_var struct {

reader chan int

writer chan int

}

//共享变量维护协程

funcsharded_var_whachdog(v sharded_var) {

go func() {

//初始值

var value int = 0

for {

//监听读写通道,完成服务

select {

case value =<-v.writer:

case v.reader <-value:

}

}

}()

}

funcmain() {

//初始化,并开始维护协程

v := sharded_var{make(chan int),make(chan int)}

sharded_var_whachdog(v)

//读取初始值

fmt.Println(<-v.reader)

//写入一个值

v.writer <- 1

//读取新写入的值

fmt.Println(<-v.reader)

}

这样,就可以在协程和通道的基础上实现一个协程安全的共享变量了。定义一个写通道,需要更新变量的时候,往里写新的值。再定义一个读通道,需要读的时候,从里面读。通过一个单独的协程来维护这两个通道。保证数据的一致性。

一般来说,协程之间不推荐使用共享变量来交互,但是按照这个办法,在一些场合,使用共享变量也是可取的。很多平台上有较为原生的共享变量支持,到底用那种实现比较好,就见仁见智了。另外利用协程和通道,可以还实现各种常见的并发数据结构,如锁等等,就不一一赘述。

协程泄漏

        协程和内存一样,是系统的资源。对于内存,有自动垃圾回收。但是对于协程,没有相应的回收机制。会不会若干年后,协程普及了,协程泄漏和内存泄漏一样成为程序员永远的痛呢?一般而言,协程执行结束后就会销毁。协程也会占用内存,如果发生协程泄漏,影响和内存泄漏一样严重。轻则拖慢程序,重则压垮机器。

C和C++都是没有自动内存回收的程序设计语言,但只要有良好的编程习惯,就能解决规避问题。对于协程是一样的,只要有好习惯就可以了。

只有两种情况会导致协程无法结束。一种情况是协程想从一个通道读数据,但无人往这个通道写入数据,或许这个通道已经被遗忘了。还有一种情况是程想往一个通道写数据,可是由于无人监听这个通道,该协程将永远无法向下执行。下面分别讨论如何避免这两种情况。

对于协程想从一个通道读数据,但无人往这个通道写入数据这种情况。解决的办法很简单,加入超时机制。对于有不确定会不会返回的情况,必须加入超时,避免出现永久等待。另外不一定要使用定时器才能终止协程。也可以对外暴露一个退出提醒通道。任何其他协程都可以通过该通道来提醒这个协程终止。

Go语言并发之美

        对于协程想往一个通道写数据,但通道阻塞无法写入这种情况。解决的办法也很简单,就是给通道加缓冲。但前提是这个通道只会接收到固定数目的写入。比方说,已知一个通道最多只会接收N次数据,那么就将这个通道的缓冲设置为N。那么该通道将永远不会堵塞,协程自然也不会泄漏。也可以将其缓冲设置为无限,不过这样就要承担内存泄漏的风险了。等协程执行完毕后,这部分通道内存将会失去引用,会被自动垃圾回收掉。

funcnever_leak(ch chan int) {

//初始化timeout,缓冲为1

timeout := make(chan bool, 1)

//启动timeout协程,由于缓存为1,不可能泄露

go func() {

time.Sleep(1 * time.Second)

timeout <- true

}()

//监听通道,由于设有超时,不可能泄露

select {

case <-ch:

// a read from ch hasoccurred

case <-timeout:

// the read from ch has timedout

}

}

上面是个避免泄漏例子。使用超时避免读堵塞,使用缓冲避免写堵塞。

和内存里面的对象一样,对于长期存在的协程,我们不用担心泄漏问题。一是长期存在,二是数量较少。要警惕的只有那些被临时创建的协程,这些协程数量大且生命周期短,往往是在循环中创建的,要应用前面提到的办法,避免泄漏发生。协程也是把双刃剑,如果出问题,不但没能提高程序性能,反而会让程序崩溃。但就像内存一样,同样有泄漏的风险,但越用越溜了。

并发模式之实现

        在并发编程大行其道的今天,对协程和通道的支持成为各个平台比不可少的一部分。虽然各家有各家的叫法,但都能满足协程的基本要求—并发执行和可大量创建。笔者对他们的实现方式总结了一下。

下面列举一些已经支持协程的常见的语言和平台。

Go语言并发之美

        GoLang 和Scala作为最新的语言,一出生就有完善的基于协程并发功能。Erlang最为老资格的并发编程语言,返老还童。其他二线语言则几乎全部在新的版本中加入了协程。

令人惊奇的是C/C++和Java这三个世界上最主流的平台没有在对协程提供语言级别的原生支持。他们都背负着厚重的历史,无法改变,也无需改变。但他们还有其他的办法使用协程。

Java平台有很多方法实现协程:

· 修改虚拟机:对JVM打补丁来实现协程,这样的实现效果好,但是失去了跨平台的好处

· 修改字节码:在编译完成后增强字节码,或者使用新的JVM语言。稍稍增加了编译的难度。

· 使用JNI:在Jar包中使用JNI,这样易于使用,但是不能跨平台。

· 使用线程模拟协程:使协程重量级,完全依赖JVM的线程实现。

其中修改字节码的方式比较常见。因为这样的实现办法,可以平衡性能和移植性。最具代表性的JVM语言Scale就能很好的支持协程并发。流行的Java Actor模型类库akka也是用修改字节码的方式实现的协程。

对于C语言,协程和线程一样。可以使用各种各样的系统调用来实现。协程作为一个比较高级的概念,实现方式实在太多,就不讨论了。比较主流的实现有libpcl, coro,lthread等等。

对于C++,有Boost实现,还有一些其他开源库。还有一门名为μC++语言,在C++基础上提供了并发扩展。

可见这种编程模型在众多的语言平台中已经得到了广泛的支持,不再小众。如果想使用的话,随时可以加到自己的工具箱中。

结语 
        本文探讨了一个极其简洁的并发模型。在只有协程和通道这两个基本元件的情况下。可以提供丰富的功能,解决形形色色实际问题。而且这个模型已经被广泛的实现,成为潮流。相信这种并发模型的功能远远不及此,一定也会有更多更简洁的用法出现。或许未来CPU核心数目将和人脑神经元数目一样多,到那个时候,我们又要重新思考并发模型了。

 | 69 views | 0 comments | 0 flags | 

【转】SOC时钟系统驱动分析

http://heljoy.github.io/linux/2013/01/11/introduce-soc-clock-driver/ 【内容复制时不完整,最好看原文】

本文主要介绍SOC片上时钟系统,对应到SPEC文档时钟部分,并不涉及系统的计时、定时等,这部分内容可参考这篇文章。本文所提到的时钟是SOC片上设备工作的时钟,主要介绍时钟相关概念、硬件、核心时钟系统的结构与驱动、部分动态调频的原理。

时钟是设备工作的脉搏,系统各部件正常的工作离不开合适的时钟。嵌入式平台上为降低系统功耗,部分模块的工作电压与时钟都是可以动态调整,并且可单独关闭某一模块的时钟以节省电源,为屏蔽时钟调整寄存器操作细节,方便时钟状态调整,统一访问接口,三星独立与LINUX时钟驱动,开发了平台相关的驱动程序,这里针对EXYNOS4412平台时钟系统,涉及到驱动框架和实现细节。

时钟相关硬件

时钟是一种有规律的电信号,具有特定的周期、频率,最常见的时钟信号的方波、正弦波等,这个是硬件晶振具有的特性。而系统中各模块工作于不同频率,为每个模块单独配置一个晶振显然不现实,并且有些模块可工作在多种频率模式,因此嵌入式时钟系统常具有动态调整频率功能,具体来说就是多路选择和分频,其时钟系统与树结构类似,拥有一个或几个时钟源,经过PLL电路,使用MUX、DIV器件为各模块提供多种工作频率。

  • PLL:锁相环电路,百度百科上有详细的解释,具体就是有反馈机制的电路,可调整部分参数达到输入与输出动态变化的目的,在SPEC文档上有调整PLL相关的寄存器说明,其中最重要的参数为PMS,确定输出频率与输入频率的关系,并有参数的推荐配置。
  • MUX:多路选择电路,从上行多路时钟选择一路输出,必须有一路输出,不能不选,也是通过寄存器配置。另外MUX分为glitch-free和normal两种,只在时钟切换时有区别。
  • DIV:分频电路,将上行时钟分频处理后输出, 分频参数为整数,所以经过电路的时钟频率为几个离散值
  • GATE:开关电路,截断上行时钟到下行设备的输出,一般针对终端设备,不要关闭下行有多个时钟或设备的时钟

片上设备时钟

一般SOC芯片都需要外部提供一个或几个稳定频率的时钟源,时钟源经过片上时钟管理系统最后提供给片上的设备,这部分的硬件连接图一般没有,但SPEC文档会介绍时钟管理系统对时钟源的处理,片上设备连接到哪个时钟域下(一般不会详细列出每个设备的时钟路线,只会给出哪些设备属于哪个时钟管理),以下给出大概的时钟路线图。

     other clock ----------+                              +----> {GATE} DEVICE0
     other clock --------+ |                              |----> {GATE} DEVICE1
                         V V                              |----> {GATE} DEVICE2
clock_src ------>[PLL] ------->[MUX] ------->[DIV] ------------> {GATE} DEVICE3

时钟源clock_src之后到DEVICE之前都属于时钟管理系统,从时钟源到设备通常会经过多个MUX、DIV器件,具体要结合SPEC文档时钟管理器部分寄存器描述。弄清楚上述关系后就可以直接访问寄存器控制时钟系统,适用于没有操作系统的环境,但linux系统屏蔽了这些硬件细节,为上层驱动提供统一的访问接口,下面具体描述统一接口到寄存器操作的映射关系,这也是时钟驱动框架的核心部分。

系统中时钟的表示

时钟驱动中关键要表达以下几个概念:时钟、时钟源、设置/获取频率等操作。

## arch/arm/plat-samsung/include/plat/clock.h struct clk { struct list_head list; //用这个链接到系统全局时钟链表 struct module *owner; //时钟也是系统中的设备 struct clk *parent; //指向父时钟,用于时钟操作等 const char *name; const char *devname; int id; int usage; //使用计数 unsigned long rate; //频率 unsigned long ctrlbit; //寄存器中第几位用于操作时钟 struct clk_ops *ops; //操作接口,set/get等 int (*enable)(struct clk *, int enable); //使能接口,配合usage使用 struct clk_lookup lookup; //Linux驱动中用于时钟索引相关,暂时没有关注 #if defined(CONFIG_PM_DEBUG) && defined(CONFIG_DEBUG_FS) struct dentry *dent; /* For visible tree hierarchy */ #endif }; 

看了这个结构心里还不会太紧张,成员不多,且大分部类型确定,起作用的也只有几个,唯一一个不明白的就是clk_ops了。

## arch/arm/plat-samsung/include/plat/clock.h struct clk_ops { int (*set_rate)(struct clk *c, unsigned long rate); //设置频率 unsigned long (*get_rate)(struct clk *c); //获取频率 unsigned long (*round_rate)(struct clk *c, unsigned long rate);//获取与给定频率最接近的支持频率 int (*set_parent)(struct clk *c, struct clk *parent);//设置父时钟 struct clk * (*get_parent)(struct clk *c); //获取父时钟 }; 

这个结构也没有我们想像的复杂,需要解释的是时钟是由MUX、DIV等出来的,并不是你设置一个频率,时钟就能以这个频率工作,通过设置MUX、DIV,时钟有一个离散工作频率范围。MUX是多选一的选择器,每个上行时钟都可能成为下行时钟的父时钟,下行时钟与父时钟的频率一致,对于DIV分频器,下行时钟只有一个父时钟,下行时钟与父时钟频率关系由分频器控制。

## arch/arm/plat-samsung/include/plat/clock-clksrc.h struct clksrc_clk { struct clk clk; //也是一个时钟,这个成员还是要的 struct clksrc_sources *sources; //时钟列表 struct clksrc_reg reg_src; //寄存器 struct clksrc_reg reg_src_stat; //寄存器 struct clksrc_reg reg_div; //寄存器 }; struct clksrc_sources { unsigned int nr_sources; struct clk **sources; }; struct clksrc_reg { void __iomem *reg; unsigned short shift; unsigned short size; }; 

时钟源的表示,用来描述MUX、DIV器件这类连接有多个时钟,通过寄存器位控制上下行时钟关系。MUX的sources一般包含多个时钟,寄存器reg_src表示设置哪个为父时钟的寄存器位,DIV不用设置sources,使用reg_div设置分频参数。这里寄存器信息只给出了基地址,偏移量和位宽,位段内包含的信息由SPEC文档解释,一般所有MUX的格式统一,所有DIV的格式也统一,故可以使用上面的抽象。

时钟注册接口

这里分两类注册,一种时钟就是单个模块使用,有些可以关闭,且关闭了不会影响其它模块工作;另一类就是生成上面一类时钟的时钟,由选择器、分频器组成,可以说是生成第一种时钟的时钟,为时钟源,对应到上节中的两个结构。

## arch/arm/plat-samsung/clock.c int s3c24xx_register_clock(struct clk *clk) { if (clk->enable == NULL) clk->enable = clk_null_enable; /* add to the list of available clocks */ /* Quick check to see if this clock has already been registered. */ BUG_ON(clk->list.prev != clk->list.next); spin_lock(&clocks_lock); list_add(&clk->list, &clocks); //添加到全局时钟链表 spin_unlock(&clocks_lock); /* fill up the clk_lookup structure and register it*/ clk->lookup.dev_id = clk->devname; clk->lookup.con_id = clk->name; clk->lookup.clk = clk; clkdev_add(&clk->lookup); //与时钟查找相关 return 0; } 

注册时钟的接口比较简单,把时钟添加到全局时钟链表就可以了,与gpio驱动中gpio_desc数组有类似的作用,相比第二类时钟要复杂一些。

void __init s3c_register_clksrc(struct clksrc_clk *clksrc, int size) { int ret; for (; size > 0; size--, clksrc++) { if (!clksrc->reg_div.reg && !clksrc->reg_src.reg) printk(KERN_ERR "%s: clock %s has no registers set\n", __func__, clksrc->clk.name); /* fill in the default functions */ if (!clksrc->clk.ops) { //选择器、分频器操作寄存器接口 if (!clksrc->reg_div.reg) clksrc->clk.ops = &clksrc_ops_nodiv; else if (!clksrc->reg_src.reg) clksrc->clk.ops = &clksrc_ops_nosrc; else clksrc->clk.ops = &clksrc_ops; } /* setup the clocksource, but do not announce it * as it may be re-set by the setup routines * called after the rest of the clocks have been * registered */ s3c_set_clksrc(clksrc, false); //初始化时钟源 ret = s3c24xx_register_clock(&clksrc->clk); //将时钟源的时钟注册进系统 if (ret < 0) { printk(KERN_ERR "%s: failed to register %s (%d)\n", __func__, clksrc->clk.name, ret); } } } 

注册时钟源要有选择或分频寄存器地址,也就是这个时钟源是可配置的,接口配置时钟源时主要是根据clk_reg设置寄存器,后面应用时再具体介绍。时钟源添加到系统时会进行初始化,这里涉及到寄存器操作。

void __init_or_cpufreq s3c_set_clksrc(struct clksrc_clk *clk, bool announce) { struct clksrc_sources *srcs = clk->sources; u32 mask = bit_mask(clk->reg_src.shift, clk->reg_src.size); u32 clksrc; if (!clk->reg_src.reg) { if (!clk->clk.parent) printk(KERN_ERR "%s: no parent clock specified\n", clk->clk.name); return; } clksrc = __raw_readl(clk->reg_src.reg); //选择器开关状态 clksrc &= mask; clksrc >>= clk->reg_src.shift; if (clksrc > srcs->nr_sources || !srcs->sources[clksrc]) { printk(KERN_ERR "%s: bad source %d\n", clk->clk.name, clksrc); return; } clk->clk.parent = srcs->sources[clksrc]; //设置当前时钟的父结点 if (announce) printk(KERN_INFO "%s: source is %s (%d), rate is %ld\n", clk->clk.name, clk->clk.parent->name, clksrc, clk_get_rate(&clk->clk)); } 

初始化主要是设置时钟的父结点,利用选择器寄存器reg_src,从父结点列表中获取当前为选择器提供时钟的父结点,分频率只有一个父结点。

时钟驱动框架结构

EXYNOS4412平台所有的时钟都从以下几个时钟派生:

  • XRTCXTI:实时钟输入,32.768KHZ,用于实时钟模块
  • XXTI:不知道做什么用的,我们没有使用这个
  • XUSBXTI:USB PHY模块使用,同时也用于系统PLL,24MHZ

主要是使用到了XUSBXTI作为时钟来源,为保证系统工作频率稳定,XUSBXTI分别输入到不同的PLL电路,经常见到的有APLL、EPLL、MPLL、VPLL,其主要针对SOC四大部分,XUSBXTI与PLL经过MUX产生SCLK_XPLL,其中APLL要分频输出SCLK_APLL,具体派生结构如下:

                              |\               +-----------+
xusbxit--+------------------->| | MUX(APLL)    |           |
         |   +--------+       | |------------->| DIV(APLL) |----------->SCLK_APLL
         +-->|  APLL  |------>| |              |           |
         |   +--------+       |/               +-----------+
         |   
         |
         |                    |\
         +------------------->| |  MUX(xPLL)            
         |   +------------+   | |-------------> SCLK_xPLL
         +-->| PLL(E,M,V) |-->| |              
             +------------+   | |
                              |/

上述5个时钟输入源,分别是xusbxit、apll_fout、epll_fout、mpll_fout、vpll_fout,根据上图建立驱动使用的模型:

## arch/arm/plat-s5p/clock.c /* Possible clock sources for APLL Mux */ static struct clk *clk_src_apll_list[] = { [0] = &clk_fin_apll, //输入APLL前的时钟,也就是xusbxit [1] = &clk_fout_apll, //从APLL输出的时钟 }; struct clksrc_sources clk_src_apll = { .sources = clk_src_apll_list, .nr_sources = ARRAY_SIZE(clk_src_apll_list), }; ## arch/arm/mach-exynos/clock-exynos4.c static struct clksrc_clk exynos4_clk_mout_apll = { //这个描述APLL后面的MUX .clk = { .name = "mout_apll", }, .sources = &clk_src_apll, //这个MUX的源时钟列表 .reg_src = { .reg = EXYNOS4_CLKSRC_CPU, .shift = 0, .size = 1 }, //用于控制MUX寄存器位 }; static struct clksrc_clk exynos4_clk_sclk_apll = { //这个描述MUX后面的DIV .clk = { .name = "sclk_apll", .parent = &exynos4_clk_mout_apll.clk, //这个的父结点就是MUX出来的时钟 }, .reg_div = { .reg = EXYNOS4_CLKDIV_CPU, .shift = 24, .size = 3 }, //用于设置分频器寄存器位 }; ## arch/arm/plat-s5p/clock.c /* Possible clock sources for EPLL Mux */ static struct clk *clk_src_epll_list[] = { [0] = &clk_fin_epll, [1] = &clk_fout_epll, }; struct clksrc_sources clk_src_epll = { .sources = clk_src_epll_list, .nr_sources = ARRAY_SIZE(clk_src_epll_list), }; ## arch/arm/mach-exynos/clock-exynos4.c static struct clksrc_clk exynos4_clk_mout_epll = { .clk = { .name = "mout_epll", }, .sources = &clk_src_epll, .reg_src = { .reg = EXYNOS4_CLKSRC_TOP0, .shift = 4, .size = 1 }, }; ... 

上面给出了建立sclk_apll和sclk_epll(mout_epll)时钟模型,其余PLL时钟模型相似。SOC上很多设备使用的时钟都是这几个PLL派生来,结合芯片datasheet,从代码中能清楚看到这种派生关系。

4. 时钟驱动接口实现

对时钟的操作首先都要获取时钟,由get_clk实现,由linux系统clk驱动完成,使用lookup成员,细节不作介绍。获取时钟后就可设置时钟频率或关闭时钟了。

## drivers/clk/clk.c unsigned long clk_get_rate(struct clk *clk) { unsigned long rate; mutex_lock(&prepare_lock); rate = __clk_get_rate(clk); mutex_unlock(&prepare_lock); return rate; } unsigned long __clk_get_rate(struct clk *clk) { unsigned long ret; if (!clk) { ret = -EINVAL; goto out; } ret = clk->rate; if (clk->flags & CLK_IS_ROOT) goto out; if (!clk->parent) ret = -ENODEV; out: return ret; } 

获取时钟频率比较简单,在clk结构中有保存时钟频率。设置频率的接口要复杂得多,如果操作的为DIV,根据父时钟频率调整分频参数,找出一个与目标频率最接近的分频参数即可,如果操作的是MUX,可选的频率集合为父时钟频率集合,查找最接近即可。

## arch/arm/plat-samsung/clock.c int clk_set_rate(struct clk *clk, unsigned long rate) { int ret; unsigned long flags; if (IS_ERR(clk)) return -EINVAL; /* We do not default just do a clk->rate = rate as * the clock may have been made this way by choice. */ WARN_ON(clk->ops == NULL); WARN_ON(clk->ops && clk->ops->set_rate == NULL); if (clk->ops == NULL || clk->ops->set_rate == NULL) return -EINVAL; spin_lock_irqsave(&clocks_lock, flags); trace_clock_set_rate(clk->name, rate, smp_processor_id()); //trace相关,不用关心 ret = (clk->ops->set_rate)(clk, rate); //接口调用 spin_unlock_irqrestore(&clocks_lock, flags); return ret; } 

这里就是调用clk设备的操作接口,第一节介绍注册时赋值。(DIV器件才有改变频率接口,MUX器件才有改变父结点接口,clk设备只有使能接口),时钟操作接口,结合时钟源的定义可关联到具体接口。

static struct clk_ops clksrc_ops = { .set_parent = s3c_setparent_clksrc, .get_parent = s3c_getparent_clksrc, .get_rate = s3c_getrate_clksrc, .set_rate = s3c_setrate_clksrc, .round_rate = s3c_roundrate_clksrc, }; static struct clk_ops clksrc_ops_nodiv = { .set_parent = s3c_setparent_clksrc, .get_parent = s3c_getparent_clksrc, }; static struct clk_ops clksrc_ops_nosrc = { .get_rate = s3c_getrate_clksrc, .set_rate = s3c_setrate_clksrc, .round_rate = s3c_roundrate_clksrc, }; 

改变时钟的频率clk_set_rate接口会调用到s3c_setrate_clksrc。

static int s3c_setrate_clksrc(struct clk *clk, unsigned long rate) { struct clksrc_clk *sclk = to_clksrc(clk); struct clk *parent; void __iomem *reg = sclk->reg_div.reg; unsigned int div; u32 mask = bit_mask(sclk->reg_div.shift, sclk->reg_div.size); u32 val; parent = __clk_get_parent(clk); //获取父结点 rate = clk_round_rate(clk, rate); div = clk_get_rate(parent) / rate; //目标频率与当前父结点频率计算分频参数 if (div > (1 << sclk->reg_div.size)) return -EINVAL; val = __raw_readl(reg); val &= ~mask; val |= (div - 1) << sclk->reg_div.shift; __raw_writel(val, reg); //修改reg_div[shift~shift+size],定义时钟源时设置 return 0; } 

其余接口不再介绍,利用上面的方法,分析datasheet文档,核对移植过程中是否存在问题。

总结

这样基础性质的驱动是系统能正常工作的保证,修改时需要认真核对SPEC文档,在移植前并不是所有的时钟都已经正确,最好是代码与文档对照来看,去掉没有的时钟,添加必须使用的时钟。有时候很多时钟的寄存器从来不会被改动,可以不用添加到系统,但为框架树形结构完整以及查找问题方便,还是建议统一都写上,从clock_tree能完整的掌握系统运行状态。

 | 74 views | 0 comments | 1 flags | 

【转】Learn haskell in Y Minutes

Learn X in Y minutes

http://learnxinyminutes.com/docs/zh-cn/haskell-cn/

Where X=haskell

Get the code: learn-haskell-zh.hs

Haskell 被设计成一种实用的纯函数式编程语言。它因为 monads 及其类型系统而出名,但是我回归到它本身因为。Haskell 使得编程对于我而言是一种真正的快乐。

-- 单行注释以两个破折号开头
{- 多行注释像这样
   被一个闭合的块包围
-}

----------------------------------------------------
-- 1. 简单的数据类型和操作符
----------------------------------------------------

-- 你有数字
3 -- 3
-- 数学计算就像你所期待的那样
1 + 1 -- 2
8 - 1 -- 7
10 * 2 -- 20
35 / 5 -- 7.0

-- 默认除法不是整除
35 / 4 -- 8.75

-- 整除
35 `div` 4 -- 8

-- 布尔值也简单
True
False

-- 布尔操作
not True -- False
not False -- True
1 == 1 -- True
1 /= 1 -- False
1 < 10 -- True

-- 在上述的例子中,`not` 是一个接受一个值的函数。
-- Haskell 不需要括号来调用函数。。。所有的参数
-- 都只是在函数名之后列出来。因此,通常的函数调用模式是:
-- func arg1 arg2 arg3...
-- 查看关于函数的章节以获得如何写你自己的函数的相关信息。

-- 字符串和字符
"This is a string."
'a' -- 字符
'对于字符串你不能使用单引号。' -- 错误!

-- 连结字符串
"Hello " ++ "world!" -- "Hello world!"

-- 一个字符串是一系列字符
"This is a string" !! 0 -- 'T'

----------------------------------------------------
-- 列表和元组
----------------------------------------------------

-- 一个列表中的每一个元素都必须是相同的类型
-- 下面两个列表一样
[1, 2, 3, 4, 5]
[1..5]

-- 在 Haskell 你可以拥有含有无限元素的列表
[1..] -- 一个含有所有自然数的列表

-- 因为 Haskell 有“懒惰计算”,所以无限元素的列表可以正常运作。这意味着
-- Haskell 可以只在它需要的时候计算。所以你可以请求
-- 列表中的第1000个元素,Haskell 会返回给你

[1..] !! 999 -- 1000

-- Haskell 计算了列表中 1 - 1000 个元素。。。但是
-- 这个无限元素的列表中剩下的元素还不存在! Haskell 不会
-- 真正地计算它们知道它需要。

<FS>- 连接两个列表
[1..5] ++ [6..10]

-- 往列表头增加元素
0:[1..5] -- [0, 1, 2, 3, 4, 5]

-- 列表中的下标
[0..] !! 5 -- 5

-- 更多列表操作
head [1..5] -- 1
tail [1..5] -- [2, 3, 4, 5]
init [1..5] -- [1, 2, 3, 4]
last [1..5] -- 5

-- 列表推导
[x*2 | x <- [1..5]] -- [2, 4, 6, 8, 10]

-- 附带条件
[x*2 | x <-[1..5], x*2 > 4] -- [6, 8, 10]

-- 元组中的每一个元素可以是不同类型的,但是一个元组
-- 的长度是固定的
-- 一个元组
("haskell", 1)

-- 获取元组中的元素
fst ("haskell", 1) -- "haskell"
snd ("haskell", 1) -- 1

----------------------------------------------------
-- 3. 函数
----------------------------------------------------
-- 一个接受两个变量的简单函数
add a b = a + b

-- 注意,如果你使用 ghci (Hakell 解释器)
-- 你将需要使用 `let`,也就是
-- let add a b = a + b

-- 使用函数
add 1 2 -- 3

-- 你也可以把函数放置在两个参数之间
-- 附带倒引号:
1 `add` 2 -- 3

-- 你也可以定义不带字符的函数!这使得
-- 你定义自己的操作符!这里有一个操作符
-- 来做整除
(//) a b = a `div` b
35 // 4 -- 8

-- 守卫:一个简单的方法在函数里做分支
fib x
  | x < 2 = x
  | otherwise = fib (x - 1) + fib (x - 2)

-- 模式匹配是类型的。这里有三种不同的 fib 
-- 定义。Haskell 将自动调用第一个
-- 匹配值的模式的函数。
fib 1 = 1
fib 2 = 2
fib x = fib (x - 1) + fib (x - 2)

-- 元组的模式匹配:
foo (x, y) = (x + 1, y + 2)

-- 列表的模式匹配。这里 `x` 是列表中第一个元素,
-- 并且 `xs` 是列表剩余的部分。我们可以写
-- 自己的 map 函数:
myMap func [] = []
myMap func (x:xs) = func x:(myMap func xs)

-- 编写出来的匿名函数带有一个反斜杠,后面跟着
-- 所有的参数。
myMap (\x -> x + 2) [1..5] -- [3, 4, 5, 6, 7]

-- 使用 fold (在一些语言称为`inject`)随着一个匿名的
-- 函数。foldl1 意味着左折叠(fold left), 并且使用列表中第一个值
-- 作为累加器的初始化值。
foldl1 (\acc x -> acc + x) [1..5] -- 15

----------------------------------------------------
-- 4. 更多的函数
----------------------------------------------------

-- 柯里化(currying):如果你不传递函数中所有的参数,
-- 它就变成“柯里化的”。这意味着,它返回一个接受剩余参数的函数。

add a b = a + b
foo = add 10 -- foo 现在是一个接受一个数并对其加 10 的函数
foo 5 -- 15

-- 另外一种方式去做同样的事
foo = (+10)
foo 5 -- 15

-- 函数组合
-- (.) 函数把其它函数链接到一起
-- 举个列子,这里 foo 是一个接受一个值的函数。它对接受的值加 10,
-- 并对结果乘以 5,之后返回最后的值。
foo = (*5) . (+10)

-- (5 + 10) * 5 = 75
foo 5 -- 75

-- 修复优先级
-- Haskell 有另外一个函数称为 `$`。它改变优先级
-- 使得其左侧的每一个操作先计算然后应用到
-- 右侧的每一个操作。你可以使用 `.` 和 `$` 来除去很多
-- 括号:

-- before
(even (fib 7)) -- true

-- after
even . fib $ 7 -- true

----------------------------------------------------
-- 5. 类型签名
----------------------------------------------------

-- Haskell 有一个非常强壮的类型系统,一切都有一个类型签名。

-- 一些基本的类型:
5 :: Integer
"hello" :: String
True :: Bool

-- 函数也有类型。
-- `not` 接受一个布尔型返回一个布尔型:
-- not :: Bool -> Bool

-- 这是接受两个参数的函数:
-- add :: Integer -> Integer -> Integer

-- 当你定义一个值,在其上写明它的类型是一个好实践:
double :: Integer -> Integer
double x = x * 2

----------------------------------------------------
-- 6. 控制流和 If 语句
----------------------------------------------------

-- if 语句
haskell = if 1 == 1 then "awesome" else "awful" -- haskell = "awesome"

-- if 语句也可以有多行,缩进是很重要的
haskell = if 1 == 1
            then "awesome"
            else "awful"

-- case 语句:这里是你可以怎样去解析命令行参数
case args of
  "help" -> printHelp
  "start" -> startProgram
  _ -> putStrLn "bad args"

-- Haskell 没有循环因为它使用递归取代之。
-- map 应用一个函数到一个数组中的每一个元素

map (*2) [1..5] -- [2, 4, 6, 8, 10]

-- 你可以使用 map 来编写 for 函数
for array func = map func array

-- 然后使用它
for [0..5] $ \i -> show i

-- 我们也可以像这样写:
for [0..5] show

-- 你可以使用 foldl 或者 foldr 来分解列表
-- foldl <fn> <initial value> <list>
foldl (\x y -> 2*x + y) 4 [1,2,3] -- 43

-- 这和下面是一样的
(2 * (2 * (2 * 4 + 1) + 2) + 3)

-- foldl 是左手边的,foldr 是右手边的-
foldr (\x y -> 2*x + y) 4 [1,2,3] -- 16

-- 这和下面是一样的
(2 * 3 + (2 * 2 + (2 * 1 + 4)))

----------------------------------------------------
-- 7. 数据类型
----------------------------------------------------

-- 这里展示在 Haskell 中你怎样编写自己的数据类型

data Color = Red | Blue | Green

-- 现在你可以在函数中使用它:

say :: Color -> String
say Red = "You are Red!"
say Blue = "You are Blue!"
say Green =  "You are Green!"

-- 你的数据类型也可以有参数:

data Maybe a = Nothing | Just a

-- 类型 Maybe 的所有
Just "hello"    -- of type `Maybe String`
Just 1          -- of type `Maybe Int`
Nothing         -- of type `Maybe a` for any `a`

----------------------------------------------------
-- 8. Haskell IO
----------------------------------------------------

-- 虽然在没有解释 monads 的情况下 IO不能被完全地解释,
-- 着手解释到位并不难。

-- 当一个 Haskell 程序被执行,函数 `main` 就被调用。
-- 它必须返回一个类型 `IO ()` 的值。举个列子:

main :: IO ()
main = putStrLn $ "Hello, sky! " ++ (say Blue) 
-- putStrLn has type String -> IO ()

-- 如果你能实现你的程序依照函数从 String 到 String,那样编写 IO 是最简单的。
-- 函数
--    interact :: (String -> String) -> IO ()
-- 输入一些文本,在其上运行一个函数,并打印出输出

countLines :: String -> String
countLines = show . length . lines

main' = interact countLines

-- 你可以考虑一个 `IO()` 类型的值,当做一系列计算机所完成的动作的代表,
-- 就像一个以命令式语言编写的计算机程序。我们可以使用 `do` 符号来把动作链接到一起。
-- 举个列子:

sayHello :: IO ()
sayHello = do 
   putStrLn "What is your name?"
   name <- getLine -- this gets a line and gives it the name "input"
   putStrLn $ "Hello, " ++ name

-- 练习:编写只读取一行输入的 `interact`

-- 然而,`sayHello` 中的代码将不会被执行。唯一被执行的动作是 `main` 的值。
-- 为了运行 `sayHello`,注释上面 `main` 的定义,并代替它:
--   main = sayHello

-- 让我们来更好地理解刚才所使用的函数 `getLine` 是怎样工作的。它的类型是:
--    getLine :: IO String
-- 你可以考虑一个 `IO a` 类型的值,代表一个当被执行的时候
-- 将产生一个 `a` 类型的值的计算机程序(除了它所做的任何事之外)。我们可以保存和重用这个值通过 `<-`。
-- 我们也可以写自己的 `IO String` 类型的动作:

action :: IO String
action = do
   putStrLn "This is a line. Duh"
   input1 <- getLine 
   input2 <- getLine
   -- The type of the `do` statement is that of its last line.
   -- `return` is not a keyword, but merely a function 
   return (input1 ++ "\n" ++ input2) -- return :: String -> IO String

-- 我们可以使用这个动作就像我们使用 `getLine`:

main'' = do
    putStrLn "I will echo two lines!"
    result <- action 
    putStrLn result
    putStrLn "This was all, folks!"

-- `IO` 类型是一个 "monad" 的例子。Haskell 使用一个 monad 来做 IO的方式允许它是一门纯函数式语言。
-- 任何与外界交互的函数(也就是 IO) 都在它的类型签名处做一个 `IO` 标志
-- 着让我们推出 什么样的函数是“纯洁的”(不与外界交互,不修改状态) 和 什么样的函数不是 “纯洁的”

-- 这是一个强有力的特征,因为并发地运行纯函数是简单的;因此,Haskell 中并发是非常简单的。

----------------------------------------------------
-- 9. The Haskell REPL
----------------------------------------------------

-- 键入 `ghci` 开始 repl。
-- 现在你可以键入 Haskell 代码。
-- 任何新值都需要通过 `let` 来创建:

let foo = 5

-- 你可以查看任何值的类型,通过命令 `:t`:

>:t foo
foo :: Integer

-- 你也可以运行任何 `IO ()`类型的动作

> sayHello
What is your name?
Friend!
Hello, Friend!

还有很多关于 Haskell,包括类型类和 monads。这些是使得编码 Haskell 是如此有趣的主意。我用一个最后的 Haskell 例子来结束:一个 Haskell 的快排实现:

qsort [] = []
qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
    where lesser  = filter (< p) xs
          greater = filter (>= p) xs

安装 Haskell 是简单的。你可以从这里获得它。

你可以从优秀的 Learn you a Haskell 或者 Real World Haskell 找到优雅不少的入门介绍。

 | 89 views | 0 comments | 0 flags | 

【转】Linux下的lds链接脚本基础

http://linux.chinaunix.net/techdoc/beginner/2009/08/12/1129972.shtml

今天在看uboot引导Linux部分,发现要对链接脚本深入了解,才能知道各个目标文件的内存分布映像,下面是我看到的一些资料
0. Contents
1. 概论
2. 基本概念
3. 脚本格式
4. 简单例子
5. 简单脚本命令
6. 对符号的赋值
7. SECTIONS命令
8. MEMORY命令
9. PHDRS命令
10. VERSION命令
11. 脚本内的表达式
12. 暗含的连接脚本
1. 概论
每一个链接过程都由链接脚本(linker script, 一般以lds作为文件的后缀名)控制. 链接脚本主要用于规定如何把输入文件内的section放入输出文件内, 并控制输出文件内各部分在程序地址空间内的布局. 但你也可以用连接命令做一些其他事情.
连接器有个默认的内置连接脚本, 可用ld –verbose查看. 连接选项-r和-N可以影响默认的连接脚本(如何影响?).
-T选项用以指定自己的链接脚本, 它将代替默认的连接脚本。你也可以使用以增加自定义的链接命令.
以下没有特殊说明,连接器指的是静态连接器.
2. 基本概念
链接器把一个或多个输入文件合成一个输出文件.
输入文件: 目标文件或链接脚本文件.
输出文件: 目标文件或可执行文件.
目标文件(包括可执行文件)具有固定的格式, 在UNIX或GNU/Linux平台下, 一般为ELF格式. 若想了解更多, 可参考 UNIX/Linux平台可执行文件格式分析
有时把输入文件内的section称为输入section(input section), 把输出文件内的section称为输出section(output sectin).
目标文件的每个section至少包含两个信息: 名字和大小. 大部分section还包含与它相关联的一块数据, 称为section contents(section内容). 一个section可被标记为“loadable(可加载的)”或“allocatable(可分配的)”.
loadable section: 在输出文件运行时, 相应的section内容将被载入进程地址空间中.
allocatable section: 内容为空的section可被标记为“可分配的”. 在输出文件运行时, 在进程地址空间中空出大小同section指定大小的部分. 某些情况下, 这块内存必须被置零.
如果一个section不是“可加载的”或“可分配的”, 那么该section通常包含了调试信息. 可用objdump -h命令查看相关信息.
每个“可加载的”或“可分配的”输出section通常包含两个地址: VMA(virtual memory address虚拟内存地址或程序地址空间地址)和LMA(load memory address加载内存地址或进程地址空间地址). 通常VMA和LMA是相同的.
在目标文件中, loadable或allocatable的输出section有两种地址: VMA(virtual Memory Address)和LMA(Load Memory Address). VMA是执行输出文件时section所在的地址, 而LMA是加载输出文件时section所在的地址. 一般而言, 某section的VMA == LMA. 但在嵌入式系统中, 经常存在加载地址和执行地址不同的情况: 比如将输出文件加载到开发板的flash中(由LMA指定), 而在运行时将位于flash中的输出文件复制到SDRAM中(由VMA指定).
可这样来理解VMA和LMA, 假设:
(1) .data section对应的VMA地址是0×08050000, 该section内包含了3个32位全局变量, i、j和k, 分别为1,2,3.
(2) .text section内包含由”printf( “j=%d “, j );”程序片段产生的代码.
连接时指定.data section的VMA为0×08050000, 产生的printf指令是将地址为0×08050004处的4字节内容作为一个整数打印出来。
如果.data section的LMA为0×08050000,显然结果是j=2
如果.data section的LMA为0×08050004,显然结果是j=1
还可这样理解LMA:
.text section内容的开始处包含如下两条指令(intel i386指令是10字节,每行对应5字节):
jmp 0×08048285
movl $0×1,%eax
如果.text section的LMA为0×08048280, 那么在进程地址空间内0×08048280处为“jmp 0×08048285”指令, 0×08048285处为movl $0×1,%eax指令. 假设某指令跳转到地址0×08048280, 显然它的执行将导致%eax寄存器被赋值为1.
如果.text section的LMA为0×08048285, 那么在进程地址空间内0×08048285处为“jmp 0×08048285”指令, 0×0804828a处为movl $0×1,%eax指令. 假设某指令跳转到地址0×08048285, 显然它的执行又跳转到进程地址空间内0×08048285处, 造成死循环.
符号(symbol): 每个目标文件都有符号表(SYMBOL TABLE), 包含已定义的符号(对应全局变量和static变量和定义的函数的名字)和未定义符号(未定义的函数的名字和引用但没定义的符号)信息.
符号值: 每个符号对应一个地址, 即符号值(这与c程序内变量的值不一样, 某种情况下可以把它看成变量的地址). 可用nm命令查看它们. (nm的使用方法可参考本blog的GNU binutils笔记)
3. 脚本格式
链接脚本由一系列命令组成, 每个命令由一个关键字(一般在其后紧跟相关参数)或一条对符号的赋值语句组成. 命令由分号‘;’分隔开.
文件名或格式名内如果包含分号’;’或其他分隔符, 则要用引号‘”’将名字全称引用起来. 无法处理含引号的文件名.
/* */之间的是注释。
4. 简单例子
在介绍链接描述文件的命令之前, 先看看下述的简单例子:
以下脚本将输出文件的text section定位在0×10000, data section定位在0×8000000:
SECTIONS
{
. = 0×10000;
.text : { *(.text) }
. = 0×8000000;
.data : { *(.data) }
.bss : { *(.bss) }
}
解释一下上述的例子:
. = 0×10000 : 把定位器符号置为0×10000 (若不指定, 则该符号的初始值为0).
.text : { *(.text) } : 将所有(*符号代表任意输入文件)输入文件的.text section合并成一个.text section, 该section的地址由定位器符号的值指定, 即0×10000.
. = 0×8000000 :把定位器符号置为0×8000000
.data : { *(.data) } : 将所有输入文件的.data section合并成一个.data section, 该section的地址被置为0×8000000.
.bss : { *(.bss) } : 将所有输入文件的.bss section合并成一个.bss section,该section的地址被置为0×8000000+.data section的大小.
连接器每读完一个section描述后, 将定位器符号的值*增加*该section的大小. 注意: 此处没有考虑对齐约束.
5. 简单脚本命令
- 1 -
ENTRY(SYMBOL) : 将符号SYMBOL的值设置成入口地址。
入口地址(entry point): 进程执行的第一条用户空间的指令在进程地址空间的地址)
ld有多种方法设置进程入口地址, 按一下顺序: (编号越前, 优先级越高)
1, ld命令行的-e选项
2, 连接脚本的ENTRY(SYMBOL)命令
3, 如果定义了start符号, 使用start符号值
4, 如果存在.text section, 使用.text section的第一字节的位置值
5, 使用值0
- 2 -INCLUDE filename : 包含其他名为filename的链接脚本
相当于c程序内的的#include指令, 用以包含另一个链接脚本.
脚本搜索路径由-L选项指定. INCLUDE指令可以嵌套使用, 最大深度为10. 即: 文件1内INCLUDE文件2, 文件2内INCLUDE文件3… , 文件10内INCLUDE文件11. 那么文件11内不能再出现 INCLUDE指令了.
- 3 -INPUT(files): 将括号内的文件做为链接过程的输入文件
ld首先在当前目录下寻找该文件, 如果没找到, 则在由-L指定的搜索路径下搜索. file可以为 -lfile形式,就象命令行的-l选项一样. 如果该命令出现在暗含的脚本内, 则该命令内的file在链接过程中的顺序由该暗含的脚本在命令行内的顺序决定.
- 4 -GROUP(files) : 指定需要重复搜索符号定义的多个输入文件
file必须是库文件, 且file文件作为一组被ld重复扫描,直到不在有新的未定义的引用出现。
- 5 -OUTPUT(FILENAME) : 定义输出文件的名字
同ld的-o选项, 不过-o选项的优先级更高. 所以它可以用来定义默认的输出文件名. 如a.out
- 6 -SEARCH_DIR(PATH) :定义搜索路径,
同ld的-L选项, 不过由-L指定的路径要比它定义的优先被搜索。
- 7 -STARTUP(filename) : 指定filename为第一个输入文件
在链接过程中, 每个输入文件是有顺序的. 此命令设置文件filename为第一个输入文件。
- 8 – OUTPUT_FORMAT(BFDNAME) : 设置输出文件使用的BFD格式
同ld选项-o format BFDNAME, 不过ld选项优先级更高.
- 9 -OUTPUT_FORMAT(DEFAULT,BIG,LITTLE) : 定义三种输出文件的格式(大小端)
若有命令行选项-EB, 则使用第2个BFD格式; 若有命令行选项-EL,则使用第3个BFD格式.否则默认选第一个BFD格式.
TARGET(BFDNAME):设置输入文件的BFD格式
同ld选项-b BFDNAME. 若使用了TARGET命令, 但未使用OUTPUT_FORMAT命令, 则最用一个TARGET命令设置的BFD格式将被作为输出文件的BFD格式.
另外还有一些:
ASSERT(EXP, MESSAGE):如果EXP不为真,终止连接过程
EXTERN(SYMBOL SYMBOL …):在输出文件中增加未定义的符号,如同连接器选项-u
FORCE_COMMON_ALLOCATION:为common symbol(通用符号)分配空间,即使用了-r连接选项也为其分配
NOCROSSREFS(SECTION SECTION …):检查列出的输出section,如果发现他们之间有相互引用,则报错。对于某些系统,特别是内存较紧张的嵌入式系统,某些section是不能同时存在内存中的,所以他们之间不能相互引用。
OUTPUT_ARCH(BFDARCH):设置输出文件的machine architecture(体系结构),BFDARCH为被BFD库使用的名字之一。可以用命令objdump -f查看。
可通过 man -S 1 ld查看ld的联机帮助, 里面也包括了对这些命令的介绍.
6. 对符号的赋值
在目标文件内定义的符号可以在链接脚本内被赋值. (注意和C语言中赋值的不同!) 此时该符号被定义为全局的. 每个符号都对应了一个地址, 此处的赋值是更改这个符号对应的地址.
e.g. 通过下面的程序查看变量a的地址:
/* a.c */
#include
int a = 100;
int main(void)
{
printf( “&a=0x%p “, &a );
return 0;
}/* a.lds */
a = 3;
$ gcc -Wall -o a-without-lds a.c
&a = 0×8049598
$ gcc -Wall -o a-with-lds a.c a.lds
&a = 0×3
注意: 对符号的赋值只对全局变量起作用!
一些简单的赋值语句
能使用任何c语言内的赋值操作:
SYMBOL = EXPRESSION ;
SYMBOL += EXPRESSION ;
SYMBOL -= EXPRESSION ;
SYMBOL *= EXPRESSION ;
SYMBOL /= EXPRESSION ;
SYMBOL >= EXPRESSION ;
SYMBOL &= EXPRESSION ;
SYMBOL |= EXPRESSION ;
除了第一类表达式外, 使用其他表达式需要SYMBOL被定义于某目标文件。
. 是一个特殊的符号,它是定位器,一个位置指针,指向程序地址空间内的某位置(或某section内的偏移,如果它在SECTIONS命令内的某section描述内),该符号只能在SECTIONS命令内使用。
注意:赋值语句包含4个语法元素:符号名、操作符、表达式、分号;一个也不能少。
被赋值后,符号所属的section被设值为表达式EXPRESSION所属的SECTION(参看11. 脚本内的表达式)
赋值语句可以出现在连接脚本的三处地方:SECTIONS命令内,SECTIONS命令内的section描述内和全局位置;如下,
floating_point = 0; /* 全局位置 */
SECTIONS
{
.text :
{
*(.text)
_etext = .; /* section描述内 */
}
_bdata = (. + 3) & ~ 4; /* SECTIONS命令内 */
.data : { *(.data) }
}
PROVIDE关键字
该关键字用于定义这类符号:在目标文件内被引用,但没有在任何目标文件内被定义的符号。
例子:
SECTIONS
{
.text :
{
*(.text)
_etext = .;
PROVIDE(etext = .);
}
}
当目标文件内引用了etext符号,确没有定义它时,etext符号对应的地址被定义为.text section之后的第一个字节的地址。
7. SECTIONS命令
SECTIONS命令告诉ld如何把输入文件的sections映射到输出文件的各个section: 如何将输入section合为输出section; 如何把输出section放入程序地址空间(VMA)和进程地址空间(LMA).该命令格式如下:
SECTIONS
{
SECTIONS-COMMAND
SECTIONS-COMMAND

}
SECTION-COMMAND有四种:
(1) ENTRY命令
(2) 符号赋值语句
(3) 一个输出section的描述(output section description)
(4) 一个section叠加描述(overlay description)
如果整个连接脚本内没有SECTIONS命令, 那么ld将所有同名输入section合成为一个输出section内, 各输入section的顺序为它们被连接器发现的顺序.
如果某输入section没有在SECTIONS命令中提到, 那么该section将被直接拷贝成输出section。
输出section描述
输出section描述具有如下格式:
SECTION [ADDRESS] [(TYPE)] : [AT(LMA)]
{
OUTPUT-SECTION-COMMAND
OUTPUT-SECTION-COMMAND

} [>REGION] [AT>LMA_REGION] [:PHDR

HDR ...] [=FILLEXP]
[ ]内的内容为可选选项, 一般不需要.
SECTION:section名字
SECTION左右的空白、圆括号、冒号是必须的,换行符和其他空格是可选的。
每个OUTPUT-SECTION-COMMAND为以下四种之一,
符号赋值语句
一个输入section描述
直接包含的数据值
一个特殊的输出section关键字
输出section名字(SECTION):
输出section名字必须符合输出文件格式要求,比如:a.out格式的文件只允许存在.text、.data和.bss section名。而有的格式只允许存在数字名字,那么此时应该用引号将所有名字内的数字组合在一起;另外,还有一些格式允许任何序列的字符存在于 section名字内,此时如果名字内包含特殊字符(比如空格、逗号等),那么需要用引号将其组合在一起。
输出section地址(ADDRESS):
ADDRESS是一个表达式,它的值用于设置VMA。如果没有该选项且有REGION选项,那么连接器将根据REGION设置VMA;如果也没有 REGION选项,那么连接器将根据定位符号‘.’的值设置该section的VMA,将定位符号的值调整到满足输出section对齐要求后的值,输出 section的对齐要求为:该输出section描述内用到的所有输入section的对齐要求中最严格的。
例子:
.text . : { *(.text) }

.text : { *(.text) }
这两个描述是截然不同的,第一个将.text section的VMA设置为定位符号的值,而第二个则是设置成定位符号的修调值,满足对齐要求后的。
ADDRESS可以是一个任意表达式,比如ALIGN(0×10)这将把该section的VMA设置成定位符号的修调值,满足16字节对齐后的。
注意:设置ADDRESS值,将更改定位符号的值。
输入section描述:
最常见的输出section描述命令是输入section描述。
输入section描述是最基本的连接脚本描述。
输入section描述基础:
基本语法:FILENAME([EXCLUDE_FILE (FILENAME1 FILENAME2 ...) SECTION1 SECTION2 ...)
FILENAME文件名,可以是一个特定的文件的名字,也可以是一个字符串模式。
SECTION名字,可以是一个特定的section名字,也可以是一个字符串模式
例子是最能说明问题的,
*(.text) :表示所有输入文件的.text section
(*(EXCLUDE_FILE (*crtend.o *otherfile.o) .ctors)) :表示除crtend.o、otherfile.o文件外的所有输入文件的.ctors section。
data.o(.data) :表示data.o文件的.data section
data.o :表示data.o文件的所有section
*(.text .data) :表示所有文件的.text section和.data section,顺序是:第一个文件的.text section,第一个文件的.data section,第二个文件的.text section,第二个文件的.data section,...
*(.text) *(.data) :表示所有文件的.text section和.data section,顺序是:第一个文件的.text section,第二个文件的.text section,...,最后一个文件的.text section,第一个文件的.data section,第二个文件的.data section,...,最后一个文件的.data section
下面看连接器是如何找到对应的文件的。
当FILENAME是一个特定的文件名时,连接器会查看它是否在连接命令行内出现或在INPUT命令中出现。
当FILENAME是一个字符串模式时,连接器仅仅只查看它是否在连接命令行内出现。
注意:如果连接器发现某文件在INPUT命令内出现,那么它会在-L指定的路径内搜寻该文件。
字符串模式内可存在以下通配符:
* :表示任意多个字符
? :表示任意一个字符
[CHARS] :表示任意一个CHARS内的字符,可用-号表示范围,如:a-z
:表示引用下一个紧跟的字符
在文件名内,通配符不匹配文件夹分隔符/,但当字符串模式仅包含通配符*时除外。
任何一个文件的任意section只能在SECTIONS命令内出现一次。看如下例子,
SECTIONS {
.data : { *(.data) }
.data1 : { data.o(.data) }
}
data.o文件的.data section在第一个OUTPUT-SECTION-COMMAND命令内被使用了,那么在第二个OUTPUT-SECTION-COMMAND命令内将不会再被使用,也就是说即使连接器不报错,输出文件的.data1 section的内容也是空的。
再次强调:连接器依次扫描每个OUTPUT-SECTION-COMMAND命令内的文件名,任何一个文件的任何一个section都只能使用一次。
读者可以用-M连接命令选项来产生一个map文件,它包含了所有输入section到输出section的组合信息。
再看个例子,
SECTIONS {
.text : { *(.text) }
.DATA : { [A-Z]*(.data) }
.data : { *(.data) }
.bss : { *(.bss) }
}
这个例子中说明,所有文件的输入.text section组成输出.text section;所有以大写字母开头的文件的.data section组成输出.DATA section,其他文件的.data section组成输出.data section;所有文件的输入.bss section组成输出.bss section。
可以用SORT()关键字对满足字符串模式的所有名字进行递增排序,如SORT(.text*)。
通用符号(common symbol)的输入section:
在许多目标文件格式中,通用符号并没有占用一个section。连接器认为:输入文件的所有通用符号在名为COMMON的section内。
例子,
.bss { *(.bss) *(COMMON) }
这个例子中将所有输入文件的所有通用符号放入输出.bss section内。可以看到COMMOM section的使用方法跟其他section的使用方法是一样的。
有些目标文件格式把通用符号分成几类。例如,在MIPS elf目标文件格式中,把通用符号分成standard common symbols(标准通用符号)和small common symbols(微通用符号,不知道这么译对不对?),此时连接器认为所有standard common symbols在COMMON section内,而small common symbols在.scommon section内。
在一些以前的连接脚本内可以看见[COMMON],相当于*(COMMON),不建议继续使用这种陈旧的方式。
输入section和垃圾回收:
在连接命令行内使用了选项–gc-sections后,连接器可能将某些它认为没用的section过滤掉,此时就有必要强制连接器保留一些特定的 section,可用KEEP()关键字达此目的。如KEEP(*(.text))或KEEP(SORT(*)(.text))
最后看个简单的输入section相关例子:
SECTIONS {
outputa 0×10000 :
{
all.o
foo.o (.input1)
}
outputb :
{
foo.o (.input2)
foo1.o (.input1)
}
outputc :
{
*(.input1)
*(.input2)
}
}
本例中,将all.o文件的所有section和foo.o文件的所有(一个文件内可以有多个同名section).input1 section依次放入输出outputa section内,该section的VMA是0×10000;将foo.o文件的所有.input2 section和foo1.o文件的所有.input1 section依次放入输出outputb section内,该section的VMA是当前定位器符号的修调值(对齐后);将其他文件(非all.o、foo.o、foo1.o)文件的. input1 section和.input2 section放入输出outputc section内。
在输出section存放数据命令:
能够显示地在输出section内填入你想要填入的信息(这样是不是可以自己通过连接脚本写程序?当然是简单的程序)。
BYTE(EXPRESSION) 1 字节
SHORT(EXPRESSION) 2 字节
LOGN(EXPRESSION) 4 字节
QUAD(EXPRESSION) 8 字节
SQUAD(EXPRESSION) 64位处理器的代码时,8 字节
输出文件的字节顺序big endianness 或little endianness,可以由输出目标文件的格式决定;如果输出目标文件的格式不能决定字节顺序,那么字节顺序与第一个输入文件的字节顺序相同。
如:BYTE(1)、LANG(addr)。
注意,这些命令只能放在输出section描述内,其他地方不行。
错误:SECTIONS { .text : { *(.text) } LONG(1) .data : { *(.data) } }
正确:SECTIONS { .text : { *(.text) LONG(1) } .data : { *(.data) } }
在当前输出section内可能存在未描述的存储区域(比如由于对齐造成的空隙),可以用FILL(EXPRESSION)命令决定这些存储区域的内容, EXPRESSION的前两字节有效,这两字节在必要时可以重复被使用以填充这类存储区域。如FILE(0×9090)。在输出section描述中可以有=FILEEXP属性,它的作用如同FILE()命令,但是FILE命令只作用于该FILE指令之后的section区域,而=FILEEXP属性作用于整个输出section区域,且FILE命令的优先级更高!!!
输出section内命令的关键字:
CREATE_OBJECT_SYMBOLS :为每个输入文件建立一个符号,符号名为输入文件的名字。每个符号所在的section是出现该关键字的section。
CONSTRUCTORS :与c++内的(全局对象的)构造函数和(全局对像的)析构函数相关,下面将它们简称为全局构造和全局析构。
对于a.out目标文件格式,连接器用一些不寻常的方法实现c++的全局构造和全局析构。当连接器生成的目标文件格式不支持任意section名字时,比如说ECOFF、XCOFF格式,连接器将通过名字来识别全局构造和全局析构,对于这些文件格式,连接器把与全局构造和全局析构的相关信息放入出现 CONSTRUCTORS关键字的输出section内。
符号__CTORS_LIST__表示全局构造信息的的开始处,__CTORS_END__表示全局构造信息的结束处。
符号__DTORS_LIST__表示全局构造信息的的开始处,__DTORS_END__表示全局构造信息的结束处。
这两块信息的开始处是一字长的信息,表示该块信息有多少项数据,然后以值为零的一字长数据结束。
一般来说,GNU C++在函数__main内安排全局构造代码的运行,而__main函数被初始化代码(在main函数调用之前执行)调用。是不是对于某些目标文件格式才这样???
对于支持任意section名的目标文件格式,比如COFF、ELF格式,GNU C++将全局构造和全局析构信息分别放入.ctors section和.dtors section内,然后在连接脚本内加入如下,
__CTOR_LIST__ = .;
LONG((__CTOR_END__ – __CTOR_LIST__) / 4 – 2)
*(.ctors)
LONG(0)
__CTOR_END__ = .;
__DTOR_LIST__ = .;
LONG((__DTOR_END__ – __DTOR_LIST__) / 4 – 2)
*(.dtors)
LONG(0)
__DTOR_END__ = .;
如果使用GNU C++提供的初始化优先级支持(它能控制每个全局构造函数调用的先后顺序),那么请在连接脚本内把CONSTRUCTORS替换成SORT (CONSTRUCTS),把*(.ctors)换成*(SORT(.ctors)),把*(.dtors)换成*(SORT(.dtors))。一般来说,默认的连接脚本已作好的这些工作。
输出section的丢弃:
例子,.foo { *(.foo) },如果没有任何一个输入文件包含.foo section,那么连接器将不会创建.foo输出section。但是如果在这些输出section描述内包含了非输入section描述命令(如符号赋值语句),那么连接器将总是创建该输出section。
有一个特殊的输出section,名为/DISCARD/,被该section引用的任何输入section将不会出现在输出文件内,这就是DISCARD的意思吧。如果/DISCARD/ section被它自己引用呢?想想看。
输出section属性:
终于讲到这里了,呵呵。
我们再回顾以下输出section描述的文法:
SECTION [ADDRESS] [(TYPE)] : [AT(LMA)]
{
OUTPUT-SECTION-COMMAND
OUTPUT-SECTION-COMMAND

} [>REGION] [AT>LMA_REGION] [:PHDR

HDR ...] [=FILLEXP]
前面我们浏览了SECTION、ADDRESS、OUTPUT-SECTION-COMMAND相关信息,下面我们将浏览其他属性。
TYPE :每个输出section都有一个类型,如果没有指定TYPE类型,那么连接器根据输出section引用的输入section的类型设置该输出section的类型。它可以为以下五种值,
NOLOAD :该section在程序运行时,不被载入内存。
DSECT,COPY,INFO,OVERLAY :这些类型很少被使用,为了向后兼容才被保留下来。这种类型的section必须被标记为“不可加载的”,以便在程序运行不为它们分配内存。
输出section的LMA :默认情况下,LMA等于VMA,但可以通过关键字AT()指定LMA。
用关键字AT()指定,括号内包含表达式,表达式的值用于设置LMA。如果不用AT()关键字,那么可用AT>LMA_REGION表达式设置指定该section加载地址的范围。
这个属性主要用于构件ROM境象。
例子,
SECTIONS
{
.text 0×1000 : { *(.text) _etext = . ; }
.mdata 0×2000 :
AT ( ADDR (.text) + SIZEOF (.text) )
{ _data = . ; *(.data); _edata = . ; }
.bss 0×3000 :
{ _bstart = . ; *(.bss) *(COMMON) ; _bend = . ;}
}
程序如下,
extern char _etext, _data, _edata, _bstart, _bend;
char *src = &_etext;
char *dst = &_data;
/* ROM has data at end of text; copy it. */
while (dst rom }
输出section所在的程序段:可以将输出section放入预先定义的程序段(program segment)内。如果某个输出section设置了它所在的一个或多个程序段,那么接下来定义的输出section的默认程序段与该输出 section的相同。除非再次显示地指定。例子,
PHDRS { text PT_LOAD ; }
SECTIONS { .text : { *(.text) } :text }
可以通过:NONE指定连接器不把该section放入任何程序段内。详情请查看PHDRS命令
输出section的填充模版:这个在前面提到过,任何输出section描述内的未指定的内存区域,连接器用该模版填充该区域。用法:=FILEEXP,前两字节有效,当区域大于两字节时,重复使用这两字节以将其填满。例子,
SECTIONS { .text : { *(.text) } =0×9090 }
覆盖图(overlay)描述:
覆盖图描述使两个或多个不同的section占用同一块程序地址空间。覆盖图管理代码负责将section的拷入和拷出。考虑这种情况,当某存储块的访问速度比其他存储块要快时,那么如果将section拷到该存储块来执行或访问,那么速度将会有所提高,覆盖图描述就很适合这种情形。文法如下,
SECTIONS {

OVERLAY [START] : [NOCROSSREFS] [AT ( LDADDR )]
{
SECNAME1
{
OUTPUT-SECTION-COMMAND
OUTPUT-SECTION-COMMAND

} [:PHDR...] [=FILL]
SECNAME2
{
OUTPUT-SECTION-COMMAND
OUTPUT-SECTION-COMMAND

} [:PHDR...] [=FILL]

} [>REGION] [:PHDR...] [=FILL]

}
由以上文法可以看出,同一覆盖图内的section具有相同的VMA。SECNAME2的LMA为SECTNAME1的LMA加上SECNAME1的大小,同理计算SECNAME2,3,4…的LMA。SECNAME1的LMA由LDADDR决定,如果它没有被指定,那么由START决定,如果它也没有被指定,那么由当前定位符号的值决定。
NOCROSSREFS关键字指定各section之间不能交叉引用,否则报错。
对于OVERLAY描述的每个section,连接器将定义两个符号__load_start_SECNAME和__load_stop_SECNAME,这两个符号的值分别代表SECNAME section的LMA地址的开始和结束。
连接器处理完OVERLAY描述语句后,将定位符号的值加上所有覆盖图内section大小的最大值。
看个例子吧,
SECTIONS{

OVERLAY 0×1000 : AT (0×4000)
{
.text0 { o1/*.o(.text) }
.text1 { o2/*.o(.text) }
}

}
.text0 section和.text1 section的VMA地址是0×1000,.text0 section加载于地址0×4000,.text1 section紧跟在其后。
程序代码,拷贝.text1 section代码,
extern char __load_start_text1, __load_stop_text1;
memcpy ((char *) 0×1000, &__load_start_text1,
&__load_stop_text1 – &__load_start_text1);
8. 内存区域命令
—————
注意:以下存储区域指的是在程序地址空间内的。
在默认情形下,连接器可以为section分配任意位置的存储区域。你也可以用MEMORY命令定义存储区域,并通过输出section描述的> REGION属性显示地将该输出section限定于某块存储区域,当存储区域大小不能满足要求时,连接器会报告该错误。
MEMORY命令的文法如下,
MEMORY {
NAME1 [(ATTR)] : ORIGIN = ORIGIN1, LENGTH = LEN2
NAME2 [(ATTR)] : ORIGIN = ORIGIN2, LENGTH = LEN2

}
NAME :存储区域的名字,这个名字可以与符号名、文件名、section名重复,因为它处于一个独立的名字空间。
ATTR :定义该存储区域的属性,在讲述SECTIONS命令时提到,当某输入section没有在SECTIONS命令内引用时,连接器会把该输入 section直接拷贝成输出section,然后将该输出section放入内存区域内。如果设置了内存区域设置了ATTR属性,那么该区域只接受满足该属性的section(怎么判断该section是否满足?输出section描述内好象没有记录该section的读写执行属性)。ATTR属性内可以出现以下7个字符,
R 只读section
W 读/写section
X 可执行section
A ‘可分配的’section
I 初始化了的section
L 同I
! 不满足该字符之后的任何一个属性的section
ORIGIN :关键字,区域的开始地址,可简写成org或o
LENGTH :关键字,区域的大小,可简写成len或l
例子,
MEMORY
{
rom (rx) : ORIGIN = 0, LENGTH = 256K
ram (!rx) : org = 0×40000000, l = 4M
}
此例中,把在SECTIONS命令内*未*引用的且具有读属性或写属性的输入section放入rom区域内,把其他未引用的输入section放入 ram。如果某输出section要被放入某内存区域内,而该输出section又没有指明ADDRESS属性,那么连接器将该输出section放在该区域内下一个能使用位置。
9. PHDRS命令
————
该命令仅在产生ELF目标文件时有效。
ELF目标文件格式用program headers程序头(程序头内包含一个或多个segment程序段描述)来描述程序如何被载入内存。可以用objdump -p命令查看。
当在本地ELF系统运行ELF目标文件格式的程序时,系统加载器通过读取程序头信息以知道如何将程序加载到内存。要了解系统加载器如何解析程序头,请参考ELF ABI文档。
在连接脚本内不指定PHDRS命令时,连接器能够很好的创建程序头,但是有时需要更精确的描述程序头,那么PAHDRS命令就派上用场了。
注意:一旦在连接脚本内使用了PHDRS命令,那么连接器**仅会**创建PHDRS命令指定的信息,所以使用时须谨慎。
PHDRS命令文法如下,
PHDRS
{
NAME TYPE [ FILEHDR ] [ PHDRS ] [ AT ( ADDRESS ) ]
[ FLAGS ( FLAGS ) ] ;
}
其中FILEHDR、PHDRS、AT、FLAGS为关键字。
NAME :为程序段名,此名字可以与符号名、section名、文件名重复,因为它在一个独立的名字空间内。此名字只能在SECTIONS命令内使用。
一个程序段可以由多个‘可加载’的section组成。通过输出section描述的属性:PHDRS可以将输出section加入一个程序段,: PHDRS中的PHDRS为程序段名。在一个输出section描述内可以多次使用:PHDRS命令,也即可以将一个section加入多个程序段。
如果在一个输出section描述内指定了:PHDRS属性,那么其后的输出section描述将默认使用该属性,除非它也定义了:PHDRS属性。显然当多个输出section属于同一程序段时可简化书写。
在TYPE属性后存在FILEHDR关键字,表示该段包含ELF文件头信息;存在PHDRS关键字,表示该段包含ELF程序头信息。
TYPE可以是以下八种形式,
PT_NULL 0
表示未被使用的程序段
PT_LOAD 1
表示该程序段在程序运行时应该被加载
PT_DYNAMIC 2
表示该程序段包含动态连接信息
PT_INTERP 3
表示该程序段内包含程序加载器的名字,在linux下常见的程序加载器是ld-linux.so.2
PT_NOTE 4
表示该程序段内包含程序的说明信息
PT_SHLIB 5
一个保留的程序头类型,没有在ELF ABI文档内定义
PT_PHDR 6
表示该程序段包含程序头信息。
EXPRESSION 表达式值
以上每个类型都对应一个数字,该表达式定义一个用户自定的程序头。
AT(ADDRESS)属性定义该程序段的加载位置(LMA),该属性将**覆盖**该程序段内的section的AT()属性。
默认情况下,连接器会根据该程序段包含的section的属性(什么属性?好象在输出section描述内没有看到)设置FLAGS标志,该标志用于设置程序段描述的p_flags域。
下面看一个典型的PHDRS设置,
PHDRS
{
headers PT_PHDR PHDRS ;
interp PT_INTERP ;
text PT_LOAD FILEHDR PHDRS ;
data PT_LOAD ;
dynamic PT_DYNAMIC ;
}
SECTIONS
{
. = SIZEOF_HEADERS;
.interp : { *(.interp) } :text :interp
.text : { *(.text) } :text
.rodata : { *(.rodata) } /* defaults to :text */

. = . + 0×1000; /* move to a new page in memory */
.data : { *(.data) } :data
.dynamic : { *(.dynamic) } :data :dynamic

}
10. 版本号命令
————–
当使用ELF目标文件格式时,连接器支持带版本号的符号。
读者可以发现仅仅在共享库中,符号的版本号属性才有意义。
动态加载器使用符号的版本号为应用程序选择共享库内的一个函数的特定实现版本。
可以在连接脚本内直接使用版本号命令,也可以将版本号命令实现于一个特定版本号描述文件(用连接选项–version-script指定该文件)。
该命令的文法如下,
VERSION { version-script-commands }
以下内容直接拷贝于以前的文档,
===================== 开始 ==================================
内容简介
———
0 前提
1 带版本号的符号的定义
2 连接到带版本的符号
3 GNU扩充
4 我的疑问
5 英文搜索关键字
6 我的参考
0. 前提
– 只限于ELF文件格式
– 以下讨论用gcc
1. 带版本号的符号的定义(共享库内)
文件b.c内容如下,
int old_true()
{
return 1;
}
int new_true()
{
return 2;
}
写连接器的版本控制脚本,本例中为b.lds,内容如下
VER1.0{
new_true;
};
VER2.0{
};
$gcc -c b.c
$gcc -shared -Wl,–version-script=b.lds -o libb.so b.o
可以在{}内填入要绑定的符号,本例中new_true符号就与VER1.0绑定了。
那么如果有一个应用程序连接到该库的new_true符号,那么它连接的就是VER1.0版本的new_true符号
如果把b.lds更改为,
VER1.0{
};
VER2.0{
new_true;
};
然后在生成libb.so文件,在运行那个连接到VER1.0版本的new_true符号的应用程序,可以发现该应用程序不能运行了,
因为库内没有VER1.0版本的new_true,只有VER2.0版本的new_true。
2. 连接到带版本的符号
写一个简单的应用(名为app)连接到libb.so,应用符号new_true
假设libb.so的版本控制文件为,
VER1.0{
};
VER2.0{
new_true;
};
$ nm app | grep new_true
U new_true@@VER1.0
$
用nm命令发现app连接到VER1.0版本的new_true
3. GNU的扩充
它允许在程序文件内绑定 *符号* 到 *带版本号的别名符号*
文件b.c内容如下,
int old_true()
{
return 1;
}
int new_true()
{
return 2;
}
__asm__( “.symver old_true,true@VER1.0″ );
__asm__( “.symver new_true,true@@VER2.0″ );
其中,带版本号的别名符号是true,其默认的版本号为VER2.0
供连接器用的版本控制脚本b.lds内容如下,
VER1.0{
};
VER2.0{
};
版本控制文件内必须包含版本VER1.0和版本VER2.0的定义,因为在b.c文件内有对他们的引用
****** 假定libb.so与app.c在同一目录下 ********
以下应用程序app.c连接到该库,
int true();
int main()
{
printf( “%d “, true );
}
$ gcc app.c libb.so
$ LD_LIBRARY_PATH=. ./app
2
$ nm app | grep true
U true@@VER2.0
$
很明显,程序app使用的是VER2.0版本的别名符号true,如果在b.c内没有指明别名符号true的默认版本,
那么gcc app.c libb.so将出现连接错误,提示true没有定义。
也可以在程序内指定特定版本的别名符号true,程序如下,
__asm__( “.symver true,true@VER1.0″ );
int true();
int main()
{
printf( “%d “, true );
}
$ gcc app.c libb.so
$ LD_LIBRARY_PATH=. ./app
1
$ nm app | grep true
U true@VER1.0
$
显然,连接到了版本号为VER1.0的别名符号true。其中只有一个@表示,该版本不是默认的版本
我的疑问:
版本控制脚本文件中,各版本号节点之间的依赖关系
英文搜索关键字:
.symver
versioned symbol
version a shared library
参考:
info ld, Scripts node
===================== 结束 ==================================
11. 表达式
———-
表达式的文法与C语言的表达式文法一致,表达式的值都是整型,如果ld的运行主机和生成文件的目标机都是32位,则表达式是32位数据,否则是64位数据。
能够在表达式内使用符号的值,设置符号的值。
下面看六项表达式相关内容,
常表达式:
_fourk_1 = 4K; /* K、M单位 */
_fourk_2 = 4096; /* 整数 */
_fourk_3 = 0×1000; /* 16 进位 */
_fourk_4 = 01000; /* 8 进位 */
1K=1024 1M=1024*1024
符号名:
没有被引号””包围的符号,以字母、下划线或’.’开头,可包含字母、下划线、’.’和’-’。当符号名被引号包围时,符号名可以与关键字相同。如,
“SECTION”=9
“with a space” = “also with a space” + 10;
定位符号’.’:
只在SECTIONS命令内有效,代表一个程序地址空间内的地址。
注意:当定位符用在SECTIONS命令的输出section描述内时,它代表的是该section的当前**偏移**,而不是程序地址空间的绝对地址。
先看个例子,
SECTIONS
{
output :
{
file1(.text)
. = . + 1000;
file2(.text)
. += 1000;
file3(.text)
} = 0×1234;
}
其中由于对定位符的赋值而产生的空隙由0×1234填充。其他的内容应该容易理解吧。
再看个例子,
SECTIONS
{
. = 0×100
.text: {
*(.text)
. = 0×200
}
. = 0×500
.data: {
*(.data)
. += 0×600
}
} .text section在程序地址空间的开始位置是0x
表达式的操作符:
与C语言一致。
优先级 结合顺序 操作符
1 left ! – ~ (1)
2 left * / %
3 left + -
4 left >>  =
6 left &
7 left |
8 left &&
9 left ||
10 right ? :
11 right &= += -= *= /= (2)
(1)表示前缀符,(2)表示赋值符。
表达式的计算:
连接器延迟计算大部分表达式的值。
但是,对待与连接过程紧密相关的表达式,连接器会立即计算表达式,如果不能计算则报错。比如,对于section的VMA地址、内存区域块的开始地址和大小,与其相关的表达式应该立即被计算。
例子,
SECTIONS
{
.text 9+this_isnt_constant :
{ *(.text) }
}
这个例子中,9+this_isnt_constant表达式的值用于设置.text section的VMA地址,因此需要立即运算,但是由于this_isnt_constant变量的值不确定,所以此时连接器无法确立表达式的值,此时连接器会报错。
相对值与绝对值:
在输出section描述内的表达式,连接器取其相对值,相对与该section的开始位置的偏移
在SECTIONS命令内且非输出section描述内的表达式,连接器取其绝对值
通过ABSOLUTE关键字可以将相对值转化成绝对值,即在原来值的基础上加上表达式所在section的VMA值。
例子,
SECTIONS
{
.data : { *(.data) _edata = ABSOLUTE(.); }
}
该例子中,_edata符号的值是.data section的末尾位置(绝对值,在程序地址空间内)。
内建函数:
ABSOLUTE(EXP) :转换成绝对值
ADDR(SECTION) :返回某section的VMA值。
ALIGN(EXP) :返回定位符’.’的修调值,对齐后的值,(. + EXP – 1) & ~(EXP – 1)
BLOCK(EXP) :如同ALIGN(EXP),为了向前兼容。
DEFINED(SYMBOL) :如果符号SYMBOL在全局符号表内,且被定义了,那么返回1,否则返回0。例子,
SECTIONS { …
.text : {
begin = DEFINED(begin) ? begin : . ;

}

}
LOADADDR(SECTION) :返回三SECTION的LMA
MAX(EXP1,EXP2) :返回大者
MIN(EXP1,EXP2) :返回小者
NEXT(EXP) :返回下一个能被使用的地址,该地址是EXP的倍数,类似于ALIGN(EXP)。除非使用了MEMORY命令定义了一些非连续的内存块,否则NEXT(EXP)与ALIGH(EXP)一定相同。
SIZEOF(SECTION) :返回SECTION的大小。当SECTION没有被分配时,即此时SECTION的大小还不能确定时,连接器会报错。
SIZEOF_HEADERS :
sizeof_headers :返回输出文件的文件头大小(还是程序头大小),用以确定第一个section的开始地址(在文件内)。???
12. 暗含的连接脚本
输入文件可以是目标文件,也可以是连接脚本,此时的连接脚本被称为 暗含的连接脚本
如果连接器不认识某个输入文件,那么该文件被当作连接脚本被解析。更进一步,如果发现它的格式又不是连接脚本的格式,那么连接器报错。
一个暗含的连接脚本不会替换默认的连接脚本,仅仅是增加新的连接而已。
一般来说,暗含的连接脚本符号分配命令,或INPUT、GROUP、VERSION命令。
在连接命令行中,每个输入文件的顺序都被固定好了,暗含的连接脚本在连接命令行内占住一个位置,这个位置决定了由该连接脚本指定的输入文件在连接过程中的顺序。
典型的暗含的连接脚本是libc.so文件,在GNU/linux内一般存在/usr/lib目录下。

 | 45 views | 0 comments | 0 flags | 

Java为什么需要保留基本数据类型

http://www.importnew.com/11915.html

基本数据类型对以数值计算为主的应用程序来说是必不可少的。

自从1996年Java发布以来,基本数据类型就是Java语言的一部分。John Moore通过对使用基本类型和不使用基本类型做java基准测试给Java中为什么要保留基本数据类型做了一个很有力的说明。然后,他还在特定类型的应用中把Java和Scala、C++和JavaScript的性能做了对比。在这些应用中,使用基本数据类型应用性能会有很显著的不同。

问:影响买房最重要的三个因素是什么?
答:位置!位置!还是位置!!

这是个很古老但却经常被提及的谚语。意思是,当购买房产的时候,位置因素是绝对的主导因素。与此类似,考虑在Java中使用基本数据类型的3个最重要的因素,那就是性能!性能!还是性能!!房产与基本数据类型有两个不同之处。首先,位置主导几乎适用于所有买房的情况。但是使用基本类型带来的性能提升,对不同类型的应用程序来大不相同。其次,尽管其他的因素与位置相比在买房时都显得不太重要,但是也是应该被考虑的因素。而使用基本数据类型的原因却只有一个——那就是性能,并且只适用于那些使用后能提升性能的应用。

基本数据类型对大多数业务相关或网络应用程序没有太大的用处,这些应用一般是采用客户端/服务器模式,后端有数据库。然而,使用基本数据类型对那种以数值计算为主的应用提升性能有很大好处。

在Java语言中包含基本数据类型是最有争议的设计决定之一,关于这个决定讨论的文章和帖子比比皆是。2011年9月,Simon Ritter在JAX London上的演讲说,要认真考虑在Java未来的某个版本中删除基本数据类型。接下来,我会简要介绍基本数据类型和Java的双类型系统。通过示例代码和简单的基准测试说明为什么基本数据类型对于某些类型的应用程序是必须的。我也会对Java与Scala、C++和JavaScript性能做一些比较。

测量软件性能

软件性能经常用时间和空间来衡量。时间可以是实际的运行时间,比如3.7分钟,或者是基于输入规模的时间复杂度,比如O(n2)。对于空间的衡量也是如此。经常用内存消耗来衡量,有时候也会扩大到磁盘的使用。改善性能经常要做时间和空间的折衷,缩短时间经常会对空间造成损害,反之亦然。时间复杂度取决于算法,把包装类型切换成基本数据类型对结果不会有任何改变,但是使用基本数据类型取代对象类型能改善时间和空间的性能。

基本数据类型vs对象类型

当你阅读这篇文章的时候,可能已经知道了Java是双类型的系统,也就是基本数据类型和对象类型,简称基本类型和对象。Java中有8个预定义的基本类型,它们的名字都是保留的关键字。常见的基本类型有int、double和boolean。Java中所有其他的类型包括用户自定义的类型,它们必然也是对象类型(我说”必然”是因为数组类型有点例外,与基本类型比数组更像是对象类型)。每一个基本类型都有一个对应的对象包装类,比如int的包装类是Integer,double的包装类是Double,boolean的包装类是Boolean。

基本类型基于值,而对象类型则基于引用。与基本类型相关的争议都源于此。为了说明它们的不同,先来看一下两个声明语句。第一个语句使用的是基本类型,第二个使用的是包装类。

1
2
int n1 = 100;
Integer n2 = new Integer(100);

使用新添加到JDK5的特性自动装箱以后,第二个声明可以简化成:

1
Integer n2 = 100;

但是,底层的语义并没有发生改变。自动装箱简化了包装类的使用,减少了程序员的编码量,但是对运行时并没有任何的改变。

图1展示了基本类型n1和包装对象类型n2的区别。

 

图1. 基本类型vs对象类型的内存结构
图1. 基本类型vs对象类型的内存结构

 

n1持有一个整数的值,但是n2持有的是对一个对象的引用,即那个对象持有整数的值。除此之外,n2引用的对象也包含了一个对Double对象的引用。

基本数据类型存在的问题

在我试图说服你需要基本类型之前,首先我应该感谢不同意我观点的那些人。Sherman Alpert在”基本类型是有害的(Primitive types considered harmful)”这篇文章中说基本类型是有害的,因为“它们把函数式的语义混进了面向对象模型里面,让面向对象变得不纯。基本类型不是对象,但是它们却存在于以一流对象为根本的语言中”。基本类型和(包装类形式的)对象类型提供了两种处理逻辑上相似的类型的方式,但是在底层的语义上却有着非常大的不同。比如,两个实例如何来比较相等性?对于基本类型,使用==操作符,但是对于对象类型,更好的方式是调用equals()方法,而基本类型是没有这个操作的。相似的,在赋值和传参的语义上也是不同的。就连默认值也是不一样的,比如int的默认是值0,但是Integer的默认值是null。

关于这个话题的更多的背景可以参考Eric Bruno的博客”关于基本类型的讨论(A modern primitive discussion)”,里面总结了关于基本类型的正反两方面的意见。Stack Overflow上也有很多关于基本类型的讨论,包括”为什么人们仍然在Java中使用基本类型?(Why do people still use primitive types in Java?)”,”有没有只使用对象不使用基本类型的理由?(Is there a reason to always use Objects instead of primitives?)”。Programmers Stack Exchange上也有一个类似的叫做”Java中什么时候应该使用基本类型和对象类型?(When to use primitive vs class in Java?)”的讨论。

内存的使用

Java中的double总是占据内存的64个比特,但是引用类型的字节数取决于JVM。我的电脑运行64位Win7和64位JVM,因此在我的电脑上一个引用占用64个比特。根据图1,一个double比如n1要占用8个字节(64比特),一个Double比如n2要占用24个字节——对象的引用占8个字节,对象中的double的值占8个字节,对象中对Double对象的引用占8个字节。此外,Java需要使用额外的内存来支持对象的垃圾回收,但是基本类型不需要。下面让我们来验证下。

跟Glen McCluskey在”Java基本类型 VS 包装类型(Java primitive types vs. wrappers)”中使用的方式类似,列表1中的方法会测量一个n*n的double类型的矩阵(二维数组)所占的字节数。

列表1. 计算double类型的内存使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static long getBytesUsingPrimitives(int n)
  {
    System.gc();   // force garbage collection
    long memStart = Runtime.getRuntime().freeMemory();
    double[][] a = new double[n][n];
    // put some random values in the matrix
    for (int i = 0;  i < n;  ++i)
      {
        for (int j = 0; j < n;  ++j)
            a[i][j] = Math.random();
      }
    long memEnd = Runtime.getRuntime().freeMemory();
    return memStart - memEnd;
  }

修改列表1中的代码(没有列出来),改变矩阵的元素类型,我们也可以测量一个nn的Double类型的矩阵所占的字节数。在我的电脑上用10001000的矩阵来测试这两个方法,我得到了表1的结果。就像之前说的那样,基本类型版本的double矩阵中每一个元素占8个多字节,跟我预期的差不多,但是,对象类型版本的Double矩阵中每一个元素占28个字节还要多一点。因此,在这个例子中,Double的内存使用是double的3倍还要多,这对那些明白上面图1说的内存布局的人来说,并不是一件让人很吃惊的事情。

表1. double和Double的内存使用情况对比

版本 总字节数 平均字节数
使用double 8,380,768 8.381
使用Double 28,166,072 28.166

运行时性能

为了比较基本类型和对象类型的运行时性能,我们需要一个数值计算占主导的算法。本文中,我选择了矩阵相乘,然后计算1000*1000的矩阵相乘所需要的时间。我用一种很直观的方式来编码double类型的矩阵相乘,就像列表2中展示的那样。可能会有更快的方式来实现矩阵相乘(比如使用并发),但那个与本文无关。我需要的仅仅是两个很简单的方法,一个使用基本类型的double,另一个使用包装类Double。Double类型的矩阵相乘的代码跟列表2非常相似,仅仅是改了类型。

列表2. 两种类型的浮点数的矩阵相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public static double[][] multiply(double[][] a, double[][] b)
  {
    if (!checkArgs(a, b))
        throw new IllegalArgumentException("Matrices not compatible for multiplication");
    int nRows = a.length;
    int nCols = b[0].length;
    double[][] result = new double[nRows][nCols];
    for (int rowNum = 0;  rowNum < nRows;  ++rowNum)
      {
        for (int colNum = 0;  colNum < nCols;  ++colNum)
          {
                double sum = 0.0;
                for (int i = 0;  i < a[0].length;  ++i)
                    sum += a[rowNum][i]*b[i][colNum];
                result[rowNum][colNum] = sum;
          }
      }
    return result;
  }

在我的计算机上分别用两个方法对两个1000*1000的矩阵做多次乘法,测量执行时间。表2中列出了平均时间。可以看出来,在本例中,double的运行时性能是Double的四倍。这是一个不能忽略的很大的不同!

版本 秒数
使用double 11.31
使用Double 48.48

SciMark2.0基准测试

迄今为止,我使用了一个简单的矩阵相乘的例子来说明基本类型比对象类型有更高的计算性能。为了让我的观点更站得住脚,我会用更科学的基准点(来做测试)。SciMark 2.0是NIST的用来测试科学和数值计算能力的Java基准工具。我下载了它的源码,创建了2个版本的基准测试,一个是使用基本类型,另一个使用包装类。第二个测试中我把int替换成了Integer,把double替换成了Double,这样来看包装类带来的影响。这两个版本在本文的源码中都可以找到。

Java基准测试: 源码下载

SciMark基准测试会测量许多种常见计算的性能,然后用大概的Mflops(每秒百万浮点运算数)给出一个综合的分数。因此,对这样的基准测试来说数据越大越好。表3给出了这个基准测试在我的计算机上对每个版本多次运行的平均综合分数。就像表中展示的那样,这两个版本的SciMark基准测试的运行时性能跟上面矩阵相乘的结果是一致的,基本类型的性能几乎比包装类型快了5倍。

表3. SciMark基准测试的运行时性能

SciMark版本 性能(Mflops)
使用double 710.80
使用Double 143.73

你已经见过使用自己的基准测试和一个更科学的方式对Java程序做数值计算的一些方式,但是,Java和其他语言比起来会怎样呢?看下Java和其他三种编程语言Scala,C++,JavaScript的性能比较,然后我会做出结论。

Scala基准测试

Scale是运行在JVM上的编程语言,貌似因此变得很流行。Scale有统一的类型系统,也就是说它不区分基本类型和对象类型。根据Erik Osheim在Scala的数值类型(第一部分)中说的,Scala在可能的情况下会使用基本类型,但是在必须的时候会使用对象类型(Scala uses primitive types when possible but will use objects if necessary)。与此相似,Martin Odersky对Scale数组的描述说:“Scala的Array[Int]数组对应Java当中的int[],Array[Double]对应Java当中的double[]”。

难道这意味着Scale的统一类型系统和Java的基本类型的运行时性能差不多?让我们来看一下。

Scala性能改善

当我两年前第一次使用Scala运行矩阵相乘的基准测试的时候,平均差不多要用超过33秒的时间,性能大概在Java基本类型和对象类型之间。最近我又用新版本的Scale重新编译一下,然后我被新版本的重大性能改善所震惊了。

我用Scale不像用Java那样熟练,但是我尝试把Java版本的矩阵相乘的基准测试直接转化成Scale版本。结果如下面列表3所示。当我在我的计算机上执行Scale版本的基准测试的时候,平均花费12.30秒,这个跟Java使用基本类型时候的性能非常接近。结果比我预期的要好很多,这个也给Scale声明的对数值类型的处理做了很好的证明。

Scala基准测试:源码下载

列表3. Scala语言实现的矩阵相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def multiply(a : Array[Array[Double]], b : Array[Array[Double]]) : Array[Array[Double]] =
  {
    if (!checkArgs(a, b))
        throw new IllegalArgumentException("Matrices not compatible for multiplication");
    val nRows : Int = a.length;
    val nCols : Int = b(0).length;
    var result = Array.ofDim[Double](nRows, nCols);
    for (rowNum <- 0 until nRows)
      {
        for (colNum <- 0 until nCols)
          {
            val sum : Double = 0.0;
            for (i <- 0  until a(0).length)
                sum += a(rowNum)(i)*b(i)(colNum);
            result(rowNum)(colNum) = sum;
          }
      }
    return result;
  }

代码转化的风险

就像James Roper指出的那样,当把一种语言直接转化成另一种语言的时候,总是存在风险的。因为缺少Scala的经验,使我意识到转换基准测试的代码有可能是可行的,这会强制Scala在运行时使用更高效的基本类型,同时还可以保留算法的基本特性。因为它用Java编写,所以折衷比较也是有意义的。

C++基准测试

因为C++是直接运行在物理机而非虚拟机上,大家自然会认为C++的速度比Java快。此外,为了确保索引是在数组声明的边界之内,Java会检查数组的访问,这对性能也有轻微的损害,C++不会做这样的检查(这是C++的一个特性,它可以导致缓冲区溢出,这可能会被黑客利用)。我发现,C++在处理基本的二维数组的时候多少有点尴尬,幸运的是,可以把这种尴尬隐藏到类内部的私有部分。我创建了一个简单的C++版本的Matrix类,重载了*操作符,用来做矩阵相乘,基本的矩阵相乘的算法是用Java版本直接转化过来的。列表4列出了C++的源码:

C++基准测试:源码下载

列表4.C++语言实现的矩阵相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Matrix operator*(const Matrix& m1, const Matrix& m2) throw(invalid_argument)
  {
    if (!Matrix::checkArgs(m1, m2))
          throw invalid_argument("matrices not compatible for multiplication");
    Matrix result(m1.nRows, m2.nCols);
    for (int i = 0;  i < result.nRows;  ++i)
      {
        for (int j = 0;  j < result.nCols;  ++j)
          {
            double sum = 0.0;
            for (int k = 0;  k < m1.nCols;  ++k)
                sum += m1.p[i][k]*m2.p[k][j];
            result.p[i][j] = sum;
          }
      }
    return result;
  }

使用Eclipse CDT和MinGW C++编译器可以创建调试版和正式版的应用程序。为了测试C++的性能,我是多次运行正式版取平均值。正如预期的那样,在这个简单的测试中C++很明显要快得多,在我的计算机上平均是7.58秒。如果性能是选择一个编程语言的主要因素的话,那么C++是数值运算密集型应用的首选。

JavaScript基准测试

好吧,这个测试的结果让我感到震惊。因为Javascript是一种动态语言,我本以为它的性能是最差的,甚至要比Java包装类的性能还要差。但是实际上,Javascript的性能跟Java使用基本类型的性能很接近。为了测试Javascript的性能,我安装了Node.js——它是一个以效率著称的Javascript引擎。测试的平均结果是15.91秒。列表5展示了运行在Node.js下Javascript版本的矩阵相乘基准测试:

JavaScript基准测试:源码下载

列表5. JavaScript语言实现的矩阵相乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
function multiply(a, b)
  {
    if (!checkArgs(a, b))
        throw ("Matrices not compatible for multiplication");
    var nRows = a.length;
    var nCols = b[0].length;
    var result = Array(nRows);
    for(var rowNum = 0;  rowNum < nRows; ++rowNum)
      {
        result[rowNum] = Array(nCols);
        for(var colNum = 0;  colNum < nCols;  ++colNum)
          {
            var sum = 0;
            for(var i = 0;  i < a[0].length;  ++i)
                sum += a[rowNum][i]*b[i][colNum];
            result[rowNum][colNum] = sum;
          }
      }
    return result;
  }

结论

当18年前Java第一次登上历史舞台的时候,对于以数值计算为主的应用程序从性能的角度来说,它并不是最好的语言。但时过境迁,随着其他领域技术的发展,比如即时编译(aka自适应或动态编译),当使用基本数据类型的时候,这类Java应用的性能已经可以匹敌编译成本地代码的那些语言。

并且,基本数据类型不需要垃圾回收,因此比对象类型多了另一个性能优势。表4总结了矩阵相乘基准测试在我的计算机上的运行时性能。还有其他的诸如可维护性可移植性和开发者擅长等因素让Java成为许多这类应用的很好地选择。

表4. 矩阵相乘基准测试的运行时性能

结果(以秒计)

C++ Java
(double)
Scala JavaScript Java
(Double)
7.58 11.31 12.30 15.91 48.48

就像前面讨论的那样,看上去Oracle似乎很严肃的考虑了是否在Java未来的版本中去掉基本数据类型。除非Java编译器能产生跟基本数据类型性能相当的代码,我认为把基本数据类型从Java中去掉会妨碍Java在某些类型应用中的使用,即那些以数值计算为主的应用。本文中,我对矩阵相乘做了基准测试,还用更科学的基准测试SciMark2.0来支持这一点。

附录

在本文发表在JavaWorld上几周以后,作者收到了来自Brian Goetz的邮件。Brian Goetz是Oracle的Java语言架构师,他说从Java中移除基本数据类型不在考虑范围之内。移除基本数据类型的说法源自于对Java未来版本的愿景讨论的误解或者是不准确的解释。

关于作者

John I. Moore, Jr.是Citadel的一位数学和计算机教授,他在工业领域和学术上都有很丰富的经验,在面向对象技术,软件工程和应用数学方面有独到的专长。在超过30年的时间里,他使用关系型数据库和很多高级语言来设计和开发软件,工作中广泛使用从1.1开始的Java的各个版本。他对计算机科学的很多高级话题都开设并教授了许多课程和研讨班。

了解更多:

1.Paul Krill在“Oracle的Java长期目标”写到Oracle对Java的长期的一些计划(JavaWorld,2012年3月)。那篇文章和相关的评论促使我写了这篇支持基本类型的文章。

Szymon Guz writes about his results in benchmarking primitive types and wrapper classes in “Primitives and objects benchmark in Java” (SimonOnSoftware, January 2011).
2.Szymon Guz在“Java中基本数据类型和对象类型的基准测试”(SimonOnSoftware,2011年1月)中写了对基本类型和包装类型做基准测试的结果。

3.C++编程准则和实践(Addison-Wesley, 2009)的支持站点上,C++的作者Bjarne提供了一个比本文要完善很多的矩阵类的实现。

4.John Rose,Brian Goetz和Guy Steele在“值的状态”一文中讨论了值的类型这个概念。值的类型可以被认为是没有标识的不变的用户自定义的类型集合,因此,可以把对象类型和基本类型的属性结合起来。值类型的好处是:像引用类型那样编码,像基本类型那样运行。

 | 148 views | 0 comments | 0 flags | 

jQuery的三击效果代码实现

http://www.gbtags.com/gb/share/3288.htm

大家可能常常需要在jQuery实现单机或者双击效果,是不是有时候需要三击效果呢?下面代码可以实现:

  1. $.event.special.tripleclick = {
  2. setup: function(data, namespaces) {
  3. var elem = this, $elem = jQuery(elem);
  4. $elem.bind(‘click’, jQuery.event.special.tripleclick.handler);
  5. },
  6. teardown: function(namespaces) {
  7. var elem = this, $elem = jQuery(elem);
  8. $elem.unbind(‘click’, jQuery.event.special.tripleclick.handler)
  9. },
  10. handler: function(event) {
  11. var elem = this, $elem = jQuery(elem), clicks = $elem.data(‘clicks’) || 0;
  12. clicks += 1;
  13. if ( clicks === 3 ) {
  14. clicks = 0;
  15. // set event type to “tripleclick”
  16. event.type = “tripleclick”;
  17. // let jQuery handle the triggering of “tripleclick” event handlers
  18. jQuery.event.handle.apply(this, arguments)
  19. }
  20. $elem.data(‘clicks’, clicks);
  21. }
  22. };

如何使用呢?

  1. $(“#whatever”).bind(“tripleclick”, function() {
  2. // do something
  3. }

是不是很好用? 别的地方搜刮来的代码,希望大家可以用的上!:D)

 | 184 views | 0 comments | 0 flags | 

程序的库设计

http://www.linuxeden.com/html/news/20140421/150949.html

最近在Stack Exchange上面看到一个帖子,是问程序库设计的指导原则的,“What guidelines should I follow while designing a library?”,有趣的是,很多人都在谈论面向设计,各路API设计,还有程序语言设计,唯独搜索“程序库设计”,无论中文还是英文,Google还是百度都找不到太多内容。但是我想,没有程序员会否认库设计的重要性吧,我想在这里结合这个帖子谈谈我的想法。

在这个帖子里面,votes最高的回答,提到了这样几类tips,我在下面简要叙述一下,其中基础的部分包括:

  • Pin Map,明确你期望库主要用来做什么,但不要把它定得太死,用户要可以比较方便地做出改变。
  • Working Library,一个工作的库,如果它连这点都达不到,一定要注明。没有人希望浪费时间在一个无法工作的程序库上面。
  • Basic Readme,清晰地描述库是用来做什么的,测试的情况等等。
  • Interfaces,接口必须清晰地定义,这可以帮助库的使用者。
  • Special Functions,特殊的功能,一定要注明,包括在readme文档中注明,以及在注释中注明。
  • Busy Waits,如果有一些场景需要使用busy wait(我不知道怎么翻译),其过程中可能会出现异常,使用interrupt或者其它妥善的方法来处理。
  • Comments,你做的任何的改变都要注释清楚,明确描述接口和其每个参数,方法是做什么的,又返回什么;如果有某个中间方法被调用到,就要注明。
  • Consistency,一致性,所有东西,包括注释。相关的方法要放在一个简单的代码文件里面,小但是逻辑一致。

其中的高级部分又包括Detailed Readme,Directory Structure,Licensing和Version Control。

这些都是需要注意的内容,并且大部分对于程序的库设计来说是基础要求,但是这些从重要性来说,并没有说到点上。《C++沉思录》里面有这样一句话:“库设计就是语言设计,语言设计就是库设计”,二者从先定义问题域到后解决问题的思路是类似的。我觉得比较重要的需要考虑的事情包括:

考虑库的目标用户。这听起来扯得有点泛,但实际上这是确切的问题,这是开源库还是你只是在小组内部使用的库,或者是公司内部使用的?用户的能力和需求是不一样的,要求当然不同。

要解决的核心问题。这是上文中Pin Map的一部分,不要重复发明轮子,那么每一个新库都有其存在的价值,这个问题既要通用又要具体,“通用”指的是库总有一个普适性,解决的实际问题对于不同的用户来说是不一样的;而“具体”是指库解决的问题对于程序员来说是非常清晰和直接的。例如设计一个库,根据某种规则把不同的数据类型(XML,BSON或者某种基于行的文本等等)都转换成JSON。

统一的编程风格。很多库都有自己精心设计的一套DSL,比如链式调用等等几种方式,当然,这也和使用的语言有关系。定义一种用起来舒服的编程风格对于程序库的推广是很有好处的。这也是一致性的一个体现。

内聚的调用入口。这和面向对象的“最少知识原则”有类似的地方,把那些不该暴露出去的库内部实现信息隐藏起来,在很多情况下,程序库不得不暴露和要求用户了解一些知识的时候,比如:

1
2
3
4
5
6
7
MappingConfig config = new MappingConfig();
config.put(MappingConfigConstants.ENCODE, "UTF-8");
FileBuilder fileBuilder = new StandardFileBuilder(mapping);
InputStream stream = fileBuilder.build().getInputStream();
DataTransformer<XMLNode> transformer = new XMLDataTransformer(...);
...
transformer.transform(stream);

这里引入了太多的概念,MappingConfig、FileBuilder、DataTransformer等等,整个过程大致是构造了一个数据源,还有一个数据转换器,然后这个数据转换器接受这个数据源来转换出最后结果的过程。那么:

这些象征着概念的接口和类最好以某种易于理解的形式组织起来,比如放在同一层比较浅的包里面,便于寻找;

也可以建立一个facade类,提供几种常用的组合,避免这些繁琐的对象构建和概念理解,例如:

1
XXFacade.buildCommonXMLTransformer();

向后兼容。当然,这一点也可以归纳到前文提到的一致性里面去。我曾经拿JDKHashTable举了一个例子,它的containsValue和contains方法其实是一样的,造成这种情况的一个原因就是为了保持向后兼容。

依赖管理。依赖管理很多情况下是一个脏活累活,但是却不得不考虑到。通常来说,任何一个库考虑自己的依赖库时都必须慎重,尤其是面对依赖的库需要升级的时候。如果依赖的库出了问题,自己设计的程序库也可能因此连累。

完善的测试用例。通常来说,程序库都配套有单元测试保证,无论是什么语言写的。

健全的文档组织。通常包括教程(tutorial)、开发者文档(developer guide)和接口API文档(API doc)。前者是帮助上手和建议使用的,中间的这个具备详尽的特性介绍,后者则是传统的API参考使用文档。

转自 http://blog.jobbole.com/65709/

 | 210 views | 0 comments | 0 flags |