lock_manager.h

Go to the documentation of this file.

#pragma once

#include <cstdint>
#include <deque>
#include <map>
#include <vector>

#include "mongo/bson/bsonobj.h"
#include "mongo/config.h"
#include "mongo/db/concurrency/lock_manager_defs.h"
#include "mongo/db/concurrency/lock_request_list.h"
#include "mongo/platform/atomic_word.h"
#include "mongo/platform/compiler.h"
#include "mongo/stdx/condition_variable.h"
#include "mongo/stdx/mutex.h"
#include "mongo/stdx/unordered_map.h"
#include "mongo/util/concurrency/mutex.h"

namespace mongo {

class LockManager {
    MONGO_DISALLOW_COPYING(LockManager);

public:
    LockManager();
    ~LockManager();

    LockResult lock(ResourceId resId, LockRequest* request, LockMode mode);
    LockResult convert(ResourceId resId, LockRequest* request, LockMode newMode);

    bool unlock(LockRequest* request);

    void downgrade(LockRequest* request, LockMode newMode);

    void cleanupUnusedLocks();

    void dump() const;

    void getLockInfoBSON(const std::map<LockerId, BSONObj>& lockToClientMap,
                         BSONObjBuilder* result);

private:
    // The deadlock detector needs to access the buckets and locks directly
    friend class DeadlockDetector;

    // The lockheads need access to the partitions
    friend struct LockHead;

    // These types describe the locks hash table

    struct LockBucket {
        SimpleMutex mutex;
        typedef stdx::unordered_map<ResourceId, LockHead*> Map;
        Map data;
        LockHead* findOrInsert(ResourceId resId);
    };

    // Each locker maps to a partition that is used for resources acquired in intent modes
    // modes and potentially other modes that don't conflict with themselves. This avoids
    // contention on the regular LockHead in the lock manager.
    struct Partition {
        PartitionedLockHead* find(ResourceId resId);
        PartitionedLockHead* findOrInsert(ResourceId resId);
        typedef stdx::unordered_map<ResourceId, PartitionedLockHead*> Map;
        SimpleMutex mutex;
        Map data;
    };

    LockBucket* _getBucket(ResourceId resId) const;


    Partition* _getPartition(LockRequest* request) const;

    void _dumpBucket(const LockBucket* bucket) const;

    void _dumpBucketToBSON(const std::map<LockerId, BSONObj>& lockToClientMap,
                           const LockBucket* bucket,
                           BSONObjBuilder* result);

    void _buildBucketBSON(const LockRequest* iter,
                          const std::map<LockerId, BSONObj>& lockToClientMap,
                          const LockBucket* bucket,
                          BSONArrayBuilder* locks);

    void _onLockModeChanged(LockHead* lock, bool checkConflictQueue);

    void _cleanupUnusedLocksInBucket(LockBucket* bucket);

    static const unsigned _numLockBuckets;
    LockBucket* _lockBuckets;

    static const unsigned _numPartitions;
    Partition* _partitions;
};


class DeadlockDetector {
public:
    DeadlockDetector(const LockManager& lockMgr, const Locker* initialLocker);

    DeadlockDetector& check() {
        while (next()) {
        }

        return *this;
    }

    bool next();

    bool hasCycle() const;

    std::string toString() const;

private:
    // An entry in the owners list below means that some locker L is blocked on some resource
    // resId, which is currently held by the given set of owners. The reason to store it in
    // such form is in order to avoid storing pointers to the lockers or to have to look them
    // up by id, both of which require some form of synchronization other than locking the
    // bucket for the resource. Instead, given the resId, we can lock the bucket for the lock
    // and find the respective LockRequests and continue our scan forward.
    typedef std::vector<LockerId> ConflictingOwnersList;

    struct Edges {
        explicit Edges(ResourceId resId) : resId(resId) {}

        // Resource id indicating the lock node
        ResourceId resId;

        // List of lock owners/pariticipants with which the initial locker conflicts for
        // obtaining the lock
        ConflictingOwnersList owners;
    };

    typedef std::map<LockerId, Edges> WaitForGraph;
    typedef WaitForGraph::value_type WaitForGraphPair;


    // We don't want to hold locks between iteration cycles, so just store the resourceId and
    // the lockerId so we can directly find them from the lock manager.
    struct UnprocessedNode {
        UnprocessedNode(LockerId lockerId, ResourceId resId) : lockerId(lockerId), resId(resId) {}

        LockerId lockerId;
        ResourceId resId;
    };

    typedef std::deque<UnprocessedNode> UnprocessedNodesQueue;


    void _processNextNode(const UnprocessedNode& node);


    // Not owned. Lifetime must be longer than that of the graph builder.
    const LockManager& _lockMgr;
    const LockerId _initialLockerId;

    UnprocessedNodesQueue _queue;
    WaitForGraph _graph;

    bool _foundCycle;
};

}  // namespace mongo