source: trunk/kernel/libk/remote_barrier.h @ 622

/*
 * remote_barrier.h - POSIX barrier definition.               
 * 
 * Author  Alain Greiner (2016,2017,2018,2019)
 *
 * Copyright (c) UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH.
 *
 * ALMOS-MKH is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2.0 of the License.
 *
 * ALMOS-MKH is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#ifndef _REMOTE_BARRIER_H_
#define _REMOTE_BARRIER_H_

#include <kernel_config.h>
#include <hal_kernel_types.h>
#include <remote_busylock.h>
#include <xlist.h>
#include <shared_pthread.h>

/***************************************************************************************
 *       This file defines two implementations for a POSIX compliant barrier.
 *
 * It is used by multi-threaded user applications to synchronise threads running in
 * different clusters. Access functions use RPCs for barrier creation/destruction,
 * and use remote access primitives for actual synchronisation (wait function).
 *
 * A barrier is declared by a given user process as a "pthread_barrier_t" user variable.
 * This user type is implemented in user space as an unsigned long, but the value is not
 * used by the kernel. ALMOS-MKH uses only the barrier virtual address as an identifier.
 * For each user barrier, ALMOS-MKH creates a kernel structure, dynamically allocated 
 * by the "generic_barrier_create()" function, destroyed by the "remote_barrier_destroy()"
 * function, and used by the "generic_barrier_wait()" function.
 *
 * Implementation note:
 * ALMOS-MKH supports two barrier implementations:
 *
 * 1) simple_barrier_t
 *    If the pointer on the barrier attributes is NULL, the barrier is implemented as
 *    a shared variable localized in the reference process cluster. 
 *    There is a risk of contention when the number of synchronizing threads is large.
 *
 * 2) dqt_barrier_t
 *    If the (x_size, y_size, nthreads) arguments are defined in the barrier attributes,
 *    the barrier is implemented as a hierarchical quad-tree covering all clusters in the
 *    (x_size * ysize) mesh, including cluster (0,0), with nthreads per cluster, and called
 *    DQT : Distributed Quad Tree. This DQT implementation supposes a regular architecture, 
 *    and a strong contraint on the threads placement: exactly "nthreads" threads per 
 *    cluster in the (x_size * y_size) mesh.
 *
 * For both implementations, the blocking "generic_barrier_wait()" function implements
 * a descheduling policy when the calling thread is not the last expected thread: 
 * the calling thread is registered in a waiting queue, rooted in the barrier structure, 
 * and the the calling thread is blocked on the THREAD_BLOCKED_USERSYNC condition. 
 * The last arrived thread unblocks all registered waiting threads.
 * **************************************************************************************/



/*****************************************************************************************
 *                 generic barrier descriptor and access functions
 *****************************************************************************************
 * This generic structure is used by both the simple and the QOT implementations.
 * It is implemented in the reference process cluster, and contains
 * - the barrier identifier,
 * - the implementation type (simple or QDT),
 * - an xlist implementing the set of barriers dynamically created by a given process,
 * - a pointer on the implementation specific descriptor (simple_barrier / sqt_barrier).
 ****************************************************************************************/

typedef struct generic_barrier_s
{
    intptr_t              ident;      /*! virtual address in user space == identifier   */
    xlist_entry_t         list;       /*! member of list of barriers in same process    */
    bool_t                is_dqt;     /*! DQT implementation when true                  */
    void                * extend;     /*! implementation specific barrier descriptor    */
} 
generic_barrier_t;

/*****************************************************************************************
 * This function returns an extended pointer on the remote barrier identified
 * by its virtual address in a given user process. It makes an associative search, 
 * scanning the list of barriers rooted in the reference process descriptor.
 * It can be used for both simple and DQT barriers, registered in the same list.
 *****************************************************************************************
 * @ ident    : barrier virtual address, used as identifier.
 * @ returns extended pointer on barrier if success / returns XPTR_NULL if not found. 
 ****************************************************************************************/
xptr_t generic_barrier_from_ident( intptr_t  ident );

