multi-core에서 spinlock 없이 프로그래밍 하기

이야기 나왔던것 중에 spinlock 없이 전역 자료를 엑세스하는 방법에 대한 설명 추가합니다.

이전에 kldp에서 누군가 올린 질문에 대답한건데 정리 안하고 그냥 올립니다.

================================================================

안녕하세요 ? Memory barrier 관련된 질문 드립니다.

리눅스 커널 코드의 timer.c 에 사용되고 있는 Barrier 관련 부분이 잘 이해가 안갑니다.

코드 부분은 아래에 적었습니다.

/*
 * Accessing ->group_leader->real_parent is not SMP-safe, it could
 * change from under us. However, rather than getting any lock
 * we can use an optimistic algorithm: get the parent
 * pid, and go back and check that the parent is still
 * the same. If it has changed (which is extremely unlikely
 * indeed), we just try again..
 *
 * NOTE! This depends on the fact that even if we _do_
 * get an old value of "parent", we can happily dereference
 * the pointer (it was and remains a dereferencable kernel pointer
 * no matter what): we just can't necessarily trust the result
 * until we know that the parent pointer is valid.
 *
 * NOTE2: ->group_leader never changes from under us.
 */
asmlinkage long sys_getppid(void)
{
	int pid;
	struct task_struct *me = current;
	struct task_struct *parent;
 
	parent = me->group_leader->real_parent;
	for (;;) {
		pid = parent->tgid;
#if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT)
{
		struct task_struct *old = parent;
 
		/*
		 * Make sure we read the pid before re-reading the
		 * parent pointer:
		 */
		smp_rmb();
		parent = me->group_leader->real_parent;
		if (old != parent)
			continue;
}
#endif
		break;
	}
	return pid;
}

위의 코드를 보게 되면 for 문 안의 pid = parent->tgid; 가 parent = me->group_leader->real_parent; 보다
나중에 실행될수 있기 때문에 smp_rmb() 를 걸어놓은것 같은데 어떤 상황에서 이런일이 발생할수 있는건가요 ?
제 생각에는 Compiler 가 최적화 과정을 통해서 for 문 안에 들어오기 전에 pid=parent->tgid 를 한번 실행하고
for 문 안에 들어오는 경우에는 위와 같은 case 가 발생할수 있기 때문이라는 생각이 들기는 하는데 좀 명확하지 않습니다.

여기 계신 전문가님들 께서 이 부분의 코드에 대해서 최대한 자세히 코멘트좀 달아주시길 부탁드립니다.

 

memory barrier는 execution

Submitted by 김성진 on 수, 2007/07/11 - 3:51pm.

memory barrier는 execution ordering을 보장하기 위한 것이지요.

execution reordering은 컴파일러 최적화에 의해서 일어날 수 도 있고,

CPU의 execute queue(정확한 용어인지...-_-;;)에서 발생할 수 있기 때문에

이것을 사용하는 것이라고 알고 있습니다.

제가 테스트해본 경험에 의하면, 컴파일러의 경우 최적화가 아무리 높더라도,

코드내부에 asm과 같은 어셈블러 코드가 들어가면, 절대로 reordering을 하지 않았고,

reordering이 걱정되는 경우에는 강제로 dependency를 만들어서 코딩하는 경우도 있습니다.

코드에서

A struct task_struct *old = parent;

/*
* Make sure we read the pid before re-reading the
* parent pointer:
*/
B smp_rmb();
C parent = me->group_leader->real_parent;
D if (old != parent)
continue;

에서 A와 C의 순서를 강제로 보장하는 것인데,

만일 C->A의 순서대로 수행이 된다고 생각해 보십시요.

D의 수행결과가 엉망이 되겠지요.

왜 이런 코드가 생기는가는 A라인이 특성 때문입니다.

컴파일러 최적화는 논리적으로는 라인과 라인 물리적으로는 opcode block과 opcode block간의

dependency가 없고, reordering에 의해서 수행비용이 낮아질 수 있다면 무조건 순서를 바꿉니다.

혹은 CPU도 opcode간의 비용계산을 통해 수행순서를 바꾸지요.

애석하게도 위의 A는 C와 아무런 의존관계가 없기 때문에 이러한 현상이 나타날 수 있습니다.

사람의 생각으로는 이전의 parent값을 가져오는 논리적인 의존관계가 있지만,

컴파일러나 CPU입장에서는 단지 임시값을 저장하는 A의 코드를 의존관계를 보지 않지요.

