#include "mcbsp-internal-macros.h"
#include "mcbsp-affinity.h"
#include "mcbsp-resiliency.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <string.h>
#include <unistd.h>
#include <stdint.h>
#include <pthread.h>
#include <stdbool.h>

Include dependency graph for mcutil.h:

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

Go to the source code of this file.

Data Structures
struct	mcbsp_util_machine_partition
	Structure representing a part of the current machine. More...

struct	mcbsp_util_machine_info
	Structure representing the machine hardware information. More...

struct	mcbsp_util_address_map
	A map from pointers to unsigned long ints. More...

struct	mcbsp_util_address_table_entry
	A single address table entry. More...

struct	mcbsp_util_stack
	Self-growing stack. More...

struct	mcbsp_util_address_table
	A table of local address locations per SPMD variable. More...

struct	mcbsp_util_pinning_info
	Return type of mcbsp_util_pinning. More...

Functions
void	mcbsp_util_stack_initialize (struct mcbsp_util_stack *const stack, const size_t elementSize)
	Initialises the mcbsp_util_stack struct. More...

void	mcbsp_util_stack_grow (struct mcbsp_util_stack *const stack, const size_t target_size)
	Increases the capacity of a given stack to match or exceed a given target capacity. More...

bool	mcbsp_util_stack_empty (const struct mcbsp_util_stack *const stack)
	Checks whether a given stack is empty. More...

void *	mcbsp_util_stack_pop (struct mcbsp_util_stack *const stack)
	Returns the newest item in the stack. More...

void *	mcbsp_util_stack_peek (const struct mcbsp_util_stack *const stack)
	Returns the top stack item. More...

void	mcbsp_util_stack_push (struct mcbsp_util_stack const stack, const void const item)
	Pushes a new item on the stack. More...

void	mcbsp_util_stack_destroy (struct mcbsp_util_stack *const stack)
	Frees all memory related to a given stack. More...

void	mcbsp_util_varstack_grow (struct mcbsp_util_stack *const stack, const size_t requested_size)
	Doubles the capacity of a given stack that consists of elements of variable size. More...

void *	mcbsp_util_varstack_pop (struct mcbsp_util_stack *const stack, const size_t size)
	Returns the top stack item of variable size, and shortens the stack by that item size. More...

void *	mcbsp_util_varstack_regpop (struct mcbsp_util_stack *const stack)
	Returns the top fixed-size item of the stack. More...

void *	mcbsp_util_varstack_peek (const struct mcbsp_util_stack *const stack, const size_t size)
	Peeks for a variably-sized item on the stack. More...

void *	mcbsp_util_varstack_regpeek (const struct mcbsp_util_stack *const stack)
	Peeks for a fixed-sized item on the stack. More...

void	mcbsp_util_varstack_push (struct mcbsp_util_stack const stack, const void const item, const size_t size)
	Pushes a variably-sized item on the stack. More...

void	mcbsp_util_varstack_regpush (struct mcbsp_util_stack const stack, const void const item)
	Pushes a fixed-size item on the stack. More...

void	mcbsp_util_address_table_initialize (struct mcbsp_util_address_table *const table, const size_t P)
	Initialises the mcbsp_util_address_table struct. More...

void	mcbsp_util_address_table_grow (struct mcbsp_util_address_table *const table, const size_t target_size)
	Increases the capacity of a given address table to match at least a given capacity. More...

void	mcbsp_util_address_table_setsize (struct mcbsp_util_address_table *const table, const size_t target_size)
	Ensures the address table is of at least the given size. More...

void	mcbsp_util_address_table_destroy (struct mcbsp_util_address_table *const table)
	Frees the memory associated with a given address table. More...

void	mcbsp_util_address_table_set (struct mcbsp_util_address_table const table, const size_t key, const size_t version, void const value, const size_t size)
	Sets an entry in a given address table. More...

struct mcbsp_util_address_table_entry *	mcbsp_util_address_table_get (const struct mcbsp_util_address_table *const table, const size_t key, const size_t version)
	Gets an entry from a given address table. More...

