freespace.c

PostgreSQL7.4.6 for Linux

			}
		}

		pfree(data);
	}

read_failed:

	/* Clean up */
	LWLockRelease(FreeSpaceLock);

	FreeFile(fp);

	/* Remove cache file before it can become stale; see notes above */
	unlink(cachefilename);
}


/*
 * Internal routines.  These all assume the caller holds the FreeSpaceLock.
 */

/*
 * Lookup a relation in the hash table.  If not present, return NULL.
 *
 * The relation's position in the LRU list is not changed.
 */
static FSMRelation *
lookup_fsm_rel(RelFileNode *rel)
{
	FSMRelation *fsmrel;

	fsmrel = (FSMRelation *) hash_search(FreeSpaceMap->relHash,
										 (void *) rel,
										 HASH_FIND,
										 NULL);
	if (!fsmrel)
		return NULL;

	return fsmrel;
}

/*
 * Lookup a relation in the hash table, creating an entry if not present.
 *
 * On successful lookup, the relation is moved to the front of the LRU list.
 */
static FSMRelation *
create_fsm_rel(RelFileNode *rel)
{
	FSMRelation *fsmrel;
	bool		found;

	fsmrel = (FSMRelation *) hash_search(FreeSpaceMap->relHash,
										 (void *) rel,
										 HASH_ENTER,
										 &found);
	if (!fsmrel)
		ereport(ERROR,
				(errcode(ERRCODE_OUT_OF_MEMORY),
				 errmsg("out of shared memory")));

	if (!found)
	{
		/* New hashtable entry, initialize it (hash_search set the key) */
		fsmrel->isIndex = false;	/* until we learn different */
		fsmrel->avgRequest = INITIAL_AVERAGE;
		fsmrel->lastPageCount = 0;
		fsmrel->firstChunk = -1;	/* no space allocated */
		fsmrel->storedPages = 0;
		fsmrel->nextPage = 0;

		/* Discard lowest-priority existing rel, if we are over limit */
		if (FreeSpaceMap->numRels >= MaxFSMRelations)
			delete_fsm_rel(FreeSpaceMap->usageListTail);

		/* Add new entry at front of LRU list */
		link_fsm_rel_usage(fsmrel);
		fsmrel->nextPhysical = NULL;	/* not in physical-storage list */
		fsmrel->priorPhysical = NULL;
		FreeSpaceMap->numRels++;
		/* sumRequests is unchanged because request must be zero */
	}
	else
	{
		/* Existing entry, move to front of LRU list */
		if (fsmrel->priorUsage != NULL)
		{
			unlink_fsm_rel_usage(fsmrel);
			link_fsm_rel_usage(fsmrel);
		}
	}

	return fsmrel;
}

/*
 * Remove an existing FSMRelation entry.
 */
static void
delete_fsm_rel(FSMRelation *fsmrel)
{
	FSMRelation *result;

	FreeSpaceMap->sumRequests -= fsm_calc_request(fsmrel);
	unlink_fsm_rel_usage(fsmrel);
	unlink_fsm_rel_storage(fsmrel);
	FreeSpaceMap->numRels--;
	result = (FSMRelation *) hash_search(FreeSpaceMap->relHash,
										 (void *) &(fsmrel->key),
										 HASH_REMOVE,
										 NULL);
	if (!result)
		elog(ERROR, "FreeSpaceMap hashtable corrupted");
}

/*
 * Reallocate space for a FSMRelation.
 *
 * This is shared code for RecordRelationFreeSpace and RecordIndexFreeSpace.
 * The return value is the actual new allocation, in chunks.
 */
static int
realloc_fsm_rel(FSMRelation *fsmrel, int nPages, bool isIndex)
{
	int			myRequest;
	int			myAlloc;
	int			curAlloc;

	/*
	 * Delete any existing entries, and update request status.
	 */
	fsmrel->storedPages = 0;
	FreeSpaceMap->sumRequests -= fsm_calc_request(fsmrel);
	fsmrel->lastPageCount = nPages;
	fsmrel->isIndex = isIndex;
	myRequest = fsm_calc_request(fsmrel);
	FreeSpaceMap->sumRequests += myRequest;
	myAlloc = fsm_calc_target_allocation(myRequest);

	/*
	 * Need to reallocate space if (a) my target allocation is more than
	 * my current allocation, AND (b) my actual immediate need
	 * (myRequest+1 chunks) is more than my current allocation. Otherwise
	 * just store the new data in-place.
	 */
	curAlloc = fsm_current_allocation(fsmrel);
	if (myAlloc > curAlloc && (myRequest + 1) > curAlloc && nPages > 0)
	{
		/* Remove entry from storage list, and compact */
		unlink_fsm_rel_storage(fsmrel);
		compact_fsm_storage();
		/* Reattach to end of storage list */
		link_fsm_rel_storage(fsmrel);
		/* And allocate storage */
		fsmrel->firstChunk = FreeSpaceMap->usedChunks;
		FreeSpaceMap->usedChunks += myAlloc;
		curAlloc = myAlloc;
		/* Watch out for roundoff error */
		if (FreeSpaceMap->usedChunks > FreeSpaceMap->totalChunks)
		{
			FreeSpaceMap->usedChunks = FreeSpaceMap->totalChunks;
			curAlloc = FreeSpaceMap->totalChunks - fsmrel->firstChunk;
		}
	}
	return curAlloc;
}

