The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/netgraph/ng_ppp.c

Version: -  FREEBSD  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

    1 
    2 /*
    3  * ng_ppp.c
    4  *
    5  * Copyright (c) 1996-2000 Whistle Communications, Inc.
    6  * All rights reserved.
    7  * 
    8  * Subject to the following obligations and disclaimer of warranty, use and
    9  * redistribution of this software, in source or object code forms, with or
   10  * without modifications are expressly permitted by Whistle Communications;
   11  * provided, however, that:
   12  * 1. Any and all reproductions of the source or object code must include the
   13  *    copyright notice above and the following disclaimer of warranties; and
   14  * 2. No rights are granted, in any manner or form, to use Whistle
   15  *    Communications, Inc. trademarks, including the mark "WHISTLE
   16  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
   17  *    such appears in the above copyright notice or in the software.
   18  * 
   19  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
   20  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
   21  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
   22  * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
   23  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
   24  * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
   25  * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
   26  * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
   27  * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
   28  * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
   29  * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
   30  * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
   31  * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
   32  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
   33  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
   34  * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
   35  * OF SUCH DAMAGE.
   36  *
   37  * Author: Archie Cobbs <archie@freebsd.org>
   38  *
   39  * $FreeBSD: stable/4/sys/netgraph/ng_ppp.c 138753 2004-12-12 19:37:52Z archie $
   40  * $Whistle: ng_ppp.c,v 1.24 1999/11/01 09:24:52 julian Exp $
   41  */
   42 
   43 /*
   44  * PPP node type.
   45  */
   46 
   47 #include <sys/param.h>
   48 #include <sys/systm.h>
   49 #include <sys/kernel.h>
   50 #include <sys/time.h>
   51 #include <sys/mbuf.h>
   52 #include <sys/malloc.h>
   53 #include <sys/errno.h>
   54 #include <sys/ctype.h>
   55 
   56 #include <machine/limits.h>
   57 
   58 #include <netgraph/ng_message.h>
   59 #include <netgraph/netgraph.h>
   60 #include <netgraph/ng_parse.h>
   61 #include <netgraph/ng_ppp.h>
   62 #include <netgraph/ng_vjc.h>
   63 
   64 #define PROT_VALID(p)           (((p) & 0x0101) == 0x0001)
   65 #define PROT_COMPRESSABLE(p)    (((p) & 0xff00) == 0x0000)
   66 
   67 /* Some PPP protocol numbers we're interested in */
   68 #define PROT_APPLETALK          0x0029
   69 #define PROT_COMPD              0x00fd
   70 #define PROT_CRYPTD             0x0053
   71 #define PROT_IP                 0x0021
   72 #define PROT_IPV6               0x0057
   73 #define PROT_IPX                0x002b
   74 #define PROT_LCP                0xc021
   75 #define PROT_MP                 0x003d
   76 #define PROT_VJCOMP             0x002d
   77 #define PROT_VJUNCOMP           0x002f
   78 
   79 /* Multilink PPP definitions */
   80 #define MP_MIN_MRRU             1500            /* per RFC 1990 */
   81 #define MP_INITIAL_SEQ          0               /* per RFC 1990 */
   82 #define MP_MIN_LINK_MRU         32
   83 
   84 #define MP_SHORT_SEQ_MASK       0x00000fff      /* short seq # mask */
   85 #define MP_SHORT_SEQ_HIBIT      0x00000800      /* short seq # high bit */
   86 #define MP_SHORT_FIRST_FLAG     0x00008000      /* first fragment in frame */
   87 #define MP_SHORT_LAST_FLAG      0x00004000      /* last fragment in frame */
   88 
   89 #define MP_LONG_SEQ_MASK        0x00ffffff      /* long seq # mask */
   90 #define MP_LONG_SEQ_HIBIT       0x00800000      /* long seq # high bit */
   91 #define MP_LONG_FIRST_FLAG      0x80000000      /* first fragment in frame */
   92 #define MP_LONG_LAST_FLAG       0x40000000      /* last fragment in frame */
   93 
   94 #define MP_NOSEQ                0x7fffffff      /* impossible sequence number */
   95 
   96 /* Sign extension of MP sequence numbers */
   97 #define MP_SHORT_EXTEND(s)      (((s) & MP_SHORT_SEQ_HIBIT) ?           \
   98                                     ((s) | ~MP_SHORT_SEQ_MASK)          \
   99                                     : ((s) & MP_SHORT_SEQ_MASK))
  100 #define MP_LONG_EXTEND(s)       (((s) & MP_LONG_SEQ_HIBIT) ?            \
  101                                     ((s) | ~MP_LONG_SEQ_MASK)           \
  102                                     : ((s) & MP_LONG_SEQ_MASK))
  103 
  104 /* Comparision of MP sequence numbers. Note: all sequence numbers
  105    except priv->xseq are stored with the sign bit extended. */
  106 #define MP_SHORT_SEQ_DIFF(x,y)  MP_SHORT_EXTEND((x) - (y))
  107 #define MP_LONG_SEQ_DIFF(x,y)   MP_LONG_EXTEND((x) - (y))
  108 
  109 #define MP_RECV_SEQ_DIFF(priv,x,y)                                      \
  110                                 ((priv)->conf.recvShortSeq ?            \
  111                                     MP_SHORT_SEQ_DIFF((x), (y)) :       \
  112                                     MP_LONG_SEQ_DIFF((x), (y)))
  113 
  114 /* Increment receive sequence number */
  115 #define MP_NEXT_RECV_SEQ(priv,seq)                                      \
  116                                 ((priv)->conf.recvShortSeq ?            \
  117                                     MP_SHORT_EXTEND((seq) + 1) :        \
  118                                     MP_LONG_EXTEND((seq) + 1))
  119 
  120 /* Don't fragment transmitted packets smaller than this */
  121 #define MP_MIN_FRAG_LEN         6
  122 
  123 /* Maximum fragment reasssembly queue length */
  124 #define MP_MAX_QUEUE_LEN        128
  125 
  126 /* Fragment queue scanner period */
  127 #define MP_FRAGTIMER_INTERVAL   (hz/2)
  128 
  129 /* We store incoming fragments this way */
  130 struct ng_ppp_frag {
  131         int                             seq;            /* fragment seq# */
  132         u_char                          first;          /* First in packet? */
  133         u_char                          last;           /* Last in packet? */
  134         struct timeval                  timestamp;      /* time of reception */
  135         struct mbuf                     *data;          /* Fragment data */
  136         meta_p                          meta;           /* Fragment meta */
  137         CIRCLEQ_ENTRY(ng_ppp_frag)      f_qent;         /* Fragment queue */
  138 };
  139 
  140 /* We use integer indicies to refer to the non-link hooks */
  141 static const char *const ng_ppp_hook_names[] = {
  142         NG_PPP_HOOK_ATALK,
  143 #define HOOK_INDEX_ATALK                0
  144         NG_PPP_HOOK_BYPASS,
  145 #define HOOK_INDEX_BYPASS               1
  146         NG_PPP_HOOK_COMPRESS,
  147 #define HOOK_INDEX_COMPRESS             2
  148         NG_PPP_HOOK_ENCRYPT,
  149 #define HOOK_INDEX_ENCRYPT              3
  150         NG_PPP_HOOK_DECOMPRESS,
  151 #define HOOK_INDEX_DECOMPRESS           4
  152         NG_PPP_HOOK_DECRYPT,
  153 #define HOOK_INDEX_DECRYPT              5
  154         NG_PPP_HOOK_INET,
  155 #define HOOK_INDEX_INET                 6
  156         NG_PPP_HOOK_IPX,
  157 #define HOOK_INDEX_IPX                  7
  158         NG_PPP_HOOK_VJC_COMP,
  159 #define HOOK_INDEX_VJC_COMP             8
  160         NG_PPP_HOOK_VJC_IP,
  161 #define HOOK_INDEX_VJC_IP               9
  162         NG_PPP_HOOK_VJC_UNCOMP,
  163 #define HOOK_INDEX_VJC_UNCOMP           10
  164         NG_PPP_HOOK_VJC_VJIP,
  165 #define HOOK_INDEX_VJC_VJIP             11
  166         NG_PPP_HOOK_IPV6,
  167 #define HOOK_INDEX_IPV6                 12
  168         NULL
  169 #define HOOK_INDEX_MAX                  13
  170 };
  171 
  172 /* We store index numbers in the hook private pointer. The HOOK_INDEX()
  173    for a hook is either the index (above) for normal hooks, or the ones
  174    complement of the link number for link hooks. */
  175 #define HOOK_INDEX(hook)        (*((int16_t *) &(hook)->private))
  176 
  177 /* Per-link private information */
  178 struct ng_ppp_link {
  179         struct ng_ppp_link_conf conf;           /* link configuration */
  180         hook_p                  hook;           /* connection to link data */
  181         int32_t                 seq;            /* highest rec'd seq# - MSEQ */
  182         struct timeval          lastWrite;      /* time of last write */
  183         int                     bytesInQueue;   /* bytes in the output queue */
  184         struct ng_ppp_link_stat stats;          /* Link stats */
  185 };
  186 
  187 /* Total per-node private information */
  188 struct ng_ppp_private {
  189         struct ng_ppp_bund_conf conf;                   /* bundle config */
  190         struct ng_ppp_link_stat bundleStats;            /* bundle stats */
  191         struct ng_ppp_link      links[NG_PPP_MAX_LINKS];/* per-link info */
  192         int32_t                 xseq;                   /* next out MP seq # */
  193         int32_t                 mseq;                   /* min links[i].seq */
  194         u_char                  vjCompHooked;           /* VJ comp hooked up? */
  195         u_char                  allLinksEqual;          /* all xmit the same? */
  196         u_char                  timerActive;            /* frag timer active? */
  197         u_int                   numActiveLinks;         /* how many links up */
  198         int                     activeLinks[NG_PPP_MAX_LINKS];  /* indicies */
  199         u_int                   lastLink;               /* for round robin */
  200         hook_p                  hooks[HOOK_INDEX_MAX];  /* non-link hooks */
  201         CIRCLEQ_HEAD(ng_ppp_fraglist, ng_ppp_frag)      /* fragment queue */
  202                                 frags;
  203         int                     qlen;                   /* fraq queue length */
  204         struct callout_handle   fragTimer;              /* fraq queue check */
  205 };
  206 typedef struct ng_ppp_private *priv_p;
  207 
  208 /* Netgraph node methods */
  209 static ng_constructor_t ng_ppp_constructor;
  210 static ng_rcvmsg_t      ng_ppp_rcvmsg;
  211 static ng_shutdown_t    ng_ppp_rmnode;
  212 static ng_newhook_t     ng_ppp_newhook;
  213 static ng_rcvdata_t     ng_ppp_rcvdata;
  214 static ng_disconnect_t  ng_ppp_disconnect;
  215 
  216 /* Helper functions */
  217 static int      ng_ppp_input(node_p node, int bypass,
  218                         int linkNum, struct mbuf *m, meta_p meta);
  219 static int      ng_ppp_output(node_p node, int bypass, int proto,
  220                         int linkNum, struct mbuf *m, meta_p meta);
  221 static int      ng_ppp_mp_input(node_p node, int linkNum,
  222                         struct mbuf *m, meta_p meta);
  223 static int      ng_ppp_check_packet(node_p node);
  224 static void     ng_ppp_get_packet(node_p node, struct mbuf **mp, meta_p *metap);
  225 static int      ng_ppp_frag_process(node_p node);
  226 static int      ng_ppp_frag_trim(node_p node);
  227 static void     ng_ppp_frag_timeout(void *arg);
  228 static void     ng_ppp_frag_checkstale(node_p node);
  229 static void     ng_ppp_frag_reset(node_p node);
  230 static int      ng_ppp_mp_output(node_p node, struct mbuf *m, meta_p meta);
  231 static void     ng_ppp_mp_strategy(node_p node, int len, int *distrib);
  232 static int      ng_ppp_intcmp(const void *v1, const void *v2);
  233 static struct   mbuf *ng_ppp_addproto(struct mbuf *m, int proto, int compOK);
  234 static struct   mbuf *ng_ppp_prepend(struct mbuf *m, const void *buf, int len);
  235 static int      ng_ppp_config_valid(node_p node,
  236                         const struct ng_ppp_node_conf *newConf);
  237 static void     ng_ppp_update(node_p node, int newConf);
  238 static void     ng_ppp_start_frag_timer(node_p node);
  239 static void     ng_ppp_stop_frag_timer(node_p node);
  240 
  241 /* Parse type for struct ng_ppp_mp_state_type */
  242 static const struct ng_parse_fixedarray_info ng_ppp_rseq_array_info = {
  243         &ng_parse_hint32_type,
  244         NG_PPP_MAX_LINKS
  245 };
  246 static const struct ng_parse_type ng_ppp_rseq_array_type = {
  247         &ng_parse_fixedarray_type,
  248         &ng_ppp_rseq_array_info,
  249 };
  250 static const struct ng_parse_struct_field ng_ppp_mp_state_type_fields[]
  251         = NG_PPP_MP_STATE_TYPE_INFO(&ng_ppp_rseq_array_type);
  252 static const struct ng_parse_type ng_ppp_mp_state_type = {
  253         &ng_parse_struct_type,
  254         &ng_ppp_mp_state_type_fields
  255 };
  256 
  257 /* Parse type for struct ng_ppp_link_conf */
  258 static const struct ng_parse_struct_field ng_ppp_link_type_fields[]
  259         = NG_PPP_LINK_TYPE_INFO;
  260 static const struct ng_parse_type ng_ppp_link_type = {
  261         &ng_parse_struct_type,
  262         &ng_ppp_link_type_fields
  263 };
  264 
  265 /* Parse type for struct ng_ppp_bund_conf */
  266 static const struct ng_parse_struct_field ng_ppp_bund_type_fields[]
  267         = NG_PPP_BUND_TYPE_INFO;
  268 static const struct ng_parse_type ng_ppp_bund_type = {
  269         &ng_parse_struct_type,
  270         &ng_ppp_bund_type_fields
  271 };
  272 
  273 /* Parse type for struct ng_ppp_node_conf */
  274 static const struct ng_parse_fixedarray_info ng_ppp_array_info = {
  275         &ng_ppp_link_type,
  276         NG_PPP_MAX_LINKS
  277 };
  278 static const struct ng_parse_type ng_ppp_link_array_type = {
  279         &ng_parse_fixedarray_type,
  280         &ng_ppp_array_info,
  281 };
  282 static const struct ng_parse_struct_field ng_ppp_conf_type_fields[]
  283         = NG_PPP_CONFIG_TYPE_INFO(&ng_ppp_bund_type, &ng_ppp_link_array_type);
  284 static const struct ng_parse_type ng_ppp_conf_type = {
  285         &ng_parse_struct_type,
  286         &ng_ppp_conf_type_fields
  287 };
  288 
  289 /* Parse type for struct ng_ppp_link_stat */
  290 static const struct ng_parse_struct_field ng_ppp_stats_type_fields[]
  291         = NG_PPP_STATS_TYPE_INFO;
  292 static const struct ng_parse_type ng_ppp_stats_type = {
  293         &ng_parse_struct_type,
  294         &ng_ppp_stats_type_fields
  295 };
  296 
  297 /* List of commands and how to convert arguments to/from ASCII */
  298 static const struct ng_cmdlist ng_ppp_cmds[] = {
  299         {
  300           NGM_PPP_COOKIE,
  301           NGM_PPP_SET_CONFIG,
  302           "setconfig",
  303           &ng_ppp_conf_type,
  304           NULL
  305         },
  306         {
  307           NGM_PPP_COOKIE,
  308           NGM_PPP_GET_CONFIG,
  309           "getconfig",
  310           NULL,
  311           &ng_ppp_conf_type
  312         },
  313         {
  314           NGM_PPP_COOKIE,
  315           NGM_PPP_GET_MP_STATE,
  316           "getmpstate",
  317           NULL,
  318           &ng_ppp_mp_state_type
  319         },
  320         {
  321           NGM_PPP_COOKIE,
  322           NGM_PPP_GET_LINK_STATS,
  323           "getstats",
  324           &ng_parse_int16_type,
  325           &ng_ppp_stats_type
  326         },
  327         {
  328           NGM_PPP_COOKIE,
  329           NGM_PPP_CLR_LINK_STATS,
  330           "clrstats",
  331           &ng_parse_int16_type,
  332           NULL
  333         },
  334         {
  335           NGM_PPP_COOKIE,
  336           NGM_PPP_GETCLR_LINK_STATS,
  337           "getclrstats",
  338           &ng_parse_int16_type,
  339           &ng_ppp_stats_type
  340         },
  341         { 0 }
  342 };
  343 
  344 /* Node type descriptor */
  345 static struct ng_type ng_ppp_typestruct = {
  346         NG_VERSION,
  347         NG_PPP_NODE_TYPE,
  348         NULL,
  349         ng_ppp_constructor,
  350         ng_ppp_rcvmsg,
  351         ng_ppp_rmnode,
  352         ng_ppp_newhook,
  353         NULL,
  354         NULL,
  355         ng_ppp_rcvdata,
  356         ng_ppp_rcvdata,
  357         ng_ppp_disconnect,
  358         ng_ppp_cmds
  359 };
  360 NETGRAPH_INIT(ppp, &ng_ppp_typestruct);
  361 
  362 static int *compareLatencies;                   /* hack for ng_ppp_intcmp() */
  363 
  364 /* Address and control field header */
  365 static const u_char ng_ppp_acf[2] = { 0xff, 0x03 };
  366 
  367 /* Maximum time we'll let a complete incoming packet sit in the queue */
  368 static const struct timeval ng_ppp_max_staleness = { 2, 0 };    /* 2 seconds */
  369 
  370 #define ERROUT(x)       do { error = (x); goto done; } while (0)
  371 
  372 /************************************************************************
  373                         NETGRAPH NODE STUFF
  374  ************************************************************************/
  375 
  376 /*
  377  * Node type constructor
  378  */
  379 static int
  380 ng_ppp_constructor(node_p *nodep)
  381 {
  382         priv_p priv;
  383         int i, error;
  384 
  385         /* Allocate private structure */
  386         MALLOC(priv, priv_p, sizeof(*priv), M_NETGRAPH, M_NOWAIT);
  387         if (priv == NULL)
  388                 return (ENOMEM);
  389         bzero(priv, sizeof(*priv));
  390 
  391         /* Call generic node constructor */
  392         if ((error = ng_make_node_common(&ng_ppp_typestruct, nodep))) {
  393                 FREE(priv, M_NETGRAPH);
  394                 return (error);
  395         }
  396         (*nodep)->private = priv;
  397 
  398         /* Initialize state */
  399         CIRCLEQ_INIT(&priv->frags);
  400         for (i = 0; i < NG_PPP_MAX_LINKS; i++)
  401                 priv->links[i].seq = MP_NOSEQ;
  402         callout_handle_init(&priv->fragTimer);
  403 
  404         /* Done */
  405         return (0);
  406 }
  407 
  408 /*
  409  * Give our OK for a hook to be added
  410  */
  411 static int
  412 ng_ppp_newhook(node_p node, hook_p hook, const char *name)
  413 {
  414         const priv_p priv = node->private;
  415         int linkNum = -1;
  416         hook_p *hookPtr = NULL;
  417         int hookIndex = -1;
  418 
  419         /* Figure out which hook it is */
  420         if (strncmp(name, NG_PPP_HOOK_LINK_PREFIX,      /* a link hook? */
  421             strlen(NG_PPP_HOOK_LINK_PREFIX)) == 0) {
  422                 const char *cp;
  423                 char *eptr;
  424 
  425                 cp = name + strlen(NG_PPP_HOOK_LINK_PREFIX);
  426                 if (!isdigit(*cp) || (cp[0] == '' && cp[1] != '\0'))
  427                         return (EINVAL);
  428                 linkNum = (int)strtoul(cp, &eptr, 10);
  429                 if (*eptr != '\0' || linkNum < 0 || linkNum >= NG_PPP_MAX_LINKS)
  430                         return (EINVAL);
  431                 hookPtr = &priv->links[linkNum].hook;
  432                 hookIndex = ~linkNum;
  433         } else {                                /* must be a non-link hook */
  434                 int i;
  435 
  436                 for (i = 0; ng_ppp_hook_names[i] != NULL; i++) {
  437                         if (strcmp(name, ng_ppp_hook_names[i]) == 0) {
  438                                 hookPtr = &priv->hooks[i];
  439                                 hookIndex = i;
  440                                 break;
  441                         }
  442                 }
  443                 if (ng_ppp_hook_names[i] == NULL)
  444                         return (EINVAL);        /* no such hook */
  445         }
  446 
  447         /* See if hook is already connected */
  448         if (*hookPtr != NULL)
  449                 return (EISCONN);
  450 
  451         /* Disallow more than one link unless multilink is enabled */
  452         if (linkNum != -1 && priv->links[linkNum].conf.enableLink
  453             && !priv->conf.enableMultilink && priv->numActiveLinks >= 1)
  454                 return (ENODEV);
  455 
  456         /* OK */
  457         *hookPtr = hook;
  458         HOOK_INDEX(hook) = hookIndex;
  459         ng_ppp_update(node, 0);
  460         return (0);
  461 }
  462 
  463 /*
  464  * Receive a control message
  465  */
  466 static int
  467 ng_ppp_rcvmsg(node_p node, struct ng_mesg *msg,
  468               const char *raddr, struct ng_mesg **rptr)
  469 {
  470         const priv_p priv = node->private;
  471         struct ng_mesg *resp = NULL;
  472         int error = 0;
  473 
  474         switch (msg->header.typecookie) {
  475         case NGM_PPP_COOKIE:
  476                 switch (msg->header.cmd) {
  477                 case NGM_PPP_SET_CONFIG:
  478                     {
  479                         struct ng_ppp_node_conf *const conf =
  480                             (struct ng_ppp_node_conf *)msg->data;
  481                         int i;
  482 
  483                         /* Check for invalid or illegal config */
  484                         if (msg->header.arglen != sizeof(*conf))
  485                                 ERROUT(EINVAL);
  486                         if (!ng_ppp_config_valid(node, conf))
  487                                 ERROUT(EINVAL);
  488 
  489                         /* Copy config */
  490                         priv->conf = conf->bund;
  491                         for (i = 0; i < NG_PPP_MAX_LINKS; i++)
  492                                 priv->links[i].conf = conf->links[i];
  493                         ng_ppp_update(node, 1);
  494                         break;
  495                     }
  496                 case NGM_PPP_GET_CONFIG:
  497                     {
  498                         struct ng_ppp_node_conf *conf;
  499                         int i;
  500 
  501                         NG_MKRESPONSE(resp, msg, sizeof(*conf), M_NOWAIT);
  502                         if (resp == NULL)
  503                                 ERROUT(ENOMEM);
  504                         conf = (struct ng_ppp_node_conf *)resp->data;
  505                         conf->bund = priv->conf;
  506                         for (i = 0; i < NG_PPP_MAX_LINKS; i++)
  507                                 conf->links[i] = priv->links[i].conf;
  508                         break;
  509                     }
  510                 case NGM_PPP_GET_MP_STATE:
  511                     {
  512                         struct ng_ppp_mp_state *info;
  513                         int i;
  514 
  515                         NG_MKRESPONSE(resp, msg, sizeof(*info), M_NOWAIT);
  516                         if (resp == NULL)
  517                                 ERROUT(ENOMEM);
  518                         info = (struct ng_ppp_mp_state *)resp->data;
  519                         bzero(info, sizeof(*info));
  520                         for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
  521                                 if (priv->links[i].seq != MP_NOSEQ)
  522                                         info->rseq[i] = priv->links[i].seq;
  523                         }
  524                         info->mseq = priv->mseq;
  525                         info->xseq = priv->xseq;
  526                         break;
  527                     }
  528                 case NGM_PPP_GET_LINK_STATS:
  529                 case NGM_PPP_CLR_LINK_STATS:
  530                 case NGM_PPP_GETCLR_LINK_STATS:
  531                     {
  532                         struct ng_ppp_link_stat *stats;
  533                         u_int16_t linkNum;
  534 
  535                         if (msg->header.arglen != sizeof(u_int16_t))
  536                                 ERROUT(EINVAL);
  537                         linkNum = *((u_int16_t *) msg->data);
  538                         if (linkNum >= NG_PPP_MAX_LINKS
  539                             && linkNum != NG_PPP_BUNDLE_LINKNUM)
  540                                 ERROUT(EINVAL);
  541                         stats = (linkNum == NG_PPP_BUNDLE_LINKNUM) ?
  542                             &priv->bundleStats : &priv->links[linkNum].stats;
  543                         if (msg->header.cmd != NGM_PPP_CLR_LINK_STATS) {
  544                                 NG_MKRESPONSE(resp, msg,
  545                                     sizeof(struct ng_ppp_link_stat), M_NOWAIT);
  546                                 if (resp == NULL)
  547                                         ERROUT(ENOMEM);
  548                                 bcopy(stats, resp->data, sizeof(*stats));
  549                         }
  550                         if (msg->header.cmd != NGM_PPP_GET_LINK_STATS)
  551                                 bzero(stats, sizeof(*stats));
  552                         break;
  553                     }
  554                 default:
  555                         error = EINVAL;
  556                         break;
  557                 }
  558                 break;
  559         case NGM_VJC_COOKIE:
  560             {
  561                 char path[NG_PATHLEN + 1];
  562                 node_p origNode;
  563 
  564                 if ((error = ng_path2node(node, raddr, &origNode, NULL)) != 0)
  565                         ERROUT(error);
  566                 snprintf(path, sizeof(path), "[%lx]:%s",
  567                     (long)node, NG_PPP_HOOK_VJC_IP);
  568                 return ng_send_msg(origNode, msg, path, rptr);
  569             }
  570         default:
  571                 error = EINVAL;
  572                 break;
  573         }
  574         if (rptr)
  575                 *rptr = resp;
  576         else if (resp)
  577                 FREE(resp, M_NETGRAPH);
  578 
  579 done:
  580         FREE(msg, M_NETGRAPH);
  581         return (error);
  582 }
  583 
  584 /*
  585  * Receive data on a hook
  586  */
  587 static int
  588 ng_ppp_rcvdata(hook_p hook, struct mbuf *m, meta_p meta)
  589 {
  590         const node_p node = hook->node;
  591         const priv_p priv = node->private;
  592         const int index = HOOK_INDEX(hook);
  593         u_int16_t linkNum = NG_PPP_BUNDLE_LINKNUM;
  594         hook_p outHook = NULL;
  595         int proto = 0, error;
  596 
  597         /* Did it come from a link hook? */
  598         if (index < 0) {
  599                 struct ng_ppp_link *link;
  600 
  601                 /* Convert index into a link number */
  602                 linkNum = (u_int16_t)~index;
  603                 KASSERT(linkNum < NG_PPP_MAX_LINKS,
  604                     ("%s: bogus index 0x%x", __FUNCTION__, index));
  605                 link = &priv->links[linkNum];
  606 
  607                 /* Stats */
  608                 link->stats.recvFrames++;
  609                 link->stats.recvOctets += m->m_pkthdr.len;
  610 
  611                 /* Strip address and control fields, if present */
  612                 if (m->m_pkthdr.len >= 2) {
  613                         if (m->m_len < 2 && (m = m_pullup(m, 2)) == NULL) {
  614                                 NG_FREE_DATA(m, meta);
  615                                 return (ENOBUFS);
  616                         }
  617                         if (bcmp(mtod(m, u_char *), &ng_ppp_acf, 2) == 0)
  618                                 m_adj(m, 2);
  619                 }
  620 
  621                 /* Dispatch incoming frame (if not enabled, to bypass) */
  622                 return ng_ppp_input(node,
  623                     !link->conf.enableLink, linkNum, m, meta);
  624         }
  625 
  626         /* Get protocol & check if data allowed from this hook */
  627         switch (index) {
  628 
  629         /* Outgoing data */
  630         case HOOK_INDEX_ATALK:
  631                 if (!priv->conf.enableAtalk) {
  632                         NG_FREE_DATA(m, meta);
  633                         return (ENXIO);
  634                 }
  635                 proto = PROT_APPLETALK;
  636                 break;
  637         case HOOK_INDEX_IPX:
  638                 if (!priv->conf.enableIPX) {
  639                         NG_FREE_DATA(m, meta);
  640                         return (ENXIO);
  641                 }
  642                 proto = PROT_IPX;
  643                 break;
  644         case HOOK_INDEX_IPV6:
  645                 if (!priv->conf.enableIPv6) {
  646                         NG_FREE_DATA(m, meta);
  647                         return (ENXIO);
  648                 }
  649                 proto = PROT_IPV6;
  650                 break;
  651         case HOOK_INDEX_INET:
  652         case HOOK_INDEX_VJC_VJIP:
  653                 if (!priv->conf.enableIP) {
  654                         NG_FREE_DATA(m, meta);
  655                         return (ENXIO);
  656                 }
  657                 proto = PROT_IP;
  658                 break;
  659         case HOOK_INDEX_VJC_COMP:
  660                 if (!priv->conf.enableVJCompression) {
  661                         NG_FREE_DATA(m, meta);
  662                         return (ENXIO);
  663                 }
  664                 proto = PROT_VJCOMP;
  665                 break;
  666         case HOOK_INDEX_VJC_UNCOMP:
  667                 if (!priv->conf.enableVJCompression) {
  668                         NG_FREE_DATA(m, meta);
  669                         return (ENXIO);
  670                 }
  671                 proto = PROT_VJUNCOMP;
  672                 break;
  673         case HOOK_INDEX_COMPRESS:
  674                 if (!priv->conf.enableCompression) {
  675                         NG_FREE_DATA(m, meta);
  676                         return (ENXIO);
  677                 }
  678                 proto = PROT_COMPD;
  679                 break;
  680         case HOOK_INDEX_ENCRYPT:
  681                 if (!priv->conf.enableEncryption) {
  682                         NG_FREE_DATA(m, meta);
  683                         return (ENXIO);
  684                 }
  685                 proto = PROT_CRYPTD;
  686                 break;
  687         case HOOK_INDEX_BYPASS:
  688                 if (m->m_pkthdr.len < 4) {
  689                         NG_FREE_DATA(m, meta);
  690                         return (EINVAL);
  691                 }
  692                 if (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL) {
  693                         NG_FREE_META(meta);
  694                         return (ENOBUFS);
  695                 }
  696                 linkNum = ntohs(mtod(m, u_int16_t *)[0]);
  697                 proto = ntohs(mtod(m, u_int16_t *)[1]);
  698                 m_adj(m, 4);
  699                 if (linkNum >= NG_PPP_MAX_LINKS
  700                     && linkNum != NG_PPP_BUNDLE_LINKNUM) {
  701                         NG_FREE_DATA(m, meta);
  702                         return (EINVAL);
  703                 }
  704                 break;
  705 
  706         /* Incoming data */
  707         case HOOK_INDEX_VJC_IP:
  708                 if (!priv->conf.enableIP || !priv->conf.enableVJDecompression) {
  709                         NG_FREE_DATA(m, meta);
  710                         return (ENXIO);
  711                 }
  712                 break;
  713         case HOOK_INDEX_DECOMPRESS:
  714                 if (!priv->conf.enableDecompression) {
  715                         NG_FREE_DATA(m, meta);
  716                         return (ENXIO);
  717                 }
  718                 break;
  719         case HOOK_INDEX_DECRYPT:
  720                 if (!priv->conf.enableDecryption) {
  721                         NG_FREE_DATA(m, meta);
  722                         return (ENXIO);
  723                 }
  724                 break;
  725         default:
  726                 panic("%s: bogus index 0x%x", __FUNCTION__, index);
  727         }
  728 
  729         /* Now figure out what to do with the frame */
  730         switch (index) {
  731 
  732         /* Outgoing data */
  733         case HOOK_INDEX_INET:
  734                 if (priv->conf.enableVJCompression && priv->vjCompHooked) {
  735                         outHook = priv->hooks[HOOK_INDEX_VJC_IP];
  736                         break;
  737                 }
  738                 /* FALLTHROUGH */
  739         case HOOK_INDEX_ATALK:
  740         case HOOK_INDEX_IPV6:
  741         case HOOK_INDEX_IPX:
  742         case HOOK_INDEX_VJC_COMP:
  743         case HOOK_INDEX_VJC_UNCOMP:
  744         case HOOK_INDEX_VJC_VJIP:
  745                 if (priv->conf.enableCompression
  746                     && priv->hooks[HOOK_INDEX_COMPRESS] != NULL) {
  747                         if ((m = ng_ppp_addproto(m, proto, 0)) == NULL) {
  748                                 NG_FREE_META(meta);
  749                                 return (ENOBUFS);
  750                         }
  751                         outHook = priv->hooks[HOOK_INDEX_COMPRESS];
  752                         break;
  753                 }
  754                 /* FALLTHROUGH */
  755         case HOOK_INDEX_COMPRESS:
  756                 if (priv->conf.enableEncryption
  757                     && priv->hooks[HOOK_INDEX_ENCRYPT] != NULL) {
  758                         if ((m = ng_ppp_addproto(m, proto, 1)) == NULL) {
  759                                 NG_FREE_META(meta);
  760                                 return (ENOBUFS);
  761                         }
  762                         outHook = priv->hooks[HOOK_INDEX_ENCRYPT];
  763                         break;
  764                 }
  765                 /* FALLTHROUGH */
  766         case HOOK_INDEX_ENCRYPT:
  767                 return ng_ppp_output(node, 0,
  768                     proto, NG_PPP_BUNDLE_LINKNUM, m, meta);
  769 
  770         case HOOK_INDEX_BYPASS:
  771                 return ng_ppp_output(node, 1, proto, linkNum, m, meta);
  772 
  773         /* Incoming data */
  774         case HOOK_INDEX_DECRYPT:
  775         case HOOK_INDEX_DECOMPRESS:
  776                 return ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta);
  777 
  778         case HOOK_INDEX_VJC_IP:
  779                 outHook = priv->hooks[HOOK_INDEX_INET];
  780                 break;
  781         }
  782 
  783         /* Send packet out hook */
  784         NG_SEND_DATA(error, outHook, m, meta);
  785         return (error);
  786 }
  787 
  788 /*
  789  * Destroy node
  790  */
  791 static int
  792 ng_ppp_rmnode(node_p node)
  793 {
  794         const priv_p priv = node->private;
  795 
  796         /* Stop fragment queue timer */
  797         ng_ppp_stop_frag_timer(node);
  798 
  799         /* Take down netgraph node */
  800         node->flags |= NG_INVALID;
  801         ng_cutlinks(node);
  802         ng_unname(node);
  803         ng_ppp_frag_reset(node);
  804         bzero(priv, sizeof(*priv));
  805         FREE(priv, M_NETGRAPH);
  806         node->private = NULL;
  807         ng_unref(node);         /* let the node escape */
  808         return (0);
  809 }
  810 
  811 /*
  812  * Hook disconnection
  813  */
  814 static int
  815 ng_ppp_disconnect(hook_p hook)
  816 {
  817         const node_p node = hook->node;
  818         const priv_p priv = node->private;
  819         const int index = HOOK_INDEX(hook);
  820 
  821         /* Zero out hook pointer */
  822         if (index < 0)
  823                 priv->links[~index].hook = NULL;
  824         else
  825                 priv->hooks[index] = NULL;
  826 
  827         /* Update derived info (or go away if no hooks left) */
  828         if (node->numhooks > 0)
  829                 ng_ppp_update(node, 0);
  830         else
  831                 ng_rmnode(node);
  832         return (0);
  833 }
  834 
  835 /************************************************************************
  836                         HELPER STUFF
  837  ************************************************************************/
  838 
  839 /*
  840  * Handle an incoming frame.  Extract the PPP protocol number
  841  * and dispatch accordingly.
  842  */
  843 static int
  844 ng_ppp_input(node_p node, int bypass, int linkNum, struct mbuf *m, meta_p meta)
  845 {
  846         const priv_p priv = node->private;
  847         hook_p outHook = NULL;
  848         int proto, error;
  849 
  850         /* Extract protocol number */
  851         for (proto = 0; !PROT_VALID(proto) && m->m_pkthdr.len > 0; ) {
  852                 if (m->m_len < 1 && (m = m_pullup(m, 1)) == NULL) {
  853                         NG_FREE_META(meta);
  854                         return (ENOBUFS);
  855                 }
  856                 proto = (proto << 8) + *mtod(m, u_char *);
  857                 m_adj(m, 1);
  858         }
  859         if (!PROT_VALID(proto)) {
  860                 if (linkNum == NG_PPP_BUNDLE_LINKNUM)
  861                         priv->bundleStats.badProtos++;
  862                 else
  863                         priv->links[linkNum].stats.badProtos++;
  864                 NG_FREE_DATA(m, meta);
  865                 return (EINVAL);
  866         }
  867 
  868         /* Bypass frame? */
  869         if (bypass)
  870                 goto bypass;
  871 
  872         /* Check protocol */
  873         switch (proto) {
  874         case PROT_COMPD:
  875                 if (priv->conf.enableDecompression)
  876                         outHook = priv->hooks[HOOK_INDEX_DECOMPRESS];
  877                 break;
  878         case PROT_CRYPTD:
  879                 if (priv->conf.enableDecryption)
  880                         outHook = priv->hooks[HOOK_INDEX_DECRYPT];
  881                 break;
  882         case PROT_VJCOMP:
  883                 if (priv->conf.enableVJDecompression && priv->vjCompHooked)
  884                         outHook = priv->hooks[HOOK_INDEX_VJC_COMP];
  885                 break;
  886         case PROT_VJUNCOMP:
  887                 if (priv->conf.enableVJDecompression && priv->vjCompHooked)
  888                         outHook = priv->hooks[HOOK_INDEX_VJC_UNCOMP];
  889                 break;
  890         case PROT_MP:
  891                 if (priv->conf.enableMultilink
  892                     && linkNum != NG_PPP_BUNDLE_LINKNUM)
  893                         return ng_ppp_mp_input(node, linkNum, m, meta);
  894                 break;
  895         case PROT_APPLETALK:
  896                 if (priv->conf.enableAtalk)
  897                         outHook = priv->hooks[HOOK_INDEX_ATALK];
  898                 break;
  899         case PROT_IPX:
  900                 if (priv->conf.enableIPX)
  901                         outHook = priv->hooks[HOOK_INDEX_IPX];
  902                 break;
  903         case PROT_IP:
  904                 if (priv->conf.enableIP)
  905                         outHook = priv->hooks[HOOK_INDEX_INET];
  906                 break;
  907         case PROT_IPV6:
  908                 if (priv->conf.enableIPv6)
  909                         outHook = priv->hooks[HOOK_INDEX_IPV6];
  910                 break;
  911         }
  912 
  913 bypass:
  914         /* For unknown/inactive protocols, forward out the bypass hook */
  915         if (outHook == NULL) {
  916                 u_int16_t hdr[2];
  917 
  918                 hdr[0] = htons(linkNum);
  919                 hdr[1] = htons((u_int16_t)proto);
  920                 if ((m = ng_ppp_prepend(m, &hdr, 4)) == NULL) {
  921                         NG_FREE_META(meta);
  922                         return (ENOBUFS);
  923                 }
  924                 outHook = priv->hooks[HOOK_INDEX_BYPASS];
  925         }
  926 
  927         /* Forward frame */
  928         NG_SEND_DATA(error, outHook, m, meta);
  929         return (error);
  930 }
  931 
  932 /*
  933  * Deliver a frame out a link, either a real one or NG_PPP_BUNDLE_LINKNUM.
  934  * If the link is not enabled then ENXIO is returned, unless "bypass" is != 0.
  935  *
  936  * If the frame is too big for the particular link, return EMSGSIZE.
  937  */
  938 static int
  939 ng_ppp_output(node_p node, int bypass,
  940         int proto, int linkNum, struct mbuf *m, meta_p meta)
  941 {
  942         const priv_p priv = node->private;
  943         struct ng_ppp_link *link;
  944         int len, error;
  945         u_int16_t mru;
  946 
  947         /* If not doing MP, map bundle virtual link to (the only) link */
  948         if (linkNum == NG_PPP_BUNDLE_LINKNUM && !priv->conf.enableMultilink)
  949                 linkNum = priv->activeLinks[0];
  950 
  951         /* Get link pointer (optimization) */
  952         link = (linkNum != NG_PPP_BUNDLE_LINKNUM) ?
  953             &priv->links[linkNum] : NULL;
  954 
  955         /* Check link status (if real) */
  956         if (linkNum != NG_PPP_BUNDLE_LINKNUM) {
  957                 if (!bypass && !link->conf.enableLink) {
  958                         NG_FREE_DATA(m, meta);
  959                         return (ENXIO);
  960                 }
  961                 if (link->hook == NULL) {
  962                         NG_FREE_DATA(m, meta);
  963                         return (ENETDOWN);
  964                 }
  965         }
  966 
  967         /* Check peer's MRU for this link */
  968         mru = (link != NULL) ? link->conf.mru : priv->conf.mrru;
  969         if (mru != 0 && m->m_pkthdr.len > mru) {
  970                 NG_FREE_DATA(m, meta);
  971                 return (EMSGSIZE);
  972         }
  973 
  974         /* Prepend protocol number, possibly compressed */
  975         if ((m = ng_ppp_addproto(m, proto,
  976             linkNum == NG_PPP_BUNDLE_LINKNUM
  977               || link->conf.enableProtoComp)) == NULL) {
  978                 NG_FREE_META(meta);
  979                 return (ENOBUFS);
  980         }
  981 
  982         /* Special handling for the MP virtual link */
  983         if (linkNum == NG_PPP_BUNDLE_LINKNUM)
  984                 return ng_ppp_mp_output(node, m, meta);
  985 
  986         /* Prepend address and control field (unless compressed) */
  987         if (proto == PROT_LCP || !link->conf.enableACFComp) {
  988                 if ((m = ng_ppp_prepend(m, &ng_ppp_acf, 2)) == NULL) {
  989                         NG_FREE_META(meta);
  990                         return (ENOBUFS);
  991                 }
  992         }
  993 
  994         /* Deliver frame */
  995         len = m->m_pkthdr.len;
  996         NG_SEND_DATA(error, link->hook, m, meta);
  997 
  998         /* Update stats and 'bytes in queue' counter */
  999         if (error == 0) {
 1000                 link->stats.xmitFrames++;
 1001                 link->stats.xmitOctets += len;
 1002                 link->bytesInQueue += len;
 1003                 getmicrouptime(&link->lastWrite);
 1004         }
 1005         return error;
 1006 }
 1007 
 1008 /*
 1009  * Handle an incoming multi-link fragment
 1010  *
 1011  * The fragment reassembly algorithm is somewhat complex. This is mainly
 1012  * because we are required not to reorder the reconstructed packets, yet
 1013  * fragments are only guaranteed to arrive in order on a per-link basis.
 1014  * In other words, when we have a complete packet ready, but the previous
 1015  * packet is still incomplete, we have to decide between delivering the
 1016  * complete packet and throwing away the incomplete one, or waiting to
 1017  * see if the remainder of the incomplete one arrives, at which time we
 1018  * can deliver both packets, in order.
 1019  *
 1020  * This problem is exacerbated by "sequence number slew", which is when
 1021  * the sequence numbers coming in from different links are far apart from
 1022  * each other. In particular, certain unnamed equipment (*cough* Ascend)
 1023  * has been seen to generate sequence number slew of up to 10 on an ISDN
 1024  * 2B-channel MP link. There is nothing invalid about sequence number slew
 1025  * but it makes the reasssembly process have to work harder.
 1026  *
 1027  * However, the peer is required to transmit fragments in order on each
 1028  * link. That means if we define MSEQ as the minimum over all links of
 1029  * the highest sequence number received on that link, then we can always
 1030  * give up any hope of receiving a fragment with sequence number < MSEQ in
 1031  * the future (all of this using 'wraparound' sequence number space).
 1032  * Therefore we can always immediately throw away incomplete packets
 1033  * missing fragments with sequence numbers < MSEQ.
 1034  *
 1035  * Here is an overview of our algorithm:
 1036  *
 1037  *    o Received fragments are inserted into a queue, for which we
 1038  *      maintain these invariants between calls to this function:
 1039  *
 1040  *      - Fragments are ordered in the queue by sequence number
 1041  *      - If a complete packet is at the head of the queue, then
 1042  *        the first fragment in the packet has seq# > MSEQ + 1
 1043  *        (otherwise, we could deliver it immediately)
 1044  *      - If any fragments have seq# < MSEQ, then they are necessarily
 1045  *        part of a packet whose missing seq#'s are all > MSEQ (otherwise,
 1046  *        we can throw them away because they'll never be completed)
 1047  *      - The queue contains at most MP_MAX_QUEUE_LEN fragments
 1048  *
 1049  *    o We have a periodic timer that checks the queue for the first
 1050  *      complete packet that has been sitting in the queue "too long".
 1051  *      When one is detected, all previous (incomplete) fragments are
 1052  *      discarded, their missing fragments are declared lost and MSEQ
 1053  *      is increased.
 1054  *
 1055  *    o If we recieve a fragment with seq# < MSEQ, we throw it away
 1056  *      because we've already delcared it lost.
 1057  *
 1058  * This assumes linkNum != NG_PPP_BUNDLE_LINKNUM.
 1059  */
 1060 static int
 1061 ng_ppp_mp_input(node_p node, int linkNum, struct mbuf *m, meta_p meta)
 1062 {
 1063         const priv_p priv = node->private;
 1064         struct ng_ppp_link *const link = &priv->links[linkNum];
 1065         struct ng_ppp_frag frag0, *frag = &frag0;
 1066         struct ng_ppp_frag *qent;
 1067         int i, diff, inserted;
 1068 
 1069         /* Stats */
 1070         priv->bundleStats.recvFrames++;
 1071         priv->bundleStats.recvOctets += m->m_pkthdr.len;
 1072 
 1073         /* Extract fragment information from MP header */
 1074         if (priv->conf.recvShortSeq) {
 1075                 u_int16_t shdr;
 1076 
 1077                 if (m->m_pkthdr.len < 2) {
 1078                         link->stats.runts++;
 1079                         NG_FREE_DATA(m, meta);
 1080                         return (EINVAL);
 1081                 }
 1082                 if (m->m_len < 2 && (m = m_pullup(m, 2)) == NULL) {
 1083                         NG_FREE_META(meta);
 1084                         return (ENOBUFS);
 1085                 }
 1086                 shdr = ntohs(*mtod(m, u_int16_t *));
 1087                 frag->seq = MP_SHORT_EXTEND(shdr);
 1088                 frag->first = (shdr & MP_SHORT_FIRST_FLAG) != 0;
 1089                 frag->last = (shdr & MP_SHORT_LAST_FLAG) != 0;
 1090                 diff = MP_SHORT_SEQ_DIFF(frag->seq, priv->mseq);
 1091                 m_adj(m, 2);
 1092         } else {
 1093                 u_int32_t lhdr;
 1094 
 1095                 if (m->m_pkthdr.len < 4) {
 1096                         link->stats.runts++;
 1097                         NG_FREE_DATA(m, meta);
 1098                         return (EINVAL);
 1099                 }
 1100                 if (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL) {
 1101                         NG_FREE_META(meta);
 1102                         return (ENOBUFS);
 1103                 }
 1104                 lhdr = ntohl(*mtod(m, u_int32_t *));
 1105                 frag->seq = MP_LONG_EXTEND(lhdr);
 1106                 frag->first = (lhdr & MP_LONG_FIRST_FLAG) != 0;
 1107                 frag->last = (lhdr & MP_LONG_LAST_FLAG) != 0;
 1108                 diff = MP_LONG_SEQ_DIFF(frag->seq, priv->mseq);
 1109                 m_adj(m, 4);
 1110         }
 1111         frag->data = m;
 1112         frag->meta = meta;
 1113         getmicrouptime(&frag->timestamp);
 1114 
 1115         /* If sequence number is < MSEQ, we've already declared this
 1116            fragment as lost, so we have no choice now but to drop it */
 1117         if (diff < 0) {
 1118                 link->stats.dropFragments++;
 1119                 NG_FREE_DATA(m, meta);
 1120                 return (0);
 1121         }
 1122 
 1123         /* Update highest received sequence number on this link and MSEQ */
 1124         priv->mseq = link->seq = frag->seq;
 1125         for (i = 0; i < priv->numActiveLinks; i++) {
 1126                 struct ng_ppp_link *const alink =
 1127                     &priv->links[priv->activeLinks[i]];
 1128 
 1129                 if (MP_RECV_SEQ_DIFF(priv, alink->seq, priv->mseq) < 0)
 1130                         priv->mseq = alink->seq;
 1131         }
 1132 
 1133         /* Allocate a new frag struct for the queue */
 1134         MALLOC(frag, struct ng_ppp_frag *, sizeof(*frag), M_NETGRAPH, M_NOWAIT);
 1135         if (frag == NULL) {
 1136                 NG_FREE_DATA(m, meta);
 1137                 ng_ppp_frag_process(node);
 1138                 return (ENOMEM);
 1139         }
 1140         *frag = frag0;
 1141 
 1142         /* Add fragment to queue, which is sorted by sequence number */
 1143         inserted = 0;
 1144         CIRCLEQ_FOREACH_REVERSE(qent, &priv->frags, f_qent) {
 1145                 diff = MP_RECV_SEQ_DIFF(priv, frag->seq, qent->seq);
 1146                 if (diff > 0) {
 1147                         CIRCLEQ_INSERT_AFTER(&priv->frags, qent, frag, f_qent);
 1148                         inserted = 1;
 1149                         break;
 1150                 } else if (diff == 0) {      /* should never happen! */
 1151                         link->stats.dupFragments++;
 1152                         NG_FREE_DATA(frag->data, frag->meta);
 1153                         FREE(frag, M_NETGRAPH);
 1154                         return (EINVAL);
 1155                 }
 1156         }
 1157         if (!inserted)
 1158                 CIRCLEQ_INSERT_HEAD(&priv->frags, frag, f_qent);
 1159         priv->qlen++;
 1160 
 1161         /* Process the queue */
 1162         return ng_ppp_frag_process(node);
 1163 }
 1164 
 1165 /*
 1166  * Examine our list of fragments, and determine if there is a
 1167  * complete and deliverable packet at the head of the list.
 1168  * Return 1 if so, zero otherwise.
 1169  */
 1170 static int
 1171 ng_ppp_check_packet(node_p node)
 1172 {
 1173         const priv_p priv = node->private;
 1174         struct ng_ppp_frag *qent, *qnext;
 1175 
 1176         /* Check for empty queue */
 1177         if (CIRCLEQ_EMPTY(&priv->frags))
 1178                 return (0);
 1179 
 1180         /* Check first fragment is the start of a deliverable packet */
 1181         qent = CIRCLEQ_FIRST(&priv->frags);
 1182         if (!qent->first || MP_RECV_SEQ_DIFF(priv, qent->seq, priv->mseq) > 1)
 1183                 return (0);
 1184 
 1185         /* Check that all the fragments are there */
 1186         while (!qent->last) {
 1187                 qnext = CIRCLEQ_NEXT(qent, f_qent);
 1188                 if (qnext == (void *)&priv->frags)      /* end of queue */
 1189                         return (0);
 1190                 if (qnext->seq != MP_NEXT_RECV_SEQ(priv, qent->seq))
 1191                         return (0);
 1192                 qent = qnext;
 1193         }
 1194 
 1195         /* Got one */
 1196         return (1);
 1197 }
 1198 
 1199 /*
 1200  * Pull a completed packet off the head of the incoming fragment queue.
 1201  * This assumes there is a completed packet there to pull off.
 1202  */
 1203 static void
 1204 ng_ppp_get_packet(node_p node, struct mbuf **mp, meta_p *metap)
 1205 {
 1206         const priv_p priv = node->private;
 1207         struct ng_ppp_frag *qent, *qnext;
 1208         struct mbuf *m = NULL, *tail;
 1209 
 1210         qent = CIRCLEQ_FIRST(&priv->frags);
 1211         KASSERT(!CIRCLEQ_EMPTY(&priv->frags) && qent->first,
 1212             ("%s: no packet", __FUNCTION__));
 1213         for (tail = NULL; qent != NULL; qent = qnext) {
 1214                 qnext = CIRCLEQ_NEXT(qent, f_qent);
 1215                 KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
 1216                     ("%s: empty q", __FUNCTION__));
 1217                 CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
 1218                 if (tail == NULL) {
 1219                         tail = m = qent->data;
 1220                         *metap = qent->meta;    /* inherit first frag's meta */
 1221                 } else {
 1222                         m->m_pkthdr.len += qent->data->m_pkthdr.len;
 1223                         tail->m_next = qent->data;
 1224                         NG_FREE_META(qent->meta); /* drop other frags' metas */
 1225                 }
 1226                 while (tail->m_next != NULL)
 1227                         tail = tail->m_next;
 1228                 if (qent->last)
 1229                         qnext = NULL;
 1230                 FREE(qent, M_NETGRAPH);
 1231                 priv->qlen--;
 1232         }
 1233         *mp = m;
 1234 }
 1235 
 1236 /*
 1237  * Trim fragments from the queue whose packets can never be completed.
 1238  * This assumes a complete packet is NOT at the beginning of the queue.
 1239  * Returns 1 if fragments were removed, zero otherwise.
 1240  */
 1241 static int
 1242 ng_ppp_frag_trim(node_p node)
 1243 {
 1244         const priv_p priv = node->private;
 1245         struct ng_ppp_frag *qent, *qnext = NULL;
 1246         int removed = 0;
 1247 
 1248         /* Scan for "dead" fragments and remove them */
 1249         while (1) {
 1250                 int dead = 0;
 1251 
 1252                 /* If queue is empty, we're done */
 1253                 if (CIRCLEQ_EMPTY(&priv->frags))
 1254                         break;
 1255 
 1256                 /* Determine whether first fragment can ever be completed */
 1257                 CIRCLEQ_FOREACH(qent, &priv->frags, f_qent) {
 1258                         if (MP_RECV_SEQ_DIFF(priv, qent->seq, priv->mseq) >= 0)
 1259                                 break;
 1260                         qnext = CIRCLEQ_NEXT(qent, f_qent);
 1261                         KASSERT(qnext != (void*)&priv->frags,
 1262                             ("%s: last frag < MSEQ?", __FUNCTION__));
 1263                         if (qnext->seq != MP_NEXT_RECV_SEQ(priv, qent->seq)
 1264                             || qent->last || qnext->first) {
 1265                                 dead = 1;
 1266                                 break;
 1267                         }
 1268                 }
 1269                 if (!dead)
 1270                         break;
 1271 
 1272                 /* Remove fragment and all others in the same packet */
 1273                 while ((qent = CIRCLEQ_FIRST(&priv->frags)) != qnext) {
 1274                         KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
 1275                             ("%s: empty q", __FUNCTION__));
 1276                         priv->bundleStats.dropFragments++;
 1277                         CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
 1278                         NG_FREE_DATA(qent->data, qent->meta);
 1279                         FREE(qent, M_NETGRAPH);
 1280                         priv->qlen--;
 1281                         removed = 1;
 1282                 }
 1283         }
 1284         return (removed);
 1285 }
 1286 
 1287 /*
 1288  * Run the queue, restoring the queue invariants
 1289  */
 1290 static int
 1291 ng_ppp_frag_process(node_p node)
 1292 {
 1293         const priv_p priv = node->private;
 1294         struct mbuf *m;
 1295         meta_p meta;
 1296 
 1297         /* Deliver any deliverable packets */
 1298         while (ng_ppp_check_packet(node)) {
 1299                 ng_ppp_get_packet(node, &m, &meta);
 1300                 ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta);
 1301         }
 1302 
 1303         /* Delete dead fragments and try again */
 1304         if (ng_ppp_frag_trim(node)) {
 1305                 while (ng_ppp_check_packet(node)) {
 1306                         ng_ppp_get_packet(node, &m, &meta);
 1307                         ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta);
 1308                 }
 1309         }
 1310 
 1311         /* Check for stale fragments while we're here */
 1312         ng_ppp_frag_checkstale(node);
 1313 
 1314         /* Check queue length */
 1315         if (priv->qlen > MP_MAX_QUEUE_LEN) {
 1316                 struct ng_ppp_frag *qent;
 1317                 int i;
 1318 
 1319                 /* Get oldest fragment */
 1320                 KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
 1321                     ("%s: empty q", __FUNCTION__));
 1322                 qent = CIRCLEQ_FIRST(&priv->frags);
 1323 
 1324                 /* Bump MSEQ if necessary */
 1325                 if (MP_RECV_SEQ_DIFF(priv, priv->mseq, qent->seq) < 0) {
 1326                         priv->mseq = qent->seq;
 1327                         for (i = 0; i < priv->numActiveLinks; i++) {
 1328                                 struct ng_ppp_link *const alink =
 1329                                     &priv->links[priv->activeLinks[i]];
 1330 
 1331                                 if (MP_RECV_SEQ_DIFF(priv,
 1332                                     alink->seq, priv->mseq) < 0)
 1333                                         alink->seq = priv->mseq;
 1334                         }
 1335                 }
 1336 
 1337                 /* Drop it */
 1338                 priv->bundleStats.dropFragments++;
 1339                 CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
 1340                 NG_FREE_DATA(qent->data, qent->meta);
 1341                 FREE(qent, M_NETGRAPH);
 1342                 priv->qlen--;
 1343 
 1344                 /* Process queue again */
 1345                 return ng_ppp_frag_process(node);
 1346         }
 1347 
 1348         /* Done */
 1349         return (0);
 1350 }
 1351 
 1352 /*
 1353  * Check for 'stale' completed packets that need to be delivered
 1354  *
 1355  * If a link goes down or has a temporary failure, MSEQ can get
 1356  * "stuck", because no new incoming fragments appear on that link.
 1357  * This can cause completed packets to never get delivered if
 1358  * their sequence numbers are all > MSEQ + 1.
 1359  *
 1360  * This routine checks how long all of the completed packets have
 1361  * been sitting in the queue, and if too long, removes fragments
 1362  * from the queue and increments MSEQ to allow them to be delivered.
 1363  */
 1364 static void
 1365 ng_ppp_frag_checkstale(node_p node)
 1366 {
 1367         const priv_p priv = node->private;
 1368         struct ng_ppp_frag *qent, *beg, *end;
 1369         struct timeval now, age;
 1370         struct mbuf *m;
 1371         meta_p meta;
 1372         int i, seq;
 1373         int endseq;
 1374 
 1375         now.tv_sec = 0;                 /* uninitialized state */
 1376         while (1) {
 1377 
 1378                 /* If queue is empty, we're done */
 1379                 if (CIRCLEQ_EMPTY(&priv->frags))
 1380                         break;
 1381 
 1382                 /* Find the first complete packet in the queue */
 1383                 beg = end = NULL;
 1384                 seq = CIRCLEQ_FIRST(&priv->frags)->seq;
 1385                 CIRCLEQ_FOREACH(qent, &priv->frags, f_qent) {
 1386                         if (qent->first)
 1387                                 beg = qent;
 1388                         else if (qent->seq != seq)
 1389                                 beg = NULL;
 1390                         if (beg != NULL && qent->last) {
 1391                                 end = qent;
 1392                                 break;
 1393                         }
 1394                         seq = MP_NEXT_RECV_SEQ(priv, seq);
 1395                 }
 1396 
 1397                 /* If none found, exit */
 1398                 if (end == NULL)
 1399                         break;
 1400 
 1401                 /* Get current time (we assume we've been up for >= 1 second) */
 1402                 if (now.tv_sec == 0)
 1403                         getmicrouptime(&now);
 1404 
 1405                 /* Check if packet has been queued too long */
 1406                 age = now;
 1407                 timevalsub(&age, &beg->timestamp);
 1408                 if (timevalcmp(&age, &ng_ppp_max_staleness, < ))
 1409                         break;
 1410 
 1411                 /* Throw away junk fragments in front of the completed packet */
 1412                 while ((qent = CIRCLEQ_FIRST(&priv->frags)) != beg) {
 1413                         KASSERT(!CIRCLEQ_EMPTY(&priv->frags),
 1414                             ("%s: empty q", __FUNCTION__));
 1415                         priv->bundleStats.dropFragments++;
 1416                         CIRCLEQ_REMOVE(&priv->frags, qent, f_qent);
 1417                         NG_FREE_DATA(qent->data, qent->meta);
 1418                         FREE(qent, M_NETGRAPH);
 1419                         priv->qlen--;
 1420                 }
 1421 
 1422                 /* Extract completed packet */
 1423                 endseq = end->seq;
 1424                 ng_ppp_get_packet(node, &m, &meta);
 1425 
 1426                 /* Bump MSEQ if necessary */
 1427                 if (MP_RECV_SEQ_DIFF(priv, priv->mseq, endseq) < 0) {
 1428                         priv->mseq = endseq;
 1429                         for (i = 0; i < priv->numActiveLinks; i++) {
 1430                                 struct ng_ppp_link *const alink =
 1431                                     &priv->links[priv->activeLinks[i]];
 1432 
 1433                                 if (MP_RECV_SEQ_DIFF(priv,
 1434                                     alink->seq, priv->mseq) < 0)
 1435                                         alink->seq = priv->mseq;
 1436                         }
 1437                 }
 1438 
 1439                 /* Deliver packet */
 1440                 ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta);
 1441         }
 1442 }
 1443 
 1444 /*
 1445  * Periodically call ng_ppp_frag_checkstale()
 1446  */
 1447 static void
 1448 ng_ppp_frag_timeout(void *arg)
 1449 {
 1450         const node_p node = arg;
 1451         const priv_p priv = node->private;
 1452         int s = splnet();
 1453 
 1454         /* Handle the race where shutdown happens just before splnet() above */
 1455         if ((node->flags & NG_INVALID) != 0) {
 1456                 ng_unref(node);
 1457                 splx(s);
 1458                 return;
 1459         }
 1460 
 1461         /* Reset timer state after timeout */
 1462         KASSERT(priv->timerActive, ("%s: !timerActive", __FUNCTION__));
 1463         priv->timerActive = 0;
 1464         KASSERT(node->refs > 1, ("%s: refs=%d", __FUNCTION__, node->refs));
 1465         ng_unref(node);
 1466 
 1467         /* Start timer again */
 1468         ng_ppp_start_frag_timer(node);
 1469 
 1470         /* Scan the fragment queue */
 1471         ng_ppp_frag_checkstale(node);
 1472         splx(s);
 1473 }
 1474 
 1475 /*
 1476  * Deliver a frame out on the bundle, i.e., figure out how to fragment
 1477  * the frame across the individual PPP links and do so.
 1478  */
 1479 static int
 1480 ng_ppp_mp_output(node_p node, struct mbuf *m, meta_p meta)
 1481 {
 1482         const priv_p priv = node->private;
 1483         const int hdr_len = priv->conf.xmitShortSeq ? 2 : 4;
 1484         int distrib[NG_PPP_MAX_LINKS];
 1485         int firstFragment;
 1486         int activeLinkNum;
 1487 
 1488         /* At least one link must be active */
 1489         if (priv->numActiveLinks == 0) {
 1490                 NG_FREE_DATA(m, meta);
 1491                 return (ENETDOWN);
 1492         }
 1493 
 1494         /* Round-robin strategy */
 1495         if (priv->conf.enableRoundRobin || m->m_pkthdr.len < MP_MIN_FRAG_LEN) {
 1496                 activeLinkNum = priv->lastLink++ % priv->numActiveLinks;
 1497                 bzero(&distrib, priv->numActiveLinks * sizeof(distrib[0]));
 1498                 distrib[activeLinkNum] = m->m_pkthdr.len;
 1499                 goto deliver;
 1500         }
 1501 
 1502         /* Strategy when all links are equivalent (optimize the common case) */
 1503         if (priv->allLinksEqual) {
 1504                 const int fraction = m->m_pkthdr.len / priv->numActiveLinks;
 1505                 int i, remain;
 1506 
 1507                 for (i = 0; i < priv->numActiveLinks; i++)
 1508                         distrib[priv->lastLink++ % priv->numActiveLinks]
 1509                             = fraction;
 1510                 remain = m->m_pkthdr.len - (fraction * priv->numActiveLinks);
 1511                 while (remain > 0) {
 1512                         distrib[priv->lastLink++ % priv->numActiveLinks]++;
 1513                         remain--;
 1514                 }
 1515                 goto deliver;
 1516         }
 1517 
 1518         /* Strategy when all links are not equivalent */
 1519         ng_ppp_mp_strategy(node, m->m_pkthdr.len, distrib);
 1520 
 1521 deliver:
 1522         /* Update stats */
 1523         priv->bundleStats.xmitFrames++;
 1524         priv->bundleStats.xmitOctets += m->m_pkthdr.len;
 1525 
 1526         /* Send alloted portions of frame out on the link(s) */
 1527         for (firstFragment = 1, activeLinkNum = priv->numActiveLinks - 1;
 1528             activeLinkNum >= 0; activeLinkNum--) {
 1529                 const int linkNum = priv->activeLinks[activeLinkNum];
 1530                 struct ng_ppp_link *const link = &priv->links[linkNum];
 1531 
 1532                 /* Deliver fragment(s) out the next link */
 1533                 for ( ; distrib[activeLinkNum] > 0; firstFragment = 0) {
 1534                         int len, lastFragment, error;
 1535                         struct mbuf *m2;
 1536                         meta_p meta2;
 1537 
 1538                         /* Calculate fragment length; don't exceed link MTU */
 1539                         len = distrib[activeLinkNum];
 1540                         if (len > link->conf.mru - hdr_len)
 1541                                 len = link->conf.mru - hdr_len;
 1542                         distrib[activeLinkNum] -= len;
 1543                         lastFragment = (len == m->m_pkthdr.len);
 1544 
 1545                         /* Split off next fragment as "m2" */
 1546                         m2 = m;
 1547                         if (!lastFragment) {
 1548                                 struct mbuf *n = m_split(m, len, M_NOWAIT);
 1549 
 1550                                 if (n == NULL) {
 1551                                         NG_FREE_DATA(m, meta);
 1552                                         return (ENOMEM);
 1553                                 }
 1554                                 m = n;
 1555                         }
 1556 
 1557                         /* Prepend MP header */
 1558                         if (priv->conf.xmitShortSeq) {
 1559                                 u_int16_t shdr;
 1560 
 1561                                 shdr = priv->xseq;
 1562                                 priv->xseq =
 1563                                     (priv->xseq + 1) & MP_SHORT_SEQ_MASK;
 1564                                 if (firstFragment)
 1565                                         shdr |= MP_SHORT_FIRST_FLAG;
 1566                                 if (lastFragment)
 1567                                         shdr |= MP_SHORT_LAST_FLAG;
 1568                                 shdr = htons(shdr);
 1569                                 m2 = ng_ppp_prepend(m2, &shdr, 2);
 1570                         } else {
 1571                                 u_int32_t lhdr;
 1572 
 1573                                 lhdr = priv->xseq;
 1574                                 priv->xseq =
 1575                                     (priv->xseq + 1) & MP_LONG_SEQ_MASK;
 1576                                 if (firstFragment)
 1577                                         lhdr |= MP_LONG_FIRST_FLAG;
 1578                                 if (lastFragment)
 1579                                         lhdr |= MP_LONG_LAST_FLAG;
 1580                                 lhdr = htonl(lhdr);
 1581                                 m2 = ng_ppp_prepend(m2, &lhdr, 4);
 1582                         }
 1583                         if (m2 == NULL) {
 1584                                 if (!lastFragment)
 1585                                         m_freem(m);
 1586                                 NG_FREE_META(meta);
 1587                                 return (ENOBUFS);
 1588                         }
 1589 
 1590                         /* Copy the meta information, if any */
 1591                         meta2 = lastFragment ? meta : ng_copy_meta(meta);
 1592 
 1593                         /* Send fragment */
 1594                         error = ng_ppp_output(node, 0,
 1595                             PROT_MP, linkNum, m2, meta2);
 1596                         if (error != 0) {
 1597                                 if (!lastFragment)
 1598                                         NG_FREE_DATA(m, meta);
 1599                                 return (error);
 1600                         }
 1601                 }
 1602         }
 1603 
 1604         /* Done */
 1605         return (0);
 1606 }
 1607 
 1608 /*
 1609  * Computing the optimal fragmentation
 1610  * -----------------------------------
 1611  *
 1612  * This routine tries to compute the optimal fragmentation pattern based
 1613  * on each link's latency, bandwidth, and calculated additional latency.
 1614  * The latter quantity is the additional latency caused by previously
 1615  * written data that has not been transmitted yet.
 1616  *
 1617  * This algorithm is only useful when not all of the links have the
 1618  * same latency and bandwidth values.
 1619  *
 1620  * The essential idea is to make the last bit of each fragment of the
 1621  * frame arrive at the opposite end at the exact same time. This greedy
 1622  * algorithm is optimal, in that no other scheduling could result in any
 1623  * packet arriving any sooner unless packets are delivered out of order.
 1624  *
 1625  * Suppose link i has bandwidth b_i (in tens of bytes per milisecond) and
 1626  * latency l_i (in miliseconds). Consider the function function f_i(t)
 1627  * which is equal to the number of bytes that will have arrived at
 1628  * the peer after t miliseconds if we start writing continuously at
 1629  * time t = 0. Then f_i(t) = b_i * (t - l_i) = ((b_i * t) - (l_i * b_i).
 1630  * That is, f_i(t) is a line with slope b_i and y-intersect -(l_i * b_i).
 1631  * Note that the y-intersect is always <= zero because latency can't be
 1632  * negative.  Note also that really the function is f_i(t) except when
 1633  * f_i(t) is negative, in which case the function is zero.  To take
 1634  * care of this, let Q_i(t) = { if (f_i(t) > 0) return 1; else return 0; }.
 1635  * So the actual number of bytes that will have arrived at the peer after
 1636  * t miliseconds is f_i(t) * Q_i(t).
 1637  *
 1638  * At any given time, each link has some additional latency a_i >= 0
 1639  * due to previously written fragment(s) which are still in the queue.
 1640  * This value is easily computed from the time since last transmission,
 1641  * the previous latency value, the number of bytes written, and the
 1642  * link's bandwidth.
 1643  *
 1644  * Assume that l_i includes any a_i already, and that the links are
 1645  * sorted by latency, so that l_i <= l_{i+1}.
 1646  *
 1647  * Let N be the total number of bytes in the current frame we are sending.
 1648  *
 1649  * Suppose we were to start writing bytes at time t = 0 on all links
 1650  * simultaneously, which is the most we can possibly do.  Then let
 1651  * F(t) be equal to the total number of bytes received by the peer
 1652  * after t miliseconds. Then F(t) = Sum_i (f_i(t) * Q_i(t)).
 1653  *
 1654  * Our goal is simply this: fragment the frame across the links such
 1655  * that the peer is able to reconstruct the completed frame as soon as
 1656  * possible, i.e., at the least possible value of t. Call this value t_0.
 1657  *
 1658  * Then it follows that F(t_0) = N. Our strategy is first to find the value
 1659  * of t_0, and then deduce how many bytes to write to each link.
 1660  *
 1661  * Rewriting F(t_0):
 1662  *
 1663  *   t_0 = ( N + Sum_i ( l_i * b_i * Q_i(t_0) ) ) / Sum_i ( b_i * Q_i(t_0) )
 1664  *
 1665  * Now, we note that Q_i(t) is constant for l_i <= t <= l_{i+1}. t_0 will
 1666  * lie in one of these ranges.  To find it, we just need to find the i such
 1667  * that F(l_i) <= N <= F(l_{i+1}).  Then we compute all the constant values
 1668  * for Q_i() in this range, plug in the remaining values, solving for t_0.
 1669  *
 1670  * Once t_0 is known, then the number of bytes to send on link i is
 1671  * just f_i(t_0) * Q_i(t_0).
 1672  *
 1673  * In other words, we start allocating bytes to the links one at a time.
 1674  * We keep adding links until the frame is completely sent.  Some links
 1675  * may not get any bytes because their latency is too high.
 1676  *
 1677  * Is all this work really worth the trouble?  Depends on the situation.
 1678  * The bigger the ratio of computer speed to link speed, and the more
 1679  * important total bundle latency is (e.g., for interactive response time),
 1680  * the more it's worth it.  There is however the cost of calling this
 1681  * function for every frame.  The running time is O(n^2) where n is the
 1682  * number of links that receive a non-zero number of bytes.
 1683  *
 1684  * Since latency is measured in miliseconds, the "resolution" of this
 1685  * algorithm is one milisecond.
 1686  *
 1687  * To avoid this algorithm altogether, configure all links to have the
 1688  * same latency and bandwidth.
 1689  */
 1690 static void
 1691 ng_ppp_mp_strategy(node_p node, int len, int *distrib)
 1692 {
 1693         const priv_p priv = node->private;
 1694         int latency[NG_PPP_MAX_LINKS];
 1695         int sortByLatency[NG_PPP_MAX_LINKS];
 1696         int activeLinkNum;
 1697         int t0, total, topSum, botSum;
 1698         struct timeval now;
 1699         int i, numFragments;
 1700 
 1701         /* If only one link, this gets real easy */
 1702         if (priv->numActiveLinks == 1) {
 1703                 distrib[0] = len;
 1704                 return;
 1705         }
 1706 
 1707         /* Get current time */
 1708         getmicrouptime(&now);
 1709 
 1710         /* Compute latencies for each link at this point in time */
 1711         for (activeLinkNum = 0;
 1712             activeLinkNum < priv->numActiveLinks; activeLinkNum++) {
 1713                 struct ng_ppp_link *alink;
 1714                 struct timeval diff;
 1715                 int xmitBytes;
 1716 
 1717                 /* Start with base latency value */
 1718                 alink = &priv->links[priv->activeLinks[activeLinkNum]];
 1719                 latency[activeLinkNum] = alink->conf.latency;
 1720                 sortByLatency[activeLinkNum] = activeLinkNum;   /* see below */
 1721 
 1722                 /* Any additional latency? */
 1723                 if (alink->bytesInQueue == 0)
 1724                         continue;
 1725 
 1726                 /* Compute time delta since last write */
 1727                 diff = now;
 1728                 timevalsub(&diff, &alink->lastWrite);
 1729                 if (now.tv_sec < 0 || diff.tv_sec >= 10) {      /* sanity */
 1730                         alink->bytesInQueue = 0;
 1731                         continue;
 1732                 }
 1733 
 1734                 /* How many bytes could have transmitted since last write? */
 1735                 xmitBytes = (alink->conf.bandwidth * diff.tv_sec)
 1736                     + (alink->conf.bandwidth * (diff.tv_usec / 1000)) / 100;
 1737                 alink->bytesInQueue -= xmitBytes;
 1738                 if (alink->bytesInQueue < 0)
 1739                         alink->bytesInQueue = 0;
 1740                 else
 1741                         latency[activeLinkNum] +=
 1742                             (100 * alink->bytesInQueue) / alink->conf.bandwidth;
 1743         }
 1744 
 1745         /* Sort active links by latency */
 1746         compareLatencies = latency;
 1747         qsort(sortByLatency,
 1748             priv->numActiveLinks, sizeof(*sortByLatency), ng_ppp_intcmp);
 1749         compareLatencies = NULL;
 1750 
 1751         /* Find the interval we need (add links in sortByLatency[] order) */
 1752         for (numFragments = 1;
 1753             numFragments < priv->numActiveLinks; numFragments++) {
 1754                 for (total = i = 0; i < numFragments; i++) {
 1755                         int flowTime;
 1756 
 1757                         flowTime = latency[sortByLatency[numFragments]]
 1758                             - latency[sortByLatency[i]];
 1759                         total += ((flowTime * priv->links[
 1760                             priv->activeLinks[sortByLatency[i]]].conf.bandwidth)
 1761                                 + 99) / 100;
 1762                 }
 1763                 if (total >= len)
 1764                         break;
 1765         }
 1766 
 1767         /* Solve for t_0 in that interval */
 1768         for (topSum = botSum = i = 0; i < numFragments; i++) {
 1769                 int bw = priv->links[
 1770                     priv->activeLinks[sortByLatency[i]]].conf.bandwidth;
 1771 
 1772                 topSum += latency[sortByLatency[i]] * bw;       /* / 100 */
 1773                 botSum += bw;                                   /* / 100 */
 1774         }
 1775         t0 = ((len * 100) + topSum + botSum / 2) / botSum;
 1776 
 1777         /* Compute f_i(t_0) all i */
 1778         bzero(distrib, priv->numActiveLinks * sizeof(*distrib));
 1779         for (total = i = 0; i < numFragments; i++) {
 1780                 int bw = priv->links[
 1781                     priv->activeLinks[sortByLatency[i]]].conf.bandwidth;
 1782 
 1783                 distrib[sortByLatency[i]] =
 1784                     (bw * (t0 - latency[sortByLatency[i]]) + 50) / 100;
 1785                 total += distrib[sortByLatency[i]];
 1786         }
 1787 
 1788         /* Deal with any rounding error */
 1789         if (total < len) {
 1790                 struct ng_ppp_link *fastLink =
 1791                     &priv->links[priv->activeLinks[sortByLatency[0]]];
 1792                 int fast = 0;
 1793 
 1794                 /* Find the fastest link */
 1795                 for (i = 1; i < numFragments; i++) {
 1796                         struct ng_ppp_link *const link =
 1797                             &priv->links[priv->activeLinks[sortByLatency[i]]];
 1798 
 1799                         if (link->conf.bandwidth > fastLink->conf.bandwidth) {
 1800                                 fast = i;
 1801                                 fastLink = link;
 1802                         }
 1803                 }
 1804                 distrib[sortByLatency[fast]] += len - total;
 1805         } else while (total > len) {
 1806                 struct ng_ppp_link *slowLink =
 1807                     &priv->links[priv->activeLinks[sortByLatency[0]]];
 1808                 int delta, slow = 0;
 1809 
 1810                 /* Find the slowest link that still has bytes to remove */
 1811                 for (i = 1; i < numFragments; i++) {
 1812                         struct ng_ppp_link *const link =
 1813                             &priv->links[priv->activeLinks[sortByLatency[i]]];
 1814 
 1815                         if (distrib[sortByLatency[slow]] == 0
 1816                           || (distrib[sortByLatency[i]] > 0
 1817                             && link->conf.bandwidth <
 1818                               slowLink->conf.bandwidth)) {
 1819                                 slow = i;
 1820                                 slowLink = link;
 1821                         }
 1822                 }
 1823                 delta = total - len;
 1824                 if (delta > distrib[sortByLatency[slow]])
 1825                         delta = distrib[sortByLatency[slow]];
 1826                 distrib[sortByLatency[slow]] -= delta;
 1827                 total -= delta;
 1828         }
 1829 }
 1830 
 1831 /*
 1832  * Compare two integers
 1833  */
 1834 static int
 1835 ng_ppp_intcmp(const void *v1, const void *v2)
 1836 {
 1837         const int index1 = *((const int *) v1);
 1838         const int index2 = *((const int *) v2);
 1839 
 1840         return compareLatencies[index1] - compareLatencies[index2];
 1841 }
 1842 
 1843 /*
 1844  * Prepend a possibly compressed PPP protocol number in front of a frame
 1845  */
 1846 static struct mbuf *
 1847 ng_ppp_addproto(struct mbuf *m, int proto, int compOK)
 1848 {
 1849         if (compOK && PROT_COMPRESSABLE(proto)) {
 1850                 u_char pbyte = (u_char)proto;
 1851 
 1852                 return ng_ppp_prepend(m, &pbyte, 1);
 1853         } else {
 1854                 u_int16_t pword = htons((u_int16_t)proto);
 1855 
 1856                 return ng_ppp_prepend(m, &pword, 2);
 1857         }
 1858 }
 1859 
 1860 /*
 1861  * Prepend some bytes to an mbuf
 1862  */
 1863 static struct mbuf *
 1864 ng_ppp_prepend(struct mbuf *m, const void *buf, int len)
 1865 {
 1866         M_PREPEND(m, len, M_NOWAIT);
 1867         if (m == NULL || (m->m_len < len && (m = m_pullup(m, len)) == NULL))
 1868                 return (NULL);
 1869         bcopy(buf, mtod(m, u_char *), len);
 1870         return (m);
 1871 }
 1872 
 1873 /*
 1874  * Update private information that is derived from other private information
 1875  */
 1876 static void
 1877 ng_ppp_update(node_p node, int newConf)
 1878 {
 1879         const priv_p priv = node->private;
 1880         int i;
 1881 
 1882         /* Update active status for VJ Compression */
 1883         priv->vjCompHooked = priv->hooks[HOOK_INDEX_VJC_IP] != NULL
 1884             && priv->hooks[HOOK_INDEX_VJC_COMP] != NULL
 1885             && priv->hooks[HOOK_INDEX_VJC_UNCOMP] != NULL
 1886             && priv->hooks[HOOK_INDEX_VJC_VJIP] != NULL;
 1887 
 1888         /* Increase latency for each link an amount equal to one MP header */
 1889         if (newConf) {
 1890                 for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
 1891                         int hdrBytes;
 1892 
 1893                         hdrBytes = (priv->links[i].conf.enableACFComp ? 0 : 2)
 1894                             + (priv->links[i].conf.enableProtoComp ? 1 : 2)
 1895                             + (priv->conf.xmitShortSeq ? 2 : 4);
 1896                         priv->links[i].conf.latency +=
 1897                             ((hdrBytes * priv->links[i].conf.bandwidth) + 50)
 1898                                 / 100;
 1899                 }
 1900         }
 1901 
 1902         /* Update list of active links */
 1903         bzero(&priv->activeLinks, sizeof(priv->activeLinks));
 1904         priv->numActiveLinks = 0;
 1905         priv->allLinksEqual = 1;
 1906         for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
 1907                 struct ng_ppp_link *const link = &priv->links[i];
 1908 
 1909                 /* Is link active? */
 1910                 if (link->conf.enableLink && link->hook != NULL) {
 1911                         struct ng_ppp_link *link0;
 1912 
 1913                         /* Add link to list of active links */
 1914                         priv->activeLinks[priv->numActiveLinks++] = i;
 1915                         link0 = &priv->links[priv->activeLinks[0]];
 1916 
 1917                         /* Determine if all links are still equal */
 1918                         if (link->conf.latency != link0->conf.latency
 1919                           || link->conf.bandwidth != link0->conf.bandwidth)
 1920                                 priv->allLinksEqual = 0;
 1921 
 1922                         /* Initialize rec'd sequence number */
 1923                         if (link->seq == MP_NOSEQ) {
 1924                                 link->seq = (link == link0) ?
 1925                                     MP_INITIAL_SEQ : link0->seq;
 1926                         }
 1927                 } else
 1928                         link->seq = MP_NOSEQ;
 1929         }
 1930 
 1931         /* Update MP state as multi-link is active or not */
 1932         if (priv->conf.enableMultilink && priv->numActiveLinks > 0)
 1933                 ng_ppp_start_frag_timer(node);
 1934         else {
 1935                 ng_ppp_stop_frag_timer(node);
 1936                 ng_ppp_frag_reset(node);
 1937                 priv->xseq = MP_INITIAL_SEQ;
 1938                 priv->mseq = MP_INITIAL_SEQ;
 1939                 for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
 1940                         struct ng_ppp_link *const link = &priv->links[i];
 1941 
 1942                         bzero(&link->lastWrite, sizeof(link->lastWrite));
 1943                         link->bytesInQueue = 0;
 1944                         link->seq = MP_NOSEQ;
 1945                 }
 1946         }
 1947 }
 1948 
 1949 /*
 1950  * Determine if a new configuration would represent a valid change
 1951  * from the current configuration and link activity status.
 1952  */
 1953 static int
 1954 ng_ppp_config_valid(node_p node, const struct ng_ppp_node_conf *newConf)
 1955 {
 1956         const priv_p priv = node->private;
 1957         int i, newNumLinksActive;
 1958 
 1959         /* Check per-link config and count how many links would be active */
 1960         for (newNumLinksActive = i = 0; i < NG_PPP_MAX_LINKS; i++) {
 1961                 if (newConf->links[i].enableLink && priv->links[i].hook != NULL)
 1962                         newNumLinksActive++;
 1963                 if (!newConf->links[i].enableLink)
 1964                         continue;
 1965                 if (newConf->links[i].mru < MP_MIN_LINK_MRU)
 1966                         return (0);
 1967                 if (newConf->links[i].bandwidth == 0)
 1968                         return (0);
 1969                 if (newConf->links[i].bandwidth > NG_PPP_MAX_BANDWIDTH)
 1970                         return (0);
 1971                 if (newConf->links[i].latency > NG_PPP_MAX_LATENCY)
 1972                         return (0);
 1973         }
 1974 
 1975         /* Check bundle parameters */
 1976         if (newConf->bund.enableMultilink && newConf->bund.mrru < MP_MIN_MRRU)
 1977                 return (0);
 1978 
 1979         /* Disallow changes to multi-link configuration while MP is active */
 1980         if (priv->numActiveLinks > 0 && newNumLinksActive > 0) {
 1981                 if (!priv->conf.enableMultilink
 1982                                 != !newConf->bund.enableMultilink
 1983                     || !priv->conf.xmitShortSeq != !newConf->bund.xmitShortSeq
 1984                     || !priv->conf.recvShortSeq != !newConf->bund.recvShortSeq)
 1985                         return (0);
 1986         }
 1987 
 1988         /* At most one link can be active unless multi-link is enabled */
 1989         if (!newConf->bund.enableMultilink && newNumLinksActive > 1)
 1990                 return (0);
 1991 
 1992         /* Configuration change would be valid */
 1993         return (1);
 1994 }
 1995 
 1996 /*
 1997  * Free all entries in the fragment queue
 1998  */
 1999 static void
 2000 ng_ppp_frag_reset(node_p node)
 2001 {
 2002         const priv_p priv = node->private;
 2003         struct ng_ppp_frag *qent, *qnext;
 2004 
 2005         for (qent = CIRCLEQ_FIRST(&priv->frags);
 2006             qent != (void *)&priv->frags; qent = qnext) {
 2007                 qnext = CIRCLEQ_NEXT(qent, f_qent);
 2008                 NG_FREE_DATA(qent->data, qent->meta);
 2009                 FREE(qent, M_NETGRAPH);
 2010         }
 2011         CIRCLEQ_INIT(&priv->frags);
 2012         priv->qlen = 0;
 2013 }
 2014 
 2015 /*
 2016  * Start fragment queue timer
 2017  */
 2018 static void
 2019 ng_ppp_start_frag_timer(node_p node)
 2020 {
 2021         const priv_p priv = node->private;
 2022 
 2023         if (!priv->timerActive) {
 2024                 priv->fragTimer = timeout(ng_ppp_frag_timeout,
 2025                     node, MP_FRAGTIMER_INTERVAL);
 2026                 priv->timerActive = 1;
 2027                 node->refs++;
 2028         }
 2029 }
 2030 
 2031 /*
 2032  * Stop fragment queue timer
 2033  */
 2034 static void
 2035 ng_ppp_stop_frag_timer(node_p node)
 2036 {
 2037         const priv_p priv = node->private;
 2038 
 2039         if (priv->timerActive) {
 2040                 untimeout(ng_ppp_frag_timeout, node, priv->fragTimer);
 2041                 priv->timerActive = 0;
 2042                 KASSERT(node->refs > 1,
 2043                     ("%s: refs=%d", __FUNCTION__, node->refs));
 2044                 ng_unref(node);
 2045         }
 2046 }
 2047 

Cache object: 116d0fe375036dab238032bc87f8c75b


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.