source: trunk/kernel/libk/list.h @ 632

Last change on this file since 632 was 632, checked in by alain, 16 months ago

This version replace the RPC by direct remote memory access
for physical pages allacation/release.
It is commited before being tested.

File size: 16.6 KB
Line 
1/*
2 * list.h - Double circular linked list
3 *
4 * Authors Ghassan Almaless  (2008,2009,2010,2011,2012)
5 *         Alain Greiner     (2016,2017,2018i,2019)
6 *
7 * Copyright (c) UPMC Sorbonne Universites
8 *
9 * This file is part of ALMOS-MKH     
10 *
11 * ALMOS-MKH is free software; you can redistribute it and/or modify it
12 * under the terms of the GNU General Public License as published by
13 * the Free Software Foundation; version 2.0 of the License.
14 *
15 * ALMOS-MKH is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
22 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
23 */
24
25#ifndef _LIST_H_
26#define _LIST_H_
27
28#include <kernel_config.h>
29#include <hal_kernel_types.h>
30#include <hal_remote.h>
31#include <printk.h>
32
33#ifndef NULL
34#define NULL (void *) 0
35#endif
36
37
38////////////////////////////////////////////////////////////////////////////
39//          Double circular linked list functions & macros
40//
41// It defines a generic local list, as all elements are in the same cluster.
42//
43// There is two sets of access functions, because these local lists can be
44// accessed by local threads, using local pointers, but they can also be
45// accessed by remote threads running in any cluster, with specific access
46// functions using extended pointers.
47////////////////////////////////////////////////////////////////////////////
48
49/***************************************************************************
50 * This structure defines a Double Circular Linked List entry.
51 * Note : The list root is an extra list-entry_t, that is NOT part
52 *            of the set of linked elements.
53 **************************************************************************/
54
55typedef struct list_entry_s
56{
57        struct list_entry_s * next;
58        struct list_entry_s * pred;
59}
60list_entry_t;
61
62/***************************************************************************
63 * This macro return an uint32_t that is the offset (number of bytes)
64 * of a field in a structure.
65 * @ type   : structure type
66 * @ member : name of the field
67 **************************************************************************/
68
69#ifndef OFFSETOF
70#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
71#endif
72
73/***************************************************************************
74 * This macro returns a pointer on a structure containing a list_entry_t.
75 ***************************************************************************
76 * @ list_ptr       : pointer on the list_entry
77 * @ container_type : type of the structure containing the list-entry
78 * @ member_name    : name of the list_entry field
79 **************************************************************************/
80
81#define LIST_ELEMENT( list_ptr , container_type , member_name)          \
82        ({const typeof(((container_type*)0)->member_name) *__member_ptr = (list_ptr); \
83        (container_type *)( (char*)__member_ptr - OFFSETOF( container_type , member_name ));})
84
85
86////////////////////////////////////////////////////////////////////////////
87// These functions and macros mus be called by a thread running
88// in the local cluster to access the local list.
89////////////////////////////////////////////////////////////////////////////
90
91/***************************************************************************
92 * This macro returns t pointer on the first element of a list.
93 ***************************************************************************
94 * @ root     : pointer on the list root
95 * @ type     : type of the linked elements
96 * @ member   : name of the list_entry_t field
97 **************************************************************************/
98
99#define LIST_FIRST( root , type , member )              \
100        LIST_ELEMENT( (root)->next , type , member )
101
102/***************************************************************************
103 * This macro returns a pointer on the last element of a list.
104 ***************************************************************************
105 * @ root     : pointer on the list root
106 * @ type     : type of the linked elements
107 * @ member   : name of the list_entry_t field
108 **************************************************************************/
109
110#define LIST_LAST( root , type , member )               \
111        LIST_ELEMENT( (root)->pred , type , member )
112
113/***************************************************************************
114 * This macro traverse a rooted double linked list in forward order.
115 * WARNING : Don't use this macro when you want to remove one or several
116 * item(s) from the traversed list.     
117 ***************************************************************************
118 * @ root      : pointer on the root list_entry
119 * @ iter      : pointer on a list_entry
120 **************************************************************************/
121
122#define LIST_FOREACH( root , iter ) \
123for( (iter) = (root)->next ;        \
124     (iter) != (root) ;                         \
125     (iter) = (iter)->next )
126       
127/***************************************************************************
128 * This macro traverse a rooted double linked list in backward order.
129 * WARNING : same as the forward traversal
130 ***************************************************************************
131 * @ root      : pointer on the root list_entry
132 * @ iter      : pointer on a list_entry
133 **************************************************************************/
134
135#define LIST_FOREACH_BACKWARD( root , iter )  \
136for( (iter) = (root)->pred ;                  \
137     (iter) != (root) ;                       \
138     (iter) = (iter)->pred )
139
140/***************************************************************************
141 * This function initializes the root of a rooted double linked list.
142 ***************************************************************************
143 * @ root    : pointer on the list root
144 **************************************************************************/
145static inline void list_root_init( list_entry_t * root )
146{
147        root->next = root;
148        root->pred = root;
149}
150
151/***************************************************************************
152 * This function initializes an entry of a rooted double linked list.
153 ***************************************************************************
154 * @ entry   : pointer on the list-entry to be initialized
155 **************************************************************************/
156static inline void list_entry_init( list_entry_t * entry )
157{
158        entry->next = NULL;
159        entry->pred = NULL;
160}
161
162/***************************************************************************
163 * This function must be called by a thread running in local cluster.
164 * It inserts a new entry in first place of a double linked list.
165 ***************************************************************************
166 * @ root    : pointer on the list root
167 * @ entry   : pointer on the list-entry to be inserted
168 **************************************************************************/
169static inline void list_add_first( list_entry_t * root, 
170                                   list_entry_t * entry )
171{
172    list_entry_t * next = root->next; 
173
174        entry->next = next;
175        entry->pred = root;
176 
177        root->next = entry;
178        next->pred = entry;
179}
180
181/***************************************************************************
182 * This function must be called by a thread running in local cluster.
183 * It inserts a new entry in last place of a double linked list.
184 ***************************************************************************
185 * @ root    : pointer on the list root
186 * @ entry   : pointer on the list-entry to be inserted
187 **************************************************************************/
188static inline void list_add_last( list_entry_t * root,
189                                  list_entry_t * entry )
190{
191    list_entry_t * pred = root->pred;
192
193        entry->next = root;
194        entry->pred = pred;
195 
196        root->pred = entry;
197        pred->next = entry;
198}
199
200/***************************************************************************
201 * This function must be called by a thread running in local cluster.
202 * It returns true if the list is empty.
203 ***************************************************************************
204 * @ root    : pointer on the list root
205 **************************************************************************/
206static inline bool_t list_is_empty( list_entry_t * root )
207{
208    return ( root == root->next );
209}
210
211
212/***************************************************************************
213 * This function must be called by a thread running in local cluster.
214 * It removes an entry from the list.
215 ***************************************************************************
216 * @ entry : pointer on the entry to be removed.
217 **************************************************************************/
218static inline void list_unlink( list_entry_t * entry )
219{
220        list_entry_t * pred;
221    list_entry_t * next;
222
223        pred = entry->pred;
224        next = entry->next;
225
226        pred->next = next;
227        next->pred = pred;
228}
229
230/***************************************************************************
231 * This function replace an entry in a rooted double linked list.
232 ***************************************************************************
233 * @current  : entry to be removed.
234 * @new      : entry to be introduced.
235 **************************************************************************/
236static inline void list_replace( list_entry_t * current,
237                                 list_entry_t * new )
238{
239    list_entry_t * pred_entry;
240    list_entry_t * next_entry;
241
242        pred_entry = current->pred;
243        next_entry = current->next;
244
245        new->next = next_entry;
246        new->pred = pred_entry;
247
248        pred_entry->next = new;
249        next_entry->pred = new;
250}
251
252/***************************************************************************
253 * This debug function displays all entries of a list.
254 * @ root    : local pointer on the root list_entry_t.
255 * @ string  : list identifier displayed in header.
256 * @ max     : max number of éléments to display.
257 **************************************************************************/
258static inline void list_display( list_entry_t * root,
259                                 char         * string,
260                                 uint32_t       max )
261{
262    list_entry_t * iter;
263    list_entry_t * next;
264    list_entry_t * pred;
265    uint32_t       index;
266
267    next = root->next;
268    pred = root->pred;
269
270    printk("\n***** root (%x) / next (%x) / pred (%x) / %s *****\n",
271    root, next, pred, string );
272
273    if( list_is_empty( root ) == false )
274    {
275        for( iter = next , index = 0 ;
276             (iter != root) && (index < max) ;
277             iter = next , index++ )
278        {
279            next = iter->next;
280                        pred = iter->pred;
281
282            printk(" - %d : iter (%x) / next (%x) / pred (%x)\n",
283            index, iter, next, pred );
284        }
285    }
286}  // end list_display()
287
288
289
290////////////////////////////////////////////////////////////////////////////
291// These functions and macros can be used by any thread running
292// in any cluster to access a remote local list.
293////////////////////////////////////////////////////////////////////////////
294
295/***************************************************************************
296 * This macro can be used by a thread running in any cluster to access
297 * a remote local list. It returns a local pointer on the first element
298 * of the remote list in the remote cluster.
299 ***************************************************************************
300 * @ cxy     : remote list cluster identifier
301 * @ root    : local pointer on the list root
302 * @ type    : type of the linked element
303 * @ member  : name of the list_entry_t field
304 **************************************************************************/
305
306#define LIST_REMOTE_FIRST( cxy , root , type , member )                       \
307    ({ list_entry_t * __first = hal_remote_lpt( XPTR( cxy , &root->next ) );  \
308           LIST_ELEMENT( __first , type , member ); })
309
310/***************************************************************************
311 * This macro can be used by a thread running in any cluster to access
312 * a remote local list. It traverse the list in forward order.
313 * WARNING : Don't use this macro when you want to remove one or several
314 * item(s) from the traversed list.     
315 ***************************************************************************
316 * @ cxy     : remote list cluster identifier
317 * @ root    : pointer on the root list_entry
318 * @ iter    : pointer on the current list_entry
319 **************************************************************************/
320
321#define LIST_REMOTE_FOREACH( cxy , root , iter )               \
322for( (iter) = hal_remote_lpt( XPTR( cxy , &(root)->next ) ) ;  \
323     (iter) != (root) ;                         \
324     (iter) = hal_remote_lpt( XPTR( cxy , &(iter)->next ) ) )
325       
326/***************************************************************************
327 * This function can be called by a thread running in any cluster to access
328 * a remote local list. It returns true if the list is empty.
329 ***************************************************************************
330 * @ cxy     : remote list cluster identifier
331 * @ root    : local pointer on the remote list root
332 **************************************************************************/
333static inline bool_t list_remote_is_empty( cxy_t          cxy,
334                                           list_entry_t * root )
335{
336    list_entry_t * next = hal_remote_lpt( XPTR( cxy , &root->next ) );
337    return( root == next );
338}
339
340/***************************************************************************
341 * This function can be called by a thread running in any cluster to access
342 * a remote local list. It inserts a new entry in first place of the list.
343 ***************************************************************************
344 * @ cxy     : remote list cluster identifier
345 * @ root    : local pointer on the remote list root
346 * @ entry   : local pointer on the remote entry to be inserted
347 **************************************************************************/
348static inline void list_remote_add_first( cxy_t          cxy,
349                                          list_entry_t * root, 
350                                          list_entry_t * entry )
351{
352    list_entry_t * first;    // local pointer on current first entry
353    list_entry_t * next;     // local pointer on current first->next entry
354 
355        first  = hal_remote_lpt( XPTR( cxy , &root->next ) );
356    next   = hal_remote_lpt( XPTR( cxy , &first->next ) );
357       
358        hal_remote_spt( XPTR( cxy , &entry->next ) , first );
359        hal_remote_spt( XPTR( cxy , &entry->pred ) , root );
360 
361        hal_remote_spt( XPTR( cxy , &root->next ) , entry );
362        hal_remote_spt( XPTR( cxy , &next->pred ) , entry );
363}
364
365/***************************************************************************
366 * This function can be called by a thread running in any cluster to access
367 * a remote local list. It inserts a new entry in last place of the list.
368 ***************************************************************************
369 * @ cxy     : remote list cluster identifier
370 * @ root    : local pointer on the remote list root
371 * @ entry   : local pointer on the remote entry to be inserted
372 **************************************************************************/
373static inline void list_remote_add_last( cxy_t          cxy,
374                                         list_entry_t * root, 
375                                         list_entry_t * entry )
376{
377    list_entry_t * last;     // local pointer on current last entry
378    list_entry_t * pred;     // local pointer on current last->pred entry
379 
380        last   = hal_remote_lpt( XPTR( cxy , &root->pred ) );
381    pred   = hal_remote_lpt( XPTR( cxy , &last->pred ) );
382       
383        hal_remote_spt( XPTR( cxy , &entry->next ) , root );
384        hal_remote_spt( XPTR( cxy , &entry->pred ) , pred );
385 
386        hal_remote_spt( XPTR( cxy , &root->pred ) , entry );
387        hal_remote_spt( XPTR( cxy , &pred->next ) , entry );
388}
389
390/***************************************************************************
391 * This function can be called by a thread running in any cluster to access
392 * a remote local list. It removes an entry from the list.
393 ***************************************************************************
394 * @ cxy     : remote list cluster identifier
395 * @ entry   : pointer on the entry to be removed.
396 **************************************************************************/
397static inline void list_remote_unlink( cxy_t          cxy,
398                                       list_entry_t * entry )
399{
400        list_entry_t * pred;
401    list_entry_t * next;
402
403        pred = hal_remote_lpt( XPTR( cxy , &entry->pred ) );
404        next = hal_remote_lpt( XPTR( cxy , &entry->next ) );
405
406        hal_remote_spt( XPTR( cxy , &pred->next ) , next );
407        hal_remote_spt( XPTR( cxy , &next->pred ) , pred );
408}
409
410
411
412#endif  /* _LIST_H_ */
Note: See TracBrowser for help on using the repository browser.