1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#pragma once
40
41#include <db.h>
42
43#include "portability/toku_stdint.h"
44#include "portability/toku_pthread.h"
45
46#include "ft/serialize/block_allocator.h"
47#include "util/nb_mutex.h"
48
49struct ft;
50
51typedef struct blocknum_s { int64_t b; } BLOCKNUM;
52
53// Offset in a disk. -1 is the 'null' pointer.
54typedef int64_t DISKOFF;
55
56// Unmovable reserved first, then reallocable.
57// We reserve one blocknum for the translation table itself.
58enum {
59 RESERVED_BLOCKNUM_NULL = 0,
60 RESERVED_BLOCKNUM_TRANSLATION = 1,
61 RESERVED_BLOCKNUM_DESCRIPTOR = 2,
62 RESERVED_BLOCKNUMS
63};
64
65typedef int (*BLOCKTABLE_CALLBACK)(BLOCKNUM b,
66 int64_t size,
67 int64_t address,
68 void *extra);
69
70static inline BLOCKNUM make_blocknum(int64_t b) {
71 BLOCKNUM result = {.b = b};
72 return result;
73}
74static const BLOCKNUM ROLLBACK_NONE = {.b = 0};
75
76/**
77 * There are three copies of the translation table (btt) in the block table:
78 *
79 * checkpointed Is initialized by deserializing from disk,
80 * and is the only version ever read from disk.
81 * When read from disk it is copied to current.
82 * It is immutable. It can be replaced by an inprogress btt.
83 *
84 * inprogress Is only filled by copying from current,
85 * and is the only version ever serialized to disk.
86 * (It is serialized to disk on checkpoint and clean
87 *shutdown.)
88 * At end of checkpoint it replaces 'checkpointed'.
89 * During a checkpoint, any 'pending' dirty writes will update
90 * inprogress.
91 *
92 * current Is initialized by copying from checkpointed,
93 * is the only version ever modified while the database is in
94 *use,
95 * and is the only version ever copied to inprogress.
96 * It is never stored on disk.
97 */
98class block_table {
99 public:
100 enum translation_type {
101 TRANSLATION_NONE = 0,
102 TRANSLATION_CURRENT,
103 TRANSLATION_INPROGRESS,
104 TRANSLATION_CHECKPOINTED,
105 TRANSLATION_DEBUG
106 };
107
108 void create();
109
110 int create_from_buffer(int fd,
111 DISKOFF location_on_disk,
112 DISKOFF size_on_disk,
113 unsigned char *translation_buffer);
114
115 void destroy();
116
117 // Checkpointing
118 void note_start_checkpoint_unlocked();
119 void note_end_checkpoint(int fd);
120 void note_skipped_checkpoint();
121 void maybe_truncate_file_on_open(int fd);
122
123 // Blocknums
124 void allocate_blocknum(BLOCKNUM *res, struct ft *ft);
125 void realloc_on_disk(BLOCKNUM b,
126 DISKOFF size,
127 DISKOFF *offset,
128 struct ft *ft,
129 int fd,
130 bool for_checkpoint);
131 void free_blocknum(BLOCKNUM *b, struct ft *ft, bool for_checkpoint);
132 void translate_blocknum_to_offset_size(BLOCKNUM b,
133 DISKOFF *offset,
134 DISKOFF *size);
135 void free_unused_blocknums(BLOCKNUM root);
136 void realloc_descriptor_on_disk(DISKOFF size,
137 DISKOFF *offset,
138 struct ft *ft,
139 int fd);
140 void get_descriptor_offset_size(DISKOFF *offset, DISKOFF *size);
141
142 // External verfication
143 void verify_blocknum_allocated(BLOCKNUM b);
144 void verify_no_data_blocks_except_root(BLOCKNUM root);
145 void verify_no_free_blocknums();
146
147 // Serialization
148 void serialize_translation_to_wbuf(int fd,
149 struct wbuf *w,
150 int64_t *address,
151 int64_t *size);
152
153 // DEBUG ONLY (ftdump included), tests included
154 void blocknum_dump_translation(BLOCKNUM b);
155 void dump_translation_table_pretty(FILE *f);
156 void dump_translation_table(FILE *f);
157 void block_free(uint64_t offset, uint64_t size);
158
159 int iterate(enum translation_type type,
160 BLOCKTABLE_CALLBACK f,
161 void *extra,
162 bool data_only,
163 bool used_only);
164 void internal_fragmentation(int64_t *total_sizep, int64_t *used_sizep);
165
166 // Requires: blocktable lock is held.
167 // Requires: report->file_size_bytes is already filled in.
168 void get_fragmentation_unlocked(TOKU_DB_FRAGMENTATION report);
169
170 int64_t get_blocks_in_use_unlocked();
171
172 void get_info64(struct ftinfo64 *);
173
174 int iterate_translation_tables(
175 uint64_t,
176 int (*)(uint64_t, int64_t, int64_t, int64_t, int64_t, void *),
177 void *);
178
179 private:
180 struct block_translation_pair {
181 // If in the freelist, use next_free_blocknum, otherwise diskoff.
182 union {
183 DISKOFF diskoff;
184 BLOCKNUM next_free_blocknum;
185 } u;
186
187 // Set to 0xFFFFFFFFFFFFFFFF for free
188 DISKOFF size;
189 };
190
191 // This is the BTT (block translation table)
192 // When the translation (btt) is stored on disk:
193 // In Header:
194 // size_on_disk
195 // location_on_disk
196 // In block translation table (in order):
197 // smallest_never_used_blocknum
198 // blocknum_freelist_head
199 // array
200 // a checksum
201 struct translation {
202 enum translation_type type;
203
204 // Number of elements in array (block_translation). always >=
205 // smallest_never_used_blocknum
206 int64_t length_of_array;
207 BLOCKNUM smallest_never_used_blocknum;
208
209 // Next (previously used) unused blocknum (free list)
210 BLOCKNUM blocknum_freelist_head;
211 struct block_translation_pair *block_translation;
212
213 // size_on_disk is stored in
214 // block_translation[RESERVED_BLOCKNUM_TRANSLATION].size
215 // location_on is stored in
216 // block_translation[RESERVED_BLOCKNUM_TRANSLATION].u.diskoff
217 };
218
219 void _create_internal();
220 int _translation_deserialize_from_buffer(
221 struct translation *t, // destination into which to deserialize
222 DISKOFF location_on_disk, // location of translation_buffer
223 uint64_t size_on_disk,
224 unsigned char *
225 translation_buffer); // buffer with serialized translation
226
227 void _copy_translation(struct translation *dst,
228 struct translation *src,
229 enum translation_type newtype);
230 void _maybe_optimize_translation(struct translation *t);
231 void _maybe_expand_translation(struct translation *t);
232 bool _translation_prevents_freeing(struct translation *t,
233 BLOCKNUM b,
234 struct block_translation_pair *old_pair);
235 void _free_blocknum_in_translation(struct translation *t, BLOCKNUM b);
236 int64_t _calculate_size_on_disk(struct translation *t);
237 bool _pair_is_unallocated(struct block_translation_pair *pair);
238 void _alloc_inprogress_translation_on_disk_unlocked();
239 void _dump_translation_internal(FILE *f, struct translation *t);
240
241 // Blocknum management
242 void _allocate_blocknum_unlocked(BLOCKNUM *res, struct ft *ft);
243 void _free_blocknum_unlocked(BLOCKNUM *bp,
244 struct ft *ft,
245 bool for_checkpoint);
246 void _realloc_descriptor_on_disk_unlocked(DISKOFF size,
247 DISKOFF *offset,
248 struct ft *ft);
249 void _realloc_on_disk_internal(BLOCKNUM b,
250 DISKOFF size,
251 DISKOFF *offset,
252 struct ft *ft,
253 bool for_checkpoint);
254 void _translate_blocknum_to_offset_size_unlocked(BLOCKNUM b,
255 DISKOFF *offset,
256 DISKOFF *size);
257
258 // File management
259 void _maybe_truncate_file(int fd, uint64_t size_needed_before);
260 void _ensure_safe_write_unlocked(int fd,
261 DISKOFF block_size,
262 DISKOFF block_offset);
263
264 // Verification
265 bool _is_valid_blocknum(struct translation *t, BLOCKNUM b);
266 void _verify_valid_blocknum(struct translation *t, BLOCKNUM b);
267 bool _is_valid_freeable_blocknum(struct translation *t, BLOCKNUM b);
268 void _verify_valid_freeable_blocknum(struct translation *t, BLOCKNUM b);
269 bool _no_data_blocks_except_root(BLOCKNUM root);
270 bool _blocknum_allocated(BLOCKNUM b);
271
272 // Locking
273 //
274 // TODO: Move the lock to the FT
275 void _mutex_lock();
276 void _mutex_unlock();
277
278 // The current translation is the one used by client threads.
279 // It is not represented on disk.
280 struct translation _current;
281
282 // The translation used by the checkpoint currently in progress.
283 // If the checkpoint thread allocates a block, it must also update the
284 // current translation.
285 struct translation _inprogress;
286
287 // The translation for the data that shall remain inviolate on disk until
288 // the next checkpoint finishes,
289 // after which any blocks used only in this translation can be freed.
290 struct translation _checkpointed;
291
292 // The in-memory data structure for block allocation.
293 // There is no on-disk data structure for block allocation.
294 // Note: This is *allocation* not *translation* - the block allocator is
295 // unaware of which
296 // blocks are used for which translation, but simply allocates and
297 // deallocates blocks.
298 BlockAllocator *_bt_block_allocator;
299 toku_mutex_t _mutex;
300 struct nb_mutex _safe_file_size_lock;
301 bool _checkpoint_skipped;
302 uint64_t _safe_file_size;
303
304 // Because the lock is in a weird place right now
305 friend void toku_ft_lock(struct ft *ft);
306 friend void toku_ft_unlock(struct ft *ft);
307};
308
309// For serialize / deserialize
310
311#include "ft/serialize/wbuf.h"
312
313static inline void wbuf_BLOCKNUM(struct wbuf *w, BLOCKNUM b) {
314 wbuf_ulonglong(w, b.b);
315}
316
317static inline void wbuf_nocrc_BLOCKNUM(struct wbuf *w, BLOCKNUM b) {
318 wbuf_nocrc_ulonglong(w, b.b);
319}
320
321static inline void wbuf_DISKOFF(struct wbuf *wb, DISKOFF off) {
322 wbuf_ulonglong(wb, (uint64_t)off);
323}
324
325#include "ft/serialize/rbuf.h"
326
327static inline DISKOFF rbuf_DISKOFF(struct rbuf *rb) {
328 return rbuf_ulonglong(rb);
329}
330
331static inline BLOCKNUM rbuf_blocknum(struct rbuf *rb) {
332 BLOCKNUM result = make_blocknum(rbuf_longlong(rb));
333 return result;
334}
335
336static inline void rbuf_ma_BLOCKNUM(struct rbuf *rb,
337 memarena *UU(ma),
338 BLOCKNUM *blocknum) {
339 *blocknum = rbuf_blocknum(rb);
340}
341