1.概述

SQLite開發者稱它為"memsys5"，這個內存分配器的實現不依賴于malloc，實現在mem5.c里，使用時需要打開SQLITE_ENABLE_MEMSYS5編譯選項，應用程序在啟動時還要調用以下接口：

sqlite3_config(SQLITE_CONFIG_HEAP, pBuf, szBuf, mnReq);

其中pBuf為初始內存，szBuf為初始內存大小，mnReq為最小的內存申請請求。

對于動態內存分配問題、內存分配失敗問題，J.M.Robson進行過系統的研究，其結果發表在如下論文中：J. M. Robson. "Bounds for Some Functions Concerning Dynamic Storage Allocation". Journal of the Association for Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499.

我們使用下面的記號（與Robson的記號類似，但不完全等同）：

N:內存分配系統為了保證不會出現分配失敗而需要的原始內存數量。
    M: 應用程序曾經在任何時間點取出的最大內存數量。
    n: 最大內存分配與最小分配的比值。我們假設每個內存分配大小都是最小分配大小的整數倍。
    Robson證明了下面的結果：
   N = M*(1 + (log2 n)/2) - n + 1

通俗地講，Robson證明表明，為了防止內存分配失敗，任何內存分配器必須使用一個大小為N的內存池，它超過曾經使用的最大內存M乘以一個取決于n的倍數。也就是說，除非所有的內存分配都是同樣的大小，否則系統需要訪問比曾經使用的更大的內存。此外我們看到，需要的剩余內存隨著比值n的增加會迅速的增長，因此我們應該保持所有的內存分配盡可能大小相同。
    Robson證明是構造性的。他提出一個算法來計算一個分配和釋放操作系列由于內存碎片（可用內存大于1字節但小N字節）將導致分配失敗。Robson還證明如果可用內存為N或更多的字節，一個“2的冪，首次命中”的內存分配器絕不會出現內存分配失敗。

上面介紹的內容取自官網的文章“Dynamic Memory Allocation In SQLite”，memsys5使用的buddy算法正是一個“2的冪，首次命中”的內存分配器，所以不會出現內存分配失敗。

2.初始化

本文以szBuf為100000，mnReq為10來說明memsys5的實現，TCL腳本可以使用如下語句來測試：

sqlite3_shutdown

sqlite3_config_heap 100000 10

初始化時調用memsys5Init(),在memsys5中每次申請的內存必須是2的冪次方大小，所以最小的分配值mem5.szAtom應該是16而不是10：

static int memsys5Log(int iValue){
  int iLog;
  for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++);
  return iLog;
}
  nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);// mnReq為10，那么nMinLog算出來是4
  mem5.szAtom = (1<<nMinLog);// mem5.szAtom是16

然后再把總的內存大小分割成n個block

 nByte = sqlite3GlobalConfig.nHeap;
  zByte = (u8*)sqlite3GlobalConfig.pHeap;
  mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8)));
  mem5.zPool = zByte;
  mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom];

這里假設nByte是100000，那么mem5.nBlock就是5882，這里5882*16大小的內存用作內存池，還有5882個大小的內存放在mem5.aCtrl用作分配和釋放的管理。

接著對這5882個block再按2的最大冪次方進行分割，如5882分割出4096，剩余1784，1784再分割出1024，如此循環往復： 

#define LOGMAX 30
for(ii=0; ii<=LOGMAX; ii++){
    mem5.aiFreelist[ii] = -1;
  }

  iOffset = 0;
  for(ii=LOGMAX; ii>=0; ii--){
    int nAlloc = (1<<ii);
    if( (iOffset+nAlloc)<=mem5.nBlock ){
      mem5.aCtrl[iOffset] = ii | CTRL_FREE;//記錄分割后該地址的塊大小并標記為未使用
      memsys5Link(iOffset, ii);//把地址記錄到aiFreelist
      iOffset += nAlloc;
    }
    assert((iOffset+nAlloc)>mem5.nBlock);
  }

分割示意圖如下

這樣分割后，就可以用2的冪來代表內存大小了，如4096是12，1024是10，然后我們用aiFreelist來表示某個大小的塊在內存中的位置，如aiFreelist[12]=0, aiFreelist[1]=5880,如果有多個內存塊的大小相同把相同大小的塊用鏈表連接起來。

