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

Overview
Comment:Re-enable incremental recycling of blocks belonging to segments for which the b-tree hierarchy is still in use.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 41bf1ae58db7a67211e0f931a7ae2da84231ffe5
User & Date: dan 2012-11-01 05:00:11.730
Context
2012-11-01
15:16
Fix a bug preventing a modified snapshot of a "full" database from being written to shared-memory. check-in: 9d8943da66 user: dan tags: trunk
05:00
Re-enable incremental recycling of blocks belonging to segments for which the b-tree hierarchy is still in use. check-in: 41bf1ae58d user: dan tags: trunk
2012-10-31
19:30
Merge the freelist-rework branch with the trunk. check-in: 58f0d07a23 user: dan tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/lsm_ckpt.c.
︙︙
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70


71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

**     2. The checkpoint id LSW.
**     3. The number of integer values in the entire checkpoint, including 
**        the two checksum values.
**     4. The total number of blocks in the database.
**     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:
**
**     0. Age of the level.
**     1. The number of right-hand segments (nRight, possibly 0),
**     2. Segment record for left-hand segment (8 integers defined below),
**     3. Segment record for each right-hand segment (8 integers defined below),
**     4. If nRight>0, The number of segments involved in the merge
**     5. if nRight>0, Current nSkip value (see Merge structure defn.),
**     6. For each segment in the merge:
**        5a. Page number of next cell to read during merge (this field
**            is 64-bits - 2 integers)
**        5b. Cell number of next cell to read during merge
**     7. Page containing current split-key (64-bits - 2 integers).
**     8. Cell within page containing current split-key.
**     9. Current pointer value (64-bits - 2 integers).
**
**   The freelist. 


**
**     1. Number of free-list entries stored in checkpoint header.
**     2. For each entry:
**        2a. Block number of free block.
**        2b. MSW of associated checkpoint id.
**        2c. LSW of associated checkpoint id.
**
**   If the overflow flag is set, then extra free-list entries may be stored
**   in the FREELIST record. The FREELIST record contains 3 32-bit integers
**   per entry, in the same format as above (without the "number of entries"
**   field).
**
**   The checksum:
**
**     1. Checksum value 1.
**     2. Checksum value 2.
**
** In the above, a segment record consists of the following four 64-bit 








<












|

















|
>
>




|
|
<
<
<
<
<








32
33
34
35
36
37
38

39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77





78
79
80
81
82
83
84

**     2. The checkpoint id LSW.
**     3. The number of integer values in the entire checkpoint, including 
**        the two checksum values.
**     4. The total number of blocks in the database.
**     5. The block size.
**     6. The number of levels.
**     7. The nominal database page size.

**
**   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:
**
**     8 integers (4 * 64-bit page numbers). See ckptExportAppendlist().
**
**   For each level in the database, a level record. Formatted as follows:
**
**     0. Age of the level.
**     1. The number of right-hand segments (nRight, possibly 0),
**     2. Segment record for left-hand segment (8 integers defined below),
**     3. Segment record for each right-hand segment (8 integers defined below),
**     4. If nRight>0, The number of segments involved in the merge
**     5. if nRight>0, Current nSkip value (see Merge structure defn.),
**     6. For each segment in the merge:
**        5a. Page number of next cell to read during merge (this field
**            is 64-bits - 2 integers)
**        5b. Cell number of next cell to read during merge
**     7. Page containing current split-key (64-bits - 2 integers).
**     8. Cell within page containing current split-key.
**     9. Current pointer value (64-bits - 2 integers).
**
**   The in-memory freelist entries. Each entry is either an insert or a
**   delete. The in-memory freelist is to the free-block-list as the
**   in-memory tree is to the users database content.
**
**     1. Number of free-list entries stored in checkpoint header.
**     2. For each entry:
**        2a. Block number of free block.
**        2b. A 64-bit integer (MSW followed by LSW). -1 for a delete entry,
**            or the associated checkpoint id for an insert.





**
**   The checksum:
**
**     1. Checksum value 1.
**     2. Checksum value 2.
**
** In the above, a segment record consists of the following four 64-bit
︙︙
Changes to src/lsm_sorted.c.
︙︙
4163
4164
4165
4166
4167
4168
4169
4170
4171
4172
4173
4174
4175
4176
4177
4178
4179
4180
4181
4182





4183
4184
4185
4186
4187
4188

4189
4190
4191
4192
4193

4194
4195
4196
4197
4198
4199
4200

    }
    pCsr->flags |= CURSOR_NEXT_OK;
  }

  return rc;
}

/* TODO: Re-enable this!!! */
static int sortedBtreeGobble(
  lsm_db *pDb, 
  MultiCursor *pCsr, 
  int iGobble
){
  int rc = LSM_OK;
  if( rtTopic(pCsr->eType)==0 ){
    Segment *pSeg = pCsr->aPtr[iGobble].pSeg;
    Blob *p = &pCsr->key;
    Pgno *aPg;
    int nPg;






    assert( pSeg->iRoot>0 );
    aPg = lsmMallocZeroRc(pDb->pEnv, sizeof(Pgno)*32, &rc);
    if( rc==LSM_OK ){
      rc = seekInBtree(pCsr, pSeg, p->pData, p->nData, aPg, 0); 
    }


    for(nPg=0; aPg[nPg]; nPg++);

#if 0
    lsmFsGobble(pDb, pSeg, aPg, nPg);
#endif


    lsmFree(pDb->pEnv, aPg);
  }
  return rc;
}

/*








<

|
|
|




<



>
>
>
>
>



|


>
|
<
<
|
<
>








4163
4164
4165
4166
4167
4168
4169

4170
4171
4172
4173
4174
4175
4176
4177

4178
4179
4180
4181
4182
4183
4184
4185
4186
4187
4188
4189
4190
4191
4192
4193


4194

4195
4196
4197
4198
4199
4200
4201
4202

    }
    pCsr->flags |= CURSOR_NEXT_OK;
  }

  return rc;
}


static int sortedBtreeGobble(
  lsm_db *pDb,                    /* Worker connection */
  MultiCursor *pCsr,              /* Multi-cursor being used for a merge */
  int iGobble                     /* pCsr->aPtr[] entry to operate on */
){
  int rc = LSM_OK;
  if( rtTopic(pCsr->eType)==0 ){
    Segment *pSeg = pCsr->aPtr[iGobble].pSeg;

    Pgno *aPg;
    int nPg;

    /* Seek from the root of the b-tree to the segment leaf that may contain
    ** a key equal to the one multi-cursor currently points to. Record the
    ** page number of each b-tree page and the leaf. The segment may be
    ** gobbled up to (but not including) the first of these page numbers.
    */
    assert( pSeg->iRoot>0 );
    aPg = lsmMallocZeroRc(pDb->pEnv, sizeof(Pgno)*32, &rc);
    if( rc==LSM_OK ){
      rc = seekInBtree(pCsr, pSeg, pCsr->key.pData, pCsr->key.nData, aPg, 0); 
    }

    if( rc==LSM_OK ){
      for(nPg=0; aPg[nPg]; nPg++);


      lsmFsGobble(pDb, pSeg, aPg, nPg);

    }

    lsmFree(pDb->pEnv, aPg);
  }
  return rc;
}

/*
︙︙