libobjc/sarray.c

   1 /* Sparse Arrays for Objective C dispatch tables
   2    Copyright (C) 1993-2014 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 \f
 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 \f
 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 }