位图bitmap

整体设计

位图本质上就是一个数组
一个位图可以表示一个空间的内存块分配情况
位图上的每一位的值，代表相应单位空间是否空闲(0空闲，1已使用)
例如：内存位图一般1位代表1页(4KB)，硬盘位图一般1页代表1扇区(512KB)

数据结构

struct bitmap{
    uint32_t btmp_bytes_len;    //位图字节长度
    uint8_t* bits;              //位图起始地址
};

函数表

/*
@brief: 初始化位图，将位图btmp全部清0
@param: 略
@retval:无
*/
void bitmap_init(struct bitmap* btmp);

/*
@brief: 返回btmp中第bit_idx位的状态
@param: 略
@retval:略
*/
bool bitmap_scan_test(struct bitmap* btmp,uint32_t bit_idx);

/*
@brief: 寻找btmp中第一个 连续cnt位为0(相当于连续cnt个页空闲)
@param: 略
@retval:成功返回偏移地址，失败返回-1
*/
int bitmap_scan(struct bitmap* btmp,uint32_t cnt);

/*
@brief: 设置btmp中第bit_idx位为value
@param: 略
@retval:无
*/
void bitmap_set(struct bitmap* btmp,uint32_t bit_idx,int8_t value);

SimpleOS-7-文件系统

Posted on 2024-01-01 Edited on 2024-01-02

整体设计方案

数据结构

/* 分区结构:一个分区就是一个文件系统 */
struct partition {
    uint32_t start_lba;		    // 起始扇区
    uint32_t sec_cnt;		    // 扇区数
    struct disk* my_disk;	    // 分区所属的硬盘
    struct list_elem part_tag;	// 用于队列中的标记，用于将分区形成链表进行管理
    char name[8];		        // 分区名称

    struct super_block* sb;	    // 本分区的超级块
    struct bitmap block_bitmap;	// 块位图
    struct bitmap inode_bitmap;	// inode位图
    struct list open_inodes;	// 本分区打开的inode缓冲队列
};

/* 超级块：文件系统元信息的配置文件 */
struct super_block {
    uint32_t magic;		            // 用来标识文件系统类型,支持多文件系统的操作系统通过此标志来识别文件系统类型

    uint32_t sec_cnt;		        // 本分区总共的扇区数
    uint32_t inode_cnt;		        // 本分区中inode数量
    uint32_t part_lba_base;	        // 本分区的起始lba地址

    uint32_t block_bitmap_lba;	    // 块位图本身起始扇区地址
    uint32_t block_bitmap_sects;    // 扇区位图本身占用的扇区数量

    uint32_t inode_bitmap_lba;	    // i结点位图起始扇区lba地址
    uint32_t inode_bitmap_sects;	// i结点位图占用的扇区数量

    uint32_t inode_table_lba;	    // i结点表起始扇区lba地址
    uint32_t inode_table_sects;	    // i结点表占用的扇区数量

    uint32_t data_start_lba;	    // 数据区开始的第一个扇区号
    uint32_t root_inode_no;	        // 根目录所在的I结点号
    uint32_t dir_entry_size;	    // 目录项大小

    uint8_t  pad[460];		        // 加上460字节,凑够512字节1扇区大小
    
} __attribute__ ((packed));

/* inode：文件的实质 */
struct inode {
    uint32_t i_no;                  // inode编号

    uint32_t i_size;                //当此inode是普通文件时,i_size是指普通文件大小
                                    //若此inode是目录,i_size是指该目录下所有目录项大小之和*/

    uint32_t i_open_cnts;           // 记录此文件被打开的次数
    bool write_deny;	            // 写文件不能并行,进程写文件前检查此标识
                        
    uint32_t i_sectors[13];         // i_sectors[0-11]是直接块,
                                    // i_sectors[12]用来存储一级间接块指针
    struct list_elem inode_tag;     //用于文件缓冲队列中
};

/* 文件结构 */
struct file
{
    uint32_t fd_pos;        // 记录当前文件操作的偏移地址，文件尾为-1
    uint32_t fd_flag;       // 文件操作标识符
    struct inode *fd_inode;
};

/* 目录结构 */
struct dir {
    struct inode* inode;   
    uint32_t dir_pos;	    // 记录在目录内的偏移
    uint8_t dir_buf[512];   // 目录的数据缓存
};

/* 目录项结构 */
struct dir_entry {
    char filename[MAX_FILE_NAME_LEN];   // 普通文件或目录名称
    uint32_t i_no;		                // 普通文件或目录对应的inode编号
    enum file_types f_type;	            // 文件类型
};

函数表

fs/fs.c

//------------------------文件系统初始化相关函数---------------------------------------

/*
@brief: 在磁盘上搜索文件系统，落没有则格式化分区创建文件系统
@detail:1.遍历整个磁盘，对每个已存在的分区创建文件系统
        2.挂载默认分区
        3.将当前分区的根目录打开
        4.初始化文件表
@param: 无
@retval:无
*/
void filesys_init();

/*
@brief: 初始化part分区的元信息,创建文件系统
@detail:初始化超级块、空闲块位图、inode位图、inode数组、根目录并全部写入磁盘
@param: 略
@retval:无
*/
static void partition_format(struct partition* part);

/*
@brief: 挂载名为part_name(arg)的分区
@detail:将硬盘中的超级块、空闲块位图、inode位图全部读取到内存中
        给cur_part赋值
@param: 略
@retval:无
*/
static bool mount_partition(struct list_elem *pelem, int arg);

//------------------------文件系统初始化相关函数---------------------------------------


//------------------------路径解析相关函数-----------------------

/*
@brief: 将最上层路径名称解析出来，存储到name_store,并返回子路径
@param: 略
@retval:无
*/
static char *path_parse(char *pathname, char *name_store);

/*
@brief: 返回路径深度
@param: 略
@retval:无
*/
int32_t path_depth_cnt(char *pathname);

/*
@brief: 搜索文件路径pathname,找到则返回其inode号,否则返回-1
@param: search_record:记录搜索过程中的父路径
@retval:无
@PS：   调用该函数后，会打开目标文件的父目录，并不会关闭，需要调用者关闭该目录
*/
static int search_file(const char *pathname, struct path_search_record *searched_record);

//------------------------路径解析相关函数-----------------------


//-------------------------系统调用-普通文件相关-------------------------

/*
@brief: 打开或创建普通文件
@detail：   1.先搜索该普通文件是否存在
            2.存在则打开，不存在则创建并打开
@param: flags:文件操作标识符
@retval:成功后,返回文件描述符,否则返回-1
*/
int32_t sys_open(const char *pathname, uint8_t flags);

/*
@brief: 关闭文件描述符fd指向的文件
@detail：   1.调用file_close()关闭普通文件;
            2.PCB->fd_table[fd]=-1;令文件描述符对应的数组可用
@param: flags:文件操作标识符
@retval:成功返回0,否则返回-1
*/
int32_t sys_close(int32_t fd)

/*
@brief: 将buf中连续count个字节写入文件描述符fd
@param: 略
@retval:成功则返回写入的字节数,失败返回-1
*/
int32_t sys_write(int32_t fd, const void *buf, uint32_t count);

/*
@brief: 从文件描述符fd指向的文件中读取count个字节到buf
@param: 略
@retval:若成功则返回读出的字节数,到文件尾则返回-1
*/
int32_t sys_read(int32_t fd, void *buf, uint32_t count);

/*
@brief: 重置用于文件读写操作的偏移指针(重置为:offset+文件指针位置)
@param: whence:文件指针位置标识符
        offset:相对于文件指针位置的偏移量
@retval:成功时返回新的偏移量,出错时返回-1
*/
int32_t sys_lseek(int32_t fd, int32_t offset, uint8_t whence);

/*
@brief: 删除普通文件(普通文件已打开则删除失败)
@param: 略
@retval:成功返回0,失败返回-1 
*/
int32_t sys_unlink(const char *pathname);
//-------------------------系统调用-普通文件相关-------------------------


//-------------------------系统调用-目录文件相关-------------------------

/*
@brief: 创建目录文件(并不打开)
@detail:1.申请inode位图，并同步到磁盘
        2.申请block位图，并同步到磁盘(先分配一个块就够用)
        3.往inode指向的数据块写入目录项'.'和'..'
        4.要将本目录的inode初始化，并同步到磁盘(无需申请内存空间)
        5.将关于本目录的目录项写入父目录数据块(写入磁盘)
        6.父目录inode更新大小并同步到磁盘
@param: pathname:目录文件路径
@retval:成功返回0,失败返回-1 
*/
int32_t sys_mkdir(const char *pathname);

/*
@brief: 打开目录文件，并返回目录指针
@detail:调用dir_open()来打开目录
        （目录打开只涉及part->open_inodes不涉及文件表、文件描述符数组等）
@param: 略
@retval:成功返回目录指针,失败返回-1 
*/
struct dir *sys_opendir(const char *name);

/*
@brief: 关闭目录
@detail:调用dir_close()来关闭目录
@param: 略
@retval:成功返回0,失败返回-1
*/
int32_t sys_closedir(struct dir *dir);

/*
@brief: 根据dir当前偏移位置，读取一个目录项，并更新偏移位置(调用dir_read()实现)
@param: 略
@retval:成功后返回其目录项地址,到目录尾时或出错时返回NULL
*/
struct dir_entry *sys_readdir(struct dir *dir);

/*
@brief: 把目录dir的指针dir_pos置0
@param: 略
@retval:无
*/
void sys_rewinddir(struct dir *dir);

/*
@brief: 删除空目录(调用dir_remove()实现)
@param: 略
@retval:成功时返回0,失败时返回-1
*/
int32_t sys_rmdir(const char *pathname);
//-------------------------系统调用-目录文件相关-------------------------


//-------------------------系统调用-cwd相关-------------------------

/*
@brief: 获得父目录的inode编号(利用目录项目'..')
@param: 略
@retval:无
*/
static uint32_t get_parent_dir_inode_nr(uint32_t child_inode_nr, void *io_buf);

/*
@brief: 在inode编号为p_inode_nr的目录中查找inode编号为c_inode_nr的子目录的名字，将名字存入缓冲区path. 
@param: 略
@retval:成功返回0,失败返-1
*/
static int get_child_dir_name(uint32_t p_inode_nr, uint32_t c_inode_nr, char *path, void *io_buf);

/*
@brief: 把当前工作目录绝对路径写入buf, size是buf的大小. 
@detail:根据PCB->cwd_inode_nr一层层向上追溯求得当前工作目录路径
@param: 略
@retval:成功返回buf,失败返NULL
*/
char *sys_getcwd(char *buf, uint32_t size);

/*
@brief: 更改当前工作目录为绝对路径path 
@detail:实质是修改PCB->cwd_inode_nr
@param: 略
@retval:成功则返回0,失败返回-1
*/
int32_t sys_chdir(const char *path);
//-------------------------系统调用-cwd相关-------------------------


//-------------------------系统调用-文件属性相关-------------------------
/*
@brief: 在buf中填充文件结构相关信息 
@param: 略
@retval:成功时返回0,失败返回-1
*/
int32_t sys_stat(const char *path, struct stat *buf);

//-------------------------系统调用-文件属性相关-------------------------


//------------------------转换函数----------------------
/*
@brief: 将文件描述符转化为文件表的下标
@param: 略
@retval:无
*/
static uint32_t fd_local2global(uint32_t local_fd);

//------------------------转换函数----------------------

fs/dir.c

/*
@brief: 打开根目录
@detail:1.利用inode_open()打开根目录
        2.并给root_dir赋值
@param: 略
@retval:无
*/
void open_root_dir(struct partition *part);

/*
@brief: 在分区part上打开节点号为inode_no的目录并返回目录指针 
@detail:1.利用inode_open()打开目录文件
        2.给目录结构pdir申请空间，初始化并返回
        （目录打开只涉及part->open_inodes不涉及文件表、文件描述符数组等）
@param: 略
@retval:无
*/
struct dir *dir_open(struct partition *part, uint32_t inode_no);

/*
@brief: 关闭目录
@detaili:1.利用inode_close()关闭目录，根目录不能被关闭
        2.释放目录结构dir的空间
@param: 略
@retval:无
*/
void dir_close(struct dir *dir);

/*
@brief: 在目录中寻找指定目录项
@detail:在part分区内的pdir目录内寻找包含name文件或目录的目录项
@param: 略
@retval:找到后返回true并将其目录项存入dir_e,否则返回false
*/
bool search_dir_entry(struct partition *part, struct dir *pdir, const char *name, struct dir_entry *dir_e);

/*
@brief: 在内存中初始化目录项p_de
@param: 略
@retval:无
*/
void create_dir_entry(char *filename, uint32_t inode_no, uint8_t file_type, struct dir_entry *p_de);

/*
@brief:     将目录项p_de写入父目录parent_dir中(直接写入磁盘)
@param:     io_buf:主调函数提供的缓冲区
@retval:    成功返回true，失败返回false
@PS：       父目录的inode.size更改过了，但并没有同步到磁盘的inode_table里！！
            调用者要负责把父目录的inode同步到磁盘
*/
bool sync_dir_entry(struct dir *parent_dir, struct dir_entry *p_de, void *io_buf);

/*
@brief: 把分区part目录pdir中关于inode_no的目录项删除（会将更新过的父目录inode写入磁盘）
@param: 略
@retval:成功返回true，失败返回false
*/
bool delete_dir_entry(struct partition *part, struct dir *pdir, uint32_t inode_no, void *io_buf);

/*
@brief: 根据dir当前偏移位置，读取一个目录项，并更新偏移位置
@param: 略
@retval:成功返回目录项，失败返回NULL
*/
struct dir_entry *dir_read(struct dir *dir);

/*
@brief: 判断目录是否为空
@detail:目录为空则代表目录中只含有.和..两个目录项
@param: 略
@retval:空返回true,非空返回false
*/
bool dir_is_empty(struct dir *dir);

/*
@brief: 移除目录child_dir
@detail:1.调用delete_dir_entry在父目录中移除本目录的目录项
        2.调用inode_release()回收本目录的inode
@param: 略
@retval:成功返回目录项，失败返回NULL
*/
int32_t dir_remove(struct dir *parent_dir, struct dir *child_dir);

fs/inode.c

/*
@brief: 打开并返回part分区里目标inode节点
        两个重要的功能：一个是打开inode、一个是返回inode节点
@detail:1.现在inode缓冲区队列中寻找该inode，若已打开则增加inode->i_open_cnts并返回inode
        2.没找到就去磁盘中寻找该inode读取到内存里，并放到inode缓冲区队列，返回inode
@param: part:目标分区
        inode_no:要打开的inode节点的i_no号
@retval:无
*/
struct inode *inode_open(struct partition *part, uint32_t inode_no);

/*
@brief: 关闭inode
@detail:1.减少inode->i_open_cnts
        2.inode->i_pen_cnts减少后若为0，则将从inode缓冲队列里去除，并释放为inode分配的空间
@param: 略
@retval:无
*/
void inode_close(struct inode *inode)

/*
@brief: 初始化new_inode，为其赋值
@param: 略
@retval:无
*/
void inode_init(uint32_t inode_no, struct inode *new_inode)


/*
@brief: 定位inode在扇区的位置
@detail:在part里获取inode所在的扇区和扇区内的偏移量并存到inode_pos中
@param: 略
@retval:无
*/
static void inode_locate(struct partition *part, uint32_t inode_no, struct inode_position *inode_pos);

/*
@brief: 将inode写入到磁盘的分区part中
@param: 略
@retval:无
*/
void inode_sync(struct partition *part, struct inode *inode, void *io_buf);


/*
@brief: 回收inode
@detail:1.回收分配给inode的所有block(修改block_bitmap)
        2.回收inode(修改inode_bitmap)
        3.调用inode_delete删除硬盘上的inode数据（可以不用这步）
        4.确保该inode完全关闭
@param: 略
@retval:无
*/
void inode_release(struct partition *part, uint32_t inode_no);

/*
@brief: 将硬盘分区part上的对应的inode清除(修改磁盘上的inode_table)
@param: inode_no:要清楚的inode号
@retval:无
*/
void inode_delete(struct partition *part, uint32_t inode_no, void *io_buf);

fs/file.c

//------------------------文件表 文件描述符数组 相关操作-----------------------

/*
@brief: 从文件表file_table中获取一个空闲位
@param: 无
@retval:成功返回文件表下标,失败返回-1 
@PS:如果file_table[fd_idx].fd_inode == NULL，则判断文件结构可用
*/
int32_t get_free_slot_in_global(void);

/*
@brief: 将全局描述符(文件表下标)安装到进程或线程自己的文件描述符数组fd_table中 
@param: globa_fd_idx:文件表的下标（全局文件描述符）
@retval:成功返回文件描述符(文件描述符数组的下标),失败返回-1
*/
int32_t pcb_fd_install(int32_t globa_fd_idx);

//------------------------文件表 文件描述符数组 相关操作-----------------------


//---------------------------位图操作-------------------------
/*
@brief: 从inode位图里分配一个inode结点 (内存操作)
@param: 略
@retval:返回节点号i_no(就是inode在位图中的位置)
*/
int32_t inode_bitmap_alloc(struct partition *part);

/*
@brief: 从block位图里分配1个空闲块(1扇区),返回其扇区地址(内存操作)
@param: 略
@retval:略
*/
int32_t block_bitmap_alloc(struct partition *part);

/*
@brief: 同步内存里的位图结构到磁盘上
@detail:将内存中bitmap第bit_idx位所在的512字节同步到硬盘
@param: btmp_type:标识是inode位图还是block位图
@retval:略
*/
void bitmap_sync(struct partition *part, uint32_t bit_idx, uint8_t btmp_type);
//---------------------------位图操作-------------------------


//-------------------------------普通文件相关操作--------------------------------
/*
@brief: 创建并打开普通文件(磁盘操作)
@detail:1.创建new_inode(修改inode位图、inode分配内存、inode初始化)
        2.修改父目录(对应目录项写入父目录(写入磁盘)，修改父目录inode.size)
        3.同步 父目录inode、new_inode、inode位图
        4.打开该文件(添加到file_table、PCB中的fd_table、Part中的open_inodes)
@param: flag:文件操作标识符
@retval:成功则返回文件描述符,否则返回-1
*/
int32_t file_create(struct dir *parent_dir, char *filename, uint8_t flag);

/*
@brief: 打开编号为inode_no的inode对应的普通文件
@detail:1.修改file_table
        2.修改PCB->fd_table
        3.调用inode_open()修改part->open_inodes
@param: 略
@retval:成功则返回文件描述符,否则返回-1
*/
int32_t file_open(uint32_t inode_no, uint8_t flag);

/*
@brief: 关闭文件结构
@detail:1.调用inode_close()修改part->open_inodes
        2. file->fd_inode = NULL; 使文件结构可用
@param: file:要关闭的文件结构
@retval:失败返回-1，成功返回0
@PS:没有将PCB中的文件描述符数组对应位置-1！！！
    调用者要负责将PCB->fd_table[]置-1
*/
int32_t file_close(struct file *file);

/*
@brief: 把buf中的count个字节写入file
@param: 略
@retval:成功则返回写入的字节数,失败则返回-1
*/
int32_t file_write(struct file *file, const void *buf, uint32_t count);

