btree_impl.h

Go to the documentation of this file.

/*
 * (c) Copyright 2011-2014, Hewlett-Packard Development Company, LP
 */

#ifndef __BTREE_IMPL_H
#define __BTREE_IMPL_H

#include "w_defines.h"

#include "btree.h"
#include "btree_verify.h"
#include "w_okvl.h"
#include "xct.h"

class btree_impl : public smlevel_0 {
public:

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    static rc_t _ux_get_page_and_status
            (StoreID store,
             const w_keystr_t& key,
             bool& need_lock, slotid_t& slot, bool& found, bool& took_XN, bool& is_ghost, btree_page_h& leaf);

    static rc_t _ux_insert(
            StoreID store,
            const w_keystr_t& key,
            const cvec_t& elem);

    static rc_t _ux_insert_core(
            StoreID store,
            const w_keystr_t& key,
            const cvec_t& elem);

    static rc_t _ux_insert_core_tail
            (StoreID store,
             const w_keystr_t& key, const cvec_t& el,
             bool& need_lock, slotid_t& slot, bool& found, bool& alreay_took_XN,
             bool& is_ghost, btree_page_h& leaf);

    static rc_t _ux_update(
            StoreID store,
            const w_keystr_t& key,
            const cvec_t& elem);

    static rc_t _ux_update_core(
            StoreID store,
            const w_keystr_t& key,
            const cvec_t& elem);

    static rc_t _ux_update_core_tail(
            StoreID store,
            const w_keystr_t& key, const cvec_t& elem,
            bool& need_lock, slotid_t& slot, bool& found, bool& is_ghost,
            btree_page_h& leaf);

    static rc_t _ux_put(
            StoreID store,
            const w_keystr_t& key,
            const cvec_t& elem);

    static rc_t _ux_put_core(
            StoreID store,
            const w_keystr_t& key,
            const cvec_t& elem);

    static rc_t _ux_overwrite(
            StoreID store,
            const w_keystr_t& key,
            const char* el, smsize_t offset, smsize_t elen);

    static rc_t _ux_overwrite_core(
            StoreID store,
            const w_keystr_t& key,
            const char* el, smsize_t offset, smsize_t elen);

    static rc_t _sx_reserve_ghost(
            btree_page_h& leaf, const w_keystr_t& key, int elem_len);

    static rc_t _ux_reserve_ghost_core(
            btree_page_h& leaf, const w_keystr_t& key, int elem_len);

    static rc_t _ux_remove(
            StoreID store,
            const w_keystr_t& key);

    static rc_t _ux_remove_core(StoreID store, const w_keystr_t& key);

    static rc_t _ux_undo_ghost_mark(
            StoreID store,
            const w_keystr_t& key);

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    enum traverse_mode_t {
        t_fence_contain,
        t_fence_low_match,
        t_fence_high_match
    };
    enum slot_follow_t {
        t_follow_invalid = -3,
        t_follow_foster = -2,
        t_follow_pid0 = -1
        // 0 to nrecs-1 is child
    };

    static rc_t _ux_traverse(
            StoreID store,
            const w_keystr_t& key,
            traverse_mode_t traverse_mode,
            latch_mode_t leaf_latch_mode,
            btree_page_h& leaf,
            bool allow_retry = true
                            );

    static rc_t _ux_traverse_recurse(
            btree_page_h& start,
            const w_keystr_t& key,
            traverse_mode_t traverse_mode,
            latch_mode_t leaf_latch_mode,
            btree_page_h& leaf,
            PageID& leaf_pid_causing_failed_upgrade
                                    );

    static inline void _ux_traverse_search(btree_impl::traverse_mode_t traverse_mode,
                                           btree_page_h* current,
                                           const w_keystr_t& key,
                                           bool& this_is_the_leaf_page, slot_follow_t& slot_to_follow);

    static rc_t _ux_traverse_try_eager_adopt(btree_page_h& current, PageID next_pid);

    static rc_t _ux_traverse_try_opportunistic_adopt(btree_page_h& current, btree_page_h& next);

    static rc_t _ux_lookup(
            StoreID store,
            const w_keystr_t& key,
            bool& found,
            void* el,
            smsize_t& elen
                          );

    static rc_t _ux_lookup_core(
            StoreID store,
            const w_keystr_t& key,
            bool& found,
            void* el,
            smsize_t& elen
                               );

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    static rc_t _sx_norec_alloc(btree_page_h& page, PageID& new_page_id);

    static rc_t _ux_norec_alloc_core(btree_page_h& page, PageID& new_page_id);

    static rc_t _sx_adopt_foster_all(
            btree_page_h& root, bool recursive = false);

    static rc_t _sx_adopt_foster_all_core(
            btree_page_h& parent, bool is_root, bool recursive);

    static rc_t _sx_adopt_foster(btree_page_h& parent, btree_page_h& child);

    static rc_t _ux_adopt_foster_core(btree_page_h& parent,
                                      btree_page_h& child, const w_keystr_t& new_child_key);

    static rc_t _sx_opportunistic_adopt_foster(btree_page_h& parent, btree_page_h& child,
                                               bool& pushedup);

    static rc_t _sx_adopt_foster_sweep(btree_page_h& parent_arg);

    static rc_t _sx_adopt_foster_sweep_approximate(btree_page_h& parent, PageID surely_need_child_pid);

    static void _ux_adopt_foster_apply_parent(btree_page_h& parent_arg,
                                              PageID new_child_pid, lsn_t new_child_emlsn,
                                              const w_keystr_t& new_child_key);

    static void _ux_adopt_foster_apply_child(btree_page_h& child);

    static rc_t _sx_split_foster(btree_page_h& page,
                                 PageID& new_page_id, const w_keystr_t& triggering_key);

