ghc/runtime/gum/GlobAddr.lc

   1 %
   2 % (c) The AQUA/Parade Projects, Glasgow University, 1995
   3 %
   4 %************************************************************************
   5 %*                                                                      *
   6 \section[GlobAddr.lc]{Global Address Manipulation}
   7 %*                                                                      *
   8 %************************************************************************
   9
  10 \begin{code}
  11 #ifdef PAR /* whole file */
  12
  13 #include "rtsdefs.h"
  14 \end{code}
  15
  16 @globalAddr@ structures are allocated in chunks to reduce malloc overhead.
  17
  18 \begin{code}
  19
  20 GALA *freeGALAList = NULL;
  21
  22 #define GCHUNK      (1024 * sizeof(W_) / sizeof(GALA))
  23                             /* Number of globalAddr cells to allocate in one go */
  24
  25 static GALA *
  26 allocGALA(STG_NO_ARGS)
  27 {
  28     GALA *gl, *p;
  29
  30     if ((gl = freeGALAList) != NULL) {
  31         freeGALAList = gl->next;
  32     } else {
  33         gl = (GALA *) stgMallocBytes(GCHUNK * sizeof(GALA), "allocGALA");
  34
  35         freeGALAList = gl + 1;
  36         for (p = freeGALAList; p < gl + GCHUNK - 1; p++)
  37             p->next = p + 1;
  38         p->next = NULL;
  39     }
  40     return gl;
  41 }
  42
  43 \end{code}
  44
  45 We don't really like GLOBAL_TASK_ID, so we keep a table of TASK_ID to
  46 PE mappings.  The idea is that a PE identifier will fit in 16 bits, whereas
  47 a TASK_ID may not.
  48
  49 \begin{code}
  50
  51 HashTable *taskIDtoPEtable = NULL;
  52
  53 static int nextPE = 0;
  54
  55 W_
  56 taskIDtoPE(GLOBAL_TASK_ID gtid)
  57 {
  58     return (W_) lookupHashTable(taskIDtoPEtable, gtid);
  59 }
  60
  61 int thisPE;
  62
  63 void
  64 registerTask(gtid)
  65 GLOBAL_TASK_ID gtid;
  66 {
  67     if (gtid == mytid)
  68         thisPE = nextPE;
  69
  70     insertHashTable(taskIDtoPEtable, gtid, (void *) (W_) nextPE++);
  71 }
  72
  73 \end{code}
  74
  75 The local address to global address mapping returns a globalAddr structure
  76 (pe task id, slot, weight) for any closure in the local heap which has a
  77 global identity.  Such closures may be copies of normal form objects with
  78 a remote `master' location, @FetchMe@ nodes referencing remote objects, or
  79 globally visible objects in the local heap (for which we are the master).
  80
  81 \begin{code}
  82
  83 HashTable *LAtoGALAtable = NULL;
  84
  85 globalAddr *
  86 LAGAlookup(addr)
  87 P_ addr;
  88 {
  89     GALA *gala;
  90
  91     /* We never look for GA's on indirections */
  92     ASSERT(INFO_PTR(addr) != (W_) Ind_info_TO_USE);
  93     if ((gala = lookupHashTable(LAtoGALAtable, (W_) addr)) == NULL)
  94         return NULL;
  95     else
  96         return &(gala->ga);
  97 }
  98
  99 \end{code}
 100
 101 We also manage a mapping of global addresses to local addresses, so that
 102 we can ``common up'' multiple references to the same object as they arrive
 103 in data packets from remote PEs.
 104
 105 The global address to local address mapping is actually managed via a
 106 ``packed global address'' to GALA hash table.  The packed global
 107 address takes the interesting part of the @globalAddr@ structure
 108 (i.e. the pe and slot fields) and packs them into a single word
 109 suitable for hashing.
 110
 111 \begin{code}
 112
 113 HashTable *pGAtoGALAtable = NULL;
 114
 115 P_
 116 GALAlookup(ga)
 117 globalAddr *ga;
 118 {
 119     W_ pga = PackGA(taskIDtoPE(ga->loc.gc.gtid), ga->loc.gc.slot);
 120     GALA *gala;
 121     P_ la;
 122
 123     if ((gala = (GALA *) lookupHashTable(pGAtoGALAtable, pga)) == NULL)
 124         return NULL;
 125     else {
 126         la = gala->la;
 127         /*
 128          * Bypass any indirections when returning a local closure to
 129          * the caller.  Note that we do not short-circuit the entry in
 130          * the GALA tables right now, because we would have to do a
 131          * hash table delete and insert in the LAtoGALAtable to keep
 132          * that table up-to-date for preferred GALA pairs.  That's
 133          * probably a bit expensive.
 134          */
 135         while (IS_INDIRECTION(INFO_PTR(la)))
 136             la = (P_) IND_CLOSURE_PTR(la);
 137         return la;
 138     }
 139 }
 140
 141 \end{code}
 142
 143 External references to our globally-visible closures are managed through an
 144 indirection table.  The idea is that the closure may move about as the result
 145 of local garbage collections, but its global identity is determined by its
 146 slot in the indirection table, which never changes.
 147
 148 The indirection table is maintained implicitly as part of the global
 149 address to local address table.  We need only keep track of the
 150 highest numbered indirection index allocated so far, along with a free
 151 list of lower numbered indices no longer in use.
 152
 153 \begin{code}
 154
 155 static I_ nextIndirection = 0;
 156
 157 GALA *freeIndirections = NULL;
 158
 159 \end{code}
 160
 161 Allocate an indirection slot for the closure currently at address @addr@.
 162
 163 \begin{code}
 164
 165 static GALA *
 166 allocIndirection(P_ addr)
 167 {
 168     GALA *gala;
 169
 170     if ((gala = freeIndirections) != NULL) {
 171         freeIndirections = gala->next;
 172     } else {
 173         gala = allocGALA();
 174         gala->ga.loc.gc.gtid = mytid;
 175         gala->ga.loc.gc.slot = nextIndirection++;
 176     }
 177     gala->ga.weight = MAX_GA_WEIGHT;
 178     gala->la = addr;
 179     return gala;
 180 }
 181
 182 \end{code}
 183
 184 Make a local closure at @addr@ globally visible.  We have to allocate an
 185 indirection slot for it, and update both the local address to global address
 186 and global address to local address maps.
 187
 188 \begin{code}
 189
 190 GALA *liveIndirections = NULL;
 191
 192 globalAddr *
 193 MakeGlobal(addr, preferred)
 194 P_ addr;
 195 rtsBool preferred;
 196 {
 197     GALA *oldGALA = lookupHashTable(LAtoGALAtable, (W_) addr);
 198     GALA *newGALA = allocIndirection(addr);
 199     W_ pga = PackGA(thisPE, newGALA->ga.loc.gc.slot);
 200
 201     ASSERT(GALAlookup(&(newGALA->ga)) == NULL);
 202
 203     newGALA->la = addr;
 204     newGALA->preferred = preferred;
 205
 206     if (preferred) {
 207         /* The new GA is now the preferred GA for the LA */
 208         if (oldGALA != NULL) {
 209             oldGALA->preferred = rtsFalse;
 210             (void) removeHashTable(LAtoGALAtable, (W_) addr, (void *) oldGALA);
 211         }
 212         insertHashTable(LAtoGALAtable, (W_) addr, (void *) newGALA);
 213     }
 214
 215     newGALA->next = liveIndirections;
 216     liveIndirections = newGALA;
 217
 218     insertHashTable(pGAtoGALAtable, pga, (void *) newGALA);
 219
 220     return &(newGALA->ga);
 221 }
 222
 223 \end{code}
 224
 225 Assign an existing remote global address to an existing closure.
 226 We do not retain the @globalAddr@ structure that's passed in as an argument,
 227 so it can be a static in the calling routine.
 228
 229 \begin{code}
 230
 231 GALA *liveRemoteGAs = NULL;
 232
 233 globalAddr *
 234 setRemoteGA(addr, ga, preferred)
 235 P_ addr;
 236 globalAddr *ga;
 237 rtsBool preferred;
 238 {
 239     GALA *oldGALA = lookupHashTable(LAtoGALAtable, (W_) addr);
 240     GALA *newGALA = allocGALA();
 241     W_ pga = PackGA(taskIDtoPE(ga->loc.gc.gtid), ga->loc.gc.slot);
 242
 243     ASSERT(ga->loc.gc.gtid != mytid);
 244     ASSERT(ga->weight > 0);
 245     ASSERT(GALAlookup(ga) == NULL);
 246
 247     newGALA->ga = *ga;
 248     newGALA->la = addr;
 249     newGALA->preferred = preferred;
 250
 251     if (preferred) {
 252         /* The new GA is now the preferred GA for the LA */
 253         if (oldGALA != NULL) {
 254             oldGALA->preferred = rtsFalse;
 255             (void) removeHashTable(LAtoGALAtable, (W_) addr, (void *) oldGALA);
 256         }
 257         insertHashTable(LAtoGALAtable, (W_) addr, (void *) newGALA);
 258     }
 259     newGALA->next = liveRemoteGAs;
 260     liveRemoteGAs = newGALA;
 261
 262     insertHashTable(pGAtoGALAtable, pga, (void *) newGALA);
 263
 264     ga->weight = 0;
 265
 266     return &(newGALA->ga);
 267 }
 268 \end{code}
 269
 270 Give me a bit of weight to give away on a new reference to a particular global
 271 address.  If we run down to nothing, we have to assign a new GA.
 272
 273 \begin{code}
 274
 275 void
 276 splitWeight(to, from)
 277 globalAddr *to, *from;
 278 {
 279     /* Make sure we have enough weight to split */
 280     if (from->weight == 1)
 281         from = MakeGlobal(GALAlookup(from), rtsTrue);
 282
 283     to->loc = from->loc;
 284
 285     if (from->weight == 0)
 286         to->weight = 1L << (BITS_IN(unsigned) - 1);
 287     else
 288         to->weight = from->weight / 2;
 289
 290     from->weight -= to->weight;
 291 }
 292
 293 \end{code}
 294
 295 Here, I am returning a bit of weight that a remote PE no longer needs.
 296
 297 \begin{code}
 298
 299 globalAddr *
 300 addWeight(ga)
 301 globalAddr *ga;
 302 {
 303     W_ pga = PackGA(taskIDtoPE(ga->loc.gc.gtid), ga->loc.gc.slot);
 304     GALA *gala = (GALA *) lookupHashTable(pGAtoGALAtable, pga);
 305
 306 #ifdef DEBUG_WEIGHT
 307     fprintf(stderr, "Adding weight %x to (%x, %d, %x), preferred = %d\n", ga->weight,
 308       gala->ga.loc.gc.gtid, gala->ga.loc.gc.slot, gala->ga.weight, gala->preferred);
 309 #endif
 310     gala->ga.weight += ga->weight;
 311     ga->weight = 0;
 312
 313     return &(gala->ga);
 314 }
 315
 316 \end{code}
 317
 318 Initialize all of the global address structures: the task ID to PE id
 319 map, the local address to global address map, the global address to
 320 local address map, and the indirection table.
 321
 322 \begin{code}
 323
 324 void
 325 initGAtables(STG_NO_ARGS)
 326 {
 327     taskIDtoPEtable = allocHashTable();
 328     LAtoGALAtable = allocHashTable();
 329     pGAtoGALAtable = allocHashTable();
 330 }
 331
 332 \end{code}
 333
 334 Rebuild the LA->GA table, assuming that the addresses in the GALAs are correct.
 335
 336 \begin{code}
 337
 338 void
 339 RebuildLAGAtable(STG_NO_ARGS)
 340 {
 341     GALA *gala;
 342
 343     /* The old LA->GA table is worthless */
 344     freeHashTable(LAtoGALAtable, NULL);
 345     LAtoGALAtable = allocHashTable();
 346
 347     for (gala = liveIndirections; gala != NULL; gala = gala->next) {
 348         if (gala->preferred)
 349             insertHashTable(LAtoGALAtable, (W_) gala->la, (void *) gala);
 350     }
 351
 352     for (gala = liveRemoteGAs; gala != NULL; gala = gala->next) {
 353         if (gala->preferred)
 354             insertHashTable(LAtoGALAtable, (W_) gala->la, (void *) gala);
 355     }
 356 }
 357 \end{code}
 358
 359 \begin{code}
 360 W_
 361 PackGA (pe, slot)
 362   W_ pe;
 363   int slot;
 364 {
 365     int pe_shift = (BITS_IN(W_)*3)/4;
 366     int pe_bits  = BITS_IN(W_) - pe_shift;
 367
 368     if ( pe_bits < 8 || slot >= (1L << pe_shift) ) { /* big trouble */
 369         fflush(stdout);
 370         fprintf(stderr, "PackGA: slot# too big (%d) or not enough pe_bits (%d)\n",slot,pe_bits);
 371         EXIT(EXIT_FAILURE);
 372     }
 373
 374     return((((W_)(pe)) << pe_shift) | ((W_)(slot)));
 375
 376     /* the idea is to use 3/4 of the bits (e.g., 24) for indirection-
 377        table "slot", and 1/4 for the pe# (e.g., 8).
 378
 379        We check for too many bits in "slot", and double-check (at
 380        compile-time?) that we have enough bits for "pe".  We *don't*
 381        check for too many bits in "pe", because SysMan enforces a
 382        MAX_PEs limit at the very very beginning.
 383
 384        Phil & Will 95/08
 385     */
 386 }
 387
 388 #endif /* PAR -- whole file */
 389 \end{code}