ProcsBuilder::wait_lock's invariant

[Medowhill]

ProcsBuilder::init은 self.wait_lock을 &'static으로 빌려서 다른 객체에 저장합니다. 따라서 self가 &'static으로 빌려진 상태이므로 &mut으로 다시 빌리면 원래는 안 됩니다. 하지만, 실제로는 self.wait_lock에는 앞으로 다시 접근하지 않을 것이기 때문에 &mut으로 빌려도 문제가 발생하지 않습니다. 그래서 Procs의 invariant로 wait_lock에 접근하지 않는다는 내용을 추가하고, self를 &mut ProcsBuilder 대신 &mut Procs 타입으로 만들어 리턴합니다. 다만 self가 이미 &'static으로 빌려진 상태에서 &mut Procs를 만들려고 하면 ownership 검사를 통과할 수 없기 때문에, self.wait_lock을 빌릴 때 raw pointer로 변환하는 과정을 거쳐 self가 &'static으로 빌려진 상태라는 것을 컴파일러가 모르게 만들었습니다.

Originally posted by @Medowhill in #454 (comment)

---

ProcsBuilder::wait_lock's invariant에 대한 논의와 정리가 필요

[Medowhill]

wait은 Proc의 메서드. 나(= 어떤 Proc)의 wait을 호출하면:
loop를 돌면서 모든 Proc의 parent를 확인
-> 나를 부모로 하는 Proc P가 있으면 P의 락을 잡고 P가 좀비인지 확인
-> P가 좀비이면 P를 정리하고 return, 아니면 다음 Proc으로
-> 나를 부모로 하는 Proc이 있지만 그중 아무도 좀비가 아니면 나는 sleep, 그런 Proc이 없으면 return
-> wakeup으로 인해 sleep에서 깨어나면 다시 loop 처음부터 시작

P가 내 유일한 자녀라고 할 때, 다음 상황이 가능:
loop을 시작하기 전 P가 좀비가 아님
-> P의 락을 잡고, P가 좀비가 아님을 확인하고, P의 락을 해제
-> P가 좀비가 된 뒤 나를 wakeup(내가 sleep 중이 아니므로 아무 효과 없음)
-> 내가 loop을 다 돌고 sleep
-> 나는 sleep에서 깨어날 방법이 없음 (lost wakeup)

현재 구현은 wait_lock을 통해 이 문제를 해결:
loop을 시작하기 전 wait_lock을 잡음
-> P를 확인
-> P가 나를 wakeup하려면 wait_lock을 잡아야 하므로 wakeup하지 못하고 기다림
-> 내가 loop을 다 돌고 sleep하면서 wait_lock을 해제
-> P가 wait_lock을 잡고, 나를 wakeup하고, wait_lock을 해제
-> 나는 wakeup된 뒤 wait_lock을 잡고 다시 loop 시작

만약 wait_lock이 없고 각 parent가 별개의 락으로 보호받고 있다면 위와 같이 문제가 해결되지 못하고 lost wakeup이 발생 가능.

옛날 xv6 구현은 wait_lock 없이 이 문제를 해결:
loop을 시작하기 전 내 락을 잡음
-> P를 확인
-> P가 나를 wakeup하려면 자신의 parent의 락, 즉 내 락을 잡아야 하므로 wakeup하지 못하고 기다림
-> 내가 loop을 다 돌고 sleep하면서 내 락을 해제
-> P가 내 락을 잡고, 나를 wakeup하고, 내 락을 해제
-> 나는 wakeup된 뒤 내 락을 잡고 다시 loop 시작

xv6 구현이 현재와 같이 바뀐 이유가

• 옛날 구현에 어떤 문제가 있기 때문인지,
• 아니면 옛날 구현이 틀린 것은 아니지만 현재 구현이 더 좋기 때문인지

는 아직 확실히 모르겠음.

[travis1829]

xv6 구현이 현재와 같이 바뀐 이유가

옛날 구현에 어떤 문제가 있기 때문인지,
아니면 옛날 구현이 틀린 것은 아니지만 현재 구현이 더 좋기 때문인지

는 아직 확실히 모르겠음.

@Medowhill
#301 를 참고하면, 현재 구현이 더 좋기 때문에 이렇게 바뀐 것으로 보입니다.

