Memory Allocator of Sqlite

| 分类 Database  | 标签 memory  allocator  sqlite 

1 Sqlite 中的内存管理

sqlite3_initialize() 会检查和设置 Sqlite 的内存分配方案。设置通过 sqlite3MallocInit() 来完成。 sqlite3MallocInit() 会检查全局设置中的内存操作指针是否为空,是的话则使用 sqlite3MemSetDefault() 来采用默认设置。

Sqlite 提供了六种分配方式,分别为 mem0, mem1, mem2, mem3, mem5 以及针对 win32 的 winMemMethods ,具体使用哪一个在编译期通过宏来决定。

相关的宏包括:

  • SQLITE_ZERO_MALLOC

    这个宏启用的时候,会使用 mem0 ,所有内存分配都会返回空指针。也许只是用来测试的?

  • SQLITE_SYSTEM_MALLOC

    该宏启用使用, mem1 被启用,会使用标准 C 提供的 malloc() 来分配内存。

    此外,如果编译期没有指定内存分配器,Sqlite 默认将此启用。

  • SQLITE_MEMDEBUG

    对应 mem2 ,同样使用系统的 malloc() ,但包含一些额外的信息用于调试内存分配。

  • SQLITE_WIN32_MALLOC

    对应 winMemMethods ,将启用 Win32 native heap API。

  • SQLITE_ENABLE_MEMSYS3

    对应 mem3 ,所有内存都从预先传入的堆中分配,不会使用 malloc

  • SQLITE_ENABLE_MEMSYS5

    对应 mem5 ,所有内存都从预先传入的堆中分配,不会使用 malloc

    TOOD:mem3 区别???

如果编译期没有指定内存分配方式, mem1 将被采用:

 1: #if defined(SQLITE_SYSTEM_MALLOC) \
 2:   + defined(SQLITE_WIN32_MALLOC) \
 3:   + defined(SQLITE_ZERO_MALLOC) \
 4:   + defined(SQLITE_MEMDEBUG)>1
 5: # error "Two or more of the following compile-time configuration options\
 6:  are defined but at most one is allowed:\
 7:  SQLITE_SYSTEM_MALLOC, SQLITE_WIN32_MALLOC, SQLITE_MEMDEBUG,\
 8:  SQLITE_ZERO_MALLOC"
 9: #endif
10: #if defined(SQLITE_SYSTEM_MALLOC) \
11:   + defined(SQLITE_WIN32_MALLOC) \
12:   + defined(SQLITE_ZERO_MALLOC) \
13:   + defined(SQLITE_MEMDEBUG)==0
14: # define SQLITE_SYSTEM_MALLOC 1
15: #endif

上述的各种方案均通过各自提供的 sqlite3MemSetDefault() 来设置函数指针:

 1: void sqlite3MemSetDefault(void){
 2:     static const sqlite3_mem_methods defaultMethods = {
 3:         sqlite3MemMalloc,
 4:         sqlite3MemFree,
 5:         sqlite3MemRealloc,
 6:         sqlite3MemSize,
 7:         sqlite3MemRoundup,
 8:         sqlite3MemInit,
 9:         sqlite3MemShutdown,
10:         0
11:     };
12:     sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods);
13: }

2 Mem1 – Standard Memory Management

mem1 中的内存操作函数是对 malloc/free 的封装。

如果系统提供了 malloc.h ,则可以通过系统提供的 API 来获取某一已经分配的空间的大小, sqlite3_mem_methods 中定义的所有方法都是简单调用。否则的话,需要对 malloc/free 做一些封装。

  • sqlite3MemMalloc 分配内存时,多分配了一些字节,并用最高的 8 个字节来保存分配的 size,并将指针加 8 后返回。
     1: /*
     2: ** Round up a number to the next larger multiple of 8.  This is used
     3: ** to force 8-byte alignment on 64-bit architectures.
     4: */
     5: #define ROUND8(x)     (((x)+7)&~7)
     6: 
     7: static void *sqlite3MemMalloc(int nByte){
     8:     sqlite3_int64 *p;
     9:     assert( nByte>0 );
    10:     nByte = ROUND8(nByte);
    11:     p = SQLITE_MALLOC( nByte+8 );
    12:     if( p ){
    13:         p[0] = nByte;
    14:         p++;
    15:     }else{/**/}
    16:     return (void *)p;
    17: }
    
  • sqlite3MemFree sqlite3MemFree 的反向操作,指针减 8 之后删除,删除即可:
    1: static void sqlite3MemFree(void *pPrior){
    2:   sqlite3_int64 *p = (sqlite3_int64*)pPrior;
    3:   assert( pPrior!=0 );
    4:   p--;
    5: }
    

3 Mem2 – Standard Memory with Debug Info

