heap_allocator
1.0.0
이것은 제가 작업해온 취미 OS용으로 작성한 간단한 힙 할당자입니다. 나는 거의 조사하지 않고 이 할당자를 작성했으며 최대한 이해하기 쉽게 만들었습니다. 나는 이 저장소가 나처럼 OS 개발이 처음이거나 malloc 및 free와 같은 기능의 단순화된 버전을 보고 싶은 사람들에게 유용할 수 있다고 생각합니다.
힙과 연결 목록을 정의하는 두 개의 헤더 파일이 있습니다. 이 저장소를 컴파일하려면:
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
그러면 할당자의 데모가 실행되고 일부 정보가 인쇄됩니다.
이 힙을 초기화하려면 메모리 섹션을 제공해야 합니다. 이 저장소에서 해당 메모리는 malloc 에 의해 제공됩니다(예, 힙을 통해 힙 할당). OS 설정에서 일부 페이지는 매핑되어 힙에 제공되어야 합니다(한 가지 시나리오). heap_t 구조체의 bin에도 할당된 메모리가 필요합니다.
init_heap 함수가 호출되면 빈 힙 구조체(할당된 bin 포인터 포함)의 주소를 제공해야 합니다. 그런 다음 init_heap 함수는 헤더( node_t 구조체)와 바닥글( footer_t 구조체)이 있는 하나의 큰 청크를 생성합니다. 이 청크의 크기를 결정하기 위해 함수는 HEAP_INIT_SIZE 상수를 사용합니다. 힙이 끝나는 위치를 결정하기 위해 이것을 start 인수에 추가합니다.
각 메모리 청크에는 시작 부분에 노드 구조체가 있고 끝에 바닥글 구조체가 있습니다. 노드는 청크가 사용 가능한지 여부에 관계없이 크기와 이중 연결 목록(next 및 prev)에 사용되는 두 개의 포인터를 보유합니다. 바닥글 구조체는 단순히 헤더에 대한 포인터를 보유합니다(인접한 청크를 해제하는 동안 사용됨). 힙 끝에 있는 청크를 "와일더니스" 청크라고 합니다. 가장 큰 청크이며 최소 및 최대 크기는 heap.h에 정의되어 있습니다. 힙을 축소하고 확장하는 것은 이 황야 덩어리의 크기를 조정하는 것만큼 쉽습니다. 사용 가능한 메모리 청크는 "빈"에 저장됩니다. 각 빈은 실제로 비슷한 크기를 가진 이중으로 연결된 노드 목록입니다. 힙 구조는 정의된 수의 bin(heap.h의 BIN_COUNT )을 보유합니다. 청크를 배치할 bin을 결정하기 위해 청크의 크기는 get_bin_index 함수에 의해 bin 인덱스에 매핑됩니다. 이 일관된 비닝 기능은 정의된 방식으로 청크에 액세스하고 저장할 수 있도록 보장합니다. 청크는 bin에 삽입될 때 정렬되므로 청크 삽입은 O(1)이 아니지만 가장 적합한 청크를 찾는 것이 훨씬 쉽습니다. 비닝 기능은 이 힙의 사용자가 적합하다고 생각하는 대로 정의할 수 있습니다. 청크를 빠르게 검색하는 데 도움이 되도록 보다 정교한 비닝 기능을 결정하는 것이 유리할 수 있습니다.
heap_alloc 함수는 할당할 힙 구조체의 주소와 크기를 가져옵니다. 이 함수는 단순히 get_bin_index 사용하여 이 크기의 청크가 있어야 하는 위치를 결정합니다. 물론 해당 크기의 청크가 없을 수도 있습니다. 해당 빈에서 청크가 발견되지 않으면 다음 빈을 확인합니다. 이는 청크가 발견될 때까지 계속되거나 마지막 빈에 도달할 때까지 계속됩니다. 이 경우 황야 청크에서 메모리 조각을 가져옵니다. 발견된 청크가 충분히 크면 분할됩니다. 청크를 분할해야 하는지 결정하기 위해 현재 할당에서 사용하지 않는 양에서 메타데이터(오버헤드)의 양을 뺍니다. 남은 것이 MIN_ALLOC_SZ 보다 크거나 같으면 이 청크를 분할하고 남은 부분을 올바른 저장소에 넣어야 함을 의미합니다. 찾은 청크를 반환할 준비가 되면 next 필드의 주소를 가져와 반환합니다. 이는 청크가 할당되는 동안 next 및 prev 필드가 사용되지 않기 때문에 수행됩니다. 따라서 청크 사용자는 힙의 내부 작업에 영향을 주지 않고 이러한 필드에 데이터를 쓸 수 있습니다.
heap_free 함수는 heap_alloc 이 반환한 포인터를 사용합니다. 노드 구조체의 주소를 얻기 위해 올바른 오프셋을 뺍니다. 단순히 청크를 올바른 빈에 배치하는 대신 제공된 청크를 둘러싼 청크를 확인합니다. 이들 청크 중 하나라도 사용 가능하다면 더 큰 청크를 생성하기 위해 청크를 통합할 수 있습니다. 청크를 합치기 위해 바닥글을 사용하여 이전 청크의 노드 구조체와 다음 청크의 노드 구조체를 가져옵니다. 예를 들어 to_free 라는 청크가 있다고 가정해 보겠습니다. 이 청크 이전의 청크를 얻으려면 sizeof(footer_t) 빼서 이전 청크의 바닥글을 얻습니다. 바닥글은 이전 청크의 헤드에 대한 포인터를 보유합니다. 다음 청크를 얻으려면 to_free 의 바닥글을 얻은 다음 다음 청크를 얻기 위해 sizeof(footer_t) 추가하면 됩니다. 이 모든 작업이 완료되고 크기가 다시 계산되면 청크가 다시 저장소에 배치됩니다.
참고: 이 코드는 원래 32비트 시스템용으로 컴파일되었습니다. 이는 이 코드가 사용될 때 둘 다 동일한 크기이기 때문에 int를 포인터로 캐스팅하는 것이 허용되었음을 의미합니다. 64비트 시스템에서는 컴파일러가 크기 차이에 대해 경고합니다. 이러한 경고를 없애기 위해 unsigned int에서 포인터로 캐스팅할 때 uintptr_t 를 사용했습니다. 이로 인해 가독성이 약간 흐려지고 일부 캐스트 및 포인터 연산이 장황하므로 코드를 읽을 때 이를 염두에 두십시오.
