/**
 * 等待队列
 * */
typedef struct {
    // 等待队列的头结点(哨兵节点)
    list_entry_t wait_head;
} wait_queue_t;

struct proc_struct;

/**
 * 等待队列节点项

 * */
typedef struct {
    // 关联的线程
    struct proc_struct *proc;
    // 唤醒标识
    uint32_t wakeup_flags;
    // 该节点所属的等待队列
    wait_queue_t *wait_queue;
    // 等待队列节点
    list_entry_t wait_link;
} wait_t;

#define le2wait(le, member)         \
    to_struct((le), wait_t, member)

// 初始化wait_t等待队列项
void wait_init(wait_t *wait, struct proc_struct *proc);
// 初始化等待队列
void wait_queue_init(wait_queue_t *queue);
// 将wait节点项插入等待队列
void wait_queue_add(wait_queue_t *queue, wait_t *wait);
// 将wait项从等待队列中移除
void wait_queue_del(wait_queue_t *queue, wait_t *wait);
// 获取等待队列中wait节点的下一项
wait_t *wait_queue_next(wait_queue_t *queue, wait_t *wait);
// 获取等待队列中wait节点的前一项
wait_t *wait_queue_prev(wait_queue_t *queue, wait_t *wait);
// 获取等待队列的第一项
wait_t *wait_queue_first(wait_queue_t *queue);
// 获取等待队列的最后一项
wait_t *wait_queue_last(wait_queue_t *queue);
// 等待队列是否为空
bool wait_queue_empty(wait_queue_t *queue);
// wait项是否在等待队列中
bool wait_in_queue(wait_t *wait);

// 将wait项从等待队列中删除（如果存在的话）
#define wait_current_del(queue, wait)                                       \
    do {                                                                    \
        if (wait_in_queue(wait)) {                                          \
            wait_queue_del(queue, wait);                                    \
        }                                                                   \
    } while (0)

#endif /* !__KERN_SYNC_WAIT_H__ */

// 将等待队列中的wait项对应的线程唤醒
void wakeup_wait(wait_queue_t *queue, wait_t *wait, uint32_t wakeup_flags, bool del);
// 将等待队列中的第一项对应的线程唤醒
void wakeup_first(wait_queue_t *queue, uint32_t wakeup_flags, bool del);
// 将等待队列中的所有项对应的线程全部唤醒
void wakeup_queue(wait_queue_t *queue, uint32_t wakeup_flags, bool del);
// 令对应wait项加入当前等待队列;令当前线程阻塞休眠，挂载在该等待队列中
void wait_current_set(wait_queue_t *queue, wait_t *wait, uint32_t wait_state);

/**
 * 信号量

 * */
typedef struct {
    // 信号量值
    int value;
    // 信号量对应的等待队列
    wait_queue_t wait_queue;
} semaphore_t;

/**
 * 初始化信号量
 * */
void
sem_init(semaphore_t *sem, int value) {
    sem->value = value;
    // 初始化等待队列
    wait_queue_init(&(sem->wait_queue));
}

/**
 * 信号量down操作 扣减信号量

 * 当信号量value不足时将当前线程阻塞在信号量上，等待其它线程up操作时将其唤醒

 * */
static __noinline uint32_t __down(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    // 暂时关闭中断，保证信号量的down操作是原子操作
    local_intr_save(intr_flag);
    if (sem->value > 0) {
        // 信号量对应的value大于0，还有权使用
        sem->value --;
        local_intr_restore(intr_flag);
        return 0;
    }

    // 信号量对应的value小于等于0，需要阻塞当前线程
    wait_t __wait, *wait = &__wait;
    // 令当前线程挂在信号量的阻塞队列中
    wait_current_set(&(sem->wait_queue), wait, wait_state);
    // 恢复中断，原子操作结束
    local_intr_restore(intr_flag);

    // 当前线程进入阻塞状态了，进行一次调度
    schedule();

    local_intr_save(intr_flag);
    // 唤醒后，原子操作将当前项从信号量的等待队列中删除
    wait_current_del(&(sem->wait_queue), wait);
    local_intr_restore(intr_flag);

    if (wait->wakeup_flags != wait_state) {
        // 如果等待线程唤醒的标识与之前设置的参数wait_state不一致，将其状态返回给调用方做进一步判断
        return wait->wakeup_flags;
    }
    return 0;
}

/**
 * 信号量up操作 增加信号量或唤醒被阻塞在信号量上的一个线程（如果有的话）
 * */
