https://www.liblfds.org/mediawiki/api.php?action=feedcontributions&user=Admin&feedformat=atomliblfds.org - User contributions [en-gb]2024-03-29T14:07:21ZUser contributionsMediaWiki 1.36.0https://www.liblfds.org/mediawiki/index.php?title=Main_Page&diff=1226Main Page2021-06-08T08:24:10Z<p>Admin: </p>
<hr />
<div><table cellspacing="8" style="width:100%; margin:0; background:none;"><br />
<tr style="width:56%;"><br />
<td style="color:#000; background:#fcfcfc; margin-top:1.2em; border:1px solid #ccc;"><br />
<table style="width:280px; border:none; background:none;"><br />
<tr style="width:280px; text-align:center; white-space:nowrap; color:#000;"><br />
<td><br />
<div style="font-size:162%; border:none; margin:0; padding:.1em; color:#000;">Welcome to liblfds.org,</div><br />
<div style="top:+0.2em; font-size:95%;">a lock-free data structure library.</div><br />
<div style="font-size:85%;">[[Special:Statistics|{{NUMBEROFARTICLES}}]] articles</div><br />
</td><br />
</tr><br />
</table><br />
</td><br />
</tr><br />
<br />
<!-- ******************************************************************************************************** --><br />
<br />
<tr><br />
<td style="border:1px solid #cef2e0; background:#f5fffa;"><br />
<table width="100%"><br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; font-weight:bold; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">Overview</h2><br />
</td><br />
<br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">As of 2021-06-07, the site has migrated to a new server. The Mediawiki migration has been rather fumbling - the usual mysterious functionality, lack of docs and error messages - but it seems now to be okay, except that a certain number of links are now showing in red, which indicates they do not exist, when they do exist. In any event, markdown/pandoc is now used and will be used for future documentation. The Mediawiki is maintained to support existing releases.</h2><br />
</td><br />
</tr><br />
<br />
<tr valign="top"><br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Documentation</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
* [[Introduction]]<br />
* [[Contributors]]<br />
* [[Articles]]<br />
* [[White Papers]]<br />
* [[Links]]<br />
* [[Next Release Status / New Features]]<br />
<br />
</div><br />
</td><br />
<br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Notes</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
Account creation and anonymous editing are disabled due to bots. Email (admin at liblfds dot org) should you wish for an account.<br />
<br />
</div><br />
<br />
</td><br />
</tr><br />
</table><br />
</td><br />
</tr><br />
<br />
<!-- ******************************************************************************************************** --><br />
<br />
<tr><br />
<td style="border:1px solid #cef2e0; background:#f5fffa;"><br />
<table width="100%"><br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; font-weight:bold; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">The Library</h2><br />
</td><br />
</tr><br />
<br />
<tr valign="top"><br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Documentation</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
* [[r6:Release 6 Documentation|Release 6]] <small>(29th Dec 2009)</small><br />
* [[r6.0.0:Release 6.0.0 Documentation|Release 6.0.0]] <small>(18th Dec 2012)</small><br />
* [[r6.1.0:Release 6.1.0 Documentation|Release 6.1.0]] <small>(31th Dec 2012)</small><br />
* [[r6.0.1:Release 6.0.1 Documentation|Release 6.0.1]] <small>(2nd Jan 2013)</small><br />
* [[r6.1.1:Release 6.1.1 Documentation|Release 6.1.1]] <small>(2nd Jan 2013)</small><br />
* [[r7.0.0:Release 7.0.0 Documentation|Release 7.0.0]] <small>(29th Dec 2015)</small><br />
* [[r7.1.0:Release 7.1.0 Documentation|Release 7.1.0]] <small>(31st May 2016)</small><br />
* [[r7.1.1:Release 7.1.1 Documentation|Release 7.1.1]] <small>(20th Feb 2017)</small><br />
<br />
</div><br />
<br />
</td><br />
<br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Notes</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
Release 6 is the original liblfds prior to the new versioning scheme.<br />
<br />
Release 6.0.0 is release 6 with and with only API and filename name changes so that it moves into the new namespace scheme, such that every version can be included and linked to concurrently in the same application. The code otherwise is ''completely'' unchanged.<br />
<br />
</div><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
__NOTOC__</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Porting_Guide_(liblfds)&diff=1169r7.1.1:Porting Guide (liblfds)2019-03-05T11:01:45Z<p>Admin: /* Partial Implementatons */</p>
<hr />
<div>{{DISPLAYTITLE:Porting Guide (liblfds)}}<br />
==Introduction==<br />
To permit ''liblfds'' to work on a range of platforms a porting abstraction layer has been written. Porting means to implement the porting abstraction layer for the new platform; the library will then compile and work. Implementating means providing values to a small set defines, macros and typedefs.<br />
<br />
==The Porting Abstraction Layer==<br />
Each of the compiler, the operating system and the processor turns out to be a source of information for a porting abstraction layer and so the porting abstraction layer is arranged as three header files, one for each, thus;<br />
<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_porting_abstraction_layer_compiler.h<br />
lfds711_porting_abstraction_layer_operating_system.h<br />
lfds711_porting_abstraction_layer_processor.h<br />
<br />
Each header file uses #ifdefs and compiler defined macros to select the appropriate porting abstraction layer implementation for the local platform.<br />
<br />
So, for example, in ''lfds711_porting_abstraction_layer_compiler.h'', for MSVC version 1400 and higher, we see the following;<br />
<br />
#if( defined _MSC_VER && _MSC_VER >= 1400 )<br />
[snip porting abstraction layer implementation]<br />
#endif<br />
<br />
Accordingly, to add a new platform, introduce a new #ifdef, which matches the appropriate compiler defined macros for your platform.<br />
<br />
===''lfds711_porting_abstraction_layer_compiler.h''===<br />
<br />
#define [[r7.1.1:define LFDS711_PAL_COMPILER_STRING|LFDS711_PAL_COMPILER_STRING]]<br />
#define [[r7.1.1:macro LFDS711_PAL_ALIGN|LFDS711_PAL_ALIGN]]( alignment )<br />
#define [[r7.1.1:define LFDS711_PAL_INLINE|LFDS711_PAL_INLINE]]<br />
#define [[r7.1.1:define LFDS711_PAL_BARRIER_COMPILER_LOAD|LFDS711_PAL_BARRIER_COMPILER_LOAD]]<br />
#define [[r7.1.1:define LFDS711_PAL_BARRIER_COMPILER_STORE|LFDS711_PAL_BARRIER_COMPILER_STORE]]<br />
#define [[r7.1.1:define LFDS711_PAL_BARRIER_COMPILER_FULL|LFDS711_PAL_BARRIER_COMPILER_FULL]]<br />
#define [[r7.1.1:define LFDS711_PAL_BARRIER_PROCESSOR_LOAD|LFDS711_PAL_BARRIER_PROCESSOR_LOAD]]<br />
#define [[r7.1.1:define LFDS711_PAL_BARRIER_PROCESSOR_STORE|LFDS711_PAL_BARRIER_PROCESSOR_STORE]]<br />
#define [[r7.1.1:define LFDS711_PAL_BARRIER_PROCESSOR_FULL|LFDS711_PAL_BARRIER_PROCESSOR_FULL]]<br />
#define [[r7.1.1:macro LFDS711_PAL_ATOMIC_ADD|LFDS711_PAL_ATOMIC_ADD]]( pointer_to_target, value, result, result_type )<br />
#define [[r7.1.1:macro LFDS711_PAL_ATOMIC_CAS|LFDS711_PAL_ATOMIC_CAS]]( pointer_to_destination, pointer_to_compare, new_destination, cas_strength, result )<br />
#define [[r7.1.1:macro LFDS711_PAL_ATOMIC_DWCAS|LFDS711_PAL_ATOMIC_DWCAS]]( pointer_to_destination, pointer_to_compare, pointer_to_new_destination, cas_strength, result )<br />
#define [[r7.1.1:macro LFDS711_PAL_ATOMIC_EXCHANGE|LFDS711_PAL_ATOMIC_EXCHANGE]]( pointer_to_destination, pointer_to_exchange )<br />
#define [[r7.1.1:macro LFDS711_PAL_ATOMIC_SET|LFDS711_PAL_ATOMIC_SET]]( pointer_to_destination, exchange )<br />
<br />
===''lfds711_porting_abstraction_layer_operating_system.h''===<br />
<br />
#define [[r7.1.1:define LFDS711_PAL_OS_STRING|LFDS711_PAL_OS_STRING]]<br />
#define [[r7.1.1:macro LFDS711_PAL_ASSERT|LFDS711_PAL_ASSERT]]( expression )<br />
<br />
===''lfds711_porting_abstraction_layer_processor.h''===<br />
<br />
typedef [type] [[r7.1.1:typedef lfds711_pal_int_t|lfds711_pal_int_t]];<br />
typedef [type] [[r7.1.1:typedef lfds711_pal_uint_t|lfds711_pal_uint_t]];<br />
#define [[r7.1.1:define LFDS711_PAL_PROCESSOR_STRING|LFDS711_PAL_PROCESSOR_STRING]]<br />
#define [[r7.1.1:define LFDS711_PAL_ALIGN_SINGLE_POINTER|LFDS711_PAL_ALIGN_SINGLE_POINTER]]<br />
#define [[r7.1.1:define LFDS711_PAL_ALIGN_DOUBLE_POINTER|LFDS711_PAL_ALIGN_DOUBLE_POINTER]]<br />
#define [[r7.1.1:define LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES|LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES]]<br />
<br />
==Partial Implementatons==<br />
It is not necessary to fully implement a porting abstraction layer. Only part, and the simple part, of the porting layer is mandatory. Dummy versions are provided for everything non-mandatory, so the library will compile and work once that which is mandatory has been provided.<br />
<br />
Naturally, if a data structure depends on a given part or parts of the porting abstraction layer and those parts have not been implemented, then that data structure cannot work.<br />
<br />
The data structures have the following requirements;<br />
<br />
<table border="1" cellpadding="4"><br />
<tr><br />
<th colspan="7">Data Structure by Atomic Operations</th><br />
</tr><br />
<br />
<tr><br />
<th>&nbsp;</th><br />
<th>Memory<BR>Barriers</th><br />
<th>Add</th><br />
<th>CAS</th><br />
<th>DWCAS</th><br />
<th>Exchange</th><br />
<th>Set</th><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Binary Tree (add-only, unbalanced)</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Freelist</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Hash (add-only)</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">List (add-only, ordered, singly-linked)</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">List (add-only, singly-linked, unordered)</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">PRNG</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Queue, bounded, single producer, single consumer</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Queue, bounded, many producer, many consumer</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Queue, unbounded, many producer, many consumer</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Ringbuffer</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
<br />
<tr align="center"><br />
<th align="left">Stack</th><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_green.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
<td><img src="http://www.liblfds.org/pages/images/button_red.png"/></td><br />
</tr><br />
</table><br />
<br />
The atomic operations above map to the following porting layer macros;<br />
<br />
<table border="1" cellpadding="4"><br />
<tr><br />
<th colspan="7">Atomic Operations</th><br />
</tr><br />
<br />
<tr><br />
<th align="left">Memory Barriers</th><br />
<td>LFDS711_PAL_BARRIER_PROCESSOR_LOAD<br>LFDS711_PAL_BARRIER_PROCESSOR_STORE<br>LFDS711_PAL_BARRIER_PROCESSOR_FULL</td><br />
</tr><br />
<br />
<tr><br />
<th align="left">Add</th><br />
<td>LFDS711_PAL_ATOMIC_ADD</td><br />
</tr><br />
<br />
<tr><br />
<th align="left">CAS</th><br />
<td>LFDS711_PAL_ATOMIC_CAS</td><br />
</tr><br />
<br />
<tr><br />
<th align="left">DWCAS</th><br />
<td>LFDS711_PAL_ATOMIC_DWCAS</td><br />
</tr><br />
<br />
<tr><br />
<th align="left">Exchange</th><br />
<td>LFDS711_PAL_ATOMIC_EXCHANGE</td><br />
</tr><br />
<br />
<tr><br />
<th align="left">Set</th><br />
<td>LFDS711_PAL_ATOMIC_SET</td><br />
</tr><br />
</table><br />
<br />
So, for example, if you port to some new platform and implement only memory barriers and DWCAS, then you can use the bounded, single producer, single consumer queue, the unbounded queue, the ringbuffer and the stack.<br />
<br />
The library will compile fully, but if you try to use the other data structures, you will call a dummy version of one of the other atomic operations, where those dummy functions intentionally try to write 0 to memory location 0, so you notice the error of your ways.<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:LFDS711_PAL_COMPILER_BARRIERS_MISSING_PRESUMED_HAVING_A_GOOD_TIME&diff=1032r7.1.1:LFDS711 PAL COMPILER BARRIERS MISSING PRESUMED HAVING A GOOD TIME2019-03-05T10:36:28Z<p>Admin: /* Optionality */</p>
<hr />
<div>{{DISPLAYTITLE:define LFDS711_PAL_COMPILER_BARRIERS_MISSING_PRESUMED_HAVING_A_GOOD_TIME}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_porting_abstraction_layer_compiler.h<br />
<br />
==Define==<br />
#define LFDS711_PAL_COMPILER_BARRIERS_MISSING_PRESUMED_HAVING_A_GOOD_TIME<br />
<br />
==Optionality==<br />
This define must be specified (its value is never used, so it merely needs to be set) if the ''LFDS711_PAL_BARRIER_COMPILER_*'' defines are not needed for a platform. If the ''LFDS711_PAL_BARRIER_COMPILER_*'' defines are needed ''but not provided'', the define must be absent.<br />
<br />
==Notes==<br />
Usually, the compiler barrier defines need to be specified in a porting abstraction layer. However, there is one current platform which does not require this, as the compiler defines are built into the compiler atomic intrinsics, and hopefully there will be more in the future. When the compiler barrier defines are not needed, because they are built-in, this define must be set. When the compiler barrier defines are neededd but simply are not provided, then this define must be absent.<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (liblfds)|Porting Guide (liblfds)]]<br />
* [[r7.1.1:define LFDS711_PAL_BARRIER_COMPILER_LOAD|LFDS711_PAL_BARRIER_COMPILER_LOAD]]<br />
* [[r7.1.1:define LFDS711_PAL_BARRIER_COMPILER_STORE|LFDS711_PAL_BARRIER_COMPILER_STORE]]<br />
* [[r7.1.1:define LFDS711_PAL_BARRIER_COMPILER_FULL|LFDS711_PAL_BARRIER_COMPILER_FULL]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=Article:CAS_and_LL/SC_Implementation_Details_by_Processor_family&diff=829Article:CAS and LL/SC Implementation Details by Processor family2019-03-01T23:21:34Z<p>Admin: /* Processor Families Implementating LL/SC */</p>
<hr />
<div>==Introduction==<br />
There exist a small set of distinct processor families which support CAS or LL/SC. Implementation details vary by platform and are important for software implementation.<br />
<br />
==CAS==<br />
CAS (Compare-and-Swap) implementations offer a small set of atomic instructions, such as ADD or EXCHANGE. These and only these instructions are atomic. The instructions have no failure mode - they are issued, and they take however long they take, and then they are done. If a CAS operation is issued, it will always succeed ''in the sense that the instruction was issued and performed'', but of course the compare being performed by the CAS may not be equal and so the target of the CAS then is not updated by the swap value.<br />
<br />
CAS means to compare-and-swap one word. DWCAS means to compare-and-swap two contigious words of memory. Only the Compare-and-Swap instruction ever offers double-word - all the others, ADD, EXCHANGE, etc, are always one word.<br />
<br />
==LL/SC==<br />
LL/CS (Load-Linked and Conditional-Store) implementations offer two instructions, LL and SC (different processor families have different names for them), where the LL loads from memory into a register but in some way monitors the memory location loaded; the caller can then continue as usual, using the whole instruction set, until the caller finally comes to issue the SC, which has to store back to the address loaded from, and where the SC operation will fail if the contents of that address have changed since the load.<br />
<br />
The nature of the monitoring of the load address varies by family. Some families allow one monitor per processor; others allow have one monitor per n bytes of memory (so that any write inside the zone (known as an "Exclusive Reservation Granule") containing the load address, by any processor, causes the store to fail), etc. For almost all processor families, only one LL can be held at a time, so issuing a second LL invalidates the first, and a context switch on a processor holding an LL normally causes the SC to fail always, when it comes to be performed.<br />
<br />
LL/SC is usually used to emulate CAS, which is to say, LL/SC is used to write a tiny bit of code which loads a target memory address, compares it to a comparand, and then writes back a swap value to the target if the comparand and target values are equal.<br />
<br />
Because the SC can fail spuriously (context switch, another processor writes into the monitor zone, etc), we see here unlike real CAS, we can see the instruction ''itself'' fail, as well as the compare itself "fail" (not be equal). This is what GCC (version 4.7.3 or greater, the new instrinics, not the old ones) is referring to in its atomic instrinics what it talks about "weak" and "strong" atomic operations. A weak operation means issue the LL/SC once, and come back with the result, even if the failure is actually a spurious failure (the target and comparand are equal, but the SC operation reported failure to write); a strong operation means loop on the LL/SC operation until the SC operation comes back with a failure or success which matches whether or not the target and comparand are equal.<br />
<br />
==Processor Families Implementating CAS==<br />
<br />
* IA64<br />
* SPARC<br />
* x64<br />
* x86<br />
<br />
==Processor Families Implementating LL/SC==<br />
<br />
* 68k<br />
* Alpha<br />
* ARM<br />
* MIPS<br />
* POWERPC<br />
* RISC V<br />
<br />
==Implementation Details==<br />
<br />
===IA64===<br />
* CAS<br />
* no DWCAS as such, but there is an instruction to compare one word and then to write back two, and this is all you need for ABA with counters; you compare the counter, and if it differs, you swap both the pointer and counter<br />
<br />
===SPARC===<br />
* CAS<br />
* no DWCAS<br />
<br />
===x64===<br />
* CAS<br />
* DWCAS<br />
* Note Intel by default (can be disabled in some BIOSes) fetches both the cache line you've asked for AND THE FOLLOWING CACHE-LINE, ALWAYS. As such atomic isolation on Intel is actually twice the cache line size.<br />
<br />
===x86===<br />
* CAS<br />
* DWCAS introduced either with the 386 or 486.<br />
<br />
===68k===<br />
* CAS<br />
* DCAS - not DWCAS - but DCAS; the ability to atomically compare-and-swap two *distinct* memory addresses.<br />
<br />
===Alpha===<br />
* LL/SC<br />
* Unknown DW LL/SC<br />
<br />
===ARM===<br />
* LL/SC<br />
* DW LL/SC (from architecture ARM6k onwards)<br />
* One LL/SC pair active per processor at any one time, uses an Exclusive Reservation Granule from 8 to 2048 bytes, but also has the concept of a per-processor (local) monitor and a global (system-wide) monitor. If the LL/SC is on a cache-line which is exclusive, only the local monitor is invoked, and the local monitor can be very weak indeed - it may even only keep track of whether or not a second LL has been issued since the original!<br />
* ERG size is 8 to 2048 bytes for both ARM32 ''and'' ARM64. The size has not changed for ARM64.<br />
<br />
===MIPS===<br />
* LL/SC<br />
* no DW LL/SC<br />
* One active LL/SC pair per processor.<br />
<br />
===POWERPC===<br />
* LL/SC<br />
* no DW LL/SC</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Freelist&diff=1109r7.1.1:Freelist2019-02-23T10:09:03Z<p>Admin: /* Benchmark Results and Analysis */</p>
<hr />
<div>{{DISPLAYTITLE:Freelist}}<br />
==Source Files==<br />
└───liblfds711<br />
├───inc<br />
│ └───liblfds711<br />
│ lfds711_freelist.h<br />
└───src<br />
└───lfds711_freelist<br />
lfds711_freelist_cleanup.c<br />
lfds711_freelist_init.c<br />
lfds711_freelist_internal.h<br />
lfds711_freelist_pop.c<br />
lfds711_freelist_push.c<br />
lfds711_freelist_query.c<br />
<br />
==Defines==<br />
#define [[r7.1.1:define LFDS711_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS|LFDS711_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS]]<br />
<br />
==Enums==<br />
enum [[r7.1.1:enum lfds711_freelist_query|lfds711_freelist_query]];<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct lfds711_freelist_element|lfds711_freelist_element]];<br />
struct [[r7.1.1:struct lfds711_freelist_state|lfds711_freelist_state]];<br />
<br />
==Macros==<br />
#define [[r7.1.1:macro LFDS711_FREELIST_GET_KEY_FROM_ELEMENT|LFDS711_FREELIST_GET_KEY_FROM_ELEMENT]]( freelist_element )<br />
#define [[r7.1.1:macro LFDS711_FREELIST_SET_KEY_IN_ELEMENT|LFDS711_FREELIST_SET_KEY_IN_ELEMENT]]( freelist_element, new_key )<br />
<br />
#define [[r7.1.1:macro LFDS711_FREELIST_GET_VALUE_FROM_ELEMENT|LFDS711_FREELIST_GET_VALUE_FROM_ELEMENT]]( freelist_element )<br />
#define [[r7.1.1:macro LFDS711_FREELIST_SET_VALUE_IN_ELEMENT|LFDS711_FREELIST_SET_VALUE_IN_ELEMENT]]( freelist_element, new_value )<br />
<br />
#define [[r7.1.1:macro LFDS711_FREELIST_GET_USER_STATE_FROM_STATE|LFDS711_FREELIST_GET_USER_STATE_FROM_STATE]]( freelist_state )<br />
<br />
==Prototypes==<br />
void [[r7.1.1:function lfds711_freelist_init_valid_on_current_logical_core|lfds711_freelist_init_valid_on_current_logical_core]]( struct lfds711_freelist_state *fs,<br />
struct lfds711_freelist_element * volatile (*elimination_array)[LFDS711_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS],<br />
lfds711_pal_uint_t elimination_array_size_in_elements,<br />
void *user_state );<br />
<br />
void [[r7.1.1:function lfds711_freelist_cleanup|lfds711_freelist_cleanup]]( struct lfds711_freelist_state *fs,<br />
void (*element_cleanup_callback)(struct lfds711_freelist_state *fs, struct lfds711_freelist_element *fe) );<br />
<br />
void [[r7.1.1:function lfds711_freelist_push|lfds711_freelist_push]]( struct lfds711_freelist_state *fs,<br />
struct lfds711_freelist_element *fe,<br />
struct lfds711_prng_st_state *psts );<br />
<br />
int [[r7.1.1:function lfds711_freelist_pop|lfds711_freelist_pop]]( struct lfds711_freelist_state *fs,<br />
struct lfds711_freelist_element **fe,<br />
struct lfds711_prng_st_state *psts );<br />
<br />
void [[r7.1.1:function lfds711_freelist_query|lfds711_freelist_query]]( struct lfds711_freelist_state *fs,<br />
enum lfds711_freelist_query query_type,<br />
void *query_input,<br />
void *query_output );<br />
<br />
==Overview==<br />
This data structure implements a freelist.<br />
<br />
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.<br />
<br />
General usage is that the user calls ''lfds711_freelist_init_valid_on_current_logical_core'' to initialize a ''struct lfds711_freelist_state'', and then calls ''lfds711_freelist_push'' and ''lfds711_freelist_pop'' to push and pop ''struct lfds711_freelist_element''s. A freelist element provides the ability to store a key and a value, both of which are of type ''void *''. The key is not used in any way by the freelist (and of course the value is neither), rather, it is available as a convenience for the user, for situations where data is being transferred between different types of data structures, where some of these data structures do support a meaningful key. The key and value are get and set by macros, such as ''LFDS711_FREELIST_SET_VALUE_IN_ELEMENT''. The SET macros can only be used when an element is outside of the freelist. (Things may seem to work even if they are used on elements which are in the freelist, but it's pure chance. Don't do it).<br />
<br />
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)<br />
<br />
The state and element structures are both public, present in the ''lfds711_freelist.h'' header file, so that users can embed them in their own structures (and where necessary pass them to ''sizeof''). Expected use is that user structures which are to enter freelists contain within themselves a ''struct lfds711_freelist_element'', and this is used when calling ''lfds711_freelist_push'', and the value set in the freelist element is a pointer to the user structure entering the freelist. This approach permits zero run-time allocation of store and also ensures the freelist element is normally in the same memory page as the user data it refers to.<br />
<br />
==Lock-free Specific Behaviour==<br />
The state initialization function, ''lfds711_freelist_init_valid_on_current_logical_core'', as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro ''[[r7.1.1:define LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'', which will do that which its name suggests.<br />
<br />
The freelist internally implements autotuning exponential backoff, which (as can be seen in the benchmark section) improves performance by about a factor of five on a Core i5.<br />
<br />
The SET macros (for setting key and value, in stack elements) can only be correctly used on elements which are outside of a freelist, and the GET macros, if called by a thread on a logical core other than the logical core of the thread which called the SET macros, can only be correctly used on a freelist element which has been pushed to the freelist and then popped.<br />
<br />
By correctly is it meant to say that the GET macros will actually read the data written by the SET macros, and not some other data.<br />
<br />
The freelist should be regarded as a safe communication channel between threads. Any freelist element which has a key and/or value set, and then is pushed to a freelist, will allow any thread which pops that element to correctly read the key and/or value (and by this is it meant to say not just the void pointer of the key and value, but also whatever they point to). This is the only guarantee. Any reads or writes of key and/or value, or what they point to, which occur outside of this pushing and popping pair are not guaranteed to be correct; the data written may never be seen by other threads.<br />
<br />
Once a freelist element structure has been pushed to the stack, it cannot be deallocated (''free'', or stack allocation lifetimes ending due to say a thread ending, etc) until ''lfds711_freelist_cleanup'' has returned. Typical usage of course with a freelist is as a store for unused elements, so this restriction in fact is in line with normal usage.<br />
<br />
===Elimination Array===<br />
The freelist also provides support for what is known as an ''elimination array''. This is a method which improves performance. The key performance bottleneck for the freelist is that all threads are trying to read and write to the freelist head pointer. The contention on this one pointer is as high as it possibly can be. A way around this, the elimination array, comes from the insight that a push and a pop operation cancel each other out - so if we have two threads, and one wants to push and the other to pop, if they could somehow communicate, they could solve each others problem without having to touch the freelist head pointer. The pushing thread would hand its element over to the poppping thread - et voilà!<br />
<br />
The implemention consists of an array of cache-line length elements, where each of these cache-line length elements is treated as an array of pointers to freelist elements. The pointers are initially set to NULL. When a thread wishes to push, it randomly selects a line and then scans it from left to right. If it finds a NULL pointer, it performs an atomic exchange with the pointer it holds which it wishes to push. If the exchange returns NULL, then the thread has successfully placed its element in the elimination array and its push operation is complete. If the exchange returns a pointer, then another thread managed to grab that slot before the current thread; as such, the current thread's element is now in the elimination array, but it now holds ''another'' pointer, which it still has to deal with - so it continues to scan the selected cache line for another NULL pointer. If no NULL pointers are found, the thread pushes as normal to the freelist, using the freelist head pointer.<br />
<br />
When a thread wishes to pop, it randomly selects a cache line in the elimination array and as with pushing then scans it from left to right. A popping thread howeer is not looking for NULLs, but for pointers to freelist elements, as set by the pushing threads. If a pointer is found, the thread performs an exchange with NULL. If the exchange returns a pointer, then the thread has successfully obtained an element from the elimination array and the pop operation is complete. If the exchange is NULL, another thread managed to grab that element just before the current thread. The slot in the elimination layer is still set to NULL, and so still is correctly available to pushing threads, and the popping thread continues to scan the cache line. If no pointers are found, the thread pops as normal from the freelist, using the freelist head pointer.<br />
<br />
This implemention leads to two considerations.<br />
<br />
Firstly, thread need to randomly select cache lines in the elimination array. This implies random number generation. Where ''liblfds'' targets a bare C implementation, and where the C implementation of rand() is anyway typically a function call, slow internally, of exceedingly poor quality and not thread safe, ''liblfds'' has implemented its own PRNG API. This API offers both a lock-free and a single-threaded PRNG. The lock-free PRNG has internally a single word-length store which is the target of an atomic add per random number generation. This means the more threads use a single lock-free PRNG instance, the more contention there is, and the worse performance becomes. If the freelist were to use a lock-free PRNG for random number generation, the performance hit taken thereby would massively and profoundly outweight the performance gain from the elimination array. As such, the freelist uses a single-threaded PRNG, and so being single-threaded is provided by the user to the ''[[r7.1.1:function lfds711_freelist_push|lfds711_freelist_push]]'' and ''[[r7.1.1:function lfds711_freelist_push|lfds711_freelist_push]]'' functions.<br />
<br />
Providing a per-thread state can be onerous or even impossible and as such, the PRNG argument to the push and pop functions can be NULL even though the elimination array is in use (the elimination array is optional; the user can indicate it is not to be used). In this case, in the push function, the actual value of the freelist element pointer argument is passed through the PRNG mixing function and used as the random value to select a cache line, and in the pop function, the actual value of the freelist element pointer to poiner argument is likewise used. As such, if a given thread has for example a single freelist pointer on its stack and is always using that pointer to pop and then push elements, that thread will always be choosing the same cache line from the elimination array, and the performance gain from the elimination array will be reduced.<br />
<br />
Secondly, where a popping thread only scans a single line of the elimination array before turning to the freelist, if the freelist proper is empty and the popping thread scans an elimination array line which is empty, the popping thread will fail to pop - even though there could be available freelist elements in other elimination array cache lines. The solution to this is to provide additional elements when initializing the freelist array, equal to the size of the elimination array minus one cache line, so that the expected number of elements will always be available. The number of additional elements required can be obtained from a call to [[r7.1.1:function lfds711_freelist_query|lfds711_freelist_query]].<br />
<br />
The size of the elimination array is chosen by the user. If the elimination array is very large, the overhead of additional elements is large. If the elimination layer is very small, the benefits are reduced. The recommended size is to consider the typical number of threads generally using the freelist, and have one cache line per thread.<br />
<br />
Note that use of the array is optional - a NULL pointer and 0 size can be passed in (and then the ''psts'' arguments to the push and pop functions are ignored. The main purpose for this option however is to facilitate the ''liblfds'' test suite, as the elimination array by randomizing the order of elements moving into and out of the freelist prevents certain forms of testing.<br />
<br />
==Benchmark Results and Analysis==<br />
<html><br />
<table border="1" cellpadding="8"><br />
<tr><br />
<th class="header" colspan="3">freelist</th><br />
<tr><br />
<br />
<tr><br />
<th class="header">ARM32</th><br />
<th class="header" colspan="2">x64</th><br />
</tr><br />
<br />
<tr><br />
<th class="header">Raspberry Pi 2 Model B</th><br />
<th class="header">AWS dedicated VM</th><br />
<th class="header">Core i5</th><br />
</tr><br />
<br />
<tr><br />
<td><a href="/pages/images/liblfds710_freelist_push1_then_pop1_smp_Raspberry Pi 2 Model B (ARM32).1200x1800.png"><img src="/pages/images/liblfds710_freelist_push1_then_pop1_smp_Raspberry Pi 2 Model B (ARM32).300x450.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_freelist_push1_then_pop1_numa_Amazon VM dedicated c4.4xlarge.4800x5400.png"><img src="/pages/images/liblfds710_freelist_push1_then_pop1_numa_Amazon VM dedicated c4.4xlarge.300x337.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_freelist_push1_then_pop1_numa_Core i5 (x64).1200x1800.png"><img src="/pages/images/liblfds710_freelist_push1_then_pop1_numa_Core i5 (x64).300x450.png"/></a></td><br />
</tr><br />
</table><br />
</html><br />
<br />
A benchmark operation is a pop-push pair.<br />
<br />
A freelist, in its straightforward form, has a single memory address which experiences intense memory contention - the head pointer in the freelist state. This means that such implementations cannot scale. As the core count rises, the single-threaded performance is simply distributed amongst the cores, with increasing inefficiency losses from contention.<br />
<br />
The lock-free implemention in 7.0.0 features exponential backoff, which improve performance by a factor of about 5x. (Benchmarks for earlier versions are not yet available - however, during development, benchmarks were made with and without backoff). With contended memory locations, backoff is absolutely profoundly fundamentally important. Without it, performance is no greater than locking solutions.<br />
<br />
Release 7.1.1 features autotuning exponential backoff, which is absolutely necessary, as the optimal backoff value varies by many factors, such as the processor/memory topology and how busy the freelist is at the current time (how mnay threads are attempting concurrent accesses), such that the optimal value is never fixed and so cannot be set statically.<br />
<br />
However, release 7.1.1 also implemented an elimination layer. This acts to address the memory contention on the freelist head pointer - it distributes access over a number of cache lines (the user can choose how many, but if we consider the maximum number of threads which could concurrently access the freelist, it should be at least one cache line per thread).<br />
<br />
This has NOT led to the expected massive performance gains, indeed it has led in many cases to perforannce loss, and it is not yet apparent why. One possible reason is the lack of backoff in the elimination layer. Real gains are shown on the 16 core AWS VM, when one thread is run per physical processor. With six or more threads running, the elimination layer roughly doubles performance. However, this is still entirely out of line with expectations. The expectation is single-thread like performance which scales.<br />
<br />
For now, it's adviseable not to use the elimination layer (it is optional), but to use 7.1.1 rather than 7.0.0 (to get the autotuning backoff).<br />
<br />
Changing subject, one particular note of interest is that of the performance of the new GCC "atomic" intrinsics vs the old GCC "sync" intrinsics. The underlying atomic operation is identical, but the old sync instrincs always issue a memory barrier, where the new atomic instrincs only issue a memory barrier if you tell them to.<br />
<br />
If we look at the ARM32 gnuplot, at the single core chart, at the first two bars, we see the first bar (GCC atonic) is about 25% higher than the second bar (GCC sync). The freelist pop operation does not require a memory barrier, and so the difference between those two benchmarks is and is only the extra memory barrier being issued by the old sync atomic during the pop operation.<br />
<br />
==White Paper==<br />
This is an implementation of ''the'' classic lock-free data structure, by R. K. Treiber, back from 1986. Treiber published a long pamphlet, "Systems Programming: Coping with Parallelism", which amongst other things described the use of compare-and-swap on some contemporary IBM mainframe hardware to implement a stack (conceptually identical to a freelist).<br />
<br />
==License==<br />
Unclear. However, no patent is known and the design is massively used throughout the industry. The autotuning backoff is derived from the design of ethernet backoff (it is ethernet backoff, but without the random component) but the implementation is native to ''liblfds''. The elimination layer was inspired by a sentence (the insight that a push and pop cancel each other out) from a paragraph from the introduction in the white paper [[Hendler, Shavit, Yerushalmi - A Scalable Lock-Free Stack Algorithm]], but the white paper was not read and so its implementation is unknown, and so the implementation used here is native to ''liblfds''.<br />
<br />
==Example==<br />
#include <stdio.h><br />
#include <stdlib.h><br />
#include "liblfds711.h"<br />
<br />
struct test_data<br />
{<br />
struct lfds711_freelist_element<br />
fe;<br />
<br />
int<br />
buffer[1024];<br />
};<br />
<br />
int main()<br />
{<br />
lfds711_pal_uint_t<br />
additional_element_count,<br />
total_element_count;<br />
<br />
struct lfds711_freelist_element<br />
* volatile (*elimination_array)[LFDS711_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS];<br />
<br />
struct lfds711_freelist_element<br />
*fe;<br />
<br />
struct lfds711_freelist_state<br />
fs;<br />
<br />
struct lfds711_prng_st_state<br />
*psts;<br />
<br />
struct test_data<br />
*td,<br />
*temp_td;<br />
<br />
/* TRD : the caller decides the elimination array size<br />
must be multiples of sizeof(struct lfds711_freelist_element) * LFDS711_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS<br />
and aligned on LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES<br />
*/<br />
<br />
elimination_array = aligned_malloc( 4 * sizeof(struct lfds711_freelist_element) * LFDS711_FREELIST_ELIMINATION_ARRAY_ELEMENT_SIZE_IN_FREELIST_ELEMENTS, LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES );<br />
<br />
lfds711_freelist_init_valid_on_current_logical_core( &fs, ea, 4, NULL );<br />
<br />
// TRD : the freelist push and pop functions benefit from a PRNG (it's not mandatory, but use it if you can)<br />
lfds711_prng_st_init( &ps, LFDS711_PRNG_SEED );<br />
<br />
/* TRD : so now we want a freelist with say 100 elements in<br />
however, we must allocate some additional elements because of the elimination array<br />
*/<br />
<br />
lfds711_freelist_query( &fs, LFDS711_FREELIST_QUERY_GET_ELIMINATION_ARRAY_EXTRA_ELEMENTS_IN_FREELIST_ELEMENTS, NULL, (void *) &additional_element_count );<br />
<br />
total_element_count = 100 + additional_element_count;<br />
<br />
td = malloc( sizeof(struct test_data) * total_element_count );<br />
<br />
for( loop = 0 ; loop < total_element_count ; loop++ )<br />
{<br />
LFDS711_FREELIST_SET_VALUE_IN_ELEMENT( td[loop].fe, &td[loop] );<br />
lfds711_freelist_push( &fs, &td[loop].fe, &ps );<br />
} <br />
<br />
// TRD : now we have a freelist with a 100 guaranteed elements (the extra in the elimination array might be available)<br />
<br />
// TRD : pop the freelist<br />
while( lfds711_freelist_pop(&fs, &fe, &ps) )<br />
{<br />
temp_td = LFDS711_FREELIST_GET_VALUE_FROM_ELEMENT( *fe );<br />
<br />
// TRD : here we can use temp_td->buffer<br />
}<br />
<br />
lfds711_freelist_cleanup( &fs, NULL );<br />
<br />
free( td );<br />
<br />
return( EXIT_SUCCESS );<br />
}<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Binary_Tree_(add-only,_unbalanced)&diff=1085r7.1.1:Binary Tree (add-only, unbalanced)2019-02-23T10:08:46Z<p>Admin: /* Benchmark Results and Analysis */</p>
<hr />
<div>{{DISPLAYTITLE:Binary Tree (add-only, unbalanced)}}<br />
==Source Files==<br />
└───liblfds711<br />
├───inc<br />
│ └───liblfds711<br />
│ lfds711_btree_addonly_unbalanced.h<br />
└───src<br />
└───lfds711_btree_addonly_unbalanced<br />
lfds711_btree_addonly_unbalanced_cleanup.c<br />
lfds711_btree_addonly_unbalanced_get.c<br />
lfds711_btree_addonly_unbalanced_init.c<br />
lfds711_btree_addonly_unbalanced_insert.c<br />
lfds711_btree_addonly_unbalanced_internal.h<br />
lfds711_btree_addonly_unbalanced_query.c<br />
<br />
==Enums==<br />
enum [[r7.1.1:enum lfds711_btree_au_absolute_position|lfds711_btree_au_absolute_position]];<br />
enum [[r7.1.1:enum lfds711_btree_au_existing_key|lfds711_btree_au_existing_key]];<br />
enum [[r7.1.1:enum lfds711_btree_au_insert_result|lfds711_btree_au_insert_result]];<br />
enum [[r7.1.1:enum lfds711_btree_au_query|lfds711_btree_au_query]];<br />
enum [[r7.1.1:enum lfds711_btree_au_relative_position|lfds711_btree_au_relative_position]];<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct lfds711_btree_au_element|lfds711_btree_au_element]];<br />
struct [[r7.1.1:struct lfds711_btree_au_state|lfds711_btree_au_state]];<br />
<br />
==Macros==<br />
#define [[r7.1.1:macro LFDS711_BTREE_AU_GET_KEY_FROM_ELEMENT|LFDS711_BTREE_AU_GET_KEY_FROM_ELEMENT]]( btree_au_element )<br />
#define [[r7.1.1:macro LFDS711_BTREE_AU_SET_KEY_IN_ELEMENT|LFDS711_BTREE_AU_SET_KEY_IN_ELEMENT]]( btree_au_element, new_key )<br />
<br />
#define [[r7.1.1:macro LFDS711_BTREE_AU_GET_VALUE_FROM_ELEMENT|LFDS711_BTREE_AU_GET_VALUE_FROM_ELEMENT]]( btree_au_element )<br />
#define [[r7.1.1:macro LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT|LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT]]( btree_au_element, new_value )<br />
<br />
#define [[r7.1.1:macro LFDS711_BTREE_AU_GET_USER_STATE_FROM_STATE|LFDS711_BTREE_AU_GET_USER_STATE_FROM_STATE]]( btree_au_state )<br />
<br />
==Prototypes==<br />
void [[r7.1.1:function lfds711_btree_au_init_valid_on_current_logical_core|lfds711_btree_au_init_valid_on_current_logical_core]]( struct lfds711_btree_au_state *baus,<br />
int (*key_compare_function)(void const *new_key, void const *existing_key),<br />
enum lfds711_btree_au_existing_key existing_key,<br />
void *user_state );<br />
<br />
void [[r7.1.1:function lfds711_btree_au_cleanup|lfds711_btree_au_cleanup]]( struct lfds711_btree_au_state *baus,<br />
void (*element_cleanup_callback)(struct lfds711_btree_au_state *baus, struct lfds711_btree_au_element *baue) );<br />
<br />
enum lfds711_btree_au_insert_result [[r7.1.1:function lfds711_btree_au_insert|lfds711_btree_au_insert]]( struct lfds711_btree_au_state *baus,<br />
struct lfds711_btree_au_element *baue,<br />
struct lfds711_btree_au_element **existing_baue );<br />
<br />
int [[r7.1.1:function lfds711_btree_au_get_by_key|lfds711_btree_au_get_by_key]]( struct lfds711_btree_au_state *baus, <br />
int (*key_compare_function)(void const *new_key, void const *existing_key),<br />
void *key,<br />
struct lfds711_btree_au_element **baue );<br />
<br />
int [[r7.1.1:function lfds711_btree_au_get_by_absolute_position_and_then_by_relative_position|lfds711_btree_au_get_by_absolute_position_and_then_by_relative_position]]( struct lfds711_btree_au_state *baus,<br />
struct lfds711_btree_au_element **baue,<br />
enum lfds711_btree_au_absolute_position absolute_position,<br />
enum lfds711_btree_au_relative_position relative_position );<br />
<br />
int [[r7.1.1:function lfds711_btree_au_get_by_absolute_position|lfds711_btree_au_get_by_absolute_position]]( struct lfds711_btree_au_state *baus,<br />
struct lfds711_btree_au_element **baue,<br />
enum lfds711_btree_au_absolute_position absolute_position );<br />
<br />
int [[r7.1.1:function lfds711_btree_au_get_by_relative_position|lfds711_btree_au_get_by_relative_position]]( struct lfds711_btree_au_element **baue,<br />
enum lfds711_btree_au_relative_position relative_position );<br />
<br />
void [[r7.1.1:function lfds711_btree_au_query|lfds711_btree_au_query]]( struct lfds711_btree_au_state *baus,<br />
enum lfds711_btree_au_query query_type,<br />
void *query_input,<br />
void *query_output );<br />
<br />
==Overview==<br />
This data structure implements an add-only, unbalanced btree. It supports any number of concurrent users, and internally implements exponential backoff to help deal with high load and so improve scalability (although being a btree it naturally acts to distribute memory access behaviour which helps scalability).<br />
<br />
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.<br />
<br />
General usage is that the user calls ''lfds711_btree_au_init_valid_on_current_logical_core'' to initialize a ''struct lfds711_btree_au_state'', and then calls ''lfds711_btree_au_link'' to add elements. A btree element provides the ability to store a key (used to place elements in the btree) and a value, both of which are of type ''void *'' and can either point to data, or can be used directly, as key comparason is performed by a user-provided callback and the value is not touched by the btree code.<br />
<br />
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)<br />
<br />
The key and value are get and set in elements by macros, such as ''LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT''. The key can only be set in elements before they are added to a tree. The value can be set at any time, in elements both inside and outside of the tree.<br />
<br />
The state and element structures are both public, present in the ''lfds711_btree_au.h'' header file, so that users can embed them in their own structures (and where necessary pass them to ''sizeof''). Expected use is that user structures which are to enter btrees contain within themselves a ''struct lfds711_btree_au_element'', where the user sets the key as necessary for the btree and the value to point to the user structure entering the btree. This approach permits zero run-time allocation of store and also ensures the btree element is normally in the same memory page as the user data it refers to.<br />
<br />
When initializing the btree, the caller specifies the behaviour of the btree when the attempt is mde to add a new element which has a key already present in the btree. The btree can be configured to either fail to add the element, or it can be configured to overwrite the value in the existing element with the value of the new element.<br />
<br />
Finally, when all is said and done, use ''lfds711_btree_au_cleanup'' to cleanup the tree. Once this function has returned, the user is then safe to deallocate all allocations.<br />
<br />
==Lock-free Specific Behaviour==<br />
The state initialization function, ''lfds711_btree_au_init_valid_on_current_logical_core'', as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro ''[[r7.1.1:define LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'', which will do that which its name suggests.<br />
<br />
Once a btree element structure has been linked to the btree, it cannot be deallocated (''free'', or stack allocation lifetimes ending due to say a thread ending, etc) until ''lfds711_btree_au_cleanup'' has returned. Elements cannot be removed from the tree, or moved within the tree. Their value however can be changed at any time.<br />
<br />
The SET macro for the key in an element can only be correctly used on elements which are outside of a btree. The SET macro for the value in an element can be used at any time, on any element. By correctly is it meant to say that the GET macros will actually read the data written by the SET macros, and not some other data. I don't have to tell you how much chaos will ensure if different logical cores are reading different keys for the same element...<br />
<br />
If shared memory is used for allocations, the virtual addresses must be the same across different processes.<br />
<br />
==Benchmark Results and Analysis==<br />
<html><br />
<table border="1" cellpadding="8"><br />
<tr><br />
<th class="header" colspan="4">btree (add-only, unbalanced)</th><br />
<tr><br />
<br />
<tr><br />
<th class="header">ARM32</th><br />
<th class="header">MIPS32</th><br />
<th class="header" colspan="2">x64</th><br />
</tr><br />
<br />
<tr><br />
<th class="header">Raspberry Pi 2 Model B</th><br />
<th class="header">Ci20</th><br />
<th class="header">AWS dedicated VM</th><br />
<th class="header">Core i5</th><br />
</tr><br />
<br />
<tr><br />
<td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Raspberry Pi 2 Model B (ARM32).1200x1800.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Raspberry Pi 2 Model B (ARM32).300x450.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Ci20 (MIPS32).800x1200.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_smp_Ci20 (MIPS32).300x450.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Amazon VM dedicated c4.4xlarge.4800x5400.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Amazon VM dedicated c4.4xlarge.300x337.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Core i5 (x64).1200x1800.png"><img src="/pages/images/liblfds710_btree_au_readn_then_writen_numa_Core i5 (x64).300x450.png"/></a></td><br />
</tr><br />
</table><br />
</html><br />
<br />
The benchmark consists of a btree state which has 1024 elements per thread, where each element has a random integer key, where the benchmark loops, performing one read and then one write operation, where the key used for the read and the key used for the write are randomly selected from the pool of keys. The pthread rwlock uses a read lock for reading, and a write lock for writing. The locking versions of the btree have one lock for the entire btree, and so only one thread accesses the btree at a time (except in the case of rwlocks, where naturally any number of readers can access the tree at any time).<br />
<br />
This beanchmark is in fact flawed. As the number of elements in the btree increases the mean number of steps through the btree to find an element increases. This means as the core count rises, the work being done by a single operation is increasing.<br />
<br />
The btree data structure benefits massively from a lock-free implementation. In locking implementations there is typically one lock per tree, so the entire tree is single-threaded. With rwlocks, there can be any number of readers, but only a single writer, and the rwlock itself is a point of contention. With lock-free, any number of thread can execute concurrently, for read and for write, and the btree, by its distributed nature, inherently lacks particular memory locations which experience contention. End result is excellent scalability, as demonstrated in the 16 core AWS dedicated VM gnuplot.<br />
<br />
Version 7.0.0 was inefficient in its use of cache lines. This actually led on the Raspberry Pi 2 Model B to the btree performing at about one tenth of the speed of the locking implementations! fixing this implementation error returned the btree to its usual place, about three times faster (on up to four cores).<br />
<br />
The autotuning exponential backoff hardly makes any difference to btree performance. Where the elements are spread out in a probabalistically balanced tree (the keys are random), threads are issuing highly dispersed memory accesses and rarely collide.<br />
<br />
==White Paper==<br />
There is no white paper for this data structure; it is native to ''liblfds''.<br />
<br />
==License==<br />
Standard ''liblfds'' license - there is no license. You are free to use this code in any way. Go forth and create wealth!<br />
<br />
If however for legal reasons a licence is required, the license of your choice will be granted, and license for convenience is hereby granted up front for a range of popular licenses : the MIT license, the BSD license, the Apache license, the GPL and LPGL (all versions thereof) and the Creative Commons licenses (all of them). Additionally, this library (which is to say, the source code, build files, documentation, everything) is placed in the public domain.<br />
<br />
==Example==<br />
#include <stdio.h><br />
#include <stdlib.h><br />
#include "liblfds711.h"<br />
<br />
struct test_data<br />
{<br />
int long long unsigned<br />
unique_id;<br />
<br />
char<br />
payload[64];<br />
<br />
struct lfds711_btree_au_element<br />
buae;<br />
};<br />
<br />
int key_compare_function( void const *new_key, void const *existing_key )<br />
{<br />
int<br />
cr = 0;<br />
<br />
int long long unsigned<br />
*new_key = (int long long unsigned *) new_key,<br />
*existing_key = (int long long unsigned *) existing_key;<br />
<br />
if( *new_key > *existing_key )<br />
cr = 1;<br />
<br />
if( *new_key < *existing_key )<br />
cr = -1;<br />
<br />
return( cr );<br />
}<br />
<br />
int main()<br />
{<br />
enum lfds711_btree_au_insert_result<br />
bauir;<br />
<br />
int long long unsigned<br />
loop;<br />
<br />
struct lfds711_btree_au_element<br />
*buae = NULL;<br />
<br />
struct lfds711_btree_au_state<br />
baus;<br />
<br />
struct test_data<br />
*td,<br />
*temp_td;<br />
<br />
lfds711_btree_au_init_valid_on_current_logical_core( &baus, key_compare_function, LFDS711_BTREE_AU_EXISTING_KEY_FAIL, NULL );<br />
<br />
// TRD : allocate ten test elements, populate with dummy data and link to tree<br />
td = malloc( sizeof(struct test_data) * 10 );<br />
<br />
for( loop = 0 ; loop < 10 ; loop++ )<br />
{<br />
td[loop].unique_id = loop;<br />
sprintf( td[loop].payload, "the unique id is %llu", loop );<br />
<br />
LFDS711_BTREE_AU_SET_KEY_IN_ELEMENT( td[loop].baue, &td[loop].unique_id );<br />
LFDS711_BTREE_AU_SET_VALUE_IN_ELEMENT( td[loop].baue, &td[loop] );<br />
<br />
bauir = lfds711_btree_au_insert( baus, &td[loop].baue, NULL );<br />
<br />
if( bauir != LFDS711_BTREE_AU_INSERT_RESULT_SUCCESS )<br />
printf( "Well, bugger! so much for quality control\n" );<br />
}<br />
<br />
// TRD : now in-order walk the tree<br />
while( lfds711_btree_au_get_by_absolute_position_and_then_by_relative_position(baus, &baue, LFDS711_BTREE_AU_SMALLEST_IN_TREE, LFDS711_BTREE_AU_INORDER_WALK_FROM_SMALLEST_TO_LARGEST) )<br />
{<br />
temp_td = LFDS711_BTREE_AU_GET_VALUE_FROM_ELEMENT( *baue );<br />
printf( "element %llu has value \"%s\"\n", temp_td->unique_id, temp_id->payload );<br />
}<br />
<br />
lfds711_btree_au_cleanup( &baus, NULL );<br />
<br />
free( td );<br />
<br />
return( EXIT_SUCCESS );<br />
}<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Queue_(unbounded,_many_producer,_many_consumer)&diff=1176r7.1.1:Queue (unbounded, many producer, many consumer)2019-02-23T10:06:30Z<p>Admin: /* Benchmark Results and Analysis */</p>
<hr />
<div>{{DISPLAYTITLE:Queue (unbounded, many producer, many consumer)}}<br />
==Source Files==<br />
└───liblfds711<br />
├───inc<br />
│ └───liblfds711<br />
│ lfds711_queue_umm.h<br />
└───src<br />
└───lfds711_queue<br />
lfds711_queue_umm_cleanup.c<br />
lfds711_queue_umm_dequeue.c<br />
lfds711_queue_umm_enqueue.c<br />
lfds711_queue_umm_init.c<br />
lfds711_queue_umm_internal.h<br />
lfds711_queue_umm_query.c<br />
<br />
==Enums==<br />
enum [[r7.1.1:enum lfds711_queue_umm_query|lfds711_queue_umm_query]];<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct lfds711_queue_umm_element|lfds711_queue_umm_element]];<br />
struct [[r7.1.1:struct lfds711_queue_umm_state|lfds711_queue_umm_state]];<br />
<br />
==Macros==<br />
#define [[r7.1.1:macro LFDS711_QUEUE_UMM_GET_KEY_FROM_ELEMENT|LFDS711_QUEUE_UMM_GET_KEY_FROM_ELEMENT]]( queue_umm_element )<br />
#define [[r7.1.1:macro LFDS711_QUEUE_UMM_SET_KEY_IN_ELEMENT|LFDS711_QUEUE_UMM_SET_KEY_IN_ELEMENT]]( queue_umm_element, new_key )<br />
<br />
#define [[r7.1.1:macro LFDS711_QUEUE_UMM_GET_VALUE_FROM_ELEMENT|LFDS711_QUEUE_UMM_GET_VALUE_FROM_ELEMENT]]( queue_umm_element )<br />
#define [[r7.1.1:macro LFDS711_QUEUE_UMM_SET_VALUE_IN_ELEMENT|LFDS711_QUEUE_UMM_SET_VALUE_IN_ELEMENT]]( queue_umm_element, new_value )<br />
<br />
#define [[r7.1.1:macro LFDS711_QUEUE_UMM_GET_USER_STATE_FROM_STATE|LFDS711_QUEUE_UMM_GET_USER_STATE_FROM_STATE]]( queue_umm_state )<br />
<br />
==Prototypes==<br />
void [[r7.1.1:function lfds711_queue_umm_init_valid_on_current_logical_core|lfds711_queue_init_valid_on_current_logical_core]]( struct lfds711_queue_umm_state *qumms,<br />
struct lfds711_queue_umm_element *qumme_dummy,<br />
void *user_state );<br />
<br />
void [[r7.1.1:function lfds711_queue_umm_cleanup|lfds711_queue_umm_cleanup]]( struct lfds711_queue_umm_state *qumms,<br />
void (*element_dequeue_callback)(struct lfds711_queue_umm_state *qumms,<br />
struct lfds711_queue_umm_element *qumme,<br />
enum lfds711_liblfds_misc_flag dummy_element_flag) );<br />
<br />
void [[r7.1.1:function lfds711_queue_umm_enqueue|lfds711_queue_umm_enqueue]]( struct lfds711_queue_umm_state *qumms,<br />
struct lfds711_queue_umm_element *qumme );<br />
<br />
int [[r7.1.1:function lfds711_queue_umm_dequeue|lfds711_queue_umm_dequeue]]( struct lfds711_queue_umm_state *qumms,<br />
struct lfds711_queue_umm_element **qumme );<br />
<br />
void [[r7.1.1:function lfds711_queue_umm_query|lfds711_queue_umm_query]]( struct lfds711_queue_umm_state *qumms,<br />
enum lfds711_queue_umm_query query_type,<br />
void *query_input,<br />
void *query_output );<br />
<br />
==Overview==<br />
This data structure implements an unbounded, many-producer, many-consumer queue and internally implements exponential backoff to help deal with high load and so improve scalability.<br />
<br />
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.<br />
<br />
General usage is that the user calls ''lfds711_queue_umm_init_valid_on_current_logical_core'' to initialize a ''struct lfds711_queue_umm_state'', and then calls ''lfds711_queue_umm_enqueue'' and ''lfds711_queue_umm_dequeue'' to enqueue and dequeue ''struct lfds711_queue_umm_element''s.<br />
<br />
A queue element provides the ability to store a key and a value, both of which are of type ''void *''. The key is not used in any way by the queue (and of course the value is neither), rather, it is available as a convenience for the user, for situations where data is being transferred between different types of data structures, where some of these data structures do support a meaningful key. The key and value are get and set by macros, such as ''LFDS711_QUEUE_UMM_SET_VALUE_IN_ELEMENT''. The SET macros can only be used when an element is outside of the queue. (Things may seem to work even if they are used on elements which are in the queue, but it's a matter of pure chance).<br />
<br />
(See the section below, on lock-free specific behaviour, for an explanation of the unusual init function name.)<br />
<br />
The state and element structures are both public, present in the ''lfds711_queue_umm.h'' header file, which is in line with the style for the rest of the library. Using this queue however differs somewhat from the usual expected method whereby each user structure contains an element structure (freelist element, btree element, etc) of the data structure it is to be placed in, because the queue always contains a dummy element (which is why there is a queue element argument to the init function; it is for the dummy element).<br />
<br />
If we imagine the queue immediately after init, but before any enqueue, we see the queue contains a single dummy element, which contains no data. If we try to dequeue, dequeue fails (the queue knows that only the dummy is present). If we enqueue, the queue then contains the dummy element (with no data) and the newly enqueued real element (with data). Now if we dequeue, we are given the dummy element, but is has been populated with the data from the real element, and the real element (which now lacks data) has become the dummy element.<br />
<br />
As such, the usual expected method of putting queue element structures in the user structures which are being enqueued does not quite work as we expect because the queue element which comes back to us is *not* the queue element in the user structure which has been returned to us. We ''can'' immediately re-use, or place on a freelist, the queue element which is returned to us - this is safe, it has left the queue - but we ''cannot'' use the queue element which is in the user structure, because this is now the dummy element in the queue - it is still in the queue.<br />
<br />
This also means we lose locality between the queue element and the user structure its in, which is unfortunate.<br />
<br />
==Lock-free Specific Behaviour==<br />
The state initialization function, ''lfds711_queue_umm_init_valid_on_current_logical_core'', as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro ''[[r7.1.1:define LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'', which will do that which its name suggests.<br />
<br />
Once a queue element structure has been enqueued to the queue, it cannot be deallocated (free, or stack allocation lifetimes ending due to say a thread ending, etc) until function ''lfds711_queue_umm_cleanup'' has returned. Typical usage is to return dequeued queue elements to a freelist. <br />
<br />
The SET macros (for setting key and value, in stack elements) can only be correctly used on elements which are outside of a queue, and the GET macros, if called by a thread on a logical core other than the logical core of the thread which called the SET macros, can only be correctly used on a queue element which has been enqueued to the queue and then dequeued.<br />
<br />
By correctly is it meant to say that the GET macros will actually read the data written by the SET macros, and not some other data.<br />
<br />
The queue should be regarded as a safe communication channel between threads. Any queue element which has a key and/or value set, and then is enqueued to a queue, will allow any thread which dequeues that element to correctly read the key and/or value (and by this is it meant to say not just the void pointer of the key and value, but also whatever they point to). This is the only guarantee. Any reads or writes of key and/or value, or what they point to, which occur outside of this enqueuing and dequeuing pair are not guaranteed to be correct; the data written may never be seen by other threads.<br />
<br />
==Benchmark Results and Analysis==<br />
<html><br />
<table border="1" cellpadding="8"><br />
<tr><br />
<th class="header" colspan="3">queue (unbounded, many produces, many consumer)</th><br />
<tr><br />
<br />
<tr><br />
<th class="header">ARM32</th><br />
<th class="header" colspan="2">x64</th><br />
</tr><br />
<br />
<tr><br />
<th class="header">Raspberry Pi 2 Model B</th><br />
<th class="header">AWS dedicated VM</th><br />
<th class="header">Core i5</th><br />
</tr><br />
<br />
<tr><br />
<td><a href="/pages/images/liblfds710_queue_umm_enqueue1_then_dequeue1_smp_Raspberry Pi 2 Model B (ARM32).1200x1800.png"><img src="/pages/images/liblfds710_queue_umm_enqueue1_then_dequeue1_smp_Raspberry Pi 2 Model B (ARM32).300x450.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_queue_umm_enqueue1_then_dequeue1_numa_Amazon VM dedicated c4.4xlarge.4800x5400.png"><img src="/pages/images/liblfds710_queue_umm_enqueue1_then_dequeue1_numa_Amazon VM dedicated c4.4xlarge.300x337.png"/></a></td><br />
<td><a href="/pages/images/liblfds710_queue_umm_enqueue1_then_dequeue1_numa_Core i5 (x64).1200x1800.png"><img src="/pages/images/liblfds710_queue_umm_enqueue1_then_dequeue1_numa_Core i5 (x64).300x450.png"/></td></a></td><br />
</tr><br />
</table><br />
</html><br />
<br />
One benchmark operation is an enqueue-dequeue pair. The enqueue function requires two DWCAS operations, and the dequeue one. The enqueue takes about twice as long as the dequeue.<br />
<br />
Quite a bit of work went into improving queue performance in 7.1.1. The basic problem was that in 7.0.0, the static exponential backoff value was much, much too low. The autotuning exponential backoff in 7.1.1 addresses this issue. There was also some improvement (or fixing of mistakes :-) with regard to cache-line usage in the queue element. The upshot is a large (3x) improvement on x64. However, for reasons yet unexplored, the ARM32 version of this data structure performs appallingly; this was not noticed during the performance improvement work, due to too-many-columns-in-a-row-blindness.<br />
<br />
==White Paper==<br />
This data structure impliments a modified version of [[Michael,_Scott_-_Simple,_Fast,_and_Practical_Non-Blocking_and_Blocking_Concurrent_Queue_Algorithms|Michael and Scott]]'s queue.<br />
<br />
Note however the word modified. There are two modifications.<br />
<br />
The first relates to an issue identified by Bryan Kerr, which can be found in this [http://polyglotplayground.com/2015/04/30/Problem-with-Michael-Scott-Lock-Free-Queue blog post]. In short, where the counters are uninitialized, and where elements carry a counter with them, it is possible when those uninitialized values happen to have the same starting values and when moving elements between multiple queues to end up when enqueuing an element to Queue A, to actually end up enqueing to Queue B - essentially, you come to enqueue the element to Queue A, and then just before that occurs, everything is dequeued from Queue A and placed into Queue B. To the atomic operation about to perform the enqueue, everything looks as it should!<br />
<br />
The solution adopted has been to endow each queue instance with an ABA counter, which is initialized by a high quality PRNG, and which then is used with atomic add to provide the initial ABA value for an element when it is enqueued.<br />
<br />
The second modification is more questionable. It is an issue which appears to me to exist - I am sure I must be wrong, but cannot for the life of me see that it does ''not'' exist, and so until someone can explain to me what has failed to be understood, I have modified the code to address the issue.<br />
<br />
The issue is discussed in this [http://www.liblfds.org/wordpress/?p=227 blog post], on the liblfds blog.<br />
<br />
Essentially, it seems there may be a typo or a bug in the psudo-code in the paper, the upshot of which is a race condition which makes the call to ''free'' in the dequeue unsafe. It is easily fixed - so easily, and given the seeming typo in the enqueue code vs enqueue comment on line E4, that is seems to me that this may be a typographic error rather than an actual design flaw. However, this does not explain the matching bug in the dequeue code, which suffers no such typo.<br />
<br />
The fix is very, very simple and does not invalidate or in any way significantly change the code or the function of the code - see the blog post for a description.<br />
<br />
==License==<br />
Unclear. The design comes from the 1998 white paper by Michael and Scott. No patent is known, and the queue is widely used - Java uses it, for example, for ConcurrentLinkedQueue.<br />
<br />
==Example==<br />
#include <stdio.h><br />
#include <stdlib.h><br />
#include "liblfds711.h"<br />
<br />
struct test_data<br />
{<br />
struct lfds711_queue_element<br />
qe;<br />
<br />
int<br />
number;<br />
};<br />
<br />
int main()<br />
{<br />
int long long unsigned<br />
loop;<br />
<br />
struct lfds711_queue_element<br />
*qe,<br />
qe_dummy;<br />
<br />
struct lfds711_queue_state<br />
qs;<br />
<br />
struct test_data<br />
*td,<br />
*td_temp;<br />
<br />
lfds711_queue_umm_init_valid_on_current_logical_core( &qs, &qe_dummy, NULL );<br />
<br />
td = malloc( sizeof(struct test_data) * 10 );<br />
<br />
// TRD : queue ten elements<br />
for( loop = 0 ; loop < 10 ; loop++ )<br />
{<br />
// TRD : we enqueue the numbers 0 to 9<br />
td[loop].number = (int) loop;<br />
LFDS711_QUEUE_UMM_SET_VALUE_IN_ELEMENT( td[loop].qe, &td[loop] );<br />
lfds711_queue_umm_enqueue( &qs, &td[loop].qe );<br />
} <br />
<br />
// TRD : dequeue until the queue is empty<br />
while( lfds711_queue_umm_dequeue(&qs, &qe) )<br />
{<br />
temp_td = LFDS711_QUEUE_UMM_GET_VALUE_FROM_ELEMENT( *qe );<br />
<br />
// TRD : we dequeue the numbers 0 to 9<br />
printf( "number = %d\n", temp_td->number );<br />
}<br />
<br />
lfds711_queue_cleanup( &qs, NULL );<br />
<br />
free( td );<br />
<br />
return( EXIT_SUCCESS );<br />
}<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(liblfds)&diff=1221r7.1.1:Usage Guide (liblfds)2019-02-23T09:44:02Z<p>Admin: /* Exclusive Reservation Granule (ARM, POWERPC) */</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (liblfds)}}<br />
==Introduction==<br />
This page describes how to use the ''liblfds'' library, and then covers the novel and pecuilar issues which originate in the lock-free nature of the data structures in the library.<br />
<br />
Where-ever possible such issues have been hidden from the user, but there are some which simply cannot be hidden and as such the user has be aware of them.<br />
<br />
==Library Initialization and Cleanup==<br />
No library initialization or cleanup are required.<br />
<br />
==Usage==<br />
To use ''liblfds'', include the header file ''liblfds711.h'' and link as normal to the library in your build.<br />
<br />
==Novel and Peculiar Issues==<br />
<br />
===Memory Allocation===<br />
The ''liblfds'' library performs no memory allocation or deallocation. Accordindly, there are no ''new'' and ''delete'' functions, but rather ''init'' and ''cleanup''.<br />
<br />
The user is responsible for all allocation and all deallocation. As such, allocations can be from the heap or from the stack, or from user-mode or from the kernel; the library itself just uses what you give it, and doesn't know about and so does not differentiate between virtual or physical addresses. Allocations can be shared memory, but note the virtual memory ranges must be the same in all processes - ''liblfds'' uses addresses directly, rather than using offsets. Being able to used shared memory is particularly important for Windows, which lacks a high performance cross-process lock; the data structures in ''liblfds'' when used with shared memory provide a process and thread safe cross-process communication channel (but they do not provide sychronization, so the reader cannot be signalled, by the library, as to ''when'' to read).<br />
<br />
===Memory Deallocation===<br />
Any data structure element which has at any time been present in a lock-free data structure can never be passed to ''free'' until the data structure in question is no longer in use and has had its ''cleanup'' function called.<br />
<br />
As such, typical usage is for data structure elements to be supplied from (and returned to) a lock-free freelist.<br />
<br />
There is a single exception to this, which is the unbounded, many producer, many consumer queue. It ''is'' safe to deallocate elements which have emerged from this data structure.<br />
<br />
===Data Structure Initialization===<br />
Passing a data structure state to its ''init'' function initializes that state but that initialization is and is only valid for the logical core upon which it occurs.<br />
<br />
The macro ''[[r7.1.1:LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'' is used to make the initialization valid on other logical cores and it will make the initialization valid upon and only upon the logical core which calls the macro.<br />
<br />
Expected use is that a thread will initialize a data structure, pass a pointer to its state to other threads, all of whom will then call ''LFDS711_LIBLFDS_MAKE_USABLE_TO_CURRENT_LOGICAL_CORE_INITS_PERFORMED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE''.<br />
<br />
===The Standard Library and ''lfds711_pal_uint_t''===<br />
The ''liblfds'' library is intended for both 32 and 64 bit platforms. As such, there is a need for an unsigned type which is 32 bits long on a 32 bit platform, and 64 bits long on a 64 bit platform - but remember that the Standard Library is not used, so we can't turn to it for a solution (and also that for C89, there wasn't really such a type anyway - ''size_t'' did in fact behave in this way on Windows and Linux, but semantically ''size_t'' means something else, and so it is only co-incidentally behaving in this way).<br />
<br />
As such, ''liblfds'' in the platform abstraction layer typedefs ''liblfds711_pal_uint_t'' (and a signed equivelent, ''lfds711_pal_int_t''). This is set to be an unsigned integer which is the natural length for the platform, i.e. the length of the processor register, 32 bits on a 32 bit CPU and 64 bits on a 64 bit CPU.<br />
<br />
===Exclusive Reservation Granule (ARM, POWERPC)===<br />
On ARM and POWERPC there is a define in the ''liblfds'' header file ''lfds711_porting_abstraction_layer_processor.h'', ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' which '''SHOULD BE SET CORRECTLY''', as the value in the header file is necessrily the worse-case (longest) value, which in the case of ARM is 2048 bytes - which has the effect ot making many of the data structure structures '''HUGE'''.<br />
<br />
There are two approaches in hardware, in processors, to implementing atomic operations. The first approach is ''compare-and-swap'' (CAS), the second approach is ''load-linked/store-conditional'' (LL/SC).<br />
<br />
Atomic operation involve writing a variable to memory. CAS implements atomicity by locking the cache-line containing the variable. LL/SC implements atomicity by loading the variable into a register, where anything can be done with it, but watching the memory location it comes from until the variable is stored again; if in the meantime another write occurred to that memory location, the store aborts.<br />
<br />
The granularity of the 'watching' varies a great deal. On some platforms, such as MIPS, only one 'watcher' is available per logical processor. On some platforms, such as ARM and POWERPC, memory is conceptually divided up into pages (which are known as "Exclusive Reservation Granules", "ERG" for short) and if a write occurs to the page which contains the target varible, then the store fails.<br />
<br />
On ARM the Exclusive Reservation Granule range in size from 8 to 2048 bytes (always a power of two, though - 8, 16, 32, 64, etc), depending on implementation.<br />
<br />
Obviously, for ''liblfds'' to alway work, the header file has to use the 2048 byte value - but where in all the ''liblfds'' structures variables which are the target of atomic operations have to be in their own granule, then naturally the larger the granule size, the larger the structure. Some structures have a number of variables which are the target of atomic operations, and so those structures can become ''very'' large.<br />
<br />
This then leads to the question of finding out or determining the ERG length.<br />
<br />
The ERG length can be obtained from the processor, it's stored in a register, but on ARM this is only possible when the processor is in supervisor mode; so ''liblfds'' cannot access this information. The documentation for any given system should, somewhere deeply buried, indicate the ERG length.<br />
<br />
There is however another way. The ''libtest'' library offers a function ''libtest_misc_determine_erg'' which attempts to empircally determine the ERG length, by running on one logical core an LL operation, then on every other logical core touching memory just inside the largest possible ERG size and then trying the SC operation, repeating this with progressively smaller ERG sizes, until the operation fails, which indicates the ERG size.<br />
<br />
This function can only work on systems which have more than one ''physical'' processor (multiple logical processors in one physical processor is not enough). This is because ARM implements per-processor 'local' watchers, which are typically much more relaxed than the 'global' (system-wide, i.e. multiple physical processors) watchers, which normally not throw an error even if a write occurs inside the ERG - i.e. with the local watcher only, it's not possible to make the LL/SC fail, so the code cannot work out the length.<br />
<br />
The ''test'' binary has an argument, "-e", which runs a test using this function, like so;<br />
<br />
test -e<br />
<br />
The output will look like this (plus a bunch of fixed explanatory text);<br />
<br />
ERG length in bytes : Number successful LL/SC ops<br />
=================================================<br />
4 bytes : 0<br />
8 bytes : 0<br />
16 bytes : 0<br />
32 bytes : 0<br />
64 bytes : 1024<br />
128 bytes : 1023<br />
256 bytes : 1023<br />
512 bytes : 1024<br />
1024 bytes : 1024<br />
2048 bytes : 12<br />
<br />
The ERG size is on the left, the number of successful LL/SC ops on the right. Each size is tested 1024 times. The smallest size with 1024, or almost 1024, operations, is the ERG size. (LL/SC ops can fail naturally due to system activity, so it's expected that sometimes one or two LL/SC operations will fail by themselves and so the total value will be slightly slower).<br />
<br />
We see here the ERG sie for this platform is 64 bytes, which is correct - this is a Cortex A7 in a Raspberry Pi 2 Model B.<br />
<br />
(That there are 12 successful ops for the 2048 byte size is not in fact understood. There is a 4 byte ERG test as a sanity check, because if it passes, then it is clear the test is not working properly).<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Porting_Guide_(libbenchmark)&diff=1168r7.1.1:Porting Guide (libbenchmark)2018-04-01T15:59:07Z<p>Admin: /* The Porting Abstraction Layer */</p>
<hr />
<div>{{DISPLAYTITLE:Porting Guide (libbenchmark)}}<br />
==Introduction==<br />
To permit ''libbenchmark'' to work on a range of platforms a porting abstraction layer has been written. Porting simply involves implementing the porting abstraction layer; the library will then compile and work. Implementation involves providing values to a small set defines, macros and typedefs and implementing one or two functions.<br />
<br />
==The Porting Abstraction Layer==<br />
The porting abstraction layer consists of one header and two C files, thus;<br />
<br />
└───test_and_benchmark<br />
└───libbenchmark<br />
├───inc<br />
│ └───libbenchmark<br />
│ └───libbenchmark_porting_abstraction_layer_operating_system.h<br />
└───src<br />
└───libbenchmark_porting_abstraction_layer<br />
├───libbenchmark_porting_abstraction_layer_populate_topology.c<br />
└───libbenchmark_porting_abstraction_layer_print_string.c<br />
<br />
Accordingly, to add a new platform, introduce a new #ifdef, which matches the appropriate compiler defined macros for your platform.<br />
<br />
===''libshared_porting_abstraction_layer_operating_system.h''===<br />
<br />
#define [[r7.1.1:define LIBBENCHMARK_PAL_OS_STRING|LIBBENCHMARK_PAL_OS_STRING]]<br />
#define [[r7.1.1:macro LIBBENCHMARK_PAL_TIME_UNITS_PER_SECOND|LIBBENCHMARK_PAL_TIME_UNITS_PER_SECOND]]( pointer_to_time_units_per_second )<br />
#define [[r7.1.1:macro LIBBENCHMARK_PAL_GET_HIGHRES_TIME|LIBBENCHMARK_PAL_GET_HIGHRES_TIME]]( pointer_to_time )<br />
<br />
Additionally, in this file, include any needed OS provided header files.<br />
<br />
===''libbenchmark_porting_abstraction_layer_populate_topology.c''===<br />
<br />
int [[r7.1.1:function libbenchmark_pal_populate_topology|libbenchmark_pal_populate_topology]]( struct libbenchmark_topology_state *ts,<br />
struct libshared_memory_state *ms );<br />
<br />
===''libbenchmark_porting_abstraction_layer_print_string.c''===<br />
<br />
void [[r7.1.1:function libbenchmark_pal_print_string|libbenchmark_pal_print_string]]( char const * const string );<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (benchmarking)|Porting Guide (benchmarking)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Porting_Guide_(libtest)&diff=1171r7.1.1:Porting Guide (libtest)2018-04-01T15:56:58Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Porting Guide (libtest)}}<br />
==Introduction==<br />
To permit ''libtest'' to work on a range of platforms a porting abstraction layer has been written. Porting simply involves implementing the porting abstraction layer; the library will then compile and work. Implementation involves providing values to a small set defines, macros and typedefs and implementing one or two functions.<br />
<br />
==The Porting Abstraction Layer==<br />
The porting abstraction layer consists of three header files and three C files, thus;<br />
<br />
└───test_and_benchmark<br />
└───libtest<br />
├───inc<br />
│ └───libtest<br />
│ ├───libtest_porting_abstraction_layer_compiler.h<br />
│ └───libtest_porting_abstraction_layer_operating_system.h<br />
└───src<br />
└───libtest_porting_abstraction_layer<br />
├───libtest_porting_abstraction_layer_free.c<br />
├───libtest_porting_abstraction_layer_get_full_logical_processor_set.c<br />
└───libtest_porting_abstraction_layer_malloc.c<br />
<br />
Each header file uses #ifdefs and compiler defined macros to select the appropriate porting abstraction layer implementation for the local platform.<br />
<br />
Accordingly, to add a new platform, introduce a new #ifdef, which matches the appropriate compiler defined macros for your platform.<br />
<br />
The abstraction layer for ''libtest'' seems much larger than it is. Most of it is optional or invariant. The only actually vital function is ''libtest_pal_get_full_logical_processor_set''.<br />
<br />
===''libtest_porting_abstraction_layer_compiler.h''===<br />
<br />
#define [[r7.1.1:define LIBTEST_PAL_LOAD_LINKED|LIBTEST_PAL_LOAD_LINKED]]( destination, source )<br />
#define [[r7.1.1:define LIBTEST_PAL_STORE_CONDITIONAL|LIBTEST_PAL_STORE_CONDITIONAL]]( destination, source, stored_flag )<br />
<br />
===''libtest_porting_abstraction_layer_operating_system.h''===<br />
<br />
#define [[r7.1.1:define LIBTEST_PAL_OS_STRING|LIBTEST_PAL_OS_STRING]]<br />
<br />
Additionally, in this file, include any needed OS provided header files. Currently, ''stdlib.h'' and ''time.h'' are required and because of this, ''libtest'' requires a hosted implementation. This will be fixed in an upcoming release.<br />
<br />
===''libtest_porting_abstraction_layer_free.c''===<br />
<br />
void [[r7.1.1:function libtest_pal_free|libtest_pal_free]]( void *memory );<br />
<br />
===''libtest_porting_abstraction_layer_get_full_logical_processor_set.c''===<br />
<br />
void [[r7.1.1:function libtest_pal_get_full_logical_processor_set|libtest_pal_get_full_logical_processor_set]]( struct lfds711_list_asu_state *lasus,<br />
struct libshared_memory_state *ms );<br />
<br />
===''libtest_porting_abstraction_layer_malloc.c''===<br />
<br />
void *[[r7.1.1:function libtest_pal_malloc|libtest_pal_malloc]]( size_t size );<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (testing)|Porting Guide (testing)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Porting_Guide_(libshared)&diff=1170r7.1.1:Porting Guide (libshared)2018-04-01T15:53:20Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Porting Guide (libshared)}}<br />
==Introduction==<br />
To permit ''libshared'' to work on a range of platforms a porting abstraction layer has been written. Porting simply involves implementing the porting abstraction layer; the library will then compile and work. Implementation involves providing values to a small set defines, macros and typedefs and implementing one or two functions.<br />
<br />
==The Porting Abstraction Layer==<br />
The porting abstraction layer consists of one header file and two C files, thus;<br />
<br />
└───test_and_benchmark<br />
└───libshared<br />
├───inc<br />
│ └───libshared<br />
│ └───libshared_porting_abstraction_layer_operating_system.h<br />
└───src<br />
└───libshared_porting_abstraction_layer<br />
├───lfds711_porting_abstraction_layer_thread_start.c<br />
└───lfds711_porting_abstraction_layer_thread_wait.c<br />
<br />
Each header file uses #ifdefs and compiler defined macros to select the appropriate porting abstraction layer implementation for the local platform.<br />
<br />
Accordingly, to add a new platform, introduce a new #ifdef, which matches the appropriate compiler defined macros for your platform.<br />
<br />
===''libshared_porting_abstraction_layer_operating_system.h''===<br />
<br />
#define [[r7.1.1:define LIBSHARED_PAL_OS_STRING|LIBSHARED_PAL_OS_STRING]]<br />
<br />
#define [[r7.1.1:define LIBSHARED_PAL_THREAD_CALLING_CONVENTION|LIBSHARED_PAL_THREAD_CALLING_CONVENTION]]<br />
#define [[r7.1.1:define LIBSHARED_PAL_THREAD_RETURN_TYPE|LIBSHARED_PAL_THREAD_RETURN_TYPE]]<br />
#define [[r7.1.1:macro LIBSHARED_PAL_THREAD_RETURN_CAST|LIBSHARED_PAL_THREAD_RETURN_CAST]]( return_value )<br />
<br />
typedef [type] [[r7.1.1:typedef libshared_pal_thread_handle_t|libshared_pal_thread_handle_t]];<br />
typedef [type] [[r7.1.1:typedef libshared_pal_thread_return_t|libshared_pal_thread_return_t]];<br />
<br />
Additionally, in this file, include any needed OS provided header files.<br />
<br />
===''libshared_porting_abstraction_layer_thread_start.c''===<br />
<br />
int [[r7.1.1:function libshared_pal_thread_start|libshared_pal_thread_start]]( libshared_pal_thread_handle_t *thread_handle,<br />
struct libshared_pal_thread_info *pti )<br />
<br />
===''libshared_porting_abstraction_layer_thread_wait.c''===<br />
<br />
void [[r7.1.1:function libshared_pal_thread_wait|libshared_pal_thread_wait]]( libshared_pal_thread_handle_t thread_handle )<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (benchmarking)|Porting Guide (benchmarking)]]<br />
* [[r7.1.1:Porting Guide (testing)|Porting Guide (testing)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Queue_(bounded,_many_producer,_many_consumer)&diff=1174r7.1.1:Queue (bounded, many producer, many consumer)2018-02-21T20:40:51Z<p>Admin: /* Prototypes */</p>
<hr />
<div>{{DISPLAYTITLE:Queue (bounded, many producer, many consumer)}}<br />
==Source Files==<br />
└───liblfds711<br />
├───inc<br />
│ └───liblfds711<br />
│ lfds711_queue_bmm.h<br />
└───src<br />
└───lfds711_queue<br />
lfds711_queue_bmm_cleanup.c<br />
lfds711_queue_bmm_dequeue.c<br />
lfds711_queue_bmm_enqueue.c<br />
lfds711_queue_bmm_init.c<br />
lfds711_queue_bmm_internal.h<br />
lfds711_queue_bmm_query.c<br />
<br />
==Enums==<br />
enum [[r7.1.1:enum lfds711_queue_bmm_query|lfds711_queue_bmm_query]];<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct lfds711_queue_bmm_element|lfds711_queue_bmm_element]];<br />
struct [[r7.1.1:struct lfds711_queue_bmm_state|lfds711_queue_bmm_state]];<br />
<br />
==Macros==<br />
#define [[r7.1.1:macro LFDS711_QUEUE_BMM_GET_USER_STATE_FROM_STATE|LFDS711_QUEUE_BMM_GET_USER_STATE_FROM_STATE]]( queue_bmm_state )<br />
<br />
==Prototypes==<br />
void [[r7.1.1:function lfds711_queue_bmm_init_valid_on_current_logical_core|lfds711_queue_init_valid_on_current_logical_core]]( struct lfds711_queue_bmm_state *qumms,<br />
struct lfds711_queue_bmm_element *element_array,<br />
lfds711_pal_uint_t number_elements,<br />
void *user_state );<br />
<br />
void [[r7.1.1:function lfds711_queue_bmm_cleanup|lfds711_queue_bmm_cleanup]]( struct lfds711_queue_bmm_state *qbmms,<br />
void (*element_dequeue_callback)(struct lfds711_queue_umm_state *qumms,<br />
void *key,<br />
void *value) );<br />
<br />
int [[r7.1.1:function lfds711_queue_bmm_enqueue|lfds711_queue_bmm_enqueue]]( struct lfds711_queue_bmm_state *qbmms, void *key, void *value );<br />
<br />
int [[r7.1.1:function lfds711_queue_bmm_dequeue|lfds711_queue_bmm_dequeue]]( struct lfds711_queue_bmm_state *qbmms, void **key, void **value );<br />
<br />
void [[r7.1.1:function lfds711_queue_bmm_query|lfds711_queue_bmm_query]]( struct lfds711_queue_bmm_state *qbmms,<br />
enum lfds711_queue_umm_query query_type,<br />
void *query_input,<br />
void *query_output );<br />
<br />
==Overview==<br />
This data structure implements a bounded, many-producer, many-consumer queue and internally implements exponential backoff to help deal with high load and so improve scalability.<br />
<br />
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.<br />
<br />
General usage is that the user calls ''lfds711_queue_bmm_init_valid_on_current_logical_core'', passing in an array of ''struct lfds711_queue_bmm_elements'' which form the store for the queue, to initialize a ''struct lfds711_queue_bmm_state'', and then calls ''lfds711_queue_bmm_enqueue'' and ''lfds711_queue_bmm_dequeue'' to enqueue and dequeue ''struct lfds711_queue_bmm_element''s.<br />
<br />
A queue element provides the ability to store a key and a value, both of which are of type ''void *''. The key is not used in any way by the queue (and of course the value is neither), rather, it is available as a convenience for the user, for situations where data is being transferred between different types of data structures, where some of these data structures do support a meaningful key.<br />
<br />
The state and element structures are both public, present in the ''lfds711_queue_bmm.h'' header file, so that users can embed them in their own structures (and where necessary pass them to ''sizeof'').<br />
<br />
==Lock-free Specific Behaviour==<br />
The number of elements passed to the init function must be a positive integer power of two, i.e. two, four, eight, sixteen, etc.<br />
<br />
The state initialization function, ''lfds711_queue_bmm_init_valid_on_current_logical_core'', as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro ''[[r7.1.1:define LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'', which will do that which its name suggests.<br />
<br />
In general, in liblfds, the data structures are written such that by the time one of their functions returns, the operation performed by that function (enqueue, push, pop, etc) is both complete and visible to all other logical cores in the system. However, this data structure is not like this; when its functions return, they guarantee the operation has occurred and is visible to the current logical core, but they do not guarantee that the operation is yet visible to all other logical cores in the system, and in fact there is no actual guarantee that it will ever be visible to other logical cores in the system, although in practise it's a bit like breathing - there's no actual guarantee you'll take your next breath, but usually, you always do :-) <br />
<br />
In the spirit of Frankie Goes to Hollywood, these data structures are known as 'relaxed', because they just don't do it :-) <br />
<br />
As such, it can be for example that, starting with a full queue, one thread fully empties the queue, but other threads for some brief time (tens of microseconds, typically) will still see the queue as full.<br />
<br />
This can make writing code using this API awkward, but the benefit is performance. All relaxed data structures go like blazes.<br />
<br />
It must be understood though that this is not actually a lock-free data structure. The term lock-free is actually a specific technical term, with a particular meaning, but this is not how the term is used generally in the computing community - there, rather, it simply means "not using locking mechaisms, such as mutexes and spinlocks".<br />
<br />
The specific technical meaning is that when multiple threads are performing operations an instance of the data structure, any given single thread will be able to complete whatever operation it issues, regardless of the state of the other threads - for example, if they have been idled by the operating system. Lock-free actually means any given thread ''cannot be locked by other threads''.<br />
<br />
If we consider say the freelist, this is lock-free; even if we had a million threads, and they were in every possible variation of performing an operation on the freelist, and they were idled, then any thread which continues working (or any new thread) would be able to perform push or pop operations just fine.<br />
<br />
This however is not true of this bounded queue. There is in fact a very brief window during every enqueue and dequeue operation - a few instructions wide - where if the thread is idled, ''no other thread can progress''.<br />
<br />
This is unfortunate - it is in fact an inherent property of using an array as the backing store. All array-backed data structures display this problem. However, as mentioned, the window is extremely brief and as such, in practise, it is not an issue.<br />
<br />
==White Paper==<br />
The code is written from scratch for ''liblfds'', but the idea which has been implemented comes from Dmitry Vyukov, from his 1024cores.net site.<br />
<br />
==License==<br />
Dmitry Vyukov granted email permission for the idea to be used and implemented in ''liblfds'', under the MIT license.<br />
<br />
==Example==<br />
#include <stdio.h><br />
#include <string.h><br />
#include "liblfds711.h"<br />
<br />
struct test_data<br />
{<br />
char<br />
name[64];<br />
};<br />
<br />
int main()<br />
{<br />
struct lfds711_queue_bmm_element<br />
qbmme[8]; // TRD : must be a positive integer power of 2 (2, 4, 8, 16, etc)<br />
<br />
struct lfds711_queue_bmm_state<br />
qbmms;<br />
<br />
struct test_data<br />
td,<br />
*temp_td;<br />
<br />
lfds711_queue_bmm_init_valid_on_current_logical_core( &qbmms, qbmme, 8, NULL );<br />
<br />
strcpy( td.name, "Madge The Skutter" );<br />
<br />
lfds711_queue_bmm_enqueue( &qbmms, NULL, &td );<br />
<br />
lfds711_queue_bmm_dequeue( &qbmms, NULL, &temp_td );<br />
<br />
printf( "skutter name = %s\n", temp_td->name );<br />
<br />
lfds711_queue_bmm_cleanup( &qbmms, NULL );<br />
<br />
return( EXIT_SUCCESS );<br />
}<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=Main_Page&diff=2Main Page2017-06-16T16:45:33Z<p>Admin: </p>
<hr />
<div><table cellspacing="8" style="width:100%; margin:0; background:none;"><br />
<tr style="width:56%;"><br />
<td style="color:#000; background:#fcfcfc; margin-top:1.2em; border:1px solid #ccc;"><br />
<table style="width:280px; border:none; background:none;"><br />
<tr style="width:280px; text-align:center; white-space:nowrap; color:#000;"><br />
<td><br />
<div style="font-size:162%; border:none; margin:0; padding:.1em; color:#000;">Welcome to liblfds.org,</div><br />
<div style="top:+0.2em; font-size:95%;">a lock-free data structure library.</div><br />
<div style="font-size:85%;">[[Special:Statistics|{{NUMBEROFARTICLES}}]] articles</div><br />
</td><br />
</tr><br />
</table><br />
</td><br />
</tr><br />
<br />
<!-- ******************************************************************************************************** --><br />
<br />
<tr><br />
<td style="border:1px solid #cef2e0; background:#f5fffa;"><br />
<table width="100%"><br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; font-weight:bold; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">Overview</h2><br />
</td><br />
</tr><br />
<br />
<tr valign="top"><br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Documentation</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
* [[Introduction]]<br />
* [[Contributors]]<br />
* [[Articles]]<br />
* [[White Papers]]<br />
* [[Links]]<br />
* [[Next Release Status / New Features]]<br />
<br />
</div><br />
</td><br />
<br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Notes</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
Account creation and anonymous editing are disabled due to bots. Email (admin at liblfds dot org) should you wish for an account.<br />
<br />
</div><br />
<br />
</td><br />
</tr><br />
</table><br />
</td><br />
</tr><br />
<br />
<!-- ******************************************************************************************************** --><br />
<br />
<tr><br />
<td style="border:1px solid #cef2e0; background:#f5fffa;"><br />
<table width="100%"><br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; font-weight:bold; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">The Library</h2><br />
</td><br />
</tr><br />
<br />
<tr valign="top"><br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Documentation</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
* [[r6:Release 6 Documentation|Release 6]] <small>(29th Dec 2009)</small><br />
* [[r6.0.0:Release 6.0.0 Documentation|Release 6.0.0]] <small>(18th Dec 2012)</small><br />
* [[r6.1.0:Release 6.1.0 Documentation|Release 6.1.0]] <small>(31th Dec 2012)</small><br />
* [[r6.0.1:Release 6.0.1 Documentation|Release 6.0.1]] <small>(2nd Jan 2013)</small><br />
* [[r6.1.1:Release 6.1.1 Documentation|Release 6.1.1]] <small>(2nd Jan 2013)</small><br />
* [[r7.0.0:Release 7.0.0 Documentation|Release 7.0.0]] <small>(29th Dec 2015)</small><br />
* [[r7.1.0:Release 7.1.0 Documentation|Release 7.1.0]] <small>(31st May 2016)</small><br />
* [[r7.1.1:Release 7.1.1 Documentation|Release 7.1.1]] <small>(20th Feb 2017)</small><br />
<br />
</div><br />
<br />
</td><br />
<br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Notes</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
Release 6 is the original liblfds prior to the new versioning scheme.<br />
<br />
Release 6.0.0 is release 6 with and with only API and filename name changes so that it moves into the new namespace scheme, such that every version can be included and linked to concurrently in the same application. The code otherwise is ''completely'' unchanged.<br />
<br />
</div><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
__NOTOC__</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=Article:Memory_Barriers_(part_1)&diff=921Article:Memory Barriers (part 1)2017-05-08T13:49:12Z<p>Admin: /* Load Barriers */</p>
<hr />
<div>{{DISPLAYTITLE:Memory Barriers (part 1)}}<br />
==Introduction==<br />
Understanding memory barriers is a bit like receiving a multi-stage immunization :-) it's a lot to adjust to, so you have the first article which takes the reader part of the way, and the second article which finishes the job. The first article usually needs two or three days to be really mentally disgested. Recommended reading is the first article, and then waiting until you find certain questions naturally coming to mind - the second article answers those questions.<br />
<br />
===Sockets, Physical Packages, Physical Cores, Logical Cores and Threads===<br />
A socket holds a single physical package which holds any number of physical cores. A physical core may hold any number of logical cores. A thread runs on a logical core. The problems described herein occur when the reader and writer threads are on logical cores in separate physical cores. A single physical core knows everything that's going on in its own logical cores, such that the problems describe herein simply do not happen.<br />
<br />
==The Problem==<br />
To throw into stark relief the nature of the problem memory barriers exist to address, I can say this about multi-physical-core systems : a write to memory by a given physical core is not guaranteed to ''ever'' be seen by any other physical core in the system.<br />
<br />
So if you have a C program with say some global variables, and a thread writes to one of them, it can be that no other thread ''ever'' sees the write that was made.<br />
<br />
Similarly, if one thread declares a variable locally, or allocates some store from the heap, and then shares that store with another thread, any writes made by either thread may never be seen by the other thread.<br />
<br />
This is due to a processor hardware concept known as ''store buffers''. What these amount to is that a physical core may locally hold on to a write for an indefinite period, before it even becomes visible to the cache coherency protocol (and so to other physical cores). Additionally, even when writes do haphazardly make their way out into the system, the ''order'' in which they do so is completely arbitrary.<br />
<br />
Clearly, there ''is'' a need in multi-physical-core systems to be able to guarantee that writes from one physical core will be seen by another physical core, and in a particular order.<br />
<br />
==The Solution==<br />
The solution consists of two components; memory barriers, and atomic operations.<br />
<br />
===Store Barriers===<br />
There are three types of memory barrier. There is the load barrier, the store barrier, and the full barrier.<br />
<br />
To begin with, we need only consider the store barrier.<br />
<br />
All barriers are placed in the flow of code, much like any statement. In the code snippet below, STORE_BARRIER is a macro which expands to whatever magic rune the given platform uses to specify a store barrier.<br />
<br />
int<br />
a,<br />
b;<br />
<br />
a = 5;<br />
<br />
STORE_BARRIER;<br />
<br />
b = 10;<br />
<br />
Now, the initial, natural, intuitive and '''absolutely and diabolically incorrect''' view of this is that the store barrier will force all writes which have occurred before it out to memory (or at least out to the cache coherency protocol, which amounts to the same thing), such that other physical cores will see them.<br />
<br />
This is not the case. Be '''absolutely clear''' about this. A store barrier '''never''' causes any writes to memory.<br />
<br />
The and the only thing a store barrier does, is make it such that when the physical core finally ''does'' make a write to memory (which it may still never do, and so all of its writes may still never be seen by any other physical core), all those write operations issued ''before'' the store barrier will be published to memory ''before'' those store operations which were issued ''after''.<br />
<br />
So in the example snippet, neither the write to ''a'' nor the write to ''b'' may ''ever'' be seen by any other physical core - but when the physical core ''does'' finally make a write (if it does!), the write to ''a'' will be published before the write to ''b''.<br />
<br />
Underwhelmed? :-)<br />
<br />
However, this functionality is vital. It addresses the ''ordering'' problem. Consider a linked list, where an element in the list has a payload of a void pointer, which the user can set as he wishes before the element is linked into the list.<br />
<br />
When the element is linked to the list, it ''must'' be that the void pointer of user data is published to memory ''before'' the pointer adjustment to the list such that the element is linked, or we will have an element which is now in the list and by being in the list is visible to other physical cores, but where the void pointer of user data is ''not'' yet published to memory, and so other physical cores will be reading some random value for the void pointer of user data. Catastrophe/hiliarity ensue.<br />
<br />
So we now have an ability through memory barriers to control the ordering of writes - but they only take effect when the physical core actually makes a write to memory. The second part of the solution is the ability to induce the physical core to make a write to memory.<br />
<br />
===Atomic Writes===<br />
Atomic operations, such an an atomic add, ''force'' a write to memory, ''always''.<br />
<br />
This in turn brings all the previously issued store barriers into effect.<br />
<br />
So if we consider the linked list example, when we come to add a new element, we set the user data, issued a store barrier, and then use an atomic operation to link the new element into the list - and this atomic operation by writing to memory forces the earlier memory barriers to be honoured, which ensures the user data is written to memory prior to the list element being joined the list by the atomic operation.<br />
<br />
===Load Barriers===<br />
There is one final, vital matter to be aware of.<br />
<br />
That a physical core has actually written a value to memory - actually, really, genuinely has done so, because we cast the necessary magic runes with store barriers and atomic writes to guarantee that it is so - this '''still''' does not mean other physical cores will actually be using the values which were written.<br />
<br />
The problem is that other physical cores, in a load-side mirror image of store buffers, are never guranteed to actually be reading the values which are ''currently'' in memory. They may continue to use values they read earlier and have cached for an indefinite period of time.<br />
<br />
It's all fun in processor land.<br />
<br />
This behaviour is caused by the ''invalidation queue''. When a write to memory occurs, any physical core which has in its caches local copies of the values in memory which have been written to receives a message, an invalidation request, telling it that its local copies are now out of date - but these messages may ''not'' be processed in a timely manner (they queue up, in the invalidation queue), and so the physical core can continue to use the earlier, incorrect copy that it already holds for an indefinite period of time.<br />
<br />
If we consider the linked list example, it would mean that even though we in our new element set the user data, then issued a store barrier, then used an atomic operation to link the new element into the list, another physical core might already hold an earlier copy of the user data (perhaps we used that memory for something else earlier on, or maybe the OS cached some data in the background we didn't know about) and so when it comes to access the new element in the list and the user data in that element, it will end up using that earlier copy of the user data because it has not yet noticied the invalidation request telling it that its local copy is out of date. Catastrophe/hilarity, etc.<br />
<br />
This is where load barriers come in.<br />
<br />
The and the only thing a load barrier does, is make it such that when the physical core finally does complete a load from memory (which it may still never do, so none of these loads necessarily happen), all those load operations issued before the load barrier will be completed (which is to say, the invalidation request queue will be fully processed, to ensure this is so) before those load operations which were issued after the load barrier.<br />
<br />
In short, issuing a load barrier ensures that when a load finally completes ''after'' the barrier, that the invalidation request queue will prior to that completion be serviced, which in turn ensures that physical core really will see whatever completed stored have been published by other cores.<br />
<br />
So before we as a thread reading the linked list access the void pointer of user data, we must always issue a load barrier; this forces the invalidation request queue to be serviced before we read the user data.<br />
<br />
(It's worth remembering that processors are much better at deferring stores than they are loads; a store can be held in the store buffers and the processor can keep going, but a load means the processor really has to go and find out what that value is to be able to do any work which uses that value, which of course means if you issued a load barrier beforehand, that the processor will end up having to honour that load barrier so there's no need, as there is with store barriers, to perform an atomic operation to force the load barrier to be honoured.)<br />
<br />
===Full Barriers===<br />
A full barrier is a combination of a load barrier and a store barrier. They exist mainly for API completeness, I think - I think I've used one ''once'', as I normally need only load or store, depending on what I'm doing in the code.<br />
<br />
==See Also==<br />
* [[Articles]]<br />
* [[article:Memory Barriers (part 2)|Memory Barriers (part 2)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=Building_GCC&diff=928Building GCC2017-05-01T11:15:29Z<p>Admin: /* Problems */</p>
<hr />
<div>==Introduction==<br />
'''Most GCC builds on most platforms fail.'''<br />
<br />
By this I mean to say that most builds of GCC, out of the box, without taking steps to fix the build system and/or the source base, on most platforms, will fail. Not because you have messed it up, but because they are actually as released broken and ''cannot'' work. x86_64 does a lot better than other platforms and most builds work.<br />
<br />
I have spent now three months working towards building every released version of GCC, starting at 4.1.2, on four platforms, ARM32, ARM64, MIPS32 and x64. I originally intended to build also the matching glibc for each version of GCC.<br />
<br />
What I have come away with from this is that it is impossible to build GCC ''with'' glibc, and that most GCC builds on plaforms other than x64 are broken. They cannot be built. There are a few cases where you can fix the build system or the source code and achieve a build.<br />
<br />
Note that you only reach the point where you can know this after many, many weeks of struggling with the build system problems which occur *prior* to the point of unrecoverable failure.<br />
<br />
If you begin to think about building GCC and/or glibc, and Google, you will find, invariably, the advice to boot up an old distro and use the GCC shipped with it. This advice exists for a reason, as you have read above : only the GCC and glibc developers themselves, and perhaps the people who actually create major distros, can build GCC/glibc, and they normally only manage this by fixing the build system and/or source code at that point such that a build can occur. You need to know enough to do development work on the GCC source base, to build it.<br />
<br />
This is a fundamental and profound problem for professional software development. We must be able to choose which versions of the compiler and C library we use to compile our code, not least to ensure our code continues to work on older compilers which are still in widespread use.<br />
<br />
Where is is impossible to build glibc, and problematic to build GCC, it is not possible to control the build system, except by keeping old distro releases around, and using them to build, test, and release, and this is unnecessarily awkward; not least because I'm looking to test with about 40 different versions of GCC. Even finding distros for those old versions is going to be difficult, and there's no reason why I can't have multiple GCC and glibc versions on my current machine, except for the problems with their build systems. It also precludes real benchmarking, as such distros are likely to be run in virtual machines.<br />
<br />
It cannot be, for serious, professional development, that we use version a.b.c of a compiler, and then are forced off that version by updates to our operating system, and are unable then to go back and continue using that old version (at least in parallel with the new version).<br />
<br />
My actual advice after all of this probably to use clang. I've not tried it yet, but from what I've seen, it has a sane and viable build system.<br />
<br />
==Dependencies==<br />
When building GCC, there are a number of tools and libraries you need to be aware of, and know how to use.<br />
<br />
* the GCC source code itself<br />
* binutils<br />
* glibc<br />
* libgmp<br />
* libmpfr<br />
* libmpc<br />
* libisl<br />
* CLooG-PPL<br />
* libppl<br />
<br />
Of these, CLooG-PPL, libppl and libisl have been used at various times up to GCC 4.8.0 to implement loop optimization code. If they're not provided when building GCC, the loop optimization goodies will not be compiled in, but GCC will compile. I didn't need them, and there was already plenty of agony getting anything to compile at all, so I've never tried using them.<br />
<br />
libgmp, libmpfr and libmpc are dependency libraries used by GCC for handling math of various kinds - I don't know much more than that. Only libgmp and libmpfr were used up to 4.5.0, and then libmpc began to be needed as well.<br />
<br />
glibc is of course the C library.<br />
<br />
binutils is a package which contains a set of vital tools used in conjunction with GCC, such as ''ar'' and ''ld''.<br />
<br />
==Building==<br />
Basically, you get hold of the GCC source code, then you make a directory that you will build in, change into that directory and from there call ''configure'' in the GCC source directory. You then call ''make''. '''Do not build in the GCC source directory itself - always ''configure'' and ''make'' in a separate directory'''.<br />
<br />
GCC when it builds self-bootstraps. It first builds itself from the sources using the system compiler, then using that version of itself to build itself again, and then using that version of itself compiles itself again.<br />
<br />
GCC has the notion of the build system, the host system and the target system - so you can for example build on your x86_64 machine a compiler which is to be run on ARM32 which emits code which runs on MIPS32. For all the work I've done, I've been doing what's known as a ''native'' build - the build, host and target systems are identical.<br />
<br />
Regardng libgmp, libmpfr and libgmp, these can either be provided as source code and placed into the GCC directory, and then GCC will automatically configure and build them, or you can use the versions which come with your distro (in which case you need to install the libraries and their development packages).<br />
<br />
I gave up trying to build glibc, so I just use the version which comes with the distro.<br />
<br />
Binutils claims it can be built in the same way as libgmp, etc, by having its directory placed into the GCC source directory before calling GCC's configure. THIS IS NOT THE CASE. IT DOES NOT WORK. THE DOCUMENTATION IS A LIE. With libgmp, etc, they go into the root of the GCC source tree, so libgmp turns up as ''gmp''. Binutils however has to have ''each subdirectory'' placed into the root of the GCC source tree - so ''ar'', ''ld'', etc, all turn up as new top level directories. However, binutils has a top level directory ''include'' - but so does GCC - and these two directory have different versions of the same files.<br />
<br />
The advantage of building binutils in the GCC source tree is that the GCC you are building will build binutils. You can however build binutils normally (configure and make) on its own. This works, and then you need to use something like configure-alternatives to be able to switch to these new versions of binutils which you produce.<br />
<br />
For the work I've been doing, I gave up bothering with this and just used the bintuils which came with the distro.<br />
<br />
So - basics - get hold of the GCC source code, get hold of the libgmp, libmpfr and libmpc (if it's used by the version of GCC you're building) sources and put them into the root of the GCC source dir. Make a build directory, cd to it, ''configure'' and ''make''.<br />
<br />
The first problems now are what arguments to give ''configure'' and which versions of libgmp, libmpfr and libmpc to use.<br />
<br />
==Problems==<br />
Oh, so many problems.<br />
<br />
I don't know where to begin, and there have been so many, for so long, that I've forgotten half of them.<br />
<br />
The long and short of it is this : '''most GCC builds on most platforms fail.'''<br />
<br />
x86_64 does much better than other platforms, though.<br />
<br />
The errors vary wildly.<br />
<br />
So for example on MIPS32, building GCC 5.4.0 with the recommended dependency library versions leads to an error where the test suite for libgmp fails because half the test binaries do not have the execute bit set. (The libgmp support mailing list had nothing to say on the matter.) If you change to the latest version of the libraries, the build then fails because it thinks it can't build the link-time optimization code.<br />
<br />
(GCC takes a while to build, too - each of these builds took more than twenty hours. I could in theory build on my laptop, but I don't trust the build system as it is - the idea of trying to make it do something more complex than native builds gives me the screaming heebee-jeebees.)<br />
<br />
I think then with this build (as with most others) I have to give up. I would have to understand the source code and/or build system enough to do the necessary development work to fix it.<br />
<br />
This will be your normal experience, except on x86_64, where things tend much more to work.<br />
<br />
One thing you might run across quite early on when Googling for some build problem, is a build bug in the GCC bugzilla, and it's marked as a duplicate, and when you go to look at the duplicate, you find the central bug is a duplicate for dozens and dozens of other bugs (each of which has no information how to fix) and its body text says something like "these are not real problems, it's that you don't know how to build GCC".<br />
<br />
===libgmp, libmpfr, libmpc===<br />
GCC depends on these libraries. There is a script, ''contrib/download_prerequisites'', available from GCC 4.6.0 onwards, which downloads the versions you should use. Only... the versions specified have actually ''never'' changed, and are incredibly old and now unmaintained versions of these libraries, and in particular I know from experience for example that the specified libmpfr version is broken on MIPS32, and that ''none'' of them work on ARM64 (as the version of autotools used is too old - I think you can fix this by running it again, but I understand it's an open question whether or not that will actually work). Also, it's not clear which versions should be used prior to 4.6.0. I figured that out from the ''configure'' page of the GCC docs from each released versions and this is what you need;<br />
<br />
<table border="1" cellpadding="4"><br />
<tr><br />
<th>GCC</th><br />
<th>libmpfr</th><br />
<th>libgmp</th><br />
<th>libmpc</th><br />
</tr><br />
<br />
<tr><br />
<td>4.2.0 - 4.2.4</td><br />
<td>2.2.1</td><br />
<td>4.1.0</td><br />
<td>unused</td><br />
</tr><br />
<br />
<tr><br />
<td>4.3.0 - 4.3.6</td><br />
<td>2.3.0</td><br />
<td>4.1.0</td><br />
<td>unused</td><br />
</tr><br />
<br />
<tr><br />
<td>4.4.0 - 4.4.7</td><br />
<td>2.3.2</td><br />
<td>4.1.0</td><br />
<td>unused</td><br />
</tr><br />
<br />
<tr><br />
<td>4.5.0 onwards</td><br />
<td>2.4.2</td><br />
<td>4.3.2</td><br />
<td>0.8.1</td><br />
</tr><br />
</table><br />
<br />
The build systems for these libraries are not what you'd call fully reliable. I've mentioned the recommended version of libmpfr being broken on MIPS32, but for a second example, libgmp fails to build on arm from about version 5.1. I've yet to find out at which point it was fixed. Generally, they seem to build on x86_64. Go to other platforms and you're rolling the dice. I also begin to think that modern versions fail with old versions of GCC; older GCCs seem to be trying to interact with them in a way which fails.<br />
<br />
Since it's not clear what breakages exist in these libraries, and it's also not clear what problems exist in GCC, one of the games you end up playing is trying to find versions of these libraries which actually build on the platform you've got with the GCC you're trying to build.<br />
<br />
Be aware that the libraries also depend on each other; there is the not just the question of which version to use with GCC, but which versions of these libraries work with each other. You cannot independently change them. As with GCC, there is no information as such as to which versions work with which, but I have compiled (below) a table of when each was released, which can be used to get a feeling for which versions might work with which.<br />
<br />
For example, libmpfr 2.4.2 cannot work with libgmp 5.0.0 or later.<br />
<br />
====libmpfr 2.4.2 on MIPS32====<br />
This version is broken on MIPS32 for GCC 4.4.0 and later.<br />
<br />
(Yes. It really does mean every version of GCC released since 4.4.0 cannot build, out of the box, on MIPS32.)<br />
<br />
The [http://www.mpfr.org/mpfr-2.4.2/ release page] for this version has information and links to a patch;<br />
<br />
====libgmp configure====<br />
There is a common problem whereby the build fails with an error something like this;<br />
<br />
checking lex output file root... flex: fatal internal error, exec of m4-not-needed failed<br />
flex: error writing output file lex.yy.c<br />
configure: error: cannot find output from flex; giving up<br />
<br />
The problem is a bug in the libgmp configure. I remember it being something like the configure works when called directly from bash, but fails if you for example call it from a Python script.<br />
<br />
To work around it, grep the libgmp ''configure'' and ''configure.in'' files and replace;<br />
<br />
M4=m4-not-required<br />
<br />
with<br />
<br />
M4=m4<br />
<br />
====libgmp 4.3.2 test failure====<br />
There is one test, ''t-scan'', which always spuriously fails. This means all GCCs starting with 4.5.0 when using the recommended dependency versions fail their test suite. This of course is a problem for anyone automating builds.<br />
<br />
===gnumake===<br />
Version 4.1.2 of GCC came out when gnumake 3.7.9 was the latest release. This version has slightly different built-in rules to later versions, which means 4.1.2 fails to build with later versions of gnumake.<br />
<br />
===texinfo===<br />
GCC comes with documentation. Texinfo is the package used to build the docs. Texinfo over time has of course seen improvements. Unfortuntately, later versions of texinfo (5 onwards, I think) are no longer able to build the docs of older versions of GCC; a build error occurs. However, older versions of GCC only try to build their docs if texinfo is installed, so a solution is to uninstall it. However however, newer versions of GCC require texinfo to be installed, and fail to build if it is not present. Also, there are some versions in the middle which require texinfo to be installed and then fail to build their docs because of the problem with later versions of texinfo.<br />
<br />
A solution to this which I use is to touch the ''.info'' file for the dependency libraries, after copying them into the GCC source tree, i.e.<br />
<br />
touch [gccroot]/gmp/doc/gmp.info<br />
touch [gccroot]/mpfr/mpfr.info (pre 3.1.1)<br />
touch [gccroot]/mpft/doc/gmp.info (post 3.1.1)<br />
<br />
This seems to stop the doc build from happening.<br />
<br />
===Hard floating point support on Raspberry Pi===<br />
The Pi Debian distro is built with hard floating point support and as such does not ship with soft floating point header files. The compiler set define __ARM_PCS_VFP is used to indicate whether or not the system has hard floating point support, and this define is required by a number of header files. Earlier versions of GCC do not set this define, which causes the build of GCC to think the system is using soft floating point, and so when the attempt is made to #include them, the build fails (as they as not provided)<br />
<br />
This define can be manually set in CFLAGS, i.e.<br />
<br />
setenv CFLAGS -D__ARM_PCS_VFP<br />
<br />
The second problem is that the Debian distro is build with VFP and hard floating point, a combination not supported by earlier versions of GCC, which I think therefore cannot be built.<br />
<br />
===library and include search paths===<br />
GCC seems to need to be told where the system libraries and header files are, and fails if not set;<br />
<br />
setenv CC gcc<br />
setenv LIBRARY_PATH /usr/lib/x86_64-linux-gnu<br />
setenv C_INCLUDE_PATH /usr/include/x86_64-linux-gnu<br />
setenv CPLUS_INCLUDE_PATH /usr/include/x86_64-linux-gnu<br />
<br />
Replace ''x86_64-linux-gnu'' with whatever you have for your system.<br />
<br />
===GCC's configure===<br />
<br />
==Dependency Versions==<br />
I have compiled a table showing when ''GCC'', ''binutils'', ''libgmp'', ''libmpc'', ''libmpfr'' and ''numctl'' released occurred, going back to release 4.1.2 of GCC.<br />
<br />
These dates have been obtained by looking inside the archive files of the releases, as the file tiemstamps are not reliable (some archives having been republished much later than their original publication date).<br />
<br />
For a given GCC, look ''backwards'' in time for ''binutils'', ''libgmp'', ''libmpc'' and ''libmpfr'' (GCC requires these tools/libraries, so the assumption is that the latest versions existant at the time of the GCC release are in use, to pick up bug fixes - but this may not be true; it might be any given major (GCC versioning is "major.minor.bugfix") release always sticks with the versions available at the time of the first release of that major release), and look ''forwards'' in time for ''glibc'' and ''numactrl'' (as these libraries could only be compiled with a compiler which already existed at the time those libraries was released).<br />
<br />
===Table of GCC, GCC Dependency, glibc and numactl Release Dates===<br />
<br />
<table border="1" cellpadding="4"><br />
<tr><br />
<th></th><br />
<th></th><br />
<th>GCC</th><br />
<th>binutils</th><br />
<th>glibc</th><br />
<th>libmpfr</th><br />
<th>numactl</th><br />
<th>libgmp</th><br />
<th>libmpc</th><br />
</tr><br />
<br />
<!-- 2016 --><br />
<br />
<tr><br />
<th rowspan="10">2016</th><br />
<th>Sep 27</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.1.5</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 22</th><br />
<td>6.2.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 4</th><br />
<td></td><br />
<td></td><br />
<td>2.24</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 3</th><br />
<td>4.9.4</td><br />
<td>2.27</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 29</th><br />
<td></td><br />
<td>2.26.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 3</th><br />
<td>5.4.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 27</th><br />
<td>6.1.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 6</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.1.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 19</th><br />
<td></td><br />
<td></td><br />
<td>2.23</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 25</th><br />
<td></td><br />
<td>2.26</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2015 --><br />
<br />
<tr><br />
<th rowspan="12">2015</th><br />
<th>Dec 10</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.11</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 4</th><br />
<td>5.3.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 1</th><br />
<td></td><br />
<td></td><br />
<td>2.22</td><br />
<td></td><br />
<td></td><br />
<td>6.1.0</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 5</th><br />
<td></td><br />
<td></td><br />
<td>2.22</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 19</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.1.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 16</th><br />
<td>5.2.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 21</th><br />
<td></td><br />
<td>2.25.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 26</th><br />
<td>4.9.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 23</th><br />
<td>4.8.5</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 22</th><br />
<td>5.1.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 16</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0.3</td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 6</th><br />
<td></td><br />
<td></td><br />
<td>2.21</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2014 --><br />
<br />
<tr><br />
<th rowspan="13">2014</th><br />
<th>Dec 23</th><br />
<td></td><br />
<td>2.25</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 10</th><br />
<td>4.8.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 30</th><br />
<td>4.9.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 20</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.10</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 7</th><br />
<td></td><br />
<td></td><br />
<td>2.20</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 16</th><br />
<td>4.9.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 12</th><br />
<td>4.7.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 22</th><br />
<td>4.8.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 22</th><br />
<td>4.9.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 25</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>6.0.0a</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 24</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>6.0.0</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 7</th><br />
<td></td><br />
<td></td><br />
<td>2.19</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 15</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0.2</td><br />
</tr><br />
<br />
<!-- 2013 --><br />
<br />
<tr><br />
<th rowspan="14">2013</th><br />
<th>Dec 2</th><br />
<td></td><br />
<td>2.24</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 16</th><br />
<td>4.8.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 8</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.9</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 30</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.1.3</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 12</th><br />
<td></td><br />
<td></td><br />
<td>2.18</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 31</th><br />
<td>4.8.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 30</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.1.2</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 12</th><br />
<td>4.6.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 11</th><br />
<td>4.7.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 25</th><br />
<td></td><br />
<td>2.23.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 22</th><br />
<td>4.8.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 13</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.1.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 11</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.1.1</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 2</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.1.0a</td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2012 --><br />
<br />
<tr><br />
<th rowspan="18">2012</th><br />
<th>Dec 25</th><br />
<td></td><br />
<td></td><br />
<td>2.17</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 18</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.1.0</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 13</th><br />
<td></td><br />
<td>2.23.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 22</th><br />
<td></td><br />
<td>2.23</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 11</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.8</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 20</th><br />
<td>4.7.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 6</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0.1</td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 3</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.1.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 2</th><br />
<td>4.5.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 30</th><br />
<td></td><br />
<td></td><br />
<td>2.16.0<small><sup>1</sup></small></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 14</th><br />
<td>4.7.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 6</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.0.5</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 22</th><br />
<td>4.7.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 21</th><br />
<td></td><br />
<td></td><br />
<td>2.15</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 13</th><br />
<td>4.4.7</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 1</th><br />
<td>4.6.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 10</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.0.4</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 27</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.0.3</td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2011 --><br />
<br />
<tr><br />
<th rowspan="15">2011</th><br />
<th>Nov 21</th><br />
<td></td><br />
<td>2.22</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 28</th><br />
<td>4.6.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 7</th><br />
<td></td><br />
<td></td><br />
<td>2.14.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 3</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.1.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 19</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0</td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 27</th><br />
<td>4.6.1, 4.3.6</td><br />
<td>2.21.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 1</th><br />
<td></td><br />
<td></td><br />
<td>2.14</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 8</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.0.2</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 28</th><br />
<td>4.5.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 16</th><br />
<td>4.4.6</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 14</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.7</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 4</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.0.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 25</th><br />
<td>4.6.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 22</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.9</td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 1</th><br />
<td></td><br />
<td></td><br />
<td>2.13</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2010 --><br />
<br />
<tr><br />
<th rowspan="21">2010</th><br />
<th>Dec 29</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.6</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 16</th><br />
<td>4.5.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 13</th><br />
<td></td><br />
<td></td><br />
<td>2.12.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 8</th><br />
<td></td><br />
<td>2.21</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 29</th><br />
<td></td><br />
<td></td><br />
<td>2.11.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 4</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.5</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 1</th><br />
<td>4.4.5</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 3</th><br />
<td></td><br />
<td></td><br />
<td>2.12.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 31</th><br />
<td>4.5.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 28</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.4</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 10</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>3.0.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 22</th><br />
<td>4.3.5</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 19</th><br />
<td></td><br />
<td></td><br />
<td>2.11.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 14</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.8.2</td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 29</th><br />
<td>4.4.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 14</th><br />
<td>4.5.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 3</th><br />
<td></td><br />
<td>2.20.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 6</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.0.1</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 21</th><br />
<td>4.4.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 8</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>5.0.0</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 7</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.3.2</td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2009 --><br />
<br />
<tr><br />
<th rowspan="22">2009</th><br />
<th>Dec 29</th><br />
<td></td><br />
<td></td><br />
<td>2.11.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Dec 7</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.8.1</td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 30</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.4.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 5</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.8</td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 3</th><br />
<td></td><br />
<td></td><br />
<td>2.11</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 15</th><br />
<td>4.4.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 10</th><br />
<td></td><br />
<td>2.20</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 10</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.7</td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 4</th><br />
<td>4.3.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 22</th><br />
<td>4.4.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 10</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.3</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 17</th><br />
<td></td><br />
<td></td><br />
<td>2.10.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 12</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.3.1</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 21</th><br />
<td>4.4.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 14</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.3.0</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 1</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.6</td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 10</th><br />
<td></td><br />
<td></td><br />
<td>2.9</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 26</th><br />
<td></td><br />
<td></td><br />
<td>2.8</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 25</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.4.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 2</th><br />
<td></td><br />
<td>2.19.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 26</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.4.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jan 24</th><br />
<td>4.3.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2008 --><br />
<br />
<tr><br />
<th rowspan="15">2008</th><br />
<th>Dec 12</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.5.2</td><br />
</tr><br />
<br />
<tr><br />
<th>Nov 18</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.5.1</td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 16</th><br />
<td></td><br />
<td>2.19</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 20</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.2.4</td><br />
<td></td><br />
</tr><br />
<br />
<br />
<tr><br />
<th>Sep 17</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.5</td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 27</th><br />
<td>4.3.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 5</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.2</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 2</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.2.3</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 10</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.1</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 6</th><br />
<td>4.3.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 19</th><br />
<td>4.2.4</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 7</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>2.0.0</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 5</th><br />
<td>4.3.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Apr 14</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0.3</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 1</th><br />
<td>4.2.3</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2007 --><br />
<br />
<tr><br />
<th rowspan="11">2007</th><br />
<th>Oct 10</th><br />
<td></td><br />
<td></td><br />
<td>2.7</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Oct 7</th><br />
<td>4.2.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 21</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0.2</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 11</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.2.2</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 28</th><br />
<td></td><br />
<td>2.18</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Aug 16</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>1.0.1, 1.0</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 31</th><br />
<td></td><br />
<td></td><br />
<td>2.5.1, 2.6.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jul 18</th><br />
<td>4.2.1</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 17</th><br />
<td></td><br />
<td></td><br />
<td>2.6</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 13</th><br />
<td>4.2.0</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Feb 13</th><br />
<td>4.1.2</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<!-- 2006 --><br />
<br />
<tr><br />
<th rowspan="5">2006</th><br />
<th>Oct 31</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>0.9.11</td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Sep 20</th><br />
<td></td><br />
<td></td><br />
<td>2.5</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Jun 23</th><br />
<td></td><br />
<td>2.17</td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>May 24</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.2.1</td><br />
<td></td><br />
</tr><br />
<br />
<tr><br />
<th>Mar 26</th><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td></td><br />
<td>4.2<sup>2</sup></td><br />
<td></td><br />
</tr><br />
<br />
</table><br />
<br />
<p><small>1. Yes, 2.16.0, not 2.16 - I have no idea why.<br><br />
2. Yes, 4.2, not 4.2.0</small></p></div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Function_lfds711_queue_bmm_init_valid_on_current_logical_core&diff=1008r7.1.1:Function lfds711 queue bmm init valid on current logical core2017-02-22T14:41:39Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:function lfds711_queue_bmm_init_valid_on_current_logical_core}}<br />
==Source Files==<br />
└───liblfds711<br />
├───inc<br />
│ └───liblfds711<br />
│ lfds711_queue_bmm.h<br />
└───src<br />
└───llfds711_queue<br />
lfds711_queue_bmm_init.c<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct lfds711_queue_bmm_element|lfds711_queue_bmm_element]];<br />
struct [[r7.1.1:struct lfds711_queue_bmm_state|lfds711_queue_bmm_state]];<br />
<br />
==Prototype==<br />
void lfds711_queue_bmm_init_valid_on_current_logical_core( struct lfds711_queue_bmm_state *qbmms,<br />
struct lfds711_queue_bmm_element *element_array,<br />
lfds711_pal_uint_t number_elements,<br />
void *user_state );<br />
<br />
==Parameters==<br />
''struct lfds711_queue_bmm_state *qbmms''<br />
: A pointer to a user-allocated ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned ''struct lfds711_queue_bmm_state''. Stack declared variables will automatically be correctly aligned by the compiler, due to the information in the structure definitions; nothing has to be done. Heap allocated variables however will by no means be correctly aligned and an aligned malloc must be used.<br />
<br />
''struct lfds711_queue_bmm_element *element_array''<br />
: A pointer to a user-allocated array of ''struct lfds711_queue_bmm_element''. There are no alignment requirements for this allocation.<br />
<br />
''lfds711_pal_uint_t number_elements''<br />
: The number of elements in the array pointed to by ''element_array''. The number of elements in the array must be a positive integer power of two, i.e. two, four, eight, sixteen, etc.<br />
<br />
''void *user_state''<br />
: A pointer to void, supplied by the user, which is returned to the user in various callback functions, permitting the user to pass his own state into those functions. This argument can be NULL.<br />
<br />
==Notes==<br />
The number of elements in the array must be a positive integer power of two, i.e. two, four, eight, sixteen, etc.<br />
<br />
As the function name indicates, the initialization work performed on the queue state is only valid on the current logical core. To make this work valid on other logical cores, threads on other cores must call ''[[r7.1.1:define LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS711_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]''.<br />
<br />
==See Also==<br />
* [[r7.1.1:Queue (bounded, many producer, many consumer)|Queue (bounded, many producer, many consumer)]]<br />
* ''[[r7.1.1:function lfds711_queue_bmm_cleanup|lfds711_queue_bmm_cleanup]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.0:Function_lfds710_queue_bmm_init_valid_on_current_logical_core&diff=823r7.1.0:Function lfds710 queue bmm init valid on current logical core2017-02-22T14:41:36Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:function lfds710_queue_bmm_init_valid_on_current_logical_core}}<br />
==Source Files==<br />
└───liblfds710<br />
├───inc<br />
│ └───liblfds710<br />
│ lfds710_queue_bmm.h<br />
└───src<br />
└───llfds710_queue<br />
lfds710_queue_bmm_init.c<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.0:struct lfds710_queue_bmm_element|lfds710_queue_bmm_element]];<br />
struct [[r7.1.0:struct lfds710_queue_bmm_state|lfds710_queue_bmm_state]];<br />
<br />
==Prototype==<br />
void lfds710_queue_bmm_init_valid_on_current_logical_core( struct lfds710_queue_bmm_state *qbmms,<br />
struct lfds710_queue_bmm_element *element_array,<br />
lfds710_pal_uint_t number_elements,<br />
void *user_state );<br />
<br />
==Parameters==<br />
''struct lfds710_queue_bmm_state *qbmms''<br />
: A pointer to a user-allocated ''LFDS710_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned ''struct lfds710_queue_bmm_state''. Stack declared variables will automatically be correctly aligned by the compiler, due to the information in the structure definitions; nothing has to be done. Heap allocated variables however will by no means be correctly aligned and an aligned malloc must be used.<br />
<br />
''struct lfds710_queue_bmm_element *element_array''<br />
: A pointer to a user-allocated array of ''struct lfds710_queue_bmm_element''. There are no alignment requirements for this allocation. <br />
<br />
''lfds710_pal_uint_t number_elements''<br />
: The number of elements in the array pointed to by ''element_array''. The number of elements in the array must be a positive integer power of two, i.e. two, four, eight, sixteen, etc.<br />
<br />
''void *user_state''<br />
: A pointer to void, supplied by the user, which is returned to the user in various callback functions, permitting the user to pass his own state into those functions. This argument can be NULL.<br />
<br />
==Notes==<br />
The number of elements in the array must be a positive integer power of two, i.e. two, four, eight, sixteen, etc.<br />
<br />
As the function name indicates, the initialization work performed on the queue state is only valid on the current logical core. To make this work valid on other logical cores, threads on other cores must call ''[[r7.1.0:define LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]''.<br />
<br />
==See Also==<br />
* [[r7.1.0:Queue (bounded, many producer, many consumer)|Queue (bounded, many producer, many consumer)]]<br />
* ''[[r7.1.0:function lfds710_queue_bmm_cleanup|lfds710_queue_bmm_cleanup]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.0:Queue_(bounded,_many_producer,_many_consumer)&diff=818r7.1.0:Queue (bounded, many producer, many consumer)2017-02-22T14:28:49Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Queue (bounded, many producer, many consumer)}}<br />
==Source Files==<br />
└───liblfds710<br />
├───inc<br />
│ └───liblfds710<br />
│ lfds710_queue_bmm.h<br />
└───src<br />
└───lfds710_queue<br />
lfds710_queue_bmm_cleanup.c<br />
lfds710_queue_bmm_dequeue.c<br />
lfds710_queue_bmm_enqueue.c<br />
lfds710_queue_bmm_init.c<br />
lfds710_queue_bmm_internal.h<br />
lfds710_queue_bmm_query.c<br />
<br />
==Enums==<br />
enum [[r7.1.0:enum lfds710_queue_bmm_query|lfds710_queue_bmm_query]];<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.0:struct lfds710_queue_bmm_element|lfds710_queue_bmm_element]];<br />
struct [[r7.1.0:struct lfds710_queue_bmm_state|lfds710_queue_bmm_state]];<br />
<br />
==Macros==<br />
#define [[r7.1.0:macro LFDS710_QUEUE_BMM_GET_USER_STATE_FROM_STATE|LFDS710_QUEUE_BMM_GET_USER_STATE_FROM_STATE]]( queue_bmm_state )<br />
<br />
==Prototypes==<br />
void [[r7.1.0:function lfds710_queue_bmm_init_valid_on_current_logical_core|lfds710_queue_init_valid_on_current_logical_core]]( struct lfds710_queue_bmm_state *qumms,<br />
struct lfds710_queue_bmm_element *element_array,<br />
lfds710_pal_uint_t number_elements,<br />
void *user_state );<br />
<br />
void [[r7.1.0:function lfds710_queue_bmm_cleanup|lfds710_queue_bmm_cleanup]]( struct lfds710_queue_bmm_state *qbmms,<br />
void (*element_dequeue_callback)(struct lfds710_queue_umm_state *qumms,<br />
void *key,<br />
void *value) );<br />
<br />
void [[r7.1.0:function lfds710_queue_bmm_enqueue|lfds710_queue_bmm_enqueue]]( struct lfds710_queue_bmm_state *qbmms, void *key, void *value );<br />
<br />
int [[r7.1.0:function lfds710_queue_bmm_dequeue|lfds710_queue_bmm_dequeue]]( struct lfds710_queue_bmm_state *qbmms, void **key, void **value );<br />
<br />
void [[r7.1.0:function lfds710_queue_bmm_query|lfds710_queue_bmm_query]]( struct lfds710_queue_bmm_state *qbmms,<br />
enum lfds710_queue_umm_query query_type,<br />
void *query_input,<br />
void *query_output );<br />
<br />
==Overview==<br />
This data structure implements a bounded, many-producer, many-consumer queue and internally implements exponential backoff to help deal with high load and so improve scalability.<br />
<br />
The implementation performs no allocations. The user is responsible for all allocations (and deallocations), where these allocations are passed into the API functions, which then use them. As such, allocations can be on the stack, on the heap, or as can sometimes be the the case in embedded systems, allocated with fixed addresses at compile time from a fixed global store. Allocations can also be shared memory, but in this case, the virtual addresses used must be the same in all processes.<br />
<br />
General usage is that the user calls ''lfds710_queue_bmm_init_valid_on_current_logical_core'', passing in an array of ''struct lfds710_queue_bmm_elements'' which form the store for the queue, to initialize a ''struct lfds710_queue_bmm_state'', and then calls ''lfds710_queue_bmm_enqueue'' and ''lfds710_queue_bmm_dequeue'' to enqueue and dequeue ''struct lfds710_queue_bmm_element''s.<br />
<br />
A queue element provides the ability to store a key and a value, both of which are of type ''void *''. The key is not used in any way by the queue (and of course the value is neither), rather, it is available as a convenience for the user, for situations where data is being transferred between different types of data structures, where some of these data structures do support a meaningful key.<br />
<br />
The state and element structures are both public, present in the ''lfds710_queue_bmm.h'' header file, so that users can embed them in their own structures (and where necessary pass them to ''sizeof'').<br />
<br />
==Lock-free Specific Behaviour==<br />
The number of elements passed to the init function must be a positive integer power of two, i.e. two, four, eight, sixteen, etc.<br />
<br />
The state initialization function, ''lfds710_queue_bmm_init_valid_on_current_logical_core'', as the same suggests, initializes the state structure but that initialization is only valid on the current logical core. For the initialization to be valid on other logical cores (i.e. other threads where they are running on other logical cores) those other threads need to call the long-windedly named macro ''[[r7.1.0:define LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE|LFDS710_MISC_MAKE_VALID_ON_CURRENT_LOGICAL_CORE_INITS_COMPLETED_BEFORE_NOW_ON_ANY_OTHER_LOGICAL_CORE]]'', which will do that which its name suggests.<br />
<br />
In general, in liblfds, the data structures are written such that by the time one of their functions returns, the operation performed by that function (enqueue, push, pop, etc) is both complete and visible to all other logical cores in the system. However, this data structure is not like this; when its functions return, they guarantee the operation has occurred and is visible to the current logical core, but they do not guarantee that the operation is yet visible to all other logical cores in the system, and in fact there is no actual guarantee that it will ever be visible to other logical cores in the system, although in practise it's a bit like breathing - there's no actual guarantee you'll take your next breath, but usually, you always do :-) <br />
<br />
In the spirit of Frankie Goes to Hollywood, these data structures are known as 'relaxed', because they just don't do it :-) <br />
<br />
As such, it can be for example that, starting with a full queue, one thread fully empties the queue, but other threads for some brief time (tens of microseconds, typically) will still see the queue as full.<br />
<br />
This can make writing code using this API awkward, but the benefit is performance. All relaxed data structures go like blazes.<br />
<br />
It must be understood though that this is not actually a lock-free data structure. The term lock-free is actually a specific technical term, with a particular meaning, but this is not how the term is used generally in the computing community - there, rather, it simply means "not using locking mechaisms, such as mutexes and spinlocks".<br />
<br />
The specific technical meaning is that when multiple threads are performing operations an instance of the data structure, any given single thread will be able to complete whatever operation it issues, regardless of the state of the other threads - for example, if they have been idled by the operating system. Lock-free actually means any given thread ''cannot be locked by other threads''.<br />
<br />
If we consider say the freelist, this is lock-free; even if we had a million threads, and they were in every possible variation of performing an operation on the freelist, and they were idled, then any thread which continues working (or any new thread) would be able to perform push or pop operations just fine.<br />
<br />
This however is not true of this bounded queue. There is in fact a very brief window during every enqueue and dequeue operation - a few instructions wide - where if the thread is idled, ''no other thread can progress''.<br />
<br />
This is unfortunate - it is in fact an inherent property of using an array as the backing store. All array-backed data structures display this problem. However, as mentioned, the window is extremely brief and as such, in practise, it is not an issue.<br />
<br />
==White Paper==<br />
The code is written from scratch for ''liblfds'', but the idea which has been implemented comes from Dmitry Vyukov, from his 1024cores.net site.<br />
<br />
==License==<br />
Dmitry Vyukov granted email permission for the idea to be used and implemented in ''liblfds'', under the MIT license.<br />
<br />
==Example==<br />
#include <stdio.h><br />
#include <string.h><br />
#include "liblfds710.h"<br />
<br />
struct test_data<br />
{<br />
char<br />
name[64];<br />
};<br />
<br />
int main()<br />
{<br />
struct lfds710_queue_bmm_element<br />
qbmme[8]; // TRD : must be a positive integer power of 2 (2, 4, 8, 16, etc)<br />
<br />
struct lfds710_queue_bmm_state<br />
qbmms;<br />
<br />
struct test_data<br />
td,<br />
*temp_td;<br />
<br />
lfds710_queue_bmm_init_valid_on_current_logical_core( &qbmms, qbmme, 8, NULL );<br />
<br />
strcpy( td.name, "Madge The Skutter" );<br />
<br />
lfds710_queue_bmm_enqueue( *qbmms, NULL, &td );<br />
<br />
lfds710_queue_bmm_dequeue( &qbmms, NULL, &temp_td );<br />
<br />
printf( "skutter name = %s\n", temp_td->name );<br />
<br />
lfds710_queue_bmm_cleanup( &qbmms, NULL );<br />
<br />
return( EXIT_SUCCESS );<br />
}<br />
<br />
==See Also==<br />
* [[r7.1.0:Release_7.1.0_Documentation|Release 7.1.0 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Known_Issues&diff=1144r7.1.1:Known Issues2017-02-18T11:25:16Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Known Issues}}<br />
==liblfds==<br />
No known issues.<br />
<br />
==libshared==<br />
* 31st May 2016 - The Linux kernel abstraction layer port is incomplete.<br />
<br />
==libtest==<br />
* 18th Feburary 2017 - some test will spuriously fail if they do not complete at least one internal iteration of the data test; this has been observed on the ringbuffer write test, on ARM32, on a Raspberry Pi 2. Currently there is a performance issue with the unbounded/many/many queue on ARM32 (this was missed when 7.1.0 was released - too many bars on the bar graph!) and this in particular causes this problem on ARM32.<br />
<br />
==libbenchmark==<br />
* 31st May 2016 - The Linux kernel abstraction layer port is incomplete.<br />
* 31st May 2016 - The btree test is a bit unfair - it does a bit more work as the number of logical cores increases, so as such, it is underplaying performance for higher core counts.<br />
<br />
==test==<br />
* 31st May 2016 - If using shared object versions of ''liblfds'' libraries, cannot link on ARM32. Quite possibly not a ''liblfds'' bug, but still an issue.<br />
<br />
==benchmark==<br />
* 31st May 2016 - If using shared object versions of ''liblfds'' libraries, cannot link on ARM32. Quite possibly not a ''liblfds'' bug, but still an issue.<br />
* 19th Aug 2016 - huge bug; builds using "gcc_gnumake_hosted_liblfds711_liblfds700" all crash, because some code involved in benchmark init effectively assumes NUMA. To work around this, install libnuma-devel (name varies a little by platform) and compile the "gcc_gnumake_hosted_liblfds711_liblfds700_libnuma" variant.<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.0:Known_Issues&diff=725r7.1.0:Known Issues2017-02-18T11:25:03Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Known Issues}}<br />
==liblfds==<br />
* 7th June 2016 - The porting abstraction layer for x64, with GCC versions >= 4.1.2 and < 4.7.3, is missing the LFDS720_PAL_ATOMIC_DWCAS macro, i.e. is broken and the code will not compile. This is my fault - I have a GCC in that version range, but only on MIPS32. To fix this, add the following code on line 314 of ''lfds710_porting_abstraction_layer_compiler.h'';<br />
<br />
#if( defined __x86_64__ )<br />
/* TRD : On 64 bit platforms, unsigned long long int is 64 bit, so we must manually use cmpxchg16b, <br />
as the atomic intrinsics will only emit cmpxchg8b<br />
*/<br />
<br />
// TRD : lfds710_pal_uint_t volatile (*destination)[2], lfds710_pal_uint_t (*compare)[2], lfds710_pal_uint_t (*new_destination)[2], enum lfds710_misc_cas_strength cas_strength, char unsigned result<br />
<br />
#define LFDS710_PAL_ATOMIC_DWCAS( pointer_to_destination, pointer_to_compare, pointer_to_new_destination, cas_strength, result ) \<br />
{ \<br />
(result) = 0; \<br />
\<br />
__asm__ __volatile__ \<br />
( \<br />
"lock;" /* make cmpxchg16b atomic */ \<br />
"cmpxchg16b %0;" /* cmpxchg16b sets ZF on success */ \<br />
"setz %4;" /* if ZF set, set result to 1 */ \<br />
\<br />
/* output */ \<br />
: "+m" ((pointer_to_destination)[0]), "+m" ((pointer_to_destination)[1]), "+a" ((pointer_to_compare)[0]), "+d" ((pointer_to_compare)[1]), "=q" (result) \<br />
\<br />
/* input */ \<br />
: "b" ((pointer_to_new_destination)[0]), "c" ((pointer_to_new_destination)[1]) \<br />
\<br />
/* clobbered */ \<br />
: \<br />
); \<br />
}<br />
#endif<br />
<br />
* 23rd June 2016 - build on MIPS64 is broken, as on that platform the #ifdefs select both the MIPS32 abstraction and the MIPS64 abstraction.<br />
<br />
* 17th Feburary 2017 - '''major bug''' in the unbounded, many, many queue. A bug was introduced in 7.1.0 in the code, outside of the lock-free code, which handles exponential backoff. This means that a race condition now exists where a queue can end up seemingly dequeuing an empty element when a non-empty element was expected, or an element which has already been dequeued. Release 7.1.1 fixes this bug. Full details here; http://www.liblfds.org/wordpress/?p=884<br />
<br />
==libshared==<br />
* 31st May 2016 - The Linux kernel abstraction layer port is incomplete.<br />
<br />
==libtest==<br />
* 18th Feburary 2017 - some test will spuriously fail if they do not complete at least one internal iteration of the data test; this has been observed on the ringbuffer write test, on ARM32, on a Raspberry Pi 2. Currently there is a performance issue with the unbounded/many/many queue on ARM32 (this was missed when 7.1.0 was released - too many bars on the bar graph!) and this in particular causes this problem on ARM32.<br />
<br />
==libbenchmark==<br />
* 31st May 2016 - The Linux kernel abstraction layer port is incomplete.<br />
* 31st May 2016 - The btree test is a bit unfair - it does a bit more work as the number of logical cores increases, so as such, it is underplaying performance for higher core counts.<br />
<br />
==test==<br />
* 31st May 2016 - If using shared object versions of ''liblfds'' libraries, cannot link on ARM32. Quite possibly not a ''liblfds'' bug, but still an issue.<br />
<br />
==benchmark==<br />
* 31st May 2016 - If using shared object versions of ''liblfds'' libraries, cannot link on ARM32. Quite possibly not a ''liblfds'' bug, but still an issue.<br />
* 19th Aug 2016 - huge bug; builds using "gcc_gnumake_hosted_liblfds710_liblfds700" all crash, because some code involved in benchmark init effectively assumes NUMA. To work around this, install libnuma-devel (name varies a little by platform) and compile the "gcc_gnumake_hosted_liblfds710_liblfds700_libnuma" variant.<br />
<br />
==See Also==<br />
* [[r7.1.0:Release_7.1.0_Documentation|Release 7.1.0 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.0:Release_7.1.0_Documentation&diff=787r7.1.0:Release 7.1.0 Documentation2017-02-18T11:21:36Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Release 7.1.0 Documentation}}<br />
<table cellspacing="8" style="width:100%; margin:0; background:none;"><br />
<br />
<tr><br />
<td style="border:1px solid #cef2e0; background:#f5fffa;"><br />
<table width="100%"><br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; font-weight:bold; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">Release 7.1.0 Documentation</h2><br />
</td><br />
</tr><br />
<br />
<tr valign="top"><br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">API Documentation</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
* [[r7.1.0:Binary Tree (add-only, unbalanced)|Binary Tree (add-only, unbalanced)]]<br />
* [[r7.1.0:Freelist|Freelist]]<br />
* [[r7.1.0:Hash (add-only)|Hash (add-only)]]<br />
* [[r7.1.0:Misc|Misc]]<br />
* [[r7.1.0:PRNG|PRNG]]<br />
* [[r7.1.0:List (add-only, singly-linked, ordered)|List (add-only, singly-linked, ordered)]]<br />
* [[r7.1.0:List (add-only, singly-linked, unordered)|List (add-only, singly-linked, unordered)]]<br />
* [[r7.1.0:Queue (bounded, many producer, many consumer)|Queue (bounded, many producer, many consumer)]]<br />
* [[r7.1.0:Queue (bounded, single producer, single consumer)|Queue (bounded, single producer, single consumer)]]<br />
* [[r7.1.0:Queue (unbounded, many producer, many consumer)|Queue (unbounded, many producer, many consumer)]]<br />
* [[r7.1.0:Ringbuffer|Ringbuffer]]<br />
* [[r7.1.0:Stack|Stack]]<br />
<br />
</div><br />
<br />
</td><br />
<br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Misc</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
liblfds consists of the library itself, a benchmark programme and a test programme.<br />
<br />
* [[r7.1.0:Introduction|Introduction]]<br />
* [[r7.1.0:Release Note / Upgrading|Release Note / Upgrading]]<br />
* [[r7.1.0:Building Guide (liblfds)|Building Guide (liblfds)]]<br />
* [[r7.1.0:Building Guide (testing)|Building Guide (testing)]]<br />
* [[r7.1.0:Building Guide (benchmarking)|Building Guide (benchmarking)]]<br />
* [[r7.1.0:Usage Guide (liblfds)|Usage Guide (liblfds)]]<br />
* [[r7.1.0:Usage Guide (testing)|Usage Guide (testing)]]<br />
* [[r7.1.0:Usage Guide (benchmarking)|Usage Guide (benchmarking)]]<br />
* [[r7.1.0:Known Issues|Known Issues]] <small>(18th Feburary 2017)</small><br />
<br />
</div><br />
<br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Porting</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
Windows and Linux are supported out of the box, for both user-mode and kernel-mode.<br />
<br />
* [[r7.1.0:Porting Guide (liblfds)|Porting Guide (liblfds)]]<br />
* [[r7.1.0:Porting Guide (testing)|Porting Guide (testing)]]<br />
* [[r7.1.0:Porting Guide (benchmarking)|Porting Guide (benchmarking)]]<br />
<br />
</div><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
__NOTOC__</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Release_7.1.1_Documentation&diff=1177r7.1.1:Release 7.1.1 Documentation2017-02-18T11:21:28Z<p>Admin: </p>
<hr />
<div>{{DISPLAYTITLE:Release 7.1.1 Documentation}}<br />
<table cellspacing="8" style="width:100%; margin:0; background:none;"><br />
<br />
<tr><br />
<td style="border:1px solid #cef2e0; background:#f5fffa;"><br />
<table width="100%"><br />
<tr><br />
<td colspan="2"><br />
<h2 style="margin:3px; background:#cef2e0; font-size:120%; font-weight:bold; border:1px solid #a3bfb1; text-align:left; color:#000; padding:0.2em 0.4em;">Release 7.1.1 Documentation</h2><br />
</td><br />
</tr><br />
<br />
<tr valign="top"><br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">API Documentation</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
* [[r7.1.1:Binary Tree (add-only, unbalanced)|Binary Tree (add-only, unbalanced)]]<br />
* [[r7.1.1:Freelist|Freelist]]<br />
* [[r7.1.1:Hash (add-only)|Hash (add-only)]]<br />
* [[r7.1.1:Misc|Misc]]<br />
* [[r7.1.1:PRNG|PRNG]]<br />
* [[r7.1.1:List (add-only, singly-linked, ordered)|List (add-only, singly-linked, ordered)]]<br />
* [[r7.1.1:List (add-only, singly-linked, unordered)|List (add-only, singly-linked, unordered)]]<br />
* [[r7.1.1:Queue (bounded, many producer, many consumer)|Queue (bounded, many producer, many consumer)]]<br />
* [[r7.1.1:Queue (bounded, single producer, single consumer)|Queue (bounded, single producer, single consumer)]]<br />
* [[r7.1.1:Queue (unbounded, many producer, many consumer)|Queue (unbounded, many producer, many consumer)]]<br />
* [[r7.1.1:Ringbuffer|Ringbuffer]]<br />
* [[r7.1.1:Stack|Stack]]<br />
<br />
</div><br />
<br />
</td><br />
<br />
<td style="width:50%; border:1px solid #cedff2; background:#f5faff;"><br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Misc</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
liblfds consists of the library itself, a benchmark programme and a test programme.<br />
<br />
* [[r7.1.1:Introduction|Introduction]]<br />
* [[r7.1.1:Release Note / Upgrading|Release Note / Upgrading]]<br />
* [[r7.1.1:Building Guide (liblfds)|Building Guide (liblfds)]]<br />
* [[r7.1.1:Building Guide (testing)|Building Guide (testing)]]<br />
* [[r7.1.1:Building Guide (benchmarking)|Building Guide (benchmarking)]]<br />
* [[r7.1.1:Usage Guide (liblfds)|Usage Guide (liblfds)]]<br />
* [[r7.1.1:Usage Guide (testing)|Usage Guide (testing)]]<br />
* [[r7.1.1:Usage Guide (benchmarking)|Usage Guide (benchmarking)]]<br />
* [[r7.1.1:Known Issues|Known Issues]] <small>(18th Feburary 2017)</small><br />
<br />
</div><br />
<br />
<h2 style="margin:3px; background:#cedff2; font-size:120%; font-weight:bold; border:1px solid #a3b0bf; text-align:left; color:#000; padding:0.2em 0.4em;">Porting</h2><br />
<br />
<div style="padding:2px 5px"><br />
<br />
Windows and Linux are supported out of the box, for both user-mode and kernel-mode.<br />
<br />
* [[r7.1.1:Porting Guide (liblfds)|Porting Guide (liblfds)]]<br />
* [[r7.1.1:Porting Guide (testing)|Porting Guide (testing)]]<br />
* [[r7.1.1:Porting Guide (benchmarking)|Porting Guide (benchmarking)]]<br />
<br />
</div><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
</td><br />
</tr><br />
</table><br />
<br />
__NOTOC__</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Release_Note_/_Upgrading&diff=1178r7.1.1:Release Note / Upgrading2017-02-17T22:07:36Z<p>Admin: /* liblfds */</p>
<hr />
<div>{{DISPLAYTITLE:Release Note / Upgrading}}<br />
==Introduction==<br />
Release 7.1.1 is a bugfix release in terms of upgrading from 7.1.0. Only the names have changed, from "710" to "711".<br />
<br />
==Upgrade Paths==<br />
It is not possible to upgrade from 6.x.x to 7.x.x. Code has to be rewritten. However, 6.0.1 and 6.1.1 can be compiled and linked into the same code base as 7.x.x, so existing code does not need to be migrated.<br />
<br />
Upgrading from 7.0.0 to 7.1.1 involves accomodating the API name change for the singly-linked ordered list and the queue, and the change to the freelist init function to accomodate the new elimination array.<br />
<br />
Upgrading from 7.1.0 to 7.1.1 involves a global search and replace for "lfds710" to "lfds711", upper-case and lower-case.<br />
<br />
==User-Visible Changes==<br />
<br />
===liblfds===<br />
* Fixed missing DWCAS abstraction for GCC >= 4.1.2 and GCC < 4.7.3 for Intel.<br />
* Fixed major bug in the unbounded/many/many queue, see [http://www.liblfds.org/wordpress/?p=884]<br />
* Abstraction layer now compiles correctly for MIPS64.<br />
<br />
===libshared===<br />
No changes.<br />
<br />
===libtest===<br />
No changes.<br />
<br />
===libbenchmark===<br />
No changes.<br />
<br />
===test===<br />
No changes.<br />
<br />
===benchmark===<br />
No changes.<br />
<br />
==User-Invisible Changes==<br />
<br />
===liblfds===<br />
No changes.<br />
<br />
===libshared===<br />
No changes.<br />
<br />
===libtest===<br />
No changes.<br />
<br />
===libbenchmark===<br />
No changes.<br />
<br />
===test===<br />
No changes.<br />
<br />
===benchmark===<br />
No changes.<br />
<br />
==Known Issues==<br />
<br />
===liblfds===<br />
No known issues.<br />
<br />
===libshared===<br />
* The Linux kernel abstraction layer port is incomplete.<br />
<br />
===libtest===<br />
No known issues.<br />
<br />
===libbenchmark===<br />
* The Linux kernel abstraction layer port is incomplete.<br />
* The btree test is a bit unfair - it does a bit more work as the number of logical cores increases, so as such, it is underplaying performance for higher core counts.<br />
<br />
===test===<br />
No known issues.<br />
<br />
===benchmark===<br />
No known issues.<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=Next_Release_Status_/_New_Features&diff=925Next Release Status / New Features2017-02-17T22:01:30Z<p>Admin: </p>
<hr />
<div>==Introduction==<br />
A list of new features present in the next release.<br />
<br />
==New Features==<br />
* 7th June 2016 - fixed missing LFDS720_PAL_ATOMIC_DWCAS macro for GCC >= 4.1.2 to GCC < 4.7.3.<br />
* 7th June 2016 - first pass at ARM64 support.<br />
* 10th June 2016 - new data structure, unbounded single producer single consumer queue<br />
* 10th June 2016 - libtest is *almost* now bare C89 (one use of bsearch and one use of qsort)<br />
* 10th June 2016 - now have an x86 Windows XP VM, for running test and benchmark<br />
* 1st August 2016 - IA64 support on Windows for DWCAS data structures (freelist, stack, ringbuffer, queue (unbounded, many, many))<br />
* 3rd August 2016 - SMR back in, along with SMR freelist, queue (unbounded, many, many) and stack<br />
* 8th October 2016 - ARM64 support for GCC 4.6.0 and later<br />
* 10th October 2016 - freelist and stack support singlethreaded (non-atomic) operations<br />
* 1st December 2016 - added unbounded, single/single queue<br />
* 1st December 2016 - added epoch based garbage collection<br />
* 1st January 2017 - added hazard pointer based garbage collection<br />
<br />
==In Progress=<br />
* 1th Feb 2017 - adding ordered singly-linked list</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(testing)&diff=1225r7.1.1:Usage Guide (testing)2017-02-17T20:16:55Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (testing)}}<br />
==Introducton==<br />
Testing functionality is implemented in a library, ''libtest'', which offers a small and simple API, so it can be used on arbitrary platforms. Using the ''libtest'' library also requires using one API exposed by the ''libshared'' library, for memory management. Finally, a convenience thin command line veneer, ''test'', is provided, which is used from the command line to run the test suite and see the results.<br />
<br />
As such, usage is either the use of the ''libtest'' API (and also the ''libshared'' API, for memory management), or the use of the command line ''test'' programme.<br />
<br />
===API Usage Guides===<br />
* [[r7.1.1:Usage Guide (libshared)|Usage Guide (libshared)]]<br />
* [[r7.1.1:Usage Guide (libtest)|Usage Guide (libtest)]]<br />
<br />
===Command Line Usage Guide===<br />
* [[r7.1.1:Usage Guide (test)|Usage Guide (test)]]<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(test)&diff=1224r7.1.1:Usage Guide (test)2017-02-17T20:16:55Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (test)}}<br />
==Introduction==<br />
The ''test'' programme is a thin command line veneer to ''libtest''. It runs a series of tests, first for the porting abstraction layer (and so can be used to validate any new ports) and then upon each data structure, and stops running on any test failure or error of any kind.<br />
<br />
Testing lock-free code is problematic since a large class of bugs are race conditions, which are impossible or nearly impossible to methodically reproduce. As such testing consists in part of simple API tests to enure every function does what it is supposed to do at least when in the absence of race conditions, but in the main of best-effort attempts to provoke race conditions and detect them.<br />
<br />
Make sure you run the release build - the debug build does so much extra work that it misses race conditions the release build will pick up on.<br />
<br />
==Running==<br />
The test programme is run from the command line. Change directory into ''test_and_benchmark/test/bin/'' and type;<br />
<br />
test -r<br />
<br />
The full command line (which is printed by ''-h'' or by running with no arguments) is as follows;<br />
<br />
test -e -h -i [n] -m [n] -r -v<br />
-e : empirically determine Exclusive Reservation Granule<br />
(currently supports only ARM32)<br />
-h : help<br />
-i [n] : number of iterations (default : 1)<br />
-m [n] : memory for tests, in mb (default : 512)<br />
-r : run (causes test to run; present so no args gives help)<br />
-v : version<br />
<br />
===Arguments===<br />
'''-e''' : Attempts to determine the Exclusive Reservation Granule. See [[r7.1.1:Usage Guide (liblfds)#Exclusive Reservation Granule (ARM, POWERPC)|Exclusive Reservation Granule (ARM, POWERPC)]] for details; this is only needed on ARM and POWERPC, and only currently supported for ARM32.<br />
<br />
'''-h''' : Show help.<br />
<br />
'''-i [n]''' : The test programme will loop ''n'' times. Any error (e.e. allocation failure) or test failure will cause the test programme to print and error and exit completely, rather than merely abort the current iteration.<br />
<br />
'''-m [n]''' : There are a large number of tests. Mainly these tests run one thread per logical core, but there are a few API tests and a few single-threaded tests. Each test being run typically allocates a large number of data structure elements with which to perform the test. The value supplied to the ''-m'' argument is the amount of memory to be used for element allocation, in megabytes. The code does not properly or consistently check for memory exhaustion; a safe absolute minimum is 4mb, 64mb is a reasonable minimum for testing, and anything more than 1gb gives no advantage.<br />
<br />
'''-r''' : If run with no arguments, the help text is displayed. As such, an argument is needed to inform the test programme that it is in fact to run tests, which is why the "-r" argument exists.<br />
<br />
'''-v''' : Shows the build version, like so;<br />
<br />
test 7.1.1 (release, user-mode)<br />
libshared 7.1.1 (release, Linux, user-mode)<br />
libtest 7.1.1 (release, Linux, user-mode)<br />
liblfds 7.1.1 (release, Linux, user-mode, x64, GCC >= 4.7.3)<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (testing)|Usage Guide (testing)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(libtest)&diff=1223r7.1.1:Usage Guide (libtest)2017-02-17T20:16:55Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (libtest)}}<br />
==Introduction==<br />
This page describes how to use the ''libtest'' library.<br />
<br />
The library implements a great deal of functionality, almost all of which is used and only used by the ''libtest'' library itself. From the point of view of an external caller to its API, there are only a few functions; a couple to init and run the entire test suite, a few more to handle the results from a test run, and one or two miscellanous functions.<br />
<br />
==Usage==<br />
To use ''libtest'', include the header file ''libtest.h'' and link as normal to the library in your build.<br />
<br />
==Dependencies==<br />
The ''libtest'' libraries depends on the ''libshared'' library and the ''liblfds711'' library.<br />
<br />
==Source Files==<br />
└── test_and_benchmark<br />
└── libtest<br />
├── inc<br />
│ └── libtest<br />
│ ├── libtest_misc.h<br />
│ ├── libtest_results.h<br />
│ └── libtest_testsuite.h<br />
└── src<br />
├── libtest_misc<br />
│ └── libtest_misc_determine_erg.c<br />
├── libtest_results<br />
│ ├── libtest_results_cleanup.c<br />
│ ├── libtest_results_get_result.c<br />
│ ├── libtest_results_init.c<br />
│ └── libtest_results_internal.h<br />
└── libtest_testsuite<br />
├── libtest_testsuite_cleanup.c<br />
├── libtest_testsuite_init.c<br />
├── libtest_testsuite_internal.h<br />
└── libtest_testsuite_run.c<br />
<br />
This is a small subset of the full set of files, and shows only those files used by the publically exposed APIs.<br />
<br />
==Enums==<br />
enum [[r7.1.1:enum lfds711_misc_validity|lfds711_misc_validity]]<br />
enum [[r7.1.1:enum libtest_misc_determine_erg_result|libtest_misc_determine_erg_result]]<br />
enum [[r7.1.1:enum libtest_test_id|libtest_test_id]]<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct libtest_results_state|libtest_results_state]]<br />
struct [[r7.1.1:struct libtest_testsuite_state|libtest_testsuite_state]]<br />
struct [[r7.1.1:struct libshared_memory_state|libshared_memory_state]]<br />
<br />
==Prototypes==<br />
void [[r7.1.1:function libtest_testsuite_init|libtest_testsuite_init]]( struct libtest_testsuite_state *ts,<br />
struct libshared_memory_state *ms,<br />
void (*callback_test_start)(char *test_name),<br />
void (*callback_test_finish)(char *result) );<br />
void [[r7.1.1:function libtest_testsuite_cleanup|libtest_testsuite_cleanup]]( struct libtest_testsuite_state *ts );<br />
void [[r7.1.1:function libtest_testsuite_run|libtest_testsuite_run]]( struct libtest_testsuite_state *ts,<br />
struct libtest_results_state *rs );<br />
<br />
void [[r7.1.1:function libtest_results_init|libtest_results_init]]( struct libtest_results_state *rs );<br />
void [[r7.1.1:function libtest_results_cleanup|libtest_results_cleanup]]( struct libtest_results_state *rs );<br />
void [[r7.1.1:function libtest_results_get_result|libtest_results_get_result]]( struct libtest_results_state *rs,<br />
enum libtest_test_id test_id,<br />
enum lfds711_misc_validity *result );<br />
<br />
void [[r7.1.1:function libtest_misc_determine_erg|libtest_misc_determine_erg]]( struct libshared_memory_state *ms,<br />
lfds711_pal_uint_t (*count_array)[10],<br />
enum libtest_misc_determine_erg_result *der,<br />
lfds711_pal_uint_t *erg_length_in_bytes );<br />
<br />
==Overview==<br />
To run the tests, take the following steps;<br />
<br />
# Initialize a ''struct libshared_memory_state'', with enough store (at least 4mb). The test code is not NUMA aware, so no special NUMA-aware allocations are required.<br />
# Initialize a ''struct libtest_results_state''.<br />
# Initialize a ''struct libtest_testsuite'', passing in the ''libshared_memory_state'' initialized earlier.<br />
# Call ''libtest_testsuite_run'', passing in the ''struct libtest_testsuite_state'' and the ''struct libtest_results_state''.<br />
<br />
When ''libtest_testsuite_run'' returns, the ''struct libtest_results_state'' will be populated, and it can be queried with ''libtest_results_get_result''.<br />
<br />
A given initialized ''struct libtest_testsuite'' can be passed any number of times to ''libtest_testsuite_run''. The ''struct libtest_results'' however must be initialized, or a new struct provided, between calls, as this structure only stores the results of a single test run.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (testing)|Usage Guide (testing)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(libshared)&diff=1222r7.1.1:Usage Guide (libshared)2017-02-17T20:16:55Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (libshared)}}<br />
==Introduction==<br />
This page describes how to use the ''libshared'' library.<br />
<br />
The library implements a great deal of functionality, almost all of which is used and only used by other ''liblfds'' components. From the point of view of an external caller to its API, there is in fact only one API, which handles user-allocated memory.<br />
<br />
==Usage==<br />
To use ''libshared'', include the header file ''libshared.h'' and link as normal to the library in your build.<br />
<br />
==Dependencies==<br />
The ''libtest'' libraries depends on the ''liblfds711'' library.<br />
<br />
==Source Files==<br />
└── test_and_benchmark<br />
└── libshared<br />
├── inc<br />
│ ├── libshared<br />
│ │ └── libshared_memory.h<br />
└── src<br />
└── libshared_memory<br />
├── libshared_memory_add.c<br />
├── libshared_memory_cleanup.c<br />
└── libshared_memory_init.c<br />
<br />
This is a small subset of the full set of files, and shows only those files used by the publically exposed APIs.<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct libshared_memory_state|libshared_memory_state]];<br />
<br />
==Prototypes==<br />
void [[r7.1.1:function libshared_memory_init|libshared_memory_init]]( struct libshared_memory_state *ms );<br />
void [[r7.1.1:function libshared_memory_cleanup|libshared_memory_cleanup]]( struct libshared_memory_state *ms,<br />
void (*memory_cleanup_callback)(enum flag known_numa_node_flag,<br />
void *store,<br />
lfds711_pal_uint_t size) );<br />
<br />
void [[r7.1.1:function libshared_memory_add_memory|libshared_memory_add_memory]]( struct libshared_memory_state *ms,<br />
void *memory,<br />
lfds711_pal_uint_t memory_size_in_bytes );<br />
void [[r7.1.1:function libshared_memory_add_memory_from_numa_node|libshared_memory_add_memory_from_numa_node]]( struct libshared_memory_state *ms,<br />
lfds711_pal_uint_t numa_node_id,<br />
void *memory,<br />
lfds711_pal_uint_t memory_size_in_bytes );<br />
<br />
==Overview==<br />
All ''liblfds'' libraries are written such that they perform no memory allocations. This is straightforward for ''liblfds'', where the user passes in state structures and so on, but it is problematic for ''libtest'' and ''libbenchmark'' as the store they require varies depending on the number of logical cores in the system, where that number cannot be known in advance, and where the work being done is complex enough that it is impractical to require the user to pass in the required store to functions - rather, a generic method is needed, where the libraries can in effect perform dynamic memory allocation.<br />
<br />
This is the purpose of the ''libshared_memory'' API. The caller of ''libtest'' or ''libbenchmark'' functionality initializes a ''struct libshared_memory_state'', performs some memory allocation by whatever means are available and adds the pointer to that memory and its size in bytes to the memory state. This memory state is then passed into such function in ''libtest'' or ''libbenchmark'' which require it, which in turn draw upon the memory so provided for dynamic allocations.<br />
<br />
The ''libtest'' library is not currently NUMA aware - it simply runs one thread per logical core and allocates everything from the allocation with the most free space at the time of the allocation request. The ''libbenchmark'' library ''is'' NUMA aware and on NUMA systems in fact ''requires'' an allocation from every NUMA node in the system.<br />
<br />
On SMP systems, or on NUMA systems but where a non-NUMA aware allocator is used (e.g. ''malloc'' rather than say ''numa_alloc_onnode'') memory is added by the ''libshared_memory_add_memory'' function. On NUMA systems, memory is added with the ''libshared_memory_add_memory_from_numa_node'' function. Any number of allocations from any number of nodes (or from the non-NUMA aware allocators) can be provided, although there's no obvious use case for this, since normal usage is to initialize and allocate per-NUMA node and then call a ''libtest'' or ''libenchmark'' function.<br />
<br />
The ''libbenchmark_topology'' API offers an iterator API, which permits easy iteration over the NUMA nodes in a system, saving the caller the trouble of having to enumerate the processor/memory topology. Note that initializing a topology state requires an initialized and populated memory state; however, this state is not NUMA sensitive, and so it can be allocated using malloc and then, once obtained, a second memory state can be populated with per-NUMA node allocations.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (benchmarking)|Usage Guide (benchmarking)]]<br />
* [[r7.1.1:Usage Guide (testing)|Usage Guide (testing)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(libbenchmark)&diff=1220r7.1.1:Usage Guide (libbenchmark)2017-02-17T20:16:55Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (libbenchmark)}}<br />
==Introduction==<br />
This page describes how to use the ''libbenchmark'' library.<br />
<br />
The library implements a great deal of functionality, almost all of which is used and only used by the ''libbenchmark'' library itself. From the point of view of an external caller to its API, there are only a few functions; a couple to init and run the entire benchmark suite, a few more to handle the results from a benchmark run and one or two miscellanous functions.<br />
<br />
==Usage==<br />
To use ''libbenchmark'', include the header file ''libbenchmark.h'' and link as normal to the library in your build.<br />
<br />
==Dependencies==<br />
The ''libbenchmark'' libraries depends on the ''libshared'' library and the ''liblfds711'' library.<br />
<br />
==Source Files==<br />
└── test_and_benchmark<br />
└── libbenchmark<br />
├── inc<br />
│ └── libbenchmark<br />
│ ├── libbenchmark_benchmarksuite.h<br />
│ ├── libbenchmark_enums.h<br />
│ ├── libbenchmark_gnuplot.h<br />
│ ├── libbenchmark_results.h<br />
│ ├── libbenchmark_topology.h<br />
│ └── libbenchmark_topology_node.h<br />
└── src<br />
├── libbenchmark_benchmarksuite<br />
│ ├── libbenchmark_benchmarksuite_cleanup.c<br />
│ ├── libbenchmark_benchmarksuite_gnuplot.c<br />
│ ├── libbenchmark_benchmarksuite_init.c<br />
│ ├── libbenchmark_benchmarksuite_internal.h<br />
│ └── libbenchmark_benchmarksuite_run.c<br />
├── libbenchmark_results<br />
│ ├── libbenchmark_results_cleanup.c<br />
│ ├── libbenchmark_results_get_result.c<br />
│ ├── libbenchmark_results_init.c<br />
│ └── libbenchmark_results_internal.h<br />
├── libbenchmark_topology<br />
│ ├── libbenchmark_topology_cleanup.c<br />
│ ├── libbenchmark_topology_init.c<br />
│ ├── libbenchmark_topology_internal.h<br />
│ ├── libbenchmark_topology_numa.c<br />
│ └── libbenchmark_topology_lpsets.c<br />
└── libbenchmark_topology_node<br />
├── libbenchmark_topology_node_cleanup.c<br />
└── libbenchmark_topology_node_init.c<br />
<br />
This is a small subset of the full set of files, and shows only those files used by the publically exposed APIs.<br />
<br />
==Defines==<br />
#define [[r7.1.1:define LIBBENCHMARK_BENCHMARKSUITE_OPTION_DURATION|LIBBENCHMARK_BENCHMARKSUITE_OPTION_DURATION]]<br />
<br />
==Enums==<br />
enum [[r7.1.1:enum libbenchmark_benchmark_id|libbenchmark_benchmark_id]];<br />
enum [[r7.1.1:enum libbenchmark_datastructure_id|libbenchmark_datastructure_id]];<br />
enum [[r7.1.1:enum libbenchmark_lock_id|libbenchmark_lock_id]];<br />
enum [[r7.1.1:enum libbenchmark_topology_node_type|libbenchmark_topology_node_type]];<br />
enum [[r7.1.1:enum libbenchmark_topology_numa_mode|libbenchmark_topology_numa_mode]];<br />
<br />
==Opaque Structures==<br />
struct [[r7.1.1:struct lfds711_list_aso_element|lfds711_list_aso_element]];<br />
struct [[r7.1.1:struct lfds711_list_aso_state|lfds711_list_aso_state]];<br />
struct [[r7.1.1:struct lfds711_list_asu_state|lfds711_list_asu_state]];<br />
struct [[r7.1.1:struct libbenchmark_gnuplot_options|libbenchmark_gnuplot_options]];<br />
struct [[r7.1.1:struct libbenchmark_results_state|libbenchmark_results_state]];<br />
struct [[r7.1.1:struct libbenchmark_benchmarksuite_state|libbenchmark_benchmarksuite_state]];<br />
struct [[r7.1.1:struct libbenchmark_topology_state|libbenchmark_topology_state]];<br />
struct [[r7.1.1:struct libbenchmark_topology_node_state|libbenchmark_topology_node_state]];<br />
struct [[r7.1.1:struct libshared_memory_state|libshared_memory_state]];<br />
<br />
==Macros==<br />
#define [[r7.1.1:macro LIBBENCHMARK_TOPOLOGY_NODE_SET_TYPE|LIBBENCHMARK_TOPOLOGY_NODE_SET_TYPE]]( tns, node_type )<br />
#define [[r7.1.1:macro LIBBENCHMARK_TOPOLOGY_NODE_SET_LOGICAL_PROCESSOR_NUMBER|LIBBENCHMARK_TOPOLOGY_NODE_SET_LOGICAL_PROCESSOR_NUMBER]]( tns, processor_number )<br />
#define [[r7.1.1:macro LIBBENCHMARK_TOPOLOGY_NODE_SET_WINDOWS_GROUP_NUMBER|LIBBENCHMARK_TOPOLOGY_NODE_SET_WINDOWS_GROUP_NUMBER]]( tns, win_group_number )<br />
#define [[r7.1.1:macro LIBBENCHMARK_TOPOLOGY_NODE_UNSET_WINDOWS_GROUP_NUMBER|LIBBENCHMARK_TOPOLOGY_NODE_UNSET_WINDOWS_GROUP_NUMBER]]( tns )<br />
<br />
#define [[r7.1.1:macro LIBBENCHMARK_GNUPLOT_OPTIONS_INIT|LIBBENCHMARK_GNUPLOT_OPTIONS_INIT]]( gpo )<br />
#define [[r7.1.1:macro LIBBENCHMARK_GNUPLOT_OPTIONS_SET_Y_AXIS_SCALE_TYPE_LOGARITHMIC|LIBBENCHMARK_GNUPLOT_OPTIONS_SET_Y_AXIS_SCALE_TYPE_LOGARITHMIC]]( gpo )<br />
#define [[r7.1.1:macro LIBBENCHMARK_GNUPLOT_OPTIONS_SET_WIDTH_IN_PIXELS|LIBBENCHMARK_GNUPLOT_OPTIONS_SET_WIDTH_IN_PIXELS]]( gpo, wip )<br />
#define [[r7.1.1:macro LIBBENCHMARK_GNUPLOT_OPTIONS_SET_HEIGHT_IN_PIXELS|LIBBENCHMARK_GNUPLOT_OPTIONS_SET_HEIGHT_IN_PIXELS]]( gpo, wip )<br />
<br />
==Prototypes==<br />
int [[r7.1.1:function libbenchmark_topology_init|libbenchmark_topology_init]]( struct libbenchmark_topology_state *ts,<br />
struct libshared_memory_state *ms );<br />
void [[r7.1.1:function libbenchmark_topology_cleanup|libbenchmark_topology_cleanup]]( struct libbenchmark_topology_state *ts );<br />
<br />
void [[r7.1.1:function libbenchmark_topology_generate_deduplicated_logical_processor_sets|libbenchmark_topology_generate_deduplicated_logical_processor_sets]]( struct libbenchmark_topology_state *ts,<br />
struct libshared_memory_state *ms,<br />
struct lfds711_list_asu_state *lp_sets );<br />
void [[r7.1.1:function libbenchmark_topology_generate_numa_modes_list|libbenchmark_topology_generate_numa_modes_list]]( struct libbenchmark_topology_state *ts,<br />
enum libbenchmark_topology_numa_mode numa_mode,<br />
struct libshared_memory_state *ms,<br />
struct lfds711_list_asu_state *numa_modes_list );<br />
<br />
void [[r7.1.1:function libbenchmark_topology_node_init|libbenchmark_topology_node_init]]( struct libbenchmark_topology_node_state *tns );<br />
void [[r7.1.1:function libbenchmark_topology_node_cleanup|libbenchmark_topology_node_cleanup]]( struct libbenchmark_topology_node_state *tns,<br />
void (*element_cleanup_callback)(struct lfds711_list_aso_state *lasos,<br />
struct lfds711_list_aso_element *lasoe) );<br />
<br />
void [[r7.1.1:function libbenchmark_results_init|libbenchmark_results_init]]( struct libbenchmark_results_state *rs,<br />
struct libshared_memory_state *ms );<br />
void [[r7.1.1:function libbenchmark_results_cleanup|libbenchmark_results_cleanup]]( struct libbenchmark_results_state *rs );<br />
int [[r7.1.1:function libbenchmark_results_get_result|libbenchmark_results_get_result]]( struct libbenchmark_results_state *rs,<br />
enum libbenchmark_datastructure_id datastructure_id,<br />
enum libbenchmark_benchmark_id benchmark_id,<br />
enum libbenchmark_lock_id lock_id,<br />
enum libbenchmark_topology_numa_mode numa_mode,<br />
struct lfds711_list_aso_state *lpset,<br />
struct libbenchmark_topology_node_state *tns,<br />
lfds711_pal_uint_t *result );<br />
<br />
void [[r7.1.1:function libbenchmark_benchmarksuite_init|libbenchmark_benchmarksuite_init]]( struct libbenchmark_benchmarksuite_state *bss,<br />
struct libbenchmark_topology_state *ts,<br />
struct libshared_memory_state *ms,<br />
enum libbenchmark_topology_numa_mode numa_mode,<br />
lfds711_pal_uint_t options_bitmask,<br />
lfds711_pal_uint_t benchmark_duration_in_seconds );<br />
void [[r7.1.1:function libbenchmark_benchmarksuite_cleanup|libbenchmark_benchmarksuite_cleanup]]( struct libbenchmark_benchmarksuite_state *bss );<br />
void [[r7.1.1:function libbenchmark_benchmarksuite_run|libbenchmark_benchmarksuite_run]]( struct libbenchmark_benchmarksuite_state *bss,<br />
struct libbenchmark_results_state *rs );<br />
void [[r7.1.1:function libbenchmark_benchmarksuite_get_list_of_gnuplot_strings|libbenchmark_benchmarksuite_get_list_of_gnuplot_strings]]( struct libbenchmark_benchmarksuite_state *bss,<br />
struct libbenchmark_results_state *rs,<br />
char *gnuplot_system_string,<br />
struct libbenchmark_gnuplot_options *gpo,<br />
struct lfds711_list_asu_state *list_of_gnuplot_strings );<br />
<br />
==Overview==<br />
It has become apparent from creating this page that the API interface to benchmarking is too complicated. The API to run the benchmarks and get hold of the results is actually simple enough - two init functions (one for the benchmark and one for the results) and then a function to run the benchmarks. The problem come when offering APIs to query the results.<br />
<br />
There are many data structures, each of which can have many benchmarks, where each benchmark is run both for the ''liblfds'' lock-free version and then for the full range of system provided locking mechanisms, where each run of the benchmark for a given lock type runs over many combinations of logical cores, where for every combination a result is stored for each logical processor; and all of this on a NUMA system with more than one NUMA node is run twice, once NUMA aware and once not, to show how much difference this makes to performance.<br />
<br />
As such, values for all of these parameters must be specified to the function which queries the result state - and this exposes a great deal of complexity and functionality, as can be seen above.<br />
<br />
It will take a day to document this library, and the effort to do so is futile, because it will still be too complex to use. As such, the effort will go instead into simplifying the API. However, this should not delay the release of 7.1.1, so the functions in this library will for now go undocumented.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (benchmarking)|Usage Guide (benchmarking)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(benchmarking)&diff=1219r7.1.1:Usage Guide (benchmarking)2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (benchmarking)}}<br />
==Introducton==<br />
Benchmarking functionality is implemented in a library, ''libbenchmark'', which offers a small and simple API, so it can be used on arbitrary platforms. Using the ''libbenchmark'' library also requires using one API exposed by the ''libshared'' library, for memory management. Finally, a convenience thin command line veneer, ''benchmark'', is provided, which is used from the command line to run the test suite and see the results.<br />
<br />
As such, usage is either the use of the ''libbenchmark'' API (and also the ''libshared'' API, for memory management), or the use of the command line ''benchmark'' programme.<br />
<br />
===API Usage Guides===<br />
* [[r7.1.1:Usage Guide (libshared)|Usage Guide (libshared)]]<br />
* [[r7.1.1:Usage Guide (libbenchmark)|Usage Guide (libbenchmark)]]<br />
<br />
===Command Line Usage Guide===<br />
* [[r7.1.1:Usage Guide (benchmark)|Usage Guide (benchmark)]]<br />
<br />
==See Also==<br />
* [[r7.1.1:Release_7.1.1_Documentation|Release 7.1.1 Documentation]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Usage_Guide_(benchmark)&diff=1218r7.1.1:Usage Guide (benchmark)2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:Usage Guide (benchmark)}}<br />
==Introduction==<br />
The ''benchmark'' programme is a thin command line veneer to ''libbenchmark'', which compares lock-free data structures to their locking counterparts, by implementing locking versions of the data structures in question and running the same benchmark on the lock-free and locking data structures.<br />
<br />
The benchmark code through its abstraction layer knows about the system processor and memory topology, and runs each benchmark over the meaningful combinations of logical cores, to illustrate the behaviour of the system under the various possible distributions of memory and processor load.<br />
<br />
Finally, ''libbenchmark'' can emit gnuplots (tested with gnuplot 4.6).<br />
<br />
==Running==<br />
The benchmark programme is run from the command line. Change directory into ''test_and_benchmark/benchmark/bin/'' and type;<br />
<br />
benchmark -r<br />
<br />
The full command line (which is printed by ''-h'' or by running with no arguments) is as follows;<br />
<br />
benchmark -g [s] -h -l -m [n] -p -r -s [n] -t -v -x [n] -y [n]<br />
-g [s] : emit gnuplots, where [s] is an arbitrary string (in quotes if spaces) describing the system<br />
-h : help (this text you're reading now)<br />
-l : logarithmic gnuplot y-axis (normally linear)<br />
-m [n] : alloc [n] mb RAM for benchmarks, default is 64 (minimum 2 (two))<br />
(user specifies RAM as libbenchmark performs no allocs - rather it is handed a block of memory<br />
on NUMA systems, each node allocates an equal fraction of the total - benchmark knows about<br />
NUMA and does the right things, including NUMA and non-NUMA versions of the benchmarks)<br />
-p : call gnuplot to emit PNGs (requires -g and gnuplot must be on the path)<br />
-r : run (causes benchmarks to run; present so no args gives help)<br />
-s [n] : individual benchmark duration in integer seconds (min 1, duh)<br />
-t : show CPU topology, uses -m (or its default) for amount of RAM to alloc<br />
-v : build and version info<br />
-x [n] : gnuplot width in pixels (in case the computed values are no good)<br />
-y [n] : gnuplot height in pixels (in case the computed values are no good)<br />
<br />
===Arguments===<br />
'''-g [s]''' : This flag causes gnuplots to be emitted once all benchmarks are complete. The gnuplot contains in its filename and in the gnuplot itself an arbitrary string, which is intended to describe the system, i.e. "Core i5" or "Raspberry Pi 2 Model B". This string is mandatory. If the string contains spaces, it must be in quotes.<br />
<br />
'''-h''' : Show help.<br />
<br />
'''-l''' : The gnuplots emitted by ''benchmark'' by default have a linear y-axix. However, there is usually such an enourmous difference in the y-axis values, between one core and many core charts, and between lock-free and locking benchmarks, that most charts end up with extremely short bars, so much so that they are visually almost indistinguishable. To address this problem, this flag instructs ''benchmark'' to emit gnuplots with a logarithmic y-axis.<br />
<br />
'''-m [n]''' : There are a large number of benchmarks. Mainly these benchmarks run one thread per logical core, but there are a few API benchmarks and a few single-threaded benchmarks. Each benchmark being run typically allocates a large number of data structure elements with which to perform the benchmark. The value supplied to the ''-m'' argument is the amount of memory to be used for element allocation, in megabytes. The code does not properly or consistently check for memory exhaustion; a safe absolute minimum is 4mb, 64mb is a reasonable minimum for benchmarking, and anything more than 1gb gives no advantage.<br />
<br />
'''-p''' : A convenience argument, for use when generating gnuplots, which causes ''benchmark'' to actually call the ''gunplot'' binary on the emitted gnuplot files, to generate the gnuplot images.<br />
<br />
'''-r''' : If run with no arguments, the help text is displayed. As such, an argument is needed to inform the benchmark programme that it is in fact to run benchmarks, which is why the "-r" argument exists.<br />
<br />
'''-s [n]''' : Specifies how long benchmarks should run for. This is the time in seconds for each individual benchmark to run, not the total time for the entire set of benchmarks. The minimum value is one second. This value should be '''at least five seconds''', the default, as there is auto-tuning behaviour in ''liblfds'' which needs a bit of time to find optimal values; very short benchmarks will be skewed by fail-safe initial settings inside ''liblfds'' not having had time to reach more sensible values.<br />
<br />
'''-t''' : Display and only display system memory and processor topology, like so;<br />
<br />
R R = Notional system root <br />
N N = NUMA node <br />
S S = Socket (physical package)<br />
L3U LnU = Level n unified cache <br />
P P LnD = Level n data cache <br />
L2U L2U LnI = Level n instruction cache<br />
L1I L1I P = Physical core <br />
L1D L1D nnn = Logical core <br />
003 001 002 000 <br />
<br />
'''-v''' : Shows the build version, like so;<br />
<br />
benchmark 7.1.1 (release, user-mode, NUMA)<br />
libbenchmark 7.1.1 (release, Linux, user-mode)<br />
libshared 7.1.1 (release, Linux, user-mode)<br />
liblfds 7.1.1 (release, Linux, user-mode, x64, GCC >= 4.7.3)<br />
<br />
'''-x [n]''' : Over-rides the default x-axis sizing of the gnuplot, for cases where the value computed by ''benchmark'' isn't any good.<br />
<br />
'''-y [n]''' : Over-rides the default y-axis sizing of the gnuplot, for cases where the value computed by ''benchmark'' isn't any good.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (benchmarking)|Usage Guide (benchmarking)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Typedef_test_pal_thread_state_t&diff=1217r7.1.1:Typedef test pal thread state t2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:typedef test_pal_thread_state_t}}<br />
==Source File==<br />
└───test<br />
└───src<br />
└───porting_abstraction_layer_operating_system.h<br />
<br />
==Typedef==<br />
typedef [type] test_pal_thread_state_t;<br />
<br />
==Optionality==<br />
This typedef is mandatory.<br />
<br />
==Notes==<br />
Threads typically have associated with them both an ID and a handle.<br />
<br />
This typedef is for the handle - i.e. the datum which the OS can wait on for thread termination.<br />
<br />
If we look at the Windows CreateThread function;<br />
<br />
HANDLE WINAPI CreateThread( _In_opt_ LPSECURITY_ATTRIBUTES lpThreadAttributes,<br />
_In_ SIZE_T dwStackSize,<br />
_In_ LPTHREAD_START_ROUTINE lpStartAddress,<br />
_In_opt_ LPVOID lpParameter,<br />
_In_ DWORD dwCreationFlags,<br />
_Out_opt_ LPDWORD lpThreadId );<br />
<br />
We see there is an argument, ''lpThreadId '', which receives the thread ID, but that the function returns a ''HANDLE'', which is the datum used by ''WaitForSingleObject'' to sleep until the thread has terminated.<br />
<br />
==Example==<br />
typedef HANDLE test_pal_thread_state_t;<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (test)|Porting Guide (test)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Typedef_test_pal_thread_return_t&diff=1216r7.1.1:Typedef test pal thread return t2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:typedef test_pal_thread_return_t}}<br />
==Source File==<br />
└───test<br />
└───src<br />
└───porting_abstraction_layer_operating_system.h<br />
<br />
==Typedef==<br />
typedef [type] test_pal_thread_return_t;<br />
<br />
==Optionality==<br />
This typedef is mandatory.<br />
<br />
==Notes==<br />
When a thread function returns, it returns a value to the OS. This typedef is the type of than return value.<br />
<br />
If we look at the Windows thread function prototype;<br />
<br />
DWORD WINAPI ThreadProc( _In_ LPVOID lpParameter );<br />
<br />
We see the return type is ''DWORD''.<br />
<br />
(The ''WINAPI'' part is actually a compiler directive and is handled in the abstraction layer by the ''[[r7.1.1:define TEST_PAL_CALLING_CONVENTION|TEST_PAL_CALLING_CONVENTION]]'' define.)<br />
<br />
==Example==<br />
typedef DWORD test_pal_thread_state_t;<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (test)|Porting Guide (test)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Typedef_libshared_pal_thread_return_t&diff=1215r7.1.1:Typedef libshared pal thread return t2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:typedef libshared_pal_thread_return_t}}<br />
==Source File==<br />
└───test_and_benchmark<br />
└───libshared<br />
└───inc<br />
└───libshared<br />
libshared_porting_abstraction_layer_compiler.h<br />
<br />
==Typedef==<br />
typedef [type] libshared_pal_thread_return_t;<br />
<br />
==Optionality==<br />
This typedef is mandatory.<br />
<br />
==Example==<br />
typedef DWORD test_pal_thread_state_t;<br />
<br />
==Notes==<br />
When a thread function returns, it returns a value to the OS. This typedef is the type of than return value.<br />
<br />
If we look at the Windows thread function prototype;<br />
<br />
DWORD WINAPI ThreadProc( _In_ LPVOID lpParameter );<br />
<br />
We see the return type is ''DWORD''.<br />
<br />
(The ''WINAPI'' part is actually a compiler directive and is handled in the abstraction layer by the ''[[r7.1.1:define LIBSHARED_PAL_THREAD_CALLING_CONVENTION|LIBSHARED_PAL_THREAD_CALLING_CONVENTION]]'' define.)<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (libshared)|Porting Guide (libshared)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Typedef_libshared_pal_thread_handle_t&diff=1214r7.1.1:Typedef libshared pal thread handle t2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:typedef libshared_pal_thread_handle_t}}<br />
==Source File==<br />
└───test_and_benchmark<br />
└───libshared<br />
└───inc<br />
└───libshared<br />
libshared_porting_abstraction_layer_compiler.h<br />
<br />
==Typedef==<br />
typedef [type] test_pal_thread_handle_t;<br />
<br />
==Optionality==<br />
This typedef is mandatory.<br />
<br />
==Example==<br />
typedef HANDLE test_pal_thread_state_t;<br />
<br />
==Notes==<br />
Threads typically have associated with them both an ID and a handle.<br />
<br />
This typedef is for the handle - i.e. the datum which the OS can wait on for thread termination.<br />
<br />
If we look at the Windows CreateThread function;<br />
<br />
HANDLE WINAPI CreateThread( _In_opt_ LPSECURITY_ATTRIBUTES lpThreadAttributes,<br />
_In_ SIZE_T dwStackSize,<br />
_In_ LPTHREAD_START_ROUTINE lpStartAddress,<br />
_In_opt_ LPVOID lpParameter,<br />
_In_ DWORD dwCreationFlags,<br />
_Out_opt_ LPDWORD lpThreadId );<br />
<br />
We see there is an argument, ''lpThreadId '', which receives the thread ID, but that the function returns a ''HANDLE'', which is the datum used by ''WaitForSingleObject'' to sleep until the thread has terminated.<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (libshared)|Porting Guide (libshared)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Typedef_lfds711_pal_uint_t&diff=1213r7.1.1:Typedef lfds711 pal uint t2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:define lfds711_pal_uint_t}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_porting_abstraction_layer_procesor.h<br />
<br />
==Typedef==<br />
typedef [type] lfds711_pal_uint_t;<br />
<br />
==Example==<br />
typedef int long long unsigned lfds711_pal_uint_t;<br />
<br />
==Optionality==<br />
This typedef is mandatory.<br />
<br />
==Notes==<br />
The library needs an unsigned type which is the natural integer length for the platform, so that for example variables used to count the number of elements in a data structure naturally and inherently provide large number ranges on more capable platforms. This type is expected also to be the same length as the type used in atomic operations.<br />
<br />
In the C89 standard, there is no such type. It should be that ''int'' works in this way, but it does not, as with Windows and Linux ''int'' is 32 bit on 64 bit platforms.<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (liblfds)|Porting Guide (liblfds)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Typedef_lfds711_pal_int_t&diff=1212r7.1.1:Typedef lfds711 pal int t2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:define lfds711_pal_int_t}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_porting_abstraction_layer_procesor.h<br />
<br />
==Typedef==<br />
typedef [type] lfds711_pal_int_t;<br />
<br />
==Example==<br />
typedef int long long lfds711_pal_uint_t;<br />
<br />
==Optionality==<br />
This typedef is mandatory.<br />
<br />
==Notes==<br />
The library needs a signed type which is the natural integer length for the platform, so that for example variables used to count the number of elements in a data structure naturally and inherently provide large number ranges on more capable platforms. This type is expected also to be the same length as the type used in atomic operations.<br />
<br />
In the C89 standard, there is no such type. It should be that ''int'' works in this way, but it does not, as with Windows and Linux ''int'' is 32 bit on 64 bit platforms.<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (liblfds)|Porting Guide (liblfds)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_test_pal_logical_processor&diff=1211r7.1.1:Struct test pal logical processor2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct test_pal_logical_processor}}<br />
==Source File==<br />
└───test<br />
└───src<br />
└───internal.h<br />
<br />
==Structure==<br />
struct test_pal_logical_processor<br />
{<br />
lfds711_pal_uint_t<br />
logical_processor_number,<br />
windows_logical_processor_group_number;<br />
<br />
struct lfds711_list_asu_element<br />
lasue;<br />
};<br />
<br />
==Notes==<br />
This structure is used by the ''test'' programme to uniquely identify a logical core, for the purpose of starting threads and pinning them to a given logical core.<br />
<br />
Linux systems have a single ID per logical core, Windows systems have (*rolls eyes*) two unique IDs per logical core, as Windows assigns logical cores into groups of up to 64 cores (which do not exactly map to NUMA nodes, either!), which is why there is the extra field for that group number.<br />
<br />
From the point of view of a user implementing the test porting abstraction layer, this structure is only in use when the user is adding it to a ''liblfds'' linked list, which is why a ''struct lfds711_list_asu_element'' is present.<br />
<br />
==See Also==<br />
* [[r7.1.1:Misc|Misc]]<br />
* ''[[r7.1.1:function test_pal_get_logical_core_ids|test_pal_get_logical_core_ids]]''<br />
* ''[[r7.1.1:function test_pal_thread_start|test_pal_thread_start]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_libtest_testsuite_state&diff=1210r7.1.1:Struct libtest testsuite state2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct libtest_testsuite_state}}<br />
==Source File==<br />
└── test_and_benchmark<br />
└── libtest<br />
└── inc<br />
└── libtest<br />
└── libtest_testsuite.h<br />
<br />
==Opaque Structure==<br />
struct libtest_testsuite_state;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned.<br />
<br />
==Notes==<br />
This structure is the main state used by the ''libtest'' library to run tests.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (libtest)|Usage Guide (libtest)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_libtest_results_state&diff=1209r7.1.1:Struct libtest results state2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct libtest_results_state}}<br />
==Source File==<br />
└── test_and_benchmark<br />
└── libtest<br />
└── inc<br />
└── libtest<br />
└── libtest_results.h<br />
<br />
==Opaque Structure==<br />
struct libtest_results_state;<br />
<br />
==Alignment==<br />
No alignment requirements.<br />
<br />
==Notes==<br />
This structure is the main state used by the ''libtest'' library to store test results.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (libtest)|Usage Guide (libtest)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_libshared_pal_thread_info&diff=1208r7.1.1:Struct libshared pal thread info2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct libshared_pal_thread_info}}<br />
==Source File==<br />
└───test_and_benchmark<br />
└───libshared<br />
└───inc<br />
└───libshared<br />
libtest_porting_abstraction_layer.h<br />
<br />
==Opaque Structure==<br />
struct libshared_pal_thread_info;<br />
<br />
==Alignment==<br />
No alignment requirements.<br />
<br />
==Notes==<br />
This structure contains all the information necessary to start a thread on a specified logcial processor. A set of macros are provided to read this information from the structure.<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (libshared)|Porting Guide (libshared)]]<br />
* [[r7.1.1:macro LIBSHARED_PAL_PTI_GET_LOGICAL_PROCESSOR_NUMBER|LIBSHARED_PAL_PTI_GET_LOGICAL_PROCESSOR_NUMBER]]<br />
* [[r7.1.1:macro LIBSHARED_PAL_PTI_GET_WINDOWS_PROCESSOR_GROUP_NUMBER|LIBSHARED_PAL_PTI_GET_WINDOWS_PROCESSOR_GROUP_NUMBER]]<br />
* [[r7.1.1:macro LIBSHARED_PAL_PTI_GET_NUMA_NODE|LIBSHARED_PAL_PTI_GET_NUMA_NODE]]<br />
* [[r7.1.1:macro LIBSHARED_PAL_PTI_GET_THREAD_FUNCTION|LIBSHARED_PAL_PTI_GET_THREAD_FUNCTION]]<br />
* [[r7.1.1:macro LIBSHARED_PAL_PTI_GET_THREAD_ARGUMENT|LIBSHARED_PAL_PTI_GET_THREAD_ARGUMENT]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_libshared_memory_state&diff=1207r7.1.1:Struct libshared memory state2017-02-17T20:16:54Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct libshared_memory_state}}<br />
==Source File==<br />
└── test_and_benchmark<br />
└── libshared<br />
└── inc<br />
└── libshared<br />
└── libshared_memory.h<br />
<br />
==Opaque Structure==<br />
struct libshared_memory_state;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned.<br />
<br />
==Notes==<br />
This structure is used to manage user-provided memory aloocations. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Usage Guide (libshared)|Usage Guide (libshared)]]</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_libbenchmark_topology_state&diff=1206r7.1.1:Struct libbenchmark topology state2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct libbenchmark_topology_state}}<br />
==Source File==<br />
└── test_and_benchmark<br />
└── libbenchmark<br />
└── inc<br />
└── libbenchmark<br />
└── libbenchmark_topology.h<br />
<br />
==Opaque Structure==<br />
struct libbenchmark_topology_state;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned.<br />
<br />
==Notes==<br />
This structure represents a topology tree.<br />
<br />
Users never themselves allocate this structure, rather, it is presented to their implementation of the abstraction layer function ''libbenchmark_pal_populate_topology''.<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (libbenchmark)|Porting Guide (libbenchmark)]]<br />
* ''[[r7.1.1:function libbenchmark_pal_populate_topology|libbenchmark_pal_populate_topology]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_libbenchmark_topology_node_state&diff=1205r7.1.1:Struct libbenchmark topology node state2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct libbenchmark_topology_node_state}}<br />
==Source File==<br />
└── test_and_benchmark<br />
└── libbenchmark<br />
└── inc<br />
└── libbenchmark<br />
└── libbenchmark_topology_node.h<br />
<br />
==Opaque Structure==<br />
struct libbenchmark_topology_node_state;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ALIGN_SINGLE_POINTER'' aligned.<br />
<br />
==Notes==<br />
This structure represents a topology entity.<br />
<br />
Users never themselves allocate this structure (this is done via a helper API).<br />
<br />
==See Also==<br />
* [[r7.1.1:Porting Guide (libbenchmark)|Porting Guide (libbenchmark)]]<br />
* ''[[r7.1.1:function libbenchmark_pal_populate_topology|libbenchmark_pal_populate_topology]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_lfds711_stack_state&diff=1204r7.1.1:Struct lfds711 stack state2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct lfds711_stack_state}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_stack.h<br />
<br />
==Opaque Structure==<br />
struct lfds711_stack_state;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned.<br />
<br />
==Notes==<br />
This structure represents the state of a stack. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Stack|Stack]]<br />
* ''[[r7.1.1:function lfds711_stack_init_valid_on_current_logical_core|lfds711_stack_init_valid_on_current_logical_core]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_lfds711_stack_element&diff=1203r7.1.1:Struct lfds711 stack element2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct lfds711_stack_element}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_stack.h<br />
<br />
==Opaque Structure==<br />
struct lfds711_stack_element;<br />
<br />
==Alignment==<br />
No alignment requirements.<br />
<br />
==Notes==<br />
This structure represents the state of a stack element. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Stack|Stack]]<br />
* ''[[r7.1.1:function lfds711_stack_push|lfds711_stack_push]]''<br />
* ''[[r7.1.1:function lfds711_stack_pop|lfds711_stack_pop]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_lfds711_ringbuffer_state&diff=1202r7.1.1:Struct lfds711 ringbuffer state2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct lfds711_ringbuffer_state}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_ringbuffer.h<br />
<br />
==Opaque Structure==<br />
struct lfds711_ringbuffer_state;<br />
<br />
==Alignment==<br />
No alignment requirements.<br />
<br />
==Notes==<br />
This structure represents the state of a ringbuffer. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Ringbuffer|Ringbuffer]]<br />
* ''[[r7.1.1:function lfds711_ringbuffer_init_valid_on_current_logical_core|lfds711_ringbuffer_init_valid_on_current_logical_core]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_lfds711_ringbuffer_element&diff=1201r7.1.1:Struct lfds711 ringbuffer element2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct lfds711_ringbuffer_element}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_ringbuffer.h<br />
<br />
==Opaque Structure==<br />
struct lfds711_ringbuffer_element;<br />
<br />
==Alignment==<br />
No alignment requirements.<br />
<br />
==Notes==<br />
This structure represents the state of a ringbuffer element. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Ringbuffer|Ringbuffer]]<br />
* ''[[r7.1.1:function lfds711_ringbuffer_init_valid_on_current_logical_core|lfds711_ringbuffer_init_valid_on_current_logical_core]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_lfds711_queue_umm_state&diff=1200r7.1.1:Struct lfds711 queue umm state2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct lfds711_queue_umm_state}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_queue_umm.h<br />
<br />
==Opaque Structure==<br />
struct lfds711_queue_umm_state;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned.<br />
<br />
==Notes==<br />
This structure represents the state of a queue. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Queue (unbounded, many producer, many consumer)|Queue (unbounded, many producer, many consumer)]]<br />
* ''[[r7.1.1:function lfds711_queue_umm_init_valid_on_current_logical_core|lfds711_queue_umm_init_valid_on_current_logical_core]]''</div>Adminhttps://www.liblfds.org/mediawiki/index.php?title=r7.1.1:Struct_lfds711_queue_umm_element&diff=1199r7.1.1:Struct lfds711 queue umm element2017-02-17T20:16:53Z<p>Admin: 1 revision imported</p>
<hr />
<div>{{DISPLAYTITLE:struct lfds711_queue_umm_element}}<br />
==Source File==<br />
└───liblfds711<br />
└───inc<br />
└───liblfds711<br />
lfds711_queue_umm.h<br />
<br />
==Opaque Structure==<br />
struct lfds711_queue_umm_element;<br />
<br />
==Alignment==<br />
Allocations must be ''LFDS711_PAL_ATOMIC_ISOLATION_IN_BYTES'' aligned.<br />
<br />
==Notes==<br />
This structure represents the state of a queue element. It is published in the public header file so it can be allocated on the stack, embedded in user structures and passed to ''sizeof''. The actual internal implementation is opaque and must not be touched.<br />
<br />
==See Also==<br />
* [[r7.1.1:Queue (unbounded, many producer, many consumer)|Queue (unbounded, many producer, many consumer)]]<br />
* ''[[r7.1.1:function lfds711_queue_umm_enqueue|lfds711_queue_umm_enqueue]]''<br />
* ''[[r7.1.1:function lfds711_queue_umm_dequeue|lfds711_queue_umm_dequeue]]''</div>Admin