Leaked source code of windows server 2003
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.
 
 
 
 
 
 

520 lines
18 KiB

/*++
Copyright (c) 1996 Microsoft Corp.
Module Name: hashutil.cxx
Abstract:
Implementation of linked list of hash tables for cache index lookup.
Author:
Rajeev Dujari (rajeevd) 22-Oct-96
--*/
#include <cache.hxx>
#define SIG_HASH ('H'|('A'<<8)|('S'<<16)|('H'<<24))
typedef LIST_FILEMAP_ENTRY HASH_FILEMAP_ENTRY;
// hash table parameters
#define BYTES_PER_PAGE 4096
#define ITEMS_PER_BUCKET ((BYTES_PER_PAGE - sizeof(HASH_FILEMAP_ENTRY))\
/ (SLOT_COUNT * sizeof(HASH_ITEM)))
#define BYTES_PER_TABLE (sizeof(HASH_FILEMAP_ENTRY) \
+ SLOT_COUNT * ITEMS_PER_BUCKET * sizeof(HASH_ITEM))
//
// Hash Function: Pearson's method
//
PRIVATE DWORD HashKey (LPCSTR lpsz, DWORD dwAddedHash)
{
union
{
DWORD dw;
BYTE c[4];
}
Hash, Hash2;
const static BYTE bTranslate[256] =
{
1, 14,110, 25, 97,174,132,119,138,170,125,118, 27,233,140, 51,
87,197,177,107,234,169, 56, 68, 30, 7,173, 73,188, 40, 36, 65,
49,213,104,190, 57,211,148,223, 48,115, 15, 2, 67,186,210, 28,
12,181,103, 70, 22, 58, 75, 78,183,167,238,157,124,147,172,144,
176,161,141, 86, 60, 66,128, 83,156,241, 79, 46,168,198, 41,254,
178, 85,253,237,250,154,133, 88, 35,206, 95,116,252,192, 54,221,
102,218,255,240, 82,106,158,201, 61, 3, 89, 9, 42,155,159, 93,
166, 80, 50, 34,175,195,100, 99, 26,150, 16,145, 4, 33, 8,189,
121, 64, 77, 72,208,245,130,122,143, 55,105,134, 29,164,185,194,
193,239,101,242, 5,171,126, 11, 74, 59,137,228,108,191,232,139,
6, 24, 81, 20,127, 17, 91, 92,251,151,225,207, 21, 98,113,112,
84,226, 18,214,199,187, 13, 32, 94,220,224,212,247,204,196, 43,
249,236, 45,244,111,182,153,136,129, 90,217,202, 19,165,231, 71,
230,142, 96,227, 62,179,246,114,162, 53,160,215,205,180, 47,109,
44, 38, 31,149,135, 0,216, 52, 63, 23, 37, 69, 39,117,146,184,
163,200,222,235,248,243,219, 10,152,131,123,229,203, 76,120,209
};
// Seed the hash values based on the first character.
Hash.c[0] = bTranslate[ *lpsz];
Hash.c[1] = bTranslate[(*lpsz+1) & 255];
Hash.c[2] = bTranslate[(*lpsz+2) & 255];
Hash.c[3] = bTranslate[(*lpsz+3) & 255];
Hash.dw += dwAddedHash;
while (*++lpsz)
{
// Allow URLs differing only by trailing slash to collide.
if (lpsz[0] == '/' && lpsz[1] == 0)
break;
Hash2.c[0] = Hash.c[0] ^ *lpsz;
Hash2.c[1] = Hash.c[1] ^ *lpsz;
Hash2.c[2] = Hash.c[2] ^ *lpsz;
Hash2.c[3] = Hash.c[3] ^ *lpsz;
Hash.c[0] = bTranslate[Hash2.c[0]];
Hash.c[1] = bTranslate[Hash2.c[1]];
Hash.c[2] = bTranslate[Hash2.c[2]];
Hash.c[3] = bTranslate[Hash2.c[3]];
}
return Hash.dw;
}
//
// HashLookupItem support functions specific to urlcache:
// AllocTable
// IsMatch
//
PRIVATE HASH_FILEMAP_ENTRY* AllocTable
(LPVOID pAllocObj, LPBYTE* ppBase, LPDWORD* ppdwOffset)
{
// Save the offset to the table offset.
DWORD_PTR dpOffsetToTableOffset = (LPBYTE)*ppdwOffset - *ppBase; // 64BIT
// Ask for BYTES_PER_PAGE instead of BYTES_PER_TABLE
// so the allocator knows to align on a page boundary.
INET_ASSERT (BYTES_PER_PAGE >= BYTES_PER_TABLE);
MEMMAP_FILE* pmmf = (MEMMAP_FILE*) pAllocObj;
HASH_FILEMAP_ENTRY* pTable =
(HASH_FILEMAP_ENTRY *) pmmf->AllocateEntry (BYTES_PER_PAGE);
if (!pTable)
return NULL;
INET_ASSERT (! (((LPBYTE) pTable - *pmmf->GetHeapStart()) & (BYTES_PER_PAGE-1)) );
// Chain new table to previous table.
*ppBase = *pmmf->GetHeapStart();
*ppdwOffset = (DWORD*) (*ppBase + dpOffsetToTableOffset);
**ppdwOffset = (DWORD) ((LPBYTE)pTable - *ppBase); // 64BIT
// Initialize the header.
pTable->dwSig = SIG_HASH;
pTable->dwNext = 0;
// Fill the rest of the entry with HASH_END
DWORD* pdw = (DWORD *) (pTable + 1);
DWORD cdw = SLOT_COUNT * ITEMS_PER_BUCKET * (sizeof(HASH_ITEM)/sizeof(DWORD));
INET_ASSERT (!(sizeof(HASH_ITEM) % sizeof(DWORD)));
while (cdw--)
*pdw++ = HASH_END;
// Return the new table.
return pTable;
}
//
// IsMatch: determine if hash table item with a matching 32-bit hash value
// is an actual match or return NULL if a collision.
//
PRIVATE HASH_ITEM* URL_CONTAINER::IsMatch
(HASH_ITEM *pItem, LPCSTR pszKey, DWORD dwFlags)
{
MEMMAP_FILE* pmmf = _UrlObjStorage;
dwFlags &= (LOOKUP_BIT_REDIR | LOOKUP_BIT_CREATE);
if (pmmf->IsBadOffset (pItem->dwOffset))
{
// Fix up a bad hash table item. This could happen if a thread
// died between allocating a hash table item and setting the offset.
pItem->MarkFree();
return NULL;
}
FILEMAP_ENTRY* pEntry = (FILEMAP_ENTRY*)
(*pmmf->GetHeapStart() + pItem->dwOffset);
switch (pEntry->dwSig)
{
case SIG_URL:
{
// Fail if lookup flags are inconsistent with url entry type.
INET_ASSERT (!(pItem->dwHash & HASH_BIT_NOTURL));
// Get pointer to URL.
URL_FILEMAP_ENTRY *pUrlEntry = (URL_FILEMAP_ENTRY *) pEntry;
LPSTR pszUrl = ((LPSTR) pUrlEntry) + pUrlEntry->UrlNameOffset;
LPCSTR pszKey2 = pszKey, pszUrl2 = pszUrl;
while ( *pszKey2 && *pszUrl2 && *pszKey2 == *pszUrl2 )
{
pszKey2++;
pszUrl2++;
}
if (!*pszKey2 && ! *pszUrl2)
{
// Found exact match.
if (dwFlags == LOOKUP_REDIR_CREATE)
{
// We are have a cache entry for a URL which is now
// redirecting. Delete the cache entry.
DeleteUrlEntry (pUrlEntry, pItem, SIG_DELETE);
return NULL;
}
return pItem;
}
// If redirects allowed, check for trailing slash match.
if ((dwFlags == LOOKUP_URL_TRANSLATE)
&& (pItem->dwHash & HASH_BIT_REDIR))
{
DWORD cbUrl = strlen (pszUrl);
DWORD cbKey = strlen (pszKey);
INET_ASSERT (cbUrl && pszUrl[cbUrl - 1] == '/');
if (cbUrl == (cbKey + 1) && !memcmp (pszUrl, pszKey, cbKey))
return pItem;
}
return NULL;
}
case SIG_REDIR:
{
// When online, filter out offline redirect entries.
if (dwFlags == LOOKUP_URL_NOCREATE)
return NULL;
// Check that redirect URL matches exactly.
REDIR_FILEMAP_ENTRY* pRedir = (REDIR_FILEMAP_ENTRY *) pEntry;
if (lstrcmp (pszKey, pRedir->szUrl))
return NULL;
switch (dwFlags)
{
case LOOKUP_URL_CREATE:
// We are creating a new entry for a URL that once
// redirected. Delete the stale redirect entry.
pmmf->FreeEntry (pRedir);
pItem->MarkFree();
return NULL;
case LOOKUP_REDIR_CREATE:
// Return the redirect item if we're looking for it.
return pItem;
case LOOKUP_URL_TRANSLATE:
// Otherwise, translate through the redirect item.
pItem = (HASH_ITEM *)
(*pmmf->GetHeapStart() + pRedir->dwItemOffset);
// Perform some consistency checks.
if (pItem->dwHash & HASH_BIT_NOTURL)
return NULL; // not an URL entry
if ((pItem->dwHash & ~SLOT_MASK) != pRedir->dwHashValue)
return NULL; // not a matching URL entry
return pItem;
default:
INET_ASSERT (FALSE);
}
}
default:
{
// Fix up a bad hash table entry. This can happen if a thread
// died between allocating a hash table item and setting the offset.
pItem->MarkFree();
return NULL;
}
}
}
//
// HashFindItem: finds a matching entry or else the first free slot
//
BOOL URL_CONTAINER::HashFindItem
(LPCSTR pszKey, DWORD dwFlags, HASH_ITEM** ppItem)
{
INET_ASSERT(!((dwFlags & LOOKUP_URL_DONT_FOLLOW) && (dwFlags & LOOKUP_BIT_CREATE)));
DWORD dwFind = 0;
BOOL fLookAgain = !(dwFlags & LOOKUP_URL_DONT_FOLLOW) && GlobalIdentity;
again:
LPVOID pAllocObj = (LPVOID) _UrlObjStorage;
LPBYTE pBase = *_UrlObjStorage->GetHeapStart();
LPDWORD pdwTableOffset = _UrlObjStorage->GetPtrToHashTableOffset();
// Scan flags.
BOOL fCreate = dwFlags & LOOKUP_BIT_CREATE;
HASH_ITEM* pFree = NULL;
DWORD nBlock = 0;
// Hash the URL and calculate the slot.
DWORD dwHash = HashKey(pszKey, dwFind);
DWORD iSlot = dwHash & SLOT_MASK;
dwHash &= ~SLOT_MASK;
// Walk through the list of hash tables.
while (*pdwTableOffset && !_UrlObjStorage->IsBadOffset(*pdwTableOffset))
{
// Calculate offset to next hash table and validate signature.
HASH_FILEMAP_ENTRY* pTable =
(HASH_FILEMAP_ENTRY*) (pBase + *pdwTableOffset);
if (pTable->dwSig != SIG_HASH || pTable->nBlock != nBlock++)
break;
// Calculate offset to bucket in this table.
HASH_ITEM* pItem = ((HASH_ITEM*) (pTable + 1)) + iSlot * ITEMS_PER_BUCKET;
// Scan the bucket.
for (DWORD iSeat=0; iSeat<ITEMS_PER_BUCKET; iSeat++, pItem++)
{
// No reserved bits should ever be set on an item.
INET_ASSERT (!(pItem->dwHash & HASH_BIT_RESERVED));
switch (pItem->dwHash)
{
case HASH_FREE: // free item but more items might follow
{
INET_ASSERT (!(pItem->dwHash & ~SLOT_MASK));
// If caller wants a free item, record the first one we find.
if (!pFree && fCreate)
pFree = pItem;
}
continue;
case HASH_END: // first previously unused free item; no more to follow
{
INET_ASSERT (!(pItem->dwHash & ~SLOT_MASK));
if (!fCreate)
*ppItem = NULL;
else
{
// Hand out the first free slot.
if (pFree)
{
// Invalidate offset in case caller neglects to set it.
pFree->dwOffset = HASH_END;
*ppItem = pFree;
}
else
{
// The first free slot has never been used before.
INET_ASSERT (pItem->dwOffset == HASH_END);
*ppItem = pItem;
}
(*ppItem)->dwHash = dwHash;
}
}
return FALSE;
default:
{
// Check if the key matches.
if (dwHash == (pItem->dwHash & ~SLOT_MASK))
{
if (dwFlags & INTERNET_CACHE_FLAG_ALLOW_COLLISIONS)
{
*ppItem = pItem;
return TRUE;
}
HASH_ITEM* pItem2 = IsMatch(pItem, pszKey, dwFlags);
if (pItem2)
{
LPURL_FILEMAP_ENTRY pEntry =
(URL_FILEMAP_ENTRY*)(*(((MEMMAP_FILE*)_UrlObjStorage)->GetHeapStart())
+ pItem2->dwOffset);
// This will check for a ~U: header or IDENTITY_CACHE_ENTRY
// We use the first for compatibility with Wininet5
// We use IDENTITY_CACHE_ENTRY for entries we wish to hide from Wininet5
if ((pEntry->dwSig==SIG_URL)
&& (!(dwFlags & LOOKUP_URL_DONT_FOLLOW)
&& ((pEntry->CacheEntryType & IDENTITY_CACHE_ENTRY)
|| IsPerUserEntry(pEntry))))
{
// We'll search again for an entry corresponding to GlobalIdentity
if (fLookAgain)
{
fLookAgain = FALSE;
dwFind = GlobalIdentity;
goto again;
}
// Guarantee that this is what we want
if (pEntry->GetIdentity()!=GlobalIdentity)
{
continue;
}
// If we're looking for an identity-0 cache entry
// and there is no filename, we need to do the following:
// 1. if we're trying to create an entry, then return this
// 2. otherwise, say No, the entry is not present
if (!pEntry->InternalFileNameOffset && !fCreate)
{
*ppItem = NULL;
return FALSE;
}
}
*ppItem = pItem2;
return TRUE;
}
}
}
continue;
} // end switch
} // end for loop to scan seats in bucket
// Follow the link to the next table.
pdwTableOffset = &pTable->dwNext;
} // end while (*pdwTableOffset)
// If we've encountered a corrupt table, we'll have to recover
if (*pdwTableOffset)
{
INET_ASSERT(FALSE);
*pdwTableOffset = 0;
}
// We are out a buckets, so an item hasn't been found.
if (fCreate && !pFree)
{
// Caller wanted a free item but we didn't find one.
HASH_FILEMAP_ENTRY* pTable = AllocTable
(pAllocObj, &pBase, &pdwTableOffset);
//////////////////////////////////////////////////////////////////////
// WARNING: the file might have grown and remapped, so any pointers //
// hereafter must be recalculated by offsets from the new base. //
//////////////////////////////////////////////////////////////////////
if (pTable)
{
pTable->nBlock = nBlock;
// Calculate next free slot.
pFree = ((HASH_ITEM*) (pTable + 1)) + iSlot * ITEMS_PER_BUCKET;
INET_ASSERT (pFree->dwHash == HASH_END);
INET_ASSERT (pFree->dwOffset == HASH_END);
}
}
// Return free item if desired and indicate no item found.
if (pFree)
{
INET_ASSERT (fCreate);
pFree->dwHash = dwHash;
pFree->dwOffset = HASH_END; // invalid in case caller neglects to set it
}
*ppItem = pFree;
return FALSE;
}
//
// HashFindNextItem: scans the table for the next valid URL item
//
PUBLIC
HASH_ITEM*
HashGetNextItem
(
IN LPVOID pAllocObj, // allocator object
IN LPBYTE pBase, // base for all offsets
IN OUT LPDWORD pdwItemOffset, // current item offset
IN DWORD dwFlags // include redirects?
)
{
INET_ASSERT (!(dwFlags & ~LOOKUP_BIT_REDIR));
// Check if there if the hash table is empty (or we are at the end already.)
if (!*pdwItemOffset)
return NULL;
HASH_ITEM* pItem = (HASH_ITEM*) (pBase + *pdwItemOffset);
// Calculate current table offset, assuming it's the previous page boundary.
INET_ASSERT (BYTES_PER_TABLE <= BYTES_PER_PAGE);
HASH_FILEMAP_ENTRY* pTable =
(HASH_FILEMAP_ENTRY*) (((DWORD_PTR)pItem) & ~(BYTES_PER_PAGE - 1));
// Advance item pointer to next location.
if (pItem == (HASH_ITEM*) pTable)
pItem = (HASH_ITEM*) (pTable + 1); // first location in table
else
pItem++; // next location in table
do // Scan the list of tables.
{
if (pTable->dwSig != SIG_HASH)
break;
// Scan the current table.
for (; (LPBYTE) pItem < ((LPBYTE) pTable) + BYTES_PER_TABLE; pItem++)
{
// No reserved bits should be set.
INET_ASSERT (!(pItem->dwHash & HASH_BIT_RESERVED));
if (!(pItem->dwHash & HASH_BIT_NOTURL)
|| (dwFlags /* & LOOKUP_BIT_REDIR */)
&& ((pItem->dwHash & HASH_FLAG_MASK) == HASH_REDIR))
{
// Found a valid entry.
*pdwItemOffset = (DWORD) ((LPBYTE)pItem - pBase); // 64BIT
return pItem;
}
}
// Follow the link to the next table.
if (!pTable->dwNext)
pTable = NULL;
else
{
// Validate the table signature and sequence number.
DWORD nBlock = pTable->nBlock;
pTable = (HASH_FILEMAP_ENTRY*) (pBase + pTable->dwNext);
if (pTable->dwSig != SIG_HASH || pTable->nBlock != nBlock + 1)
pTable = NULL;
// Set pointer to first location in table.
pItem = (HASH_ITEM*) (pTable + 1);
}
}
while (pTable);
// We reached the end of the last table.
*pdwItemOffset = 0;
return NULL;
}