GNUC alloc

简介

• 前面自行设计的分配器, 在应用方面有比较大的局限性, GCC的编译器有一个比较全面的分配器, 原理就是上面的实现, 只不过内部做了更详细的划分

流程(先图形, 后文字)

36.png

37.png

39.png

40.png

41.png

42.png

43.png

44.png

45.png

46.png

47.png

• <font color=red>流程说明</font>

alloc_1(第1张图)是一个概述图

重要的结构:
    1. alloc有16条链(array[16])表来管理不同的区块的大小

    2. 每个区块是8的倍数(8, 16, 24, .... , 128)

    3. 内部维护了一个 pool, 作用是可分割的内存





基本工作流程:
    如果现在索取的内存大小是len

    0. 根据len找到是第idx链表表头head

    1. 如果head有值, 则直接将head指向的空间返回出去, head指向下一个

    2. 第1步不成立, 则看pool
        2.1 如果pool大小为0, 向 malloc要 chunk大小(chunk_mem), head指向chunk_mem
            > 然后从chunk中取一半出来按len大小切割, 做成链表
            > 返回链表的head给客户, head指向下1个
            > 剩下的一半被pool记录

        2.2 如果pool大小 > len
            > 取一部分出来做成链表, head指向链表
            > 返回head给客户, head指向下一个(可能为空)
            > 另一部分再被pool记录
            

        2.3 pool 有值但 < len
            > 将当前pool空间(大小是cache,一定是8的倍数)挂到cache对应的链表, 此时pool大小就为0了
            > 然后重复2.1


    ps:
        在这个过程中,在2.3中的第1小步, 是对碎片的处理, 但没有malloc失败的情况处理
        下面开始对上面的图做更细致的解说
        



变量:
    pool       大小
    start_free 指向pool的起始
    end_free   指向pool的结束
    total      已经向malloc申请的内存
    


alloc_2:
    申请32字节

    1. 由#3负责的链表

    2. #3为空, 并且pool为0, 所以pool向malloc索取:
        32 * 20 * 2 + RoundUp(total >> 4)(1280byte)

    3. 取出一半640, 为#3做成链表(切割成20份, 每份32字节)
        3.1 #3当前指向的空间返回给客户, #3指向下一个

    4. 另一半被pool记录(用start_free和end_free指向pool)

    ps: total:1280, pool:640





alloc_3:
    申请64字节

    1. 由#7负责的链表

    2. #7为空, 但pool有值(640)

    3. pool有值, 但 < 20*64
        3.1 pool最多可以被切割成64的10倍, 所以做成链表给#7
        3.2 #7指向的空间返回给客户, #7指向下一个

    ps: total:1280, pool:0
            
        




alloc_4:
    申请96字节

    1. 由#11负责的链表

    2. #11为空, 并且pool为空, 所以向malloc索取 96*20*2 + RoundUp(1280 >> 4)
    
    3. 取出 96*20 的空间做成链表给#11
        3.1 #11指向的空间给客户
        3.2 #11指向下一个
        3.3 其余的用pool记录

    ps: total:5200, pool:2000



 

alloc_5:
    申请88字节

    1. 由#10负责, #10为空, 但pool有值(2000)

    2. pool可以为88切割成20份:
        2.1 切割为20份给#10
        2.2 #10返回给客户, #10指向下一个
        2.3 剩下的由pool记录

    ps: total:5200, pool:240





alloc_6:
    申请3次88字节, 这个时候直接从#10取




alloc_7:
    申请8个字节

    1. 由#0负责, #0为空, 但pool有值

    2. pool中的大小足够切割为 8*20
        2.1 切割成20份给#0
        2.2 #0返回给客户, #0指向下一个
        2.3 剩余的由pool记录

    ps: total:5200, pool:80





alloc_8:
    申请104字节

    1. 由#12负责, #12为空, 但pool有值

    2. pool(80) < 104, 所以:
        2.1 将pool中的80的空间挂到对应的#9
        2.2 向malloc索取 104*20*2 + RoundUp(5200>>4)
        2.3 取出新获得的内存中104*20做成链表给#12
        2.4 #12返回给客户, #12指向下一个
        2.5 其余的由pool记录

    ps: total:9688, pool:2408






alloc_9:
    申请112字节

    1. #13负责, #13为空, 但pool有值

    2. 取出pool中112*20大小的空间,做成链表给#13
        2.1 #13返回给客户, #13指向下一个
        2.2 其余pool记录

    ps: total:9688, pool:168







alloc_10
    申请48字节

    1. 由#5负责, #5为空, 但pool有值

    2. pool最多加被切割成3*48,做成链表给#5
        2.1 #5返回给客户, #5指向下一个
        2.2 其余pool记录
        
    ps: total:9688, pool:24





alloc_11:
    申请72字节

    1. 由#8负责, #8为空, pool有值

    2. pool(24) < 72, 所以:
        2.1 将pool的24大小的空间做成链表, 并挂到对应的#2中
        2.2 向malloc索取(72*20*2 + roundUp(9688>>4))    
            由于测试最边界, 所以设置了索取最大值为10000
        2.3 malloc失败, 于是从#8往后找, 发现#9(80字节)链表有值:
            > 从#9取出第1块的80字节
            > #9指向下一个
            > 取出的80字最多能切割成 72*1, 切好后给#8
            > #8返回客户, #8指向下一个
            > 剩余的由pool记录

    ps: total:9688, pool:8



后续的过程也是如此:
    1.先看对应的链表

    2. 再看pool, 根据情况处理碎片, malloc成功时处理, malloc失败处理等等


代码实现分3步
    第1步
        将16条链表的表头抽象成一个线程安全的类
            它的主要作用:
                1. 往外给head, head指向next
                2. 接收一段内存, 封装成链表
            ps:取值和封装成链表的过程是线程安全的

    第2步
        将上面图的pool抽取出来做成1个线程安全的类

    第3步
        实现内存池的逻辑

代码实现第1步(封装链表)

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<string>
#include<vector>
#include<atomic>
#include<thread>
using namespace std;


namespace lb {
/*
    常量
*/
    enum class _constant_{
        CHUNK       = 20,
        MAX         = 128,
        ALIGN_MIN   = 8,
        MIN         = 8,
        LIST_SIZE   = 16,
        _2          = 2
    };
#define C_CHUNK     ((int)      (_constant_::CHUNK))
#define C_MAX       ((int)      (_constant_::MAX))
#define C_ALIGN_MIN ((unsigned) (_constant_::ALIGN_MIN))
#define C_MIN       ((int)      (_constant_::MIN))
#define C_LIST_SIZE ((int)      (_constant_::LIST_SIZE))
#define C_2         ((int)      (_constant_::_2))







    

    template<size_t _Offset>
    struct _list_ : public _list_<_Offset - 1> {

        virtual _list_<_Offset>* operator++() {
            return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) + _Offset);
        }

        virtual _list_<_Offset>* operator--() {
            return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) - _Offset);
        }
    };


    template<> 
    struct _list_<0-1> {
        _list_<0>* next{};
    };


    

    constexpr size_t g_offset(size_t idx) {
        return (idx + 1) * C_ALIGN_MIN;
    }

    
    template<size_t _Idx, typename _Flag> struct _list_thread;

    template<> struct _list_thread<0-1,true_type> {
        atomic<_list_<0>*> head{};

        //析构是空的, 不可以释放内存
        ~_list_thread() {}
    };

    //线程安全
    template<size_t _Idx> 
    struct _list_thread<_Idx,true_type>: public _list_thread<_Idx-1,true_type>{
            
        //不包含end
        virtual void make_list(void* begin, void* end) {
            
#define _MAKE_LIST  // 将给过来的内存串成链表
        _MAKE_LIST{
            _list_<0>* record = reinterpret_cast<_list_<0>*>(begin);

            for (; record != end;) {

                /** 
                    必须调用 placement new, 将void*的空间初始化为对应的 _list_<_offset>
                    ps: 不能调用 _list_<0>的ctor, 因为 operator++ 是1个虚函数, 这里的目的是生成对应
                        的_list_<_offset>*, 而不同的_list_<_offset>的虚指针是不同的
                */
                new(record)_list_<g_offset(_Idx)>;

                record->next = this->head.load(memory_order_acquire);
                
                while (!this->head.compare_exchange_weak(record->next, record, memory_order_acq_rel));

                record = record->operator++();
            }
        }
#undef _MAKE_LIST
        }


        virtual void* get() {
            while (this->head.load()){
                auto result = this->head.load();

                while (!this->head.compare_exchange_weak(result, result->next, memory_order_acq_rel));

                return result;
            }

        }
    };
}



