rte_bitmap.h File Reference

#include <string.h>
#include <rte_common.h>
#include <rte_config.h>
#include <rte_debug.h>
#include <rte_memory.h>
#include <rte_branch_prediction.h>
#include <rte_prefetch.h>

Go to the source code of this file.

Data Structures
struct	rte_bitmap

Functions
static uint32_t	rte_bitmap_get_memory_footprint (uint32_t n_bits)
static struct rte_bitmap *	rte_bitmap_init (uint32_t n_bits, uint8_t *mem, uint32_t mem_size)
static int	rte_bitmap_free (struct rte_bitmap *bmp)
static void	rte_bitmap_reset (struct rte_bitmap *bmp)
static void	rte_bitmap_prefetch0 (struct rte_bitmap *bmp, uint32_t pos)
static uint64_t	rte_bitmap_get (struct rte_bitmap *bmp, uint32_t pos)
static void	rte_bitmap_set (struct rte_bitmap *bmp, uint32_t pos)
static void	rte_bitmap_set_slab (struct rte_bitmap *bmp, uint32_t pos, uint64_t slab)
static void	rte_bitmap_clear (struct rte_bitmap *bmp, uint32_t pos)
static int	rte_bitmap_scan (struct rte_bitmap *bmp, uint32_t *pos, uint64_t *slab)

Detailed Description

RTE Bitmap

The bitmap component provides a mechanism to manage large arrays of bits through bit get/set/clear and bit array scan operations.

The bitmap scan operation is optimized for 64-bit CPUs using 64/128 byte cache lines. The bitmap is hierarchically organized using two arrays (array1 and array2), with each bit in array1 being associated with a full cache line (512/1024 bits) of bitmap bits, which are stored in array2: the bit in array1 is set only when there is at least one bit set within its associated array2 bits, otherwise the bit in array1 is cleared. The read and write operations for array1 and array2 are always done in slabs of 64 bits.

This bitmap is not thread safe. For lock free operation on a specific bitmap instance, a single writer thread performing bit set/clear operations is allowed, only the writer thread can do bitmap scan operations, while there can be several reader threads performing bit get operations in parallel with the writer thread. When the use of locking primitives is acceptable, the serialization of the bit set/clear and bitmap scan operations needs to be enforced by the caller, while the bit get operation does not require locking the bitmap.

Definition in file rte_bitmap.h.

Function Documentation

rte_bitmap_get_memory_footprint()

static uint32_t rte_bitmap_get_memory_footprint ( uint32_t  n_bits )

inlinestatic

Bitmap memory footprint calculation

Parameters

n_bits

Number of bits in the bitmap

Returns

Bitmap memory footprint measured in bytes on success, 0 on error

Definition at line 148 of file rte_bitmap.h.

rte_bitmap_init()

static struct rte_bitmap* rte_bitmap_init ( uint32_t  n_bits, uint8_t *  mem, uint32_t  mem_size  )

static

Bitmap initialization

Parameters

n_bits	Number of pre-allocated bits in array2.
mem	Base address of array1 and array2.
mem_size	Minimum expected size of bitmap.

Returns

Handle to bitmap instance.

Definition at line 170 of file rte_bitmap.h.

rte_bitmap_free()

static int rte_bitmap_free ( struct rte_bitmap *  bmp )

inlinestatic

Bitmap free

Parameters

bmp	Handle to bitmap instance

Returns

0 upon success, error code otherwise

Definition at line 214 of file rte_bitmap.h.

rte_bitmap_reset()

static void rte_bitmap_reset ( struct rte_bitmap *  bmp )

inlinestatic

Bitmap reset

Parameters

bmp	Handle to bitmap instance

Definition at line 231 of file rte_bitmap.h.

rte_bitmap_prefetch0()

static void rte_bitmap_prefetch0 ( struct rte_bitmap *  bmp, uint32_t  pos  )

inlinestatic

Bitmap location prefetch into CPU L1 cache

Parameters

bmp	Handle to bitmap instance
pos	Bit position

Returns

0 upon success, error code otherwise

Definition at line 249 of file rte_bitmap.h.

rte_bitmap_get()

static uint64_t rte_bitmap_get ( struct rte_bitmap *  bmp, uint32_t  pos  )

inlinestatic

Bitmap bit get

Parameters

bmp	Handle to bitmap instance
pos	Bit position

Returns

0 when bit is cleared, non-zero when bit is set

Definition at line 270 of file rte_bitmap.h.

rte_bitmap_set()

static void rte_bitmap_set ( struct rte_bitmap *  bmp, uint32_t  pos  )

inlinestatic

Bitmap bit set

Parameters

bmp	Handle to bitmap instance
pos	Bit position

Definition at line 290 of file rte_bitmap.h.

rte_bitmap_set_slab()

static void rte_bitmap_set_slab ( struct rte_bitmap *  bmp, uint32_t  pos, uint64_t  slab  )

inlinestatic

Bitmap slab set

Parameters

bmp	Handle to bitmap instance
pos	Bit position identifying the array2 slab
slab	Value to be assigned to the 64-bit slab in array2

Definition at line 318 of file rte_bitmap.h.

rte_bitmap_clear()

static void rte_bitmap_clear ( struct rte_bitmap *  bmp, uint32_t  pos  )

inlinestatic

Bitmap bit clear

Parameters

bmp	Handle to bitmap instance
pos	Bit position

Definition at line 358 of file rte_bitmap.h.

rte_bitmap_scan()

static int rte_bitmap_scan ( struct rte_bitmap *  bmp, uint32_t *  pos, uint64_t *  slab  )

inlinestatic

Bitmap scan (with automatic wrap-around)

Parameters

bmp	Handle to bitmap instance
pos	When function call returns 1, pos contains the position of the next set bit, otherwise not modified
slab	When function call returns 1, slab contains the value of the entire 64-bit slab where the bit indicated by pos is located. Slabs are always 64-bit aligned, so the position of the first bit of the slab (this bit is not necessarily set) is pos / 64. Once a slab has been returned by the bitmap scan operation, the internal pointers of the bitmap are updated to point after this slab, so the same slab will not be returned again if it contains more than one bit which is set. When function call returns 0, slab is not modified.

Returns

0 if there is no bit set in the bitmap, 1 otherwise

Definition at line 467 of file rte_bitmap.h.