syscall

eax保存子功能号。参数从左到右依次放入通用寄存器 ebx、ecx、edx、esi、edi 。
下面是一个三个参数的简略版本的 syscall：

#define _syscall3(NUMBER,ARG1,ARG2,ARG3) ({       \
        int retval;                     \
        asm volatile(                   \
        "int $0x80;"                    \
        : "=a"(retval)                  \
        : "0"(NUMBER),"b"(ARG1),"c"(ARG2),"d"(ARG3) \
        );                              \
        retval;                         \
    })

让我们来到调用链的源头，用户进程调用了一个操作系统接口。
syscall.h 里放功能号。
syscall.c 里放跟用户相关的一些接口。这些接口参数为功能号，调用相关接口，实际上是调用_syscall*，产生int 0x80中断。

enum SYSCALL {
    SYS_GETPID,
    SYS_WRITE,
    SYS_MALLOC,
    SYS_FREE
};

uint_32 getpid(void) {
    return _syscall0(SYS_GETPID);
}
uint_32 write(char* str) {
    return _syscall1(SYS_WRITE,str);
}

在 IDT表中额外添加针对 int 0x80 的中断处理函数。

void init_idt_desc(void)
{
    for (int i=0;i<IDT_DESC_NUMBER;i++) {
        make_idt_desc(&gate_desc_table[i],INT_ATTR_DPL0,idt_desc_addr[i]);
    }
    make_idt_desc(&gate_desc_table[0x80],INT_ATTR_DPL3,syscall_handler);
}

在 kernel.S 里添加该中断函数的描述符。

section .text
global syscall_handler
syscall_handler:
    push 0
    push ds
    push es
    push fs
    push gs
    pushad
    push 0x80 ;占位而已，0x80实际没意义，与前面压中断号保持队形罢了
    
    push ebx
    push ecx
    push edx
    call [syscall_table + eax*4]
    add esp,12

    mov [esp+0x20],eax
    jmp int_exit

在对 int 0x80 的中断处理程序中，根据传入的eax(系统调用子功能号) 调用 syscall_table 里的 syscall 。
syscall_table 是一个储藏函数（系统调用）地址数组。

#define SYSCALL_NR  10
typedef void* syscall;
syscall syscall_table[SYSCALL_NR];

syscall_table 内的系统函数,那些真正干活的家伙们都需要在 syscall_table 内进行注册。

void syscall_init(void)
{
    put_str("syscall init start\n");
    syscall_table[SYS_GETPID] = sys_getpid;
    syscall_table[SYS_WRITE]  = sys_write;
    syscall_table[SYS_MALLOC] = sys_malloc;
    syscall_table[SYS_FREE]   = sys_free;
    put_str("syscall init done\n");
}

中断会调用真正的系统函数。

uint_32 sys_getpid(void){
    struct task_struct* cur = running_thread();
    return cur->pid;
}
uint_32 sys_write(char* str)
{
    console_put_str(str);
    return strlen(str);
}

printf

printf的幕后黑手是 vsprintf 和 itoa 。
其中，itoa将数字转为要求进制的数字字符串，将(*buf_ptr)指向目标字符串的下一个位置。如果 val / base != 0 ，证明当前位前面还有位。调用 itoa(q,buf_ptr,base); ，搞定前面的数字位，然后将当前位简单转化成字符后写入。

static void itoa(uint_32 val,char** buf_ptr,uint_8 base)
{
    ASSERT(base<=16);
    uint_32 m = val % base;
    uint_32 q = val / base;
    if (q) {
        itoa(q,buf_ptr,base);
    }
    char c;
    if (m>=0 && m<=9) {
        c = m + '0';
    } else if (m>=10 && m<=15) {
        c = m-10 + 'a';
    }
    *((*buf_ptr)++) = c;
}

vsprintf格式化字符串。它的实现需要我们在代码中，根据所提供的格式化字符串相继取出可变参数。
所以我们需要一串宏操作栈里的数据
进行一个

#define _INTSIZEOF(n)  ((sizeof(n) + sizeof(int)-1) & ~(sizeof(int)-1))
#define va_list char*
#define va_start(ap,v) ( ap = (va_list)&v + _INTSIZEOF(v) )
#define va_arg(ap,T) ( *(T*)((ap += _INTSIZEOF(T)) - _INTSIZEOF(T)) )
#define va_end(ap)  ( ap = NULL )

