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