typedef struct NvmeCmd {
    uint8_t     opcode; // 操作码
    uint8_t     fuse; // 组合操作FUSE
    uint16_t    cid; // [15:14]传输数据的方式(PSDT，PRP还是SGL) [13:10]保留 [9:8]组合操作FUSE
    uint32_t    nsid; // 命令空间标识NSID
    uint64_t    res1; // 保留
    uint64_t    mptr; // 元数据指针mptr,只有在命令有元数据，并且元数据没有与数据的逻辑块交织时有效，并且元数据的地址标识方式由cdw0.psdt决定
    uint64_t    prp1;
    uint64_t    prp2;
    // 数据指针dptr
    uint32_t    cdw10;
    uint32_t    cdw11;
    uint32_t    cdw12;
    uint32_t    cdw13;
    uint32_t    cdw14;
    uint32_t    cdw15;
    // 上面的cdw在具体命令中被指定含义
} NvmeCmd;

typedef struct NvmeCqe {
    union {
        struct {
            uint32_t    result;
            uint32_t    rsvd;
        } n;
        uint64_t res64;
    };
    uint16_t    sq_head; // 完成队列头指针
    uint16_t    sq_id; // 完成队列表示
    uint16_t    cid;
    uint16_t    status;
} NvmeCqe;

uint16_t nvme_create_cq(FemuCtrl *n, NvmeCmd *cmd)
{
    ...
}

uint16_t nvme_init_cq(NvmeCQueue *cq, FemuCtrl *n, uint64_t dma_addr,
    uint16_t cqid, uint16_t vector, uint16_t size, uint16_t irq_enabled,
    int contig)
{
    ...
}

uint16_t nvme_create_sq(FemuCtrl *n, NvmeCmd *cmd)
{
    ...
}

uint16_t nvme_init_sq(NvmeSQueue *sq, FemuCtrl *n, uint64_t dma_addr,
    uint16_t sqid, uint16_t cqid, uint16_t size, enum NvmeQueueFlags prio,
    int contig)
{
    ...
}

static uint16_t nvme_rw(FemuCtrl *n, NvmeNamespace *ns, NvmeCmd *cmd,
    NvmeRequest *req)
{
    // 解析出nvme提交队列项到NvmeReq数据结构里
    // 检查cmd，slba，nlb等参数合理性
    NvmeRwCmd *rw = (NvmeRwCmd *)cmd;
    ... 
    err = femu_nvme_rw_check_req(n, ns, cmd, req, slba, elba, nlb, ctrl, data_size, meta_size);

    // 根据req中的参数，通过prp1和prp2获取DMA传输的数据块地址
    if (nvme_map_prp(&req->qsg, &req->iov, prp1, prp2, data_size, n)) {
        nvme_set_error_page(n, req->sq->sqid, cmd->cid, NVME_INVALID_FIELD,
            offsetof(NvmeRwCmd, prp1), 0, ns->id);
        return NVME_INVALID_FIELD | NVME_DNR;
    }

    // 在后端内存存/取数据
    ret = femu_rw_mem_backend_bb(&n->mbe, &req->qsg, data_offset, req->is_write);
}

void nvme_process_sq_io(void *opaque, int index_poller){
    // 更新sq_head_db，生成新的nvme_io_cmd
    ...
}

static void nvme_post_cqe(NvmeCQueue *cq, NvmeRequest *req){\
    // 更新完成队列尾部命令寄存器（cq_tail_db）和执行中断服务例程（isr）
    ...
}

// process.c
int do_wait(int child_pid){
  // handle with waiting child proc
  current->waiting_pid = child_pid;
  from_ready_to_blocked(current);
  schedule();
  return child_pid;
}

int do_fork( process* parent){
  alloc_proc(child);
  init_proc(child);

  child->status = READY;
  child->parent = parent;
  from_blocked_to_ready( child );
  return child->pid;
}

int free_process( process* proc ) {
  // we set the status to ZOMBIE, but cannot destruct its vm space immediately.
  // since proc can be current process, and its user kernel stack is currently in use!
  // but for proxy kernel, it (memory leaking) may NOT be a really serious issue,
  // as it is different from regular OS, which needs to run 7x24.
  proc->status = ZOMBIE;
  remove_from_blocked_queue(proc);
  remove_from_ready_queue(proc);

  return 0;
}

