/ Check-in [16041116]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3925)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 16041116aaaa2d52a289aa02a24bef579ba60896
User & Date: drh 2007-05-05 11:48:52
Original Comment: Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3925)
Original User & Date: drh 2007-05-05 11:48:53
Context
2007-05-05
11:48
Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3926) check-in: ad549a40 user: drh tags: trunk
11:48
Refactoring. Split btreeInt.h off from btree.c. Split malloc.c off from util.c. Expect much more to follow. (CVS 3925) check-in: 16041116 user: drh tags: trunk
2007-05-04
19:16
Add documentation on the incremental vacuum feature. (CVS 3924) check-in: b3e2cdae user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to Makefile.in.

   119    119   TCC += -DSQLITE_OMIT_LOAD_EXTENSION=1
   120    120   
   121    121   # Object files for the SQLite library.
   122    122   #
   123    123   LIBOBJ = alter.lo analyze.lo attach.lo auth.lo btree.lo build.lo \
   124    124            callback.lo complete.lo date.lo \
   125    125            delete.lo expr.lo func.lo hash.lo insert.lo loadext.lo \
   126         -         main.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
          126  +         main.lo malloc.lo opcodes.lo os.lo os_unix.lo os_win.lo os_os2.lo \
   127    127            pager.lo parse.lo pragma.lo prepare.lo printf.lo random.lo \
   128    128            select.lo table.lo tokenize.lo trigger.lo update.lo \
   129    129            util.lo vacuum.lo \
   130    130            vdbe.lo vdbeapi.lo vdbeaux.lo vdbefifo.lo vdbemem.lo \
   131    131            where.lo utf.lo legacy.lo vtab.lo
   132    132   
   133    133   # All of the source code files.
................................................................................
   148    148     $(TOP)/src/func.c \
   149    149     $(TOP)/src/hash.c \
   150    150     $(TOP)/src/hash.h \
   151    151     $(TOP)/src/insert.c \
   152    152     $(TOP)/src/legacy.c \
   153    153     $(TOP)/src/loadext.c \
   154    154     $(TOP)/src/main.c \
          155  +  $(TOP)/src/mallo.c \
   155    156     $(TOP)/src/os.c \
   156    157     $(TOP)/src/os_unix.c \
   157    158     $(TOP)/src/os_win.c \
   158    159     $(TOP)/src/os_os2.c \
   159    160     $(TOP)/src/pager.c \
   160    161     $(TOP)/src/pager.h \
   161    162     $(TOP)/src/parse.y \
................................................................................
   200    201   # Source code to the test files.
   201    202   #
   202    203   TESTSRC = \
   203    204     $(TOP)/src/btree.c \
   204    205     $(TOP)/src/date.c \
   205    206     $(TOP)/src/func.c \
   206    207     $(TOP)/src/insert.c \
          208  +  $(TOP)/src/malloc.c \
   207    209     $(TOP)/src/os.c \
   208    210     $(TOP)/src/os_os2.c \
   209    211     $(TOP)/src/os_unix.c \
   210    212     $(TOP)/src/os_win.c \
   211    213     $(TOP)/src/pager.c \
   212    214     $(TOP)/src/pragma.c \
   213    215     $(TOP)/src/printf.c \
................................................................................
   234    236     $(TOP)/src/where.c
   235    237   
   236    238   # Header files used by all library source files.
   237    239   #
   238    240   HDR = \
   239    241      sqlite3.h  \
   240    242      $(TOP)/src/btree.h \
          243  +   $(TOP)/src/btreeInt.h \
   241    244      $(TOP)/src/hash.h \
   242    245      opcodes.h \
   243    246      $(TOP)/src/os.h \
   244    247      $(TOP)/src/os_common.h \
   245    248      $(TOP)/src/sqlite3ext.h \
   246    249      $(TOP)/src/sqliteInt.h  \
   247    250      $(TOP)/src/vdbe.h \
................................................................................
   362    365   
   363    366   loadext.lo:	$(TOP)/src/loadext.c $(HDR)
   364    367   	$(LTCOMPILE) -c $(TOP)/src/loadext.c
   365    368   
   366    369   main.lo:	$(TOP)/src/main.c $(HDR)
   367    370   	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/main.c
   368    371   
          372  +malloc.lo:	$(TOP)/src/malloc.c $(HDR)
          373  +	$(LTCOMPILE) $(TEMP_STORE) -c $(TOP)/src/malloc.c
          374  +
   369    375   pager.lo:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
   370    376   	$(LTCOMPILE) -c $(TOP)/src/pager.c
   371    377   
   372    378   opcodes.lo:	opcodes.c
   373    379   	$(LTCOMPILE) -c opcodes.c
   374    380   
   375    381   opcodes.c:	opcodes.h $(TOP)/mkopcodec.awk

Changes to main.mk.

    54     54   TCCX = $(TCC) $(OPTS) $(THREADSAFE) $(USLEEP) -I. -I$(TOP)/src
    55     55   
    56     56   # Object files for the SQLite library.
    57     57   #
    58     58   LIBOBJ+= alter.o analyze.o attach.o auth.o btree.o build.o \
    59     59            callback.o complete.o date.o delete.o \
    60     60            expr.o func.o hash.o insert.o loadext.o \
    61         -         main.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
           61  +         main.o malloc.o opcodes.o os.o os_os2.o os_unix.o os_win.o \
    62     62            pager.o parse.o pragma.o prepare.o printf.o random.o \
    63     63            select.o table.o tclsqlite.o tokenize.o trigger.o \
    64     64            update.o util.o vacuum.o \
    65     65            vdbe.o vdbeapi.o vdbeaux.o vdbeblob.o vdbefifo.o vdbemem.o \
    66     66            where.o utf.o legacy.o vtab.o
    67     67   
    68     68   # All of the source code files.
................................................................................
    83     83     $(TOP)/src/func.c \
    84     84     $(TOP)/src/hash.c \
    85     85     $(TOP)/src/hash.h \
    86     86     $(TOP)/src/insert.c \
    87     87     $(TOP)/src/legacy.c \
    88     88     $(TOP)/src/loadext.c \
    89     89     $(TOP)/src/main.c \
           90  +  $(TOP)/src/malloc.c \
    90     91     $(TOP)/src/os.c \
    91     92     $(TOP)/src/os_os2.c \
    92     93     $(TOP)/src/os_unix.c \
    93     94     $(TOP)/src/os_win.c \
    94     95     $(TOP)/src/pager.c \
    95     96     $(TOP)/src/pager.h \
    96     97     $(TOP)/src/parse.y \
................................................................................
   156    157   #
   157    158   TESTSRC = \
   158    159     $(TOP)/src/btree.c \
   159    160     $(TOP)/src/date.c \
   160    161     $(TOP)/src/func.c \
   161    162     $(TOP)/src/insert.c \
   162    163     $(TOP)/src/main.c \
          164  +  $(TOP)/src/malloc.c \
   163    165     $(TOP)/src/os.c \
   164    166     $(TOP)/src/os_os2.c \
   165    167     $(TOP)/src/os_unix.c \
   166    168     $(TOP)/src/os_win.c \
   167    169     $(TOP)/src/pager.c \
   168    170     $(TOP)/src/pragma.c \
   169    171     $(TOP)/src/printf.c \
................................................................................
   190    192     $(TOP)/src/where.c
   191    193   
   192    194   # Header files used by all library source files.
   193    195   #
   194    196   HDR = \
   195    197      sqlite3.h  \
   196    198      $(TOP)/src/btree.h \
          199  +   $(TOP)/src/btreeInt.h \
   197    200      $(TOP)/src/hash.h \
   198    201      opcodes.h \
   199    202      $(TOP)/src/os.h \
   200    203      $(TOP)/src/os_common.h \
   201    204      $(TOP)/src/sqlite3ext.h \
   202    205      $(TOP)/src/sqliteInt.h  \
   203    206      $(TOP)/src/vdbe.h \