/*
@brief: 从文件file中读取count个字节写入buf
@param: 略
@retval:返回读出的字节数,若到文件尾则返回-1
*/
int32_t file_read(struct file *file, void *buf, uint32_t count);
//-------------------------------普通文件相关操作--------------------------------

关键函数说明

文件系统初始化函数

文件操作相关函数

工作路径相关函数

fs/file.c/file_create()

fs/file.c/file_write()

fs/file.c/file_read()

背景知识

inode、super_block、目录、目录项、超级块与文件系统布局

硬盘驱动

工具图表

文件系统布局

整体设计方案

内存管理模块整体方案如下：

物理内存池划分如下：

虚拟内存池划分如下：

数据结构

//物理内存池
struct pool{
    struct bitmap pool_bitmap;  //物理内存池位图
    uint32_t phy_addr_start;    //管理空间起始地址
    uint32_t pool_size;         //管理空间长度

    struct lock lock;           //进程申请物理内存时需要上锁
};

//虚拟内存池
struct virtual_addr{
    struct bitmap vaddr_bitmap; //虚拟内存池位图
    uint32_t vaddr_start;       //管理空间起始地址
};

/* 内存块 */
struct mem_block {
    struct list_elem free_elem;
};

/* 内存块描述符 */
struct mem_block_desc {
    uint32_t block_size;		 // 内存块大小
    uint32_t blocks_per_arena;	 // 本arena中可容纳此mem_block的数量.
    struct list free_list;	 // 目前可用的mem_block链表
};

/* 内存仓库arena元信息 */
struct arena {
    struct mem_block_desc* desc;	 // 此arena关联的mem_block_desc
    uint32_t cnt;
    bool large;		                // large为ture时,cnt表示的是页框数。否则cnt表示空闲mem_block数量
};

内存池提供以页为单位的内存空间
对于每一页内存空间都由元信息arena来组织，并将剩余空间切分成小块
每一个元信息arena组织的内存仓库都按照块的大小有着相应的mem_block_desc
由mem_block_desc中的free_list来串起所有同一大小的空闲内存块

函数表

kernel/memory.c

  //-------------------------------------内存系统初始化相关函数---------------------------

  /*
  @brief: 初始化内存相关数据结构(内存池、内存仓库、内存块描述符)
  @param: 无
  @retval:无
  */
  void mem_init();

  /*
  @brief: 内存池初始化(物理内核内存池、物理用户内存池、虚拟内核内存池)
  @param: all_mem:物理内存总量
  @retval:无
  */
  static void mem_pool_init(uint32_t all_mem);

  /*
  @brief: 初始化内存块描述符数组(管理7种不同的内存块描述符(16、32、64、128、256、512、1024))
  @param: desc_array：要初始化的内存块描述符数组
  @retval:无
  */
  void block_desc_init(struct mem_block_desc* desc_array);

  //-------------------------------------内存系统初始化相关函数---------------------------

  //-------------------------------------内存分配相关函数---------------------------

  /*
  @brief: 分配pg_cnt页的内存空间
  @param: pf:内存池类型标识符(内核/用户)
          pg_nct:申请分配的页数
  @retval:成功返回起始虚拟地址,失败返回NULL
  */
  void* malloc_page(enum pool_flags pf,uint32_t pg_cnt);

  /*
  @brief: 向虚拟内存池申请pg_cnt页的空间
  @param: pf:内存池类型标识符(内核/用户)
          pg_nct:申请分配的页数
  @retval:成功返回起始虚拟地址,失败返回NULL
  */
  static void* vaddr_get(enum pool_flags pf,uint32_t pg_cnt);

  /*
  @brief: 向物理内核/用户内存池申请1页空间，
  @param: m_pool:申请的物理内存池(用户/内核)
  @retval:成功返回地址起点，失败返回-1
  */
  static void* palloc(struct pool* m_pool);

  /*
  @brief: 建立从虚拟地址到物理地址的映射(以页为单位)(建立相应的页表/页目录)
  @param: _vaddr:虚拟地址
          _page_phyaddr:物理地址
  @retval:无
  */
  static void page_table_add(void* _vaddr,void* _page_phyaddr);

  /*
  @brief: 给内核分配pg_cnt页内存，
  @param: 略
  @retval:成功则返回虚拟地址，失败返回NULL
  */
  void* get_kernel_pages(uint32_t pg_cnt);

  /*
  @brief: 给用户分配pg_cnt页内存，
  @param: 略
  @retval:成功则返回虚拟地址，失败返回NULL
  */
  void* get_user_pages(uint32_t pg_cnt);

  /*
  @brief: 在堆(即内存池)中申请size字节内存(灵活申请)
  @param: 略
  @retval:无
  */
  void* sys_malloc(uint32_t size);

  /*
  @brief: 给指定虚拟地址分配一页内存
  @param: pf:内存池表示符
          vaddr:指定虚拟地址
  @retval:成功则返回虚拟地址，失败返回NULL
  */
  void* get_a_page(enum pool_flags pf,uint32_t vaddr);
  //-------------------------------------内存分配相关函数---------------------------
              
  //-------------------------------------内存回收相关函数---------------------------

  /*
  @brief: 释放 内核/用户 内存池种以虚拟地址vaddr为起点的cnt个物理页框 
  @param: pf:内存池标识符
          _vaddr:要回收的虚拟地址
          pg_cnt:要回收的页数
  @retval:无
  */
  void mfree_page(enum pool_flags pf, void* _vaddr, uint32_t pg_cnt);


  /*
  @brief: 将1张物理页回收到物理内存池，实质就是清除物理内存池中位图的位
  @param: pg_pyh_addr:要回收页的物理地址
  @retval:无
  */
  void pfree(uint32_t pg_phy_addr);

  /*
  @brief: 将以_vaddr起始的连续pg_cnt个虚拟页回收到虚拟内存池，实质就是清除虚拟内存池中位图的位
  @param: pf:内存池标识符
          _vaddr:要回收的虚拟地址
          pg_cnt:要回收的页数
  @retval:无
  */
  static void vaddr_remove(enum pool_flags pf, void* _vaddr, uint32_t pg_cnt)

  /*
  @brief: 解除页表中虚拟地址vaddr的映射,实质是将vaddr对应的pte存在位置0
  @param: 略
  @retval:无
  */
  static void page_table_pte_remove(uint32_t vaddr);

  /*
  @brief: 回收ptr指向的内存块(内存块大小由arena指出)
  @param: 略
  @retval:无
  */
  void sys_free(void* ptr);

  //-------------------------------------内存回收相关函数---------------------------

  //------------------------------工具函数-----------------------------------------

  /*
  @brief: 返回虚拟地址映射的物理地址 
  @param: 略
  @retval:略
  */
  uint32_t addr_v2p(uint32_t vaddr);

  /*
  @brief: 返回arena中第idx个内存块的地址
  @param: 略
  @retval:略
  */
  static struct mem_block* arena2block(struct arena* a, uint32_t idx);

  /*
  @brief: 返回内存块b所在的arena地址
  @param: 略
  @retval:略
  */
  static struct arena* block2arena(struct mem_block* b);

  /*
  @brief: 得到虚拟地址vaddr对应的pte指针
  @param: 略
  @retval:略
  */
  uint32_t* pte_ptr(uint32_t vaddr);

  /*
  @brief: 得到虚拟地址vaddr对应的pde指针
  @param: 略
  @retval:略
  */
  uint32_t* pde_ptr(uint32_t vaddr)

  //------------------------------工具函数-----------------------------------------

关键函数说明

kernel/memory.c/内存分配相关函数
kernel/memory.c/内存回收相关函数
kernel/memory.c/page_table_add()
kernel/memory.c/sys_malloc()

背景知识

pool-virtual_addr

arena-mem_block_desc

工具图表

SimpleOS-2-Boot

Posted on 2023-12-30 Edited on 2024-05-07

整体设计方案

如图电脑的启动后接力棒的第一棒从BIOS开始，第二棒MBR负责把硬盘上的loader加载到内存里，第三棒loader处理完5个子功能后把接力棒正式交给内核。

我们在本模块所做的事，就是构建具备上述功能的MBR以及loader。

在了解MBR和loader的设计之前请先了解实模式下低端物理内存1MB的布局

MBR设计

MBR只需要负责加载loader到相应位置即可

MBR的程序代码分为三个部分：

寄存器初始化（包括栈顶指针初始化）
调用函数loader_ready_proc()（寄存器传参）

PS：请先了解LBA28相关知识
loader_ready_proc()的具体实现（功能是装载loader,也就是把loader写入磁盘相应位置）

PS：请先了解磁盘写入相关知识
保证MBR一共512字节，并最后两字节必须是0x55和0xaa，使得BIOS能够检测并识别

loader设计

loader要负责做的事情可多了，大致可分为六个部分

数据段

loader程序的数据段里存放着GDT等重要数据结构，安排如下图所示
计算内存大小并存储到0xb00（也就是total_men_bytes标号处）

我们模仿Linux获取内存的方法，调用BIOS中断0x15的三个子功能（0xe820、0xe801、0x88）去获取内存（一种失败了就接着使用另外一种，直到成功）

0xb00则是我们安排在loader.S数据段的一个固定位置,当然如果你喜欢也可以存放在其他位置。

注意：我们使用BIOS中断0x15时，该中断会以ARDS数据结构（描述内存段大小的信息）的形式，返回数个ARDS，所以我们需要在loader.S中划分一块缓冲区用于临时存放返回的ARDS
从实模式切换到保护模式

PS：请先了解保护模式相关知识点,以及如何从实模式进入保护模式
构建内核页表页目录，开启分页机制

PS：请先了解分页机制

我们所要建立的满足可以自举证的分页模型如下图所示
1. 物理空间中低端1MB用于存放内核代码，紧接着0x100000~0x200000这1MB空间用于存放255个页表+1个页目录，每个页表/页目录都刚好是一个4KB自然页大小，每个页表项/页目录项则占4字节大小
2. 虚拟空间0x00~0x100000和0xc0000000~0xc0100000两个区间都被映射到物理空间的低端1MB内核代码区间
3. PD[1023]指向页目录本身，为的是实现在开启分页机制后还能正确访问页表和页目录
  
  如果虚地址高10位全为1、虚地址中10位全为0，就把PD[0]当成自己的页表项，最终指向物理页地址0x101000
  如果虚地址高10位全为1、虚地址中10位全为1，就把PD[1023]当成自己的页表项,最终指向物理页地址0x100000
  如果虚地址高10位全为1、虚地址中10位处于一定范围内，就把PD[768]~PD[1022]当成自己的页表项目，最终指向物理地址0x101000及以上空间
  
  总结出不变的规律：
  - 要获取页目录表物理地址：让虚位高20位地址全为1，低12位全为0，即0xfffff000。这就是页目录自身的起始物理地址
  - 要访问页目录中的页目录项，即获取页表物理地址：使虚拟地址为0xfffffxxx,其中xxx是页目录项的索引*4
  - 访问页表中的页表项:虚拟地址公式为 0x3ff<<22+中间10位<<12+低12位（中间10位是页表的索引，低12位为页表内的偏移地址）
加载kernel到内存中

将硬盘从0x9开始占据200扇区的kernel代码读取到内存0x70000起始处
初始化kernel

PS：请先了解加载并初始化内核相关知识以及elf文件格式

数据结构

无

函数表

boot/mbr.S

  /*
  @brief: 该函数负责把磁盘上的loader装载到内存里(汇编函数/寄存器传参)
  @param: loader_start_sector是loader的LBA28扇区地址
          loader_base_addr是内存起始地址
          sector_cnt是移动的扇区数目
  @retval:无
  */
  void loader_ready_proc(loader_start_sector,loader_base_addr,sector_cnt);

boot/loader.S

  /*
  @brief: 该函数负责5件事分布如下：(汇编函数)
          1. 计算内存并存储到0xb00
          2. 从实模式到保护模式
          3. 构建内核页表页目录，开启分页机制
          4. 加载kernel到内核中
          5. 初始化kernel
  @param: 无
  @retval:无
  */
  void loader_start();

关键函数说明

无

背景知识/工具图表

实模式下低端物理内存1MB布局

我们整个SimpleOS的代码实际上只会装载到0x500~0x9FBFF这块内存区间（包括两块空闲的可用区域，和一块由BIOS确定的MBR区域）
512字节的MBR将会被BIOS强制装载到0x7C00~0x7DFF，（MBR只负责加载loader，运行过一次就没用了，之后可以被其他代码覆盖）
2048字节的loader规划在可用区间0x900~0x1100（loader是内核的起点，安排在离0x500近一点的地方，为之后的内核文件腾出足够的空间。至于和0x500之间存在的一点间隔存储个人决策，可以忽略）
200扇区kernel.bin，将其装载在0x70000~0x89000可用区域,（内核代码应该装载在可用空间的尽可能高位，为内核映像文件腾出位置）
保护模式下一些虚地址分配
- 0xc0001500(虚地址)作为内核代码的入口
- 一般来说可用空间的上界限0xc009fc00是最好的栈顶，但是为了让内存的每一块都形成4KB的自然页，所以栈顶最好取4KB的整数倍，因此栈顶设置为0xc009f000
- 0xc009e000~0xc009f0004KB空间分配给内核主线程PCB
- 0xc009a000~0xc009e000这四个页的空间(可管理一共512MB空间)大小全给位图(物理内核内存池位图、物理用户内存池位图、虚拟内核内存池位图)

LBA28相关知识

LBA28是用28位比特来描述一个扇区的地址的一种方式

其中前24位分别写在3个8位寄存器LBAlow、LBAmid、LBAhigh，最后4位写在device寄存器里

磁盘写入相关知识

硬盘并行接口-PATA

PATA接口的线缆也称IDE线

一个主盘提供了两个IDE插槽，这两个插槽称为两个通道，IDE0叫Primary通道，IDE1叫Secondary通道

每一个IDE线都可以挂载两块硬盘，一个主盘(master),一个从盘(slave)

硬盘操作方法

当我们要读取硬盘时，我们要先在控制寄存器里写入读取命令字，然后才能从相关寄存器里读取到所需要的数据

而当我们需要写入硬盘时，我们要先在相关寄存器里写入数据，然后再向控制寄存器里写入写入命令字，即完成写入

硬盘控制器主要的端口寄存器

Command Block registers用于向硬盘驱动器写入命令字或者从硬盘控制器里活得硬盘状态

Control Block registers用于控制硬盘状态

data寄存器用于管理数据
Error寄存器用于记录失败时的错误信息/Feature寄存器用于部分命令需要指定额外参数
Sector count寄存器用来指定带读取/写入的扇区数目
3个8位的LBA寄存器用于记录LBA28地址的低24位（高4位记录在device寄存器）
Command寄存器用于写入操作时存放命令字，可使用命令字如下：

identify：0xEC （硬盘识别）
read sector：0x20 （读扇区）
write sector：0x30（写扇区）
device寄存器是杂项，status寄存器用于给出硬盘状态信息，具体信息见下图

与端口交互的in/out指令

in指令用于从端口中读取数据，格式如下：
```
 in al,dx
 in ax,dx
```
只要使用in指令，源操作数必须是dx(存放端口号)，而目的操作数是用al，还是ax取决于dx端口指代的寄存器是8位宽还是16位宽
out 指令用于往端口中写数据，格式如下：
```
 out dx,al
 out dx,ax
 out 立即数,al
 out 立即数,ax
```
out指令的源操作数是ax还是al取决于目标端口指代的寄存器是8位宽还是16位宽，源操作数可以是立即数直接给出端口号，也可以用dx（存放端口号）

硬盘操作约定顺序

先选择通道，往该通道的sector cout寄存器写入待操作的扇区数
往通道上的三个LBA写入扇区地址LBA28的低24位
往device写入LBA28的高4位，指定主从盘，并选择LBA寻址模式
第四步往该通道的command寄存器写入命令（一旦写入立即执行）
读取status寄存器，判断硬盘工作是否完成
将硬盘数据读出(如果是写硬盘则无需这步)

保护模式概述

为什么要有保护模式(实模式的缺点)

实模式下用户程序和操作系统同一等级，而且逻辑地址就是物理地址，用户程序可以随意修改段基址访问所有内存，不安全
实模式16位寄存器决定访问超过64KB的内存区域要切换段基址、麻烦
一次只能运行一个程序，无法充分利用计算机资源
只有20条地址线，最大可用内存的寻址范围只有1MB，不够用

保护模式的特点

应用程序只能访问虚拟地址，虚拟地址由处理器和操作系统协作转换后才显示真正的物理地址
保护模式的运行环境是32位，寄存器、数据线、地址线也相应都被扩展到32位，指令格式也有了相应的扩展（允许32位源操作数）
保护模式不再使用中断向量表、段基址寄存器这些概念。取而代之的是段选择子寄存器、全局描述符、中断描述符表、各种门结构
保护模式引入了特权级的概念，应用程序不再和操作系统拥有同一特权级

保护模式的扩展

寄存器扩展：

保护模式下寄存器、地址线和数据总线都扩展到32位，内存寻址空间可达4GB，段内寻址空间也可达4GB。也就是说对内存的访问甚至可以让段基址=0，只由一个记录偏移量的寄存器来访问内存，这也就是所谓的平坦模型

另外一提：保护模式抛弃基址这个概念，而是在内存里放入一个全局描述符表，每一个表项都是一个段描述符，用来描述各个内存段的起始地址、大小、权限等信息。段寄存器保护的也不再是段基址了，而是“选择子”，选择子本质上就是全局描述符表中的索引，就像是数组下标一样的东西。
寻址扩展：

如图所示保护模式的寻址方式更加灵活多变，不仅在基址寄存器(所有通用寄存器都可)和变址寄存器(处理esp外的所有通用寄存器都可)有了更多选择外，还引入了比例因子
运行模式反转：

由于32位CPU兼容保护模式和实模式，所以如果你在保护模式下使用实模式的命令，或者在实模式下使用保护模式的命令，都会触发运行模式反转，将会在二进制机器码前加上相应的反转前缀。

注意：模式反转前缀只对单条指令有效，效果并非是全局的
```
 [bit 16] ;告诉编译器接下来的代码是实模式
 [bit 32] ;告诉编译器接下来的代码是保护模式
```
- 操作数反转前缀 0x66
  
  如图上半部分是代码，下半部分是编译后的机器指令
  
  第三行在[bit 16]实模式下使用了eax，触发了保护模式转换，因此机器码前加了前缀0x66
  
  第五行在[bit 32]保护模式下使用了ax，触发了实模式转换，因此机器码前加了前缀0x66
- 寻址方式反转前缀 0x67
  
  第四行在[bit 16]实模式下同时使用了保护模式的32位源操作数和更加灵活的寻址方式，触发模式转换，机器码添加了前缀0x66、0x67
指令扩展

指令扩展后允许32位寄存器和32位源操作数

从实模式到保护模式

从实模式到保护模式我们要执行四个步骤：

打开A20地址线
加载GDT
将CR0的PE位置1
使用jump指令更新流水线，避免指令出错

对于这三个步骤的讲解请看下文

段描述符

到了保护模式下，内存段不再是简单用寄存器加载即可用，而是需要提前把段定义好才可使用。全局描述符就是用来存储对每个段描述的表，全局描述符中的每一个表项包含段描述符，段描述符就是对一个段的描述，64位段描述符格式如下：

