Changeset 1098 for sfio/trunk

Show
Ignore:
Timestamp:
08/26/06 08:18:07 (2 years ago)
Author:
rossb
Message:

sfio: renamed grame02_stack grame02_lifo, updated comments

Location:
sfio/trunk/src/lockfree
Files:
3 modified
2 moved

Legend:

Unmodified
Added
Removed

  • sfio/trunk/src/lockfree/BcbTestProject.bpr

    r1094 r1098  
    1515# --------------------------------------------------------------------------- 
    1616PROJECT = BcbTestProject.exe 
    17 OBJFILES = BcbTestProject.obj ms96_queue.obj grame02_stack.obj MessageQueue.obj 
     17OBJFILES = BcbTestProject.obj ms96_queue.obj MessageQueue.obj grame02_lifo.obj 
    1818RESFILES = 
    1919RESDEPEN = $(RESFILES) 

  • sfio/trunk/src/lockfree/BcbTestProject.cpp

    r1094 r1098  
    66 
    77#include "ms96_queue.h" 
    8 #include "grame02_stack.h" 
     8#include "grame02_lifo.h" 
    99#include "MessageQueue.h" 
    1010 
    1111//--------------------------------------------------------------------------- 
    1212USEUNIT("ms96_queue.c"); 
    13 USEUNIT("grame02_stack.c"); 
    1413USEUNIT("MessageQueue.cpp"); 
     14USEUNIT("grame02_lifo.c"); 
    1515//--------------------------------------------------------------------------- 
    1616#pragma argsused 
    … …  
    1919 
    2020    ms96_queue_test(); 
    21     grame02_stack_test(); 
     21    grame02_lifo_test(); 
    2222 
    2323    MessageQueue::Test(); 

  • sfio/trunk/src/lockfree/MessageQueue.cpp

    r1094 r1098  
    55 
    66#include "ms96_queue.h" 
    7 #include "grame02_stack.h" 
     7#include "grame02_lifo.h" 
    88 
    99 
    1010static size_t nodeSize_; 
    11 static grame02_stack_t nodeFreeList_; 
    12 static grame02_stack_t messageFreeList_; 
     11static grame02_lifo_t nodeFreeList_; 
     12static grame02_lifo_t messageFreeList_; 
    1313 
    1414// for now we limit the message size to 64 bytes, all messages occupy the same space. 
    … …  
    2323void Message::InitializeAllocator() 
    2424{ 
    25     nodeSize_ = std::max( sizeof(ms96_queue_node_t), sizeof(grame02_stack_node_t) ); 
     25    nodeSize_ = std::max( sizeof(ms96_queue_node_t), sizeof(grame02_lifo_node_t) ); 
    2626 
    2727 
    28     grame02_stack_initialize( &nodeFreeList_ ); 
    29     grame02_stack_initialize( &messageFreeList_ ); 
     28    grame02_lifo_initialize( &nodeFreeList_ ); 
     29    grame02_lifo_initialize( &messageFreeList_ ); 
    3030} 
    3131 
    … …  
    3333void* AllocateNode() 
    3434{ 
    35     grame02_stack_node_t *node = grame02_stack_pop( &nodeFreeList_ ); 
     35    grame02_lifo_node_t *node = grame02_lifo_pop( &nodeFreeList_ ); 
    3636    if( !node ) 
    37         node = reinterpret_cast<grame02_stack_node_t*>( ::operator new( nodeSize_ ) ); 
     37        node = reinterpret_cast<grame02_lifo_node_t*>( ::operator new( nodeSize_ ) ); 
    3838 
    3939    return node; 
    … …  
    4343void FreeNode( void * node ) 
    4444{ 
    45     grame02_stack_push( &nodeFreeList_, reinterpret_cast<grame02_stack_node_t*>(node) ); 
     45    grame02_lifo_push( &nodeFreeList_, reinterpret_cast<grame02_lifo_node_t*>(node) ); 
    4646} 
    4747 
    … …  
    5959    assert( size <= MAX_MESSAGE_SIZE ); // if you exceed this value you should retune the system... 
    6060     
    61     grame02_stack_node_t *node = grame02_stack_pop( &messageFreeList_ ); 
     61    grame02_lifo_node_t *node = grame02_lifo_pop( &messageFreeList_ ); 
    6262    if( node ){ 
    6363        Message *message = reinterpret_cast<Message*>( node->value ); // pretend we already have a message so we can set the lf node 
    … …  
    6565        return message; 
    6666    }else{ 
    67         node = reinterpret_cast<grame02_stack_node_t*>( AllocateNode() ); 
     67        node = reinterpret_cast<grame02_lifo_node_t*>( AllocateNode() ); 
    6868        Message *message = reinterpret_cast<Message*>( ::operator new( MAX_MESSAGE_SIZE ) ); 
    6969        message->SetLFNode( node ); 
    … …  
    7676{ 
    7777    Message *message = reinterpret_cast<Message*>( p ); // pretend we already have a message so we can set the lf node 
    78     grame02_stack_node_t *node = reinterpret_cast<grame02_stack_node_t*>( message->GetLFNode() ); 
     78    grame02_lifo_node_t *node = reinterpret_cast<grame02_lifo_node_t*>( message->GetLFNode() ); 
    7979    assert( node ); 
    8080 
    8181    node->value = message; 
    82     grame02_stack_push( &messageFreeList_, node ); 
     82    grame02_lifo_push( &messageFreeList_, node ); 
    8383} 
    8484 

  • sfio/trunk/src/lockfree/grame02_lifo.c

    r1095 r1098  
    1 #include "grame02_stack.h" 
     1#include "grame02_lifo.h" 
    22 
    33#include <stdio.h> 
    44#include <stdlib.h> 
    55 
     6/* 
     7fixme: could rename lifo 
     8*/ 
    69 
    7 static int CAS( volatile void *p, volatile void *oldValue, volatile void *newValue ) 
     10 
     11static int CAS32( volatile void *p32, volatile void *oldValue, volatile void *newValue ) 
    812{ 
    913    unsigned char resultFlags; 
    … …  
    1317        mov ebx, newValue 
    1418 
    15         mov esi, p 
     19        mov esi, p32 
    1620         
    1721        lock cmpxchg [esi], ebx 
    … …  
    2630 
    2731 
    28 static int CAS2( volatile grame02_stack_t *p, volatile void *oldPtr, volatile unsigned long oldCount, 
     32static int CAS64( volatile void *p64, volatile void *oldPtr, volatile unsigned long oldCount, 
    2933        void *newPtr, unsigned long newCount ) 
    3034{ 
    … …  
    3842        mov ecx, newCount 
    3943 
    40         mov esi, p 
     44        mov esi, p64 
    4145         
    4246        lock cmpxchg8b [esi] 
    … …  
    5155 
    5256 
    53 LIBLFDS_CALLING_CONVENTION(void) grame02_stack_initialize( grame02_stack_t* stack ) 
     57LIBLFDS_CALLING_CONVENTION(void) grame02_lifo_initialize( grame02_lifo_t* stack ) 
    5458{ 
    55     stack->top = 0; 
     59    stack->top = NULL; 
    5660} 
    5761 
    5862 
    59 LIBLFDS_CALLING_CONVENTION(void) grame02_stack_push( grame02_stack_t* stack, grame02_stack_node_t *node ) 
     63LIBLFDS_CALLING_CONVENTION(void) grame02_lifo_push( grame02_lifo_t* stack, grame02_lifo_node_t *node ) 
    6064{ 
    61 // B1: loop 
     65/* B1: loop                                                                   */ 
    6266    for(;;){ 
    63 // B2:      cl->next = lf->top # set the cell next pointer to top of the lifo 
     67/* B2:  cl->next = lf->top # set the cell next pointer to top of the lifo     */ 
     68 
     69        /* On IA32 the CAS32 below ensures the visibility of stack->top to all 
     70         * other threads. Otherwise we may need a read barrier here to ensure 
     71         * that the current value of stack->top is being fetched. 
     72         * ==> actually not 100% this is true if CAS32 fails, should check 
     73         */ 
     74 
    6475        node->next = stack->top; 
    65 // B3:      if CAS (&lf->top, cl->next, cl) # try to set the top of the lifo to cell 
    66 // B4:          break 
    67 // B5:      endif 
     76         
     77/* B3:  if CAS (&lf->top, cl->next, cl) # try to set the top of 
     78                                        #                    the lifo to cell */ 
     79/* B4:   break                                                                */ 
     80/* B5:  endif                                                                 */ 
    6881 
    69         // on IA32 CAS has full fence semantics, otherwise we would need a write barrier 
    70         // here to ensure that node->next and node->value were stored before the CAS is executed 
    71  
    72         if( CAS( &stack->top, node->next, node ) ) 
     82        /* On IA32 CAS has full fence semantics, otherwise we may need a write 
     83         * barrier here to ensure that node->next and node->value are stored 
     84         * before the CAS is executed. 
     85         */ 
     86          
     87        if( CAS32( &stack->top, node->next, node ) ) 
    7388            break; 
    74 // B6: endloop 
     89/* B6: endloop                                                                */ 
    7590    } 
    7691} 
    7792 
    7893 
    79 LIBLFDS_CALLING_CONVENTION(grame02_stack_node_t*) grame02_stack_pop( grame02_stack_t* stack ) 
     94LIBLFDS_CALLING_CONVENTION(grame02_lifo_node_t*) grame02_lifo_pop( grame02_lifo_t* stack ) 
    8095{ 
    81     grame02_stack_node_t *top, *next; 
     96    grame02_lifo_node_t *top, *next; 
    8297    unsigned long pop_count; 
    83 // SC1: loop 
     98/* SC1: loop                                                                  */ 
    8499    for(;;){ 
    85 // SC2:     head = lf->top # get the top cell of the lifo 
    86 // SC2:     oc = lf->ocount # get the pop operations count 
    87         top = (grame02_stack_node_t*)stack->top; 
     100 
     101        /* On some architectures a read barrier may be necessary here to ensure 
     102         * that fresh values are being read for stack->top and stack->pop_count 
     103         * and also for top->value (because we return top below and value needs 
     104         * to be present for the client to use it). 
     105         */ 
     106 
     107/* SC2:     head = lf->top # get the top cell of the lifo                     */ 
     108/* SC2:     oc = lf->ocount # get the pop operations count                    */ 
     109        top = (grame02_lifo_node_t*)stack->top; 
    88110        pop_count = stack->pop_count; 
    89111 
    90 // SC3:     if head == NULL 
    91 // SC4:         return NULL # LIFO is empty 
    92 // SC5:     endif 
     112/* SC3:     if head == NULL                                                   */ 
     113/* SC4:         return NULL # LIFO is empty                                   */ 
     114/* SC5:     endif                                                             */ 
    93115        if( !top ) 
    94             return 0; 
     116            return NULL; 
    95117 
    96 // SC6:     next = head->next # get the next cell of cell 
    97         next = (grame02_stack_node_t*)top->next; 
    98          
    99 // SC7:     if CAS2 (&lf->top, head, oc, next, oc + 1) # try to change both the top of the lifo and pop count 
    100 // SC8:         break 
    101 // SC9:     endif 
    102         if( CAS2( stack, top, pop_count, next, pop_count + 1 ) ) 
     118        /* If a read barrier is needed at all, one above should ensure that 
     119         * top->next is also up to date when we read it. 
     120         */ 
     121 
     122/* SC6:     next = head->next # get the next cell of cell                     */ 
     123        next = (grame02_lifo_node_t*)top->next; 
     124 
     125/* SC7:     if CAS2 (&lf->top, head, oc, next, oc + 1) # try to change both 
     126                                                       # the top of the lifo 
     127                                                       # and pop count        */ 
     128/* SC8:         break                                                         */ 
     129/* SC9:     endif 
     130                                                      */ 
     131        if( CAS64( stack, top, pop_count, next, pop_count + 1 ) ) 
    103132            break; 
    104133 
    105 // SC10: endloop 
     134/* SC10: endloop                                                              */ 
    106135    } 
    107 // SC11: return head 
     136/* SC11: return head                                                          */ 
    108137    return top; 
    109138} 
    110139 
    111140 
    112 LIBLFDS_CALLING_CONVENTION(void) grame02_stack_test(void) 
     141LIBLFDS_CALLING_CONVENTION(void) grame02_lifo_test(void) 
    113142{ 
    114143    const char *s = "\n!dlrow olleh"; 
    115     grame02_stack_t stack; 
     144    grame02_lifo_t stack; 
    116145    const char *p; 
    117     grame02_stack_node_t *node; 
     146    grame02_lifo_node_t *node; 
    118147    
    119     grame02_stack_initialize( &stack ); 
     148    grame02_lifo_initialize( &stack ); 
    120149     
    121150    p = s; 
    … …  
    123152        char *p2 = (char*)malloc( 1 ); 
    124153        *p2 = *p++; 
    125         node = (grame02_stack_node_t*)malloc( sizeof(grame02_stack_node_t) ); 
     154        node = (grame02_lifo_node_t*)malloc( sizeof(grame02_lifo_node_t) ); 
    126155        node->value = p2; 
    127         grame02_stack_push( &stack, node ); 
     156        grame02_lifo_push( &stack, node ); 
    128157    } 
    129158 
    130     node = grame02_stack_pop( &stack ); 
     159    node = grame02_lifo_pop( &stack ); 
    131160    while( node ){ 
    132161        //free( node ); // actually it isn't safe to free node here, this is just a test so we leak it 
    133162        printf( "%c", * ((char*)(node->value)) ); 
    134163        free( node->value ); 
    135         node = grame02_stack_pop( &stack ); 
     164        node = grame02_lifo_pop( &stack ); 
    136165    } 
    137166} 

  • sfio/trunk/src/lockfree/grame02_lifo.h

    r1095 r1098  
    1 #ifndef INCLUDED_GRAME02_STACK_H 
    2 #define INCLUDED_GRAME02_STACK_H 
     1#ifndef INCLUDED_GRAME02_LIFO_H 
     2#define INCLUDED_GRAME02_LIFO_H 
    33 
    44/* 
    … …  
    2222 
    2323 
    24 typedef void* grame02_value_t;     /* this is the "payload" data type which is stored in the stack node */ 
     24typedef void* grame02_lifo_value_t;     /* this is the "payload" data type which is stored in the stack node */ 
    2525 
    26 struct grame02_stack_node_t; 
    27 typedef struct grame02_stack_node_t grame02_stack_node_t; 
     26struct grame02_lifo_node_t; 
     27typedef struct grame02_lifo_node_t grame02_lifo_node_t; 
    2828 
    2929#pragma pack( push, 4 ) 
    3030 
    3131 
    32 typedef struct grame02_stack_node_t{ 
    33     grame02_value_t value; 
    34     volatile grame02_stack_node_t *next; 
    35 } grame02_stack_node_t; 
     32typedef struct grame02_lifo_node_t{ 
     33    grame02_lifo_value_t value; 
     34    volatile grame02_lifo_node_t *next; 
     35} grame02_lifo_node_t; 
    3636 
    3737 
    38 typedef struct grame02_stack_t{ 
    39     volatile grame02_stack_node_t *top; 
     38typedef struct grame02_lifo_t{ 
     39    volatile grame02_lifo_node_t *top; 
    4040    volatile unsigned long pop_count; 
    41 }grame02_stack_t; 
     41}grame02_lifo_t; 
    4242 
    4343 
    … …  
    4545 
    4646 
    47 LIBLFDS_CALLING_CONVENTION(void) grame02_stack_initialize( grame02_stack_t* stack ); 
     47LIBLFDS_CALLING_CONVENTION(void) grame02_lifo_initialize( grame02_lifo_t* stack ); 
    4848 
    49 LIBLFDS_CALLING_CONVENTION(void) grame02_stack_push( grame02_stack_t* stack, grame02_stack_node_t *node ); 
     49LIBLFDS_CALLING_CONVENTION(void) grame02_lifo_push( grame02_lifo_t* stack, grame02_lifo_node_t *node ); 
    5050 
    51 LIBLFDS_CALLING_CONVENTION(grame02_stack_node_t*) grame02_stack_pop( grame02_stack_t* stack ); 
     51LIBLFDS_CALLING_CONVENTION(grame02_lifo_node_t*) grame02_lifo_pop( grame02_lifo_t* stack ); 
    5252 
    53 LIBLFDS_CALLING_CONVENTION(void) grame02_stack_test(void); 
     53LIBLFDS_CALLING_CONVENTION(void) grame02_lifo_test(void); 
    5454 
    5555#ifdef __cplusplus 
    … …  
    5757#endif /* __cplusplus */ 
    5858 
    59 #endif /* INCLUDED_GRAME02_STACK_H */ 
     59#endif /* INCLUDED_GRAME02_LIFO_H */ 
    6060