Programming Assignment #2

Important Techniques Learned in this Homework

1. how to use fork(), wait(), waitpid()
2. how to use pipe() and mkfifo() to do inter process communication(IPC)
3. how to avoid deadlock when opening a FIFO

readme.txt

Execution:
    (1) Compilation: $ make
    (2) Run: $ ./bidding_system [host_num] [player_num]

    * NOTE: Please ensure that there are no any .FIFO files in working directory, or it will exit and print error message

Description:
    (1) bidding_system.c:
        * algorithm to enumerate all subset of size 8 on the player set: 
            一開始，我將 int set[8] 初始化成 {1, 2, 3, 4, 5, 6, 7, 8} 並在每次需要assign新的coompetition給root_host時，
            函數 next_subset() 會將 set[] 改成字典序比原本的subset大的最小subset。具體實作方式爲從 i = 7 開始往前掃，如果
            把 set[i] + 1 不超過 player_num，且 set[i] + 1 ... player_num 足夠填完 set[i...7]，就令 set[i] = set[i] + 1
            ，並令set[i+1] = set[i] + 1, set[i+2] = set[i+1] + 1...以此類推。如此以來，我就能得到字典序比原本的subset大的最小subset。
            若找不到這樣的subset，也就是當前的subset已經是字典序最大的subset了，next_subset()回傳-1,我就知道已經枚舉完 C(player_num, 8)
            種不同的subset了。

        * create FIFO:
            我在把每一個FIFO成功open之後，便立刻unlink掉他們，確保即使程式crash了，也不會遺留這些檔案。

        * avoid deadlock when opening FIFO:
            因爲在blocking mode下open FIFO時，如果對面沒有reader/writer，便會被block住，因此，我在執行open() + exec()後才能去open這些
            FIFO，如此以來，如果其中一邊被block住了，系統便會context switch到另一個process，此時因爲他已經能看到reader/writer，所以就不會
            被block住。最後在切換會本來被block住的process，就能使parent和child都順利開啓FIFO。

        * output rank of each player:
            因爲在排序後我們仍然要知道每一個player本來的index，所以我對pointer排序，這樣就可以透過pointer的value得知原本在array中的位置。

    (2) host.c:
        * pipe
            我在host建pipe的策略是對於每一個不同的child、write/read都各自建立一個獨立的pipe，我認爲這樣可以減少發生race condition的可能性。

        * function sublist(int list[], int L, int R, char buf[]):
            將list[]中 [L, R) 的數字轉換爲字串寫到buffer裏，方便我建構給child的訊息。

    (3) player.c:
        * 由於對於player來說，所有讀寫都是在standard input/output完成的，因此只需要簡單的scanf/printf就能達成我們的要求

bidding_system.c

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <fcntl.h>
#include <sys/wait.h>
#include <sys/stat.h>

const char *const usage_msg = "usage: ./bidding_system [host_num] [player_num]\n";
const char *const read_fifo_name = "Host.FIFO";

#define HOST_NUM_MAX 10
#define PLAYER_NUM_MAX 14
#define FIFO_NAME_MAX 128

typedef struct {
    pid_t pid;
    int fd;
    int random_key;
    char fifo_name[FIFO_NAME_MAX];
} RootHost;

void ERR_EXIT(char *msg) { perror(msg); exit(128); }

void flush_fsync(FILE *stream) { fflush(stream); fsync(fileno(stream)); }

int rank_to_score(int rank) { return 8 - rank; }

int next_subset(int, int[]);

void create_fifo(RootHost root_host_list[], int host_num);

void fork_root_hosts(RootHost root_host_list[], int host_num);

void assign_competition(RootHost *root_host, int set[]);

void output_rank(int player_num, int player_score[]);

