hashovfl.c

关系型数据库 Postgresql 6.5.2

/*-------------------------------------------------------------------------
 *
 * hashovfl.c
 *	  Overflow 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/hashovfl.c,v 1.20.2.1 1999/08/02 05:24:34 scrappy Exp $
 *
 * NOTES
 *	  Overflow pages look like ordinary relation pages.
 *
 *-------------------------------------------------------------------------
 */
#include "postgres.h"

#include "access/hash.h"


static OverflowPageAddress _hash_getovfladdr(Relation rel, Buffer *metabufp);
static uint32 _hash_firstfreebit(uint32 map);

/*
 *	_hash_addovflpage
 *
 *	Add an overflow page to the page currently pointed to by the buffer
 *	argument 'buf'.
 *
 *	*Metabufp has a read lock upon entering the function; buf has a
 *	write lock.
 *
 */
Buffer
_hash_addovflpage(Relation rel, Buffer *metabufp, Buffer buf)
{

	OverflowPageAddress oaddr;
	BlockNumber ovflblkno;
	Buffer		ovflbuf;
	HashMetaPage metap;
	HashPageOpaque ovflopaque;
	HashPageOpaque pageopaque;
	Page		page;
	Page		ovflpage;

	/* this had better be the last page in a bucket chain */
	page = BufferGetPage(buf);
	_hash_checkpage(page, LH_BUCKET_PAGE | LH_OVERFLOW_PAGE);
	pageopaque = (HashPageOpaque) PageGetSpecialPointer(page);
	Assert(!BlockNumberIsValid(pageopaque->hasho_nextblkno));

	metap = (HashMetaPage) BufferGetPage(*metabufp);
	_hash_checkpage((Page) metap, LH_META_PAGE);

	/* allocate an empty overflow page */
	oaddr = _hash_getovfladdr(rel, metabufp);
	if (oaddr == InvalidOvflAddress)
		elog(ERROR, "_hash_addovflpage: problem with _hash_getovfladdr.");
	ovflblkno = OADDR_TO_BLKNO(OADDR_OF(SPLITNUM(oaddr), OPAGENUM(oaddr)));
	Assert(BlockNumberIsValid(ovflblkno));
	ovflbuf = _hash_getbuf(rel, ovflblkno, HASH_WRITE);
	Assert(BufferIsValid(ovflbuf));
	ovflpage = BufferGetPage(ovflbuf);

	/* initialize the new overflow page */
	_hash_pageinit(ovflpage, BufferGetPageSize(ovflbuf));
	ovflopaque = (HashPageOpaque) PageGetSpecialPointer(ovflpage);
	ovflopaque->hasho_prevblkno = BufferGetBlockNumber(buf);
	ovflopaque->hasho_nextblkno = InvalidBlockNumber;
	ovflopaque->hasho_flag = LH_OVERFLOW_PAGE;
	ovflopaque->hasho_oaddr = oaddr;
	ovflopaque->hasho_bucket = pageopaque->hasho_bucket;
	_hash_wrtnorelbuf(rel, ovflbuf);

	/* logically chain overflow page to previous page */
	pageopaque->hasho_nextblkno = ovflblkno;
	_hash_wrtnorelbuf(rel, buf);
	return ovflbuf;
}

/*
 *	_hash_getovfladdr()
 *
 *	Find an available overflow page and return its address.
 *
 *	When we enter this function, we have a read lock on *metabufp which
 *	we change to a write lock immediately. Before exiting, the write lock
 *	is exchanged for a read lock.
 *
 */
static OverflowPageAddress
_hash_getovfladdr(Relation rel, Buffer *metabufp)
{
	HashMetaPage metap;
	Buffer		mapbuf = 0;
	BlockNumber blkno;
	PageOffset	offset;
	OverflowPageAddress oaddr;
	SplitNumber splitnum;
	uint32	   *freep = NULL;
	uint32		max_free;
	uint32		bit;
	uint32		first_page;
	uint32		free_bit;
	uint32		free_page;
	uint32		in_use_bits;
	uint32		i,
				j;

	metap = (HashMetaPage) _hash_chgbufaccess(rel, metabufp, HASH_READ, HASH_WRITE);

	splitnum = metap->OVFL_POINT;
	max_free = metap->SPARES[splitnum];

	free_page = (max_free - 1) >> (metap->hashm_bshift + BYTE_TO_BIT);
	free_bit = (max_free - 1) & (BMPGSZ_BIT(metap) - 1);

	/* Look through all the free maps to find the first free block */
	first_page = metap->LAST_FREED >> (metap->hashm_bshift + BYTE_TO_BIT);
	for (i = first_page; i <= free_page; i++)
	{
		Page		mappage;

		blkno = metap->hashm_mapp[i];
		mapbuf = _hash_getbuf(rel, blkno, HASH_WRITE);
		mappage = BufferGetPage(mapbuf);
		_hash_checkpage(mappage, LH_BITMAP_PAGE);
		freep = HashPageGetBitmap(mappage);
		Assert(freep);

		if (i == free_page)
			in_use_bits = free_bit;
		else
			in_use_bits = BMPGSZ_BIT(metap) - 1;

		if (i == first_page)
		{
			bit = metap->LAST_FREED & (BMPGSZ_BIT(metap) - 1);
			j = bit / BITS_PER_MAP;
			bit = bit & ~(BITS_PER_MAP - 1);
		}
		else
		{
			bit = 0;
			j = 0;
		}
		for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP)
			if (freep[j] != ALL_SET)
				goto found;
	}

	/* No Free Page Found - have to allocate a new page */
	metap->LAST_FREED = metap->SPARES[splitnum];
	metap->SPARES[splitnum]++;
	offset = metap->SPARES[splitnum] -
		(splitnum ? metap->SPARES[splitnum - 1] : 0);

