xref: /6.0.3/forestdb/src/superblock.h (revision 30dcf327)
1/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 *     Copyright 2015 Couchbase, Inc
4 *
5 *   Licensed under the Apache License, Version 2.0 (the "License");
6 *   you may not use this file except in compliance with the License.
7 *   You may obtain a copy of the License at
8 *
9 *       http://www.apache.org/licenses/LICENSE-2.0
10 *
11 *   Unless required by applicable law or agreed to in writing, software
12 *   distributed under the License is distributed on an "AS IS" BASIS,
13 *   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 *   See the License for the specific language governing permissions and
15 *   limitations under the License.
16 */
17
18#ifndef _FDB_SUPERBLOCK_H
19#define _FDB_SUPERBLOCK_H
20
21#include "libforestdb/fdb_types.h"
22#include "libforestdb/fdb_errors.h"
23#include "common.h"
24
25#include "filemgr.h"
26#include "avltree.h"
27#include "atomic.h"
28#include "docio.h"
29
30#ifdef __cplusplus
31extern "C" {
32#endif
33
34/**
35 * Superblock config options that are passed to sb_init() API.
36 */
37struct sb_config {
38    /**
39     * Number of superblocks that are concurrently maintained for crash recovery.
40     */
41    uint8_t num_sb;
42};
43
44/**
45 * Reserved bitmap is destroyed or not initialized.
46 */
47#define SB_RSV_VOID (0x0)
48/**
49 * Reserved bitmap is being initialized (not ready to use).
50 */
51#define SB_RSV_INITIALIZING (0x1)
52/**
53 * Reserved bitmap is being written into the DB file.
54 */
55#define SB_RSV_WRITING (0x2)
56/**
57 * Reserved bitmap is now available.
58 */
59#define SB_RSV_READY (0xffff)
60
61/**
62 * Pre-reclaimed reusable block bitmap info.
63 * Each attribute is same as that in superblock.
64 */
65struct sb_rsv_bmp {
66    /**
67     * Revision number of the reserved bitmap.
68     */
69    uint64_t bmp_revnum;
70    /**
71     * Number of bits in the bitmap. Each bit represents a block.
72     */
73    uint64_t bmp_size;
74    /**
75     * Pointer to the bitmap.
76     */
77    uint8_t *bmp;
78    /**
79     * Bitmap index for fast searching of next reusable block.
80     */
81    struct avl_tree bmp_idx;
82    /**
83     * Pointer to array of bitmap document offsets, where a bitmap document is a
84     * system documents containing a part of the bitmap.
85     */
86    bid_t *bmp_doc_offset;
87    /**
88     * Pointer to array of bitmap document in-memory objects.
89     */
90    struct docio_object *bmp_docs;
91    /**
92     * Number of bitmap documents.
93     */
94    uint64_t num_bmp_docs;
95    /**
96     * Current number of free blocks in the bitmap.
97     */
98    uint64_t num_free_blocks;
99    /**
100     * BID of a block to be allocated next time.
101     */
102    bid_t cur_alloc_bid;
103    /**
104     * Revision number of the oldest header that is not reclaimed yet and is currently
105     * active in the file.
106     */
107    uint64_t min_live_hdr_revnum;
108    /**
109     * BID of the oldest header that is not reclaimed yet and is currently active in the
110     * file.
111     */
112    bid_t min_live_hdr_bid;
113    /**
114     * Status of the reserved bitmap.
115     */
116    atomic_uint32_t status;
117};
118
119/**
120 * Superblock structure definition.
121 *
122 * Note: following functions should be adapted
123 *       if this structure is changed:
124 *       _sb_init()
125 *       _sb_copy()
126 */
127struct superblock {
128    /**
129     * Superblock configuration.
130     */
131    struct sb_config *config;
132    /**
133     * Current revision number of superblock. This value increases whenever superblock
134     * is written back into file.
135     */
136    atomic_uint64_t revnum;
137    /**
138     * Current revision number of bitmap in superblock. This value increases whenever
139     * ForestDB reclaims stale blocks and accordingly bitmap is updated.
140     */
141    uint64_t bmp_revnum;
142    /**
143     * Number of bits in the bitmap. Each bit represents a block.
144     */
145    atomic_uint64_t bmp_size;
146    /**
147     * Pointer to the bitmap.
148     */
149    std::atomic<uint8_t *> bmp;
150    /**
151     * Reference counter for bitmap readers.
152     */
153    atomic_uint64_t bmp_rcount;
154    /**
155     * Reference counter for bitmap writers.
156     */
157    atomic_uint64_t bmp_wcount;
158    /**
159     * Lock for bitmap modification.
160     */
161    spin_t bmp_lock;
162    /**
163     * Number of bits in the previous bitmap. Each bit represents a block.
164     */
165    uint64_t bmp_prev_size;
166    /**
167     * Pointer to the previous (previous bitmap revnum) bitmap.
168     */
169    uint8_t *bmp_prev;
170    /**
171     * Bitmap index for fast searching of next reusable block.
172     */
173    struct avl_tree bmp_idx;
174    /**
175     * Pointer to array of bitmap document offsets, where a bitmap document is a
176     * system documents containing a part of the bitmap.
177     */
178    bid_t *bmp_doc_offset;
179    /**
180     * Pointer to array of bitmap document in-memory objects.
181     */
182    struct docio_object *bmp_docs;
183    /**
184     * Number of bitmap documents.
185     */
186    uint64_t num_bmp_docs;
187    /**
188     * Initial number of free blocks in the bitmap right after the bitmap is updated.
189     */
190    uint64_t num_init_free_blocks;
191    /**
192     * Current number of free blocks in the bitmap.
193     */
194    uint64_t num_free_blocks;
195    /**
196     * Reserved bitmap for the next round block reuse.
197     */
198    struct sb_rsv_bmp *rsv_bmp;
199    /**
200     * BID of a block to be allocated next time.
201     */
202    atomic_uint64_t cur_alloc_bid;
203    /**
204     * BID of the last header.
205     */
206    atomic_uint64_t last_hdr_bid;
207    /**
208     * Revision number of the oldest header that is not reclaimed yet and is currently
209     * active in the file.
210     */
211    uint64_t min_live_hdr_revnum;
212    /**
213     * BID of the oldest header that is not reclaimed yet and is currently active in the
214     * file.
215     */
216    bid_t min_live_hdr_bid;
217    /**
218     * Revision number of the last header.
219     */
220    atomic_uint64_t last_hdr_revnum;
221    /**
222     * Number of allocated blocks since the last superblock sync.
223     */
224    uint64_t num_alloc;
225    /**
226     * Lock for superblock initialization.
227     */
228    spin_t lock;
229};
230
231struct sb_ops {
232    fdb_status (*init)(struct filemgr *file,
233                       struct sb_config sconfig,
234                       err_log_callback *log_callback);
235    struct sb_config (*get_default_config)();
236    fdb_status (*read_latest)(struct filemgr *file,
237                              struct sb_config sconfig,
238                              err_log_callback *log_callback);
239    bid_t (*alloc_block)(struct filemgr *file);
240    bool (*is_writable)(struct filemgr *file, bid_t bid);
241    uint64_t (*get_bmp_revnum)(struct filemgr *file);
242    uint64_t (*get_min_live_revnum)(struct filemgr *file);
243    fdb_status (*release)(struct filemgr *file);
244};
245
246/**
247 * Check if superblock has non-empty bitmap.
248 *
249 * @param sb Pointer to superblock structure.
250 * @return True if bitmap exists.
251 */
252INLINE bool sb_bmp_exists(struct superblock *sb)
253{
254    if (sb && atomic_get_uint64_t(&sb->bmp_size)) {
255        return true;
256    }
257    return false;
258}
259
260/**
261 * Create system docs for bitmap and append them into the file.
262 *
263 * @param handle Pointer to ForestDB KV store handle.
264 * @return void.
265 */
266void sb_bmp_append_doc(fdb_kvs_handle *handle);
267
268/**
269 * Create system docs for reserved bitmap and append them into the file.
270 *
271 * @param handle Pointer to ForestDB KV store handle.
272 * @return void.
273 */
274void sb_rsv_append_doc(fdb_kvs_handle *handle);
275
276/**
277 * Read bitmap docs from file and reconstruct bitmap.
278 *
279 * @param handle Pointer to ForestDB KV store handle.
280 * @return FDB_RESULT_SUCCESS on success.
281 */
282fdb_status sb_bmp_fetch_doc(fdb_kvs_handle *handle);
283
284/**
285 * Update in-memory structure of superblock using current header info.
286 *
287 * @param handle Pointer to ForestDB KV store handle.
288 * @return True if superblock is updated.
289 */
290bool sb_update_header(fdb_kvs_handle *handle);
291
292/**
293 * Reset counter for the number of block allocation.
294 *
295 * @param handle Pointer to ForestDB KV store handle.
296 * @return void.
297 */
298void sb_reset_num_alloc(fdb_kvs_handle *handle);
299
300/**
301 * Write back superblock info into the file.
302 *
303 * @param handle Pointer to ForestDB KV store handle.
304 * @return FDB_RESULT_SUCCESS on success.
305 */
306fdb_status sb_sync_circular(fdb_kvs_handle *handle);
307/**
308 * Check if superblock needs to be written back into the file.
309 *
310 * @param handle Pointer to ForestDB KV store handle.
311 * @return True if superblock meets the sync period.
312 */
313bool sb_check_sync_period(fdb_kvs_handle *handle);
314
315/**
316 * Reusable block reclaim logic decision.
317 */
318typedef enum {
319    /**
320     * Do nothing.
321     */
322    SBD_NONE = 0,
323    /**
324     * Reclaim reusable blocks and update the bitmap immediately.
325     */
326    SBD_RECLAIM = 1,
327    /**
328     * Reclaim reusable blocks but reserve them for the next round.
329     */
330    SBD_RESERVE = 2,
331    /**
332     * Discard the current bitmap and take the reserved bitmap.
333     */
334    SBD_SWITCH = 3
335} sb_decision_t;
336
337/**
338 * Check if more blocks need to be reclaimed for being reused.
339 *
340 * @param handle Pointer to ForestDB KV store handle.
341 * @return True if block reusing is necessary.
342 */
343sb_decision_t sb_check_block_reusing(fdb_kvs_handle *handle);
344
345/**
346 * Reclaim stale blocks and update the in-memory structure of bitmap in superblock.
347 *
348 * @param handle Pointer to ForestDB KV store handle.
349 * @return True if block reclaiming succeeded.
350 */
351bool sb_reclaim_reusable_blocks(fdb_kvs_handle *handle);
352
353/**
354 * Switch reserved blocks to currently being used blocks.
355 *
356 * @param file Pointer to file manager handle.
357 * @return True if switching succeeded.
358 */
359bool sb_switch_reserved_blocks(struct filemgr *file);
360
361/**
362 * Reclaim stale blocks for the next round block reuse and create an in-memory
363 * structure for the reserved bitmap array.
364 *
365 * @param handle Pointer to ForestDB KV store handle.
366 * @return True if block reclaiming succeeded.
367 */
368bool sb_reserve_next_reusable_blocks(fdb_kvs_handle *handle);
369
370/**
371 * Restore all remaining reusable blocks including reserved blocks
372 * into stale tree again.
373 *
374 * @param handle Pointer to ForestDB KV store handle.
375 * @return void.
376 */
377void sb_return_reusable_blocks(fdb_kvs_handle *handle);
378
379/**
380 * Set bitmap bits for the given blocks.
381 *
382 * @param bmp Pointer to bitmap array.
383 * @param bid Starting BID.
384 * @param len Number of blocks.
385 * @return void.
386 */
387void sb_bmp_set(uint8_t *bmp, bid_t bid, uint64_t len);
388/**
389 * Clear bitmap bits for the given blocks.
390 *
391 * @param bmp Pointer to bitmap array.
392 * @param bid Starting BID.
393 * @param len Number of blocks.
394 * @return void.
395 */
396void sb_bmp_clear(uint8_t *bmp, bid_t bid, uint64_t len);
397/**
398 * Initialize bitmap masks for bitmap operations.
399 *
400 * @return void.
401 */
402void sb_bmp_mask_init();
403/**
404 * Investigate if the given block is writable.
405 *
406 * @param file Pointer to filemgr handle.
407 * @param bid ID of block.
408 * @return True if the block is writable.
409 */
410bool sb_bmp_is_writable(struct filemgr *file, bid_t bid);
411
412/**
413 * Initialize superblock structure.
414 *
415 * @param file Pointer to filemgr handle.
416 * @param sconfig Superblock configuration.
417 * @param log_callback Pointer to log callback function.
418 * @return FDB_RESULT_SUCCESS on success.
419 */
420fdb_status sb_init(struct filemgr *file, struct sb_config sconfig,
421                   err_log_callback * log_callback);
422
423/**
424 * Write a superblock with the given ID.
425 *
426 * @param file Pointer to filemgr handle.
427 * @param sb_no Superblock ID.
428 * @param log_callback Pointer to log callback function.
429 * @return FDB_RESULT_SUCCESS on success.
430 */
431fdb_status sb_write(struct filemgr *file, size_t sb_no,
432                    err_log_callback * log_callback);
433
434/**
435 * Read all superblocks and take the most recent superblock.
436 *
437 * @param file Pointer to filemgr handle.
438 * @param sconfig Superblock configuration.
439 * @param log_callback Pointer to log callback function.
440 * @return FDB_RESULT_SUCCESS on success.
441 */
442fdb_status sb_read_latest(struct filemgr *file,
443                          struct sb_config sconfig,
444                          err_log_callback *log_callback);
445
446/**
447 * Allocate a free block by referring the bitmap in superblock, in a circular manner.
448 *
449 * @param file Pointer to filemgr handle.
450 * @return ID of the allocated block. BLK_NOT_FOUND if there is no free block in the
451 *         bitmap.
452 */
453bid_t sb_alloc_block(struct filemgr *file);
454
455/**
456 * Get the current revision number of bitmap in superblock.
457 *
458 * @param file Pointer to filemgr handle.
459 * @return Bitmap revision number.
460 */
461uint64_t sb_get_bmp_revnum(struct filemgr *file);
462
463/**
464 * Get the oldest active header revision number.
465 *
466 * @param file Pointer to filemgr handle.
467 * @return Header revision number.
468 */
469uint64_t sb_get_min_live_revnum(struct filemgr *file);
470
471/**
472 * Get the number of free blocks in the bitmap of superblock.
473 *
474 * @param file Pointer to filemgr handle.
475 * @return Number of free blocks.
476 */
477uint64_t sb_get_num_free_blocks(struct filemgr *file);
478
479/**
480 * Free all in-memory superblock structures.
481 *
482 * @param file Pointer to filemgr handle.
483 * @return FDB_RESULT_SUCCESS on success.
484 */
485fdb_status sb_free(struct filemgr *file);
486
487/**
488 * Get the default superblock configurations.
489 *
490 * @return sb_config instance that contains the default configurations.
491 */
492struct sb_config sb_get_default_config();
493
494#ifdef __cplusplus
495}
496#endif
497
498#endif /* _FDB_SUPERBLOCK_H */
499
500