2017 q3 Homework08 - Server-framework

contributed <williamchang,twngbm>

tags: `Class_Project`, `Jserv`

Target

先對技術原理了解
完整的技術報告
釐清前人的結果
錄影
原程式網址:
- embedded2016/server-framework
- ktvexe/server-framework
原 Hackmd 技術報告及講解:

對技術原理的了解

Server-framework 的行為，作者這張圖太好理解整個流程，所以就沿用他的

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

首先對 epoll 做初步的原理了解

epoll 是 Linux 核心的可擴展 I/O 事件通知機制，目的在於取代原有的 POSIX select(2)與poll(2)系統函式，讓需要大量操作檔案描述子的程式得以發揮優異的效能
與 FreeBSD 的 kqueue 類似，底層都是由可組態的核心物件所構成，以檔案描述子 (file descriptor) 的形式呈現給使用者。
比較：

傳統的系統函式的 Time complexity = O(n)
epoll 的 Time complexity = O(log n)

epoll 提供兩個模式
- edge-triggered
- level-triggered
Edge-triggered 的模式中， epoll_wait 只會在新事件首次被加入 epoll 物件時返回。
level-triggered 的模式中， epoll_wait 在事件狀態為變更前會不斷觸發，直到緩衝區的資料全數被取出。

再來思考為什麼會比較快，也就是時間複雜度為何會比較低

epoll 及 select 最主要的差別在於一個任務下處理的數目

select : 當一個 select 的系統呼叫開始， file descriptor 的列表檔只會存在單一個系統呼叫存在的時間，而這個呼叫任務只會待在 socket's wait queue 在這一個單獨的呼叫中，當呼叫結束則會跟著結束。若有 200 需求等待資料傳輸的系統呼叫，在此情況下就需要 200 個系統呼叫直到結束，很顯然的 Time complexity bounded in O(n)。另外一個直觀的說法是，因為在 fd 內等待的數目增增加而降低效率。
epoll : 與 select 不同的是，當一次系統呼叫後，其餘的需求會由直接在列表上給 kernel 處理，不需分批的一直系統呼叫，直到沒有事件在 waiting queue 中才返回，直到下一次呼叫再一次傳完 waiting queue 。再由上述的例子， 200 個需求只需要一次系統呼叫，把所有在 waiting queue 的 200 個事件傳完，平均下來 Time complexity approximate bounded in O(log n)。不會因為在 fd 內等待的數目增增加而降低效率。

參考資料：
- Wikipedia-epoll
- stackoverflow-Why is epoll faster than select?

由實驗來驗證 epoll 是相對比較快的方式

參考資料：

在這個我們所使用的環境下，用 epoll 來操作很明顯地是很適合的，epoll 適用於 file descriptor 大量的環境下，而 server-framework 剛好適用在此情況下能達到較好的效能，順帶一題，在 UNIX and Linux 的系統呼叫中，
大量的系統呼叫都是依賴file descriptor
根據 edge-triggered 及 level-triggered 可以這麼想，前者像是 Interrupt 機制，當有新的訊息才返回，而後者像是 polling 機制，一直去詢問直到資料傳完才返回williamchangTW
看看 epoll 的行為，如圖：

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

出處：Server Develop （六） Linux epoll总结

運作流程

這部分沿用原作者的講解：實作在protocol-server.c:srv_listen()

Server 啟動後 socket，建立通訊端並取得 file descriptor
socket bind 到特定位址及 port 以接收來自外部的通訊
透過 Async.create() 建立 thread pool，準備處理來自 reactor 的工作
- 每個 thread 會執行 Async.worker_thread_cycle()
將 server 接收端的 file descriptor 放到 epoll 中，並啟動 reactor，處理：
- Accept connect
- Printing connector
- Dealing request
Client 的 request 將由 Server 的 Reactor 先送入 Work queue 並在 pipe 寫入 one byte
- work queue 為 linked list
worker thread 將會取得 pipe 的 one byte 負責工作 (i.e. 處理某個 client 的 request)
Async.wait(): 等待所有 thread 跳出 Async.worker_thread_cycle() 迴圈。並處理完剩下的工作
- 或者透過TERM (ctrl+c) 進入 close()
  - close(): 將結束 Reactor 內的 Async 裡的所有 Worker thread

HTTP request & web server

Web Server 的功能包含下列三個步驟：
- step 1 : 接收瀏覽器所傳的網址
- step 2 : 取出相對應的檔案
- step 3 : 將檔案內容傳回瀏覽器
超文字傳送協定 (Hyper Text Transfer Protocol, HTTP)
server 要處裡 client 的連線需要先建立 socket，socket 會涉及七層，因為屬於 TCP/IP 的 interface
- create
- listen
- connect
- accept
- send
- read
- write

