~drizzle-trunk/drizzle/development

/*****************************************************************************

Copyright (c) 1995, 2010, Innobase Oy. All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free Software

Foundation; version 2 of the License.

This program is distributed in the hope that it will be useful, but WITHOUT

ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS

FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with

this program; if not, write to the Free Software Foundation, Inc., 51 Franklin

St, Fifth Floor, Boston, MA 02110-1301 USA

*****************************************************************************/

/******************************************************************//**

@file fsp/fsp0fsp.c

File space management

Created 11/29/1995 Heikki Tuuri

***********************************************************************/

#include "fsp0fsp.h"

#ifdef UNIV_NONINL

#include "fsp0fsp.ic"

#endif

#include "buf0buf.h"

#include "fil0fil.h"

#include "mtr0log.h"

#include "ut0byte.h"

#include "page0page.h"

#include "page0zip.h"

#ifdef UNIV_HOTBACKUP

# include "fut0lst.h"

#else /* UNIV_HOTBACKUP */

# include "sync0sync.h"

# include "fut0fut.h"

# include "srv0srv.h"

# include "ibuf0ibuf.h"

# include "btr0btr.h"

# include "btr0sea.h"

# include "dict0boot.h"

# include "log0log.h"

#endif /* UNIV_HOTBACKUP */

#include "dict0mem.h"

#define FSP_HEADER_OFFSET	FIL_PAGE_DATA	/* Offset of the space header

						within a file page */

/* The data structures in files are defined just as byte strings in C */

typedef	byte	fsp_header_t;

typedef	byte	xdes_t;

/*			SPACE HEADER

			============

File space header data structure: this data structure is contained in the

first page of a space. The space for this header is reserved in every extent

descriptor page, but used only in the first. */

/*-------------------------------------*/

#define FSP_SPACE_ID		0	/* space id */

#define FSP_NOT_USED		4	/* this field contained a value up to

					which we know that the modifications

					in the database have been flushed to

					the file space; not used now */

#define	FSP_SIZE		8	/* Current size of the space in

					pages */

#define	FSP_FREE_LIMIT		12	/* Minimum page number for which the

					free list has not been initialized:

					the pages >= this limit are, by

					definition, free; note that in a

					single-table tablespace where size

					< 64 pages, this number is 64, i.e.,

					we have initialized the space

					about the first extent, but have not

					physically allocted those pages to the

					file */

#define	FSP_SPACE_FLAGS		16	/* table->flags & ~DICT_TF_COMPACT */

#define	FSP_FRAG_N_USED		20	/* number of used pages in the

					FSP_FREE_FRAG list */

#define	FSP_FREE		24	/* list of free extents */

#define	FSP_FREE_FRAG		(24 + FLST_BASE_NODE_SIZE)

					/* list of partially free extents not

					belonging to any segment */

#define	FSP_FULL_FRAG		(24 + 2 * FLST_BASE_NODE_SIZE)

					/* list of full extents not belonging

					to any segment */

#define FSP_SEG_ID		(24 + 3 * FLST_BASE_NODE_SIZE)

					/* 8 bytes which give the first unused

					segment id */

#define FSP_SEG_INODES_FULL	(32 + 3 * FLST_BASE_NODE_SIZE)

					/* list of pages containing segment

					headers, where all the segment inode

					slots are reserved */

#define FSP_SEG_INODES_FREE	(32 + 4 * FLST_BASE_NODE_SIZE)

					/* list of pages containing segment

					headers, where not all the segment

					header slots are reserved */

/*-------------------------------------*/

/* File space header size */

#define	FSP_HEADER_SIZE		(32 + 5 * FLST_BASE_NODE_SIZE)

#define	FSP_FREE_ADD		4	/* this many free extents are added

					to the free list from above

					FSP_FREE_LIMIT at a time */

/*			FILE SEGMENT INODE

			==================

Segment inode which is created for each segment in a tablespace. NOTE: in

purge we assume that a segment having only one currently used page can be

freed in a few steps, so that the freeing cannot fill the file buffer with

bufferfixed file pages. */

typedef	byte	fseg_inode_t;

#define FSEG_INODE_PAGE_NODE	FSEG_PAGE_DATA

					/* the list node for linking

					segment inode pages */

#define FSEG_ARR_OFFSET		(FSEG_PAGE_DATA + FLST_NODE_SIZE)

