libgupc/smp/upc_lock.upc

   1 /* Copyright (C) 2010-2013 Free Software Foundation, Inc.
   2    This file is part of the UPC runtime Library.
   3    Written by Gary Funck <gary@intrepid.com>
   4    and Nenad Vukicevic <nenad@intrepid.com>
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 3, or (at your option)
  11 any later version.
  12
  13 GCC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 Under Section 7 of GPL version 3, you are granted additional
  19 permissions described in the GCC Runtime Library Exception, version
  20 3.1, as published by the Free Software Foundation.
  21
  22 You should have received a copy of the GNU General Public License and
  23 a copy of the GCC Runtime Library Exception along with this program;
  24 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 <http://www.gnu.org/licenses/>.  */
  26
  27 #include <upc.h>
  28 #include <stdlib.h>
  29 #include <stddef.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32 #include "config.h"
  33 #include "upc_lock_sup.h"
  34
  35 /* UPC lock implementation.
  36
  37    The UPC lock functions use MCS locks as described in the
  38    Mellor-Crummey and Scott paper: "Algorithms for Scalable Synchronization
  39    on Shared-Memory Multiprocessors", ACM Transaction on Computer Systems,
  40    February 1991.
  41
  42    The following data structures are used in this implementation:
  43
  44    * Lock link block
  45      A data structure in the shared address space used to link threads
  46      waiting on the lock.  Each thread inserts itself on the list with
  47      a link block that but has affinity to the thread itself. It has
  48      three fields: (1) next - link list pointer, (2) signal - notification
  49      of lock ownership transfer, (3) free flag - link block was freed by
  50      some other thread. A link block has affinity to the owner of the block.
  51    * Lock Link block reference
  52      A 64 bits container for pointer to shared that contains only a thread
  53      number and address field.  Link reference allow the lock routines to
  54      efficiently execute atomic operations on shared pointers.
  55    * Lock structure (upc_lock_t)
  56      A lock is a data structure living in the shared memory space.
  57      Contains two lock link references: (1) last - a lock link reference
  58      to the link block of the last thread on the lock waiting list,
  59      (2) owner - link reference to the lock's owner link block. The lock
  60      data structure has affinity of the thread that created the lock.
  61
  62    The lock data structure goes though the following states:
  63
  64    * Lock is free
  65      Last link block reference is NULL.
  66    * Lock is taken
  67      Last link block reference points to the last thread's link block on
  68      the waiting queue.  Owner link reference points to the owner thread's
  69      link block.  Only the owner of the lock is allowed to manipulate the
  70      owner's link reference in the lock data structure.
  71
  72    The following operations are performed on the lock data structure:
  73
  74    * Lock acquire
  75      Thread allocates a link block and write its reference to the 'last'
  76      filed of the lock data structure by performing an atomic SWAP
  77      operation.  If returned value is NULL, thread is the owner of the
  78      lock.  Otherwise a link reference to the last thread on the waiting
  79      queue is returned and thread needs to link itself on the waiting
  80      queue.
  81    * Lock release
  82      Attempt to write a NULL link block reference into the lock's 'last'
  83      field with atomic CSWAP operation.  If successful, lock is released.
  84      Otherwise, the ownership of the lock must be passed to the first
  85      thread on the wait queue.
  86    * Lock allocation/free
  87      Lock is allocated from the shared memory space or from the local
  88      free list.  They are freed by placing the lock data structure on
  89      the local lock free list if the lock has affinity of the thread that
  90      releases it.  Otherwise lock's memory is released.
  91 */
  92
  93 struct upc_lock_link_cache_struct
  94 {
  95   upc_lock_link_t lock_links[GUPCR_MAX_LOCKS];
  96 };
  97 typedef struct upc_lock_link_cache_struct upc_lock_link_cache_t;
  98
  99 /* Array of lock links managed as a per-thread free list.  */
 100 static shared upc_lock_link_cache_t upc_lock_link_cache[THREADS];
 101
 102 /* Per thread lock link free list.  */
 103 static upc_lock_link_t *upc_lock_links;
 104 /* Null link block reference.  Used for CSWAP operations.  */
 105 upc_link_ref null_link = {.atomic = 0 };
 106
 107 /* UPC lock free list.  */
 108 static upc_lock_t *lock_free;
 109
 110 /* Memory allocation support.  */
 111 upc_lock_t *shared __upc_all_lock;
 112 shared upc_lock_t __upc_alloc_lock;
 113
 114 __attribute__ ((__always_inline__))
 115 static inline
 116 void
 117 upc_new_lock_init (upc_lock_t *lock)
 118 {
 119   lock->last.atomic = 0;
 120   lock->owner_link.atomic = 0;
 121 }
 122
 123 /* Lock link block utilities.  */
 124
 125 /* Lock link block is a data structure that links
 126    lock waiting threads.  It is located in the
 127    shared space of the thread waiting for the lock.
 128    They are locally managed with a free list rooted
 129    at 'upc_lock_links'.
 130
 131    NOTE:
 132    The current design for memory allocation uses
 133    UPC locks in alloc/free routines.  Thus, link blocks
 134    cannot be allocate with the UPC memory allocation
 135    routines.  */
 136
 137 /* Initialize lock link block free list.
 138    NOTE: Link with local addresses for faster access.  */
 139 static void
 140 upc_lock_link_init (void)
 141 {
 142   shared [] upc_lock_link_t *slink = upc_lock_link_cache[MYTHREAD].lock_links;
 143   upc_lock_link_t *link = (upc_lock_link_t *) slink;
 144   upc_lock_links = link;
 145   memset (link, '\0', sizeof (upc_lock_link_cache_t));
 146   for (int i = 0; i < (GUPCR_MAX_LOCKS - 1); i++)
 147     {
 148       link[i].link_ref = upc_to_link_ref (slink++);
 149       link[i].link = &link[i + 1];
 150     }
 151   link[GUPCR_MAX_LOCKS - 1].link_ref = upc_to_link_ref (slink++);
 152 }
 153
 154 /* Release lock link block.  */
 155 __attribute__ ((__always_inline__))
 156 static inline
 157 void
 158 upc_lock_link_free (upc_lock_link_t * link)
 159 {
 160   SET_NULL_LOCK_REF (link->next);
 161   link->signal = 0;
 162   link->link = upc_lock_links;
 163   upc_lock_links = link;
 164 }
 165
 166 /* Allocate lock link block.  */
 167 __attribute__ ((__always_inline__))
 168 static inline
 169 upc_lock_link_t *
 170 upc_lock_link_alloc (void)
 171 {
 172   upc_lock_link_t *link = upc_lock_links;
 173   if (!link)
 174     {
 175       /* Try to find a link block that has been freed by
 176          some other thread and thus not returned to the free list.  */
 177       upc_lock_link_t *llink = (upc_lock_link_t *)
 178         upc_lock_link_cache[MYTHREAD].lock_links;
 179       for (int i = 0; i < (GUPCR_MAX_LOCKS - 1); ++i)
 180         {
 181           if (llink->free)
 182             {
 183               llink->free = 0;
 184               upc_lock_link_free (llink);
 185             }
 186           llink++;
 187         }
 188       link = upc_lock_links;
 189       if (!link)
 190         __upc_fatal ("Cannot allocate a UPC lock link. "
 191                 "The number of allocated per thread lock links "
 192                 "exceeds the configuration defined maximum of entries.");
 193     }
 194   upc_lock_links = link->link;
 195   return link;
 196 }
 197
 198 /* Allocate a lock and return a pointer to it.
 199    This is not a collective function.  */
 200 upc_lock_t *
 201 upc_global_lock_alloc (void)
 202 {
 203   upc_lock_t *lock;
 204   if (lock_free)
 205     {
 206       lock = lock_free;
 207       lock_free = lock->free_link;
 208     }
 209   else
 210     {
 211       /* Allocate space for the lock from shared memory with
 212          affinity to the calling thread.  */
 213       lock = upc_alloc (sizeof (upc_lock_t));
 214       if (lock == NULL)
 215         __upc_fatal ("Cannot allocate memory for the lock");
 216     }
 217   upc_new_lock_init (lock);
 218   return lock;
 219 }
 220
 221 /* Free all lock resources.
 222    If lock has affinity to the calling thread it is released on the
 223    local free list.  If 'lock' is a null pointer, no action occurs.
 224    Otherwise, if the argument does not match a pointer earlier
 225    returned by the alloc function, or if the lock has been de-allocated
 226    by a previous call to 'upc_lock_free' the behavior is undefined.  */
 227
 228 void
 229 upc_lock_free (upc_lock_t *lock)
 230 {
 231   upc_link_ref owner;
 232   if (lock == NULL)
 233     return;
 234   /* Release the link block if this thread owns the lock.  */
 235   owner = lock->owner_link;
 236   if (!NULL_LOCK_REF (owner))
 237     {
 238       shared upc_lock_link_t *link = upc_from_link_ref (owner);
 239       if (MYTHREAD == (int) upc_threadof (link))
 240         {
 241           upc_lock_link_free ((upc_lock_link_t *) link);
 242         }
 243       else
 244         link->free = 1;
 245     }
 246   if (MYTHREAD == (int) upc_threadof (lock))
 247     {
 248       /* Release it on the local free list.  */
 249       lock->free_link = lock_free;
 250       lock_free = lock;
 251     }
 252   else
 253     upc_free (lock);
 254 }
 255
 256 /* Collective free all lock resources.  */
 257 void
 258 upc_all_lock_free (upc_lock_t *lock)
 259 {
 260   upc_link_ref owner;
 261   if (lock == NULL)
 262     return;
 263   /* Release the link block if this thread owns the lock.  */
 264   owner = lock->owner_link;
 265   if (!NULL_LOCK_REF (owner))
 266     {
 267       shared upc_lock_link_t *link = upc_from_link_ref (owner);
 268       if (MYTHREAD == (int) upc_threadof (link))
 269         {
 270           upc_lock_link_free ((upc_lock_link_t *) link);
 271         }
 272     }
 273   if (MYTHREAD == (int) upc_threadof (lock))
 274     {
 275       /* Release it on the local free list.  */
 276       lock->free_link = lock_free;
 277       lock_free = lock;
 278     }
 279   upc_barrier;
 280 }
 281
 282 /* Allocate a lock and return a pointer to it.
 283    'upc_all_lock_alloc' is a collective function.  */
 284 upc_lock_t *
 285 upc_all_lock_alloc (void)
 286 {
 287   upc_lock_t *lock;
 288   upc_barrier (-1);
 289   if (MYTHREAD == 0)
 290     {
 291       if (lock_free)
 292         {
 293           lock = lock_free;
 294           lock_free = lock->free_link;
 295         }
 296       else
 297         {
 298           lock = upc_alloc (sizeof (upc_lock_t));
 299           if (lock == NULL)
 300             __upc_fatal ("Cannot allocate memory for the lock");
 301         }
 302       upc_new_lock_init (lock);
 303       __upc_all_lock = lock;
 304     }
 305   upc_barrier (-1);
 306   return __upc_all_lock;
 307 }
 308
 309 /* UPC lock acquire.  */
 310 void
 311 upc_lock (upc_lock_t *lock)
 312 {
 313   upc_lock_link_t *link;
 314   upc_link_ref old_link_ref;
 315   link = upc_lock_link_alloc ();
 316
 317   /* Insert this thread on the waiting list.  */
 318   upc_link_ref_swap (&lock->last, &old_link_ref, link->link_ref);
 319   if (!NULL_LOCK_REF (old_link_ref))
 320     {
 321       /* We have to wait.  "old_link_ref" contains a reference
 322          to the last thread on the wait queue.  */
 323       shared upc_lock_link_t *rmt_link = upc_from_link_ref (old_link_ref);
 324       upc_link_ref_put ((shared upc_link_ref *) &rmt_link->next,
 325                         link->link_ref);
 326       /* Wait for lock ownership notification.  */
 327       __upc_spin_until (link->signal);
 328     }
 329   lock->owner_link = link->link_ref;
 330   upc_fence;
 331 }
 332
 333 /* UPC lock acquire attempt.
 334    Return 1 if lock is acquired, 0 otherwise.  */
 335 int
 336 upc_lock_attempt (upc_lock_t *lock)
 337 {
 338   upc_lock_link_t *link;
 339   int compare_ok;
 340   /* No need go further if lock is unavailable.  */
 341   if (!NULL_LOCK_REF (upc_link_ref_last (&lock->last)))
 342     return 0;
 343   /* Try to allocate the lock.  */
 344   link = upc_lock_link_alloc ();
 345   compare_ok = upc_link_ref_cswap (&lock->last, null_link, link->link_ref);
 346   if (compare_ok)
 347     {
 348       lock->owner_link = link->link_ref;
 349       upc_fence;
 350     }
 351   else
 352     {
 353       upc_lock_link_free (link);
 354     }
 355   return compare_ok;
 356 }
 357
 358 /* UPC lock release.  */
 359 void
 360 upc_unlock (upc_lock_t *lock)
 361 {
 362   upc_lock_link_t *link;
 363   upc_link_ref link_ref = lock->owner_link;
 364   int compare_ok;
 365
 366   if (!lock)
 367     __upc_fatal ("Trying to release a NULL lock");
 368   if (NULL_LOCK_REF (link_ref))
 369     __upc_fatal ("Trying to release a lock that is not locked");
 370   upc_fence;
 371   link = (upc_lock_link_t *) upc_from_link_ref (link_ref);
 372
 373   /* Try to release the lock by trying to write a NULL into lock
 374      block (last).  Use CSWAP with link_ref as expected.  */
 375   compare_ok = upc_link_ref_cswap (&lock->last, link_ref, null_link);
 376   if (!compare_ok)
 377     {
 378       /* Another thread is already waiting for the lock,
 379          pass the ownership.  */
 380       /* Make sure that waiting thread completed insertion on the
 381          waiting list.  */
 382       __upc_spin_until (!NULL_LOCK_REF (upc_link_ref_get (&link->next)));
 383       /* Notify the waiting thread that it now owns the lock.  */
 384       {
 385         shared upc_lock_link_t *rmt_link;
 386         rmt_link = upc_from_link_ref (link->next);
 387         rmt_link->signal = 1;
 388       }
 389     }
 390   upc_lock_link_free (link);
 391 }
 392
 393 /* Heap manager lock support.  */
 394
 395 void
 396 __upc_acquire_alloc_lock ()
 397 {
 398   upc_lock (&__upc_alloc_lock);
 399 }
 400
 401 void
 402 __upc_release_alloc_lock ()
 403 {
 404   upc_unlock (&__upc_alloc_lock);
 405 }
 406
 407 /* Initialize UPC lock resources.  */
 408 void
 409 __upc_lock_init (void)
 410 {
 411   upc_lock_link_init ();
 412   lock_free = NULL;
 413
 414   /* Heap manager lock must be manually initialized.  */
 415   if (!MYTHREAD)
 416     upc_new_lock_init (&__upc_alloc_lock);
 417 }
 418
 419 /** @} */