버디 할당 자 이해

Question

리눅스 커널이 자유 블록을 관리하는 방식을 이해하는데 개념적으로 의심 스럽습니다. 지금까지 내가 읽은 것을 통해 해석했다. Buddy Allocator 구현은 일반적인 2의 power-of-2 할당을 결합하는 할당 체계입니다. 사용할 수없는 크기의 블록이 필요할 때가되면 큰 블록을 두 개로 나눕니다. 그 두 블록은 친구입니다. 아마도 그것은 Buddy Allocator라고 불립니다. 소스를 통해 free_area_t 구조체 배열이 무료 인 페이지 블록의 링크 된 목록을 가리키는 각 순서에 대해 유지된다는 것을 알게되었습니다. 내가 <linux/mm.h>

typedef struct free_area_struct { 
    struct list_head free_list; 
    unsigned long *map; 
} free_area_t; 

free_list 표시에서 발견 페이지 블록의 연결 목록이 될? 내 질문은 그것이 무료 페이지 또는 사용 된 페이지 목록인지 여부입니다.

그리고 map은 한 쌍의 친구 상태를 나타내는 비트 맵처럼 보입니다.

내 질문은 어떻게 한 쌍의 상태 비트를 보유하는 단일 비트 수 있습니까? 왜냐하면 만약 내가 하나의 블록을 버디 - 페어에 할당하고 다른 하나는 자유롭게 남겨두면 그 상태는 어떻게 될 것이고 어떻게 그 비트를 단일 비트에 저장할 수 있을까요? 블록 크기가 필요할 때 두 부분으로 나눌 수있는 2의 거듭 제곱의 전체 블록을 나타내므로 할당 된 절반은 나머지 절반의 버디은 무료입니다. 절반이 할당되고 절반이 무료 인 경우라면 map의 상태는 무엇입니까? 둘 다 무료라면? 둘 다 할당되면 어떻게 될까요? 블록의 3 가지 상태를 나타내는 이진 값은 어떻게 될 수 있습니까?

편집 : 추가 읽기 후에 첫 번째 의심이 제거됩니다. 어떤 말 : 요청 된 주문에서 무료 블록을 찾을 수없는 경우 상위 주문 블록 이 두 명의 친구로 분할됩니다. 하나는 할당되고 다른 하나는 낮은 순서 에 대한 무료 목록에 배치됩니다. 그래서 그것은 자유 페이지의 링크 된 목록입니다.

Answer 1

map은 최하위 레벨에있는 단일 메모리 블록의 상태를 나타냅니다.