WaitChannel design

[efenniht]

WaitChannel 에 대해서 고민해봤는데, 이런 형태의 디자인이 과연 올바른 지 궁금합니다. @jeehoonkang

• 원래 xv6 는 애초에 wait channel 이라는 type 이 없고 서로 다른 변수에 대한 주소를 wait channel identifier로 사용합니다. Make wait channel non-zero-sized #236 에 의해 WaitChannel 을 들고 있는 타입은 크기가 커집니다. 그렇다고 WaitChannel<T> 같은 타입은 더 이상한 것 같습니다.
• WaitChannel 은 주소가 wait 대상의 identifier 가 되므로 move 되면 스레드를 깨워도 일어나지 않거나 이상한 스레드가 깨는 등 의도되지 않은 일이 일어날 수 있습니다. 따라서 올바른 API는 sleep(self: Pin<&mut Self>, ...) 이 되어야 합니다. 다만 이것은 safety invariant 는 아니므로 주석만 쓰고 넘길 수도 있습니다.
• Redox 의 구현은 해당 채널을 대기하고 있는 스레드를 queue 에 넣어서 WaitChannel 의 멤버로 들고 있습니다. 이러면 channel 이 move 되어도 문제가 없습니다.

어떻게 수정하는 것이 옳을까요?

1. 현상 유지
2. Pin 넣고 타입 대공사
3. Redox 처럼 수정하기

Originally posted by @efenniht in #236 (comment)

[jeehoonkang]

저는 2가 어떨까 합니다. 되도록 xv6의 의도를 따라가면서도 safe api를 지원하면 좋겠어서 그렇습니다. 1은 unsafe, 3은 xv6의 의도와 다름.

[coolofficials]

혹시 급한(쓰시는 논문에 중요하게 다룰 예정인) refactoring point가 아니라면 시험 이후에 제가 좀 봐도 괜찮을까요? @efenniht

이유는

1. Proc.rs와의 관련성
2. Pin API의 사용
   입니다.

[efenniht]

혹시 급한(쓰시는 논문에 중요하게 다룰 예정인) refactoring point가 아니라면 시험 이후에 제가 좀 봐도 괜찮을까요? @efenniht

이유는

1. Proc.rs와의 관련성

2. Pin API의 사용
   입니다.

네, 부탁드립니다 🙏

[coolofficials]

현재는 WaitChannel의 move가 발생하는 부분이 존재하지 않기 때문에 이 이슈는 후순위로 미루고 proc.rs 의 다른 refactoring point를 먼저 진행하도록 하겠습니다. (현재 발생하지 않은 문제에 대한 예방책입니다.)

[jeehoonkang]

@travis1829 혹시 진행중인 PR이 있나요?

[travis1829]

@travis1829 혹시 진행중인 PR이 있나요?

아직 PR은 없습니다!

[travis1829]

WaitChannel을 어떻게 바꾸면 좋을지에 대해 의문사항이 좀 있어서 comment을 답니다.

• Pin API가 의미가 있으려면, WaitChannel API (ex: WaitChannel::new())가 WaitChannel은 노출시키지 않고 Pin<&WaitChannel>만을 노출시켜야 되는 것 같습니다. 다만, 이러면 WaitChannel 자체는 어디에 저장을 시키느냐가 문제인 것 같습니다.
  • 현재는 WaitChannel을 Pipe나 Proc 등 struct의 field로 저장하므로 WaitChannel이 노출되고, WaitChannel 또는 그 struct 자체가 move되지 않도록 알아서 조심해야 됩니다.
  • 일반적으로는 WaitChannel자체는 heap에 저장하고 WaitChannel::new()는 Pin<&WaitChannel>을 리턴하게 하면 되겠지만 kernel 내부에서는 heap의 개념이 없으니, WaitChannel 자체는 그냥 static한 array에 저장을 하면 어떨지 제안드립니다. (다만, 이러면 xv6랑은 달라지기도 하고, 각각의 WaitChannel을 어떤 index에 저장할지를 macro등으로 미리 결정해야합니다.)
• 훨씬 더 간단한 방법으로는, 그냥 macro로 각각의 WaitChannel에 usize id를 assign해주면 나중에 move되든 어떻게 되든 상관이 없어지게 됩니다. 다만, 이것도 xv6랑 달라지게 되는 건 마찬가지입니다.

참고: 혹시, 제가 Pin API에 대해 잘못 이해하고 있는게 있다면 알려주세요.

[jeehoonkang]

WaitChannel과 이를 포함하는 struct (Pipe, Proc) 모두 안움직이도록 강제할 수도 있을까요? 제가 Pin에 대해 까먹었는데 가령 Pin<Proc> 같은 타입을 쓰면 해결되는지 궁금합니다.

[travis1829]

예, API가 Pipe나 Proc자체는 노출시키지 않고 (그러면서 어딘가에는 저장을 하고), 그 대신 Pin<&Pipe>나 Pin<&Proc>만 노출시키도록 변경하면 모두 안 움직이게 강제할 수 있습니다! 다만, 이러면 타입 대공사의 규모가 훨씬 커질것 같습니다.

