OSDN Git Service

37b2b4eebf9b6de94356d65aecf013f8425f54d3
[pf3gnuchains/gcc-fork.git] / libobjc / class.c
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-private/common.h"
91 #include "objc/objc.h"
92 #include "objc/objc-api.h"
93 #include "objc/thr.h"
94 #include "objc-private/runtime.h"            /* the kitchen sink */
95
96 /* We use a table which maps a class name to the corresponding class
97  * pointer.  The first part of this file defines this table, and
98  * functions to do basic operations on the table.  The second part of
99  * the file implements some higher level Objective-C functionality for
100  * classes by using the functions provided in the first part to manage
101  * the table. */
102
103 /**
104  ** Class Table Internals
105  **/
106
107 /* A node holding a class */
108 typedef struct class_node
109 {
110   struct class_node *next;      /* Pointer to next entry on the list.
111                                    NULL indicates end of list. */
112   
113   const char *name;             /* The class name string */
114   int length;                   /* The class name string length */
115   Class pointer;                /* The Class pointer */
116   
117 } *class_node_ptr;
118
119 /* A table containing classes is a class_node_ptr (pointing to the
120    first entry in the table - if it is NULL, then the table is
121    empty). */
122
123 /* We have 1024 tables.  Each table contains all class names which
124    have the same hash (which is a number between 0 and 1023).  To look
125    up a class_name, we compute its hash, and get the corresponding
126    table.  Once we have the table, we simply compare strings directly
127    till we find the one which we want (using the length first).  The
128    number of tables is quite big on purpose (a normal big application
129    has less than 1000 classes), so that you shouldn't normally get any
130    collisions, and get away with a single comparison (which we can't
131    avoid since we need to know that you have got the right thing).  */
132 #define CLASS_TABLE_SIZE 1024
133 #define CLASS_TABLE_MASK 1023
134
135 static class_node_ptr class_table_array[CLASS_TABLE_SIZE];
136
137 /* The table writing mutex - we lock on writing to avoid conflicts
138    between different writers, but we read without locks.  That is
139    possible because we assume pointer assignment to be an atomic
140    operation.  */
141 static objc_mutex_t __class_table_lock = NULL;
142
143 /* CLASS_TABLE_HASH is how we compute the hash of a class name.  It is
144    a macro - *not* a function - arguments *are* modified directly.  
145
146    INDEX should be a variable holding an int;
147    HASH should be a variable holding an int;
148    CLASS_NAME should be a variable holding a (char *) to the class_name.  
149
150    After the macro is executed, INDEX contains the length of the
151    string, and HASH the computed hash of the string; CLASS_NAME is
152    untouched.  */
153
154 #define CLASS_TABLE_HASH(INDEX, HASH, CLASS_NAME)          \
155   HASH = 0;                                                  \
156   for (INDEX = 0; CLASS_NAME[INDEX] != '\0'; INDEX++)        \
157     {                                                        \
158       HASH = (HASH << 4) ^ (HASH >> 28) ^ CLASS_NAME[INDEX]; \
159     }                                                        \
160                                                              \
161   HASH = (HASH ^ (HASH >> 10) ^ (HASH >> 20)) & CLASS_TABLE_MASK;
162
163 /* Setup the table.  */
164 static void
165 class_table_setup (void)
166 {
167   /* Start - nothing in the table.  */
168   memset (class_table_array, 0, sizeof (class_node_ptr) * CLASS_TABLE_SIZE);
169
170   /* The table writing mutex.  */
171   __class_table_lock = objc_mutex_allocate ();
172 }
173
174
175 /* Insert a class in the table (used when a new class is registered).  */
176 static void 
177 class_table_insert (const char *class_name, Class class_pointer)
178 {
179   int hash, length;
180   class_node_ptr new_node;
181
182   /* Find out the class name's hash and length.  */
183   CLASS_TABLE_HASH (length, hash, class_name);
184   
185   /* Prepare the new node holding the class.  */
186   new_node = objc_malloc (sizeof (struct class_node));
187   new_node->name = class_name;
188   new_node->length = length;
189   new_node->pointer = class_pointer;
190
191   /* Lock the table for modifications.  */
192   objc_mutex_lock (__class_table_lock);
193   
194   /* Insert the new node in the table at the beginning of the table at
195      class_table_array[hash].  */
196   new_node->next = class_table_array[hash];
197   class_table_array[hash] = new_node;
198   
199   objc_mutex_unlock (__class_table_lock);
200 }
201
202 /* Replace a class in the table (used only by poseAs:).  */
203 static void 
204 class_table_replace (Class old_class_pointer, Class new_class_pointer)
205 {
206   int hash;
207   class_node_ptr node;
208
209   objc_mutex_lock (__class_table_lock);
210   
211   hash = 0;
212   node = class_table_array[hash];
213   
214   while (hash < CLASS_TABLE_SIZE)
215     {
216       if (node == NULL)
217         {
218           hash++;
219           if (hash < CLASS_TABLE_SIZE)
220             {
221               node = class_table_array[hash];
222             }
223         }
224       else
225         {
226           Class class1 = node->pointer;
227
228           if (class1 == old_class_pointer)
229             {
230               node->pointer = new_class_pointer;
231             }
232           node = node->next;
233         }
234     }
235
236   objc_mutex_unlock (__class_table_lock);
237 }
238
239
240 /* Get a class from the table.  This does not need mutex protection.
241    Currently, this function is called each time you call a static
242    method, this is why it must be very fast.  */
243 static inline Class 
244 class_table_get_safe (const char *class_name)
245 {
246   class_node_ptr node;  
247   int length, hash;
248
249   /* Compute length and hash.  */
250   CLASS_TABLE_HASH (length, hash, class_name);
251   
252   node = class_table_array[hash];
253   
254   if (node != NULL)
255     {
256       do
257         {
258           if (node->length == length)
259             {
260               /* Compare the class names.  */
261               int i;
262
263               for (i = 0; i < length; i++)
264                 {
265                   if ((node->name)[i] != class_name[i]) 
266                     {
267                       break;
268                     }
269                 }
270               
271               if (i == length)
272                 {
273                   /* They are equal!  */
274                   return node->pointer;
275                 }
276             }
277         }
278       while ((node = node->next) != NULL);
279     }
280
281   return Nil;
282 }
283
284 /* Enumerate over the class table.  */
285 struct class_table_enumerator
286 {
287   int hash;
288   class_node_ptr node;
289 };
290
291
292 static Class
293 class_table_next (struct class_table_enumerator **e)
294 {
295   struct class_table_enumerator *enumerator = *e;
296   class_node_ptr next;
297   
298   if (enumerator == NULL)
299     {
300        *e = objc_malloc (sizeof (struct class_table_enumerator));
301       enumerator = *e;
302       enumerator->hash = 0;
303       enumerator->node = NULL;
304
305       next = class_table_array[enumerator->hash];
306     }
307   else
308     {
309       next = enumerator->node->next;
310     }
311   
312   if (next != NULL)
313     {
314       enumerator->node = next;
315       return enumerator->node->pointer;
316     }
317   else 
318     {
319       enumerator->hash++;
320      
321       while (enumerator->hash < CLASS_TABLE_SIZE)
322         {
323           next = class_table_array[enumerator->hash];
324           if (next != NULL)
325             {
326               enumerator->node = next;
327               return enumerator->node->pointer;
328             }
329           enumerator->hash++;
330         }
331       
332       /* Ok - table finished - done.  */
333       objc_free (enumerator);
334       return Nil;
335     }
336 }
337
338 #if 0 /* DEBUGGING FUNCTIONS */
339 /* Debugging function - print the class table.  */
340 void
341 class_table_print (void)
342 {
343   int i;
344   
345   for (i = 0; i < CLASS_TABLE_SIZE; i++)
346     {
347       class_node_ptr node;
348       
349       printf ("%d:\n", i);
350       node = class_table_array[i];
351       
352       while (node != NULL)
353         {
354           printf ("\t%s\n", node->name);
355           node = node->next;
356         }
357     }
358 }
359
360 /* Debugging function - print an histogram of number of classes in
361    function of hash key values.  Useful to evaluate the hash function
362    in real cases.  */
363 void
364 class_table_print_histogram (void)
365 {
366   int i, j;
367   int counter = 0;
368   
369   for (i = 0; i < CLASS_TABLE_SIZE; i++)
370     {
371       class_node_ptr node;
372       
373       node = class_table_array[i];
374       
375       while (node != NULL)
376         {
377           counter++;
378           node = node->next;
379         }
380       if (((i + 1) % 50) == 0)
381         {
382           printf ("%4d:", i + 1);
383           for (j = 0; j < counter; j++)
384             {
385               printf ("X");
386             }
387           printf ("\n");
388           counter = 0;
389         }
390     }
391   printf ("%4d:", i + 1);
392   for (j = 0; j < counter; j++)
393     {
394       printf ("X");
395     }
396   printf ("\n");
397 }
398 #endif /* DEBUGGING FUNCTIONS */
399
400 /**
401  ** Objective-C runtime functions
402  **/
403
404 /* From now on, the only access to the class table data structure
405    should be via the class_table_* functions.  */
406
407 /* This is a hook which is called by objc_get_class and
408    objc_lookup_class if the runtime is not able to find the class.  
409    This may e.g. try to load in the class using dynamic loading.  */
410 Class (*_objc_lookup_class) (const char *name) = 0;      /* !T:SAFE */
411
412
413 /* True when class links has been resolved.  */     
414 BOOL __objc_class_links_resolved = NO;                  /* !T:UNUSED */
415
416
417 void
418 __objc_init_class_tables (void)
419 {
420   /* Allocate the class hash table.  */
421   
422   if (__class_table_lock)
423     return;
424   
425   objc_mutex_lock (__objc_runtime_mutex);
426   
427   class_table_setup ();
428
429   objc_mutex_unlock (__objc_runtime_mutex);
430 }  
431
432 /* This function adds a class to the class hash table, and assigns the
433    class a number, unless it's already known.  */
434 void
435 __objc_add_class_to_hash (Class class)
436 {
437   Class h_class;
438
439   objc_mutex_lock (__objc_runtime_mutex);
440
441   /* Make sure the table is there.  */
442   assert (__class_table_lock);
443
444   /* Make sure it's not a meta class.  */
445   assert (CLS_ISCLASS (class));
446
447   /* Check to see if the class is already in the hash table.  */
448   h_class = class_table_get_safe (class->name);
449   if (! h_class)
450     {
451       /* The class isn't in the hash table.  Add the class and assign a class
452          number.  */
453       static unsigned int class_number = 1;
454
455       CLS_SETNUMBER (class, class_number);
456       CLS_SETNUMBER (class->class_pointer, class_number);
457
458       ++class_number;
459       class_table_insert (class->name, class);
460     }
461
462   objc_mutex_unlock (__objc_runtime_mutex);
463 }
464
465 /* Get the class object for the class named NAME.  If NAME does not
466    identify a known class, the hook _objc_lookup_class is called.  If
467    this fails, nil is returned.  */
468 Class
469 objc_lookup_class (const char *name)
470 {
471   Class class;
472
473   class = class_table_get_safe (name);
474
475   if (class)
476     return class;
477
478   if (_objc_lookup_class)
479     return (*_objc_lookup_class) (name);
480   else
481     return 0;
482 }
483
484 /* Get the class object for the class named NAME.  If NAME does not
485    identify a known class, the hook _objc_lookup_class is called.  If
486    this fails, an error message is issued and the system aborts.  */
487 Class
488 objc_get_class (const char *name)
489 {
490   Class class;
491
492   class = class_table_get_safe (name);
493
494   if (class)
495     return class;
496
497   if (_objc_lookup_class)
498     class = (*_objc_lookup_class) (name);
499
500   if (class)
501     return class;
502   
503   objc_error (nil, OBJC_ERR_BAD_CLASS, 
504               "objc runtime: cannot find class %s\n", name);
505   return 0;
506 }
507
508 MetaClass
509 objc_get_meta_class (const char *name)
510 {
511   return objc_get_class (name)->class_pointer;
512 }
513
514 /* This function provides a way to enumerate all the classes in the
515    executable.  Pass *ENUM_STATE == NULL to start the enumeration.  The
516    function will return 0 when there are no more classes.  
517    For example: 
518        id class; 
519        void *es = NULL;
520        while ((class = objc_next_class (&es)))
521          ... do something with class; 
522 */
523 Class
524 objc_next_class (void **enum_state)
525 {
526   Class class;
527
528   objc_mutex_lock (__objc_runtime_mutex);
529   
530   /* Make sure the table is there.  */
531   assert (__class_table_lock);
532
533   class = class_table_next ((struct class_table_enumerator **) enum_state);
534
535   objc_mutex_unlock (__objc_runtime_mutex);
536   
537   return class;
538 }
539
540 /* Resolve super/subclass links for all classes.  The only thing we
541    can be sure of is that the class_pointer for class objects point to
542    the right meta class objects.  */
543 void
544 __objc_resolve_class_links (void)
545 {
546   struct class_table_enumerator *es = NULL;
547   Class object_class = objc_get_class ("Object");
548   Class class1;
549
550   assert (object_class);
551
552   objc_mutex_lock (__objc_runtime_mutex);
553
554   /* Assign subclass links.  */
555   while ((class1 = class_table_next (&es)))
556     {
557       /* Make sure we have what we think we have.  */
558       assert (CLS_ISCLASS (class1));
559       assert (CLS_ISMETA (class1->class_pointer));
560
561       /* The class_pointer of all meta classes point to Object's meta
562          class.  */
563       class1->class_pointer->class_pointer = object_class->class_pointer;
564
565       if (! CLS_ISRESOLV (class1))
566         {
567           CLS_SETRESOLV (class1);
568           CLS_SETRESOLV (class1->class_pointer);
569               
570           if (class1->super_class)
571             {   
572               Class a_super_class 
573                 = objc_get_class ((char *) class1->super_class);
574               
575               assert (a_super_class);
576               
577               DEBUG_PRINTF ("making class connections for: %s\n",
578                             class1->name);
579               
580               /* Assign subclass links for superclass.  */
581               class1->sibling_class = a_super_class->subclass_list;
582               a_super_class->subclass_list = class1;
583               
584               /* Assign subclass links for meta class of superclass.  */
585               if (a_super_class->class_pointer)
586                 {
587                   class1->class_pointer->sibling_class
588                     = a_super_class->class_pointer->subclass_list;
589                   a_super_class->class_pointer->subclass_list 
590                     = class1->class_pointer;
591                 }
592             }
593           else /* A root class, make its meta object be a subclass of
594                   Object.  */
595             {
596               class1->class_pointer->sibling_class 
597                 = object_class->subclass_list;
598               object_class->subclass_list = class1->class_pointer;
599             }
600         }
601     }
602
603   /* Assign superclass links.  */
604    es = NULL;
605    while ((class1 = class_table_next (&es)))
606     {
607       Class sub_class;
608       for (sub_class = class1->subclass_list; sub_class;
609            sub_class = sub_class->sibling_class)
610         {
611           sub_class->super_class = class1;
612           if (CLS_ISCLASS (sub_class))
613             sub_class->class_pointer->super_class = class1->class_pointer;
614         }
615     }
616
617   objc_mutex_unlock (__objc_runtime_mutex);
618 }
619
620
621
622 #define CLASSOF(c) ((c)->class_pointer)
623
624 Class
625 class_pose_as (Class impostor, Class super_class)
626 {
627   if (! CLS_ISRESOLV (impostor))
628     __objc_resolve_class_links ();
629
630   /* Preconditions */
631   assert (impostor);
632   assert (super_class);
633   assert (impostor->super_class == super_class);
634   assert (CLS_ISCLASS (impostor));
635   assert (CLS_ISCLASS (super_class));
636   assert (impostor->instance_size == super_class->instance_size);
637
638   {
639     Class *subclass = &(super_class->subclass_list);
640
641     /* Move subclasses of super_class to impostor.  */
642     while (*subclass)
643       {
644         Class nextSub = (*subclass)->sibling_class;
645
646         if (*subclass != impostor)
647           {
648             Class sub = *subclass;
649
650             /* Classes */
651             sub->sibling_class = impostor->subclass_list;
652             sub->super_class = impostor;
653             impostor->subclass_list = sub;
654
655             /* It will happen that SUB is not a class object if it is
656                the top of the meta class hierarchy chain (root
657                meta-class objects inherit their class object).  If
658                that is the case... don't mess with the meta-meta
659                class.  */
660             if (CLS_ISCLASS (sub))
661               {
662                 /* Meta classes */
663                 CLASSOF (sub)->sibling_class = 
664                   CLASSOF (impostor)->subclass_list;
665                 CLASSOF (sub)->super_class = CLASSOF (impostor);
666                 CLASSOF (impostor)->subclass_list = CLASSOF (sub);
667               }
668           }
669
670         *subclass = nextSub;
671       }
672
673     /* Set subclasses of superclass to be impostor only.  */
674     super_class->subclass_list = impostor;
675     CLASSOF (super_class)->subclass_list = CLASSOF (impostor);
676     
677     /* Set impostor to have no sibling classes.  */
678     impostor->sibling_class = 0;
679     CLASSOF (impostor)->sibling_class = 0;
680   }
681   
682   /* Check relationship of impostor and super_class is kept.  */
683   assert (impostor->super_class == super_class);
684   assert (CLASSOF (impostor)->super_class == CLASSOF (super_class));
685
686   /* This is how to update the lookup table.  Regardless of what the
687      keys of the hashtable is, change all values that are superclass
688      into impostor.  */
689
690   objc_mutex_lock (__objc_runtime_mutex);
691
692   class_table_replace (super_class, impostor);
693
694   objc_mutex_unlock (__objc_runtime_mutex);
695
696   /* Next, we update the dispatch tables...  */
697   __objc_update_dispatch_table_for_class (CLASSOF (impostor));
698   __objc_update_dispatch_table_for_class (impostor);
699
700   return impostor;
701 }