1 /* GNU Objective C Runtime class related functions 2 Copyright (C) 1993, 1995, 1996, 1997, 2001, 2002, 2009 3 Free Software Foundation, Inc. 4 Contributed by Kresten Krab Thorup and Dennis Glatting. 5 6 Lock-free class table code designed and written from scratch by 7 Nicola Pero, 2001. 8 9 This file is part of GCC. 10 11 GCC is free software; you can redistribute it and/or modify it under the 12 terms of the GNU General Public License as published by the Free Software 13 Foundation; either version 3, or (at your option) any later version. 14 15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 18 details. 19 20 Under Section 7 of GPL version 3, you are granted additional 21 permissions described in the GCC Runtime Library Exception, version 22 3.1, as published by the Free Software Foundation. 23 24 You should have received a copy of the GNU General Public License and 25 a copy of the GCC Runtime Library Exception along with this program; 26 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 27 <http://www.gnu.org/licenses/>. */ 28 29 /* 30 The code in this file critically affects class method invocation 31 speed. This long preamble comment explains why, and the issues 32 involved. 33 34 35 One of the traditional weaknesses of the GNU Objective-C runtime is 36 that class method invocations are slow. The reason is that when you 37 write 38 39 array = [NSArray new]; 40 41 this gets basically compiled into the equivalent of 42 43 array = [(objc_get_class ("NSArray")) new]; 44 45 objc_get_class returns the class pointer corresponding to the string 46 `NSArray'; and because of the lookup, the operation is more 47 complicated and slow than a simple instance method invocation. 48 49 Most high performance Objective-C code (using the GNU Objc runtime) 50 I had the opportunity to read (or write) work around this problem by 51 caching the class pointer: 52 53 Class arrayClass = [NSArray class]; 54 55 ... later on ... 56 57 array = [arrayClass new]; 58 array = [arrayClass new]; 59 array = [arrayClass new]; 60 61 In this case, you always perform a class lookup (the first one), but 62 then all the [arrayClass new] methods run exactly as fast as an 63 instance method invocation. It helps if you have many class method 64 invocations to the same class. 65 66 The long-term solution to this problem would be to modify the 67 compiler to output tables of class pointers corresponding to all the 68 class method invocations, and to add code to the runtime to update 69 these tables - that should in the end allow class method invocations 70 to perform precisely as fast as instance method invocations, because 71 no class lookup would be involved. I think the Apple Objective-C 72 runtime uses this technique. Doing this involves synchronized 73 modifications in the runtime and in the compiler. 74 75 As a first medicine to the problem, I [NP] have redesigned and 76 rewritten the way the runtime is performing class lookup. This 77 doesn't give as much speed as the other (definitive) approach, but 78 at least a class method invocation now takes approximately 4.5 times 79 an instance method invocation on my machine (it would take approx 12 80 times before the rewriting), which is a lot better. 81 82 One of the main reason the new class lookup is so faster is because 83 I implemented it in a way that can safely run multithreaded without 84 using locks - a so-called `lock-free' data structure. The atomic 85 operation is pointer assignment. The reason why in this problem 86 lock-free data structures work so well is that you never remove 87 classes from the table - and the difficult thing with lock-free data 88 structures is freeing data when is removed from the structures. */ 89 90 #include "objc/runtime.h" /* the kitchen sink */ 91 #include "objc/sarray.h" 92 93 #include "objc/objc.h" 94 #include "objc/objc-api.h" 95 #include "objc/thr.h" 96 97 /* We use a table which maps a class name to the corresponding class 98 * pointer. The first part of this file defines this table, and 99 * functions to do basic operations on the table. The second part of 100 * the file implements some higher level Objective-C functionality for 101 * classes by using the functions provided in the first part to manage 102 * the table. */ 103 104 /** 105 ** Class Table Internals 106 **/ 107 108 /* A node holding a class */ 109 typedef struct class_node 110 { 111 struct class_node *next; /* Pointer to next entry on the list. 112 NULL indicates end of list. */ 113 114 const char *name; /* The class name string */ 115 int length; /* The class name string length */ 116 Class pointer; /* The Class pointer */ 117 118 } *class_node_ptr; 119 120 /* A table containing classes is a class_node_ptr (pointing to the 121 first entry in the table - if it is NULL, then the table is 122 empty). */ 123 124 /* We have 1024 tables. Each table contains all class names which 125 have the same hash (which is a number between 0 and 1023). To look 126 up a class_name, we compute its hash, and get the corresponding 127 table. Once we have the table, we simply compare strings directly 128 till we find the one which we want (using the length first). The 129 number of tables is quite big on purpose (a normal big application 130 has less than 1000 classes), so that you shouldn't normally get any 131 collisions, and get away with a single comparison (which we can't 132 avoid since we need to know that you have got the right thing). */ 133 #define CLASS_TABLE_SIZE 1024 134 #define CLASS_TABLE_MASK 1023 135 136 static class_node_ptr class_table_array[CLASS_TABLE_SIZE]; 137 138 /* The table writing mutex - we lock on writing to avoid conflicts 139 between different writers, but we read without locks. That is 140 possible because we assume pointer assignment to be an atomic 141 operation. */ 142 static objc_mutex_t __class_table_lock = NULL; 143 144 /* CLASS_TABLE_HASH is how we compute the hash of a class name. It is 145 a macro - *not* a function - arguments *are* modified directly. 146 147 INDEX should be a variable holding an int; 148 HASH should be a variable holding an int; 149 CLASS_NAME should be a variable holding a (char *) to the class_name. 150 151 After the macro is executed, INDEX contains the length of the 152 string, and HASH the computed hash of the string; CLASS_NAME is 153 untouched. */ 154 155 #define CLASS_TABLE_HASH(INDEX, HASH, CLASS_NAME) \ 156 HASH = 0; \ 157 for (INDEX = 0; CLASS_NAME[INDEX] != '\0'; INDEX++) \ 158 { \ 159 HASH = (HASH << 4) ^ (HASH >> 28) ^ CLASS_NAME[INDEX]; \ 160 } \ 161 \ 162 HASH = (HASH ^ (HASH >> 10) ^ (HASH >> 20)) & CLASS_TABLE_MASK; 163 164 /* Setup the table. */ 165 static void 166 class_table_setup (void) 167 { 168 /* Start - nothing in the table. */ 169 memset (class_table_array, 0, sizeof (class_node_ptr) * CLASS_TABLE_SIZE); 170 171 /* The table writing mutex. */ 172 __class_table_lock = objc_mutex_allocate (); 173 } 174 175 176 /* Insert a class in the table (used when a new class is registered). */ 177 static void 178 class_table_insert (const char *class_name, Class class_pointer) 179 { 180 int hash, length; 181 class_node_ptr new_node; 182 183 /* Find out the class name's hash and length. */ 184 CLASS_TABLE_HASH (length, hash, class_name); 185 186 /* Prepare the new node holding the class. */ 187 new_node = objc_malloc (sizeof (struct class_node)); 188 new_node->name = class_name; 189 new_node->length = length; 190 new_node->pointer = class_pointer; 191 192 /* Lock the table for modifications. */ 193 objc_mutex_lock (__class_table_lock); 194 195 /* Insert the new node in the table at the beginning of the table at 196 class_table_array[hash]. */ 197 new_node->next = class_table_array[hash]; 198 class_table_array[hash] = new_node; 199 200 objc_mutex_unlock (__class_table_lock); 201 } 202 203 /* Replace a class in the table (used only by poseAs:). */ 204 static void 205 class_table_replace (Class old_class_pointer, Class new_class_pointer) 206 { 207 int hash; 208 class_node_ptr node; 209 210 objc_mutex_lock (__class_table_lock); 211 212 hash = 0; 213 node = class_table_array[hash]; 214 215 while (hash < CLASS_TABLE_SIZE) 216 { 217 if (node == NULL) 218 { 219 hash++; 220 if (hash < CLASS_TABLE_SIZE) 221 { 222 node = class_table_array[hash]; 223 } 224 } 225 else 226 { 227 Class class1 = node->pointer; 228 229 if (class1 == old_class_pointer) 230 { 231 node->pointer = new_class_pointer; 232 } 233 node = node->next; 234 } 235 } 236 237 objc_mutex_unlock (__class_table_lock); 238 } 239 240 241 /* Get a class from the table. This does not need mutex protection. 242 Currently, this function is called each time you call a static 243 method, this is why it must be very fast. */ 244 static inline Class 245 class_table_get_safe (const char *class_name) 246 { 247 class_node_ptr node; 248 int length, hash; 249 250 /* Compute length and hash. */ 251 CLASS_TABLE_HASH (length, hash, class_name); 252 253 node = class_table_array[hash]; 254 255 if (node != NULL) 256 { 257 do 258 { 259 if (node->length == length) 260 { 261 /* Compare the class names. */ 262 int i; 263 264 for (i = 0; i < length; i++) 265 { 266 if ((node->name)[i] != class_name[i]) 267 { 268 break; 269 } 270 } 271 272 if (i == length) 273 { 274 /* They are equal! */ 275 return node->pointer; 276 } 277 } 278 } 279 while ((node = node->next) != NULL); 280 } 281 282 return Nil; 283 } 284 285 /* Enumerate over the class table. */ 286 struct class_table_enumerator 287 { 288 int hash; 289 class_node_ptr node; 290 }; 291 292 293 static Class 294 class_table_next (struct class_table_enumerator **e) 295 { 296 struct class_table_enumerator *enumerator = *e; 297 class_node_ptr next; 298 299 if (enumerator == NULL) 300 { 301 *e = objc_malloc (sizeof (struct class_table_enumerator)); 302 enumerator = *e; 303 enumerator->hash = 0; 304 enumerator->node = NULL; 305 306 next = class_table_array[enumerator->hash]; 307 } 308 else 309 { 310 next = enumerator->node->next; 311 } 312 313 if (next != NULL) 314 { 315 enumerator->node = next; 316 return enumerator->node->pointer; 317 } 318 else 319 { 320 enumerator->hash++; 321 322 while (enumerator->hash < CLASS_TABLE_SIZE) 323 { 324 next = class_table_array[enumerator->hash]; 325 if (next != NULL) 326 { 327 enumerator->node = next; 328 return enumerator->node->pointer; 329 } 330 enumerator->hash++; 331 } 332 333 /* Ok - table finished - done. */ 334 objc_free (enumerator); 335 return Nil; 336 } 337 } 338 339 #if 0 /* DEBUGGING FUNCTIONS */ 340 /* Debugging function - print the class table. */ 341 void 342 class_table_print (void) 343 { 344 int i; 345 346 for (i = 0; i < CLASS_TABLE_SIZE; i++) 347 { 348 class_node_ptr node; 349 350 printf ("%d:\n", i); 351 node = class_table_array[i]; 352 353 while (node != NULL) 354 { 355 printf ("\t%s\n", node->name); 356 node = node->next; 357 } 358 } 359 } 360 361 /* Debugging function - print an histogram of number of classes in 362 function of hash key values. Useful to evaluate the hash function 363 in real cases. */ 364 void 365 class_table_print_histogram (void) 366 { 367 int i, j; 368 int counter = 0; 369 370 for (i = 0; i < CLASS_TABLE_SIZE; i++) 371 { 372 class_node_ptr node; 373 374 node = class_table_array[i]; 375 376 while (node != NULL) 377 { 378 counter++; 379 node = node->next; 380 } 381 if (((i + 1) % 50) == 0) 382 { 383 printf ("%4d:", i + 1); 384 for (j = 0; j < counter; j++) 385 { 386 printf ("X"); 387 } 388 printf ("\n"); 389 counter = 0; 390 } 391 } 392 printf ("%4d:", i + 1); 393 for (j = 0; j < counter; j++) 394 { 395 printf ("X"); 396 } 397 printf ("\n"); 398 } 399 #endif /* DEBUGGING FUNCTIONS */ 400 401 /** 402 ** Objective-C runtime functions 403 **/ 404 405 /* From now on, the only access to the class table data structure 406 should be via the class_table_* functions. */ 407 408 /* This is a hook which is called by objc_get_class and 409 objc_lookup_class if the runtime is not able to find the class. 410 This may e.g. try to load in the class using dynamic loading. */ 411 Class (*_objc_lookup_class) (const char *name) = 0; /* !T:SAFE */ 412 413 414 /* True when class links has been resolved. */ 415 BOOL __objc_class_links_resolved = NO; /* !T:UNUSED */ 416 417 418 void 419 __objc_init_class_tables (void) 420 { 421 /* Allocate the class hash table. */ 422 423 if (__class_table_lock) 424 return; 425 426 objc_mutex_lock (__objc_runtime_mutex); 427 428 class_table_setup (); 429 430 objc_mutex_unlock (__objc_runtime_mutex); 431 } 432 433 /* This function adds a class to the class hash table, and assigns the 434 class a number, unless it's already known. */ 435 void 436 __objc_add_class_to_hash (Class class) 437 { 438 Class h_class; 439 440 objc_mutex_lock (__objc_runtime_mutex); 441 442 /* Make sure the table is there. */ 443 assert (__class_table_lock); 444 445 /* Make sure it's not a meta class. */ 446 assert (CLS_ISCLASS (class)); 447 448 /* Check to see if the class is already in the hash table. */ 449 h_class = class_table_get_safe (class->name); 450 if (! h_class) 451 { 452 /* The class isn't in the hash table. Add the class and assign a class 453 number. */ 454 static unsigned int class_number = 1; 455 456 CLS_SETNUMBER (class, class_number); 457 CLS_SETNUMBER (class->class_pointer, class_number); 458 459 ++class_number; 460 class_table_insert (class->name, class); 461 } 462 463 objc_mutex_unlock (__objc_runtime_mutex); 464 } 465 466 /* Get the class object for the class named NAME. If NAME does not 467 identify a known class, the hook _objc_lookup_class is called. If 468 this fails, nil is returned. */ 469 Class 470 objc_lookup_class (const char *name) 471 { 472 Class class; 473 474 class = class_table_get_safe (name); 475 476 if (class) 477 return class; 478 479 if (_objc_lookup_class) 480 return (*_objc_lookup_class) (name); 481 else 482 return 0; 483 } 484 485 /* Get the class object for the class named NAME. If NAME does not 486 identify a known class, the hook _objc_lookup_class is called. If 487 this fails, an error message is issued and the system aborts. */ 488 Class 489 objc_get_class (const char *name) 490 { 491 Class class; 492 493 class = class_table_get_safe (name); 494 495 if (class) 496 return class; 497 498 if (_objc_lookup_class) 499 class = (*_objc_lookup_class) (name); 500 501 if (class) 502 return class; 503 504 objc_error (nil, OBJC_ERR_BAD_CLASS, 505 "objc runtime: cannot find class %s\n", name); 506 return 0; 507 } 508 509 MetaClass 510 objc_get_meta_class (const char *name) 511 { 512 return objc_get_class (name)->class_pointer; 513 } 514 515 /* This function provides a way to enumerate all the classes in the 516 executable. Pass *ENUM_STATE == NULL to start the enumeration. The 517 function will return 0 when there are no more classes. 518 For example: 519 id class; 520 void *es = NULL; 521 while ((class = objc_next_class (&es))) 522 ... do something with class; 523 */ 524 Class 525 objc_next_class (void **enum_state) 526 { 527 Class class; 528 529 objc_mutex_lock (__objc_runtime_mutex); 530 531 /* Make sure the table is there. */ 532 assert (__class_table_lock); 533 534 class = class_table_next ((struct class_table_enumerator **) enum_state); 535 536 objc_mutex_unlock (__objc_runtime_mutex); 537 538 return class; 539 } 540 541 /* Resolve super/subclass links for all classes. The only thing we 542 can be sure of is that the class_pointer for class objects point to 543 the right meta class objects. */ 544 void 545 __objc_resolve_class_links (void) 546 { 547 struct class_table_enumerator *es = NULL; 548 Class object_class = objc_get_class ("Object"); 549 Class class1; 550 551 assert (object_class); 552 553 objc_mutex_lock (__objc_runtime_mutex); 554 555 /* Assign subclass links. */ 556 while ((class1 = class_table_next (&es))) 557 { 558 /* Make sure we have what we think we have. */ 559 assert (CLS_ISCLASS (class1)); 560 assert (CLS_ISMETA (class1->class_pointer)); 561 562 /* The class_pointer of all meta classes point to Object's meta 563 class. */ 564 class1->class_pointer->class_pointer = object_class->class_pointer; 565 566 if (! CLS_ISRESOLV (class1)) 567 { 568 CLS_SETRESOLV (class1); 569 CLS_SETRESOLV (class1->class_pointer); 570 571 if (class1->super_class) 572 { 573 Class a_super_class 574 = objc_get_class ((char *) class1->super_class); 575 576 assert (a_super_class); 577 578 DEBUG_PRINTF ("making class connections for: %s\n", 579 class1->name); 580 581 /* Assign subclass links for superclass. */ 582 class1->sibling_class = a_super_class->subclass_list; 583 a_super_class->subclass_list = class1; 584 585 /* Assign subclass links for meta class of superclass. */ 586 if (a_super_class->class_pointer) 587 { 588 class1->class_pointer->sibling_class 589 = a_super_class->class_pointer->subclass_list; 590 a_super_class->class_pointer->subclass_list 591 = class1->class_pointer; 592 } 593 } 594 else /* A root class, make its meta object be a subclass of 595 Object. */ 596 { 597 class1->class_pointer->sibling_class 598 = object_class->subclass_list; 599 object_class->subclass_list = class1->class_pointer; 600 } 601 } 602 } 603 604 /* Assign superclass links. */ 605 es = NULL; 606 while ((class1 = class_table_next (&es))) 607 { 608 Class sub_class; 609 for (sub_class = class1->subclass_list; sub_class; 610 sub_class = sub_class->sibling_class) 611 { 612 sub_class->super_class = class1; 613 if (CLS_ISCLASS (sub_class)) 614 sub_class->class_pointer->super_class = class1->class_pointer; 615 } 616 } 617 618 objc_mutex_unlock (__objc_runtime_mutex); 619 } 620 621 622 623 #define CLASSOF(c) ((c)->class_pointer) 624 625 Class 626 class_pose_as (Class impostor, Class super_class) 627 { 628 if (! CLS_ISRESOLV (impostor)) 629 __objc_resolve_class_links (); 630 631 /* Preconditions */ 632 assert (impostor); 633 assert (super_class); 634 assert (impostor->super_class == super_class); 635 assert (CLS_ISCLASS (impostor)); 636 assert (CLS_ISCLASS (super_class)); 637 assert (impostor->instance_size == super_class->instance_size); 638 639 { 640 Class *subclass = &(super_class->subclass_list); 641 642 /* Move subclasses of super_class to impostor. */ 643 while (*subclass) 644 { 645 Class nextSub = (*subclass)->sibling_class; 646 647 if (*subclass != impostor) 648 { 649 Class sub = *subclass; 650 651 /* Classes */ 652 sub->sibling_class = impostor->subclass_list; 653 sub->super_class = impostor; 654 impostor->subclass_list = sub; 655 656 /* It will happen that SUB is not a class object if it is 657 the top of the meta class hierarchy chain (root 658 meta-class objects inherit their class object). If 659 that is the case... don't mess with the meta-meta 660 class. */ 661 if (CLS_ISCLASS (sub)) 662 { 663 /* Meta classes */ 664 CLASSOF (sub)->sibling_class = 665 CLASSOF (impostor)->subclass_list; 666 CLASSOF (sub)->super_class = CLASSOF (impostor); 667 CLASSOF (impostor)->subclass_list = CLASSOF (sub); 668 } 669 } 670 671 *subclass = nextSub; 672 } 673 674 /* Set subclasses of superclass to be impostor only. */ 675 super_class->subclass_list = impostor; 676 CLASSOF (super_class)->subclass_list = CLASSOF (impostor); 677 678 /* Set impostor to have no sibling classes. */ 679 impostor->sibling_class = 0; 680 CLASSOF (impostor)->sibling_class = 0; 681 } 682 683 /* Check relationship of impostor and super_class is kept. */ 684 assert (impostor->super_class == super_class); 685 assert (CLASSOF (impostor)->super_class == CLASSOF (super_class)); 686 687 /* This is how to update the lookup table. Regardless of what the 688 keys of the hashtable is, change all values that are superclass 689 into impostor. */ 690 691 objc_mutex_lock (__objc_runtime_mutex); 692 693 class_table_replace (super_class, impostor); 694 695 objc_mutex_unlock (__objc_runtime_mutex); 696 697 /* Next, we update the dispatch tables... */ 698 __objc_update_dispatch_table_for_class (CLASSOF (impostor)); 699 __objc_update_dispatch_table_for_class (impostor); 700 701 return impostor; 702 } 703