gnunet-service-dht_routing.c

Go to the documentation of this file.

/*
     This file is part of GNUnet.
     Copyright (C) 2011, 2022, 2026 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
 */
 
#include "platform.h"
#include "gnunet-service-dht_neighbours.h"
#include "gnunet-service-dht_routing.h"
#include "gnunet-service-dht.h"
#include "gnunet_block_group_lib.h"
 
 
#define DHT_MAX_RECENT (1024 * 128)
 
 
struct RecentRequest
{
  struct GNUNET_PeerIdentity peer;
 
  struct GNUNET_HashCode key;
 
  struct GNUNET_CONTAINER_HeapNode *heap_node;
 
  struct GNUNET_BLOCK_Group *bg;
 
  const void *xquery;
 
  size_t xquery_size;
 
  enum GNUNET_BLOCK_Type type;
 
  enum GNUNET_DHT_RouteOption options;
};
 
 
static struct GNUNET_CONTAINER_Heap *recent_heap;
 
static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
 
 
struct ProcessContext
{
  const struct GNUNET_DATACACHE_Block *bd;
 
  const struct GNUNET_DHT_PathElement *get_path;
 
  unsigned int get_path_length;
 
};
 
 
static enum GNUNET_GenericReturnValue
process (void *cls,
         const struct GNUNET_HashCode *query_hash,
         void *value)
{
  struct ProcessContext *pc = cls;
  struct RecentRequest *rr = value;
  enum GNUNET_BLOCK_ReplyEvaluationResult eval;
  unsigned int get_path_length;
  struct GNUNET_DATACACHE_Block bdx = *pc->bd;
 
  if ( (rr->type != GNUNET_BLOCK_TYPE_ANY) &&
       (rr->type != pc->bd->type) )
    return GNUNET_OK;           /* type mismatch */
  if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
  {
    get_path_length = pc->get_path_length;
  }
  else
  {
    get_path_length = 0;
    bdx.put_path_length = 0;
    bdx.put_path = NULL;
  }
  if ( (0 == (rr->options & GNUNET_DHT_RO_FIND_APPROXIMATE)) &&
       (0 != GNUNET_memcmp (query_hash,
                            &bdx.key)) )
  {
    GNUNET_STATISTICS_update (GDS_stats,
                              "# Inexact matches discarded in exact search",
                              1,
                              GNUNET_NO);
    return GNUNET_OK; /* exact search, but inexact match */
  }
  eval = GNUNET_BLOCK_check_reply (GDS_block_context,
                                   bdx.type,
                                   rr->bg,
                                   &bdx.key,
                                   rr->xquery,
                                   rr->xquery_size,
                                   bdx.data,
                                   bdx.data_size);
  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
              "Result for %s of type %d was evaluated as %d\n",
              GNUNET_h2s (&bdx.key),
              bdx.type,
              eval);
  if (GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED == eval)
  {
    /* If we do not know the block type, we still filter
       exact duplicates by the block content */
    struct GNUNET_HashCode chash;
 
    GNUNET_CRYPTO_hash (bdx.data,
                        bdx.data_size,
                        &chash);
    if (GNUNET_YES ==
        GNUNET_BLOCK_GROUP_bf_test_and_set (rr->bg,
                                            &chash))
      eval = GNUNET_BLOCK_REPLY_OK_DUPLICATE;
    else
      eval = GNUNET_BLOCK_REPLY_OK_MORE;
  }
  switch (eval)
  {
  case GNUNET_BLOCK_REPLY_OK_MORE:
  case GNUNET_BLOCK_REPLY_OK_LAST:
  case GNUNET_BLOCK_REPLY_TYPE_NOT_SUPPORTED:
    {
      struct PeerInfo *pi;
 
      GNUNET_STATISTICS_update (GDS_stats,
                                "# Good REPLIES matched against routing table",
                                1,
                                GNUNET_NO);
      pi = GDS_NEIGHBOURS_lookup_peer (&rr->peer);
      if (NULL == pi)
      {
        /* peer disconnected in the meantime, drop reply */
        GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                    "No matching peer for reply for key %s\n",
                    GNUNET_h2s (query_hash));
        return GNUNET_OK;
      }
      GDS_NEIGHBOURS_handle_reply (pi,
                                   &bdx,
                                   query_hash,
                                   get_path_length,
                                   pc->get_path,
                                   NULL,
                                   NULL);
    }
    break;
  case GNUNET_BLOCK_REPLY_OK_DUPLICATE:
    GNUNET_STATISTICS_update (GDS_stats,
                              "# Duplicate REPLIES matched against routing table",
                              1,
                              GNUNET_NO);
    return GNUNET_OK;
  case GNUNET_BLOCK_REPLY_IRRELEVANT:
    GNUNET_STATISTICS_update (GDS_stats,
                              "# Irrelevant REPLIES matched against routing table",
                              1,
                              GNUNET_NO);
    return GNUNET_OK;
  default:
    GNUNET_break (0);
    return GNUNET_OK;
  }
  return GNUNET_OK;
}
 
 
void
GDS_ROUTING_process (const struct GNUNET_DATACACHE_Block *bd,
                     const struct GNUNET_HashCode *query_hash,
                     unsigned int get_path_length,
                     const struct GNUNET_DHT_PathElement *get_path)
{
  struct ProcessContext pc = {
    .bd = bd,
    .get_path = get_path,
    .get_path_length = get_path_length
  };
 
  GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
                                              query_hash,
                                              &process,
                                              &pc);
}
 
 
static void
expire_oldest_entry (void)
{
  struct RecentRequest *recent_req;
 
  GNUNET_STATISTICS_update (GDS_stats,
                            "# Old entries removed from routing table",
                            1,
                            GNUNET_NO);
  recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
  GNUNET_assert (recent_req != NULL);
  GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
  GNUNET_BLOCK_group_destroy (recent_req->bg);
  GNUNET_assert (GNUNET_YES ==
                 GNUNET_CONTAINER_multihashmap_remove (recent_map,
                                                       &recent_req->key,
                                                       recent_req));
  GNUNET_free (recent_req);
}
 
 
static enum GNUNET_GenericReturnValue
try_combine_recent (void *cls,
                    const struct GNUNET_HashCode *key,
                    void *value)
{
  struct RecentRequest *in = cls;
  struct RecentRequest *rr = value;
 
  if ( (0 != GNUNET_memcmp (&in->peer,
                            &rr->peer)) ||
       (in->type != rr->type) ||
       (in->xquery_size != rr->xquery_size) ||
       (0 != memcmp (in->xquery,
                     rr->xquery,
                     in->xquery_size) ) )
    return GNUNET_OK;
  GNUNET_break (GNUNET_SYSERR !=
                GNUNET_BLOCK_group_merge (in->bg,
                                          rr->bg));
  rr->bg = in->bg;
  GNUNET_free (in);
  return GNUNET_SYSERR;
}
 
 
void
GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
                 enum GNUNET_BLOCK_Type type,
                 struct GNUNET_BLOCK_Group *bg,
                 enum GNUNET_DHT_RouteOption options,
                 const struct GNUNET_HashCode *key,
                 const void *xquery,
                 size_t xquery_size)
{
  struct RecentRequest *recent_req;
 
  while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
    expire_oldest_entry ();
  GNUNET_STATISTICS_update (GDS_stats,
                            "# Entries added to routing table",
                            1,
                            GNUNET_NO);
  recent_req = GNUNET_malloc (sizeof(struct RecentRequest) + xquery_size);
  recent_req->peer = *sender;
  recent_req->key = *key;
  recent_req->bg = bg;
  recent_req->type = type;
  recent_req->options = options;
  recent_req->xquery = &recent_req[1];
  GNUNET_memcpy (&recent_req[1],
                 xquery,
                 xquery_size);
  recent_req->xquery_size = xquery_size;
  if (GNUNET_SYSERR ==
      GNUNET_CONTAINER_multihashmap_get_multiple (recent_map,
                                                  key,
                                                  &try_combine_recent,
                                                  recent_req))
  {
    GNUNET_STATISTICS_update (GDS_stats,
                              "# DHT requests combined",
                              1,
                              GNUNET_NO);
    return;
  }
  recent_req->heap_node
    = GNUNET_CONTAINER_heap_insert (
        recent_heap,
        recent_req,
        GNUNET_TIME_absolute_get ().abs_value_us);
  (void) GNUNET_CONTAINER_multihashmap_put (
    recent_map,
    key,
    recent_req,
    GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
}
 
 
void
GDS_ROUTING_init ()
{
  recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
  recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3,
                                                     GNUNET_NO);
}
 
 
void
GDS_ROUTING_done ()
{
  while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
    expire_oldest_entry ();
  GNUNET_assert (0 ==
                 GNUNET_CONTAINER_heap_get_size (recent_heap));
  GNUNET_CONTAINER_heap_destroy (recent_heap);
  recent_heap = NULL;
  GNUNET_assert (0 ==
                 GNUNET_CONTAINER_multihashmap_size (recent_map));
  GNUNET_CONTAINER_multihashmap_destroy (recent_map);
  recent_map = NULL;
}
 
 
/* end of gnunet-service-dht_routing.c */