近来做 Stanford CS140e 的一些进展和思考(6)

在上一篇文章之后,作者终于更新了测试的用例,我的程序终于可以成功跑过所有测试,也成功在树莓派跑起来。不过,我的代码中很多地方的错误处理比较偷懒,往往直接 panic ,显然并不友好。同时,我想到了使用 cargo-fuzz 来进行自动化测试,果然,使用这个很快就修复了不少我没想到的会出错的地方,比如乘法溢出,目录项没有正确结束等等。目前还发现一个 timeout 的问题,研究发现大概是文件的 cluster chain 中出现了环,导致一直读取文件而没有停止。要解决这个问题,我目前想到的是 Floyd 的判圈算法,但还没上实现。等过几天,新的 Assignment 3 出了以后,再继续更新。希望作者少点跳票,多点勤奋,哈哈哈哈哈 更新:下一篇在这里。

Read More

近来做 Stanford CS140e 的一些进展和思考(5)

在上一篇文章之后,作者多次延期跳票之后(again),终于放出了 Assignment 2 Phase 3: Saddle Up 。这次,我们要做的变成了把已经写好的(错漏百出)的 fat32 的驱动搬到树莓派里面去,然后实现一些基本的 shell 命令: ls cat cd 等等。作者首先更新了老版本的新的测试样例,放了一些映像然后提供了预期的结果,结果发现,这里的 fat32 有一些不同,主要的就是 bytes_per_sector 不是 512 了,意味着物理的扇区和逻辑扇区并不一致。同时, sectors_per_cluster 也不是 1 了,需要考虑多个扇区的情况。同时, read_cluster 传入的 offset 也可能不再是第一个 sector 中的,所以需要做一个处理。对于物理和逻辑扇区的问题,作者推荐的方案是,把 fat32 之外的扇区保持不变,把其内的扇区视为逻辑扇区。这样,其它代码都可以透明地工作,而不用到处更改,这就体现了封装的威力。接着,作者提供了一个写好了的 libsd 和一些导出的函数,使用这些函数即可。不过,在错误处理和 timeout 上也遇到了一些坑。后面,把东西搬到树莓派上运行,问题就出现了:读取了第一个扇区(即 MBR 所在的扇区)之后,直接就死掉了。想了半天都没找到方案,突然想起可以利用 panic! 对错误语句进行二分查找。查找了大概有七八个小时之后,终于发现,问题出现在读取一个 u32 类型的变量上。我起初怀疑是栈出了问题,所以放到堆上分配,然而还是不行。忽然想起以前遇到的对齐问题,在 AArch64 架构上,可能为了简化,读取的 u32 必须对齐到四个字节上。于是找了找 Rust 中的对齐方面的文档,找到了 #[repr(align=4)] 这种表示方法,代替了原来的 #[repr(packed)] ,并且把数据先拷贝到对齐后的栈上的对应数据结构,然后再读取对应的项。果然,这个问题就解决了。然后又发现我的盘中会出现 lfn 项并不是从后往前的情况,于是我又修改了一下相关的代码。现在,终于可以成功地 ls cat cd 。 不过还是要吐槽一下,作者的测试用的映像文件中,会出现 0xE5 表示这个项已经被删除的情况,但是似乎作者的代码并没有处理这个,所以在预期的输出中出现了一些明显不正确的结果,导致我的代码跑测试并不能通过。而且,作者的代码在一些情况下会把文件的后缀漏掉。作者后来更新了几次测试的文件,不过这个问题只解决了一部分,并没有完全解决。坐等作者继续放出新的测试文件吧。 更新:下一篇在这里。

Read More

近来做 Stanford CS140e 的一些进展和思考(4)

