linked_list 问题追踪：Arceos vs Rust for Linux

[zjp-CN]

• https://github.com/arceos-org/linked_list_r4l 基于 Rust for Linux 的 linked_list.rs
• 该 R4L 的代码处于 rust 分支，两年前就停止开发了；目前 R4L 的开发处于 rust-next 分支 (主线代码 | 最新 API 文档)
• 需要对比 linked_list_r4l 和当时的 R4L 的代码差异
• 需要对比 R4L 当时和现在的 linked_list 实现差异
  • 一个 2022 年 Cursor API unsound 的旧讨论：Linked List CursorMut unsoundness Rust-for-Linux/linux#944
  • 主线代码只将 Arc<T> 作为链表节点的数据指针，并对 Cursor、Iter 等结构提供 &T 而 不再暴露 &mut T
• 需要考虑能否检测当前 R4L 的 linked_list 代码（或者 R4L 对 Miri 的使用情况）
  • R4L 2021 年的时候，搜集过几个 Miri 的问题： Miri wanted features & bugfixes Rust-for-Linux/linux#397
  • 但 R4L 没有将 Miri 应用起来，在 zulipchat 上也几乎没有讨论

something like &mut foo as *mut T as *const T as *mut T is entirely harmless. What is relevant is the initial cast, when a reference is turned to a raw pointer.

src: rust-lang/unsafe-code-guidelines#257

[zjp-CN]

linked_list_r4l 还影响了 axsched 库，因此调整了 API 之后需要更新 axsched。

fix-tree-borrows 只修复针对 tree borrows 检测到的 UB，在 stack borrows 上，依然存在 UB：

linked_list_r4l $ cargo miri test --lib
running 5 tests
test linked_list::tests::test_push_back ... ok
test raw_list::tests::test_one_insert_after ... error: Undefined Behavior: trying to retag from <165717> for SharedReadWrite permission at all
oc50876[0x0], but that tag does not exist in the borrow stack for this location
   --> src/raw_list.rs:358:23
    |
358 |         Some(unsafe { &*cur.as_ptr() })
    |                       ^^^^^^^^^^^^^^ this error occurs as part of retag at alloc50876[0x0..0x18]
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are st
ill experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <165717> was created by a SharedReadWrite retag at offsets [0x0..0x11]
   --> src/raw_list.rs:149:58
    |
149 |         self.insert_after_priv(existing, new_entry, Some(NonNull::from(new)));
    |                                                          ^^^^^^^^^^^^^^^^^^
help: <165717> was later invalidated at offsets [0x0..0x18] by a Unique retag
   --> src/raw_list.rs:594:29
    |
594 |             v.insert(i + 1, extra);
    |                             ^^^^^
    = note: BACKTRACE (of the first span) on thread `raw_list::tests`:
    = note: inside `raw_list::Cursor::<'_, raw_list::tests::Example>::current` at src/raw_list.rs:358:23: 358:37
note: inside `<raw_list::Iterator<'_, raw_list::tests::Example> as std::iter::Iterator>::next`
   --> src/raw_list.rs:453:19
    |
453 |         let ret = self.cursor_front.current()?;
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: inside `<std::iter::Enumerate<raw_list::Iterator<'_, raw_list::tests::Example>> as std::iter::Iterator>::next` at /home/gh-zjp-CN/
.rustup/toolchains/nightly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/iter/adapters/enumerate.rs:80:17: 80:33
note: inside `raw_list::tests::test_one_insert_after`
   --> src/raw_list.rs:588:9
    |
588 | /         test_each_element(1, 10, |v, list, i, extra| {
...   |
594 | |             v.insert(i + 1, extra);
595 | |         });
    | |__________^
note: inside closure
   --> src/raw_list.rs:587:31
    |
586 |     #[test]
    |     ------- in this attribute macro expansion
587 |     fn test_one_insert_after() {
    |                               ^

axsched $ cargo miri test -- tests::fifo::bench_remove tests::fifo::test_sched
running 2 tests
test tests::fifo::bench_remove ... error: Undefined Behavior: trying to retag from <3527920> for SharedReadWrite permission at alloc1195775[0x
0], but that tag does not exist in the borrow stack for this location
   --> /home/gh-zjp-CN/.rustup/toolchains/nightly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:444:18
    |
444 |         unsafe { &*self.as_ptr().cast_const() }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ this error occurs as part of retag at alloc1195775[0x0..0x30]
    |
    = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are st
ill experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <3527920> was created by a SharedReadOnly retag at offsets [0x29..0x71]
   --> src/fifo.rs:50:18
    |
 50 |         unsafe { self.ready_queue.remove(task) }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: BACKTRACE (of the first span) on thread `tests::fifo::be`:
    = note: inside `std::ptr::NonNull::<alloc::sync::ArcInner<fifo::FifoTask<usize>>>::as_ref::<'_>` at /home/gh-zjp-CN/.rustup/toolchains/nig
htly-aarch64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/non_null.rs:444:18: 444:46
    = note: inside `std::sync::Arc::<fifo::FifoTask<usize>>::inner` at /home/gh-zjp-CN/.rustup/toolchains/nightly-aarch64-unknown-linux-gnu/li
b/rustlib/src/rust/library/alloc/src/sync.rs:1917:18: 1917:35
    = note: inside `<std::sync::Arc<fifo::FifoTask<usize>> as std::ops::Deref>::deref` at /home/gh-zjp-CN/.rustup/toolchains/nightly-aarch64-u
nknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/sync.rs:2232:10: 2232:22
note: inside `tests::fifo::bench_remove`
   --> src/tests.rs:69:33
    |
 69 |                     assert_eq!(*t.inner(), i);
    |                                 ^^^^^^^^^
...
 82 | def_test_sched!(fifo, FifoScheduler::<usize>, FifoTask::<usize>);
    | ---------------------------------------------------------------- in this macro invocation
note: inside closure
   --> src/tests.rs:55:30
    |
 55 |             fn bench_remove() {
    |                              ^
...
 82 | def_test_sched!(fifo, FifoScheduler::<usize>, FifoTask::<usize>);
    | ---------------------------------------------------------------- in this macro invocation
    = note: this error originates in the macro `def_test_sched` (in Nightly builds, run with -Z macro-backtrace for more info)

[zjp-CN]

提交 linked_list_r4l 修复：

• Fix: Aliasing UB Reported by Miri arceos-org/linked_list_r4l#3
• Unsoundness of exposing &mut G::EntryType arceos-org/linked_list_r4l#4