Binary buddy allocator for compressed pages. More...

#include "buf0buddy.h"
#include "buf0buf.h"
#include "buf0flu.h"
#include "buf0lru.h"
#include "dict0dict.h"
#include "page0zip.h"

Classes
struct	CheckZipFree
	Validate a given zip_free list. More...

Enumerations
enum	buf_buddy_state_t { BUF_BUDDY_STATE_FREE , BUF_BUDDY_STATE_USED , BUF_BUDDY_STATE_PARTIALLY_USED }
	Return type of buf_buddy_is_free() More...

Functions
static void	buf_buddy_mem_invalid (buf_buddy_free_t *, ulint i)

static bool	buf_buddy_stamp_is_free (const buf_buddy_free_t *buf)
	Check if a buddy is stamped free. More...

static void	buf_buddy_stamp_free (buf_buddy_free_t *buf, ulint i)
	Stamps a buddy free. More...

static void	buf_buddy_stamp_nonfree (buf_buddy_free_t *buf, ulint i)
	Stamps a buddy nonfree. More...

static void *	buf_buddy_get (byte *page, ulint size)
	Get the offset of the buddy of a compressed page frame. More...

static void	buf_buddy_list_validate (const buf_pool_t *buf_pool, ulint i)
	Validate a buddy list. More...

static bool	buf_buddy_check_free (buf_pool_t buf_pool, const buf_buddy_free_t buf, ulint i)
	Debug function to validate that a buffer is indeed free i.e. More...

static buf_buddy_state_t	buf_buddy_is_free (buf_buddy_free_t *buf, ulint i)
	Checks if a buf is free i.e. More...

static void	buf_buddy_add_to_free (buf_pool_t buf_pool, buf_buddy_free_t buf, ulint i)
	Add a block to the head of the appropriate buddy free list. More...

static void	buf_buddy_remove_from_free (buf_pool_t buf_pool, buf_buddy_free_t buf, ulint i)
	Remove a block from the appropriate buddy free list. More...

static buf_buddy_free_t *	buf_buddy_alloc_zip (buf_pool_t *buf_pool, ulint i)
	Try to allocate a block from buf_pool->zip_free[]. More...

static void	buf_buddy_block_free (buf_pool_t buf_pool, void buf)
	Deallocate a buffer frame of UNIV_PAGE_SIZE. More...

static void	buf_buddy_block_register (buf_block_t *block)
	Allocate a buffer block to the buddy allocator. More...

static void *	buf_buddy_alloc_from (buf_pool_t buf_pool, void buf, ulint i, ulint j)
	Allocate a block from a bigger object. More...

void *	buf_buddy_alloc_low (buf_pool_t *buf_pool, ulint i)
	Allocate a block. More...

static bool	buf_buddy_relocate (buf_pool_t buf_pool, void src, void *dst, ulint i, bool force)
	Try to relocate a block. More...

void	buf_buddy_free_low (buf_pool_t buf_pool, void buf, ulint i, bool has_zip_free)
	Deallocate a block. More...

bool	buf_buddy_realloc (buf_pool_t buf_pool, void buf, ulint size)
	Try to reallocate a block. More...

void	buf_buddy_condense_free (buf_pool_t *buf_pool)
	Combine all pairs of free buddies. More...

Variables
constexpr uint32_t	BUF_BUDDY_STAMP_OFFSET = FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID
	When freeing a buf we attempt to coalesce by looking at its buddy and deciding whether it is free or not. More...

constexpr uint64_t	BUF_BUDDY_STAMP_FREE = dict_sys_t::s_log_space_id
	Value that we stamp on all buffers that are currently on the zip_free list. More...

constexpr uint64_t	BUF_BUDDY_STAMP_NONFREE = 0XFFFFFFFFUL
	Stamp value for non-free buffers. More...

Detailed Description

Binary buddy allocator for compressed pages.

Created December 2006 by Marko Makela

Enumeration Type Documentation

◆ buf_buddy_state_t

enum buf_buddy_state_t

Return type of buf_buddy_is_free()

Enumerator
BUF_BUDDY_STATE_FREE	If the buddy to completely free.
BUF_BUDDY_STATE_USED	Buddy currently in used.
BUF_BUDDY_STATE_PARTIALLY_USED	Some sub-blocks in the buddy are in use.

Function Documentation

◆ buf_buddy_add_to_free()

static void buf_buddy_add_to_free	(	buf_pool_t *	buf_pool,
		buf_buddy_free_t *	buf,
		ulint	i
	)

inlinestatic

Add a block to the head of the appropriate buddy free list.

Parameters

[in]	buf_pool	buffer pool instance
[in,out]	buf	block to be freed
[in]	i	index of buf_pool->zip_free[]

◆ buf_buddy_alloc_from()