段基址：

每个段都有32位的段基址，在段描述符中被拆分成三块存储。

为什么被拆分成三块？为的是兼容，实模式下段基址是16位，80286有关短暂的24位段基址，而现在则是32位段基址，为了兼容原本应该连续存放的段基址被拆分为16-8-8的形式。

当需要查看段基址时，硬件会把三个分散的段基址取出来并拼接在一起得到一个完整的32位段基址。

PS：现在知道为什么有那么多屎山代码了，为了兼容旧时代的程序，屎山代码将成为每一个持续发展产品的最终归宿！
段界限：

段界限表示段边界的扩展最值，20位段界限被拆分为两部分(当然又是为了兼容)。

段界限是一个单位量，单位要么是1字节，要么是4KB(单位由G段决定)。也就是说段的最大寻址范围要么是1*2^20=1MB；要么是2*12*2^20=4GB。(注意寻址范围!=空间)

实际的段界限边界值=(描述符中段界限+1)*(段界限的粒度大小：4KB/1Byte)-1
S字段和type字段：

S字段只有1位：S=0 则说明是系统段(凡是硬件允许需要用到的东西，程序入口、调用门之类);S=1 则说明是非系统段(凡是软件运行需要的东西，数据、代码、栈都是数据段)

type字段有4位：type字段只有在S确认后才有意义，X区分代码段和数据段，R代表是否可读，W代表是否可写，C代表是否一致，E代表向上扩展(E=0,低地址到高地址)或向下扩展(E=1，高地址到低地址)，A代表是否被CPU读过（CPU访问过则置1）
DPL（Descriptor Privilege Level）

2位的DPL字段表示特权级，特权级从0~3,数字越低特权级越高，操作系统是0级，一般应用程序是3级
P字段（Present）：

1位P表示段是否存在，有时候内存不够时，保护模式下CPU可能会按页(4KB)的单位将内存换到磁盘里，此时相当于该段不存在，即P=0;
AVL字段（Avaliable）:

1位AVL字段代表该段是否可用，是否可用是对用户来说，对操作系统来说可随意访问此位
L字段：

1位L字段，L=1表示代码段是64位，L=0表示代码段是32位，我们在32位地址下编程将其设置为0即可
D/B字段：

1位D/B字段指定有效地址及操作数大小，对不同段的意义不同
- 如果针对代码段，D=0时指令中有效地址和操作数是16位，指令有效地址用IP寄存器；D=1时指令中有效地址和操作数是32位，指令有效地址用EIP寄存器
- 如果针对栈段，B=0时栈使用SP寄存器，栈最大寻址范围为2^16；B=1时栈使用ESP寄存器，栈最大寻址范围为2^32
G段：

1位G段用来指定段界限的单位大小，G=0时，段界限的单位时1字节；G=1时，段界限的单位是4KB

全局描述符号GDT、选择子以及GDTR寄存器

GDT(Global Descriptor Table)相当于是段描述符的数组，每一表项都是一个段描述符
选择子是什么？选择子由三部分组成，如下图：

0~1位用来存储RPL，即特权级；第2位是TI(Table Indicator)，用来表示选择子是GDT还是LDT的索引；3~5位是描述符的索引值，就是数组下表

PS：我们注意到索引一共是13位，也就是说一个GDT最多有2^13=8192个表项
LDT(Local Descriptor Table)是局部描述符，一个任务对应一个LDT，但它在现实中应用很少，我们的系统中也未用到LDT
GDTR(Global Descriptor Table Register)是用来指向GDT的寄存器，GDT存储在内存中，GDTR存储的则是GDT的地址。

如图所示是GDTR的结构，48位寄存器前16位是GDT以字节为单位的界限，后32位是GDT在内存中的起始地址

GDT界限范围有16位，也就是占有2^16个字节，而一个表项占有8字节，一个GDT一共可以存储2^16/8=8192个表项，和上面结论相符合
ldgt(load Gloabal Descriptor Table)指令用来加载GPT，一般情况下从实模式进入保护模式我们需要使用命令ldgt来初始化GPTR，不仅如此，在保护模式中我们也可以使用ldgt命令来修改GPTR的值。ldgt的指令格式是：lgdt 48位内存数据
段描述符与内存的关系

如图可知，段描述符指向内存的各个地方。但是GDT的第0个段描述符是不可用的，因为GDT是用选择子来索引的，如果选择子忘记初始化就默认为0，这样选择子相当于索引到不可用的段描述符，而不会索引到其他内存空间。

打开A20地址线

实模式下的地址回绕

实模式下有20根地址线，也就是说最多可以索引1MB空间。实模式下我们用16位段基址:16位偏移量的形式来计算物理地址，我们发现假设16位段基址是0xFFFF，16位地址量是0xFFFF，最终计算得到的物理地址应该是：0xFFFF*16+0xFFFF=0x10FFEF,我们发现这个地址已经超出了20位地址线所能传输的最大范围0xFFFFF。那当我们在实模式下访问超出0xFFFFF物理地址范围的空间时会发生什么事吗？其实并不会发生太糟糕的事，由于硬件原因，超出20位地址线的位将被舍弃，当你访问超过0x100000时就相当于访问0x00000,访问0x10FFEF时就相当于访问0x0FFEF。这个特点就叫做地址回绕。
32位CPU也要兼容地址回绕

实模式下地址回绕的特性被许多程序员视为优点加以利用编程，但是保护模式却没有地址回绕这个问题。所以为了满足32位CPU必须兼容保护模式和实模式的特点，我们必须让32位CPU也要具备可以自由使用地址回绕的特点。

我们知道32位CPU有32位的地址线，IBM在键盘控制器上的一些输出线来控制第21根地址线(A20)的有效性，成为A20Gate。

如果A20Gate=1，当访问0x100000~0x10FFEF之间的地址将会正常访问

如果A20Gate=0，当访问0x100000~0x10FFEF之间的地址将会触发地址回绕特性
打开A20地址线

因此，当我们想从实模式进入保护模式时，我们必须打开A20Gate才能让保护模式的程序正常运行，打开A20地址总线的方式是将端口0x92的第一位置1，代码如下：
```
 in al,0x92
 or al,0000_0010B
 out 0x92,al
```

保护模式的开关,CRO寄存器的PE位

想从实模式进入保护模式，我们还差最后一步。控制寄存器CRx是CPU的窗口，既可以用来展示CPU内部状态，又可以用来控制CPU运行机制。这次我们要用到CR0寄存器的PE（Protection Eanble）位，CR0寄存器构造如下图所示：

右上方是CR0格式位，下方则是对每个位的描述，我们目前只需要关注PE位就行了，将PE位置1，让CPU知道我们要进入保护模式了，代码如下：

mov eax,cr0
or eax,0x00000001
mov cr0,eax

为什么使用远跳转指令来清空流水线

我们使用jmp dword SELECTOR_CODE:p_mode_start来更新流水线，究竟是为什么？

段描述缓冲寄存器未更新

32位CPU兼容保护模式和实模式，段缓存寄存器在实模式下和保护模式下都有用。实模式下：段描述缓冲寄存器用于缓存段基址，保护模式下：段描述缓冲寄存器缓存段描述符。只有当CPU重新引用一个段后，段描述缓冲寄存器才会更新。

当我们从实模式到保护模式后，我们的段描述缓存寄存器存在的还是实模式下用的20位段基址，这当然是不行的。所以我们指令跳转到SELECTOR_CODE:p_mode_start相当于重新引用一个段，让它更新。
流水线中指令译码错误

从实模式到保护模式，一开始我们是16位指令，后来是32位指令。因为CPU的流水线技术提前被加载进流水线的32位指令可能会被译码错误成16位指令。因此我们使用无条件跳转指令jmp,跳转过后会自动清空流水线，避免译码错误。
dword

dword则是让编译器将p_mode_start当成32位操作数处理保证得到正确的地址

分页机制

为什么要分页？

我们只有4GB的内存空间，但我们想让每一个程序都拥有（或者以为自己拥有）4GB的内存空间，于是有了分页机制。

分页机制是在内存分段的基础上进行的
分页机制的核心思想是：通过映射，可以使连续的线性地址与任意物理内存地址相关联，逻辑上连续的线性地址其对应的物理地址可以不连续
一个程序它申请4GB的内存空间，实际上它并不是每时每刻都需要全部的4GB内存空间，大部分时候它都只在使用其中一两小部分的内存空间。我们将该4GB的内存空间分成好多个等大小的块（页），然后根据一个映射规则将当前有用到的块映射到物理内存中，这样4GB的物理内存就可以同时被接受多个程序享用。

一级页表

分页

内存分段机制下的内存访问示意图如下：

我们在实模式下提供段基址，或者是在保护模式下提供的选择子加上另外提供的偏移量，在段部件的处理下形成了线性地址。在还没开启分页机制的情况下，这个线性地址就是真实的物理地址

分页机制下的内存访问示意图如下：

如果打开了分页机制，线性地址还要经过页部件(负责检索页表的部件)的处理，然后才变成了真正的物理地址。我们把没经过页部件处理的线性地址叫做虚拟地址

分页机制的作用在于：
- 将线性地址转换成物理地址
- 用大小相等的页代替大小不相等的段
如下图所示：

在分段的基础上，将虚拟空间中的段划分为一块块大小相等的页然后映射到任意物理地址空间里
映射

我们把存储映射关系的数据结构叫做页表（页表也是存储在内存中），页表中的每一项叫做页表项(记录着页对应的物理地址)，一个页表项需要4字节的大小来描述，页表与物理内存之间的关系如下图所示：

线性地址和物理地址之间的映射有多种可选择的方案

比如最简单的是逐字节映射，虚拟空间中的每一个字节对应到物理空间地址上的每一个字节，那么4GB的虚拟空间对应的页表就得有4G个页表项，每个页表项需要4字节，则一共需要16GB空间大小的页表。为了扩展4GB的内存空间而使用了16GB内存空间这明显是不合适的，所以我们要找到一个合适的映射关系，使得分页机机制即能实现，也不会占用太大的额外内存空间。

最终决定的合适的映射方案是：每4KB大小的空间作为一页。也就是说4GB的内存空间一共可以划分成4GB/4KB=1M个页，一张页表就得含有1M个页表项，总大小为4MB（就空间耗费而言可以接受）
从线性地址到物理地址

现在我们如何从线性地址定位到物理地址呢？
- 首先页表是存在内存中的，页表的起始物理地址我们会放置在CR3控制器中，这样CPU就知道页表的位置了
- 然后我们要定位到具体的页表项，取出线性地址的高20位作为索引*4（因为每个页表项占据4字节）+CR3中页表的起始物理地址=目标页表项的地址。找到了页表项也就相当于找到了该页对应的物理地址
- 最后我们把线性地址低12位作为偏移量+页物理地址=线性地址对应的真正物理地址
线性地址到物理地址转换的全过程如图所示：

二级页表

一级页表的大小有4MB，这个大小虽然可以接受但不够灵活，我们需要保证内存里有一整块连续的4MB空间。而且每一个进程对应一个页表，当电脑同时运行多个进程的同时页表就会占据很大的空间。我们希望能更节约空间，于是有了二级页表机制

二级页表将原本一共有1M个页表项的大页表分成1k个每个包含1K个页表项的小页表。小页表的空间是1K*4Byte=4KB，刚好小页表的大小也是一个页。这样这些1K个小页表就可以灵活得分散到内存空间各个地方里了。但是为了找到这些小页表，我们需要一张页目录(页表的页表),页目录的每一项叫做页目录项（一个页目录项大小也是4字节，一共是1K项），每一项记录着对应小页表的物理地址。真巧！页目录的大小刚刚好也是1K*4Byte=4KB(就是一个页的大小)。

二级页表内存分布如下图所示：

这样做有什么好处吗？我们发现二级页表并没有让真正的页表所占用空间变少（只是把它们拆散了），反而多出了一个4KB大小的页目录。但实际上，这样做以后，小页表不仅不需要连续的大空间，而且也可以像普通的页一样在使用频率少的情况下被从内存换到磁盘上，只在需要用的时候才取回来。用4KB空间换取的灵活能带来更多好处。

如何从线性地址定位到物理地址（二级页表）？

同样也是放在内存中的页目录变成了起点，页目录的起始物理地址我们会放置在CR3控制器中，这样CPU就知道页目录的位置了
我们先取线性地址的高10位*4（页目录项也是4字节）定位到页目录中相对应的页目录项，找到了页目录项就相当于找到了对应页表的物理地址
将线性地址的中间10位*4+对应页表的物理地址找到了页表项，找到了页表项就相当于找到了页的物理地址
将线性地址的最后12位+页的物理地址=线性地址对应的真正物理地址

线性地址到物理地址（二级页表）转换的全过程如图所示：

页目录项、页表项以及CR3格式

页目录项和页表项的格式如下：

页目录基址寄存器(CR3)格式如下：

为什么页目录项的页表物理地址只有20位而不是32位？因为内存是以4KB每页为单位划分的，因此只要20位地址就可以找到对应的页表了
为什么页表的物理页地址也只有20位？这20位足够索引到内存中的对应页了，剩下的12位是段内偏移量由线性地址的最后12位组成
AVL是Available位，表示可用，是给软件看的。操作系统可以不管该位
G，全局位。G=1，则代表缓存在TLB（页表缓冲寄存器）中了，可以不用经过地址转换，直接通过TLB取值
PAT（Page Attribute Table）此位比较复杂，直接置0即可
D(Dirty)脏位，CPU对一个页进行写操作时，对应的页表项D位置1，表示该页已被修改过
A（Accessd）访问位，每当CPU访问过该页时，对应的A位置1。过一段时间后由操作系统同一置0，操作系统可以通过置0的频率来判断该页是否被经常使用
PCD(Page-level Cache Disable)页表高速缓冲禁止位，别管那么多，置0就行
PWT（Page-level Write-Through）页级通写位，别管那么多，置0就行
US（User/Supervisor）普通用户/超级用户位，为1表示User级，任意特权程序可访问。为0表示Supervisor级，特权级别3的程序不可访问
RW（Read/Write）1表示可读可写，0表示可读不可写
P（Present）存在位，P=0表示该表不在物理内存中

启用分页机制的步骤

启用分页机制要做三件事：

准备好页目录以及页表
将页目录地址写入控制寄存器cr3
寄存器cr0的PG位置1

什么是可以自举的分页模型？

当我们想要访问一个物理地址时，我们给出的线性地址将会经过页部件的转换（页目录和页表的查询）后指向真实的物理地址。

现在有一个问题，如果我想要在开启分页机制的情况下修改现有的分表/页目录，我该怎么做？

你可能已经发现问题所在了，我们给出的线性地址都是经过页表/页目录的映射后才指向真实的物理地址。但是如果我想访问页表和页目录，我给出的地址也是会经过页表/页目录的映射后指向其他地方。所以我们需要可以自举的分页模型，也就是说给出的线性地址经过经过页部件转换后可以真正指向目标页表/页目录的物理地址。

接下来我们为loader构建的分页模型就是一个可以自举的分页模型

加载内核并初始化

加载内核并初始化的步骤

我们将告别汇编，用C编写内核文件kernel.bin,用C编写将会和之前有以下区别：

加载内核要做的事如下：

用C编写并使用gcc编译链接得到kernel.bin文件，然后用dd指令将kernel.bin文件放到磁盘里
修改loader.S，负责把kernel.bin文件加载到合适的位置(执行完第三步kernel.bin就没用了)
修改loader.S，负责初始化内核，即通过elf头文件信息将kernel.bin文件里的每个段分别放置在elf头文件指定位置(elf中包含头文件，我们总不能把头文件里的元信息也放置到CPU上执行，所以需要拆解)
跳转到kernel的程序入口地址，loader.S交出最后一棒接力棒

内核文件的内存布局

我们要讲内核加载到内存的哪里？请看下图低端1MB内存布局里三个打勾的位置：

三个打勾的位置将会是我们内核存放的地方（加载在0x7c00的MBR的工作已经做完了，可以被覆盖。加载在0x900的loader里面包含gdt设置，不能被覆盖），从上述加载内核的步骤看我们需要两个地方来存储内核。

第一个地方存储kernel.bin(对应第2步)

第二个地方存储被loader.S处理后的真正的内核映像文件(对应第三步)

kernel.bin应尽量位于高地址，给不断增长的kernel映像文件腾出空间。预计kernel.bin不会超过100kb，计划存储在0x70000（0x70000~0x9fbff有190KB）。

kernel被处理后的映像文件应该尽量放在低地址同时不能覆盖loader。预计loader大小不会超过2000字节,0x900+2000=0x10d0,取一个整数为kernel的映像文件地址0x1500。

上述我们说的都是物理地址，由于我们开启了分页机制后，写代码时里要将物理地址转化为虚拟地址，相应的两个虚拟地址分别是0xc0070000和0xc0001500

在加载完内核后，我们还需要选择一个新的地方作为内核代码的栈顶，可用空间的顶部0x9fc00作为栈顶是最合适的。但是由于pcb（后面章节讲）要求4KB对齐，所以栈顶既要接近0x9fc00又要是4KB的整数倍,所以我们选择了0x9f000作为内核代码的栈顶，转化为虚拟地址即是0xc009f000

elf文件格式

elf文件布局

elf文件=二进制可执行文件+头文件(存储元信息)

一个elf文件的逻辑布局如下图：

物理布局如下图：

关于这两图我们要讲几点：

Section和Segment的区别：

Section是写代码时为了更清楚的逻辑划分，程序员将代码主动划分为一节一节。（汇编语言中的section、segment关键字本质上划分的都是节）

Segment是编译器将相同类型的Section集合在一起形成了段，如代码段、数据段。（经过编译器链接后，我们才称为段）
我们关注的重点：

大部分的Section经过编译器链接后成为了Segment，我们关注的重点在Segment，我们所要做的就是根据elf头文件的指示，将每一个Segment放到它该去的地方

elf header结构

elf格式的数据类型（它们就和int、double一样，只关注字节大小就好了）

elf header的数据结构(该数据结构的布局是重点，我们关注每个字段的字节偏移，这样loader.S就可以读取它需要的字段了)

elf header具体数据成员意义描述（重在会查表应用，而且大部分时候我们只使用其中关键的几项:e_phoff、e_phentisize、e_phnum）：

e_ident
e_type
e_machine
others

program table header结构

program table header的数据结构(该数据结构的布局是重点，我们关注每个字段的字节偏移，这样loader.S就可以读取它需要的字段了)

program table header的成员描述（重在会查表应用，而且大部分时候我们只使用其中关键的几项:p_offset、p_vaddr、p_mensz）：

p_type
p_flags
others

实例：请参照操作系统真相象还原P218-5.3.4；我们可以使用命令readelf -e '文件名'来查看一个elf文件的头的具体数据,也可以使用hd '文件名'来查看一个elf文件的十六进制形式

完整源代码

见连接如下：

SimpleOS-1-简介

Posted on 2023-12-30

本系列博客将用于展示、刨析项目SimpleOS的设计思路，以及提供一些实战时必不可少的工具图表。

SimpleOS是我跟着《操作系统真象还原》一书学习制作的在bochs上运行的简易操作系统。这本书实践性强，知名度高，网络上也有许多关于这本书的教学博客或视频。因此本博客的核心不在于教学如何搭建SimpleOS，本博客的核心是服务于我自己：让本人可以在只有博客的情况下从零开始搭建一个SimpleOS项目。而对于其他读者来说，本博客可以让你从整体上把握SimpleOS并有一个更深入的了解。

