Bitmap. More...

Data Structures
struct	bitmap_t
	Bitmap structure. More...

Macros
#define	BITMAP_BITS_TO_QWORDS(bits) (((bits) + 63) / 64)
	Convert number of bits to number of qwords.

#define	BITMAP_BITS_TO_BYTES(bits) (BITMAP_BITS_TO_QWORDS(bits) * sizeof(uint64_t))
	Convert number of bits to number of bytes.

#define	BITMAP_QWORDS_TO_BITS(qwords) ((qwords) * 64)
	Convert number of qwords to number of bits.

#define	BITMAP_FOR_EACH_SET(idx, map)
	Iterate over each set bit in the bitmap.

Functions
static void	bitmap_init (bitmap_t map, void buffer, uint64_t length)
	Initialize a bitmap.

static bool	bitmap_is_set (bitmap_t *map, uint64_t idx)
	Check if a bit is set in the bitmap.

static void	bitmap_set (bitmap_t *map, uint64_t index)
	Set a bit in the bitmap.

static void	bitmap_set_range (bitmap_t *map, uint64_t low, uint64_t high)
	Set a range of bits in the bitmap.

static uint64_t	bitmap_find_clear_region_and_set (bitmap_t *map, uint64_t length, uintptr_t maxIdx, uint64_t align)
	Find a clear region of specified length and alignment, and set it.

static void	bitmap_clear (bitmap_t *map, uint64_t index)
	Clear a bit in the bitmap.

static void	bitmap_clear_range (bitmap_t *map, uint64_t low, uint64_t high)
	Clear a range of bits in the bitmap.

static uint64_t	bitmap_sum (bitmap_t *map, uint64_t low, uint64_t high)
	Sum the number of set bits in a range.

static uint64_t	bitmap_find_first_clear (bitmap_t *map)
	Find the first clear bit in the bitmap.

static uint64_t	bitmap_find_first_set (bitmap_t *map, uint64_t startIdx)
	Find the first set bit in the bitmap.

Detailed Description

Bitmap.

Macro Definition Documentation

◆ BITMAP_BITS_TO_BYTES

#define BITMAP_BITS_TO_BYTES ( bits ) (BITMAP_BITS_TO_QWORDS(bits) * sizeof(uint64_t))

Convert number of bits to number of bytes.

Parameters

bits	Number of bits.

Returns: Number of bytes.

Definition at line 42 of file bitmap.h.

◆ BITMAP_BITS_TO_QWORDS

#define BITMAP_BITS_TO_QWORDS ( bits ) (((bits) + 63) / 64)

Convert number of bits to number of qwords.

Parameters

bits	Number of bits.

Returns: Number of qwords.

Definition at line 34 of file bitmap.h.

◆ BITMAP_FOR_EACH_SET

#define BITMAP_FOR_EACH_SET	(	idx,
		map
	)

Value:

    for (uint64_t qwordIdx = 0; qwordIdx < BITMAP_BITS_TO_QWORDS((map)->length); qwordIdx++) \
        for (uint64_t tempQword = (map)->buffer[qwordIdx]; tempQword != 0; tempQword &= (tempQword - 1)) \
            if (({ \
                    uint64_t bit = __builtin_ctzll(tempQword); \
                    *(idx) = qwordIdx * 64 + bit; \
                    *(idx) < (map)->length; \
                }))

Iterate over each set bit in the bitmap.

Parameters

idx	Pointer to store the current index.
map	The bitmap.

Definition at line 58 of file bitmap.h.

◆ BITMAP_QWORDS_TO_BITS

#define BITMAP_QWORDS_TO_BITS ( qwords ) ((qwords) * 64)

Convert number of qwords to number of bits.

Parameters

qwords Number of qwords.

Returns: Number of bits.

Definition at line 50 of file bitmap.h.

Function Documentation

◆ bitmap_clear()

static void bitmap_clear	(	bitmap_t *	map,
		uint64_t	index
	)

inlinestatic

Clear a bit in the bitmap.

Parameters

map	Pointer to the bitmap.
index	Index of the bit to clear.

Definition at line 186 of file bitmap.h.

References boot_memory_map_t::length, map, and MIN.

Referenced by _heap_alloc(), _heap_remove_from_free_list(), space_free_callback(), and vfs_ctx_free_fd().

◆ bitmap_clear_range()

static void bitmap_clear_range	(	bitmap_t *	map,
		uint64_t	low,
		uint64_t	high
	)

inlinestatic

Clear a range of bits in the bitmap.

Parameters

map	Pointer to the bitmap.
low	Low index of the range (inclusive).
high	High index of the range (exclusive).

Definition at line 206 of file bitmap.h.

References boot_memory_map_t::length, map, and MIN.

Referenced by pmm_bitmap_free().

