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


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

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

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

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

Cache object: 4f59ca83a8eac0efc6e6b1f396dbbb02


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