MySQL数据库

开发平台：
Visual C++

fsp0fsp.c：源码内容
							/**********************************************************************
File space management
(c) 1995 Innobase Oy
Created 11/29/1995 Heikki Tuuri
***********************************************************************/
#include "fsp0fsp.h"
#ifdef UNIV_NONINL
#include "fsp0fsp.ic"
#endif
#include "buf0buf.h"
#include "fil0fil.h"
#include "sync0sync.h"
#include "mtr0log.h"
#include "fut0fut.h"
#include "ut0byte.h"
#include "srv0srv.h"
#include "page0types.h"
#include "ibuf0ibuf.h"
#include "btr0btr.h"
#include "btr0sea.h"
#include "dict0boot.h"
#include "dict0mem.h"
#include "log0log.h"
/* 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_HEADER_OFFSET	FIL_PAGE_DATA	/* Offset of the space header
						within a file page */
/*-------------------------------------*/
#define FSP_NOT_USED		0	/* 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 */
#define	FSP_LOWEST_NO_WRITE	16	/* The lowest page offset for which
					the page has not been written to disk
					(if it has been written, we know that
					the OS has really reserved the
					physical space for the page) */
#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
					ut_dulint_zero, 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	((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. The "+ 7 ) / 8" part in the
definition rounds the number of bytes upward. */
#define	XDES_SIZE	(XDES_BITMAP +
			 (FSP_EXTENT_SIZE * XDES_BITS_PER_PAGE + 7) / 8)
/* Offset of the descriptor array on a descriptor page */
#define	XDES_ARR_OFFSET		(FSP_HEADER_OFFSET + FSP_HEADER_SIZE)
					
/**************************************************************************
Returns an extent to the free list of a space. */
static
void
fsp_free_extent(
/*============*/
	ulint		space,	/* in: space id */
	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		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. */
static
ulint
fseg_n_reserved_pages_low(
/*======================*/
				/* out: number of reserved pages */
	fseg_inode_t* 	header,	/* in: segment inode */
	ulint*		used,	/* out: number of pages used (<= 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		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. */
static
xdes_t*
fseg_get_first_extent(
/*==================*/
				/* out: the first extent descriptor, or NULL if
				none */
	fseg_inode_t*	inode,	/* in: segment inode */
	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(
/*===============*/
	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. */
static
ulint
fseg_alloc_free_page_low(
/*=====================*/
				/* out: the allocated page number, FIL_NULL
				if no page could be allocated */
	ulint		space,	/* in: space */
	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 */
/**************************************************************************
Gets a pointer to the space header and x-locks its page. */
UNIV_INLINE
fsp_header_t*
fsp_get_space_header(
/*=================*/
			/* out: pointer to the space header, page x-locked */
	ulint	id,	/* in: space id */
	mtr_t*	mtr)	/* in: mtr */
{
	fsp_header_t*	header;
	ut_ad(mtr);
	header = FSP_HEADER_OFFSET + buf_page_get(id, 0, RW_X_LATCH, mtr);
	
	buf_page_dbg_add_level(header, SYNC_FSP_PAGE);
	return(header);
}
/**************************************************************************
Gets a descriptor bit of a page. */
UNIV_INLINE
ibool
xdes_get_bit(
/*=========*/
			/* out: TRUE if free */
	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(mtr, buf_block_align(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(mtr, buf_block_align(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. */
UNIV_INLINE
ulint
xdes_find_bit(
/*==========*/
			/* out: bit index of the bit, ULINT_UNDEFINED if not
			found */
	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(mtr, buf_block_align(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. */
UNIV_INLINE
ulint
xdes_find_bit_downward(
/*===================*/
			/* out: bit index of the bit, ULINT_UNDEFINED if not
			found */
	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(mtr, buf_block_align(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. */
UNIV_INLINE
ulint
xdes_get_n_used(
/*============*/
			/* out: number of pages used */
	xdes_t*	descr,	/* in: descriptor */
	mtr_t*	mtr)	/* in: mtr */
{
	ulint	i;
	ulint	count	= 0;
	
	ut_ad(descr && mtr);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(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. */
UNIV_INLINE
ibool
xdes_is_free(
/*=========*/
			/* out: TRUE if totally free */
	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. */
UNIV_INLINE
ibool
xdes_is_full(
/*=========*/
			/* out: TRUE if full */
	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: 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(mtr, buf_block_align(descr),
							MTR_MEMO_PAGE_X_FIX));
	mlog_write_ulint(descr + XDES_STATE, state, MLOG_4BYTES, mtr); 
}
/**************************************************************************
Gets the state of an xdes. */
UNIV_INLINE
ulint
xdes_get_state(
/*===========*/
			/* out: state */
	xdes_t*	descr,	/* in: descriptor */
	mtr_t*	mtr)	/* in: mtr handle */
{
	ut_ad(descr && mtr);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(descr),
							MTR_MEMO_PAGE_X_FIX));
	return(mtr_read_ulint(descr + XDES_STATE, MLOG_4BYTES, mtr)); 
}
/**************************************************************************
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(mtr, buf_block_align(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, 0xFFFFFFFF, MLOG_4BYTES, mtr);
	}
	xdes_set_state(descr, XDES_FREE, mtr);
}	
/************************************************************************
Calculates the page where the descriptor of a page resides. */
UNIV_INLINE
ulint
xdes_calc_descriptor_page(
/*======================*/
				/* out: descriptor page offset */
	ulint	offset)		/* in: page offset */
{
	ut_ad(UNIV_PAGE_SIZE > XDES_ARR_OFFSET
		+ (XDES_DESCRIBED_PER_PAGE / FSP_EXTENT_SIZE) * XDES_SIZE);
	return(ut_2pow_round(offset, XDES_DESCRIBED_PER_PAGE));
}
/************************************************************************
Calculates the descriptor index within a descriptor page. */
UNIV_INLINE
ulint
xdes_calc_descriptor_index(
/*=======================*/
				/* out: descriptor index */
	ulint	offset)		/* in: page offset */
{
	return(ut_2pow_remainder(offset, XDES_DESCRIBED_PER_PAGE) /
							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. */
UNIV_INLINE
xdes_t*
xdes_get_descriptor_with_space_hdr(
/*===============================*/
				/* out: pointer to the extent descriptor,
				NULL if the page does not exist in the
				space or if offset > free limit */
	fsp_header_t*	sp_header,/* in: 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	descr_page_no;
	page_t*	descr_page;
	ut_ad(mtr);
	ut_ad(mtr_memo_contains(mtr, fil_space_get_latch(space), MTR_MEMO_X_LOCK));
	/* Read free limit and space size */
	limit = mtr_read_ulint(sp_header + FSP_FREE_LIMIT, MLOG_4BYTES, mtr);
	size  = mtr_read_ulint(sp_header + FSP_SIZE, MLOG_4BYTES, mtr);
	/* 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(space, sp_header, mtr);
	}
	descr_page_no = xdes_calc_descriptor_page(offset);
	if (descr_page_no == 0) {
		/* It is on the space header page */
		descr_page = buf_frame_align(sp_header);
	} else {
		descr_page = buf_page_get(space, descr_page_no, RW_X_LATCH,
									mtr);
		buf_page_dbg_add_level(descr_page, SYNC_FSP_PAGE);
	}	
	return(descr_page + XDES_ARR_OFFSET
	       + XDES_SIZE * xdes_calc_descriptor_index(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. */
static
xdes_t*
xdes_get_descriptor(
/*================*/
			/* out: pointer to the extent descriptor, NULL if the
			page does not exist in the space or if offset > free
			limit */
	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 */
{
	fsp_header_t*	sp_header;
	sp_header = FSP_HEADER_OFFSET
				+ buf_page_get(space, 0, RW_X_LATCH, mtr);
	buf_page_dbg_add_level(sp_header, SYNC_FSP_PAGE);
	
	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. */
UNIV_INLINE
xdes_t*
xdes_lst_get_descriptor(
/*====================*/
				/* out: pointer to the extent descriptor */
	ulint		space,	/* in: space id */
	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), MTR_MEMO_X_LOCK));
	
	descr = fut_get_ptr(space, lst_node, RW_X_LATCH, mtr) - XDES_FLST_NODE;
	return(descr);
}
/************************************************************************
Gets pointer to the next descriptor in a descriptor list and x-locks its
page. */
UNIV_INLINE
xdes_t*
xdes_lst_get_next(
/*==============*/
	xdes_t*	descr,	/* in: pointer to a descriptor */
	mtr_t*	mtr)	/* in: mtr handle */
{
	ulint	space;
	ut_ad(mtr && descr);
	space = buf_frame_get_space_id(descr);
	return(xdes_lst_get_descriptor(space,
		flst_get_next_addr(descr + XDES_FLST_NODE, mtr), mtr));
}
/************************************************************************
Returns page offset of the first page in extent described by a descriptor. */
UNIV_INLINE
ulint
xdes_get_offset(
/*============*/
			/* out: offset of the first page in extent */
	xdes_t*	descr)	/* in: extent descriptor */
{
	ut_ad(descr);
	return(buf_frame_get_page_no(descr)
		+ ((descr - buf_frame_align(descr) - XDES_ARR_OFFSET)
		   / XDES_SIZE)
		  * FSP_EXTENT_SIZE);
}
/***************************************************************
Inits a file page whose prior contents should be ignored. */
static
void
fsp_init_file_page_low(
/*=====================*/
	byte*	ptr)	/* in: pointer to a page */
{
	page_t*	page;
#ifdef UNIV_BASIC_LOG_DEBUG
	ulint	i;
#endif
	page = buf_frame_align(ptr);
#ifdef UNIV_BASIC_LOG_DEBUG	
/*	printf("In log debug version: Erase the contents of the file pagen");
*/
	for (i = 0; i < UNIV_PAGE_SIZE; i++) {
		page[i] = 0xFF;
	}
#endif
	mach_write_to_8(page + UNIV_PAGE_SIZE - FIL_PAGE_END_LSN,
							ut_dulint_zero);
	mach_write_to_8(page + FIL_PAGE_LSN, ut_dulint_zero);
}
/***************************************************************
Inits a file page whose prior contents should be ignored. */
void
fsp_init_file_page(
/*===============*/
	page_t*	page,	/* in: page */
	mtr_t*	mtr)	/* in: mtr */
{
	fsp_init_file_page_low(page);
		
	mlog_write_initial_log_record(page, MLOG_INIT_FILE_PAGE, mtr);
}
	
/***************************************************************
Parses a redo log record of a file page init. */
byte*
fsp_parse_init_file_page(
/*=====================*/
			/* out: end of log record or NULL */
	byte*	ptr,	/* in: buffer */
	byte*	end_ptr,/* in: buffer end */
	page_t*	page)	/* in: page or NULL */
{
	ut_ad(ptr && end_ptr);
	if (page) {
		fsp_init_file_page_low(page);
	}
	
	return(ptr);
}
/**************************************************************************
Initializes the fsp system. */
void
fsp_init(void)
/*==========*/
{
	/* Does nothing at the moment */
}
/**************************************************************************
Initializes the space header of a new created space and creates also the
insert buffer tree root. */
void
fsp_header_init(
/*============*/
	ulint	space,	/* in: space id */
	ulint	size,	/* in: current size in blocks */
	mtr_t*	mtr)	/* in: mini-transaction handle */	
{
	fsp_header_t*	header;
	page_t*		page;
	
	ut_ad(mtr);
	mtr_x_lock(fil_space_get_latch(space), mtr);
	page = buf_page_create(space, 0, mtr);
	buf_page_dbg_add_level(page, SYNC_FSP_PAGE);
	buf_page_get(space, 0, RW_X_LATCH, mtr);
	buf_page_dbg_add_level(page, SYNC_FSP_PAGE);
	/* The prior contents of the file page should be ignored */
	fsp_init_file_page(page, mtr);
	header = FSP_HEADER_OFFSET + page;
	mlog_write_ulint(header + FSP_SIZE, size, MLOG_4BYTES, mtr); 
	mlog_write_ulint(header + FSP_FREE_LIMIT, 0, MLOG_4BYTES, mtr); 
	mlog_write_ulint(header + FSP_LOWEST_NO_WRITE, 0, MLOG_4BYTES, mtr); 
	mlog_write_ulint(header + FSP_FRAG_N_USED, 0, MLOG_4BYTES, mtr); 
	
	flst_init(header + FSP_FREE, mtr);
	flst_init(header + FSP_FREE_FRAG, mtr);
	flst_init(header + FSP_FULL_FRAG, mtr);
	flst_init(header + FSP_SEG_INODES_FULL, mtr);
	flst_init(header + FSP_SEG_INODES_FREE, mtr);
	mlog_write_dulint(header + FSP_SEG_ID, ut_dulint_create(0, 1),
							MLOG_8BYTES, mtr); 
	fsp_fill_free_list(space, header, mtr);
	btr_create(DICT_CLUSTERED | DICT_UNIVERSAL | DICT_IBUF, space,
				ut_dulint_add(DICT_IBUF_ID_MIN, space), mtr);
}
/**************************************************************************
Increases the space size field of a space. */
void
fsp_header_inc_size(
/*================*/
	ulint	space,	/* in: space id */
	ulint	size_inc,/* in: size increment in pages */
	mtr_t*	mtr)	/* in: mini-transaction handle */	
{
	fsp_header_t*	header;
	ulint		size;
	
	ut_ad(mtr);
	mtr_x_lock(fil_space_get_latch(space), mtr);	
	header = fsp_get_space_header(space, mtr);
	size = mtr_read_ulint(header + FSP_SIZE, MLOG_4BYTES, mtr);
	mlog_write_ulint(header + FSP_SIZE, size + size_inc, MLOG_4BYTES, 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(
/*===============*/
	ulint		space,	/* in: space */
	fsp_header_t*	header,	/* in: space header */
	mtr_t*		mtr)	/* in: mtr */
{
	ulint	limit;
	ulint	size;
	xdes_t*	descr;
	ulint	count 		= 0;
	ulint	frag_n_used;
	page_t*	descr_page;
	page_t*	ibuf_page;
	mtr_t	ibuf_mtr;
	ulint	i;
	ut_ad(header && mtr);
	
	/* Check if we can fill free list from above the free list limit */
	size = mtr_read_ulint(header + FSP_SIZE, MLOG_4BYTES, mtr);
	limit = mtr_read_ulint(header + FSP_FREE_LIMIT, MLOG_4BYTES, mtr);
	i = limit;
		
	while ((i + FSP_EXTENT_SIZE <= size) && (count < FSP_FREE_ADD)) {
		mlog_write_ulint(header + FSP_FREE_LIMIT, i + FSP_EXTENT_SIZE,
							MLOG_4BYTES, mtr); 
		if (0 == i % XDES_DESCRIBED_PER_PAGE) {
			/* We are going to initialize a new descriptor page
			and a new ibuf bitmap page: the prior contents of the
			pages should be ignored. */
			if (i > 0) {
				descr_page = buf_page_create(space, i, mtr);
				buf_page_dbg_add_level(descr_page,
								SYNC_FSP_PAGE);
				buf_page_get(space, i, RW_X_LATCH, mtr);
				buf_page_dbg_add_level(descr_page,
								SYNC_FSP_PAGE);
				fsp_init_file_page(descr_page, mtr);
			}
			/* Initialize the ibuf page in a separate
			mini-transaction because it is low in the latching
			order, and we must be able to release the its latch
			before returning from the fsp routine */
			
			mtr_start(&ibuf_mtr);
			ibuf_page = buf_page_create(space,
					i + FSP_IBUF_BITMAP_OFFSET, &ibuf_mtr);
			buf_page_dbg_add_level(ibuf_page, SYNC_IBUF_BITMAP);
			buf_page_get(space, i + FSP_IBUF_BITMAP_OFFSET,
							RW_X_LATCH, &ibuf_mtr);
			buf_page_dbg_add_level(ibuf_page, SYNC_FSP_PAGE);
			fsp_init_file_page(ibuf_page, &ibuf_mtr);
			ibuf_bitmap_page_init(ibuf_page, &ibuf_mtr);
			mtr_commit(&ibuf_mtr);
		}
		descr = xdes_get_descriptor_with_space_hdr(header, space, i,
									mtr);
		xdes_init(descr, mtr);
		ut_ad(XDES_DESCRIBED_PER_PAGE % FSP_EXTENT_SIZE == 0);
		if (0 == i % XDES_DESCRIBED_PER_PAGE) {
			/* The first page in the extent is a descriptor page
			and the second is an ibuf bitmap page: mark them
			used */
			xdes_set_bit(descr, XDES_FREE_BIT, 0, FALSE, mtr);
			xdes_set_bit(descr, XDES_FREE_BIT,
					FSP_IBUF_BITMAP_OFFSET, FALSE, mtr);
			xdes_set_state(descr, XDES_FREE_FRAG, mtr);
			flst_add_last(header + FSP_FREE_FRAG,
					descr + XDES_FLST_NODE, mtr);
			frag_n_used = mtr_read_ulint(header + FSP_FRAG_N_USED,
						     MLOG_4BYTES, mtr);
			mlog_write_ulint(header + FSP_FRAG_N_USED,
					frag_n_used + 2, MLOG_4BYTES, mtr);
		} else {
			flst_add_last(header + FSP_FREE,
						descr + XDES_FLST_NODE, mtr);
			count++;
		}
		i += FSP_EXTENT_SIZE;
	}
}	
/**************************************************************************
Allocates a new free extent. */
static
xdes_t*
fsp_alloc_free_extent(
/*==================*/
			/* out: extent descriptor, NULL if cannot be
			allocated */
	ulint	space,	/* in: space id */
	ulint	hint,	/* in: hint of which extent would be desirable: any
			page offset in the extent goes; the hint must not
			be > FSP_FREE_LIMIT */
	mtr_t*	mtr)	/* in: mtr */
{
	fsp_header_t*	header;
	fil_addr_t	first;
	xdes_t*		descr;
	
	ut_ad(mtr);
	header = fsp_get_space_header(space, mtr);
	descr = xdes_get_descriptor_with_space_hdr(header, space, hint, mtr);
	if (descr && (xdes_get_state(descr, mtr) == XDES_FREE)) {
		/* Ok, we can take this extent */
	} else {	
		/* Take the first extent in the free list */
		first = flst_get_first(header + FSP_FREE, mtr);
		if (fil_addr_is_null(first)) {
			fsp_fill_free_list(space, header, mtr);
			first = flst_get_first(header + FSP_FREE, mtr);
		}
		if (fil_addr_is_null(first)) {
			return(NULL);	/* No free extents left */
		}
	
		descr = xdes_lst_get_descriptor(space, first, mtr);
	}
	flst_remove(header + FSP_FREE, descr + XDES_FLST_NODE, mtr);
	return(descr);
}
/**************************************************************************
Allocates a single free page from a space. The page is marked as used. */
static
ulint
fsp_alloc_free_page(
/*================*/
			/* out: the page offset, FIL_NULL if no page could
			be allocated */
	ulint	space,	/* in: space id */
	ulint	hint,	/* in: hint of which page would be desirable */
	mtr_t*	mtr)	/* in: mtr handle */
{
	fsp_header_t*	header;
	fil_addr_t	first;
	xdes_t*		descr;
	page_t*		page;
	ulint		free;
	ulint		frag_n_used;
	ulint		page_no;
	
	ut_ad(mtr);
	header = fsp_get_space_header(space, mtr);
	/* Get the hinted descriptor */
	descr = xdes_get_descriptor_with_space_hdr(header, space, hint, mtr);
	if (descr && (xdes_get_state(descr, mtr) == XDES_FREE_FRAG)) {
		/* Ok, we can take this extent */
	} else {
		/* Else take the first extent in free_frag list */
		first = flst_get_first(header + FSP_FREE_FRAG, mtr);
		if (fil_addr_is_null(first)) {
			/* There are no partially full fragments: allocate
			a free extent and add it to the FREE_FRAG list. NOTE
			that the allocation may have as a side-effect that an
			extent containing a descriptor page is added to the
			FREE_FRAG list. But we will allocate our page from the
			the free extent anyway. */
			
			descr = fsp_alloc_free_extent(space, hint, mtr);
			if (descr == NULL) {
				/* No free space left */
				return(FIL_NULL);
			}
			xdes_set_state(descr, XDES_FREE_FRAG, mtr);
			flst_add_last(header + FSP_FREE_FRAG,
						descr + XDES_FLST_NODE, mtr);
		} else {
			descr = xdes_lst_get_descriptor(space, first, mtr);
		}
		/* Reset the hint */
		hint = 0;
	}
	/* Now we have in descr an extent with at least one free page. Look
	for a free page in the extent. */
	free = xdes_find_bit(descr, XDES_FREE_BIT, TRUE,
						hint % FSP_EXTENT_SIZE, mtr);
	ut_a(free != ULINT_UNDEFINED);
	xdes_set_bit(descr, XDES_FREE_BIT, free, FALSE, mtr);
	/* Update the FRAG_N_USED field */
	frag_n_used = mtr_read_ulint(header + FSP_FRAG_N_USED, MLOG_4BYTES,
									mtr);
	frag_n_used++;
	mlog_write_ulint(header + FSP_FRAG_N_USED, frag_n_used, MLOG_4BYTES,
									mtr);
	if (xdes_is_full(descr, mtr)) {
		/* The fragment is full: move it to another list */
		flst_remove(header + FSP_FREE_FRAG, descr + XDES_FLST_NODE,
									mtr);
		xdes_set_state(descr, XDES_FULL_FRAG, mtr);
		
		flst_add_last(header + FSP_FULL_FRAG, descr + XDES_FLST_NODE,
									mtr);
		mlog_write_ulint(header + FSP_FRAG_N_USED,
				frag_n_used - FSP_EXTENT_SIZE, MLOG_4BYTES,
									mtr);
	}
	page_no = xdes_get_offset(descr) + free;
	/* Initialize the allocated page to the buffer pool, so that it can
	be obtained immediately with buf_page_get without need for a disk
	read. */
	
	buf_page_create(space, page_no, mtr);
	page = buf_page_get(space, page_no, RW_X_LATCH, mtr);	
	buf_page_dbg_add_level(page, SYNC_FSP_PAGE);
	/* Prior contents of the page should be ignored */
	fsp_init_file_page(page, mtr);
	
	return(page_no);
}
/**************************************************************************
Frees a single page of a space. The page is marked as free and clean. */
static
void
fsp_free_page(
/*==========*/
	ulint	space,	/* in: space id */
	ulint	page,	/* in: page offset */
	mtr_t*	mtr)	/* in: mtr handle */
{
	fsp_header_t*	header;
	xdes_t*		descr;
	ulint		state;
	ulint		frag_n_used;
	
	ut_ad(mtr);
/*	printf("Freeing page %lu in space %lun", page, space); */
	header = fsp_get_space_header(space, mtr);
	descr = xdes_get_descriptor_with_space_hdr(header, space, page, mtr);
	state = xdes_get_state(descr, mtr);
	
	ut_a((state == XDES_FREE_FRAG) || (state == XDES_FULL_FRAG));
	ut_a(xdes_get_bit(descr, XDES_FREE_BIT, page % FSP_EXTENT_SIZE, mtr)
								== FALSE);
	xdes_set_bit(descr, XDES_FREE_BIT, page % FSP_EXTENT_SIZE, TRUE, mtr);
	xdes_set_bit(descr, XDES_CLEAN_BIT, page % FSP_EXTENT_SIZE, TRUE, mtr);
	frag_n_used = mtr_read_ulint(header + FSP_FRAG_N_USED, MLOG_4BYTES,
									mtr);
	if (state == XDES_FULL_FRAG) {
		/* The fragment was full: move it to another list */
		flst_remove(header + FSP_FULL_FRAG, descr + XDES_FLST_NODE,
									mtr);
		xdes_set_state(descr, XDES_FREE_FRAG, mtr);
		flst_add_last(header + FSP_FREE_FRAG, descr + XDES_FLST_NODE,
									mtr);
		mlog_write_ulint(header + FSP_FRAG_N_USED,
					frag_n_used + FSP_EXTENT_SIZE - 1,
							MLOG_4BYTES, mtr);
	} else {
		ut_a(frag_n_used > 0);
		mlog_write_ulint(header + FSP_FRAG_N_USED, frag_n_used - 1,
							MLOG_4BYTES, mtr);
	}
	if (xdes_is_free(descr, mtr)) {
	    	/* The extent has become free: move it to another list */
		flst_remove(header + FSP_FREE_FRAG, descr + XDES_FLST_NODE,
									mtr);
		fsp_free_extent(space, page, mtr);
	}		
}
/**************************************************************************
Returns an extent to the free list of a space. */
static
void
fsp_free_extent(
/*============*/
	ulint	space,	/* in: space id */
	ulint	page,	/* in: page offset in the extent */
	mtr_t*	mtr)	/* in: mtr */
{
	fsp_header_t*	header;
	xdes_t*		descr;
	
	ut_ad(mtr);
	header = fsp_get_space_header(space, mtr);
	descr = xdes_get_descriptor_with_space_hdr(header, space, page, mtr);
	ut_a(xdes_get_state(descr, mtr) != XDES_FREE);
	xdes_init(descr, mtr);
	flst_add_last(header + FSP_FREE, descr + XDES_FLST_NODE, mtr);
}
/**************************************************************************
Returns the nth inode slot on an inode page. */
UNIV_INLINE
fseg_inode_t*
fsp_seg_inode_page_get_nth_inode(
/*=============================*/
			/* out: segment inode */
	page_t*	page,	/* in: segment inode page */
	ulint	i,	/* in: inode index on page */
	mtr_t*	mtr)	/* in: mini-transaction handle */
{
	ut_ad(i < FSP_SEG_INODES_PER_PAGE);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(page),
							MTR_MEMO_PAGE_X_FIX));
	return(page + FSEG_ARR_OFFSET + FSEG_INODE_SIZE * i);
}
/**************************************************************************
Looks for a used segment inode on a segment inode page. */ 
static
ulint
fsp_seg_inode_page_find_used(
/*=========================*/
			/* out: segment inode index, or ULINT_UNDEFINED
			if not found */
	page_t*	page,	/* in: segment inode page */
	mtr_t*	mtr)	/* in: mini-transaction handle */
{
	ulint		i;
	fseg_inode_t*	inode;
	for (i = 0; i < FSP_SEG_INODES_PER_PAGE; i++) {
		inode = fsp_seg_inode_page_get_nth_inode(page, i, mtr);
		if (ut_dulint_cmp(mach_read_from_8(inode + FSEG_ID),
						ut_dulint_zero) != 0) {
			/* This is used */
			
			return(i);
		}
	}
	return(ULINT_UNDEFINED);
}
/**************************************************************************
Looks for an unused segment inode on a segment inode page. */ 
static
ulint
fsp_seg_inode_page_find_free(
/*=========================*/
			/* out: segment inode index, or ULINT_UNDEFINED
			if not found */
	page_t*	page,	/* in: segment inode page */
	ulint	j,	/* in: search forward starting from this index */
	mtr_t*	mtr)	/* in: mini-transaction handle */
{
	ulint		i;
	fseg_inode_t*	inode;
	for (i = j; i < FSP_SEG_INODES_PER_PAGE; i++) {
		inode = fsp_seg_inode_page_get_nth_inode(page, i, mtr);
		if (ut_dulint_cmp(mach_read_from_8(inode + FSEG_ID),
						ut_dulint_zero) == 0) {
			/* This is unused */
			
			return(i);
		}
	}
	return(ULINT_UNDEFINED);
}
/**************************************************************************
Allocates a new file segment inode page. */
static
ibool
fsp_alloc_seg_inode_page(
/*=====================*/
					/* out: TRUE if could be allocated */
	fsp_header_t*	space_header,	/* in: space header */
	mtr_t*		mtr)		/* in: mini-transaction handle */
{
	fseg_inode_t*	inode;
	page_t*		page;
	ulint		page_no;
	ulint		space;
	ulint		i;
	space = buf_frame_get_space_id(space_header);
	
	page_no = fsp_alloc_free_page(space, 0, mtr);
	if (page_no == FIL_NULL) {
		return(FALSE);
	}
	page = buf_page_get(space, page_no, RW_X_LATCH, mtr);	
	buf_page_dbg_add_level(page, SYNC_FSP_PAGE);
	for (i = 0; i < FSP_SEG_INODES_PER_PAGE; i++) {
		inode = fsp_seg_inode_page_get_nth_inode(page, i, mtr);
		mlog_write_dulint(inode + FSEG_ID, ut_dulint_zero,
							MLOG_8BYTES, mtr);
	}
	flst_add_last(space_header + FSP_SEG_INODES_FREE,
					page + FSEG_INODE_PAGE_NODE, mtr);
	return(TRUE);
}
/**************************************************************************
Allocates a new file segment inode. */
static
fseg_inode_t*
fsp_alloc_seg_inode(
/*================*/
					/* out: segment inode, or NULL if
					not enough space */
	fsp_header_t*	space_header,	/* in: space header */
	mtr_t*		mtr)		/* in: mini-transaction handle */
{
	ulint		page_no;
	page_t*		page;
	fseg_inode_t*	inode;
	ibool		success;
	ulint		n;
	
	if (flst_get_len(space_header + FSP_SEG_INODES_FREE, mtr) == 0) {
		/* Allocate a new segment inode page */
		success = fsp_alloc_seg_inode_page(space_header, mtr);
		if (!success) {
			return(NULL);
		}
	}
	page_no = flst_get_first(space_header + FSP_SEG_INODES_FREE, mtr).page;
	page = buf_page_get(buf_frame_get_space_id(space_header), page_no,
							RW_X_LATCH, mtr);
	buf_page_dbg_add_level(page, SYNC_FSP_PAGE);
	n = fsp_seg_inode_page_find_free(page, 0, mtr);
	ut_a(n != ULINT_UNDEFINED);
	inode = fsp_seg_inode_page_get_nth_inode(page, n, mtr);
	if (ULINT_UNDEFINED == fsp_seg_inode_page_find_free(page, n + 1, mtr)) {
		/* There are no other unused headers left on the page: move it
		to another list */
		flst_remove(space_header + FSP_SEG_INODES_FREE,
				page + FSEG_INODE_PAGE_NODE, mtr);
		flst_add_last(space_header + FSP_SEG_INODES_FULL,
				page + FSEG_INODE_PAGE_NODE, mtr);
	}
	return(inode);	
}
/**************************************************************************
Frees a file segment inode. */
static
void
fsp_free_seg_inode(
/*===============*/
	ulint		space,	/* in: space id */
	fseg_inode_t*	inode,	/* in: segment inode */
	mtr_t*		mtr)	/* in: mini-transaction handle */
{
	page_t*		page;
	fsp_header_t*	space_header;
	
	page = buf_frame_align(inode);
	space_header = fsp_get_space_header(space, mtr);
	ut_ad(mach_read_from_4(inode + FSEG_MAGIC_N) == FSEG_MAGIC_N_VALUE);
	if (ULINT_UNDEFINED == fsp_seg_inode_page_find_free(page, 0, mtr)) {
		/* Move the page to another list */
		flst_remove(space_header + FSP_SEG_INODES_FULL,
				page + FSEG_INODE_PAGE_NODE, mtr);
		flst_add_last(space_header + FSP_SEG_INODES_FREE,
				page + FSEG_INODE_PAGE_NODE, mtr);
	}
	mlog_write_dulint(inode + FSEG_ID, ut_dulint_zero, MLOG_8BYTES, mtr); 
	mlog_write_ulint(inode + FSEG_MAGIC_N, 0, MLOG_4BYTES, mtr); 
	
	if (ULINT_UNDEFINED == fsp_seg_inode_page_find_used(page, mtr)) {
		/* There are no other used headers left on the page: free it */
		flst_remove(space_header + FSP_SEG_INODES_FREE,
				page + FSEG_INODE_PAGE_NODE, mtr);
		fsp_free_page(space, buf_frame_get_page_no(page), mtr);		
	}
}
/**************************************************************************
Returns the file segment inode, page x-latched. */
static
fseg_inode_t*
fseg_inode_get(
/*===========*/
				/* out: segment inode, page x-latched */
	fseg_header_t*	header,	/* in: segment header */
	mtr_t*		mtr)	/* in: mtr handle */
{
	fil_addr_t	inode_addr;
	fseg_inode_t*	inode;
	inode_addr.page = mach_read_from_4(header + FSEG_HDR_PAGE_NO);
	inode_addr.boffset = mach_read_from_2(header + FSEG_HDR_OFFSET);
	
	inode = fut_get_ptr(mach_read_from_4(header + FSEG_HDR_SPACE),
						inode_addr, RW_X_LATCH, mtr);
	
	ut_ad(mach_read_from_4(inode + FSEG_MAGIC_N) == FSEG_MAGIC_N_VALUE);
	return(inode);
}
/**************************************************************************
Gets the page number from the nth fragment page slot. */
UNIV_INLINE
ulint
fseg_get_nth_frag_page_no(
/*======================*/
				/* out: page number, FIL_NULL if not in use */
	fseg_inode_t* 	inode,	/* in: segment inode */
	ulint		n,	/* in: slot index */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ut_ad(inode && mtr);
	ut_ad(n < FSEG_FRAG_ARR_N_SLOTS);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(inode),
							MTR_MEMO_PAGE_X_FIX));
	return(mach_read_from_4(inode + FSEG_FRAG_ARR
						+ n * FSEG_FRAG_SLOT_SIZE));
}
/**************************************************************************
Sets the page number in the nth fragment page slot. */
UNIV_INLINE
void
fseg_set_nth_frag_page_no(
/*======================*/
	fseg_inode_t* 	inode,	/* in: segment inode */
	ulint		n,	/* in: slot index */
	ulint		page_no,/* in: page number to set */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ut_ad(inode && mtr);
	ut_ad(n < FSEG_FRAG_ARR_N_SLOTS);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(inode),
							MTR_MEMO_PAGE_X_FIX));
	mlog_write_ulint(inode + FSEG_FRAG_ARR + n * FSEG_FRAG_SLOT_SIZE,
						page_no, MLOG_4BYTES, mtr);
}
/**************************************************************************
Finds a fragment page slot which is free. */
static
ulint
fseg_find_free_frag_page_slot(
/*==========================*/
				/* out: slot index; ULINT_UNDEFINED if none
				found */
	fseg_inode_t* 	inode,	/* in: segment inode */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ulint	i;
	ulint	page_no;
	ut_ad(inode && mtr);
	for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
		page_no = fseg_get_nth_frag_page_no(inode, i, mtr);
		if (page_no == FIL_NULL) {
			return(i);
		}
	}
	return(ULINT_UNDEFINED);
}
/**************************************************************************
Finds a fragment page slot which is used and last in the array. */
static
ulint
fseg_find_last_used_frag_page_slot(
/*===============================*/
				/* out: slot index; ULINT_UNDEFINED if none
				found */
	fseg_inode_t* 	inode,	/* in: segment inode */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ulint	i;
	ulint	page_no;
	ut_ad(inode && mtr);
	for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
		page_no = fseg_get_nth_frag_page_no(inode,
					FSEG_FRAG_ARR_N_SLOTS - i - 1, mtr);
		if (page_no != FIL_NULL) {
			return(FSEG_FRAG_ARR_N_SLOTS - i - 1);
		}
	}
	return(ULINT_UNDEFINED);
}
/**************************************************************************
Calculates reserved fragment page slots. */
static
ulint
fseg_get_n_frag_pages(
/*==================*/
				/* out: number of fragment pages */
	fseg_inode_t* 	inode,	/* in: segment inode */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ulint	i;
	ulint	count	= 0;
	ut_ad(inode && mtr);
	for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
		if (FIL_NULL != fseg_get_nth_frag_page_no(inode, i, mtr)) {
			count++;
		}
	}
	return(count);
}
/**************************************************************************
Creates a new segment. */
page_t*
fseg_create_general(
/*================*/
			/* out: the page where the segment header is placed,
			x-latched, NULL if could not create segment
			because of lack of space */
	ulint	space,	/* in: space id */
	ulint	page,	/* in: page where the segment header is placed: if
			this is != 0, the page must belong to another segment,
			if this is 0, a new page will be allocated and it
			will belong to the created segment */
	ulint	byte_offset, /* in: byte offset of the created segment header
			on the page */
	ibool	has_done_reservation, /* in: TRUE if the caller has
			already done the reservation for the pages
			with fsp_reserve_free_extents (at least 2 extents:
			one for the inode and, then there other for the
			segment) is no need to do the check for this
			individual operation */
	mtr_t*	mtr)	/* in: mtr */
{
	fsp_header_t*	space_header;
	fseg_inode_t*	inode;
	dulint		seg_id;
	fseg_header_t*	header;
	rw_lock_t*	latch;
	ibool		success;
	page_t*		ret		= NULL;
	ulint		i;
	ut_ad(mtr);
	if (page != 0) {
		header = byte_offset + buf_page_get(space, page, RW_X_LATCH,
									mtr);
	}	
	
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	latch = fil_space_get_latch(space);
	mtr_x_lock(latch, mtr);	
	if (rw_lock_get_x_lock_count(latch) == 1) {
		/* This thread did not own the latch before this call: free
		excess pages from the insert buffer free list */
		ibuf_free_excess_pages(space);
	}
	if (!has_done_reservation) { 
		success = fsp_reserve_free_extents(space, 2, FSP_NORMAL, mtr);
		if (!success) {
			return(NULL);
		}
	}
	space_header = fsp_get_space_header(space, mtr);
	inode = fsp_alloc_seg_inode(space_header, mtr);
	if (inode == NULL) {
		goto funct_exit;
	}
	/* Read the next segment id from space header and increment the
	value in space header */
	seg_id = mtr_read_dulint(space_header + FSP_SEG_ID, MLOG_8BYTES, mtr);
	mlog_write_dulint(space_header + FSP_SEG_ID, ut_dulint_add(seg_id, 1),
							MLOG_8BYTES, mtr);
	mlog_write_dulint(inode + FSEG_ID, seg_id, MLOG_8BYTES, mtr); 
	mlog_write_ulint(inode + FSEG_NOT_FULL_N_USED, 0, MLOG_4BYTES, mtr); 
	flst_init(inode + FSEG_FREE, mtr);
	flst_init(inode + FSEG_NOT_FULL, mtr);
	flst_init(inode + FSEG_FULL, mtr);
	mlog_write_ulint(inode + FSEG_MAGIC_N, FSEG_MAGIC_N_VALUE,
							MLOG_4BYTES, mtr); 
	for (i = 0; i < FSEG_FRAG_ARR_N_SLOTS; i++) {
		fseg_set_nth_frag_page_no(inode, i, FIL_NULL, mtr);
	}
	if (page == 0) {
		page = fseg_alloc_free_page_low(space, inode, 0, FSP_UP, mtr);
		
		if (page == FIL_NULL) {
			fsp_free_seg_inode(space, inode, mtr);
			goto funct_exit;
		}
		header = byte_offset
			 + buf_page_get(space, page, RW_X_LATCH, mtr);
	}	
	mlog_write_ulint(header + FSEG_HDR_OFFSET,
			inode - buf_frame_align(inode), MLOG_2BYTES, mtr);
	mlog_write_ulint(header + FSEG_HDR_PAGE_NO,
			buf_frame_get_page_no(inode), MLOG_4BYTES, mtr);
	mlog_write_ulint(header + FSEG_HDR_SPACE, space, MLOG_4BYTES, mtr);
	ret = buf_frame_align(header);
funct_exit:
	if (!has_done_reservation) { 
	
		fil_space_release_free_extents(space, 2);
	}
	
	return(ret);
}
/**************************************************************************
Creates a new segment. */
page_t*
fseg_create(
/*========*/
			/* out: the page where the segment header is placed,
			x-latched, NULL if could not create segment
			because of lack of space */
	ulint	space,	/* in: space id */
	ulint	page,	/* in: page where the segment header is placed: if
			this is != 0, the page must belong to another segment,
			if this is 0, a new page will be allocated and it
			will belong to the created segment */
	ulint	byte_offset, /* in: byte offset of the created segment header
			on the page */
	mtr_t*	mtr)	/* in: mtr */
{
	return(fseg_create_general(space, page, byte_offset, FALSE, mtr));
}
/**************************************************************************
Calculates the number of pages reserved by a segment, and how many pages are
currently used. */
static
ulint
fseg_n_reserved_pages_low(
/*======================*/
				/* out: number of reserved pages */
	fseg_inode_t* 	inode,	/* in: segment inode */
	ulint*		used,	/* out: number of pages used (<= reserved) */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ulint	ret;
	ut_ad(inode && used && mtr);
	ut_ad(mtr_memo_contains(mtr, buf_block_align(inode),
						MTR_MEMO_PAGE_X_FIX));
	
	*used = mtr_read_ulint(inode + FSEG_NOT_FULL_N_USED, MLOG_4BYTES, mtr)
		+ FSP_EXTENT_SIZE * flst_get_len(inode + FSEG_FULL, mtr)
		+ fseg_get_n_frag_pages(inode, mtr);
	ret = fseg_get_n_frag_pages(inode, mtr)
		+ FSP_EXTENT_SIZE * flst_get_len(inode + FSEG_FREE, mtr)
		+ FSP_EXTENT_SIZE * flst_get_len(inode + FSEG_NOT_FULL, mtr)
		+ FSP_EXTENT_SIZE * flst_get_len(inode + FSEG_FULL, mtr);
	return(ret);
}
/**************************************************************************
Calculates the number of pages reserved by a segment, and how many pages are
currently used. */
ulint
fseg_n_reserved_pages(
/*==================*/
				/* out: number of reserved pages */
	fseg_header_t* 	header,	/* in: segment header */
	ulint*		used,	/* out: number of pages used (<= reserved) */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ulint		ret;
	fseg_inode_t*	inode;
	ulint		space;
	space = buf_frame_get_space_id(header);
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	mtr_x_lock(fil_space_get_latch(space), mtr);	
	inode = fseg_inode_get(header, mtr);
	
	ret = fseg_n_reserved_pages_low(inode, used, mtr);
	return(ret);
}
/*************************************************************************
Tries to fill the free list of a segment with consecutive free extents.
This happens if the segment is big enough to allow extents in the free list,
the free list is empty, and the extents can be allocated consecutively from
the hint onward. */
static
void
fseg_fill_free_list(
/*================*/
	fseg_inode_t*	inode,	/* in: segment inode */
	ulint		space,	/* in: space id */
	ulint		hint,	/* in: hint which extent would be good as
				the first extent */
	mtr_t*		mtr)	/* in: mtr */
{
	xdes_t*	descr;
	ulint	i;
	dulint	seg_id;
	ulint	reserved;
	ulint	used;
		
	ut_ad(inode && mtr);
	reserved = fseg_n_reserved_pages_low(inode, &used, mtr);
	if (reserved < FSEG_FREE_LIST_LIMIT * FSP_EXTENT_SIZE) {
		/* The segment is too small to allow extents in free list */
		return;
	}
	if (flst_get_len(inode + FSEG_FREE, mtr) > 0) {
		/* Free list is not empty */
		return;
	}
		
	for (i = 0; i < FSEG_FREE_LIST_MAX_LEN; i++) {
		descr = xdes_get_descriptor(space, hint, mtr);
		if ((descr == NULL) ||
		    (XDES_FREE != xdes_get_state(descr, mtr))) {
			/* We cannot allocate the desired extent: stop */
		    	return;
		}
		descr = fsp_alloc_free_extent(space, hint, mtr);
		
		xdes_set_state(descr, XDES_FSEG, mtr);
		
		seg_id = mtr_read_dulint(inode + FSEG_ID, MLOG_8BYTES, mtr);
		mlog_write_dulint(descr + XDES_ID, seg_id, MLOG_8BYTES, mtr);
		flst_add_last(inode + FSEG_FREE, descr + XDES_FLST_NODE, mtr);
		hint += FSP_EXTENT_SIZE;
	}
}
/*************************************************************************
Allocates a free extent for the segment: looks first in the free list of the
segment, then tries to allocate from the space free list. NOTE that the extent
returned still resides in the segment free list, it is not yet taken off it! */
static
xdes_t*
fseg_alloc_free_extent(
/*===================*/
				/* out: allocated extent, still placed in the
				segment free list, NULL if could
				not be allocated */
	fseg_inode_t*	inode,	/* in: segment inode */
	ulint		space,	/* in: space id */
	mtr_t*		mtr)	/* in: mtr */
{
	xdes_t*		descr;
	dulint		seg_id;
	fil_addr_t 	first;
		
	if (flst_get_len(inode + FSEG_FREE, mtr) > 0) {
		/* Segment free list is not empty, allocate from it */
		
		first = flst_get_first(inode + FSEG_FREE, mtr);
		descr = xdes_lst_get_descriptor(space, first, mtr);
	} else {
		/* Segment free list was empty, allocate from space */
		descr = fsp_alloc_free_extent(space, 0, mtr);
		if (descr == NULL) {
			return(NULL);
		}
		seg_id = mtr_read_dulint(inode + FSEG_ID, MLOG_8BYTES, mtr);
		
		xdes_set_state(descr, XDES_FSEG, mtr);
		mlog_write_dulint(descr + XDES_ID, seg_id, MLOG_8BYTES, mtr);
		flst_add_last(inode + FSEG_FREE, descr + XDES_FLST_NODE, mtr);
		
		/* Try to fill the segment free list */
		fseg_fill_free_list(inode, space,
			xdes_get_offset(descr) + FSP_EXTENT_SIZE, mtr);
	}
	return(descr);
}
/**************************************************************************
Allocates a single free page from a segment. This function implements
the intelligent allocation strategy which tries to minimize file space
fragmentation. */
static
ulint
fseg_alloc_free_page_low(
/*=====================*/
				/* out: the allocated page number, FIL_NULL
				if no page could be allocated */
	ulint		space,	/* in: space */
	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 */
{
	dulint		seg_id;
	ulint		used;
	ulint		reserved;
	fil_addr_t	first;
	xdes_t*		descr;		/* extent of the hinted page */
	ulint		ret_page;	/* the allocated page offset, FIL_NULL
					if could not be allocated */
	xdes_t*		ret_descr;	/* the extent of the allocated page */
	page_t*		page;
	ibool		frag_page_allocated = FALSE;
	ulint		n;
					
	ut_ad(mtr);
	ut_ad((direction >= FSP_UP) && (direction <= FSP_NO_DIR));
	ut_ad(mach_read_from_4(seg_inode + FSEG_MAGIC_N) ==
							FSEG_MAGIC_N_VALUE);
	seg_id = mtr_read_dulint(seg_inode + FSEG_ID, MLOG_8BYTES, mtr);
	ut_ad(ut_dulint_cmp(seg_id, ut_dulint_zero) > 0);
	
	reserved = fseg_n_reserved_pages_low(seg_inode, &used, mtr);
	
	descr = xdes_get_descriptor(space, hint, mtr);
	if (descr == NULL) {
		/* Hint outside space or too high above free limit: reset
		hint */
		hint = 0;
		descr = xdes_get_descriptor(space, hint, mtr);
	}
 
	/* In the big if-else below we look for ret_page and ret_descr */
	/*-------------------------------------------------------------*/ 
	if ((xdes_get_state(descr, mtr) == XDES_FSEG)
	           && (0 == ut_dulint_cmp(mtr_read_dulint(descr + XDES_ID,
							MLOG_8BYTES, mtr),
							seg_id))
	           && (xdes_get_bit(descr, XDES_FREE_BIT,
				hint % FSP_EXTENT_SIZE, mtr) == TRUE)) {
		/* 1. We can take the hinted page
		=================================*/
		ret_descr = descr;
		ret_page = hint;
	/*-------------------------------------------------------------*/ 
	} else if ((xdes_get_state(descr, mtr) == XDES_FREE)
		   && ((reserved - used) < reserved / FSEG_FILLFACTOR)
		   && (used >= FSEG_FRAG_LIMIT)) {
		/* 2. We allocate the free extent from space and can take
		=========================================================
		the hinted page
		===============*/
		ret_descr = fsp_alloc_free_extent(space, hint, mtr);
		ut_a(ret_descr == descr);
		
		xdes_set_state(ret_descr, XDES_FSEG, mtr);
		mlog_write_dulint(ret_descr + XDES_ID, seg_id, MLOG_8BYTES,
									mtr);
		flst_add_last(seg_inode + FSEG_FREE,
					ret_descr + XDES_FLST_NODE, mtr);
		/* Try to fill the segment free list */
		fseg_fill_free_list(seg_inode, space,
					hint + FSP_EXTENT_SIZE, mtr);
		ret_page = hint;
	/*-------------------------------------------------------------*/ 
	} else if ((direction != FSP_NO_DIR)
		   && ((reserved - used) < reserved / FSEG_FILLFACTOR)
		   && (used >= FSEG_FRAG_LIMIT)
		   && (NULL != (ret_descr =
			fseg_alloc_free_extent(seg_inode, space, mtr)))) {
		/* 3. We take any free extent (which was already assigned above
		===============================================================
		in the if-condition to ret_descr) and take the lowest or
		========================================================
		highest page in it, depending on the direction
		==============================================*/
		ret_page = xdes_get_offset(ret_descr);	
		if (direction == FSP_DOWN) {
			ret_page += FSP_EXTENT_SIZE - 1;
		}
	/*-------------------------------------------------------------*/ 
	} else if ((xdes_get_state(descr, mtr) == XDES_FSEG)
	           && (0 == ut_dulint_cmp(mtr_read_dulint(descr + XDES_ID,
							MLOG_8BYTES, mtr),
						seg_id))
	           && (!xdes_is_full(descr, mtr))) {
		/* 4. We can take the page from the same extent as the
		======================================================
		hinted page (and the extent already belongs to the
		==================================================
		segment)
		========*/
		ret_descr = descr;
		ret_page = xdes_get_offset(ret_descr) +
				xdes_find_bit(ret_descr, XDES_FREE_BIT, TRUE,
					hint % FSP_EXTENT_SIZE, mtr);
	/*-------------------------------------------------------------*/ 
	} else if (reserved - used > 0) {
		/* 5. We take any unused page from the segment
		==============================================*/
		if (flst_get_len(seg_inode + FSEG_NOT_FULL, mtr) > 0) {
			first = flst_get_first(seg_inode + FSEG_NOT_FULL,
									mtr);
		} else if (flst_get_len(seg_inode + FSEG_FREE, mtr) > 0) {
			first = flst_get_first(seg_inode + FSEG_FREE, mtr);
		} else {
			ut_error;
		}
		ret_descr = xdes_lst_get_descriptor(space, first, mtr);
		ret_page = xdes_get_offset(ret_descr) +
				xdes_find_bit(ret_descr, XDES_FREE_BIT, TRUE,
								0, mtr);
	/*-------------------------------------------------------------*/ 
	} else if (used < FSEG_FRAG_LIMIT) {
		/* 6. We allocate an individual page from the space
		===================================================*/
		ret_page = fsp_alloc_free_page(space, hint, mtr);
		ret_descr = NULL;
		
		frag_page_allocated = TRUE;
		
		if (ret_page != FIL_NULL) {
			/* Put the page in the fragment page array of the
			segment */
			n = fseg_find_free_frag_page_slot(seg_inode, mtr);
			ut_a(n != FIL_NULL);
			fseg_set_nth_frag_page_no(seg_inode, n, ret_page,
									mtr);
		}
	/*-------------------------------------------------------------*/ 
	} else {
		/* 7. We allocate a new extent and take its first page
		======================================================*/
		ret_descr = fseg_alloc_free_extent(seg_inode, space, mtr);
		if (ret_descr == NULL) {
			ret_page = FIL_NULL;
		} else {
			ret_page = xdes_get_offset(ret_descr);
		}	
	}
	
	if (ret_page == FIL_NULL) {
		/* Page could not be allocated */
	
		return(FIL_NULL);
	}
	if (!frag_page_allocated) {
		/* Initialize the allocated page to buffer pool, so that it
		can be obtained immediately with buf_page_get without need
		for a disk read */
	
		page = buf_page_create(space, ret_page, mtr);
		ut_a(page == buf_page_get(space, ret_page, RW_X_LATCH, mtr));
		buf_page_dbg_add_level(page, SYNC_FSP_PAGE);
		/* The prior contents of the page should be ignored */
		fsp_init_file_page(page, mtr);
	
		/* At this point we know the extent and the page offset.
		The extent is still in the appropriate list (FSEG_NOT_FULL
		or FSEG_FREE), and the page is not yet marked as used. */
		
		ut_ad(xdes_get_descriptor(space, ret_page, mtr) == ret_descr);
		ut_ad(xdes_get_bit(ret_descr, XDES_FREE_BIT,
				ret_page % FSP_EXTENT_SIZE, mtr) == TRUE);
		
		fseg_mark_page_used(seg_inode, space, ret_page, mtr);
	}
	return(ret_page);	
}
/**************************************************************************
Allocates a single free page from a segment. This function implements
the intelligent allocation strategy which tries to minimize file space
fragmentation. */
ulint
fseg_alloc_free_page_general(
/*=========================*/
				/* out: allocated page offset, FIL_NULL if no
				page could be allocated */
	fseg_header_t*	seg_header,/* in: segment header */
	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 */
	ibool		has_done_reservation, /* in: TRUE if the caller has
				already done the reservation for the page
				with fsp_reserve_free_extents, then there
				is no need to do the check for this individual
				page */
	mtr_t*		mtr)	/* in: mtr handle */
{
	fseg_inode_t*	inode;
	ulint		space;
	rw_lock_t*	latch;
	ibool		success;
	ulint		page_no;
	space = buf_frame_get_space_id(seg_header);
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	latch = fil_space_get_latch(space);
	mtr_x_lock(latch, mtr);	
	
	if (rw_lock_get_x_lock_count(latch) == 1) {
		/* This thread did not own the latch before this call: free
		excess pages from the insert buffer free list */
		ibuf_free_excess_pages(space);
	}
	inode = fseg_inode_get(seg_header, mtr);
	if (!has_done_reservation) {
		success = fsp_reserve_free_extents(space, 2, FSP_NORMAL, mtr);
		if (!success) {
			return(FIL_NULL);
		}
	}
	page_no = fseg_alloc_free_page_low(buf_frame_get_space_id(inode),
					inode, hint, direction, mtr);
	if (!has_done_reservation) {
		fil_space_release_free_extents(space, 2);
	}
	return(page_no);
}
/**************************************************************************
Allocates a single free page from a segment. This function implements
the intelligent allocation strategy which tries to minimize file space
fragmentation. */
ulint
fseg_alloc_free_page(
/*=================*/
				/* out: allocated page offset, FIL_NULL if no
				page could be allocated */
	fseg_header_t*	seg_header,/* in: segment header */
	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 */
{
	return(fseg_alloc_free_page_general(seg_header, hint, direction,
								FALSE, mtr));
}
/**************************************************************************
Reserves free pages from a tablespace. All mini-transactions which may
use several pages from the tablespace should call this function beforehand
and reserve enough free extents so that they certainly will be able
to do their operation, like a B-tree page split, fully. Reservations
must be released with function fil_space_release_free_extents!
The alloc_type below has the following meaning: FSP_NORMAL means an
operation which will probably result in more space usage, like an
insert in a B-tree; FSP_UNDO means allocation to undo logs: if we are
deleting rows, then this allocation will in the long run result in
less space usage (after a purge); FSP_CLEANING means allocation done
in a physical record delete (like in a purge) or other cleaning operation
which will result in less space usage in the long run. We prefer the latter
two types of allocation: when space is scarce, FSP_NORMAL allocations
will not succeed, but the latter two allocations will succeed, if possible.
The purpose is to avoid dead end where the database is full but the
user cannot free any space because these freeing operations temporarily
reserve some space. */ 
ibool
fsp_reserve_free_extents(
/*=====================*/
			/* out: TRUE if we were able to make the reservation */
	ulint	space,	/* in: space id */
	ulint	n_ext,	/* in: number of extents to reserve */
	ulint	alloc_type,/* in: FSP_NORMAL, FSP_UNDO, or FSP_CLEANING */
	mtr_t*	mtr)	/* in: mtr */
{
	fsp_header_t*	space_header;
	ulint		n_free_list_ext;
	ulint		free_limit;
	ulint		size;
	ulint		n_free;
	ulint		n_free_up;
	ulint		reserve;
	rw_lock_t*	latch;
	ut_ad(mtr);	
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	latch = fil_space_get_latch(space);
	mtr_x_lock(latch, mtr);
	space_header = fsp_get_space_header(space, mtr);
	size = mtr_read_ulint(space_header + FSP_SIZE, MLOG_4BYTES, mtr);
	
	n_free_list_ext = flst_get_len(space_header + FSP_FREE, mtr);
	
	free_limit = mtr_read_ulint(space_header + FSP_FREE_LIMIT,
							MLOG_4BYTES, mtr);
	/* Below we play safe when counting free extents above the free limit:
	some of them will contain extent descriptor pages, and therefore
	will not be free extents */
	n_free_up = (size - free_limit) / FSP_EXTENT_SIZE;
	if (n_free_up > 0) {
		n_free_up--;
		n_free_up = n_free_up - n_free_up
				/ (XDES_DESCRIBED_PER_PAGE / FSP_EXTENT_SIZE);
	}
	
	n_free = n_free_list_ext + n_free_up;
	if (alloc_type == FSP_NORMAL) {
		/* We reserve 1 extent + 4 % of the space size to undo logs
		and 1 extent + 1 % to cleaning operations; NOTE: this source
		code is duplicated in the function below! */
		reserve = 2 + ((size / FSP_EXTENT_SIZE) * 5) / 100;
		if (n_free <= reserve + n_ext) {
			return(FALSE);
		}
	} else if (alloc_type == FSP_UNDO) {
		/* We reserve 1 % of the space size to cleaning operations */
		reserve = 1 + ((size / FSP_EXTENT_SIZE) * 1) / 100;
		if (n_free <= reserve + n_ext) {
			return(FALSE);
		}
	} else {
		ut_a(alloc_type == FSP_CLEANING);
	}
	return(fil_space_reserve_free_extents(space, n_free, n_ext));
}
/**************************************************************************
This function should be used to get information on how much we still
will be able to insert new data to the database without running out the
tablespace. Only free extents are taken into account and we also subtract
the safety margin required by the above function fsp_reserve_free_extents. */
ulint
fsp_get_available_space_in_free_extents(
/*====================================*/
			/* out: available space in kB */
	ulint	space)	/* in: space id */
{
	fsp_header_t*	space_header;
	ulint		n_free_list_ext;
	ulint		free_limit;
	ulint		size;
	ulint		n_free;
	ulint		n_free_up;
	ulint		reserve;
	rw_lock_t*	latch;
	mtr_t		mtr;
	
	ut_ad(!mutex_own(&kernel_mutex));
	mtr_start(&mtr);
	
	latch = fil_space_get_latch(space);
	mtr_x_lock(latch, &mtr);
	space_header = fsp_get_space_header(space, &mtr);
	size = mtr_read_ulint(space_header + FSP_SIZE, MLOG_4BYTES, &mtr);
	
	n_free_list_ext = flst_get_len(space_header + FSP_FREE, &mtr);
	
	free_limit = mtr_read_ulint(space_header + FSP_FREE_LIMIT,
							MLOG_4BYTES, &mtr);
	mtr_commit(&mtr);
	/* Below we play safe when counting free extents above the free limit:
	some of them will contain extent descriptor pages, and therefore
	will not be free extents */
	n_free_up = (size - free_limit) / FSP_EXTENT_SIZE;
	if (n_free_up > 0) {
		n_free_up--;
		n_free_up = n_free_up - n_free_up
				/ (XDES_DESCRIBED_PER_PAGE / FSP_EXTENT_SIZE);
	}
	
	n_free = n_free_list_ext + n_free_up;
	/* We reserve 1 extent + 4 % of the space size to undo logs
	and 1 extent + 1 % to cleaning operations; NOTE: this source
	code is duplicated in the function above! */
	reserve = 2 + ((size / FSP_EXTENT_SIZE) * 5) / 100;
	if (reserve > n_free) {
		return(0);
	}
	return(((n_free - reserve) * FSP_EXTENT_SIZE)
					* (UNIV_PAGE_SIZE / 1024));
}
	
/************************************************************************
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		page,	/* in: page offset */
	mtr_t*		mtr)	/* in: mtr */
{
	xdes_t*	descr;
	ulint	not_full_n_used;
	ut_ad(seg_inode && mtr);
	
	descr = xdes_get_descriptor(space, page, mtr);
	
	ut_ad(mtr_read_ulint(seg_inode + FSEG_ID, MLOG_4BYTES, mtr) ==
		mtr_read_ulint(descr + XDES_ID, MLOG_4BYTES, mtr));
	if (xdes_is_free(descr, mtr)) {
		/* We move the extent from the free list to the
		NOT_FULL list */
		flst_remove(seg_inode + FSEG_FREE, descr + XDES_FLST_NODE,
									mtr);
		flst_add_last(seg_inode + FSEG_NOT_FULL,
						descr + XDES_FLST_NODE, mtr);
	}
	ut_ad(xdes_get_bit(descr, XDES_FREE_BIT, page % FSP_EXTENT_SIZE, mtr)
								== TRUE);
	/* We mark the page as used */
	xdes_set_bit(descr, XDES_FREE_BIT, page % FSP_EXTENT_SIZE, FALSE, mtr);
	not_full_n_used = mtr_read_ulint(seg_inode + FSEG_NOT_FULL_N_USED,
							MLOG_4BYTES, mtr);
	not_full_n_used++;
	mlog_write_ulint(seg_inode + FSEG_NOT_FULL_N_USED, not_full_n_used,
							MLOG_4BYTES, mtr);
	if (xdes_is_full(descr, mtr)) {
		/* We move the extent from the NOT_FULL list to the
		FULL list */
		flst_remove(seg_inode + FSEG_NOT_FULL,
						descr + XDES_FLST_NODE, mtr);
		flst_add_last(seg_inode + FSEG_FULL,
						descr + XDES_FLST_NODE, mtr);
			
		mlog_write_ulint(seg_inode + FSEG_NOT_FULL_N_USED,
					not_full_n_used - FSP_EXTENT_SIZE,
							MLOG_4BYTES, mtr);
	}
}
/**************************************************************************
Frees a single page of a segment. */
static
void
fseg_free_page_low(
/*===============*/
	fseg_inode_t*	seg_inode, /* in: segment inode */
	ulint		space,	/* in: space id */
	ulint		page,	/* in: page offset */
	mtr_t*		mtr)	/* in: mtr handle */
{
	xdes_t*	descr;
	ulint	not_full_n_used;
	ulint	state;
	ulint	i;
	
	ut_ad(seg_inode && mtr);
	ut_ad(mach_read_from_4(seg_inode + FSEG_MAGIC_N) ==
							FSEG_MAGIC_N_VALUE);
	/* Drop search system page hash index if the page is found in
	the pool and is hashed */
	btr_search_drop_page_hash_when_freed(space, page);
	descr = xdes_get_descriptor(space, page, mtr);
	ut_a(descr);
	ut_a(xdes_get_bit(descr, XDES_FREE_BIT, page % FSP_EXTENT_SIZE, mtr)
								== FALSE);
	state = xdes_get_state(descr, mtr);
	if (state != XDES_FSEG) {
		/* The page is in the fragment pages of the segment */
		for (i = 0;; i++) {
			if (fseg_get_nth_frag_page_no(seg_inode, i, mtr)
			    == page) {
				fseg_set_nth_frag_page_no(seg_inode, i,
							FIL_NULL, mtr);
				break;
			}
		}
		fsp_free_page(space, page, mtr);
				
		return;
	}
	/* If we get here, the page is in some extent of the segment */	
	ut_a(0 == ut_dulint_cmp(
		mtr_read_dulint(descr + XDES_ID, MLOG_8BYTES, mtr),
		mtr_read_dulint(seg_inode + FSEG_ID, MLOG_8BYTES, mtr)));
	not_full_n_used = mtr_read_ulint(seg_inode + FSEG_NOT_FULL_N_USED,
							MLOG_4BYTES, mtr);
	if (xdes_is_full(descr, mtr)) {
		/* The fragment is full: move it to another list */
		flst_remove(seg_inode + FSEG_FULL,
						descr + XDES_FLST_NODE, mtr);
		flst_add_last(seg_inode + FSEG_NOT_FULL,
						descr + XDES_FLST_NODE, mtr);
		mlog_write_ulint(seg_inode + FSEG_NOT_FULL_N_USED,
					not_full_n_used + FSP_EXTENT_SIZE - 1,
							MLOG_4BYTES, mtr);
	} else {
		ut_a(not_full_n_used > 0);
		mlog_write_ulint(seg_inode + FSEG_NOT_FULL_N_USED,
					not_full_n_used - 1, MLOG_4BYTES, mtr);
	}
	xdes_set_bit(descr, XDES_FREE_BIT, page % FSP_EXTENT_SIZE, TRUE, mtr);
	xdes_set_bit(descr, XDES_CLEAN_BIT, page % FSP_EXTENT_SIZE, TRUE, mtr);
	if (xdes_is_free(descr, mtr)) {
	    	/* The extent has become free: free it to space */
		flst_remove(seg_inode + FSEG_NOT_FULL,
						descr + XDES_FLST_NODE, mtr);
		fsp_free_extent(space, page, mtr);
	}		
}
/**************************************************************************
Frees a single page of a segment. */
void
fseg_free_page(
/*===========*/
	fseg_header_t*	seg_header, /* in: segment header */
	ulint		space,	/* in: space id */
	ulint		page,	/* in: page offset */
	mtr_t*		mtr)	/* in: mtr handle */
{
	fseg_inode_t*	seg_inode;
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	mtr_x_lock(fil_space_get_latch(space), mtr);	
	seg_inode = fseg_inode_get(seg_header, mtr);
	fseg_free_page_low(seg_inode, space, page, 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		page,	/* in: a page in the extent */
	mtr_t*		mtr)	/* in: mtr handle */
{
	ulint	first_page_in_extent;
	xdes_t*	descr;
	ulint	not_full_n_used;
	ulint	descr_n_used;
	ulint	i;
	
	ut_ad(seg_inode && mtr);
	descr = xdes_get_descriptor(space, page, mtr);
	ut_a(xdes_get_state(descr, mtr) == XDES_FSEG);
	ut_a(0 == ut_dulint_cmp(
		mtr_read_dulint(descr + XDES_ID, MLOG_8BYTES, mtr),
	     	mtr_read_dulint(seg_inode + FSEG_ID, MLOG_8BYTES, mtr)));
	first_page_in_extent = page - (page % FSP_EXTENT_SIZE);
	     	
	for (i = 0; i < FSP_EXTENT_SIZE; i++) {
		if (FALSE == xdes_get_bit(descr, XDES_FREE_BIT, i, mtr)) {
			/* Drop search system page hash index if the page is
			found in the pool and is hashed */
			btr_search_drop_page_hash_when_freed(space,
					first_page_in_extent + i);
		}
	}
	if (xdes_is_full(descr, mtr)) {
		flst_remove(seg_inode + FSEG_FULL,
				descr + XDES_FLST_NODE, mtr);
	} else if (xdes_is_free(descr, mtr)) {
		flst_remove(seg_inode + FSEG_FREE,
				descr + XDES_FLST_NODE, mtr);
	} else {
		flst_remove(seg_inode + FSEG_NOT_FULL,
				descr + XDES_FLST_NODE, mtr);
		not_full_n_used = mtr_read_ulint(
					seg_inode + FSEG_NOT_FULL_N_USED,
					MLOG_4BYTES, mtr);
		descr_n_used = xdes_get_n_used(descr, mtr);
		ut_a(not_full_n_used >= descr_n_used);
		mlog_write_ulint(seg_inode + FSEG_NOT_FULL_N_USED,
				not_full_n_used - descr_n_used,
				MLOG_4BYTES, mtr);
	}
	fsp_free_extent(space, page, mtr);
}
/**************************************************************************
Frees part of a segment. This function can be used to free a segment by
repeatedly calling this function in different mini-transactions. Doing
the freeing in a single mini-transaction might result in too big a
mini-transaction. */
ibool
fseg_free_step(
/*===========*/
				/* out: TRUE if freeing completed */
	fseg_header_t*	header,	/* in, own: segment header; NOTE: if the header
				resides on the first page of the frag list
				of the segment, this pointer becomes obsolete
				after the last freeing step */
	mtr_t*		mtr)	/* in: mtr */
{
	ulint		n;
	ulint		page;
	xdes_t*		descr;
	fseg_inode_t*	inode;
	ulint		space;
	space = buf_frame_get_space_id(header);
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	mtr_x_lock(fil_space_get_latch(space), mtr);	
	inode = fseg_inode_get(header, mtr);
	descr = fseg_get_first_extent(inode, mtr);
	if (descr != NULL) {
		/* Free the extent held by the segment */
		page = xdes_get_offset(descr);
		fseg_free_extent(inode, space, page, mtr);
	
		return(FALSE);
	}
	/* Free a frag page */
	n = fseg_find_last_used_frag_page_slot(inode, mtr);
	if (n == ULINT_UNDEFINED) {
		/* Freeing completed: free the segment inode */
		fsp_free_seg_inode(space, inode, mtr);
		return(TRUE);
	}
	fseg_free_page_low(inode, space,
			fseg_get_nth_frag_page_no(inode, n, mtr), mtr);
	return(FALSE);
}
/**************************************************************************
Frees part of a segment. Differs from fseg_free_step because this function
leaves the header page unfreed. */
ibool
fseg_free_step_not_header(
/*======================*/
				/* out: TRUE if freeing completed, except the
				header page */
	fseg_header_t*	header,	/* in: segment header which must reside on
				the first fragment page of the segment */
	mtr_t*		mtr)	/* in: mtr */
{
	ulint		n;
	ulint		page;
	xdes_t*		descr;
	fseg_inode_t*	inode;
	ulint		space;
	ulint		page_no;
	space = buf_frame_get_space_id(header);
	
	ut_ad(!mutex_own(&kernel_mutex)
	      || mtr_memo_contains(mtr, fil_space_get_latch(space),
							MTR_MEMO_X_LOCK));
	mtr_x_lock(fil_space_get_latch(space), mtr);	
	inode = fseg_inode_get(header, mtr);
	descr = fseg_get_first_extent(inode, mtr);
	if (descr != NULL) {
		/* Free the extent held by the segment */
		page = xdes_get_offset(descr);
		fseg_free_extent(inode, space, page, mtr);
	
		return(FALSE);
	}
	/* Free a frag page */
	n = fseg_find_last_used_frag_page_slot(inode, mtr);
	if (n == ULINT_UNDEFINED) {
		ut_error;
	}
	page_no = fseg_get_nth_frag_page_no(inode, n, mtr);
	
	if (page_no == buf_frame_get_page_no(header)) {
		return(TRUE);
	}
	
	fseg_free_page_low(inode, space, page_no, mtr);
	return(FALSE);
}
/***********************************************************************
Frees a segment. The freeing is performed in several mini-transactions,
so that there is no danger of bufferfixing too many buffer pages. */
void
fseg_free(
/*======*/
	ulint	space,	/* in: space id */
	ulint	page_no,/* in: page number where the segment header is
			placed */
	ulint	offset) /* in: byte offset of the segment header on that
			page */
{
	mtr_t		mtr;
	ibool		finished;
	fseg_header_t*	header;
	fil_addr_t	addr;
	addr.page = page_no;
	addr.boffset = offset;
	for (;;) {
		mtr_start(&mtr);
		header = fut_get_ptr(space, addr, RW_X_LATCH, &mtr);
		finished = fseg_free_step(header, &mtr);
	
		mtr_commit(&mtr);
		if (finished) {
			return;
		}
	}
}
/**************************************************************************
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. */
static
xdes_t*
fseg_get_first_extent(
/*==================*/
				/* out: the first extent descriptor, or NULL if
				none */
	fseg_inode_t*	inode,	/* in: segment inode */
	mtr_t*		mtr)	/* in: mtr */
{
	fil_addr_t	first;
	ulint		space;
	xdes_t*		descr;
	
	ut_ad(inode && mtr);
	space = buf_frame_get_space_id(inode);
	first = fil_addr_null;
	
	if (flst_get_len(inode + FSEG_FULL, mtr) > 0) {
		first = flst_get_first(inode + FSEG_FULL, mtr);
	} else if (flst_get_len(inode + FSEG_NOT_FULL, mtr) > 0) {
		first = flst_get_first(inode + FSEG_NOT_FULL, mtr);
	} else if (flst_get_len(inode + FSEG_FREE, mtr) > 0) {
		first = flst_get_first(inode + FSEG_FREE, mtr);
	}
	if (first.page == FIL_NULL) {
		return(NULL);
	}
	descr = xdes_lst_get_descriptor(space, first, mtr);
	return(descr);
}
/***********************************************************************
Validates a segment. */
static
ibool
fseg_validate_low(
/*==============*/
				/* out: TRUE if ok */
	fseg_inode_t*	inode, /* in: segment inode */
	mtr_t*		mtr2)	/* in: mtr */
{
	ulint		space;
	dulint		seg_id;
	mtr_t		mtr;
	xdes_t*		descr;
	fil_addr_t	node_addr;
	ulint		n_used		= 0;
	ulint		n_used2		= 0;
	
	ut_ad(mtr_memo_contains(mtr2, buf_block_align(inode),
							MTR_MEMO_PAGE_X_FIX));
	ut_ad(mach_read_from_4(inode + FSEG_MAGIC_N) == FSEG_MAGIC_N_VALUE);
	space = buf_frame_get_space_id(inode);
	
	seg_id = mtr_read_dulint(inode + FSEG_ID, MLOG_8BYTES, mtr2); 
	n_used = mtr_read_ulint(inode + FSEG_NOT_FULL_N_USED,
							MLOG_4BYTES, mtr2); 
	flst_validate(inode + FSEG_FREE, mtr2);
	flst_validate(inode + FSEG_NOT_FULL, mtr2);
	flst_validate(inode + FSEG_FULL, mtr2);
	/* Validate FSEG_FREE list */
	node_addr = flst_get_first(inode + FSEG_FREE, mtr2);
	while (!fil_addr_is_null(node_addr)) {
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);	
		descr = xdes_lst_get_descriptor(space, node_addr, &mtr);
		ut_a(xdes_get_n_used(descr, &mtr) == 0);
		ut_a(xdes_get_state(descr, &mtr) == XDES_FSEG);
		ut_a(0 == ut_dulint_cmp(
			mtr_read_dulint(descr + XDES_ID, MLOG_8BYTES,
					&mtr), seg_id));
		node_addr = flst_get_next_addr(descr + XDES_FLST_NODE, &mtr);
		mtr_commit(&mtr);
	}
	/* Validate FSEG_NOT_FULL list */
	node_addr = flst_get_first(inode + FSEG_NOT_FULL, mtr2);
	while (!fil_addr_is_null(node_addr)) {
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);	
		descr = xdes_lst_get_descriptor(space, node_addr, &mtr);
		ut_a(xdes_get_n_used(descr, &mtr) > 0);
		ut_a(xdes_get_n_used(descr, &mtr) < FSP_EXTENT_SIZE);
		ut_a(xdes_get_state(descr, &mtr) == XDES_FSEG);
		ut_a(0 == ut_dulint_cmp(
			mtr_read_dulint(descr + XDES_ID, MLOG_8BYTES,
					&mtr), seg_id));
		n_used2 += xdes_get_n_used(descr, &mtr);
		node_addr = flst_get_next_addr(descr + XDES_FLST_NODE, &mtr);
		mtr_commit(&mtr);
	}
	/* Validate FSEG_FULL list */
	node_addr = flst_get_first(inode + FSEG_FULL, mtr2);
	while (!fil_addr_is_null(node_addr)) {
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);	
		descr = xdes_lst_get_descriptor(space, node_addr, &mtr);
		ut_a(xdes_get_n_used(descr, &mtr) == FSP_EXTENT_SIZE);
		ut_a(xdes_get_state(descr, &mtr) == XDES_FSEG);
		ut_a(0 == ut_dulint_cmp(
			mtr_read_dulint(descr + XDES_ID, MLOG_8BYTES,
					&mtr), seg_id));
		node_addr = flst_get_next_addr(descr + XDES_FLST_NODE, &mtr);
		mtr_commit(&mtr);
	}
	ut_a(n_used == n_used2);
	return(TRUE);
}
	
/***********************************************************************
Validates a segment. */
ibool
fseg_validate(
/*==========*/
				/* out: TRUE if ok */
	fseg_header_t*	header, /* in: segment header */
	mtr_t*		mtr2)	/* in: mtr */
{
	fseg_inode_t*	inode;
	ibool		ret;
	ulint		space;
	space = buf_frame_get_space_id(header);
	mtr_x_lock(fil_space_get_latch(space), mtr2);	
	inode = fseg_inode_get(header, mtr2);
	ret = fseg_validate_low(inode, mtr2);
	return(ret);
}
/***********************************************************************
Writes info of a segment. */
static
void
fseg_print_low(
/*===========*/
	fseg_inode_t*	inode, /* in: segment inode */
	mtr_t*		mtr)	/* in: mtr */
{
	ulint	space;
	ulint	seg_id_low;
	ulint	seg_id_high;
	ulint	n_used;
	ulint	n_frag;
	ulint	n_free;
	ulint	n_not_full;
	ulint	n_full;
	ulint	reserved;
	ulint	used;
	ulint	page_no;
	dulint   d_var;
	
	ut_ad(mtr_memo_contains(mtr, buf_block_align(inode),
							MTR_MEMO_PAGE_X_FIX));
	space = buf_frame_get_space_id(inode);
	page_no = buf_frame_get_page_no(inode);
	reserved = fseg_n_reserved_pages_low(inode, &used, mtr);
	d_var = mtr_read_dulint(inode + FSEG_ID, MLOG_8BYTES, mtr);	
	seg_id_low = ut_dulint_get_low(d_var);
	seg_id_high = ut_dulint_get_high(d_var);
	
	n_used = mtr_read_ulint(inode + FSEG_NOT_FULL_N_USED,
							MLOG_4BYTES, mtr); 
	n_frag = fseg_get_n_frag_pages(inode, mtr);
	n_free = flst_get_len(inode + FSEG_FREE, mtr);
	n_not_full = flst_get_len(inode + FSEG_NOT_FULL, mtr);
	n_full = flst_get_len(inode + FSEG_FULL, mtr);
	printf(
    "SEGMENT id %lu %lu space %lu; page %lu; res %lu used %lu; full ext %lun",
		seg_id_high, seg_id_low, space, page_no, reserved, used,
		n_full);
	printf(
    "fragm pages %lu; free extents %lu; not full extents %lu: pages %lun",
		n_frag, n_free, n_not_full, n_used);
}
/***********************************************************************
Writes info of a segment. */
void
fseg_print(
/*=======*/
	fseg_header_t*	header, /* in: segment header */
	mtr_t*		mtr)	/* in: mtr */
{
	fseg_inode_t*	inode;
	ulint		space;
	space = buf_frame_get_space_id(header);
	mtr_x_lock(fil_space_get_latch(space), mtr);	
	inode = fseg_inode_get(header, mtr);
	fseg_print_low(inode, mtr);
}
/***********************************************************************
Validates the file space system and its segments. */
ibool
fsp_validate(
/*=========*/
			/* out: TRUE if ok */
	ulint	space)	/* in: space id */
{
	fsp_header_t*	header;
	fseg_inode_t*	seg_inode;
	page_t*		seg_inode_page;
	ulint		size;
	ulint		free_limit;
	ulint		frag_n_used;
	mtr_t		mtr;
	mtr_t		mtr2;
	xdes_t*		descr;
	fil_addr_t	node_addr;
	fil_addr_t	next_node_addr;
	ulint		descr_count	= 0;
	ulint		n_used		= 0;
	ulint		n_used2		= 0;
	ulint		n_full_frag_pages;
	ulint		n;
	ulint		seg_inode_len_free;
	ulint		seg_inode_len_full;
	
	/* Start first a mini-transaction mtr2 to lock out all other threads
	from the fsp system */
	mtr_start(&mtr2);
	mtr_x_lock(fil_space_get_latch(space), &mtr2);	
	
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	
	header = fsp_get_space_header(space, &mtr);
	size = mtr_read_ulint(header + FSP_SIZE, MLOG_4BYTES, &mtr); 
	free_limit = mtr_read_ulint(header + FSP_FREE_LIMIT,
					MLOG_4BYTES, &mtr); 
	frag_n_used = mtr_read_ulint(header + FSP_FRAG_N_USED,
					MLOG_4BYTES, &mtr); 
	n_full_frag_pages = FSP_EXTENT_SIZE *
				flst_get_len(header + FSP_FULL_FRAG, &mtr);
					
	ut_a(free_limit <= size);
					
	flst_validate(header + FSP_FREE, &mtr);
	flst_validate(header + FSP_FREE_FRAG, &mtr);
	flst_validate(header + FSP_FULL_FRAG, &mtr);
	mtr_commit(&mtr);
	/* Validate FSP_FREE list */
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_FREE, &mtr);
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);	
		descr_count++;
		descr = xdes_lst_get_descriptor(space, node_addr, &mtr);
		ut_a(xdes_get_n_used(descr, &mtr) == 0);
		ut_a(xdes_get_state(descr, &mtr) == XDES_FREE);
		node_addr = flst_get_next_addr(descr + XDES_FLST_NODE, &mtr);
		mtr_commit(&mtr);
	}
	/* Validate FSP_FREE_FRAG list */
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_FREE_FRAG, &mtr);
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);	
		descr_count++;
		descr = xdes_lst_get_descriptor(space, node_addr, &mtr);
		ut_a(xdes_get_n_used(descr, &mtr) > 0);
		ut_a(xdes_get_n_used(descr, &mtr) < FSP_EXTENT_SIZE);
		ut_a(xdes_get_state(descr, &mtr) == XDES_FREE_FRAG);
		n_used += xdes_get_n_used(descr, &mtr);
		node_addr = flst_get_next_addr(descr + XDES_FLST_NODE, &mtr);
		mtr_commit(&mtr);
	}
	/* Validate FSP_FULL_FRAG list */
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_FULL_FRAG, &mtr);
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);	
		descr_count++;
		descr = xdes_lst_get_descriptor(space, node_addr, &mtr);
		ut_a(xdes_get_n_used(descr, &mtr) == FSP_EXTENT_SIZE);
		ut_a(xdes_get_state(descr, &mtr) == XDES_FULL_FRAG);
		node_addr = flst_get_next_addr(descr + XDES_FLST_NODE, &mtr);
		mtr_commit(&mtr);
	}
	
	/* Validate segments */
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_SEG_INODES_FULL, &mtr);	
	seg_inode_len_full = flst_get_len(header + FSP_SEG_INODES_FULL, &mtr);
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
	    for (n = 0; n < FSP_SEG_INODES_PER_PAGE; n++) {	
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);
		seg_inode_page = fut_get_ptr(space, node_addr, RW_X_LATCH,
						&mtr) - FSEG_INODE_PAGE_NODE;
		seg_inode = fsp_seg_inode_page_get_nth_inode(seg_inode_page,
								n, &mtr);
		ut_a(ut_dulint_cmp(mach_read_from_8(seg_inode + FSEG_ID),
						ut_dulint_zero) != 0);
		fseg_validate_low(seg_inode, &mtr);
		descr_count += flst_get_len(seg_inode + FSEG_FREE, &mtr);
		descr_count += flst_get_len(seg_inode + FSEG_FULL, &mtr);
		descr_count += flst_get_len(seg_inode + FSEG_NOT_FULL, &mtr);
		n_used2 += fseg_get_n_frag_pages(seg_inode, &mtr);
	    	next_node_addr = flst_get_next_addr(seg_inode_page
						+ FSEG_INODE_PAGE_NODE, &mtr);
		mtr_commit(&mtr);
	    }
	    node_addr = next_node_addr;
	}
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_SEG_INODES_FREE, &mtr);
	seg_inode_len_free = flst_get_len(header + FSP_SEG_INODES_FREE, &mtr);
	
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
	    for (n = 0; n < FSP_SEG_INODES_PER_PAGE; n++) {	
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);
		seg_inode_page = fut_get_ptr(space, node_addr, RW_X_LATCH,
						&mtr) - FSEG_INODE_PAGE_NODE;
		seg_inode = fsp_seg_inode_page_get_nth_inode(seg_inode_page,
								n, &mtr);
		if (ut_dulint_cmp(mach_read_from_8(seg_inode + FSEG_ID),
						ut_dulint_zero) != 0) {
			fseg_validate_low(seg_inode, &mtr);
			descr_count += flst_get_len(seg_inode + FSEG_FREE,
									&mtr);
			descr_count += flst_get_len(seg_inode + FSEG_FULL,
									&mtr);
			descr_count += flst_get_len(seg_inode + FSEG_NOT_FULL,
									&mtr);
			n_used2 += fseg_get_n_frag_pages(seg_inode, &mtr);
		}
	    	next_node_addr = flst_get_next_addr(seg_inode_page
						+ FSEG_INODE_PAGE_NODE, &mtr);
		mtr_commit(&mtr);
	    }
	    node_addr = next_node_addr;
	}
	
	ut_a(descr_count * FSP_EXTENT_SIZE == free_limit);
	ut_a(n_used + n_full_frag_pages
		== n_used2 + (free_limit + XDES_DESCRIBED_PER_PAGE - 1)
				 / XDES_DESCRIBED_PER_PAGE
		   + seg_inode_len_full + seg_inode_len_free);
	ut_a(frag_n_used == n_used);
	mtr_commit(&mtr2);
	return(TRUE);
}
/***********************************************************************
Prints info of a file space. */
void
fsp_print(
/*======*/
	ulint	space)	/* in: space id */
{
	fsp_header_t*	header;
	fseg_inode_t*	seg_inode;
	page_t*		seg_inode_page;
	ulint		size;
	ulint		free_limit;
	ulint		frag_n_used;
	fil_addr_t	node_addr;
	fil_addr_t	next_node_addr;
	ulint		n_free;
	ulint		n_free_frag;
	ulint		n_full_frag;
	ulint		seg_id_low;
	ulint		seg_id_high;
	ulint		n;
	ulint		n_segs		= 0;
	dulint          d_var;
	mtr_t		mtr;
	mtr_t		mtr2;
	
	/* Start first a mini-transaction mtr2 to lock out all other threads
	from the fsp system */
	mtr_start(&mtr2);
	mtr_x_lock(fil_space_get_latch(space), &mtr2);	
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	
	header = fsp_get_space_header(space, &mtr);
	size = mtr_read_ulint(header + FSP_SIZE, MLOG_4BYTES, &mtr); 
	free_limit = mtr_read_ulint(header + FSP_FREE_LIMIT, MLOG_4BYTES,
									&mtr); 
	frag_n_used = mtr_read_ulint(header + FSP_FRAG_N_USED, MLOG_4BYTES,
									&mtr);
	n_free = flst_get_len(header + FSP_FREE, &mtr);
	n_free_frag = flst_get_len(header + FSP_FREE_FRAG, &mtr);
	n_full_frag = flst_get_len(header + FSP_FULL_FRAG, &mtr);
	d_var = mtr_read_dulint(header + FSP_SEG_ID, MLOG_8BYTES, &mtr);
	seg_id_low = ut_dulint_get_low(d_var);
	seg_id_high = ut_dulint_get_high(d_var);
	printf("FILE SPACE INFO: id %lun", space);
	printf("size %lu, free limit %lu, free extents %lun",
						size, free_limit, n_free);
	printf(
	"not full frag extents %lu: used pages %lu, full frag extents %lun",
					n_free_frag, frag_n_used, n_full_frag);
	printf("first seg id not used %lu %lun", seg_id_high, seg_id_low);
	mtr_commit(&mtr);	
	/* Print segments */
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_SEG_INODES_FULL, &mtr);	
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
	    for (n = 0; n < FSP_SEG_INODES_PER_PAGE; n++) {	
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);
		seg_inode_page = fut_get_ptr(space, node_addr, RW_X_LATCH,
						&mtr) - FSEG_INODE_PAGE_NODE;
		seg_inode = fsp_seg_inode_page_get_nth_inode(seg_inode_page,
								n, &mtr);
		ut_a(ut_dulint_cmp(mach_read_from_8(seg_inode + FSEG_ID),
							ut_dulint_zero) != 0);
		fseg_print_low(seg_inode, &mtr);
		n_segs++;
		
	    	next_node_addr = flst_get_next_addr(seg_inode_page
						+ FSEG_INODE_PAGE_NODE, &mtr);
		mtr_commit(&mtr);
	    }
	    node_addr = next_node_addr;
	}
	mtr_start(&mtr);
	mtr_x_lock(fil_space_get_latch(space), &mtr);	
	header = fsp_get_space_header(space, &mtr);
	node_addr = flst_get_first(header + FSP_SEG_INODES_FREE, &mtr);
	mtr_commit(&mtr);
	while (!fil_addr_is_null(node_addr)) {
	    for (n = 0; n < FSP_SEG_INODES_PER_PAGE; n++) {	
		mtr_start(&mtr);
		mtr_x_lock(fil_space_get_latch(space), &mtr);
		seg_inode_page = fut_get_ptr(space, node_addr, RW_X_LATCH,
						&mtr) - FSEG_INODE_PAGE_NODE;
		seg_inode = fsp_seg_inode_page_get_nth_inode(seg_inode_page,
								n, &mtr);
		if (ut_dulint_cmp(mach_read_from_8(seg_inode + FSEG_ID),
						ut_dulint_zero) != 0) {
			fseg_print_low(seg_inode, &mtr);
			n_segs++;
		}
	    	next_node_addr = flst_get_next_addr(seg_inode_page
						+ FSEG_INODE_PAGE_NODE, &mtr);
		mtr_commit(&mtr);
	    }
	    node_addr = next_node_addr;
	}
	
	mtr_commit(&mtr2);
	printf("NUMBER of file segments: %lun", n_segs);	
}

						