ganeti

Safe HaskellSafe-Infered

Ganeti.Locking.Waiting

Description

Implementation of a priority waiting structure for locks.

Synopsis

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

(Show a, Show b, Show c) => Show (LockWaiting a b c) 
(Arbitrary a, Lock a, Arbitrary b, Ord b, Arbitrary c, Ord c) => Arbitrary (LockWaiting a b c) 
(Lock a, JSON a, Ord b, JSON b, Show b, Ord c, JSON c) => JSON (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, (==) 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

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.