轻量级C通用库Klib解读 —— kalloc

前言

Klib是一个独立的轻量级c通用库，里面大多数组件除了C标准库外不包含外部库，想用对应组件直接拷贝对应文件即可使用。
该库致力于高效和较小的内存占用，其中部分组件（如khash、kbtree、ksort、kvec），无论是内存还是速度方面，都是所有编程语言中相似算法或数据结构最高效的实现之一。

kalloc

源代码在这里，还有对应的.c文件
这是一个内存管理模块，可以实现类似操作系统那样“当你申请一小块内存时就从可用的大内存块里分一部分给你”的效果
整个模块分为两部分：

1. 底层的内存块管理及其API
2. 利用内存块管理的一个小内存池

内存块管理：void *km

数据结构主体

kmem_t：隐藏的主体结构，接口里的void *基本都是它，负责管理内存块
内存中连续的比较大的一块内存，代码中叫做core
申请与分配内存块时基本是按照header_t大小的整数倍去处理的，所以把sizeof(header_t)叫做一个内存单元unit

typedef struct header_t {size_t size;struct header_t *ptr;
} header_t;typedef struct {void *par;size_t min_core_size;header_t base, *loop_head, *core_head; /* base is a zero-sized block always kept in the loop */
} kmem_t;

• header_t：内存块使用的链表基础结构
  • size：内存块大小（单位为unit）
  • ptr：指向下一块内存
• kmem_t：包含一个带头节点的单向循环loop链表(记录内存块中的可用内存块的信息)，和一个单向不循环core链表(记录整体内存块信息)
  • par：父指针(parent)，可指向另一个kmem_t结构。如果不为空则申请内存时是在父结构的内存块中申请内存给自己使用，释放内存时归还给父结构
  • min_core_size：最小core大小，默认为2¹⁹=512k（单位为unit）
  • base：loop链表的头节点，大小size永远为0，永远在loop链表中
  • loop_head：loop链表头指针
  • core_head：core链表头指针（总是指向最新申请的core）

注：上图为内存结构示意图，假设sizeof(size_t) = 4, sizeof(header_t) = 8
橙黄色箭头表示单向不循环的core链表，浅蓝色箭头表示单向循环的loop链表，红色箭头表示两次调用kmalloc申请内存返回的内存地址

• 每个core的头sizeof(header_t)字节用来存放core_head节点信息，所以实际能用的内存比设置的min_core_size整数倍要少
• 每次用kmalloc等接口申请内存时，实际申请出来的内存会比要求的内存大一点（具体见kmalloc代码第7行），这是为了在头sizeof(size_t)字节存储该块的大小，方便以后kfree的时候进行计算（kfree代码第7、8行就是把p设置为这段内存真正的起始位置并获取大小）

API接口

初始化/销毁：km_init、km_destroy

申请

malloc：kmalloc系列

kmalloc：最核心的申请内存接口
申请步骤：

• km为空则直接malloc申请对应大小的内存
• 否则尝试从当前内存块链表中取满足大小的内存块出来
  • 先计算申请的内存块大小相当于多少个unit：n_units
  • 循环loop链表，尝试找到一个满足目标大小的节点p->size >= n_units
    • 如果找得到且大小刚好符合，直接把该节点取出来，更新loop_head并返回
    • 如果找得到且大小比较大，则把该节点的后半部分取出来，更新loop_head并返回
    • 如果找不到，则需要调用morecore新增一个core，再从新的core部分取目标大小出来

void *kmalloc(void *_km, size_t n_bytes) {kmem_t *km = (kmem_t*)_km;size_t n_units;header_t *p, *q;...if (km == NULL) return malloc(n_bytes);n_units = (n_bytes + sizeof(size_t) + sizeof(header_t) - 1) / sizeof(header_t); /* header+n_bytes requires at least this number of units */if (!(q = km->loop_head)) /* the first time when kmalloc() is called, intialize it */q = km->loop_head = km->base.ptr = &km->base;for (p = q->ptr;; q = p, p = p->ptr) { /* search for a suitable block */if (p->size >= n_units) { /* p->size if the size of current block. This line means the current block is large enough. */if (p->size == n_units) q->ptr = p->ptr; /* no need to split the block */else { /* split the block. NB: memory is allocated at the end of the block! */p->size -= n_units; /* reduce the size of the free block */p += p->size; /* p points to the allocated block */*(size_t*)p = n_units; /* set the size */}km->loop_head = q; /* set the end of chain */return (size_t*)p + 1;}if (p == km->loop_head) { /* then ask for more "cores" */if ((p = morecore(km, n_units)) == 0) return 0;}}
}

