source: tests/concurrency/lockfree_stack.cfa@ 4b30318b

//
// Cforall Version 1.0.0 Copyright (C) 2022 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// lockfree_stack.cfa -- 
//
// Author           : Peter A. Buhr
// Created On       : Thu May 25 15:36:50 2023
// Last Modified By : Peter A. Buhr
// Last Modified On : Fri Jun  9 14:01:07 2023
// Update Count     : 68
// 

#include <thread.hfa>
#include <atomic.hfa>                                                                   // CASV
#include <fstream.hfa>

struct Node;                                                                                    // forward declaration
union Link {
        struct {                                                                                        // 32/64-bit x 2
                Node * volatile top;                                                    // pointer to stack top
                uintptr_t count;                                                                // count each push
        };
        #if defined( __SIZEOF_INT128__ )
        __int128 atom;                                                                          // gcc, 128-bit integer
        #else
        int64_t atom;
        #endif // __SIZEOF_INT128__
};

struct Node {
        // resource data
        Link next;                                                                                      // pointer to next node/count (resource)
};
struct Stack {
        Link stack;
};

void push( Stack & s, Node & n ) with(s) {
        n.next = stack;                                                                         // atomic assignment unnecessary
        for () {                                                                                        // busy wait
                Link temp{ &n, n.next.count + 1 };
                if ( CASV( s.stack.atom, n.next.atom, temp.atom ) ) break; // attempt to update top node
        }
}

Node * pop( Stack & s ) with(s) {
        Link t = stack;                                                                         // atomic assignment unnecessary
        for () {                                                                                        // busy wait
                if ( t.top == NULL ) return NULL;                               // empty stack ?
                Link temp{ t.top->next.top, t.count };
                if ( CASV( stack.atom, t.atom, temp.atom ) ) return t.top; // attempt to update top node
        }
}
void ?{}( Stack & s ) with(s) { stack.atom = 0; }

Stack stack;                                                                                    // global stack

enum { Times = 2_000_000 };

thread Worker {};
void main( Worker & w ) {
        for ( i; Times ) {
                Node & n = *pop( stack );                                               // pop any node
                assert( &n != NULL );
                n.next.top = 0p;                                                                // scrub fields
                n.next.count = 0;
                //yield( rand() % 3 );
                push( stack, n );                                                               // push it back
        }
}

int main() {
        enum { N = 8 };                                                                         // kernel threads
        processor p[N - 1];                                                                     // add kernel threads

        for ( i; N ) {                                                                          // push N values on stack
                push( stack, *(Node *)new() );                                  // must be 16-byte aligned
        }
        {
                Worker workers[N];                                                              // run test
        }
        for ( i; N ) {                                                                          // pop N nodes from list
                free( pop( stack ) );
        }
        sout | "done";                                                                          // non-empty .expect file
}

// Local Variables: //
// compile-command: "cfa -g -O3 lockfree_stack.cfa" //
// End: //