Cache Coherence Protocol - MESIF

http://en.wikipedia.org/wiki/MESIF_protocol

MESIF: cache coherent NUMA(ccNUMA) system을 위한 cache coherence protocol
(참고: nehalem 등에서 MESIF 사용함)

* MESIF protocol에서 cache line의 상태
 - MODIFIED: MESI와 동일
 - EXCLUSIVE: MESI와 동일
 - SHARED: MESI와 동일
 - INVALID: MESI와 동일
 - FORWARD
  -> SHARED 상태의 특수한 형태로써
  -> 해당 cache line에 대한 request에 대해 designated responder로 행동
  -> SHARED 상태의 cache가 있다면 FORWARD 상태인 cache는 없거나 있다면 한 개만 존재


* MESIF가 훌륭한 이유는?
 - MESI 사용 시스템에서는 여럿이 공유하는 SHARED 상태의 cache line에 대해 request를 보내면 main memory에 갔다오거나, 모든 cache가 response DOS attack을 보낼 수 있음..이는 비효율적임
 - MESIF 사용 시스템에서는 FORWARD 상태인 cache만 response를 해주면 된다!


* 그럼 누가 FORWARD 상태가 될 것인가?
FORWARD 상태의 cache가 discard되는 것을 최소화하기 위해서 가장 최근의 requestor의 cache line이 FORWARD 상태가 된다.
FORWARD 상태의 cache가 response를 하면, 해당 cache는 FORWARD 상태를 새로운 cache에게 양보함


* FORWARD 상태인 cache가 없는 경우에는?
메모리에 갔다와야 함. -.-


Cache Coherence Protocol - MESI

http://en.wikipedia.org/wiki/MESI_protocol

* MESI States
MODIFIED: cache line이 현재 cache에 올라와 있고 dirty 상태. 언젠간 write-back해야 함. write-back 후에는 EXCLUSIVE 상태로 전이
EXCLUSIVE: cache line이 현재 cache에 올라와 있고 clean 상태
SHARED: 이 cache line이 다른 cache에도 올라가 있을 수 있으며 clean한 상태.
INVALID: 이 cache line은 invalid 함


* Operations
- INVALID를 제외한 모든 상태에서 read 가능.
  INVALID 상태인 경우 메모리에서 fetch 해야 함
- cache가 MODIFIED/EXCLUSIVE 상태인 경우에만 write 가능.
  SHARED 상태에서 write가 일어나면 다른 곳에 있는 cache들을 모두 invalidate해야 함.
  이는 Request For Ownership(RFO)에 의해 수행 됨.
- non-MODIFIED 상태의 cache는 언제라도 discard(=INVALID 상태로 전이) 될 수 있음
  MODIFIED 상태인 경우 먼저 write-back이 일어나야 한다.
- MODIFIED 상태의 cache는 해당 메모리 영약에 대해 반드시 모든 read를 snoop해야 한다.
  이것은 강제로 해당 read를 back off(i.e. 나중에 재시도)하는 것으로 수행된다. 
  그리고 나서 memory에 해당 데이터를 write하고 cache의 상태를 shared 상태로 변경한다.
- SHARED 상태의 cache line을 유지하고 있는 cache는 반드시 invalidate 혹은 RFO 메시지를 listen하고 있다가 해당 메시지를 받으면 해당 cache line을 discard해야 한다.
- EXCLUSIVE 상태의 cache line을 유지하고 있는 cache는 반드시 모든 read operation을 snooping하고 있다가 해당 메시지를 받으면 SHARED 상태로 만들어야 한다.

- MODIFIED/EXCLUSIVE 상태는 항상 정확함
  -> 시스템에서 해당 cache line에 대한 ownership이 match 됨
- SHARED 상태는 부정확할 수 있음
  -> SHARED 상태의 cache line을 remote에서 discard하면 이 cache line은 나만의 것이 되지만 EXCLUSIVE가 되지는 않는다.
- 이런 맥락에서 EXCLUSIVE 상태는 기회 최적화(opportunistic optimization)이다.
  -> SHARED 상태의 cache line의 변경 => 다른 모든 cache를 invalidate하기 위해 bus transaction 필요
  -> EXCLUSIVE 상태를 변경하는 것은 bus transaction이 필요치 않음


* Request For Ownership(RFO)
read operation과 invalidate broadcast의 결합이다.
이것은 EXCLUSIVE 혹은 MODIFIED 상태가 아닌(=SHARED 혹은 INVALID 상태인) cacheline에 대해 write를 하는 CPU가 보냄
이 메시지를 받은 CPU는 해당 cache line을 INVALID 상태로 전이

