Safe Haskell	None

Ganeti.Locking.Waiting

Description

Implementation of a priority waiting structure for locks.

Synopsis

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 lwAllocation :: LockAllocation a b lwPending :: Map b (Set (c, b, [LockRequest a])) lwPendingOwners :: Map b (b, (c, b, [LockRequest a]))

Instances

Instances details

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

emptyWaiting :: (Ord a, Ord b, Ord c) => LockWaiting a b c Source #

A state without locks and pending requests.

getPendingOwners :: LockWaiting a b c -> Set b Source #

Get the set of owners with pending lock requests.

hasPendingRequest :: Ord b => b -> LockWaiting a b c -> Bool Source #

Predicate on whether an owner has a pending lock request.

getAllocation :: LockWaiting a b c -> LockAllocation a b Source #

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 c Source #

Get a representation, comparable by (==), that captures the extensional behaviour. In other words, (==) on extRepr is a bisumlation.

tryFulfillRequest :: (Lock a, Ord b, Ord c) => (LockWaiting a b c, Set b) -> (c, b, [LockRequest a]) -> (LockWaiting a b c, Set b) Source #

Internal function to fulfill one request if possible, and keep track of the owners to be notified. The type is chosen to be suitable as fold operation.

This function calls the later defined updateLocksWaiting', as they are mutually recursive.

revisitRequests Source #

Arguments

:: (Lock a, Ord b, Ord c)
=> Set b	the owners where the requests keyed by them already have been revisited
-> Set b	the owners where requests keyed by them need to be revisited
-> LockWaiting a b c	state before revisiting
-> (Set b, LockWaiting a b c)	owners visited and state after revisiting

Internal function to recursively follow the consequences of a change.

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 owner whose requests have been fulfilled. 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.

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.

requestFulfilled :: (Ord a, Ord b) => b -> [LockRequest a] -> LockWaiting a b c -> Bool Source #

Predicate whether a request is already fulfilled in a given state and no requests for that owner are pending.

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 c Source #

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 c Source #

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 #

Manipulate a all locks of an owner that have a given property. Also drop all pending requests.

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.