/*-------------------------------------*/

#define	FSEG_ID			0	/* 8 bytes of segment id: if this is 0,

					it means that the header is unused */

#define FSEG_NOT_FULL_N_USED	8

					/* number of used segment pages in

					the FSEG_NOT_FULL list */

#define	FSEG_FREE		12

					/* list of free extents of this

					segment */

#define	FSEG_NOT_FULL		(12 + FLST_BASE_NODE_SIZE)

					/* list of partially free extents */

#define	FSEG_FULL		(12 + 2 * FLST_BASE_NODE_SIZE)

					/* list of full extents */

#define	FSEG_MAGIC_N		(12 + 3 * FLST_BASE_NODE_SIZE)

					/* magic number used in debugging */

#define	FSEG_FRAG_ARR		(16 + 3 * FLST_BASE_NODE_SIZE)

					/* array of individual pages

					belonging to this segment in fsp

					fragment extent lists */

#define FSEG_FRAG_ARR_N_SLOTS	(FSP_EXTENT_SIZE / 2)

					/* number of slots in the array for

					the fragment pages */

#define	FSEG_FRAG_SLOT_SIZE	4	/* a fragment page slot contains its

					page number within space, FIL_NULL

					means that the slot is not in use */

/*-------------------------------------*/

#define FSEG_INODE_SIZE					\

	(16 + 3 * FLST_BASE_NODE_SIZE			\

	 + FSEG_FRAG_ARR_N_SLOTS * FSEG_FRAG_SLOT_SIZE)

#define FSP_SEG_INODES_PER_PAGE(zip_size)		\

	(((zip_size ? zip_size : UNIV_PAGE_SIZE)	\

	  - FSEG_ARR_OFFSET - 10) / FSEG_INODE_SIZE)

				/* Number of segment inodes which fit on a

				single page */

#define FSEG_MAGIC_N_VALUE	97937874

#define	FSEG_FILLFACTOR		8	/* If this value is x, then if

					the number of unused but reserved

					pages in a segment is less than

					reserved pages * 1/x, and there are

					at least FSEG_FRAG_LIMIT used pages,

					then we allow a new empty extent to

					be added to the segment in

					fseg_alloc_free_page. Otherwise, we

					use unused pages of the segment. */

#define FSEG_FRAG_LIMIT		FSEG_FRAG_ARR_N_SLOTS

					/* If the segment has >= this many

					used pages, it may be expanded by

					allocating extents to the segment;

					until that only individual fragment

					pages are allocated from the space */

#define	FSEG_FREE_LIST_LIMIT	40	/* If the reserved size of a segment

					is at least this many extents, we

					allow extents to be put to the free

					list of the extent: at most

					FSEG_FREE_LIST_MAX_LEN many */

#define	FSEG_FREE_LIST_MAX_LEN	4

/*			EXTENT DESCRIPTOR

			=================

File extent descriptor data structure: contains bits to tell which pages in

the extent are free and which contain old tuple version to clean. */

/*-------------------------------------*/

#define	XDES_ID			0	/* The identifier of the segment

					to which this extent belongs */

#define XDES_FLST_NODE		8	/* The list node data structure

					for the descriptors */

#define	XDES_STATE		(FLST_NODE_SIZE + 8)

					/* contains state information

					of the extent */

#define	XDES_BITMAP		(FLST_NODE_SIZE + 12)

					/* Descriptor bitmap of the pages

					in the extent */

/*-------------------------------------*/

#define	XDES_BITS_PER_PAGE	2	/* How many bits are there per page */

#define	XDES_FREE_BIT		0	/* Index of the bit which tells if

					the page is free */

#define	XDES_CLEAN_BIT		1	/* NOTE: currently not used!

					Index of the bit which tells if

					there are old versions of tuples

					on the page */

/* States of a descriptor */

#define	XDES_FREE		1	/* extent is in free list of space */

#define	XDES_FREE_FRAG		2	/* extent is in free fragment list of

					space */

#define	XDES_FULL_FRAG		3	/* extent is in full fragment list of

					space */

#define	XDES_FSEG		4	/* extent belongs to a segment */

/* File extent data structure size in bytes. */

#define	XDES_SIZE							\

	(XDES_BITMAP + UT_BITS_IN_BYTES(FSP_EXTENT_SIZE * XDES_BITS_PER_PAGE))