自学建议

如果你想自己体会一步一步搭建SimpleOS的全过程，这边给出了建议：

《操作系统真象还原》——这本书的实践部分写得非常详细，跟着这本书一步步做可以解决80%的问题。
《操作系统真象还原》从零开始自制操作系统全流程记录——这篇博客在我搭建SimpleOS时提供了必不可少的帮助，该博客可以帮你解决剩下10%的问题（别小看着10%，帮我省了不少时间）
本仓库是自己学习操作系统真象还原的代码仓库，请配合本人的笔记与视频使用——最后10%的问题我是通过该Github仓库解决的，该Github仓库提供了从第一章到最后一章每一步的SimpleOS详细代码，并在B站上有视频教程。

SimpleOS系统框架

该系统分为6大模块：Boot程序、内存管理、进程管理、驱动程序、文件系统、Shell

接下来将有7篇博客，前6篇分别介绍这6个模块，最后一篇模块则是介绍通用的工具代码。

对于每一个模块本博客将会采用如下结构进行详细介绍：整体设计方案-数据结构-函数表-关键函数说明-背景知识-工具图表

环境配置

window环境下的虚拟机管理软件采用VMware17

开发环境用linux操作系统Ubuntu20.04.6

C编译器用gcc4(gcc过高将和本书的介绍的elf格式不兼容)

SimpleOS将会安装在PC模拟软件(也是虚拟机)Bochs2.6.8

自制简易操作系统（十四）

Posted on 2023-12-24 Edited on 2023-12-30

文件系统

文件系统的核心是管理

超级块

用于描述管理信息（大小一共512字节，一扇区也是一块）

/* 超级块 */
struct super_block {
    uint32_t magic;		    // 用来标识文件系统类型,支持多文件系统的操作系统通过此标志来识别文件系统类型

    //描述总分区信息
    uint32_t sec_cnt;		    // 本分区总共的扇区数
    uint32_t inode_cnt;		    // 本分区中inode数量
    uint32_t part_lba_base;	    // 本分区的起始lba地址


    //描述空闲块位图
    uint32_t block_bitmap_lba;	    // 块位图本身起始扇区地址
    uint32_t block_bitmap_sects;     // 扇区位图本身占用的扇区数量


    //描述inode位图
    uint32_t inode_bitmap_lba;	    // i结点位图起始扇区lba地址
    uint32_t inode_bitmap_sects;	    // i结点位图占用的扇区数量


    //描述inode表
    uint32_t inode_table_lba;	    // i结点表起始扇区lba地址
    uint32_t inode_table_sects;	    // i结点表占用的扇区数量


    //描述数据区(包含根目录)
    uint32_t data_start_lba;	    // 数据区开始的第一个扇区号
    uint32_t root_inode_no;	    // 根目录所在的I结点号
    uint32_t dir_entry_size;	    // 目录项大小

    uint8_t  pad[460];		    // 加上460字节,凑够512字节1扇区大小
} __attribute__ ((packed));

空闲块位图

inode位图

inode表

根目录数据区

inode

inode相当于是文件的本身，一个inode就是一个文件

/* inode结构 */
struct inode {
    uint32_t i_no;    // inode编号

    /* 当此inode是文件时,i_size是指文件大小,
    若此inode是目录,i_size是指该目录下所有目录项大小之和*/
    uint32_t i_size;

    uint32_t i_open_cnts;   // 记录此文件被打开的次数
    bool write_deny;	   // 写文件不能并行,进程写文件前检查此标识

    /* i_sectors[0-11]是直接块, i_sectors[12]用来存储一级间接块指针 */
    uint32_t i_sectors[13];
    struct list_elem inode_tag;
};

自制简易操作系统（十一）

Posted on 2023-12-12

用户进程

任务状态段TSS

TSS结构如下：

TSS是用于切换任务时保存当前环境的工具。TTS提供了三个特权级栈，当该任务提升特权级时就会对应使用相应的特权级栈（使用不同的栈保证低特权级无法访问到高特权级的资源）

在Linux系统中，用户程序处于特权级3，内核程序处于特权级0，Linux不使用TTS结构来保存上下文环境，Linux只使用了TSS中的0特权级栈一个结构。

LinuxOS的逻辑如下：只维护一个TSS，每次切换任务时修改TSS0特权级栈，其他功能一律不使用。至于上下文环境Linux则是保存在PCB结构中。

TSS结构本质上是一个特殊的段，因此要在GDT中构造TSS专用的TSS描述符，同时也得构造TSS选择子，我们可以通过TSS选择子在GDT中寻找到TSS描述符，进而寻找到TSS结构。

TR寄存器通过TSS选择子寻找到TSS结构，然后存储TSS的起始地址以及偏移大小。（TR加载命令如下：ltr 16位TTS选择子）

TR结构如下图所示：

通过TSS选择子寻找TSS的逻辑如下图所示：

定义并初始化TSS

我们所要做的事如下：

定义TSS段描述符，并装载在gdt中
定义TSS段描述符，并用 ltr 命令装载到 TR 里
初始化TSS（初始化一次TSS后就无需再更换了，后续切换任务只修改TSS中0特权级栈的内容）

代码如下：

kernel/global.h

  #ifndef __KERNEL_GLOBAL_H
  #define __KERNEL_GLOBAL_H
  #include "stdint.h"

  #define	 RPL0  0
  #define	 RPL1  1
  #define	 RPL2  2
  #define	 RPL3  3
  #define	 PG_SIZE  4096

  #define TI_GDT 0
  #define TI_LDT 1

  //--------------   GDT描述符属性  ------------

  #define DESC_G_4K	1
  #define DESC_D_32	1
  #define DESC_L		0
  #define DESC_AVL	0
  #define DESC_P		1
  #define DESC_DPL_0	0
  #define DESC_DPL_1	1
  #define DESC_DPL_2	2
  #define DESC_DPL_3	3

  #define DESC_S_CODE	1
  #define DESC_S_DATA	DESC_S_CODE
  #define DESC_S_SYS	0
  #define DESC_TYPE_CODE	8

  #define DESC_TYPE_DATA 2
  #define DESC_TYPE_TSS  9

  /*KERNEL段*/
  #define SELECTOR_K_CODE	   ((1 << 3) + (TI_GDT << 2) + RPL0)
  #define SELECTOR_K_DATA	   ((2 << 3) + (TI_GDT << 2) + RPL0)
  #define SELECTOR_K_STACK          SELECTOR_K_DATA 
  #define SELECTOR_K_GS	           ((3 << 3) + (TI_GDT << 2) + RPL0)
  /*这里是TSS*/
  /*USER段*/
  #define SELECTOR_U_CODE  	   ((5 << 3) + (TI_GDT << 2) + RPL3)
  #define SELECTOR_U_DATA	   ((6 << 3) + (TI_GDT << 2) + RPL3)
  #define SELECTOR_U_STACK	   SELECTOR_U_DATA

  #define GDT_ATTR_HIGH		   ((DESC_G_4K << 7) + (DESC_D_32 << 6) + (DESC_L << 5) + (DESC_AVL << 4))

  #define GDT_CODE_ATTR_LOW_DPL3    ((DESC_P << 7) + (DESC_DPL_3 << 5) + (DESC_S_CODE << 4) + DESC_TYPE_CODE)

  #define GDT_DATA_ATTR_LOW_DPL3    ((DESC_P << 7) + (DESC_DPL_3 << 5) + (DESC_S_DATA << 4) + DESC_TYPE_DATA)



  //--------------   IDT描述符属性  ------------
  #define	 IDT_DESC_P	 1 
  #define	 IDT_DESC_DPL0   0
  #define	 IDT_DESC_DPL3   3
  #define	 IDT_DESC_32_TYPE     0xE   // 32位的门
  #define	 IDT_DESC_16_TYPE     0x6   // 16位的门，不用，定义它只为和32位门区分
  #define	 IDT_DESC_ATTR_DPL0  ((IDT_DESC_P << 7) + (IDT_DESC_DPL0 << 5) + IDT_DESC_32_TYPE)
  #define	 IDT_DESC_ATTR_DPL3  ((IDT_DESC_P << 7) + (IDT_DESC_DPL3 << 5) + IDT_DESC_32_TYPE)


  //--------------   TSS描述符属性  ------------
  #define	 TSS_DESC_D 0
  #define 	 TSS_ATTR_HIGH ((DESC_G_4K << 7) + (TSS_DESC_D << 6) + (DESC_L << 5) + (DESC_AVL << 4) + 0X0)
  #define 	 TSS_ATTR_LOW  ((DESC_P << 7) + (DESC_DPL_0 << 5) + (DESC_S_SYS << 4) + DESC_TYPE_TSS)

  #define 	 SELECTOR_TSS  ((4 << 3) + (TI_GDT << 2) + RPL0)

  /*描述符结构*/
  struct gdt_desc
  {
      uint16_t limit_low_word;
      uint16_t base_low_word;
      uint8_t  base_mid_byte;
      uint8_t  attr_low_byte;
      uint8_t  limit_high_attr_high;
      uint8_t  base_high_byte;
  };

  #endif

userprog/tss.c

  #include "tss.h"
  #include "global.h"
  #include "thread.h"
  #include "print.h"
  #include "string.h"
  #include "stdint.h"

  struct tss
  {
      uint32_t backlink;
      uint32_t* esp0;
      uint32_t ss0;
      uint32_t* esp1;
      uint32_t ss1;
      uint32_t* esp2;
      uint32_t ss2;
      uint32_t cr3;
      uint32_t (*eip) (void);  //eip是一个函数指针
      uint32_t eflags;
      uint32_t eax;
      uint32_t ecx;
      uint32_t edx;
      uint32_t ebx;
      uint32_t esp;
      uint32_t ebp;
      uint32_t esi;
      uint32_t edi;
      uint32_t es;
      uint32_t cs;
      uint32_t ss;
      uint32_t ds;
      uint32_t fs;
      uint32_t gs;
      uint32_t ldt;
      uint32_t trace;
      uint32_t io_base;
  };

  static struct tss tss;

  //切换tss的0特权级栈，相当于任务切换
  void updata_tss_esp(struct task_struct* pthread)
  {
      tss.esp0 = (uint32_t*)((uint32_t)pthread + PG_SIZE);
  }


  struct gdt_desc make_gdt_desc(uint32_t* desc_addr,uint32_t limit,uint8_t attr_low,uint8_t attr_high)
  {
      struct gdt_desc desc;
      uint32_t desc_base = (uint32_t) desc_addr;
      desc.limit_low_word =  limit & 0x0000ffff;
      desc.base_low_word = desc_base & 0x0000ffff;
      desc.base_mid_byte = ((desc_base & 0x00ff0000) >> 16);
      desc.attr_low_byte = (uint8_t)(attr_low);
      desc.limit_high_attr_high = (((limit & 0x000f0000) >> 16) + (uint8_t)(attr_high));
      desc.base_high_byte = desc_base >> 24;
      return desc;
  }

  void tss_init()
  {
      put_str("tss_init start\n");
      uint32_t tss_size = sizeof(tss);
      memset(&tss,0,tss_size);
      tss.ss0 = SELECTOR_K_STACK;
      tss.io_base = tss_size;
      
      //之前的gdt放在了0xc0000903的位置
      *((struct gdt_desc*)0xc0000923) = make_gdt_desc((uint32_t*)&tss,tss_size-1,TSS_ATTR_LOW,TSS_ATTR_HIGH);
      *((struct gdt_desc*)0xc000092b) = make_gdt_desc((uint32_t*)0,0xfffff,GDT_CODE_ATTR_LOW_DPL3,\
                                              GDT_ATTR_HIGH);
      *((struct gdt_desc*)0xc0000933) = make_gdt_desc((uint32_t*)0,0xfffff,GDT_DATA_ATTR_LOW_DPL3,\
                                              GDT_ATTR_HIGH);
      
      uint64_t gdt_operand = \
      ((8*7 - 1) | ((uint64_t)(uint32_t)0xc0000903 << 16));
      

      //重新加载gdt
      asm volatile("lgdt %0" :: "m"(gdt_operand));

      //将tss加载到tr
      asm volatile("ltr %w0" :: "r"(SELECTOR_TSS));

      put_str("tss_init and ltr done\n");
  }

程序运行后现在可以看到gdt里一共有7个段描述符：

自制简易操作系统（十）

Posted on 2023-11-30 Edited on 2023-12-12

同步机制——锁

当多个线程共同使用一样公共资源时，就有可能会出现竞争问题。在我们上一章节主线程、A线程和B线程都在打印字符，显存以及put_str()就是我们的公共资源。正是因为竞争问题，所以在上一章节中运行过程会出现字符串错误，并且运行到最后会报错(显存越界)。

所以我们需要实现一个锁，只有持有锁的人才能操作公共资源。我们将使用二元信号量实现锁的同步机制。

函数逻辑关系如图：

代码如下：

thread/thread.c(新增部分)

  void thread_block(enum task_status stat){
      ASSERT((stat==TASK_BLOCKED)||(stat==TASK_HANGING)||(stat==TASK_WAITING));
      enum intr_status old_status=intr_disable();

      struct task_struct* cur_thread=running_thread();
      cur_thread->status=stat;
      schedule();

      intr_set_status(old_status);
  }

  void thread_unblock(struct task_struct* pthread){
      enum intr_status old_status=intr_disable();

      ASSERT((pthread->status==TASK_BLOCKED)||(pthread->status==TASK_HANGING)||(pthread->status==TASK_WAITING));
      if(pthread->status!=TASK_READY){
          ASSERT(!elem_fimd(&thread_ready_list,&pthread->general_tag));
          if(elem_fimd(&thread_ready_list,&pthread->general_tag)){
              PANIC("thread_unblock:blocked thread in ready_list\n");
          }
          list_push(&thread_ready_list,&pthread->general_tag);
          pthread->status=TASK_READY;
      }

      intr_set_status(old_status);
  }

thread/sync.h

  #ifndef __THREAD_SYNC_H__
  #define __THREAD_SYNC_H__

  #include "list.h"
  #include "stdint.h"
  #include "thread.h"


  struct semaphore{
      uint8_t value;
      struct list waiters;
  };


  struct lock{
      struct task_struct* holder;
      struct semaphore semaphore;  //用二元信号量实现锁
      uint32_t holder_repeat_nr;
  };

  void sema_init(struct semaphore* psema,uint8_t value);
  void lock_init(struct lock* plock);
  void sema_down(struct semaphore* psema);
  void sema_up(struct semaphore* psema);
  void lock_acquire(struct lock* plock);
  void lock_release(struct lock* plock);

  #endif

thread/sync.c

  #include "sync.h"

  void sema_init(struct semaphore* psema,uint8_t value){

      psema->value=value;
      list_init(&psema->waiters);

  }

  void lock_init(struct lock* plock){
      plock->holder=NULL;
      plock->holder_repeat_nr=0;
      sema_init(&plock->semaphore,1);
  }


  //信号量-1操作
  void sema_down(struct semaphore* psema){
      enum intr_status old_status=intr_disable();

      while(psema->value==0){
          ASSERT(!elem_find(&psema->waiters,&running_thread()->general_tag));

          if(elem_find(&psema->waiters,&running_thread()->general_tag)){
              PANIC("sema_down:thread blocked has been in waiters_list\n");
          }

          list_append(&psema->waiters,&running_thread()->general_tag);
          thread_block(TASK_BLOCKED);
      }
      psema->value--;
      ASSERT(psema->value==0);

      intr_set_status(old_status);
  }

  //信号量+1操作
  void sema_up(struct semaphore* psema){
      enum intr_status old_status=intr_disable();
      
      ASSERT(psema->value==0);
      if(!list_empty(&psema->waiters)){
          struct task_struct* thread_blocked =elem2entry(struct task_struct, general_tag,list_pop(&psema->waiters));
          thread_unblock(thread_blocked);
      }
      psema->value++;
      ASSERT(psema->value==1);

      intr_set_stauts(old_status);
  }

  //获取锁plock
  void lock_acquire(struct lock* plock){
      if(plock->holder!=running_thread()){
          sema_down(&plock->semaphore);
          plock->holder=running_thread();
          ASSERT(plock->holder_repeat_nr==0);
          plock->holder_repeat_nr=1;
      }else{
          plock->holder_repeat_nr++;
      }
  }

  //释放锁plock
  void lock_release(struct lock* plock){
      ASSERT(plock->holder==running_thread());
      if(plock->holder_repeat_nr>1){
          plock->holder_repeat_nr--;
          return;
      }
      ASSERT(plock->holder_repeat_nr==1);
      
      plock->holder=NULL;
      plock->holder_repeat_nr=0;
      sema_up(&plock->semaphore);
  }

接下来我们将在控制台作为一个公共资源，在控制台上打印字符就必须获得控制台的锁，实现代码如下

device/console.h

  #ifndef __DEVICE_CONSOLE_H__
  #define __DEVICE_CONSOLE_H__
  #include "stdint.h"

  void console_init(void);

  void console_release(void);

  void console_acquire(void);

  void console_put_char(uint8_t char_asci);

  void console_put_str(char* str);

  void console_put_int(uint32_t num);

  #endif

device/console.c

  #include "console.h"
  #include "print.h"
  #include "stdint.h"
  #include "sync.h"
  #include "thread.h"

  static struct lock console_lock;

  void console_init(){
      lock_init(&console_lock);
  }

  void console_release(){
      lock_release(&console_lock);
  }

  void console_acquire(){
      lock_acquire(&console_lock);
  }

  void console_put_char(uint8_t char_asci){
      console_acquire();
      put_char(char_asci);
      console_release();
  }

  void console_put_str(char* str){
      console_acquire();
      put_str(str);
      console_release();  
  }

  void console_put_int(uint32_t num){
      console_acquire();
      put_int(num);
      console_release();  
  }

kernel/main.c(将原本的put_str()换成console_put_str())

  #include "print.h"
  #include "init.h"
  #include "debug.h"
  #include "memory.h"
  #include "thread.h"
  #include "console.h"

  void k_thread_a(void*);
  void k_thread_b(void*);

  int main(void) {
  put_str("I am kernel\n");
  init_all();


  thread_start("k_thread_a",31,k_thread_a,"argA ");
  thread_start("k_thread_b",8,k_thread_b,"argB ");

  intr_enable();
  while(1){
      console_put_str("Main ");
  };
  
  return 0;
  }


  //在线程中运行的函数
  void k_thread_a(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      console_put_str(para);
  }
  }

  void k_thread_b(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      console_put_str(para);
  }
  }

我们就可以正确的打印字符而不报错了。

编写键盘驱动程序

如上图所示，键盘上有芯片8048用于捕获按键的扫描码并传递给8042，8042是再主机上的键盘控制器负责CPU和键盘之间的沟通，8042会将从8048里收到的不同格式的扫描码统一成第一套键盘扫描码并向8259A发送键盘中断信号，8259A就是我们的老朋友了，用于中断管理。

