OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libobjc/] [objc-sync.c] - Blame information for rev 739

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 739 jeremybenn
/* 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
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.