mem2 同样采用系统的 malloc/free/realloc 来分配内存,但在其基础上增加了额外的调试信息,可以帮助检测内存泄漏 (HOW?) 和内存的其他错误。

3.1 sqlite3MemMalloc()

每块内存的布局如下:

mem2_allocation.png

  • Title
    Title 是一个用户设置的字符串(up to 100 bytes),其值通过 sqlite3MemdebugSettitle() 设置到全局的 mem 静态变量中,并在 sqlite3MemMalloc() 中拷贝至每一个 block 中,并在 sqlite3MemdebugDump() 中输出到指定文件里。
  • Backtrace Pointers
    包含若干 backtrace 的指针,backtrace 的数量由 mem.nBacktrace 指定。
  • MemBlockHdr
    1: struct MemBlockHdr {
    2:   i64 iSize;                          /* Size of this allocation */
    3:   struct MemBlockHdr *pNext, *pPrev;  /* Linked list of all unfreed memory */
    4:   char nBacktrace;                    /* Number of backtraces on this alloc */
    5:   char nBacktraceSlots;               /* Available backtrace slots */
    6:   u8 nTitle;                          /* Bytes of title; includes '\0' */
    7:   u8 eType;                           /* Allocation type code */
    8:   int iForeGuard;                     /* Guard word for sanity */
    9: };
    
  • allocation
    allocationmem2 的用户能真正使用的内存块。改块在分配成功后会用随机数来填充。
  • EndGuard
    EndGuardMemBlockHdr.iForeGuard 分别作为 allocation 的前后标记,将会在若干检查中用到,其值分别为:
    1: /*
    2:  ** Guard words
    3:  */
    4: #define FOREGUARD 0x80F5E153
    5: #define REARGUARD 0xE4676B53
    
  • mem
    mem2 中另有一个静态的 mem 变量, 其中有指向分配的 MemBlockHdr 指针:
     1: /*
     2: ** All of the static variables used by this module are collected
     3: ** into a single structure named "mem".  This is to keep the
     4: ** static variables organized and to reduce namespace pollution
     5: ** when this module is combined with other in the amalgamation.
     6: */
     7: static struct {
     8: 
     9:     /*
    10:     ** Mutex to control access to the memory allocation subsystem.
    11:     */
    12:     sqlite3_mutex *mutex;
    13: 
    14:     /*
    15:     ** Head and tail of a linked list of all outstanding allocations
    16:     */
    17:     struct MemBlockHdr *pFirst;
    18:     struct MemBlockHdr *pLast;
    19: 
    20:     /*
    21:     ** The number of levels of backtrace to save in new allocations.
    22:     */
    23:     int nBacktrace;
    24:     void (*xBacktrace)(int, int, void **);
    25: 
    26:     /*
    27:     ** Title text to insert in front of each block
    28:     */
    29:     int nTitle;        /* Bytes of zTitle to save.  Includes '\0' and padding */
    30:     char zTitle[100];  /* The title text */
    31: 
    32:     /*
    33:     ** sqlite3MallocDisallow() increments the following counter.
    34:     ** sqlite3MallocAllow() decrements it.
    35:     */
    36:     int disallow; /* Do not allow memory allocation */
    37: 
    38:     /*
    39:     ** Gather statistics on the sizes of memory allocations.
    40:     ** nAlloc[i] is the number of allocation attempts of i*8
    41:     ** bytes.  i==NCSIZE is the number of allocation attempts for
    42:     ** sizes more than NCSIZE*8 bytes.
    43:     */
    44:     int nAlloc[NCSIZE];      /* Total number of allocations */
    45:     int nCurrent[NCSIZE];    /* Current number of allocations */
    46:     int mxCurrent[NCSIZE];   /* Highwater mark for nCurrent */
    47: 
    48: } mem;
    

    mem_2_mem.png

3.2 sqlite3MemdebugDump()

用于将已经分配的资源 dump 到指定的文件中。

4 Mem3

mem3 不使用 malloc/free ,而是从预先分好的内存中( sqlite3GlobalConfig.pHeap )动态规划。整个 Heap 被分成 N 个 chunk ( N = size_of_Heap/sizeof(Mem3Block)):

 1: typedef struct Mem3Block Mem3Block;
 2: struct Mem3Block {
 3:     union {
 4:         struct {
 5:             u32 prevSize;   /* Size of previous chunk in Mem3Block elements */
 6:             u32 size4x;     /* 4x the size of current chunk in Mem3Block elements */
 7:         } hdr;
 8:         struct {
 9:             u32 next;       /* Index in mem3.aPool[] of next free chunk */
10:             u32 prev;       /* Index in mem3.aPool[] of previous free chunk */
11:         } list;
12:     } u;
13: };