void test_main_thread() {
    lb::_list_thread<0, true_type>* p_a = new lb::_list_thread<0, true_type>;
    lb::_list_thread<0, true_type>* p_b = new lb::_list_thread<1, true_type>;

    auto mem = ::operator new(8 * 10);
    auto end = ((char*)mem) + 80;

    /**
        单线程不同大小 head-list 测试
    */
    p_a->make_list(mem, end);
    p_b->make_list(mem, end);
}

void test_multi_thread() {
    lb::_list_thread<0, true_type>* p_b = new lb::_list_thread<1, true_type>;

    auto lambda_ = [&p_b] {
        auto start = ::operator new(320);
        auto ended = ((char*)start) + 320;

        ostringstream buffer(std::ios_base::app);
        buffer << "thread: " << this_thread::get_id();
        buffer << endl;
        buffer << " malloc: \n";
        buffer << "{\n";
        for (char* i = (char*)start; i != ended; i += 16)
            buffer << "\t" << (void*)i << "\n";
        buffer << "}\n\n";
        cout << buffer.str();

        p_b->make_list(start, ended);
    };
    thread t_a(lambda_);
    thread t_b(lambda_);
    thread t_c(lambda_);
    thread t_d(lambda_);
    thread t_e(lambda_);

    t_a.join();
    t_b.join();
    t_c.join();
    t_d.join();
    t_e.join();
    for (auto i = p_b->head.load(); i; i = i->next)
        cout << "\t" << i << endl;

    cout << "\n***************test_multi_thread_get\n";

    auto mem_get = [&p_b]{
        ostringstream buffer(std::ios_base::app);
        while (1){
            auto m = p_b->get();
            buffer << "thread: " << this_thread::get_id();
            buffer << " ";
            buffer << "get memory: " << m << endl;
            cout << buffer.str();
            buffer.seekp(0);
            if (m == nullptr)
                break;
        }
    };
    thread f(mem_get);
    thread g(mem_get);
    thread h(mem_get);
    thread i(mem_get);

    f.join();
    g.join();
    h.join();
    i.join();

    cout << "\n***************交叉测试\n";
    {
        thread t_a(lambda_);
        thread t_b(lambda_);
        thread t_c(mem_get);
        thread t_d(mem_get);
        thread t_e(lambda_);
        thread t_f(lambda_);
        thread t_g(mem_get);
        thread t_h(lambda_);
        thread t_i(mem_get);


        t_a.join();
        t_b.join();
        t_c.join();
        t_d.join();
        t_e.join();
        t_f.join();
        t_g.join();
        t_h.join();
        t_i.join();
    }
    cout << "over\n";
}

int main(int arg, char** args) {
    {
        cout << "********_list_大小测试**********\n";
        cout << sizeof(lb::_list_<8>) << endl;
        cout << sizeof(lb::_list_<16>) << endl;
        cout << sizeof(lb::_list_<24>) << endl;
        cout << sizeof(lb::_list_<32>) << endl;
        cout << sizeof(lb::_list_<40>) << endl;

        cout << "\n\n********test_main_thread**********\n";
        test_main_thread();

        
        cout << "\n\n********test_multi_thread**********\n";
        test_multi_thread();
    }
    return 0;
}

第2步和第3步(分文件)

48.png

/** 
    pool_constant.h
*/
#ifndef _POOL_CONSTANT_H
#define _POOL_CONSTANT_H

namespace lb {
namespace _pool {
/*
    常量
*/
enum class _constant_ {
    CHUNK = 20,
    MAX = 128,
    ALIGN_MIN = 8,
    MIN = 8,
    LIST_SIZE = 16,
    _2 = 2
};
#define C_CHUNK     ((int)      (_constant_::CHUNK))
#define C_MAX       ((int)      (_constant_::MAX))
#define C_ALIGN_MIN ((unsigned) (_constant_::ALIGN_MIN))
#define C_MIN       ((int)      (_constant_::MIN))
#define C_LIST_SIZE ((int)      (_constant_::LIST_SIZE))
#define C_2         ((int)      (_constant_::_2))
#define ALLOC_NO_MEMORY -1
}
}
#endif











/** 
    pool_func.h
*/
#ifndef _POOL_FUNC_H
#define _POOL_FUNC_H
#include"pool_constant.h"
namespace lb {
namespace _pool {
    using namespace std;
    inline constexpr size_t g_offset(size_t idx) {
        return (idx + 1) * C_ALIGN_MIN;
    }
    size_t round_up(size_t len);
    size_t getidx(size_t unit);
}
}
#endif // !_POOL_FUNC_H

/** 
    pool_func.cpp
*/
#include"pool_func.h"

namespace lb {
namespace _pool {
    

    /** 
        上调为8的倍数, 其实原理很简单:
            一个数N
            当N + 7的后, 结果(result)一定是 >= 8的
            而在计算机中, 8的倍数的数字, 则一定是以 0b xxxx 000(3个0结尾的)
            所以result想再调整为8的倍数, 则result的第0,1,2的bit位应该设置为0
            但result的其他位不可以变, 则需要取一个 掩码(0b1111 1111 1111 1111 1111 1111 1111 1000)
            与result做&操作, 而掩码的值其实就是 ~7

            同理调整为16的倍数, 也是一样的道理
    */
    size_t round_up(size_t len) {
        return (len + C_ALIGN_MIN - 1) & ~(C_ALIGN_MIN - 1);
    }

    size_t getidx(size_t unit) {
        return unit / C_ALIGN_MIN - 1;
    }

    
}
}








/** 
    pool_head.hpp
    16条链表的表头对象
*/
#ifndef _POOL_HEAD_HPP
#define _POOL_HEAD_HPP
#include<atomic>
namespace lb {namespace _pool {
    using namespace std;

    template<size_t _Offset>struct _list_ : public _list_<_Offset - 1> {
        virtual _list_<_Offset>* operator++() {
            return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) + _Offset);
        }

        virtual _list_<_Offset>* operator--() {
            return reinterpret_cast<_list_<_Offset>*>(reinterpret_cast<char*>(this) - _Offset);
        }
    };

    template<>struct _list_<0 - 1> {
        _list_<0>* next{};
    };



    template<size_t _Idx, typename _Flag> struct _list_thread;

    template<> struct _list_thread<-1, true_type> {
        atomic<_list_<0>*> head{};
        ~_list_thread() {}
    };

    //线程安全
    template<size_t _Idx>
    struct _list_thread<_Idx, true_type> : public _list_thread<_Idx - 1, true_type> {

        //不包含end
        virtual void make_list(void* begin, void* end) {
            _list_<0>* record = reinterpret_cast<_list_<0>*>(begin);

            for (; record != end;) {
                new(record)_list_<g_offset(_Idx)>;

                record->next = this->head.load(memory_order_acquire);

                while (!this->head.compare_exchange_weak(record->next, record, memory_order_acq_rel));

                record = record->operator++();
            }
        }


        virtual void* get() {
            while (this->head.load()) {
                auto result = this->head.load();

                while (!this->head.compare_exchange_weak(result, result->next, memory_order_acq_rel));

                return result;
            }

        }
    };

}}

