Lock Free RingBuffer

Share your advanced PureBasic knowledge/code with the community.
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Lock Free RingBuffer

Post by idle »

Lock Free RingBuffer for PB 6.0 x86/x64 asm and c backend, port of portaudio ring buffer
single producer / consumer threads only.

Tested
Windows x64/ x86 windows and c backend
Linux arm c backend

Code: Select all

;lock free threadsafe RINGBUFFER for single reader writers x86/x64/arm 
;Author Idle, adapted from portaudio ringbuffer
;v1.0

DeclareModule RINGBUFFER 
  
  Structure RingBuffer_Ar 
    e.a[0]   
  EndStructure
  
  Structure RingBuffer 
    stop.i
    bufferSize.i
    writeIndex.i
    readIndex.i
    bigMask.i
    smallMask.i
    elementSizeBytes.i 
    *buffer.Ringbuffer_Ar 
  EndStructure   
  
  Declare  RB_Initialize(*rb.RingBuffer,elementSizeBytes,elementCount) 
  Declare  RB_Free(*rb.RingBuffer)  
  
  Declare  RB_Write(*rb.RingBuffer,*Data,elementCount)
  Declare  RB_Read(*rb.RingBuffer,*Data,elementCount)
       
EndDeclareModule 

Module RINGBUFFER 
  
  Macro _mfence() 
    CompilerIf #PB_Compiler_Backend = #PB_Backend_Asm     
      !mfence 
    CompilerElse 
      CompilerSelect #PB_Compiler_Processor
        CompilerCase #PB_Processor_Arm32; 
          !__sync_synchronize();   
        CompilerCase #PB_Processor_Arm64  
          !__sync_synchronize();  
        Default   
          !__asm__("mfence" ::: "memory"); 
      CompilerEndSelect   
    CompilerEndIf   
  EndMacro 
  
  Macro _sfence()
    CompilerIf #PB_Compiler_Backend = #PB_Backend_Asm  
      !sfence 
    CompilerElse  
      CompilerSelect #PB_Compiler_Processor
        CompilerCase #PB_Processor_Arm32; 
          !__sync_synchronize();   
        CompilerCase #PB_Processor_Arm64  
          !__sync_synchronize();  
        Default   
          !__asm__("sfence" ::: "memory"); 
      CompilerEndSelect   
    CompilerEndIf   
  EndMacro 
  
  Macro _lfence() 
    CompilerIf #PB_Compiler_Backend = #PB_Backend_Asm   
      !lfence
    CompilerElse  
      CompilerSelect #PB_Compiler_Processor
        CompilerCase #PB_Processor_Arm32; 
          !__sync_synchronize();   
        CompilerCase #PB_Processor_Arm64  
          !__sync_synchronize();  
        Default   
          !__asm__("lfence" ::: "memory"); 
      CompilerEndSelect   
    CompilerEndIf    
  EndMacro 
   
  Procedure RB_Initialize(*rb.RingBuffer,elementSizeBytes,elementCount)
    
    If(((elementCount-1) & elementCount) <> 0) ;element count must be power of 2 
      ProcedureReturn -1
    EndIf  
    
    *rb\bufferSize = elementCount
    *rb\buffer = AllocateMemory(elementCount*elementSizeBytes)  
    *rb\bigMask = (elementCount*2)-1
    *rb\smallMask = (elementCount)-1
    *rb\elementSizeBytes = elementSizeBytes
    
    ProcedureReturn *rb\buffer 
    
  EndProcedure 
  
  Procedure RB_Free(*rb.RingBuffer) 
    
    If *rb 
      If *rb\buffer 
        FreeMemory(*rb\buffer) 
        *rb\buffer = #Null 
      EndIf 
    EndIf
    
  EndProcedure   
     
  Procedure RB_Write(*rb.RingBuffer,*Data,elementCount)
    Protected size1, size2, available
    Protected data1, data2 
       
    available.i =  (*rb\bufferSize - ((*rb\writeIndex - *rb\readIndex) & *rb\bigMask)) 
    
    If elementCount > available 
      elementCount = available
    EndIf   
    
    index = (*rb\writeIndex & *rb\smallMask)
    
    If(index + elementCount) > *rb\bufferSize 
      firstHalf = *rb\bufferSize - index
      data1 = @*rb\buffer\e[index * *rb\elementSizeBytes]
      size1 = firstHalf
      data2 = @*rb\buffer\e[0]
      size2 = elementCount - firstHalf
    Else
      data1 = @*rb\buffer\e[index * *rb\elementSizeBytes]
      size1 = elementCount
      data2 = #Null
      size2 = 0
    EndIf 
    
    If available 
      _mfence() 
    EndIf 
        
    If size2 > 0
      CopyMemory(*Data,data1,size1 * *rb\elementSizeBytes)
      *data + (size1 * *rb\elementSizeBytes)
      CopyMemory(*Data,data2,size2 * *rb\elementSizeBytes)
    Else
      CopyMemory(*Data,data1, size1 * *rb\elementSizeBytes )
    EndIf 
    
    _sfence()
    *rb\writeIndex = (*rb\writeIndex + elementCount) & *rb\bigMask
        
    ProcedureReturn elementCount               
    
  EndProcedure 
  
  Procedure RB_Read(*rb.RingBuffer,*Data,elementCount)
    Protected size1, size2, available 
    Protected data1, data2
        
    available.i = ((*rb\writeIndex - *rb\readIndex) & *rb\bigMask)
    
    If( elementCount > available ) 
      elementCount = available
    EndIf   
    
    index = (*rb\readIndex & *rb\smallMask)
    
    If((index + elementCount) > *rb\bufferSize )
      firstHalf = *rb\bufferSize - index
      datat1 = @*rb\buffer\e[index * *rb\elementSizeBytes]
      size1 = firstHalf
      data2 = @*rb\buffer\e[0]
      size2 = elementCount - firstHalf
    Else
      data1 = @*rb\buffer\e[index * *rb\elementSizeBytes]
      size1 = elementCount
      data2 = 0
      size2 = 0
    EndIf 
    
    If available 
      _lfence() 
    EndIf 
        
    If size2 > 0
      CopyMemory(data1,*data,size1 * *rb\elementSizeBytes )
      *Data + size1 * *rb\elementSizeBytes
      CopyMemory(data2,*Data,size2 * *rb\elementSizeBytes )
    Else
      CopyMemory(data1,*Data,size1 * *rb\elementSizeBytes )
    EndIf 
    
    _mfence()
    *rb\readIndex = (*rb\readIndex + elementCount) & *rb\bigMask
       
    ProcedureReturn  elementCount             
      
  EndProcedure 
  
 EndModule  
  
  CompilerIf #PB_Compiler_IsMainFile   
    
    UseModule RINGBUFFER 
    
    Procedure Producer(*RB.RingBuffer) 
      
      Protected num,ct  
      Dim inputs.f(64) 
      
      Repeat 
        
        For a = 0 To 63
          inputs(a) = ct 
          ct+1 
        Next 
        
        num = RB_Write(*RB,@inputs(0),64) ;write 64 elements to the ring if full it will return 0  
        
        Debug "num write " + Str(num) 
        
        Delay(Random(10))  
        
      Until *RB\stop 
      
    EndProcedure 
    
    
    Procedure Consumer(*RB.RingBuffer) 
      
      et= ElapsedMilliseconds() + 10000
      Dim outputs.f(64) 
      
      Repeat 
        
        num = RB_Read(*RB,@outputs(0),64)  ;read 64 elements off ring if empty it will return 0 
        
        Debug "num read " + Str(num) + " " + StrF(outputs(0),3)      
        
        Delay(Random(10))  
        
      Until ElapsedMilliseconds() > et       
      
      *rb\stop = 1 ;stop buffering  
      
    EndProcedure   
    
    
    Global RB.RingBuffer                  ;decalre a RB              
    RB_Initialize(@RB,SizeOf(float),1024) ;set the size in bytes of elements and the number or elements in the ring buffer must be a power of 2 
                                          ;it is only thread safe for single writer and reader threads 
    t1 = CreateThread(@Producer(),@RB)    ;create writer thread 
    t2 = CreateThread(@consumer(),@RB)    ;create reader thread 
    
    WaitThread(t2) 
    
  CompilerEndIf 
   
 
