btree_logic.h

Go to the documentation of this file.

#pragma once

#include <string>

#include "mongo/db/catalog/head_manager.h"
#include "mongo/db/catalog/index_catalog_entry.h"
#include "mongo/db/jsobj.h"
#include "mongo/db/operation_context.h"
#include "mongo/db/storage/index_entry_comparison.h"
#include "mongo/db/storage/mmap_v1/btree/btree_ondisk.h"
#include "mongo/db/storage/mmap_v1/btree/key.h"
#include "mongo/db/storage/mmap_v1/diskloc.h"

namespace mongo {

class PseudoRandom;
class RecordStore;
class SavedCursorRegistry;

// Used for unit-testing only
template <class BtreeLayout>
class BtreeLogicTestBase;
template <class BtreeLayout>
class ArtificialTreeBuilder;

template <class BtreeLayout>
class BtreeLogic {
public:
    // AKA _keyNode
    typedef typename BtreeLayout::FixedWidthKeyType KeyHeaderType;

    // AKA Key
    typedef typename BtreeLayout::KeyType KeyDataType;

    // AKA KeyOwned
    typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType;

    // AKA Loc
    typedef typename BtreeLayout::LocType LocType;

    // AKA BucketBasics or BtreeBucket, either one.
    typedef typename BtreeLayout::BucketType BucketType;

    BtreeLogic(HeadManager* head,
               RecordStore* store,
               SavedCursorRegistry* cursors,
               const Ordering& ordering,
               const std::string& indexName,
               bool isUnique)
        : _headManager(head),
          _recordStore(store),
          _cursorRegistry(cursors),
          _ordering(ordering),
          _indexName(indexName),
          _isUnique(isUnique) {}

    //
    // Public-facing
    //

    class Builder {
    public:
        typedef typename BtreeLayout::KeyOwnedType KeyDataOwnedType;
        typedef typename BtreeLayout::KeyType KeyDataType;

        Status addKey(const BSONObj& key, const DiskLoc& loc);

    private:
        friend class BtreeLogic;

        class SetRightLeafLocChange;

        Builder(BtreeLogic* logic, OperationContext* opCtx, bool dupsAllowed);

        DiskLoc newBucket(BucketType* leftSib, DiskLoc leftSibLoc);

        BucketType* _getModifiableBucket(DiskLoc loc);
        BucketType* _getBucket(DiskLoc loc);

        // Not owned.
        BtreeLogic* _logic;

        DiskLoc _rightLeafLoc;  // DiskLoc of right-most (highest) leaf bucket.
        bool _dupsAllowed;
        std::unique_ptr<KeyDataOwnedType> _keyLast;

        // Not owned.
        OperationContext* _opCtx;
    };

    Builder* newBuilder(OperationContext* opCtx, bool dupsAllowed);

    Status dupKeyCheck(OperationContext* opCtx, const BSONObj& key, const DiskLoc& loc) const;

    Status insert(OperationContext* opCtx,
                  const BSONObj& rawKey,
                  const DiskLoc& value,
                  bool dupsAllowed);

    bool locate(OperationContext* opCtx,
                const BSONObj& key,
                const DiskLoc& recordLoc,
                const int direction,
                int* posOut,
                DiskLoc* bucketLocOut) const;

    void advance(OperationContext* opCtx,
                 DiskLoc* bucketLocInOut,
                 int* posInOut,
                 int direction) const;

    bool exists(OperationContext* opCtx, const KeyDataType& key) const;

    bool unindex(OperationContext* opCtx, const BSONObj& key, const DiskLoc& recordLoc);

    bool isEmpty(OperationContext* opCtx) const;

    long long fullValidate(OperationContext*,
                           long long* unusedCount,
                           bool strict,
                           bool dumpBuckets,
                           unsigned depth) const;

    DiskLoc getDiskLoc(OperationContext* opCtx,
                       const DiskLoc& bucketLoc,
                       const int keyOffset) const;