static __noinline void __up(semaphore_t *sem, uint32_t wait_state) {
    bool intr_flag;
    // 暂时关闭中断，保证信号量的up操作是原子操作
    local_intr_save(intr_flag);
    {
        wait_t *wait;
        if ((wait = wait_queue_first(&(sem->wait_queue))) == NULL) {
            // 信号量的等待队列为空，说明没有线程等待在该信号量上

            // 信号量value加1
            sem->value ++;
        }
        else {
            assert(wait->proc->wait_state == wait_state);
            // 将等待队列中的对应等待线程唤醒
            wakeup_wait(&(sem->wait_queue), wait, wait_state, 1);
        }
    }
    local_intr_restore(intr_flag);
}

#define N 5 /* 哲学家数目 */
#define LEFT (i-1+N)%N /* i的左邻号码 */
#define RIGHT (i+1)%N /* i的右邻号码 */
#define THINKING 0 /* 哲学家正在思考 */
#define HUNGRY 1 /* 哲学家想取得叉子 */
#define EATING 2 /* 哲学家正在吃面 */
#define TIMES  4 /* 吃4次饭 */
#define SLEEP_TIME 10

void check_sync(void){
    int i;

    //check semaphore 信号量解决哲学家就餐问题
    sem_init(&mutex, 1);
    for(i=0;i<N;i++){
        sem_init(&s[i], 0);
        int pid = kernel_thread(philosopher_using_semaphore, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_semaphore failed.\n");
        }
        philosopher_proc_sema[i] = find_proc(pid);
        set_proc_name(philosopher_proc_sema[i], "philosopher_sema_proc");
    }

    。。。 条件变量(管程)解决哲学家就餐问题(暂时忽略)
}


//---------- philosophers problem using semaphore ----------------------
int state_sema[N]; /* 记录每个人状态的数组 */
/* 信号量是一个特殊的整型变量 */
semaphore_t mutex; /* 临界区互斥 */
semaphore_t s[N]; /* 每个哲学家一个信号量 */

/**
 * 哲学家线程主体执行逻辑
 * */
int philosopher_using_semaphore(void * arg) /* i：哲学家号码，从0到N-1 */
{
    int i, iter=0;
    i=(int)arg;
    cprintf("I am No.%d philosopher_sema\n",i);
    while(iter++<TIMES)
    { /* 无限循环 */
        cprintf("Iter %d, No.%d philosopher_sema is thinking\n",iter,i); /* 哲学家正在思考 */
        // 使用休眠阻塞来模拟思考(哲学家线程阻塞N秒)
        do_sleep(SLEEP_TIME);
        // 哲学家尝试着去拿左右两边的叉子(如果没拿到会阻塞)
        phi_take_forks_sema(i); 
        /* 需要两只叉子，或者阻塞 */
        cprintf("Iter %d, No.%d philosopher_sema is eating\n",iter,i); /* 进餐 */
        // 使用休眠阻塞来模拟进餐(哲学家线程阻塞N秒)
        do_sleep(SLEEP_TIME);
        // 哲学家就餐结束，将叉子放回桌子。

        // 当发现之前有临近的哲学家尝试着拿左右叉子就餐时却没有成功拿到，尝试着唤醒对应的哲学家
        phi_put_forks_sema(i); 
        /* 把两把叉子同时放回桌子 */
    }
    cprintf("No.%d philosopher_sema quit\n",i);
    return 0;    
}

/**
 * 哲学家i拿起左右叉子
 */
void phi_take_forks_sema(int i) /* i：哲学家号码从0到N-1 */
{ 
    // 拿叉子时需要通过mutex信号量进行互斥，防止并发问题(进入临界区)
    down(&mutex);
    // 记录下哲学家i饥饿的事实(执行phi_take_forks_sema尝试拿叉子，说明哲学家i进入了HUNGRY饥饿状态)
    state_sema[i]=HUNGRY;
    // 试图同时得到左右两只叉子
    phi_test_sema(i);
    // 离开临界区(唤醒可能阻塞在mutex上的其它线程)
    up(&mutex);
    // phi_test_sema中如果成功拿到叉子进入了就餐状态，会先执行up(&s[i])，再执行down(&s[i])时便不会阻塞
    // 反之，如果phi_test_sema中没有拿到叉子，则down(&s[i])将会令哲学家i阻塞在信号量s[i]上
    down(&s[i]);
}
/**
 * 哲学家i放下左右叉子
 */
