xref: /5.5.2/forestdb/src/internal_types.h (revision 5b78091c)
1/* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 *     Copyright 2010 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 _INTERNAL_TYPES_H
19#define _INTERNAL_TYPES_H
20
21#include <stdint.h>
22
23#include "libforestdb/fdb_types.h"
24#include "common.h"
25#include "atomic.h"
26#include "avltree.h"
27#include "list.h"
28
29#ifdef __cplusplus
30extern "C" {
31#endif
32
33struct hbtrie;
34struct btree;
35struct filemgr;
36struct btreeblk_handle;
37struct docio_handle;
38struct btree_blk_ops;
39struct snap_handle;
40
41#define OFFSET_SIZE (sizeof(uint64_t))
42
43#define FDB_MAX_KEYLEN_INTERNAL (65520)
44
45/**
46 * Error logging callback struct definition.
47 */
48typedef struct {
49    /**
50     * Error logging callback function.
51     */
52    fdb_log_callback callback;
53    /**
54     * Application-specific context data that is passed to the logging callback
55     * function.
56     */
57    void *ctx_data;
58} err_log_callback;
59
60typedef struct _fdb_transaction fdb_txn;
61
62typedef uint64_t fdb_kvs_id_t;
63
64typedef uint8_t kvs_type_t;
65enum {
66    KVS_ROOT = 0,
67    KVS_SUB = 1
68};
69
70struct list;
71struct kvs_opened_node;
72
73/**
74 * KV store info for each handle.
75 */
76struct kvs_info {
77    /**
78     * KV store type.
79     */
80    kvs_type_t type;
81    /**
82     * KV store ID.
83     */
84    fdb_kvs_id_t id;
85    /**
86     * Pointer to root handle.
87     */
88    fdb_kvs_handle *root;
89};
90
91/**
92 * Attributes in KV store statistics.
93 */
94typedef enum {
95    KVS_STAT_NLIVENODES,
96    KVS_STAT_NDOCS,
97    KVS_STAT_NDELETES,
98    KVS_STAT_DATASIZE,
99    KVS_STAT_WAL_NDOCS,
100    KVS_STAT_WAL_NDELETES,
101    KVS_STAT_DELTASIZE
102} kvs_stat_attr_t;
103
104/**
105 * KV store statistics.
106 */
107struct kvs_stat {
108    /**
109     * The number of live index nodes.
110     */
111    uint64_t nlivenodes;
112    /**
113     * The number of documents.
114     */
115    uint64_t ndocs;
116    /**
117     * The number of deleted documents in main index.
118     */
119    uint64_t ndeletes;
120    /**
121     * The amount of space occupied by documents.
122     */
123    uint64_t datasize;
124    /**
125     * The number of documents in WAL.
126     */
127    uint64_t wal_ndocs;
128    /**
129     * The number of deleted documents in WAL.
130     */
131    uint64_t wal_ndeletes;
132    /**
133     * The amount of space occupied by documents+index since last commit.
134     */
135    int64_t deltasize;
136};
137
138// Versioning information...
139// Version 002 - added stale-block tree info
140#define FILEMGR_MAGIC_002 (UINT64_C(0xdeadcafebeefc002))
141// Version 001 - added delta size to DB header and CRC-32C
142#define FILEMGR_MAGIC_001 (UINT64_C(0xdeadcafebeefc001))
143// Version 000 - old format (It involves various DB header formats so that we cannot
144//               identify those different formats by using magic number. To avoid
145//               unexpected behavior or crash, this magic number is no longer
146//               supported.)
147#define FILEMGR_MAGIC_000 (UINT64_C(0xdeadcafebeefbeef))
148#define FILEMGR_LATEST_MAGIC FILEMGR_MAGIC_002
149
150/**
151 * Atomic counters of operational statistics in ForestDB KV store.
152 */
153struct kvs_ops_stat {
154
155    kvs_ops_stat& operator=(const kvs_ops_stat& ops_stat) {
156        atomic_store_uint64_t(&num_sets,
157                              atomic_get_uint64_t(&ops_stat.num_sets,
158                                                  std::memory_order_relaxed),
159                              std::memory_order_relaxed);
160        atomic_store_uint64_t(&num_dels,
161                              atomic_get_uint64_t(&ops_stat.num_dels,
162                                                  std::memory_order_relaxed),
163                              std::memory_order_relaxed);
164        atomic_store_uint64_t(&num_commits,
165                              atomic_get_uint64_t(&ops_stat.num_commits,
166                                                  std::memory_order_relaxed),
167                              std::memory_order_relaxed);
168        atomic_store_uint64_t(&num_compacts,
169                              atomic_get_uint64_t(&ops_stat.num_compacts,
170                                                  std::memory_order_relaxed),
171                              std::memory_order_relaxed);
172        atomic_store_uint64_t(&num_gets,
173                              atomic_get_uint64_t(&ops_stat.num_gets,
174                                                  std::memory_order_relaxed),
175                              std::memory_order_relaxed);
176        atomic_store_uint64_t(&num_iterator_gets,
177                              atomic_get_uint64_t(&ops_stat.num_iterator_gets,
178                                                  std::memory_order_relaxed),
179                              std::memory_order_relaxed);
180        atomic_store_uint64_t(&num_iterator_moves,
181                              atomic_get_uint64_t(&ops_stat.num_iterator_moves,
182                                                  std::memory_order_relaxed),
183                              std::memory_order_relaxed);
184        return *this;
185    }
186
187    // TODO: Move these variables to private members as we refactor the code in C++.
188    /**
189     * Number of fdb_set operations.
190     */
191    atomic_uint64_t num_sets;
192    /**
193     * Number of fdb_del operations.
194     */
195    atomic_uint64_t num_dels;
196    /**
197     * Number of fdb_commit operations.
198     */
199    atomic_uint64_t num_commits;
200    /**
201     * Number of fdb_compact operations on underlying file.
202     */
203    atomic_uint64_t num_compacts;
204    /**
205     * Number of fdb_get* (includes metaonly, byseq etc) operations.
206     */
207    atomic_uint64_t num_gets;
208    /**
209     * Number of fdb_iterator_get* (includes meta_only) operations.
210     */
211    atomic_uint64_t num_iterator_gets;
212    /**
213     * Number of fdb_iterator_moves (includes next,prev,seek) operations.
214     */
215    atomic_uint64_t num_iterator_moves;
216};
217
218#define FHANDLE_ROOT_OPENED (0x1)
219#define FHANDLE_ROOT_INITIALIZED (0x2)
220#define FHANDLE_ROOT_CUSTOM_CMP (0x4)
221/**
222 * ForestDB file handle definition.
223 */
224struct _fdb_file_handle {
225    /**
226     * The root KV store handle.
227     */
228    fdb_kvs_handle *root;
229    /**
230     * List of opened default KV store handles
231     * (except for the root handle).
232     */
233    struct list *handles;
234    /**
235     * List of custom compare functions assigned by user
236     */
237    struct list *cmp_func_list;
238    /**
239     * Flags for the file handle.
240     */
241    uint64_t flags;
242    /**
243     * Spin lock for the file handle.
244     */
245    spin_t lock;
246};
247
248/**
249 * ForestDB KV store key comparison callback context
250 */
251struct _fdb_key_cmp_info {
252    /**
253     * ForestDB KV store level config.
254     */
255    fdb_kvs_config kvs_config;
256    /**
257     * KV store information.
258     */
259    struct kvs_info *kvs;
260};
261
262/**
263 * ForestDB KV store handle definition.
264 */
265struct _fdb_kvs_handle {
266
267    _fdb_kvs_handle& operator=(const _fdb_kvs_handle& kv_handle) {
268        kvs_config = kv_handle.kvs_config;
269        kvs = kv_handle.kvs;
270        op_stats = kv_handle.op_stats;
271        fhandle = kv_handle.fhandle;
272        trie = kv_handle.trie;
273        staletree = kv_handle.staletree;
274        if (kv_handle.kvs) {
275            seqtrie = kv_handle.seqtrie;
276        } else {
277            seqtree = kv_handle.seqtree;
278        }
279        file = kv_handle.file;
280        dhandle = kv_handle.dhandle;
281        bhandle = kv_handle.bhandle;
282        btreeblkops = kv_handle.btreeblkops;
283        fileops = kv_handle.fileops;
284        config = kv_handle.config;
285        log_callback = kv_handle.log_callback;
286        atomic_store_uint64_t(&cur_header_revnum, kv_handle.cur_header_revnum);
287        atomic_store_uint64_t(&last_hdr_bid, kv_handle.last_hdr_bid);
288        last_wal_flush_hdr_bid = kv_handle.last_wal_flush_hdr_bid;
289        kv_info_offset = kv_handle.kv_info_offset;
290        shandle = kv_handle.shandle;
291        seqnum = kv_handle.seqnum;
292        max_seqnum = kv_handle.max_seqnum;
293        filename = kv_handle.filename;
294        txn = kv_handle.txn;
295        atomic_store_uint8_t(&handle_busy,
296                             atomic_get_uint8_t(&kv_handle.handle_busy));
297        dirty_updates = kv_handle.dirty_updates;
298        node = kv_handle.node;
299        num_iterators = kv_handle.num_iterators;
300        return *this;
301    }
302
303    // TODO: Move these variables to private members as we refactor the code in C++.
304
305    /**
306     * ForestDB KV store level config. (Please retain as first struct member)
307     */
308    fdb_kvs_config kvs_config;
309    /**
310     * KV store information. (Please retain as second struct member)
311     */
312    struct kvs_info *kvs;
313    /**
314     * Operational statistics for this kv store.
315     */
316    struct kvs_ops_stat *op_stats;
317    /**
318     * Pointer to the corresponding file handle.
319     */
320    fdb_file_handle *fhandle;
321    /**
322     * HB+-Tree Trie instance.
323     */
324    struct hbtrie *trie;
325    /**
326     * Stale block B+-Tree instance.
327     * Maps from 'commit revision number' to 'stale block info' system document.
328     */
329    struct btree *staletree;
330    /**
331     * Sequence B+-Tree instance.
332     */
333    union {
334        struct btree *seqtree; // single KV instance mode
335        struct hbtrie *seqtrie; // multi KV instance mode
336    };
337    /**
338     * File manager instance.
339     */
340    struct filemgr *file;
341    /**
342     * Doc IO handle instance.
343     */
344    struct docio_handle *dhandle;
345    /**
346     * B+-Tree handle instance.
347     */
348    struct btreeblk_handle *bhandle;
349    /**
350     * B+-Tree block operation handle.
351     */
352    struct btree_blk_ops *btreeblkops;
353    /**
354     * File manager IO operation handle.
355     */
356    struct filemgr_ops *fileops;
357    /**
358     * ForestDB file level config.
359     */
360    fdb_config config;
361    /**
362     * Error logging callback.
363     */
364    err_log_callback log_callback;
365    /**
366     * File header revision number.
367     */
368    atomic_uint64_t cur_header_revnum;
369    /**
370     * Header revision number of rollback point.
371     */
372    uint64_t rollback_revnum;
373    /**
374     * Last header's block ID.
375     * Why Atomic?
376     * reader thread in fdb_sync_db_header can update last_hdr_bid while
377     * writer thread sharing same file handle can get_oldest_active_header()
378     * as part of its sb_reclaim_reusable_blocks()
379     */
380    atomic_uint64_t last_hdr_bid;
381    /**
382     * Block ID of a header created with most recent WAL flush.
383     */
384    uint64_t last_wal_flush_hdr_bid;
385    /**
386     * File offset of a document containing KV instance info.
387     */
388    uint64_t kv_info_offset;
389    /**
390     * Snapshot Information.
391     */
392    struct snap_handle *shandle;
393    /**
394     * KV store's current sequence number.
395     */
396    fdb_seqnum_t seqnum;
397    /**
398     * KV store's max sequence number for snapshot or rollback.
399     */
400    fdb_seqnum_t max_seqnum;
401    /**
402     * Virtual filename (DB instance filename given by users).
403     */
404    char *filename;
405    /**
406     * Transaction handle.
407     */
408    fdb_txn *txn;
409    /**
410     * Atomic flag to detect if handles are being shared among threads.
411     */
412    atomic_uint8_t handle_busy;
413    /**
414     * Flag that indicates whether this handle made dirty updates or not.
415     */
416    uint8_t dirty_updates;
417    /**
418     * List element that will be inserted into 'handles' list in the root handle.
419     */
420    struct kvs_opened_node *node;
421    /**
422     * Number of active iterator instances created from this handle
423     */
424    uint32_t num_iterators;
425};
426
427struct hbtrie_iterator;
428struct avl_tree;
429struct avl_node;
430
431/**
432 * ForestDB iterator cursor movement direction
433 */
434typedef uint8_t fdb_iterator_dir_t;
435enum {
436    /**
437     * Iterator cursor default.
438     */
439    FDB_ITR_DIR_NONE = 0x00,
440    /**
441     * Iterator cursor moving forward
442     */
443    FDB_ITR_FORWARD = 0x01,
444    /**
445     * Iterator cursor moving backwards
446     */
447    FDB_ITR_REVERSE = 0x02
448};
449
450/**
451 * ForestDB iterator status
452 */
453typedef uint8_t fdb_iterator_status_t;
454enum {
455    /**
456     * The last returned doc was retrieved from the main index.
457     */
458    FDB_ITR_IDX = 0x00,
459    /**
460     * The last returned doc was retrieved from the WAL.
461     */
462    FDB_ITR_WAL = 0x01
463};
464
465/**
466 * ForestDB iterator structure definition.
467 */
468struct _fdb_iterator {
469    /**
470     * ForestDB KV store handle.
471     */
472    fdb_kvs_handle *handle;
473    /**
474     * HB+Trie iterator instance.
475     */
476    struct hbtrie_iterator *hbtrie_iterator;
477    /**
478     * B+Tree iterator for sequence number iteration
479     */
480    struct btree_iterator *seqtree_iterator;
481    /**
482     * HB+Trie iterator for sequence number iteration
483     * (for multiple KV instance mode)
484     */
485    struct hbtrie_iterator *seqtrie_iterator;
486    /**
487     * Current seqnum pointed by the iterator.
488     */
489    fdb_seqnum_t _seqnum;
490    /**
491     * WAL Iterator to iterate over the shared sharded global WAL
492     */
493    struct wal_iterator *wal_itr;
494    /**
495     * Cursor instance of WAL iterator.
496     */
497    struct wal_item *tree_cursor;
498    /**
499     * Unique starting AVL node indicating the WAL iterator's start node.
500     */
501    struct wal_item *tree_cursor_start;
502    /**
503     * Previous position of WAL cursor.
504     */
505    struct wal_item *tree_cursor_prev;
506    /**
507     * Iterator start key.
508     */
509    void *start_key;
510    union {
511        /**
512         * Iterator start seqnum.
513         */
514        fdb_seqnum_t start_seqnum;
515        /**
516         * Start key length.
517         */
518        size_t start_keylen;
519    };
520    /**
521     * Iterator end key.
522     */
523    void *end_key;
524    union {
525        /**
526         * Iterator end seqnum.
527         */
528        fdb_seqnum_t end_seqnum;
529        /**
530         * End key length.
531         */
532        size_t end_keylen;
533    };
534    /**
535     * Iterator option.
536     */
537    fdb_iterator_opt_t opt;
538    /**
539     * Iterator cursor direction status.
540     */
541    fdb_iterator_dir_t direction;
542    /**
543     * The last returned document info.
544     */
545    fdb_iterator_status_t status;
546    /**
547     * Was this iterator created on an pre-existing snapshot handle
548     */
549    bool snapshot_handle;
550    /**
551     * Current key pointed by the iterator.
552     */
553    void *_key;
554    /**
555     * Length of key pointed by the iterator.
556     */
557    size_t _keylen;
558    /**
559     * Key offset.
560     */
561    uint64_t _offset;
562    /**
563     * Doc IO handle instance to the correct file.
564     */
565    struct docio_handle *_dhandle;
566    /**
567     * Cursor offset to key, meta and value on disk
568     */
569    uint64_t _get_offset;
570};
571
572struct wal_txn_wrapper;
573
574/**
575 * ForestDB transaction structure definition.
576 */
577struct _fdb_transaction {
578    /**
579     * ForestDB KV store handle.
580     */
581    fdb_kvs_handle *handle;
582    /**
583     * Unique monotonically increasing transaction id to distinguish
584     * items that once belonged to a transaction which has ended.
585     */
586    uint64_t txn_id;
587    /**
588     * Block ID of the last header before the transaction begins.
589     */
590    uint64_t prev_hdr_bid;
591    /**
592     * Rev number of the last header before the transaction begins.
593     */
594    uint64_t prev_revnum;
595    /**
596     * List of dirty WAL items.
597     */
598    struct list *items;
599    /**
600     * Transaction isolation level.
601     */
602    fdb_isolation_level_t isolation;
603    /**
604     * Pointer to transaction wrapper.
605     */
606    struct wal_txn_wrapper *wrapper;
607};
608
609/* Global KV store header for each file
610 */
611struct kvs_header {
612    /**
613     * Monotonically increasing counter to generate KV store IDs.
614     */
615    fdb_kvs_id_t id_counter;
616    /**
617     * The custom comparison function if set by user.
618     */
619    fdb_custom_cmp_variable default_kvs_cmp;
620    /**
621     * A tree linking all KV stores in a file by their KV store name.
622     */
623    struct avl_tree *idx_name;
624    /**
625     * A tree linking all KV stores in file by their ID.
626     */
627    struct avl_tree *idx_id;
628    /**
629     * Boolean to determine if custom compare function for a KV store is set.
630     */
631    uint8_t custom_cmp_enabled;
632    /**
633     * Number of KV store instances
634     */
635    size_t num_kv_stores;
636    /**
637     * lock to protect access to the idx_name and idx_id trees above
638     */
639    spin_t lock;
640};
641
642/** Mapping data for each KV store in DB file.
643 * (global & most fields are persisted in the DB file)
644 */
645#define KVS_FLAG_CUSTOM_CMP (0x1)
646struct kvs_node {
647    /**
648     * Name of the KV store as given by user.
649     */
650    char *kvs_name;
651    /**
652     * Unique KV Store ID generated and permanently assigned.
653     */
654    fdb_kvs_id_t id;
655    /**
656     * Highest sequence number seen in this KV store.
657     */
658    fdb_seqnum_t seqnum;
659    /**
660     * Flags indicating various states of the KV store.
661     */
662    uint64_t flags;
663    /**
664     * Custom compare function set by user (in-memory only).
665     */
666    fdb_custom_cmp_variable custom_cmp;
667    /**
668     * Operational CRUD statistics for this KV store (in-memory only).
669     */
670    struct kvs_ops_stat op_stat;
671    /**
672     * Persisted KV store statistics.
673     */
674    struct kvs_stat stat;
675    /**
676     * Link to the global list of KV stores indexed by store name.
677     */
678    struct avl_node avl_name;
679    /**
680     * Link to the global list of KV stores indexed by store ID.
681     */
682    struct avl_node avl_id;
683};
684
685/**
686 * Type of filename in use.
687 */
688typedef enum {
689    /**
690     * Filename used is a virtual filename (typically in auto compaction).
691     */
692    FDB_VFILENAME = 0,
693    /**
694     * Filename used is the actual filename (typically in manual compaction).
695     */
696    FDB_AFILENAME = 1,
697} fdb_filename_mode_t;
698
699/**
700 * Stale data position & length
701 */
702struct stale_data {
703    /**
704     * Starting offset of the stale data
705     */
706    uint64_t pos;
707    /**
708     * Length of the stale data
709     */
710    uint32_t len;
711    union {
712        struct list_elem le;
713        struct avl_node avl;
714    };
715};
716
717/**
718 * List of stale data
719 */
720struct stale_regions {
721    /**
722     * Number of regions
723     */
724    size_t n_regions;
725    union {
726        /**
727         * Pointer to the array of regions, if n_regions > 1
728         */
729        struct stale_data *regions;
730        /**
731         * Stale region, if n_regions == 1
732         */
733        struct stale_data region;
734    };
735};
736
737#define FDB_FLAG_SEQTREE_USE (0x1)
738#define FDB_FLAG_ROOT_INITIALIZED (0x2)
739#define FDB_FLAG_ROOT_CUSTOM_CMP (0x4)
740
741#ifdef __cplusplus
742}
743#endif
744
745#endif
746