工作流程如下：每当我们按下键盘的任一一个按键时，8048会捕获该按键的扫描码并发送给8042。8042接受扫描码后会将其翻译成第一套键盘扫描码(统一格式)，每一个按键的扫描码可能是一个字节也可能是两个字节（甚至可能是多个字节）。但8042只会一个字节一个字节的放到自己的缓冲区里并通知CPU来取数据(通过键盘中断),CPU不取走上一个数据，8042就不会放下一个数据，如此循环直到键盘按键的所有信息都被传输给了CPU

第一套键盘扫描码格式如下：

8048工作内容以及寄存器如下：

PS：在8048中的4个寄存器我们只需要从0x60的输出缓冲区里不断读取数据

写下来我们要编写键盘驱动程序，键盘驱动程序的核心就是一个中断处理函数intr_keyboard_handler(void);该函数负责把从8042中取得的第一套扫描码转化成相应的ASCII码，然后用put_char()输出。

看上去很简单对吧，但这是在没有组合键的请看下，组合键shift、Ctrl、Capslk让一切都变得有些麻烦(当我们按下组合键时并不会输入任何字符，但是当我们同时搭配组合键和普通按键时却会改变普通按键的功能)，请直接看代码。

kernel/kernel.S(添加几个中断入口，支持的中断数由原本的33个变成48个)

  VECTOR 0X20 ,ZERO					;时钟中断
  VECTOR 0X21 ,ZERO					;键盘中断
  VECTOR 0X22 ,ZERO					;级联
  VECTOR 0X23 ,ZERO					;串口2
  VECTOR 0X24 ,ZERO					;串口1
  VECTOR 0X25 ,ZERO					;并口2
  VECTOR 0X26 ,ZERO					;软盘
  VECTOR 0X27 ,ZERO					;并口1
  VECTOR 0X28 ,ZERO					;实时时钟
  VECTOR 0X29 ,ZERO					;重定向
  VECTOR 0X2A ,ZERO					;保留
  VECTOR 0x2B ,ZERO					;保留
  VECTOR 0x2C ,ZERO					;ps/2 鼠标
  VECTOR 0x2D ,ZERO					;fpu 浮点单元异常
  VECTOR 0x2E ,ZERO					;硬盘
  VECTOR 0x2F ,ZERO					;保留

device/keyboard.c

  #include "keyboard.h"
  #include "print.h"
  #include "interrupt.h"
  #include "io.h"
  #include "global.h"
  #include "stdint.h"

  #define KBD_BUF_PORT 0x60

  //定义部分字符控制键的转义字符（可直接用put_char处理）
  #define esc     '\0x33'     //八进制ASCII码转义
  #define backspace '\b'
  #define tab       '\t'
  #define enter       '\r'
  #define delete      '\177'  //八进制ASCII码转义

  //定义不可见字符为0
  #define char_invisible 0
  #define ctrl_l_char char_invisible
  #define ctrl_r_char char_invisible
  #define shift_l_char char_invisible
  #define shift_r_char char_invisible
  #define alt_l_char char_invisible
  #define alt_r_char char_invisible
  #define caps_lock_char char_invisible


  //定义控制字符的通码和断码
  #define shift_l_make 0x2a
  #define shift_r_make 0x36
  #define alt_l_make 0x38
  #define alt_r_make 0xe038
  #define alt_r_break 0xe0b8
  #define ctrl_l_make 0x1d
  #define ctrl_r_make 0xe01d
  #define ctrl_r_break 0xe09d
  #define caps_lock_make 0x3a


  bool ctrl_status = false,shift_status = false,alt_status = false,caps_lock_status = false,ext_scancode = false;


  //该二维数组的索引是扫描码，元素0代表未按下shift键时的输出字符，元素1代表按下shift键时的输出字符
  char keymap[][2] = {
  /* 0x00 */	{0,	0},		
  /* 0x01 */	{esc,	esc},		
  /* 0x02 */	{'1',	'!'},		
  /* 0x03 */	{'2',	'@'},		
  /* 0x04 */	{'3',	'#'},		
  /* 0x05 */	{'4',	'$'},		
  /* 0x06 */	{'5',	'%'},		
  /* 0x07 */	{'6',	'^'},		
  /* 0x08 */	{'7',	'&'},		
  /* 0x09 */	{'8',	'*'},		
  /* 0x0A */	{'9',	'('},		
  /* 0x0B */	{'0',	')'},		
  /* 0x0C */	{'-',	'_'},		
  /* 0x0D */	{'=',	'+'},		
  /* 0x0E */	{backspace, backspace},	
  /* 0x0F */	{tab,	tab},		
  /* 0x10 */	{'q',	'Q'},		
  /* 0x11 */	{'w',	'W'},		
  /* 0x12 */	{'e',	'E'},		
  /* 0x13 */	{'r',	'R'},		
  /* 0x14 */	{'t',	'T'},		
  /* 0x15 */	{'y',	'Y'},		
  /* 0x16 */	{'u',	'U'},		
  /* 0x17 */	{'i',	'I'},		
  /* 0x18 */	{'o',	'O'},		
  /* 0x19 */	{'p',	'P'},		
  /* 0x1A */	{'[',	'{'},		
  /* 0x1B */	{']',	'}'},		
  /* 0x1C */	{enter,  enter},
  /* 0x1D */	{ctrl_l_char, ctrl_l_char},
  /* 0x1E */	{'a',	'A'},		
  /* 0x1F */	{'s',	'S'},		
  /* 0x20 */	{'d',	'D'},		
  /* 0x21 */	{'f',	'F'},		
  /* 0x22 */	{'g',	'G'},		
  /* 0x23 */	{'h',	'H'},		
  /* 0x24 */	{'j',	'J'},		
  /* 0x25 */	{'k',	'K'},		
  /* 0x26 */	{'l',	'L'},		
  /* 0x27 */	{';',	':'},		
  /* 0x28 */	{'\'',	'"'},		
  /* 0x29 */	{'`',	'~'},		
  /* 0x2A */	{shift_l_char, shift_l_char},	
  /* 0x2B */	{'\\',	'|'},		
  /* 0x2C */	{'z',	'Z'},		
  /* 0x2D */	{'x',	'X'},		
  /* 0x2E */	{'c',	'C'},		
  /* 0x2F */	{'v',	'V'},		
  /* 0x30 */	{'b',	'B'},		
  /* 0x31 */	{'n',	'N'},		
  /* 0x32 */	{'m',	'M'},		
  /* 0x33 */	{',',	'<'},		
  /* 0x34 */	{'.',	'>'},		
  /* 0x35 */	{'/',	'?'},
  /* 0x36	*/	{shift_r_char, shift_r_char},	
  /* 0x37 */	{'*',	'*'},    	
  /* 0x38 */	{alt_l_char, alt_l_char},
  /* 0x39 */	{' ',	' '},		
  /* 0x3A */	{caps_lock_char, caps_lock_char}
  };


  static void intr_kerboard_handler(void){

      bool ctrl_down_last=ctrl_status;
      bool shift_down_last=shift_status;
      bool caps_lock_last=caps_lock_status;

      bool break_code;
      uint16_t scancode=inb(KBD_BUF_PORT);//必须读取缓冲区数据，否则8042不再继续响应键盘中断

      //打开拓展标志，并返回，（说明要接受的扫描码不止1字节，有两字节）
      if(scancode == 0xe0){
          ext_scancode=true;
          return;
      }

      if(ext_scancode){
          scancode=(0xe000|scancode);
          ext_scancode=false;
      }


      //true则代表是断码，否则是通码
      break_code=((scancode&0x0080)!=0);

      if(break_code){
          uint16_t make_code=(scancode&=0xff7f);

          //改变状态
          if(make_code==ctrl_l_make||make_code==ctrl_r_make){
              ctrl_status=false;
          }else if(make_code == shift_l_make || make_code==shift_r_make){
              shift_status=false;
          }else if(make_code == alt_l_make || make_code ==alt_r_make){
              alt_status=false;
          }

          return;
      }else if((scancode>0x00 && scancode<0x3b)||(scancode == alt_r_make)||(scancode ==ctrl_r_make)){
          
          //shift用于判断keymap到底是要输出元素0还是元素1
          bool shift=false;


          //区分双字符键和单子符键，capslk和shift对双字符键和单字符键作用不一样
          if((scancode < 0x0e) || (scancode == 0x29) || (scancode == 0x1a) || \
          (scancode == 0x1b) || (scancode == 0x2b) || (scancode == 0x27) || \
          (scancode == 0x28) || (scancode == 0x33) || (scancode == 0x34) || \
          (scancode == 0x35)){

              if(shift_down_last){
                  shift = true;
              }

          }else{  //默认是字符键
              if(shift_down_last && caps_lock_last){
                  shift = false; //效果确实是这样子的 我试了一下
              }else if(shift_down_last || caps_lock_last){
                  shift = true; //其中任意一个都是大写的作用
              }else{
                  shift = false;
              } 
          }


          //忽略高8位，也就是0xe0的影响
          uint8_t index=(scancode&=0x00ff);

          char cur_char = keymap[index][shift];

          if(cur_char){
              put_char(cur_char);
              return;
          }

          if(scancode == ctrl_l_make || scancode == ctrl_r_make){
              ctrl_status = true;
          }  	
          else if(scancode == shift_l_make || scancode == shift_r_make){
              shift_status = true;
          }
          else if(scancode == alt_l_make || scancode == alt_r_make){
              alt_status = true;
          }
          else if(scancode == caps_lock_make){
              caps_lock_status = !caps_lock_status;
          }
          
      }else{
          put_str("unknown key\n");
      }

  }

  void keyboard_init(){
      put_str("keyboard init start\n");
      register_handler(0x21,intr_kerboard_handler);
      put_str("kerboard init done\n");
  }

环形输入缓冲区

如图是线性缓冲区的生成者与消费者示例图，生产者在前面生产，消费者在后面消费

我们要将线性缓冲区变成环形，如下图示：

构造环形输入缓冲区是为了实现Shell命令的键入，Shell的命令是由数个字符组成，我们可以先用键盘输入(生产者),将数个字符存在缓冲区中，再用shell一次性读入（消费者）

实现代码如下：

device/ioqueue.h

  #ifndef __DEVICE_IOQUEUE_H__
  #define __DEVICE_IOQUEUE_H__

  #include "stdint.h"
  #include "thread.h"
  #include "sync.h"

  #define bufsize 64

  struct ioqueue{
      struct lock lock;
      struct task_struct* producer;
      struct task_struct* consumer;
      char buf[bufsize];
      int32_t head;
      int32_t tail;
  };


  void ioqueue_init(struct ioqueue* ioq);
  char ioq_getchar(struct ioqueue* ioq);
  void ioq_putchar(struct ioqueue* ioq,char byte);
  bool ioq_empty(struct ioqueue* ioq);
  bool ioq_full(struct ioqueue* ioq);

  #endif

device/ioqueue.c

  #include "ioqueue.h"
  #include "interrupt.h"
  #include "global.h"
  #include "debug.h"


  void ioqueue_init(struct ioqueue* ioq){
      lock_init(&ioq->lock);
      ioq->producer=ioq->consumer=NULL;
      ioq->head=ioq->tail=0;
  }


  static int32_t next_pos(int32_t pos){
      return (pos+1)%bufsize;
  }

  bool ioq_full(struct ioqueue* ioq){
      ASSERT(intr_get_status()==INTR_OFF);
      return next_pos(ioq->head)==ioq->tail;
  }

  bool ioq_empty(struct ioqueue* ioq){
      ASSERT(intr_get_status()==INTR_OFF);
      return ioq->head==ioq->tail;
  }


  static void ioq_wait(struct  task_struct** waiter){
      ASSERT(*waiter==NULL && waiter!=NULL);
      *waiter = running_thread();
      thread_block(TASK_BLOCKED);
  }

  static void wakeup(struct task_struct** waiter){
      ASSERT(*waiter!=NULL);
      thread_unblock(*waiter);
      *waiter=NULL;
  }

  char ioq_getchar(struct ioqueue* ioq){
      ASSERT(intr_get_status()==INTR_OFF);

      while(ioq_empty(ioq)){
          lock_acquire(&ioq->lock);
          ioq_wait(&ioq->consumer);
          lock_release(&ioq->lock);
      }

      char byte=ioq->buf[ioq->tail];
      ioq->tail=next_pos(ioq->tail);

      if(ioq->producer!=NULL){
          wakeup(&ioq->producer);
      }

      return byte;
  }


  void ioq_putchar(struct ioqueue* ioq,char byte){
      ASSERT(intr_get_status()==INTR_OFF);

      while(ioq_full(ioq)){
          lock_acquire(&ioq->lock);
          ioq_wait(&ioq->producer);
          lock_release(&ioq->lock);
      }

      ioq->buf[ioq->head]=byte;
      ioq->head=next_pos(ioq->head);

      if(ioq->consumer!=NULL){
          wakeup(&ioq->consumer);
      }
  }

device/keyboard.h

  #ifndef __KEYBOARD_H__
  #define __KEYBOARD_H__

  void keyboard_init(void);

  extern struct ioqueue kbd_buf;

  #endif

device/keyboard.c(修改)

  #include "keyboard.h"
  #include "print.h"
  #include "interrupt.h"
  #include "io.h"
  #include "global.h"
  #include "stdint.h"
  #include "ioqueue.h"

  #define KBD_BUF_PORT 0x60

  //定义部分字符控制键的转义字符（可直接用put_char处理）
  #define esc     '\0x33'     //八进制ASCII码转义
  #define backspace '\b'
  #define tab       '\t'
  #define enter       '\r'
  #define delete      '\177'  //八进制ASCII码转义

  //定义不可见字符为0
  #define char_invisible 0
  #define ctrl_l_char char_invisible
  #define ctrl_r_char char_invisible
  #define shift_l_char char_invisible
  #define shift_r_char char_invisible
  #define alt_l_char char_invisible
  #define alt_r_char char_invisible
  #define caps_lock_char char_invisible


  //定义控制字符的通码和断码
  #define shift_l_make 0x2a
  #define shift_r_make 0x36
  #define alt_l_make 0x38
  #define alt_r_make 0xe038
  #define alt_r_break 0xe0b8
  #define ctrl_l_make 0x1d
  #define ctrl_r_make 0xe01d
  #define ctrl_r_break 0xe09d
  #define caps_lock_make 0x3a


  bool ctrl_status = false,shift_status = false,alt_status = false,caps_lock_status = false,ext_scancode = false;


  //定义键盘缓冲区:
  struct ioqueue kbd_buf;


  //该二维数组的索引是扫描码，元素0代表未按下shift键时的输出字符，元素1代表按下shift键时的输出字符
  char keymap[][2] = {
  /* 0x00 */	{0,	0},		
  /* 0x01 */	{esc,	esc},		
  /* 0x02 */	{'1',	'!'},		
  /* 0x03 */	{'2',	'@'},		
  /* 0x04 */	{'3',	'#'},		
  /* 0x05 */	{'4',	'$'},		
  /* 0x06 */	{'5',	'%'},		
  /* 0x07 */	{'6',	'^'},		
  /* 0x08 */	{'7',	'&'},		
  /* 0x09 */	{'8',	'*'},		
  /* 0x0A */	{'9',	'('},		
  /* 0x0B */	{'0',	')'},		
  /* 0x0C */	{'-',	'_'},		
  /* 0x0D */	{'=',	'+'},		
  /* 0x0E */	{backspace, backspace},	
  /* 0x0F */	{tab,	tab},		
  /* 0x10 */	{'q',	'Q'},		
  /* 0x11 */	{'w',	'W'},		
  /* 0x12 */	{'e',	'E'},		
  /* 0x13 */	{'r',	'R'},		
  /* 0x14 */	{'t',	'T'},		
  /* 0x15 */	{'y',	'Y'},		
  /* 0x16 */	{'u',	'U'},		
  /* 0x17 */	{'i',	'I'},		
  /* 0x18 */	{'o',	'O'},		
  /* 0x19 */	{'p',	'P'},		
  /* 0x1A */	{'[',	'{'},		
  /* 0x1B */	{']',	'}'},		
  /* 0x1C */	{enter,  enter},
  /* 0x1D */	{ctrl_l_char, ctrl_l_char},
  /* 0x1E */	{'a',	'A'},		
  /* 0x1F */	{'s',	'S'},		
  /* 0x20 */	{'d',	'D'},		
  /* 0x21 */	{'f',	'F'},		
  /* 0x22 */	{'g',	'G'},		
  /* 0x23 */	{'h',	'H'},		
  /* 0x24 */	{'j',	'J'},		
  /* 0x25 */	{'k',	'K'},		
  /* 0x26 */	{'l',	'L'},		
  /* 0x27 */	{';',	':'},		
  /* 0x28 */	{'\'',	'"'},		
  /* 0x29 */	{'`',	'~'},		
  /* 0x2A */	{shift_l_char, shift_l_char},	
  /* 0x2B */	{'\\',	'|'},		
  /* 0x2C */	{'z',	'Z'},		
  /* 0x2D */	{'x',	'X'},		
  /* 0x2E */	{'c',	'C'},		
  /* 0x2F */	{'v',	'V'},		
  /* 0x30 */	{'b',	'B'},		
  /* 0x31 */	{'n',	'N'},		
  /* 0x32 */	{'m',	'M'},		
  /* 0x33 */	{',',	'<'},		
  /* 0x34 */	{'.',	'>'},		
  /* 0x35 */	{'/',	'?'},
  /* 0x36	*/	{shift_r_char, shift_r_char},	
  /* 0x37 */	{'*',	'*'},    	
  /* 0x38 */	{alt_l_char, alt_l_char},
  /* 0x39 */	{' ',	' '},		
  /* 0x3A */	{caps_lock_char, caps_lock_char}
  };


  static void intr_keyboard_handler(void){

      bool ctrl_down_last=ctrl_status;
      bool shift_down_last=shift_status;
      bool caps_lock_last=caps_lock_status;

      bool break_code;
      uint16_t scancode=inb(KBD_BUF_PORT);//必须读取缓冲区数据，否则8042不再继续响应键盘中断

      //打开拓展标志，并返回，（说明要接受的扫描码不止1字节，有两字节）
      if(scancode == 0xe0){
          ext_scancode=true;
          return;
      }

      if(ext_scancode){
          scancode=(0xe000|scancode);
          ext_scancode=false;
      }


      //true则代表是断码，否则是通码
      break_code=((scancode&0x0080)!=0);

      if(break_code){
          uint16_t make_code=(scancode&=0xff7f);

          //改变状态
          if(make_code==ctrl_l_make||make_code==ctrl_r_make){
              ctrl_status=false;
          }else if(make_code == shift_l_make || make_code==shift_r_make){
              shift_status=false;
          }else if(make_code == alt_l_make || make_code ==alt_r_make){
              alt_status=false;
          }

          return;
      }else if((scancode>0x00 && scancode<0x3b)||(scancode == alt_r_make)||(scancode ==ctrl_r_make)){
          
          //shift用于判断keymap到底是要输出元素0还是元素1
          bool shift=false;


          //区分双字符键和单子符键，capslk和shift对双字符键和单字符键作用不一样
          if((scancode < 0x0e) || (scancode == 0x29) || (scancode == 0x1a) || \
          (scancode == 0x1b) || (scancode == 0x2b) || (scancode == 0x27) || \
          (scancode == 0x28) || (scancode == 0x33) || (scancode == 0x34) || \
          (scancode == 0x35)){

              if(shift_down_last){
                  shift = true;
              }

          }else{  //默认是字符键
              if(shift_down_last && caps_lock_last){
                  shift = false; //效果确实是这样子的 我试了一下
              }else if(shift_down_last || caps_lock_last){
                  shift = true; //其中任意一个都是大写的作用
              }else{
                  shift = false;
              } 
          }


          //忽略高8位，也就是0xe0的影响
          uint8_t index=(scancode&=0x00ff);

          char cur_char = keymap[index][shift];

          if(cur_char){
              if(!ioq_full(&kbd_buf)){
  //               put_char(cur_char);
                  ioq_putchar(&kbd_buf,cur_char);
              }
              return;
          }

          if(scancode == ctrl_l_make || scancode == ctrl_r_make){
              ctrl_status = true;
          }  	
          else if(scancode == shift_l_make || scancode == shift_r_make){
              shift_status = true;
          }
          else if(scancode == alt_l_make || scancode == alt_r_make){
              alt_status = true;
          }
          else if(scancode == caps_lock_make){
              caps_lock_status = !caps_lock_status;
          }
          
      }else{
          put_str("unknown key\n");
      }

  }

  void keyboard_init(){
      put_str("keyboard init start\n");
      ioqueue_init(&kbd_buf);
      register_handler(0x21,intr_keyboard_handler);
      put_str("kerboard init done\n");
  }