ownership transaction을 위한 read operation은 해당 memory에 write하기 위한 read 임.그래서 이 operation은 exclusive 하다.
이로써 데이터를 내 cache로 가져오고 다른 CPU의 cache들은 invalidate 시킨다.

(A read for ownership transaction is a read operation with intent to write to that memory address. Therefore this operation is exclusive. It brings data to the cache and invalidates all other processor caches which hold this memory line.)

* 참고
clean: memory의 데이터와 cache의 데이터가 일치
dirty: memory의 데이터와 cache의 데이터가 불일치



결국, 각 상태마다 어떤 메시지들을 snoop 하거나 특정 메시지를 broadcast 함으로써 state transition을 수행..
이로써 cache coherence 지원..흠...


[LWN.net] Making workqueues non-reentrant

Making workqueues non-reentrant

By Jonathan Corbet
August 15, 2012


Workqueues are the primary mechanism for deferring work within the Linux kernel. The maintainer of this facility is Tejun Heo, who recently posted a patch series changing an aspect of workqueue behavior that, perhaps, few kernel developers know about. Most workqueues are reentrant, meaning that the same work item can be running on multiple CPUs at the same time. That can result in concurrency that developers are not expecting; it also significantly complicates the various "flush" operations in surprising ways. In summary, Tejun says:
(역) workqueues(=WQ)는 리눅스 커널에서 작업을 미루는 중요한 메커니즘이다. 이 메커니즘의 maintainer인 허태준님은 최근에 커널 개발자들이 잘 알지 못하는 WQ의 행동을 바꾸는 a patch series를 보냈다. 대부분의 WQ들이 reentrant한데, 이는 같은 작업이 동시에 여러 CPU 상에서 동작할 수 있다는 의미이다. 이것은 개발자들이 예상하지 못했던 concurrency 문제를 일으킨다. 또한 다양한 "flush" operation을 매우 복잡하게 한다. 허태준님은 다음과 같이 말했다.

In the end, workqueue is a pain in the ass to get completely correct and the breakages are very subtle. Depending on queueing pattern, assuming non-reentrancy might work fine most of the time. The effect of using flush_work() where flush_work_sync() should be used could be a lot more subtle. flush_work() becoming noop would happen extremely rarely for most users but it definitely is there.

A tool which is used as widely as workqueue shouldn't be this difficult and error-prone. This is just silly.

(역) WQ를 완전히 올바르게 하는게 힘들었지만 손실은 매우 적었다. queueing pattern에 따라 non-reentrancy라고 가정하는 것은 대부분 잘 동작한다. 반드시 flush_work_sync()가 사용되어야 하는 flush_work()의 효과는 좀더 어려울 수 있다. flush_work()가 아무일도 하지 않게 되는 것은 극히 드물지만 발생한다. WQ는 사용하기 쉬워야 한다...란 말인가..음..-_-;;;

Tejun's patch set is intended to make the workqueue interface work more like the timer interface, which is rather more careful about allowing concurrent operations on the same timer. All workqueues become non-reentrant, and aspects of the API related to reentrant behavior have been simplified. There is, evidently, a slight performance cost to the change, but Tejun says it is small, and the cost of flush operations should go down. It seems like a worthwhile trade-off, overall, but anybody who maintains code that depends on concurrent work item execution will want to be aware of the change.

(역) 허태준님의 패치는 WQ interface를 timer interface와 비슷하게 만들었다. 이것은 concurrent operation들을 사용할 때 좀 더 주의를 기울이도록 한다. 모든 WQ가 non-reentrant해졌고, 단순해졌다. 분명 성능이 약간 떨어지기는 했지만 허태준님은 성능 저하는 작고 flush operation cost는 작아져야 한다고 했다. 이것은 전반적으로 훌륭한 trade-off로 보인다. 하지만 concurrent 작업을 수행하는 코드를 관리하는 사람은 이 변화에 대해 알고 싶어할 것이다.


-----------------------------------------------------------------
허태준님이 WQ를 non-reentrant 하도록 수정하셨나보다.
여러 코드에서 널리 사용되는 WQ를 non-reentrant하도록 보장한 것.. 분명 잘 한 것으로 생각한다.
많은 개발자들이 커널의 기능을 사용하면서 그 깊고 오묘한 부분까지 알면서 개발하지는 못할 것이다.
물론 빠삭하게 알고 개발하기도 하지만, 그래야 하기도 하지만..대부분 있는 기능 잘 돌아가면 그냥 쓰기도 하는게 사실 아니던가?
리눅스 커널 전체를 다 몰라도 '(버그는 있을지언정)잘 돌아가겠거니..' 하지 않던가..
나만 그런 것은 아니겠지-_-;;
여튼..약간의 성능 저하가 있지만 개발자들이 크게 신경쓰지 않고 개발할 수 있는 환경을 만든 것..난 잘 한 선택이라고 본다.(물론 나따위 반대한다고 달라질 것은 없겠지만..-.-)