/* Offset of the descriptor array on a descriptor page */

#define	XDES_ARR_OFFSET		(FSP_HEADER_OFFSET + FSP_HEADER_SIZE)

#ifndef UNIV_HOTBACKUP

/* Flag to indicate if we have printed the tablespace full error. */

static ibool fsp_tbs_full_error_printed = FALSE;

/**********************************************************************//**

Returns an extent to the free list of a space. */

static

void

fsp_free_extent(

/*============*/

	ulint		space,	/*!< in: space id */

	ulint		zip_size,/*!< in: compressed page size in bytes

				or 0 for uncompressed pages */

	ulint		page,	/*!< in: page offset in the extent */

	mtr_t*		mtr);	/*!< in: mtr */

/**********************************************************************//**

Frees an extent of a segment to the space free list. */

static

void

fseg_free_extent(

/*=============*/

	fseg_inode_t*	seg_inode, /*!< in: segment inode */

	ulint		space,	/*!< in: space id */

	ulint		zip_size,/*!< in: compressed page size in bytes

				or 0 for uncompressed pages */

	ulint		page,	/*!< in: page offset in the extent */

	mtr_t*		mtr);	/*!< in: mtr handle */

/**********************************************************************//**

Calculates the number of pages reserved by a segment, and how

many pages are currently used.

@return	number of reserved pages */

static

ulint

fseg_n_reserved_pages_low(

/*======================*/

	fseg_inode_t*	header,	/*!< in: segment inode */

	ulint*		used,	/*!< out: number of pages used (not

				more than reserved) */

	mtr_t*		mtr);	/*!< in: mtr handle */

/********************************************************************//**

Marks a page used. The page must reside within the extents of the given

segment. */

static

void

fseg_mark_page_used(

/*================*/

	fseg_inode_t*	seg_inode,/*!< in: segment inode */

	ulint		space,	/*!< in: space id */

	ulint		zip_size,/*!< in: compressed page size in bytes

				or 0 for uncompressed pages */

	ulint		page,	/*!< in: page offset */

	mtr_t*		mtr);	/*!< in: mtr */

/**********************************************************************//**

Returns the first extent descriptor for a segment. We think of the extent

lists of the segment catenated in the order FSEG_FULL -> FSEG_NOT_FULL

-> FSEG_FREE.

@return	the first extent descriptor, or NULL if none */

static

xdes_t*

fseg_get_first_extent(

/*==================*/

	fseg_inode_t*	inode,	/*!< in: segment inode */

	ulint		space,	/*!< in: space id */

	ulint		zip_size,/*!< in: compressed page size in bytes

				or 0 for uncompressed pages */

	mtr_t*		mtr);	/*!< in: mtr */

/**********************************************************************//**

Puts new extents to the free list if

there are free extents above the free limit. If an extent happens

to contain an extent descriptor page, the extent is put to

the FSP_FREE_FRAG list with the page marked as used. */

static

void

fsp_fill_free_list(

/*===============*/

	ibool		init_space,	/*!< in: TRUE if this is a single-table

					tablespace and we are only initing

					the tablespace's first extent

					descriptor page and ibuf bitmap page;

					then we do not allocate more extents */

	ulint		space,		/*!< in: space */

	fsp_header_t*	header,		/*!< in: space header */

	mtr_t*		mtr);		/*!< in: mtr */

/**********************************************************************//**

Allocates a single free page from a segment. This function implements

the intelligent allocation strategy which tries to minimize file space

fragmentation.

@return	the allocated page number, FIL_NULL if no page could be allocated */

static

ulint

fseg_alloc_free_page_low(

/*=====================*/

	ulint		space,	/*!< in: space */

	ulint		zip_size,/*!< in: compressed page size in bytes

				or 0 for uncompressed pages */

	fseg_inode_t*	seg_inode, /*!< in: segment inode */

	ulint		hint,	/*!< in: hint of which page would be desirable */

	byte		direction, /*!< in: if the new page is needed because

				of an index page split, and records are

				inserted there in order, into which

				direction they go alphabetically: FSP_DOWN,

				FSP_UP, FSP_NO_DIR */

	mtr_t*		mtr);	/*!< in: mtr handle */

#endif /* !UNIV_HOTBACKUP */

