1/* GNU Objective C Runtime message lookup 2 Copyright (C) 1993, 1995, 1996, 1997, 1998, 3 2001, 2002, 2004, 2009 Free Software Foundation, Inc. 4 Contributed by Kresten Krab Thorup 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under the 9terms of the GNU General Public License as published by the Free Software 10Foundation; either version 3, or (at your option) any later version. 11 12GCC is distributed in the hope that it will be useful, but WITHOUT ANY 13WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 14FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 15details. 16 17Under Section 7 of GPL version 3, you are granted additional 18permissions described in the GCC Runtime Library Exception, version 193.1, as published by the Free Software Foundation. 20 21You should have received a copy of the GNU General Public License and 22a copy of the GCC Runtime Library Exception along with this program; 23see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 24<http://www.gnu.org/licenses/>. */ 25 26 27/* FIXME: This file has no business including tm.h. */ 28/* FIXME: This should be using libffi instead of __builtin_apply 29 and friends. */ 30 31#include "tconfig.h" 32#include "coretypes.h" 33#include "tm.h" 34#include "objc/runtime.h" 35#include "objc/sarray.h" 36#include "objc/encoding.h" 37#include "runtime-info.h" 38 39/* This is how we hack STRUCT_VALUE to be 1 or 0. */ 40#define gen_rtx(args...) 1 41#define gen_rtx_MEM(args...) 1 42#define gen_rtx_REG(args...) 1 43/* Alread defined in gcc/coretypes.h. So prevent double definition warning. */ 44#undef rtx 45#define rtx int 46 47#if ! defined (STRUCT_VALUE) || STRUCT_VALUE == 0 48#define INVISIBLE_STRUCT_RETURN 1 49#else 50#define INVISIBLE_STRUCT_RETURN 0 51#endif 52 53/* The uninstalled dispatch table */ 54struct sarray *__objc_uninstalled_dtable = 0; /* !T:MUTEX */ 55 56/* Two hooks for method forwarding. If either is set, it is invoked 57 * to return a function that performs the real forwarding. If both 58 * are set, the result of __objc_msg_forward2 will be preferred over 59 * that of __objc_msg_forward. If both return NULL or are unset, 60 * the libgcc based functions (__builtin_apply and friends) are 61 * used. 62 */ 63IMP (*__objc_msg_forward) (SEL) = NULL; 64IMP (*__objc_msg_forward2) (id, SEL) = NULL; 65 66/* Send +initialize to class */ 67static void __objc_send_initialize (Class); 68 69static void __objc_install_dispatch_table_for_class (Class); 70 71/* Forward declare some functions */ 72static void __objc_init_install_dtable (id, SEL); 73 74/* Various forwarding functions that are used based upon the 75 return type for the selector. 76 __objc_block_forward for structures. 77 __objc_double_forward for floats/doubles. 78 __objc_word_forward for pointers or types that fit in registers. */ 79static double __objc_double_forward (id, SEL, ...); 80static id __objc_word_forward (id, SEL, ...); 81typedef struct { id many[8]; } __big; 82#if INVISIBLE_STRUCT_RETURN 83static __big 84#else 85static id 86#endif 87__objc_block_forward (id, SEL, ...); 88static Method_t search_for_method_in_hierarchy (Class class, SEL sel); 89Method_t search_for_method_in_list (MethodList_t list, SEL op); 90id nil_method (id, SEL); 91 92/* Given a selector, return the proper forwarding implementation. */ 93inline 94IMP 95__objc_get_forward_imp (id rcv, SEL sel) 96{ 97 /* If a custom forwarding hook was registered, try getting a forwarding 98 function from it. There are two forward routine hooks, one that 99 takes the receiver as an argument and one that does not. */ 100 if (__objc_msg_forward2) 101 { 102 IMP result; 103 if ((result = __objc_msg_forward2 (rcv, sel)) != NULL) 104 return result; 105 } 106 if (__objc_msg_forward) 107 { 108 IMP result; 109 if ((result = __objc_msg_forward (sel)) != NULL) 110 return result; 111 } 112 113 /* In all other cases, use the default forwarding functions built using 114 __builtin_apply and friends. */ 115 { 116 const char *t = sel->sel_types; 117 118 if (t && (*t == '[' || *t == '(' || *t == '{') 119#ifdef OBJC_MAX_STRUCT_BY_VALUE 120 && objc_sizeof_type (t) > OBJC_MAX_STRUCT_BY_VALUE 121#endif 122 ) 123 return (IMP)__objc_block_forward; 124 else if (t && (*t == 'f' || *t == 'd')) 125 return (IMP)__objc_double_forward; 126 else 127 return (IMP)__objc_word_forward; 128 } 129} 130 131/* Given a class and selector, return the selector's implementation. */ 132inline 133IMP 134get_imp (Class class, SEL sel) 135{ 136 /* In a vanilla implementation we would first check if the dispatch 137 table is installed. Here instead, to get more speed in the 138 standard case (that the dispatch table is installed) we first try 139 to get the imp using brute force. Only if that fails, we do what 140 we should have been doing from the very beginning, that is, check 141 if the dispatch table needs to be installed, install it if it's 142 not installed, and retrieve the imp from the table if it's 143 installed. */ 144 void *res = sarray_get_safe (class->dtable, (size_t) sel->sel_id); 145 if (res == 0) 146 { 147 /* Not a valid method */ 148 if (class->dtable == __objc_uninstalled_dtable) 149 { 150 /* The dispatch table needs to be installed. */ 151 objc_mutex_lock (__objc_runtime_mutex); 152 153 /* Double-checked locking pattern: Check 154 __objc_uninstalled_dtable again in case another thread 155 installed the dtable while we were waiting for the lock 156 to be released. */ 157 if (class->dtable == __objc_uninstalled_dtable) 158 { 159 __objc_install_dispatch_table_for_class (class); 160 } 161 162 objc_mutex_unlock (__objc_runtime_mutex); 163 /* Call ourselves with the installed dispatch table 164 and get the real method */ 165 res = get_imp (class, sel); 166 } 167 else 168 { 169 /* The dispatch table has been installed. */ 170 171 /* Get the method from the dispatch table (we try to get it 172 again in case another thread has installed the dtable just 173 after we invoked sarray_get_safe, but before we checked 174 class->dtable == __objc_uninstalled_dtable). 175 */ 176 res = sarray_get_safe (class->dtable, (size_t) sel->sel_id); 177 if (res == 0) 178 { 179 /* The dispatch table has been installed, and the method 180 is not in the dispatch table. So the method just 181 doesn't exist for the class. Return the forwarding 182 implementation. */ 183 res = __objc_get_forward_imp ((id)class, sel); 184 } 185 } 186 } 187 return res; 188} 189 190/* Query if an object can respond to a selector, returns YES if the 191object implements the selector otherwise NO. Does not check if the 192method can be forwarded. */ 193inline 194BOOL 195__objc_responds_to (id object, SEL sel) 196{ 197 void *res; 198 199 /* Install dispatch table if need be */ 200 if (object->class_pointer->dtable == __objc_uninstalled_dtable) 201 { 202 objc_mutex_lock (__objc_runtime_mutex); 203 if (object->class_pointer->dtable == __objc_uninstalled_dtable) 204 { 205 __objc_install_dispatch_table_for_class (object->class_pointer); 206 } 207 objc_mutex_unlock (__objc_runtime_mutex); 208 } 209 210 /* Get the method from the dispatch table */ 211 res = sarray_get_safe (object->class_pointer->dtable, (size_t) sel->sel_id); 212 return (res != 0); 213} 214 215/* This is the lookup function. All entries in the table are either a 216 valid method *or* zero. If zero then either the dispatch table 217 needs to be installed or it doesn't exist and forwarding is attempted. */ 218inline 219IMP 220objc_msg_lookup (id receiver, SEL op) 221{ 222 IMP result; 223 if (receiver) 224 { 225 result = sarray_get_safe (receiver->class_pointer->dtable, 226 (sidx)op->sel_id); 227 if (result == 0) 228 { 229 /* Not a valid method */ 230 if (receiver->class_pointer->dtable == __objc_uninstalled_dtable) 231 { 232 /* The dispatch table needs to be installed. 233 This happens on the very first method call to the class. */ 234 __objc_init_install_dtable (receiver, op); 235 236 /* Get real method for this in newly installed dtable */ 237 result = get_imp (receiver->class_pointer, op); 238 } 239 else 240 { 241 /* The dispatch table has been installed. Check again 242 if the method exists (just in case the dispatch table 243 has been installed by another thread after we did the 244 previous check that the method exists). 245 */ 246 result = sarray_get_safe (receiver->class_pointer->dtable, 247 (sidx)op->sel_id); 248 if (result == 0) 249 { 250 /* If the method still just doesn't exist for the 251 class, attempt to forward the method. */ 252 result = __objc_get_forward_imp (receiver, op); 253 } 254 } 255 } 256 return result; 257 } 258 else 259 return (IMP)nil_method; 260} 261 262IMP 263objc_msg_lookup_super (Super_t super, SEL sel) 264{ 265 if (super->self) 266 return get_imp (super->class, sel); 267 else 268 return (IMP)nil_method; 269} 270 271int method_get_sizeof_arguments (Method *); 272 273retval_t 274objc_msg_sendv (id object, SEL op, arglist_t arg_frame) 275{ 276 Method *m = class_get_instance_method (object->class_pointer, op); 277 const char *type; 278 *((id *) method_get_first_argument (m, arg_frame, &type)) = object; 279 *((SEL *) method_get_next_argument (arg_frame, &type)) = op; 280 return __builtin_apply ((apply_t) m->method_imp, 281 arg_frame, 282 method_get_sizeof_arguments (m)); 283} 284 285void 286__objc_init_dispatch_tables () 287{ 288 __objc_uninstalled_dtable = sarray_new (200, 0); 289} 290 291/* This function is called by objc_msg_lookup when the 292 dispatch table needs to be installed; thus it is called once 293 for each class, namely when the very first message is sent to it. */ 294static void 295__objc_init_install_dtable (id receiver, SEL op __attribute__ ((__unused__))) 296{ 297 objc_mutex_lock (__objc_runtime_mutex); 298 299 /* This may happen, if the programmer has taken the address of a 300 method before the dtable was initialized... too bad for him! */ 301 if (receiver->class_pointer->dtable != __objc_uninstalled_dtable) 302 { 303 objc_mutex_unlock (__objc_runtime_mutex); 304 return; 305 } 306 307 if (CLS_ISCLASS (receiver->class_pointer)) 308 { 309 /* receiver is an ordinary object */ 310 assert (CLS_ISCLASS (receiver->class_pointer)); 311 312 /* install instance methods table */ 313 __objc_install_dispatch_table_for_class (receiver->class_pointer); 314 315 /* call +initialize -- this will in turn install the factory 316 dispatch table if not already done :-) */ 317 __objc_send_initialize (receiver->class_pointer); 318 } 319 else 320 { 321 /* receiver is a class object */ 322 assert (CLS_ISCLASS ((Class)receiver)); 323 assert (CLS_ISMETA (receiver->class_pointer)); 324 325 /* Install real dtable for factory methods */ 326 __objc_install_dispatch_table_for_class (receiver->class_pointer); 327 328 __objc_send_initialize ((Class)receiver); 329 } 330 objc_mutex_unlock (__objc_runtime_mutex); 331} 332 333/* Install dummy table for class which causes the first message to 334 that class (or instances hereof) to be initialized properly */ 335void 336__objc_install_premature_dtable (Class class) 337{ 338 assert (__objc_uninstalled_dtable); 339 class->dtable = __objc_uninstalled_dtable; 340} 341 342/* Send +initialize to class if not already done */ 343static void 344__objc_send_initialize (Class class) 345{ 346 /* This *must* be a class object */ 347 assert (CLS_ISCLASS (class)); 348 assert (! CLS_ISMETA (class)); 349 350 if (! CLS_ISINITIALIZED (class)) 351 { 352 CLS_SETINITIALIZED (class); 353 CLS_SETINITIALIZED (class->class_pointer); 354 355 /* Create the garbage collector type memory description */ 356 __objc_generate_gc_type_description (class); 357 358 if (class->super_class) 359 __objc_send_initialize (class->super_class); 360 361 { 362 SEL op = sel_register_name ("initialize"); 363 IMP imp = 0; 364 MethodList_t method_list = class->class_pointer->methods; 365 366 while (method_list) { 367 int i; 368 Method_t method; 369 370 for (i = 0; i < method_list->method_count; i++) { 371 method = &(method_list->method_list[i]); 372 if (method->method_name 373 && method->method_name->sel_id == op->sel_id) { 374 imp = method->method_imp; 375 break; 376 } 377 } 378 379 if (imp) 380 break; 381 382 method_list = method_list->method_next; 383 384 } 385 if (imp) 386 (*imp) ((id) class, op); 387 388 } 389 } 390} 391 392/* Walk on the methods list of class and install the methods in the reverse 393 order of the lists. Since methods added by categories are before the methods 394 of class in the methods list, this allows categories to substitute methods 395 declared in class. However if more than one category replaces the same 396 method nothing is guaranteed about what method will be used. 397 Assumes that __objc_runtime_mutex is locked down. */ 398static void 399__objc_install_methods_in_dtable (Class class, MethodList_t method_list) 400{ 401 int i; 402 403 if (! method_list) 404 return; 405 406 if (method_list->method_next) 407 __objc_install_methods_in_dtable (class, method_list->method_next); 408 409 for (i = 0; i < method_list->method_count; i++) 410 { 411 Method_t method = &(method_list->method_list[i]); 412 sarray_at_put_safe (class->dtable, 413 (sidx) method->method_name->sel_id, 414 method->method_imp); 415 } 416} 417 418/* Assumes that __objc_runtime_mutex is locked down. */ 419static void 420__objc_install_dispatch_table_for_class (Class class) 421{ 422 Class super; 423 424 /* If the class has not yet had its class links resolved, we must 425 re-compute all class links */ 426 if (! CLS_ISRESOLV (class)) 427 __objc_resolve_class_links (); 428 429 super = class->super_class; 430 431 if (super != 0 && (super->dtable == __objc_uninstalled_dtable)) 432 __objc_install_dispatch_table_for_class (super); 433 434 /* Allocate dtable if necessary */ 435 if (super == 0) 436 { 437 objc_mutex_lock (__objc_runtime_mutex); 438 class->dtable = sarray_new (__objc_selector_max_index, 0); 439 objc_mutex_unlock (__objc_runtime_mutex); 440 } 441 else 442 class->dtable = sarray_lazy_copy (super->dtable); 443 444 __objc_install_methods_in_dtable (class, class->methods); 445} 446 447void 448__objc_update_dispatch_table_for_class (Class class) 449{ 450 Class next; 451 struct sarray *arr; 452 453 /* not yet installed -- skip it */ 454 if (class->dtable == __objc_uninstalled_dtable) 455 return; 456 457 objc_mutex_lock (__objc_runtime_mutex); 458 459 arr = class->dtable; 460 __objc_install_premature_dtable (class); /* someone might require it... */ 461 sarray_free (arr); /* release memory */ 462 463 /* could have been lazy... */ 464 __objc_install_dispatch_table_for_class (class); 465 466 if (class->subclass_list) /* Traverse subclasses */ 467 for (next = class->subclass_list; next; next = next->sibling_class) 468 __objc_update_dispatch_table_for_class (next); 469 470 objc_mutex_unlock (__objc_runtime_mutex); 471} 472 473 474/* This function adds a method list to a class. This function is 475 typically called by another function specific to the run-time. As 476 such this function does not worry about thread safe issues. 477 478 This one is only called for categories. Class objects have their 479 methods installed right away, and their selectors are made into 480 SEL's by the function __objc_register_selectors_from_class. */ 481void 482class_add_method_list (Class class, MethodList_t list) 483{ 484 /* Passing of a linked list is not allowed. Do multiple calls. */ 485 assert (! list->method_next); 486 487 __objc_register_selectors_from_list(list); 488 489 /* Add the methods to the class's method list. */ 490 list->method_next = class->methods; 491 class->methods = list; 492 493 /* Update the dispatch table of class */ 494 __objc_update_dispatch_table_for_class (class); 495} 496 497Method_t 498class_get_instance_method (Class class, SEL op) 499{ 500 return search_for_method_in_hierarchy (class, op); 501} 502 503Method_t 504class_get_class_method (MetaClass class, SEL op) 505{ 506 return search_for_method_in_hierarchy (class, op); 507} 508 509 510/* Search for a method starting from the current class up its hierarchy. 511 Return a pointer to the method's method structure if found. NULL 512 otherwise. */ 513 514static Method_t 515search_for_method_in_hierarchy (Class cls, SEL sel) 516{ 517 Method_t method = NULL; 518 Class class; 519 520 if (! sel_is_mapped (sel)) 521 return NULL; 522 523 /* Scan the method list of the class. If the method isn't found in the 524 list then step to its super class. */ 525 for (class = cls; ((! method) && class); class = class->super_class) 526 method = search_for_method_in_list (class->methods, sel); 527 528 return method; 529} 530 531 532 533/* Given a linked list of method and a method's name. Search for the named 534 method's method structure. Return a pointer to the method's method 535 structure if found. NULL otherwise. */ 536Method_t 537search_for_method_in_list (MethodList_t list, SEL op) 538{ 539 MethodList_t method_list = list; 540 541 if (! sel_is_mapped (op)) 542 return NULL; 543 544 /* If not found then we'll search the list. */ 545 while (method_list) 546 { 547 int i; 548 549 /* Search the method list. */ 550 for (i = 0; i < method_list->method_count; ++i) 551 { 552 Method_t method = &method_list->method_list[i]; 553 554 if (method->method_name) 555 if (method->method_name->sel_id == op->sel_id) 556 return method; 557 } 558 559 /* The method wasn't found. Follow the link to the next list of 560 methods. */ 561 method_list = method_list->method_next; 562 } 563 564 return NULL; 565} 566 567static retval_t __objc_forward (id object, SEL sel, arglist_t args); 568 569/* Forwarding pointers/integers through the normal registers */ 570static id 571__objc_word_forward (id rcv, SEL op, ...) 572{ 573 void *args, *res; 574 575 args = __builtin_apply_args (); 576 res = __objc_forward (rcv, op, args); 577 if (res) 578 __builtin_return (res); 579 else 580 return res; 581} 582 583/* Specific routine for forwarding floats/double because of 584 architectural differences on some processors. i386s for 585 example which uses a floating point stack versus general 586 registers for floating point numbers. This forward routine 587 makes sure that GCC restores the proper return values */ 588static double 589__objc_double_forward (id rcv, SEL op, ...) 590{ 591 void *args, *res; 592 593 args = __builtin_apply_args (); 594 res = __objc_forward (rcv, op, args); 595 __builtin_return (res); 596} 597 598#if INVISIBLE_STRUCT_RETURN 599static __big 600#else 601static id 602#endif 603__objc_block_forward (id rcv, SEL op, ...) 604{ 605 void *args, *res; 606 607 args = __builtin_apply_args (); 608 res = __objc_forward (rcv, op, args); 609 if (res) 610 __builtin_return (res); 611 else 612#if INVISIBLE_STRUCT_RETURN 613 return (__big) {{0, 0, 0, 0, 0, 0, 0, 0}}; 614#else 615 return nil; 616#endif 617} 618 619 620/* This function is installed in the dispatch table for all methods which are 621 not implemented. Thus, it is called when a selector is not recognized. */ 622static retval_t 623__objc_forward (id object, SEL sel, arglist_t args) 624{ 625 IMP imp; 626 static SEL frwd_sel = 0; /* !T:SAFE2 */ 627 SEL err_sel; 628 629 /* first try if the object understands forward:: */ 630 if (! frwd_sel) 631 frwd_sel = sel_get_any_uid ("forward::"); 632 633 if (__objc_responds_to (object, frwd_sel)) 634 { 635 imp = get_imp (object->class_pointer, frwd_sel); 636 return (*imp) (object, frwd_sel, sel, args); 637 } 638 639 /* If the object recognizes the doesNotRecognize: method then we're going 640 to send it. */ 641 err_sel = sel_get_any_uid ("doesNotRecognize:"); 642 if (__objc_responds_to (object, err_sel)) 643 { 644 imp = get_imp (object->class_pointer, err_sel); 645 return (*imp) (object, err_sel, sel); 646 } 647 648 /* The object doesn't recognize the method. Check for responding to 649 error:. If it does then sent it. */ 650 { 651 char msg[256 + strlen ((const char *) sel_get_name (sel)) 652 + strlen ((const char *) object->class_pointer->name)]; 653 654 sprintf (msg, "(%s) %s does not recognize %s", 655 (CLS_ISMETA (object->class_pointer) 656 ? "class" 657 : "instance" ), 658 object->class_pointer->name, sel_get_name (sel)); 659 660 err_sel = sel_get_any_uid ("error:"); 661 if (__objc_responds_to (object, err_sel)) 662 { 663 imp = get_imp (object->class_pointer, err_sel); 664 return (*imp) (object, sel_get_any_uid ("error:"), msg); 665 } 666 667 /* The object doesn't respond to doesNotRecognize: or error:; Therefore, 668 a default action is taken. */ 669 objc_error (object, OBJC_ERR_UNIMPLEMENTED, "%s\n", msg); 670 671 return 0; 672 } 673} 674 675void 676__objc_print_dtable_stats () 677{ 678 int total = 0; 679 680 objc_mutex_lock (__objc_runtime_mutex); 681 682#ifdef OBJC_SPARSE2 683 printf ("memory usage: (%s)\n", "2-level sparse arrays"); 684#else 685 printf ("memory usage: (%s)\n", "3-level sparse arrays"); 686#endif 687 688 printf ("arrays: %d = %ld bytes\n", narrays, 689 (long) ((size_t) narrays * sizeof (struct sarray))); 690 total += narrays * sizeof (struct sarray); 691 printf ("buckets: %d = %ld bytes\n", nbuckets, 692 (long) ((size_t) nbuckets * sizeof (struct sbucket))); 693 total += nbuckets * sizeof (struct sbucket); 694 695 printf ("idxtables: %d = %ld bytes\n", 696 idxsize, (long) ((size_t) idxsize * sizeof (void *))); 697 total += idxsize * sizeof (void *); 698 printf ("-----------------------------------\n"); 699 printf ("total: %d bytes\n", total); 700 printf ("===================================\n"); 701 702 objc_mutex_unlock (__objc_runtime_mutex); 703} 704 705/* Returns the uninstalled dispatch table indicator. 706 If a class' dispatch table points to __objc_uninstalled_dtable 707 then that means it needs its dispatch table to be installed. */ 708inline 709struct sarray * 710objc_get_uninstalled_dtable () 711{ 712 return __objc_uninstalled_dtable; 713} 714