本篇研究采用Bitmapped Allocation这种策略实现的bitmap_allocator分配器，这也是我找到的唯一一份该策略的实现，质量很高。多数代码都来自gnu5.3，选择这个版本是因为我机子上以前就安装的有，而且新版本中的实现也没有多大变化，只是不知从哪个版本开始free_list中的一些关键代码找不到了，所以我又找了较低的gnu3.4.5，从中摘出了这部分代码。

Bitmapped Allocation这种策略使用位数组来表示内存的使用情况，在bitmap_allocator中，使用1来表示内存未使用，使用0来表示内存已被占用。使用size_t(unsigned int)来表示一块bitmap，size_t占4bytes，也就是一个bitmap可以表示32块内存的使用情况。

如第一次分配内存的情况如图所示：

实现中，最低分配内存块数被定义为64块，所以需要2个bitmap来表示内存的使用情况。仅有bitmap还不够，因为它只能记录每块内存的使用情况，无法告诉你控制着多少内存，因此它还多用了4bytes来对使用情况进行计数。此外，它还专门记录了占用内存的总大小，位于首位。

一次填充内存池的块称为blocks，它表示用户可以实际使用的内存，对于用户来说，它也只能看到这部分内存。blocks加上bitmap和使用计数以及记录大小的总占用，称为一块super block，用于分配器自己用于管理内存。

_S_mem_blocks用于管理多个super blocks，free_list用于管理处于「全回收」状态的super blocks，它们其实都是一个简易版的vector容器。

__mini_vector

__mini_vector是std::vector的一个简化版，用于管理super block。那么为何不直接使用std::vector呢？因为其自身就是个分配器，是给容器用的，而自己却又要依赖于容器，这就陷入了循环依赖。所以分配器中若是需要使用容器，必须由自己实现。

既然是std::vector的简化版，那么其中实现自然也会很相似。它的定义如下：

