diff options
author | irungentoo <irungentoo@gmail.com> | 2013-06-25 12:11:11 -0400 |
---|---|---|
committer | irungentoo <irungentoo@gmail.com> | 2013-06-25 12:11:11 -0400 |
commit | 3396d8e495598c2b8ee1cdb2dd5f748647971c26 (patch) | |
tree | de7d07e18488976db5687454ba8c1929cef1a2c8 /core | |
parent | 338bfc151023474bd09030cbededa49d0816efc6 (diff) |
DHT implementation finished. Currently testing it.
Diffstat (limited to 'core')
-rw-r--r-- | core/DHT.c | 140 | ||||
-rw-r--r-- | core/DHT.h | 12 |
2 files changed, 113 insertions, 39 deletions
@@ -9,6 +9,7 @@ int sendpacket(IP_Port ip_port, char * data, uint32_t length) | |||
9 | { | 9 | { |
10 | ADDR addr = {AF_INET, ip_port.port, ip_port.ip}; | 10 | ADDR addr = {AF_INET, ip_port.port, ip_port.ip}; |
11 | return sendto(sock, data, length, 0, (struct sockaddr *)&addr, sizeof(addr)); | 11 | return sendto(sock, data, length, 0, (struct sockaddr *)&addr, sizeof(addr)); |
12 | |||
12 | } | 13 | } |
13 | 14 | ||
14 | //Function to recieve data, ip and port of sender is put into ip_port | 15 | //Function to recieve data, ip and port of sender is put into ip_port |
@@ -27,6 +28,7 @@ int recievepacket(IP_Port * ip_port, char * data, uint32_t * length) | |||
27 | ip_port->ip = addr.ip; | 28 | ip_port->ip = addr.ip; |
28 | ip_port->port = addr.port; | 29 | ip_port->port = addr.port; |
29 | return 0; | 30 | return 0; |
31 | |||
30 | } | 32 | } |
31 | 33 | ||
32 | 34 | ||
@@ -35,7 +37,7 @@ int recievepacket(IP_Port * ip_port, char * data, uint32_t * length) | |||
35 | //return 0 if both are same distance | 37 | //return 0 if both are same distance |
36 | //return 1 if client_id1 is closer. | 38 | //return 1 if client_id1 is closer. |
37 | //return 2 if client_id2 is closer. | 39 | //return 2 if client_id2 is closer. |
38 | int id_closest(char * client_id, char * client_id1, char * client_id2) | 40 | int id_closest(char * client_id, char * client_id1, char * client_id2)//tested |
39 | { | 41 | { |
40 | uint32_t i; | 42 | uint32_t i; |
41 | for(i = 0; i < CLIENT_ID_SIZE; i++) | 43 | for(i = 0; i < CLIENT_ID_SIZE; i++) |
@@ -52,6 +54,7 @@ int id_closest(char * client_id, char * client_id1, char * client_id2) | |||
52 | } | 54 | } |
53 | 55 | ||
54 | return 0; | 56 | return 0; |
57 | |||
55 | } | 58 | } |
56 | 59 | ||
57 | //check if client with client_id is already in list of length length. | 60 | //check if client with client_id is already in list of length length. |
@@ -78,6 +81,7 @@ int client_in_list(Client_data * list, uint32_t length, char * client_id) | |||
78 | } | 81 | } |
79 | } | 82 | } |
80 | return 0; | 83 | return 0; |
84 | |||
81 | } | 85 | } |
82 | 86 | ||
83 | //check if client with client_id is already in node format list of length length. | 87 | //check if client with client_id is already in node format list of length length. |
@@ -102,6 +106,7 @@ int client_in_nodelist(Node_format * list, uint32_t length, char * client_id) | |||
102 | } | 106 | } |
103 | } | 107 | } |
104 | return 0; | 108 | return 0; |
109 | |||
105 | } | 110 | } |
106 | 111 | ||
107 | 112 | ||
@@ -172,6 +177,7 @@ int get_close_nodes(char * client_id, Node_format * nodes_list) | |||
172 | } | 177 | } |
173 | 178 | ||
174 | return num_nodes; | 179 | return num_nodes; |
180 | |||
175 | } | 181 | } |
176 | 182 | ||
177 | 183 | ||
@@ -179,7 +185,7 @@ int get_close_nodes(char * client_id, Node_format * nodes_list) | |||
179 | //replace first bad (or empty) node with this one | 185 | //replace first bad (or empty) node with this one |
180 | //return 0 if successfull | 186 | //return 0 if successfull |
181 | //return 1 if not (list contains no bad nodes) | 187 | //return 1 if not (list contains no bad nodes) |
182 | int replace_bad(Client_data * list, uint32_t length, char * client_id, IP_Port ip_port) | 188 | int replace_bad(Client_data * list, uint32_t length, char * client_id, IP_Port ip_port)//tested |
183 | { | 189 | { |
184 | uint32_t i; | 190 | uint32_t i; |
185 | uint32_t temp_time = unix_time(); | 191 | uint32_t temp_time = unix_time(); |
@@ -194,6 +200,7 @@ int replace_bad(Client_data * list, uint32_t length, char * client_id, IP_Port i | |||
194 | } | 200 | } |
195 | } | 201 | } |
196 | return 1; | 202 | return 1; |
203 | |||
197 | } | 204 | } |
198 | 205 | ||
199 | //replace the first good node further to the comp_client_id than that of the client_id | 206 | //replace the first good node further to the comp_client_id than that of the client_id |
@@ -211,6 +218,7 @@ int replace_good(Client_data * list, uint32_t length, char * client_id, IP_Port | |||
211 | } | 218 | } |
212 | } | 219 | } |
213 | return 1; | 220 | return 1; |
221 | |||
214 | } | 222 | } |
215 | 223 | ||
216 | //Attempt to add client with ip_port and client_id to the friends client list and close_clientlist | 224 | //Attempt to add client with ip_port and client_id to the friends client list and close_clientlist |
@@ -239,11 +247,8 @@ void addto_lists(IP_Port ip_port, char * client_id) | |||
239 | //if we can't replace bad nodes we try replacing good ones | 247 | //if we can't replace bad nodes we try replacing good ones |
240 | replace_good(friends_list[i].client_list, MAX_FRIEND_CLIENTS, client_id, ip_port, self_client_id); | 248 | replace_good(friends_list[i].client_list, MAX_FRIEND_CLIENTS, client_id, ip_port, self_client_id); |
241 | } | 249 | } |
242 | |||
243 | } | 250 | } |
244 | } | 251 | } |
245 | |||
246 | |||
247 | } | 252 | } |
248 | 253 | ||
249 | 254 | ||
@@ -313,6 +318,7 @@ int add_pinging(IP_Port ip_port) | |||
313 | } | 318 | } |
314 | } | 319 | } |
315 | return 0; | 320 | return 0; |
321 | |||
316 | } | 322 | } |
317 | 323 | ||
318 | //Same but for get node requests | 324 | //Same but for get node requests |
@@ -334,6 +340,7 @@ int add_gettingnodes(IP_Port ip_port) | |||
334 | } | 340 | } |
335 | } | 341 | } |
336 | return 0; | 342 | return 0; |
343 | |||
337 | } | 344 | } |
338 | 345 | ||
339 | 346 | ||
@@ -398,25 +405,31 @@ int getnodes(IP_Port ip_port, char * client_id) | |||
398 | memcpy(data + 5 + CLIENT_ID_SIZE, client_id, CLIENT_ID_SIZE); | 405 | memcpy(data + 5 + CLIENT_ID_SIZE, client_id, CLIENT_ID_SIZE); |
399 | 406 | ||
400 | return sendpacket(ip_port, data, sizeof(data)); | 407 | return sendpacket(ip_port, data, sizeof(data)); |
408 | |||
401 | } | 409 | } |
402 | 410 | ||
403 | 411 | ||
404 | //send a send nodes response | 412 | //send a send nodes response |
405 | //Currently incomplete: missing bunch of stuff | ||
406 | int sendnodes(IP_Port ip_port, char * client_id, uint32_t ping_id) | 413 | int sendnodes(IP_Port ip_port, char * client_id, uint32_t ping_id) |
407 | { | 414 | { |
408 | char data[5 + (CLIENT_ID_SIZE + sizeof(IP_Port))*MAX_SENT_NODES]; | 415 | char data[5 + (CLIENT_ID_SIZE + sizeof(IP_Port))*MAX_SENT_NODES]; |
409 | Node_format nodes_list[MAX_SENT_NODES]; | 416 | Node_format nodes_list[MAX_SENT_NODES]; |
410 | 417 | ||
411 | int num_nodes = get_close_nodes(client_id, nodes_list); | 418 | int num_nodes = get_close_nodes(client_id, nodes_list); |
412 | 419 | ||
413 | data[0] = 3; | 420 | if(num_nodes == 0) |
414 | 421 | { | |
415 | memcpy(data + 1, &ping_id, 4); | 422 | return 0; |
416 | memcpy(data + 5, self_client_id, CLIENT_ID_SIZE); | 423 | } |
417 | memcpy(data + 5 + CLIENT_ID_SIZE, nodes_list, num_nodes * (CLIENT_ID_SIZE + sizeof(IP_Port))); | 424 | |
425 | data[0] = 3; | ||
426 | |||
427 | memcpy(data + 1, &ping_id, 4); | ||
428 | memcpy(data + 5, self_client_id, CLIENT_ID_SIZE); | ||
429 | memcpy(data + 5 + CLIENT_ID_SIZE, nodes_list, num_nodes * (CLIENT_ID_SIZE + sizeof(IP_Port))); | ||
430 | |||
431 | return sendpacket(ip_port, data, 5 + CLIENT_ID_SIZE + num_nodes * (CLIENT_ID_SIZE + sizeof(IP_Port))); | ||
418 | 432 | ||
419 | return sendpacket(ip_port, data, 5 + CLIENT_ID_SIZE + num_nodes * (CLIENT_ID_SIZE + sizeof(IP_Port))); | ||
420 | } | 433 | } |
421 | 434 | ||
422 | 435 | ||
@@ -425,7 +438,7 @@ int sendnodes(IP_Port ip_port, char * client_id, uint32_t ping_id) | |||
425 | //Packet handling functions | 438 | //Packet handling functions |
426 | //One to handle each types of packets we recieve | 439 | //One to handle each types of packets we recieve |
427 | 440 | ||
428 | int handle_pingreq(char * packet, uint32_t length, IP_Port source) | 441 | int handle_pingreq(char * packet, uint32_t length, IP_Port source)//tested |
429 | { | 442 | { |
430 | if(length != 5 + CLIENT_ID_SIZE) | 443 | if(length != 5 + CLIENT_ID_SIZE) |
431 | { | 444 | { |
@@ -440,9 +453,10 @@ int handle_pingreq(char * packet, uint32_t length, IP_Port source) | |||
440 | pingreq(source); | 453 | pingreq(source); |
441 | 454 | ||
442 | return 0; | 455 | return 0; |
456 | |||
443 | } | 457 | } |
444 | 458 | ||
445 | int handle_pingres(char * packet, uint32_t length, IP_Port source) | 459 | int handle_pingres(char * packet, uint32_t length, IP_Port source)//tested |
446 | { | 460 | { |
447 | if(length != (5 + CLIENT_ID_SIZE)) | 461 | if(length != (5 + CLIENT_ID_SIZE)) |
448 | { | 462 | { |
@@ -451,6 +465,7 @@ int handle_pingres(char * packet, uint32_t length, IP_Port source) | |||
451 | 465 | ||
452 | addto_lists(source, packet + 5); | 466 | addto_lists(source, packet + 5); |
453 | return 0; | 467 | return 0; |
468 | |||
454 | } | 469 | } |
455 | 470 | ||
456 | int handle_getnodes(char * packet, uint32_t length, IP_Port source) | 471 | int handle_getnodes(char * packet, uint32_t length, IP_Port source) |
@@ -466,20 +481,21 @@ int handle_getnodes(char * packet, uint32_t length, IP_Port source) | |||
466 | pingreq(source); | 481 | pingreq(source); |
467 | 482 | ||
468 | return 0; | 483 | return 0; |
484 | |||
469 | } | 485 | } |
470 | 486 | ||
471 | int handle_sendnodes(char * packet, uint32_t length, IP_Port source) | 487 | int handle_sendnodes(char * packet, uint32_t length, IP_Port source)//tested |
472 | { | 488 | { |
473 | if(length > 5 + MAX_SENT_NODES * (CLIENT_ID_SIZE + sizeof(IP_Port)) || | 489 | if(length > (5 + CLIENT_ID_SIZE + MAX_SENT_NODES * (CLIENT_ID_SIZE + sizeof(IP_Port))) || |
474 | (length - 5) % (CLIENT_ID_SIZE + sizeof(IP_Port)) != 0) | 490 | (length - 5 - CLIENT_ID_SIZE) % (CLIENT_ID_SIZE + sizeof(IP_Port)) != 0) |
475 | { | 491 | { |
476 | return 1; | 492 | return 1; |
477 | } | 493 | } |
478 | int num_nodes = (length - 5) / (CLIENT_ID_SIZE + sizeof(IP_Port)); | 494 | int num_nodes = (length - 5 - CLIENT_ID_SIZE) / (CLIENT_ID_SIZE + sizeof(IP_Port)); |
479 | uint32_t i; | 495 | uint32_t i; |
480 | 496 | ||
481 | Node_format nodes_list[MAX_SENT_NODES]; | 497 | Node_format nodes_list[MAX_SENT_NODES]; |
482 | memcpy(nodes_list, packet + 5, num_nodes); | 498 | memcpy(nodes_list, packet + 5 + CLIENT_ID_SIZE, num_nodes * (CLIENT_ID_SIZE + sizeof(IP_Port))); |
483 | 499 | ||
484 | for(i = 0; i < num_nodes; i++) | 500 | for(i = 0; i < num_nodes; i++) |
485 | { | 501 | { |
@@ -488,25 +504,31 @@ int handle_sendnodes(char * packet, uint32_t length, IP_Port source) | |||
488 | 504 | ||
489 | addto_lists(source, packet + 5); | 505 | addto_lists(source, packet + 5); |
490 | return 0; | 506 | return 0; |
507 | |||
491 | } | 508 | } |
492 | 509 | ||
493 | //END of packet handling functions | 510 | //END of packet handling functions |
494 | 511 | ||
495 | 512 | ||
496 | 513 | ||
497 | void addfriend(char * client_id) | 514 | int addfriend(char * client_id) |
498 | { | 515 | { |
499 | //TODO: Make the array of friends dynamic instead of a static array with 256 places.. | 516 | //TODO:Maybe make the array of friends dynamic instead of a static array with 256 |
500 | //WARNING:This will segfault if the number of friends exceeds 256. | 517 | if(MAX_FRIENDS > num_friends) |
501 | memcpy(friends_list[num_friends].client_id, client_id, CLIENT_ID_SIZE); | 518 | { |
502 | num_friends++; | 519 | memcpy(friends_list[num_friends].client_id, client_id, CLIENT_ID_SIZE); |
520 | num_friends++; | ||
521 | return 0; | ||
522 | } | ||
523 | return 1; | ||
524 | |||
503 | } | 525 | } |
504 | 526 | ||
505 | 527 | ||
506 | 528 | ||
507 | 529 | ||
508 | 530 | ||
509 | char delfriend(char * client_id) | 531 | int delfriend(char * client_id) |
510 | { | 532 | { |
511 | uint32_t i; | 533 | uint32_t i; |
512 | for(i = 0; i < num_friends; i++) | 534 | for(i = 0; i < num_friends; i++) |
@@ -519,6 +541,7 @@ char delfriend(char * client_id) | |||
519 | } | 541 | } |
520 | } | 542 | } |
521 | return 1; | 543 | return 1; |
544 | |||
522 | } | 545 | } |
523 | 546 | ||
524 | 547 | ||
@@ -548,6 +571,7 @@ IP_Port getfriendip(char * client_id) | |||
548 | } | 571 | } |
549 | empty.ip.i = 1; | 572 | empty.ip.i = 1; |
550 | return empty; | 573 | return empty; |
574 | |||
551 | } | 575 | } |
552 | 576 | ||
553 | 577 | ||
@@ -574,7 +598,8 @@ int DHT_recvpacket(char * packet, uint32_t length, IP_Port source) | |||
574 | 598 | ||
575 | } | 599 | } |
576 | 600 | ||
577 | return 0; | 601 | return 0; |
602 | |||
578 | } | 603 | } |
579 | 604 | ||
580 | //The timeout after which a node is discarded completely. | 605 | //The timeout after which a node is discarded completely. |
@@ -583,12 +608,23 @@ return 0; | |||
583 | //ping interval in seconds for each node in our lists. | 608 | //ping interval in seconds for each node in our lists. |
584 | #define PING_INTERVAL 60 | 609 | #define PING_INTERVAL 60 |
585 | 610 | ||
611 | //ping interval in seconds for each random sending of a get nodes request. | ||
612 | #define GET_NODE_INTERVAL 20 | ||
613 | |||
586 | //Ping each client in the "friends" list every 60 seconds. | 614 | //Ping each client in the "friends" list every 60 seconds. |
587 | //Send a get nodes request every 20 seconds to a random good node for each "friend" in our "friends" list. | 615 | //Send a get nodes request every 20 seconds to a random good node for each "friend" in our "friends" list. |
616 | |||
617 | uint32_t friend_lastgetnode[MAX_FRIENDS]; | ||
618 | |||
619 | |||
588 | void doFriends() | 620 | void doFriends() |
589 | { | 621 | { |
590 | uint32_t i, j; | 622 | uint32_t i, j; |
591 | uint32_t temp_time = unix_time(); | 623 | uint32_t temp_time = unix_time(); |
624 | uint32_t num_nodes = 0; | ||
625 | uint32_t rand_node; | ||
626 | uint32_t index[MAX_FRIEND_CLIENTS]; | ||
627 | |||
592 | for(i = 0; i < num_friends; i++) | 628 | for(i = 0; i < num_friends; i++) |
593 | { | 629 | { |
594 | for(j = 0; j < MAX_FRIEND_CLIENTS; j++) | 630 | for(j = 0; j < MAX_FRIEND_CLIENTS; j++) |
@@ -600,18 +636,36 @@ void doFriends() | |||
600 | { | 636 | { |
601 | pingreq(friends_list[i].client_list[j].ip_port); | 637 | pingreq(friends_list[i].client_list[j].ip_port); |
602 | } | 638 | } |
603 | //TODO: Send getnodes requests | 639 | if(friends_list[i].client_list[j].timestamp + BAD_NODE_TIMEOUT > temp_time)//if node is good. |
604 | } | 640 | { |
641 | index[num_nodes] = j; | ||
642 | num_nodes++; | ||
643 | } | ||
644 | } | ||
645 | } | ||
646 | if(friend_lastgetnode[i] + GET_NODE_INTERVAL <= temp_time && num_nodes != 0) | ||
647 | { | ||
648 | rand_node = rand() % num_nodes; | ||
649 | getnodes(friends_list[i].client_list[index[rand_node]].ip_port, | ||
650 | friends_list[i].client_list[index[rand_node]].client_id); | ||
651 | friend_lastgetnode[i] = temp_time; | ||
605 | } | 652 | } |
606 | } | 653 | } |
607 | } | 654 | } |
608 | 655 | ||
656 | uint32_t close_lastgetnodes; | ||
609 | 657 | ||
610 | void doClose() | 658 | //Ping each client in the close nodes list every 60 seconds. |
659 | //Send a get nodes request every 20 seconds to a random good node int the list. | ||
660 | void doClose()//tested | ||
611 | { | 661 | { |
612 | uint32_t i; | 662 | uint32_t i; |
613 | uint32_t temp_time = unix_time(); | 663 | uint32_t temp_time = unix_time(); |
614 | for(i = 0; i < MAX_FRIEND_CLIENTS; i++) | 664 | uint32_t num_nodes = 0; |
665 | uint32_t rand_node; | ||
666 | uint32_t index[LCLIENT_LIST]; | ||
667 | |||
668 | for(i = 0; i < LCLIENT_LIST; i++) | ||
615 | { | 669 | { |
616 | if(close_clientlist[i].timestamp + Kill_NODE_TIMEOUT > temp_time)//if node is not dead. | 670 | if(close_clientlist[i].timestamp + Kill_NODE_TIMEOUT > temp_time)//if node is not dead. |
617 | { | 671 | { |
@@ -620,9 +674,23 @@ void doClose() | |||
620 | { | 674 | { |
621 | pingreq(close_clientlist[i].ip_port); | 675 | pingreq(close_clientlist[i].ip_port); |
622 | } | 676 | } |
677 | if(close_clientlist[i].timestamp + BAD_NODE_TIMEOUT > temp_time)//if node is good. | ||
678 | { | ||
679 | index[num_nodes] = i; | ||
680 | num_nodes++; | ||
681 | } | ||
623 | //TODO: Send getnodes requests | 682 | //TODO: Send getnodes requests |
624 | } | 683 | } |
625 | } | 684 | } |
685 | |||
686 | if(close_lastgetnodes + GET_NODE_INTERVAL <= temp_time && num_nodes != 0) | ||
687 | { | ||
688 | rand_node = rand() % num_nodes; | ||
689 | getnodes(close_clientlist[index[rand_node]].ip_port, | ||
690 | close_clientlist[index[rand_node]].client_id); | ||
691 | close_lastgetnodes = temp_time; | ||
692 | } | ||
693 | |||
626 | } | 694 | } |
627 | 695 | ||
628 | 696 | ||
@@ -92,13 +92,15 @@ typedef struct | |||
92 | 92 | ||
93 | //Add a new friend to the friends list | 93 | //Add a new friend to the friends list |
94 | //client_id must be CLIENT_ID_SIZE bytes long. | 94 | //client_id must be CLIENT_ID_SIZE bytes long. |
95 | void addfriend(char * client_id); | 95 | //returns 0 if success |
96 | //returns 1 if failure (friends list is full) | ||
97 | int addfriend(char * client_id); | ||
96 | 98 | ||
97 | //Delete a friend from the friends list | 99 | //Delete a friend from the friends list |
98 | //client_id must be CLIENT_ID_SIZE bytes long. | 100 | //client_id must be CLIENT_ID_SIZE bytes long. |
99 | //returns 0 if success | 101 | //returns 0 if success |
100 | //returns 1 if failure (client_id not in friends list) | 102 | //returns 1 if failure (client_id not in friends list) |
101 | char delfriend(char * client_id); | 103 | int delfriend(char * client_id); |
102 | 104 | ||
103 | 105 | ||
104 | //Get ip of friend | 106 | //Get ip of friend |
@@ -137,13 +139,17 @@ char self_client_id[CLIENT_ID_SIZE]; | |||
137 | //We only use one so it's much easier to have it as a global variable | 139 | //We only use one so it's much easier to have it as a global variable |
138 | int sock; | 140 | int sock; |
139 | 141 | ||
142 | //TODO: Move these out of here and put them into the .c file. | ||
140 | //A list of the clients mathematically closest to ours. | 143 | //A list of the clients mathematically closest to ours. |
141 | #define LCLIENT_LIST 32 | 144 | #define LCLIENT_LIST 32 |
142 | Client_data close_clientlist[LCLIENT_LIST]; | 145 | Client_data close_clientlist[LCLIENT_LIST]; |
143 | 146 | ||
144 | 147 | ||
148 | //Hard maximum number of friends | ||
149 | #define MAX_FRIENDS 256 | ||
150 | |||
145 | //Let's start with a static array for testing. | 151 | //Let's start with a static array for testing. |
146 | Friend friends_list[256]; | 152 | Friend friends_list[MAX_FRIENDS]; |
147 | uint16_t num_friends; | 153 | uint16_t num_friends; |
148 | 154 | ||
149 | //The list of ip ports along with the ping_id of what we sent them and a timestamp | 155 | //The list of ip ports along with the ping_id of what we sent them and a timestamp |