From c8e02c8a4947afa4f9ac20e78a3c8808b3945804 Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Mon, 8 Dec 2008 10:11:57 +0000 Subject: [PATCH] server/peer: Use hash tables to find peer records. Organization: Straylight/Edgeware From: Mark Wooding --- server/Makefile.am | 1 + server/addrmap.c | 172 ++++++++++++++++++++++++++++++++++++++++ server/admin.c | 14 ++-- server/peer.c | 121 +++++++++++++++++----------- server/tripe-admin.5.in | 6 ++ server/tripe.h | 131 ++++++++++++++++++++++++++++-- 6 files changed, 381 insertions(+), 64 deletions(-) create mode 100644 server/addrmap.c diff --git a/server/Makefile.am b/server/Makefile.am index fe904419..e033ab0c 100644 --- a/server/Makefile.am +++ b/server/Makefile.am @@ -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 index 00000000..0ab72e97 --- /dev/null +++ b/server/addrmap.c @@ -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 -------------------------------------------------*/ diff --git a/server/admin.c b/server/admin.c index 73c71070..288a64ff 100644 --- a/server/admin.c +++ b/server/admin.c @@ -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); } diff --git a/server/peer.c b/server/peer.c index 675ceff8..e57c6ba4 100644 --- a/server/peer.c +++ b/server/peer.c @@ -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 -------------------------------------------------*/ diff --git a/server/tripe-admin.5.in b/server/tripe-admin.5.in index 201b464b..63cfb635 100644 --- a/server/tripe-admin.5.in +++ b/server/tripe-admin.5.in @@ -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 .) diff --git a/server/tripe.h b/server/tripe.h index 9c9653e0..bf599774 100644 --- a/server/tripe.h +++ b/server/tripe.h @@ -71,6 +71,7 @@ #include #include #include +#include #include #include #include @@ -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 ----------------------------------------------------*/ -- [mdw]