diff options
author | Christian Grothoff <christian@grothoff.org> | 2018-04-13 11:30:48 +0200 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2018-04-13 11:32:32 +0200 |
commit | 66a629d3bee4652268ffd0e4b15b9cc490d3974f (patch) | |
tree | c17517e084c6be1516449ae506e8a964d11b3165 /src | |
parent | 78b04addaf643f8084df2f649f26dde01a1b5ddd (diff) | |
download | gnunet-66a629d3bee4652268ffd0e4b15b9cc490d3974f.tar.gz gnunet-66a629d3bee4652268ffd0e4b15b9cc490d3974f.zip |
use heap instead of DLL
Diffstat (limited to 'src')
-rw-r--r-- | src/namestore/gnunet-zoneimport.c | 139 |
1 files changed, 67 insertions, 72 deletions
diff --git a/src/namestore/gnunet-zoneimport.c b/src/namestore/gnunet-zoneimport.c index 9041431d1..bac3d2603 100644 --- a/src/namestore/gnunet-zoneimport.c +++ b/src/namestore/gnunet-zoneimport.c | |||
@@ -40,7 +40,7 @@ struct Record | |||
40 | * Kept in a DLL. | 40 | * Kept in a DLL. |
41 | */ | 41 | */ |
42 | struct Record *next; | 42 | struct Record *next; |
43 | 43 | ||
44 | /** | 44 | /** |
45 | * Kept in a DLL. | 45 | * Kept in a DLL. |
46 | */ | 46 | */ |
@@ -50,7 +50,7 @@ struct Record | |||
50 | * GNS record. | 50 | * GNS record. |
51 | */ | 51 | */ |
52 | struct GNUNET_GNSRECORD_Data grd; | 52 | struct GNUNET_GNSRECORD_Data grd; |
53 | 53 | ||
54 | }; | 54 | }; |
55 | 55 | ||
56 | 56 | ||
@@ -60,27 +60,22 @@ struct Record | |||
60 | struct Request | 60 | struct Request |
61 | { | 61 | { |
62 | /** | 62 | /** |
63 | * Requests are kept in a DLL. | 63 | * Requests are kept in a heap. |
64 | */ | ||
65 | struct Request *next; | ||
66 | |||
67 | /** | ||
68 | * Requests are kept in a DLL. | ||
69 | */ | 64 | */ |
70 | struct Request *prev; | 65 | struct GNUNET_CONTAINER_HeapNode *hn; |
71 | 66 | ||
72 | /** | 67 | /** |
73 | * Head of records that should be published in GNS for | 68 | * Head of records that should be published in GNS for |
74 | * this hostname. | 69 | * this hostname. |
75 | */ | 70 | */ |
76 | struct Record *rec_head; | 71 | struct Record *rec_head; |
77 | 72 | ||
78 | /** | 73 | /** |
79 | * Tail of records that should be published in GNS for | 74 | * Tail of records that should be published in GNS for |
80 | * this hostname. | 75 | * this hostname. |
81 | */ | 76 | */ |
82 | struct Record *rec_tail; | 77 | struct Record *rec_tail; |
83 | 78 | ||
84 | /** | 79 | /** |
85 | * Socket used to make the request, NULL if not active. | 80 | * Socket used to make the request, NULL if not active. |
86 | */ | 81 | */ |
@@ -106,19 +101,19 @@ struct Request | |||
106 | * if not active. | 101 | * if not active. |
107 | */ | 102 | */ |
108 | struct GNUNET_DNSPARSER_Packet *p; | 103 | struct GNUNET_DNSPARSER_Packet *p; |
109 | 104 | ||
110 | /** | 105 | /** |
111 | * At what time does the (earliest) of the returned records | 106 | * At what time does the (earliest) of the returned records |
112 | * for this name expire? At this point, we need to re-fetch | 107 | * for this name expire? At this point, we need to re-fetch |
113 | * the record. | 108 | * the record. |
114 | */ | 109 | */ |
115 | struct GNUNET_TIME_Absolute expires; | 110 | struct GNUNET_TIME_Absolute expires; |
116 | 111 | ||
117 | /** | 112 | /** |
118 | * Number of bytes in @e raw. | 113 | * Number of bytes in @e raw. |
119 | */ | 114 | */ |
120 | size_t raw_len; | 115 | size_t raw_len; |
121 | 116 | ||
122 | /** | 117 | /** |
123 | * When did we last issue this request? | 118 | * When did we last issue this request? |
124 | */ | 119 | */ |
@@ -139,7 +134,7 @@ struct Request | |||
139 | 134 | ||
140 | /** | 135 | /** |
141 | * Handle to the identity service. | 136 | * Handle to the identity service. |
142 | */ | 137 | */ |
143 | static struct GNUNET_IDENTITY_Handle *id; | 138 | static struct GNUNET_IDENTITY_Handle *id; |
144 | 139 | ||
145 | /** | 140 | /** |
@@ -178,16 +173,10 @@ static unsigned int failures; | |||
178 | static unsigned int records; | 173 | static unsigned int records; |
179 | 174 | ||
180 | /** | 175 | /** |
181 | * Head of DLL of all requests to perform, sorted by | 176 | * Heap of all requests to perform, sorted by |
182 | * the time we should next do the request (i.e. by expires). | ||
183 | */ | ||
184 | static struct Request *req_head; | ||
185 | |||
186 | /** | ||
187 | * Tail of DLL of all requests to perform, sorted by | ||
188 | * the time we should next do the request (i.e. by expires). | 177 | * the time we should next do the request (i.e. by expires). |
189 | */ | 178 | */ |
190 | static struct Request *req_tail; | 179 | static struct GNUNET_CONTAINER_Heap *req_heap; |
191 | 180 | ||
192 | /** | 181 | /** |
193 | * Main task. | 182 | * Main task. |
@@ -211,7 +200,7 @@ static struct GNUNET_CRYPTO_EcdsaPrivateKey zone; | |||
211 | 200 | ||
212 | /** | 201 | /** |
213 | * Which zone should records be imported into? | 202 | * Which zone should records be imported into? |
214 | */ | 203 | */ |
215 | static char *zone_name; | 204 | static char *zone_name; |
216 | 205 | ||
217 | /** | 206 | /** |
@@ -264,7 +253,7 @@ for_all_records (const struct GNUNET_DNSPARSER_Packet *p, | |||
264 | for (unsigned int i=0;i<p->num_answers;i++) | 253 | for (unsigned int i=0;i<p->num_answers;i++) |
265 | { | 254 | { |
266 | struct GNUNET_DNSPARSER_Record *rs = &p->answers[i]; | 255 | struct GNUNET_DNSPARSER_Record *rs = &p->answers[i]; |
267 | 256 | ||
268 | rp (rp_cls, | 257 | rp (rp_cls, |
269 | rs); | 258 | rs); |
270 | } | 259 | } |
@@ -288,28 +277,14 @@ for_all_records (const struct GNUNET_DNSPARSER_Packet *p, | |||
288 | /** | 277 | /** |
289 | * Insert @a req into DLL sorted by next fetch time. | 278 | * Insert @a req into DLL sorted by next fetch time. |
290 | * | 279 | * |
291 | * @param req request to insert into #req_head / #req_tail DLL | 280 | * @param req request to insert into #req_heap |
292 | */ | 281 | */ |
293 | static void | 282 | static void |
294 | insert_sorted (struct Request *req) | 283 | insert_sorted (struct Request *req) |
295 | { | 284 | { |
296 | struct Request *prev; | 285 | req->hn = GNUNET_CONTAINER_heap_insert (req_heap, |
297 | 286 | req, | |
298 | prev = NULL; | 287 | req->expires.abs_value_us); |
299 | /* NOTE: this linear-time loop may actually be our | ||
300 | main burner of CPU time for large zones, to be | ||
301 | revisited if CPU utilization turns out to be an | ||
302 | issue! */ | ||
303 | for (struct Request *pos = req_head; | ||
304 | ( (NULL != pos) && | ||
305 | (NULL != pos->next) && | ||
306 | (pos->expires.abs_value_us <= req->expires.abs_value_us) ); | ||
307 | pos = pos->next) | ||
308 | prev = pos; | ||
309 | GNUNET_CONTAINER_DLL_insert_after (req_head, | ||
310 | req_tail, | ||
311 | prev, | ||
312 | req); | ||
313 | } | 288 | } |
314 | 289 | ||
315 | 290 | ||
@@ -482,7 +457,7 @@ check_for_glue (void *cls, | |||
482 | break; | 457 | break; |
483 | default: | 458 | default: |
484 | /* useless, do nothing */ | 459 | /* useless, do nothing */ |
485 | break; | 460 | break; |
486 | } | 461 | } |
487 | } | 462 | } |
488 | 463 | ||
@@ -730,9 +705,8 @@ process_result (void *cls, | |||
730 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, | 705 | GNUNET_log (GNUNET_ERROR_TYPE_ERROR, |
731 | "Stub gave up on DNS reply for `%s'\n", | 706 | "Stub gave up on DNS reply for `%s'\n", |
732 | req->hostname); | 707 | req->hostname); |
733 | GNUNET_CONTAINER_DLL_remove (req_head, | 708 | GNUNET_assert (req == GNUNET_CONTAINER_heap_remove_node (req->hn)); |
734 | req_tail, | 709 | req->hn = NULL; |
735 | req); | ||
736 | if (req->issue_num > MAX_RETRIES) | 710 | if (req->issue_num > MAX_RETRIES) |
737 | { | 711 | { |
738 | failures++; | 712 | failures++; |
@@ -741,10 +715,8 @@ process_result (void *cls, | |||
741 | GNUNET_free (req); | 715 | GNUNET_free (req); |
742 | return; | 716 | return; |
743 | } | 717 | } |
744 | GNUNET_CONTAINER_DLL_insert_tail (req_head, | ||
745 | req_tail, | ||
746 | req); | ||
747 | req->rs = NULL; | 718 | req->rs = NULL; |
719 | insert_sorted (req); | ||
748 | return; | 720 | return; |
749 | } | 721 | } |
750 | if (req->id != dns->id) | 722 | if (req->id != dns->id) |
@@ -752,9 +724,8 @@ process_result (void *cls, | |||
752 | pending--; | 724 | pending--; |
753 | GNUNET_DNSSTUB_resolve_cancel (req->rs); | 725 | GNUNET_DNSSTUB_resolve_cancel (req->rs); |
754 | req->rs = NULL; | 726 | req->rs = NULL; |
755 | GNUNET_CONTAINER_DLL_remove (req_head, | 727 | GNUNET_assert (req == GNUNET_CONTAINER_heap_remove_node (req->hn)); |
756 | req_tail, | 728 | req->hn = NULL; |
757 | req); | ||
758 | p = GNUNET_DNSPARSER_parse ((const char *) dns, | 729 | p = GNUNET_DNSPARSER_parse ((const char *) dns, |
759 | dns_len); | 730 | dns_len); |
760 | if (NULL == p) | 731 | if (NULL == p) |
@@ -816,7 +787,7 @@ process_result (void *cls, | |||
816 | /* convert linked list into array */ | 787 | /* convert linked list into array */ |
817 | for (rec = req->rec_head; NULL != rec; rec =rec->next) | 788 | for (rec = req->rec_head; NULL != rec; rec =rec->next) |
818 | rd[off++] = rec->grd; | 789 | rd[off++] = rec->grd; |
819 | if (GNUNET_OK != | 790 | if (GNUNET_OK != |
820 | ns->store_records (ns->cls, | 791 | ns->store_records (ns->cls, |
821 | &zone, | 792 | &zone, |
822 | req->label, | 793 | req->label, |
@@ -888,26 +859,32 @@ submit_req (struct Request *req) | |||
888 | static void | 859 | static void |
889 | process_queue(void *cls) | 860 | process_queue(void *cls) |
890 | { | 861 | { |
862 | struct Request *req; | ||
863 | |||
891 | (void) cls; | 864 | (void) cls; |
892 | t = NULL; | 865 | t = NULL; |
893 | for (struct Request *req = req_head; | 866 | do |
894 | NULL != req; | ||
895 | req = req->next) | ||
896 | { | 867 | { |
897 | if (GNUNET_TIME_absolute_get_remaining (req->expires).rel_value_us > 0) | 868 | req = GNUNET_CONTAINER_heap_peek (req_heap); |
869 | if (NULL == req) | ||
898 | break; | 870 | break; |
899 | if (GNUNET_SYSERR == submit_req (req)) | 871 | if (GNUNET_TIME_absolute_get_remaining (req->expires).rel_value_us > 0) |
900 | break; | 872 | break; |
873 | GNUNET_assert (req == GNUNET_CONTAINER_heap_remove_root (req_heap)); | ||
874 | req->hn = NULL; | ||
901 | } | 875 | } |
902 | if (NULL != req_head) | 876 | while (GNUNET_SYSERR != submit_req (req)); |
877 | |||
878 | req = GNUNET_CONTAINER_heap_peek (req_heap); | ||
879 | if (NULL != req) | ||
903 | { | 880 | { |
904 | if (GNUNET_TIME_absolute_get_remaining (req_head->expires).rel_value_us > 0) | 881 | if (GNUNET_TIME_absolute_get_remaining (req->expires).rel_value_us > 0) |
905 | { | 882 | { |
906 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, | 883 | GNUNET_log (GNUNET_ERROR_TYPE_INFO, |
907 | "Waiting until %s for next record (`%s') to expire\n", | 884 | "Waiting until %s for next record (`%s') to expire\n", |
908 | GNUNET_STRINGS_absolute_time_to_string (req_head->expires), | 885 | GNUNET_STRINGS_absolute_time_to_string (req->expires), |
909 | req_head->hostname); | 886 | req->hostname); |
910 | t = GNUNET_SCHEDULER_add_at (req_head->expires, | 887 | t = GNUNET_SCHEDULER_add_at (req->expires, |
911 | &process_queue, | 888 | &process_queue, |
912 | NULL); | 889 | NULL); |
913 | } | 890 | } |
@@ -937,6 +914,8 @@ process_queue(void *cls) | |||
937 | static void | 914 | static void |
938 | do_shutdown (void *cls) | 915 | do_shutdown (void *cls) |
939 | { | 916 | { |
917 | struct Request *req; | ||
918 | |||
940 | (void) cls; | 919 | (void) cls; |
941 | if (NULL != id) | 920 | if (NULL != id) |
942 | { | 921 | { |
@@ -956,8 +935,23 @@ do_shutdown (void *cls) | |||
956 | GNUNET_free (db_lib_name); | 935 | GNUNET_free (db_lib_name); |
957 | db_lib_name = NULL; | 936 | db_lib_name = NULL; |
958 | } | 937 | } |
959 | GNUNET_DNSSTUB_stop (ctx); | 938 | if (NULL != ctx) |
960 | ctx = NULL; | 939 | { |
940 | GNUNET_DNSSTUB_stop (ctx); | ||
941 | ctx = NULL; | ||
942 | } | ||
943 | while (NULL != (req = GNUNET_CONTAINER_heap_remove_root (req_heap))) | ||
944 | { | ||
945 | req->hn = NULL; | ||
946 | GNUNET_free (req->hostname); | ||
947 | GNUNET_free (req->label); | ||
948 | GNUNET_free (req); | ||
949 | } | ||
950 | if (NULL != req_heap) | ||
951 | { | ||
952 | GNUNET_CONTAINER_heap_destroy (req_heap); | ||
953 | req_heap = NULL; | ||
954 | } | ||
961 | } | 955 | } |
962 | 956 | ||
963 | 957 | ||
@@ -988,13 +982,13 @@ import_records (void *cls, | |||
988 | { | 982 | { |
989 | struct GNUNET_TIME_Absolute at; | 983 | struct GNUNET_TIME_Absolute at; |
990 | 984 | ||
991 | at.abs_value_us = rd->expiration_time; | 985 | at.abs_value_us = rd->expiration_time; |
992 | add_record (req, | 986 | add_record (req, |
993 | rd->record_type, | 987 | rd->record_type, |
994 | at, | 988 | at, |
995 | rd->data, | 989 | rd->data, |
996 | rd->data_size); | 990 | rd->data_size); |
997 | } | 991 | } |
998 | } | 992 | } |
999 | 993 | ||
1000 | 994 | ||
@@ -1024,7 +1018,7 @@ queue (const char *hostname) | |||
1024 | } | 1018 | } |
1025 | /* TODO: may later support importing zones that | 1019 | /* TODO: may later support importing zones that |
1026 | are not TLD, for this we mostly need to change | 1020 | are not TLD, for this we mostly need to change |
1027 | the logic here to remove the zone's suffix | 1021 | the logic here to remove the zone's suffix |
1028 | instead of just ".tld" */ | 1022 | instead of just ".tld" */ |
1029 | dot = strrchr (hostname, | 1023 | dot = strrchr (hostname, |
1030 | (unsigned char) '.'); | 1024 | (unsigned char) '.'); |
@@ -1094,7 +1088,7 @@ queue (const char *hostname) | |||
1094 | else | 1088 | else |
1095 | { | 1089 | { |
1096 | unsigned int rd_count = 0; | 1090 | unsigned int rd_count = 0; |
1097 | 1091 | ||
1098 | req->expires = GNUNET_TIME_UNIT_FOREVER_ABS; | 1092 | req->expires = GNUNET_TIME_UNIT_FOREVER_ABS; |
1099 | for (struct Record *rec = req->rec_head; | 1093 | for (struct Record *rec = req->rec_head; |
1100 | NULL != rec; | 1094 | NULL != rec; |
@@ -1235,6 +1229,7 @@ run (void *cls, | |||
1235 | (void) cls; | 1229 | (void) cls; |
1236 | (void) args; | 1230 | (void) args; |
1237 | (void) cfgfile; | 1231 | (void) cfgfile; |
1232 | req_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); | ||
1238 | ctx = GNUNET_DNSSTUB_start (dns_server); | 1233 | ctx = GNUNET_DNSSTUB_start (dns_server); |
1239 | if (NULL == ctx) | 1234 | if (NULL == ctx) |
1240 | { | 1235 | { |
@@ -1254,7 +1249,7 @@ run (void *cls, | |||
1254 | "libgnunet_plugin_namestore_%s", | 1249 | "libgnunet_plugin_namestore_%s", |
1255 | database); | 1250 | database); |
1256 | ns = GNUNET_PLUGIN_load (db_lib_name, | 1251 | ns = GNUNET_PLUGIN_load (db_lib_name, |
1257 | (void *) cfg); | 1252 | (void *) cfg); |
1258 | GNUNET_free (database); | 1253 | GNUNET_free (database); |
1259 | GNUNET_SCHEDULER_add_shutdown (&do_shutdown, | 1254 | GNUNET_SCHEDULER_add_shutdown (&do_shutdown, |
1260 | NULL); | 1255 | NULL); |
@@ -1284,7 +1279,7 @@ main (int argc, | |||
1284 | GNUNET_GETOPT_option_mandatory | 1279 | GNUNET_GETOPT_option_mandatory |
1285 | (GNUNET_GETOPT_option_string ('s', | 1280 | (GNUNET_GETOPT_option_string ('s', |
1286 | "server", | 1281 | "server", |
1287 | "IP", | 1282 | "IP", |
1288 | "which DNS server should be used", | 1283 | "which DNS server should be used", |
1289 | &dns_server)), | 1284 | &dns_server)), |
1290 | GNUNET_GETOPT_option_mandatory | 1285 | GNUNET_GETOPT_option_mandatory |