1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
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
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
|
/*-
* Copyright (c) 2008-2012 WiredTiger, Inc.
* All rights reserved.
*
* See the file LICENSE for redistribution information.
*/
/*
* WiredTiger's block manager interface.
*/
#define WT_BM_MAX_ADDR_COOKIE 255 /* Maximum address cookie */
/*
* The file's description is written into the first 512B of the file, which
* means we can use an offset of 0 as an invalid offset.
*/
#define WT_BLOCK_DESC_SECTOR 512
#define WT_BLOCK_INVALID_OFFSET 0
/*
* The block allocator maintains two primary skiplists: first, the by-offset
* list linking WT_FREE elements and sorted by file offset (low-to-high):
* this list has an entry for every free chunk in the file. The second primary
* skiplist is the by-size list linking WT_SIZE elements and sorted by chunk
* size (low-to-high). This list has an entry for every free chunk size seen
* since the list was created.
* Additionally, each WT_SIZE element has a skiplist of its own, linking
* WT_FREE elements and sorted by file offset (low-to-high). This list has an
* entry for every free chunk in the file of a particular size.
* The trickiness is that each individual WT_FREE element appears on two
* skiplists. In order to minimize allocation calls, we allocate a single
* array of WT_FREE pointers at the end of the WT_FREE structure, for both
* skiplists, and store the depth of the skiplist in the WT_FREE structure.
* The skiplist entries for the offset skiplist start at WT_FREE.next[0] and
* the entries for the size skiplist start at WT_FREE.next[WT_FREE.depth].
*
* WT_FREE --
* Encapsulation of a free chunk of space.
*/
struct __wt_free {
off_t off; /* File offset */
off_t size; /* Size */
uint8_t depth; /* Skip list depth */
/*
* Variable-length array, sized by the number of skiplist elements.
* The first depth array entries are the offset skiplist elements,
* the second depth array entries are the size skiplist.
*/
WT_FREE *next[0]; /* Offset, size skiplists */
};
/*
* WT_SIZE --
* Encapsulation of a block size skiplist entry.
*/
struct __wt_size {
off_t size; /* Size */
uint8_t depth; /* Skip list depth */
WT_FREE *foff[WT_SKIP_MAXDEPTH]; /* Per-size offset skiplist */
/* Variable-length array, sized by the number of skiplist elements. */
WT_SIZE *next[0]; /* Size skiplist */
};
/*
* WT_FREE_FOREACH --
* Walk a block manager skiplist.
* WT_FREE_FOREACH_OFF --
* Walk a block manager skiplist where the WT_FREE.next entries are offset
* by the depth.
*/
#define WT_FREE_FOREACH(skip, head) \
for ((skip) = (head)[0]; \
(skip) != NULL; (skip) = (skip)->next[0])
#define WT_FREE_FOREACH_OFF(skip, head) \
for ((skip) = (head)[0]; \
(skip) != NULL; (skip) = (skip)->next[(skip)->depth])
/*
* WT_BLOCK --
* Encapsulation of the standard WiredTiger block manager.
*/
struct __wt_block {
const char *name; /* Name */
WT_FH *fh; /* Backing file handle */
uint64_t write_gen; /* Write generation */
uint32_t allocsize; /* Allocation size */
int checksum; /* If checksums configured */
WT_COMPRESSOR *compressor; /* Page compressor */
/* Freelist support */
WT_SPINLOCK freelist_lock; /* Lock to protect the freelist. */
uint64_t freelist_bytes; /* Freelist byte count */
uint32_t freelist_entries; /* Freelist entry count */
int freelist_dirty; /* Freelist has been modified */
/* Freelist offset/size skiplists */
WT_FREE *foff[WT_SKIP_MAXDEPTH];
WT_SIZE *fsize[WT_SKIP_MAXDEPTH];
off_t free_offset; /* Freelist file location */
uint32_t free_size;
uint32_t free_cksum;
/* Salvage support */
off_t slvg_off; /* Salvage file offset */
/* Verification support */
uint32_t frags; /* Total frags */
uint8_t *fragbits; /* Frag tracking bit list */
#define WT_BLOCK_OK 0x01 /* File successfully opened */
uint32_t flags;
};
/*
* WT_BLOCK_DESC --
* The file's description.
*/
struct __wt_block_desc {
#define WT_BLOCK_MAGIC 120897
uint32_t magic; /* 00-03: Magic number */
#define WT_BLOCK_MAJOR_VERSION 1
uint16_t majorv; /* 04-05: Major version */
#define WT_BLOCK_MINOR_VERSION 0
uint16_t minorv; /* 06-07: Minor version */
uint32_t cksum; /* 08-11: Description block checksum */
uint32_t unused; /* 12-15: Padding */
#define WT_BLOCK_FREELIST_MAGIC 071002
uint64_t free_offset; /* 16-23: Free list page offset */
uint32_t free_size; /* 24-27: Free list page length */
uint32_t free_cksum; /* 28-31: Free list page checksum */
/*
* We maintain page write-generations in the non-transactional case
* (where, instead of a transactional LSN, the value is a counter),
* as that's how salvage can determine the most recent page between
* pages overlapping the same key range. The value has to persist,
* so it's included in the file's metadata.
*/
uint64_t write_gen; /* 32-39: Write generation */
};
/*
* WT_BLOCK_DESC_SIZE is the expected structure size -- we verify the build to
* ensure the compiler hasn't inserted padding (padding won't cause failure,
* since we reserve the first sector of the file for this information, but it
* would be worth investigation, regardless).
*/
#define WT_BLOCK_DESC_SIZE 40
/*
* WT_BLOCK_HEADER --
* Blocks have a common header, a WT_PAGE_HEADER structure followed by a
* block-manager specific structure: WT_BLOCK_HEADER is WiredTiger's default.
*/
struct __wt_block_header {
/*
* We maintain page write-generations in the non-transactional case
* (where, instead of a transactional LSN, the value is a counter),
* as that's how salvage can determine the most recent page between
* pages overlapping the same key range.
*
* !!!
* The write-generation is "owned" by the btree layer, but it's easier
* to set it (when physically writing blocks), to persist it (in the
* WT_BLOCK_DESC structure, rather than the schema file), and restore
* it during salvage, in the block-manager layer.
*/
uint64_t write_gen; /* 00-07: write generation */
/*
* We write the page size in the on-disk page header because it makes
* salvage easier. (If we don't know the expected page length, we'd
* have to read increasingly larger chunks from the file until we find
* one that checksums, and that's going to be harsh given WiredTiger's
* potentially large page sizes.)
*/
uint32_t disk_size; /* 08-11: on-disk page size */
/*
* Page checksums are stored in two places. First, a page's checksum
* is in the internal page that references a page as part of the
* address cookie. This is done to improve the chances that we detect
* corruption (e.g., overwriting a page with another valid page image).
* Second, a page's checksum is stored in the disk header. This is for
* salvage, so that salvage knows when it has found a page that may be
* useful.
*
* Applications can turn off checksums, which is a promise that the
* file can never become corrupted, but people sometimes make promises
* they can't keep. If no checksums are configured, we use a pattern
* of alternating bits as the checksum, as that is unlikely to occur as
* the result of corruption in the file. If a page happens to checksum
* to this special bit pattern, we bump it by one during reads and
* writes to avoid ambiguity.
*/
#define WT_BLOCK_CHECKSUM_NOT_SET 0xA5C35A3C
uint32_t cksum; /* 12-15: checksum */
};
/*
* WT_BLOCK_HEADER_SIZE is the number of bytes we allocate for the structure: if
* the compiler inserts padding it will break the world.
*/
#define WT_BLOCK_HEADER_SIZE 16
/*
* WT_BLOCK_HEADER_BYTE
* WT_BLOCK_HEADER_BYTE_SIZE --
* The first usable data byte on the block (past the combined headers).
*/
#define WT_BLOCK_HEADER_BYTE_SIZE \
(WT_PAGE_HEADER_SIZE + WT_BLOCK_HEADER_SIZE)
#define WT_BLOCK_HEADER_BYTE(dsk) \
((void *)((uint8_t *)(dsk) + WT_BLOCK_HEADER_BYTE_SIZE))
/*
* Don't compress the block's WT_PAGE_HEADER and WT_BLOCK_HEADER structures.
* We need the WT_PAGE_HEADER in-memory size, and the WT_BLOCK_HEADER checksum
* and on-disk size to be immediately available without decompression. We use
* the on-disk size and checksum during salvage to figure out where the blocks
* are, and the in-memory size tells us how large a buffer we need to decompress
* the block. We could skip less than 64B, but a 64B boundary may offer better
* alignment for the underlying compression engine, and skipping 64B won't make
* a difference in terms of compression efficiency.
*/
#define WT_BLOCK_COMPRESS_SKIP 64
|