在上一篇文章之后,作者多次延期跳票之后,终于放出了 Assignment 2 Phase 2:32-bit Lipids ,这两天就把只读 FAT32 写完了(不过封装得并不好,许多地方利用了 pub(super) 把变量可以访问的范围控制到 vfat 中,然后直接读,只有少数需要特殊处理的进行了函数的封装)。首先当然是研究了半天 MBR 和 FAT32 的结构,拿了不同来源的 FAT 结构说明进行对比和验证,最后终于把格式搞清楚了,先实现了 MasterBootRecord ,这个其实很好实现,以前也有接触过 MBR ,本身也很简单。然后就是根据 MBR 找到第一个 FAT32 的分区,根据偏移找到分区的开头,开头的第一个扇区就是 EBPB 数据结构,里面保存了 FAT32 分区的各种信息。根据里面的信息,可以找到 FAT 表的位置和数量,还有数据部分的 Cluster 的位置和数量。接着,解析一下 FAT 表,实际上是一个与 Cluster 一一对应的链表结构,用特殊的数据代表链表的尾和空、坏扇区。利用这些,和 EBPB 中根目录所在的第一个 Cluster ,先在 VFat 里面实现了读取一个 Cluster 链的内容的函数,利用这个函数读取一个一个的目录项,解析目录项,把长文件名的项合并到一个之中,然后对应地丢到 Entry 对象中,目录则可以枚举子目录项,根据名字比较去找子目录或者子文件夹,文件则实现了 io::Read和 io::Seek 使得可以读取文件的内容。实现好了这些以后,就拿了 raspbian-strech-lite.img 作为硬盘映像,从文件里读取文件信息,成功地把 config.txt 读取出来。 其中还是遇到许多困难,如各种偏移的计算,如何处理跨 Cluster 和跨 Sector 的读写,等等,有不少的坑在其中,花了两天的空余时间才差不多完善了这个功能。还有就是利用 Rust 现有的功能完成 C 里面很轻易就可以实现的指针操作,也花了不少时间。 更新:下一篇在这里。

Read More

近来做 Stanford CS140e 的一些进展和思考(3)

由于 Assignment 2: File System 延期发布,所以中间那段时间转向 MIT 6.828 稍微研究了一下。前几天放出了新的任务,在上一篇文章之后,我又有了一些进展: 实现了从内存中读取 ATAGS(ARM Tags) 信息的代码,从而可以获得内存大小的信息,根据这个信息,实现了 bump 和 bin 两种内存分配器,并且把二者之一注册为全局内存分配器,利用上更新了的 std 就可以使用需要动态分配内存的相关工具了。利用这个,我实现了 shell 输入历史的回溯,把输入历史保存在一个动态增长的数组中,再特殊处理上下键,把当前的行替换为历史。 这个过程也不是没有踩坑。一开始代码放出来了,但是题目说明还没出,我就自己按照代码做了 ATAGS 和 bump 分配器,后来做完了,看到说明出了以后,发现理解还是有偏差,把代码更改了并修复了分配器的 BUG 。看到 bin 分配器的时候,我按照网上的 buddy memory allocation 实现了一个内存分配器,原理看起来简单实现起来还是有很多细节问题,后来按照新放出的单元测试,修修补补才写得差不多可用了。同时,原来的 bootloader 因为用了新的 std 而缺失了 alloc 不能编译,我就把 kernel 下的相关文件软连接过去,调了数次后把问题解决。此时, kernel 文件大小已经有 40K ,按照 115200 Baudrate 发送需要几秒才能传输过去,我就调到了 230400 Baudrate ,果然现在的传输速度就有所提升,可以接受了。等之后写了 EMMC(SD card) 的驱动和 FAT32 的文件系统后,就可以实现更多的 shell 的功能了。中间还遇到一个问题,就是如果给 kernel 开启了 bin 分配器,使用 exit 回到 bootloader 就无法传新的 kernel 上去了,结果发现是因为 bin 中用到的侵入式 LinkedList 实现覆盖了部分 bootloader 的代码,换回不能回收内存的 bump 分配器即可,反正目前远远还用不了那么多内存。

Read More

近来做 Stanford CS140e 的一些进展和思考(2)

