550 lines
16 KiB
C++
550 lines
16 KiB
C++
//+---------------------------------------------------------------------------
|
|
//
|
|
// Microsoft Windows
|
|
// Copyright (C) Microsoft Corporation, 1991 - 1999
|
|
//
|
|
// File: filidmap.cxx
|
|
//
|
|
// Contents: FileId to wid mapping using hashed access
|
|
//
|
|
// History: 07-May-97 SitaramR Created
|
|
//
|
|
// Notes: Only ntfs 5.0 wids are added to the file id map because all
|
|
// non-ntfs 5.0 wids map to fileIdInvalid, which means that there
|
|
// will be too many collisions on fileIdInvalid, which will degrade
|
|
// the performance of the hashed access. One drawback of mapping
|
|
// only ntfs 5.0 wids is that the count of wids in fileid map and
|
|
// property store cannot be checked for equality to detect
|
|
// corruption as is done for the strings table. However, there is a
|
|
// correlation between a count mismatch in strings table and in
|
|
// file id map table because the file id map table is flushed before
|
|
// the strings table. As a result, when a corruption is detected
|
|
// in strings table, a corruption error is thrown and the processing
|
|
// for that corruption error reinitializes both strings table and the
|
|
// file id map table.
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
#include <pch.cxx>
|
|
#pragma hdrstop
|
|
|
|
#include <filidmap.hxx>
|
|
#include <mmstrm.hxx>
|
|
#include <cistore.hxx>
|
|
#include <prpstmgr.hxx>
|
|
#include <propiter.hxx>
|
|
#include <cicat.hxx>
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::CFileIdMap
|
|
//
|
|
// Synopsis: Constructor
|
|
//
|
|
// Arguments: [propStoreMgr] -- Property store
|
|
// [cicat] -- CiCat
|
|
//
|
|
// History: 07-May-97 SitaramR Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
CFileIdMap::CFileIdMap( CPropStoreManager &propStoreMgr )
|
|
: CPersHash( propStoreMgr, FALSE ),
|
|
_cCacheEntries( 0 )
|
|
#if CIDBG == 1
|
|
, _cCacheHits( 0 ),
|
|
_cCacheNegativeHits( 0 ),
|
|
_cCacheMisses( 0 ),
|
|
_cCacheNegativeMisses( 0 )
|
|
#endif
|
|
{
|
|
}
|
|
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::FastInit
|
|
//
|
|
// Synopsis: Fast initialization
|
|
//
|
|
// Arguments: [pStorage] -- Ci storage
|
|
// [pwcsCatDir] -- Catalog directory
|
|
// [pwcsFile] -- File id file name
|
|
// [version] -- Content index version
|
|
//
|
|
// History: 28-Jul-97 SitaramR Created
|
|
// 13-Mar-98 KitmanH Passed in True to
|
|
// CPerHash::FastInit to specify
|
|
// that a FileIdMap is wanted
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
BOOL CFileIdMap::FastInit( CiStorage * pStorage,
|
|
ULONG version )
|
|
{
|
|
return CPersHash::FastInit(pStorage, version, TRUE);
|
|
}
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::LongInit
|
|
//
|
|
// Synopsis: Initialization that may take a long time
|
|
//
|
|
// Arguments: [version] -- CI version
|
|
// [fDirtyShutdown] -- Set to TRUE if the previous shutdown
|
|
// was dirty.
|
|
//
|
|
// History: 28-Jul-97 SitaramR Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::LongInit ( ULONG version, BOOL fDirtyShutdown )
|
|
{
|
|
CPersHash::LongInit( version, fDirtyShutdown );
|
|
}
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::LokFlush
|
|
//
|
|
// Synopsis: Flushes fileid map
|
|
//
|
|
// History: 28-Jul-97 SitaramR Created
|
|
// 27-Feb-98 KitmanH Don't flush if catalog is
|
|
// read-only
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::LokFlush()
|
|
{
|
|
if ( !_fIsReadOnly )
|
|
CPersHash::LokFlush();
|
|
} //LokFlush
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::AddToCache, private
|
|
//
|
|
// Synopsis: Adds an entry to the cache, or overwrites wid if the
|
|
// entry currently exists. The oldest entry is bumped out.
|
|
// Caching an entry with widInvalid is valid.
|
|
//
|
|
// Arguments: [fileId] -- FileId to add
|
|
// [wid] -- VolumeId to add
|
|
// [volumeId] -- VolumeId to add
|
|
//
|
|
// History: 22-Jul-98 dlee Created
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::AddToCache(
|
|
FILEID & fileId,
|
|
WORKID wid,
|
|
VOLUMEID volumeId )
|
|
{
|
|
// First look for the fileid/volumeid currently in the cache
|
|
|
|
for ( unsigned iCache = 0; iCache < _cCacheEntries; iCache++ )
|
|
{
|
|
if ( _aCache[ iCache ].fileId == fileId &&
|
|
_aCache[ iCache ].volumeId == volumeId )
|
|
{
|
|
_aCache[ iCache ].wid = wid;
|
|
return;
|
|
}
|
|
}
|
|
|
|
Win4Assert( _cCacheEntries <= cFileIdMapCacheEntries );
|
|
|
|
// Bump out the oldest item and put the new item first in the array
|
|
|
|
unsigned cToMove;
|
|
|
|
if ( _cCacheEntries == cFileIdMapCacheEntries )
|
|
{
|
|
cToMove = cFileIdMapCacheEntries - 1;
|
|
}
|
|
else
|
|
{
|
|
cToMove = _cCacheEntries;
|
|
_cCacheEntries++;
|
|
}
|
|
|
|
RtlMoveMemory( & _aCache[ 1 ],
|
|
& _aCache[ 0 ],
|
|
sizeof SFileIdMapEntry * cToMove );
|
|
|
|
_aCache[0].fileId = fileId;
|
|
_aCache[0].volumeId = volumeId;
|
|
_aCache[0].wid = wid;
|
|
} //AddToCache
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::FindInCache, private
|
|
//
|
|
// Synopsis: Locates a workid in the cache given a fileid and volumeid
|
|
//
|
|
// Arguments: [fileId] -- FileId of entry to find
|
|
// [volumeId] -- VolumeId of entry to find
|
|
// [wid] -- Returns the workid if found
|
|
//
|
|
// Returns: TRUE if found or FALSE if not found
|
|
//
|
|
// History: 22-Jul-98 dlee Created
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
|
|
BOOL CFileIdMap::FindInCache(
|
|
FILEID & fileId,
|
|
VOLUMEID volumeId,
|
|
WORKID & wid )
|
|
{
|
|
for ( unsigned iCache = 0; iCache < _cCacheEntries; iCache++ )
|
|
{
|
|
if ( _aCache[ iCache ].fileId == fileId &&
|
|
_aCache[ iCache ].volumeId == volumeId )
|
|
{
|
|
wid = _aCache[ iCache ].wid;
|
|
|
|
#if CIDBG == 1
|
|
ciDebugOut(( DEB_USN,
|
|
"fim::find cache worked %#I64x %#x, vol %wc\n",
|
|
fileId, wid, volumeId ));
|
|
|
|
_cCacheHits++;
|
|
|
|
if ( widInvalid == wid )
|
|
_cCacheNegativeHits++;
|
|
#endif
|
|
|
|
return TRUE;
|
|
}
|
|
}
|
|
|
|
return FALSE;
|
|
} //FindInCache
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::RemoveFromCache, private
|
|
//
|
|
// Synopsis: Removes the item from the cache if it exists
|
|
//
|
|
// Arguments: [fileId] -- FileId of entry to remove (only used for assert)
|
|
// [wid] -- Workid of entry to remove
|
|
//
|
|
// History: 22-Jul-98 dlee Created
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::RemoveFromCache(
|
|
FILEID & fileId,
|
|
WORKID wid )
|
|
{
|
|
for ( unsigned iCache = 0; iCache < _cCacheEntries; iCache++ )
|
|
{
|
|
if ( _aCache[ iCache ].wid == wid )
|
|
{
|
|
Win4Assert( _aCache[ iCache ].fileId == fileId );
|
|
|
|
RtlCopyMemory( & _aCache[ iCache ],
|
|
& _aCache[ iCache + 1 ],
|
|
sizeof SFileIdMapEntry * ( _cCacheEntries - iCache - 1 ) );
|
|
_cCacheEntries--;
|
|
break;
|
|
}
|
|
}
|
|
} //RemoveFromCache
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::LokFind, private
|
|
//
|
|
// Synopsis: Given fileId, find workid.
|
|
//
|
|
// Arguments: [fileId] - FileId to locate
|
|
// [volumeId] - Volume id of fileid
|
|
//
|
|
// Returns: Workid of FileId
|
|
//
|
|
// History: 07-May-97 SitaramR Created
|
|
//
|
|
// Notes: File ids are not unique across different volumes, hence the
|
|
// need for volume ids.
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
|
|
WORKID CFileIdMap::LokFind( FILEID fileId, VOLUMEID volumeId )
|
|
{
|
|
Win4Assert( _fFullInit );
|
|
WORKID wid;
|
|
|
|
if ( FindInCache( fileId, volumeId, wid ) )
|
|
return wid;
|
|
|
|
#if CIDBG == 1
|
|
_cCacheMisses++;
|
|
#endif
|
|
|
|
#ifdef DO_STATS
|
|
unsigned cSearchLen = 0;
|
|
#endif
|
|
|
|
CShortWidList list( HashFun(fileId), _hTable );
|
|
|
|
for ( wid = list.WorkId(); wid != widInvalid; wid = list.NextWorkId() )
|
|
{
|
|
|
|
#ifdef DO_STATS
|
|
cSearchLen++;
|
|
#endif
|
|
|
|
XPrimaryRecord rec( _PropStoreMgr, wid );
|
|
|
|
PROPVARIANT propVar;
|
|
BOOL fFound = _PropStoreMgr.ReadProperty( rec.GetReference(),
|
|
pidFileIndex,
|
|
propVar );
|
|
|
|
ciDebugOut(( DEB_ITRACE, "trying wid %#x, fFound %d, fid %#I64x\n",
|
|
wid, fFound, propVar.uhVal.QuadPart ));
|
|
if ( fFound && propVar.uhVal.QuadPart == fileId )
|
|
{
|
|
Win4Assert( propVar.vt == VT_UI8 );
|
|
|
|
BOOL fFound = _PropStoreMgr.ReadProperty( rec.GetReference(),
|
|
pidVolumeId,
|
|
propVar );
|
|
|
|
if ( fFound && propVar.ulVal == volumeId )
|
|
{
|
|
Win4Assert( propVar.vt == VT_UI4 );
|
|
|
|
#ifdef DO_STATS
|
|
_hTable.UpdateStats( cSearchLen );
|
|
#endif
|
|
|
|
ciDebugOut(( DEB_USN, "fim::find worked %#I64x %#x, vol %wc\n",
|
|
fileId, wid, volumeId ));
|
|
|
|
AddToCache( fileId, wid, volumeId );
|
|
return wid;
|
|
}
|
|
else
|
|
{
|
|
ciDebugOut(( DEB_USN, "fim::find fileid match, but not volid: %#x, %#x\n",
|
|
propVar.ulVal, volumeId ));
|
|
}
|
|
}
|
|
}
|
|
|
|
ciDebugOut(( DEB_USN, "fim::find failed %#I64x, vol %wc\n", fileId, volumeId ));
|
|
|
|
#if CIDBG == 1
|
|
_cCacheNegativeMisses++;
|
|
#endif
|
|
|
|
//
|
|
// Often, a new file is looked up multiple times before it is added, so
|
|
// add the widInvalid entry to the cache. Negative lookups are slow.
|
|
//
|
|
|
|
AddToCache( fileId, widInvalid, volumeId );
|
|
|
|
return widInvalid;
|
|
} //LokFind
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::LokAdd
|
|
//
|
|
// Synopsis: Add a new fileid to wid mapping
|
|
//
|
|
// Arguments: [fileId] -- File Id
|
|
// [wid] -- Workid
|
|
//
|
|
// History: 07-May-97 SitaramR Created
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::LokAdd( FILEID fileId, WORKID wid, VOLUMEID volumeId )
|
|
{
|
|
ciDebugOut(( DEB_USN, "Adding map fileid %#I64x -> wid %x, vol %wc\n",
|
|
fileId, wid, volumeId ));
|
|
|
|
Win4Assert( fileIdInvalid != fileId );
|
|
Win4Assert( _fFullInit );
|
|
|
|
//
|
|
// Must grow hash table first, as it grovels through property store.
|
|
//
|
|
|
|
if ( _hTable.IsFull() )
|
|
GrowHashTable();
|
|
|
|
AddToCache( fileId, wid, volumeId );
|
|
|
|
_hTable.Add ( HashFun(fileId), wid );
|
|
} //LokAdd
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::LokDelete
|
|
//
|
|
// Synopsis: Delete file id from table
|
|
//
|
|
// Arguments: [fileId] -- FileId to remove
|
|
// [wid] -- Workid to remove
|
|
//
|
|
// History: 07-May-97 SitaramR Created.
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::LokDelete( FILEID fileId, WORKID wid )
|
|
{
|
|
ciDebugOut(( DEB_USN, "Removing map fileid %#I64x, %#x\n", fileId, wid ));
|
|
|
|
RemoveFromCache( fileId, wid );
|
|
|
|
_hTable.Remove( HashFun( fileId ), wid, TRUE );
|
|
} //LokDelete
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::HashAll
|
|
//
|
|
// Synopsis: Re-hash all fileId's (after hash table growth)
|
|
//
|
|
// History: 07-May-97 May Created
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
void CFileIdMap::HashAll()
|
|
{
|
|
// Count the number of hash table entries and grow the hash table
|
|
|
|
{
|
|
CPropertyStoreWids iter( _PropStoreMgr );
|
|
|
|
unsigned cWids = 0;
|
|
|
|
for ( WORKID wid = iter.WorkId(); wid != widInvalid; wid = iter.NextWorkId() )
|
|
{
|
|
if ( _fAbort )
|
|
{
|
|
ciDebugOut(( DEB_WARN,
|
|
"Stopping FileIdMap::HashAll because of shutdown\n" ));
|
|
THROW( CException(STATUS_TOO_LATE) );
|
|
}
|
|
|
|
PROPVARIANT propVar;
|
|
BOOL fFound = _PropStoreMgr.ReadPrimaryProperty( wid, pidFileIndex, propVar );
|
|
|
|
// Only ntfs 5.0 wids have valid fileid's
|
|
|
|
if ( fFound &&
|
|
( VT_UI8 == propVar.vt ) &&
|
|
( fileIdInvalid != propVar.uhVal.QuadPart ) )
|
|
cWids++;
|
|
}
|
|
|
|
GrowToSize( cWids );
|
|
}
|
|
|
|
// Add the wids to the hash table
|
|
|
|
CPropertyStoreWids iter( _PropStoreMgr );
|
|
|
|
for ( WORKID wid = iter.WorkId(); wid != widInvalid; wid = iter.NextWorkId() )
|
|
{
|
|
if ( _fAbort )
|
|
{
|
|
ciDebugOut(( DEB_WARN,
|
|
"Stopping FileIdMap::HashAll because of shutdown\n" ));
|
|
THROW( CException(STATUS_TOO_LATE) );
|
|
}
|
|
|
|
PROPVARIANT propVar;
|
|
BOOL fFound = _PropStoreMgr.ReadPrimaryProperty( wid, pidFileIndex, propVar );
|
|
|
|
//
|
|
// Only ntfs 5.0 wids have valid fileid's
|
|
//
|
|
if ( fFound &&
|
|
( VT_UI8 == propVar.vt ) &&
|
|
( fileIdInvalid != propVar.uhVal.QuadPart ) )
|
|
_hTable.Add ( HashFun( propVar.uhVal.QuadPart ), wid );
|
|
}
|
|
|
|
#if 0
|
|
|
|
//
|
|
// Look-up every file to see what the hashing looks like.
|
|
//
|
|
|
|
{
|
|
CPropertyStoreWids iter( _PropStoreMgr );
|
|
|
|
unsigned cWids = 0;
|
|
|
|
for ( WORKID wid = iter.WorkId(); wid != widInvalid; wid = iter.NextWorkId() )
|
|
{
|
|
XPrimaryRecord rec( _PropStoreMgr, wid );
|
|
PROPVARIANT propVar;
|
|
BOOL fFound = _PropStoreMgr.ReadProperty( rec.GetReference(),
|
|
pidFileIndex,
|
|
propVar );
|
|
|
|
// Only ntfs 5.0 wids have valid fileid's
|
|
|
|
if ( fFound &&
|
|
( VT_UI8 == propVar.vt ) &&
|
|
( fileIdInvalid != propVar.uhVal.QuadPart ) )
|
|
{
|
|
FILEID fid = propVar.uhVal.QuadPart;
|
|
_PropStoreMgr.ReadProperty( rec.GetReference(),
|
|
pidVolumeId,
|
|
propVar );
|
|
LokFind( fid, propVar.ulVal );
|
|
}
|
|
}
|
|
|
|
ciDebugOut(( DEB_FORCE,
|
|
"hash: size %d count %d maxchain %d searches %d length %d\n",
|
|
_hTable.Size(),
|
|
_hTable.Count(),
|
|
_hTable._cMaxChainLen,
|
|
_hTable._cTotalSearches,
|
|
_hTable._cTotalLength ));
|
|
}
|
|
#endif
|
|
} //HashAll
|
|
|
|
//+-------------------------------------------------------------------------
|
|
//
|
|
// Member: CFileIdMap::HashFun
|
|
//
|
|
// Synopsis: Hash function for fileid's
|
|
//
|
|
// Arguments: [fileId] - FileId to hash
|
|
//
|
|
// History: 07-May-97 SitaramR Created
|
|
//
|
|
//--------------------------------------------------------------------------
|
|
|
|
unsigned CFileIdMap::HashFun( FILEID fileId )
|
|
{
|
|
//
|
|
// The lower 32 bits of the fileid are unique at any given time. The
|
|
// upper 32 bits of the fileid represent a sequence number that is
|
|
// incremented every time one of the lower 32 bits number is reused.
|
|
// So, a good hash function is to simply use the lower 32 bits.
|
|
//
|
|
|
|
return (unsigned) fileId;
|
|
} //HashFun
|
|
|
|
|