• mit-pdos/xv6-riscv@8d4fbc6 이전에는, reparent() 이 끝나면 wakeup(initproc)을 하지 않고 exit()을 실행하는 중간에 wakeup(initproc)을 실행합니다. 이는 reparent()내에서 wakeup(initproc)을 실행하면 deadlock이 생길 수 있기 때문입니다.

pp->parent = initproc;
// we should wake up init here, but that would require
// initproc->lock, which would be a deadlock, since we hold
// the lock on one of init's children (pp). this is why
// exit() always wakes init (before acquiring any locks).

mit-pdos/xv6-riscv@8d4fbc6#diff-f06ba4e6ae5b13cb787bad05af2c231bcf826410f25bfd78b18774115f0d20a8L328-L332

• 또한, 주석을 참고해보니 이전에는 initproc이 wakeup을 놓칠수도 있었던 모양입니다.

// we might re-parent a child to init. we can't be precise about
// waking up init, since we can't acquire its lock once we've
// acquired any other proc lock. so wake up init whether that's
// necessary or not. init may miss this wakeup, but that seems
// harmless.

mit-pdos/xv6-riscv@8d4fbc6#diff-f06ba4e6ae5b13cb787bad05af2c231bcf826410f25bfd78b18774115f0d20a8L362-L366

[Medowhill]

현재는 Proc이 parent 필드를 가지고 있으며 Procs가 Proc의 리스트를 가지고 있는 구조이지만, 이를 Procs가 Proc의 리스트와 각 Proc의 parent에 해당하는 *const Proc의 리스트를 가지고 있다고 해석할 수 있습니다. 이 parent의 리스트를 parents라고 부른다면, wait에서는 parents 리스트를 iteration합니다. Iteration 도중에 다른 스레드에 의해 parents가 수정되면 원하지 않는 동작(UB는 아니지만 wakeup을 잃어버려 프로세스가 영원히 sleep하게 됨)이 일어날 수 있기 때문에 parents는 락에 의해 자료 구조 전체가 보호 받아야 합니다. 현재 구현에서 이 락에 해당하는 것이 wait_lock입니다. 즉, 원래는 parents라는 하나의 자료 구조가 락에 의해 보호받는 형태여야 하는 것이 현재는 parents의 각 원소가 Proc들에 흩어져 있고 모든 원소를 하나의 락으로 보호하기 위해 SpinlockProtected를 사용했다고 볼 수 있습니다.

코드 형태로 정리하자면 다음과 같습니다.

현재 구조:

struct Procs {
    process_pool: List<Proc>,
    wait_lock: Lock
    ...
}

struct Proc {
    parent: LockProtected<*const Proc>,
    data: ProcData,
    ...
}

논리적인 구조:

struct Procs {
    process_pool: List<Proc>,
    parents: Lock<List<*const Proc>>,
}

struct Proc {
    data: ProcData
    ...
}

실제로 구현을 후자와 같이 수정하는 것을 시도해 볼 수도 있을 것 같습니다. 다만, process_pool과 parents의 원소 사이의 관계를 만들어 줘야 할텐데 이 부분 때문에 구현이 잘 될지는 아직 모르겠습니다. 또한, wait과 wait_lock의 관점에서는 parents가 별도의 리스트로 존재하는 것이 이해하기 쉬운 설계일 수 있으나, Proc의 관점에서는 Proc이 소유한 데이터로 볼 법한 parent가 별도의 리스트에 존재하는 것이 이상한 설계로 느껴질 수 있어 보입니다.

[travis1829]

이러면, Proc이 자신의 parent Proc을 알아내기 위해서는 (ex: parent Proc을 wakeup 시킬때)

• Proc 내부에 Procs를 가리키는 reference등을 추가하기 (∵ Procs가 여러개일 수 있으므로),
• Proc 내부에 index number를 usize로 저장하기 (∵ 자신의 parent가 Procs::parents의 몇번째 index에 저장되어있는지 알기 위해서) (다만, 이는 동일한 index에 저장한다고 가정하면, pointer arithmetic을 이용해서 우회할 수도 있음),

등 위와 같은 변화가 필요한 것인지 문의드립니다.

[Medowhill]

네. 그럴 것 같습니다.

[Medowhill]

"각 Proc이 자신의 zombie children 리스트를 intrusive linked list 형태로 가지고 있도록 동작을 바꾸자"는 제안.

[Medowhill]

Linux에서 어떻게 하는지 조사해 보자.

