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

Last change on this file since 623 was 623, checked in by alain, 3 years ago

Introduce three new types of vsegs (KCODE,KDATA,KDEV)
to map the kernel vsegs in the process VSL and GPT.
This now used by both the TSAR and the I86 architectures.

File size: 18.1 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, and called
59 *    DQT : Distributed Quad Tree. This DQT implementation supposes a regular architecture,
60                     uint32_t arity = hal_remote_l32( XPTR( node_cxy , &node_ptr->arity       ));
61 *    and a strong contraint on the threads placement: exactly "nthreads" threads per
62 *    cluster in the (x_size * y_size) mesh.
63 *
64 * For both implementations, the blocking "generic_barrier_wait()" function implements
65 * a descheduling policy when the calling thread is not the last expected thread:
66 * the calling thread is registered in a waiting queue, rooted in the barrier structure,
67 * and the the calling thread is blocked on the THREAD_BLOCKED_USERSYNC condition.
68 * The last arrived thread unblocks all registered waiting threads.
69 * **************************************************************************************/
70
71
72
73/*****************************************************************************************
74 *                 generic barrier descriptor and access functions
75 *****************************************************************************************
76 * This generic structure is used by both the simple and the QOT implementations.
77 * It is implemented in the reference process cluster, and contains
78 * - the barrier identifier,
79 * - the implementation type (simple or QDT),
80 * - an xlist implementing the set of barriers dynamically created by a given process,
81 * - a pointer on the implementation specific descriptor (simple_barrier / sqt_barrier).
82 ****************************************************************************************/
83
84typedef struct generic_barrier_s
85{
86    intptr_t              ident;      /*! virtual address in user space == identifier   */
87    xlist_entry_t         list;       /*! member of list of barriers in same process    */
88    bool_t                is_dqt;     /*! DQT implementation when true                  */
89    void                * extend;     /*! implementation specific barrier descriptor    */
90} 
91generic_barrier_t;
92
93/*****************************************************************************************
94 * This function returns an extended pointer on the remote barrier identified
95 * by its virtual address in a given user process. It makes an associative search,
96 * scanning the list of barriers rooted in the reference process descriptor.
97 * It can be used for both simple and DQT barriers, registered in the same list.
98 *****************************************************************************************
99 * @ ident    : barrier virtual address, used as identifier.
100 * @ returns extended pointer on barrier if success / returns XPTR_NULL if not found.
101 ****************************************************************************************/
102xptr_t generic_barrier_from_ident( intptr_t  ident );
103
104/*****************************************************************************************
105 * This function implements the pthread_barrier_init() syscall.
106 * It allocates and initialises the generic barrier descriptor in the reference process
107 * cluster, and - depending on the <attr> argument, calls the relevant (simple or DQT)
108 * function to allocate and initialize the implementation dependant barrier descriptor.
109 * Finally, it registers the barrier in the reference process xlist of user barriers.
110 * It can be called by a thread running in any cluster, as it use RPC if required.
111 *****************************************************************************************
112 * @ ident    : barrier virtual address, used as identifier.
113 * @ count    : number of expected threads.
114 * @ attr     : barrier attributes (x_size,y_size,nthreads), used by QDT implementation.
115 * @ returns 0 if success / returns -1 if not found.
116 ****************************************************************************************/
117error_t generic_barrier_create( intptr_t                ident,
118                                uint32_t                count,
119                                pthread_barrierattr_t * attr );
120
121/*****************************************************************************************
122 * This function implements the pthread_barrier_destroy() syscall.
123 * It calls the relevant function (simple or DQT) to release the memory allocated for
124 * the implementation specific barrier descriptor, and releases the memory allocated
125 * for the generic barrier descriptor.
126 * It removes the barrier from the list of barriers rooted in the reference process.
127 * It can be called by a thread running in any cluster, as it use RPC if required.
128 *****************************************************************************************
129 * @ gen_barrier_xp  : extended pointer on generic barrier descriptor.
130 ****************************************************************************************/
131void generic_barrier_destroy( xptr_t gen_barrier_xp );
132
133/*****************************************************************************************
134 * This blocking function implements the pthread_barrier_wait() syscall.
135 * It calls the relevant function (simple or DQT) depending on the implementation,
136 * and returns only when all expected threads reach the barrier.
137 * It can be called by a thread running in any cluster, as it use remote accesses.
138 *****************************************************************************************
139 * @ gen_barrier_xp   : extended pointer on generic barrier descriptor.
140 ****************************************************************************************/
141void generic_barrier_wait( xptr_t gen_barrier_xp );
142
143
144/*****************************************************************************************
145 * This debug function uses remote accesses to display the current state of a generic
146 * barrier identified by the <gen_barrier_xp> argument.
147 * It calls the relevant function (simple or DQT) to display relevant information.
148 * It can be called by a thread running in any cluster.
149 *****************************************************************************************
150 * @ barrier_xp   : extended pointer on generic barrier descriptor.
151 ****************************************************************************************/
152
153void generic_barrier_display( xptr_t gen_barrier_xp );
154
155
156
157/*****************************************************************************************
158 *                        simple barrier descriptor
159 *****************************************************************************************
160 * This structure defines the simple barrier descriptor. It is localized in the process
161 * reference cluster, as an extension of the generic barrier descriptor.
162 * It implements a toggle barrier remotely accessed by all threads.
163 * It contains the root of the xlist registering all arrived threads.
164 ****************************************************************************************/
165
166typedef struct simple_barrier_s
167{
168    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
169    uint32_t           current;       /*! number of arrived threads                     */
170    uint32_t           sense;         /*! barrier state (toggle)                        */
171    uint32_t           arity;         /*! number of expected threads                    */ 
172    xlist_entry_t      root;          /*! root of list of waiting threads               */
173} 
174simple_barrier_t;
175
176/*****************************************************************************************
177 * This function allocates memory for the simple barrier descriptor in the reference
178 * cluster of the calling process. It initializes the barrier state and returns
179 * a local pointer on the created simple barrier descriptor in reference cluster.
180 * It can be called by a thread running in any cluster, as it use RPC if required.
181 *****************************************************************************************
182 * @ count          : [in] number of expected threads.
183 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
184 ****************************************************************************************/
185simple_barrier_t * simple_barrier_create( uint32_t  count );
186
187/*****************************************************************************************
188 * This function releases the memory allocated for the simple barrier descriptor.
189 * It can be called by a thread running in any cluster, as it use RPC if required.
190 *****************************************************************************************
191 * @ barrier_xp  : extended pointer on simple barrier descriptor.
192 ****************************************************************************************/
193void simple_barrier_destroy( xptr_t   barrier_xp );
194
195/*****************************************************************************************
196 * This blocking function returns only when all expected threads reach the barrier.
197 * It can be called by a thread running in any cluster, as it use remote accesses.
198 * Waiting threads use a descheduling policy.
199 *****************************************************************************************
200 * @ barrier_xp   : extended pointer on simple barrier descriptor.
201 ****************************************************************************************/
202void simple_barrier_wait( xptr_t   barrier_xp );
203
204/*****************************************************************************************
205 * This debug function uses remote accesses to display the current state of a simple
206 * barrier identified by the <barrier_xp> argument.
207 * It can be called by a thread running in any cluster.
208 *****************************************************************************************
209 * @ barrier_xp   : extended pointer on simple barrier descriptor.
210 ****************************************************************************************/
211void simple_barrier_display( xptr_t barrier_xp );
212
213
214
215
216/*****************************************************************************************
217 *                              dqt_barrier
218 *****************************************************************************************
219 * These structuree define  the hierarchical DQT barrier, physically distributed in a
220 * mesh of clusters defined by the (x_size, y_size, nthreads) arguments:
221 *   . The involved clusters form a mesh [x_size * y_size]
222 *   . The lower left involved cluster is cluster(0,0) 
223 *   . The number of threads per cluster is the same in all clusters.
224 *
225 * Implementation note:
226 * - The quad three is implemented as a three dimensions array of node[x][y][l]
227 *   . [x][y] are the cluster coordinates / max values are (DQT_XMAX-1), (DQT_YMAX-1)
228 *   . [l] is the node level / 0 for terminal nodes / (DQT_LMAX-1) for the root node
229 * - The dqt_barrier_t is the global barrier descriptor, allocated in the reference
230 *   process cluster as an extension of the generic barrier descriptor. It contains a
231 *   3D array of extended pointers on all DQT nodes implementing the DQT barrier.
232 * - The dqt_node_t is a local barrier implementing a togle barrier between all threads
233 *   of a given cluster (for a terminal node), or between all representatives of the four
234 *   children nodes (for a non terminal node).
235 ****************************************************************************************/
236
237#define  DQT_XMAX    16               // max number of clusters in a row
238#define  DQT_YMAX    16               // max number of clusters in a column
239#define  DQT_LMAX    5                // max depth of the quad tree
240
241typedef struct dqt_node_s
242{
243    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
244    volatile uint32_t  sense;         /*! barrier state (toggle)                        */
245    volatile uint32_t  current;       /*! number of locally arrived threads             */
246    uint32_t           arity;         /*! total number of locally expected threads      */
247    uint32_t           level;         /*! hierarchical level (0 is bottom)              */
248    xptr_t             parent_xp;     /*! x_pointer on parent node (NULL for root)      */
249    xptr_t             child_xp[4];   /*! x_pointer on children node (NULL for bottom)  */
250    xlist_entry_t      root;          /*! root of list of waiting threads               */
251}
252dqt_node_t;
253
254typedef struct dqt_barrier_s
255{
256    xptr_t    node_xp[DQT_XMAX][DQT_YMAX][DQT_LMAX];  /*! array of xptr on DQT nodes    */
257
258    uint32_t  x_size;                 /*! number of clusters in one row of DQT mesh     */
259    uint32_t  y_size;                 /*! number of clusters in one column of DQT mesh  */
260    uint32_t  nthreads;               /*! number of expected threads in one cluster     */
261} 
262dqt_barrier_t;
263
264/*****************************************************************************************
265 * This function allocates memory for the DQT barrier descriptor in the reference cluster
266 * of the calling process. It allocates also memory in all clusters of the QDT mesh,
267 * to store up to 5 QDT nodes per cluster.
268 * It initializes the barrier descriptor, including initialisation of the parent/children
269 * extended pointers in the distributed QDT nodes.
270 * It returns a local pointer on the QDT barrier descriptor in reference cluster.
271 * It can be called by a thread running in any cluster, as it use RPCs for memory
272 * allocation, and remote access for QDT initialisation.
273 *****************************************************************************************
274 * @ x_size      : [in] number of clusters in a line of DQT mesh.
275 * @ y_size      : [in] number of clusters in a column of DQT mesh.
276 * @ nthreads    : [in] number of threads per cluster.
277 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
278 ****************************************************************************************/
279dqt_barrier_t * dqt_barrier_create( uint32_t  x_size,
280                                    uint32_t  y_size,
281                                    uint32_t  nthreads );
282
283/*****************************************************************************************
284 * This function releases all memory allocated for the QDT barrier descriptor.
285 * It removes the barrier from the list of barriers rooted in the reference process.
286 * It can be called by a thread running in any cluster, as it use RPCs.
287 *****************************************************************************************
288 * @ barrier_xp  : extended pointer on DQT barrier descriptor.
289 ****************************************************************************************/
290void dqt_barrier_destroy( xptr_t   barrier_xp );
291
292/*****************************************************************************************
293 * This blocking function returns only when all expected threads reach the barrier.
294 * It can be called by a thread running in any cluster, as it use remote accesses.
295 * Waiting threads use a descheduling policy.
296 *****************************************************************************************
297 * @ barrier_xp   : extended pointer on DQT barrier descriptor.
298 ****************************************************************************************/
299void dqt_barrier_wait( xptr_t   barrier_xp );
300
301/*****************************************************************************************
302 * This debug function uses remote accesses to display the current state of all
303 * ditributed nodes in a DQT barrier identified by the <barrier_xp> argument.
304 * It can be called by a thread running in any cluster.
305 *****************************************************************************************
306 * @ barrier_xp   : extended pointer on DQT barrier descriptor.
307 ****************************************************************************************/
308void dqt_barrier_display( xptr_t barrier_xp );
309
310#endif  /* _REMOTE_BARRIER_H_ */
Note: See TracBrowser for help on using the repository browser.