safe한 lifetime-less linked list

[travis1829]

intrusive linked list는 특이하게도 list가 node를 own하지 않으므로, node가 언제 mutate/drop될지를 알 수 없습니다.
그러므로, intrusive linked list를 safe하게 쓰기 위해서는 dynamic check이 필요할 것으로 보이며,
특히, StaticRefCell이 도움이 될 것으로 보입니다.

dynamic check을 최소한으로만 사용하는 safe한 linked list를 구상해보았습니다. #443 (comment)

다만, 이 부분은 #450 이 해결된 후 해결하는게 좋을 것 같습니다.

[travis1829]

• https://gitlab.mpi-sws.org/FP/ghostcell/-/blob/master/ghostcell/src/dlist_arena.rs 에서 한 것과 비슷하게, GhostCell이나 Branded를 사용하면 runtime check 없이 safe한 lifetime-less linked list를 구현할 수 있을 것 같습니다.
  • 다만, 위 예시는 사실상 heap-allocating linked list이고, 따로 List라는 type이 없으므로, 저희가 원하는 List와는 조금 다릅니다.
• 구현 예시
  • List<T> <-> ListHandle<'id, T>, Node<T> <-> NodeHandle<'id, T>
  • Node<T>는 T를 access할 수 없습니다.
  • NodeHandle<'id, T>는 T를 access할 수 있지만, &ListHandle<'id, T>/&mut ListHandle<'id, T>가 필요합니다.
  • Node가 drop될 때는, 자동으로 주변 Node와 unlink됩니다.

[travis1829]

Branded를 사용하지 않고 다른 방법을 이용하여 safe한 linked list를 구현해보았습니다. (PR #495)

핵심은 다음과 같습니다.

• NodeRef, NodeMut는 Node가 List 안에 있는 동안에만 존재합니다.
• NodeRef를 얻으려면, 항상 1) NodeRef와 2) ListRef가 둘다 필요합니다.
  (즉, List와 Node를 둘다 immutable borrow해야 합니다.)
• NodeMut를 얻으려면, 항상 1) NodeMut와 2) ListMut가 둘다 필요합니다.
  (즉, List와 Node를 둘다 mutable borrow해야 합니다.)
• 하나의 List에 대해, NodeMut는 항상 단 한개만 존재합니다.
• Node가 List안에 있는 상태에서 drop되면 panic합니다. (유일한 runtime cost)

이렇게 하면, lifetime 제한이나 functionality 제한 등을 걸지 않더라도 linked list를 safe하게 구현할 수 있습니다.

Comparison

tock의 linked list와 GhostCell의 linked list는 다음과 같은 단점이 있습니다.

• tock의 linked list의 단점
  • tock의 linked list는 List가 drop하기 전에는 Node를 mutate하거나 drop할 수 없습니다. 이는, Node가 List로부터 remove된 이후에도 마찬가지입니다. 이와 달리, PR [Closes #443] Safe list that does not own its nodes #495 의 List는 이러한 lifetime 제약을 걸지 않습니다.
• GhostCell의 linked list의 단점
  • Node는 List(또는 GhostToken)가 먼저 만들어진 후에만 만들 수 있으며, Node는 하나의 List와 영원히 연결되어 있습니다.
    • Node는 정해진 List말고 다른 List로 insert될 수 없습니다.
    • &mut Node를 얻으려면, &mut List를 얻어야만 합니다. (Node가 List에서 이미 remove되었더라도 필요함)
  • List가 drop하기 전에 모든 Node들이 drop되어야 합니다. (tock의 경우와 반대)

PR #495 의 List는 위와 같은 단점이 없습니다. 그 대신, 다음과 같은 단점이 있습니다.

• runtime cost: Node가 List안에 있는 상태에서 drop되면 panic합니다.
  • 다만, 매우 작은 runtime cost라고 생각합니다.
• List의 API는 모두 safe하지만, Node의 API의 경우 Node::{as_ref_unchecked, as_mut_unchecked}는 unsafe합니다.
  • 다만, 일반적으로 List를 access하고 싶을때는 List의 API를 사용하므로, 이 부분은 크게 문제가 되지 않을 것 같습니다.
  • 특히, 이 부분은 Branded를 사용하면 user가 쉽게 safety를 justify할 수 있습니다.

[travis1829]

추가적으로, 이 List는 singly linked list도 구현할 수 있을 것 같습니다.

• 현재, PR Use List for Kmem #468 에서 Kmem이 doubly linked list를 사용하도록 변경한 것으로 알고 있는데, 이러면 singly linked list를 사용하도록 변경할 수 있을 것 같습니다.

[travis1829]

다만, 이 List는 intrusive linked list가 아닙니다.
지금의 rv6에서는 이런 List면 충분하지만, 추후 Node가 여러 List안에 insert될 수 있는 safe한 Node/List를 만들면 좋을 것 같습니다.

• 이때, const generic을 이용해서 List가 Node의 몇번째 ListEntry를 사용하는지를 표현하면 좋을 것 같습니다. (ex: 59cfe85)
• 이러한 list의 ownership을 어떻게 해야할지를 잘 고민해봐야 합니다.