chiark / gitweb /
server/peer: Use hash tables to find peer records.
authorMark Wooding <mdw@distorted.org.uk>
Mon, 8 Dec 2008 10:11:57 +0000 (10:11 +0000)
committerMark Wooding <mdw@distorted.org.uk>
Mon, 8 Dec 2008 20:10:08 +0000 (20:10 +0000)
server/Makefile.am
server/addrmap.c [new file with mode: 0644]
server/admin.c
server/peer.c
server/tripe-admin.5.in
server/tripe.h

index fe90441..e033ab0 100644 (file)
@@ -41,6 +41,7 @@ tripe_SOURCES         += tripe.h
 
 ## Main sources.
 tripe_SOURCES          += servutil.c
+tripe_SOURCES          += addrmap.c
 tripe_SOURCES          += keymgmt.c
 tripe_SOURCES          += keyset.c
 tripe_SOURCES          += keyexch.c
diff --git a/server/addrmap.c b/server/addrmap.c
new file mode 100644 (file)
index 0000000..0ab72e9
--- /dev/null
@@ -0,0 +1,172 @@
+/* -*-c-*-
+ *
+ * Hashtables keyed by network addresses
+ *
+ * (c) 2007 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of Trivial IP Encryption (TrIPE).
+ *
+ * TrIPE 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 2 of the License, or
+ * (at your option) any later version.
+ *
+ * TrIPE 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 TrIPE; if not, write to the Free Software Foundation,
+ * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include "tripe.h"
+
+#define AM_LOAD(n) (((n) * 3)/2)
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @am_create@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *
+ * Returns:    ---
+ *
+ * Use:                Create an address map, properly set up.
+ */
+
+void am_create(addrmap *m)
+{
+  hash_create(&m->t, 16);
+  m->load = AM_LOAD(m->t.mask + 1);
+}
+
+/* --- @am_destroy@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *
+ * Returns:    ---
+ *
+ * Use:                Destroy an address map, throwing away all the entries.
+ */
+
+void am_destroy(addrmap *m)
+{
+  hash_base *p;
+  hash_iter i;
+
+  for (hash_mkiter(&i, &m->t); (p = hash_next(&i)) != 0; )
+    x_free(m->t.a, p);
+  hash_destroy(&m->t);
+}
+
+/* --- @hash@ --- *
+ *
+ * Arguments:  @const addr *a@ = pointer to address
+ *
+ * Returns:    The hash of the address.
+ */
+
+uint32 hash(const addr *a)
+{
+  switch (a->sa.sa_family) {
+    case AF_INET:
+      return (U32((AF_INET * 0x4eaac1b7ul) +
+                 (a->sin.sin_addr.s_addr * 0xa5dbc837) +
+                 (a->sin.sin_port * 0x3b049e83)));
+    default:
+      abort();
+  }
+}
+
+/* --- @addreq@ --- *
+ *
+ * Arguments:  @const addr *a, *b@ = pointer to addresses
+ *
+ * Returns:    Nonzero if the addresses are equal.
+ */
+
+int addreq(const addr *a, const addr *b)
+{
+  if (a->sa.sa_family != b->sa.sa_family)
+    return (0);
+  switch (a->sa.sa_family) {
+    case AF_INET:
+      return (a->sin.sin_addr.s_addr == b->sin.sin_addr.s_addr &&
+             a->sin.sin_port == b->sin.sin_port);
+    default:
+      abort();
+  }
+}
+
+/* --- @am_find@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *             @const addr *a@ = address to look up
+ *             @size_t sz@ = size of block to allocate
+ *             @unsigned *f@ = where to store flags
+ *
+ * Returns:    Pointer to found item, or null.
+ *
+ * Use:                Finds a record with the given IP address, set @*f@ nonzero
+ *             and returns it.  If @sz@ is zero, and no match was found,
+ *             return null; otherwise allocate a new block of @sz@ bytes,
+ *             clear @*f@ to zero and return the block pointer.
+ */
+
+void *am_find(addrmap *m, const addr *a, size_t sz, unsigned *f)
+{
+  uint32 h = hash(a);
+  hash_base **b, **bb;
+  addrmap_base *i;
+
+  bb = HASH_BIN(&m->t, h);
+  for (b = bb; *b; b = &(*b)->next) {
+    i = (addrmap_base *)*b;
+    if (i->b.hash == h && addreq(a, &i->a)) {
+      *b = i->b.next;
+      i->b.next = *bb;
+      *bb = &i->b;
+      if (f) *f = 1;
+      return (i);
+    }
+  }
+
+  if (f) *f = 0;
+  if (!sz) return (0);
+  i = x_alloc(m->t.a, sz);
+  i->b.hash = h;
+  i->b.next = *bb;
+  *bb = &i->b;
+  i->a = *a;
+
+  if (m->load)
+    m->load--;
+  if (!m->load && hash_extend(&m->t))
+    m->load = AM_LOAD(m->t.mask + 1);
+  return (i);
+}
+
+/* --- @am_remove@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *             @void *i@ = pointer to the item
+ *
+ * Returns:    ---
+ *
+ * Use:                Removes an item from the map.
+ */
+
+void am_remove(addrmap *m, void *i)
+{
+  hash_remove(&m->t, i);
+  x_free(m->t.a, i);
+}
+
+/*----- That's all, folks -------------------------------------------------*/
index 73c7107..288a64f 100644 (file)
@@ -499,12 +499,9 @@ void a_notify(const char *fmt, ...)
 
 void a_quit(void)
 {
-  peer *p;
-
   close(sock.fd);
   unlink(sockname);
-  while ((p = p_first()) != 0)
-    p_destroy(p);
+  FOREACH_PEER(p, { p_destroy(p); });
   exit(0);
 }
 
