mem5.c
上传用户:sunhongbo
上传日期:2022-01-25
资源大小:3010k
文件大小:13k
源码类别:

数据库系统

开发平台:

C/C++

  1. /*
  2. ** 2007 October 14
  3. **
  4. ** The author disclaims copyright to this source code.  In place of
  5. ** a legal notice, here is a blessing:
  6. **
  7. **    May you do good and not evil.
  8. **    May you find forgiveness for yourself and forgive others.
  9. **    May you share freely, never taking more than you give.
  10. **
  11. *************************************************************************
  12. ** This file contains the C functions that implement a memory
  13. ** allocation subsystem for use by SQLite. 
  14. **
  15. ** This version of the memory allocation subsystem omits all
  16. ** use of malloc().  All dynamically allocatable memory is
  17. ** contained in a static array, mem.aPool[].  The size of this
  18. ** fixed memory pool is SQLITE_POW2_MEMORY_SIZE bytes.
  19. **
  20. ** This version of the memory allocation subsystem is used if
  21. ** and only if SQLITE_POW2_MEMORY_SIZE is defined.
  22. **
  23. ** $Id: mem5.c,v 1.4 2008/02/19 15:15:16 drh Exp $
  24. */
  25. #include "sqliteInt.h"
  26. /*
  27. ** This version of the memory allocator is used only when 
  28. ** SQLITE_POW2_MEMORY_SIZE is defined.
  29. */
  30. #ifdef SQLITE_POW2_MEMORY_SIZE
  31. /*
  32. ** Log2 of the minimum size of an allocation.  For example, if
  33. ** 4 then all allocations will be rounded up to at least 16 bytes.
  34. ** If 5 then all allocations will be rounded up to at least 32 bytes.
  35. */
  36. #ifndef SQLITE_POW2_LOGMIN
  37. # define SQLITE_POW2_LOGMIN 6
  38. #endif
  39. #define POW2_MIN (1<<SQLITE_POW2_LOGMIN)
  40. /*
  41. ** Log2 of the maximum size of an allocation.
  42. */
  43. #ifndef SQLITE_POW2_LOGMAX
  44. # define SQLITE_POW2_LOGMAX 18
  45. #endif
  46. #define POW2_MAX (((unsigned int)1)<<SQLITE_POW2_LOGMAX)
  47. /*
  48. ** Number of distinct allocation sizes.
  49. */
  50. #define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)
  51. /*
  52. ** A minimum allocation is an instance of the following structure.
  53. ** Larger allocations are an array of these structures where the
  54. ** size of the array is a power of 2.
  55. */
  56. typedef struct Mem5Block Mem5Block;
  57. struct Mem5Block {
  58.   union {
  59.     char aData[POW2_MIN];
  60.     struct {
  61.       int next;       /* Index in mem.aPool[] of next free chunk */
  62.       int prev;       /* Index in mem.aPool[] of previous free chunk */
  63.     } list;
  64.   } u;
  65. };
  66. /*
  67. ** Number of blocks of memory available for allocation.
  68. */
  69. #define NBLOCK (SQLITE_POW2_MEMORY_SIZE/POW2_MIN)
  70. /*
  71. ** The size in blocks of an POW2_MAX allocation
  72. */
  73. #define SZ_MAX (1<<(NSIZE-1))
  74. /*
  75. ** Masks used for mem.aCtrl[] elements.
  76. */
  77. #define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */
  78. #define CTRL_FREE     0x20    /* True if not checked out */
  79. /*
  80. ** All of the static variables used by this module are collected
  81. ** into a single structure named "mem".  This is to keep the
  82. ** static variables organized and to reduce namespace pollution
  83. ** when this module is combined with other in the amalgamation.
  84. */
  85. static struct {
  86.   /*
  87.   ** The alarm callback and its arguments.  The mem.mutex lock will
  88.   ** be held while the callback is running.  Recursive calls into
  89.   ** the memory subsystem are allowed, but no new callbacks will be
  90.   ** issued.  The alarmBusy variable is set to prevent recursive
  91.   ** callbacks.
  92.   */
  93.   sqlite3_int64 alarmThreshold;
  94.   void (*alarmCallback)(void*, sqlite3_int64,int);
  95.   void *alarmArg;
  96.   int alarmBusy;
  97.   
  98.   /*
  99.   ** Mutex to control access to the memory allocation subsystem.
  100.   */
  101.   sqlite3_mutex *mutex;
  102.   /*
  103.   ** Performance statistics
  104.   */
  105.   u64 nAlloc;         /* Total number of calls to malloc */
  106.   u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
  107.   u64 totalExcess;    /* Total internal fragmentation */
  108.   u32 currentOut;     /* Current checkout, including internal fragmentation */
  109.   u32 currentCount;   /* Current number of distinct checkouts */
  110.   u32 maxOut;         /* Maximum instantaneous currentOut */
  111.   u32 maxCount;       /* Maximum instantaneous currentCount */
  112.   u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
  113.   
  114.   /*
  115.   ** Lists of free blocks of various sizes.
  116.   */
  117.   int aiFreelist[NSIZE];
  118.   /*
  119.   ** Space for tracking which blocks are checked out and the size
  120.   ** of each block.  One byte per block.
  121.   */
  122.   u8 aCtrl[NBLOCK];
  123.   /*
  124.   ** Memory available for allocation
  125.   */
  126.   Mem5Block aPool[NBLOCK];
  127. } mem;
  128. /*
  129. ** Unlink the chunk at mem.aPool[i] from list it is currently
  130. ** on.  It should be found on mem.aiFreelist[iLogsize].
  131. */
  132. static void memsys5Unlink(int i, int iLogsize){
  133.   int next, prev;
  134.   assert( i>=0 && i<NBLOCK );
  135.   assert( iLogsize>=0 && iLogsize<NSIZE );
  136.   assert( (mem.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
  137.   assert( sqlite3_mutex_held(mem.mutex) );
  138.   next = mem.aPool[i].u.list.next;
  139.   prev = mem.aPool[i].u.list.prev;
  140.   if( prev<0 ){
  141.     mem.aiFreelist[iLogsize] = next;
  142.   }else{
  143.     mem.aPool[prev].u.list.next = next;
  144.   }
  145.   if( next>=0 ){
  146.     mem.aPool[next].u.list.prev = prev;
  147.   }
  148. }
  149. /*
  150. ** Link the chunk at mem.aPool[i] so that is on the iLogsize
  151. ** free list.
  152. */
  153. static void memsys5Link(int i, int iLogsize){
  154.   int x;
  155.   assert( sqlite3_mutex_held(mem.mutex) );
  156.   assert( i>=0 && i<NBLOCK );
  157.   assert( iLogsize>=0 && iLogsize<NSIZE );
  158.   assert( (mem.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
  159.   mem.aPool[i].u.list.next = x = mem.aiFreelist[iLogsize];
  160.   mem.aPool[i].u.list.prev = -1;
  161.   if( x>=0 ){
  162.     assert( x<NBLOCK );
  163.     mem.aPool[x].u.list.prev = i;
  164.   }
  165.   mem.aiFreelist[iLogsize] = i;
  166. }
  167. /*
  168. ** Enter the mutex mem.mutex. Allocate it if it is not already allocated.
  169. **
  170. ** Also:  Initialize the memory allocation subsystem the first time
  171. ** this routine is called.
  172. */
  173. static void memsys5Enter(void){
  174.   if( mem.mutex==0 ){
  175.     int i;
  176.     assert( sizeof(Mem5Block)==POW2_MIN );
  177.     assert( (SQLITE_POW2_MEMORY_SIZE % POW2_MAX)==0 );
  178.     assert( SQLITE_POW2_MEMORY_SIZE>=POW2_MAX );
  179.     mem.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM);
  180.     sqlite3_mutex_enter(mem.mutex);
  181.     for(i=0; i<NSIZE; i++) mem.aiFreelist[i] = -1;
  182.     for(i=0; i<=NBLOCK-SZ_MAX; i += SZ_MAX){
  183.       mem.aCtrl[i] = (NSIZE-1) | CTRL_FREE;
  184.       memsys5Link(i, NSIZE-1);
  185.     }
  186.   }else{
  187.     sqlite3_mutex_enter(mem.mutex);
  188.   }
  189. }
  190. /*
  191. ** Return the amount of memory currently checked out.
  192. */
  193. sqlite3_int64 sqlite3_memory_used(void){
  194.   return mem.currentOut;
  195. }
  196. /*
  197. ** Return the maximum amount of memory that has ever been
  198. ** checked out since either the beginning of this process
  199. ** or since the most recent reset.
  200. */
  201. sqlite3_int64 sqlite3_memory_highwater(int resetFlag){
  202.   sqlite3_int64 n;
  203.   memsys5Enter();
  204.   n = mem.maxOut;
  205.   if( resetFlag ){
  206.     mem.maxOut = mem.currentOut;
  207.   }
  208.   sqlite3_mutex_leave(mem.mutex);  
  209.   return n;
  210. }
  211. /*
  212. ** Trigger the alarm 
  213. */
  214. static void memsys5Alarm(int nByte){
  215.   void (*xCallback)(void*,sqlite3_int64,int);
  216.   sqlite3_int64 nowUsed;
  217.   void *pArg;
  218.   if( mem.alarmCallback==0 || mem.alarmBusy  ) return;
  219.   mem.alarmBusy = 1;
  220.   xCallback = mem.alarmCallback;
  221.   nowUsed = mem.currentOut;
  222.   pArg = mem.alarmArg;
  223.   sqlite3_mutex_leave(mem.mutex);
  224.   xCallback(pArg, nowUsed, nByte);
  225.   sqlite3_mutex_enter(mem.mutex);
  226.   mem.alarmBusy = 0;
  227. }
  228. /*
  229. ** Change the alarm callback.
  230. **
  231. ** This is a no-op for the static memory allocator.  The purpose
  232. ** of the memory alarm is to support sqlite3_soft_heap_limit().
  233. ** But with this memory allocator, the soft_heap_limit is really
  234. ** a hard limit that is fixed at SQLITE_POW2_MEMORY_SIZE.
  235. */
  236. int sqlite3_memory_alarm(
  237.   void(*xCallback)(void *pArg, sqlite3_int64 used,int N),
  238.   void *pArg,
  239.   sqlite3_int64 iThreshold
  240. ){
  241.   memsys5Enter();
  242.   mem.alarmCallback = xCallback;
  243.   mem.alarmArg = pArg;
  244.   mem.alarmThreshold = iThreshold;
  245.   sqlite3_mutex_leave(mem.mutex);
  246.   return SQLITE_OK;
  247. }
  248. /*
  249. ** Return the size of an outstanding allocation, in bytes.  The
  250. ** size returned omits the 8-byte header overhead.  This only
  251. ** works for chunks that are currently checked out.
  252. */
  253. int sqlite3MallocSize(void *p){
  254.   int iSize = 0;
  255.   if( p ){
  256.     int i = ((Mem5Block*)p) - mem.aPool;
  257.     assert( i>=0 && i<NBLOCK );
  258.     iSize = 1 << ((mem.aCtrl[i]&CTRL_LOGSIZE) + SQLITE_POW2_LOGMIN);
  259.   }
  260.   return iSize;
  261. }
  262. /*
  263. ** Find the first entry on the freelist iLogsize.  Unlink that
  264. ** entry and return its index. 
  265. */
  266. static int memsys5UnlinkFirst(int iLogsize){
  267.   int i;
  268.   int iFirst;
  269.   assert( iLogsize>=0 && iLogsize<NSIZE );
  270.   i = iFirst = mem.aiFreelist[iLogsize];
  271.   assert( iFirst>=0 );
  272.   while( i>0 ){
  273.     if( i<iFirst ) iFirst = i;
  274.     i = mem.aPool[i].u.list.next;
  275.   }
  276.   memsys5Unlink(iFirst, iLogsize);
  277.   return iFirst;
  278. }
  279. /*
  280. ** Return a block of memory of at least nBytes in size.
  281. ** Return NULL if unable.
  282. */
  283. static void *memsys5Malloc(int nByte){
  284.   int i;           /* Index of a mem.aPool[] slot */
  285.   int iBin;        /* Index into mem.aiFreelist[] */
  286.   int iFullSz;     /* Size of allocation rounded up to power of 2 */
  287.   int iLogsize;    /* Log2 of iFullSz/POW2_MIN */
  288.   assert( sqlite3_mutex_held(mem.mutex) );
  289.   /* Keep track of the maximum allocation request.  Even unfulfilled
  290.   ** requests are counted */
  291.   if( nByte>mem.maxRequest ){
  292.     mem.maxRequest = nByte;
  293.   }
  294.   /* Simulate a memory allocation fault */
  295.   if( sqlite3FaultStep(SQLITE_FAULTINJECTOR_MALLOC) ) return 0;
  296.   /* Round nByte up to the next valid power of two */
  297.   if( nByte>POW2_MAX ) return 0;
  298.   for(iFullSz=POW2_MIN, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
  299.   /* If we will be over the memory alarm threshold after this allocation,
  300.   ** then trigger the memory overflow alarm */
  301.   if( mem.alarmCallback!=0 && mem.currentOut+iFullSz>=mem.alarmThreshold ){
  302.     memsys5Alarm(iFullSz);
  303.   }
  304.   /* Make sure mem.aiFreelist[iLogsize] contains at least one free
  305.   ** block.  If not, then split a block of the next larger power of
  306.   ** two in order to create a new free block of size iLogsize.
  307.   */
  308.   for(iBin=iLogsize; mem.aiFreelist[iBin]<0 && iBin<NSIZE; iBin++){}
  309.   if( iBin>=NSIZE ) return 0;
  310.   i = memsys5UnlinkFirst(iBin);
  311.   while( iBin>iLogsize ){
  312.     int newSize;
  313.     iBin--;
  314.     newSize = 1 << iBin;
  315.     mem.aCtrl[i+newSize] = CTRL_FREE | iBin;
  316.     memsys5Link(i+newSize, iBin);
  317.   }
  318.   mem.aCtrl[i] = iLogsize;
  319.   /* Update allocator performance statistics. */
  320.   mem.nAlloc++;
  321.   mem.totalAlloc += iFullSz;
  322.   mem.totalExcess += iFullSz - nByte;
  323.   mem.currentCount++;
  324.   mem.currentOut += iFullSz;
  325.   if( mem.maxCount<mem.currentCount ) mem.maxCount = mem.currentCount;
  326.   if( mem.maxOut<mem.currentOut ) mem.maxOut = mem.currentOut;
  327.   /* Return a pointer to the allocated memory. */
  328.   return (void*)&mem.aPool[i];
  329. }
  330. /*
  331. ** Free an outstanding memory allocation.
  332. */
  333. void memsys5Free(void *pOld){
  334.   u32 size, iLogsize;
  335.   int i;
  336.   i = ((Mem5Block*)pOld) - mem.aPool;
  337.   assert( sqlite3_mutex_held(mem.mutex) );
  338.   assert( i>=0 && i<NBLOCK );
  339.   assert( (mem.aCtrl[i] & CTRL_FREE)==0 );
  340.   iLogsize = mem.aCtrl[i] & CTRL_LOGSIZE;
  341.   size = 1<<iLogsize;
  342.   assert( i+size-1<NBLOCK );
  343.   mem.aCtrl[i] |= CTRL_FREE;
  344.   mem.aCtrl[i+size-1] |= CTRL_FREE;
  345.   assert( mem.currentCount>0 );
  346.   assert( mem.currentOut>=0 );
  347.   mem.currentCount--;
  348.   mem.currentOut -= size*POW2_MIN;
  349.   assert( mem.currentOut>0 || mem.currentCount==0 );
  350.   assert( mem.currentCount>0 || mem.currentOut==0 );
  351.   mem.aCtrl[i] = CTRL_FREE | iLogsize;
  352.   while( iLogsize<NSIZE-1 ){
  353.     int iBuddy;
  354.     if( (i>>iLogsize) & 1 ){
  355.       iBuddy = i - size;
  356.     }else{
  357.       iBuddy = i + size;
  358.     }
  359.     assert( iBuddy>=0 && iBuddy<NBLOCK );
  360.     if( mem.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
  361.     memsys5Unlink(iBuddy, iLogsize);
  362.     iLogsize++;
  363.     if( iBuddy<i ){
  364.       mem.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
  365.       mem.aCtrl[i] = 0;
  366.       i = iBuddy;
  367.     }else{
  368.       mem.aCtrl[i] = CTRL_FREE | iLogsize;
  369.       mem.aCtrl[iBuddy] = 0;
  370.     }
  371.     size *= 2;
  372.   }
  373.   memsys5Link(i, iLogsize);
  374. }
  375. /*
  376. ** Allocate nBytes of memory
  377. */
  378. void *sqlite3_malloc(int nBytes){
  379.   sqlite3_int64 *p = 0;
  380.   if( nBytes>0 ){
  381.     memsys5Enter();
  382.     p = memsys5Malloc(nBytes);
  383.     sqlite3_mutex_leave(mem.mutex);
  384.   }
  385.   return (void*)p; 
  386. }
  387. /*
  388. ** Free memory.
  389. */
  390. void sqlite3_free(void *pPrior){
  391.   if( pPrior==0 ){
  392.     return;
  393.   }
  394.   assert( mem.mutex!=0 );
  395.   sqlite3_mutex_enter(mem.mutex);
  396.   memsys5Free(pPrior);
  397.   sqlite3_mutex_leave(mem.mutex);  
  398. }
  399. /*
  400. ** Change the size of an existing memory allocation
  401. */
  402. void *sqlite3_realloc(void *pPrior, int nBytes){
  403.   int nOld;
  404.   void *p;
  405.   if( pPrior==0 ){
  406.     return sqlite3_malloc(nBytes);
  407.   }
  408.   if( nBytes<=0 ){
  409.     sqlite3_free(pPrior);
  410.     return 0;
  411.   }
  412.   assert( mem.mutex!=0 );
  413.   nOld = sqlite3MallocSize(pPrior);
  414.   if( nBytes<=nOld ){
  415.     return pPrior;
  416.   }
  417.   sqlite3_mutex_enter(mem.mutex);
  418.   p = memsys5Malloc(nBytes);
  419.   if( p ){
  420.     memcpy(p, pPrior, nOld);
  421.     memsys5Free(pPrior);
  422.   }
  423.   sqlite3_mutex_leave(mem.mutex);
  424.   return p;
  425. }
  426. /*
  427. ** Open the file indicated and write a log of all unfreed memory 
  428. ** allocations into that log.
  429. */
  430. void sqlite3MemdebugDump(const char *zFilename){
  431. #ifdef SQLITE_DEBUG
  432.   FILE *out;
  433.   int i, j, n;
  434.   if( zFilename==0 || zFilename[0]==0 ){
  435.     out = stdout;
  436.   }else{
  437.     out = fopen(zFilename, "w");
  438.     if( out==0 ){
  439.       fprintf(stderr, "** Unable to output memory debug output log: %s **n",
  440.                       zFilename);
  441.       return;
  442.     }
  443.   }
  444.   memsys5Enter();
  445.   for(i=0; i<NSIZE; i++){
  446.     for(n=0, j=mem.aiFreelist[i]; j>=0; j = mem.aPool[j].u.list.next, n++){}
  447.     fprintf(out, "freelist items of size %d: %dn", POW2_MIN << i, n);
  448.   }
  449.   fprintf(out, "mem.nAlloc       = %llun", mem.nAlloc);
  450.   fprintf(out, "mem.totalAlloc   = %llun", mem.totalAlloc);
  451.   fprintf(out, "mem.totalExcess  = %llun", mem.totalExcess);
  452.   fprintf(out, "mem.currentOut   = %un", mem.currentOut);
  453.   fprintf(out, "mem.currentCount = %un", mem.currentCount);
  454.   fprintf(out, "mem.maxOut       = %un", mem.maxOut);
  455.   fprintf(out, "mem.maxCount     = %un", mem.maxCount);
  456.   fprintf(out, "mem.maxRequest   = %un", mem.maxRequest);
  457.   sqlite3_mutex_leave(mem.mutex);
  458.   if( out==stdout ){
  459.     fflush(stdout);
  460.   }else{
  461.     fclose(out);
  462.   }
  463. #endif
  464. }
  465. #endif /* !SQLITE_POW2_MEMORY_SIZE */