2 % (c) The AQUA/Parade Projects, Glasgow University, 1995
4 %************************************************************************
6 \section[GlobAddr.lc]{Global Address Manipulation}
8 %************************************************************************
11 #ifdef PAR /* whole file */
16 @globalAddr@ structures are allocated in chunks to reduce malloc overhead.
20 GALA *freeGALAList = NULL;
22 #define GCHUNK (1024 * sizeof(W_) / sizeof(GALA))
23 /* Number of globalAddr cells to allocate in one go */
26 allocGALA(STG_NO_ARGS)
30 if ((gl = freeGALAList) != NULL) {
31 freeGALAList = gl->next;
33 gl = (GALA *) stgMallocBytes(GCHUNK * sizeof(GALA), "allocGALA");
35 freeGALAList = gl + 1;
36 for (p = freeGALAList; p < gl + GCHUNK - 1; p++)
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
51 HashTable *taskIDtoPEtable = NULL;
53 static int nextPE = 0;
56 taskIDtoPE(GLOBAL_TASK_ID gtid)
58 return (W_) lookupHashTable(taskIDtoPEtable, gtid);
70 insertHashTable(taskIDtoPEtable, gtid, (void *) (W_) nextPE++);
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).
83 HashTable *LAtoGALAtable = NULL;
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)
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.
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.
113 HashTable *pGAtoGALAtable = NULL;
119 W_ pga = PackGA(taskIDtoPE(ga->loc.gc.gtid), ga->loc.gc.slot);
123 if ((gala = (GALA *) lookupHashTable(pGAtoGALAtable, pga)) == NULL)
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.
135 while (IS_INDIRECTION(INFO_PTR(la)))
136 la = (P_) IND_CLOSURE_PTR(la);
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.
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.
155 static I_ nextIndirection = 0;
157 GALA *freeIndirections = NULL;
161 Allocate an indirection slot for the closure currently at address @addr@.
166 allocIndirection(P_ addr)
170 if ((gala = freeIndirections) != NULL) {
171 freeIndirections = gala->next;
174 gala->ga.loc.gc.gtid = mytid;
175 gala->ga.loc.gc.slot = nextIndirection++;
177 gala->ga.weight = MAX_GA_WEIGHT;
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.
190 GALA *liveIndirections = NULL;
193 MakeGlobal(addr, preferred)
197 GALA *oldGALA = lookupHashTable(LAtoGALAtable, (W_) addr);
198 GALA *newGALA = allocIndirection(addr);
199 W_ pga = PackGA(thisPE, newGALA->ga.loc.gc.slot);
201 ASSERT(GALAlookup(&(newGALA->ga)) == NULL);
204 newGALA->preferred = 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);
212 insertHashTable(LAtoGALAtable, (W_) addr, (void *) newGALA);
215 newGALA->next = liveIndirections;
216 liveIndirections = newGALA;
218 insertHashTable(pGAtoGALAtable, pga, (void *) newGALA);
220 return &(newGALA->ga);
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.
231 GALA *liveRemoteGAs = NULL;
234 setRemoteGA(addr, ga, preferred)
239 GALA *oldGALA = lookupHashTable(LAtoGALAtable, (W_) addr);
240 GALA *newGALA = allocGALA();
241 W_ pga = PackGA(taskIDtoPE(ga->loc.gc.gtid), ga->loc.gc.slot);
243 ASSERT(ga->loc.gc.gtid != mytid);
244 ASSERT(ga->weight > 0);
245 ASSERT(GALAlookup(ga) == NULL);
249 newGALA->preferred = 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);
257 insertHashTable(LAtoGALAtable, (W_) addr, (void *) newGALA);
259 newGALA->next = liveRemoteGAs;
260 liveRemoteGAs = newGALA;
262 insertHashTable(pGAtoGALAtable, pga, (void *) newGALA);
266 return &(newGALA->ga);
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.
276 splitWeight(to, from)
277 globalAddr *to, *from;
279 /* Make sure we have enough weight to split */
280 if (from->weight == 1)
281 from = MakeGlobal(GALAlookup(from), rtsTrue);
285 if (from->weight == 0)
286 to->weight = 1L << (BITS_IN(unsigned) - 1);
288 to->weight = from->weight / 2;
290 from->weight -= to->weight;
295 Here, I am returning a bit of weight that a remote PE no longer needs.
303 W_ pga = PackGA(taskIDtoPE(ga->loc.gc.gtid), ga->loc.gc.slot);
304 GALA *gala = (GALA *) lookupHashTable(pGAtoGALAtable, pga);
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);
310 gala->ga.weight += ga->weight;
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.
325 initGAtables(STG_NO_ARGS)
327 taskIDtoPEtable = allocHashTable();
328 LAtoGALAtable = allocHashTable();
329 pGAtoGALAtable = allocHashTable();
334 Rebuild the LA->GA table, assuming that the addresses in the GALAs are correct.
339 RebuildLAGAtable(STG_NO_ARGS)
343 /* The old LA->GA table is worthless */
344 freeHashTable(LAtoGALAtable, NULL);
345 LAtoGALAtable = allocHashTable();
347 for (gala = liveIndirections; gala != NULL; gala = gala->next) {
349 insertHashTable(LAtoGALAtable, (W_) gala->la, (void *) gala);
352 for (gala = liveRemoteGAs; gala != NULL; gala = gala->next) {
354 insertHashTable(LAtoGALAtable, (W_) gala->la, (void *) gala);
365 int pe_shift = (BITS_IN(W_)*3)/4;
366 int pe_bits = BITS_IN(W_) - pe_shift;
368 if ( pe_bits < 8 || slot >= (1L << pe_shift) ) { /* big trouble */
370 fprintf(stderr, "PackGA: slot# too big (%d) or not enough pe_bits (%d)\n",slot,pe_bits);
374 return((((W_)(pe)) << pe_shift) | ((W_)(slot)));
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).
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.
388 #endif /* PAR -- whole file */