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

Cache object: b2fb7a2bd90ef75f61b979f97402da0a


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