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

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

1) Fix a bug in KSH : after the "load" command,

the [ksh] prompt is now printed after completion
of the loaded application.

2) Fix a bug in vmm_handle_cow() : the copy-on-write

use now a hal_remote_memcpy() to replicate the page content.


File size: 16.2 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 "remote_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 *    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 QDT),
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
145
146
147/*****************************************************************************************
148 *                        simple barrier descriptor
149 *****************************************************************************************
150 * This structure defines the simple barrier descriptor. It is localized in the process
151 * reference cluster, as an extension of the generic barrier descriptor.
152 * It implements a toggle barrier remotely accessed by all threads.
153 * It contains the root of the xlist registering all arrived threads.
154 ****************************************************************************************/
155
156typedef struct simple_barrier_s
157{
158    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
159    uint32_t           current;       /*! number of arrived threads                     */
160    uint32_t           sense;         /*! barrier state (toggle)                        */
161    uint32_t           arity;         /*! number of expected threads                    */ 
162    xlist_entry_t      root;          /*! root of list of waiting threads               */
163} 
164simple_barrier_t;
165
166/*****************************************************************************************
167 * This function allocates memory for the simple barrier descriptor in the reference
168 * cluster of the calling process. It initializes the barrier state and returns
169 * a local pointer on the created simple barrier descriptor in reference cluster.
170 * It can be called by a thread running in any cluster, as it use RPC if required.
171 *****************************************************************************************
172 * @ count          : [in] number of expected threads.
173 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
174 ****************************************************************************************/
175simple_barrier_t * simple_barrier_create( uint32_t  count );
176
177/*****************************************************************************************
178 * This function releases the memory allocated for the simple barrier descriptor.
179 * It can be called by a thread running in any cluster, as it use RPC if required.
180 *****************************************************************************************
181 * @ barrier_xp  : extended pointer on simple barrier descriptor.
182 ****************************************************************************************/
183void simple_barrier_destroy( xptr_t   barrier_xp );
184
185/*****************************************************************************************
186 * This blocking function returns only when all expected threads reach the barrier.
187 * It can be called by a thread running in any cluster, as it use remote accesses.
188 * Waiting threads use a descheduling policy.
189 *****************************************************************************************
190 * @ barrier_xp   : extended pointer on simple barrier descriptor.
191 ****************************************************************************************/
192void simple_barrier_wait( xptr_t   barrier_xp );
193
194
195
196
197
198/*****************************************************************************************
199 *                              dqt_barrier
200 *****************************************************************************************
201 * These structuree define  the hierarchical DQT barrier, physically distributed in a
202 * mesh of clusters defined by the (x_size, y_size, nthreads) arguments:
203 *   . The involved clusters form a mesh [x_size * y_size]
204 *   . The lower left involved cluster is cluster(0,0) 
205 *   . The number of threads per cluster is the same in all clusters.
206 *
207 * Implementation note:
208 * - The quad three is implemented as a three dimensions array of node[x][y][l]
209 *   . [x][y] are the cluster coordinates / max values are (DQT_XMAX-1), (DQT_YMAX-1)
210 *   . [l] is the node level / 0 for terminal nodes / (DQT_LMAX-1) for the root node
211 * - The dqt_barrier_t is the global barrier descriptor, allocated in the reference
212 *   process cluster as an extension of the generic barrier descriptor. It contains a
213 *   3D array of extended pointers on all DQT nodes implementing the DQT barrier.
214 * - The dqt_node_t is a local barrier implementing a togle barrier between all threads
215 *   of a given cluster (for a terminal node), or between all representatives of the four
216 *   children nodes (for a non terminal node).
217 ****************************************************************************************/
218
219#define  DQT_XMAX    16               // max number of clusters in a row
220#define  DQT_YMAX    16               // max number of clusters in a column
221#define  DQT_LMAX    5                // max depth of the quad tree
222
223typedef struct dqt_node_s
224{
225    remote_busylock_t  lock;          /*! lock protecting list of waiting threads       */
226    volatile uint32_t  sense;         /*! barrier state (toggle)                        */
227    volatile uint32_t  current;       /*! number of locally arrived threads             */
228    uint32_t           arity;         /*! total number of locally expected threads      */
229    uint32_t           level;         /*! hierarchical level (0 is bottom)              */
230    xptr_t             parent_xp;     /*! x_pointer on parent node (NULL for root)      */
231    xptr_t             child_xp[4];   /*! x_pointer on children node (NULL for bottom)  */
232    xlist_entry_t      root;          /*! root of list of waiting threads               */
233}
234dqt_node_t;
235
236typedef struct dqt_barrier_s
237{
238    xptr_t    node_xp[DQT_XMAX][DQT_YMAX][DQT_LMAX];  /*! array of xptr on DQT nodes    */
239
240    uint32_t  x_size;                 /*! number of clusters in one row of DQT mesh     */
241    uint32_t  y_size;                 /*! number of clusters in one column of DQT mesh  */
242    uint32_t  nthreads;               /*! number of expected threads in one cluster     */
243} 
244dqt_barrier_t;
245
246/*****************************************************************************************
247 * This function allocates memory for the DQT barrier descriptor in the reference cluster
248 * of the calling process. It allocates also memory in all clusters of the QDT mesh,
249 * to store up to 5 QDT nodes per cluster.
250 * It initializes the barrier descriptor, including initialisation of the parent/children
251 * extended pointers in the distributed QDT nodes.
252 * It returns a local pointer on the QDT barrier descriptor in reference cluster.
253 * It can be called by a thread running in any cluster, as it use RPCs for memory
254 * allocation, and remote access for QDT initialisation.
255 *****************************************************************************************
256 * @ x_size      : [in] number of clusters in a line of DQT mesh.
257 * @ y_size      : [in] number of clusters in a column of DQT mesh.
258 * @ nthreads    : [in] number of threads per cluster.
259 * @ return Local pointer on barrier descriptor if success / return NULL if failure.
260 ****************************************************************************************/
261dqt_barrier_t * dqt_barrier_create( uint32_t  x_size,
262                                    uint32_t  y_size,
263                                    uint32_t  nthreads );
264
265/*****************************************************************************************
266 * This function releases all memory allocated for the QDT barrier descriptor.
267 * It removes the barrier from the list of barriers rooted in the reference process.
268 * It can be called by a thread running in any cluster, as it use RPCs.
269 *****************************************************************************************
270 * @ barrier_xp  : extended pointer on DQT barrier descriptor.
271 ****************************************************************************************/
272void dqt_barrier_destroy( xptr_t   barrier_xp );
273
274/*****************************************************************************************
275 * This blocking function returns only when all expected threads reach the barrier.
276 * It can be called by a thread running in any cluster, as it use remote accesses.
277 * Waiting threads use a descheduling policy.
278 *****************************************************************************************
279 * @ barrier_xp   : extended pointer on DQT barrier descriptor.
280 ****************************************************************************************/
281void dqt_barrier_wait( xptr_t   barrier_xp );
282
283
284
285#endif  /* _REMOTE_BARRIER_H_ */
Note: See TracBrowser for help on using the repository browser.