bitmap.h File Reference

#include "spinlock.h"
#include <stddef.h>

Include dependency graph for bitmap.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	utils_bitmap

Macros
#define	UTILS_BITMAP_CALC_BYTES(BITS)
#define	BITMAP_NOT_FOUND   ((size_t) -1)

Typedefs
typedef struct utils_bitmap	utils_bitmap_s

Functions
utils_bitmap_s *	utils_bitmap_init (void *mem, size_t size_bits)
size_t	utils_bitmap_size (utils_bitmap_s *bmp)
size_t	utils_bitmap_used (utils_bitmap_s *bmp)
size_t	utils_bitmap_free (utils_bitmap_s *bmp)
size_t	utils_bitmap_alloc_bits (utils_bitmap_s *bmp, size_t bits)
void	utils_bitmap_free_bits (utils_bitmap_s *bmp, size_t start, size_t bits)
size_t	utils_bitmap_count_allocated (utils_bitmap_s *bmp)
void	utils_bitmap_print_bits (utils_bitmap_s *bmp)

Macro Definition Documentation

BITMAP_NOT_FOUND

#define BITMAP_NOT_FOUND   ((size_t) -1)

Definition at line 18 of file bitmap.h.

Referenced by arax_mmap(), find_end_small(), find_start(), find_start_big(), find_start_small(), utils_bitmap_alloc_bits(), and utils_bitmap_free_bits().

UTILS_BITMAP_CALC_BYTES

#define UTILS_BITMAP_CALC_BYTES

(

BITS

)

Value:

((sizeof(utils_bitmap_s) + sizeof(uint64_t) * ((BITS + 63) / 64)))

Definition at line 16 of file bitmap.h.

Typedef Documentation

utils_bitmap_s

typedef struct utils_bitmap utils_bitmap_s

Function Documentation

utils_bitmap_alloc_bits()

size_t utils_bitmap_alloc_bits	(	utils_bitmap_s *	bmp,
		size_t	bits )

Allocate bits cotiguous bits from bmp and return index of first bit.

bmp An initialized utils_bitmap_s instance.

Returns

Bit index of allocation start.

Definition at line 217 of file bitmap.c.

References BITMAP_NOT_FOUND, utils_bitmap::bits, utils_bitmap::end, find_start(), utils_bitmap::free_p, utils_bitmap::lock, utils_bitmap_free(), utils_spinlock_lock, and utils_spinlock_unlock.

Referenced by arax_mmap().

Here is the call graph for this function:

Here is the caller graph for this function:

utils_bitmap_count_allocated()

size_t utils_bitmap_count_allocated

(

utils_bitmap_s *

bmp

)

Count allocated bits of bmp.

Should always return the same value as utils_bitmap_used().

Note

This should only be used in tests, as it is very slow.

bmp An initialized utils_bitmap_s instance.

Returns

Bits allocated(set) in bits array of bmp

Definition at line 298 of file bitmap.c.

References utils_bitmap::bits, and utils_bitmap::size_bits.

utils_bitmap_free()

size_t utils_bitmap_free

(

utils_bitmap_s *

bmp

)

Returns number of unused bits in bmp.

Note

This is utils_bitmap_size() - utils_bitmap_used()

bmp An initialized utils_bitmap_s instance.

Returns

Number of free bits in bmp.

Definition at line 53 of file bitmap.c.

References utils_bitmap::size_bits, and utils_bitmap::used_bits.

Referenced by utils_bitmap_alloc_bits().

Here is the caller graph for this function:

utils_bitmap_free_bits()

void utils_bitmap_free_bits	(	utils_bitmap_s *	bmp,
		size_t	start,
		size_t	bits )

Free contiguous bits starting from start, from the bmp bitmap.

bmp An initialized utils_bitmap_s instance. start First bit index to be freed. bits Number of bits to free.

Definition at line 255 of file bitmap.c.

References arax_assert, BITMAP_NOT_FOUND, utils_bitmap::bits, utils_bitmap::lock, utils_bitmap::used_bits, utils_spinlock_lock, and utils_spinlock_unlock.

Referenced by arax_ummap().

Here is the caller graph for this function:

utils_bitmap_init()

utils_bitmap_s * utils_bitmap_init	(	void *	mem,
		size_t	size_bits )

Initialize bitmap starting in mem, holding size_bits bits.

Note

Ensure mem is greater than or equal to UTILS_BITMAP_CALC_BYTES()

Parameters

mem	Pointer to memory of UTILS_BITMAP_CALC_BYTES(size_bits) or more
size_bits	Number of bits this bitmap will hold.

Returns

Returns mem on success, null otherwise.

A bit about the bitmap:

It is arranged in 'chunks' of uint64_t (8 bytes).

Initially all bits are 0, meaning free.

Allocation happens in squential order for chunks. First chunk[0] will be usedm then chunk[1], etc...

Inside a chunk bit allocation occurs in a lsb to msb order:

An initialy empty chunk: 0x0000 0000 0000 0000 After a 16bit allocation: 0x0000 0000 0000 000F After an 8bit allocation: 0x0000 0000 0000 008F

Definition at line 25 of file bitmap.c.

References utils_bitmap::bits, utils_bitmap::end, utils_bitmap::free_p, utils_bitmap::lock, utils_bitmap::size_bits, utils_bitmap::used_bits, and utils_spinlock_init.

Referenced by arch_alloc_init_once().

Here is the caller graph for this function:

utils_bitmap_print_bits()

void utils_bitmap_print_bits

(

utils_bitmap_s *

bmp

)

Print the bitmap oc bmp, in stderr.

Note

Use this for debuging

bmp An initialized utils_bitmap_s instance.

Definition at line 311 of file bitmap.c.

References utils_bitmap::bits, and utils_bitmap::size_bits.

utils_bitmap_size()

size_t utils_bitmap_size

(

utils_bitmap_s *

bmp

)

Returns number of bits bmp holds, same as the value given in utils_bitmap_init.

bmp An initialized utils_bitmap_s instance.

Returns

Bits contained in bmp

Definition at line 43 of file bitmap.c.

References utils_bitmap::size_bits.

utils_bitmap_used()

size_t utils_bitmap_used

(

utils_bitmap_s *

bmp

)

Returns number of bits currently used in bmp.

bmp An initialized utils_bitmap_s instance.

Returns

Number of allocated bits in bmp.

Definition at line 48 of file bitmap.c.

References utils_bitmap::used_bits.