From fdf5ef27fec1368a33801a98bbc5ed3556476979 Mon Sep 17 00:00:00 2001 From: Douglas Rumbaugh Date: Mon, 8 May 2023 12:59:46 -0400 Subject: Began porting source files over from other repository --- include/util/Cursor.h | 89 +++++++++++++++++++++++++++++++++++++++ include/util/base.h | 73 ++++++++++++++++++++++++++++++++ include/util/bf_config.h | 27 ++++++++++++ include/util/hash.h | 61 +++++++++++++++++++++++++++ include/util/internal_record.h | 96 ++++++++++++++++++++++++++++++++++++++++++ include/util/record.h | 65 ++++++++++++++++++++++++++++ include/util/timer.h | 37 ++++++++++++++++ include/util/types.h | 71 +++++++++++++++++++++++++++++++ 8 files changed, 519 insertions(+) create mode 100644 include/util/Cursor.h create mode 100644 include/util/base.h create mode 100644 include/util/bf_config.h create mode 100644 include/util/hash.h create mode 100644 include/util/internal_record.h create mode 100644 include/util/record.h create mode 100644 include/util/timer.h create mode 100644 include/util/types.h (limited to 'include/util') diff --git a/include/util/Cursor.h b/include/util/Cursor.h new file mode 100644 index 0000000..3f5f20f --- /dev/null +++ b/include/util/Cursor.h @@ -0,0 +1,89 @@ +/* + * include/util/Cursor.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * Dong Xie + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include "util/base.h" +#include "util/record.h" +#include "io/PagedFile.h" + +namespace de { +struct Cursor { + record_t *ptr; + const record_t *end; + size_t cur_rec_idx; + size_t rec_cnt; + + friend bool operator==(const Cursor &a, const Cursor &b) { + return a.ptr == b.ptr && a.end == b.end; + } +}; + +static Cursor g_empty_cursor = {0}; + +/* + * Advance the cursor to the next record. If the cursor is backed by an + * iterator, will attempt to advance the iterator once the cursor reaches its + * end and reset the cursor to the beginning of the read page. + * + * If the advance succeeds, ptr will be updated to point to the new record + * and true will be returned. If the advance reaches the end, then ptr will + * be updated to be equal to end, and false will be returned. Iterators will + * not be closed. + */ +inline static bool advance_cursor(Cursor *cur, PagedFileIterator *iter = nullptr) { + cur->ptr++; + cur->cur_rec_idx++; + + if (cur->cur_rec_idx >= cur->rec_cnt) return false; + + if (cur->ptr >= cur->end) { + if (iter && iter->next()) { + cur->ptr = (record_t*)iter->get_item(); + cur->end = cur->ptr + (PAGE_SIZE / sizeof(record_t)); + return true; + } + + return false; + } + return true; +} + +/* + * Process the list of cursors to return the cursor containing the next + * largest element. Does not advance any of the cursors. If current is + * specified, then skip the current head of that cursor during checking. + * This allows for "peaking" at the next largest element after the current + * largest is processed. + */ +inline static Cursor *get_next(std::vector &cursors, Cursor *current=&g_empty_cursor) { + const record_t *min_rec = nullptr; + Cursor *result = &g_empty_cursor; + for (size_t i=0; i< cursors.size(); i++) { + if (cursors[i] == g_empty_cursor) continue; + + const record_t *rec = (&cursors[i] == current) ? cursors[i].ptr + 1 : cursors[i].ptr; + if (rec >= cursors[i].end) continue; + + if (min_rec == nullptr) { + result = &cursors[i]; + min_rec = rec; + continue; + } + + if (*rec < *min_rec) { + result = &cursors[i]; + min_rec = rec; + } + } + + return result; +} + +} diff --git a/include/util/base.h b/include/util/base.h new file mode 100644 index 0000000..1729687 --- /dev/null +++ b/include/util/base.h @@ -0,0 +1,73 @@ +/* + * include/util/base.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * Dong Xie + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include +#include +#include +#include + +namespace de { + +// The correct quantity for use in alignment of buffers to be +// compatible with O_DIRECT +const size_t SECTOR_SIZE = 512; + +// The standard sized block of data (in bytes) for use in IO +// operations. +const size_t PAGE_SIZE = 4096; + +// The size of a cacheline, for alignment purposes. +const size_t CACHELINE_SIZE = 64; + +// The largest representable PageNum. A given file cannot +// have more pages than this. +const size_t MAX_PAGE_COUNT = UINT32_MAX; + +// The largest representable FileId. The file manager cannot +// manage more files than this. +const size_t MAX_FILE_COUNT = UINT32_MAX; + +// The largest representable FrameId. No buffer can be defined with +// more frames than this. +const size_t MAX_FRAME_COUNT = UINT32_MAX; + +// The number of bytes of zeroes available in ZEROBUF. Will be +// a multiple of the parm::PAGE_SIZE. +constexpr size_t ZEROBUF_SIZE = 8 * PAGE_SIZE; + +// A large, preallocated, buffer of zeroes used for pre-allocation +// of pages in a file. +alignas(SECTOR_SIZE) const char ZEROBUF[ZEROBUF_SIZE] = {0}; + + +// alignment code taken from TacoDB (file: tdb_base.h) +template +constexpr T +TYPEALIGN(uint64_t ALIGNVAL, T LEN) { + return (((uint64_t) (LEN) + ((ALIGNVAL) - 1)) & ~((uint64_t) ((ALIGNVAL) - 1))); +} + +#define SHORTALIGN(LEN) TYPEALIGN(2, (LEN)) +#define INTALIGN(LEN) TYPEALIGN(4, (LEN)) +#define LONGALIGN(LEN) TYPEALIGN(8, (LEN)) +#define DOUBLEALIGN(LEN) TYPEALIGN(8, (LEN)) +#define MAXALIGN(LEN) TYPEALIGN(8, (LEN)) +#define CACHELINEALIGN(LEN) TYPEALIGN(CACHELINE_SIZE, (LEN)) +#define MAXALIGN_OF 8 + +// Returns a pointer to the idx'th page contained within a multi-page +// buffer. buffer must be page aligned, and idx must be less than the +// number of pages within the buffer, or the result is undefined. +static inline char *get_page(char *buffer, size_t idx) { + return buffer + (idx * PAGE_SIZE); +} + +} diff --git a/include/util/bf_config.h b/include/util/bf_config.h new file mode 100644 index 0000000..b4d68bc --- /dev/null +++ b/include/util/bf_config.h @@ -0,0 +1,27 @@ +/* + * include/util/bf_config.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * Dong Xie + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include "util/base.h" + +namespace de { + +static double BF_FPR = .01; +static size_t BF_HASH_FUNCS = 7; + +static void BF_SET_FPR(double fpr) { + BF_FPR = fpr; +} + +static void BF_SET_HASHFUNC(size_t func_cnt) { + BF_HASH_FUNCS = func_cnt; +} + +} diff --git a/include/util/hash.h b/include/util/hash.h new file mode 100644 index 0000000..04871dc --- /dev/null +++ b/include/util/hash.h @@ -0,0 +1,61 @@ +/* + * include/util/hash.h + * + * Copyright (C) 2023 Dong Xie + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include +#include + +namespace de { + +// 40343 is a "magic constant" that works well, +// 38299 is another good value. +// Both are primes and have a good distribution of bits. +const uint64_t kHashMagicNum = 40343; + +inline uint64_t rotr64(uint64_t x, size_t n) { + return (((x) >> n) | ((x) << (64 - n))); +} + +inline uint64_t hash(uint64_t input) { + uint64_t local_rand = input; + uint64_t local_rand_hash = 8; + local_rand_hash = 40343 * local_rand_hash + ((local_rand) & 0xFFFF); + local_rand_hash = 40343 * local_rand_hash + ((local_rand >> 16) & 0xFFFF); + local_rand_hash = 40343 * local_rand_hash + ((local_rand >> 32) & 0xFFFF); + local_rand_hash = 40343 * local_rand_hash + (local_rand >> 48); + local_rand_hash = 40343 * local_rand_hash; + return rotr64(local_rand_hash, 43); +} + +inline uint64_t hash_bytes(const char* str, size_t len) { + uint64_t hashState = len; + + for(size_t idx = 0; idx < len; ++idx) { + hashState = kHashMagicNum * hashState + str[idx]; + } + + // The final scrambling helps with short keys that vary only on the high order bits. + // Low order bits are not always well distributed so shift them to the high end, where they'll + // form part of the 14-bit tag. + return rotr64(kHashMagicNum * hashState, 6); +} + +inline uint64_t hash_bytes_with_salt(const char* str, size_t len, uint16_t salt) { + uint64_t hashState = len; + + for(size_t idx = 0; idx < len; ++idx) { + hashState = kHashMagicNum * hashState + str[idx]; + } + + hashState = kHashMagicNum * hashState + salt; + + return rotr64(kHashMagicNum * hashState, 6); +} + +} diff --git a/include/util/internal_record.h b/include/util/internal_record.h new file mode 100644 index 0000000..d898b8b --- /dev/null +++ b/include/util/internal_record.h @@ -0,0 +1,96 @@ +/* + * include/util/internal_record.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once +#pragma once + +#include "util/record.h" +#include "util/types.h" + +/* + * Utility functions for use in handling internal nodes within an ISAM + * tree. + */ + +namespace de { + +struct ISAMTreeInternalNodeHeader { + PageNum next_sibling; // INVALID_PNUM this is the last node on a level + PageNum prev_sibling; // INVALID_PNUM if this is the first node on a level + size_t leaf_rec_cnt; // number of records in leaf nodes under this node + size_t internal_rec_cnt; // number of internal records in this node +}; + +/* + * The total (aligned) size of an ISAMTreeInternalNodeHeader object. + */ +static constexpr PageOffset ISAMTreeInternalNodeHeaderSize = MAXALIGN(sizeof(ISAMTreeInternalNodeHeader)); + +/* + * The number of bytes occupied by an ISAM tree internal record, including alignment bytes. + */ +static constexpr size_t internal_record_size = sizeof(key_t) + MAXALIGN(sizeof(PageNum)); + +/* + * The maximum number of internal records that can be stored in an internal + * node, accounting for alignment and the node header. + */ +static constexpr size_t internal_records_per_page = (PAGE_SIZE - ISAMTreeInternalNodeHeaderSize) / internal_record_size; + +/* + * Format an internal record, starting in the first byte of buffer, with the + * specified key and target page number. If either buffer or key refer to + * memory regions of insufficient size, the results are undefined. + */ +static inline void build_internal_record(char *buffer, const char *key, PageNum target_page) { + memcpy(buffer, key, sizeof(key_t)); + memcpy(buffer + sizeof(key_t), &target_page, sizeof(PageNum)); +} + +/* + * Return the idx'th internal record within an internal node. + * internal_page_buffer must refer to the first byte of a page containing a + * full internal node, including the header. The returned value is undefined if + * idx is greater than or equal to the number of internal records within the + * node. + */ +static inline char *get_internal_record(char *internal_page_buffer, size_t idx) { + return internal_page_buffer + ISAMTreeInternalNodeHeaderSize + internal_record_size * idx; +} + +/* + * Return a pointer to the key contained within an internal record, pointed + * to by buffer. Buffer must point to the beginning of a valid internal record, + * or the result of this function is undefined. + */ +static inline const char *get_internal_key(const char *buffer) { + return buffer; +} + +/* + * Return the Page Number (value) of an internal record, pointed to by buffer. + * Buffer must point to the beginning of a valid internal record, or the result + * of this function is undefined. + */ +static inline PageNum get_internal_value(const char *buffer) { + return *((PageNum *) (buffer + sizeof(key_t))); +} + +/* + * Return a pointer to the header of an ISAM Tree internal node, referred to by + * buffer. If buffer contains multiple nodes, a specific node can be requested + * using the idx parameter, otherwise the header of the first node will be returned. + * Buffer must point to the beginning of a valid ISAM Tree internal node, and idx + * must be less than the number of internal nodes within the buffer, or the + * returned value is undefined. + */ +static inline ISAMTreeInternalNodeHeader *get_header(char *buffer, size_t idx=0) { + return (ISAMTreeInternalNodeHeader *) get_page(buffer, idx); +} + +} diff --git a/include/util/record.h b/include/util/record.h new file mode 100644 index 0000000..0ba0f97 --- /dev/null +++ b/include/util/record.h @@ -0,0 +1,65 @@ +/* + * include/util/record.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * Dong Xie + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include + +#include "util/base.h" + +namespace de { + +typedef uint32_t hdr_t; +typedef uint64_t key_t; +typedef uint32_t value_t; +typedef uint64_t weight_t; + +struct record_t { + key_t key; + value_t value; + hdr_t header; + weight_t weight; + + inline bool match(key_t k, value_t v, bool is_tombstone) const { + return (key == k) && (value == v) && ((header & 1) == is_tombstone); + } + + inline void set_delete_status() { + header |= 2; + } + + inline bool get_delete_status() const { + return header & 2; + } + + inline bool is_tombstone() const { + return header & 1; + } + + inline int match(const record_t* other) const { + return key == other->key && value == other->value; + } + + inline bool operator<(const record_t& other) const { + return key < other.key || (key == other.key && value < other.value); + } + + inline bool lt(const key_t& k, const value_t& v) const { + return key < k || (key == k && value < v); + } +}; + +static_assert(sizeof(record_t) == 24, "Record is not 24 bytes long."); + +static bool memtable_record_cmp(const record_t& a, const record_t& b) { + return (a.key < b.key) || (a.key == b.key && a.value < b.value) + || (a.key == b.key && a.value == b.value && a.header < b.header); +} + +} diff --git a/include/util/timer.h b/include/util/timer.h new file mode 100644 index 0000000..a9784a8 --- /dev/null +++ b/include/util/timer.h @@ -0,0 +1,37 @@ +/* + * include/util/timer.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * + * All rights reserved. Published under the Modified BSD License. + * + */ +#pragma once + +#include + +#ifdef ENABLE_TIMER +#define TIMER_INIT() \ + auto timer_start = std::chrono::high_resolution_clock::now(); \ + auto timer_stop = std::chrono::high_resolution_clock::now(); + +#define TIMER_START() \ + timer_start = std::chrono::high_resolution_clock::now() + +#define TIMER_STOP() \ + timer_stop = std::chrono::high_resolution_clock::now() + +#define TIMER_RESULT() \ + std::chrono::duration_cast(timer_stop - timer_start).count() + +#else + #define TIMER_INIT() \ + do {} while(0) + #define TIMER_START() \ + do {} while(0) + #define TIMER_STOP() \ + do {} while(0) + #define TIMER_RESULT() \ + 0l +#endif + diff --git a/include/util/types.h b/include/util/types.h new file mode 100644 index 0000000..63da3fa --- /dev/null +++ b/include/util/types.h @@ -0,0 +1,71 @@ +/* + * include/util/types.h + * + * Copyright (C) 2023 Douglas Rumbaugh + * + * All rights reserved. Published under the Modified BSD License. + * + * A centralized header file for various datatypes used throughout the + * code base. There are a few very specific types, such as header formats, + * that are defined within the header files that make direct use of them, + * but all generally usable, simple types are defined here. + * + */ +#pragma once + +#include +#include +#include +#include + +#include "util/base.h" + +namespace de { + +using std::byte; + +// Represents a page offset within a specific file (physical or virtual) +typedef uint32_t PageNum; + +// Byte offset within a page. Also used for lengths of records, etc., +// within the codebase. size_t isn't necessary, as the maximum offset +// is only parm::PAGE_SIZE +typedef uint16_t PageOffset; + +// A unique identifier for a frame within a buffer or cache. +typedef int32_t FrameId; + +// A unique timestamp for use in MVCC concurrency control. Currently stored in +// record headers, but not used by anything. +typedef uint32_t Timestamp; +const Timestamp TIMESTAMP_MIN = 0; +const Timestamp TIMESTAMP_MAX = UINT32_MAX; + +// Invalid values for various IDs. Used throughout the code base to indicate +// uninitialized values and error conditions. +const PageNum INVALID_PNUM = 0; +const FrameId INVALID_Fshid = -1; + +// An ID for a given shard within the index. The level_idx is the index +// in the memory_levels and disk_levels vectors corresponding to the +// shard, and the shard_idx is the index with the level (always 0 in the +// case of leveling). Note that the two vectors of levels are treated +// as a contiguous index space. +struct ShardID { + ssize_t level_idx; + ssize_t shard_idx; + + friend bool operator==(const ShardID &shid1, const ShardID &shid2) { + return shid1.level_idx == shid2.level_idx && shid1.shard_idx == shid2.shard_idx; + } +}; + +const ShardID INVALID_SHID = {-1, -1}; + +struct SampleRange { + ShardID run_id; + size_t low; + size_t high; +}; + +} -- cgit v1.2.3