距離上次分享Linux container相關文章已經五年多了, 沒想到五年後居然有人用Linux container搞出了大名堂, 是的, 就是Docker!  最近越來越常聽到大家在討論Docker, 但是也很常聽到有人在問Docker跟VM到底哪裡不同.

舉個例子來說明:

在以前如果想要在同一台電腦上面同時虛擬化AP server + APP, DB, Mail server applications, 我們需要在Hosting OS上面跑三個VM instances (如下圖左邊的VMs), 每一個VM instance雖然只執行各自被指派的任務 (如下圖左邊填滿橘色, 綠色, 灰色的部分), 但是從OS層來說卻是在同一台實體機器上執行了四份OS, 相同的libraries被重覆載入四次 (如下圖左邊藍色的部分), 所以記憶體, CPU等資源等於浪費了.

有了Container (如下圖右邊的Containers)我們就不需要浪費資源在各application共用的部分, 下圖右邊的Containers所要表現的就是我們不再需要為了執行虛擬化的application而重複地在各個虛擬環境中執行OS, 各虛擬環境透過使用Hosting OS已經載入過的libraries替我們節省實體機器上的資源, 當然, 這只是眾多優點中的一個而已.

另外一個優點就是透過maintain Dockerfile (點我看sample)能幫助我們更清楚地知道每個application的環境是如何建立出來的, 包含需要安裝哪些套件, 需要先設定什麼樣的參數與執行什麼樣的指令.  

Dockerfile中可以reference既有的docker image讓我們動態且快速的調整出不同情況下所需的虛擬環境, 而且Dockerfile很小的文字檔, 需要的人很快就可以取得並在自己的環境把image build出來, 而不需要隨便就傳個幾GB的流量.

概念上的說明進行到這裡就好, 關於Docker的基本設定+使用google已經提供很多資訊了, 下面是我實際設定+使用過程中預到的問題以及小筆記:

// ssh connection closed by remote
http://stackoverflow.com/questions/18173889/cannot-access-centos-sshd-on-docker

// unable to run firefox from docker

http://www.torkwrench.com/2011/12/16/d-bus-library-appears-to-be-incorrectly-set-up-failed-to-read-machine-uuid-failed-to-open-varlibdbusmachine-id/

// configure docker to use devicemapper rather than aufs (某些application需要在devicemapper模式下才能在docker中執行, eg. DB2)
https://gist.github.com/pcolazurdo/e61cfb84812a70b93e74
umount -l $(grep 'aufs' /proc/mounts | awk '{print $2}' | sort -r)
rm -rf /var/lib/docker
vi /etc/init.d/docker
touch /var/lib/boot2docker/profile
在profile中加入
#!/bin/sh
EXTRA_ARGS="--storage-opt dm.basesize=20G --storage-driver=devicemapper"

// create local docker registry (for local push/pull, 如果想讓開發測試團隊在內網就能夠分享docker images, 自己建個docker registry是個不錯的選擇)
http://cloudcounselor.com/2014/01/07/docker-private-registry-on-centos-rhel-6-5/

// private docker-registry
yum install -y docker-registry
default port: 5000
default repository location: /var/lib/docker-registry
編輯/var/lib/boot2docker/profile:
EXTRA_ARGS="--storage-opt dm.basesize=40G --storage-driver=devicemapper --insecure-registry localdocker:5000"
編輯/etc/hosts:
{intranet IP} localdocker
編輯/etc/hosts後要重啓docker:
/etc/init.d/docker stop
/etc/init.d/docker start
push to private docker-registry: docker push localdocker:5000/{repository}:{tag}
pull from private docker-registry: docker pull localdocker:5000/{repository}:{tag}

// docker-registry rest api (用來管理local docker registry裡的docker images+版本)
https://docs.docker.com/reference/api/registry_api/#delete-a-repository-tag
eg. get tags of mydb2:
GET http://localdocker:5000/v1/repositories/library/mydb2/tags
eg. remove ssosdpbase tag from db2-trinity:
DELETE http://localdocker:5000/v1/repositories/library/mydb2/tags/base
remove repository:
DELETE http://localdocker:5000/v1/repositories/mydb2

tar + exclude

長久以來都是整個目錄tar起來，還沒有真的用過exclude功能，嘗試了一下之後發現exclude除了要帶路徑之外還要再加上個*，不然想exclude的路徑一樣會被tar起來。

這樣子是不會work2的：
tar czf auto_import.tar.gz --exclude="auto_import/csv_files/" --exclude="auto_import/tmp_csv/" auto_import

這樣子才對：
tar czf auto_import.tar.gz --exclude="auto_import/csv_files/*" --exclude="auto_import/tmp_csv/*" auto_import

山不轉路轉

上一篇寫到要如何用Network Namespaces + Vconfig來做到只用一台電腦與一張PCI網卡就可以監控使用相同IP網段的多個VLAN，結果發現從獨立namespace發出帶有VLAN ID的封包始終無法成功的送到網路上，經過整整一個星期的思考，在iptables & ip route之間穿梭，卻找不到一個可以把封包丟出去的方法。。。
在我勤奮不懈的努力之下，洗澡的時候忽然有個"Multiple routing table"的想法閃過腦中，於是踏出浴室之後馬上google Linux是否有這種東西＆要怎麼用，話說天救自救者，就這樣給我試出來了，哇哈哈哈！

有興趣的人可以用下面的script試一下：

+--NS2:------------------------------------------------

./ns_exec -nm -- /bin/bash
echo $$

+------------------------------------------------------

+--NS3:------------------------------------------------

./ns_exec -nm -- /bin/bash
echo $$

+------------------------------------------------------

