只要我能过Extra就会更新的。

试题内容为作者考后回忆，仅供参考

LAB2 EXAM

题目

实现函数

u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va)

效果为将地址 ([begin_va,end_va)之间的pgdir的有效二级页表项中权限位和perm_mask交集不为空的清空，并且统计数量。

题目已经提示了参考page_remove,并且提示了page_decref,page_lookup,tlb_invalidate的知识，所以我们参考page_remove加上一个循环和对于权限位的判断即可

u_int page_conditional_remove(Pde *pgdir, u_int asid, u_int perm_mask, u_long begin_va, u_long end_va){
    Pte* ppte;
    struct Page * pp;
    int cnt=0;
    for(u_long i=begin_va;i<end_va;i+=PAGE_SIZE){
        if((pp=page_lookup(pgdir,i,&ppte))==NULL)
            continue;
        if(((*ppte ) & perm_mask)==0)
            continue;
        page_decref(pp);
        *ppte=0;
        cnt++;
        tlb_invalidate(asid,i);
    }
    return cnt;
}

LAB2 EXTRA

题目

实现malloc和free函数，提供了

#define HEAP_BEGIN 0x80400000
#define HEAP_SIZE 0x400000

#define MBLOCK_SIZE sizeof(struct MBlock)

#define MBLOCK_PREV(elm, field) (struct MBlock *)((elm)->field.le_prev) // place entry at first

struct MBlock {
    MBlock_LIST_entry_t mb_link;

    u_int size;    // size of the available space, if allocated, is the size of allocated space
    void *ptr;     // pointer to the begin of block, as a magic number to check for validity
    u_int free;    // 1 if block is free, 0 if the block is allocated
    u_int padding; // padding to make size of block multiple of 8
    char data[];   // data of the block, allocated for user
};

使用链表管理这部分内存，对于每次malloc，遍历链表找到第一个空闲空间大于等于要分配的size的块，然后根据剩余空间的大小决定将整个块分配还是分配正好大小的块并且分裂出一个新的块。
对于free，则是判断当前位置是否由malloc分配出来，并且保证可以通过简单的等式mp->ptr!=tmp->data进行判断，释放之后如果存在相连的空闲块，需要立即合并。

看起来很复杂，但是题面中给出了详细的实现方案，只要翻译成C语言代码即可。题目保证了不需要考虑释放空间的时候清空数据的问题，即，只要维护链表即可。
并不需要设计复杂的虚拟地址的转换等内容
需要注意，控制块本身是占据一定内存的，并且控制块和他所控制的内存是紧邻的。而Mbblock中的size是不包括Mbblock的内存的。

void insertBlock(struct MBlock * pre,void * va,u_int new_size){
    struct MBlock *new_Block=(struct MBlock *) va;
    new_Block->size=new_size-MBLOCK_SIZE;
    new_Block->ptr=new_Block->data;
    new_Block->free=1;
    LIST_INSERT_AFTER(pre,new_Block,mb_link);
}
void *malloc(size_t size) {
    /* Your Code Here (1/2) */
    size=ROUND(size,8);
    struct MBlock* tmp=NULL;
    LIST_FOREACH(tmp,&mblock_list,mb_link){
        //printk("%d %d %d\n",tmp->size,size,tmp->free);
        if(tmp->size>=size&&tmp->free==1){
            size_t res=tmp->size-size;
        //  printk("\nTRY TO ALLOC\n");
            if(res<MBLOCK_SIZE+8){
                tmp->ptr=tmp->data;
                tmp->free=0;
                //printk("%u\n",tmp->data);
                return tmp->data;
            }else{
                tmp->ptr=tmp->data;
                size_t pre_size=tmp->size;
                tmp->free=0;
                tmp->size=size;
                insertBlock(tmp,((void *)(tmp->data))+size,pre_size-size);
                //printk("%u\n",tmp->data);
                return tmp->data;
            }
        }
    }
    //printk("FAIL TO ALLOC");
    return NULL;
}

void free(void *p) {
    /* Your Code Here (2/2) */
    if(!(p<=HEAP_BEGIN+HEAP_SIZE&&p>=HEAP_BEGIN+MBLOCK_SIZE))
        return ;
    p-=MBLOCK_SIZE;
    struct MBlock* tmp=(struct MBlock *)p;
    if(tmp->ptr!=tmp->data||tmp->free==1) return ;
    tmp->free=1;
    struct MBlock * past=LIST_NEXT(tmp,mb_link);
    if(past!=NULL){
        if(past->free!=0){
            tmp->size+=MBLOCK_SIZE+past->size;
            LIST_REMOVE(past,mb_link);
        }
    }
    if(LIST_FIRST(&mblock_list)!=tmp){
        struct MBlock * pre=MBLOCK_PREV(tmp,mb_link);
        if(pre->free!=0){
            pre->size+=MBLOCK_SIZE+tmp->size;
            LIST_REMOVE(tmp,mb_link);
            tmp=pre;
        }
    }

    return ;
}

总结

题目难度并不高，exam是已有的函数加上几行，而extra是给出了实现方案的。
只要正确的理解了地址的构成等相关内容，都是很好解决的。