Safe Haskell	None

Ganeti.Locking.Allocation

Description

Implementation of lock allocation.

Synopsis

data OwnerState
- = OwnShared
- | OwnExclusive
type IndirectOwners a b = Map (a, b) OwnerState
data AllocationState a b
- = Exclusive b (IndirectOwners a b)
- | Shared (Set b) (IndirectOwners a b)
indirectOwners :: (Ord a, Ord b) => Map (a, b) OwnerState -> Set b
indirectExclusives :: (Ord a, Ord b) => Map (a, b) OwnerState -> Set b
data LockAllocation a b = LockAllocation {
- laLocks :: Map a (AllocationState a b)
- laOwned :: Map b (Map a OwnerState)
}
emptyAllocation :: (Ord a, Ord b) => LockAllocation a b
lockOwners :: Ord b => LockAllocation a b -> [b]
listLocks :: Ord b => b -> LockAllocation a b -> Map a OwnerState
listAllLocks :: Ord b => LockAllocation a b -> [a]
toOwnersList :: AllocationState a b -> [(b, OwnerState)]
listAllLocksOwners :: LockAllocation a b -> [(a, [(b, OwnerState)])]
holdsLock :: (Ord a, Ord b) => b -> a -> OwnerState -> LockAllocation a b -> Bool
data LockRequest a = LockRequest {
- lockAffected :: a
- lockRequestType :: Maybe OwnerState
}
requestExclusive :: a -> LockRequest a
requestShared :: a -> LockRequest a
requestRelease :: a -> LockRequest a
updateAllocState :: (Ord a, Ord b) => (Maybe (AllocationState a b) -> AllocationState a b) -> LockAllocation a b -> a -> LockAllocation a b
updateLock :: (Ord a, Ord b) => b -> LockAllocation a b -> LockRequest a -> LockAllocation a b
updateIndirectSet :: (Ord a, Ord b) => (IndirectOwners a b -> IndirectOwners a b) -> LockAllocation a b -> a -> LockAllocation a b
updateIndirects :: (Lock a, Ord b) => b -> LockAllocation a b -> LockRequest a -> LockAllocation a b
updateLocks :: (Lock a, Ord b) => b -> [LockRequest a] -> LockAllocation a b -> (LockAllocation a b, Result (Set b))
manipulateLocksPredicate :: (Lock a, Ord b) => (a -> LockRequest a) -> (a -> Bool) -> b -> LockAllocation a b -> LockAllocation a b
freeLocksPredicate :: (Lock a, Ord b) => (a -> Bool) -> LockAllocation a b -> b -> LockAllocation a b
freeLocks :: (Lock a, Ord b) => LockAllocation a b -> b -> LockAllocation a b
readLockOwnerstate :: JSON a => JSValue -> Result (a, OwnerState)
readOwnerLock :: (JSON a, JSON b) => JSValue -> Result (b, [(a, OwnerState)])
toRequest :: (a, OwnerState) -> LockRequest a
allocationFromOwners :: (Lock a, Ord b, Show b) => [(b, [(a, OwnerState)])] -> Result (LockAllocation a b)

Documentation

data OwnerState Source #

Data type describing the way a lock can be owned.

Constructors

OwnShared
OwnExclusive

Instances

Instances details

Eq OwnerState #
Instance details Defined in Ganeti.Locking.Allocation Methods (==) :: OwnerState -> OwnerState -> Bool (/=) :: OwnerState -> OwnerState -> Bool
Ord OwnerState #
Instance details Defined in Ganeti.Locking.Allocation Methods compare :: OwnerState -> OwnerState -> Ordering (<) :: OwnerState -> OwnerState -> Bool (<=) :: OwnerState -> OwnerState -> Bool (>) :: OwnerState -> OwnerState -> Bool (>=) :: OwnerState -> OwnerState -> Bool max :: OwnerState -> OwnerState -> OwnerState min :: OwnerState -> OwnerState -> OwnerState
Show OwnerState #
Instance details Defined in Ganeti.Locking.Allocation Methods showsPrec :: Int -> OwnerState -> ShowS show :: OwnerState -> String showList :: [OwnerState] -> ShowS
JSON OwnerState #	Serializaiton of Lock Allocations To serialize a lock allocation, we only remember which owner holds which locks at which level (shared or exclusive). From this information, everything else can be reconstructed, simply using updateLocks.
Instance details Defined in Ganeti.Locking.Allocation Methods readJSON :: JSValue -> Result OwnerState showJSON :: OwnerState -> JSValue readJSONs :: JSValue -> Result [OwnerState] showJSONs :: [OwnerState] -> JSValue
Arbitrary OwnerState
Instance details Defined in Test.Ganeti.Locking.Allocation Methods arbitrary :: Gen OwnerState shrink :: OwnerState -> [OwnerState]

