/* * 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 #include #include #include #include /*************************************************************************************** * 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 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_ */