#endif // !_POOL_HEAD_HPP









/** 
    cache.h 负责缓存的类
    它不能回收外界的内存(由safe_pool回收), 因为cache的记录的内存必须是连续的
    而外界传过来的地址可能和当前cache中记录的地址的边界不是相邻的
*/
#ifndef _POOL_CACHE_H
#define _POOL_CACHE_H
#include<thread>
#include<sstream>
#include<iostream>
#include"pool_constant.h"
#include"pool_func.h"
#include"pool_head.hpp"

namespace lb {namespace _pool {
    using namespace std;
class cache{
public:
    void get(size_t unit, void** head_start = nullptr, void** head_ended = nullptr);
public:
    static size_t total;

    //start和ended的之间的内存必须是连续的
    static atomic<void*> start;
    static size_t byte;
};
}}

#endif // !_POOL_CACHE_H

/** 
    cache.cpp
*/
#include "cache.h"


#define _TEST_

namespace lb { namespace _pool {
    size_t cache::total{};
    size_t cache::byte{};
    atomic<void*> cache::start{};


    void cache::get(size_t unit, void** head_start, void** head_ended) {

        //start指向空, 表示没有cache   
        if (!start.load(memory_order_acquire)) {
            static atomic<bool> alloc_flag{};

            //this_thread::sleep_for()

            // 这里想malloc, 虽然是多线程, 但start此时已经指向空, 其他线程不可能在其他地方同时调整start这块内存
            /// 但可能有多个线程来这里malloc, 只允许同一时间内只有1个线程在malloc
            while (true) {
                if (alloc_flag.exchange(true, memory_order_acq_rel)) {
                    this_thread::yield();
                    continue;
                }

                // 后面进来的线程判断有没有cache
                if (start.load(memory_order_acquire)) {
                    alloc_flag.store(false, memory_order_release);
                    break;
                }

                size_t half = unit * C_CHUNK;
                size_t count = half * C_2 + round_up(total >> 3);

                void* malloc_mem = malloc(count);
#ifdef _TEST_
                //测试malloc失败的情况
                if (count > 3600) {
                    if (malloc_mem) {
                        free(malloc_mem);
                        malloc_mem = nullptr;
                    }
                }
#endif // _TEST_


                if (malloc_mem) {
                    char* cache_start = (char*)malloc_mem + half;

                    total += count;
                    byte = count - half;
                    start.store(cache_start, memory_order_release);

                    alloc_flag.store(false, memory_order_release);

                    *head_start = malloc_mem;
                    *head_ended = cache_start;
#ifdef _TEST_
                    ostringstream str(ios_base::app);
                    str << "malloc {\n";
                    static int __count = 0;
                    for (char* i = (char*)malloc_mem, *end = i + count; i != end; ++i) {
                        ++__count;
                    }
                    str << "\t" << __count << endl;
                    str << "}";
                    cout << str.str();
    
#endif // _TEST_

                return;
                }

                /// malloc失败, pool应该到header中的head去找内存
                alloc_flag.store(false, memory_order_release);
                *head_start = *head_ended = nullptr;
                return;
            }
            return get(unit, head_start, head_ended);
        }


        static atomic<bool> block_flag{};
        while (true) {
            if (block_flag.exchange(true, memory_order_acq_rel)) {
                this_thread::yield();
                continue;
            }
            if (byte == 0) {
                *head_start = nullptr;
                *head_ended = nullptr;
                block_flag.store(false, memory_order_release);
                //再去malloc
                return get(unit, head_start, head_ended);
            }

            //cache不够, 应该将内存给pool, 挂到对应的链表中
            if (byte < unit) {
                void* val = start;
                *head_start = val;
                *head_ended = (char*)val + byte;
                byte = 0;
                start = nullptr;

            }
            else {
                //cache足够, 划出最多20块的空间给外界的pool去处理
                void* val = start;
                *head_start = val;
                size_t block = byte / unit;
                *head_ended = (char*)val + (block > C_CHUNK ? (C_CHUNK * unit) : (block * unit));
                byte -= ((char*)*head_ended - *head_start);
                if (byte)
                    start = *head_ended;
                else
                    start = 0;
            }
            block_flag.store(false, memory_order_release);
            break;
        }
    }


}}







/** 
    pool.hpp
    提供给外界用的类
*/
#ifndef _POOL_HPP
#define _POOL_HPP
#include"cache.h"

#define _TEST_


namespace lb {
namespace _pool {
    using namespace std;

    template<typename _Bool_type>class pool {};

    class safe_pool : public pool<true_type> {
    private:
        using Header    = _list_thread<0, true_type>;
        using Header_p  = add_pointer<Header>::type;
        using Header_pp = add_pointer<Header_p>::type;


    public:
        void* alloc(size_t len) {
            if (len > C_MAX)
                return ::operator new(len);

            size_t unit = round_up(len);
            size_t idx = getidx(unit);

            auto tar_head = header[idx];

            auto result = tar_head->get();

            // 从链表中取到(线程安全)内存, 就直接返回
            if (result) return result;

            void* head_start = nullptr;
            void* head_ended = nullptr;
            memory.get(unit, &head_start, &head_ended);
            size_t get_mem = (char*)head_ended - head_start;

            // malloc失败, 以当前表头(head)为准, 依次往后面的head中找内存
            if (!head_start) {
                for (size_t i = idx, end = C_LIST_SIZE; ++i < end; ) {
                    auto next_head = header[i];
                    auto need = next_head->get();
                    
                    // 找到了, 先拿unit的大小出来给外界, 余下的挂载到对应序号的表头上
                    if (need) {
                        auto other_head_start = (char*)need + unit;
                        auto other_head_ended = (char*)need + ((i+1)*C_ALIGN_MIN);
                        header[(getidx(other_head_ended-other_head_start))]->make_list(other_head_start, other_head_ended);
                        return need;
                    }
                }

                // 没有找到, 抛异常
                //throw ALLOC_NO_MEMORY;
                return 0;

            }else {
                // 内存不足够, 先挂载到对应序号的链表中(get_mem一定是某个表头需要的大小), 再要内存
                if (get_mem < unit) {
                    header[getidx(get_mem)]->make_list(head_start, head_ended);
                    head_start = head_ended = nullptr;
                    memory.get(unit, &head_start, &head_ended);

                //内存足够(unit的整数倍), 先挂载到自己的链表上
                }else {
                    tar_head->make_list(head_start, head_ended);
                    head_start = head_ended = nullptr;
                }
            }

            return tar_head->get();
        }

        void dealloc(void* ptr, size_t len) {
            if (len > C_MAX) return ::operator delete(ptr);
            
            if (ptr == nullptr)
                return;
            
            // 只能挂到对应序号的链表上, 不能回收到cache中
            size_t unit = round_up(len);
            header[getidx(unit)]->make_list(ptr, (char*)ptr + unit);
        }


        void print() {
            size_t count = 0;
            for (size_t i = 0; i < C_LIST_SIZE; ++i) {
                auto head = header[i];
                for (auto i = head->head.load(); i; i = i->next)
                    count++;
            }
            cout << count << endl;
            cout << memory.byte << endl;
            cout << memory.total << endl;
        }
#ifdef _TEST_
        void test() {
            auto mem = malloc(128);
            this->header[C_LIST_SIZE - 1]->make_list(mem, (char*)mem + 128);
        }
#endif // _TEST_



    private:
        template<size_t _idx>
        static constexpr void initialize_header(Header_pp header) {
            static _list_thread<_idx, true_type> head;
            header[_idx] = static_cast<Header_p>(&head);
            initialize_header<_idx - 1>(header);
        }