[Medowhill]

Linux 코드가 길고 복잡하다보니 제가 제대로 이해했다는 확신은 없습니다만, 지금까지 이해한 내용을 바탕으로 적은 Linux에서 wait의 lost wakeup을 해결하는 방법에 대한 글입니다.

Linux의 wait syscall 처리 루틴은 kernel/exit.c 에 있습니다. wait syscall은 kernel_wait4 함수에 의해 처리됩니다.

long kernel_wait4(pid_t upid, int __user *stat_addr, int options,
		  struct rusage *ru)

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L1595-L1596

kernel_wait4는 do_wait을 호출합니다.

	ret = do_wait(&wo);

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L1630

실질적인 wait 처리는 do_wait에서 이루어집니다.

static long do_wait(struct wait_opts *wo)

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L1442

do_wait은 tasklist_lock이라는 rwlock에 read_lock을 건 뒤 do_wait_thread를 호출합니다.

	read_lock(&tasklist_lock);
	tsk = current;
	do {
		retval = do_wait_thread(wo, tsk);
		if (retval)
			goto end;

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L1465-L1470

do_wait_thread에서는 list_for_each_entry 매크로를 통해 현재 task의 각 자녀 task를 인자로 하여 wait_consider_task를 호출합니다. wait_consider_task는 해당 task가 wait syscall이 기다리는 task이면 tasklist_lock의 read_lock을 해제한 뒤 0보다 큰 정수를 반환합니다.

static int do_wait_thread(struct wait_opts *wo, struct task_struct *tsk)
{
	struct task_struct *p;

	list_for_each_entry(p, &tsk->children, sibling) {
		int ret = wait_consider_task(wo, 0, p);

		if (ret)
			return ret;
	}

	return 0;
}

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L1392-L1404

조건에 부합하는 자녀를 찾았으면 do_wait이 결과를 반환하면서 syscall이 처리되고, 찾지 못했으면 schedule을 호출해 sleep 상태에 들어갔다가 나중에 깨워지면 다시 do_wait_thread를 호출합니다.

			schedule();
			goto repeat;
		}
	}
end:
	__set_current_state(TASK_RUNNING);
	remove_wait_queue(&current->signal->wait_chldexit, &wo->child_wait);
	return retval;

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L1486-L1493

rv6에서는 조건을 만족하는 자녀를 찾기 위해 전체 process의 리스트를 탐색하지만, Linux에서는 각 task마다 자신의 자녀 task의 리스트를 가지고 있어 해당 리스트만 탐색한다는 차이가 있습니다. 이를 제외하면 기본적인 로직은 유사한 것 같습니다.

같은 파일에 exit syscall을 처리하는 루틴도 있습니다. 그중 exit_notify를 보면, tasklist_lock에 write_lock을 건 뒤 자신의 exit state를 ZOMBIE로 바꾸고 do_notify_parent를 호출합니다. do_notify_parent에서는 __wake_up_parent를 호출해 부모를 깨웁니다.