◆ bitmap_find_clear_region_and_set()

static uint64_t bitmap_find_clear_region_and_set	(	bitmap_t *	map,
		uint64_t	length,
		uintptr_t	maxIdx,
		uint64_t	align
	)

inlinestatic

Find a clear region of specified length and alignment, and set it.

Parameters

map	Pointer to the bitmap.
length	Length of the region to find.
maxIdx	Maximum index to search up to.
align	Alignment of the region.

Returns: Starting index of the found region, or map->length if not found.

Definition at line 147 of file bitmap.h.

References bitmap_is_set(), bitmap_set_range(), boot_memory_map_t::length, map, MAX, and ROUND_UP.

Referenced by pmm_bitmap_alloc().

◆ bitmap_find_first_clear()

static uint64_t bitmap_find_first_clear ( bitmap_t * map )

inlinestatic

Find the first clear bit in the bitmap.

Parameters

map	The bitmap.

Returns: Index of the first clear bit, or map->length if none found.

Definition at line 283 of file bitmap.h.

References BITMAP_BITS_TO_QWORDS, boot_memory_map_t::length, and map.

Referenced by space_alloc_callback(), vfs_ctx_alloc_fd(), and vfs_ctx_dup().

◆ bitmap_find_first_set()

static uint64_t bitmap_find_first_set	(	bitmap_t *	map,
		uint64_t	startIdx
	)

inlinestatic

Find the first set bit in the bitmap.

Parameters

map	The bitmap.
startIdx	Index to start searching from.

Returns: Index of the first set bit, or map->length if none found.

Definition at line 323 of file bitmap.h.

References BITMAP_BITS_TO_QWORDS, boot_memory_map_t::length, and map.

Referenced by _heap_alloc().

◆ bitmap_init()

static void bitmap_init	(	bitmap_t *	map,
		void *	buffer,
		uint64_t	length
	)

inlinestatic

Initialize a bitmap.

Parameters

map	The bitmap.
buffer	Pointer to the buffer, must be a multiple of 8 bytes.
length	Length of the bitmap in bits.

Definition at line 74 of file bitmap.h.

References buffer, boot_memory_map_t::length, and map.

Referenced by _heap_init(), pmm_bitmap_init(), space_init(), and vfs_ctx_init().

◆ bitmap_is_set()

static bool bitmap_is_set	(	bitmap_t *	map,
		uint64_t	idx
	)

inlinestatic

Check if a bit is set in the bitmap.

Parameters

map	The bitmap.
idx	Index of the bit to check.

Returns: true if the bit is set, false otherwise.

Definition at line 88 of file bitmap.h.

References boot_memory_map_t::length, and map.

Referenced by bitmap_find_clear_region_and_set().

◆ bitmap_set()

static void bitmap_set	(	bitmap_t *	map,
		uint64_t	index
	)

inlinestatic

Set a bit in the bitmap.

Parameters

map	Pointer to the bitmap.
index	Index of the bit to set.

Definition at line 106 of file bitmap.h.

References boot_memory_map_t::length, and map.

Referenced by _heap_add_to_free_list(), bitmap_set_range(), space_alloc_callback(), vfs_ctx_alloc_fd(), vfs_ctx_dup(), vfs_ctx_dup2(), and vfs_ctx_set_fd().

◆ bitmap_set_range()

static void bitmap_set_range	(	bitmap_t *	map,
		uint64_t	low,
		uint64_t	high
	)

inlinestatic

Set a range of bits in the bitmap.

Parameters

map	Pointer to the bitmap.
low	Low index of the range (inclusive).
high	High index of the range (exclusive).

Definition at line 125 of file bitmap.h.

References bitmap_set(), boot_memory_map_t::length, and map.

Referenced by bitmap_find_clear_region_and_set().

◆ bitmap_sum()

static uint64_t bitmap_sum	(	bitmap_t *	map,
		uint64_t	low,
		uint64_t	high
	)

inlinestatic

Sum the number of set bits in a range.

Parameters

map	Pointer to the bitmap.
low	Low index of the range (inclusive).
high	High index of the range (exclusive).

Returns: Number of set bits in the range.

Definition at line 230 of file bitmap.h.

References boot_memory_map_t::length, and map.

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ BITMAP_BITS_TO_BYTES

◆ BITMAP_BITS_TO_QWORDS

◆ BITMAP_FOR_EACH_SET

◆ BITMAP_QWORDS_TO_BITS

Function Documentation

◆ bitmap_clear()

◆ bitmap_clear_range()

◆ bitmap_find_clear_region_and_set()

◆ bitmap_find_first_clear()

◆ bitmap_find_first_set()

◆ bitmap_init()

◆ bitmap_is_set()

◆ bitmap_set()

◆ bitmap_set_range()

◆ bitmap_sum()