................................................................................
   314    317   	$(TCCX) -c $(TOP)/src/legacy.c
   315    318   
   316    319   loadext.o:	$(TOP)/src/loadext.c $(HDR)
   317    320   	$(TCCX) -c $(TOP)/src/loadext.c
   318    321   
   319    322   main.o:	$(TOP)/src/main.c $(HDR)
   320    323   	$(TCCX) -c $(TOP)/src/main.c
          324  +
          325  +malloc.o:	$(TOP)/src/malloc.c $(HDR)
          326  +	$(TCCX) -c $(TOP)/src/malloc.c
   321    327   
   322    328   pager.o:	$(TOP)/src/pager.c $(HDR) $(TOP)/src/pager.h
   323    329   	$(TCCX) -c $(TOP)/src/pager.c
   324    330   
   325    331   opcodes.o:	opcodes.c
   326    332   	$(TCCX) -c opcodes.c
   327    333   

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.375 2007/05/04 19:03:03 danielk1977 Exp $
           12  +** $Id: btree.c,v 1.376 2007/05/05 11:48:54 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15         -** For a detailed discussion of BTrees, refer to
    16         -**
    17         -**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18         -**     "Sorting And Searching", pages 473-480. Addison-Wesley
    19         -**     Publishing Company, Reading, Massachusetts.
    20         -**
    21         -** The basic idea is that each page of the file contains N database
    22         -** entries and N+1 pointers to subpages.
    23         -**
    24         -**   ----------------------------------------------------------------
    25         -**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
    26         -**   ----------------------------------------------------------------
    27         -**
    28         -** All of the keys on the page that Ptr(0) points to have values less
    29         -** than Key(0).  All of the keys on page Ptr(1) and its subpages have
    30         -** values greater than Key(0) and less than Key(1).  All of the keys
    31         -** on Ptr(N) and its subpages have values greater than Key(N-1).  And
    32         -** so forth.
    33         -**
    34         -** Finding a particular key requires reading O(log(M)) pages from the 
    35         -** disk where M is the number of entries in the tree.
    36         -**
    37         -** In this implementation, a single file can hold one or more separate 
    38         -** BTrees.  Each BTree is identified by the index of its root page.  The
    39         -** key and data for any entry are combined to form the "payload".  A
    40         -** fixed amount of payload can be carried directly on the database
    41         -** page.  If the payload is larger than the preset amount then surplus
    42         -** bytes are stored on overflow pages.  The payload for an entry
    43         -** and the preceding pointer are combined to form a "Cell".  Each 
    44         -** page has a small header which contains the Ptr(N) pointer and other
    45         -** information such as the size of key and data.
    46         -**
    47         -** FORMAT DETAILS
    48         -**
    49         -** The file is divided into pages.  The first page is called page 1,
    50         -** the second is page 2, and so forth.  A page number of zero indicates
    51         -** "no such page".  The page size can be anything between 512 and 65536.
    52         -** Each page can be either a btree page, a freelist page or an overflow
    53         -** page.
    54         -**
    55         -** The first page is always a btree page.  The first 100 bytes of the first
    56         -** page contain a special header (the "file header") that describes the file.
    57         -** The format of the file header is as follows:
    58         -**
    59         -**   OFFSET   SIZE    DESCRIPTION
    60         -**      0      16     Header string: "SQLite format 3\000"
    61         -**     16       2     Page size in bytes.  
    62         -**     18       1     File format write version
    63         -**     19       1     File format read version
    64         -**     20       1     Bytes of unused space at the end of each page
    65         -**     21       1     Max embedded payload fraction
    66         -**     22       1     Min embedded payload fraction
    67         -**     23       1     Min leaf payload fraction
    68         -**     24       4     File change counter
    69         -**     28       4     Reserved for future use
    70         -**     32       4     First freelist page
    71         -**     36       4     Number of freelist pages in the file
    72         -**     40      60     15 4-byte meta values passed to higher layers
    73         -**
    74         -** All of the integer values are big-endian (most significant byte first).
    75         -**
    76         -** The file change counter is incremented when the database is changed more
    77         -** than once within the same second.  This counter, together with the
    78         -** modification time of the file, allows other processes to know
    79         -** when the file has changed and thus when they need to flush their
    80         -** cache.
    81         -**
    82         -** The max embedded payload fraction is the amount of the total usable
    83         -** space in a page that can be consumed by a single cell for standard
    84         -** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default
    85         -** is to limit the maximum cell size so that at least 4 cells will fit
    86         -** on one page.  Thus the default max embedded payload fraction is 64.
    87         -**
    88         -** If the payload for a cell is larger than the max payload, then extra
    89         -** payload is spilled to overflow pages.  Once an overflow page is allocated,
    90         -** as many bytes as possible are moved into the overflow pages without letting
    91         -** the cell size drop below the min embedded payload fraction.
    92         -**
    93         -** The min leaf payload fraction is like the min embedded payload fraction
    94         -** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum
    95         -** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
    96         -** not specified in the header.
    97         -**
    98         -** Each btree pages is divided into three sections:  The header, the
    99         -** cell pointer array, and the cell area area.  Page 1 also has a 100-byte
   100         -** file header that occurs before the page header.
   101         -**
   102         -**      |----------------|
   103         -**      | file header    |   100 bytes.  Page 1 only.
   104         -**      |----------------|
   105         -**      | page header    |   8 bytes for leaves.  12 bytes for interior nodes
   106         -**      |----------------|
   107         -**      | cell pointer   |   |  2 bytes per cell.  Sorted order.
   108         -**      | array          |   |  Grows downward
   109         -**      |                |   v
   110         -**      |----------------|
   111         -**      | unallocated    |
   112         -**      | space          |
   113         -**      |----------------|   ^  Grows upwards
   114         -**      | cell content   |   |  Arbitrary order interspersed with freeblocks.
   115         -**      | area           |   |  and free space fragments.
   116         -**      |----------------|
   117         -**
   118         -** The page headers looks like this:
   119         -**
   120         -**   OFFSET   SIZE     DESCRIPTION
   121         -**      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
   122         -**      1       2      byte offset to the first freeblock
   123         -**      3       2      number of cells on this page
   124         -**      5       2      first byte of the cell content area
   125         -**      7       1      number of fragmented free bytes
   126         -**      8       4      Right child (the Ptr(N) value).  Omitted on leaves.
   127         -**
   128         -** The flags define the format of this btree page.  The leaf flag means that
   129         -** this page has no children.  The zerodata flag means that this page carries
   130         -** only keys and no data.  The intkey flag means that the key is a integer
   131         -** which is stored in the key size entry of the cell header rather than in
   132         -** the payload area.
   133         -**
   134         -** The cell pointer array begins on the first byte after the page header.
   135         -** The cell pointer array contains zero or more 2-byte numbers which are
   136         -** offsets from the beginning of the page to the cell content in the cell
   137         -** content area.  The cell pointers occur in sorted order.  The system strives
   138         -** to keep free space after the last cell pointer so that new cells can
   139         -** be easily added without having to defragment the page.
   140         -**
   141         -** Cell content is stored at the very end of the page and grows toward the
   142         -** beginning of the page.
   143         -**
   144         -** Unused space within the cell content area is collected into a linked list of
   145         -** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset
   146         -** to the first freeblock is given in the header.  Freeblocks occur in
   147         -** increasing order.  Because a freeblock must be at least 4 bytes in size,
   148         -** any group of 3 or fewer unused bytes in the cell content area cannot
   149         -** exist on the freeblock chain.  A group of 3 or fewer free bytes is called
   150         -** a fragment.  The total number of bytes in all fragments is recorded.
   151         -** in the page header at offset 7.
   152         -**
   153         -**    SIZE    DESCRIPTION
   154         -**      2     Byte offset of the next freeblock
   155         -**      2     Bytes in this freeblock
   156         -**
   157         -** Cells are of variable length.  Cells are stored in the cell content area at
   158         -** the end of the page.  Pointers to the cells are in the cell pointer array
   159         -** that immediately follows the page header.  Cells is not necessarily
   160         -** contiguous or in order, but cell pointers are contiguous and in order.
   161         -**
   162         -** Cell content makes use of variable length integers.  A variable
   163         -** length integer is 1 to 9 bytes where the lower 7 bits of each 
   164         -** byte are used.  The integer consists of all bytes that have bit 8 set and
   165         -** the first byte with bit 8 clear.  The most significant byte of the integer
   166         -** appears first.  A variable-length integer may not be more than 9 bytes long.
   167         -** As a special case, all 8 bytes of the 9th byte are used as data.  This
   168         -** allows a 64-bit integer to be encoded in 9 bytes.
   169         -**
   170         -**    0x00                      becomes  0x00000000
   171         -**    0x7f                      becomes  0x0000007f
   172         -**    0x81 0x00                 becomes  0x00000080
   173         -**    0x82 0x00                 becomes  0x00000100
   174         -**    0x80 0x7f                 becomes  0x0000007f
   175         -**    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678
   176         -**    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081
   177         -**
   178         -** Variable length integers are used for rowids and to hold the number of
   179         -** bytes of key and data in a btree cell.
   180         -**
   181         -** The content of a cell looks like this:
   182         -**
   183         -**    SIZE    DESCRIPTION
   184         -**      4     Page number of the left child. Omitted if leaf flag is set.
   185         -**     var    Number of bytes of data. Omitted if the zerodata flag is set.
   186         -**     var    Number of bytes of key. Or the key itself if intkey flag is set.
   187         -**      *     Payload
   188         -**      4     First page of the overflow chain.  Omitted if no overflow
   189         -**
   190         -** Overflow pages form a linked list.  Each page except the last is completely
   191         -** filled with data (pagesize - 4 bytes).  The last page can have as little
   192         -** as 1 byte of data.
   193         -**
   194         -**    SIZE    DESCRIPTION
   195         -**      4     Page number of next overflow page
   196         -**      *     Data
   197         -**
   198         -** Freelist pages come in two subtypes: trunk pages and leaf pages.  The
   199         -** file header points to first in a linked list of trunk page.  Each trunk
   200         -** page points to multiple leaf pages.  The content of a leaf page is
   201         -** unspecified.  A trunk page looks like this:
   202         -**
   203         -**    SIZE    DESCRIPTION
   204         -**      4     Page number of next trunk page
   205         -**      4     Number of leaf pointers on this page
   206         -**      *     zero or more pages numbers of leaves
   207         -*/
   208         -#include "sqliteInt.h"
   209         -#include "pager.h"
   210         -#include "btree.h"
   211         -#include "os.h"
   212         -#include <assert.h>
   213         -
   214         -/* Round up a number to the next larger multiple of 8.  This is used
   215         -** to force 8-byte alignment on 64-bit architectures.
   216         -*/
   217         -#define ROUND8(x)   ((x+7)&~7)
   218         -
   219         -
   220         -/* The following value is the maximum cell size assuming a maximum page
   221         -** size give above.
   222         -*/
   223         -#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)
   224         -
   225         -/* The maximum number of cells on a single page of the database.  This
   226         -** assumes a minimum cell size of 3 bytes.  Such small cells will be
   227         -** exceedingly rare, but they are possible.
   228         -*/
   229         -#define MX_CELL(pBt) ((pBt->pageSize-8)/3)
   230         -
   231         -/* Forward declarations */
   232         -typedef struct MemPage MemPage;
   233         -typedef struct BtLock BtLock;
   234         -
   235         -/*
   236         -** This is a magic string that appears at the beginning of every
   237         -** SQLite database in order to identify the file as a real database.
   238         -**
   239         -** You can change this value at compile-time by specifying a
   240         -** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
   241         -** header must be exactly 16 bytes including the zero-terminator so
   242         -** the string itself should be 15 characters long.  If you change
   243         -** the header, then your custom library will not be able to read 
   244         -** databases generated by the standard tools and the standard tools
   245         -** will not be able to read databases created by your custom library.
   246         -*/
   247         -#ifndef SQLITE_FILE_HEADER /* 123456789 123456 */
   248         -#  define SQLITE_FILE_HEADER "SQLite format 3"
   249         -#endif
           15  +** See the header comment on "btreeInt.h" for additional information.
           16  +** Including a description of file format and an overview of operation.
           17  +*/
           18  +#include "btreeInt.h"
           19  +
           20  +/*
           21  +** The header string that appears at the beginning of every
           22  +** SQLite database.
           23  +*/
   250     24   static const char zMagicHeader[] = SQLITE_FILE_HEADER;
   251     25   
   252         -/*
   253         -** Page type flags.  An ORed combination of these flags appear as the
   254         -** first byte of every BTree page.
   255         -*/
   256         -#define PTF_INTKEY    0x01
   257         -#define PTF_ZERODATA  0x02
   258         -#define PTF_LEAFDATA  0x04
   259         -#define PTF_LEAF      0x08
   260         -
   261         -/*
   262         -** As each page of the file is loaded into memory, an instance of the following
   263         -** structure is appended and initialized to zero.  This structure stores
   264         -** information about the page that is decoded from the raw file page.
   265         -**
   266         -** The pParent field points back to the parent page.  This allows us to
   267         -** walk up the BTree from any leaf to the root.  Care must be taken to
   268         -** unref() the parent page pointer when this page is no longer referenced.
   269         -** The pageDestructor() routine handles that chore.
   270         -*/
   271         -struct MemPage {
   272         -  u8 isInit;           /* True if previously initialized. MUST BE FIRST! */
   273         -  u8 idxShift;         /* True if Cell indices have changed */
   274         -  u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */
   275         -  u8 intKey;           /* True if intkey flag is set */
   276         -  u8 leaf;             /* True if leaf flag is set */
   277         -  u8 zeroData;         /* True if table stores keys only */
   278         -  u8 leafData;         /* True if tables stores data on leaves only */
   279         -  u8 hasData;          /* True if this page stores data */
   280         -  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
   281         -  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
   282         -  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
   283         -  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
   284         -  u16 cellOffset;      /* Index in aData of first cell pointer */
   285         -  u16 idxParent;       /* Index in parent of this node */
   286         -  u16 nFree;           /* Number of free bytes on the page */
   287         -  u16 nCell;           /* Number of cells on this page, local and ovfl */
   288         -  struct _OvflCell {   /* Cells that will not fit on aData[] */
   289         -    u8 *pCell;          /* Pointers to the body of the overflow cell */
   290         -    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
   291         -  } aOvfl[5];
   292         -  BtShared *pBt;       /* Pointer back to BTree structure */
   293         -  u8 *aData;           /* Pointer back to the start of the page */
   294         -  DbPage *pDbPage;     /* Pager page handle */
   295         -  Pgno pgno;           /* Page number for this page */
   296         -  MemPage *pParent;    /* The parent of this page.  NULL for root */
   297         -};
   298         -
   299         -/*
   300         -** The in-memory image of a disk page has the auxiliary information appended
   301         -** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
   302         -** that extra information.
   303         -*/
   304         -#define EXTRA_SIZE sizeof(MemPage)
   305         -
   306         -/* Btree handle */
   307         -struct Btree {
   308         -  sqlite3 *pSqlite;
   309         -  BtShared *pBt;
   310         -  u8 inTrans;            /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
   311         -};
   312         -
   313         -/*
   314         -** Btree.inTrans may take one of the following values.
   315         -**
   316         -** If the shared-data extension is enabled, there may be multiple users
   317         -** of the Btree structure. At most one of these may open a write transaction,
   318         -** but any number may have active read transactions. Variable Btree.pDb 
   319         -** points to the handle that owns any current write-transaction.
   320         -*/
   321         -#define TRANS_NONE  0
   322         -#define TRANS_READ  1
   323         -#define TRANS_WRITE 2
   324         -
   325         -/*
   326         -** Everything we need to know about an open database
   327         -*/
   328         -struct BtShared {
   329         -  Pager *pPager;        /* The page cache */
   330         -  BtCursor *pCursor;    /* A list of all open cursors */
   331         -  MemPage *pPage1;      /* First page of the database */
   332         -  u8 inStmt;            /* True if we are in a statement subtransaction */
   333         -  u8 readOnly;          /* True if the underlying file is readonly */
   334         -  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
   335         -  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
   336         -  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
   337         -  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
   338         -#ifndef SQLITE_OMIT_AUTOVACUUM
   339         -  u8 autoVacuum;        /* True if auto-vacuum is enabled */
   340         -  u8 incrVacuum;        /* True if incr-vacuum is enabled */
   341         -  Pgno nTrunc;          /* Non-zero if the db will be truncated (incr vacuum) */
   342         -#endif
   343         -  u16 pageSize;         /* Total number of bytes on a page */
   344         -  u16 usableSize;       /* Number of usable bytes on each page */
   345         -  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
   346         -  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
   347         -  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
   348         -  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
   349         -  BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */
   350         -  u8 inTransaction;     /* Transaction state */
   351         -  int nRef;             /* Number of references to this structure */
   352         -  int nTransaction;     /* Number of open transactions (read + write) */
   353         -  void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */
   354         -  void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */
   355         -#ifndef SQLITE_OMIT_SHARED_CACHE
   356         -  BtLock *pLock;        /* List of locks held on this shared-btree struct */
   357         -  BtShared *pNext;      /* Next in ThreadData.pBtree linked list */
   358         -#endif
   359         -};
   360         -
   361         -/*
   362         -** An instance of the following structure is used to hold information
   363         -** about a cell.  The parseCellPtr() function fills in this structure
   364         -** based on information extract from the raw disk page.
   365         -*/
   366         -typedef struct CellInfo CellInfo;
   367         -struct CellInfo {
   368         -  u8 *pCell;     /* Pointer to the start of cell content */
   369         -  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
   370         -  u32 nData;     /* Number of bytes of data */
   371         -  u32 nPayload;  /* Total amount of payload */
   372         -  u16 nHeader;   /* Size of the cell content header in bytes */
   373         -  u16 nLocal;    /* Amount of payload held locally */
   374         -  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
   375         -  u16 nSize;     /* Size of the cell content on the main b-tree page */
   376         -};
   377         -
   378         -/*
   379         -** A cursor is a pointer to a particular entry in the BTree.
   380         -** The entry is identified by its MemPage and the index in
   381         -** MemPage.aCell[] of the entry.
   382         -*/
   383         -struct BtCursor {
   384         -  Btree *pBtree;            /* The Btree to which this cursor belongs */
   385         -  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
   386         -  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
   387         -  void *pArg;               /* First arg to xCompare() */
   388         -  Pgno pgnoRoot;            /* The root page of this tree */
   389         -  MemPage *pPage;           /* Page that contains the entry */
   390         -  int idx;                  /* Index of the entry in pPage->aCell[] */
   391         -  CellInfo info;            /* A parse of the cell we are pointing at */
   392         -  u8 wrFlag;                /* True if writable */
   393         -  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
   394         -  void *pKey;      /* Saved key that was cursor's last known position */
   395         -  i64 nKey;        /* Size of pKey, or last integer key */
   396         -  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
   397         -#ifndef SQLITE_OMIT_INCRBLOB
   398         -  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
   399         -  Pgno *aOverflow;          /* Cache of overflow page locations */
   400         -#endif
   401         -};
   402         -
   403         -/*
   404         -** Potential values for BtCursor.eState.
   405         -**
   406         -** CURSOR_VALID:
   407         -**   Cursor points to a valid entry. getPayload() etc. may be called.
   408         -**
   409         -** CURSOR_INVALID:
   410         -**   Cursor does not point to a valid entry. This can happen (for example) 
   411         -**   because the table is empty or because BtreeCursorFirst() has not been
   412         -**   called.
   413         -**
   414         -** CURSOR_REQUIRESEEK:
   415         -**   The table that this cursor was opened on still exists, but has been 
   416         -**   modified since the cursor was last used. The cursor position is saved
   417         -**   in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in 
   418         -**   this state, restoreOrClearCursorPosition() can be called to attempt to
   419         -**   seek the cursor to the saved position.
   420         -*/
   421         -#define CURSOR_INVALID           0
   422         -#define CURSOR_VALID             1
   423         -#define CURSOR_REQUIRESEEK       2
   424         -
   425         -/*
   426         -** The TRACE macro will print high-level status information about the
   427         -** btree operation when the global variable sqlite3_btree_trace is
   428         -** enabled.
           26  +
           27  +/*
           28  +** Set this global variable to 1 to enable tracing using the TRACE
           29  +** macro.
   429     30   */
   430     31   #if SQLITE_TEST
   431         -# define TRACE(X)   if( sqlite3_btree_trace )\
   432         -/*                        { sqlite3DebugPrintf X; fflush(stdout); } */ \
   433         -{ printf X; fflush(stdout); }
   434     32   int sqlite3_btree_trace=0;  /* True to enable tracing */
   435         -#else
   436         -# define TRACE(X)
   437     33   #endif
   438     34   
   439     35   /*
   440     36   ** Forward declaration
   441     37   */
   442     38   static int checkReadLocks(Btree*,Pgno,BtCursor*);
   443     39   
   444         -/*
   445         -** Read or write a two- and four-byte big-endian integer values.
   446         -*/
   447         -static u32 get2byte(unsigned char *p){
   448         -  return (p[0]<<8) | p[1];
   449         -}
   450         -static u32 get4byte(unsigned char *p){
   451         -  return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
   452         -}
   453         -static void put2byte(unsigned char *p, u32 v){
   454         -  p[0] = v>>8;
   455         -  p[1] = v;
   456         -}
   457         -static void put4byte(unsigned char *p, u32 v){
   458         -  p[0] = v>>24;
   459         -  p[1] = v>>16;
   460         -  p[2] = v>>8;
   461         -  p[3] = v;
   462         -}
   463         -
   464         -/*
   465         -** Routines to read and write variable-length integers.  These used to
   466         -** be defined locally, but now we use the varint routines in the util.c
   467         -** file.
   468         -*/
   469         -#define getVarint    sqlite3GetVarint
   470         -/* #define getVarint32  sqlite3GetVarint32 */
   471         -#define getVarint32(A,B)  ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))
   472         -#define putVarint    sqlite3PutVarint
   473         -
   474         -/* The database page the PENDING_BYTE occupies. This page is never used.
   475         -** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
   476         -** should possibly be consolidated (presumably in pager.h).
   477         -**
   478         -** If disk I/O is omitted (meaning that the database is stored purely
   479         -** in memory) then there is no pending byte.
   480         -*/
   481         -#ifdef SQLITE_OMIT_DISKIO
   482         -# define PENDING_BYTE_PAGE(pBt)  0x7fffffff
   483         -#else
   484         -# define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)
   485         -#endif
   486         -
   487         -/*
   488         -** A linked list of the following structures is stored at BtShared.pLock.
   489         -** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
   490         -** is opened on the table with root page BtShared.iTable. Locks are removed
   491         -** from this list when a transaction is committed or rolled back, or when
   492         -** a btree handle is closed.
   493         -*/
   494         -struct BtLock {
   495         -  Btree *pBtree;        /* Btree handle holding this lock */
   496         -  Pgno iTable;          /* Root page of table */
   497         -  u8 eLock;             /* READ_LOCK or WRITE_LOCK */
   498         -  BtLock *pNext;        /* Next in BtShared.pLock list */
   499         -};
   500         -
   501         -/* Candidate values for BtLock.eLock */
   502         -#define READ_LOCK     1
   503         -#define WRITE_LOCK    2
   504     40   
   505     41   #ifdef SQLITE_OMIT_SHARED_CACHE
   506     42     /*
   507     43     ** The functions queryTableLock(), lockTable() and unlockAllTables()
   508     44     ** manipulate entries in the BtShared.pLock linked list used to store
   509     45     ** shared-cache table level locks. If the library is compiled with the
   510     46     ** shared-cache feature disabled, then there is only ever one user
................................................................................
   781    317   }
   782    318   
   783    319   #define restoreOrClearCursorPosition(p) \
   784    320     (p->eState==CURSOR_REQUIRESEEK?restoreOrClearCursorPositionX(p):SQLITE_OK)
   785    321   
   786    322   #ifndef SQLITE_OMIT_AUTOVACUUM
   787    323   /*
   788         -** These macros define the location of the pointer-map entry for a 
   789         -** database page. The first argument to each is the number of usable
   790         -** bytes on each page of the database (often 1024). The second is the
   791         -** page number to look up in the pointer map.
   792         -**
   793         -** PTRMAP_PAGENO returns the database page number of the pointer-map
   794         -** page that stores the required pointer. PTRMAP_PTROFFSET returns
   795         -** the offset of the requested map entry.
   796         -**
   797         -** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
   798         -** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
   799         -** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
   800         -** this test.
          324  +** Given a page number of a regular database page, return the page
          325  +** number for the pointer-map page that contains the entry for the
          326  +** input page number.
   801    327   */
   802         -#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)
   803         -#define PTRMAP_PTROFFSET(pBt, pgno) (5*(pgno-ptrmapPageno(pBt, pgno)-1))
   804         -#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))
   805         -
   806    328   static Pgno ptrmapPageno(BtShared *pBt, Pgno pgno){
   807    329     int nPagesPerMapPage = (pBt->usableSize/5)+1;
   808    330     int iPtrMap = (pgno-2)/nPagesPerMapPage;
   809    331     int ret = (iPtrMap*nPagesPerMapPage) + 2; 
   810    332     if( ret==PENDING_BYTE_PAGE(pBt) ){
   811    333       ret++;
   812    334     }
   813    335     return ret;
   814    336   }
   815    337   
   816         -/*
   817         -** The pointer map is a lookup table that identifies the parent page for
   818         -** each child page in the database file.  The parent page is the page that
   819         -** contains a pointer to the child.  Every page in the database contains
   820         -** 0 or 1 parent pages.  (In this context 'database page' refers
   821         -** to any page that is not part of the pointer map itself.)  Each pointer map
   822         -** entry consists of a single byte 'type' and a 4 byte parent page number.
   823         -** The PTRMAP_XXX identifiers below are the valid types.
   824         -**
   825         -** The purpose of the pointer map is to facility moving pages from one
   826         -** position in the file to another as part of autovacuum.  When a page
   827         -** is moved, the pointer in its parent must be updated to point to the
   828         -** new location.  The pointer map is used to locate the parent page quickly.
   829         -**
   830         -** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
   831         -**                  used in this case.
   832         -**
   833         -** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
   834         -**                  is not used in this case.
   835         -**
   836         -** PTRMAP_OVERFLOW1: The database page is the first page in a list of 
   837         -**                   overflow pages. The page number identifies the page that
   838         -**                   contains the cell with a pointer to this overflow page.
   839         -**
   840         -** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
   841         -**                   overflow pages. The page-number identifies the previous
   842         -**                   page in the overflow page list.
   843         -**
   844         -** PTRMAP_BTREE: The database page is a non-root btree page. The page number
   845         -**               identifies the parent page in the btree.
   846         -*/
   847         -#define PTRMAP_ROOTPAGE 1
   848         -#define PTRMAP_FREEPAGE 2
   849         -#define PTRMAP_OVERFLOW1 3
   850         -#define PTRMAP_OVERFLOW2 4
   851         -#define PTRMAP_BTREE 5
   852         -
   853    338   /*
   854    339   ** Write an entry into the pointer map.
   855    340   **
   856    341   ** This routine updates the pointer map entry for page number 'key'
   857    342   ** so that it maps to type 'eType' and parent page number 'pgno'.
   858    343   ** An error code is returned if something goes wrong, otherwise SQLITE_OK.
   859    344   */
