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<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                        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(OctagonStateTransitionWatcher* 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.currentFlags _onqueueSetFlag:flag];
 290         [self _onqueuePokeStateMachine];
 291     });
 292 }
 293
 294 - (void)handlePendingFlag:(OctagonPendingFlag *)pendingFlag {
 295     dispatch_sync(self.queue, ^{
 296         [self _onqueueHandlePendingFlag:pendingFlag];
 297     });
 298 }
 299
 300 - (void)_onqueueHandlePendingFlag:(OctagonPendingFlag*)pendingFlag {
 301     dispatch_assert_queue(self.queue);
 302
 303     // Overwrite any existing pending flag!
 304     self.pendingFlags[pendingFlag.flag] = pendingFlag;
 305
 306     // Do we need to recheck any conditions? Anything which is currently the state of the world needs checking
 307     OctagonPendingConditions recheck = pendingFlag.conditions & self.currentConditions;
 308     if(recheck != 0x0) {
 309         // Technically don't need this if, but it adds readability
 310         self.currentConditions &= ~recheck;
 311     }
 312
 313     [self _onqueueRecheckConditions];
 314     [self _onqueueSendAnyPendingFlags];
 315 }
 316
 317 - (void)disablePendingFlags {
 318     dispatch_sync(self.queue, ^{
 319         self.allowPendingFlags = false;
 320     });
 321 }
 322
 323 - (NSDictionary<NSString*, NSString*>*)dumpPendingFlags
 324 {
 325     __block NSMutableDictionary<NSString*, NSString*>* d = [NSMutableDictionary dictionary];
 326     dispatch_sync(self.queue, ^{
 327         for(OctagonFlag* flag in [self.pendingFlags allKeys]) {
 328             d[flag] = [self.pendingFlags[flag] description];
 329         }
 330     });
 331
 332     return d;
 333 }
 334
 335 - (NSArray<OctagonFlag*>*)possiblePendingFlags
 336 {
 337     return [self.pendingFlags allKeys];
 338 }
 339
 340 - (void)_onqueueRecheckConditions
 341 {
 342     dispatch_assert_queue(self.queue);
 343
 344     if(!self.allowPendingFlags) {
 345         return;
 346     }
 347
 348     NSArray<OctagonPendingFlag*>* flags = [self.pendingFlags.allValues copy];
 349     OctagonPendingConditions allConditions = 0;
 350     for(OctagonPendingFlag* flag in flags) {
 351         allConditions |= flag.conditions;
 352     }
 353     if(allConditions == 0x0) {
 354         // No conditions? Don't bother.
 355         return;
 356     }
 357
 358     // We need to recheck everything that is not currently the state of the world
 359     OctagonPendingConditions pendingConditions = allConditions & ~(self.currentConditions);
 360
 361     // But we don't need to recheck anything that's currently being checked
 362     OctagonPendingConditions conditionsToCheck = pendingConditions & ~(self.conditionChecksInFlight);
 363
 364     WEAKIFY(self);
 365
 366     if(conditionsToCheck & OctagonPendingConditionsDeviceUnlocked) {
 367         statemachinelog("conditions", "Waiting for unlock");
 368         self.checkUnlockOperation = [NSBlockOperation blockOperationWithBlock:^{
 369             STRONGIFY(self);
 370             dispatch_sync(self.queue, ^{
 371                 statemachinelog("pending-flag", "Unlock occurred");
 372                 self.currentConditions |= OctagonPendingConditionsDeviceUnlocked;
 373                 self.conditionChecksInFlight &= ~OctagonPendingConditionsDeviceUnlocked;
 374                 [self _onqueueSendAnyPendingFlags];
 375             });
 376         }];
 377         self.conditionChecksInFlight |= OctagonPendingConditionsDeviceUnlocked;
 378
 379         [self.checkUnlockOperation addNullableDependency:self.lockStateTracker.unlockDependency];
 380         [self.operationQueue addOperation:self.checkUnlockOperation];
 381     }
 382 }
 383
 384 - (void)_onqueueSendAnyPendingFlags
 385 {
 386     dispatch_assert_queue(self.queue);
 387
 388     if(!self.allowPendingFlags) {
 389         return;
 390     }
 391
 392     // Copy pending flags so we can edit the list
 393     NSArray<OctagonPendingFlag*>* flags = [self.pendingFlags.allValues copy];
 394     bool setFlag = false;
 395
 396     NSDate* now = [NSDate date];
 397     NSDate* earliestDeadline = nil;
 398     for(OctagonPendingFlag* pendingFlag in flags) {
 399         bool send = true;
 400
 401         if(pendingFlag.fireTime) {
 402             if([pendingFlag.fireTime compare:now] == NSOrderedAscending) {
 403                 statemachinelog("pending-flag", "Delay has ended for pending flag %@", pendingFlag.flag);
 404             } else {
 405                 send = false;
 406                 earliestDeadline = earliestDeadline == nil ?
 407                     pendingFlag.fireTime :
 408                     [earliestDeadline earlierDate:pendingFlag.fireTime];
 409             }
 410         }
 411
 412         if(pendingFlag.conditions != 0x0) {
 413             // Also, send the flag if the conditions are right
 414             if((pendingFlag.conditions & self.currentConditions) == pendingFlag.conditions) {
 415                 // leave send alone!
 416                 statemachinelog("pending-flag", "Conditions are right for %@", pendingFlag.flag);
 417             } else {
 418                 send = false;
 419             }
 420         }
 421
 422         if(send) {
 423             [self.currentFlags _onqueueSetFlag:pendingFlag.flag];
 424             self.pendingFlags[pendingFlag.flag] = nil;
 425             setFlag = true;
 426         }
 427     }
 428
 429     if(earliestDeadline != nil) {
 430         NSTimeInterval delay = [earliestDeadline timeIntervalSinceDate:now];
 431         uint64_t delayNanoseconds = delay * NSEC_PER_SEC;
 432
 433         [self.pendingFlagsScheduler triggerAt:delayNanoseconds];
 434     }
 435
 436     if(setFlag) {
 437         [self _onqueuePokeStateMachine];
 438     }
 439 }
 440
 441 #pragma mark - Client Services
 442
 443 - (BOOL)isPaused
 444 {
 445     __block BOOL ret = false;
 446     dispatch_sync(self.queue, ^{
 447         ret = self.nextStateMachineCycleOperation == nil;
 448     });
 449
 450     return ret;
 451 }
 452
 453 - (void)startOperation {
 454     dispatch_sync(self.queue, ^{
 455         if(self.holdStateMachineOperation) {
 456             [self.operationQueue addOperation: self.holdStateMachineOperation];
 457             self.holdStateMachineOperation = nil;
 458         }
 459     });
 460 }
 461
 462 - (void)haltOperation
 463 {
 464     dispatch_sync(self.queue, ^{
 465         if(self.holdStateMachineOperation) {
 466             [self.operationQueue addOperation:self.holdStateMachineOperation];
 467             self.holdStateMachineOperation = nil;
 468         }
 469
 470         self.halted = true;
 471         self.allowPendingFlags = false;
 472
 473         // Ask the state machine to halt itself
 474         [self _onqueuePokeStateMachine];
 475     });
 476
 477     [self.nextStateMachineCycleOperation waitUntilFinished];
 478 }
 479
 480 - (void)handleExternalRequest:(OctagonStateTransitionRequest<CKKSResultOperation<OctagonStateTransitionOperationProtocol>*>*)request
 481 {
 482     dispatch_sync(self.queue, ^{
 483         [self.stateMachineRequests addObject:request];
 484         [self _onqueuePokeStateMachine];
 485     });
 486 }
 487
 488 - (void)registerStateTransitionWatcher:(OctagonStateTransitionWatcher*)watcher
 489 {
 490     dispatch_sync(self.queue, ^{
 491         [self.stateMachineWatchers addObject: watcher];
 492         [self _onqueuePokeStateMachine];
 493     });
 494 }
 495
 496 #pragma mark - RPC Helpers
 497
 498 - (void)doSimpleStateMachineRPC:(NSString*)name
 499                              op:(CKKSResultOperation<OctagonStateTransitionOperationProtocol>*)op
 500                    sourceStates:(NSSet<OctagonState*>*)sourceStates
 501                           reply:(nonnull void (^)(NSError * _Nullable))reply
 502 {
 503     statemachinelog("state-rpc", "Beginning a '%@' rpc", name);
 504
 505     OctagonStateTransitionRequest* request = [[OctagonStateTransitionRequest alloc] init:name
 506                                                                             sourceStates:sourceStates
 507                                                                              serialQueue:self.queue
 508                                                                                  timeout:10*NSEC_PER_SEC
 509                                                                             transitionOp:op];
 510     [self handleExternalRequest:request];
 511
 512     WEAKIFY(self);
 513     CKKSResultOperation* callback = [CKKSResultOperation named:[NSString stringWithFormat: @"%@-callback", name]
 514                                                      withBlock:^{
 515                                                          STRONGIFY(self);
 516                                                          statemachinelog("state-rpc", "Returning '%@' result: %@", name, op.error ?: @"no error");
 517                                                          reply(op.error);
 518                                                      }];
 519     [callback addDependency:op];
 520     [self.operationQueue addOperation: callback];
 521 }
 522
 523 - (void)setWatcherTimeout:(uint64_t)timeout
 524 {
 525     self.timeout = timeout;
 526 }
 527
 528 - (void)doWatchedStateMachineRPC:(NSString*)name
 529                     sourceStates:(NSSet<OctagonState*>*)sourceStates
 530                             path:(OctagonStateTransitionPath*)path
 531                            reply:(nonnull void (^)(NSError *error))reply
 532 {
 533     statemachinelog("state-rpc", "Beginning a '%@' rpc", name);
 534
 535     CKKSResultOperation<OctagonStateTransitionOperationProtocol>* initialTransitionOp
 536         = [OctagonStateTransitionOperation named:[NSString stringWithFormat:@"intial-transition-%@", name]
 537                                         entering:path.initialState];
 538
 539     // Note that this has an initial timeout of 10s, and isn't configurable.
 540     OctagonStateTransitionRequest* request = [[OctagonStateTransitionRequest alloc] init:name
 541                                                                             sourceStates:sourceStates
 542                                                                              serialQueue:self.queue
 543                                                                                  timeout:10 * NSEC_PER_SEC
 544                                                                             transitionOp:initialTransitionOp];
 545
 546     OctagonStateTransitionWatcher* watcher = [[OctagonStateTransitionWatcher alloc] initNamed:[NSString stringWithFormat:@"watcher-%@", name]
 547                                                                                   serialQueue:self.queue
 548                                                                                          path:path
 549                                                                                initialRequest:request];
 550     [watcher timeout:self.timeout?:120*NSEC_PER_SEC];
 551
 552     [self registerStateTransitionWatcher:watcher];
 553
 554     WEAKIFY(self);
 555     CKKSResultOperation* replyOp = [CKKSResultOperation named:[NSString stringWithFormat: @"%@-callback", name]
 556                                                     withBlock:^{
 557                                                         STRONGIFY(self);
 558                                                         statemachinelog("state-rpc", "Returning '%@' result: %@", name, watcher.result.error ?: @"no error");
 559                                                         reply(watcher.result.error);
 560                                                     }];
 561     [replyOp addDependency:watcher.result];
 562     [self.operationQueue addOperation:replyOp];
 563
 564
 565     [self handleExternalRequest:request];
 566 }
 567
 568 @end
 569
 570 #endif