Difference between pages "r6.0.0:Lfds600 slist set user data in element" and "r6.0.0:Lfds600 stack"

From liblfds.org
(Difference between pages)
Jump to navigation Jump to search
m (1 revision imported)
 
m (1 revision imported)
 
Line 1: Line 1:
{{DISPLAYTITLE:r6.0.0:lfds600_slist_set_user_data_in_element}}
{{DISPLAYTITLE:r6.0.0:lfds600_stack}}
==Source Files==
==Source Files==
  /liblfds600/src/lfds600_slist/lfds600_slist_get_and_set.c
  /liblfds600/src/lfds600_stack/lfds600_stack_delete.c
/liblfds600/src/lfds600_stack/lfds600_stack_new.c
/liblfds600/src/lfds600_stack/lfds600_stack_push_pop.c
/liblfds600/src/lfds600_stack/lfds600_stack_query.c
/liblfds600/src/lfds600_stack/lfds600_stack_internal.h
  /liblfds600/inc/liblfds600.h
  /liblfds600/inc/liblfds600.h


==Prototype==
==Incomplete Types==
  int lfds600_slist_set_user_data_in_element( struct lfds600_slist_element *se, void *user_data );
  struct lfds600_stack_state;


==Parameters==
==Enums==
''struct lfds600_slist_element *se''
enum lfds600_stack_query_type
: A pointer to an slist element as allocated by ''[[r6.0.0:lfds600_slist_new_head|lfds600_slist_new_head]]'' or ''[[r6.0.0:lfds600_slist_new_next|lfds600_slist_new_next]]''.
{
  LFDS600_STACK_QUERY_ELEMENT_COUNT
};


''void *user_data''
==Prototypes==
: A void pointer of user data which will be placed into the slist element.
int [[r6.0.0:lfds600_stack_new|lfds600_stack_new]]( struct lfds600_stack_state **ss, lfds600_atom_t number_elements );
void [[r6.0.0:lfds600_stack_delete|lfds600_stack_delete]]( struct lfds600_stack_state *ss,
                            void (*user_data_delete_function)(void *user_data, void *user_state),
                            void *user_state );
void [[r6.0.0:lfds600_stack_clear|lfds600_stack_clear]]( struct lfds600_stack_state *ss,
                          void (*user_data_clear_function)(void *user_data, void *user_state),
                          void *user_state );
int [[r6.0.0:lfds600_stack_push|lfds600_stack_push]]( struct lfds600_stack_state *ss, void *user_data );
int [[r6.0.0:lfds600_stack_guaranteed_push|lfds600_stack_guaranteed_push]]( struct lfds600_stack_state *ss, void *user_data );
int [[r6.0.0:lfds600_stack_pop|lfds600_stack_pop]]( struct lfds600_stack_state *ss, void **user_data );
void [[r6.0.0:lfds600_stack_query|lfds600_stack_query]]( struct lfds600_stack_state *ss, enum lfds600_stack_query_type query_type, void *query_input, void *query_output );


==Return Value==
==Overview==
Returns 1 on success, 0 on failure.  The only cause of failure is if you try to set the user data in an element which has been logically deleted.
This API implements a stack.  A new stack is instantiated by the ''lfds600_stack_new'' function, where the argument ''number_elements'' is the maximum number of elements which can be pushed to the stack at any one time.  The caller then uses the stack by pushing and popping, via the ''lfds600_stack_push'' and ''lfds600_stack_pop'' functions, respectively.  A push or pop operation will push or pop a single void pointer of user data.  These void pointers are expected to point to user allocated state although of course they can be used directly to store a single value.  Finally, the stack is deleted using ''lfds600_stack_delete''.


==Notes==
The function ''lfds600_stack_push'' only fails when there are no elements available in the stack.  In this case, the function ''lfds600_stack_guaranteed_push'' can be called. This allocates a single new element and then pushes that element.  This permanently increases the maximum number of elements in the stack by one.  This function only fails when ''malloc'' fails.
This function sets the user data void pointer in the slist element.