void phi_put_forks_sema(int i) /* i：哲学家号码从0到N-1 */
{ 
    // 放叉子时需要通过mutex信号量进行互斥，防止并发问题(进入临界区)
    down(&mutex); /* 进入临界区 */
    // 哲学家进餐结束(执行phi_put_forks_sema放下叉子，说明哲学家已经就餐完毕，重新进入THINKING思考状态)
    state_sema[i]=THINKING;
    // 当哲学家i就餐结束，放下叉子时。需要判断左、右临近的哲学家在自己就餐的这段时间内是否也进入了饥饿状态，却因为自己就餐拿走了叉子而无法同时获得左右两个叉子。

    // 为此哲学家i在放下叉子后需要尝试着判断在自己放下叉子后，左/右临近的、处于饥饿的哲学家能否进行就餐,如果可以就唤醒阻塞的哲学家线程，并令其进入就餐状态(EATING)
    phi_test_sema(LEFT); /* 看一下左邻居现在是否能进餐 */
    phi_test_sema(RIGHT); /* 看一下右邻居现在是否能进餐 */
    up(&mutex); /* 离开临界区q(唤醒可能阻塞在mutex上的其它线程) */
}

/**
 * 判断哲学家i是否可以拿起左右叉子
 */
void phi_test_sema(i) /* i：哲学家号码从0到N-1 */
{ 
    // 当哲学家i处于饥饿状态(HUNGRY),且其左右临近的哲学家都没有在就餐状态(EATING)
    if(state_sema[i]==HUNGRY&&state_sema[LEFT]!=EATING
            &&state_sema[RIGHT]!=EATING)
    {
        // 哲学家i饿了(HUNGRY)，且左右两边的叉子都没人用。

        // 令哲学家进入就餐状态（EATING）
        state_sema[i]=EATING;
        // 唤醒阻塞在对应信号量上的哲学家线程(当是哲学家线程i自己执行phi_test_sema(i)时，则信号量直接加1，抵消掉phi_take_forks_sema中的down操作，代表直接拿起叉子就餐成功而不用进入阻塞态)
        up(&s[i]);
    }
} 

/**
 * 条件变量
 * */
typedef struct condvar{
    // 条件变量相关的信号量，用于阻塞/唤醒线程
    semaphore_t sem;        // the sem semaphore  is used to down the waiting proc, and the signaling proc should up the waiting proc
    // 等待在条件变量之上的线程数
    int count;              // the number of waiters on condvar
    // 拥有该条件变量的monitor管程
    monitor_t * owner;      // the owner(monitor) of this condvar
} condvar_t;

/**
 * 管程
 * */
typedef struct monitor{
    // 管程控制并发的互斥锁（应该被初始化为1的互斥信号量）
    semaphore_t mutex;      // the mutex lock for going into the routines in monitor, should be initialized to 1
    // 管程内部协调各并发线程的信号量（线程可以通过该信号量挂起自己，其它并发线程或者被唤醒的线程可以反过来唤醒它）
    semaphore_t next;       // the next semaphore is used to down the signaling proc itself, and the other OR wakeuped waiting proc should wake up the sleeped signaling proc.
    // 休眠在next信号量中的线程个数
    int next_count;         // the number of of sleeped signaling proc
    // 管程所属的条件变量（可以是数组，对应n个条件变量）
    condvar_t *cv;          // the condvars in monitor
} monitor_t;

/**
 * 初始化管程

 * */
void     
monitor_init (monitor_t * mtp, size_t num_cv) {
    int i;
    assert(num_cv>0);
    mtp->next_count = 0;
    mtp->cv = NULL;
    // 管程的互斥信号量值设为1（初始化时未被锁住）
    sem_init(&(mtp->mutex), 1); //unlocked
    // 管程的协调信号量设为0，当任何一个线程发现不满足条件时，立即阻塞在该信号量上
    sem_init(&(mtp->next), 0);
    // 为条件变量分配内存空间（参数num_cv指定管程所拥有的条件变量的个数）
    mtp->cv =(condvar_t *) kmalloc(sizeof(condvar_t)*num_cv);
    assert(mtp->cv!=NULL);
    // 构造对应个数的条件变量
    for(i=0; i<num_cv; i++){
        mtp->cv[i].count=0;
        // 条件变量信号量初始化时设置为0，当任何一个线程发现不满足条件时，立即阻塞在该信号量上
        sem_init(&(mtp->cv[i].sem),0);
        mtp->cv[i].owner=mtp;
    }
}

