vcs.maemo.org Git - monky/blob - src/libtcp-portmon.h

   1 /* -------------------------------------------------------------------------
   2  * libtcp-portmon.h:  tcp port monitoring library.
   3  *
   4  * Copyright (C) 2005  Philip Kovacs kovacsp3@comcast.net
   5  *
   6  * $Id$
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  21  * --------------------------------------------------------------------------- */
  22
  23 #ifndef LIBTCP_PORTMON_H
  24 #define LIBTCP_PORTMON_H
  25
  26 #include <sys/socket.h>
  27
  28 #include <arpa/inet.h>
  29 #include <netinet/in.h>
  30 #include <netinet/tcp.h>
  31
  32 #include <math.h>
  33 #include <netdb.h>
  34 #include <stdlib.h>
  35 #include <stdio.h>
  36 #include <string.h>
  37
  38 #include "hash.h"
  39
  40 /* ------------------------------------------------------------------------------------------------
  41  * Each port monitor contains a connection hash whose contents changes dynamically as the monitor
  42  * is presented with connections on each update cycle.   This implementation maintains the health
  43  * of this hash by enforcing several rules.  First, the hash cannot contain more items than the
  44  * TCP_CONNECTION_HASH_MAX_LOAD_RATIO permits.  For example, a 512 element hash with a max load of
  45  * 0.5 cannot contain more than 256 connections.  Additional connections are ignored by the monitor.
  46  * The load factor of 0.5 is low enough to keep the hash running at near O(1) performanace at all
  47  * times.  As elements are removed from the hash, the hash slots are tagged vacated, as required
  48  * by open address hashing.  The vacated tags are essential as they enable the hash to find elements
  49  * for which there were collisions during insert (requiring additional probing for an open slot).
  50  * The problem with vacated slots (even though they are reused) is that, as they increase in number,
  51  * esp. past about 1/4 of all slots, the average number of probes the hash has to perform increases
  52  * from O(1) on average to O(n) worst case. To keep the hash healthy, we simply rebuild it when the
  53  * percentage of vacated slots gets too high (above TCP_CONNECTION_HASH_MAX_VACATED_RATIO).
  54  * Rebuilding the hash takes O(n) on the number of elements, but it well worth it as it keeps the
  55  * hash running at an average access time of O(1).
  56  * ------------------------------------------------------------------------------------------------*/
  57
  58 #define TCP_CONNECTION_HASH_SIZE_DEFAULT 512            /* connection hash size default -- must be a power of two */
  59 #define TCP_CONNECTION_HASH_SIZE_MAX 65536              /* connection hash size maximum -- must be a power of two */
  60 #define TCP_CONNECTION_HASH_MAX_LOAD_RATIO 0.5          /* disallow inserts after this load ratio is exceeded */
  61 #define TCP_CONNECTION_HASH_MAX_VACATED_RATIO 0.25      /* rebalance hash after this ratio of vacated slots is exceeded */
  62 #define TCP_CONNECTION_STARTING_AGE 1                   /* connection deleted if unseen again after this # of refreshes */
  63
  64 /* ----------------------------------------------------------------------------------------
  65  * The tcp port monitor collection also contains a hash to track the monitors it contains.
  66  * This hash, unlike the connection hash describes above, is not very dynamic.  Clients of
  67  * this library typically create a fixed number of monitors and let them run until program
  68  * termination.  For this reason, I haven't included any hash rebuilding code as is done
  69  * above.  You may store up to TCP_MONITOR_HASH_SIZE_MAX monitors in this hash, but you
  70  * should remember that keeping the load low (e.g. 0.5) keeps the monitor lookups at O(1).
  71  * ----------------------------------------------------------------------------------------*/
  72
  73 #define TCP_MONITOR_HASH_SIZE_DEFAULT 32                /* monitor hash size default -- must be a power of two */
  74 #define TCP_MONITOR_HASH_SIZE_MAX 512                   /* monitor hash size maximum -- must be a power of two */
  75 #define TCP_MONITOR_HASH_MAX_LOAD_RATIO 0.5             /* disallow new monitors after this load ratio is exceeded */
  76
  77 /* -------------------------------------------------------------------
  78  * IMPLEMENTATION INTERFACE
  79  *
  80  * Implementation-specific interface begins here.  Clients should not
  81  * manipulate these structures directly, nor call the defined helper
  82  * functions.  Use the "Client interface" functions defined at bottom.
  83  * ------------------------------------------------------------------- */
  84
  85 /* The inventory of peekable items within the port monitor. */
  86 enum tcp_port_monitor_peekables { COUNT=0, REMOTEIP, REMOTEHOST, REMOTEPORT, LOCALIP, LOCALHOST, LOCALPORT, LOCALSERVICE };
  87
  88 /* ------------------------------------------------------------------------
  89  * A single tcp connection
  90  *
  91  * The age variable provides the mechanism for removing connections if they
  92  * are not seen again in subsequent update cycles.
  93  * ------------------------------------------------------------------------ */
  94 typedef struct _tcp_connection_t {
  95         in_addr_t local_addr;
  96         in_port_t local_port;
  97         in_addr_t remote_addr;
  98         in_port_t remote_port;
  99         int age;
 100 } tcp_connection_t;
 101
 102 /* ----------------------------------
 103  * Copy a connection
 104  *
 105  * Returns 0 on success, -1 otherwise
 106  * ----------------------------------*/
 107 int copy_tcp_connection(
 108         tcp_connection_t *                      /* p_dest_connection */,
 109         const tcp_connection_t *                /* p_source_connection */
 110         );
 111
 112 /* ------------------------------------------------------------------------
 113  * A tcp connection node/list
 114  *
 115  * Connections within each monitor are stored in a double-linked list.
 116  * ------------------------------------------------------------------------ */
 117 typedef struct _tcp_connection_node_t {
 118         tcp_connection_t connection;
 119         struct _tcp_connection_node_t * p_prev;
 120         struct _tcp_connection_node_t * p_next;
 121 } tcp_connection_node_t;
 122
 123 typedef struct _tcp_connection_list_t {
 124         tcp_connection_node_t * p_head;
 125         tcp_connection_node_t * p_tail;
 126 } tcp_connection_list_t;
 127
 128 /* --------------
 129  * A port monitor
 130  * -------------- */
 131 typedef struct _tcp_port_monitor_t {
 132         in_port_t port_range_begin;
 133         in_port_t port_range_end;               /* begin = end to monitor a single port */
 134         tcp_connection_list_t connection_list;  /* list of connections for this monitor */
 135         hash_table_t hash;                      /* hash table contains pointers into monitor's connection list */
 136         tcp_connection_t **p_peek;              /* array of connection pointers for O(1) peeking by index */
 137 } tcp_port_monitor_t;
 138
 139 /* -----------------------------------------------------------------------------
 140  * Open-addressed hash implementation requires that we supply two hash functions
 141  * and a match function to compare two hash elements for identity.
 142  * ----------------------------------------------------------------------------- */
 143
 144 /* --------------------------------------------------
 145  * Functions to hash the connections within a monitor
 146  * --------------------------------------------------*/
 147
 148 /* First connection hash function */
 149 int connection_hash_function_1( const void * /* p_data */ );
 150
 151 /* Second connection hash function */
 152 int connection_hash_function_2( const void * /* p_data */ );
 153
 154 /* Connection match function returns non-zero if hash elements are identical. */
 155 int connection_match_function( const void * /* p_data1 */, const void * /* p_data2 */ );
 156
 157 /* --------------------------------------------------
 158  * Functions to hash the monitors within a collection
 159  * --------------------------------------------------*/
 160
 161 /* First monitor hash function */
 162 int monitor_hash_function_1( const void * /* p_data */ );
 163
 164 /* Second monitor hash function */
 165 int monitor_hash_function_2( const void * /* p_data */ );
 166
 167 /* Monitor match function returns non-zero if hash elements are identical. */
 168 int monitor_match_function( const void * /* p_data1 */, const void * /* p_data2 */ );
 169
 170 /* ------------------------
 171  * A port monitor node/list
 172  * ------------------------ */
 173 typedef struct _tcp_port_monitor_node_t {
 174         tcp_port_monitor_t * p_monitor;
 175         struct _tcp_port_monitor_node_t *p_next;
 176 } tcp_port_monitor_node_t;
 177
 178 typedef struct __tcp_port_monitor_list_t {
 179         tcp_port_monitor_node_t * p_head;
 180         tcp_port_monitor_node_t * p_tail;
 181 } tcp_port_monitor_list_t;
 182
 183 /* ---------------------------------------
 184  * A port monitor utility function typedef
 185  * ---------------------------------------*/
 186 typedef void (*tcp_port_monitor_function_ptr_t)( tcp_port_monitor_t * /* p_monitor */, void * /* p_void */ );
 187
 188 /* ---------------------------------------------------------------------------
 189  * Port monitor utility functions implementing tcp_port_monitor_function_ptr_t
 190  * ---------------------------------------------------------------------------*/
 191 void destroy_tcp_port_monitor(
 192         tcp_port_monitor_t *                    /* p_monitor */,
 193         void *                                  /* p_void (use NULL for this function) */
 194         );
 195
 196 void age_tcp_port_monitor(
 197         tcp_port_monitor_t *                    /* p_monitor */,
 198         void *                                  /* p_void (use NULL for this function) */
 199         );
 200
 201 void maintain_tcp_port_monitor_hash(
 202         tcp_port_monitor_t *                    /* p_monitor */,
 203         void *                                  /* p_void (use NULL for this function) */
 204         );
 205
 206 void rebuild_tcp_port_monitor_peek_table(
 207         tcp_port_monitor_t *                    /* p_monitor */,
 208         void *                                  /* p_void (use NULL for this function) */
 209         );
 210
 211 void show_connection_to_tcp_port_monitor(
 212         tcp_port_monitor_t *                    /* p_monitor */,
 213         void *                                  /* p_connection (client should cast) */
 214         );
 215
 216 /* -----------------------------
 217  * A tcp port monitor collection
 218  * -----------------------------*/
 219 typedef struct _tcp_port_monitor_collection_t {
 220         tcp_port_monitor_list_t monitor_list;   /* list of monitors for this collection */
 221         hash_table_t hash;                      /* hash table contains pointers into collection's monitor list */
 222 } tcp_port_monitor_collection_t;
 223
 224 /* ---------------------------------------------------------------------------------------
 225  * Apply a tcp_port_monitor_function_ptr_t function to each port monitor in the collection.
 226  * ---------------------------------------------------------------------------------------*/
 227 void for_each_tcp_port_monitor_in_collection(
 228         tcp_port_monitor_collection_t *         /* p_collection */,
 229         tcp_port_monitor_function_ptr_t         /* p_function */,
 230         void *                                  /* p_function_args (for user arguments) */
 231         );
 232
 233 /* ----------------------------------------------------------------------------------------
 234  * Calculate an efficient hash size based on the desired number of elements and load factor.
 235  * ---------------------------------------------------------------------------------------- */
 236 int calc_efficient_hash_size(
 237         int                                     /* min_elements, the minimum number of elements to store */,
 238         int                                     /* max_hash_size, the maximum permissible hash size */,
 239         double                                  /* max_load_factor, the fractional load we wish not to exceed, e.g. 0.5 */
 240         );
 241
 242 /* ----------------------------------------------------------------------
 243  * CLIENT INTERFACE
 244  *
 245  * Clients should call only those functions below this line.
 246  * ---------------------------------------------------------------------- */
 247
 248 /* struct to hold monitor creation arguments */
 249 typedef struct _tcp_port_monitor_args_t {
 250         int     min_port_monitor_connections;   /* monitor must support tracking at least this many connections */
 251 } tcp_port_monitor_args_t;
 252
 253
 254 /* struct to hold collection creation arguments */
 255 typedef struct _tcp_port_monitor_collection_args_t {
 256         int     min_port_monitors;              /* collection must support creation of at least this many monitors */
 257 } tcp_port_monitor_collection_args_t;
 258
 259 /* ----------------------------------
 260  * Client operations on port monitors
 261  * ---------------------------------- */
 262
 263 /* Clients should first try to "find_tcp_port_monitor" before creating one
 264    so that there are no redundant monitors. */
 265 tcp_port_monitor_t * create_tcp_port_monitor(
 266         in_port_t                               /* port_range_begin */,
 267         in_port_t                               /* port_range_end */,
 268         tcp_port_monitor_args_t *               /* p_creation_args, NULL ok for library defaults */
 269         );
 270
 271 /* Clients use this function to get connection data from the indicated port monitor.
 272    The requested monitor value is copied into a client-supplied char buffer.
 273    Returns 0 on success, -1 otherwise. */
 274 int peek_tcp_port_monitor(
 275         const tcp_port_monitor_t *              /* p_monitor */,
 276         int                                     /* item, ( item of interest, from tcp_port_monitor_peekables enum ) */,
 277         int                                     /* connection_index, ( 0 to number of connections in monitor - 1 )*/,
 278         char *                                  /* p_buffer, buffer to receive requested value */,
 279         size_t                                  /* buffer_size, size of p_buffer */
 280         );
 281
 282 /* --------------------------------
 283  * Client operations on collections
 284  * -------------------------------- */
 285
 286 /* Create a monitor collection.  Do this one first. */
 287 tcp_port_monitor_collection_t * create_tcp_port_monitor_collection(
 288         tcp_port_monitor_collection_args_t *    /* p_creation_args, NULL ok for library defaults */
 289         );
 290
 291 /* Destroy the monitor collection (and everything it contains).  Do this one last. */
 292 void destroy_tcp_port_monitor_collection(
 293         tcp_port_monitor_collection_t *         /* p_collection */
 294         );
 295
 296 /* Updates the tcp statitics for all monitors within a collection */
 297 void update_tcp_port_monitor_collection(
 298         tcp_port_monitor_collection_t *         /* p_collection */
 299         );
 300
 301 /* After clients create a monitor, use this to add it to the collection.
 302    Returns 0 on success, -1 otherwise. */
 303 int insert_tcp_port_monitor_into_collection(
 304         tcp_port_monitor_collection_t *         /* p_collection */,
 305         tcp_port_monitor_t *                    /* p_monitor */
 306         );
 307
 308 /* Clients need a way to find monitors */
 309 tcp_port_monitor_t * find_tcp_port_monitor(
 310         const tcp_port_monitor_collection_t *   /* p_collection */,
 311         in_port_t                               /* port_range_begin */,
 312         in_port_t                               /* port_range_end */
 313         );
 314
 315 #endif