文中在 server settimg 有探討 port 8080 的用途，可是卻沒有詳細的討論完整，在這補充完成前一位同學未完成的部份
williamchangTW

先了解 80 Port : 是為 HTTP (HyperText Transport Protocol, 超本文傳輸協定) 開放的，上網瀏覽時使用率最普及的協定，主要用於 (World Wide Web,WWW 萬維網) 服務上傳輸資訊的協定。
8080Port : 8080Port 如同 80Port，是被利用於 WWW 代理服務，可以實現網頁瀏覽。經常訪問某個網站或代理伺服器時，會加上 "8080"Port 號，如： http://www.cce.com.cn:8080
8080Port 漏洞可以被各種病毒程式所利用，如： Brown Orifice (BrO) 特洛伊木馬病毒可以完全利用 8080Port 來感染其他電腦， RemoConChubo, RingZero 木馬也可以對該 Port 做攻擊
補充背景知識：
Port 有兩種意思：第一種是物理上的定義，第二種是邏輯上的意義

物理上 :
- 如 RJ-45Port, SCPort 用於連接其他網路設備的介面。
邏輯上 :
- 指的是 TCP/IP 協議中的 Port, Port 範圍由 0 ~ 65535(2¹⁶-1)，上面介紹的就是這裡說的。
  按照協議分類，可以分為 TCP, UDP, IP, ICMP(Internet 控制消息協定) 等 Port。
TCP Port : 即時傳輸控制協定 Port，需要在用戶端與伺服端建立連線，可以提供可靠的資料傳輸

參考資料：
- 常用 TCP Port 作用及操作建議
- TCP/UDP 常用端口列表

程式碼組成

參考作業資料 : 2016q1 Homework #3
server-framework 為一個由C99所撰寫的物件導向(Objected-Oriented)伺服器框架，包含以下三個部分：
- async.c
- reactor.c
- protocol-server.c
主程式部分為：httpd.c
參考影片：
- Server framework 效能強化 part 1
- Server framework 效能強化 part 2
async.c (影片中提出命名應為跟 thread pool 有關)

處理工作分配與控管 thread 在 thread pool

reactor.c

使用 epoll 管理 server 所有 file descriptor 的狀態，並負責派送工作給 async.c

protocol-server.c

定義一個 server 所需要的功能，如：發送網頁內容

Async 的部份程式碼解釋

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Reactor 的 Client 工作會將處理 request 的工作丟入Work queue，並且在 pipe 寫入 1 byte 紀錄
Worker thread 若發現 pipe 有紀錄，則會將該 1 byte 取出並執行 Work queue 中對應的 request
API








/* API handler*/
struct __ASYNC_API__ Async = {
    .create = async_create,
    .signal = async_signal,
    .wait = async_wait,
    .finish = async_finish,
    .run = async_run,
};

static int async run : 這個部份處理要被存進 workqueue 裡面運行


























/*a part of async run*/
/* Task Management - add a task and perform all tasks in queue */
// 處理存入 work queue 的運行，透過 pipe 喚醒 work thread 處理
static int async_run(async_p async, void (*task)(void *), void *arg)
{
     struct AsyncTask *c; /* work queue 採 linked list 存放，struct AsyncTask 為linked list 的 node */
.../*skip some code*/
    write(async -> pipe.out, c->task, 1);
    return 0;
}
// thread 進入 read 將會被 block 住
// work threads 將執行此函數負責讀取 pipe 並透過 perform_tasks() 來取得 task
// 處理工作直到所有 task 被處理完 (thread 欲取得 task 時將進入 lock)
// 每個 work thread 進入 lock 取得 task 之後就會 unlock，隨後執行完 task 才會再執行第2次 while loop 請求 task
/*listen pipe and release thread*/
static void *worker_thread_cycle(void *_async)
{
    .../*skip some code*/
    while (async->run && (read(async->pipe.in, &sig_buf, 1) >= 0)) {
    /*read 就是讀取 async_run 中 write 的 1 byte，若 async->run 為 0 則 work thread 會被強制結束*/
        perform_tasks(async); //當 workqueue 有資料的時候執行
        sched_yield(); //通知排程器，將自己的優先權設定為最低，讓 CPU 給其他程序使用
    } // 這裡是在等候上面 write() 有無資料 在 workqueue 中
    perform_tasks(async);//處裡剩下的工作，為了保證 workqueue 中的需求都被做完
    return 0;
}