Kmalloc、KMALLOC：都是调用kmalloc，一个指定类型，一个传入指针即可

#define Kmalloc(km, type, cnt)       ((type*)kmalloc((km), (cnt) * sizeof(type)))
#define KMALLOC(km, ptr, len) ((ptr) = (__typeof__(ptr))kmalloc((km), (len) * sizeof(*(ptr))))

新申请一个core

申请步骤：

• 计算目标大小占用unit数nu，换算到整数个min_core_size上
• 从父结构那里申请对应大小的内存bytes（如果父结构为空则直接malloc）
• 把新core插入到core链表头部
• 调用kfree初始化新core，把它加入到loop链表中，并返回loop_head

static header_t *morecore(kmem_t *km, size_t nu)
{header_t *q;size_t bytes, *p;nu = (nu + 1 + (km->min_core_size - 1)) / km->min_core_size * km->min_core_size; /* the first +1 for core header */bytes = nu * sizeof(header_t);q = (header_t*)kmalloc(km->par, bytes);if (!q) panic("[morecore] insufficient memory");q->ptr = km->core_head, q->size = nu, km->core_head = q;p = (size_t*)(q + 1);*p = nu - 1; /* the size of the free block; -1 because the first unit is used for the core header */kfree(km, p + 1); /* initialize the new "core"; NB: the core header is not looped. */return km->loop_head;
}

calloc：kcalloc系列

• kcalloc：根据情况选用calloc或kmalloc
• Kcalloc、KCALLOC：都是调用kcalloc

void *kcalloc(void *_km, size_t count, size_t size) {...if (km == NULL) return calloc(count, size);p = kmalloc(km, count * size);memset(p, 0, count * size);return p;
}#define Kcalloc(km, type, cnt)       ((type*)kcalloc((km), (cnt), sizeof(type)))
#define KCALLOC(km, ptr, len) ((ptr) = (__typeof__(ptr))kcalloc((km), (len), sizeof(*(ptr))))

realloc：krealloc系列

• krealloc：根据情况选用realloc或kmalloc。如果容量剩余空间比较大则直接返回，否则重新申请一块区域并拷贝数据，然后释放原位置
• Krealloc、KREALLOC：都是调用krealloc

void *krealloc(void *_km, void *ap, size_t n_bytes) { // TODO: this can be made more efficient in principle...if (km == NULL) return realloc(ap, n_bytes);if (ap == NULL) return kmalloc(km, n_bytes);...if (cap >= n_bytes) return ap; /* TODO: this prevents shrinking */q = (size_t*)kmalloc(km, n_bytes);memcpy(q, ap, cap);kfree(km, ap);return q;
}#define Krealloc(km, type, ptr, cnt) ((type*)krealloc((km), (ptr), (cnt) * sizeof(type)))
#define KREALLOC(km, ptr, len) ((ptr) = (__typeof__(ptr))krealloc((km), (ptr), (len) * sizeof(*(ptr))))

krelocate

就是重新找块区域放置数据，可用于内存比较碎片化时整理内存

void *krelocate(void *km, void *ap, size_t n_bytes) {...p = kmalloc(km, n_bytes);memcpy(p, ap, n_bytes);kfree(km, ap);return p;
}

expand：Kexpand系列

调用krealloc，按1.5倍的增长趋势扩大内存块

#define Kexpand(km, type, a, m) do { \(m) = (m) >= 4? (m) + ((m)>>1) : 16; \(a) = Krealloc(km, type, (a), (m)); \} while (0)#define KEXPAND(km, a, m) do { \(m) = (m) >= 4? (m) + ((m)>>1) : 16; \KREALLOC((km), (a), (m)); \} while (0)

释放：kfree

用于把一块“外部内存块”加入当前loop链表

释放过程：

• km为空则表示直接释放对应内存
• p指向要释放的内存块头信息的位置
• 尝试找到应该插入的位置q，根据p与q的位置关系判断其情况，进行合并
  • 下面的注释中显示了五种情况，源代码中只有四种情况的图示（p与q或q->ptr相邻可以整合的），我加了第三种p与两边都不相邻的图示

