hashpage.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * hashpage.c
 *	  Hash table page management code for the Postgres hash access method
 *
 * Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $Header: /usr/local/cvsroot/pgsql/src/backend/access/hash/hashpage.c,v 1.20.2.1 1999/08/02 05:56:34 scrappy Exp $
 *
 * NOTES
 *	  Postgres hash pages look like ordinary relation pages.  The opaque
 *	  data at high addresses includes information about the page including
 *	  whether a page is an overflow page or a true bucket, the block
 *	  numbers of the preceding and following pages, and the overflow
 *	  address of the page if it is an overflow page.
 *
 *	  The first page in a hash relation, page zero, is special -- it stores
 *	  information describing the hash table; it is referred to as teh
 *	  "meta page." Pages one and higher store the actual data.
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/genam.h"
#include "access/hash.h"
#include "miscadmin.h"


static void _hash_setpagelock(Relation rel, BlockNumber blkno, int access);
static void _hash_unsetpagelock(Relation rel, BlockNumber blkno, int access);
static void _hash_splitpage(Relation rel, Buffer metabuf, Bucket obucket, Bucket nbucket);

/*
 *	We use high-concurrency locking on hash indices.  There are two cases in
 *	which we don't do locking.  One is when we're building the index.
 *	Since the creating transaction has not committed, no one can see
 *	the index, and there's no reason to share locks.  The second case
 *	is when we're just starting up the database system.  We use some
 *	special-purpose initialization code in the relation cache manager
 *	(see utils/cache/relcache.c) to allow us to do indexed scans on
 *	the system catalogs before we'd normally be able to.  This happens
 *	before the lock table is fully initialized, so we can't use it.
 *	Strictly speaking, this violates 2pl, but we don't do 2pl on the
 *	system catalogs anyway.
 */


#define USELOCKING		(!BuildingHash && !IsInitProcessingMode())


/*
 *	_hash_metapinit() -- Initialize the metadata page of a hash index,
 *				the two buckets that we begin with and the initial
 *				bitmap page.
 */
void
_hash_metapinit(Relation rel)
{
	HashMetaPage metap;
	HashPageOpaque pageopaque;
	Buffer		metabuf;
	Buffer		buf;
	Page		pg;
	int			nbuckets;
	uint32		nelem;			/* number elements */
	uint32		lg2nelem;		/* _hash_log2(nelem)   */
	uint32		nblocks;
	uint16		i;

	/* can't be sharing this with anyone, now... */
	if (USELOCKING)
		LockRelation(rel, AccessExclusiveLock);

	if ((nblocks = RelationGetNumberOfBlocks(rel)) != 0)
	{
		elog(ERROR, "Cannot initialize non-empty hash table %s",
			 RelationGetRelationName(rel));
	}

	metabuf = _hash_getbuf(rel, HASH_METAPAGE, HASH_WRITE);
	pg = BufferGetPage(metabuf);
	metap = (HashMetaPage) pg;
	_hash_pageinit(pg, BufferGetPageSize(metabuf));

	metap->hashm_magic = HASH_MAGIC;
	metap->hashm_version = HASH_VERSION;
	metap->hashm_nkeys = 0;
	metap->hashm_nmaps = 0;
	metap->hashm_ffactor = DEFAULT_FFACTOR;
	metap->hashm_bsize = BufferGetPageSize(metabuf);
	metap->hashm_bshift = _hash_log2(metap->hashm_bsize);
	for (i = metap->hashm_bshift; i > 0; --i)
	{
		if ((1 << i) < (metap->hashm_bsize -
						(MAXALIGN(sizeof(PageHeaderData)) +
						 MAXALIGN(sizeof(HashPageOpaqueData)))))
			break;
	}
	Assert(i);
	metap->hashm_bmsize = 1 << i;
	metap->hashm_procid = index_getprocid(rel, 1, HASHPROC);

	/*
	 * Make nelem = 2 rather than 0 so that we end up allocating space for
	 * the next greater power of two number of buckets.
	 */
	nelem = 2;
	lg2nelem = 1;				/* _hash_log2(MAX(nelem, 2)) */
	nbuckets = 2;				/* 1 << lg2nelem */

	MemSet((char *) metap->hashm_spares, 0, sizeof(metap->hashm_spares));
	MemSet((char *) metap->hashm_mapp, 0, sizeof(metap->hashm_mapp));

	metap->hashm_spares[lg2nelem] = 2;	/* lg2nelem + 1 */
	metap->hashm_spares[lg2nelem + 1] = 2;		/* lg2nelem + 1 */
	metap->hashm_ovflpoint = 1; /* lg2nelem */
	metap->hashm_lastfreed = 2;

	metap->hashm_maxbucket = metap->hashm_lowmask = 1;	/* nbuckets - 1 */
	metap->hashm_highmask = 3;	/* (nbuckets << 1) - 1 */

	pageopaque = (HashPageOpaque) PageGetSpecialPointer(pg);
	pageopaque->hasho_oaddr = InvalidOvflAddress;
	pageopaque->hasho_prevblkno = InvalidBlockNumber;
	pageopaque->hasho_nextblkno = InvalidBlockNumber;
	pageopaque->hasho_flag = LH_META_PAGE;
	pageopaque->hasho_bucket = -1;

	/*
	 * First bitmap page is at: splitpoint lg2nelem page offset 1 which
	 * turns out to be page 3. Couldn't initialize page 3  until we
	 * created the first two buckets above.
	 */
	if (_hash_initbitmap(rel, metap, OADDR_OF(lg2nelem, 1), lg2nelem + 1, 0))
		elog(ERROR, "Problem with _hash_initbitmap.");

	/* all done */
	_hash_wrtnorelbuf(rel, metabuf);

	/*
	 * initialize the first two buckets
	 */
	for (i = 0; i <= 1; i++)
	{
		buf = _hash_getbuf(rel, BUCKET_TO_BLKNO(i), HASH_WRITE);
		pg = BufferGetPage(buf);
		_hash_pageinit(pg, BufferGetPageSize(buf));
		pageopaque = (HashPageOpaque) PageGetSpecialPointer(pg);
		pageopaque->hasho_oaddr = InvalidOvflAddress;
		pageopaque->hasho_prevblkno = InvalidBlockNumber;
		pageopaque->hasho_nextblkno = InvalidBlockNumber;
		pageopaque->hasho_flag = LH_BUCKET_PAGE;
		pageopaque->hasho_bucket = i;
		_hash_wrtbuf(rel, buf);
	}

	_hash_relbuf(rel, metabuf, HASH_WRITE);

	if (USELOCKING)
		UnlockRelation(rel, AccessExclusiveLock);
}

