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.
6 Lock-free class table code designed and written from scratch by
9 This file is part of GCC.
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.
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
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.
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/>. */
30 The code in this file critically affects class method invocation
31 speed. This long preamble comment explains why, and the issues
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
39 array = [NSArray new];
41 this gets basically compiled into the equivalent of
43 array = [(objc_get_class ("NSArray")) new];
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.
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:
53 Class arrayClass = [NSArray class];
57 array = [arrayClass new];
58 array = [arrayClass new];
59 array = [arrayClass new];
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.
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.
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.
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. */
90 #include "objc-private/common.h"
91 #include "objc-private/error.h"
92 #include "objc/runtime.h"
94 #include "objc-private/module-abi-8.h" /* For CLS_ISCLASS and similar. */
95 #include "objc-private/runtime.h" /* the kitchen sink */
96 #include <string.h> /* For memset */
98 /* We use a table which maps a class name to the corresponding class
99 * pointer. The first part of this file defines this table, and
100 * functions to do basic operations on the table. The second part of
101 * the file implements some higher level Objective-C functionality for
102 * classes by using the functions provided in the first part to manage
106 ** Class Table Internals
109 /* A node holding a class */
110 typedef struct class_node
112 struct class_node
*next
; /* Pointer to next entry on the list.
113 NULL indicates end of list. */
115 const char *name
; /* The class name string */
116 int length
; /* The class name string length */
117 Class pointer
; /* The Class pointer */
121 /* A table containing classes is a class_node_ptr (pointing to the
122 first entry in the table - if it is NULL, then the table is
125 /* We have 1024 tables. Each table contains all class names which
126 have the same hash (which is a number between 0 and 1023). To look
127 up a class_name, we compute its hash, and get the corresponding
128 table. Once we have the table, we simply compare strings directly
129 till we find the one which we want (using the length first). The
130 number of tables is quite big on purpose (a normal big application
131 has less than 1000 classes), so that you shouldn't normally get any
132 collisions, and get away with a single comparison (which we can't
133 avoid since we need to know that you have got the right thing). */
134 #define CLASS_TABLE_SIZE 1024
135 #define CLASS_TABLE_MASK 1023
137 static class_node_ptr class_table_array
[CLASS_TABLE_SIZE
];
139 /* The table writing mutex - we lock on writing to avoid conflicts
140 between different writers, but we read without locks. That is
141 possible because we assume pointer assignment to be an atomic
142 operation. TODO: This is only true under certain circumstances,
143 which should be clarified. */
144 static objc_mutex_t __class_table_lock
= NULL
;
146 /* CLASS_TABLE_HASH is how we compute the hash of a class name. It is
147 a macro - *not* a function - arguments *are* modified directly.
149 INDEX should be a variable holding an int;
150 HASH should be a variable holding an int;
151 CLASS_NAME should be a variable holding a (char *) to the class_name.
153 After the macro is executed, INDEX contains the length of the
154 string, and HASH the computed hash of the string; CLASS_NAME is
157 #define CLASS_TABLE_HASH(INDEX, HASH, CLASS_NAME) \
159 for (INDEX = 0; CLASS_NAME[INDEX] != '\0'; INDEX++) \
161 HASH = (HASH << 4) ^ (HASH >> 28) ^ CLASS_NAME[INDEX]; \
164 HASH = (HASH ^ (HASH >> 10) ^ (HASH >> 20)) & CLASS_TABLE_MASK;
166 /* Setup the table. */
168 class_table_setup (void)
170 /* Start - nothing in the table. */
171 memset (class_table_array
, 0, sizeof (class_node_ptr
) * CLASS_TABLE_SIZE
);
173 /* The table writing mutex. */
174 __class_table_lock
= objc_mutex_allocate ();
178 /* Insert a class in the table (used when a new class is registered). */
180 class_table_insert (const char *class_name
, Class class_pointer
)
183 class_node_ptr new_node
;
185 /* Find out the class name's hash and length. */
186 CLASS_TABLE_HASH (length
, hash
, class_name
);
188 /* Prepare the new node holding the class. */
189 new_node
= objc_malloc (sizeof (struct class_node
));
190 new_node
->name
= class_name
;
191 new_node
->length
= length
;
192 new_node
->pointer
= class_pointer
;
194 /* Lock the table for modifications. */
195 objc_mutex_lock (__class_table_lock
);
197 /* Insert the new node in the table at the beginning of the table at
198 class_table_array[hash]. */
199 new_node
->next
= class_table_array
[hash
];
200 class_table_array
[hash
] = new_node
;
202 objc_mutex_unlock (__class_table_lock
);
205 /* Replace a class in the table (used only by poseAs:). */
207 class_table_replace (Class old_class_pointer
, Class new_class_pointer
)
212 objc_mutex_lock (__class_table_lock
);
215 node
= class_table_array
[hash
];
217 while (hash
< CLASS_TABLE_SIZE
)
222 if (hash
< CLASS_TABLE_SIZE
)
224 node
= class_table_array
[hash
];
229 Class class1
= node
->pointer
;
231 if (class1
== old_class_pointer
)
233 node
->pointer
= new_class_pointer
;
239 objc_mutex_unlock (__class_table_lock
);
243 /* Get a class from the table. This does not need mutex protection.
244 Currently, this function is called each time you call a static
245 method, this is why it must be very fast. */
247 class_table_get_safe (const char *class_name
)
252 /* Compute length and hash. */
253 CLASS_TABLE_HASH (length
, hash
, class_name
);
255 node
= class_table_array
[hash
];
261 if (node
->length
== length
)
263 /* Compare the class names. */
266 for (i
= 0; i
< length
; i
++)
268 if ((node
->name
)[i
] != class_name
[i
])
276 /* They are equal! */
277 return node
->pointer
;
281 while ((node
= node
->next
) != NULL
);
287 /* Enumerate over the class table. */
288 struct class_table_enumerator
296 class_table_next (struct class_table_enumerator
**e
)
298 struct class_table_enumerator
*enumerator
= *e
;
301 if (enumerator
== NULL
)
303 *e
= objc_malloc (sizeof (struct class_table_enumerator
));
305 enumerator
->hash
= 0;
306 enumerator
->node
= NULL
;
308 next
= class_table_array
[enumerator
->hash
];
312 next
= enumerator
->node
->next
;
317 enumerator
->node
= next
;
318 return enumerator
->node
->pointer
;
324 while (enumerator
->hash
< CLASS_TABLE_SIZE
)
326 next
= class_table_array
[enumerator
->hash
];
329 enumerator
->node
= next
;
330 return enumerator
->node
->pointer
;
335 /* Ok - table finished - done. */
336 objc_free (enumerator
);
341 #if 0 /* DEBUGGING FUNCTIONS */
342 /* Debugging function - print the class table. */
344 class_table_print (void)
348 for (i
= 0; i
< CLASS_TABLE_SIZE
; i
++)
353 node
= class_table_array
[i
];
357 printf ("\t%s\n", node
->name
);
363 /* Debugging function - print an histogram of number of classes in
364 function of hash key values. Useful to evaluate the hash function
367 class_table_print_histogram (void)
372 for (i
= 0; i
< CLASS_TABLE_SIZE
; i
++)
376 node
= class_table_array
[i
];
383 if (((i
+ 1) % 50) == 0)
385 printf ("%4d:", i
+ 1);
386 for (j
= 0; j
< counter
; j
++)
394 printf ("%4d:", i
+ 1);
395 for (j
= 0; j
< counter
; j
++)
401 #endif /* DEBUGGING FUNCTIONS */
404 ** Objective-C runtime functions
407 /* From now on, the only access to the class table data structure
408 should be via the class_table_* functions. */
410 /* This is a hook which is called by objc_get_class and
411 objc_lookup_class if the runtime is not able to find the class.
412 This may e.g. try to load in the class using dynamic loading.
414 This hook was a public, global variable in the Traditional GNU
415 Objective-C Runtime API (objc/objc-api.h). The modern GNU
416 Objective-C Runtime API (objc/runtime.h) provides the
417 objc_setGetUnknownClassHandler() function instead.
419 Class (*_objc_lookup_class
) (const char *name
) = 0; /* !T:SAFE */
421 /* The handler currently in use. PS: if both
422 __obj_get_unknown_class_handler and _objc_lookup_class are defined,
423 __objc_get_unknown_class_handler is called first. */
424 static objc_get_unknown_class_handler
425 __objc_get_unknown_class_handler
= NULL
;
427 objc_get_unknown_class_handler
428 objc_setGetUnknownClassHandler (objc_get_unknown_class_handler
431 objc_get_unknown_class_handler old_handler
432 = __objc_get_unknown_class_handler
;
433 __objc_get_unknown_class_handler
= new_handler
;
438 /* True when class links has been resolved. */
439 BOOL __objc_class_links_resolved
= NO
; /* !T:UNUSED */
443 __objc_init_class_tables (void)
445 /* Allocate the class hash table. */
447 if (__class_table_lock
)
450 objc_mutex_lock (__objc_runtime_mutex
);
452 class_table_setup ();
454 objc_mutex_unlock (__objc_runtime_mutex
);
457 /* This function adds a class to the class hash table, and assigns the
458 class a number, unless it's already known. */
460 __objc_add_class_to_hash (Class
class)
464 objc_mutex_lock (__objc_runtime_mutex
);
466 /* Make sure the table is there. */
467 assert (__class_table_lock
);
469 /* Make sure it's not a meta class. */
470 assert (CLS_ISCLASS (class));
472 /* Check to see if the class is already in the hash table. */
473 h_class
= class_table_get_safe (class->name
);
476 /* The class isn't in the hash table. Add the class and assign a class
478 static unsigned int class_number
= 1;
480 CLS_SETNUMBER (class, class_number
);
481 CLS_SETNUMBER (class->class_pointer
, class_number
);
484 class_table_insert (class->name
, class);
487 objc_mutex_unlock (__objc_runtime_mutex
);
491 objc_getClass (const char *name
)
498 class = class_table_get_safe (name
);
503 if (__objc_get_unknown_class_handler
)
504 return (*__objc_get_unknown_class_handler
) (name
);
506 if (_objc_lookup_class
)
507 return (*_objc_lookup_class
) (name
);
513 objc_lookupClass (const char *name
)
518 return class_table_get_safe (name
);
522 objc_getMetaClass (const char *name
)
524 Class
class = objc_getClass (name
);
527 return class->class_pointer
;
533 objc_getRequiredClass (const char *name
)
535 Class
class = objc_getClass (name
);
540 _objc_abort ("objc_getRequiredClass ('%s') failed: class not found\n", name
);
544 objc_getClassList (Class
*returnValue
, int maxNumberOfClassesToReturn
)
546 /* Iterate over all entries in the table. */
549 objc_mutex_lock (__class_table_lock
);
551 for (hash
= 0; hash
< CLASS_TABLE_SIZE
; hash
++)
553 class_node_ptr node
= class_table_array
[hash
];
559 if (count
< maxNumberOfClassesToReturn
)
560 returnValue
[count
] = node
->pointer
;
563 objc_mutex_unlock (__class_table_lock
);
572 objc_mutex_unlock (__class_table_lock
);
576 /* Traditional GNU Objective-C Runtime API. */
577 /* Get the class object for the class named NAME. If NAME does not
578 identify a known class, the hook _objc_lookup_class is called. If
579 this fails, nil is returned. */
581 objc_lookup_class (const char *name
)
583 return objc_getClass (name
);
586 /* Traditional GNU Objective-C Runtime API. Important: this method is
587 called automatically by the compiler while messaging (if using the
588 traditional ABI), so it is worth keeping it fast; don't make it
589 just a wrapper around objc_getClass(). */
590 /* Note that this is roughly equivalent to objc_getRequiredClass(). */
591 /* Get the class object for the class named NAME. If NAME does not
592 identify a known class, the hook _objc_lookup_class is called. If
593 this fails, an error message is issued and the system aborts. */
595 objc_get_class (const char *name
)
599 class = class_table_get_safe (name
);
604 if (__objc_get_unknown_class_handler
)
605 class = (*__objc_get_unknown_class_handler
) (name
);
607 if ((!class) && _objc_lookup_class
)
608 class = (*_objc_lookup_class
) (name
);
613 _objc_abort ("objc runtime: cannot find class %s\n", name
);
619 objc_get_meta_class (const char *name
)
621 return objc_get_class (name
)->class_pointer
;
624 /* This function provides a way to enumerate all the classes in the
625 executable. Pass *ENUM_STATE == NULL to start the enumeration. The
626 function will return 0 when there are no more classes.
630 while ((class = objc_next_class (&es)))
631 ... do something with class;
634 objc_next_class (void **enum_state
)
638 objc_mutex_lock (__objc_runtime_mutex
);
640 /* Make sure the table is there. */
641 assert (__class_table_lock
);
643 class = class_table_next ((struct class_table_enumerator
**) enum_state
);
645 objc_mutex_unlock (__objc_runtime_mutex
);
650 /* Resolve super/subclass links for all classes. The only thing we
651 can be sure of is that the class_pointer for class objects point to
652 the right meta class objects. */
654 __objc_resolve_class_links (void)
656 struct class_table_enumerator
*es
= NULL
;
657 Class object_class
= objc_get_class ("Object");
660 assert (object_class
);
662 objc_mutex_lock (__objc_runtime_mutex
);
664 /* Assign subclass links. */
665 while ((class1
= class_table_next (&es
)))
667 /* Make sure we have what we think we have. */
668 assert (CLS_ISCLASS (class1
));
669 assert (CLS_ISMETA (class1
->class_pointer
));
671 /* The class_pointer of all meta classes point to Object's meta
673 class1
->class_pointer
->class_pointer
= object_class
->class_pointer
;
675 if (! CLS_ISRESOLV (class1
))
677 CLS_SETRESOLV (class1
);
678 CLS_SETRESOLV (class1
->class_pointer
);
680 if (class1
->super_class
)
683 = objc_get_class ((char *) class1
->super_class
);
685 assert (a_super_class
);
687 DEBUG_PRINTF ("making class connections for: %s\n",
690 /* Assign subclass links for superclass. */
691 class1
->sibling_class
= a_super_class
->subclass_list
;
692 a_super_class
->subclass_list
= class1
;
694 /* Assign subclass links for meta class of superclass. */
695 if (a_super_class
->class_pointer
)
697 class1
->class_pointer
->sibling_class
698 = a_super_class
->class_pointer
->subclass_list
;
699 a_super_class
->class_pointer
->subclass_list
700 = class1
->class_pointer
;
703 else /* A root class, make its meta object be a subclass of
706 class1
->class_pointer
->sibling_class
707 = object_class
->subclass_list
;
708 object_class
->subclass_list
= class1
->class_pointer
;
713 /* Assign superclass links. */
715 while ((class1
= class_table_next (&es
)))
718 for (sub_class
= class1
->subclass_list
; sub_class
;
719 sub_class
= sub_class
->sibling_class
)
721 sub_class
->super_class
= class1
;
722 if (CLS_ISCLASS (sub_class
))
723 sub_class
->class_pointer
->super_class
= class1
->class_pointer
;
727 objc_mutex_unlock (__objc_runtime_mutex
);
731 class_getName (Class class_
)
740 class_isMetaClass (Class class_
)
742 /* CLS_ISMETA includes the check for Nil class_. */
743 return CLS_ISMETA (class_
);
747 class_getSuperclass (Class class_
)
752 return class_
->super_class
;
756 class_getVersion (Class class_
)
761 return (int)(class_
->version
);
765 class_setVersion (Class class_
, int version
)
770 class_
->version
= version
;
774 class_getInstanceSize (Class class_
)
779 return class_
->instance_size
;
782 #define CLASSOF(c) ((c)->class_pointer)
785 class_pose_as (Class impostor
, Class super_class
)
787 if (! CLS_ISRESOLV (impostor
))
788 __objc_resolve_class_links ();
792 assert (super_class
);
793 assert (impostor
->super_class
== super_class
);
794 assert (CLS_ISCLASS (impostor
));
795 assert (CLS_ISCLASS (super_class
));
796 assert (impostor
->instance_size
== super_class
->instance_size
);
799 Class
*subclass
= &(super_class
->subclass_list
);
801 /* Move subclasses of super_class to impostor. */
804 Class nextSub
= (*subclass
)->sibling_class
;
806 if (*subclass
!= impostor
)
808 Class sub
= *subclass
;
811 sub
->sibling_class
= impostor
->subclass_list
;
812 sub
->super_class
= impostor
;
813 impostor
->subclass_list
= sub
;
815 /* It will happen that SUB is not a class object if it is
816 the top of the meta class hierarchy chain (root
817 meta-class objects inherit their class object). If
818 that is the case... don't mess with the meta-meta
820 if (CLS_ISCLASS (sub
))
823 CLASSOF (sub
)->sibling_class
=
824 CLASSOF (impostor
)->subclass_list
;
825 CLASSOF (sub
)->super_class
= CLASSOF (impostor
);
826 CLASSOF (impostor
)->subclass_list
= CLASSOF (sub
);
833 /* Set subclasses of superclass to be impostor only. */
834 super_class
->subclass_list
= impostor
;
835 CLASSOF (super_class
)->subclass_list
= CLASSOF (impostor
);
837 /* Set impostor to have no sibling classes. */
838 impostor
->sibling_class
= 0;
839 CLASSOF (impostor
)->sibling_class
= 0;
842 /* Check relationship of impostor and super_class is kept. */
843 assert (impostor
->super_class
== super_class
);
844 assert (CLASSOF (impostor
)->super_class
== CLASSOF (super_class
));
846 /* This is how to update the lookup table. Regardless of what the
847 keys of the hashtable is, change all values that are superclass
850 objc_mutex_lock (__objc_runtime_mutex
);
852 class_table_replace (super_class
, impostor
);
854 objc_mutex_unlock (__objc_runtime_mutex
);
856 /* Next, we update the dispatch tables... */
857 __objc_update_dispatch_table_for_class (CLASSOF (impostor
));
858 __objc_update_dispatch_table_for_class (impostor
);