음..패치 내용에 대해서도 좀 봐야겠구먼~
-----------------------------------------------------------------
내용 추가.(2012/09/05)

패치 내용을 살펴보니..
기존에 flag로 제공하던 non-reentrant 기능(WQ_NON_REENTRANT)을 모든 workqueue에 기본 제공(선택사항 없음)하도록 한 것이었다.

[LWN.net] A generic hash table

A generic hash table by Jake Edge, August 8, 2012

출처: https://lwn.net/Articles/510202/


A data structure implementation that is more or less replicated in 50 or more places in the kernel seems like some nice low-hanging fruit to pick. That is just what Sasha Levin is trying to do with his generic hash table patch set. It implements a simple fixed-size hash table and starts the process of changing various existing hash table implementations to use this new infrastructure.
(역) Sasha Levin이 generic hash table patch를 작성했다. 이 패치는 simple fixed-size hash table을 구현했는데, 이는 기 존재하는 hash table을 새로운 infrastructure로 만들어 나가기 시작했다.

The interface to Levin's hash table is fairly straightforward. The API isdefined in linux/hashtable.h and one declares a hash table as follows:

    DEFINE_HASHTABLE(name, bits)

This creates a table with the given name and a power-of-2 size based on bits. The table is implemented using buckets containing a kernel struct hlist_head type. It implements a chaining hash, where hash collisions are simply added to the head of the hlist. One then calls:
    hash_init(name, bits);
to initialize the buckets.


(역) 이 hash table의 interface는 직관적인데, linux/hashtable.h에 정의되어 있다. hash_init()은 이름이 name, size는 2의 n승(power-of-2)인 hash table을 생성한다. 이 table은 struct hlist_head type의 bucket으로 구현되어있고, 새로운 entry들은 head에 들어가게 된다. 이 hash table을 초기화 하기 위해서는 hash_init()을 호출한다.

Once that's done, a structure containing a struct hlist_nodepointer can be constructed to hold the data to be inserted, which is done with:

    hash_add(name, bits, node, key);
where node is a pointer to the hlist_node andkey is the key that is hashed into the table.
(역)entry를 추가하기 위해서는 hash_add() 호출. node는 hlist_node이고, key는가 그야말로 key-_-;

There are also two mechanisms to iterate over the table. The first iterates through the entire hash table, returning the entries in each bucket:
    hash_for_each(name, bits, bkt, node, obj, member)
The second returns only the entries that correspond to the key's hash bucket:
    hash_for_each_possible(name, obj, bits, node, member, key)
In each case, obj is the type of the underlying data,node is a struct hlist_head pointer to use as a loop cursor, and member is the name of the struct hlist_node member in the stored data type. In addition, hash_for_each() needs an integer loop cursor, bkt.

(역) iterate를 위해 두 가지 macro 제공한다. hash_for_each()는 hash table 전체를 iterate 함. hash_for_eash_possible()은 key가 포함되는 bucket만 iterate 한다.
 - obj: data type
 - node: loop cursor로 사용할 struct hlist_head pointer 변수
 - member: structure 내의 hlist_node type 변수 이름
 - bkt: integer loop cursor(역자주: bucket id가 들어갈 변수)


Beyond that, one can remove an entry from the table with:
    hash_del(node);


(역) entry 삭제시에는 hash_del() 호출.


Levin has also converted six different hash table uses in the kernel as examples in the patch set. While the code savings aren't huge (a net loss of 16 lines), they could be reasonably significant after converting the 50+ different fixed-size hash tables that Levin found in the kernel. There is also the obvious advantage of restricting all of the hash table implementation bugs to one place.
(역) 저자는 patch set에 예제로 kernel에서 사용 중인 6개의 hash table을 변경했다. 이로 인해 전체적인 코드 사이즈 감량은 얼마 되지 않았지만 50개 이상의 hash table을 변경하면 꽤 클 것으로 보임. 그리고 분명히 코드를 하나로 통일했다는 장점이 있다.

There has been a fair amount of discussion of the patches over the three revisions that Levin has posted so far. Much of it concerned implementation details, but there was another more global concern as well. Eric W. Biederman was not convincedthat replacing the existing simple hash tables was desirable:

For a trivial hash table I don't know if the abstraction is worth it. For a hash table that starts off small and grows as big as you need it the [incentive] to use a hash table abstraction seems a lot stronger.