User avatar
blueb
Addict
Addict
Posts: 1041
Joined: Sat Apr 26, 2003 2:15 pm
Location: Cuernavaca, Mexico

Re: Lock Free RingBuffer

Post by blueb »

Thanks idle,

I was looking for circular buffers, and this is perfect!
- It was too lonely at the top.

System : PB 6.10 Beta 9 (x64) and Win Pro 11 (x64)
Hardware: AMD Ryzen 9 5900X w/64 gigs Ram, AMD RX 6950 XT Graphics w/16gigs Mem
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Lock Free RingBuffer

Post by idle »

blueb wrote: Thu Jul 07, 2022 2:03 pm Thanks idle,

I was looking for circular buffers, and this is perfect!
I've wondered how to do a lock free one for a while, so it was a good find.
User avatar
Mijikai
Addict
Addict
Posts: 1360
Joined: Sun Sep 11, 2016 2:17 pm

Re: Lock Free RingBuffer

Post by Mijikai »

Thanks 8)
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Lock Free RingBuffer

Post by idle »

updated to module and replaced the memory fence macros for c backend x86/x64/arm
Mindphazer
Enthusiast
Enthusiast
Posts: 340
Joined: Mon Sep 10, 2012 10:41 am
Location: Savoie

Re: Lock Free RingBuffer

Post by Mindphazer »

I think you should use CompilerCase instead of Case inside the CompilerSelect in your macros
MacBook Pro 14" M1 Pro - 16 Gb - MacOS 14 - Iphone 15 Pro Max - iPad at home
...and unfortunately... Windows at work...
User avatar
idle
Always Here
Always Here
Posts: 5042
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: Lock Free RingBuffer

Post by idle »

Mindphazer wrote: Sat Jul 15, 2023 10:08 am I think you should use CompilerCase instead of Case inside the CompilerSelect in your macros
Thanks well spotted.
Post Reply