GNUnet  0.17.6
gnunet-service-cadet_paths.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2001-2017 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your 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  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
26 #include "platform.h"
31 
32 
33 #define LOG(level, ...) GNUNET_log_from (level, "cadet-pat", __VA_ARGS__)
34 
35 
40 {
46 
52 
58 
62  unsigned int entries_length;
63 };
64 
65 
71 static void
73 {
74  double result = 0.0;
75 
76  for (unsigned int i = 0; i < path->entries_length; i++)
77  {
78  struct CadetPeer *cp = path->entries[i]->peer;
79 
81  i);
82  }
84 }
85 
86 
102 {
103  return path->desirability;
104 }
105 
106 
117 struct CadetConnection *
119  struct CadetPeer *destination,
120  unsigned int off)
121 {
122  struct CadetPeerPathEntry *entry;
123 
124  GNUNET_assert (off < path->entries_length);
125  entry = path->entries[off];
126  GNUNET_assert (entry->peer == destination);
127  return entry->cc;
128 }
129 
130 
139 void
141  unsigned int off,
142  struct CadetConnection *cc)
143 {
144  struct CadetPeerPathEntry *entry;
145 
147  "Adding %s to path %s at offset %u\n",
148  GCC_2s (cc),
149  GCPP_2s (path),
150  off);
151  GNUNET_assert (off < path->entries_length);
152  entry = path->entries[off];
153  GNUNET_assert (NULL == entry->cc);
154  GNUNET_assert (NULL != cc);
155  entry->cc = cc;
156 }
157 
158 
167 void
169  unsigned int off,
170  struct CadetConnection *cc)
171 {
172  struct CadetPeerPathEntry *entry;
173 
175  "Removing connection %s to path %s at offset %u\n",
176  GCC_2s (cc),
177  GCPP_2s (path),
178  off);
179  GNUNET_assert (off < path->entries_length);
180  entry = path->entries[off];
181  GNUNET_assert (cc == entry->cc);
182  entry->cc = NULL;
183 }
184 
185 
195 static void
196 attach_path (struct CadetPeerPath *path, unsigned int stop_at)
197 {
198  GNUNET_assert (NULL == path->hn);
199 
200  /* Try to attach this path to a peer, working backwards from the end. */
201  while (path->entries_length > stop_at)
202  {
203  unsigned int end = path->entries_length - 1;
204  struct CadetPeerPathEntry *entry = path->entries[end];
205  int force = GNUNET_NO;
206 
208  /* If the entry already has a connection using it, force attach. */
209  if (NULL != entry->cc)
210  force = GNUNET_YES;
211  path->hn = GCP_attach_path (entry->peer,
212  path,
213  end,
214  force);
215  if (NULL != path->hn)
216  break;
217 
218  /* Attach failed, trim this entry from the path. */
219  GNUNET_assert (NULL == entry->cc);
220  GCP_path_entry_remove (entry->peer,
221  entry,
222  end);
223  GNUNET_free (entry);
224  path->entries[end] = NULL;
225  path->entries_length--;
226  }
227 
228  /* Shrink array to actual path length. */
232 }
233 
234 
242 void
244 {
245  struct CadetPeerPathEntry *entry;
246 
248  "Owner releases path %s\n",
249  GCPP_2s (path));
250  path->hn = NULL;
251  entry = path->entries[path->entries_length - 1];
252  GNUNET_assert (path == entry->path);
253  GNUNET_assert (NULL == entry->cc);
254  /* cut 'off' end of path */
255  GCP_path_entry_remove (entry->peer,
256  entry,
257  path->entries_length - 1);
258  GNUNET_free (entry);
259  path->entries[path->entries_length - 1] = NULL;
260  path->entries_length--;
261  /* see if new peer at the end likes this path any better */
262  attach_path (path, 0);
263  if (NULL == path->hn)
264  {
265  /* nobody wants us, discard the path */
267  GNUNET_assert (NULL == path->entries);
268  GNUNET_free (path);
269  }
270 }
271 
272 
281 void
283  unsigned int off,
284  int delta)
285 {
286  struct CadetPeerPathEntry *entry;
287 
288  GNUNET_assert (off < path->entries_length);
289  entry = path->entries[off];
290 
291  /* Add delta, with checks for overflows */
292  if (delta >= 0)
293  {
294  if (delta + entry->score < entry->score)
295  entry->score = INT_MAX;
296  else
297  entry->score += delta;
298  }
299  else
300  {
301  if (delta + entry->score > entry->score)
302  entry->score = INT_MIN;
303  else
304  entry->score += delta;
305  }
307 }
308 
309 
314 {
319 
323  struct CadetPeer **cpath;
324 
328  unsigned int cpath_length;
329 };
330 
331 
342 static int
343 check_match (void *cls,
344  struct CadetPeerPath *path,
345  unsigned int off)
346 {
347  struct CheckMatchContext *cm_ctx = cls;
348 
349  GNUNET_assert (path->entries_length > off);
350  if ((path->entries_length != off + 1) &&
351  (off + 1 != cm_ctx->cpath_length))
352  {
354  "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n",
355  GCPP_2s (path),
356  path->entries_length,
357  off + 1,
358  cm_ctx->cpath_length);
359  return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
360  }
361  for (unsigned int i = 0; i < off; i++)
362  if (cm_ctx->cpath[i] !=
364  i))
365  {
367  "check_match path %s mismatches at offset %u\n",
368  GCPP_2s (path),
369  i);
370  return GNUNET_YES; /* mismatch, ignore */
371  }
373  "check_match found match with path %s\n",
374  GCPP_2s (path));
375  cm_ctx->match = path;
376  return GNUNET_NO; /* match, we are done! */
377 }
378 
379 
390 static void
392  struct CadetPeer **peers,
393  unsigned int num_peers,
394  int force)
395 {
396  unsigned int old_len = path->entries_length;
397  int i;
398 
399  /* Expand path */
400  GNUNET_array_grow (path->entries,
401  path->entries_length,
402  old_len + num_peers);
403  for (i = num_peers - 1; i >= 0; i--)
404  {
405  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
406 
407  path->entries[old_len + i] = entry;
408  entry->peer = peers[i];
409  entry->path = path;
410  }
411  for (i = num_peers - 1; i >= 0; i--)
412  {
413  struct CadetPeerPathEntry *entry = path->entries[old_len + i];
414 
415  GCP_path_entry_add (entry->peer,
416  entry,
417  old_len + i);
418  }
419 
420  /* If we extend an existing path, detach it from the
421  old owner and re-attach to the new one */
422  GCP_detach_path (path->entries[old_len - 1]->peer,
423  path,
424  path->hn);
425  path->hn = NULL;
426  path->entries_length = old_len + num_peers;
427  if (GNUNET_YES == force)
428  {
429  int end = path->entries_length - 1;
430 
432  path,
433  end,
434  GNUNET_YES);
435  }
436  else
437  {
438  attach_path (path, old_len);
439  }
440  if (NULL == path->hn)
441  {
442  /* none of the peers is interested in this path;
443  re-attach. */
444  GNUNET_assert (old_len == path->entries_length);
445  path->hn = GCP_attach_path (path->entries[old_len - 1]->peer,
446  path,
447  old_len - 1,
448  GNUNET_YES);
449  GNUNET_assert (NULL != path->hn);
450  return;
451  }
453  "Extended path %s\n",
454  GCPP_2s (path));
455 }
456 
457 
470 void
472  unsigned int get_path_length,
473  const struct GNUNET_DHT_PathElement *put_path,
474  unsigned int put_path_length)
475 {
476  struct CadetPeer *cpath[get_path_length + put_path_length];
477  struct CheckMatchContext cm_ctx;
478  struct CadetPeerPath *path;
479  unsigned int skip;
480  unsigned int total_len;
481 
482  /* precompute 'cpath' so we can avoid doing the lookups lots of times */
483  skip = 0;
484  memset (cpath,
485  0,
486  sizeof(cpath)); /* Just to trigger harder errors later. */
487  total_len = get_path_length + put_path_length;
488  for (unsigned int off = 0; off < total_len; off++)
489  {
490  const struct GNUNET_PeerIdentity *pid;
491 
492  pid = (off < get_path_length)
493  ? &get_path[get_path_length - off - 1].pred
494  : &put_path[get_path_length + put_path_length - off - 1].pred;
495  /* Check that I am not in the path */
496  if (0 == GNUNET_memcmp (&my_full_id,
497  pid))
498  {
499  skip = off + 1;
500  continue;
501  }
502  cpath[off - skip] = GCP_get (pid,
503  GNUNET_YES);
504  /* Check that no peer is twice on the path */
505  for (unsigned int i = 0; i < off - skip; i++)
506  {
507  if (cpath[i] == cpath[off - skip])
508  {
509  skip = off - i;
510  break;
511  }
512  }
513  }
514  if (skip >= total_len)
515  {
517  "Path discovered from DHT is one big cycle?\n");
518  return;
519  }
520  total_len -= skip;
521 
522  /* First figure out if this path is a subset of an existing path, an
523  extension of an existing path, or a new path. */
524  cm_ctx.cpath_length = total_len;
525  cm_ctx.cpath = cpath;
526  cm_ctx.match = NULL;
527  for (int i = total_len - 1; i >= 0; i--)
528  {
529  GCP_iterate_paths_at (cpath[i],
530  (unsigned int) i,
531  &check_match,
532  &cm_ctx);
533  if (NULL != cm_ctx.match)
534  {
535  if (i == total_len - 1)
536  {
537  /* Existing path includes this one, nothing to do! */
539  "Path discovered from DHT is already known\n");
540  return;
541  }
542  if (cm_ctx.match->entries_length == i + 1)
543  {
544  /* Existing path ends in the middle of new path, extend it! */
546  "Trying to extend existing path %s by additional links discovered from DHT\n",
547  GCPP_2s (cm_ctx.match));
548  extend_path (cm_ctx.match,
549  &cpath[i + 1],
550  total_len - i - 1,
551  GNUNET_NO);
552  return;
553  }
554  }
555  }
556 
557  /* No match at all, create completely new path */
558  path = GNUNET_new (struct CadetPeerPath);
559  path->entries_length = total_len;
560  path->entries = GNUNET_new_array (path->entries_length,
561  struct CadetPeerPathEntry *);
562  for (int i = path->entries_length - 1; i >= 0; i--)
563  {
564  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
565 
566  path->entries[i] = entry;
567  entry->peer = cpath[i];
568  entry->path = path;
569  }
570  for (int i = path->entries_length - 1; i >= 0; i--)
571  {
572  struct CadetPeerPathEntry *entry = path->entries[i];
573 
574  GCP_path_entry_add (entry->peer,
575  entry,
576  i);
577  }
578 
579  /* Finally, try to attach it */
580  attach_path (path, 0);
581  if (NULL == path->hn)
582  {
583  /* None of the peers on the path care about it. */
585  "Path discovered from DHT is not interesting to us\n");
587  GNUNET_assert (NULL == path->entries);
588  GNUNET_free (path);
589  return;
590  }
592  "Created new path %s based on information from DHT\n",
593  GCPP_2s (path));
594 }
595 
596 
597 struct CadetPeerPath *
598 GCPP_get_path_from_route (unsigned int path_length,
599  const struct GNUNET_PeerIdentity *pids)
600 {
601  struct CheckMatchContext cm_ctx;
602  struct CadetPeer *cpath[path_length];
603  struct CadetPeerPath *path;
604 
605  /* precompute inverted 'cpath' so we can avoid doing the lookups and
606  have the correct order */
607  for (unsigned int off = 0; off < path_length; off++)
608  cpath[off] = GCP_get (&pids[path_length - 1 - off],
609  GNUNET_YES);
610 
611  /* First figure out if this path is a subset of an existing path, an
612  extension of an existing path, or a new path. */
613  cm_ctx.cpath = cpath;
614  cm_ctx.cpath_length = path_length;
615  cm_ctx.match = NULL;
616  for (int i = path_length - 1; i >= 0; i--)
617  {
618  GCP_iterate_paths_at (cpath[i],
619  (unsigned int) i,
620  &check_match,
621  &cm_ctx);
622  if (NULL != cm_ctx.match)
623  {
624  if (i == path_length - 1)
625  {
626  /* Existing path includes this one, return the match! */
628  "Returning existing path %s as inverse for incoming connection\n",
629  GCPP_2s (cm_ctx.match));
630  return cm_ctx.match;
631  }
632  if (cm_ctx.match->entries_length == i + 1)
633  {
634  /* Existing path ends in the middle of new path, extend it! */
636  "Extending existing path %s to create inverse for incoming connection\n",
637  GCPP_2s (cm_ctx.match));
638  extend_path (cm_ctx.match,
639  &cpath[i + 1],
640  path_length - i - 1,
641  GNUNET_YES);
642  /* Check that extension was successful */
643  GNUNET_assert (cm_ctx.match->entries_length == path_length);
644  return cm_ctx.match;
645  }
646  /* Eh, we found a match but couldn't use it? Something is wrong. */
647  GNUNET_break (0);
648  }
649  }
650 
651  /* No match at all, create completely new path */
652  path = GNUNET_new (struct CadetPeerPath);
653  path->entries_length = path_length;
654  path->entries = GNUNET_new_array (path->entries_length,
655  struct CadetPeerPathEntry *);
656  for (int i = path_length - 1; i >= 0; i--)
657  {
658  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
659 
660  path->entries[i] = entry;
661  entry->peer = cpath[i];
662  entry->path = path;
663  }
664  for (int i = path_length - 1; i >= 0; i--)
665  {
666  struct CadetPeerPathEntry *entry = path->entries[i];
667 
668  GCP_path_entry_add (entry->peer,
669  entry,
670  i);
671  }
674  "Created new path %s to create inverse for incoming connection\n",
675  GCPP_2s (path));
676  path->hn = GCP_attach_path (cpath[path_length - 1],
677  path,
678  path_length - 1,
679  GNUNET_YES);
680  return path;
681 }
682 
683 
691 unsigned int
693 {
694  return path->entries_length;
695 }
696 
697 
705 unsigned int
707  struct CadetPeer *cp)
708 {
709  for (unsigned int off = 0;
710  off < path->entries_length;
711  off++)
712  if (cp == GCPP_get_peer_at_offset (path,
713  off))
714  return off;
715  return UINT_MAX;
716 }
717 
718 
719 struct CadetPeer *
721  unsigned int off)
722 {
723  GNUNET_assert (off < path->entries_length);
724  return path->entries[off]->peer;
725 }
726 
727 
734 const char *
735 GCPP_2s (struct CadetPeerPath *path)
736 {
737  static char buf[2048];
738  size_t off;
739  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
740 
741  off = 0;
742  for (unsigned int i = 0;
743  i < path->entries_length;
744  i++)
745  {
746  if ((path->entries_length > max_plen) &&
747  (i == max_plen / 2))
748  off += GNUNET_snprintf (&buf[off],
749  sizeof(buf) - off,
750  "...-");
751  if ((path->entries_length > max_plen) &&
752  (i > max_plen / 2) &&
753  (i < path->entries_length - max_plen / 2))
754  continue;
755  off += GNUNET_snprintf (&buf[off],
756  sizeof(buf) - off,
757  "%s%s",
759  path,
760  i))),
761  (i == path->entries_length - 1) ? "" : "-");
762  }
763  GNUNET_snprintf (&buf[off],
764  sizeof(buf) - off,
765  "(%p)",
766  path);
767  return buf;
768 }
769 
770 
771 /* end of gnunet-service-cadet-new_paths.c */
#define INT_MAX
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static struct CadetPeer * peers
Operation to get peer ids.
static unsigned int num_peers
static int result
Global testing status.
struct GNUNET_PeerIdentity my_full_id
Local peer own ID.
const char * GCC_2s(const struct CadetConnection *cc)
Get a (static) string for a connection.
A connection is a live end-to-end messaging mechanism where the peers are identified by a path and kn...
static int check_match(void *cls, struct CadetPeerPath *path, unsigned int off)
Check if the given path is identical on all of the hops until off, and not longer than off.
void GCPP_try_path_from_dht(const struct GNUNET_DHT_PathElement *get_path, unsigned int get_path_length, const struct GNUNET_DHT_PathElement *put_path, unsigned int put_path_length)
Create a peer path based on the result of a DHT lookup.
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
unsigned int GCPP_get_length(struct CadetPeerPath *path)
Return the length of the path.
static void attach_path(struct CadetPeerPath *path, unsigned int stop_at)
Tries to attach path to a peer, working backwards from the end and stopping at stop_at.
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path's desirability score.
void GCPP_update_score(struct CadetPeerPath *path, unsigned int off, int delta)
Updates the score for an entry on the path based on our experiences with using path.
struct CadetPeerPath * GCPP_get_path_from_route(unsigned int path_length, const struct GNUNET_PeerIdentity *pids)
We got an incoming connection, obtain the corresponding path.
GNUNET_CONTAINER_HeapCostType GCPP_get_desirability(const struct CadetPeerPath *path)
Return how much we like keeping the path.
struct CadetConnection * GCPP_get_connection(struct CadetPeerPath *path, struct CadetPeer *destination, unsigned int off)
Return connection to destination using path, or return NULL if no such connection exists.
void GCPP_del_connection(struct CadetPeerPath *path, unsigned int off, struct CadetConnection *cc)
Notify path that it is no longer used for connection cc which ended at the path's offset off.
void GCPP_release(struct CadetPeerPath *path)
The owning peer of this path is no longer interested in maintaining it, so the path should be discard...
#define LOG(level,...)
void GCPP_add_connection(struct CadetPeerPath *path, unsigned int off, struct CadetConnection *cc)
Notify path that it is used for connection cc which ends at the path's offset off.
static void extend_path(struct CadetPeerPath *path, struct CadetPeer **peers, unsigned int num_peers, int force)
Extend path path by the num_peers from the peers array, assuming the owners past the current owner wa...
unsigned int GCPP_find_peer(struct CadetPeerPath *path, struct CadetPeer *cp)
Find peer's offset on path.
void GCP_detach_path(struct CadetPeer *cp, struct CadetPeerPath *path, struct GNUNET_CONTAINER_HeapNode *hn)
This peer can no longer own path as the path has been extended and a peer further down the line is no...
void GCP_path_entry_add(struct CadetPeer *cp, struct CadetPeerPathEntry *entry, unsigned int off)
Add an entry to the DLL of all of the paths that this peer is on.
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this cp.
void GCP_path_entry_remove(struct CadetPeer *cp, struct CadetPeerPathEntry *entry, unsigned int off)
Remove an entry from the DLL of all of the paths that this peer is on.
unsigned int GCP_iterate_paths_at(struct CadetPeer *cp, unsigned int dist, GCP_PathIterator callback, void *callback_cls)
Iterate over the paths to peer where peer is at distance dist from us.
double GCP_get_desirability_of_path(struct CadetPeer *cp, unsigned int off)
Calculate how desirable a path is for cp if cp is at offset off in the path.
const struct GNUNET_PeerIdentity * GCP_get_id(struct CadetPeer *cp)
Obtain the peer identity for a struct CadetPeer.
struct CadetPeer * GCP_get(const struct GNUNET_PeerIdentity *peer_id, int create)
Retrieve the CadetPeer structure associated with the peer.
Information we track per peer.
Information we track per tunnel.
static char buf[2048]
static struct GNUNET_PeerIdentity pid
Identity of the peer we transmit to / connect to.
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
@ GNUNET_YES
@ GNUNET_NO
Definition: gnunet_common.h:98
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
int GNUNET_snprintf(char *buf, size_t size, const char *format,...) __attribute__((format(printf
Like snprintf, just aborts if the buffer is of insufficient size.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
static struct GNUNET_TIME_Relative delta
Definition: speedup.c:35
Low-level connection to a destination.
struct CadetPeerPath * path
Path we are using to our destination.
unsigned int off
Offset of our destination in path.
struct CadetPeer * destination
To which peer does this connection go?
Entry in a peer path.
int score
Path's historic score up to this point.
struct CadetPeer * peer
The peer at this offset of the path.
struct CadetConnection * cc
Connection using this path, or NULL for none.
struct CadetPeerPath * path
Path this entry belongs to.
Information regarding a possible path to reach a peer.
unsigned int entries_length
Length of the entries array.
struct CadetPeerPathEntry ** entries
Array of all the peers on the path.
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the path.
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner's heap.
Peer description.
Closure for #find_peer_at() and check_match().
struct CadetPeerPath * match
Set to a matching path, if any.
unsigned int cpath_length
How long is the cpath array?
struct CadetPeer ** cpath
Array the combined paths.
A (signed) path tracking a block's flow through the DHT is represented by an array of path elements,...
The identity of the host (wraps the signing key of the peer).