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

Last change on this file since 666 was 666, checked in by alain, 14 months ago

Cosmetic.

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