/**********************************************************************//**

Reads the file space size stored in the header page.

@return	tablespace size stored in the space header */

UNIV_INTERN

ulint

fsp_get_size_low(

/*=============*/

	page_t*	page)	/*!< in: header page (page 0 in the tablespace) */

{

	return(mach_read_from_4(page + FSP_HEADER_OFFSET + FSP_SIZE));

}

#ifndef UNIV_HOTBACKUP

/**********************************************************************//**

Gets a pointer to the space header and x-locks its page.

@return	pointer to the space header, page x-locked */

UNIV_INLINE

fsp_header_t*

fsp_get_space_header(

/*=================*/

	ulint	id,	/*!< in: space id */

	ulint	zip_size,/*!< in: compressed page size in bytes

			or 0 for uncompressed pages */

	mtr_t*	mtr)	/*!< in: mtr */

{

	buf_block_t*	block;

	fsp_header_t*	header;

	ut_ad(ut_is_2pow(zip_size));

	ut_ad(zip_size <= UNIV_PAGE_SIZE);

	ut_ad(!zip_size || zip_size >= PAGE_ZIP_MIN_SIZE);

	ut_ad(id || !zip_size);

	block = buf_page_get(id, zip_size, 0, RW_X_LATCH, mtr);

	header = FSP_HEADER_OFFSET + buf_block_get_frame(block);

	buf_block_dbg_add_level(block, SYNC_FSP_PAGE);

	ut_ad(id == mach_read_from_4(FSP_SPACE_ID + header));

	ut_ad(zip_size == dict_table_flags_to_zip_size(

		      mach_read_from_4(FSP_SPACE_FLAGS + header)));

	return(header);

}

/**********************************************************************//**

Gets a descriptor bit of a page.

@return	TRUE if free */

UNIV_INLINE

ibool

xdes_get_bit(

/*=========*/

	const xdes_t*	descr,	/*!< in: descriptor */

	ulint		bit,	/*!< in: XDES_FREE_BIT or XDES_CLEAN_BIT */

	ulint		offset,	/*!< in: page offset within extent:

				0 ... FSP_EXTENT_SIZE - 1 */

	mtr_t*		mtr)	/*!< in: mtr */

{

	ulint	index;

	ulint	byte_index;

	ulint	bit_index;

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	ut_ad((bit == XDES_FREE_BIT) || (bit == XDES_CLEAN_BIT));

	ut_ad(offset < FSP_EXTENT_SIZE);

	index = bit + XDES_BITS_PER_PAGE * offset;

	byte_index = index / 8;

	bit_index = index % 8;

	return(ut_bit_get_nth(mtr_read_ulint(descr + XDES_BITMAP + byte_index,

					     MLOG_1BYTE, mtr),

			      bit_index));

}

/**********************************************************************//**

Sets a descriptor bit of a page. */

UNIV_INLINE

void

xdes_set_bit(

/*=========*/

	xdes_t*	descr,	/*!< in: descriptor */

	ulint	bit,	/*!< in: XDES_FREE_BIT or XDES_CLEAN_BIT */

	ulint	offset,	/*!< in: page offset within extent:

			0 ... FSP_EXTENT_SIZE - 1 */

	ibool	val,	/*!< in: bit value */

	mtr_t*	mtr)	/*!< in: mtr */

{

	ulint	index;

	ulint	byte_index;

	ulint	bit_index;

	ulint	descr_byte;

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	ut_ad((bit == XDES_FREE_BIT) || (bit == XDES_CLEAN_BIT));

	ut_ad(offset < FSP_EXTENT_SIZE);

	index = bit + XDES_BITS_PER_PAGE * offset;

	byte_index = index / 8;

	bit_index = index % 8;

	descr_byte = mtr_read_ulint(descr + XDES_BITMAP + byte_index,

				    MLOG_1BYTE, mtr);

	descr_byte = ut_bit_set_nth(descr_byte, bit_index, val);

	mlog_write_ulint(descr + XDES_BITMAP + byte_index, descr_byte,

			 MLOG_1BYTE, mtr);

}

/**********************************************************************//**

Looks for a descriptor bit having the desired value. Starts from hint

and scans upward; at the end of the extent the search is wrapped to

the start of the extent.

@return	bit index of the bit, ULINT_UNDEFINED if not found */

UNIV_INLINE

ulint

