## root / test / hs / Test / Ganeti / Locking / Allocation.hs @ 89d140d1

History | View | Annotate | Download (13.6 kB)

1 |
{-# LANGUAGE TemplateHaskell #-} |
---|---|

2 |
{-# OPTIONS_GHC -fno-warn-orphans #-} |

3 | |

4 |
{-| Tests for lock allocation. |

5 | |

6 |
-} |

7 | |

8 |
{- |

9 | |

10 |
Copyright (C) 2014 Google Inc. |

11 | |

12 |
This program is free software; you can redistribute it and/or modify |

13 |
it under the terms of the GNU General Public License as published by |

14 |
the Free Software Foundation; either version 2 of the License, or |

15 |
(at your option) any later version. |

16 | |

17 |
This program is distributed in the hope that it will be useful, but |

18 |
WITHOUT ANY WARRANTY; without even the implied warranty of |

19 |
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |

20 |
General Public License for more details. |

21 | |

22 |
You should have received a copy of the GNU General Public License |

23 |
along with this program; if not, write to the Free Software |

24 |
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |

25 |
02110-1301, USA. |

26 | |

27 |
-} |

28 | |

29 |
module Test.Ganeti.Locking.Allocation (testLocking_Allocation) where |

30 | |

31 |
import Control.Applicative |

32 |
import qualified Data.Foldable as F |

33 |
import qualified Data.Map as M |

34 |
import qualified Data.Set as S |

35 |
import qualified Text.JSON as J |

36 | |

37 |
import Test.QuickCheck |

38 | |

39 |
import Test.Ganeti.TestCommon |

40 |
import Test.Ganeti.TestHelper |

41 | |

42 |
import Ganeti.BasicTypes |

43 |
import Ganeti.Locking.Allocation |

44 |
import Ganeti.Locking.Types |

45 | |

46 |
{- |

47 | |

48 |
Ganeti.Locking.Allocation is polymorphic in the types of locks |

49 |
and lock owners. So we can use much simpler types here than Ganeti's |

50 |
real locks and lock owners, knowning at polymorphic functions cannot |

51 |
exploit the simplicity of the types they're deling with. |

52 | |

53 |
-} |

54 | |

55 |
data TestOwner = TestOwner Int deriving (Ord, Eq, Show) |

56 | |

57 |
instance Arbitrary TestOwner where |

58 |
arbitrary = TestOwner <$> choose (0, 2) |

59 | |

60 |
data TestLock = TestBigLock |

61 |
| TestCollectionLockA |

62 |
| TestLockA Int |

63 |
| TestCollectionLockB |

64 |
| TestLockB Int |

65 |
deriving (Ord, Eq, Show, Read) |

66 | |

67 |
instance Arbitrary TestLock where |

68 |
arbitrary = frequency [ (1, elements [ TestBigLock |

69 |
, TestCollectionLockA |

70 |
, TestCollectionLockB |

71 |
]) |

72 |
, (2, TestLockA <$> choose (0, 2)) |

73 |
, (2, TestLockB <$> choose (0, 2)) |

74 |
] |

75 | |

76 |
instance Lock TestLock where |

77 |
lockImplications (TestLockA _) = [TestCollectionLockA, TestBigLock] |

78 |
lockImplications (TestLockB _) = [TestCollectionLockB, TestBigLock] |

79 |
lockImplications TestBigLock = [] |

80 |
lockImplications _ = [TestBigLock] |

81 | |

82 |
{- |

83 | |

84 |
All states of a LockAllocation every available outside the |

85 |
Ganeti.Locking.Allocation module must be constructed by starting |

86 |
with emptyAllocation and applying the exported functions. |

87 | |

88 |
-} |

89 | |

90 |
instance Arbitrary OwnerState where |

91 |
arbitrary = elements [OwnShared, OwnExclusive] |

92 | |

93 |
instance Arbitrary a => Arbitrary (LockRequest a) where |

94 |
arbitrary = LockRequest <$> arbitrary <*> genMaybe arbitrary |

95 | |

96 |
data UpdateRequest b a = UpdateRequest b [LockRequest a] |

97 |
| IntersectRequest b [a] |

98 |
| OpportunisticUnion b [(a, OwnerState)] |

99 |
| FreeLockRequest b |

100 |
deriving Show |

101 | |

102 |
instance (Arbitrary a, Arbitrary b) => Arbitrary (UpdateRequest a b) where |

103 |
arbitrary = |

104 |
frequency [ (4, UpdateRequest <$> arbitrary <*> (choose (1, 4) >>= vector)) |

105 |
, (2, IntersectRequest <$> arbitrary |

106 |
<*> (choose (1, 4) >>= vector)) |

107 |
, (2, OpportunisticUnion <$> arbitrary |

108 |
<*> (choose (1, 4) >>= vector)) |

109 |
, (1, FreeLockRequest <$> arbitrary) |

110 |
] |

111 | |

112 |
-- | Transform an UpdateRequest into the corresponding state transformer. |

113 |
asAllocTrans :: (Lock a, Ord b, Show b) |

114 |
=> LockAllocation a b -> UpdateRequest b a -> LockAllocation a b |

115 |
asAllocTrans state (UpdateRequest owner updates) = |

116 |
fst $ updateLocks owner updates state |

117 |
asAllocTrans state (IntersectRequest owner locks) = |

118 |
intersectLocks owner locks state |

119 |
asAllocTrans state (OpportunisticUnion owner locks) = |

120 |
fst $ opportunisticLockUnion owner locks state |

121 |
asAllocTrans state (FreeLockRequest owner) = freeLocks state owner |

122 | |

123 |
-- | Fold a sequence of requests to transform a lock allocation onto the empty |

124 |
-- allocation. As we consider all exported LockAllocation transformers, any |

125 |
-- LockAllocation definable is obtained in this way. |

126 |
foldUpdates :: (Lock a, Ord b, Show b) |

127 |
=> [UpdateRequest b a] -> LockAllocation a b |

128 |
foldUpdates = foldl asAllocTrans emptyAllocation |

129 | |

130 |
instance (Arbitrary a, Lock a, Arbitrary b, Ord b, Show b) |

131 |
=> Arbitrary (LockAllocation a b) where |

132 |
arbitrary = foldUpdates <$> (choose (0, 8) >>= vector) |

133 | |

134 |
-- | Basic property of locking: the exclusive locks of one user |

135 |
-- are disjoint from any locks of any other user. |

136 |
prop_LocksDisjoint :: Property |

137 |
prop_LocksDisjoint = |

138 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

139 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

140 |
forAll (arbitrary `suchThat` (/= a)) $ \b -> |

141 |
let aExclusive = M.keysSet . M.filter (== OwnExclusive) $ listLocks a state |

142 |
bAll = M.keysSet $ listLocks b state |

143 |
in printTestCase |

144 |
(show a ++ "'s exclusive lock" ++ " is not respected by " ++ show b) |

145 |
(S.null $ S.intersection aExclusive bAll) |

146 | |

147 |
-- | Verify that exclusive group locks are honored, i.e., verify that if someone |

148 |
-- holds a lock, then no one else can hold a lock on an exclusive lock on an |

149 |
-- implied lock. |

150 |
prop_LockImplicationX :: Property |

151 |
prop_LockImplicationX = |

152 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

153 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

154 |
forAll (arbitrary `suchThat` (/= a)) $ \b -> |

155 |
let bExclusive = M.keysSet . M.filter (== OwnExclusive) $ listLocks b state |

156 |
in printTestCase "Others cannot have an exclusive lock on an implied lock" . |

157 |
flip all (M.keys $ listLocks a state) $ \lock -> |

158 |
flip all (lockImplications lock) $ \impliedlock -> |

159 |
not $ S.member impliedlock bExclusive |

160 | |

161 |
-- | Verify that shared group locks are honored, i.e., verify that if someone |

162 |
-- holds an exclusive lock, then no one else can hold any form on lock on an |

163 |
-- implied lock. |

164 |
prop_LockImplicationS :: Property |

165 |
prop_LockImplicationS = |

166 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

167 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

168 |
forAll (arbitrary `suchThat` (/= a)) $ \b -> |

169 |
let aExclusive = M.keys . M.filter (== OwnExclusive) $ listLocks a state |

170 |
bAll = M.keysSet $ listLocks b state |

171 |
in printTestCase "Others cannot hold locks implied by an exclusive lock" . |

172 |
flip all aExclusive $ \lock -> |

173 |
flip all (lockImplications lock) $ \impliedlock -> |

174 |
not $ S.member impliedlock bAll |

175 | |

176 |
-- | Verify that locks can only be modified by updates of the owner. |

177 |
prop_LocksStable :: Property |

178 |
prop_LocksStable = |

179 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

180 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

181 |
forAll (arbitrary `suchThat` (/= a)) $ \b -> |

182 |
forAll (arbitrary :: Gen [LockRequest TestLock]) $ \request -> |

183 |
let (state', _) = updateLocks b request state |

184 |
in (listLocks a state ==? listLocks a state') |

185 | |

186 |
-- | Verify that a given request is statisfied in list of owned locks |

187 |
requestSucceeded :: Ord a => M.Map a OwnerState -> LockRequest a -> Bool |

188 |
requestSucceeded owned (LockRequest lock status) = M.lookup lock owned == status |

189 | |

190 |
-- | Verify that lock updates are atomic, i.e., either we get all the required |

191 |
-- locks, or the state is completely unchanged. |

192 |
prop_LockupdateAtomic :: Property |

193 |
prop_LockupdateAtomic = |

194 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

195 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

196 |
forAll (arbitrary :: Gen [LockRequest TestLock]) $ \request -> |

197 |
let (state', result) = updateLocks a request state |

198 |
in if result == Ok S.empty |

199 |
then printTestCase |

200 |
("Update succeeded, but in final state " ++ show state' |

201 |
++ "not all locks are as requested") |

202 |
$ let owned = listLocks a state' |

203 |
in all (requestSucceeded owned) request |

204 |
else printTestCase |

205 |
("Update failed, but state changed to " ++ show state') |

206 |
(state == state') |

207 | |

208 |
-- | Verify that releasing a lock always succeeds. |

209 |
prop_LockReleaseSucceeds :: Property |

210 |
prop_LockReleaseSucceeds = |

211 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

212 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

213 |
forAll (arbitrary :: Gen TestLock) $ \lock -> |

214 |
let (_, result) = updateLocks a [requestRelease lock] state |

215 |
in printTestCase |

216 |
("Releasing a lock has to suceed uncondiationally, but got " |

217 |
++ show result) |

218 |
(isOk result) |

219 | |

220 |
-- | Verify the property that only the blocking owners prevent |

221 |
-- lock allocation. We deliberatly go for the expensive variant |

222 |
-- restraining by suchThat, as otherwise the number of cases actually |

223 |
-- covered is too small. |

224 |
prop_BlockSufficient :: Property |

225 |
prop_BlockSufficient = |

226 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

227 |
forAll (arbitrary :: Gen TestLock) $ \lock -> |

228 |
forAll (elements [ [requestShared lock] |

229 |
, [requestExclusive lock]]) $ \request -> |

230 |
forAll ((arbitrary :: Gen (LockAllocation TestLock TestOwner)) |

231 |
`suchThat` (genericResult (const False) (not . S.null) |

232 |
. snd . updateLocks a request)) $ \state -> |

233 |
let (_, result) = updateLocks a request state |

234 |
blockedOn = genericResult (const S.empty) id result |

235 |
in printTestCase "After all blockers release, a request must succeed" |

236 |
. isOk . snd . updateLocks a request $ F.foldl freeLocks state blockedOn |

237 | |

238 |
-- | Verify the property that every blocking owner is necessary, i.e., even |

239 |
-- if we only keep the locks of one of the blocking owners, the request still |

240 |
-- will be blocked. We deliberatly use the expensive variant of restraining |

241 |
-- to ensure good coverage. To make sure the request can always be blocked |

242 |
-- by two owners, for a shared request we request two different locks. |

243 |
prop_BlockNecessary :: Property |

244 |
prop_BlockNecessary = |

245 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

246 |
forAll (arbitrary :: Gen TestLock) $ \lock -> |

247 |
forAll (arbitrary `suchThat` (/= lock)) $ \lock' -> |

248 |
forAll (elements [ [requestShared lock, requestShared lock'] |

249 |
, [requestExclusive lock]]) $ \request -> |

250 |
forAll ((arbitrary :: Gen (LockAllocation TestLock TestOwner)) |

251 |
`suchThat` (genericResult (const False) ((>= 2) . S.size) |

252 |
. snd . updateLocks a request)) $ \state -> |

253 |
let (_, result) = updateLocks a request state |

254 |
blockers = genericResult (const S.empty) id result |

255 |
in printTestCase "Each blocker alone must block the request" |

256 |
. flip all (S.elems blockers) $ \blocker -> |

257 |
(==) (Ok $ S.singleton blocker) . snd . updateLocks a request |

258 |
. F.foldl freeLocks state |

259 |
$ S.filter (/= blocker) blockers |

260 | |

261 |
-- | Verify that opportunistic union only increases the locks held. |

262 |
prop_OpportunisticMonotone :: Property |

263 |
prop_OpportunisticMonotone = |

264 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

265 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

266 |
forAll ((choose (1,3) >>= vector) :: Gen [(TestLock, OwnerState)]) $ \req -> |

267 |
let (state', _) = opportunisticLockUnion a req state |

268 |
oldOwned = listLocks a state |

269 |
oldLocks = M.keys oldOwned |

270 |
newOwned = listLocks a state' |

271 |
in printTestCase "Opportunistic union may only increase the set of locks held" |

272 |
. flip all oldLocks $ \lock -> |

273 |
M.lookup lock newOwned >= M.lookup lock oldOwned |

274 | |

275 |
-- | Verify the result list of the opportunistic union: if a lock is not in |

276 |
-- the result that, than its state has not changed, and if it is, it is as |

277 |
-- requested. The latter property is tested in that liberal way, so that we |

278 |
-- really can take arbitrary requests, including those that require both, shared |

279 |
-- and exlusive state for the same lock. |

280 |
prop_OpportunisticAnswer :: Property |

281 |
prop_OpportunisticAnswer = |

282 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

283 |
forAll (arbitrary :: Gen TestOwner) $ \a -> |

284 |
forAll ((choose (1,3) >>= vector) :: Gen [(TestLock, OwnerState)]) $ \req -> |

285 |
let (state', result) = opportunisticLockUnion a req state |

286 |
oldOwned = listLocks a state |

287 |
newOwned = listLocks a state' |

288 |
involvedLocks = M.keys oldOwned ++ map fst req |

289 |
in conjoin [ printTestCase ("Locks not in the answer set " ++ show result |

290 |
++ " may not be changed, but found " |

291 |
++ show state') |

292 |
. flip all involvedLocks $ \lock -> |

293 |
(lock `S.member` result) |

294 |
|| (M.lookup lock oldOwned == M.lookup lock newOwned) |

295 |
, printTestCase ("Locks not in the answer set " ++ show result |

296 |
++ " must be as requested, but found " |

297 |
++ show state') |

298 |
. flip all involvedLocks $ \lock -> |

299 |
(lock `S.notMember` result) |

300 |
|| maybe False (flip elem req . (,) lock) |

301 |
(M.lookup lock newOwned) |

302 |
] |

303 | |

304 |
instance J.JSON TestOwner where |

305 |
showJSON (TestOwner x) = J.showJSON x |

306 |
readJSON = (>>= return . TestOwner) . J.readJSON |

307 | |

308 |
instance J.JSON TestLock where |

309 |
showJSON = J.showJSON . show |

310 |
readJSON = (>>= return . read) . J.readJSON |

311 | |

312 |
-- | Verify that for LockAllocation we have readJSON . showJSON = Ok. |

313 |
prop_ReadShow :: Property |

314 |
prop_ReadShow = |

315 |
forAll (arbitrary :: Gen (LockAllocation TestLock TestOwner)) $ \state -> |

316 |
J.readJSON (J.showJSON state) ==? J.Ok state |

317 | |

318 |
testSuite "Locking/Allocation" |

319 |
[ 'prop_LocksDisjoint |

320 |
, 'prop_LockImplicationX |

321 |
, 'prop_LockImplicationS |

322 |
, 'prop_LocksStable |

323 |
, 'prop_LockupdateAtomic |

324 |
, 'prop_LockReleaseSucceeds |

325 |
, 'prop_BlockSufficient |

326 |
, 'prop_BlockNecessary |

327 |
, 'prop_OpportunisticMonotone |

328 |
, 'prop_OpportunisticAnswer |

329 |
, 'prop_ReadShow |

330 |
] |