changes
[oweals/gnunet.git] / src / ats / gnunet-service-ats_addresses_simplistic.c
1 /*
2      This file is part of GNUnet.
3      (C) 2011 Christian Grothoff (and other contributing authors)
4
5      GNUnet is free software; you can redistribute it and/or modify
6      it under the terms of the GNU General Public License as published
7      by the Free Software Foundation; either version 3, or (at your
8      option) any later version.
9
10      GNUnet is distributed in the hope that it will be useful, but
11      WITHOUT ANY WARRANTY; without even the implied warranty of
12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13      General Public License for more details.
14
15      You should have received a copy of the GNU General Public License
16      along with GNUnet; see the file COPYING.  If not, write to the
17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18      Boston, MA 02111-1307, USA.
19 */
20
21 /**
22  * @file ats/gnunet-service-ats_addresses_simplistic.h
23  * @brief ats simplistic ressource assignment
24  * @author Matthias Wachs
25  * @author Christian Grothoff
26  */
27 #include "platform.h"
28 #include "gnunet_util_lib.h"
29 #include "gnunet-service-ats_addresses.h"
30 #include "gnunet_statistics_service.h"
31
32 #define LOG(kind,...) GNUNET_log_from (kind, "ats-simplistic",__VA_ARGS__)
33
34 /**
35  * ATS simplistic solver
36  *
37  * Assigns in and outbound bandwidth equally for all addresses in specific
38  * network type (WAN, LAN) based on configured in and outbound quota for this
39  * network.
40  *
41  * For each peer only a single is selected and marked as "active" in the address
42  * struct.
43  *
44  * E.g.:
45  *
46  * You have the networks WAN and LAN and quotas
47  * WAN_TOTAL_IN, WAN_TOTAL_OUT
48  * LAN_TOTAL_IN, LAN_TOTAL_OUT
49  *
50  * If you have x addresses in the network segment LAN, the quotas are
51  * QUOTA_PER_ADDRESS = LAN_TOTAL_OUT / x
52  *
53  * Quotas are automatically recalculated and reported back when addresses are
54  * - requested
55  *
56  */
57
58
59 /**
60  * A handle for the simplistic solver
61  */
62 struct GAS_SIMPLISTIC_Handle
63 {
64   unsigned int total_addresses;
65   unsigned int active_addresses;
66
67   struct Network *network_entries;
68
69   unsigned int networks;
70   GAS_bandwidth_changed_cb bw_changed;
71   void *bw_changed_cls;
72 };
73
74 struct Network
75 {
76   /**
77    * ATS network type
78    */
79   unsigned int type;
80
81   /**
82    * Network description
83    */
84   char *desc;
85
86   /**
87    * Total inbound quota
88    *
89    */
90   unsigned long long total_quota_in;
91
92   /**
93    * Total outbound quota
94    *
95    */
96   unsigned long long total_quota_out;
97
98   /**
99    * Number of active addresses for this network
100    */
101   unsigned int active_addresses;
102
103   /**
104    * Number of total addresses for this network
105    */
106   unsigned int total_addresses;
107
108   struct AddressWrapper *head;
109   struct AddressWrapper *tail;
110 };
111
112 struct AddressWrapper
113 {
114   struct AddressWrapper *next;
115   struct AddressWrapper *prev;
116
117   struct ATS_Address *addr;
118 };
119
120 /**
121  * Init the simplistic problem solving component
122  *
123  * Quotas:
124  * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
125  * out_quota[i] contains outbound quota for network type i
126  * in_quota[i] contains inbound quota for network type i
127  *
128  * Example
129  * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
130  * network[2]   == GNUNET_ATS_NET_LAN
131  * out_quota[2] == 65353
132  * in_quota[2]  == 65353
133  *
134  * @param cfg configuration handle
135  * @param stats the GNUNET_STATISTICS handle
136  * @param network array of GNUNET_ATS_NetworkType with length dest_length
137  * @param out_quota array of outbound quotas
138  * @param in_quota array of outbound quota
139  * @param dest_length array length for quota arrays
140  * @param bw_changed_cb callback for changed bandwidth amounts
141  * @param bw_changed_cb_cls cls for callback
142  * @return handle for the solver on success, NULL on fail
143  */
144 void *
145 GAS_simplistic_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
146                      const struct GNUNET_STATISTICS_Handle *stats,
147                      int *network,
148                      unsigned long long *out_quota,
149                      unsigned long long *in_quota,
150                      int dest_length,
151                      GAS_bandwidth_changed_cb bw_changed_cb,
152                      void *bw_changed_cb_cls)
153 {
154   int c;
155   struct GAS_SIMPLISTIC_Handle *s = GNUNET_malloc (sizeof (struct GAS_SIMPLISTIC_Handle));
156   struct Network * cur;
157   char * net_str[GNUNET_ATS_NetworkTypeCount] = {"UNSPECIFIED", "LOOPBACK", "LAN", "WAN", "WLAN"};
158
159   s->bw_changed = bw_changed_cb;
160   s->bw_changed_cls = bw_changed_cb_cls;
161   s->networks = dest_length;
162   s->network_entries = GNUNET_malloc (dest_length * sizeof (struct Network));
163   s->active_addresses = 0;
164   s->total_addresses = 0;
165
166   for (c = 0; c < dest_length; c++)
167   {
168       cur = &s->network_entries[c];
169       cur->total_addresses = 0;
170       cur->active_addresses = 0;
171       cur->type = network[c];
172       cur->total_quota_in = in_quota[c];
173       cur->total_quota_out = out_quota[c];
174       cur->desc = net_str[c];
175   }
176   return s;
177 }
178
179
180 /**
181  * Shutdown the simplistic problem solving component
182  *
183  * @param solver the respective handle to shutdown
184  */
185 void
186 GAS_simplistic_done (void *solver)
187 {
188   struct GAS_SIMPLISTIC_Handle *s = solver;
189   struct AddressWrapper *cur;
190   struct AddressWrapper *next;
191   int c;
192   GNUNET_assert (s != NULL);
193
194   for (c = 0; c < s->networks; c++)
195   {
196       if (s->network_entries[c].total_addresses > 0)
197       {
198         LOG (GNUNET_ERROR_TYPE_ERROR,
199                     "Had %u addresses for network `%s' not deleted during shutdown\n",
200                     s->network_entries[c].total_addresses,
201                     s->network_entries[c].desc);
202         GNUNET_break (0);
203       }
204
205       if (s->network_entries[c].active_addresses > 0)
206       {
207         LOG (GNUNET_ERROR_TYPE_ERROR,
208                     "Had %u active addresses for network `%s' not deleted during shutdown\n",
209                     s->network_entries[c].active_addresses,
210                     s->network_entries[c].desc);
211         GNUNET_break (0);
212       }
213
214       next = s->network_entries[c].head;
215       while (NULL != (cur = next))
216       {
217           next = cur->next;
218           GNUNET_CONTAINER_DLL_remove (s->network_entries[c].head,
219                                        s->network_entries[c].tail,
220                                        cur);
221           GNUNET_free (cur);
222
223       }
224   }
225   if (s->total_addresses > 0)
226   {
227     LOG (GNUNET_ERROR_TYPE_ERROR,
228                 "Had %u addresses not deleted during shutdown\n",
229                 s->total_addresses);
230     GNUNET_break (0);
231   }
232   if (s->active_addresses > 0)
233   {
234     LOG (GNUNET_ERROR_TYPE_ERROR,
235                 "Had %u active addresses not deleted during shutdown\n",
236                 s->active_addresses);
237     GNUNET_break (0);
238   }
239
240   GNUNET_free (s->network_entries);
241   GNUNET_free (s);
242 }
243
244 /**
245  * Update the quotas for a network type
246  *
247  * @param s the solver handle
248  * @param net the network type to update
249  * @param address_except address excluded from notifcation, since we suggest
250  * this address
251  */
252
253 static void
254 update_quota_per_network (struct GAS_SIMPLISTIC_Handle *s,
255                           struct Network *net,
256                           struct ATS_Address *address_except)
257 {
258   unsigned long long quota_in = 0;
259   unsigned long long quota_out = 0;
260   struct AddressWrapper *cur;
261
262   LOG (GNUNET_ERROR_TYPE_DEBUG,
263               "Recalculate quota for network type `%s' for %u addresses (in/out): %llu/%llu \n",
264               net->desc, net->active_addresses, quota_in, quota_out);
265
266   if (net->active_addresses == 0)
267     return; /* no addresses to update */
268
269   quota_in = net->total_quota_in / net->active_addresses;
270   quota_out = net->total_quota_out / net->active_addresses;
271
272   LOG (GNUNET_ERROR_TYPE_DEBUG,
273               "New per address quota for network type `%s' for %u addresses (in/out): %llu/%llu \n",
274               net->desc, net->active_addresses, quota_in, quota_out);
275
276   cur = net->head;
277   while (NULL != cur)
278   {
279       /* Compare to current bandwidth assigned */
280       if ((quota_in != ntohl(cur->addr->assigned_bw_in.value__)) ||
281           (quota_out != ntohl(cur->addr->assigned_bw_out.value__)))
282       {
283         cur->addr->assigned_bw_in.value__ = htonl (quota_in);
284         cur->addr->assigned_bw_out.value__ = htonl (quota_out);
285         /* Notify on change */
286         if ((GNUNET_YES == cur->addr->active) && (cur->addr != address_except))
287           s->bw_changed (s->bw_changed_cls, cur->addr);
288       }
289       cur = cur->next;
290   }
291 }
292
293
294 /**
295  * Add a single address to the solve
296  *
297  * @param solver the solver Handle
298  * @param addresses the address hashmap containing all addresses
299  * @param address the address to add
300  */
301 void
302 GAS_simplistic_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
303 {
304   struct GAS_SIMPLISTIC_Handle *s = solver;
305   struct Network *cur = NULL;
306   struct AddressWrapper *aw = NULL;
307   GNUNET_assert (NULL != s);
308   int c;
309   for (c = 0; c < s->networks; c++)
310   {
311       cur = &s->network_entries[c];
312       if (address->atsp_network_type == cur->type)
313           break;
314   }
315   if (NULL == cur)
316   {
317     GNUNET_break (0);
318     return;
319   }
320
321   aw = GNUNET_malloc (sizeof (struct AddressWrapper));
322   aw->addr = address;
323   GNUNET_CONTAINER_DLL_insert (cur->head, cur->tail, aw);
324   cur->total_addresses ++;
325   s->total_addresses ++;
326   aw->addr->solver_information = cur;
327
328   LOG (GNUNET_ERROR_TYPE_DEBUG,
329               "Adding new address for network type `%s' (now %u total)\n",
330               cur->desc,
331               cur->active_addresses);
332 }
333
334 /**
335  * Remove an address from the solver
336  *
337  * @param solver the solver handle
338  * @param addresses the address hashmap containing all addresses
339  * @param address the address to remove
340  * @param session_only delete only session not whole address
341  */
342 void
343 GAS_simplistic_address_delete (void *solver,
344     struct GNUNET_CONTAINER_MultiHashMap * addresses,
345     struct ATS_Address *address, int session_only)
346 {
347   struct GAS_SIMPLISTIC_Handle *s = solver;
348   struct Network *net;
349   struct AddressWrapper *aw;
350
351   /* Remove an adress completely, we have to:
352    * - Remove from specific network
353    * - Decrease number of total addresses
354    * - If active:
355    *   - decrease number of active addreses
356    *   - update quotas
357    */
358
359   net = (struct Network *) address->solver_information;
360
361   if (GNUNET_NO == session_only)
362   {
363     LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting %s address %p for peer `%s' from network `%s' (total: %u/ active: %u)\n",
364         (GNUNET_NO == address->active) ? "inactive" : "active",
365         address, GNUNET_i2s (&address->peer),
366         net->desc, net->total_addresses, net->active_addresses);
367
368     /* Remove address */
369     if (net->total_addresses < 1)
370       GNUNET_break (0);
371     else
372       net->total_addresses --;
373     if (s->total_addresses < 1)
374       GNUNET_break (0);
375     else
376       s->total_addresses --;
377
378     for (aw = net->head; NULL != aw; aw = aw->next)
379     {
380         if (aw->addr == address)
381           break;
382     }
383     if (NULL == aw )
384     {
385         GNUNET_break (0);
386         return;
387     }
388     GNUNET_CONTAINER_DLL_remove (net->head, net->tail, aw);
389     GNUNET_free (aw);
390   }
391   else
392   {
393       /* Remove session only: remove if active and update */
394       LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting %s session %p for peer `%s' from network `%s' (total: %u/ active: %u)\n",
395           (GNUNET_NO == address->active) ? "inactive" : "active",
396           address, GNUNET_i2s (&address->peer),
397           net->desc, net->total_addresses, net->active_addresses);
398   }
399
400   if (GNUNET_YES == address->active)
401   {
402       /* Address was active, remove from network and update quotas*/
403       address->active = GNUNET_NO;
404       if (net->active_addresses < 1)
405         GNUNET_break (0);
406       else
407         net->active_addresses --;
408       if (s->active_addresses < 1)
409         GNUNET_break (0);
410       else
411         s->active_addresses --;
412       update_quota_per_network (s, net, NULL);
413   }
414 }
415
416 /**
417  * Updates a single address in the solve
418  *
419  * @param solver the solver Handle
420  * @param addresses the address hashmap containing all addresses
421  * @param address the update address
422  * @param session the new session (if changed otherwise current)
423  * @param in_use the new address in use state (if changed otherwise current)
424  * @param atsi the latest ATS information
425  * @param atsi_count the atsi count
426  */
427 void
428 GAS_simplistic_address_update (void *solver,
429                               struct GNUNET_CONTAINER_MultiHashMap *addresses,
430                               struct ATS_Address *address,
431                               uint32_t session,
432                               int in_use,
433                               const struct GNUNET_ATS_Information *atsi,
434                               uint32_t atsi_count)
435 {
436   int i;
437   uint32_t value;
438   uint32_t type;
439   for (i = 0; i < atsi_count; i++)
440   {
441     type = ntohl (atsi[i].type);
442     value = ntohl (atsi[i].value);
443     switch (type)
444     {
445     case GNUNET_ATS_UTILIZATION_UP:
446       //if (address->atsp_utilization_out.value__ != atsi[i].value)
447
448       break;
449     case GNUNET_ATS_UTILIZATION_DOWN:
450       //if (address->atsp_utilization_in.value__ != atsi[i].value)
451
452       break;
453     case GNUNET_ATS_QUALITY_NET_DELAY:
454       //if (address->atsp_latency.rel_value != value)
455
456       break;
457     case GNUNET_ATS_QUALITY_NET_DISTANCE:
458       //if (address->atsp_distance != value)
459
460       break;
461     case GNUNET_ATS_COST_WAN:
462       //if (address->atsp_cost_wan != value)
463
464       break;
465     case GNUNET_ATS_COST_LAN:
466       //if (address->atsp_cost_lan != value)
467
468       break;
469     case GNUNET_ATS_COST_WLAN:
470       //if (address->atsp_cost_wlan != value)
471
472       break;
473     case GNUNET_ATS_NETWORK_TYPE:
474       if (address->atsp_network_type != value)
475       {
476
477         LOG (GNUNET_ERROR_TYPE_DEBUG, "Network changed from `%s' to `%s'\n",
478             GNUNET_ATS_print_network_type(address->atsp_network_type),
479             GNUNET_ATS_print_network_type(value));
480 #if 0
481         /* FIXME */
482         int active = address->active;
483         address->atsp_network_type = value;
484         /* Remove address from old network */
485         GAS_simplistic_address_delete (solver, addresses, address, GNUNET_NO);
486         /* Add to new network */
487         GAS_simplistic_address_add (solver, addresses, address);
488         address->active = active;
489         update_quota_per_network(solver, address->solver_information, NULL);
490 #endif
491       }
492       break;
493     case GNUNET_ATS_ARRAY_TERMINATOR:
494       break;
495     default:
496       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
497                   "Received unsupported ATS type %u\n", type);
498       GNUNET_break (0);
499       break;
500
501     }
502
503   }
504
505
506   if (address->session_id != session)
507   {
508       LOG (GNUNET_ERROR_TYPE_DEBUG,
509                   "Session changed from %u to %u\n", address->session_id, session);
510       address->session_id = session;
511   }
512   if (address->used != in_use)
513   {
514       LOG (GNUNET_ERROR_TYPE_DEBUG,
515                   "Usage changed from %u to %u\n", address->used, in_use);
516       address->used = in_use;
517   }
518
519 }
520
521
522
523 /**
524  * Find a "good" address to use for a peer.  If we already have an existing
525  * address, we stick to it.  Otherwise, we pick by lowest distance and then
526  * by lowest latency.
527  *
528  * @param cls the 'struct ATS_Address**' where we store the result
529  * @param key unused
530  * @param value another 'struct ATS_Address*' to consider using
531  * @return GNUNET_OK (continue to iterate)
532  */
533 static int
534 find_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
535 {
536   struct ATS_Address **previous_p = cls;
537   struct ATS_Address *current = (struct ATS_Address *) value;
538   struct ATS_Address *previous = *previous_p;
539   struct GNUNET_TIME_Absolute now;
540
541   now = GNUNET_TIME_absolute_get();
542
543   if (current->blocked_until.abs_value == GNUNET_TIME_absolute_max (now, current->blocked_until).abs_value)
544   {
545     /* This address is blocked for suggestion */
546     LOG (GNUNET_ERROR_TYPE_DEBUG,
547                 "Address %p blocked for suggestion for %llu ms \n",
548                 current,
549                 GNUNET_TIME_absolute_get_difference(now, current->blocked_until).rel_value);
550     return GNUNET_OK;
551   }
552
553   if (NULL != previous)
554   {
555     if ((0 == strcmp (previous->plugin, "tcp")) &&
556         (0 == strcmp (current->plugin, "tcp")))
557     {
558       if ((0 != previous->addr_len) &&
559           (0 == current->addr_len))
560       {
561         /* saved address was an outbound address, but we have an inbound address */
562         *previous_p = current;
563         return GNUNET_OK;
564       }
565       if (0 == previous->addr_len)
566       {
567         /* saved address was an inbound address, so do not overwrite */
568         return GNUNET_OK;
569       }
570     }
571   }
572
573   if (NULL == previous)
574   {
575     *previous_p = current;
576     return GNUNET_OK;
577   }
578   if ((ntohl (previous->assigned_bw_in.value__) == 0) &&
579       (ntohl (current->assigned_bw_in.value__) > 0))
580   {
581     /* stick to existing connection */
582     *previous_p = current;
583     return GNUNET_OK;
584   }
585   if (previous->atsp_distance > current->atsp_distance)
586   {
587     /* user shorter distance */
588     *previous_p = current;
589     return GNUNET_OK;
590   }
591   if (previous->atsp_latency.rel_value > current->atsp_latency.rel_value)
592   {
593     /* user lower latency */
594     *previous_p = current;
595     return GNUNET_OK;
596   }
597   /* don't care */
598   return GNUNET_OK;
599 }
600
601 static int
602 find_active_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
603 {
604   struct ATS_Address * dest = (struct ATS_Address *) (*(struct ATS_Address **)cls);
605   struct ATS_Address * aa = (struct ATS_Address *) value;
606
607   if (GNUNET_YES == aa->active)
608   {
609       if (dest != NULL)
610       {
611           /* should never happen */
612           LOG (GNUNET_ERROR_TYPE_ERROR, "Multiple active addresses for peer `%s'\n", GNUNET_i2s (&aa->peer));
613           GNUNET_break (0);
614           return GNUNET_NO;
615       }
616       dest = aa;
617   }
618   return GNUNET_OK;
619 }
620
621 static struct ATS_Address *
622 find_active_address (void *solver,
623                      struct GNUNET_CONTAINER_MultiHashMap * addresses,
624                      const struct GNUNET_PeerIdentity *peer)
625 {
626   struct ATS_Address * dest = NULL;
627
628   GNUNET_CONTAINER_multihashmap_get_multiple(addresses,
629        &peer->hashPubKey,
630        &find_active_address_it, &dest);
631   return dest;
632 }
633
634 /**
635  * Get the prefered address for a specific peer
636  *
637  * @param solver the solver handle
638  * @param addresses the address hashmap containing all addresses
639  * @param peer the identity of the peer
640  */
641 const struct ATS_Address *
642 GAS_simplistic_get_preferred_address (void *solver,
643                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
644                                const struct GNUNET_PeerIdentity *peer)
645 {
646   struct GAS_SIMPLISTIC_Handle *s = solver;
647   struct Network *net_prev;
648   struct Network *net_cur;
649   struct ATS_Address *cur;
650   struct ATS_Address *prev;
651
652   GNUNET_assert (s != NULL);
653   cur = NULL;
654   /* Get address with: stick to current address, lower distance, lower latency */
655   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey,
656                                               &find_address_it, &cur);
657   if (NULL == cur)
658   {
659     LOG (GNUNET_ERROR_TYPE_DEBUG, "Cannot suggest address for peer `%s'\n", GNUNET_i2s (peer));
660     return NULL;
661   }
662
663   LOG (GNUNET_ERROR_TYPE_DEBUG, "Suggesting %s address %p for peer `%s'\n",
664       (GNUNET_NO == cur->active) ? "inactive" : "active",
665       cur, GNUNET_i2s (peer));
666   net_cur = (struct Network *) cur->solver_information;
667   if (GNUNET_YES == cur->active)
668   {
669       /* This address was selected previously, so no need to update quotas */
670       return cur;
671   }
672
673   /* This address was not active, so we have to:
674    *
675    * - mark previous active address as not active
676    * - update quota for previous address network
677    * - update quota for this address network
678    */
679
680   prev = find_active_address (s, addresses, peer);
681   if (NULL != prev)
682   {
683       net_prev = (struct Network *) prev->solver_information;
684       prev->active = GNUNET_NO; /* No active any longer */
685       prev->assigned_bw_in = GNUNET_BANDWIDTH_value_init (0); /* no bw assigned */
686       prev->assigned_bw_out = GNUNET_BANDWIDTH_value_init (0); /* no bw assigned */
687       s->bw_changed (s->bw_changed_cls, prev); /* notify about bw change, REQUIRED? */
688       if (net_prev->active_addresses < 1)
689         GNUNET_break (0);
690       else
691         net_prev->active_addresses --;
692       if (s->active_addresses < 1)
693         GNUNET_break (0);
694       else
695         s->active_addresses --;
696       update_quota_per_network (s, net_prev, NULL);
697   }
698
699   cur->active = GNUNET_YES;
700   s->active_addresses ++;
701   net_cur->active_addresses ++;
702   update_quota_per_network (s, net_cur, cur);
703
704   return cur;
705 }
706
707
708 /**
709  * Changes the preferences for a peer in the problem
710  *
711  * @param solver the solver handle
712  * @param peer the peer to change the preference for
713  * @param kind the kind to change the preference
714  * @param score the score
715  */
716 void
717 GAS_simplistic_address_change_preference (void *solver,
718                                    const struct GNUNET_PeerIdentity *peer,
719                                    enum GNUNET_ATS_PreferenceKind kind,
720                                    float score)
721 {
722   /* FIXME : implement this */
723 }
724
725 /* end of gnunet-service-ats_addresses_simplistic.c */