/*
 *	_hash_getbuf() -- Get a buffer by block number for read or write.
 *
 *		When this routine returns, the appropriate lock is set on the
 *		requested buffer its reference count is correct.
 *
 *		XXX P_NEW is not used because, unlike the tree structures, we
 *		need the bucket blocks to be at certain block numbers.	we must
 *		depend on the caller to call _hash_pageinit on the block if it
 *		knows that this is a new block.
 */
Buffer
_hash_getbuf(Relation rel, BlockNumber blkno, int access)
{
	Buffer		buf;

	if (blkno == P_NEW)
		elog(ERROR, "_hash_getbuf: internal error: hash AM does not use P_NEW");
	switch (access)
	{
		case HASH_WRITE:
		case HASH_READ:
			_hash_setpagelock(rel, blkno, access);
			break;
		default:
			elog(ERROR, "_hash_getbuf: invalid access (%d) on new blk: %s",
				 access, RelationGetRelationName(rel));
			break;
	}
	buf = ReadBuffer(rel, blkno);

	/* ref count and lock type are correct */
	return buf;
}

/*
 *	_hash_relbuf() -- release a locked buffer.
 */
void
_hash_relbuf(Relation rel, Buffer buf, int access)
{
	BlockNumber blkno;

	blkno = BufferGetBlockNumber(buf);

	switch (access)
	{
		case HASH_WRITE:
		case HASH_READ:
			_hash_unsetpagelock(rel, blkno, access);
			break;
		default:
			elog(ERROR, "_hash_relbuf: invalid access (%d) on blk %x: %s",
				 access, blkno, RelationGetRelationName(rel));
	}

	ReleaseBuffer(buf);
}

/*
 *	_hash_wrtbuf() -- write a hash page to disk.
 *
 *		This routine releases the lock held on the buffer and our reference
 *		to it.	It is an error to call _hash_wrtbuf() without a write lock
 *		or a reference to the buffer.
 */
void
_hash_wrtbuf(Relation rel, Buffer buf)
{
	BlockNumber blkno;

	blkno = BufferGetBlockNumber(buf);
	WriteBuffer(buf);
	_hash_unsetpagelock(rel, blkno, HASH_WRITE);
}

/*
 *	_hash_wrtnorelbuf() -- write a hash page to disk, but do not release
 *						 our reference or lock.
 *
 *		It is an error to call _hash_wrtnorelbuf() without a write lock
 *		or a reference to the buffer.
 */
void
_hash_wrtnorelbuf(Relation rel, Buffer buf)
{
	BlockNumber blkno;

	blkno = BufferGetBlockNumber(buf);
	WriteNoReleaseBuffer(buf);
}

Page
_hash_chgbufaccess(Relation rel,
				   Buffer *bufp,
				   int from_access,
				   int to_access)
{
	BlockNumber blkno;

	blkno = BufferGetBlockNumber(*bufp);

	switch (from_access)
	{
		case HASH_WRITE:
			_hash_wrtbuf(rel, *bufp);
			break;
		case HASH_READ:
			_hash_relbuf(rel, *bufp, from_access);
			break;
		default:
			elog(ERROR, "_hash_chgbufaccess: invalid access (%d) on blk %x: %s",
				 from_access, blkno, RelationGetRelationName(rel));
			break;
	}
	*bufp = _hash_getbuf(rel, blkno, to_access);
	return BufferGetPage(*bufp);
}

/*
 *	_hash_pageinit() -- Initialize a new page.
 */
void
_hash_pageinit(Page page, Size size)
{
	Assert(((PageHeader) page)->pd_lower == 0);
	Assert(((PageHeader) page)->pd_upper == 0);
	Assert(((PageHeader) page)->pd_special == 0);

	/*
	 * Cargo-cult programming -- don't really need this to be zero, but
	 * creating new pages is an infrequent occurrence and it makes me feel
	 * good when I know they're empty.
	 */
	MemSet(page, 0, size);

	PageInit(page, size, sizeof(HashPageOpaqueData));
}

static void
_hash_setpagelock(Relation rel,
				  BlockNumber blkno,
				  int access)
{

	if (USELOCKING)
	{
		switch (access)
		{
				case HASH_WRITE:
				LockPage(rel, blkno, ExclusiveLock);
				break;
			case HASH_READ:
				LockPage(rel, blkno, ShareLock);
				break;
			default:
				elog(ERROR, "_hash_setpagelock: invalid access (%d) on blk %x: %s",
					 access, blkno, RelationGetRelationName(rel));
				break;
		}
	}
}

static void
_hash_unsetpagelock(Relation rel,
					BlockNumber blkno,
					int access)
{

	if (USELOCKING)
	{
		switch (access)
		{
				case HASH_WRITE:
				UnlockPage(rel, blkno, ExclusiveLock);
				break;
			case HASH_READ:
				UnlockPage(rel, blkno, ShareLock);