You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
338 lines
9.4 KiB
338 lines
9.4 KiB
//========= Copyright © 1996-2008, Valve Corporation, All rights reserved. ============// |
|
// |
|
// Purpose: |
|
// |
|
// $NoKeywords: $ |
|
// |
|
//=============================================================================// |
|
#include "cbase.h" |
|
#include "querycache.h" |
|
#include "tier0/vprof.h" |
|
#include "tier1/utlintrusivelist.h" |
|
#include "datacache/imdlcache.h" |
|
#include "vstdlib/jobthread.h" |
|
|
|
|
|
// memdbgon must be the last include file in a .cpp file!!! |
|
#include "tier0/memdbgon.h" |
|
|
|
|
|
|
|
#define QUERYCACHE_SIZE 1024 |
|
|
|
static QueryCacheEntry_t s_QCache[QUERYCACHE_SIZE]; |
|
|
|
#define QUERYCACHE_HASH_SIZE ( QUERYCACHE_SIZE * 2 ) |
|
|
|
// elements available for cache reuse |
|
static CUtlIntrusiveDList<QueryCacheEntry_t> s_VictimList; |
|
|
|
|
|
static CUtlIntrusiveDList<QueryCacheEntry_t> s_HashChains[QUERYCACHE_HASH_SIZE]; |
|
|
|
|
|
|
|
static int s_nReplaceCtr = QUERYCACHE_SIZE - 1; |
|
static int s_nTimeStampCounter = 0 ; |
|
static int s_nNumCacheQueries = 0; |
|
static int s_nNumCacheMisses = 0; |
|
static int s_SuccessfulSpeculatives = 0; |
|
static int s_WastedSpeculativeUpdates = 0; |
|
|
|
void QueryCacheKey_t::ComputeHashIndex( void ) |
|
{ |
|
unsigned int ret = ( unsigned int ) m_Type; |
|
for( int i = 0 ; i < m_nNumValidPoints; i++ ) |
|
{ |
|
ret += ( unsigned int ) m_pEntities[i].ToInt(); |
|
ret += ( unsigned int ) m_nOffsetMode; |
|
} |
|
ret += *( ( uint32 *) &m_flMinimumUpdateInterval ); |
|
ret += m_nTraceMask; |
|
m_nHashIdx = ret % QUERYCACHE_HASH_SIZE; |
|
} |
|
|
|
|
|
ConVar sv_disable_querycache("sv_disable_querycache", "0", FCVAR_CHEAT | FCVAR_REPLICATED | FCVAR_DEVELOPMENTONLY, "debug - disable trace query cache" ); |
|
|
|
static QueryCacheEntry_t *FindOrAllocateCacheEntry( QueryCacheKey_t const &entry ) |
|
{ |
|
QueryCacheEntry_t *pFound = NULL; |
|
// see if we find it |
|
for( QueryCacheEntry_t *pNode = s_HashChains[entry.m_nHashIdx].m_pHead; pNode; pNode = pNode->m_pNext ) |
|
{ |
|
if ( pNode->m_QueryParams.Matches( &entry ) ) |
|
{ |
|
pFound = pNode; |
|
break; |
|
} |
|
} |
|
if (! pFound ) |
|
{ |
|
pFound = s_VictimList.RemoveHead(); |
|
if ( ! pFound ) |
|
{ |
|
// randomly replace one |
|
pFound = s_QCache + s_nReplaceCtr; |
|
s_nReplaceCtr--; |
|
if ( s_nReplaceCtr < 0 ) |
|
s_nReplaceCtr = QUERYCACHE_SIZE - 1; |
|
if ( pFound->m_QueryParams.m_Type != EQUERY_INVALID ) |
|
{ |
|
s_HashChains[pFound->m_QueryParams.m_nHashIdx].RemoveNode( pFound ); |
|
} |
|
} |
|
pFound->m_QueryParams = entry; |
|
s_HashChains[pFound->m_QueryParams.m_nHashIdx].AddToHead( pFound ); |
|
pFound->m_bSpeculativelyDone = false; |
|
pFound->IssueQuery(); |
|
} |
|
else |
|
{ |
|
if ( sv_disable_querycache.GetInt() || |
|
( gpGlobals->curtime - pFound->m_flLastUpdateTime >= |
|
pFound->m_QueryParams.m_flMinimumUpdateInterval ) ) |
|
{ |
|
pFound->m_bSpeculativelyDone = false; |
|
pFound->IssueQuery(); |
|
} |
|
else |
|
{ |
|
if ( pFound->m_bSpeculativelyDone ) |
|
s_SuccessfulSpeculatives++; |
|
} |
|
|
|
} |
|
return pFound; |
|
} |
|
|
|
static QueryCacheEntry_t *FindOrAllocateCacheEntry( EQueryType_t nType, |
|
CBaseEntity *pEntity1, CBaseEntity *pEntity2, |
|
EEntityOffsetMode_t nMode1, EEntityOffsetMode_t nMode2, |
|
unsigned int nTraceMask ) |
|
{ |
|
QueryCacheKey_t entry; |
|
entry.m_Type = nType; |
|
entry.m_pEntities[0] = pEntity1; |
|
entry.m_pEntities[1] = pEntity2; |
|
entry.m_nOffsetMode[0] = nMode1; |
|
entry.m_nOffsetMode[1] = nMode2; |
|
entry.m_nTraceMask = nTraceMask; |
|
entry.m_nNumValidPoints = 2; |
|
entry.ComputeHashIndex(); |
|
return FindOrAllocateCacheEntry( entry ); |
|
} |
|
|
|
bool QueryCacheKey_t::Matches( QueryCacheKey_t const *pNode ) const |
|
{ |
|
if ( |
|
( pNode->m_Type != m_Type ) || |
|
( pNode->m_nTraceMask != m_nTraceMask ) || |
|
( pNode->m_pTraceFilterFunction != m_pTraceFilterFunction ) || |
|
( pNode->m_nNumValidPoints != m_nNumValidPoints ) || |
|
( pNode->m_flMinimumUpdateInterval != m_flMinimumUpdateInterval ) |
|
) |
|
return false; |
|
for( int i = 0; i < m_nNumValidPoints; i++ ) |
|
{ |
|
if ( |
|
( pNode->m_pEntities[i] != m_pEntities[i] ) || |
|
( pNode->m_nOffsetMode[i] != m_nOffsetMode[i] ) |
|
) |
|
return false; |
|
} |
|
return true; |
|
} |
|
|
|
static void CalculateOffsettedPosition( CBaseEntity *pEntity, EEntityOffsetMode_t nMode, Vector *pVecOut ) |
|
{ |
|
switch( nMode ) |
|
{ |
|
case EOFFSET_MODE_WORLDSPACE_CENTER: |
|
*pVecOut = pEntity->WorldSpaceCenter(); |
|
break; |
|
|
|
case EOFFSET_MODE_EYEPOSITION: |
|
*pVecOut = pEntity->EyePosition(); |
|
break; |
|
|
|
case EOFFSET_MODE_NONE: |
|
pVecOut->Init(); |
|
break; |
|
} |
|
} |
|
|
|
|
|
|
|
struct QueryCacheUpdateRecord_t |
|
{ |
|
int m_nStartHashChain; |
|
int m_nNumHashChainsToUpdate; |
|
CUtlIntrusiveDListWithTailPtr<QueryCacheEntry_t> m_KilledList; |
|
}; |
|
|
|
|
|
|
|
void ProcessQueryCacheUpdate( QueryCacheUpdateRecord_t &workItem ) |
|
{ |
|
float flCurTime = gpGlobals->curtime; |
|
// run through all of the cache. |
|
for( int i = 0; i < workItem.m_nNumHashChainsToUpdate; i++ ) |
|
{ |
|
QueryCacheEntry_t *pNext; |
|
for( QueryCacheEntry_t *pEntry = s_HashChains[i + workItem.m_nStartHashChain].m_pHead ; pEntry; pEntry = pNext ) |
|
{ |
|
pNext = pEntry->m_pNext; |
|
if ( pEntry->m_bUsedSinceUpdated ) |
|
{ |
|
if ( flCurTime - pEntry->m_flLastUpdateTime >= |
|
pEntry->m_QueryParams.m_flMinimumUpdateInterval ) |
|
{ |
|
// don't bother updating if we have recently |
|
pEntry->IssueQuery(); |
|
pEntry->m_bUsedSinceUpdated = false; |
|
pEntry->m_bSpeculativelyDone = true; |
|
} |
|
} |
|
else |
|
{ |
|
if ( flCurTime - pEntry->m_flLastUpdateTime > pEntry->m_QueryParams.m_flMinimumUpdateInterval ) |
|
{ |
|
if ( pEntry->m_bSpeculativelyDone && ( !pEntry->m_bUsedSinceUpdated ) ) |
|
{ |
|
s_WastedSpeculativeUpdates++; |
|
} |
|
pEntry->m_QueryParams.m_Type = EQUERY_INVALID; |
|
s_HashChains[pEntry->m_QueryParams.m_nHashIdx].RemoveNode( pEntry ); |
|
workItem.m_KilledList.AddToHead( pEntry ); |
|
} |
|
} |
|
} |
|
} |
|
} |
|
|
|
|
|
#define N_WAYS_TO_SPLIT_CACHE_UPDATE 8 |
|
|
|
static void PreUpdateQueryCache() |
|
{ |
|
mdlcache->BeginCoarseLock(); |
|
mdlcache->BeginLock(); |
|
} |
|
|
|
static void PostUpdateQueryCache() |
|
{ |
|
mdlcache->EndLock(); |
|
mdlcache->EndCoarseLock(); |
|
} |
|
|
|
|
|
void UpdateQueryCache( void ) |
|
{ |
|
// parallel process all hash chains |
|
QueryCacheUpdateRecord_t workList[N_WAYS_TO_SPLIT_CACHE_UPDATE]; |
|
int nCurEntry = 0; |
|
for( int i =0 ; i < N_WAYS_TO_SPLIT_CACHE_UPDATE; i++ ) |
|
{ |
|
workList[i].m_nStartHashChain = nCurEntry; |
|
if ( i != N_WAYS_TO_SPLIT_CACHE_UPDATE -1 ) |
|
workList[i].m_nNumHashChainsToUpdate = ARRAYSIZE( s_HashChains ) / N_WAYS_TO_SPLIT_CACHE_UPDATE; |
|
else |
|
workList[i].m_nNumHashChainsToUpdate = ARRAYSIZE( s_HashChains ) - nCurEntry; |
|
nCurEntry += ARRAYSIZE( s_HashChains ) / N_WAYS_TO_SPLIT_CACHE_UPDATE; |
|
} |
|
ParallelProcess( workList, N_WAYS_TO_SPLIT_CACHE_UPDATE, ProcessQueryCacheUpdate, PreUpdateQueryCache, PostUpdateQueryCache, ( sv_disable_querycache.GetBool() ) ? 0 : INT_MAX ); |
|
// now, we need to take all of the obsolete cache entries each thread generated and add them to |
|
// the victim cache |
|
for( int i = 0 ; i < N_WAYS_TO_SPLIT_CACHE_UPDATE; i++ ) |
|
{ |
|
PrependDListWithTailToDList( workList[i].m_KilledList, s_VictimList ); |
|
} |
|
} |
|
|
|
void InvalidateQueryCache( void ) |
|
{ |
|
s_VictimList.RemoveAll(); |
|
for( int i = 0; i < ARRAYSIZE( s_HashChains); i++ ) |
|
s_HashChains[i].RemoveAll(); |
|
// now, invalidate all cache entries and add them to the victims |
|
for( int i = 0; i < ARRAYSIZE( s_QCache ); i++ ) |
|
{ |
|
s_QCache[i].m_QueryParams.m_Type = EQUERY_INVALID; |
|
s_VictimList.AddToHead( s_QCache + i ); |
|
} |
|
} |
|
|
|
|
|
void QueryCacheEntry_t::IssueQuery( void ) |
|
{ |
|
for( int i = 0 ; i < m_QueryParams.m_nNumValidPoints; i++ ) |
|
{ |
|
CBaseEntity *pEntity = m_QueryParams.m_pEntities[i]; |
|
if (! pEntity ) |
|
{ |
|
m_QueryParams.m_Type = EQUERY_INVALID; |
|
s_HashChains[m_QueryParams.m_nHashIdx].RemoveNode( this ); |
|
s_VictimList.AddToHead( this ); |
|
return; |
|
} |
|
CalculateOffsettedPosition( pEntity, m_QueryParams.m_nOffsetMode[i], |
|
&( m_QueryParams.m_Points[i] ) ); |
|
} |
|
CTraceFilterSimple filter( m_QueryParams.m_pEntities[2], |
|
m_QueryParams.m_nCollisionGroup, |
|
m_QueryParams.m_pTraceFilterFunction ); |
|
trace_t result; |
|
s_nNumCacheMisses++; |
|
UTIL_TraceLine( m_QueryParams.m_Points[0], m_QueryParams.m_Points[1], |
|
m_QueryParams.m_nTraceMask, &filter, &result ); |
|
m_bResult = ! ( result.DidHit() ); |
|
m_flLastUpdateTime = gpGlobals->curtime; |
|
} |
|
|
|
|
|
bool IsLineOfSightBetweenTwoEntitiesClear( CBaseEntity *pSrcEntity, |
|
EEntityOffsetMode_t nSrcOffsetMode, |
|
CBaseEntity *pDestEntity, |
|
EEntityOffsetMode_t nDestOffsetMode, |
|
CBaseEntity *pSkipEntity, |
|
int nCollisionGroup, |
|
unsigned int nTraceMask, |
|
ShouldHitFunc_t pTraceFilterCallback, |
|
float flMinimumUpdateInterval ) |
|
{ |
|
QueryCacheKey_t entry; |
|
entry.m_Type = EQUERY_ENTITY_LOS_CHECK; |
|
entry.m_pEntities[0] = pSrcEntity; |
|
entry.m_pEntities[1] = pDestEntity; |
|
entry.m_pEntities[2] = pSkipEntity; |
|
entry.m_nOffsetMode[0] = nSrcOffsetMode; |
|
entry.m_nOffsetMode[1] = nDestOffsetMode; |
|
entry.m_nOffsetMode[2] = EOFFSET_MODE_NONE; |
|
entry.m_nTraceMask = nTraceMask; |
|
entry.m_nNumValidPoints = 3; |
|
entry.m_nCollisionGroup = nCollisionGroup; |
|
entry.m_pTraceFilterFunction = pTraceFilterCallback; |
|
entry.m_flMinimumUpdateInterval = flMinimumUpdateInterval; |
|
entry.ComputeHashIndex(); |
|
|
|
s_nNumCacheQueries++; |
|
QueryCacheEntry_t *pNode = FindOrAllocateCacheEntry( entry ); |
|
pNode->m_bUsedSinceUpdated = true; |
|
return pNode->m_bResult; |
|
} |
|
|
|
|
|
#if defined( CLIENT_DLL ) |
|
CON_COMMAND_F( cl_querycache_stats, "Display status of the query cache (client only)", FCVAR_CHEAT ) |
|
#else |
|
CON_COMMAND( sv_querycache_stats, "Display status of the query cache (client only)" ) |
|
#endif |
|
{ |
|
Warning( "%d queries, %d misses (%d free) suc spec = %d wasted spec=%d\n", |
|
s_nNumCacheQueries, s_nNumCacheMisses, s_VictimList.Count(), |
|
s_SuccessfulSpeculatives, s_WastedSpeculativeUpdates ); |
|
} |
|
|
|
|
|
|
|
|