From fa130fbc186ef1ed28032b15d79e3d88bf49634a Mon Sep 17 00:00:00 2001 From: Frederic Suter Date: Mon, 16 Mar 2020 09:27:25 +0100 Subject: [PATCH] convert (and simplify a bit) dht-kademlia example --- MANIFEST.in | 27 +- examples/c/CMakeLists.txt | 35 +- .../msg => c}/dht-kademlia/answer.c | 64 +-- .../msg => c}/dht-kademlia/answer.h | 8 +- .../msg => c}/dht-kademlia/common.h | 8 +- examples/c/dht-kademlia/dht-kademlia.c | 103 +++++ .../msg => c}/dht-kademlia/dht-kademlia.tesh | 4 +- .../msg => c}/dht-kademlia/dht-kademlia_d.xml | 0 .../msg => c}/dht-kademlia/generate.py | 0 examples/c/dht-kademlia/message.c | 29 ++ examples/c/dht-kademlia/message.h | 30 ++ examples/c/dht-kademlia/node.c | 377 ++++++++++++++++++ examples/c/dht-kademlia/node.h | 72 ++++ .../msg => c}/dht-kademlia/routing_table.c | 27 +- .../msg => c}/dht-kademlia/routing_table.h | 18 +- examples/deprecated/msg/CMakeLists.txt | 39 +- .../msg/dht-kademlia/dht-kademlia.c | 377 ------------------ .../msg/dht-kademlia/dht-kademlia.h | 23 -- examples/deprecated/msg/dht-kademlia/node.c | 172 -------- examples/deprecated/msg/dht-kademlia/node.h | 55 --- examples/deprecated/msg/dht-kademlia/task.c | 78 ---- examples/deprecated/msg/dht-kademlia/task.h | 41 -- examples/s4u/dht-kademlia/node.cpp | 1 + teshsuite/msg/CMakeLists.txt | 3 +- 24 files changed, 731 insertions(+), 860 deletions(-) rename examples/{deprecated/msg => c}/dht-kademlia/answer.c (73%) rename examples/{deprecated/msg => c}/dht-kademlia/answer.h (87%) rename examples/{deprecated/msg => c}/dht-kademlia/common.h (81%) create mode 100644 examples/c/dht-kademlia/dht-kademlia.c rename examples/{deprecated/msg => c}/dht-kademlia/dht-kademlia.tesh (92%) rename examples/{deprecated/msg => c}/dht-kademlia/dht-kademlia_d.xml (100%) rename examples/{deprecated/msg => c}/dht-kademlia/generate.py (100%) create mode 100644 examples/c/dht-kademlia/message.c create mode 100644 examples/c/dht-kademlia/message.h create mode 100644 examples/c/dht-kademlia/node.c create mode 100644 examples/c/dht-kademlia/node.h rename examples/{deprecated/msg => c}/dht-kademlia/routing_table.c (79%) rename examples/{deprecated/msg => c}/dht-kademlia/routing_table.h (66%) delete mode 100644 examples/deprecated/msg/dht-kademlia/dht-kademlia.c delete mode 100644 examples/deprecated/msg/dht-kademlia/dht-kademlia.h delete mode 100644 examples/deprecated/msg/dht-kademlia/node.c delete mode 100644 examples/deprecated/msg/dht-kademlia/node.h delete mode 100644 examples/deprecated/msg/dht-kademlia/task.c delete mode 100644 examples/deprecated/msg/dht-kademlia/task.h diff --git a/MANIFEST.in b/MANIFEST.in index 2bab98f4de..09810cb88d 100644 --- a/MANIFEST.in +++ b/MANIFEST.in @@ -77,6 +77,19 @@ include examples/c/cloud-migration/cloud-migration.c include examples/c/cloud-migration/cloud-migration.tesh include examples/c/cloud-simple/cloud-simple.c include examples/c/cloud-simple/cloud-simple.tesh +include examples/c/dht-kademlia/answer.c +include examples/c/dht-kademlia/answer.h +include examples/c/dht-kademlia/common.h +include examples/c/dht-kademlia/dht-kademlia.c +include examples/c/dht-kademlia/dht-kademlia.tesh +include examples/c/dht-kademlia/dht-kademlia_d.xml +include examples/c/dht-kademlia/generate.py +include examples/c/dht-kademlia/message.c +include examples/c/dht-kademlia/message.h +include examples/c/dht-kademlia/node.c +include examples/c/dht-kademlia/node.h +include examples/c/dht-kademlia/routing_table.c +include examples/c/dht-kademlia/routing_table.h include examples/c/energy-exec-ptask/energy-exec-ptask.c include examples/c/energy-exec-ptask/energy-exec-ptask.tesh include examples/c/energy-exec/energy-exec.c @@ -225,20 +238,6 @@ include examples/deprecated/java/trace/pingpong/Receiver.java include examples/deprecated/java/trace/pingpong/Sender.java include examples/deprecated/java/trace/pingpong/trace-pingpong.tesh include examples/deprecated/msg/README.doc -include examples/deprecated/msg/dht-kademlia/answer.c -include examples/deprecated/msg/dht-kademlia/answer.h -include examples/deprecated/msg/dht-kademlia/common.h -include examples/deprecated/msg/dht-kademlia/dht-kademlia.c -include examples/deprecated/msg/dht-kademlia/dht-kademlia.h -include examples/deprecated/msg/dht-kademlia/dht-kademlia.tesh -include examples/deprecated/msg/dht-kademlia/dht-kademlia_d.xml -include examples/deprecated/msg/dht-kademlia/generate.py -include examples/deprecated/msg/dht-kademlia/node.c -include examples/deprecated/msg/dht-kademlia/node.h -include examples/deprecated/msg/dht-kademlia/routing_table.c -include examples/deprecated/msg/dht-kademlia/routing_table.h -include examples/deprecated/msg/dht-kademlia/task.c -include examples/deprecated/msg/dht-kademlia/task.h include examples/deprecated/msg/dht-pastry/dht-pastry.c include examples/deprecated/msg/dht-pastry/dht-pastry.tesh include examples/deprecated/msg/dht-pastry/dht-pastry_d.xml diff --git a/examples/c/CMakeLists.txt b/examples/c/CMakeLists.txt index b354060957..8126348a19 100644 --- a/examples/c/CMakeLists.txt +++ b/examples/c/CMakeLists.txt @@ -36,6 +36,16 @@ foreach (file chainsend broadcaster peer) endforeach() set(teshsuite_src ${teshsuite_src} ${CMAKE_CURRENT_SOURCE_DIR}/app-chainsend/chainsend.h) +#DHT-Kademlia +add_executable (dht-kademlia-c EXCLUDE_FROM_ALL dht-kademlia/dht-kademlia.c dht-kademlia/node.c dht-kademlia/routing_table.c dht-kademlia/message.c dht-kademlia/answer.c) +target_link_libraries(dht-kademlia-c simgrid) +set_target_properties(dht-kademlia-c PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/dht-kademlia) +add_dependencies(tests dht-kademlia-c) + +foreach (file answer node routing_table message) + set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/${file}.c ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/${file}.h) +endforeach() + # Add all extra files to the archive #################################### @@ -43,8 +53,11 @@ set(teshsuite_src ${teshsuite_src} PARENT_SCOPE) set(tesh_files ${tesh_files} ${CMAKE_CURRENT_SOURCE_DIR}/app-chainsend/app-chainsend.tesh ${CMAKE_CURRENT_SOURCE_DIR}/app-masterworker/app-masterworker-multicore.tesh ${CMAKE_CURRENT_SOURCE_DIR}/app-masterworker/app-masterworker-vivaldi.tesh + ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/dht-kademlia.tesh PARENT_SCOPE) - +set(bin_files ${bin_files} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/generate.py PARENT_SCOPE) +set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/common.h + ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/dht-kademlia.c PARENT_SCOPE) set(xml_files ${xml_files} ${CMAKE_CURRENT_SOURCE_DIR}/actor-create/actor-create_d.xml ${CMAKE_CURRENT_SOURCE_DIR}/actor-lifetime/actor-lifetime_d.xml ${CMAKE_CURRENT_SOURCE_DIR}/actor-yield/actor-yield_d.xml @@ -59,6 +72,7 @@ set(xml_files ${xml_files} ${CMAKE_CURRENT_SOURCE_DIR}/actor-create/actor-cr ${CMAKE_CURRENT_SOURCE_DIR}/async-wait/async-wait4_d.xml ${CMAKE_CURRENT_SOURCE_DIR}/async-waitall/async-waitall_d.xml ${CMAKE_CURRENT_SOURCE_DIR}/async-waitany/async-waitany_d.xml + ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/dht-kademlia_d.xml ${CMAKE_CURRENT_SOURCE_DIR}/io-file-remote/io-file-remote_d.xml ${CMAKE_CURRENT_SOURCE_DIR}/platform-properties/platform-properties_d.xml PARENT_SCOPE) @@ -90,3 +104,22 @@ ADD_TESH_FACTORIES(app-masterworker-vivaldi "thread;ucontext;raw;boost" --setenv bindir=${CMAKE_BINARY_DIR}/examples/c/app-masterworker --setenv platfdir=${CMAKE_HOME_DIRECTORY}/examples/platforms ${CMAKE_HOME_DIRECTORY}/examples/c/app-masterworker/app-masterworker-vivaldi.tesh) +ADD_TESH_FACTORIES(c-dht-kademlia "thread;ucontext;raw;boost" + --setenv bindir=${CMAKE_BINARY_DIR}/examples/c/dht-kademlia + --setenv srcdir=${CMAKE_HOME_DIRECTORY}/examples/c/dht-kademlia + --setenv platfdir=${CMAKE_HOME_DIRECTORY}/examples/platforms + ${CMAKE_HOME_DIRECTORY}/examples/c/dht-kademlia/dht-kademlia.tesh) + +if(CMAKE_SYSTEM_NAME STREQUAL "SunOS" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "i386" AND CMAKE_SIZEOF_VOID_P EQUAL 8) + # Thread-local storage (TLS) is needed for parallel execution, but it doesn't + # play well with Ucontexts on 64bit SunOS (at least on x86_64). + set(parallel-factories "thread;raw;boost") +else() + set(parallel-factories "thread;ucontext;raw;boost") +endif() + +ADD_TESH_FACTORIES(c-dht-kademlia-parallel "${parallel-factories}" --cfg contexts/nthreads:4 ${CONTEXTS_SYNCHRO} + --setenv bindir=${CMAKE_BINARY_DIR}/examples/c/dht-kademlia + --setenv srcdir=${CMAKE_HOME_DIRECTORY}/examples/c/dht-kademlia + --setenv platfdir=${CMAKE_HOME_DIRECTORY}/examples/platforms + ${CMAKE_HOME_DIRECTORY}/examples/c/dht-kademlia/dht-kademlia.tesh) diff --git a/examples/deprecated/msg/dht-kademlia/answer.c b/examples/c/dht-kademlia/answer.c similarity index 73% rename from examples/deprecated/msg/dht-kademlia/answer.c rename to examples/c/dht-kademlia/answer.c index 8b61b75691..916cf1b79b 100644 --- a/examples/deprecated/msg/dht-kademlia/answer.c +++ b/examples/c/dht-kademlia/answer.c @@ -7,14 +7,14 @@ #include "answer.h" #include "node.h" -XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(msg_kademlia_node); +XBT_LOG_EXTERNAL_DEFAULT_CATEGORY(dht_kademlia_node); /** Initialize a node answer object. */ answer_t answer_init(unsigned int destination_id) { - answer_t answer = xbt_new(s_answer_t, 1); - answer->nodes = xbt_dynar_new(sizeof(node_contact_t), NULL); - answer->size = 0; + answer_t answer = xbt_new(s_answer_t, 1); + answer->nodes = xbt_dynar_new(sizeof(node_contact_t), NULL); + answer->size = 0; answer->destination_id = destination_id; return answer; @@ -25,7 +25,7 @@ void answer_free(answer_t answer) { unsigned int i; for (i = 0; i < answer->size; i++) { - node_contact_free(*(void **) xbt_dynar_get_ptr(answer->nodes, i)); + node_contact_free(*(void**)xbt_dynar_get_ptr(answer->nodes, i)); } xbt_dynar_free(&answer->nodes); xbt_free(answer); @@ -37,23 +37,26 @@ void answer_print(const_answer_t answer) unsigned int cpt; node_contact_t contact; XBT_INFO("Searching %08x, size %u", answer->destination_id, answer->size); - xbt_dynar_foreach(answer->nodes, cpt, contact) { + xbt_dynar_foreach (answer->nodes, cpt, contact) { XBT_INFO("Node %08x: %08x is at distance %u", cpt, contact->id, contact->distance); } } /** @brief Merge two answer_t together, only keeping the best nodes - * @param destination the destination in which the nodes will be put - * @param source the source of the nodes to add - */ + * @param destination the destination in which the nodes will be put + * @param source the source of the nodes to add + */ unsigned int answer_merge(answer_t destination, const_answer_t source) { + if (destination == source) + return 0; + node_contact_t contact; node_contact_t contact_copy; unsigned int cpt; unsigned int nb_added = 0; /* TODO: Check if same destination */ - xbt_dynar_foreach(source->nodes, cpt, contact) { + xbt_dynar_foreach (source->nodes, cpt, contact) { if (answer_contains(destination, contact->id) == 0) { contact_copy = node_contact_copy(contact); xbt_dynar_push(destination->nodes, &contact_copy); @@ -67,31 +70,30 @@ unsigned int answer_merge(answer_t destination, const_answer_t source) } /** Helper to sort answer_t objects */ -static int _answer_sort_function(const void *e1, const void *e2) +static int _answer_sort_function(const void* e1, const void* e2) { const s_node_contact_t* c1 = *(const node_contact_t*)e1; const s_node_contact_t* c2 = *(const node_contact_t*)e2; if (c1->distance == c2->distance) return 0; + else if (c1->distance < c2->distance) + return -1; else - if (c1->distance < c2->distance) - return -1; - else - return 1; + return 1; } /** @brief Sorts a answer_t, by node distance. - * @param answer the answer to sort - * @param destination_id the id of the guy we are trying to find - */ + * @param answer the answer to sort + * @param destination_id the id of the guy we are trying to find + */ void answer_sort(const_answer_t answer) { xbt_dynar_sort(answer->nodes, &_answer_sort_function); } /** @brief Trims a answer_t, in order for it to have a size of less or equal to "BUCKET_SIZE" - * @param answer the answer_t to trim - */ + * @param answer the answer_t to trim + */ void answer_trim(answer_t answer) { node_contact_t value; @@ -104,10 +106,10 @@ void answer_trim(answer_t answer) } /** @brief Adds the content of a bucket unsigned into a answer object. - * @param bucket the bucket we have to had unsigned into - * @param answer the answer object we're going to put the data in - * @param destination_id the id of the guy we are trying to find. - */ + * @param bucket the bucket we have to had unsigned into + * @param answer the answer object we're going to put the data in + * @param destination_id the id of the guy we are trying to find. + */ void answer_add_bucket(const_bucket_t bucket, answer_t answer) { xbt_assert((bucket != NULL), "Provided a NULL bucket"); @@ -115,7 +117,7 @@ void answer_add_bucket(const_bucket_t bucket, answer_t answer) unsigned int cpt; unsigned int id; - xbt_dynar_foreach(bucket->nodes, cpt, id) { + xbt_dynar_foreach (bucket->nodes, cpt, id) { unsigned int distance = id ^ answer->destination_id; node_contact_t contact = node_contact_new(id, distance); xbt_dynar_push(answer->nodes, &contact); @@ -124,13 +126,13 @@ void answer_add_bucket(const_bucket_t bucket, answer_t answer) } /** @brief Returns if the id supplied is in the answer. - * @param id : id we're looking for - */ + * @param id : id we're looking for + */ unsigned int answer_contains(const_answer_t answer, unsigned int id) { unsigned int i = 0; node_contact_t contact; - xbt_dynar_foreach(answer->nodes, i, contact){ + xbt_dynar_foreach (answer->nodes, i, contact) { if (id == contact->id) { return 1; } @@ -139,9 +141,9 @@ unsigned int answer_contains(const_answer_t answer, unsigned int id) } /** @brief Returns if the destination we are trying to find is found - * @param answer the answer - * @return if the destination is found. - */ + * @param answer the answer + * @return if the destination is found. + */ unsigned int answer_destination_found(const_answer_t answer) { if (xbt_dynar_is_empty(answer->nodes)) { diff --git a/examples/deprecated/msg/dht-kademlia/answer.h b/examples/c/dht-kademlia/answer.h similarity index 87% rename from examples/deprecated/msg/dht-kademlia/answer.h rename to examples/c/dht-kademlia/answer.h index 97838e0a25..9e617ef13f 100644 --- a/examples/deprecated/msg/dht-kademlia/answer.h +++ b/examples/c/dht-kademlia/answer.h @@ -6,17 +6,17 @@ #ifndef _KADEMLIA_EXAMPLES_ANSWER_H_ #define _KADEMLIA_EXAMPLES_ANSWER_H_ -#include #include "routing_table.h" +#include /* Node query answer. contains the elements closest to the id given. */ typedef struct s_node_answer { unsigned int destination_id; - xbt_dynar_t nodes; //Dynar of node_contact_t + xbt_dynar_t nodes; // Dynar of node_contact_t unsigned int size; } s_answer_t; -typedef s_answer_t *answer_t; +typedef s_answer_t* answer_t; typedef const s_answer_t* const_answer_t; answer_t answer_init(unsigned int destination_id); @@ -29,4 +29,4 @@ void answer_add_bucket(const_bucket_t bucket, answer_t answer); unsigned int answer_contains(const_answer_t answer, unsigned int id); unsigned int answer_destination_found(const_answer_t answer); -#endif /* _KADEMLIA_EXAMPLES_ANSWER_H_ */ +#endif /* _KADEMLIA_EXAMPLES_ANSWER_H_ */ diff --git a/examples/deprecated/msg/dht-kademlia/common.h b/examples/c/dht-kademlia/common.h similarity index 81% rename from examples/deprecated/msg/dht-kademlia/common.h rename to examples/c/dht-kademlia/common.h index 6e54aebc99..4a730ee893 100644 --- a/examples/deprecated/msg/dht-kademlia/common.h +++ b/examples/c/dht-kademlia/common.h @@ -4,8 +4,8 @@ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#ifndef _KADEMLIA_EXAMPLES_COMMON -#define _KADEMLIA_EXAMPLES_COMMON +#ifndef _DHT_KADEMLIA_COMMON +#define _DHT_KADEMLIA_COMMON #define MAX_JOIN_TRIALS 4 @@ -22,7 +22,6 @@ #define MAILBOX_NAME_SIZE 16 /* (identifier_size / 4) (hex encoded) */ #define COMM_SIZE 1 -#define COMP_SIZE 0 #define MAX_STEPS 10 @@ -30,5 +29,4 @@ #define RANDOM_LOOKUP_NODE 0 - -#endif /* _KADEMLIA_EXAMPLES_COMMON */ +#endif /* _DHT_KADEMLIA_COMMON */ diff --git a/examples/c/dht-kademlia/dht-kademlia.c b/examples/c/dht-kademlia/dht-kademlia.c new file mode 100644 index 0000000000..ceee01a589 --- /dev/null +++ b/examples/c/dht-kademlia/dht-kademlia.c @@ -0,0 +1,103 @@ +/* Copyright (c) 2012-2020. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "message.h" +#include "node.h" + +#include "simgrid/actor.h" +#include "simgrid/comm.h" +#include "simgrid/engine.h" +#include "simgrid/mailbox.h" + +#include "xbt/asserts.h" +#include "xbt/log.h" + +XBT_LOG_NEW_DEFAULT_CATEGORY(dht_kademlia, "Messages specific for this example"); + +/** @brief Node function + * @param my node ID + * @param the ID of the person I know in the system (or not) + * @param Time before I leave the system because I'm bored + */ +static void node(int argc, char* argv[]) +{ + unsigned int join_success = 1; + double deadline; + xbt_assert(argc == 3 || argc == 4, "Wrong number of arguments"); + /* Node initialization */ + unsigned int id = strtoul(argv[1], NULL, 0); + node_t node = node_init(id); + + if (argc == 4) { + XBT_INFO("Hi, I'm going to join the network with id %s", sg_mailbox_get_name(node->mailbox)); + unsigned int id_known = strtoul(argv[2], NULL, 0); + join_success = join(node, id_known); + deadline = strtod(argv[3], NULL); + } else { + deadline = strtod(argv[2], NULL); + XBT_INFO("Hi, I'm going to create the network with id %s", sg_mailbox_get_name(node->mailbox)); + routing_table_update(node, node->id); + } + if (join_success) { + XBT_VERB("Ok, I'm joining the network with id %s", sg_mailbox_get_name(node->mailbox)); + // We start the main loop + double next_lookup_time = simgrid_get_clock() + RANDOM_LOOKUP_INTERVAL; + + XBT_VERB("Main loop start"); + + sg_mailbox_t mailbox = get_node_mailbox(node->id); + + while (simgrid_get_clock() < deadline) { + if (node->receive_comm == NULL) + node->receive_comm = sg_mailbox_get_async(mailbox, &node->received_msg); + + if (sg_comm_test(node->receive_comm)) { + // There has been a transfer, we need to handle it ! + const kademlia_message_t msg = (kademlia_message_t)(node->received_msg); + if (msg) { + handle_find_node(node, msg); + free(msg->answer); + free(msg); + node->receive_comm = NULL; + } else + sg_actor_sleep_for(1); + } else { + /* We search for a pseudo random node */ + if (simgrid_get_clock() >= next_lookup_time) { + random_lookup(node); + next_lookup_time += RANDOM_LOOKUP_INTERVAL; + } else { + // Didn't get a task: sleep for a while... + sg_actor_sleep_for(1); + } + } + } + } else { + XBT_INFO("I couldn't join the network :("); + } + XBT_DEBUG("I'm leaving the network"); + XBT_INFO("%u/%u FIND_NODE have succeeded", node->find_node_success, node->find_node_success + node->find_node_failed); + node_free(node); +} + +/** @brief Main function */ +int main(int argc, char* argv[]) +{ + simgrid_init(&argc, argv); + + /* Check the arguments */ + xbt_assert(argc > 2, "Usage: %s platform_file deployment_file\n\tExample: %s msg_platform.xml msg_deployment.xml\n", + argv[0], argv[0]); + + simgrid_load_platform(argv[1]); + simgrid_register_function("node", node); + simgrid_load_deployment(argv[2]); + + simgrid_run(); + + XBT_INFO("Simulated time: %g", simgrid_get_clock()); + + return 0; +} diff --git a/examples/deprecated/msg/dht-kademlia/dht-kademlia.tesh b/examples/c/dht-kademlia/dht-kademlia.tesh similarity index 92% rename from examples/deprecated/msg/dht-kademlia/dht-kademlia.tesh rename to examples/c/dht-kademlia/dht-kademlia.tesh index 7825b34c4e..ead6bf5c83 100644 --- a/examples/deprecated/msg/dht-kademlia/dht-kademlia.tesh +++ b/examples/c/dht-kademlia/dht-kademlia.tesh @@ -1,9 +1,9 @@ #!/usr/bin/env tesh -p Testing the Kademlia implementation with MSG +p Testing the Kademlia implementation ! output sort 19 -$ ${bindir:=.}/dht-kademlia ${platfdir}/cluster_backbone.xml ${srcdir}/dht-kademlia_d.xml "--log=root.fmt:[%10.6r]%e(%02i:%P@%h)%e%m%n" +$ ${bindir:=.}/dht-kademlia-c ${platfdir}/cluster_backbone.xml ${srcdir}/dht-kademlia_d.xml "--log=root.fmt:[%10.6r]%e(%02i:%P@%h)%e%m%n" > [ 0.000000] ( 1:node@node-0.simgrid.org) Hi, I'm going to create the network with id 0 > [ 0.000000] ( 2:node@node-1.simgrid.org) Hi, I'm going to join the network with id 1 > [ 0.000000] ( 3:node@node-2.simgrid.org) Hi, I'm going to join the network with id 3 diff --git a/examples/deprecated/msg/dht-kademlia/dht-kademlia_d.xml b/examples/c/dht-kademlia/dht-kademlia_d.xml similarity index 100% rename from examples/deprecated/msg/dht-kademlia/dht-kademlia_d.xml rename to examples/c/dht-kademlia/dht-kademlia_d.xml diff --git a/examples/deprecated/msg/dht-kademlia/generate.py b/examples/c/dht-kademlia/generate.py similarity index 100% rename from examples/deprecated/msg/dht-kademlia/generate.py rename to examples/c/dht-kademlia/generate.py diff --git a/examples/c/dht-kademlia/message.c b/examples/c/dht-kademlia/message.c new file mode 100644 index 0000000000..b3fb01ceb0 --- /dev/null +++ b/examples/c/dht-kademlia/message.c @@ -0,0 +1,29 @@ +/* Copyright (c) 2012-2020. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "message.h" +#include "answer.h" + +kademlia_message_t new_message(unsigned int sender_id, unsigned int destination_id, answer_t answer, + sg_mailbox_t mailbox, const char* hostname) +{ + kademlia_message_t msg = xbt_new(s_kademlia_message_t, 1); + + msg->sender_id = sender_id; + msg->destination_id = destination_id; + msg->answer = answer; + msg->answer_to = mailbox; + msg->issuer_host_name = hostname; + + return msg; +} + +void free_message(void* message) +{ + const kademlia_message_t msg = (kademlia_message_t)message; + free(msg->answer); + free(msg); +} diff --git a/examples/c/dht-kademlia/message.h b/examples/c/dht-kademlia/message.h new file mode 100644 index 0000000000..cf20f26557 --- /dev/null +++ b/examples/c/dht-kademlia/message.h @@ -0,0 +1,30 @@ +/* Copyright (c) 2012-2020. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef _DHT_KADEMLIA_MESSAGE +#define _DHT_KADEMLIA_MESSAGE +#include "answer.h" +#include "common.h" +#include "simgrid/mailbox.h" +#include "xbt/sysdep.h" + +typedef struct s_kademlia_message { + unsigned int sender_id; // Id of the guy who sent the task + unsigned int destination_id; // Id we are trying to find, if needed. + answer_t answer; // Answer to the request made, if needed. + sg_mailbox_t answer_to; // mailbox to send the answer to (if not an answer). + const char* issuer_host_name; // used for logging +} s_kademlia_message_t; + +typedef s_kademlia_message_t* kademlia_message_t; + +// Task handling functions +kademlia_message_t task_new_find_node(unsigned int sender_id, unsigned int destination_id, sg_mailbox_t mailbox, + const char* hostname); +kademlia_message_t new_message(unsigned int sender_id, unsigned int destination_id, answer_t answer, + sg_mailbox_t mailbox, const char* hostname); +void free_message(void* message); +#endif /* _DHT_KADEMLIA_MESSAGE */ diff --git a/examples/c/dht-kademlia/node.c b/examples/c/dht-kademlia/node.c new file mode 100644 index 0000000000..71b0512c4b --- /dev/null +++ b/examples/c/dht-kademlia/node.c @@ -0,0 +1,377 @@ +/* Copyright (c) 2010-2020. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "node.h" +#include "routing_table.h" +#include "simgrid/comm.h" + +#include /* snprintf */ + +XBT_LOG_NEW_DEFAULT_CATEGORY(dht_kademlia_node, "Messages specific for this example"); + +/** @brief Initialization of a node + * @param node_id the id of the node + * @return the node created + */ +node_t node_init(unsigned int node_id) +{ + node_t node = xbt_new(s_node_t, 1); + node->id = node_id; + node->table = routing_table_init(node_id); + node->mailbox = get_node_mailbox(node_id); + node->find_node_failed = 0; + node->find_node_success = 0; + + node->received_msg = NULL; + node->receive_comm = NULL; + + return node; +} + +/* @brief Node destructor */ +void node_free(node_t node) +{ + routing_table_free(node->table); + xbt_free(node); +} + +/** + * @brief Tries to join the network + * @param node node data + * @param id_known id of the node I know in the network. + */ +unsigned int join(node_t node, unsigned int id_known) +{ + unsigned int i; + unsigned int got_answer = 0; + + sg_mailbox_t mailbox = get_node_mailbox(node->id); + + /* Add the guy we know to our routing table and ourselves. */ + routing_table_update(node, node->id); + routing_table_update(node, id_known); + + /* First step: Send a "FIND_NODE" request to the node we know */ + send_find_node(node, id_known, node->id); + do { + if (node->receive_comm == NULL) + node->receive_comm = sg_mailbox_get_async(mailbox, &node->received_msg); + + if (sg_comm_test(node->receive_comm)) { + XBT_DEBUG("Received an answer from the node I know."); + got_answer = 1; + // retrieve the node list and ping them. + const kademlia_message_t msg = (kademlia_message_t)(node->received_msg); + const s_answer_t* node_list = msg->answer; + if (node_list != NULL) { + node_contact_t contact; + xbt_dynar_foreach (node_list->nodes, i, contact) + routing_table_update(node, contact->id); + node->received_msg = NULL; + } else { + handle_find_node(node, msg); + } + free(msg->answer); + free(msg); + node->receive_comm = NULL; + } else { + sg_actor_sleep_for(1); + } + } while (got_answer == 0); + + /* Second step: Send a FIND_NODE to a a random node in buckets */ + unsigned int bucket_id = routing_table_find_bucket(node->table, id_known)->id; + xbt_assert(bucket_id <= IDENTIFIER_SIZE); + for (i = 0; ((bucket_id > i) || (bucket_id + i) <= IDENTIFIER_SIZE) && i < JOIN_BUCKETS_QUERIES; i++) { + if (bucket_id > i) { + unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id - i); + find_node(node, id_in_bucket, 0); + } + if (bucket_id + i <= IDENTIFIER_SIZE) { + unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id + i); + find_node(node, id_in_bucket, 0); + } + } + return got_answer; +} + +/** @brief Send a "FIND_NODE" to a node + * @param node sender node data + * @param id node we are querying + * @param destination node we are trying to find. + */ +void send_find_node(node_t node, unsigned int id, unsigned int destination) +{ + /* Gets the mailbox to send to */ + sg_mailbox_t mailbox = get_node_mailbox(id); + /* Build the message */ + kademlia_message_t msg = new_message(node->id, destination, NULL, node->mailbox, sg_host_self_get_name()); + sg_comm_t comm = sg_mailbox_put_init(mailbox, msg, COMM_SIZE); + sg_comm_detach(comm, free_message); + XBT_VERB("Asking %u for its closest nodes", id); +} + +/** + * Sends to the best "KADEMLIA_ALPHA" nodes in the "node_list" array a "FIND_NODE" request, to ask them for their best + * nodes + */ +unsigned int send_find_node_to_best(node_t node, const_answer_t node_list) +{ + unsigned int i = 0; + unsigned int j = 0; + unsigned int destination = node_list->destination_id; + while (j < KADEMLIA_ALPHA && i < node_list->size) { + /* We need to have at most "KADEMLIA_ALPHA" requests each time, according to the protocol */ + /* Gets the node we want to send the query to */ + const s_node_contact_t* node_to_query = xbt_dynar_get_as(node_list->nodes, i, node_contact_t); + if (node_to_query->id != node->id) { /* No need to query ourselves */ + send_find_node(node, node_to_query->id, destination); + j++; + } + i++; + } + return i; +} + +/** @brief Updates/Puts the node id unsigned into our routing table + * @param node Our node data + * @param id The id of the node we need to add unsigned into our routing table + */ +void routing_table_update(const_node_t node, unsigned int id) +{ + const_routing_table_t table = node->table; + // retrieval of the bucket in which the should be + const_bucket_t bucket = routing_table_find_bucket(table, id); + + // check if the id is already in the bucket. + unsigned int id_pos = bucket_find_id(bucket, id); + + if (id_pos == -1) { + /* We check if the bucket is full or not. If it is, we evict an old element */ + if (xbt_dynar_length(bucket->nodes) >= BUCKET_SIZE) + xbt_dynar_pop(bucket->nodes, NULL); + + xbt_dynar_unshift(bucket->nodes, &id); + XBT_VERB("I'm adding to my routing table %08x", id); + } else { + // We push to the front of the dynar the element. + unsigned int element = xbt_dynar_get_as(bucket->nodes, id_pos, unsigned int); + xbt_dynar_remove_at(bucket->nodes, id_pos, NULL); + xbt_dynar_unshift(bucket->nodes, &element); + XBT_VERB("I'm updating %08x", element); + } +} + +/** @brief Finds the closest nodes to the node given. + * @param node : our node + * @param destination_id : the id of the guy we are trying to find + */ +answer_t find_closest(const_node_t node, unsigned int destination_id) +{ + int i; + answer_t answer = answer_init(destination_id); + /* We find the corresponding bucket for the id */ + const_bucket_t bucket = routing_table_find_bucket(node->table, destination_id); + int bucket_id = bucket->id; + xbt_assert((bucket_id <= IDENTIFIER_SIZE), "Bucket found has a wrong identifier"); + /* So, we copy the contents of the bucket unsigned into our result dynar */ + answer_add_bucket(bucket, answer); + + /* However, if we don't have enough elements in our bucket, we NEED to include at least "BUCKET_SIZE" elements + * (if, of course, we know at least "BUCKET_SIZE" elements. So we're going to look unsigned into the other buckets. + */ + for (i = 1; answer->size < BUCKET_SIZE && ((bucket_id - i > 0) || (bucket_id + i < IDENTIFIER_SIZE)); i++) { + /* We check the previous buckets */ + if (bucket_id - i >= 0) { + const_bucket_t bucket_p = &node->table->buckets[bucket_id - i]; + answer_add_bucket(bucket_p, answer); + } + /* We check the next buckets */ + if (bucket_id + i <= IDENTIFIER_SIZE) { + const_bucket_t bucket_n = &node->table->buckets[bucket_id + i]; + answer_add_bucket(bucket_n, answer); + } + } + /* We sort the array by XOR distance */ + answer_sort(answer); + /* We trim the array to have only BUCKET_SIZE or less elements */ + answer_trim(answer); + + return answer; +} + +unsigned int find_node(node_t node, unsigned int id_to_find, unsigned int count_in_stats) +{ + unsigned int i = 0; + unsigned int queries; + unsigned int answers; + unsigned int destination_found = 0; + unsigned int nodes_added = 0; + double global_timeout = simgrid_get_clock() + FIND_NODE_GLOBAL_TIMEOUT; + unsigned int steps = 0; + + /* First we build a list of who we already know */ + answer_t node_list = find_closest(node, id_to_find); + xbt_assert((node_list != NULL), "node_list incorrect"); + + XBT_DEBUG("Doing a FIND_NODE on %08x", id_to_find); + + /* Ask the nodes on our list if they have information about the node we are trying to find */ + sg_mailbox_t mailbox = get_node_mailbox(node->id); + do { + answers = 0; + queries = send_find_node_to_best(node, node_list); + nodes_added = 0; + double timeout = simgrid_get_clock() + FIND_NODE_TIMEOUT; + steps++; + double time_beginreceive = simgrid_get_clock(); + + do { + if (node->receive_comm == NULL) + node->receive_comm = sg_mailbox_get_async(mailbox, &node->received_msg); + + if (sg_comm_test(node->receive_comm)) { + // Figure out if we received an answer or something else + const kademlia_message_t msg = (kademlia_message_t)(node->received_msg); + + // Check if what we have received is what we are looking for. + if (msg->answer != NULL && msg->answer->destination_id == id_to_find) { + // Handle the answer + routing_table_update(node, msg->sender_id); + node_contact_t contact; + xbt_dynar_foreach (node_list->nodes, i, contact) + routing_table_update(node, contact->id); + + answers++; + + nodes_added = answer_merge(node_list, msg->answer); + XBT_DEBUG("Received an answer from %s (%s) with %lu nodes on it", sg_mailbox_get_name(msg->answer_to), + msg->issuer_host_name, xbt_dynar_length(msg->answer->nodes)); + } else { + if (msg->answer != NULL) { + routing_table_update(node, msg->sender_id); + XBT_DEBUG("Received a wrong answer for a FIND_NODE"); + } else { + handle_find_node(node, msg); + } + // Update the timeout if we didn't have our answer + timeout += simgrid_get_clock() - time_beginreceive; + time_beginreceive = simgrid_get_clock(); + } + free(msg->answer); + free(msg); + node->receive_comm = NULL; + } else { + sg_actor_sleep_for(1); + } + } while (simgrid_get_clock() < timeout && answers < queries); + destination_found = answer_destination_found(node_list); + } while (!destination_found && (nodes_added > 0 || answers == 0) && simgrid_get_clock() < global_timeout && + steps < MAX_STEPS); + if (destination_found) { + if (count_in_stats) + node->find_node_success++; + if (queries > 4) + XBT_VERB("FIND_NODE on %08x success in %u steps", id_to_find, steps); + routing_table_update(node, id_to_find); + } else { + if (count_in_stats) { + node->find_node_failed++; + XBT_VERB("%08x not found in %u steps", id_to_find, steps); + } + } + answer_free(node_list); + return destination_found; +} + +/** @brief Does a pseudo-random lookup for someone in the system + * @param node caller node data + */ +void random_lookup(node_t node) +{ + unsigned int id_to_look = RANDOM_LOOKUP_NODE; // Totally random. + /* TODO: Use some pseudorandom generator. */ + XBT_DEBUG("I'm doing a random lookup"); + find_node(node, id_to_look, 1); +} + +/** @brief Handles the answer to an incoming "find_node" message */ +void handle_find_node(node_t node, kademlia_message_t msg) +{ + routing_table_update(node, msg->sender_id); + XBT_VERB("Received a FIND_NODE from %s (%s), he's trying to find %08x", sg_mailbox_get_name(msg->answer_to), + msg->issuer_host_name, msg->destination_id); + // Building the msg to send + kademlia_message_t answer = new_message(node->id, msg->destination_id, find_closest(node, msg->destination_id), + node->mailbox, sg_host_self_get_name()); + // Sending the msg + sg_comm_t comm = sg_mailbox_put_init(msg->answer_to, answer, COMM_SIZE); + sg_comm_detach(comm, &free_message); +} + +/**@brief Returns an identifier which is in a specific bucket of a routing table + * @param id id of the routing table owner + * @param prefix id of the bucket where we want that identifier to be + */ +unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix) +{ + if (prefix == 0) { + return 0; + } else { + return (1U << ((unsigned int)(prefix - 1))) ^ id; + } +} + +/** @brief Returns the prefix of an identifier. + * The prefix is the id of the bucket in which the remote identifier xor our identifier should be stored. + * @param id : big unsigned int id to test + * @param nb_bits : key size + */ +unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits) +{ + unsigned int size = sizeof(unsigned int) * 8; + for (unsigned int j = 0; j < size; j++) { + if (((id >> (size - 1 - j)) & 0x1) != 0) { + return nb_bits - (j); + } + } + return 0; +} + +/** @brief Gets the mailbox name of a host given its identifier */ +sg_mailbox_t get_node_mailbox(unsigned int id) +{ + char mailbox_name[MAILBOX_NAME_SIZE]; + snprintf(mailbox_name, MAILBOX_NAME_SIZE - 1, "%u", id); + return sg_mailbox_by_name(mailbox_name); +} + +/** Constructor, build a new contact information. */ +node_contact_t node_contact_new(unsigned int id, unsigned int distance) +{ + node_contact_t contact = xbt_new(s_node_contact_t, 1); + + contact->id = id; + contact->distance = distance; + + return contact; +} + +/** Builds a contact information from a contact information */ +node_contact_t node_contact_copy(const_node_contact_t node_contact) +{ + node_contact_t contact = xbt_new(s_node_contact_t, 1); + + contact->id = node_contact->id; + contact->distance = node_contact->distance; + + return contact; +} + +/** Destructor */ +void node_contact_free(node_contact_t contact) +{ + xbt_free(contact); +} diff --git a/examples/c/dht-kademlia/node.h b/examples/c/dht-kademlia/node.h new file mode 100644 index 0000000000..e269cbe2cd --- /dev/null +++ b/examples/c/dht-kademlia/node.h @@ -0,0 +1,72 @@ +/* Copyright (c) 2012-2020. The SimGrid Team. + * All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef _DHT_KADEMLIA_ROUTING_H +#define _DHT_KADEMLIA_ROUTING_H +#include "simgrid/actor.h" +#include "simgrid/comm.h" +#include "simgrid/engine.h" +#include "simgrid/host.h" +#include "simgrid/mailbox.h" +#include "xbt/dynar.h" +#include "xbt/log.h" +#include "xbt/sysdep.h" + +#include "answer.h" +#include "common.h" +#include "message.h" +#include "routing_table.h" + +/* Information about a foreign node */ +typedef struct s_node_contact { + unsigned int id; // The node identifier + unsigned int distance; // The distance from the node +} s_node_contact_t; + +typedef s_node_contact_t* node_contact_t; +typedef const s_node_contact_t* const_node_contact_t; + +/* Node data */ +typedef struct s_node { + unsigned int id; // node id - 160 bits + routing_table_t table; // node routing table + sg_comm_t receive_comm; // current receiving communication. + void* received_msg; // current task being received + + sg_mailbox_t mailbox; // node mailbox + unsigned int find_node_success; // Number of find_node which have succeeded. + unsigned int find_node_failed; // Number of find_node which have failed. +} s_node_t; + +typedef s_node_t* node_t; +typedef const s_node_t* const_node_t; + +// node functions +node_t node_init(unsigned int id); +void node_free(node_t node); +void routing_table_update(const_node_t node, unsigned int id); +answer_t find_closest(const_node_t node, unsigned int destination_id); + +// identifier functions +unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix); +unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits); +sg_mailbox_t get_node_mailbox(unsigned int id); + +// node contact functions +node_contact_t node_contact_new(unsigned int id, unsigned int distance); +node_contact_t node_contact_copy(const_node_contact_t node_contact); +void node_contact_free(node_contact_t contact); + +unsigned int join(node_t node, unsigned int id_known); +unsigned int find_node(node_t node, unsigned int id_to_find, unsigned int count_in_stats); +void random_lookup(node_t node); + +void send_find_node(node_t node, unsigned int id, unsigned int destination); +unsigned int send_find_node_to_best(node_t node, const_answer_t node_list); + +void handle_find_node(node_t node, kademlia_message_t data); + +#endif diff --git a/examples/deprecated/msg/dht-kademlia/routing_table.c b/examples/c/dht-kademlia/routing_table.c similarity index 79% rename from examples/deprecated/msg/dht-kademlia/routing_table.c rename to examples/c/dht-kademlia/routing_table.c index 418040bbea..b8204f837d 100644 --- a/examples/deprecated/msg/dht-kademlia/routing_table.c +++ b/examples/c/dht-kademlia/routing_table.c @@ -6,9 +6,8 @@ #include "routing_table.h" #include "node.h" -#include "simgrid/msg.h" -XBT_LOG_NEW_DEFAULT_CATEGORY(msg_kademlia_routing_table, "Messages specific for this msg example"); +XBT_LOG_NEW_DEFAULT_CATEGORY(dht_kademlia_routing_table, "Messages specific for this example"); /** @brief Initialization of a node routing table. */ routing_table_t routing_table_init(unsigned int node_id) @@ -17,7 +16,7 @@ routing_table_t routing_table_init(unsigned int node_id) table->buckets = xbt_new(s_bucket_t, IDENTIFIER_SIZE + 1); for (unsigned int i = 0; i < IDENTIFIER_SIZE + 1; i++) { table->buckets[i].nodes = xbt_dynar_new(sizeof(unsigned int), NULL); - table->buckets[i].id = i; + table->buckets[i].id = i; } table->id = node_id; return table; @@ -27,7 +26,7 @@ routing_table_t routing_table_init(unsigned int node_id) void routing_table_free(routing_table_t table) { unsigned int i; - //Free the buckets. + // Free the buckets. for (i = 0; i <= IDENTIFIER_SIZE; i++) { xbt_dynar_free(&table->buckets[i].nodes); } @@ -45,7 +44,7 @@ void routing_table_print(const_routing_table_t table) for (unsigned int i = 0; i <= IDENTIFIER_SIZE; i++) { if (!xbt_dynar_is_empty(table->buckets[i].nodes)) { XBT_INFO("Bucket number %u: ", i); - xbt_dynar_foreach(table->buckets[i].nodes, j, value) { + xbt_dynar_foreach (table->buckets[i].nodes, j, value) { XBT_INFO("Element %u: %08x", j, value); } } @@ -53,15 +52,15 @@ void routing_table_print(const_routing_table_t table) } /** @brief Finds an identifier in a bucket and returns its position or returns -1 if it doesn't exists - * @param bucket the bucket in which we try to find our identifier - * @param id the id - */ + * @param bucket the bucket in which we try to find our identifier + * @param id the id + */ unsigned int bucket_find_id(const_bucket_t bucket, unsigned int id) { unsigned int i; unsigned int current_id; - xbt_dynar_foreach(bucket->nodes, i, current_id){ - if (id == current_id){ + xbt_dynar_foreach (bucket->nodes, i, current_id) { + if (id == current_id) { return i; } } @@ -69,10 +68,10 @@ unsigned int bucket_find_id(const_bucket_t bucket, unsigned int id) } /** @brief Finds the corresponding bucket in a routing table for a given identifier - * @param table the routing table - * @param id the identifier - * @return the bucket in which the the identifier would be. - */ + * @param table the routing table + * @param id the identifier + * @return the bucket in which the the identifier would be. + */ bucket_t routing_table_find_bucket(const_routing_table_t table, unsigned int id) { unsigned int xor_number = table->id ^ id; diff --git a/examples/deprecated/msg/dht-kademlia/routing_table.h b/examples/c/dht-kademlia/routing_table.h similarity index 66% rename from examples/deprecated/msg/dht-kademlia/routing_table.h rename to examples/c/dht-kademlia/routing_table.h index 95048b8632..0240bef086 100644 --- a/examples/deprecated/msg/dht-kademlia/routing_table.h +++ b/examples/c/dht-kademlia/routing_table.h @@ -4,27 +4,27 @@ /* This program is free software; you can redistribute it and/or modify it * under the terms of the license (GNU LGPL) which comes with this package. */ -#ifndef _MSG_KADEMLIA_EXAMPLES_ROUTING_TABLE -#define _MSG_KADEMLIA_EXAMPLES_ROUTING_TABLE +#ifndef _DHT_KADEMLIA_ROUTING_TABLE +#define _DHT_KADEMLIA_ROUTING_TABLE #include "common.h" #include /* Routing table bucket */ typedef struct s_bucket { - xbt_dynar_t nodes; //Nodes in the bucket. - unsigned int id; //bucket id + xbt_dynar_t nodes; // Nodes in the bucket. + unsigned int id; // bucket id } s_bucket_t; -typedef s_bucket_t *bucket_t; +typedef s_bucket_t* bucket_t; typedef const s_bucket_t* const_bucket_t; /* Node routing table */ typedef struct s_routing_table { - unsigned int id; //node id of the client's routing table - s_bucket_t *buckets; //Node bucket list - 160 sized. + unsigned int id; // node id of the client's routing table + s_bucket_t* buckets; // Node bucket list - 160 sized. } s_routing_table_t; -typedef s_routing_table_t *routing_table_t; +typedef s_routing_table_t* routing_table_t; typedef const s_routing_table_t* const_routing_table_t; // bucket functions @@ -36,4 +36,4 @@ void routing_table_free(routing_table_t table); void routing_table_print(const_routing_table_t table); bucket_t routing_table_find_bucket(const_routing_table_t table, unsigned int id); -#endif /* _MSG_KADEMLIA_EXAMPLES_ROUTING_TABLE */ +#endif /* _DHT_KADEMLIA_ROUTING_TABLE */ diff --git a/examples/deprecated/msg/CMakeLists.txt b/examples/deprecated/msg/CMakeLists.txt index bd59723696..11bcdfb976 100644 --- a/examples/deprecated/msg/CMakeLists.txt +++ b/examples/deprecated/msg/CMakeLists.txt @@ -13,30 +13,18 @@ foreach(x dht-pastry set(tesh_files ${tesh_files} ${CMAKE_CURRENT_SOURCE_DIR}/${x}/${x}.tesh) endforeach() -if(enable_msg) - add_executable (dht-kademlia EXCLUDE_FROM_ALL dht-kademlia/dht-kademlia.c dht-kademlia/node.c dht-kademlia/routing_table.c dht-kademlia/task.c dht-kademlia/answer.c) - target_link_libraries(dht-kademlia simgrid) - set_target_properties(dht-kademlia PROPERTIES RUNTIME_OUTPUT_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/dht-kademlia) - add_dependencies(tests dht-kademlia) -endif() -foreach (file answer dht-kademlia node routing_table task) - set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/${file}.c ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/${file}.h) -endforeach() - -foreach (file dht-kademlia dht-pastry) +foreach (file dht-pastry) set(xml_files ${xml_files} ${CMAKE_CURRENT_SOURCE_DIR}/${file}/${file}_d.xml) endforeach() -set(txt_files ${txt_files} ${CMAKE_CURRENT_SOURCE_DIR}/README.doc PARENT_SCOPE) -set(bin_files ${bin_files} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/generate.py - ${CMAKE_CURRENT_SOURCE_DIR}/dht-pastry/generate.py PARENT_SCOPE) -set(examples_src ${examples_src} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/common.h PARENT_SCOPE) -set(tesh_files ${tesh_files} ${CMAKE_CURRENT_SOURCE_DIR}/dht-kademlia/dht-kademlia.tesh - PARENT_SCOPE) -set(xml_files ${xml_files} PARENT_SCOPE) +set(examples_src ${examples_src} PARENT_SCOPE) +set(txt_files ${txt_files} ${CMAKE_CURRENT_SOURCE_DIR}/README.doc PARENT_SCOPE) +set(bin_files ${bin_files} ${CMAKE_CURRENT_SOURCE_DIR}/dht-pastry/generate.py PARENT_SCOPE) +set(tesh_files ${tesh_files} PARENT_SCOPE) +set(xml_files ${xml_files} PARENT_SCOPE) if(enable_msg) - foreach(x dht-pastry dht-kademlia synchro-semaphore) + foreach(x dht-pastry synchro-semaphore) ADD_TESH_FACTORIES(msg-${x} "thread;ucontext;raw;boost" --setenv bindir=${CMAKE_BINARY_DIR}/examples/deprecated/msg/${x} --setenv srcdir=${CMAKE_HOME_DIRECTORY}/examples/deprecated/msg/${x} @@ -51,17 +39,4 @@ if(enable_msg) --cd ${CMAKE_BINARY_DIR}/examples/deprecated/msg/${x} ${CMAKE_HOME_DIRECTORY}/examples/deprecated/msg/${x}/${x}.tesh) endforeach() - - if(CMAKE_SYSTEM_NAME STREQUAL "SunOS" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "i386" AND CMAKE_SIZEOF_VOID_P EQUAL 8) - # Thread-local storage (TLS) is needed for parallel execution, but it doesn't - # play well with Ucontexts on 64bit SunOS (at least on x86_64). - set(parallel-factories "thread;raw;boost") - else() - set(parallel-factories "thread;ucontext;raw;boost") - endif() - ADD_TESH_FACTORIES(msg-dht-kademlia-parallel "${parallel-factories}" --cfg contexts/nthreads:4 ${CONTEXTS_SYNCHRO} - --setenv bindir=${CMAKE_BINARY_DIR}/examples/deprecated/msg/dht-kademlia - --setenv srcdir=${CMAKE_HOME_DIRECTORY}/examples/deprecated/msg/dht-kademlia - --setenv platfdir=${CMAKE_HOME_DIRECTORY}/examples/platforms - ${CMAKE_HOME_DIRECTORY}/examples/deprecated/msg/dht-kademlia/dht-kademlia.tesh) endif(enable_msg) \ No newline at end of file diff --git a/examples/deprecated/msg/dht-kademlia/dht-kademlia.c b/examples/deprecated/msg/dht-kademlia/dht-kademlia.c deleted file mode 100644 index 9129794454..0000000000 --- a/examples/deprecated/msg/dht-kademlia/dht-kademlia.c +++ /dev/null @@ -1,377 +0,0 @@ -/* Copyright (c) 2012-2020. The SimGrid Team. All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#include "dht-kademlia.h" -#include "node.h" -#include "task.h" - -#include "simgrid/msg.h" - -#include /* snprintf */ - -/** @addtogroup MSG_examples - * kademlia/kademlia.c: Kademlia protocol - * Implements the Kademlia protocol, using 32 bits identifiers. - */ -XBT_LOG_NEW_DEFAULT_CATEGORY(msg_kademlia, "Messages specific for this msg example"); - -/* Main loop for the process */ -static void main_loop(node_t node, double deadline) -{ - double next_lookup_time = MSG_get_clock() + RANDOM_LOOKUP_INTERVAL; - XBT_VERB("Main loop start"); - while (MSG_get_clock() < deadline) { - - if (node->receive_comm == NULL) { - node->task_received = NULL; - node->receive_comm = MSG_task_irecv(&node->task_received, node->mailbox); - } - if (node->receive_comm) { - if (!MSG_comm_test(node->receive_comm)) { - /* We search for a pseudo random node */ - if (MSG_get_clock() >= next_lookup_time) { - random_lookup(node); - next_lookup_time += RANDOM_LOOKUP_INTERVAL; - } else { - //Didn't get a task: sleep for a while... - MSG_process_sleep(1); - } - } else { - //There has been a transfer, we need to handle it ! - msg_error_t status = MSG_comm_get_status(node->receive_comm); - MSG_comm_destroy(node->receive_comm); - node->receive_comm = NULL; - - if (status == MSG_OK) { - xbt_assert((node->task_received != NULL), "We received an incorrect task"); - handle_task(node, node->task_received); - } else { - xbt_assert((MSG_comm_get_task(node->receive_comm) == NULL), "Comm failed but received a task."); - XBT_DEBUG("Nevermind, the communication has failed."); - } - } - } else { - //Didn't get a comm: sleep. - MSG_process_sleep(1); - } - } - //Cleanup the receiving communication. - if (node->receive_comm != NULL) { - if (MSG_comm_test(node->receive_comm) && MSG_comm_get_status(node->receive_comm) == MSG_OK) { - task_free(MSG_comm_get_task(node->receive_comm)); - } - MSG_comm_destroy(node->receive_comm); - } -} - -/** @brief Node function - * @param my node ID - * @param the ID of the person I know in the system (or not) - * @param Time before I leave the system because I'm bored - */ -static int node(int argc, char *argv[]) -{ - unsigned int join_sucess = 1; - double deadline; - xbt_assert(argc == 3 || argc == 4, "Wrong number of arguments"); - /* Node initialization */ - unsigned int id = strtoul(argv[1], NULL, 0); - node_t node = node_init(id); - - if (argc == 4) { - XBT_INFO("Hi, I'm going to join the network with id %s", node->mailbox); - unsigned int id_known = strtoul(argv[2], NULL, 0); - join_sucess = join(node, id_known); - deadline = strtod(argv[3], NULL); - } else { - deadline = strtod(argv[2], NULL); - XBT_INFO("Hi, I'm going to create the network with id %s", node->mailbox); - node_routing_table_update(node, node->id); - } - if (join_sucess) { - XBT_VERB("Ok, I'm joining the network with id %s", node->mailbox); - //We start the main loop - main_loop(node, deadline); - } else { - XBT_INFO("I couldn't join the network :("); - } - XBT_DEBUG("I'm leaving the network"); - XBT_INFO("%u/%u FIND_NODE have succeeded", node->find_node_success, node->find_node_success + node->find_node_failed); - node_free(node); - - return 0; -} - -/** - * @brief Tries to join the network - * @param node node data - * @param id_known id of the node I know in the network. - */ -unsigned int join(node_t node, unsigned int id_known) -{ - const s_answer_t* node_list; - msg_error_t status; - unsigned int trial = 0; - unsigned int i; - unsigned int answer_got = 0; - - /* Add the guy we know to our routing table and ourselves. */ - node_routing_table_update(node, node->id); - node_routing_table_update(node, id_known); - - /* First step: Send a "FIND_NODE" request to the node we know */ - send_find_node(node, id_known, node->id); - do { - if (node->receive_comm == NULL) { - node->task_received = NULL; - node->receive_comm = MSG_task_irecv(&node->task_received, node->mailbox); - } - if (node->receive_comm) { - if (MSG_comm_test(node->receive_comm)) { - status = MSG_comm_get_status(node->receive_comm); - MSG_comm_destroy(node->receive_comm); - node->receive_comm = NULL; - if (status == MSG_OK) { - XBT_DEBUG("Received an answer from the node I know."); - answer_got = 1; - //retrieve the node list and ping them. - const s_task_data_t* data = MSG_task_get_data(node->task_received); - xbt_assert((data != NULL), "Null data received"); - if (data->type == TASK_FIND_NODE_ANSWER) { - node_contact_t contact; - node_list = data->answer; - xbt_dynar_foreach(node_list->nodes, i, contact) { - node_routing_table_update(node, contact->id); - } - task_free(node->task_received); - } else { - handle_task(node, node->task_received); - } - } else { - trial++; - } - } else { - MSG_process_sleep(1); - } - } else { - MSG_process_sleep(1); - } - } while (answer_got == 0 && trial < MAX_JOIN_TRIALS); - /* Second step: Send a FIND_NODE to a a random node in buckets */ - unsigned int bucket_id = routing_table_find_bucket(node->table, id_known)->id; - for (i = 0; ((bucket_id > i) || (bucket_id + i) <= IDENTIFIER_SIZE) && i < JOIN_BUCKETS_QUERIES; i++) { - if (bucket_id > i) { - unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id - i); - find_node(node, id_in_bucket, 0); - } - if (bucket_id + i <= IDENTIFIER_SIZE) { - unsigned int id_in_bucket = get_id_in_prefix(node->id, bucket_id + i); - find_node(node, id_in_bucket, 0); - } - } - return answer_got; -} - -/** @brief Send a request to find a node in the node routing table. - * @param node our node data - * @param id_to_find the id of the node we are trying to find - */ -unsigned int find_node(node_t node, unsigned int id_to_find, unsigned int count_in_stats) -{ - unsigned int i = 0; - unsigned int queries; - unsigned int answers; - unsigned int destination_found = 0; - unsigned int nodes_added = 0; - double global_timeout = MSG_get_clock() + FIND_NODE_GLOBAL_TIMEOUT; - unsigned int steps = 0; - - /* First we build a list of who we already know */ - answer_t node_list = node_find_closest(node, id_to_find); - xbt_assert((node_list != NULL), "node_list incorrect"); - - XBT_DEBUG("Doing a FIND_NODE on %08x", id_to_find); - - msg_error_t status; - - /* Ask the nodes on our list if they have information about the node we are trying to find */ - do { - answers = 0; - queries = send_find_node_to_best(node, node_list); - nodes_added = 0; - double timeout = MSG_get_clock() + FIND_NODE_TIMEOUT; - steps++; - double time_beginreceive = MSG_get_clock(); - do { - if (node->receive_comm == NULL) { - node->task_received = NULL; - node->receive_comm = MSG_task_irecv(&node->task_received, node->mailbox); - } - if (node->receive_comm) { - if (MSG_comm_test(node->receive_comm)) { - status = MSG_comm_get_status(node->receive_comm); - MSG_comm_destroy(node->receive_comm); - node->receive_comm = NULL; - if (status == MSG_OK) { - xbt_assert((node->task_received != NULL), "Invalid task received"); - //Figure out if we received an answer or something else - const s_task_data_t* data = MSG_task_get_data(node->task_received); - xbt_assert((data != NULL), "No data in the task"); - - //Check if what we have received is what we are looking for. - if (data->type == TASK_FIND_NODE_ANSWER && data->answer->destination_id == id_to_find) { - //Handle the answer - node_routing_table_update(node, data->sender_id); - node_contact_t contact; - xbt_dynar_foreach(node_list->nodes, i, contact) { - node_routing_table_update(node, contact->id); - } - answers++; - - nodes_added = answer_merge(node_list, data->answer); - XBT_DEBUG("Received an answer from %s (%s) with %lu nodes on it", data->answer_to, data->issuer_host_name, - xbt_dynar_length(data->answer->nodes)); - - task_free(node->task_received); - } else { - handle_task(node, node->task_received); - //Update the timeout if we didn't have our answer - timeout += MSG_get_clock() - time_beginreceive; - time_beginreceive = MSG_get_clock(); - } - } - } else { - MSG_process_sleep(1); - } - } else { - MSG_process_sleep(1); - } - } while (MSG_get_clock() < timeout && answers < queries); - destination_found = answer_destination_found(node_list); - } while (!destination_found && (nodes_added > 0 || answers == 0) && MSG_get_clock() < global_timeout - && steps < MAX_STEPS); - if (destination_found) { - if (count_in_stats) - node->find_node_success++; - if (queries > 4) - XBT_VERB("FIND_NODE on %08x success in %u steps", id_to_find, steps); - node_routing_table_update(node, id_to_find); - } else { - if (count_in_stats) { - node->find_node_failed++; - XBT_VERB("%08x not found in %u steps", id_to_find, steps); - } - } - answer_free(node_list); - return destination_found; -} - -/** @brief Does a pseudo-random lookup for someone in the system - * @param node caller node data - */ -void random_lookup(node_t node) -{ - unsigned int id_to_look = RANDOM_LOOKUP_NODE; //Totally random. - /* TODO: Use some pseudorandom generator. */ - XBT_DEBUG("I'm doing a random lookup"); - find_node(node, id_to_look, 1); -} - -/** @brief Send a "FIND_NODE" to a node - * @param node sender node data - * @param id node we are querying - * @param destination node we are trying to find. - */ -void send_find_node(node_t node, unsigned int id, unsigned int destination) -{ - char mailbox[MAILBOX_NAME_SIZE]; - /* Gets the mailbox to send to */ - get_node_mailbox(id, mailbox); - /* Build the task */ - msg_task_t task = task_new_find_node(node->id, destination, node->mailbox, MSG_host_get_name(MSG_host_self())); - /* Send the task */ - xbt_assert((task != NULL), "Trying to send a NULL task."); - MSG_task_dsend(task, mailbox, task_free_v); - XBT_VERB("Asking %s for its closest nodes", mailbox); -} - -/** - * Sends to the best "KADEMLIA_ALPHA" nodes in the "node_list" array a "FIND_NODE" request, to ask them for their best - * nodes - */ -unsigned int send_find_node_to_best(node_t node, const_answer_t node_list) -{ - unsigned int i = 0; - unsigned int j = 0; - unsigned int destination = node_list->destination_id; - while (j < KADEMLIA_ALPHA && i < node_list->size) { - /* We need to have at most "KADEMLIA_ALPHA" requests each time, according to the protocol */ - /* Gets the node we want to send the query to */ - const s_node_contact_t* node_to_query = xbt_dynar_get_as(node_list->nodes, i, node_contact_t); - if (node_to_query->id != node->id) { /* No need to query ourselves */ - send_find_node(node, node_to_query->id, destination); - j++; - } - i++; - } - return i; -} - -/** @brief Handles an incoming received task */ -void handle_task(node_t node, msg_task_t task) -{ - const_task_data_t data = MSG_task_get_data(task); - xbt_assert((data != NULL), "Received NULL data"); - //Adding/updating the guy to our routing table - node_routing_table_update(node, data->sender_id); - switch (data->type) { - case TASK_FIND_NODE: - handle_find_node(node, data); - break; - case TASK_FIND_NODE_ANSWER: - XBT_DEBUG("Received a wrong answer for a FIND_NODE"); - break; - default: - break; - } - task_free(task); -} - -/** @brief Handles the answer to an incoming "find_node" task */ -void handle_find_node(node_t node, const_task_data_t data) -{ - XBT_VERB("Received a FIND_NODE from %s (%s), he's trying to find %08x", - data->answer_to, data->issuer_host_name, data->destination_id); - //Building the answer to the request - answer_t answer = node_find_closest(node, data->destination_id); - //Building the task to send - msg_task_t task = task_new_find_node_answer(node->id, data->destination_id, answer, node->mailbox, - MSG_host_get_name(MSG_host_self())); - //Sending the task - MSG_task_dsend(task, data->answer_to, task_free_v); -} - -/** @brief Main function */ -int main(int argc, char *argv[]) -{ - MSG_init(&argc, argv); - - /* Check the arguments */ - xbt_assert(argc > 2, "Usage: %s platform_file deployment_file\n\tExample: %s msg_platform.xml msg_deployment.xml\n", - argv[0], argv[0]); - - const char *platform_file = argv[1]; - const char *deployment_file = argv[2]; - - MSG_create_environment(platform_file); - MSG_function_register("node", node); - MSG_launch_application(deployment_file); - - msg_error_t res = MSG_main(); - - XBT_INFO("Simulated time: %g", MSG_get_clock()); - - return res != MSG_OK; -} diff --git a/examples/deprecated/msg/dht-kademlia/dht-kademlia.h b/examples/deprecated/msg/dht-kademlia/dht-kademlia.h deleted file mode 100644 index 6d5913109b..0000000000 --- a/examples/deprecated/msg/dht-kademlia/dht-kademlia.h +++ /dev/null @@ -1,23 +0,0 @@ -/* Copyright (c) 2012-2020. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#ifndef _MSG_EXAMPLES_KADEMLIA_H -#define _MSG_EXAMPLES_KADEMLIA_H -#include "node.h" -#include "task.h" - -//core kademlia functions -unsigned int join(node_t node, unsigned int id_known); -unsigned int find_node(node_t node, unsigned int id_to_find, unsigned int count_in_stats); -void random_lookup(node_t node); - -void send_find_node(node_t node, unsigned int id, unsigned int destination); -unsigned int send_find_node_to_best(node_t node, const_answer_t node_list); - -void handle_task(node_t node, msg_task_t task); -void handle_find_node(node_t node, const_task_data_t data); - -#endif /* _MSG_EXAMPLES_KADEMLIA_H */ diff --git a/examples/deprecated/msg/dht-kademlia/node.c b/examples/deprecated/msg/dht-kademlia/node.c deleted file mode 100644 index 286f513aa3..0000000000 --- a/examples/deprecated/msg/dht-kademlia/node.c +++ /dev/null @@ -1,172 +0,0 @@ -/* Copyright (c) 2010-2020. The SimGrid Team. All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#include "node.h" -#include "routing_table.h" -#include "simgrid/msg.h" - -#include /* snprintf */ - -XBT_LOG_NEW_DEFAULT_CATEGORY(msg_kademlia_node, "Messages specific for this msg example"); - -/** @brief Initialization of a node - * @param node_id the id of the node - * @return the node created - */ -node_t node_init(unsigned int node_id) -{ - node_t node = xbt_new(s_node_t, 1); - - node->id = node_id; - node->table = routing_table_init(node_id); - snprintf(node->mailbox, MAILBOX_NAME_SIZE - 1, "%u", node_id); - node->find_node_failed = 0; - node->find_node_success = 0; - - node->task_received = NULL; - node->receive_comm = NULL; - - return node; -} - -/* @brief Node destructor */ -void node_free(node_t node) -{ - routing_table_free(node->table); - xbt_free(node); -} - -/** @brief Updates/Puts the node id unsigned into our routing table - * @param node Our node data - * @param id The id of the node we need to add unsigned into our routing table - */ -void node_routing_table_update(const_node_t node, unsigned int id) -{ - const_routing_table_t table = node->table; - //retrieval of the bucket in which the should be - const_bucket_t bucket = routing_table_find_bucket(table, id); - - //check if the id is already in the bucket. - unsigned int id_pos = bucket_find_id(bucket, id); - - if (id_pos == -1) { - /* We check if the bucket is full or not. If it is, we evict old offline elements */ - if (xbt_dynar_length(bucket->nodes) < BUCKET_SIZE) { - //TODO: this is not really very efficient. Maybe we should use something else than dynars ? - xbt_dynar_unshift(bucket->nodes, &id); - XBT_VERB("I'm adding to my routing table %08x", id); - } else { - /* TODO: we need to evict the old elements: that's why this function is in "node" instead of "routing table". - * This is not implemented yet. */ - } - } else { - //We push to the front of the dynar the element. - unsigned int element = xbt_dynar_get_as(bucket->nodes, id_pos, unsigned int); - xbt_dynar_remove_at(bucket->nodes, id_pos, NULL); - xbt_dynar_unshift(bucket->nodes, &element); - XBT_VERB("I'm updating %08x", element); - } -} - -/** @brief Finds the closest nodes to the node given. - * @param node : our node - * @param destination_id : the id of the guy we are trying to find - */ -answer_t node_find_closest(const_node_t node, unsigned int destination_id) -{ - int i; - answer_t answer = answer_init(destination_id); - /* We find the corresponding bucket for the id */ - const_bucket_t bucket = routing_table_find_bucket(node->table, destination_id); - int bucket_id = bucket->id; - xbt_assert((bucket_id <= IDENTIFIER_SIZE), "Bucket found has a wrong identifier"); - /* So, we copy the contents of the bucket unsigned into our result dynar */ - answer_add_bucket(bucket, answer); - - /* However, if we don't have enough elements in our bucket, we NEED to include at least "BUCKET_SIZE" elements - * (if, of course, we know at least "BUCKET_SIZE" elements. So we're going to look unsigned into the other buckets. - */ - for (i = 1; answer->size < BUCKET_SIZE && ((bucket_id - i > 0) || (bucket_id + i < IDENTIFIER_SIZE)); i++) { - /* We check the previous buckets */ - if (bucket_id - i >= 0) { - const_bucket_t bucket_p = &node->table->buckets[bucket_id - i]; - answer_add_bucket(bucket_p, answer); - } - /* We check the next buckets */ - if (bucket_id + i <= IDENTIFIER_SIZE) { - const_bucket_t bucket_n = &node->table->buckets[bucket_id + i]; - answer_add_bucket(bucket_n, answer); - } - } - /* We sort the array by XOR distance */ - answer_sort(answer); - /* We trim the array to have only BUCKET_SIZE or less elements */ - answer_trim(answer); - - return answer; -} - -/**@brief Returns an identifier which is in a specific bucket of a routing table - * @param id id of the routing table owner - * @param prefix id of the bucket where we want that identifier to be - */ -unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix) -{ - if (prefix == 0) { - return 0; - } else { - return (1U << ((unsigned int)(prefix - 1))) ^ id; - } -} - -/** @brief Returns the prefix of an identifier. - * The prefix is the id of the bucket in which the remote identifier xor our identifier should be stored. - * @param id : big unsigned int id to test - * @param nb_bits : key size - */ -unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits) -{ - unsigned int size = sizeof(unsigned int) * 8; - for (unsigned int j = 0; j < size; j++) { - if (((id >> (size - 1 - j)) & 0x1) != 0) { - return nb_bits - (j); - } - } - return 0; -} - -/** @brief Gets the mailbox name of a host given its identifier */ -void get_node_mailbox(unsigned int id, char *mailbox) -{ - snprintf(mailbox, MAILBOX_NAME_SIZE - 1, "%u", id); -} - -/** Constructor, build a new contact information. */ -node_contact_t node_contact_new(unsigned int id, unsigned int distance) -{ - node_contact_t contact = xbt_new(s_node_contact_t, 1); - - contact->id = id; - contact->distance = distance; - - return contact; -} - -/** Builds a contact information from a contact information */ -node_contact_t node_contact_copy(const_node_contact_t node_contact) -{ - node_contact_t contact = xbt_new(s_node_contact_t, 1); - - contact->id = node_contact->id; - contact->distance = node_contact->distance; - - return contact; -} - -/** Destructor */ -void node_contact_free(node_contact_t contact) -{ - xbt_free(contact); -} diff --git a/examples/deprecated/msg/dht-kademlia/node.h b/examples/deprecated/msg/dht-kademlia/node.h deleted file mode 100644 index f67f2cf47e..0000000000 --- a/examples/deprecated/msg/dht-kademlia/node.h +++ /dev/null @@ -1,55 +0,0 @@ -/* Copyright (c) 2012-2020. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#ifndef _MSG_EXAMPLES_ROUTING_H -#define _MSG_EXAMPLES_ROUTING_H -#include "xbt/dynar.h" -#include "simgrid/msg.h" - -#include "common.h" -#include "answer.h" -#include "routing_table.h" - -/* Information about a foreign node */ -typedef struct s_node_contact { - unsigned int id; //The node identifier - unsigned int distance; //The distance from the node -} s_node_contact_t; - -typedef s_node_contact_t *node_contact_t; -typedef const s_node_contact_t* const_node_contact_t; - -/* Node data */ -typedef struct s_node { - unsigned int id; //node id - 160 bits - routing_table_t table; //node routing table - msg_comm_t receive_comm; //current receiving communication. - msg_task_t task_received; //current task being received - - char mailbox[MAILBOX_NAME_SIZE]; //node mailbox - unsigned int find_node_success; //Number of find_node which have succeeded. - unsigned int find_node_failed; //Number of find_node which have failed. -} s_node_t; - -typedef s_node_t *node_t; -typedef const s_node_t* const_node_t; - -// node functions -node_t node_init(unsigned int id); -void node_free(node_t node); -void node_routing_table_update(const_node_t node, unsigned int id); -answer_t node_find_closest(const_node_t node, unsigned int destination_id); - -// identifier functions -unsigned int get_id_in_prefix(unsigned int id, unsigned int prefix); -unsigned int get_node_prefix(unsigned int id, unsigned int nb_bits); -void get_node_mailbox(unsigned int id, char *mailbox); - -// node contact functions -node_contact_t node_contact_new(unsigned int id, unsigned int distance); -node_contact_t node_contact_copy(const_node_contact_t node_contact); -void node_contact_free(node_contact_t contact); -#endif /* _MSG_EXAMPLES_ROUTING_H */ diff --git a/examples/deprecated/msg/dht-kademlia/task.c b/examples/deprecated/msg/dht-kademlia/task.c deleted file mode 100644 index cbe8b644e7..0000000000 --- a/examples/deprecated/msg/dht-kademlia/task.c +++ /dev/null @@ -1,78 +0,0 @@ -/* Copyright (c) 2012-2020. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#include "task.h" -#include "answer.h" - -/** @brief Creates a new "find node" task - * @param sender_id the id of the node who sends the task - * @param destination_id the id the sender is trying to find - * @param hostname the hostname of the node, for logging purposes - */ -msg_task_t task_new_find_node(unsigned int sender_id, unsigned int destination_id, char *mailbox, const char *hostname) -{ - task_data_t data = xbt_new(s_task_data_t, 1); - - data->type = TASK_FIND_NODE; - data->sender_id = sender_id; - data->destination_id = destination_id; - data->answer = NULL; - data->answer_to = mailbox; - data->issuer_host_name = hostname; - - msg_task_t task = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, data); - - return task; -} - -/** @brief Creates a new "answer to find node" task - * @param sender_id the node who sent the task - * @param destination_id the node that should be found - * @param answer the answer to send - * @param mailbox The mailbox of the sender - * @param hostname sender hostname - */ -msg_task_t task_new_find_node_answer(unsigned int sender_id, unsigned int destination_id, answer_t answer, - char *mailbox, const char *hostname) -{ - task_data_t data = xbt_new(s_task_data_t, 1); - - data->type = TASK_FIND_NODE_ANSWER; - data->sender_id = sender_id; - data->destination_id = destination_id; - data->answer = answer; - data->answer_to = mailbox; - data->issuer_host_name = hostname; - - msg_task_t task = MSG_task_create(NULL, COMP_SIZE, COMM_SIZE, data); - - return task; -} - -/** @brief Destroys a task and its data - * @param task the task that'll be destroyed - */ -void task_free(msg_task_t task) -{ - xbt_assert((task != NULL), "Tried to free a NULL task"); - - task_data_t data = MSG_task_get_data(task); - - if (data->answer) { - answer_free(data->answer); - } - xbt_free(data); - - MSG_task_destroy(task); -} - -/** @brief Destroys a task and its data (taking a void* pointer - * @param task The task that'll be destroyed - */ -void task_free_v(void *task) -{ - task_free(task); -} diff --git a/examples/deprecated/msg/dht-kademlia/task.h b/examples/deprecated/msg/dht-kademlia/task.h deleted file mode 100644 index 80141d499e..0000000000 --- a/examples/deprecated/msg/dht-kademlia/task.h +++ /dev/null @@ -1,41 +0,0 @@ -/* Copyright (c) 2012-2020. The SimGrid Team. - * All rights reserved. */ - -/* This program is free software; you can redistribute it and/or modify it - * under the terms of the license (GNU LGPL) which comes with this package. */ - -#ifndef _MSG_KADEMLIA_EXAMPLES_TASK -#define _MSG_KADEMLIA_EXAMPLES_TASK -#include "common.h" -#include "node.h" -#include "simgrid/msg.h" - -/* Types of tasks exchanged */ -typedef enum { - TASK_FIND_NODE, - TASK_FIND_NODE_ANSWER, - TASK_FIND_VALUE, - TASK_FIND_VALUE_ANSWER, - TASK_LEAVING -} e_task_type_t; - -/* Data attached with the tasks */ -typedef struct s_task_data { - e_task_type_t type; - unsigned int sender_id; //Id of the guy who sent the task - unsigned int destination_id; //Id we are trying to find, if needed. - answer_t answer; //Answer to the request made, if needed. - char *answer_to; // mailbox to send the answer to (if not an answer). - const char *issuer_host_name; // used for logging -} s_task_data_t; - -typedef s_task_data_t *task_data_t; -typedef const s_task_data_t* const_task_data_t; - -//Task handling functions -msg_task_t task_new_find_node(unsigned int sender_id, unsigned int destination_id, char *mailbox, const char *hostname); -msg_task_t task_new_find_node_answer(unsigned int sender_id, unsigned int destination_id, answer_t answer, - char *mailbox, const char *hostname); -void task_free(msg_task_t task); -void task_free_v(void *task); -#endif /* _MSG_KADEMLIA_EXAMPLES_TASK */ diff --git a/examples/s4u/dht-kademlia/node.cpp b/examples/s4u/dht-kademlia/node.cpp index 9b09d69a05..fc2a7e481f 100644 --- a/examples/s4u/dht-kademlia/node.cpp +++ b/examples/s4u/dht-kademlia/node.cpp @@ -81,6 +81,7 @@ void Node::sendFindNode(unsigned int id, unsigned int destination) /* Gets the mailbox to send to */ simgrid::s4u::Mailbox* mailbox = simgrid::s4u::Mailbox::by_name(std::to_string(id)); /* Build the task */ + Message* msg = new Message(id_, destination, simgrid::s4u::Mailbox::by_name(std::to_string(id_)), simgrid::s4u::Host::current()->get_cname()); diff --git a/teshsuite/msg/CMakeLists.txt b/teshsuite/msg/CMakeLists.txt index eeaa9c08e7..6782fe736d 100644 --- a/teshsuite/msg/CMakeLists.txt +++ b/teshsuite/msg/CMakeLists.txt @@ -28,8 +28,7 @@ set(xml_files ${xml_files} ${CMAKE_CURRENT_SOURCE_DIR}/app-bittorrent/ap PARENT_SCOPE) if(enable_msg) - foreach(x app-bittorrent cloud-two-tasks get_sender task_destroy_cancel task_listen_from - io-file) + foreach(x app-bittorrent cloud-two-tasks get_sender task_destroy_cancel task_listen_from io-file) ADD_TESH_FACTORIES(tesh-msg-${x} "raw" --setenv platfdir=${CMAKE_HOME_DIRECTORY}/examples/platforms --setenv bindir=${CMAKE_BINARY_DIR}/teshsuite/msg/${x} -- 2.20.1