// Suspend calling thread on a condition variable waiting for condition Atomically unlocks 
// mutex and suspends calling thread on conditional variable after waking up locks mutex. Notice: mp is mutex semaphore for monitor's procedures
/**
 * 条件变量阻塞等待操作
 * 令当前线程阻塞在该条件变量上，等待其它线程将其通过cond_signal将其唤醒。

 * */
void
cond_wait (condvar_t *cvp) {
    //LAB7 EXERCISE1: YOUR CODE
    cprintf("cond_wait begin:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
    /*
     *         cv.count ++;
     *         if(mt.next_count>0)
     *            signal(mt.next)
     *         else
     *            signal(mt.mutex);
     *         wait(cv.sem);
     *         cv.count --;
     */

    // 阻塞在当前条件变量上的线程数加1
    cvp->count++;
    if(cvp->owner->next_count > 0)
        // 对应管程中存在被阻塞的其它线程

        // 唤醒阻塞在对应管程协调信号量next中的线程
        up(&(cvp->owner->next));
    else
        // 如果对应管程中不存在被阻塞的其它线程
        // 释放对应管程的mutex二元信号量
        up(&(cvp->owner->mutex));
    // 令当前线程阻塞在条件变量上
    down(&(cvp->sem));
    // down返回，说明已经被再次唤醒，条件变量count减1
    cvp->count --;
    cprintf("cond_wait end:  cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

// Unlock one of threads waiting on the condition variable. 
/**
 * 条件变量唤醒操作
 * 解锁（唤醒）一个等待在当前条件变量上的线程
 * */
void 
cond_signal (condvar_t *cvp) {
    //LAB7 EXERCISE1: YOUR CODE
    cprintf("cond_signal begin: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
    /*
     *      cond_signal(cv) {
     *          if(cv.count>0) {
     *             mt.next_count ++;
     *             signal(cv.sem);
     *             wait(mt.next);
     *             mt.next_count--;
     *          }
     *       }
     */
    // 如果等待在条件变量上的线程数大于0
    if(cvp->count>0) {
        // 需要将当前线程阻塞在管程的协调信号量next上，next_count加1
        cvp->owner->next_count ++;
        // 令阻塞在条件变量上的线程进行up操作，唤醒线程
        up(&(cvp->sem));
        // 令当前线程阻塞在管程的协调信号量next上

        // 保证管程临界区中只有一个活动线程，先令自己阻塞在next信号量上；等待被唤醒的线程在离开临界区后来反过来将自己从next信号量上唤醒
        down(&(cvp->owner->next));
        // 当前线程被其它线程唤醒从down函数中返回，next_count减1
        cvp->owner->next_count --;
    }
    cprintf("cond_signal end: cvp %x, cvp->count %d, cvp->owner->next_count %d\n", cvp, cvp->count, cvp->owner->next_count);
}

void check_sync(void){
    int i;

    //check semaphore
    sem_init(&mutex, 1);
    for(i=0;i<N;i++){
        sem_init(&s[i], 0);
        int pid = kernel_thread(philosopher_using_semaphore, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_semaphore failed.\n");
        }
        philosopher_proc_sema[i] = find_proc(pid);
        set_proc_name(philosopher_proc_sema[i], "philosopher_sema_proc");
    }

    //check condition variable
    monitor_init(&mt, N);
    for(i=0;i<N;i++){
        state_condvar[i]=THINKING;
        int pid = kernel_thread(philosopher_using_condvar, (void *)i, 0);
        if (pid <= 0) {
            panic("create No.%d philosopher_using_condvar failed.\n");
        }
        philosopher_proc_condvar[i] = find_proc(pid);
        set_proc_name(philosopher_proc_condvar[i], "philosopher_condvar_proc");
    }
}

void phi_take_forks_condvar(int i) {
    // 拿叉子时需要通过mutex信号量进行互斥，防止并发问题(进入临界区)
    down(&(mtp->mutex));
//--------into routine in monitor--------------
    // LAB7 EXERCISE1: YOUR CODE
    // I am hungry
    // try to get fork
    // I am hungry
    // 记录下哲学家i饥饿的事实(执行phi_take_forks_condvar尝试拿叉子，说明哲学家i进入了HUNGRY饥饿状态)
    state_condvar[i]=HUNGRY;
    // 试图同时得到左右两只叉子
    phi_test_condvar(i);
    if (state_condvar[i] != EATING) {
        // state_condvar[i]状态不为EATING，说明phi_test_condvar尝试拿左右叉子进餐失败
        cprintf("phi_take_forks_condvar: %d didn't get fork and will wait\n",i);
        // 等待阻塞在管程的条件变量cv[i]上
        cond_wait(&mtp->cv[i]);
    }
//--------leave routine in monitor--------------
    if(mtp->next_count>0){
        // 当离开管程临界区时，如果发现存在线程等待在mtp->next上

        // 在当前实验中，执行到这里的当前线程可能是阻塞在cond_wait中被其它线程唤醒的，对应线程是通过phi_test_condvar的cond_signal操作唤醒当前线程的

        // 执行cond_signal时为了保证管程临界区内不存在并发的线程访问，在唤醒其它线程时，会把自己阻塞在管程的next信号量上，等待此时离开临界区的线程将其唤醒
        up(&(mtp->next));
    }else{
        // 当离开管程临界区时,没有其它线程等待在mtp->next上，直接释放管程的互斥锁mutex即可(唤醒可能阻塞在mutex上的其它线程)
        up(&(mtp->mutex));
    }
}

void phi_put_forks_condvar(int i) {
    // 放叉子时需要通过mutex信号量进行互斥，防止并发问题(进入临界区)
    down(&(mtp->mutex));

//--------into routine in monitor--------------
    // LAB7 EXERCISE1: YOUR CODE
    // I ate over
    // test left and right neighbors
    // I ate over
    // 哲学家进餐结束(执行phi_put_forks_condvar放下叉子，说明哲学家已经就餐完毕，重新进入THINKING思考状态)
    state_condvar[i]=THINKING;
    // test left and right neighbors
    // 当哲学家i就餐结束，放下叉子时。需要判断左、右临近的哲学家在自己就餐的这段时间内是否也进入了饥饿状态，却因为自己就餐拿走了叉子而无法同时获得左右两个叉子。

    // 为此哲学家i在放下叉子后需要尝试着判断在自己放下叉子后，左/右临近的、处于饥饿的哲学家能否进行就餐,如果可以就唤醒阻塞的哲学家线程，并令其进入就餐状态(EATING)
    phi_test_condvar(LEFT); // 看一下左邻居现在是否能进餐
    phi_test_condvar(RIGHT); // 看一下右邻居现在是否能进餐

//--------leave routine in monitor--------------
    // lab7的参考答案
    if(mtp->next_count>0){
        cprintf("execute here mtp->next_count>0 \n\n\n\n\n\n");
        up(&(mtp->next));
    }else{
        cprintf("execute here mtp->next_count=0 \n\n\n\n\n");
        up(&(mtp->mutex));
    }

    // 个人认为放叉子和取叉子的情况并不一样，不会出现mtp->next_count>0的情况，这里只需要释放互斥锁即可（如果这里理解的有问题，还请指正）

    // 当放叉子的线程在phi_put_forks_condvar中离开管程临界区时，只有两种情况

    // 1. 没有发现邻居可以进餐，自身不会被阻塞
    // 2. 发现有邻居之前被拿不到叉子阻塞了，现在可以进餐了，phi_test_condvar中的cond_signal会暂时令自己阻塞在next信号量上
    // 但是很快被自己叫醒的相邻的哲学家线程在被唤醒后一离开临界区就会将自己唤醒，在cond_signal被唤醒后的操作中mtp->next_count会自减，而变为0
    //
    // 以上两种情况下，由于管程本身最外面有一个mutex互斥信号量，所以不会出现两个线程同时阻塞在next信号量中，因此也就不会出现参考答案中mtp->next_count>0的情况

    // up(&(mtp->mutex));
} 

void phi_test_condvar (i) {
    // 当哲学家i处于饥饿状态(HUNGRY),且其左右临近的哲学家都没有在就餐状态(EATING)
    if(state_condvar[i]==HUNGRY&&state_condvar[LEFT]!=EATING
            &&state_condvar[RIGHT]!=EATING) {
        cprintf("phi_test_condvar: state_condvar[%d] will eating\n",i);
        // 哲学家i饿了(HUNGRY)，且左右两边的叉子都没人用。

        // 令哲学家进入就餐状态（EATING）
        state_condvar[i] = EATING ;
        cprintf("phi_test_condvar: signal self_cv[%d] \n",i);
        // 唤醒阻塞在对应信号量上的哲学家线程
        cond_signal(&mtp->cv[i]) ;
    }
}