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

Last change on this file since 452 was 435, checked in by alain, 7 years ago

Fix a bad bug in scheduler...

File size: 12.0 KB
Line 
1/*
2 * xlist.h - Double Circular Linked lists, using extended pointers.
3 *
4 * Author : Alain Greiner (2016)
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 _ALMOS_XLIST_H_
25#define _ALMOS_XLIST_H_
26
27#include <kernel_config.h>
28#include <hal_types.h>
29#include <hal_remote.h>
30
31/**** global variables ***/
32
33cxy_t  local_cxy;
34
35/***************************************************************************
36 * This structure defines an Extended Double Circular Linked List entry.
37 * Note (1) The list root is an extra xlist_entry_t, that is NOT part
38 *          of the set of linked elements.
39 * Note (2) Do NOT change the fields order in this struct.
40 **************************************************************************/
41
42typedef struct xlist_entry_s
43{
44    xptr_t  next;              // extended pointer on next xlist_entry_t
45    xptr_t  pred;              // extended pointer on previous xlist_entry_t
46}
47xlist_entry_t;
48
49/***************************************************************************
50 * This macro returns the offset (in bytes) of a field in a structure.
51 * @ type   : structure type
52 * @ member : name of the field
53 **************************************************************************/
54
55#ifndef OFFSETOF
56#define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member)
57#endif
58
59/***************************************************************************
60 * This macro returns an extended pointer on the structure containing an
61 * embedded xlist_entry_t field.
62 * @ xlist_xp : extended pointer on the xlist_entry_t field
63 * @ type     : type of the structure containing the xlist_entry_t
64 * @ member   : name of the xlist_entry_t field
65 **************************************************************************/
66
67#define XLIST_ELEMENT( xlist_xp , type , member ) \
68    (xlist_xp - OFFSETOF( type , member ))
69
70/***************************************************************************
71 * This macro returns an extended pointer on the first element of an
72 * extended double linked list, identified by the extended pointer on
73 * the root xlist_entry_t.
74 * WARNING : check list non empty before using this macro.
75 * @ root_xp : extended pointer on the root xlist_entry_t
76 * @ type    : type of the linked elements
77 * @ member  : name of the xlist_entry_t field
78 **************************************************************************/
79
80#define XLIST_FIRST_ELEMENT( root_xp , type , member ) \
81    ({ xptr_t __first = hal_remote_lwd( root_xp );     \
82           XLIST_ELEMENT( __first , type , member ); })
83
84/***************************************************************************
85 * This macro returns an extended pointer on the last element of an
86 * extended double linked list, identified by the extended pointer on
87 * the root xlist_entry_t.
88 * WARNING : check list non empty before using this macro.
89 * @ root_xp : extended pointer on the root xlist_entry_t
90 * @ type    : type of the linked elements
91 * @ member  : name of the xlist_entry_t field
92 **************************************************************************/
93
94#define XLIST_LAST_ELEMENT( root_xp , type , member )  \
95    ({ xptr_t __last = hal_remote_lwd( root_xp + 8 );  \
96           XLIST_ELEMENT( __last , type , member ); })
97
98/***************************************************************************
99 * This macro traverses an extended double linked list in forward order.
100 * The iter variable should NOT be deleted during traversal.
101 * @ root_xp  : extended pointer on the root xlist_entry_t
102 * @ iter_xp  : current extended pointer on a xlist_entry_t
103 **************************************************************************/
104
105#define XLIST_FOREACH( root_xp , iter_xp )    \
106for( (iter_xp) = hal_remote_lwd( root_xp ) ;  \
107     (iter_xp) != (root_xp) ;                 \
108     (iter_xp) = hal_remote_lwd( iter_xp ) )
109
110/***************************************************************************
111 * This macro traverses an extended double linked list in backward order.
112 * The iter variable should NOT be deleted during traversal.
113 * @ root_xp  : extended pointer on the root xlist_entry_t
114 * @ iter_xp  : current extended pointer on a xlist_entry_t
115 **************************************************************************/
116
117#define XLIST_FOREACH_BACKWARD( root_xp , iter_xp )  \
118for( (iter_xp) = hal_remote_lwd( (root_xp) + 8 ) ;   \
119     (iter_xp) != (root_xp) ;                        \
120     (iter_xp) = hal_remote_lwd( (iter_xp) + 8 ) )
121
122/***************************************************************************
123 * This function returns an extended pointer on the next xlist_entry_t,
124 * from an extended pointer on a reference xlist_entry_t.
125 * @ root    : extended pointer on the root xlist_entry_t
126 * @ ref     : extended pointer on the reference xlist_entry_t
127 **************************************************************************/
128static inline xptr_t xlist_next( xptr_t  root,
129                                 xptr_t  ref )
130{
131    // get root->next
132    xptr_t root_next = (xptr_t)hal_remote_lwd( root );
133
134    // get ref->next
135    xptr_t ref_next  = (xptr_t)hal_remote_lwd( ref );
136
137    // test if list is empty or ref is the last element 
138    if( (root_next == root) || (ref_next == root) )  return XPTR_NULL;
139   
140        return ref_next;
141}
142
143/***************************************************************************
144 * This function returns an extended pointer on the previous xlist_entry_t.
145 * @ root    : extended pointer on the root xlist_entry_t
146 * @ ref     : extended pointer on the reference xlist_entry_t
147 **************************************************************************/
148static inline xptr_t xlist_pred( xptr_t root,
149                                 xptr_t ref )
150{
151    // get root->next
152    xptr_t root_next = (xptr_t)hal_remote_lwd( root );
153
154    // get ref->pred
155    xptr_t ref_pred  = (xptr_t)hal_remote_lwd( ref + 8 );
156
157    // test if list is empty or ref is the first element 
158    if( (root_next == root) || (ref_pred == root) )  return XPTR_NULL;
159   
160        return ref_pred;
161}
162
163/***************************************************************************
164 * This function initialises the root of an extended double linked list.
165 * The root can be located in any cluster.
166 * @ root_xp   :  extended pointer on the root xlist_entry_t
167 **************************************************************************/
168static inline void xlist_root_init( xptr_t root_xp )
169{
170    hal_remote_swd(  root_xp   , root_xp );
171    hal_remote_swd(  root_xp+8 , root_xp );
172}
173
174/***************************************************************************
175 * This function initialises an entry of an extended double linked list.
176 * The entry can be located in any cluster.
177 * @ entry_xp  : extended pointer on the xlist_entry_t
178 **************************************************************************/
179static inline void xlist_entry_init( xptr_t entry_xp )
180{
181    hal_remote_swd(  entry_xp   , 0 );
182    hal_remote_swd(  entry_xp+8 , 0 );
183}
184
185/***************************************************************************
186 * This function inserts a new entry in the first place of an extended 
187 * double linked list. Four extended pointers must be modified.
188 * The lock protecting the list should have been previously taken.
189 * @ root   : extended pointer on the root xlist_entry_t
190 * @ entry  : extended pointer on the xlist_entry_t to be inserted
191 **************************************************************************/
192static inline void xlist_add_first( xptr_t root, 
193                                    xptr_t entry )
194{
195    // get the extended pointer on the first element in list
196    xptr_t first = (xptr_t)hal_remote_lwd( root );
197
198    // update root.next <= entry
199    hal_remote_swd( root , (uint64_t)entry );
200
201    // update entry.next <= first
202    hal_remote_swd( entry , (uint64_t)first );
203
204    // entry.pred <= root
205    hal_remote_swd( entry + 8 , (uint64_t)root );
206   
207    // first.pred <= new
208    hal_remote_swd( first + 8 , (uint64_t)entry );
209}
210
211/***************************************************************************
212 * This function inserts a new entry in the last place of an extended 
213 * double linked list.  Four extended pointers must be modified.
214 * The lock protecting the list should have been previously taken.
215 * @ root   : extended pointer on the root xlist_entry_t
216 * @ entry  : extended pointer on the xlist_entry_t to be inserted
217 **************************************************************************/
218static inline void xlist_add_last( xptr_t root, 
219                                   xptr_t entry )
220{
221    // get the extended pointer on the last element in list
222    xptr_t last = (xptr_t)hal_remote_lwd( root + 8 );
223
224    // update root.pred <= entry
225    hal_remote_swd( root + 8 , (uint64_t)entry );
226
227    // update entry.pred <= last
228    hal_remote_swd( entry + 8 , (uint64_t)last );
229
230    // entry.next <= root
231    hal_remote_swd( entry , (uint64_t)root );
232   
233    // last.next <= entry
234    hal_remote_swd( last , (uint64_t)entry );
235}
236
237
238/***************************************************************************
239 * This function returns true if the list is empty.
240 * @ root  : extended pointer on the root xlist_entry_t
241 **************************************************************************/
242static inline bool_t xlist_is_empty( xptr_t root )
243{
244    // get the extended pointer root.next value
245    xptr_t next = (xptr_t)hal_remote_lwd( root );
246
247    return ( root == next );
248} 
249
250/***************************************************************************
251 * This function removes an entry from an extended  double linked list.
252 * Two extended pointers must be modified.
253 * The memory allocated to the removed entry is not released.
254 * @ xp : extended pointer on the xlist_entry_t to be removed.
255 **************************************************************************/
256static inline void xlist_unlink( xptr_t xp )
257{
258    // get a local copy of the xlist_entry_t to be removed
259    xlist_entry_t entry;
260    hal_remote_memcpy( XPTR( local_cxy , &entry ) ,
261                                  xp , 
262                                  sizeof(xlist_entry_t) );
263
264    xptr_t next = entry.next;
265    xptr_t pred = entry.pred;
266
267    // update pred.next <= next
268    hal_remote_swd( pred , (uint64_t)next );
269
270    // update next.pred <= pred
271    hal_remote_swd( next + 8 , (uint64_t)pred );
272}
273
274/***************************************************************************
275 * This function replaces an entry in an extended double linked list.
276 * Four extended pointers must be modified.
277 * The memory allocated to the removed entry is not released.
278 * @old      : extended pointer on the xlist_entry_t to be removed.
279 * @new      : extended pointer on the xlist_entry_t to be inserted.
280 **************************************************************************/
281static inline void xlist_replace( xptr_t old,
282                                  xptr_t new )
283{
284    // get a local copy of the xlist_entry_t to be removed
285    xlist_entry_t entry;
286    hal_remote_memcpy( XPTR( local_cxy , &entry ) , 
287                                  old , 
288                                  sizeof(xlist_entry_t) );
289
290    xptr_t next = entry.next;
291    xptr_t pred = entry.pred;
292
293        // update new.next <= next
294    hal_remote_swd( new , (uint64_t)next );
295
296    // update new.pred <= pred
297    hal_remote_swd( new + 8 , (uint64_t)pred );
298
299        // update pred.next <= new
300    hal_remote_swd( pred , (uint64_t)new );
301
302    // update next.pred <= new
303    hal_remote_swd( next + 8 , (uint64_t)new );
304}
305
306#endif  /* _ALMOS_LIST_H_ */
Note: See TracBrowser for help on using the repository browser.