1 /*---------------------------------------------------------------------------
2 * Pointer Registration Table
3 *
4 *---------------------------------------------------------------------------
5 * Several actions in the driver involve a depth search through all
6 * mappings and arrays referenced from one object, including the detection
7 * of cyclic references.
8 *
9 * This is solved with a two-dimension hash structure, recording every
10 * mapping/array pointer encountered. As the same functionality
11 * is needed in some other places of the driver, too, the whole bunch
12 * of functions are made public.
13 *
14 * The table is used to create a mirror of the array/mapping relations:
15 * every mapping/array is represented by one record, recording an
16 * ID number and how often the represented array/mapping was encountered.
17 *
18 * The entries of the top-level hashtable may be unused, contain plain
19 * records or one of the second-level hashtables. The bit vector hash_usage
20 * keeps track of which entry is what.
21 *
22 * TODO: A generic walk_this_svalue() function should go in here, with
23 * TODO:: a callback foundthis(svalue, ptable, extra), returning
24 * TODO:: true if svalue shall be further descended into.
25 *---------------------------------------------------------------------------
26 */
27
28 #include "driver.h"
29
30 #include <sys/types.h>
31
32 #include "ptrtable.h"
33 #include "mempools.h"
34 #include "simulate.h"
35
36 /*-------------------------------------------------------------------------*/
37
38 #define PTABLE_SIZE 256
39 /* Sice of a pointer table. The value must be a power of 2.
40 */
41
42 /*-------------------------------------------------------------------------*/
43 /* Structure definitions
44 */
45
46 /* One sub table.
47 */
48 struct sub_table
49 {
50 struct pointer_record *records[PTABLE_SIZE];
51 /* The table of hash chains */
52 char used[PTABLE_SIZE / CHAR_BIT];
53 /* Bitvector denoting which record[] entries are valid */
54 };
55
56
57 /* The pointer table base structure.
58 */
59 struct pointer_table
60 {
61 Mempool pool;
62 /* The memory pool from which the table and all structures are
63 * allocated.
64 */
65
66 struct pointer_record *table[PTABLE_SIZE];
67 /* The top-level hashtable.
68 */
69
70 char hash_usage[ PTABLE_SIZE * 2 / CHAR_BIT ];
71 /* Bit vector describing the state of every entry in table[],
72 * two bits each.
73 *
74 * The state of entry table[hash] is described
75 * in hash_usage[(hash/8 ) * 2] and hash_usage[(hash/8) * 2 + 1],
76 * bit hash%8 each. The first bit is true if the associated entry
77 * is in use, the second if the entry holds a sub table.
78 */
79 };
80
81 /*-------------------------------------------------------------------------*/
82 struct pointer_table *
new_pointer_table(void)83 new_pointer_table (void)
84
85 /* Allocate and initialise a new pointer table and return it.
86 */
87
88 {
89 Mempool pool;
90 struct pointer_table *ptable;
91
92 pool = new_mempool(size_mempool(sizeof(struct pointer_record)));
93 if (!pool)
94 return NULL;
95 ptable = mempool_alloc(pool, sizeof(*ptable));
96 if (!ptable)
97 {
98 mempool_delete(pool);
99 return NULL;
100 }
101 memset(ptable->hash_usage, 0, sizeof ptable->hash_usage);
102 memset(ptable->table, 0, sizeof ptable->table);
103 ptable->pool = pool;
104
105 return ptable;
106 } /* new_pointer_table() */
107
108 /*-------------------------------------------------------------------------*/
109 void
free_pointer_table(struct pointer_table * ptable)110 free_pointer_table (struct pointer_table *ptable)
111
112 /* Deallocate the table <ptable> and all referenced memory.
113 */
114
115 {
116 mempool_delete(ptable->pool);
117 } /* free_pointer_table() */
118
119 /*-------------------------------------------------------------------------*/
120 struct pointer_record *
find_add_pointer(struct pointer_table * ptable,void * pointer,Bool bAdd)121 find_add_pointer (struct pointer_table *ptable, void *pointer, Bool bAdd)
122
123 /* Lookup the <pointer> in the <ptable> and return the pointer to its
124 * pointer_record. If the <pointer> is not registered yet and <bAdd> is
125 * false, NULL is returned. Otherwise, a new entry with .ref_count set to -1,
126 * .id_number and .data cleared, is generated and returned.
127 */
128
129 {
130 p_uint key; /* The <pointer> as a normal int */
131 int hash; /* hash computed from <key> aka <pointer> */
132 int mask; /* mask for <hash> in to <usage_p> */
133 char *usage_p; /* First usage vector byte for entry <hash> */
134 struct pointer_record *old; /* Record to add a new one after */
135 struct pointer_record *new; /* New record to add */
136 struct pointer_record **insert; /* Pointer to hashed table entry */
137
138 key = (p_uint)pointer;
139
140 /* Compute the hash value, and the index and mask for
141 * the usage vector
142 */
143
144 /* TODO: This code assumes that a pointer is 32 Bits long */
145 hash = key ^ key >> 16;
146 hash ^= hash >> 8;
147 hash &= (PTABLE_SIZE-1);
148 mask = 1 << (hash & (CHAR_BIT-1));
149 /* TODO: this statement assumes CHAR_BIT == 8 */
150 usage_p = ptable->hash_usage + (hash >> 2 & ~1);
151
152 insert = &(ptable->table[hash]);
153
154 /* Search the pointer among the existing entries.
155 *
156 * The switch() allows an easy way out of the if() when
157 * a new entry has to be generated.
158 */
159
160 old = NULL;
161 if (usage_p[0] & mask) switch (0) { default:
162
163 /* The place in the main hash table has been used before */
164
165 if (usage_p[1] & mask)
166 {
167 /* This place is already used for a sub-table.
168 * Continue the search in there.
169 */
170 struct sub_table *table;
171
172 table = *(struct sub_table**)insert;
173
174 hash = (key ^ key >> 16) & (PTABLE_SIZE-1);
175 mask = 1 << (hash & (CHAR_BIT-1));
176 /* TODO: this statement assumes CHAR_BIT == 8 */
177 usage_p = &table->used[hash >> 3];
178
179 insert = &table->records[hash];
180
181 if ( !(usage_p[0] & mask) )
182 /* need to insert in free place */
183 break;
184
185 old = *insert;
186 do {
187 if (old->key == key)
188 {
189 return old;
190 }
191 } while ( NULL != (old = old->next) );
192 old = *insert;
193 /* need to insert at top of sub hash chain */
194 break;
195 }
196 else
197 {
198 /* The entry is occupied by a record */
199
200 struct sub_table *table;
201 int old_hash;
202
203 old = *insert;
204 if (old->key == key) {
205 return old;
206 }
207
208 if (!bAdd)
209 return NULL;
210
211 /* Hash collision: create a new sub-table. */
212
213 usage_p[1] |= mask;
214
215 table = mempool_alloc(ptable->pool, sizeof *table);
216 if (!table)
217 errorf("(pointertable) Out of memory (%zu bytes pooled) "
218 "for subtable.\n", sizeof *table);
219 *insert = (struct pointer_record *)table;
220 memset(table->used, 0, sizeof table->used);
221
222 /* Put the old entry into the new subtable */
223
224 /* TODO: This code yaddayadda... */
225 old_hash = (old->key ^ old->key >> 16) & (PTABLE_SIZE-1);
226 table->used[old_hash >> 3] |= 1 << (old_hash & (CHAR_BIT-1));
227 table->records[old_hash] = old;
228
229 /* Compute the position for the new entry */
230
231 hash = (key ^ key >> 16) & (PTABLE_SIZE-1);
232 if (hash != old_hash)
233 {
234 old = NULL;
235 }
236 insert = &table->records[hash];
237 mask = 1 << (hash & (CHAR_BIT-1));
238 usage_p = &table->used[hash >> 3];
239 }
240 }
241
242
243 /* Pointer not found in table: create a new entry? */
244 if (!bAdd)
245 return NULL;
246
247 usage_p[0] |= mask;
248 new = mempool_alloc(ptable->pool, sizeof *new);
249 if (!new)
250 errorf("(pointertable) Out of memory (%zu bytes pooled) for "
251 "new entry.\n", sizeof *new);
252 *insert = new;
253 new->key = key;
254 new->next = old;
255 new->ref_count = -1;
256 new->id_number = 0;
257 new->data = NULL;
258
259 return new;
260 } /* find_add_pointer() */
261
262 /*-------------------------------------------------------------------------*/
263 struct pointer_record *
register_pointer(struct pointer_table * ptable,void * pointer)264 register_pointer (struct pointer_table *ptable, void *pointer)
265
266 /* Register the <pointer> in the <ptable>. If it is already in there,
267 * the number of registrations is incremented and the functions returns NULL.
268 * If the pointer is not in the table, a new entry is generated, the
269 * .ref_count, .id_number and .data entry are cleared and the function
270 * returns the new record.
271 */
272
273 {
274 struct pointer_record * prc;
275
276 prc = find_add_pointer(ptable, pointer, MY_TRUE);
277 prc->ref_count++;
278 return (!prc->ref_count ? prc : NULL);
279 } /* register_pointer() */
280
281 /***************************************************************************/
282
283