前置知识：在 32 位系统中，堆栈每个数据单元的大小为 4 字节。小于等于 4 字节的数据，比如字节、字、双字和布尔型，在堆栈中都是占 4 个字节的；大于 4 字节的数据在堆栈中占4字节整数倍的空间。
_INTSIZEOF(n) ：关于4字节（或者说是sizeof(int)）向上取整
void va_start(va_list ap, v) ：初始化ap(argument pointer) , 指向固定参数后第一个可变参数。
type va_arg(va_list ap, type) ：返回ap当前指向的元素,并将 ap 指向下一个arg。
void va_end(va_list ap) ：做最后的收尾工作。

uint_32 vsprintf(char* buf,const char* format,va_list ap)
{
    const char* fmtp = format;
    char* bufp = buf;

    uint_32 val;
    char* arg_str;
    while(*fmtp)
    {
        if (*fmtp != '%'){
            *bufp = *(fmtp++);
            ++bufp;
            continue;
        }
        char next_char = *(++fmtp);
        switch(next_char)
        {
            case 'x':
                val = va_arg(ap,int);
                itoa(val,&bufp,16);
                ++fmtp;
                break;
            case 'd':
                val = va_arg(ap,int);
                if (val < 0) {
                    *(bufp++) = '-';
                    val = -val;
                }
                itoa(val,&bufp,10);
                ++fmtp;
                break;
            case 'c':
                *(bufp++) = va_arg(ap,char);
                ++fmtp;
                break;
            case 's':
                arg_str = va_arg(ap,char*);
                strcpy(bufp,arg_str);
                bufp += strlen(arg_str);
                ++fmtp;
                break;
        }
    }

    return strlen(buf);
}

printf 做好初始化ap的工作 , 调用 vsprintf , 填满事先准备好的缓冲区。

uint_32 printf(const char* format,...)
{
    char buf[1024]={0};
    uint_32 retLen;
    va_list ap;
    va_start(ap,format);
    retLen = vsprintf(buf,format,ap);
    va_end(ap);
    write(buf);
    return retLen;
}

内存分配与释放

内存分配
mem_block_desc 中最重要的是 free_list ，它是所有可用空闲block的链表。

struct mem_block_desc {
    uint_32 block_size;
    uint_32 blocks_per_arena;
    struct list free_list;
};

我们总共有7种不同的 mem_block_desc ，它们的不同点在于 mem_block 的大小不同。
让吾做一个世界一流水准的比喻：mem_block_desc数组里存放不同种类的mem_block_desc，就像一个长长的葡萄藤。而这葡萄藤上有DESC_CNT个不同的结点(mem_block_desc)，结点下面挂着的一串葡萄一般大，但不同结点的下面的葡萄大小不一（free_list）。
mem_block_desc 显然需要初始化，ker_block_desc 在mem_init内，用户进程的就在创建用户进程时顺便初始化了就行。

void mem_init(void)
{
    put_str("memory init start\n");
    uint_32 tot_mem = *((uint_32*)0x800);
    mem_pool_init(tot_mem);
/******************************************************/
    block_desc_init(ker_block_desc);
/******************************************************/
    put_str("memory init done\n");
}

void block_desc_init(struct mem_block_desc* descs)
{
    uint_32 b_sz = 16;
    for (uint_8 desc_idx=0 ; desc_idx < DESC_CNT ; desc_idx++)
    {
        descs[desc_idx].block_size = b_sz;
        descs[desc_idx].blocks_per_arena = (PAGESIZE - sizeof(struct arena))/b_sz;
        list_init(&descs[desc_idx].free_list);
        b_sz *= 2;
    }
}

void process_execute(char* name,void* filename)
{
/* 。前省略 。 */
    usr_vaddr_init(pcb);
/* 。后省略 。 */
}

void usr_vaddr_init(struct task_struct* pcb)
{
    uint_32 btmp_pgsize = DIV_ROUND_UP((0xc0000000 - USR_VADDR_START)/PAGESIZE/8,PAGESIZE);

    struct virt_addr* usr_vaddr = &pcb->usrprog_vaddr;
    usr_vaddr->vaddr_start = USR_VADDR_START;
    usr_vaddr->btmp.bits     = get_kernel_pages(btmp_pgsize);
    usr_vaddr->btmp.map_size = (0xc0000000-USR_VADDR_START)/PAGESIZE/8;
    bit_init(&pcb->usrprog_vaddr.btmp);
    block_desc_init(pcb->usr_block_desc);
}