Reactor 部份程式碼解釋 - 回應 request ，使用 epoll 監控

參考資料 :
Inter Process Communication, IPC 是用 pipe 的方式
Reactor 是一個設計模式 (design pattern)，是一種事件處理模式為了同時處理多個或單個服務需求傳送給服務處理程序 (server handler)。Server handler 將傳入的需求 demultiplexes 然後同步分派給相關的 request handler。在 server-framework 中可知道是由 epoll 實作這個概念。
- 再來思考為什麼需要 Reactor pattern，考慮以下情境，在沒有 Reactor pattern 概念的一般的狀況下 web application 的 Process 接到了 request ，處理過後接著要讀取資料或是寫入資料到資料庫，中間可能等待 Database 處理的時間（可能十幾毫秒或更長）該Process 其實是處於 sleeping 的狀態不做事情的，這也是為什麼你可能會發現 server 的 request 處理量一直上不去，但 CPU utilization still full，這就因為 Process 在處理資料庫的存取、檔案的 IO 或者是跟其他 Service 的溝通之間的等待時間，其實該 Process 都處於 Sleeping 狀態。
- 前述這樣的行為稱之為 I/O Blocking ，想像因為去處理其他所需要的檔案 I/O，或資料存取的時間所擋住應該想像中需要馬上執行該事件服務該發生的服務。
- 而上述的情況讓 Reactor pattern 概念有了實用之處，在Reactor Pattern 中有一個 Single thread 的 event loop，不停的循環等待是否有新的事件進來要處理，事件處理的過程中如有IO Blocking的產生，會使用 defer 將這個動作丟到 event loop 以外的另一個 thread，讓等待資料庫讀取的 sleeping 是發生在另外一個 thread，而不會讓 event loop 產生阻塞並且繼續服務下一個事件，等待資料庫讀取完了資料回傳回來以後，再透過 callback 將資料傳回event loop這個thread 中繼續處理
Reactor structure ：
- Resources : 從系統中任何可以提供輸入或 consume 輸出的資源。如: client 的 request。
- Synchronous Event Demultiplexer : 用 event loop 去阻擋所有 resource。多對一的傳送資源給分派器 (dispatch) 當有可能開啟同步運算在單一資源上而不被 blocking (example : 同步呼叫 read() 將會被 block ，如果沒有資料可供讀取的話)。如：epoll 將收到的 client request 放到 work queu 等待執行，而不會被 blocking。
- Dispatcher : 從 demultiplexer 分派資源給關聯的需求處理程序 (Request handler)。需求處理程序 (Request handler)處理 registering 和 unregistering。如：將 client 待處理的 request 丟入 Work queue ，並喚醒 thread 處理這些 request。函式 async_run( ) 即是呈現此功能。
- Request Handler : 定義如何應用 requset handler 和他相關的資源。如：worker thread 去處理工作 (client request)
set_fd_polling() : 將 request 送入 epoll 之中











int set_fd_polling(int queue, int fd, int action, long milliseconds){
    struct epoll_event chevent;
    chevent.data.fd = fd;
    chevent.events = EPOLLOUT | EPOLLIN | EPOLLET | EPOLLERR | EPOLLRDHUP | EPOLLHUP; //這邊為 epoll 的系統呼叫參數來表達不同的 epoll 狀態
    if (milliseconds){
        struct itimerspec newtime;
        .../*skip some code*/
        timerfd_settime(fd, 0, &newtime, NULL);
    }//這邊是 epoll 所設定的時間 timer
    return epoll_ctl(queue, action, fd, &chevent); //將工作的訊息送入 epoll 中執行
}

reator_review() : 將 epoll 中的工作拿出來執行






















int reactor_review(struct Reactor *reactor){
    .../*skip some code*/
    int active_count = _WAIT_FOR_EVENTS_; //這個 active_count 是用於 epoll_wait() 的系統呼叫，是 ready queue 裡面準備執行的工作，估計有幾個工作要執行
    if (active_count < 0) return -1; //假設沒有事件需要執行就結束
    if (active_count > 0) {
    /*for 迴圈會在有事件時，進去把所有需求事件 epoll 一遍*/
        for (int i = 0; i < active_count; i++) {
            if (_EVENTERROR_())
                /*errors are hendled as disconnections (on_close)*/
                reator_close(reactor, _GETFD_(i));
            }else{
                /*no error, then it is an active event*/
                /*以下的部分是在 ready queue 等待服務的事件抓出來執行*/
                if (_EVEBTREADY_(i) && reactor->on_ready)
                    reactor->on_ready(reactor, _GETFD_(i));
                if (_EVENTDATA_(i) && reactor->on_data)
                    reactor->on_data(reactor, _GETFD_(i));
            }
        }
    }
    return active_count;
}