// syscall.c
long do_syscall(long a0, long a1, long a2, long a3, long a4, long a5, long a6, long a7){
  insert_to_ready_queue(current);
}

// sched.c
void schedule() {
  // 检查父进程等待的子进程是否已经zombie，如果是，则将父进程重新投入运行（重置waiting_pid, status）
  if (blocked_queue_head){
    for(process* p = blocked_queue_head; p != NULL; p = p->queue_next){
      if(procs[p->waiting_pid].status == ZOMBIE){
        p->waiting_pid = -1;
        from_blocked_to_ready(p);
      }
    }
  }

  if ( !ready_queue_head ){
    int should_shutdown = 1;

    for( int i=0; i<NPROC; i++ )
      if( (procs[i].status != FREE) && (procs[i].status != ZOMBIE) ){
        should_shutdown = 0;
        sprint( "ready queue empty, but process %d is not in free/zombie state:%d\n", 
          i, procs[i].status );
      }

    if( should_shutdown ){
      sprint( "no more ready processes, system shutdown now.\n" );
      shutdown( 0 );
    }else{
      panic( "Not handled: we should let system wait for unfinished processes.\n" );
    }
  }

  current = ready_queue_head;
  assert( current->status == READY );
  ready_queue_head = ready_queue_head->queue_next;

  current->status = RUNNING;
  sprint( "going to schedule process %d to run.\n", current->pid );
  switch_to( current );
}

struct dentry *lookup_final_dentry(const char *path, struct dentry **parent, char *miss_name) {
  // sprint("lookup_final_dentry: %s\n", path);
  int hartid = (int)read_tp();

  char path_copy[MAX_PATH_LEN];
  strcpy(path_copy, path);

  // 处理直接文件名，转为相对路径
  if(path_copy[0] != '.' && path_copy[0] != '/'){
    str_insert_to_head(path_copy, "./");
  }

  // split the path, and retrieves a token at a time.
  // note: strtok() uses a static (local) variable to store the input path
  // string at the first time it is called. thus it can out a token each time.
  // for example, when input path is: /RAMDISK0/test_dir/ramfile2
  // strtok() outputs three tokens: 1)RAMDISK0, 2)test_dir and 3)ramfile2
  // at its three continuous invocations.
  int flag = 0;
  char *token = strtok(path_copy, "/");
  struct dentry* this = *parent;
  struct dentry* cwd = NULL;
  if(current[hartid] != NULL){
    cwd = current[hartid]->pfiles->cwd;
  }

  while (token != NULL) {
    if(strcmp(token, "..") == 0){
      if(cwd == NULL){
        panic("lookup_final_dentry: proc not init\n");
        return NULL;
      }
      if(flag == 0){
        if(cwd == vfs_root_dentry){
          panic("already in root\n");
          return NULL;
        }
        (*parent) = cwd->parent;       
        flag = 1;
      }else{
        if((*parent) == vfs_root_dentry){
          panic("already in root\n");
          return NULL;
        }
        (*parent) = (*parent)->parent;
      }
      this = (*parent);
    }else if(strcmp(token, ".") == 0){
      if(cwd == NULL){
        panic("lookup_final_dentry: proc not init\n");
        return NULL;
      }
      if(flag == 0){
        (*parent) = cwd;
        flag = 1;
      }
      this = (*parent);  
    }else{
      // function return subdir's dentry
      this = hash_get_dentry((*parent), token);

      if (this == NULL) {
        // function return subdir's dentry
        this = alloc_vfs_dentry(token, NULL, *parent);

        // get subdir's vinode
        struct vinode *found_vinode = viop_lookup((*parent)->dentry_inode, this);

        // dentry not in hash && vinode not in disk
        // return miss
        if (found_vinode == NULL) {
          // not found in both hash table and directory file on disk.
          free_page(this);
          strcpy(miss_name, token);
          return NULL;
        }

        // dentry not in hash && vinode in disk
        // ensure dentry and vinode in hash
        struct vinode *same_inode = hash_get_vinode(found_vinode->sb, found_vinode->inum);
        if (same_inode != NULL) {
          // the vinode is already in the hash table (i.e. we are opening another hard link)
          this->dentry_inode = same_inode;
          same_inode->ref++;
          free_page(found_vinode);
        } else {
          // the vinode is not in the hash table
          this->dentry_inode = found_vinode;
          found_vinode->ref++;
          hash_put_vinode(found_vinode);
        }
        hash_put_dentry(this);
      }
      flag = 1;
      *parent = this;
    }

    // get next token
    token = strtok(NULL, "/");
  }
  return this;
}