물론, 사람은 D의 라인을 통해 이전의 값과 최신값을 비교하는 기능을 하고 싶은 것이지만,

컴파일러나 CPU는 그렇지 않다는데 문제가 있습니다.

사실 이런 문제를 코딩할 때 제대로 catch하기는 상당히 힘듭니다.

제가 몸담고 있는 회사의 경우에도 설계/구현시에는 아무런 문제가 없었다가,

IBM p690이라는 CPU 32개의 기계에서 memory barrier관련 문제가 발생하여서,

상당히 혼난적이 있습니다.

경험으로는 위의 코드는 강제로 depencency를 주어서 해결하기도 하였지만,

100% 보장은 못하겠습니다.

int a = 0;

if (a++ == 0)
{
execution A;
}

if (a++ == 1)
{
execution B;
}

이렇게 해결한 적도 있습니다만..쩝.

김성진

고도의 추상화, 극도의 구체화, 에디슨을 그리워하다.

»

• 답글

그런데 코멘트를 보게 되면

Submitted by kernelnewbie on 수, 2007/07/11 - 6:12pm.

설명 감사드립니다.

그런데 코드 안의 아래 코멘트를 참조하면

Make sure we read the pid before re-reading the parent pointer

old 보다는 pid 를 읽는게 실질적인 이유인것 같은데 어떻게 생각하시는지요 ?

»

• 답글

rmb 는 read간의 순서를 맞춰주기 위한 barrier 입니다.

Submitted by molla on 금, 2007/07/20 - 7:35pm.

rmb, smp_rmb 모두 read memory barrier로, barrier위의 read가 끝난 뒤, barrier 아래의 read를 수행하라는 내용입니다.

두 read간의 순서가 어긋날 수 있는 것은 위의 김성진님이 말씀하신 것처럼, compiler의 optimization에 의해 일어날 수도 있고, cpu에서 최적화하는 과정에서 일어날 수도 있습니다. 물론 rmb 는 이 둘 모두를 막아주는 것이지요.

위의 내용은 맨 윗줄의 주석에 보니, real_parent라는 값 자체가 다른 cpu에 의해 변할 수 있는 값이라고 나오는군요. 따라서 정확한 값을 읽으려면 spinlock 을 사용하면 되겠지만, optimistic한 알고리즘을 써서 그냥 좀 비정확하더라도 spinlock overhead를 줄이겠다는 것이지요.

따라서 약간의 텀을 두고 real_parent를 두번 읽은 다음, 두번 사이에 변하지 않았다면 그게 맞는 거다 라고 생각하겠다 라는 것인듯 합니다. 그리고 그 두번의 텀을 주기 위해(라면 좀 이상할 수도 있겠지만. 여튼) real_parent의 pid를 먼저 읽고 그 뒤에 다시 real_parent를 읽겠다는 것입니다. 그리고 그 두 read간의 순서를 보장하기 위해 smp_rmb를 사용했다. 라고 생각하시면 될 듯 합니다.

»

• 답글

이 코드의 효과를 잘 모르겠네요.

Submitted by robo872 on 토, 2007/07/21 - 10:54pm.

컴파일러가 barrier 없이 만들 수 있는 최악의 코드는
temp = me->group_leader->real_parent;
*old = parent;
parent = temp;
이정도로 보입니다.
barrier가 있다면 현재 소스 코드 형태로 코드가 생성되는 걸 보장할 수 있겠죠.
그래봐야 최악의 경우랑 비교해볼 때 old와 parent 값을 구하는 사이에 시간이 살짝 (인스트럭션 몇개 수행하는 시간 정도) 차이가 나니. 당연히 그사이에 값이 바뀔 확률이 높아 지는 건 맞는 것 같아보입니다.
아는 것만큼 보인다고 저게 뭔 효과가 명확하게 있나 모르겠네요.
고수님들 있고 없고의 차이와 성능에 대해 설명 좀 부탁드립니다.
그리고 #ifdef로 SMB와 PREEMPT가 있던데 왜 이 경우에 해당하는지도 설명해주시면 좋겠네요.

커널 소스는 참 어렵네요.

»

• 답글

컴파일러가 더욱

Submitted by wariua on 일, 2007/07/22 - 3:29am.

