source: trunk/kernel/libk/xlist.h @ 645

Last change on this file since 645 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: 14.5 KB
Line 
1/*
2 * xlist.h - Double Circular Linked lists, using extended pointers.
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-kernel 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-kernel 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-kernel; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#ifndef _XLIST_H_
25#define _XLIST_H_
26
27#include <kernel_config.h>
28#include <hal_kernel_types.h>
29#include <hal_remote.h>
30#include <printk.h>
31
32/**** global variables ***/
33
34cxy_t  local_cxy;
35
36/***************************************************************************
37 * This structure defines an Extended Double Circular Linked List entry.
38 * Note (1) The list root is an extra xlist_entry_t, that is NOT part
39 *          of the set of linked elements.
40 * Note (2) Do NOT change the fields order in this struct.
41 **************************************************************************/
42
43typedef struct xlist_entry_s
44{
45    xptr_t  next;              // extended pointer on next xlist_entry_t
46    xptr_t  pred;              // extended pointer on previous xlist_entry_t
47}
48xlist_entry_t;
49
50/***************************************************************************
51 * This macro returns the offset (in bytes) of a field in a structure.
52 * @ type   : structure type
53 * @ member : name of the field
54 **************************************************************************/
55
56#ifndef OFFSETOF
57#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
58#endif
59
60/***************************************************************************
61 * This macro returns an extended pointer on the structure containing an
62 * embedded xlist_entry_t field.
63 * @ xlist_xp : extended pointer on the xlist_entry_t field
64 * @ type     : type of the structure containing the xlist_entry_t
65 * @ member   : name of the xlist_entry_t field
66 **************************************************************************/
67
68#define XLIST_ELEMENT( xlist_xp , type , member ) \
69    (xlist_xp - OFFSETOF( type , member ))
70
71/***************************************************************************
72 * This macro returns an extended pointer on the first element of an
73 * extended double linked list, identified by the extended pointer on
74 * the root xlist_entry_t.
75 * WARNING : check list non empty before using this macro.
76 * @ root_xp : extended pointer on the root xlist_entry_t
77 * @ type    : type of the linked elements
78 * @ member  : name of the xlist_entry_t field
79 **************************************************************************/
80
81#define XLIST_FIRST( root_xp , type , member )       \
82    ({ xptr_t __first = hal_remote_l64( root_xp );   \
83           XLIST_ELEMENT( __first , type , member ); })
84
85/***************************************************************************
86 * This macro returns an extended pointer on the last element of an
87 * extended double linked list, identified by the extended pointer on
88 * the root xlist_entry_t.
89 * WARNING : check list non empty before using this macro.
90 * @ root_xp : extended pointer on the root xlist_entry_t
91 * @ type    : type of the linked elements
92 * @ member  : name of the xlist_entry_t field
93 **************************************************************************/
94
95#define XLIST_LAST( root_xp , type , member )                       \
96    ({ xptr_t __last = hal_remote_l64( root_xp + sizeof(xptr_t) );  \
97           XLIST_ELEMENT( __last , type , member ); })
98
99/***************************************************************************
100 * This macro traverses an extended double linked list in forward order.
101 * WARNING : the iter variable should NOT be deleted during traversal.
102 * @ root_xp  : extended pointer on the root xlist_entry_t
103 * @ iter_xp  : current extended pointer on a xlist_entry_t
104 **************************************************************************/
105
106#define XLIST_FOREACH( root_xp , iter_xp )    \
107for( (iter_xp) = hal_remote_l64( root_xp ) ;  \
108     (iter_xp) != (root_xp) ;                 \
109     (iter_xp) = hal_remote_l64( iter_xp ) )
110
111/***************************************************************************
112 * This macro traverses an extended double linked list in backward order.
113 * WARNING : the iter variable should NOT be deleted during traversal.
114 * @ root_xp  : extended pointer on the root xlist_entry_t
115 * @ iter_xp  : current extended pointer on a xlist_entry_t
116 **************************************************************************/
117
118#define XLIST_FOREACH_BACKWARD( root_xp , iter_xp )              \
119for( (iter_xp) = hal_remote_l64( (root_xp) + sizeof(xptr_t) ) ;  \
120     (iter_xp) != (root_xp) ;                                    \
121     (iter_xp) = hal_remote_l64( (iter_xp) + sizeof(xptr_t) ) )
122
123/***************************************************************************
124 * This function returns an extended pointer on the next xlist_entry_t,
125 * from an extended pointer on a reference xlist_entry_t.
126 * @ root    : extended pointer on the root xlist_entry_t
127 * @ ref     : extended pointer on the reference xlist_entry_t
128 **************************************************************************/
129static inline xptr_t xlist_next( xptr_t  root,
130                                 xptr_t  ref )
131{
132    // get root->next
133    xptr_t root_next = (xptr_t)hal_remote_l64( root );
134
135    // get ref->next
136    xptr_t ref_next  = (xptr_t)hal_remote_l64( ref );
137
138    // test if list is empty or ref is the last element 
139    if( (root_next == root) || (ref_next == root) )  return XPTR_NULL;
140   
141        return ref_next;
142}
143
144/***************************************************************************
145 * This function returns an extended pointer on the previous xlist_entry_t.
146 * @ root    : extended pointer on the root xlist_entry_t
147 * @ ref     : extended pointer on the reference xlist_entry_t
148 **************************************************************************/
149static inline xptr_t xlist_pred( xptr_t root,
150                                 xptr_t ref )
151{
152    // get root->next
153    xptr_t root_next = (xptr_t)hal_remote_l64( root );
154
155    // get ref->pred
156    xptr_t ref_pred  = (xptr_t)hal_remote_l64( ref + sizeof(xptr_t) );
157
158    // test if list is empty or ref is the first element 
159    if( (root_next == root) || (ref_pred == root) )  return XPTR_NULL;
160   
161        return ref_pred;
162}
163
164/***************************************************************************
165 * This function initialises the root of an extended double linked list.
166 * The root can be located in any cluster.
167 * @ root_xp   :  extended pointer on the root xlist_entry_t
168xixi **************************************************************************/
169static inline void xlist_root_init( xptr_t root_xp )
170{
171    hal_remote_s64( root_xp                  , root_xp );
172    hal_remote_s64( root_xp + sizeof(xptr_t) , root_xp );
173}
174
175/***************************************************************************
176 * This function initialises an entry of an extended double linked list.
177 * The entry can be located in any cluster.
178 * @ entry_xp  : extended pointer on the xlist_entry_t
179 **************************************************************************/
180static inline void xlist_entry_init( xptr_t entry_xp )
181{
182    hal_remote_s64( entry_xp                  , 0 );
183    hal_remote_s64( entry_xp + sizeof(xptr_t) , 0 );
184}
185
186/***************************************************************************
187 * This function inserts a new entry in the first place of an extended 
188 * double linked list. Four extended pointers must be modified.
189 * The lock protecting the list should have been previously taken.
190 * @ root_xp   : extended pointer on the root xlist_entry_t
191 * @ entry_xp  : extended pointer on the xlist_entry_t to be inserted
192 **************************************************************************/
193static inline void xlist_add_first( xptr_t root_xp, 
194                                    xptr_t entry_xp )
195{
196    // get the extended pointer on the first element in list
197    xptr_t first_xp = hal_remote_l64( root_xp );
198
199    // update root_xp->next <= entry_xp
200    hal_remote_s64( root_xp , entry_xp );
201
202    // update entry_xp->next <= first_xp
203    hal_remote_s64( entry_xp , first_xp );
204
205    // update entry_xp->pred <= root_xp
206    hal_remote_s64( entry_xp + sizeof(xptr_t) , root_xp );
207   
208    // update first_xp->pred <= entry_xp
209    hal_remote_s64( first_xp + sizeof(xptr_t) , entry_xp );
210}
211
212/***************************************************************************
213 * This function inserts a new entry in the last place of an extended 
214 * double linked list.  Four extended pointers must be modified.
215 * The lock protecting the list should have been previously taken.
216 * @ root_xp   : extended pointer on the root xlist_entry_t
217 * @ entry_xp  : extended pointer on the xlist_entry_t to be inserted
218 **************************************************************************/
219static inline void xlist_add_last( xptr_t root_xp, 
220                                   xptr_t entry_xp )
221{
222    // get the extended pointer on the last element in list
223    xptr_t last_xp = hal_remote_l64( root_xp + sizeof(xptr_t) );
224
225    // update root_xp->pred <= entry_xp
226    hal_remote_s64( root_xp + sizeof(xptr_t) , entry_xp );
227
228    // update entry_xp->pred <= last_xp
229    hal_remote_s64( entry_xp + sizeof(xptr_t) , last_xp );
230
231    // update entry_xp->next <= root_xp
232    hal_remote_s64( entry_xp , root_xp );
233   
234    // update last_xp->next <= entry_xp
235    hal_remote_s64( last_xp , entry_xp );
236}
237
238
239/***************************************************************************
240 * This function returns true if the list is empty.
241 * @ root_xp  : extended pointer on the root xlist_entry_t.
242 **************************************************************************/
243static inline bool_t xlist_is_empty( xptr_t root_xp )
244{
245    // get the extended pointer root.next value
246    xptr_t next = (xptr_t)hal_remote_l64( root_xp );
247
248    return ( root_xp == next );
249} 
250
251/***************************************************************************
252 * This function removes an entry from an extended  double linked list.
253 * Two extended pointers must be modified.
254 * The memory allocated to the removed entry is not released.
255 * @ xp : extended pointer on the xlist_entry_t to be removed.
256 **************************************************************************/
257static inline void xlist_unlink( xptr_t xp )
258{
259    // get a local copy of the xlist_entry_t to be removed
260    xlist_entry_t entry;
261    hal_remote_memcpy( XPTR( local_cxy , &entry ) ,
262                       xp , 
263                       sizeof(xlist_entry_t) );
264
265    xptr_t next = entry.next;
266    xptr_t pred = entry.pred;
267
268    // update pred.next <= next
269    hal_remote_s64( pred , (uint64_t)next );
270
271    // update next.pred <= pred
272    hal_remote_s64( next + sizeof(xptr_t) , (uint64_t)pred );
273}
274
275/***************************************************************************
276 * This function replaces an entry in an extended double linked list.
277 * Four extended pointers must be modified.
278 * The memory allocated to the removed entry is not released.
279 * @ old      : extended pointer on the xlist_entry_t to be removed.
280 * @ new      : extended pointer on the xlist_entry_t to be inserted.
281 **************************************************************************/
282static inline void xlist_replace( xptr_t old,
283                                  xptr_t new )
284{
285    // get a local copy of the xlist_entry_t to be removed
286    xlist_entry_t entry;
287    hal_remote_memcpy( XPTR( local_cxy , &entry ) , 
288                                  old , 
289                                  sizeof(xlist_entry_t) );
290
291    xptr_t next = entry.next;
292    xptr_t pred = entry.pred;
293
294        // update new.next <= next
295    hal_remote_s64( new , (uint64_t)next );
296
297    // update new.pred <= pred
298    hal_remote_s64( new + sizeof(xptr_t) , (uint64_t)pred );
299
300        // update pred.next <= new
301    hal_remote_s64( pred , (uint64_t)new );
302
303    // update next.pred <= new
304    hal_remote_s64( next + sizeof(xptr_t) , (uint64_t)new );
305}
306
307/***************************************************************************
308 * This debug function displays all entries of an xlist.
309 * @ root_xp : extended pointer on the root xlist_entry_t.
310 * @ string  : list identifier displayed in header.
311 * @ max     : max number of éléments to display.
312 **************************************************************************/
313static inline void xlist_display( xptr_t  root_xp,
314                                  char  * string,
315                                  uint32_t max )
316{
317    cxy_t           root_cxy;
318    xlist_entry_t * root_ptr;
319
320    xptr_t          iter_xp;
321    cxy_t           iter_cxy;
322    xlist_entry_t * iter_ptr;
323
324    xptr_t          next_xp;
325    cxy_t           next_cxy;
326    xlist_entry_t * next_ptr;
327
328    xptr_t          pred_xp;
329    cxy_t           pred_cxy;
330    xlist_entry_t * pred_ptr;
331
332    uint32_t        index;
333
334    root_cxy = GET_CXY( root_xp );
335    root_ptr = GET_PTR( root_xp );
336
337    next_xp  = hal_remote_l64( XPTR( root_cxy , &root_ptr->next ) );
338    next_cxy = GET_CXY( next_xp );
339    next_ptr = GET_PTR( next_xp );
340
341    pred_xp  = hal_remote_l64( XPTR( root_cxy , &root_ptr->pred ) );
342    pred_cxy = GET_CXY( pred_xp );
343    pred_ptr = GET_PTR( pred_xp );
344
345    printk("\n***** root (%x,%x) / next (%x,%x) / pred (%x,%x) / %s *****\n",
346    root_cxy, root_ptr, next_cxy, next_ptr, pred_cxy, pred_ptr, string );
347
348    if( xlist_is_empty( root_xp ) == false )
349    {
350        for( iter_xp = hal_remote_l64( XPTR( root_cxy , &root_ptr->next) ) , index = 0 ;
351             (iter_xp != root_xp) && (index < max) ;
352             iter_xp = next_xp , index++ )
353        {
354            iter_cxy = GET_CXY( iter_xp );
355            iter_ptr = GET_PTR( iter_xp );
356
357            next_xp  = hal_remote_l64( XPTR( iter_cxy , &iter_ptr->next ) );
358            next_cxy = GET_CXY( next_xp );
359            next_ptr = GET_PTR( next_xp );
360
361            pred_xp  = hal_remote_l64( XPTR( iter_cxy , &iter_ptr->pred ) );
362            pred_cxy = GET_CXY( pred_xp );
363            pred_ptr = GET_PTR( pred_xp );
364
365            printk(" - %d : iter (%x,%x) / next (%x,%x) / pred (%x,%x)\n",
366            index, iter_cxy, iter_ptr, next_cxy, next_ptr, pred_cxy, pred_ptr );
367        }
368    }
369}  // end xlist_display()
370
371#endif  /* _XLIST_H_ */
Note: See TracBrowser for help on using the repository browser.