EDIT: 다만, 애초에 Pipe나 Proc이 WaitChannel을 소유하지 않고 Pin<&WaitChannel>만을 가지고 있다면, Proc나 Pipe이 move하게 되더라도 WaitChannel은 문제없이 사용 가능합니다.

[jeehoonkang]

• (편의상 WC라고 하게씁니다) WC를 만들고 이동하는 것까지 허용하되, 누군가가 거기서 wait하고 있으면 더이상 이동할 수 없도록 API를 디자인할 수도있지 않을가요?
• 저는 일단 xv6의 디자인을 좀 따라가보는게 어떨까 합니다. 나중에 가면 waitlist를 구현하기도 할텐데 (redox처럼) waitlist가 없는 구현도 필요하긴 할것 같아서요
• 구체적으로 어떻게 API를 디자인해야할지 고민이 필요한데, 제가 어렴풋이 기억하기로 이문제의 해답중에 Pin이 꼭 있어야 할겁니다. 근데 제가 Pin에 대해 좀 까먹어서 그런데 혹시 API 문서 보시고 간단히 요약해서 정리해주실 수 있으시면 감사드리겠습니다.

[travis1829]

누군가가 거기서 wait하고 있으면 더이상 이동할 수 없도록 API를 디자인할 수도있지 않을가요?