+--NS1:------------------------------------------------

ip link add type veth
ip link add type veth

ip link set veth1 netns 1691
ip link set veth3 netns 1704

ifconfig veth0 192.168.0.1/24 up
ifconfig veth2 192.168.2.1/24 up

vconfig add eth0 11
vconfig add eth0 33

ifconfig eth0.11 10.0.0.11/24 up
ifconfig eth0.33 10.0.0.33/24 up

echo 1 > /proc/sys/net/ipv4/ip_forward
echo 1 > /proc/sys/net/ipv4/conf/eth0/proxy_arp

ip rule add from 192.168.0.2 lookup 102
ip rule add from 192.168.2.2 lookup 122

ip route add default via 10.0.0.11 dev eth0.11 table 102
ip route add default via 10.0.0.33 dev eth0.33 table 122

+------------------------------------------------------

+--NS2:------------------------------------------------

ifconfig veth1 192.168.0.2/24 up
ip route add default via 192.168.0.1 dev veth1

+------------------------------------------------------

+--NS3:------------------------------------------------

ifconfig veth3 192.168.2.2/24 up
ip route add default via 192.168.2.1 dev veth3

+------------------------------------------------------

+--NS1:------------------------------------------------

tcpdump -ne -i eth0 not port 22

+------------------------------------------------------

tcpdump擷取到的封包資訊：

[root@vmf11 ~]# tcpdump -ne -i eth0 not port 22
tcpdump: verbose output suppressed, use -v or -vv for full protocol decode
listening on eth0, link-type EN10MB (Ethernet), capture size 96 bytes
10:51:41.882589 00:0c:29:56:fb:d3 > Broadcast, ethertype 802.1Q (0x8100), length 46: vlan 11, p 0, ethertype ARP, arp who-has 10.0.0.10 tell 10.0.0.11
10:51:42.326170 00:0c:29:56:fb:d3 > Broadcast, ethertype 802.1Q (0x8100), length 46: vlan 33, p 0, ethertype ARP, arp who-has 10.0.0.10 tell 10.0.0.33

看到了嗎？
問相同IP地址的封包被加上不同的VLAN ID了！

Linux Container (Network Namespaces) + 802.1q (vconfig) + screen

今天要作筆記的對象是Virtual VLAN interface，虛擬化已經從最早的虛擬電腦（Vmware/Virtual PC/Qemu/Virtual box/Xen/KVM...etc）演進到虛擬switch（Virtual route forwarding enabled switch），虛擬的的Network interface其實也存在好一陣子（eg. IP alias），不過虛擬的VLAN interface倒是很少見。
雖然在2004年有人寫了個linux-vrf的patch，讓我們在Linux下可以透過chvrf這個工具指定某個process要透過哪張虛擬的VLAN interface對外丟封包，只不過該patch只支援到2.6.8版的Linux kernel（等同於Fedora Core2時代），那麼新版的Linux用戶該怎麼辦呢？沒關係，待我細細道來。
首先要先介紹Linux Container＆802.1q support in Linux kernel。
簡單來說Linux Container是用來讓每個process有獨立的作業空間，這裡我們只用到獨立network interface的功能，802.1q support in Linux kernel則是讓使用者有能力創建支援VLAN tag的network interface，因此把這兩個功能相加之後便可以達到虛擬VLAN interface的功能，下面兩個連結有更詳盡的說明與tutorial：
Linux Container
Linux Container configuration guide中所提到的ns_exec工具可以用下面指令取得：
git clone git://git.sr71.net/~hallyn/cr_tests.git
802.1q support in Linux kernel


看完上面兩個連結之後，我們知道怎麼為各作業空間建立獨立的virtual network interface，也知道怎麼建立能夠發出帶有VLAN tag封包的virtual network interface，但是，如果我們想要用一台主機跟多個VLAN裡面的設備溝通時該怎麼辦呢？
答案就是在建立完veth之後再用vconfig在veth上面另外長個VLAN tag enabled network interface！
設定可以參考下面的script，這個例子用到screen來達到完全自動化（while-loop裡面可以再改進），在一般bash shell下執行script，而script中使用screen -X下達指令的對象為另一個bash shell中的screen，而兩個bash shell都必須使用root登入：

echo 1 > /proc/sys/net/ipv4/ip_forward

echo 1 > /proc/sys/net/ipv4/conf/eth0/proxy_arp

ip link add type veth

ifconfig veth0 192.168.0.101/24 up

route add -host 192.168.0.102 dev veth0

echo 1 > /proc/sys/net/ipv4/conf/veth0/proxy_arp



screen -X stuff './ns_exec -nm -- /bin/bash'

screen -X eval 'stuff "\015"'

sleep 1

screen -X stuff 'echo $$ >> pid'

screen -X eval 'stuff "\015"'



val=1;

while read line

do

        echo $val $line;

        veth=veth$val;

        ip link set $veth netns $line;

        #cmd='ifconfig veth1 192.168.0.102/24 up';

        #echo $cmd;

        #screen -X stuff $cmd;

        screen -X stuff 'ifconfig veth1 192.168.0.102/24 up';

        screen -X eval 'stuff "\015"'

        screen -X stuff 'vconfig add veth1 11';

        screen -X eval 'stuff "\015"'

        screen -X stuff 'ifconfig veth1.11 10.0.0.1/24 up';

        screen -X eval 'stuff "\015"'

        screen -X stuff 'ip route add default via 192.168.0.102 dev veth1';

        screen -X eval 'stuff "\015"'

        val=`expr $val + 2`;

done < "pid"



echo finish startup

Tomcat & /etc/hosts