    BSONObj getKey(OperationContext* opCtx, const DiskLoc& bucketLoc, const int keyOffset) const;

    IndexKeyEntry getRandomEntry(OperationContext* opCtx) const;

    DiskLoc getHead(OperationContext* opCtx) const {
        return DiskLoc::fromRecordId(_headManager->getHead(opCtx));
    }

    Status touch(OperationContext* opCtx) const;

    //
    // Composite key navigation methods
    //

    void customLocate(OperationContext* opCtx,
                      DiskLoc* locInOut,
                      int* keyOfsInOut,
                      const IndexSeekPoint& seekPoint,
                      int direction) const;

    void advanceTo(OperationContext*,
                   DiskLoc* thisLocInOut,
                   int* keyOfsInOut,
                   const IndexSeekPoint& seekPoint,
                   int direction) const;

    void restorePosition(OperationContext* opCtx,
                         const BSONObj& savedKey,
                         const DiskLoc& savedLoc,
                         int direction,
                         DiskLoc* bucketInOut,
                         int* keyOffsetInOut) const;

    //
    // Creation and deletion
    //

    Status initAsEmpty(OperationContext* opCtx);

    //
    // Size constants
    //

    const RecordStore* getRecordStore() const {
        return _recordStore;
    }

    SavedCursorRegistry* savedCursors() const {
        return _cursorRegistry;
    }

    static int lowWaterMark();

    Ordering ordering() const {
        return _ordering;
    }

    int customBSONCmp(const BSONObj& inIndex_left,
                      const IndexSeekPoint& seekPoint_right,
                      int direction) const;

    bool isUnique() const {
        return _isUnique;
    }

private:
    friend class BtreeLogic::Builder;

    // Used for unit-testing only
    friend class BtreeLogicTestBase<BtreeLayout>;
    friend class ArtificialTreeBuilder<BtreeLayout>;

    struct FullKey {
        FullKey(const BucketType* bucket, int i)
            : header(getKeyHeader(bucket, i)),
              prevChildBucket(header.prevChildBucket),
              recordLoc(header.recordLoc),
              data(bucket->data + header.keyDataOfs()) {}

        // This is actually a reference to something on-disk.
        const KeyHeaderType& header;

        // These are actually in 'header'.
        const LocType& prevChildBucket;
        const LocType& recordLoc;

        // This is *not* memory-mapped but its members point to something on-disk.
        KeyDataType data;
    };

    //
    // Functions that depend on the templated type info but nothing in 'this'.
    //

    static LocType& childLocForPos(BucketType* bucket, int pos);

    static FullKey getFullKey(const BucketType* bucket, int i);

    static KeyHeaderType& getKeyHeader(BucketType* bucket, int i);

    static const KeyHeaderType& getKeyHeader(const BucketType* bucket, int i);

    static char* dataAt(BucketType* bucket, short ofs);

    static void markUnused(BucketType* bucket, int keypos);

    static int totalDataSize(BucketType* bucket);

    static void init(BucketType* bucket);

    static int _alloc(BucketType* bucket, int bytes);

    static void _unalloc(BucketType* bucket, int bytes);

    static void _delKeyAtPos(BucketType* bucket, int keypos, bool mayEmpty = false);

    static void popBack(BucketType* bucket, DiskLoc* recordLocOut, KeyDataType* keyDataOut);

    static bool mayDropKey(BucketType* bucket, int index, int refPos);

    static int _packedDataSize(BucketType* bucket, int refPos);

    static void setPacked(BucketType* bucket);

    static void setNotPacked(BucketType* bucket);

    static BucketType* btreemod(OperationContext* opCtx, BucketType* bucket);

    static int splitPos(BucketType* bucket, int keypos);

    static void reserveKeysFront(BucketType* bucket, int nAdd);

    static void setKey(BucketType* bucket,
                       int i,
                       const DiskLoc recordLoc,
                       const KeyDataType& key,
                       const DiskLoc prevChildBucket);

    static bool isHead(BucketType* bucket);

