/* * xlist.h - Double Circular Linked lists, using extended pointers. * * Author : Alain Greiner (2016,2017,2018,2019) * * Copyright (c) UPMC Sorbonne Universites * * This file is part of ALMOS-MKH. * * ALMOS-kernel is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; version 2.0 of the License. * * ALMOS-kernel is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with ALMOS-kernel; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */ #ifndef _XLIST_H_ #define _XLIST_H_ #include #include #include #include /**** global variables ***/ cxy_t local_cxy; /*************************************************************************** * This structure defines an Extended Double Circular Linked List entry. * Note (1) The list root is an extra xlist_entry_t, that is NOT part * of the set of linked elements. * Note (2) Do NOT change the fields order in this struct. **************************************************************************/ typedef struct xlist_entry_s { xptr_t next; // extended pointer on next xlist_entry_t xptr_t pred; // extended pointer on previous xlist_entry_t } xlist_entry_t; /*************************************************************************** * This macro returns the offset (in bytes) of a field in a structure. * @ type : structure type * @ member : name of the field **************************************************************************/ #ifndef OFFSETOF #define OFFSETOF( type , member ) ((intptr_t) & ((type *)0)->member) #endif /*************************************************************************** * This macro returns an extended pointer on the structure containing an * embedded xlist_entry_t field. * @ xlist_xp : extended pointer on the xlist_entry_t field * @ type : type of the structure containing the xlist_entry_t * @ member : name of the xlist_entry_t field **************************************************************************/ #define XLIST_ELEMENT( xlist_xp , type , member ) \ (xlist_xp - OFFSETOF( type , member )) /*************************************************************************** * This macro returns an extended pointer on the first element of an * extended double linked list, identified by the extended pointer on * the root xlist_entry_t. * WARNING : check list non empty before using this macro. * @ root_xp : extended pointer on the root xlist_entry_t * @ type : type of the linked elements * @ member : name of the xlist_entry_t field **************************************************************************/ #define XLIST_FIRST( root_xp , type , member ) \ ({ xptr_t __first = hal_remote_l64( root_xp ); \ XLIST_ELEMENT( __first , type , member ); }) /*************************************************************************** * This macro returns an extended pointer on the last element of an * extended double linked list, identified by the extended pointer on * the root xlist_entry_t. * WARNING : check list non empty before using this macro. * @ root_xp : extended pointer on the root xlist_entry_t * @ type : type of the linked elements * @ member : name of the xlist_entry_t field **************************************************************************/ #define XLIST_LAST( root_xp , type , member ) \ ({ xptr_t __last = hal_remote_l64( root_xp + sizeof(xptr_t) ); \ XLIST_ELEMENT( __last , type , member ); }) /*************************************************************************** * This macro traverses an extended double linked list in forward order. * WARNING : the iter variable should NOT be deleted during traversal. * @ root_xp : extended pointer on the root xlist_entry_t * @ iter_xp : current extended pointer on a xlist_entry_t **************************************************************************/ #define XLIST_FOREACH( root_xp , iter_xp ) \ for( (iter_xp) = hal_remote_l64( root_xp ) ; \ (iter_xp) != (root_xp) ; \ (iter_xp) = hal_remote_l64( iter_xp ) ) /*************************************************************************** * This macro traverses an extended double linked list in backward order. * WARNING : the iter variable should NOT be deleted during traversal. * @ root_xp : extended pointer on the root xlist_entry_t * @ iter_xp : current extended pointer on a xlist_entry_t **************************************************************************/ #define XLIST_FOREACH_BACKWARD( root_xp , iter_xp ) \ for( (iter_xp) = hal_remote_l64( (root_xp) + sizeof(xptr_t) ) ; \ (iter_xp) != (root_xp) ; \ (iter_xp) = hal_remote_l64( (iter_xp) + sizeof(xptr_t) ) ) /*************************************************************************** * This function returns an extended pointer on the next xlist_entry_t, * from an extended pointer on a reference xlist_entry_t. * @ root : extended pointer on the root xlist_entry_t * @ ref : extended pointer on the reference xlist_entry_t **************************************************************************/ static inline xptr_t xlist_next( xptr_t root, xptr_t ref ) { // get root->next xptr_t root_next = (xptr_t)hal_remote_l64( root ); // get ref->next xptr_t ref_next = (xptr_t)hal_remote_l64( ref ); // test if list is empty or ref is the last element if( (root_next == root) || (ref_next == root) ) return XPTR_NULL; return ref_next; } /*************************************************************************** * This function returns an extended pointer on the previous xlist_entry_t. * @ root : extended pointer on the root xlist_entry_t * @ ref : extended pointer on the reference xlist_entry_t **************************************************************************/ static inline xptr_t xlist_pred( xptr_t root, xptr_t ref ) { // get root->next xptr_t root_next = (xptr_t)hal_remote_l64( root ); // get ref->pred xptr_t ref_pred = (xptr_t)hal_remote_l64( ref + sizeof(xptr_t) ); // test if list is empty or ref is the first element if( (root_next == root) || (ref_pred == root) ) return XPTR_NULL; return ref_pred; } /*************************************************************************** * This function initialises the root of an extended double linked list. * The root can be located in any cluster. * @ root_xp : extended pointer on the root xlist_entry_t xixi **************************************************************************/ static inline void xlist_root_init( xptr_t root_xp ) { hal_remote_s64( root_xp , root_xp ); hal_remote_s64( root_xp + sizeof(xptr_t) , root_xp ); } /*************************************************************************** * This function initialises an entry of an extended double linked list. * The entry can be located in any cluster. * @ entry_xp : extended pointer on the xlist_entry_t **************************************************************************/ static inline void xlist_entry_init( xptr_t entry_xp ) { hal_remote_s64( entry_xp , 0 ); hal_remote_s64( entry_xp + sizeof(xptr_t) , 0 ); } /*************************************************************************** * This function inserts a new entry in the first place of an extended * double linked list. Four extended pointers must be modified. * The lock protecting the list should have been previously taken. * @ root_xp : extended pointer on the root xlist_entry_t * @ entry_xp : extended pointer on the xlist_entry_t to be inserted **************************************************************************/ static inline void xlist_add_first( xptr_t root_xp, xptr_t entry_xp ) { // get the extended pointer on the first element in list xptr_t first_xp = hal_remote_l64( root_xp ); // update root_xp->next <= entry_xp hal_remote_s64( root_xp , entry_xp ); // update entry_xp->next <= first_xp hal_remote_s64( entry_xp , first_xp ); // update entry_xp->pred <= root_xp hal_remote_s64( entry_xp + sizeof(xptr_t) , root_xp ); // update first_xp->pred <= entry_xp hal_remote_s64( first_xp + sizeof(xptr_t) , entry_xp ); } /*************************************************************************** * This function inserts a new entry in the last place of an extended * double linked list. Four extended pointers must be modified. * The lock protecting the list should have been previously taken. * @ root_xp : extended pointer on the root xlist_entry_t * @ entry_xp : extended pointer on the xlist_entry_t to be inserted **************************************************************************/ static inline void xlist_add_last( xptr_t root_xp, xptr_t entry_xp ) { // get the extended pointer on the last element in list xptr_t last_xp = hal_remote_l64( root_xp + sizeof(xptr_t) ); // update root_xp->pred <= entry_xp hal_remote_s64( root_xp + sizeof(xptr_t) , entry_xp ); // update entry_xp->pred <= last_xp hal_remote_s64( entry_xp + sizeof(xptr_t) , last_xp ); // update entry_xp->next <= root_xp hal_remote_s64( entry_xp , root_xp ); // update last_xp->next <= entry_xp hal_remote_s64( last_xp , entry_xp ); } /*************************************************************************** * This function returns true if the list is empty. * @ root_xp : extended pointer on the root xlist_entry_t. **************************************************************************/ static inline bool_t xlist_is_empty( xptr_t root_xp ) { // get the extended pointer root.next value xptr_t next = (xptr_t)hal_remote_l64( root_xp ); return ( root_xp == next ); } /*************************************************************************** * This function removes an entry from an extended double linked list. * Two extended pointers must be modified. * The memory allocated to the removed entry is not released. * @ xp : extended pointer on the xlist_entry_t to be removed. **************************************************************************/ static inline void xlist_unlink( xptr_t xp ) { // get a local copy of the xlist_entry_t to be removed xlist_entry_t entry; hal_remote_memcpy( XPTR( local_cxy , &entry ) , xp , sizeof(xlist_entry_t) ); xptr_t next = entry.next; xptr_t pred = entry.pred; // update pred.next <= next hal_remote_s64( pred , (uint64_t)next ); // update next.pred <= pred hal_remote_s64( next + sizeof(xptr_t) , (uint64_t)pred ); } /*************************************************************************** * This function replaces an entry in an extended double linked list. * Four extended pointers must be modified. * The memory allocated to the removed entry is not released. * @ old : extended pointer on the xlist_entry_t to be removed. * @ new : extended pointer on the xlist_entry_t to be inserted. **************************************************************************/ static inline void xlist_replace( xptr_t old, xptr_t new ) { // get a local copy of the xlist_entry_t to be removed xlist_entry_t entry; hal_remote_memcpy( XPTR( local_cxy , &entry ) , old , sizeof(xlist_entry_t) ); xptr_t next = entry.next; xptr_t pred = entry.pred; // update new.next <= next hal_remote_s64( new , (uint64_t)next ); // update new.pred <= pred hal_remote_s64( new + sizeof(xptr_t) , (uint64_t)pred ); // update pred.next <= new hal_remote_s64( pred , (uint64_t)new ); // update next.pred <= new hal_remote_s64( next + sizeof(xptr_t) , (uint64_t)new ); } /*************************************************************************** * This debug function displays all entries of an xlist. * @ root_xp : extended pointer on the root xlist_entry_t. * @ string : list identifier displayed in header. * @ max : max number of éléments to display. **************************************************************************/ static inline void xlist_display( xptr_t root_xp, char * string, uint32_t max ) { cxy_t root_cxy; xlist_entry_t * root_ptr; xptr_t iter_xp; cxy_t iter_cxy; xlist_entry_t * iter_ptr; xptr_t next_xp; cxy_t next_cxy; xlist_entry_t * next_ptr; xptr_t pred_xp; cxy_t pred_cxy; xlist_entry_t * pred_ptr; uint32_t index; root_cxy = GET_CXY( root_xp ); root_ptr = GET_PTR( root_xp ); next_xp = hal_remote_l64( XPTR( root_cxy , &root_ptr->next ) ); next_cxy = GET_CXY( next_xp ); next_ptr = GET_PTR( next_xp ); pred_xp = hal_remote_l64( XPTR( root_cxy , &root_ptr->pred ) ); pred_cxy = GET_CXY( pred_xp ); pred_ptr = GET_PTR( pred_xp ); printk("\n***** root (%x,%x) / next (%x,%x) / pred (%x,%x) / %s *****\n", root_cxy, root_ptr, next_cxy, next_ptr, pred_cxy, pred_ptr, string ); if( xlist_is_empty( root_xp ) == false ) { for( iter_xp = hal_remote_l64( XPTR( root_cxy , &root_ptr->next) ) , index = 0 ; (iter_xp != root_xp) && (index < max) ; iter_xp = next_xp , index++ ) { iter_cxy = GET_CXY( iter_xp ); iter_ptr = GET_PTR( iter_xp ); next_xp = hal_remote_l64( XPTR( iter_cxy , &iter_ptr->next ) ); next_cxy = GET_CXY( next_xp ); next_ptr = GET_PTR( next_xp ); pred_xp = hal_remote_l64( XPTR( iter_cxy , &iter_ptr->pred ) ); pred_cxy = GET_CXY( pred_xp ); pred_ptr = GET_PTR( pred_xp ); printk(" - %d : iter (%x,%x) / next (%x,%x) / pred (%x,%x)\n", index, iter_cxy, iter_ptr, next_cxy, next_ptr, pred_cxy, pred_ptr ); } } } // end xlist_display() #endif /* _XLIST_H_ */