// Copyright (c) 2006-2009 Nokia Corporation and/or its subsidiary(-ies).

 // All rights reserved.

 // This component and the accompanying materials are made available

 // under the terms of the License "Eclipse Public License v1.0"

 // which accompanies this distribution, and is available

 // at the URL "http://www.eclipse.org/legal/epl-v10.html".

 //

 // Initial Contributors:

 // Nokia Corporation - initial contribution.

 //

 // Contributors:

 //

 // Description:

 // e32test\nkernsa\rwspinlock.cpp

 //---------------------------------------------------------------------------------------------------------------------

 //! @SYMTestCaseID				KBASE-rwspinlock-2442

 //! @SYMTestType				UT

 //! @SYMTestCaseDesc			Verifying the nkern SpinLock

 //! @SYMPREQ					PREQ2094

 //! @SYMTestPriority			High

 //! @SYMTestActions				

 //! 	1. 	RWParallelTest: run a number of reader and writer threads accessing a

 //! 		common data block. Each writer completely rewrites the block over and

 //! 		over, and the readers verify that the data is consistent.

 //! 	2. 	RWOrderingTest: run a number of reader and writer threads which spin-

 //! 		wait while holding the spinlock. Each works out the maximum time it

 //!         had to wait to acquire the spinlock.

 //! 		

 //! 

 //! @SYMTestExpectedResults

 //! 	1.	Properties checked:

 //! 		1) readers never see a partial write transaction

 //! 		2) the number of writers active is never greater than 1

 //! 		3) the number of readers active while a writer is active is 0

 //! 		4) more than one reader ran concurrently

 //! 	

 //! 	2. Properties checked:

 //! 		5) Threads acquire the spinlock in the order which they asked for it

 //!     	   i.e. neither reader nor writer priority but FIFO

 //---------------------------------------------------------------------------------------------------------------------

 #include <nktest/nkutils.h>

 #ifdef __SMP__

 // cheap and cheerful, no side effects please

 #define MIN(a, b) ((a)<(b)?(a):(b))

 // The spinlock, used throughout

 TRWSpinLock RW(TSpinLock::EOrderNone);

 ///////////////////////////////////////////////

 // First test: RWParallelTest

 //

 // Number of words in the data block

 #define BLOCK_SIZE 1024

 // Number of write transactions to execute in total (across all writers)

 #define WRITE_GOAL 100000

 // The data block, the first entry is used as the seed value and is just

 // incremented by one each time.

 TUint32 Array[BLOCK_SIZE];

 // The number of readers currently holding the lock

 TUint32 Readers = 0;

 // The number of writers currently holding the lock

 TUint32 Writers = 0;

 // The maximum number of readers that were seen holding the lock at once

 TUint32 HighReaders = 0;

 void RWParallelReadThread(TAny*)

 	{

 	// high_r is the maximum number of readers seen by this particular reader

 	TUint32 c, r, high_r = 0;

 	TBool failed;

 	do

 		{

 		failed = EFalse;

 		// Take read lock and update reader count

 		RW.LockIrqR();

 		__e32_atomic_add_ord32(&Readers, 1);

 		// Check property 1

 		c = Array[0];

 		if (!verify_block_no_trace(Array, BLOCK_SIZE))

 			failed = ETrue;

 		// Update reader count and release read lock

 		r = __e32_atomic_add_ord32(&Readers, (TUint32)-1);

 		RW.UnlockIrqR();

 		TEST_RESULT(!failed, "Array data inconsistent");

 		// Update local high reader count

 		if (r > high_r)

 			high_r = r;

 		}

 	while (c < WRITE_GOAL);

 	// Update HighReaders if our high reader count is greater

 	TUint32 global_high = __e32_atomic_load_acq32(&HighReaders);

 	do

 		{

 		if (global_high >= high_r)

 			break;

 		}

 	while (!__e32_atomic_cas_ord32(&HighReaders, &global_high, high_r));

 	}

 void RWParallelWriteThread(TAny*)

 	{

 	TUint32 c, r, w;

 	do

 		{

 		// Take write lock and update writer count

 		RW.LockIrqW();

 		w = __e32_atomic_add_ord32(&Writers, 1);

 		// Get reader count

 		r = __e32_atomic_load_acq32(&Readers);

 		// Increment seed and recalculate array data

 		c = ++Array[0];

 		setup_block(Array, BLOCK_SIZE);

 		// Update writer count and release write lock

 		__e32_atomic_add_ord32(&Writers, (TUint32)-1);

 		RW.UnlockIrqW();

 		// Check properties 2 and 3

 		TEST_RESULT(w == 0, "Multiple writers active");

 		TEST_RESULT(r == 0, "Reader active while writing");

 		}

 	while (c < WRITE_GOAL);

 	}

 void RWParallelTest()

 	{

 	TEST_PRINT("Testing read consistency during parallel accesses");

 	NFastSemaphore exitSem(0);

 	// Set up the block for the initial seed of 0

 	setup_block(Array, BLOCK_SIZE);

 	// Spawn three readers and a writer for each processor, all equal priority

 	TInt cpu;

 	TInt threads = 0;

 	for_each_cpu(cpu)

 		{

 		CreateThreadSignalOnExit("RWParallelTestR1", &RWParallelReadThread, 10, NULL, 0, KSmallTimeslice, &exitSem, cpu);

 		CreateThreadSignalOnExit("RWParallelTestR2", &RWParallelReadThread, 10, NULL, 0, KSmallTimeslice, &exitSem, cpu);

 		CreateThreadSignalOnExit("RWParallelTestR3", &RWParallelReadThread, 10, NULL, 0, KSmallTimeslice, &exitSem, cpu);

 		CreateThreadSignalOnExit("RWParallelTestW", &RWParallelWriteThread, 10, NULL, 0, KSmallTimeslice, &exitSem, cpu);

 		threads += 4;

 		}

 	// Wait for all threads to terminate

 	while (threads--)

 		NKern::FSWait(&exitSem);

 	// Check property 4

 	TUint r = __e32_atomic_load_acq32(&HighReaders);

 	TEST_RESULT(r > 1, "Didn't see concurrent reads");

 	TEST_PRINT1("Done, max concurrent readers was %d", r);

 	}

 ///////////////////////////////////////////////

 // Second test: RWOrderingTest

 //

 // Number of times for each thread to try the lock

 #define ORDERING_REPEATS 5000

 // Time base for spinning

 #define SPIN_BASE 100

 // Time for read threads to spin (prime)

 #define READ_SPIN 7

 // Time for write threads to spin (different prime)

 #define WRITE_SPIN 11

 // Maximum write-thread wait seen

 TUint32 MaxWriteWait;

 // Maximum read-thread wait seen

 TUint32 MaxReadWait;

 void RWOrderingThread(TAny* aWrite)

 	{

 	NThreadBase* us = NKern::CurrentThread();

 	TUint32 seed[2] = {(TUint32)us, 0};

 	TUint32 c, maxdelay = 0;

 	for (c = 0; c < ORDERING_REPEATS; ++c)

 		{

 		// Disable interrupts to stop preemption disrupting timing

 		TInt irq = NKern::DisableAllInterrupts();

 		// Time taking lock

 		TUint32 before = norm_fast_counter();

 		if (aWrite)

 			RW.LockOnlyW();

 		else

 			RW.LockOnlyR();

 		TUint32 after = norm_fast_counter();

 		TUint32 delay = after - before;

 		if (delay > maxdelay)

 			maxdelay = delay;

 		// Spin for a fixed amount of time

 		nfcfspin(SPIN_BASE * (aWrite ? WRITE_SPIN : READ_SPIN));

 		// Release lock

 		if (aWrite)

 			RW.UnlockOnlyW();

 		else

 			RW.UnlockOnlyR();

 		// Reenable interrupts

 		NKern::RestoreInterrupts(irq);

 		// Sleep for a tick ~50% of the time to shuffle ordering

 		if (random(seed) & 0x4000)

 			NKern::Sleep(1);

 		}

 	// Update Max{Read,Write}Wait if ours is higher

 	TUint32 global_high = __e32_atomic_load_acq32(aWrite ? &MaxWriteWait : &MaxReadWait);

 	do

 		{

 		if (global_high >= maxdelay)

 			break;

 		}

 	while (!__e32_atomic_cas_ord32(aWrite ? &MaxWriteWait : &MaxReadWait, &global_high, maxdelay));

 	if (aWrite)

 		TEST_PRINT1("Write max delay: %d", maxdelay);

 	else

 		TEST_PRINT1("Read max delay: %d", maxdelay);

 	}

 void RWOrderingTest()

 	{

 	TEST_PRINT("Testing lock acquisition ordering");

 	NFastSemaphore exitSem(0);

 	TInt cpus = NKern::NumberOfCpus();

 	TInt writers, cpu;

 	for (writers = 0; writers <= cpus; ++writers)

 		{

 		TInt readers = cpus - writers;

 		// reset maximums

 		__e32_atomic_store_rel32(&MaxWriteWait, 0);

 		__e32_atomic_store_rel32(&MaxReadWait, 0);

 		// start one thread on each cpu, according to readers/writers

 		for (cpu = 0; cpu < writers; ++cpu)

 			CreateThreadSignalOnExit("RWOrderingTestW", &RWOrderingThread, 10, (TAny*)ETrue, 0, KSmallTimeslice, &exitSem, cpu);

 		for (       ; cpu < cpus; ++cpu)

 			CreateThreadSignalOnExit("RWOrderingTestR", &RWOrderingThread, 10, (TAny*)EFalse, 0, KSmallTimeslice, &exitSem, cpu);

 		// Wait for all threads to terminate

 		while (cpu--)

 			NKern::FSWait(&exitSem);

 		// Get, round, and print maximum delays

 		TUint32 w = __e32_atomic_load_acq32(&MaxWriteWait);

 		TUint32 r = __e32_atomic_load_acq32(&MaxReadWait);

 		w += (SPIN_BASE/2) - 1;

 		r += (SPIN_BASE/2) - 1;

 		w /= SPIN_BASE;

 		r /= SPIN_BASE;

 		TEST_PRINT4("%d writers, %d readers, max delay: write %d read %d", writers, readers, w, r);

 		// Work out expected delays

 		// For writers, we might have every other writer ahead of us, with the readers interleaved

 		TUint32 we = ((writers-1) * WRITE_SPIN) + (MIN(readers  , writers) * READ_SPIN);

 		// For readers, we might have every writer ahead of us, with the other readers interleaved

 		TUint32 re = ((writers  ) * WRITE_SPIN) + (MIN(readers-1, writers) * READ_SPIN);

 		// Compare

 		if (writers)

 			{

 			TEST_PRINT1("Expected write %d", we);

 			TEST_RESULT(w==we, "Write delay not expected time");

 			}

 		if (readers)

 			{

 			TEST_PRINT1("Expected read %d", re);

 			TEST_RESULT(r==re, "Read delay not expected time");

 			}

 		}

 	TEST_PRINT("Done");

 	}

 /////////////////////

 // Run all tests

 void TestRWSpinLock()

 	{

 	TEST_PRINT("Testing R/W Spinlocks...");

 	RWParallelTest();

 	RWOrderingTest();

 	}

 #else

 void TestRWSpinLock()

 	{

 	TEST_PRINT("Skipping R/W Spinlock tests on uniproc");

 	}

 #endif