#define OVMSG	"HASH: Out of overflow pages.  Out of luck.\n"

	if (offset > SPLITMASK)
	{
		if (++splitnum >= NCACHED)
			elog(ERROR, OVMSG);
		metap->OVFL_POINT = splitnum;
		metap->SPARES[splitnum] = metap->SPARES[splitnum - 1];
		metap->SPARES[splitnum - 1]--;
		offset = 0;
	}

	/* Check if we need to allocate a new bitmap page */
	if (free_bit == BMPGSZ_BIT(metap) - 1)
	{
		/* won't be needing old map page */

		_hash_relbuf(rel, mapbuf, HASH_WRITE);

		free_page++;
		if (free_page >= NCACHED)
			elog(ERROR, OVMSG);

		/*
		 * This is tricky.	The 1 indicates that you want the new page
		 * allocated with 1 clear bit.	Actually, you are going to
		 * allocate 2 pages from this map.	The first is going to be the
		 * map page, the second is the overflow page we were looking for.
		 * The init_bitmap routine automatically, sets the first bit of
		 * itself to indicate that the bitmap itself is in use.  We would
		 * explicitly set the second bit, but don't have to if we tell
		 * init_bitmap not to leave it clear in the first place.
		 */
		if (_hash_initbitmap(rel, metap, OADDR_OF(splitnum, offset),
							 1, free_page))
			elog(ERROR, "overflow_page: problem with _hash_initbitmap.");
		metap->SPARES[splitnum]++;
		offset++;
		if (offset > SPLITMASK)
		{
			if (++splitnum >= NCACHED)
				elog(ERROR, OVMSG);
			metap->OVFL_POINT = splitnum;
			metap->SPARES[splitnum] = metap->SPARES[splitnum - 1];
			metap->SPARES[splitnum - 1]--;
			offset = 0;
		}
	}
	else
	{

		/*
		 * Free_bit addresses the last used bit.  Bump it to address the
		 * first available bit.
		 */
		free_bit++;
		SETBIT(freep, free_bit);
		_hash_wrtbuf(rel, mapbuf);
	}

	/* Calculate address of the new overflow page */
	oaddr = OADDR_OF(splitnum, offset);
	_hash_chgbufaccess(rel, metabufp, HASH_WRITE, HASH_READ);
	return oaddr;

found:
	bit = bit + _hash_firstfreebit(freep[j]);
	SETBIT(freep, bit);
	_hash_wrtbuf(rel, mapbuf);

	/*
	 * Bits are addressed starting with 0, but overflow pages are
	 * addressed beginning at 1. Bit is a bit addressnumber, so we need to
	 * increment it to convert it to a page number.
	 */

	bit = 1 + bit + (i * BMPGSZ_BIT(metap));
	if (bit >= metap->LAST_FREED)
		metap->LAST_FREED = bit - 1;

	/* Calculate the split number for this page */
	for (i = 0; (i < splitnum) && (bit > metap->SPARES[i]); i++)
		;
	offset = (i ? bit - metap->SPARES[i - 1] : bit);
	if (offset >= SPLITMASK)
		elog(ERROR, OVMSG);

	/* initialize this page */
	oaddr = OADDR_OF(i, offset);
	_hash_chgbufaccess(rel, metabufp, HASH_WRITE, HASH_READ);
	return oaddr;
}

/*
 *	_hash_firstfreebit()
 *
 *	Return the first bit that is not set in the argument 'map'. This
 *	function is used to find an available overflow page within a
 *	splitnumber.
 *
 */
static uint32
_hash_firstfreebit(uint32 map)
{
	uint32		i,
				mask;

	mask = 0x1;
	for (i = 0; i < BITS_PER_MAP; i++)
	{
		if (!(mask & map))
			return i;
		mask = mask << 1;
	}
	return i;
}

/*
 *	_hash_freeovflpage() -
 *
 *	Mark this overflow page as free and return a buffer with
 *	the page that follows it (which may be defined as
 *	InvalidBuffer).
 *
 */
Buffer
_hash_freeovflpage(Relation rel, Buffer ovflbuf)
{
	HashMetaPage metap;
	Buffer		metabuf;
	Buffer		mapbuf;
	BlockNumber prevblkno;
	BlockNumber blkno;
	BlockNumber nextblkno;
	HashPageOpaque ovflopaque;
	Page		ovflpage;
	Page		mappage;
	OverflowPageAddress addr;
	SplitNumber splitnum;
	uint32	   *freep;
	uint32		ovflpgno;
	int32		bitmappage,
				bitmapbit;
	Bucket		bucket;

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