................................................................................
  1086    571     u8 *pCell;
  1087    572     pCell = findOverflowCell(pPage, iCell);
  1088    573     return ptrmapPutOvflPtr(pPage, pCell);
  1089    574   }
  1090    575   #endif
  1091    576   
  1092    577   
  1093         -/* A bunch of assert() statements to check the transaction state variables
  1094         -** of handle p (type Btree*) are internally consistent.
  1095         -*/
  1096         -#define btreeIntegrity(p) \
  1097         -  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
  1098         -  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
  1099         -  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
  1100         -  assert( p->pBt->inTransaction>=p->inTrans ); 
  1101         -
  1102    578   /*
  1103    579   ** Defragment the page given.  All Cells are moved to the
  1104    580   ** end of the page and all free space is collected into one
  1105    581   ** big FreeBlk that occurs in between the header and cell
  1106    582   ** pointer array and the cell content area.
  1107    583   */
  1108    584   static int defragmentPage(MemPage *pPage){
................................................................................
  4763   4239     ** in case the divider cell inserted caused it to become overfull.
  4764   4240     */
  4765   4241     releasePage(pNew);
  4766   4242     return balance(pParent, 0);
  4767   4243   }
  4768   4244   #endif /* SQLITE_OMIT_QUICKBALANCE */
  4769   4245   
  4770         -/*
  4771         -** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
  4772         -** if the database supports auto-vacuum or not. Because it is used
  4773         -** within an expression that is an argument to another macro 
  4774         -** (sqliteMallocRaw), it is not possible to use conditional compilation.
  4775         -** So, this macro is defined instead.
  4776         -*/
  4777         -#ifndef SQLITE_OMIT_AUTOVACUUM
  4778         -#define ISAUTOVACUUM (pBt->autoVacuum)
  4779         -#else
  4780         -#define ISAUTOVACUUM 0
  4781         -#endif
  4782         -
  4783   4246   /*
  4784   4247   ** This routine redistributes Cells on pPage and up to NN*2 siblings
  4785   4248   ** of pPage so that all pages have about the same amount of free space.
  4786   4249   ** Usually NN siblings on either side of pPage is used in the balancing,
  4787   4250   ** though more siblings might come from one side if pPage is the first
  4788   4251   ** or last child of its parent.  If pPage has fewer than 2*NN siblings
  4789   4252   ** (something which can only happen if pPage is the root page or a 
................................................................................
  6375   5838   ** Return the pager associated with a BTree.  This routine is used for
  6376   5839   ** testing and debugging only.
  6377   5840   */
  6378   5841   Pager *sqlite3BtreePager(Btree *p){
  6379   5842     return p->pBt->pPager;
  6380   5843   }
  6381   5844   
  6382         -/*
  6383         -** This structure is passed around through all the sanity checking routines
  6384         -** in order to keep track of some global state information.
  6385         -*/
  6386         -typedef struct IntegrityCk IntegrityCk;
  6387         -struct IntegrityCk {
  6388         -  BtShared *pBt;    /* The tree being checked out */
  6389         -  Pager *pPager;    /* The associated pager.  Also accessible by pBt->pPager */
  6390         -  int nPage;        /* Number of pages in the database */
  6391         -  int *anRef;       /* Number of times each page is referenced */
  6392         -  int mxErr;        /* Stop accumulating errors when this reaches zero */
  6393         -  char *zErrMsg;    /* An error message.  NULL if no errors seen. */
  6394         -  int nErr;         /* Number of messages written to zErrMsg so far */
  6395         -};
  6396         -
  6397   5845   #ifndef SQLITE_OMIT_INTEGRITY_CHECK
  6398   5846   /*
  6399   5847   ** Append a message to the error message string.
  6400   5848   */
  6401   5849   static void checkAppendMsg(
  6402   5850     IntegrityCk *pCheck,
  6403   5851     char *zMsg1,

Added src/btreeInt.h.

            1  +/*
            2  +** 2004 April 6
            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  +** $Id: btreeInt.h,v 1.1 2007/05/05 11:48:54 drh Exp $
           13  +**
           14  +** This file implements a external (disk-based) database using BTrees.
           15  +** For a detailed discussion of BTrees, refer to
           16  +**
           17  +**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
           18  +**     "Sorting And Searching", pages 473-480. Addison-Wesley
           19  +**     Publishing Company, Reading, Massachusetts.
           20  +**
           21  +** The basic idea is that each page of the file contains N database
           22  +** entries and N+1 pointers to subpages.
           23  +**
           24  +**   ----------------------------------------------------------------
           25  +**   |  Ptr(0) | Key(0) | Ptr(1) | Key(1) | ... | Key(N-1) | Ptr(N) |
           26  +**   ----------------------------------------------------------------
           27  +**
           28  +** All of the keys on the page that Ptr(0) points to have values less
           29  +** than Key(0).  All of the keys on page Ptr(1) and its subpages have
           30  +** values greater than Key(0) and less than Key(1).  All of the keys
           31  +** on Ptr(N) and its subpages have values greater than Key(N-1).  And
           32  +** so forth.
           33  +**
           34  +** Finding a particular key requires reading O(log(M)) pages from the 
           35  +** disk where M is the number of entries in the tree.
           36  +**
           37  +** In this implementation, a single file can hold one or more separate 
           38  +** BTrees.  Each BTree is identified by the index of its root page.  The
           39  +** key and data for any entry are combined to form the "payload".  A
           40  +** fixed amount of payload can be carried directly on the database
           41  +** page.  If the payload is larger than the preset amount then surplus
           42  +** bytes are stored on overflow pages.  The payload for an entry
           43  +** and the preceding pointer are combined to form a "Cell".  Each 
           44  +** page has a small header which contains the Ptr(N) pointer and other
           45  +** information such as the size of key and data.
           46  +**
           47  +** FORMAT DETAILS
           48  +**
           49  +** The file is divided into pages.  The first page is called page 1,
           50  +** the second is page 2, and so forth.  A page number of zero indicates
           51  +** "no such page".  The page size can be anything between 512 and 65536.
           52  +** Each page can be either a btree page, a freelist page or an overflow
           53  +** page.
           54  +**
           55  +** The first page is always a btree page.  The first 100 bytes of the first
           56  +** page contain a special header (the "file header") that describes the file.
           57  +** The format of the file header is as follows:
           58  +**
           59  +**   OFFSET   SIZE    DESCRIPTION
           60  +**      0      16     Header string: "SQLite format 3\000"
           61  +**     16       2     Page size in bytes.  
           62  +**     18       1     File format write version
           63  +**     19       1     File format read version
           64  +**     20       1     Bytes of unused space at the end of each page
           65  +**     21       1     Max embedded payload fraction
           66  +**     22       1     Min embedded payload fraction
           67  +**     23       1     Min leaf payload fraction
           68  +**     24       4     File change counter
           69  +**     28       4     Reserved for future use
           70  +**     32       4     First freelist page
           71  +**     36       4     Number of freelist pages in the file
           72  +**     40      60     15 4-byte meta values passed to higher layers
           73  +**
           74  +** All of the integer values are big-endian (most significant byte first).
           75  +**
           76  +** The file change counter is incremented when the database is changed more
           77  +** than once within the same second.  This counter, together with the
           78  +** modification time of the file, allows other processes to know
           79  +** when the file has changed and thus when they need to flush their
           80  +** cache.
           81  +**
           82  +** The max embedded payload fraction is the amount of the total usable
           83  +** space in a page that can be consumed by a single cell for standard
           84  +** B-tree (non-LEAFDATA) tables.  A value of 255 means 100%.  The default
           85  +** is to limit the maximum cell size so that at least 4 cells will fit
           86  +** on one page.  Thus the default max embedded payload fraction is 64.
           87  +**
           88  +** If the payload for a cell is larger than the max payload, then extra
           89  +** payload is spilled to overflow pages.  Once an overflow page is allocated,
           90  +** as many bytes as possible are moved into the overflow pages without letting
           91  +** the cell size drop below the min embedded payload fraction.
           92  +**
           93  +** The min leaf payload fraction is like the min embedded payload fraction
           94  +** except that it applies to leaf nodes in a LEAFDATA tree.  The maximum
           95  +** payload fraction for a LEAFDATA tree is always 100% (or 255) and it
           96  +** not specified in the header.
           97  +**
           98  +** Each btree pages is divided into three sections:  The header, the
           99  +** cell pointer array, and the cell area area.  Page 1 also has a 100-byte
          100  +** file header that occurs before the page header.
          101  +**
          102  +**      |----------------|
          103  +**      | file header    |   100 bytes.  Page 1 only.
          104  +**      |----------------|
          105  +**      | page header    |   8 bytes for leaves.  12 bytes for interior nodes
          106  +**      |----------------|
          107  +**      | cell pointer   |   |  2 bytes per cell.  Sorted order.
          108  +**      | array          |   |  Grows downward
          109  +**      |                |   v
          110  +**      |----------------|
          111  +**      | unallocated    |
          112  +**      | space          |
          113  +**      |----------------|   ^  Grows upwards
          114  +**      | cell content   |   |  Arbitrary order interspersed with freeblocks.
          115  +**      | area           |   |  and free space fragments.
          116  +**      |----------------|
          117  +**
          118  +** The page headers looks like this:
          119  +**
          120  +**   OFFSET   SIZE     DESCRIPTION
          121  +**      0       1      Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
          122  +**      1       2      byte offset to the first freeblock
          123  +**      3       2      number of cells on this page
          124  +**      5       2      first byte of the cell content area
          125  +**      7       1      number of fragmented free bytes
          126  +**      8       4      Right child (the Ptr(N) value).  Omitted on leaves.
          127  +**
          128  +** The flags define the format of this btree page.  The leaf flag means that
          129  +** this page has no children.  The zerodata flag means that this page carries
          130  +** only keys and no data.  The intkey flag means that the key is a integer
          131  +** which is stored in the key size entry of the cell header rather than in
          132  +** the payload area.
          133  +**
          134  +** The cell pointer array begins on the first byte after the page header.
          135  +** The cell pointer array contains zero or more 2-byte numbers which are
          136  +** offsets from the beginning of the page to the cell content in the cell
          137  +** content area.  The cell pointers occur in sorted order.  The system strives
          138  +** to keep free space after the last cell pointer so that new cells can
          139  +** be easily added without having to defragment the page.
          140  +**
          141  +** Cell content is stored at the very end of the page and grows toward the
          142  +** beginning of the page.
          143  +**
          144  +** Unused space within the cell content area is collected into a linked list of
          145  +** freeblocks.  Each freeblock is at least 4 bytes in size.  The byte offset
          146  +** to the first freeblock is given in the header.  Freeblocks occur in
          147  +** increasing order.  Because a freeblock must be at least 4 bytes in size,
          148  +** any group of 3 or fewer unused bytes in the cell content area cannot
          149  +** exist on the freeblock chain.  A group of 3 or fewer free bytes is called
          150  +** a fragment.  The total number of bytes in all fragments is recorded.
          151  +** in the page header at offset 7.
          152  +**
          153  +**    SIZE    DESCRIPTION
          154  +**      2     Byte offset of the next freeblock
          155  +**      2     Bytes in this freeblock
          156  +**
          157  +** Cells are of variable length.  Cells are stored in the cell content area at
          158  +** the end of the page.  Pointers to the cells are in the cell pointer array
          159  +** that immediately follows the page header.  Cells is not necessarily
          160  +** contiguous or in order, but cell pointers are contiguous and in order.
          161  +**
          162  +** Cell content makes use of variable length integers.  A variable
          163  +** length integer is 1 to 9 bytes where the lower 7 bits of each 
          164  +** byte are used.  The integer consists of all bytes that have bit 8 set and
          165  +** the first byte with bit 8 clear.  The most significant byte of the integer
          166  +** appears first.  A variable-length integer may not be more than 9 bytes long.
          167  +** As a special case, all 8 bytes of the 9th byte are used as data.  This
          168  +** allows a 64-bit integer to be encoded in 9 bytes.
          169  +**
          170  +**    0x00                      becomes  0x00000000
          171  +**    0x7f                      becomes  0x0000007f
          172  +**    0x81 0x00                 becomes  0x00000080
          173  +**    0x82 0x00                 becomes  0x00000100
          174  +**    0x80 0x7f                 becomes  0x0000007f
          175  +**    0x8a 0x91 0xd1 0xac 0x78  becomes  0x12345678
          176  +**    0x81 0x81 0x81 0x81 0x01  becomes  0x10204081
          177  +**
          178  +** Variable length integers are used for rowids and to hold the number of
          179  +** bytes of key and data in a btree cell.
          180  +**
          181  +** The content of a cell looks like this:
          182  +**
          183  +**    SIZE    DESCRIPTION
          184  +**      4     Page number of the left child. Omitted if leaf flag is set.
          185  +**     var    Number of bytes of data. Omitted if the zerodata flag is set.
          186  +**     var    Number of bytes of key. Or the key itself if intkey flag is set.
          187  +**      *     Payload
          188  +**      4     First page of the overflow chain.  Omitted if no overflow
          189  +**
          190  +** Overflow pages form a linked list.  Each page except the last is completely
          191  +** filled with data (pagesize - 4 bytes).  The last page can have as little
          192  +** as 1 byte of data.
          193  +**
          194  +**    SIZE    DESCRIPTION
          195  +**      4     Page number of next overflow page
          196  +**      *     Data
          197  +**
          198  +** Freelist pages come in two subtypes: trunk pages and leaf pages.  The
          199  +** file header points to first in a linked list of trunk page.  Each trunk
          200  +** page points to multiple leaf pages.  The content of a leaf page is
          201  +** unspecified.  A trunk page looks like this:
          202  +**
          203  +**    SIZE    DESCRIPTION
          204  +**      4     Page number of next trunk page
          205  +**      4     Number of leaf pointers on this page
          206  +**      *     zero or more pages numbers of leaves
          207  +*/
          208  +#include "sqliteInt.h"
          209  +#include "pager.h"
          210  +#include "btree.h"
          211  +#include "os.h"
          212  +#include <assert.h>
          213  +
          214  +/* Round up a number to the next larger multiple of 8.  This is used
          215  +** to force 8-byte alignment on 64-bit architectures.
          216  +*/
          217  +#define ROUND8(x)   ((x+7)&~7)
          218  +
          219  +
          220  +/* The following value is the maximum cell size assuming a maximum page
          221  +** size give above.
          222  +*/
          223  +#define MX_CELL_SIZE(pBt)  (pBt->pageSize-8)
          224  +
          225  +/* The maximum number of cells on a single page of the database.  This
          226  +** assumes a minimum cell size of 3 bytes.  Such small cells will be
          227  +** exceedingly rare, but they are possible.
          228  +*/
          229  +#define MX_CELL(pBt) ((pBt->pageSize-8)/3)
          230  +
          231  +/* Forward declarations */
          232  +typedef struct MemPage MemPage;
          233  +typedef struct BtLock BtLock;
          234  +
          235  +/*
          236  +** This is a magic string that appears at the beginning of every
          237  +** SQLite database in order to identify the file as a real database.
          238  +**
          239  +** You can change this value at compile-time by specifying a
          240  +** -DSQLITE_FILE_HEADER="..." on the compiler command-line.  The
          241  +** header must be exactly 16 bytes including the zero-terminator so
          242  +** the string itself should be 15 characters long.  If you change
          243  +** the header, then your custom library will not be able to read 
          244  +** databases generated by the standard tools and the standard tools
          245  +** will not be able to read databases created by your custom library.
          246  +*/
          247  +#ifndef SQLITE_FILE_HEADER /* 123456789 123456 */
          248  +#  define SQLITE_FILE_HEADER "SQLite format 3"
          249  +#endif
          250  +
          251  +/*
          252  +** Page type flags.  An ORed combination of these flags appear as the
          253  +** first byte of every BTree page.
          254  +*/
          255  +#define PTF_INTKEY    0x01
          256  +#define PTF_ZERODATA  0x02
          257  +#define PTF_LEAFDATA  0x04
          258  +#define PTF_LEAF      0x08
          259  +
          260  +/*
          261  +** As each page of the file is loaded into memory, an instance of the following
          262  +** structure is appended and initialized to zero.  This structure stores
          263  +** information about the page that is decoded from the raw file page.
          264  +**
          265  +** The pParent field points back to the parent page.  This allows us to
          266  +** walk up the BTree from any leaf to the root.  Care must be taken to
          267  +** unref() the parent page pointer when this page is no longer referenced.
          268  +** The pageDestructor() routine handles that chore.
          269  +*/
          270  +struct MemPage {
          271  +  u8 isInit;           /* True if previously initialized. MUST BE FIRST! */
          272  +  u8 idxShift;         /* True if Cell indices have changed */
          273  +  u8 nOverflow;        /* Number of overflow cell bodies in aCell[] */
          274  +  u8 intKey;           /* True if intkey flag is set */
          275  +  u8 leaf;             /* True if leaf flag is set */
          276  +  u8 zeroData;         /* True if table stores keys only */
          277  +  u8 leafData;         /* True if tables stores data on leaves only */
          278  +  u8 hasData;          /* True if this page stores data */
          279  +  u8 hdrOffset;        /* 100 for page 1.  0 otherwise */
          280  +  u8 childPtrSize;     /* 0 if leaf==1.  4 if leaf==0 */
          281  +  u16 maxLocal;        /* Copy of Btree.maxLocal or Btree.maxLeaf */
          282  +  u16 minLocal;        /* Copy of Btree.minLocal or Btree.minLeaf */
          283  +  u16 cellOffset;      /* Index in aData of first cell pointer */
          284  +  u16 idxParent;       /* Index in parent of this node */
          285  +  u16 nFree;           /* Number of free bytes on the page */
          286  +  u16 nCell;           /* Number of cells on this page, local and ovfl */
          287  +  struct _OvflCell {   /* Cells that will not fit on aData[] */
          288  +    u8 *pCell;          /* Pointers to the body of the overflow cell */
          289  +    u16 idx;            /* Insert this cell before idx-th non-overflow cell */
          290  +  } aOvfl[5];
          291  +  BtShared *pBt;       /* Pointer back to BTree structure */
          292  +  u8 *aData;           /* Pointer back to the start of the page */
          293  +  DbPage *pDbPage;     /* Pager page handle */
          294  +  Pgno pgno;           /* Page number for this page */
          295  +  MemPage *pParent;    /* The parent of this page.  NULL for root */
          296  +};
          297  +
          298  +/*
          299  +** The in-memory image of a disk page has the auxiliary information appended
          300  +** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
          301  +** that extra information.
          302  +*/
          303  +#define EXTRA_SIZE sizeof(MemPage)
          304  +
          305  +/* Btree handle */
          306  +struct Btree {
          307  +  sqlite3 *pSqlite;
          308  +  BtShared *pBt;
          309  +  u8 inTrans;            /* TRANS_NONE, TRANS_READ or TRANS_WRITE */
          310  +};
          311  +
          312  +/*
          313  +** Btree.inTrans may take one of the following values.
          314  +**
          315  +** If the shared-data extension is enabled, there may be multiple users
          316  +** of the Btree structure. At most one of these may open a write transaction,
          317  +** but any number may have active read transactions. Variable Btree.pDb 
          318  +** points to the handle that owns any current write-transaction.
          319  +*/
          320  +#define TRANS_NONE  0
          321  +#define TRANS_READ  1
          322  +#define TRANS_WRITE 2
          323  +
          324  +/*
          325  +** Everything we need to know about an open database
          326  +*/
          327  +struct BtShared {
          328  +  Pager *pPager;        /* The page cache */
          329  +  BtCursor *pCursor;    /* A list of all open cursors */
          330  +  MemPage *pPage1;      /* First page of the database */
          331  +  u8 inStmt;            /* True if we are in a statement subtransaction */
          332  +  u8 readOnly;          /* True if the underlying file is readonly */
          333  +  u8 maxEmbedFrac;      /* Maximum payload as % of total page size */
          334  +  u8 minEmbedFrac;      /* Minimum payload as % of total page size */
          335  +  u8 minLeafFrac;       /* Minimum leaf payload as % of total page size */
          336  +  u8 pageSizeFixed;     /* True if the page size can no longer be changed */
          337  +#ifndef SQLITE_OMIT_AUTOVACUUM
          338  +  u8 autoVacuum;        /* True if auto-vacuum is enabled */
          339  +  u8 incrVacuum;        /* True if incr-vacuum is enabled */
          340  +  Pgno nTrunc;          /* Non-zero if the db will be truncated (incr vacuum) */
          341  +#endif
          342  +  u16 pageSize;         /* Total number of bytes on a page */
          343  +  u16 usableSize;       /* Number of usable bytes on each page */
          344  +  int maxLocal;         /* Maximum local payload in non-LEAFDATA tables */
          345  +  int minLocal;         /* Minimum local payload in non-LEAFDATA tables */
          346  +  int maxLeaf;          /* Maximum local payload in a LEAFDATA table */
          347  +  int minLeaf;          /* Minimum local payload in a LEAFDATA table */
          348  +  BusyHandler *pBusyHandler;   /* Callback for when there is lock contention */
          349  +  u8 inTransaction;     /* Transaction state */
          350  +  int nRef;             /* Number of references to this structure */
          351  +  int nTransaction;     /* Number of open transactions (read + write) */
          352  +  void *pSchema;        /* Pointer to space allocated by sqlite3BtreeSchema() */
          353  +  void (*xFreeSchema)(void*);  /* Destructor for BtShared.pSchema */
          354  +#ifndef SQLITE_OMIT_SHARED_CACHE
          355  +  BtLock *pLock;        /* List of locks held on this shared-btree struct */
          356  +  BtShared *pNext;      /* Next in ThreadData.pBtree linked list */
          357  +#endif
          358  +};
          359  +
          360  +/*
          361  +** An instance of the following structure is used to hold information
          362  +** about a cell.  The parseCellPtr() function fills in this structure
          363  +** based on information extract from the raw disk page.
          364  +*/
          365  +typedef struct CellInfo CellInfo;
          366  +struct CellInfo {
          367  +  u8 *pCell;     /* Pointer to the start of cell content */
          368  +  i64 nKey;      /* The key for INTKEY tables, or number of bytes in key */
          369  +  u32 nData;     /* Number of bytes of data */
          370  +  u32 nPayload;  /* Total amount of payload */
          371  +  u16 nHeader;   /* Size of the cell content header in bytes */
          372  +  u16 nLocal;    /* Amount of payload held locally */
          373  +  u16 iOverflow; /* Offset to overflow page number.  Zero if no overflow */
          374  +  u16 nSize;     /* Size of the cell content on the main b-tree page */
          375  +};
          376  +
          377  +/*
          378  +** A cursor is a pointer to a particular entry in the BTree.
          379  +** The entry is identified by its MemPage and the index in
          380  +** MemPage.aCell[] of the entry.
          381  +*/
          382  +struct BtCursor {
          383  +  Btree *pBtree;            /* The Btree to which this cursor belongs */
          384  +  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */
          385  +  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
          386  +  void *pArg;               /* First arg to xCompare() */
          387  +  Pgno pgnoRoot;            /* The root page of this tree */
          388  +  MemPage *pPage;           /* Page that contains the entry */
          389  +  int idx;                  /* Index of the entry in pPage->aCell[] */
          390  +  CellInfo info;            /* A parse of the cell we are pointing at */
          391  +  u8 wrFlag;                /* True if writable */
          392  +  u8 eState;                /* One of the CURSOR_XXX constants (see below) */
          393  +  void *pKey;      /* Saved key that was cursor's last known position */
          394  +  i64 nKey;        /* Size of pKey, or last integer key */
          395  +  int skip;        /* (skip<0) -> Prev() is a no-op. (skip>0) -> Next() is */
          396  +#ifndef SQLITE_OMIT_INCRBLOB
          397  +  u8 isIncrblobHandle;      /* True if this cursor is an incr. io handle */
          398  +  Pgno *aOverflow;          /* Cache of overflow page locations */
          399  +#endif
          400  +};
          401  +
          402  +/*
          403  +** Potential values for BtCursor.eState.
          404  +**
          405  +** CURSOR_VALID:
          406  +**   Cursor points to a valid entry. getPayload() etc. may be called.
          407  +**
          408  +** CURSOR_INVALID:
          409  +**   Cursor does not point to a valid entry. This can happen (for example) 
          410  +**   because the table is empty or because BtreeCursorFirst() has not been
          411  +**   called.
          412  +**
          413  +** CURSOR_REQUIRESEEK:
          414  +**   The table that this cursor was opened on still exists, but has been 
          415  +**   modified since the cursor was last used. The cursor position is saved
          416  +**   in variables BtCursor.pKey and BtCursor.nKey. When a cursor is in 
          417  +**   this state, restoreOrClearCursorPosition() can be called to attempt to
          418  +**   seek the cursor to the saved position.
          419  +*/
          420  +#define CURSOR_INVALID           0
          421  +#define CURSOR_VALID             1
          422  +#define CURSOR_REQUIRESEEK       2
          423  +
          424  +/*
          425  +** The TRACE macro will print high-level status information about the
          426  +** btree operation when the global variable sqlite3_btree_trace is
          427  +** enabled.
          428  +*/
          429  +#if SQLITE_TEST
          430  +# define TRACE(X)   if( sqlite3_btree_trace ){ printf X; fflush(stdout); }
          431  +#else
          432  +# define TRACE(X)
          433  +#endif
          434  +
          435  +/*
          436  +** Routines to read and write variable-length integers.  These used to
          437  +** be defined locally, but now we use the varint routines in the util.c
          438  +** file.
          439  +*/
          440  +#define getVarint    sqlite3GetVarint
          441  +#define getVarint32(A,B)  ((*B=*(A))<=0x7f?1:sqlite3GetVarint32(A,B))
          442  +#define putVarint    sqlite3PutVarint
          443  +
          444  +/* The database page the PENDING_BYTE occupies. This page is never used.
          445  +** TODO: This macro is very similary to PAGER_MJ_PGNO() in pager.c. They
          446  +** should possibly be consolidated (presumably in pager.h).
          447  +**
          448  +** If disk I/O is omitted (meaning that the database is stored purely
          449  +** in memory) then there is no pending byte.
          450  +*/
          451  +#ifdef SQLITE_OMIT_DISKIO
          452  +# define PENDING_BYTE_PAGE(pBt)  0x7fffffff
          453  +#else
          454  +# define PENDING_BYTE_PAGE(pBt) ((PENDING_BYTE/(pBt)->pageSize)+1)
          455  +#endif
          456  +
          457  +/*
          458  +** A linked list of the following structures is stored at BtShared.pLock.
          459  +** Locks are added (or upgraded from READ_LOCK to WRITE_LOCK) when a cursor 
          460  +** is opened on the table with root page BtShared.iTable. Locks are removed
          461  +** from this list when a transaction is committed or rolled back, or when
          462  +** a btree handle is closed.
          463  +*/
          464  +struct BtLock {
          465  +  Btree *pBtree;        /* Btree handle holding this lock */
          466  +  Pgno iTable;          /* Root page of table */
          467  +  u8 eLock;             /* READ_LOCK or WRITE_LOCK */
          468  +  BtLock *pNext;        /* Next in BtShared.pLock list */
          469  +};
          470  +
          471  +/* Candidate values for BtLock.eLock */
          472  +#define READ_LOCK     1
          473  +#define WRITE_LOCK    2
          474  +
          475  +/*
          476  +** These macros define the location of the pointer-map entry for a 
          477  +** database page. The first argument to each is the number of usable
          478  +** bytes on each page of the database (often 1024). The second is the
          479  +** page number to look up in the pointer map.
          480  +**
          481  +** PTRMAP_PAGENO returns the database page number of the pointer-map
          482  +** page that stores the required pointer. PTRMAP_PTROFFSET returns
          483  +** the offset of the requested map entry.
          484  +**
          485  +** If the pgno argument passed to PTRMAP_PAGENO is a pointer-map page,
          486  +** then pgno is returned. So (pgno==PTRMAP_PAGENO(pgsz, pgno)) can be
          487  +** used to test if pgno is a pointer-map page. PTRMAP_ISPAGE implements
          488  +** this test.
          489  +*/
          490  +#define PTRMAP_PAGENO(pBt, pgno) ptrmapPageno(pBt, pgno)
          491  +#define PTRMAP_PTROFFSET(pBt, pgno) (5*(pgno-ptrmapPageno(pBt, pgno)-1))
          492  +#define PTRMAP_ISPAGE(pBt, pgno) (PTRMAP_PAGENO((pBt),(pgno))==(pgno))
          493  +
          494  +/*
          495  +** The pointer map is a lookup table that identifies the parent page for
          496  +** each child page in the database file.  The parent page is the page that
          497  +** contains a pointer to the child.  Every page in the database contains
          498  +** 0 or 1 parent pages.  (In this context 'database page' refers
          499  +** to any page that is not part of the pointer map itself.)  Each pointer map
          500  +** entry consists of a single byte 'type' and a 4 byte parent page number.
          501  +** The PTRMAP_XXX identifiers below are the valid types.
          502  +**
          503  +** The purpose of the pointer map is to facility moving pages from one
          504  +** position in the file to another as part of autovacuum.  When a page
          505  +** is moved, the pointer in its parent must be updated to point to the
          506  +** new location.  The pointer map is used to locate the parent page quickly.
          507  +**
          508  +** PTRMAP_ROOTPAGE: The database page is a root-page. The page-number is not
          509  +**                  used in this case.
          510  +**
          511  +** PTRMAP_FREEPAGE: The database page is an unused (free) page. The page-number 
          512  +**                  is not used in this case.
          513  +**
          514  +** PTRMAP_OVERFLOW1: The database page is the first page in a list of 
          515  +**                   overflow pages. The page number identifies the page that
          516  +**                   contains the cell with a pointer to this overflow page.
          517  +**
          518  +** PTRMAP_OVERFLOW2: The database page is the second or later page in a list of
          519  +**                   overflow pages. The page-number identifies the previous
          520  +**                   page in the overflow page list.
          521  +**
          522  +** PTRMAP_BTREE: The database page is a non-root btree page. The page number
          523  +**               identifies the parent page in the btree.
          524  +*/
          525  +#define PTRMAP_ROOTPAGE 1
          526  +#define PTRMAP_FREEPAGE 2
          527  +#define PTRMAP_OVERFLOW1 3
          528  +#define PTRMAP_OVERFLOW2 4
          529  +#define PTRMAP_BTREE 5
          530  +
          531  +/* A bunch of assert() statements to check the transaction state variables
          532  +** of handle p (type Btree*) are internally consistent.
          533  +*/
          534  +#define btreeIntegrity(p) \
          535  +  assert( p->inTrans!=TRANS_NONE || p->pBt->nTransaction<p->pBt->nRef ); \
          536  +  assert( p->pBt->nTransaction<=p->pBt->nRef ); \
          537  +  assert( p->pBt->inTransaction!=TRANS_NONE || p->pBt->nTransaction==0 ); \
          538  +  assert( p->pBt->inTransaction>=p->inTrans ); 
          539  +
          540  +
          541  +/*
          542  +** The ISAUTOVACUUM macro is used within balance_nonroot() to determine
          543  +** if the database supports auto-vacuum or not. Because it is used
          544  +** within an expression that is an argument to another macro 
          545  +** (sqliteMallocRaw), it is not possible to use conditional compilation.
          546  +** So, this macro is defined instead.
          547  +*/
          548  +#ifndef SQLITE_OMIT_AUTOVACUUM
          549  +#define ISAUTOVACUUM (pBt->autoVacuum)
          550  +#else
          551  +#define ISAUTOVACUUM 0
          552  +#endif
          553  +
          554  +
          555  +/*
          556  +** This structure is passed around through all the sanity checking routines
          557  +** in order to keep track of some global state information.
          558  +*/
          559  +typedef struct IntegrityCk IntegrityCk;
          560  +struct IntegrityCk {
          561  +  BtShared *pBt;    /* The tree being checked out */
          562  +  Pager *pPager;    /* The associated pager.  Also accessible by pBt->pPager */
          563  +  int nPage;        /* Number of pages in the database */
          564  +  int *anRef;       /* Number of times each page is referenced */
          565  +  int mxErr;        /* Stop accumulating errors when this reaches zero */
          566  +  char *zErrMsg;    /* An error message.  NULL if no errors seen. */
          567  +  int nErr;         /* Number of messages written to zErrMsg so far */
          568  +};
          569  +
          570  +/*
          571  +** Read or write a two- and four-byte big-endian integer values.
          572  +*/
          573  +#define get2byte sqlite3Get2byte
          574  +#define get4byte sqlite3Get4byte
          575  +#define put2byte sqlite3Put2byte
          576  +#define put4byte sqlite3Put4byte

Added src/malloc.c.

            1  +/*
            2  +** 2001 September 15
            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  +** Memory allocation functions used throughout sqlite.
           13  +**
           14  +**
           15  +** $Id: malloc.c,v 1.1 2007/05/05 11:48:54 drh Exp $
           16  +*/
           17  +#include "sqliteInt.h"
           18  +#include "os.h"
           19  +#include <stdarg.h>
           20  +#include <ctype.h>
           21  +
           22  +/*
           23  +** MALLOC WRAPPER ARCHITECTURE
           24  +**
           25  +** The sqlite code accesses dynamic memory allocation/deallocation by invoking
           26  +** the following six APIs (which may be implemented as macros).
           27  +**
           28  +**     sqlite3Malloc()
           29  +**     sqlite3MallocRaw()
           30  +**     sqlite3Realloc()
           31  +**     sqlite3ReallocOrFree()
           32  +**     sqlite3Free()
           33  +**     sqlite3AllocSize()
           34  +**
           35  +** The function sqlite3FreeX performs the same task as sqlite3Free and is
           36  +** guaranteed to be a real function. The same holds for sqlite3MallocX
           37  +**
           38  +** The above APIs are implemented in terms of the functions provided in the
           39  +** operating-system interface. The OS interface is never accessed directly
           40  +** by code outside of this file.
           41  +**
           42  +**     sqlite3OsMalloc()
           43  +**     sqlite3OsRealloc()
           44  +**     sqlite3OsFree()
           45  +**     sqlite3OsAllocationSize()
           46  +**
           47  +** Functions sqlite3MallocRaw() and sqlite3Realloc() may invoke 
           48  +** sqlite3_release_memory() if a call to sqlite3OsMalloc() or
           49  +** sqlite3OsRealloc() fails (or if the soft-heap-limit for the thread is
           50  +** exceeded). Function sqlite3Malloc() usually invokes
           51  +** sqlite3MallocRaw().
           52  +**
           53  +** MALLOC TEST WRAPPER ARCHITECTURE
           54  +**
           55  +** The test wrapper provides extra test facilities to ensure the library 
           56  +** does not leak memory and handles the failure of the underlying OS level
           57  +** allocation system correctly. It is only present if the library is 
           58  +** compiled with the SQLITE_MEMDEBUG macro set.
           59  +**
           60  +**     * Guardposts to detect overwrites.
           61  +**     * Ability to cause a specific Malloc() or Realloc() to fail.
           62  +**     * Audit outstanding memory allocations (i.e check for leaks).
           63  +*/
           64  +
           65  +#define MAX(x,y) ((x)>(y)?(x):(y))
           66  +
           67  +#if defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) && !defined(SQLITE_OMIT_DISKIO)
           68  +/*
           69  +** Set the soft heap-size limit for the current thread. Passing a negative
           70  +** value indicates no limit.
           71  +*/
           72  +void sqlite3_soft_heap_limit(int n){
           73  +  ThreadData *pTd = sqlite3ThreadData();
           74  +  if( pTd ){
           75  +    pTd->nSoftHeapLimit = n;
           76  +  }
           77  +  sqlite3ReleaseThreadData();
           78  +}
           79  +
           80  +/*
           81  +** Release memory held by SQLite instances created by the current thread.
           82  +*/
           83  +int sqlite3_release_memory(int n){
           84  +  return sqlite3PagerReleaseMemory(n);
           85  +}
           86  +#else
           87  +/* If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, then define a version
           88  +** of sqlite3_release_memory() to be used by other code in this file.
           89  +** This is done for no better reason than to reduce the number of 
           90  +** pre-processor #ifndef statements.
           91  +*/
           92  +#define sqlite3_release_memory(x) 0    /* 0 == no memory freed */
           93  +#endif
           94  +
           95  +#ifdef SQLITE_MEMDEBUG
           96  +/*--------------------------------------------------------------------------
           97  +** Begin code for memory allocation system test layer.
           98  +**
           99  +** Memory debugging is turned on by defining the SQLITE_MEMDEBUG macro.
          100  +**
          101  +** SQLITE_MEMDEBUG==1    -> Fence-posting only (thread safe) 
          102  +** SQLITE_MEMDEBUG==2    -> Fence-posting + linked list of allocations (not ts)
          103  +** SQLITE_MEMDEBUG==3    -> Above + backtraces (not thread safe, req. glibc)
          104  +*/
          105  +
          106  +/* Figure out whether or not to store backtrace() information for each malloc.
          107  +** The backtrace() function is only used if SQLITE_MEMDEBUG is set to 2 or 
          108  +** greater and glibc is in use. If we don't want to use backtrace(), then just
          109  +** define it as an empty macro and set the amount of space reserved to 0.
          110  +*/
          111  +#if defined(__GLIBC__) && SQLITE_MEMDEBUG>2
          112  +  extern int backtrace(void **, int);
          113  +  #define TESTALLOC_STACKSIZE 128
          114  +  #define TESTALLOC_STACKFRAMES ((TESTALLOC_STACKSIZE-8)/sizeof(void*))
          115  +#else
          116  +  #define backtrace(x, y)
          117  +  #define TESTALLOC_STACKSIZE 0
          118  +  #define TESTALLOC_STACKFRAMES 0
          119  +#endif
          120  +
          121  +/*
          122  +** Number of 32-bit guard words.  This should probably be a multiple of
          123  +** 2 since on 64-bit machines we want the value returned by sqliteMalloc()
          124  +** to be 8-byte aligned.
          125  +*/
          126  +#ifndef TESTALLOC_NGUARD
          127  +# define TESTALLOC_NGUARD 2
          128  +#endif
          129  +
          130  +/*
          131  +** Size reserved for storing file-name along with each malloc()ed blob.
          132  +*/
          133  +#define TESTALLOC_FILESIZE 64
          134  +
          135  +/*
          136  +** Size reserved for storing the user string. Each time a Malloc() or Realloc()
          137  +** call succeeds, up to TESTALLOC_USERSIZE bytes of the string pointed to by
          138  +** sqlite3_malloc_id are stored along with the other test system metadata.
          139  +*/
          140  +#define TESTALLOC_USERSIZE 64
          141  +const char *sqlite3_malloc_id = 0;
          142  +
          143  +/*
          144  +** Blocks used by the test layer have the following format:
          145  +**
          146  +**        <sizeof(void *) pNext pointer>
          147  +**        <sizeof(void *) pPrev pointer>
          148  +**        <TESTALLOC_NGUARD 32-bit guard words>
          149  +**            <The application level allocation>
          150  +**        <TESTALLOC_NGUARD 32-bit guard words>
          151  +**        <32-bit line number>
          152  +**        <TESTALLOC_FILESIZE bytes containing null-terminated file name>
          153  +**        <TESTALLOC_STACKSIZE bytes of backtrace() output>
          154  +*/ 
          155  +
          156  +#define TESTALLOC_OFFSET_GUARD1(p)    (sizeof(void *) * 2)
          157  +#define TESTALLOC_OFFSET_DATA(p) ( \
          158  +  TESTALLOC_OFFSET_GUARD1(p) + sizeof(u32) * TESTALLOC_NGUARD \
          159  +)
          160  +#define TESTALLOC_OFFSET_GUARD2(p) ( \
          161  +  TESTALLOC_OFFSET_DATA(p) + sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD \
          162  +)
          163  +#define TESTALLOC_OFFSET_LINENUMBER(p) ( \
          164  +  TESTALLOC_OFFSET_GUARD2(p) + sizeof(u32) * TESTALLOC_NGUARD \
          165  +)
          166  +#define TESTALLOC_OFFSET_FILENAME(p) ( \
          167  +  TESTALLOC_OFFSET_LINENUMBER(p) + sizeof(u32) \
          168  +)
          169  +#define TESTALLOC_OFFSET_USER(p) ( \
          170  +  TESTALLOC_OFFSET_FILENAME(p) + TESTALLOC_FILESIZE \
          171  +)
          172  +#define TESTALLOC_OFFSET_STACK(p) ( \
          173  +  TESTALLOC_OFFSET_USER(p) + TESTALLOC_USERSIZE + 8 - \
          174  +  (TESTALLOC_OFFSET_USER(p) % 8) \
          175  +)
          176  +
          177  +#define TESTALLOC_OVERHEAD ( \
          178  +  sizeof(void *)*2 +                   /* pPrev and pNext pointers */   \
          179  +  TESTALLOC_NGUARD*sizeof(u32)*2 +              /* Guard words */       \
          180  +  sizeof(u32) + TESTALLOC_FILESIZE +   /* File and line number */       \
          181  +  TESTALLOC_USERSIZE +                 /* User string */                \
          182  +  TESTALLOC_STACKSIZE                  /* backtrace() stack */          \
          183  +)
          184  +
          185  +
          186  +/*
          187  +** For keeping track of the number of mallocs and frees.   This
          188  +** is used to check for memory leaks.  The iMallocFail and iMallocReset
          189  +** values are used to simulate malloc() failures during testing in 
          190  +** order to verify that the library correctly handles an out-of-memory
          191  +** condition.
          192  +*/
          193  +int sqlite3_nMalloc;         /* Number of sqliteMalloc() calls */
          194  +int sqlite3_nFree;           /* Number of sqliteFree() calls */
          195  +int sqlite3_memUsed;         /* TODO Total memory obtained from malloc */
          196  +int sqlite3_memMax;          /* TODO Mem usage high-water mark */
          197  +int sqlite3_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
          198  +int sqlite3_iMallocReset = -1; /* When iMallocFail reaches 0, set to this */
          199  +
          200  +void *sqlite3_pFirst = 0;         /* Pointer to linked list of allocations */
          201  +int sqlite3_nMaxAlloc = 0;        /* High water mark of ThreadData.nAlloc */
          202  +int sqlite3_mallocDisallowed = 0; /* assert() in sqlite3Malloc() if set */
          203  +int sqlite3_isFail = 0;           /* True if all malloc calls should fail */
          204  +const char *sqlite3_zFile = 0;    /* Filename to associate debug info with */
          205  +int sqlite3_iLine = 0;            /* Line number for debug info */
          206  +
          207  +/*
          208  +** Check for a simulated memory allocation failure.  Return true if
          209  +** the failure should be simulated.  Return false to proceed as normal.
          210  +*/
          211  +int sqlite3TestMallocFail(){
          212  +  if( sqlite3_isFail ){
          213  +    return 1;
          214  +  }
          215  +  if( sqlite3_iMallocFail>=0 ){
          216  +    sqlite3_iMallocFail--;
          217  +    if( sqlite3_iMallocFail==0 ){
          218  +      sqlite3_iMallocFail = sqlite3_iMallocReset;
          219  +      sqlite3_isFail = 1;
          220  +      return 1;
          221  +    }
          222  +  }
          223  +  return 0;
          224  +}
          225  +
          226  +/*
          227  +** The argument is a pointer returned by sqlite3OsMalloc() or xRealloc().
          228  +** assert() that the first and last (TESTALLOC_NGUARD*4) bytes are set to the
          229  +** values set by the applyGuards() function.
          230  +*/
          231  +static void checkGuards(u32 *p)
          232  +{
          233  +  int i;
          234  +  char *zAlloc = (char *)p;
          235  +  char *z;
          236  +
          237  +  /* First set of guard words */
          238  +  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
          239  +  for(i=0; i<TESTALLOC_NGUARD; i++){
          240  +    assert(((u32 *)z)[i]==0xdead1122);
          241  +  }
          242  +
          243  +  /* Second set of guard words */
          244  +  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
          245  +  for(i=0; i<TESTALLOC_NGUARD; i++){
          246  +    u32 guard = 0;
          247  +    memcpy(&guard, &z[i*sizeof(u32)], sizeof(u32));
          248  +    assert(guard==0xdead3344);
          249  +  }
          250  +}
          251  +
          252  +/*
          253  +** The argument is a pointer returned by sqlite3OsMalloc() or Realloc(). The
          254  +** first and last (TESTALLOC_NGUARD*4) bytes are set to known values for use as 
          255  +** guard-posts.
          256  +*/
          257  +static void applyGuards(u32 *p)
          258  +{
          259  +  int i;
          260  +  char *z;
          261  +  char *zAlloc = (char *)p;
          262  +
          263  +  /* First set of guard words */
          264  +  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
          265  +  for(i=0; i<TESTALLOC_NGUARD; i++){
          266  +    ((u32 *)z)[i] = 0xdead1122;
          267  +  }
          268  +
          269  +  /* Second set of guard words */
          270  +  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
          271  +  for(i=0; i<TESTALLOC_NGUARD; i++){
          272  +    static const int guard = 0xdead3344;
          273  +    memcpy(&z[i*sizeof(u32)], &guard, sizeof(u32));
          274  +  }
          275  +
          276  +  /* Line number */
          277  +  z = &((char *)z)[TESTALLOC_NGUARD*sizeof(u32)];             /* Guard words */
          278  +  z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
          279  +  memcpy(z, &sqlite3_iLine, sizeof(u32));
          280  +
          281  +  /* File name */
          282  +  z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
          283  +  strncpy(z, sqlite3_zFile, TESTALLOC_FILESIZE);
          284  +  z[TESTALLOC_FILESIZE - 1] = '\0';
          285  +
          286  +  /* User string */
          287  +  z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
          288  +  z[0] = 0;
          289  +  if( sqlite3_malloc_id ){
          290  +    strncpy(z, sqlite3_malloc_id, TESTALLOC_USERSIZE);
          291  +    z[TESTALLOC_USERSIZE-1] = 0;
          292  +  }
          293  +
          294  +  /* backtrace() stack */
          295  +  z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
          296  +  backtrace((void **)z, TESTALLOC_STACKFRAMES);
          297  +
          298  +  /* Sanity check to make sure checkGuards() is working */
          299  +  checkGuards(p);
          300  +}
          301  +
          302  +/*
          303  +** The argument is a malloc()ed pointer as returned by the test-wrapper.
          304  +** Return a pointer to the Os level allocation.
          305  +*/
          306  +static void *getOsPointer(void *p)
          307  +{
          308  +  char *z = (char *)p;
          309  +  return (void *)(&z[-1 * TESTALLOC_OFFSET_DATA(p)]);
          310  +}
          311  +
          312  +
          313  +#if SQLITE_MEMDEBUG>1
          314  +/*
          315  +** The argument points to an Os level allocation. Link it into the threads list
          316  +** of allocations.
          317  +*/
          318  +static void linkAlloc(void *p){
          319  +  void **pp = (void **)p;
          320  +  pp[0] = 0;
          321  +  pp[1] = sqlite3_pFirst;
          322  +  if( sqlite3_pFirst ){
          323  +    ((void **)sqlite3_pFirst)[0] = p;
          324  +  }
          325  +  sqlite3_pFirst = p;
          326  +}
          327  +
          328  +/*
          329  +** The argument points to an Os level allocation. Unlinke it from the threads
          330  +** list of allocations.
          331  +*/
          332  +static void unlinkAlloc(void *p)
          333  +{
          334  +  void **pp = (void **)p;
          335  +  if( p==sqlite3_pFirst ){
          336  +    assert(!pp[0]);
          337  +    assert(!pp[1] || ((void **)(pp[1]))[0]==p);
          338  +    sqlite3_pFirst = pp[1];
          339  +    if( sqlite3_pFirst ){
          340  +      ((void **)sqlite3_pFirst)[0] = 0;
          341  +    }
          342  +  }else{
          343  +    void **pprev = pp[0];
          344  +    void **pnext = pp[1];
          345  +    assert(pprev);
          346  +    assert(pprev[1]==p);
          347  +    pprev[1] = (void *)pnext;
          348  +    if( pnext ){
          349  +      assert(pnext[0]==p);
          350  +      pnext[0] = (void *)pprev;
          351  +    }
          352  +  }
          353  +}
          354  +
          355  +/*
          356  +** Pointer p is a pointer to an OS level allocation that has just been
          357  +** realloc()ed. Set the list pointers that point to this entry to it's new
          358  +** location.
          359  +*/
          360  +static void relinkAlloc(void *p)
          361  +{
          362  +  void **pp = (void **)p;
          363  +  if( pp[0] ){
          364  +    ((void **)(pp[0]))[1] = p;
          365  +  }else{
          366  +    sqlite3_pFirst = p;
          367  +  }
          368  +  if( pp[1] ){
          369  +    ((void **)(pp[1]))[0] = p;
          370  +  }
          371  +}
          372  +#else
          373  +#define linkAlloc(x)
          374  +#define relinkAlloc(x)
          375  +#define unlinkAlloc(x)
          376  +#endif
          377  +
          378  +/*
          379  +** This function sets the result of the Tcl interpreter passed as an argument
          380  +** to a list containing an entry for each currently outstanding call made to 
          381  +** sqliteMalloc and friends by the current thread. Each list entry is itself a
          382  +** list, consisting of the following (in order):
          383  +**
          384  +**     * The number of bytes allocated
          385  +**     * The __FILE__ macro at the time of the sqliteMalloc() call.
          386  +**     * The __LINE__ macro ...
          387  +**     * The value of the sqlite3_malloc_id variable ...
          388  +**     * The output of backtrace() (if available) ...
          389  +**
          390  +** Todo: We could have a version of this function that outputs to stdout, 
          391  +** to debug memory leaks when Tcl is not available.
          392  +*/
          393  +#if defined(TCLSH) && defined(SQLITE_DEBUG) && SQLITE_MEMDEBUG>1
          394  +#include <tcl.h>
          395  +int sqlite3OutstandingMallocs(Tcl_Interp *interp){
          396  +  void *p;
          397  +  Tcl_Obj *pRes = Tcl_NewObj();
          398  +  Tcl_IncrRefCount(pRes);
          399  +
          400  +
          401  +  for(p=sqlite3_pFirst; p; p=((void **)p)[1]){
          402  +    Tcl_Obj *pEntry = Tcl_NewObj();
          403  +    Tcl_Obj *pStack = Tcl_NewObj();
          404  +    char *z;
          405  +    u32 iLine;
          406  +    int nBytes = sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD;
          407  +    char *zAlloc = (char *)p;
          408  +    int i;
          409  +
          410  +    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(nBytes));
          411  +
          412  +    z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
          413  +    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));
          414  +
          415  +    z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
          416  +    memcpy(&iLine, z, sizeof(u32));
          417  +    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(iLine));
          418  +
          419  +    z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
          420  +    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));
          421  +
          422  +    z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
          423  +    for(i=0; i<TESTALLOC_STACKFRAMES; i++){
          424  +      char zHex[128];
          425  +      sqlite3_snprintf(sizeof(zHex), zHex, "%p", ((void **)z)[i]);
          426  +      Tcl_ListObjAppendElement(0, pStack, Tcl_NewStringObj(zHex, -1));
          427  +    }
          428  +
          429  +    Tcl_ListObjAppendElement(0, pEntry, pStack);
          430  +    Tcl_ListObjAppendElement(0, pRes, pEntry);
          431  +  }
          432  +
          433  +  Tcl_ResetResult(interp);
          434  +  Tcl_SetObjResult(interp, pRes);
          435  +  Tcl_DecrRefCount(pRes);
          436  +  return TCL_OK;
          437  +}
          438  +#endif
          439  +
          440  +/*
          441  +** This is the test layer's wrapper around sqlite3OsMalloc().
          442  +*/
          443  +static void * OSMALLOC(int n){
          444  +  sqlite3OsEnterMutex();
          445  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          446  +  sqlite3_nMaxAlloc = 
          447  +      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
          448  +#endif
          449  +  assert( !sqlite3_mallocDisallowed );
          450  +  if( !sqlite3TestMallocFail() ){
          451  +    u32 *p;
          452  +    p = (u32 *)sqlite3OsMalloc(n + TESTALLOC_OVERHEAD);
          453  +    assert(p);
          454  +    sqlite3_nMalloc++;
          455  +    applyGuards(p);
          456  +    linkAlloc(p);
          457  +    sqlite3OsLeaveMutex();
          458  +    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
          459  +  }
          460  +  sqlite3OsLeaveMutex();
          461  +  return 0;
          462  +}
          463  +
          464  +static int OSSIZEOF(void *p){
          465  +  if( p ){
          466  +    u32 *pOs = (u32 *)getOsPointer(p);
          467  +    return sqlite3OsAllocationSize(pOs) - TESTALLOC_OVERHEAD;
          468  +  }
          469  +  return 0;
          470  +}
          471  +
          472  +/*
          473  +** This is the test layer's wrapper around sqlite3OsFree(). The argument is a
          474  +** pointer to the space allocated for the application to use.
          475  +*/
          476  +static void OSFREE(void *pFree){
          477  +  u32 *p;         /* Pointer to the OS-layer allocation */
          478  +  sqlite3OsEnterMutex();
          479  +  p = (u32 *)getOsPointer(pFree);
          480  +  checkGuards(p);
          481  +  unlinkAlloc(p);
          482  +  memset(pFree, 0x55, OSSIZEOF(pFree));
          483  +  sqlite3OsFree(p);
          484  +  sqlite3_nFree++;
          485  +  sqlite3OsLeaveMutex();
          486  +}
          487  +
          488  +/*
          489  +** This is the test layer's wrapper around sqlite3OsRealloc().
          490  +*/
          491  +static void * OSREALLOC(void *pRealloc, int n){
          492  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          493  +  sqlite3_nMaxAlloc = 
          494  +      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
          495  +#endif
          496  +  assert( !sqlite3_mallocDisallowed );
          497  +  if( !sqlite3TestMallocFail() ){
          498  +    u32 *p = (u32 *)getOsPointer(pRealloc);
          499  +    checkGuards(p);
          500  +    p = sqlite3OsRealloc(p, n + TESTALLOC_OVERHEAD);
          501  +    applyGuards(p);
          502  +    relinkAlloc(p);
          503  +    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
          504  +  }
          505  +  return 0;
          506  +}
          507  +
          508  +static void OSMALLOC_FAILED(){
          509  +  sqlite3_isFail = 0;
          510  +}
          511  +
          512  +#else
          513  +/* Define macros to call the sqlite3OsXXX interface directly if 
          514  +** the SQLITE_MEMDEBUG macro is not defined.
          515  +*/
          516  +#define OSMALLOC(x)        sqlite3OsMalloc(x)
          517  +#define OSREALLOC(x,y)     sqlite3OsRealloc(x,y)
          518  +#define OSFREE(x)          sqlite3OsFree(x)
          519  +#define OSSIZEOF(x)        sqlite3OsAllocationSize(x)
          520  +#define OSMALLOC_FAILED()
          521  +
          522  +#endif  /* SQLITE_MEMDEBUG */
          523  +/*
          524  +** End code for memory allocation system test layer.
          525  +**--------------------------------------------------------------------------*/
          526  +
          527  +/*
          528  +** This routine is called when we are about to allocate n additional bytes
          529  +** of memory.  If the new allocation will put is over the soft allocation
          530  +** limit, then invoke sqlite3_release_memory() to try to release some
          531  +** memory before continuing with the allocation.
          532  +**
          533  +** This routine also makes sure that the thread-specific-data (TSD) has
          534  +** be allocated.  If it has not and can not be allocated, then return
          535  +** false.  The updateMemoryUsedCount() routine below will deallocate
          536  +** the TSD if it ought to be.
          537  +**
          538  +** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
          539  +** a no-op
          540  +*/ 
          541  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          542  +static int enforceSoftLimit(int n){
          543  +  ThreadData *pTsd = sqlite3ThreadData();
          544  +  if( pTsd==0 ){
          545  +    return 0;
          546  +  }
          547  +  assert( pTsd->nAlloc>=0 );
          548  +  if( n>0 && pTsd->nSoftHeapLimit>0 ){
          549  +    while( pTsd->nAlloc+n>pTsd->nSoftHeapLimit && sqlite3_release_memory(n) ){}
          550  +  }
          551  +  return 1;
          552  +}
          553  +#else
          554  +# define enforceSoftLimit(X)  1
          555  +#endif
          556  +
          557  +/*
          558  +** Update the count of total outstanding memory that is held in
          559  +** thread-specific-data (TSD).  If after this update the TSD is
          560  +** no longer being used, then deallocate it.
          561  +**
          562  +** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
          563  +** a no-op
          564  +*/
          565  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          566  +static void updateMemoryUsedCount(int n){
          567  +  ThreadData *pTsd = sqlite3ThreadData();
          568  +  if( pTsd ){
          569  +    pTsd->nAlloc += n;
          570  +    assert( pTsd->nAlloc>=0 );
          571  +    if( pTsd->nAlloc==0 && pTsd->nSoftHeapLimit==0 ){
          572  +      sqlite3ReleaseThreadData();
          573  +    }
          574  +  }
          575  +}
          576  +#else
          577  +#define updateMemoryUsedCount(x)  /* no-op */
          578  +#endif
          579  +
          580  +/*
          581  +** Allocate and return N bytes of uninitialised memory by calling
          582  +** sqlite3OsMalloc(). If the Malloc() call fails, attempt to free memory 
          583  +** by calling sqlite3_release_memory().
          584  +*/
          585  +void *sqlite3MallocRaw(int n, int doMemManage){
          586  +  void *p = 0;
          587  +  if( n>0 && !sqlite3MallocFailed() && (!doMemManage || enforceSoftLimit(n)) ){
          588  +    while( (p = OSMALLOC(n))==0 && sqlite3_release_memory(n) ){}
          589  +    if( !p ){
          590  +      sqlite3FailedMalloc();
          591  +      OSMALLOC_FAILED();
          592  +    }else if( doMemManage ){
          593  +      updateMemoryUsedCount(OSSIZEOF(p));
          594  +    }
          595  +  }
          596  +  return p;
          597  +}
          598  +
          599  +/*
          600  +** Resize the allocation at p to n bytes by calling sqlite3OsRealloc(). The
          601  +** pointer to the new allocation is returned.  If the Realloc() call fails,
          602  +** attempt to free memory by calling sqlite3_release_memory().
          603  +*/
          604  +void *sqlite3Realloc(void *p, int n){
          605  +  if( sqlite3MallocFailed() ){
          606  +    return 0;
          607  +  }
          608  +
          609  +  if( !p ){
          610  +    return sqlite3Malloc(n, 1);
          611  +  }else{
          612  +    void *np = 0;
          613  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          614  +    int origSize = OSSIZEOF(p);
          615  +#endif
          616  +    if( enforceSoftLimit(n - origSize) ){
          617  +      while( (np = OSREALLOC(p, n))==0 && sqlite3_release_memory(n) ){}
          618  +      if( !np ){
          619  +        sqlite3FailedMalloc();
          620  +        OSMALLOC_FAILED();
          621  +      }else{
          622  +        updateMemoryUsedCount(OSSIZEOF(np) - origSize);
          623  +      }
          624  +    }
          625  +    return np;
          626  +  }
          627  +}
          628  +
          629  +/*
          630  +** Free the memory pointed to by p. p must be either a NULL pointer or a 
          631  +** value returned by a previous call to sqlite3Malloc() or sqlite3Realloc().
          632  +*/
          633  +void sqlite3FreeX(void *p){
          634  +  if( p ){
          635  +    updateMemoryUsedCount(0 - OSSIZEOF(p));
          636  +    OSFREE(p);
          637  +  }
          638  +}
          639  +
          640  +/*
          641  +** A version of sqliteMalloc() that is always a function, not a macro.
          642  +** Currently, this is used only to alloc to allocate the parser engine.
          643  +*/
          644  +void *sqlite3MallocX(int n){
          645  +  return sqliteMalloc(n);
          646  +}
          647  +
          648  +/*
          649  +** sqlite3Malloc
          650  +** sqlite3ReallocOrFree
          651  +**
          652  +** These two are implemented as wrappers around sqlite3MallocRaw(), 
          653  +** sqlite3Realloc() and sqlite3Free().
          654  +*/ 
          655  +void *sqlite3Malloc(int n, int doMemManage){
          656  +  void *p = sqlite3MallocRaw(n, doMemManage);
          657  +  if( p ){
          658  +    memset(p, 0, n);
          659  +  }
          660  +  return p;
          661  +}
          662  +void *sqlite3ReallocOrFree(void *p, int n){
          663  +  void *pNew;
          664  +  pNew = sqlite3Realloc(p, n);
          665  +  if( !pNew ){
          666  +    sqlite3FreeX(p);
          667  +  }
          668  +  return pNew;
          669  +}
          670  +
          671  +/*
          672  +** sqlite3ThreadSafeMalloc() and sqlite3ThreadSafeFree() are used in those
          673  +** rare scenarios where sqlite may allocate memory in one thread and free
          674  +** it in another. They are exactly the same as sqlite3Malloc() and 
          675  +** sqlite3Free() except that:
          676  +**
          677  +**   * The allocated memory is not included in any calculations with 
          678  +**     respect to the soft-heap-limit, and
          679  +**
          680  +**   * sqlite3ThreadSafeMalloc() must be matched with ThreadSafeFree(),
          681  +**     not sqlite3Free(). Calling sqlite3Free() on memory obtained from
          682  +**     ThreadSafeMalloc() will cause an error somewhere down the line.
          683  +*/
          684  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          685  +void *sqlite3ThreadSafeMalloc(int n){
          686  +  (void)ENTER_MALLOC;
          687  +  return sqlite3Malloc(n, 0);
          688  +}
          689  +void sqlite3ThreadSafeFree(void *p){
          690  +  (void)ENTER_MALLOC;
          691  +  if( p ){
          692  +    OSFREE(p);
          693  +  }
          694  +}
          695  +#endif
          696  +
          697  +
          698  +/*
          699  +** Return the number of bytes allocated at location p. p must be either 
          700  +** a NULL pointer (in which case 0 is returned) or a pointer returned by 
          701  +** sqlite3Malloc(), sqlite3Realloc() or sqlite3ReallocOrFree().
          702  +**
          703  +** The number of bytes allocated does not include any overhead inserted by 
          704  +** any malloc() wrapper functions that may be called. So the value returned
          705  +** is the number of bytes that were available to SQLite using pointer p, 
          706  +** regardless of how much memory was actually allocated.
          707  +*/
          708  +#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
          709  +int sqlite3AllocSize(void *p){
          710  +  return OSSIZEOF(p);
          711  +}
          712  +#endif
          713  +
          714  +/*
          715  +** Make a copy of a string in memory obtained from sqliteMalloc(). These 
          716  +** functions call sqlite3MallocRaw() directly instead of sqliteMalloc(). This
          717  +** is because when memory debugging is turned on, these two functions are 
          718  +** called via macros that record the current file and line number in the
          719  +** ThreadData structure.
          720  +*/
          721  +char *sqlite3StrDup(const char *z){
          722  +  char *zNew;
          723  +  int n;
          724  +  if( z==0 ) return 0;
          725  +  n = strlen(z)+1;
          726  +  zNew = sqlite3MallocRaw(n, 1);
          727  +  if( zNew ) memcpy(zNew, z, n);
          728  +  return zNew;
          729  +}
          730  +char *sqlite3StrNDup(const char *z, int n){
          731  +  char *zNew;
          732  +  if( z==0 ) return 0;
          733  +  zNew = sqlite3MallocRaw(n+1, 1);
          734  +  if( zNew ){
          735  +    memcpy(zNew, z, n);
          736  +    zNew[n] = 0;
          737  +  }
          738  +  return zNew;
          739  +}
          740  +
          741  +/*
          742  +** Create a string from the 2nd and subsequent arguments (up to the
          743  +** first NULL argument), store the string in memory obtained from
          744  +** sqliteMalloc() and make the pointer indicated by the 1st argument
          745  +** point to that string.  The 1st argument must either be NULL or 
          746  +** point to memory obtained from sqliteMalloc().
          747  +*/
          748  +void sqlite3SetString(char **pz, ...){
          749  +  va_list ap;
          750  +  int nByte;
          751  +  const char *z;
          752  +  char *zResult;
          753  +
          754  +  assert( pz!=0 );
          755  +  nByte = 1;
          756  +  va_start(ap, pz);
          757  +  while( (z = va_arg(ap, const char*))!=0 ){
          758  +    nByte += strlen(z);
          759  +  }
          760  +  va_end(ap);
          761  +  sqliteFree(*pz);
          762  +  *pz = zResult = sqliteMallocRaw( nByte );
          763  +  if( zResult==0 ){
          764  +    return;
          765  +  }
          766  +  *zResult = 0;
          767  +  va_start(ap, pz);
          768  +  while( (z = va_arg(ap, const char*))!=0 ){
          769  +    int n = strlen(z);
          770  +    memcpy(zResult, z, n);
          771  +    zResult += n;
          772  +  }
          773  +  zResult[0] = 0;
          774  +  va_end(ap);
          775  +}
          776  +
          777  +
          778  +/*
          779  +** This function must be called before exiting any API function (i.e. 
          780  +** returning control to the user) that has called sqlite3Malloc or
          781  +** sqlite3Realloc.
          782  +**
          783  +** The returned value is normally a copy of the second argument to this
          784  +** function. However, if a malloc() failure has occured since the previous
          785  +** invocation SQLITE_NOMEM is returned instead. 
          786  +**
          787  +** If the first argument, db, is not NULL and a malloc() error has occured,
          788  +** then the connection error-code (the value returned by sqlite3_errcode())
          789  +** is set to SQLITE_NOMEM.
          790  +*/
          791  +static int mallocHasFailed = 0;
          792  +int sqlite3ApiExit(sqlite3* db, int rc){
          793  +  if( sqlite3MallocFailed() ){
          794  +    mallocHasFailed = 0;
          795  +    sqlite3OsLeaveMutex();
          796  +    sqlite3Error(db, SQLITE_NOMEM, 0);
          797  +    rc = SQLITE_NOMEM;
          798  +  }
          799  +  return rc & (db ? db->errMask : 0xff);
          800  +}
          801  +
          802  +/* 
          803  +** Return true is a malloc has failed in this thread since the last call
          804  +** to sqlite3ApiExit(), or false otherwise.
          805  +*/
          806  +int sqlite3MallocFailed(){
          807  +  return (mallocHasFailed && sqlite3OsInMutex(1));
          808  +}
          809  +
          810  +/* 
          811  +** Set the "malloc has failed" condition to true for this thread.
          812  +*/
          813  +void sqlite3FailedMalloc(){
          814  +  if( !sqlite3MallocFailed() ){
          815  +    sqlite3OsEnterMutex();
          816  +    assert( mallocHasFailed==0 );
          817  +    mallocHasFailed = 1;
          818  +  }
          819  +}
          820  +
          821  +#ifdef SQLITE_MEMDEBUG
          822  +/*
          823  +** This function sets a flag in the thread-specific-data structure that will
          824  +** cause an assert to fail if sqliteMalloc() or sqliteRealloc() is called.
          825  +*/
          826  +void sqlite3MallocDisallow(){
          827  +  assert( sqlite3_mallocDisallowed>=0 );
          828  +  sqlite3_mallocDisallowed++;
          829  +}
          830  +
          831  +/*
          832  +** This function clears the flag set in the thread-specific-data structure set
          833  +** by sqlite3MallocDisallow().
          834  +*/
          835  +void sqlite3MallocAllow(){
          836  +  assert( sqlite3_mallocDisallowed>0 );
          837  +  sqlite3_mallocDisallowed--;
          838  +}
          839  +#endif

