CSK.Blog--个人原创Weblog

Saturday, April 28, 2007

决定了

长达半年的思考，今天终于想通了，今后开始走学术路线 虽然我知道自己在学术，也就是理论研究方面，做过的事为0，而且也不知道自己能不能适应。但我决定去尝试，无论道路多么艰辛。 趁着自己还年轻，应该多学一些高深的理论。 当然，我是适合搞工程的，无论今后如何，我会始终相信一切高深的理论都要经过实践的考验，世上没有那种只说不做的事。 从今天开始一切都要慢慢改变，此帖以表决心。
Tags:
发布:csk | 分类:随感 | 评论:12 | 引用:0 | 浏览:

Wednesday, April 25, 2007

写了一个GRE单词背诵辅助程序

标题没有表达清楚。情况是这样的。

相信各位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

Tags:
发布:csk | 分类:Design&Engineering | 评论:5 | 引用:0 | 浏览:

Sunday, April 22, 2007

关于linux kernel课程中semaphore计数作业

好久没写blog了啊，来篇技术点的

最近一直忙着做linux kernel的作业，难度到是不大，就是每次重新编译内核要30分钟，实在吃不消。

刚做好一个task.要求是这样的：

    • Add wait_times, wait_duration, 2 new data members into definition of data struct semaphore; Every time to wait(Sleep) for every lock being free, increase wait_times.After getting the lock, calc the wait duration and add itinto wait_duration;

    • Add use_times, use_duration, 2 new data members into definition of data struct semaphore; Every time after getting the sema, inc use_times. After releasing the sema, calc the utilization duration and add it into use_duration;
    • Use tsc to calc time;

    • Add function register_sema(struct *semaphore): Add sema_perf_list, a global var and a list_head to record all sema registered by register_sema;

    • choose a list of sema and register them before using them;

    • Export the 4 data and sema address of the registered sema list by proc;

最终要求作出的效果是在proc下导出文件semadata,显示如下内容：

#cat /proc/semadata
0xa0000000 1001 56890 2002 89765
0xa000ff00 401 6890 888 9765

-----------------------------------------

下面是我的解题思路和解决办法

关于这个问题网上也有不少的解法，其中我参考了

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中增加：

 unsigned long wait_times;
 u64 wait_duration;
 unsigned long use_times;
 u64  use_duration;

2.然后在struct semaphore中增加增加：

 struct task_struct * structlst[10];
 u64 tsk_start_using[10];

为什么增加这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

最终编译好这些代码，进入新的内核，就可以看到效果了：

starting sema dump... total: 4
0xf8c3618c 0 0 0 0
0xf8c360e8 0 0 0 0
0xf8c36044 0 0 0 0
0xf8c35fa0 27198 119425837 29922 71715898387
----------------------
 dump completed

因为只使用了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

Tags: 教程  
发布:csk | 分类:Design&amp;amp;amp;Engineering | 评论:7 | 引用:0 | 浏览:

Saturday, April 07, 2007

AW完结，blog暂时解冻

GRE战役的第一部分，analytical writting部分，在4.6日完成了，想想那一月的准备时间，虽然并没有gter上有些人说的“非人的生活”那么夸张，但的确可以使得让我不想再经历第二回。 考试好了原本打算就可以轻松下的，实则不然，回到寝室马上就准备4点的linux kernel的上机作业... 但目前还是对这学期的课云里雾里... 之前花了些时间重做了我网站封页，让他看上去正规些，大家可以去看看，今后就不打算改了。基本上做到2点，1.起到访客导航作用 2.提供一些额外的背景信息。 虽然哪些信息在我flash网站的关于部分写的很详细，但总有不少朋友会说花了不少力气才找到我的email地址这些信息... 这学期看起来不太好过，而且刚在在设计页面时候分明感觉自己已经生疏了不少...
Tags:
发布:csk | 分类:随感 | 评论:3 | 引用:0 | 浏览:
分页:[«]1[»]

Copyright Shikai Chen 2000-2012. Powered By Z-Blog(CSK Modified)