GSoC 2015 Week4

The biggest news for this week is that I’ve had my last final of this semster finished.

Well… Not many works I’ve done due to dealing with those finals. However, as the good news suggests, I’ll have more time from now on to work on. Things will be better. The tough issue ID-103 is still ahead of me.

Done

  • After lots of discussion… I’ve fixed this LDAP issue reported by Michael. Something related with LDAP was wrong, but I don’t know where it is. However, I’m pretty sure, it shouldn’t be Dashboard’s fault form the log file.

  • Discussed other issues and future works

ToDo

  • ID-88, Replace MySQL legacy stuff.

GSoC 2015 Week3

Another week of exam…

I’ve mainly done two things this week, finishing ID-89 and ID-102.

There is not much to talk about ID-102, just deleting and replacing… For ID-89, refactoring ldap.js, It’s been a long time that I noticed that operations related with ldap.js would be much slower than the ordinary. After checking the search operations, I found that the old one will use search which has baseDN of ou=users,dc=openmrs,dc=org and a filter of uid=USERNAME. Then inspired by intuition, I realized that LDAP server may highly possible first fetch all entries under baseDN and then use that filter to select the items. This would be intolerant in production, as we can directly find the entry via DN of uid=USERNAME,ou=users,dc=openmrs,dc=org.

After performing a little experimentation on my machine and proving that search with direct DN would be 1 times more faster than with filter. I rewrote all the operations in the new ldap.js. Hence, this time, the refactor doesn’t only focus on logic flow and readabilities, but also efficiency.

TODO for Next Week

  • ES6 investigation
  • Something else interesting

GSoC 2015 Week2

Well… Exam period is coming… For the sake of GPA, I have to spend lots of time on reviewing. Hence, commits were getting less.

However, goodnews is that the midterm goals are kind of easier compared to those final, and I’ve finished a lot. Currently I’m working on managing front-end dependencies by Bower, which is a npm-like package management tools. Though the task itself is rather easy, all I need to do is find the referrence and replace it, some parts of codebase of Dashboard are kind of aged with lots of deprecated code and dependencies that sometimes will confuse developer, namely me for now. So besides adorpting Bower, I’m also reviewing our code-base to filter out-dated parts which would make things easier in the future. That’s work related with ID-102

Also, I’ve been working on ID-89 as well which aims to refactor ldap.js and add tests.

To summarize:

Done:

  • Reviewed some parts of Dashboard front-end thing.
  • Refactored ldap.js and added some tests for it.

ToDo

  • Finish these tasks: ID-102 and ID-89.
  • See what I can achieve with ES6.

GSoC 2015: Week1

The first week has passed with not too many troubles, and I hope that this could last for the whole summer. :)

Though having pressure to deal with school works as well, I still managed to deliver some simple work. It’s ID-105 that concerns about creating and synchronizing the OpenMRS-ID with Talk’s account system.

Well, originally I thought this would be a simple task that only costs a few hours. However, it’s not that easy. From my work log, I can recall that I’ve spent one and a half day to get the testing environment set up. The Discourse has a paucity of documentation, like many start-up opensource projects, and it’s also a Ruby on Rails project, which is a technique I’m totally unfamiliar with. And after setting up the environment, I then used a day to mess around with its API, which turns out to be inappropriate. :/ So exhausted I am, I decided to use the brutal-force way, which is to imitate user’s login behaviour as SSO will handle the sync automatically.

Right before I deliver my PR, Robby notified me about the newly added PR convention of OpenMRS listed here. The guide suggests us to use git rebase to squash all commits into one and then make the PR. That’s indeed very thoughtful idea. It’s a pity that I only know this now. And then I wrote another script for syncing current accounts.

Anyway to sum up briefly:

What I Have Done

  • Added an auto-sync hook for TALK.
  • Wrote a script to import current accouts.

Actually…… It’s not so much that I have done. Sorry, used a few days to get familiar to development again.

GSoC 2015: New Start

Well, I’ve been luckily enough to get selected in this year’s GSoC with OpenMRS again.

I’ll continue to work on the Dashboard, to make it a better and mature platform, as the works I did last year was a rookie’s first trial. Though it has been running well for quiet a long time, there are appreicably problems remained, as mentioned here

I hope I’ll solve those problems during this summer, and present a better ID Dashboard.

