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

Last change on this file since 576 was 563, checked in by alain, 6 years ago

Complete restructuration of kernel spinlocks.

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