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

Cache object: a71285e80c3d49416f8985bf805bc95f


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