CSK.Blog--个人原创Weblog

« AW完结,blog暂时解冻写了一个GRE单词背诵辅助程序 »

关于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

  • quote 1.water
  • 呵呵几天没上网,上来就看到你的更新了。
    转专业了没操作系统课了,哎
  • 4/22/2007 10:53:12 PM 回复该留言
  • quote 2.TonyHuang
  • 赞~~~~
    好久没有看到更新了

    我有一个别的思路,一会儿想明白了再来发
  • 4/25/2007 7:25:10 PM 回复该留言
  • quote 3.Ivordong
  • 这个题目根本不必要如此复杂,不需要
    struct task_struct * structlst[10];
    u64 tsk_start_using[10];
    这两个变量
    只要在semaphore里面在加两个变量即可。。。
  • 5/27/2007 9:15:26 AM 回复该留言
  • quote 5.Ivordong
  • 如果你只是完成Linux Kernel作业的话没有必要使用数组来解决嵌套问题,有更简洁的算法,至少我认为是没有什么BUG的(Intel的工程师也暂时没有找出破绽)
  • 5/27/2007 8:35:31 PM 回复该留言
  • quote 6.csk
  • 恩,那说下你的算法吧,不是很懂为啥不需要数组...
  • 5/28/2007 12:16:47 PM 回复该留言
  • quote 7.Ivordong
  • 你可以在上课的时候问问布置那个作业的工程师,我把算法告诉他了,也欢迎你找出BUG
  • 5/28/2007 8:28:17 PM 回复该留言

发表评论:

注意:为了有效防止SPAM,任何含有http://字样的消息会被阻止发布同时,本站仅供技术交流,请不要讨论任何政治敏感话题或者低级趣味问题。

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

日历

最新评论及回复

最近发表

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