xdes_find_bit(

/*==========*/

	xdes_t*	descr,	/*!< in: descriptor */

	ulint	bit,	/*!< in: XDES_FREE_BIT or XDES_CLEAN_BIT */

	ibool	val,	/*!< in: desired bit value */

	ulint	hint,	/*!< in: hint of which bit position would be desirable */

	mtr_t*	mtr)	/*!< in: mtr */

{

	ulint	i;

	ut_ad(descr && mtr);

	ut_ad(val <= TRUE);

	ut_ad(hint < FSP_EXTENT_SIZE);

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	for (i = hint; i < FSP_EXTENT_SIZE; i++) {

		if (val == xdes_get_bit(descr, bit, i, mtr)) {

			return(i);

		}

	}

	for (i = 0; i < hint; i++) {

		if (val == xdes_get_bit(descr, bit, i, mtr)) {

			return(i);

		}

	}

	return(ULINT_UNDEFINED);

}

/**********************************************************************//**

Looks for a descriptor bit having the desired value. Scans the extent in

a direction opposite to xdes_find_bit.

@return	bit index of the bit, ULINT_UNDEFINED if not found */

UNIV_INLINE

ulint

xdes_find_bit_downward(

/*===================*/

	xdes_t*	descr,	/*!< in: descriptor */

	ulint	bit,	/*!< in: XDES_FREE_BIT or XDES_CLEAN_BIT */

	ibool	val,	/*!< in: desired bit value */

	ulint	hint,	/*!< in: hint of which bit position would be desirable */

	mtr_t*	mtr)	/*!< in: mtr */

{

	ulint	i;

	ut_ad(descr && mtr);

	ut_ad(val <= TRUE);

	ut_ad(hint < FSP_EXTENT_SIZE);

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	for (i = hint + 1; i > 0; i--) {

		if (val == xdes_get_bit(descr, bit, i - 1, mtr)) {

			return(i - 1);

		}

	}

	for (i = FSP_EXTENT_SIZE - 1; i > hint; i--) {

		if (val == xdes_get_bit(descr, bit, i, mtr)) {

			return(i);

		}

	}

	return(ULINT_UNDEFINED);

}

/**********************************************************************//**

Returns the number of used pages in a descriptor.

@return	number of pages used */

UNIV_INLINE

ulint

xdes_get_n_used(

/*============*/

	const xdes_t*	descr,	/*!< in: descriptor */

	mtr_t*		mtr)	/*!< in: mtr */

{

	ulint	i;

	ulint	count	= 0;

	ut_ad(descr && mtr);

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	for (i = 0; i < FSP_EXTENT_SIZE; i++) {

		if (FALSE == xdes_get_bit(descr, XDES_FREE_BIT, i, mtr)) {

			count++;

		}

	}

	return(count);

}

/**********************************************************************//**

Returns true if extent contains no used pages.

@return	TRUE if totally free */

UNIV_INLINE

ibool

xdes_is_free(

/*=========*/

	const xdes_t*	descr,	/*!< in: descriptor */

	mtr_t*		mtr)	/*!< in: mtr */

{

	if (0 == xdes_get_n_used(descr, mtr)) {

		return(TRUE);

	}

	return(FALSE);

}

/**********************************************************************//**

Returns true if extent contains no free pages.

@return	TRUE if full */

UNIV_INLINE

ibool

xdes_is_full(

/*=========*/

	const xdes_t*	descr,	/*!< in: descriptor */

	mtr_t*		mtr)	/*!< in: mtr */

{

	if (FSP_EXTENT_SIZE == xdes_get_n_used(descr, mtr)) {

		return(TRUE);

	}

	return(FALSE);

}

/**********************************************************************//**

Sets the state of an xdes. */

UNIV_INLINE

void

xdes_set_state(

/*===========*/

	xdes_t*	descr,	/*!< in/out: descriptor */

	ulint	state,	/*!< in: state to set */

	mtr_t*	mtr)	/*!< in: mtr handle */

{

	ut_ad(descr && mtr);

	ut_ad(state >= XDES_FREE);

	ut_ad(state <= XDES_FSEG);

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	mlog_write_ulint(descr + XDES_STATE, state, MLOG_4BYTES, mtr);

}

/**********************************************************************//**

Gets the state of an xdes.

@return	state */

UNIV_INLINE

ulint

