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 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 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 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 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 * 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 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 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 * 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