@@ -1177,7 +1174,9 @@ static void a_doadd(admin_resop *r, int rc)
   if (rc == ARES_OK) {
     add->peer.sasz = add->r.sasz;
     add->peer.sa = add->r.sa;
-    if (p_find(add->peer.name))
+    if (p_findbyaddr(&add->r.sa))
+      a_bgfail(&add->r.bg, "peer-addr-exists", "?ADDR", &add->r.sa, A_END);
+    else if (p_find(add->peer.name))
       a_bgfail(&add->r.bg, "peer-exists", "%s", add->peer.name, A_END);
     else if (!p_create(&add->peer))
       a_bgfail(&add->r.bg, "peer-create-fail", "%s", add->peer.name, A_END);
@@ -1648,10 +1647,7 @@ static void acmd_bgcancel(admin *a, unsigned ac, char *av[])
 
 static void acmd_list(admin *a, unsigned ac, char *av[])
 {
-  peer *p;
-
-  for (p = p_first(); p; p = p_next(p))
-    a_info(a, "%s", p_name(p), A_END);
+  FOREACH_PEER(p, {  a_info(a, "%s", p_name(p), A_END); });
   a_ok(a);
 }
 
index 675ceff..e57c6ba 100644 (file)
@@ -30,7 +30,8 @@
 
 /*----- Static variables --------------------------------------------------*/
 
-static peer *peers = 0;
+static sym_table byname;
+static addrmap byaddr;
 static sel_file sock;
 
 /*----- Tunnel table ------------------------------------------------------*/
@@ -175,16 +176,11 @@ static void p_read(int fd, unsigned mode, void *v)
 
   /* --- Find the appropriate peer --- */
 
-  assert(a.sa.sa_family == AF_INET);
-  for (p = peers; p; p = p->next) {
-    if (p->spec.sa.sin.sin_addr.s_addr == a.sin.sin_addr.s_addr &&
-       p->spec.sa.sin.sin_port == a.sin.sin_port)
-      goto found;
+  if ((p = p_findbyaddr(&a)) == 0) {
+    a_warn("PEER", "-", "unexpected-source", "?ADDR", &a, A_END);
+    return;
   }
-  a_warn("PEER", "-", "unexpected-source", "?ADDR", &a, A_END);
-  return;
 
-found:
   IF_TRACING(T_PEER, {
     trace(T_PEER, "peer: packet received from `%s'", p->spec.name);
     trace_block(T_PACKET, "peer: packet contents", buf_i, n);
@@ -510,12 +506,8 @@ void p_tun(peer *p, buf *b)
 
 void p_keyreload(void)
 {
-  peer *p;
-
-  if (km_reload()) {
-    for (p = peers; p; p = p->next)
-      kx_newkeys(&p->kx);
-  }
+  if (km_reload())
+    FOREACH_PEER(p, { kx_newkeys(&p->kx); });
 }
 
 /* --- @p_interval@ --- *
@@ -529,11 +521,8 @@ void p_keyreload(void)
 
 void p_interval(void)
 {
-  peer *p;
-
   p_keyreload();
-  for (p = peers; p; p = p->next)
-    ksl_prune(&p->ks);
+  FOREACH_PEER(p, { ksl_prune(&p->ks); });
 }
 
 /* --- @p_stats@ --- *
@@ -622,6 +611,9 @@ void p_init(struct in_addr addr, unsigned port)
   sel_initfile(&sel, &sock, fd, SEL_READ, p_read, 0);
   sel_addfile(&sock);
   T( trace(T_PEER, "peer: created socket"); )
+
+  sym_create(&byname);
+  am_create(&byaddr);
 }
 
 /* --- @p_port@ --- *
@@ -693,25 +685,27 @@ static void p_setkatimer(peer *p)
 peer *p_create(peerspec *spec)
 {
   peer *p = CREATE(peer);
+  unsigned f;
+
+  p->byname = sym_find(&byname, spec->name, -1, sizeof(peer_byname), &f);
+  if (f) goto tidy_0;
+  p->byaddr = am_find(&byaddr, &spec->sa, sizeof(peer_byaddr), &f);
+  if (f) goto tidy_1;
+  p->byname->p = p->byaddr->p = p;
 
   T( trace(T_PEER, "peer: creating new peer `%s'", spec->name); )
   p->spec = *spec;
-  p->spec.name = xstrdup(spec->name);
+  p->spec.name = (/*unconst*/ char *)SYM_NAME(p->byname);
   p->ks = 0;
-  p->prev = 0;
   p->pings = 0;
   p->ifname = 0;
   memset(&p->st, 0, sizeof(stats));
   p->st.t_start = time(0);
   if ((p->t = spec->tops->create(p, &p->ifname)) == 0)
-    goto tidy_0;
+    goto tidy_2;
   p_setkatimer(p);
   if (kx_init(&p->kx, p, &p->ks, p->spec.kxf))
-    goto tidy_1;
-  p->next = peers;
-  if (peers)
-    peers->prev = p;
-  peers = p;
+    goto tidy_3;
   a_notify("ADD",
            "?PEER", p,
            "%s", p->ifname,
@@ -723,13 +717,16 @@ peer *p_create(peerspec *spec)
   }
   return (p);
 
-tidy_1:
+tidy_3:
   if (spec->t_ka)
     sel_rmtimer(&p->tka);
   xfree(p->ifname);
   p->t->ops->destroy(p->t);
+tidy_2:
+  am_remove(&byaddr, p->byaddr);
+tidy_1:
+  sym_remove(&byname, p->byname);
 tidy_0:
-  xfree(p->spec.name);
   DESTROY(p);
   return (0);
 }
@@ -752,6 +749,24 @@ const char *p_name(peer *p) { return (p->spec.name); }
 
 const peerspec *p_spec(peer *p) { return (&p->spec); }
 
+/* --- @p_findbyaddr@ --- *
+ *
+ * Arguments:  @const addr *a@ = address to look up
+ *
+ * Returns:    Pointer to the peer block, or null if not found.
+ *
+ * Use:                Finds a peer by address.
+ */
+
+peer *p_findbyaddr(const addr *a)
+{
+  peer_byaddr *pa;
+
+  if ((pa = am_find(&byaddr, a, 0, 0)) != 0)
+    return (pa->p);
+  return (0);
+}
+
 /* --- @p_find@ --- *
  *
  * Arguments:  @const char *name@ = name to look up
@@ -763,11 +778,10 @@ const peerspec *p_spec(peer *p) { return (&p->spec); }
 
 peer *p_find(const char *name)
 {
-  peer *p;
-  for (p = peers; p; p = p->next) {
-    if (strcmp(name, p->spec.name) == 0)
-      return (p);
-  }
+  peer_byname *pn;
+
+  if ((pn = sym_find(&byname, name, -1, 0, 0)) != 0)
+    return (pn->p);
   return (0);
 }
 
@@ -797,25 +811,38 @@ void p_destroy(peer *p)
     ppg = pg->next;
     p_pingdone(pg, PING_PEERDIED);
   }
-  if (p->next)
-    p->next->prev = p->prev;
-  if (p->prev)
-    p->prev->next = p->next;
-  else
-    peers = p->next;
+  sym_remove(&byname, p->byname);
+  am_remove(&byaddr, p->byaddr);
   DESTROY(p);
 }
 
-/* --- @p_first@, @p_next@ --- *
+/* --- @p_mkiter@ --- *
+ *
+ * Arguments:  @peer_iter *i@ = pointer to an iterator
+ *
+ * Returns:    ---
+ *
+ * Use:                Initializes the iterator.
+ */
+
+void p_mkiter(peer_iter *i) { sym_mkiter(&i->i, &byname); }
+
+/* --- @p_next@ --- *
+ *
+ * Arguments:  @peer_iter *i@ = pointer to an iterator
  *
- * Arguments:  @peer *p@ = a peer block
+ * Returns:    Next peer, or null if at the end.
  *
- * Returns:    @peer_first@ returns the first peer in some ordering;
- *             @peer_next@ returns the peer following a given one in the
- *             same ordering.  Null is returned for the end of the list.
+ * Use:                Returns the next peer.
  */
 
-peer *p_first(void) { return (peers); }
-peer *p_next(peer *p) { return (p->next); }
+peer *p_next(peer_iter *i)
+{
+  peer_byname *pn;
+
+  if ((pn = sym_next(&i->i)) == 0)
+    return (0);
+  return (pn->p);
+}
 
 /*----- That's all, folks -------------------------------------------------*/
index 201b464..63cfb63 100644 (file)
@@ -836,6 +836,12 @@ Adding
 failed for some reason.  A warning should have been emitted explaining
 why.
 .SP
+.BI "peer-addr-exists " address\fR...
+(For
+.BR ADD .)
+There is already a peer with the given
+.IR address .
+.SP
 .BI "peer-exists " peer
 (For
 .BR ADD .)
index 9c9653e..bf59977 100644 (file)
@@ -71,6 +71,7 @@
 #include <mLib/env.h>
 #include <mLib/fdflags.h>
 #include <mLib/fwatch.h>
+#include <mLib/hash.h>
 #include <mLib/macros.h>
 #include <mLib/mdwopt.h>
 #include <mLib/quis.h>
@@ -163,6 +164,18 @@ typedef union addr {
   struct sockaddr_in sin;
 } addr;
 
+/* --- Mapping keyed on addresses --- */
+
+typedef struct addrmap {
+  hash_table t;
+  size_t load;
+} addrmap;
+
+typedef struct addrmap_base {
+  hash_base b;
+  addr a;
+} addrmap_base;
+
 /* --- Sequence number checking --- */
 
 typedef struct seqwin {
@@ -314,8 +327,19 @@ typedef struct peerspec {
   unsigned kxf;                                /* Key exchange flags to set */
 } peerspec;
 
+typedef struct peer_byname {
+  sym_base _b;
+  struct peer *p;
+} peer_byname;
+
+typedef struct peer_byaddr {
+  addrmap_base _b;
+  struct peer *p;
+} peer_byaddr;
+
 typedef struct peer {
-  struct peer *next, *prev;            /* Links to next and previous */
+  peer_byname *byname;                 /* Lookup-by-name block */
+  peer_byaddr *byaddr;                 /* Lookup-by-address block */
   struct ping *pings;                  /* Pings we're waiting for */
   peerspec spec;                       /* Specifications for this peer */
   tunnel *t;                           /* Tunnel for local packets */
@@ -327,6 +351,8 @@ typedef struct peer {
   sel_timer tka;                       /* Timer for keepalives */
 } peer;
 
+typedef struct peer_iter { sym_iter i; } peer_iter;
+
 typedef struct ping {
   struct ping *next, *prev;            /* Links to next and previous */
   peer *p;                             /* Peer so we can free it */
@@ -865,6 +891,60 @@ extern void a_daemon(void);
 
 extern void a_init(const char */*sock*/);
 
+/*----- Mapping with addresses as keys ------------------------------------*/
+
+/* --- @am_create@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *
+ * Returns:    ---
+ *
+ * Use:                Create an address map, properly set up.
+ */
+
+extern void am_create(addrmap */*m*/);
+
+/* --- @am_destroy@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *
+ * Returns:    ---
+ *
+ * Use:                Destroy an address map, throwing away all the entries.
+ */
+
+extern void am_destroy(addrmap */*m*/);
+
+/* --- @am_find@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *             @const addr *a@ = address to look up
+ *             @size_t sz@ = size of block to allocate
+ *             @unsigned *f@ = where to store flags
+ *
+ * Returns:    Pointer to found item, or null.
+ *
+ * Use:                Finds a record with the given IP address, set @*f@ nonzero
+ *             and returns it.  If @sz@ is zero, and no match was found,
+ *             return null; otherwise allocate a new block of @sz@ bytes,
+ *             clear @*f@ to zero and return the block pointer.
+ */
+
+extern void *am_find(addrmap */*m*/, const addr */*a*/,
+                    size_t /*sz*/, unsigned */*f*/);
+
+/* --- @am_remove@ --- *
+ *
+ * Arguments:  @addrmap *m@ = pointer to map
+ *             @void *i@ = pointer to the item
+ *
+ * Returns:    ---
+ *
+ * Use:                Removes an item from the map.
+ */
+
+extern void am_remove(addrmap */*m*/, void */*i*/);
+
 /*----- Peer management ---------------------------------------------------*/
 
 /* --- @p_txstart@ --- *
@@ -1061,6 +1141,17 @@ extern const char *p_name(peer */*p*/);
 
 extern const peerspec *p_spec(peer */*p*/);
 
+/* --- @p_findbyaddr@ --- *
+ *
+ * Arguments:  @const addr *a@ = address to look up
+ *
+ * Returns:    Pointer to the peer block, or null if not found.
+ *
+ * Use:                Finds a peer by address.
+ */
+
+extern peer *p_findbyaddr(const addr */*a*/);
+
 /* --- @p_find@ --- *
  *
  * Arguments:  @const char *name@ = name to look up
@@ -1083,17 +1174,41 @@ extern peer *p_find(const char */*name*/);
 
 extern void p_destroy(peer */*p*/);
 
-/* --- @p_first@, @p_next@ --- *
+/* --- @FOREACH_PEER@ --- *
+ *
+ * Arguments:  @p@ = name to bind to each peer
+ *             @stuff@ = thing to do for each item
+ *
+ * Use:                Does something for each current peer.
+ */
+
+#define FOREACH_PEER(p, stuff) do {                                    \
+  peer_iter i_;                                                                \
+  peer *p;                                                             \
+  for (p_mkiter(&i_); (p = p_next(&i_)) != 0; ) do stuff while (0);    \
+} while (0)
+
+/* --- @p_mkiter@ --- *
+ *
+ * Arguments:  @peer_iter *i@ = pointer to an iterator
+ *
+ * Returns:    ---
+ *
+ * Use:                Initializes the iterator.
+ */
+
+extern void p_mkiter(peer_iter */*i*/);
+
+/* --- @p_next@ --- *
+ *
+ * Arguments:  @peer_iter *i@ = pointer to an iterator
  *
- * Arguments:  @peer *p@ = a peer block
+ * Returns:    Next peer, or null if at the end.
  *
- * Returns:    @peer_first@ returns the first peer in some ordering;
- *             @peer_next@ returns the peer following a given one in the
- *             same ordering.  Null is returned for the end of the list.
+ * Use:                Returns the next peer.
  */
 
-extern peer *p_first(void);
-extern peer *p_next(peer */*p*/);
+extern peer *p_next(peer_iter */*i*/);
 
 /*----- Tunnel drivers ----------------------------------------------------*/