Safe한 intrusive linked list

[travis1829]

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

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

Originally posted by @travis1829 in https://github.com/kaist-cp/rv6/issues/443#issuecomment-829131283

[travis1829]

조금 부연설명을 드리자면,

• "util::list::{List, Node}"는 intrusive linked list/node가 아니지만, rv6내에서는 intrusive list가 필요하지 않으므로 이 정도면 충분합니다.
• 그러나, 다른 OS들의 경우, kernel에서 intrusive linked list를 쓰는 경우가 매우 많으므로, 따로 safe한 intrusive linked list에 대해서도 구상을 해보면 좋을 것 같습니다.

  • 이를 위해, const generic을 사용하면 도움이 될 것 같습니다. 이러면, ListEntry가 여러개있는 Node의 경우, List가 이 Node의 몇번째 ListEntry를 사용하도록 하면 되는지를 지정해줄 수 있습니다. (구현 예: 59cfe85)

  • 다만, ownership을 어떻게 하면 좋을지에 대해서는 좀 더 고민을 해보아야 합니다. 예를 들면,

    • Node1 trait의 경우, 하나의 List에 들어가면 그 List가 read/write하는 형태,
    • Node2 trait의 경우, 여러개의 List에 들어갈 수 있지만 모두 read (or interior mutability)만 하는 형태,

    등 다양한 방법이 있을 것 같습니다.