/*****************************************************************************************
 * This function implements the pthread_barrier_init() syscall.
 * It allocates and initialises the generic barrier descriptor in the reference process 
 * cluster, and - depending on the <attr> argument, calls the relevant (simple or DQT) 
 * function to allocate and initialize the implementation dependant barrier descriptor.
 * Finally, it registers the barrier in the reference process xlist of user barriers.
 * It can be called by a thread running in any cluster, as it use RPC if required.
 *****************************************************************************************
 * @ ident    : barrier virtual address, used as identifier.
 * @ count    : number of expected threads.
 * @ attr     : barrier attributes (x_size,y_size,nthreads), used by QDT implementation.
 * @ returns 0 if success / returns -1 if not found. 
 ****************************************************************************************/
error_t generic_barrier_create( intptr_t                ident,
                                uint32_t                count,
                                pthread_barrierattr_t * attr );

/*****************************************************************************************
 * This function implements the pthread_barrier_destroy() syscall.
 * It calls the relevant function (simple or DQT) to release the memory allocated for 
 * the implementation specific barrier descriptor, and releases the memory allocated
 * for the generic barrier descriptor.
 * It removes the barrier from the list of barriers rooted in the reference process.
 * It can be called by a thread running in any cluster, as it use RPC if required.
 *****************************************************************************************
 * @ gen_barrier_xp  : extended pointer on generic barrier descriptor.
 ****************************************************************************************/
void generic_barrier_destroy( xptr_t gen_barrier_xp );

/*****************************************************************************************
 * This blocking function implements the pthread_barrier_wait() syscall.
 * It calls the relevant function (simple or DQT) depending on the implementation,
 * and returns only when all expected threads reach the barrier.
 * It can be called by a thread running in any cluster, as it use remote accesses.
 *****************************************************************************************
 * @ gen_barrier_xp   : extended pointer on generic barrier descriptor.
 ****************************************************************************************/
void generic_barrier_wait( xptr_t gen_barrier_xp );






/*****************************************************************************************
 *                        simple barrier descriptor
 *****************************************************************************************
 * This structure defines the simple barrier descriptor. It is localized in the process
 * reference cluster, as an extension of the generic barrier descriptor.
 * It implements a toggle barrier remotely accessed by all threads.
 * It contains the root of the xlist registering all arrived threads.
 ****************************************************************************************/

typedef struct simple_barrier_s
{
    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
    uint32_t           current;       /*! number of arrived threads                     */
    uint32_t           sense;         /*! barrier state (toggle)                        */
    uint32_t           arity;         /*! number of expected threads                    */ 
    xlist_entry_t      root;          /*! root of list of waiting threads               */
} 
simple_barrier_t;

/*****************************************************************************************
 * This function allocates memory for the simple barrier descriptor in the reference 
 * cluster of the calling process. It initializes the barrier state and returns
 * a local pointer on the created simple barrier descriptor in reference cluster.
 * It can be called by a thread running in any cluster, as it use RPC if required.
 *****************************************************************************************
 * @ count          : [in] number of expected threads.
 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
 ****************************************************************************************/
simple_barrier_t * simple_barrier_create( uint32_t  count );

/*****************************************************************************************
 * This function releases the memory allocated for the simple barrier descriptor. 
 * It can be called by a thread running in any cluster, as it use RPC if required.
 *****************************************************************************************
 * @ barrier_xp  : extended pointer on simple barrier descriptor.
 ****************************************************************************************/
void simple_barrier_destroy( xptr_t   barrier_xp );

/*****************************************************************************************
 * This blocking function returns only when all expected threads reach the barrier.
 * It can be called by a thread running in any cluster, as it use remote accesses.
 * Waiting threads use a descheduling policy.
 *****************************************************************************************
 * @ barrier_xp   : extended pointer on simple barrier descriptor.
 ****************************************************************************************/
void simple_barrier_wait( xptr_t   barrier_xp );