        template<>
        static void initialize_header<0>(Header_pp header) {
            static _list_thread<0, true_type> head;
            header[0] = static_cast<Header_p>(&head);
        }

        template<size_t _count>
        static constexpr Header_pp initialize_header() {
            static Header_p header[_count];
            initialize_header<_count - 1>(static_cast<Header_pp>(header));
            return static_cast<Header_pp>(header);
        }
    private:
        static cache memory;
        static Header_pp header;
    };
    cache safe_pool::memory;
    safe_pool::Header_pp safe_pool::header = safe_pool::initialize_header<C_LIST_SIZE>();
    
}
}
#endif // !_POOL_HPP







/** 
    main测试
*/
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<thread>
#include<future>
#include"pool.hpp"

void test_safe_pool_get() {
    _pool::safe_pool tmp;
    auto lambda = [&tmp](int size) {
        ostringstream ostr(ios_base::app);
        ostr << "\n\nthread: " << this_thread::get_id();
        ostr << "\n\talloc(" << size << ") address: " << tmp.alloc(size) << "\n\n";
        cout << ostr.str();
    };
    thread t_a(lambda, 6);
    thread t_b(lambda, 72);
    thread t_c(lambda, 16);
    thread t_d(lambda, 30);
    thread t_e(lambda, 128);
    thread t_f(lambda, 13);
    thread t_g(lambda, 8);
    thread t_h(lambda, 8);
    thread t_i(lambda, 24);

    t_a.join();
    t_b.join();
    t_c.join();
    t_d.join();
    t_e.join();
    t_f.join();
    t_g.join();
    t_h.join();
    t_i.join();

    tmp.print();
}


void test_safe_pool_new_delete(){

    _pool::safe_pool tmp;

    auto get_mem = [&tmp](int size) -> void*{
        auto result = tmp.alloc(size);
        printf("thread: %u\n\tget mem: %p size: %d\n",this_thread::get_id(), result,size);
        return result;
    };

    auto del_mem =� [&tmp](future<void*>& f, size_t len) {
        auto del = f.get();
        printf("thread: %u\n\tdel mem: %p size: %d\n",this_thread::get_id(), del, len);
        return tmp.dealloc(del, len);
    };

    

    /** 
        这里测试的时候, 1个task只能对应1个thread, 如果想测试更多的线程, 则只有将循环的次数增大
    */
    for (int i = -1; ++i < 10;) {
        packaged_task<void* (int)> task(get_mem);
        auto f = task.get_future();

        srand(std::chrono::system_clock::to_time_t(std::chrono::system_clock::now()));
        int n = rand() % 129;

        thread t_get(std::ref(task), n);
        thread t_del(del_mem,std::ref(f), n);

        this_thread::sleep_for(chrono::milliseconds(100));
        t_get.join();
        t_del.join();
    }
    
    
    tmp.print();
}
int main(int arg, char** args) {
    cout << "内存池的安全获取测试\n";
    //test_safe_pool_get();

    cout << "内存池的交叉(获取和归还)测试\n";
    test_safe_pool_new_delete();
    return 0;
}

malloc

介绍

• 它是1个独立的算法, 由于内存在本质上是由os管理的资源, 所以内存事实上是由os来管理的

• os实现内存的管理也借助了malloc(==在VC6以后win最明显==), 但malloc作为跨平台的一个c语言的算法, 是不可能依赖os的, 所以在linux中, 也有自己的malloc实现, 也就是说各个平台基于malloc都有自己的扩展, 但大致来说, 实现的原理差不多

• malloc属于crt^[1]的一部分, 下面在MSVC(==2019==)中调试一下

CRT

• main函数启动前, 程序的初始化

49.png

50.png

51.png

52.png

第0张图:
    运行可执行文件时的调用栈(CRT)


第1张图:
    运行可执行文件时, 内核开始调用CRT代码的第1步


一直到第3张, 开始CRT的初始化, 但已经看不到源码了


ps: 其中第2张图的后续, 会调用到 main函数, 这里没有截出来

sbh

• small block heap

ps: 前面实现的内存管理(==alloc==), 是基于区块的管理(8~128字节), 同样的这里的small block heap也是基于小区块(==1024==以下)

VC6的调用栈

_heap_init()                            _1
  __sbh_heap_init(...)                  _2
_ioinit()                               _3  
  _malloc_dbg(...)                      _4
    _nh_malloc_dbg(...)                 _5
      _heap_alloc_dbg(...)              _6
        __sbh_alloc_block(...)          _7
          __sbh_alloc_new_region()      _8
          __sbh_alloc_new_group(...)    _9
GetCommandLineA()                       _10
__crtGetEnvironmentStringsA()           _11
_setargv()
_setenvp()
_cint()
  _initterm(,,)
    __initstdio()
  _initterm(,,)
mian()
exit(code)
...

_heap_init

int __cdecl _heap_init( int mtflag){
    if (_crtheap != 4096 [向window索取 4096 字节的空间])
        失败直接返回

    if(__sbh_heap_init() == 0){
        释放_crtheap的空间
    }

    return 1;

    /** 
        _crtheap是CRT提个的全局变量
        
        后面再要内存的时候可以从 _crtheap开始的内存(共4096)处取内存
    */
}

__crt_heap_init

int __cdecl __sbh_heap_init(void){

    if (!(__sbh_pHeadList = 16个HEADER大小的空间))
        失败直接返回

    __sbh_pHeaderDefer = NULL;  
    //sbh手上始终有一个区块, 就是用这个来记录的, 当free的动作造成1个区块的完整合并
    // 如果这个值不为空, 则会将合并后的块还给os, 如果为空, 则会记录刚合并好的块

    ...

    /** 
        这个函数是用来索取 16个 HEADER大小的空间(从_crtheap中拿), 
        很像前面的alloc的管理机制(内存管理在某些方面是相通的)

        HEADER的结构
    */
}

• <font color=red>HEADER的结构</font>

typedef unsigned int BITVEC;
typedef struct tagHeader{
    BITVEC      bitvEntryHi;
    BITVEC      bitvEntryLo;
    BITVEC      bitvCommit;
    void*       pHeapData;
    struct tagRegin* pRegion;
} HEADER, *PHEADER;
/** 
    Hi和Lo构成了64个bit

    pHeapData指向的是1MB的空间起始地址, 但每次要内存是32kb

    pRegion是用来高效管理1MB内存, 后面说
*/

• HEADER的图

  
  
  53.png

所以程序第1块内存是_crtheap(4096), 但malloc(sbh)还没出场,因为
第0个HEADER中的 pHeapData还指向空(没有内存)

接下来是 crt自己需要内存时, 发现sbh为0, 则就要开始sbh的初始化
    即 为第0个HEADER中的pHeapData分配1MB(虚空间), 并创建这1MB的管理(pRegion)

    ps:pHeapData指向的是1MB,并且地址是连续的, 但管理这1MB的机制是分段
        每次管理32kb(由pPegion的结构决定)

_ioinit

/** 
    前面的2步, 已经初始化好了第0个HEADER(但没有内存(pHeapData为空))
    这一步就是CRT自己malloc第1块内存(前面的4096就不算了)
    用来为io准备的
*/
void __cdecl _ioinit(void){
    ...
    if((pio = _malloc_crt(IOINFO_ARRAY_ELTS * sizeof(ioinfo))) == 0)
    ...
}

