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