一个典型的 buddy system. 代码在env/env_alloc.c
数据结构:
ALLOC_LAYOUT: 管理整块内存(即bdb的某个region)的 数据结构. 放于此内存 开头位置.
SH_TAILQ_HEAD(__addrq) addrq; // address queue. 按地址排序. 用于内存块 的分裂和 合并. 所有的内存块 都会放入address queue中.
#define DB_SIZE_Q_COUNT 11
SIZEQ_HEAD sizeq[DB_SIZE_Q_COUNT]; // size queue. 用于快速查找可用内存. 11个queue, 从1024字节 到 1M.
// 每个queue中 的内存块 按长度 从大到小 排序. size queue中放的是 当前没有使用的内存.
ALLOC_ELEMENT: 放于每一个内存块的开头
SH_TAILQ_ENTRY addrq; // 其在address queue中的entry
SH_TAILQ_ENTRY sizeq; // 其在size queue中的entry
uintmax_t len; // 此内存块 总的长度
uintmax_t ulen; // 用户可用的长度
// 仅当 剩余内存(空闲内存块大小 - 用户需要的大小) 大于 SHALLOC_FRAGMENT, 做内存分割
#define SHALLOC_FRAGMENT (sizeof(ALLOC_ELEMENT) + 64)
// 对指定的内存大小len, q返回对应的 size queue. head指向当前region的 ALLOC_LAYOUT.
#define SET_QUEUE_FOR_SIZE(head, q, i, len) do { \
for (i = 0; i < DB_SIZE_Q_COUNT; ++i) { \
q = &(head)->sizeq[i]; \
if ((len) <= (u_int64_t)1024 << i) \
break; \
} \
} while (0)
// 一个ALLOC_ELEMENT 占用的内存大小. 需做对齐
#define DB_ALLOC_SIZE(len) \
(size_t)DB_ALIGN((len) + sizeof(ALLOC_ELEMENT), sizeof(uintmax_t))初始化, __env_alloc_init():
REGINFO->head为 ALLOC_LAYOUT. 初始化其 address queue, size queue.
剩下的内存 初始化为 一个 ALLOC_ELEMENT, 放入address queue 和 sizeq[DB_SIZE_Q_COUNT - 1]
note: 有可能 region 初始化大小 不足1M, 放入sizeq[DB_SIZE_Q_COUNT - 1] 没有关系, 次分配内存 会把其放入 合适的size queue.
分配内存, __env_alloc():
基于 堆的内存分配(malloc), 这里不讨论.
head = infop->head; // 此region的ALLOC_LAYOUT对象 total_len = DB_ALLOC_SIZE(len); // 需分配的内存大小 SET_QUEUE_FOR_SIZE(head, q, i, total_len); // 找到对应的size queue for (elp = NULL;; ++q) { // 若在当前size queue没找到, 则去 更大的size queue里找 SH_TAILQ_FOREACH(elp_tmp, q, sizeq, __alloc_element) { // 遍历当前size queue if (elp_tmp->len < total_len) // size queue中元素从大到小排序. 若当前元素不够大, 则后面的肯定也不够 break; elp = elp_tmp; // 此内存块满足条件. 缓存此ALLOC_ELEMENT.若有更合适的, 则elp会被重新赋值. if (elp_tmp->len - total_len <= SHALLOC_FRAGMENT) // 使用当前内存块, 若无需分割. 确保找到大小刚好合适的 free内存(没法再小了, 或无须分割) break; } if (elp != NULL || ++i >= DB_SIZE_Q_COUNT) // 在当前queue中找到; 或者查完所有size queue都未找到. break; } if (elp == NULL) { // 查完所有size queue未找到合适内存的情况 ... // 如果可以, extend当前region内存块, retry. 否则 退出. }
// 下面是已经找到合适内存的情况 SH_TAILQ_REMOVE(q, elp, sizeq, __alloc_element); // 将其从 对应的size queue 移除. if (elp->len - total_len > SHALLOC_FRAGMENT) { // 需要做内存分割 frag = (ALLOC_ELEMENT *)((u_int8_t *)elp + total_len); // 分割后的新内存块 frag->len = elp->len - total_len; frag->ulen = ; elp->len = total_len; // 原内存块缩小了 SH_TAILQ_INSERT_AFTER( // 分割得到的新内存块正好 放入 原内存块的address queue之后. &head->addrq, elp, frag, addrq, __alloc_element); __env_size_insert(head, frag); // 新内存块 放入size queue } p = (u_int8_t *)elp + sizeof(ALLOC_ELEMENT); elp->ulen = len; // elp为返回给用户的内存块
释放内存, __env_alloc_free():
head = infop->head; // 此region的ALLOC_LAYOUT对象 p = ptr; elp = (ALLOC_ELEMENT *)(p - sizeof(ALLOC_ELEMENT)); // 得到需要释放内存的ALLOC_ELEMENT对象 elp->ulen = ; // ulen为0, 表示此内存不再使用 // address queue中元素按 其 地址排序. if ((elp_tmp = SH_TAILQ_PREV(&head->addrq, elp, addrq, __alloc_element)) != NULL && // elp_tmp设为 此elp 在address queue之前的 元素 elp_tmp->ulen == && // 之前的元素 未被使用 (u_int8_t *)elp_tmp + elp_tmp->len == (u_int8_t *)elp) { // 且两段地址 相邻 SH_TAILQ_REMOVE(&head->addrq, elp, addrq, __alloc_element); // 把当前内存 和之前的内存 做合并. 当前内存块 移除 addrq SET_QUEUE_FOR_SIZE(head, q, i, elp_tmp->len); // 得到 之前元素所在 的size queue SH_TAILQ_REMOVE(q, elp_tmp, sizeq, __alloc_element); // 前面的内存块 移除 其对应的 size queue elp_tmp->len += elp->len; // 做合并 elp = elp_tmp; // elp 指向 合并后的内存地址 } if ((elp_tmp = SH_TAILQ_NEXT(elp, addrq, __alloc_element)) != NULL && // elp_tmp设为 此elp 在adress queue之后的 元素 elp_tmp->ulen == && // 之后的元素 未被使用 (u_int8_t *)elp + elp->len == (u_int8_t *)elp_tmp) { // 且两段地址 相邻 SH_TAILQ_REMOVE(&head->addrq, elp_tmp, addrq, __alloc_element); // 把当前内存和 之后的内存 做合并.后面内存块移除addrq SET_QUEUE_FOR_SIZE(head, q, i, elp_tmp->len); // 得到之后元素 所在的size queue SH_TAILQ_REMOVE(q, elp_tmp, sizeq, __alloc_element); // 后面的内存块 移除 size queue elp->len += elp_tmp->len; // 做合并. elp 指向 合并后的内存地址 } __env_size_insert(head, elp); // 合并后的 内存块入 size queue
__env_size_insert(): 将某个 ALLOC_ELEMENT 插入其对应的 size queue中.
SET_QUEUE_FOR_SIZE(head, q, i, elp->len); // 找到其对应的size queue SH_TAILQ_FOREACH(elp_tmp, q, sizeq, __alloc_element) // 遍历此size queue if (elp->len >= elp_tmp->len) // size queue元素从大到小排序, elp大小位于 当前元素和前一个元素之间(前一个元素可能为空). 需要插入到当前elp_tmp之前 break; if (elp_tmp == NULL) SH_TAILQ_INSERT_TAIL(q, elp, sizeq); // elp插入队尾 else SH_TAILQ_INSERT_BEFORE(q, elp_tmp, elp, sizeq, __alloc_element); // elp插入到当前elp_tmp之前
注: env_alloc/env_alloc_free 都未加锁. 对其的调用需要 加相应region的锁.
来源 https://www.cnblogs.com/brayden/p/5221160.html
