개요
Motivation
C/C++ 처럼 많은 Unsafe한 Langauge들은 메모리 버그에 특히 Heap termporal memory safety버그에 취약하다. 이를 Memory allocator의 디자인으로 막을 수 있다.
Importance
기존의 방식들은 성능이 좋지 않거나, 보안상 취약점이 있거나, 아니면 Transparent하지 않다는 단점이 있었다.
Main Idea
우선 Memory allocator의 user-after-free를 lock and key 문제로 은유할 수 있다. 이는 Memory allocate (Lock)이 된후 사용되고 Free되면 (Unlock)사용을 하지 않아야 함이 유사하기 때문이다. 각각의 Object는 Lock이며, 이 Object를 가르키는 Pointer는 Key인데, Pointer는 Lock에 대한 접근이 허용된 경우만 사용해야 한다.
Background
Explicit한 방식은 따로 Metadata에 대한 Update와 Check를 매 Dereference마다 수행하여서 체크하는 방식이며, Implicit한 방식은 내부적으로 포인터에 대한 접근을 Invalidate시켜서 잘못된 접근을 체크하는 방식이다.
- Explicit lock and key
- Change the lock
- 각각의 Object들에 대해서 생성되는 포인터들에 대해서 키값을 부여하고, Derefernece상황에서 키값이 오브젝트의 락에 대해서 일치하는지를 검사하는 것이다.
- Explicit lock and key
- Revoke the keys
- Explicit lock and key에서는 오브젝트를 새로 할당할 경우에 새로운 Lock이 오브젝트에 할당되었다. 그렇게 하지 않고, Free상황에서 Object로 향하는 모든 Key값에 대해서 Key를 무력화 시키는 방식이다. 이 방식은 Pointer propagation을 고려하여야 하기 때문에 복잡하다.
- Implicit lock and key
- Revoke the keys
- Explicit한 방식들은 따로 Lock과 Key값을 에 대한 메타데이터를 업데이트 하였다. 그러나 Implicit방식에서는 그렇게 하지 않고 내부적으로 처리한다. 이 방법에서는, Free시, Key값을 가지는 오브젝트를 모두 Nullifying하는 방식으로 invalidate시켜서 포인터가 잘못된 오브젝트에서 dereference 하지 않도록 한다. 각각의 포인터에 대한 Physical address가 필요하기 때문에, Memory overhead가 크다. 이러한 오버헤드를 제거하기 위해서 Sweep과 같은 Garbage collection이 수행되는데, 이러한 경우에는 CPU Overhead가 커진다.
- Implicit lock and key
- Change the lock
- 이 방식은 위의 방식보다 조금더 단순하다. 이 방식에서는 Virtual address를 lock으로 생각한다. VA에 대한 Mapping을 제거하는 방식으로 Key들이 VA에 대한 접근을 할 수 없도록 만든다. 즉 Lock == VA이고 새로운 오브젝트 마다 새로운 Lock즉 새로운 VA를 부여받는 것이다. 그러나 이 방식은 Systemcall을 자주 사용해야 하며 (Mapping update를 위해서), TLB pressure 그리고 Fork에 대한 Compatibility가 떨어진다는 단점이 있다. 이때 같은 Physical address를 같지만 다른 VA를 가지는 Page들을 Aliased page라고 명명하였다.
Oscar Idea
Oscar에서는 Implicit lock and key에서 드는 비용을 system call overhead, TLB pressure, aliasing virtual address 그리고 metadata update에 드는 비용으로 분석하여 최적하였다.
Design
Naive Implementation
- Canonical page: 원래 원본이 되는 MMAP를 통해서 얻은 페이지이다.
- Alias page: Aliased page란 VA를 통해서 한번 Wrap된 페이지를 말한다. MAP_SHARED를 통해서 Aliased page를 만들도록 하였다. 각각의 page들은 원래 VA (Canonical page)를 가르키는 포인터를 Padding에 저장한다. 이 페이지를 만들기 위해서 mremap을 사용하였으며, free시에는 mprotect(PROT_NONE)을 통해서 free하였다.
Oscar Design
나이브 솔루션은 VM_AREA_STRUCTURE Explosion문제, To many system call 그리고 Fork를 허용하지 않는 문제가 발생하였다. 이를 해결하기 위해서 Oscar은 다음과 같은 솔류션을 제시하였다.
- High water mark: mremap을 통해서 anonymous하게 shadow page를 만드는 것이 아니라 우선 큰 영역을 mmap으로 잡아두고, high water mark를 계속해서 증가시키며 memory를 mremap으로 명시적으로 제공하였다. 이후 사용하지 않는 영역은 mprotect가 아니라 munmap으로 날리는 방식을 채택하였다. 이 문제는 vm_area_struct의 한계를 극복하기 위한 방법으로 제공되었다.
- Refershing shadows: 최근에 할당된 메모리의 크기는 free된 뒤에도 또 사용될 확율이 높다. 이를 Oscar에서는 speculative하게 할당하는 방식으로 shadow page를 할당하게 하도록 하였다. 이는 mremap한번의 사용으로 free와 alloc을 하게 해서 시스템 콜의 개수를 줄이는데도 도움이 되었다.
- MAP_PRIVATE: 큰 오브젝트와 같은 경우에는 MAP_SHARED를 사용하는 코스트가 크기 때문에 MAP_PRIVATE로 할당하고 나중에 realloc시에 content를 copy하였다.
- Supporting fork: MAP_SHARED를 사용할 경우에는 Fork를 제공할 수 없다. Socar는 fork시에 fork명령어를 hooking해서 모든 MAP_SHARED contents를 copy하는 방식으로 구현하였다.
Evaluation
- 대략 80%에 대한 메모리 오버헤드와 최대 350%정도 되는 오베헤드는 피할 수 없었다.
Conclusion
여러 구현상, 디자인 상의 한계가 있지만 후에 FFMALLOC, DangZero와 같은 여러 One time allocator의 다지인에 영향을 주었다.