/*
 * Link a FSMRelation into the LRU list (always at the head).
 */
static void
link_fsm_rel_usage(FSMRelation *fsmrel)
{
	fsmrel->priorUsage = NULL;
	fsmrel->nextUsage = FreeSpaceMap->usageList;
	FreeSpaceMap->usageList = fsmrel;
	if (fsmrel->nextUsage != NULL)
		fsmrel->nextUsage->priorUsage = fsmrel;
	else
		FreeSpaceMap->usageListTail = fsmrel;
}

/*
 * Delink a FSMRelation from the LRU list.
 */
static void
unlink_fsm_rel_usage(FSMRelation *fsmrel)
{
	if (fsmrel->priorUsage != NULL)
		fsmrel->priorUsage->nextUsage = fsmrel->nextUsage;
	else
		FreeSpaceMap->usageList = fsmrel->nextUsage;
	if (fsmrel->nextUsage != NULL)
		fsmrel->nextUsage->priorUsage = fsmrel->priorUsage;
	else
		FreeSpaceMap->usageListTail = fsmrel->priorUsage;

	/*
	 * We don't bother resetting fsmrel's links, since it's about to be
	 * deleted or relinked at the head.
	 */
}

/*
 * Link a FSMRelation into the storage-order list (always at the tail).
 */
static void
link_fsm_rel_storage(FSMRelation *fsmrel)
{
	fsmrel->nextPhysical = NULL;
	fsmrel->priorPhysical = FreeSpaceMap->lastRel;
	if (FreeSpaceMap->lastRel != NULL)
		FreeSpaceMap->lastRel->nextPhysical = fsmrel;
	else
		FreeSpaceMap->firstRel = fsmrel;
	FreeSpaceMap->lastRel = fsmrel;
}

/*
 * Delink a FSMRelation from the storage-order list, if it's in it.
 */
static void
unlink_fsm_rel_storage(FSMRelation *fsmrel)
{
	if (fsmrel->priorPhysical != NULL || FreeSpaceMap->firstRel == fsmrel)
	{
		if (fsmrel->priorPhysical != NULL)
			fsmrel->priorPhysical->nextPhysical = fsmrel->nextPhysical;
		else
			FreeSpaceMap->firstRel = fsmrel->nextPhysical;
		if (fsmrel->nextPhysical != NULL)
			fsmrel->nextPhysical->priorPhysical = fsmrel->priorPhysical;
		else
			FreeSpaceMap->lastRel = fsmrel->priorPhysical;
	}
	/* mark as not in list, since we may not put it back immediately */
	fsmrel->nextPhysical = NULL;
	fsmrel->priorPhysical = NULL;
	/* Also mark it as having no storage */
	fsmrel->firstChunk = -1;
	fsmrel->storedPages = 0;
}

/*
 * Look to see if a page with at least the specified amount of space is
 * available in the given FSMRelation.	If so, return its page number,
 * and advance the nextPage counter so that the next inquiry will return
 * a different page if possible; also update the entry to show that the
 * requested space is not available anymore.  Return InvalidBlockNumber
 * if no success.
 */
