1 /* ---------------------------------------------------------------------------
2 Time-stamp: <Sat Dec 04 1999 21:28:56 Stardate: [-30]3999.47 hwloidl>
3 $Id: Global.c,v 1.2 2000/01/13 14:34:06 hwloidl Exp $
5 (c) The AQUA/Parade Projects, Glasgow University, 1995
6 The GdH/APART 624 Projects, Heriot-Watt University, Edinburgh, 1999
8 Global Address Manipulation.
10 The GALA and LAGA tables for mapping global addresses to local addresses
11 (i.e. heap pointers) are defined here. We use the generic hash tables
13 ------------------------------------------------------------------------- */
15 #ifdef PAR /* whole file */
19 //* Global tables and lists::
20 //* Fcts on GALA tables::
21 //* Interface to taskId-PE table::
22 //* Interface to LAGA table::
23 //* Interface to GALA table::
24 //* GC functions for GALA tables::
28 //@node Includes, Global tables and lists, Global Address Manipulation, Global Address Manipulation
29 //@subsection Includes
36 #include "ParallelRts.h"
39 @globalAddr@ structures are allocated in chunks to reduce malloc overhead.
42 //@node Global tables and lists, Fcts on GALA tables, Includes, Global Address Manipulation
43 //@subsection Global tables and lists
53 //@node Free lists, Hash tables, Global tables and lists, Global tables and lists
54 //@subsubsection Free lists
56 /* Free list of GALA entries */
57 GALA *freeGALAList = NULL;
59 /* Number of globalAddr cells to allocate in one go */
60 #define GCHUNK (1024 * sizeof(StgWord) / sizeof(GALA))
62 /* Free list of indirections */
64 //@cindex nextIndirection
65 static StgInt nextIndirection = 0;
66 //@cindex freeIndirections
67 GALA *freeIndirections = NULL;
69 /* The list of live indirections has to be marked for GC (see makeGlobal) */
70 //@cindex liveIndirections
71 GALA *liveIndirections = NULL;
73 /* The list of remote indirections has to be marked for GC (see setRemoteGA) */
74 //@cindex liveRemoteGAs
75 GALA *liveRemoteGAs = NULL;
77 //@node Hash tables, , Free lists, Global tables and lists
78 //@subsubsection Hash tables
80 /* Mapping global task ids PEs */
81 //@cindex taskIDtoPEtable
82 HashTable *taskIDtoPEtable = NULL;
84 static int nextPE = 0;
86 /* LAGA table: StgClosure* -> globalAddr*
87 (Remember: globalAddr = (GlobalTaskId, Slot, Weight))
88 Mapping local to global addresses (see interface below)
91 //@cindex LAtoGALAtable
92 HashTable *LAtoGALAtable = NULL;
94 /* GALA table: globalAddr* -> StgClosure*
95 (Remember: globalAddr = (GlobalTaskId, Slot, Weight))
96 Mapping global to local addresses (see interface below)
99 //@cindex pGAtoGALAtable
100 HashTable *pGAtoGALAtable = NULL;
102 //@node Fcts on GALA tables, Interface to taskId-PE table, Global tables and lists, Global Address Manipulation
103 //@subsection Fcts on GALA tables
111 if ((gl = freeGALAList) != NULL) {
112 freeGALAList = gl->next;
114 gl = (GALA *) stgMallocBytes(GCHUNK * sizeof(GALA), "allocGALA");
116 freeGALAList = gl + 1;
117 for (p = freeGALAList; p < gl + GCHUNK - 1; p++)
124 //@node Interface to taskId-PE table, Interface to LAGA table, Fcts on GALA tables, Global Address Manipulation
125 //@subsection Interface to taskId-PE table
128 We don't really like GLOBAL_TASK_ID, so we keep a table of TASK_ID to
129 PE mappings. The idea is that a PE identifier will fit in 16 bits, whereas
135 taskIDtoPE(GlobalTaskId gtid)
137 return (PEs) lookupHashTable(taskIDtoPEtable, gtid);
140 //@cindex registerTask
148 insertHashTable(taskIDtoPEtable, gtid, (void *) (StgWord) nextPE++);
151 //@node Interface to LAGA table, Interface to GALA table, Interface to taskId-PE table, Global Address Manipulation
152 //@subsection Interface to LAGA table
155 The local address to global address mapping returns a globalAddr structure
156 (pe task id, slot, weight) for any closure in the local heap which has a
157 global identity. Such closures may be copies of normal form objects with
158 a remote `master' location, @FetchMe@ nodes referencing remote objects, or
159 globally visible objects in the local heap (for which we are the master).
169 /* We never look for GA's on indirections */
170 ASSERT(IS_INDIRECTION(addr) == NULL);
171 if ((gala = lookupHashTable(LAtoGALAtable, (StgWord) addr)) == NULL)
177 //@node Interface to GALA table, GC functions for GALA tables, Interface to LAGA table, Global Address Manipulation
178 //@subsection Interface to GALA table
181 We also manage a mapping of global addresses to local addresses, so that
182 we can ``common up'' multiple references to the same object as they arrive
183 in data packets from remote PEs.
185 The global address to local address mapping is actually managed via a
186 ``packed global address'' to GALA hash table. The packed global
187 address takes the interesting part of the @globalAddr@ structure
188 (i.e. the pe and slot fields) and packs them into a single word
189 suitable for hashing.
197 StgWord pga = PackGA(taskIDtoPE(ga->payload.gc.gtid), ga->payload.gc.slot);
200 if ((gala = (GALA *) lookupHashTable(pGAtoGALAtable, pga)) == NULL)
204 * Bypass any indirections when returning a local closure to
205 * the caller. Note that we do not short-circuit the entry in
206 * the GALA tables right now, because we would have to do a
207 * hash table delete and insert in the LAtoGALAtable to keep
208 * that table up-to-date for preferred GALA pairs. That's
209 * probably a bit expensive.
211 return UNWIND_IND((StgClosure *)(gala->la));
216 External references to our globally-visible closures are managed through an
217 indirection table. The idea is that the closure may move about as the result
218 of local garbage collections, but its global identity is determined by its
219 slot in the indirection table, which never changes.
221 The indirection table is maintained implicitly as part of the global
222 address to local address table. We need only keep track of the
223 highest numbered indirection index allocated so far, along with a free
224 list of lower numbered indices no longer in use.
228 Allocate an indirection slot for the closure currently at address @addr@.
231 //@cindex allocIndirection
233 allocIndirection(StgPtr addr)
237 if ((gala = freeIndirections) != NULL) {
238 freeIndirections = gala->next;
241 gala->ga.payload.gc.gtid = mytid;
242 gala->ga.payload.gc.slot = nextIndirection++;
244 gala->ga.weight = MAX_GA_WEIGHT;
250 Make a local closure at @addr@ globally visible. We have to allocate an
251 indirection slot for it, and update both the local address to global address
252 and global address to local address maps.
257 makeGlobal(addr, preferred)
261 GALA *oldGALA = lookupHashTable(LAtoGALAtable, (StgWord) addr);
262 GALA *newGALA = allocIndirection((StgPtr)addr);
263 StgWord pga = PackGA(thisPE, newGALA->ga.payload.gc.slot);
265 ASSERT(HEAP_ALLOCED(addr)); // check that addr might point into the heap
266 ASSERT(GALAlookup(&(newGALA->ga)) == NULL);
269 newGALA->preferred = preferred;
272 /* The new GA is now the preferred GA for the LA */
273 if (oldGALA != NULL) {
274 oldGALA->preferred = rtsFalse;
275 (void) removeHashTable(LAtoGALAtable, (StgWord) addr, (void *) oldGALA);
277 insertHashTable(LAtoGALAtable, (StgWord) addr, (void *) newGALA);
280 /* put the new GALA entry on the list of live indirections */
281 newGALA->next = liveIndirections;
282 liveIndirections = newGALA;
284 insertHashTable(pGAtoGALAtable, pga, (void *) newGALA);
286 return &(newGALA->ga);
290 Assign an existing remote global address to an existing closure.
291 We do not retain the @globalAddr@ structure that's passed in as an argument,
292 so it can be a static in the calling routine.
295 //@cindex setRemoteGA
297 setRemoteGA(addr, ga, preferred)
302 GALA *oldGALA = lookupHashTable(LAtoGALAtable, (StgWord) addr);
303 GALA *newGALA = allocGALA();
304 StgWord pga = PackGA(taskIDtoPE(ga->payload.gc.gtid), ga->payload.gc.slot);
306 ASSERT(ga->payload.gc.gtid != mytid);
307 ASSERT(ga->weight > 0);
308 ASSERT(GALAlookup(ga) == NULL);
312 newGALA->preferred = preferred;
315 /* The new GA is now the preferred GA for the LA */
316 if (oldGALA != NULL) {
317 oldGALA->preferred = rtsFalse;
318 (void) removeHashTable(LAtoGALAtable, (StgWord) addr, (void *) oldGALA);
320 insertHashTable(LAtoGALAtable, (StgWord) addr, (void *) newGALA);
322 newGALA->next = liveRemoteGAs;
323 liveRemoteGAs = newGALA;
325 insertHashTable(pGAtoGALAtable, pga, (void *) newGALA);
329 return &(newGALA->ga);
333 Give me a bit of weight to give away on a new reference to a particular
334 global address. If we run down to nothing, we have to assign a new GA.
337 //@cindex splitWeight
339 splitWeight(to, from)
340 globalAddr *to, *from;
342 /* Make sure we have enough weight to split */
343 if (from->weight == 1)
344 from = makeGlobal(GALAlookup(from), rtsTrue);
346 to->payload = from->payload;
348 if (from->weight == 0)
349 to->weight = 1L << (BITS_IN(unsigned) - 1);
351 to->weight = from->weight / 2;
353 from->weight -= to->weight;
357 Here, I am returning a bit of weight that a remote PE no longer needs.
365 StgWord pga = PackGA(taskIDtoPE(ga->payload.gc.gtid), ga->payload.gc.slot);
366 GALA *gala = (GALA *) lookupHashTable(pGAtoGALAtable, pga);
369 fprintf(stderr, "@* Adding weight %x to ", ga->weight);
370 printGA(&(gala->ga));
371 fputc('\n', stderr));
373 gala->ga.weight += ga->weight;
380 Initialize all of the global address structures: the task ID to PE id
381 map, the local address to global address map, the global address to
382 local address map, and the indirection table.
385 //@cindex initGAtables
389 taskIDtoPEtable = allocHashTable();
390 LAtoGALAtable = allocHashTable();
391 pGAtoGALAtable = allocHashTable();
400 int pe_shift = (BITS_IN(StgWord)*3)/4;
401 int pe_bits = BITS_IN(StgWord) - pe_shift;
403 if ( pe_bits < 8 || slot >= (1L << pe_shift) ) { /* big trouble */
405 fprintf(stderr, "PackGA: slot# too big (%d) or not enough pe_bits (%d)\n",
407 stg_exit(EXIT_FAILURE);
410 return((((StgWord)(pe)) << pe_shift) | ((StgWord)(slot)));
412 /* the idea is to use 3/4 of the bits (e.g., 24) for indirection-
413 table "slot", and 1/4 for the pe# (e.g., 8).
415 We check for too many bits in "slot", and double-check (at
416 compile-time?) that we have enough bits for "pe". We *don't*
417 check for too many bits in "pe", because SysMan enforces a
418 MAX_PEs limit at the very very beginning.
424 //@node GC functions for GALA tables, Debugging routines, Interface to GALA table, Global Address Manipulation
425 //@subsection GC functions for GALA tables
428 When we do a copying collection, we want to evacuate all of the local
429 entries in the GALA table for which there are outstanding remote
430 pointers (i.e. for which the weight is not MAX_GA_WEIGHT.)
432 //@cindex markLocalGAs
434 markLocalGAs(rtsBool full)
439 StgPtr old_la, new_la;
440 nat n=0, m=0; // debugging only
443 belch("@@ markLocalGAs: Marking LIVE INDIRECTIONS in GALA table starting with GALA at %p\n",
447 for (gala = liveIndirections, m=0; gala != NULL; gala = next, m++) {
449 printGA(&(gala->ga));
450 fprintf(stderr, ";@ %d: LA: %p (%s) ",
451 m, gala->la, info_type(gala->la)));
454 ASSERT(gala->ga.payload.gc.gtid == mytid); /* it's supposed to be local */
455 if (get_itbl((StgClosure *)old_la)->type == EVACUATED) {
456 /* somebody else already evacuated this closure */
457 new_la = ((StgEvacuated *)old_la)->evacuee;
459 belch(" already evacuated to %p\n", new_la));
461 StgClosure *foo ; // debugging only
463 IF_PAR_DEBUG(verbose,
464 if (IS_INDIRECTION((StgClosure *)old_la))
465 belch("{markLocalGAs}Daq ghuH: trying to mark an indirection %p (%s) -> %p (%s); [closure=%p]",
466 old_la, info_type(old_la),
467 (foo = UNWIND_IND((StgClosure *)old_la)), info_type(foo),
469 new_la = MarkRoot(UNWIND_IND((StgClosure *)old_la)); // or just evacuate(old_ga)
471 belch(" evacuated %p to %p\n", old_la, new_la));
475 /* remove old LA and replace with new LA */
476 //(void) removeHashTable(LAtoGALAtable, (StgWord) old_la, (void *) gala);
477 //insertHashTable(LAtoGALAtable, (StgWord) new_la, (void *) gala);
482 liveIndirections = prev; /* list has been reversed during the marking */
484 IF_PAR_DEBUG(verbose,
485 belch("@@ markLocalGAs: %d of %d GALAs marked on PE %x",
488 /* -------------------------------------------------------------------- */
490 n=0; m=0; // debugging only
493 belch("@@ markLocalGAs: Marking LIVE REMOTE GAs in GALA table starting with GALA at %p\n",
496 for (gala = liveRemoteGAs, prev = NULL; gala != NULL; gala = next) {
498 printGA(&(gala->ga)));
501 ASSERT(gala->ga.payload.gc.gtid != mytid); /* it's supposed to be remote */
502 if (get_itbl((StgClosure *)old_la)->type == EVACUATED) {
503 /* somebody else already evacuated this closure */
504 new_la = ((StgEvacuated *)old_la)->evacuee;
507 new_la = MarkRoot((StgClosure *)old_la); // or just evacuate(old_ga)
511 /* remove old LA and replace with new LA */
512 //(void) removeHashTable(LAtoGALAtable, (StgWord) old_la, (void *) gala);
513 //insertHashTable(LAtoGALAtable, (StgWord) new_la, (void *) gala);
518 liveRemoteGAs = prev; /* list is reversed during marking */
520 /* If we have any remaining FREE messages to send off, do so now */
521 // sendFreeMessages();
524 belch("@@ markLocalGAs: GALA after marking");
526 belch("--------------------------------------"));
531 OLDmarkLocalGAs(rtsBool full)
533 extern StgClosure *MarkRootHWL(StgClosure *root);
539 nat n=0, m=0; // debugging only
542 belch("@@ markLocalGAs: Marking entries in GALA table starting with GALA at %p",
546 for (gala = liveIndirections; gala != NULL; gala = next) {
548 printGA(&(gala->ga));
549 fprintf(stderr, " LA: %p (%s) ",
550 gala->la, info_type(gala->la)));
552 ASSERT(gala->ga.payload.gc.gtid == mytid); /* it's supposed to be local */
553 if (gala->ga.weight != MAX_GA_WEIGHT) {
554 /* Remote references exist, so we must evacuate the local closure */
555 StgPtr old_la = gala->la;
557 if (get_itbl((StgClosure *)old_la)->type != EVACUATED) { // track evacuee!??
560 fprintf(stderr, " marking as root\n"));
561 new_la = MarkRoot((StgClosure *)old_la); // or just evacuate(old_ga)
563 // fprintf(stderr, " new LA is %p ", new_la));
564 if (!full && gala->preferred && new_la != old_la) {
566 fprintf(stderr, " replacing %p with %p in LAGA table\n",
568 (void) removeHashTable(LAtoGALAtable, (StgWord) old_la, (void *) gala);
569 insertHashTable(LAtoGALAtable, (StgWord) new_la, (void *) gala);
573 fprintf(stderr, " EVAC "));
574 new_la = ((StgEvacuated *)old_la)->evacuee;
576 fprintf(stderr, " replacing %p with %p in LAGA table\n",
578 (void) removeHashTable(LAtoGALAtable, (StgWord) old_la, (void *) gala);
579 insertHashTable(LAtoGALAtable, (StgWord) new_la, (void *) gala);
584 /* Since we have all of the weight, this GA is no longer needed */
585 StgWord pga = PackGA(thisPE, gala->ga.payload.gc.slot);
589 fprintf(stderr, " freeing slot %d",
590 gala->ga.payload.gc.slot));
592 /* put the now redundant GALA onto the free list */
593 gala->next = freeIndirections;
594 freeIndirections = gala;
595 /* remove the GALA from the GALA table; now it's just local */
596 (void) removeHashTable(pGAtoGALAtable, pga, (void *) gala);
597 if (!full && gala->preferred)
598 (void) removeHashTable(LAtoGALAtable, (StgWord) gala->la, (void *) gala);
601 gala->ga.weight = 0x0d0d0d0d;
602 gala->la = (StgWord) 0x0bad0bad;
606 liveIndirections = prev; /* list has been reversed during the marking */
608 IF_PAR_DEBUG(verbose,
609 belch("@@ markLocalGAs: %d GALAs marked, %d GALAs nuked on PE %x",
614 //@cindex RebuildGAtables
616 RebuildGAtables(rtsBool full)
621 StgClosure *closure, *last, *new_closure;
623 //prepareFreeMsgBuffers();
629 belch("@@ RebuildGAtables: After ReBuilding GALA table starting with GALA at %p",
635 OLDRebuildGAtables(rtsBool full)
640 StgClosure *closure, *last, *new_closure;
642 prepareFreeMsgBuffers();
644 for (gala = liveRemoteGAs, prev = NULL; gala != NULL; gala = next) {
646 printGA(&(gala->ga)));
648 ASSERT(gala->ga.payload.gc.gtid != mytid); /* it's supposed to be remote */
650 closure = (StgClosure *) (gala->la);
653 * If the old closure has not been forwarded, we let go. Note that this
654 * approach also drops global aliases for PLCs.
657 if (!full && gala->preferred)
658 (void) removeHashTable(LAtoGALAtable, (StgWord) gala->la, (void *) gala);
660 /* Follow indirection chains to the end, just in case */
661 closure = UNWIND_IND(closure);
664 if (get_itbl(closure)->type != EVACUATED) { // (new_closure = isAlive(closure)) == NULL) { // (W_) Forward_Ref_info)
665 // closure is not alive any more, thus remove GA
666 int pe = taskIDtoPE(gala->ga.payload.gc.gtid);
667 StgWord pga = PackGA(pe, gala->ga.payload.gc.slot);
670 fprintf(stderr, " (LA: %p (%s)) is unused on this PE -> sending free\n",
671 closure, info_type(closure)));
673 (void) removeHashTable(pGAtoGALAtable, pga, (void *) gala);
674 freeRemoteGA(pe, &(gala->ga));
675 gala->next = freeGALAList;
679 if (get_itbl(closure)->type == EVACUATED) {
681 fprintf(stderr, " EVAC %p (%s)\n",
682 closure, info_type(closure)));
683 closure = ((StgEvacuated *)closure)->evacuee;
686 fprintf(stderr, " !EVAC %p (%s)\n",
687 closure, info_type(closure)));
690 if (!full && gala->preferred)
691 insertHashTable(LAtoGALAtable, (StgWord) gala->la, (void *) gala);
696 liveRemoteGAs = prev; /* list is reversed during marking */
698 /* If we have any remaining FREE messages to send off, do so now */
705 belch("@@ RebuildGAtables: After ReBuilding GALA table starting with GALA at %p",
711 Rebuild the LA->GA table, assuming that the addresses in the GALAs are
715 //@cindex RebuildLAGAtable
717 RebuildLAGAtable(void)
720 nat n=0, m=0; // debugging
722 /* The old LA->GA table is worthless */
723 freeHashTable(LAtoGALAtable, NULL);
724 LAtoGALAtable = allocHashTable();
727 belch("@@ RebuildLAGAtable: new LAGA table at %p",
730 for (gala = liveIndirections; gala != NULL; gala = gala->next) {
733 insertHashTable(LAtoGALAtable, (StgWord) gala->la, (void *) gala);
736 for (gala = liveRemoteGAs; gala != NULL; gala = gala->next) {
739 insertHashTable(LAtoGALAtable, (StgWord) gala->la, (void *) gala);
743 belch("@@ RebuildLAGAtable: inserted %d entries from liveIndirections and %d entries from liveRemoteGAs",
748 //@node Debugging routines, Index, GC functions for GALA tables, Global Address Manipulation
749 //@subsection Debugging routines
753 printGA (globalAddr *ga)
755 fprintf(stderr, "((%x, %d, %x))",
763 printGALA (GALA *gala)
765 printGA(&(gala->ga));
766 fprintf(stderr, " -> %p (%s)", (StgPtr)gala->la, info_type(gala->la));
767 fprintf(stderr, " %s", (gala->preferred) ? "PREF" : "____");
771 Printing the LA->GA table.
774 //@cindex DebugPrintLAGAtable
779 nat n=0, m=0; // debugging
781 belch("@@ LAGAtable (%p) with liveIndirections=%p, liveRemoteGAs=%p:",
782 LAtoGALAtable, liveIndirections, liveRemoteGAs);
784 for (gala = liveIndirections; gala != NULL; gala = gala->next) {
790 for (gala = liveRemoteGAs; gala != NULL; gala = gala->next) {
795 belch("@@ LAGAtable has %d liveIndirections entries and %d liveRemoteGAs entries",
799 #endif /* PAR -- whole file */
801 //@node Index, , Debugging routines, Global Address Manipulation
805 //* GALAlookup:: @cindex\s-+GALAlookup
806 //* LAGAlookup:: @cindex\s-+LAGAlookup
807 //* LAtoGALAtable:: @cindex\s-+LAtoGALAtable
808 //* PackGA:: @cindex\s-+PackGA
809 //* RebuildGAtables:: @cindex\s-+RebuildGAtables
810 //* RebuildLAGAtable:: @cindex\s-+RebuildLAGAtable
811 //* addWeight:: @cindex\s-+addWeight
812 //* allocGALA:: @cindex\s-+allocGALA
813 //* allocIndirection:: @cindex\s-+allocIndirection
814 //* freeIndirections:: @cindex\s-+freeIndirections
815 //* initGAtables:: @cindex\s-+initGAtables
816 //* liveIndirections:: @cindex\s-+liveIndirections
817 //* liveRemoteGAs:: @cindex\s-+liveRemoteGAs
818 //* makeGlobal:: @cindex\s-+makeGlobal
819 //* markLocalGAs:: @cindex\s-+markLocalGAs
820 //* nextIndirection:: @cindex\s-+nextIndirection
821 //* pGAtoGALAtable:: @cindex\s-+pGAtoGALAtable
822 //* registerTask:: @cindex\s-+registerTask
823 //* setRemoteGA:: @cindex\s-+setRemoteGA
824 //* splitWeight:: @cindex\s-+splitWeight
825 //* taskIDtoPE:: @cindex\s-+taskIDtoPE
826 //* taskIDtoPEtable:: @cindex\s-+taskIDtoPEtable
827 //* thisPE:: @cindex\s-+thisPE