static void * buf_buddy_alloc_from	(	buf_pool_t *	buf_pool,
		void *	buf,
		ulint	i,
		ulint	j
	)

static

Allocate a block from a bigger object.

Parameters

[in]	buf_pool	buffer pool instance
[in]	buf	a block that is free to use
[in]	i	index of buf_pool->zip_free[]
[in]	j	size of buf as an index of buf_pool->zip_free[]

Returns: allocated block

◆ buf_buddy_alloc_low()

void * buf_buddy_alloc_low	(	buf_pool_t *	buf_pool,
		ulint	i
	)

Allocate a block.

Parameters

[in,out]	buf_pool	buffer pool instance
[in]	i	index of buf_pool->zip_free[] or BUF_BUDDY_SIZES

Returns: allocated block, never NULL

◆ buf_buddy_alloc_zip()

static buf_buddy_free_t * buf_buddy_alloc_zip	(	buf_pool_t *	buf_pool,
		ulint	i
	)

static

Try to allocate a block from buf_pool->zip_free[].

Parameters

[in]	buf_pool	buffer pool instance
[in]	i	index of buf_pool->zip_free[]

Returns: allocated block, or NULL if buf_pool->zip_free[] was empty

◆ buf_buddy_block_free()

static void buf_buddy_block_free	(	buf_pool_t *	buf_pool,
		void *	buf
	)

static

Deallocate a buffer frame of UNIV_PAGE_SIZE.

Parameters

[in]	buf_pool	buffer pool instance
[in]	buf	buffer frame to deallocate

◆ buf_buddy_block_register()

static void buf_buddy_block_register ( buf_block_t * block )

static

Allocate a buffer block to the buddy allocator.

Parameters

[in] block buffer frame to allocate

◆ buf_buddy_check_free()

static bool buf_buddy_check_free	(	buf_pool_t *	buf_pool,
		const buf_buddy_free_t *	buf,
		ulint	i
	)

inlinestatic

Debug function to validate that a buffer is indeed free i.e.

: in the zip_free[].

Parameters

[in]	buf_pool	buffer pool instance
[in]	buf	block to check
[in]	i	index of buf_pool->zip_free[]

Returns: true if free

◆ buf_buddy_condense_free()

void buf_buddy_condense_free ( buf_pool_t * buf_pool )

Combine all pairs of free buddies.

Parameters

[in] buf_pool buffer pool instance

◆ buf_buddy_free_low()

void buf_buddy_free_low	(	buf_pool_t *	buf_pool,
		void *	buf,
		ulint	i,
		bool	has_zip_free
	)

Deallocate a block.

Parameters

[in]	buf_pool	buffer pool instance
[in]	buf	block to be freed, must not be pointed to by the buffer pool
[in]	i	index of buf_pool->zip_free[], or BUF_BUDDY_SIZES
[in]	has_zip_free	whether has zip_free_mutex

◆ buf_buddy_get()

static void * buf_buddy_get	(	byte *	page,
		ulint	size
	)

inlinestatic

Get the offset of the buddy of a compressed page frame.

Returns: the buddy relative of page

Parameters

page	in: compressed page
size	in: page size in bytes

◆ buf_buddy_is_free()

static buf_buddy_state_t buf_buddy_is_free	(	buf_buddy_free_t *	buf,
		ulint	i
	)

static

Checks if a buf is free i.e.

: in the zip_free[].

Return values

BUF_BUDDY_STATE_FREE	if fully free
BUF_BUDDY_STATE_USED	if currently in use
BUF_BUDDY_STATE_PARTIALLY_USED	if partially in use.

Parameters

buf	in: block to check
i	in: index of buf_pool->zip_free[]

◆ buf_buddy_list_validate()

static void buf_buddy_list_validate	(	const buf_pool_t *	buf_pool,
		ulint	i
	)

static

Validate a buddy list.

Parameters

[in]	buf_pool	buffer pool instance
[in]	i	buddy size to validate

◆ buf_buddy_mem_invalid()

static void buf_buddy_mem_invalid	(	buf_buddy_free_t *	,
		ulint	i
	)

inlinestatic

◆ buf_buddy_realloc()

bool buf_buddy_realloc	(	buf_pool_t *	buf_pool,
		void *	buf,
		ulint	size
	)

Try to reallocate a block.

Parameters

[in]	buf_pool	buffer pool instance
[in]	buf	block to be reallocated, must be pointed to by the buffer pool
[in]	size	block size, up to UNIV_PAGE_SIZE

Return values

true	if succeeded or if failed because the block was fixed
false	if failed because of no free blocks.

◆ buf_buddy_relocate()

static bool buf_buddy_relocate	(	buf_pool_t *	buf_pool,
		void *	src,
		void *	dst,
		ulint	i,
		bool	force
	)

static

Try to relocate a block.