static BlockNumber
find_free_space(FSMRelation *fsmrel, Size spaceNeeded)
{
	FSMPageData *info;
	int			pagesToCheck,	/* outer loop counter */
				pageIndex;		/* current page index */

	if (fsmrel->isIndex)
		elog(ERROR, "find_free_space called for an index relation");
	info = (FSMPageData *)
		(FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
	pageIndex = fsmrel->nextPage;
	/* Last operation may have left nextPage pointing past end */
	if (pageIndex >= fsmrel->storedPages)
		pageIndex = 0;

	for (pagesToCheck = fsmrel->storedPages; pagesToCheck > 0; pagesToCheck--)
	{
		FSMPageData *page = info + pageIndex;
		Size		spaceAvail = FSMPageGetSpace(page);

		/* Check this page */
		if (spaceAvail >= spaceNeeded)
		{
			/*
			 * Found what we want --- adjust the entry, and update
			 * nextPage.
			 */
			FSMPageSetSpace(page, spaceAvail - spaceNeeded);
			fsmrel->nextPage = pageIndex + 1;
			return FSMPageGetPageNum(page);
		}
		/* Advance pageIndex, wrapping around if needed */
		if (++pageIndex >= fsmrel->storedPages)
			pageIndex = 0;
	}

	return InvalidBlockNumber;	/* nothing found */
}

/*
 * As above, but for index case --- we only deal in whole pages.
 */
static BlockNumber
find_index_free_space(FSMRelation *fsmrel)
{
	IndexFSMPageData *info;
	BlockNumber result;

	/*
	 * If isIndex isn't set, it could be that RecordIndexFreeSpace() has
	 * never yet been called on this relation, and we're still looking at
	 * the default setting from create_fsm_rel().  If so, just act as
	 * though there's no space.
	 */
	if (!fsmrel->isIndex)
	{
		if (fsmrel->storedPages == 0)
			return InvalidBlockNumber;
		elog(ERROR, "find_index_free_space called for a non-index relation");
	}

	/*
	 * For indexes, there's no need for the nextPage state variable; we
	 * just remove and return the first available page.  (We could save
	 * cycles here by returning the last page, but it seems better to
	 * encourage re-use of lower-numbered pages.)
	 */
	if (fsmrel->storedPages <= 0)
		return InvalidBlockNumber;		/* no pages available */
	info = (IndexFSMPageData *)
		(FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
	result = IndexFSMPageGetPageNum(info);
	fsmrel->storedPages--;
	memmove(info, info + 1, fsmrel->storedPages * sizeof(IndexFSMPageData));
	return result;
}

/*
 * fsm_record_free_space - guts of RecordFreeSpace operation (now only
 * provided as part of RecordAndGetPageWithFreeSpace).
 */
static void
fsm_record_free_space(FSMRelation *fsmrel, BlockNumber page, Size spaceAvail)
{
	int			pageIndex;

	if (fsmrel->isIndex)
		elog(ERROR, "fsm_record_free_space called for an index relation");
	if (lookup_fsm_page_entry(fsmrel, page, &pageIndex))
	{
		/* Found an existing entry for page; update it */
		FSMPageData *info;

		info = (FSMPageData *)
			(FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
		info += pageIndex;
		FSMPageSetSpace(info, spaceAvail);
	}
	else
	{
		/*
		 * No existing entry; ignore the call.	We used to add the page to
		 * the FSM --- but in practice, if the page hasn't got enough
		 * space to satisfy the caller who's kicking it back to us, then
		 * it's probably uninteresting to everyone else as well.
		 */
	}
}

/*
 * Look for an entry for a specific page (block number) in a FSMRelation.
 * Returns TRUE if a matching entry exists, else FALSE.
 *
 * The output argument *outPageIndex is set to indicate where the entry exists
 * (if TRUE result) or could be inserted (if FALSE result).
 */
static bool
lookup_fsm_page_entry(FSMRelation *fsmrel, BlockNumber page,
					  int *outPageIndex)
{
	/* Check for empty relation */
	if (fsmrel->storedPages <= 0)
	{
		*outPageIndex = 0;
		return false;
	}

	/* Do binary search */
	if (fsmrel->isIndex)
	{
		IndexFSMPageData *info;
		int			low,
					high;

		info = (IndexFSMPageData *)
			(FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
		low = 0;
		high = fsmrel->storedPages - 1;
		while (low <= high)
		{
			int			middle;
			BlockNumber probe;

			middle = low + (high - low) / 2;
			probe = IndexFSMPageGetPageNum(info + middle);
			if (probe == page)
			{
				*outPageIndex = middle;
				return true;
			}
			else if (probe < page)
				low = middle + 1;
			else
				high = middle - 1;
		}
		*outPageIndex = low;
		return false;
	}
	else
	{
		FSMPageData *info;
		int			low,
					high;

		info = (FSMPageData *)
			(FreeSpaceMap->arena + fsmrel->firstChunk * CHUNKBYTES);
		low = 0;
		high = fsmrel->storedPages - 1;
		while (low <= high)
		{
			int			middle;
			BlockNumber probe;

			middle = low + (high - low) / 2;
			probe = FSMPageGetPageNum(info + middle);
			if (probe == page)
			{
				*outPageIndex = middle;
				return true;
			}
			else if (probe < page)
				low = middle + 1;
			else
				high = middle - 1;
		}
		*outPageIndex = low;
		return false;
	}
}

/*
 * Re-pack the FSM storage arena, dropping data if necessary to meet the
 * current allocation target for each relation.  At conclusion, all available
 * space in the arena will be coalesced at the end.
 */
static void
compact_fsm_storage(void)
{
	int			nextChunkIndex = 0;
	bool		did_push = false;
	FSMRelation *fsmrel;

	for (fsmrel = FreeSpaceMap->firstRel;
		 fsmrel != NULL;
		 fsmrel = fsmrel->nextPhysical)
	{
		int			newAlloc;
		int			newAllocPages;
		int			newChunkIndex;
		int			oldChunkIndex;
		int			curChunks;
		char	   *newLocation;
		char	   *oldLocation;

		/*
		 * Calculate target allocation, make sure we don't overrun due to
		 * roundoff error
		 */
		newAlloc = fsm_calc_target_allocation(fsm_calc_request(fsmrel));