/*****************************************************************************************
 *                              dqt_barrier
 *****************************************************************************************
 * These structuree define  the hierarchical DQT barrier, physically distributed in a
 * mesh of clusters defined by the (x_size, y_size, nthreads) arguments:
 *   . The involved clusters form a mesh [x_size * y_size]
 *   . The lower left involved cluster is cluster(0,0)  
 *   . The number of threads per cluster is the same in all clusters.
 *
 * Implementation note:
 * - The quad three is implemented as a three dimensions array of node[x][y][l]
 *   . [x][y] are the cluster coordinates / max values are (DQT_XMAX-1), (DQT_YMAX-1)
 *   . [l] is the node level / 0 for terminal nodes / (DQT_LMAX-1) for the root node
 * - The dqt_barrier_t is the global barrier descriptor, allocated in the reference
 *   process cluster as an extension of the generic barrier descriptor. It contains a
 *   3D array of extended pointers on all DQT nodes implementing the DQT barrier.
 * - The dqt_node_t is a local barrier implementing a togle barrier between all threads
 *   of a given cluster (for a terminal node), or between all representatives of the four
 *   children nodes (for a non terminal node).
 ****************************************************************************************/

#define  DQT_XMAX    16               // max number of clusters in a row
#define  DQT_YMAX    16               // max number of clusters in a column
#define  DQT_LMAX    5                // max depth of the quad tree

typedef struct dqt_node_s
{
    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
    volatile uint32_t  sense;         /*! barrier state (toggle)                        */
    volatile uint32_t  current;       /*! number of locally arrived threads             */
    uint32_t           arity;         /*! total number of locally expected threads      */
    uint32_t           level;         /*! hierarchical level (0 is bottom)              */
    xptr_t             parent_xp;     /*! x_pointer on parent node (NULL for root)      */
    xptr_t             child_xp[4];   /*! x_pointer on children node (NULL for bottom)  */
    xlist_entry_t      root;          /*! root of list of waiting threads               */
}
dqt_node_t;

typedef struct dqt_barrier_s
{
    xptr_t    node_xp[DQT_XMAX][DQT_YMAX][DQT_LMAX];  /*! array of xptr on DQT nodes    */

    uint32_t  x_size;                 /*! number of clusters in one row of DQT mesh     */
    uint32_t  y_size;                 /*! number of clusters in one column of DQT mesh  */
    uint32_t  nthreads;               /*! number of expected threads in one cluster     */
} 
dqt_barrier_t;

/*****************************************************************************************
 * This function allocates memory for the DQT barrier descriptor in the reference cluster
 * of the calling process. It allocates also memory in all clusters of the QDT mesh, 
 * to store up to 5 QDT nodes per cluster. 
 * It initializes the barrier descriptor, including initialisation of the parent/children
 * extended pointers in the distributed QDT nodes.
 * It returns a local pointer on the QDT barrier descriptor in reference cluster.
 * It can be called by a thread running in any cluster, as it use RPCs for memory
 * allocation, and remote access for QDT initialisation.
 *****************************************************************************************
 * @ x_size      : [in] number of clusters in a line of DQT mesh.
 * @ y_size      : [in] number of clusters in a column of DQT mesh.
 * @ nthreads    : [in] number of threads per cluster.
 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
 ****************************************************************************************/
dqt_barrier_t * dqt_barrier_create( uint32_t  x_size,
                                    uint32_t  y_size,
                                    uint32_t  nthreads );

/*****************************************************************************************
 * This function releases all memory allocated for the QDT barrier descriptor.
 * It removes the barrier from the list of barriers rooted in the reference process.
 * It can be called by a thread running in any cluster, as it use RPCs.
 *****************************************************************************************
 * @ barrier_xp  : extended pointer on DQT barrier descriptor.
 ****************************************************************************************/
void dqt_barrier_destroy( xptr_t   barrier_xp );

/*****************************************************************************************
 * This blocking function returns only when all expected threads reach the barrier.
 * It can be called by a thread running in any cluster, as it use remote accesses.
 * Waiting threads use a descheduling policy.
 *****************************************************************************************
 * @ barrier_xp   : extended pointer on DQT barrier descriptor.
 ****************************************************************************************/
void dqt_barrier_wait( xptr_t   barrier_xp );



#endif  /* _REMOTE_BARRIER_H_ */