lfqueue 
Minimize lock-free queue, it's easy to use and easy to read. It's only 150 line code so it is easy to understand, best code for education ever!
Do not use these code in production
Support multiple comsumer and multiple producer at sametime.
| Arch | Build status | Test |
|---|---|---|
| Linux |  |
On testing |
| Windows(msbuild) | Not tested Issue | |
| Windows(Mingw) | Not tested | |
| Windows(MinGW64) | Not tested | |
| Windows(Cygwin) | Not tested | |
| Windows(Cygwin64) | Not tested |
Build Guide
In any gnu toolchain, just type make.
In any visual studio build toolchain, just type msbuild "Visual Stdio\lfqueue.sln" /verbosity:minimal /property:Configuration=Release /property:Platform=x86 or 64bit version msbuild "Visual Stdio\lfqueue.sln" /verbosity:minimal /property:Configuration=Release /property:Platform=x64.
How to use
Just copy past everywhere and use it. If you copy these code into your project.
Next Milestone
- Compile on MACOS ( I do not have MAC, need somebody help!! )
- Compile in kernel module.
- Use lock-free memory manager. (free is very slow in windows)
Example
Sample example
It is an minimize sample code for how to using lfq.
Even if int or long value is valid input data, but you will hard to distinguish empty queue or other error message.
We not suggestion use int or long as queue data type
#include <stdio.h>
#include <stdlib.h>
#include "lfq.h"
int main() {
long ret;
struct lfq_ctx ctx;
lfq_init(&ctx, 0);
lfq_enqueue(&ctx,(void *)1);
lfq_enqueue(&ctx,(void *)3);
lfq_enqueue(&ctx,(void *)5);
lfq_enqueue(&ctx,(void *)8);
lfq_enqueue(&ctx,(void *)4);
lfq_enqueue(&ctx,(void *)6);
while ( (ret = (long)lfq_dequeue(&ctx)) != 0 )
printf("lfq_dequeue %ld\n", ret);
lfq_clean(&ctx);
return 0;
}Advance example
If you want to get best performance with the cost of developing speed, you can control thread_id yourself.
This API only impilement on HP branch
#include <stdio.h>
#include <stdlib.h>
#include "lfq.h"
#define MAX_CONSUMER_THREAD 4
int main() {
long ret;
struct lfq_ctx ctx;
lfq_init(&ctx, MAX_CONSUMER_THREAD);
lfq_enqueue(&ctx,(void *)1);
// The second number is thread id, this thread id should unique between threads.
// And this tid must less than MAX_CONSUMER_THREAD
// In this sample code, this tid must 0, 1, 2, 3.
ret = (long)lfq_dequeue_tid(&ctx, 1);
lfq_clean(&ctx);
return 0;
}API
lfq_init(struct lfq_ctx *ctx, int max_consume_thread)
Init lock-free queue.
Arguments:
- ctx : Lock-free queue handler.
- max_consume_thread : Max consume thread numbers. If this value set to zero, use default value (16).
Return: The lfq_init() functions return zero on success. On error, this functions return negative errno.
lfq_clean(struct lfq_ctx *ctx)
Clean lock-free queue from ctx.
Arguments:
- ctx : Lock-free queue handler.
Return: The lfq_clean() functions return zero on success. On error, this functions return -1.
lfq_enqueue(struct lfq_ctx *ctx, void * data)
Push data into queue.
Arguments:
- ctx : Lock-free queue handler.
- data : User data.
Return: The lfq_clean() functions return zero on success. On error, this functions return negative errno.
lfq_dequeue(struct lfq_ctx *ctx)
Pop data from queue.
Arguments:
- ctx : Lock-free queue handler.
Return: The lfq_clean() functions return zero if empty queue. Return positive pointer. On error, this functions return negative errno.
lfq_dequeue_tid(struct lfq_ctx *ctx, int tid)
Pop data from queue.
Arguments:
- ctx : Lock-free queue handler.
- tid : Unique thread id.
Return: The lfq_dequeue_tid() functions return zero if empty queue. Return positive pointer. On error, this functions return negative errno.
Issues
ENOMEM
This lfqueue do not have size limit, so count your struct yourself.
Can i iterate lfqueue inner struct?
No, iterate inner struct is not threadsafe.
If you do not get segmentation fault because you are iterate lfqueue in single thread.
We should always iterate lfqueue by lfq_enqueue and lfq_dequeue method.
CPU time slice waste? Other thread blocking and waiting for swap?
Enqueue
No, CAS operator not lock. Loser not block and wait winner.
If a thread race win a CAS, other thread will get false and try to retrive next pointer. Because winner already swap tail, so other losers can do next race.
Example:
4 thread race push
1 win Push A, 2 lose, 1 do not have CPU time slice
1 win go out queue, 2 losers race A as tail, 1 race initnode as tail
1 win go out queue, 1 win push B, 1 lose, 1 race A failed because tail not initnode now
So lock-free queue have better performance then lock queue.
Dequeue
We choice Hazard Pointers to reaolve ABA problems. So dequeue is fast as enqueue.
There has many papers to resolve this problem:
- Lock-Free Reference Counting
- ABA-Prevention Tags
- Hazard Pointers Beta
- Fucking stupid head wait Stable
Free memory very slow in Visual studio
Sorry, i have no idea why. Still finding problems in windows.
Contributions
License
WTFPL