xref: /5.5.2/forestdb/src/internal_types.h (revision b6e47bcd)
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/**
223 * ForestDB file handle definition.
224 */
225struct _fdb_file_handle {
226    /**
227     * The root KV store handle.
228     */
229    fdb_kvs_handle *root;
230    /**
231     * List of opened default KV store handles
232     * (except for the root handle).
233     */
234    struct list *handles;
235    /**
236     * List of custom compare functions assigned by user
237     */
238    struct list *cmp_func_list;
239    /**
240     * Flags for the file handle.
241     */
242    uint64_t flags;
243    /**
244     * Spin lock for the file handle.
245     */
246    spin_t lock;
247};
248
249/**
250 * ForestDB KV store key comparison callback context
251 */
252struct _fdb_key_cmp_info {
253    /**
254     * ForestDB KV store level config.
255     */
256    fdb_kvs_config kvs_config;
257    /**
258     * KV store information.
259     */
260    struct kvs_info *kvs;
261};
262
263/**
264 * ForestDB KV store handle definition.
265 */
266struct _fdb_kvs_handle {
267
268    _fdb_kvs_handle& operator=(const _fdb_kvs_handle& kv_handle) {
269        kvs_config = kv_handle.kvs_config;
270        kvs = kv_handle.kvs;
271        op_stats = kv_handle.op_stats;
272        fhandle = kv_handle.fhandle;
273        trie = kv_handle.trie;
274        staletree = kv_handle.staletree;
275        if (kv_handle.kvs) {
276            seqtrie = kv_handle.seqtrie;
277        } else {
278            seqtree = kv_handle.seqtree;
279        }
280        file = kv_handle.file;
281        dhandle = kv_handle.dhandle;
282        bhandle = kv_handle.bhandle;
283        btreeblkops = kv_handle.btreeblkops;
284        fileops = kv_handle.fileops;
285        config = kv_handle.config;
286        log_callback = kv_handle.log_callback;
287        atomic_store_uint64_t(&cur_header_revnum, kv_handle.cur_header_revnum);
288        atomic_store_uint64_t(&last_hdr_bid, kv_handle.last_hdr_bid);
289        last_wal_flush_hdr_bid = kv_handle.last_wal_flush_hdr_bid;
290        kv_info_offset = kv_handle.kv_info_offset;
291        shandle = kv_handle.shandle;
292        seqnum = kv_handle.seqnum;
293        max_seqnum = kv_handle.max_seqnum;
294        filename = kv_handle.filename;
295        txn = kv_handle.txn;
296        atomic_store_uint8_t(&handle_busy,
297                             atomic_get_uint8_t(&kv_handle.handle_busy));
298        dirty_updates = kv_handle.dirty_updates;
299        node = kv_handle.node;
300        num_iterators = kv_handle.num_iterators;
301        return *this;
302    }
303
304    // TODO: Move these variables to private members as we refactor the code in C++.
305
306    /**
307     * ForestDB KV store level config. (Please retain as first struct member)
308     */
309    fdb_kvs_config kvs_config;
310    /**
311     * KV store information. (Please retain as second struct member)
312     */
313    struct kvs_info *kvs;
314    /**
315     * Operational statistics for this kv store.
316     */
317    struct kvs_ops_stat *op_stats;
318    /**
319     * Pointer to the corresponding file handle.
320     */
321    fdb_file_handle *fhandle;
322    /**
323     * HB+-Tree Trie instance.
324     */
325    struct hbtrie *trie;
326    /**
327     * Stale block B+-Tree instance.
328     * Maps from 'commit revision number' to 'stale block info' system document.
329     */
330    struct btree *staletree;
331    /**
332     * Sequence B+-Tree instance.
333     */
334    union {
335        struct btree *seqtree; // single KV instance mode
336        struct hbtrie *seqtrie; // multi KV instance mode
337    };
338    /**
339     * File manager instance.
340     */
341    struct filemgr *file;
342    /**
343     * Doc IO handle instance.
344     */
345    struct docio_handle *dhandle;
346    /**
347     * B+-Tree handle instance.
348     */
349    struct btreeblk_handle *bhandle;
350    /**
351     * B+-Tree block operation handle.
352     */
353    struct btree_blk_ops *btreeblkops;
354    /**
355     * File manager IO operation handle.
356     */
357    struct filemgr_ops *fileops;
358    /**
359     * ForestDB file level config.
360     */
361    fdb_config config;
362    /**
363     * Error logging callback.
364     */
365    err_log_callback log_callback;
366    /**
367     * File header revision number.
368     */
369    atomic_uint64_t cur_header_revnum;
370    /**
371     * Header revision number of rollback point.
372     */
373    uint64_t rollback_revnum;
374    /**
375     * Last header's block ID.
376     * Why Atomic?
377     * reader thread in fdb_sync_db_header can update last_hdr_bid while
378     * writer thread sharing same file handle can get_oldest_active_header()
379     * as part of its sb_reclaim_reusable_blocks()
380     */
381    atomic_uint64_t last_hdr_bid;
382    /**
383     * Block ID of a header created with most recent WAL flush.
384     */
385    uint64_t last_wal_flush_hdr_bid;
386    /**
387     * File offset of a document containing KV instance info.
388     */
389    uint64_t kv_info_offset;
390    /**
391     * Snapshot Information.
392     */
393    struct snap_handle *shandle;
394    /**
395     * KV store's current sequence number.
396     */
397    fdb_seqnum_t seqnum;
398    /**
399     * KV store's max sequence number for snapshot or rollback.
400     */
401    fdb_seqnum_t max_seqnum;
402    /**
403     * Virtual filename (DB instance filename given by users).
404     */
405    char *filename;
406    /**
407     * Transaction handle.
408     */
409    fdb_txn *txn;
410    /**
411     * Atomic flag to detect if handles are being shared among threads.
412     */
413    atomic_uint8_t handle_busy;
414    /**
415     * Flag that indicates whether this handle made dirty updates or not.
416     */
417    uint8_t dirty_updates;
418    /**
419     * List element that will be inserted into 'handles' list in the root handle.
420     */
421    struct kvs_opened_node *node;
422    /**
423     * Number of active iterator instances created from this handle
424     */
425    uint32_t num_iterators;
426};
427
428struct hbtrie_iterator;
429struct avl_tree;
430struct avl_node;
431
432/**
433 * ForestDB iterator cursor movement direction
434 */
435typedef uint8_t fdb_iterator_dir_t;
436enum {
437    /**
438     * Iterator cursor default.
439     */
440    FDB_ITR_DIR_NONE = 0x00,
441    /**
442     * Iterator cursor moving forward
443     */
444    FDB_ITR_FORWARD = 0x01,
445    /**
446     * Iterator cursor moving backwards
447     */
448    FDB_ITR_REVERSE = 0x02
449};
450
451/**
452 * ForestDB iterator status
453 */
454typedef uint8_t fdb_iterator_status_t;
455enum {
456    /**
457     * The last returned doc was retrieved from the main index.
458     */
459    FDB_ITR_IDX = 0x00,
460    /**
461     * The last returned doc was retrieved from the WAL.
462     */
463    FDB_ITR_WAL = 0x01
464};
465
466/**
467 * ForestDB iterator structure definition.
468 */
469struct _fdb_iterator {
470    /**
471     * ForestDB KV store handle.
472     */
473    fdb_kvs_handle *handle;
474    /**
475     * HB+Trie iterator instance.
476     */
477    struct hbtrie_iterator *hbtrie_iterator;
478    /**
479     * B+Tree iterator for sequence number iteration
480     */
481    struct btree_iterator *seqtree_iterator;
482    /**
483     * HB+Trie iterator for sequence number iteration
484     * (for multiple KV instance mode)
485     */
486    struct hbtrie_iterator *seqtrie_iterator;
487    /**
488     * Current seqnum pointed by the iterator.
489     */
490    fdb_seqnum_t _seqnum;
491    /**
492     * WAL Iterator to iterate over the shared sharded global WAL
493     */
494    struct wal_iterator *wal_itr;
495    /**
496     * Cursor instance of WAL iterator.
497     */
498    struct wal_item *tree_cursor;
499    /**
500     * Unique starting AVL node indicating the WAL iterator's start node.
501     */
502    struct wal_item *tree_cursor_start;
503    /**
504     * Previous position of WAL cursor.
505     */
506    struct wal_item *tree_cursor_prev;
507    /**
508     * Iterator start key.
509     */
510    void *start_key;
511    union {
512        /**
513         * Iterator start seqnum.
514         */
515        fdb_seqnum_t start_seqnum;
516        /**
517         * Start key length.
518         */
519        size_t start_keylen;
520    };
521    /**
522     * Iterator end key.
523     */
524    void *end_key;
525    union {
526        /**
527         * Iterator end seqnum.
528         */
529        fdb_seqnum_t end_seqnum;
530        /**
531         * End key length.
532         */
533        size_t end_keylen;
534    };
535    /**
536     * Iterator option.
537     */
538    fdb_iterator_opt_t opt;
539    /**
540     * Iterator cursor direction status.
541     */
542    fdb_iterator_dir_t direction;
543    /**
544     * The last returned document info.
545     */
546    fdb_iterator_status_t status;
547    /**
548     * Was this iterator created on an pre-existing snapshot handle
549     */
550    bool snapshot_handle;
551    /**
552     * Current key pointed by the iterator.
553     */
554    void *_key;
555    /**
556     * Length of key pointed by the iterator.
557     */
558    size_t _keylen;
559    /**
560     * Key offset.
561     */
562    uint64_t _offset;
563    /**
564     * Doc IO handle instance to the correct file.
565     */
566    struct docio_handle *_dhandle;
567    /**
568     * Cursor offset to key, meta and value on disk
569     */
570    uint64_t _get_offset;
571};
572
573struct wal_txn_wrapper;
574
575/**
576 * ForestDB transaction structure definition.
577 */
578struct _fdb_transaction {
579    /**
580     * ForestDB KV store handle.
581     */
582    fdb_kvs_handle *handle;
583    /**
584     * Unique monotonically increasing transaction id to distinguish
585     * items that once belonged to a transaction which has ended.
586     */
587    uint64_t txn_id;
588    /**
589     * Block ID of the last header before the transaction begins.
590     */
591    uint64_t prev_hdr_bid;
592    /**
593     * Rev number of the last header before the transaction begins.
594     */
595    uint64_t prev_revnum;
596    /**
597     * List of dirty WAL items.
598     */
599    struct list *items;
600    /**
601     * Transaction isolation level.
602     */
603    fdb_isolation_level_t isolation;
604    /**
605     * Pointer to transaction wrapper.
606     */
607    struct wal_txn_wrapper *wrapper;
608};
609
610/* Global KV store header for each file
611 */
612struct kvs_header {
613    /**
614     * Monotonically increasing counter to generate KV store IDs.
615     */
616    fdb_kvs_id_t id_counter;
617    /**
618     * The custom comparison function if set by user.
619     */
620    fdb_custom_cmp_variable default_kvs_cmp;
621    /**
622     * A tree linking all KV stores in a file by their KV store name.
623     */
624    struct avl_tree *idx_name;
625    /**
626     * A tree linking all KV stores in file by their ID.
627     */
628    struct avl_tree *idx_id;
629    /**
630     * Boolean to determine if custom compare function for a KV store is set.
631     */
632    uint8_t custom_cmp_enabled;
633    /**
634     * Number of KV store instances
635     */
636    size_t num_kv_stores;
637    /**
638     * lock to protect access to the idx_name and idx_id trees above
639     */
640    spin_t lock;
641};
642
643/** Mapping data for each KV store in DB file.
644 * (global & most fields are persisted in the DB file)
645 */
646#define KVS_FLAG_CUSTOM_CMP (0x1)
647struct kvs_node {
648    /**
649     * Name of the KV store as given by user.
650     */
651    char *kvs_name;
652    /**
653     * Unique KV Store ID generated and permanently assigned.
654     */
655    fdb_kvs_id_t id;
656    /**
657     * Highest sequence number seen in this KV store.
658     */
659    fdb_seqnum_t seqnum;
660    /**
661     * Flags indicating various states of the KV store.
662     */
663    uint64_t flags;
664    /**
665     * Custom compare function set by user (in-memory only).
666     */
667    fdb_custom_cmp_variable custom_cmp;
668    /**
669     * Operational CRUD statistics for this KV store (in-memory only).
670     */
671    struct kvs_ops_stat op_stat;
672    /**
673     * Persisted KV store statistics.
674     */
675    struct kvs_stat stat;
676    /**
677     * Link to the global list of KV stores indexed by store name.
678     */
679    struct avl_node avl_name;
680    /**
681     * Link to the global list of KV stores indexed by store ID.
682     */
683    struct avl_node avl_id;
684};
685
686/**
687 * Type of filename in use.
688 */
689typedef enum {
690    /**
691     * Filename used is a virtual filename (typically in auto compaction).
692     */
693    FDB_VFILENAME = 0,
694    /**
695     * Filename used is the actual filename (typically in manual compaction).
696     */
697    FDB_AFILENAME = 1,
698} fdb_filename_mode_t;
699
700/**
701 * Stale data position & length
702 */
703struct stale_data {
704    /**
705     * Starting offset of the stale data
706     */
707    uint64_t pos;
708    /**
709     * Length of the stale data
710     */
711    uint32_t len;
712    union {
713        struct list_elem le;
714        struct avl_node avl;
715    };
716};
717
718/**
719 * List of stale data
720 */
721struct stale_regions {
722    /**
723     * Number of regions
724     */
725    size_t n_regions;
726    union {
727        /**
728         * Pointer to the array of regions, if n_regions > 1
729         */
730        struct stale_data *regions;
731        /**
732         * Stale region, if n_regions == 1
733         */
734        struct stale_data region;
735    };
736};
737
738#define FDB_FLAG_SEQTREE_USE (0x1)
739#define FDB_FLAG_ROOT_INITIALIZED (0x2)
740#define FDB_FLAG_ROOT_CUSTOM_CMP (0x4)
741#define FDB_FLAG_SUCCESSFULLY_COMPACTED (0x8)
742
743#ifdef __cplusplus
744}
745#endif
746
747#endif
748