GNUnet  0.10.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 
39 struct CadetPeerPath {
45 
51 
57 
61  unsigned int entries_length;
62 };
63 
64 
70 static void
72 {
73  double result = 0.0;
74 
75  for (unsigned int i = 0; i < path->entries_length; i++)
76  {
77  struct CadetPeer *cp = path->entries[i]->peer;
78 
79  result += GCP_get_desirability_of_path(cp,
80  i);
81  }
83 }
84 
85 
101 {
102  return path->desirability;
103 }
104 
105 
116 struct CadetConnection *
118  struct CadetPeer *destination,
119  unsigned int off)
120 {
121  struct CadetPeerPathEntry *entry;
122 
123  GNUNET_assert(off < path->entries_length);
124  entry = path->entries[off];
125  GNUNET_assert(entry->peer == destination);
126  return entry->cc;
127 }
128 
129 
138 void
140  unsigned int off,
141  struct CadetConnection *cc)
142 {
143  struct CadetPeerPathEntry *entry;
144 
146  "Adding %s to path %s at offset %u\n",
147  GCC_2s(cc),
148  GCPP_2s(path),
149  off);
150  GNUNET_assert(off < path->entries_length);
151  entry = path->entries[off];
152  GNUNET_assert(NULL == entry->cc);
153  GNUNET_assert(NULL != cc);
154  entry->cc = cc;
155 }
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);
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. */
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 */
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 
318 
322  struct CadetPeer **cpath;
323 
327  unsigned int cpath_length;
328 };
329 
330 
341 static int
342 check_match(void *cls,
343  struct CadetPeerPath *path,
344  unsigned int off)
345 {
346  struct CheckMatchContext *cm_ctx = cls;
347 
348  GNUNET_assert(path->entries_length > off);
349  if ((path->entries_length != off + 1) &&
350  (off + 1 != cm_ctx->cpath_length))
351  {
353  "check_match mismatch because path %s is too long (%u vs. %u vs. %u)\n",
354  GCPP_2s(path),
355  path->entries_length,
356  off + 1,
357  cm_ctx->cpath_length);
358  return GNUNET_YES; /* too long, goes somewhere else already, thus cannot be useful */
359  }
360  for (unsigned int i = 0; i < off; i++)
361  if (cm_ctx->cpath[i] !=
363  i))
364  {
366  "check_match path %s mismatches at offset %u\n",
367  GCPP_2s(path),
368  i);
369  return GNUNET_YES; /* mismatch, ignore */
370  }
372  "check_match found match with path %s\n",
373  GCPP_2s(path));
374  cm_ctx->match = path;
375  return GNUNET_NO; /* match, we are done! */
376 }
377 
378 
389 static void
391  struct CadetPeer **peers,
392  unsigned int num_peers,
393  int force)
394 {
395  unsigned int old_len = path->entries_length;
396  int i;
397 
398  /* Expand path */
400  path->entries_length,
401  old_len + num_peers);
402  for (i = num_peers - 1; i >= 0; i--)
403  {
404  struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
405 
406  path->entries[old_len + i] = entry;
407  entry->peer = peers[i];
408  entry->path = path;
409  }
410  for (i = num_peers - 1; i >= 0; i--)
411  {
412  struct CadetPeerPathEntry *entry = path->entries[old_len + i];
413 
414  GCP_path_entry_add(entry->peer,
415  entry,
416  old_len + i);
417  }
418 
419  /* If we extend an existing path, detach it from the
420  old owner and re-attach to the new one */
421  GCP_detach_path(path->entries[old_len - 1]->peer,
422  path,
423  path->hn);
424  path->hn = NULL;
425  path->entries_length = old_len + num_peers;
426  if (GNUNET_YES == force)
427  {
428  int end = path->entries_length - 1;
429 
430  path->hn = GCP_attach_path(path->entries[end]->peer,
431  path,
432  end,
433  GNUNET_YES);
434  }
435  else
436  {
437  attach_path(path, old_len);
438  }
439  if (NULL == path->hn)
440  {
441  /* none of the peers is interested in this path;
442  re-attach. */
443  GNUNET_assert(old_len == path->entries_length);
444  path->hn = GCP_attach_path(path->entries[old_len - 1]->peer,
445  path,
446  old_len - 1,
447  GNUNET_YES);
448  GNUNET_assert(NULL != path->hn);
449  return;
450  }
452  "Extended path %s\n",
453  GCPP_2s(path));
454 }
455 
456 
469 void
471  unsigned int get_path_length,
472  const struct GNUNET_PeerIdentity *put_path,
473  unsigned int put_path_length)
474 {
475  struct CadetPeer *cpath[get_path_length + put_path_length];
476  struct CheckMatchContext cm_ctx;
477  struct CadetPeerPath *path;
478  unsigned int skip;
479  unsigned int total_len;
480 
481  /* precompute 'cpath' so we can avoid doing the lookups lots of times */
482  skip = 0;
483  memset(cpath,
484  0,
485  sizeof(cpath)); /* Just to trigger harder errors later. */
486  total_len = get_path_length + put_path_length;
487  for (unsigned int off = 0; off < total_len; off++)
488  {
489  const struct GNUNET_PeerIdentity *pid;
490 
491  pid = (off < get_path_length)
492  ? &get_path[get_path_length - off - 1]
493  : &put_path[get_path_length + put_path_length - off - 1];
494  /* Check that I am not in the path */
495  if (0 == GNUNET_memcmp(&my_full_id,
496  pid))
497  {
498  skip = off + 1;
499  continue;
500  }
501  cpath[off - skip] = GCP_get(pid,
502  GNUNET_YES);
503  /* Check that no peer is twice on the path */
504  for (unsigned int i = 0; i < off - skip; i++)
505  {
506  if (cpath[i] == cpath[off - skip])
507  {
508  skip = off - i;
509  break;
510  }
511  }
512  }
513  if (skip >= total_len)
514  {
516  "Path discovered from DHT is one big cycle?\n");
517  return;
518  }
519  total_len -= skip;
520 
521  /* First figure out if this path is a subset of an existing path, an
522  extension of an existing path, or a new path. */
523  cm_ctx.cpath_length = total_len;
524  cm_ctx.cpath = cpath;
525  cm_ctx.match = NULL;
526  for (int i = total_len - 1; i >= 0; i--)
527  {
528  GCP_iterate_paths_at(cpath[i],
529  (unsigned int)i,
530  &check_match,
531  &cm_ctx);
532  if (NULL != cm_ctx.match)
533  {
534  if (i == total_len - 1)
535  {
536  /* Existing path includes this one, nothing to do! */
538  "Path discovered from DHT is already known\n");
539  return;
540  }
541  if (cm_ctx.match->entries_length == i + 1)
542  {
543  /* Existing path ends in the middle of new path, extend it! */
545  "Trying to extend existing path %s by additional links discovered from DHT\n",
546  GCPP_2s(cm_ctx.match));
547  extend_path(cm_ctx.match,
548  &cpath[i + 1],
549  total_len - i - 1,
550  GNUNET_NO);
551  return;
552  }
553  }
554  }
555 
556  /* No match at all, create completely new path */
557  path = GNUNET_new(struct CadetPeerPath);
558  path->entries_length = total_len;
560  struct CadetPeerPathEntry *);
561  for (int i = path->entries_length - 1; i >= 0; i--)
562  {
563  struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
564 
565  path->entries[i] = entry;
566  entry->peer = cpath[i];
567  entry->path = path;
568  }
569  for (int i = path->entries_length - 1; i >= 0; i--)
570  {
571  struct CadetPeerPathEntry *entry = path->entries[i];
572 
573  GCP_path_entry_add(entry->peer,
574  entry,
575  i);
576  }
577 
578  /* Finally, try to attach it */
579  attach_path(path, 0);
580  if (NULL == path->hn)
581  {
582  /* None of the peers on the path care about it. */
584  "Path discovered from DHT is not interesting to us\n");
585  GNUNET_assert(0 == path->entries_length);
586  GNUNET_assert(NULL == path->entries);
587  GNUNET_free(path);
588  return;
589  }
591  "Created new path %s based on information from DHT\n",
592  GCPP_2s(path));
593 }
594 
595 
603 struct CadetPeerPath *
604 GCPP_get_path_from_route(unsigned int path_length,
605  const struct GNUNET_PeerIdentity *pids)
606 {
607  struct CheckMatchContext cm_ctx;
608  struct CadetPeer *cpath[path_length];
609  struct CadetPeerPath *path;
610 
611  /* precompute inverted 'cpath' so we can avoid doing the lookups and
612  have the correct order */
613  for (unsigned int off = 0; off < path_length; off++)
614  cpath[off] = GCP_get(&pids[path_length - 1 - off],
615  GNUNET_YES);
616 
617  /* First figure out if this path is a subset of an existing path, an
618  extension of an existing path, or a new path. */
619  cm_ctx.cpath = cpath;
620  cm_ctx.cpath_length = path_length;
621  cm_ctx.match = NULL;
622  for (int i = path_length - 1; i >= 0; i--)
623  {
624  GCP_iterate_paths_at(cpath[i],
625  (unsigned int)i,
626  &check_match,
627  &cm_ctx);
628  if (NULL != cm_ctx.match)
629  {
630  if (i == path_length - 1)
631  {
632  /* Existing path includes this one, return the match! */
634  "Returning existing path %s as inverse for incoming connection\n",
635  GCPP_2s(cm_ctx.match));
636  return cm_ctx.match;
637  }
638  if (cm_ctx.match->entries_length == i + 1)
639  {
640  /* Existing path ends in the middle of new path, extend it! */
642  "Extending existing path %s to create inverse for incoming connection\n",
643  GCPP_2s(cm_ctx.match));
644  extend_path(cm_ctx.match,
645  &cpath[i + 1],
646  path_length - i - 1,
647  GNUNET_YES);
648  /* Check that extension was successful */
649  GNUNET_assert(cm_ctx.match->entries_length == path_length);
650  return cm_ctx.match;
651  }
652  /* Eh, we found a match but couldn't use it? Something is wrong. */
653  GNUNET_break(0);
654  }
655  }
656 
657  /* No match at all, create completely new path */
658  path = GNUNET_new(struct CadetPeerPath);
659  path->entries_length = path_length;
661  struct CadetPeerPathEntry *);
662  for (int i = path_length - 1; i >= 0; i--)
663  {
664  struct CadetPeerPathEntry *entry = GNUNET_new(struct CadetPeerPathEntry);
665 
666  path->entries[i] = entry;
667  entry->peer = cpath[i];
668  entry->path = path;
669  }
670  for (int i = path_length - 1; i >= 0; i--)
671  {
672  struct CadetPeerPathEntry *entry = path->entries[i];
673 
674  GCP_path_entry_add(entry->peer,
675  entry,
676  i);
677  }
680  "Created new path %s to create inverse for incoming connection\n",
681  GCPP_2s(path));
682  path->hn = GCP_attach_path(cpath[path_length - 1],
683  path,
684  path_length - 1,
685  GNUNET_YES);
686  return path;
687 }
688 
689 
697 unsigned int
699 {
700  return path->entries_length;
701 }
702 
703 
711 unsigned int
713  struct CadetPeer *cp)
714 {
715  for (unsigned int off = 0;
716  off < path->entries_length;
717  off++)
718  if (cp == GCPP_get_peer_at_offset(path,
719  off))
720  return off;
721  return UINT_MAX;
722 }
723 
724 
732 struct CadetPeer *
734  unsigned int off)
735 {
736  GNUNET_assert(off < path->entries_length);
737  return path->entries[off]->peer;
738 }
739 
740 
747 const char *
748 GCPP_2s(struct CadetPeerPath *path)
749 {
750  static char buf[2048];
751  size_t off;
752  const unsigned int max_plen = (sizeof(buf) - 16) / 5 - 2; /* 5 characters per entry */
753 
754  off = 0;
755  for (unsigned int i = 0;
756  i < path->entries_length;
757  i++)
758  {
759  if ((path->entries_length > max_plen) &&
760  (i == max_plen / 2))
761  off += GNUNET_snprintf(&buf[off],
762  sizeof(buf) - off,
763  "...-");
764  if ((path->entries_length > max_plen) &&
765  (i > max_plen / 2) &&
766  (i < path->entries_length - max_plen / 2))
767  continue;
768  off += GNUNET_snprintf(&buf[off],
769  sizeof(buf) - off,
770  "%s%s",
772  i))),
773  (i == path->entries_length - 1) ? "" : "-");
774  }
775  GNUNET_snprintf(&buf[off],
776  sizeof(buf) - off,
777  "(%p)",
778  path);
779  return buf;
780 }
781 
782 
783 /* 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.