/** 
    其中 _malloc_crt是一个macro, 在debug环境下会附带内存相关的信息

#define _FREE_BLOCK         0
#define _NORMAL_BLOCK       1
#define _CRT_BLOCK          2
#define _IGNORE_BLOCK       3
#define _CLIENT_BLOCK       4
#define _MAX_BLOCKS         5

#ifndef _DEBUG
#define _malloc_crt malloc

#else
#define _THISFILE _FILE_
#define _malloc_crt(s) _malloc_dbg(s, _CRT_BLOCK, _THISFILE, __LINE__)
..
#endif


所以当在debug环境下, _malloc_crt会对内存附加:
    1. 当前哪个文件申请的内存
    2. 哪1行申请的内存
    3. 是谁申请的(_CRT_BLOCK(crt自己) 还是 _NORMAL_BLOCK(其他人))
    ps: 这些值会在后面的 _heap_alloc_dbg中添加上

IOINFO_ARRAY_ELTS长度是32字节
ioinfo是8字节
    typedef strcut{
        long osfhnd;
        char osfile;
        char pipech;
    } ioinfo;
所以crt的第1块内存是256字节(100H)
*/

_heap_alloc_dbg(==跳过了不相关的函数==)

...
// nSize是前面传递来的256字节
blockSize = sizeof(_CrtMemBlockHeader) + nSize + nNoMandsLandSize;     //_code_a

..

//向sbh要内存
pHead = (_CrtMemBlockHeader*)_heap_alloc_base(blockSize); 

//_code_b
if(_pFirstBlock)
    _pFirstBlock->pBlockHeaderPrev = pHead;
esle
    _pLastBlock = pHead;

//对分配好的内存填充数据
pHead->pBlockHeaderPrev = NULL;
pHead->pBlockHeaderNext = _pFirstBlock->pBlockHeaderNext;
... 后面是文件, 行号, 等信息的赋值


_pFirstBlock = pHead;


//_code_c
memset(pHead->gap, _bnoMansLandFill, nNoMansLandSize);  //_code_c_a
memset(pbData(pHead), _bnoMansLandFill, nNoMansLandSize);  //_code_c_b
memset(pbData(pHead), _bCleanLandFill, nsize);  //_code_c_c

return pbData(pHead);

54.png

/** 
   _code_a是对传递来的256字节做附加(debug调试需要的信息)

#define nNoMandsLandSize 4
typedef struct _CrtMemBlockHeader{
    struct _CrtMemBlockHeader* pBlockHeaderNext;
    struct _CrtMemBlockHeader* pBlockHeaderPrev;
    char*       sZFileName;     //文件路径和名
    int         nLine;          //行号
    size_t      nDataSize;      //要用户需要的内存大小
    int         nBlockUse;      //是crt在申请, 还是其他人在申请
    long        lRequest;       //流水号
    unsigned char gap[nNoMandsLandSize];//4个字节的 uchar
} _CrtMemBlockHeader; 如上图
    
    也就是说1块malloc的内存给出后(debug), 会被crt记载:
        1. 指向下一个malloc的内存
        2. 指向上一个malloc的内存
        3. 当前这块内存是由哪个文件发出的
        4. 由哪一行发出的
        5. 申请的多大
        6. 由谁(crt或用户)申请的
        7. 第几次申请(流水号)
        8. 由gap来隔离userdata(如图中的gap)
        9. 用户的数据
        10.gap
        ps: gap的作用是用户数据的上下栅栏,后面在分配好内存后会被填上 0xfd



    _code_b 是说分配出来的 pHead插入到当前_pFirstBlock前
        如果_pFirstBlock 没有值, 则记录_pLastBlock为pHead
    
        ps: _pFirstBlock和_pLastBlock是全局的2个变量(_CrtMemBlockHeader*), 也就是说所有的malloc出来的内存都会被串到双向链表中



   _code_c 是将分配出来的内存在 栅栏(gap)和用户的数据区填充上值
   static uchar _bNoMansLandFill    = 0xFD;
   static uchar _bDeadLandFill      = 0xDD;
   static uchar _bClearLandFill     = 0xCD;

   所以用户得到的内存pbData(pHead)的空间中填充的是0xCD, 所以在很多次
   断点调试中, 如果用1个char*去接收malloc时, 会发现得到内存中的内容是屯
   测试如下图:
*/

55.png

