pmalloc() 최적화

[JuneParkCode]

문제 상황

• pmalloc() 의 가용 공간의 경우 기본 16KB 로 약 200 개의 pool node 를 담을 수 있다.
• 하지만, 할당 요청이 아주 많은 경우 (특히 LARGE 가 수 없이 많이 할당되는 경우) pool node 의 사용량이 급격하게 증가한다.
• 660e436 의 코드의 경우, 해당 상황에서 pfree() 호출 이후 다음과 같은 문제가 발생할 수 있다.
• pmalloc_space 탐색 시간이 O(N) 으로 느리다.
• pmalloc_spsce 가 완전히 가용할 때 시스템에 의해 회수되지 않고 그대로 남아있다. (leak)
• 이후 pmalloc() 호출에서 가용한 pmalloc_space를 탐색하기 위해 O(N) 이 소요된다.

변경 사항

• pmalloc_space 이 시스템에 회수 가능하도록 변경한다.
• 현재 가용한 space 를 O(1) 로 접근할 수 있도록 정보를 저장한다.

논의

• 시스템에 자원이 회수되도록 하기 위해서는 pmalloc_space 에 속한 free_block 의 회수 또한 이루어져야한다. 그러나, head space 의 free_list 에 의해서 모든 free_block 이 관리되고 있기 때문에, 해당 과정은 N = number of free_block 에서 O(N) 이 소요되는 작업이다. 해당 문제가 space의 개수가 클 때 발생하는 것을 감안하면, 시간이 상당히 소요되는 작업이다.
• 따라서, head space 에서 관리되던 체계에서, 각 space 의 free_list 를 통해 접근하는 방식으로 전환하고, space 를 찾는데 시간을 들이는 것이 더 유리하다.
• free_block 이 각각의 space 에서 관리하게 된다면, free_block 의 주소를 통해서 space 를 찾아내는 작업이 필요하다. 기존 구조를 통해서라면 주소값 비교를 통해서 진행해야하므로 space의 개수 = N O(N) 이 소요된다.
• 이는 O(1) 로 space 에 접근하기 위해 메타데이터를 앞선 8바이트에 저장하여 해결할 수 있다.
  • 블록의 사이즈가 64 byte aligned 되어있지 않기 때문에, 충분하다.
• pfree() 시의 문제는 위 해결방안으로 해결되나, pmalloc() 시 가용 space 탐색 문제는 아직 해결되지 않는다.
• pmalloc() 의 경우, 이전에 사용한 space 를 활용하는 방안을 고려할 수 있다.
  • 이를 cache_space 라고 칭하자.
• cache_space 는 현재 가용한 space 중 가장 최근에 접근된 space 를 가리킨다. 이를 통해 최근에 사용한 메모리를 재활용할 수 있으며, cache_space가 존재하는 대부분의 경우에는 O(1) 로 space 탐색이 가능해진다.
  • 다만, 모두 실패한 경우 space 탐색이 O(N)으로 발생한다.

해결 방안

• free_list 를 head 가 아닌 각각 통합 관리
• space 의 가용성 추적을 위해 가용 블록 개수 저장
• space 를 pfree() 시에 빠르게 찾기 위해, space 에 대한 정보를 블록 앞에 저장 후 반환한다.
• space 를 pmalloc() 에서 빠르게 탐색하기 위해 cached_space 를 구성한다.
• space 회수를 위해 malloc() 에서와 마찬가지로 free_space 를 구성한다.
  • 존재할 경우 회수 작업을 진행한다.

해결 커밋

f1a36ff