diff options
| -rw-r--r-- | Makefile | 15 | ||||
| -rw-r--r-- | lf_ring_buffer.c | 174 | ||||
| -rw-r--r-- | lf_ring_buffer.h | 73 | ||||
| -rw-r--r-- | lf_ring_buffer_test.c | 191 | ||||
| -rw-r--r-- | lf_ringbuffer.c (renamed from lf_ring_buffer2.c) | 2 | ||||
| -rw-r--r-- | lf_ringbuffer.h (renamed from lf_ring_buffer2.h) | 2 | ||||
| -rw-r--r-- | lf_ringbuffer_data.h (renamed from lf_ring_buffer_data.h) | 0 | ||||
| -rw-r--r-- | lf_ringbuffer_test.c (renamed from lf_ring_buffer_test2.c) | 2 |
8 files changed, 8 insertions, 451 deletions
@@ -3,7 +3,7 @@ CC = gcc STD = _GNU_SOURCE CFLAGS = -DDEBUG -BIN = cas container_of lock_free_queue_test lf_fifo_test lf_ring_buffer_test lf_ring_buffer_test2 +BIN = cas container_of lock_free_queue_test lf_fifo_test lf_ringbuffer_test .c.o: $(CC) -march=i686 -O2 -c -Wall -I. $(CFLAGS) -D$(STD) $< @@ -30,15 +30,10 @@ lf_fifo_test.o: lf_fifo_test.c lf_fifo_test: lf_fifo.o lf_fifo_test.o $(CC) lf_fifo.o lf_fifo_test.o -o lf_fifo_test -lf_ring_buffer.o: lf_ring_buffer.h lf_ring_buffer.c lf_ring_buffer_data.h lf_portable_cas.h -lf_ring_buffer_test.o: lf_ring_buffer_test.c -lf_ring_buffer_test: lf_ring_buffer.o lf_ring_buffer_test.o - $(CC) -lrt lf_ring_buffer.o lf_ring_buffer_test.o -o lf_ring_buffer_test - -lf_ring_buffer2.o: lf_ring_buffer2.h lf_ring_buffer2.c lf_ring_buffer_data.h lf_portable_cas.h -lf_ring_buffer_test2.o: lf_ring_buffer_test2.c -lf_ring_buffer_test2: lf_ring_buffer2.o lf_ring_buffer_test2.o - $(CC) -lrt lf_ring_buffer2.o lf_ring_buffer_test2.o -o lf_ring_buffer_test2 +lf_ringbuffer.o: lf_ringbuffer.h lf_ringbuffer.c lf_ringbuffer_data.h lf_portable_cas.h +lf_ringbuffer_test.o: lf_ringbuffer_test.c lf_ringbuffer.h +lf_ringbuffer_test: lf_ringbuffer.o lf_ringbuffer_test.o + $(CC) -lrt lf_ringbuffer.o lf_ringbuffer_test.o -o lf_ringbuffer_test clean: rm -f *~ *.o *.s core $(BIN) diff --git a/lf_ring_buffer.c b/lf_ring_buffer.c deleted file mode 100644 index 606e29a..0000000 --- a/lf_ring_buffer.c +++ /dev/null @@ -1,174 +0,0 @@ -/* - * File : lf_ring_buffer.c - * Author : Jérémy Zurcher <jeremy@asynk.ch> - * Date : 05/01/010 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#include "lf_ring_buffer.h" -#include "lf_portable_cas.h" -#include <stdlib.h> -#include <string.h> -#include <time.h> - -//#define DEBUG_LFRB_KO 1 -//#define DEBUG_LFRB_CAS 1 -//#define DEBUG_LFRB 1 - -#ifdef DEBUG_LFRB - #include <stdio.h> - #define _LOG_KO_( ... ) fprintf(stdout,__VA_ARGS__) - #define _LOG_CAS_( ... ) fprintf(stdout,__VA_ARGS__) -#elif defined DEBUG_LFRB_CAS - #include <stdio.h> - #define _LOG_KO_( ... ) - #define _LOG_CAS_( ... ) fprintf(stdout,__VA_ARGS__) -#elif defined DEBUG_LFRB_KO - #include <stdio.h> - #define _LOG_KO_( ... ) fprintf(stdout,__VA_ARGS__) - #define _LOG_CAS_( ... ) -#else - #define _LOG_KO_( ... ) - #define _LOG_CAS_( ... ) -#endif - -#define BACKOFF_NANO_SLEEP 100000 - -/* initialize an empty lf_ring_buffer struct */ -lf_ring_buffer_t* lf_ring_buffer_create( size_t n_buf ) { - /* alloc ring_buffer struct */ - lf_ring_buffer_t *r = malloc(sizeof(lf_ring_buffer_t)); - if(r==NULL) return NULL; - /* */ - r->buffer = malloc(LFRB_BUFFER_SIZE*n_buf); - if(r->buffer==NULL) { - free(r); - return NULL; - } - memset(r->buffer,0,LFRB_BUFFER_SIZE*n_buf); - r->n_buf = n_buf; - r->read_from = -1; - r->write_to = 0; - return r; -} - -/* destroy an lf_ring_buffer strcture */ -void lf_ring_buffer_destroy( lf_ring_buffer_t *r ) { - free(r->buffer); - free(r); -} - -/* return 1 if is empty */ -int lf_ring_buffer_empty( lf_ring_buffer_t *r ) { return r->read_from==-1; } - -/* write data into the ring buffer */ -int lf_ring_buffer_write( lf_ring_buffer_t *r, void *data, int flags ) { - int write_to, read_from, next; - struct timespec backoff; - int backoff_time = BACKOFF_NANO_SLEEP; - /* reserve a buffer */ - for(;;){ - write_to = r->write_to; - read_from = r->read_from; - if(LFRB_IS_AVAILABLE( r->buffer[write_to] ) ) { - /* read_from==write_to means that the buffer is full and that a writer thread which at first reserved this buffer - * hasn't had enough CPU cycles to call MARK_AS_FILLED - */ - if( read_from!=write_to ) { - next = write_to+1; - if (next==r->n_buf) next=0; - /* what might have happend between IS_AVAILABLE and now : - * - a writter has reserved this buffer => write_to has moved => CAS fails - * - a reader has consumed a buffer => read_from has moved => we've got more space - */ - _LOG_CAS_( "write: CAS %d %d %d\n", r->write_to, write_to, next ); - if( CompareAndSwapInt( &r->write_to, write_to, next ) ) { - /* !!!!!!!!!!!!!! WARNING !!!!!!!!!!!!!!!!! - * - if the ring is empty before this write operation (r->read_from==-1 or latest idx) - * - and n_buf other threads execute this same function before the next CAS is finished - * then, the last thread will : - * - see this buffer as available - * - and see the ring as empty instead of full !!!!! - * so it will ends with two threads writing on this buffer - */ - if(r->read_from==-1) CompareAndSwapInt( &r->read_from, -1, write_to ); - break; - } - } else { - _LOG_KO_("write: ring full %d %d\n",r->read_from,idx); - if(IS_NOT_BLOCKING(flags)) return -1; - backoff.tv_sec = 0; - backoff.tv_nsec = backoff_time; - nanosleep(&backoff,NULL); - } - } else { - _LOG_KO_("write: buffer not available\n"); - if(IS_NOT_BLOCKING(flags)) return -1; - backoff.tv_sec = 0; - backoff.tv_nsec = backoff_time; - nanosleep(&backoff,NULL); - } - backoff_time += BACKOFF_NANO_SLEEP; - } - /* fill this buffer and mark it as filled */ - memcpy( LFRB_DATA_PTR(r->buffer[write_to]), data, LFRB_DATA_SIZE ); - LFRB_MARK_AS_FILLED( r->buffer[write_to] ); - return 0; -} - -/* read data from the ring buffer */ -int lf_ring_buffer_read( lf_ring_buffer_t *r, void *data, int flags ) { - int write_to, read_from, next; - struct timespec backoff; - int backoff_time = BACKOFF_NANO_SLEEP; - for(;;) { - write_to = r->write_to; - read_from = r->read_from; - if( !(LFRB_IS_AVAILABLE( r->buffer[read_from] )) && read_from!=-1 ) { - next = read_from+1; - if (next==r->n_buf) next=0; - /* will do bad things if data dst buffer is too small !! */ - memcpy( data, LFRB_DATA_PTR(r->buffer[read_from]), LFRB_DATA_SIZE ); - _LOG_CAS_( "read: CAS %d %d %d\n", r->read_from, read_from, next ); - if( CompareAndSwapInt( &r->read_from, read_from, next ) ) { - if(r->read_from==r->write_to) { - /* the buffer is empty but writers will see it as full */ - _LOG_CAS_( "read: empty CAS %d %d %d\n", r->read_from, next, -1 ); - CompareAndSwapInt( &r->read_from, next, -1 ); - } - break; - } - } - - _LOG_KO_("read: ring empty\n"); - if(IS_NOT_BLOCKING(flags)) return -1; - backoff.tv_sec = 0; - backoff.tv_nsec = backoff_time; - nanosleep(&backoff,NULL); - backoff_time += BACKOFF_NANO_SLEEP; - } - /* finish the read process */ - LFRB_MARK_AS_READ( r->buffer[read_from] ); - return 0; -} - diff --git a/lf_ring_buffer.h b/lf_ring_buffer.h deleted file mode 100644 index 14a1aec..0000000 --- a/lf_ring_buffer.h +++ /dev/null @@ -1,73 +0,0 @@ -/* - * File : lf_ring_buffer.h - * Author : Jérémy Zurcher <jeremy@asynk.ch> - * Date : 05/01/010 - * License : - * - * Permission is hereby granted, free of charge, to any person obtaining - * a copy of this software and associated documentation files (the - * "Software"), to deal in the Software without restriction, including - * without limitation the rights to use, copy, modify, merge, publish, - * distribute, sublicense, and/or sell copies of the Software, and to - * permit persons to whom the Software is furnished to do so, subject to - * the following conditions: - * - * The above copyright notice and this permission notice shall be - * included in all copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, - * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF - * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND - * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE - * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION - * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION - * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. - * - */ - -#ifndef _LF_RING_BUFFER_H_ -#define _LF_RING_BUFFER_H_ - -# ifdef __cplusplus -extern "C" { -# endif /* __cplusplus */ - -#include <sys/types.h> -#include "lf_ring_buffer_data.h" - -#define LFRB_NO_BLOCK 1 /* if buffer is full, leave instead of try again and again */ -#define IS_NOT_BLOCKING( flags ) ( (flags)&LFRB_NO_BLOCK ) - -typedef struct ring_buffer { - LFRB_BUFFER_TYPE *buffer; /* buffer data */ - size_t n_buf; /* number of buffers */ - int read_from; /* index where to read data from */ - int write_to; /* index where to write data to */ -} lf_ring_buffer_t; - -/* return an initialized lf_ring_buffer_t struct */ -lf_ring_buffer_t* lf_ring_buffer_create( size_t n_buf ); - -/* destroy an lf_ring_buffer_t struct */ -void lf_ring_buffer_destroy( lf_ring_buffer_t *r ); - -/* return 1 if is empty */ -int lf_ring_buffer_empty( lf_ring_buffer_t *r ); - -/* write data into the ring buffer - * return 0 on success - * return -1 if IS_NOT_BLOCKING and buffer is full - */ -int lf_ring_buffer_write( lf_ring_buffer_t *r, void *data, int flags ); - -/* read data from the ring buffer - * return 0 on success - * return -1 if IS_NOT_BLOCKING and buffer is empty - */ -int lf_ring_buffer_read( lf_ring_buffer_t *r, void *data, int flags ); - -# ifdef __cplusplus -} -# endif /* __cplusplus */ - -# endif /* _LF_RING_BUFFER_H_ */ diff --git a/lf_ring_buffer_test.c b/lf_ring_buffer_test.c deleted file mode 100644 index 2f95af1..0000000 --- a/lf_ring_buffer_test.c +++ /dev/null @@ -1,191 +0,0 @@ -#include <pthread.h> -#include <stdio.h> -#include <stdlib.h> -#include <stdint.h> - -#include "lf_ring_buffer.h" - -#define BUFFER_LEN 5000000 - -//static rb_data_t data[BUFFER_LEN][RB_DATA_LEN]; - -static int64_t time_diff(struct timespec *t0, struct timespec *t1) -{ - return ((t1->tv_sec * 1000000000) + t1->tv_nsec) - ((t0->tv_sec * 1000000000) + t0->tv_nsec); -} - -/* -static void print_now(char* s) { - fprintf(stdout,s); - fflush(stdout); -} -*/ - -static void report( char* op, int n, uint64_t dt, int redo ) { - fprintf(stdout,"\t%9d %s operations in %4d [ms] => %7d [us] => %10d [ns]\t >>> %6d [ns/op]\t%4d redone operations\n", - n, op, (int)(dt/1000000), (int)(dt/1000), (int)dt, (int)(dt/n), redo ); -} - -struct thread_params { - lf_ring_buffer_t *ring; - int n; - int flags; - uint64_t dt; -}; - -/* -static void feed_data( int n){ - int i; - for(i=0; i<n; i++){ - sprintf(data[i],"hello world %04d\n",i); - } -} -*/ - -static uint64_t sequential_writes( lf_ring_buffer_t *ring, int n, int flags ) { - int i, redo=0; - rb_data_t data[RB_DATA_LEN]; - struct timespec start, end; - clock_gettime(CLOCK_MONOTONIC, &start); - if(flags==0) { - for(i=0; i<n; i++) lf_ring_buffer_write( ring, data, flags ); - } else { - for(i=0; i<n;) { - if(lf_ring_buffer_write( ring, data, flags )==0) { i++; } else { redo+=1; } - } - } - clock_gettime(CLOCK_MONOTONIC, &end); - report( "write", n, time_diff( &start, &end ), redo ); - return time_diff( &start, &end ); -} - -static uint64_t sequential_reads( lf_ring_buffer_t *ring, int n, int flags ) { - int i,redo=0; - rb_data_t data[RB_DATA_LEN]; - struct timespec start, end; - clock_gettime(CLOCK_MONOTONIC, &start); - if(flags==0) { - for(i=0; i<n; i++) lf_ring_buffer_read( ring, data, flags ); - } else { - for(i=0; i<n;) { - if(lf_ring_buffer_read( ring, data, flags )==0) { i++; } else { redo+=1; } - } - } - clock_gettime(CLOCK_MONOTONIC, &end); - report( "read ", n, time_diff( &start, &end ), redo ); - return time_diff( &start, &end ); -} - -void* writer_thread( void* param ) { - struct thread_params *params = (struct thread_params*)param; - //report( "write", params->n, sequential_writes( params->ring, params->n, params->flags ) ); - params->dt = sequential_writes( params->ring, params->n, params->flags ); - return NULL; -} - -void* reader_thread( void* param ) { - struct thread_params *params = (struct thread_params*)param; - //report( "read ", params->n, sequential_reads( params->ring, params->n, params->flags ) ); - params->dt = sequential_reads( params->ring, params->n, params->flags ); - return NULL; -} - -static void parallel_op( int op, int nt, lf_ring_buffer_t *ring, int n, int flags ) { - int i; - uint64_t dt; - - pthread_t *threads = malloc( sizeof(pthread_t)*nt); - struct thread_params *params = malloc( sizeof(struct thread_params)*nt); - - for(i=0; i<nt; i++) { - params[i].ring = ring; - params[i].n = n/nt; - params[i].flags = flags; - if(op==0) { - if (pthread_create( &threads[i], NULL, writer_thread, ¶ms[i])) { - fprintf(stderr,"Failed to create writer thread[%d]\n",i); - exit(1); - } - } else if(op==1) { - if (pthread_create( &threads[i], NULL, reader_thread, ¶ms[i])) { - fprintf(stderr,"Failed to create reader thread[%d]\n",i); - exit(1); - } - } else { - params[i].n /=2; - if (pthread_create( &threads[i], NULL, writer_thread, ¶ms[i])) { - fprintf(stderr,"Failed to create writer thread[%d]\n",i); - exit(1); - } - if (pthread_create( &threads[i], NULL, reader_thread, ¶ms[i])) { - fprintf(stderr,"Failed to create reader thread[%d]\n",i); - exit(1); - } - } - } - dt = 0; - for(i=0; i<nt; i++) { - pthread_join( threads[i], NULL ); - dt += params[i].dt; - } - dt/=nt; - fprintf(stdout,"\t\t\t Mean : %4d [ms] => %7d [us] => %10d [ns]\t >>> %6d [ns/op]\n",(int)(dt/1000000), (int)(dt/1000), (int)dt, (int)(dt/(n/nt)) ); - /* empty the ring */ - free(threads); - free(params); -} - -int main( int argc, char** argv ) { - - int i; - int b_len = BUFFER_LEN; - lf_ring_buffer_t *ring; - - ring = lf_ring_buffer_create( b_len ); - if(ring==NULL){ - fprintf(stderr,"ERROR : lf_ring_buffer_create( %d );\n",b_len); - exit( EXIT_FAILURE ); - } - - /* - print_now("feed the data ... "); - feed_data(b_len); - printf("done.\n"); - */ - - printf("sequential non blocking write operations ...\n"); - sequential_writes( ring, b_len, 0 ); - printf("sequential non blocking read operations ...\n"); - sequential_reads( ring, b_len, 0 ); - if(!lf_ring_buffer_empty(ring)) { fprintf(stderr,"ring should be empty but is not\n"); exit( EXIT_FAILURE ); } - printf("sequential blocking write operations ...\n"); - sequential_writes( ring, b_len, LFRB_NO_BLOCK ); - printf("sequential blocking read operations ...\n"); - sequential_reads( ring, b_len, LFRB_NO_BLOCK ); - if(!lf_ring_buffer_empty(ring)) { fprintf(stderr,"ring should be empty but is not\n"); exit( EXIT_FAILURE ); } - - for(i=5; i<=100;i*=2) { - printf("%d parallel blocking with backoff inc write operations .... \n",i); - parallel_op( 0, i, ring, b_len, 0 ); - printf("parallel blocking read operations ...\n"); - sequential_reads( ring, b_len, 0 ); - if(!lf_ring_buffer_empty(ring)) { fprintf(stderr,"ring should be empty but is not\n"); exit( EXIT_FAILURE ); } - } - for(i=5; i<=100;i*=2) { - printf("%d parallel non blocking write operations .... \n",i); - parallel_op( 0, i, ring, b_len, LFRB_NO_BLOCK ); - printf("non blocking read operations ...\n"); - sequential_reads( ring, b_len, LFRB_NO_BLOCK ); - if(!lf_ring_buffer_empty(ring)) { fprintf(stderr,"ring should be empty but is not\n"); exit( EXIT_FAILURE ); } - } - for(i=10; i<=100;i*=2) { - printf("%d parallel blocking write and read operations .... \n",i*2); - parallel_op( 3, i, ring, b_len, 0 ); - if(!lf_ring_buffer_empty(ring)) { fprintf(stderr,"ring should be empty but is not\n"); exit( EXIT_FAILURE ); } - } - - lf_ring_buffer_destroy( ring ); - - return EXIT_SUCCESS; -} - diff --git a/lf_ring_buffer2.c b/lf_ringbuffer.c index 4a1a3cd..99b8766 100644 --- a/lf_ring_buffer2.c +++ b/lf_ringbuffer.c @@ -25,7 +25,7 @@ * */ -#include "lf_ring_buffer2.h" +#include "lf_ringbuffer.h" #include "lf_portable_cas.h" #include <stdlib.h> #include <string.h> diff --git a/lf_ring_buffer2.h b/lf_ringbuffer.h index acf9974..2266ba2 100644 --- a/lf_ring_buffer2.h +++ b/lf_ringbuffer.h @@ -33,7 +33,7 @@ extern "C" { # endif /* __cplusplus */ #include <sys/types.h> -#include "lf_ring_buffer_data.h" +#include "lf_ringbuffer_data.h" #define LFRB_NO_BLOCK 1 /* if buffer is full, leave instead of try again and again */ #define IS_NOT_BLOCKING( flags ) ( (flags)&LFRB_NO_BLOCK ) diff --git a/lf_ring_buffer_data.h b/lf_ringbuffer_data.h index 80092d5..80092d5 100644 --- a/lf_ring_buffer_data.h +++ b/lf_ringbuffer_data.h diff --git a/lf_ring_buffer_test2.c b/lf_ringbuffer_test.c index c1288cc..8c41b97 100644 --- a/lf_ring_buffer_test2.c +++ b/lf_ringbuffer_test.c @@ -3,7 +3,7 @@ #include <stdlib.h> #include <stdint.h> -#include "lf_ring_buffer2.h" +#include "lf_ringbuffer.h" #define BUFFER_LEN 65000 |