123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776 |
- /*
- This file is part of GNUnet.
- Copyright (C) 2011-2015 GNUnet e.V.
- GNUnet is free software: you can redistribute it and/or modify it
- under the terms of the GNU Affero General Public License as published
- by the Free Software Foundation, either version 3 of the License,
- or (at your option) any later version.
- GNUnet is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- Affero General Public License for more details.
- You should have received a copy of the GNU Affero General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
- SPDX-License-Identifier: AGPL3.0-or-later
- */
- /**
- * @file ats/gnunet-service-ats_preferences.c
- * @brief manage preferences expressed by clients
- * @author Matthias Wachs
- * @author Christian Grothoff
- */
- #include "platform.h"
- #include "gnunet-service-ats.h"
- #include "gnunet-service-ats_addresses.h"
- #include "gnunet-service-ats_performance.h"
- #include "gnunet-service-ats_plugins.h"
- #include "gnunet-service-ats_preferences.h"
- #include "gnunet-service-ats_reservations.h"
- #include "ats.h"
- #define LOG(kind, ...) GNUNET_log_from (kind, "ats-preferences", __VA_ARGS__)
- /**
- * How frequently do we age preference values?
- */
- #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply ( \
- GNUNET_TIME_UNIT_SECONDS, 10)
- /**
- * By which factor do we age preferences expressed during
- * each #PREF_AGING_INTERVAL?
- */
- #define PREF_AGING_FACTOR 0.95
- /**
- * What is the lowest threshold up to which prefernce values
- * are aged, and below which we consider them zero and thus
- * no longer subject to aging?
- */
- #define PREF_EPSILON 0.01
- /**
- * Relative preferences for a peer.
- */
- struct PeerRelative
- {
- /**
- * Array of relative preference values, to be indexed by
- * an `enum GNUNET_ATS_PreferenceKind`.
- */
- double f_rel[GNUNET_ATS_PREFERENCE_END];
- /**
- * Number of clients that are expressing a preference for
- * this peer. When this counter reaches zero, this entry
- * is freed.
- */
- unsigned int num_clients;
- };
- /**
- * Default values, returned as our preferences if we do not
- * have any preferences expressed for a peer.
- */
- static struct PeerRelative defvalues;
- /**
- * Preference information per peer and client.
- */
- struct PreferencePeer
- {
- /**
- * Next in DLL of preference entries for the same client.
- */
- struct PreferencePeer *next;
- /**
- * Previous in DLL of preference entries for the same client.
- */
- struct PreferencePeer *prev;
- /**
- * Absolute preference values for all preference types
- * as expressed by this client for this peer.
- */
- double f_abs[GNUNET_ATS_PREFERENCE_END];
- /**
- * Relative preference values for all preference types,
- * normalized in [0..1] based on how the respective
- * client scored other peers.
- */
- double f_rel[GNUNET_ATS_PREFERENCE_END];
- };
- /**
- * Preference client, as in a client that expressed preferences
- * for peers. This is the information we keep track of for each
- * such client.
- */
- struct PreferenceClient
- {
- /**
- * Next in client list
- */
- struct PreferenceClient *next;
- /**
- * Previous in client peer list
- */
- struct PreferenceClient *prev;
- /**
- * Client handle
- */
- struct GNUNET_SERVICE_Client *client;
- /**
- * Mapping peer identities to `struct PreferencePeer` entry
- * for the respective peer.
- */
- struct GNUNET_CONTAINER_MultiPeerMap *peer2pref;
- /**
- * Array of sums of absolute preferences for all
- * peers as expressed by this client.
- */
- double f_abs_sum[GNUNET_ATS_PREFERENCE_END];
- };
- /**
- * Hashmap to store peer information for preference normalization.
- * Maps the identity of a peer to a `struct PeerRelative` containing
- * the current relative preference values for that peer.
- */
- static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
- /**
- * Clients in DLL: head
- */
- static struct PreferenceClient *pc_head;
- /**
- * Clients in DLL: tail
- */
- static struct PreferenceClient *pc_tail;
- /**
- * Handle for task we run periodically to age preferences over time.
- */
- static struct GNUNET_SCHEDULER_Task *aging_task;
- /**
- * Closure for #sum_relative_preferences().
- */
- struct SumContext
- {
- /**
- * Where to accumulate the result.
- */
- double f_rel_total;
- /**
- * Which kind of preference value are we adding up?
- */
- enum GNUNET_ATS_PreferenceKind kind;
- };
- /**
- * Add the relative preference for the kind given to the
- * closure.
- *
- * @param cls the `struct SumContext` with the kind and place
- * to store the result
- * @param peer ignored
- * @param value the `struct PreferencePeer` for getting the rel pref.
- * @return #GNUNET_OK
- */
- static int
- sum_relative_preferences (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- void *value)
- {
- struct SumContext *sum_ctx = cls;
- struct PreferencePeer *p_cur = value;
- sum_ctx->f_rel_total += p_cur->f_rel[sum_ctx->kind];
- return GNUNET_OK;
- }
- /**
- * Update the total releative preference for a peer by summing
- * up the relative preferences all clients have for this peer.
- *
- * @param id peer id of the peer for which we should do the update
- * @param kind the kind of preference value to update
- * @return the new relative preference
- */
- static void
- update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
- enum GNUNET_ATS_PreferenceKind kind)
- {
- struct PreferenceClient *c_cur;
- struct SumContext sum_ctx;
- struct PeerRelative *rp;
- sum_ctx.f_rel_total = 0.0;
- sum_ctx.kind = kind;
- for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
- GNUNET_CONTAINER_multipeermap_get_multiple (c_cur->peer2pref,
- id,
- &sum_relative_preferences,
- &sum_ctx);
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Total relative preference for peer `%s' for `%s' is %.3f\n",
- GNUNET_i2s (id),
- GNUNET_ATS_print_preference_type (kind),
- sum_ctx.f_rel_total);
- rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
- id);
- GNUNET_assert (NULL != rp);
- if (rp->f_rel[kind] != sum_ctx.f_rel_total)
- {
- rp->f_rel[kind] = sum_ctx.f_rel_total;
- GAS_plugin_notify_preference_changed (id,
- kind,
- rp->f_rel[kind]);
- }
- }
- /**
- * Free a peer's `struct PeerRelative`.
- *
- * @param cls unused
- * @param key the key
- * @param value the `struct PeerRelative` to free.
- * @return #GNUNET_OK to continue
- */
- static int
- free_peer (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct PeerRelative *rp = value;
- GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multipeermap_remove (preference_peers,
- key,
- value));
- GNUNET_free (rp);
- return GNUNET_OK;
- }
- /**
- * Free `struct PreferencePeer` entry in map.
- *
- * @param cls the `struct PreferenceClient` with the map
- * @param key the peer the entry is for
- * @param value the `struct PreferencePeer` entry to free
- * @return #GNUNET_OK (continue to iterate)
- */
- static int
- free_preference (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct PreferenceClient *pc = cls;
- struct PreferencePeer *p = value;
- struct PeerRelative *pr;
- GNUNET_assert (GNUNET_OK ==
- GNUNET_CONTAINER_multipeermap_remove (pc->peer2pref,
- key,
- p));
- GNUNET_free (p);
- pr = GNUNET_CONTAINER_multipeermap_get (preference_peers,
- key);
- GNUNET_assert (NULL != pr);
- GNUNET_assert (pr->num_clients > 0);
- pr->num_clients--;
- if (0 == pr->num_clients)
- {
- free_peer (NULL,
- key,
- pr);
- }
- return GNUNET_OK;
- }
- /**
- * Closure for #age_values().
- */
- struct AgeContext
- {
- /**
- * Counter of values remaining to update, incremented for each value
- * changed (to a new non-zero value).
- */
- unsigned int values_to_update;
- /**
- * Client we are currently aging values for.
- */
- struct PreferenceClient *cur_client;
- };
- /**
- * Age preference values of the given peer.
- *
- * @param cls a `
- * @param peer peer being aged
- * @param value the `struct PreferencePeer` for the peer
- * @return #GNUNET_OK (continue to iterate)
- */
- static int
- age_values (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- void *value)
- {
- struct AgeContext *ac = cls;
- struct PreferencePeer *p = value;
- unsigned int i;
- int dead;
- dead = GNUNET_YES;
- for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
- {
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "Aging preference for peer `%s'\n",
- GNUNET_i2s (peer));
- if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
- p->f_abs[i] *= PREF_AGING_FACTOR;
- if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
- {
- p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
- p->f_rel[i] = DEFAULT_REL_PREFERENCE;
- update_relative_values_for_peer (peer,
- i);
- }
- else
- {
- ac->values_to_update++;
- dead = GNUNET_NO;
- }
- }
- if (GNUNET_YES == dead)
- {
- /* all preferences are zero, remove this entry */
- free_preference (ac->cur_client,
- peer,
- p);
- }
- return GNUNET_OK;
- }
- /**
- * Reduce absolute preferences since they got old.
- *
- * @param cls unused
- */
- static void
- preference_aging (void *cls)
- {
- struct AgeContext ac;
- aging_task = NULL;
- GAS_plugin_solver_lock ();
- ac.values_to_update = 0;
- for (ac.cur_client = pc_head; NULL != ac.cur_client; ac.cur_client =
- ac.cur_client->next)
- GNUNET_CONTAINER_multipeermap_iterate (ac.cur_client->peer2pref,
- &age_values,
- &ac);
- GAS_plugin_solver_unlock ();
- if (ac.values_to_update > 0)
- {
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "Rescheduling aging task due to %u elements remaining to age\n",
- ac.values_to_update);
- if (NULL == aging_task)
- aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
- &preference_aging,
- NULL);
- }
- else
- {
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "No values to age left, not rescheduling aging task\n");
- }
- }
- /**
- * Closure for #update_rel_sum() and #update_abs_sum().
- */
- struct UpdateContext
- {
- /**
- * Preference client with the sum of all absolute scores.
- */
- struct PreferenceClient *pc;
- /**
- * Which kind are we updating?
- */
- enum GNUNET_ATS_PreferenceKind kind;
- };
- /**
- * Compute updated absolute score for the client based on the
- * current absolute scores for each peer.
- *
- * @param cls a `struct UpdateContext`
- * @param peer peer being updated
- * @param value the `struct PreferencePeer` for the peer
- * @return #GNUNET_OK (continue to iterate)
- */
- static int
- update_abs_sum (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- void *value)
- {
- struct UpdateContext *uc = cls;
- struct PreferencePeer *p_cur = value;
- uc->pc->f_abs_sum[uc->kind] += p_cur->f_abs[uc->kind];
- return GNUNET_OK;
- }
- /**
- * Compute updated relative score for each peer based on the
- * current absolute score given by this client.
- *
- * @param cls a `struct UpdateContext`
- * @param peer peer being updated
- * @param value the `struct PreferencePeer` for the peer (updated)
- * @return #GNUNET_OK (continue to iterate)
- */
- static int
- update_rel_sum (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- void *value)
- {
- struct UpdateContext *uc = cls;
- struct PreferencePeer *p_cur = value;
- p_cur->f_rel[uc->kind] = p_cur->f_abs[uc->kind] / uc->pc->f_abs_sum[uc->kind];
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Client has relative preference for %s for peer `%s' of %.3f\n",
- GNUNET_ATS_print_preference_type (uc->kind),
- GNUNET_i2s (peer),
- p_cur->f_rel[uc->kind]);
- return GNUNET_OK;
- }
- /**
- * Recalculate preference for a specific ATS property
- *
- * @param c the preference client
- * @param kind the preference kind
- * @return the result
- */
- static void
- recalculate_relative_preferences (struct PreferenceClient *c,
- enum GNUNET_ATS_PreferenceKind kind)
- {
- struct UpdateContext uc;
- /* For this client: sum of absolute preference values for this preference */
- uc.kind = kind;
- uc.pc = c;
- c->f_abs_sum[kind] = 0.0;
- /* For all peers: calculate sum of absolute preferences */
- GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
- &update_abs_sum,
- &uc);
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Client has sum of total preferences for %s of %.3f\n",
- GNUNET_ATS_print_preference_type (kind),
- c->f_abs_sum[kind]);
- /* For all peers: calculate relative preference */
- GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
- &update_rel_sum,
- &uc);
- }
- /**
- * The relative preferences of one of the clients have
- * changed, update the global preferences for the given
- * peer and notify the plugin.
- *
- * @param cls the kind of preference to calculate the
- * new global relative preference values for
- * @param key the peer to update relative preference values for
- * @param value a `struct PeerRelative`, unused
- */
- static int
- update_iterator (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- enum GNUNET_ATS_PreferenceKind *kind = cls;
- update_relative_values_for_peer (key,
- *kind);
- return GNUNET_OK;
- }
- /**
- * Update the absolute preference and calculate the
- * new relative preference value.
- *
- * @param client the client with this preference
- * @param peer the peer to change the preference for
- * @param kind the kind to change the preference
- * @param score_abs the normalized score
- */
- static void
- update_preference (struct GNUNET_SERVICE_Client *client,
- const struct GNUNET_PeerIdentity *peer,
- enum GNUNET_ATS_PreferenceKind kind,
- float score_abs)
- {
- struct PreferenceClient *c_cur;
- struct PreferencePeer *p_cur;
- struct PeerRelative *r_cur;
- unsigned int i;
- if (kind >= GNUNET_ATS_PREFERENCE_END)
- {
- GNUNET_break (0);
- return;
- }
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Client changes preference for peer `%s' for `%s' to %.2f\n",
- GNUNET_i2s (peer),
- GNUNET_ATS_print_preference_type (kind),
- score_abs);
- /* Find preference client */
- for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
- if (client == c_cur->client)
- break;
- /* Not found: create new preference client */
- if (NULL == c_cur)
- {
- c_cur = GNUNET_new (struct PreferenceClient);
- c_cur->client = client;
- c_cur->peer2pref = GNUNET_CONTAINER_multipeermap_create (16,
- GNUNET_NO);
- for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
- c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
- GNUNET_CONTAINER_DLL_insert (pc_head,
- pc_tail,
- c_cur);
- }
- /* check global peer entry exists */
- if (NULL ==
- (r_cur = GNUNET_CONTAINER_multipeermap_get (preference_peers,
- peer)))
- {
- /* Create struct for peer */
- r_cur = GNUNET_new (struct PeerRelative);
- for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
- r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
- GNUNET_assert (GNUNET_OK ==
- GNUNET_CONTAINER_multipeermap_put (preference_peers,
- peer,
- r_cur,
- GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
- }
- /* Find entry for peer */
- p_cur = GNUNET_CONTAINER_multipeermap_get (c_cur->peer2pref,
- peer);
- if (NULL == p_cur)
- {
- /* Not found: create new peer entry */
- p_cur = GNUNET_new (struct PreferencePeer);
- for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
- {
- /* Default value per peer absolute preference for a preference*/
- p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
- /* Default value per peer relative preference for a quality */
- p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
- }
- GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multipeermap_put (c_cur->peer2pref,
- peer,
- p_cur,
- GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
- r_cur->num_clients++;
- }
- p_cur->f_abs[kind] += score_abs;
- recalculate_relative_preferences (c_cur, kind);
- GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
- &update_iterator,
- &kind);
- if (NULL == aging_task)
- aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
- &preference_aging,
- NULL);
- }
- /**
- * Handle 'preference change' messages from clients.
- *
- * @param client the client that sent the request
- * @param msg the request message
- */
- void
- GAS_handle_preference_change (struct GNUNET_SERVICE_Client *client,
- const struct ChangePreferenceMessage *msg)
- {
- const struct PreferenceInformation *pi;
- uint32_t nump;
- nump = ntohl (msg->num_preferences);
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "Received PREFERENCE_CHANGE message for peer `%s'\n",
- GNUNET_i2s (&msg->peer));
- GNUNET_STATISTICS_update (GSA_stats,
- "# preference change requests processed",
- 1,
- GNUNET_NO);
- pi = (const struct PreferenceInformation *) &msg[1];
- GAS_plugin_solver_lock ();
- for (uint32_t i = 0; i < nump; i++)
- update_preference (client,
- &msg->peer,
- (enum GNUNET_ATS_PreferenceKind) ntohl (
- pi[i].preference_kind),
- pi[i].preference_value);
- GAS_plugin_solver_unlock ();
- }
- /**
- * Initialize preferences subsystem.
- */
- void
- GAS_preference_init ()
- {
- unsigned int i;
- preference_peers = GNUNET_CONTAINER_multipeermap_create (16,
- GNUNET_NO);
- for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
- defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
- }
- /**
- * Shutdown preferences subsystem.
- */
- void
- GAS_preference_done ()
- {
- struct PreferenceClient *pc;
- struct PreferenceClient *next_pc;
- if (NULL != aging_task)
- {
- GNUNET_SCHEDULER_cancel (aging_task);
- aging_task = NULL;
- }
- next_pc = pc_head;
- while (NULL != (pc = next_pc))
- {
- next_pc = pc->next;
- GNUNET_CONTAINER_DLL_remove (pc_head,
- pc_tail,
- pc);
- GNUNET_CONTAINER_multipeermap_iterate (pc->peer2pref,
- &free_preference,
- pc);
- GNUNET_CONTAINER_multipeermap_destroy (pc->peer2pref);
- GNUNET_free (pc);
- }
- GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
- &free_peer,
- NULL);
- GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
- }
- /**
- * Get the normalized preference values for a specific peer or
- * the default values if
- *
- * @param cls ignored
- * @param id the peer
- * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
- * default preferences if peer does not exist
- */
- const double *
- GAS_preference_get_by_peer (void *cls,
- const struct GNUNET_PeerIdentity *id)
- {
- struct PeerRelative *rp;
- if (NULL ==
- (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
- id)))
- {
- return defvalues.f_rel;
- }
- return rp->f_rel;
- }
- /**
- * A performance client disconnected
- *
- * @param client the client
- */
- void
- GAS_preference_client_disconnect (struct GNUNET_SERVICE_Client *client)
- {
- struct PreferenceClient *c_cur;
- for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
- if (client == c_cur->client)
- break;
- if (NULL == c_cur)
- return;
- GNUNET_CONTAINER_DLL_remove (pc_head,
- pc_tail,
- c_cur);
- GNUNET_CONTAINER_multipeermap_iterate (c_cur->peer2pref,
- &free_preference,
- c_cur);
- GNUNET_CONTAINER_multipeermap_destroy (c_cur->peer2pref);
- GNUNET_free (c_cur);
- }
- /* end of gnunet-service-ats_preferences.c */
|