Index: trunk/kernel/libk/remote_barrier.h
===================================================================
--- trunk/kernel/libk/remote_barrier.h	(revision 581)
+++ trunk/kernel/libk/remote_barrier.h	(revision 619)
@@ -2,5 +2,5 @@
  * remote_barrier.h - POSIX barrier definition.               
  * 
- * Author  Alain Greiner (2016,2017,2018)
+ * Author  Alain Greiner (2016,2017,2018,2019)
  *
  * Copyright (c) UPMC Sorbonne Universites
@@ -29,46 +29,64 @@
 #include <remote_busylock.h>
 #include <xlist.h>
+#include <shared_pthread.h>
 
 /***************************************************************************************
- *          This file defines a POSIX compliant barrier.
+ *       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, as all access functions uses hal_remote_l32() / hal_remote_s32()
- * remote access primitives.
- *
- * A barrier is declared by a given user process as a "pthread_barrier_t" global variable.
- * This user type is implemented 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 "remote_barrier_t" structure,
- * dynamically allocated in the reference cluster by the remote_barrier_create() function, 
- * and destroyed by the remote_barrier_destroy() function, using RPC if the calling thread
- * is not running in the reference cluster.
- *
- * The blocking "remote_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 registtered waiting threads.
+ * 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.
  * **************************************************************************************/
 
-/*****************************************************************************************
- * This structure defines the barrier descriptor.
- * - It contains an xlist of all barriers dynamically created by a given process,
- *   rooted in the reference process descriptor.
- * - It contains the root of another xlist to register all arrived threads.
- ****************************************************************************************/
-
-typedef struct remote_barrier_s
-{
-    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
-    intptr_t           ident;         /*! virtual address in user space == identifier   */
-    uint32_t           current;       /*! number of arrived threads                     */
-    uint32_t           sense;         /*! barrier state (toggle)                        */
-    uint32_t           nb_threads;    /*! number of expected threads                    */ 
-    xlist_entry_t      list;          /*! member of list of barriers in same process    */
-    xlist_entry_t      root;          /*! root of list of 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    */
 } 
-remote_barrier_t;
-
+generic_barrier_t;
 
 /*****************************************************************************************
@@ -76,40 +94,191 @@
  * 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 remote_barrier_from_ident( intptr_t  ident );
-
-/*****************************************************************************************
- * This function implement the pthread_barrier_init() syscall.
- * It allocates memory for the barrier descriptor in the reference cluster for
- * the calling process, it initializes the barrier state, and register it in the 
- * list of barriers owned by the reference process.
- *****************************************************************************************
- * @ count       : number of expected threads.
- * @ ident       : barrier identifier (virtual address in user space).
- * @ return 0 if success / return ENOMEM if failure.
- ****************************************************************************************/
-error_t remote_barrier_create( intptr_t ident,
-                               uint32_t count );
-
-/*****************************************************************************************
- * This function implement the pthread_barrier_destroy() syscall.
- * It releases thr memory allocated for the barrier descriptor, and remove the barrier 
- * from the list of barriers owned by the reference process.
- *****************************************************************************************
- * @ barrier_xp  : extended pointer on barrier descriptor.
- ****************************************************************************************/
-void remote_barrier_destroy( xptr_t   barrier_xp );
-
-/*****************************************************************************************
- * This function implement the pthread_barrier_wait() syscall.
- * It returns only when the number of expected threads (registered in the barrier
- * dexcriptor) reach the barrier.
- *****************************************************************************************
- * @ barrier_xp   : extended pointer on barrier descriptor.
- ****************************************************************************************/
-void remote_barrier_wait( xptr_t   barrier_xp );
+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 );
+
 
 
