Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Make it possible to flush part of the in-memory tree to disk without blocking writer clients. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
6c686c6d1a860ff29dd2bdcd1fda4d5d |
User & Date: | dan 2012-09-17 20:41:53.645 |
Context
2012-09-18
| ||
15:48 | Fix a bug preventing block recycling in multi-threaded tests. check-in: 93d9ff7c12 user: dan tags: trunk | |
2012-09-17
| ||
20:41 | Make it possible to flush part of the in-memory tree to disk without blocking writer clients. check-in: 6c686c6d1a user: dan tags: trunk | |
2012-09-15
| ||
17:03 | Improve performance testing script lsmperf.tcl. check-in: 108a6143bf user: dan tags: trunk | |
Changes
Changes to lsm-test/lsmtest_main.c.
︙ | ︙ | |||
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 | #define ST_PAUSE 2 #define ST_FETCH 3 #define ST_SCAN 4 #define ST_NSCAN 5 #define ST_KEYSIZE 6 #define ST_VALSIZE 7 int do_speed_test2(int nArg, char **azArg){ struct Option { const char *zOpt; int eVal; int iDefault; } aOpt[] = { { "-repeat", ST_REPEAT, 10}, { "-write", ST_WRITE, 10000}, { "-pause", ST_PAUSE, 0}, { "-fetch", ST_FETCH, 0}, { "-scan", ST_SCAN, 0}, { "-nscan", ST_NSCAN, 0}, { "-keysize", ST_KEYSIZE, 12}, { "-valsize", ST_VALSIZE, 100}, { "-system", -1, 0}, {0, 0, 0} }; int i; int aParam[8]; int rc = 0; TestDb *pDb; | > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | #define ST_PAUSE 2 #define ST_FETCH 3 #define ST_SCAN 4 #define ST_NSCAN 5 #define ST_KEYSIZE 6 #define ST_VALSIZE 7 static void print_speed_test_help(){ printf( "\n" "Repeat the following $repeat times:\n" " 1. Insert $write key-value pairs. One transaction for each write op.\n" " 2. Pause for $pause ms.\n" " 3. Perform $fetch queries on the database.\n" "\n" " Keys are $keysize bytes in size. Values are $valsize bytes in size\n" " Both keys and values are pseudo-randomly generated\n" "\n" "Options are:\n" " -repeat $repeat (default value 10)\n" " -write $write (default value 10000)\n" " -pause $pause (default value 0)\n" " -fetch $fetch (default value 0)\n" " -keysize $keysize (default value 12)\n" " -valsize $valsize (default value 100)\n" " -system $system (default value \"lsm\"\n" "\n" ); } int do_speed_test2(int nArg, char **azArg){ struct Option { const char *zOpt; int eVal; int iDefault; } aOpt[] = { { "-repeat", ST_REPEAT, 10}, { "-write", ST_WRITE, 10000}, { "-pause", ST_PAUSE, 0}, { "-fetch", ST_FETCH, 0}, { "-scan", ST_SCAN, 0}, { "-nscan", ST_NSCAN, 0}, { "-keysize", ST_KEYSIZE, 12}, { "-valsize", ST_VALSIZE, 100}, { "-system", -1, 0}, { "help", -2, 0}, {0, 0, 0} }; int i; int aParam[8]; int rc = 0; TestDb *pDb; |
︙ | ︙ | |||
513 514 515 516 517 518 519 | if( aOpt[i].zOpt ) aParam[aOpt[i].eVal] = aOpt[i].iDefault; } /* Process the command line switches. */ for(i=0; i<nArg; i+=2){ int iSel; rc = testArgSelect(aOpt, "switch", azArg[i], &iSel); | | > > > > > > | 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 | if( aOpt[i].zOpt ) aParam[aOpt[i].eVal] = aOpt[i].iDefault; } /* Process the command line switches. */ for(i=0; i<nArg; i+=2){ int iSel; rc = testArgSelect(aOpt, "switch", azArg[i], &iSel); if( rc ){ return rc; } if( aOpt[iSel].eVal==-2 ){ print_speed_test_help(); return 0; } if( i+1==nArg ){ testPrintError("option %s requires an argument\n", aOpt[iSel].zOpt); return 1; } if( aOpt[iSel].eVal>=0 ){ aParam[aOpt[iSel].eVal] = atoi(azArg[i+1]); }else{ |
︙ | ︙ |
Changes to lsm-test/lsmtest_tdb3.c.
︙ | ︙ | |||
585 586 587 588 589 590 591 592 | static void xWorkHook(lsm_db *db, void *pArg){ LsmDb *p = (LsmDb *)pArg; if( p->xWork ) p->xWork(db, p->pWorkCtx); } #define TEST_NO_RECOVERY -1 | > | | > > > | 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 | static void xWorkHook(lsm_db *db, void *pArg){ LsmDb *p = (LsmDb *)pArg; if( p->xWork ) p->xWork(db, p->pWorkCtx); } #define TEST_NO_RECOVERY -1 #define TEST_THREADS -2 static int test_lsm_config_str( LsmDb *pLsm, lsm_db *db, int bWorker, const char *zStr, int *pnThread ){ struct CfgParam { const char *zParam; int bWorker; int eParam; } aParam[] = { { "write_buffer", 0, LSM_CONFIG_WRITE_BUFFER }, { "page_size", 0, LSM_CONFIG_PAGE_SIZE }, { "block_size", 0, LSM_CONFIG_BLOCK_SIZE }, { "safety", 0, LSM_CONFIG_SAFETY }, { "autowork", 0, LSM_CONFIG_AUTOWORK }, { "log_size", 0, LSM_CONFIG_LOG_SIZE }, { "mmap", 0, LSM_CONFIG_MMAP }, { "use_log", 0, LSM_CONFIG_USE_LOG }, { "nmerge", 0, LSM_CONFIG_NMERGE }, { "max_freelist", 0, LSM_CONFIG_MAX_FREELIST }, { "multi_proc", 0, LSM_CONFIG_MULTIPLE_PROCESSES }, { "worker_nmerge", 1, LSM_CONFIG_NMERGE }, { "test_no_recovery", 0, TEST_NO_RECOVERY }, { "threads", 0, TEST_THREADS }, { 0, 0 } }; const char *z = zStr; int nThread = 1; assert( db ); while( z[0] ){ const char *zStart; /* Skip whitespace */ while( *z==' ' ) z++; |
︙ | ︙ | |||
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 | } }else{ if( pLsm ){ switch( eParam ){ case TEST_NO_RECOVERY: pLsm->bNoRecovery = iVal; break; } } } }else if( z!=zStart ){ goto syntax_error; } } return 0; syntax_error: testPrintError("syntax error at: \"%s\"\n", z); return 1; } int tdb_lsm_config_str(TestDb *pDb, const char *zStr){ int rc = 0; if( tdb_lsm(pDb) ){ int i; LsmDb *pLsm = (LsmDb *)pDb; | > > > > | | > > | 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 | } }else{ if( pLsm ){ switch( eParam ){ case TEST_NO_RECOVERY: pLsm->bNoRecovery = iVal; break; case TEST_THREADS: nThread = iVal; break; } } } }else if( z!=zStart ){ goto syntax_error; } } if( pnThread ) *pnThread = nThread; return 0; syntax_error: testPrintError("syntax error at: \"%s\"\n", z); return 1; } int tdb_lsm_config_str(TestDb *pDb, const char *zStr){ int rc = 0; if( tdb_lsm(pDb) ){ int i; LsmDb *pLsm = (LsmDb *)pDb; rc = test_lsm_config_str(pLsm, pLsm->db, 0, zStr, 0); #ifdef LSM_MUTEX_PTHREADS for(i=0; rc==0 && i<pLsm->nWorker; i++){ rc = test_lsm_config_str(0, pLsm->aWorker[i].pWorker, 1, zStr, 0); } #endif } return rc; } static int testLsmStartWorkers(LsmDb *, int, const char *, const char *); static int testLsmOpen( const char *zCfg, const char *zFilename, int bClear, TestDb **ppDb ){ |
︙ | ︙ | |||
747 748 749 750 751 752 753 754 755 | pDb->env.xShmBarrier = testEnvShmBarrier; pDb->env.xShmMap = testEnvShmMap; pDb->env.xShmUnmap = testEnvShmUnmap; pDb->env.xSleep = testEnvSleep; rc = lsm_new(&pDb->env, &pDb->db); if( rc==LSM_OK ){ lsm_config_log(pDb->db, xLog, 0); lsm_config_work_hook(pDb->db, xWorkHook, (void *)pDb); | > | > > > > > > > > | 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 | pDb->env.xShmBarrier = testEnvShmBarrier; pDb->env.xShmMap = testEnvShmMap; pDb->env.xShmUnmap = testEnvShmUnmap; pDb->env.xSleep = testEnvSleep; rc = lsm_new(&pDb->env, &pDb->db); if( rc==LSM_OK ){ int nThread = 1; lsm_config_log(pDb->db, xLog, 0); lsm_config_work_hook(pDb->db, xWorkHook, (void *)pDb); rc = test_lsm_config_str(pDb, pDb->db, 0, zCfg, &nThread); if( rc==LSM_OK ) rc = lsm_open(pDb->db, zFilename); #ifdef LSM_MUTEX_PTHREADS if( rc==LSM_OK && (nThread==2 || nThread==3) ){ testLsmStartWorkers(pDb, nThread-1, zFilename, zCfg); } #endif if( rc!=LSM_OK ){ test_lsm_close((TestDb *)pDb); pDb = 0; } } *ppDb = (TestDb *)pDb; |
︙ | ︙ | |||
883 884 885 886 887 888 889 890 | while( (pWorker = p->pWorker) ){ int nWrite = 0; int rc; /* Do some work. If an error occurs, exit. */ pthread_mutex_unlock(&p->worker_mutex); rc = lsm_work(pWorker, p->lsm_work_flags, p->lsm_work_npage, &nWrite); pthread_mutex_lock(&p->worker_mutex); | > | > | 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 | while( (pWorker = p->pWorker) ){ int nWrite = 0; int rc; /* Do some work. If an error occurs, exit. */ pthread_mutex_unlock(&p->worker_mutex); rc = lsm_work(pWorker, p->lsm_work_flags, p->lsm_work_npage, &nWrite); printf("# worked %d units\n", nWrite); pthread_mutex_lock(&p->worker_mutex); if( rc!=LSM_OK && rc!=LSM_BUSY ){ p->worker_rc = rc; break; } /* If the call to lsm_work() indicates that there is nothing more ** to do at this point, wait on the condition variable. The thread will ** wake up when it is signaled either because the client thread has ** flushed an in-memory tree into the db file or when the connection ** is being closed. */ if( nWrite==0 ){ if( p->pWorker && p->bDoWork==0 ){ pthread_cond_wait(&p->worker_cond, &p->worker_mutex); } p->bDoWork = 0; } } pthread_mutex_unlock(&p->worker_mutex); printf("# worker EXIT\n"); return 0; } /* ** Signal worker thread iWorker that there may be work to do. |
︙ | ︙ | |||
962 963 964 965 966 967 968 969 970 971 972 973 974 975 | static void mt_client_work_hook(lsm_db *db, void *pArg){ LsmDb *pDb = (LsmDb *)pArg; /* LsmDb database handle */ int i; /* Iterator variable */ /* Invoke the user level work-hook, if any. */ if( pDb->xWork ) pDb->xWork(db, pDb->pWorkCtx); /* Signal each worker thread */ for(i=0; i<pDb->nWorker; i++){ mt_signal_worker(pDb, i); } } static void mt_worker_work_hook(lsm_db *db, void *pArg){ | > | 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 | static void mt_client_work_hook(lsm_db *db, void *pArg){ LsmDb *pDb = (LsmDb *)pArg; /* LsmDb database handle */ int i; /* Iterator variable */ /* Invoke the user level work-hook, if any. */ if( pDb->xWork ) pDb->xWork(db, pDb->pWorkCtx); printf("# signalling worker threads\n"); /* Signal each worker thread */ for(i=0; i<pDb->nWorker; i++){ mt_signal_worker(pDb, i); } } static void mt_worker_work_hook(lsm_db *db, void *pArg){ |
︙ | ︙ | |||
1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 | /* Kick off the worker thread. */ if( rc==0 ) rc = pthread_cond_init(&p->worker_cond, 0); if( rc==0 ) rc = pthread_mutex_init(&p->worker_mutex, 0); if( rc==0 ) rc = pthread_create(&p->worker_thread, 0, worker_main, (void *)p); return rc; } static int test_lsm_mt( const char *zFilename, /* File to open */ int nWorker, /* Either 1 or 2, for worker threads */ int bClear, /* True to delete any existing db */ TestDb **ppDb /* OUT: TestDb database handle */ ){ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 | /* Kick off the worker thread. */ if( rc==0 ) rc = pthread_cond_init(&p->worker_cond, 0); if( rc==0 ) rc = pthread_mutex_init(&p->worker_mutex, 0); if( rc==0 ) rc = pthread_create(&p->worker_thread, 0, worker_main, (void *)p); return rc; } static int testLsmStartWorkers( LsmDb *pDb, int nWorker, const char *zFilename, const char *zCfg ){ int rc; int bAutowork = 0; assert( nWorker==1 || nWorker==2 ); #if 0 /* Turn off auto-work and configure a work-hook on the client connection. */ lsm_config(pDb->db, LSM_CONFIG_AUTOWORK, &bAutowork); #endif lsm_config_work_hook(pDb->db, mt_client_work_hook, (void *)pDb); pDb->aWorker = (LsmWorker *)testMalloc(sizeof(LsmWorker) * nWorker); memset(pDb->aWorker, 0, sizeof(LsmWorker) * nWorker); pDb->nWorker = nWorker; rc = mt_start_worker( pDb, 0, zFilename, LSM_WORK_CHECKPOINT|LSM_WORK_FLUSH, 512 ); #if 0 rc = mt_start_worker(pDb, 0, zFilename, LSM_WORK_CHECKPOINT, nWorker==1 ? 512 : 0 ); #endif if( rc==0 && nWorker==2 ){ rc = mt_start_worker(pDb, 1, zFilename, 0, 512); } return rc; } static int test_lsm_mt( const char *zFilename, /* File to open */ int nWorker, /* Either 1 or 2, for worker threads */ int bClear, /* True to delete any existing db */ TestDb **ppDb /* OUT: TestDb database handle */ ){ |
︙ | ︙ |
Changes to src/lsmInt.h.
︙ | ︙ | |||
79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | typedef struct FileSystem FileSystem; 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 MetaPage MetaPage; typedef struct MultiCursor MultiCursor; typedef struct Page Page; typedef struct Segment Segment; typedef struct SegmentMerger SegmentMerger; typedef struct Snapshot Snapshot; typedef struct TransMark TransMark; typedef struct Tree Tree; | > > > > > | | | < < < | < < < | 79 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 | typedef struct FileSystem FileSystem; 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; typedef struct MergeInput MergeInput; typedef struct MetaPage MetaPage; typedef struct MultiCursor MultiCursor; typedef struct Page Page; typedef struct Segment Segment; typedef struct SegmentMerger SegmentMerger; typedef struct ShmChunk ShmChunk; typedef struct ShmHeader ShmHeader; typedef struct ShmReader ShmReader; typedef struct Snapshot Snapshot; typedef struct TransMark TransMark; typedef struct Tree Tree; typedef struct TreeCursor TreeCursor; typedef struct TreeHeader TreeHeader; typedef struct TreeMark TreeMark; typedef struct TreeRoot TreeRoot; typedef unsigned char u8; typedef unsigned short int u16; typedef unsigned int u32; typedef lsm_i64 i64; typedef unsigned long long int u64; |
︙ | ︙ | |||
229 230 231 232 233 234 235 236 237 238 239 240 241 242 | struct DbLog { u32 cksum0; /* Checksum 0 at offset iOff */ u32 cksum1; /* Checksum 1 at offset iOff */ i64 iSnapshotId; /* Log space has been reclaimed to this ss */ LogRegion aRegion[3]; /* Log file regions (see docs in lsm_log.c) */ }; /* ** Tree header structure. */ struct TreeHeader { u32 iUsedShmid; /* Id of first shm chunk used by this tree */ u32 iNextShmid; /* Shm-id of next chunk allocated */ u32 iFirst; /* Chunk number of smallest shm-id */ | > > > > > > < | < > > > > > | 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 259 260 261 262 263 | struct DbLog { u32 cksum0; /* Checksum 0 at offset iOff */ u32 cksum1; /* Checksum 1 at offset iOff */ i64 iSnapshotId; /* Log space has been reclaimed to this ss */ LogRegion aRegion[3]; /* Log file regions (see docs in lsm_log.c) */ }; struct TreeRoot { u32 iRoot; u32 nHeight; u32 iTransId; }; /* ** Tree header structure. */ struct TreeHeader { u32 iUsedShmid; /* Id of first shm chunk used by this tree */ u32 iNextShmid; /* Shm-id of next chunk allocated */ u32 iFirst; /* Chunk number of smallest shm-id */ u32 nChunk; /* Number of chunks in shared-memory file */ TreeRoot root; /* Root and height of current tree */ u32 iWrite; /* Write offset in shm file */ u32 nByte; /* Size of current tree structure in bytes */ TreeRoot oldroot; /* Root and height of the previous tree */ u32 iOldShmid; /* Last shm-id used by previous tree */ i64 iOldLog; /* Log offset associated with old tree */ u32 oldcksum0; u32 oldcksum1; DbLog log; /* Current layout of log file */ u32 aCksum[2]; /* Checksums 1 and 2. */ }; /* ** Database handle structure. ** |
︙ | ︙ | |||
458 459 460 461 462 463 464 465 466 467 468 469 470 471 | ** to read or write a database file on disk. See the description of struct ** Database below for futher details. */ struct Snapshot { Database *pDatabase; /* Database this snapshot belongs to */ Level *pLevel; /* Pointer to level 0 of snapshot (or NULL) */ i64 iId; /* Snapshot id */ /* Used by worker snapshots only */ int nBlock; /* Number of blocks in database file */ u32 aiAppend[LSM_APPLIST_SZ]; /* Append point list */ Freelist freelist; /* Free block list */ int nFreelistOvfl; /* Number of extra free-list entries in LSM */ }; | > | 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 | ** to read or write a database file on disk. See the description of struct ** Database below for futher details. */ struct Snapshot { Database *pDatabase; /* Database this snapshot belongs to */ Level *pLevel; /* Pointer to level 0 of snapshot (or NULL) */ i64 iId; /* Snapshot id */ i64 iLogOff; /* Log file offset */ /* Used by worker snapshots only */ int nBlock; /* Number of blocks in database file */ u32 aiAppend[LSM_APPLIST_SZ]; /* Append point list */ Freelist freelist; /* Free block list */ int nFreelistOvfl; /* Number of extra free-list entries in LSM */ }; |
︙ | ︙ | |||
508 509 510 511 512 513 514 515 516 | */ int lsmTreeNew(lsm_env *, int (*)(void *, int, void *, int), Tree **ppTree); void lsmTreeRelease(lsm_env *, Tree *); void lsmTreeClear(lsm_db *); int lsmTreeInit(lsm_db *); int lsmTreeRepair(lsm_db *); int lsmTreeSize(lsm_db *); int lsmTreeEndTransaction(lsm_db *pDb, int bCommit); | > > > > < | | 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 | */ int lsmTreeNew(lsm_env *, int (*)(void *, int, void *, int), Tree **ppTree); void lsmTreeRelease(lsm_env *, Tree *); void lsmTreeClear(lsm_db *); int lsmTreeInit(lsm_db *); int lsmTreeRepair(lsm_db *); void lsmTreeMakeOld(lsm_db *pDb, int *pnFlush); void lsmTreeDiscardOld(lsm_db *pDb); int lsmTreeHasOld(lsm_db *pDb); int lsmTreeSize(lsm_db *); int lsmTreeEndTransaction(lsm_db *pDb, int bCommit); int lsmTreeLoadHeader(lsm_db *pDb, int *); int lsmTreeLoadHeaderOk(lsm_db *, int); int lsmTreeInsert(lsm_db *pDb, void *pKey, int nKey, void *pVal, int nVal); void lsmTreeRollback(lsm_db *pDb, TreeMark *pMark); void lsmTreeMark(lsm_db *pDb, TreeMark *pMark); int lsmTreeCursorNew(lsm_db *pDb, int, TreeCursor **); void lsmTreeCursorDestroy(TreeCursor *); int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes); int lsmTreeCursorNext(TreeCursor *pCsr); int lsmTreeCursorPrev(TreeCursor *pCsr); int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast); void lsmTreeCursorReset(TreeCursor *pCsr); |
︙ | ︙ |
Changes to src/lsm_ckpt.c.
︙ | ︙ | |||
36 37 38 39 40 41 42 | ** 5. The block size. ** 6. The number of levels. ** 7. The nominal database page size. ** 8. Flag indicating if there exists a FREELIST record in the database. ** ** Log pointer: ** | > > | > > | | 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | ** 5. The block size. ** 6. The number of levels. ** 7. The nominal database page size. ** 8. Flag indicating if there exists a FREELIST record in the database. ** ** Log pointer: ** ** 1. The log offset MSW. ** 2. The log offset LSW. ** 3. Log checksum 0. ** 4. Log checksum 1. ** ** See ckptExportLog() and ckptImportLog(). ** ** Append points: ** ** 4 integers. See ckptExportAppendlist(). ** ** For each level in the database, a level record. Formatted as follows: ** |
︙ | ︙ | |||
322 323 324 325 326 327 328 | int *piOut, int *pRc ){ int iOut = *piOut; assert( iOut==CKPT_HDR_LO_MSW ); | | | < | | | 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 | int *piOut, int *pRc ){ int iOut = *piOut; assert( iOut==CKPT_HDR_LO_MSW ); if( bFlush && pDb->treehdr.iOldShmid ){ i64 iOff = pDb->treehdr.iOldLog; ckptSetValue(p, iOut++, (iOff >> 32) & 0xFFFFFFFF, pRc); ckptSetValue(p, iOut++, (iOff & 0xFFFFFFFF), pRc); ckptSetValue(p, iOut++, pDb->treehdr.oldcksum0, pRc); ckptSetValue(p, iOut++, pDb->treehdr.oldcksum1, pRc); }else{ for(; iOut<=CKPT_HDR_LO_CKSUM2; iOut++){ ckptSetValue(p, iOut, pDb->pShmhdr->aSnap2[iOut], pRc); } } *piOut = iOut; |
︙ | ︙ | |||
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 | int nCopy; int nLevel = (int)aCkpt[CKPT_HDR_NLEVEL]; int iIn = CKPT_HDR_SIZE + CKPT_APPENDLIST_SIZE + CKPT_LOGPTR_SIZE; pNew->iId = lsmCheckpointId(aCkpt, 0); pNew->nBlock = aCkpt[CKPT_HDR_NBLOCK]; rc = ckptLoadLevels(pDb, aCkpt, &iIn, nLevel, &pNew->pLevel); /* Make a copy of the append-list */ nCopy = sizeof(u32) * LSM_APPLIST_SZ; memcpy(pNew->aiAppend, &aCkpt[CKPT_HDR_SIZE+CKPT_LOGPTR_SIZE], nCopy); /* Copy the free-list */ if( bInclFreelist ){ | > | 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 | int nCopy; int nLevel = (int)aCkpt[CKPT_HDR_NLEVEL]; int iIn = CKPT_HDR_SIZE + CKPT_APPENDLIST_SIZE + CKPT_LOGPTR_SIZE; pNew->iId = lsmCheckpointId(aCkpt, 0); pNew->nBlock = aCkpt[CKPT_HDR_NBLOCK]; rc = ckptLoadLevels(pDb, aCkpt, &iIn, nLevel, &pNew->pLevel); pNew->iLogOff = lsmCheckpointLogOffset(aCkpt); /* Make a copy of the append-list */ nCopy = sizeof(u32) * LSM_APPLIST_SZ; memcpy(pNew->aiAppend, &aCkpt[CKPT_HDR_SIZE+CKPT_LOGPTR_SIZE], nCopy); /* Copy the free-list */ if( bInclFreelist ){ |
︙ | ︙ |
Changes to src/lsm_main.c.
︙ | ︙ | |||
218 219 220 221 222 223 224 | } /* Write the contents of the in-memory tree into the database file and ** update the worker snapshot accordingly. Then flush the contents of ** the db file to disk too. No calls to fsync() are made here - just ** write(). */ if( rc==LSM_OK ) rc = lsmSortedFlushTree(pDb, &nOvfl); | < < | 218 219 220 221 222 223 224 225 226 227 228 229 230 231 | } /* Write the contents of the in-memory tree into the database file and ** update the worker snapshot accordingly. Then flush the contents of ** the db file to disk too. No calls to fsync() are made here - just ** write(). */ if( rc==LSM_OK ) rc = lsmSortedFlushTree(pDb, &nOvfl); lsmFinishWork(pDb, 1, nOvfl, &rc); /* Restore the position of any open cursors */ if( rc==LSM_OK && pDb->pCsr ){ lsmFreeSnapshot(pDb->pEnv, pDb->pClient); pDb->pClient = 0; rc = lsmCheckpointLoad(pDb, 0); |
︙ | ︙ | |||
532 533 534 535 536 537 538 539 540 541 542 543 544 545 | nBefore = lsmTreeSize(pDb); rc = lsmTreeInsert(pDb, (void *)pKey, nKey, (void *)pVal, nVal); nAfter = lsmTreeSize(pDb); nDiff = (nAfter/nQuant) - (nBefore/nQuant); if( rc==LSM_OK && pDb->bAutowork && nDiff!=0 ){ rc = dbAutoWork(pDb, nDiff * LSM_AUTOWORK_QUANT); } } /* If a transaction was opened at the start of this function, commit it. ** Or, if an error has occurred, roll it back. */ if( bCommit ){ | > | 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 | nBefore = lsmTreeSize(pDb); rc = lsmTreeInsert(pDb, (void *)pKey, nKey, (void *)pVal, nVal); nAfter = lsmTreeSize(pDb); nDiff = (nAfter/nQuant) - (nBefore/nQuant); if( rc==LSM_OK && pDb->bAutowork && nDiff!=0 ){ rc = dbAutoWork(pDb, nDiff * LSM_AUTOWORK_QUANT); if( rc==LSM_BUSY ) rc = LSM_OK; } } /* If a transaction was opened at the start of this function, commit it. ** Or, if an error has occurred, roll it back. */ if( bCommit ){ |
︙ | ︙ | |||
713 714 715 716 717 718 719 | } } return rc; } int lsm_commit(lsm_db *pDb, int iLevel){ | | < < < < < > > > | | > > > > > > > > > > > > > > > > > | | | > > > | 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 | } } return rc; } int lsm_commit(lsm_db *pDb, int iLevel){ int nFlush = 0; /* Number of flushable trees in memory */ int rc = LSM_OK; assert_db_state( pDb ); /* A value less than zero means close the innermost nested transaction. */ if( iLevel<0 ) iLevel = LSM_MAX(0, pDb->nTransOpen - 1); if( iLevel<pDb->nTransOpen ){ if( iLevel==0 ){ /* Commit the transaction to disk. */ if( rc==LSM_OK ) rc = lsmLogCommit(pDb); if( rc==LSM_OK && pDb->eSafety==LSM_SAFETY_FULL ){ rc = lsmFsSyncLog(pDb->pFS); } if( lsmTreeSize(pDb)>pDb->nTreeLimit ){ lsmTreeMakeOld(pDb, &nFlush); } lsmFinishWriteTrans(pDb, (rc==LSM_OK)); } pDb->nTransOpen = iLevel; } dbReleaseClientSnapshot(pDb); /* If nFlush==0, then do not flush any data from the in-memory tree to ** disk. If nFlush==1, then there exists an "old" tree that should be ** flushed to disk if auto-work is enabled. Or if nFlush==2, then both ** the old and current trees are large enough to flush to disk. In this ** case do so regardless of the auto-work setting. ** ** If auto-work is enabled and data was written to disk, also sync the ** db and checkpoint the latest snapshot. ** ** Ignore any LSM_BUSY errors that occur during these operations. If ** LSM_BUSY does occur, it means some other connection is already working ** on flushing the in-memory tree or checkpointing the database. */ assert( rc!=LSM_BUSY); if( rc==LSM_OK && (nFlush>1 || (nFlush && pDb->bAutowork)) ){ rc = lsmFlushToDisk(pDb); if( rc==LSM_OK && pDb->bAutowork ){ rc = lsmCheckpointWrite(pDb); } } if( rc==LSM_BUSY ) rc = LSM_OK; return rc; } int lsm_rollback(lsm_db *pDb, int iLevel){ int rc = LSM_OK; assert_db_state( pDb ); |
︙ | ︙ |
Changes to src/lsm_shared.c.
︙ | ︙ | |||
172 173 174 175 176 177 178 | if( rc==LSM_OK ){ /* Flush the in-memory tree, if required. If there is data to flush, ** this will create a new client snapshot in Database.pClient. The ** checkpoint (serialization) of this snapshot may be written to disk ** by the following block. */ rc = lsmTreeLoadHeader(pDb, 0); if( rc==LSM_OK && lsmTreeSize(pDb)>0 ){ | > > | | 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | if( rc==LSM_OK ){ /* Flush the in-memory tree, if required. If there is data to flush, ** this will create a new client snapshot in Database.pClient. The ** checkpoint (serialization) of this snapshot may be written to disk ** by the following block. */ rc = lsmTreeLoadHeader(pDb, 0); if( rc==LSM_OK && lsmTreeSize(pDb)>0 ){ int nFlush = 0; lsmTreeMakeOld(pDb, &nFlush); if( nFlush ) rc = lsmFlushToDisk(pDb); } /* Write a checkpoint to disk. */ if( rc==LSM_OK ){ rc = lsmCheckpointWrite(pDb); } |
︙ | ︙ | |||
735 736 737 738 739 740 741 742 | rc = lsmLogBegin(pDb); } /* If everything was successful, set the "transaction-in-progress" flag ** and return LSM_OK. Otherwise, if some error occurred, relinquish the ** WRITER lock and return an error code. */ if( rc==LSM_OK ){ pShm->bWriter = 1; | > | > > > | 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 | rc = lsmLogBegin(pDb); } /* If everything was successful, set the "transaction-in-progress" flag ** and return LSM_OK. Otherwise, if some error occurred, relinquish the ** WRITER lock and return an error code. */ if( rc==LSM_OK ){ TreeHeader *p = &pDb->treehdr; pShm->bWriter = 1; p->root.iTransId++; if( lsmTreeHasOld(pDb) && p->iOldLog==pDb->pClient->iLogOff ){ lsmTreeDiscardOld(pDb); } }else{ lsmShmLock(pDb, LSM_LOCK_WRITER, LSM_LOCK_UNLOCK, 0); if( pDb->pCsr==0 ) lsmFinishReadTrans(pDb); } return rc; } |
︙ | ︙ |
Changes to src/lsm_sorted.c.
︙ | ︙ | |||
250 251 252 253 254 255 256 | int flags; /* Mask of CURSOR_XXX flags */ int (*xCmp)(void *, int, void *, int); /* Compare function */ int eType; /* Cache of current key type */ Blob key; /* Cache of current key (or NULL) */ Blob val; /* Cache of current value */ | | | > | | | 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 | int flags; /* Mask of CURSOR_XXX flags */ int (*xCmp)(void *, int, void *, int); /* Compare function */ int eType; /* Cache of current key type */ Blob key; /* Cache of current key (or NULL) */ Blob val; /* Cache of current value */ TreeCursor *apTreeCsr[2]; /* One or two tree cursors */ int nSegCsr; /* Size of aSegCsr[] array */ LevelCursor *aSegCsr; /* Array of cursors open on sorted files */ int nTree; int *aTree; BtreeCursor *pBtCsr; Snapshot *pSnap; /* Used by cursors flushing the in-memory tree only */ int *pnOvfl; /* Number of free-list entries to store */ void *pSystemVal; /* Pointer to buffer to free */ }; #define CURSOR_DATA_TREE0 0 /* Current tree cursor */ #define CURSOR_DATA_TREE1 1 /* The "old" tree, if any */ #define CURSOR_DATA_SYSTEM 2 #define CURSOR_DATA_SEGMENT 3 /* ** CURSOR_IGNORE_DELETE ** If set, this cursor will not visit SORTED_DELETE keys. ** ** CURSOR_NEW_SYSTEM |
︙ | ︙ | |||
1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 | lsmFsPageRef(pTest); while( pTest ){ Page *pNext; int rc = lsmFsDbPageNext(pPtr->pSeg, pTest, eDir, &pNext); lsmFsPageRelease(pTest); pTest = pNext; if( pTest ){ int nData; u8 *aData = fsPageData(pTest, &nData); int nCell = pageGetNRec(aData, nData); int flags = pageGetFlags(aData, nData); | > | 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 | lsmFsPageRef(pTest); while( pTest ){ Page *pNext; int rc = lsmFsDbPageNext(pPtr->pSeg, pTest, eDir, &pNext); lsmFsPageRelease(pTest); if( rc ) return 1; pTest = pNext; if( pTest ){ int nData; u8 *aData = fsPageData(pTest, &nData); int nCell = pageGetNRec(aData, nData); int flags = pageGetFlags(aData, nData); |
︙ | ︙ | |||
1850 1851 1852 1853 1854 1855 1856 | } static void mcursorFreeComponents(MultiCursor *pCsr){ int i; lsm_env *pEnv = pCsr->pDb->pEnv; /* Close the tree cursor, if any. */ | | > | 1852 1853 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 | } static void mcursorFreeComponents(MultiCursor *pCsr){ int i; lsm_env *pEnv = pCsr->pDb->pEnv; /* Close the tree cursor, if any. */ lsmTreeCursorDestroy(pCsr->apTreeCsr[0]); lsmTreeCursorDestroy(pCsr->apTreeCsr[1]); /* Close the sorted file cursors */ for(i=0; i<pCsr->nSegCsr; i++){ segmentCursorClose(pEnv, &pCsr->aSegCsr[i]); } /* And the b-tree cursor, if any */ |
︙ | ︙ | |||
1872 1873 1874 1875 1876 1877 1878 | /* Zero fields */ pCsr->nSegCsr = 0; pCsr->aSegCsr = 0; pCsr->nTree = 0; pCsr->aTree = 0; pCsr->pSystemVal = 0; pCsr->pSnap = 0; | | > | 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 | /* Zero fields */ pCsr->nSegCsr = 0; pCsr->aSegCsr = 0; pCsr->nTree = 0; pCsr->aTree = 0; pCsr->pSystemVal = 0; pCsr->pSnap = 0; pCsr->apTreeCsr[0] = 0; pCsr->apTreeCsr[1] = 0; pCsr->pBtCsr = 0; } void lsmMCursorClose(MultiCursor *pCsr){ if( pCsr ){ lsm_db *pDb = pCsr->pDb; MultiCursor **pp; /* Iterator variable */ |
︙ | ︙ | |||
1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 | } } return rc; } static int multiCursorNew( lsm_db *pDb, /* Database handle */ Snapshot *pSnap, /* Snapshot to use for this cursor */ | > > > > > > | > > | > > > > > | > | 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 | } } return rc; } /* ** Parameter iUseTree must be set to 0, 1 or 2. If it is not zero, then a ** tree cursor is added to the multi-cursor before it is returned. If ** iUseTree is 1, then the cursor accesses the entire tree. Otherwise, if ** iUseTree is 2, it iterates through the "old" tree only. */ static int multiCursorNew( lsm_db *pDb, /* Database handle */ Snapshot *pSnap, /* Snapshot to use for this cursor */ int iUseTree, /* If true, search the in-memory tree */ int bUserOnly, /* If true, ignore all system data */ MultiCursor **ppCsr /* OUT: Allocated cursor */ ){ int rc = LSM_OK; /* Return Code */ MultiCursor *pCsr = *ppCsr; /* Allocated multi-cursor */ assert( iUseTree==0 || iUseTree==1 || iUseTree==2 ); if( pCsr==0 ){ pCsr = (MultiCursor *)lsmMallocZeroRc(pDb->pEnv, sizeof(MultiCursor), &rc); if( pCsr ){ pCsr->pNext = pDb->pCsr; pDb->pCsr = pCsr; } } if( rc==LSM_OK ){ if( iUseTree ){ rc = lsmTreeCursorNew(pDb, iUseTree-1, &pCsr->apTreeCsr[0]); if( rc==LSM_OK && lsmTreeHasOld(pDb) && iUseTree==1 && pDb->treehdr.iOldLog!=pSnap->iLogOff ){ rc = lsmTreeCursorNew(pDb, 1, &pCsr->apTreeCsr[1]); } } pCsr->pDb = pDb; pCsr->pSnap = pSnap; pCsr->xCmp = pDb->xCmp; if( bUserOnly ){ pCsr->flags |= CURSOR_IGNORE_SYSTEM; } |
︙ | ︙ | |||
2127 2128 2129 2130 2131 2132 2133 | int *pnKey /* OUT: Size of *ppKey in bytes */ ){ int nKey = 0; void *pKey = 0; int eType = 0; switch( iKey ){ | | > > | | | > | 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 | int *pnKey /* OUT: Size of *ppKey in bytes */ ){ int nKey = 0; void *pKey = 0; int eType = 0; switch( iKey ){ case CURSOR_DATA_TREE0: case CURSOR_DATA_TREE1: { TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; if( lsmTreeCursorValid(pTreeCsr) ){ int nVal; void *pVal; lsmTreeCursorKey(pTreeCsr, &pKey, &nKey); lsmTreeCursorValue(pTreeCsr, &pVal, &nVal); eType = (nVal<0) ? SORTED_DELETE : SORTED_WRITE; } break; } case CURSOR_DATA_SYSTEM: if( pCsr->flags & CURSOR_AT_FREELIST ){ pKey = (void *)"FREELIST"; nKey = 8; eType = SORTED_SYSTEM_WRITE; } |
︙ | ︙ | |||
2172 2173 2174 2175 2176 2177 2178 | static int multiCursorGetVal( MultiCursor *pCsr, int iVal, void **ppVal, int *pnVal ){ int rc = LSM_OK; | | > | | | 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 | static int multiCursorGetVal( MultiCursor *pCsr, int iVal, void **ppVal, int *pnVal ){ int rc = LSM_OK; if( iVal==CURSOR_DATA_TREE0 || iVal==CURSOR_DATA_TREE1 ){ TreeCursor *pTreeCsr = pCsr->apTreeCsr[iVal-CURSOR_DATA_TREE0]; if( lsmTreeCursorValid(pTreeCsr) ){ lsmTreeCursorValue(pTreeCsr, ppVal, pnVal); }else{ *ppVal = 0; *pnVal = 0; } }else if( iVal==CURSOR_DATA_SYSTEM ){ if( pCsr->flags & CURSOR_AT_FREELIST ){ void *aVal; |
︙ | ︙ | |||
2318 2319 2320 2321 2322 2323 2324 | } static int multiCursorEnd(MultiCursor *pCsr, int bLast){ int rc = LSM_OK; int i; pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK); | | | > > > > > | 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 2361 | } static int multiCursorEnd(MultiCursor *pCsr, int bLast){ int rc = LSM_OK; int i; pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK); if( pCsr->apTreeCsr[0] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[0], bLast); } if( rc==LSM_OK && pCsr->apTreeCsr[1] ){ rc = lsmTreeCursorEnd(pCsr->apTreeCsr[1], bLast); } if( pCsr->flags & CURSOR_NEW_SYSTEM ){ assert( bLast==0 ); pCsr->flags |= CURSOR_AT_FREELIST; } for(i=0; rc==LSM_OK && i<pCsr->nSegCsr; i++){ rc = segmentCursorEnd(&pCsr->aSegCsr[i], bLast); } |
︙ | ︙ | |||
2364 2365 2366 2367 2368 2369 2370 | return rc; } int mcursorSave(MultiCursor *pCsr){ int rc = LSM_OK; if( pCsr->aTree ){ | | > | 2391 2392 2393 2394 2395 2396 2397 2398 2399 2400 2401 2402 2403 2404 2405 2406 | return rc; } int mcursorSave(MultiCursor *pCsr){ int rc = LSM_OK; if( pCsr->aTree ){ int iTree = pCsr->aTree[1]; if( iTree==CURSOR_DATA_TREE0 || iTree==CURSOR_DATA_TREE1 ){ multiCursorCacheKey(pCsr, &rc); } mcursorFreeComponents(pCsr); } return rc; } |
︙ | ︙ | |||
2417 2418 2419 2420 2421 2422 2423 | return pCsr->pDb; } void lsmMCursorReset(MultiCursor *pCsr){ int i; | | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > < | < < < < < < < < | < < < < < < < < < | 2445 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 2469 2470 2471 2472 2473 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491 2492 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 2510 2511 2512 2513 | return pCsr->pDb; } void lsmMCursorReset(MultiCursor *pCsr){ int i; lsmTreeCursorReset(pCsr->apTreeCsr[0]); lsmTreeCursorReset(pCsr->apTreeCsr[1]); for(i=0; i<pCsr->nSegCsr; i++){ segmentCursorReset(&pCsr->aSegCsr[i]); } pCsr->key.nData = 0; } static void treeCursorSeek( TreeCursor *pTreeCsr, void *pKey, int nKey, int eSeek ){ if( pTreeCsr ){ int res = 0; lsmTreeCursorSeek(pTreeCsr, pKey, nKey, &res); switch( eSeek ){ case LSM_SEEK_EQ: if( res!=0 ){ lsmTreeCursorReset(pTreeCsr); } break; case LSM_SEEK_GE: if( res<0 && lsmTreeCursorValid(pTreeCsr) ){ lsmTreeCursorNext(pTreeCsr); } break; default: if( res>0 ){ assert( lsmTreeCursorValid(pTreeCsr) ); lsmTreeCursorPrev(pTreeCsr); } break; } } } /* ** Seek the cursor. */ int lsmMCursorSeek(MultiCursor *pCsr, void *pKey, int nKey, int eSeek){ int eESeek = eSeek; /* Effective eSeek parameter */ int rc = LSM_OK; int i; int iPtr = 0; 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_NEW_SYSTEM)==0 ); assert( (pCsr->flags & CURSOR_AT_FREELIST)==0 ); pCsr->flags &= ~(CURSOR_NEXT_OK | CURSOR_PREV_OK); treeCursorSeek(pCsr->apTreeCsr[0], pKey, nKey, eESeek); treeCursorSeek(pCsr->apTreeCsr[1], pKey, nKey, eESeek); for(i=0; rc==LSM_OK && i<pCsr->nSegCsr; i++){ rc = segmentCursorSeek(&pCsr->aSegCsr[i], pKey, nKey, iPtr, eESeek, &iPtr); } if( rc==LSM_OK ){ rc = multiCursorAllocTree(pCsr); |
︙ | ︙ | |||
2502 2503 2504 2505 2506 2507 2508 | return rc; } int lsmMCursorValid(MultiCursor *pCsr){ int res = 0; if( pCsr->aTree ){ int iKey = pCsr->aTree[1]; | | | | 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 2557 | return rc; } int lsmMCursorValid(MultiCursor *pCsr){ int res = 0; if( pCsr->aTree ){ int iKey = pCsr->aTree[1]; if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){ res = lsmTreeCursorValid(pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]); }else{ void *pKey; multiCursorGetKey(pCsr, iKey, 0, &pKey, 0); res = pKey!=0; } } return res; |
︙ | ︙ | |||
2560 2561 2562 2563 2564 2565 2566 | } static int multiCursorAdvance(MultiCursor *pCsr, int bReverse){ int rc = LSM_OK; /* Return Code */ if( lsmMCursorValid(pCsr) ){ do { int iKey = pCsr->aTree[1]; | | > | | | 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 | } static int multiCursorAdvance(MultiCursor *pCsr, int bReverse){ int rc = LSM_OK; /* Return Code */ if( lsmMCursorValid(pCsr) ){ do { int iKey = pCsr->aTree[1]; if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){ 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_AT_FREELIST ); assert( pCsr->flags & CURSOR_NEW_SYSTEM ); assert( bReverse==0 ); pCsr->flags &= ~CURSOR_AT_FREELIST; }else if( iKey==(CURSOR_DATA_SEGMENT+pCsr->nSegCsr) ){ |
︙ | ︙ | |||
2600 2601 2602 2603 2604 2605 2606 2607 | int lsmMCursorPrev(MultiCursor *pCsr){ if( (pCsr->flags & CURSOR_PREV_OK)==0 ) return LSM_MISUSE_BKPT; return multiCursorAdvance(pCsr, 1); } int lsmMCursorKey(MultiCursor *pCsr, void **ppKey, int *pnKey){ | > | > | | | 2641 2642 2643 2644 2645 2646 2647 2648 2649 2650 2651 2652 2653 2654 2655 2656 2657 2658 2659 2660 2661 2662 2663 2664 2665 2666 | int lsmMCursorPrev(MultiCursor *pCsr){ if( (pCsr->flags & CURSOR_PREV_OK)==0 ) return LSM_MISUSE_BKPT; return multiCursorAdvance(pCsr, 1); } int lsmMCursorKey(MultiCursor *pCsr, void **ppKey, int *pnKey){ int iKey = pCsr->aTree[1]; if( iKey==CURSOR_DATA_TREE0 || iKey==CURSOR_DATA_TREE1 ){ TreeCursor *pTreeCsr = pCsr->apTreeCsr[iKey-CURSOR_DATA_TREE0]; lsmTreeCursorKey(pTreeCsr, ppKey, pnKey); }else{ int nKey; #ifndef NDEBUG void *pKey; int eType; multiCursorGetKey(pCsr, iKey, &eType, &pKey, &nKey); assert( eType==pCsr->eType ); assert( nKey==pCsr->key.nData ); assert( memcmp(pKey, pCsr->key.pData, nKey)==0 ); #endif nKey = pCsr->key.nData; if( nKey==0 ){ |
︙ | ︙ | |||
3483 3484 3485 3486 3487 3488 3489 | pNext = lsmDbSnapshotLevel(pDb->pWorker); pNew = (Level *)lsmMallocZeroRc(pDb->pEnv, sizeof(Level), &rc); /* 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). */ if( rc==LSM_OK ){ | | | 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 | pNext = lsmDbSnapshotLevel(pDb->pWorker); pNew = (Level *)lsmMallocZeroRc(pDb->pEnv, sizeof(Level), &rc); /* 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). */ if( rc==LSM_OK ){ rc = multiCursorNew(pDb, pDb->pWorker, (bTree ? 2 : 0), 0, &pCsr); if( rc==LSM_OK ){ pNew->pNext = pNext; lsmDbSnapshotSetLevel(pDb->pWorker, pNew); } if( rc==LSM_OK ){ if( pNext ){ assert( pNext->pMerge==0 || pNext->nRight>0 ); |
︙ | ︙ | |||
3583 3584 3585 3586 3587 3588 3589 | int *pnOvfl /* OUT: Number of free-list entries written */ ){ int rc; assert( pDb->pWorker ); /* If there is nothing to do, return early. */ | | | 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 | int *pnOvfl /* OUT: Number of free-list entries written */ ){ int rc; assert( pDb->pWorker ); /* If there is nothing to do, return early. */ if( lsmTreeHasOld(pDb)==0 && lsmCheckpointOverflowRequired(pDb)==0 ){ *pnOvfl = 0; return LSM_OK; } rc = sortedNewToplevel(pDb, 1, pnOvfl); assert( rc!=LSM_OK || lsmFsIntegrityCheck(pDb) ); |
︙ | ︙ | |||
4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 | } /* ** Perform work to merge database segments together. */ int lsm_work(lsm_db *pDb, int flags, int nPage, int *pnWrite){ int rc = LSM_OK; /* Return code */ /* This function may not be called if pDb has an open read or write ** transaction. Return LSM_MISUSE if an application attempts this. */ if( pDb->nTransOpen || pDb->pCsr ) return LSM_MISUSE_BKPT; | > > > > < < | > | > | | | | | | > > > | | | > | > > > > > > | > > > | | | | < < < < | 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 | } /* ** Perform work to merge database segments together. */ int lsm_work(lsm_db *pDb, int flags, int nPage, int *pnWrite){ int rc = LSM_OK; /* Return code */ int nOvfl = 0; int bFlush = 0; int bFinishWork = 0; int nWrite = 0; /* This function may not be called if pDb has an open read or write ** transaction. Return LSM_MISUSE if an application attempts this. */ if( pDb->nTransOpen || pDb->pCsr ) return LSM_MISUSE_BKPT; if( (flags & LSM_WORK_FLUSH) && (flags & LSM_WORK_OPTIMIZE) ){ rc = lsmBeginWriteTrans(pDb); if( rc==LSM_OK ){ int nDummy; lsmTreeMakeOld(pDb, &nDummy); lsmFinishWriteTrans(pDb, 1); lsmFinishReadTrans(pDb); } if( rc==LSM_BUSY ) rc = LSM_OK; } assert( pDb->pWorker==0 ); if( (flags & LSM_WORK_FLUSH) || nPage>0 ){ rc = lsmBeginWork(pDb); bFinishWork = 1; } /* If the FLUSH flag is set, try to flush the contents of the in-memory ** tree to disk. */ if( rc==LSM_OK && ((flags & LSM_WORK_FLUSH)) ){ rc = lsmTreeLoadHeader(pDb, 0); if( rc==LSM_OK && pDb->treehdr.iOldShmid ){ rc = lsmSortedFlushTree(pDb, &nOvfl); bFlush = 1; } } /* If nPage is greater than zero, do some merging. */ if( rc==LSM_OK && nPage>0 ){ int bOptimize = ((flags & LSM_WORK_OPTIMIZE) ? 1 : 0); rc = sortedWork(pDb, nPage, bOptimize, &nWrite); if( rc==LSM_OK && nWrite ){ rc = lsmSortedFlushDb(pDb); if( rc==LSM_OK && lsmCheckpointOverflowRequired(pDb) ){ nOvfl = -1; rc = sortedNewToplevel(pDb, 0, &nOvfl); } } } if( pnWrite ) *pnWrite = nWrite; if( bFinishWork ){ if( nWrite || bFlush ){ lsmFinishWork(pDb, bFlush, nOvfl, &rc); }else{ int rcdummy = LSM_BUSY; lsmFinishWork(pDb, 0, 0, &rcdummy); } } assert( pDb->pWorker==0 ); /* If the LSM_WORK_CHECKPOINT flag is specified and one is available, ** write a checkpoint out to disk. */ if( rc==LSM_OK && (flags & LSM_WORK_CHECKPOINT) ){ rc = lsmCheckpointWrite(pDb); } |
︙ | ︙ | |||
4514 4515 4516 4517 4518 4519 4520 | return LSM_OK; } void lsmSortedSaveTreeCursors(lsm_db *pDb){ MultiCursor *pCsr; for(pCsr=pDb->pCsr; pCsr; pCsr=pCsr->pNext){ | | > | 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 | return LSM_OK; } void lsmSortedSaveTreeCursors(lsm_db *pDb){ MultiCursor *pCsr; for(pCsr=pDb->pCsr; pCsr; pCsr=pCsr->pNext){ lsmTreeCursorSave(pCsr->apTreeCsr[0]); lsmTreeCursorSave(pCsr->apTreeCsr[1]); } } #ifdef LSM_DEBUG_EXPENSIVE /* ** This function is only included in the build if LSM_DEBUG_EXPENSIVE is ** defined. Its only purpose is to evaluate various assert() statements to |
︙ | ︙ |
Changes to src/lsm_tree.c.
︙ | ︙ | |||
90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #define MAX_DEPTH 32 typedef struct TreeKey TreeKey; typedef struct TreeNode TreeNode; typedef struct TreeLeaf TreeLeaf; typedef struct NodeVersion NodeVersion; /* ** Container for a key-value pair. Within the *-shm file, each key/value ** pair is stored in a single allocation (which may not actually be ** contiguous in memory). Layout is the TreeKey structure, followed by ** the nKey bytes of key blob, followed by the nValue bytes of value blob ** (if nValue is non-negative). */ | > > > > > > | 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #define MAX_DEPTH 32 typedef struct TreeKey TreeKey; typedef struct TreeNode TreeNode; typedef struct TreeLeaf TreeLeaf; typedef struct NodeVersion NodeVersion; struct TreeOld { u32 iShmid; /* Last shared-memory chunk in use by old */ u32 iRoot; /* Offset of root node in shm file */ u32 nHeight; /* Height of tree structure */ }; /* ** Container for a key-value pair. Within the *-shm file, each key/value ** pair is stored in a single allocation (which may not actually be ** contiguous in memory). Layout is the TreeKey structure, followed by ** the nKey bytes of key blob, followed by the nValue bytes of value blob ** (if nValue is non-negative). */ |
︙ | ︙ | |||
148 149 150 151 152 153 154 155 156 157 158 159 160 161 | ** Entries in the apTreeNode[] and aiCell[] arrays contain the node and ** index of the TreeNode.apChild[] pointer followed to descend to the ** current element. Hence apTreeNode[0] always contains the root node of ** the tree. */ struct TreeCursor { lsm_db *pDb; /* Database handle for this cursor */ int iNode; /* Cursor points at apTreeNode[iNode] */ TreeNode *apTreeNode[MAX_DEPTH];/* Current position in tree */ u8 aiCell[MAX_DEPTH]; /* Current position in tree */ TreeKey *pSave; /* Saved key */ TreeBlob blob; /* Dynamic storage for a key */ }; | > | 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 | ** Entries in the apTreeNode[] and aiCell[] arrays contain the node and ** index of the TreeNode.apChild[] pointer followed to descend to the ** current element. Hence apTreeNode[0] always contains the root node of ** the tree. */ struct TreeCursor { lsm_db *pDb; /* Database handle for this cursor */ TreeRoot *pRoot; /* Root node and height of tree to access */ int iNode; /* Cursor points at apTreeNode[iNode] */ TreeNode *apTreeNode[MAX_DEPTH];/* Current position in tree */ u8 aiCell[MAX_DEPTH]; /* Current position in tree */ TreeKey *pSave; /* Saved key */ TreeBlob blob; /* Dynamic storage for a key */ }; |
︙ | ︙ | |||
352 353 354 355 356 357 358 | /* ** Run various assert() statements to check that the working-version of the ** tree is correct in the following respects: ** ** * todo... */ void assert_tree_looks_ok(int rc, Tree *pTree){ | < < < < < < < | 359 360 361 362 363 364 365 366 367 368 369 370 371 372 | /* ** Run various assert() statements to check that the working-version of the ** tree is correct in the following respects: ** ** * todo... */ void assert_tree_looks_ok(int rc, Tree *pTree){ } #else # define assert_tree_looks_ok(x,y) #endif #ifdef LSM_DEBUG |
︙ | ︙ | |||
430 431 432 433 434 435 436 | } } printf("%s\n", s.z); lsmStringClear(&s); for(i=0; i<4 && nHeight>0; i++){ | | > | | | > > > > > | | 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 | } } printf("%s\n", s.z); lsmStringClear(&s); for(i=0; i<4 && nHeight>0; i++){ u32 iPtr = getChildPtr(pNode, pDb->treehdr.root.iTransId, i); if( iPtr ){ dump_node_contents(pDb, iPtr, nIndent + 2, nHeight-1); } } tblobFree(pDb, &b); } void dump_tree_contents(lsm_db *pDb, const char *zCaption){ TreeRoot *p = &pDb->treehdr.root; printf("\n%s\n", zCaption); if( p->iRoot ){ dump_node_contents(pDb, p->iRoot, 0, p->nHeight-1); } fflush(stdout); } #endif /* ** Initialize a cursor object, the space for which has already been ** allocated. */ static void treeCursorInit(lsm_db *pDb, int bOld, TreeCursor *pCsr){ memset(pCsr, 0, sizeof(TreeCursor)); pCsr->pDb = pDb; if( bOld ){ pCsr->pRoot = &pDb->treehdr.oldroot; }else{ pCsr->pRoot = &pDb->treehdr.root; } pCsr->iNode = -1; } /* ** Return a pointer to the mapping of the TreeKey object that the cursor ** is pointing to. */ static TreeKey *csrGetKey(TreeCursor *pCsr, TreeBlob *pBlob, int *pRc){ return (TreeKey *)treeShmkey(pCsr->pDb, pCsr->apTreeNode[pCsr->iNode]->aiKeyPtr[pCsr->aiCell[pCsr->iNode]], TK_LOADVAL, pBlob, pRc ); } /* ** Save the current position of tree cursor pCsr. */ int lsmTreeCursorSave(TreeCursor *pCsr){ int rc = LSM_OK; if( pCsr && pCsr->pSave==0 ){ int iNode = pCsr->iNode; if( iNode>=0 ){ pCsr->pSave = csrGetKey(pCsr, &pCsr->blob, &rc); } pCsr->iNode = -1; } return rc; |
︙ | ︙ | |||
622 623 624 625 626 627 628 | ){ TreeKey *p; u32 iPtr; int nRem; u8 *a; int n; | < < < < < < < < < < < < | 628 629 630 631 632 633 634 635 636 637 638 639 640 641 | ){ TreeKey *p; u32 iPtr; int nRem; u8 *a; int n; /* Allocate space for the TreeKey structure itself */ *piPtr = iPtr = treeShmalloc(pDb, 1, sizeof(TreeKey), pRc); p = treeShmptr(pDb, iPtr, pRc); if( *pRc ) return 0; p->nKey = nKey; p->nValue = nVal; |
︙ | ︙ | |||
716 717 718 719 720 721 722 | ** internal node, or by allocating a new TreeNode structure and then ** calling this function on the parent of the internal node. */ static int treeUpdatePtr(lsm_db *pDb, TreeCursor *pCsr, u32 iNew){ int rc = LSM_OK; if( pCsr->iNode<0 ){ /* iNew is the new root node */ | | | 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 | ** internal node, or by allocating a new TreeNode structure and then ** calling this function on the parent of the internal node. */ static int treeUpdatePtr(lsm_db *pDb, TreeCursor *pCsr, u32 iNew){ int rc = LSM_OK; if( pCsr->iNode<0 ){ /* iNew is the new root node */ pDb->treehdr.root.iRoot = iNew; }else{ /* If this node already has version 2 content, allocate a copy and ** update the copy with the new pointer value. Otherwise, store the ** new pointer as v2 data within the current node structure. */ TreeNode *p; /* The node to be modified */ int iChildPtr; /* apChild[] entry to modify */ |
︙ | ︙ | |||
742 743 744 745 746 747 748 | pCopy->aiChildPtr[iChildPtr] = iNew; pCsr->iNode--; rc = treeUpdatePtr(pDb, pCsr, iCopy); } }else{ /* The "v2 data" option */ u32 iPtr; | | | | | | 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 | pCopy->aiChildPtr[iChildPtr] = iNew; pCsr->iNode--; rc = treeUpdatePtr(pDb, pCsr, iCopy); } }else{ /* The "v2 data" option */ u32 iPtr; assert( pDb->treehdr.root.iTransId>0 ); if( pCsr->iNode ){ iPtr = getChildPtr( pCsr->apTreeNode[pCsr->iNode-1], pDb->treehdr.root.iTransId, pCsr->aiCell[pCsr->iNode-1] ); }else{ iPtr = pDb->treehdr.root.iRoot; } rc = intArrayAppend(pDb->pEnv, &pDb->rollback, iPtr); if( rc==LSM_OK ){ p->iV2 = pDb->treehdr.root.iTransId; p->iV2Child = (u8)iChildPtr; p->iV2Ptr = iNew; } } } return rc; |
︙ | ︙ | |||
817 818 819 820 821 822 823 | u32 iRoot; TreeNode *pRoot; /* New root node */ pRoot = newTreeNode(pDb, &iRoot, &rc); pRoot->aiKeyPtr[1] = pNode->aiKeyPtr[1]; pRoot->aiChildPtr[1] = iLeft; pRoot->aiChildPtr[2] = iRight; | | | | 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 | u32 iRoot; TreeNode *pRoot; /* New root node */ pRoot = newTreeNode(pDb, &iRoot, &rc); pRoot->aiKeyPtr[1] = pNode->aiKeyPtr[1]; pRoot->aiChildPtr[1] = iLeft; pRoot->aiChildPtr[2] = iRight; pDb->treehdr.root.iRoot = iRoot; pDb->treehdr.root.nHeight++; }else{ pCsr->iNode--; rc = treeInsert(pDb, pCsr, iLeft, pNode->aiKeyPtr[1], iRight, pCsr->aiCell[pCsr->iNode] ); } |
︙ | ︙ | |||
959 960 961 962 963 964 965 | return rc; } /* ** Empty the contents of the in-memory tree. */ void lsmTreeClear(lsm_db *pDb){ | > > > | > > > > > > > > > > > > > > > | | | > > > > > > > | > > > > > | | 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 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 | return rc; } /* ** Empty the contents of the in-memory tree. */ void lsmTreeClear(lsm_db *pDb){ pDb->treehdr.root.iTransId = 1; pDb->treehdr.root.iRoot = 0; pDb->treehdr.root.nHeight = 0; pDb->treehdr.nByte = 0; pDb->treehdr.iUsedShmid = pDb->treehdr.iNextShmid-1; } void lsmTreeMakeOld(lsm_db *pDb, int *pnFlush){ if( pDb->treehdr.iOldShmid ){ *pnFlush = 2; }else{ *pnFlush = 1; pDb->treehdr.iOldLog = pDb->treehdr.log.aRegion[2].iEnd; pDb->treehdr.oldcksum0 = pDb->treehdr.log.cksum0; pDb->treehdr.oldcksum1 = pDb->treehdr.log.cksum1; pDb->treehdr.iOldShmid = pDb->treehdr.iNextShmid-1; memcpy(&pDb->treehdr.oldroot, &pDb->treehdr.root, sizeof(TreeRoot)); pDb->treehdr.root.iTransId = 1; pDb->treehdr.root.iRoot = 0; pDb->treehdr.root.nHeight = 0; pDb->treehdr.nByte = 0; } } void lsmTreeDiscardOld(lsm_db *pDb){ assert( lsmShmAssertLock(pDb, LSM_LOCK_WRITER, LSM_LOCK_EXCL) || lsmShmAssertLock(pDb, LSM_LOCK_DMS2, LSM_LOCK_EXCL) ); pDb->treehdr.iUsedShmid = pDb->treehdr.iOldShmid; pDb->treehdr.iOldShmid = 0; } int lsmTreeHasOld(lsm_db *pDb){ return pDb->treehdr.iOldShmid!=0; } /* ** This function is called during recovery to initialize the ** tree header. Only the database connections private copy of the tree-header ** is initialized here - it will be copied into shared memory if log file ** recovery is successful. */ int lsmTreeInit(lsm_db *pDb){ ShmChunk *pOne; int rc = LSM_OK; pDb->treehdr.root.iTransId = 1; pDb->treehdr.iFirst = 1; pDb->treehdr.nChunk = 2; pDb->treehdr.iWrite = LSM_SHM_CHUNK_SIZE + LSM_SHM_CHUNK_HDR; pDb->treehdr.iNextShmid = 2; pDb->treehdr.iUsedShmid = 1; pOne = treeShmChunkRc(pDb, 1, &rc); |
︙ | ︙ | |||
1080 1081 1082 1083 1084 1085 1086 | /* ** Iterate through the current in-memory tree. If there are any v2-pointers ** with transaction ids larger than db->treehdr.iTransId, zero them. */ static int treeRepairPtrs(lsm_db *db){ int rc = LSM_OK; | | | | | | | 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 | /* ** Iterate through the current in-memory tree. If there are any v2-pointers ** with transaction ids larger than db->treehdr.iTransId, zero them. */ static int treeRepairPtrs(lsm_db *db){ int rc = LSM_OK; if( db->treehdr.root.nHeight>1 ){ TreeCursor csr; /* Cursor used to iterate through tree */ u32 iTransId = db->treehdr.root.iTransId; /* Initialize the cursor structure. Also decrement the nHeight variable ** in the tree-header. This will prevent the cursor from visiting any ** leaf nodes. */ db->treehdr.root.nHeight--; treeCursorInit(db, 0, &csr); rc = lsmTreeCursorEnd(&csr, 0); while( rc==LSM_OK && lsmTreeCursorValid(&csr) ){ TreeNode *pNode = csr.apTreeNode[csr.iNode]; if( pNode->iV2>iTransId ){ pNode->iV2Child = 0; pNode->iV2Ptr = 0; pNode->iV2 = 0; } rc = lsmTreeCursorNext(&csr); } tblobFree(csr.pDb, &csr.blob); db->treehdr.root.nHeight++; } return rc; } static int treeRepairList(lsm_db *db){ int rc = LSM_OK; |
︙ | ︙ | |||
1239 1240 1241 1242 1243 1244 1245 | int nKey, /* Size of key data in bytes */ void *pVal, /* Pointer to value data (or NULL) */ int nVal /* Bytes in value data (or -ve for delete) */ ){ int rc = LSM_OK; /* Return Code */ TreeKey *pTreeKey; /* New key-value being inserted */ u32 iTreeKey; | | | | | | | | | 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 | int nKey, /* Size of key data in bytes */ void *pVal, /* Pointer to value data (or NULL) */ int nVal /* Bytes in value data (or -ve for delete) */ ){ int rc = LSM_OK; /* Return Code */ TreeKey *pTreeKey; /* New key-value being inserted */ u32 iTreeKey; TreeRoot *p = &pDb->treehdr.root; assert( nVal>=0 || pVal==0 ); assert_tree_looks_ok(LSM_OK, pTree); #if 0 dump_tree_contents(pDb, "before"); #endif /* Allocate and populate a new key-value pair structure */ pTreeKey = newTreeKey(pDb, &iTreeKey, pKey, nKey, pVal, nVal, &rc); if( rc!=LSM_OK ) return rc; if( p->iRoot==0 ){ /* The tree is completely empty. Add a new root node and install ** (pKey/nKey) as the middle entry. Even though it is a leaf at the ** moment, use newTreeNode() to allocate the node (i.e. allocate enough ** space for the fields used by interior nodes). This is because the ** treeInsert() routine may convert this node to an interior node. */ TreeNode *pRoot = newTreeNode(pDb, &p->iRoot, &rc); if( rc==LSM_OK ){ assert( p->nHeight==0 ); pRoot->aiKeyPtr[1] = iTreeKey; p->nHeight = 1; } }else{ TreeCursor csr; int res; /* Seek to the leaf (or internal node) that the new key belongs on */ treeCursorInit(pDb, 0, &csr); lsmTreeCursorSeek(&csr, pKey, nKey, &res); if( res==0 ){ /* The search found a match within the tree. */ TreeNode *pNew; u32 iNew; TreeNode *pNode = csr.apTreeNode[csr.iNode]; int iCell = csr.aiCell[csr.iNode]; /* Create a copy of this node */ if( (csr.iNode>0 && csr.iNode==(p->nHeight-1)) ){ pNew = copyTreeLeaf(pDb, (TreeLeaf *)pNode, &iNew, &rc); }else{ pNew = copyTreeNode(pDb, pNode, &iNew, &rc); } if( rc==LSM_OK ){ /* Modify the value in the new version */ |
︙ | ︙ | |||
1332 1333 1334 1335 1336 1337 1338 | int lsmTreeSize(lsm_db *pDb){ return pDb->treehdr.nByte; } /* ** Open a cursor on the in-memory tree pTree. */ | | | > | | > | 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 | int lsmTreeSize(lsm_db *pDb){ return pDb->treehdr.nByte; } /* ** Open a cursor on the in-memory tree pTree. */ int lsmTreeCursorNew(lsm_db *pDb, int bOld, TreeCursor **ppCsr){ TreeCursor *pCsr; *ppCsr = pCsr = lsmMalloc(pDb->pEnv, sizeof(TreeCursor)); if( pCsr ){ treeCursorInit(pDb, bOld, pCsr); return LSM_OK; } return LSM_NOMEM_BKPT; } /* ** Close an in-memory tree cursor. */ void lsmTreeCursorDestroy(TreeCursor *pCsr){ if( pCsr ){ tblobFree(pCsr->pDb, &pCsr->blob); lsmFree(pCsr->pDb->pEnv, pCsr); } } void lsmTreeCursorReset(TreeCursor *pCsr){ if( pCsr ){ pCsr->iNode = -1; pCsr->pSave = 0; } } #ifndef NDEBUG static int treeCsrCompare(TreeCursor *pCsr, void *pKey, int nKey){ TreeKey *p; int cmp = 0; int rc = LSM_OK; |
︙ | ︙ | |||
1389 1390 1391 1392 1393 1394 1395 | ** is smaller than the key and set *pRes to -1, or ** ** * If the tree is empty, leave the cursor at EOF and set *pRes to -1. */ int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes){ int rc = LSM_OK; /* Return code */ lsm_db *pDb = pCsr->pDb; | | | | | 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 | ** is smaller than the key and set *pRes to -1, or ** ** * If the tree is empty, leave the cursor at EOF and set *pRes to -1. */ int lsmTreeCursorSeek(TreeCursor *pCsr, void *pKey, int nKey, int *pRes){ int rc = LSM_OK; /* Return code */ lsm_db *pDb = pCsr->pDb; TreeRoot *pRoot = pCsr->pRoot; int (*xCmp)(void *, int, void *, int) = pDb->xCmp; u32 iNodePtr; /* Location of current node in search */ /* Discard any saved position data */ treeCursorRestore(pCsr, 0); iNodePtr = pRoot->iRoot; if( iNodePtr==0 ){ /* Either an error occurred or the tree is completely empty. */ assert( rc!=LSM_OK || pRoot->iRoot==0 ); *pRes = -1; pCsr->iNode = -1; }else{ TreeBlob b = {0, 0}; int res = 0; /* Result of comparison function */ int iNode = -1; while( iNodePtr ){ |
︙ | ︙ | |||
1443 1444 1445 1446 1447 1448 1449 | res = xCmp((void *)&pTreeKey[1], pTreeKey->nKey, pKey, nKey); if( res==0 ){ pCsr->aiCell[iNode] = iTest; break; } } | | | | 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 | res = xCmp((void *)&pTreeKey[1], pTreeKey->nKey, pKey, nKey); if( res==0 ){ pCsr->aiCell[iNode] = iTest; break; } } if( iNode<(pRoot->nHeight-1) ){ iNodePtr = getChildPtr(pNode, pRoot->iTransId, iTest + (res<0)); }else{ iNodePtr = 0; } pCsr->aiCell[iNode] = iTest + (iNodePtr && (res<0)); } *pRes = res; |
︙ | ︙ | |||
1473 1474 1475 1476 1477 1478 1479 | int lsmTreeCursorNext(TreeCursor *pCsr){ #ifndef NDEBUG TreeKey *pK1; TreeBlob key1 = {0, 0}; #endif lsm_db *pDb = pCsr->pDb; | > | | 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 | int lsmTreeCursorNext(TreeCursor *pCsr){ #ifndef NDEBUG TreeKey *pK1; TreeBlob key1 = {0, 0}; #endif lsm_db *pDb = pCsr->pDb; TreeRoot *pRoot = pCsr->pRoot; const int iLeaf = pRoot->nHeight-1; int iCell; int rc = LSM_OK; TreeNode *pNode; /* Restore the cursor position, if required */ int iRestore = 0; treeCursorRestore(pCsr, &iRestore); |
︙ | ︙ | |||
1500 1501 1502 1503 1504 1505 1506 | pNode = pCsr->apTreeNode[pCsr->iNode]; iCell = ++pCsr->aiCell[pCsr->iNode]; /* If the current node is not a leaf, and the current cell has sub-tree ** associated with it, descend to the left-most key on the left-most ** leaf of the sub-tree. */ | | | | 1527 1528 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 | pNode = pCsr->apTreeNode[pCsr->iNode]; iCell = ++pCsr->aiCell[pCsr->iNode]; /* If the current node is not a leaf, and the current cell has sub-tree ** associated with it, descend to the left-most key on the left-most ** leaf of the sub-tree. */ if( pCsr->iNode<iLeaf && getChildPtr(pNode, pRoot->iTransId, iCell) ){ do { u32 iNodePtr; pCsr->iNode++; iNodePtr = getChildPtr(pNode, pRoot->iTransId, iCell); pNode = (TreeNode *)treeShmptr(pDb, iNodePtr, &rc); pCsr->apTreeNode[pCsr->iNode] = pNode; iCell = pCsr->aiCell[pCsr->iNode] = (pNode->aiKeyPtr[0]==0); }while( pCsr->iNode < iLeaf ); } /* Otherwise, the next key is found by following pointer up the tree |
︙ | ︙ | |||
1538 1539 1540 1541 1542 1543 1544 | int lsmTreeCursorPrev(TreeCursor *pCsr){ #ifndef NDEBUG TreeKey *pK1; TreeBlob key1 = {0, 0}; #endif lsm_db *pDb = pCsr->pDb; | > | | 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 | int lsmTreeCursorPrev(TreeCursor *pCsr){ #ifndef NDEBUG TreeKey *pK1; TreeBlob key1 = {0, 0}; #endif lsm_db *pDb = pCsr->pDb; TreeRoot *pRoot = pCsr->pRoot; const int iLeaf = pRoot->nHeight-1; int iCell; int rc = LSM_OK; TreeNode *pNode; /* Restore the cursor position, if required */ int iRestore = 0; treeCursorRestore(pCsr, &iRestore); |
︙ | ︙ | |||
1564 1565 1566 1567 1568 1569 1570 | pNode = pCsr->apTreeNode[pCsr->iNode]; iCell = pCsr->aiCell[pCsr->iNode]; assert( iCell>=0 && iCell<3 ); /* If the current node is not a leaf, and the current cell has sub-tree ** associated with it, descend to the right-most key on the right-most ** leaf of the sub-tree. */ | | | | 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 | pNode = pCsr->apTreeNode[pCsr->iNode]; iCell = pCsr->aiCell[pCsr->iNode]; assert( iCell>=0 && iCell<3 ); /* If the current node is not a leaf, and the current cell has sub-tree ** associated with it, descend to the right-most key on the right-most ** leaf of the sub-tree. */ if( pCsr->iNode<iLeaf && getChildPtr(pNode, pRoot->iTransId, iCell) ){ do { u32 iNodePtr; pCsr->iNode++; iNodePtr = getChildPtr(pNode, pRoot->iTransId, iCell); pNode = (TreeNode *)treeShmptr(pDb, iNodePtr, &rc); if( rc!=LSM_OK ) break; pCsr->apTreeNode[pCsr->iNode] = pNode; iCell = 1 + (pNode->aiKeyPtr[2]!=0) + (pCsr->iNode < iLeaf); pCsr->aiCell[pCsr->iNode] = iCell; }while( pCsr->iNode < iLeaf ); } |
︙ | ︙ | |||
1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 | /* ** Move the cursor to the first (bLast==0) or last (bLast!=0) entry in the ** in-memory tree. */ int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast){ lsm_db *pDb = pCsr->pDb; TreeHeader *pHdr = &pDb->treehdr; int rc = LSM_OK; u32 iNodePtr; pCsr->iNode = -1; /* Discard any saved position data */ treeCursorRestore(pCsr, 0); | > | | | | 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 | /* ** Move the cursor to the first (bLast==0) or last (bLast!=0) entry in the ** in-memory tree. */ int lsmTreeCursorEnd(TreeCursor *pCsr, int bLast){ lsm_db *pDb = pCsr->pDb; TreeHeader *pHdr = &pDb->treehdr; TreeRoot *pRoot = pCsr->pRoot; int rc = LSM_OK; u32 iNodePtr; pCsr->iNode = -1; /* Discard any saved position data */ treeCursorRestore(pCsr, 0); iNodePtr = pRoot->iRoot; while( iNodePtr ){ int iCell; TreeNode *pNode; pNode = (TreeNode *)treeShmptr(pDb, iNodePtr, &rc); if( rc ) break; if( bLast ){ iCell = ((pNode->aiKeyPtr[2]==0) ? 2 : 3); }else{ iCell = ((pNode->aiKeyPtr[0]==0) ? 1 : 0); } pCsr->iNode++; pCsr->apTreeNode[pCsr->iNode] = pNode; if( pCsr->iNode<pRoot->nHeight-1 ){ iNodePtr = getChildPtr(pNode, pRoot->iTransId, iCell); }else{ iNodePtr = 0; } pCsr->aiCell[pCsr->iNode] = iCell - (iNodePtr==0 && bLast); } return rc; |
︙ | ︙ | |||
1695 1696 1697 1698 1699 1700 1701 | /* ** Store a mark in *pMark. Later on, a call to lsmTreeRollback() with a ** pointer to the same TreeMark structure may be used to roll the tree ** contents back to their current state. */ void lsmTreeMark(lsm_db *pDb, TreeMark *pMark){ | | | | 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 | /* ** Store a mark in *pMark. Later on, a call to lsmTreeRollback() with a ** pointer to the same TreeMark structure may be used to roll the tree ** contents back to their current state. */ void lsmTreeMark(lsm_db *pDb, TreeMark *pMark){ pMark->iRoot = pDb->treehdr.root.iRoot; pMark->nHeight = pDb->treehdr.root.nHeight; pMark->iWrite = pDb->treehdr.iWrite; pMark->nChunk = pDb->treehdr.nChunk; pMark->iNextShmid = pDb->treehdr.iNextShmid; pMark->iRollback = intArraySize(&pDb->rollback); } /* |
︙ | ︙ | |||
1753 1754 1755 1756 1757 1758 1759 | pFree->iNext = pDb->treehdr.iFirst; pFree->iShmid = iShmid--; pDb->treehdr.iFirst = iFree; } } /* Restore the tree-header fields */ | | | | 1782 1783 1784 1785 1786 1787 1788 1789 1790 1791 1792 1793 1794 1795 1796 1797 | pFree->iNext = pDb->treehdr.iFirst; pFree->iShmid = iShmid--; pDb->treehdr.iFirst = iFree; } } /* Restore the tree-header fields */ pDb->treehdr.root.iRoot = pMark->iRoot; pDb->treehdr.root.nHeight = pMark->nHeight; pDb->treehdr.iWrite = pMark->iWrite; pDb->treehdr.nChunk = pMark->nChunk; pDb->treehdr.iNextShmid = pMark->iNextShmid; } /* ** Load the in-memory tree header from shared-memory into pDb->treehdr. |
︙ | ︙ | |||
1814 1815 1816 1817 1818 1819 1820 | } pShm->bWriter = 0; intArrayFree(pDb->pEnv, &pDb->rollback); return LSM_OK; } | < < < < < < < < | 1843 1844 1845 1846 1847 1848 1849 | } pShm->bWriter = 0; intArrayFree(pDb->pEnv, &pDb->rollback); return LSM_OK; } |
Changes to tool/lsmperf.tcl.
︙ | ︙ | |||
148 149 150 151 152 153 154 | incr nShift [expr $nWrite/4] } append script "plot $plot1 $plot2 $plot3\n" append script $data1 append script $data2 append script $data3 | < | | < | 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 | incr nShift [expr $nWrite/4] } append script "plot $plot1 $plot2 $plot3\n" append script $data1 append script $data2 append script $data3 append script "pause -1\n" exec_gnuplot_script $script $zPng } do_write_test x.png 180 10000 10000 1000 { LSM "mmap=1 multi_proc=0 safety=1 threads=2 autowork=0" } |