Понимание Buddy Allocator

Question

У меня есть концептуальное сомнение в понимании того, как Linux Kernel управляет свободными блоками. Вот что я прочитал до сих пор. Реализация Buddy Allocator - это схема распределения, которая сочетает в себе нормальное распределение мощности-2. Иногда, когда нам нужен блок размера, который недоступен, он делит большой блок на два. Эти два блока - это друзья, вероятно, поэтому он называется Бадди-Алокатор. Через источник я узнал, что для каждого порядка поддерживается массив из 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 выглядит как растровое изображение, представляющее состояние пары приятелей.

Мой вопрос: Как это может быть однобитовый, который содержит бит состояния для пары друзей? Потому что, если, я использую один из блоков в папке Buddy-pair для allocats, а другой - свободный, каково было бы состояние тогда, и как это удалось сохранить в одном бите? Означает ли он весь блок размера power-of-two, который можно разделить на две части, когда нам нужен размер блока, который недоступен, поэтому выделенная половина равна Buddy другой половины, которая является бесплатной? Если это так, что половина выделяется, а половина остается свободной, то каков будет статус map? Что делать, если они свободны? и что, если оба выделены? Как может быть двоичное значение, представляющее 3 состояния блока?

Редактировать: После дальнейшего чтения первое сомнение очищается. Который говорит: если свободный код не может быть найден запрошенного заказа, блок более высокого порядка разделен на двух приятелей. Один выделяется, а другой помещается в свободный список для нижнего порядка. Поэтому он связан списком бесплатных страниц.

Answer 1

map представляет состояние одного блока памяти на самом нижнем уровне.