type IndirectOwners a b = Map (a, b) OwnerState Source #

Type describing indirect ownership on a lock. We keep the set of all (lock, owner)-pairs for locks that are implied in the given lock, annotated with the type of ownership (shared or exclusive).

data AllocationState a b Source #

The state of a lock that is taken. Besides the state of the lock itself, we also keep track of all other lock allocation that affect the given lock by means of implication.

Constructors

Exclusive b (IndirectOwners a b)
Shared (Set b) (IndirectOwners a b)

indirectOwners :: (Ord a, Ord b) => Map (a, b) OwnerState -> Set b Source #

Compute the set of indirect owners from the information about indirect ownership.

indirectExclusives :: (Ord a, Ord b) => Map (a, b) OwnerState -> Set b Source #

Compute the (zero or one-elment) set of exclusive indirect owners.

data LockAllocation a b Source #

Representation of a Lock allocation

To keep queries for locks efficient, we keep two associations, with the invariant that they fit together: the association from locks to their allocation state, and the association from an owner to the set of locks owned. As we do not export the constructor, the problem of keeping this invariant reduces to only exporting functions that keep the invariant.

Constructors

LockAllocation
Fields laLocks :: Map a (AllocationState a b) laOwned :: Map b (Map a OwnerState)

Instances

Instances details

(Eq a, Eq b) => Eq (LockAllocation a b) #
Instance details Defined in Ganeti.Locking.Allocation Methods (==) :: LockAllocation a b -> LockAllocation a b -> Bool (/=) :: LockAllocation a b -> LockAllocation a b -> Bool
(Show a, Show b) => Show (LockAllocation a b) #
Instance details Defined in Ganeti.Locking.Allocation Methods showsPrec :: Int -> LockAllocation a b -> ShowS show :: LockAllocation a b -> String showList :: [LockAllocation a b] -> ShowS
(Lock a, JSON a, Ord b, JSON b, Show b) => JSON (LockAllocation a b) #
Instance details Defined in Ganeti.Locking.Allocation Methods readJSON :: JSValue -> Result (LockAllocation a b) showJSON :: LockAllocation a b -> JSValue readJSONs :: JSValue -> Result [LockAllocation a b] showJSONs :: [LockAllocation a b] -> JSValue
(Arbitrary a, Lock a, Arbitrary b, Ord b, Show b) => Arbitrary (LockAllocation a b)
Instance details Defined in Test.Ganeti.Locking.Allocation Methods arbitrary :: Gen (LockAllocation a b) shrink :: LockAllocation a b -> [LockAllocation a b]

emptyAllocation :: (Ord a, Ord b) => LockAllocation a b Source #

A state with all locks being free.

lockOwners :: Ord b => LockAllocation a b -> [b] Source #

Obtain the list of all owners holding at least a single lock.

listLocks :: Ord b => b -> LockAllocation a b -> Map a OwnerState Source #

Obtain the locks held by a given owner. The locks are reported as a map from the owned locks to the form of ownership (OwnShared or OwnExclusive).

listAllLocks :: Ord b => LockAllocation a b -> [a] Source #

List all locks currently (directly or indirectly) owned by someone.

toOwnersList :: AllocationState a b -> [(b, OwnerState)] Source #

Map an AllocationState to a list of pairs of owners and type of ownership, showing the direct owners only.

listAllLocksOwners :: LockAllocation a b -> [(a, [(b, OwnerState)])] Source #

List all locks currently (directly of indirectly) in use together with the direct owners.

holdsLock :: (Ord a, Ord b) => b -> a -> OwnerState -> LockAllocation a b -> Bool Source #

Returns True if the given owner holds the given lock at the given ownership level or higher. This means that querying for a shared lock returns True of the owner holds the lock in shared or exlusive mode.

data LockRequest a Source #

Data Type describing a change request on a single lock.

Constructors

LockRequest
Fields lockAffected :: a lockRequestType :: Maybe OwnerState

Instances

