libgupc/smp/upc_alloc.upc

   1 /* Copyright (C) 2006-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
  28 #include <upc.h>
  29 #ifdef __sgi__
  30 /* UPC's definitions conflict with definitions in SGI's
  31    header files, which are included by upc_config.h.  */
  32 #undef barrier
  33 #undef fence
  34 #endif /* __sgi__ */
  35 #include <stdlib.h>
  36 #include <stddef.h>
  37 #include <stdio.h>
  38
  39 #define DEBUG_ALLOC 1
  40 #undef DEBUG_ALLOC
  41
  42 /* upc_alloc.upc implements UPC's dynamic memory allocation
  43    routines.  The implementation is written in UPC, because
  44    it needs to run above the runtime library's memory mapping
  45    facility.  Internal runtime locks are used rather than
  46    the UPC language-defined locks, because those locks
  47    depend upon dynamic memory management, and we need to
  48    break the circular dependency.  */
  49
  50 typedef struct upc_heap_struct
  51   {
  52     shared struct upc_heap_struct *next;   /* MUST BE FIRST FIELD */
  53     size_t size;
  54     int alloc_tag;
  55     int is_global;
  56     int alloc_seq;
  57   } upc_heap_t;
  58 typedef shared upc_heap_t *upc_heap_p;
  59 #define GUPCR_HEAP_OVERHEAD GUPCR_ROUND (sizeof (upc_heap_t), GUPCR_HEAP_ALLOC_MIN)
  60
  61 static shared upc_heap_p __upc_global_heap;
  62 static shared upc_heap_p __upc_local_heap[THREADS];
  63 static shared void * shared __upc_all_alloc_val;
  64 static shared int __upc_alloc_seq;
  65
  66 #undef NULL
  67 #define NULL (shared void *)0
  68
  69 typedef union _pts_as_rep
  70   {
  71     shared void *pts;
  72     upc_shared_ptr_t rep;
  73   } pts_as_rep_t;
  74
  75 /* Create a shared pointer, given (addrfield, thread)  */
  76 static inline
  77 shared void *
  78 __upc_alloc_build_pts (size_t addrfield, size_t thread)
  79 {
  80   pts_as_rep_t r;
  81   r.pts = NULL;
  82   GUPCR_PTS_SET_VADDR  (r.rep, addrfield);
  83   GUPCR_PTS_SET_THREAD (r.rep, thread);
  84   return r.pts;
  85 }
  86
  87 /* Increment a shared pointer, by nbytes */
  88 static inline
  89 shared void *
  90 __upc_alloc_ptr_add (shared void *ptr, ptrdiff_t nbytes)
  91 {
  92   return (shared void *)(((shared [] char *)ptr) + nbytes);
  93 }
  94
  95 #ifdef DEBUG_ALLOC
  96 static
  97 char *
  98 __upc_alloc_sptostr (shared void *p)
  99 {
 100   static char s[100];
 101   sprintf (s, "(0x%012lx,0x%02x,0x%016lx)",
 102     (long unsigned int)upc_phaseof(p), (unsigned int)upc_threadof(p),
 103     (long unsigned int)upc_addrfield(p));
 104   return s;
 105 }
 106 #endif /* DEBUG_ALLOC */
 107
 108 /* upc_heap_init() is called from the runtime to initially
 109    create the heap.  Heap_base is the virtual address
 110    of where the heap should begin, and heap_size is the
 111    initial heap_size.  The caller has already allocated
 112    the underlying space.  Note that the lower level
 113    heap manager doesn't use locks -- all locking must
 114    be done at a higher level.  */
 115
 116 void
 117 __upc_heap_init (upc_shared_ptr_t heap_base, size_t heap_size)
 118 {
 119   int t;
 120   upc_heap_p heap;
 121   heap = *((upc_heap_p *)&heap_base);
 122   upc_memset (heap, '\0', sizeof (upc_heap_t));
 123   __upc_alloc_seq = 0;
 124   /* the size of each free list entry includes its overhead. */
 125   heap->size = heap_size;
 126   heap->next = NULL;
 127   heap->is_global = 1;
 128   heap->alloc_seq = ++__upc_alloc_seq;
 129   __upc_global_heap = heap;
 130   for (t = 0; t < THREADS; ++t)
 131     __upc_local_heap[t] = NULL;
 132 }
 133
 134 /* Allocate a block of size 'alloc_size' identified indirectly
 135    via 'heap_p'.  'alloc_size' must include the heap overhead.
 136    The 'global_flag' is simply copied into the newly allocated
 137    heap node.  A pointer to the heap node is returned.  */
 138
 139 static
 140 upc_heap_p
 141 __upc_heap_alloc (shared upc_heap_p *heap_p, size_t alloc_size,
 142                     int global_flag)
 143 {
 144   shared upc_heap_p *p;
 145   upc_heap_p alloc;
 146 #ifdef DEBUG_ALLOC
 147   printf ("%d: --> __upc_heap_alloc (%ld): heap on entry\n", MYTHREAD, (long int) alloc_size);
 148   for (p = heap_p; *p; p = (shared upc_heap_p *)&(*p)->next)
 149     printf("%d: addr: %s size: %ld global: %d seq: %d\n", MYTHREAD, __upc_alloc_sptostr(*p),(long int)(*p)->size,(*p)->is_global,(*p)->alloc_seq);
 150 #endif /* DEBUG_ALLOC */
 151   for (p = heap_p; *p && ((*p)->size < alloc_size);
 152        p = (shared upc_heap_p *)&(*p)->next) /* loop */ ;
 153   alloc = *p;
 154   if (alloc)
 155     {
 156       size_t this_size = alloc->size;
 157       size_t rem = this_size - alloc_size;
 158       alloc->is_global = global_flag;
 159       alloc->alloc_tag = GUPCR_HEAP_ALLOC_TAG;
 160       /* make sure the remaining fragment meets min. size requirement */
 161       if (rem < (GUPCR_HEAP_ALLOC_MIN + GUPCR_HEAP_OVERHEAD))
 162         {
 163           alloc_size = this_size;
 164           rem = 0;
 165         }
 166       alloc->size = alloc_size;
 167       if (rem > 0)
 168         {
 169           /* link the remainder onto the free list */
 170           upc_heap_p frag = __upc_alloc_ptr_add (alloc, alloc_size);
 171           frag->next = alloc->next;
 172           frag->alloc_seq = alloc->alloc_seq;
 173           frag->is_global = alloc->is_global;
 174           frag->alloc_tag = 0;
 175           frag->size = rem;
 176           *p = frag;
 177         }
 178       else
 179         {
 180           /* entry exactly fits, delink this free list entry */
 181           *p = alloc->next;
 182         }
 183 #ifdef DEBUG_ALLOC
 184   printf ("%d:   __upc_heap_alloc: heap on exit\n", MYTHREAD);
 185   for (p = heap_p; *p; p = ( shared upc_heap_p *)&(*p)->next)
 186     printf("%d: addr: %s size: %ld global: %d seq: %d\n",MYTHREAD,__upc_alloc_sptostr(*p),(long int)(*p)->size,(*p)->is_global,(*p)->alloc_seq);
 187 #endif /* DEBUG_ALLOC */
 188     }
 189 #ifdef DEBUG_ALLOC
 190   printf ("%d: <- __upc_heap_alloc: %s\n", MYTHREAD, __upc_alloc_sptostr (alloc));
 191 #endif /* DEBUG_ALLOC */
 192   return alloc;
 193 }
 194
 195 static
 196 void
 197 __upc_heap_free (shared upc_heap_p *heap_p, upc_heap_p ptr)
 198 {
 199   shared upc_heap_p *p;
 200   upc_heap_p prev;
 201 #ifdef DEBUG_ALLOC
 202   printf ("%d: --> __upc_heap_free: ", MYTHREAD);
 203   printf("%d: addr: %s size: %ld global: %d seq: %d\n", MYTHREAD,
 204     __upc_alloc_sptostr(ptr),(long int)ptr->size,ptr->is_global,ptr->alloc_seq);
 205   printf ("%d:   heap on entry\n", MYTHREAD);
 206   for (p = heap_p; *p; p = ( shared upc_heap_p *)&(*p)->next)
 207     printf("%d: addr: %s size: %ld global: %d seq: %d\n", MYTHREAD, __upc_alloc_sptostr(*p),(long int)(*p)->size,(*p)->is_global,(*p)->alloc_seq);
 208 #endif /* DEBUG_ALLOC */
 209   for (p = heap_p, prev = NULL; *p && (ptr > *p);
 210        prev = *p, p = (shared upc_heap_p *)&(*p)->next) /* loop */ ;
 211   ptr->alloc_tag = 0;
 212   ptr->next = *p;
 213   *p = ptr;
 214   if (ptr->next && (ptr->next == __upc_alloc_ptr_add (ptr, ptr->size))
 215       && (ptr->alloc_seq == ptr->next->alloc_seq))
 216     {
 217       /* adjacent, merge this block with the next */
 218       ptr->size += ptr->next->size;
 219       ptr->next =  ptr->next->next;
 220     }
 221   if (prev && (ptr  == __upc_alloc_ptr_add (prev, prev->size))
 222       && (ptr->alloc_seq == prev->alloc_seq))
 223     {
 224       /* adjacent, merge this block with previous */
 225       prev->size += ptr->size;
 226       prev->next =  ptr->next;
 227     }
 228 #ifdef DEBUG_ALLOC
 229   printf ("%d: <- __upc_heap_free: heap on exit\n", MYTHREAD);
 230   for (p = heap_p; *p; p = ( shared upc_heap_p *)&(*p)->next)
 231     printf("%d: addr: %s size: %ld global: %d seq: %d\n",MYTHREAD,__upc_alloc_sptostr(*p),(long int)(*p)->size,(*p)->is_global,(*p)->alloc_seq);
 232 #endif /* DEBUG_ALLOC */
 233 }
 234
 235
 236 /* Allocate a block of size 'alloc_size' from the global heap.
 237    Extend the heap if more space is needed.  'alloc_size' is
 238    the size of the heap node returned, inclusive of overhead.  */
 239
 240 static
 241 upc_heap_p
 242 __upc_global_heap_alloc (size_t alloc_size)
 243 {
 244   shared upc_heap_p *heap_p = &__upc_global_heap;
 245   upc_heap_p alloc;
 246 #ifdef DEBUG_ALLOC
 247   printf ("%d: -> __upc_global_heap_alloc (%ld)\n", MYTHREAD, (long int)alloc_size);
 248 #endif /* DEBUG_ALLOC */
 249   alloc = __upc_heap_alloc (heap_p, alloc_size, 1);
 250   if (!alloc)
 251     {
 252       /* Extend the heap.  */
 253       const size_t chunk_size = GUPCR_ROUND (alloc_size,
 254                                           GUPCR_HEAP_CHUNK_SIZE);
 255       const size_t vm_alloc_size = GUPCR_ROUND (chunk_size, GUPCR_VM_PAGE_SIZE);
 256       const upc_page_num_t vm_alloc_pages = vm_alloc_size / GUPCR_VM_PAGE_SIZE;
 257       const upc_page_num_t cur_page_alloc = __upc_vm_get_cur_page_alloc ();
 258       const size_t new_alloc_base = (size_t)cur_page_alloc * GUPCR_VM_PAGE_SIZE;
 259       const upc_heap_p new_alloc = __upc_alloc_build_pts (new_alloc_base, 0);
 260 #ifdef DEBUG_ALLOC
 261       printf ("%d: __upc_global_heap_alloc: extend heap by %d pages\n",
 262          MYTHREAD, vm_alloc_pages);
 263 #endif /* DEBUG_ALLOC */
 264       if (!__upc_vm_alloc (vm_alloc_pages))
 265         return NULL;
 266       upc_memset (new_alloc, '\0', sizeof (upc_heap_t));
 267       new_alloc->size = vm_alloc_size;
 268       new_alloc->next = NULL;
 269       new_alloc->is_global = 1;
 270       new_alloc->alloc_seq = ++__upc_alloc_seq;;
 271       /* Return the newly allocated space to the heap.  */
 272       __upc_heap_free (heap_p, new_alloc);
 273       alloc = __upc_heap_alloc (heap_p, alloc_size, 1);
 274       if (!alloc)
 275         __upc_fatal ("insufficient UPC dynamic shared memory");
 276     }
 277 #ifdef DEBUG_ALLOC
 278   printf ("%d: <- __upc_global_heap_alloc: %s\n", MYTHREAD, __upc_alloc_sptostr (alloc));
 279 #endif /* DEBUG_ALLOC */
 280   return alloc;
 281 }
 282
 283 static
 284 shared void *
 285 __upc_global_alloc (size_t size)
 286 {
 287   shared void *mem = NULL;
 288   if (size)
 289     {
 290       const size_t alloc_size = GUPCR_ROUND (size + GUPCR_HEAP_OVERHEAD,
 291                                           GUPCR_HEAP_ALLOC_MIN);
 292       upc_heap_p alloc;
 293       __upc_acquire_alloc_lock ();
 294       alloc = __upc_global_heap_alloc (alloc_size);
 295       __upc_release_alloc_lock ();
 296       if (alloc)
 297         mem = __upc_alloc_ptr_add (alloc, GUPCR_HEAP_OVERHEAD);
 298 #ifdef DEBUG_ALLOC
 299       printf ("%d: <- __upc_global_alloc: %s\n", MYTHREAD, __upc_alloc_sptostr(mem));
 300 #endif /* DEBUG_ALLOC */
 301     }
 302   return mem;
 303 }
 304
 305 static
 306 inline
 307 shared void *
 308 __upc_local_alloc (size_t size)
 309 {
 310   shared void *mem = NULL;
 311 #ifdef DEBUG_ALLOC
 312   printf ("%d: --> __upc_local_alloc (%ld)\n", MYTHREAD,(long int)size);
 313 #endif /* DEBUG_ALLOC */
 314   if (size)
 315     {
 316       const size_t alloc_size = GUPCR_ROUND (size + GUPCR_HEAP_OVERHEAD,
 317                                           GUPCR_HEAP_ALLOC_MIN);
 318       shared upc_heap_p *heap_p = &__upc_local_heap[MYTHREAD];
 319       upc_heap_p alloc;
 320       __upc_acquire_alloc_lock ();
 321       alloc = __upc_heap_alloc (heap_p, alloc_size, 0);
 322       if (!alloc)
 323         {
 324           int chunk_seq;
 325           int t;
 326           size_t chunk_size = GUPCR_ROUND (size + GUPCR_HEAP_OVERHEAD,
 327                                                   GUPCR_HEAP_CHUNK_SIZE);
 328           upc_heap_p chunk = __upc_global_heap_alloc (chunk_size);
 329           if (!chunk)
 330             return NULL;
 331           chunk_size = chunk->size;
 332           chunk_seq = chunk->alloc_seq;
 333           /* distribute this chunk over each local free list */
 334           for (t = 0; t < THREADS; ++t)
 335             {
 336               shared upc_heap_p *local_heap_p = &__upc_local_heap[t];
 337               /* Set the thread to 't' so that we can link
 338                  this chunk onto the thread's local heap.  */
 339               upc_heap_p local_chunk = __upc_alloc_build_pts (
 340                                           upc_addrfield (chunk), t);
 341               upc_fence;
 342               /* add this local chunk onto the local free list */
 343               upc_memset (local_chunk, '\0', sizeof (upc_heap_t));
 344               local_chunk->size = chunk_size;
 345               local_chunk->alloc_seq = chunk_seq;
 346               __upc_heap_free (local_heap_p, local_chunk);
 347             }
 348           alloc = __upc_heap_alloc (heap_p, alloc_size, 0);
 349         }
 350       __upc_release_alloc_lock ();
 351       if (alloc)
 352         mem = __upc_alloc_ptr_add (alloc, GUPCR_HEAP_OVERHEAD);
 353     }
 354 #ifdef DEBUG_ALLOC
 355   printf ("%d: <-- __upc_local_alloc: %s\n", MYTHREAD, __upc_alloc_sptostr (mem));
 356 #endif /* DEBUG_ALLOC */
 357   return mem;
 358 }
 359
 360 shared void *
 361 upc_global_alloc (size_t nblocks, size_t nbytes)
 362 {
 363   size_t request_size = GUPCR_ROUND(nblocks, THREADS) * nbytes;
 364   size_t alloc_size = request_size / THREADS;
 365   shared void *mem = __upc_global_alloc (alloc_size);
 366   return mem;
 367 }
 368
 369 shared void *
 370 upc_all_alloc (size_t nblocks, size_t nbytes)
 371 {
 372   size_t request_size = GUPCR_ROUND(nblocks, THREADS) * nbytes;
 373   size_t alloc_size = request_size / THREADS;
 374   shared void *mem = NULL;
 375   if (alloc_size)
 376     {
 377       upc_barrier -1;
 378       if (MYTHREAD == 0)
 379         __upc_all_alloc_val = __upc_global_alloc (alloc_size);
 380       upc_barrier -1;
 381       mem = __upc_all_alloc_val;
 382     }
 383   return mem;
 384 }
 385
 386 shared void *
 387 upc_alloc (size_t nbytes)
 388 {
 389   shared void *mem = NULL;
 390   if (nbytes)
 391     mem = __upc_local_alloc (nbytes);
 392   return mem;
 393 }
 394
 395 void
 396 upc_all_free (shared void *ptr)
 397 {
 398   if (ptr)
 399     {
 400       const int thread = (int)upc_threadof (ptr);
 401       upc_barrier -1;
 402       /* Check for errors only on thread 0.  */
 403       if ((MYTHREAD == 0) && (thread >= THREADS))
 404         __upc_fatal ("upc_all_free() called with invalid shared pointer");
 405       if (thread == MYTHREAD)
 406         upc_free (ptr);
 407     }
 408 }
 409
 410 void
 411 upc_free (shared void *ptr)
 412 {
 413   if (ptr)
 414     {
 415       const size_t offset __attribute__ ((unused)) = upc_addrfield (ptr);
 416       const int thread = (int)upc_threadof (ptr);
 417       const size_t phase = upc_phaseof (ptr);
 418       shared upc_heap_p *heap_p;
 419       upc_heap_p thisp;
 420       if (phase || thread >= THREADS)
 421         __upc_fatal ("upc_free() called with invalid shared pointer");
 422       thisp = (upc_heap_p) __upc_alloc_ptr_add (ptr, -GUPCR_HEAP_OVERHEAD);
 423       if (thisp->is_global && thread)
 424         __upc_fatal ("upc_free() called with invalid shared pointer");
 425       if (thisp->alloc_tag != GUPCR_HEAP_ALLOC_TAG)
 426         __upc_fatal ("upc_free() called with pointer to unallocated space");
 427       if (thisp->is_global)
 428         heap_p = (shared upc_heap_p *)&__upc_global_heap;
 429       else
 430         heap_p = (shared upc_heap_p *)&__upc_local_heap[thread];
 431       __upc_acquire_alloc_lock ();
 432       __upc_heap_free (heap_p, thisp);
 433       __upc_release_alloc_lock ();
 434     }
 435 }