xdes_get_state(

/*===========*/

	const xdes_t*	descr,	/*!< in: descriptor */

	mtr_t*		mtr)	/*!< in: mtr handle */

{

	ulint	state;

	ut_ad(descr && mtr);

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	state = mtr_read_ulint(descr + XDES_STATE, MLOG_4BYTES, mtr);

	ut_ad(state - 1 < XDES_FSEG);

	return(state);

}

/**********************************************************************//**

Inits an extent descriptor to the free and clean state. */

UNIV_INLINE

void

xdes_init(

/*======*/

	xdes_t*	descr,	/*!< in: descriptor */

	mtr_t*	mtr)	/*!< in: mtr */

{

	ulint	i;

	ut_ad(descr && mtr);

	ut_ad(mtr_memo_contains_page(mtr, descr, MTR_MEMO_PAGE_X_FIX));

	ut_ad((XDES_SIZE - XDES_BITMAP) % 4 == 0);

	for (i = XDES_BITMAP; i < XDES_SIZE; i += 4) {

		mlog_write_ulint(descr + i, 0xFFFFFFFFUL, MLOG_4BYTES, mtr);

	}

	xdes_set_state(descr, XDES_FREE, mtr);

}

/********************************************************************//**

Calculates the page where the descriptor of a page resides.

@return	descriptor page offset */

UNIV_INLINE

ulint

xdes_calc_descriptor_page(

/*======================*/

	ulint	zip_size,	/*!< in: compressed page size in bytes;

				0 for uncompressed pages */

	ulint	offset)		/*!< in: page offset */

{

#ifndef DOXYGEN /* Doxygen gets confused of these */

# if UNIV_PAGE_SIZE <= XDES_ARR_OFFSET \

		+ (UNIV_PAGE_SIZE / FSP_EXTENT_SIZE) * XDES_SIZE

#  error

# endif

# if PAGE_ZIP_MIN_SIZE <= XDES_ARR_OFFSET \

		+ (PAGE_ZIP_MIN_SIZE / FSP_EXTENT_SIZE) * XDES_SIZE

#  error

# endif

#endif /* !DOXYGEN */

	ut_ad(ut_is_2pow(zip_size));

	if (!zip_size) {

		return(ut_2pow_round(offset, UNIV_PAGE_SIZE));

	} else {

		ut_ad(zip_size > XDES_ARR_OFFSET

		      + (zip_size / FSP_EXTENT_SIZE) * XDES_SIZE);

		return(ut_2pow_round(offset, zip_size));

	}

}

/********************************************************************//**

Calculates the descriptor index within a descriptor page.

@return	descriptor index */

UNIV_INLINE

ulint

xdes_calc_descriptor_index(

/*=======================*/

	ulint	zip_size,	/*!< in: compressed page size in bytes;

				0 for uncompressed pages */

	ulint	offset)		/*!< in: page offset */

{

	ut_ad(ut_is_2pow(zip_size));

	if (!zip_size) {

		return(ut_2pow_remainder(offset, UNIV_PAGE_SIZE)

		       / FSP_EXTENT_SIZE);

	} else {

		return(ut_2pow_remainder(offset, zip_size) / FSP_EXTENT_SIZE);

	}

}

/********************************************************************//**

Gets pointer to a the extent descriptor of a page. The page where the extent

descriptor resides is x-locked. If the page offset is equal to the free limit

of the space, adds new extents from above the free limit to the space free

list, if not free limit == space size. This adding is necessary to make the

descriptor defined, as they are uninitialized above the free limit.

@return pointer to the extent descriptor, NULL if the page does not

exist in the space or if the offset exceeds the free limit */

UNIV_INLINE

xdes_t*

xdes_get_descriptor_with_space_hdr(

/*===============================*/

	fsp_header_t*	sp_header,/*!< in/out: space header, x-latched */

	ulint		space,	/*!< in: space id */

	ulint		offset,	/*!< in: page offset;

				if equal to the free limit,

				we try to add new extents to

				the space free list */

	mtr_t*		mtr)	/*!< in: mtr handle */