bool	mcbsp_util_address_table_delete (struct mcbsp_util_address_table *const table, const size_t key, const size_t version)
	Removes an entry from a given address table. More...

void	mcbsp_util_address_map_initialize (struct mcbsp_util_address_map *const address_map)
	Initialises a mcbsp_util_address_map struct. More...

void	mcbsp_util_address_map_grow (struct mcbsp_util_address_map *const address_map)
	Doubles the capacity of a given address map. More...

void	mcbsp_util_address_map_destroy (struct mcbsp_util_address_map *const address_map)
	Frees the memory related to a given address map. More...

size_t	mcbsp_util_address_map_get (const struct mcbsp_util_address_map const address_map, const void const key)
	Address map accessor. More...

void	mcbsp_util_address_map_insert (struct mcbsp_util_address_map const address_map, void const key, const size_t value)
	Inserts a key-value pair in the map. More...

void	mcbsp_util_address_map_remove (struct mcbsp_util_address_map const address_map, void const key)
	Removes a key-value pair from the map. More...

size_t	mcbsp_util_address_map_binsearch (const struct mcbsp_util_address_map const address_map, const void const key, size_t lo, size_t hi)
	Helper-function for mcbsp_util_address_map_insert, and mcbsp_util_address_map_remove. More...

size_t	mcbsp_util_detect_hardware_threads (void)
	Attempts to detect the number of hard-ware threads supported on the current machine. More...

struct mcbsp_util_machine_info *	mcbsp_util_createMachineInfo (void)
	Creates a new machine info struct. More...

void	mcbsp_util_destroyMachineInfo (void *machine_info)
	If a current machine info instance exists, destroys it. More...

int	mcbsp_util_integer_compare (const void a, const void b)
	Comparison function for use with qsort on arrays of size_t's. More...

size_t	mcbsp_util_log2 (size_t x)
	Binary logarithm, unsigned integer version, rounding up. More...

size_t	mcbsp_util_sort_unique_integers (size_t *const array, const size_t length, const size_t lower_bound, const size_t upper_bound)
	Sorts an array of integers. More...

bool	mcbsp_util_contains (const size_t *const array, const size_t value, const size_t lo, const size_t hi)
	Returns whether an array contains a given value. More...

struct mcbsp_util_pinning_info	mcbsp_util_pinning (const size_t P, struct mcbsp_util_machine_info const machine, const struct mcbsp_util_machine_partition const super_machine)
	Function that yields a pinning of P threads according to the given machine info. More...

void	mcbsp_util_fatal (void)
	Handles a fatal error in a uniform fashion. More...

void	mcbsp_util_check_machine_info (struct mcbsp_util_machine_info *const machine)
	Function that prepares a mcbsp_util_machine_info for use. More...

struct mcbsp_util_machine_partition	mcbsp_util_derive_partition (const struct mcbsp_util_machine_info *const info)
	Derives an initial machine partition from a machine_info object. More...

struct mcbsp_util_stack	mcbsp_util_partition (const struct mcbsp_util_machine_partition subpart, const size_t P, const enum mcbsp_affinity_mode affinity)
	Derives a P-way subpartition from a given machine partition. More...

size_t *	mcbsp_util_derive_standard_pinning (const struct mcbsp_util_machine_partition *iterator, const size_t size)
	Derives a pinning from an array of machine partitions. More...

void	mcbsp_util_filter_standard_pinning (const struct mcbsp_util_machine_info const info, size_t const array, const size_t P)
	Filters reserved cores from a standard pinning list. More...

void	mcbsp_util_translate_standard_pinning (const struct mcbsp_util_machine_info const info, size_t const array, const size_t P)
	Translates thread numbers in the standard pinning format (consecutive), to the numbering format active on this machine. More...

size_t	mcbsp_util_array_sizet_lbound (const size_t *const array, const size_t key, size_t lo, size_t hi)
	Searches an array for the largest value lower or equal to a given key. More...