void kfree(void *_km, void *ap) { /* kfree() also adds a new core to the circular list */...if (km == NULL) {free(ap);return;}p = (header_t*)((size_t*)ap - 1);p->size = *((size_t*)ap - 1);/* Find the pointer that points to the block to be freed. The following loop can stop on two conditions:** a) "p>q && p<q->ptr": @------#++++++++#+++++++@-------    @---------------#+++++++@-------*    (can also be in    |      |                |        => |                       |*     two cores)        q      p           q->ptr           q                       q->ptr**                       @--------    #+++++++++@--------    @--------    @------------------*                       |            |         |         => |            |*                       q            p    q->ptr            q            q->ptr**                       @-----#++++++#++++++#++++@------    @-----#++++++@------#++++@------*                       |            |           |       => |            |           |*                       q            p      q->ptr          q            q->ptr      q->ptr->ptr** b) "q>=q->ptr && (p>q || p<q->ptr)": * 						 @-------#+++++   @--------#+++++++     @-------#+++++   @----------------*                       |                |        |         => |                |*                  q->ptr                q        p       q->ptr                q**                       #+++++++@-----   #++++++++@-------     @-------------   #++++++++@-------*                       |       |                 |         => |                         |*                       p     q->ptr              q       q->ptr                         q*/for (q = km->loop_head; !(p > q && p < q->ptr); q = q->ptr)if (q >= q->ptr && (p > q || p < q->ptr)) break;if (p + p->size == q->ptr) { /* two adjacent blocks, merge p and q->ptr (the 2nd and 5th cases) */p->size += q->ptr->size;p->ptr = q->ptr->ptr;} else if (p + p->size > q->ptr && q->ptr >= p) { /* this should not happen */panic("[kfree] The end of the allocated block enters a free block.");} else p->ptr = q->ptr; /* backup q->ptr (the 3rd case) */if (q + q->size == p) { /* two adjacent blocks, merge q and p (the 1st and 4th cases) */q->size += p->size;q->ptr = p->ptr;km->loop_head = q;} else if (q + q->size > p && p >= q) { /* this should not happen */panic("[kfree] The end of a free block enters the allocated block.");} else km->loop_head = p, q->ptr = p; /* in two cores, cannot be merged; create a new block in the list */

内存池

数据结构主体

还记得klist模块的小内存池吗？这个跟那个是一样的，用数组模拟栈操作，就只是用上面的内存块管理模块替换了直接申请内存操作

#define KALLOC_POOL_INIT2(SCOPE, name, kmptype_t) \typedef struct { \size_t cnt, n, max; \kmptype_t **buf; \void *km; \} kmp_##name##_t; ...#define KALLOC_POOL_INIT(name, kmptype_t) \KALLOC_POOL_INIT2(static inline klib_unused, name, kmptype_t)

• kmp_##name##_t：内存池结构
  • cnt：给外部使用的内存块个数
  • n：目前内存池中可用的内存块个数
  • max：内存池容量
  • buf：内存池
  • km：内存块管理结构体指针
• KALLOC_POOL_INIT：定义内存池宏
  • name：用户自定义名字（大小写字母下划线数字等）
  • kmptype_t：内存池管理的数据类型

初始化/销毁：kmp_init_name、kmp_destroy_name

申请/释放：kmp_alloc_name、kmp_free_name

kmp_alloc_##name：没有可用的内存块就用kcalloc申请，有则直接返回“栈顶”内存块（出栈）
kmp_free_##name：内存池容量已满就用Kexpand扩容，然后把内存块放到“栈顶”（入栈）

#define KALLOC_POOL_INIT2(SCOPE, name, kmptype_t) \...\SCOPE kmptype_t *kmp_alloc_##name(kmp_##name##_t *mp) { \++mp->cnt; \if (mp->n == 0) return (kmptype_t*)kcalloc(mp->km, 1, sizeof(kmptype_t)); \return mp->buf[--mp->n]; \} \SCOPE void kmp_free_##name(kmp_##name##_t *mp, kmptype_t *p) { \--mp->cnt; \if (mp->n == mp->max) Kexpand(mp->km, kmptype_t*, mp->buf, mp->max); \mp->buf[mp->n++] = p; \}