GNUnet  0.11.x
gnunet-service-consensus.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2012, 2013, 2017, 2020 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
25 #include "platform.h"
26 #include "gnunet_util_lib.h"
27 #include "gnunet_block_lib.h"
28 #include "gnunet_protocols.h"
29 #include "gnunet_applications.h"
30 #include "gnunet_set_service.h"
33 #include "consensus_protocol.h"
34 #include "consensus.h"
35 
36 
38 {
43  VOTE_STAY = 0,
47  VOTE_ADD = 1,
52 };
53 
54 
56 {
60 };
61 
62 
64 {
78 };
79 
80 
81 enum SetKind
82 {
91 };
92 
94 {
99 };
100 
102 {
107 };
108 
109 
111 
115 struct TaskKey
116 {
120  uint16_t kind GNUNET_PACKED;
121 
127 
132 
137 
144 };
145 
146 
147 struct SetKey
148 {
149  enum SetKind set_kind GNUNET_PACKED;
158 };
159 
160 
161 struct SetEntry
162 {
163  struct SetKey key;
165 
171 };
172 
173 
174 struct DiffKey
175 {
176  enum DiffKind diff_kind GNUNET_PACKED;
177 
179 
181 };
182 
183 struct RfnKey
184 {
185  enum RfnKind rfn_kind GNUNET_PACKED;
188 };
189 
190 
192 
193 
194 struct SetOpCls
195 {
196  struct SetKey input_set;
197 
198  struct SetKey output_set;
199  struct RfnKey output_rfn;
200  struct DiffKey output_diff;
201 
203 
205 
207 };
208 
209 
210 struct FinishCls
211 {
212  struct SetKey input_set;
213 };
214 
220 {
221  struct SetOpCls setop;
222  struct FinishCls finish;
223 };
224 
225 
226 struct TaskEntry;
227 
228 
229 typedef void
230 (*TaskFunc) (struct TaskEntry *task);
231 
232 
233 /*
234  * Node in the consensus task graph.
235  */
236 struct TaskEntry
237 {
238  struct TaskKey key;
239 
240  struct Step *step;
241 
243 
245 
248 
249  union TaskFuncCls cls;
250 };
251 
252 
253 struct Step
254 {
259  struct Step *prev;
260 
265  struct Step *next;
266 
268 
272  struct TaskEntry **tasks;
273  unsigned int tasks_len;
274  unsigned int tasks_cap;
275 
276  unsigned int finished_tasks;
277 
278  /*
279  * Tasks that have this task as dependency.
280  *
281  * We store pointers to subordinates rather
282  * than to prerequisites since it makes
283  * tracking the readiness of a task easier.
284  */
285  struct Step **subordinates;
286  unsigned int subordinates_len;
287  unsigned int subordinates_cap;
288 
293 
298 
299  unsigned int is_running;
300 
301  unsigned int is_finished;
302 
306  unsigned int round;
307 
311  char *debug_name;
312 
322 };
323 
324 
326 {
328 
332  int *votes;
333 
337  enum ReferendumVote proposal;
338 };
339 
340 
342 {
343  struct RfnKey key;
344 
345  /*
346  * Elements where there is at least one proposed change.
347  *
348  * Maps the hash of the GNUNET_SET_Element
349  * to 'struct RfnElementInfo'.
350  */
352 
353  unsigned int num_peers;
354 
366 
367 
374 };
375 
376 
378 {
380 
385  int weight;
386 };
387 
388 
392 struct DiffEntry
393 {
394  struct DiffKey key;
396 };
397 
398 struct SetHandle
399 {
400  struct SetHandle *prev;
401  struct SetHandle *next;
402 
404 };
405 
406 
411 {
416 
421 
423 
427 
432 
433  /*
434  * Mapping from (hashed) TaskKey to TaskEntry.
435  *
436  * We map the application_id for a round to the task that should be
437  * executed, so we don't have to go through all task whenever we get
438  * an incoming set op request.
439  */
441 
442  struct Step *steps_head;
443  struct Step *steps_tail;
444 
446 
448 
453  struct GNUNET_HashCode global_id;
454 
459 
464 
468  struct GNUNET_TIME_Absolute conclude_start;
469 
475  struct GNUNET_TIME_Absolute conclude_deadline;
476 
478 
482  unsigned int num_peers;
483 
487  unsigned int local_peer_idx;
488 
494 
499 
503  uint64_t first_size;
504 
506 
510  uint64_t lower_bound;
511 
514 };
515 
520 
525 
529 static const struct GNUNET_CONFIGURATION_Handle *cfg;
530 
535 
540 
541 
542 static void
543 finish_task (struct TaskEntry *task);
544 
545 
546 static void
547 run_ready_steps (struct ConsensusSession *session);
548 
549 
550 static const char *
551 phasename (uint16_t phase)
552 {
553  switch (phase)
554  {
555  case PHASE_KIND_ALL_TO_ALL: return "ALL_TO_ALL";
556 
557  case PHASE_KIND_ALL_TO_ALL_2: return "ALL_TO_ALL_2";
558 
559  case PHASE_KIND_FINISH: return "FINISH";
560 
561  case PHASE_KIND_GRADECAST_LEADER: return "GRADECAST_LEADER";
562 
563  case PHASE_KIND_GRADECAST_ECHO: return "GRADECAST_ECHO";
564 
565  case PHASE_KIND_GRADECAST_ECHO_GRADE: return "GRADECAST_ECHO_GRADE";
566 
567  case PHASE_KIND_GRADECAST_CONFIRM: return "GRADECAST_CONFIRM";
568 
569  case PHASE_KIND_GRADECAST_CONFIRM_GRADE: return "GRADECAST_CONFIRM_GRADE";
570 
571  case PHASE_KIND_APPLY_REP: return "APPLY_REP";
572 
573  default: return "(unknown)";
574  }
575 }
576 
577 
578 static const char *
579 setname (uint16_t kind)
580 {
581  switch (kind)
582  {
583  case SET_KIND_CURRENT: return "CURRENT";
584 
585  case SET_KIND_LEADER_PROPOSAL: return "LEADER_PROPOSAL";
586 
587  case SET_KIND_NONE: return "NONE";
588 
589  default: return "(unknown)";
590  }
591 }
592 
593 
594 static const char *
595 rfnname (uint16_t kind)
596 {
597  switch (kind)
598  {
599  case RFN_KIND_NONE: return "NONE";
600 
601  case RFN_KIND_ECHO: return "ECHO";
602 
603  case RFN_KIND_CONFIRM: return "CONFIRM";
604 
605  default: return "(unknown)";
606  }
607 }
608 
609 
610 static const char *
611 diffname (uint16_t kind)
612 {
613  switch (kind)
614  {
615  case DIFF_KIND_NONE: return "NONE";
616 
617  case DIFF_KIND_LEADER_CONSENSUS: return "LEADER_CONSENSUS";
618 
619  case DIFF_KIND_GRADECAST_RESULT: return "GRADECAST_RESULT";
620 
621  case DIFF_KIND_LEADER_PROPOSAL: return "LEADER_PROPOSAL";
622 
623  default: return "(unknown)";
624  }
625 }
626 
627 
628 #ifdef GNUNET_EXTRA_LOGGING
629 
630 
631 static const char *
632 debug_str_element (const struct GNUNET_SET_Element *el)
633 {
634  struct GNUNET_HashCode hash;
635 
636  GNUNET_SET_element_hash (el, &hash);
637 
638  return GNUNET_h2s (&hash);
639 }
640 
641 
642 static const char *
643 debug_str_task_key (const struct TaskKey *tk)
644 {
645  static char buf[256];
646 
647  snprintf (buf, sizeof(buf),
648  "TaskKey kind=%s, p1=%d, p2=%d, l=%d, rep=%d",
649  phasename (tk->kind), tk->peer1, tk->peer2,
650  tk->leader, tk->repetition);
651 
652  return buf;
653 }
654 
655 
656 static const char *
657 debug_str_diff_key (const struct DiffKey *dk)
658 {
659  static char buf[256];
660 
661  snprintf (buf, sizeof(buf),
662  "DiffKey kind=%s, k1=%d, k2=%d",
663  diffname (dk->diff_kind), dk->k1, dk->k2);
664 
665  return buf;
666 }
667 
668 
669 static const char *
670 debug_str_set_key (const struct SetKey *sk)
671 {
672  static char buf[256];
673 
674  snprintf (buf, sizeof(buf),
675  "SetKey kind=%s, k1=%d, k2=%d",
676  setname (sk->set_kind),
677  sk->k1,
678  sk->k2);
679  return buf;
680 }
681 
682 
683 static const char *
684 debug_str_rfn_key (const struct RfnKey *rk)
685 {
686  static char buf[256];
687 
688  snprintf (buf, sizeof(buf),
689  "RfnKey kind=%s, k1=%d, k2=%d",
690  rfnname (rk->rfn_kind),
691  rk->k1,
692  rk->k2);
693  return buf;
694 }
695 
696 
697 #endif /* GNUNET_EXTRA_LOGGING */
698 
699 
709 static int
711  const struct GNUNET_SET_Element *element)
712 {
713  struct TaskEntry *task = (struct TaskEntry *) cls;
714  struct ConsensusSession *session = task->step->session;
715  struct GNUNET_MQ_Envelope *ev;
716 
717  if (NULL != element)
718  {
720  const struct ConsensusElement *ce;
721 
723  element->element_type);
724  ce = element->data;
725 
726  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "marker is %u\n",
727  (unsigned) ce->marker);
728 
729  if (0 != ce->marker)
730  return GNUNET_YES;
731 
733  "P%d: sending element %s to client\n",
734  session->local_peer_idx,
735  debug_str_element (element));
736 
737  ev = GNUNET_MQ_msg_extra (m,
738  element->size - sizeof(struct ConsensusElement),
740  m->element_type = ce->payload_type;
741  GNUNET_memcpy (&m[1],
742  &ce[1],
743  element->size - sizeof(struct ConsensusElement));
744  GNUNET_MQ_send (session->client_mq,
745  ev);
746  }
747  else
748  {
750  "P%d: finished iterating elements for client\n",
751  session->local_peer_idx);
752  ev = GNUNET_MQ_msg_header (
754  GNUNET_MQ_send (session->client_mq,
755  ev);
756  }
757  return GNUNET_YES;
758 }
759 
760 
761 static struct SetEntry *
762 lookup_set (struct ConsensusSession *session,
763  const struct SetKey *key)
764 {
765  struct GNUNET_HashCode hash;
766 
768  "P%u: looking up set {%s}\n",
769  session->local_peer_idx,
770  debug_str_set_key (key));
771 
773  GNUNET_CRYPTO_hash (key,
774  sizeof(struct SetKey),
775  &hash);
776  return GNUNET_CONTAINER_multihashmap_get (session->setmap,
777  &hash);
778 }
779 
780 
781 static struct DiffEntry *
782 lookup_diff (struct ConsensusSession *session,
783  const struct DiffKey *key)
784 {
785  struct GNUNET_HashCode hash;
786 
788  "P%u: looking up diff {%s}\n",
789  session->local_peer_idx,
790  debug_str_diff_key (key));
792  GNUNET_CRYPTO_hash (key,
793  sizeof(struct DiffKey),
794  &hash);
796  &hash);
797 }
798 
799 
800 static struct ReferendumEntry *
801 lookup_rfn (struct ConsensusSession *session,
802  const struct RfnKey *key)
803 {
804  struct GNUNET_HashCode hash;
805 
807  "P%u: looking up rfn {%s}\n",
808  session->local_peer_idx,
809  debug_str_rfn_key (key));
811  GNUNET_CRYPTO_hash (key,
812  sizeof(struct RfnKey),
813  &hash);
814  return GNUNET_CONTAINER_multihashmap_get (session->rfnmap,
815  &hash);
816 }
817 
818 
819 static void
820 diff_insert (struct DiffEntry *diff,
821  int weight,
822  const struct GNUNET_SET_Element *element)
823 {
824  struct DiffElementInfo *di;
825  struct GNUNET_HashCode hash;
826 
827  GNUNET_assert ((1 == weight) || (-1 == weight));
828 
830  "diff_insert with element size %u\n",
831  element->size);
832 
834  "hashing element\n");
835 
836  GNUNET_SET_element_hash (element, &hash);
837 
839  "hashed element\n");
840 
841  di = GNUNET_CONTAINER_multihashmap_get (diff->changes, &hash);
842 
843  if (NULL == di)
844  {
845  di = GNUNET_new (struct DiffElementInfo);
846  di->element = GNUNET_SET_element_dup (element);
849  &hash,
850  di,
852  }
853 
854  di->weight = weight;
855 }
856 
857 
858 static void
860  uint16_t commit_peer)
861 {
862  GNUNET_assert (commit_peer < rfn->num_peers);
863 
864  rfn->peer_commited[commit_peer] = GNUNET_YES;
865 }
866 
867 
868 static void
870  uint16_t contested_peer)
871 {
872  GNUNET_assert (contested_peer < rfn->num_peers);
873 
874  rfn->peer_contested[contested_peer] = GNUNET_YES;
875 }
876 
877 
878 static uint16_t
880 {
881  uint16_t ret;
882 
883  ret = 0;
884  for (uint16_t i = 0; i < rfn->num_peers; i++)
885  if ((GNUNET_YES == rfn->peer_commited[i]) && (GNUNET_NO ==
886  rfn->peer_contested[i]))
887  ret++;
888 
889  return ret;
890 }
891 
892 
893 static void
895  uint16_t voting_peer,
896  enum ReferendumVote vote,
897  const struct GNUNET_SET_Element *element)
898 {
899  struct RfnElementInfo *ri;
900  struct GNUNET_HashCode hash;
901 
902  GNUNET_assert (voting_peer < rfn->num_peers);
903 
904  /* Explicit voting only makes sense with VOTE_ADD or VOTE_REMOTE,
905  since VOTE_KEEP is implicit in not voting. */
906  GNUNET_assert ((VOTE_ADD == vote) || (VOTE_REMOVE == vote));
907 
908  GNUNET_SET_element_hash (element, &hash);
910 
911  if (NULL == ri)
912  {
913  ri = GNUNET_new (struct RfnElementInfo);
914  ri->element = GNUNET_SET_element_dup (element);
915  ri->votes = GNUNET_new_array (rfn->num_peers, int);
918  &hash, ri,
920  }
921 
922  ri->votes[voting_peer] = GNUNET_YES;
923  ri->proposal = vote;
924 }
925 
926 
927 static uint16_t
929 {
930  uint16_t me = task->step->session->local_peer_idx;
931 
932  if (task->key.peer1 == me)
933  return task->key.peer2;
934  return task->key.peer1;
935 }
936 
937 
938 static int
939 cmp_uint64_t (const void *pa, const void *pb)
940 {
941  uint64_t a = *(uint64_t *) pa;
942  uint64_t b = *(uint64_t *) pb;
943 
944  if (a == b)
945  return 0;
946  if (a < b)
947  return -1;
948  return 1;
949 }
950 
951 
961 static void
962 set_result_cb (void *cls,
963  const struct GNUNET_SET_Element *element,
964  uint64_t current_size,
966 {
967  struct TaskEntry *task = cls;
968  struct ConsensusSession *session = task->step->session;
969  struct SetEntry *output_set = NULL;
970  struct DiffEntry *output_diff = NULL;
971  struct ReferendumEntry *output_rfn = NULL;
972  unsigned int other_idx;
973  struct SetOpCls *setop;
974  const struct ConsensusElement *consensus_element = NULL;
975 
976  if (NULL != element)
977  {
979  "P%u: got element of type %u, status %u\n",
980  session->local_peer_idx,
981  (unsigned) element->element_type,
982  (unsigned) status);
984  element->element_type);
985  consensus_element = element->data;
986  }
987 
988  setop = &task->cls.setop;
989 
990 
992  "P%u: got set result for {%s}, status %u\n",
993  session->local_peer_idx,
994  debug_str_task_key (&task->key),
995  status);
996 
997  if (GNUNET_NO == task->is_started)
998  {
999  GNUNET_break_op (0);
1000  return;
1001  }
1002 
1003  if (GNUNET_YES == task->is_finished)
1004  {
1005  GNUNET_break_op (0);
1006  return;
1007  }
1008 
1009  other_idx = task_other_peer (task);
1010 
1011  if (SET_KIND_NONE != setop->output_set.set_kind)
1012  {
1013  output_set = lookup_set (session,
1014  &setop->output_set);
1015  GNUNET_assert (NULL != output_set);
1016  }
1017 
1018  if (DIFF_KIND_NONE != setop->output_diff.diff_kind)
1019  {
1020  output_diff = lookup_diff (session, &setop->output_diff);
1021  GNUNET_assert (NULL != output_diff);
1022  }
1023 
1024  if (RFN_KIND_NONE != setop->output_rfn.rfn_kind)
1025  {
1026  output_rfn = lookup_rfn (session, &setop->output_rfn);
1027  GNUNET_assert (NULL != output_rfn);
1028  }
1029 
1030  if (GNUNET_YES == session->peers_blacklisted[other_idx])
1031  {
1032  /* Peer might have been blacklisted
1033  by a gradecast running in parallel, ignore elements from now */
1034  if (GNUNET_SET_STATUS_ADD_LOCAL == status)
1035  return;
1036  if (GNUNET_SET_STATUS_ADD_REMOTE == status)
1037  return;
1038  }
1039 
1040  if ((NULL != consensus_element) && (0 != consensus_element->marker))
1041  {
1043  "P%u: got some marker\n",
1044  session->local_peer_idx);
1045  if ((GNUNET_YES == setop->transceive_contested) &&
1046  (CONSENSUS_MARKER_CONTESTED == consensus_element->marker))
1047  {
1048  GNUNET_assert (NULL != output_rfn);
1049  rfn_contest (output_rfn, task_other_peer (task));
1050  return;
1051  }
1052 
1053  if (CONSENSUS_MARKER_SIZE == consensus_element->marker)
1054  {
1056  "P%u: got size marker\n",
1057  session->local_peer_idx);
1058 
1059 
1060  struct ConsensusSizeElement *cse = (void *) consensus_element;
1061 
1062  if (cse->sender_index == other_idx)
1063  {
1064  if (NULL == session->first_sizes_received)
1065  session->first_sizes_received = GNUNET_new_array (session->num_peers,
1066  uint64_t);
1067  session->first_sizes_received[other_idx] = GNUNET_ntohll (cse->size);
1068 
1069  uint64_t *copy = GNUNET_memdup (session->first_sizes_received,
1070  sizeof(uint64_t) * session->num_peers);
1071  qsort (copy, session->num_peers, sizeof(uint64_t), cmp_uint64_t);
1072  session->lower_bound = copy[session->num_peers / 3 + 1];
1074  "P%u: lower bound %llu\n",
1075  session->local_peer_idx,
1076  (long long) session->lower_bound);
1077  GNUNET_free (copy);
1078  }
1079  return;
1080  }
1081 
1082  return;
1083  }
1084 
1085  switch (status)
1086  {
1088  GNUNET_assert (NULL != consensus_element);
1090  "Adding element in Task {%s}\n",
1091  debug_str_task_key (&task->key));
1092  if (NULL != output_set)
1093  {
1094  // FIXME: record pending adds, use callback
1095  GNUNET_SET_add_element (output_set->h,
1096  element,
1097  NULL,
1098  NULL);
1099 #ifdef GNUNET_EXTRA_LOGGING
1101  "P%u: adding element %s into set {%s} of task {%s}\n",
1102  session->local_peer_idx,
1103  debug_str_element (element),
1104  debug_str_set_key (&setop->output_set),
1105  debug_str_task_key (&task->key));
1106 #endif
1107  }
1108  if (NULL != output_diff)
1109  {
1110  diff_insert (output_diff, 1, element);
1111 #ifdef GNUNET_EXTRA_LOGGING
1113  "P%u: adding element %s into diff {%s} of task {%s}\n",
1114  session->local_peer_idx,
1115  debug_str_element (element),
1116  debug_str_diff_key (&setop->output_diff),
1117  debug_str_task_key (&task->key));
1118 #endif
1119  }
1120  if (NULL != output_rfn)
1121  {
1122  rfn_vote (output_rfn, task_other_peer (task), VOTE_ADD, element);
1123 #ifdef GNUNET_EXTRA_LOGGING
1125  "P%u: adding element %s into rfn {%s} of task {%s}\n",
1126  session->local_peer_idx,
1127  debug_str_element (element),
1128  debug_str_rfn_key (&setop->output_rfn),
1129  debug_str_task_key (&task->key));
1130 #endif
1131  }
1132  // XXX: add result to structures in task
1133  break;
1134 
1136  GNUNET_assert (NULL != consensus_element);
1137  if (GNUNET_YES == setop->do_not_remove)
1138  break;
1139  if (CONSENSUS_MARKER_CONTESTED == consensus_element->marker)
1140  break;
1142  "Removing element in Task {%s}\n",
1143  debug_str_task_key (&task->key));
1144  if (NULL != output_set)
1145  {
1146  // FIXME: record pending adds, use callback
1147  GNUNET_SET_remove_element (output_set->h,
1148  element,
1149  NULL,
1150  NULL);
1151 #ifdef GNUNET_EXTRA_LOGGING
1153  "P%u: removing element %s from set {%s} of task {%s}\n",
1154  session->local_peer_idx,
1155  debug_str_element (element),
1156  debug_str_set_key (&setop->output_set),
1157  debug_str_task_key (&task->key));
1158 #endif
1159  }
1160  if (NULL != output_diff)
1161  {
1162  diff_insert (output_diff, -1, element);
1163 #ifdef GNUNET_EXTRA_LOGGING
1165  "P%u: removing element %s from diff {%s} of task {%s}\n",
1166  session->local_peer_idx,
1167  debug_str_element (element),
1168  debug_str_diff_key (&setop->output_diff),
1169  debug_str_task_key (&task->key));
1170 #endif
1171  }
1172  if (NULL != output_rfn)
1173  {
1174  rfn_vote (output_rfn, task_other_peer (task), VOTE_REMOVE, element);
1175 #ifdef GNUNET_EXTRA_LOGGING
1177  "P%u: removing element %s from rfn {%s} of task {%s}\n",
1178  session->local_peer_idx,
1179  debug_str_element (element),
1180  debug_str_rfn_key (&setop->output_rfn),
1181  debug_str_task_key (&task->key));
1182 #endif
1183  }
1184  break;
1185 
1187  // XXX: check first if any changes to the underlying
1188  // set are still pending
1190  "P%u: Finishing setop in Task {%s} (%u/%u)\n",
1191  session->local_peer_idx,
1192  debug_str_task_key (&task->key),
1193  (unsigned int) task->step->finished_tasks,
1194  (unsigned int) task->step->tasks_len);
1195  if (NULL != output_rfn)
1196  {
1197  rfn_commit (output_rfn, task_other_peer (task));
1198  }
1199  if (PHASE_KIND_ALL_TO_ALL == task->key.kind)
1200  {
1201  session->first_size = current_size;
1202  }
1203  finish_task (task);
1204  break;
1205 
1207  // XXX: cleanup
1208  GNUNET_break_op (0);
1209  finish_task (task);
1210  return;
1211 
1212  default:
1213  /* not reached */
1214  GNUNET_assert (0);
1215  }
1216 }
1217 
1218 
1219 #ifdef EVIL
1220 
1221 enum EvilnessType
1222 {
1223  EVILNESS_NONE,
1224  EVILNESS_CRAM_ALL,
1225  EVILNESS_CRAM_LEAD,
1226  EVILNESS_CRAM_ECHO,
1227  EVILNESS_SLACK,
1228  EVILNESS_SLACK_A2A,
1229 };
1230 
1231 enum EvilnessSubType
1232 {
1233  EVILNESS_SUB_NONE,
1234  EVILNESS_SUB_REPLACEMENT,
1235  EVILNESS_SUB_NO_REPLACEMENT,
1236 };
1237 
1238 struct Evilness
1239 {
1240  enum EvilnessType type;
1241  enum EvilnessSubType subtype;
1242  unsigned int num;
1243 };
1244 
1245 
1246 static int
1247 parse_evilness_cram_subtype (const char *evil_subtype_str,
1248  struct Evilness *evil)
1249 {
1250  if (0 == strcmp ("replace", evil_subtype_str))
1251  {
1252  evil->subtype = EVILNESS_SUB_REPLACEMENT;
1253  }
1254  else if (0 == strcmp ("noreplace", evil_subtype_str))
1255  {
1256  evil->subtype = EVILNESS_SUB_NO_REPLACEMENT;
1257  }
1258  else
1259  {
1261  "Malformed field '%s' in EVIL_SPEC (unknown subtype), behaving like a good peer.\n",
1262  evil_subtype_str);
1263  return GNUNET_SYSERR;
1264  }
1265  return GNUNET_OK;
1266 }
1267 
1268 
1269 static void
1270 get_evilness (struct ConsensusSession *session, struct Evilness *evil)
1271 {
1272  char *evil_spec;
1273  char *field;
1274  char *evil_type_str = NULL;
1275  char *evil_subtype_str = NULL;
1276 
1277  GNUNET_assert (NULL != evil);
1278 
1279  if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_string (cfg, "consensus",
1280  "EVIL_SPEC",
1281  &evil_spec))
1282  {
1284  "P%u: no evilness\n",
1285  session->local_peer_idx);
1286  evil->type = EVILNESS_NONE;
1287  return;
1288  }
1290  "P%u: got evilness spec\n",
1291  session->local_peer_idx);
1292 
1293  for (field = strtok (evil_spec, "/");
1294  NULL != field;
1295  field = strtok (NULL, "/"))
1296  {
1297  unsigned int peer_num;
1298  unsigned int evil_num;
1299  int ret;
1300 
1301  evil_type_str = NULL;
1302  evil_subtype_str = NULL;
1303 
1304  ret = sscanf (field, "%u;%m[a-z-];%m[a-z-];%u", &peer_num, &evil_type_str,
1305  &evil_subtype_str, &evil_num);
1306 
1307  if (ret != 4)
1308  {
1310  "Malformed field '%s' in EVIL_SPEC (expected 4 components got %d), behaving like a good peer.\n",
1311  field,
1312  ret);
1313  goto not_evil;
1314  }
1315 
1316  GNUNET_assert (NULL != evil_type_str);
1317  GNUNET_assert (NULL != evil_subtype_str);
1318 
1319  if (peer_num == session->local_peer_idx)
1320  {
1321  if (0 == strcmp ("slack", evil_type_str))
1322  {
1323  evil->type = EVILNESS_SLACK;
1324  }
1325  if (0 == strcmp ("slack-a2a", evil_type_str))
1326  {
1327  evil->type = EVILNESS_SLACK_A2A;
1328  }
1329  else if (0 == strcmp ("cram-all", evil_type_str))
1330  {
1331  evil->type = EVILNESS_CRAM_ALL;
1332  evil->num = evil_num;
1333  if (GNUNET_OK != parse_evilness_cram_subtype (evil_subtype_str, evil))
1334  goto not_evil;
1335  }
1336  else if (0 == strcmp ("cram-lead", evil_type_str))
1337  {
1338  evil->type = EVILNESS_CRAM_LEAD;
1339  evil->num = evil_num;
1340  if (GNUNET_OK != parse_evilness_cram_subtype (evil_subtype_str, evil))
1341  goto not_evil;
1342  }
1343  else if (0 == strcmp ("cram-echo", evil_type_str))
1344  {
1345  evil->type = EVILNESS_CRAM_ECHO;
1346  evil->num = evil_num;
1347  if (GNUNET_OK != parse_evilness_cram_subtype (evil_subtype_str, evil))
1348  goto not_evil;
1349  }
1350  else
1351  {
1353  "Malformed field '%s' in EVIL_SPEC (unknown type), behaving like a good peer.\n",
1354  evil_type_str);
1355  goto not_evil;
1356  }
1357  goto cleanup;
1358  }
1359  /* No GNUNET_free since memory was allocated by libc */
1360  free (evil_type_str);
1361  evil_type_str = NULL;
1362  evil_subtype_str = NULL;
1363  }
1364 not_evil:
1365  evil->type = EVILNESS_NONE;
1366 cleanup:
1367  GNUNET_free (evil_spec);
1368  /* no GNUNET_free since it wasn't
1369  * allocated with GNUNET_malloc */
1370  if (NULL != evil_type_str)
1371  free (evil_type_str);
1372  if (NULL != evil_subtype_str)
1373  free (evil_subtype_str);
1374 }
1375 
1376 
1377 #endif
1378 
1379 
1383 static void
1384 commit_set (struct ConsensusSession *session,
1385  struct TaskEntry *task)
1386 {
1387  struct SetEntry *set;
1388  struct SetOpCls *setop = &task->cls.setop;
1389 
1390  GNUNET_assert (NULL != setop->op);
1391  set = lookup_set (session, &setop->input_set);
1392  GNUNET_assert (NULL != set);
1393 
1394  if ((GNUNET_YES == setop->transceive_contested) && (GNUNET_YES ==
1395  set->is_contested))
1396  {
1397  struct GNUNET_SET_Element element;
1398  struct ConsensusElement ce = { 0 };
1399 
1401  element.data = &ce;
1402  element.size = sizeof(struct ConsensusElement);
1404  GNUNET_SET_add_element (set->h, &element, NULL, NULL);
1405  }
1406 
1407  if (PHASE_KIND_ALL_TO_ALL_2 == task->key.kind)
1408  {
1409  struct GNUNET_SET_Element element;
1410  struct ConsensusSizeElement cse = {
1411  .size = 0,
1412  .sender_index = 0
1413  };
1414  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "inserting size marker\n");
1416  cse.size = GNUNET_htonll (session->first_size);
1417  cse.sender_index = session->local_peer_idx;
1418  element.data = &cse;
1419  element.size = sizeof(struct ConsensusSizeElement);
1421  GNUNET_SET_add_element (set->h, &element, NULL, NULL);
1422  }
1423 
1424 #ifdef EVIL
1425  {
1426  struct Evilness evil;
1427 
1428  get_evilness (session, &evil);
1429  if (EVILNESS_NONE != evil.type)
1430  {
1431  /* Useful for evaluation */
1432  GNUNET_STATISTICS_set (statistics,
1433  "is evil",
1434  1,
1435  GNUNET_NO);
1436  }
1437  switch (evil.type)
1438  {
1439  case EVILNESS_CRAM_ALL:
1440  case EVILNESS_CRAM_LEAD:
1441  case EVILNESS_CRAM_ECHO:
1442  /* We're not cramming elements in the
1443  all-to-all round, since that would just
1444  add more elements to the result set, but
1445  wouldn't test robustness. */
1446  if (PHASE_KIND_ALL_TO_ALL == task->key.kind)
1447  {
1448  GNUNET_SET_commit (setop->op, set->h);
1449  break;
1450  }
1451  if ((EVILNESS_CRAM_LEAD == evil.type) &&
1452  ((PHASE_KIND_GRADECAST_LEADER != task->key.kind) ||
1453  (SET_KIND_CURRENT != set->key.set_kind) ))
1454  {
1455  GNUNET_SET_commit (setop->op, set->h);
1456  break;
1457  }
1458  if ((EVILNESS_CRAM_ECHO == evil.type) && (PHASE_KIND_GRADECAST_ECHO !=
1459  task->key.kind))
1460  {
1461  GNUNET_SET_commit (setop->op, set->h);
1462  break;
1463  }
1464  for (unsigned int i = 0; i < evil.num; i++)
1465  {
1466  struct GNUNET_SET_Element element;
1467  struct ConsensusStuffedElement se = {
1468  .ce.payload_type = 0,
1469  .ce.marker = 0,
1470  };
1471  element.data = &se;
1472  element.size = sizeof(struct ConsensusStuffedElement);
1474 
1475  if (EVILNESS_SUB_REPLACEMENT == evil.subtype)
1476  {
1477  /* Always generate a new element. */
1479  &se.rand);
1480  }
1481  else if (EVILNESS_SUB_NO_REPLACEMENT == evil.subtype)
1482  {
1483  /* Always cram the same elements, derived from counter. */
1484  GNUNET_CRYPTO_hash (&i, sizeof(i), &se.rand);
1485  }
1486  else
1487  {
1488  GNUNET_assert (0);
1489  }
1490  GNUNET_SET_add_element (set->h, &element, NULL, NULL);
1491 #ifdef GNUNET_EXTRA_LOGGING
1493  "P%u: evil peer: cramming element %s into set {%s} of task {%s}\n",
1494  session->local_peer_idx,
1495  debug_str_element (&element),
1496  debug_str_set_key (&setop->input_set),
1497  debug_str_task_key (&task->key));
1498 #endif
1499  }
1500  GNUNET_STATISTICS_update (statistics,
1501  "# stuffed elements",
1502  evil.num,
1503  GNUNET_NO);
1504  GNUNET_SET_commit (setop->op, set->h);
1505  break;
1506 
1507  case EVILNESS_SLACK:
1509  "P%u: evil peer: slacking\n",
1510  (unsigned int) session->local_peer_idx);
1511 
1512  /* Do nothing. */
1513  case EVILNESS_SLACK_A2A:
1514  if ((PHASE_KIND_ALL_TO_ALL_2 == task->key.kind) ||
1515  (PHASE_KIND_ALL_TO_ALL == task->key.kind))
1516  {
1517  struct GNUNET_SET_Handle *empty_set;
1518  empty_set = GNUNET_SET_create (cfg, GNUNET_SET_OPERATION_UNION);
1519  GNUNET_SET_commit (setop->op, empty_set);
1520  GNUNET_SET_destroy (empty_set);
1521  }
1522  else
1523  {
1524  GNUNET_SET_commit (setop->op,
1525  set->h);
1526  }
1527  break;
1528 
1529  case EVILNESS_NONE:
1530  GNUNET_SET_commit (setop->op,
1531  set->h);
1532  break;
1533  }
1534  }
1535 #else
1536  if (GNUNET_NO == session->peers_blacklisted[task_other_peer (task)])
1537  {
1538  GNUNET_SET_commit (setop->op, set->h);
1539  }
1540  else
1541  {
1542  /* For our testcases, we don't want the blacklisted
1543  peers to wait. */
1545  setop->op = NULL;
1546  finish_task (task);
1547  }
1548 #endif
1549 }
1550 
1551 
1552 static void
1553 put_diff (struct ConsensusSession *session,
1554  struct DiffEntry *diff)
1555 {
1556  struct GNUNET_HashCode hash;
1557 
1558  GNUNET_CRYPTO_hash (&diff->key,
1559  sizeof(struct DiffKey),
1560  &hash);
1563  &hash,
1564  diff,
1566 }
1567 
1568 
1569 static void
1570 put_set (struct ConsensusSession *session,
1571  struct SetEntry *set)
1572 {
1573  struct GNUNET_HashCode hash;
1574 
1575  GNUNET_assert (NULL != set->h);
1577  "Putting set %s\n",
1578  debug_str_set_key (&set->key));
1579  GNUNET_CRYPTO_hash (&set->key,
1580  sizeof(struct SetKey),
1581  &hash);
1584  &hash,
1585  set,
1587 }
1588 
1589 
1590 static void
1591 put_rfn (struct ConsensusSession *session,
1592  struct ReferendumEntry *rfn)
1593 {
1594  struct GNUNET_HashCode hash;
1595 
1596  GNUNET_CRYPTO_hash (&rfn->key, sizeof(struct RfnKey), &hash);
1599  &hash,
1600  rfn,
1602 }
1603 
1604 
1605 static void
1607 {
1608  /* not implemented yet */
1609  GNUNET_assert (0);
1610 }
1611 
1612 
1613 static void
1615  struct ReferendumEntry *rfn,
1616  uint16_t voting_peer,
1617  uint16_t num_peers)
1618 {
1620  struct DiffElementInfo *di;
1621 
1623 
1624  while (GNUNET_YES ==
1626  NULL,
1627  (const void **) &di))
1628  {
1629  if (di->weight > 0)
1630  {
1631  rfn_vote (rfn, voting_peer, VOTE_ADD, di->element);
1632  }
1633  if (di->weight < 0)
1634  {
1635  rfn_vote (rfn, voting_peer, VOTE_REMOVE, di->element);
1636  }
1637  }
1638 
1640 }
1641 
1642 
1643 static struct DiffEntry *
1645 {
1646  struct DiffEntry *d = GNUNET_new (struct DiffEntry);
1647 
1649  GNUNET_NO);
1650 
1651  return d;
1652 }
1653 
1654 
1655 #if 0
1656 static struct DiffEntry *
1657 diff_compose (struct DiffEntry *diff_1,
1658  struct DiffEntry *diff_2)
1659 {
1660  struct DiffEntry *diff_new;
1662  struct DiffElementInfo *di;
1663 
1664  diff_new = diff_create ();
1665 
1667  while (GNUNET_YES ==
1669  NULL,
1670  (const void **) &di))
1671  {
1672  diff_insert (diff_new,
1673  di->weight,
1674  di->element);
1675  }
1677 
1679  while (GNUNET_YES ==
1681  NULL,
1682  (const void **) &di))
1683  {
1684  diff_insert (diff_new,
1685  di->weight,
1686  di->element);
1687  }
1689 
1690  return diff_new;
1691 }
1692 
1693 
1694 #endif
1695 
1696 
1697 struct ReferendumEntry *
1698 rfn_create (uint16_t size)
1699 {
1700  struct ReferendumEntry *rfn;
1701 
1702  rfn = GNUNET_new (struct ReferendumEntry);
1704  rfn->peer_commited = GNUNET_new_array (size, int);
1705  rfn->peer_contested = GNUNET_new_array (size, int);
1706  rfn->num_peers = size;
1707 
1708  return rfn;
1709 }
1710 
1711 
1712 #if UNUSED
1713 static void
1714 diff_destroy (struct DiffEntry *diff)
1715 {
1717  GNUNET_free (diff);
1718 }
1719 
1720 
1721 #endif
1722 
1723 
1729 static void
1730 rfn_majority (const struct ReferendumEntry *rfn,
1731  const struct RfnElementInfo *ri,
1732  uint16_t *ret_majority,
1733  enum ReferendumVote *ret_vote)
1734 {
1735  uint16_t votes_yes = 0;
1736  uint16_t num_commited = 0;
1737 
1739  "Computing rfn majority for element %s of rfn {%s}\n",
1740  debug_str_element (ri->element),
1741  debug_str_rfn_key (&rfn->key));
1742 
1743  for (uint16_t i = 0; i < rfn->num_peers; i++)
1744  {
1745  if (GNUNET_NO == rfn->peer_commited[i])
1746  continue;
1747  num_commited++;
1748 
1749  if (GNUNET_YES == ri->votes[i])
1750  votes_yes++;
1751  }
1752 
1753  if (votes_yes > (num_commited) / 2)
1754  {
1755  *ret_vote = ri->proposal;
1756  *ret_majority = votes_yes;
1757  }
1758  else
1759  {
1760  *ret_vote = VOTE_STAY;
1761  *ret_majority = num_commited - votes_yes;
1762  }
1763 }
1764 
1765 
1767 {
1768  struct TaskEntry *task;
1769  struct SetKey dst_set_key;
1770 };
1771 
1772 
1773 static void
1774 set_copy_cb (void *cls,
1775  struct GNUNET_SET_Handle *copy)
1776 {
1777  struct SetCopyCls *scc = cls;
1778  struct TaskEntry *task = scc->task;
1779  struct SetKey dst_set_key = scc->dst_set_key;
1780  struct SetEntry *set;
1781  struct SetHandle *sh = GNUNET_new (struct SetHandle);
1782 
1783  sh->h = copy;
1785  task->step->session->set_handles_tail,
1786  sh);
1787 
1788  GNUNET_free (scc);
1789  set = GNUNET_new (struct SetEntry);
1790  set->h = copy;
1791  set->key = dst_set_key;
1792  put_set (task->step->session, set);
1793 
1794  task->start (task);
1795 }
1796 
1797 
1802 static void
1804  struct SetKey *src_set_key,
1805  struct SetKey *dst_set_key)
1806 {
1807  struct SetEntry *src_set;
1808  struct SetCopyCls *scc = GNUNET_new (struct SetCopyCls);
1809 
1811  "Copying set {%s} to {%s} for task {%s}\n",
1812  debug_str_set_key (src_set_key),
1813  debug_str_set_key (dst_set_key),
1814  debug_str_task_key (&task->key));
1815 
1816  scc->task = task;
1817  scc->dst_set_key = *dst_set_key;
1818  src_set = lookup_set (task->step->session, src_set_key);
1819  GNUNET_assert (NULL != src_set);
1820  GNUNET_SET_copy_lazy (src_set->h,
1821  set_copy_cb,
1822  scc);
1823 }
1824 
1825 
1827 {
1832  struct TaskEntry *task;
1833 };
1834 
1835 
1836 static void
1838 {
1839  struct SetMutationProgressCls *pc = cls;
1840 
1841  GNUNET_assert (pc->num_pending > 0);
1842 
1843  pc->num_pending--;
1844 
1845  if (0 == pc->num_pending)
1846  {
1847  struct TaskEntry *task = pc->task;
1848  GNUNET_free (pc);
1849  finish_task (task);
1850  }
1851 }
1852 
1853 
1854 static void
1856 {
1857  if (GNUNET_YES == step->is_running)
1858  return;
1859  if (GNUNET_YES == step->is_finished)
1860  return;
1861  if (GNUNET_NO == step->early_finishable)
1862  return;
1863 
1864  step->is_finished = GNUNET_YES;
1865 
1866 #ifdef GNUNET_EXTRA_LOGGING
1868  "Finishing step `%s' early.\n",
1869  step->debug_name);
1870 #endif
1871 
1872  for (unsigned int i = 0; i < step->subordinates_len; i++)
1873  {
1874  GNUNET_assert (step->subordinates[i]->pending_prereq > 0);
1875  step->subordinates[i]->pending_prereq--;
1876 #ifdef GNUNET_EXTRA_LOGGING
1878  "Decreased pending_prereq to %u for step `%s'.\n",
1879  (unsigned int) step->subordinates[i]->pending_prereq,
1880  step->subordinates[i]->debug_name);
1881 #endif
1883  }
1884 
1885  // XXX: maybe schedule as task to avoid recursion?
1886  run_ready_steps (step->session);
1887 }
1888 
1889 
1890 static void
1892 {
1893  GNUNET_assert (step->finished_tasks == step->tasks_len);
1894  GNUNET_assert (GNUNET_YES == step->is_running);
1895  GNUNET_assert (GNUNET_NO == step->is_finished);
1896 
1897 #ifdef GNUNET_EXTRA_LOGGING
1899  "All tasks of step `%s' with %u subordinates finished.\n",
1900  step->debug_name,
1901  step->subordinates_len);
1902 #endif
1903 
1904  for (unsigned int i = 0; i < step->subordinates_len; i++)
1905  {
1906  GNUNET_assert (step->subordinates[i]->pending_prereq > 0);
1907  step->subordinates[i]->pending_prereq--;
1908 #ifdef GNUNET_EXTRA_LOGGING
1910  "Decreased pending_prereq to %u for step `%s'.\n",
1911  (unsigned int) step->subordinates[i]->pending_prereq,
1912  step->subordinates[i]->debug_name);
1913 #endif
1914  }
1915 
1916  step->is_finished = GNUNET_YES;
1917 
1918  // XXX: maybe schedule as task to avoid recursion?
1919  run_ready_steps (step->session);
1920 }
1921 
1922 
1929 static void
1931 {
1932  struct ConsensusSession *session = task->step->session;
1933  struct SetKey sk_in;
1934  struct SetKey sk_out;
1935  struct RfnKey rk_in;
1936  struct SetEntry *set_out;
1937  struct ReferendumEntry *rfn_in;
1939  struct RfnElementInfo *ri;
1940  struct SetMutationProgressCls *progress_cls;
1941  uint16_t worst_majority = UINT16_MAX;
1942 
1943  sk_in = (struct SetKey) { SET_KIND_CURRENT, task->key.repetition };
1944  rk_in = (struct RfnKey) { RFN_KIND_GRADECAST_RESULT, task->key.repetition };
1945  sk_out = (struct SetKey) { SET_KIND_CURRENT, task->key.repetition + 1 };
1946 
1947  set_out = lookup_set (session, &sk_out);
1948  if (NULL == set_out)
1949  {
1951  &sk_in,
1952  &sk_out);
1953  return;
1954  }
1955 
1956  rfn_in = lookup_rfn (session, &rk_in);
1957  GNUNET_assert (NULL != rfn_in);
1958 
1959  progress_cls = GNUNET_new (struct SetMutationProgressCls);
1960  progress_cls->task = task;
1961 
1963 
1964  while (GNUNET_YES ==
1966  NULL,
1967  (const void **) &ri))
1968  {
1969  uint16_t majority_num;
1970  enum ReferendumVote majority_vote;
1971 
1972  rfn_majority (rfn_in, ri, &majority_num, &majority_vote);
1973 
1974  if (worst_majority > majority_num)
1975  worst_majority = majority_num;
1976 
1977  switch (majority_vote)
1978  {
1979  case VOTE_ADD:
1980  progress_cls->num_pending++;
1982  GNUNET_SET_add_element (set_out->h,
1983  ri->element,
1985  progress_cls));
1987  "P%u: apply round: adding element %s with %u-majority.\n",
1988  session->local_peer_idx,
1989  debug_str_element (ri->element), majority_num);
1990  break;
1991 
1992  case VOTE_REMOVE:
1993  progress_cls->num_pending++;
1995  GNUNET_SET_remove_element (set_out->h,
1996  ri->element,
1998  progress_cls));
2000  "P%u: apply round: deleting element %s with %u-majority.\n",
2001  session->local_peer_idx,
2002  debug_str_element (ri->element), majority_num);
2003  break;
2004 
2005  case VOTE_STAY:
2007  "P%u: apply round: keeping element %s with %u-majority.\n",
2008  session->local_peer_idx,
2009  debug_str_element (ri->element), majority_num);
2010  // do nothing
2011  break;
2012 
2013  default:
2014  GNUNET_assert (0);
2015  break;
2016  }
2017  }
2018 
2019  if (0 == progress_cls->num_pending)
2020  {
2021  // call closure right now, no pending ops
2022  GNUNET_free (progress_cls);
2023  finish_task (task);
2024  }
2025 
2026  {
2027  uint16_t thresh = (session->num_peers / 3) * 2;
2028 
2029  if (worst_majority >= thresh)
2030  {
2031  switch (session->early_stopping)
2032  {
2033  case EARLY_STOPPING_NONE:
2036  "P%u: Stopping early (after one more superround)\n",
2037  session->local_peer_idx);
2038  break;
2039 
2042  "P%u: finishing steps due to early finish\n",
2043  session->local_peer_idx);
2045  {
2046  struct Step *step;
2047  for (step = session->steps_head; NULL != step; step = step->next)
2048  try_finish_step_early (step);
2049  }
2050  break;
2051 
2052  case EARLY_STOPPING_DONE:
2053  /* We shouldn't be here anymore after early stopping */
2054  GNUNET_break (0);
2055  break;
2056 
2057  default:
2058  GNUNET_assert (0);
2059  break;
2060  }
2061  }
2062  else if (EARLY_STOPPING_NONE != session->early_stopping)
2063  {
2064  // Our assumption about the number of bad peers
2065  // has been broken.
2066  GNUNET_break_op (0);
2067  }
2068  else
2069  {
2071  "P%u: NOT finishing early (majority not good enough)\n",
2072  session->local_peer_idx);
2073  }
2074  }
2076 }
2077 
2078 
2079 static void
2081 {
2082  struct ConsensusSession *session = task->step->session;
2083  struct ReferendumEntry *output_rfn;
2084  struct ReferendumEntry *input_rfn;
2085  struct DiffEntry *input_diff;
2086  struct RfnKey rfn_key;
2087  struct DiffKey diff_key;
2089  struct RfnElementInfo *ri;
2090  unsigned int gradecast_confidence = 2;
2091 
2092  rfn_key = (struct RfnKey) { RFN_KIND_GRADECAST_RESULT, task->key.repetition };
2093  output_rfn = lookup_rfn (session, &rfn_key);
2094  if (NULL == output_rfn)
2095  {
2096  output_rfn = rfn_create (session->num_peers);
2097  output_rfn->key = rfn_key;
2098  put_rfn (session, output_rfn);
2099  }
2100 
2101  diff_key = (struct DiffKey) { DIFF_KIND_LEADER_PROPOSAL, task->key.repetition,
2102  task->key.leader };
2103  input_diff = lookup_diff (session, &diff_key);
2104  GNUNET_assert (NULL != input_diff);
2105 
2106  rfn_key = (struct RfnKey) { RFN_KIND_ECHO, task->key.repetition,
2107  task->key.leader };
2108  input_rfn = lookup_rfn (session, &rfn_key);
2109  GNUNET_assert (NULL != input_rfn);
2110 
2112  input_rfn->rfn_elements);
2113 
2114  apply_diff_to_rfn (input_diff, output_rfn, task->key.leader,
2115  session->num_peers);
2116 
2117  while (GNUNET_YES ==
2119  NULL,
2120  (const void **) &ri))
2121  {
2122  uint16_t majority_num;
2123  enum ReferendumVote majority_vote;
2124 
2125  // XXX: we need contested votes and non-contested votes here
2126  rfn_majority (input_rfn, ri, &majority_num, &majority_vote);
2127 
2128  if (majority_num <= session->num_peers / 3)
2129  majority_vote = VOTE_REMOVE;
2130 
2131  switch (majority_vote)
2132  {
2133  case VOTE_STAY:
2134  break;
2135 
2136  case VOTE_ADD:
2137  rfn_vote (output_rfn, task->key.leader, VOTE_ADD, ri->element);
2138  break;
2139 
2140  case VOTE_REMOVE:
2141  rfn_vote (output_rfn, task->key.leader, VOTE_REMOVE, ri->element);
2142  break;
2143 
2144  default:
2145  GNUNET_assert (0);
2146  break;
2147  }
2148  }
2150 
2151  {
2152  uint16_t noncontested;
2153  noncontested = rfn_noncontested (input_rfn);
2154  if (noncontested < (session->num_peers / 3) * 2)
2155  {
2156  gradecast_confidence = GNUNET_MIN (1, gradecast_confidence);
2157  }
2158  if (noncontested < (session->num_peers / 3) + 1)
2159  {
2160  gradecast_confidence = 0;
2161  }
2162  }
2163 
2164  if (gradecast_confidence >= 1)
2165  rfn_commit (output_rfn, task->key.leader);
2166 
2167  if (gradecast_confidence <= 1)
2168  session->peers_blacklisted[task->key.leader] = GNUNET_YES;
2169 
2170  finish_task (task);
2171 }
2172 
2173 
2174 static void
2176 {
2177  struct SetEntry *input;
2178  struct SetOpCls *setop = &task->cls.setop;
2179  struct ConsensusSession *session = task->step->session;
2180 
2181  input = lookup_set (session, &setop->input_set);
2182  GNUNET_assert (NULL != input);
2183  GNUNET_assert (NULL != input->h);
2184 
2185  /* We create the outputs for the operation here
2186  (rather than in the set operation callback)
2187  because we want something valid in there, even
2188  if the other peer doesn't talk to us */
2189 
2190  if (SET_KIND_NONE != setop->output_set.set_kind)
2191  {
2192  /* If we don't have an existing output set,
2193  we clone the input set. */
2194  if (NULL == lookup_set (session, &setop->output_set))
2195  {
2197  &setop->input_set,
2198  &setop->output_set);
2199  return;
2200  }
2201  }
2202 
2203  if (RFN_KIND_NONE != setop->output_rfn.rfn_kind)
2204  {
2205  if (NULL == lookup_rfn (session, &setop->output_rfn))
2206  {
2207  struct ReferendumEntry *rfn;
2208 
2210  "P%u: output rfn <%s> missing, creating.\n",
2211  session->local_peer_idx,
2212  debug_str_rfn_key (&setop->output_rfn));
2213 
2214  rfn = rfn_create (session->num_peers);
2215  rfn->key = setop->output_rfn;
2216  put_rfn (session, rfn);
2217  }
2218  }
2219 
2220  if (DIFF_KIND_NONE != setop->output_diff.diff_kind)
2221  {
2222  if (NULL == lookup_diff (session, &setop->output_diff))
2223  {
2224  struct DiffEntry *diff;
2225 
2226  diff = diff_create ();
2227  diff->key = setop->output_diff;
2228  put_diff (session, diff);
2229  }
2230  }
2231 
2232  if ((task->key.peer1 == session->local_peer_idx) && (task->key.peer2 ==
2233  session->local_peer_idx))
2234  {
2235  /* XXX: mark the corresponding rfn as commited if necessary */
2236  finish_task (task);
2237  return;
2238  }
2239 
2240  if (task->key.peer1 == session->local_peer_idx)
2241  {
2243 
2245  "P%u: Looking up set {%s} to run remote union\n",
2246  session->local_peer_idx,
2247  debug_str_set_key (&setop->input_set));
2249  rcm.header.size = htons (sizeof(rcm));
2250  rcm.kind = htons (task->key.kind);
2251  rcm.peer1 = htons (task->key.peer1);
2252  rcm.peer2 = htons (task->key.peer2);
2253  rcm.leader = htons (task->key.leader);
2254  rcm.repetition = htons (task->key.repetition);
2255  rcm.is_contested = htons (0);
2256 
2257  GNUNET_assert (NULL == setop->op);
2259  "P%u: initiating set op with P%u, our set is %s\n",
2260  session->local_peer_idx,
2261  task->key.peer2,
2262  debug_str_set_key (&setop->input_set));
2263 
2264  struct GNUNET_SET_Option opts[] = {
2265  { GNUNET_SET_OPTION_BYZANTINE, { .num = session->lower_bound } },
2267  };
2268 
2269  // XXX: maybe this should be done while
2270  // setting up tasks alreays?
2271  setop->op = GNUNET_SET_prepare (&session->peers[task->key.peer2],
2272  &session->global_id,
2273  &rcm.header,
2275  opts,
2276  set_result_cb,
2277  task);
2278 
2279  commit_set (session, task);
2280  }
2281  else if (task->key.peer2 == session->local_peer_idx)
2282  {
2283  /* Wait for the other peer to contact us */
2284  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: waiting set op with P%u\n",
2285  session->local_peer_idx, task->key.peer1);
2286 
2287  if (NULL != setop->op)
2288  {
2289  commit_set (session, task);
2290  }
2291  }
2292  else
2293  {
2294  /* We made an error while constructing the task graph. */
2295  GNUNET_assert (0);
2296  }
2297 }
2298 
2299 
2300 static void
2302 {
2304  struct ReferendumEntry *input_rfn;
2305  struct RfnElementInfo *ri;
2306  struct SetEntry *output_set;
2307  struct SetMutationProgressCls *progress_cls;
2308  struct ConsensusSession *session = task->step->session;
2309  struct SetKey sk_in;
2310  struct SetKey sk_out;
2311  struct RfnKey rk_in;
2312 
2313  sk_in = (struct SetKey) { SET_KIND_LEADER_PROPOSAL, task->key.repetition,
2314  task->key.leader };
2315  sk_out = (struct SetKey) { SET_KIND_ECHO_RESULT, task->key.repetition,
2316  task->key.leader };
2317  output_set = lookup_set (session, &sk_out);
2318  if (NULL == output_set)
2319  {
2321  &sk_in,
2322  &sk_out);
2323  return;
2324  }
2325 
2326  {
2327  // FIXME: should be marked as a shallow copy, so
2328  // we can destroy everything correctly
2329  struct SetEntry *last_set = GNUNET_new (struct SetEntry);
2330 
2331  last_set->h = output_set->h;
2332  last_set->key = (struct SetKey) { SET_KIND_LAST_GRADECAST };
2333  put_set (session, last_set);
2334  }
2335 
2337  "Evaluating referendum in Task {%s}\n",
2338  debug_str_task_key (&task->key));
2339 
2340  progress_cls = GNUNET_new (struct SetMutationProgressCls);
2341  progress_cls->task = task;
2342  rk_in = (struct RfnKey) { RFN_KIND_ECHO, task->key.repetition,
2343  task->key.leader };
2344  input_rfn = lookup_rfn (session, &rk_in);
2345  GNUNET_assert (NULL != input_rfn);
2347  input_rfn->rfn_elements);
2348  GNUNET_assert (NULL != iter);
2349 
2350  while (GNUNET_YES ==
2352  NULL,
2353  (const void **) &ri))
2354  {
2355  enum ReferendumVote majority_vote;
2356  uint16_t majority_num;
2357 
2358  rfn_majority (input_rfn, ri, &majority_num, &majority_vote);
2359 
2360  if (majority_num < session->num_peers / 3)
2361  {
2362  /* It is not the case that all nonfaulty peers
2363  echoed the same value. Since we're doing a set reconciliation, we
2364  can't simply send "nothing" for the value. Thus we mark our 'confirm'
2365  reconciliation as contested. Other peers might not know that the
2366  leader is faulty, thus we still re-distribute in the confirmation
2367  round. *///
2368  output_set->is_contested = GNUNET_YES;
2369  }
2370 
2371  switch (majority_vote)
2372  {
2373  case VOTE_ADD:
2374  progress_cls->num_pending++;
2376  GNUNET_SET_add_element (output_set->h,
2377  ri->element,
2379  progress_cls));
2380  break;
2381 
2382  case VOTE_REMOVE:
2383  progress_cls->num_pending++;
2385  GNUNET_SET_remove_element (output_set->h,
2386  ri->element,
2388  progress_cls));
2389  break;
2390 
2391  case VOTE_STAY:
2392  /* Nothing to do. */
2393  break;
2394 
2395  default:
2396  /* not reached */
2397  GNUNET_assert (0);
2398  }
2399  }
2400 
2402 
2403  if (0 == progress_cls->num_pending)
2404  {
2405  // call closure right now, no pending ops
2406  GNUNET_free (progress_cls);
2407  finish_task (task);
2408  }
2409 }
2410 
2411 
2412 static void
2414 {
2415  struct SetEntry *final_set;
2416  struct ConsensusSession *session = task->step->session;
2417 
2418  final_set = lookup_set (session,
2419  &task->cls.finish.input_set);
2420  GNUNET_assert (NULL != final_set);
2421  GNUNET_SET_iterate (final_set->h,
2423  task);
2424 }
2425 
2426 
2427 static void
2428 start_task (struct ConsensusSession *session,
2429  struct TaskEntry *task)
2430 {
2432  "P%u: starting task {%s}\n",
2433  session->local_peer_idx,
2434  debug_str_task_key (&task->key));
2435  GNUNET_assert (GNUNET_NO == task->is_started);
2436  GNUNET_assert (GNUNET_NO == task->is_finished);
2437  GNUNET_assert (NULL != task->start);
2438  task->start (task);
2439  task->is_started = GNUNET_YES;
2440 }
2441 
2442 
2443 /*
2444  * Run all steps of the session that don't any
2445  * more dependencies.
2446  */
2447 static void
2449 {
2450  struct Step *step;
2451 
2452  step = session->steps_head;
2453 
2454  while (NULL != step)
2455  {
2456  if ((GNUNET_NO == step->is_running) && (0 == step->pending_prereq) &&
2457  (GNUNET_NO == step->is_finished))
2458  {
2459  GNUNET_assert (0 == step->finished_tasks);
2460 
2461 #ifdef GNUNET_EXTRA_LOGGING
2463  "P%u: Running step `%s' of round %d with %d tasks and %d subordinates\n",
2464  session->local_peer_idx,
2465  step->debug_name,
2466  step->round, step->tasks_len, step->subordinates_len);
2467 #endif
2468 
2469  step->is_running = GNUNET_YES;
2470  for (size_t i = 0; i < step->tasks_len; i++)
2471  start_task (session, step->tasks[i]);
2472 
2473  /* Sometimes there is no task to trigger finishing the step, so we have to do it here. */
2474  if ((step->finished_tasks == step->tasks_len) && (GNUNET_NO ==
2475  step->is_finished))
2476  finish_step (step);
2477 
2478  /* Running the next ready steps will be triggered by task completion */
2479  return;
2480  }
2481  step = step->next;
2482  }
2483 
2484  return;
2485 }
2486 
2487 
2488 static void
2489 finish_task (struct TaskEntry *task)
2490 {
2491  GNUNET_assert (GNUNET_NO == task->is_finished);
2492  task->is_finished = GNUNET_YES;
2493  task->step->finished_tasks++;
2495  "P%u: Finishing Task {%s} (now %u/%u tasks finished in step)\n",
2496  task->step->session->local_peer_idx,
2497  debug_str_task_key (&task->key),
2498  (unsigned int) task->step->finished_tasks,
2499  (unsigned int) task->step->tasks_len);
2500 
2501  if (task->step->finished_tasks == task->step->tasks_len)
2502  finish_step (task->step);
2503 }
2504 
2505 
2513 static int
2515  const struct ConsensusSession *session)
2516 {
2517  for (int i = 0; i < session->num_peers; i++)
2518  if (0 == GNUNET_memcmp (peer, &session->peers[i]))
2519  return i;
2520  return -1;
2521 }
2522 
2523 
2533 static void
2535  const struct GNUNET_HashCode *local_session_id)
2536 {
2537  const char *salt = "gnunet-service-consensus/session_id";
2538 
2540  GNUNET_CRYPTO_kdf (&session->global_id,
2541  sizeof(struct GNUNET_HashCode),
2542  salt,
2543  strlen (salt),
2544  session->peers,
2545  session->num_peers * sizeof(struct
2547  local_session_id,
2548  sizeof(struct GNUNET_HashCode),
2549  NULL));
2550 }
2551 
2552 
2560 static int
2561 peer_id_cmp (const void *h1,
2562  const void *h2)
2563 {
2564  return memcmp (h1, h2, sizeof(struct GNUNET_PeerIdentity));
2565 }
2566 
2567 
2575 static void
2577  struct ConsensusSession *session,
2578  const struct GNUNET_CONSENSUS_JoinMessage *join_msg)
2579 {
2580  const struct GNUNET_PeerIdentity *msg_peers
2581  = (const struct GNUNET_PeerIdentity *) &join_msg[1];
2582  int local_peer_in_list;
2583 
2584  session->num_peers = ntohl (join_msg->num_peers);
2585 
2586  /* Peers in the join message, may or may not include the local peer,
2587  Add it if it is missing. */
2588  local_peer_in_list = GNUNET_NO;
2589  for (unsigned int i = 0; i < session->num_peers; i++)
2590  {
2591  if (0 == GNUNET_memcmp (&msg_peers[i],
2592  &my_peer))
2593  {
2594  local_peer_in_list = GNUNET_YES;
2595  break;
2596  }
2597  }
2598  if (GNUNET_NO == local_peer_in_list)
2599  session->num_peers++;
2600 
2601  session->peers = GNUNET_new_array (session->num_peers,
2602  struct GNUNET_PeerIdentity);
2603  if (GNUNET_NO == local_peer_in_list)
2604  session->peers[session->num_peers - 1] = my_peer;
2605  GNUNET_memcpy (session->peers,
2606  msg_peers,
2607  ntohl (join_msg->num_peers)
2608  * sizeof(struct GNUNET_PeerIdentity));
2609  qsort (session->peers,
2610  session->num_peers,
2611  sizeof (struct GNUNET_PeerIdentity),
2612  &peer_id_cmp);
2613 }
2614 
2615 
2616 static struct TaskEntry *
2617 lookup_task (const struct ConsensusSession *session,
2618  const struct TaskKey *key)
2619 {
2620  struct GNUNET_HashCode hash;
2621 
2622  GNUNET_CRYPTO_hash (key,
2623  sizeof(struct TaskKey),
2624  &hash);
2626  "Looking up task hash %s\n",
2627  GNUNET_h2s (&hash));
2628  return GNUNET_CONTAINER_multihashmap_get (session->taskmap,
2629  &hash);
2630 }
2631 
2632 
2648 static void
2649 set_listen_cb (void *cls,
2650  const struct GNUNET_PeerIdentity *other_peer,
2651  const struct GNUNET_MessageHeader *context_msg,
2652  struct GNUNET_SET_Request *request)
2653 {
2654  struct ConsensusSession *session = cls;
2655  struct TaskKey tk;
2656  struct TaskEntry *task;
2658 
2659  if (NULL == context_msg)
2660  {
2661  GNUNET_break_op (0);
2662  return;
2663  }
2664 
2666  context_msg->type))
2667  {
2668  GNUNET_break_op (0);
2669  return;
2670  }
2671 
2672  if (sizeof(struct GNUNET_CONSENSUS_RoundContextMessage) != ntohs (
2673  context_msg->size))
2674  {
2675  GNUNET_break_op (0);
2676  return;
2677  }
2678 
2679  cm = (struct GNUNET_CONSENSUS_RoundContextMessage *) context_msg;
2680 
2681  tk = ((struct TaskKey) {
2682  .kind = ntohs (cm->kind),
2683  .peer1 = ntohs (cm->peer1),
2684  .peer2 = ntohs (cm->peer2),
2685  .repetition = ntohs (cm->repetition),
2686  .leader = ntohs (cm->leader),
2687  });
2688 
2689  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "P%u: got req for task %s\n",
2690  session->local_peer_idx, debug_str_task_key (&tk));
2691 
2692  task = lookup_task (session, &tk);
2693 
2694  if (NULL == task)
2695  {
2696  GNUNET_break_op (0);
2697  return;
2698  }
2699 
2700  if (GNUNET_YES == task->is_finished)
2701  {
2702  GNUNET_break_op (0);
2703  return;
2704  }
2705 
2706  if (task->key.peer2 != session->local_peer_idx)
2707  {
2708  /* We're being asked, so we must be thne 2nd peer. */
2709  GNUNET_break_op (0);
2710  return;
2711  }
2712 
2713  GNUNET_assert (! ((task->key.peer1 == session->local_peer_idx) &&
2714  (task->key.peer2 == session->local_peer_idx)));
2715 
2716  struct GNUNET_SET_Option opts[] = {
2717  { GNUNET_SET_OPTION_BYZANTINE, { .num = session->lower_bound } },
2719  };
2720 
2721  task->cls.setop.op = GNUNET_SET_accept (request,
2723  opts,
2724  &set_result_cb,
2725  task);
2726 
2727  /* If the task hasn't been started yet,
2728  we wait for that until we commit. */
2729 
2730  if (GNUNET_YES == task->is_started)
2731  {
2732  commit_set (session, task);
2733  }
2734 }
2735 
2736 
2737 static void
2739  struct TaskEntry *t)
2740 {
2741  struct GNUNET_HashCode round_hash;
2742  struct Step *s;
2743 
2744  GNUNET_assert (NULL != t->step);
2745  t = GNUNET_memdup (t, sizeof(struct TaskEntry));
2746  s = t->step;
2747  if (s->tasks_len == s->tasks_cap)
2748  {
2749  unsigned int target_size = 3 * (s->tasks_cap + 1) / 2;
2751  s->tasks_cap,
2752  target_size);
2753  }
2754 
2755 #ifdef GNUNET_EXTRA_LOGGING
2756  GNUNET_assert (NULL != s->debug_name);
2757  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Putting task <%s> into step `%s'\n",
2758  debug_str_task_key (&t->key),
2759  s->debug_name);
2760 #endif
2761 
2762  s->tasks[s->tasks_len] = t;
2763  s->tasks_len++;
2764 
2765  GNUNET_CRYPTO_hash (&t->key,
2766  sizeof(struct TaskKey),
2767  &round_hash);
2770  &round_hash,
2771  t,
2773 }
2774 
2775 
2776 static void
2778 {
2779  /* Given the fully constructed task graph
2780  with rounds for tasks, we can give the tasks timeouts. */
2781 
2782  // unsigned int max_round;
2783 
2784  /* XXX: implement! */
2785 }
2786 
2787 
2788 /*
2789  * Arrange two peers in some canonical order.
2790  */
2791 static void
2792 arrange_peers (uint16_t *p1,
2793  uint16_t *p2,
2794  uint16_t n)
2795 {
2796  uint16_t a;
2797  uint16_t b;
2798 
2799  GNUNET_assert (*p1 < n);
2800  GNUNET_assert (*p2 < n);
2801 
2802  if (*p1 < *p2)
2803  {
2804  a = *p1;
2805  b = *p2;
2806  }
2807  else
2808  {
2809  a = *p2;
2810  b = *p1;
2811  }
2812 
2813  /* For uniformly random *p1, *p2,
2814  this condition is true with 50% chance */
2815  if (((b - a) + n) % n <= n / 2)
2816  {
2817  *p1 = a;
2818  *p2 = b;
2819  }
2820  else
2821  {
2822  *p1 = b;
2823  *p2 = a;
2824  }
2825 }
2826 
2827 
2831 static void
2832 step_depend_on (struct Step *step,
2833  struct Step *dep)
2834 {
2835  /* We're not checking for cyclic dependencies,
2836  but this is a cheap sanity check. */
2837  GNUNET_assert (step != dep);
2838  GNUNET_assert (NULL != step);
2839  GNUNET_assert (NULL != dep);
2840  GNUNET_assert (dep->round <= step->round);
2841 
2842 #ifdef GNUNET_EXTRA_LOGGING
2843  /* Make sure we have complete debugging information.
2844  Also checks that we don't screw up too badly
2845  constructing the task graph. */
2846  GNUNET_assert (NULL != step->debug_name);
2847  GNUNET_assert (NULL != dep->debug_name);
2849  "Making step `%s' depend on `%s'\n",
2850  step->debug_name,
2851  dep->debug_name);
2852 #endif
2853 
2854  if (dep->subordinates_cap == dep->subordinates_len)
2855  {
2856  unsigned int target_size = 3 * (dep->subordinates_cap + 1) / 2;
2858  dep->subordinates_cap,
2859  target_size);
2860  }
2861 
2863 
2864  dep->subordinates[dep->subordinates_len] = step;
2865  dep->subordinates_len++;
2866 
2867  step->pending_prereq++;
2868 }
2869 
2870 
2871 static struct Step *
2873  int round,
2874  int early_finishable)
2875 {
2876  struct Step *step;
2877 
2878  step = GNUNET_new (struct Step);
2879  step->session = session;
2880  step->round = round;
2883  session->steps_tail,
2884  step);
2885  return step;
2886 }
2887 
2888 
2892 static void
2894  uint16_t rep,
2895  uint16_t lead,
2896  struct Step *step_before,
2897  struct Step *step_after)
2898 {
2899  uint16_t n = session->num_peers;
2900  uint16_t me = session->local_peer_idx;
2901  uint16_t p1;
2902  uint16_t p2;
2903  /* The task we're currently setting up. */
2904  struct TaskEntry task;
2905  struct Step *step;
2906  struct Step *prev_step;
2907  uint16_t round;
2908 
2909  round = step_before->round + 1;
2910 
2911  /* gcast step 1: leader disseminates */
2912  step = create_step (session,
2913  round,
2914  GNUNET_YES);
2915 #ifdef GNUNET_EXTRA_LOGGING
2916  GNUNET_asprintf (&step->debug_name,
2917  "disseminate leader %u rep %u",
2918  lead,
2919  rep);
2920 #endif
2921  step_depend_on (step,
2922  step_before);
2923 
2924  if (lead == me)
2925  {
2926  for (unsigned int k = 0; k < n; k++)
2927  {
2928  if (k == me)
2929  continue;
2930  p1 = me;
2931  p2 = k;
2932  arrange_peers (&p1, &p2, n);
2933  task = ((struct TaskEntry) {
2934  .step = step,
2935  .start = task_start_reconcile,
2936  .cancel = task_cancel_reconcile,
2937  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_LEADER, p1, p2, rep,
2938  me },
2939  });
2940  task.cls.setop.input_set = (struct SetKey) { SET_KIND_CURRENT, rep };
2941  put_task (session->taskmap, &task);
2942  }
2943  /* We run this task to make sure that the leader
2944  has the stored the SET_KIND_LEADER set of himself,
2945  so it can participate in the rest of the gradecast
2946  without the code having to handle any special cases. */
2947  task = ((struct TaskEntry) {
2948  .step = step,
2949  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_LEADER, me, me, rep, me },
2950  .start = task_start_reconcile,
2951  .cancel = task_cancel_reconcile,
2952  });
2953  task.cls.setop.input_set = (struct SetKey) { SET_KIND_CURRENT, rep };
2954  task.cls.setop.output_set = (struct SetKey) { SET_KIND_LEADER_PROPOSAL, rep,
2955  me };
2957  rep, me };
2958  put_task (session->taskmap, &task);
2959  }
2960  else
2961  {
2962  p1 = me;
2963  p2 = lead;
2964  arrange_peers (&p1, &p2, n);
2965  task = ((struct TaskEntry) {
2966  .step = step,
2967  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_LEADER, p1, p2, rep,
2968  lead },
2969  .start = task_start_reconcile,
2970  .cancel = task_cancel_reconcile,
2971  });
2972  task.cls.setop.input_set = (struct SetKey) { SET_KIND_CURRENT, rep };
2973  task.cls.setop.output_set = (struct SetKey) { SET_KIND_LEADER_PROPOSAL, rep,
2974  lead };
2976  rep, lead };
2977  put_task (session->taskmap, &task);
2978  }
2979 
2980  /* gcast phase 2: echo */
2981  prev_step = step;
2982  round += 1;
2983  step = create_step (session,
2984  round,
2985  GNUNET_YES);
2986 #ifdef GNUNET_EXTRA_LOGGING
2987  GNUNET_asprintf (&step->debug_name,
2988  "echo leader %u rep %u",
2989  lead,
2990  rep);
2991 #endif
2992  step_depend_on (step,
2993  prev_step);
2994 
2995  for (unsigned int k = 0; k < n; k++)
2996  {
2997  p1 = k;
2998  p2 = me;
2999  arrange_peers (&p1, &p2, n);
3000  task = ((struct TaskEntry) {
3001  .step = step,
3002  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_ECHO, p1, p2, rep, lead },
3003  .start = task_start_reconcile,
3004  .cancel = task_cancel_reconcile,
3005  });
3006  task.cls.setop.input_set = (struct SetKey) { SET_KIND_LEADER_PROPOSAL, rep,
3007  lead };
3008  task.cls.setop.output_rfn = (struct RfnKey) { RFN_KIND_ECHO, rep, lead };
3009  put_task (session->taskmap, &task);
3010  }
3011 
3012  prev_step = step;
3013  /* Same round, since step only has local tasks */
3014  step = create_step (session, round, GNUNET_YES);
3015 #ifdef GNUNET_EXTRA_LOGGING
3016  GNUNET_asprintf (&step->debug_name, "echo grade leader %u rep %u", lead, rep);
3017 #endif
3018  step_depend_on (step, prev_step);
3019 
3020  arrange_peers (&p1, &p2, n);
3021  task = ((struct TaskEntry) {
3022  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_ECHO_GRADE, -1, -1, rep,
3023  lead },
3024  .step = step,
3025  .start = task_start_eval_echo
3026  });
3027  put_task (session->taskmap, &task);
3028 
3029  prev_step = step;
3030  round += 1;
3031  step = create_step (session, round, GNUNET_YES);
3032 #ifdef GNUNET_EXTRA_LOGGING
3033  GNUNET_asprintf (&step->debug_name, "confirm leader %u rep %u", lead, rep);
3034 #endif
3035  step_depend_on (step, prev_step);
3036 
3037  /* gcast phase 3: confirmation and grading */
3038  for (unsigned int k = 0; k < n; k++)
3039  {
3040  p1 = k;
3041  p2 = me;
3042  arrange_peers (&p1, &p2, n);
3043  task = ((struct TaskEntry) {
3044  .step = step,
3045  .start = task_start_reconcile,
3046  .cancel = task_cancel_reconcile,
3047  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_CONFIRM, p1, p2, rep,
3048  lead },
3049  });
3050  task.cls.setop.input_set = (struct SetKey) { SET_KIND_ECHO_RESULT, rep,
3051  lead };
3052  task.cls.setop.output_rfn = (struct RfnKey) { RFN_KIND_CONFIRM, rep, lead };
3053  /* If there was at least one element in the echo round that was
3054  contested (i.e. it had no n-t majority), then we let the other peers
3055  know, and other peers let us know. The contested flag for each peer is
3056  stored in the rfn. */
3058  put_task (session->taskmap, &task);
3059  }
3060 
3061  prev_step = step;
3062  /* Same round, since step only has local tasks */
3063  step = create_step (session, round, GNUNET_YES);
3064 #ifdef GNUNET_EXTRA_LOGGING
3065  GNUNET_asprintf (&step->debug_name, "confirm grade leader %u rep %u", lead,
3066  rep);
3067 #endif
3068  step_depend_on (step, prev_step);
3069 
3070  task = ((struct TaskEntry) {
3071  .step = step,
3072  .key = (struct TaskKey) { PHASE_KIND_GRADECAST_CONFIRM_GRADE, -1, -1, rep,
3073  lead },
3074  .start = task_start_grade,
3075  });
3076  put_task (session->taskmap, &task);
3077 
3078  step_depend_on (step_after, step);
3079 }
3080 
3081 
3082 static void
3084 {
3085  uint16_t n = session->num_peers;
3086  uint16_t t = n / 3;
3087  uint16_t me = session->local_peer_idx;
3088  /* The task we're currently setting up. */
3089  struct TaskEntry task;
3090  /* Current leader */
3091  unsigned int lead;
3092  struct Step *step;
3093  struct Step *prev_step;
3094  unsigned int round = 0;
3095 
3096  // XXX: introduce first step,
3097  // where we wait for all insert acks
3098  // from the set service
3099 
3100  /* faster but brittle all-to-all */
3101 
3102  // XXX: Not implemented yet
3103 
3104  /* all-to-all step */
3105 
3106  step = create_step (session, round, GNUNET_NO);
3107 
3108 #ifdef GNUNET_EXTRA_LOGGING
3109  step->debug_name = GNUNET_strdup ("all to all");
3110 #endif
3111 
3112  for (unsigned int i = 0; i < n; i++)
3113  {
3114  uint16_t p1;
3115  uint16_t p2;
3116 
3117  p1 = me;
3118  p2 = i;
3119  arrange_peers (&p1, &p2, n);
3120  task = ((struct TaskEntry) {
3121  .key = (struct TaskKey) { PHASE_KIND_ALL_TO_ALL, p1, p2, -1, -1 },
3122  .step = step,
3123  .start = task_start_reconcile,
3124  .cancel = task_cancel_reconcile,
3125  });
3126  task.cls.setop.input_set = (struct SetKey) { SET_KIND_CURRENT, 0 };
3127  task.cls.setop.output_set = task.cls.setop.input_set;
3129  put_task (session->taskmap, &task);
3130  }
3131 
3132  round += 1;
3133  prev_step = step;
3134  step = create_step (session, round, GNUNET_NO);;
3135 #ifdef GNUNET_EXTRA_LOGGING
3136  step->debug_name = GNUNET_strdup ("all to all 2");
3137 #endif
3138  step_depend_on (step, prev_step);
3139 
3140 
3141  for (unsigned int i = 0; i < n; i++)
3142  {
3143  uint16_t p1;
3144  uint16_t p2;
3145 
3146  p1 = me;
3147  p2 = i;
3148  arrange_peers (&p1, &p2, n);
3149  task = ((struct TaskEntry) {
3150  .key = (struct TaskKey) { PHASE_KIND_ALL_TO_ALL_2, p1, p2, -1, -1 },
3151  .step = step,
3152  .start = task_start_reconcile,
3153  .cancel = task_cancel_reconcile,
3154  });
3155  task.cls.setop.input_set = (struct SetKey) { SET_KIND_CURRENT, 0 };
3156  task.cls.setop.output_set = task.cls.setop.input_set;
3158  put_task (session->taskmap, &task);
3159  }
3160 
3161  round += 1;
3162 
3163  prev_step = step;
3164  step = NULL;
3165 
3166 
3167  /* Byzantine union */
3168 
3169  /* sequential repetitions of the gradecasts */
3170  for (unsigned int i = 0; i < t + 1; i++)
3171  {
3172  struct Step *step_rep_start;
3173  struct Step *step_rep_end;
3174 
3175  /* Every repetition is in a separate round. */
3176  step_rep_start = create_step (session, round, GNUNET_YES);
3177 #ifdef GNUNET_EXTRA_LOGGING
3178  GNUNET_asprintf (&step_rep_start->debug_name, "gradecast start rep %u", i);
3179 #endif
3180 
3181  step_depend_on (step_rep_start, prev_step);
3182 
3183  /* gradecast has three rounds */
3184  round += 3;
3185  step_rep_end = create_step (session, round, GNUNET_YES);
3186 #ifdef GNUNET_EXTRA_LOGGING
3187  GNUNET_asprintf (&step_rep_end->debug_name, "gradecast end rep %u", i);
3188 #endif
3189 
3190  /* parallel gradecasts */
3191  for (lead = 0; lead < n; lead++)
3192  construct_task_graph_gradecast (session, i, lead, step_rep_start,
3193  step_rep_end);
3194 
3195  task = ((struct TaskEntry) {
3196  .step = step_rep_end,
3197  .key = (struct TaskKey) { PHASE_KIND_APPLY_REP, -1, -1, i, -1 },
3198  .start = task_start_apply_round,
3199  });
3200  put_task (session->taskmap, &task);
3201 
3202  prev_step = step_rep_end;
3203  }
3204 
3205  /* There is no next gradecast round, thus the final
3206  start step is the overall end step of the gradecasts */
3207  round += 1;
3208  step = create_step (session, round, GNUNET_NO);
3209 #ifdef GNUNET_EXTRA_LOGGING
3210  GNUNET_asprintf (&step->debug_name, "finish");
3211 #endif
3212  step_depend_on (step, prev_step);
3213 
3214  task = ((struct TaskEntry) {
3215  .step = step,
3216  .key = (struct TaskKey) { PHASE_KIND_FINISH, -1, -1, -1, -1 },
3217  .start = task_start_finish,
3218  });
3219  task.cls.finish.input_set = (struct SetKey) { SET_KIND_LAST_GRADECAST };
3220 
3221  put_task (session->taskmap, &task);
3222 }
3223 
3224 
3232 static int
3234  const struct GNUNET_CONSENSUS_JoinMessage *m)
3235 {
3236  uint32_t listed_peers = ntohl (m->num_peers);
3237 
3238  if ((ntohs (m->header.size) - sizeof(*m)) !=
3239  listed_peers * sizeof(struct GNUNET_PeerIdentity))
3240  {
3241  GNUNET_break (0);
3242  return GNUNET_SYSERR;
3243  }
3244  return GNUNET_OK;
3245 }
3246 
3247 
3254 static void
3256  const struct GNUNET_CONSENSUS_JoinMessage *m)
3257 {
3258  struct ConsensusSession *session = cls;
3259  struct ConsensusSession *other_session;
3260 
3262  m);
3263  compute_global_id (session,
3264  &m->session_id);
3265 
3266  /* Check if some local client already owns the session.
3267  It is only legal to have a session with an existing global id
3268  if all other sessions with this global id are finished.*/
3269  for (other_session = sessions_head;
3270  NULL != other_session;
3271  other_session = other_session->next)
3272  {
3273  if ( (other_session != session) &&
3274  (0 == GNUNET_CRYPTO_hash_cmp (&session->global_id,
3275  &other_session->global_id)) )
3276  break;
3277  }
3278 
3279  session->conclude_deadline
3281  session->conclude_start
3283  session->local_peer_idx = get_peer_idx (&my_peer,
3284  session);
3285  GNUNET_assert (-1 != session->local_peer_idx);
3286 
3288  "Joining consensus session %s containing %u peers as %u with timeout %s\n",
3289  GNUNET_h2s (&m->session_id),
3290  session->num_peers,
3291  session->local_peer_idx,
3294  session->conclude_deadline),
3295  GNUNET_YES));
3296 
3297  session->set_listener
3298  = GNUNET_SET_listen (cfg,
3300  &session->global_id,
3301  &set_listen_cb,
3302  session);
3303 
3305  GNUNET_NO);
3307  GNUNET_NO);
3309  GNUNET_NO);
3311  GNUNET_NO);
3312 
3313  {
3314  struct SetEntry *client_set;
3315 
3316  client_set = GNUNET_new (struct SetEntry);
3317  client_set->h = GNUNET_SET_create (cfg,
3319  struct SetHandle *sh = GNUNET_new (struct SetHandle);
3320  sh->h = client_set->h;
3322  session->set_handles_tail,
3323  sh);
3324  client_set->key = ((struct SetKey) { SET_KIND_CURRENT, 0, 0 });
3325  put_set (session,
3326  client_set);
3327  }
3328 
3329  session->peers_blacklisted = GNUNET_new_array (session->num_peers,
3330  int);
3331 
3332  /* Just construct the task graph,
3333  but don't run anything until the client calls conclude. */
3334  construct_task_graph (session);
3336 }
3337 
3338 
3346 static int
3348  const struct GNUNET_CONSENSUS_ElementMessage *msg)
3349 {
3350  return GNUNET_OK;
3351 }
3352 
3353 
3360 static void
3362  const struct GNUNET_CONSENSUS_ElementMessage *msg)
3363 {
3364  struct ConsensusSession *session = cls;
3365  ssize_t element_size;
3366  struct GNUNET_SET_Handle *initial_set;
3367  struct ConsensusElement *ce;
3368 
3369  if (GNUNET_YES == session->conclude_started)
3370  {
3371  GNUNET_break (0);
3373  return;
3374  }
3375  element_size = ntohs (msg->header.size) - sizeof(*msg);
3376  ce = GNUNET_malloc (sizeof(struct ConsensusElement) + element_size);
3377  GNUNET_memcpy (&ce[1],
3378  &msg[1],
3379  element_size);
3380  ce->payload_type = msg->element_type;
3381 
3382  {
3383  struct SetKey key = { SET_KIND_CURRENT, 0, 0 };
3384  struct SetEntry *entry;
3385 
3386  entry = lookup_set (session,
3387  &key);
3388  GNUNET_assert (NULL != entry);
3389  initial_set = entry->h;
3390  }
3391 
3392  session->num_client_insert_pending++;
3393 
3394  {
3395  struct GNUNET_SET_Element element = {
3397  .size = sizeof(struct ConsensusElement) + element_size,
3398  .data = ce,
3399  };
3400 
3401  GNUNET_SET_add_element (initial_set,
3402  &element,
3403  NULL,
3404  NULL);
3405 #ifdef GNUNET_EXTRA_LOGGING
3407  "P%u: element %s added\n",
3408  session->local_peer_idx,
3409  debug_str_element (&element));
3410 #endif
3411  }
3412  GNUNET_free (ce);
3414 }
3415 
3416 
3423 static void
3425  const struct GNUNET_MessageHeader *message)
3426 {
3427  struct ConsensusSession *session = cls;
3428 
3429  if (GNUNET_YES == session->conclude_started)
3430  {
3431  /* conclude started twice */
3432  GNUNET_break (0);
3434  return;
3435  }
3437  "conclude requested\n");
3438  session->conclude_started = GNUNET_YES;
3439  install_step_timeouts (session);
3440  run_ready_steps (session);
3442 }
3443 
3444 
3450 static void
3451 shutdown_task (void *cls)
3452 {
3454  "shutting down\n");
3455  GNUNET_STATISTICS_destroy (statistics,
3456  GNUNET_NO);
3457  statistics = NULL;
3458 }
3459 
3460 
3468 static void
3469 run (void *cls,
3470  const struct GNUNET_CONFIGURATION_Handle *c,
3472 {
3473  cfg = c;
3474  if (GNUNET_OK !=
3476  &my_peer))
3477  {
3479  "Could not retrieve host identity\n");
3481  return;
3482  }
3483  statistics = GNUNET_STATISTICS_create ("consensus",
3484  cfg);
3486  NULL);
3487 }
3488 
3489 
3498 static void *
3500  struct GNUNET_SERVICE_Client *c,
3501  struct GNUNET_MQ_Handle *mq)
3502 {
3503  struct ConsensusSession *session = GNUNET_new (struct ConsensusSession);
3504 
3505  session->client = c;
3506  session->client_mq = mq;
3507  GNUNET_CONTAINER_DLL_insert (sessions_head,
3508  sessions_tail,
3509  session);
3510  return session;
3511 }
3512 
3513 
3521 static void
3523  struct GNUNET_SERVICE_Client *c,
3524  void *internal_cls)
3525 {
3526  struct ConsensusSession *session = internal_cls;
3527 
3528  if (NULL != session->set_listener)
3529  {
3531  session->set_listener = NULL;
3532  }
3533  GNUNET_CONTAINER_DLL_remove (sessions_head,
3534  sessions_tail,
3535  session);
3536  while (session->set_handles_head)
3537  {
3538  struct SetHandle *sh = session->set_handles_head;
3539 
3540  session->set_handles_head = sh->next;
3541  GNUNET_SET_destroy (sh->h);
3542  GNUNET_free (sh);
3543  }
3544  GNUNET_free (session);
3545 }
3546 
3547 
3552  "consensus",
3554  &run,
3557  NULL,
3558  GNUNET_MQ_hd_fixed_size (client_conclude,
3560  struct GNUNET_MessageHeader,
3561  NULL),
3562  GNUNET_MQ_hd_var_size (client_insert,
3565  NULL),
3566  GNUNET_MQ_hd_var_size (client_join,
3569  NULL),
3571 
3572 /* end of gnunet-service-consensus.c */
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
#define GNUNET_MESSAGE_TYPE_CONSENSUS_P2P_ROUND_CONTEXT
Provide context for a consensus round.
uint64_t first_size
Our set size from the first round.
Vote that an element should be removed.
struct FinishCls finish
void GNUNET_CONTAINER_multihashmap_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
Closure for both start_task and cancel_task.
static struct ReferendumEntry * lookup_rfn(struct ConsensusSession *session, const struct RfnKey *key)
int * peer_contested
Contestation state of the peer.
static GNUNET_NETWORK_STRUCT_END struct GNUNET_PeerIdentity me
Our own peer identity.
static int cmp_uint64_t(const void *pa, const void *pb)
struct GNUNET_CONTAINER_MultiHashMap * rfnmap
static int get_peer_idx(const struct GNUNET_PeerIdentity *peer, const struct ConsensusSession *session)
Search peer in the list of peers in session.
struct GNUNET_SET_ListenHandle * GNUNET_SET_listen(const struct GNUNET_CONFIGURATION_Handle *cfg, enum GNUNET_SET_OperationType op_type, const struct GNUNET_HashCode *app_id, GNUNET_SET_ListenCallback listen_cb, void *listen_cls)
Wait for set operation requests for the given application ID.
Definition: set_api.c:1017
static struct GNUNET_SERVICE_Handle * service
Handle to our service instance.
unsigned int subordinates_cap
int GNUNET_CONTAINER_multihashmap_iterator_next(struct GNUNET_CONTAINER_MultiHashMapIterator *iter, struct GNUNET_HashCode *key, const void **value)
Retrieve the next element from the hash map at the iterator&#39;s position.
int GNUNET_SET_remove_element(struct GNUNET_SET_Handle *set, const struct GNUNET_SET_Element *element, GNUNET_SET_Continuation cont, void *cont_cls)
Remove an element to the given set.
Definition: set_api.c:734
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
static struct GNUNET_VPN_RedirectionRequest * request
Opaque redirection request handle.
Definition: gnunet-vpn.c:41
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_ntoh(struct GNUNET_TIME_AbsoluteNBO a)
Convert absolute time from network byte order.
Definition: time.c:673
static unsigned int phase
Processing stage that we are in.
Definition: gnunet-arm.c:114
static struct DiffEntry * diff_create(void)
struct GNUNET_STATISTICS_Handle * statistics
Statistics handle.
int k1
Repetition counter.
static int check_client_join(void *cls, const struct GNUNET_CONSENSUS_JoinMessage *m)
Check join message.
static unsigned int element_size
static void try_finish_step_early(struct Step *step)
Weighted diff.
#define GNUNET_CONTAINER_DLL_insert(head, tail, element)
Insert an element at the head of a DLL.
int GNUNET_SET_add_element(struct GNUNET_SET_Handle *set, const struct GNUNET_SET_Element *element, GNUNET_SET_Continuation cont, void *cont_cls)
Add an element to the given set.
Definition: set_api.c:687
int * peer_commited
Stores, for every peer in the session, whether the peer finished the whole referendum.
If a value with the given key exists, replace it.
Consensus element, either marker or payload.
struct GNUNET_SET_ListenHandle * set_listener
Listener for requests from other peers.
static void shutdown_task(void *cls)
Called to clean up, after a shutdown has been requested.
uint16_t payload_type
Payload element_type, only valid if this is not a marker element.
static void commit_set(struct ConsensusSession *session, struct TaskEntry *task)
Commit the appropriate set for a task.
Handle for a set operation request from another peer.
Definition: set_api.c:115
struct SetHandle * set_handles_head
static void * client_connect_cb(void *cls, struct GNUNET_SERVICE_Client *c, struct GNUNET_MQ_Handle *mq)
Callback called when a client connects to the service.
Handle to a service.
Definition: service.c:116
static void apply_diff_to_rfn(struct DiffEntry *diff, struct ReferendumEntry *rfn, uint16_t voting_peer, uint16_t num_peers)
int16_t repetition
Repetition of the gradecast phase.
static void construct_task_graph(struct ConsensusSession *session)
Element should be added to the result set of the remote peer, i.e.
static void task_start_reconcile(struct TaskEntry *task)
static void put_diff(struct ConsensusSession *session, struct DiffEntry *diff)
struct GNUNET_CONTAINER_MultiHashMapIterator * GNUNET_CONTAINER_multihashmap_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap *map)
Create an iterator for a multihashmap.
struct ReferendumEntry * rfn_create(uint16_t size)
static void task_start_grade(struct TaskEntry *task)
static void rfn_contest(struct ReferendumEntry *rfn, uint16_t contested_peer)
struct GNUNET_SCHEDULER_Task * GNUNET_SCHEDULER_add_shutdown(GNUNET_SCHEDULER_TaskCallback task, void *task_cls)
Schedule a new task to be run on shutdown, that is when a CTRL-C signal is received, or when GNUNET_SCHEDULER_shutdown() is being invoked.
Definition: scheduler.c:1331
static void task_start_finish(struct TaskEntry *task)
Element stored in a set.
struct GNUNET_STATISTICS_Handle * GNUNET_STATISTICS_create(const char *subsystem, const struct GNUNET_CONFIGURATION_Handle *cfg)
Get handle for the statistics service.
enum RfnKind rfn_kind
struct GNUNET_SET_Handle * GNUNET_SET_create(const struct GNUNET_CONFIGURATION_Handle *cfg, enum GNUNET_SET_OperationType op)
Create an empty set, supporting the specified operation.
Definition: set_api.c:657
uint16_t is_contested
Non-zero if this set reconciliation had elements removed because they were contested.
Element should be added to the result set of the local peer, i.e.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_SET_Handle * h
static struct ConsensusSession * sessions_tail
Linked list of sessions this peer participates in.
static const char * phasename(uint16_t phase)
struct GNUNET_CONTAINER_MultiHashMap * setmap
struct ConsensusSession * session
struct ConsensusSession * next
Consensus sessions are kept in a DLL.
static void arrange_peers(uint16_t *p1, uint16_t *p2, uint16_t n)
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_MQ_hd_fixed_size(name, code, str, ctx)
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static void finish_task(struct TaskEntry *task)
static int peer_id_cmp(const void *h1, const void *h2)
Compare two peer identities (for qsort()).
unsigned int num_peers
Number of other peers in the consensus.
#define GNUNET_memdup(buf, size)
Allocate and initialize a block of memory.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
unsigned int tasks_len
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct GNUNET_SET_OperationHandle * GNUNET_SET_prepare(const struct GNUNET_PeerIdentity *other_peer, const struct GNUNET_HashCode *app_id, const struct GNUNET_MessageHeader *context_msg, enum GNUNET_SET_ResultMode result_mode, struct GNUNET_SET_Option options[], GNUNET_SET_ResultIterator result_cb, void *result_cls)
Prepare a set operation to be evaluated with another peer.
Definition: set_api.c:813
static struct GNUNET_PeerIdentity my_peer
Peer that runs this service.
static void compute_global_id(struct ConsensusSession *session, const struct GNUNET_HashCode *local_session_id)
Compute a global, (hopefully) unique consensus session id, from the local id of the consensus session...
static struct GNUNET_SCHEDULER_Task * t
Main task.
uint16_t size
The length of the struct (in bytes, including the length field itself), in big-endian format...
void GNUNET_STATISTICS_destroy(struct GNUNET_STATISTICS_Handle *h, int sync_first)
Destroy a handle (free all state associated with it).
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
struct GNUNET_TIME_AbsoluteNBO start
Start time for the consensus.
Definition: consensus.h:58
struct Step * next
All steps of one session are in a linked list for easier deallocation.
void GNUNET_SCHEDULER_shutdown(void)
Request the shutdown of a scheduler.
Definition: scheduler.c:531
Handle for the service.
const struct GNUNET_SET_Element * element
GNUNET_SERVICE_MAIN("consensus", GNUNET_SERVICE_OPTION_NONE, &run, &client_connect_cb, &client_disconnect_cb, NULL, GNUNET_MQ_hd_fixed_size(client_conclude, GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_CONCLUDE, struct GNUNET_MessageHeader, NULL), GNUNET_MQ_hd_var_size(client_insert, GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_INSERT, struct GNUNET_CONSENSUS_ElementMessage, NULL), GNUNET_MQ_hd_var_size(client_join, GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_JOIN, struct GNUNET_CONSENSUS_JoinMessage, NULL), GNUNET_MQ_handler_end())
Define "main" method using service macro.
Last result set from a gradecast.
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
struct GNUNET_CONTAINER_MultiHashMap * taskmap
size_t pending_prereq
Counter for the prerequisites of this step.
static struct ConsensusSession * sessions_head
Linked list of sessions this peer participates in.
void GNUNET_SET_copy_lazy(struct GNUNET_SET_Handle *set, GNUNET_SET_CopyReadyCallback cb, void *cls)
Definition: set_api.c:1194
Success, all elements have been sent (and received).
struct GNUNET_HashCode session_id
Session id of the consensus.
Definition: consensus.h:53
Internal representation of the hash map.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
void GNUNET_SET_element_hash(const struct GNUNET_SET_Element *element, struct GNUNET_HashCode *ret_hash)
Hash a set element.
Definition: set_api.c:1246
struct SetKey input_set
#define GNUNET_NETWORK_STRUCT_BEGIN
Define as empty, GNUNET_PACKED should suffice, but this won&#39;t work on W32.
struct Step * prev
All steps of one session are in a linked list for easier deallocation.
const void * data
Actual data of the element.
Sent as context message for set reconciliation.
int * peers_blacklisted
Array of peers with length &#39;num_peers&#39;.
void * GNUNET_CONTAINER_multihashmap_get(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Given a key find a value in the map matching the key.
static void set_copy_cb(void *cls, struct GNUNET_SET_Handle *copy)
Handle to a client that is connected to a service.
Definition: service.c:250
void GNUNET_SET_destroy(struct GNUNET_SET_Handle *set)
Destroy the set handle, and free all associated resources.
Definition: set_api.c:772
uint32_t num_peers
Number of peers (at the end of this message) that want to participate in the consensus.
Definition: consensus.h:48
struct ConsensusElement ce
static void construct_task_graph_gradecast(struct ConsensusSession *session, uint16_t rep, uint16_t lead, struct Step *step_before, struct Step *step_after)
Construct the task graph for a single gradecast.
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:104
static void handle_client_join(void *cls, const struct GNUNET_CONSENSUS_JoinMessage *m)
Called when a client wants to join a consensus session.
static void finish_step(struct Step *step)
struct GNUNET_PeerIdentity * peers
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
#define GNUNET_MQ_msg_extra(mvar, esize, type)
Allocate an envelope, with extra space allocated after the space needed by the message struct...
Definition: gnunet_mq_lib.h:52
struct GNUNET_TIME_Absolute conclude_start
Time when the conclusion of the consensus should begin.
static void create_set_copy_for_task(struct TaskEntry *task, struct SetKey *src_set_key, struct SetKey *dst_set_key)
Call the start function of the given task again after we created a copy of the given set...
uint16_t type
The type of the message (GNUNET_MESSAGE_TYPE_XXXX), in big-endian format.
void(* TaskFunc)(struct TaskEntry *task)
int16_t peer2
Number of the second peer in canonical order.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
static struct Step * create_step(struct ConsensusSession *session, int round, int early_finishable)
, &#39; bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_...
void GNUNET_CRYPTO_hash_create_random(enum GNUNET_CRYPTO_Quality mode, struct GNUNET_HashCode *result)
Create a random hash code.
Definition: crypto_hash.c:144
struct GNUNET_MessageHeader header
Type: GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_JOIN.
Definition: consensus.h:42
struct Step ** subordinates
The other peer refused to to the operation with us, or something went wrong.
static int check_client_insert(void *cls, const struct GNUNET_CONSENSUS_ElementMessage *msg)
Called when a client performs an insert operation.
struct GNUNET_CONTAINER_MultiHashMap * changes
static void diff_insert(struct DiffEntry *diff, int weight, const struct GNUNET_SET_Element *element)
static void install_step_timeouts(struct ConsensusSession *session)
static struct DiffEntry * lookup_diff(struct ConsensusSession *session, const struct DiffKey *key)
struct SetHandle * set_handles_tail
uint64_t lower_bound
Bounded Eppstein lower bound.
static void set_listen_cb(void *cls, const struct GNUNET_PeerIdentity *other_peer, const struct GNUNET_MessageHeader *context_msg, struct GNUNET_SET_Request *request)
Called when another peer wants to do a set operation with the local peer.
#define GNUNET_MQ_hd_var_size(name, code, str, ctx)
static struct TaskEntry * lookup_task(const struct ConsensusSession *session, const struct TaskKey *key)
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:48
static void handle_client_conclude(void *cls, const struct GNUNET_MessageHeader *message)
Called when a client performs the conclude operation.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
struct TaskEntry * task
Task to finish once all changes are through.
GNUNET_SET_Status
Status for the result callback.
Message with an element.
Definition: consensus.h:72
static struct SolverHandle * sh
#define GNUNET_MIN(a, b)
Definition: gnunet_common.h:93
struct DiffKey key
Vote that nothing should change.
const char * GNUNET_STRINGS_relative_time_to_string(struct GNUNET_TIME_Relative delta, int do_round)
Give relative time in human-readable fancy format.
Definition: strings.c:702
struct SetKey dst_set_key
int weight
Positive weight for &#39;add&#39;, negative weights for &#39;remove&#39;.
uint16_t status
See PRISM_STATUS_*-constants.
static char buf[2048]
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
static uint16_t task_other_peer(struct TaskEntry *task)
static void cleanup(void *cls)
Function scheduled as very last function, cleans up after us.
static const struct GNUNET_CONFIGURATION_Handle * cfg
Configuration of the consensus service.
p2p message definitions for consensus
struct SetKey input_set
struct GNUNET_MessageHeader header
Type: Either GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_RECEIVED_ELEMENT or GNUNET_MESSAGE_TYPE_CONSENSUS_C...
Definition: consensus.h:79
static void client_disconnect_cb(void *cls, struct GNUNET_SERVICE_Client *c, void *internal_cls)
Callback called when a client disconnected from the service.
void GNUNET_STATISTICS_set(struct GNUNET_STATISTICS_Handle *handle, const char *name, uint64_t value, int make_persistent)
Set statistic value for the peer.
Apply a repetition of the all-to-all gradecast to the current set.
A 512-bit hashcode.
Client gets notified of the required changes for both the local and the remote set.
void GNUNET_SERVICE_client_drop(struct GNUNET_SERVICE_Client *c)
Ask the server to disconnect from the given client.
Definition: service.c:2323
struct ConsensusSession * prev
Consensus sessions are kept in a DLL.
char * debug_name
Human-readable name for the task, used for debugging.
enum DiffKind diff_kind
Opaque handle to a set.
Definition: set_api.c:49
static const char * setname(uint16_t kind)
int GNUNET_CONFIGURATION_get_value_string(const struct GNUNET_CONFIGURATION_Handle *cfg, const char *section, const char *option, char **value)
Get a configuration value that should be a string.
static void task_start_eval_echo(struct TaskEntry *task)
struct TaskKey key
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:36
There must only be one value per key; storing a value should fail if a value under the same key alrea...
static uint16_t rfn_noncontested(struct ReferendumEntry *rfn)
struct TaskEntry ** tasks
Tasks that this step is composed of.
struct GNUNET_TESTBED_Peer * peer
The peer associated with this model.
static struct SetEntry * lookup_set(struct ConsensusSession *session, const struct SetKey *key)
struct GNUNET_HashCode key
The key used in the DHT.
int early_finishable
When we&#39;re doing an early finish, how should this step be treated? If GNUNET_YES, the step will be ma...
static unsigned int size
Size of the "table".
Definition: peer.c:67
#define GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_RECEIVED_ELEMENT
Sent by service when a new element is added.
static void step_depend_on(struct Step *step, struct Step *dep)
Record dep as a dependency of step.
struct GNUNET_CONTAINER_MultiHashMap * diffmap
int is_contested
GNUNET_YES if the set resulted from applying a referendum with contested elements.
static void initialize_session_peer_list(struct ConsensusSession *session, const struct GNUNET_CONSENSUS_JoinMessage *join_msg)
Create the sorted list of peers for the session, add the local peer if not in the join message...
struct GNUNET_HashCode global_id
Global consensus identification, computed from the session id and participating authorities.
#define GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_CONCLUDE
Sent by client to service in order to start the consensus conclusion.
void GNUNET_SET_listen_cancel(struct GNUNET_SET_ListenHandle *lh)
Cancel the given listen operation.
Definition: set_api.c:1051
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
struct GNUNET_MQ_Handle * client_mq
Queued messages to the client.
Option for set operations.
int GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
Sent by the client to the service, when the client wants the service to join a consensus session...
Definition: consensus.h:37
static unsigned int num_peers
#define GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_INSERT
Insert an element.
static void put_rfn(struct ConsensusSession *session, struct ReferendumEntry *rfn)
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
unsigned int is_finished
struct DiffKey output_diff
int16_t leader
Leader in the gradecast phase.
Handle to an operation.
Definition: set_api.c:135
Handle to a message queue.
Definition: mq.c:85
A consensus session consists of one local client and the remote authorities.
static struct GNUNET_CRYPTO_PowSalt salt
Salt for PoW calcualations.
Tuple of integers that together identify a task uniquely.
static void run_ready_steps(struct ConsensusSession *session)
#define GNUNET_NETWORK_STRUCT_END
Define as empty, GNUNET_PACKED should suffice, but this won&#39;t work on W32;.
unsigned int round
Synchrony round of the task.
struct GNUNET_HashCode rand
#define GNUNET_MQ_msg_header(type)
Allocate a GNUNET_MQ_Envelope, where the message only consists of a header.
Definition: gnunet_mq_lib.h:76
static struct GNUNET_FS_PublishContext * pc
Handle to FS-publishing operation.
The identity of the host (wraps the signing key of the peer).
int GNUNET_SET_commit(struct GNUNET_SET_OperationHandle *oh, struct GNUNET_SET_Handle *set)
Commit a set to be used with a set operation.
Definition: set_api.c:1128
static const char * diffname(uint16_t kind)
uint16_t kind
A value from &#39;enum PhaseKind&#39;.
uint8_t marker
Is this a marker element?
Vote that an element should be added.
static void task_cancel_reconcile(struct TaskEntry *task)
static void set_result_cb(void *cls, const struct GNUNET_SET_Element *element, uint64_t current_size, enum GNUNET_SET_Status status)
Callback for set operation results.
#define GNUNET_PACKED
gcc-ism to get packed structs.
unsigned int finished_tasks
configuration data
Definition: configuration.c:84
struct GNUNET_MessageHeader header
Type: GNUNET_MESSAGE_TYPE_CONSENSUS_P2P_ROUND_CONTEXT.
struct GNUNET_SET_Handle * h
int GNUNET_CRYPTO_hash_cmp(const struct GNUNET_HashCode *h1, const struct GNUNET_HashCode *h2)
Compare function for HashCodes, producing a total ordering of all hashcodes.
Definition: crypto_hash.c:311
struct SetHandle * next
uint16_t element_type
Type: GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_NEW_ELEMENT.
Definition: consensus.h:84
Block type for consensus elements.
#define GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_CONCLUDE_DONE
Sent by service to client in order to signal a completed consensus conclusion.
int16_t leader
Leader in the gradecast phase.
uint16_t size
Number of bytes in the buffer pointed to by data.
struct Step * step
struct GNUNET_MQ_Handle * mq
Definition: 003.c:5
const struct GNUNET_SET_Element * element
#define GNUNET_log(kind,...)
Entry in list of pending tasks.
Definition: scheduler.c:134
unsigned int local_peer_idx
Index of the local peer in the peers array.
unsigned int is_running
#define GNUNET_MESSAGE_TYPE_CONSENSUS_CLIENT_JOIN
Join a consensus session.
Opaque handle to a listen operation.
Definition: set_api.c:186
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
enum ReferendumVote proposal
Proposal for this element, can only be VOTE_ADD or VOTE_REMOVE.
int GNUNET_CRYPTO_get_peer_identity(const struct GNUNET_CONFIGURATION_Handle *cfg, struct GNUNET_PeerIdentity *dst)
Retrieve the identity of the host&#39;s peer.
struct SetOpCls setop
unsigned int num_client_insert_pending
static const char * rfnname(uint16_t kind)
static void run(void *cls, const struct GNUNET_CONFIGURATION_Handle *c, struct GNUNET_SERVICE_Handle *service)
Start processing consensus requests.
struct GNUNET_TIME_Absolute conclude_deadline
Timeout for all rounds together, single rounds will schedule a timeout task with a fraction of the co...
void GNUNET_SET_operation_cancel(struct GNUNET_SET_OperationHandle *oh)
Cancel the given set operation.
Definition: set_api.c:516
static void handle_client_insert(void *cls, const struct GNUNET_CONSENSUS_ElementMessage *msg)
Called when a client performs an insert operation.
static int send_to_client_iter(void *cls, const struct GNUNET_SET_Element *element)
Send the final result set of the consensus to the client, element by element.
struct GNUNET_SET_Element * GNUNET_SET_element_dup(const struct GNUNET_SET_Element *element)
Create a copy of an element.
Definition: set_api.c:1223
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model
struct GNUNET_SET_OperationHandle * op
Header for all communications.
struct GNUNET_SERVICE_Client * client
Client that inhabits the session.
Time for absolute times used by GNUnet, in microseconds.
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_difference(struct GNUNET_TIME_Absolute start, struct GNUNET_TIME_Absolute end)
Compute the time difference between the given start and end times.
Definition: time.c:354
static void rfn_commit(struct ReferendumEntry *rfn, uint16_t commit_peer)
void GNUNET_MQ_send(struct GNUNET_MQ_Handle *mq, struct GNUNET_MQ_Envelope *ev)
Send a message with the given message queue.
Definition: mq.c:355
struct RfnKey output_rfn
static void set_mutation_done(void *cls)
union TaskFuncCls cls
struct SetHandle * prev
static void rfn_majority(const struct ReferendumEntry *rfn, const struct RfnElementInfo *ri, uint16_t *ret_majority, enum ReferendumVote *ret_vote)
For a given majority, count what the outcome is (add/remove/keep), and give the number of peers that ...
unsigned int tasks_cap
int16_t peer1
Number of the first peer in canonical order.
struct ConsensusElement ce
static void start_task(struct ConsensusSession *session, struct TaskEntry *task)
int * votes
GNUNET_YES if the peer votes for the proposal.
Set union, return all elements that are in at least one of the sets.
static struct GNUNET_IDENTITY_EgoLookup * el
EgoLookup.
Definition: gnunet-abd.c:51
int GNUNET_SET_iterate(struct GNUNET_SET_Handle *set, GNUNET_SET_ElementIterator iter, void *iter_cls)
Iterate over all elements in the given set.
Definition: set_api.c:1172
unsigned int subordinates_len
struct SetKey output_set
enum SetKind set_kind
static void task_start_apply_round(struct TaskEntry *task)
Apply the result from one round of gradecasts (i.e.
static void put_set(struct ConsensusSession *session, struct SetEntry *set)
struct GNUNET_CONTAINER_MultiHashMap * rfn_elements
int GNUNET_CRYPTO_kdf(void *result, size_t out_len, const void *xts, size_t xts_len, const void *skm, size_t skm_len,...)
Derive key.
Definition: crypto_kdf.c:90
int k2
Leader (or 0).
void GNUNET_SERVICE_client_continue(struct GNUNET_SERVICE_Client *c)
Continue receiving further messages from the given client.
Definition: service.c:2242
#define GNUNET_MQ_handler_end()
End-marker for the handlers array.
struct GNUNET_TIME_AbsoluteNBO deadline
Deadline for conclude.
Definition: consensus.h:63
int early_stopping
State of our early stopping scheme.
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
static void rfn_vote(struct ReferendumEntry *rfn, uint16_t voting_peer, enum ReferendumVote vote, const struct GNUNET_SET_Element *element)
static void put_task(struct GNUNET_CONTAINER_MultiHashMap *taskmap, struct TaskEntry *t)
#define GNUNET_malloc(size)
Wrapper around malloc.
int16_t peer1
Number of the first peer in canonical order.
struct SetKey key
int16_t peer2
Number of the second peer in canonical order.
uint64_t GNUNET_ntohll(uint64_t n)
Convert unsigned 64-bit integer to host byte order.
Definition: common_endian.c:53
struct TaskEntry * task
#define GNUNET_free(ptr)
Wrapper around free.
uint16_t element_type
Application-specific element type.
int16_t repetition
Repetition of the gradecast phase.
struct GNUNET_SET_OperationHandle * GNUNET_SET_accept(struct GNUNET_SET_Request *request, enum GNUNET_SET_ResultMode result_mode, struct GNUNET_SET_Option options[], GNUNET_SET_ResultIterator result_cb, void *result_cls)
Accept a request we got via GNUNET_SET_listen().
Definition: set_api.c:1085
struct GNUNET_SCHEDULER_Task * timeout_task
Task that will run this step despite any pending prerequisites.
Fail set operations when the other peer shows weird behavior that might by a Byzantine fault...
uint16_t kind
A value from &#39;enum PhaseKind&#39;.