typedef struct page_dentry{
  uint64 va_page;
  uint64 pa_page;
}page_dentry;

page_dentry* page_dir;

typedef struct malloc_dentry{
  uint64 va_start;
  uint64 va_end;
}malloc_dentry;

malloc_dentry* malloc_dir;

// syscall.c
uint64 do_malloc(int n){
  // 在没有已分配页面时
  if(current->num_page == 0){
    // 需要num_page页,alloc后map,加入表中
    int page_need = ROUNDUP(n, PGSIZE) / PGSIZE;
    if(alloc_n_page(page_need) == 0){
      panic("page alloc error\n");
    }

    // 添加malloc表
    uint64 va_start = current->page_dir[0].va_page;
    if(current->num_malloc + 1 > MAX_MALLOC_IN_HEAP){
      panic("malloc error\n");
    }
    add_to_malloc_dir(va_start, va_start + n);
    // print_malloc_dir();
    return va_start;
  }

  uint64 va_page_start = current->page_dir[0].va_page;
  uint64 va_page_end = current->page_dir[current->num_page - 1].va_page + PGSIZE;

  // 首先检查头是否可用
  int front_offset = current->malloc_dir[0].va_start - va_page_start;
  if(front_offset >= n){
    add_to_malloc_dir(va_page_start, va_page_start + n);
    // print_malloc_dir();
    return va_page_start;
  }

  // 检查空隙是否可用
  if(current->num_malloc >= 2){
    for(int i = 0; i < current->num_malloc - 1; i++){
      int gap = current->malloc_dir[i + 1].va_start - current->malloc_dir[i].va_end;
      if(gap >= n){
        uint64 new_va_start = current->malloc_dir[i].va_end;
        add_to_malloc_dir(new_va_start, new_va_start + n);
        // print_malloc_dir();
        return new_va_start;
      }
    }
  }

  // 使用末尾，先填入malloc表，（不够时）再去alloc page并map
  uint64 new_va_start = current->malloc_dir[current->num_malloc - 1].va_end;
  add_to_malloc_dir(new_va_start, new_va_start + n);
  // print_malloc_dir();

  int rear_offset = va_page_end - new_va_start;
  if(rear_offset < n){
    int page_need = ROUNDUP((n - rear_offset), PGSIZE) / PGSIZE;
    if(alloc_n_page(page_need) == 0){
      panic("page alloc error\n");
    }
  }
  return new_va_start;
}

void do_free(uint64 va){
  int index;
  if((index = find_malloc_dir(va)) == -1){
    panic("free error\n");
  }
  remove_from_malloc_dir(index);

  // 注意到这里 free 的处理时简化过的，即 malloc 放生后，我们先不返回页面，只有在进程 exit 后，我们统一 free 所有被 malloc 占用的 page 并清空两个 dir。
}

int alloc_n_page(int n){
  if(current->num_page + n > MAX_PAGE_IN_HEAP){
    return 0;
  }
  for(int i = 0; i < n; i++){
    uint64 pa = (uint64)alloc_page();
    user_vm_map((pagetable_t)current->pagetable, g_ufree_page, PGSIZE, pa, prot_to_type(PROT_WRITE | PROT_READ, 1));
    add_to_page_dir(g_ufree_page, pa);
    g_ufree_page += PGSIZE;
  }
  return 1;
}

void add_to_page_dir(uint64 va_page, uint64 pa_page);
void sort_page_dir();
void add_to_malloc_dir(uint64 va_start, uint64 va_end);
void sort_malloc_dir();
int find_malloc_dir(uint64 va);
void remove_from_malloc_dir(int index);