]> git.saurik.com Git - apple/security.git/blob - keychain/ot/OctagonStateMachine.m
Security-59754.41.1.tar.gz
[apple/security.git] / keychain / ot / OctagonStateMachine.m
1
2 #if OCTAGON
3
4 #import "keychain/ot/OctagonStateMachine.h"
5 #import "keychain/ot/OctagonStateMachineObservers.h"
6 #import "keychain/ot/ObjCImprovements.h"
7 #import "keychain/ckks/CKKSNearFutureScheduler.h"
8 #import "keychain/ckks/CKKS.h"
9 #import "keychain/ot/OTStates.h"
10 #import "utilities/debugging.h"
11
12 #define statemachinelog(scope, format, ...) \
13 { \
14 os_log(secLogObjForCFScope((__bridge CFStringRef)[NSString stringWithFormat:@"%@-%@", self.name, @(scope)]), \
15 format, \
16 ##__VA_ARGS__); \
17 }
18
19 @interface OctagonStateMachine ()
20 {
21 OctagonState* _currentState;
22 }
23
24 @property (weak) id<OctagonStateMachineEngine> stateEngine;
25
26 @property dispatch_queue_t queue;
27 @property NSOperationQueue* operationQueue;
28
29 @property NSString* name;
30
31 // Make writable
32 @property CKKSCondition* paused;
33 @property OctagonState* currentState;
34 @property OctagonFlags* currentFlags;
35
36 // Set this to an operation to pause the state machine in-flight
37 @property NSOperation* holdStateMachineOperation;
38
39 @property (nullable) CKKSResultOperation* nextStateMachineCycleOperation;
40
41 @property NSMutableArray<OctagonStateTransitionRequest<CKKSResultOperation<OctagonStateTransitionOperationProtocol>*>*>* stateMachineRequests;
42 @property NSMutableArray<id<OctagonStateTransitionWatcherProtocol>>* stateMachineWatchers;
43
44 @property BOOL halted;
45 @property bool allowPendingFlags;
46 @property NSMutableDictionary<OctagonFlag*, OctagonPendingFlag*>* pendingFlags;
47 @property CKKSNearFutureScheduler* pendingFlagsScheduler;
48
49 @property OctagonPendingConditions conditionChecksInFlight;
50 @property OctagonPendingConditions currentConditions;
51 @property NSOperation* checkUnlockOperation;
52 @end
53
54 @implementation OctagonStateMachine
55
56 - (instancetype)initWithName:(NSString*)name
57 states:(NSSet<OctagonState*>*)possibleStates
58 flags:(NSSet<OctagonFlag*>*)possibleFlags
59 initialState:(OctagonState*)initialState
60 queue:(dispatch_queue_t)queue
61 stateEngine:(id<OctagonStateMachineEngine>)stateEngine
62 lockStateTracker:(CKKSLockStateTracker*)lockStateTracker
63 {
64 if ((self = [super init])) {
65 _name = name;
66
67 _lockStateTracker = lockStateTracker;
68 _conditionChecksInFlight = 0;
69 _currentConditions = 0;
70
71 // Every state machine starts in OctagonStateMachineNotStarted, so help them out a bit.
72 _allowableStates = [possibleStates setByAddingObjectsFromArray:@[OctagonStateMachineNotStarted, OctagonStateMachineHalted]];
73
74 _queue = queue;
75 _operationQueue = [[NSOperationQueue alloc] init];
76 _currentFlags = [[OctagonFlags alloc] initWithQueue:queue flags:possibleFlags];
77
78 _stateEngine = stateEngine;
79
80 _holdStateMachineOperation = [NSBlockOperation blockOperationWithBlock:^{}];
81 _halted = false;
82
83 _stateConditions = [[NSMutableDictionary alloc] init];
84 [possibleStates enumerateObjectsUsingBlock:^(OctagonState * _Nonnull obj, BOOL * _Nonnull stop) {
85 self.stateConditions[obj] = [[CKKSCondition alloc] init];
86 }];
87
88 // Use the setter method to set the condition variables
89 self.currentState = OctagonStateMachineNotStarted;
90
91 _stateMachineRequests = [NSMutableArray array];
92 _stateMachineWatchers = [NSMutableArray array];
93
94 WEAKIFY(self);
95 _allowPendingFlags = true;
96 _pendingFlags = [NSMutableDictionary dictionary];
97 _pendingFlagsScheduler = [[CKKSNearFutureScheduler alloc] initWithName:[NSString stringWithFormat:@"%@-pending-flag", name]
98 delay:100*NSEC_PER_MSEC
99 keepProcessAlive:false
100 dependencyDescriptionCode:CKKSResultDescriptionPendingFlag
101 block:^{
102 STRONGIFY(self);
103 dispatch_sync(self.queue, ^{
104 [self _onqueueSendAnyPendingFlags];
105 });
106 }];
107
108 OctagonStateTransitionOperation* initializeOp = [OctagonStateTransitionOperation named:@"initialize"
109 entering:initialState];
110 [initializeOp addDependency:_holdStateMachineOperation];
111 [_operationQueue addOperation:initializeOp];
112
113 _paused = [[CKKSCondition alloc] init];
114
115 _nextStateMachineCycleOperation = [self createOperationToFinishAttempt:initializeOp];
116 [_operationQueue addOperation:_nextStateMachineCycleOperation];
117 }
118 return self;
119 }
120
121 - (NSString*)pendingFlagsString
122 {
123 return [self.pendingFlags.allValues componentsJoinedByString:@","];
124 }
125
126 - (NSString*)description
127 {
128 NSString* pendingFlags = @"";
129 if(self.pendingFlags.count != 0) {
130 pendingFlags = [NSString stringWithFormat:@" (pending: %@)", [self pendingFlagsString]];
131 }
132 return [NSString stringWithFormat:@"<OctagonStateMachine(%@,%@,%@)>", self.name, self.currentState, pendingFlags];
133 }
134
135 #pragma mark - Bookkeeping
136
137 - (id<OctagonFlagSetter>)flags {
138 return self.currentFlags;
139 }
140
141 - (OctagonState* _Nonnull)currentState {
142 return _currentState;
143 }
144
145 - (void)setCurrentState:(OctagonState* _Nonnull)state {
146 if((state == nil && _currentState == nil) || ([state isEqualToString:_currentState])) {
147 // No change, do nothing.
148 } else {
149 // Fixup the condition variables as part of setting this state
150 if(_currentState) {
151 self.stateConditions[_currentState] = [[CKKSCondition alloc] init];
152 }
153
154 NSAssert([self.allowableStates containsObject:state], @"state machine tried to enter unknown state %@", state);
155 _currentState = state;
156
157 if(state) {
158 [self.stateConditions[state] fulfill];
159 }
160 }
161 }
162
163 - (OctagonState* _Nonnull)waitForState:(OctagonState* _Nonnull)wantedState wait:(uint64_t)timeout {
164 if ([self.stateConditions[wantedState] wait:timeout]) {
165 return _currentState;
166 } else {
167 return wantedState;
168 }
169 }
170
171 #pragma mark - Machinery
172
173 - (CKKSResultOperation<OctagonStateTransitionOperationProtocol>* _Nullable)_onqueueNextStateMachineTransition
174 {
175 dispatch_assert_queue(self.queue);
176
177 if(self.halted) {
178 if([self.currentState isEqualToString:OctagonStateMachineHalted]) {
179 return nil;
180 } else {
181 return [OctagonStateTransitionOperation named:@"halt"
182 entering:OctagonStateMachineHalted];
183 }
184 }
185
186 // Check requests: do any of them want to come from this state?
187 for(OctagonStateTransitionRequest<OctagonStateTransitionOperation*>* request in self.stateMachineRequests) {
188 if([request.sourceStates containsObject:self.currentState]) {
189 OctagonStateTransitionOperation* attempt = [request _onqueueStart];
190
191 if(attempt) {
192 statemachinelog("state", "Running state machine request %@ (from %@)", request, self.currentState);
193 return attempt;
194 }
195 }
196 }
197
198 // Ask the stateEngine what it would like to do
199 return [self.stateEngine _onqueueNextStateMachineTransition:self.currentState
200 flags:self.currentFlags
201 pendingFlags:self];
202 }
203
204 - (void)_onqueueStartNextStateMachineOperation:(bool)immediatelyAfterPreviousOp {
205 dispatch_assert_queue(self.queue);
206
207 // early-exit if there's an existing operation. That operation will call this function after it's done
208 if(self.nextStateMachineCycleOperation) {
209 return;
210 }
211
212 CKKSResultOperation<OctagonStateTransitionOperationProtocol>* nextOp = [self _onqueueNextStateMachineTransition];
213 if(nextOp) {
214 statemachinelog("state", "Beginning state transition attempt %@", nextOp);
215
216 self.nextStateMachineCycleOperation = [self createOperationToFinishAttempt:nextOp];
217 [self.operationQueue addOperation:self.nextStateMachineCycleOperation];
218
219 [nextOp addNullableDependency:self.holdStateMachineOperation];
220 nextOp.qualityOfService = NSQualityOfServiceUserInitiated;
221 [self.operationQueue addOperation:nextOp];
222
223 if(!immediatelyAfterPreviousOp) {
224 self.paused = [[CKKSCondition alloc] init];
225 }
226 } else {
227 statemachinelog("state", "State machine rests (%@, f:[%@] p:[%@])", self.currentState, [self.currentFlags contentsAsString], [self pendingFlagsString]);
228 [self.paused fulfill];
229 }
230 }
231
232
233 - (CKKSResultOperation*)createOperationToFinishAttempt:(CKKSResultOperation<OctagonStateTransitionOperationProtocol>*)op
234 {
235 WEAKIFY(self);
236
237 CKKSResultOperation* followUp = [CKKSResultOperation named:@"octagon-state-follow-up" withBlock:^{
238 STRONGIFY(self);
239
240 dispatch_sync(self.queue, ^{
241 statemachinelog("state", "Finishing state transition attempt (ending in %@, intended: %@, f:[%@], p:[%@]): %@ %@",
242 op.nextState,
243 op.intendedState,
244 [self.currentFlags contentsAsString],
245 [self pendingFlagsString],
246 op,
247 op.error ?: @"(no error)");
248
249 for(id<OctagonStateTransitionWatcherProtocol> watcher in self.stateMachineWatchers) {
250 statemachinelog("state", "notifying watcher: %@", watcher);
251 [watcher onqueueHandleTransition:op];
252 }
253
254 // finished watchers can be removed from the list. Use a reversed for loop to enable removal
255 for (NSInteger i = self.stateMachineWatchers.count - 1; i >= 0; i--) {
256 if([self.stateMachineWatchers[i].result isFinished]) {
257 [self.stateMachineWatchers removeObjectAtIndex:i];
258 }
259 }
260
261 self.currentState = op.nextState;
262 self.nextStateMachineCycleOperation = nil;
263
264 [self _onqueueStartNextStateMachineOperation:true];
265 });
266 }];
267 [followUp addNullableDependency:self.holdStateMachineOperation];
268 [followUp addNullableDependency:op];
269 followUp.qualityOfService = NSQualityOfServiceUserInitiated;
270 return followUp;
271 }
272
273 - (void)pokeStateMachine
274 {
275 dispatch_sync(self.queue, ^{
276 [self _onqueuePokeStateMachine];
277 });
278 }
279
280 - (void)_onqueuePokeStateMachine
281 {
282 dispatch_assert_queue(self.queue);
283 [self _onqueueStartNextStateMachineOperation:false];
284 }
285
286 - (void)handleFlag:(OctagonFlag*)flag
287 {
288 dispatch_sync(self.queue, ^{
289 [self _onqueueHandleFlag:flag];
290 });
291 }
292
293
294 - (void)_onqueueHandleFlag:(OctagonFlag*)flag
295 {
296 dispatch_assert_queue(self.queue);
297 [self.currentFlags _onqueueSetFlag:flag];
298 [self _onqueuePokeStateMachine];
299 }
300
301 - (void)handlePendingFlag:(OctagonPendingFlag *)pendingFlag {
302 dispatch_sync(self.queue, ^{
303 [self _onqueueHandlePendingFlag:pendingFlag];
304 });
305 }
306
307 - (void)_onqueueHandlePendingFlag:(OctagonPendingFlag*)pendingFlag {
308 dispatch_assert_queue(self.queue);
309
310 // Overwrite any existing pending flag!
311 self.pendingFlags[pendingFlag.flag] = pendingFlag;
312
313 // Do we need to recheck any conditions? Anything which is currently the state of the world needs checking
314 OctagonPendingConditions recheck = pendingFlag.conditions & self.currentConditions;
315 if(recheck != 0x0) {
316 // Technically don't need this if, but it adds readability
317 self.currentConditions &= ~recheck;
318 }
319
320 if(pendingFlag.afterOperation) {
321 WEAKIFY(self);
322 NSOperation* after = [NSBlockOperation blockOperationWithBlock:^{
323 STRONGIFY(self);
324 dispatch_sync(self.queue, ^{
325 statemachinelog("pending-flag", "Finished waiting for operation");
326 [self _onqueueSendAnyPendingFlags];
327 });
328 }];
329
330 [after addNullableDependency:pendingFlag.afterOperation];
331 [self.operationQueue addOperation:after];
332 }
333
334 [self _onqueueRecheckConditions];
335 [self _onqueueSendAnyPendingFlags];
336 }
337
338 - (void)disablePendingFlags {
339 dispatch_sync(self.queue, ^{
340 self.allowPendingFlags = false;
341 });
342 }
343
344 - (NSDictionary<NSString*, NSString*>*)dumpPendingFlags
345 {
346 __block NSMutableDictionary<NSString*, NSString*>* d = [NSMutableDictionary dictionary];
347 dispatch_sync(self.queue, ^{
348 for(OctagonFlag* flag in [self.pendingFlags allKeys]) {
349 d[flag] = [self.pendingFlags[flag] description];
350 }
351 });
352
353 return d;
354 }
355
356 - (NSArray<OctagonFlag*>*)possiblePendingFlags
357 {
358 return [self.pendingFlags allKeys];
359 }
360
361 - (void)_onqueueRecheckConditions
362 {
363 dispatch_assert_queue(self.queue);
364
365 if(!self.allowPendingFlags) {
366 return;
367 }
368
369 NSArray<OctagonPendingFlag*>* flags = [self.pendingFlags.allValues copy];
370 OctagonPendingConditions allConditions = 0;
371 for(OctagonPendingFlag* flag in flags) {
372 allConditions |= flag.conditions;
373 }
374 if(allConditions == 0x0) {
375 // No conditions? Don't bother.
376 return;
377 }
378
379 // We need to recheck everything that is not currently the state of the world
380 OctagonPendingConditions pendingConditions = allConditions & ~(self.currentConditions);
381
382 // But we don't need to recheck anything that's currently being checked
383 OctagonPendingConditions conditionsToCheck = pendingConditions & ~(self.conditionChecksInFlight);
384
385 WEAKIFY(self);
386
387 if(conditionsToCheck & OctagonPendingConditionsDeviceUnlocked) {
388 statemachinelog("conditions", "Waiting for unlock");
389 self.checkUnlockOperation = [NSBlockOperation blockOperationWithBlock:^{
390 STRONGIFY(self);
391 dispatch_sync(self.queue, ^{
392 statemachinelog("pending-flag", "Unlock occurred");
393 self.currentConditions |= OctagonPendingConditionsDeviceUnlocked;
394 self.conditionChecksInFlight &= ~OctagonPendingConditionsDeviceUnlocked;
395 [self _onqueueSendAnyPendingFlags];
396 });
397 }];
398 self.conditionChecksInFlight |= OctagonPendingConditionsDeviceUnlocked;
399
400 [self.checkUnlockOperation addNullableDependency:self.lockStateTracker.unlockDependency];
401 [self.operationQueue addOperation:self.checkUnlockOperation];
402 }
403 }
404
405 - (void)_onqueueSendAnyPendingFlags
406 {
407 dispatch_assert_queue(self.queue);
408
409 if(!self.allowPendingFlags) {
410 return;
411 }
412
413 // Copy pending flags so we can edit the list
414 NSArray<OctagonPendingFlag*>* flags = [self.pendingFlags.allValues copy];
415 bool setFlag = false;
416
417 NSDate* now = [NSDate date];
418 NSDate* earliestDeadline = nil;
419 for(OctagonPendingFlag* pendingFlag in flags) {
420 bool send = true;
421
422 if(pendingFlag.fireTime) {
423 if([pendingFlag.fireTime compare:now] == NSOrderedAscending) {
424 statemachinelog("pending-flag", "Delay has ended for pending flag %@", pendingFlag.flag);
425 } else {
426 send = false;
427 earliestDeadline = earliestDeadline == nil ?
428 pendingFlag.fireTime :
429 [earliestDeadline earlierDate:pendingFlag.fireTime];
430 }
431 }
432
433 if(pendingFlag.afterOperation) {
434 if(![pendingFlag.afterOperation isFinished]) {
435 send = false;
436 } else {
437 statemachinelog("pending-flag", "Operation has ended for pending flag %@: %@", pendingFlag.flag, pendingFlag.afterOperation);
438 }
439 }
440
441 if(pendingFlag.conditions != 0x0) {
442 // Also, send the flag if the conditions are right
443 if((pendingFlag.conditions & self.currentConditions) == pendingFlag.conditions) {
444 // leave send alone!
445 statemachinelog("pending-flag", "Conditions are right for %@", pendingFlag.flag);
446 } else {
447 send = false;
448 }
449 }
450
451 if(send) {
452 [self.currentFlags _onqueueSetFlag:pendingFlag.flag];
453 self.pendingFlags[pendingFlag.flag] = nil;
454 setFlag = true;
455 }
456 }
457
458 if(earliestDeadline != nil) {
459 NSTimeInterval delay = [earliestDeadline timeIntervalSinceDate:now];
460 uint64_t delayNanoseconds = delay * NSEC_PER_SEC;
461
462 [self.pendingFlagsScheduler triggerAt:delayNanoseconds];
463 }
464
465 if(setFlag) {
466 [self _onqueuePokeStateMachine];
467 }
468 }
469
470 #pragma mark - Client Services
471
472 - (BOOL)isPaused
473 {
474 __block BOOL ret = false;
475 dispatch_sync(self.queue, ^{
476 ret = self.nextStateMachineCycleOperation == nil;
477 });
478
479 return ret;
480 }
481
482 - (void)startOperation {
483 dispatch_sync(self.queue, ^{
484 if(self.holdStateMachineOperation) {
485 [self.operationQueue addOperation: self.holdStateMachineOperation];
486 self.holdStateMachineOperation = nil;
487 }
488 });
489 }
490
491 - (void)haltOperation
492 {
493 dispatch_sync(self.queue, ^{
494 if(self.holdStateMachineOperation) {
495 [self.operationQueue addOperation:self.holdStateMachineOperation];
496 self.holdStateMachineOperation = nil;
497 }
498
499 self.halted = true;
500 self.allowPendingFlags = false;
501
502 // Ask the state machine to halt itself
503 [self _onqueuePokeStateMachine];
504 });
505
506 [self.nextStateMachineCycleOperation waitUntilFinished];
507 }
508
509 - (void)handleExternalRequest:(OctagonStateTransitionRequest<CKKSResultOperation<OctagonStateTransitionOperationProtocol>*>*)request
510 {
511 dispatch_sync(self.queue, ^{
512 [self.stateMachineRequests addObject:request];
513 [self _onqueuePokeStateMachine];
514 });
515 }
516
517
518 - (void)registerStateTransitionWatcher:(OctagonStateTransitionWatcher*)watcher
519 {
520 dispatch_sync(self.queue, ^{
521 [self.stateMachineWatchers addObject: watcher];
522 [self _onqueuePokeStateMachine];
523 });
524 }
525
526 - (void)registerMultiStateArrivalWatcher:(OctagonStateMultiStateArrivalWatcher*)watcher
527 {
528 dispatch_sync(self.queue, ^{
529 if([watcher.states containsObject:self.currentState]) {
530 [watcher onqueueEnterState:self.currentState];
531 } else {
532 [self.stateMachineWatchers addObject:watcher];
533 [self _onqueuePokeStateMachine];
534 }
535 });
536 }
537
538 #pragma mark - RPC Helpers
539
540 - (void)doSimpleStateMachineRPC:(NSString*)name
541 op:(CKKSResultOperation<OctagonStateTransitionOperationProtocol>*)op
542 sourceStates:(NSSet<OctagonState*>*)sourceStates
543 reply:(nonnull void (^)(NSError * _Nullable))reply
544 {
545 statemachinelog("state-rpc", "Beginning a '%@' rpc", name);
546
547 OctagonStateTransitionRequest* request = [[OctagonStateTransitionRequest alloc] init:name
548 sourceStates:sourceStates
549 serialQueue:self.queue
550 timeout:10*NSEC_PER_SEC
551 transitionOp:op];
552 [self handleExternalRequest:request];
553
554 WEAKIFY(self);
555 CKKSResultOperation* callback = [CKKSResultOperation named:[NSString stringWithFormat: @"%@-callback", name]
556 withBlock:^{
557 STRONGIFY(self);
558 statemachinelog("state-rpc", "Returning '%@' result: %@", name, op.error ?: @"no error");
559 reply(op.error);
560 }];
561 [callback addDependency:op];
562 [self.operationQueue addOperation: callback];
563 }
564
565 - (void)setWatcherTimeout:(uint64_t)timeout
566 {
567 self.timeout = timeout;
568 }
569
570 - (CKKSResultOperation*)doWatchedStateMachineRPC:(NSString*)name
571 sourceStates:(NSSet<OctagonState*>*)sourceStates
572 path:(OctagonStateTransitionPath*)path
573 reply:(nonnull void (^)(NSError *error))reply
574 {
575 statemachinelog("state-rpc", "Beginning a '%@' rpc", name);
576
577 CKKSResultOperation<OctagonStateTransitionOperationProtocol>* initialTransitionOp
578 = [OctagonStateTransitionOperation named:[NSString stringWithFormat:@"intial-transition-%@", name]
579 entering:path.initialState];
580
581 // Note that this has an initial timeout of 10s, and isn't configurable.
582 OctagonStateTransitionRequest* request = [[OctagonStateTransitionRequest alloc] init:name
583 sourceStates:sourceStates
584 serialQueue:self.queue
585 timeout:10 * NSEC_PER_SEC
586 transitionOp:initialTransitionOp];
587
588 OctagonStateTransitionWatcher* watcher = [[OctagonStateTransitionWatcher alloc] initNamed:[NSString stringWithFormat:@"watcher-%@", name]
589 serialQueue:self.queue
590 path:path
591 initialRequest:request];
592 [watcher timeout:self.timeout?:120*NSEC_PER_SEC];
593
594 [self registerStateTransitionWatcher:watcher];
595
596 CKKSResultOperation* replyOp = [CKKSResultOperation named:[NSString stringWithFormat: @"%@-callback", name]
597 withBlockTakingSelf:^(CKKSResultOperation * _Nonnull op) {
598 statemachinelog("state-rpc", "Returning '%@' result: %@", name, watcher.result.error ?: @"no error");
599 if(reply) {
600 reply(watcher.result.error);
601 }
602 op.error = watcher.result.error;
603 }];
604
605 [replyOp addDependency:watcher.result];
606 [self.operationQueue addOperation:replyOp];
607
608
609 [self handleExternalRequest:request];
610 return replyOp;
611 }
612
613 @end
614
615 #endif