xref: /4.6.0/forestdb/src/superblock.h (revision c3456ce2)
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     * Why atomic?
141     * during docio_read_through_buffer() we must invalidate docio cache if the
142     * bitmap revnum had changed which can race with
143     * sb_reclaim_reusable_blocks called during commit in writer thread if file
144     * handle is shared between the reader and writer threads
145     */
146    atomic_uint64_t bmp_revnum;
147    /**
148     * Number of bits in the bitmap. Each bit represents a block.
149     */
150    atomic_uint64_t bmp_size;
151    /**
152     * Pointer to the bitmap.
153     */
154    std::atomic<uint8_t *> bmp;
155    /**
156     * Reference counter for bitmap readers.
157     */
158    atomic_uint64_t bmp_rcount;
159    /**
160     * Reference counter for bitmap writers.
161     */
162    atomic_uint64_t bmp_wcount;
163    /**
164     * Lock for bitmap modification.
165     */
166    spin_t bmp_lock;
167    /**
168     * Number of bits in the previous bitmap. Each bit represents a block.
169     */
170    uint64_t bmp_prev_size;
171    /**
172     * Pointer to the previous (previous bitmap revnum) bitmap.
173     */
174    uint8_t *bmp_prev;
175    /**
176     * Bitmap index for fast searching of next reusable block.
177     */
178    struct avl_tree bmp_idx;
179    /**
180     * Pointer to array of bitmap document offsets, where a bitmap document is a
181     * system documents containing a part of the bitmap.
182     */
183    bid_t *bmp_doc_offset;
184    /**
185     * Pointer to array of bitmap document in-memory objects.
186     */
187    struct docio_object *bmp_docs;
188    /**
189     * Number of bitmap documents.
190     */
191    uint64_t num_bmp_docs;
192    /**
193     * Initial number of free blocks in the bitmap right after the bitmap is updated.
194     */
195    uint64_t num_init_free_blocks;
196    /**
197     * Current number of free blocks in the bitmap.
198     */
199    uint64_t num_free_blocks;
200    /**
201     * Reserved bitmap for the next round block reuse.
202     */
203    struct sb_rsv_bmp *rsv_bmp;
204    /**
205     * BID of a block to be allocated next time.
206     */
207    atomic_uint64_t cur_alloc_bid;
208    /**
209     * BID of the last header.
210     */
211    atomic_uint64_t last_hdr_bid;
212    /**
213     * Revision number of the oldest header that is not reclaimed yet and is currently
214     * active in the file.
215     */
216    uint64_t min_live_hdr_revnum;
217    /**
218     * BID of the oldest header that is not reclaimed yet and is currently active in the
219     * file.
220     */
221    bid_t min_live_hdr_bid;
222    /**
223     * Revision number of the last header.
224     */
225    atomic_uint64_t last_hdr_revnum;
226    /**
227     * Number of allocated blocks since the last superblock sync.
228     */
229    uint64_t num_alloc;
230    /**
231     * Lock for superblock initialization.
232     */
233    spin_t lock;
234};
235
236struct sb_ops {
237    fdb_status (*init)(struct filemgr *file,
238                       struct sb_config sconfig,
239                       err_log_callback *log_callback);
240    struct sb_config (*get_default_config)();
241    fdb_status (*read_latest)(struct filemgr *file,
242                              struct sb_config sconfig,
243                              err_log_callback *log_callback);
244    bid_t (*alloc_block)(struct filemgr *file);
245    bool (*is_writable)(struct filemgr *file, bid_t bid);
246    uint64_t (*get_bmp_revnum)(struct filemgr *file);
247    uint64_t (*get_min_live_revnum)(struct filemgr *file);
248    fdb_status (*release)(struct filemgr *file);
249};
250
251/**
252 * Check if superblock has non-empty bitmap.
253 *
254 * @param sb Pointer to superblock structure.
255 * @return True if bitmap exists.
256 */
257INLINE bool sb_bmp_exists(struct superblock *sb)
258{
259    if (sb && atomic_get_uint64_t(&sb->bmp_size)) {
260        return true;
261    }
262    return false;
263}
264
265/**
266 * Create system docs for bitmap and append them into the file.
267 *
268 * @param handle Pointer to ForestDB KV store handle.
269 * @return void.
270 */
271void sb_bmp_append_doc(fdb_kvs_handle *handle);
272
273/**
274 * Create system docs for reserved bitmap and append them into the file.
275 *
276 * @param handle Pointer to ForestDB KV store handle.
277 * @return void.
278 */
279void sb_rsv_append_doc(fdb_kvs_handle *handle);
280
281/**
282 * Read bitmap docs from file and reconstruct bitmap.
283 *
284 * @param handle Pointer to ForestDB KV store handle.
285 * @return FDB_RESULT_SUCCESS on success.
286 */
287fdb_status sb_bmp_fetch_doc(fdb_kvs_handle *handle);
288
289/**
290 * Update in-memory structure of superblock using current header info.
291 *
292 * @param handle Pointer to ForestDB KV store handle.
293 * @return True if superblock is updated.
294 */
295bool sb_update_header(fdb_kvs_handle *handle);
296
297/**
298 * Reset counter for the number of block allocation.
299 *
300 * @param handle Pointer to ForestDB KV store handle.
301 * @return void.
302 */
303void sb_reset_num_alloc(fdb_kvs_handle *handle);
304
305/**
306 * Write back superblock info into the file.
307 *
308 * @param handle Pointer to ForestDB KV store handle.
309 * @return FDB_RESULT_SUCCESS on success.
310 */
311fdb_status sb_sync_circular(fdb_kvs_handle *handle);
312/**
313 * Check if superblock needs to be written back into the file.
314 *
315 * @param handle Pointer to ForestDB KV store handle.
316 * @return True if superblock meets the sync period.
317 */
318bool sb_check_sync_period(fdb_kvs_handle *handle);
319
320/**
321 * Reusable block reclaim logic decision.
322 */
323typedef enum {
324    /**
325     * Do nothing.
326     */
327    SBD_NONE = 0,
328    /**
329     * Reclaim reusable blocks and update the bitmap immediately.
330     */
331    SBD_RECLAIM = 1,
332    /**
333     * Reclaim reusable blocks but reserve them for the next round.
334     */
335    SBD_RESERVE = 2,
336    /**
337     * Discard the current bitmap and take the reserved bitmap.
338     */
339    SBD_SWITCH = 3
340} sb_decision_t;
341
342/**
343 * Check if more blocks need to be reclaimed for being reused.
344 *
345 * @param handle Pointer to ForestDB KV store handle.
346 * @return True if block reusing is necessary.
347 */
348sb_decision_t sb_check_block_reusing(fdb_kvs_handle *handle);
349
350/**
351 * Reclaim stale blocks and update the in-memory structure of bitmap in superblock.
352 *
353 * @param handle Pointer to ForestDB KV store handle.
354 * @return True if block reclaiming succeeded.
355 */
356bool sb_reclaim_reusable_blocks(fdb_kvs_handle *handle);
357
358/**
359 * Switch reserved blocks to currently being used blocks.
360 *
361 * @param file Pointer to file manager handle.
362 * @return True if switching succeeded.
363 */
364bool sb_switch_reserved_blocks(struct filemgr *file);
365
366/**
367 * Reclaim stale blocks for the next round block reuse and create an in-memory
368 * structure for the reserved bitmap array.
369 *
370 * @param handle Pointer to ForestDB KV store handle.
371 * @return True if block reclaiming succeeded.
372 */
373bool sb_reserve_next_reusable_blocks(fdb_kvs_handle *handle);
374
375/**
376 * Restore all remaining reusable blocks including reserved blocks
377 * into stale tree again.
378 *
379 * @param handle Pointer to ForestDB KV store handle.
380 * @return void.
381 */
382void sb_return_reusable_blocks(fdb_kvs_handle *handle);
383
384/**
385 * Set bitmap bits for the given blocks.
386 *
387 * @param bmp Pointer to bitmap array.
388 * @param bid Starting BID.
389 * @param len Number of blocks.
390 * @return void.
391 */
392void sb_bmp_set(uint8_t *bmp, bid_t bid, uint64_t len);
393/**
394 * Clear bitmap bits for the given blocks.
395 *
396 * @param bmp Pointer to bitmap array.
397 * @param bid Starting BID.
398 * @param len Number of blocks.
399 * @return void.
400 */
401void sb_bmp_clear(uint8_t *bmp, bid_t bid, uint64_t len);
402/**
403 * Initialize bitmap masks for bitmap operations.
404 *
405 * @return void.
406 */
407void sb_bmp_mask_init();
408/**
409 * Investigate if the given block is writable.
410 *
411 * @param file Pointer to filemgr handle.
412 * @param bid ID of block.
413 * @return True if the block is writable.
414 */
415bool sb_bmp_is_writable(struct filemgr *file, bid_t bid);
416
417/**
418 * Initialize superblock structure.
419 *
420 * @param file Pointer to filemgr handle.
421 * @param sconfig Superblock configuration.
422 * @param log_callback Pointer to log callback function.
423 * @return FDB_RESULT_SUCCESS on success.
424 */
425fdb_status sb_init(struct filemgr *file, struct sb_config sconfig,
426                   err_log_callback * log_callback);
427
428/**
429 * Write a superblock with the given ID.
430 *
431 * @param file Pointer to filemgr handle.
432 * @param sb_no Superblock ID.
433 * @param log_callback Pointer to log callback function.
434 * @return FDB_RESULT_SUCCESS on success.
435 */
436fdb_status sb_write(struct filemgr *file, size_t sb_no,
437                    err_log_callback * log_callback);
438
439/**
440 * Read all superblocks and take the most recent superblock.
441 *
442 * @param file Pointer to filemgr handle.
443 * @param sconfig Superblock configuration.
444 * @param log_callback Pointer to log callback function.
445 * @return FDB_RESULT_SUCCESS on success.
446 */
447fdb_status sb_read_latest(struct filemgr *file,
448                          struct sb_config sconfig,
449                          err_log_callback *log_callback);
450
451/**
452 * Allocate a free block by referring the bitmap in superblock, in a circular manner.
453 *
454 * @param file Pointer to filemgr handle.
455 * @return ID of the allocated block. BLK_NOT_FOUND if there is no free block in the
456 *         bitmap.
457 */
458bid_t sb_alloc_block(struct filemgr *file);
459
460/**
461 * Get the current revision number of bitmap in superblock.
462 *
463 * @param file Pointer to filemgr handle.
464 * @return Bitmap revision number.
465 */
466uint64_t sb_get_bmp_revnum(struct filemgr *file);
467
468/**
469 * Get the oldest active header revision number.
470 *
471 * @param file Pointer to filemgr handle.
472 * @return Header revision number.
473 */
474uint64_t sb_get_min_live_revnum(struct filemgr *file);
475
476/**
477 * Get the number of free blocks in the bitmap of superblock.
478 *
479 * @param file Pointer to filemgr handle.
480 * @return Number of free blocks.
481 */
482uint64_t sb_get_num_free_blocks(struct filemgr *file);
483
484/**
485 * Free all in-memory superblock structures.
486 *
487 * @param file Pointer to filemgr handle.
488 * @return FDB_RESULT_SUCCESS on success.
489 */
490fdb_status sb_free(struct filemgr *file);
491
492/**
493 * Get the default superblock configurations.
494 *
495 * @return sb_config instance that contains the default configurations.
496 */
497struct sb_config sb_get_default_config();
498
499#ifdef __cplusplus
500}
501#endif
502
503#endif /* _FDB_SUPERBLOCK_H */
504
505