GNUnet  0.11.x
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 
80  result += GCP_get_desirability_of_path (cp,
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. */
229  GNUNET_array_grow (path->entries,
230  path->entries_length,
231  path->entries_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 */
266  GNUNET_assert (0 == path->entries_length);
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 
431  path->hn = GCP_attach_path (path->entries[end]->peer,
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_PeerIdentity *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]
494  : &put_path[get_path_length + put_path_length - off - 1];
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");
586  GNUNET_assert (0 == path->entries_length);
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 
604 struct CadetPeerPath *
605 GCPP_get_path_from_route (unsigned int path_length,
606  const struct GNUNET_PeerIdentity *pids)
607 {
608  struct CheckMatchContext cm_ctx;
609  struct CadetPeer *cpath[path_length];
610  struct CadetPeerPath *path;
611 
612  /* precompute inverted 'cpath' so we can avoid doing the lookups and
613  have the correct order */
614  for (unsigned int off = 0; off < path_length; off++)
615  cpath[off] = GCP_get (&pids[path_length - 1 - off],
616  GNUNET_YES);
617 
618  /* First figure out if this path is a subset of an existing path, an
619  extension of an existing path, or a new path. */
620  cm_ctx.cpath = cpath;
621  cm_ctx.cpath_length = path_length;
622  cm_ctx.match = NULL;
623  for (int i = path_length - 1; i >= 0; i--)
624  {
625  GCP_iterate_paths_at (cpath[i],
626  (unsigned int) i,
627  &check_match,
628  &cm_ctx);
629  if (NULL != cm_ctx.match)
630  {
631  if (i == path_length - 1)
632  {
633  /* Existing path includes this one, return the match! */
635  "Returning existing path %s as inverse for incoming connection\n",
636  GCPP_2s (cm_ctx.match));
637  return cm_ctx.match;
638  }
639  if (cm_ctx.match->entries_length == i + 1)
640  {
641  /* Existing path ends in the middle of new path, extend it! */
643  "Extending existing path %s to create inverse for incoming connection\n",
644  GCPP_2s (cm_ctx.match));
645  extend_path (cm_ctx.match,
646  &cpath[i + 1],
647  path_length - i - 1,
648  GNUNET_YES);
649  /* Check that extension was successful */
650  GNUNET_assert (cm_ctx.match->entries_length == path_length);
651  return cm_ctx.match;
652  }
653  /* Eh, we found a match but couldn't use it? Something is wrong. */
654  GNUNET_break (0);
655  }
656  }
657 
658  /* No match at all, create completely new path */
659  path = GNUNET_new (struct CadetPeerPath);
660  path->entries_length = path_length;
661  path->entries = GNUNET_new_array (path->entries_length,
662  struct CadetPeerPathEntry *);
663  for (int i = path_length - 1; i >= 0; i--)
664  {
665  struct CadetPeerPathEntry *entry = GNUNET_new (struct CadetPeerPathEntry);
666 
667  path->entries[i] = entry;
668  entry->peer = cpath[i];
669  entry->path = path;
670  }
671  for (int i = path_length - 1; i >= 0; i--)
672  {
673  struct CadetPeerPathEntry *entry = path->entries[i];
674 
675  GCP_path_entry_add (entry->peer,
676  entry,
677  i);
678  }
681  "Created new path %s to create inverse for incoming connection\n",
682  GCPP_2s (path));
683  path->hn = GCP_attach_path (cpath[path_length - 1],
684  path,
685  path_length - 1,
686  GNUNET_YES);
687  return path;
688 }
689 
690 
698 unsigned int
700 {
701  return path->entries_length;
702 }
703 
704 
712 unsigned int
714  struct CadetPeer *cp)
715 {
716  for (unsigned int off = 0;
717  off < path->entries_length;
718  off++)
719  if (cp == GCPP_get_peer_at_offset (path,
720  off))
721  return off;
722  return UINT_MAX;
723 }
724 
725 
733 struct CadetPeer *
735  unsigned int off)
736 {
737  GNUNET_assert (off < path->entries_length);
738  return path->entries[off]->peer;
739 }
740 
741 
748 const char *
749 GCPP_2s (struct CadetPeerPath *path)
750 {
751  static char buf[2048];
752  size_t off;
753  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
754 
755  off = 0;
756  for (unsigned int i = 0;
757  i < path->entries_length;
758  i++)
759  {
760  if ((path->entries_length > max_plen) &&
761  (i == max_plen / 2))
762  off += GNUNET_snprintf (&buf[off],
763  sizeof(buf) - off,
764  "...-");
765  if ((path->entries_length > max_plen) &&
766  (i > max_plen / 2) &&
767  (i < path->entries_length - max_plen / 2))
768  continue;
769  off += GNUNET_snprintf (&buf[off],
770  sizeof(buf) - off,
771  "%s%s",
773  path,
774  i))),
775  (i == path->entries_length - 1) ? "" : "-");
776  }
777  GNUNET_snprintf (&buf[off],
778  sizeof(buf) - off,
779  "(%p)",
780  path);
781  return buf;
782 }
783 
784 
785 /* end of gnunet-service-cadet-new_paths.c */
struct GNUNET_CONTAINER_HeapNode * hn
Node of this path in the owner&#39;s heap.
Peer description.
Low-level connection to a destination.
static struct GNUNET_TIME_Relative delta
Definition: speedup.c:35
static void recalculate_path_desirability(struct CadetPeerPath *path)
Calculate the path&#39;s desirability score.
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
struct CadetPeer * peer
The peer at this offset of the path.
A connection is a live end-to-end messaging mechanism where the peers are identified by a path and kn...
struct CadetConnection * cc
Connection using this path, or NULL for none.
int GNUNET_snprintf(char *buf, size_t size, const char *format,...)
Like snprintf, just aborts if the buffer is of insufficient size.
const char * GCC_2s(const struct CadetConnection *cc)
Get a (static) string for a connection.
struct GNUNET_PeerIdentity my_full_id
Local peer own ID.
Entry in a peer path.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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...
struct CadetPeerPath * path
Path we are using to our destination.
struct CadetPeer * destination
To which peer does this connection go?
struct CadetPeer ** cpath
Array the combined paths.
#define GNUNET_NO
Definition: gnunet_common.h:78
struct GNUNET_CONTAINER_HeapNode * GCP_attach_path(struct CadetPeer *cp, struct CadetPeerPath *path, unsigned int off, int force)
Try adding a path to this peer.
Information we track per tunnel.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
void GCPP_try_path_from_dht(const struct GNUNET_PeerIdentity *get_path, unsigned int get_path_length, const struct GNUNET_PeerIdentity *put_path, unsigned int put_path_length)
Create a peer path based on the result of a DHT lookup.
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.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
struct CadetPeerPath * match
Set to a matching path, if any.
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.
const char * GCPP_2s(struct CadetPeerPath *path)
Convert a path to a human-readable string.
#define INT_MAX
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
Information we track per peer.
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.
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.
struct CadetPeerPath * path
Path this entry belongs to.
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...
static char buf[2048]
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
static int result
Global testing status.
#define LOG(level,...)
int score
Path&#39;s historic score up to this point.
Node in the heap.
GNUNET_CONTAINER_HeapCostType desirability
Desirability of the path.
unsigned int cpath_length
How long is the cpath array?
uint64_t GNUNET_CONTAINER_HeapCostType
Cost by which elements in a heap can be ordered.
GNUNET_CONTAINER_HeapCostType GCPP_get_desirability(const struct CadetPeerPath *path)
Return how much we like keeping the path.
static unsigned int num_peers
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
unsigned int GCP_iterate_paths_at(struct CadetPeer *cp, unsigned int dist, GCP_PathIterator callback, void *callback_cls)
Iterate over the paths to cp where cp is at distance dist from us.
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.
unsigned int GCPP_find_peer(struct CadetPeerPath *path, struct CadetPeer *cp)
Find peer&#39;s offset on path.
The identity of the host (wraps the signing key of the peer).
struct CadetPeer * GCP_get(const struct GNUNET_PeerIdentity *peer_id, int create)
Retrieve the CadetPeer stucture associated with the peer.
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&#39;s offset off...
static struct CadetPeer * peers
Operation to get peer ids.
struct CadetPeerPathEntry ** entries
Array of all the peers on the 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...
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.
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...
struct CadetPeer * GCPP_get_peer_at_offset(struct CadetPeerPath *path, unsigned int off)
Obtain the peer at offset off in path.
#define GNUNET_YES
Definition: gnunet_common.h:77
unsigned int entries_length
Length of the entries array.
static struct GNUNET_PeerIdentity pid
Identity of the peer we transmit to / connect to.
Closure for #find_peer_at() and check_match().
Information regarding a possible path to reach a peer.
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&#39;s offset off.
unsigned int GCPP_get_length(struct CadetPeerPath *path)
Return the length of the path.
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
#define GNUNET_free(ptr)
Wrapper around free.
const struct GNUNET_PeerIdentity * GCP_get_id(struct CadetPeer *cp)
Obtain the peer identity for a struct CadetPeer.
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...
unsigned int off
Offset of our destination in path.