Debian Codegraph @

dune/uggrid/parallel/ddd/ident/ident.cc

raw
1 // SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file LICENSE.md in module root
2 // SPDX-License-Identifier: LGPL-2.1-or-later
3 // -*- tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*-
4 // vi: set et ts=4 sw=2 sts=2:
5 /****************************************************************************/
6 /* */
7 /* File: ident.c */
8 /* */
9 /* Purpose: object identification for ddd module */
10 /* */
11 /* Author: Klaus Birken */
12 /* Rechenzentrum Uni Stuttgart */
13 /* Universitaet Stuttgart */
14 /* Allmandring 30 */
15 /* 70550 Stuttgart */
16 /* internet: [email protected] */
17 /* */
18 /* History: 93/11/30 kb begin */
19 /* 94/04/25 kb major revision, all Identfy-functions impl. */
20 /* 96/02/08 kb fixed bug in vchannel handling (due to T3D) */
21 /* 96/11/25 kb added indirect identification */
22 /* */
23 /* Remarks: */
24 /* */
25 /****************************************************************************/
26
27 #define DebugIdent 10 /* 10 is off */
28
29
30 /****************************************************************************/
31
32
33 /*
34 in debuglevel DebugIdentCons, additional data is sent with
35 the identify-messages, in order to check the consistency of
36 the identification tuples.
37
38 this is for configuring the debug actions only.
39 */
40 #define DebugIdentCons 8
41
42
43
44 /****************************************************************************/
45 /* */
46 /* include files */
47 /* system include files */
48 /* application include files */
49 /* */
50 /****************************************************************************/
51
52 /* standard C library */
53 #include <config.h>
54 #include <cstdlib>
55 #include <cstdio>
56 #include <cstring>
57
58 #include <algorithm>
59 #include <iomanip>
60 #include <iostream>
61 #include <iterator>
62 #include <tuple>
63
64 #include <dune/common/exceptions.hh>
65 #include <dune/common/stdstreams.hh>
66
67 #include <dune/uggrid/parallel/ddd/dddcontext.hh>
68
69 #include <dune/uggrid/parallel/ddd/dddi.h>
70 #include <dune/uggrid/parallel/ddd/basic/notify.h>
71 #include <dune/uggrid/parallel/ddd/basic/oopp.h> /* for object-orientated style via preprocessor */
72
73 USING_UG_NAMESPACE
74
75 /* PPIF namespace: */
76 using namespace PPIF;
77
78 namespace DDD {
79 namespace Ident {
80
81 /****************************************************************************/
82 /* */
83 /* defines in the following order */
84 /* */
85 /* compile time constants defining static data size (i.e. arrays) */
86 /* other constants */
87 /* macros */
88 /* */
89 /****************************************************************************/
90
91
92 /* types of IDENTINFO items, ID_OBJECT must be the smallest value!! */
93 #define ID_OBJECT 1
94 #define ID_NUMBER 2
95 #define ID_STRING 3
96
97
98 #define TUPLE_LEN(t) ((int)((t)&0x3f))
99
100
101 /* overall mode of identification */
102 enum class IdentMode : unsigned char {
103 IMODE_IDLE = 0, /* waiting for next DDD_IdentifyBegin() */
104 IMODE_CMDS, /* after DDD_IdentifyBegin(), before DDD_IdentifyEnd() */
105 IMODE_BUSY /* during DDD_IdentifyEnd() */
106 };
107
108
109
110 /***/
111
112 /* some macros for customizing oopp */
113 #define _NEWPARAMS
114 #define _NEWPARAMS_OR_VOID void
115
116 #define __INDENT(n) { int i; for(i=0; i<n; i++) fputs(" ",fp);}
117 #define _PRINTPARAMS , int indent, FILE *fp
118 #define _PRINTPARAMS_DEFAULT ,0,stdout
119 #define _INDENT __INDENT(indent)
120 #define _INDENT1 __INDENT(indent+1)
121 #define _INDENT2 __INDENT(indent+2)
122 #define _PRINTNEXT , indent+1, fp
123 #define _PRINTSAME , indent, fp
124
125
126 /* map memory allocation calls */
127 #define OO_Allocate std::malloc
128 #define OO_Free std::free
129
130
131 /* extra prefix for all xfer-related data structures and/or typedefs */
132 /*#define ClassPrefix*/
133
134
135
136 /*
137 NOTE: all container-classes from ooppcc.h are implemented in this
138 source file by setting the following define.
139 */
140 #define ContainerImplementation
141 #define _CHECKALLOC(ptr) assert(ptr!=NULL)
142
143
144 /****************************************************************************/
145 /* */
146 /* data structures */
147 /* */
148 /****************************************************************************/
149
150
151 /****************************************************************************/
152 /* IDENTIFIER: */
153 /****************************************************************************/
154
155 union IDENTIFIER {
156 int number;
157 char *string;
158 DDD_GID object;
159 };
160
161
162
163 /****************************************************************************/
164 /* MSGITEM: */
165 /****************************************************************************/
166
167 struct MSGITEM {
168 DDD_GID gid;
169 DDD_PRIO prio;
170
171 # if DebugIdent<=DebugIdentCons
172 unsigned long tuple; /* send tuple ID for checking consistency */
173 # endif
174
175 };
176
177
178
179 /****************************************************************************/
180 /* IDENTINFO: */
181 /****************************************************************************/
182
183 struct ID_TUPLE;
184
185 struct IDENTINFO {
186 int typeId;
187 int entry;
188 IDENTIFIER id;
189
190
191 MSGITEM msg; /* this item is sent to other procs */
192
193 DDD_HDR hdr;
194
195 ID_TUPLE *tuple;
196 };
197
198
199
200 /****************************************************************************/
201 /* ID_TUPLE: */
202 /****************************************************************************/
203
204 struct ID_REFDBY
205 {
206 IDENTINFO *by;
207 ID_REFDBY *next;
208 };
209
210
211 struct ID_TUPLE {
212 unsigned long tId;
213 IDENTINFO **infos;
214
215 int nObjIds; /* number of entries with typeID==ID_OBJECT */
216
217 int loi; /* level of indirection */
218 ID_REFDBY *refd; /* list of referencing IdEntries */
219 };
220
221
222 /****************************************************************************/
223 /* IdEntry: */
224 /****************************************************************************/
225
226
227 struct IdEntry {
228 IDENTINFO msg;
229 };
230
231 namespace {
232
233 /* define container class */
234 #define SegmListOf IdEntry
235 #define SegmSize 128
236 #include <dune/uggrid/parallel/ddd/basic/ooppcc.h>
237
238 } /* namespace */
239
240
241 /****************************************************************************/
242 /* ID_PLIST: */
243 /****************************************************************************/
244
245 struct ID_PLIST {
246 DDD_PROC proc;
247 int nEntries;
248 int nIdentObjs;
249
250 ID_PLIST *next;
251 IdEntrySegmList *entries;
252
253 IDENTINFO **local_ids;
254 ID_TUPLE *indexmap; /* index-mapping of local_ids array */
255
256 MSGITEM *msgin, *msgout;
257 msgid idin, idout;
258 };
259
260 } /* namespace Ident */
261 } /* namespace DDD */
262
263 /****************************************************************************/
264 /* */
265 /* routines */
266 /* */
267 /****************************************************************************/
268
269 START_UGDIM_NAMESPACE
270
271 using namespace DDD::Ident;
272
273 /****************************************************************************/
274 /*
275 management functions for IdentMode.
276
277 these functions control the mode the ident-module is
278 currently in. this is used for error detection, but
279 also for correct detection of coupling inconsistencies
280 and recovery.
281 */
282
283 static const char *IdentModeName(IdentMode mode)
284 {
285 switch(mode)
286 {
287 case IdentMode::IMODE_IDLE : return "idle-mode";
288 case IdentMode::IMODE_CMDS : return "commands-mode";
289 case IdentMode::IMODE_BUSY : return "busy-mode";
290 }
291 return "unknown-mode";
292 }
293
294
295 static void IdentSetMode(DDD::DDDContext& context, IdentMode mode)
296 {
297 context.identContext().identMode = mode;
298
299 # if DebugIdent<=8
300 Dune::dinfo << "IdentMode=" << IdentModeName(mode) << "\n";
301 # endif
302 }
303
304
305 static IdentMode IdentSuccMode(IdentMode mode)
306 {
307 switch(mode)
308 {
309 case IdentMode::IMODE_IDLE : return IdentMode::IMODE_CMDS;
310 case IdentMode::IMODE_CMDS : return IdentMode::IMODE_BUSY;
311 case IdentMode::IMODE_BUSY : return IdentMode::IMODE_IDLE;
312 }
313 DUNE_THROW(Dune::InvalidStateException, "invalid IdentMode");
314 }
315
316
317
318 /*
319 static int IdentMode (void)
320 {
321 return identMode;
322 }
323 */
324
325
326 static bool IdentActive(const DDD::DDDContext& context)
327 {
328 return context.identContext().identMode != IdentMode::IMODE_IDLE;
329 }
330
331
332 static bool IdentStepMode(DDD::DDDContext& context, IdentMode old)
333 {
334 auto& identMode = context.identContext().identMode;
335
336 if (identMode != old)
337 DUNE_THROW(Dune::Exception,
338 "wrong Ident-mode (currently in " << IdentModeName(identMode)
339 << ", expected " << IdentModeName(old) << ")");
340
341 IdentSetMode(context, IdentSuccMode(identMode));
342 return true;
343 }
344
345
346 /****************************************************************************/
347
348
349 static void PrintPList (ID_PLIST *plist)
350 {
351 using std::setw;
352 std::ostream& out = std::cout;
353
354 out << "PList proc=" << setw(4) << plist->proc
355 << " entries=" << setw(5) << plist->nEntries << "\n";
356 }
357
358
359
360 /****************************************************************************/
361
362
363 static int compareId (const IDENTINFO *el1, const IDENTINFO *el2)
364 {
365 int cmp;
366
367 /* first compare id type (NUMBER, STRING or OBJECT) */
368 if (el1->typeId < el2->typeId) return(-1);
369 if (el1->typeId > el2->typeId) return(1);
370
371
372 /* same typeIds, compare identification then */
373 switch (el1->typeId) {
374 case ID_NUMBER :
375 if (el1->id.number < el2->id.number) return(-1);
376 if (el1->id.number > el2->id.number) return(1);
377 break;
378
379 case ID_STRING :
380 cmp = strcmp(el1->id.string, el2->id.string);
381 if (cmp!=0) return(cmp);
382 break;
383
384 case ID_OBJECT :
385 if (el1->id.object < el2->id.object) return(-1);
386 if (el1->id.object > el2->id.object) return(1);
387 break;
388 }
389
390 return(0);
391 }
392
393
394
395 /****************************************************************************/
396
397 /*
398 two functions for sorting IdentifyXXX-requests into tuples:
399
400 sort_intoTuplesLists keeps order of IdentifyXXX-issueing by
401 application program, i.e., the ordering is relevant
402
403 sort_intoTuplesSets reorders the IdentifyXXX-items inside each
404 tuple itself;
405 at this level the ordering is done only by typeId, where
406 ID_OBJECT comes first. lateron the IdentifyObject-items will
407 be sorted according to their gid (for objects with loi==0)
408 or the index of the loi-1 object (for objects with loi>0)
409 */
410
411
412 static bool sort_intoTuplesLists(const IDENTINFO* a, const IDENTINFO* b)
413 {
414 /* sort according to (old) global ids */
415 /* if equal, keep ordering of input */
416 return std::tie(a->msg.gid, a->entry) < std::tie(b->msg.gid, b->entry);
417 }
418
419 static bool sort_intoTuplesSets(const IDENTINFO* a, const IDENTINFO* b)
420 {
421 /* sort according to (old) global ids */
422 /* if equal, sort according to identificator itself */
423 if (a->msg.gid < b->msg.gid)
424 return true;
425 else if (a->msg.gid > b->msg.gid)
426 return false;
427 else
428 return compareId(a, b) < 0;
429 }
430
431
432
433
434 /****************************************************************************/
435
436
437 static int sort_tupleOrder (const void *e1, const void *e2)
438 {
439 ID_TUPLE *el1, *el2;
440 int nIds;
441 DDD_HDR el1hdr, el2hdr;
442
443 el1 = (ID_TUPLE *) e1;
444 el2 = (ID_TUPLE *) e2;
445
446
447 /* sort according to tuple id */
448 if (el1->tId < el2->tId) return(-1);
449 if (el1->tId > el2->tId) return(1);
450
451 /* ids are equal, sort according tuple value */
452
453 /* recode tuple length from lowest 6 bits */
454 nIds = TUPLE_LEN(el1->tId);
455
456
457 /* compare until one tuple entry differs */
458 for (int i = 0; i < nIds; i++) {
459 int cmp = compareId(el1->infos[i], el2->infos[i]);
460 if (cmp != 0)
461 return(cmp);
462 }
463
464
465 /* if tuples are equal by all means up to now, we
466 sort according to DDD_TYPE of local object.
467 hence, we can identify two pairs of local objects with
468 the same tuple.
469 this has to be omitted if objects with different
470 types should be identifiable. KB 960814
471 */
472 el1hdr = el1->infos[0]->hdr;
473 el2hdr = el2->infos[0]->hdr;
474 if (OBJ_TYPE(el1hdr) < OBJ_TYPE(el2hdr)) return(-1);
475 if (OBJ_TYPE(el1hdr) > OBJ_TYPE(el2hdr)) return(1);
476
477
478 if (el1hdr!=el2hdr) {
479 /*
480 for(i=0; i<nIds; i++) {
481 printf("%4d: tuple[%d] %08x/%d %08x/%d (id/loi)\n",
482 me, i,
483 el1->infos[i]->id.object, el1->loi,
484 el2->infos[i]->id.object, el2->loi);
485 }
486 */
487
488 DUNE_THROW(Dune::Exception,
489 "same identification tuple for objects "
490 << OBJ_GID(el1hdr) << " and " << OBJ_GID(el2hdr));
491 }
492
493 return(0);
494 }
495
496
497 /****************************************************************************/
498
499 static void SetLOI (IDENTINFO *ii, int loi)
500 {
501 ID_REFDBY *rby;
502 ID_TUPLE *tuple = ii->tuple;
503
504 /*
505 printf("%4d: %08x SetLOI(%d, %d)\n", me, ii->msg.gid, loi, ii->loi);
506 */
507
508 /* set loi to maximum of current and new value */
509 tuple->loi = MAX(loi, tuple->loi);
510
511 /* primitive cycle detection */
512 if (tuple->loi > 64)
513 DUNE_THROW(Dune::Exception,
514 "IdentifyObject-cycle, objects "
515 << ii->msg.gid << " and " << ii->id.object);
516
517
518 for(rby=tuple->refd; rby!=NULL; rby=rby->next)
519 {
520 SetLOI(rby->by, loi+1);
521
522 /* TODO detection of cycles */
523 }
524 }
525
526
527
528 static void ResolveDependencies (
529 ID_TUPLE *tuples, int nTuples,
530 IDENTINFO **id, int nIds, int nIdentObjs)
531 {
532 int i, j;
533
534 if (nIdentObjs==0)
535 return;
536
537 std::vector<IDENTINFO*> refd;
538 refd.reserve(nIdentObjs);
539
540 /* build array of pointers to objects being used for identification */
541 std::copy_if(
542 id, id + nIds,
543 std::back_inserter(refd),
544 [](const IDENTINFO* ii) { return ii->typeId == ID_OBJECT; }
545 );
546 assert(refd.size() == nIdentObjs);
547
548 /* sort it according to GID of referenced objects */
549 std::sort(
550 refd.begin(), refd.end(),
551 [](const IDENTINFO* a, const IDENTINFO* b) {
552 return a->id.object < b->id.object;
553 });
554
555 /*
556 for(j=0; j<nIdentObjs; j++)
557 printf("%4d: DepObj %08x (from %08x)\n",
558 me, refd[j]->id.object, OBJ_GID(refd[j]->hdr));
559 */
560
561
562 for(i=0, j=0; i<nTuples; i++)
563 {
564 while (j<nIdentObjs &&
565 refd[j]->id.object < tuples[i].infos[0]->msg.gid)
566 j++;
567
568 while (j<nIdentObjs &&
569 refd[j]->id.object == tuples[i].infos[0]->msg.gid)
570 {
571 ID_REFDBY *rby = new ID_REFDBY;
572
573 /* remember that idp[i] is referenced by refd[j] */
574 rby->by = refd[j];
575 rby->next = tuples[i].refd;
576 tuples[i].refd = rby;
577
578 j++;
579 }
580 }
581
582
583 for(i=0; i<nTuples; i++)
584 {
585 ID_REFDBY *rby;
586
587 for(rby=tuples[i].refd; rby!=NULL; rby=rby->next)
588 {
589 /* if loi>0, this subtree has been loi-ed before */
590 if (tuples[i].loi==0)
591 SetLOI(rby->by, tuples[i].loi+1);
592 }
593 }
594
595
596 # if DebugIdent<=2
597 /* display */
598 for(i=0; i<nTuples; i++)
599 {
600 ID_REFDBY *rby;
601
602 printf("%08x has loi %d\n",
603 tuples[i].infos[0]->msg.gid, tuples[i].loi);
604
605 for(rby=tuples[i].refd; rby!=NULL; rby=rby->next)
606 {
607 printf("%08x referenced by %08x\n",
608 tuples[i].infos[0]->msg.gid, rby->by->msg.gid);
609 }
610 }
611 # endif
612 }
613
614
615
616 static void CleanupLOI (ID_TUPLE *tuples, int nTuples)
617 {
618 int i;
619
620 for(i=0; i<nTuples; i++)
621 {
622 ID_REFDBY *rby, *next=0;
623
624 for(rby=tuples[i].refd; rby!=NULL; rby=next)
625 {
626 next = rby->next;
627
628 /* TODO use freelists */
629 delete rby;
630 }
631 }
632 }
633
634
635 /****************************************************************************/
636
637
638 /*
639 tuple-id doesn't contain information about the data in
640 the tuple, it does only contain information about the
641 structure of a tuple!
642 */
643 static void TupleInit (ID_TUPLE *tuple, IDENTINFO **id, int nIds)
644 {
645 int i, nObjIds;
646 unsigned long tId;
647
648 /* init tuple auxiliary data */
649 tuple->loi = 0;
650 tuple->refd = NULL;
651
652
653 /* compute tuple id */
654 tId = 0;
655 nObjIds = 0;
656 for(i=0; i<nIds; i++)
657 {
658 tId = (tId<<2) | id[i]->typeId;
659
660 /* count entries with ID_OBJECT */
661 if (id[i]->typeId==ID_OBJECT)
662 nObjIds++;
663 }
664
665
666 /* code length of tuple into lowest 6 bits */
667 tId = (tId<<6) | nIds;
668
669 /* printf("%4d: compute tuple id = %08x\n", me, tId); */
670
671
672 /* insert tuple id, number of ID_OBJECT-entries, and link to
673 array of pointers to the tuple's IDENTINFO structs */
674 tuple->tId = tId;
675 tuple->nObjIds = nObjIds;
676 tuple->infos = id;
677
678
679 /* set link from IDENTINFOs to tuple */
680 for(i=0; i<nIds; i++)
681 {
682 id[i]->tuple = tuple;
683 }
684 }
685
686
687
688 static int IdentifySort (const DDD::DDDContext& context,
689 IDENTINFO **id, int nIds,
690 int nIdentObjs, MSGITEM *items_out, ID_TUPLE **indexmap_out,
691 DDD_PROC dest
692 )
693 {
694 int i, j, last, nTuples;
695 int keep_order_inside_tuple;
696
697
698 /* sort to recognize identification tuples */
699 /* in case of IDMODE_LISTS, the original ordering
700 inside each tuple is kept. for IDMODE_SETS, each tuple
701 is sorted according to the identificators themselves. */
702 STAT_RESET3;
703 switch (DDD_GetOption(context, OPT_IDENTIFY_MODE))
704 {
705 case IDMODE_LISTS :
706 std::sort(id, id + nIds, sort_intoTuplesLists);
707 keep_order_inside_tuple = true;
708 break;
709
710 case IDMODE_SETS :
711 std::sort(id, id + nIds, sort_intoTuplesSets);
712 keep_order_inside_tuple = false;
713 break;
714
715 default :
716 DUNE_THROW(Dune::Exception, "unknown OPT_IDENTIFY_MODE");
717 }
718 STAT_INCTIMER3(T_QSORT_TUPLE);
719
720
721 /* compute number of tuples and allocate tuple array */
722 for(i=0, last=0, nTuples=1; i<nIds; i++)
723 {
724 if (id[i]->msg.gid > id[last]->msg.gid)
725 {
726 nTuples++;
727 last=i;
728 }
729 }
730 ID_TUPLE* tuples = new ID_TUPLE[nTuples];
731
732 /* init tuples (e.g., compute tuple ids) */
733 for(i=0, last=0, j=0; i<nIds; i++)
734 {
735 if (id[i]->msg.gid > id[last]->msg.gid)
736 {
737 TupleInit(&(tuples[j]), &(id[last]), i-last);
738 j++;
739 last=i;
740 }
741 }
742 TupleInit(&(tuples[j]), &(id[last]), nIds-last);
743
744
745 /*
746 now, 'tuples' is an array of identification tuples,
747 sorted according the gid of the object the tuple has
748 been specified for.
749
750 i.e., in a more abstract way tuples is a list of object
751 gids which will be identified.
752 */
753
754 /* resolve dependencies caused by IdentifyObject,
755 and set level-of-indirection accordingly */
756 STAT_RESET3;
757 ResolveDependencies(tuples, nTuples, id, nIds, nIdentObjs);
758 STAT_INCTIMER3(T_RESOLVE_DEP);
759
760
761 /*
762 the setting for loi is used for the next sorting procedure,
763 first level of indirection comes first.
764 */
765
766 /* sort array for loi */
767 STAT_RESET3;
768 std::sort(
769 tuples, tuples + nTuples,
770 [](const ID_TUPLE& a, const ID_TUPLE& b) { return a.loi < b.loi; }
771 );
772 STAT_INCTIMER3(T_QSORT_LOI);
773
774
775 STAT_RESET3;
776 i=0; j=0;
777 do {
778 while (j<nTuples && tuples[i].loi==tuples[j].loi)
779 {
780 /* reorder because of changes in id.object */
781 if (! keep_order_inside_tuple)
782 {
783 std::sort(
784 tuples[j].infos, tuples[j].infos + tuples[j].nObjIds,
785 sort_intoTuplesSets
786 );
787 }
788 j++;
789 }
790
791 /* sort sub-array for tupleId, tupleValue */
792 if (j-i > 1)
793 qsort(tuples+i, j-i, sizeof(ID_TUPLE), sort_tupleOrder);
794
795 /* inherit index to tuples referencing this one */
796 while (i<j)
797 {
798 ID_REFDBY *rby;
799
800 for(rby=tuples[i].refd; rby!=NULL; rby=rby->next)
801 {
802 /* dont use gid of referenced object (because it
803 will be known only after identification), but its
804 position in the identification table instead! */
805
806 /*
807 printf("%4d: insertRef dest=%d loi=%d i=%d, %08x <- %08x\n",
808 me, dest, tuples[i].loi, i, OBJ_GID(tuples[i].infos[0]->hdr),
809 OBJ_GID(rby->by->hdr));
810 */
811
812
813 rby->by->id.object = i;
814
815 /* if the ordering is not significant, we must reorder
816 the tuple after this operation. (i.e., for IDMODE_SETS).
817 */
818 }
819
820 i++;
821 }
822 /* now i==j */
823
824 } while (i<nTuples);
825 STAT_INCTIMER3(T_BUILD_GRAPH);
826
827
828 /* construct array which will be sent actually */
829 STAT_RESET3;
830 for(j=0; j<nTuples; j++)
831 {
832 /*
833 int k;
834 */
835 # if DebugIdent<=1
836 printf("Ident dest=%d msg_idx[ %08x ] = %5d, loi=%d\n",
837 dest, tuples[j].infos[0]->msg.gid, j, tuples[j].loi);
838 # endif
839
840 /*
841 for(k=0;k<tuples[j].nObjIds;k++)
842 {
843 printf("%4d: msg_idx %d %08x\n", me,
844 k, tuples[j].infos[k]->id.object);
845 }
846 */
847
848
849
850 items_out[j] = tuples[j].infos[0]->msg;
851
852 # if DebugIdent<=DebugIdentCons
853 /* send additional data for cons-checking */
854 items_out[j].tuple = tuples[j].tId;
855 # endif
856 }
857 STAT_INCTIMER3(T_CONSTRUCT_ARRAY);
858
859
860 CleanupLOI(tuples, nTuples);
861
862 /* return indexmap table, in order to keep ordering of tuples */
863 /* note: this array has to be freed in the calling function! */
864 *indexmap_out = tuples;
865
866 return(nTuples);
867 }
868
869
870
871 static int InitComm(DDD::DDDContext& context, int nPartners)
872 {
873 auto& ctx = context.identContext();
874
875 ID_PLIST *plist;
876 int i, err;
877 DDD_PROC *partners = DDD_ProcArray(context);
878
879 /* fill partner processor numbers into array */
880 for(plist=ctx.thePLists, i=0; i<nPartners; i++, plist=plist->next)
881 partners[i] = plist->proc;
882
883 if (! IS_OK(DDD_GetChannels(context, nPartners)))
884 {
885 return(false);
886 }
887
888
889 /* initiate asynchronous receives and sends */
890 for(plist=ctx.thePLists; plist!=NULL; plist=plist->next)
891 {
892 long *len_adr;
893
894 plist->idin = RecvASync(context.ppifContext(), VCHAN_TO(context, plist->proc),
895 ((char *)plist->msgin) - sizeof(long),
896 sizeof(MSGITEM)*plist->nEntries + sizeof(long), &err);
897
898 /* store number of entries at beginning of message */
899 len_adr = (long *) (((char *)plist->msgout) - sizeof(long));
900 *len_adr = plist->nEntries;
901 plist->idout = SendASync(context.ppifContext(), VCHAN_TO(context, plist->proc),
902 ((char *)plist->msgout) - sizeof(long),
903 sizeof(MSGITEM)*plist->nEntries + sizeof(long), &err);
904 }
905
906 return(true);
907 }
908
909
910 /****************************************************************************/
911
912 /*
913 this routine checks whether number of idents per proc is indeed
914 pairwise consistent.
915 */
916
917 static void idcons_CheckPairs(DDD::DDDContext& context)
918 {
919 auto& ctx = context.identContext();
920
921 NOTIFY_DESC *msgs = DDD_NotifyBegin(context, ctx.nPLists);
922 ID_PLIST *plist;
923 int i, j, nRecvs, err=false;
924
925 for(i=0, plist=ctx.thePLists; plist!=NULL; plist=plist->next, i++)
926 {
927 msgs[i].proc = plist->proc;
928 msgs[i].size = plist->nEntries;
929 }
930
931 /* communicate */
932 nRecvs = DDD_Notify(context);
933 if (nRecvs==ERROR)
934 DUNE_THROW(Dune::Exception, "Notify failed in Ident-ConsCheck");
935
936
937 /* perform checking */
938 for(plist=ctx.thePLists; plist!=NULL; plist=plist->next)
939 {
940 for(j=0; j<nRecvs; j++)
941 {
942 if (msgs[j].proc==plist->proc)
943 break;
944 }
945
946 if (j==nRecvs)
947 {
948 Dune::dgrave << "Identify: no Ident-calls from proc " << plist->proc
949 << ", expected " << plist->nEntries << "\n";
950 err=true;
951 }
952 else if (msgs[j].size!=plist->nEntries)
953 {
954 Dune::dgrave << "Identify: " << msgs[j].size << " Ident-calls from proc "
955 << plist->proc << ", expected " << plist->nEntries << "\n";
956 err=true;
957 }
958 }
959
960 DDD_NotifyEnd(context);
961
962 if (err)
963 {
964 DUNE_THROW(Dune::Exception, "found errors in IdentifyEnd()");
965 }
966 else
967 {
968 Dune::dwarn << "Ident-ConsCheck level 0: ok\n";
969 }
970 }
971
972
973
974 /****************************************************************************/
975
976 /****************************************************************************/
977 /* */
978 /* Function: DDD_IdentifyEnd */
979 /* */
980 /****************************************************************************/
981
982 /**
983 End of identication phase.
984 This function starts the object identification process. After a call to
985 this function (on all processors) all {\bf Identify}-commands since the
986 last call to \funk{IdentifyBegin} are executed. This involves a set
987 of local communications between the processors.
988 */
989
990 DDD_RET DDD_IdentifyEnd(DDD::DDDContext& context)
991 {
992 auto& ctx = context.identContext();
993
994 ID_PLIST *plist, *pnext=NULL;
995 int cnt, j;
996
997 /* REMARK: dont use the id->msg.msg.prio fields until they
998 are explicitly set at line L1! */
999
1000 STAT_SET_MODULE(DDD_MODULE_IDENT);
1001 STAT_ZEROALL;
1002
1003 # if DebugIdent<=9
1004 printf("DDD_IdentifyEnd.\n");
1005 fflush(stdout);
1006 # endif
1007
1008 /* step mode and check whether call to IdentifyEnd is valid */
1009 if (!IdentStepMode(context, IdentMode::IMODE_CMDS))
1010 DUNE_THROW(Dune::Exception, "DDD_IdentifyEnd() aborted");
1011
1012
1013 # if DebugIdent<=9
1014 idcons_CheckPairs(context);
1015 # endif
1016
1017
1018 STAT_RESET1;
1019
1020 /* for each id_plist entry */
1021 for(plist=ctx.thePLists, cnt=0; plist!=NULL; plist=plist->next, cnt++)
1022 {
1023 /* allocate message buffers */
1024 /* use one alloc for three buffers */
1025 plist->local_ids = (IDENTINFO **) std::malloc(
1026 sizeof(IDENTINFO *)*plist->nEntries + /* for local id-infos */
1027 sizeof(long) + /* len of incoming msg */
1028 sizeof(MSGITEM) *plist->nEntries + /* for incoming msg */
1029 sizeof(long) + /* len of outgoing msg */
1030 sizeof(MSGITEM) *plist->nEntries /* for outgoing msg */
1031 );
1032
1033 if (plist->local_ids==NULL)
1034 throw std::bad_alloc();
1035
1036 plist->msgin = (MSGITEM *)
1037 (((char *)&plist->local_ids[plist->nEntries]) + sizeof(long));
1038 plist->msgout = (MSGITEM *)
1039 (((char *)&plist->msgin[plist->nEntries]) + sizeof(long));
1040
1041
1042 /* construct pointer array to IDENTINFO structs */
1043 /* AND: fill in current priority from object's header */
1044 {
1045 IdEntrySegm *li;
1046 int i = 0;
1047
1048 for(li=plist->entries->first; li!=NULL; li=li->next)
1049 {
1050 int entry;
1051 for(entry=0; entry<li->nItems; entry++)
1052 {
1053 IdEntry *id = &(li->data[entry]);
1054
1055 plist->local_ids[i] = &(id->msg);
1056 id->msg.msg.prio = OBJ_PRIO(id->msg.hdr); /* L1 */
1057 i++;
1058 }
1059 }
1060 }
1061
1062
1063 /* sort outgoing items */
1064 STAT_RESET2;
1065 plist->nEntries = IdentifySort(context,
1066 plist->local_ids, plist->nEntries,
1067 plist->nIdentObjs,
1068 plist->msgout, /* output: msgbuffer outgoing */
1069 &plist->indexmap, /* output: mapping of indices to local_ids array */
1070 plist->proc);
1071 STAT_INCTIMER2(T_PREPARE_SORT);
1072
1073
1074 # if DebugIdent<=5
1075 PrintPList(plist);
1076 # endif
1077 }
1078 STAT_TIMER1(T_PREPARE);
1079 STAT_SETCOUNT(N_PARTNERS, cnt);
1080
1081 /* initiate comm-channels and send/receive calls */
1082 STAT_RESET1;
1083 if (!InitComm(context, cnt))
1084 DUNE_THROW(Dune::Exception, "DDD_IdentifyEnd() aborted");
1085
1086
1087 /*
1088 each pair of processors now has a plist with one copy on
1089 each side. the actual OBJ_GID is computed as the minimum
1090 of the two local object ids on each processor.
1091 */
1092
1093 # if DebugIdent<=4
1094 printf("DDD_IdentifyEnd. PLists ready.\n"); fflush(stdout);
1095 # endif
1096
1097
1098 /* poll receives */
1099 for(plist=ctx.thePLists, j=0; j<cnt; )
1100 {
1101 if (plist->msgin!=NULL)
1102 {
1103 int ret;
1104
1105 if ((ret=InfoARecv(context.ppifContext(), VCHAN_TO(context, plist->proc), plist->idin))==1)
1106 {
1107 /* process single plist */
1108 MSGITEM *msgin = plist->msgin;
1109 ID_TUPLE *msgout = plist->indexmap;
1110
1111 /* check control data */
1112 long *len_adr = (long *) (((char *)msgin) - sizeof(long));
1113 if (*len_adr != plist->nEntries)
1114 DUNE_THROW(Dune::Exception,
1115 "Identify: " << ((int) *len_adr) << " identified objects"
1116 << " from proc " << plist->proc << ", expected "
1117 << plist->nEntries);
1118
1119 for (int i = 0; i < plist->nEntries; i++, msgin++, msgout++)
1120 {
1121 # if DebugIdent<=1
1122 printf("identifying %08x with %08x/%d to %08x\n",
1123 OBJ_GID(msgout->infos[0]->hdr), msgin->gid,
1124 plist->proc,
1125 MIN(OBJ_GID(msgout->infos[0]->hdr), msgin->gid));
1126 # endif
1127
1128 # if DebugIdent<=DebugIdentCons
1129 if (msgout->tId != msgin->tuple)
1130 {
1131 DUNE_THROW(Dune::Exception,
1132 "inconsistent tuples, gid "
1133 << OBJ_GID(msgout->infos[0]->hdr) << " on " << context.me()
1134 << ", gid " << msgin->gid << " on " << plist->proc);
1135 }
1136 # endif
1137
1138 /* compute new GID from minimum of both current GIDs */
1139 OBJ_GID(msgout->infos[0]->hdr) =
1140 MIN(OBJ_GID(msgout->infos[0]->hdr), msgin->gid);
1141
1142 /* add a coupling for new object copy */
1143 AddCoupling(context, msgout->infos[0]->hdr, plist->proc, msgin->prio);
1144 }
1145
1146 /* free indexmap (=tuple) array */
1147 delete[] plist->indexmap;
1148
1149 /* mark plist as finished */
1150 plist->msgin=NULL;
1151 j++;
1152 }
1153 else
1154 {
1155 if (ret==-1)
1156 DUNE_THROW(Dune::Exception,
1157 "couldn't receive message from " << plist->proc);
1158 }
1159 }
1160
1161 /* next plist, perhaps restart */
1162 plist=plist->next; if (plist==NULL) plist=ctx.thePLists;
1163 };
1164 STAT_TIMER1(T_COMM_AND_IDENT);
1165
1166 /* poll sends */
1167 for(plist=ctx.thePLists; plist!=0; plist=pnext)
1168 {
1169 pnext = plist->next;
1170
1171 /* wait for correct send and free buffer */
1172 while(InfoASend(context.ppifContext(), VCHAN_TO(context, plist->proc), plist->idout)!=1)
1173 ;
1174
1175 /* now, the plist->entries list isn't needed anymore, free */
1176 IdEntrySegmList_Free(plist->entries);
1177
1178 std::free(plist->local_ids);
1179 delete plist;
1180 };
1181
1182
1183 # if DebugIdent<=8
1184 printf("DDD_IdentifyEnd. Rebuilding interfaces.\n");
1185 fflush(stdout);
1186 # endif
1187
1188
1189
1190 /* rebuild interfaces after topological change */
1191 STAT_RESET1;
1192 IFAllFromScratch(context);
1193 STAT_TIMER1(T_BUILD_IF);
1194
1195
1196 # if DebugIdent<=9
1197 printf("DDD_IdentifyEnd. Ready.\n"); fflush(stdout);
1198 # endif
1199
1200 IdentStepMode(context, IdentMode::IMODE_BUSY);
1201
1202 return(DDD_RET_OK);
1203 }
1204
1205
1206
1207 /****************************************************************************/
1208
1209
1210 static IdEntry *IdentifyIdEntry(DDD::DDDContext& context, DDD_HDR hdr, DDD_PROC proc, int typeId)
1211 {
1212 auto& ctx = context.identContext();
1213
1214 IdEntry *id;
1215 ID_PLIST *plist;
1216
1217 /* check whether Identify-call is valid */
1218 if (!IdentActive(context))
1219 DUNE_THROW(Dune::Exception, "Missing DDD_IdentifyBegin(), aborted");
1220
1221 if (proc == context.me())
1222 DUNE_THROW(Dune::Exception,
1223 "cannot identify " << OBJ_GID(hdr) << " with myself");
1224
1225 if (proc >= context.procs())
1226 DUNE_THROW(Dune::Exception,
1227 "cannot identify " << OBJ_GID(hdr)
1228 << " with processor " << proc);
1229
1230
1231
1232 /* search current plist entries */
1233 for(plist=ctx.thePLists; plist!=NULL; plist=plist->next) {
1234 if (plist->proc==proc)
1235 break;
1236 }
1237
1238 if (plist==NULL)
1239 {
1240 /* get new id_plist record */
1241 plist = new ID_PLIST;
1242
1243 plist->proc = proc;
1244 plist->nEntries = 0;
1245 plist->entries = New_IdEntrySegmList();
1246 plist->nIdentObjs = 0;
1247 plist->next = ctx.thePLists;
1248 ctx.thePLists = plist;
1249 ctx.nPLists++;
1250 }
1251
1252
1253 /* insert into current plist */
1254 id = IdEntrySegmList_NewItem(plist->entries);
1255 id->msg.typeId = typeId;
1256 id->msg.hdr = hdr;
1257 id->msg.msg.gid = OBJ_GID(hdr);
1258
1259 plist->nEntries++;
1260 if (id->msg.typeId==ID_OBJECT) {
1261 plist->nIdentObjs++;
1262 }
1263
1264
1265 /* NOTE: priority can change between Identify-command and IdentifyEnd!
1266 therefore, scan priorities at the beginning of IdentifyEnd, and not
1267 here. KB 970730.
1268 id->msg.msg.prio = OBJ_PRIO(hdr);
1269 */
1270
1271 id->msg.entry = ctx.cntIdents++;
1272
1273 return(id);
1274 }
1275
1276
1277 /****************************************************************************/
1278 /* */
1279 /* Function: DDD_IdentifyNumber */
1280 /* */
1281 /****************************************************************************/
1282
1283 /**
1284 DDD Object identification via integer number.
1285 After an initial call to \funk{IdentifyBegin}, this function
1286 identifies two object copies on separate processors. It has to be
1287 called on both processors with the same identification value.
1288 The necessary actions (e.g. message transfer) are executed via the
1289 final call to \funk{IdentifyEnd}; therefore a whole set of
1290 \funk{Identify}-operations is accumulated.
1291
1292 After the identification both objects have the same DDD global
1293 object ID, which is build using the minimum of both local object IDs.
1294
1295 The identification specified here may be detailed even further by
1296 additional calls to {\bf Identify}-operations with the same
1297 local object. This will construct an identification tuple from
1298 all {\bf Identify}-commands for this local object.
1299
1300 @param hdr DDD local object which has to be identified with another object
1301 @param proc Owner (processor number) of corresponding local object. This processor has to issue a corresponding call to this {\bf DDD\_Identify}-function.
1302 @param ident Identification value. This is an arbitrary number to identify two corresponding operations on different processors.
1303 */
1304
1305 void DDD_IdentifyNumber(DDD::DDDContext& context, DDD_HDR hdr, DDD_PROC proc, int ident)
1306 {
1307 IdEntry *id;
1308
1309 id = IdentifyIdEntry(context, hdr, proc, ID_NUMBER);
1310 if (id==NULL)
1311 throw std::bad_alloc();
1312
1313 id->msg.id.number = ident;
1314
1315 #if DebugIdent<=2
1316 printf("%4d: IdentifyNumber %08x %02d with %4d num %d\n", context.me(),
1317 OBJ_GID(hdr), OBJ_TYPE(hdr), proc, id->msg.id.number);
1318 #endif
1319 }
1320
1321
1322 /****************************************************************************/
1323 /* */
1324 /* Function: DDD_IdentifyString */
1325 /* */
1326 /****************************************************************************/
1327
1328 /**
1329 DDD Object identification via character string.
1330 After an initial call to \funk{IdentifyBegin}, this function
1331 identifies two object copies on separate processors. It has to be
1332 called on both processors with the same identification string.
1333 The necessary actions (e.g. message transfer) are executed via the
1334 final call to \funk{IdentifyEnd}; therefore a whole set of
1335 \funk{Identify}-operations is accumulated.
1336
1337 After the identification both objects have the same DDD global
1338 object ID, which is build using the minimum of both local object IDs.
1339
1340 The identification specified here may be detailed even further by
1341 additional calls to {\bf Identify}-operations with the same
1342 local object. This will construct an identification tuple from
1343 all {\bf Identify}-commands for this local object.
1344
1345 @param hdr DDD local object which has to be identified with another object
1346 @param proc Owner (processor number) of corresponding local object. This processor has to issue a corresponding call to this {\bf DDD\_Identify}-function.
1347 @param ident Identification value. This is an arbitrary string to identify two corresponding operations on different processors.
1348 */
1349
1350 void DDD_IdentifyString(DDD::DDDContext& context, DDD_HDR hdr, DDD_PROC proc, char *ident)
1351 {
1352 IdEntry *id;
1353
1354 id = IdentifyIdEntry(context, hdr, proc, ID_STRING);
1355 if (id==NULL)
1356 throw std::bad_alloc();
1357
1358 id->msg.id.string = ident;
1359
1360 #if DebugIdent<=2
1361 printf("%4d: IdentifyString %08x %02d with %4d str %s\n", context.me(),
1362 OBJ_GID(hdr), OBJ_TYPE(hdr), proc, id->msg.id.string);
1363 #endif
1364 }
1365
1366
1367
1368 /****************************************************************************/
1369 /* */
1370 /* Function: DDD_IdentifyObject */
1371 /* */
1372 /****************************************************************************/
1373
1374 /**
1375 DDD Object identification via another DDD Object.
1376 After an initial call to \funk{IdentifyBegin}, this function
1377 identifies two object copies on separate processors. It has to be
1378 called on both processors with the same identification object.
1379 The necessary actions (e.g. message transfer) are executed via the
1380 final call to \funk{IdentifyEnd}; therefore a whole set of
1381 \funk{Identify}-operations is accumulated.
1382
1383 After the identification both objects have the same DDD global
1384 object ID, which is build using the minimum of both local object IDs.
1385
1386 The identification object {\em ident} must be either a distributed
1387 object known to both processors issuing the \funk{IdentifyObject}-command
1388 or a local object which is not known to these two processors, but which
1389 will also be identified during the current {\bf Identify}-process.
1390
1391 The identification specified here may be detailed even further by
1392 additional calls to {\bf Identify}-operations with the same
1393 local object. This will construct an identification tuple from
1394 all {\bf Identify}-commands for this local object.
1395
1396 @param hdr DDD local object which has to be identified with another object
1397 @param proc Owner (processor number) of corresponding local object. This processor has to issue a corresponding call to this {\bf DDD\_Identify}-function.
1398 @param ident Identification object. This is an arbitrary global object which is known to both processors involved to identify the two corresponding operations on these processors.
1399 */
1400
1401 void DDD_IdentifyObject(DDD::DDDContext& context, DDD_HDR hdr, DDD_PROC proc, DDD_HDR ident)
1402 {
1403 IdEntry *id;
1404
1405 id = IdentifyIdEntry(context, hdr, proc, ID_OBJECT);
1406 if (id==NULL)
1407 throw std::bad_alloc();
1408
1409 /* use OBJ_GID as estimate for identification value, this estimate
1410 might be replaced when the corresponding object is identified
1411 itself. then its index in the identify-message will be used.
1412 remember identification value in order to replace above estimate,
1413 if necessary (i.e., remember ptr to ddd-hdr) */
1414 id->msg.id.object = OBJ_GID(ident);
1415
1416 #if DebugIdent<=2
1417 printf("%4d: IdentifyObject %08x %02d with %4d gid %08x\n", context.me(),
1418 OBJ_GID(hdr), OBJ_TYPE(hdr), proc, id->msg.id.object);
1419 #endif
1420 }
1421
1422
1423
1424 /****************************************************************************/
1425 /* */
1426 /* Function: DDD_IdentifyBegin */
1427 /* */
1428 /****************************************************************************/
1429
1430 /**
1431 Begin identification phase.
1432 A call to this function establishes a global identification operation.
1433 It should be issued on all processors. After this call an arbitrary
1434 series of {\bf Identify}-commands may be issued. The global
1435 identification operation is carried out via a \funk{IdentifyEnd}
1436 call on each processor.
1437
1438 All identification commands given for one local object will be collected
1439 into an {\em identification tuple}. Thus, object identificators can be
1440 constructed from several simple identification calls. DDD option
1441 #IDENTIFY_MODE# may be set before the \funk{IdentifyEnd} call
1442 in order to specify how the order of simple identificators is
1443 handled for each complex identification tuple:
1444
1445 \begin{description}
1446 \item[#IDMODE_LISTS#:]%
1447 The order of all identification commands for one local object is kept.
1448 Both processors with corresponding complex identificators must issue
1449 the identification commands in the same order.
1450 %
1451 \item[#IDMODE_SETS#:]%
1452 The order of all identification commands for one local object is
1453 not relevant. The DDD identification module sorts the commands
1454 inside each complex identificator. Both processors with corresponding
1455 identification tuples may issue the identification commands in any
1456 order.
1457 \end{description}
1458 */
1459
1460 void DDD_IdentifyBegin(DDD::DDDContext& context)
1461 {
1462 auto& ctx = context.identContext();
1463
1464 /* step mode and check whether call to IdentifyBegin is valid */
1465 if (!IdentStepMode(context, IdentMode::IMODE_IDLE))
1466 DUNE_THROW(Dune::Exception, "DDD_IdentifyBegin() aborted");
1467
1468 ctx.thePLists = nullptr;
1469 ctx.nPLists = 0;
1470 ctx.cntIdents = 0;
1471 }
1472
1473
1474 /****************************************************************************/
1475
1476
1477 void ddd_IdentInit(DDD::DDDContext& context)
1478 {
1479 IdentSetMode(context, IdentMode::IMODE_IDLE);
1480 }
1481
1482
1483 void ddd_IdentExit(DDD::DDDContext&)
1484 {}
1485
1486 /****************************************************************************/
1487
1488 END_UGDIM_NAMESPACE