kernel/interrupt.c（修改）

  //打开主片上的IR0,接受时钟中断和键盘中断
  outb(PIC_M_DATA, 0xfc);
  outb(PIC_S_DATA, 0xff);

（该main.c用两个线程AB充当消费者，键盘键入充当生产者）

kernel/main.c

  #include "print.h"
  #include "init.h"
  #include "debug.h"
  #include "memory.h"
  #include "thread.h"
  #include "console.h"
  #include "interrupt.h"
  #include "ioqueue.h"
  #include "keyboard.h"

  void k_thread_a(void*);
  void k_thread_b(void*);

  int main(void) {
  put_str("I am kernel\n");
  init_all();


  thread_start("k_thread_a",31,k_thread_a," A_");
  thread_start("k_thread_b",31,k_thread_b," B_");

  intr_enable();
  while(1);
  // while(1){
  //    console_put_str("Main ");
  // };
  return 0;
  }


  //在线程中运行的函数
  void k_thread_a(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      enum intr_status old_status =intr_disable();
      if(!ioq_empty(&kbd_buf)){
          console_put_str(para);
          char byte=ioq_getchar(&kbd_buf);
          console_put_char(byte);
      }
      intr_set_status(old_status);
  }
  }

  void k_thread_b(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      enum intr_status old_status =intr_disable();
      if(!ioq_empty(&kbd_buf)){
          console_put_str(para);
          char byte=ioq_getchar(&kbd_buf);
          console_put_char(byte);
      }
      intr_set_status(old_status);
  }
  }