OSLAB Notes4

这个实验的要求是利用linux的字符设备(char devices)创建一个类似管道(pipe)的媒介以供进程间进行通信。

我主要参考了Linux Devices Drivers, Third Edition(LDD3)这本书,有关字符设备的内容在第三章以及第六章,另外该书的源码在github上有,here。愿意深入研究的同学可以去看一下。(注意:LDD3针对的是2.6,如果使用的是3.x版本需要修改一些地方,我的Ubuntu是3.13

完成这个实验,主要需要两方面的知识,一是Linux的字符设备的相关函数,二是如何利用信号量来进行同步。省事起见,我的代码很多细节都没有考虑,完全是为了达到实验效果而写:)

字符设备

Linux将所有的外设都包装为文件来进行处理,这样能极大方便用户态的程序,使用现成的文件操作就可以与外设进行交互。为了包装成文件,需要提供相应的一些操作,如文件的打开,关闭,读写等。在内核中定义了这样的一个结构file_operations,通过其成员可以为一个文件提供各种操作,如其read成员负责着文件的读取,具体的可以参考LDD3 ch03。若为了完成本次实验的效果,只需要使用readwrite就好。

读操作函数形式为,ssize_t (*read) (struct file *, char __user *, size_t, loff_t *); 写操作函数形式为,ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *); 这里第一个参数为在内核中文件的指针;第二个参数为用户态程序提供的用来交互的buffer,我们向其中读写;第三个参数为用户态希望读写的长度;第四个则是偏移量。

在定义了我们的操作后,需要将其与设备关联起来,并且在内核中注册。设备有major number和minor number两个标号,major区分着设备的类型,而由于同一类型的设备可能有多种,需要使用minor来进行区分。这里我们不管minor,只实现一个就好。注册字符设备可以使用两种方法,LDD3上推荐使用的新方法比较麻烦,需要申请、注册、各种初始化,不表。我们使用老方法。

注册int register_chrdev(unsigned int major, const char *name, struct file_operations *fops);

注销int unregister_chrdev(unsigned int major, const char *name);

注册时可以直接硬编码一个major,但是这样可能会出现冲突等问题。我们可以令major为0,register_chrdev会为我们返回注册到的号,使用printk将其输出即可。注意,注册后并不会在文件系统中生成文件,需要另外编码,或者在用户态中使用mknod。简单起见,我们使用后者。

同步

因为多个进程要同时操作一个文件,这会带来竞争问题。我们可以使用信号量以及睡眠/唤醒机制来控制文件的同步。这里具体可以参考LDD3 ch06。

信号量

信号量semaphore,其定义在<linux/semaphore.h>内。我们只需要以下的几种操作:

初始化

1
2
struct semaphore sem; 
sema_init(&sem,1); //将sem初始化为1,即一个mutex

P操作 down_interruptible(&sem),V操作up(&sem)。(down_interruptible,故名思议,允许在函数执行时发生中断,不解释细节,下同)

睡眠/唤醒

当某资源不可用时,我们可以通过令进程进入睡眠态来阻塞进程,而后将其唤醒,这样能使得效率高一些。

唤醒的时候存在这样一个问题,我们需要知道去哪找那些睡着了的进程,也就是说需要存储下来睡眠态的进程。内核提供了wait_queue_head_t这样的一种数据结构用以存储睡眠的进程。其初始化方法为init_waitqueue_head(&que)

当我们希望一个进程睡眠时,可以使用wait_event_interruptible(que, condition)来将其放入que中以备将来唤醒。这里的condition可以是任意的表达式,其作用相当于循环中的入口条件,开始时当condition不满足时进程会进入睡眠,当其被唤醒后会再次检查condition若仍不满足会继续睡眠。这里就很迷惑了,函数是按值传递的,condition怎么还能这样用,还可以检测它变动的值?其实看源码的话会发现,wait_event_interruptible是一个宏函数,它会被展开成相应的条件循环逻辑。

换行时使用wake_up_interruptible(&que),其会将que中的所有使用wait_event_interruptible放入的进程唤醒。

制作管道

有了以上的预备知识后,也就能开始搞我们的程序了(buggy)。

为了尽量简单,我们将存储的buffer,以及等待队列等数据结构都只做一份全局的,因为我们只需要一个设备。注册模块的时候完成各种初始化以及字符设备的注册,并将注册到的major号输出出来以备使用。

