Hello hackers,

I wonder what the PageGetMaxOffsetNumber macro is supposed to do (in a
btree index page)?

The scenario is the following:  I need to get the pointer to a btree
page (leaf or internal) in its parent page, to call _bt_itemdel on it.
The only thing I can think of is to use its parent link and then iterate
in every OffsetNumber to see which item points down to the page I'm
looking for.  I think the gotcha here is that the parent page can split
and I may have to walk right in order to find the new parent (Is this
right?  Can the parent go someplace else?)

I iterate over the elements of the parent page in a for loop, and the
upper bound is rarely reached because the item is found.  However
sometimes the item isn't found, and PageGetItem fails its assertion
because the item isn't used (LP_USED).  I have found that
PageGetMaxOffsetNumber (the upper bound) returns a consistent value
that's far too high (4294967291, 0xFFFFFFFB) and therefore the for loop
eventually falls out of bounds.


The btree freelist patch is "almost ready" (which means it works in the
trivial cases I've tested and there are some corner cases I haven't
even covered), however I am stuck on this.  Can anyone give me a light?
Maybe there's another way to get at the pointer to a page in its parent?

-- 
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"Crear es tan dificil como ser libre" (Elsa Triolet)

Sun, 15 Dec 2002 23:49:57 -0300
Alvaro Herrera <alvherre@dcc.uchile.cl>
PageGetMaxOffsetNumber
On Sun, Dec 15, 2002 at 11:49:57PM -0300, Alvaro Herrera wrote:

> I iterate over the elements of the parent page in a for loop, and the
> upper bound is rarely reached because the item is found.  However
> sometimes the item isn't found, and PageGetItem fails its assertion
> because the item isn't used (LP_USED).  I have found that
> PageGetMaxOffsetNumber (the upper bound) returns a consistent value
> that's far too high (4294967291, 0xFFFFFFFB) and therefore the for loop
> eventually falls out of bounds.

FWIW, the code that is supposed to do this (and appears to work fine on
most cases) is the following.  buf is the page I'm going to free and
pblkno is the BlockNumber of its parent as seen in btpo_parent.

/*
 * Delete the pointer to a child page.  If the parent page is empty after
 * the deletion, delete the pointer from its parent too.
 */
static void
_bt_deletefromparent(Relation rel, BlockNumber pblkno, Buffer buf)
{
	Buffer			pbuf;
	OffsetNumber	offnum;
	Page			ppage;
	BTPageOpaque	pop;
	BlockNumber		blkno = BufferGetBlockNumber(buf),
					max;

	pbuf = _bt_getbuf(rel, pblkno, BT_WRITE);
	Assert(!BufferIsInvalid(pbuf));

	ppage = BufferGetPage(pbuf);
	pop = (BTPageOpaque) PageGetSpecialPointer(ppage);

	/*
	 * Repeat until the correct parent page is found.	Splits may
	 * cause the parent page to move right.
	 */
	for (;;)
	{
		BlockNumber	next;

		/* Make sure no one else tries to look at the page. */
		LockBuffer(pbuf, BUFFER_LOCK_UNLOCK);
		LockBufferForCleanup(pbuf);
		max = PageGetMaxOffsetNumber(pop);

		/*
		 * Look every offset of the page for the item pointing to the
		 * dead page.
		 */
		for (offnum = FirstOffsetNumber; offnum <= max; offnum++)
		{
			BTItem			item;
			ItemPointer		iptr;

			item = (BTItem) PageGetItem(ppage, PageGetItemId(ppage, offnum));
			iptr  = &(item->bti_itup.t_tid);
			if (ItemPointerGetBlockNumber(iptr) == blkno)
			{
				/* Ok, we found the page.  Now delete the pointer. */
				ItemPointer		iptrd = palloc(SizeOfIptrData);

				ItemPointerSet(iptrd, pblkno, offnum);
				_bt_itemdel(rel, pbuf, iptrd);
				_bt_wrtnorelbuf(rel, pbuf);
				LockBuffer(pbuf, BUFFER_LOCK_UNLOCK);

				/*
				 * If the parent page is empty after this deletion,
				 * mark it dead and free it too.
				 */
				if (_bt_pageisempty(ppage))
				{
					pop->btpo_flags |= BTP_DEAD;
					_bt_processdead(rel, pbuf);
				}
				ReleaseBuffer(pbuf);
				return;
			}
		}

		/*
		 * If we just finished scanning the rightmost page of the upper level,
		 * there's some wrong.
		 */
		if (P_RIGHTMOST(pop))
			elog(ERROR, "Unable to find parent page!");

		/* Oops, the parent was split.	Check its right sibling. */
		next = pop->btpo_next;
		_bt_relbuf(rel, pbuf);
		pbuf = _bt_getbuf(rel, next, BT_WRITE);
		ppage = BufferGetPage(pbuf);
		pop = (BTPageOpaque) PageGetSpecialPointer(ppage);
	}
}

-- 
Alvaro Herrera (<alvherre[a]dcc.uchile.cl>)
"Aprende a avergonzarte mas ante ti que ante los demas" (Democrito)

Mon, 16 Dec 2002 00:05:20 -0300
Alvaro Herrera <alvherre@dcc.uchile.cl>
Re: PageGetMaxOffsetNumber
On Sun, 15 Dec 2002 23:49:57 -0300, Alvaro Herrera
<alvherre@dcc.uchile.cl> wrote:
>PageGetMaxOffsetNumber (the upper bound) returns a consistent value
>that's far too high (4294967291, 0xFFFFFFFB)

Alvaro, maybe this comment from bufpage.h can shed some light on it?

/*
 * PageGetMaxOffsetNumber
 *  Returns the maximum offset number used by the given page.
 *  Since offset numbers are 1-based, this is also the number
 *  of items on the page.
 *
 *  NOTE: to ensure sane behavior if the page is not initialized
 *  (pd_lower == 0), cast the unsigned values to int before dividing.
 *  That way we get -1 or so, not a huge positive number...
 */

#define PageGetMaxOffsetNumber(page) \
  (((int) (((PageHeader) (page))->pd_lower - SizeOfPageHeaderData)) \
   / ((int) sizeof(ItemIdData)))

0xFFFFFFFB is -5.
With SizeOfPageHeaderData == 20 and sizeof(ItemIdData) == 4 you get
this result for pd_lower == 0.

Servus
 Manfred

Mon, 16 Dec 2002 09:58:55 +0100
Manfred Koizar <mkoi-pg@aon.at>
Re: PageGetMaxOffsetNumber
Alvaro Herrera <alvherre@dcc.uchile.cl> writes:
> 	ppage = BufferGetPage(pbuf);
> 	pop = (BTPageOpaque) PageGetSpecialPointer(ppage);

> 		max = PageGetMaxOffsetNumber(pop);

I believe you want PageGetMaxOffsetNumber(ppage) ...

			regards, tom lane

Mon, 16 Dec 2002 13:21:40 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: PageGetMaxOffsetNumber 