在上一篇文章之后,我又有了一些进展:UART ,简易的shell ,修复了之前写的 xmodem 中的 BUG,一个可以从 UART 接收一个 kernel 写入到内存中再跳转过去的 bootloader 。 首先是 UART ,就是通过两个 GPIO pin 进行数据传输,首先在 memory mapped IO 上进行相应的初始化,然后包装了 io::Read 和 io::Write (这里实现一开始有 BUG,后来修复了),然后很快地完成了一个仅仅能 echo 的 kernel 。 然后实现了 CONSOLE ,一个对 MiniUart 和单例封装,就可以用 kprint!/kprintln! 宏来输出到 UART ,接着实现了一个 echo 的 shell ,读入一行输出一行。然后实现退格键和方向键,这里的难点在于要控制光标并且用读入的或者空格覆盖掉屏幕上已经显示而不应该显示的内容。接着,利用 skeleton 中的 Command 做了一个简单的 echo 命令。 接着,利用之前编写的 tty ,配合上新编写的 bootloader ,实现通过 UART 把新的 kernel 通过 XMODEM 协议发送到设备,写入 0x80000 启动地址并且调转到新加载的 kernel 中执行。 最后,又实现了 uptime (输出设备启动到现在的时间)和 exit (跳转回 bootloader ,可以上传新的 kernel )。并添加了 TUNA 作为 shell 启动时输出的 BANNER 。

Read More

近来做 Stanford CS140e 的一些进展和思考

最近,受各路安利,剁手买下了 这个淘宝商家的树莓派的套餐C ,还买了许多 LED 灯泡、杜邦线和电阻,开始按照 CS 140e 学习 Rust 并且用 Rust 编译写一个简易的操作系统。Assignment 0 的目标就是编写一个向 GPIO 16 连接的 LED 灯闪烁。首先当然就是愉快地按照教程下载 bootloader ,下载交叉编译工具链,顺带装一个 Raspbian 到机器上,随时可以当成一个低性能的 ARM/ARM64 (实际上,Raspbian 只用了armv7l,没有用 64bit)机器来用,以后如果配上 @scateu 团购的 Motorola Laptop Dock 的话就是一个几百块的笔记本了。把课程上的文件丢上去,可以看到绿色的活动指示灯闪烁,后面又把 CP2102 模块连上去,又能看到 Blink on, Blink off 的输出。然后按照要求,自己先码一段 C 语言,实现 blinky: #define GPIO_BASE (0x3F000000 + 0x200000) volatile unsigned *GPIO_FSEL1 = (volatile unsigned *)(GPIO_BASE + 0x04); volatile unsigned *GPIO_SET0 = (volatile unsigned *)(GPIO_BASE + 0x1C); volatile unsigned *GPIO_CLR0 = (volatile unsigned *)(GPIO_BASE + 0x28); static void spin_sleep_us(unsigned int us) { for (unsigned int i = 0; i < us * 6; i++) { asm volatile("nop"); } } static void spin_sleep_ms(unsigned int ms) { spin_sleep_us(ms * 1000); } int main(void) { // STEP 1: Set GPIO Pin 16 as output.

Read More

再次吐槽 VS 关于 scanf 和 scanf_s 的问题

继上次的吐槽后,今天再次遇到同学因为 scanf 在 VS 下的 deprecation error 感到十分迷茫,在知乎上求助又因为拍照的原因被说,我就在此再次吐槽一下 VS 这对初学者很不友善很不友善的两点。 一点就是上面提到的这个,另一点就是程序结束后任意键以退出这一功能要做得更加醒目一点 。前者由于大多数新手在学习 C/C++ 的时候都会跟着书上或者网上的代码敲一遍输入输出的代码,很容易就会撞到这个问题。后者则会让新手习惯性地以为程序闪退了,没有出结果,而不知道其实是程序执行结束后关闭而已。

Read More

我正在使用的两个 Emacs 的 Patch