今天終於解決了一樁千古懸案 --> 啟動Tomcat之後就無法關閉。
之前一直以為是客戶IT的機車firewall規則造成的，後來在以色列同仁詢問我無法啟動Tomcat的原因時一並附上的error log中找到了關鍵字"Cannot assign requested address"，上google搜尋之後發現原來是/etc/hosts沒有設定好（因為之前主機換地方所以IP也換了，但是忘了改/etc/hosts）。
至於完整解得請參考這裡

Design Database with Dia

Dia可以用來model database不稀奇，用UML模式即可。
用Dia model好的database可以自動變成SQL指令就希奇了！
是的，今天要介紹的就是使用Dia model好database之後要如何自動產生SQL指令。
在這個不景氣的時代能省則省，一切從簡，因此我決定直接hot link別人寫好的tutorial，如下：
Database Design with Dia
Tutorial中提到的tedia2sql可以從這裡下載。

tedia2sql的安裝說明只提及使用apt安裝dependency的package名稱，若透過fedora 9的yum可以使用下列指令安裝：
yum install perl-XML-Parser-2.36-3.fc9.i386 perl-libxml-perl-0.08-7.fc9.noarch perl-XML-RegExp-0.03-4.fc9.noarch perl-XML-DOM-1.44-4.fc9.noarch

最後要注意的是在tutorial中的associate符號其實並不是UML的association building block，其實那只是一般用方塊代替箭號的直線！如果真的用association building block就會在產生SQL指令時出現警告訊息，當然不會有SQL指令了。

天殺的SELINUX

雖然SELINUX已經存在各Linux disto中很久了，但是以前在使用Debian/Ubuntu時從來沒有用過它，應該說從來沒有裝過它！因此對它的實際功能不是很了解，只約略知道它是加強安全性的一個核心套件而已。雖然大部分的distro把他列為optional套件，但Red Hat系列中卻將SELINUX設定為預設安裝並執行的套件之一。

最近因為某些原因於是在vmware下裝起Red Hat系列的Fedora（別了Debian/Ubuntu），等安裝好Tomcat之後要測試的時候發現連到localhost時完全正常，但是從host machine要連過去的時候就是不work，總是在firefox的分頁中看到連線錯誤的訊息。

接下來做了很多嘗試與微調，其中最讓我不解的是為什麼我用Putty連SSH連得好好的，web server卻連不上？在vmware下執行netstat -an時明明看到web server與Tomcat的port處於listen狀態，後來終於在姑且一試的心態下從host machine對vmware展開port scan，發現只有SSH的port 22是開的？！心想"我明明沒有裝firewall套件阿，為什麼外部只看得到port 22？"

上google求救之後終於發現原來是SELINUX在搞鬼，因為SELINUX會設定一些iptables規則導致於最後只有port 22是預設對外開放的port。在disable SELINUX並停止iptables service後一切總算在隨著重新開機回歸正常，從host machine也終於能夠順利連到vmware的web server中。

disable SELINUX的方法：
將/etc/selinux/config其中的SELINUX=enforcing改為SELINUX=disabled

停止iptbales service的指令：
/sbin/service iptables stop

Update @ 20081021
昨天發現跟SELINUX沒關係，只要修改iptables規則就可以，但是由於懶得修改，所以還是直接把iptables service停掉了。
這麼說來標題似乎下錯了！

CS in my Ubuntu box!

今天照著google到的三篇文章^1,2,3半信半疑地把wine裝起來，沒想到真的就真的跑起來了！重點是還蠻流暢的。
第一篇說明如何設定wine以及安裝cs，第二篇則是說明如何讓cs能夠顯示中文字，第三篇用來解決聲音延遲的問題。
我要對字體取得以及registry設定補充說明：

1. 首先字體可以從裝有Windows的機器上取得，以新細明體為例，完整路徑為c:\windows\Fonts\mingliu.ttc
2. 將字體複製到Linux機器上，例如放到wine的字體目錄中，~/.wine/drive_c/windows/Fonts
3. 接下來執行wine regedit開啟registry編輯器，找到HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\Fonts之後新增字串，因為我們要直接套用第二篇文章提供的.reg檔案，因此新增字串的名稱取名為 PMingLiU，內容為mingliu.ttc的完整路徑，/home/"user_name"/.wine/drive_c/windows /Fonts/mingliu.ttc
4. 將第二篇文章提供的.reg檔匯入registry中
5. 完成，使用根據第三篇文章提到的aoss wine啟動cs執行檔進入遊戲

最後附上真相：


1. http://ubuntuforums.org/showthread.php?t=304528
2. http://wiki.ubuntu-tw.net/index.php?title=Wine
3. http://ubuntuforums.org/showthread.php?t=187666

auto mount usb drive failed

累積兩個星期的ubuntu update終於在昨天一口氣更新完畢，只不過更新完後卻發現原本用得好好的外接usb硬碟現在卻沒有辦法在接上usb port時自動掛載到系統中，自動掛載的過程會出現下列的錯誤訊息：

org.freedesktop.hal.storage.mount-removable no <-- (action, result).

原本一度以為可能是硬碟壞掉，由於不甘心眼睜睜看著硬碟中的資料¹就這麼付諸流水，因此特地將上面提及的錯誤訊息丟到google中好好搜尋一番，沒有多久便在某網頁²找到類似的解決方法：

sudo gnome-mount -vbd /dev/sdb1

從dmesg中得知我的外接usb硬碟的代號為/dev/sdb，而原本主要的資料都存在第一個劃分區塊因此決定mount /dev/sdb1。



1 hm... you know exactly what i am saying :-)
2 http://ubuntuforums.org/showthread.php?t=857374