void	mcbsp_util_memcpy (void const restrict dest, const void const restrict src, const size_t size)
	Copies the data in [src,src+size) to [dest,dest+size). More...

void *	mcbsp_util_malloc (const size_t size, const char *const name)
	Memory allocation function used for internal MulticoreBSP for C memory areas. More...

Variables
struct mcbsp_util_address_map	MCBSP_UTIL_EMPTY_ADDRESS_MAP
	A default initialiser of type mcbsp_util_address_map. More...

Function Documentation

size_t mcbsp_util_address_map_binsearch	(	const struct mcbsp_util_address_map *const	address_map,
		const void *const	key,
		size_t	lo,
		size_t	hi
	)

Helper-function for mcbsp_util_address_map_insert, and mcbsp_util_address_map_remove.

Performs a binary search for key and returns the largest index for which the map key is less or equal to the supplied key value.

Parameters

address_map	Pointer to the map to look in.
key	The key value to look for.
lo	Lower bound on range of the map to look for.
hi	upper bound (inclusive) on range of the map to look for.

void mcbsp_util_address_map_destroy ( struct mcbsp_util_address_map *const address_map )

Frees the memory related to a given address map.

Parameters

address_map Pointer to the struct to destroy.

size_t mcbsp_util_address_map_get	(	const struct mcbsp_util_address_map *const	address_map,
		const void *const	key
	)

Address map accessor.

Parameters

address_map	Pointer to the map to consult.
key	Which key to search for.

Returns: The value associated with the key.

void mcbsp_util_address_map_grow ( struct mcbsp_util_address_map *const address_map )

Doubles the capacity of a given address map.

Parameters

address_map Pointer to the struct of the map to increase storage of.

void mcbsp_util_address_map_initialize ( struct mcbsp_util_address_map *const address_map )

Initialises a mcbsp_util_address_map struct.

Parameters

address_map Pointer to the struct to initialise.

void mcbsp_util_address_map_insert	(	struct mcbsp_util_address_map *const	address_map,
		void *const	key,
		const size_t	value
	)

Inserts a key-value pair in the map.

Parameters

address_map	Pointer to the map to insert in.
key	Under which key to insert the value.
value	The value to insert.

void mcbsp_util_address_map_remove	(	struct mcbsp_util_address_map *const	address_map,
		void *const	key
	)

Removes a key-value pair from the map.

Does nothing when the key is not in the map.

Parameters

address_map	Pointer to the map to remove from.
key	Key of the key-value pair to remove.

bool mcbsp_util_address_table_delete	(	struct mcbsp_util_address_table *const	table,
		const size_t	key,
		const size_t	version
	)

Removes an entry from a given address table.

Does not do boundary checks.

Parameters

table	Pointer to the address table.
key	Which entry to remove.
version	Which local version to remove.

Returns: Whether the registration stack at (key,version) is empty.

void mcbsp_util_address_table_destroy ( struct mcbsp_util_address_table *const table )

Frees the memory associated with a given address table.

Parameters

table Pointer to the struct to destroy.

Warning: This function is not thread-safe.

struct mcbsp_util_address_table_entry* mcbsp_util_address_table_get	(	const struct mcbsp_util_address_table *const	table,
		const size_t	key,
		const size_t	version
	)

Gets an entry from a given address table.

Does not do boundary checks.

Parameters

table	Pointer to the address table.
key	Which entry to get.
version	Which local version to obtain.

Returns: The requested address pointer.

This function is thread-safe as long as other threads only access the same table.

void mcbsp_util_address_table_grow	(	struct mcbsp_util_address_table *const	table,
		const size_t	target_size
	)

Increases the capacity of a given address table to match at least a given capacity.

Parameters

[in]	table	Pointer to the struct of the table to increase the storage of.
[in]	target_size	the minimum size at function exit.

Warning: This function is not thread-safe.

void mcbsp_util_address_table_initialize	(	struct mcbsp_util_address_table *const	table,
		const size_t	P
	)

Initialises the mcbsp_util_address_table struct.

Parameters

