标题没有表达清楚。情况是这样的。
相信各位G友都看过杨鹏写的《17天搞定GRE单词》,说来惭愧,我可能算是进度很慢的了,现在还没搞定红宝书...
这本书实际上就是对艾宾浩斯记忆曲线的应用,每当新背诵一批word list以后,应当在今后的1、2、4、7、15天后复习,以达到最快且最佳的背诵效果。但我不是什么聪明的人,我不可能记住每天背诵的list应当何时是最佳复习时间。当然我可以按照杨鹏书上说的那样列一个表格。
但这样十分不灵活,比如很有可能某天我要忙着做其他事情,导致当日任务无法完成,从而整个表格就要变动。而且我也懒得去列这个表格。
作为一名CS学生,这类事情应当动动脑子写个程序了,所以就有了这个东西。
下面是他的截图:
这是一个用asp写的程序,作用是按照设定,它可以告诉你每天需要复习和新背诵的wordlist。同时会提示你某项list是处于第几轮复习状态。
如果当天完成了某个项目,可以点"proceed"通过,如果没有点击,则系统自动安排顺延。
你可能会说这年头这种程序不是多得是吗?的确,我写这个东西还有个目的,就是可以使用手机访问。这样不用天天开那个电脑...因此在我上课或自修时候,先用手机登陆网站核对下任务就可以开始学习了。而且也是为了锻炼写程序....
如果你对这个程序感兴趣,不妨用我给出的代码作一定修改。
只需要asp支持,算法写的很傻,不用去研究了
在第一次使用时候,将代码line 151的注释
'init_conf 51,3,8
去除注释。这个函数表示初始化配置文件,第一个参数表示总共的word list数,第二个是每天新背诵的word list数,第三个暂时没有实现,是最多的任务条目,我觉得这个参数还是不去处理为好
这个设定就是杨鹏书上推荐的做法,当然你可以按照你的喜好设定。同时稍微修改代码,就可以从你当前背诵的进度开始执行任务了。不过我比较懒,宁愿从头开始背...
好了,废话就写这么多,如果这个程序能对你派上用场。不妨留言告诉我,我会很开心~
下载地址:
http://www.csksoft.net/data/legacyftp/Products/code_and_lib/src_gre_tracer.rar
最近一直忙着做linux kernel的作业,难度到是不大,就是每次重新编译内核要30分钟,实在吃不消。
刚做好一个task.要求是这样的:
最终要求作出的效果是在proc下导出文件semadata,显示如下内容:
-----------------------------------------
下面是我的解题思路和解决办法
关于这个问题网上也有不少的解法,其中我参考了
http://bbs.ss.pku.edu.cn/ss/index.php/6122/action_viewspace_itemid_9362.html
的办法,不过其中也有不少问题,所以我把我的修正点和不同的做法写出,一些基本的做法就看上文的链接
好了,下面说我的具体做法
1.在semaphore.h中增加4个规定的变量
由于要求用rdtsc指令记录时间,所以采用rdtscll宏,这个宏实质就是wrap了x86的rstsc指令,返回一个64bit的数据记录CPU的clock数
所以我用u64类型(unsigned long long)记录use_duration和wait_duration
1.在struct semaphore中增加:
2.然后在struct semaphore中增加增加:
为什么增加这2个成员呢?考虑到同一个semaphore在用一个时刻可以被不同process调用(执行down() ),所以考虑到需要记录不同process使用该semaphore的开始时间。
intel给我们的tips要求的是在task_struct中增加一个u64 start_time[10];
他的思路正好和上面的办法颠倒,是让每个task记住自己使用一个semaphore的开始时间。
同时因为考虑到一个process可以嵌套的调用很多semapore。
比如:
processA:
Down(sema1);
//some codes
Down(sema2);
//some codes
Up(sema2);
Up(sema1);
这样一来必须记录每个semaphore的开始时间。然后用一个int pos来跟踪嵌套调用down()的深度(好比是堆栈指针)
但是这也有个问题(多谢xris提醒)
考虑下面的调用顺序:
processA:
Down(sema1);
//some codes
Up(sema2);
Down(sema2);
//some codes
Up(sema1);
每个semapore是交错调用的,这样用前面stack数据结构来记录肯定失效了
所以我原先的做法是在task_struct中加入下面2个成员:
u64 start_time[10];
struct semaphore * used_sema_handle[10];
这样一来就能解决上面的问题,但是要求每次先从used_sema_handle里面找到对应semaphore的下标,然后在操作上面的start_time数组。
(用10个元素只是近似情况。同时这个办法也有问题,比如同一个semaphore可以连续down();2次,这样这个方法也实效,如果你有更好的办法欢迎告诉我)
那么为什么我最终没有修改task_struct而是在semaphore里面加了2个对应的变量呢?
那只是因为之前这个办法编译没有通过,提示task_struct在semaphore.h中是unreferenced (我还是不太习惯gcc,没办法,汗...),所以只好在struct semahore里面加2个对应的变量,可以起到同样效果
3.在semahore.h中增加下面函数:
static inline void reg_and_settime (struct semaphore *sem, u64 qw_start)
{
struct task_struct *tsk = current;
int npos = 0;
for (;npos < 10;npos++)
{
if (sem->structlst[npos] == NULL)
{
sem->structlst[npos] =tsk;
sem->tsk_start_using[npos] = qw_start;
break;
}
}
}
static inline u64 rm_and_rdtime (struct semaphore *sem)
{
int npos = 0;
struct task_struct *tsk = current;
for (;npos < 10; npos ++){
if (sem->structlst[npos] == tsk)
{
sem->structlst[npos] = NULL;
return sem->tsk_start_using[npos];
}
}
return 0;/* oops~ not found */
}
这2个函数就是操作那对structlst和tsk_start_using成员的,reg_and_settime将当前的task指针记录到structlst,并找到一个位置存放此时的start_time。rm_and_rdtime则将当前task对应的start_time读出,然后把自身记录抹去。具体就不解释了
4.在down,down_interruptible,down_trylock加入下面代码:
u64 qw_start_time;
sem->use_times++;
rdtscll(qw_start_time);
reg_and_settime(sem,qw_start_time);
5.在up中第一行加入:
u64 qw_current_time,qw_start_time;
rdtscll(qw_current_time);
qw_start_time = rm_and_rdtime(sem);
if (qw_start_time != 0){ /* ensure the process invoked down before this up*/
sem->use_duration += qw_current_time- qw_start_time;
}
6.按照参考文章的办法修改lib/semaphore_sleeper.c。以及为了修改fs/proc/proc_misc.c所作的所有操作
7.在proc_misc.c中,修正参考文章的问题
unregister_sema修改为:
int unregister_sema(struct semaphore *sema)
{
int ret;
ret = 0;
struct list_head *pos;
struct list_head *next;
struct list_head *prev;
struct semaperf_list *psema;
pos = container_of(sema, struct semaperf_list, sema_list);
__list_for_each(pos, &g_semaperf_head.sema_list)
{
psema = container_of(pos, struct semaperf_list, sema_list);
if (psema->semaperf == sema)
{
next = pos->next;
prev = pos->prev;
__list_del(prev, next);
kfree(psema);
--g_regist_count;
}
}
return ret;
}
原文的办法,通过container_of宏查找semaphore *所在的struct semaperf_list指针是行不通的,这样只会造成调用该函数访问空地址,造成内核崩溃,当然我的修改也很愚蠢...
get_semaperf_list中的显示函数的打印语句改为:
length += sprintf(buffer, "0x%x %ld %llu %ld %llu\n", (unsigned int)psema->semaperf,
psema->semaperf->wait_times,
psema->semaperf->wait_duration,
psema->semaperf->use_times,
psema->semaperf->use_duration);
strcat(page, buffer);
这个不用多做解释,use_duration这些是u64的
8.编写module
写module有2个功能
1).通过module创建n个semaphore,然后调用register_sema,以便显示
2).提供能够由ring 3的程序调用的down和up
其中第一个功能很容易实现,第二个很明显就是要用systemcall。但是这是一个module,不可能通过常规手段修改内核代码添加systemcall(除非你把这2个systemcall编译进内核)
我采取的办法是在module启动时候获取IDRT向量表,然后找到system call的int 80表向,最终找到system_call数组表,然后动态替换2个无用system_call实现增加systemcall的手段(对了,就是流氓软件hook system call的办法)
module的代码很长,我把它附在文章的末尾
9.编写测试程序调用module提供的systemcall
下面是我写的程序:
int main(void)
{
while(1)
{
syscall_sema_dw(0); //enter critical region
usleep(500); //sleep for 500 milliseconds
syscall_sema_up(0); //leave critical region
usleep(200);
}
}
把程序编译为mutex_racer,然后同时执行2个该程序。可以看成使对一个critical_region的访问操作。
其中syscall_sema_dw和syscall_sema_up是module提供的systemcall,参数0表示使用module创建的第一个semaphore
最终编译好这些代码,进入新的内核,就可以看到效果了:
因为只使用了1个semaphore,所以前3项都是0
好了,到此任务大功告成,当然你也可以写其他的测试程序,比如模拟PV操作看效果。
最后附上我写的module代码:
/*
Semaphore debug helper module
BY CSK
csk@live.com
*/
#include<linux/kernel.h>
#include<linux/module.h>
#include<linux/init.h>
#include<linux/unistd.h>
#include<asm/uaccess.h> // for copy_to_user
#include<linux/sched.h> // for current macro
#include <linux/sema_helper.h>
/* index 223 and 285 is not used in kernel 2.6.20.3 */
#define __NR_HELPER_SEMA_UP 223
#define __NR_HELPER_SEMA_DW 285
long * systable; /* location to store system_call_table */
static int (*saved_223)(void);
static int (*saved_285)(void);
#define HELPER_SEMA_NUM 4
static struct semaphore pSema_lst[HELPER_SEMA_NUM];
/* init semaphore */
static void init_env()
{
int pos = 0;
/* init each sema */
for (;pos<HELPER_SEMA_NUM ; pos++)
{
sema_init(pSema_lst + pos , 1); //mutex-style sema
memset(pSema_lst[pos].structlst,NULL,10*sizeof(struct task_struct *));
register_sema(pSema_lst + pos);
}
}
static void release_env()
{
int pos = 0;
for (; pos<HELPER_SEMA_NUM; pos++)
{
unregister_sema(pSema_lst + pos );
}
}
/* new syscall */
asmlinkage int helper_down_sema(int sema_id)
{
//struct timeval ktv;
//do_gettimeofday(&ktv);
//copy_to_user(tv,&ktv,sizeof(ktv));
down(pSema_lst + sema_id );
// printk(KERN_ALERT"<helper_down_sema>PID %ld called ,with value %d.\n",(long)current->pid,sema_id);
return 0;
}
asmlinkage int helper_up_sema(int sema_id)
{
//struct timeval ktv;
//do_gettimeofday(&ktv);
//copy_to_user(tv,&ktv,sizeof(ktv));
//printk(KERN_ALERT"<helper_up_sema>PID %ld called ,with value %d.\n",(long)current->pid,sema_id);
up(pSema_lst + sema_id);
return 0;
}
/* Begin hacking code ;-) */
//IDTR
struct {
unsigned short limit;
unsigned int base;
} __attribute__((packed)) idtr;
// IDT
struct {
unsigned short off1;
unsigned short sel;
unsigned char none, flags;
unsigned short off2;
} __attribute__((packed)) idt;
// find the address of sys_call_tb
void disp_sys_call_table(void)
{
unsigned int sys_call_off;
unsigned int sys_call_table;
char* p;
int i;
asm("sidt %0":"=m"(idtr));
printk("addr of idtr: %x\n", &idtr);
memcpy(&idt, idtr.base+8*0x80, sizeof(idt));
sys_call_off=((idt.off2<<16)|idt.off1);
printk("addr of idt 0x80: %x\n", sys_call_off);
p=sys_call_off;
for (i=0; i<100; i++)
{
if (p[i]=='\xff' && p[i+1]=='\x14' && p[i+2]=='\x85')
{
sys_call_table=*(unsigned int*)(p+i+3);
systable = (long *)sys_call_table;
printk("addr of sys_call_table: %x\n", sys_call_table);
return ;
}
}
}
/* end of hacking code ;-) */
int syscall(void)
{
/* init semaphore data */
init_env();
/* start kernel hacking! */
disp_sys_call_table();
//save old entiry before replace
saved_223=(int(*)(void))(systable[__NR_HELPER_SEMA_UP]);
saved_285=(int(*)(void))(systable[__NR_HELPER_SEMA_DW]);
//ok, replace them
systable[__NR_HELPER_SEMA_UP]=(unsigned long)helper_up_sema;
systable[__NR_HELPER_SEMA_DW]=(unsigned long)helper_down_sema;
return 0;
}
void exit_syscall(void)
{
release_env();
//save back
systable[__NR_HELPER_SEMA_UP]=(unsigned long)saved_223;
systable[__NR_HELPER_SEMA_DW]=(unsigned long)saved_285;
}
module_init(syscall);
module_exit(exit_syscall);
-----------------------
写的虎头蛇尾,如果觉得哪里不正确欢迎指出
CSK 2007-4-22