具体数据结构如下,

1
struct plypy_pipe {
    wait_queue_head_t inq, outq;       /* read and write queues */
    char buffer[MAXN], *end;           /* static buffer */
    char *wp;                          /* where the data ends */
    struct semaphore sem;              /* mutual exclusion semaphore */
};

inq,outq分别用来存储读/写的进程。buffer数组用来存储数据,end是一个辅助的变量用来标记buffer的末尾。wp用来标记buffer数据的末尾,可以用来判断buffer是否为空。sem则为一个信号量。

简单起见,我们的读写逻辑是这样的。buffer中只存储一次写的数据,不支持连续写,不支持连续读。即只有在buffer为空的时候,才可以再写入下一个数据;只有在buffer中有数据的时候,才能读取数据,并且每次读取完毕后将其设为空。可以看出我们的管道只支持‘写读写读写读……’这样的操作序列,并且每次数据的传输都是从某一个写进程传向某一个读进程,并非广播。

在读写数据时,涉及到一次数据从内核到用户的传输,需要使用copy_to_usercopy_from_user两个函数来完成。

读写的流程也比较简单,不再赘述,直接看源码吧,如下:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
/**
* Create a virtual char devices
**/


#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/fs.h>
#include <linux/semaphore.h>
#include <linux/types.h>
#include <linux/wait.h>
#include <linux/cdev.h>
#include <linux/sched.h>
#include <asm/uaccess.h>

#define MAXN 1024
#define PLYPY_DEV_NAME "plypy_chrdev"


/* static int plypy_dev_open(struct inode *, struct file *filp); */
static ssize_t plypy_dev_read(struct file *, char *, size_t, loff_t *);
static ssize_t plypy_dev_write(struct file *, const char *, size_t, loff_t *);
/* static int plypy_dev_release(struct inode *, struct file *filp); */

struct file_operations fops =
{
/* .open = plypy_dev_open, */
/* .release = plypy_dev_release, */
.read = plypy_dev_read,
.write = plypy_dev_write
};

int Major;
struct plypy_pipe {
wait_queue_head_t inq, outq; /* read and write queues */
char buffer[MAXN], *end; /* static buffer */
char *wp; /* where the data ends */
struct semaphore sem; /* mutual exclusion semaphore */
};

static struct plypy_pipe plypy_pipe;
static struct plypy_pipe *dev = &plypy_pipe;

static ssize_t plypy_dev_read(struct file *filp, char __user *buf, size_t count,
loff_t *offset)

{

if (down_interruptible(&dev->sem))
return -ERESTARTSYS;

/* There may be multiple readers, so the use of loop is necessary */
while (dev->buffer == dev->wp) { /* nothing to read, wait for inputs */
up(&dev->sem);

if (wait_event_interruptible(dev->inq, (dev->buffer != dev->wp)))
return -ERESTARTSYS;
/* Loop and reacquire the lock */
if (down_interruptible(&dev->sem))
return -ERESTARTSYS;
}

/* read data */
count = min(count, (size_t)(dev->wp - dev->buffer));
if (copy_to_user(buf, dev->buffer, count)) {
/* error happened */
up(&dev->sem);
return -EFAULT;
}
dev->wp = dev->buffer;
up(&dev->sem);

wake_up_interruptible(&dev->outq);
return count;
}


static ssize_t plypy_dev_write(struct file *filp, const char __user *buf,
size_t count, loff_t *offset)

{

if (down_interruptible(&dev->sem))
return -ERESTARTSYS;

while (dev->buffer != dev->wp) { /* the old data haven't been retrieved */
up(&dev->sem);
if (wait_event_interruptible(dev->outq, (dev->buffer == dev->wp)))
return -ERESTARTSYS;
/* P and loop again */
if (down_interruptible(&dev->sem))
return -ERESTARTSYS;
}

count = min(count, (size_t)( dev->end - dev->buffer ));
if (copy_from_user(dev->buffer, buf, count)) {
/* error happened */
up(&dev->sem);
return -EFAULT;
}
dev->wp += count;
up(&dev->sem);
wake_up_interruptible(&dev->inq);

return count;
}