static void exit_notify(struct task_struct *tsk, int group_dead)
{
	bool autoreap;
	struct task_struct *p, *n;
	LIST_HEAD(dead);

	write_lock_irq(&tasklist_lock);
	forget_original_parent(tsk, &dead);

	if (group_dead)
		kill_orphaned_pgrp(tsk->group_leader, NULL);

	tsk->exit_state = EXIT_ZOMBIE;
	if (unlikely(tsk->ptrace)) {
		int sig = thread_group_leader(tsk) &&
				thread_group_empty(tsk) &&
				!ptrace_reparented(tsk) ?
			tsk->exit_signal : SIGCHLD;
		autoreap = do_notify_parent(tsk, sig);
	} else if (thread_group_leader(tsk)) {
		autoreap = thread_group_empty(tsk) &&
			do_notify_parent(tsk, tsk->exit_signal);

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L661-L682

프로세스 종료 로직 역시 xv6와 Linux에서 큰 차이는 없는 것 같습니다.

xv6에서 wait_lock을 통해 lost wakeup을 방지한 것처럼, Linux에서는 tasklist_lock으로 인해 lost wakeup이 일어나지 않는 것 같습니다. 다만, wait_lock은 오직 wait의 올바른 처리를 위해 존재하는 것과 달리, tasklist_lock은 많은 경우에 사용되는 더 일반적인 목적의 락인 것 같고 lost wakeup을 방지하는 효과는 부수적인 것이 아닌가 싶습니다.

[jeehoonkang]

잘 조사해주셔서 감사합니다.

rv6에서는 조건을 만족하는 자녀를 찾기 위해 전체 process의 리스트를 탐색하지만, Linux에서는 각 task마다 자신의 자녀 task의 리스트를 가지고 있어 해당 리스트만 탐색한다는 차이가 있습니다. 이를 제외하면 기본적인 로직은 유사한 것 같습니다.

혹시 children iteration이 필요한 다른 syscall이 있나요? children list를 따로 관리할 motivation이 궁금해서 질문드립니다.

우리도 Linux 디자인을 따라가는게 어떨지 제안드립니다. 다만 제가 이해한게 맞다면 read_lock(...)은 전체 task list에 대한 lock인 것 같은데, parent proc에 대한 lock으로 scope을 좁혀 잡아도 되는거 아닌가 하는 생각이 듭니다. 확인 요청드립니다.

[jeehoonkang]

아니면 심지어 한술 더떠서... completely lock-free kernel을 상상해볼 수도 있겠습니다. Rust를 이용해서 적은 비용으로 리팩토링 잘 해서 lock-free design을 만들었다는게 key contribution... 아마 다음 future work에서...

[Medowhill]

grep으로 ->children을 찾아 보면 사용되는 곳이 몇 군데 더 있기는 합니다. 예를 들어,

• task가 종료될 때 mm(각 task에 할당되는 memory descriptor인 것 같습니다)을 넘겨줄 task를 찾기 위해 자신의 자녀와 형제를 순회합니다.

/*
 * A task is exiting.   If it owned this mm, find a new owner for the mm.
 */
void mm_update_next_owner(struct mm_struct *mm)
{
	...
	/*
	 * Search in the children
	 */
	list_for_each_entry(c, &p->children, sibling) {
		if (c->mm == mm)
			goto assign_new_owner;
	}

	/*
	 * Search in the siblings
	 */
	list_for_each_entry(c, &p->real_parent->children, sibling) {
		if (c->mm == mm)
			goto assign_new_owner;
	}

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/exit.c#L343-L382

• 스케줄러에서 자녀의 실행 시간을 확인하는 경우도 있는 것 같습니다.

	/*
	 * The sum of our children's runtime should not exceed our own.
	 */
	list_for_each_entry_rcu(child, &tg->children, siblings) {
		period = ktime_to_ns(child->rt_bandwidth.rt_period);
		runtime = child->rt_bandwidth.rt_runtime;


		if (child == d->tg) {
			period = d->rt_period;
			runtime = d->rt_runtime;
		}


		sum += to_ratio(period, runtime);
	}


	if (sum > total)
		return -EINVAL;

https://github.com/torvalds/linux/blob/d19cc4bfbff1ae72c3505a00fb8ce0d3fa519e6c/kernel/sched/rt.c#L2577-L2593

Linux 디자인을 따라간다는 것이 어떤 뜻인가요? Linux처럼 자녀 프로세스 리스트를 만들어서 관리하자는 말씀이신가요? 아니면 지금처럼 wait_lock을 사용하는 설계를 유지하자는 말씀이신가요?

Linux에는 parent proc을 보호하는 lock은 따로 없는 것 같습니다. xv6에서 parent proc을 보호하는 락이 별도로 존재하는 이유는 wait에서 lost wakeup이 생기는 것을 막기 위함인데, Linux에서는 어차피 tasklist_lock을 잡음으로써 critical section이 만들어지기 때문에 parent만 따로 보호할 이유는 없어 보입니다. 다만, wait을 처리할 때 tasklist_lock을 잡아야 하는 이유와 tasklist_lock이 보호하는 대상이 무엇인지 아직 잘 모르겠는데, 코드를 읽어서는 알기 쉽지 않고 tasklist_lock의 목적을 설명하는 주석이나 문서가 보이지 않아서 어려움을 겪고 있습니다.

[Medowhill]

이제 wait_lock의 invariant는 어느 정도 정리된 것 같습니다. 여전히 이 설계가 바람직한지에 대한 의문이 남아 있지만, 오늘 미팅에서 논의한 내용에 따라 우선은 현재의 설계를 유지하도록 하겠습니다. wait_lock을 사용하지 않는 설계에 대해서는 #474 에서 논의합시다.