xref: /4.6.0/forestdb/src/internal_types.h (revision 5f874bbf)
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        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     */
376    uint64_t last_hdr_bid;
377    /**
378     * Block ID of a header created with most recent WAL flush.
379     */
380    uint64_t last_wal_flush_hdr_bid;
381    /**
382     * File offset of a document containing KV instance info.
383     */
384    uint64_t kv_info_offset;
385    /**
386     * Snapshot Information.
387     */
388    struct snap_handle *shandle;
389    /**
390     * KV store's current sequence number.
391     */
392    fdb_seqnum_t seqnum;
393    /**
394     * KV store's max sequence number for snapshot or rollback.
395     */
396    fdb_seqnum_t max_seqnum;
397    /**
398     * Virtual filename (DB instance filename given by users).
399     */
400    char *filename;
401    /**
402     * Transaction handle.
403     */
404    fdb_txn *txn;
405    /**
406     * Atomic flag to detect if handles are being shared among threads.
407     */
408    atomic_uint8_t handle_busy;
409    /**
410     * Flag that indicates whether this handle made dirty updates or not.
411     */
412    uint8_t dirty_updates;
413    /**
414     * List element that will be inserted into 'handles' list in the root handle.
415     */
416    struct kvs_opened_node *node;
417    /**
418     * Number of active iterator instances created from this handle
419     */
420    uint32_t num_iterators;
421};
422
423struct hbtrie_iterator;
424struct avl_tree;
425struct avl_node;
426
427/**
428 * ForestDB iterator cursor movement direction
429 */
430typedef uint8_t fdb_iterator_dir_t;
431enum {
432    /**
433     * Iterator cursor default.
434     */
435    FDB_ITR_DIR_NONE = 0x00,
436    /**
437     * Iterator cursor moving forward
438     */
439    FDB_ITR_FORWARD = 0x01,
440    /**
441     * Iterator cursor moving backwards
442     */
443    FDB_ITR_REVERSE = 0x02
444};
445
446/**
447 * ForestDB iterator status
448 */
449typedef uint8_t fdb_iterator_status_t;
450enum {
451    /**
452     * The last returned doc was retrieved from the main index.
453     */
454    FDB_ITR_IDX = 0x00,
455    /**
456     * The last returned doc was retrieved from the WAL.
457     */
458    FDB_ITR_WAL = 0x01
459};
460
461/**
462 * ForestDB iterator structure definition.
463 */
464struct _fdb_iterator {
465    /**
466     * ForestDB KV store handle.
467     */
468    fdb_kvs_handle *handle;
469    /**
470     * HB+Trie iterator instance.
471     */
472    struct hbtrie_iterator *hbtrie_iterator;
473    /**
474     * B+Tree iterator for sequence number iteration
475     */
476    struct btree_iterator *seqtree_iterator;
477    /**
478     * HB+Trie iterator for sequence number iteration
479     * (for multiple KV instance mode)
480     */
481    struct hbtrie_iterator *seqtrie_iterator;
482    /**
483     * Current seqnum pointed by the iterator.
484     */
485    fdb_seqnum_t _seqnum;
486    /**
487     * WAL Iterator to iterate over the shared sharded global WAL
488     */
489    struct wal_iterator *wal_itr;
490    /**
491     * Cursor instance of WAL iterator.
492     */
493    struct wal_item *tree_cursor;
494    /**
495     * Unique starting AVL node indicating the WAL iterator's start node.
496     */
497    struct wal_item *tree_cursor_start;
498    /**
499     * Previous position of WAL cursor.
500     */
501    struct wal_item *tree_cursor_prev;
502    /**
503     * Iterator start key.
504     */
505    void *start_key;
506    union {
507        /**
508         * Iterator start seqnum.
509         */
510        fdb_seqnum_t start_seqnum;
511        /**
512         * Start key length.
513         */
514        size_t start_keylen;
515    };
516    /**
517     * Iterator end key.
518     */
519    void *end_key;
520    union {
521        /**
522         * Iterator end seqnum.
523         */
524        fdb_seqnum_t end_seqnum;
525        /**
526         * End key length.
527         */
528        size_t end_keylen;
529    };
530    /**
531     * Iterator option.
532     */
533    fdb_iterator_opt_t opt;
534    /**
535     * Iterator cursor direction status.
536     */
537    fdb_iterator_dir_t direction;
538    /**
539     * The last returned document info.
540     */
541    fdb_iterator_status_t status;
542    /**
543     * Was this iterator created on an pre-existing snapshot handle
544     */
545    bool snapshot_handle;
546    /**
547     * Current key pointed by the iterator.
548     */
549    void *_key;
550    /**
551     * Length of key pointed by the iterator.
552     */
553    size_t _keylen;
554    /**
555     * Key offset.
556     */
557    uint64_t _offset;
558    /**
559     * Doc IO handle instance to the correct file.
560     */
561    struct docio_handle *_dhandle;
562    /**
563     * Cursor offset to key, meta and value on disk
564     */
565    uint64_t _get_offset;
566};
567
568struct wal_txn_wrapper;
569
570/**
571 * ForestDB transaction structure definition.
572 */
573struct _fdb_transaction {
574    /**
575     * ForestDB KV store handle.
576     */
577    fdb_kvs_handle *handle;
578    /**
579     * Unique monotonically increasing transaction id to distinguish
580     * items that once belonged to a transaction which has ended.
581     */
582    uint64_t txn_id;
583    /**
584     * Block ID of the last header before the transaction begins.
585     */
586    uint64_t prev_hdr_bid;
587    /**
588     * Rev number of the last header before the transaction begins.
589     */
590    uint64_t prev_revnum;
591    /**
592     * List of dirty WAL items.
593     */
594    struct list *items;
595    /**
596     * Transaction isolation level.
597     */
598    fdb_isolation_level_t isolation;
599    /**
600     * Pointer to transaction wrapper.
601     */
602    struct wal_txn_wrapper *wrapper;
603};
604
605/* Global KV store header for each file
606 */
607struct kvs_header {
608    /**
609     * Monotonically increasing counter to generate KV store IDs.
610     */
611    fdb_kvs_id_t id_counter;
612    /**
613     * The custom comparison function if set by user.
614     */
615    fdb_custom_cmp_variable default_kvs_cmp;
616    /**
617     * A tree linking all KV stores in a file by their KV store name.
618     */
619    struct avl_tree *idx_name;
620    /**
621     * A tree linking all KV stores in file by their ID.
622     */
623    struct avl_tree *idx_id;
624    /**
625     * Boolean to determine if custom compare function for a KV store is set.
626     */
627    uint8_t custom_cmp_enabled;
628    /**
629     * Number of KV store instances
630     */
631    size_t num_kv_stores;
632    /**
633     * lock to protect access to the idx_name and idx_id trees above
634     */
635    spin_t lock;
636};
637
638/** Mapping data for each KV store in DB file.
639 * (global & most fields are persisted in the DB file)
640 */
641#define KVS_FLAG_CUSTOM_CMP (0x1)
642struct kvs_node {
643    /**
644     * Name of the KV store as given by user.
645     */
646    char *kvs_name;
647    /**
648     * Unique KV Store ID generated and permanently assigned.
649     */
650    fdb_kvs_id_t id;
651    /**
652     * Highest sequence number seen in this KV store.
653     */
654    fdb_seqnum_t seqnum;
655    /**
656     * Flags indicating various states of the KV store.
657     */
658    uint64_t flags;
659    /**
660     * Custom compare function set by user (in-memory only).
661     */
662    fdb_custom_cmp_variable custom_cmp;
663    /**
664     * Operational CRUD statistics for this KV store (in-memory only).
665     */
666    struct kvs_ops_stat op_stat;
667    /**
668     * Persisted KV store statistics.
669     */
670    struct kvs_stat stat;
671    /**
672     * Link to the global list of KV stores indexed by store name.
673     */
674    struct avl_node avl_name;
675    /**
676     * Link to the global list of KV stores indexed by store ID.
677     */
678    struct avl_node avl_id;
679};
680
681/**
682 * Type of filename in use.
683 */
684typedef enum {
685    /**
686     * Filename used is a virtual filename (typically in auto compaction).
687     */
688    FDB_VFILENAME = 0,
689    /**
690     * Filename used is the actual filename (typically in manual compaction).
691     */
692    FDB_AFILENAME = 1,
693} fdb_filename_mode_t;
694
695/**
696 * Stale data position & length
697 */
698struct stale_data {
699    /**
700     * Starting offset of the stale data
701     */
702    uint64_t pos;
703    /**
704     * Length of the stale data
705     */
706    uint32_t len;
707    union {
708        struct list_elem le;
709        struct avl_node avl;
710    };
711};
712
713/**
714 * List of stale data
715 */
716struct stale_regions {
717    /**
718     * Number of regions
719     */
720    size_t n_regions;
721    union {
722        /**
723         * Pointer to the array of regions, if n_regions > 1
724         */
725        struct stale_data *regions;
726        /**
727         * Stale region, if n_regions == 1
728         */
729        struct stale_data region;
730    };
731};
732
733#define FDB_FLAG_SEQTREE_USE (0x1)
734#define FDB_FLAG_ROOT_INITIALIZED (0x2)
735#define FDB_FLAG_ROOT_CUSTOM_CMP (0x4)
736
737#ifdef __cplusplus
738}
739#endif
740
741#endif
742