static int plypy_init(void)
{

plypy_pipe.end = dev->buffer+MAXN;
plypy_pipe.wp = dev->buffer;
init_waitqueue_head(&dev->inq);
init_waitqueue_head(&dev->outq);
sema_init(&dev->sem, 1);

Major = register_chrdev(0, PLYPY_DEV_NAME, &fops);
if (Major < 0) {
return Major;
}
printk(KERN_INFO "The %s is assigned major number %d",
PLYPY_DEV_NAME, Major);
printk(KERN_INFO "Use 'mknod /dev/%s c %d 0' to create a file",
PLYPY_DEV_NAME, Major);
return 0;
}

static void plypy_exit(void)
{

unregister_chrdev(Major, PLYPY_DEV_NAME);
printk(KERN_INFO "The %s is destroyed", PLYPY_DEV_NAME);
}

module_init(plypy_init);
module_exit(plypy_exit);

MODULE_LICENSE("GPL");

编译&测试

我使用的是如下的Makefile进行的测试

1
source := plypy
cdevname := plypy_chrdev
major := $(shell awk -v mod='$(cdevname)' '$$2==mod{print $$1}' /proc/devices)

ifneq ($(KERNELRELEASE),)
	obj-m:=$(source).o
else
	KERNELDIR:=/lib/modules/$(shell uname -r)/build
	PWD:=$(shell pwd)
endif
build:
	$(MAKE) -C $(KERNELDIR) M=$(PWD) modules

install:
	insmod $(source).ko
	mknod /dev/$(cdevname) c $(major) 0

remove:
	rmmod $(source)
	rm /dev/$(cdevname)

clean:
	rm modules.order Module.symvers *.ko *.o

source这里是你的源文件的名字(无后缀),cdevname是注册字符设备时使用的名字,需要通过它在/proc/devices里找刚刚我们的设备注册到的major。

在root下依次执行如下命令,编译安装模块并创建字符设备文件。

1
#make build
#make install

接下来可以用catecho来测试,开启一个终端执行#cat /dev/plypy_chrdev,在另一个终端下不断用echo写入数据,如下:

1
#echo 20 > /dev/plypy_chrdev
#echo 30 > /dev/plypy_chrdev

可以看到每次写入后,均会在cat中出现。

若要编程测试的话也比较简单,无非就是一端read,一端write

读程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h> /* O_RDWR */
#include <unistd.h> /* read/write */
#include <fcntl.h> /* open */
#define MAXN 128

char buffer[MAXN];
int main(void)
{

int fd = open("/dev/plypy_chrdev", O_RDWR);
while (1) {
printf("Read something?");
memset(buffer, 0, sizeof(buffer));
while (getchar() != '\n') /* eat it all */
continue;
read(fd, buffer, MAXN-1);
puts(buffer);
}
return 0;
}

写程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h> /* O_RDWR */
#include <unistd.h> /* read/write */
#include <fcntl.h> /* open */
#define MAXN 128

char buffer[MAXN];
int main(void)
{

int fd = open("/dev/plypy_chrdev", O_RDWR);
while (1) {
printf("Write something:\n");
memset(buffer, 0, sizeof(buffer));
gets(buffer);
write(fd, buffer, strlen(buffer)+1);
}
return 0;
}

编译后在root下执行即可。

End

就这样

OSLAB Notes3

这学期的操作系统实验基本上算是上学期操作系统课的一个延续,实验的内容上面也是。。。多有重复。。。

第一个任务就是添加系统调用,编译内核。。。上一次的笔记OSLAB Adding a system call to Linux kernel. 以下是老师的要求

为Linux内核设计添加一个系统调用,将系统的相关信息(CPU型号、操作系统的版本号、系统中的进程等类似于Windows的任务管理器的信息)以文字形式列表显示于屏幕,并编写用户程序予以验证 对于proc文件系统的相关说明,读取proc文件系统的相关信息,可考虑相应的proc编程实验

关于proc,可以参考wikipediaman proc。简要来说就是内核通过一个虚拟的文件系统,向用户空间的程序提供的一个信息交换的渠道。比如说你可以用 cat /proc/version读出你的操作系统的相关信息,实际上各种工具如uname, ps所做的事情就是读取proc文件并进行解析。