int main(int argc, char *argv[])
{
    if ( argc != 3 ) {
        // the number of arguments should be exactly 2
        fprintf(stderr, usage_msg);
        exit(2);
    }
    int host_num = atoi(argv[1]);  // 1 <= x <= 10
    int player_num = atoi(argv[2]);  // 8 <= x <= 14

    FILE *read_fifo;
    RootHost root_host_list[HOST_NUM_MAX + 5];
    create_fifo(root_host_list, host_num);

    // fork root hosts
    fork_root_hosts(root_host_list, host_num);
    if ( (read_fifo = fopen(read_fifo_name, "rt")) == NULL )
        ERR_EXIT("fopen");
    unlink(read_fifo_name);

    // assign every hosts a competition
    int set[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    int active_host_num = 0;
    for ( int i = 1; i <= host_num; i++) {
        if ( (i == 1) || (i > 1 && next_subset(player_num, set)) ) {
            assign_competition(&root_host_list[i], set);
            active_host_num++;
        }
    }

    int player_score[PLAYER_NUM_MAX + 5] = {0};

    while ( active_host_num > 0 ) {
        int key;
        fscanf(read_fifo, "%d", &key);
        for ( int i = 0; i < 8; i++) {
            int id, rank;
            fscanf(read_fifo, "%d %d", &id, &rank);
            player_score[id] += rank_to_score(rank);
        }
        for ( int i = 1; i <= host_num; i++) {
            if ( root_host_list[i].random_key == key ) {
                if ( next_subset(player_num, set) ) {
                    assign_competition(&root_host_list[i], set);
                } else {
                    active_host_num--;
                }
            }
        }
    }

    for ( int i = 1; i <= host_num; i++) {
        char *msg = "-1 -1 -1 -1 -1 -1 -1 -1\n";
        write(root_host_list[i].fd, msg, strlen(msg));
        fsync(root_host_list[i].fd);
    }

    for ( int i = 1; i <= host_num; i++) {
        int term_status;
        waitpid(root_host_list[i].pid, &term_status, 0);
        if ( close(root_host_list[i].fd) == -1 )
            ERR_EXIT("close");
    }

    output_rank(player_num, player_score);

    exit(EXIT_SUCCESS);
}

void create_fifo(RootHost root_host_list[], int host_num) {
    if ( mkfifo(read_fifo_name, 0600) < 0 )
        ERR_EXIT("mkfifo");
    for ( int i = 1; i <= host_num; i++) {
        snprintf(root_host_list[i].fifo_name, FIFO_NAME_MAX, "Host%d.FIFO", i);
        if ( mkfifo(root_host_list[i].fifo_name, 0600) < 0 )
            ERR_EXIT("mkfifo");
    }
}

#define KEY_MAX 65536
void fork_root_hosts(RootHost root_host_list[], int host_num) {
    int used[KEY_MAX] = {0};
    srand(time(NULL));
    for ( int i = 1; i <= host_num; i++) {
        do {
            root_host_list[i].random_key = rand() % KEY_MAX;
        } while ( used[root_host_list[i].random_key] );

        used[root_host_list[i].random_key] = 1;

        root_host_list[i].pid = fork();
        if ( root_host_list[i].pid == -1 ) {
            ERR_EXIT("fork");
        } else if ( root_host_list[i].pid == 0 ) {
            char host_id_str[32], random_key_str[32];
            snprintf(host_id_str, 32, "%d", i);
            snprintf(random_key_str, 32, "%d", root_host_list[i].random_key);
            execl("./host", "host", host_id_str, random_key_str, "0", (char*)0);
        } else {
            if ( (root_host_list[i].fd = open(root_host_list[i].fifo_name, O_WRONLY)) == -1 )
                ERR_EXIT("open");
            unlink(root_host_list[i].fifo_name);
        }
    }
}

void assign_competition(RootHost *root_host, int set[]) {
    char set_str[BUFSIZ];
    int len = snprintf(set_str, BUFSIZ, "%d %d %d %d %d %d %d %d\n", 
                       set[0], set[1], set[2], set[3], set[4], set[5], set[6], set[7]);
    write(root_host->fd, set_str, len);
    fsync(root_host->fd);
}

int next_subset(int player_num, int set[]) {
    for ( int i = 7; i >= 0; i--) {
        if ( set[i] + (7 - i) < player_num ) {
            set[i]++;
            for ( int j = i + 1; j <= 7; j++)
                set[j] = set[j-1] + 1;
            return 1;
        }
    }
    return 0;
}

int cmp(const void *a, const void *b) {
    int x = **(int**)a, y = **(int**)b;
    return (x < y) - (x > y);
}

void output_rank(int player_num, int player_score[]) {
    int *ptr[PLAYER_NUM_MAX + 5];
    for ( int i = 1; i <= player_num; i++)
        ptr[i] = &player_score[i];
    qsort(ptr + 1, player_num, sizeof(int*), cmp);
    int rank[PLAYER_NUM_MAX + 5];
    rank[ptr[1] - player_score] = 1;
    for ( int i = 2; i <= player_num; i++)
        rank[ptr[i] - player_score] = (*ptr[i] == *ptr[i-1]) ? rank[ptr[i-1] - player_score] : i;
    for ( int i = 1; i <= player_num; i++)
        printf("%d %d\n", i, rank[i]);
}

host.c

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <fcntl.h>
#include <sys/wait.h>
#include <sys/stat.h>
#include <sys/types.h>

const char *const usage_msg = "usage: ./host [host_id] [random_key] [depth]";
const char *const write_fifo_name = "Host.FIFO";

#define FIFO_NAME_MAX 128
const int ROOT_HOST_DEP = 0;
const int CHILD_HOST_DEP = 1;
const int LEAF_HOST_DEP = 2;
const int ROUND_NUM = 10;

typedef struct {
    int player_id, score, rank;
} PlayerRecord;

typedef struct {
    pid_t pid;
    int wr_pipe_fd, rd_pipe_fd;
} Child;

void ERR_EXIT(char *msg) { perror(msg); exit(128); }

void flush_fsync(FILE *stream) { fflush(stream); fsync(fileno(stream)); }

void read_player_id(int player_id_list[], int n, int fd);

int sublist(int list[], int L, int R, char buf[]);

void fork_child(Child child_list[], int player_id_list[], int depth, char *argv[]);

void run_game(Child child_list[], int depth, void *extra);

void calc_rank(PlayerRecord player_record_list[]);

void clean_child(Child child_host_list[]);

int main(int argc, char *argv[])
{
    if ( argc != 4 ) {
        // the number of arguments should be exactly 3
        fprintf(stderr, usage_msg);
        exit(2);
    }

    int host_id = atoi(argv[1]);
    int random_key = atoi(argv[2]);
    int depth = atoi(argv[3]);

    if ( depth == ROOT_HOST_DEP ) {
        // fifo for read from bidding system
        char fifo_path[FIFO_NAME_MAX];
        snprintf(fifo_path, FIFO_NAME_MAX, "Host%d.FIFO", host_id);
        int read_fifo_fd = open(fifo_path, O_RDONLY);
        if ( read_fifo_fd == -1 )
            ERR_EXIT("open");

        // fifo for write to bidding system
        int write_fifo_fd = open(write_fifo_name, O_WRONLY);
        if ( write_fifo_fd == -1 )
            ERR_EXIT("open");

        // fork 2 child hosts
        Child child_host_list[2];
        fork_child(child_host_list, NULL, depth, argv);

        while ( 1 ) {
            int player_id_list[8];
            read_player_id(player_id_list, 8, read_fifo_fd);
            if ( player_id_list[0] == -1 ) {
                for ( int i = 0; i < 2; i++) {
                    char *msg = "-1 -1 -1 -1\n";
                    write(child_host_list[i].wr_pipe_fd, msg, strlen(msg));
                    fsync(child_host_list[i].wr_pipe_fd);
                }
                break;
            }

            // assign players to 2 child hosts
            for ( int i = 0; i < 2; i++) {
                char buf[BUFSIZ];
                int len = sublist(player_id_list, i * (4 >> depth), i * (4 >> depth) + (4 >> depth), buf);
                write(child_host_list[i].wr_pipe_fd, buf, len);
                fsync(child_host_list[i].wr_pipe_fd);
            }

            // init player record
            PlayerRecord player_record_list[8];
            for ( int i = 0; i < 8; i++) {
                player_record_list[i].player_id = player_id_list[i];
                player_record_list[i].score = 0;
            }
            run_game(child_host_list, depth, player_record_list);

            calc_rank(player_record_list);

            char buf[BUFSIZ];
            char *p = buf;
            p += snprintf(buf, BUFSIZ, "%d\n", random_key);
            for ( int i = 0; i < 8; i++) {
                p += snprintf(p, BUFSIZ, "%d %d\n", player_record_list[i].player_id, player_record_list[i].rank);
            }
            write(write_fifo_fd, buf, strlen(buf));
            fsync(write_fifo_fd);
        }

        clean_child(child_host_list);

        close(read_fifo_fd);
        close(write_fifo_fd);

    } else if ( depth == CHILD_HOST_DEP ) {
        Child leaf_host_list[2];
        fork_child(leaf_host_list, NULL, depth, argv);

        while ( 1 ) {
            int player_id_list[4];
            read_player_id(player_id_list, 4, STDIN_FILENO);
            if ( player_id_list[0] == -1 ) {
                for ( int i = 0; i < 2; i++) {
                    char *msg = "-1 -1\n";
                    write(leaf_host_list[i].wr_pipe_fd, msg, strlen(msg));
                    fsync(leaf_host_list[i].wr_pipe_fd);
                }
                break;
            }

            for ( int i = 0; i < 2; i++) {
                char buf[BUFSIZ];
                int len = sublist(player_id_list, i * (4 >> depth), i * (4 >> depth) + (4 >> depth), buf);
                write(leaf_host_list[i].wr_pipe_fd, buf, len);
                fsync(leaf_host_list[i].wr_pipe_fd);
            }

            run_game(leaf_host_list, depth, NULL);
        }

        clean_child(leaf_host_list);
    } else if ( depth == LEAF_HOST_DEP ) {
        while ( 1 ) {
            int player_id_list[2];
            read_player_id(player_id_list, 2, STDIN_FILENO);
            if ( player_id_list[0] == -1 ) {
                break;
            }

            Child player_list[2];

            fork_child(player_list, player_id_list, depth, argv);

            run_game(player_list, depth, NULL);

            clean_child(player_list);
        }
    }

    return EXIT_SUCCESS;
}

void read_player_id(int player_id_list[], int n, int fd) {
    char buf[BUFSIZ];
    char *p = buf;
    read(fd, p, BUFSIZ);
    for ( int i = 0; i < n; i++) {
        player_id_list[i] = strtol(p, &p, 10);
    }
}

int sublist(int list[], int L, int R, char buf[]) {
    char *ptr = buf;
    for ( int i = L; i < R; i++)
        ptr += snprintf(ptr, BUFSIZ, "%d%c", list[i], " \n"[i==R-1]);
    return (ptr - buf);
}

void fork_child(Child child_list[], int player_id_list[], int depth, char *argv[]) {
    for ( int i = 0; i < 2; i++) {
        // pipe
        int pfd[2][2];
        int pip_res1 = pipe(pfd[0]);  // parent read, child write
        int pip_res2 = pipe(pfd[1]);  // parent write, child read
        if ( pip_res1 == -1 || pip_res2 == -1 )
            ERR_EXIT("pipe");

        // fork
        child_list[i].pid = fork();
        if ( child_list[i].pid == -1 ) {
            ERR_EXIT("fork");
        } else if ( child_list[i].pid == 0 ) {
            // child
            close(pfd[0][0]);
            dup2(pfd[0][1], 1);
            close(pfd[0][1]);

            close(pfd[1][1]);
            dup2(pfd[1][0], 0);
            close(pfd[1][0]);

            if ( depth != LEAF_HOST_DEP ) {
                char next_dep[4];
                snprintf(next_dep, 4, "%d", depth + 1);
                execl("./host", "host", argv[1], argv[2], next_dep, NULL);
            } else {
                char buf[4];
                snprintf(buf, 4, "%d", player_id_list[i]);
                execl("./player", "player", buf, NULL);
            }

        } else {
            // parent
            close(pfd[0][1]);
            child_list[i].rd_pipe_fd = pfd[0][0];

            close(pfd[1][0]);
            child_list[i].wr_pipe_fd = pfd[1][1];
        }
    }
}

void run_game(Child child_list[], int depth, void *extra) {
    PlayerRecord *player_record_list = (PlayerRecord*)extra;
    int id_2_idx[32];
    for ( int i = 0; depth == 0 && i < 8; i++)
        id_2_idx[ player_record_list[i].player_id ] = i;

    for ( int round = 1; round <= ROUND_NUM; round++) {
        // read result from two child hosts
        int player_id[2], money[2];
        char buf[BUFSIZ];
        read(child_list[0].rd_pipe_fd, buf, BUFSIZ);
        sscanf(buf, "%d %d", &player_id[0], &money[0]);

        read(child_list[1].rd_pipe_fd, buf, BUFSIZ);
        sscanf(buf, "%d %d", &player_id[1], &money[1]);
        // compare two results
        int winner_id, win_money;
        if ( money[0] > money[1] ) {
            winner_id = player_id[0];
            win_money = money[0];
        } else {
            winner_id = player_id[1];
            win_money = money[1];
        }

        if ( depth == 0 ) {
            // if dep == 0: update player score and write winner to 2 child
            ++player_record_list[ id_2_idx[winner_id] ].score;
            if ( round != ROUND_NUM ) {
                for ( int i = 0; i < 2; i++) {
                    int len = sprintf(buf, "%d\n", winner_id);
                    write(child_list[i].wr_pipe_fd, buf, len);
                    fsync(child_list[i].wr_pipe_fd);
                }
            }
        } else {
            // if dep > 0: write winner, money to stdout and read final winner from stdin and write final winner to 2 child
            int len = sprintf(buf, "%d %d\n", winner_id, win_money);
            write(STDOUT_FILENO, buf, len);
            fsync(STDOUT_FILENO);

            if ( round != ROUND_NUM ) {
                int len = read(STDIN_FILENO, buf, BUFSIZ);
                for ( int i = 0; i < 2; i++) {
                    write(child_list[i].wr_pipe_fd, buf, len);
                    fsync(child_list[i].wr_pipe_fd);
                }
            }
        }
    }
}

int cmp(const void *a, const void *b) {
    int x = (*(PlayerRecord**)a)->score, y = (*(PlayerRecord**)b)->score;
    return (x < y) - (x > y);
}

void calc_rank(PlayerRecord player_record_list[]) {
    PlayerRecord* ptr[8];
    for ( int i = 0; i < 8; i++)
        ptr[i] = &player_record_list[i];
    qsort(ptr, 8, sizeof(PlayerRecord*), cmp);
    ptr[0]->rank = 1;
    for ( int i = 1; i < 8; i++)
        ptr[i]->rank = (ptr[i]->score == ptr[i-1]->score) ? ptr[i-1]->rank : i + 1;
}

void clean_child(Child child_list[]) {
    for ( int i = 0; i < 2; i++) {        
        int status;
        waitpid(child_list[i].pid, &status, 0);

        close(child_list[i].rd_pipe_fd);
        close(child_list[i].wr_pipe_fd);
    }
}

player.c

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

const char *const usage_msg = "usage: ./player [player_id]";

const int ROUND_NUM = 10;

void ERR_EXIT(char *msg) { perror(msg); exit(128); }

void flush_fsync(FILE *stream) { fflush(stream); fsync(fileno(stream)); }

void read_winner_id() {
    int winner_id;
    scanf("%d", &winner_id);
}

void tell_host_money(int player_id, int money) {
    printf("%d %d\n", player_id, money);
    flush_fsync(stdout);
}

int main(int argc, char *argv[])
{
    if ( argc != 2 ) {
        // the number of arguments should be exactly 1
        fprintf(stderr, usage_msg);
        exit(2);
    }

    const int player_id = atoi(argv[1]);
    const int money = player_id * 100;

    for ( int round = 1; round <= ROUND_NUM; ++round) {
        if ( round > 1 )
            read_winner_id();

        tell_host_money(player_id, money);
    }

    return EXIT_SUCCESS;
}