ext/lsm1/lsmInt.h

   1 /*
   2 ** 2011-08-18
   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 ** Internal structure definitions for the LSM module.
  13 */
  14 #ifndef _LSM_INT_H
  15 #define _LSM_INT_H
  16
  17 #include "lsm.h"
  18 #include <assert.h>
  19 #include <string.h>
  20
  21 #include <stdarg.h>
  22 #include <stdlib.h>
  23 #include <stdio.h>
  24 #include <ctype.h>
  25
  26 #ifdef _WIN32
  27 # ifdef _MSC_VER
  28 #  define snprintf _snprintf
  29 # endif
  30 #else
  31 # include <unistd.h>
  32 #endif
  33
  34 #ifdef NDEBUG
  35 # ifdef LSM_DEBUG_EXPENSIVE
  36 #  undef LSM_DEBUG_EXPENSIVE
  37 # endif
  38 # ifdef LSM_DEBUG
  39 #  undef LSM_DEBUG
  40 # endif
  41 #else
  42 # ifndef LSM_DEBUG
  43 #  define LSM_DEBUG
  44 # endif
  45 #endif
  46
  47 /* #define LSM_DEBUG_EXPENSIVE 1 */
  48
  49 /*
  50 ** Default values for various data structure parameters. These may be
  51 ** overridden by calls to lsm_config().
  52 */
  53 #define LSM_DFLT_PAGE_SIZE          (4 * 1024)
  54 #define LSM_DFLT_BLOCK_SIZE         (1 * 1024 * 1024)
  55 #define LSM_DFLT_AUTOFLUSH          (1 * 1024 * 1024)
  56 #define LSM_DFLT_AUTOCHECKPOINT     (i64)(2 * 1024 * 1024)
  57 #define LSM_DFLT_AUTOWORK           1
  58 #define LSM_DFLT_LOG_SIZE           (128*1024)
  59 #define LSM_DFLT_AUTOMERGE          4
  60 #define LSM_DFLT_SAFETY             LSM_SAFETY_NORMAL
  61 #define LSM_DFLT_MMAP               (LSM_IS_64_BIT ? 1 : 32768)
  62 #define LSM_DFLT_MULTIPLE_PROCESSES 1
  63 #define LSM_DFLT_USE_LOG            1
  64
  65 /* Initial values for log file checksums. These are only used if the
  66 ** database file does not contain a valid checkpoint.  */
  67 #define LSM_CKSUM0_INIT 42
  68 #define LSM_CKSUM1_INIT 42
  69
  70 /* "mmap" mode is currently only used in environments with 64-bit address
  71 ** spaces. The following macro is used to test for this.  */
  72 #define LSM_IS_64_BIT (sizeof(void*)==8)
  73
  74 #define LSM_AUTOWORK_QUANT 32
  75
  76 typedef struct Database Database;
  77 typedef struct DbLog DbLog;
  78 typedef struct FileSystem FileSystem;
  79 typedef struct Freelist Freelist;
  80 typedef struct FreelistEntry FreelistEntry;
  81 typedef struct Level Level;
  82 typedef struct LogMark LogMark;
  83 typedef struct LogRegion LogRegion;
  84 typedef struct LogWriter LogWriter;
  85 typedef struct LsmString LsmString;
  86 typedef struct Mempool Mempool;
  87 typedef struct Merge Merge;
  88 typedef struct MergeInput MergeInput;
  89 typedef struct MetaPage MetaPage;
  90 typedef struct MultiCursor MultiCursor;
  91 typedef struct Page Page;
  92 typedef struct Redirect Redirect;
  93 typedef struct Segment Segment;
  94 typedef struct SegmentMerger SegmentMerger;
  95 typedef struct ShmChunk ShmChunk;
  96 typedef struct ShmHeader ShmHeader;
  97 typedef struct ShmReader ShmReader;
  98 typedef struct Snapshot Snapshot;
  99 typedef struct TransMark TransMark;
 100 typedef struct Tree Tree;
 101 typedef struct TreeCursor TreeCursor;
 102 typedef struct TreeHeader TreeHeader;
 103 typedef struct TreeMark TreeMark;
 104 typedef struct TreeRoot TreeRoot;
 105
 106 #ifndef _SQLITEINT_H_
 107 typedef unsigned char u8;
 108 typedef unsigned short int u16;
 109 typedef unsigned int u32;
 110 typedef lsm_i64 i64;
 111 typedef unsigned long long int u64;
 112 #endif
 113
 114 /* A page number is a 64-bit integer. */
 115 typedef i64 LsmPgno;
 116
 117 #ifdef LSM_DEBUG
 118 int lsmErrorBkpt(int);
 119 #else
 120 # define lsmErrorBkpt(x) (x)
 121 #endif
 122
 123 #define LSM_PROTOCOL_BKPT lsmErrorBkpt(LSM_PROTOCOL)
 124 #define LSM_IOERR_BKPT    lsmErrorBkpt(LSM_IOERR)
 125 #define LSM_NOMEM_BKPT    lsmErrorBkpt(LSM_NOMEM)
 126 #define LSM_CORRUPT_BKPT  lsmErrorBkpt(LSM_CORRUPT)
 127 #define LSM_MISUSE_BKPT   lsmErrorBkpt(LSM_MISUSE)
 128
 129 #define unused_parameter(x) (void)(x)
 130 #define array_size(x) (sizeof(x)/sizeof(x[0]))
 131
 132
 133 /* The size of each shared-memory chunk */
 134 #define LSM_SHM_CHUNK_SIZE (32*1024)
 135
 136 /* The number of bytes reserved at the start of each shm chunk for MM. */
 137 #define LSM_SHM_CHUNK_HDR  (sizeof(ShmChunk))
 138
 139 /* The number of available read locks. */
 140 #define LSM_LOCK_NREADER   6
 141
 142 /* The number of available read-write client locks. */
 143 #define LSM_LOCK_NRWCLIENT   16
 144
 145 /* Lock definitions.
 146 */
 147 #define LSM_LOCK_DMS1         1   /* Serialize connect/disconnect ops */
 148 #define LSM_LOCK_DMS2         2   /* Read-write connections */
 149 #define LSM_LOCK_DMS3         3   /* Read-only connections */
 150 #define LSM_LOCK_WRITER       4
 151 #define LSM_LOCK_WORKER       5
 152 #define LSM_LOCK_CHECKPOINTER 6
 153 #define LSM_LOCK_ROTRANS      7
 154 #define LSM_LOCK_READER(i)    ((i) + LSM_LOCK_ROTRANS + 1)
 155 #define LSM_LOCK_RWCLIENT(i)  ((i) + LSM_LOCK_READER(LSM_LOCK_NREADER))
 156
 157 #define LSM_N_LOCK LSM_LOCK_RWCLIENT(LSM_LOCK_NRWCLIENT)
 158
 159 /*
 160 ** Meta-page size and usable size.
 161 */
 162 #define LSM_META_PAGE_SIZE 4096
 163
 164 #define LSM_META_RW_PAGE_SIZE (LSM_META_PAGE_SIZE - LSM_N_LOCK)
 165
 166 /*
 167 ** Hard limit on the number of free-list entries that may be stored in
 168 ** a checkpoint (the remainder are stored as a system record in the LSM).
 169 ** See also LSM_CONFIG_MAX_FREELIST.
 170 */
 171 #define LSM_MAX_FREELIST_ENTRIES 24
 172
 173 #define LSM_MAX_BLOCK_REDIRECTS 16
 174
 175 #define LSM_ATTEMPTS_BEFORE_PROTOCOL 10000
 176
 177
 178 /*
 179 ** Each entry stored in the LSM (or in-memory tree structure) has an
 180 ** associated mask of the following flags.
 181 */
 182 #define LSM_START_DELETE 0x01     /* Start of open-ended delete range */
 183 #define LSM_END_DELETE   0x02     /* End of open-ended delete range */
 184 #define LSM_POINT_DELETE 0x04     /* Delete this key */
 185 #define LSM_INSERT       0x08     /* Insert this key and value */
 186 #define LSM_SEPARATOR    0x10     /* True if entry is separator key only */
 187 #define LSM_SYSTEMKEY    0x20     /* True if entry is a system key (FREELIST) */
 188
 189 #define LSM_CONTIGUOUS   0x40     /* Used in lsm_tree.c */
 190
 191 /*
 192 ** A string that can grow by appending.
 193 */
 194 struct LsmString {
 195   lsm_env *pEnv;              /* Run-time environment */
 196   int n;                      /* Size of string.  -1 indicates error */
 197   int nAlloc;                 /* Space allocated for z[] */
 198   char *z;                    /* The string content */
 199 };
 200
 201 typedef struct LsmFile LsmFile;
 202 struct LsmFile {
 203   lsm_file *pFile;
 204   LsmFile *pNext;
 205 };
 206
 207 /*
 208 ** An instance of the following type is used to store an ordered list of
 209 ** u32 values.
 210 **
 211 ** Note: This is a place-holder implementation. It should be replaced by
 212 ** a version that avoids making a single large allocation when the array
 213 ** contains a large number of values. For this reason, the internals of
 214 ** this object should only manipulated by the intArrayXXX() functions in
 215 ** lsm_tree.c.
 216 */
 217 typedef struct IntArray IntArray;
 218 struct IntArray {
 219   int nAlloc;
 220   int nArray;
 221   u32 *aArray;
 222 };
 223
 224 struct Redirect {
 225   int n;                          /* Number of redirects */
 226   struct RedirectEntry {
 227     int iFrom;
 228     int iTo;
 229   } *a;
 230 };
 231
 232 /*
 233 ** An instance of this structure represents a point in the history of the
 234 ** tree structure to roll back to. Refer to comments in lsm_tree.c for
 235 ** details.
 236 */
 237 struct TreeMark {
 238   u32 iRoot;                      /* Offset of root node in shm file */
 239   u32 nHeight;                    /* Current height of tree structure */
 240   u32 iWrite;                     /* Write offset in shm file */
 241   u32 nChunk;                     /* Number of chunks in shared-memory file */
 242   u32 iFirst;                     /* First chunk in linked list */
 243   u32 iNextShmid;                 /* Next id to allocate */
 244   int iRollback;                  /* Index in lsm->rollback to revert to */
 245 };
 246
 247 /*
 248 ** An instance of this structure represents a point in the database log.
 249 */
 250 struct LogMark {
 251   i64 iOff;                       /* Offset into log (see lsm_log.c) */
 252   int nBuf;                       /* Size of in-memory buffer here */
 253   u8 aBuf[8];                     /* Bytes of content in aBuf[] */
 254   u32 cksum0;                     /* Checksum 0 at offset (iOff-nBuf) */
 255   u32 cksum1;                     /* Checksum 1 at offset (iOff-nBuf) */
 256 };
 257
 258 struct TransMark {
 259   TreeMark tree;
 260   LogMark log;
 261 };
 262
 263 /*
 264 ** A structure that defines the start and end offsets of a region in the
 265 ** log file. The size of the region in bytes is (iEnd - iStart), so if
 266 ** iEnd==iStart the region is zero bytes in size.
 267 */
 268 struct LogRegion {
 269   i64 iStart;                     /* Start of region in log file */
 270   i64 iEnd;                       /* End of region in log file */
 271 };
 272
 273 struct DbLog {
 274   u32 cksum0;                     /* Checksum 0 at offset iOff */
 275   u32 cksum1;                     /* Checksum 1 at offset iOff */
 276   i64 iSnapshotId;                /* Log space has been reclaimed to this ss */
 277   LogRegion aRegion[3];           /* Log file regions (see docs in lsm_log.c) */
 278 };
 279
 280 struct TreeRoot {
 281   u32 iRoot;
 282   u32 nHeight;
 283   u32 nByte;                      /* Total size of this tree in bytes */
 284   u32 iTransId;
 285 };
 286
 287 /*
 288 ** Tree header structure.
 289 */
 290 struct TreeHeader {
 291   u32 iUsedShmid;                 /* Id of first shm chunk used by this tree */
 292   u32 iNextShmid;                 /* Shm-id of next chunk allocated */
 293   u32 iFirst;                     /* Chunk number of smallest shm-id */
 294   u32 nChunk;                     /* Number of chunks in shared-memory file */
 295   TreeRoot root;                  /* Root and height of current tree */
 296   u32 iWrite;                     /* Write offset in shm file */
 297   TreeRoot oldroot;               /* Root and height of the previous tree */
 298   u32 iOldShmid;                  /* Last shm-id used by previous tree */
 299   u32 iUsrVersion;                /* get/set_user_version() value */
 300   i64 iOldLog;                    /* Log offset associated with old tree */
 301   u32 oldcksum0;
 302   u32 oldcksum1;
 303   DbLog log;                      /* Current layout of log file */
 304   u32 aCksum[2];                  /* Checksums 1 and 2. */
 305 };
 306
 307 /*
 308 ** Database handle structure.
 309 **
 310 ** mLock:
 311 **   A bitmask representing the locks currently held by the connection.
 312 **   An LSM database supports N distinct locks, where N is some number less
 313 **   than or equal to 32. Locks are numbered starting from 1 (see the
 314 **   definitions for LSM_LOCK_WRITER and co.).
 315 **
 316 **   The least significant 32-bits in mLock represent EXCLUSIVE locks. The
 317 **   most significant are SHARED locks. So, if a connection holds a SHARED
 318 **   lock on lock region iLock, then the following is true:
 319 **
 320 **       (mLock & ((iLock+32-1) << 1))
 321 **
 322 **   Or for an EXCLUSIVE lock:
 323 **
 324 **       (mLock & ((iLock-1) << 1))
 325 **
 326 ** pCsr:
 327 **   Points to the head of a linked list that contains all currently open
 328 **   cursors. Once this list becomes empty, the user has no outstanding
 329 **   cursors and the database handle can be successfully closed.
 330 **
 331 ** pCsrCache:
 332 **   This list contains cursor objects that have been closed using
 333 **   lsm_csr_close(). Each time a cursor is closed, it is shifted from
 334 **   the pCsr list to this list. When a new cursor is opened, this list
 335 **   is inspected to see if there exists a cursor object that can be
 336 **   reused. This is an optimization only.
 337 */
 338 struct lsm_db {
 339
 340   /* Database handle configuration */
 341   lsm_env *pEnv;                            /* runtime environment */
 342   int (*xCmp)(void *, int, void *, int);    /* Compare function */
 343
 344   /* Values configured by calls to lsm_config */
 345   int eSafety;                    /* LSM_SAFETY_OFF, NORMAL or FULL */
 346   int bAutowork;                  /* Configured by LSM_CONFIG_AUTOWORK */
 347   int nTreeLimit;                 /* Configured by LSM_CONFIG_AUTOFLUSH */
 348   int nMerge;                     /* Configured by LSM_CONFIG_AUTOMERGE */
 349   int bUseLog;                    /* Configured by LSM_CONFIG_USE_LOG */
 350   int nDfltPgsz;                  /* Configured by LSM_CONFIG_PAGE_SIZE */
 351   int nDfltBlksz;                 /* Configured by LSM_CONFIG_BLOCK_SIZE */
 352   int nMaxFreelist;               /* Configured by LSM_CONFIG_MAX_FREELIST */
 353   int iMmap;                      /* Configured by LSM_CONFIG_MMAP */
 354   i64 nAutockpt;                  /* Configured by LSM_CONFIG_AUTOCHECKPOINT */
 355   int bMultiProc;                 /* Configured by L_C_MULTIPLE_PROCESSES */
 356   int bReadonly;                  /* Configured by LSM_CONFIG_READONLY */
 357   lsm_compress compress;          /* Compression callbacks */
 358   lsm_compress_factory factory;   /* Compression callback factory */
 359
 360   /* Sub-system handles */
 361   FileSystem *pFS;                /* On-disk portion of database */
 362   Database *pDatabase;            /* Database shared data */
 363
 364   int iRwclient;                  /* Read-write client lock held (-1 == none) */
 365
 366   /* Client transaction context */
 367   Snapshot *pClient;              /* Client snapshot */
 368   int iReader;                    /* Read lock held (-1 == unlocked) */
 369   int bRoTrans;                   /* True if a read-only db trans is open */
 370   MultiCursor *pCsr;              /* List of all open cursors */
 371   LogWriter *pLogWriter;          /* Context for writing to the log file */
 372   int nTransOpen;                 /* Number of opened write transactions */
 373   int nTransAlloc;                /* Allocated size of aTrans[] array */
 374   TransMark *aTrans;              /* Array of marks for transaction rollback */
 375   IntArray rollback;              /* List of tree-nodes to roll back */
 376   int bDiscardOld;                /* True if lsmTreeDiscardOld() was called */
 377
 378   MultiCursor *pCsrCache;         /* List of all closed cursors */
 379
 380   /* Worker context */
 381   Snapshot *pWorker;              /* Worker snapshot (or NULL) */
 382   Freelist *pFreelist;            /* See sortedNewToplevel() */
 383   int bUseFreelist;               /* True to use pFreelist */
 384   int bIncrMerge;                 /* True if currently doing a merge */
 385
 386   int bInFactory;                 /* True if within factory.xFactory() */
 387
 388   /* Debugging message callback */
 389   void (*xLog)(void *, int, const char *);
 390   void *pLogCtx;
 391
 392   /* Work done notification callback */
 393   void (*xWork)(lsm_db *, void *);
 394   void *pWorkCtx;
 395
 396   u64 mLock;                      /* Mask of current locks. See lsmShmLock(). */
 397   lsm_db *pNext;                  /* Next connection to same database */
 398
 399   int nShm;                       /* Size of apShm[] array */
 400   void **apShm;                   /* Shared memory chunks */
 401   ShmHeader *pShmhdr;             /* Live shared-memory header */
 402   TreeHeader treehdr;             /* Local copy of tree-header */
 403   u32 aSnapshot[LSM_META_PAGE_SIZE / sizeof(u32)];
 404 };
 405
 406 struct Segment {
 407   LsmPgno iFirst;                  /* First page of this run */
 408   LsmPgno iLastPg;                 /* Last page of this run */
 409   LsmPgno iRoot;                   /* Root page number (if any) */
 410   LsmPgno nSize;                   /* Size of this run in pages */
 411
 412   Redirect *pRedirect;             /* Block redirects (or NULL) */
 413 };
 414
 415 /*
 416 ** iSplitTopic/pSplitKey/nSplitKey:
 417 **   If nRight>0, this buffer contains a copy of the largest key that has
 418 **   already been written to the left-hand-side of the level.
 419 */
 420 struct Level {
 421   Segment lhs;                    /* Left-hand (main) segment */
 422   int nRight;                     /* Size of apRight[] array */
 423   Segment *aRhs;                  /* Old segments being merged into this */
 424   int iSplitTopic;                /* Split key topic (if nRight>0) */
 425   void *pSplitKey;                /* Pointer to split-key (if nRight>0) */
 426   int nSplitKey;                  /* Number of bytes in split-key */
 427
 428   u16 iAge;                       /* Number of times data has been written */
 429   u16 flags;                      /* Mask of LEVEL_XXX bits */
 430   Merge *pMerge;                  /* Merge operation currently underway */
 431   Level *pNext;                   /* Next level in tree */
 432 };
 433
 434 /*
 435 ** The Level.flags field is set to a combination of the following bits.
 436 **
 437 ** LEVEL_FREELIST_ONLY:
 438 **   Set if the level consists entirely of free-list entries.
 439 **
 440 ** LEVEL_INCOMPLETE:
 441 **   This is set while a new toplevel level is being constructed. It is
 442 **   never set for any level other than a new toplevel.
 443 */
 444 #define LEVEL_FREELIST_ONLY      0x0001
 445 #define LEVEL_INCOMPLETE         0x0002
 446
 447
 448 /*
 449 ** A structure describing an ongoing merge. There is an instance of this
 450 ** structure for every Level currently undergoing a merge in the worker
 451 ** snapshot.
 452 **
 453 ** It is assumed that code that uses an instance of this structure has
 454 ** access to the associated Level struct.
 455 **
 456 ** iOutputOff:
 457 **   The byte offset to write to next within the last page of the
 458 **   output segment.
 459 */
 460 struct MergeInput {
 461   LsmPgno iPg;                    /* Page on which next input is stored */
 462   int iCell;                      /* Cell containing next input to merge */
 463 };
 464 struct Merge {
 465   int nInput;                     /* Number of input runs being merged */
 466   MergeInput *aInput;             /* Array nInput entries in size */
 467   MergeInput splitkey;            /* Location in file of current splitkey */
 468   int nSkip;                      /* Number of separators entries to skip */
 469   int iOutputOff;                 /* Write offset on output page */
 470   LsmPgno iCurrentPtr;            /* Current pointer value */
 471 };
 472
 473 /*
 474 ** The first argument to this macro is a pointer to a Segment structure.
 475 ** Returns true if the structure instance indicates that the separators
 476 ** array is valid.
 477 */
 478 #define segmentHasSeparators(pSegment) ((pSegment)->sep.iFirst>0)
 479
 480 /*
 481 ** The values that accompany the lock held by a database reader.
 482 */
 483 struct ShmReader {
 484   u32 iTreeId;
 485   i64 iLsmId;
 486 };
 487
 488 /*
 489 ** An instance of this structure is stored in the first shared-memory
 490 ** page. The shared-memory header.
 491 **
 492 ** bWriter:
 493 **   Immediately after opening a write transaction taking the WRITER lock,
 494 **   each writer client sets this flag. It is cleared right before the
 495 **   WRITER lock is relinquished. If a subsequent writer finds that this
 496 **   flag is already set when a write transaction is opened, this indicates
 497 **   that a previous writer failed mid-transaction.
 498 **
 499 ** iMetaPage:
 500 **   If the database file does not contain a valid, synced, checkpoint, this
 501 **   value is set to 0. Otherwise, it is set to the meta-page number that
 502 **   contains the most recently written checkpoint (either 1 or 2).
 503 **
 504 ** hdr1, hdr2:
 505 **   The two copies of the in-memory tree header. Two copies are required
 506 **   in case a writer fails while updating one of them.
 507 */
 508 struct ShmHeader {
 509   u32 aSnap1[LSM_META_PAGE_SIZE / 4];
 510   u32 aSnap2[LSM_META_PAGE_SIZE / 4];
 511   u32 bWriter;
 512   u32 iMetaPage;
 513   TreeHeader hdr1;
 514   TreeHeader hdr2;
 515   ShmReader aReader[LSM_LOCK_NREADER];
 516 };
 517
 518 /*
 519 ** An instance of this structure is stored at the start of each shared-memory
 520 ** chunk except the first (which is the header chunk - see above).
 521 */
 522 struct ShmChunk {
 523   u32 iShmid;
 524   u32 iNext;
 525 };
 526
 527 /*
 528 ** Maximum number of shared-memory chunks allowed in the *-shm file. Since
 529 ** each shared-memory chunk is 32KB in size, this is a theoretical limit only.
 530 */
 531 #define LSM_MAX_SHMCHUNKS  (1<<30)
 532
 533 /* Return true if shm-sequence "a" is larger than or equal to "b" */
 534 #define shm_sequence_ge(a, b) (((u32)a-(u32)b) < LSM_MAX_SHMCHUNKS)
 535
 536 #define LSM_APPLIST_SZ 4
 537
 538 /*
 539 ** An instance of the following structure stores the in-memory part of
 540 ** the current free block list. This structure is to the free block list
 541 ** as the in-memory tree is to the users database content. The contents
 542 ** of the free block list is found by merging the in-memory components
 543 ** with those stored in the LSM, just as the contents of the database is
 544 ** found by merging the in-memory tree with the user data entries in the
 545 ** LSM.
 546 **
 547 ** Each FreelistEntry structure in the array represents either an insert
 548 ** or delete operation on the free-list. For deletes, the FreelistEntry.iId
 549 ** field is set to -1. For inserts, it is set to zero or greater.
 550 **
 551 ** The array of FreelistEntry structures is always sorted in order of
 552 ** block number (ascending).
 553 **
 554 ** When the in-memory free block list is written into the LSM, each insert
 555 ** operation is written separately. The entry key is the bitwise inverse
 556 ** of the block number as a 32-bit big-endian integer. This is done so that
 557 ** the entries in the LSM are sorted in descending order of block id.
 558 ** The associated value is the snapshot id, formated as a varint.
 559 */
 560 struct Freelist {
 561   FreelistEntry *aEntry;          /* Free list entries */
 562   int nEntry;                     /* Number of valid slots in aEntry[] */
 563   int nAlloc;                     /* Allocated size of aEntry[] */
 564 };
 565 struct FreelistEntry {
 566   u32 iBlk;                       /* Block number */
 567   i64 iId;                        /* Largest snapshot id to use this block */
 568 };
 569
 570 /*
 571 ** A snapshot of a database. A snapshot contains all the information required
 572 ** to read or write a database file on disk. See the description of struct
 573 ** Database below for futher details.
 574 */
 575 struct Snapshot {
 576   Database *pDatabase;            /* Database this snapshot belongs to */
 577   u32 iCmpId;                     /* Id of compression scheme */
 578   Level *pLevel;                  /* Pointer to level 0 of snapshot (or NULL) */
 579   i64 iId;                        /* Snapshot id */
 580   i64 iLogOff;                    /* Log file offset */
 581   Redirect redirect;              /* Block redirection array */
 582
 583   /* Used by worker snapshots only */
 584   int nBlock;                        /* Number of blocks in database file */
 585   LsmPgno aiAppend[LSM_APPLIST_SZ];  /* Append point list */
 586   Freelist freelist;                 /* Free block list */
 587   u32 nWrite;                        /* Total number of pages written to disk */
 588 };
 589 #define LSM_INITIAL_SNAPSHOT_ID 11
 590
 591 /*
 592 ** Functions from file "lsm_ckpt.c".
 593 */
 594 int lsmCheckpointWrite(lsm_db *, u32 *);
 595 int lsmCheckpointLevels(lsm_db *, int, void **, int *);
 596 int lsmCheckpointLoadLevels(lsm_db *pDb, void *pVal, int nVal);
 597
 598 int lsmCheckpointRecover(lsm_db *);
 599 int lsmCheckpointDeserialize(lsm_db *, int, u32 *, Snapshot **);
 600
 601 int lsmCheckpointLoadWorker(lsm_db *pDb);
 602 int lsmCheckpointStore(lsm_db *pDb, int);
 603
 604 int lsmCheckpointLoad(lsm_db *pDb, int *);
 605 int lsmCheckpointLoadOk(lsm_db *pDb, int);
 606 int lsmCheckpointClientCacheOk(lsm_db *);
 607
 608 u32 lsmCheckpointNBlock(u32 *);
 609 i64 lsmCheckpointId(u32 *, int);
 610 u32 lsmCheckpointNWrite(u32 *, int);
 611 i64 lsmCheckpointLogOffset(u32 *);
 612 int lsmCheckpointPgsz(u32 *);
 613 int lsmCheckpointBlksz(u32 *);
 614 void lsmCheckpointLogoffset(u32 *aCkpt, DbLog *pLog);
 615 void lsmCheckpointZeroLogoffset(lsm_db *);
 616
 617 int lsmCheckpointSaveWorker(lsm_db *pDb, int);
 618 int lsmDatabaseFull(lsm_db *pDb);
 619 int lsmCheckpointSynced(lsm_db *pDb, i64 *piId, i64 *piLog, u32 *pnWrite);
 620
 621 int lsmCheckpointSize(lsm_db *db, int *pnByte);
 622
 623 int lsmInfoCompressionId(lsm_db *db, u32 *piCmpId);
 624
 625 /*
 626 ** Functions from file "lsm_tree.c".
 627 */
 628 int lsmTreeNew(lsm_env *, int (*)(void *, int, void *, int), Tree **ppTree);
 629 void lsmTreeRelease(lsm_env *, Tree *);
 630 int lsmTreeInit(lsm_db *);
 631 int lsmTreeRepair(lsm_db *);
 632
 633 void lsmTreeMakeOld(lsm_db *pDb);
 634 void lsmTreeDiscardOld(lsm_db *pDb);
 635 int lsmTreeHasOld(lsm_db *pDb);
 636
 637 int lsmTreeSize(lsm_db *);
 638 int lsmTreeEndTransaction(lsm_db *pDb, int bCommit);
 639 int lsmTreeLoadHeader(lsm_db *pDb, int *);
 640 int lsmTreeLoadHeaderOk(lsm_db *, int);
 641
 642 int lsmTreeInsert(lsm_db *pDb, void *pKey, int nKey, void *pVal, int nVal);
 643 int lsmTreeDelete(lsm_db *db, void *pKey1, int nKey1, void *pKey2, int nKey2);
 644 void lsmTreeRollback(lsm_db *pDb, TreeMark *pMark);
 645 void lsmTreeMark(lsm_db *pDb, TreeMark *pMark);
 646
 647 int lsmTreeCursorNew(lsm_db *pDb, int, TreeCursor **);
 648 void lsmTreeCursorDestroy(TreeCursor *);
 649
 650 int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes);
 651 int lsmTreeCursorNext(TreeCursor *pCsr);
 652 int lsmTreeCursorPrev(TreeCursor *pCsr);
 653 int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast);
 654 void lsmTreeCursorReset(TreeCursor *pCsr);
 655 int lsmTreeCursorKey(TreeCursor *pCsr, int *pFlags, void **ppKey, int *pnKey);
 656 int lsmTreeCursorFlags(TreeCursor *pCsr);
 657 int lsmTreeCursorValue(TreeCursor *pCsr, void **ppVal, int *pnVal);
 658 int lsmTreeCursorValid(TreeCursor *pCsr);
 659 int lsmTreeCursorSave(TreeCursor *pCsr);
 660
 661 void lsmFlagsToString(int flags, char *zFlags);
 662
 663 /*
 664 ** Functions from file "mem.c".
 665 */
 666 void *lsmMalloc(lsm_env*, size_t);
 667 void lsmFree(lsm_env*, void *);
 668 void *lsmRealloc(lsm_env*, void *, size_t);
 669 void *lsmReallocOrFree(lsm_env*, void *, size_t);
 670 void *lsmReallocOrFreeRc(lsm_env *, void *, size_t, int *);
 671
 672 void *lsmMallocZeroRc(lsm_env*, size_t, int *);
 673 void *lsmMallocRc(lsm_env*, size_t, int *);
 674
 675 void *lsmMallocZero(lsm_env *pEnv, size_t);
 676 char *lsmMallocStrdup(lsm_env *pEnv, const char *);
 677
 678 /*
 679 ** Functions from file "lsm_mutex.c".
 680 */
 681 int lsmMutexStatic(lsm_env*, int, lsm_mutex **);
 682 int lsmMutexNew(lsm_env*, lsm_mutex **);
 683 void lsmMutexDel(lsm_env*, lsm_mutex *);
 684 void lsmMutexEnter(lsm_env*, lsm_mutex *);
 685 int lsmMutexTry(lsm_env*, lsm_mutex *);
 686 void lsmMutexLeave(lsm_env*, lsm_mutex *);
 687
 688 #ifndef NDEBUG
 689 int lsmMutexHeld(lsm_env *, lsm_mutex *);
 690 int lsmMutexNotHeld(lsm_env *, lsm_mutex *);
 691 #endif
 692
 693 /**************************************************************************
 694 ** Start of functions from "lsm_file.c".
 695 */
 696 int lsmFsOpen(lsm_db *, const char *, int);
 697 int lsmFsOpenLog(lsm_db *, int *);
 698 void lsmFsCloseLog(lsm_db *);
 699 void lsmFsClose(FileSystem *);
 700
 701 int lsmFsUnmap(FileSystem *);
 702
 703 int lsmFsConfigure(lsm_db *db);
 704
 705 int lsmFsBlockSize(FileSystem *);
 706 void lsmFsSetBlockSize(FileSystem *, int);
 707 int lsmFsMoveBlock(FileSystem *pFS, Segment *pSeg, int iTo, int iFrom);
 708
 709 int lsmFsPageSize(FileSystem *);
 710 void lsmFsSetPageSize(FileSystem *, int);
 711
 712 int lsmFsFileid(lsm_db *pDb, void **ppId, int *pnId);
 713
 714 /* Creating, populating, gobbling and deleting sorted runs. */
 715 void lsmFsGobble(lsm_db *, Segment *, LsmPgno *, int);
 716 int lsmFsSortedDelete(FileSystem *, Snapshot *, int, Segment *);
 717 int lsmFsSortedFinish(FileSystem *, Segment *);
 718 int lsmFsSortedAppend(FileSystem *, Snapshot *, Level *, int, Page **);
 719 int lsmFsSortedPadding(FileSystem *, Snapshot *, Segment *);
 720
 721 /* Functions to retrieve the lsm_env pointer from a FileSystem or Page object */
 722 lsm_env *lsmFsEnv(FileSystem *);
 723 lsm_env *lsmPageEnv(Page *);
 724 FileSystem *lsmPageFS(Page *);
 725
 726 int lsmFsSectorSize(FileSystem *);
 727
 728 void lsmSortedSplitkey(lsm_db *, Level *, int *);
 729
 730 /* Reading sorted run content. */
 731 int lsmFsDbPageLast(FileSystem *pFS, Segment *pSeg, Page **ppPg);
 732 int lsmFsDbPageGet(FileSystem *, Segment *, LsmPgno, Page **);
 733 int lsmFsDbPageNext(Segment *, Page *, int eDir, Page **);
 734
 735 u8 *lsmFsPageData(Page *, int *);
 736 int lsmFsPageRelease(Page *);
 737 int lsmFsPagePersist(Page *);
 738 void lsmFsPageRef(Page *);
 739 LsmPgno lsmFsPageNumber(Page *);
 740
 741 int lsmFsNRead(FileSystem *);
 742 int lsmFsNWrite(FileSystem *);
 743
 744 int lsmFsMetaPageGet(FileSystem *, int, int, MetaPage **);
 745 int lsmFsMetaPageRelease(MetaPage *);
 746 u8 *lsmFsMetaPageData(MetaPage *, int *);
 747
 748 #ifdef LSM_DEBUG
 749 int lsmFsDbPageIsLast(Segment *pSeg, Page *pPg);
 750 int lsmFsIntegrityCheck(lsm_db *);
 751 #endif
 752
 753 LsmPgno lsmFsRedirectPage(FileSystem *, Redirect *, LsmPgno);
 754
 755 int lsmFsPageWritable(Page *);
 756
 757 /* Functions to read, write and sync the log file. */
 758 int lsmFsWriteLog(FileSystem *pFS, i64 iOff, LsmString *pStr);
 759 int lsmFsSyncLog(FileSystem *pFS);
 760 int lsmFsReadLog(FileSystem *pFS, i64 iOff, int nRead, LsmString *pStr);
 761 int lsmFsTruncateLog(FileSystem *pFS, i64 nByte);
 762 int lsmFsTruncateDb(FileSystem *pFS, i64 nByte);
 763 int lsmFsCloseAndDeleteLog(FileSystem *pFS);
 764
 765 LsmFile *lsmFsDeferClose(FileSystem *pFS);
 766
 767 /* And to sync the db file */
 768 int lsmFsSyncDb(FileSystem *, int);
 769
 770 void lsmFsFlushWaiting(FileSystem *, int *);
 771
 772 /* Used by lsm_info(ARRAY_STRUCTURE) and lsm_config(MMAP) */
 773 int lsmInfoArrayStructure(lsm_db *pDb, int bBlock, LsmPgno iFirst, char **pz);
 774 int lsmInfoArrayPages(lsm_db *pDb, LsmPgno iFirst, char **pzOut);
 775 int lsmConfigMmap(lsm_db *pDb, int *piParam);
 776
 777 int lsmEnvOpen(lsm_env *, const char *, int, lsm_file **);
 778 int lsmEnvClose(lsm_env *pEnv, lsm_file *pFile);
 779 int lsmEnvLock(lsm_env *pEnv, lsm_file *pFile, int iLock, int eLock);
 780 int lsmEnvTestLock(lsm_env *pEnv, lsm_file *pFile, int iLock, int nLock, int);
 781
 782 int lsmEnvShmMap(lsm_env *, lsm_file *, int, int, void **);
 783 void lsmEnvShmBarrier(lsm_env *);
 784 void lsmEnvShmUnmap(lsm_env *, lsm_file *, int);
 785
 786 void lsmEnvSleep(lsm_env *, int);
 787
 788 int lsmFsReadSyncedId(lsm_db *db, int, i64 *piVal);
 789
 790 int lsmFsSegmentContainsPg(FileSystem *pFS, Segment *, LsmPgno, int *);
 791
 792 void lsmFsPurgeCache(FileSystem *);
 793
 794 /*
 795 ** End of functions from "lsm_file.c".
 796 **************************************************************************/
 797
 798 /*
 799 ** Functions from file "lsm_sorted.c".
 800 */
 801 int lsmInfoPageDump(lsm_db *, LsmPgno, int, char **);
 802 void lsmSortedCleanup(lsm_db *);
 803 int lsmSortedAutoWork(lsm_db *, int nUnit);
 804
 805 int lsmSortedWalkFreelist(lsm_db *, int, int (*)(void *, int, i64), void *);
 806
 807 int lsmSaveWorker(lsm_db *, int);
 808
 809 int lsmFlushTreeToDisk(lsm_db *pDb);
 810
 811 void lsmSortedRemap(lsm_db *pDb);
 812
 813 void lsmSortedFreeLevel(lsm_env *pEnv, Level *);
 814
 815 int lsmSortedAdvanceAll(lsm_db *pDb);
 816
 817 int lsmSortedLoadMerge(lsm_db *, Level *, u32 *, int *);
 818 int lsmSortedLoadFreelist(lsm_db *pDb, void **, int *);
 819
 820 void *lsmSortedSplitKey(Level *pLevel, int *pnByte);
 821
 822 void lsmSortedSaveTreeCursors(lsm_db *);
 823
 824 int lsmMCursorNew(lsm_db *, MultiCursor **);
 825 void lsmMCursorClose(MultiCursor *, int);
 826 int lsmMCursorSeek(MultiCursor *, int, void *, int , int);
 827 int lsmMCursorFirst(MultiCursor *);
 828 int lsmMCursorPrev(MultiCursor *);
 829 int lsmMCursorLast(MultiCursor *);
 830 int lsmMCursorValid(MultiCursor *);
 831 int lsmMCursorNext(MultiCursor *);
 832 int lsmMCursorKey(MultiCursor *, void **, int *);
 833 int lsmMCursorValue(MultiCursor *, void **, int *);
 834 int lsmMCursorType(MultiCursor *, int *);
 835 lsm_db *lsmMCursorDb(MultiCursor *);
 836 void lsmMCursorFreeCache(lsm_db *);
 837
 838 int lsmSaveCursors(lsm_db *pDb);
 839 int lsmRestoreCursors(lsm_db *pDb);
 840
 841 void lsmSortedDumpStructure(lsm_db *pDb, Snapshot *, int, int, const char *);
 842 void lsmFsDumpBlocklists(lsm_db *);
 843
 844 void lsmSortedExpandBtreePage(Page *pPg, int nOrig);
 845
 846 void lsmPutU32(u8 *, u32);
 847 u32 lsmGetU32(u8 *);
 848 u64 lsmGetU64(u8 *);
 849
 850 /*
 851 ** Functions from "lsm_varint.c".
 852 */
 853 int lsmVarintPut32(u8 *, int);
 854 int lsmVarintGet32(u8 *, int *);
 855 int lsmVarintPut64(u8 *aData, i64 iVal);
 856 int lsmVarintGet64(const u8 *aData, i64 *piVal);
 857
 858 int lsmVarintLen64(i64);
 859
 860 int lsmVarintLen32(int);
 861 int lsmVarintSize(u8 c);
 862
 863 /*
 864 ** Functions from file "main.c".
 865 */
 866 void lsmLogMessage(lsm_db *, int, const char *, ...);
 867 int lsmInfoFreelist(lsm_db *pDb, char **pzOut);
 868
 869 /*
 870 ** Functions from file "lsm_log.c".
 871 */
 872 int lsmLogBegin(lsm_db *pDb);
 873 int lsmLogWrite(lsm_db *, int, void *, int, void *, int);
 874 int lsmLogCommit(lsm_db *);
 875 void lsmLogEnd(lsm_db *pDb, int bCommit);
 876 void lsmLogTell(lsm_db *, LogMark *);
 877 void lsmLogSeek(lsm_db *, LogMark *);
 878 void lsmLogClose(lsm_db *);
 879
 880 int lsmLogRecover(lsm_db *);
 881 int lsmInfoLogStructure(lsm_db *pDb, char **pzVal);
 882
 883 /* Valid values for the second argument to lsmLogWrite(). */
 884 #define LSM_WRITE        0x06
 885 #define LSM_DELETE       0x08
 886 #define LSM_DRANGE       0x0A
 887
 888 /**************************************************************************
 889 ** Functions from file "lsm_shared.c".
 890 */
 891
 892 int lsmDbDatabaseConnect(lsm_db*, const char *);
 893 void lsmDbDatabaseRelease(lsm_db *);
 894
 895 int lsmBeginReadTrans(lsm_db *);
 896 int lsmBeginWriteTrans(lsm_db *);
 897 int lsmBeginFlush(lsm_db *);
 898
 899 int lsmDetectRoTrans(lsm_db *db, int *);
 900 int lsmBeginRoTrans(lsm_db *db);
 901
 902 int lsmBeginWork(lsm_db *);
 903 void lsmFinishWork(lsm_db *, int, int *);
 904
 905 int lsmFinishRecovery(lsm_db *);
 906 void lsmFinishReadTrans(lsm_db *);
 907 int lsmFinishWriteTrans(lsm_db *, int);
 908 int lsmFinishFlush(lsm_db *, int);
 909
 910 int lsmSnapshotSetFreelist(lsm_db *, int *, int);
 911
 912 Snapshot *lsmDbSnapshotClient(lsm_db *);
 913 Snapshot *lsmDbSnapshotWorker(lsm_db *);
 914
 915 void lsmSnapshotSetCkptid(Snapshot *, i64);
 916
 917 Level *lsmDbSnapshotLevel(Snapshot *);
 918 void lsmDbSnapshotSetLevel(Snapshot *, Level *);
 919
 920 void lsmDbRecoveryComplete(lsm_db *, int);
 921
 922 int lsmBlockAllocate(lsm_db *, int, int *);
 923 int lsmBlockFree(lsm_db *, int);
 924 int lsmBlockRefree(lsm_db *, int);
 925
 926 void lsmFreelistDeltaBegin(lsm_db *);
 927 void lsmFreelistDeltaEnd(lsm_db *);
 928 int lsmFreelistDelta(lsm_db *pDb);
 929
 930 DbLog *lsmDatabaseLog(lsm_db *pDb);
 931
 932 #ifdef LSM_DEBUG
 933   int lsmHoldingClientMutex(lsm_db *pDb);
 934   int lsmShmAssertLock(lsm_db *db, int iLock, int eOp);
 935   int lsmShmAssertWorker(lsm_db *db);
 936 #endif
 937
 938 void lsmFreeSnapshot(lsm_env *, Snapshot *);
 939
 940
 941 /* Candidate values for the 3rd argument to lsmShmLock() */
 942 #define LSM_LOCK_UNLOCK 0
 943 #define LSM_LOCK_SHARED 1
 944 #define LSM_LOCK_EXCL   2
 945
 946 int lsmShmCacheChunks(lsm_db *db, int nChunk);
 947 int lsmShmLock(lsm_db *db, int iLock, int eOp, int bBlock);
 948 int lsmShmTestLock(lsm_db *db, int iLock, int nLock, int eOp);
 949 void lsmShmBarrier(lsm_db *db);
 950
 951 #ifdef LSM_DEBUG
 952 void lsmShmHasLock(lsm_db *db, int iLock, int eOp);
 953 #else
 954 # define lsmShmHasLock(x,y,z)
 955 #endif
 956
 957 int lsmReadlock(lsm_db *, i64 iLsm, u32 iShmMin, u32 iShmMax);
 958
 959 int lsmLsmInUse(lsm_db *db, i64 iLsmId, int *pbInUse);
 960 int lsmTreeInUse(lsm_db *db, u32 iLsmId, int *pbInUse);
 961 int lsmFreelistAppend(lsm_env *pEnv, Freelist *p, int iBlk, i64 iId);
 962
 963 int lsmDbMultiProc(lsm_db *);
 964 void lsmDbDeferredClose(lsm_db *, lsm_file *, LsmFile *);
 965 LsmFile *lsmDbRecycleFd(lsm_db *);
 966
 967 int lsmWalkFreelist(lsm_db *, int, int (*)(void *, int, i64), void *);
 968
 969 int lsmCheckCompressionId(lsm_db *, u32);
 970
 971
 972 /**************************************************************************
 973 ** functions in lsm_str.c
 974 */
 975 void lsmStringInit(LsmString*, lsm_env *pEnv);
 976 int lsmStringExtend(LsmString*, int);
 977 int lsmStringAppend(LsmString*, const char *, int);
 978 void lsmStringVAppendf(LsmString*, const char *zFormat, va_list, va_list);
 979 void lsmStringAppendf(LsmString*, const char *zFormat, ...);
 980 void lsmStringClear(LsmString*);
 981 char *lsmMallocPrintf(lsm_env*, const char*, ...);
 982 int lsmStringBinAppend(LsmString *pStr, const u8 *a, int n);
 983
 984 int lsmStrlen(const char *zName);
 985
 986
 987
 988 /*
 989 ** Round up a number to the next larger multiple of 8.  This is used
 990 ** to force 8-byte alignment on 64-bit architectures.
 991 */
 992 #define ROUND8(x)     (((x)+7)&~7)
 993
 994 #define LSM_MIN(x,y) ((x)>(y) ? (y) : (x))
 995 #define LSM_MAX(x,y) ((x)>(y) ? (x) : (y))
 996
 997 #endif