按我揣测来看,老师的意思是让我们在内核态下使用proc来读出各种各样的信息。依我愚见,这是不能完成的,因为内核是proc的提供者,而非使用者,内核态下连文件系统的概念都还没有(尚为源码,还未实现),怎么去读取。而且就算有方法读取,但是你作为提供者,为什么还要费工夫再以使用者的身份调用自己的API,多此一举。所以我把基于系统调用的和proc的分开成两个做了。

UPDATE


其实肯定是有方法可以做的,毕竟一切皆可实现,只不过是漂亮不漂亮,符不符合正常逻辑的问题。我跟指导老师谈了一下这个,老师告诉我编译的时候是没有文件系统,可运行的时候就有了,然后读文件的方法用vfs就可以。详见vfs_read(),当然还存在一些其他的函数,更底层并且更不安全。总的来说吧,合理的逻辑就是,内核提供文件以及proc等,然后各种用户态的程序再去访问它们。虽然我们可以皆由hack调用其他的函数去读取文件,但这本质上是脏的,是不符合设计哲学的,不过毕竟是实验,听老师的……有兴趣的同学可以去hack一下,我还是保留我这个方案。

另外老师要求要直接输出到屏幕上,以下的代码调用的printk生成的输出都需要通过dmesg去访问,老师说不符合要求…… printk其实是有记录级别的,就是常见的那种log level,这些level的宏定义在linux/kernel.h中。warning, error, info啊之类的,可以看一下百度百科,另外关于printk的教程在

这些记录级别其实就是一个数字,越小的越严重,在Linux运行的时候他的console有一个console log level可以通过cat /proc/sys/kernel/printk来查看,第一个数字既是。一般来说默认的应该是4(warning),那么只有小于4的可以被输出到console中。

可以通过printk(KERN_DEBUG "str")这样来明确具体输出的级别,当不声明级别的时候一般默认为KERN_WARNING(4)。为了保证输出到console,可以采用最高级别KERN_EMERG。

但是如果已经编译了内核了,再修改再编译就太蛋疼了,可以通过dmesg -n x来将其修改,我们使用5就可以显示结果了。

另外如果你在图形界面下的终端去执行的话,仍然会看不到dmesg的结果,需要切换到text console(tty1~tty6),可以通过Ctrl+Alt+Fx切换到ttyx,切换到tty7即可回到图形界面。tty会要求你登录,依次输入用户名,密码即可,接下来就跟操作终端一样了。

我编译的内核的tty给挂掉了,显示的是一个空黑屏,AskUbuntu上的这个帖子提供了解决方案,遇到同样问题的可以参考一下。

注意老师要求的是使用SYSCALL, 可以忽略proc那部分


UPDATE END

我只实现了显示内核版本,数个进程名与PID的功能。关于内核版本的查询方式,可参照/proc/version使用utsname()->release源码。 遍历所有进程可以采用如下代码(代码我是手敲的没编译,可能存在错误,下同)

1
2
3
4
5
6
#include <linux/sched.h>
struct task_struct *task;
for_each_process(task)
{
printk("%s [%d]\n", task->comm, task->pid);
}

动态模块加载

再具体实现的时候,可以先用Linux的动态模块来测试,这样就不需要说整整编译一次源码了,可以参考实验书。下面是一个最简单的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>

static int plypy_init(void)
{

printk("Loading Ply_py's module\n");
return 0;
}

static void plypy_exit(void)
{

printk("Dropping Ply_py's module\n");
}

module_init(plypy_init);
module_exit(plypy_exit);
MODULE_LICENSE("GPL");

基本上就是为自己的模块提供上init和exit函数,然后再用module_init,module_exit去注册即可,另外这里MODULE_LICENSE是一个声明许可证的宏,用GPL就行了。再添加一个Makefile,这是实验书上的。(注意Makefile是使用TAB字符进行缩进的)

1
ifneq ($(KERNELRELEASE),)
	obj-m:=plypy_mod.o
else
	KERNELDIR:=/lib/modules/$(shell uname -r)/build
	PWD:=$(shell pwd)
modules:
	$(MAKE) -C $(KERNELDIR) M=$(PWD) modules
endif

基本上这个Makefile就是切换了一下目录,然后使用了当前正在运行的内核编译模块的Makefile。然后# make,(一般#前缀表示root用户,$表示普通用户)。接下来正常的话会生成一堆文件,其中有一个plypy_mod.ko,是我们用来加载的模块。 使用# insmod plypy_mod.ko来加载,# rmmod plypy_mod.ko来卸载。 同时借助dmesg可以观察到相应的信息。

