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