Mount drive in dosbox

1. 在terminal下執行dosbox指令
2. 在dosbox的console下執行mount指令，例如：

mount c /home/user/tmp
mount d /media/cdrom

PS. dosbox的mount指令只能接受完整路徑，因此在Linux環境下用~是行不通的。

[Scheduler] More Detail In Scheduler

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

我們在上一篇¹提到2.6.24.3以後版本的scheduler永遠將cfs_rq rb-tree²中最左邊的node挑出來成為current task，而kernel是依據每個task的vruntime大小決定該task在cfs_rq rb-tree中的位置。最後發現不論是task的vruntime或是單次執行時間長度都與task的load欄位³有密切的關係，因此決定再花一篇的篇幅解釋load究竟是何方神聖。

之前所提到的load其實是個內含integer type的weight與inv_weight的structure，一般狀況下weight與inv_weight分別來自於prio_to_weight與prio_to_wmult兩個integer array，也可以稱這兩個array為對照表（look-up table），若是遇到task為real-time task或是idle task，kernel便直接將weight與inv_weight設定為某固定值，實際上替task取得load參數的函式為set_load_weight。

static void set_load_weight(struct task_struct *p)
{
        if (task_has_rt_policy(p)) {
                p->se.load.weight = prio_to_weight[0] * 2;
                p->se.load.inv_weight = prio_to_wmult[0] >> 1;
                return;
        }

        /*
         * SCHED_IDLE tasks get minimal weight:
         */
        if (p->policy == SCHED_IDLE) {
                p->se.load.weight = WEIGHT_IDLEPRIO;
                p->se.load.inv_weight = WMULT_IDLEPRIO;
                return;
        }

        p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
        p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

當task為一般task時，它的load便取決於它的static priority，顧名思義static priority通常在建立task的時候就設定好，位於100與140之間⁴，一般預設為120⁵。在已知MAX_RT_PRIO被設定為100的情況下，得知task的static priority之後便可以利用對照表取得weight與inv_weight，weight與inv_weight相乘後約為2^32⁶，prio_to_weight array中的數字則是新版scheduler中少見的magic number。

static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

static const u32 prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

看完load的由來之後我們知道kernel schedules tasks與決定每個task單次執行時間長度的主要依據為task的static priority與目前在runqueue的task數（cfs_rq->nr_running）。當runqueue中task數小於或等於5⁷時，task的priority與單次執行時間長度僅受task的static priority影響，當runqueue中的task數大於5時，則runqueue中的task數也成為影響因素之一。

static u64 __sched_period(unsigned long nr_running)
{
        u64 period = sysctl_sched_latency;

        unsigned long nr_latency = sched_nr_latency;

        if (unlikely(nr_running > nr_latency)) {
                period *= nr_running;
                do_div(period, nr_latency);
        }

        return period;
}

1 http://memyselfandtaco.blogspot.com/2008/07/scheduler-behind-scene.html
2 red-black tree（紅黑樹）。
3 load其實是在task_struct中sched_entity裡的欄位。
4 數字越小優先權越高，0~99為real-time task的priority範圍。
5 nice的範圍為-20到20的典故便由此而來。
6 整數運算自動刪除小數位。
7 又是一個magic number。

[Scheduler] Behind The Scene

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

本篇要討論的是scheduler背後幫助我們更容易了解scheduler如何運作的一些細節，主要以解釋下列兩個問題的方式進行：

1. Kernel以什麼為依據決定將task放runqueue¹中哪個位置？
   
2. 在沒有preemption發生的時候kernel怎麼知道什麼時候該讓current task釋出CPU給其他task使用？

Kernel以什麼為依據決定將task放runqueue中哪個位置？
版本2.6.22之後的kernel在runqueue中以新增的cfs_rq紅黑樹結構存放schedule entity（SE），也就是紀錄與每個task執行相關的時間數據。Kernel在runqueue新增資料的時候以SE中的vruntime為比較依據，與樹中各SE的vruntime相比，帶有小vruntime的SE往左邊擺，反之帶有大vruntime的se則往右邊擺，直到新的SE本身成為最左邊或最右邊的node為止。SE中的vruntime的型態為64-bit integer代表的意義是在第vruntime個tick²之前該SE代表的task要取得CPU執行工作，是kernel用來確保schedule公平性的新做法。

當新task被產生出來以後task_new_fair函式先透過place_entity函式取得新task的vruntime。

place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
        u64 vruntime;

        vruntime = cfs_rq->min_vruntime;

        if (sched_feat(TREE_AVG)) {
                struct sched_entity *last = __pick_last_entity(cfs_rq);
                if (last) {
                        vruntime += last->vruntime;
                        vruntime >>= 1;
                }
        } else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
                vruntime += sched_vslice(cfs_rq)/2;

        /*
         * The 'current' period is already promised to the current tasks,
         * however the extra weight of the new task will slow them down a
         * little, place the new task so that it fits in the slot that
         * stays open at the end.
         */
        if (initial && sched_feat(START_DEBIT))
                vruntime += sched_vslice_add(cfs_rq, se);

        if (!initial) {
                /* sleeps upto a single latency don't count. */
                if (sched_feat(NEW_FAIR_SLEEPERS))
                        vruntime -= sysctl_sched_latency;

                /* ensure we never gain time by being placed backwards. */
                vruntime = max_vruntime(se->vruntime, vruntime);
        }

        se->vruntime = vruntime;
}

cfs_rq->min_vruntime其實就是整個紅黑樹中最左邊schedule entity的vruntime，在kernel呼叫__update_curr函式時更新，而整個紅黑樹中每個schedule entity的vruntime會隨著時間而增加。