然后可以先将,之前读取内核版本以及进程的逻辑置于我们模块的init函数中做一个测试。

PROC_FS

由于proc提供的是一个虚拟的文件系统,所以我们需要将我们的信息包装成一个文件的形式,为其提供open,read等操作相对应的服务,参照fs/proc/version.c。 基本上就是为我们的虚拟文件提供了open服务。观察代码,我们可以发现,虚拟文件系统这个名字描述地非常准确,实际上这个文件在物理上并不存在(即不存在于磁盘中),每当用户请求打开文件的时候,内核才会动态生成其内容。 代码如下:

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/utsname.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/fs.h>

struct proc_dir_entry *entry;

static int plypy_proc_show(struct seq_file *m, void *v)
{

struct task_struct *task;
int i = 0;
seq_printf(m, "Kernel version: %s\n", utsname()->release);
seq_printf(m, "Processes, to name a few:\n");
for_each_process(task)
{
if (i++ > 9) break; // show only 10 processes at most
seq_printf(m, "%s [%d]\n", task->comm, task->pid);
}
return 0;
}

static int plypy_proc_open(struct inode *inode, struct file *file)
{

return single_open(file, plypy_proc_show, NULL);
}

static const struct file_operations plypy_proc_fops = {
.open = plypy_proc_open,
.read = seq_read,
.llseek = seq_lseek,
.release = single_release,
};

static int plypy_init(void)
{

printk("Loading Ply_py's module\n");
entry = proc_create("plypy", 0, NULL, &plypy_proc_fops);
return 0;
}

static void plypy_exit(void)
{

proc_remove(entry);
printk("Dropping Ply_py's module\n");
}
module_init(plypy_init);
module_exit(plypy_exit);
MODULE_LICENSE("GPL");

通过insmod加载了后,可以通过cat /proc/plypy观察结果。

SYSCALL

这个可以参照之前的那篇OSLAB Adding a system call to Linux kernel,只用把具体的函数逻辑改一改就行,如下:

1
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/sched.h>
#include <linux/utsname.h>
#include <linux/kernel.h>

asmlinkage long sys_plypy_hello(void)
{
    struct task_struct *task;
        int i = 0;
        printk("Kernel version: %s\n", utsname()->release);
        printk("Processes, to name a few:\n");
        for_each_process(task)
        {
                if (i++ > 9) break; // show only 10 processes at most
                printk("%s [%d]\n", task->comm, task->pid);
        }
    return 0;
}

就这样。

CF: Rockethon 2015

Though I’ve been coding algorithm contests since high school, when I was an OIer, and for 5 years till now. I’ve never really achieved something big in the algo contest field, due to having been lack of persistence and being distracted by other annoying things from time to time, and most of all, the limit of gift(:/). End of the sad story.

However, I’ve decided to make some changes by starting to get my color red in Codeforces. Actually you can see the story above pretty much by my rating curves

Anyway, I’ve practiced the Rockethon 2015, here are some conclusions.

A. Game:

Silly problems.

B. Permutations:

The constraint constraints will largely reduce the number of valid permutations. Let’s view this sum by the contribution each individual number made. In the largest cases, the 1 is counted n times, n-1 times for 2, n-2 times for 3… Thus, to make this happen, 1 should be placed at either end of the spots, 2 should be placed at one end of the remaining spots, and so on. Hence, there are 2^n valid sequences, and the first 2^n-1 start with 1, and others end with 1, then in these subsequences, the first half start with 2 and the second half end with 2 and so on. And so goes the way that we generate the kth lexicographical sequence.

C.

Since n is at most 5, and R is at most 10000, brute-force can be safely used. So we classify the bidders into 3, the ones that bid lower than the second price, those who bid equally, and those who bid higher. Notice that there are 2 cases, the first is that 1 highest bid and several second bids and the second is that the highest bid has the value as the second one.

To Be Updated

winter bricks

A week ago, the 5th semester of my university life had ended. It was not bad, I had new things learned, new concepts adopted, few old minds enhanced, few essential questions discovered, and maybe myself found.

Anyway, I’m sitting in my home, wondering the future, which is full of uncertainties.

Enough for the garbages, I’m not good at playing with words, especially not in my first language. Let’s note something real, those bricks that I, a hard-working brick-carrier, want to carry this winter.

