1
/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2
// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
5
COPYING CONDITIONS NOTICE:
7
This program is free software; you can redistribute it and/or modify
8
it under the terms of version 2 of the GNU General Public License as
9
published by the Free Software Foundation, and provided that the
10
following conditions are met:
12
* Redistributions of source code must retain this COPYING
13
CONDITIONS NOTICE, the COPYRIGHT NOTICE (below), the
14
DISCLAIMER (below), the UNIVERSITY PATENT NOTICE (below), the
15
PATENT MARKING NOTICE (below), and the PATENT RIGHTS
18
* Redistributions in binary form must reproduce this COPYING
19
CONDITIONS NOTICE, the COPYRIGHT NOTICE (below), the
20
DISCLAIMER (below), the UNIVERSITY PATENT NOTICE (below), the
21
PATENT MARKING NOTICE (below), and the PATENT RIGHTS
22
GRANT (below) in the documentation and/or other materials
23
provided with the distribution.
25
You should have received a copy of the GNU General Public License
26
along with this program; if not, write to the Free Software
27
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
32
TokuFT, Tokutek Fractal Tree Indexing Library.
33
Copyright (C) 2007-2014 Tokutek, Inc.
37
This program is distributed in the hope that it will be useful, but
38
WITHOUT ANY WARRANTY; without even the implied warranty of
39
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
40
General Public License for more details.
42
UNIVERSITY PATENT NOTICE:
44
The technology is licensed by the Massachusetts Institute of
45
Technology, Rutgers State University of New Jersey, and the Research
46
Foundation of State University of New York at Stony Brook under
47
United States of America Serial No. 11/760379 and to the patents
48
and/or patent applications resulting from it.
50
PATENT MARKING NOTICE:
52
This software is covered by US Patent No. 8,185,551.
53
This software is covered by US Patent No. 8,489,638.
57
"THIS IMPLEMENTATION" means the copyrightable works distributed by
58
Tokutek as part of the Fractal Tree project.
60
"PATENT CLAIMS" means the claims of patents that are owned or
61
licensable by Tokutek, both currently or in the future; and that in
62
the absence of this license would be infringed by THIS
63
IMPLEMENTATION or by using or running THIS IMPLEMENTATION.
65
"PATENT CHALLENGE" shall mean a challenge to the validity,
66
patentability, enforceability and/or non-infringement of any of the
67
PATENT CLAIMS or otherwise opposing any of the PATENT CLAIMS.
69
Tokutek hereby grants to you, for the term and geographical scope of
70
the PATENT CLAIMS, a non-exclusive, no-charge, royalty-free,
71
irrevocable (except as stated in this section) patent license to
72
make, have made, use, offer to sell, sell, import, transfer, and
73
otherwise run, modify, and propagate the contents of THIS
74
IMPLEMENTATION, where such license applies only to the PATENT
75
CLAIMS. This grant does not include claims that would be infringed
76
only as a consequence of further modifications of THIS
77
IMPLEMENTATION. If you or your agent or licensee institute or order
78
or agree to the institution of patent litigation against any entity
79
(including a cross-claim or counterclaim in a lawsuit) alleging that
80
THIS IMPLEMENTATION constitutes direct or contributory patent
81
infringement, or inducement of patent infringement, then any rights
82
granted to you under this License shall terminate as of the date
83
such litigation is filed. If you or your agent or exclusive
84
licensee institute or order or agree to the institution of a PATENT
85
CHALLENGE, then Tokutek may terminate any rights granted to you
91
#ident "Copyright (c) 2007-2014 Tokutek Inc. All rights reserved."
92
#ident "The technology is licensed by the Massachusetts Institute of Technology, Rutgers State University of New Jersey, and the Research Foundation of State University of New York at Stony Brook under United States of America Serial No. 11/760379 and to the patents and/or patent applications resulting from it."
96
#include "portability/toku_stdint.h"
97
#include "portability/toku_pthread.h"
99
#include "ft/serialize/block_allocator.h"
100
#include "util/nb_mutex.h"
104
typedef struct blocknum_s { int64_t b; } BLOCKNUM;
106
// Offset in a disk. -1 is the 'null' pointer.
107
typedef int64_t DISKOFF;
109
// Unmovable reserved first, then reallocable.
110
// We reserve one blocknum for the translation table itself.
112
RESERVED_BLOCKNUM_NULL = 0,
113
RESERVED_BLOCKNUM_TRANSLATION = 1,
114
RESERVED_BLOCKNUM_DESCRIPTOR = 2,
118
typedef int (*BLOCKTABLE_CALLBACK)(BLOCKNUM b, int64_t size, int64_t address, void *extra);
120
static inline BLOCKNUM make_blocknum(int64_t b) {
121
BLOCKNUM result = { .b = b };
124
static const BLOCKNUM ROLLBACK_NONE = { .b = 0 };
127
* There are three copies of the translation table (btt) in the block table:
129
* checkpointed Is initialized by deserializing from disk,
130
* and is the only version ever read from disk.
131
* When read from disk it is copied to current.
132
* It is immutable. It can be replaced by an inprogress btt.
134
* inprogress Is only filled by copying from current,
135
* and is the only version ever serialized to disk.
136
* (It is serialized to disk on checkpoint and clean shutdown.)
137
* At end of checkpoint it replaces 'checkpointed'.
138
* During a checkpoint, any 'pending' dirty writes will update
141
* current Is initialized by copying from checkpointed,
142
* is the only version ever modified while the database is in use,
143
* and is the only version ever copied to inprogress.
144
* It is never stored on disk.
148
enum translation_type {
149
TRANSLATION_NONE = 0,
151
TRANSLATION_INPROGRESS,
152
TRANSLATION_CHECKPOINTED,
158
int create_from_buffer(int fd, DISKOFF location_on_disk, DISKOFF size_on_disk, unsigned char *translation_buffer);
163
void note_start_checkpoint_unlocked();
164
void note_end_checkpoint(int fd);
165
void note_skipped_checkpoint();
166
void maybe_truncate_file_on_open(int fd);
169
void allocate_blocknum(BLOCKNUM *res, struct ft *ft);
170
void realloc_on_disk(BLOCKNUM b, DISKOFF size, DISKOFF *offset, struct ft *ft, int fd, bool for_checkpoint, uint64_t heat);
171
void free_blocknum(BLOCKNUM *b, struct ft *ft, bool for_checkpoint);
172
void translate_blocknum_to_offset_size(BLOCKNUM b, DISKOFF *offset, DISKOFF *size);
173
void free_unused_blocknums(BLOCKNUM root);
174
void realloc_descriptor_on_disk(DISKOFF size, DISKOFF *offset, struct ft *ft, int fd);
175
void get_descriptor_offset_size(DISKOFF *offset, DISKOFF *size);
177
// External verfication
178
void verify_blocknum_allocated(BLOCKNUM b);
179
void verify_no_data_blocks_except_root(BLOCKNUM root);
180
void verify_no_free_blocknums();
183
void serialize_translation_to_wbuf(int fd, struct wbuf *w, int64_t *address, int64_t *size);
185
// DEBUG ONLY (ftdump included), tests included
186
void blocknum_dump_translation(BLOCKNUM b);
187
void dump_translation_table_pretty(FILE *f);
188
void dump_translation_table(FILE *f);
189
void block_free(uint64_t offset);
191
int iterate(enum translation_type type, BLOCKTABLE_CALLBACK f, void *extra, bool data_only, bool used_only);
192
void internal_fragmentation(int64_t *total_sizep, int64_t *used_sizep);
194
// Requires: blocktable lock is held.
195
// Requires: report->file_size_bytes is already filled in.
196
void get_fragmentation_unlocked(TOKU_DB_FRAGMENTATION report);
198
int64_t get_blocks_in_use_unlocked();
200
void get_info64(struct ftinfo64 *);
202
int iterate_translation_tables(uint64_t, int (*)(uint64_t, int64_t, int64_t, int64_t, int64_t, void *), void *);
205
struct block_translation_pair {
206
// If in the freelist, use next_free_blocknum, otherwise diskoff.
209
BLOCKNUM next_free_blocknum;
212
// Set to 0xFFFFFFFFFFFFFFFF for free
216
// This is the BTT (block translation table)
217
// When the translation (btt) is stored on disk:
221
// In block translation table (in order):
222
// smallest_never_used_blocknum
223
// blocknum_freelist_head
227
enum translation_type type;
229
// Number of elements in array (block_translation). always >= smallest_never_used_blocknum
230
int64_t length_of_array;
231
BLOCKNUM smallest_never_used_blocknum;
233
// Next (previously used) unused blocknum (free list)
234
BLOCKNUM blocknum_freelist_head;
235
struct block_translation_pair *block_translation;
237
// size_on_disk is stored in block_translation[RESERVED_BLOCKNUM_TRANSLATION].size
238
// location_on is stored in block_translation[RESERVED_BLOCKNUM_TRANSLATION].u.diskoff
241
void _create_internal();
242
int _translation_deserialize_from_buffer(struct translation *t, // destination into which to deserialize
243
DISKOFF location_on_disk, // location of translation_buffer
244
uint64_t size_on_disk,
245
unsigned char * translation_buffer); // buffer with serialized translation
247
void _copy_translation(struct translation *dst, struct translation *src, enum translation_type newtype);
248
void _maybe_optimize_translation(struct translation *t);
249
void _maybe_expand_translation(struct translation *t);
250
bool _translation_prevents_freeing(struct translation *t, BLOCKNUM b, struct block_translation_pair *old_pair);
251
void _free_blocknum_in_translation(struct translation *t, BLOCKNUM b);
252
int64_t _calculate_size_on_disk(struct translation *t);
253
bool _pair_is_unallocated(struct block_translation_pair *pair);
254
void _alloc_inprogress_translation_on_disk_unlocked();
255
void _dump_translation_internal(FILE *f, struct translation *t);
257
// Blocknum management
258
void _allocate_blocknum_unlocked(BLOCKNUM *res, struct ft *ft);
259
void _free_blocknum_unlocked(BLOCKNUM *bp, struct ft *ft, bool for_checkpoint);
260
void _realloc_descriptor_on_disk_unlocked(DISKOFF size, DISKOFF *offset, struct ft *ft);
261
void _realloc_on_disk_internal(BLOCKNUM b, DISKOFF size, DISKOFF *offset, struct ft *ft, bool for_checkpoint, uint64_t heat);
262
void _translate_blocknum_to_offset_size_unlocked(BLOCKNUM b, DISKOFF *offset, DISKOFF *size);
265
void _maybe_truncate_file(int fd, uint64_t size_needed_before);
266
void _ensure_safe_write_unlocked(int fd, DISKOFF block_size, DISKOFF block_offset);
269
bool _is_valid_blocknum(struct translation *t, BLOCKNUM b);
270
void _verify_valid_blocknum(struct translation *t, BLOCKNUM b);
271
bool _is_valid_freeable_blocknum(struct translation *t, BLOCKNUM b);
272
void _verify_valid_freeable_blocknum(struct translation *t, BLOCKNUM b);
273
bool _no_data_blocks_except_root(BLOCKNUM root);
274
bool _blocknum_allocated(BLOCKNUM b);
278
// TODO: Move the lock to the FT
280
void _mutex_unlock();
282
// The current translation is the one used by client threads.
283
// It is not represented on disk.
284
struct translation _current;
286
// The translation used by the checkpoint currently in progress.
287
// If the checkpoint thread allocates a block, it must also update the current translation.
288
struct translation _inprogress;
290
// The translation for the data that shall remain inviolate on disk until the next checkpoint finishes,
291
// after which any blocks used only in this translation can be freed.
292
struct translation _checkpointed;
294
// The in-memory data structure for block allocation.
295
// There is no on-disk data structure for block allocation.
296
// Note: This is *allocation* not *translation* - the block allocator is unaware of which
297
// blocks are used for which translation, but simply allocates and deallocates blocks.
298
block_allocator _bt_block_allocator;
300
struct nb_mutex _safe_file_size_lock;
301
bool _checkpoint_skipped;
302
uint64_t _safe_file_size;
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);
309
// For serialize / deserialize
311
#include "ft/serialize/wbuf.h"
313
static inline void wbuf_BLOCKNUM (struct wbuf *w, BLOCKNUM b) {
314
wbuf_ulonglong(w, b.b);
317
static inline void wbuf_nocrc_BLOCKNUM (struct wbuf *w, BLOCKNUM b) {
318
wbuf_nocrc_ulonglong(w, b.b);
321
static inline void wbuf_DISKOFF(struct wbuf *wb, DISKOFF off) {
322
wbuf_ulonglong(wb, (uint64_t) off);
325
#include "ft/serialize/rbuf.h"
327
static inline DISKOFF rbuf_DISKOFF(struct rbuf *rb) {
328
return rbuf_ulonglong(rb);
331
static inline BLOCKNUM rbuf_blocknum(struct rbuf *rb) {
332
BLOCKNUM result = make_blocknum(rbuf_longlong(rb));
336
static inline void rbuf_ma_BLOCKNUM(struct rbuf *rb, memarena *UU(ma), BLOCKNUM *blocknum) {
337
*blocknum = rbuf_blocknum(rb);
added
removed
storage/tokudb/ft-index/ft/serialize/block_table.h