table	Pointer to the struct to initialise.
P	The number of local versions to maintain for each entry.

Warning: This function is not thread-safe.

void mcbsp_util_address_table_set	(	struct mcbsp_util_address_table *const	table,
		const size_t	key,
		const size_t	version,
		void *const	value,
		const size_t	size
	)

Sets an entry in a given address table.

Grows table capacity if required.

Parameters

table	Pointer to the address table.
key	Which entry to set.
version	Which local version to set.
value	Pointer to the local memory region..
size	Size of the local memory region.

This function is thread-safe.

Warning: This function is costly to call especially when many function do so concurrently, using the same table.

void mcbsp_util_address_table_setsize	(	struct mcbsp_util_address_table *const	table,
		const size_t	target_size
	)

Ensures the address table is of at least the given size.

Parameters

table	Pointer to the struct to check the size of, and expand the size of, if necessary.
target_size	The (new) minimum size of the table after function exit.

Warning: This function is not thread-safe.

size_t mcbsp_util_array_sizet_lbound	(	const size_t *const	array,
		const size_t	key,
		size_t	lo,
		size_t	hi
	)

Searches an array for the largest value lower or equal to a given key.

The array is assumed to be sorted. The array is assumed to contain unique values only. The array has elements of type size_t.

Parameters

array	The array to search in.
key	The key to search for.
lo	The lower bound on the index of the elements of array to search in (inclusive).
hi	The higher bound on the index of the elements of array to search in (inclusive).

Returns: The index of the element in array with the largest value lower or equal to key.

void mcbsp_util_check_machine_info ( struct mcbsp_util_machine_info *const machine )

Function that prepares a mcbsp_util_machine_info for use.

The reserved_cores list will be sorted, and some sanity checks on the supplied information are performed.

Parameters

machine The struct to check.

bool mcbsp_util_contains	(	const size_t *const	array,
		const size_t	value,
		const size_t	lo,
		const size_t	hi
	)

Returns whether an array contains a given value.

Only the range [lo,hi) of array is checked for value.

Parameters

array	Where to search in.
value	The value to search for.
lo	From which index on to search (inclusive).
hi	Up to which index to search (exclusive).

Returns: Whether array contains value in the given range.

struct mcbsp_util_machine_info* mcbsp_util_createMachineInfo ( void )

Creates a new machine info struct.

Returns: A pointer to a new machine info struct.

struct mcbsp_util_machine_partition mcbsp_util_derive_partition ( const struct mcbsp_util_machine_info *const info )

Derives an initial machine partition from a machine_info object.

Parameters

info	The machine info to derive a partitition from.

Returns: The derived initial partitioning.

size_t* mcbsp_util_derive_standard_pinning	(	const struct mcbsp_util_machine_partition *	iterator,
		const size_t	size
	)

Derives a pinning from an array of machine partitions.

Should be post-processed to cope with reserved cores and HW thread numbering. If size is smaller than P, multiple threads will pin to the same HW thread, using a wrapping fashion.

Parameters

iterator	Pointer to the first element of the array of machine partitions.
size	Number of partitions.

Returns: A standard pinning derived from the partitions in consecutive HW thread numbering.

void mcbsp_util_destroyMachineInfo ( void * machine_info )

If a current machine info instance exists, destroys it.

This function is not thread-safe.

Parameters

machine_info Pointer to the machine info to deallocate properly.

size_t mcbsp_util_detect_hardware_threads ( void )

Attempts to detect the number of hard-ware threads supported on the current machine.

Returns: Detected number of HW threads.

void mcbsp_util_fatal ( void )

Handles a fatal error in a uniform fashion.

Only call this function if the error is fatal and unrecoverable, and should thus stop the entire parallel execution.

void mcbsp_util_filter_standard_pinning	(	const struct mcbsp_util_machine_info *const	info,
		size_t *const	array,
		const size_t	P
	)

Filters reserved cores from a standard pinning list.

Will substitute other HW thread numbers if available; otherwise, it will wrap to already-allocated HW threads. Assumes the data in mcbsp_util_machine_info is sorted.