The emacs adventure

While I was working on the OpenMRS-ID project, my once trusty editor Sublime Text 2 went broken. It just goes freeze from time to time and made me angry. Few months ago, I had a thought about trying to learn emacs. However, being scared about the complexity of ‘the Emacs Operating System’, and satisfied what I had in ST2, I forgot this gradually.

But as my ST2 went down, ‘We shall all be crazy once in a while, and it’s the perfect time to be crazy’, I thought. So I decided to give emacs a try, and downloaded it, and began to read the tutorial. ‘Oh WTF…’ There were just so many C-key and M-key keystrokes to memorize. As a VIM-like keybinding user, I cannot feel even slightly confortable with it, however, those emacs packages, like ORG-mode, are so attractive. So I googled ‘emacs + vim keybinding’.

Well, the first interesting page bumped out was this SO question, Why don’t more people use emacs with viper-mode? [closed]. There few funny words in the answer accepted,

Because you are either a vi person or an emacs person. The same way you’re either a dog person or a cat person.

And, anyway, emacs with its strange command sequence like

CTRL META LEFTSHIFT RIGHTSHIFT WINDOWS OPENAPPLE ALT K

is better suited to aliens with 87 fingers, or elite pianists :-)

However, I found the Evil package, like those other vim add-ons on other IDEs/editors. It was amazing, just amazing.

Ah, finally the Emacs OS get a good editor, evil.

The adventure so far was fun, I’m still learning the Emacs Operating System.

The Rasberry Pi OS

As we’ve learnt OS this semester, so I want to try my skills. And by suggestions of one my older fellow student(Xue Zhang). I dived into the Baking Pi online course provided by Cambridge University. Well, I was f##ked… it has nothing to do with modern OS development, but merely some low-level programming with ARMv6 assembly.

Anyway, it’s still somehow interesting, and I’ve put my works here.

Other bricks

  • The network and SDN stuff
  • Concrete Mathematics ( Bible of brick-carrying )
  • Coursera courses
    • Yale’s Introduction to Classical Music
    • NTU’s Machine Learning Techniques ( A lot to catch up… )
  • Literature
    • Love in the Time of Cholera ( El amor en los tiempos del colera )
    • A Tale of Two Cities ( And other Charles Dickens books I bought )
  • Some real OS stuff ( minix maybe? )

This will be an fulfilling summer, at least the plan is…

OSLAB notes 2

This time, we are asked to play with the fork(), signal(), kill() and some other POSIX APIs related with process control and communication.

Fork and pass signal

The first task is to use fork to create 2 child-processes and then use soft interrupt (signal) to make interprocess communication.

Fork

Well, first of all you need to create 2 child-processes. And how to achieve that, this?

1
2
pid1 = fork();
pid2 = fork();

Well, young man, you’re simply naiveeee.

Before making further explanation, you’d better run this code yourself.

1
2
3
4
pid_t pid1, pid2;
pid1 = fork();
pid2 = fork();
printf("The father %d created, pid1: %d \t pid2: %d\n", getpid(), pid1, pid2);

The output goes like this,

The father 6281 created, pid1: 6282     pid2: 6283
The father 6282 created, pid1: 0        pid2: 6284
The father 6284 created, pid1: 0        pid2: 0
The father 6283 created, pid1: 6282     pid2: 0

Strange, huh? There is 4 processes created, rather than 3 that we expected; and the child process 6282 has also created one process 6284.

Well, let’s explain this. The fork will create a duplicate of the running process, and the process created will be the child of the original process. Since the child is a replica, it will have the same local variables ,same PC(program counter) and a bunch of other stuff you may see its man page for details.

See the child and the parent processes are almost identical, the child will have the same PC as the parent’s, which means, it will continue to execute the code after where fork is called. And that is the reason of the “wrong” behavior we have above. The execution flow goes like this.


  1. Parent 6281 created child 6282, then 6281 & 6282 will continue to execute pid2 = fork()
  2. 6281 created another child 6283, while child 6282 also created one child of its own, 6284.

Then how shall we distinguish the child and the parent? Notice that some pids are 0. After fork returned the child and the parent will receive 2 different value. The parent will get the pid of its child, meanwhile the child will have a 0. Also -1 for failed duplicate. And we can work on that.

Signal and Kill

