1 /* Sparse Arrays for Objective C dispatch tables
2 Copyright (C) 1993-2016 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 Under Section 7 of GPL version 3, you are granted additional
17 permissions described in the GCC Runtime Library Exception, version
18 3.1, as published by the Free Software Foundation.
19
20 You should have received a copy of the GNU General Public License and
21 a copy of the GCC Runtime Library Exception along with this program;
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 <http://www.gnu.org/licenses/>. */
24
25 #include "objc-private/common.h"
26 #include "objc-private/sarray.h"
27 #include "objc/runtime.h" /* For objc_malloc */
28 #include "objc/thr.h" /* For objc_mutex_lock */
29 #include "objc-private/module-abi-8.h"
30 #include "objc-private/runtime.h"
31 #include <stdio.h>
32 #include <string.h> /* For memset */
33 #include <assert.h> /* For assert */
34
35 int nbuckets = 0; /* !T:MUTEX */
36 int nindices = 0; /* !T:MUTEX */
37 int narrays = 0; /* !T:MUTEX */
38 int idxsize = 0; /* !T:MUTEX */
39
40 static void *first_free_data = NULL; /* !T:MUTEX */
41
42 #ifdef OBJC_SPARSE2
43 const char *__objc_sparse2_id = "2 level sparse indices";
44 #endif
45
46 #ifdef OBJC_SPARSE3
47 const char *__objc_sparse3_id = "3 level sparse indices";
48 #endif
49
50 /* This function removes any structures left over from free operations
51 that were not safe in a multi-threaded environment. */
52 void
sarray_remove_garbage(void)53 sarray_remove_garbage (void)
54 {
55 void **vp;
56 void *np;
57
58 objc_mutex_lock (__objc_runtime_mutex);
59
60 vp = first_free_data;
61 first_free_data = NULL;
62
63 while (vp)
64 {
65 np = *vp;
66 objc_free (vp);
67 vp = np;
68 }
69
70 objc_mutex_unlock (__objc_runtime_mutex);
71 }
72
73 /* Free a block of dynamically allocated memory. If we are in
74 multi-threaded mode, it is ok to free it. If not, we add it to the
75 garbage heap to be freed later. */
76 static void
sarray_free_garbage(void * vp)77 sarray_free_garbage (void *vp)
78 {
79 objc_mutex_lock (__objc_runtime_mutex);
80
81 if (__objc_runtime_threads_alive == 1)
82 {
83 objc_free (vp);
84 if (first_free_data)
85 sarray_remove_garbage ();
86 }
87 else
88 {
89 *(void **)vp = first_free_data;
90 first_free_data = vp;
91 }
92
93 objc_mutex_unlock (__objc_runtime_mutex);
94 }
95
96 /* sarray_at_put copies data in such a way as to be thread reader
97 safe. */
98 void
sarray_at_put(struct sarray * array,sidx index,void * element)99 sarray_at_put (struct sarray *array, sidx index, void *element)
100 {
101 #ifdef OBJC_SPARSE3
102 struct sindex **the_index;
103 struct sindex *new_index;
104 #endif
105 struct sbucket **the_bucket;
106 struct sbucket *new_bucket;
107 #ifdef OBJC_SPARSE3
108 size_t ioffset;
109 #endif
110 size_t boffset;
111 size_t eoffset;
112 #ifdef PRECOMPUTE_SELECTORS
113 union sofftype xx;
114 xx.idx = index;
115 #ifdef OBJC_SPARSE3
116 ioffset = xx.off.ioffset;
117 #endif
118 boffset = xx.off.boffset;
119 eoffset = xx.off.eoffset;
120 #else /* not PRECOMPUTE_SELECTORS */
121 #ifdef OBJC_SPARSE3
122 ioffset = index/INDEX_CAPACITY;
123 boffset = (index/BUCKET_SIZE)%INDEX_SIZE;
124 eoffset = index%BUCKET_SIZE;
125 #else
126 boffset = index/BUCKET_SIZE;
127 eoffset = index%BUCKET_SIZE;
128 #endif
129 #endif /* not PRECOMPUTE_SELECTORS */
130
131 assert (soffset_decode (index) < array->capacity); /* Range check */
132
133 #ifdef OBJC_SPARSE3
134 the_index = &(array->indices[ioffset]);
135 the_bucket = &((*the_index)->buckets[boffset]);
136 #else
137 the_bucket = &(array->buckets[boffset]);
138 #endif
139
140 if ((*the_bucket)->elems[eoffset] == element)
141 return; /* Great! we just avoided a lazy copy. */
142
143 #ifdef OBJC_SPARSE3
144
145 /* First, perform lazy copy/allocation of index if needed. */
146
147 if ((*the_index) == array->empty_index)
148 {
149 /* The index was previously empty, allocate a new. */
150 new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
151 memcpy (new_index, array->empty_index, sizeof (struct sindex));
152 new_index->version.version = array->version.version;
153 *the_index = new_index; /* Prepared for install. */
154 the_bucket = &((*the_index)->buckets[boffset]);
155
156 nindices += 1;
157 }
158 else if ((*the_index)->version.version != array->version.version)
159 {
160 /* This index must be lazy copied. */
161 struct sindex *old_index = *the_index;
162 new_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
163 memcpy (new_index, old_index, sizeof (struct sindex));
164 new_index->version.version = array->version.version;
165 *the_index = new_index; /* Prepared for install. */
166 the_bucket = &((*the_index)->buckets[boffset]);
167
168 nindices += 1;
169 }
170
171 #endif /* OBJC_SPARSE3 */
172
173 /* Next, perform lazy allocation/copy of the bucket if needed. */
174 if ((*the_bucket) == array->empty_bucket)
175 {
176 /* The bucket was previously empty (or something like that),
177 allocate a new. This is the effect of `lazy' allocation. */
178 new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
179 memcpy ((void *) new_bucket, (const void *) array->empty_bucket,
180 sizeof (struct sbucket));
181 new_bucket->version.version = array->version.version;
182 *the_bucket = new_bucket; /* Prepared for install. */
183
184 nbuckets += 1;
185
186 }
187 else if ((*the_bucket)->version.version != array->version.version)
188 {
189 /* Perform lazy copy. */
190 struct sbucket *old_bucket = *the_bucket;
191 new_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
192 memcpy (new_bucket, old_bucket, sizeof (struct sbucket));
193 new_bucket->version.version = array->version.version;
194 *the_bucket = new_bucket; /* Prepared for install. */
195
196 nbuckets += 1;
197 }
198 (*the_bucket)->elems[eoffset] = element;
199 }
200
201 void
sarray_at_put_safe(struct sarray * array,sidx index,void * element)202 sarray_at_put_safe (struct sarray *array, sidx index, void *element)
203 {
204 if (soffset_decode (index) >= array->capacity)
205 sarray_realloc (array, soffset_decode (index) + 1);
206 sarray_at_put (array, index, element);
207 }
208
209 struct sarray *
sarray_new(int size,void * default_element)210 sarray_new (int size, void *default_element)
211 {
212 struct sarray *arr;
213 #ifdef OBJC_SPARSE3
214 size_t num_indices = ((size - 1)/(INDEX_CAPACITY)) + 1;
215 struct sindex **new_indices;
216 #else /* OBJC_SPARSE2 */
217 size_t num_indices = ((size - 1)/BUCKET_SIZE) + 1;
218 struct sbucket **new_buckets;
219 #endif
220 size_t counter;
221
222 assert (size > 0);
223
224 /* Allocate core array. */
225 arr = (struct sarray *) objc_malloc (sizeof (struct sarray));
226 arr->version.version = 0;
227
228 /* Initialize members. */
229 #ifdef OBJC_SPARSE3
230 arr->capacity = num_indices*INDEX_CAPACITY;
231 new_indices = (struct sindex **)
232 objc_malloc (sizeof (struct sindex *) * num_indices);
233
234 arr->empty_index = (struct sindex *) objc_malloc (sizeof (struct sindex));
235 arr->empty_index->version.version = 0;
236
237 narrays += 1;
238 idxsize += num_indices;
239 nindices += 1;
240
241 #else /* OBJC_SPARSE2 */
242 arr->capacity = num_indices*BUCKET_SIZE;
243 new_buckets = (struct sbucket **)
244 objc_malloc (sizeof (struct sbucket *) * num_indices);
245
246 narrays += 1;
247 idxsize += num_indices;
248
249 #endif
250
251 arr->empty_bucket = (struct sbucket *) objc_malloc (sizeof (struct sbucket));
252 arr->empty_bucket->version.version = 0;
253
254 nbuckets += 1;
255
256 arr->ref_count = 1;
257 arr->is_copy_of = (struct sarray *) 0;
258
259 for (counter = 0; counter < BUCKET_SIZE; counter++)
260 arr->empty_bucket->elems[counter] = default_element;
261
262 #ifdef OBJC_SPARSE3
263 for (counter = 0; counter < INDEX_SIZE; counter++)
264 arr->empty_index->buckets[counter] = arr->empty_bucket;
265
266 for (counter = 0; counter < num_indices; counter++)
267 new_indices[counter] = arr->empty_index;
268
269 #else /* OBJC_SPARSE2 */
270
271 for (counter = 0; counter < num_indices; counter++)
272 new_buckets[counter] = arr->empty_bucket;
273
274 #endif
275
276 #ifdef OBJC_SPARSE3
277 arr->indices = new_indices;
278 #else /* OBJC_SPARSE2 */
279 arr->buckets = new_buckets;
280 #endif
281
282 return arr;
283 }
284
285
286 /* Reallocate the sparse array to hold `newsize' entries Note: We
287 really allocate and then free. We have to do this to ensure that
288 any concurrent readers notice the update. */
289 void
sarray_realloc(struct sarray * array,int newsize)290 sarray_realloc (struct sarray *array, int newsize)
291 {
292 #ifdef OBJC_SPARSE3
293 size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
294 size_t new_max_index = ((newsize - 1)/INDEX_CAPACITY);
295 size_t rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
296
297 struct sindex **new_indices;
298 struct sindex **old_indices;
299
300 #else /* OBJC_SPARSE2 */
301 size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
302 size_t new_max_index = ((newsize - 1)/BUCKET_SIZE);
303 size_t rounded_size = (new_max_index + 1) * BUCKET_SIZE;
304
305 struct sbucket **new_buckets;
306 struct sbucket **old_buckets;
307
308 #endif
309
310 size_t counter;
311
312 assert (newsize > 0);
313
314 /* The size is the same, just ignore the request. */
315 if (rounded_size <= array->capacity)
316 return;
317
318 assert (array->ref_count == 1); /* stop if lazy copied... */
319
320 /* We are asked to extend the array -- allocate new bucket table,
321 and insert empty_bucket in newly allocated places. */
322 if (rounded_size > array->capacity)
323 {
324 #ifdef OBJC_SPARSE3
325 new_max_index += 4;
326 rounded_size = (new_max_index + 1) * INDEX_CAPACITY;
327 #else /* OBJC_SPARSE2 */
328 new_max_index += 4;
329 rounded_size = (new_max_index + 1) * BUCKET_SIZE;
330 #endif
331
332 /* Update capacity. */
333 array->capacity = rounded_size;
334
335 #ifdef OBJC_SPARSE3
336 /* Alloc to force re-read by any concurrent readers. */
337 old_indices = array->indices;
338 new_indices = (struct sindex **)
339 objc_malloc ((new_max_index + 1) * sizeof (struct sindex *));
340 #else /* OBJC_SPARSE2 */
341 old_buckets = array->buckets;
342 new_buckets = (struct sbucket **)
343 objc_malloc ((new_max_index + 1) * sizeof (struct sbucket *));
344 #endif
345
346 /* Copy buckets below old_max_index (they are still valid). */
347 for (counter = 0; counter <= old_max_index; counter++ )
348 {
349 #ifdef OBJC_SPARSE3
350 new_indices[counter] = old_indices[counter];
351 #else /* OBJC_SPARSE2 */
352 new_buckets[counter] = old_buckets[counter];
353 #endif
354 }
355
356 #ifdef OBJC_SPARSE3
357 /* Reset entries above old_max_index to empty_bucket. */
358 for (counter = old_max_index + 1; counter <= new_max_index; counter++)
359 new_indices[counter] = array->empty_index;
360 #else /* OBJC_SPARSE2 */
361 /* Reset entries above old_max_index to empty_bucket. */
362 for (counter = old_max_index + 1; counter <= new_max_index; counter++)
363 new_buckets[counter] = array->empty_bucket;
364 #endif
365
366 #ifdef OBJC_SPARSE3
367 /* Install the new indices. */
368 array->indices = new_indices;
369 #else /* OBJC_SPARSE2 */
370 array->buckets = new_buckets;
371 #endif
372
373 #ifdef OBJC_SPARSE3
374 /* Free the old indices. */
375 sarray_free_garbage (old_indices);
376 #else /* OBJC_SPARSE2 */
377 sarray_free_garbage (old_buckets);
378 #endif
379
380 idxsize += (new_max_index-old_max_index);
381 return;
382 }
383 }
384
385
386 /* Free a sparse array allocated with sarray_new */
387 void
sarray_free(struct sarray * array)388 sarray_free (struct sarray *array) {
389 #ifdef OBJC_SPARSE3
390 size_t old_max_index = (array->capacity - 1)/INDEX_CAPACITY;
391 struct sindex **old_indices;
392 #else
393 size_t old_max_index = (array->capacity - 1)/BUCKET_SIZE;
394 struct sbucket **old_buckets;
395 #endif
396 size_t counter = 0;
397
398 assert (array->ref_count != 0); /* Freed multiple times!!! */
399
400 if (--(array->ref_count) != 0) /* There exists copies of me */
401 return;
402
403 #ifdef OBJC_SPARSE3
404 old_indices = array->indices;
405 #else
406 old_buckets = array->buckets;
407 #endif
408
409 /* Free all entries that do not point to empty_bucket. */
410 for (counter = 0; counter <= old_max_index; counter++ )
411 {
412 #ifdef OBJC_SPARSE3
413 struct sindex *idx = old_indices[counter];
414 if ((idx != array->empty_index)
415 && (idx->version.version == array->version.version))
416 {
417 int c2;
418 for (c2 = 0; c2 < INDEX_SIZE; c2++)
419 {
420 struct sbucket *bkt = idx->buckets[c2];
421 if ((bkt != array->empty_bucket)
422 && (bkt->version.version == array->version.version))
423 {
424 sarray_free_garbage (bkt);
425 nbuckets -= 1;
426 }
427 }
428 sarray_free_garbage (idx);
429 nindices -= 1;
430 }
431 #else /* OBJC_SPARSE2 */
432 struct sbucket *bkt = old_buckets[counter];
433 if ((bkt != array->empty_bucket)
434 && (bkt->version.version == array->version.version))
435 {
436 sarray_free_garbage (bkt);
437 nbuckets -= 1;
438 }
439 #endif
440 }
441
442 #ifdef OBJC_SPARSE3
443 /* Free empty_index. */
444 if (array->empty_index->version.version == array->version.version)
445 {
446 sarray_free_garbage (array->empty_index);
447 nindices -= 1;
448 }
449 #endif
450
451 /* Free empty_bucket. */
452 if (array->empty_bucket->version.version == array->version.version)
453 {
454 sarray_free_garbage (array->empty_bucket);
455 nbuckets -= 1;
456 }
457 idxsize -= (old_max_index + 1);
458 narrays -= 1;
459
460 #ifdef OBJC_SPARSE3
461 /* Free bucket table. */
462 sarray_free_garbage (array->indices);
463 #else
464 /* Free bucket table. */
465 sarray_free_garbage (array->buckets);
466 #endif
467
468 /* If this is a copy of another array, we free it (which might just
469 decrement its reference count so it will be freed when no longer
470 in use). */
471 if (array->is_copy_of)
472 sarray_free (array->is_copy_of);
473
474 /* Free array. */
475 sarray_free_garbage (array);
476 }
477
478 /* This is a lazy copy. Only the core of the structure is actually
479 copied. */
480 struct sarray *
sarray_lazy_copy(struct sarray * oarr)481 sarray_lazy_copy (struct sarray *oarr)
482 {
483 struct sarray *arr;
484
485 #ifdef OBJC_SPARSE3
486 size_t num_indices = ((oarr->capacity - 1)/INDEX_CAPACITY) + 1;
487 struct sindex **new_indices;
488 #else /* OBJC_SPARSE2 */
489 size_t num_indices = ((oarr->capacity - 1)/BUCKET_SIZE) + 1;
490 struct sbucket **new_buckets;
491 #endif
492
493 /* Allocate core array. */
494 arr = (struct sarray *) objc_malloc (sizeof (struct sarray)); /* !!! */
495 arr->version.version = oarr->version.version + 1;
496 #ifdef OBJC_SPARSE3
497 arr->empty_index = oarr->empty_index;
498 #endif
499 arr->empty_bucket = oarr->empty_bucket;
500 arr->ref_count = 1;
501 oarr->ref_count += 1;
502 arr->is_copy_of = oarr;
503 arr->capacity = oarr->capacity;
504
505 #ifdef OBJC_SPARSE3
506 /* Copy bucket table. */
507 new_indices = (struct sindex **)
508 objc_malloc (sizeof (struct sindex *) * num_indices);
509 memcpy (new_indices, oarr->indices, sizeof (struct sindex *) * num_indices);
510 arr->indices = new_indices;
511 #else
512 /* Copy bucket table. */
513 new_buckets = (struct sbucket **)
514 objc_malloc (sizeof (struct sbucket *) * num_indices);
515 memcpy (new_buckets, oarr->buckets, sizeof (struct sbucket *) * num_indices);
516 arr->buckets = new_buckets;
517 #endif
518
519 idxsize += num_indices;
520 narrays += 1;
521
522 return arr;
523 }
524