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

Last change on this file since 610 was 610, checked in by alain, 11 months ago

Fix several bugs in VFS to support the following
ksh commandis : cp, mv, rm, mkdir, cd, pwd

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