Protocol-server 部份程式碼解釋 - 定義 server, 連線收發, 連線後工作狀態

static void srv_cycle_core : 用來監控整個系統中工作的狀態，並決定該工作是否該不該被中斷或繼續連線（程式中最靈魂的地方）

























/*review connection and check state*/
static void srv_cycle_core(server_pt server) {
    static size_t idle_performed = 0;
    int delta;
    delta = reactor_review(_reactor_(server)); //每當呼叫 srv_cycle_core 都會執行 reactor_review 一次（epoll 的實做得到所有事件的狀態）
    ...{/*skip some code*/
    if (server->tout[i]) {//檢查所有狀態
        if (server->tout[i] > server->idle[i]) //如果 time out 的時間大於 idle 的時間則會到 reactor_close 中斷這個事件
            server->idle[i] += server->idle[i] ? delta : 1;
            else {
                if (server->protocol_map[i] && server->protocol_map[i]->ping)server->protocol_map[i]->ping(server, i);
                else if (!server->busy[i] || server->idle[i] == 255)
                    reactor_close(_reactor_(server), i);//結束事件(連線)
            }
    }
}
server->last_to = _reactor_(server)->last_tick;
}
if  (server->run && Async.run(server->async,(void (*)(void *)) srv_cycle_core, server)) {//透過這一行持續的把 srv_cycle_core 這個靈魂函式推入 cycle 中持續監控所有活動
    perror(
        "FATAL ERROR:"
        "couldn't schedule the server's reactor in the task queue"
    );
    exit(1);
}

struct Server : 儲存 server 屬性與資料管理的 data structure






























struct Server {
    struct Reactor reactor; // 每個 server 都有專屬的 reactor
    struct ServerSettings *setting;
    struct Async *async;    // Thread pool
    pthread_mutex_t lock;   // Server object 是會被搶的
    
    /* 這區的 member 主要用來紀錄每個 connection 對應的資料，透過 fd 作為 offset 去存取 */
    struct Protocol * volatile *protocol_map;    // 聲明 "protoco_map" 是 pointer to array of pointer，而且指向的 struct Protocol 可能會被意外的改變
    struct Server **server_map; 
    void **udata_map;
    ssize_t (**reading_hooks)(server_pt srv, int fd, void *buffer, size_t size);
    volatile char *busy;    // 是否連結忙碌中
    unsigned char *tout;    // Timeout value of this connection
    unsigned char *idle;    // Idle cycle counts
    
    pthread_mutex_t task_lock;    //分辨要搶哪個 task
    
    struct FDTask *fd_task_pool;
    struct GroupTask *group_task_pool;
    size_t fd_task_pool_size;
    size_t group_task_pool_size;
    
    void **buffer_map;
    long capacity; /**< socket capacity */
    time_t last_to; /**< the last timeout review */
    
    int srvfd; // Server 用來聆聽 socket 的 fd
    pid_t root_pid; // Process 的 PID
    volatile char run; // Running flag
}

struct FDtask : 配送給某一個 fd (connection) 的 task，用 linked list 來管理










/* the data-type for async messages */
// ^^^ bad comment ^^^
struct FDTask {
    struct FDTask *next;
    struct Server *server;
    int fd;
    void (*task)(struct Server *server, int fd, void *arg);    // 主要派送的任務
    void *arg;
    void (*fallback)(struct Server *server, int fd, void *arg);    // 任務執行完要執行的工作
};

struct GroupTask : 需要在多個 fd (connection) 執行的共同 task











/* A self handling task structure */
// Self handling?
struct GroupTask {
    struct GroupTask *next;
    struct Server *server;
    int fd_origin;
    void (*task)(struct Server *server, int fd, void *arg);
    void *arg;
    void (*on_finished)(struct Server *server, int fd, void *arg);
    unsigned char fds[];    // 要被執行的所有 task
};

Listen 這部分做解釋 - 本身有一個 income queu

listen(srvfd, SOMAXCONN) : SOMAXCONN 是定義聆聽最大數量






if (listen(srvfd, SOMAXCONN) < 0) { 
    perror("couldn't start listening");
    close(srvfd);
    return -1;
}
/*若沒有請求則會往下做印出 "couldn't start listening" 然後關閉 srvfd 這個 queue 然後回傳錯誤*/

static void accept_async(server_pt server) :