所有全局信息存于静态变量 mem3 中:

 1: static SQLITE_WSD struct Mem3Global {
 2:     /*
 3:     ** Memory available for allocation. nPool is the size of the array
 4:     ** (in Mem3Blocks) pointed to by aPool less 2.
 5:     */
 6:     u32 nPool;
 7:     Mem3Block *aPool;
 8: 
 9:     /*
10:     ** True if we are evaluating an out-of-memory callback.
11:     */
12:     int alarmBusy;
13: 
14:     /*
15:     ** Mutex to control access to the memory allocation subsystem.
16:     */
17:     sqlite3_mutex *mutex;
18: 
19:     /*
20:     ** The minimum amount of free space that we have seen.
21:     */
22:     u32 mnMaster;
23: 
24:     /*
25:     ** iMaster is the index of the master chunk.  Most new allocations
26:     ** occur off of this chunk.  szMaster is the size (in Mem3Blocks)
27:     ** of the current master.  iMaster is 0 if there is not master chunk.
28:     ** The master chunk is not in either the aiHash[] or aiSmall[].
29:     */
30:     u32 iMaster;
31:     u32 szMaster;
32: 
33:     /*
34:     ** Array of lists of free blocks according to the block size
35:     ** for smaller chunks, or a hash on the block size for larger
36:     ** chunks.
37:     */
38:     u32 aiSmall[MX_SMALL-1];   /* For sizes 2 through MX_SMALL, inclusive */
39:     u32 aiHash[N_HASH];        /* For sizes MX_SMALL+1 and larger */
40: } mem3 = { 97535575 };

分配内存时,优先从 mem3->aiSmall 或者 mem3->aiHash 中寻找何时的 chunk,如果找不到,则从 mem3->aPool 中分配,并设置 block header.

回收内存时,将 chunk 链入 mem3->aiSmall 或者 mem3->aiHash

5 Mem5

mem5 遵循三条规则:

  • 分配的大小,向上取整对齐到的 2 的 N 次方
  • 如果存在两块相邻的同等大小的内存,则合并之。
  • 新内存始终从第一块空闲的内存块中分配。

5.1 memsys5Init()

与之前的几种分配方式相同,mem5 中也有一个静态变量用于记录全局信息, memsys5Init() 用于初始化它:

 1: /*
 2: ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since
 3: ** mem5.szAtom is always at least 8 and 32-bit integers are used,
 4: ** it is not actually possible to reach this limit.
 5: */
 6: #define LOGMAX 30
 7: 
 8: static SQLITE_WSD struct Mem5Global {
 9:     /*
10:     ** Memory available for allocation
11:     */
12:     int szAtom;      /* Smallest possible allocation in bytes */
13:     int nBlock;      /* Number of szAtom sized blocks in zPool */
14:     u8 *zPool;       /* Memory available to be allocated */
15: 
16:     /*
17:     ** Mutex to control access to the memory allocation subsystem.
18:     */
19:     sqlite3_mutex *mutex;
20: 
21:     /*
22:     ** Performance statistics
23:     */
24:     u64 nAlloc;         /* Total number of calls to malloc */
25:     u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
26:     u64 totalExcess;    /* Total internal fragmentation */
27:     u32 currentOut;     /* Current checkout, including internal fragmentation */
28:     u32 currentCount;   /* Current number of distinct checkouts */
29:     u32 maxOut;         /* Maximum instantaneous currentOut */
30:     u32 maxCount;       /* Maximum instantaneous currentCount */
31:     u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
32: 
33:     /*
34:     ** Lists of free blocks.  aiFreelist[0] is a list of free blocks of
35:     ** size mem5.szAtom.  aiFreelist[1] holds blocks of size szAtom*2.
36:     ** and so forth.
37:     */
38:     int aiFreelist[LOGMAX+1];
39: 
40:     /*
41:     ** Space for tracking which blocks are checked out and the size
42:     ** of each block.  One byte per block.
43:     */
44:     u8 *aCtrl;
45: 
46: } mem5;
  • zPool
    用户(程序)指定的堆。
  • szAtom
    内存分配的最小单元,其值为 sqlite3GlobalConfig.mnReq 向上取整到 2 整次幂与 Mem5Link 中的较大值。
  • aCtrl
    用于跟踪 block 使用情况的字符数组,每一个 block 都有一个对应的 ctrl
  • nBlock 由于每个 block 都需要一个额外的 byte 来记录使用信息,所以每个 block 实际的大小为: szAtom+1 ,总共可用的 block 个数为:
    1: mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
    
  • aiFreelist
    List of free blocks

    mem5_aiFreeList.png

5.2 memsys5Malloc()

  • Round nByte up to the next valid power of two
  • Make sure mem5.aiFreelist[iLogsize] contains at least one free block. If not, then split a block of the next larger power of two in order to create a new free block of size iLogsize.

上一篇     下一篇