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

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

Fix a bug in list_remote_add_first() and list_remote_add_last() functions,
used by the physical memory allocator, that corrupted the PPM state.

File size: 17.0 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,2018,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_ELEMENT( hal_remote_lpt( XPTR( (cxy) , &(root)->next ) ), \
308                  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 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 macro can be used by a thread running in any cluster to access
328 * a remote local list. It traverse the list in backward order.
329 * WARNING : same as the forward traversal
330 ***************************************************************************
331 * @ cxy       : remote cluster identifier.
332 * @ root      : pointer on the root list_entry.
333 * @ iter      : pointer on the current list_entry.
334 **************************************************************************/
335
336#define LIST_REMOTE_FOREACH_BACKWARD( cxy , root , iter )       \
337for( (iter) = hal_remote_lpt( XPTR( (cxy) , &(root)->pred ) ) ; \
338     (iter) != (root) ;                                         \
339     (iter) = hal_remote_lpt( XPTR( (cxy) , &(iter)->pred ) ) )
340
341/***************************************************************************
342 * This function can be called by a thread running in any cluster to access
343 * a remote local list. It returns true if the list is empty.
344 ***************************************************************************
345 * @ cxy     : remote list cluster identifier
346 * @ root    : local pointer on the remote list root
347 **************************************************************************/
348static inline bool_t list_remote_is_empty( cxy_t          cxy,
349                                           list_entry_t * root )
350{
351    list_entry_t * next = hal_remote_lpt( XPTR( cxy , &root->next ) );
352    return( root == next );
353}
354
355/***************************************************************************
356 * This function can be called by a thread running in any cluster to access
357 * a remote local list. It inserts a new entry in first place of the list.
358 ***************************************************************************
359 * @ cxy     : remote list cluster identifier
360 * @ root    : local pointer on the remote list root
361 * @ entry   : local pointer on the remote entry to be inserted
362 **************************************************************************/
363static inline void list_remote_add_first( cxy_t          cxy,
364                                          list_entry_t * root, 
365                                          list_entry_t * entry )
366{
367    list_entry_t * next = hal_remote_lpt( XPTR( cxy , &root->next ) );
368       
369        hal_remote_spt( XPTR( cxy , &entry->next ) , next );
370        hal_remote_spt( XPTR( cxy , &entry->pred ) , root );
371 
372        hal_remote_spt( XPTR( cxy , &root->next ) , entry );
373        hal_remote_spt( XPTR( cxy , &next->pred ) , entry );
374}
375
376/***************************************************************************
377 * This function can be called by a thread running in any cluster to access
378 * a remote local list. It inserts a new entry in last place of the list.
379 ***************************************************************************
380 * @ cxy     : remote list cluster identifier
381 * @ root    : local pointer on the remote list root
382 * @ entry   : local pointer on the remote entry to be inserted
383 **************************************************************************/
384static inline void list_remote_add_last( cxy_t          cxy,
385                                         list_entry_t * root, 
386                                         list_entry_t * entry )
387{
388    list_entry_t * pred = hal_remote_lpt( XPTR( cxy , &root->pred ) );
389       
390        hal_remote_spt( XPTR( cxy , &entry->next ) , root );
391        hal_remote_spt( XPTR( cxy , &entry->pred ) , pred );
392 
393        hal_remote_spt( XPTR( cxy , &root->pred ) , entry );
394        hal_remote_spt( XPTR( cxy , &pred->next ) , entry );
395}
396
397/***************************************************************************
398 * This function can be called by a thread running in any cluster to access
399 * a remote local list. It removes an entry from the list.
400 ***************************************************************************
401 * @ cxy     : remote list cluster identifier
402 * @ entry   : pointer on the entry to be removed.
403 **************************************************************************/
404static inline void list_remote_unlink( cxy_t          cxy,
405                                       list_entry_t * entry )
406{
407        list_entry_t * pred;
408    list_entry_t * next;
409
410        pred = hal_remote_lpt( XPTR( cxy , &entry->pred ) );
411        next = hal_remote_lpt( XPTR( cxy , &entry->next ) );
412
413        hal_remote_spt( XPTR( cxy , &pred->next ) , next );
414        hal_remote_spt( XPTR( cxy , &next->pred ) , pred );
415}
416
417
418#endif  /* _LIST_H_ */
Note: See TracBrowser for help on using the repository browser.