The caller must hold zip_free_mutex, and this function will release and lock it again.

Parameters

[in]	buf_pool	buffer pool instance
[in]	src	block to relocate
[in]	dst	free block to relocated to
[in]	i	index of buf_pool->zip_free[]
[in]	force	true if we must relocated always

Returns: true if relocated

◆ buf_buddy_remove_from_free()

static void buf_buddy_remove_from_free	(	buf_pool_t *	buf_pool,
		buf_buddy_free_t *	buf,
		ulint	i
	)

inlinestatic

Remove a block from the appropriate buddy free list.

Parameters

[in]	buf_pool	buffer pool instance
[in,out]	buf	block to be freed
[in]	i	index of buf_pool->zip_free[]

◆ buf_buddy_stamp_free()

static void buf_buddy_stamp_free	(	buf_buddy_free_t *	buf,
		ulint	i
	)

inlinestatic

Stamps a buddy free.

Parameters

buf	in/out: block to stamp
i	in: block size

◆ buf_buddy_stamp_is_free()

static bool buf_buddy_stamp_is_free ( const buf_buddy_free_t * buf )

inlinestatic

Check if a buddy is stamped free.

Returns: whether the buddy is free

Parameters

buf	in: block to check

◆ buf_buddy_stamp_nonfree()

static void buf_buddy_stamp_nonfree	(	buf_buddy_free_t *	buf,
		ulint	i
	)

inlinestatic

Stamps a buddy nonfree.

Parameters

[in,out]	buf	block to stamp
[in]	i	block size

Variable Documentation

◆ BUF_BUDDY_STAMP_FREE

constexpr uint64_t BUF_BUDDY_STAMP_FREE = dict_sys_t::s_log_space_id

constexpr

Value that we stamp on all buffers that are currently on the zip_free list.

This value is stamped at BUF_BUDDY_STAMP_OFFSET offset

◆ BUF_BUDDY_STAMP_NONFREE

constexpr uint64_t BUF_BUDDY_STAMP_NONFREE = 0XFFFFFFFFUL

constexpr

Stamp value for non-free buffers.

Will be overwritten by a non-zero value by the consumer of the block

◆ BUF_BUDDY_STAMP_OFFSET

constexpr uint32_t BUF_BUDDY_STAMP_OFFSET = FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID

constexpr

When freeing a buf we attempt to coalesce by looking at its buddy and deciding whether it is free or not.

To ascertain if the buddy is free we look for BUF_BUDDY_STAMP_FREE at BUF_BUDDY_STAMP_OFFSET within the buddy. The question is how we can be sure that it is safe to look at BUF_BUDDY_STAMP_OFFSET. The answer lies in following invariants: All blocks allocated by buddy allocator are used for compressed page frame. A compressed table always have space_id < dict_sys_t::s_log_space_id BUF_BUDDY_STAMP_OFFSET always points to the space_id field in a frame. – The above is true because we look at these fields when the corresponding buddy block is free which implies that:

The block we are looking at must have an address aligned at the same size that its free buddy has. For example, if we have a free block of 8K then its buddy's address must be aligned at 8K as well.
It is possible that the block we are looking at may have been further divided into smaller sized blocks but its starting address must still remain the start of a page frame i.e.: it cannot be middle of a block. For example, if we have a free block of size 8K then its buddy may be divided into blocks of, say, 1K, 1K, 2K, 4K but the buddy's address will still be the starting address of first 1K compressed page.
What is important to note is that for any given block, the buddy's address cannot be in the middle of a larger block i.e.: in above example, our 8K block cannot have a buddy whose address is aligned on 8K but it is part of a larger 16K block. Offset within buf_buddy_free_t where free or non_free stamps are written.

Classes

Enumerations

Functions

Variables

Detailed Description

Enumeration Type Documentation

◆ buf_buddy_state_t

Function Documentation

◆ buf_buddy_add_to_free()

◆ buf_buddy_alloc_from()

◆ buf_buddy_alloc_low()

◆ buf_buddy_alloc_zip()

◆ buf_buddy_block_free()

◆ buf_buddy_block_register()

◆ buf_buddy_check_free()

◆ buf_buddy_condense_free()

◆ buf_buddy_free_low()

◆ buf_buddy_get()

◆ buf_buddy_is_free()

◆ buf_buddy_list_validate()

◆ buf_buddy_mem_invalid()

◆ buf_buddy_realloc()

◆ buf_buddy_relocate()

◆ buf_buddy_remove_from_free()

◆ buf_buddy_stamp_free()

◆ buf_buddy_stamp_is_free()

◆ buf_buddy_stamp_nonfree()

Variable Documentation

◆ BUF_BUDDY_STAMP_FREE

◆ BUF_BUDDY_STAMP_NONFREE

◆ BUF_BUDDY_STAMP_OFFSET