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