我在本地对 emacs.rb 进行了修改: diff --git a/Formula/emacs.rb b/Formula/emacs.rb index d0138cd..de3c5ff 100644 --- a/Formula/emacs.rb +++ b/Formula/emacs.rb @@ -4,6 +4,14 @@ class Emacs < Formula url "https://ftp.gnu.org/gnu/emacs/emacs-25.3.tar.xz" sha256 "253ac5e7075e594549b83fd9ec116a9dc37294d415e2f21f8ee109829307c00b" + patch do + url "https://gist.githubusercontent.com/aatxe/260261daf70865fbf1749095de9172c5/raw/214b50c62450be1cbee9f11cecba846dd66c7d06/patch-multicolor-font.diff" + end + + patch do + url "https://debbugs.gnu.org/cgi/bugreport.cgi?filename=0001-Fix-child-frame-placement-issues-bug-29953.patch;bug=29953;att=1;msg=8" + end + bottle do sha256 "d5ce62eb55d64830264873a363a99f3de58c35c0bd1602cb7fd0bc37137b0c9d" => :high_sierra sha256 "4d7ff7f96c9812a9f58cd45796aef789a1b5d26c58e3e68ecf520fab34af524d" => :sierra 主要涉及到两个 Patch : 启用对 Multicolor font ,比如 Emoji 的支持。由于一些 ethic problems 暂时在 Emacs 中被禁用了,所以自己启用回来。 打上我前几天上报的 BUG #29953 的修复。已经在上游 Merge 到 emacs-26 分支中,这个修复会在下一个版本中。 有了第一个,就可以正常显示 Emoji (对不起,RMS);有了第二个,就解决了 pyim 和 lsp-ui-peek 用 child-frame 显示的一些问题了。

Read More

NAT64 初尝试

最近宿舍里有线网络的 IPv4 总是拿不到地址,只能连无线网,不禁对计算机系学生的可怕的设备数量有了深刻的认识。不过,作为一个有道德(误)的良好青年,还是不要给已经枯竭的 IPv4 地址填堵了,还是赶紧玩玩 IPv6 的网络吧。然后在 TUNA 群里受青年千人续本达 (@heroxbd) 的安利,本地搭建一下 NAT64+DNS64 的环境。不过考虑到宿舍还是拿不到有线的 IPv4 地址,我就先利用苹果先前在强制 iOS 的应用支持 NAT64 网络的同时,在 macOS 上为了方便开发者调试,提供的便捷的建立 NAT64 网络的能力。 首先在设置中按住 Option 键打开 Sharing , 点击 Internet Sharing ,勾上 Create NAT64 Network 然后把网络共享给设备。然后在手机上关掉 Wi-Fi 和 Cellular ,发现还能正常上网。此时可以打开 Wireshark 验证我们的成果了: 在手机上打开浏览器,浏览千度,得到如下的 Wireshark 截图: 这里,2001:2:0:aab1::1 是本机在这个子网中的地址,2001:2::aab1:cda2:5de:87f6:fd78 是我的 iOS 设备的地址,然后 iOS 向 macOS 发出了 DNS请求, macOS 发送 DNS 请求后得到 baidu.com 的 IPv4 地址之一为 111.13.101.208 : 上图中,我们可以看到, baidu.com 的 AAAA 记录是 2001:2:0:1baa::6f0d:65d0 ,这个就是 DNS64 转译的地址,前面为网关的 prefix ,后面就是对应的 IPv4 地址: 0x6f=111, 0x0d=13, 0x65=101, 0xd0=208 ,当客户端向这个地址发包的时候,网关发现前缀符合条件,把最后的这部分 IPv4 地址取出来,自己把包发送到真实的地址上去,再把返回来的包再转为 IPv6 的地址返还给客户端。可以验证,剩下的几个地址也符合这个转译规则。

Read More

有趣的 Java 日期格式化问题

今天在群里看到有人说, Java 的日期格式化有问题,如果用 YYYY-MM-dd ,今天的日期就会显示 2018-12-31 。我立马在本地用 Java REPL (aka Groovy) 跑了一下,果然如此: $ date = new Date() ===> Sun Dec 31 10:51:26 CST 2017 $ import java.text.SimpleDateFormat ===> java.text.SimpleDateFormat $ new SimpleDateFormat("YYYY-MM-dd").format(date) ===> 2018-12-31 解决方案是,把格式换为 yyyy-MM-dd ,确实就可以了。于是我就去研究了一下文档: Class SimpleDateFormat ,发现了问题: y 代表 year ,而 Y 代表 week year 。根据 week year ,因为今年最后的一个星期在明年的部分更多,于是这个星期被归在了明年,所以这一周属于 2018 ,这就可以解释之前的那个输出问题了。

Read More