Changes to src/pager.c.

    14     14   ** The pager is used to access a database disk file.  It implements
    15     15   ** atomic commit and rollback through the use of a journal file that
    16     16   ** is separate from the database file.  The pager also implements file
    17     17   ** locking to prevent two processes from writing the same database
    18     18   ** file simultaneously, or one process from reading the database while
    19     19   ** another is writing.
    20     20   **
    21         -** @(#) $Id: pager.c,v 1.335 2007/05/04 13:15:56 drh Exp $
           21  +** @(#) $Id: pager.c,v 1.336 2007/05/05 11:48:54 drh Exp $
    22     22   */
    23     23   #ifndef SQLITE_OMIT_DISKIO
    24     24   #include "sqliteInt.h"
    25     25   #include "os.h"
    26     26   #include "pager.h"
    27     27   #include <assert.h>
    28     28   #include <string.h>
................................................................................
   454    454   **
   455    455   ** All values are stored on disk as big-endian.
   456    456   */
   457    457   static int read32bits(OsFile *fd, u32 *pRes){
   458    458     unsigned char ac[4];
   459    459     int rc = sqlite3OsRead(fd, ac, sizeof(ac));
   460    460     if( rc==SQLITE_OK ){
   461         -    *pRes = (ac[0]<<24) | (ac[1]<<16) | (ac[2]<<8) | ac[3];
          461  +    *pRes = sqlite3Get4byte(ac);
   462    462     }
   463    463     return rc;
   464    464   }
   465    465   
   466    466   /*
   467    467   ** Write a 32-bit integer into a string buffer in big-endian byte order.
   468    468   */
   469         -static void put32bits(char *ac, u32 val){
   470         -  ac[0] = (val>>24) & 0xff;
   471         -  ac[1] = (val>>16) & 0xff;
   472         -  ac[2] = (val>>8) & 0xff;
   473         -  ac[3] = val & 0xff;
   474         -}
          469  +#define put32bits(A,B)  sqlite3Put4byte((u8*)A,B)
   475    470   
   476    471   /*
   477    472   ** Write a 32-bit integer into the given file descriptor.  Return SQLITE_OK
   478    473   ** on success or an error code is something goes wrong.
   479    474   */
   480    475   static int write32bits(OsFile *fd, u32 val){
   481    476     char ac[4];
................................................................................
   486    481   /*
   487    482   ** Read a 32-bit integer at offset 'offset' from the page identified by
   488    483   ** page header 'p'.
   489    484   */
   490    485   static u32 retrieve32bits(PgHdr *p, int offset){
   491    486     unsigned char *ac;
   492    487     ac = &((unsigned char*)PGHDR_TO_DATA(p))[offset];
   493         -  return (ac[0]<<24) | (ac[1]<<16) | (ac[2]<<8) | ac[3];
          488  +  return sqlite3Get4byte(ac);
   494    489   }
   495    490   
   496    491   
   497    492   /*
   498    493   ** This function should be called when an error occurs within the pager
   499    494   ** code. The first argument is a pointer to the pager structure, the
   500    495   ** second the error-code about to be returned by a pager API function. 

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.556 2007/05/04 18:30:41 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.557 2007/05/05 11:48:54 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   #if defined(SQLITE_TCL) || defined(TCLSH)
    20     20   # include <tcl.h>
    21     21   #endif
................................................................................
  1910   1910   int sqlite3VtabCallCreate(sqlite3*, int, const char *, char **);
  1911   1911   int sqlite3VtabCallConnect(Parse*, Table*);
  1912   1912   int sqlite3VtabCallDestroy(sqlite3*, int, const char *);
  1913   1913   int sqlite3VtabBegin(sqlite3 *, sqlite3_vtab *);
  1914   1914   FuncDef *sqlite3VtabOverloadFunction(FuncDef*, int nArg, Expr*);
  1915   1915   void sqlite3InvalidFunction(sqlite3_context*,int,sqlite3_value**);
  1916   1916   int sqlite3Reprepare(Vdbe*);
         1917  +
         1918  +u32 sqlite3Get2byte(const u8*);
         1919  +u32 sqlite3Get4byte(const u8*);
         1920  +void sqlite3Put2byte(u8*, u32);
         1921  +void sqlite3Put4byte(u8*, u32);
  1917   1922   
  1918   1923   #ifdef SQLITE_SSE
  1919   1924   #include "sseInt.h"
  1920   1925   #endif
  1921   1926   
  1922   1927   /*
  1923   1928   ** If the SQLITE_ENABLE IOTRACE exists then the global variable

Changes to src/test1.c.

     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Code for testing all sorts of SQLite interfaces.  This code
    13     13   ** is not included in the SQLite library.  It is used for automated
    14     14   ** testing of the SQLite library.
    15     15   **
    16         -** $Id: test1.c,v 1.244 2007/05/04 19:03:03 danielk1977 Exp $
           16  +** $Id: test1.c,v 1.245 2007/05/05 11:48:54 drh Exp $
    17     17   */
    18     18   #include "sqliteInt.h"
    19     19   #include "tcl.h"
    20     20   #include "os.h"
    21     21   #include <stdlib.h>
    22     22   #include <string.h>
    23     23   
................................................................................
    26     26   ** tclsqlite.c.  We need it here so that the get_sqlite_pointer routine
    27     27   ** can extract the sqlite3* pointer from an existing Tcl SQLite
    28     28   ** connection.
    29     29   */
    30     30   struct SqliteDb {
    31     31     sqlite3 *db;
    32     32   };
           33  +
           34  +/*
           35  +** Convert text generated by the "%p" conversion format back into
           36  +** a pointer.
           37  +*/
           38  +static int testHexToInt(int h){
           39  +  if( h>='0' && h<='9' ){
           40  +    return h - '0';
           41  +  }else if( h>='a' && h<='f' ){
           42  +    return h - 'a' + 10;
           43  +  }else{
           44  +    assert( h>='A' && h<='F' );
           45  +    return h - 'A' + 10;
           46  +  }
           47  +}
           48  +void *sqlite3TextToPtr(const char *z){
           49  +  void *p;
           50  +  u64 v;
           51  +  u32 v2;
           52  +  if( z[0]=='0' && z[1]=='x' ){
           53  +    z += 2;
           54  +  }
           55  +  v = 0;
           56  +  while( *z ){
           57  +    v = (v<<4) + testHexToInt(*z);
           58  +    z++;
           59  +  }
           60  +  if( sizeof(p)==sizeof(v) ){
           61  +    memcpy(&p, &v, sizeof(p));
           62  +  }else{
           63  +    assert( sizeof(p)==sizeof(v2) );
           64  +    v2 = (u32)v;
           65  +    memcpy(&p, &v2, sizeof(p));
           66  +  }
           67  +  return p;
           68  +}
           69  +
    33     70   
    34     71   /*
    35     72   ** A TCL command that returns the address of the sqlite* pointer
    36     73   ** for an sqlite connection instance.  Bad things happen if the
    37     74   ** input is not an sqlite connection.
    38     75   */
    39     76   static int get_sqlite_pointer(

Changes to src/util.c.

    10     10   **
    11     11   *************************************************************************
    12     12   ** Utility functions used throughout sqlite.
    13     13   **
    14     14   ** This file contains functions for allocating memory, comparing
    15     15   ** strings, and stuff like that.
    16     16   **
    17         -** $Id: util.c,v 1.200 2007/05/04 13:15:56 drh Exp $
           17  +** $Id: util.c,v 1.201 2007/05/05 11:48:54 drh Exp $
    18     18   */
    19     19   #include "sqliteInt.h"
    20     20   #include "os.h"
    21     21   #include <stdarg.h>
    22     22   #include <ctype.h>
    23     23   
    24         -/*
    25         -** MALLOC WRAPPER ARCHITECTURE
    26         -**
    27         -** The sqlite code accesses dynamic memory allocation/deallocation by invoking
    28         -** the following six APIs (which may be implemented as macros).
    29         -**
    30         -**     sqlite3Malloc()
    31         -**     sqlite3MallocRaw()
    32         -**     sqlite3Realloc()
    33         -**     sqlite3ReallocOrFree()
    34         -**     sqlite3Free()
    35         -**     sqlite3AllocSize()
    36         -**
    37         -** The function sqlite3FreeX performs the same task as sqlite3Free and is
    38         -** guaranteed to be a real function. The same holds for sqlite3MallocX
    39         -**
    40         -** The above APIs are implemented in terms of the functions provided in the
    41         -** operating-system interface. The OS interface is never accessed directly
    42         -** by code outside of this file.
    43         -**
    44         -**     sqlite3OsMalloc()
    45         -**     sqlite3OsRealloc()
    46         -**     sqlite3OsFree()
    47         -**     sqlite3OsAllocationSize()
    48         -**
    49         -** Functions sqlite3MallocRaw() and sqlite3Realloc() may invoke 
    50         -** sqlite3_release_memory() if a call to sqlite3OsMalloc() or
    51         -** sqlite3OsRealloc() fails (or if the soft-heap-limit for the thread is
    52         -** exceeded). Function sqlite3Malloc() usually invokes
    53         -** sqlite3MallocRaw().
    54         -**
    55         -** MALLOC TEST WRAPPER ARCHITECTURE
    56         -**
    57         -** The test wrapper provides extra test facilities to ensure the library 
    58         -** does not leak memory and handles the failure of the underlying OS level
    59         -** allocation system correctly. It is only present if the library is 
    60         -** compiled with the SQLITE_MEMDEBUG macro set.
    61         -**
    62         -**     * Guardposts to detect overwrites.
    63         -**     * Ability to cause a specific Malloc() or Realloc() to fail.
    64         -**     * Audit outstanding memory allocations (i.e check for leaks).
    65         -*/
    66         -
    67         -#define MAX(x,y) ((x)>(y)?(x):(y))
    68         -
    69         -#if defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) && !defined(SQLITE_OMIT_DISKIO)
    70         -/*
    71         -** Set the soft heap-size limit for the current thread. Passing a negative
    72         -** value indicates no limit.
    73         -*/
    74         -void sqlite3_soft_heap_limit(int n){
    75         -  ThreadData *pTd = sqlite3ThreadData();
    76         -  if( pTd ){
    77         -    pTd->nSoftHeapLimit = n;
    78         -  }
    79         -  sqlite3ReleaseThreadData();
    80         -}
    81         -
    82         -/*
    83         -** Release memory held by SQLite instances created by the current thread.
    84         -*/
    85         -int sqlite3_release_memory(int n){
    86         -  return sqlite3PagerReleaseMemory(n);
    87         -}
    88         -#else
    89         -/* If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, then define a version
    90         -** of sqlite3_release_memory() to be used by other code in this file.
    91         -** This is done for no better reason than to reduce the number of 
    92         -** pre-processor #ifndef statements.
    93         -*/
    94         -#define sqlite3_release_memory(x) 0    /* 0 == no memory freed */
    95         -#endif
    96         -
    97         -#ifdef SQLITE_MEMDEBUG
    98         -/*--------------------------------------------------------------------------
    99         -** Begin code for memory allocation system test layer.
   100         -**
   101         -** Memory debugging is turned on by defining the SQLITE_MEMDEBUG macro.
   102         -**
   103         -** SQLITE_MEMDEBUG==1    -> Fence-posting only (thread safe) 
   104         -** SQLITE_MEMDEBUG==2    -> Fence-posting + linked list of allocations (not ts)
   105         -** SQLITE_MEMDEBUG==3    -> Above + backtraces (not thread safe, req. glibc)
   106         -*/
   107         -
   108         -/* Figure out whether or not to store backtrace() information for each malloc.
   109         -** The backtrace() function is only used if SQLITE_MEMDEBUG is set to 2 or 
   110         -** greater and glibc is in use. If we don't want to use backtrace(), then just
   111         -** define it as an empty macro and set the amount of space reserved to 0.
   112         -*/
   113         -#if defined(__GLIBC__) && SQLITE_MEMDEBUG>2
   114         -  extern int backtrace(void **, int);
   115         -  #define TESTALLOC_STACKSIZE 128
   116         -  #define TESTALLOC_STACKFRAMES ((TESTALLOC_STACKSIZE-8)/sizeof(void*))
   117         -#else
   118         -  #define backtrace(x, y)
   119         -  #define TESTALLOC_STACKSIZE 0
   120         -  #define TESTALLOC_STACKFRAMES 0
   121         -#endif
   122         -
   123         -/*
   124         -** Number of 32-bit guard words.  This should probably be a multiple of
   125         -** 2 since on 64-bit machines we want the value returned by sqliteMalloc()
   126         -** to be 8-byte aligned.
   127         -*/
   128         -#ifndef TESTALLOC_NGUARD
   129         -# define TESTALLOC_NGUARD 2
   130         -#endif
   131         -
   132         -/*
   133         -** Size reserved for storing file-name along with each malloc()ed blob.
   134         -*/
   135         -#define TESTALLOC_FILESIZE 64
   136         -
   137         -/*
   138         -** Size reserved for storing the user string. Each time a Malloc() or Realloc()
   139         -** call succeeds, up to TESTALLOC_USERSIZE bytes of the string pointed to by
   140         -** sqlite3_malloc_id are stored along with the other test system metadata.
   141         -*/
   142         -#define TESTALLOC_USERSIZE 64
   143         -const char *sqlite3_malloc_id = 0;
   144         -
   145         -/*
   146         -** Blocks used by the test layer have the following format:
   147         -**
   148         -**        <sizeof(void *) pNext pointer>
   149         -**        <sizeof(void *) pPrev pointer>
   150         -**        <TESTALLOC_NGUARD 32-bit guard words>
   151         -**            <The application level allocation>
   152         -**        <TESTALLOC_NGUARD 32-bit guard words>
   153         -**        <32-bit line number>
   154         -**        <TESTALLOC_FILESIZE bytes containing null-terminated file name>
   155         -**        <TESTALLOC_STACKSIZE bytes of backtrace() output>
   156         -*/ 
   157         -
   158         -#define TESTALLOC_OFFSET_GUARD1(p)    (sizeof(void *) * 2)
   159         -#define TESTALLOC_OFFSET_DATA(p) ( \
   160         -  TESTALLOC_OFFSET_GUARD1(p) + sizeof(u32) * TESTALLOC_NGUARD \
   161         -)
   162         -#define TESTALLOC_OFFSET_GUARD2(p) ( \
   163         -  TESTALLOC_OFFSET_DATA(p) + sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD \
   164         -)
   165         -#define TESTALLOC_OFFSET_LINENUMBER(p) ( \
   166         -  TESTALLOC_OFFSET_GUARD2(p) + sizeof(u32) * TESTALLOC_NGUARD \
   167         -)
   168         -#define TESTALLOC_OFFSET_FILENAME(p) ( \
   169         -  TESTALLOC_OFFSET_LINENUMBER(p) + sizeof(u32) \
   170         -)
   171         -#define TESTALLOC_OFFSET_USER(p) ( \
   172         -  TESTALLOC_OFFSET_FILENAME(p) + TESTALLOC_FILESIZE \
   173         -)
   174         -#define TESTALLOC_OFFSET_STACK(p) ( \
   175         -  TESTALLOC_OFFSET_USER(p) + TESTALLOC_USERSIZE + 8 - \
   176         -  (TESTALLOC_OFFSET_USER(p) % 8) \
   177         -)
   178         -
   179         -#define TESTALLOC_OVERHEAD ( \
   180         -  sizeof(void *)*2 +                   /* pPrev and pNext pointers */   \
   181         -  TESTALLOC_NGUARD*sizeof(u32)*2 +              /* Guard words */       \
   182         -  sizeof(u32) + TESTALLOC_FILESIZE +   /* File and line number */       \
   183         -  TESTALLOC_USERSIZE +                 /* User string */                \
   184         -  TESTALLOC_STACKSIZE                  /* backtrace() stack */          \
   185         -)
   186         -
   187         -
   188         -/*
   189         -** For keeping track of the number of mallocs and frees.   This
   190         -** is used to check for memory leaks.  The iMallocFail and iMallocReset
   191         -** values are used to simulate malloc() failures during testing in 
   192         -** order to verify that the library correctly handles an out-of-memory
   193         -** condition.
   194         -*/
   195         -int sqlite3_nMalloc;         /* Number of sqliteMalloc() calls */
   196         -int sqlite3_nFree;           /* Number of sqliteFree() calls */
   197         -int sqlite3_memUsed;         /* TODO Total memory obtained from malloc */
   198         -int sqlite3_memMax;          /* TODO Mem usage high-water mark */
   199         -int sqlite3_iMallocFail;     /* Fail sqliteMalloc() after this many calls */
   200         -int sqlite3_iMallocReset = -1; /* When iMallocFail reaches 0, set to this */
   201         -
   202         -void *sqlite3_pFirst = 0;         /* Pointer to linked list of allocations */
   203         -int sqlite3_nMaxAlloc = 0;        /* High water mark of ThreadData.nAlloc */
   204         -int sqlite3_mallocDisallowed = 0; /* assert() in sqlite3Malloc() if set */
   205         -int sqlite3_isFail = 0;           /* True if all malloc calls should fail */
   206         -const char *sqlite3_zFile = 0;    /* Filename to associate debug info with */
   207         -int sqlite3_iLine = 0;            /* Line number for debug info */
   208         -
   209         -/*
   210         -** Check for a simulated memory allocation failure.  Return true if
   211         -** the failure should be simulated.  Return false to proceed as normal.
   212         -*/
   213         -int sqlite3TestMallocFail(){
   214         -  if( sqlite3_isFail ){
   215         -    return 1;
   216         -  }
   217         -  if( sqlite3_iMallocFail>=0 ){
   218         -    sqlite3_iMallocFail--;
   219         -    if( sqlite3_iMallocFail==0 ){
   220         -      sqlite3_iMallocFail = sqlite3_iMallocReset;
   221         -      sqlite3_isFail = 1;
   222         -      return 1;
   223         -    }
   224         -  }
   225         -  return 0;
   226         -}
   227         -
   228         -/*
   229         -** The argument is a pointer returned by sqlite3OsMalloc() or xRealloc().
   230         -** assert() that the first and last (TESTALLOC_NGUARD*4) bytes are set to the
   231         -** values set by the applyGuards() function.
   232         -*/
   233         -static void checkGuards(u32 *p)
   234         -{
   235         -  int i;
   236         -  char *zAlloc = (char *)p;
   237         -  char *z;
   238         -
   239         -  /* First set of guard words */
   240         -  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
   241         -  for(i=0; i<TESTALLOC_NGUARD; i++){
   242         -    assert(((u32 *)z)[i]==0xdead1122);
   243         -  }
   244         -
   245         -  /* Second set of guard words */
   246         -  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
   247         -  for(i=0; i<TESTALLOC_NGUARD; i++){
   248         -    u32 guard = 0;
   249         -    memcpy(&guard, &z[i*sizeof(u32)], sizeof(u32));
   250         -    assert(guard==0xdead3344);
   251         -  }
   252         -}
   253         -
   254         -/*
   255         -** The argument is a pointer returned by sqlite3OsMalloc() or Realloc(). The
   256         -** first and last (TESTALLOC_NGUARD*4) bytes are set to known values for use as 
   257         -** guard-posts.
   258         -*/
   259         -static void applyGuards(u32 *p)
   260         -{
   261         -  int i;
   262         -  char *z;
   263         -  char *zAlloc = (char *)p;
   264         -
   265         -  /* First set of guard words */
   266         -  z = &zAlloc[TESTALLOC_OFFSET_GUARD1(p)];
   267         -  for(i=0; i<TESTALLOC_NGUARD; i++){
   268         -    ((u32 *)z)[i] = 0xdead1122;
   269         -  }
   270         -
   271         -  /* Second set of guard words */
   272         -  z = &zAlloc[TESTALLOC_OFFSET_GUARD2(p)];
   273         -  for(i=0; i<TESTALLOC_NGUARD; i++){
   274         -    static const int guard = 0xdead3344;
   275         -    memcpy(&z[i*sizeof(u32)], &guard, sizeof(u32));
   276         -  }
   277         -
   278         -  /* Line number */
   279         -  z = &((char *)z)[TESTALLOC_NGUARD*sizeof(u32)];             /* Guard words */
   280         -  z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
   281         -  memcpy(z, &sqlite3_iLine, sizeof(u32));
   282         -
   283         -  /* File name */
   284         -  z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
   285         -  strncpy(z, sqlite3_zFile, TESTALLOC_FILESIZE);
   286         -  z[TESTALLOC_FILESIZE - 1] = '\0';
   287         -
   288         -  /* User string */
   289         -  z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
   290         -  z[0] = 0;
   291         -  if( sqlite3_malloc_id ){
   292         -    strncpy(z, sqlite3_malloc_id, TESTALLOC_USERSIZE);
   293         -    z[TESTALLOC_USERSIZE-1] = 0;
   294         -  }
   295         -
   296         -  /* backtrace() stack */
   297         -  z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
   298         -  backtrace((void **)z, TESTALLOC_STACKFRAMES);
   299         -
   300         -  /* Sanity check to make sure checkGuards() is working */
   301         -  checkGuards(p);
   302         -}
   303         -
   304         -/*
   305         -** The argument is a malloc()ed pointer as returned by the test-wrapper.
   306         -** Return a pointer to the Os level allocation.
   307         -*/
   308         -static void *getOsPointer(void *p)
   309         -{
   310         -  char *z = (char *)p;
   311         -  return (void *)(&z[-1 * TESTALLOC_OFFSET_DATA(p)]);
   312         -}
   313         -
   314         -
   315         -#if SQLITE_MEMDEBUG>1
   316         -/*
   317         -** The argument points to an Os level allocation. Link it into the threads list
   318         -** of allocations.
   319         -*/
   320         -static void linkAlloc(void *p){
   321         -  void **pp = (void **)p;
   322         -  pp[0] = 0;
   323         -  pp[1] = sqlite3_pFirst;
   324         -  if( sqlite3_pFirst ){
   325         -    ((void **)sqlite3_pFirst)[0] = p;
   326         -  }
   327         -  sqlite3_pFirst = p;
   328         -}
   329         -
   330         -/*
   331         -** The argument points to an Os level allocation. Unlinke it from the threads
   332         -** list of allocations.
   333         -*/
   334         -static void unlinkAlloc(void *p)
   335         -{
   336         -  void **pp = (void **)p;
   337         -  if( p==sqlite3_pFirst ){
   338         -    assert(!pp[0]);
   339         -    assert(!pp[1] || ((void **)(pp[1]))[0]==p);
   340         -    sqlite3_pFirst = pp[1];
   341         -    if( sqlite3_pFirst ){
   342         -      ((void **)sqlite3_pFirst)[0] = 0;
   343         -    }
   344         -  }else{
   345         -    void **pprev = pp[0];
   346         -    void **pnext = pp[1];
   347         -    assert(pprev);
   348         -    assert(pprev[1]==p);
   349         -    pprev[1] = (void *)pnext;
   350         -    if( pnext ){
   351         -      assert(pnext[0]==p);
   352         -      pnext[0] = (void *)pprev;
   353         -    }
   354         -  }
   355         -}
   356         -
   357         -/*
   358         -** Pointer p is a pointer to an OS level allocation that has just been
   359         -** realloc()ed. Set the list pointers that point to this entry to it's new
   360         -** location.
   361         -*/
   362         -static void relinkAlloc(void *p)
   363         -{
   364         -  void **pp = (void **)p;
   365         -  if( pp[0] ){
   366         -    ((void **)(pp[0]))[1] = p;
   367         -  }else{
   368         -    sqlite3_pFirst = p;
   369         -  }
   370         -  if( pp[1] ){
   371         -    ((void **)(pp[1]))[0] = p;
   372         -  }
   373         -}
   374         -#else
   375         -#define linkAlloc(x)
   376         -#define relinkAlloc(x)
   377         -#define unlinkAlloc(x)
   378         -#endif
   379         -
   380         -/*
   381         -** This function sets the result of the Tcl interpreter passed as an argument
   382         -** to a list containing an entry for each currently outstanding call made to 
   383         -** sqliteMalloc and friends by the current thread. Each list entry is itself a
   384         -** list, consisting of the following (in order):
   385         -**
   386         -**     * The number of bytes allocated
   387         -**     * The __FILE__ macro at the time of the sqliteMalloc() call.
   388         -**     * The __LINE__ macro ...
   389         -**     * The value of the sqlite3_malloc_id variable ...
   390         -**     * The output of backtrace() (if available) ...
   391         -**
   392         -** Todo: We could have a version of this function that outputs to stdout, 
   393         -** to debug memory leaks when Tcl is not available.
   394         -*/
   395         -#if defined(TCLSH) && defined(SQLITE_DEBUG) && SQLITE_MEMDEBUG>1
   396         -#include <tcl.h>
   397         -int sqlite3OutstandingMallocs(Tcl_Interp *interp){
   398         -  void *p;
   399         -  Tcl_Obj *pRes = Tcl_NewObj();
   400         -  Tcl_IncrRefCount(pRes);
   401         -
   402         -
   403         -  for(p=sqlite3_pFirst; p; p=((void **)p)[1]){
   404         -    Tcl_Obj *pEntry = Tcl_NewObj();
   405         -    Tcl_Obj *pStack = Tcl_NewObj();
   406         -    char *z;
   407         -    u32 iLine;
   408         -    int nBytes = sqlite3OsAllocationSize(p) - TESTALLOC_OVERHEAD;
   409         -    char *zAlloc = (char *)p;
   410         -    int i;
   411         -
   412         -    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(nBytes));
   413         -
   414         -    z = &zAlloc[TESTALLOC_OFFSET_FILENAME(p)];
   415         -    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));
   416         -
   417         -    z = &zAlloc[TESTALLOC_OFFSET_LINENUMBER(p)];
   418         -    memcpy(&iLine, z, sizeof(u32));
   419         -    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewIntObj(iLine));
   420         -
   421         -    z = &zAlloc[TESTALLOC_OFFSET_USER(p)];
   422         -    Tcl_ListObjAppendElement(0, pEntry, Tcl_NewStringObj(z, -1));
   423         -
   424         -    z = &zAlloc[TESTALLOC_OFFSET_STACK(p)];
   425         -    for(i=0; i<TESTALLOC_STACKFRAMES; i++){
   426         -      char zHex[128];
   427         -      sqlite3_snprintf(sizeof(zHex), zHex, "%p", ((void **)z)[i]);
   428         -      Tcl_ListObjAppendElement(0, pStack, Tcl_NewStringObj(zHex, -1));
   429         -    }
   430         -
   431         -    Tcl_ListObjAppendElement(0, pEntry, pStack);
   432         -    Tcl_ListObjAppendElement(0, pRes, pEntry);
   433         -  }
   434         -
   435         -  Tcl_ResetResult(interp);
   436         -  Tcl_SetObjResult(interp, pRes);
   437         -  Tcl_DecrRefCount(pRes);
   438         -  return TCL_OK;
   439         -}
   440         -#endif
   441         -
   442         -/*
   443         -** This is the test layer's wrapper around sqlite3OsMalloc().
   444         -*/
   445         -static void * OSMALLOC(int n){
   446         -  sqlite3OsEnterMutex();
   447         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   448         -  sqlite3_nMaxAlloc = 
   449         -      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
   450         -#endif
   451         -  assert( !sqlite3_mallocDisallowed );
   452         -  if( !sqlite3TestMallocFail() ){
   453         -    u32 *p;
   454         -    p = (u32 *)sqlite3OsMalloc(n + TESTALLOC_OVERHEAD);
   455         -    assert(p);
   456         -    sqlite3_nMalloc++;
   457         -    applyGuards(p);
   458         -    linkAlloc(p);
   459         -    sqlite3OsLeaveMutex();
   460         -    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
   461         -  }
   462         -  sqlite3OsLeaveMutex();
   463         -  return 0;
   464         -}
   465         -
   466         -static int OSSIZEOF(void *p){
   467         -  if( p ){
   468         -    u32 *pOs = (u32 *)getOsPointer(p);
   469         -    return sqlite3OsAllocationSize(pOs) - TESTALLOC_OVERHEAD;
   470         -  }
   471         -  return 0;
   472         -}
   473         -
   474         -/*
   475         -** This is the test layer's wrapper around sqlite3OsFree(). The argument is a
   476         -** pointer to the space allocated for the application to use.
   477         -*/
   478         -static void OSFREE(void *pFree){
   479         -  u32 *p;         /* Pointer to the OS-layer allocation */
   480         -  sqlite3OsEnterMutex();
   481         -  p = (u32 *)getOsPointer(pFree);
   482         -  checkGuards(p);
   483         -  unlinkAlloc(p);
   484         -  memset(pFree, 0x55, OSSIZEOF(pFree));
   485         -  sqlite3OsFree(p);
   486         -  sqlite3_nFree++;
   487         -  sqlite3OsLeaveMutex();
   488         -}
   489         -
   490         -/*
   491         -** This is the test layer's wrapper around sqlite3OsRealloc().
   492         -*/
   493         -static void * OSREALLOC(void *pRealloc, int n){
   494         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   495         -  sqlite3_nMaxAlloc = 
   496         -      MAX(sqlite3_nMaxAlloc, sqlite3ThreadDataReadOnly()->nAlloc);
   497         -#endif
   498         -  assert( !sqlite3_mallocDisallowed );
   499         -  if( !sqlite3TestMallocFail() ){
   500         -    u32 *p = (u32 *)getOsPointer(pRealloc);
   501         -    checkGuards(p);
   502         -    p = sqlite3OsRealloc(p, n + TESTALLOC_OVERHEAD);
   503         -    applyGuards(p);
   504         -    relinkAlloc(p);
   505         -    return (void *)(&p[TESTALLOC_NGUARD + 2*sizeof(void *)/sizeof(u32)]);
   506         -  }
   507         -  return 0;
   508         -}
   509         -
   510         -static void OSMALLOC_FAILED(){
   511         -  sqlite3_isFail = 0;
   512         -}
   513         -
   514         -#else
   515         -/* Define macros to call the sqlite3OsXXX interface directly if 
   516         -** the SQLITE_MEMDEBUG macro is not defined.
   517         -*/
   518         -#define OSMALLOC(x)        sqlite3OsMalloc(x)
   519         -#define OSREALLOC(x,y)     sqlite3OsRealloc(x,y)
   520         -#define OSFREE(x)          sqlite3OsFree(x)
   521         -#define OSSIZEOF(x)        sqlite3OsAllocationSize(x)
   522         -#define OSMALLOC_FAILED()
   523         -
   524         -#endif  /* SQLITE_MEMDEBUG */
   525         -/*
   526         -** End code for memory allocation system test layer.
   527         -**--------------------------------------------------------------------------*/
   528         -
   529         -/*
   530         -** This routine is called when we are about to allocate n additional bytes
   531         -** of memory.  If the new allocation will put is over the soft allocation
   532         -** limit, then invoke sqlite3_release_memory() to try to release some
   533         -** memory before continuing with the allocation.
   534         -**
   535         -** This routine also makes sure that the thread-specific-data (TSD) has
   536         -** be allocated.  If it has not and can not be allocated, then return
   537         -** false.  The updateMemoryUsedCount() routine below will deallocate
   538         -** the TSD if it ought to be.
   539         -**
   540         -** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
   541         -** a no-op
   542         -*/ 
   543         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   544         -static int enforceSoftLimit(int n){
   545         -  ThreadData *pTsd = sqlite3ThreadData();
   546         -  if( pTsd==0 ){
   547         -    return 0;
   548         -  }
   549         -  assert( pTsd->nAlloc>=0 );
   550         -  if( n>0 && pTsd->nSoftHeapLimit>0 ){
   551         -    while( pTsd->nAlloc+n>pTsd->nSoftHeapLimit && sqlite3_release_memory(n) ){}
   552         -  }
   553         -  return 1;
   554         -}
   555         -#else
   556         -# define enforceSoftLimit(X)  1
   557         -#endif
   558         -
   559         -/*
   560         -** Update the count of total outstanding memory that is held in
   561         -** thread-specific-data (TSD).  If after this update the TSD is
   562         -** no longer being used, then deallocate it.
   563         -**
   564         -** If SQLITE_ENABLE_MEMORY_MANAGEMENT is not defined, this routine is
   565         -** a no-op
   566         -*/
   567         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   568         -static void updateMemoryUsedCount(int n){
   569         -  ThreadData *pTsd = sqlite3ThreadData();
   570         -  if( pTsd ){
   571         -    pTsd->nAlloc += n;
   572         -    assert( pTsd->nAlloc>=0 );
   573         -    if( pTsd->nAlloc==0 && pTsd->nSoftHeapLimit==0 ){
   574         -      sqlite3ReleaseThreadData();
   575         -    }
   576         -  }
   577         -}
   578         -#else
   579         -#define updateMemoryUsedCount(x)  /* no-op */
   580         -#endif
   581         -
   582         -/*
   583         -** Allocate and return N bytes of uninitialised memory by calling
   584         -** sqlite3OsMalloc(). If the Malloc() call fails, attempt to free memory 
   585         -** by calling sqlite3_release_memory().
   586         -*/
   587         -void *sqlite3MallocRaw(int n, int doMemManage){
   588         -  void *p = 0;
   589         -  if( n>0 && !sqlite3MallocFailed() && (!doMemManage || enforceSoftLimit(n)) ){
   590         -    while( (p = OSMALLOC(n))==0 && sqlite3_release_memory(n) ){}
   591         -    if( !p ){
   592         -      sqlite3FailedMalloc();
   593         -      OSMALLOC_FAILED();
   594         -    }else if( doMemManage ){
   595         -      updateMemoryUsedCount(OSSIZEOF(p));
   596         -    }
   597         -  }
   598         -  return p;
   599         -}
   600         -
   601         -/*
   602         -** Resize the allocation at p to n bytes by calling sqlite3OsRealloc(). The
   603         -** pointer to the new allocation is returned.  If the Realloc() call fails,
   604         -** attempt to free memory by calling sqlite3_release_memory().
   605         -*/
   606         -void *sqlite3Realloc(void *p, int n){
   607         -  if( sqlite3MallocFailed() ){
   608         -    return 0;
   609         -  }
   610         -
   611         -  if( !p ){
   612         -    return sqlite3Malloc(n, 1);
   613         -  }else{
   614         -    void *np = 0;
   615         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   616         -    int origSize = OSSIZEOF(p);
   617         -#endif
   618         -    if( enforceSoftLimit(n - origSize) ){
   619         -      while( (np = OSREALLOC(p, n))==0 && sqlite3_release_memory(n) ){}
   620         -      if( !np ){
   621         -        sqlite3FailedMalloc();
   622         -        OSMALLOC_FAILED();
   623         -      }else{
   624         -        updateMemoryUsedCount(OSSIZEOF(np) - origSize);
   625         -      }
   626         -    }
   627         -    return np;
   628         -  }
   629         -}
   630         -
   631         -/*
   632         -** Free the memory pointed to by p. p must be either a NULL pointer or a 
   633         -** value returned by a previous call to sqlite3Malloc() or sqlite3Realloc().
   634         -*/
   635         -void sqlite3FreeX(void *p){
   636         -  if( p ){
   637         -    updateMemoryUsedCount(0 - OSSIZEOF(p));
   638         -    OSFREE(p);
   639         -  }
   640         -}
   641         -
   642         -/*
   643         -** A version of sqliteMalloc() that is always a function, not a macro.
   644         -** Currently, this is used only to alloc to allocate the parser engine.
   645         -*/
   646         -void *sqlite3MallocX(int n){
   647         -  return sqliteMalloc(n);
   648         -}
   649         -
   650         -/*
   651         -** sqlite3Malloc
   652         -** sqlite3ReallocOrFree
   653         -**
   654         -** These two are implemented as wrappers around sqlite3MallocRaw(), 
   655         -** sqlite3Realloc() and sqlite3Free().
   656         -*/ 
   657         -void *sqlite3Malloc(int n, int doMemManage){
   658         -  void *p = sqlite3MallocRaw(n, doMemManage);
   659         -  if( p ){
   660         -    memset(p, 0, n);
   661         -  }
   662         -  return p;
   663         -}
   664         -void *sqlite3ReallocOrFree(void *p, int n){
   665         -  void *pNew;
   666         -  pNew = sqlite3Realloc(p, n);
   667         -  if( !pNew ){
   668         -    sqlite3FreeX(p);
   669         -  }
   670         -  return pNew;
   671         -}
   672         -
   673         -/*
   674         -** sqlite3ThreadSafeMalloc() and sqlite3ThreadSafeFree() are used in those
   675         -** rare scenarios where sqlite may allocate memory in one thread and free
   676         -** it in another. They are exactly the same as sqlite3Malloc() and 
   677         -** sqlite3Free() except that:
   678         -**
   679         -**   * The allocated memory is not included in any calculations with 
   680         -**     respect to the soft-heap-limit, and
   681         -**
   682         -**   * sqlite3ThreadSafeMalloc() must be matched with ThreadSafeFree(),
   683         -**     not sqlite3Free(). Calling sqlite3Free() on memory obtained from
   684         -**     ThreadSafeMalloc() will cause an error somewhere down the line.
   685         -*/
   686         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   687         -void *sqlite3ThreadSafeMalloc(int n){
   688         -  (void)ENTER_MALLOC;
   689         -  return sqlite3Malloc(n, 0);
   690         -}
   691         -void sqlite3ThreadSafeFree(void *p){
   692         -  (void)ENTER_MALLOC;
   693         -  if( p ){
   694         -    OSFREE(p);
   695         -  }
   696         -}
   697         -#endif
   698         -
   699         -
   700         -/*
   701         -** Return the number of bytes allocated at location p. p must be either 
   702         -** a NULL pointer (in which case 0 is returned) or a pointer returned by 
   703         -** sqlite3Malloc(), sqlite3Realloc() or sqlite3ReallocOrFree().
   704         -**
   705         -** The number of bytes allocated does not include any overhead inserted by 
   706         -** any malloc() wrapper functions that may be called. So the value returned
   707         -** is the number of bytes that were available to SQLite using pointer p, 
   708         -** regardless of how much memory was actually allocated.
   709         -*/
   710         -#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
   711         -int sqlite3AllocSize(void *p){
   712         -  return OSSIZEOF(p);
   713         -}
   714         -#endif
   715         -
   716         -/*
   717         -** Make a copy of a string in memory obtained from sqliteMalloc(). These 
   718         -** functions call sqlite3MallocRaw() directly instead of sqliteMalloc(). This
   719         -** is because when memory debugging is turned on, these two functions are 
   720         -** called via macros that record the current file and line number in the
   721         -** ThreadData structure.
   722         -*/
   723         -char *sqlite3StrDup(const char *z){
   724         -  char *zNew;
   725         -  int n;
   726         -  if( z==0 ) return 0;
   727         -  n = strlen(z)+1;
   728         -  zNew = sqlite3MallocRaw(n, 1);
   729         -  if( zNew ) memcpy(zNew, z, n);
   730         -  return zNew;
   731         -}
   732         -char *sqlite3StrNDup(const char *z, int n){
   733         -  char *zNew;
   734         -  if( z==0 ) return 0;
   735         -  zNew = sqlite3MallocRaw(n+1, 1);
   736         -  if( zNew ){
   737         -    memcpy(zNew, z, n);
   738         -    zNew[n] = 0;
   739         -  }
   740         -  return zNew;
   741         -}
   742         -
   743         -/*
   744         -** Create a string from the 2nd and subsequent arguments (up to the
   745         -** first NULL argument), store the string in memory obtained from
   746         -** sqliteMalloc() and make the pointer indicated by the 1st argument
   747         -** point to that string.  The 1st argument must either be NULL or 
   748         -** point to memory obtained from sqliteMalloc().
   749         -*/
   750         -void sqlite3SetString(char **pz, ...){
   751         -  va_list ap;
   752         -  int nByte;
   753         -  const char *z;
   754         -  char *zResult;
   755         -
   756         -  assert( pz!=0 );
   757         -  nByte = 1;
   758         -  va_start(ap, pz);
   759         -  while( (z = va_arg(ap, const char*))!=0 ){
   760         -    nByte += strlen(z);
   761         -  }
   762         -  va_end(ap);
   763         -  sqliteFree(*pz);
   764         -  *pz = zResult = sqliteMallocRaw( nByte );
   765         -  if( zResult==0 ){
   766         -    return;
   767         -  }
   768         -  *zResult = 0;
   769         -  va_start(ap, pz);
   770         -  while( (z = va_arg(ap, const char*))!=0 ){
   771         -    int n = strlen(z);
   772         -    memcpy(zResult, z, n);
   773         -    zResult += n;
   774         -  }
   775         -  zResult[0] = 0;
   776         -  va_end(ap);
   777         -}
   778     24   
   779     25   /*
   780     26   ** Set the most recent error code and error string for the sqlite
   781     27   ** handle "db". The error code is set to "err_code".
   782     28   **
   783     29   ** If it is not NULL, string zFormat specifies the format of the
   784     30   ** error string in the style of the printf functions: The following
................................................................................
  1128    374     int i, c;
  1129    375     if( *zNum=='-' || *zNum=='+' ) zNum++;
  1130    376     for(i=0; (c=zNum[i])>='0' && c<='9'; i++){}
  1131    377     return i<19 || (i==19 && memcmp(zNum,"9223372036854775807",19)<=0);
  1132    378   }
  1133    379   
  1134    380   
  1135         -/*
  1136         -** Change the sqlite.magic from SQLITE_MAGIC_OPEN to SQLITE_MAGIC_BUSY.
  1137         -** Return an error (non-zero) if the magic was not SQLITE_MAGIC_OPEN
  1138         -** when this routine is called.
  1139         -**
  1140         -** This routine is called when entering an SQLite API.  The SQLITE_MAGIC_OPEN
  1141         -** value indicates that the database connection passed into the API is
  1142         -** open and is not being used by another thread.  By changing the value
  1143         -** to SQLITE_MAGIC_BUSY we indicate that the connection is in use.
  1144         -** sqlite3SafetyOff() below will change the value back to SQLITE_MAGIC_OPEN
  1145         -** when the API exits. 
  1146         -**
  1147         -** This routine is a attempt to detect if two threads use the
  1148         -** same sqlite* pointer at the same time.  There is a race 
  1149         -** condition so it is possible that the error is not detected.
  1150         -** But usually the problem will be seen.  The result will be an
  1151         -** error which can be used to debug the application that is
  1152         -** using SQLite incorrectly.
  1153         -**
  1154         -** Ticket #202:  If db->magic is not a valid open value, take care not
  1155         -** to modify the db structure at all.  It could be that db is a stale
  1156         -** pointer.  In other words, it could be that there has been a prior
  1157         -** call to sqlite3_close(db) and db has been deallocated.  And we do
  1158         -** not want to write into deallocated memory.
  1159         -*/
  1160         -int sqlite3SafetyOn(sqlite3 *db){
  1161         -  if( db->magic==SQLITE_MAGIC_OPEN ){
  1162         -    db->magic = SQLITE_MAGIC_BUSY;
  1163         -    return 0;
  1164         -  }else if( db->magic==SQLITE_MAGIC_BUSY ){
  1165         -    db->magic = SQLITE_MAGIC_ERROR;
  1166         -    db->u1.isInterrupted = 1;
  1167         -  }
  1168         -  return 1;
  1169         -}
  1170         -
  1171         -/*
  1172         -** Change the magic from SQLITE_MAGIC_BUSY to SQLITE_MAGIC_OPEN.
  1173         -** Return an error (non-zero) if the magic was not SQLITE_MAGIC_BUSY
  1174         -** when this routine is called.
  1175         -*/
  1176         -int sqlite3SafetyOff(sqlite3 *db){
  1177         -  if( db->magic==SQLITE_MAGIC_BUSY ){
  1178         -    db->magic = SQLITE_MAGIC_OPEN;
  1179         -    return 0;
  1180         -  }else {
  1181         -    db->magic = SQLITE_MAGIC_ERROR;
  1182         -    db->u1.isInterrupted = 1;
  1183         -    return 1;
  1184         -  }
  1185         -}
  1186         -
  1187    381   /*
  1188    382   ** Check to make sure we have a valid db pointer.  This test is not
  1189    383   ** foolproof but it does provide some measure of protection against
  1190    384   ** misuse of the interface such as passing in db pointers that are
  1191    385   ** NULL or which have been previously closed.  If this routine returns
  1192    386   ** TRUE it means that the db pointer is invalid and should not be
  1193    387   ** dereferenced for any reason.  The calling function should invoke
................................................................................
  1333    527     int i = 0;
  1334    528     do{
  1335    529       i++;
  1336    530       v >>= 7;
  1337    531     }while( v!=0 && i<9 );
  1338    532     return i;
  1339    533   }
          534  +
          535  +
          536  +/*
          537  +** Read or write a two- and four-byte big-endian integer values.
          538  +*/
          539  +u32 sqlite3Get2byte(const u8 *p){
          540  +  return (p[0]<<8) | p[1];
          541  +}
          542  +u32 sqlite3Get4byte(const u8 *p){
          543  +  return (p[0]<<24) | (p[1]<<16) | (p[2]<<8) | p[3];
          544  +}
          545  +void sqlite3Put2byte(unsigned char *p, u32 v){
          546  +  p[0] = v>>8;
          547  +  p[1] = v;
          548  +}
          549  +void sqlite3Put4byte(unsigned char *p, u32 v){
          550  +  p[0] = v>>24;
          551  +  p[1] = v>>16;
          552  +  p[2] = v>>8;
          553  +  p[3] = v;
          554  +}
          555  +
          556  +
  1340    557   
  1341    558   #if !defined(SQLITE_OMIT_BLOB_LITERAL) || defined(SQLITE_HAS_CODEC) \
  1342    559       || defined(SQLITE_TEST)
  1343    560   /*
  1344    561   ** Translate a single byte of Hex into an integer.
  1345    562   */
  1346    563   static int hexToInt(int h){
................................................................................
  1374    591         zBlob[i/2] = (hexToInt(z[i])<<4) | hexToInt(z[i+1]);
  1375    592       }
  1376    593     }
  1377    594     return zBlob;
  1378    595   }
  1379    596   #endif /* !SQLITE_OMIT_BLOB_LITERAL || SQLITE_HAS_CODEC */
  1380    597   
  1381         -#if defined(SQLITE_TEST)
          598  +
  1382    599   /*
  1383         -** Convert text generated by the "%p" conversion format back into
  1384         -** a pointer.
          600  +** Change the sqlite.magic from SQLITE_MAGIC_OPEN to SQLITE_MAGIC_BUSY.
          601  +** Return an error (non-zero) if the magic was not SQLITE_MAGIC_OPEN
          602  +** when this routine is called.
          603  +**
          604  +** This routine is called when entering an SQLite API.  The SQLITE_MAGIC_OPEN
          605  +** value indicates that the database connection passed into the API is
          606  +** open and is not being used by another thread.  By changing the value
          607  +** to SQLITE_MAGIC_BUSY we indicate that the connection is in use.
          608  +** sqlite3SafetyOff() below will change the value back to SQLITE_MAGIC_OPEN
          609  +** when the API exits. 
          610  +**
          611  +** This routine is a attempt to detect if two threads use the
          612  +** same sqlite* pointer at the same time.  There is a race 
          613  +** condition so it is possible that the error is not detected.
          614  +** But usually the problem will be seen.  The result will be an
          615  +** error which can be used to debug the application that is
          616  +** using SQLite incorrectly.
          617  +**
          618  +** Ticket #202:  If db->magic is not a valid open value, take care not
          619  +** to modify the db structure at all.  It could be that db is a stale
          620  +** pointer.  In other words, it could be that there has been a prior
          621  +** call to sqlite3_close(db) and db has been deallocated.  And we do
          622  +** not want to write into deallocated memory.
  1385    623   */
  1386         -void *sqlite3TextToPtr(const char *z){
  1387         -  void *p;
  1388         -  u64 v;
  1389         -  u32 v2;
  1390         -  if( z[0]=='0' && z[1]=='x' ){
  1391         -    z += 2;
  1392         -  }
  1393         -  v = 0;
  1394         -  while( *z ){
  1395         -    v = (v<<4) + hexToInt(*z);
  1396         -    z++;
          624  +int sqlite3SafetyOn(sqlite3 *db){
          625  +  if( db->magic==SQLITE_MAGIC_OPEN ){
          626  +    db->magic = SQLITE_MAGIC_BUSY;
          627  +    return 0;
          628  +  }else if( db->magic==SQLITE_MAGIC_BUSY ){
          629  +    db->magic = SQLITE_MAGIC_ERROR;
          630  +    db->u1.isInterrupted = 1;
  1397    631     }
  1398         -  if( sizeof(p)==sizeof(v) ){
  1399         -    memcpy(&p, &v, sizeof(p));
  1400         -  }else{
  1401         -    assert( sizeof(p)==sizeof(v2) );
  1402         -    v2 = (u32)v;
  1403         -    memcpy(&p, &v2, sizeof(p));
  1404         -  }
  1405         -  return p;
          632  +  return 1;
  1406    633   }
  1407         -#endif
          634  +
          635  +/*
          636  +** Change the magic from SQLITE_MAGIC_BUSY to SQLITE_MAGIC_OPEN.
          637  +** Return an error (non-zero) if the magic was not SQLITE_MAGIC_BUSY
          638  +** when this routine is called.
          639  +*/
          640  +int sqlite3SafetyOff(sqlite3 *db){
          641  +  if( db->magic==SQLITE_MAGIC_BUSY ){
          642  +    db->magic = SQLITE_MAGIC_OPEN;
          643  +    return 0;
          644  +  }else {
          645  +    db->magic = SQLITE_MAGIC_ERROR;
          646  +    db->u1.isInterrupted = 1;
          647  +    return 1;
          648  +  }
          649  +}
  1408    650   
  1409    651   /*
  1410    652   ** Return a pointer to the ThreadData associated with the calling thread.
  1411    653   */
  1412    654   ThreadData *sqlite3ThreadData(){
  1413    655     ThreadData *p = (ThreadData*)sqlite3OsThreadSpecificData(1);
  1414    656     if( !p ){
................................................................................
  1432    674   /*
  1433    675   ** Check to see if the ThreadData for this thread is all zero.  If it
  1434    676   ** is, then deallocate it. 
  1435    677   */
  1436    678   void sqlite3ReleaseThreadData(){
  1437    679     sqlite3OsThreadSpecificData(-1);
  1438    680   }
  1439         -
  1440         -/*
  1441         -** This function must be called before exiting any API function (i.e. 
  1442         -** returning control to the user) that has called sqlite3Malloc or
  1443         -** sqlite3Realloc.
  1444         -**
  1445         -** The returned value is normally a copy of the second argument to this
  1446         -** function. However, if a malloc() failure has occured since the previous
  1447         -** invocation SQLITE_NOMEM is returned instead. 
  1448         -**
  1449         -** If the first argument, db, is not NULL and a malloc() error has occured,
  1450         -** then the connection error-code (the value returned by sqlite3_errcode())
  1451         -** is set to SQLITE_NOMEM.
  1452         -*/
  1453         -static int mallocHasFailed = 0;
  1454         -int sqlite3ApiExit(sqlite3* db, int rc){
  1455         -  if( sqlite3MallocFailed() ){
  1456         -    mallocHasFailed = 0;
  1457         -    sqlite3OsLeaveMutex();
  1458         -    sqlite3Error(db, SQLITE_NOMEM, 0);
  1459         -    rc = SQLITE_NOMEM;
  1460         -  }
  1461         -  return rc & (db ? db->errMask : 0xff);
  1462         -}
  1463         -
  1464         -/* 
  1465         -** Return true is a malloc has failed in this thread since the last call
  1466         -** to sqlite3ApiExit(), or false otherwise.
  1467         -*/
  1468         -int sqlite3MallocFailed(){
  1469         -  return (mallocHasFailed && sqlite3OsInMutex(1));
  1470         -}
  1471         -
  1472         -/* 
  1473         -** Set the "malloc has failed" condition to true for this thread.
  1474         -*/
  1475         -void sqlite3FailedMalloc(){
  1476         -  if( !sqlite3MallocFailed() ){
  1477         -    sqlite3OsEnterMutex();
  1478         -    assert( mallocHasFailed==0 );
  1479         -    mallocHasFailed = 1;
  1480         -  }
  1481         -}
  1482         -
  1483         -#ifdef SQLITE_MEMDEBUG
  1484         -/*
  1485         -** This function sets a flag in the thread-specific-data structure that will
  1486         -** cause an assert to fail if sqliteMalloc() or sqliteRealloc() is called.
  1487         -*/
  1488         -void sqlite3MallocDisallow(){
  1489         -  assert( sqlite3_mallocDisallowed>=0 );
  1490         -  sqlite3_mallocDisallowed++;
  1491         -}
  1492         -
  1493         -/*
  1494         -** This function clears the flag set in the thread-specific-data structure set
  1495         -** by sqlite3MallocDisallow().
  1496         -*/
  1497         -void sqlite3MallocAllow(){
  1498         -  assert( sqlite3_mallocDisallowed>0 );
  1499         -  sqlite3_mallocDisallowed--;
  1500         -}
  1501         -#endif

Changes to tool/mksqlite3c.tcl.

    68     68   
    69     69   # These are the header files used by SQLite.  The first time any of these 
    70     70   # files are seen in a #include statement in the C code, include the complete
    71     71   # text of the file in-line.  The file only needs to be included once.
    72     72   #
    73     73   foreach hdr {
    74     74      btree.h
           75  +   btreeInt.h
    75     76      hash.h
    76     77      keywordhash.h
    77     78      opcodes.h
    78     79      os_common.h
    79     80      os.h
    80     81      os_os2.h
    81     82      pager.h
................................................................................
   148    149   #
   149    150   foreach file {
   150    151      sqlite3.h
   151    152   
   152    153      date.c
   153    154      os.c
   154    155   
          156  +   malloc.c
   155    157      printf.c
   156    158      random.c
   157    159      utf.c
   158    160      util.c
   159    161      hash.c
   160    162      opcodes.c
   161    163