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

Last change on this file since 641 was 640, checked in by alain, 5 years ago

Remove all RPCs in page-fault handling.

File size: 18.0 KB
Line 
1/*
2 * remote_barrier.h - POSIX barrier definition.               
3 *
4 * Author  Alain Greiner (2016,2017,2018,2019)
5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; version 2.0 of the License.
13 *
14 * ALMOS-MKH is distributed in the hope that it will be useful, but
15 * WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
17 * General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#ifndef _REMOTE_BARRIER_H_
25#define _REMOTE_BARRIER_H_
26
27#include <kernel_config.h>
28#include <hal_kernel_types.h>
29#include <remote_busylock.h>
30#include <xlist.h>
31#include <shared_pthread.h>
32
33/***************************************************************************************
34 *       This file defines two implementations for a POSIX compliant barrier.
35 *
36 * It is used by multi-threaded user applications to synchronise threads running in
37 * different clusters. Access functions use RPCs for barrier creation/destruction,
38 * and use remote access primitives for actual synchronisation (wait function).
39 *
40 * A barrier is declared by a given user process as a "pthread_barrier_t" user variable.
41 * This user type is implemented in user space as an unsigned long, but the value is not
42 * used by the kernel. ALMOS-MKH uses only the barrier virtual address as an identifier.
43 * For each user barrier, ALMOS-MKH creates a kernel structure, dynamically allocated
44 * by the generic_barrier_create() function, destroyed by the generic_barrier_destroy()
45 * function, and used by the generic_barrier_wait() function.
46 *
47 * Implementation note:
48 * ALMOS-MKH supports two barrier implementations:
49 *
50 * 1) simple_barrier_t
51 *    If the pointer on the barrier attributes is NULL, the barrier is implemented as
52 *    a shared variable localized in the reference process cluster.
53 *    There is a risk of contention when the number of synchronizing threads is large.
54 *
55 * 2) dqt_barrier_t
56 *    If the (x_size, y_size, nthreads) arguments are defined in the barrier attributes,
57 *    the barrier is implemented as a hierarchical quad-tree covering all clusters in the
58 *    (x_size * ysize) mesh, including cluster (0,0), with nthreads per cluster.
59 *    This DQT (Distributed Quad Tree) implementation assumes a regular architecture,
60 *    and a strong contraint on the threads placement: exactly "nthreads" threads per
61 *    cluster in the (x_size * y_size) mesh.
62 *
63 * For both implementations, the blocking "generic_barrier_wait()" function implements
64 * a descheduling policy when the calling thread is not the last expected thread:
65 * the calling thread is registered in a waiting queue, rooted in the barrier structure,
66 * and the the calling thread is blocked on the THREAD_BLOCKED_USERSYNC condition.
67 * The last arrived thread unblocks all registered waiting threads.
68 * **************************************************************************************/
69
70
71
72/*****************************************************************************************
73 *                 generic barrier descriptor and access functions
74 *****************************************************************************************
75 * This generic structure is used by both the simple and the QOT implementations.
76 * It is implemented in the reference process cluster, and contains
77 * - the barrier identifier,
78 * - the implementation type (simple or dqt),
79 * - an xlist implementing the set of barriers dynamically created by a given process,
80 * - a pointer on the implementation specific descriptor (simple_barrier / sqt_barrier).
81 ****************************************************************************************/
82
83typedef struct generic_barrier_s
84{
85    intptr_t              ident;      /*! virtual address in user space == identifier   */
86    xlist_entry_t         list;       /*! member of list of barriers in same process    */
87    bool_t                is_dqt;     /*! DQT implementation when true                  */
88    void                * extend;     /*! implementation specific barrier descriptor    */
89} 
90generic_barrier_t;
91
92/*****************************************************************************************
93 * This function returns an extended pointer on the remote barrier identified
94 * by its virtual address in a given user process. It makes an associative search,
95 * scanning the list of barriers rooted in the reference process descriptor.
96 * It can be used for both simple and DQT barriers, registered in the same list.
97 *****************************************************************************************
98 * @ ident    : barrier virtual address, used as identifier.
99 * @ returns extended pointer on barrier if success / returns XPTR_NULL if not found.
100 ****************************************************************************************/
101xptr_t generic_barrier_from_ident( intptr_t  ident );
102
103/*****************************************************************************************
104 * This function implements the pthread_barrier_init() syscall.
105 * It allocates and initialises the generic barrier descriptor in the reference process
106 * cluster, and - depending on the <attr> argument, calls the relevant (simple or DQT)
107 * function to allocate and initialize the implementation dependant barrier descriptor.
108 * Finally, it registers the barrier in the reference process xlist of user barriers.
109 * It can be called by a thread running in any cluster, as it use RPC if required.
110 *****************************************************************************************
111 * @ ident    : barrier virtual address, used as identifier.
112 * @ count    : number of expected threads.
113 * @ attr     : barrier attributes (x_size,y_size,nthreads), used by QDT implementation.
114 * @ returns 0 if success / returns -1 if not found.
115 ****************************************************************************************/
116error_t generic_barrier_create( intptr_t                ident,
117                                uint32_t                count,
118                                pthread_barrierattr_t * attr );
119
120/*****************************************************************************************
121 * This function implements the pthread_barrier_destroy() syscall.
122 * It calls the relevant function (simple or DQT) to release the memory allocated for
123 * the implementation specific barrier descriptor, and releases the memory allocated
124 * for the generic barrier descriptor.
125 * It removes the barrier from the list of barriers rooted in the reference process.
126 * It can be called by a thread running in any cluster, as it use RPC if required.
127 *****************************************************************************************
128 * @ gen_barrier_xp  : extended pointer on generic barrier descriptor.
129 ****************************************************************************************/
130void generic_barrier_destroy( xptr_t gen_barrier_xp );
131
132/*****************************************************************************************
133 * This blocking function implements the pthread_barrier_wait() syscall.
134 * It calls the relevant function (simple or DQT) depending on the implementation,
135 * and returns only when all expected threads reach the barrier.
136 * It can be called by a thread running in any cluster, as it use remote accesses.
137 *****************************************************************************************
138 * @ gen_barrier_xp   : extended pointer on generic barrier descriptor.
139 ****************************************************************************************/
140void generic_barrier_wait( xptr_t gen_barrier_xp );
141
142
143/*****************************************************************************************
144 * This debug function uses remote accesses to display the current state of a generic
145 * barrier identified by the <gen_barrier_xp> argument.
146 * It calls the relevant function (simple or DQT) to display relevant information.
147 * It can be called by a thread running in any cluster.
148 *****************************************************************************************
149 * @ barrier_xp   : extended pointer on generic barrier descriptor.
150 ****************************************************************************************/
151
152void generic_barrier_display( xptr_t gen_barrier_xp );
153
154
155
156/*****************************************************************************************
157 *                        simple barrier descriptor
158 *****************************************************************************************
159 * This structure defines the simple barrier descriptor. It is localized in the process
160 * reference cluster, as an extension of the generic barrier descriptor.
161 * It implements a toggle barrier remotely accessed by all threads.
162 * It contains the root of the xlist registering all arrived threads.
163 ****************************************************************************************/
164
165typedef struct simple_barrier_s
166{
167    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
168    uint32_t           current;       /*! number of arrived threads                     */
169    uint32_t           sense;         /*! barrier state (toggle)                        */
170    uint32_t           arity;         /*! number of expected threads                    */ 
171    xlist_entry_t      root;          /*! root of list of waiting threads               */
172} 
173simple_barrier_t;
174
175/*****************************************************************************************
176 * This function allocates memory for the simple barrier descriptor in the reference
177 * cluster of the calling process. It initializes the barrier state and returns
178 * a local pointer on the created simple barrier descriptor in reference cluster.
179 * It can be called by a thread running in any cluster, as it use RPC if required.
180 *****************************************************************************************
181 * @ count          : [in] number of expected threads.
182 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
183 ****************************************************************************************/
184simple_barrier_t * simple_barrier_create( uint32_t  count );
185
186/*****************************************************************************************
187 * This function releases the memory allocated for the simple barrier descriptor.
188 * It can be called by a thread running in any cluster, as it use RPC if required.
189 *****************************************************************************************
190 * @ barrier_xp  : extended pointer on simple barrier descriptor.
191 ****************************************************************************************/
192void simple_barrier_destroy( xptr_t   barrier_xp );
193
194/*****************************************************************************************
195 * This blocking function returns only when all expected threads reach the barrier.
196 * It can be called by a thread running in any cluster, as it use remote accesses.
197 * Waiting threads use a descheduling policy.
198 *****************************************************************************************
199 * @ barrier_xp   : extended pointer on simple barrier descriptor.
200 ****************************************************************************************/
201void simple_barrier_wait( xptr_t   barrier_xp );
202
203/*****************************************************************************************
204 * This debug function uses remote accesses to display the current state of a simple
205 * barrier identified by the <barrier_xp> argument.
206 * It can be called by a thread running in any cluster.
207 *****************************************************************************************
208 * @ barrier_xp   : extended pointer on simple barrier descriptor.
209 ****************************************************************************************/
210void simple_barrier_display( xptr_t barrier_xp );
211
212
213
214
215/*****************************************************************************************
216 *                              dqt_barrier
217 *****************************************************************************************
218 * These structuree define  the hierarchical DQT barrier, physically distributed in a
219 * mesh of clusters defined by the (x_size, y_size, nthreads) arguments:
220 *   . The involved clusters form a mesh [x_size * y_size]
221 *   . The lower left involved cluster is cluster(0,0) 
222 *   . The number of threads per cluster is the same in all clusters.
223 *
224 * Implementation note:
225 * - The quad three is implemented as a three dimensions array of node[x][y][l]
226 *   . [x][y] are the cluster coordinates / max values are (DQT_XMAX-1), (DQT_YMAX-1)
227 *   . [l] is the node level / 0 for terminal nodes / (DQT_LMAX-1) for the root node
228 * - The dqt_barrier_t is the global barrier descriptor, allocated in the reference
229 *   process cluster as an extension of the generic barrier descriptor. It contains a
230 *   3D array of extended pointers on all DQT nodes implementing the DQT barrier.
231 * - The dqt_node_t is a local barrier implementing a togle barrier between all threads
232 *   of a given cluster (for a terminal node), or between all representatives of the four
233 *   children nodes (for a non terminal node).
234 ****************************************************************************************/
235
236#define  DQT_XMAX    16               // max number of clusters in a row
237#define  DQT_YMAX    16               // max number of clusters in a column
238#define  DQT_LMAX    5                // max depth of the quad tree
239
240typedef struct dqt_node_s
241{
242    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
243    volatile uint32_t  sense;         /*! barrier state (toggle)                        */
244    volatile uint32_t  current;       /*! number of locally arrived threads             */
245    uint32_t           arity;         /*! total number of locally expected threads      */
246    uint32_t           level;         /*! hierarchical level (0 is bottom)              */
247    xptr_t             parent_xp;     /*! x_pointer on parent node (NULL for root)      */
248    xptr_t             child_xp[4];   /*! x_pointer on children node (NULL for bottom)  */
249    xlist_entry_t      root;          /*! root of list of waiting threads               */
250}
251dqt_node_t;
252
253typedef struct dqt_barrier_s
254{
255    xptr_t    node_xp[DQT_XMAX][DQT_YMAX][DQT_LMAX];  /*! array of xptr on DQT nodes    */
256
257    uint32_t  x_size;                 /*! number of clusters in one row of DQT mesh     */
258    uint32_t  y_size;                 /*! number of clusters in one column of DQT mesh  */
259    uint32_t  nthreads;               /*! number of expected threads in one cluster     */
260} 
261dqt_barrier_t;
262
263/*****************************************************************************************
264 * This function allocates memory for the DQT barrier descriptor in the reference cluster
265 * of the calling process. It allocates also memory in all clusters of the QDT mesh,
266 * to store up to 5 QDT nodes per cluster.
267 * It initializes the barrier descriptor, including initialisation of the parent/children
268 * extended pointers in the distributed QDT nodes.
269 * It returns a local pointer on the QDT barrier descriptor in reference cluster.
270 * It can be called by a thread running in any cluster, as it use RPCs for memory
271 * allocation, and remote access for QDT initialisation.
272 *****************************************************************************************
273 * @ x_size      : [in] number of clusters in a line of DQT mesh.
274 * @ y_size      : [in] number of clusters in a column of DQT mesh.
275 * @ nthreads    : [in] number of threads per cluster.
276 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
277 ****************************************************************************************/
278dqt_barrier_t * dqt_barrier_create( uint32_t  x_size,
279                                    uint32_t  y_size,
280                                    uint32_t  nthreads );
281
282/*****************************************************************************************
283 * This function releases all memory allocated for the QDT barrier descriptor.
284 * It removes the barrier from the list of barriers rooted in the reference process.
285 * It can be called by a thread running in any cluster, as it use RPCs.
286 *****************************************************************************************
287 * @ barrier_xp  : extended pointer on DQT barrier descriptor.
288 ****************************************************************************************/
289void dqt_barrier_destroy( xptr_t   barrier_xp );
290
291/*****************************************************************************************
292 * This blocking function returns only when all expected threads reach the barrier.
293 * It can be called by a thread running in any cluster, as it use remote accesses.
294 * Waiting threads use a descheduling policy.
295 *****************************************************************************************
296 * @ barrier_xp   : extended pointer on DQT barrier descriptor.
297 ****************************************************************************************/
298void dqt_barrier_wait( xptr_t   barrier_xp );
299
300/*****************************************************************************************
301 * This debug function uses remote accesses to display the current state of all
302 * ditributed nodes in a DQT barrier identified by the <barrier_xp> argument.
303 * It can be called by a thread running in any cluster.
304 *****************************************************************************************
305 * @ barrier_xp   : extended pointer on DQT barrier descriptor.
306 ****************************************************************************************/
307void dqt_barrier_display( xptr_t barrier_xp );
308
309#endif  /* _REMOTE_BARRIER_H_ */
Note: See TracBrowser for help on using the repository browser.