超详细NCNN内存分配算法（小白必看，不懂打我）_ncnn 内存泄漏

NCNN是一款高效易用的深度学习推理框架，支持各种神经网络模型，如pytorch、tensorflow、onnx等，以及多种硬件后端，如x86、arm、riscv、mips、vulkan等，本文详细介绍内存分配算法。（从各个博客进行整理，争取以详细易懂的方式讲解这个算法。

字节分配算法

问题：分配n字节 ，以 align字节为对齐字节。

#原始算法
unsigned int calc_align(unsigned int n,unsigned align)
{
    if ( n / align * align == n)
            return n;
        return  (n / align + 1) * align;
}

返回能容纳n个字节的整除align个字节的最小空间字节数。

#进阶版算法  
unsigned int calc_align(unsigned int n,unsigned int align)
{
    return (n+ align - 1) & ~(align - 1);
}

难点1

理解 (n + align - 1) & ~(align - 1)
由于，可得

为向上对齐，可能进位，使得分配字节为align倍数内能容纳完n个字节。

而用于截断：
由于，

为取反码，那么

若，即，，那么，就刚好囊括大于align字节数的范围。无视低于align的部分，因为前面是n+align-1，多余的align-1可以去除。

NCNN写法

NCNN是这么写的。

static inline size_t alignSize(size_t sz, int n)
 
{
    return (sz + n-1) & -n;
}

难点2

为什么？
常识：负数补码为取负+1
那么这里，若即二进制得，
，也就是前面所说的覆盖大于等于align的字节数范围。
同时也就是前面所说的。

NCNN分配内存算法

// Aligns a pointer to the specified number of bytes
// ptr Aligned pointer
// n Alignment size that must be a power of two
template<typename _Tp>
static NCNN_FORCEINLINE _Tp* alignPtr(_Tp* ptr, int n = (int)sizeof(_Tp))
{
    return (_Tp*)(((size_t)ptr + n - 1) & -n);
}
 
// Aligns a buffer size to the specified number of bytes
// The function returns the minimum number that is greater or equal to sz and is divisible by n
// sz Buffer size to align
// n Alignment size that must be a power of two
static NCNN_FORCEINLINE size_t alignSize(size_t sz, int n)
{
    return (sz + n - 1) & -n;
}
 
static NCNN_FORCEINLINE void* fastMalloc(size_t size)
{
#if _MSC_VER
    return _aligned_malloc(size, NCNN_MALLOC_ALIGN);
#elif (defined(__unix__) || defined(__APPLE__)) && _POSIX_C_SOURCE >= 200112L || (__ANDROID__ && __ANDROID_API__ >= 17)
    void* ptr = 0;
    if (posix_memalign(&ptr, NCNN_MALLOC_ALIGN, size + NCNN_MALLOC_OVERREAD))
        ptr = 0;
    return ptr;
#elif __ANDROID__ && __ANDROID_API__ < 17
    return memalign(NCNN_MALLOC_ALIGN, size + NCNN_MALLOC_OVERREAD);
#else
    unsigned char* udata = (unsigned char*)malloc(size + sizeof(void*) + NCNN_MALLOC_ALIGN + NCNN_MALLOC_OVERREAD);
    if (!udata)
        return 0;
    unsigned char** adata = alignPtr((unsigned char**)udata + 1, NCNN_MALLOC_ALIGN);
    adata[-1] = udata;
    return adata;
#endif
}
 
static NCNN_FORCEINLINE void fastFree(void* ptr)
{
    if (ptr)
    {
#if _MSC_VER
        _aligned_free(ptr);
#elif (defined(__unix__) || defined(__APPLE__)) && _POSIX_C_SOURCE >= 200112L || (__ANDROID__ && __ANDROID_API__ >= 17)
        free(ptr);
#elif __ANDROID__ && __ANDROID_API__ < 17
        free(ptr);
#else
        unsigned char* udata = ((unsigned char**)ptr)[-1];
        free(udata);
#endif
    }
}

函数alighPtr 分配指针
函数alighSize 分配内存
函数fastMalloc 快速分配内存

难点3

为什么有udata之后还有adata？udata是怎么分配字节的？

unsigned char*udata =(unsigned char*)malloc (size+sizeof(void*)+MALLOC_ALIGN)
unsigned char**adata=alignPtr((unsigned char**)udata+1,MALLOC_ALIGN);

这里的udata分配 size以外还给了一个指针sizeof(void*) 等于8字节，buffer MALLOC_ALIGN对齐用，保存原始地址 + 对齐。

adata分配了+1，这里1用于记录结尾指针 用于free时候用。adata[-1] = udata, 就是保存最开始分配内存的头指针。

难点4

为什么用** 双重指针？ adata为什么强转**

// 采用类比的方式解释 
unsigned char *a = new char[5]; 
// a + 1 表示从a指针指向的地址走了1个字节, 为啥是1个字节 
// 因为unsigned char *a前面是unsigned char, unsigned char是1个字节 
unsigned char** b = (unsigned char** )a;
 // 同理, b + 1 表示从b指针指向的地址走了8个字节, 为啥是8个字节
 // 因为unsigned char **b前面是unsigned char*, unsigned char*是8个字节 

unsigned char*是个指针类型, 指针类型占8字节的大小，而如果用unsigned char*，分配只有1个字节，造成不对齐。 指针的加减 可以看做去掉一个*, 然后看前面的类型占多少字节。

所以 (unsigned char**)udata + 1 表示udata指向的类型为unsigned char*(是一个指针类型占8字节), 再加一, 即udata从指向的地址往前走了8个字节，达到对齐的目的。