bins 数组高效索引不同大小的内存块

bins数组是 ptmalloc2 的核心索引结构。它用一个一维数组通过巧妙的计算同时管理了Unsorted Bin、Small Bins和Large Bins。A. 数组布局在malloc_state结构体中bins被定义为一个包含NBINS * 2 - 2个元素的数组NBINS 128。为了高效管理它被逻辑上划分为以下几个部分索引区间 (逻辑)类型管理方式特点bins[0](逻辑)Unsorted Bin循环双向链表唯一一个不按大小分桶的“中转站”bins[1]未使用占位-保持索引对齐bins[2]至bins[63]Small Bins每个索引对应一个固定大小每个桶内的块大小完全相等bins[64]至bins[126]Large Bins每个索引对应一个大小范围每个桶内的块大小各不相同但都属于同一区间B. 索引算法如何从请求大小计算 bin 索引这是 ptmalloc2 最精妙的设计之一它完全依赖位运算和预计算表来实现 O(1) 的索引计算。Small Bin 索引计算SMALLBIN_WIDTH 16字节对于大小sz已包含 chunk 头且已对齐到 16 字节其 bin 索引为idx (sz / 16) - 1例如请求 32 字节sz 32idx (32/16) - 1 1对应bins[2]。因为每个 Small Bin 大小固定分配时直接取链表头部即可时间复杂度为O(1)。Large Bin 索引计算幂次区间映射Large Bins 的索引计算比较复杂它通过位运算将大小映射到 63 个桶中每个桶覆盖一个大小范围。算法核心是large_bin_index(sz)它通过__builtin_clz计算前导零等指令快速确定大小所在的“幂次区间”然后通过查表或位移得到精确索引。这种设计的巧妙之处在于利用二进制位运算将连续的大小值高效地映射到 63 个离散的区间上避免了复杂的比较和遍历。溢出桶NSMALLBINS超过 Small Bin 范围 1024字节的大小都会落入这个幂次区间映射的 Large Bin 中最后一个桶bins[126]用于管理所有非常大的块无上限。C. 双链表实现原理每个 bin 在数组中占据两个元素bins[2*i]和bins[2*i1]分别作为双向链表的fd前向指针和bk后向指针的哨兵节点。当链表为空时两个指针都指向自身bins[2*i] bins[2*i1]这是一个经典的环形链表设计。这种布局使得插入unlink和删除link操作的时间复杂度都是O(1)且无需额外分配哨兵节点。总结bins的索引效率来自于Small Bin 的除法映射和Large Bin 的位运算区间映射两者都将查找一个合适的空闲块的时间复杂度控制在了O(1)Large Bin 在最坏情况下需要遍历链表但遍历长度受限于桶的大小范围通常很短。