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