571 lines
11 KiB
C++
571 lines
11 KiB
C++
//========== Copyright © 2007, Valve Corporation, All rights reserved. ========
|
|
//
|
|
// Purpose:
|
|
//
|
|
//=============================================================================
|
|
|
|
#include "pch_tier0.h"
|
|
#include "tier0/tslist.h"
|
|
#if defined( _X360 )
|
|
#include "xbox/xbox_win32stubs.h"
|
|
#endif
|
|
|
|
#include <stdlib.h>
|
|
#include "tier0/threadtools.h" // for rand()
|
|
// NOTE: This has to be the last file included!
|
|
#include "tier0/memdbgon.h"
|
|
|
|
extern ThreadHandle_t * CreateTestThreads( ThreadFunc_t fnThread, int numThreads, int nProcessorsToDistribute );
|
|
extern void JoinTestThreads( ThreadHandle_t *pHandles );
|
|
|
|
namespace TSListTests
|
|
{
|
|
int NUM_TEST = 10000;
|
|
int NUM_THREADS;
|
|
int MAX_THREADS = 8;
|
|
int NUM_PROCESSORS = 1;
|
|
|
|
CInterlockedInt g_nTested;
|
|
CInterlockedInt g_nThreads;
|
|
CInterlockedInt g_nPushThreads;
|
|
CInterlockedInt g_nPopThreads;
|
|
CInterlockedInt g_nPushes;
|
|
CInterlockedInt g_nPops;
|
|
CTSQueue<int, true> g_TestQueue;
|
|
CTSList<int> g_TestList;
|
|
volatile bool g_bStart;
|
|
|
|
int *g_pTestBuckets;
|
|
|
|
CTSListBase g_Test;
|
|
TSLNodeBase_t **g_nodes;
|
|
int idx = 0;
|
|
|
|
const char *g_pListType;
|
|
|
|
class CTestOps
|
|
{
|
|
public:
|
|
virtual void Push( int item ) = 0;
|
|
virtual bool Pop( int *pResult ) = 0;
|
|
virtual bool Validate() { return true; }
|
|
virtual bool IsEmpty() = 0;
|
|
};
|
|
|
|
bool g_bUseMutex = false;
|
|
CThreadConditionalMutex< CThreadFastMutex, &g_bUseMutex > g_TestLock;
|
|
|
|
class CQueueOps : public CTestOps
|
|
{
|
|
void Push( int item )
|
|
{
|
|
g_TestLock.Lock();
|
|
g_TestQueue.PushItem( item );
|
|
g_TestLock.Unlock();
|
|
g_nPushes++;
|
|
}
|
|
bool Pop( int *pResult )
|
|
{
|
|
g_TestLock.Lock();
|
|
if ( g_TestQueue.PopItem( pResult ) )
|
|
{
|
|
g_TestLock.Unlock();
|
|
g_nPops++;
|
|
return true;
|
|
}
|
|
g_TestLock.Unlock();
|
|
return false;
|
|
}
|
|
bool Validate()
|
|
{
|
|
return true; //g_TestQueue.Validate();
|
|
}
|
|
bool IsEmpty()
|
|
{
|
|
return ( g_TestQueue.Count() == 0 );
|
|
}
|
|
} g_QueueOps;
|
|
|
|
class CListOps : public CTestOps
|
|
{
|
|
void Push( int item )
|
|
{
|
|
g_TestLock.Lock();
|
|
g_TestList.PushItem( item );
|
|
g_nPushes++;
|
|
}
|
|
bool Pop( int *pResult )
|
|
{
|
|
g_TestLock.Lock();
|
|
if ( g_TestList.PopItem( pResult ) )
|
|
{
|
|
g_TestLock.Unlock();
|
|
g_nPops++;
|
|
return true;
|
|
}
|
|
g_TestLock.Unlock();
|
|
return false;
|
|
}
|
|
bool Validate()
|
|
{
|
|
return true;
|
|
}
|
|
bool IsEmpty()
|
|
{
|
|
return ( g_TestList.Count() == 0 );
|
|
}
|
|
} g_ListOps;
|
|
|
|
CTestOps *g_pTestOps;
|
|
|
|
void ClearBuckets()
|
|
{
|
|
memset( g_pTestBuckets, 0, sizeof(int) * NUM_TEST );
|
|
}
|
|
|
|
void IncBucket( int i )
|
|
{
|
|
if ( i < NUM_TEST ) // tests can slop over a bit
|
|
{
|
|
ThreadInterlockedIncrement( &g_pTestBuckets[i] );
|
|
}
|
|
}
|
|
|
|
void DecBucket( int i )
|
|
{
|
|
if ( i < NUM_TEST ) // tests can slop over a bit
|
|
{
|
|
ThreadInterlockedDecrement( &g_pTestBuckets[i] );
|
|
}
|
|
}
|
|
|
|
void ValidateBuckets()
|
|
{
|
|
for ( int i = 0; i < NUM_TEST; i++ )
|
|
{
|
|
if ( g_pTestBuckets[i] != 0 )
|
|
{
|
|
Msg( "Test bucket %d has an invalid value %d\n", i, g_pTestBuckets[i] );
|
|
DebuggerBreakIfDebugging();
|
|
return;
|
|
}
|
|
}
|
|
}
|
|
|
|
uintp PopThreadFunc( void *)
|
|
{
|
|
//ThreadSetDebugName( "PopThread" );
|
|
g_nPopThreads++;
|
|
g_nThreads++;
|
|
while ( !g_bStart )
|
|
{
|
|
ThreadSleep( 1 );
|
|
}
|
|
int ignored;
|
|
for (;;)
|
|
{
|
|
if ( !g_pTestOps->Pop( &ignored ) )
|
|
{
|
|
ThreadPause();
|
|
ThreadSleep(0);
|
|
if ( g_nPushThreads == 0 )
|
|
{
|
|
// Pop the rest
|
|
while ( g_pTestOps->Pop( &ignored ) )
|
|
{
|
|
ThreadPause();
|
|
ThreadSleep( 0 );
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
g_nThreads--;
|
|
g_nPopThreads--;
|
|
return 0;
|
|
}
|
|
|
|
uintp PushThreadFunc( void * )
|
|
{
|
|
//ThreadSetDebugName( "PushThread" );
|
|
g_nPushThreads++;
|
|
g_nThreads++;
|
|
while ( !g_bStart )
|
|
{
|
|
ThreadPause();
|
|
ThreadSleep( 0 );
|
|
}
|
|
|
|
while ( ++g_nTested <= NUM_TEST )
|
|
{
|
|
g_pTestOps->Push( g_nTested );
|
|
}
|
|
g_nThreads--;
|
|
g_nPushThreads--;
|
|
return 0;
|
|
}
|
|
|
|
void TestStart()
|
|
{
|
|
g_nTested = 0;
|
|
g_nThreads = 0;
|
|
g_nPushThreads = 0;
|
|
g_nPopThreads = 0;
|
|
g_bStart = false;
|
|
g_nPops = g_nPushes = 0;
|
|
ClearBuckets();
|
|
}
|
|
|
|
void TestWait()
|
|
{
|
|
while ( g_nThreads < NUM_THREADS )
|
|
{
|
|
ThreadSleep( 0 );
|
|
}
|
|
g_bStart = true;
|
|
while ( g_nThreads > 0 )
|
|
{
|
|
ThreadSleep( 0 );
|
|
}
|
|
}
|
|
|
|
void TestEnd( bool bExpectEmpty = true )
|
|
{
|
|
ValidateBuckets();
|
|
|
|
if ( g_nPops != g_nPushes )
|
|
{
|
|
Msg( "FAIL: Not all items popped\n" );
|
|
return;
|
|
}
|
|
|
|
if ( g_pTestOps->Validate() )
|
|
{
|
|
if ( !bExpectEmpty || g_pTestOps->IsEmpty() )
|
|
{
|
|
Msg("pass\n");
|
|
}
|
|
else
|
|
{
|
|
Msg("FAIL: !IsEmpty()\n");
|
|
}
|
|
}
|
|
else
|
|
{
|
|
Msg("FAIL: !Validate()\n");
|
|
}
|
|
}
|
|
|
|
|
|
//--------------------------------------------------
|
|
//
|
|
// Shared Tests for CTSQueue and CTSList
|
|
//
|
|
//--------------------------------------------------
|
|
void PushPopTest()
|
|
{
|
|
Msg( "%s test: single thread push/pop, in order... ", g_pListType );
|
|
ClearBuckets();
|
|
g_nTested = 0;
|
|
int value;
|
|
while ( g_nTested < NUM_TEST )
|
|
{
|
|
value = g_nTested++;
|
|
g_pTestOps->Push( value );
|
|
IncBucket( value );
|
|
}
|
|
|
|
g_pTestOps->Validate();
|
|
|
|
while ( g_pTestOps->Pop( &value ) )
|
|
{
|
|
DecBucket( value );
|
|
}
|
|
TestEnd();
|
|
}
|
|
|
|
void PushPopInterleavedTestGuts()
|
|
{
|
|
int value;
|
|
for (;;)
|
|
{
|
|
bool bPush = ( rand() % 2 == 0 );
|
|
if ( bPush && ( value = g_nTested++ ) < NUM_TEST )
|
|
{
|
|
g_pTestOps->Push( value );
|
|
IncBucket( value );
|
|
}
|
|
else if ( g_pTestOps->Pop( &value ) )
|
|
{
|
|
DecBucket( value );
|
|
}
|
|
else
|
|
{
|
|
if ( g_nTested >= NUM_TEST )
|
|
{
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void PushPopInterleavedTest()
|
|
{
|
|
Msg( "%s test: single thread push/pop, interleaved... ", g_pListType );
|
|
srand( Plat_MSTime() );
|
|
g_nTested = 0;
|
|
ClearBuckets();
|
|
PushPopInterleavedTestGuts();
|
|
TestEnd();
|
|
}
|
|
|
|
uintp PushPopInterleavedTestThreadFunc( void * )
|
|
{
|
|
ThreadSetDebugName( "PushPopThread" );
|
|
g_nThreads++;
|
|
while ( !g_bStart )
|
|
{
|
|
ThreadSleep( 0 );
|
|
}
|
|
PushPopInterleavedTestGuts();
|
|
g_nThreads--;
|
|
return 0;
|
|
}
|
|
|
|
|
|
|
|
void STPushMTPop( bool bDistribute )
|
|
{
|
|
Msg( "%s test: single thread push, multithread pop, %s", g_pListType, bDistribute ? "distributed..." : "no affinity..." );
|
|
TestStart();
|
|
ThreadHandle_t hPush = CreateSimpleThread( &PushThreadFunc, NULL );
|
|
ThreadHandle_t *arrPops = CreateTestThreads( PopThreadFunc, NUM_THREADS - 1, ( bDistribute ) ? NUM_PROCESSORS : 0 );
|
|
|
|
TestWait();
|
|
TestEnd();
|
|
JoinTestThreads( arrPops );
|
|
ThreadJoin( hPush );
|
|
ReleaseThreadHandle( hPush );
|
|
}
|
|
|
|
void MTPushSTPop( bool bDistribute )
|
|
{
|
|
Msg( "%s test: multithread push, single thread pop, %s", g_pListType, bDistribute ? "distributed..." : "no affinity..." );
|
|
TestStart();
|
|
ThreadHandle_t hPop = CreateSimpleThread( &PopThreadFunc, NULL );
|
|
ThreadHandle_t* arrPushes = CreateTestThreads( PushThreadFunc, NUM_THREADS - 1, ( bDistribute ) ? NUM_PROCESSORS : 0 );
|
|
|
|
TestWait();
|
|
TestEnd();
|
|
JoinTestThreads( arrPushes );
|
|
ThreadJoin( hPop );
|
|
ReleaseThreadHandle( hPop );
|
|
}
|
|
|
|
|
|
void MTPushMTPop( bool bDistribute )
|
|
{
|
|
Msg( "%s test: multithread push, multithread pop, %s", g_pListType, bDistribute ? "distributed..." : "no affinity..." );
|
|
TestStart();
|
|
int ct = 0;
|
|
ThreadHandle_t *threadHandles = (ThreadHandle_t *)stackalloc( NUM_THREADS * sizeof(ThreadHandle_t) );
|
|
int nHandles = 0;
|
|
|
|
for ( int i = 0; i < NUM_THREADS / 2 ; i++ )
|
|
{
|
|
ThreadHandle_t hThread = CreateSimpleThread( &PopThreadFunc, NULL );
|
|
threadHandles[nHandles++] = hThread;
|
|
if ( bDistribute )
|
|
{
|
|
int32 mask = 1 << (ct++ % NUM_PROCESSORS);
|
|
ThreadSetAffinity( hThread, mask );
|
|
}
|
|
}
|
|
for ( int i = 0; i < NUM_THREADS / 2 ; i++ )
|
|
{
|
|
ThreadHandle_t hThread = CreateSimpleThread( &PushThreadFunc, NULL );
|
|
threadHandles[nHandles++] = hThread;
|
|
if ( bDistribute )
|
|
{
|
|
int32 mask = 1 << (ct++ % NUM_PROCESSORS);
|
|
ThreadSetAffinity( hThread, mask );
|
|
}
|
|
}
|
|
|
|
TestWait();
|
|
TestEnd();
|
|
|
|
for ( int i = 0; i < nHandles; i++ )
|
|
{
|
|
ReleaseThreadHandle( threadHandles[i] );
|
|
}
|
|
}
|
|
|
|
void MTPushPopPopInterleaved( bool bDistribute )
|
|
{
|
|
Msg( "%s test: multithread interleaved push/pop, %s", g_pListType, bDistribute ? "distributed..." : "no affinity..." );
|
|
srand( Plat_MSTime() );
|
|
TestStart();
|
|
ThreadHandle_t * arrPushPops = CreateTestThreads( &PushPopInterleavedTestThreadFunc, NUM_THREADS, ( bDistribute ) ? NUM_PROCESSORS : 0 );
|
|
TestWait();
|
|
TestEnd();
|
|
JoinTestThreads( arrPushPops );
|
|
}
|
|
|
|
|
|
|
|
void MTPushSeqPop( bool bDistribute )
|
|
{
|
|
Msg( "%s test: multithread push, sequential pop, %s", g_pListType, bDistribute ? "distributed..." : "no affinity..." );
|
|
TestStart();
|
|
ThreadHandle_t * arrPushes = CreateTestThreads( PushThreadFunc, NUM_THREADS, ( bDistribute ) ? NUM_PROCESSORS : 0 );
|
|
|
|
TestWait();
|
|
int ignored;
|
|
g_pTestOps->Validate();
|
|
int nPopped = 0;
|
|
while ( g_pTestOps->Pop( &ignored ) )
|
|
{
|
|
nPopped++;
|
|
}
|
|
if ( nPopped != NUM_TEST )
|
|
{
|
|
Msg( "Pops != pushes?\n" );
|
|
DebuggerBreakIfDebugging();
|
|
}
|
|
TestEnd();
|
|
|
|
JoinTestThreads( arrPushes );
|
|
}
|
|
|
|
|
|
void SeqPushMTPop( bool bDistribute )
|
|
{
|
|
Msg( "%s test: sequential push, multithread pop, %s", g_pListType, bDistribute ? "distributed..." : "no affinity..." );
|
|
TestStart();
|
|
while ( g_nTested++ < NUM_TEST )
|
|
{
|
|
g_pTestOps->Push( g_nTested );
|
|
}
|
|
|
|
ThreadHandle_t * arrPops = CreateTestThreads( PopThreadFunc, NUM_THREADS, ( bDistribute ) ? NUM_PROCESSORS : 0 );
|
|
|
|
TestWait();
|
|
TestEnd();
|
|
|
|
JoinTestThreads( arrPops );
|
|
}
|
|
|
|
|
|
#ifdef _PS3
|
|
void TestThreadProc( uint64_t id )
|
|
{
|
|
printf( "(TS)Hello from PPU thread %lld @%p\n", id, &id );
|
|
sys_ppu_thread_exit( id );
|
|
}
|
|
uintp TestThreadProc2( void *p )
|
|
{
|
|
printf( "(TS)Hello from PPU thread %lld @%p\n", (int64)p, &p );
|
|
return (uintp)p;
|
|
}
|
|
#endif
|
|
|
|
void TestThreads()
|
|
{
|
|
#ifdef _PS3
|
|
printf("(TS)testing threads\n");
|
|
const int numThreads = 40;
|
|
ThreadHandle_t * arrTests = CreateTestThreads( TestThreadProc2, numThreads, false );
|
|
JoinTestThreads( arrTests );
|
|
#endif
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
void RunSharedTests( int nTests )
|
|
{
|
|
using namespace TSListTests;
|
|
TestThreads();
|
|
const CPUInformation &pi = GetCPUInformation();
|
|
NUM_PROCESSORS = pi.m_nLogicalProcessors;
|
|
MAX_THREADS = NUM_PROCESSORS * 2;
|
|
g_pTestBuckets = new int[NUM_TEST];
|
|
while ( nTests-- )
|
|
{
|
|
for ( NUM_THREADS = 2; NUM_THREADS <= MAX_THREADS; NUM_THREADS *= 2)
|
|
{
|
|
Msg( "\nTesting %d threads:\n", NUM_THREADS );
|
|
PushPopTest();
|
|
PushPopInterleavedTest();
|
|
SeqPushMTPop( false );
|
|
STPushMTPop( false );
|
|
MTPushSeqPop( false );
|
|
MTPushSTPop( false );
|
|
MTPushMTPop( false );
|
|
MTPushPopPopInterleaved( false );
|
|
if ( NUM_PROCESSORS > 1 )
|
|
{
|
|
SeqPushMTPop( true );
|
|
STPushMTPop( true );
|
|
MTPushSeqPop( true );
|
|
MTPushSTPop( true );
|
|
MTPushMTPop( true );
|
|
MTPushPopPopInterleaved( true );
|
|
}
|
|
}
|
|
}
|
|
delete[] g_pTestBuckets;
|
|
}
|
|
|
|
bool RunTSListTests( int nListSize, int nTests )
|
|
{
|
|
using namespace TSListTests;
|
|
NUM_TEST = nListSize;
|
|
|
|
#ifdef USE_NATIVE_SLIST
|
|
|
|
#ifdef _WIN64
|
|
int maxSize = 65536; // FIXME: How should this be computed?
|
|
#else
|
|
int maxSize = ( 1 << (sizeof( ((TSLHead_t *)(0))->Depth ) * 8) ) - 1;
|
|
#endif
|
|
|
|
#else
|
|
int maxSize = ( 1 << (sizeof( ((TSLHead_t *)(0))->value.Depth ) * 8) ) - 1;
|
|
#endif
|
|
if ( NUM_TEST > maxSize )
|
|
{
|
|
Msg( "TSList cannot hold more that %d nodes\n", maxSize );
|
|
return false;
|
|
}
|
|
|
|
|
|
g_pTestOps = &g_ListOps;
|
|
g_pListType = "CTSList";
|
|
|
|
RunSharedTests( nTests );
|
|
|
|
Msg("Tests done, purging test memory..." );
|
|
g_TestList.Purge();
|
|
Msg( "done\n");
|
|
return true;
|
|
}
|
|
|
|
bool RunTSQueueTests( int nListSize, int nTests )
|
|
{
|
|
using namespace TSListTests;
|
|
NUM_TEST = nListSize;
|
|
|
|
g_pTestOps = &g_QueueOps;
|
|
g_pListType = "CTSQueue";
|
|
|
|
RunSharedTests( nTests );
|
|
|
|
Msg("Tests done, purging test memory..." );
|
|
g_TestQueue.Purge();
|
|
Msg( "done\n");
|
|
return true;
|
|
}
|