But, Linus Torvalds disagreed. He mentioned that he had been "playing around" with a directory cache (dcache) patch that uses a fixed-size hash table as an L1 cache for directory entries that provided a noticeable performance boost. If a lookup in that first hash table fails, the code then falls back to the existing dynamically sized hash table. The reason that the code hasn't been committed yet is because "filling of the small L1 hash is racy for me right now" and he has not yet found a lockless and race-free way to do so. So:

[...] what I really wanted to bring up was the fact that static hash tables of a fixed size are really quite noticeably faster. So I would say that Sasha's patch to make *that* case easy actually sounds nice, rather than making some more complicated case that is fundamentally slower and more complicated.

Torvalds posted his patch (dropped diff attachment) after a request from Josh Triplett. The race condition is "almost entirely theoretical", he said, so it could be used to generate some preliminary performance numbers. Beyond just using the small fixed-sized table, Torvalds's patch also circumvents any chaining; if the hash bucket doesn't contain the entry, the second cache is consulted. By avoiding "pointer chasing", the L1 dcache "really improved performance".

Torvalds's dcache work is, of course, something of an aside in terms of Levin's patches, but several kernel developers seemed favorably inclined toward consolidating the various kernel hash table implementations. Biederman was unimpressed with the conversion of the UID cache in the user namespace code and Nacked it. On the other hand, Mathieu Desnoyers had only minor comments on the conversion of the tracepoint hash table and Eric Dumazet had mostly stylistic comments on the conversion of the 9p protocol error table. There are several other maintainers who have not yet weighed in, but so far most of the reaction has been positive. Levin is trying to attract more reviews by converting a few subsystems, as he notes in the patch.

It is still a fair amount of work to convert the other 40+ implementations, but the conversion seems fairly straightforward. But, Biederman's complaint about the conversion of the namespace code is something to note: "I don't have the time for a new improved better hash table that makes the code buggier." Levin will need to prove that his implementation works well, and that the conversions don't introduce regressions, before there is any chance that we will see it in the mainline. There is no reason that all hash tables need to be converted before that happens—though it might make it more likely to go in.

--------------------------------------------------------------------------------------------------

이 패치를 들여다보면..사실 코드 자체는 별게 없다.
기존에 잘 사용하고 있는 hlist를 이용하여 hash table을 쉽게 생성/조작할 수 있는 macro 몇 개 제공...
하지만 코드 양이 적다고 무시할게 아니지 않은가.
거의 비슷한 형태로 각 모듈의 개발자들이 구현해 놓은  simple hash table을 하나의 interface로 통일할 수 있도록 한게 가장 큰 의미이지 싶다.

자체 hash function을 사용할 수 있게 한다던지 하는 약간의 option을 더 넣었으면 어떨까 싶다.
그리고 hash table 전체의 entry 개수라던지 bucket 별 entry 개수도 있으면 좋겠고...
개인적으로 실제로 사용하기에 조금 아쉬움이 있긴 하지만..
이건 "very simple hash table implementation"(저자의 표현을 인용)이니까..이대로도 분명히 좋은 코드라는 생각이 든다.

저자가 뽑아 놓은 future work 중에 RCU support는 반드시 조만간 지원 되기를 바란다.
(요즘 어지간 한 코드는 SMP 환경을 고려해야 한다. lookup 성능을 위해서는 RCU가 반드시 필요...)
그리고 lock은 알아서 써야하는 수 밖에 없나...음....


별 내용 없는 허접한 번역 끝-
(과연 이것을 번역이라 칭할 수 있는가.....-_-;;;;)



덧.
리뷰어에 허태준님.*_*
한국 사람이 리뷰어라는 것 만으로도 놀랍고 설렌다.
멋져요~ >_<b


[LWN.net] 동향 파악을 위한 lwn.net의 article 번역

어떻게 하면 최신의 커널 동향에 대해 파악할 수 있을까..라는 생각을 몇번 해봤지만..별 답은 없었다.
사실 현재의 커널도 잘 모르는데 어떻게 최신 동향을 follow-up 할 수 있을까..라는 다른 질문을 던지기도...OTL

그러다가 답이 될만한 것을 하나 찾았다.
바로 LWN.net의 article 번역.

LWN.net이 최신의 리눅스(정확히 하자면 open source?) 동향을 다루고 있기 때문에 LWN.net의 기사들을 보는 것이 분명 도움이 될 것이라 생각했다.
전부 다..는 아니겠지만..일단 조금이라도 알고 있고, 관심가는 분야를 하나씩 보다보면 좀 도움이 되지 않을까...하는 생각이 들었다.
이 블로그를 오가는 사람들에게도 조금이나마 도움이 될 수도 있을 것 같고..

여튼.. 이제 시작~!

1 2