    static void dumpBucket(const BucketType* bucket, int indentLength = 0);

    static void assertValid(const std::string& ns,
                            BucketType* bucket,
                            const Ordering& ordering,
                            bool force = false);

    //
    // 'this'-specific helpers (require record store, catalog information, or ordering, or type
    // information).
    //

    bool basicInsert(OperationContext* opCtx,
                     BucketType* bucket,
                     const DiskLoc bucketLoc,
                     int& keypos,
                     const KeyDataType& key,
                     const DiskLoc recordLoc);

    void dropFront(BucketType* bucket, int nDrop, int& refpos);

    void _pack(OperationContext* opCtx, BucketType* bucket, const DiskLoc thisLoc, int& refPos);

    void customLocate(OperationContext* opCtx,
                      DiskLoc* locInOut,
                      int* keyOfsInOut,
                      const IndexSeekPoint& seekPoint,
                      int direction,
                      std::pair<DiskLoc, int>& bestParent) const;

    Status _find(OperationContext* opCtx,
                 BucketType* bucket,
                 const KeyDataType& key,
                 const DiskLoc& recordLoc,
                 bool errorIfDup,
                 int* keyPositionOut,
                 bool* foundOut) const;

    bool customFind(OperationContext* opCtx,
                    int low,
                    int high,
                    const IndexSeekPoint& seekPoint,
                    int direction,
                    DiskLoc* thisLocInOut,
                    int* keyOfsInOut,
                    std::pair<DiskLoc, int>& bestParent) const;

    void advanceToImpl(OperationContext* opCtx,
                       DiskLoc* thisLocInOut,
                       int* keyOfsInOut,
                       const IndexSeekPoint& seekPoint,
                       int direction) const;

    bool wouldCreateDup(OperationContext* opCtx, const KeyDataType& key, const DiskLoc self) const;

    bool keyIsUsed(OperationContext* opCtx, const DiskLoc& loc, const int& pos) const;

    void skipUnusedKeys(OperationContext* opCtx, DiskLoc* loc, int* pos, int direction) const;

    DiskLoc advance(OperationContext* opCtx,
                    const DiskLoc& bucketLoc,
                    int* posInOut,
                    int direction) const;

    DiskLoc _locate(OperationContext* opCtx,
                    const DiskLoc& bucketLoc,
                    const KeyDataType& key,
                    int* posOut,
                    bool* foundOut,
                    const DiskLoc& recordLoc,
                    const int direction) const;

    long long _fullValidate(OperationContext* opCtx,
                            const DiskLoc bucketLoc,
                            long long* unusedCount,
                            bool strict,
                            bool dumpBuckets,
                            unsigned depth) const;

    DiskLoc _addBucket(OperationContext* opCtx);

    bool canMergeChildren(OperationContext* opCtx,
                          BucketType* bucket,
                          const DiskLoc bucketLoc,
                          const int leftIndex);

    // has to look in children of 'bucket' and requires record store
    int _rebalancedSeparatorPos(OperationContext* opCtx, BucketType* bucket, int leftIndex);

    void _packReadyForMod(BucketType* bucket, int& refPos);

    void truncateTo(BucketType* bucket, int N, int& refPos);

    void split(OperationContext* opCtx,
               BucketType* bucket,
               const DiskLoc bucketLoc,
               int keypos,
               const DiskLoc recordLoc,
               const KeyDataType& key,
               const DiskLoc lchild,
               const DiskLoc rchild);

    Status _insert(OperationContext* opCtx,
                   BucketType* bucket,
                   const DiskLoc bucketLoc,
                   const KeyDataType& key,
                   const DiskLoc recordLoc,
                   bool dupsAllowed,
                   const DiskLoc leftChild,
                   const DiskLoc rightChild);

    // TODO take a BucketType*?
    void insertHere(OperationContext* opCtx,
                    const DiskLoc bucketLoc,
                    int pos,
                    const KeyDataType& key,
                    const DiskLoc recordLoc,
                    const DiskLoc leftChild,
                    const DiskLoc rightChild);

