MySQL 8.0.32
Source Code Documentation
buf0buddy.cc File Reference

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_tbuf_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

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_poolbuffer pool instance
[in,out]bufblock to be freed
[in]iindex 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_poolbuffer pool instance
[in]bufa block that is free to use
[in]iindex of buf_pool->zip_free[]
[in]jsize 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_poolbuffer pool instance
[in]iindex 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_poolbuffer pool instance
[in]iindex 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_poolbuffer pool instance
[in]bufbuffer 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]blockbuffer 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_poolbuffer pool instance
[in]bufblock to check
[in]iindex 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_poolbuffer 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_poolbuffer pool instance
[in]bufblock to be freed, must not be pointed to by the buffer pool
[in]iindex of buf_pool->zip_free[], or BUF_BUDDY_SIZES
[in]has_zip_freewhether 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
pagein: compressed page
sizein: 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_FREEif fully free
BUF_BUDDY_STATE_USEDif currently in use
BUF_BUDDY_STATE_PARTIALLY_USEDif partially in use.
Parameters
bufin: block to check
iin: 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_poolbuffer pool instance
[in]ibuddy 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_poolbuffer pool instance
[in]bufblock to be reallocated, must be pointed to by the buffer pool
[in]sizeblock size, up to UNIV_PAGE_SIZE
Return values
trueif succeeded or if failed because the block was fixed
falseif 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_poolbuffer pool instance
[in]srcblock to relocate
[in]dstfree block to relocated to
[in]iindex of buf_pool->zip_free[]
[in]forcetrue 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_poolbuffer pool instance
[in,out]bufblock to be freed
[in]iindex 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
bufin/out: block to stamp
iin: 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
bufin: 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]bufblock to stamp
[in]iblock 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.