stdlib/private/StdlibUnittest/RaceTest.swift - third_party/swift - Git at Google

 //===--- RaceTest.swift ---------------------------------------------------===//
 //
 // This source file is part of the Swift.org open source project
 //
 // Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
 // Licensed under Apache License v2.0 with Runtime Library Exception
 //
 // See https://swift.org/LICENSE.txt for license information
 // See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
 //
 //===----------------------------------------------------------------------===//
 ///
 /// This file implements support for race tests.
 ///
 /// Race test harness executes the given operation in multiple threads over a
 /// set of shared data, trying to ensure that executions overlap in time.
 ///
 /// The name "race test" does not imply that the race actually happens in the
 /// harness or in the operation being tested.  The harness contains all the
 /// necessary synchronization for its own data, and for publishing test data to
 /// threads.  But if the operation under test is, in fact, racy, it should be
 /// easier to discover the bug in this environment.
 ///
 /// Every execution of a race test is called a trial.  During a single trial
 /// the operation under test is executed multiple times in each thread over
 /// different data items (`RaceData` instances).  Different threads process
 /// data in different order.  Choosing an appropriate balance between the
 /// number of threads and data items, the harness uses the birthday paradox to
 /// increase the probability of "collisions" between threads.
 ///
 /// After performing the operation under test, the thread should observe the
 /// data in a test-dependent way to detect if presence of other concurrent
 /// actions disturbed the result.  The observation should be as short as
 /// possible, and the results should be returned as `Observation`.  Evaluation
 /// (cross-checking) of observations is deferred until the end of the trial.
 ///
 //===----------------------------------------------------------------------===//

 import SwiftPrivate
 import SwiftPrivateLibcExtras
 import SwiftPrivateThreadExtras
 #if os(macOS) || os(iOS)
 import Darwin
 #elseif os(Linux) || os(FreeBSD) || os(PS4) || os(Android) || os(Cygwin) || os(Haiku)
 import Glibc
 #elseif os(Windows)
 import MSVCRT
 import WinSDK
 #endif

 #if _runtime(_ObjC)
 import ObjectiveC
 #else
 func autoreleasepool(invoking code: () -> Void) {
   // Native runtime does not have autorelease pools.  Execute the code
   // directly.
   code()
 }
 #endif

 /// Race tests that need a fresh set of data for every trial should implement
 /// this protocol.
 ///
 /// All racing threads execute the same operation, `thread1`.
 ///
 /// Types conforming to this protocol should be structs.  (The type
 /// should be a struct to reduce unnecessary reference counting during
 /// the test.)  The types should be stateless.
 public protocol RaceTestWithPerTrialData {

   /// Input for threads.
   ///
   /// This type should be a class.  (The harness will not pass struct instances
   /// between threads correctly.)
   associatedtype RaceData : AnyObject

   /// Type of thread-local data.
   ///
   /// Thread-local data is newly created for every trial.
   associatedtype ThreadLocalData

   /// Results of the observation made after performing an operation.
   associatedtype Observation

   init()

   /// Creates a fresh instance of `RaceData`.
   func makeRaceData() -> RaceData

   /// Creates a fresh instance of `ThreadLocalData`.
   func makeThreadLocalData() -> ThreadLocalData

   /// Performs the operation under test and makes an observation.
   func thread1(
     _ raceData: RaceData, _ threadLocalData: inout ThreadLocalData) -> Observation

   /// Evaluates the observations made by all threads for a particular instance
   /// of `RaceData`.
   func evaluateObservations(
     _ observations: [Observation],
     _ sink: (RaceTestObservationEvaluation) -> Void)
 }

 /// The result of evaluating observations.
 ///
 /// Case payloads can carry test-specific data.  Results will be grouped
 /// according to it.
 public enum RaceTestObservationEvaluation : Equatable, CustomStringConvertible {
   /// Normal 'pass'.
   case pass

   /// An unusual 'pass'.
   case passInteresting(String)

   /// A failure.
   case failure
   case failureInteresting(String)

   public var description: String {
     switch self {
     case .pass:
       return "Pass"

     case .passInteresting(let s):
       return "Pass(\(s))"

     case .failure:
       return "Failure"

     case .failureInteresting(let s):
       return "Failure(\(s))"
     }
   }
 }

 public func == (
   lhs: RaceTestObservationEvaluation, rhs: RaceTestObservationEvaluation
 ) -> Bool {
   switch (lhs, rhs) {
   case (.pass, .pass),
        (.failure, .failure):
     return true

   case (.passInteresting(let s1), .passInteresting(let s2)):
     return s1 == s2

   default:
     return false
   }
 }

 /// An observation result that consists of one `UInt`.
 public struct Observation1UInt : Equatable, CustomStringConvertible {
   public var data1: UInt

   public init(_ data1: UInt) {
     self.data1 = data1
   }

   public var description: String {
     return "(\(data1))"
   }
 }

 public func == (lhs: Observation1UInt, rhs: Observation1UInt) -> Bool {
   return lhs.data1 == rhs.data1
 }

 /// An observation result that consists of four `UInt`s.
 public struct Observation4UInt : Equatable, CustomStringConvertible {
   public var data1: UInt
   public var data2: UInt
   public var data3: UInt
   public var data4: UInt

   public init(_ data1: UInt, _ data2: UInt, _ data3: UInt, _ data4: UInt) {
     self.data1 = data1
     self.data2 = data2
     self.data3 = data3
     self.data4 = data4
   }

   public var description: String {
     return "(\(data1), \(data2), \(data3), \(data4))"
   }
 }

 public func == (lhs: Observation4UInt, rhs: Observation4UInt) -> Bool {
   return
     lhs.data1 == rhs.data1 &&
     lhs.data2 == rhs.data2 &&
     lhs.data3 == rhs.data3 &&
     lhs.data4 == rhs.data4
 }

 /// An observation result that consists of three `Int`s.
 public struct Observation3Int : Equatable, CustomStringConvertible {
   public var data1: Int
   public var data2: Int
   public var data3: Int

   public init(_ data1: Int, _ data2: Int, _ data3: Int) {
     self.data1 = data1
     self.data2 = data2
     self.data3 = data3
   }

   public var description: String {
     return "(\(data1), \(data2), \(data3))"
   }
 }

 public func == (lhs: Observation3Int, rhs: Observation3Int) -> Bool {
   return
     lhs.data1 == rhs.data1 &&
     lhs.data2 == rhs.data2 &&
     lhs.data3 == rhs.data3
 }

 /// An observation result that consists of four `Int`s.
 public struct Observation4Int : Equatable, CustomStringConvertible {
   public var data1: Int
   public var data2: Int
   public var data3: Int
   public var data4: Int

   public init(_ data1: Int, _ data2: Int, _ data3: Int, _ data4: Int) {
     self.data1 = data1
     self.data2 = data2
     self.data3 = data3
     self.data4 = data4
   }

   public var description: String {
     return "(\(data1), \(data2), \(data3), \(data4))"
   }
 }

 public func == (lhs: Observation4Int, rhs: Observation4Int) -> Bool {
   return
     lhs.data1 == rhs.data1 &&
     lhs.data2 == rhs.data2 &&
     lhs.data3 == rhs.data3 &&
     lhs.data4 == rhs.data4
 }

 /// An observation result that consists of five `Int`s.
 public struct Observation5Int : Equatable, CustomStringConvertible {
   public var data1: Int
   public var data2: Int
   public var data3: Int
   public var data4: Int
   public var data5: Int

   public init(
     _ data1: Int, _ data2: Int, _ data3: Int, _ data4: Int, _ data5: Int
   ) {
     self.data1 = data1
     self.data2 = data2
     self.data3 = data3
     self.data4 = data4
     self.data5 = data5
   }

   public var description: String {
     return "(\(data1), \(data2), \(data3), \(data4), \(data5))"
   }
 }

 public func == (lhs: Observation5Int, rhs: Observation5Int) -> Bool {
   return
     lhs.data1 == rhs.data1 &&
     lhs.data2 == rhs.data2 &&
     lhs.data3 == rhs.data3 &&
     lhs.data4 == rhs.data4 &&
     lhs.data5 == rhs.data5
 }

 /// An observation result that consists of nine `Int`s.
 public struct Observation9Int : Equatable, CustomStringConvertible {
   public var data1: Int
   public var data2: Int
   public var data3: Int
   public var data4: Int
   public var data5: Int
   public var data6: Int
   public var data7: Int
   public var data8: Int
   public var data9: Int

   public init(
     _ data1: Int, _ data2: Int, _ data3: Int, _ data4: Int,
     _ data5: Int, _ data6: Int, _ data7: Int, _ data8: Int,
     _ data9: Int
   ) {
     self.data1 = data1
     self.data2 = data2
     self.data3 = data3
     self.data4 = data4
     self.data5 = data5
     self.data6 = data6
     self.data7 = data7
     self.data8 = data8
     self.data9 = data9
   }

   public var description: String {
     return "(\(data1), \(data2), \(data3), \(data4), \(data5), \(data6), \(data7), \(data8), \(data9))"
   }
 }

 public func == (lhs: Observation9Int, rhs: Observation9Int) -> Bool {
   return
     lhs.data1 == rhs.data1 &&
     lhs.data2 == rhs.data2 &&
     lhs.data3 == rhs.data3 &&
     lhs.data4 == rhs.data4 &&
     lhs.data5 == rhs.data5 &&
     lhs.data6 == rhs.data6 &&
     lhs.data7 == rhs.data7 &&
     lhs.data8 == rhs.data8 &&
     lhs.data9 == rhs.data9
 }

 /// A helper that is useful to implement
 /// `RaceTestWithPerTrialData.evaluateObservations()` in race tests.
 public func evaluateObservationsAllEqual<T : Equatable>(_ observations: [T])
   -> RaceTestObservationEvaluation {
   let first = observations.first!
   for x in observations {
     if x != first {
       return .failure
     }
   }
   return .pass
 }

 struct _RaceTestAggregatedEvaluations : CustomStringConvertible {
   var passCount: Int = 0
   var passInterestingCount = [String: Int]()
   var failureCount: Int = 0
   var failureInterestingCount = [String: Int]()

   init() {}

   mutating func addEvaluation(_ evaluation: RaceTestObservationEvaluation) {
     switch evaluation {
     case .pass:
       passCount += 1

     case .passInteresting(let s):
       if passInterestingCount[s] == nil {
         passInterestingCount[s] = 0
       }
       passInterestingCount[s] = passInterestingCount[s]! + 1

     case .failure:
       failureCount += 1

     case .failureInteresting(let s):
       if failureInterestingCount[s] == nil {
         failureInterestingCount[s] = 0
       }
       failureInterestingCount[s] = failureInterestingCount[s]! + 1
     }
   }

   var isFailed: Bool {
     return failureCount != 0 || !failureInterestingCount.isEmpty
   }

   var description: String {
     var result = ""
     result += "Pass: \(passCount) times\n"
     for desc in passInterestingCount.keys.sorted() {
       let count = passInterestingCount[desc]!
       result += "Pass \(desc): \(count) times\n"
     }
     result += "Failure: \(failureCount) times\n"
     for desc in failureInterestingCount.keys.sorted() {
       let count = failureInterestingCount[desc]!
       result += "Failure \(desc): \(count) times\n"
     }
     return result
   }
 }

 // FIXME: protect this class against false sharing.
 class _RaceTestWorkerState<RT : RaceTestWithPerTrialData> {
   // FIXME: protect every element of 'raceData' against false sharing.
   var raceData: [RT.RaceData] = []
   var raceDataShuffle: [Int] = []
   var observations: [RT.Observation] = []
 }

 class _RaceTestSharedState<RT : RaceTestWithPerTrialData> {
   var racingThreadCount: Int
   var stopNow = _stdlib_AtomicInt(0)

   var trialBarrier: _stdlib_Barrier
   var trialSpinBarrier = _stdlib_AtomicInt()

   var raceData: [RT.RaceData] = []
   var workerStates: [_RaceTestWorkerState<RT>] = []
   var aggregatedEvaluations: _RaceTestAggregatedEvaluations =
     _RaceTestAggregatedEvaluations()

   init(racingThreadCount: Int) {
     self.racingThreadCount = racingThreadCount
     self.trialBarrier = _stdlib_Barrier(threadCount: racingThreadCount + 1)

     self.workerStates.reserveCapacity(racingThreadCount)
     for _ in 0..<racingThreadCount {
       self.workerStates.append(_RaceTestWorkerState<RT>())
     }
   }
 }

 func _masterThreadStopWorkers<RT>( _ sharedState: _RaceTestSharedState<RT>) {
   // Workers are proceeding to the first barrier in _workerThreadOneTrial.
   sharedState.stopNow.store(1)
   // Allow workers to proceed past that first barrier. They will then see
   // stopNow==true and stop.
   sharedState.trialBarrier.wait()
 }

 func _masterThreadOneTrial<RT>(_ sharedState: _RaceTestSharedState<RT>) {
   let racingThreadCount = sharedState.racingThreadCount
   let raceDataCount = racingThreadCount * racingThreadCount
   let rt = RT()

   sharedState.raceData.removeAll(keepingCapacity: true)

   sharedState.raceData.append(contentsOf: (0..<raceDataCount).lazy.map { _ in
     rt.makeRaceData()
   })

   let identityShuffle = Array(0..<sharedState.raceData.count)
   sharedState.workerStates.removeAll(keepingCapacity: true)

   sharedState.workerStates.append(contentsOf: (0..<racingThreadCount).lazy.map {
     _ in
     let workerState = _RaceTestWorkerState<RT>()

     // Shuffle the data so that threads process it in different order.
     let shuffle = identityShuffle.shuffled()
     workerState.raceData = scatter(sharedState.raceData, shuffle)
     workerState.raceDataShuffle = shuffle

     workerState.observations = []
     workerState.observations.reserveCapacity(sharedState.raceData.count)

     return workerState
   })

   sharedState.trialSpinBarrier.store(0)
   sharedState.trialBarrier.wait()
   // Race happens.
   sharedState.trialBarrier.wait()

   // Collect and compare results.
   for i in 0..<racingThreadCount {
     let shuffle = sharedState.workerStates[i].raceDataShuffle
     sharedState.workerStates[i].raceData =
       gather(sharedState.workerStates[i].raceData, shuffle)
     sharedState.workerStates[i].observations =
       gather(sharedState.workerStates[i].observations, shuffle)
   }
   if true {
     // FIXME: why doesn't the bracket syntax work?
     // <rdar://problem/18305718> Array sugar syntax does not work when used
     // with associated types
     var observations: [RT.Observation] = []
     observations.reserveCapacity(racingThreadCount)
     for i in 0..<raceDataCount {
       for j in 0..<racingThreadCount {
         observations.append(sharedState.workerStates[j].observations[i])
       }

       let sink = { sharedState.aggregatedEvaluations.addEvaluation($0) }
       rt.evaluateObservations(observations, sink)
       observations.removeAll(keepingCapacity: true)
     }
   }
 }

 func _workerThreadOneTrial<RT>(
   _ tid: Int, _ sharedState: _RaceTestSharedState<RT>
 ) -> Bool {
   sharedState.trialBarrier.wait()
   if sharedState.stopNow.load() == 1 {
     return true
   }
   let racingThreadCount = sharedState.racingThreadCount
   let workerState = sharedState.workerStates[tid]
   let rt = RT()
   var threadLocalData = rt.makeThreadLocalData()
   do {
     let trialSpinBarrier = sharedState.trialSpinBarrier
     _ = trialSpinBarrier.fetchAndAdd(1)
     while trialSpinBarrier.load() < racingThreadCount {}
   }
   // Perform racy operations.
   // Warning: do not add any synchronization in this loop, including
   // any implicit reference counting of shared data.
   for raceData in workerState.raceData {
     workerState.observations.append(rt.thread1(raceData, &threadLocalData))
   }
   sharedState.trialBarrier.wait()
   return false
 }

 /// One-shot sleep in one thread, allowing interrupt by another.
 #if os(Windows)
 class _InterruptibleSleep {
   let event: HANDLE?
   var completed: Bool = false

   init() {
     self.event = CreateEventW(nil, TRUE, FALSE, nil)
     precondition(self.event != nil)
   }

   deinit {
     CloseHandle(self.event)
   }

   func sleep(durationInSeconds duration: Int) {
     guard completed == false else { return }

     let result: DWORD = WaitForSingleObject(event, DWORD(duration * 1000))
     precondition(result == WAIT_OBJECT_0)

     completed = true
   }

   func wake() {
     guard completed == false else { return }
     let result: BOOL = SetEvent(self.event)
     precondition(result == TRUE)
   }
 }
 #else
 class _InterruptibleSleep {
   let writeEnd: CInt
   let readEnd: CInt
   var completed = false

   init() {
     (readEnd: readEnd, writeEnd: writeEnd, _) = _stdlib_pipe()
   }

   deinit {
     close(readEnd)
     close(writeEnd)
   }

   /// Sleep for durationInSeconds or until another
   /// thread calls wake(), whichever comes first.
   func sleep(durationInSeconds duration: Int) {
     if completed {
       return
     }

     var timeout = timeval(tv_sec: duration, tv_usec: 0)

     var readFDs = _stdlib_fd_set()
     var writeFDs = _stdlib_fd_set()
     var errorFDs = _stdlib_fd_set()
     readFDs.set(readEnd)

     let ret = _stdlib_select(&readFDs, &writeFDs, &errorFDs, &timeout)
     precondition(ret >= 0)
     completed = true
   }

   /// Wake the thread in sleep().
   func wake() {
     if completed { return }

     let buffer: [UInt8] = [1]
     let ret = write(writeEnd, buffer, 1)
     precondition(ret >= 0)
   }
 }
 #endif

 #if os(Windows)
 typealias ThreadHandle = HANDLE
 #else
 typealias ThreadHandle = pthread_t
 #endif

 public func runRaceTest<RT : RaceTestWithPerTrialData>(
   _: RT.Type,
   trials: Int,
   timeoutInSeconds: Int? = nil,
   threads: Int? = nil
 ) {
   let racingThreadCount = threads ?? max(2, _stdlib_getHardwareConcurrency())
   let sharedState = _RaceTestSharedState<RT>(racingThreadCount: racingThreadCount)

   // Alarm thread sets timeoutReached.
   // Master thread sees timeoutReached and tells worker threads to stop.
   let timeoutReached = _stdlib_AtomicInt(0)
   let alarmTimer = _InterruptibleSleep()

   let masterThreadBody = {
     () -> Void in
     for t in 0..<trials {
       // Check for timeout.
       // _masterThreadStopWorkers must run BEFORE the last _masterThreadOneTrial
       // to make the thread coordination barriers work
       // but we do want to run at least one trial even if the timeout occurs.
       if timeoutReached.load() == 1 && t > 0 {
         _masterThreadStopWorkers(sharedState)
         break
       }

       autoreleasepool {
         _masterThreadOneTrial(sharedState)
       }
     }
   }

   let racingThreadBody = {
     (tid: Int) -> Void in
     for _ in 0..<trials {
       let stopNow = _workerThreadOneTrial(tid, sharedState)
       if stopNow { break }
     }
   }

   let alarmThreadBody = {
     () -> Void in
     guard let timeoutInSeconds = timeoutInSeconds
     else { return }

     alarmTimer.sleep(durationInSeconds: timeoutInSeconds)
     _ = timeoutReached.fetchAndAdd(1)
   }

   var testTids = [ThreadHandle]()
   var alarmTid: ThreadHandle

   // Create the master thread.
   do {
     let (ret, tid) = _stdlib_thread_create_block(masterThreadBody, ())
     expectEqual(0, ret)
     testTids.append(tid!)
   }

   // Create racing threads.
   for i in 0..<racingThreadCount {
     let (ret, tid) = _stdlib_thread_create_block(racingThreadBody, i)
     expectEqual(0, ret)
     testTids.append(tid!)
   }

   // Create the alarm thread that enforces the timeout.
   do {
     let (ret, tid) = _stdlib_thread_create_block(alarmThreadBody, ())
     expectEqual(0, ret)
     alarmTid = tid!
   }

   // Join all testing threads.
   for tid in testTids {
     let (ret, _) = _stdlib_thread_join(tid, Void.self)
     expectEqual(0, ret)
   }

   // Tell the alarm thread to stop if it hasn't already, then join it.
   do {
     alarmTimer.wake()
     let (ret, _) = _stdlib_thread_join(alarmTid, Void.self)
     expectEqual(0, ret)
   }

   let aggregatedEvaluations = sharedState.aggregatedEvaluations
   expectFalse(aggregatedEvaluations.isFailed)
   print(aggregatedEvaluations)
 }

 internal func _divideRoundUp(_ lhs: Int, _ rhs: Int) -> Int {
   return (lhs + rhs) / rhs
 }

 public func runRaceTest<RT : RaceTestWithPerTrialData>(
   _ test: RT.Type,
   operations: Int,
   timeoutInSeconds: Int? = nil,
   threads: Int? = nil
 ) {
   let racingThreadCount = threads ?? max(2, _stdlib_getHardwareConcurrency())

   // Each trial runs threads^2 operations.
   let operationsPerTrial = racingThreadCount * racingThreadCount
   let trials = _divideRoundUp(operations, operationsPerTrial)
   runRaceTest(test, trials: trials, timeoutInSeconds: timeoutInSeconds,
     threads: threads)
 }

 public func consumeCPU(units amountOfWork: Int) {
   for _ in 0..<amountOfWork {
     let scale = 16
     for _ in 0..<scale {
       _blackHole(42)
     }
   }
 }

 internal struct ClosureBasedRaceTest : RaceTestWithPerTrialData {
   static var thread: () -> Void = {}

   class RaceData {}
   typealias ThreadLocalData = Void
   typealias Observation = Void

   func makeRaceData() -> RaceData { return RaceData() }
   func makeThreadLocalData() -> Void { return Void() }

   func thread1(
     _ raceData: RaceData, _ threadLocalData: inout ThreadLocalData
   ) {
     ClosureBasedRaceTest.thread()
   }

   func evaluateObservations(
     _ observations: [Observation],
     _ sink: (RaceTestObservationEvaluation) -> Void
   ) {}
 }

 public func runRaceTest(
   trials: Int,
   timeoutInSeconds: Int? = nil,
   threads: Int? = nil,
   invoking body: @escaping () -> Void
 ) {
   ClosureBasedRaceTest.thread = body
   runRaceTest(ClosureBasedRaceTest.self, trials: trials,
     timeoutInSeconds: timeoutInSeconds, threads: threads)
 }

 public func runRaceTest(
   operations: Int,
   timeoutInSeconds: Int? = nil,
   threads: Int? = nil,
   invoking body: @escaping () -> Void
 ) {
   ClosureBasedRaceTest.thread = body
   runRaceTest(ClosureBasedRaceTest.self, operations: operations,
     timeoutInSeconds: timeoutInSeconds, threads: threads)
 }
	//===--- RaceTest.swift ---------------------------------------------------===//
	//
	// This source file is part of the Swift.org open source project
	//
	// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
	// Licensed under Apache License v2.0 with Runtime Library Exception
	//
	// See https://swift.org/LICENSE.txt for license information
	// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
	//
	//===----------------------------------------------------------------------===//
	///
	/// This file implements support for race tests.
	///
	/// Race test harness executes the given operation in multiple threads over a
	/// set of shared data, trying to ensure that executions overlap in time.
	///
	/// The name "race test" does not imply that the race actually happens in the
	/// harness or in the operation being tested. The harness contains all the
	/// necessary synchronization for its own data, and for publishing test data to
	/// threads. But if the operation under test is, in fact, racy, it should be
	/// easier to discover the bug in this environment.
	///
	/// Every execution of a race test is called a trial. During a single trial
	/// the operation under test is executed multiple times in each thread over
	/// different data items (`RaceData` instances). Different threads process
	/// data in different order. Choosing an appropriate balance between the
	/// number of threads and data items, the harness uses the birthday paradox to
	/// increase the probability of "collisions" between threads.
	///
	/// After performing the operation under test, the thread should observe the
	/// data in a test-dependent way to detect if presence of other concurrent
	/// actions disturbed the result. The observation should be as short as
	/// possible, and the results should be returned as `Observation`. Evaluation
	/// (cross-checking) of observations is deferred until the end of the trial.
	///
	//===----------------------------------------------------------------------===//

	import SwiftPrivate
	import SwiftPrivateLibcExtras
	import SwiftPrivateThreadExtras
	#if os(macOS) \|\| os(iOS)
	import Darwin
	#elseif os(Linux) \|\| os(FreeBSD) \|\| os(PS4) \|\| os(Android) \|\| os(Cygwin) \|\| os(Haiku)
	import Glibc
	#elseif os(Windows)
	import MSVCRT
	import WinSDK
	#endif

	#if _runtime(_ObjC)
	import ObjectiveC
	#else
	func autoreleasepool(invoking code: () -> Void) {
	// Native runtime does not have autorelease pools. Execute the code
	// directly.
	code()
	}
	#endif

	/// Race tests that need a fresh set of data for every trial should implement
	/// this protocol.
	///
	/// All racing threads execute the same operation, `thread1`.
	///
	/// Types conforming to this protocol should be structs. (The type
	/// should be a struct to reduce unnecessary reference counting during
	/// the test.) The types should be stateless.
	public protocol RaceTestWithPerTrialData {

	/// Input for threads.
	///
	/// This type should be a class. (The harness will not pass struct instances
	/// between threads correctly.)
	associatedtype RaceData : AnyObject

	/// Type of thread-local data.
	///
	/// Thread-local data is newly created for every trial.
	associatedtype ThreadLocalData

	/// Results of the observation made after performing an operation.
	associatedtype Observation

	init()

	/// Creates a fresh instance of `RaceData`.
	func makeRaceData() -> RaceData

	/// Creates a fresh instance of `ThreadLocalData`.
	func makeThreadLocalData() -> ThreadLocalData

	/// Performs the operation under test and makes an observation.
	func thread1(
	_ raceData: RaceData, _ threadLocalData: inout ThreadLocalData) -> Observation

	/// Evaluates the observations made by all threads for a particular instance
	/// of `RaceData`.
	func evaluateObservations(
	_ observations: [Observation],
	_ sink: (RaceTestObservationEvaluation) -> Void)
	}

	/// The result of evaluating observations.
	///
	/// Case payloads can carry test-specific data. Results will be grouped
	/// according to it.
	public enum RaceTestObservationEvaluation : Equatable, CustomStringConvertible {
	/// Normal 'pass'.
	case pass

	/// An unusual 'pass'.
	case passInteresting(String)

	/// A failure.
	case failure
	case failureInteresting(String)

	public var description: String {
	switch self {
	case .pass:
	return "Pass"

	case .passInteresting(let s):
	return "Pass(\(s))"

	case .failure:
	return "Failure"

	case .failureInteresting(let s):
	return "Failure(\(s))"
	}
	}
	}

	public func == (
	lhs: RaceTestObservationEvaluation, rhs: RaceTestObservationEvaluation
	) -> Bool {
	switch (lhs, rhs) {
	case (.pass, .pass),
	(.failure, .failure):
	return true

	case (.passInteresting(let s1), .passInteresting(let s2)):
	return s1 == s2

	default:
	return false
	}
	}

	/// An observation result that consists of one `UInt`.
	public struct Observation1UInt : Equatable, CustomStringConvertible {
	public var data1: UInt

	public init(_ data1: UInt) {
	self.data1 = data1
	}

	public var description: String {
	return "(\(data1))"
	}
	}

	public func == (lhs: Observation1UInt, rhs: Observation1UInt) -> Bool {
	return lhs.data1 == rhs.data1
	}

	/// An observation result that consists of four `UInt`s.
	public struct Observation4UInt : Equatable, CustomStringConvertible {
	public var data1: UInt
	public var data2: UInt
	public var data3: UInt
	public var data4: UInt

	public init(_ data1: UInt, _ data2: UInt, _ data3: UInt, _ data4: UInt) {
	self.data1 = data1
	self.data2 = data2
	self.data3 = data3
	self.data4 = data4
	}

	public var description: String {
	return "(\(data1), \(data2), \(data3), \(data4))"
	}
	}

	public func == (lhs: Observation4UInt, rhs: Observation4UInt) -> Bool {
	return
	lhs.data1 == rhs.data1 &&
	lhs.data2 == rhs.data2 &&
	lhs.data3 == rhs.data3 &&
	lhs.data4 == rhs.data4
	}

	/// An observation result that consists of three `Int`s.
	public struct Observation3Int : Equatable, CustomStringConvertible {
	public var data1: Int
	public var data2: Int
	public var data3: Int

	public init(_ data1: Int, _ data2: Int, _ data3: Int) {
	self.data1 = data1
	self.data2 = data2
	self.data3 = data3
	}

	public var description: String {
	return "(\(data1), \(data2), \(data3))"
	}
	}

	public func == (lhs: Observation3Int, rhs: Observation3Int) -> Bool {
	return
	lhs.data1 == rhs.data1 &&
	lhs.data2 == rhs.data2 &&
	lhs.data3 == rhs.data3
	}

	/// An observation result that consists of four `Int`s.
	public struct Observation4Int : Equatable, CustomStringConvertible {
	public var data1: Int
	public var data2: Int
	public var data3: Int
	public var data4: Int

	public init(_ data1: Int, _ data2: Int, _ data3: Int, _ data4: Int) {
	self.data1 = data1
	self.data2 = data2
	self.data3 = data3
	self.data4 = data4
	}

	public var description: String {
	return "(\(data1), \(data2), \(data3), \(data4))"
	}
	}

	public func == (lhs: Observation4Int, rhs: Observation4Int) -> Bool {
	return
	lhs.data1 == rhs.data1 &&
	lhs.data2 == rhs.data2 &&
	lhs.data3 == rhs.data3 &&
	lhs.data4 == rhs.data4
	}

	/// An observation result that consists of five `Int`s.
	public struct Observation5Int : Equatable, CustomStringConvertible {
	public var data1: Int
	public var data2: Int
	public var data3: Int
	public var data4: Int
	public var data5: Int

	public init(
	_ data1: Int, _ data2: Int, _ data3: Int, _ data4: Int, _ data5: Int
	) {
	self.data1 = data1
	self.data2 = data2
	self.data3 = data3
	self.data4 = data4
	self.data5 = data5
	}

	public var description: String {
	return "(\(data1), \(data2), \(data3), \(data4), \(data5))"
	}
	}

	public func == (lhs: Observation5Int, rhs: Observation5Int) -> Bool {
	return
	lhs.data1 == rhs.data1 &&
	lhs.data2 == rhs.data2 &&
	lhs.data3 == rhs.data3 &&
	lhs.data4 == rhs.data4 &&
	lhs.data5 == rhs.data5
	}

	/// An observation result that consists of nine `Int`s.
	public struct Observation9Int : Equatable, CustomStringConvertible {
	public var data1: Int
	public var data2: Int
	public var data3: Int
	public var data4: Int
	public var data5: Int
	public var data6: Int
	public var data7: Int
	public var data8: Int
	public var data9: Int

	public init(
	_ data1: Int, _ data2: Int, _ data3: Int, _ data4: Int,
	_ data5: Int, _ data6: Int, _ data7: Int, _ data8: Int,
	_ data9: Int
	) {
	self.data1 = data1
	self.data2 = data2
	self.data3 = data3
	self.data4 = data4
	self.data5 = data5
	self.data6 = data6
	self.data7 = data7
	self.data8 = data8
	self.data9 = data9
	}

	public var description: String {
	return "(\(data1), \(data2), \(data3), \(data4), \(data5), \(data6), \(data7), \(data8), \(data9))"
	}
	}

	public func == (lhs: Observation9Int, rhs: Observation9Int) -> Bool {
	return
	lhs.data1 == rhs.data1 &&
	lhs.data2 == rhs.data2 &&
	lhs.data3 == rhs.data3 &&
	lhs.data4 == rhs.data4 &&
	lhs.data5 == rhs.data5 &&
	lhs.data6 == rhs.data6 &&
	lhs.data7 == rhs.data7 &&
	lhs.data8 == rhs.data8 &&
	lhs.data9 == rhs.data9
	}

	/// A helper that is useful to implement
	/// `RaceTestWithPerTrialData.evaluateObservations()` in race tests.
	public func evaluateObservationsAllEqual<T : Equatable>(_ observations: [T])
	-> RaceTestObservationEvaluation {
	let first = observations.first!
	for x in observations {
	if x != first {
	return .failure
	}
	}
	return .pass
	}

	struct _RaceTestAggregatedEvaluations : CustomStringConvertible {
	var passCount: Int = 0
	var passInterestingCount = [String: Int]()
	var failureCount: Int = 0
	var failureInterestingCount = [String: Int]()

	init() {}

	mutating func addEvaluation(_ evaluation: RaceTestObservationEvaluation) {
	switch evaluation {
	case .pass:
	passCount += 1

	case .passInteresting(let s):
	if passInterestingCount[s] == nil {
	passInterestingCount[s] = 0
	}
	passInterestingCount[s] = passInterestingCount[s]! + 1

	case .failure:
	failureCount += 1

	case .failureInteresting(let s):
	if failureInterestingCount[s] == nil {
	failureInterestingCount[s] = 0
	}
	failureInterestingCount[s] = failureInterestingCount[s]! + 1
	}
	}

	var isFailed: Bool {
	return failureCount != 0 \|\| !failureInterestingCount.isEmpty
	}

	var description: String {
	var result = ""
	result += "Pass: \(passCount) times\n"
	for desc in passInterestingCount.keys.sorted() {
	let count = passInterestingCount[desc]!
	result += "Pass \(desc): \(count) times\n"
	}
	result += "Failure: \(failureCount) times\n"
	for desc in failureInterestingCount.keys.sorted() {
	let count = failureInterestingCount[desc]!
	result += "Failure \(desc): \(count) times\n"
	}
	return result
	}
	}

	// FIXME: protect this class against false sharing.
	class _RaceTestWorkerState<RT : RaceTestWithPerTrialData> {
	// FIXME: protect every element of 'raceData' against false sharing.
	var raceData: [RT.RaceData] = []
	var raceDataShuffle: [Int] = []
	var observations: [RT.Observation] = []
	}

	class _RaceTestSharedState<RT : RaceTestWithPerTrialData> {
	var racingThreadCount: Int
	var stopNow = _stdlib_AtomicInt(0)

	var trialBarrier: _stdlib_Barrier
	var trialSpinBarrier = _stdlib_AtomicInt()

	var raceData: [RT.RaceData] = []
	var workerStates: [_RaceTestWorkerState<RT>] = []
	var aggregatedEvaluations: _RaceTestAggregatedEvaluations =
	_RaceTestAggregatedEvaluations()

	init(racingThreadCount: Int) {
	self.racingThreadCount = racingThreadCount
	self.trialBarrier = _stdlib_Barrier(threadCount: racingThreadCount + 1)

	self.workerStates.reserveCapacity(racingThreadCount)
	for _ in 0..<racingThreadCount {
	self.workerStates.append(_RaceTestWorkerState<RT>())
	}
	}
	}

	func _masterThreadStopWorkers<RT>( _ sharedState: _RaceTestSharedState<RT>) {
	// Workers are proceeding to the first barrier in _workerThreadOneTrial.
	sharedState.stopNow.store(1)
	// Allow workers to proceed past that first barrier. They will then see
	// stopNow==true and stop.
	sharedState.trialBarrier.wait()
	}

	func _masterThreadOneTrial<RT>(_ sharedState: _RaceTestSharedState<RT>) {
	let racingThreadCount = sharedState.racingThreadCount
	let raceDataCount = racingThreadCount * racingThreadCount
	let rt = RT()

	sharedState.raceData.removeAll(keepingCapacity: true)

	sharedState.raceData.append(contentsOf: (0..<raceDataCount).lazy.map { _ in
	rt.makeRaceData()
	})

	let identityShuffle = Array(0..<sharedState.raceData.count)
	sharedState.workerStates.removeAll(keepingCapacity: true)

	sharedState.workerStates.append(contentsOf: (0..<racingThreadCount).lazy.map {
	_ in
	let workerState = _RaceTestWorkerState<RT>()

	// Shuffle the data so that threads process it in different order.
	let shuffle = identityShuffle.shuffled()
	workerState.raceData = scatter(sharedState.raceData, shuffle)
	workerState.raceDataShuffle = shuffle

	workerState.observations = []
	workerState.observations.reserveCapacity(sharedState.raceData.count)

	return workerState
	})

	sharedState.trialSpinBarrier.store(0)
	sharedState.trialBarrier.wait()
	// Race happens.
	sharedState.trialBarrier.wait()

	// Collect and compare results.
	for i in 0..<racingThreadCount {
	let shuffle = sharedState.workerStates[i].raceDataShuffle
	sharedState.workerStates[i].raceData =
	gather(sharedState.workerStates[i].raceData, shuffle)
	sharedState.workerStates[i].observations =
	gather(sharedState.workerStates[i].observations, shuffle)
	}
	if true {
	// FIXME: why doesn't the bracket syntax work?
	// <rdar://problem/18305718> Array sugar syntax does not work when used
	// with associated types
	var observations: [RT.Observation] = []
	observations.reserveCapacity(racingThreadCount)
	for i in 0..<raceDataCount {
	for j in 0..<racingThreadCount {
	observations.append(sharedState.workerStates[j].observations[i])
	}

	let sink = { sharedState.aggregatedEvaluations.addEvaluation($0) }
	rt.evaluateObservations(observations, sink)
	observations.removeAll(keepingCapacity: true)
	}
	}
	}

	func _workerThreadOneTrial<RT>(
	_ tid: Int, _ sharedState: _RaceTestSharedState<RT>
	) -> Bool {
	sharedState.trialBarrier.wait()
	if sharedState.stopNow.load() == 1 {
	return true
	}
	let racingThreadCount = sharedState.racingThreadCount
	let workerState = sharedState.workerStates[tid]
	let rt = RT()
	var threadLocalData = rt.makeThreadLocalData()
	do {
	let trialSpinBarrier = sharedState.trialSpinBarrier
	_ = trialSpinBarrier.fetchAndAdd(1)
	while trialSpinBarrier.load() < racingThreadCount {}
	}
	// Perform racy operations.
	// Warning: do not add any synchronization in this loop, including
	// any implicit reference counting of shared data.
	for raceData in workerState.raceData {
	workerState.observations.append(rt.thread1(raceData, &threadLocalData))
	}
	sharedState.trialBarrier.wait()
	return false
	}

	/// One-shot sleep in one thread, allowing interrupt by another.
	#if os(Windows)
	class _InterruptibleSleep {
	let event: HANDLE?
	var completed: Bool = false

	init() {
	self.event = CreateEventW(nil, TRUE, FALSE, nil)
	precondition(self.event != nil)
	}

	deinit {
	CloseHandle(self.event)
	}

	func sleep(durationInSeconds duration: Int) {
	guard completed == false else { return }

	let result: DWORD = WaitForSingleObject(event, DWORD(duration * 1000))
	precondition(result == WAIT_OBJECT_0)

	completed = true
	}

	func wake() {
	guard completed == false else { return }
	let result: BOOL = SetEvent(self.event)
	precondition(result == TRUE)
	}
	}
	#else
	class _InterruptibleSleep {
	let writeEnd: CInt
	let readEnd: CInt
	var completed = false

	init() {
	(readEnd: readEnd, writeEnd: writeEnd, _) = _stdlib_pipe()
	}

	deinit {
	close(readEnd)
	close(writeEnd)
	}

	/// Sleep for durationInSeconds or until another
	/// thread calls wake(), whichever comes first.
	func sleep(durationInSeconds duration: Int) {
	if completed {
	return
	}

	var timeout = timeval(tv_sec: duration, tv_usec: 0)

	var readFDs = _stdlib_fd_set()
	var writeFDs = _stdlib_fd_set()
	var errorFDs = _stdlib_fd_set()
	readFDs.set(readEnd)

	let ret = _stdlib_select(&readFDs, &writeFDs, &errorFDs, &timeout)
	precondition(ret >= 0)
	completed = true
	}

	/// Wake the thread in sleep().
	func wake() {
	if completed { return }

	let buffer: [UInt8] = [1]
	let ret = write(writeEnd, buffer, 1)
	precondition(ret >= 0)
	}
	}
	#endif

	#if os(Windows)
	typealias ThreadHandle = HANDLE
	#else
	typealias ThreadHandle = pthread_t
	#endif

	public func runRaceTest<RT : RaceTestWithPerTrialData>(
	_: RT.Type,
	trials: Int,
	timeoutInSeconds: Int? = nil,
	threads: Int? = nil
	) {
	let racingThreadCount = threads ?? max(2, _stdlib_getHardwareConcurrency())
	let sharedState = _RaceTestSharedState<RT>(racingThreadCount: racingThreadCount)

	// Alarm thread sets timeoutReached.
	// Master thread sees timeoutReached and tells worker threads to stop.
	let timeoutReached = _stdlib_AtomicInt(0)
	let alarmTimer = _InterruptibleSleep()

	let masterThreadBody = {
	() -> Void in
	for t in 0..<trials {
	// Check for timeout.
	// _masterThreadStopWorkers must run BEFORE the last _masterThreadOneTrial
	// to make the thread coordination barriers work
	// but we do want to run at least one trial even if the timeout occurs.
	if timeoutReached.load() == 1 && t > 0 {
	_masterThreadStopWorkers(sharedState)
	break
	}

	autoreleasepool {
	_masterThreadOneTrial(sharedState)
	}
	}
	}

	let racingThreadBody = {
	(tid: Int) -> Void in
	for _ in 0..<trials {
	let stopNow = _workerThreadOneTrial(tid, sharedState)
	if stopNow { break }
	}
	}

	let alarmThreadBody = {
	() -> Void in
	guard let timeoutInSeconds = timeoutInSeconds
	else { return }

	alarmTimer.sleep(durationInSeconds: timeoutInSeconds)
	_ = timeoutReached.fetchAndAdd(1)
	}

	var testTids = [ThreadHandle]()
	var alarmTid: ThreadHandle

	// Create the master thread.
	do {
	let (ret, tid) = _stdlib_thread_create_block(masterThreadBody, ())
	expectEqual(0, ret)
	testTids.append(tid!)
	}

	// Create racing threads.
	for i in 0..<racingThreadCount {
	let (ret, tid) = _stdlib_thread_create_block(racingThreadBody, i)
	expectEqual(0, ret)
	testTids.append(tid!)
	}

	// Create the alarm thread that enforces the timeout.
	do {
	let (ret, tid) = _stdlib_thread_create_block(alarmThreadBody, ())
	expectEqual(0, ret)
	alarmTid = tid!
	}

	// Join all testing threads.
	for tid in testTids {
	let (ret, _) = _stdlib_thread_join(tid, Void.self)
	expectEqual(0, ret)
	}

	// Tell the alarm thread to stop if it hasn't already, then join it.
	do {
	alarmTimer.wake()
	let (ret, _) = _stdlib_thread_join(alarmTid, Void.self)
	expectEqual(0, ret)
	}

	let aggregatedEvaluations = sharedState.aggregatedEvaluations
	expectFalse(aggregatedEvaluations.isFailed)
	print(aggregatedEvaluations)
	}

	internal func _divideRoundUp(_ lhs: Int, _ rhs: Int) -> Int {
	return (lhs + rhs) / rhs
	}

	public func runRaceTest<RT : RaceTestWithPerTrialData>(
	_ test: RT.Type,
	operations: Int,
	timeoutInSeconds: Int? = nil,
	threads: Int? = nil
	) {
	let racingThreadCount = threads ?? max(2, _stdlib_getHardwareConcurrency())

	// Each trial runs threads^2 operations.
	let operationsPerTrial = racingThreadCount * racingThreadCount
	let trials = _divideRoundUp(operations, operationsPerTrial)
	runRaceTest(test, trials: trials, timeoutInSeconds: timeoutInSeconds,
	threads: threads)
	}

	public func consumeCPU(units amountOfWork: Int) {
	for _ in 0..<amountOfWork {
	let scale = 16
	for _ in 0..<scale {
	_blackHole(42)
	}
	}
	}

	internal struct ClosureBasedRaceTest : RaceTestWithPerTrialData {
	static var thread: () -> Void = {}

	class RaceData {}
	typealias ThreadLocalData = Void
	typealias Observation = Void

	func makeRaceData() -> RaceData { return RaceData() }
	func makeThreadLocalData() -> Void { return Void() }

	func thread1(
	_ raceData: RaceData, _ threadLocalData: inout ThreadLocalData
	) {
	ClosureBasedRaceTest.thread()
	}

	func evaluateObservations(
	_ observations: [Observation],
	_ sink: (RaceTestObservationEvaluation) -> Void
	) {}
	}

	public func runRaceTest(
	trials: Int,
	timeoutInSeconds: Int? = nil,
	threads: Int? = nil,
	invoking body: @escaping () -> Void
	) {
	ClosureBasedRaceTest.thread = body
	runRaceTest(ClosureBasedRaceTest.self, trials: trials,
	timeoutInSeconds: timeoutInSeconds, threads: threads)
	}

	public func runRaceTest(
	operations: Int,
	timeoutInSeconds: Int? = nil,
	threads: Int? = nil,
	invoking body: @escaping () -> Void
	) {
	ClosureBasedRaceTest.thread = body
	runRaceTest(ClosureBasedRaceTest.self, operations: operations,
	timeoutInSeconds: timeoutInSeconds, threads: threads)
	}