Safe Haskell | None |
---|

Implementation of a priority waiting structure for locks.

## Synopsis

- data LockWaiting a b c
- 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
- 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
- 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.

## Instances

(Show a, Show b, Show c) => Show (LockWaiting a b c) # | |

Defined in Ganeti.Locking.Waiting 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) # | |

Defined in Ganeti.Locking.Waiting 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) | |

Defined in Test.Ganeti.Locking.Waiting 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, `(==) `

is a bisumlation.`on`

extRepr

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.

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.