1 /* GNU Objective C Runtime class related functions
2 Copyright (C) 1993, 1995, 1996, 1997, 2001, 2002
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 2, 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 You should have received a copy of the GNU General Public License along with
21 GCC; see the file COPYING. If not, write to the Free Software
22 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
24 /* As a special exception, if you link this library with files compiled with
25 GCC to produce an executable, this does not cause the resulting executable
26 to be covered by the GNU General Public License. This exception does not
27 however invalidate any other reasons why the executable file might be
28 covered by the GNU General Public License. */
31 The code in this file critically affects class method invocation
32 speed. This long preamble comment explains why, and the issues
36 One of the traditional weaknesses of the GNU Objective-C runtime is
37 that class method invocations are slow. The reason is that when you
40 array = [NSArray new];
42 this gets basically compiled into the equivalent of
44 array = [(objc_get_class ("NSArray")) new];
46 objc_get_class returns the class pointer corresponding to the string
47 `NSArray'; and because of the lookup, the operation is more
48 complicated and slow than a simple instance method invocation.
50 Most high performance Objective-C code (using the GNU Objc runtime)
51 I had the opportunity to read (or write) work around this problem by
52 caching the class pointer:
54 Class arrayClass = [NSArray class];
58 array = [arrayClass new];
59 array = [arrayClass new];
60 array = [arrayClass new];
62 In this case, you always perform a class lookup (the first one), but
63 then all the [arrayClass new] methods run exactly as fast as an
64 instance method invocation. It helps if you have many class method
65 invocations to the same class.
67 The long-term solution to this problem would be to modify the
68 compiler to output tables of class pointers corresponding to all the
69 class method invocations, and to add code to the runtime to update
70 these tables - that should in the end allow class method invocations
71 to perform precisely as fast as instance method invocations, because
72 no class lookup would be involved. I think the Apple Objective-C
73 runtime uses this technique. Doing this involves synchronized
74 modifications in the runtime and in the compiler.
76 As a first medicine to the problem, I [NP] have redesigned and
77 rewritten the way the runtime is performing class lookup. This
78 doesn't give as much speed as the other (definitive) approach, but
79 at least a class method invocation now takes approximately 4.5 times
80 an instance method invocation on my machine (it would take approx 12
81 times before the rewriting), which is a lot better.
83 One of the main reason the new class lookup is so faster is because
84 I implemented it in a way that can safely run multithreaded without
85 using locks - a so-called `lock-free' data structure. The atomic
86 operation is pointer assignment. The reason why in this problem
87 lock-free data structures work so well is that you never remove
88 classes from the table - and the difficult thing with lock-free data
89 structures is freeing data when is removed from the structures. */
91 #include "runtime.h" /* the kitchen sink */
94 #include <objc/objc.h>
95 #include <objc/objc-api.h>
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
143 static objc_mutex_t __class_table_lock
= NULL
;
145 /* CLASS_TABLE_HASH is how we compute the hash of a class name. It is
146 a macro - *not* a function - arguments *are* modified directly.
148 INDEX should be a variable holding an int;
149 HASH should be a variable holding an int;
150 CLASS_NAME should be a variable holding a (char *) to the class_name.
152 After the macro is executed, INDEX contains the length of the
153 string, and HASH the computed hash of the string; CLASS_NAME is
156 #define CLASS_TABLE_HASH(INDEX, HASH, CLASS_NAME) \
158 for (INDEX = 0; CLASS_NAME[INDEX] != '\0'; INDEX++) \
160 HASH = (HASH << 4) ^ (HASH >> 28) ^ CLASS_NAME[INDEX]; \
163 HASH = (HASH ^ (HASH >> 10) ^ (HASH >> 20)) & CLASS_TABLE_MASK;
165 /* Setup the table. */
167 class_table_setup (void)
169 /* Start - nothing in the table. */
170 memset (class_table_array
, 0, sizeof (class_node_ptr
) * CLASS_TABLE_SIZE
);
172 /* The table writing mutex. */
173 __class_table_lock
= objc_mutex_allocate ();
177 /* Insert a class in the table (used when a new class is registered). */
179 class_table_insert (const char *class_name
, Class class_pointer
)
182 class_node_ptr new_node
;
184 /* Find out the class name's hash and length. */
185 CLASS_TABLE_HASH (length
, hash
, class_name
);
187 /* Prepare the new node holding the class. */
188 new_node
= objc_malloc (sizeof (struct class_node
));
189 new_node
->name
= class_name
;
190 new_node
->length
= length
;
191 new_node
->pointer
= class_pointer
;
193 /* Lock the table for modifications. */
194 objc_mutex_lock (__class_table_lock
);
196 /* Insert the new node in the table at the beginning of the table at
197 class_table_array[hash]. */
198 new_node
->next
= class_table_array
[hash
];
199 class_table_array
[hash
] = new_node
;
201 objc_mutex_unlock (__class_table_lock
);
204 /* Replace a class in the table (used only by poseAs:). */
206 class_table_replace (Class old_class_pointer
, Class new_class_pointer
)
211 objc_mutex_lock (__class_table_lock
);
214 node
= class_table_array
[hash
];
216 while (hash
< CLASS_TABLE_SIZE
)
221 if (hash
< CLASS_TABLE_SIZE
)
223 node
= class_table_array
[hash
];
228 Class class1
= node
->pointer
;
230 if (class1
== old_class_pointer
)
232 node
->pointer
= new_class_pointer
;
238 objc_mutex_unlock (__class_table_lock
);
242 /* Get a class from the table. This does not need mutex protection.
243 Currently, this function is called each time you call a static
244 method, this is why it must be very fast. */
246 class_table_get_safe (const char *class_name
)
251 /* Compute length and hash. */
252 CLASS_TABLE_HASH (length
, hash
, class_name
);
254 node
= class_table_array
[hash
];
260 if (node
->length
== length
)
262 /* Compare the class names. */
265 for (i
= 0; i
< length
; i
++)
267 if ((node
->name
)[i
] != class_name
[i
])
275 /* They are equal! */
276 return node
->pointer
;
280 while ((node
= node
->next
) != NULL
);
286 /* Enumerate over the class table. */
287 struct class_table_enumerator
295 class_table_next (struct class_table_enumerator
**e
)
297 struct class_table_enumerator
*enumerator
= *e
;
300 if (enumerator
== NULL
)
302 *e
= objc_malloc (sizeof (struct class_table_enumerator
));
304 enumerator
->hash
= 0;
305 enumerator
->node
= NULL
;
307 next
= class_table_array
[enumerator
->hash
];
311 next
= enumerator
->node
->next
;
316 enumerator
->node
= next
;
317 return enumerator
->node
->pointer
;
323 while (enumerator
->hash
< CLASS_TABLE_SIZE
)
325 next
= class_table_array
[enumerator
->hash
];
328 enumerator
->node
= next
;
329 return enumerator
->node
->pointer
;
334 /* Ok - table finished - done. */
335 objc_free (enumerator
);
340 #if 0 /* DEBUGGING FUNCTIONS */
341 /* Debugging function - print the class table. */
343 class_table_print (void)
347 for (i
= 0; i
< CLASS_TABLE_SIZE
; i
++)
352 node
= class_table_array
[i
];
356 printf ("\t%s\n", node
->name
);
362 /* Debugging function - print an histogram of number of classes in
363 function of hash key values. Useful to evaluate the hash function
366 class_table_print_histogram (void)
371 for (i
= 0; i
< CLASS_TABLE_SIZE
; i
++)
375 node
= class_table_array
[i
];
382 if (((i
+ 1) % 50) == 0)
384 printf ("%4d:", i
+ 1);
385 for (j
= 0; j
< counter
; j
++)
393 printf ("%4d:", i
+ 1);
394 for (j
= 0; j
< counter
; j
++)
400 #endif /* DEBUGGING FUNCTIONS */
403 ** Objective-C runtime functions
406 /* From now on, the only access to the class table data structure
407 should be via the class_table_* functions. */
409 /* This is a hook which is called by objc_get_class and
410 objc_lookup_class if the runtime is not able to find the class.
411 This may e.g. try to load in the class using dynamic loading. */
412 Class (*_objc_lookup_class
) (const char *name
) = 0; /* !T:SAFE */
415 /* True when class links has been resolved. */
416 BOOL __objc_class_links_resolved
= NO
; /* !T:UNUSED */
420 __objc_init_class_tables (void)
422 /* Allocate the class hash table. */
424 if (__class_table_lock
)
427 objc_mutex_lock (__objc_runtime_mutex
);
429 class_table_setup ();
431 objc_mutex_unlock (__objc_runtime_mutex
);
434 /* This function adds a class to the class hash table, and assigns the
435 class a number, unless it's already known. */
437 __objc_add_class_to_hash (Class
class)
441 objc_mutex_lock (__objc_runtime_mutex
);
443 /* Make sure the table is there. */
444 assert (__class_table_lock
);
446 /* Make sure it's not a meta class. */
447 assert (CLS_ISCLASS (class));
449 /* Check to see if the class is already in the hash table. */
450 h_class
= class_table_get_safe (class->name
);
453 /* The class isn't in the hash table. Add the class and assign a class
455 static unsigned int class_number
= 1;
457 CLS_SETNUMBER (class, class_number
);
458 CLS_SETNUMBER (class->class_pointer
, class_number
);
461 class_table_insert (class->name
, class);
464 objc_mutex_unlock (__objc_runtime_mutex
);
467 /* Get the class object for the class named NAME. If NAME does not
468 identify a known class, the hook _objc_lookup_class is called. If
469 this fails, nil is returned. */
471 objc_lookup_class (const char *name
)
475 class = class_table_get_safe (name
);
480 if (_objc_lookup_class
)
481 return (*_objc_lookup_class
) (name
);
486 /* Get the class object for the class named NAME. If NAME does not
487 identify a known class, the hook _objc_lookup_class is called. If
488 this fails, an error message is issued and the system aborts. */
490 objc_get_class (const char *name
)
494 class = class_table_get_safe (name
);
499 if (_objc_lookup_class
)
500 class = (*_objc_lookup_class
) (name
);
505 objc_error (nil
, OBJC_ERR_BAD_CLASS
,
506 "objc runtime: cannot find class %s\n", name
);
511 objc_get_meta_class (const char *name
)
513 return objc_get_class (name
)->class_pointer
;
516 /* This function provides a way to enumerate all the classes in the
517 executable. Pass *ENUM_STATE == NULL to start the enumeration. The
518 function will return 0 when there are no more classes.
522 while ((class = objc_next_class (&es)))
523 ... do something with class;
526 objc_next_class (void **enum_state
)
530 objc_mutex_lock (__objc_runtime_mutex
);
532 /* Make sure the table is there. */
533 assert (__class_table_lock
);
535 class = class_table_next ((struct class_table_enumerator
**) enum_state
);
537 objc_mutex_unlock (__objc_runtime_mutex
);
542 /* Resolve super/subclass links for all classes. The only thing we
543 can be sure of is that the class_pointer for class objects point to
544 the right meta class objects. */
546 __objc_resolve_class_links (void)
548 struct class_table_enumerator
*es
= NULL
;
549 Class object_class
= objc_get_class ("Object");
552 assert (object_class
);
554 objc_mutex_lock (__objc_runtime_mutex
);
556 /* Assign subclass links. */
557 while ((class1
= class_table_next (&es
)))
559 /* Make sure we have what we think we have. */
560 assert (CLS_ISCLASS (class1
));
561 assert (CLS_ISMETA (class1
->class_pointer
));
563 /* The class_pointer of all meta classes point to Object's meta
565 class1
->class_pointer
->class_pointer
= object_class
->class_pointer
;
567 if (! CLS_ISRESOLV (class1
))
569 CLS_SETRESOLV (class1
);
570 CLS_SETRESOLV (class1
->class_pointer
);
572 if (class1
->super_class
)
575 = objc_get_class ((char *) class1
->super_class
);
577 assert (a_super_class
);
579 DEBUG_PRINTF ("making class connections for: %s\n",
582 /* Assign subclass links for superclass. */
583 class1
->sibling_class
= a_super_class
->subclass_list
;
584 a_super_class
->subclass_list
= class1
;
586 /* Assign subclass links for meta class of superclass. */
587 if (a_super_class
->class_pointer
)
589 class1
->class_pointer
->sibling_class
590 = a_super_class
->class_pointer
->subclass_list
;
591 a_super_class
->class_pointer
->subclass_list
592 = class1
->class_pointer
;
595 else /* A root class, make its meta object be a subclass of
598 class1
->class_pointer
->sibling_class
599 = object_class
->subclass_list
;
600 object_class
->subclass_list
= class1
->class_pointer
;
605 /* Assign superclass links. */
607 while ((class1
= class_table_next (&es
)))
610 for (sub_class
= class1
->subclass_list
; sub_class
;
611 sub_class
= sub_class
->sibling_class
)
613 sub_class
->super_class
= class1
;
614 if (CLS_ISCLASS (sub_class
))
615 sub_class
->class_pointer
->super_class
= class1
->class_pointer
;
619 objc_mutex_unlock (__objc_runtime_mutex
);
624 #define CLASSOF(c) ((c)->class_pointer)
627 class_pose_as (Class impostor
, Class super_class
)
629 if (! CLS_ISRESOLV (impostor
))
630 __objc_resolve_class_links ();
634 assert (super_class
);
635 assert (impostor
->super_class
== super_class
);
636 assert (CLS_ISCLASS (impostor
));
637 assert (CLS_ISCLASS (super_class
));
638 assert (impostor
->instance_size
== super_class
->instance_size
);
641 Class
*subclass
= &(super_class
->subclass_list
);
643 /* Move subclasses of super_class to impostor. */
646 Class nextSub
= (*subclass
)->sibling_class
;
648 if (*subclass
!= impostor
)
650 Class sub
= *subclass
;
653 sub
->sibling_class
= impostor
->subclass_list
;
654 sub
->super_class
= impostor
;
655 impostor
->subclass_list
= sub
;
657 /* It will happen that SUB is not a class object if it is
658 the top of the meta class hierarchy chain (root
659 meta-class objects inherit their class object). If
660 that is the case... don't mess with the meta-meta
662 if (CLS_ISCLASS (sub
))
665 CLASSOF (sub
)->sibling_class
=
666 CLASSOF (impostor
)->subclass_list
;
667 CLASSOF (sub
)->super_class
= CLASSOF (impostor
);
668 CLASSOF (impostor
)->subclass_list
= CLASSOF (sub
);
675 /* Set subclasses of superclass to be impostor only. */
676 super_class
->subclass_list
= impostor
;
677 CLASSOF (super_class
)->subclass_list
= CLASSOF (impostor
);
679 /* Set impostor to have no sibling classes. */
680 impostor
->sibling_class
= 0;
681 CLASSOF (impostor
)->sibling_class
= 0;
684 /* Check relationship of impostor and super_class is kept. */
685 assert (impostor
->super_class
== super_class
);
686 assert (CLASSOF (impostor
)->super_class
== CLASSOF (super_class
));
688 /* This is how to update the lookup table. Regardless of what the
689 keys of the hashtable is, change all values that are superclass
692 objc_mutex_lock (__objc_runtime_mutex
);
694 class_table_replace (super_class
, impostor
);
696 objc_mutex_unlock (__objc_runtime_mutex
);
698 /* Next, we update the dispatch tables... */
699 __objc_update_dispatch_table_for_class (CLASSOF (impostor
));
700 __objc_update_dispatch_table_for_class (impostor
);