==See Also==
==Lock-free Specific Behaviour==
* [[r6.0.0:lfds600_slist|lfds600_slist]]
The maximum number of elements in the stack must be specified when the stack is created and these elements are allocated in full when the stack is created. It is possible after the stack is created to increase the number of elements in the stack, by using the function ''lfds600_stack_guaranteed_push'', but it is never possible to decrease the number of elements in the stack; the stack can only grow.
* [[r6.0.0:lfds600_slist_get_user_data_from_element|lfds600_slist_get_user_data_from_element]]
 
==Algorithm==
This freelist implements Treiber's stack algorithm.  As such it does not truly scale; contention for entry and exit to and from the stack ultimately reduces performance as the CPU count increases.  Indeed, with enough CPUs, performance becomes ''less'' than with fewer CPUs, for there are so many threads, they almost always fail in their attempt to enter or leave the stack and so are prevented from doing other work.
 
There is a far more scalable stack, based on the work done by Hendler, Shavit and Yerushalmi, which I understand (I've not looked at in depth) is basically the Treiber stack but with a layer in front of the stack where any threads which at the same time wish to push and pop can exchange their respective operations (the pusher giving his element to the popper) and so avoid having to touch the stack. I intend to implement this in the future.

Latest revision as of 14:07, 4 January 2015

Source Files

/liblfds600/src/lfds600_stack/lfds600_stack_delete.c
/liblfds600/src/lfds600_stack/lfds600_stack_new.c
/liblfds600/src/lfds600_stack/lfds600_stack_push_pop.c
/liblfds600/src/lfds600_stack/lfds600_stack_query.c
/liblfds600/src/lfds600_stack/lfds600_stack_internal.h
/liblfds600/inc/liblfds600.h

Incomplete Types

struct lfds600_stack_state;

Enums

enum lfds600_stack_query_type
{
  LFDS600_STACK_QUERY_ELEMENT_COUNT
};

Prototypes

int lfds600_stack_new( struct lfds600_stack_state **ss, lfds600_atom_t number_elements );
void lfds600_stack_delete( struct lfds600_stack_state *ss,
                           void (*user_data_delete_function)(void *user_data, void *user_state),
                           void *user_state );

void lfds600_stack_clear( struct lfds600_stack_state *ss,
                          void (*user_data_clear_function)(void *user_data, void *user_state),
                          void *user_state );

int lfds600_stack_push( struct lfds600_stack_state *ss, void *user_data );
int lfds600_stack_guaranteed_push( struct lfds600_stack_state *ss, void *user_data );
int lfds600_stack_pop( struct lfds600_stack_state *ss, void **user_data );

void lfds600_stack_query( struct lfds600_stack_state *ss, enum lfds600_stack_query_type query_type, void *query_input, void *query_output );

Overview

This API implements a stack. A new stack is instantiated by the lfds600_stack_new function, where the argument number_elements is the maximum number of elements which can be pushed to the stack at any one time. The caller then uses the stack by pushing and popping, via the lfds600_stack_push and lfds600_stack_pop functions, respectively. A push or pop operation will push or pop a single void pointer of user data. These void pointers are expected to point to user allocated state although of course they can be used directly to store a single value. Finally, the stack is deleted using lfds600_stack_delete.

The function lfds600_stack_push only fails when there are no elements available in the stack. In this case, the function lfds600_stack_guaranteed_push can be called. This allocates a single new element and then pushes that element. This permanently increases the maximum number of elements in the stack by one. This function only fails when malloc fails.

Lock-free Specific Behaviour

The maximum number of elements in the stack must be specified when the stack is created and these elements are allocated in full when the stack is created. It is possible after the stack is created to increase the number of elements in the stack, by using the function lfds600_stack_guaranteed_push, but it is never possible to decrease the number of elements in the stack; the stack can only grow.

Algorithm

This freelist implements Treiber's stack algorithm. As such it does not truly scale; contention for entry and exit to and from the stack ultimately reduces performance as the CPU count increases. Indeed, with enough CPUs, performance becomes less than with fewer CPUs, for there are so many threads, they almost always fail in their attempt to enter or leave the stack and so are prevented from doing other work.

There is a far more scalable stack, based on the work done by Hendler, Shavit and Yerushalmi, which I understand (I've not looked at in depth) is basically the Treiber stack but with a layer in front of the stack where any threads which at the same time wish to push and pop can exchange their respective operations (the pusher giving his element to the popper) and so avoid having to touch the stack. I intend to implement this in the future.