{

	ulint	limit;

	ulint	size;

	ulint	zip_size;

	ulint	descr_page_no;

	page_t*	descr_page;

	ut_ad(mtr);

	ut_ad(mtr_memo_contains(mtr, fil_space_get_latch(space, NULL),

				MTR_MEMO_X_LOCK));

	ut_ad(mtr_memo_contains_page(mtr, sp_header, MTR_MEMO_PAGE_S_FIX)

	      || mtr_memo_contains_page(mtr, sp_header, MTR_MEMO_PAGE_X_FIX));

	ut_ad(page_offset(sp_header) == FSP_HEADER_OFFSET);

	/* Read free limit and space size */

	limit = mach_read_from_4(sp_header + FSP_FREE_LIMIT);

	size  = mach_read_from_4(sp_header + FSP_SIZE);

	zip_size = dict_table_flags_to_zip_size(

		mach_read_from_4(sp_header + FSP_SPACE_FLAGS));

	/* If offset is >= size or > limit, return NULL */

	if ((offset >= size) || (offset > limit)) {

		return(NULL);

	}

	/* If offset is == limit, fill free list of the space. */

	if (offset == limit) {

		fsp_fill_free_list(FALSE, space, sp_header, mtr);

	}

	descr_page_no = xdes_calc_descriptor_page(zip_size, offset);

	if (descr_page_no == 0) {

		/* It is on the space header page */

		descr_page = page_align(sp_header);

	} else {

		buf_block_t*	block;

		block = buf_page_get(space, zip_size, descr_page_no,

				     RW_X_LATCH, mtr);

		buf_block_dbg_add_level(block, SYNC_FSP_PAGE);

		descr_page = buf_block_get_frame(block);

	}

	return(descr_page + XDES_ARR_OFFSET

	       + XDES_SIZE * xdes_calc_descriptor_index(zip_size, offset));

}

/********************************************************************//**

Gets pointer to a the extent descriptor of a page. The page where the

extent descriptor resides is x-locked. If the page offset is equal to

the free limit of the space, adds new extents from above the free limit

to the space free list, if not free limit == space size. This adding

is necessary to make the descriptor defined, as they are uninitialized

above the free limit.

@return pointer to the extent descriptor, NULL if the page does not

exist in the space or if the offset exceeds the free limit */

static

xdes_t*

xdes_get_descriptor(

/*================*/

	ulint	space,	/*!< in: space id */

	ulint	zip_size,/*!< in: compressed page size in bytes

			or 0 for uncompressed pages */

	ulint	offset,	/*!< in: page offset; if equal to the free limit,

			we try to add new extents to the space free list */

	mtr_t*	mtr)	/*!< in: mtr handle */

{

	buf_block_t*	block;

	fsp_header_t*	sp_header;

	block = buf_page_get(space, zip_size, 0, RW_X_LATCH, mtr);

	buf_block_dbg_add_level(block, SYNC_FSP_PAGE);

	sp_header = FSP_HEADER_OFFSET + buf_block_get_frame(block);

	return(xdes_get_descriptor_with_space_hdr(sp_header, space, offset,

						  mtr));

}

/********************************************************************//**

Gets pointer to a the extent descriptor if the file address

of the descriptor list node is known. The page where the

extent descriptor resides is x-locked.

@return	pointer to the extent descriptor */

UNIV_INLINE

xdes_t*

xdes_lst_get_descriptor(

/*====================*/

	ulint		space,	/*!< in: space id */

	ulint		zip_size,/*!< in: compressed page size in bytes

				or 0 for uncompressed pages */

	fil_addr_t	lst_node,/*!< in: file address of the list node

				contained in the descriptor */

	mtr_t*		mtr)	/*!< in: mtr handle */

{

	xdes_t*	descr;

	ut_ad(mtr);

	ut_ad(mtr_memo_contains(mtr, fil_space_get_latch(space, NULL),

				MTR_MEMO_X_LOCK));

	descr = fut_get_ptr(space, zip_size, lst_node, RW_X_LATCH, mtr)

		- XDES_FLST_NODE;

	return(descr);

}

/********************************************************************//**

Returns page offset of the first page in extent described by a descriptor.

@return	offset of the first page in extent */

UNIV_INLINE

ulint

xdes_get_offset(

/*============*/

	xdes_t*	descr)	/*!< in: extent descriptor */

{

	ut_ad(descr);

	return(page_get_page_no(page_align(descr))

	       + ((page_offset(descr) - XDES_ARR_OFFSET) / XDES_SIZE)

	       * FSP_EXTENT_SIZE);

}