    static rc_t _sx_split_if_needed(btree_page_h& page,
                                    const w_keystr_t& new_key);

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    static rc_t _ux_lock_key(
            const StoreID& store,
            btree_page_h& leaf,
            const w_keystr_t& key,
            latch_mode_t latch_mode,
            const okvl_mode& lock_mode,
            bool check_only
                            );

    static rc_t _ux_lock_key(
            const StoreID& store,
            btree_page_h& leaf,
            const void* keystr,
            size_t keylen,
            latch_mode_t latch_mode,
            const okvl_mode& lock_mode,
            bool check_only
                            );

    static rc_t _ux_lock_range(const StoreID& store,
                               btree_page_h& leaf,
                               const w_keystr_t& key,
                               slotid_t slot,
                               latch_mode_t latch_mode,
                               const okvl_mode& exact_hit_lock_mode,
                               const okvl_mode& miss_lock_mode,
                               bool check_only);

    static rc_t _ux_lock_range(const StoreID& store,
                               btree_page_h& leaf,
                               const void* keystr,
                               size_t keylen,
                               slotid_t slot,
                               latch_mode_t latch_mode,
                               const okvl_mode& exact_hit_lock_mode,
                               const okvl_mode& miss_lock_mode,
                               bool check_only);

    static rc_t _ux_assure_fence_low_entry(btree_page_h& leaf);

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    static rc_t _ux_create_tree_core(const StoreID& stid, const PageID& root_pid);

    static rc_t _sx_shrink_tree(btree_page_h& root);

    static rc_t _ux_shrink_tree_core(btree_page_h& root);

    static rc_t _sx_grow_tree(btree_page_h& root);

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    static rc_t _ux_verify_tree(
            StoreID store, int hash_bits, bool& consistent);

    static rc_t _ux_verify_tree_recurse(
            btree_page_h& parent, verification_context& context);

    static rc_t _ux_verify_feed_page(
            btree_page_h& page, verification_context& context);

    static rc_t _ux_verify_volume(
            int hash_bits, verify_volume_result& result);

    static void inquery_verify_init(StoreID store);

    static void inquery_verify_fact(btree_page_h& page);

    static void inquery_verify_expect(btree_page_h& page, slot_follow_t next_follow);

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE

    static rc_t _sx_defrag_tree(
            StoreID store,
            uint16_t inpage_defrag_ghost_threshold = 10,
            uint16_t inpage_defrag_usage_threshold = 50,
            bool does_adopt = true,
            bool does_merge = true);

    static rc_t _ux_defrag_tree_core(
            StoreID store,
            uint16_t inpage_defrag_ghost_threshold,
            uint16_t inpage_defrag_usage_threshold,
            bool does_adopt,
            bool does_merge);

    static rc_t _sx_defrag_page(btree_page_h& page);

    static rc_t _ux_defrag_page_core(btree_page_h& p);

    static okvl_mode create_part_okvl(okvl_mode::element_lock_mode mode, const w_keystr_t& key);

#ifdef DOXYGEN_HIDE
#endif // DOXYGEN_HIDE
    // see jira ticket:78 "Eager-Opportunistic Hybrid Latching" (originally trac ticket:80)
    // these are used to help determine when we should do eager EX latching.
    // these don't have to be exact or transactionally protected, so just static variables.
    enum {
        GAC_HASH_BITS = 16, // 64K
        GAC_HASH_MOD = 65521 // some prime number smaller than 2^GAC_HASH_BITS
    };

    static uint8_t s_ex_need_counts[1 << GAC_HASH_BITS];

    static queue_based_lock_t s_ex_need_mutex[1 << GAC_HASH_BITS];

    static uint8_t s_foster_children_counts[1 << GAC_HASH_BITS];

    inline static uint32_t shpid2hash(PageID pid) {
        return pid % GAC_HASH_MOD;
    }

    inline static queue_based_lock_t* mutex_for_high_contention(PageID pid) {
        return s_ex_need_mutex + shpid2hash(pid);
    }

    inline static bool is_ex_recommended(PageID pid) {
        uint32_t hash = shpid2hash(pid);
        w_assert1(hash < (1 << GAC_HASH_BITS));
        return (s_ex_need_counts[hash] > 30);
    }

    inline static uint8_t get_expected_childrens(PageID pid) {
        uint32_t hash = shpid2hash(pid);
        w_assert1(hash < (1 << GAC_HASH_BITS));
        return s_foster_children_counts[hash];
    }

    inline static void increase_ex_need(PageID real_parent_pid) {
        uint32_t hash = shpid2hash(real_parent_pid);
        w_assert1(hash < (1 << GAC_HASH_BITS));
        if (s_ex_need_counts[hash] < 255) {
            ++s_ex_need_counts[hash];
        }
    }

    inline static void increase_forster_child(PageID new_foster_parent_pid) {
        uint32_t hash = shpid2hash(new_foster_parent_pid);
        w_assert1(hash < (1 << GAC_HASH_BITS));
        ++s_foster_children_counts[hash];
        if (s_foster_children_counts[hash] < 255) {
            ++s_foster_children_counts[hash];
        }
    }

    inline static void clear_ex_need(PageID real_parent_pid) {
        uint32_t hash = shpid2hash(real_parent_pid);
        w_assert1(hash < (1 << GAC_HASH_BITS));
        s_ex_need_counts[hash] = 0;
    }

    inline static void clear_forster_child(PageID foster_parent_pid) {
        uint32_t hash = shpid2hash(foster_parent_pid);
        w_assert1(hash < (1 << GAC_HASH_BITS));
        s_foster_children_counts[hash] = 0;
    }
};

#endif // __BTREE_IMPL_H