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

Cache object: 477b48388d04e20ab73f587e4bb1df9f


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