In this task, we used software interrupt to achieve interprocess communication. That is, one process listen for a specific signal (interrupt) and then the other one send that signal. These are done by signal and kill respectively.

The signal(signum, handler) will bind the specified signal with id signum with the handler function handler. And kill(pid, sig) will send signal sig to process pid.

Design

Then everything is simple, as the task asked us to let the parent listen for keyboard interrupt and then send signal to kill the children. We shall simply let the parent listen to the SIGINT, and then bind a handler function that will send signals to the 2 children, the children then wait for the signals to commit suicide.

However, there are few things to note.

Notes

The guide provided is… well, it made few mistakes. Only on some specific OS the break and delete will generate the SIGINT, mostly it’s for Ctrl+c. And since we are using SIGINT, it’s vital to overwrite the orignal handler for it. Or it will cause the processes to terminate, though the outcome is same, it’s not what we want.

All in all, it’s my code below.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/**
* Author: Ply_py
* OSLAB: fork and signal passing
*/

#include <stdio.h>
#include <signal.h>
#include <unistd.h>
#include <sys/types.h>
#include <stdlib.h>

void killer(int);
void suicide(int);

pid_t pid1, pid2;

int
main(int argc, int *argv[])
{

// make all process of this group ignore the normal soft interrupt
signal(SIGINT, SIG_IGN);
// create child process 1
while (-1 == (pid1 = fork())) continue;

if (pid1 > 0) { // parent
// create child process 2
while (-1 == (pid2 = fork())) continue;

if (pid2 > 0) { // parent
printf("Parent: %ld\t Child1: %ld\t Child2: %ld\n",
(long) getpid(), (long) pid1, (long) pid2);

signal(SIGINT, killer);
// wait for death of 2 children
wait(0);
wait(0);
puts("The parent has killed his children");
exit(EXIT_SUCCESS);
} else { // child 2
printf("child 2: %ld created\n", (long) getpid());
signal(16, suicide);
while (1) sleep(5);
}

} else { // child 1
printf("child 1: %ld created\n", (long) getpid());
signal(17, suicide);
while (1) sleep(5);
}
printf("I, %ld can get here\n", (long) getpid());
}

void
killer(int signum)
{

static counter = 0;
printf("process %ld catching signal %d\n", (long) getpid(), signum);
if (0 == counter) {
kill(pid1, 17); // kill child 1
} else {
kill(pid2, 16); // kill child 2
}
++counter;
}

void
suicide(int signum)
{

printf("Process %ld is committing suicide, by signal %d\n",
(long) getpid(), signum);
exit(EXIT_SUCCESS);
}

Pipe

The task 2 demand us to implement another interprocess communication via pipe.

Well it’s rather easy, as we already got here. Use pipe to create a communication tunnel, and use that to pass messages. But notice there are 2 process writing to that pipe concurently, so proper lock is needed. Check lockf.

Code here,

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
* Author: Ply_py
* OSLAB: pipe
*/

#include <unistd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>

#define BUF_SIZE 105
pid_t pid1,pid2;

int
main(int argc, char const *argv[])
{

int fd[2];
// fd[0] dest, fd[1] source
char in_buf[BUF_SIZE];
char out_buf[BUF_SIZE];

if (-1 == pipe(fd)) {
perror("pipe");
exit(EXIT_FAILURE);
}

while (-1 == (pid1 = fork())) continue;

if (0 == pid1) {//child1
lockf(fd[1], F_LOCK, 0);
sprintf(out_buf, "\nChild process 1 is sending a message\n");
write(fd[1], out_buf, BUF_SIZE);
lockf(fd[1], F_ULOCK, 0);
exit(EXIT_SUCCESS);
} else {
while (-1 == (pid2 = fork())) continue;

if (0 == pid2) {// child2
lockf(fd[1], F_LOCK, 0);
sprintf(out_buf, "\nChild process 2 is sending a message\n");
write(fd[1], out_buf, BUF_SIZE);
lockf(fd[1], F_ULOCK, 0);
exit(EXIT_SUCCESS);
} else { // parent
read(fd[0], in_buf, BUF_SIZE);
puts(in_buf);
wait(pid1);
read(fd[0], in_buf, BUF_SIZE);
puts(in_buf);
wait(pid2);
exit(EXIT_SUCCESS);
}
}
return 0;
}