컴파일러가 더욱 바람직하지 않은 코드를 만들 수도 있습니다. 커널 소스의 경우 기본적으로 -O2 최적화가 이뤄지는데, 위 코드에서 smb_rmb() (내지는 barrier())가 없는 경우 컴파일러는 parent 변수의 값이 항상 동일할 것이라고 판단하여 "if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT)" 내의 코드를 모두 생략해 버릴 수 있습니다. 타이밍 내지는 확률 정도의 문제가 아닌 게 되는 거죠. :-)

SMP와 PREEMPT의 의미는...

위 코드의 "if defined ..." 안에 있는 내용은 위 코드의 일부가 실행된 상태에서 me->group_leader->real_parent의 값을 바꿔버리는 다른 코드(가령, kernel/exit.c의 forget_original_parent())가 실행되는 경우에 발생할 수 있는 문제(반환되는 pid 값이 유효하지 않은 값이 되는 것)에 대처하기 위한 것입니다. 그런 경우는 크게 두 가지가 있습니다. 다른 코드가 이웃 CPU에서 동시에 실행되는 경우와, 실행 도중에 이 코드를 다른 코드가 선점하는 경우입니다. 각각 CONFIG_SMP와 CONFIG_PREEMPT에 대응하게 됩니다.

& 그나저나... 위 코드가 어느 버전의 코드인지는 모르겠지만, 최근 버전에서는 rcu를 이용해서 훨씬 단순하게 바뀌었나 보군요.
----
$PWD `date`

»

• 답글

깔끔한 답변

Submitted by robo872 on 일, 2007/07/22 - 8:41pm.

깔끔한 답변 감사합니다.
컴파일러 입장에서는 값이 바뀌는 경우가 없으니 for loop 밖에서 구한 me->goup_leader->real_parent의 값을 for loop안에서 그대로 이용하겠네요.
더 최적화한다면 똑같은 값을 parent에 넣는 거니 의미 없는 코드로 생각해 삭제해도 전혀 문제가 되지 않는 군요.
이런 건 정말 사람 눈에 보이지 않겠습니다.
컴파일러가 warning을 발생이라도 시켠 준단 몰라도 사람이 판단해기는 어렵겠네요.
코드에 워닝 나는 거 대충 생까주고 있는데, 낼부터 조심해서 봐야겠습니다.

»

• 답글

아무리 compiler가 ILP

Submitted by anfl on 화, 2007/07/24 - 2:06pm.

아무리 compiler가 ILP 최적화를 수행하고, processor에서 reorder 한다고 해도 위코드는 말씀하신대로 reorder 되지는 않습니다.

===========================================
A: pid = temp;
B: old = temp;
C: temp = me->group_leader->real_parent;
===========================================

A,B와 C와의 관계는 ANTI-depedency 관계에 있기 때문에 일반적인 방법으로 reorder 할수 없습니다.
ANTI-dependency와 같은 false depedency는 register renameing과 같은 방법을 쓰면 reorder 할수 있습니다.
그리고 이때는 renaming 했기 때문에 reorder해도 아무 문제가 없기 때문에 질문하신분의 내용과는 크게 관계 없을듯 합니다.

때문에 굳이 smp_rmb()를 넣은 이유를 들라면 molla님께서 잘 설명해주셨듯이
spinlock을 동기화 해야 될 부분을 real_parent의 값을 두번읽어봄으로써 spinlock을
안쓰고 overheader 줄이려고 했고 이때 wariua님 말대로 이전에 읽은 parent를 보장하기 위해
smp_rmb()를 넣은 것입니다.

»

• 답글

쓰신 내용에 제가

Submitted by robo872 on 수, 2007/07/25 - 1:30am.

쓰신 내용에 제가 모르는 내용이 많아서 몇가지 검색하면서 새로운 것들 많이 배웠습니다.
Processor Reordering이 뭔지 어떻게 되나 알수가 없었는데, Out-of-Order Processor라는 게 있더군요.
인스트럭션을 큐에다 집어넣고, 인스트럭션의 operand가 가용할 때까지 기다렸다고 수행해서 메모리에서 로드될 때까지 기다리는 시간을 줄이는 방법이더군요.
상세히는 모르겟지만 대충 감은 잡히더군요.

그런데 이런 의문이 들더군요.
고수님들은 Processor의 이런 기능까지 고려해서 코드를 작성합니까?
어셈블러가 아닌 C 언어에서도 이 기능들을 이용한 최적화가 가능합니까?
저로서는 도저히 감이 안 잡힙니다. 혹 이런 원칙이 있으면 알려주세요.