Parameters

info	The full machine description.
array	The standard pinning array to modify.
P	The size of array.

int mcbsp_util_integer_compare	(	const void *	a,
		const void *	b
	)

Comparison function for use with qsort on arrays of size_t's.

size_t mcbsp_util_log2 ( size_t x )

Binary logarithm, unsigned integer version, rounding up.

Note: returns 0 for x=0.

void* mcbsp_util_malloc	(	const size_t	size,
		const char *const	name
	)

Memory allocation function used for internal MulticoreBSP for C memory areas.

Returned memory areas are guaranteed algined to MCBSP_ALIGNMENT bytes, and the returned pointer is compatible with ANSI standard free(). Should allocation fail, this function will trigger the default failure behaviour by calling mcbsp_util_fatal.

Parameters

size	The requested memory area size (in bytes).
name	Name of the array, reported to stderr in case of failure.

Returns: Pointer to the newly allocated aligned memory area of the requested size.

void mcbsp_util_memcpy	(	void *const restrict	dest,
		const void *const restrict	src,
		const size_t	size
	)

Copies the data in [src,src+size) to [dest,dest+size).

The two memory areas must not overlap (or undefined behaviour will occur).

Parameters

dest	Destination pointer.
src	Source pointer.
size	Amount of data to copy (in bytes).

struct mcbsp_util_stack mcbsp_util_partition	(	const struct mcbsp_util_machine_partition	subpart,
		const size_t	P,
		const enum mcbsp_affinity_mode	affinity
	)

Derives a P-way subpartition from a given machine partition.

Parameters

subpart	The parent partition.
P	The number of subpartitions to create.
affinity	The affinity mode to partition with.

Returns: A mcbsp_util_stack consisting of P subpartitions.

struct mcbsp_util_pinning_info mcbsp_util_pinning	(	const size_t	P,
		struct mcbsp_util_machine_info *const	machine,
		const struct mcbsp_util_machine_partition *const	super_machine
	)

Function that yields a pinning of P threads according to the given machine info.

Parameters

P	The number of threads to pin.
machine	The machine to pin for.
super_machine	The top-level machine partition, if any (can be NULL).

Returns: An array R where R[i] gives the core to which thread i should pin to.

size_t mcbsp_util_sort_unique_integers	(	size_t *const	array,
		const size_t	length,
		const size_t	lower_bound,
		const size_t	upper_bound
	)

Sorts an array of integers.

The array is assumed to hold unique elements in a given range of values. The algorithm runs linearly in the amount of possible values.

Parameters

array	The array to sort.
length	Length of array.
lower_bound	Lower bound (inclusive) on values in array.
upper_bound	Upper bound (exclusive) on values in array.

Returns: Size of the sorted array.

void mcbsp_util_stack_destroy ( struct mcbsp_util_stack *const stack )

Frees all memory related to a given stack.

Parameters

stack The stack to destroy.

bool mcbsp_util_stack_empty ( const struct mcbsp_util_stack *const stack )

Checks whether a given stack is empty.

Parameters

stack The stack to check the emptiness of.

void mcbsp_util_stack_grow	(	struct mcbsp_util_stack *const	stack,
		const size_t	target_size
	)

Increases the capacity of a given stack to match or exceed a given target capacity.

Uses recursive doubling.

Parameters

[in]	stack	the stack whose capacity to increase.
[in]	target_size	the minimum size at function exit.

void mcbsp_util_stack_initialize	(	struct mcbsp_util_stack *const	stack,
		const size_t	elementSize
	)

Initialises the mcbsp_util_stack struct.

Parameters

stack	The stack to initialise.
elementSize	The size of a single element in the stack.

void* mcbsp_util_stack_peek ( const struct mcbsp_util_stack *const stack )

Returns the top stack item.

Does not remove it from the stack.

Does not do boundary checking! Call mcbsp_util_stack_empty first when unsure if the stack still contains items.

Parameters

stack The stack to peek in to.

Returns: A pointer to the top element in the stack.

