/* This file is part of GNUnet. (C) 2011 Christian Grothoff (and other contributing authors) GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, 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 General Public License for more details. You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ /** * @file ats/gnunet-service-ats_normalization.c * @brief ats service address: management of ATS properties and preferences normalization * @author Matthias Wachs * @author Christian Grothoff */ #include "platform.h" #include "gnunet_ats_service.h" #include "gnunet-service-ats_normalization.h" /** * Preference client */ struct PreferenceClient { /** * Next in DLL */ struct PreferenceClient *prev; /** * Next in DLL */ struct PreferenceClient *next; /** * Client handle */ void *client; /** * Total preference for this peer */ double f_abs_sum[GNUNET_ATS_PreferenceCount]; /** * List of peer preferences for this client */ /** * Head of peer list */ struct PreferencePeer *p_head; /** * Tail of peer list */ struct PreferencePeer *p_tail; }; /** * Preference peer */ struct PreferencePeer { /** * Next in DLL */ struct PreferencePeer *next; /** * Previous in DLL */ struct PreferencePeer *prev; /** * Client */ struct PreferenceClient *client; /** * Peer id */ struct GNUNET_PeerIdentity id; /** * Absolute preference values */ double f_abs[GNUNET_ATS_PreferenceCount]; /** * Relative preference values */ double f_rel[GNUNET_ATS_PreferenceCount]; /** * Aging Task */ GNUNET_SCHEDULER_TaskIdentifier aging_task; }; /** * Relative preferences for a peer */ struct PeerRelative { /** * Relative preference values */ double f_rel[GNUNET_ATS_PreferenceCount]; /** * Peer id */ struct GNUNET_PeerIdentity id; }; /** * Callback to call on changing preference values */ static GAS_Normalization_preference_changed_cb pref_changed_cb; /** * Closure for callback to call on changing preference values */ static void *pref_changed_cb_cls; /** * Hashmap to store peer information */ static struct GNUNET_CONTAINER_MultiHashMap *peers; /** * Clients in DLL: head */ static struct PreferenceClient *pc_head; /** * Clients in DLL: tail */ static struct PreferenceClient *pc_tail; /** * Default values */ static struct PeerRelative defvalues; /** * Update a peer * @param id peer id * @pram kind the kind */ static double update_peers (struct GNUNET_PeerIdentity *id, enum GNUNET_ATS_PreferenceKind kind) { struct PreferenceClient *c_cur; struct PreferencePeer *p_cur; struct PeerRelative *rp; double f_rel_total; double backup; unsigned int count; f_rel_total = 0.0; count = 0; /* For all clients */ for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next) { /* Find peer with id */ for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) { if (0 == memcmp (id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity))) break; } if (NULL != p_cur) { /* Found peer with id */ f_rel_total += p_cur->f_rel[kind]; count ++; } } /* Find a client */ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "%u clients have a total relative preference for peer `%s''s `%s' of %.3f\n", count, GNUNET_i2s (id), GNUNET_ATS_print_preference_type (kind), f_rel_total); if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey))) { backup = rp->f_rel[kind]; if (0 < count) { rp->f_rel[kind] = f_rel_total / count; } else { rp->f_rel[kind] = DEFAULT_REL_PREFERENCE; } } else { return DEFAULT_REL_PREFERENCE; } if ((backup != rp->f_rel[kind]) && (NULL != pref_changed_cb)) { pref_changed_cb (pref_changed_cb_cls, &rp->id, kind, rp->f_rel[kind]); } return rp->f_rel[kind]; } /** * Recalculate preference for a specific ATS property * * @param c the preference client * @param p the peer * @param kind the preference kind * @return the result */ static double recalculate_rel_preferences (struct PreferenceClient *c, struct PreferencePeer *p, enum GNUNET_ATS_PreferenceKind kind) { struct PreferencePeer *p_cur; struct PeerRelative *rp; double backup; double res; double ret; /* For this client: sum preferences to total preference */ c->f_abs_sum[kind] = 0; for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next) c->f_abs_sum[kind] += p_cur->f_abs[kind]; GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p has total preference for %s of %.3f\n", c->client, GNUNET_ATS_print_preference_type (kind), c->f_abs_sum[kind]); ret = DEFAULT_REL_PREFERENCE; /* For all peers: calculate relative preference */ for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next) { /* Calculate relative preference for specific kind */ backup = p_cur->f_rel[kind]; if (DEFAULT_ABS_PREFERENCE == c->f_abs_sum[kind]) /* No peer has a preference for this property, * so set default preference */ p_cur->f_rel[kind] = DEFAULT_REL_PREFERENCE; else p_cur->f_rel[kind] = (c->f_abs_sum[kind] + p_cur->f_abs[kind]) / c->f_abs_sum[kind]; GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p: peer `%s' has relative preference for %s of %.3f\n", c->client, GNUNET_i2s (&p_cur->id), GNUNET_ATS_print_preference_type (kind), p_cur->f_rel[kind]); res = 0.0; if (p_cur->f_rel[kind] != backup) { /* Value changed, recalculate */ res = update_peers (&p_cur->id,kind); if (0 == memcmp (&p->id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity))) ret = res; } else { /* Value did not chang, return old value*/ GNUNET_assert (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &p->id.hashPubKey))); ret = rp->f_rel[kind]; } } return ret; } /** * Update the absolute preference value for a peer * @param id peer id * @param kind the kind * @return the new relative preference value */ static double update_preference (struct PreferenceClient *c, struct PreferencePeer *p, enum GNUNET_ATS_PreferenceKind kind, float score_abs) { double score = score_abs; /* Update preference value according to type */ switch (kind) { case GNUNET_ATS_PREFERENCE_BANDWIDTH: case GNUNET_ATS_PREFERENCE_LATENCY: p->f_abs[kind] = (p->f_abs[kind] + score) / 2; break; case GNUNET_ATS_PREFERENCE_END: break; default: break; } return recalculate_rel_preferences (c, p, kind); } /** * Reduce absolute preferences since they got old * * @param cls the PreferencePeer * @param tc context */ static void preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) { int i; double backup; struct PreferencePeer *p = cls; GNUNET_assert (NULL != p); p->aging_task = GNUNET_SCHEDULER_NO_TASK; GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aging preferences for peer `%s'\n", GNUNET_i2s (&p->id)); /* Aging absolute values: */ for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) { backup = p->f_abs[i]; if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE) p->f_abs[i] *= PREF_AGING_FACTOR; if (backup != p->f_abs[i]) { GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aged preference for peer `%s' from %.3f to %.3f\n", GNUNET_i2s (&p->id), backup, p->f_abs[i]); recalculate_rel_preferences (p->client, p, i); } } p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p); } /** * Normalize an updated preference value * * @param src 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 */ float GAS_normalization_change_preference (void *src, const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind, float score_abs) { float score_rel; struct PreferenceClient *c_cur; struct PreferencePeer *p_cur; struct PeerRelative *r_cur; int i; GNUNET_assert (NULL != src); GNUNET_assert (NULL != peer); GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Client %p changes preference for peer `%s' for `%s' to %.2f\n", src, GNUNET_i2s (peer), GNUNET_ATS_print_preference_type (kind), score_abs); if (kind >= GNUNET_ATS_PreferenceCount) { GNUNET_break (0); return 0.0; } /* Find preference client */ for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next) { if (src == c_cur->client) break; } /* Not found: create new preference client */ if (NULL == c_cur) { c_cur = GNUNET_malloc (sizeof (struct PreferenceClient)); c_cur->client = src; GNUNET_CONTAINER_DLL_insert (pc_head, pc_tail, c_cur); } /* Find entry for peer */ for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next) if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id))) break; /* Not found: create new peer entry */ if (NULL == p_cur) { p_cur = GNUNET_malloc (sizeof (struct PreferencePeer)); p_cur->client = c_cur; p_cur->id = (*peer); for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) { /* Default value per peer absolut preference for a quality: * No value set, so absolute preference 0 */ p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE; /* Default value per peer relative preference for a quality: 1.0 */ p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE; } p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL, &preference_aging, p_cur); GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur); } if (NULL == (r_cur = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey))) { r_cur = GNUNET_malloc (sizeof (struct PeerRelative)); r_cur->id = (*peer); for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE; GNUNET_CONTAINER_multihashmap_put (peers, &r_cur->id.hashPubKey, r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); } score_rel = update_preference (c_cur, p_cur, kind, score_abs); return score_rel; } /** * Get the normalized preference values for a specific peer or * the default values if * * @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_normalization_get_preferences (const struct GNUNET_PeerIdentity *id) { GNUNET_assert (NULL != peers); GNUNET_assert (NULL != id); struct PeerRelative *rp; if (NULL == (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey))) { return defvalues.f_rel; } return rp->f_rel; } /** * Start the normalization component * * @param pref_ch_cb callback to call on relative preference changing * @param ref_ch_cb_cls cls for the callback */ void GAS_normalization_start (GAS_Normalization_preference_changed_cb pref_ch_cb, void *pref_ch_cb_cls) { int i; peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO); pref_changed_cb = pref_ch_cb; pref_changed_cb_cls = pref_ch_cb_cls; for (i = 0; i < GNUNET_ATS_PreferenceCount; i++) defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE; return; } /** * Free a peer * * @param cls unused * @param key the key * @param value RelativePeer * @return GNUNET_OK to continue */ static int free_peer (void *cls, const struct GNUNET_HashCode * key, void *value) { struct PeerRelative *rp = value; GNUNET_CONTAINER_multihashmap_remove (peers, key, value); GNUNET_free (rp); return GNUNET_OK; } /** * Stop the normalization component and free all items */ void GAS_normalization_stop () { struct PreferenceClient *pc; struct PreferenceClient *next_pc; struct PreferencePeer *p; struct PreferencePeer *next_p; next_pc = pc_head; while (NULL != (pc = next_pc)) { next_pc = pc->next; GNUNET_CONTAINER_DLL_remove (pc_head, pc_tail, pc); next_p = pc->p_head; while (NULL != (p = next_p)) { next_p = p->next; if (GNUNET_SCHEDULER_NO_TASK != p->aging_task) { GNUNET_SCHEDULER_cancel(p->aging_task); p->aging_task = GNUNET_SCHEDULER_NO_TASK; } GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p); GNUNET_free (p); } GNUNET_free (pc); } GNUNET_CONTAINER_multihashmap_iterate (peers, &free_peer, NULL); GNUNET_CONTAINER_multihashmap_destroy (peers); return; } /* end of gnunet-service-ats_normalization.c */