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"
12 #define statemachinelog(scope, format, ...) \
14 os_log(secLogObjForCFScope((__bridge CFStringRef)[NSString stringWithFormat:@"%@-%@", self.name, @(scope)]), \
19 @interface OctagonStateMachine ()
21 OctagonState* _currentState;
24 @property (weak) id<OctagonStateMachineEngine> stateEngine;
26 @property dispatch_queue_t queue;
27 @property NSOperationQueue* operationQueue;
29 @property NSString* name;
32 @property CKKSCondition* paused;
33 @property OctagonState* currentState;
34 @property OctagonFlags* currentFlags;
36 // Set this to an operation to pause the state machine in-flight
37 @property NSOperation* holdStateMachineOperation;
39 @property (nullable) CKKSResultOperation* nextStateMachineCycleOperation;
41 @property NSMutableArray<OctagonStateTransitionRequest<CKKSResultOperation<OctagonStateTransitionOperationProtocol>*>*>* stateMachineRequests;
42 @property NSMutableArray<id<OctagonStateTransitionWatcherProtocol>>* stateMachineWatchers;
44 @property BOOL halted;
45 @property bool allowPendingFlags;
46 @property NSMutableDictionary<OctagonFlag*, OctagonPendingFlag*>* pendingFlags;
47 @property CKKSNearFutureScheduler* pendingFlagsScheduler;
49 @property OctagonPendingConditions conditionChecksInFlight;
50 @property OctagonPendingConditions currentConditions;
51 @property NSOperation* checkUnlockOperation;
54 @implementation OctagonStateMachine
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
64 if ((self = [super init])) {
67 _lockStateTracker = lockStateTracker;
68 _conditionChecksInFlight = 0;
69 _currentConditions = 0;
71 // Every state machine starts in OctagonStateMachineNotStarted, so help them out a bit.
72 _allowableStates = [possibleStates setByAddingObjectsFromArray:@[OctagonStateMachineNotStarted, OctagonStateMachineHalted]];
75 _operationQueue = [[NSOperationQueue alloc] init];
76 _currentFlags = [[OctagonFlags alloc] initWithQueue:queue flags:possibleFlags];
78 _stateEngine = stateEngine;
80 _holdStateMachineOperation = [NSBlockOperation blockOperationWithBlock:^{}];
83 _stateConditions = [[NSMutableDictionary alloc] init];
84 [possibleStates enumerateObjectsUsingBlock:^(OctagonState * _Nonnull obj, BOOL * _Nonnull stop) {
85 self.stateConditions[obj] = [[CKKSCondition alloc] init];
88 // Use the setter method to set the condition variables
89 self.currentState = OctagonStateMachineNotStarted;
91 _stateMachineRequests = [NSMutableArray array];
92 _stateMachineWatchers = [NSMutableArray array];
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
103 dispatch_sync(self.queue, ^{
104 [self _onqueueSendAnyPendingFlags];
108 OctagonStateTransitionOperation* initializeOp = [OctagonStateTransitionOperation named:@"initialize"
109 entering:initialState];
110 [initializeOp addDependency:_holdStateMachineOperation];
111 [_operationQueue addOperation:initializeOp];
113 _paused = [[CKKSCondition alloc] init];
115 _nextStateMachineCycleOperation = [self createOperationToFinishAttempt:initializeOp];
116 [_operationQueue addOperation:_nextStateMachineCycleOperation];
121 - (NSString*)pendingFlagsString
123 return [self.pendingFlags.allValues componentsJoinedByString:@","];
126 - (NSString*)description
128 NSString* pendingFlags = @"";
129 if(self.pendingFlags.count != 0) {
130 pendingFlags = [NSString stringWithFormat:@" (pending: %@)", [self pendingFlagsString]];
132 return [NSString stringWithFormat:@"<OctagonStateMachine(%@,%@,%@)>", self.name, self.currentState, pendingFlags];
135 #pragma mark - Bookkeeping
137 - (id<OctagonFlagSetter>)flags {
138 return self.currentFlags;
141 - (OctagonState* _Nonnull)currentState {
142 return _currentState;
145 - (void)setCurrentState:(OctagonState* _Nonnull)state {
146 if((state == nil && _currentState == nil) || ([state isEqualToString:_currentState])) {
147 // No change, do nothing.
149 // Fixup the condition variables as part of setting this state
151 self.stateConditions[_currentState] = [[CKKSCondition alloc] init];
154 NSAssert([self.allowableStates containsObject:state], @"state machine tried to enter unknown state %@", state);
155 _currentState = state;
158 [self.stateConditions[state] fulfill];
163 - (OctagonState* _Nonnull)waitForState:(OctagonState* _Nonnull)wantedState wait:(uint64_t)timeout {
164 if ([self.stateConditions[wantedState] wait:timeout]) {
165 return _currentState;
171 #pragma mark - Machinery
173 - (CKKSResultOperation<OctagonStateTransitionOperationProtocol>* _Nullable)_onqueueNextStateMachineTransition
175 dispatch_assert_queue(self.queue);
178 if([self.currentState isEqualToString:OctagonStateMachineHalted]) {
181 return [OctagonStateTransitionOperation named:@"halt"
182 entering:OctagonStateMachineHalted];
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];
192 statemachinelog("state", "Running state machine request %@ (from %@)", request, self.currentState);
198 // Ask the stateEngine what it would like to do
199 return [self.stateEngine _onqueueNextStateMachineTransition:self.currentState
200 flags:self.currentFlags
204 - (void)_onqueueStartNextStateMachineOperation:(bool)immediatelyAfterPreviousOp {
205 dispatch_assert_queue(self.queue);
207 // early-exit if there's an existing operation. That operation will call this function after it's done
208 if(self.nextStateMachineCycleOperation) {
212 CKKSResultOperation<OctagonStateTransitionOperationProtocol>* nextOp = [self _onqueueNextStateMachineTransition];
214 statemachinelog("state", "Beginning state transition attempt %@", nextOp);
216 self.nextStateMachineCycleOperation = [self createOperationToFinishAttempt:nextOp];
217 [self.operationQueue addOperation:self.nextStateMachineCycleOperation];
219 [nextOp addNullableDependency:self.holdStateMachineOperation];
220 nextOp.qualityOfService = NSQualityOfServiceUserInitiated;
221 [self.operationQueue addOperation:nextOp];
223 if(!immediatelyAfterPreviousOp) {
224 self.paused = [[CKKSCondition alloc] init];
227 statemachinelog("state", "State machine rests (%@, f:[%@] p:[%@])", self.currentState, [self.currentFlags contentsAsString], [self pendingFlagsString]);
228 [self.paused fulfill];
233 - (CKKSResultOperation*)createOperationToFinishAttempt:(CKKSResultOperation<OctagonStateTransitionOperationProtocol>*)op
237 CKKSResultOperation* followUp = [CKKSResultOperation named:@"octagon-state-follow-up" withBlock:^{
240 dispatch_sync(self.queue, ^{
241 statemachinelog("state", "Finishing state transition attempt (ending in %@, intended: %@, f:[%@], p:[%@]): %@ %@",
244 [self.currentFlags contentsAsString],
245 [self pendingFlagsString],
247 op.error ?: @"(no error)");
249 for(id<OctagonStateTransitionWatcherProtocol> watcher in self.stateMachineWatchers) {
250 statemachinelog("state", "notifying watcher: %@", watcher);
251 [watcher onqueueHandleTransition:op];
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];
261 self.currentState = op.nextState;
262 self.nextStateMachineCycleOperation = nil;
264 [self _onqueueStartNextStateMachineOperation:true];
267 [followUp addNullableDependency:self.holdStateMachineOperation];
268 [followUp addNullableDependency:op];
269 followUp.qualityOfService = NSQualityOfServiceUserInitiated;
273 - (void)pokeStateMachine
275 dispatch_sync(self.queue, ^{
276 [self _onqueuePokeStateMachine];
280 - (void)_onqueuePokeStateMachine
282 dispatch_assert_queue(self.queue);
283 [self _onqueueStartNextStateMachineOperation:false];
286 - (void)handleFlag:(OctagonFlag*)flag
288 dispatch_sync(self.queue, ^{
289 [self _onqueueHandleFlag:flag];
294 - (void)_onqueueHandleFlag:(OctagonFlag*)flag
296 dispatch_assert_queue(self.queue);
297 [self.currentFlags _onqueueSetFlag:flag];
298 [self _onqueuePokeStateMachine];
301 - (void)handlePendingFlag:(OctagonPendingFlag *)pendingFlag {
302 dispatch_sync(self.queue, ^{
303 [self _onqueueHandlePendingFlag:pendingFlag];
307 - (void)_onqueueHandlePendingFlag:(OctagonPendingFlag*)pendingFlag {
308 dispatch_assert_queue(self.queue);
310 // Overwrite any existing pending flag!
311 self.pendingFlags[pendingFlag.flag] = pendingFlag;
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;
316 // Technically don't need this if, but it adds readability
317 self.currentConditions &= ~recheck;
320 if(pendingFlag.afterOperation) {
322 NSOperation* after = [NSBlockOperation blockOperationWithBlock:^{
324 dispatch_sync(self.queue, ^{
325 statemachinelog("pending-flag", "Finished waiting for operation");
326 [self _onqueueSendAnyPendingFlags];
330 [after addNullableDependency:pendingFlag.afterOperation];
331 [self.operationQueue addOperation:after];
334 [self _onqueueRecheckConditions];
335 [self _onqueueSendAnyPendingFlags];
338 - (void)disablePendingFlags {
339 dispatch_sync(self.queue, ^{
340 self.allowPendingFlags = false;
344 - (NSDictionary<NSString*, NSString*>*)dumpPendingFlags
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];
356 - (NSArray<OctagonFlag*>*)possiblePendingFlags
358 return [self.pendingFlags allKeys];
361 - (void)_onqueueRecheckConditions
363 dispatch_assert_queue(self.queue);
365 if(!self.allowPendingFlags) {
369 NSArray<OctagonPendingFlag*>* flags = [self.pendingFlags.allValues copy];
370 OctagonPendingConditions allConditions = 0;
371 for(OctagonPendingFlag* flag in flags) {
372 allConditions |= flag.conditions;
374 if(allConditions == 0x0) {
375 // No conditions? Don't bother.
379 // We need to recheck everything that is not currently the state of the world
380 OctagonPendingConditions pendingConditions = allConditions & ~(self.currentConditions);
382 // But we don't need to recheck anything that's currently being checked
383 OctagonPendingConditions conditionsToCheck = pendingConditions & ~(self.conditionChecksInFlight);
387 if(conditionsToCheck & OctagonPendingConditionsDeviceUnlocked) {
388 statemachinelog("conditions", "Waiting for unlock");
389 self.checkUnlockOperation = [NSBlockOperation blockOperationWithBlock:^{
391 dispatch_sync(self.queue, ^{
392 statemachinelog("pending-flag", "Unlock occurred");
393 self.currentConditions |= OctagonPendingConditionsDeviceUnlocked;
394 self.conditionChecksInFlight &= ~OctagonPendingConditionsDeviceUnlocked;
395 [self _onqueueSendAnyPendingFlags];
398 self.conditionChecksInFlight |= OctagonPendingConditionsDeviceUnlocked;
400 [self.checkUnlockOperation addNullableDependency:self.lockStateTracker.unlockDependency];
401 [self.operationQueue addOperation:self.checkUnlockOperation];
405 - (void)_onqueueSendAnyPendingFlags
407 dispatch_assert_queue(self.queue);
409 if(!self.allowPendingFlags) {
413 // Copy pending flags so we can edit the list
414 NSArray<OctagonPendingFlag*>* flags = [self.pendingFlags.allValues copy];
415 bool setFlag = false;
417 NSDate* now = [NSDate date];
418 NSDate* earliestDeadline = nil;
419 for(OctagonPendingFlag* pendingFlag in flags) {
422 if(pendingFlag.fireTime) {
423 if([pendingFlag.fireTime compare:now] == NSOrderedAscending) {
424 statemachinelog("pending-flag", "Delay has ended for pending flag %@", pendingFlag.flag);
427 earliestDeadline = earliestDeadline == nil ?
428 pendingFlag.fireTime :
429 [earliestDeadline earlierDate:pendingFlag.fireTime];
433 if(pendingFlag.afterOperation) {
434 if(![pendingFlag.afterOperation isFinished]) {
437 statemachinelog("pending-flag", "Operation has ended for pending flag %@: %@", pendingFlag.flag, pendingFlag.afterOperation);
441 if(pendingFlag.conditions != 0x0) {
442 // Also, send the flag if the conditions are right
443 if((pendingFlag.conditions & self.currentConditions) == pendingFlag.conditions) {
445 statemachinelog("pending-flag", "Conditions are right for %@", pendingFlag.flag);
452 [self.currentFlags _onqueueSetFlag:pendingFlag.flag];
453 self.pendingFlags[pendingFlag.flag] = nil;
458 if(earliestDeadline != nil) {
459 NSTimeInterval delay = [earliestDeadline timeIntervalSinceDate:now];
460 uint64_t delayNanoseconds = delay * NSEC_PER_SEC;
462 [self.pendingFlagsScheduler triggerAt:delayNanoseconds];
466 [self _onqueuePokeStateMachine];
470 #pragma mark - Client Services
474 __block BOOL ret = false;
475 dispatch_sync(self.queue, ^{
476 ret = self.nextStateMachineCycleOperation == nil;
482 - (void)startOperation {
483 dispatch_sync(self.queue, ^{
484 if(self.holdStateMachineOperation) {
485 [self.operationQueue addOperation: self.holdStateMachineOperation];
486 self.holdStateMachineOperation = nil;
491 - (void)haltOperation
493 dispatch_sync(self.queue, ^{
494 if(self.holdStateMachineOperation) {
495 [self.operationQueue addOperation:self.holdStateMachineOperation];
496 self.holdStateMachineOperation = nil;
500 self.allowPendingFlags = false;
502 // Ask the state machine to halt itself
503 [self _onqueuePokeStateMachine];
506 [self.nextStateMachineCycleOperation waitUntilFinished];
509 - (void)handleExternalRequest:(OctagonStateTransitionRequest<CKKSResultOperation<OctagonStateTransitionOperationProtocol>*>*)request
511 dispatch_sync(self.queue, ^{
512 [self.stateMachineRequests addObject:request];
513 [self _onqueuePokeStateMachine];
518 - (void)registerStateTransitionWatcher:(OctagonStateTransitionWatcher*)watcher
520 dispatch_sync(self.queue, ^{
521 [self.stateMachineWatchers addObject: watcher];
522 [self _onqueuePokeStateMachine];
526 - (void)registerMultiStateArrivalWatcher:(OctagonStateMultiStateArrivalWatcher*)watcher
528 dispatch_sync(self.queue, ^{
529 if([watcher.states containsObject:self.currentState]) {
530 [watcher onqueueEnterState:self.currentState];
532 [self.stateMachineWatchers addObject:watcher];
533 [self _onqueuePokeStateMachine];
538 #pragma mark - RPC Helpers
540 - (void)doSimpleStateMachineRPC:(NSString*)name
541 op:(CKKSResultOperation<OctagonStateTransitionOperationProtocol>*)op
542 sourceStates:(NSSet<OctagonState*>*)sourceStates
543 reply:(nonnull void (^)(NSError * _Nullable))reply
545 statemachinelog("state-rpc", "Beginning a '%@' rpc", name);
547 OctagonStateTransitionRequest* request = [[OctagonStateTransitionRequest alloc] init:name
548 sourceStates:sourceStates
549 serialQueue:self.queue
550 timeout:10*NSEC_PER_SEC
552 [self handleExternalRequest:request];
555 CKKSResultOperation* callback = [CKKSResultOperation named:[NSString stringWithFormat: @"%@-callback", name]
558 statemachinelog("state-rpc", "Returning '%@' result: %@", name, op.error ?: @"no error");
561 [callback addDependency:op];
562 [self.operationQueue addOperation: callback];
565 - (void)setWatcherTimeout:(uint64_t)timeout
567 self.timeout = timeout;
570 - (CKKSResultOperation*)doWatchedStateMachineRPC:(NSString*)name
571 sourceStates:(NSSet<OctagonState*>*)sourceStates
572 path:(OctagonStateTransitionPath*)path
573 reply:(nonnull void (^)(NSError *error))reply
575 statemachinelog("state-rpc", "Beginning a '%@' rpc", name);
577 CKKSResultOperation<OctagonStateTransitionOperationProtocol>* initialTransitionOp
578 = [OctagonStateTransitionOperation named:[NSString stringWithFormat:@"intial-transition-%@", name]
579 entering:path.initialState];
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];
588 OctagonStateTransitionWatcher* watcher = [[OctagonStateTransitionWatcher alloc] initNamed:[NSString stringWithFormat:@"watcher-%@", name]
589 serialQueue:self.queue
591 initialRequest:request];
592 [watcher timeout:self.timeout?:120*NSEC_PER_SEC];
594 [self registerStateTransitionWatcher:watcher];
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");
600 reply(watcher.result.error);
602 op.error = watcher.result.error;
605 [replyOp addDependency:watcher.result];
606 [self.operationQueue addOperation:replyOp];
609 [self handleExternalRequest:request];