OSDN Git Service

PR ada/60703
[pf3gnuchains/gcc-fork.git] / libobjc / objc-sync.c
1 /* GNU Objective C Runtime @synchronized implementation
2    Copyright (C) 2010 Free Software Foundation, Inc.
3    Contributed by Nicola Pero <nicola.pero@meta-innovation.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under the
8 terms of the GNU General Public License as published by the Free Software
9 Foundation; either version 3, or (at your option) any later version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
14 details.
15
16 Under Section 7 of GPL version 3, you are granted additional
17 permissions described in the GCC Runtime Library Exception, version
18 3.1, as published by the Free Software Foundation.
19
20 You should have received a copy of the GNU General Public License and
21 a copy of the GCC Runtime Library Exception along with this program;
22 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 <http://www.gnu.org/licenses/>.  */
24
25 /* This file implements objc_sync_enter() and objc_sync_exit(), the
26    two functions required to support @synchronized().
27
28    objc_sync_enter(object) needs to get a recursive lock associated
29    with 'object', and lock it.
30    
31    objc_sync_exit(object) needs to get the recursive lock associated
32    with 'object', and unlock it.  */
33
34 /* To avoid the overhead of continuously allocating and deallocating
35    locks, we implement a pool of locks.  When a lock is needed for an
36    object, we get a lock from the pool and associate it with the
37    object.
38  
39    The lock pool need to be protected by its own lock (the
40    "protection" lock), which has to be locked then unlocked each time
41    objc_sync_enter() and objc_sync_exit() are called.  To reduce the
42    contention on the protection lock, instead of a single pool with a
43    single (global) protection lock we use a number of smaller pools,
44    each with its own pool protection lock.  To decide which lock pool
45    to use for each object, we compute a hash from the object pointer.
46  
47    The implementation of each lock pool uses a linked list of all the
48    locks in the pool (both unlocked, and locked); this works in the
49    assumption that the number of locks concurrently required is very
50    low.  In practice, it seems that you rarely see more than a few
51    locks ever concurrently required.
52  
53    A standard case is a thread acquiring a lock recursively, over and
54    over again: for example when most methods of a class are protected
55    by @synchronized(self) but they also call each other.  We use
56    thread-local storage to implement a cache and optimize this case.
57    The cache stores locks that the thread successfully acquired,
58    allowing objc_sync_enter() and objc_sync_exit() to locate a lock
59    which is already held by the current thread without having to use
60    any protection lock or synchronization mechanism.  It can so detect
61    recursive locks/unlocks, and transform them into no-ops that
62    require no actual locking or synchronization mechanisms at all.  */
63
64 /* You can disable the thread-local cache (most likely to benchmark
65    the code with and without it) by compiling with
66    -DSYNC_CACHE_DISABLE, or commenting out the following line.  */
67 /* #define SYNC_CACHE_DISABLE */
68
69 /* If thread-local storage is not available, automatically disable the
70    cache.  */
71 #ifndef HAVE_TLS
72 # define SYNC_CACHE_DISABLE
73 #endif
74
75 #include "objc-private/common.h"
76 #include "objc/objc-sync.h"         /* For objc_sync_enter(), objc_sync_exit() */
77 #include "objc/runtime.h"           /* For objc_malloc() */
78 #include "objc/thr.h"               /* For objc_mutex_loc() and similar */
79 #include "objc-private/objc-sync.h" /* For __objc_sync_init() */
80
81 /* We have 32 pools of locks, each of them protected by its own
82    protection lock.  It's tempting to increase this number to reduce
83    contention; but in our tests it is high enough.  */
84 #define SYNC_NUMBER_OF_POOLS 32
85
86 /* Given an object, it determines which pool contains the associated
87    lock.  */
88 #define SYNC_OBJECT_HASH(OBJECT) ((((size_t)OBJECT >> 8) ^ (size_t)OBJECT) & (SYNC_NUMBER_OF_POOLS - 1))
89
90 /* The locks protecting each pool.  */
91 static objc_mutex_t sync_pool_protection_locks[SYNC_NUMBER_OF_POOLS];
92
93 /* The data structure (linked list) holding the locks.  */
94 typedef struct lock_node
95 {
96   /* Pointer to next entry on the list.  NULL indicates end of list.
97      You need to hold the appropriate sync_pool_protection_locks[N] to
98      read or write this variable.  */
99   struct lock_node *next;
100
101   /* The (recursive) lock.  Allocated when the node is created, and
102      always not-NULL, and unchangeable, after that.  */
103   objc_mutex_t lock;
104
105   /* This is how many times the objc_mutex_lock() has been called on
106      the lock (it is 0 when the lock is unused).  Used to track when
107      the lock is no longer associated with an object and can be reused
108      for another object.  It records "real" locks, potentially (but
109      not necessarily) by multiple threads.  You need to hold the
110      appropriate sync_pool_protection_locks[N] to read or write this
111      variable.  */
112   unsigned int usage_count;
113
114   /* The object that the lock is associated with.  This variable can
115      only be written when holding the sync_pool_protection_locks[N]
116      and when node->usage_count == 0, ie, the lock is not being used.
117      You can read this variable either when you hold the
118      sync_pool_protection_locks[N] or when you hold node->lock,
119      because in that case you know that node->usage_count can't get to
120      zero until you release the lock.  It is valid to have usage_count
121      == 0 and object != nil; in that case, the lock is not currently
122      being used, but is still currently associated with the
123      object.  */
124   id object;
125
126   /* This is a counter reserved for use by the thread currently
127      holding the lock.  So, you need to hold node->lock to read or
128      write this variable.  It is normally 0, and if the cache is not
129      being used, it is kept at 0 (even if recursive locks are being
130      done; in that case, no difference is made between recursive and
131      non-recursive locks: they all increase usage_count, and call
132      objc_mutex_lock()).  When the cache is being used, a thread may
133      be able to find a lock that it already holds using the cache; in
134      that case, to perform additional locks/unlocks it can
135      increase/decrease the recursive_usage_count (which does not
136      require any synchronization with other threads, since it's
137      protected by the node->lock itself) instead of the usage_count
138      (which requires locking the pool protection lock).  And it can
139      skip the call to objc_mutex_lock/unlock too.  */
140   unsigned int recursive_usage_count;
141 } *lock_node_ptr;
142
143
144 /* The pools of locks.  Each of them is a linked list of lock_nodes.
145    In the list we keep both unlocked and locked nodes.  */
146 static lock_node_ptr sync_pool_array[SYNC_NUMBER_OF_POOLS];
147
148 #ifndef SYNC_CACHE_DISABLE
149 /* We store a cache of locks acquired by each thread in thread-local
150    storage.  */
151 static __thread lock_node_ptr *lock_cache = NULL;
152
153 /* This is a conservative implementation that uses a static array of
154    fixed size as cache.  Because the cache is an array that we scan
155    linearly, the bigger it is, the slower it gets.  This does not
156    matter much at small sizes (eg, the overhead of checking 8 cache
157    slots instead of 4 is very small compared to the other overheads
158    involved such as function calls and lock/unlock operations), but at
159    large sizes it becomes important as obviously there is a size over
160    which using the cache backfires: the lookup is so slow that the
161    cache slows down the software instead of speeding it up.  In
162    practice, it seems that most threads use a small number of
163    concurrent locks, so we have a conservative implementation with a
164    fixed-size cache of 8 locks which gives a very predictable
165    behaviour.  If a thread locks lots of different locks, only the
166    first 8 get the speed benefits of the cache, but the cache remains
167    always small, fast and predictable.
168  
169    SYNC_CACHE_SIZE is the size of the lock cache for each thread.  */
170 #define SYNC_CACHE_SIZE 8
171 #endif /* SYNC_CACHE_DISABLE */
172
173 /* Called at startup by init.c.  */
174 void
175 __objc_sync_init (void)
176 {
177   int i;
178
179   for (i = 0; i < SYNC_NUMBER_OF_POOLS; i++)
180     {
181       lock_node_ptr new_node;
182       
183       /* Create a protection lock for each pool.  */
184       sync_pool_protection_locks[i] = objc_mutex_allocate ();
185
186       /* Preallocate a lock per pool.  */
187       new_node = objc_malloc (sizeof (struct lock_node));
188       new_node->lock = objc_mutex_allocate ();
189       new_node->object = nil;
190       new_node->usage_count = 0;
191       new_node->recursive_usage_count = 0;
192       new_node->next = NULL;
193
194       sync_pool_array[i] = new_node;
195     }
196 }  
197
198 int
199 objc_sync_enter (id object)
200 {
201 #ifndef SYNC_CACHE_DISABLE
202   int free_cache_slot;
203 #endif
204   int hash;
205   lock_node_ptr node;
206   lock_node_ptr unused_node;
207
208   if (object == nil)
209     return OBJC_SYNC_SUCCESS;
210
211 #ifndef SYNC_CACHE_DISABLE
212   if (lock_cache == NULL)
213     {
214       /* Note that this calloc only happen only once per thread, the
215          very first time a thread does a objc_sync_enter().  */
216       lock_cache = objc_calloc (SYNC_CACHE_SIZE, sizeof (lock_node_ptr));
217     }
218
219   /* Check the cache to see if we have a record of having already
220      locked the lock corresponding to this object.  While doing so,
221      keep track of the first free cache node in case we need it
222      later.  */ 
223   node = NULL;
224   free_cache_slot = -1;
225
226   {
227     int i;
228     for (i = 0; i < SYNC_CACHE_SIZE; i++)
229       {
230         lock_node_ptr locked_node = lock_cache[i];
231         
232         if (locked_node == NULL)
233           {
234             if (free_cache_slot == -1)
235               free_cache_slot = i;
236           }
237         else if (locked_node->object == object)
238           {
239             node = locked_node;
240             break;
241           }
242       }
243   }
244
245   if (node != NULL)
246     {
247       /* We found the lock.  Increase recursive_usage_count, which is
248          protected by node->lock, which we already hold.  */
249       node->recursive_usage_count++;
250       
251       /* There is no need to actually lock anything, since we already
252          hold the lock.  Correspondingly, objc_sync_exit() will just
253          decrease recursive_usage_count and do nothing to unlock.  */
254       return OBJC_SYNC_SUCCESS;
255     }
256 #endif /* SYNC_CACHE_DISABLE */
257
258   /* The following is the standard lookup for the lock in the standard
259      pool lock.  It requires a pool protection lock.  */
260   hash = SYNC_OBJECT_HASH(object);
261
262   /* Search for an existing lock for 'object'.  While searching, make
263      note of any unused lock if we find any.  */
264   unused_node = NULL;
265
266   objc_mutex_lock (sync_pool_protection_locks[hash]);
267
268   node = sync_pool_array[hash];
269
270   while (node != NULL)
271     {
272       if (node->object == object)
273         {
274           /* We found the lock.  */
275           node->usage_count++;
276           objc_mutex_unlock (sync_pool_protection_locks[hash]);
277
278 #ifndef SYNC_CACHE_DISABLE
279           /* Put it in the cache.  */
280           if (free_cache_slot != -1)
281             lock_cache[free_cache_slot] = node;
282 #endif
283
284           /* Lock it.  */
285           objc_mutex_lock (node->lock);
286
287           return OBJC_SYNC_SUCCESS;
288         }
289
290       if (unused_node == NULL  &&  node->usage_count == 0)
291         {
292           /* We found the first unused node.  Record it.  */
293           unused_node = node;
294         }
295       
296       node = node->next;
297     }
298
299   /* An existing lock for 'object' could not be found.  */
300   if (unused_node != NULL)
301     {
302       /* But we found a unused lock; use it.  */
303       unused_node->object = object;
304       unused_node->usage_count = 1;
305       unused_node->recursive_usage_count = 0;
306       objc_mutex_unlock (sync_pool_protection_locks[hash]);
307
308 #ifndef SYNC_CACHE_DISABLE
309       if (free_cache_slot != -1)
310         lock_cache[free_cache_slot] = unused_node;
311 #endif
312
313       objc_mutex_lock (unused_node->lock);
314
315       return OBJC_SYNC_SUCCESS;
316     }
317   else
318     {
319       /* There are no unused nodes; allocate a new node.  */
320       lock_node_ptr new_node;
321
322       /* Create the node.  */
323       new_node = objc_malloc (sizeof (struct lock_node));
324       new_node->lock = objc_mutex_allocate ();
325       new_node->object = object;
326       new_node->usage_count = 1;
327       new_node->recursive_usage_count = 0;
328
329       /* Attach it at the beginning of the pool.  */
330       new_node->next = sync_pool_array[hash];
331       sync_pool_array[hash] = new_node;
332       objc_mutex_unlock (sync_pool_protection_locks[hash]);
333
334 #ifndef SYNC_CACHE_DISABLE
335       if (free_cache_slot != -1)
336         lock_cache[free_cache_slot] = new_node;
337 #endif
338
339       objc_mutex_lock (new_node->lock);
340
341       return OBJC_SYNC_SUCCESS;
342     }
343 }
344
345 int
346 objc_sync_exit (id object)
347 {
348   int hash;
349   lock_node_ptr node;
350
351   if (object == nil)
352     return OBJC_SYNC_SUCCESS;
353   
354 #ifndef SYNC_CACHE_DISABLE
355   if (lock_cache != NULL)
356     {
357       int i;
358     
359       /* Find the lock in the cache.  */
360       node = NULL;
361       for (i = 0; i < SYNC_CACHE_SIZE; i++)
362         {
363           lock_node_ptr locked_node = lock_cache[i];
364           
365           if (locked_node != NULL  &&  locked_node->object == object)
366             {
367               node = locked_node;
368               break;
369             }
370         }
371       /* Note that, if a node was found in the cache, the variable i
372          now holds the index where it was found, which will be used to
373          remove it from the cache.  */
374       if (node != NULL)
375         {
376           if (node->recursive_usage_count > 0)
377             {
378               node->recursive_usage_count--;
379               return OBJC_SYNC_SUCCESS;
380             }
381           else
382             {
383               /* We need to do a real unlock.  */
384               hash = SYNC_OBJECT_HASH(object);
385               
386               /* TODO: If we had atomic increase/decrease operations
387                  with memory barriers, we could avoid the lock
388                  here!  */
389               objc_mutex_lock (sync_pool_protection_locks[hash]);
390               node->usage_count--;
391               /* Normally, we do not reset object to nil here.  We'll
392                  leave the lock associated with that object, at zero
393                  usage count.  This makes it slighly more efficient to
394                  provide a lock for that object if (as likely)
395                  requested again.  If the object is deallocated, we
396                  don't care.  It will never match a new lock that is
397                  requested, and the node will be reused at some point.
398
399                  But, if garbage collection is enabled, leaving a
400                  pointer to the object in memory might prevent the
401                  object from being released.  In that case, we remove
402                  it (TODO: maybe we should avoid using the garbage
403                  collector at all ?  Nothing is ever deallocated in
404                  this file).  */
405 #if OBJC_WITH_GC
406               node->object = nil;
407 #endif
408               objc_mutex_unlock (sync_pool_protection_locks[hash]);
409             
410               /* PS: Between objc_mutex_unlock
411                  (sync_pool_protection_locks[hash]) and
412                  objc_mutex_unlock (node->lock), the pool is unlocked
413                  so other threads may allocate this same lock to
414                  another object (!).  This is not a problem, but it is
415                  curious.  */
416               objc_mutex_unlock (node->lock);
417               
418               /* Remove the node from the cache.  */
419               lock_cache[i] = NULL;
420               
421               return OBJC_SYNC_SUCCESS;
422             }
423         }
424     }
425 #endif    
426
427   /* The cache either wasn't there, or didn't work (eg, we overflowed
428      it at some point and stopped recording new locks in the cache).
429      Proceed with a full search of the lock pool.  */
430   hash = SYNC_OBJECT_HASH(object);
431
432   objc_mutex_lock (sync_pool_protection_locks[hash]);
433
434   /* Search for an existing lock for 'object'.  */
435   node = sync_pool_array[hash];
436
437   while (node != NULL)
438     {
439       if (node->object == object)
440         {
441           /* We found the lock.  */
442           node->usage_count--;
443           objc_mutex_unlock (sync_pool_protection_locks[hash]);
444
445           objc_mutex_unlock (node->lock);
446
447           /* No need to remove the node from the cache, since it
448              wasn't found in the cache when we looked for it!  */
449           return OBJC_SYNC_SUCCESS;
450         }
451       
452       node = node->next;
453     }
454
455   objc_mutex_unlock (sync_pool_protection_locks[hash]);
456
457   /* A lock for 'object' to unlock could not be found (!!).  */
458   return OBJC_SYNC_NOT_OWNING_THREAD_ERROR;
459 }