分配内存就是改变元信息的登记信息，分为虚拟内存和物理内存两部分。使用的物理内存需要被记录已分配，那记录在哪里呢？因此要决定哪个物理内存池；虚拟内存被提前分配好串在 特定 mem_block_desc 的free_list中，因此需要根据 size 选择适当的 mem_block_desc 。
借助 free_list，可以了解哪些虚拟内存是空闲的。我们可以很轻易地取走里面的一个元素，取走后，这个世界上便又少了一个空闲的内存块，多了一个被利用的内存块，这就相当于malloc了一块内存。sys_malloc 的过程其实就是取走 mem_block_desc的 free_list 中的元素用于使用的过程。
情况一：分配的size超出了1024字节，尺寸太大以至于根本没有与之匹配的内存块。这时我们就不把它放入任何一种 mem_block_desc中，而直接叫调用者把分配来的原材料（页框）拿走得了。
情况二：size未超1024字节。此时 free_list 内可能缺少内存块，需要分配一个新页，将里面一块块的 block 给串入free_list中。

void* sys_malloc(uint_32 size)
{
    enum pool_flag pf;
    struct pool* m_pool;
    struct mem_block_desc* desc;

    struct task_struct* cur = running_thread();
    if (cur->pdir == NULL) {
        pf = PF_KERNEL;
        m_pool = &kernel_pool;
        desc = ker_block_desc;
    } else {
        pf = PF_USER;
        m_pool = &user_pool;
        desc = cur->usr_block_desc;
    }

    struct arena* arena;
    struct mem_block* blk;
    lock_acquire(&m_pool->lock);
    if (size > m_pool->pool_size)  return NULL;
    // 情况一：
    if (size > 1024)
    {
        uint_32 page_cnt = DIV_ROUND_UP(size + sizeof(struct arena),PAGESIZE);
        arena = malloc_page(pf,page_cnt);
        ASSERT(arena != NULL);
        memset(arena,0,PAGESIZE*page_cnt);

        arena->blk_desc = NULL;
        arena->cnt      = page_cnt;
        arena->large    = true;

        lock_release(&m_pool->lock);
        return (void*)(arena + 1);
    }

    // 情况二：
    uint_32 desc_nr;
    for (desc_nr=0 ; desc_nr<DESC_CNT ; desc_nr++) {
        if (size <= desc[desc_nr].block_size) break;
    }
    desc = &desc[desc_nr];
    // free_list 没货
    if (list_empty(&desc->free_list))
    {
        arena = malloc_page(pf,1);
        arena->blk_desc = desc;
        arena->cnt      = desc->blocks_per_arena;
        arena->large    = false;

        enum intr_status old_status = intr_disable();   //操作list需要原子操作
        for (uint_32 idx=0 ; idx < desc->blocks_per_arena ; idx++)
        {
            blk = arena2block(arena,idx);
            list_append(&desc->free_list,&blk->elm);
        }
        intr_set_status(old_status);
    }

    // 将 block 从 free_list 移除，相当于分配出去了
    blk = mem2entry(struct mem_block,list_pop(&desc->free_list),elm);
    memset(blk,0,desc->block_size);
    arena = block2arena(blk);
    arena->cnt--;

    lock_release(&m_pool->lock);
    return (void*)blk;
}

让我们聚焦在填充 free_list 的过程：
malloc_page 返回pcnt个空闲的虚拟地址连续的内存块的起始。我们把 malloc_page 的虚拟页划分为许多块，加入到 free_list 中去。

void* malloc_page(enum pool_flag pf,uint_32 pcnt)
{
    ASSERT(pcnt>0 && pcnt<64000); //按照用户和内核各250MB来计算
    uint_32 cnt = pcnt;
    struct pool* m_pool = pf==PF_KERNEL? &kernel_pool : &user_pool;
    void* vaddr_start = get_vaddr(pf,pcnt);
    if (vaddr_start == NULL){
        return NULL;
    }

    void* vaddr = vaddr_start;
    while (cnt--)
    {
        void* paddr = palloc(m_pool);
        if (paddr == NULL) {
            return NULL;
        }
        page_table_add(vaddr,paddr);
        vaddr =(void*)((uint_32)vaddr + PAGE_SIZE);
    }

    return vaddr_start;
}

然而，在 释放内存 时，需要释放指针指向的地方的内存，就是说要根据所指的地方把 mem_block 添加进 free_list ，这就没有那么容易了。
所以，我们需要在指针指向的地方额外记录一些信息，这个结构体称为 arena。