makefile

  BUILD_DIR = ./build
  ENTRY_POINT = 0xc0001500
  AS = nasm
  CC = gcc
  LD = ld
  LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/ -I thread/ 
  ASFLAGS = -f elf

  CFLAGS = -Wall -m32 -fno-stack-protector $(LIB) -c -fno-builtin -W -Wstrict-prototypes -Wmissing-prototypes
  # -fno-stack-protector 闭栈保护的编译选项，栈保护作用是禁止编译器在函数的栈帧中插入栈保护符号，以防止栈溢出攻击。
  # -fno-builtin 告诉编译器不要采用内部函数，因为我们以后会自定义与内部函数同名的函数
  # -Wall 启动所有警告
  # -W 启动常见警告
  # -Wstrict-prototypes  要求函数声明中必须有参数类型，否则警告
  # -Wmissing-prototypes 要求函数必须声明，否则警告

  LDFLAGS =  -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map
  # -Map $(BUILD_DIR)/kernel.map  输出文件build/kernel.map。用于记录kernel符号地址

  OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
      $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o \
      $(BUILD_DIR)/debug.o $(BUILD_DIR)/string.o $(BUILD_DIR)/memory.o \
      $(BUILD_DIR)/bitmap.o $(BUILD_DIR)/thread.o $(BUILD_DIR)/list.o \
      $(BUILD_DIR)/switch.o $(BUILD_DIR)/sync.o $(BUILD_DIR)/console.o \
      $(BUILD_DIR)/keyboard.o $(BUILD_DIR)/ioqueue.o
  # 定义目标文件名集合，用于ld时依赖文件项


  ##############     c代码编译     			###############
  $(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
          lib/stdint.h kernel/init.h lib/string.h kernel/memory.h \
          thread/thread.h kernel/interrupt.h device/console.h \
          device/keyboard.h device/ioqueue.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/init.o: kernel/init.c kernel/init.h lib/kernel/print.h \
          lib/stdint.h kernel/interrupt.h device/timer.h kernel/memory.h \
          thread/thread.h device/console.h device/keyboard.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/interrupt.o: kernel/interrupt.c kernel/interrupt.h \
          lib/stdint.h kernel/global.h lib/kernel/io.h lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/kernel/io.h lib/kernel/print.h \
          kernel/interrupt.h thread/thread.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/debug.o: kernel/debug.c kernel/debug.h \
          lib/kernel/print.h lib/stdint.h kernel/interrupt.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/string.o: lib/string.c lib/string.h \
          kernel/debug.h kernel/global.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h \
          lib/stdint.h lib/kernel/bitmap.h kernel/debug.h lib/string.h \
          lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/bitmap.o: lib/kernel/bitmap.c lib/kernel/bitmap.h \
          lib/string.h kernel/interrupt.h lib/kernel/print.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/thread.o: thread/thread.c thread/thread.h \
          lib/stdint.h lib/string.h kernel/global.h kernel/memory.h \
          kernel/debug.h kernel/interrupt.h lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/list.o: lib/kernel/list.c lib/kernel/list.h \
          kernel/interrupt.h lib/stdint.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/sync.o: thread/sync.c thread/sync.h \
          lib/stdint.h thread/thread.h kernel/debug.h kernel/interrupt.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/console.o: device/console.c device/console.h \
          lib/kernel/print.h thread/sync.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/keyboard.o: device/keyboard.c device/keyboard.h \
          lib/kernel/print.h lib/kernel/io.h kernel/interrupt.h \
          kernel/global.h lib/stdint.h device/ioqueue.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/ioqueue.o: device/ioqueue.c device/ioqueue.h \
          kernel/interrupt.h kernel/global.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  ##############     c代码编译     			###############


  ##############    汇编代码编译    ###############
  $(BUILD_DIR)/kernel.o: kernel/kernel.S
      $(AS) $(ASFLAGS) $< -o $@

  $(BUILD_DIR)/print.o: lib/kernel/print.S
      $(AS) $(ASFLAGS) $< -o $@

  $(BUILD_DIR)/switch.o: thread/switch.S
      $(AS) $(ASFLAGS) $< -o $@
  ##############    汇编代码编译    ###############


  ##############    链接所有目标文件    #############
  $(BUILD_DIR)/kernel.bin: $(OBJS)
      $(LD) $(LDFLAGS) $^ -o $@
  ##############    链接所有目标文件    #############


  ################  伪目标 ###############################
  .PHONY : mk_dir hd clean build all

  mk_dir:
      if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi

  hd:
      dd if=$(BUILD_DIR)/kernel.bin \
          of=/home/sparkle2/bochs/hd60M.img \
          bs=512 count=200 seek=9 conv=notrunc

  clean:
      cd $(BUILD_DIR) && rm -f  ./*

  build: $(BUILD_DIR)/kernel.bin

  all: mk_dir build hd
  ################  伪目标 ###############################

自制简易操作系统（九）

Posted on 2023-11-29 Edited on 2023-11-30

进程和线程

进程和线程的区别：

线程程是具有能动性、执行力、独立的代码块；进程就是线程的集合+资源。

每个进程都有自己独立的内存空间，线程没有自己独立的内存空间，一个进程里的所有线程共享该进程内所有内存空间

线程才是最基本的调度单位（进程的调度比线程更高一级），也可以称为是执行流
进程和线程的状态图

PS：图中写的是进程的状态图，但我们知道线程才是最基本的调度单位，所以我认为这也代表线程的状态图
进程的身份证————PCB

左图是PCB的结构，右图是进程表（也就是PCB的集合）。PCB让我们了解一个进程的各个状态，并给出了上下文环境（PCB的结构并非是固定的，取决于程操作系统的复杂程度，一般一个PCB的大小相当于一个自然页4KB）。进程表将PCB集合存放在一个位置，这样操作系统就会在一个统一的地方查询PCB方便调度
实现线程的两种方式————内核或用户进程

用户进程的意思是，操作系统不支持线程调度（操作系统根本不知道这回事），由用户程序自己实现线程调度（线程表在用户空间）。

内核进程则是操作系统本身就支持线程调度，由操作系统来负责所有进程以及线程的调用（线程表放在内核）

可以说内核进程才是真正发挥出了线程的作用，我们要实现的也是内核进程

在内核空间实现线程

在内核实现线程的关键是PCB的构建，我们引入了三个新的结构体来构建PCB：

我们打算构建的PCB结构如下图所示：

函数thread_start实现创建并运行一个线程，函数之间的逻辑关系如下图所示：

代码如下：

thread/thread.h

  #ifndef __THREAD_THREAD_H__
  #define __THREAD_THREAD_H__

  #include "stdint.h"

  //注意：这是定义一个函数类型 thread_func ,而不是一个函数指针类型
  //定义函数指针类型格式是：typedef void (*thread_func)(void*);
  typedef void thread_func(void*);

  enum task_status{
      TASK_RUNNING,
      TASK_READY,
      TASK_BLOCKED,
      TASK_WAITING,
      TASK_HANGING,
      TASK_DIED,
  };

  //中断栈定义，用于线程中断时保护上下文环境
  struct intr_stack{
      uint32_t vec_no;
      uint32_t edi;
      uint32_t esi;
      uint32_t ebp;
      uint32_t esp_dummy;

      uint32_t ebx;
      uint32_t edx;
      uint32_t ecx;
      uint32_t eax;

      uint32_t gs;
      uint32_t fs;
      uint32_t es;
      uint32_t ds;

      //CPU由低特权级进入高特权级时压入
      uint32_t err_code;

      //定义了一个函数指针
      void* (*eip)(void);
      uint32_t cs;
      uint32_t eflags;
      void* esp;
      uint32_t ss;
  };


  //线程栈
  //1、第一次运行时，eip用于存储线程中待执行的函数
  //2、在switch_to（任务切换）时，eip用于保存新任务的返回地址 
  struct thread_stack{

      //ABI规定被调用函数不允许破坏ebp、ebx、edi、esi、esp，所以我们要将他们保护好（esp由调用约定保护）
      //但其实我也不知道这边的真实用途？？？
      uint32_t ebp;
      uint32_t ebx;
      uint32_t edi;
      uint32_t esi;

      void (*eip)(thread_func* func,void* func_arg);//指向线程待执行函数
      
      void (*unused_retaddr); //占位符，原本该地方放置的应该是线程待执行函数的返回地址
      thread_func* function;  //function是指向thread_func类型函数的指针
      void* func_arg;

  };


  //PCB结构
  struct task_struct{
      uint32_t* self_kstack; //PCB结构中包含了线程的内核栈，该成员变量相当于栈顶指针
      enum task_status status;
      uint8_t priority;
      char name[16];
      uint32_t stack_magic; 
  };


  void thread_create(struct task_struct* pthread, thread_func function,void* func_arg);
  void init_thread(struct task_struct* pthread,char* name,int prio);
  struct task_struct* thread_start(char* name,int prio,thread_func function,void* func_arg);

  #endif

thread/thread.c

  #include "thread.h"
  #include "stdint.h"
  #include "string.h"
  #include "global.h"
  #include "memory.h"

  #define PG_SIZE 4096


  //由kernel_thread去执行function(func_arg)
  static void kernel_thread(thread_func* function,void* func_arg){
      function(func_arg);
  }

  //初始化线程栈
  void thread_create(struct task_struct* pthread, thread_func function,void* func_arg){
      //预留中断栈空间和线程栈空间

      pthread->self_kstack -= sizeof(struct intr_stack);
      pthread->self_kstack -= sizeof(struct thread_stack);
      
      struct thread_stack* kthread_stack=(struct thread_stack*)pthread->self_kstack;

      kthread_stack->eip=kernel_thread;
      kthread_stack->function=function;
      kthread_stack->func_arg=func_arg;
      kthread_stack->ebp=kthread_stack->ebx=kthread_stack->esi=kthread_stack->edi=0;

  }


  //初始化PCB
  void init_thread(struct task_struct* pthread,char* name,int prio){
      memset(pthread,0,sizeof(*pthread));
      strcpy(pthread->name,name);
      pthread->status=TASK_RUNNING;
      pthread->priority=prio;
      pthread->self_kstack=(uint32_t*)((uint32_t)pthread+PG_SIZE);
      pthread->stack_magic=0x19666666; //自定义的魔数

  }

  //创建一个优先级为prio的线程，线程名为name，线程所执行的函数是function(func_arg)
  struct task_struct* thread_start(char* name,int prio,thread_func function,void* func_arg){
      struct task_struct* thread=get_kernel_pages(1);
      init_thread(thread,name,prio);
      thread_create(thread,function,func_arg);

      asm volatile("movl %0,%%esp; pop %%ebp; pop %%ebx; pop %%edi; pop %%esi; ret"::"g"(thread->self_kstack):"memory");

      return thread;
  }

kernel/main.c

  #include "print.h"
  #include "init.h"
  #include "debug.h"
  #include "memory.h"
  #include "thread.h"

  void k_thread_a(void* arg);

  int main(void) {
  put_str("I am kernel\n");
  init_all();


  thread_start("k_thread_a",31,k_thread_a,"argA ");


  while(1);
  return 0;
  }


  //在线程中运行的函数
  void k_thread_a(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      put_str(para);
  }
  }

多线程调度

要实现多线程调度，我们的PCB就不能像之前那么简单了，之间的PCB只是一个简单的示范。我们现在要给PCB增加一些新的成员，相应的一些线程相关函数也要有对应的更改。

想要实现多线程调度的关键是维护两个队列，一个是进程就绪队列，还有一个是所有进程队列(包括被阻塞的进程)。而如果我们把整个PCB作为链表的节点来说实在是太麻烦了，不够灵活（整个链表的遍历负担也大）。所以我们需要一个轻量级的链表。

我们在PCB中引入新的成员：struct list_elem general_tag; //存放在一般队列中的节点 和struct list_elem all_list_tag; //存在在所有线程队列的节点，这样的节点元素只有前指针和后指针两个元素8字节大小，维护两个这样的tag链表代替PCB链表。当然我们必须能够实现对应tag和PCB指针之间的相互转换才能真正实现该队列。

新的PCB结构如以下代码：

thread/thread.h(部分代码)

  //PCB结构
  struct task_struct{
      uint32_t* self_kstack; //PCB结构中包含了线程的内核栈，该成员变量相当于栈顶指针
      enum task_status status;
      char name[16];
      uint8_t priority; //把优先级设置位一次执行时间片的长短，优先级越高则一次时间片越长
      uint8_t ticks;   //时间片，记录再执行几次时钟中断就将它换下
      uint32_t elapsed_ticks;  //该线程在CPU执行的总时钟中断数
      struct list_elem general_tag;  //存放在一般队列中的节点
      struct list_elem all_list_tag; //存在在所有线程队列的节点
      uint32_t* pgdir;         //进程自己页表的虚拟地址（线程没有自己的页表则该值为0）
      uint32_t stack_magic;   //该数字位于PCB结构的最高位，也就是说一旦PCB的栈顶冲破了PCB信息结构，
                              //stack_magic会最先被破坏，因此用该位判断PCB的内核栈是否越界
  };

修改后的thread/thread.c代码

  #include "thread.h"
  #include "stdint.h"
  #include "string.h"
  #include "global.h"
  #include "memory.h"
  #include "interrupt.h"

  #define PG_SIZE 4096


  struct task_struct* main_thread;  //主线程PCB
  struct list thread_ready_list;     //就绪队列
  struct list thread_all_list;      //所有线程队列
  static struct list_elem* thread_tag;  //用于 tag转化为PCB指针 时的中介

  extern void switch_to(struct task_struct* cur,struct task_struct* next);


  //返回当前线程的PCB指针
  //当前esp存取的是当前线程的栈顶指针，而线程的栈全在PCB中，所以取当前栈顶指针的前20位即是PCB其实地址
  struct task_struct* running_thread(){
      uint32_t esp;
      asm ("mov %%esp,%0":"=g"(esp));
      return (struct task_struct*)(esp & 0xfffff000);
  }

  //由kernel_thread去执行function(func_arg)
  static void kernel_thread(thread_func* function,void* func_arg){
      intr_enable();//开启中断，避免线程独占CPU
      function(func_arg);
  }

  //初始化线程栈
  void thread_create(struct task_struct* pthread, thread_func function,void* func_arg){
      //预留中断栈空间和线程栈空间

      pthread->self_kstack -= sizeof(struct intr_stack);
      pthread->self_kstack -= sizeof(struct thread_stack);
      
      struct thread_stack* kthread_stack=(struct thread_stack*)pthread->self_kstack;

      kthread_stack->eip=kernel_thread;
      kthread_stack->function=function;
      kthread_stack->func_arg=func_arg;
      kthread_stack->ebp=kthread_stack->ebx=kthread_stack->esi=kthread_stack->edi=0;

  }


  //初始化PCB
  void init_thread(struct task_struct* pthread,char* name,int prio){
      memset(pthread,0,sizeof(*pthread));
      strcpy(pthread->name,name);

      if(pthread==main_thread){
          pthread->status=TASK_RUNNING;
      }else{
          pthread->status=TASK_READY;
      }
      
      pthread->self_kstack=(uint32_t*)((uint32_t)pthread+PG_SIZE);
      pthread->priority=prio;
      pthread->ticks=prio;
      pthread->elapsed_ticks=0;
      pthread->pgdir=NULL;//线程没有自己的地址空间
      pthread->stack_magic=0x19870916; //自定义的魔数，这个值一旦被不一样了，就证明栈顶越界了

  }

  //创建一个优先级为prio的线程，线程名为name，线程所执行的函数是function(func_arg)
  struct task_struct* thread_start(char* name,int prio,thread_func function,void* func_arg){
      struct task_struct* thread=get_kernel_pages(1);
      init_thread(thread,name,prio);
      thread_create(thread,function,func_arg);


      //确保线程之前不在队列里
      ASSERT(!elem_find(&thread_ready_list,&thread->general_tag));     
      list_append(&thread_ready_list,&thread->general_tag);
      
      ASSERT(!elem_find(&thread_all_list,&thread->all_list_tag));
      list_append(&thread_all_list,&thread->all_list_tag);


      return thread;
  }


  //完善kernel中的main的主线程
  //我怎么确定主线程在0xc009e00？？？
  static void make_main_thread(void){
      main_thread=running_thread();

      init_thread(main_thread,"main",31);

      ASSERT(!elem_find(&thread_all_list,&main_thread->all_list_tag));
      list_append(&thread_all_list,&main_thread->all_list_tag);
  }

接下来我们要实现一些新的函数，借助新函数来完成进程调度和上下文切换，新函数之间的逻辑关系如下：

代码如下：

kernel/interrupt.c

  //为专门的中断号注册专门的中断函数
  void register_handler(uint8_t vector_no,intr_handler function){
      idt_table[vector_no]=function;
  }

device/timer.c

  static void intr_timer_handler(void){
      struct task_struct* cur_thread =running_thread();

      //检测栈是否溢出
      ASSERT(cur_thread->stack_magic==0x19870916);


      cur_thread->elapsed_ticks++;
      ticks++;

      if(cur_thread->ticks == 0){
          schedule();
      }else{
          cur_thread->ticks--;
      }

  }

PS:记得在时钟初始化上调用注册函数注册时钟中断的专门处理函数

thread/switch.S

  [bits 32]
  section .text
  global switch_to
  switch_to:
      ;此处是返回地址
      push esi
      push edi
      push ebx
      push ebp

      mov eax,[esp+20]    ;得到栈中参数cur
      mov [eax],esp       ;保存栈顶指针esp到self_kstack;

  ;-------------以上是备份环境，下面是恢复下一个线程的环境------------

      mov eax,[esp+24]    ;得到栈中参数next
      mov esp,[eax]       ;pcb的第一个成员是self_kstack

      pop ebp
      pop ebx
      pop edi
      pop esi
      
      ret

thread/thread.c

  void schedule(){
      ASSERT(intr_get_status()==INTR_OFF);

      struct task_struct* cur =running_thread();
      if(cur->status==TASK_RUNNING){
          //时间片时间到了,将cpu上的线程重置时间片后放回就绪队列尾部
          ASSERT(!elem_find(&thread_ready_list,&cur->general_tag));
          list_append(&thread_ready_list,&cur->general_tag);
          cur->ticks=cur->priority;
          cur->status=TASK_READY;
      }else{
          //如果是被阻塞的话，就不同特殊处理
          //因为被阻塞线程本身就不在就绪队列中
          //只需要调度新的线程进来就行了
      }

      ASSERT(!list_empty(&thread_ready_list));
      
      //将thread_ready_list队列中第一个就绪栈弹出，准备将其调度上CPU
      thread_tag=NULL;
      thread_tag=list_pop(&thread_ready_list);
      struct task_struct* next=elem2entry(struct task_struct,general_tag,thread_tag);
      next->status=TASK_RUNNING;
      switch_to(cur,next);
  }

kernel/main.c

  #include "print.h"
  #include "init.h"
  #include "debug.h"
  #include "memory.h"
  #include "thread.h"

  void k_thread_a(void*);
  void k_thread_b(void*);

  int main(void) {
  put_str("I am kernel\n");
  init_all();


  thread_start("k_thread_a",31,k_thread_a,"argA ");
  thread_start("k_thread_b",8,k_thread_b,"argB ");

  intr_enable();
  while(1){
      put_str("Main ");
  };
  
  return 0;
  }


  //在线程中运行的函数
  void k_thread_a(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      put_str(para);
  }
  }

  void k_thread_b(void* arg){
  //被调用的函数知道自己需要什么类型的参数，自己转换再用
  char* para=arg;

  while(1){
      put_str(para);
  }
  }

makefile

  BUILD_DIR = ./build
  ENTRY_POINT = 0xc0001500
  AS = nasm
  CC = gcc
  LD = ld
  LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/ -I thread/ 
  ASFLAGS = -f elf

  CFLAGS = -Wall -m32 -fno-stack-protector $(LIB) -c -fno-builtin -W -Wstrict-prototypes -Wmissing-prototypes
  # -fno-stack-protector 闭栈保护的编译选项，栈保护作用是禁止编译器在函数的栈帧中插入栈保护符号，以防止栈溢出攻击。
  # -fno-builtin 告诉编译器不要采用内部函数，因为我们以后会自定义与内部函数同名的函数
  # -Wall 启动所有警告
  # -W 启动常见警告
  # -Wstrict-prototypes  要求函数声明中必须有参数类型，否则警告
  # -Wmissing-prototypes 要求函数必须声明，否则警告

  LDFLAGS =  -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map
  # -Map $(BUILD_DIR)/kernel.map  输出文件build/kernel.map。用于记录kernel符号地址

  OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
      $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o \
      $(BUILD_DIR)/debug.o $(BUILD_DIR)/string.o $(BUILD_DIR)/memory.o \
      $(BUILD_DIR)/bitmap.o $(BUILD_DIR)/thread.o $(BUILD_DIR)/list.o \
      $(BUILD_DIR)/switch.o
  # 定义目标文件名集合，用于ld时依赖文件项


  ##############     c代码编译     			###############
  $(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
          lib/stdint.h kernel/init.h lib/string.h kernel/memory.h \
          thread/thread.h kernel/interrupt.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/init.o: kernel/init.c kernel/init.h lib/kernel/print.h \
          lib/stdint.h kernel/interrupt.h device/timer.h kernel/memory.h \
          thread/thread.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/interrupt.o: kernel/interrupt.c kernel/interrupt.h \
          lib/stdint.h kernel/global.h lib/kernel/io.h lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/kernel/io.h lib/kernel/print.h \
          kernel/interrupt.h thread/thread.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/debug.o: kernel/debug.c kernel/debug.h \
          lib/kernel/print.h lib/stdint.h kernel/interrupt.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/string.o: lib/string.c lib/string.h \
          kernel/debug.h kernel/global.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h \
          lib/stdint.h lib/kernel/bitmap.h kernel/debug.h lib/string.h \
          lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/bitmap.o: lib/kernel/bitmap.c lib/kernel/bitmap.h \
          lib/string.h kernel/interrupt.h lib/kernel/print.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/thread.o: thread/thread.c thread/thread.h \
          lib/stdint.h lib/string.h kernel/global.h kernel/memory.h \
          kernel/debug.h kernel/interrupt.h lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/list.o: lib/kernel/list.c lib/kernel/list.h \
          kernel/interrupt.h lib/stdint.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@

  ##############     c代码编译     			###############


  ##############    汇编代码编译    ###############
  $(BUILD_DIR)/kernel.o: kernel/kernel.S
      $(AS) $(ASFLAGS) $< -o $@

  $(BUILD_DIR)/print.o: lib/kernel/print.S
      $(AS) $(ASFLAGS) $< -o $@

  $(BUILD_DIR)/switch.o: thread/switch.S
      $(AS) $(ASFLAGS) $< -o $@
  ##############    汇编代码编译    ###############


  ##############    链接所有目标文件    #############
  $(BUILD_DIR)/kernel.bin: $(OBJS)
      $(LD) $(LDFLAGS) $^ -o $@
  ##############    链接所有目标文件    #############


  ################  伪目标 ###############################
  .PHONY : mk_dir hd clean build all

  mk_dir:
      if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi

  hd:
      dd if=$(BUILD_DIR)/kernel.bin \
          of=/home/sparkle2/bochs/hd60M.img \
          bs=512 count=200 seek=9 conv=notrunc

  clean:
      cd $(BUILD_DIR) && rm -f  ./*

  build: $(BUILD_DIR)/kernel.bin

  all: mk_dir build hd
  ################  伪目标 ###############################

一定要从main函数开始，跟着流程走一遍，才能真正理解线程之间的压栈出栈和跳转。

注意！PCB结构中的intr_stack和thread_stack只是规定了入栈出栈的顺序，二者的位置则是不固定的，并不是说二者的位置就一定固定在栈顶

自制简易操作系统（八）

Posted on 2023-11-25 Edited on 2023-11-28

断言assert

断言即断定的说，是一种用来调试的手段。比如我在程序的某个地方这断定的说flag=1（ASSERT(flag==1)）,如果条件成立则无事发生，如果不成立则触发断言屏幕悬停并在屏幕上打印错误信息。断言还分为系统断言和用户断言，我们本节要通过宏定义实现系统断言。

断言触发时我们希望能停止中断（避免CPU中断切换任务），所以首先我们需要能灵活打开关闭中断(eflags里的’IF’位)的函数。于是我们在interrupt.c里添加了四个工具函数以实现灵活控制中断。

新增代码如下：

kernel/interrupt.h：

  #ifndef __KERNEL_INTERRUPT_H__
  #define __KERNEL_INTERRUPT_H__

  typedef void* intr_handler;

  void idt_init(void);

  enum intr_status{
      INTR_OFF,
      INTR_ON
  };

  enum intr_status intr_get_status(void);
  enum intr_status intr_set_status(enum intr_status);
  enum intr_status intr_enable(void);
  enum intr_status intr_disable(void);

  #endif

kernel/interrupt.c:

  #define EFLAGS_IF 0x00000200

  //用内联汇编实现查询eflags状态
  #define GET_EFLAGS(EFLAG_VAR) asm volatile("pushfl; popl %0": "=g"(EFLAG_VAR))

  //开中断并返回当前状态
  enum intr_status intr_enable()
  {
      if(intr_get_status() != INTR_ON)
      {
          asm volatile("sti");
          return INTR_OFF;
      }
      return INTR_ON;
  }

  //关中断并返回当前状态
  enum intr_status intr_disable()
  {
      if(intr_get_status() != INTR_OFF)
      {
          asm volatile("cli");
          return INTR_ON;
      }
      return INTR_OFF;
  }

  //设置中断状态
  enum intr_status intr_set_status(enum intr_status status)
  {
      return (status & INTR_ON) ? intr_enable() : intr_disable();
  }

  //获取中断状态
  enum intr_status intr_get_status()
  {
      uint32_t eflags = 0;
      GET_EFLAGS(eflags);
      return (eflags & EFLAGS_IF) ? INTR_ON : INTR_OFF; 
  }

接下来我们要用宏定义实现断言:

kernel/debug.h:

  #ifndef __KERNEL_DEBUG_H__
  #define __KERNEL_DEBUG_H__

  void panic_spin(char* filename,int line,const char* func,const char*condition);

  #define PANIC(...) panic_spin(__FILE__ , __LINE__ , __func__, __VA_ARGS__)
  //(...)是可变宏参数, __VA_ARGS__预处理器专用标识符，他就相当于是可变宏参数的形参
  //__FILE__ , __LINE__ , __func__则是由系统自动提供的，分别代表文件名、行号、函数名


  //如果通过编译器定义了NDEBUG(`gcc-DNDEBUG`)就把断言清空（避免影响系统运作速度）
  //否则就在有断言的地方进行条件判断，条件为假则触发断言函数
  #ifdef NDEBUG 
  #define ASSERT(CONDITION) ((void)0)
  #else
  #define ASSERT(CONDITION) \
  if(CONDITION){}        \
  else{ PANIC(#CONDITION); }
  //#CONDITION是将CONDITION转化为字符串传入宏函数PANIC

  #endif
  #endif

kernel/debug.c：

  #include"debug.h"
  #include"../lib/kernel/print.h"
  #include"interrupt.h"

  void panic_spin(char* filename,int line,const char* func,const char*condition){

      intr_disable();                 //关闭中断，防止cpu处理其他进程被调换

      //打印错误信息
      put_str("\n\n\n\\**********ERROR\\**********\\\n");
      put_str("Filename: ");put_str(filename);put_char('\n');
      put_str("Line: "); put_int(line); put_char('\n');
      put_str("Func: ");put_str((char*)func);put_char('\n');
      put_str("Condition: ");put_str((char*)condition);put_char('\n');
      put_str("\\**********ERROR\\**********\\\n");

      while(1);
  }

make和makefile

之前我们都是把每一个独立的.c/.S文件编译成.o文件，然后再一起链接。手动输入命令太过麻烦，而且如果其中一个头文件被修改过，所有引用过该头文件的文件都需要重新编译。而如果一个.o文件被修改过，所有文件都要重新链接。在复杂的系统里用人工来处理这件事是相当麻烦的，所以我们引用了make和makefile来帮助我们快捷的编译链接文件。

make是命令，makefile则是写规则的文件。

makefile里最基础的规则格式如下:

目标文件:依赖文件
[Tab]命令

当我们使用命令make 目标文件时，系统会自动检测所有依赖文件，如果依赖文件没有新的修改，则无事发生；如果依赖文件被修改过了，则执行shell命令。shell命令一般是将所有依赖文件编译成目标文件。

这里不再讲述更多的makefile语法，需要的话请网上查找

当前的makefile文件如下：

    BUILD_DIR = ./build
    ENTRY_POINT = 0xc0001500
    AS = nasm
    CC = gcc
    LD = ld
    LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/ 
    ASFLAGS = -f elf

    CFLAGS = -Wall -m32 -fno-stack-protector $(LIB) -c -fno-builtin -W -Wstrict-prototypes -Wmissing-prototypes
    # -fno-stack-protector 闭栈保护的编译选项，栈保护作用是禁止编译器在函数的栈帧中插入栈保护符号，以防止栈溢出攻击。
    # -fno-builtin 告诉编译器不要采用内部函数，因为我们以后会自定义与内部函数同名的函数
    # -Wall 启动所有警告
    # -W 启动常见警告
    # -Wstrict-prototypes  要求函数声明中必须有参数类型，否则警告
    # -Wmissing-prototypes 要求函数必须声明，否则警告

    LDFLAGS =  -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map
    # -Map $(BUILD_DIR)/kernel.map  输出文件build/kernel.map。用于记录kernel符号地址

    OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
        $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o \
        $(BUILD_DIR)/debug.o 
    # 定义目标文件名集合，用于ld时依赖文件项


    ##############     c代码编译     			###############
    $(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
            lib/stdint.h kernel/init.h
        $(CC) $(CFLAGS) $< -o $@

    $(BUILD_DIR)/init.o: kernel/init.c kernel/init.h lib/kernel/print.h \
            lib/stdint.h kernel/interrupt.h device/timer.h
        $(CC) $(CFLAGS) $< -o $@

    $(BUILD_DIR)/interrupt.o: kernel/interrupt.c kernel/interrupt.h \
            lib/stdint.h kernel/global.h lib/kernel/io.h lib/kernel/print.h
        $(CC) $(CFLAGS) $< -o $@

    $(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/stdint.h\
            lib/kernel/io.h lib/kernel/print.h
        $(CC) $(CFLAGS) $< -o $@

    $(BUILD_DIR)/debug.o: kernel/debug.c kernel/debug.h \
            lib/kernel/print.h lib/stdint.h kernel/interrupt.h
        $(CC) $(CFLAGS) $< -o $@
    ##############     c代码编译     			###############


    ##############    汇编代码编译    ###############
    $(BUILD_DIR)/kernel.o: kernel/kernel.S
        $(AS) $(ASFLAGS) $< -o $@

    $(BUILD_DIR)/print.o: lib/kernel/print.S
        $(AS) $(ASFLAGS) $< -o $@
    ##############    汇编代码编译    ###############


    ##############    链接所有目标文件    #############
    $(BUILD_DIR)/kernel.bin: $(OBJS)
        $(LD) $(LDFLAGS) $^ -o $@
    ##############    链接所有目标文件    #############


    ################  伪目标 ###############################
    .PHONY : mk_dir hd clean build all

    mk_dir:
        if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi

    hd:
        dd if=$(BUILD_DIR)/kernel.bin \
            of=/home/sparkle2/bochs/hd60M.img \
            bs=512 count=200 seek=9 conv=notrunc

    clean:
        cd $(BUILD_DIR) && rm -f  ./*

    build: $(BUILD_DIR)/kernel.bin

    all: mk_dir build hd
    ################  伪目标 ###############################

实现自己的字符串操作函数

lib/string.h

  #ifndef __LIB_STRING_H
  #define __LIB_STRING_H

  #include "stdint.h"
  #define NULL 0

  void memset(void* dst_,uint8_t value,uint32_t size);
  void memcpy(void* dst_,const void* src_,uint32_t size);
  int memcmp(const void* a_,const void* b_, uint32_t size);
  char* strcpy(char* dst_,const char* src_);
  uint32_t strlen(const char* str);
  int8_t strcmp(const char* a,const char* b);
  char* strchr(const char* str,const char ch);
  char* strrchr(const char* str,const uint8_t ch);
  char* strcat(char* dst_,const char* src_);
  char* strchrs(const char* str,uint8_t ch);
  #endif

lib/string.c

  #include"string.h"
  #include"global.h"
  #include"debug.h"

  //将dst_起始的size个字节置为value
  void memset(void* dst_,uint8_t value,uint32_t size){
      ASSERT(dst_!=NULL);
      uint8_t* dst =(uint8_t*)dst_;
      while(size-- >0){
          *dst++=value;
      }
  }

  //将src_起始的size个字复制到dst_
  void memcpy(void* dst_,const void* src_,uint32_t size)
  {
      ASSERT(dst_ != NULL && src_ != NULL);
      uint8_t* dst = dst_;
      const uint8_t* src = src_;
      while((size--) > 0)
          *dst++= *src++;
      return;
  }

  //连续比较地址a和地址b开头的size字节，若相等则返回0，a>b返回1，a<b返回-1
  int memcmp(const void* a_,const void* b_, uint32_t size)
  {
      const char* a = a_;
      const char* b = b_;
      ASSERT(a != NULL || b != NULL);
      while((size--) > 0)
      {
          if(*a != *b)	return (*a > *b) ? 1 : -1;
          a++;
          b++;
      }
      return 0;
  }


  //将字符串从src_复制到dst_
  char* strcpy(char* dst_,const char* src_)
  {
      ASSERT(dst_ != NULL && src_ != NULL);
      char* dst = dst_;
      while((*(dst_++) = *(src_++) ));
      return dst;     
  }

  //返回字符串长度
  uint32_t strlen(const char* str)
  {
      ASSERT(str != NULL);
      const char* ptr = str;
      while(*(ptr++));
      return (ptr - str - 1);             //例如一个字 1 '\0' ptr会指向'\0'后面一位
  }


  //比较两个字符串，a>b返回1，a<b返回-1，a==b返回0
  int8_t strcmp(const char* a,const char* b)
  {
      ASSERT(a != NULL && b != NULL);
      while(*a!=0 && *a == *b)
      {
          a++,b++;
      }   
      return (*a < *b) ? -1 : (*a > *b) ; 
  }

  //从左到右查找字符串str中首次出现的字符ch的地址
  char* strchr(const char* str,const char ch)
  {
      ASSERT(str != NULL);
      while(*str)
      {
          if(*str == ch)
              return (char*)str;
          str++;
      } 
      return NULL;
  }

  //从后往前查找字符串str中首次出现字符ch的地址
  char* strrchr(const char* str,const uint8_t ch)
  {
      ASSERT(str != NULL);
      const char* last_chrptr = NULL;
      while(*str != 0)
      {
          if(ch == *str)	
              last_chrptr = str;
          str++;
      }
      return (char*)last_chrptr;   
  }

  //将字符串src_拼接到dst_后，返回拼接的串地址
  char* strcat(char* dst_,const char* src_)
  {
      ASSERT(dst_ != NULL && src_ != NULL);
      char* str = dst_;
      while(*(str++));
      str--;
      while((*str++ = *src_++));
      return dst_;
  }

  //在字符串str中查找字符ch出现的次数
  char* strchrs(const char* str,uint8_t ch)
  {
      ASSERT(str != NULL);
      uint32_t ch_cnt = 0;
      const char*p =str;
      while(*p!=0){
          if(*p==ch){
              ch_cnt++;
          }
          p++;
      }
      return ch_cnt
  }

位图bitmap以及函数实现

我们引入一种数据结构用于资源管理：位图

位图是一个线性数组，其中每一位都代表着对应的物理页(4KB)是否空闲，如下图所示：

bitmap的数据结构以及工具代码如下：

lib/kernel/bitmap.h

  #ifndef __KERNEL_BITMAP_H__
  #define __KERNEL_BITMAP_H__

  #include "global.h"

  #define BITMAP_MASK 1
  struct bitmap{
      uint32_t btmp_bytes_len;
      uint8_t* btmp_ptr;
  };

  void bitmap_init(struct bitmap* btmp);
  bool bitmap_scan_test(struct bitmap*btmp,uint32_t bit_idx);
  int bitmap_scan(struct bitmap*btmp,uint32_t cnt);
  void bitmap_set(struct bitmap* btmp,uint32_t bit_idx,int8_t value);

  #endif

lib/kernel/bitmap.c

  #include"bitmap.h"
  #include"stdint.h"
  #include"string.h"
  #include"print.h"
  #include"interrupt.h"
  #include"debug.h"

  void bitmap_init(struct bitmap* btmp){
      memset(btmp->btmp_ptr,0,btmp->btmp_bytes_len);
  }


  //返回btmp中第bit_idx位的状态
  bool bitmap_scan_test(struct bitmap*btmp,uint32_t bit_idx){
      uint32_t byte_idx=bit_idx/8;
      uint32_t bit_remainder=bit_idx%8;
      return btmp->btmp_ptr[byte_idx] & (BITMAP_MASK<<bit_remainder);
  }

  //返回btmp里第一个连续cnt字节的空闲空间的起始地址,找不到则返回-1
  int bitmap_scan(struct bitmap*btmp,uint32_t cnt){
      uint32_t free_byte_idx=0;   //用于记录空闲位所在字节

      while((0xff==btmp->btmp_ptr[free_byte_idx])&&(free_byte_idx<btmp->btmp_bytes_len)){
          free_byte_idx++;
      }

      ASSERT(free_byte_idx<btmp->btmp_bytes_len);
      if(free_byte_idx == btmp->btmp_bytes_len){
          return -1;
      }

      int free_bit_idx=0;
      while( (uint8_t)(BITMAP_MASK<<free_bit_idx) & btmp->btmp_ptr[free_byte_idx] ){
          free_bit_idx++;
      }

      int free_bit_idx_strat=free_byte_idx*8+free_bit_idx;
      if(cnt==1){
          return free_bit_idx_strat;
      }

      uint32_t bit_leftover=btmp->btmp_bytes_len*8-free_bit_idx_strat;

      uint32_t next_bit=free_bit_idx_strat+1;
      uint32_t count=1; //用于记录找到空闲位的个数

      free_bit_idx_strat=-1;//假设找不到连续的字节那就返回-1

      while(bit_leftover--){
          if(!(bitmap_scan_test(btmp,next_bit))){
              count++;
          }else{
              count=0;
          }

          if(count==cnt){
              free_bit_idx_strat=next_bit-cnt+1;
              break;
          }
          next_bit++;
      }
      return free_bit_idx_strat;

  }

  void bitmap_set(struct bitmap* btmp,uint32_t bit_idx,int8_t value){
      ASSERT((value==0) ||(value==1));
      uint32_t byte_idx =bit_idx/8;
      uint32_t bit_remainder=bit_idx%8;

      if(value){
          btmp->btmp_ptr[byte_idx] |= (BITMAP_MASK<<bit_remainder);
      }else{
          btmp->btmp_ptr[byte_idx] &= (BITMAP_MASK<<bit_remainder);
      }

  }

内存管理系统

内存池规划

分页机制下有了虚拟地址和物理地址，操作系统有责任把这两种地址分别管理，并通过页表将这两类地址关联。为了实现内存管理，我们需要实现一个数据结构————内存池

我们打算将物理内存划分为两个内存池，一半用于内核，一半用于用户。并使用内核物理内存池和用户物理内存池来分配物理地址。

而对于每一个进程，我们都需要一个虚拟用户内存池来分配虚拟地址给进程；也需要一个虚拟内核内存池来分配虚拟地址给内核。

接下来我们要实现memory.h和memory.c文件，在这两个文件里实现内核物理内存池、用户物理内存池以及一个虚拟内核内存池（现在一个进程都没有，自然不需要虚拟内核用户池）

memory.c里引入了两种新数据结构：pool(物理内存池)、virtual_addr(虚拟内存池)

两种数据结构的构造以及3个内存池的初始化请看以下代码和图片：

memory.c的代码逻辑（五步走）：
执行完mem_init()后的物理低端1MB内存布局：

kernel/memory.h:

  #ifndef __KERNEL_MEMORY_H__
  #define __KERNEL_MEMORY_H__

  #include "stdint.h"
  #include "bitmap.h"


  //虚拟地址池
  struct virtual_addr{
      struct bitmap vaddr_bitmap;
      uint32_t vaddr_start;
  };

  extern struct pool kernel_pool,user_pool;

  void men_init(void);


  #endif

kernel/memory.c:

  #include "memory.h"
  #include "stdint.h"
  #include "print.h"

  #define PG_SIZE 4096

  //0xc009f00是内核栈栈顶，0xc009e00分给内核主线程PCB,0xc009a00~0xc009e00这四个页的空间大小全给位图(可管理一共512MB空间)
  #define MEM_BITMAP_BASE 0xc009a000
  #define K_HEAP_START 0xc0100000


  //物理内存池
  struct pool{
      struct bitmap pool_bitmap;
      uint32_t phy_addr_start;
      uint32_t pool_size;
  };

  struct pool kernel_pool,user_pool;

  struct virtual_addr kernel_vaddr;

  static void mem_pool_init(uint32_t all_mem){
      put_str(" mem_pool_init start\n");

      //从物理地址0x100000开始往上，一共有一个页目录和255个页表，总共256个页表
      uint32_t page_table_size=PG_SIZE*256;
      //加上0x100000后就是我们可以使用的物理地址起始地址
      uint32_t used_mem=page_table_size+0x100000;

      uint32_t free_mem=all_mem-used_mem;
      uint16_t all_free_pages=free_mem/PG_SIZE;
      
      uint16_t kernel_free_pages=all_free_pages/2;
      uint16_t user_free_pages=all_free_pages-kernel_free_pages;

      //一字节位图可以代表8页
      uint32_t kbm_length=kernel_free_pages/8;
      uint32_t ubm_length=user_free_pages/8;

      uint32_t kp_start=used_mem;
      uint32_t up_start=kp_start+kernel_free_pages*PG_SIZE;

      kernel_pool.phy_addr_start=kp_start;
      user_pool.phy_addr_start=up_start;

      kernel_pool.pool_size=kernel_free_pages*PG_SIZE;
      user_pool.pool_size=user_free_pages*PG_SIZE;

      kernel_pool.pool_bitmap.btmp_bytes_len=kbm_length;
      user_pool.pool_bitmap.btmp_bytes_len=ubm_length;

      kernel_pool.pool_bitmap.btmp_ptr=(void*)MEM_BITMAP_BASE;
      user_pool.pool_bitmap.btmp_ptr=(void*)(MEM_BITMAP_BASE+kbm_length);

      put_str("       kernel_pool_bitmap_start:");
      put_int((int)kernel_pool.pool_bitmap.btmp_ptr);
      put_str("   kernel_pool_phy_addr_start:");
      put_int((int)kernel_pool.phy_addr_start);
      put_str("\n");

      put_str("       user_pool_bitmap_start:");
      put_int((int)user_pool.pool_bitmap.btmp_ptr);
      put_str("   user_pool_phy_addr_start:");
      put_int((int)user_pool.phy_addr_start);
      put_str("\n");

      bitmap_init(&kernel_pool.pool_bitmap);
      bitmap_init(&user_pool.pool_bitmap);

      
      //初始化内核虚拟内存池
      kernel_vaddr.vaddr_bitmap.btmp_bytes_len=kbm_length;
      kernel_vaddr.vaddr_bitmap.btmp_ptr=(void*)(MEM_BITMAP_BASE+kbm_length+ubm_length);
      kernel_vaddr.vaddr_start=K_HEAP_START;
      bitmap_init(&kernel_vaddr.vaddr_bitmap);
      put_str("   mem_pool_init done\n");
      
  }


  void mem_init(){
      put_str("mem_init start\n");
      uint32_t mem_bytes_total=(*(uint32_t*)(0xb03));//我们计算出来的地址存到0xb03里
      mem_pool_init(mem_bytes_total);
      put_str("mem_init done\n");
  }

内存管理系统第一步，分配内存页

我们已经完成内存池的规划以及初始化函数，现在我们要实现malloc函数（我们实现的malloc函数只能以页为单位分配），实现系统调用分配内存。

malloc_page的逻辑如下：

其中page_table_add(vaddr,page_phyaddr)的逻辑较为复制，因此绘制其流程图：

代码如下：

kernel/memory.c(增加部分):

  #include "memory.h"
  #include "stdint.h"
  #include "print.h"
  #include "bitmap.h"
  #include "global.h"
  #include "debug.h"
  #include "string.h"


  #define PDE_IDX(addr)   ((addr & 0xffc00000)>>22)
  #define PTE_IDX(addr)   ((addr & 0x003ff000)>>12)

  #define PG_SIZE 4096



  //  内核/用户 向虚拟内存池申请连续个pg_cnt个虚拟地址，成功返回地址起点，失败返回-1
  static void* vaddr_get(enum pool_flags pf,uint32_t pg_cnt){
      int vaddr_start=0,bit_idx_start=-1;
      uint32_t cnt=0;
      if( pf ==PF_KERNEL){
          bit_idx_start=bitmap_scan(&kernel_vaddr.vaddr_bitmap,pg_cnt);
          if(bit_idx_start==-1){
              return NULL;
          }
          while(cnt<pg_cnt){
              bitmap_set(&kernel_vaddr.vaddr_bitmap,bit_idx_start+cnt++,1);
          }
          vaddr_start=kernel_vaddr.vaddr_start+bit_idx_start*PG_SIZE;
      }else{
          //用户内存池，将来实现
      }
      return (void*)vaddr_start;
  }

  // 内核/用户 向物理内存池申请连续1页，成功返回地址起点，失败返回-1
  static void* palloc(struct pool* m_pool){
      int bit_idx_start=bitmap_scan(&m_pool->pool_bitmap,1);
      if(bit_idx_start==-1){
          return NULL;
      }
      bitmap_set(&m_pool->pool_bitmap,bit_idx_start,1);
      uint32_t page_phyaddr=((bit_idx_start*PG_SIZE)+m_pool->phy_addr_start);
      return (void*)page_phyaddr;
  }

  //得到虚拟地址vaddr对应的pte指针
  uint32_t* pte_ptr(uint32_t vaddr){
      //该公式见第五章关于页目录自映射
      uint32_t* pte=(uint32_t*)(0xffc00000+ ((vaddr & 0xffc00000)>>10)+PTE_IDX(vaddr)*4);
      return pte;
  }

  //得到虚拟地址vaddr对应的pde指针
  uint32_t* pde_ptr(uint32_t vaddr){
      //该公式见第五章关于页目录自映射
      uint32_t* pde=(uint32_t*)((0xfffff000) + PDE_IDX(vaddr)*4);
      return pde;
  }


  //建立从虚拟地址到物理地址的映射
  static void page_table_add(void* _vaddr,void* _page_phyaddr){
      uint32_t vaddr=(uint32_t)_vaddr,page_phyaddr=(uint32_t)_page_phyaddr;

      //指针本身就是虚拟地址
      uint32_t* pde=pde_ptr(vaddr);
      uint32_t* pte=pte_ptr(vaddr);


      if(*pde & 0x00000001){
          ASSERT(!(*pte & 0x00000001));
          if(!(*pte & 0x00000001)){
              *pte=(page_phyaddr|PG_US_U|PG_RW_W|PG_P_1);
          }else{
              PANIC("pte repeat");
              *pte=(page_phyaddr|PG_US_U|PG_RW_W|PG_P_1);
          }
      }else{
          //这儿为页表申请地址，pde_phyaddr记录的其实是页表的其实地址
          uint32_t pde_phyaddr=(uint32_t)palloc(&kernel_pool);
          *pde=(pde_phyaddr|PG_US_U|PG_RW_W|PG_P_1);
          
          memset((void*)((int)pte & 0xfffff000),0,PG_SIZE);

          ASSERT(!(*pte & 0x00000001));

          *pte=(page_phyaddr|PG_US_U|PG_RW_W|PG_P_1);
      }

  }

  //实现自己的以页为单位分配空间的malloc函数,成功返回起始虚拟地址,失败返回NULL
  void* malloc_page(enum pool_flags pf,uint32_t pg_cnt){

      //分配的页不能超过真实物理内存的一半（16MB，我们取整就是3840页）
      ASSERT(pg_cnt>0 && pg_cnt<3840);

      void* vaddr_start = vaddr_get(pf,pg_cnt);
      if(vaddr_start==NULL){
          return NULL;
      }

      uint32_t vaddr=(uint32_t)vaddr_start,cnt=pg_cnt;

      struct pool* mem_pool=pf & PF_KERNEL? &kernel_pool:&user_pool;

      while(cnt-- >0){
          void* page_phyaddr =palloc(mem_pool);
          if(page_phyaddr==NULL){
              return NULL;
          }
          page_table_add((void*)vaddr,page_phyaddr);
          vaddr+=PG_SIZE;
      }
      
      return vaddr_start;
  }


  //从内核物理内存池里获取pg_cnt页内存，成功则返回虚拟地址
  void* get_kernel_pages(uint32_t pg_cnt){

      void* vaddr=malloc_page(PF_KERNEL,pg_cnt);

      //将申请的空间请0
      if(vaddr!=NULL){
          memset(vaddr,0,pg_cnt*PG_SIZE);
      }
      return vaddr;
  }

kernel/memory.h:

  #ifndef __KERNEL_MEMORY_H__
  #define __KERNEL_MEMORY_H__

  #include "stdint.h"
  #include "bitmap.h"

  //虚拟地址池
  struct virtual_addr{
      struct bitmap vaddr_bitmap;
      uint32_t vaddr_start;
  };

  enum pool_flags{
      PF_KERNEL=1,
      PF_USER=3
  };

  #define PG_P_1      1
  #define PG_P_0      0
  #define PG_Rw_R     0
  #define PG_RW_W     2
  #define PG_US_S     0
  #define PG_US_U     4


  extern struct pool kernel_pool,user_pool;


  void mem_init(void);
  uint32_t* pte_ptr(uint32_t vaddr);
  uint32_t* pde_ptr(uint32_t vaddr);
  void* malloc_page(enum pool_flags pf,uint32_t pg_cnt);
  void* get_kernel_pages(uint32_t pg_cnt);

  #endif

调试：

最后可以通过info tab来查看新建立的映射是否正确,并且可以通过page 页虚拟地址来查看该线性页落到哪一个物理页上

makefile(更新过):

  BUILD_DIR = ./build
  ENTRY_POINT = 0xc0001500
  AS = nasm
  CC = gcc
  LD = ld
  LIB = -I lib/ -I lib/kernel/ -I lib/user/ -I kernel/ -I device/ 
  ASFLAGS = -f elf

  CFLAGS = -Wall -m32 -fno-stack-protector $(LIB) -c -fno-builtin -W -Wstrict-prototypes -Wmissing-prototypes
  # -fno-stack-protector 闭栈保护的编译选项，栈保护作用是禁止编译器在函数的栈帧中插入栈保护符号，以防止栈溢出攻击。
  # -fno-builtin 告诉编译器不要采用内部函数，因为我们以后会自定义与内部函数同名的函数
  # -Wall 启动所有警告
  # -W 启动常见警告
  # -Wstrict-prototypes  要求函数声明中必须有参数类型，否则警告
  # -Wmissing-prototypes 要求函数必须声明，否则警告

  LDFLAGS =  -m elf_i386 -Ttext $(ENTRY_POINT) -e main -Map $(BUILD_DIR)/kernel.map
  # -Map $(BUILD_DIR)/kernel.map  输出文件build/kernel.map。用于记录kernel符号地址

  OBJS = $(BUILD_DIR)/main.o $(BUILD_DIR)/init.o $(BUILD_DIR)/interrupt.o \
      $(BUILD_DIR)/timer.o $(BUILD_DIR)/kernel.o $(BUILD_DIR)/print.o \
      $(BUILD_DIR)/debug.o $(BUILD_DIR)/string.o $(BUILD_DIR)/memory.o \
      $(BUILD_DIR)/bitmap.o
  # 定义目标文件名集合，用于ld时依赖文件项


  ##############     c代码编译     			###############
  $(BUILD_DIR)/main.o: kernel/main.c lib/kernel/print.h \
          lib/stdint.h kernel/init.h lib/string.h kernel/memory.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/init.o: kernel/init.c kernel/init.h lib/kernel/print.h \
          lib/stdint.h kernel/interrupt.h device/timer.h kernel/memory.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/interrupt.o: kernel/interrupt.c kernel/interrupt.h \
          lib/stdint.h kernel/global.h lib/kernel/io.h lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/timer.o: device/timer.c device/timer.h lib/stdint.h\
          lib/kernel/io.h lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/debug.o: kernel/debug.c kernel/debug.h \
          lib/kernel/print.h lib/stdint.h kernel/interrupt.h
      $(CC) $(CFLAGS) $< -o $@

  $(BUILD_DIR)/string.o: lib/string.c lib/string.h \
          kernel/debug.h kernel/global.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/memory.o: kernel/memory.c kernel/memory.h \
          lib/stdint.h lib/kernel/bitmap.h kernel/debug.h lib/string.h \
          lib/kernel/print.h
      $(CC) $(CFLAGS) $< -o $@
      
  $(BUILD_DIR)/bitmap.o: lib/kernel/bitmap.c lib/kernel/bitmap.h \
          lib/string.h kernel/interrupt.h lib/kernel/print.h kernel/debug.h
      $(CC) $(CFLAGS) $< -o $@
  ##############     c代码编译     			###############


  ##############    汇编代码编译    ###############
  $(BUILD_DIR)/kernel.o: kernel/kernel.S
      $(AS) $(ASFLAGS) $< -o $@

  $(BUILD_DIR)/print.o: lib/kernel/print.S
      $(AS) $(ASFLAGS) $< -o $@
  ##############    汇编代码编译    ###############


  ##############    链接所有目标文件    #############
  $(BUILD_DIR)/kernel.bin: $(OBJS)
      $(LD) $(LDFLAGS) $^ -o $@
  ##############    链接所有目标文件    #############


  ################  伪目标 ###############################
  .PHONY : mk_dir hd clean build all

  mk_dir:
      if [ ! -d $(BUILD_DIR) ]; then mkdir $(BUILD_DIR); fi

  hd:
      dd if=$(BUILD_DIR)/kernel.bin \
          of=/home/sparkle2/bochs/hd60M.img \
          bs=512 count=200 seek=9 conv=notrunc

  clean:
      cd $(BUILD_DIR) && rm -f  ./*

  build: $(BUILD_DIR)/kernel.bin

  all: mk_dir build hd
  ################  伪目标 ###############################