15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2007 October 14 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The author disclaims copyright to this source code. In place of 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a legal notice, here is a blessing: 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you do good and not evil. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you find forgiveness for yourself and forgive others. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you share freely, never taking more than you give. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)************************************************************************* 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This file contains the C functions that implement a memory 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** allocation subsystem for use by SQLite. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This version of the memory allocation subsystem omits all 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** use of malloc(). The application gives SQLite a block of memory 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** before calling sqlite3_initialize() from which allocations 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** are made and returned by the xMalloc() and xRealloc() 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** implementations. Once sqlite3_initialize() has been called, 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** the amount of memory available to SQLite is fixed and cannot 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** be changed. 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This version of the memory allocation subsystem is included 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** in the build only if SQLITE_ENABLE_MEMSYS5 is defined. 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This memory allocator uses the following algorithm: 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1. All memory allocations sizes are rounded up to a power of 2. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2. If two adjacent free blocks are the halves of a larger block, 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** then the two blocks are coalesed into the single larger block. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3. New memory is allocated from the first available free block. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This algorithm is described in: J. M. Robson. "Bounds for Some Functions 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Concerning Dynamic Storage Allocation". Journal of the Association for 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Computing Machinery, Volume 21, Number 8, July 1974, pages 491-499. 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Let n be the size of the largest allocation divided by the minimum 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** allocation size (after rounding all sizes up to a power of 2.) Let M 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** be the maximum amount of memory ever outstanding at one time. Let 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** N be the total amount of memory available for allocation. Robson 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** proved that this memory allocator will never breakdown due to 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** fragmentation as long as the following constraint holds: 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** N >= M*(1 + log2(n)/2) - n + 1 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The sqlite3_status() logic tracks the maximum values of n and M so 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** that an application can, at any time, verify this constraint. 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sqliteInt.h" 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This version of the memory allocator is used only when 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** SQLITE_ENABLE_MEMSYS5 is defined. 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef SQLITE_ENABLE_MEMSYS5 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** A minimum allocation is an instance of the following structure. 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Larger allocations are an array of these structures where the 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** size of the array is a power of 2. 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The size of this object must be a power of two. That fact is 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** verified in memsys5Init(). 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef struct Mem5Link Mem5Link; 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct Mem5Link { 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int next; /* Index of next free chunk */ 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int prev; /* Index of previous free chunk */ 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Maximum size of any allocation is ((1<<LOGMAX)*mem5.szAtom). Since 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** mem5.szAtom is always at least 8 and 32-bit integers are used, 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** it is not actually possible to reach this limit. 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define LOGMAX 30 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Masks used for mem5.aCtrl[] elements. 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block */ 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define CTRL_FREE 0x20 /* True if not checked out */ 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** All of the static variables used by this module are collected 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** into a single structure named "mem5". This is to keep the 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** static variables organized and to reduce namespace pollution 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** when this module is combined with other in the amalgamation. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static SQLITE_WSD struct Mem5Global { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** Memory available for allocation 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int szAtom; /* Smallest possible allocation in bytes */ 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nBlock; /* Number of szAtom sized blocks in zPool */ 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u8 *zPool; /* Memory available to be allocated */ 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** Mutex to control access to the memory allocation subsystem. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_mutex *mutex; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** Performance statistics 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u64 nAlloc; /* Total number of calls to malloc */ 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u64 totalAlloc; /* Total of all malloc calls - includes internal frag */ 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u64 totalExcess; /* Total internal fragmentation */ 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 currentOut; /* Current checkout, including internal fragmentation */ 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 currentCount; /* Current number of distinct checkouts */ 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 maxOut; /* Maximum instantaneous currentOut */ 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 maxCount; /* Maximum instantaneous currentCount */ 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 maxRequest; /* Largest allocation (exclusive of internal frag) */ 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** Lists of free blocks. aiFreelist[0] is a list of free blocks of 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** size mem5.szAtom. aiFreelist[1] holds blocks of size szAtom*2. 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** and so forth. 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int aiFreelist[LOGMAX+1]; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** Space for tracking which blocks are checked out and the size 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** of each block. One byte per block. 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u8 *aCtrl; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} mem5; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Access the static variable through a macro for SQLITE_OMIT_WSD 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define mem5 GLOBAL(struct Mem5Global, mem5) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Assuming mem5.zPool is divided up into an array of Mem5Link 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** structures, return a pointer to the idx-th such lik. 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.szAtom])) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Unlink the chunk at mem5.aPool[i] from list it is currently 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** on. It should be found on mem5.aiFreelist[iLogsize]. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5Unlink(int i, int iLogsize){ 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int next, prev; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( i>=0 && i<mem5.nBlock ); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iLogsize>=0 && iLogsize<=LOGMAX ); 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next = MEM5LINK(i)->next; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) prev = MEM5LINK(i)->prev; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( prev<0 ){ 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aiFreelist[iLogsize] = next; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MEM5LINK(prev)->next = next; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( next>=0 ){ 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MEM5LINK(next)->prev = prev; 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Link the chunk at mem5.aPool[i] so that is on the iLogsize 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** free list. 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5Link(int i, int iLogsize){ 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int x; 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( sqlite3_mutex_held(mem5.mutex) ); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( i>=0 && i<mem5.nBlock ); 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iLogsize>=0 && iLogsize<=LOGMAX ); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize]; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MEM5LINK(i)->prev = -1; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( x>=0 ){ 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( x<mem5.nBlock ); 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MEM5LINK(x)->prev = i; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aiFreelist[iLogsize] = i; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If the STATIC_MEM mutex is not already held, obtain it now. The mutex 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** will already be held (obtained by code in malloc.c) if 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** sqlite3GlobalConfig.bMemStat is true. 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5Enter(void){ 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_mutex_enter(mem5.mutex); 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5Leave(void){ 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_mutex_leave(mem5.mutex); 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return the size of an outstanding allocation, in bytes. The 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** size returned omits the 8-byte header overhead. This only 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** works for chunks that are currently checked out. 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int memsys5Size(void *p){ 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iSize = 0; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p ){ 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i = ((u8 *)p-mem5.zPool)/mem5.szAtom; 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( i>=0 && i<mem5.nBlock ); 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iSize = mem5.szAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE)); 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iSize; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Find the first entry on the freelist iLogsize. Unlink that 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** entry and return its index. 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int memsys5UnlinkFirst(int iLogsize){ 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iFirst; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iLogsize>=0 && iLogsize<=LOGMAX ); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = iFirst = mem5.aiFreelist[iLogsize]; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iFirst>=0 ); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( i>0 ){ 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( i<iFirst ) iFirst = i; 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = MEM5LINK(i)->next; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Unlink(iFirst, iLogsize); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iFirst; 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return a block of memory of at least nBytes in size. 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return NULL if unable. Return NULL if nBytes==0. 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The caller guarantees that nByte positive. 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The caller has obtained a mutex prior to invoking this 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** routine so there is never any chance that two or more 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** threads can be in this routine at the same time. 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void *memsys5MallocUnsafe(int nByte){ 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; /* Index of a mem5.aPool[] slot */ 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iBin; /* Index into mem5.aiFreelist[] */ 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iFullSz; /* Size of allocation rounded up to power of 2 */ 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iLogsize; /* Log2 of iFullSz/POW2_MIN */ 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* nByte must be a positive */ 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( nByte>0 ); 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Keep track of the maximum allocation request. Even unfulfilled 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** requests are counted */ 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (u32)nByte>mem5.maxRequest ){ 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.maxRequest = nByte; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Abort if the requested allocation size is larger than the largest 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** power of two that we can represent using 32-bit signed integers. 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( nByte > 0x40000000 ){ 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Round nByte up to the next valid power of two */ 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(iFullSz=mem5.szAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){} 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Make sure mem5.aiFreelist[iLogsize] contains at least one free 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** block. If not, then split a block of the next larger power of 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** two in order to create a new free block of size iLogsize. 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){} 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( iBin>LOGMAX ){ 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) testcase( sqlite3GlobalConfig.xLog!=0 ); 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_log(SQLITE_NOMEM, "failed to allocate %u bytes", nByte); 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i = memsys5UnlinkFirst(iBin); 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( iBin>iLogsize ){ 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int newSize; 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iBin--; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) newSize = 1 << iBin; 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[i+newSize] = CTRL_FREE | iBin; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Link(i+newSize, iBin); 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[i] = iLogsize; 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Update allocator performance statistics. */ 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.nAlloc++; 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.totalAlloc += iFullSz; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.totalExcess += iFullSz - nByte; 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.currentCount++; 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.currentOut += iFullSz; 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount; 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut; 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Return a pointer to the allocated memory. */ 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (void*)&mem5.zPool[i*mem5.szAtom]; 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Free an outstanding memory allocation. 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5FreeUnsafe(void *pOld){ 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u32 size, iLogsize; 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iBlock; 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Set iBlock to the index of the block pointed to by pOld in 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** the array of mem5.szAtom byte blocks pointed to by mem5.zPool. 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iBlock = ((u8 *)pOld-mem5.zPool)/mem5.szAtom; 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* Check that the pointer pOld points to a valid, non-free block. */ 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iBlock>=0 && iBlock<mem5.nBlock ); 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( ((u8 *)pOld-mem5.zPool)%mem5.szAtom==0 ); 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 ); 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE; 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size = 1<<iLogsize; 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iBlock+size-1<(u32)mem5.nBlock ); 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBlock] |= CTRL_FREE; 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBlock+size-1] |= CTRL_FREE; 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( mem5.currentCount>0 ); 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( mem5.currentOut>=(size*mem5.szAtom) ); 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.currentCount--; 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.currentOut -= size*mem5.szAtom; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( mem5.currentOut>0 || mem5.currentCount==0 ); 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( mem5.currentCount>0 || mem5.currentOut==0 ); 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( ALWAYS(iLogsize<LOGMAX) ){ 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iBuddy; 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (iBlock>>iLogsize) & 1 ){ 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iBuddy = iBlock - size; 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iBuddy = iBlock + size; 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( iBuddy>=0 ); 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break; 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Unlink(iBuddy, iLogsize); 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iLogsize++; 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( iBuddy<iBlock ){ 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize; 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBlock] = 0; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iBlock = iBuddy; 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize; 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iBuddy] = 0; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) size *= 2; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Link(iBlock, iLogsize); 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Allocate nBytes of memory 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void *memsys5Malloc(int nBytes){ 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_int64 *p = 0; 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( nBytes>0 ){ 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Enter(); 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = memsys5MallocUnsafe(nBytes); 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Leave(); 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return (void*)p; 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Free memory. 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The outer layer memory allocator prevents this routine from 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** being called with pPrior==0. 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5Free(void *pPrior){ 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pPrior!=0 ); 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Enter(); 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5FreeUnsafe(pPrior); 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Leave(); 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Change the size of an existing memory allocation. 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The outer layer memory allocator prevents this routine from 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** being called with pPrior==0. 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** nBytes is always a value obtained from a prior call to 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memsys5Round(). Hence nBytes is always a non-negative power 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** of two. If nBytes==0 that means that an oversize allocation 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** (an allocation larger than 0x40000000) was requested and this 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** routine should return 0 without freeing pPrior. 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void *memsys5Realloc(void *pPrior, int nBytes){ 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nOld; 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *p; 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pPrior!=0 ); 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( (nBytes&(nBytes-1))==0 ); /* EV: R-46199-30249 */ 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( nBytes>=0 ); 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( nBytes==0 ){ 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nOld = memsys5Size(pPrior); 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( nBytes<=nOld ){ 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return pPrior; 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Enter(); 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = memsys5MallocUnsafe(nBytes); 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p ){ 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memcpy(p, pPrior, nOld); 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5FreeUnsafe(pPrior); 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Leave(); 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Round up a request size to the next valid allocation size. If 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** the allocation is too large to be handled by this allocation system, 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** return 0. 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** All allocations must be a power of two and must be expressed by a 4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 32-bit signed integer. Hence the largest allocation is 0x40000000 4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** or 1073741824 bytes. 4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int memsys5Roundup(int n){ 4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iFullSz; 4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( n > 0x40000000 ) return 0; 4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(iFullSz=mem5.szAtom; iFullSz<n; iFullSz *= 2); 4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iFullSz; 4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return the ceiling of the logarithm base 2 of iValue. 4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Examples: memsys5Log(1) -> 0 4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memsys5Log(2) -> 1 4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memsys5Log(4) -> 2 4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memsys5Log(5) -> 3 4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memsys5Log(8) -> 3 4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memsys5Log(9) -> 4 4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int memsys5Log(int iValue){ 4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iLog; 4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(iLog=0; (iLog<(int)((sizeof(int)*8)-1)) && (1<<iLog)<iValue; iLog++); 4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return iLog; 4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Initialize the memory allocator. 4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This routine is not threadsafe. The caller must be holding a mutex 4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** to prevent multiple threads from entering at the same time. 4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int memsys5Init(void *NotUsed){ 4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int ii; /* Loop counter */ 4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nByte; /* Number of bytes of memory available to this allocator */ 4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u8 *zByte; /* Memory usable by this allocator */ 4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nMinLog; /* Log base 2 of minimum allocation size in bytes */ 4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iOffset; /* An offset into mem5.aCtrl[] */ 4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UNUSED_PARAMETER(NotUsed); 4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* For the purposes of this routine, disable the mutex */ 4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.mutex = 0; 4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The size of a Mem5Link object must be a power of two. Verify that 4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** this is case. 4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( (sizeof(Mem5Link)&(sizeof(Mem5Link)-1))==0 ); 4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nByte = sqlite3GlobalConfig.nHeap; 4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) zByte = (u8*)sqlite3GlobalConfig.pHeap; 4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( zByte!=0 ); /* sqlite3_config() does not allow otherwise */ 4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* boundaries on sqlite3GlobalConfig.mnReq are enforced in sqlite3_config() */ 4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq); 4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.szAtom = (1<<nMinLog); 4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( (int)sizeof(Mem5Link)>mem5.szAtom ){ 4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.szAtom = mem5.szAtom << 1; 4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.nBlock = (nByte / (mem5.szAtom+sizeof(u8))); 4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.zPool = zByte; 4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.szAtom]; 4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(ii=0; ii<=LOGMAX; ii++){ 4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aiFreelist[ii] = -1; 4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iOffset = 0; 4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(ii=LOGMAX; ii>=0; ii--){ 4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nAlloc = (1<<ii); 4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( (iOffset+nAlloc)<=mem5.nBlock ){ 4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.aCtrl[iOffset] = ii | CTRL_FREE; 4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Link(iOffset, ii); 4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) iOffset += nAlloc; 4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert((iOffset+nAlloc)>mem5.nBlock); 5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* If a mutex is required for normal operation, allocate one */ 5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( sqlite3GlobalConfig.bMemstat==0 ){ 5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM); 5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return SQLITE_OK; 5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Deinitialize this module. 5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void memsys5Shutdown(void *NotUsed){ 5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) UNUSED_PARAMETER(NotUsed); 5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) mem5.mutex = 0; 5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef SQLITE_TEST 5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Open the file indicated and write a log of all unfreed memory 5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** allocations into that log. 5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3Memsys5Dump(const char *zFilename){ 5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) FILE *out; 5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i, j, n; 5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nMinLog; 5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( zFilename==0 || zFilename[0]==0 ){ 5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out = stdout; 5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) out = fopen(zFilename, "w"); 5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( out==0 ){ 5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(stderr, "** Unable to output memory debug output log: %s **\n", 5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) zFilename); 5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Enter(); 5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nMinLog = memsys5Log(mem5.szAtom); 5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0; i<=LOGMAX && i+nMinLog<32; i++){ 5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){} 5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "freelist items of size %d: %d\n", mem5.szAtom << i, n); 5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc); 5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc); 5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess); 5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut); 5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount); 5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut); 5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount); 5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest); 5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Leave(); 5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( out==stdout ){ 5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fflush(stdout); 5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) fclose(out); 5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This routine is the only routine in this file with external 5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** linkage. It returns a pointer to a static sqlite3_mem_methods 5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** struct populated with the memsys5 methods. 5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){ 5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static const sqlite3_mem_methods memsys5Methods = { 5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Malloc, 5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Free, 5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Realloc, 5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Size, 5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Roundup, 5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Init, 5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memsys5Shutdown, 5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }; 5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return &memsys5Methods; 5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif /* SQLITE_ENABLE_MEMSYS5 */ 582