templateclass __mini_vector{__mini_vector(const __mini_vector&);__mini_vector& operator=(const __mini_vector&);public:typedef _Tp value_type;typedef _Tp* pointer;typedef _Tp& reference;typedef const _Tp& const_reference;typedef size_t size_type;typedef ptrdiff_t difference_type;typedef pointer iterator;private:pointer _M_start;  // 表示目前使用空间的头pointer _M_finish;  // 表示目前使用空间的尾pointer _M_end_of_storage;  // 表示目前可用空间的尾// 返回目前可用空间大小size_type _M_space_left() const throw(){return _M_end_of_storage - _M_finish;}// 申请内存pointer allocate(size_type __n){return static_cast(::operator new(__n * sizeof(_Tp)));}// 释放内存void deallocate(pointer __p, size_type){::operator delete(__p);}public:__mini_vector(): _M_start(0), _M_finish(0), _M_end_of_storage(0) { }// 返回目前使用空间大小size_type size() const throw(){return _M_finish - _M_start;}iterator begin() const throw(){return this->_M_start;}iterator end() const throw(){return this->_M_finish;}// 返回最后一个元素reference back() const throw(){return *(this->end() - 1);}reference operator[](const size_type __pos) const throw(){return this->_M_start[__pos];}// 指定位置插入元素void insert(iterator __pos, const_reference __x);// 末尾插入元素void push_back(const_reference __x){if (this->_M_space_left()){*this->end() = __x;++this->_M_finish;}elsethis->insert(this->end(), __x);}// 删除末尾元素void pop_back() throw(){--this->_M_finish;}void erase(iterator __pos) throw();void clear() throw(){this->_M_finish = this->_M_start;}};

很简单，便不赘述。具体结构如图所示：

其中最关键的成员函数其实是插入函数和删除函数，它们的实现如下：

template  // 插入BPPairvoid __mini_vector<_tp>::insert(iterator __pos, const_reference __x){if (this->_M_space_left())  // 有剩余空间{size_type __to_move = this->_M_finish - __pos;  // 若pos是3，则to_move=3--M_finishiterator __dest = this->end();                  // dest=M_finishiterator __src = this->end() - 1;// src=M_finish-1++this->_M_finish;  // M_finish自增1while (__to_move)// 若是4次，则依次向后移动4次数据{*__dest = *__src;  // 数据移次向后移动一位--__dest; --__src; --__to_move;}*__pos = __x;  // 目标位置插入新数据}else  // 目前已经没有可用空间了，需要重新找一块更大的地方{size_type __new_size = this->size() ? this->size() * 2 : 1;  // 当前大小为0时，设为1；若不为0，则以2倍增长iterator __new_start = this->allocate(__new_size);  // 此处申请内存 最开始是1个BPPairiterator __first = this->begin();  // 当前指针头iterator __start = __new_start;  // 新申请内存的指针头while (__first != __pos)  // 挪窝（第一次这里都是0，所以不会执行）{*__start = *__first;   // start保存当前指针头中的值++__start; ++__first;  // 皆自增，直到first==pos}*__start = __x;  // 存放BPPair++__start;  // 再自增while (__first != this->end())  // 若理解此处，不要把上面的pos和this->end()做虚拟假设。{// 如：若从3处插入，那么就是先把3之前的移到新窝，添加好新元素之后，再把3之后的元素挪过来*__start = *__first;++__start; ++__first;}if (this->_M_start)  // 释放旧窝this->deallocate(this->_M_start, this->size());this->_M_start = __new_start;  // M_start指向新窝头this->_M_finish = __start;     // M_finish指向新窝中刚加入BPPair的尾巴，或是挪过来元素的尾巴this->_M_end_of_storage = this->_M_start + __new_size;  // M_end_of_storage指向新窝尾}}// 删除元素templatevoid __mini_vector<_tp>::erase(iterator __pos) throw(){while (__pos + 1 != this->end())  // 若是最后一个元素，则直接删；{*__pos = __pos[1];  // 元素依次向前移动一个 __pos[1]==*(pos+1)++__pos;}--this->_M_finish;  // M_finish向后退一位}

可以看到，其实都和std::vector的实现差不多，此处便不着墨细论了，这里完全可以把它当成是vector，只是分配内存转变成了自己管理。

free_list

free_list在系统中的作用是管理处于「全回收」状态的_Block_pair，那么什么又是_Block_pair呢？它的声明如下：

typedef typename std::pair<_alloc_block _alloc_block>    _Block_pair;

可以看到它是一个std::pair类型的别名，具体类型为_Alloc_block*，_Alloc_block是一个结构体，定义如下：

struct _Alloc_block{// _BALLOC_ALIGN_BYTES为8，最小blocks的大小// 未使用大小char __M_unused[aligned_size::value];};

该结构体用于表示blocks的大小，也就是所申请单个内存块的大小，最小值为8。比如，创建一个int型的内存池，那么由于在32位系统上int占4个字节，所以此处的单个内存块大小就为8个字节。

再回来看_Block_pair，它的作用就是保存一整块blocks的头与尾。

弄懂了_Block_pair的结构，接着来看free_list，概览结构如下：

class free_list{public:typedef size_t*  value_type;typedef __detail::__mini_vector vector_type;  // 使用__mini_vector，相当于std::vectortypedef vector_type::iterator  iterator;typedef __mutex  __mutex_type;....};

这里主要是定义了一个vector_type，这个类型作为free_list的类型，真正的free_list是使用单例模式获取的：

vector_type& _M_get_free_list(){static vector_type _S_free_list;  // 单例模式，获取free_listreturn _S_free_list;}

当用户第一次申请内存时，会经历层层调用，最终就会到达free_list的get函数里，具体的处理如下：

// 从「全回收列表」中申请内存static unsigned int *_S_get_free_list(unsigned int __sz) throw (std::bad_alloc){// 找出第一个大于sz的区块_FLIter __temp = std::lower_bound(_S_free_list.begin(), _S_free_list.end(),__sz, _LT_pointer_compare());if (__temp == _S_free_list.end() || !_S_should_i_give(**__temp, __sz))  // 失败{//We hold the lock because the OOM_Handler is a stateless//entity._OOM_handler __set_handler(_BFL_type::_S_clear);unsigned int *__ret_val = reinterpret_cast(operator new (__sz + sizeof(unsigned int)));  // free_list中无法满足，使用new分配*__ret_val = __sz;  // 首位保存所申请区块的总大小return ++__ret_val;  // 返回第一位给用户}else  // free_list可以满足需求{unsigned int* __ret_val = *__temp;_S_free_list.erase(__temp);  // 从free_list中删除return ++__ret_val;}}

首先，该函数试图从free_list中查找一份刚好满足申请需求的super_block，保存到__temp。

若找到了符合条件的super_block，并且确定由其分配，那么将该super_block从free_list中移除，恢复使用。

若没有符合条件的super_block，或内存不该由其给予，那么他会先设置一个OOM_handler（具体作用，后面细说），接着使用operator new来真正的分配内存，最终返回内存给用户。

上面有两个函数未曾谈论，分别是_S_should_i_give和__set_handler，下面分别来论。

先说_S_should_i_give，作用是检查当前内存是否应该由其分配。诸位可能奇怪，既然已经从free_list中找到符合的内存的，那肯定可以给予分配，怎么还要判断一下呢？这就是实现者的严谨之处，具体通过代码来看，实现如下：

static bool _S_should_i_give(unsigned int __block_size, unsigned int __required_size) throw(){const unsigned int __max_wastage_percentage = 36;// 比如用户要申请一个120的内存，但我找到的内存量远大于它，我就不给它if (__block_size >= __required_size &&  // (剩余量 / 总量) * 100 

实现者在此处应该是根据自身经验，设立了一个最大浪费率标准为36%。当所申请内存的容量远小于所找到符合super_block的容量时，则会造成大量浪费，那么就不该由我分配。这个过程就好像小孩来找你要零花钱，你想着孩子太小不应该给太多的钱，那么你有10块，20块的可能就会直接给孩子；而发现只有100一张的时候，就觉得不应该给了。此处具体细节可参考代码和注释。

接着来看__set_handler。

当operator new无法满足用户所申请的内存时，便会采用__set_handler所设置的处理方式来进行处理。什么时候会出现这种情况呢？就是当系统也没有内存能满足你的时候，此时operator new内部所调用的malloc会失败。这种情况下operator new只能表示无能为力，唯有交给使用者来自己尝试释放一些内存，然后再重新申请，若释放之后满足需求则将内存返回给你，若依旧不满足，就只能返回0了。

这里分配器采取的处理方式是_S_clear，实现如下：

// 清空free_list，内存还给系统static void _S_clear(){_FLIter __iter = _S_free_list.begin();while (__iter != _S_free_list.end()){operator delete((void*)*__iter);++__iter;}_S_free_list.clear();}

这里直接将采取的做法是直接释放掉free_list中所有的内存，之后就可以系统就能满足需求了。

最后，还有一个重要的操作是往free_list中插入数据，即插入「全回收」状态的super blocks。

inline void _M_insert(size_t* __addr) throw(){// Call _M_validate to decide what should be done with// this particular free list.this->_M_validate(reinterpret_cast(__addr) - 1);  // 再减1就指向内存块大小了// See discussion as to why this is 1!}

调用该函数的位置可以在后面的释放内存处找到。__addr指向的位置其实是使用计数的位置，再减1则就为保存内存大小的位置。因为free_list中是按序排列的，所以会通过内存块的大小来进行比较。

具体细节，来看_M_validate的实现：

void _M_validate(size_t* __addr) throw(){vector_type& __free_list = _M_get_free_list();  // 获取free_listconst vector_type::size_type __max_size = 64;   // 最多装64个if (__free_list.size() >= __max_size)  // 已经装满了{// Ok, the threshold value has been reached.  We determine// which block to remove from the list of free blocks.if (*__addr >= *__free_list.back())  // 内存数大于最后一个{// Ok, the new block is greater than or equal to the// last block in the list of free blocks. We just free// the new block.::operator delete(static_cast(__addr));  // 大于末尾，则直接归还后返回return;}else{// Deallocate the last block in the list of free lists,// and insert the new one in its correct position.::operator delete(static_cast(__free_list.back()));  // 末尾大，归还末尾__free_list.pop_back();  // 删除最后一个}}// Just add the block to the list of free lists unconditionally.iterator __temp = __detail::__lower_bound  // 找出适当插入的位置(__free_list.begin(), __free_list.end(),*__addr, _LT_pointer_compare());// We may insert the new free list before _temp;__free_list.insert(__temp, __addr);  // addr插入到temp之前}

处理的流程是，看新归还的这个内存是否大于最末尾保存的内存大小，因为是按序排列的，所以最末尾的就是当前最大的内存块。若归还的这个内存块大于最末尾的内存块大小，则直接将其归还给系统。若所归还内存小于最末尾的内存，则要先找到合适的插入位置，即排序操作，它最多保存64个内存块，原因后面有所提及。若当前还未达到上限，就只是排序操作，若已经装满64个了，那么会先释放掉最末尾的内存，再进行排序。

bitmap_allocator

若从研究源码的角度来说，应该是以输出作为切入点来反编译作者的思路，这是一个「自下到上」的思维方式；而作者要实现这个功能，往往是一个「自上而下」的思维方式。待阅读完源码后，我们才能够和作者一样站在高处，俯瞰源码各个组件、各个层次之间的联系。所以这篇文章其实也是采用自上而下的思路写的，真正阅读源码时，若是直接从前面的那些组件开始阅读，我也会一脸懵逼，难以建立联系。正确的做法就是从bitmap_allocator开始研究，所以若对于前面的组件你还有些迷茫，那从这里开始就是一个逆向的思维来研究，再回头看前面的组件，便会豁然开朗。

每个标准内存分配器都必须提供一个allocate和deallocate接口，所以就可以从这里着手。

allocate的实现如下：

pointer allocate(size_type __n){if (__n > this->max_size())std::__throw_bad_alloc();if (__builtin_expect(__n == 1, true))  // 对于单个对象，由分配器处理return this->_M_allocate_single_object();else{// 多个对象，交由::operator newconst size_type __b = __n * sizeof(value_type);return reinterpret_cast(::operator new(__b));}}

内存分配器只用于处理单个对象，所以当传入多个对象时，就相当于直接调用了全局的operator new。

真正的设计是_M_allocate_single_object，接着来看该类的具体实现。

bitmap_allocator类的声明如下：

templateclass bitmap_allocator : private free_list // free_list登记的是全回收的

可以看到，它采用私有继承的形式继承自free_list，意味着它可以使用free_list的所有实现。

接着，直接找到分配内存动作的函数，代码较多，所以解释全部以注释的形式表达，如下：

// allocate的时候用这个pointer _M_allocate_single_object() throw(std::bad_alloc){// _S_last_request表示的是最后一次分配内存的位置，每次有分配请求，// 它不会从头遍历，而是先看需求是否和上一次相近，相近则从上一次分配的位置进行查找// 首次执行时第一个条件会不满足，所以直接跳过whilewhile (_S_last_request._M_finished() == false && (*(_S_last_request._M_get()) == 0))_S_last_request.operator++();// 首次执行时M_finished会比较返回true，所以此结果依旧不满足，直接跳过if (__builtin_expect(_S_last_request._M_finished() == true, false))  // 没找到有效区块，求助于First Fit method{// Fall Back to First Fit algorithm. // 退回使用最先匹配法则typedef typename __detail::_Ffit_finder<_alloc_block> _FFF;_FFF __fff;// 从_S_block_size中遍历出可用的blocks// __fff会指向该blocks中可用的bitmap_BPiter __bpi = _S_find(__detail::_Functor_Ref<_fff>(__fff));if (__bpi != _S_mem_blocks.end())  // 找到了有效的blocks{// Search was successful. Ok, now mark the first bit from// the right as 0, meaning Allocated. This bit is obtained// by calling _M_get() on __fff.// nz_bit表示从右起第几位为1，也就是有内存的那块size_t __nz_bit = _Bit_scan_forward(*__fff._M_get());  // fff.M_get()是可用bitmap的头__detail::__bit_allocate(__fff._M_get(), __nz_bit);  // 该位的内存将被使用，所以标记为0// 重置最后一次申请内存在_S_mem_blocks中的位置_S_last_request._M_reset(__bpi - _S_mem_blocks.begin());// Now, get the address of the bit we marked as allocated.// 返回给用户的内存// first + 偏移块（由bitmap决定，0就是0，1就是32） + 有效内存的位索引 即是要分配出去的那块内存pointer __ret = reinterpret_cast(__bpi->first + __fff._M_offset() + __nz_bit);// 找到使用计数的位置size_t* __puse_count =  reinterpret_cast(__bpi->first) - (__detail::__num_bitmaps(*__bpi) + 1);++(*__puse_count);  // 使用计数+1return __ret;  // 返回有效内存}else  // _S_mem_blocks中没有可用内存{// Search was unsuccessful. We Add more memory to the// pool by calling _S_refill_pool().// 填充内存池_S_refill_pool();// _M_Reset the _S_last_request structure to the first// free block's bit map.// 重置最后一次申请内存在_S_mem_blocks中的位置_S_last_request._M_reset(_S_mem_blocks.size() - 1);// Now, mark that bit as allocated.}}// _S_last_request holds a pointer to a valid bit map, that// points to a free block in memory.// nz_bit表示从右起第几位为1，也就是有内存的那块size_t __nz_bit = _Bit_scan_forward(*_S_last_request._M_get());  // 括号内首次为0，相当于_Bit_scan_forward(0);__detail::__bit_allocate(_S_last_request._M_get(), __nz_bit);  // 该位的内存将被使用，所以标记为0// 返回给用户的内存// M_base + 偏移块（由bitmap决定，0就是0，1就是32） + 有效内存的位索引 即是要分配出去的那块内存pointer __ret = reinterpret_cast(_S_last_request._M_base() + _S_last_request._M_offset() + __nz_bit);// 设置use_count的值// _M_start - (2 + 1) = use_countsize_t* __puse_count = reinterpret_cast(_S_mem_blocks[_S_last_request._M_where()].first)- (__detail::__num_bitmaps(_S_mem_blocks[_S_last_request._M_where()]) + 1);  ++(*__puse_count);  // 使用计数加1return __ret;}

简单地说，当用户申请内存时，它就从_S_mem_blocks寻找可用内存，找到了就直接返回给用户，没找到就重新填充内存池，再返回可用内存给用户。

_S_mem_blocks使用mini_vector来管理各个super_blocks，定义如下：

typedef typename std::pair<_alloc_block _alloc_block>    _Block_pair;typedef typename __detail::__mini_vector<_block_pair>_BPVector;static _BPVector _S_mem_blocks;  // 登记的是内存信息

_Block_pair在前面已经介绍过，下图可以帮助来理解这个过程：

它会记录最后一次分配内存的位置，下次分配时从该位置开始找起，这样查找的效率较高。当没有找到有效区块时，则表示本次请求和上次相差较大，此时退而其次，转而使用最先匹配法则来进行查找：

templatestatic _BPiter _S_find(_Predicate __p){// 遍历_S_mem_blocks_BPiter __first = _S_mem_blocks.begin();while (__first != _S_mem_blocks.end() && !__p(*__first))++__first;return __first;  // 返回有可用区块的bloks迭代器}

此时有两种可能，找到了或者依旧没找到。找到的情况下，首先设置bitmap标志，将这块内存由1（未使用）状态标记为0（已使用）状态，接着设置使用计数自增1，最后这个分配动作到此结束，返回可用内存给用户。

那么什么情况下会依旧没找到可用内存呢？第一种是首次使用，此时内存池并未填充；第二种是当前内存池已满，那么就需要重新填充内存池。

这两种操作都是使用_S_refill_pool()完成的，实现如下：

void _S_refill_pool() throw(std::bad_alloc){const size_t __num_bitmaps = (_S_block_size  // bits的个数/ size_t(__detail::bits_per_block));  // blocks=64 per_block=32 num_bitmaps=2const size_t __size_to_allocate = sizeof(size_t)  // 4 + 64 * Alloc_block + 2 * 4 如为int分配，则Alloc_block=8。+ _S_block_size * sizeof(_Alloc_block) // 4: use count; 64*Alloc_block: block size=512，也就是给用户用的+ __num_bitmaps * sizeof(size_t);  // 2 * 4: bitmap=8   sum=524// 从free_list中获取内存size_t* __temp =reinterpret_cast(this->_M_get(__size_to_allocate));  *__temp = 0;  // 第一位为use_count++__temp; // 移至第二位// The Header information goes at the Beginning of the Block._Block_pair __bp =std::make_pair(reinterpret_cast<_alloc_block>(__temp + __num_bitmaps),reinterpret_cast<_alloc_block>(__temp + __num_bitmaps)+ _S_block_size - 1);   // 单块blocks的头跟尾   // Fill the Vector with this information._S_mem_blocks.push_back(__bp);  // blocks存入_S_mem_blocks// bitmap的每一位初使值置1，表示未使用for (size_t __i = 0; __i (0); // 1 Indicates all Free._S_block_size *= 2;  // 成2倍增长，即64 128 256 512...}

这是比较重要的一个函数。

第一，它会计算出所需bitmap的个数。_S_block_size为blocks的个数，首次为64；bits_per_block表示单个bitmap所能标识的个数，一个size_t为4bytes，1byte占8bits，所以一个bitmap能表示32个内存块。因此首次需要2个bitmap。

第二，计算总共需要的内存大小。为64个blocks和2个bitmaps和一个use_count，所以第一个super_block的大小就为64*8+2*4+4=524。

第三，从free_list来获取内存，接着把第一位用来表示use_count，从第二位开始就是bitmap和blocks。首先它把blocks，也就是真正可以被用户使用的内存头和尾存入_S_mem_blocks中。接着把bitmap的每一位置1，表示未被使用。

最后，设置区块下次成长的大小，以2倍增长。

以上就是内存分配的所有动作，下面再来看释放动作。

同样先从deallocate入手，

void deallocate(pointer __p, size_type __n) throw(){if (__builtin_expect(__p != 0, true)){if (__builtin_expect(__n == 1, true))this->_M_deallocate_single_object(__p);else::operator delete(__p);}}

和分配动作相同，对于单个对象由其释放，多个对象直接调用operator delete释放。

我们跳到_M_deallocate_single_object来看：

// deallocate的时候用这个void _M_deallocate_single_object(pointer __p) throw(){_Alloc_block* __real_p = reinterpret_cast<_alloc_block>(__p);typedef typename _BPVector::iterator _Iterator;typedef typename _BPVector::difference_type _Difference_type;_Difference_type __diff;  // 就是个int __difflong __displacement;  // 偏移距离_GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);// 计算该块内存在blocks中的偏移// 同样会先从上次释放的位置进行查询// 若没有在上次释放的super_blocks中，// 则采用最先匹配法则从头检查__detail::_Inclusive_between<_alloc_block> __ibt(__real_p);if (__ibt(_S_mem_blocks[_S_last_dealloc_index]))  // 是否在上次释放的blocks内{_GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index(_S_mem_blocks[__diff].first) - 1;  // 第一个bitmap__bitmapC -= (__displacement / size_t(__detail::bits_per_block)); // 根据偏移的结果来移动的正确的bitmap，如34，则bitmap就应在第二个bitmap中__detail::__bit_free(__bitmapC, __rotate);  // 更改bitmap中的占用状态为0size_t* __puse_count = reinterpret_cast  // 找出use_count的位置(_S_mem_blocks[__diff].first)- (__detail::__num_bitmaps(_S_mem_blocks[__diff]) + 1);_GLIBCXX_DEBUG_ASSERT(*__puse_count != 0);--(*__puse_count);  // use_count也减1// use_count为0，说明达到了「全归还」状态。false是为了告诉编译器为false的可能性大if (__builtin_expect(*__puse_count == 0, false)) {_S_block_size /= 2;  // 下次分配大小减半// We can safely remove this block.// _Block_pair __bp = _S_mem_blocks[__diff];this->_M_insert(__puse_count);_S_mem_blocks.erase(_S_mem_blocks.begin() + __diff);  // 移除元素，_S_mem_blocks向前移动// Reset the _S_last_request variable to reflect the// erased block. We do this to protect future requests// after the last block has been removed from a particular// memory Chunk, which in turn has been returned to the// free list, and hence had been erased from the vector,// so the size of the vector gets reduced by 1.if ((_Difference_type)_S_last_request._M_where() >= __diff--)  // diff索引也要随着元素的移除减1_S_last_request._M_reset(__diff);// If the Index into the vector of the region of memory// that might hold the next address that will be passed to// deallocated may have been invalidated due to the above// erase procedure being called on the vector, hence we// try to restore this invariant too.if (_S_last_dealloc_index >= _S_mem_blocks.size()){_S_last_dealloc_index = (__diff != -1 ? __diff : 0);_GLIBCXX_DEBUG_ASSERT(_S_last_dealloc_index >= 0);}}}

注释已经解释的很清楚了，在此便稍作些补充。

释放操作的思路就是先找到归还内存的位置，也就是说它在哪块super_block中，然后找到它相对于blocks的偏移量，比如归还的内存处于第一块super_block中，归还的内存为第31块，那么偏移量就为31，偏移量（displacement）的表示如图所示：

归还的时候要对「全归还」状态的内存块进行特殊处理，将其加入到free_list中。这样下次再遇到重新填充内存池的情况，就会先从free_list中重新取用这块内存。这个步骤其实就是内存管理中的「延迟归还」。

按理说当一个内存块被全部归还后，就应该将这块内存归还给系统。因为一个内存管理系统要想持续运行，必须要有流入量和流出量，内存池这个存量若是只有流入量，由于系统的内存是一定的，那么这个内存管理系统终将走向死亡。要想可持续发展，必须还要有流出量。

当一块内存被全部归还后，就应该将这部分归还给系统。但是由于现实中往往存在着时间延迟性，所以立即进行处理就不是个明智的选择了。比如：用户虽然此时将内存全部归还了，但稍后又需要大量申请，若一个分配器直接将内存归还给系统了，此时就又需要重新从系统申请内存，影响效率。

因此，一个较好的内存分配器，基本上都有「延迟归还」的特性。

但是延迟归还多少合适呢？这里采取的做法是最多保存64块，当大于64块时，检查当前归还的内存块是否是当前free_list中最大的内存，若是则直接释放。若不是最大的，则先将该块内存插入到合适的位置（按从小到大排列）然后释放最后一块内存。

这部分代码在free_list那部分，_M_validate()就是进行这个操作。

到此，这份bitmap分配器就分析完了，可以再通过这张图总体地回顾一下，组织一下思路：