void* mcbsp_util_stack_pop ( struct mcbsp_util_stack *const stack )

Returns the newest item in the stack.

This function removes that item from the stack.

Does not do boundary checking! Call mcbsp_util_stack_empty first when unsure if the stack still contains items, or otherwise undefined behaviour may occur.

Parameters

stack The stack to pop.

Returns: A pointer to the next element in the stack.

void mcbsp_util_stack_push	(	struct mcbsp_util_stack *const	stack,
		const void *const	item
	)

Pushes a new item on the stack.

The item is assumed to be of the native stack item size, set at stack creation.

Parameters

stack	The stack on which a new element will be pushed on to.
item	Pointer to the element to push.

void mcbsp_util_translate_standard_pinning	(	const struct mcbsp_util_machine_info *const	info,
		size_t *const	array,
		const size_t	P
	)

Translates thread numbers in the standard pinning format (consecutive), to the numbering format active on this machine.

Parameters

info	The full machine description.
array	The pinning array.
P	The size of array.

void mcbsp_util_varstack_grow	(	struct mcbsp_util_stack *const	stack,
		const size_t	requested_size
	)

Doubles the capacity of a given stack that consists of elements of variable size.

Parameters

stack	The variable stack to grow.
requested_size	The minimum size the variable stack should be able to contain.

void* mcbsp_util_varstack_peek	(	const struct mcbsp_util_stack *const	stack,
		const size_t	size
	)

Peeks for a variably-sized item on the stack.

Parameters

stack	The stack to peek into.
size	The size of the top stack item.

Returns: A pointer to the top stack item.

Referenced by mcbsp_util_varstack_regpeek().

void* mcbsp_util_varstack_pop	(	struct mcbsp_util_stack *const	stack,
		const size_t	size
	)

Returns the top stack item of variable size, and shortens the stack by that item size.

Parameters

stack	Pointer to the variable stack.
size	Size of the top element of the given stack.

Returns: A pointer to the item now removed from the stack.

Referenced by mcbsp_util_varstack_regpop().

void mcbsp_util_varstack_push	(	struct mcbsp_util_stack *const	stack,
		const void *const	item,
		const size_t	size
	)

Pushes a variably-sized item on the stack.

Parameters

stack	The variable stack to push onto.
item	Pointer to the data element to push.
size	Size (in bytes) of the data element to push.

Referenced by mcbsp_util_varstack_regpush().

void* mcbsp_util_varstack_regpeek ( const struct mcbsp_util_stack *const stack )

inline

Peeks for a fixed-sized item on the stack.

(The fixed size was set at varstack initialisation.)

Note that this function is inlined because it translates to the mcbsp_util_varstack_peek.

Parameters

stack The stack to peek in to.

Returns: A pointer to the top-level item.

References mcbsp_util_varstack_peek(), and mcbsp_util_stack::size.

void* mcbsp_util_varstack_regpop ( struct mcbsp_util_stack *const stack )

inline

Returns the top fixed-size item of the stack.

The returned item is removed from the stack. (The fixed size was set at varstack initialisation.)

Note that this function is inlined because it translates to the mcbsp_util_varstack_pop.

Parameters

stack The variable stack to pop.

Returns: The element just removed from the variable stack.

References mcbsp_util_varstack_pop(), and mcbsp_util_stack::size.

void mcbsp_util_varstack_regpush	(	struct mcbsp_util_stack *const	stack,
		const void *const	item
	)

inline

Pushes a fixed-size item on the stack.

(The fixed size was set at varstack initialisation.)

Note that this function is inlined because it translates to the mcbsp_util_varstack_push.

Parameters

stack	The stack to push on to.
item	The item to push on to the given stack.

References mcbsp_util_varstack_push(), and mcbsp_util_stack::size.

Variable Documentation

struct mcbsp_util_address_map MCBSP_UTIL_EMPTY_ADDRESS_MAP

A default initialiser of type mcbsp_util_address_map.

Data Structures

Functions

Variables

Function Documentation

Variable Documentation