    std::string dupKeyError(const KeyDataType& key) const;

    void setInternalKey(OperationContext* opCtx,
                        BucketType* bucket,
                        const DiskLoc bucketLoc,
                        int keypos,
                        const DiskLoc recordLoc,
                        const KeyDataType& key,
                        const DiskLoc lchild,
                        const DiskLoc rchild);

    void fixParentPtrs(OperationContext* trans,
                       BucketType* bucket,
                       const DiskLoc bucketLoc,
                       int firstIndex = 0,
                       int lastIndex = -1);

    bool mayBalanceWithNeighbors(OperationContext* opCtx,
                                 BucketType* bucket,
                                 const DiskLoc bucketLoc);

    void doBalanceChildren(OperationContext* opCtx,
                           BucketType* bucket,
                           const DiskLoc bucketLoc,
                           int leftIndex);

    void doBalanceLeftToRight(OperationContext* opCtx,
                              BucketType* bucket,
                              const DiskLoc thisLoc,
                              int leftIndex,
                              int split,
                              BucketType* l,
                              const DiskLoc lchild,
                              BucketType* r,
                              const DiskLoc rchild);

    void doBalanceRightToLeft(OperationContext* opCtx,
                              BucketType* bucket,
                              const DiskLoc thisLoc,
                              int leftIndex,
                              int split,
                              BucketType* l,
                              const DiskLoc lchild,
                              BucketType* r,
                              const DiskLoc rchild);

    bool tryBalanceChildren(OperationContext* opCtx,
                            BucketType* bucket,
                            const DiskLoc bucketLoc,
                            int leftIndex);

    int indexInParent(OperationContext* opCtx, BucketType* bucket, const DiskLoc bucketLoc) const;

    void doMergeChildren(OperationContext* opCtx,
                         BucketType* bucket,
                         const DiskLoc bucketLoc,
                         int leftIndex);

    void replaceWithNextChild(OperationContext* opCtx, BucketType* bucket, const DiskLoc bucketLoc);

    void deleteInternalKey(OperationContext* opCtx,
                           BucketType* bucket,
                           const DiskLoc bucketLoc,
                           int keypos);

    void delKeyAtPos(OperationContext* opCtx, BucketType* bucket, const DiskLoc bucketLoc, int p);

    void delBucket(OperationContext* opCtx, BucketType* bucket, const DiskLoc bucketLoc);

    void deallocBucket(OperationContext* opCtx, BucketType* bucket, const DiskLoc bucketLoc);

    bool _keyIsAt(const BSONObj& savedKey,
                  const DiskLoc& savedLoc,
                  BucketType* bucket,
                  int keyPos) const;

    bool pushBack(BucketType* bucket,
                  const DiskLoc recordLoc,
                  const KeyDataType& key,
                  const DiskLoc prevChild);


    BucketType* childForPos(OperationContext* opCtx, BucketType* bucket, int pos) const;

    BucketType* getBucket(OperationContext* opCtx, const DiskLoc dl) const {
        return getBucket(opCtx, dl.toRecordId());
    }
    BucketType* getBucket(OperationContext* opCtx, const RecordId dl) const;

    BucketType* getRoot(OperationContext* opCtx) const;

    DiskLoc getRootLoc(OperationContext* opCtx) const;

    void recordRandomWalk(OperationContext* opCtx,
                          PseudoRandom* prng,
                          BucketType* curBucket,
                          int64_t nBucketsInCurrentLevel,
                          std::vector<int64_t>* nKeysInLevel,
                          std::vector<FullKey>* selectedKeys) const;

    //
    // Data
    //

    // Not owned here.
    HeadManager* _headManager;

    // Not owned here.
    RecordStore* _recordStore;

    // Not owned Here.
    SavedCursorRegistry* _cursorRegistry;

    Ordering _ordering;

    std::string _indexName;

    // True if this is a unique index, i.e. if duplicate key values are disallowed.
    const bool _isUnique;
};

}  // namespace mongo