source: trunk/kernel/libk/xhtab.h @ 644

Last change on this file since 644 was 635, checked in by alain, 5 years ago

This version is a major evolution: The physical memory allocators,
defined in the kmem.c, ppm.c, and kcm.c files have been modified
to support remote accesses. The RPCs that were previously user
to allocate physical memory in a remote cluster have been removed.
This has been done to cure a dead-lock in case of concurrent page-faults.

This version 2.2 has been tested on a (4 clusters / 2 cores per cluster)
TSAR architecture, for both the "sort" and the "fft" applications.
File size: 10.5 KB
Line 
1/*
2 * xhtab.h - Remote access embedded hash table definition.
3 *
4 * Author     Alain Greiner  (2016,2017,2018,2019)
5 *
6 * Copyright (c) UPMC Sorbonne Universites
7 *
8 * This file is part of ALMOS-MKH.
9 *
10 * ALMOS-MKH 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-MKH 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-MKH; if not, write to the Free Software Foundation,
21 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24#ifndef _XHTAB_H_
25#define _XHTAB_H_
26
27#include <kernel_config.h>
28#include <hal_kernel_types.h>
29#include <remote_rwlock.h>
30#include <xlist.h>
31
32
33///////////////////////////////////////////////////////////////////////////////////////////
34// This file define a generic, embedded, remotely accessible, hash table.
35//
36// It can be accessed by any thread, running in any cluster.
37// It is generic as it can be used to register various types of items.
38// The main goal is to speedup search by key in a large number of items of same type.
39// For this purpose the set of all registered items is split in several subsets.
40// Each subset is organised as an embedded double linked xlist.
41// - an item is uniquely identified by a <key>, that is a item specific pointer,
42//   that can be a - for example - a char* defining the item "name".
43// - From the <key> value, the hash table uses an item type specific index_from_key()
44//   function, to compute an <index> value, defining a subset of registered items.
45// - to discriminate between items that have the same <index>, the hash table makes
46//   an associative search on the key in subset, using the item type specific
47//   item_match_key() function.
48// - Each registered item is a structure, that must contain an embedded xlist_entry,
49//   that is part of the xlist implementing the subset.
50//
51// For all registered items, a total order is defined by the increasing index values,
52// and for each index value, by the position in the xlist implementing a subset.
53// This order is used by the two functions xhtab_get_first() and xhtab_get_next(), that
54// are used to scan all registered items. The two "current_index" and "current_xlist_xp"
55// fields in the hash table header register the current item during a scan.
56//
57// Implementation Note:
58// To inroduce a new item type, you must define the four item-type-specific
59// functions specified below, and you must update the xhtab_init() function
60// and the xhtab_item_type_t.
61///////////////////////////////////////////////////////////////////////////////////////////
62
63#define XHASHTAB_SIZE    128   // number of subsets
64
65/******************************************************************************************
66 * Here are the four item_type_specific function prototypes that must be defined
67 * for each item type.
68 *****************************************************************************************/
69
70typedef  bool_t    (item_match_key_t)   ( xptr_t item_xp , void * key );
71typedef  xptr_t    (item_from_xlist_t)  ( xptr_t xlist_xp );
72typedef  uint32_t  (index_from_key_t)   ( void * key );
73typedef  void      (item_print_key_t)   ( xptr_t item_xp );
74
75/******************************************************************************************
76 * This define the currently supported item types.
77 * - The XHTAB_DENTRY_TYPE is used to implement the set of directory entries for a
78 *   directory inode : the "children" inode field is an embedded xhtab.
79 *****************************************************************************************/
80
81typedef enum
82{
83    XHTAB_DENTRY_TYPE = 0,                    /*! item is a vfs_dentry_t                 */ 
84}
85xhtab_item_type_t;
86
87/******************************************************************************************
88 * This structure define the root of the remotely accessible hash table.
89 *****************************************************************************************/
90
91typedef struct xhtab_s
92{
93        xlist_entry_t       roots[XHASHTAB_SIZE];  /*! array of roots of xlist               */
94    index_from_key_t  * index_from_key;        /*! item specific function pointer        */
95    item_match_key_t  * item_match_key;        /*! item specific function pointer        */
96    item_from_xlist_t * item_from_xlist;       /*! item specific function pointer        */
97    item_print_key_t  * item_print_key;        /*! item specific function pointer        */
98    uint32_t            items;                 /*! number of registered items            */
99    remote_busylock_t   lock;                  /*! lock protecting hash table accesses   */
100    uint32_t            current_index;         /*! current item subset index             */
101    xptr_t              current_xlist_xp;      /*! xptr on current item xlist entry      */
102}
103xhtab_t;
104
105/******************************************************************************************
106 * This function initializes an empty hash table (zero registered item).
107 * The initialisation must be done by a thread running in cluster containing the table.
108 ******************************************************************************************
109 * @ xhtab    : local pointer on local xhtab to be initialized.
110 * @ type     : item type (see above).
111 *****************************************************************************************/
112void xhtab_init( xhtab_t           * xhtab,
113                 xhtab_item_type_t   type );
114
115/******************************************************************************************
116 * This function safely register an item in the hash table, using the lock protecting it.
117 ******************************************************************************************
118 * @ xhtab_xp   : extended pointer on hash table.
119 * @ key        : local pointer on item identifier.
120 * @ xlist_xp   : extended pointer on xlist_entry_t embedded in item to be registered.
121 * @ return 0 if success / return EINVAL if item already registered.
122 *****************************************************************************************/
123error_t xhtab_insert( xptr_t   xhtab_xp,
124                      void   * key,
125                      xptr_t   xlist_xp );
126
127/******************************************************************************************
128 * This function safely remove an item from the hash table, using the lock protecting it.
129 ******************************************************************************************
130 * @ xhtab_xp   : extended pointer on hash table.
131 * @ key        : local pointer on item identifier.
132 * @ xlist_xp   : extended pointer on xlist_entry embedded in item to be removed.
133 * @ return 0 if item found / return false if item not found.
134 *****************************************************************************************/
135bool_t xhtab_remove( xptr_t   xhtab_xp,
136                     void   * key,
137                     xptr_t   xlist_entry_xp );
138
139/******************************************************************************************
140 * This function search an item by its key in hash table, using the lock protecting it.
141 ******************************************************************************************
142 * @ xhtab_xp  : extended pointer on hash table.
143 * @ key       : local pointer on searched item identifier.
144 * @ return extended pointer on the searched item if found / XPTR_NULL if not found.
145 *****************************************************************************************/
146xptr_t  xhtab_lookup( xptr_t    xhtab_xp,
147                      void    * key );
148
149/******************************************************************************************
150 * This blocking function takes the lock protecting exclusive access to the hash table.
151 * It should be called before the xhtab_get_first() & xhtab_get_next() functions.
152 ******************************************************************************************
153 * @ xhtab_xp  : extended pointer on hash table.
154 *****************************************************************************************/
155void xhtab_lock( xptr_t xhtab_xp );
156
157/******************************************************************************************
158 * This function releases the lock protecting exclusive access to the hash table.
159 * It should be called after the xhtab_get_first() & xhtab_get_next() functions.
160 ******************************************************************************************
161 * @ xhtab_xp  : extended pointer on hash table.
162 *****************************************************************************************/
163void xhtab_unlock( xptr_t xhtab_xp );
164
165/******************************************************************************************
166 * This function returns an extended pointer on the first item registered in hash table,
167 * and register this pointer in the hash table header.
168 * The lock protecting the hash table must have been previously taken by the caller.
169 ******************************************************************************************
170 * @ xhtab_xp  : extended pointer on hash table.
171 * @ return extended pointer on item if success / XPTR_NULL if not found.
172 *****************************************************************************************/
173xptr_t xhtab_get_first( xptr_t xhtab_xp );
174
175/******************************************************************************************
176 * This function returns an extended pointer on item following the currently pointed
177 * item in the hash table header.
178 * The lock protecting the hash table must have been previously taken by the caller.
179 ******************************************************************************************
180 * @ xhtab_xp  : extended pointer on hash table.
181 * @ return extended pointer on item if success / XPTR_NULL if not found.
182 *****************************************************************************************/
183xptr_t xhtab_get_next( xptr_t xhtab_xp );
184
185/******************************************************************************************
186 * This function displays the full content of an xhtab.
187 ******************************************************************************************
188 * @ xhtab_xp  : extended pointer on hash table.
189 *****************************************************************************************/
190void xhtab_display( xptr_t  xhtab_xp );
191
192#endif  /* _XHTAB_H_ */
Note: See TracBrowser for help on using the repository browser.