Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch freelist-rework Excluding Merge-Ins
This is equivalent to a diff from 90f46bd082 to 503f49b0cc
2012-10-31
| ||
19:30 | Merge the freelist-rework branch with the trunk. check-in: 58f0d07a23 user: dan tags: trunk | |
19:27 | Fix a crash in the check-blocks assert that may occur following an OOM condition. Leaf check-in: 503f49b0cc user: dan tags: freelist-rework | |
18:46 | Remove dead code. Fix a read-lock related problem causing the multi-threaded tests to fail. check-in: f512ea3c4d user: dan tags: freelist-rework | |
2012-10-29
| ||
20:04 | Rework the free block list storage so that it scales properly. Currently some test cases fail. check-in: ebca1063ac user: dan tags: freelist-rework | |
09:19 | Fix a couple of crashes and a memory leak in OOM tests. check-in: 90f46bd082 user: dan tags: trunk | |
2012-10-28
| ||
11:38 | Merge compression-hooks branch with trunk. check-in: a701b281e9 user: dan tags: trunk | |
Changes to lsm-test/lsmtest_tdb3.c.
︙ | ︙ | |||
894 895 896 897 898 899 900 | int test_lsm_lomem_open( const char *zFilename, int bClear, TestDb **ppDb ){ const char *zCfg = "page_size=256 block_size=65536 write_buffer=16384 " | | | | 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 | int test_lsm_lomem_open( const char *zFilename, int bClear, TestDb **ppDb ){ const char *zCfg = "page_size=256 block_size=65536 write_buffer=16384 " "max_freelist=2 autocheckpoint=32768 " "mmap=0 " ; return testLsmOpen(zCfg, zFilename, bClear, ppDb); } int test_lsm_zip_open( const char *zFilename, int bClear, TestDb **ppDb ){ const char *zCfg = "page_size=256 block_size=65536 write_buffer=16384 " "max_freelist=2 autocheckpoint=32768 compression=1" "mmap=0 " ; return testLsmOpen(zCfg, zFilename, bClear, ppDb); } lsm_db *tdb_lsm(TestDb *pDb){ if( pDb->pMethods->xClose==test_lsm_close ){ |
︙ | ︙ |
Changes to src/lsmInt.h.
︙ | ︙ | |||
58 59 60 61 62 63 64 | /* "mmap" mode is currently only used in environments with 64-bit address ** spaces. The following macro is used to test for this. */ #define LSM_IS_64_BIT (sizeof(void*)==8) #define LSM_AUTOWORK_QUANT 32 | < < < < < < < < > > | 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | /* "mmap" mode is currently only used in environments with 64-bit address ** spaces. The following macro is used to test for this. */ #define LSM_IS_64_BIT (sizeof(void*)==8) #define LSM_AUTOWORK_QUANT 32 typedef struct Database Database; typedef struct DbLog DbLog; typedef struct FileSystem FileSystem; typedef struct Freelist Freelist; typedef struct FreelistEntry FreelistEntry; typedef struct Level Level; typedef struct LogMark LogMark; typedef struct LogRegion LogRegion; typedef struct LogWriter LogWriter; typedef struct LsmString LsmString; typedef struct Mempool Mempool; typedef struct Merge Merge; |
︙ | ︙ | |||
318 319 320 321 322 323 324 325 326 327 328 329 330 331 | int nTransOpen; /* Number of opened write transactions */ int nTransAlloc; /* Allocated size of aTrans[] array */ TransMark *aTrans; /* Array of marks for transaction rollback */ IntArray rollback; /* List of tree-nodes to roll back */ /* Worker context */ Snapshot *pWorker; /* Worker snapshot (or NULL) */ /* Debugging message callback */ void (*xLog)(void *, int, const char *); void *pLogCtx; /* Work done notification callback */ void (*xWork)(lsm_db *, void *); | > > | 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 | int nTransOpen; /* Number of opened write transactions */ int nTransAlloc; /* Allocated size of aTrans[] array */ TransMark *aTrans; /* Array of marks for transaction rollback */ IntArray rollback; /* List of tree-nodes to roll back */ /* Worker context */ Snapshot *pWorker; /* Worker snapshot (or NULL) */ Freelist *pFreelist; /* See sortedNewToplevel() */ int bUseFreelist; /* True to use pFreelist */ /* Debugging message callback */ void (*xLog)(void *, int, const char *); void *pLogCtx; /* Work done notification callback */ void (*xWork)(lsm_db *, void *); |
︙ | ︙ | |||
446 447 448 449 450 451 452 | }; /* Return true if shm-sequence "a" is larger than or equal to "b" */ #define shm_sequence_ge(a, b) (((u32)a-(u32)b) < (1<<30)) #define LSM_APPLIST_SZ 4 | < < < | | > > > > > > > > > > > | > > > > > | | 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 | }; /* Return true if shm-sequence "a" is larger than or equal to "b" */ #define shm_sequence_ge(a, b) (((u32)a-(u32)b) < (1<<30)) #define LSM_APPLIST_SZ 4 /* ** An instance of the following structure stores the in-memory part of ** the current free block list. This structure is to the free block list ** as the in-memory tree is to the users database content. The contents ** of the free block list is found by merging the in-memory components ** with those stored in the LSM, just as the contents of the database is ** found by merging the in-memory tree with the user data entries in the ** LSM. ** ** Each FreelistEntry structure in the array represents either an insert ** or delete operation on the free-list. For deletes, the FreelistEntry.iId ** field is set to -1. For inserts, it is set to zero or greater. ** ** The array of FreelistEntry structures is always sorted in order of ** block number (ascending). ** ** When the in-memory free block list is written into the LSM, each insert ** operation is written separately. The entry key is the bitwise inverse ** of the block number as a 32-bit big-endian integer. This is done so that ** the entries in the LSM are sorted in descending order of block id. ** The associated value is the snapshot id, formated as a varint. */ struct Freelist { FreelistEntry *aEntry; /* Free list entries */ int nEntry; /* Number of valid slots in aEntry[] */ int nAlloc; /* Allocated size of aEntry[] */ }; struct FreelistEntry { |
︙ | ︙ | |||
480 481 482 483 484 485 486 | i64 iId; /* Snapshot id */ i64 iLogOff; /* Log file offset */ /* Used by worker snapshots only */ int nBlock; /* Number of blocks in database file */ Pgno aiAppend[LSM_APPLIST_SZ]; /* Append point list */ Freelist freelist; /* Free block list */ | < < < < < | | 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 | i64 iId; /* Snapshot id */ i64 iLogOff; /* Log file offset */ /* Used by worker snapshots only */ int nBlock; /* Number of blocks in database file */ Pgno aiAppend[LSM_APPLIST_SZ]; /* Append point list */ Freelist freelist; /* Free block list */ u32 nWrite; /* Total number of pages written to disk */ }; #define LSM_INITIAL_SNAPSHOT_ID 11 /* ** Functions from file "lsm_ckpt.c". */ int lsmCheckpointWrite(lsm_db *, u32 *); int lsmCheckpointLevels(lsm_db *, int, void **, int *); int lsmCheckpointLoadLevels(lsm_db *pDb, void *pVal, int nVal); int lsmCheckpointRecover(lsm_db *); int lsmCheckpointDeserialize(lsm_db *, int, u32 *, Snapshot **); int lsmCheckpointLoadWorker(lsm_db *pDb); int lsmCheckpointStore(lsm_db *pDb, int); int lsmCheckpointLoad(lsm_db *pDb, int *); int lsmCheckpointLoadOk(lsm_db *pDb, int); int lsmCheckpointClientCacheOk(lsm_db *); i64 lsmCheckpointId(u32 *, int); u32 lsmCheckpointNWrite(u32 *, int); i64 lsmCheckpointLogOffset(u32 *); int lsmCheckpointPgsz(u32 *); int lsmCheckpointBlksz(u32 *); void lsmCheckpointLogoffset(u32 *aCkpt, DbLog *pLog); void lsmCheckpointZeroLogoffset(lsm_db *); int lsmCheckpointSaveWorker(lsm_db *pDb, int); int lsmDatabaseFull(lsm_db *pDb); int lsmCheckpointSynced(lsm_db *pDb, i64 *piId, i64 *piLog, u32 *pnWrite); /* ** Functions from file "lsm_tree.c". */ |
︙ | ︙ | |||
688 689 690 691 692 693 694 695 696 697 698 699 700 701 | /* ** Functions from file "lsm_sorted.c". */ int lsmInfoPageDump(lsm_db *, Pgno, int, char **); void lsmSortedCleanup(lsm_db *); int lsmSortedAutoWork(lsm_db *, int nUnit); int lsmFlushTreeToDisk(lsm_db *pDb); void lsmSortedRemap(lsm_db *pDb); void lsmSortedFreeLevel(lsm_env *pEnv, Level *); int lsmSortedAdvanceAll(lsm_db *pDb); | > > | 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 | /* ** Functions from file "lsm_sorted.c". */ int lsmInfoPageDump(lsm_db *, Pgno, int, char **); void lsmSortedCleanup(lsm_db *); int lsmSortedAutoWork(lsm_db *, int nUnit); int lsmSortedWalkFreelist(lsm_db *, int (*)(void *, int, i64), void *); int lsmFlushTreeToDisk(lsm_db *pDb); void lsmSortedRemap(lsm_db *pDb); void lsmSortedFreeLevel(lsm_env *pEnv, Level *); int lsmSortedAdvanceAll(lsm_db *pDb); |
︙ | ︙ | |||
769 770 771 772 773 774 775 | void lsmDbDatabaseRelease(lsm_db *); int lsmBeginReadTrans(lsm_db *); int lsmBeginWriteTrans(lsm_db *); int lsmBeginFlush(lsm_db *); int lsmBeginWork(lsm_db *); | | | 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 | void lsmDbDatabaseRelease(lsm_db *); int lsmBeginReadTrans(lsm_db *); int lsmBeginWriteTrans(lsm_db *); int lsmBeginFlush(lsm_db *); int lsmBeginWork(lsm_db *); void lsmFinishWork(lsm_db *, int, int *); int lsmFinishRecovery(lsm_db *); void lsmFinishReadTrans(lsm_db *); int lsmFinishWriteTrans(lsm_db *, int); int lsmFinishFlush(lsm_db *, int); int lsmSnapshotSetFreelist(lsm_db *, int *, int); |
︙ | ︙ |
Changes to src/lsm_ckpt.c.
︙ | ︙ | |||
163 164 165 166 167 168 169 | + (((x)&0x00FF0000)>>8) + (((x)&0xFF000000)>>24) \ ) static const int one = 1; #define LSM_LITTLE_ENDIAN (*(u8 *)(&one)) /* Sizes, in integers, of various parts of the checkpoint. */ | | < | | | | | | 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 | + (((x)&0x00FF0000)>>8) + (((x)&0xFF000000)>>24) \ ) static const int one = 1; #define LSM_LITTLE_ENDIAN (*(u8 *)(&one)) /* Sizes, in integers, of various parts of the checkpoint. */ #define CKPT_HDR_SIZE 8 #define CKPT_LOGPTR_SIZE 4 #define CKPT_APPENDLIST_SIZE (LSM_APPLIST_SZ * 2) /* A #define to describe each integer in the checkpoint header. */ #define CKPT_HDR_ID_MSW 0 #define CKPT_HDR_ID_LSW 1 #define CKPT_HDR_NCKPT 2 #define CKPT_HDR_NBLOCK 3 #define CKPT_HDR_BLKSZ 4 #define CKPT_HDR_NLEVEL 5 #define CKPT_HDR_PGSZ 6 #define CKPT_HDR_NWRITE 7 #define CKPT_HDR_LO_MSW 8 #define CKPT_HDR_LO_LSW 9 #define CKPT_HDR_LO_CKSUM1 10 #define CKPT_HDR_LO_CKSUM2 11 typedef struct CkptBuffer CkptBuffer; /* ** Dynamic buffer used to accumulate data for a checkpoint. */ struct CkptBuffer { |
︙ | ︙ | |||
379 380 381 382 383 384 385 | for(i=0; i<LSM_APPLIST_SZ; i++){ ckptAppend64(p, piOut, aiAppend[i], pRc); } }; static int ckptExportSnapshot( lsm_db *pDb, /* Connection handle */ | < < < < < < < < < < | 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 | for(i=0; i<LSM_APPLIST_SZ; i++){ ckptAppend64(p, piOut, aiAppend[i], pRc); } }; static int ckptExportSnapshot( lsm_db *pDb, /* Connection handle */ int bLog, /* True to update log-offset fields */ i64 iId, /* Checkpoint id */ int bCksum, /* If true, include checksums */ void **ppCkpt, /* OUT: Buffer containing checkpoint */ int *pnCkpt /* OUT: Size of checkpoint in bytes */ ){ int rc = LSM_OK; /* Return Code */ FileSystem *pFS = pDb->pFS; /* File system object */ Snapshot *pSnap = pDb->pWorker; /* Worker snapshot */ int nLevel = 0; /* Number of levels in checkpoint */ int iLevel; /* Used to count out nLevel levels */ int iOut = 0; /* Current offset in aCkpt[] */ Level *pLevel; /* Level iterator */ int i; /* Iterator used while serializing freelist */ CkptBuffer ckpt; /* Initialize the output buffer */ memset(&ckpt, 0, sizeof(CkptBuffer)); ckpt.pEnv = pDb->pEnv; iOut = CKPT_HDR_SIZE; /* Write the log offset into the checkpoint. */ |
︙ | ︙ | |||
428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 | for(pLevel=lsmDbSnapshotLevel(pSnap); iLevel<nLevel; pLevel=pLevel->pNext){ ckptExportLevel(pLevel, &ckpt, &iOut, &rc); iLevel++; } /* Write the freelist */ if( rc==LSM_OK ){ ckptSetValue(&ckpt, iOut++, nFree, &rc); for(i=0; i<nFree; i++){ FreelistEntry *p = &pSnap->freelist.aEntry[i]; ckptSetValue(&ckpt, iOut++, p->iBlk, &rc); ckptSetValue(&ckpt, iOut++, (p->iId >> 32) & 0xFFFFFFFF, &rc); ckptSetValue(&ckpt, iOut++, p->iId & 0xFFFFFFFF, &rc); } } /* Write the checkpoint header */ assert( iId>=0 ); ckptSetValue(&ckpt, CKPT_HDR_ID_MSW, (u32)(iId>>32), &rc); ckptSetValue(&ckpt, CKPT_HDR_ID_LSW, (u32)(iId&0xFFFFFFFF), &rc); ckptSetValue(&ckpt, CKPT_HDR_NCKPT, iOut+2, &rc); ckptSetValue(&ckpt, CKPT_HDR_NBLOCK, pSnap->nBlock, &rc); ckptSetValue(&ckpt, CKPT_HDR_BLKSZ, lsmFsBlockSize(pFS), &rc); ckptSetValue(&ckpt, CKPT_HDR_NLEVEL, nLevel, &rc); ckptSetValue(&ckpt, CKPT_HDR_PGSZ, lsmFsPageSize(pFS), &rc); | > < | | 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 | for(pLevel=lsmDbSnapshotLevel(pSnap); iLevel<nLevel; pLevel=pLevel->pNext){ ckptExportLevel(pLevel, &ckpt, &iOut, &rc); iLevel++; } /* Write the freelist */ if( rc==LSM_OK ){ int nFree = pSnap->freelist.nEntry; ckptSetValue(&ckpt, iOut++, nFree, &rc); for(i=0; i<nFree; i++){ FreelistEntry *p = &pSnap->freelist.aEntry[i]; ckptSetValue(&ckpt, iOut++, p->iBlk, &rc); ckptSetValue(&ckpt, iOut++, (p->iId >> 32) & 0xFFFFFFFF, &rc); ckptSetValue(&ckpt, iOut++, p->iId & 0xFFFFFFFF, &rc); } } /* Write the checkpoint header */ assert( iId>=0 ); ckptSetValue(&ckpt, CKPT_HDR_ID_MSW, (u32)(iId>>32), &rc); ckptSetValue(&ckpt, CKPT_HDR_ID_LSW, (u32)(iId&0xFFFFFFFF), &rc); ckptSetValue(&ckpt, CKPT_HDR_NCKPT, iOut+2, &rc); ckptSetValue(&ckpt, CKPT_HDR_NBLOCK, pSnap->nBlock, &rc); ckptSetValue(&ckpt, CKPT_HDR_BLKSZ, lsmFsBlockSize(pFS), &rc); ckptSetValue(&ckpt, CKPT_HDR_NLEVEL, nLevel, &rc); ckptSetValue(&ckpt, CKPT_HDR_PGSZ, lsmFsPageSize(pFS), &rc); ckptSetValue(&ckpt, CKPT_HDR_NWRITE, pSnap->nWrite, &rc); if( bCksum ){ ckptAddChecksum(&ckpt, iOut, &rc); }else{ ckptSetValue(&ckpt, iOut, 0, &rc); ckptSetValue(&ckpt, iOut+1, 0, &rc); } iOut += 2; assert( iOut<=1024 ); #ifdef LSM_LOG_FREELIST lsmLogMessage(pDb, rc, "ckptExportSnapshot(): id=%lld freelist: %d", iId, pSnap->freelist.nEntry ); #endif *ppCkpt = (void *)ckpt.aCkpt; if( pnCkpt ) *pnCkpt = sizeof(u32)*iOut; return rc; } |
︙ | ︙ | |||
661 662 663 664 665 666 667 | *paVal = (void *)ckpt.aCkpt; *pnVal = iOut * sizeof(u32); }else{ *pnVal = 0; *paVal = 0; } | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 650 651 652 653 654 655 656 657 658 659 660 661 662 663 | *paVal = (void *)ckpt.aCkpt; *pnVal = iOut * sizeof(u32); }else{ *pnVal = 0; *paVal = 0; } return rc; } /* ** Read the checkpoint id from meta-page pPg. */ static i64 ckptLoadId(MetaPage *pPg){ |
︙ | ︙ | |||
1078 1079 1080 1081 1082 1083 1084 | for(i=0; i<LSM_APPLIST_SZ; i++){ u32 *a = &aCkpt[CKPT_HDR_SIZE + CKPT_LOGPTR_SIZE + i*2]; pNew->aiAppend[i] = ckptRead64(a); } /* Copy the free-list */ if( bInclFreelist ){ | < | 922 923 924 925 926 927 928 929 930 931 932 933 934 935 | for(i=0; i<LSM_APPLIST_SZ; i++){ u32 *a = &aCkpt[CKPT_HDR_SIZE + CKPT_LOGPTR_SIZE + i*2]; pNew->aiAppend[i] = ckptRead64(a); } /* Copy the free-list */ if( bInclFreelist ){ nFree = aCkpt[iIn++]; if( nFree ){ pNew->freelist.aEntry = (FreelistEntry *)lsmMallocZeroRc( pDb->pEnv, sizeof(FreelistEntry)*nFree, &rc ); if( rc==LSM_OK ){ int i; |
︙ | ︙ | |||
1143 1144 1145 1146 1147 1148 1149 | ** ** This function updates the shared-memory worker and client snapshots with ** the new snapshot produced by the work performed by pDb. ** ** If successful, LSM_OK is returned. Otherwise, if an error occurs, an LSM ** error code is returned. */ | | < < < < < < < | > | 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 | ** ** This function updates the shared-memory worker and client snapshots with ** the new snapshot produced by the work performed by pDb. ** ** If successful, LSM_OK is returned. Otherwise, if an error occurs, an LSM ** error code is returned. */ int lsmCheckpointSaveWorker(lsm_db *pDb, int bFlush){ Snapshot *pSnap = pDb->pWorker; ShmHeader *pShm = pDb->pShmhdr; void *p = 0; int n = 0; int rc; rc = ckptExportSnapshot(pDb, bFlush, pSnap->iId+1, 1, &p, &n); if( rc!=LSM_OK ) return rc; assert( ckptChecksumOk((u32 *)p) ); assert( n<=LSM_META_PAGE_SIZE ); memcpy(pShm->aSnap2, p, n); lsmShmBarrier(pDb); memcpy(pShm->aSnap1, p, n); lsmFree(pDb->pEnv, p); assert( lsmFsIntegrityCheck(pDb) ); return LSM_OK; } /* ** This function is used to determine the snapshot-id of the most recently ** checkpointed snapshot. Variable ShmHeader.iMetaPage indicates which of ** the two meta-pages said snapshot resides on (if any). |
︙ | ︙ |
Changes to src/lsm_file.c.
︙ | ︙ | |||
185 186 187 188 189 190 191 | lsm_file *fdDb; /* Database file */ lsm_file *fdLog; /* Log file */ int szSector; /* Database file sector size */ /* If this is a compressed database, a pointer to the compression methods. ** For an uncompressed database, a NULL pointer. */ lsm_compress *pCompress; | | > | 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 | lsm_file *fdDb; /* Database file */ lsm_file *fdLog; /* Log file */ int szSector; /* Database file sector size */ /* If this is a compressed database, a pointer to the compression methods. ** For an uncompressed database, a NULL pointer. */ lsm_compress *pCompress; u8 *aIBuffer; /* Buffer to compress to */ u8 *aOBuffer; /* Buffer to uncompress from */ int nBuffer; /* Allocated size of aBuffer[] in bytes */ /* mmap() mode things */ int bUseMmap; /* True to use mmap() to access db file */ void *pMap; /* Current mapping of database file */ i64 nMap; /* Bytes mapped at pMap */ Page *pFree; |
︙ | ︙ | |||
554 555 556 557 558 559 560 | pPg = pNext; } if( pFS->fdDb ) lsmEnvClose(pFS->pEnv, pFS->fdDb ); if( pFS->fdLog ) lsmEnvClose(pFS->pEnv, pFS->fdLog ); lsmFree(pEnv, pFS->pLsmFile); lsmFree(pEnv, pFS->apHash); | | > | 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 | pPg = pNext; } if( pFS->fdDb ) lsmEnvClose(pFS->pEnv, pFS->fdDb ); if( pFS->fdLog ) lsmEnvClose(pFS->pEnv, pFS->fdLog ); lsmFree(pEnv, pFS->pLsmFile); lsmFree(pEnv, pFS->apHash); lsmFree(pEnv, pFS->aIBuffer); lsmFree(pEnv, pFS->aOBuffer); lsmFree(pEnv, pFS); } } void lsmFsDeferClose(FileSystem *pFS, LsmFile **pp){ LsmFile *p = pFS->pLsmFile; assert( p->pNext==0 ); |
︙ | ︙ | |||
1011 1012 1013 1014 1015 1016 1017 | } rc = fsBlockNext(pFS, fsPageToBlock(pFS, iOff), &iBlk); *piRes = fsFirstPageOnBlock(pFS, iBlk) + iAdd - (iEob - iOff + 1); return rc; } | | > > > > > | > > > > > | | > | 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 | } rc = fsBlockNext(pFS, fsPageToBlock(pFS, iOff), &iBlk); *piRes = fsFirstPageOnBlock(pFS, iBlk) + iAdd - (iEob - iOff + 1); return rc; } static int fsAllocateBuffer(FileSystem *pFS, int bWrite){ u8 **pp; /* Pointer to either aIBuffer or aOBuffer */ assert( pFS->pCompress ); /* If neither buffer has been allocated, figure out how large they ** should be. Store this value in FileSystem.nBuffer. */ if( pFS->nBuffer==0 ){ assert( pFS->aIBuffer==0 && pFS->aOBuffer==0 ); pFS->nBuffer = pFS->pCompress->xBound(pFS->pCompress->pCtx, pFS->nPagesize); if( pFS->nBuffer<(pFS->szSector+6) ){ pFS->nBuffer = pFS->szSector+6; } } pp = (bWrite ? &pFS->aOBuffer : &pFS->aIBuffer); if( *pp==0 ){ *pp = lsmMalloc(pFS->pEnv, LSM_MAX(pFS->nBuffer, pFS->nPagesize)); if( *pp==0 ) return LSM_NOMEM_BKPT; } return LSM_OK; } /* ** This function is only called in compressed database mode. It reads and ** uncompresses the compressed data for page pPg from the database and ** populates the pPg->aData[] buffer and pPg->nCompress field. |
︙ | ︙ | |||
1043 1044 1045 1046 1047 1048 1049 | lsm_compress *p = pFS->pCompress; i64 iOff = pPg->iPg; u8 aSz[3]; int rc; assert( p && pPg->nCompress==0 ); | | | 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 | lsm_compress *p = pFS->pCompress; i64 iOff = pPg->iPg; u8 aSz[3]; int rc; assert( p && pPg->nCompress==0 ); if( fsAllocateBuffer(pFS, 0) ) return LSM_NOMEM; rc = fsReadData(pFS, iOff, aSz, sizeof(aSz)); if( rc==LSM_OK ){ int bFree; if( aSz[0] & 0x80 ){ pPg->nCompress = (int)getRecordSize(aSz, &bFree); |
︙ | ︙ | |||
1067 1068 1069 1070 1071 1072 1073 | } }else{ rc = fsAddOffset(pFS, iOff, 3, &iOff); if( rc==LSM_OK ){ if( pPg->nCompress>pFS->nBuffer ){ rc = LSM_CORRUPT_BKPT; }else{ | | | | | 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 | } }else{ rc = fsAddOffset(pFS, iOff, 3, &iOff); if( rc==LSM_OK ){ if( pPg->nCompress>pFS->nBuffer ){ rc = LSM_CORRUPT_BKPT; }else{ rc = fsReadData(pFS, iOff, pFS->aIBuffer, pPg->nCompress); } if( rc==LSM_OK ){ int n = pFS->nPagesize; rc = p->xUncompress(p->pCtx, (char *)pPg->aData, &n, (const char *)pFS->aIBuffer, pPg->nCompress ); if( rc==LSM_OK && n!=pPg->nData ){ rc = LSM_CORRUPT_BKPT; } } } } } |
︙ | ︙ | |||
1532 1533 1534 1535 1536 1537 1538 | } /* If this is the first page allocated, or if the page allocated is the ** last in the block, allocate a new block here. */ if( iApp==0 || fsIsLast(pFS, iApp) ){ int iNew; /* New block number */ | | > | 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 | } /* If this is the first page allocated, or if the page allocated is the ** last in the block, allocate a new block here. */ if( iApp==0 || fsIsLast(pFS, iApp) ){ int iNew; /* New block number */ rc = lsmBlockAllocate(pFS->pDb, &iNew); if( rc!=LSM_OK ) return rc; if( iApp==0 ){ iApp = fsFirstPageOnBlock(pFS, iNew); }else{ iNext = fsFirstPageOnBlock(pFS, iNew); } } |
︙ | ︙ | |||
1842 1843 1844 1845 1846 1847 1848 | ** ** If buffer pFS->aBuffer[] has not been allocated then this function ** allocates it. If this fails, LSM_NOMEM is returned. Otherwise, LSM_OK. */ static int fsCompressIntoBuffer(FileSystem *pFS, Page *pPg){ lsm_compress *p = pFS->pCompress; | | | | 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 | ** ** If buffer pFS->aBuffer[] has not been allocated then this function ** allocates it. If this fails, LSM_NOMEM is returned. Otherwise, LSM_OK. */ static int fsCompressIntoBuffer(FileSystem *pFS, Page *pPg){ lsm_compress *p = pFS->pCompress; if( fsAllocateBuffer(pFS, 1) ) return LSM_NOMEM; assert( pPg->nData==pFS->nPagesize ); pPg->nCompress = pFS->nBuffer; return p->xCompress(p->pCtx, (char *)pFS->aOBuffer, &pPg->nCompress, (const char *)pPg->aData, pPg->nData ); } /* ** If the page passed as an argument is dirty, update the database file ** (or mapping of the database file) with its current contents and mark |
︙ | ︙ | |||
1878 1879 1880 1881 1882 1883 1884 | rc = fsCompressIntoBuffer(pFS, pPg); /* Serialize the compressed size into buffer aSz[] */ putRecordSize(aSz, pPg->nCompress, 0); /* Write the serialized page record into the database file. */ pPg->iPg = fsAppendData(pFS, pPg->pSeg, aSz, sizeof(aSz), &rc); | | | 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 | rc = fsCompressIntoBuffer(pFS, pPg); /* Serialize the compressed size into buffer aSz[] */ putRecordSize(aSz, pPg->nCompress, 0); /* Write the serialized page record into the database file. */ pPg->iPg = fsAppendData(pFS, pPg->pSeg, aSz, sizeof(aSz), &rc); fsAppendData(pFS, pPg->pSeg, pFS->aOBuffer, pPg->nCompress, &rc); fsAppendData(pFS, pPg->pSeg, aSz, sizeof(aSz), &rc); /* Now that it has a page number, insert the page into the hash table */ iHash = fsHashKey(pFS->nHash, pPg->iPg); pPg->pHashNext = pFS->apHash[iHash]; pFS->apHash[iHash] = pPg; |
︙ | ︙ | |||
1948 1949 1950 1951 1952 1953 1954 | assert( nPad>=0 ); if( nPad>=6 ){ pSeg->nSize += nPad; nPad -= 6; putRecordSize(aSz, nPad, 1); fsAppendData(pFS, pSeg, aSz, sizeof(aSz), &rc); | | | | 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 | assert( nPad>=0 ); if( nPad>=6 ){ pSeg->nSize += nPad; nPad -= 6; putRecordSize(aSz, nPad, 1); fsAppendData(pFS, pSeg, aSz, sizeof(aSz), &rc); memset(pFS->aOBuffer, 0, nPad); fsAppendData(pFS, pSeg, pFS->aOBuffer, nPad, &rc); fsAppendData(pFS, pSeg, aSz, sizeof(aSz), &rc); }else if( nPad>0 ){ u8 aBuf[5] = {0,0,0,0,0}; aBuf[0] = (u8)nPad; aBuf[nPad-1] = (u8)nPad; fsAppendData(pFS, pSeg, aBuf, nPad, &rc); } |
︙ | ︙ | |||
2120 2121 2122 2123 2124 2125 2126 | lsmStringAppendf(&str, " %d", pArray->iLastPg); *pzOut = str.z; } if( bUnlock ){ int rcwork = LSM_BUSY; | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > | | > > > > | > > > | > > > > > > > > > > | | < | > > > > | > > > | > > | > > | | | | > > > > > > > > > > > > > > > > | | | < < < < < | < < < < | < < | < < > | < | | > | 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 | lsmStringAppendf(&str, " %d", pArray->iLastPg); *pzOut = str.z; } if( bUnlock ){ int rcwork = LSM_BUSY; lsmFinishWork(pDb, 0, &rcwork); } return rc; } /* ** The following macros are used by the integrity-check code. Associated with ** each block in the database is an 8-bit bit mask (the entry in the aUsed[] ** array). As the integrity-check meanders through the database, it sets the ** following bits to indicate how each block is used. ** ** INTEGRITY_CHECK_FIRST_PG: ** First page of block is in use by sorted run. ** ** INTEGRITY_CHECK_LAST_PG: ** Last page of block is in use by sorted run. ** ** INTEGRITY_CHECK_USED: ** At least one page of the block is in use by a sorted run. ** ** INTEGRITY_CHECK_FREE: ** The free block list contains an entry corresponding to this block. */ #define INTEGRITY_CHECK_FIRST_PG 0x01 #define INTEGRITY_CHECK_LAST_PG 0x02 #define INTEGRITY_CHECK_USED 0x04 #define INTEGRITY_CHECK_FREE 0x08 /* ** Helper function for lsmFsIntegrityCheck() */ static void checkBlocks( FileSystem *pFS, Segment *pSeg, int bExtra, /* If true, count the "next" block if any */ int nUsed, u8 *aUsed ){ if( pSeg ){ if( pSeg && pSeg->nSize>0 ){ int rc; Pgno iLast = pSeg->iLastPg; int iBlk; int iLastBlk; int bLastIsLastOnBlock; iBlk = fsPageToBlock(pFS, pSeg->iFirst); iLastBlk = fsPageToBlock(pFS, pSeg->iLastPg); bLastIsLastOnBlock = (fsLastPageOnBlock(pFS, iLastBlk)==iLast); assert( iBlk>0 ); /* If the first page of this run is also the first page of its first ** block, set the flag to indicate that the first page of iBlk is ** in use. */ if( fsFirstPageOnBlock(pFS, iBlk)==pSeg->iFirst ){ assert( (aUsed[iBlk-1] & INTEGRITY_CHECK_FIRST_PG)==0 ); aUsed[iBlk-1] |= INTEGRITY_CHECK_FIRST_PG; } do { /* iBlk is a part of this sorted run. */ aUsed[iBlk-1] |= INTEGRITY_CHECK_USED; /* Unless the sorted run finishes before the last page on this block, ** the last page of this block is also in use. */ if( iBlk!=iLastBlk || bLastIsLastOnBlock ){ assert( (aUsed[iBlk-1] & INTEGRITY_CHECK_LAST_PG)==0 ); aUsed[iBlk-1] |= INTEGRITY_CHECK_LAST_PG; } /* Special case. The sorted run being scanned is the output run of ** a level currently undergoing an incremental merge. The sorted ** run ends on the last page of iBlk, but the next block has already ** been allocated. So mark it as in use as well. */ if( iBlk==iLastBlk && bLastIsLastOnBlock && bExtra ){ int iExtra = 0; rc = fsBlockNext(pFS, iBlk, &iExtra); assert( rc==LSM_OK ); assert( aUsed[iExtra-1]==0 ); aUsed[iExtra-1] |= INTEGRITY_CHECK_USED; aUsed[iExtra-1] |= INTEGRITY_CHECK_FIRST_PG; aUsed[iExtra-1] |= INTEGRITY_CHECK_LAST_PG; } /* Move on to the next block in the sorted run. Or set iBlk to zero ** in order to break out of the loop if this was the last block in ** the run. */ if( iBlk==iLastBlk ){ iBlk = 0; }else{ rc = fsBlockNext(pFS, iBlk, &iBlk); assert( rc==LSM_OK ); } }while( iBlk ); } } } typedef struct CheckFreelistCtx CheckFreelistCtx; typedef struct CheckFreelistCtx { u8 *aUsed; int nBlock; }; static int checkFreelistCb(void *pCtx, int iBlk, i64 iSnapshot){ CheckFreelistCtx *p = (CheckFreelistCtx *)pCtx; assert( iBlk>=1 ); assert( iBlk<=p->nBlock ); assert( p->aUsed[iBlk-1]==0 ); p->aUsed[iBlk-1] = INTEGRITY_CHECK_FREE; return 0; } /* ** This function checks that all blocks in the database file are accounted ** for. For each block, exactly one of the following must be true: ** ** + the block is part of a sorted run, or ** + the block is on the free-block list ** ** This function also checks that there are no references to blocks with ** out-of-range block numbers. ** ** If no errors are found, non-zero is returned. If an error is found, an ** assert() fails. */ int lsmFsIntegrityCheck(lsm_db *pDb){ CheckFreelistCtx ctx; FileSystem *pFS = pDb->pFS; int i; int j; int rc; Freelist freelist = {0, 0, 0}; u8 *aUsed; Level *pLevel; Snapshot *pWorker = pDb->pWorker; int nBlock = pWorker->nBlock; aUsed = lsmMallocZero(pDb->pEnv, nBlock); if( aUsed==0 ){ /* Malloc has failed. Since this function is only called within debug ** builds, this probably means the user is running an OOM injection test. ** Regardless, it will not be possible to run the integrity-check at this ** time, so assume the database is Ok and return non-zero. */ return 1; } for(pLevel=pWorker->pLevel; pLevel; pLevel=pLevel->pNext){ int i; checkBlocks(pFS, &pLevel->lhs, (pLevel->nRight!=0), nBlock, aUsed); for(i=0; i<pLevel->nRight; i++){ checkBlocks(pFS, &pLevel->aRhs[i], 0, nBlock, aUsed); } } /* Mark all blocks in the free-list as used */ ctx.aUsed = aUsed; ctx.nBlock = nBlock; rc = lsmWalkFreelist(pDb, checkFreelistCb, (void *)&ctx); if( rc==LSM_OK ){ for(i=0; i<nBlock; i++) assert( aUsed[i]!=0 ); } lsmFree(pDb->pEnv, aUsed); lsmFree(pDb->pEnv, freelist.aEntry); return 1; } |
︙ | ︙ |
Changes to src/lsm_main.c.
︙ | ︙ | |||
368 369 370 371 372 373 374 | *pp = pDb->pWorker; return rc; } static void infoFreeWorker(lsm_db *pDb, int bUnlock){ if( bUnlock ){ int rcdummy = LSM_BUSY; | | | 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 | *pp = pDb->pWorker; return rc; } static void infoFreeWorker(lsm_db *pDb, int bUnlock){ if( bUnlock ){ int rcdummy = LSM_BUSY; lsmFinishWork(pDb, 0, &rcdummy); } } int lsmStructList( lsm_db *pDb, /* Database handle */ char **pzOut /* OUT: Nul-terminated string (tcl list) */ ){ |
︙ | ︙ | |||
419 420 421 422 423 424 425 | int rc; /* Obtain the worker snapshot */ rc = infoGetWorker(pDb, &pWorker, &bUnlock); if( rc!=LSM_OK ) return rc; lsmStringInit(&s, pDb->pEnv); | | | 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 | int rc; /* Obtain the worker snapshot */ rc = infoGetWorker(pDb, &pWorker, &bUnlock); if( rc!=LSM_OK ) return rc; lsmStringInit(&s, pDb->pEnv); lsmStringAppendf(&s, "%d", pWorker->freelist.nEntry); for(i=0; i<pWorker->freelist.nEntry; i++){ FreelistEntry *p = &pWorker->freelist.aEntry[i]; lsmStringAppendf(&s, " {%d %d}", p->iBlk, (int)p->iId); } rc = s.n>=0 ? LSM_OK : LSM_NOMEM; /* Release the snapshot and return */ |
︙ | ︙ |
Changes to src/lsm_shared.c.
︙ | ︙ | |||
80 81 82 83 84 85 86 | } } #else # define assertNotInFreelist(x,y) #endif /* | | | > > > | < | < > > | < < | | | | < | | < > | | | < | > | | > < | | < < < < < < < < | | 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 | } } #else # define assertNotInFreelist(x,y) #endif /* ** Append an entry to the free-list. If (iId==-1), this is a delete. */ int freelistAppend(lsm_db *db, int iBlk, i64 iId){ lsm_env *pEnv = db->pEnv; Freelist *p; int i; assert( iId==-1 || iId>=0 ); p = db->bUseFreelist ? db->pFreelist : &db->pWorker->freelist; /* Extend the space allocated for the freelist, if required */ assert( p->nAlloc>=p->nEntry ); if( p->nAlloc==p->nEntry ){ int nNew; int nByte; FreelistEntry *aNew; nNew = (p->nAlloc==0 ? 4 : p->nAlloc*2); nByte = sizeof(FreelistEntry) * nNew; aNew = (FreelistEntry *)lsmRealloc(pEnv, p->aEntry, nByte); if( !aNew ) return LSM_NOMEM_BKPT; p->nAlloc = nNew; p->aEntry = aNew; } for(i=0; i<p->nEntry; i++){ assert( i==0 || p->aEntry[i].iBlk > p->aEntry[i-1].iBlk ); if( p->aEntry[i].iBlk>=iBlk ) break; } if( i<p->nEntry && p->aEntry[i].iBlk==iBlk ){ /* Clobber an existing entry */ p->aEntry[i].iId = iId; }else{ /* Insert a new entry into the list */ int nByte = sizeof(FreelistEntry)*(p->nEntry-i); memmove(&p->aEntry[i+1], &p->aEntry[i], nByte); p->aEntry[i].iBlk = iBlk; p->aEntry[i].iId = iId; p->nEntry++; } return LSM_OK; } /* ** This function frees all resources held by the Database structure passed ** as the only argument. */ static void freeDatabase(lsm_env *pEnv, Database *p){ assert( holdingGlobalMutex(pEnv) ); if( p ){ /* Free the mutexes */ lsmMutexDel(pEnv, p->pClientMutex); |
︙ | ︙ | |||
424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 | return pSnapshot->pLevel; } void lsmDbSnapshotSetLevel(Snapshot *pSnap, Level *pLevel){ pSnap->pLevel = pLevel; } /* ** Allocate a new database file block to write data to, either by extending ** the database file or by recycling a free-list entry. The worker snapshot ** must be held in order to call this function. ** ** If successful, *piBlk is set to the block number allocated and LSM_OK is ** returned. Otherwise, *piBlk is zeroed and an lsm error code returned. */ int lsmBlockAllocate(lsm_db *pDb, int *piBlk){ Snapshot *p = pDb->pWorker; | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < > | | < < < < < < < | | | < | | < < > > | | > > | > > > > > | < < | < | | | < < < < | < < < > | | | | | > > | < | | | | | < | | | 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 | return pSnapshot->pLevel; } void lsmDbSnapshotSetLevel(Snapshot *pSnap, Level *pLevel){ pSnap->pLevel = pLevel; } /* TODO: Shuffle things around to get rid of this */ static int firstSnapshotInUse(lsm_db *, i64 *); /* ** Context object used by the lsmWalkFreelist() utility. */ typedef struct WalkFreelistCtx WalkFreelistCtx; struct WalkFreelistCtx { lsm_db *pDb; Freelist *pFreelist; int iFree; int (*xUsr)(void *, int, i64); /* User callback function */ void *pUsrctx; /* User callback context */ }; /* ** Callback used by lsmWalkFreelist(). */ static int walkFreelistCb(void *pCtx, int iBlk, i64 iSnapshot){ WalkFreelistCtx *p = (WalkFreelistCtx *)pCtx; Freelist *pFree = p->pFreelist; if( pFree ){ while( (p->iFree < pFree->nEntry) ){ FreelistEntry *pEntry = &pFree->aEntry[p->iFree]; if( pEntry->iBlk>iBlk ){ break; }else{ p->iFree++; if( pEntry->iId>=0 && p->xUsr(p->pUsrctx, pEntry->iBlk, pEntry->iId) ){ return 1; } if( pEntry->iBlk==iBlk ) return 0; } } } return p->xUsr(p->pUsrctx, iBlk, iSnapshot); } /* ** The database handle passed as the first argument must be the worker ** connection. This function iterates through the contents of the current ** free block list, invoking the supplied callback once for each list ** element. ** ** The difference between this function and lsmSortedWalkFreelist() is ** that lsmSortedWalkFreelist() only considers those free-list elements ** stored within the LSM. This function also merges in any in-memory ** elements. */ int lsmWalkFreelist( lsm_db *pDb, /* Database handle (must be worker) */ int (*x)(void *, int, i64), /* Callback function */ void *pCtx /* First argument to pass to callback */ ){ int rc; int iCtx; WalkFreelistCtx ctx[2]; ctx[0].pDb = pDb; ctx[0].pFreelist = &pDb->pWorker->freelist; ctx[0].iFree = 0; ctx[0].xUsr = walkFreelistCb; ctx[0].pUsrctx = (void *)&ctx[1]; ctx[1].pDb = pDb; ctx[1].pFreelist = pDb->pFreelist; ctx[1].iFree = 0; ctx[1].xUsr = x; ctx[1].pUsrctx = pCtx; rc = lsmSortedWalkFreelist(pDb, walkFreelistCb, (void *)&ctx[0]); for(iCtx=0; iCtx<2; iCtx++){ int i; WalkFreelistCtx *p = &ctx[iCtx]; for(i=p->iFree; p->pFreelist && rc==LSM_OK && i<p->pFreelist->nEntry; i++){ FreelistEntry *pEntry = &p->pFreelist->aEntry[i]; if( pEntry->iId>=0 && p->xUsr(p->pUsrctx, pEntry->iBlk, pEntry->iId) ){ return LSM_OK; } } } return rc; } typedef struct FindFreeblockCtx FindFreeblockCtx; struct FindFreeblockCtx { i64 iInUse; int iRet; }; static int findFreeblockCb(void *pCtx, int iBlk, i64 iSnapshot){ FindFreeblockCtx *p = (FindFreeblockCtx *)pCtx; if( iSnapshot<p->iInUse ){ p->iRet = iBlk; return 1; } return 0; } static int findFreeblock(lsm_db *pDb, i64 iInUse, int *piRet){ int rc; /* Return code */ FindFreeblockCtx ctx; /* Context object */ ctx.iInUse = iInUse; ctx.iRet = 0; rc = lsmWalkFreelist(pDb, findFreeblockCb, (void *)&ctx); *piRet = ctx.iRet; return rc; } /* ** Allocate a new database file block to write data to, either by extending ** the database file or by recycling a free-list entry. The worker snapshot ** must be held in order to call this function. ** ** If successful, *piBlk is set to the block number allocated and LSM_OK is ** returned. Otherwise, *piBlk is zeroed and an lsm error code returned. */ int lsmBlockAllocate(lsm_db *pDb, int *piBlk){ Snapshot *p = pDb->pWorker; int iRet = 0; /* Block number of allocated block */ int rc = LSM_OK; i64 iInUse = 0; /* Snapshot id still in use */ assert( p ); /* Set iInUse to the smallest snapshot id that is either: ** ** * Currently in use by a database client, ** * May be used by a database client in the future, or ** * Is the most recently checkpointed snapshot (i.e. the one that will ** be used following recovery if a failure occurs at this point). */ rc = lsmCheckpointSynced(pDb, &iInUse, 0, 0); if( rc==LSM_OK && iInUse==0 ) iInUse = p->iId; if( rc==LSM_OK && pDb->pClient ) iInUse = LSM_MIN(iInUse, pDb->pClient->iId); if( rc==LSM_OK ) rc = firstSnapshotInUse(pDb, &iInUse); /* Query the free block list for a suitable block */ if( rc==LSM_OK ) rc = findFreeblock(pDb, iInUse, &iRet); /* If a block was found in the free block list, use it and remove it from ** the list. Otherwise, if no suitable block was found, allocate one from ** the end of the file. */ if( rc==LSM_OK ){ if( iRet>0 ){ #ifdef LSM_LOG_FREELIST lsmLogMessage(pDb, 0, "reusing block %d (snapshot-in-use=%lld)", iRet, iInUse); #endif rc = freelistAppend(pDb, iRet, -1); }else{ iRet = ++(p->nBlock); #ifdef LSM_LOG_FREELIST lsmLogMessage(pDb, 0, "extending file to %d blocks", iRet); #endif } } assert( iRet>0 || rc!=LSM_OK ); *piBlk = iRet; return rc; } /* ** Free a database block. The worker snapshot must be held in order to call ** this function. ** ** If successful, LSM_OK is returned. Otherwise, an lsm error code (e.g. ** LSM_NOMEM). */ int lsmBlockFree(lsm_db *pDb, int iBlk){ Snapshot *p = pDb->pWorker; assert( lsmShmAssertWorker(pDb) ); #ifdef LSM_LOG_FREELIST lsmLogMessage(pDb, LSM_OK, "lsmBlockFree(): Free block %d", iBlk); #endif return freelistAppend(pDb, iBlk, p->iId); } /* ** Refree a database block. The worker snapshot must be held in order to call ** this function. ** ** Refreeing is required when a block is allocated using lsmBlockAllocate() ** but then not used. This function is used to push the block back onto ** the freelist. Refreeing a block is different from freeing is, as a refreed ** block may be reused immediately. Whereas a freed block can not be reused ** until (at least) after the next checkpoint. */ int lsmBlockRefree(lsm_db *pDb, int iBlk){ int rc = LSM_OK; /* Return code */ Snapshot *p = pDb->pWorker; #ifdef LSM_LOG_FREELIST lsmLogMessage(pDb, LSM_OK, "lsmBlockRefree(): Refree block %d", iBlk); #endif rc = freelistAppend(pDb, iBlk, 0); return rc; } /* ** If required, copy a database checkpoint from shared memory into the ** database itself. ** |
︙ | ︙ | |||
630 631 632 633 634 635 636 | /* ** Argument bFlush is true if the contents of the in-memory tree has just ** been flushed to disk. The significance of this is that once the snapshot ** created to hold the updated state of the database is synced to disk, log ** file space can be recycled. */ | | < | | 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 | /* ** Argument bFlush is true if the contents of the in-memory tree has just ** been flushed to disk. The significance of this is that once the snapshot ** created to hold the updated state of the database is synced to disk, log ** file space can be recycled. */ void lsmFinishWork(lsm_db *pDb, int bFlush, int *pRc){ assert( *pRc!=0 || pDb->pWorker ); if( pDb->pWorker ){ /* If no error has occurred, serialize the worker snapshot and write ** it to shared memory. */ if( *pRc==LSM_OK ){ *pRc = lsmCheckpointSaveWorker(pDb, bFlush); } lsmFreeSnapshot(pDb->pEnv, pDb->pWorker); pDb->pWorker = 0; } lsmShmLock(pDb, LSM_LOCK_WORKER, LSM_LOCK_UNLOCK, 0); } |
︙ | ︙ | |||
718 719 720 721 722 723 724 | } if( rc==LSM_BUSY ){ rc = LSM_OK; } } #if 0 if( rc==LSM_OK && pDb->pClient ){ | > | < | 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 | } if( rc==LSM_BUSY ){ rc = LSM_OK; } } #if 0 if( rc==LSM_OK && pDb->pClient ){ fprintf(stderr, "reading %p: snapshot:%d used-shmid:%d trans-id:%d iOldShmid=%d\n", (void *)pDb, (int)pDb->pClient->iId, (int)pDb->treehdr.iUsedShmid, (int)pDb->treehdr.root.iTransId, (int)pDb->treehdr.iOldShmid ); } #endif } if( rc!=LSM_OK ){ lsmReleaseReadlock(pDb); } |
︙ | ︙ | |||
754 755 756 757 758 759 760 761 762 763 764 765 766 767 | #if 0 if( pClient ){ lsmFreeSnapshot(pDb->pEnv, pDb->pClient); pDb->pClient = 0; } #endif if( pDb->iReader>=0 ) lsmReleaseReadlock(pDb); } /* ** Open a write transaction. */ int lsmBeginWriteTrans(lsm_db *pDb){ | > > > > > > > > | 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 | #if 0 if( pClient ){ lsmFreeSnapshot(pDb->pEnv, pDb->pClient); pDb->pClient = 0; } #endif #if 0 if( pDb->pClient && pDb->iReader>=0 ){ fprintf(stderr, "finished reading %p: snapshot:%d\n", (void *)pDb, (int)pDb->pClient->iId ); } #endif if( pDb->iReader>=0 ) lsmReleaseReadlock(pDb); } /* ** Open a write transaction. */ int lsmBeginWriteTrans(lsm_db *pDb){ |
︙ | ︙ | |||
958 959 960 961 962 963 964 965 966 967 968 969 970 971 | if( rc==LSM_BUSY ){ *pbInUse = 1; return LSM_OK; } *pbInUse = 0; return rc; } int lsmTreeInUse(lsm_db *db, u32 iShmid, int *pbInUse){ if( db->treehdr.iUsedShmid==iShmid ){ *pbInUse = 1; return LSM_OK; } return isInUse(db, 0, iShmid, pbInUse); | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 | if( rc==LSM_BUSY ){ *pbInUse = 1; return LSM_OK; } *pbInUse = 0; return rc; } /* ** This function is called by worker connections to determine the smallest ** snapshot id that is currently in use by a database client. The worker ** connection uses this result to determine whether or not it is safe to ** recycle a database block. */ static int firstSnapshotInUse( lsm_db *db, /* Database handle */ i64 *piInUse /* IN/OUT: Smallest snapshot id in use */ ){ ShmHeader *pShm = db->pShmhdr; i64 iInUse = *piInUse; int i; assert( iInUse>0 ); for(i=0; i<LSM_LOCK_NREADER; i++){ ShmReader *p = &pShm->aReader[i]; if( p->iLsmId ){ i64 iThis = p->iLsmId; if( iThis!=0 && iInUse>iThis ){ int rc = lsmShmLock(db, LSM_LOCK_READER(i), LSM_LOCK_EXCL, 0); if( rc==LSM_OK ){ p->iLsmId = 0; lsmShmLock(db, LSM_LOCK_READER(i), LSM_LOCK_UNLOCK, 0); }else if( rc==LSM_BUSY ){ iInUse = iThis; }else{ /* Some error other than LSM_BUSY. Return the error code to ** the caller in this case. */ return rc; } } } } *piInUse = iInUse; return LSM_OK; } int lsmTreeInUse(lsm_db *db, u32 iShmid, int *pbInUse){ if( db->treehdr.iUsedShmid==iShmid ){ *pbInUse = 1; return LSM_OK; } return isInUse(db, 0, iShmid, pbInUse); |
︙ | ︙ |
Changes to src/lsm_sorted.c.
︙ | ︙ | |||
192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 | int eType; /* Cache of current key type */ Blob key; /* Cache of current key (or NULL) */ Blob val; /* Cache of current value */ /* All the component cursors: */ TreeCursor *apTreeCsr[2]; /* Up to two tree cursors */ SegmentPtr *aPtr; /* Array of segment pointers */ int nPtr; /* Size of array aPtr[] */ BtreeCursor *pBtCsr; /* b-tree cursor (db writes only) */ /* Comparison results */ int nTree; /* Size of aTree[] array */ int *aTree; /* Array of comparison results */ /* Used by cursors flushing the in-memory tree only */ | > < > > > > | | | | < < < < < < < | | | < | 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 | int eType; /* Cache of current key type */ Blob key; /* Cache of current key (or NULL) */ Blob val; /* Cache of current value */ /* All the component cursors: */ TreeCursor *apTreeCsr[2]; /* Up to two tree cursors */ int iFree; /* Next element of free-list (-ve for eof) */ SegmentPtr *aPtr; /* Array of segment pointers */ int nPtr; /* Size of array aPtr[] */ BtreeCursor *pBtCsr; /* b-tree cursor (db writes only) */ /* Comparison results */ int nTree; /* Size of aTree[] array */ int *aTree; /* Array of comparison results */ /* Used by cursors flushing the in-memory tree only */ void *pSystemVal; /* Pointer to buffer to free */ /* Used by worker cursors only */ Pgno *pPrevMergePtr; }; /* ** The following constants are used to assign integers to each component ** cursor of a multi-cursor. */ #define CURSOR_DATA_TREE0 0 /* Current tree cursor (apTreeCsr[0]) */ #define CURSOR_DATA_TREE1 1 /* The "old" tree, if any (apTreeCsr[1]) */ #define CURSOR_DATA_SYSTEM 2 /* Free-list entries (new-toplevel only) */ #define CURSOR_DATA_SEGMENT 3 /* ** CURSOR_IGNORE_DELETE ** If set, this cursor will not visit SORTED_DELETE keys. ** ** CURSOR_FLUSH_FREELIST ** This cursor is being used to create a new toplevel. It should also ** iterate through the contents of the in-memory free block list. ** ** CURSOR_IGNORE_SYSTEM ** If set, this cursor ignores system keys. ** ** CURSOR_NEXT_OK ** Set if it is Ok to call lsm_csr_next(). ** ** CURSOR_PREV_OK ** Set if it is Ok to call lsm_csr_prev(). ** ** CURSOR_READ_SEPARATORS ** Set if this cursor should visit the separator keys in segment ** aPtr[nPtr-1]. ** ** CURSOR_SEEK_EQ ** Cursor has undergone a successful lsm_csr_seek(LSM_SEEK_EQ) operation. ** The key and value are stored in MultiCursor.key and MultiCursor.val ** respectively. */ #define CURSOR_IGNORE_DELETE 0x00000001 #define CURSOR_FLUSH_FREELIST 0x00000002 #define CURSOR_IGNORE_SYSTEM 0x00000010 #define CURSOR_NEXT_OK 0x00000020 #define CURSOR_PREV_OK 0x00000040 #define CURSOR_READ_SEPARATORS 0x00000080 #define CURSOR_SEEK_EQ 0x00000100 typedef struct MergeWorker MergeWorker; |
︙ | ︙ | |||
1907 1908 1909 1910 1911 1912 1913 | lsmTreeCursorKey(pTreeCsr, &eType, &pKey, &nKey); lsmTreeCursorValue(pTreeCsr, &pVal, &nVal); } break; } | | > | > > > > > > | | > | > > | > > | 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 | lsmTreeCursorKey(pTreeCsr, &eType, &pKey, &nKey); lsmTreeCursorValue(pTreeCsr, &pVal, &nVal); } break; } case CURSOR_DATA_SYSTEM: { Snapshot *pWorker = pCsr->pDb->pWorker; if( (pCsr->flags & CURSOR_FLUSH_FREELIST) && pWorker && pWorker->freelist.nEntry > pCsr->iFree ){ int iEntry = pWorker->freelist.nEntry - pCsr->iFree - 1; FreelistEntry *pEntry = &pWorker->freelist.aEntry[iEntry]; u32 i = ~((u32)(pEntry->iBlk)); lsmPutU32(pCsr->pSystemVal, i); pKey = pCsr->pSystemVal; nKey = 4; if( pEntry->iId>=0 ){ eType = LSM_SYSTEMKEY | LSM_INSERT; }else{ eType = LSM_SYSTEMKEY | LSM_POINT_DELETE; } } break; } default: { int iPtr = iKey - CURSOR_DATA_SEGMENT; assert( iPtr>=0 ); if( iPtr==pCsr->nPtr ){ if( pCsr->pBtCsr ){ pKey = pCsr->pBtCsr->pKey; |
︙ | ︙ | |||
2250 2251 2252 2253 2254 2255 2256 | } /* ** If the free-block list is not empty, then have this cursor visit a key ** with (a) the system bit set, and (b) the key "FREELIST" and (c) a value ** blob containing the serialized free-block list. */ | | < | | > > | 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 | } /* ** If the free-block list is not empty, then have this cursor visit a key ** with (a) the system bit set, and (b) the key "FREELIST" and (c) a value ** blob containing the serialized free-block list. */ static int multiCursorVisitFreelist(MultiCursor *pCsr){ int rc = LSM_OK; pCsr->flags |= CURSOR_FLUSH_FREELIST; pCsr->pSystemVal = lsmMallocRc(pCsr->pDb->pEnv, 4 + 8, &rc); return rc; } /* ** Allocate and return a new database cursor. */ int lsmMCursorNew( lsm_db *pDb, /* Database handle */ |
︙ | ︙ | |||
2302 2303 2304 2305 2306 2307 2308 | }else{ *ppVal = 0; *pnVal = 0; } break; } | | | | | | > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 2393 2394 2395 2396 2397 2398 2399 | }else{ *ppVal = 0; *pnVal = 0; } break; } case CURSOR_DATA_SYSTEM: { Snapshot *pWorker = pCsr->pDb->pWorker; if( pWorker && pWorker->freelist.nEntry > pCsr->iFree ){ int iEntry = pWorker->freelist.nEntry - pCsr->iFree - 1; u8 *aVal = &((u8 *)(pCsr->pSystemVal))[4]; lsmPutU64(aVal, pWorker->freelist.aEntry[iEntry].iId); *ppVal = aVal; *pnVal = 8; } break; } default: { int iPtr = iVal-CURSOR_DATA_SEGMENT; if( iPtr<pCsr->nPtr ){ SegmentPtr *pPtr = &pCsr->aPtr[iPtr]; if( pPtr->pPg ){ *ppVal = pPtr->pVal; *pnVal = pPtr->nVal; } } } } assert( rc==LSM_OK || (*ppVal==0 && *pnVal==0) ); return rc; } /* ** This function is called by worker connections to walk the part of the ** free-list stored within the LSM data structure. */ int lsmSortedWalkFreelist( lsm_db *pDb, /* Database handle */ int (*x)(void *, int, i64), /* Callback function */ void *pCtx /* First argument to pass to callback */ ){ MultiCursor *pCsr; /* Cursor used to read db */ int rc = LSM_OK; /* Return Code */ Snapshot *pSnap = 0; assert( pDb->pWorker ); rc = lsmCheckpointDeserialize(pDb, 0, pDb->pShmhdr->aSnap1, &pSnap); if( rc!=LSM_OK ) return rc; pCsr = multiCursorNew(pDb, &rc); if( pCsr ){ rc = multiCursorAddAll(pCsr, pSnap); pCsr->flags |= CURSOR_IGNORE_DELETE; } if( rc==LSM_OK ){ rc = lsmMCursorLast(pCsr); while( rc==LSM_OK && lsmMCursorValid(pCsr) && rtIsSystem(pCsr->eType) ){ void *pKey; int nKey; void *pVal; int nVal; rc = lsmMCursorKey(pCsr, &pKey, &nKey); if( rc==LSM_OK ) rc = lsmMCursorValue(pCsr, &pVal, &nVal); if( rc==LSM_OK && (nKey!=4 || nVal!=8) ) rc = LSM_CORRUPT_BKPT; if( rc==LSM_OK ){ int iBlk; i64 iSnap; iBlk = (int)(~(lsmGetU32((u8 *)pKey))); iSnap = (i64)lsmGetU64((u8 *)pVal); if( x(pCtx, iBlk, iSnap) ) break; rc = lsmMCursorPrev(pCsr); } } } lsmMCursorClose(pCsr); lsmFreeSnapshot(pDb->pEnv, pSnap); return rc; } int lsmSortedLoadFreelist( lsm_db *pDb, /* Database handle (must be worker) */ void **ppVal, /* OUT: Blob containing LSM free-list */ int *pnVal /* OUT: Size of *ppVal blob in bytes */ |
︙ | ︙ | |||
2446 2447 2448 2449 2450 2451 2452 | if( pCsr->apTreeCsr[0] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[0], bLast); } if( rc==LSM_OK && pCsr->apTreeCsr[1] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[1], bLast); } | < < | < | 2508 2509 2510 2511 2512 2513 2514 2515 2516 2517 2518 2519 2520 2521 2522 | if( pCsr->apTreeCsr[0] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[0], bLast); } if( rc==LSM_OK && pCsr->apTreeCsr[1] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[1], bLast); } pCsr->iFree = 0; for(i=0; rc==LSM_OK && i<pCsr->nPtr; i++){ SegmentPtr *pPtr = &pCsr->aPtr[i]; Level *pLvl = pPtr->pLevel; rc = segmentPtrEnd(pCsr, pPtr, bLast); if( rc==LSM_OK && bLast==0 && pLvl->nRight && pPtr->pSeg==&pLvl->lhs ){ |
︙ | ︙ | |||
2622 2623 2624 2625 2626 2627 2628 | int rc = LSM_OK; /* Return code */ int iPtr = 0; /* Used to iterate through pCsr->aPtr[] */ Pgno iPgno = 0; /* FC pointer value */ if( eESeek==LSM_SEEK_LEFAST ) eESeek = LSM_SEEK_LE; assert( eESeek==LSM_SEEK_EQ || eESeek==LSM_SEEK_LE || eESeek==LSM_SEEK_GE ); | | < | 2681 2682 2683 2684 2685 2686 2687 2688 2689 2690 2691 2692 2693 2694 2695 | int rc = LSM_OK; /* Return code */ int iPtr = 0; /* Used to iterate through pCsr->aPtr[] */ Pgno iPgno = 0; /* FC pointer value */ if( eESeek==LSM_SEEK_LEFAST ) eESeek = LSM_SEEK_LE; assert( eESeek==LSM_SEEK_EQ || eESeek==LSM_SEEK_LE || eESeek==LSM_SEEK_GE ); assert( (pCsr->flags & CURSOR_FLUSH_FREELIST)==0 ); assert( pCsr->nPtr==0 || pCsr->aPtr[0].pLevel ); pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK | CURSOR_SEEK_EQ); rc = treeCursorSeek(pCsr, pCsr->apTreeCsr[0], pKey, nKey, eESeek, &bStop); if( rc==LSM_OK && bStop==0 ){ rc = treeCursorSeek(pCsr, pCsr->apTreeCsr[1], pKey, nKey, eESeek, &bStop); } |
︙ | ︙ | |||
2757 2758 2759 2760 2761 2762 2763 | TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; if( bReverse ){ rc = lsmTreeCursorPrev(pTreeCsr); }else{ rc = lsmTreeCursorNext(pTreeCsr); } }else if( iKey==CURSOR_DATA_SYSTEM ){ | | < | | 2815 2816 2817 2818 2819 2820 2821 2822 2823 2824 2825 2826 2827 2828 2829 2830 2831 | TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; if( bReverse ){ rc = lsmTreeCursorPrev(pTreeCsr); }else{ rc = lsmTreeCursorNext(pTreeCsr); } }else if( iKey==CURSOR_DATA_SYSTEM ){ assert( pCsr->flags & CURSOR_FLUSH_FREELIST ); assert( bReverse==0 ); pCsr->iFree++; }else if( iKey==(CURSOR_DATA_SEGMENT+pCsr->nPtr) ){ assert( bReverse==0 && pCsr->pBtCsr ); rc = btreeCursorNext(pCsr->pBtCsr); }else{ rc = segmentCursorAdvance(pCsr, iKey-CURSOR_DATA_SEGMENT, bReverse); } if( rc==LSM_OK ){ |
︙ | ︙ | |||
3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 | /* ** The cursor passed as the first argument is being used as the input for ** a merge operation. When this function is called, *piFlags contains the ** database entry flags for the current entry. The entry about to be written ** to the output. ** */ static void mergeRangeDeletes(MultiCursor *pCsr, int *piFlags){ int f = *piFlags; int iKey = pCsr->aTree[1]; int i; if( pCsr->flags & CURSOR_IGNORE_DELETE ){ /* The ignore-delete flag is set when the output of the merge will form ** the oldest level in the database. In this case there is no point in ** retaining any range-delete flags. */ assert( (f & LSM_POINT_DELETE)==0 ); f &= ~(LSM_START_DELETE|LSM_END_DELETE); }else{ if( iKey==0 ){ int btreeflags = lsmTreeCursorFlags(pCsr->apTreeCsr[1]); if( btreeflags & LSM_END_DELETE ){ f |= (LSM_START_DELETE|LSM_END_DELETE); } } for(i=LSM_MAX(0, iKey+1-CURSOR_DATA_SEGMENT); i<pCsr->nPtr; i++){ | > > > > | | 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 | /* ** The cursor passed as the first argument is being used as the input for ** a merge operation. When this function is called, *piFlags contains the ** database entry flags for the current entry. The entry about to be written ** to the output. ** ** Note that this function only has to work for cursors configured to ** iterate forwards (not backwards). */ static void mergeRangeDeletes(MultiCursor *pCsr, int *piFlags){ int f = *piFlags; int iKey = pCsr->aTree[1]; int i; assert( pCsr->flags & CURSOR_NEXT_OK ); if( pCsr->flags & CURSOR_IGNORE_DELETE ){ /* The ignore-delete flag is set when the output of the merge will form ** the oldest level in the database. In this case there is no point in ** retaining any range-delete flags. */ assert( (f & LSM_POINT_DELETE)==0 ); f &= ~(LSM_START_DELETE|LSM_END_DELETE); }else{ if( iKey==0 ){ int btreeflags = lsmTreeCursorFlags(pCsr->apTreeCsr[1]); if( btreeflags & LSM_END_DELETE ){ f |= (LSM_START_DELETE|LSM_END_DELETE); } } for(i=LSM_MAX(0, iKey+1-CURSOR_DATA_SEGMENT); i<pCsr->nPtr; i++){ SegmentPtr *pPtr = &pCsr->aPtr[i]; if( pPtr->pPg && (pPtr->eType & LSM_END_DELETE) ){ f |= (LSM_START_DELETE|LSM_END_DELETE); } } if( (f & LSM_START_DELETE) && (f & LSM_END_DELETE) && (f & LSM_INSERT)==0 ){ f = 0; } |
︙ | ︙ | |||
3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 | pCsr = pMW->pCsr; pSeg = &pMW->pLevel->lhs; /* Pull the next record out of the source cursor. */ lsmMCursorKey(pCsr, &pKey, &nKey); eType = pCsr->eType; /* Figure out if the output record may have a different pointer value ** than the previous. This is the case if the current key is identical to ** a key that appears in the lowest level run being merged. If so, set ** iPtr to the absolute pointer value. If not, leave iPtr set to zero, ** indicating that the output pointer value should be a copy of the pointer ** value written with the previous key. */ | > > > > > | 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 | pCsr = pMW->pCsr; pSeg = &pMW->pLevel->lhs; /* Pull the next record out of the source cursor. */ lsmMCursorKey(pCsr, &pKey, &nKey); eType = pCsr->eType; if( eType & LSM_SYSTEMKEY ){ int i; i = 1; } /* Figure out if the output record may have a different pointer value ** than the previous. This is the case if the current key is identical to ** a key that appears in the lowest level run being merged. If so, set ** iPtr to the absolute pointer value. If not, leave iPtr set to zero, ** indicating that the output pointer value should be a copy of the pointer ** value written with the previous key. */ |
︙ | ︙ | |||
3814 3815 3816 3817 3818 3819 3820 | pDb->xWork(pDb, pDb->pWorkCtx); } } static int sortedNewToplevel( lsm_db *pDb, /* Connection handle */ int eTree, /* One of the TREE_XXX constants */ | < > | > > > | > | > | 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 3924 3925 3926 | pDb->xWork(pDb, pDb->pWorkCtx); } } static int sortedNewToplevel( lsm_db *pDb, /* Connection handle */ int eTree, /* One of the TREE_XXX constants */ int *pnWrite /* OUT: Number of database pages written */ ){ int rc = LSM_OK; /* Return Code */ MultiCursor *pCsr = 0; Level *pNext = 0; /* The current top level */ Level *pNew; /* The new level itself */ Segment *pDel = 0; /* Delete separators from this segment */ int nWrite = 0; /* Number of database pages written */ Freelist freelist; assert( pDb->bUseFreelist==0 ); pDb->pFreelist = &freelist; pDb->bUseFreelist = 1; memset(&freelist, 0, sizeof(freelist)); /* Allocate the new level structure to write to. */ pNext = lsmDbSnapshotLevel(pDb->pWorker); pNew = (Level *)lsmMallocZeroRc(pDb->pEnv, sizeof(Level), &rc); if( pNew ){ pNew->pNext = pNext; lsmDbSnapshotSetLevel(pDb->pWorker, pNew); } /* Create a cursor to gather the data required by the new segment. The new ** segment contains everything in the tree and pointers to the next segment ** in the database (if any). */ pCsr = multiCursorNew(pDb, &rc); if( pCsr ){ pCsr->pDb = pDb; rc = multiCursorVisitFreelist(pCsr); if( rc==LSM_OK ){ rc = multiCursorAddTree(pCsr, pDb->pWorker, eTree); } if( rc==LSM_OK && pNext && pNext->pMerge==0 && pNext->lhs.iRoot ){ pDel = &pNext->lhs; rc = btreeCursorNew(pDb, pDel, &pCsr->pBtCsr); } if( pNext==0 ){ multiCursorIgnoreDelete(pCsr); |
︙ | ︙ | |||
3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 | mergeworker.bFlush = 1; /* Do the work to create the new merged segment on disk */ if( rc==LSM_OK ) rc = lsmMCursorFirst(pCsr); while( rc==LSM_OK && mergeWorkerDone(&mergeworker)==0 ){ rc = mergeWorkerStep(&mergeworker); } nWrite = mergeworker.nWork; mergeWorkerShutdown(&mergeworker, &rc); pNew->pMerge = 0; pNew->iAge = 0; } | > < | < < > | > | > > > > > > > > | > > > | 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962 3963 3964 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 | mergeworker.bFlush = 1; /* Do the work to create the new merged segment on disk */ if( rc==LSM_OK ) rc = lsmMCursorFirst(pCsr); while( rc==LSM_OK && mergeWorkerDone(&mergeworker)==0 ){ rc = mergeWorkerStep(&mergeworker); } assert( rc!=LSM_OK || mergeworker.nWork==0 || pNew->lhs.iFirst ); nWrite = mergeworker.nWork; mergeWorkerShutdown(&mergeworker, &rc); pNew->pMerge = 0; pNew->iAge = 0; } if( rc!=LSM_OK || pNew->lhs.iFirst==0 ){ assert( rc!=LSM_OK || pDb->pWorker->freelist.nEntry==0 ); lsmDbSnapshotSetLevel(pDb->pWorker, pNext); sortedFreeLevel(pDb->pEnv, pNew); }else{ if( pDel ) pDel->iRoot = 0; #if 0 lsmSortedDumpStructure(pDb, pDb->pWorker, 0, 0, "new-toplevel"); #endif if( freelist.nEntry ){ Freelist *p = &pDb->pWorker->freelist; lsmFree(pDb->pEnv, p->aEntry); memcpy(p, &freelist, sizeof(freelist)); freelist.aEntry = 0; }else{ pDb->pWorker->freelist.nEntry = 0; } assertBtreeOk(pDb, &pNew->lhs); sortedInvokeWorkHook(pDb); } if( pnWrite ) *pnWrite = nWrite; pDb->pWorker->nWrite += nWrite; pDb->pFreelist = 0; pDb->bUseFreelist = 0; lsmFree(pDb->pEnv, freelist.aEntry); return rc; } /* ** The nMerge levels in the LSM beginning with pLevel consist of a ** left-hand-side segment only. Replace these levels with a single new ** level consisting of a new empty segment on the left-hand-side and the |
︙ | ︙ | |||
4301 4302 4303 4304 4305 4306 4307 | /* Clean up the MergeWorker object initialized above. If no error ** has occurred, invoke the work-hook to inform the application that ** the database structure has changed. */ mergeWorkerShutdown(&mergeworker, &rc); if( rc==LSM_OK ) sortedInvokeWorkHook(pDb); #if 0 | | | 4383 4384 4385 4386 4387 4388 4389 4390 4391 4392 4393 4394 4395 4396 4397 | /* Clean up the MergeWorker object initialized above. If no error ** has occurred, invoke the work-hook to inform the application that ** the database structure has changed. */ mergeWorkerShutdown(&mergeworker, &rc); if( rc==LSM_OK ) sortedInvokeWorkHook(pDb); #if 0 lsmSortedDumpStructure(pDb, pDb->pWorker, 0, 0, "work"); #endif assertBtreeOk(pDb, &pLevel->lhs); assertRunInOrder(pDb, &pLevel->lhs); /* If bFlush is true and the database is no longer considered "full", ** break out of the loop even if nRemaining is still greater than ** zero. The caller has an in-memory tree to flush to disk. */ |
︙ | ︙ | |||
4362 4363 4364 4365 4366 4367 4368 | int bShutdown, int flags, int nPage, /* Number of pages to write to disk */ int *pnWrite, /* OUT: Pages actually written to disk */ int *pbCkpt /* OUT: True if an auto-checkpoint is req. */ ){ int rc = LSM_OK; /* Return code */ | < | < < | > > > > > < > | | > | | | < > | < < | | | < > | | > > | | > > | | < | | 4444 4445 4446 4447 4448 4449 4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 4469 4470 4471 4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 | int bShutdown, int flags, int nPage, /* Number of pages to write to disk */ int *pnWrite, /* OUT: Pages actually written to disk */ int *pbCkpt /* OUT: True if an auto-checkpoint is req. */ ){ int rc = LSM_OK; /* Return code */ int bDirty = 0; int nMax = nPage; /* Maximum pages to write to disk */ int nRem = nPage; int bCkpt = 0; /* Open the worker 'transaction'. It will be closed before this function ** returns. */ assert( pDb->pWorker==0 ); rc = lsmBeginWork(pDb); if( rc!=LSM_OK ) return rc; /* If this connection is doing auto-checkpoints, set nMax (and nRem) so ** that this call stops writing when the auto-checkpoint is due. The ** caller will do the checkpoint, then possibly call this function again. */ if( bShutdown==0 && pDb->nAutockpt ){ u32 nSync; u32 nUnsync; int nPgsz; int nMax; lsmCheckpointSynced(pDb, 0, 0, &nSync); nUnsync = lsmCheckpointNWrite(pDb->pShmhdr->aSnap1, 0); nPgsz = lsmCheckpointPgsz(pDb->pShmhdr->aSnap1); nMax = (pDb->nAutockpt/nPgsz) - (nUnsync-nSync); if( nMax<nRem ){ bCkpt = 1; nRem = LSM_MAX(nMax, 0); } } /* If there exists in-memory data ready to be flushed to disk, attempt ** to flush it now. */ if( sortedTreeHasOld(pDb, &rc) ){ /* sortedDbIsFull() returns non-zero if either (a) there are too many ** levels in total in the db, or (b) there are too many levels with the ** the same age in the db. Either way, call sortedWork() to merge ** existing segments together until this condition is cleared. */ if( sortedDbIsFull(pDb) ){ int nPg = 0; rc = sortedWork(pDb, nRem, 0, 1, &nPg); nRem -= nPg; assert( rc!=LSM_OK || nRem<=0 || !sortedDbIsFull(pDb) ); } if( rc==LSM_OK && nRem>0 ){ int nPg = 0; rc = sortedNewToplevel(pDb, TREE_OLD, &nPg); nRem -= nPg; if( rc==LSM_OK ){ if( pDb->nTransOpen>0 ){ lsmTreeDiscardOld(pDb); } rc = lsmCheckpointSaveWorker(pDb, 1); } } } /* If nPage is still greater than zero, do some merging. */ if( rc==LSM_OK && nRem>0 && bShutdown==0 ){ int nPg = 0; int bOptimize = ((flags & LSM_WORK_OPTIMIZE) ? 1 : 0); rc = sortedWork(pDb, nRem, bOptimize, 0, &nPg); nRem -= nPg; if( nPg ) bDirty = 1; } /* If the in-memory part of the free-list is too large, write a new ** top-level containing just the in-memory free-list entries to disk. */ if( rc==LSM_OK && pDb->pWorker->freelist.nEntry > pDb->nMaxFreelist ){ int nPg = 0; while( rc==LSM_OK && sortedDbIsFull(pDb) ){ rc = sortedWork(pDb, 16, 0, 1, &nPg); nRem -= nPg; } if( rc==LSM_OK ){ rc = sortedNewToplevel(pDb, TREE_NONE, &nPg); } nRem -= nPg; if( nPg ) bDirty = 1; } if( rc==LSM_OK && bDirty ){ lsmFinishWork(pDb, 0, &rc); }else{ int rcdummy = LSM_BUSY; lsmFinishWork(pDb, 0, &rcdummy); } assert( pDb->pWorker==0 ); if( rc==LSM_OK ){ if( pnWrite ) *pnWrite = (nMax - nRem); if( pbCkpt ) *pbCkpt = (bCkpt && nRem<=0); }else{ |
︙ | ︙ | |||
4561 4562 4563 4564 4565 4566 4567 | /* ** This function is only called during system shutdown. The contents of ** any in-memory trees present (old or current) are written out to disk. */ int lsmFlushTreeToDisk(lsm_db *pDb){ int rc; | < | | | 4647 4648 4649 4650 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 4666 4667 4668 4669 4670 | /* ** This function is only called during system shutdown. The contents of ** any in-memory trees present (old or current) are written out to disk. */ int lsmFlushTreeToDisk(lsm_db *pDb){ int rc; rc = lsmBeginWork(pDb); while( rc==LSM_OK && sortedDbIsFull(pDb) ){ rc = sortedWork(pDb, 256, 0, 1, 0); } if( rc==LSM_OK ){ rc = sortedNewToplevel(pDb, TREE_BOTH, 0); } lsmFinishWork(pDb, 1, &rc); return rc; } /* ** Return a string representation of the segment passed as the only argument. ** Space for the returned string is allocated using lsmMalloc(), and should ** be freed by the caller using lsmFree(). |
︙ | ︙ | |||
4844 4845 4846 4847 4848 4849 4850 4851 4852 4853 4854 4855 4856 4857 | ); infoAppendBlob(&str, bHex, aKey, nKey); if( nVal>0 && bValues ){ lsmStringAppendf(&str, "%*s", nKeyWidth - (nKey*(1+bHex)), ""); lsmStringAppendf(&str, " "); infoAppendBlob(&str, bHex, aVal, nVal); } lsmStringAppendf(&str, "\n"); } if( bData ){ lsmStringAppendf(&str, "\n-------------------" "-------------------------------------------------------------\n"); lsmStringAppendf(&str, "Page %d\n", | > > > > > > > > > | 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 | ); infoAppendBlob(&str, bHex, aKey, nKey); if( nVal>0 && bValues ){ lsmStringAppendf(&str, "%*s", nKeyWidth - (nKey*(1+bHex)), ""); lsmStringAppendf(&str, " "); infoAppendBlob(&str, bHex, aVal, nVal); } if( rtTopic(eType) ){ int iBlk = (int)~lsmGetU32(aKey); lsmStringAppendf(&str, " (block=%d", iBlk); if( nVal>0 ){ i64 iSnap = lsmGetU64(aVal); lsmStringAppendf(&str, " snapshot=%lld", iSnap); } lsmStringAppendf(&str, ")"); } lsmStringAppendf(&str, "\n"); } if( bData ){ lsmStringAppendf(&str, "\n-------------------" "-------------------------------------------------------------\n"); lsmStringAppendf(&str, "Page %d\n", |
︙ | ︙ |