diff options
author | Christian Grothoff <christian@grothoff.org> | 2017-01-29 17:57:58 +0100 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2017-01-29 17:57:58 +0100 |
commit | dc430a9d23f8fd76f700d6836d4f4748429d70cd (patch) | |
tree | 8ae160786516d67c22a3188e965d05b987029499 /src/cadet | |
parent | 65fd774bf2f5ab1ccef337af7371b31e0e7e26a1 (diff) | |
download | gnunet-dc430a9d23f8fd76f700d6836d4f4748429d70cd.tar.gz gnunet-dc430a9d23f8fd76f700d6836d4f4748429d70cd.zip |
optimize mqm_head scans by avoiding constantly scanning over definitively non-ready entries
Diffstat (limited to 'src/cadet')
-rw-r--r-- | src/cadet/gnunet-service-cadet-new_peer.c | 55 |
1 files changed, 42 insertions, 13 deletions
diff --git a/src/cadet/gnunet-service-cadet-new_peer.c b/src/cadet/gnunet-service-cadet-new_peer.c index 97bb1378e..bcc69be53 100644 --- a/src/cadet/gnunet-service-cadet-new_peer.c +++ b/src/cadet/gnunet-service-cadet-new_peer.c | |||
@@ -29,7 +29,6 @@ | |||
29 | * where we actually need it (i.e. not if we have a direct connection, | 29 | * where we actually need it (i.e. not if we have a direct connection, |
30 | * or if we already have plenty of good short ones, or maybe even | 30 | * or if we already have plenty of good short ones, or maybe even |
31 | * to take a break if we have some connections and have searched a lot (?)) | 31 | * to take a break if we have some connections and have searched a lot (?)) |
32 | * - optimize MQM ready scans (O(n) -> O(1)) | ||
33 | */ | 32 | */ |
34 | #include "platform.h" | 33 | #include "platform.h" |
35 | #include "gnunet_util_lib.h" | 34 | #include "gnunet_util_lib.h" |
@@ -142,6 +141,11 @@ struct CadetPeer | |||
142 | struct GCP_MessageQueueManager *mqm_tail; | 141 | struct GCP_MessageQueueManager *mqm_tail; |
143 | 142 | ||
144 | /** | 143 | /** |
144 | * Pointer to first "ready" entry in @e mqm_head. | ||
145 | */ | ||
146 | struct GCP_MessageQueueManager *mqm_ready_ptr; | ||
147 | |||
148 | /** | ||
145 | * MIN-heap of paths owned by this peer (they also end at this | 149 | * MIN-heap of paths owned by this peer (they also end at this |
146 | * peer). Ordered by desirability. | 150 | * peer). Ordered by desirability. |
147 | */ | 151 | */ |
@@ -295,6 +299,7 @@ destroy_peer (void *cls) | |||
295 | notifications. Thus we can assert that mqm_head is empty at this | 299 | notifications. Thus we can assert that mqm_head is empty at this |
296 | point. */ | 300 | point. */ |
297 | GNUNET_assert (NULL == cp->mqm_head); | 301 | GNUNET_assert (NULL == cp->mqm_head); |
302 | GNUNET_assert (NULL == cp->mqm_ready_ptr); | ||
298 | GNUNET_free (cp); | 303 | GNUNET_free (cp); |
299 | } | 304 | } |
300 | 305 | ||
@@ -540,6 +545,10 @@ mqm_execute (struct GCP_MessageQueueManager *mqm) | |||
540 | { | 545 | { |
541 | struct CadetPeer *cp = mqm->cp; | 546 | struct CadetPeer *cp = mqm->cp; |
542 | 547 | ||
548 | /* Move ready pointer to the next entry that might be ready. */ | ||
549 | if ( (mqm == cp->mqm_ready_ptr) && | ||
550 | (NULL != mqm->next) ) | ||
551 | cp->mqm_ready_ptr = mqm->next; | ||
543 | /* Move entry to the end of the DLL, to be fair. */ | 552 | /* Move entry to the end of the DLL, to be fair. */ |
544 | if (mqm != cp->mqm_tail) | 553 | if (mqm != cp->mqm_tail) |
545 | { | 554 | { |
@@ -577,6 +586,29 @@ mqm_execute (struct GCP_MessageQueueManager *mqm) | |||
577 | 586 | ||
578 | 587 | ||
579 | /** | 588 | /** |
589 | * Find the next ready message in the queue (starting | ||
590 | * the search from the `cp->mqm_ready_ptr`) and if possible | ||
591 | * execute the transmission. | ||
592 | * | ||
593 | * @param cp peer to try to send the next ready message to | ||
594 | */ | ||
595 | static void | ||
596 | send_next_ready (struct CadetPeer *cp) | ||
597 | { | ||
598 | struct GCP_MessageQueueManager *mqm; | ||
599 | |||
600 | if (0 == cp->mqm_ready_counter) | ||
601 | return; | ||
602 | while ( (NULL != (mqm = cp->mqm_ready_ptr)) && | ||
603 | (NULL == mqm->env) ) | ||
604 | cp->mqm_ready_ptr = mqm->next; | ||
605 | if (NULL == mqm) | ||
606 | return; /* nothing to do */ | ||
607 | mqm_execute (mqm); | ||
608 | } | ||
609 | |||
610 | |||
611 | /** | ||
580 | * Function called when CORE took one of the messages from | 612 | * Function called when CORE took one of the messages from |
581 | * a message queue manager and transmitted it. | 613 | * a message queue manager and transmitted it. |
582 | * | 614 | * |
@@ -590,17 +622,7 @@ mqm_send_done (void *cls) | |||
590 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 622 | LOG (GNUNET_ERROR_TYPE_DEBUG, |
591 | "Sending to peer %s completed\n", | 623 | "Sending to peer %s completed\n", |
592 | GCP_2s (cp)); | 624 | GCP_2s (cp)); |
593 | if (0 == cp->mqm_ready_counter) | 625 | send_next_ready (cp); |
594 | return; /* nothing to do */ | ||
595 | for (struct GCP_MessageQueueManager *mqm = cp->mqm_head; | ||
596 | NULL != mqm; | ||
597 | mqm = mqm->next) | ||
598 | { | ||
599 | if (NULL == mqm->env) | ||
600 | continue; | ||
601 | mqm_execute (mqm); | ||
602 | return; | ||
603 | } | ||
604 | } | 626 | } |
605 | 627 | ||
606 | 628 | ||
@@ -617,6 +639,7 @@ GCP_send (struct GCP_MessageQueueManager *mqm, | |||
617 | { | 639 | { |
618 | struct CadetPeer *cp = mqm->cp; | 640 | struct CadetPeer *cp = mqm->cp; |
619 | 641 | ||
642 | GNUNET_assert (NULL != env); | ||
620 | LOG (GNUNET_ERROR_TYPE_DEBUG, | 643 | LOG (GNUNET_ERROR_TYPE_DEBUG, |
621 | "Queueing message to peer %s in MQM %p\n", | 644 | "Queueing message to peer %s in MQM %p\n", |
622 | GCP_2s (cp), | 645 | GCP_2s (cp), |
@@ -628,9 +651,13 @@ GCP_send (struct GCP_MessageQueueManager *mqm, | |||
628 | cp); | 651 | cp); |
629 | mqm->env = env; | 652 | mqm->env = env; |
630 | cp->mqm_ready_counter++; | 653 | cp->mqm_ready_counter++; |
654 | if (mqm != cp->mqm_ready_ptr) | ||
655 | cp->mqm_ready_ptr = cp->mqm_head; | ||
656 | if (1 == cp->mqm_ready_counter) | ||
657 | cp->mqm_ready_ptr = mqm; | ||
631 | if (0 != GNUNET_MQ_get_length (cp->core_mq)) | 658 | if (0 != GNUNET_MQ_get_length (cp->core_mq)) |
632 | return; | 659 | return; |
633 | mqm_execute (mqm); | 660 | send_next_ready (cp); |
634 | } | 661 | } |
635 | 662 | ||
636 | 663 | ||
@@ -1285,6 +1312,8 @@ GCP_request_mq_cancel (struct GCP_MessageQueueManager *mqm, | |||
1285 | else | 1312 | else |
1286 | GNUNET_MQ_discard (last_env); | 1313 | GNUNET_MQ_discard (last_env); |
1287 | } | 1314 | } |
1315 | if (cp->mqm_ready_ptr == mqm) | ||
1316 | cp->mqm_ready_ptr = mqm->next; | ||
1288 | GNUNET_CONTAINER_DLL_remove (cp->mqm_head, | 1317 | GNUNET_CONTAINER_DLL_remove (cp->mqm_head, |
1289 | cp->mqm_tail, | 1318 | cp->mqm_tail, |
1290 | mqm); | 1319 | mqm); |