取得新task的vruntime之後task_new_fair函式再間接透過enqueue_task_fair函式呼叫__enqueue_entity函式將新task的schedule entity放入cfs_rq，vruntime正是在__enqueue_entity函式中被拿來當作決定新task該放在cfs_rq紅黑樹中的哪個位置。

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
        struct rb_node *parent = NULL;
        struct sched_entity *entry;
        s64 key = entity_key(cfs_rq, se);
        int leftmost = 1;

        /*
         * Find the right place in the rbtree:
         */
        while (*link) {
                parent = *link;
                entry = rb_entry(parent, struct sched_entity, run_node);
                /*
                 * We dont care about collisions. Nodes with
                 * the same key stay together.
                 */
                if (key < entity_key(cfs_rq, entry)) {
                        link = &parent->rb_left;
                } else {
                        link = &parent->rb_right;
                        leftmost = 0;
                }
        }

        /*
         * Maintain a cache of leftmost tree entries (it is frequently
         * used):
         */
        if (leftmost)
                cfs_rq->rb_leftmost = &se->run_node;

        rb_link_node(&se->run_node, parent, link);
        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

在已知kernel_init為kernel中第一支thread也是當runqueue中沒有其他user threads時所跑的thread的情況下，我們可以合理地推測kernel_init的vruntime應該相當大。

在沒有preemption發生的時候kernel怎麼知道什麼時候該讓current task釋出CPU給其他task使用？
timer interrupt會輾轉透過update_process_times函式呼叫scheduler_tick函式，在2.6.22以前的版本中 scheduler_tick函式會遞減current task的time slice直到time_slice為零或是達到單次允許執行的長度（利用TIMESLICE_GRANULARITY macro取得）時便將current task的flag加上表示該讓scheduler重新挑選task讓CPU執行的數值（TIF_NEED_RESCHED）。但是在2.6.22之後版本的scheduler_tick函數中卻沒有這些機制，這讓我合理的懷疑新版的kernel完全摒棄time slice機制，新版scheduler_tick函式的原始碼如下。

新版的scheduler_tick函式輾轉透過task_tick_fair函式（scheduler_tick函式的第18行，row 3493）與entity_tick函式呼叫check_preempt_tick函式判斷current task是否該將CPU讓出以執行其他task。在版本2.6.22之後的kernel中的time slice成為如vruntime一般的抽象的概念，單純透過比較數字大小決定是否要將TIF_NEED_RESCHED加入task flag，因此kernel也不再花力氣在task_struct中maintain time slice。

sched_slice函式會根據目前runqueue中task的數量決定每個task的最佳執行時間長度⁴與current task使用CPU時間³相比較，當current task使用CPU時間已超過它的最佳執行時間長度kernel便會將current task標示為need reschedule。current task的sum_exec_runtime則是在每次scheduler_tick函式被timer interrupt觸發的時候更新。

看過code之後發現與2.6.22以前的原始碼比較起來新版的scheduler用了比較少magic number，至於效能上改進多少我也就無法得知，留給有緣人去研究。

剛才不論是在討論task的vruntime還是單次執行時間長度，計算過程中都使用到schedule entity中的load欄位，至於這個load究竟是什麼東西又是從何而來，我們就留給下篇去討論吧。



1 正確來說應該是runqueue中的cfs_rq，雖然說將task放入runqueue其實是將代表task的SE放入runqueue的cfs_rq欄位。
2 tick用於紀錄timer interrupt signals的次數，是Linux中最小的時間單位，決定於define值HZ，此版本中的預設值為250。
3 從最後一次被scheduler挑選出來開始使用CPU的時間開始計算。
4 sched_slice函式中也用到了一些magic numbers。

[Scheduler] Before Schedule Takes Place

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

假設我們遇到的是一般task，在schedule暫停current task並讓原本暫停中的task成為current task之前會呼叫put_prev_task_fair函式將current task¹讓出CPU的使用權，如果current task已執行完畢就會被從runqueue移除，否則重新放回runqueue等待下次輪到它使用CPU繼續執行。

static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
       struct sched_entity *se = &prev->se;
       struct cfs_rq *cfs_rq;

       for_each_sched_entity(se) {
               cfs_rq = cfs_rq_of(se);
               put_prev_entity(cfs_rq, se);
       }
}

這裡出現新的struct，一個名為sched_entity，這個struct跟sched_class一樣屬於task_struct的一個欄位，主要用來紀錄可以被schedule的task在執行時間方面的相關資訊與維持紅黑樹架構的rb_node；另一個名為cfs_rq²，cfs_rq是runqueue中用來處理fairness的一個欄位。put_prev_entity函式主要是將原本指到current task的指標（cfs_rq->curr）設為NULL，在此之前如果發現current task還沒有執行完畢³的話便將代表current task的schedule entity重新放回runqueue等待下次被scheduler挑選出來執行。

當current task讓出CPU使用權之後kernel的工作便是從runqueue中挑選出一個task讓它成為下一個current task，這個動作透過pick_next_task函式呼叫pick_next_task_fair函式完成。pick_next_task_fair函式呼叫__pick_next_entity函式從cfs_rq中將最左邊的schedule entity挑選為下一個current task。

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
       struct sched_entity *se = NULL;

       if (first_fair(cfs_rq)) {
               se = __pick_next_entity(cfs_rq);
               set_next_entity(cfs_rq, se);
       }

       return se;
}

確認新選出的current task與原本的current task並不是同一個task之後便呼叫context_switch函式備份原task的狀態並還原新task的狀態，待備份還原狀態完成之後便直接開始執行新的current task。

