rename ring_buffer to ringbuffer and remove previous attempt

8 files changed, 8 insertions, 451 deletions

diff --git a/Makefile b/Makefile
index 79b79ab..38ab176 100644
--- a/Makefile
+++ b/Makefile
@@ -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, &params[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, &params[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, &params[i])) {
-                fprintf(stderr,"Failed to create writer thread[%d]\n",i);
-                exit(1);
-            }
-            if (pthread_create( &threads[i], NULL, reader_thread, &params[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