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

Cache object: cc5fc990e2811ab003d75b0dda4892ee


[ 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.