看到這裡大家應該都會有一些共同的疑問，例如，kernel是以什麼原則為依據將task放入cfs_rq的樹狀結構中，以及在current task沒有遭到preempt的狀況下kernel怎麼知道該呼叫schedule函式讓其他task也有機會執行。我會在下一篇文章中試著以我理解的程度解釋這些疑點。



1 current task指的是CPU正在執行的task。
2 cfs為complete fair scheduler的縮寫。
3 schedule entity中on_rq欄位的值為1。

Share folder with virtualbox -- just a short note

If you are running Linux as guest OS, use mount.vboxsf instead of mount -t vboxsf when you encounter the following error message:

mounting failed with the error: Protocol error

The complete command should look like this (ignore the brackets when you type in):

sudo mount.vboxsf [share folder's name] [your mount point]

[Scheduler] The Overview

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

Linux schedules tasks的過程中會依據task_struct中紀錄¹的schedule scheme決定如何操作²runqueue，每個task所屬的schedule scheme不是fair_sched_class就是rt_sched_class。Fair schedule class用於schedule所有一般的tasks，rt schedule class用於schedule所有real-time tasks³。我們先看看fair_sched_class與rt_sched_class兩個struct的內容：

static const struct sched_class fair_sched_class = {
        .next                   = &idle_sched_class,
        .enqueue_task           = enqueue_task_fair,
        .dequeue_task           = dequeue_task_fair,
        .yield_task             = yield_task_fair,

        .check_preempt_curr     = check_preempt_wakeup,

        .pick_next_task         = pick_next_task_fair,
        .put_prev_task          = put_prev_task_fair,

#ifdef CONFIG_SMP
        .load_balance           = load_balance_fair,
        .move_one_task          = move_one_task_fair,
#endif

        .set_curr_task          = set_curr_task_fair,
        .task_tick              = task_tick_fair,
        .task_new               = task_new_fair,
};

const struct sched_class rt_sched_class = {
        .next                   = &fair_sched_class,
        .enqueue_task           = enqueue_task_rt,
        .dequeue_task           = dequeue_task_rt,
        .yield_task             = yield_task_rt,

        .check_preempt_curr     = check_preempt_curr_rt,

        .pick_next_task         = pick_next_task_rt,
        .put_prev_task          = put_prev_task_rt,

#ifdef CONFIG_SMP
        .load_balance           = load_balance_rt,
        .move_one_task          = move_one_task_rt,
#endif

        .set_curr_task          = set_curr_task_rt,
        .task_tick              = task_tick_rt,
};

再來看看取自schedule函式的範例：

prev->sched_class->put_prev_task(rq, prev);

若prev為一般task，則實際呼叫的函式為put_prev_task_fair，否則呼叫put_prev_task_rt函式。
改版後的schedule函式將schedule scheme切成兩個部分，一般task與real-time task，一般task使用紅黑樹的方式排序，real-time task則延續使用2.6.22版本以前的O(1)方式排序，code與之前的版本相比也更為精簡，由2.6.22的158行減少為2.6.24的63 行。新版schedule函式的重點落在下面幾行code上：

prev->sched_class->put_prev_task(rq, prev);
next = pick_next_task(rq, prev);

sched_info_switch(prev, next);

if (likely(prev != next)) {
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        context_switch(rq, prev, next); /* unlocks the rq */
} else
        spin_unlock_irq(&rq->lock);

1 紀錄於task_struct的sched_class欄位中。
2 在runqueue中新增移除task，或者改變task在runqueue中的位置（優先順序）。
3 PC環境中很難做到真的real-time，因此這裡的real-time task指的是擁有高執行優先權要儘早執行完畢的task。

Linux scheduler大改版

原本今天打算開始寫Linux scheduler的部分，但是一看src code之後發現跟之前看的src code與教科書¹有很大的出入，傳說中的O(1) scheduler早已不復存在，於是決定好好研究一下再下筆。看著看著發現一個新的資料結構，名為struct cfs_rq cfs，Google之後大概知道它的作用，也找到了一個有趣的blog²，有趣的部分在於它的comment。

PS. 這時候前恩師的話在腦中響起"src code在眼前為什麼不看而要相信書上寫的呢？"。



1 大名鼎鼎的Understanding Linux Kernel與Linux Kernel Development。
2 http://zylix666.blogspot.com/2007/10/cfs.html

[Process Management] Process/Thread Termination Part 2

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。
• PID即為TID。
  

Kernel版本：

• v2.6.24.3
  

What does do_exit do?
按照正常的邏輯推理，當一個thread執行結束後作業系統需要做的事情包含將thread標示為離開作業環境，將thread佔用的資源釋出，例如檔案、lock、thread與descriptor的記憶體空間等。現在就來看看do_exit函式究竟做了哪些事情。

當一個thread執行結束之後do_exit函式會先將PF_EXITING寫入該thread task_struct的flags欄位。經過一些house keeping work之後透過exit_mm函式呼叫mmput函式將該thread所使用的記憶體空間與其descriptor釋出。

void mmput(struct mm_struct *mm)
{
        might_sleep();

        if (atomic_dec_and_test(&mm->mm_users)) {
                exit_aio(mm);
                exit_mmap(mm);
                if (!list_empty(&mm->mmlist)) {
                        spin_lock(&mmlist_lock);
                        list_del(&mm->mmlist);
                        spin_unlock(&mmlist_lock);
                }
                put_swap_token(mm);
                mmdrop(mm);
        }
}

接著釋出的是該thread使用的檔案，透過__exit_files函數呼叫put_files_struct函數將檔案關閉並且釋出descriptor空間，而接下來的__exit_fs函式則是用來釋出檔案系統中規劃給剛剛關閉的檔案用的cache。

static void __exit_files(struct task_struct *tsk)
{
        struct files_struct * files = tsk->files;

        if (files) {
                task_lock(tsk);
                tsk->files = NULL;
                task_unlock(tsk);
                put_files_struct(files);
        }
}

static void __exit_fs(struct task_struct *tsk)
{
        struct fs_struct * fs = tsk->fs;

        if (fs) {
                task_lock(tsk);
                tsk->fs = NULL;
                task_unlock(tsk);
                __put_fs_struct(fs);
        }
}

資源釋出完畢之後便呼叫exit_thread函式移除該thread使用的I/O bitmap與TSS¹。

void exit_thread(void)
{
        /* The process may have allocated an io port bitmap... nuke it. */
        if (unlikely(test_thread_flag(TIF_IO_BITMAP))) {
                struct task_struct *tsk = current;
                struct thread_struct *t = &tsk->thread;
                int cpu = get_cpu();
                struct tss_struct *tss = &per_cpu(init_tss, cpu);

                kfree(t->io_bitmap_ptr);
                t->io_bitmap_ptr = NULL;
                clear_thread_flag(TIF_IO_BITMAP);
                /*
                 * Careful, clear this in the TSS too:
                 */
                memset(tss->io_bitmap, 0xff, tss->io_bitmap_max);
                t->io_bitmap_max = 0;
                tss->io_bitmap_owner = NULL;
                tss->io_bitmap_max = 0;
                tss->x86_tss.io_bitmap_base = INVALID_IO_BITMAP_OFFSET;
                put_cpu();
        }
}

接著呼叫exit_notify函式告知作業系統中其他的threads有thread執行完畢要離開，exit_notify函式最主要的功用是通知該thread的parent與children threads，並將其children threads過戶給其他thread作為他們新的parent。exit_notify函式呼叫forget_original_parent函式將children threads過戶給同一個thread group的其他thread，若thread group只有執行結束的那個thread則將children threads過給kernel_init thread。

do {
        reaper = next_thread(reaper);
        if (reaper == father) {
                reaper = task_child_reaper(father);
                break;
        }
} while (reaper->flags & PF_EXITING);
...
list_for_each_entry_safe(p, n, &father->ptrace_children, ptrace_list) {
        p->real_parent = reaper;
        reparent_thread(p, father, 1);
}

處理完children threads之後輪到通知parent，將exit_signal設為SIGCHLD讓parent知道該thread已經執行完畢。

if (tsk->exit_signal != SIGCHLD && tsk->exit_signal != -1 &&
    ( tsk->parent_exec_id != t->self_exec_id  ||
      tsk->self_exec_id != tsk->parent_exec_id)
    && !capable(CAP_KILL))
        tsk->exit_signal = SIGCHLD;

exit_notify函式最後將該thread的狀態改為EXIT_ZOMBIE讓Linux知道有thread執行完畢²並且可以將該thread移除，同時確保該thread在被Linux移除之前不會再被挑選出來執行。執行完exit_notify函式之後do_exit函式將執行結束的thread的狀態再改為TASK_DEAD才呼叫schedule函式，將狀態改為TASK_DEAD的用意是讓稍後的schedule函式可以透過context_switch函式呼叫finish_task_switch函式中的put_task_struct函式移除該thread的task_struct。

tsk->state = TASK_DEAD;

schedule();

static void finish_task_switch(struct rq *rq, struct task_struct *prev)
        __releases(rq->lock)
{
        struct mm_struct *mm = rq->prev_mm;
        long prev_state;

        rq->prev_mm = NULL;

        /*
         * ...
         */
        prev_state = prev->state;
        finish_arch_switch(prev);
        finish_lock_switch(rq, prev);
        fire_sched_in_preempt_notifiers(current);
        if (mm)
                mmdrop(mm);
        if (unlikely(prev_state == TASK_DEAD)) {
                /*
                 * ...
                 */
                kprobe_flush_task(prev);
                put_task_struct(prev);
        }
}

明明在呼叫schedule函式之前已經明確將狀態改為TASK_DEAD為什麼最後一個判斷式裡面要用unlikely？因為完成context switch的thread不一定執行完畢，而與正常執行被context switch的次數比起來執行完畢所占的context switch次數少太多了³，所以使用unlikely預測大部分時候是不成立的以節省branching所需的時間。



1 TSS存放的是每個thread被context switch時所需要的資訊，會於稍後的memory management介紹。
2 包含釋出所有佔用的資源。
3 每個thread只會結束一次而已，但是會被context switch很多次，time slice的range為數十ms到數百ms，稍後在討論schedule的時候會加以介紹。

More on LXR -- The partial use of hosts file

今天再來討論一下有關LXR的議題。
當我們編輯lxrng.conf的時候會指定base_url，如果裡面填寫的是domain name則其他在同樣LAN的電腦可能會無法開啟LXR網頁，這時候我們需要在瀏覽端電腦上設定hosts檔案，hosts檔案在Linux與Winows下的路徑分別為：
Linux --> /etc/hosts
Windows --> C:\WINDOWS\system32\drivers\etc\hosts

在裡面加上：
LXR機器的IP¹ LXR機器的domain name

如此一來不論瀏覽端電腦是否在LAN²都可以使用LXR機器的domain name開啟LXR頁面。



1 甚至"localhost"也可以
2 包括LXR本機

[Process Management] Process/Thread Termination Part 1

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
  
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。

Kernel版本：

• v2.6.24.3
  

有關thread termination有兩件事情需要確認，一是kernel thread與user thread結束的步驟是否相同（Part 1），二是他們結束的步驟各¹為何（Part 2）。

講到thread termination讓人立即想到的就是程式執行（user thread）完畢，user thread通常是因執行應用程式的可執行檔而產生，而compiler在編譯應用程式可執行檔的過程中會在程式最後加上exit函式，該函式會透過system call sys_exit讓Linux結束並移除該應用程式（user thread）[1]，實際上sys_exit函式就等於do_exit函式。

asmlinkage long sys_exit(int error_code)
{
        do_exit((error_code&0xff)<<8);
}

雖然說kernel thread通常在關機（或重新開機）前是不會停止運作²，kernel thread一旦執行完畢³還是會跟user thread走相同的步驟呼叫do_exit函式，詳見下圖。

上圖所顯示的是kernel thread hello_world執行完畢正在被Linux移除的debug screenshot，我們在kernel中新增一個叫做hello_world的函式並於開機的過程中⁴透過kernel_thread函式執行列印二行文字⁵，而breakpoint正是設在hello_world第二次呼叫printk的時候。

以上說明了Linux透過相同的do_exit函式移除束完畢的kernel thread與user thread。



1 如果結束步驟不同再分別探討。
2 Kernel thread大部分都是用於維持電腦正常運作，因此都會以無窮回圈方式執行，但如果是由driver所建立的kernel thread就有可能在某些時候遭到停止甚至移除。
3 離開無窮回圈或根本就沒有回圈存在。
4 於rest_init函式中呼叫，確定一些基本硬體設定都已初始完成。
5 分別為"hello world"與"leaving now"。


[1] Linux Kernel Development, Robert Love, DEVELOPER'S LIBRARY
http://www.amazon.com/exec/obidos/tg/detail/-/0672327201/ref=lpr_g_1/104-4939002-4103159?v=glance&s=books&n=507846

[Process Management] Process/Thread Creation Part 3

專門用語：

• 使用打字機（Courier New）字體表示原始碼。
• task/process即為Linux中的thread。
• 文中的Linux與Linux kernel指的皆為作業系統核心。
• 使用斜體字型標示Linux中的資料結構，macro，變數或函式名稱。

Kernel版本：

• v2.6.24.3

Kernel thread與User thread建立過程的相同之處：

• 都會呼叫do_fork函式建立task_struct，task_thread_info，與堆疊空間。
• 新建立的thread的狀態都是可以執行，但不一定馬上被執行。

Kernel thread與User thread建立過程的不同之處：

• 傳入do_fork的數性參數不同，就連產生user thread的三個函式¹本身傳入的屬性參數都不同。
• 產生kernel thread時新thread要執行的函式已經存在記憶體中，因此可以直接將函數指標存入暫存器²，而產生user thread時Linux需要先呼叫sys_execve函式讀取存放於硬碟的執行檔並將內容放入記憶體中再將函式指標存入暫存器。

建立好新Thread，然後呢？ 這個部分要討論的是每個thread被建立出來直到執行完畢有可能經歷的狀態³，Linux將thread的狀態主要分為以下幾種（並附上說明）：

• TASK_RUNNING：擁有此狀態的thread是被放在runqueue中，隨時有可能被scheduler選出來執行。
• TASK_INTERRUPTIBLE：擁有此狀態的thread並不存在於runqueue中，只有在等待的條件成立或是接收到signal時才會被重新放入runqueue成為可執行的thread。
• TASK_UNINTERRUPTIBLE：與擁有TASK_INTERRUPTIBLE狀態的thread一樣不存在於runqueue中並等待條件成立，但是該thread並不會因為接收到signal⁴而被重新放入runqueue等待執行。
• EXIT_ZOMBIE：當一個thread執行完畢但是它的task_struct，task_thread_info與堆疊空間還存在於記憶體中的時候該thread便是此狀態，因此runqueue中當然也找不到該thread。
• TASK_STOPPED：這個狀態表示一個thread的運行因接收到signal而遭到停止，最好的例子便是進入GDB除錯模式的thread。

每個thread從被建立出來到執行結束都離不開上述幾個狀態，那麼thread的狀態又是在什麼時候改變的呢？請參照下圖（懶得畫，直接節錄自Robert Love 寫的Linux Kernel Development，若有侵權疑慮請告知，我會在看到通知之後替換 ）：

上圖中的TASK_ZOMBIE在2.6.24.3裡面其實就是EXIT_ZOMBIE。
以下是thread狀態的define值：

#define TASK_RUNNING            0
#define TASK_INTERRUPTIBLE      1
#define TASK_UNINTERRUPTIBLE    2
#define TASK_STOPPED            4
#define TASK_TRACED             8
/* in tsk->exit_state */
#define EXIT_ZOMBIE             16
#define EXIT_DEAD               32
/* in tsk->state again */
#define TASK_DEAD               64

當thread被標示為TASK_TRACED狀態時表示該thread正在被其parent使用ptrace⁵觀察它的運行，至於EXIT_DEAD與TASK_DEAD狀態就等我們探討Linux如何移除執行完畢的thread時再好好觀察他們的作用各是什麼。接下來我們要討論當thread進入EXIT_ZOMBIE狀態之後Linux是如何將它移除。



1 sys_fork，sys_vfork，與sys_clone。
2 此指新thread存放暫存器的資料結構，當scheduler挑選新thread執行之前該資料結構中的暫存器內容全部都會被放進真實的暫存器中。
3 紀錄於task_struct中的state欄位。
4 應該說是完全感受不到signal的存在。
5 可以把它看作debug工具的一種（http://linux.about.com/library/cmd/blcmdl2_ptrace.htm ）。