ps: 上面只是在 <font color=red>调整最初的256字节(==100H==)的debug-header</font>, 真正分配内存的是==_heap_alloc_base==函数(<font color=#800080>上面的代码也调用了</font>), 在探究_heap_alloc_base前, 先给出一张malloc内存的链表图

56.png

每1块内存的2端, 是记录malloc出去的内存大小, 一定是16的倍数, 借用第0个bit, 如果是1表示已经借出去, 如果为0表示free还回来, ==packed==是在 <font color=red>debug后的空间的基础上, 上调为16倍数需要扩展的内存</font>, ==mem_b, mem_c==没有画出其他部分的数据, 懒的画了, 可以发现新的malloc内存是从==_pFirstBlock==位置插入的

heap_alloc_base

...
/** 
    前面函数将最初的256字节附加debug后(size),此时还没调整为16的倍数
    如果size < 1016, 则由sbh(即malloc)来分配
        这里的1016是没有加上 malloc区块在大小(8字节, 上下各1个),也就是说用户需要的
        内存在附加debug-header后, 大于1kb, 则交给os处理

    否则在当前函数中将size调整为16的倍数, 交给window给出内存
    ps: 其实os分配时可能不是16的倍数, 但sbh自己会调整为16的倍数

*/
if(size <= __sbh_threshold){
    pvReturn = __sbh_alloc_block(size);
    if(pvReturn) return pvReturn
}

if(size == 0)
    size = 1;
size = (size + 0xf) &~ (0xf);   //上调为16的倍数

return HeapAlloc(_crtheap,0,size);
...

__sbh_alloc_block

• 将上面的size调整为16的倍数
  • 计算最初的==256==的malloc大小

size_t mem = 256 + sizeof(_CrtMemBlockHeader)(36) + 2*(sizeof(int));
mem再上调 为16的倍数

ps: 由于是32的操作系统, 所以上下2端的空间大小用int表示,可以存储所有内存(4GB[2^32])

__sbh_alloc_new_xxx

57.png

• 后面就是以图的方式来解说 <font color=red>__sbh_alloc_new_region 和 _sbh_alloc_new_group</font>

前面所有的工作:
    1. ioinit发出256字节的内存
    2. 附加debug所需的大小
    3. 调整为16的倍数

已经准备完成, 但由于是向sbh要第1块内存, HEADER[0]中的pHeapData还是空, 所以接下来就是真正的初始化sbh

如上图, 先在HEADER[0]中向os索取1MB内存, 但只是登记,取32kb出来, 其余的给sbh留着
获取到32kb后, HEADER[0]中的pRegion就接着初始化

region的相关结构如下

struct REGION{
    int indGroupUse;
    char cntRegionSize[64];
    BITVEC bitvGroupHi[32];
    BITVEC bitvGroupLo[32]; //uint
    struct tagGroup grpHeadList[32];
};

struct tagGroup{
    int cntEntries;
    struct tagListHead listHead[64];
};

struct tagListHead{
    struct tagEntry* pEntryNext;
    struct tagEntry* pEntryPrev;
};
/** 
    将这些结构作成如上的图
*/

总的来说就是1个HEADER管理1MB的内存

每个HEADER通过 32个组(group)来管理1MB

所以每个组就管理32kb, 而group中又通过 64对双向链表来管理这个组的32kb

group的64对链表的概念就是前面内存池16条链表对应的概念
第0条管理16字节
第1条管理32字节
...
最后1条链表是特殊的, 管理1kb(1024byte)以上的内存


而group管理自己的32kb也是分段管理, 将32kb分成8段, 每段4kb(4096)
如下图:

58.png

如上图, 每个group将32kb分为8个page, 每个page为4kb
每个page可以看成1个没有debug空间的malloc块

如上图:
    每个块4096, 看成malloc块后 > 1024, 所以挂载在group中的第63号链表上
    在这个块中, 预设有:
        1. 底部的0xFFFFFFFF
        2. 顶部的0xFFFFFFFF

    非预设但填值:
        1. 底部记录当前malloc的区块
        2. 顶部记录当前malloc的区块
        3. 一个Entry*next, Entry* prev 

        struct Entry{
            int size;
            Entry* next;
            Entry* prev;
        };

        typedef struct Entry tagEntry;

    其中第1和第2是栅栏, 用来隔开数据, 因为 1MB有32个32kb, 32kb中有8个4kb, 所以
    1Mb有256个4kb(page), 这些page都是相连的, 所是要用上下2个0xFFFFFFFF隔开
    但被视为malloc的4kb必须为16的倍数, 因为第1,2已经消耗了8个字节, 所以剩下4096-8 = 4088 
    调整为16的倍数就是4080


 外界获取内存(mem)时:
    sbh先看当前应该到哪个HEADER[n]中
    哪个group中
    哪个链表

由于ioinit发出的是256字节, 并且sbh发现是第1次, HEADER[0]的pHeadData为空
所以向os要了1MB的虚拟空间, 然后初始化sbh环境(真正取32kb)
然后创建region, 发现256(debug+调整后大小是130H), 应该到18号链表中找
但18没有, 然后就像alloc中一样, 从18往后找, 然后在第63号中发现有内存
于是从63号链表中next找到链表切割



额外说明:
    前面的region中的group中, 有64对双向链表, 它们的类型是Entry*
    group的结构(上上张图)发现在初始化的时候:
        每一对链表(next,prev)中的next指向上一个prev, 而prev和next指的是同一个地址
        Entry的结构是(int, Entry* next, Entry* prev)
        也就是说形成了一个双向循环链表, 比如上面的图, sbh初始化后
        32kb的空间挂载到了第63号链表中:
          第63号链表的next指向了32kb的第0个page可用地址
          32kb的8个page之间是双向相连的 
          32kb的第7个page的next指向了第62号链表的prev,这样解释第7个page的next指针时, 62号链表的prev就会被当作int,而紧接着prev后的就是第63号链表的next(指向了第0个page的next)
        第63号的prev又指向了第7个page的next, 这样就形成了双向循环链表
    总结就是 group中的每1对链表在初始化后, 会指向上一个链表的prev,目的是借用一个int(在32位中int和void*大小相等)形成双向循环链表, 这也是实现上的一个技巧


ps: HEADER中那些bit位以及region中的bit位, 就是用来快速定位, 提高效率

下面开始细说,内存是怎么切割的

sbh的第1块内存(==vc6==)

59.png

ioinit第1块内存, 会从第63号链表中切割出130H, 并由_pFirstBloc和_pLastBlock记载
切割后的内存被标记为131, 最后1个bit置1是借出去

然后剩余EC0H, 大于1024, 所以继续挂载在第63号链表中

并且region中的计数器cntEntries +1

sbh的第2块内存

60.png

和前面一样, 先到对应的链表中有没有, 没有一直找到后面有内存的链表
注意指针的拉动

在给内存的过程中, 如果发现剩余的内存不够1kb, 就会挂到对应的链表中

后续的就不再给图了

free

• free的动作就是将客户的内存定位到:
  • HEADER[N]
  • group[N]
  • list[N]
  • 然后定位到malloc的上区块, 将最后1个bit位的1改为0
  • 将对应的内存挂载到对应的链表, 调整相关的指针
  • 修改region的计数器-1

ps: 需要说明的是, malloc查询N号链表内存的流程和前面的alloc一样, 只是实现方式不同

合并

• free的过程也会试着合并, 因为有上下区块的大小, 所以从理论上合并完全没有问题
• 当region的计数器为0时, 表示32kb的内存完全合并, 这个时候就会考虑是否还给os

要看__sbh_pHeaderDefer是有值, 如果有则会将刚完全合并的内存还给os, 如果没有, 则会将合并好的内存指给__sbh_pHeaderDefer

release下的malloc

• 只记录上下2个malloc块大小(当然还是16的倍数所以可能会有填充)

• malloc的实现远远不只这么多, 但流程基本就这样, 像malloc可能还要查找内存对齐等等, 都有自己高效的算法

VS2019简单测试

int main(int arg, char** args) {
    constexpr size_t s = sizeof(long);
    char* tmp_a = (char*)malloc(5);
    /** 
        测试(32位, VS2019, debug)
    */

    // 用户得到的内存的上面4个字节(gap篱笆),(已经不是0xfdfdfdfd了, 而是0xfffffffd)
    cout << std::hex << (unsigned int)*(tmp_a - 4) << endl;

    // 用户得到的内存的下面4个字节, 和上面的结果一样
    cout << std::hex << (unsigned int)*(tmp_a + 5) << endl;

    //流水号, 这个其实之前解释的也不是很清楚, 不要管这个
    cout << std::hex << (unsigned int)*(tmp_a - 8) << endl;

    //这里想测试是crt申请的内存还是用户的, 但发现打印的是用户申请的内存大小
    //用户申请的内存大小(这里是5, 如果上面改成malloc(11), 则这里打印就是11)
    cout << std::hex << (unsigned int)*(tmp_a - 12) << endl;

    //这里想打印malloc中的行号, 但发现打印的是1, 根据前面的分析, 这个1可能就是标记
    /// 这块内存是crt(2)申请的还是用户(1)申请的, 所以代表此内存是用户申请的
    cout << std::hex << (unsigned int)*(tmp_a - 16) << endl;
    

    //后面找不到行号和文件, 看来现在的vc在实现方面已经和以前有所不同了
    cout << std::hex << (char*)&*(tmp_a - 28);
}

内存泄露的正确概念

• 通过前面的 <font color=red>malloc块的结构</font>, 可以总结出:
  • 只有当 <font color=red>main函数结束前</font>, 在 <font color=red>malloc给出的内存链表中</font>, 那些 <font color=red>在debug模式下, 如果链表中还存在标记为1的(用户申请的malloc块), 才是内存泄露</font>, main结束后, crt会释放自己的malloc块, 但其实main结束, sbh也就完全销毁了, 用户泄露的内存也随着销毁

loki

简介

• <font color=red>loki是一个库, 这里只是拿他的分配器来说事</font>

• 回顾前面的 <font color=red>GNUC的alloc</font>, 它的缺点就是 <font color=red>没办法将内存还给OS</font>, 原因是设计上不允许

• 可归还给os的内存池, 抛开malloc那种复杂的设计, 一种比较直观的解决方案是 <font color=red>一块malloc出来的chunk块内存不要在使用的过程中挂载到其他地方</font>, 也就是说 <font color=red>就只使用它</font>, 以一个简单的demo来说明

using namespace std;

const int unit = 8;
const int chunk = 20;
char* start = NULL;
unsigned next_idx;
unsigned available;

void init(void* begin) {
    for (int i = 0, j = 0; j < chunk; i += unit)
        *(unsigned int*)(start + i) = ++j;

    next_idx = 0;
    available = chunk;
}

void* get() {
    if (available == 0)
        return 0;

    void* result = (void*)(start + next_idx * unit);
    next_idx = *(unsigned*)result;
    --available;
    return result;
}

void del(void* ptr) {
    if (ptr == nullptr)
        return;
    
    if (ptr < start || ptr >= (start + unit * chunk))
        return;

    *(unsigned*)ptr = next_idx;
    next_idx = ((char*)ptr - start) / unit;

    ++available;
}

void test_get() {
    void* get_a = get();
    cout << get_a << endl;
    void* get_b = get();
    cout << get_b << endl;
    void* get_c = get();
    cout << get_c << endl;
}

void test_del() {
    void* get_a = get();
    cout << get_a << endl;
    void* get_b = get();
    cout << get_b << endl;
    void* get_c = get();
    cout << get_c << endl;
    void* get_d = get();
    cout << get_d << endl;

    del(get_c);
    del(get_a);
    void* get_e = get();
    cout << get_e << endl;  //获取的是原来的get_a
    void* get_f = get();
    cout << get_f << endl;  //获取的是原来的get_c
    void* get_g = get();
    cout << get_g << endl; //获取的是原来get_d后面的1块内存地址

}

int main(int arg, char** args) {
    start = (char*)malloc(unit * chunk);
    init(start);

    //test_get();
    test_del();
}

/** 
00DA06A0        get_a
00DA06A8        get_b
00DA06B0        get_c
00DA06B8        get_d
00DA06A0        get_e
00DA06B0        get_f
00DA06C0        get_g

测试的是 test_del()


*/

上述小例子的原理

61.png

62.png

63.png

64.png

65.png

图中的过程其实很清楚了

案例中核心的思想是:
    没用过的内存, 坚决不用, 一定要等它前面的内存用完后, 再用后面没有用过的
        如第5块内存, 因为它前面先后还了第3块和第1块, 所以后续再用的时候, 必须先取它前面没用过的

    为了实现 第5块内存 之前没用过的内存要先后用完, 所以用了next_idx来标记 再取内存时应该从哪里开始
    每1块回来的内存都会标记 这块内存用完后下1块可取的内存序号, 所以就无形形成了1个链表, 形成链表的目的:
        就是用完目前第5块前面所有的内存


这就是loki内存分配器的核心, 很明显, 这里完全可以构造出 vector<(start, next_idx, avaiable)> 多个这样的结构
用来处理不同chunk, 并且根据avaiable就可以做到归还os(avaiable为满值时)

loki分配器的3个类结构

67.png

流程:
    Chunk就是上面小例子中的实现机制, 用来分配内存, 收回内存

    FixedAllotator是 多个相同 大小的chunk容器
        如它的Chunk对象只负责8字节

    SmallObjAllocator就是 管理不同字节大小的 FixedAllocator

    对比前面的GNUC alloc:
        FixedAllocator就是某个字节大小(如:8字节)的链表, 但它是用数组的方式来管理,每次malloc的内存有记录,并连续 便于回收
        SmallObjAllocator就是管理各个不同大小的FixedAllocator(8字节, 16字节, ....)

    
    下面就依照这张图, 来实现一个可收回的allocator
    ps: 并不是实现loki, 话说本人是并不知道loki的具体实现, 但既然loki是用 上面小案例的机制实现了可回收的分配器
        那从道理上讲, 不管是怎么实现的, 原理都一样, 只是设计上会有出入

    下面是一个简单的实现, 没怎么细致测试

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<vector>
#include<unordered_map>
#include<atomic>
#include<thread>

#define _TEST_

#ifdef _TEST_
#include<sstream>
#define from_print ((void*)from)
#define full_print ((void*)full)
#endif // _TEST_



using namespace std;
/**
    最大管理 96字节, 超过后交给::operator new
    每条链表最多 是 96 * 16 的空间(1536)

    _unit       _chunk
    8           192
    16          96
    24          64
    32          48
    40          38(实际是1536/40 = 38.4, 要小于1536, 所以取38)
    48          32
    56          27(同40的情况)
    64          24
    72          21
    80          19
    88          17
    96          16
*/

namespace lb { namespace loki {
    using namespace std;

    constexpr size_t MAX_UNIT = 96;
    constexpr size_t MIN_UNIT = 8;
    constexpr size_t ARR_SIZE = 12;
    constexpr size_t MAX_MEMORY = MAX_UNIT * 16;

    template<size_t _unit>constexpr size_t get_chunk() {
        static_assert((_unit % MIN_UNIT == 0), "必须为8的倍数");
        return (size_t)(MAX_MEMORY / _unit);
    }
    template<>constexpr size_t get_chunk<0>() {return 0;}



    template<size_t _unit, size_t _chunk> class group_chunk;

    static size_t get_count;
    static size_t del_count;
    static size_t total;

    template<>class group_chunk<0, 0> {

    public:
        virtual void test() { }
        virtual void* alloc() { return 0; }
        virtual void dealloc(void* ptr) { }
        
    public:
        template<size_t _unit, size_t _chunk>
        struct _alloc : public _alloc<0,0>{
            _alloc(){init();}
        
            void init() {
                start = (char*)::operator new(_unit * _chunk);
                total += _chunk;
                for (int i = 0, j = 0; j < _chunk; i += _unit)
                    *(unsigned int*)(start + i) = ++j;

                idx = 0;
                available = _chunk;
            }

            virtual void* get() {
                ++get_count;
                if (available == 0)
                    return 0;
                void* result = (void*)(start + idx * _unit);
                idx = *(size_t*)result;
                --available;
                return result;
            }

            virtual void del(void* ptr) {
                ++del_count;
                *(size_t*)ptr = idx;
                idx = ((char*)ptr - start) / _unit;
                ++available;
            }

            virtual bool full()const {
                return available == _chunk;
            }
        };

        template<>
        struct _alloc<0, 0> {
            char* start;
            size_t idx = 0;
            size_t available = 0;
            virtual void* get() { return 0; }
            virtual void del(void* ptr) { }
            virtual bool full()const { return false; }


            // 因为本案例中, map存放的是指针, 所以这里不给出big three, 以及移动ctor

            virtual ~_alloc(){
                if (start) {
                    delete start;
                }
            }
        };
    protected:
        unordered_map<char*, _alloc<0,0>*> map;
        char* from;
        char* full;
        atomic<bool> lock{false};
    };
    


    
    
    

    template<size_t _unit, size_t _chunk = get_chunk<_unit>()>
    class group_chunk : public group_chunk<0,0> {
        virtual void test() {
            cout << "_unit: " << _unit << endl;
            cout << "_chunk: " << _chunk << endl;
            cout << "map: " << &this->map << endl;
        }

        char* find_has() {
            for (auto it = map.begin(), end = map.end(); it != end; ++it) 
                if (it->second->available) 
                    return it->first;

            return nullptr;
        }
        
        virtual void* alloc() override {
            while (this->lock.exchange(true, memory_order_acq_rel)){
                this_thread::yield();
                continue;
            }

            if (this->from) {
                auto cur_alloc = this->map[this->from];
                
                auto result = cur_alloc->get();

                if (!result) {
                    this->from = nullptr;
                    this->lock.store(false, memory_order_release);
                    return alloc();
                }

                // 如果调用前当前的区块已经是全回收, 给出内存后,full要去掉记录
                if (this->full == cur_alloc->start) 
                    this->full = nullptr;

                this->from = cur_alloc->available ? this->from : find_has();
                this->lock.store(false, memory_order_release);
                return result;
            }

            //map中没有可用的数组, 创建一块空间
            _alloc<0, 0>* arr = new _alloc<_unit, _chunk>();

            map.insert(make_pair(arr->start, arr));
            this->from = arr->start;

            this->lock.store(false, memory_order_release);
            return alloc();
        }

        virtual void dealloc(void* ptr) override {
            char* tmp_ptr = (char*)ptr;
            
            char* record_del = 0;

            while (this->lock.exchange(true, memory_order_acq_rel)) {
                this_thread::yield();
                continue;
            }


            for (auto it = map.begin(), end = map.end(); it != end; ++it) {
                if (tmp_ptr >= it->first && tmp_ptr < it->first+(_chunk * _unit)) {
                    it->second->del(ptr);

                    // 当前全回收, 并且有记录, 则要删除当前的这个
                    if (it->second->full() && this->full) 
                        record_del = it->first;
                    
                    // 当前全回收, 但没有记录, 则记录下当前这个
                    else if(it->second->full() && !this->full) {
                        this->full = it->first;
                    }

                    //还内存了, 就意味着有可取内存, 则看from有没有值, 没有就记录当前这个
                    /// 下次就根据from从当前的空间取(from可能和full共用)
                    if(this->from == nullptr && !record_del)
                        this->from = it->first;

                    //from有值(指向当前), 但当前被删除, 则为from寻找下一个有值的区块
                    if (this->from == record_del) {
                        this->from = find_has();
                    }
                    break;
                }
            }

            if (record_del) {
                auto del_alloc = map.at(record_del);

                // 从容器中删除
                map.erase(record_del);

                delete del_alloc;
            }

            this->lock.store(false, memory_order_release);
        }
    };




    class allocator {
    public:
        void* alloc(size_t len) {
            size_t up = (len + MIN_UNIT - 1) & ~(MIN_UNIT - 1);
            size_t index = up / MIN_UNIT - 1;
            return groups[index]->alloc();
        }
        void dealloc(void* ptr, size_t len) {
            size_t up = (len + MIN_UNIT - 1) & ~(MIN_UNIT - 1);
            size_t index = up / MIN_UNIT - 1;
            groups[index]->dealloc(ptr);
        }
    private:
        template<size_t _idx>
        static constexpr size_t round_up() {
            return (_idx + 1) * MIN_UNIT;
        }

        template<size_t _idx>
        static constexpr void initialize_header(group_chunk<0, 0>** header) {
            static group_chunk<round_up<_idx>()> group;
            header[_idx] = static_cast<group_chunk<0, 0>*>(&group);
            initialize_header<_idx - 1>(header);
        }

        template<>
        static void initialize_header<0>(group_chunk<0,0>** header) {
            static group_chunk<8> group;
            header[0] = static_cast<group_chunk<0,0>*>(&group);
        }

        template<size_t _count>
        static constexpr group_chunk<0, 0>** initialize_header() {
            static group_chunk<0, 0>* header[_count];
            initialize_header<_count - 1>(static_cast<group_chunk<0, 0>**>(header));
            return static_cast<group_chunk<0, 0>**>(header);
        }

        static group_chunk<0, 0>** groups;
    };

    group_chunk<0, 0>** lb::loki::allocator::groups = initialize_header<ARR_SIZE>();


}}


void test_size() {
    lb::loki::group_chunk<0, 0>* ptr_8 = new lb::loki::group_chunk<8>();
    lb::loki::group_chunk<0, 0>* ptr_16 = new lb::loki::group_chunk<16>();
    lb::loki::group_chunk<0, 0>* ptr_24 = new lb::loki::group_chunk<24>();
    lb::loki::group_chunk<0, 0>* ptr_32 = new lb::loki::group_chunk<32>();
    cout << "大小:\n";
    cout << sizeof(lb::loki::group_chunk<8>) << endl;
    cout << sizeof(lb::loki::group_chunk<16>) << endl;
    cout << sizeof(lb::loki::group_chunk<24>) << endl;
    cout << sizeof(lb::loki::group_chunk<32>) << endl;
    cout << sizeof(unordered_map<char*, lb::loki::group_chunk<0,0>::_alloc<0,0>*>) << endl;
}


/** 
    测试单独的group_chunk
*/
void test_multi() {
    using __alloc__ = lb::loki::group_chunk<96>;
    lb::loki::group_chunk<0, 0>* ptr_96 = new lb::loki::group_chunk<96>();

    auto mem_get = [ptr_96](bool rmv)->void {
        auto mem = ptr_96->alloc();
        ostringstream os;
        os << "thread: " << this_thread::get_id() << endl;
        os << "get mem: " << mem << endl;
        cout << os.str();
        ptr_96->dealloc(mem);
    };


    for (int i = 0; i < 10; ++i) {
        thread t_a(mem_get, i%2);
        thread t_b(mem_get, i%2);
        thread t_c(mem_get, i%2);
        thread t_d(mem_get, i%2);
        thread t_e(mem_get, i%2);
        thread t_f(mem_get, i%2);

        
        
        t_a.join();
        t_b.join();
        t_c.join();
        t_d.join();
        t_e.join();
        t_f.join();
    }
    cout << "over\n";
    cout << lb::loki::get_count << endl;
    cout << lb::loki::del_count << endl;
    cout << lb::loki::total << endl;
}


void test_loki() {
    lb::loki::allocator _all;

    auto mem_get = [&_all](size_t len)->void {
        auto mem = _all.alloc(len);
        ostringstream os;
        os << "thread: " << this_thread::get_id() << endl;
        os << "get mem: " << mem << endl;
        cout << os.str();
        _all.dealloc(mem,len);
    };


    for (int i = 0; i < 10; ++i) {
        thread t_a(mem_get, 6);
        thread t_b(mem_get, 6);
        thread t_c(mem_get, 6);
        thread t_d(mem_get, 6);
        thread t_e(mem_get, 6);
        thread t_f(mem_get, 6);



        t_a.join();
        t_b.join();
        t_c.join();
        t_d.join();
        t_e.join();
        t_f.join();
    }
    cout << "over\n";
    cout << lb::loki::get_count << endl;
    cout << lb::loki::del_count << endl;
    cout << lb::loki::total << endl;
}

int main(int arg, char** args) {
    //test_size();
    cout << "********************\n";
    //test_multi();
    cout << "********************\n";
    test_loki();

}

GNUC的其他分配器

分配器的标准描述

• 分配器的意义在于 <font color=red>容器服务</font>, 原因就不说了

• 当 <font color=red>元素加入到容器中时</font>, 容器必须分配更多内存来保存这些元素, 于是向 <font color=red>模板参数Allocator发出申请</font>

• 每个元素类型为T的容器的==Allocator==模板的==默认参数==是 <font color=red>allocator<T></font>, 接口大概有==20==个==public==声明, 但最重要的2个是:
  • T* allocate(size_type n, const void* hint = 0)
  • void deallocate(T* p, size_type n)

  ps: n是n个T, 并不是总量, 它们是通过用::operator new获取内存, 但==何时调用==, 以及==调用频率==, 没有具体指定(即==没有做缓存管理==)

• 最容易满足的作法就是 <font color=red>需要时就==要==, 释放时就==还==</font>, 就是所谓的 <font color=red>operator new和operator delete</font>,优势就是跨平台
  • 支持这样作法的分配器有:
    • __gnu_cxx::new_allocator
    • __gnu_cxx::malloc_allocator

    ps: 第1个是调用 <font color=red>::operator new和delete</font>, 是C++的标准, 支持跨平台, 支持重载, 第2个是C的标准, 内部直接调用的malloc/free, 但不能重载

• 另一种就是使用 <font color=red>智能型</font>, 就是前面实现的==allocate==, 不过在GNUC中还有其他功能的内存池

array_allocator

/** 
    相当于一个static array[static size_t]

    下面是在g++的环境下
*/
using namespace std;
using namespace std::tr1;   //array_allocator可能引用的是TR1版本的array, 但其实和C++11的array实现是一样的
using namespace __gnu_cxx;  //因为不是标准的分配器, 所以放在别的namespace中
    
int arr[20];

array_allocator<int, array<int,20>> arr_alloc(&arr);

void test(){
    int* p_a = arr_alloc.allocate(1);
    int* p_b = arr_alloc.allocate(3);

    // 内部并不会释放空间, 因为是静态数组
    /// 先不管它是怎么实现的, 如果自己来实现复用, 那不就是可以利用上面的loki的原理
    // 但其实array_allocator的deallocate什么都没有做
    arr_alloc.deallocate(p_a);
    arr_alloc.deallocate(p_b);
}

<font color=red size=12>以后再回补充</font>

1. C运行环境(==C runtime library,也可以理解为进程初始化==)[图片上传中...(36.png-570617-1614094151878-0)] ↩