• 일단, Pin의 기본적인 contract은 한번 Pin한건 계속 Pin하는게 원칙인 것 같습니다. (https://doc.rust-lang.org/std/pin/struct.Pin.html#safety)

  A value, once pinned, must remain pinned forever

• 다만, Pipe::read_waitChannel같은 걸 enum으로 바꿔서 아무도 wait하지 않을 때는 WaitChannel을 저장하고, 누군가가 wait할때는 Pin<&WaitChannel>을 저장하도록 할 수는 있을 것 같습니다. 그러나, 이렇게 하더라도 Pin<&WaitChannel>로 바뀌기 이전에 얻은 reference들이 남아있을 수 있을 것 같습니다.

---

저는 일단 xv6의 디자인을 좀 따라가보는게 어떨까 합니다.

• 그러면 WaitChannel마다 usize id를 부여하는 건 지양해보도록 하겠습니다.

---

API 문서 보시고 간단히 요약해서 정리해주실 수 있으시면 감사드리겠습니다.

(아직 작성중...)

• This is a wrapper around a kind of pointer which makes that pointer "pin" its value in place, preventing the value referenced by that pointer from being moved
• 일단, Pin<&mut T>는 &mut T 같은 Pointer을 wrap하는 것 뿐이며, get_ref()같은걸로 &T를 얻을 수도 있습니다. 다만, &mut T를 얻게된다면 mem::swap(&mut test1, &mut test2)같은 방식으로 move이 가능하기 때문에, &mut T는 safe한 방법으로는 획득할 수 없도록 제한합니다. (즉, safe한 방법으로는 move이 불가능합니다)

[travis1829]

이 issue를 해결하기 위해서는 크게 3가지 방법이 있는 것 같습니다.

1. Pin을 이용해서 WaitChannel을 직접 own하는 struct, 또는 그 struct을 own하고 있는 struct이 move되지 않도록 강제해아합니다. 그러나, 이렇게 되면 굉장히 많은 struct가 포함되게 됩니다. 이러한 struct을 access할때는 항상 Pin<&mut Struct>의 형태로만 access하도록 모두 바꾸거나, 아니면 지금처럼 이러한 struct가 move되지 않도록 알아서 조심해야됩니다.
2. struct들이 WaitChannel을 직접 own하는 대신, Pin<&mut WaitChannel>만을 가지게 하면 그 struct들이 move되더라도 상관이 없어집니다. 다만, 이러면 WaitChannel은 static한 어딘가에 따로 저장해야됩니다. 또, lifetime을 지정해줘야 하는 곳이 많이 생길것으로 예상됩니다.
3. 제 3의 방법으로는, 현재의 redox처럼 waitlist을 사용하거나, 아니면 WaitChannel::_padding을 없애고 WaitChannel::id같은걸 넣어서 사용하는 방법이 있습니다.

• 제 개인적인 생각으로는, 어차피 나중에 waitlist을 구현할 예정이면 지금 미리 구현하는 것도 괜찮을 것 같습니다. 1번 방법은 WaitChannel하나만을 위해서 너무 많은 부분을 수정해야하며, 2번 방법은 xv6에는 없는 static array를 추가해야되고 const fn에서는 쓰기 힘들어진다는 단점이 있습니다.

혹시 이 부분에 대해 어떻게 생각하시나요? @jeehoonkang @efenniht

[jeehoonkang]

저는 장기적으로 1번이 맞아보이긴 합니다. 지금 object가 옮기면 안된다는 invariant를 가정하는 부분이 상당히 많은데 (waitchannel이 아니더라도) 따라서 Kernel도 pin이 되어야 할 것 같아서요. 혹시 얼마나 코드를 많이 변경해야하는지 가늠해주실 수 있을까요?

(너무 비용이 크면 3도 좋은 선택이라고 생각합니다.)

[efenniht]

교수님께서 말씀하신 대로 이미 Pin 이 필요한 부분이 많습니다. 당장 생각나는 것만 해도:

• intrusive linked list 를 사용하는 코드 (MruArena)
• virtqueue 에 접근하는 Disk
• parent process 의 포인터를 저장하는 parent field

이 정도인데 이런 것들을 지원하려면 Kernel 이 pin 이 되어야 합니다.

[travis1829]

그러면 1번을 이용해보도록 하겠습니다!

혹시 얼마나 코드를 많이 변경해야하는지 가늠해주실 수 있을까요?

일단, 제가 간단히 알아본걸 미리 말씀드리자면,

• WaitChannel이 저장되는 곳:
  • BufEntry::vdisk_request_waitchannel
  • Pipe::read_waitchannel, Pipe::write_waitchannel
  • ProcInfo::child_waitchannel
  • Sleepablelock::waitchannel
• Sleepablelock이 저장되는 곳:
  • FileSystem::disk
  • Kernel::console, Kernel::ticks
  • RawSleeplock::locked
  • Uart::tx_lock
• 이외, Sleeplock, Proc 등이 있습니다! (다만, complete한 list는 아닐수도 있습니다!)

[travis1829]

API 문서 보시고 간단히 요약해서 정리해주실 수 있으시면 감사드리겠습니다.
#356 (comment)

• Pin관련 issue([Stabilization] Pin APIs rust-lang/rust#55766 (comment)) 에도 나와있듯이, Pin != !Move 입니다. 즉, Pin은 그저 또다른 pointer일 뿐이며, Pin을 이용한다고 해서 특정 struct을 !Move로 표시하는게 아니고 그저 Pin만을 가지고서는 move를 할 수 없는 것 뿐입니다. 예로, 다음과 같은 코드는 compile error가 발생하지 않습니다. (즉, move가 가능합니다.)

fn move_pinned_ref<T>(mut a: T, mut b: T) {
    unsafe {
        let p: Pin<&mut T> = Pin::new_unchecked(&mut a);
        // This should mean the pointee `a` can never move again.
    }
    mem::swap(&mut a, &mut b);
    // The address of `a` changed to `b`'s stack slot, so `a` got moved even
    // though we have previously pinned it! We have violated the pinning API contract.
}

• 만약 Pin<&mut T>밖에 없다면 (즉, &mut T는 가지고 있지 않고 얻을 수도 없다면), T를 move할 방법이 없으므로 move를 근본적으로 방지할 수 있습니다.
  • 다만, 이러기 위해서는 T를 stack이나 다른 struct의 field이 아니라, heap에 저장해야 합니다. 그렇지 않으면 safe code에서도 &mut T를 얻을 수 있기에, 프로그래머가 직접 조심해야 됩니다. (macro를 쓰면 조금 더 편해지긴 하지만, 그래도 마찬가지입니다.) 그리고 Pin된 상태를 계속 유지해야 합니다.
  • rv6에서는 struct을 kernel().alloc()으로 page의 주소값을 받아서 거기에 struct을 저장하는 경우에는, move를 근본적으로 방지할 수 있습니다. (즉, heap에 저장하는 경우와 유사한 예입니다.) 다만, 이런 struct는 Pipe하나 뿐입니다.
  • rv6의 나머지 struct들은 모두 또다른 더 큰 struct의 field로 저장되기 때문에, 그 (더 큰) struct 내부에서는 자유롭게 &mut T를 얻을 수 있고, 내부 struct를 move할 수 있으며, 조심하지 않으면 그 &mut T를 외부로 내보낼 수도 있습니다.

[jeehoonkang]

"더 큰 struct"도 pin으로 접근하면 안되나요?

[travis1829]

"더 큰 struct"도 pin으로 접근하면 안되나요?

장기적으로는 그런식으로 해야 합니다. 즉, struct가 move되서는 안되는 field를 직접적으로, 또는 다른 field의 하위 field로 간접적으로 가지고 있으면, 항상 pin으로 접근해야 합니다.

[travis1829]

• 교수님과 홍재민님과 의논한 결과, 어떤 Proc이 WaitChannel에 대해서 sleep()하고 있다면 WaitChannel에 대한 immutable reference를 가지고 있으므로, safe한 방법으로는 WaitChannel이 move될 수 없는 것으로 보입니다.

• WaitChannel을 raw pointer로 저장해두는 곳이 한 곳 있기는 하나 (ProcInfo::waitchannel), 이 부분은 그 Proc이 sleep() 안에들어갈때만 임시적으로 non-null한 값으로 쓰여졌다가 sleep()이 끝나기 전에 다시 null로 바뀝니다.

• 이 issue는 close하면 될 것으로 보입니다. 다만, 그렇다 하더라도 move되선 안되는 struct들이 rv6에 여전히 포함되어 있기 때문에, Pin API에 관한 논의는 다른 issue에서 진행하겠습니다.

[travis1829]

superseded by #378