mono/metadata/jit-info.c

   1 /*
   2  * jit-info.c: MonoJitInfo functionality
   3  *
   4  * Author:
   5  *      Dietmar Maurer (dietmar@ximian.com)
   6  *      Patrik Torstensson
   7  *
   8  * Copyright 2001-2003 Ximian, Inc (http://www.ximian.com)
   9  * Copyright 2004-2009 Novell, Inc (http://www.novell.com)
  10  * Copyright 2011-2012 Xamarin, Inc (http://www.xamarin.com)
  11  */
  12
  13 #include <config.h>
  14 #include <glib.h>
  15 #include <string.h>
  16 #include <sys/stat.h>
  17
  18 #include <mono/metadata/gc-internals.h>
  19
  20 #include <mono/utils/atomic.h>
  21 #include <mono/utils/mono-compiler.h>
  22 #include <mono/utils/mono-logger-internals.h>
  23 #include <mono/utils/mono-membar.h>
  24 #include <mono/utils/mono-counters.h>
  25 #include <mono/utils/hazard-pointer.h>
  26 #include <mono/utils/mono-tls.h>
  27 #include <mono/utils/mono-mmap.h>
  28 #include <mono/utils/mono-threads.h>
  29 #include <mono/metadata/object.h>
  30 #include <mono/metadata/object-internals.h>
  31 #include <mono/metadata/domain-internals.h>
  32 #include <mono/metadata/class-internals.h>
  33 #include <mono/metadata/assembly.h>
  34 #include <mono/metadata/exception.h>
  35 #include <mono/metadata/metadata-internals.h>
  36 #include <mono/metadata/gc-internals.h>
  37 #include <mono/metadata/appdomain.h>
  38 #include <mono/metadata/mono-debug-debugger.h>
  39 #include <mono/metadata/mono-config.h>
  40 #include <mono/metadata/threads-types.h>
  41 #include <mono/metadata/runtime.h>
  42 #include <metadata/threads.h>
  43 #include <metadata/profiler-private.h>
  44 #include <mono/metadata/coree.h>
  45
  46 static MonoJitInfoFindInAot jit_info_find_in_aot_func = NULL;
  47
  48 #define JIT_INFO_TABLE_FILL_RATIO_NOM           3
  49 #define JIT_INFO_TABLE_FILL_RATIO_DENOM         4
  50 #define JIT_INFO_TABLE_FILLED_NUM_ELEMENTS      (MONO_JIT_INFO_TABLE_CHUNK_SIZE * JIT_INFO_TABLE_FILL_RATIO_NOM / JIT_INFO_TABLE_FILL_RATIO_DENOM)
  51
  52 #define JIT_INFO_TABLE_LOW_WATERMARK(n)         ((n) / 2)
  53 #define JIT_INFO_TABLE_HIGH_WATERMARK(n)        ((n) * 5 / 6)
  54
  55 #define JIT_INFO_TOMBSTONE_MARKER       ((MonoMethod*)NULL)
  56 #define IS_JIT_INFO_TOMBSTONE(ji)       ((ji)->d.method == JIT_INFO_TOMBSTONE_MARKER)
  57
  58 #define JIT_INFO_TABLE_HAZARD_INDEX             0
  59 #define JIT_INFO_HAZARD_INDEX                   1
  60
  61 static int
  62 jit_info_table_num_elements (MonoJitInfoTable *table)
  63 {
  64         int i;
  65         int num_elements = 0;
  66
  67         for (i = 0; i < table->num_chunks; ++i) {
  68                 MonoJitInfoTableChunk *chunk = table->chunks [i];
  69                 int chunk_num_elements = chunk->num_elements;
  70                 int j;
  71
  72                 for (j = 0; j < chunk_num_elements; ++j) {
  73                         if (!IS_JIT_INFO_TOMBSTONE (chunk->data [j]))
  74                                 ++num_elements;
  75                 }
  76         }
  77
  78         return num_elements;
  79 }
  80
  81 static MonoJitInfoTableChunk*
  82 jit_info_table_new_chunk (void)
  83 {
  84         MonoJitInfoTableChunk *chunk = g_new0 (MonoJitInfoTableChunk, 1);
  85         chunk->refcount = 1;
  86
  87         return chunk;
  88 }
  89
  90 MonoJitInfoTable *
  91 mono_jit_info_table_new (MonoDomain *domain)
  92 {
  93         MonoJitInfoTable *table = (MonoJitInfoTable *)g_malloc0 (MONO_SIZEOF_JIT_INFO_TABLE + sizeof (MonoJitInfoTableChunk*));
  94
  95         table->domain = domain;
  96         table->num_chunks = 1;
  97         table->chunks [0] = jit_info_table_new_chunk ();
  98
  99         return table;
 100 }
 101
 102 void
 103 mono_jit_info_table_free (MonoJitInfoTable *table)
 104 {
 105         int i;
 106         int num_chunks = table->num_chunks;
 107         MonoDomain *domain = table->domain;
 108
 109         mono_domain_lock (domain);
 110
 111         table->domain->num_jit_info_tables--;
 112         if (table->domain->num_jit_info_tables <= 1) {
 113                 GSList *list;
 114
 115                 for (list = table->domain->jit_info_free_queue; list; list = list->next)
 116                         g_free (list->data);
 117
 118                 g_slist_free (table->domain->jit_info_free_queue);
 119                 table->domain->jit_info_free_queue = NULL;
 120         }
 121
 122         /* At this point we assume that there are no other threads
 123            still accessing the table, so we don't have to worry about
 124            hazardous pointers. */
 125
 126         for (i = 0; i < num_chunks; ++i) {
 127                 MonoJitInfoTableChunk *chunk = table->chunks [i];
 128                 MonoJitInfo *tombstone;
 129
 130                 if (--chunk->refcount > 0)
 131                         continue;
 132
 133                 for (tombstone = chunk->next_tombstone; tombstone; ) {
 134                         MonoJitInfo *next = tombstone->n.next_tombstone;
 135                         g_free (tombstone);
 136                         tombstone = next;
 137                 }
 138
 139                 g_free (chunk);
 140         }
 141
 142         mono_domain_unlock (domain);
 143
 144         g_free (table);
 145 }
 146
 147 /* The jit_info_table is sorted in ascending order by the end
 148  * addresses of the compiled methods.  The reason why we have to do
 149  * this is that once we introduce tombstones, it becomes possible for
 150  * code ranges to overlap, and if we sort by code start and insert at
 151  * the back of the table, we cannot guarantee that we won't overlook
 152  * an entry.
 153  *
 154  * There are actually two possible ways to do the sorting and
 155  * inserting which work with our lock-free mechanism:
 156  *
 157  * 1. Sort by start address and insert at the front.  When looking for
 158  * an entry, find the last one with a start address lower than the one
 159  * you're looking for, then work your way to the front of the table.
 160  *
 161  * 2. Sort by end address and insert at the back.  When looking for an
 162  * entry, find the first one with an end address higher than the one
 163  * you're looking for, then work your way to the end of the table.
 164  *
 165  * We chose the latter out of convenience.
 166  */
 167 static int
 168 jit_info_table_index (MonoJitInfoTable *table, gint8 *addr)
 169 {
 170         int left = 0, right = table->num_chunks;
 171
 172         g_assert (left < right);
 173
 174         do {
 175                 int pos = (left + right) / 2;
 176                 MonoJitInfoTableChunk *chunk = table->chunks [pos];
 177
 178                 if (addr < chunk->last_code_end)
 179                         right = pos;
 180                 else
 181                         left = pos + 1;
 182         } while (left < right);
 183         g_assert (left == right);
 184
 185         if (left >= table->num_chunks)
 186                 return table->num_chunks - 1;
 187         return left;
 188 }
 189
 190 static int
 191 jit_info_table_chunk_index (MonoJitInfoTableChunk *chunk, MonoThreadHazardPointers *hp, gint8 *addr)
 192 {
 193         int left = 0, right = chunk->num_elements;
 194
 195         while (left < right) {
 196                 int pos = (left + right) / 2;
 197                 MonoJitInfo *ji = (MonoJitInfo *)get_hazardous_pointer((gpointer volatile*)&chunk->data [pos], hp, JIT_INFO_HAZARD_INDEX);
 198                 gint8 *code_end = (gint8*)ji->code_start + ji->code_size;
 199
 200                 if (addr < code_end)
 201                         right = pos;
 202                 else
 203                         left = pos + 1;
 204         }
 205         g_assert (left == right);
 206
 207         return left;
 208 }
 209
 210 static MonoJitInfo*
 211 jit_info_table_find (MonoJitInfoTable *table, MonoThreadHazardPointers *hp, gint8 *addr)
 212 {
 213         MonoJitInfo *ji;
 214         int chunk_pos, pos;
 215
 216         chunk_pos = jit_info_table_index (table, (gint8*)addr);
 217         g_assert (chunk_pos < table->num_chunks);
 218
 219         pos = jit_info_table_chunk_index (table->chunks [chunk_pos], hp, (gint8*)addr);
 220
 221         /* We now have a position that's very close to that of the
 222            first element whose end address is higher than the one
 223            we're looking for.  If we don't have the exact position,
 224            then we have a position below that one, so we'll just
 225            search upward until we find our element. */
 226         do {
 227                 MonoJitInfoTableChunk *chunk = table->chunks [chunk_pos];
 228
 229                 while (pos < chunk->num_elements) {
 230                         ji = (MonoJitInfo *)get_hazardous_pointer ((gpointer volatile*)&chunk->data [pos], hp, JIT_INFO_HAZARD_INDEX);
 231
 232                         ++pos;
 233
 234                         if (IS_JIT_INFO_TOMBSTONE (ji)) {
 235                                 mono_hazard_pointer_clear (hp, JIT_INFO_HAZARD_INDEX);
 236                                 continue;
 237                         }
 238                         if ((gint8*)addr >= (gint8*)ji->code_start
 239                                         && (gint8*)addr < (gint8*)ji->code_start + ji->code_size) {
 240                                 mono_hazard_pointer_clear (hp, JIT_INFO_HAZARD_INDEX);
 241                                 return ji;
 242                         }
 243
 244                         /* If we find a non-tombstone element which is already
 245                            beyond what we're looking for, we have to end the
 246                            search. */
 247                         if ((gint8*)addr < (gint8*)ji->code_start)
 248                                 goto not_found;
 249                 }
 250
 251                 ++chunk_pos;
 252                 pos = 0;
 253         } while (chunk_pos < table->num_chunks);
 254
 255  not_found:
 256         if (hp)
 257                 mono_hazard_pointer_clear (hp, JIT_INFO_HAZARD_INDEX);
 258         return NULL;
 259 }
 260
 261 /*
 262  * mono_jit_info_table_find_internal:
 263  *
 264  * If TRY_AOT is FALSE, avoid loading information for missing methods from AOT images, which is currently not async safe.
 265  * In this case, only those AOT methods will be found whose jit info is already loaded.
 266  * If ALLOW_TRAMPOLINES is TRUE, this can return a MonoJitInfo which represents a trampoline (ji->is_trampoline is true).
 267  * ASYNC SAFETY: When called in an async context (mono_thread_info_is_async_context ()), this is async safe.
 268  * In this case, the returned MonoJitInfo might not have metadata information, in particular,
 269  * mono_jit_info_get_method () could fail.
 270  */
 271 MonoJitInfo*
 272 mono_jit_info_table_find_internal (MonoDomain *domain, char *addr, gboolean try_aot, gboolean allow_trampolines)
 273 {
 274         MonoJitInfoTable *table;
 275         MonoJitInfo *ji, *module_ji;
 276         MonoThreadHazardPointers *hp = mono_hazard_pointer_get ();
 277
 278         ++mono_stats.jit_info_table_lookup_count;
 279
 280         /* First we have to get the domain's jit_info_table.  This is
 281            complicated by the fact that a writer might substitute a
 282            new table and free the old one.  What the writer guarantees
 283            us is that it looks at the hazard pointers after it has
 284            changed the jit_info_table pointer.  So, if we guard the
 285            table by a hazard pointer and make sure that the pointer is
 286            still there after we've made it hazardous, we don't have to
 287            worry about the writer freeing the table. */
 288         table = (MonoJitInfoTable *)get_hazardous_pointer ((gpointer volatile*)&domain->jit_info_table, hp, JIT_INFO_TABLE_HAZARD_INDEX);
 289
 290         ji = jit_info_table_find (table, hp, (gint8*)addr);
 291         if (hp)
 292                 mono_hazard_pointer_clear (hp, JIT_INFO_TABLE_HAZARD_INDEX);
 293         if (ji && ji->is_trampoline && !allow_trampolines)
 294                 return NULL;
 295         if (ji)
 296                 return ji;
 297
 298         /* Maybe its an AOT module */
 299         if (try_aot && mono_get_root_domain () && mono_get_root_domain ()->aot_modules) {
 300                 table = (MonoJitInfoTable *)get_hazardous_pointer ((gpointer volatile*)&mono_get_root_domain ()->aot_modules, hp, JIT_INFO_TABLE_HAZARD_INDEX);
 301                 module_ji = jit_info_table_find (table, hp, (gint8*)addr);
 302                 if (module_ji)
 303                         ji = jit_info_find_in_aot_func (domain, module_ji->d.image, addr);
 304                 if (hp)
 305                         mono_hazard_pointer_clear (hp, JIT_INFO_TABLE_HAZARD_INDEX);
 306         }
 307
 308         if (ji && ji->is_trampoline && !allow_trampolines)
 309                 return NULL;
 310
 311         return ji;
 312 }
 313
 314 MonoJitInfo*
 315 mono_jit_info_table_find (MonoDomain *domain, char *addr)
 316 {
 317         return mono_jit_info_table_find_internal (domain, addr, TRUE, FALSE);
 318 }
 319
 320 static G_GNUC_UNUSED void
 321 jit_info_table_check (MonoJitInfoTable *table)
 322 {
 323         int i;
 324
 325         for (i = 0; i < table->num_chunks; ++i) {
 326                 MonoJitInfoTableChunk *chunk = table->chunks [i];
 327                 int j;
 328
 329                 g_assert (chunk->refcount > 0 /* && chunk->refcount <= 8 */);
 330                 if (chunk->refcount > 10)
 331                         printf("warning: chunk refcount is %d\n", chunk->refcount);
 332                 g_assert (chunk->num_elements <= MONO_JIT_INFO_TABLE_CHUNK_SIZE);
 333
 334                 for (j = 0; j < chunk->num_elements; ++j) {
 335                         MonoJitInfo *this_ji = chunk->data [j];
 336                         MonoJitInfo *next;
 337
 338                         g_assert ((gint8*)this_ji->code_start + this_ji->code_size <= chunk->last_code_end);
 339
 340                         if (j < chunk->num_elements - 1)
 341                                 next = chunk->data [j + 1];
 342                         else if (i < table->num_chunks - 1) {
 343                                 int k;
 344
 345                                 for (k = i + 1; k < table->num_chunks; ++k)
 346                                         if (table->chunks [k]->num_elements > 0)
 347                                                 break;
 348
 349                                 if (k >= table->num_chunks)
 350                                         return;
 351
 352                                 g_assert (table->chunks [k]->num_elements > 0);
 353                                 next = table->chunks [k]->data [0];
 354                         } else
 355                                 return;
 356
 357                         g_assert ((gint8*)this_ji->code_start + this_ji->code_size <= (gint8*)next->code_start + next->code_size);
 358                 }
 359         }
 360 }
 361
 362 static MonoJitInfoTable*
 363 jit_info_table_realloc (MonoJitInfoTable *old)
 364 {
 365         int i;
 366         int num_elements = jit_info_table_num_elements (old);
 367         int required_size;
 368         int num_chunks;
 369         int new_chunk, new_element;
 370         MonoJitInfoTable *result;
 371
 372         /* number of needed places for elements needed */
 373         required_size = (int)((long)num_elements * JIT_INFO_TABLE_FILL_RATIO_DENOM / JIT_INFO_TABLE_FILL_RATIO_NOM);
 374         num_chunks = (required_size + MONO_JIT_INFO_TABLE_CHUNK_SIZE - 1) / MONO_JIT_INFO_TABLE_CHUNK_SIZE;
 375         if (num_chunks == 0) {
 376                 g_assert (num_elements == 0);
 377                 return mono_jit_info_table_new (old->domain);
 378         }
 379         g_assert (num_chunks > 0);
 380
 381         result = (MonoJitInfoTable *)g_malloc (MONO_SIZEOF_JIT_INFO_TABLE + sizeof (MonoJitInfoTableChunk*) * num_chunks);
 382         result->domain = old->domain;
 383         result->num_chunks = num_chunks;
 384
 385         for (i = 0; i < num_chunks; ++i)
 386                 result->chunks [i] = jit_info_table_new_chunk ();
 387
 388         new_chunk = 0;
 389         new_element = 0;
 390         for (i = 0; i < old->num_chunks; ++i) {
 391                 MonoJitInfoTableChunk *chunk = old->chunks [i];
 392                 int chunk_num_elements = chunk->num_elements;
 393                 int j;
 394
 395                 for (j = 0; j < chunk_num_elements; ++j) {
 396                         if (!IS_JIT_INFO_TOMBSTONE (chunk->data [j])) {
 397                                 g_assert (new_chunk < num_chunks);
 398                                 result->chunks [new_chunk]->data [new_element] = chunk->data [j];
 399                                 if (++new_element >= JIT_INFO_TABLE_FILLED_NUM_ELEMENTS) {
 400                                         result->chunks [new_chunk]->num_elements = new_element;
 401                                         ++new_chunk;
 402                                         new_element = 0;
 403                                 }
 404                         }
 405                 }
 406         }
 407
 408         if (new_chunk < num_chunks) {
 409                 g_assert (new_chunk == num_chunks - 1);
 410                 result->chunks [new_chunk]->num_elements = new_element;
 411                 g_assert (result->chunks [new_chunk]->num_elements > 0);
 412         }
 413
 414         for (i = 0; i < num_chunks; ++i) {
 415                 MonoJitInfoTableChunk *chunk = result->chunks [i];
 416                 MonoJitInfo *ji = chunk->data [chunk->num_elements - 1];
 417
 418                 result->chunks [i]->last_code_end = (gint8*)ji->code_start + ji->code_size;
 419         }
 420
 421         return result;
 422 }
 423
 424 static void
 425 jit_info_table_split_chunk (MonoJitInfoTableChunk *chunk, MonoJitInfoTableChunk **new1p, MonoJitInfoTableChunk **new2p)
 426 {
 427         MonoJitInfoTableChunk *new1 = jit_info_table_new_chunk ();
 428         MonoJitInfoTableChunk *new2 = jit_info_table_new_chunk ();
 429
 430         g_assert (chunk->num_elements == MONO_JIT_INFO_TABLE_CHUNK_SIZE);
 431
 432         new1->num_elements = MONO_JIT_INFO_TABLE_CHUNK_SIZE / 2;
 433         new2->num_elements = MONO_JIT_INFO_TABLE_CHUNK_SIZE - new1->num_elements;
 434
 435         memcpy ((void*)new1->data, (void*)chunk->data, sizeof (MonoJitInfo*) * new1->num_elements);
 436         memcpy ((void*)new2->data, (void*)(chunk->data + new1->num_elements), sizeof (MonoJitInfo*) * new2->num_elements);
 437
 438         new1->last_code_end = (gint8*)new1->data [new1->num_elements - 1]->code_start
 439                 + new1->data [new1->num_elements - 1]->code_size;
 440         new2->last_code_end = (gint8*)new2->data [new2->num_elements - 1]->code_start
 441                 + new2->data [new2->num_elements - 1]->code_size;
 442
 443         *new1p = new1;
 444         *new2p = new2;
 445 }
 446
 447 static MonoJitInfoTable*
 448 jit_info_table_copy_and_split_chunk (MonoJitInfoTable *table, MonoJitInfoTableChunk *chunk)
 449 {
 450         MonoJitInfoTable *new_table = (MonoJitInfoTable *)g_malloc (MONO_SIZEOF_JIT_INFO_TABLE
 451                 + sizeof (MonoJitInfoTableChunk*) * (table->num_chunks + 1));
 452         int i, j;
 453
 454         new_table->domain = table->domain;
 455         new_table->num_chunks = table->num_chunks + 1;
 456
 457         j = 0;
 458         for (i = 0; i < table->num_chunks; ++i) {
 459                 if (table->chunks [i] == chunk) {
 460                         jit_info_table_split_chunk (chunk, &new_table->chunks [j], &new_table->chunks [j + 1]);
 461                         j += 2;
 462                 } else {
 463                         new_table->chunks [j] = table->chunks [i];
 464                         ++new_table->chunks [j]->refcount;
 465                         ++j;
 466                 }
 467         }
 468
 469         g_assert (j == new_table->num_chunks);
 470
 471         return new_table;
 472 }
 473
 474 static MonoJitInfoTableChunk*
 475 jit_info_table_purify_chunk (MonoJitInfoTableChunk *old)
 476 {
 477         MonoJitInfoTableChunk *result = jit_info_table_new_chunk ();
 478         int i, j;
 479
 480         j = 0;
 481         for (i = 0; i < old->num_elements; ++i) {
 482                 if (!IS_JIT_INFO_TOMBSTONE (old->data [i]))
 483                         result->data [j++] = old->data [i];
 484         }
 485
 486         result->num_elements = j;
 487         if (result->num_elements > 0)
 488                 result->last_code_end = (gint8*)result->data [j - 1]->code_start + result->data [j - 1]->code_size;
 489         else
 490                 result->last_code_end = old->last_code_end;
 491
 492         return result;
 493 }
 494
 495 static MonoJitInfoTable*
 496 jit_info_table_copy_and_purify_chunk (MonoJitInfoTable *table, MonoJitInfoTableChunk *chunk)
 497 {
 498         MonoJitInfoTable *new_table = (MonoJitInfoTable *)g_malloc (MONO_SIZEOF_JIT_INFO_TABLE
 499                 + sizeof (MonoJitInfoTableChunk*) * table->num_chunks);
 500         int i, j;
 501
 502         new_table->domain = table->domain;
 503         new_table->num_chunks = table->num_chunks;
 504
 505         j = 0;
 506         for (i = 0; i < table->num_chunks; ++i) {
 507                 if (table->chunks [i] == chunk)
 508                         new_table->chunks [j++] = jit_info_table_purify_chunk (table->chunks [i]);
 509                 else {
 510                         new_table->chunks [j] = table->chunks [i];
 511                         ++new_table->chunks [j]->refcount;
 512                         ++j;
 513                 }
 514         }
 515
 516         g_assert (j == new_table->num_chunks);
 517
 518         return new_table;
 519 }
 520
 521 /* As we add an element to the table the case can arise that the chunk
 522  * to which we need to add is already full.  In that case we have to
 523  * allocate a new table and do something about that chunk.  We have
 524  * several strategies:
 525  *
 526  * If the number of elements in the table is below the low watermark
 527  * or above the high watermark, we reallocate the whole table.
 528  * Otherwise we only concern ourselves with the overflowing chunk:
 529  *
 530  * If there are no tombstones in the chunk then we split the chunk in
 531  * two, each half full.
 532  *
 533  * If the chunk does contain tombstones, we just make a new copy of
 534  * the chunk without the tombstones, which will have room for at least
 535  * the one element we have to add.
 536  */
 537 static MonoJitInfoTable*
 538 jit_info_table_chunk_overflow (MonoJitInfoTable *table, MonoJitInfoTableChunk *chunk)
 539 {
 540         int num_elements = jit_info_table_num_elements (table);
 541         int i;
 542
 543         if (num_elements < JIT_INFO_TABLE_LOW_WATERMARK (table->num_chunks * MONO_JIT_INFO_TABLE_CHUNK_SIZE)
 544                         || num_elements > JIT_INFO_TABLE_HIGH_WATERMARK (table->num_chunks * MONO_JIT_INFO_TABLE_CHUNK_SIZE)) {
 545                 //printf ("reallocing table\n");
 546                 return jit_info_table_realloc (table);
 547         }
 548
 549         /* count the number of non-tombstone elements in the chunk */
 550         num_elements = 0;
 551         for (i = 0; i < chunk->num_elements; ++i) {
 552                 if (!IS_JIT_INFO_TOMBSTONE (chunk->data [i]))
 553                         ++num_elements;
 554         }
 555
 556         if (num_elements == MONO_JIT_INFO_TABLE_CHUNK_SIZE) {
 557                 //printf ("splitting chunk\n");
 558                 return jit_info_table_copy_and_split_chunk (table, chunk);
 559         }
 560
 561         //printf ("purifying chunk\n");
 562         return jit_info_table_copy_and_purify_chunk (table, chunk);
 563 }
 564
 565 /* We add elements to the table by first making space for them by
 566  * shifting the elements at the back to the right, one at a time.
 567  * This results in duplicate entries during the process, but during
 568  * all the time the table is in a sorted state.  Also, when an element
 569  * is replaced by another one, the element that replaces it has an end
 570  * address that is equal to or lower than that of the replaced
 571  * element.  That property is necessary to guarantee that when
 572  * searching for an element we end up at a position not higher than
 573  * the one we're looking for (i.e. we either find the element directly
 574  * or we end up to the left of it).
 575  */
 576 static void
 577 jit_info_table_add (MonoDomain *domain, MonoJitInfoTable *volatile *table_ptr, MonoJitInfo *ji)
 578 {
 579         MonoJitInfoTable *table;
 580         MonoJitInfoTableChunk *chunk;
 581         int chunk_pos, pos;
 582         int num_elements;
 583         int i;
 584
 585         table = *table_ptr;
 586
 587  restart:
 588         chunk_pos = jit_info_table_index (table, (gint8*)ji->code_start + ji->code_size);
 589         g_assert (chunk_pos < table->num_chunks);
 590         chunk = table->chunks [chunk_pos];
 591
 592         if (chunk->num_elements >= MONO_JIT_INFO_TABLE_CHUNK_SIZE) {
 593                 MonoJitInfoTable *new_table = jit_info_table_chunk_overflow (table, chunk);
 594
 595                 /* Debugging code, should be removed. */
 596                 //jit_info_table_check (new_table);
 597
 598                 *table_ptr = new_table;
 599                 mono_memory_barrier ();
 600                 domain->num_jit_info_tables++;
 601                 mono_thread_hazardous_free_or_queue (table, (MonoHazardousFreeFunc)mono_jit_info_table_free, TRUE, FALSE);
 602                 table = new_table;
 603
 604                 goto restart;
 605         }
 606
 607         /* Debugging code, should be removed. */
 608         //jit_info_table_check (table);
 609
 610         num_elements = chunk->num_elements;
 611
 612         pos = jit_info_table_chunk_index (chunk, NULL, (gint8*)ji->code_start + ji->code_size);
 613
 614         /* First we need to size up the chunk by one, by copying the
 615            last item, or inserting the first one, if the table is
 616            empty. */
 617         if (num_elements > 0)
 618                 chunk->data [num_elements] = chunk->data [num_elements - 1];
 619         else
 620                 chunk->data [0] = ji;
 621         mono_memory_write_barrier ();
 622         chunk->num_elements = ++num_elements;
 623
 624         /* Shift the elements up one by one. */
 625         for (i = num_elements - 2; i >= pos; --i) {
 626                 mono_memory_write_barrier ();
 627                 chunk->data [i + 1] = chunk->data [i];
 628         }
 629
 630         /* Now we have room and can insert the new item. */
 631         mono_memory_write_barrier ();
 632         chunk->data [pos] = ji;
 633
 634         /* Set the high code end address chunk entry. */
 635         chunk->last_code_end = (gint8*)chunk->data [chunk->num_elements - 1]->code_start
 636                 + chunk->data [chunk->num_elements - 1]->code_size;
 637
 638         /* Debugging code, should be removed. */
 639         //jit_info_table_check (table);
 640 }
 641
 642 void
 643 mono_jit_info_table_add (MonoDomain *domain, MonoJitInfo *ji)
 644 {
 645         g_assert (ji->d.method != NULL);
 646
 647         mono_domain_lock (domain);
 648
 649         ++mono_stats.jit_info_table_insert_count;
 650
 651         jit_info_table_add (domain, &domain->jit_info_table, ji);
 652
 653         mono_domain_unlock (domain);
 654 }
 655
 656 static MonoJitInfo*
 657 mono_jit_info_make_tombstone (MonoJitInfoTableChunk *chunk, MonoJitInfo *ji)
 658 {
 659         MonoJitInfo *tombstone = g_new0 (MonoJitInfo, 1);
 660
 661         tombstone->code_start = ji->code_start;
 662         tombstone->code_size = ji->code_size;
 663         tombstone->d.method = JIT_INFO_TOMBSTONE_MARKER;
 664         tombstone->n.next_tombstone = chunk->next_tombstone;
 665         chunk->next_tombstone = tombstone;
 666
 667         return tombstone;
 668 }
 669
 670 /*
 671  * LOCKING: domain lock
 672  */
 673 static void
 674 mono_jit_info_free_or_queue (MonoDomain *domain, MonoJitInfo *ji)
 675 {
 676         if (domain->num_jit_info_tables <= 1) {
 677                 /* Can it actually happen that we only have one table
 678                    but ji is still hazardous? */
 679                 mono_thread_hazardous_free_or_queue (ji, g_free, TRUE, FALSE);
 680         } else {
 681                 domain->jit_info_free_queue = g_slist_prepend (domain->jit_info_free_queue, ji);
 682         }
 683 }
 684
 685 static void
 686 jit_info_table_remove (MonoJitInfoTable *table, MonoJitInfo *ji)
 687 {
 688         MonoJitInfoTableChunk *chunk;
 689         gpointer start = ji->code_start;
 690         int chunk_pos, pos;
 691
 692         chunk_pos = jit_info_table_index (table, (gint8 *)start);
 693         g_assert (chunk_pos < table->num_chunks);
 694
 695         pos = jit_info_table_chunk_index (table->chunks [chunk_pos], NULL, (gint8 *)start);
 696
 697         do {
 698                 chunk = table->chunks [chunk_pos];
 699
 700                 while (pos < chunk->num_elements) {
 701                         if (chunk->data [pos] == ji)
 702                                 goto found;
 703
 704                         g_assert (IS_JIT_INFO_TOMBSTONE (chunk->data [pos]));
 705                         g_assert ((guint8*)chunk->data [pos]->code_start + chunk->data [pos]->code_size
 706                                 <= (guint8*)ji->code_start + ji->code_size);
 707
 708                         ++pos;
 709                 }
 710
 711                 ++chunk_pos;
 712                 pos = 0;
 713         } while (chunk_pos < table->num_chunks);
 714
 715  found:
 716         g_assert (chunk->data [pos] == ji);
 717
 718         chunk->data [pos] = mono_jit_info_make_tombstone (chunk, ji);
 719
 720         /* Debugging code, should be removed. */
 721         //jit_info_table_check (table);
 722 }
 723
 724 void
 725 mono_jit_info_table_remove (MonoDomain *domain, MonoJitInfo *ji)
 726 {
 727         MonoJitInfoTable *table;
 728
 729         mono_domain_lock (domain);
 730         table = domain->jit_info_table;
 731
 732         ++mono_stats.jit_info_table_remove_count;
 733
 734         jit_info_table_remove (table, ji);
 735
 736         mono_jit_info_free_or_queue (domain, ji);
 737
 738         mono_domain_unlock (domain);
 739 }
 740
 741 void
 742 mono_jit_info_add_aot_module (MonoImage *image, gpointer start, gpointer end)
 743 {
 744         MonoJitInfo *ji;
 745         MonoDomain *domain = mono_get_root_domain ();
 746
 747         g_assert (domain);
 748         mono_domain_lock (domain);
 749
 750         /*
 751          * We reuse MonoJitInfoTable to store AOT module info,
 752          * this gives us async-safe lookup.
 753          */
 754         if (!domain->aot_modules) {
 755                 domain->num_jit_info_tables ++;
 756                 domain->aot_modules = mono_jit_info_table_new (domain);
 757         }
 758
 759         ji = g_new0 (MonoJitInfo, 1);
 760         ji->d.image = image;
 761         ji->code_start = start;
 762         ji->code_size = (guint8*)end - (guint8*)start;
 763         jit_info_table_add (domain, &domain->aot_modules, ji);
 764
 765         mono_domain_unlock (domain);
 766 }
 767
 768 void
 769 mono_install_jit_info_find_in_aot (MonoJitInfoFindInAot func)
 770 {
 771         jit_info_find_in_aot_func = func;
 772 }
 773
 774 int
 775 mono_jit_info_size (MonoJitInfoFlags flags, int num_clauses, int num_holes)
 776 {
 777         int size = MONO_SIZEOF_JIT_INFO;
 778
 779         size += num_clauses * sizeof (MonoJitExceptionInfo);
 780         if (flags & JIT_INFO_HAS_GENERIC_JIT_INFO)
 781                 size += sizeof (MonoGenericJitInfo);
 782         if (flags & JIT_INFO_HAS_TRY_BLOCK_HOLES)
 783                 size += sizeof (MonoTryBlockHoleTableJitInfo) + num_holes * sizeof (MonoTryBlockHoleJitInfo);
 784         if (flags & JIT_INFO_HAS_ARCH_EH_INFO)
 785                 size += sizeof (MonoArchEHJitInfo);
 786         if (flags & JIT_INFO_HAS_THUNK_INFO)
 787                 size += sizeof (MonoThunkJitInfo);
 788         return size;
 789 }
 790
 791 void
 792 mono_jit_info_init (MonoJitInfo *ji, MonoMethod *method, guint8 *code, int code_size,
 793                                         MonoJitInfoFlags flags, int num_clauses, int num_holes)
 794 {
 795         ji->d.method = method;
 796         ji->code_start = code;
 797         ji->code_size = code_size;
 798         ji->num_clauses = num_clauses;
 799         if (flags & JIT_INFO_HAS_GENERIC_JIT_INFO)
 800                 ji->has_generic_jit_info = 1;
 801         if (flags & JIT_INFO_HAS_TRY_BLOCK_HOLES)
 802                 ji->has_try_block_holes = 1;
 803         if (flags & JIT_INFO_HAS_ARCH_EH_INFO)
 804                 ji->has_arch_eh_info = 1;
 805         if (flags & JIT_INFO_HAS_THUNK_INFO)
 806                 ji->has_thunk_info = 1;
 807 }
 808
 809 gpointer
 810 mono_jit_info_get_code_start (MonoJitInfo* ji)
 811 {
 812         return ji->code_start;
 813 }
 814
 815 int
 816 mono_jit_info_get_code_size (MonoJitInfo* ji)
 817 {
 818         return ji->code_size;
 819 }
 820
 821 MonoMethod*
 822 mono_jit_info_get_method (MonoJitInfo* ji)
 823 {
 824         g_assert (!ji->async);
 825         g_assert (!ji->is_trampoline);
 826         return ji->d.method;
 827 }
 828
 829 static gpointer
 830 jit_info_key_extract (gpointer value)
 831 {
 832         MonoJitInfo *info = (MonoJitInfo*)value;
 833
 834         return info->d.method;
 835 }
 836
 837 static gpointer*
 838 jit_info_next_value (gpointer value)
 839 {
 840         MonoJitInfo *info = (MonoJitInfo*)value;
 841
 842         return (gpointer*)&info->n.next_jit_code_hash;
 843 }
 844
 845 void
 846 mono_jit_code_hash_init (MonoInternalHashTable *jit_code_hash)
 847 {
 848         mono_internal_hash_table_init (jit_code_hash,
 849                                        mono_aligned_addr_hash,
 850                                        jit_info_key_extract,
 851                                        jit_info_next_value);
 852 }
 853
 854 MonoGenericJitInfo*
 855 mono_jit_info_get_generic_jit_info (MonoJitInfo *ji)
 856 {
 857         if (ji->has_generic_jit_info)
 858                 return (MonoGenericJitInfo*)&ji->clauses [ji->num_clauses];
 859         else
 860                 return NULL;
 861 }
 862
 863 /*
 864  * mono_jit_info_get_generic_sharing_context:
 865  * @ji: a jit info
 866  *
 867  * Returns the jit info's generic sharing context, or NULL if it
 868  * doesn't have one.
 869  */
 870 MonoGenericSharingContext*
 871 mono_jit_info_get_generic_sharing_context (MonoJitInfo *ji)
 872 {
 873         MonoGenericJitInfo *gi = mono_jit_info_get_generic_jit_info (ji);
 874
 875         if (gi)
 876                 return gi->generic_sharing_context;
 877         else
 878                 return NULL;
 879 }
 880
 881 /*
 882  * mono_jit_info_set_generic_sharing_context:
 883  * @ji: a jit info
 884  * @gsctx: a generic sharing context
 885  *
 886  * Sets the jit info's generic sharing context.  The jit info must
 887  * have memory allocated for the context.
 888  */
 889 void
 890 mono_jit_info_set_generic_sharing_context (MonoJitInfo *ji, MonoGenericSharingContext *gsctx)
 891 {
 892         MonoGenericJitInfo *gi = mono_jit_info_get_generic_jit_info (ji);
 893
 894         g_assert (gi);
 895
 896         gi->generic_sharing_context = gsctx;
 897 }
 898
 899 MonoTryBlockHoleTableJitInfo*
 900 mono_jit_info_get_try_block_hole_table_info (MonoJitInfo *ji)
 901 {
 902         if (ji->has_try_block_holes) {
 903                 char *ptr = (char*)&ji->clauses [ji->num_clauses];
 904                 if (ji->has_generic_jit_info)
 905                         ptr += sizeof (MonoGenericJitInfo);
 906                 return (MonoTryBlockHoleTableJitInfo*)ptr;
 907         } else {
 908                 return NULL;
 909         }
 910 }
 911
 912 static int
 913 try_block_hole_table_size (MonoJitInfo *ji)
 914 {
 915         MonoTryBlockHoleTableJitInfo *table;
 916
 917         table = mono_jit_info_get_try_block_hole_table_info (ji);
 918         g_assert (table);
 919         return sizeof (MonoTryBlockHoleTableJitInfo) + table->num_holes * sizeof (MonoTryBlockHoleJitInfo);
 920 }
 921
 922 MonoArchEHJitInfo*
 923 mono_jit_info_get_arch_eh_info (MonoJitInfo *ji)
 924 {
 925         if (ji->has_arch_eh_info) {
 926                 char *ptr = (char*)&ji->clauses [ji->num_clauses];
 927                 if (ji->has_generic_jit_info)
 928                         ptr += sizeof (MonoGenericJitInfo);
 929                 if (ji->has_try_block_holes)
 930                         ptr += try_block_hole_table_size (ji);
 931                 return (MonoArchEHJitInfo*)ptr;
 932         } else {
 933                 return NULL;
 934         }
 935 }
 936
 937 MonoThunkJitInfo*
 938 mono_jit_info_get_thunk_info (MonoJitInfo *ji)
 939 {
 940         if (ji->has_thunk_info) {
 941                 char *ptr = (char*)&ji->clauses [ji->num_clauses];
 942                 if (ji->has_generic_jit_info)
 943                         ptr += sizeof (MonoGenericJitInfo);
 944                 if (ji->has_try_block_holes)
 945                         ptr += try_block_hole_table_size (ji);
 946                 if (ji->has_arch_eh_info)
 947                         ptr += sizeof (MonoArchEHJitInfo);
 948                 return (MonoThunkJitInfo*)ptr;
 949         } else {
 950                 return NULL;
 951         }
 952 }