| Safe Haskell | Safe-Infered |
|---|
Ganeti.Locking.Waiting
Description
Implementation of a priority waiting structure for locks.
- data LockWaiting a b c = LockWaiting {
- lwAllocation :: LockAllocation a b
- lwPending :: Map b (Set (c, b, [LockRequest a]))
- lwPendingOwners :: Map b (b, (c, b, [LockRequest a]))
- emptyWaiting :: (Ord a, Ord b, Ord c) => LockWaiting a b c
- getPendingOwners :: LockWaiting a b c -> Set b
- hasPendingRequest :: Ord b => b -> LockWaiting a b c -> Bool
- getAllocation :: LockWaiting a b c -> LockAllocation a b
- getPendingRequests :: (Ord a, Ord b, Ord c) => LockWaiting a b c -> Set (c, b, [LockRequest a])
- type ExtWaiting a b c = (LockAllocation a b, Set (c, b, [LockRequest a]))
- extRepr :: (Ord a, Ord b, Ord c) => LockWaiting a b c -> ExtWaiting a b c
- tryFulfillRequest :: (Lock a, Ord b, Ord c) => (LockWaiting a b c, Set b) -> (c, b, [LockRequest a]) -> (LockWaiting a b c, Set b)
- revisitRequests :: (Lock a, Ord b, Ord c) => Set b -> Set b -> LockWaiting a b c -> (Set b, LockWaiting a b c)
- updateLocks' :: (Lock a, Ord b, Ord c) => b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))
- updateLocksWaiting' :: (Lock a, Ord b, Ord c) => c -> b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))
- requestFulfilled :: (Ord a, Ord b) => b -> [LockRequest a] -> LockWaiting a b c -> Bool
- updateLocks :: (Lock a, Ord b, Ord c) => b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))
- updateLocksWaiting :: (Lock a, Ord b, Ord c) => c -> b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))
- removePendingRequest :: (Lock a, Ord b, Ord c) => b -> LockWaiting a b c -> LockWaiting a b c
- safeUpdateLocksWaiting :: (Lock a, Ord b, Ord c) => c -> b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))
- releaseResources :: (Lock a, Ord b, Ord c) => b -> LockWaiting a b c -> (LockWaiting a b c, Set b)
- fromExtRepr :: (Lock a, Ord b, Ord c) => ExtWaiting a b c -> LockWaiting a b c
- manipulateLocksPredicate :: (Lock a, Ord b, Ord c) => (a -> LockRequest a) -> (a -> Bool) -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)
- freeLocksPredicate :: (Lock a, Ord b, Ord c) => (a -> Bool) -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)
- downGradeLocksPredicate :: (Lock a, Ord b, Ord c) => (a -> Bool) -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)
- intersectLocks :: (Lock a, Ord b, Ord c) => [a] -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)
- opportunisticLockUnion :: (Lock a, Ord b, Ord c) => b -> [(a, OwnerState)] -> LockWaiting a b c -> (LockWaiting a b c, ([a], Set b))
- guardedOpportunisticLockUnion :: (Lock a, Ord b, Ord c) => Int -> b -> [(a, OwnerState)] -> LockWaiting a b c -> (LockWaiting a b c, ([a], Set b))
Documentation
data LockWaiting a b c Source
Representation of the waiting structure
For any request we cannot fullfill immediately, we have a set of lock owners it is blocked on. We can pick one of the owners, the smallest say; then we know that this request cannot possibly be fulfilled until this owner does something. So we can index the pending requests by such a chosen owner and only revisit them once the owner acts. For the requests to revisit we need to do so in order of increasing priority; this order can be maintained by the Set data structure, where we make use of the fact that tuples are ordered lexicographically.
Additionally, we keep track of which owners have pending requests, to disallow them any other lock tasks till their request is fulfilled. To allow canceling of pending requests, we also keep track on which owner their request is pending on and what the request was.
Constructors
| LockWaiting | |
Fields
| |
Instances
| (Show a, Show b, Show c) => Show (LockWaiting a b c) | |
| (Lock a, JSON a, Ord b, JSON b, Show b, Ord c, JSON c) => JSON (LockWaiting a b c) | |
| (Arbitrary a, Lock a, Arbitrary b, Ord b, Arbitrary c, Ord c) => Arbitrary (LockWaiting a b c) |
emptyWaiting :: (Ord a, Ord b, Ord c) => LockWaiting a b cSource
A state without locks and pending requests.
getPendingOwners :: LockWaiting a b c -> Set bSource
Get the set of owners with pending lock requests.
hasPendingRequest :: Ord b => b -> LockWaiting a b c -> BoolSource
Predicate on whether an owner has a pending lock request.
getAllocation :: LockWaiting a b c -> LockAllocation a bSource
Get the allocation state from the waiting state
getPendingRequests :: (Ord a, Ord b, Ord c) => LockWaiting a b c -> Set (c, b, [LockRequest a])Source
Get the list of all pending requests.
type ExtWaiting a b c = (LockAllocation a b, Set (c, b, [LockRequest a]))Source
Type of the extensional representation of a LockWaiting.
extRepr :: (Ord a, Ord b, Ord c) => LockWaiting a b c -> ExtWaiting a b cSource
Get a representation, comparable by (==), that captures the extensional
behaviour. In other words, (==) is a bisumlation.
on extRepr
tryFulfillRequest :: (Lock a, Ord b, Ord c) => (LockWaiting a b c, Set b) -> (c, b, [LockRequest a]) -> (LockWaiting a b c, Set b)Source
revisitRequests :: (Lock a, Ord b, Ord c) => Set b -> Set b -> LockWaiting a b c -> (Set b, LockWaiting a b c)Source
updateLocks' :: (Lock a, Ord b, Ord c) => b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))Source
updateLocksWaiting' :: (Lock a, Ord b, Ord c) => c -> b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))Source
requestFulfilled :: (Ord a, Ord b) => b -> [LockRequest a] -> LockWaiting a b c -> BoolSource
updateLocks :: (Lock a, Ord b, Ord c) => b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))Source
Update the locks on an onwer according to the given request, if possible. Additionally (if the request succeeds) fulfill any pending requests that became possible through this request. Return the new state of the waiting structure, the result of the operation, and a list of owners to be notified. The result is, as for lock allocation, the set of owners the request is blocked on. Again, the type is chosen to be suitable for use in atomicModifyIORef. For convenience, fulfilled requests are always accepted.
updateLocksWaiting :: (Lock a, Ord b, Ord c) => c -> b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))Source
Update locks as soon as possible. If the request cannot be fulfilled immediately add the request to the waiting queue. The first argument is the priority at which the owner is waiting, the remaining are as for updateLocks, and so is the output. For convenience, fulfilled requests are always accepted.
removePendingRequest :: (Lock a, Ord b, Ord c) => b -> LockWaiting a b c -> LockWaiting a b cSource
Compute the state of a waiting after an owner gives up on his pending request.
safeUpdateLocksWaiting :: (Lock a, Ord b, Ord c) => c -> b -> [LockRequest a] -> LockWaiting a b c -> (LockWaiting a b c, (Result (Set b), Set b))Source
A repeatable version of updateLocksWaiting. If the owner has a pending
request and the pending request is equal to the current one, do nothing;
otherwise call updateLocksWaiting.
releaseResources :: (Lock a, Ord b, Ord c) => b -> LockWaiting a b c -> (LockWaiting a b c, Set b)Source
Convenience function to release all pending requests and locks of a given owner. Return the new configuration and the owners to notify.
fromExtRepr :: (Lock a, Ord b, Ord c) => ExtWaiting a b c -> LockWaiting a b cSource
Obtain a LockWaiting from its extensional representation.
manipulateLocksPredicate :: (Lock a, Ord b, Ord c) => (a -> LockRequest a) -> (a -> Bool) -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)Source
freeLocksPredicate :: (Lock a, Ord b, Ord c) => (a -> Bool) -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)Source
Free all Locks of a given owner satisfying a given predicate. As this operation is supposed to unconditionally suceed, all pending requests are dropped as well.
downGradeLocksPredicate :: (Lock a, Ord b, Ord c) => (a -> Bool) -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)Source
Downgrade all locks of a given owner that satisfy a given predicate. As this operation is supposed to unconditionally suceed, all pending requests are dropped as well.
intersectLocks :: (Lock a, Ord b, Ord c) => [a] -> b -> LockWaiting a b c -> (LockWaiting a b c, Set b)Source
Intersect locks to a given set.
opportunisticLockUnion :: (Lock a, Ord b, Ord c) => b -> [(a, OwnerState)] -> LockWaiting a b c -> (LockWaiting a b c, ([a], Set b))Source
Opprotunistically allocate locks for a given owner; return the set of newly actually acquired locks (i.e., locks already held before are not mentioned).
guardedOpportunisticLockUnion :: (Lock a, Ord b, Ord c) => Int -> b -> [(a, OwnerState)] -> LockWaiting a b c -> (LockWaiting a b c, ([a], Set b))Source
A guarded version of opportunisticLockUnion; if the number of fulfilled requests is not at least the given amount, then do not change anything.