struct arena {
    struct mem_block_desc* blk_desc;
    uint_32 cnt;
    Bool large;
};

在分配的地方初始化 arena，以便释放。

释放内存
正常情况下，释放内存。只需将 mem_block 重新加入 mem_block_desc 里的free_list，表示该block再次空闲。

void sys_free(void* ptr)
{
    if (ptr == NULL){
        return ;
    }
    enum pool_flag pf;
    struct pool* m_pool;
    struct task_struct* cur = running_thread();
    if (cur->pdir == NULL) {
        pf = PF_KERNEL;
        m_pool = &kernel_pool;
    } else {
        pf = PF_USER;
        m_pool = &user_pool;
    }

    lock_acquire(&m_pool->lock);
    struct mem_block* b = ptr;
    struct arena* a = block2arena(b);
    if (a->blk_desc == NULL && a->large == true) {
        mfree_page(pf,a,a->cnt);
        lock_release(&m_pool->lock);
        return ;
    }

    ASSERT(a->blk_desc != NULL && a->large == false);
    struct mem_block_desc* desc = a->blk_desc;
    list_append(&desc->free_list,&b->elm);
    if (++a->cnt == desc->blocks_per_arena)
    {
        uint_32 idx;
        for (idx = 0 ; idx < desc->blocks_per_arena ; idx++)
        {
            struct mem_block* b = arena2block(a,idx);
            list_remove(&b->elm);
        }
        mfree_page(pf,a,1);
    }
    lock_release(&m_pool->lock);
}

有时需要释放整页内存，比如释放按页框申请的整片内存 以及 所有块中block都被加入free_list。
释放整页内存总共需要三个步骤：1.释放物理页 2.解除物理页与虚拟页的映射关系 3.释放虚拟页

void mfree_page(enum pool_flag pf,void* _vaddr,uint_32 pcnt)
{
    uint_32 cnt = 0;
    void* vaddr = _vaddr;
    uint_32 paddr = v2p(_vaddr);
    ASSERT((paddr % PAGESIZE)==0 && paddr >= 0x102000);
    while (cnt < pcnt) 
    {
        pfree(paddr);
        remove_pte(vaddr);
        vaddr = (void*)((uint_32)vaddr + PAGESIZE);
        paddr = v2p(vaddr); //物理地址不一定连续，不能直接加PAGESIZE，得根据vaddr求得
        cnt++;
    }

    vfree(pf,_vaddr,pcnt);
}

pfree 释放物理地址处的内存（释放内存就是把相关的bitmap置0）。通过物理内存的数值，我们可以推断出到底是在物理内存池还是在用户内存池。

void pfree(uint_32 paddr)
{
    uint_32 bit_idx;
    if (paddr >= user_pool.paddr_start) {
        bit_idx = (paddr - user_pool.paddr_start)/PAGESIZE;
        bitmap_set(&user_pool.btmp,bit_idx,0);
    } else {
        bit_idx = (paddr - kernel_pool.paddr_start)/PAGESIZE;
        bitmap_set(&kernel_pool.btmp,bit_idx,0);
    }
}

释放虚拟内存与释放物理内存十分类似，只要给出 内核/用户内存池，然后把相应的bitmap置零即可。

void vfree(enum pool_flag pf,void* vaddr,uint_32 pcnt)
{
    struct task_struct* cur = running_thread();
    uint_32 bit_idx_start;
    uint_32 cnt = 0;
    if (pf == PF_KERNEL) {
        bit_idx_start = ((uint_32)vaddr - ker_vaddr.vaddr_start)/PAGESIZE;
        while (cnt < pcnt) {
            bitmap_set(&ker_vaddr.btmp,bit_idx_start+cnt++,0);
        }
    } else {
        bit_idx_start = ((uint_32)vaddr - cur->usrprog_vaddr.vaddr_start)/PAGESIZE;
        while (cnt < pcnt) {
            bitmap_set(&cur->usrprog_vaddr.btmp,bit_idx_start+cnt++,0);
        }
    }
}

映射的关键是页表，解除映射关系其实就是修改页表，我们不需要将pte全部置0,只需要把 P位 置0即可。

void remove_pte(void* vaddr)
{
    uint_32 v = (uint_32)vaddr;
    uint_32* pte = pte_ptr(v);
    *pte &= ~PG_P;
}

参考资料：
操作系统真象还原
C++堆栈工作机制