적다 보니 살짝 한심한 생각이 드네요.
N^2이니 NlogN 같은 루프 수행 회수나 확실히 줄이고, 그 다음에 몇 clock 줄이는 방법 고민해야지.
걷지도 못하는 주제에 뛸려고 하는 것 같습니다.
그래도 요런게 신기하고 또 재미는 있네요.
이런 놈들 때문에 클럭 단위의 수행 시간 계산은 거의 불가능하네요.
cache hit에다가 instruction도 순서대로 수행 안 될 수도 있으니.. 참 복잡하고 경이로운 세상입니다.
엔지니어링의 마지막은 최적화인가 봅니다.
수많은 패러미터들 위에서 최적 방법을 찾는 건 정말 Art입니다.

»

• 답글

일반적으로

Submitted by anfl on 수, 2007/07/25 - 5:24am.

일반적으로 application을 개발할때는 고려하지 않습니다.
사실 이런류의 architecture 최적화는 들이는 노력에 비해 얻는것이 크지 않기 때문입니다.
그 보다는 알고리즘 level 또는 자료구조를 잘 설계하기 위해 노력합니다.

하지만 OS, compiler와 같은 system level 프로그래밍을 하거나 codec과 같은 성능에 민감한 프로그래밍을 할때는 고려를 합니다.

compiler의 경우 compiler 자체 source code에서는 고려하지 않고 compiler가 생성하는 code에 대해서는 모두 이런 특징을 고려하고 있습니다.

OS와 같은 경우에는 linux kernel source에서 보신봐와 같이 c level에서 어떻게 assembly code가 생성될지... 그리고 그 assembly code가 architecture 특징에 따라 어떻게 scheduling 될지에 따라 최적화 되고 안되고의 문제를 떠나 정상적으로 수행될지 안될지의 문제가 생기기 때문에 항상 c 소스를 코딩하면서 머리속으로 컴파일 하고 scheduling 하면서 코딩을 합니다. 그렇지 않으면 이런류의 오류는 쉽게 발견되기도 힘들고 큰 사고로 연결될수 있기 때문입니다.
그리고 c level에서 이렇게 생각할수 있는건 어느 정도의 compiler 지식과, architecture 지식을 가지고 습관적으로 연습하면 어렵지 않게 할수 있습니다.

codec 같은 경우에는 이정도까지 고려는 하지 않고 SIMD와 DMA 쓰는것 정도로 고려를 하는것 같습니다. codec 하시는 분들은 대부분 architecture나 compiler에 대해서는 깊게 모르시더군요. 하지만 워낙 성능에 민감한 프로그램이라서 architecture에서 제공해주는 최적화 기능들을 사용하려고 노력하는것 같았습니다.

결국 일반적인 application을 작성할때는 고려를 하면 좋지만 굳이 그럴필요까지는 없다고 생각합니다. processor나 compiler에 맞겨버리면 되는 문제라는 생각이 듭니다. 하지만 처음부터 고려를 하는것이 목적인 프로그램을 작성하시거나, 고려하지 않으면 문제가 발생할수 있는 프로그래밍을 하실때는 그때는 심각하게 고려를 해야겠지요.

»

• 편집
• 답글

parent구하기와 pid구하기를 atomic하게 실행할 수 없기 때문

Submitted by prether on 화, 2008/04/08 - 9:41am.

아래 두 statement를 atomic하게 실행할 수 없기 때문이라고 봅니다.
parent = me->group_leader->real_parent;
pid = parent->tgid;

위의 두 statement를 실행하는 동안 real_parent가 바뀔 수도 있고 결과적으로 parent의 pid도 바뀔 수 있습니다(SMP, preemptive환경에서).

이를 막기 위해 두 statement의 앞뒤로 lock 쓸 수 있으나 그럴 경우 성능이 떨어지기 때문에 안쓴겁니다.

대신에 아래와 같이 parent 포인터 구하기를 두 번 실행하고

parent = me->group_leader->real_parent;
pid = parent->tgid;
parent = me->group_leader->real_parent;

그 두 parent 포인터가 변하지 않았다면 처음 두 statement를 실행하는 동안 real_parent가 변하지 않았다는 것을 입증할 수 있습니다.

그러나 instruction reordering에 의해 pid구하기가 두 번의 parent 포인터 구하기 사이에 실행되지 않고 그 후에 실행된다면 real_parent가 변하지 않았다는 것을 입증할 수 없습니다.
이를 방지하기 위해 memory barrier를 사용한 것으로 보입니다.

/***************************************
Being the one is just like being in love.
***************************************/