Instances details

Eq a => Eq (LockRequest a) #
Instance details Defined in Ganeti.Locking.Allocation Methods (==) :: LockRequest a -> LockRequest a -> Bool (/=) :: LockRequest a -> LockRequest a -> Bool
Ord a => Ord (LockRequest a) #
Instance details Defined in Ganeti.Locking.Allocation Methods compare :: LockRequest a -> LockRequest a -> Ordering (<) :: LockRequest a -> LockRequest a -> Bool (<=) :: LockRequest a -> LockRequest a -> Bool (>) :: LockRequest a -> LockRequest a -> Bool (>=) :: LockRequest a -> LockRequest a -> Bool max :: LockRequest a -> LockRequest a -> LockRequest a min :: LockRequest a -> LockRequest a -> LockRequest a
Show a => Show (LockRequest a) #
Instance details Defined in Ganeti.Locking.Allocation Methods showsPrec :: Int -> LockRequest a -> ShowS show :: LockRequest a -> String showList :: [LockRequest a] -> ShowS
JSON a => JSON (LockRequest a) #
Instance details Defined in Ganeti.Locking.Allocation Methods readJSON :: JSValue -> Result (LockRequest a) showJSON :: LockRequest a -> JSValue readJSONs :: JSValue -> Result [LockRequest a] showJSONs :: [LockRequest a] -> JSValue
Arbitrary a => Arbitrary (LockRequest a)
Instance details Defined in Test.Ganeti.Locking.Allocation Methods arbitrary :: Gen (LockRequest a) shrink :: LockRequest a -> [LockRequest a]

requestExclusive :: a -> LockRequest a Source #

Lock request for an exclusive lock.

requestShared :: a -> LockRequest a Source #

Lock request for a shared lock.

requestRelease :: a -> LockRequest a Source #

Request to release a lock.

updateAllocState :: (Ord a, Ord b) => (Maybe (AllocationState a b) -> AllocationState a b) -> LockAllocation a b -> a -> LockAllocation a b Source #

Update the Allocation state of a lock according to a given function.

updateLock :: (Ord a, Ord b) => b -> LockAllocation a b -> LockRequest a -> LockAllocation a b Source #

Internal function to update the state according to a single lock request, assuming all prerequisites are met.

updateIndirectSet :: (Ord a, Ord b) => (IndirectOwners a b -> IndirectOwners a b) -> LockAllocation a b -> a -> LockAllocation a b Source #

Update the set of indirect ownerships of a lock by the given function.

updateIndirects :: (Lock a, Ord b) => b -> LockAllocation a b -> LockRequest a -> LockAllocation a b Source #

Update all indirect onwerships of a given lock.

updateLocks :: (Lock a, Ord b) => b -> [LockRequest a] -> LockAllocation a b -> (LockAllocation a b, Result (Set b)) Source #

Update the locks of an owner according to the given request. Return the pair of the new state and the result of the operation, which is the the set of owners on which the operation was blocked on. so an empty set is success, and the state is updated if, and only if, the returned set is emtpy. In that way, it can be used in atomicModifyIORef.

manipulateLocksPredicate :: (Lock a, Ord b) => (a -> LockRequest a) -> (a -> Bool) -> b -> LockAllocation a b -> LockAllocation a b Source #

Manipluate all locks of the owner with a given property.

freeLocksPredicate :: (Lock a, Ord b) => (a -> Bool) -> LockAllocation a b -> b -> LockAllocation a b Source #

Compute the state after an owner releases all its locks that satisfy a certain property.

freeLocks :: (Lock a, Ord b) => LockAllocation a b -> b -> LockAllocation a b Source #

Compute the state after an onwer releases all its locks.

readLockOwnerstate :: JSON a => JSValue -> Result (a, OwnerState) Source #

Read a lock-ownerstate pair from JSON.

readOwnerLock :: (JSON a, JSON b) => JSValue -> Result (b, [(a, OwnerState)]) Source #

Read an owner-lock pair from JSON.

toRequest :: (a, OwnerState) -> LockRequest a Source #

Transform a lock-ownerstate pair into a LockRequest.

allocationFromOwners :: (Lock a, Ord b, Show b) => [(b, [(a, OwnerState)])] -> Result (LockAllocation a b) Source #

Obtain a LockAllocation from a given owner-locks list. The obtained allocation is the one obtained if the respective owners requested their locks sequentially.