简介 链表（Linked List）是一种常见的线性数据结构，与数组相比，它具有不同的存储方式和操作特性。链表通过节点（Node）来存储数据，每个节点包含数据域和指针域，指针域指向下一个节点，从而形成一条节点链。 链表类型 单向链表（Singly Linked List）：每个节点只有一个指针，指向下一个节点。 双向链表（Doubly Linked List）：每个节点有两个指针，分别指向前一个节点和后一个节点。 循环链表（Circular Linked List）：链表的最后一个节点指向第一个节点，形成一个环。 链表操作 插入（Insertion）：在链表的指定位置插入一个新节点。 删除（Deletion）：删除链表中的指定节点。 查找（Search）：在链表中查找指定值的节点。 遍历（Traversal）：从头到尾访问链表中的每个节点。 Rust实现 完整代码可以看这里 ...
简介 顺序表（Sequential List）是一种基于数组实现的数据结构，用于存储一组具有顺序关系的元素。顺序表的特点是将元素按照一定的顺序存储在连续的内存空间中，通常使用数组来实现。顺序表支持随机访问，即可以通过下标直接访问任意位置的元素。 顺序表的主要特点： 连续存储：顺序表中的元素存储在连续的内存空间中，这使得访问任意元素的时间复杂度为 O(1)。 固定大小（静态顺序表）：在静态顺序表中，存储空间的大小是固定的，通常通过静态数组实现。 动态扩展（动态顺序表）：在动态顺序表中，存储空间可以根据需要进行扩展，通常通过动态数组或链表实现。 随机访问：由于元素是连续存储的，可以通过下标直接访问任意位置的元素，时间复杂度为 O(1)。 插入和删除效率较低：在顺序表中插入或删除元素时，可能需要移动其他元素，导致时间复杂度为 O(n)。 顺序表类型 静态顺序表：静态顺序表使用静态数组来存储数据，数组的大小在编译时确定，无法动态扩展。 动态顺序表：动态顺序表使用动态数组或链表来存储数据，可以根据需要动态扩展存储空间。 顺序表的操作 初始化：创建一个空的顺序表。 插入：在指定位置插入一个元素。 删除：删除指定位置的元素。 查找：查找指定元素的位置。 修改：修改指定位置的元素。 使用Rust实现顺序表（SeqList） 定义顺序表结构 首先，定义一个名为 SeqList 的结构体，它包含两个字段： data 是一个动态数组 Vec<T>，用于存储实际的数据元素； length 是一个 usize 类型的字段，用于记录当前顺序表中元素的数量。 ...
实现完整的文件系统 完整文件系统只需要实现下面的几个函数: 打开文件 fs_open: 遍历文件表, 查找与 pathname 匹配的文件. 如果找到匹配的文件, 初始化文件的打开偏移量为0, 并返回文件描述符. 如果未找到匹配的文件, 返回错误. 读取文件 fs_read: 检查文件描述符是否有效. 根据文件的读取函数指针调用相应的读取函数. 更新文件的打开偏移量. 写入文件 fs_write: ...
实现异常响应机制 熟悉的读手册环节, 根据NEMU的要求, 我们需要添加三个CSR寄存器: // src/isa/riscv32/include/isa-def.h typedef struct { vaddr_t mepc; word_t mcause; word_t mstatus; word_t mtvec; } CSR; typedef struct { word_t gpr[MUXDEF(CONFIG_RVE, 16, 32)]; vaddr_t pc; CSR csr; // csr uint8_t mode; // riscv特权级状态 } MUXDEF(CONFIG_RV64, riscv64_CPU_state, riscv32_CPU_state); 根据官方手册, 每当程序调用ecall时, cpu会将当前pc保存在mepc中, 异常原因写入mcause, 并修改mstatus, 最后跳转到mtvec保存的地址. ...
输入输出 实现IOE: 时钟 按照文档完成am/src/platform/nemu/ioe/timer.c即可, 代码本身很简单, 直接贴出如下: static uint64_t boot_time = 0; void __am_timer_init() { uint32_t high = inl(RTC_ADDR+4); uint32_t low = inl(RTC_ADDR); boot_time = (uint64_t)low + (((uint64_t)high) << 32); } void __am_timer_uptime(AM_TIMER_UPTIME_T *uptime) { uint32_t high = inl(RTC_ADDR+4); uint32_t low = inl(RTC_ADDR); uptime->us = (uint64_t)low + (((uint64_t)high) << 32) - boot_time; } int is_leap_year(int year) { return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0); } int days_in_month(int year, int month) { static const int days[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }; if (month == 2 && is_leap_year(year)) { return 29; } return days[month - 1]; } void __am_timer_rtc(AM_TIMER_RTC_T *rtc) { uint32_t high = inl(RTC_ADDR+4); uint32_t low = inl(RTC_ADDR); uint64_t total_second = ((uint64_t)low + (((uint64_t)high) << 32)) / 1000000; total_second += 8 * 3600; // Asia/Shanghai UTC+8 uint32_t days = total_second / 86400; uint32_t second_in_day = total_second % 86400; rtc->year = 1970; while(true) { int days_in_year = is_leap_year(rtc->year) ? 366 : 365; if (days >= days_in_year) { days -= days_in_year; rtc->year++; } else { break; } } rtc->month = 1; while (1) { int dim = days_in_month(rtc->year, rtc->month); if (days >= dim) { days -= dim; rtc->month++; } else { break; } } rtc->day = days + 1; rtc->hour = second_in_day / 3600; second_in_day %= 3600; rtc->minute = second_in_day / 60; rtc->second = second_in_day % 60; } 若想查看实时时间, 可修改nemu/src/utils/timer.c中的get_time函数如下: ...
Trace实现 itrace 关于反编译的部分, NEMU已经实现了. 我们需要做的只是使用一个合适的数据结构来保存这些信息. 文档中推荐使用环形缓冲区. 作者最初选择仅保存pc, 在需要打印信息时直接通过pc获取指令与反汇编的信息. 但考虑到可能存在自修改程序, 最终决定将指令信息也一并保存. struct ItraceNode { paddr_t pc; uint32_t inst; struct ItraceNode *next; }; struct ItraceNode iringbuf[CONFIG_ITRACE_BSIZE]; struct ItraceNode *iringbufNow; // 初始化环形缓冲 void init_iringbuf(void) { iringbufNow = &iringbuf[CONFIG_ITRACE_BSIZE - 1]; for (int i = 0; i < CONFIG_ITRACE_BSIZE; i++) { iringbuf[i].next = &iringbuf[(i + 1) % CONFIG_ITRACE_BSIZE]; iringbuf[i].inst = 0; iringbuf[i].pc = 0; } } // 存入缓冲, 需要放到正确的位置 void push_inst(paddr_t pc, uint32_t inst) { iringbufNow->next->inst = inst; iringbufNow->next->pc = pc; iringbufNow = iringbufNow->next; } 打印部分需要先反汇编后再输出. 为了美观, 代码写得稍微复杂了一些, 如果嫌麻烦可以直接顺序打印. ...
NEMU运行逻辑 这里简单梳理一下NEMU的生命周期内都干了些什么. 从main函数看, 基本可以分成三个阶段: // 简化版本 int main(int argc, char *argv[]) { init_monitor(argc, argv); // 初始化模拟器 engine_start(); // 开始运行 return is_exit_status_bad(); // 结束运行, 判断结果 } 初始化 实际上进入init_monitor函数就能很清晰的看到整个初始化过程都做了些什么事. 先由parse_args处理输入参数, 并保存到对应变量, 后续有个任务也需要看懂这个函数才能完成对应操作. ...
前言 这是一篇关于ICS-PA的二周目学习记录. 作者在完成YSYX项目后编写此文, 因此内容可能存在遗漏或跳阶段的情况. 如有好的想法或疑问, 欢迎通过邮件与我交流. 目前YSYX项目使用的是riscv32e架构. 经过考虑, 本文及后续分享将基于riscv32e进行. 但在与riscv64和riscv32有特殊区别时, 会特别说明. ...
前言 来自2024年的提示: 如果条件允许, 有多余的设备, 实机安装反而是最省事的选择. WSL在部分情况（网络）下还是要折腾一下. 但是确实算是个不错的选择. 为什么选择WSL 由于我的部分开发环境必须使用Linux环境, 我必须在实际安装/虚拟机/WSL之中选择一个, 最后我选择了WSL. 主要原因如下: 占用空间小 消耗资源少 可以与Windows共存 WSL GUI可应付绝大部分需要图形界面的情况 常用软件都可以使用可以一边打游戏一边听音乐写代码 安装并启用WSL 事实上微软的官方教程已经很详细了:官方链接. ...