typedef struct Mem5Link Mem5Link;
struct Mem5Link {
  int next;       /* Index of next free chunk */
  int prev;       /* Index of previous free chunk */
};
#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom]))
/*
** Link the chunk at mem5.aPool[i] so that is on the iLogsize
** free list.
*/
static void memsys5Link(int i, int iLogsize){
  int x;
  assert( sqlite3_mutex_held(mem5.mutex) );
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
  //i為塊在內存中的地址，iLogsize為塊大小的2次冪
  x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
  MEM5LINK(i)->prev = -1;//新塊作為頭結點
  if( x>=0 ){
    assert( x<mem5.nBlock );
    MEM5LINK(x)->prev = i;//該大小的塊已經存在，加入鏈表
  }
  mem5.aiFreelist[iLogsize] = i;//記錄塊大小為2^Logsize的地址
}

3.內存申請

假設申請內存大小為64，首先定位滿足64字節大小的內存塊：

for(iFullSz=mem5.szAtom,iLogsize=0; iFullSz<nByte; iFullSz*=2,iLogsize++){}

得到iFullSz為64，即4個mem5.szAtom，所以冪iLogsize為2，由上面的分割可知存在2^2個block大小的塊，那么繼續搜索2^3大小的塊，直到找到為止

/* 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.
  */
  for(iBin=iLogsize; iBin<=LOGMAX && mem5.aiFreelist[iBin]<0; iBin++){}

找到后把這個塊標記為未使用，并分裂這個塊，一直分裂到最小的塊大小為2^ iLogsize

static void memsys5Unlink(int i, int iLogsize){
  int next, prev;
  assert( i>=0 && i<mem5.nBlock );
  assert( iLogsize>=0 && iLogsize<=LOGMAX );
  assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

  next = MEM5LINK(i)->next;
  prev = MEM5LINK(i)->prev;
  if( prev<0 ){
    mem5.aiFreelist[iLogsize] = next;
  }else{
    MEM5LINK(prev)->next = next;
  }
  if( next>=0 ){
    MEM5LINK(next)->prev = prev;
  }
}

i = mem5.aiFreelist[iBin];
  memsys5Unlink(i, iBin);//把這個塊從mem5.aiFreelist[iBin]鏈表中移除，然后再開始分裂
  while( iBin>iLogsize ){
    int newSize;
   /*以下為分裂操作*/
    iBin--;
    newSize = 1 << iBin;//分成2半
    mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
    memsys5Link(i+newSize, iBin);//后一半標記為未使用
  }

要記住把一個塊分裂成2塊后，這2個塊叫做buddy塊，釋放時如果2個buddy塊都為空閑，那么會合并成一塊。

4.內存釋放

這部分是最復雜的，用到了buddy算法，當內存多次分配后，每個原始的塊已經被分裂過很多次，釋放時要找到對應的buddy塊進行合并。合并完成的塊再插入到mem5.aiFreelist鏈表里。

釋放的塊根據一定的特征來判斷自己在分裂的前端還是分裂的后端來尋找自己的buddy。

/*
** Free an outstanding memory allocation.
*/
static void memsys5FreeUnsafe(void *pOld){
  u32 size, iLogsize;
  int iBlock;

  /* Set iBlock to the index of the block pointed to by pOld in 
  ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool.
  */
  iBlock = (int)(((u8 *)pOld-mem5.zPool)/mem5.szAtom);//獲取釋放塊的地址

  /* Check that the pointer pOld points to a valid, non-free block. */
  assert( iBlock>=0 && iBlock<mem5.nBlock );
  assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 );
  assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );

  iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;//獲取2的冪次
  size = 1<<iLogsize;//獲取塊的大小
  assert( iBlock+size-1<(u32)mem5.nBlock );

  mem5.aCtrl[iBlock] |= CTRL_FREE;
  mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;


  mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;//標記塊為未使用
  while( ALWAYS(iLogsize<LOGMAX) ){
    int iBuddy;
    if( (iBlock>>iLogsize) & 1 ){//釋放的塊在后端
      iBuddy = iBlock - size;//獲取前端buddy
      assert( iBuddy>=0 );
    }else{//釋放的塊在前端
      iBuddy = iBlock + size;//獲取后端buddy
      if( iBuddy>=mem5.nBlock ) break;//到內存池的邊界
    }
    if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;//buddy仍未釋放
    memsys5Unlink(iBuddy, iLogsize);//把buddy從aiFreelist鏈表移除
    iLogsize++;//合并后大小為原來2倍
    if( iBuddy<iBlock ){// iBuddy為前端
      mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBlock] = 0;
      iBlock = iBuddy;
    }else{// iBlock為前端
      mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
      mem5.aCtrl[iBuddy] = 0;
    }
    size *= 2;//合并后再繼續下一次合并
  }

參考資料：

【1】SQLite剖析(9)：動態內存分配

http://blog.csdn.net/zhoudaxia/article/details/8257784