sys/netgraph/ng_ppp.c

   1 /*-
   2  * Copyright (c) 1996-2000 Whistle Communications, Inc.
   3  * All rights reserved.
   4  *
   5  * Subject to the following obligations and disclaimer of warranty, use and
   6  * redistribution of this software, in source or object code forms, with or
   7  * without modifications are expressly permitted by Whistle Communications;
   8  * provided, however, that:
   9  * 1. Any and all reproductions of the source or object code must include the
  10  *    copyright notice above and the following disclaimer of warranties; and
  11  * 2. No rights are granted, in any manner or form, to use Whistle
  12  *    Communications, Inc. trademarks, including the mark "WHISTLE
  13  *    COMMUNICATIONS" on advertising, endorsements, or otherwise except as
  14  *    such appears in the above copyright notice or in the software.
  15  *
  16  * THIS SOFTWARE IS BEING PROVIDED BY WHISTLE COMMUNICATIONS "AS IS", AND
  17  * TO THE MAXIMUM EXTENT PERMITTED BY LAW, WHISTLE COMMUNICATIONS MAKES NO
  18  * REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED, REGARDING THIS SOFTWARE,
  19  * INCLUDING WITHOUT LIMITATION, ANY AND ALL IMPLIED WARRANTIES OF
  20  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT.
  21  * WHISTLE COMMUNICATIONS DOES NOT WARRANT, GUARANTEE, OR MAKE ANY
  22  * REPRESENTATIONS REGARDING THE USE OF, OR THE RESULTS OF THE USE OF THIS
  23  * SOFTWARE IN TERMS OF ITS CORRECTNESS, ACCURACY, RELIABILITY OR OTHERWISE.
  24  * IN NO EVENT SHALL WHISTLE COMMUNICATIONS BE LIABLE FOR ANY DAMAGES
  25  * RESULTING FROM OR ARISING OUT OF ANY USE OF THIS SOFTWARE, INCLUDING
  26  * WITHOUT LIMITATION, ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY,
  27  * PUNITIVE, OR CONSEQUENTIAL DAMAGES, PROCUREMENT OF SUBSTITUTE GOODS OR
  28  * SERVICES, LOSS OF USE, DATA OR PROFITS, HOWEVER CAUSED AND UNDER ANY
  29  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  31  * THIS SOFTWARE, EVEN IF WHISTLE COMMUNICATIONS IS ADVISED OF THE POSSIBILITY
  32  * OF SUCH DAMAGE.
  33  *
  34  * Copyright (c) 2007 Alexander Motin <mav@alkar.net>
  35  * All rights reserved.
  36  *
  37  * Redistribution and use in source and binary forms, with or without
  38  * modification, are permitted provided that the following conditions
  39  * are met:
  40  * 1. Redistributions of source code must retain the above copyright
  41  *    notice unmodified, this list of conditions, and the following
  42  *    disclaimer.
  43  * 2. Redistributions in binary form must reproduce the above copyright
  44  *    notice, this list of conditions and the following disclaimer in the
  45  *    documentation and/or other materials provided with the distribution.
  46  *
  47  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  48  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  49  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  50  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  51  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  52  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  53  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  54  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  55  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  56  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  57  * SUCH DAMAGE.
  58  *
  59  * Authors: Archie Cobbs <archie@freebsd.org>, Alexander Motin <mav@alkar.net>
  60  *
  61  * $FreeBSD$
  62  * $Whistle: ng_ppp.c,v 1.24 1999/11/01 09:24:52 julian Exp $
  63  */
  64
  65 /*
  66  * PPP node type data-flow.
  67  *
  68  *       hook      xmit        layer         recv      hook
  69  *              ------------------------------------
  70  *       inet ->                                    -> inet
  71  *       ipv6 ->                                    -> ipv6
  72  *        ipx ->               proto                -> ipx
  73  *      atalk ->                                    -> atalk
  74  *     bypass ->                                    -> bypass
  75  *              -hcomp_xmit()----------proto_recv()-
  76  *     vjc_ip <-                                    <- vjc_ip
  77  *   vjc_comp ->         header compression         -> vjc_comp
  78  * vjc_uncomp ->                                    -> vjc_uncomp
  79  *   vjc_vjip ->
  80  *              -comp_xmit()-----------hcomp_recv()-
  81  *   compress <-            compression             <- decompress
  82  *   compress ->                                    -> decompress
  83  *              -crypt_xmit()-----------comp_recv()-
  84  *    encrypt <-             encryption             <- decrypt
  85  *    encrypt ->                                    -> decrypt
  86  *              -ml_xmit()-------------crypt_recv()-
  87  *                           multilink
  88  *              -link_xmit()--------------ml_recv()-
  89  *      linkX <-               link                 <- linkX
  90  *
  91  */
  92
  93 #include <sys/param.h>
  94 #include <sys/systm.h>
  95 #include <sys/kernel.h>
  96 #include <sys/limits.h>
  97 #include <sys/time.h>
  98 #include <sys/mbuf.h>
  99 #include <sys/malloc.h>
 100 #include <sys/endian.h>
 101 #include <sys/errno.h>
 102 #include <sys/ctype.h>
 103
 104 #include <netgraph/ng_message.h>
 105 #include <netgraph/netgraph.h>
 106 #include <netgraph/ng_parse.h>
 107 #include <netgraph/ng_ppp.h>
 108 #include <netgraph/ng_vjc.h>
 109
 110 #ifdef NG_SEPARATE_MALLOC
 111 MALLOC_DEFINE(M_NETGRAPH_PPP, "netgraph_ppp", "netgraph ppp node");
 112 #else
 113 #define M_NETGRAPH_PPP M_NETGRAPH
 114 #endif
 115
 116 #define PROT_VALID(p)           (((p) & 0x0101) == 0x0001)
 117 #define PROT_COMPRESSABLE(p)    (((p) & 0xff00) == 0x0000)
 118
 119 /* Some PPP protocol numbers we're interested in */
 120 #define PROT_ATALK              0x0029
 121 #define PROT_COMPD              0x00fd
 122 #define PROT_CRYPTD             0x0053
 123 #define PROT_IP                 0x0021
 124 #define PROT_IPV6               0x0057
 125 #define PROT_IPX                0x002b
 126 #define PROT_LCP                0xc021
 127 #define PROT_MP                 0x003d
 128 #define PROT_VJCOMP             0x002d
 129 #define PROT_VJUNCOMP           0x002f
 130
 131 /* Multilink PPP definitions */
 132 #define MP_INITIAL_SEQ          0               /* per RFC 1990 */
 133 #define MP_MIN_LINK_MRU         32
 134
 135 #define MP_SHORT_SEQ_MASK       0x00000fff      /* short seq # mask */
 136 #define MP_SHORT_SEQ_HIBIT      0x00000800      /* short seq # high bit */
 137 #define MP_SHORT_FIRST_FLAG     0x00008000      /* first fragment in frame */
 138 #define MP_SHORT_LAST_FLAG      0x00004000      /* last fragment in frame */
 139
 140 #define MP_LONG_SEQ_MASK        0x00ffffff      /* long seq # mask */
 141 #define MP_LONG_SEQ_HIBIT       0x00800000      /* long seq # high bit */
 142 #define MP_LONG_FIRST_FLAG      0x80000000      /* first fragment in frame */
 143 #define MP_LONG_LAST_FLAG       0x40000000      /* last fragment in frame */
 144
 145 #define MP_NOSEQ                0x7fffffff      /* impossible sequence number */
 146
 147 /* Sign extension of MP sequence numbers */
 148 #define MP_SHORT_EXTEND(s)      (((s) & MP_SHORT_SEQ_HIBIT) ?           \
 149                                     ((s) | ~MP_SHORT_SEQ_MASK)          \
 150                                     : ((s) & MP_SHORT_SEQ_MASK))
 151 #define MP_LONG_EXTEND(s)       (((s) & MP_LONG_SEQ_HIBIT) ?            \
 152                                     ((s) | ~MP_LONG_SEQ_MASK)           \
 153                                     : ((s) & MP_LONG_SEQ_MASK))
 154
 155 /* Comparision of MP sequence numbers. Note: all sequence numbers
 156    except priv->xseq are stored with the sign bit extended. */
 157 #define MP_SHORT_SEQ_DIFF(x,y)  MP_SHORT_EXTEND((x) - (y))
 158 #define MP_LONG_SEQ_DIFF(x,y)   MP_LONG_EXTEND((x) - (y))
 159
 160 #define MP_RECV_SEQ_DIFF(priv,x,y)                                      \
 161                                 ((priv)->conf.recvShortSeq ?            \
 162                                     MP_SHORT_SEQ_DIFF((x), (y)) :       \
 163                                     MP_LONG_SEQ_DIFF((x), (y)))
 164
 165 /* Increment receive sequence number */
 166 #define MP_NEXT_RECV_SEQ(priv,seq)                                      \
 167                                 ((priv)->conf.recvShortSeq ?            \
 168                                     MP_SHORT_EXTEND((seq) + 1) :        \
 169                                     MP_LONG_EXTEND((seq) + 1))
 170
 171 /* Don't fragment transmitted packets to parts smaller than this */
 172 #define MP_MIN_FRAG_LEN         32
 173
 174 /* Maximum fragment reasssembly queue length */
 175 #define MP_MAX_QUEUE_LEN        128
 176
 177 /* Fragment queue scanner period */
 178 #define MP_FRAGTIMER_INTERVAL   (hz/2)
 179
 180 /* Average link overhead. XXX: Should be given by user-level */
 181 #define MP_AVERAGE_LINK_OVERHEAD        16
 182
 183 /* Keep this equal to ng_ppp_hook_names lower! */
 184 #define HOOK_INDEX_MAX          13
 185
 186 /* We store incoming fragments this way */
 187 struct ng_ppp_frag {
 188         int                             seq;            /* fragment seq# */
 189         uint8_t                         first;          /* First in packet? */
 190         uint8_t                         last;           /* Last in packet? */
 191         struct timeval                  timestamp;      /* time of reception */
 192         struct mbuf                     *data;          /* Fragment data */
 193         TAILQ_ENTRY(ng_ppp_frag)        f_qent;         /* Fragment queue */
 194 };
 195
 196 /* Per-link private information */
 197 struct ng_ppp_link {
 198         struct ng_ppp_link_conf conf;           /* link configuration */
 199         struct ng_ppp_link_stat64       stats;  /* link stats */
 200         hook_p                  hook;           /* connection to link data */
 201         int32_t                 seq;            /* highest rec'd seq# - MSEQ */
 202         uint32_t                latency;        /* calculated link latency */
 203         struct timeval          lastWrite;      /* time of last write for MP */
 204         int                     bytesInQueue;   /* bytes in the output queue for MP */
 205 };
 206
 207 /* Total per-node private information */
 208 struct ng_ppp_private {
 209         struct ng_ppp_bund_conf conf;                   /* bundle config */
 210         struct ng_ppp_link_stat64       bundleStats;    /* bundle stats */
 211         struct ng_ppp_link      links[NG_PPP_MAX_LINKS];/* per-link info */
 212         int32_t                 xseq;                   /* next out MP seq # */
 213         int32_t                 mseq;                   /* min links[i].seq */
 214         uint16_t                activeLinks[NG_PPP_MAX_LINKS];  /* indicies */
 215         uint16_t                numActiveLinks;         /* how many links up */
 216         uint16_t                lastLink;               /* for round robin */
 217         uint8_t                 vjCompHooked;           /* VJ comp hooked up? */
 218         uint8_t                 allLinksEqual;          /* all xmit the same? */
 219         hook_p                  hooks[HOOK_INDEX_MAX];  /* non-link hooks */
 220         struct ng_ppp_frag      fragsmem[MP_MAX_QUEUE_LEN]; /* fragments storage */
 221         TAILQ_HEAD(ng_ppp_fraglist, ng_ppp_frag)        /* fragment queue */
 222                                 frags;
 223         TAILQ_HEAD(ng_ppp_fragfreelist, ng_ppp_frag)    /* free fragment queue */
 224                                 fragsfree;
 225         struct callout          fragTimer;              /* fraq queue check */
 226         struct mtx              rmtx;                   /* recv mutex */
 227         struct mtx              xmtx;                   /* xmit mutex */
 228 };
 229 typedef struct ng_ppp_private *priv_p;
 230
 231 /* Netgraph node methods */
 232 static ng_constructor_t ng_ppp_constructor;
 233 static ng_rcvmsg_t      ng_ppp_rcvmsg;
 234 static ng_shutdown_t    ng_ppp_shutdown;
 235 static ng_newhook_t     ng_ppp_newhook;
 236 static ng_rcvdata_t     ng_ppp_rcvdata;
 237 static ng_disconnect_t  ng_ppp_disconnect;
 238
 239 static ng_rcvdata_t     ng_ppp_rcvdata_inet;
 240 static ng_rcvdata_t     ng_ppp_rcvdata_ipv6;
 241 static ng_rcvdata_t     ng_ppp_rcvdata_ipx;
 242 static ng_rcvdata_t     ng_ppp_rcvdata_atalk;
 243 static ng_rcvdata_t     ng_ppp_rcvdata_bypass;
 244
 245 static ng_rcvdata_t     ng_ppp_rcvdata_vjc_ip;
 246 static ng_rcvdata_t     ng_ppp_rcvdata_vjc_comp;
 247 static ng_rcvdata_t     ng_ppp_rcvdata_vjc_uncomp;
 248 static ng_rcvdata_t     ng_ppp_rcvdata_vjc_vjip;
 249
 250 static ng_rcvdata_t     ng_ppp_rcvdata_compress;
 251 static ng_rcvdata_t     ng_ppp_rcvdata_decompress;
 252
 253 static ng_rcvdata_t     ng_ppp_rcvdata_encrypt;
 254 static ng_rcvdata_t     ng_ppp_rcvdata_decrypt;
 255
 256 /* We use integer indicies to refer to the non-link hooks. */
 257 static const struct {
 258         char *const name;
 259         ng_rcvdata_t *fn;
 260 } ng_ppp_hook_names[] = {
 261 #define HOOK_INDEX_ATALK        0
 262         { NG_PPP_HOOK_ATALK,    ng_ppp_rcvdata_atalk },
 263 #define HOOK_INDEX_BYPASS       1
 264         { NG_PPP_HOOK_BYPASS,   ng_ppp_rcvdata_bypass },
 265 #define HOOK_INDEX_COMPRESS     2
 266         { NG_PPP_HOOK_COMPRESS, ng_ppp_rcvdata_compress },
 267 #define HOOK_INDEX_ENCRYPT      3
 268         { NG_PPP_HOOK_ENCRYPT,  ng_ppp_rcvdata_encrypt },
 269 #define HOOK_INDEX_DECOMPRESS   4
 270         { NG_PPP_HOOK_DECOMPRESS, ng_ppp_rcvdata_decompress },
 271 #define HOOK_INDEX_DECRYPT      5
 272         { NG_PPP_HOOK_DECRYPT,  ng_ppp_rcvdata_decrypt },
 273 #define HOOK_INDEX_INET         6
 274         { NG_PPP_HOOK_INET,     ng_ppp_rcvdata_inet },
 275 #define HOOK_INDEX_IPX          7
 276         { NG_PPP_HOOK_IPX,      ng_ppp_rcvdata_ipx },
 277 #define HOOK_INDEX_VJC_COMP     8
 278         { NG_PPP_HOOK_VJC_COMP, ng_ppp_rcvdata_vjc_comp },
 279 #define HOOK_INDEX_VJC_IP       9
 280         { NG_PPP_HOOK_VJC_IP,   ng_ppp_rcvdata_vjc_ip },
 281 #define HOOK_INDEX_VJC_UNCOMP   10
 282         { NG_PPP_HOOK_VJC_UNCOMP, ng_ppp_rcvdata_vjc_uncomp },
 283 #define HOOK_INDEX_VJC_VJIP     11
 284         { NG_PPP_HOOK_VJC_VJIP, ng_ppp_rcvdata_vjc_vjip },
 285 #define HOOK_INDEX_IPV6         12
 286         { NG_PPP_HOOK_IPV6,     ng_ppp_rcvdata_ipv6 },
 287         { NULL, NULL }
 288 };
 289
 290 /* Helper functions */
 291 static int      ng_ppp_proto_recv(node_p node, item_p item, uint16_t proto,
 292                     uint16_t linkNum);
 293 static int      ng_ppp_hcomp_xmit(node_p node, item_p item, uint16_t proto);
 294 static int      ng_ppp_hcomp_recv(node_p node, item_p item, uint16_t proto,
 295                     uint16_t linkNum);
 296 static int      ng_ppp_comp_xmit(node_p node, item_p item, uint16_t proto);
 297 static int      ng_ppp_comp_recv(node_p node, item_p item, uint16_t proto,
 298                     uint16_t linkNum);
 299 static int      ng_ppp_crypt_xmit(node_p node, item_p item, uint16_t proto);
 300 static int      ng_ppp_crypt_recv(node_p node, item_p item, uint16_t proto,
 301                     uint16_t linkNum);
 302 static int      ng_ppp_mp_xmit(node_p node, item_p item, uint16_t proto);
 303 static int      ng_ppp_mp_recv(node_p node, item_p item, uint16_t proto,
 304                     uint16_t linkNum);
 305 static int      ng_ppp_link_xmit(node_p node, item_p item, uint16_t proto,
 306                     uint16_t linkNum, int plen);
 307
 308 static int      ng_ppp_bypass(node_p node, item_p item, uint16_t proto,
 309                     uint16_t linkNum);
 310
 311 static void     ng_ppp_bump_mseq(node_p node, int32_t new_mseq);
 312 static int      ng_ppp_frag_drop(node_p node);
 313 static int      ng_ppp_check_packet(node_p node);
 314 static void     ng_ppp_get_packet(node_p node, struct mbuf **mp);
 315 static int      ng_ppp_frag_process(node_p node, item_p oitem);
 316 static int      ng_ppp_frag_trim(node_p node);
 317 static void     ng_ppp_frag_timeout(node_p node, hook_p hook, void *arg1,
 318                     int arg2);
 319 static void     ng_ppp_frag_checkstale(node_p node);
 320 static void     ng_ppp_frag_reset(node_p node);
 321 static void     ng_ppp_mp_strategy(node_p node, int len, int *distrib);
 322 static int      ng_ppp_intcmp(void *latency, const void *v1, const void *v2);
 323 static struct mbuf *ng_ppp_addproto(struct mbuf *m, uint16_t proto, int compOK);
 324 static struct mbuf *ng_ppp_cutproto(struct mbuf *m, uint16_t *proto);
 325 static struct mbuf *ng_ppp_prepend(struct mbuf *m, const void *buf, int len);
 326 static int      ng_ppp_config_valid(node_p node,
 327                     const struct ng_ppp_node_conf *newConf);
 328 static void     ng_ppp_update(node_p node, int newConf);
 329 static void     ng_ppp_start_frag_timer(node_p node);
 330 static void     ng_ppp_stop_frag_timer(node_p node);
 331
 332 /* Parse type for struct ng_ppp_mp_state_type */
 333 static const struct ng_parse_fixedarray_info ng_ppp_rseq_array_info = {
 334         &ng_parse_hint32_type,
 335         NG_PPP_MAX_LINKS
 336 };
 337 static const struct ng_parse_type ng_ppp_rseq_array_type = {
 338         &ng_parse_fixedarray_type,
 339         &ng_ppp_rseq_array_info,
 340 };
 341 static const struct ng_parse_struct_field ng_ppp_mp_state_type_fields[]
 342         = NG_PPP_MP_STATE_TYPE_INFO(&ng_ppp_rseq_array_type);
 343 static const struct ng_parse_type ng_ppp_mp_state_type = {
 344         &ng_parse_struct_type,
 345         &ng_ppp_mp_state_type_fields
 346 };
 347
 348 /* Parse type for struct ng_ppp_link_conf */
 349 static const struct ng_parse_struct_field ng_ppp_link_type_fields[]
 350         = NG_PPP_LINK_TYPE_INFO;
 351 static const struct ng_parse_type ng_ppp_link_type = {
 352         &ng_parse_struct_type,
 353         &ng_ppp_link_type_fields
 354 };
 355
 356 /* Parse type for struct ng_ppp_bund_conf */
 357 static const struct ng_parse_struct_field ng_ppp_bund_type_fields[]
 358         = NG_PPP_BUND_TYPE_INFO;
 359 static const struct ng_parse_type ng_ppp_bund_type = {
 360         &ng_parse_struct_type,
 361         &ng_ppp_bund_type_fields
 362 };
 363
 364 /* Parse type for struct ng_ppp_node_conf */
 365 static const struct ng_parse_fixedarray_info ng_ppp_array_info = {
 366         &ng_ppp_link_type,
 367         NG_PPP_MAX_LINKS
 368 };
 369 static const struct ng_parse_type ng_ppp_link_array_type = {
 370         &ng_parse_fixedarray_type,
 371         &ng_ppp_array_info,
 372 };
 373 static const struct ng_parse_struct_field ng_ppp_conf_type_fields[]
 374         = NG_PPP_CONFIG_TYPE_INFO(&ng_ppp_bund_type, &ng_ppp_link_array_type);
 375 static const struct ng_parse_type ng_ppp_conf_type = {
 376         &ng_parse_struct_type,
 377         &ng_ppp_conf_type_fields
 378 };
 379
 380 /* Parse type for struct ng_ppp_link_stat */
 381 static const struct ng_parse_struct_field ng_ppp_stats_type_fields[]
 382         = NG_PPP_STATS_TYPE_INFO;
 383 static const struct ng_parse_type ng_ppp_stats_type = {
 384         &ng_parse_struct_type,
 385         &ng_ppp_stats_type_fields
 386 };
 387
 388 /* Parse type for struct ng_ppp_link_stat64 */
 389 static const struct ng_parse_struct_field ng_ppp_stats64_type_fields[]
 390         = NG_PPP_STATS64_TYPE_INFO;
 391 static const struct ng_parse_type ng_ppp_stats64_type = {
 392         &ng_parse_struct_type,
 393         &ng_ppp_stats64_type_fields
 394 };
 395
 396 /* List of commands and how to convert arguments to/from ASCII */
 397 static const struct ng_cmdlist ng_ppp_cmds[] = {
 398         {
 399           NGM_PPP_COOKIE,
 400           NGM_PPP_SET_CONFIG,
 401           "setconfig",
 402           &ng_ppp_conf_type,
 403           NULL
 404         },
 405         {
 406           NGM_PPP_COOKIE,
 407           NGM_PPP_GET_CONFIG,
 408           "getconfig",
 409           NULL,
 410           &ng_ppp_conf_type
 411         },
 412         {
 413           NGM_PPP_COOKIE,
 414           NGM_PPP_GET_MP_STATE,
 415           "getmpstate",
 416           NULL,
 417           &ng_ppp_mp_state_type
 418         },
 419         {
 420           NGM_PPP_COOKIE,
 421           NGM_PPP_GET_LINK_STATS,
 422           "getstats",
 423           &ng_parse_int16_type,
 424           &ng_ppp_stats_type
 425         },
 426         {
 427           NGM_PPP_COOKIE,
 428           NGM_PPP_CLR_LINK_STATS,
 429           "clrstats",
 430           &ng_parse_int16_type,
 431           NULL
 432         },
 433         {
 434           NGM_PPP_COOKIE,
 435           NGM_PPP_GETCLR_LINK_STATS,
 436           "getclrstats",
 437           &ng_parse_int16_type,
 438           &ng_ppp_stats_type
 439         },
 440         {
 441           NGM_PPP_COOKIE,
 442           NGM_PPP_GET_LINK_STATS64,
 443           "getstats64",
 444           &ng_parse_int16_type,
 445           &ng_ppp_stats64_type
 446         },
 447         {
 448           NGM_PPP_COOKIE,
 449           NGM_PPP_GETCLR_LINK_STATS64,
 450           "getclrstats64",
 451           &ng_parse_int16_type,
 452           &ng_ppp_stats64_type
 453         },
 454         { 0 }
 455 };
 456
 457 /* Node type descriptor */
 458 static struct ng_type ng_ppp_typestruct = {
 459         .version =      NG_ABI_VERSION,
 460         .name =         NG_PPP_NODE_TYPE,
 461         .constructor =  ng_ppp_constructor,
 462         .rcvmsg =       ng_ppp_rcvmsg,
 463         .shutdown =     ng_ppp_shutdown,
 464         .newhook =      ng_ppp_newhook,
 465         .rcvdata =      ng_ppp_rcvdata,
 466         .disconnect =   ng_ppp_disconnect,
 467         .cmdlist =      ng_ppp_cmds,
 468 };
 469 NETGRAPH_INIT(ppp, &ng_ppp_typestruct);
 470
 471 /* Address and control field header */
 472 static const uint8_t ng_ppp_acf[2] = { 0xff, 0x03 };
 473
 474 /* Maximum time we'll let a complete incoming packet sit in the queue */
 475 static const struct timeval ng_ppp_max_staleness = { 2, 0 };    /* 2 seconds */
 476
 477 #define ERROUT(x)       do { error = (x); goto done; } while (0)
 478
 479 /************************************************************************
 480                         NETGRAPH NODE STUFF
 481  ************************************************************************/
 482
 483 /*
 484  * Node type constructor
 485  */
 486 static int
 487 ng_ppp_constructor(node_p node)
 488 {
 489         priv_p priv;
 490         int i;
 491
 492         /* Allocate private structure */
 493         priv = malloc(sizeof(*priv), M_NETGRAPH_PPP, M_NOWAIT | M_ZERO);
 494         if (priv == NULL)
 495                 return (ENOMEM);
 496
 497         NG_NODE_SET_PRIVATE(node, priv);
 498
 499         /* Initialize state */
 500         TAILQ_INIT(&priv->frags);
 501         TAILQ_INIT(&priv->fragsfree);
 502         for (i = 0; i < MP_MAX_QUEUE_LEN; i++)
 503                 TAILQ_INSERT_TAIL(&priv->fragsfree, &priv->fragsmem[i], f_qent);
 504         for (i = 0; i < NG_PPP_MAX_LINKS; i++)
 505                 priv->links[i].seq = MP_NOSEQ;
 506         ng_callout_init(&priv->fragTimer);
 507
 508         mtx_init(&priv->rmtx, "ng_ppp_recv", NULL, MTX_DEF);
 509         mtx_init(&priv->xmtx, "ng_ppp_xmit", NULL, MTX_DEF);
 510
 511         /* Done */
 512         return (0);
 513 }
 514
 515 /*
 516  * Give our OK for a hook to be added
 517  */
 518 static int
 519 ng_ppp_newhook(node_p node, hook_p hook, const char *name)
 520 {
 521         const priv_p priv = NG_NODE_PRIVATE(node);
 522         hook_p *hookPtr = NULL;
 523         int linkNum = -1;
 524         int hookIndex = -1;
 525
 526         /* Figure out which hook it is */
 527         if (strncmp(name, NG_PPP_HOOK_LINK_PREFIX,      /* a link hook? */
 528             strlen(NG_PPP_HOOK_LINK_PREFIX)) == 0) {
 529                 const char *cp;
 530                 char *eptr;
 531
 532                 cp = name + strlen(NG_PPP_HOOK_LINK_PREFIX);
 533                 if (!isdigit(*cp) || (cp[0] == '0' && cp[1] != '\0'))
 534                         return (EINVAL);
 535                 linkNum = (int)strtoul(cp, &eptr, 10);
 536                 if (*eptr != '\0' || linkNum < 0 || linkNum >= NG_PPP_MAX_LINKS)
 537                         return (EINVAL);
 538                 hookPtr = &priv->links[linkNum].hook;
 539                 hookIndex = ~linkNum;
 540
 541                 /* See if hook is already connected. */
 542                 if (*hookPtr != NULL)
 543                         return (EISCONN);
 544
 545                 /* Disallow more than one link unless multilink is enabled. */
 546                 if (priv->links[linkNum].conf.enableLink &&
 547                     !priv->conf.enableMultilink && priv->numActiveLinks >= 1)
 548                         return (ENODEV);
 549
 550         } else {                                /* must be a non-link hook */
 551                 int i;
 552
 553                 for (i = 0; ng_ppp_hook_names[i].name != NULL; i++) {
 554                         if (strcmp(name, ng_ppp_hook_names[i].name) == 0) {
 555                                 hookPtr = &priv->hooks[i];
 556                                 hookIndex = i;
 557                                 break;
 558                         }
 559                 }
 560                 if (ng_ppp_hook_names[i].name == NULL)
 561                         return (EINVAL);        /* no such hook */
 562
 563                 /* See if hook is already connected */
 564                 if (*hookPtr != NULL)
 565                         return (EISCONN);
 566
 567                 /* Every non-linkX hook have it's own function. */
 568                 NG_HOOK_SET_RCVDATA(hook, ng_ppp_hook_names[i].fn);
 569         }
 570
 571         /* OK */
 572         *hookPtr = hook;
 573         NG_HOOK_SET_PRIVATE(hook, (void *)(intptr_t)hookIndex);
 574         ng_ppp_update(node, 0);
 575         return (0);
 576 }
 577
 578 /*
 579  * Receive a control message
 580  */
 581 static int
 582 ng_ppp_rcvmsg(node_p node, item_p item, hook_p lasthook)
 583 {
 584         const priv_p priv = NG_NODE_PRIVATE(node);
 585         struct ng_mesg *resp = NULL;
 586         int error = 0;
 587         struct ng_mesg *msg;
 588
 589         NGI_GET_MSG(item, msg);
 590         switch (msg->header.typecookie) {
 591         case NGM_PPP_COOKIE:
 592                 switch (msg->header.cmd) {
 593                 case NGM_PPP_SET_CONFIG:
 594                     {
 595                         struct ng_ppp_node_conf *const conf =
 596                             (struct ng_ppp_node_conf *)msg->data;
 597                         int i;
 598
 599                         /* Check for invalid or illegal config */
 600                         if (msg->header.arglen != sizeof(*conf))
 601                                 ERROUT(EINVAL);
 602                         if (!ng_ppp_config_valid(node, conf))
 603                                 ERROUT(EINVAL);
 604
 605                         /* Copy config */
 606                         priv->conf = conf->bund;
 607                         for (i = 0; i < NG_PPP_MAX_LINKS; i++)
 608                                 priv->links[i].conf = conf->links[i];
 609                         ng_ppp_update(node, 1);
 610                         break;
 611                     }
 612                 case NGM_PPP_GET_CONFIG:
 613                     {
 614                         struct ng_ppp_node_conf *conf;
 615                         int i;
 616
 617                         NG_MKRESPONSE(resp, msg, sizeof(*conf), M_NOWAIT);
 618                         if (resp == NULL)
 619                                 ERROUT(ENOMEM);
 620                         conf = (struct ng_ppp_node_conf *)resp->data;
 621                         conf->bund = priv->conf;
 622                         for (i = 0; i < NG_PPP_MAX_LINKS; i++)
 623                                 conf->links[i] = priv->links[i].conf;
 624                         break;
 625                     }
 626                 case NGM_PPP_GET_MP_STATE:
 627                     {
 628                         struct ng_ppp_mp_state *info;
 629                         int i;
 630
 631                         NG_MKRESPONSE(resp, msg, sizeof(*info), M_NOWAIT);
 632                         if (resp == NULL)
 633                                 ERROUT(ENOMEM);
 634                         info = (struct ng_ppp_mp_state *)resp->data;
 635                         bzero(info, sizeof(*info));
 636                         for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
 637                                 if (priv->links[i].seq != MP_NOSEQ)
 638                                         info->rseq[i] = priv->links[i].seq;
 639                         }
 640                         info->mseq = priv->mseq;
 641                         info->xseq = priv->xseq;
 642                         break;
 643                     }
 644                 case NGM_PPP_GET_LINK_STATS:
 645                 case NGM_PPP_CLR_LINK_STATS:
 646                 case NGM_PPP_GETCLR_LINK_STATS:
 647                 case NGM_PPP_GET_LINK_STATS64:
 648                 case NGM_PPP_GETCLR_LINK_STATS64:
 649                     {
 650                         struct ng_ppp_link_stat64 *stats;
 651                         uint16_t linkNum;
 652
 653                         /* Process request. */
 654                         if (msg->header.arglen != sizeof(uint16_t))
 655                                 ERROUT(EINVAL);
 656                         linkNum = *((uint16_t *) msg->data);
 657                         if (linkNum >= NG_PPP_MAX_LINKS
 658                             && linkNum != NG_PPP_BUNDLE_LINKNUM)
 659                                 ERROUT(EINVAL);
 660                         stats = (linkNum == NG_PPP_BUNDLE_LINKNUM) ?
 661                             &priv->bundleStats : &priv->links[linkNum].stats;
 662
 663                         /* Make 64bit reply. */
 664                         if (msg->header.cmd == NGM_PPP_GET_LINK_STATS64 ||
 665                             msg->header.cmd == NGM_PPP_GETCLR_LINK_STATS64) {
 666                                 NG_MKRESPONSE(resp, msg,
 667                                     sizeof(struct ng_ppp_link_stat64), M_NOWAIT);
 668                                 if (resp == NULL)
 669                                         ERROUT(ENOMEM);
 670                                 bcopy(stats, resp->data, sizeof(*stats));
 671                         } else
 672                         /* Make 32bit reply. */
 673                         if (msg->header.cmd == NGM_PPP_GET_LINK_STATS ||
 674                             msg->header.cmd == NGM_PPP_GETCLR_LINK_STATS) {
 675                                 struct ng_ppp_link_stat *rs;
 676                                 NG_MKRESPONSE(resp, msg,
 677                                     sizeof(struct ng_ppp_link_stat), M_NOWAIT);
 678                                 if (resp == NULL)
 679                                         ERROUT(ENOMEM);
 680                                 rs = (struct ng_ppp_link_stat *)resp->data;
 681                                 /* Truncate 64->32 bits. */
 682                                 rs->xmitFrames = stats->xmitFrames;
 683                                 rs->xmitOctets = stats->xmitOctets;
 684                                 rs->recvFrames = stats->recvFrames;
 685                                 rs->recvOctets = stats->recvOctets;
 686                                 rs->badProtos = stats->badProtos;
 687                                 rs->runts = stats->runts;
 688                                 rs->dupFragments = stats->dupFragments;
 689                                 rs->dropFragments = stats->dropFragments;
 690                         }
 691                         /* Clear stats. */
 692                         if (msg->header.cmd != NGM_PPP_GET_LINK_STATS &&
 693                             msg->header.cmd != NGM_PPP_GET_LINK_STATS64)
 694                                 bzero(stats, sizeof(*stats));
 695                         break;
 696                     }
 697                 default:
 698                         error = EINVAL;
 699                         break;
 700                 }
 701                 break;
 702         case NGM_VJC_COOKIE:
 703             {
 704                 /*
 705                  * Forward it to the vjc node. leave the
 706                  * old return address alone.
 707                  * If we have no hook, let NG_RESPOND_MSG
 708                  * clean up any remaining resources.
 709                  * Because we have no resp, the item will be freed
 710                  * along with anything it references. Don't
 711                  * let msg be freed twice.
 712                  */
 713                 NGI_MSG(item) = msg;    /* put it back in the item */
 714                 msg = NULL;
 715                 if ((lasthook = priv->hooks[HOOK_INDEX_VJC_IP])) {
 716                         NG_FWD_ITEM_HOOK(error, item, lasthook);
 717                 }
 718                 return (error);
 719             }
 720         default:
 721                 error = EINVAL;
 722                 break;
 723         }
 724 done:
 725         NG_RESPOND_MSG(error, node, item, resp);
 726         NG_FREE_MSG(msg);
 727         return (error);
 728 }
 729
 730 /*
 731  * Destroy node
 732  */
 733 static int
 734 ng_ppp_shutdown(node_p node)
 735 {
 736         const priv_p priv = NG_NODE_PRIVATE(node);
 737
 738         /* Stop fragment queue timer */
 739         ng_ppp_stop_frag_timer(node);
 740
 741         /* Take down netgraph node */
 742         ng_ppp_frag_reset(node);
 743         mtx_destroy(&priv->rmtx);
 744         mtx_destroy(&priv->xmtx);
 745         bzero(priv, sizeof(*priv));
 746         free(priv, M_NETGRAPH_PPP);
 747         NG_NODE_SET_PRIVATE(node, NULL);
 748         NG_NODE_UNREF(node);            /* let the node escape */
 749         return (0);
 750 }
 751
 752 /*
 753  * Hook disconnection
 754  */
 755 static int
 756 ng_ppp_disconnect(hook_p hook)
 757 {
 758         const node_p node = NG_HOOK_NODE(hook);
 759         const priv_p priv = NG_NODE_PRIVATE(node);
 760         const int index = (intptr_t)NG_HOOK_PRIVATE(hook);
 761
 762         /* Zero out hook pointer */
 763         if (index < 0)
 764                 priv->links[~index].hook = NULL;
 765         else
 766                 priv->hooks[index] = NULL;
 767
 768         /* Update derived info (or go away if no hooks left). */
 769         if (NG_NODE_NUMHOOKS(node) > 0)
 770                 ng_ppp_update(node, 0);
 771         else if (NG_NODE_IS_VALID(node))
 772                 ng_rmnode_self(node);
 773
 774         return (0);
 775 }
 776
 777 /*
 778  * Proto layer
 779  */
 780
 781 /*
 782  * Receive data on a hook inet.
 783  */
 784 static int
 785 ng_ppp_rcvdata_inet(hook_p hook, item_p item)
 786 {
 787         const node_p node = NG_HOOK_NODE(hook);
 788         const priv_p priv = NG_NODE_PRIVATE(node);
 789
 790         if (!priv->conf.enableIP) {
 791                 NG_FREE_ITEM(item);
 792                 return (ENXIO);
 793         }
 794         return (ng_ppp_hcomp_xmit(NG_HOOK_NODE(hook), item, PROT_IP));
 795 }
 796
 797 /*
 798  * Receive data on a hook ipv6.
 799  */
 800 static int
 801 ng_ppp_rcvdata_ipv6(hook_p hook, item_p item)
 802 {
 803         const node_p node = NG_HOOK_NODE(hook);
 804         const priv_p priv = NG_NODE_PRIVATE(node);
 805
 806         if (!priv->conf.enableIPv6) {
 807                 NG_FREE_ITEM(item);
 808                 return (ENXIO);
 809         }
 810         return (ng_ppp_hcomp_xmit(NG_HOOK_NODE(hook), item, PROT_IPV6));
 811 }
 812
 813 /*
 814  * Receive data on a hook atalk.
 815  */
 816 static int
 817 ng_ppp_rcvdata_atalk(hook_p hook, item_p item)
 818 {
 819         const node_p node = NG_HOOK_NODE(hook);
 820         const priv_p priv = NG_NODE_PRIVATE(node);
 821
 822         if (!priv->conf.enableAtalk) {
 823                 NG_FREE_ITEM(item);
 824                 return (ENXIO);
 825         }
 826         return (ng_ppp_hcomp_xmit(NG_HOOK_NODE(hook), item, PROT_ATALK));
 827 }
 828
 829 /*
 830  * Receive data on a hook ipx
 831  */
 832 static int
 833 ng_ppp_rcvdata_ipx(hook_p hook, item_p item)
 834 {
 835         const node_p node = NG_HOOK_NODE(hook);
 836         const priv_p priv = NG_NODE_PRIVATE(node);
 837
 838         if (!priv->conf.enableIPX) {
 839                 NG_FREE_ITEM(item);
 840                 return (ENXIO);
 841         }
 842         return (ng_ppp_hcomp_xmit(NG_HOOK_NODE(hook), item, PROT_IPX));
 843 }
 844
 845 /*
 846  * Receive data on a hook bypass
 847  */
 848 static int
 849 ng_ppp_rcvdata_bypass(hook_p hook, item_p item)
 850 {
 851         uint16_t linkNum;
 852         uint16_t proto;
 853         struct mbuf *m;
 854
 855         NGI_GET_M(item, m);
 856         if (m->m_pkthdr.len < 4) {
 857                 NG_FREE_ITEM(item);
 858                 return (EINVAL);
 859         }
 860         if (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL) {
 861                 NG_FREE_ITEM(item);
 862                 return (ENOBUFS);
 863         }
 864         linkNum = be16dec(mtod(m, uint8_t *));
 865         proto = be16dec(mtod(m, uint8_t *) + 2);
 866         m_adj(m, 4);
 867         NGI_M(item) = m;
 868
 869         if (linkNum == NG_PPP_BUNDLE_LINKNUM)
 870                 return (ng_ppp_hcomp_xmit(NG_HOOK_NODE(hook), item, proto));
 871         else
 872                 return (ng_ppp_link_xmit(NG_HOOK_NODE(hook), item, proto,
 873                     linkNum, 0));
 874 }
 875
 876 static int
 877 ng_ppp_bypass(node_p node, item_p item, uint16_t proto, uint16_t linkNum)
 878 {
 879         const priv_p priv = NG_NODE_PRIVATE(node);
 880         uint16_t hdr[2];
 881         struct mbuf *m;
 882         int error;
 883
 884         if (priv->hooks[HOOK_INDEX_BYPASS] == NULL) {
 885             NG_FREE_ITEM(item);
 886             return (ENXIO);
 887         }
 888
 889         /* Add 4-byte bypass header. */
 890         hdr[0] = htons(linkNum);
 891         hdr[1] = htons(proto);
 892
 893         NGI_GET_M(item, m);
 894         if ((m = ng_ppp_prepend(m, &hdr, 4)) == NULL) {
 895                 NG_FREE_ITEM(item);
 896                 return (ENOBUFS);
 897         }
 898         NGI_M(item) = m;
 899
 900         /* Send packet out hook. */
 901         NG_FWD_ITEM_HOOK(error, item, priv->hooks[HOOK_INDEX_BYPASS]);
 902         return (error);
 903 }
 904
 905 static int
 906 ng_ppp_proto_recv(node_p node, item_p item, uint16_t proto, uint16_t linkNum)
 907 {
 908         const priv_p priv = NG_NODE_PRIVATE(node);
 909         hook_p outHook = NULL;
 910         int error;
 911 #ifdef ALIGNED_POINTER
 912         struct mbuf *m, *n;
 913
 914         NGI_GET_M(item, m);
 915         if (!ALIGNED_POINTER(mtod(m, caddr_t), uint32_t)) {
 916                 n = m_defrag(m, M_NOWAIT);
 917                 if (n == NULL) {
 918                         m_freem(m);
 919                         NG_FREE_ITEM(item);
 920                         return (ENOBUFS);
 921                 }
 922                 m = n;
 923         }
 924         NGI_M(item) = m;
 925 #endif /* ALIGNED_POINTER */
 926         switch (proto) {
 927             case PROT_IP:
 928                 if (priv->conf.enableIP)
 929                     outHook = priv->hooks[HOOK_INDEX_INET];
 930                 break;
 931             case PROT_IPV6:
 932                 if (priv->conf.enableIPv6)
 933                     outHook = priv->hooks[HOOK_INDEX_IPV6];
 934                 break;
 935             case PROT_ATALK:
 936                 if (priv->conf.enableAtalk)
 937                     outHook = priv->hooks[HOOK_INDEX_ATALK];
 938                 break;
 939             case PROT_IPX:
 940                 if (priv->conf.enableIPX)
 941                     outHook = priv->hooks[HOOK_INDEX_IPX];
 942                 break;
 943         }
 944
 945         if (outHook == NULL)
 946                 return (ng_ppp_bypass(node, item, proto, linkNum));
 947
 948         /* Send packet out hook. */
 949         NG_FWD_ITEM_HOOK(error, item, outHook);
 950         return (error);
 951 }
 952
 953 /*
 954  * Header compression layer
 955  */
 956
 957 static int
 958 ng_ppp_hcomp_xmit(node_p node, item_p item, uint16_t proto)
 959 {
 960         const priv_p priv = NG_NODE_PRIVATE(node);
 961
 962         if (proto == PROT_IP &&
 963             priv->conf.enableVJCompression &&
 964             priv->vjCompHooked) {
 965                 int error;
 966
 967                 /* Send packet out hook. */
 968                 NG_FWD_ITEM_HOOK(error, item, priv->hooks[HOOK_INDEX_VJC_IP]);
 969                 return (error);
 970         }
 971
 972         return (ng_ppp_comp_xmit(node, item, proto));
 973 }
 974
 975 /*
 976  * Receive data on a hook vjc_comp.
 977  */
 978 static int
 979 ng_ppp_rcvdata_vjc_comp(hook_p hook, item_p item)
 980 {
 981         const node_p node = NG_HOOK_NODE(hook);
 982         const priv_p priv = NG_NODE_PRIVATE(node);
 983
 984         if (!priv->conf.enableVJCompression) {
 985                 NG_FREE_ITEM(item);
 986                 return (ENXIO);
 987         }
 988         return (ng_ppp_comp_xmit(node, item, PROT_VJCOMP));
 989 }
 990
 991 /*
 992  * Receive data on a hook vjc_uncomp.
 993  */
 994 static int
 995 ng_ppp_rcvdata_vjc_uncomp(hook_p hook, item_p item)
 996 {
 997         const node_p node = NG_HOOK_NODE(hook);
 998         const priv_p priv = NG_NODE_PRIVATE(node);
 999
1000         if (!priv->conf.enableVJCompression) {
1001                 NG_FREE_ITEM(item);
1002                 return (ENXIO);
1003         }
1004         return (ng_ppp_comp_xmit(node, item, PROT_VJUNCOMP));
1005 }
1006
1007 /*
1008  * Receive data on a hook vjc_vjip.
1009  */
1010 static int
1011 ng_ppp_rcvdata_vjc_vjip(hook_p hook, item_p item)
1012 {
1013         const node_p node = NG_HOOK_NODE(hook);
1014         const priv_p priv = NG_NODE_PRIVATE(node);
1015
1016         if (!priv->conf.enableVJCompression) {
1017                 NG_FREE_ITEM(item);
1018                 return (ENXIO);
1019         }
1020         return (ng_ppp_comp_xmit(node, item, PROT_IP));
1021 }
1022
1023 static int
1024 ng_ppp_hcomp_recv(node_p node, item_p item, uint16_t proto, uint16_t linkNum)
1025 {
1026         const priv_p priv = NG_NODE_PRIVATE(node);
1027
1028         if (priv->conf.enableVJDecompression && priv->vjCompHooked) {
1029                 hook_p outHook = NULL;
1030
1031                 switch (proto) {
1032                     case PROT_VJCOMP:
1033                         outHook = priv->hooks[HOOK_INDEX_VJC_COMP];
1034                         break;
1035                     case PROT_VJUNCOMP:
1036                         outHook = priv->hooks[HOOK_INDEX_VJC_UNCOMP];
1037                         break;
1038                 }
1039
1040                 if (outHook) {
1041                         int error;
1042
1043                         /* Send packet out hook. */
1044                         NG_FWD_ITEM_HOOK(error, item, outHook);
1045                         return (error);
1046                 }
1047         }
1048
1049         return (ng_ppp_proto_recv(node, item, proto, linkNum));
1050 }
1051
1052 /*
1053  * Receive data on a hook vjc_ip.
1054  */
1055 static int
1056 ng_ppp_rcvdata_vjc_ip(hook_p hook, item_p item)
1057 {
1058         const node_p node = NG_HOOK_NODE(hook);
1059         const priv_p priv = NG_NODE_PRIVATE(node);
1060
1061         if (!priv->conf.enableVJDecompression) {
1062                 NG_FREE_ITEM(item);
1063                 return (ENXIO);
1064         }
1065         return (ng_ppp_proto_recv(node, item, PROT_IP, NG_PPP_BUNDLE_LINKNUM));
1066 }
1067
1068 /*
1069  * Compression layer
1070  */
1071
1072 static int
1073 ng_ppp_comp_xmit(node_p node, item_p item, uint16_t proto)
1074 {
1075         const priv_p priv = NG_NODE_PRIVATE(node);
1076
1077         if (priv->conf.enableCompression &&
1078             proto < 0x4000 &&
1079             proto != PROT_COMPD &&
1080             proto != PROT_CRYPTD &&
1081             priv->hooks[HOOK_INDEX_COMPRESS] != NULL) {
1082                 struct mbuf *m;
1083                 int error;
1084
1085                 NGI_GET_M(item, m);
1086                 if ((m = ng_ppp_addproto(m, proto, 0)) == NULL) {
1087                         NG_FREE_ITEM(item);
1088                         return (ENOBUFS);
1089                 }
1090                 NGI_M(item) = m;
1091
1092                 /* Send packet out hook. */
1093                 NG_FWD_ITEM_HOOK(error, item, priv->hooks[HOOK_INDEX_COMPRESS]);
1094                 return (error);
1095         }
1096
1097         return (ng_ppp_crypt_xmit(node, item, proto));
1098 }
1099
1100 /*
1101  * Receive data on a hook compress.
1102  */
1103 static int
1104 ng_ppp_rcvdata_compress(hook_p hook, item_p item)
1105 {
1106         const node_p node = NG_HOOK_NODE(hook);
1107         const priv_p priv = NG_NODE_PRIVATE(node);
1108         uint16_t proto;
1109
1110         switch (priv->conf.enableCompression) {
1111             case NG_PPP_COMPRESS_NONE:
1112                 NG_FREE_ITEM(item);
1113                 return (ENXIO);
1114             case NG_PPP_COMPRESS_FULL:
1115                 {
1116                         struct mbuf *m;
1117
1118                         NGI_GET_M(item, m);
1119                         if ((m = ng_ppp_cutproto(m, &proto)) == NULL) {
1120                                 NG_FREE_ITEM(item);
1121                                 return (EIO);
1122                         }
1123                         NGI_M(item) = m;
1124                         if (!PROT_VALID(proto)) {
1125                                 NG_FREE_ITEM(item);
1126                                 return (EIO);
1127                         }
1128                 }
1129                 break;
1130             default:
1131                 proto = PROT_COMPD;
1132                 break;
1133         }
1134         return (ng_ppp_crypt_xmit(node, item, proto));
1135 }
1136
1137 static int
1138 ng_ppp_comp_recv(node_p node, item_p item, uint16_t proto, uint16_t linkNum)
1139 {
1140         const priv_p priv = NG_NODE_PRIVATE(node);
1141
1142         if (proto < 0x4000 &&
1143             ((proto == PROT_COMPD && priv->conf.enableDecompression) ||
1144             priv->conf.enableDecompression == NG_PPP_DECOMPRESS_FULL) &&
1145             priv->hooks[HOOK_INDEX_DECOMPRESS] != NULL) {
1146                 int error;
1147
1148                 if (priv->conf.enableDecompression == NG_PPP_DECOMPRESS_FULL) {
1149                         struct mbuf *m;
1150                         NGI_GET_M(item, m);
1151                         if ((m = ng_ppp_addproto(m, proto, 0)) == NULL) {
1152                                 NG_FREE_ITEM(item);
1153                                 return (EIO);
1154                         }
1155                         NGI_M(item) = m;
1156                 }
1157
1158                 /* Send packet out hook. */
1159                 NG_FWD_ITEM_HOOK(error, item,
1160                     priv->hooks[HOOK_INDEX_DECOMPRESS]);
1161                 return (error);
1162         } else if (proto == PROT_COMPD) {
1163                 /* Disabled protos MUST be silently discarded, but
1164                  * unsupported MUST not. Let user-level decide this. */
1165                 return (ng_ppp_bypass(node, item, proto, linkNum));
1166         }
1167
1168         return (ng_ppp_hcomp_recv(node, item, proto, linkNum));
1169 }
1170
1171 /*
1172  * Receive data on a hook decompress.
1173  */
1174 static int
1175 ng_ppp_rcvdata_decompress(hook_p hook, item_p item)
1176 {
1177         const node_p node = NG_HOOK_NODE(hook);
1178         const priv_p priv = NG_NODE_PRIVATE(node);
1179         uint16_t proto;
1180         struct mbuf *m;
1181
1182         if (!priv->conf.enableDecompression) {
1183                 NG_FREE_ITEM(item);
1184                 return (ENXIO);
1185         }
1186         NGI_GET_M(item, m);
1187         if ((m = ng_ppp_cutproto(m, &proto)) == NULL) {
1188                 NG_FREE_ITEM(item);
1189                 return (EIO);
1190         }
1191         NGI_M(item) = m;
1192         if (!PROT_VALID(proto)) {
1193                 priv->bundleStats.badProtos++;
1194                 NG_FREE_ITEM(item);
1195                 return (EIO);
1196         }
1197         return (ng_ppp_hcomp_recv(node, item, proto, NG_PPP_BUNDLE_LINKNUM));
1198 }
1199
1200 /*
1201  * Encryption layer
1202  */
1203
1204 static int
1205 ng_ppp_crypt_xmit(node_p node, item_p item, uint16_t proto)
1206 {
1207         const priv_p priv = NG_NODE_PRIVATE(node);
1208
1209         if (priv->conf.enableEncryption &&
1210             proto < 0x4000 &&
1211             proto != PROT_CRYPTD &&
1212             priv->hooks[HOOK_INDEX_ENCRYPT] != NULL) {
1213                 struct mbuf *m;
1214                 int error;
1215
1216                 NGI_GET_M(item, m);
1217                 if ((m = ng_ppp_addproto(m, proto, 0)) == NULL) {
1218                         NG_FREE_ITEM(item);
1219                         return (ENOBUFS);
1220                 }
1221                 NGI_M(item) = m;
1222
1223                 /* Send packet out hook. */
1224                 NG_FWD_ITEM_HOOK(error, item, priv->hooks[HOOK_INDEX_ENCRYPT]);
1225                 return (error);
1226         }
1227
1228         return (ng_ppp_mp_xmit(node, item, proto));
1229 }
1230
1231 /*
1232  * Receive data on a hook encrypt.
1233  */
1234 static int
1235 ng_ppp_rcvdata_encrypt(hook_p hook, item_p item)
1236 {
1237         const node_p node = NG_HOOK_NODE(hook);
1238         const priv_p priv = NG_NODE_PRIVATE(node);
1239
1240         if (!priv->conf.enableEncryption) {
1241                 NG_FREE_ITEM(item);
1242                 return (ENXIO);
1243         }
1244         return (ng_ppp_mp_xmit(node, item, PROT_CRYPTD));
1245 }
1246
1247 static int
1248 ng_ppp_crypt_recv(node_p node, item_p item, uint16_t proto, uint16_t linkNum)
1249 {
1250         const priv_p priv = NG_NODE_PRIVATE(node);
1251
1252         if (proto == PROT_CRYPTD) {
1253                 if (priv->conf.enableDecryption &&
1254                     priv->hooks[HOOK_INDEX_DECRYPT] != NULL) {
1255                         int error;
1256
1257                         /* Send packet out hook. */
1258                         NG_FWD_ITEM_HOOK(error, item,
1259                             priv->hooks[HOOK_INDEX_DECRYPT]);
1260                         return (error);
1261                 } else {
1262                         /* Disabled protos MUST be silently discarded, but
1263                          * unsupported MUST not. Let user-level decide this. */
1264                         return (ng_ppp_bypass(node, item, proto, linkNum));
1265                 }
1266         }
1267
1268         return (ng_ppp_comp_recv(node, item, proto, linkNum));
1269 }
1270
1271 /*
1272  * Receive data on a hook decrypt.
1273  */
1274 static int
1275 ng_ppp_rcvdata_decrypt(hook_p hook, item_p item)
1276 {
1277         const node_p node = NG_HOOK_NODE(hook);
1278         const priv_p priv = NG_NODE_PRIVATE(node);
1279         uint16_t proto;
1280         struct mbuf *m;
1281
1282         if (!priv->conf.enableDecryption) {
1283                 NG_FREE_ITEM(item);
1284                 return (ENXIO);
1285         }
1286         NGI_GET_M(item, m);
1287         if ((m = ng_ppp_cutproto(m, &proto)) == NULL) {
1288                 NG_FREE_ITEM(item);
1289                 return (EIO);
1290         }
1291         NGI_M(item) = m;
1292         if (!PROT_VALID(proto)) {
1293                 priv->bundleStats.badProtos++;
1294                 NG_FREE_ITEM(item);
1295                 return (EIO);
1296         }
1297         return (ng_ppp_comp_recv(node, item, proto, NG_PPP_BUNDLE_LINKNUM));
1298 }
1299
1300 /*
1301  * Link layer
1302  */
1303
1304 static int
1305 ng_ppp_link_xmit(node_p node, item_p item, uint16_t proto, uint16_t linkNum, int plen)
1306 {
1307         const priv_p priv = NG_NODE_PRIVATE(node);
1308         struct ng_ppp_link *link;
1309         int len, error;
1310         struct mbuf *m;
1311         uint16_t mru;
1312
1313         /* Check if link correct. */
1314         if (linkNum >= NG_PPP_MAX_LINKS) {
1315                 ERROUT(ENETDOWN);
1316         }
1317
1318         /* Get link pointer (optimization). */
1319         link = &priv->links[linkNum];
1320
1321         /* Check link status (if real). */
1322         if (link->hook == NULL) {
1323                 ERROUT(ENETDOWN);
1324         }
1325
1326         /* Extract mbuf. */
1327         NGI_GET_M(item, m);
1328
1329         /* Check peer's MRU for this link. */
1330         mru = link->conf.mru;
1331         if (mru != 0 && m->m_pkthdr.len > mru) {
1332                 NG_FREE_M(m);
1333                 ERROUT(EMSGSIZE);
1334         }
1335
1336         /* Prepend protocol number, possibly compressed. */
1337         if ((m = ng_ppp_addproto(m, proto, link->conf.enableProtoComp)) ==
1338             NULL) {
1339                 ERROUT(ENOBUFS);
1340         }
1341
1342         /* Prepend address and control field (unless compressed). */
1343         if (proto == PROT_LCP || !link->conf.enableACFComp) {
1344                 if ((m = ng_ppp_prepend(m, &ng_ppp_acf, 2)) == NULL)
1345                         ERROUT(ENOBUFS);
1346         }
1347
1348         /* Deliver frame. */
1349         len = m->m_pkthdr.len;
1350         NG_FWD_NEW_DATA(error, item, link->hook, m);
1351
1352         mtx_lock(&priv->xmtx);
1353
1354         /* Update link stats. */
1355         link->stats.xmitFrames++;
1356         link->stats.xmitOctets += len;
1357
1358         /* Update bundle stats. */
1359         if (plen > 0) {
1360             priv->bundleStats.xmitFrames++;
1361             priv->bundleStats.xmitOctets += plen;
1362         }
1363
1364         /* Update 'bytes in queue' counter. */
1365         if (error == 0) {
1366                 /* bytesInQueue and lastWrite required only for mp_strategy. */
1367                 if (priv->conf.enableMultilink && !priv->allLinksEqual &&
1368                     !priv->conf.enableRoundRobin) {
1369                         /* If queue was empty, then mark this time. */
1370                         if (link->bytesInQueue == 0)
1371                                 getmicrouptime(&link->lastWrite);
1372                         link->bytesInQueue += len + MP_AVERAGE_LINK_OVERHEAD;
1373                         /* Limit max queue length to 50 pkts. BW can be defined
1374                            incorrectly and link may not signal overload. */
1375                         if (link->bytesInQueue > 50 * 1600)
1376                                 link->bytesInQueue = 50 * 1600;
1377                 }
1378         }
1379         mtx_unlock(&priv->xmtx);
1380         return (error);
1381
1382 done:
1383         NG_FREE_ITEM(item);
1384         return (error);
1385 }
1386
1387 /*
1388  * Receive data on a hook linkX.
1389  */
1390 static int
1391 ng_ppp_rcvdata(hook_p hook, item_p item)
1392 {
1393         const node_p node = NG_HOOK_NODE(hook);
1394         const priv_p priv = NG_NODE_PRIVATE(node);
1395         const int index = (intptr_t)NG_HOOK_PRIVATE(hook);
1396         const uint16_t linkNum = (uint16_t)~index;
1397         struct ng_ppp_link * const link = &priv->links[linkNum];
1398         uint16_t proto;
1399         struct mbuf *m;
1400         int error = 0;
1401
1402         KASSERT(linkNum < NG_PPP_MAX_LINKS,
1403             ("%s: bogus index 0x%x", __func__, index));
1404
1405         NGI_GET_M(item, m);
1406
1407         mtx_lock(&priv->rmtx);
1408
1409         /* Stats */
1410         link->stats.recvFrames++;
1411         link->stats.recvOctets += m->m_pkthdr.len;
1412
1413         /* Strip address and control fields, if present. */
1414         if (m->m_len < 2 && (m = m_pullup(m, 2)) == NULL)
1415                 ERROUT(ENOBUFS);
1416         if (mtod(m, uint8_t *)[0] == 0xff &&
1417             mtod(m, uint8_t *)[1] == 0x03)
1418                 m_adj(m, 2);
1419
1420         /* Get protocol number */
1421         if ((m = ng_ppp_cutproto(m, &proto)) == NULL)
1422                 ERROUT(ENOBUFS);
1423         NGI_M(item) = m;        /* Put changed m back into item. */
1424
1425         if (!PROT_VALID(proto)) {
1426                 link->stats.badProtos++;
1427                 ERROUT(EIO);
1428         }
1429
1430         /* LCP packets must go directly to bypass. */
1431         if (proto >= 0xB000) {
1432                 mtx_unlock(&priv->rmtx);
1433                 return (ng_ppp_bypass(node, item, proto, linkNum));
1434         }
1435
1436         /* Other packets are denied on a disabled link. */
1437         if (!link->conf.enableLink)
1438                 ERROUT(ENXIO);
1439
1440         /* Proceed to multilink layer. Mutex will be unlocked inside. */
1441         error = ng_ppp_mp_recv(node, item, proto, linkNum);
1442         mtx_assert(&priv->rmtx, MA_NOTOWNED);
1443         return (error);
1444
1445 done:
1446         mtx_unlock(&priv->rmtx);
1447         NG_FREE_ITEM(item);
1448         return (error);
1449 }
1450
1451 /*
1452  * Multilink layer
1453  */
1454
1455 /*
1456  * Handle an incoming multi-link fragment
1457  *
1458  * The fragment reassembly algorithm is somewhat complex. This is mainly
1459  * because we are required not to reorder the reconstructed packets, yet
1460  * fragments are only guaranteed to arrive in order on a per-link basis.
1461  * In other words, when we have a complete packet ready, but the previous
1462  * packet is still incomplete, we have to decide between delivering the
1463  * complete packet and throwing away the incomplete one, or waiting to
1464  * see if the remainder of the incomplete one arrives, at which time we
1465  * can deliver both packets, in order.
1466  *
1467  * This problem is exacerbated by "sequence number slew", which is when
1468  * the sequence numbers coming in from different links are far apart from
1469  * each other. In particular, certain unnamed equipment (*cough* Ascend)
1470  * has been seen to generate sequence number slew of up to 10 on an ISDN
1471  * 2B-channel MP link. There is nothing invalid about sequence number slew
1472  * but it makes the reasssembly process have to work harder.
1473  *
1474  * However, the peer is required to transmit fragments in order on each
1475  * link. That means if we define MSEQ as the minimum over all links of
1476  * the highest sequence number received on that link, then we can always
1477  * give up any hope of receiving a fragment with sequence number < MSEQ in
1478  * the future (all of this using 'wraparound' sequence number space).
1479  * Therefore we can always immediately throw away incomplete packets
1480  * missing fragments with sequence numbers < MSEQ.
1481  *
1482  * Here is an overview of our algorithm:
1483  *
1484  *    o Received fragments are inserted into a queue, for which we
1485  *      maintain these invariants between calls to this function:
1486  *
1487  *      - Fragments are ordered in the queue by sequence number
1488  *      - If a complete packet is at the head of the queue, then
1489  *        the first fragment in the packet has seq# > MSEQ + 1
1490  *        (otherwise, we could deliver it immediately)
1491  *      - If any fragments have seq# < MSEQ, then they are necessarily
1492  *        part of a packet whose missing seq#'s are all > MSEQ (otherwise,
1493  *        we can throw them away because they'll never be completed)
1494  *      - The queue contains at most MP_MAX_QUEUE_LEN fragments
1495  *
1496  *    o We have a periodic timer that checks the queue for the first
1497  *      complete packet that has been sitting in the queue "too long".
1498  *      When one is detected, all previous (incomplete) fragments are
1499  *      discarded, their missing fragments are declared lost and MSEQ
1500  *      is increased.
1501  *
1502  *    o If we recieve a fragment with seq# < MSEQ, we throw it away
1503  *      because we've already delcared it lost.
1504  *
1505  * This assumes linkNum != NG_PPP_BUNDLE_LINKNUM.
1506  */
1507 static int
1508 ng_ppp_mp_recv(node_p node, item_p item, uint16_t proto, uint16_t linkNum)
1509 {
1510         const priv_p priv = NG_NODE_PRIVATE(node);
1511         struct ng_ppp_link *const link = &priv->links[linkNum];
1512         struct ng_ppp_frag *frag;
1513         struct ng_ppp_frag *qent;
1514         int i, diff, inserted;
1515         struct mbuf *m;
1516         int     error = 0;
1517
1518         if ((!priv->conf.enableMultilink) || proto != PROT_MP) {
1519                 /* Stats */
1520                 priv->bundleStats.recvFrames++;
1521                 priv->bundleStats.recvOctets += NGI_M(item)->m_pkthdr.len;
1522
1523                 mtx_unlock(&priv->rmtx);
1524                 return (ng_ppp_crypt_recv(node, item, proto, linkNum));
1525         }
1526
1527         NGI_GET_M(item, m);
1528
1529         /* Get a new frag struct from the free queue */
1530         if ((frag = TAILQ_FIRST(&priv->fragsfree)) == NULL) {
1531                 printf("No free fragments headers in ng_ppp!\n");
1532                 NG_FREE_M(m);
1533                 goto process;
1534         }
1535
1536         /* Extract fragment information from MP header */
1537         if (priv->conf.recvShortSeq) {
1538                 uint16_t shdr;
1539
1540                 if (m->m_pkthdr.len < 2) {
1541                         link->stats.runts++;
1542                         NG_FREE_M(m);
1543                         ERROUT(EINVAL);
1544                 }
1545                 if (m->m_len < 2 && (m = m_pullup(m, 2)) == NULL)
1546                         ERROUT(ENOBUFS);
1547
1548                 shdr = be16dec(mtod(m, void *));
1549                 frag->seq = MP_SHORT_EXTEND(shdr);
1550                 frag->first = (shdr & MP_SHORT_FIRST_FLAG) != 0;
1551                 frag->last = (shdr & MP_SHORT_LAST_FLAG) != 0;
1552                 diff = MP_SHORT_SEQ_DIFF(frag->seq, priv->mseq);
1553                 m_adj(m, 2);
1554         } else {
1555                 uint32_t lhdr;
1556
1557                 if (m->m_pkthdr.len < 4) {
1558                         link->stats.runts++;
1559                         NG_FREE_M(m);
1560                         ERROUT(EINVAL);
1561                 }
1562                 if (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL)
1563                         ERROUT(ENOBUFS);
1564
1565                 lhdr = be32dec(mtod(m, void *));
1566                 frag->seq = MP_LONG_EXTEND(lhdr);
1567                 frag->first = (lhdr & MP_LONG_FIRST_FLAG) != 0;
1568                 frag->last = (lhdr & MP_LONG_LAST_FLAG) != 0;
1569                 diff = MP_LONG_SEQ_DIFF(frag->seq, priv->mseq);
1570                 m_adj(m, 4);
1571         }
1572         frag->data = m;
1573         getmicrouptime(&frag->timestamp);
1574
1575         /* If sequence number is < MSEQ, we've already declared this
1576            fragment as lost, so we have no choice now but to drop it */
1577         if (diff < 0) {
1578                 link->stats.dropFragments++;
1579                 NG_FREE_M(m);
1580                 ERROUT(0);
1581         }
1582
1583         /* Update highest received sequence number on this link and MSEQ */
1584         priv->mseq = link->seq = frag->seq;
1585         for (i = 0; i < priv->numActiveLinks; i++) {
1586                 struct ng_ppp_link *const alink =
1587                     &priv->links[priv->activeLinks[i]];
1588
1589                 if (MP_RECV_SEQ_DIFF(priv, alink->seq, priv->mseq) < 0)
1590                         priv->mseq = alink->seq;
1591         }
1592
1593         /* Remove frag struct from free queue. */
1594         TAILQ_REMOVE(&priv->fragsfree, frag, f_qent);
1595
1596         /* Add fragment to queue, which is sorted by sequence number */
1597         inserted = 0;
1598         TAILQ_FOREACH_REVERSE(qent, &priv->frags, ng_ppp_fraglist, f_qent) {
1599                 diff = MP_RECV_SEQ_DIFF(priv, frag->seq, qent->seq);
1600                 if (diff > 0) {
1601                         TAILQ_INSERT_AFTER(&priv->frags, qent, frag, f_qent);
1602                         inserted = 1;
1603                         break;
1604                 } else if (diff == 0) {      /* should never happen! */
1605                         link->stats.dupFragments++;
1606                         NG_FREE_M(frag->data);
1607                         TAILQ_INSERT_HEAD(&priv->fragsfree, frag, f_qent);
1608                         ERROUT(EINVAL);
1609                 }
1610         }
1611         if (!inserted)
1612                 TAILQ_INSERT_HEAD(&priv->frags, frag, f_qent);
1613
1614 process:
1615         /* Process the queue */
1616         /* NOTE: rmtx will be unlocked for sending time! */
1617         error = ng_ppp_frag_process(node, item);
1618         mtx_unlock(&priv->rmtx);
1619         return (error);
1620
1621 done:
1622         mtx_unlock(&priv->rmtx);
1623         NG_FREE_ITEM(item);
1624         return (error);
1625 }
1626
1627 /************************************************************************
1628                         HELPER STUFF
1629  ************************************************************************/
1630
1631 /*
1632  * If new mseq > current then set it and update all active links
1633  */
1634 static void
1635 ng_ppp_bump_mseq(node_p node, int32_t new_mseq)
1636 {
1637         const priv_p priv = NG_NODE_PRIVATE(node);
1638         int i;
1639
1640         if (MP_RECV_SEQ_DIFF(priv, priv->mseq, new_mseq) < 0) {
1641                 priv->mseq = new_mseq;
1642                 for (i = 0; i < priv->numActiveLinks; i++) {
1643                         struct ng_ppp_link *const alink =
1644                             &priv->links[priv->activeLinks[i]];
1645
1646                         if (MP_RECV_SEQ_DIFF(priv,
1647                             alink->seq, new_mseq) < 0)
1648                                 alink->seq = new_mseq;
1649                 }
1650         }
1651 }
1652
1653 /*
1654  * Examine our list of fragments, and determine if there is a
1655  * complete and deliverable packet at the head of the list.
1656  * Return 1 if so, zero otherwise.
1657  */
1658 static int
1659 ng_ppp_check_packet(node_p node)
1660 {
1661         const priv_p priv = NG_NODE_PRIVATE(node);
1662         struct ng_ppp_frag *qent, *qnext;
1663
1664         /* Check for empty queue */
1665         if (TAILQ_EMPTY(&priv->frags))
1666                 return (0);
1667
1668         /* Check first fragment is the start of a deliverable packet */
1669         qent = TAILQ_FIRST(&priv->frags);
1670         if (!qent->first || MP_RECV_SEQ_DIFF(priv, qent->seq, priv->mseq) > 1)
1671                 return (0);
1672
1673         /* Check that all the fragments are there */
1674         while (!qent->last) {
1675                 qnext = TAILQ_NEXT(qent, f_qent);
1676                 if (qnext == NULL)      /* end of queue */
1677                         return (0);
1678                 if (qnext->seq != MP_NEXT_RECV_SEQ(priv, qent->seq))
1679                         return (0);
1680                 qent = qnext;
1681         }
1682
1683         /* Got one */
1684         return (1);
1685 }
1686
1687 /*
1688  * Pull a completed packet off the head of the incoming fragment queue.
1689  * This assumes there is a completed packet there to pull off.
1690  */
1691 static void
1692 ng_ppp_get_packet(node_p node, struct mbuf **mp)
1693 {
1694         const priv_p priv = NG_NODE_PRIVATE(node);
1695         struct ng_ppp_frag *qent, *qnext;
1696         struct mbuf *m = NULL, *tail;
1697
1698         qent = TAILQ_FIRST(&priv->frags);
1699         KASSERT(!TAILQ_EMPTY(&priv->frags) && qent->first,
1700             ("%s: no packet", __func__));
1701         for (tail = NULL; qent != NULL; qent = qnext) {
1702                 qnext = TAILQ_NEXT(qent, f_qent);
1703                 KASSERT(!TAILQ_EMPTY(&priv->frags),
1704                     ("%s: empty q", __func__));
1705                 TAILQ_REMOVE(&priv->frags, qent, f_qent);
1706                 if (tail == NULL)
1707                         tail = m = qent->data;
1708                 else {
1709                         m->m_pkthdr.len += qent->data->m_pkthdr.len;
1710                         tail->m_next = qent->data;
1711                 }
1712                 while (tail->m_next != NULL)
1713                         tail = tail->m_next;
1714                 if (qent->last) {
1715                         qnext = NULL;
1716                         /* Bump MSEQ if necessary */
1717                         ng_ppp_bump_mseq(node, qent->seq);
1718                 }
1719                 TAILQ_INSERT_HEAD(&priv->fragsfree, qent, f_qent);
1720         }
1721         *mp = m;
1722 }
1723
1724 /*
1725  * Trim fragments from the queue whose packets can never be completed.
1726  * This assumes a complete packet is NOT at the beginning of the queue.
1727  * Returns 1 if fragments were removed, zero otherwise.
1728  */
1729 static int
1730 ng_ppp_frag_trim(node_p node)
1731 {
1732         const priv_p priv = NG_NODE_PRIVATE(node);
1733         struct ng_ppp_frag *qent, *qnext = NULL;
1734         int removed = 0;
1735
1736         /* Scan for "dead" fragments and remove them */
1737         while (1) {
1738                 int dead = 0;
1739
1740                 /* If queue is empty, we're done */
1741                 if (TAILQ_EMPTY(&priv->frags))
1742                         break;
1743
1744                 /* Determine whether first fragment can ever be completed */
1745                 TAILQ_FOREACH(qent, &priv->frags, f_qent) {
1746                         if (MP_RECV_SEQ_DIFF(priv, qent->seq, priv->mseq) >= 0)
1747                                 break;
1748                         qnext = TAILQ_NEXT(qent, f_qent);
1749                         KASSERT(qnext != NULL,
1750                             ("%s: last frag < MSEQ?", __func__));
1751                         if (qnext->seq != MP_NEXT_RECV_SEQ(priv, qent->seq)
1752                             || qent->last || qnext->first) {
1753                                 dead = 1;
1754                                 break;
1755                         }
1756                 }
1757                 if (!dead)
1758                         break;
1759
1760                 /* Remove fragment and all others in the same packet */
1761                 while ((qent = TAILQ_FIRST(&priv->frags)) != qnext) {
1762                         KASSERT(!TAILQ_EMPTY(&priv->frags),
1763                             ("%s: empty q", __func__));
1764                         priv->bundleStats.dropFragments++;
1765                         TAILQ_REMOVE(&priv->frags, qent, f_qent);
1766                         NG_FREE_M(qent->data);
1767                         TAILQ_INSERT_HEAD(&priv->fragsfree, qent, f_qent);
1768                         removed = 1;
1769                 }
1770         }
1771         return (removed);
1772 }
1773
1774 /*
1775  * Drop fragments on queue overflow.
1776  * Returns 1 if fragments were removed, zero otherwise.
1777  */
1778 static int
1779 ng_ppp_frag_drop(node_p node)
1780 {
1781         const priv_p priv = NG_NODE_PRIVATE(node);
1782
1783         /* Check queue length */
1784         if (TAILQ_EMPTY(&priv->fragsfree)) {
1785                 struct ng_ppp_frag *qent;
1786
1787                 /* Get oldest fragment */
1788                 KASSERT(!TAILQ_EMPTY(&priv->frags),
1789                     ("%s: empty q", __func__));
1790                 qent = TAILQ_FIRST(&priv->frags);
1791
1792                 /* Bump MSEQ if necessary */
1793                 ng_ppp_bump_mseq(node, qent->seq);
1794
1795                 /* Drop it */
1796                 priv->bundleStats.dropFragments++;
1797                 TAILQ_REMOVE(&priv->frags, qent, f_qent);
1798                 NG_FREE_M(qent->data);
1799                 TAILQ_INSERT_HEAD(&priv->fragsfree, qent, f_qent);
1800
1801                 return (1);
1802         }
1803         return (0);
1804 }
1805
1806 /*
1807  * Run the queue, restoring the queue invariants
1808  */
1809 static int
1810 ng_ppp_frag_process(node_p node, item_p oitem)
1811 {
1812         const priv_p priv = NG_NODE_PRIVATE(node);
1813         struct mbuf *m;
1814         item_p item;
1815         uint16_t proto;
1816
1817         do {
1818                 /* Deliver any deliverable packets */
1819                 while (ng_ppp_check_packet(node)) {
1820                         ng_ppp_get_packet(node, &m);
1821                         if ((m = ng_ppp_cutproto(m, &proto)) == NULL)
1822                                 continue;
1823                         if (!PROT_VALID(proto)) {
1824                                 priv->bundleStats.badProtos++;
1825                                 NG_FREE_M(m);
1826                                 continue;
1827                         }
1828                         if (oitem) { /* If original item present - reuse it. */
1829                                 item = oitem;
1830                                 oitem = NULL;
1831                                 NGI_M(item) = m;
1832                         } else {
1833                                 item = ng_package_data(m, NG_NOFLAGS);
1834                         }
1835                         if (item != NULL) {
1836                                 /* Stats */
1837                                 priv->bundleStats.recvFrames++;
1838                                 priv->bundleStats.recvOctets +=
1839                                     NGI_M(item)->m_pkthdr.len;
1840
1841                                 /* Drop mutex for the sending time.
1842                                  * Priv may change, but we are ready!
1843                                  */
1844                                 mtx_unlock(&priv->rmtx);
1845                                 ng_ppp_crypt_recv(node, item, proto,
1846                                         NG_PPP_BUNDLE_LINKNUM);
1847                                 mtx_lock(&priv->rmtx);
1848                         }
1849                 }
1850           /* Delete dead fragments and try again */
1851         } while (ng_ppp_frag_trim(node) || ng_ppp_frag_drop(node));
1852
1853         /* If we haven't reused original item - free it. */
1854         if (oitem) NG_FREE_ITEM(oitem);
1855
1856         /* Done */
1857         return (0);
1858 }
1859
1860 /*
1861  * Check for 'stale' completed packets that need to be delivered
1862  *
1863  * If a link goes down or has a temporary failure, MSEQ can get
1864  * "stuck", because no new incoming fragments appear on that link.
1865  * This can cause completed packets to never get delivered if
1866  * their sequence numbers are all > MSEQ + 1.
1867  *
1868  * This routine checks how long all of the completed packets have
1869  * been sitting in the queue, and if too long, removes fragments
1870  * from the queue and increments MSEQ to allow them to be delivered.
1871  */
1872 static void
1873 ng_ppp_frag_checkstale(node_p node)
1874 {
1875         const priv_p priv = NG_NODE_PRIVATE(node);
1876         struct ng_ppp_frag *qent, *beg, *end;
1877         struct timeval now, age;
1878         struct mbuf *m;
1879         int seq;
1880         item_p item;
1881         int endseq;
1882         uint16_t proto;
1883
1884         now.tv_sec = 0;                 /* uninitialized state */
1885         while (1) {
1886
1887                 /* If queue is empty, we're done */
1888                 if (TAILQ_EMPTY(&priv->frags))
1889                         break;
1890
1891                 /* Find the first complete packet in the queue */
1892                 beg = end = NULL;
1893                 seq = TAILQ_FIRST(&priv->frags)->seq;
1894                 TAILQ_FOREACH(qent, &priv->frags, f_qent) {
1895                         if (qent->first)
1896                                 beg = qent;
1897                         else if (qent->seq != seq)
1898                                 beg = NULL;
1899                         if (beg != NULL && qent->last) {
1900                                 end = qent;
1901                                 break;
1902                         }
1903                         seq = MP_NEXT_RECV_SEQ(priv, seq);
1904                 }
1905
1906                 /* If none found, exit */
1907                 if (end == NULL)
1908                         break;
1909
1910                 /* Get current time (we assume we've been up for >= 1 second) */
1911                 if (now.tv_sec == 0)
1912                         getmicrouptime(&now);
1913
1914                 /* Check if packet has been queued too long */
1915                 age = now;
1916                 timevalsub(&age, &beg->timestamp);
1917                 if (timevalcmp(&age, &ng_ppp_max_staleness, < ))
1918                         break;
1919
1920                 /* Throw away junk fragments in front of the completed packet */
1921                 while ((qent = TAILQ_FIRST(&priv->frags)) != beg) {
1922                         KASSERT(!TAILQ_EMPTY(&priv->frags),
1923                             ("%s: empty q", __func__));
1924                         priv->bundleStats.dropFragments++;
1925                         TAILQ_REMOVE(&priv->frags, qent, f_qent);
1926                         NG_FREE_M(qent->data);
1927                         TAILQ_INSERT_HEAD(&priv->fragsfree, qent, f_qent);
1928                 }
1929
1930                 /* Extract completed packet */
1931                 endseq = end->seq;
1932                 ng_ppp_get_packet(node, &m);
1933
1934                 if ((m = ng_ppp_cutproto(m, &proto)) == NULL)
1935                         continue;
1936                 if (!PROT_VALID(proto)) {
1937                         priv->bundleStats.badProtos++;
1938                         NG_FREE_M(m);
1939                         continue;
1940                 }
1941
1942                 /* Deliver packet */
1943                 if ((item = ng_package_data(m, NG_NOFLAGS)) != NULL) {
1944                         /* Stats */
1945                         priv->bundleStats.recvFrames++;
1946                         priv->bundleStats.recvOctets += NGI_M(item)->m_pkthdr.len;
1947
1948                         ng_ppp_crypt_recv(node, item, proto,
1949                                 NG_PPP_BUNDLE_LINKNUM);
1950                 }
1951         }
1952 }
1953
1954 /*
1955  * Periodically call ng_ppp_frag_checkstale()
1956  */
1957 static void
1958 ng_ppp_frag_timeout(node_p node, hook_p hook, void *arg1, int arg2)
1959 {
1960         /* XXX: is this needed? */
1961         if (NG_NODE_NOT_VALID(node))
1962                 return;
1963
1964         /* Scan the fragment queue */
1965         ng_ppp_frag_checkstale(node);
1966
1967         /* Start timer again */
1968         ng_ppp_start_frag_timer(node);
1969 }
1970
1971 /*
1972  * Deliver a frame out on the bundle, i.e., figure out how to fragment
1973  * the frame across the individual PPP links and do so.
1974  */
1975 static int
1976 ng_ppp_mp_xmit(node_p node, item_p item, uint16_t proto)
1977 {
1978         const priv_p priv = NG_NODE_PRIVATE(node);
1979         const int hdr_len = priv->conf.xmitShortSeq ? 2 : 4;
1980         int distrib[NG_PPP_MAX_LINKS];
1981         int firstFragment;
1982         int activeLinkNum;
1983         struct mbuf *m;
1984         int     plen;
1985         int     frags;
1986         int32_t seq;
1987
1988         /* At least one link must be active */
1989         if (priv->numActiveLinks == 0) {
1990                 NG_FREE_ITEM(item);
1991                 return (ENETDOWN);
1992         }
1993
1994         /* Save length for later stats. */
1995         plen = NGI_M(item)->m_pkthdr.len;
1996
1997         if (!priv->conf.enableMultilink) {
1998                 return (ng_ppp_link_xmit(node, item, proto,
1999                     priv->activeLinks[0], plen));
2000         }
2001
2002         /* Check peer's MRRU for this bundle. */
2003         if (plen > priv->conf.mrru) {
2004                 NG_FREE_ITEM(item);
2005                 return (EMSGSIZE);
2006         }
2007
2008         /* Extract mbuf. */
2009         NGI_GET_M(item, m);
2010
2011         /* Prepend protocol number, possibly compressed. */
2012         if ((m = ng_ppp_addproto(m, proto, 1)) == NULL) {
2013                 NG_FREE_ITEM(item);
2014                 return (ENOBUFS);
2015         }
2016
2017         /* Clear distribution plan */
2018         bzero(&distrib, priv->numActiveLinks * sizeof(distrib[0]));
2019
2020         mtx_lock(&priv->xmtx);
2021
2022         /* Round-robin strategy */
2023         if (priv->conf.enableRoundRobin) {
2024                 activeLinkNum = priv->lastLink++ % priv->numActiveLinks;
2025                 distrib[activeLinkNum] = m->m_pkthdr.len;
2026                 goto deliver;
2027         }
2028
2029         /* Strategy when all links are equivalent (optimize the common case) */
2030         if (priv->allLinksEqual) {
2031                 int     numFrags, fraction, remain;
2032                 int     i;
2033
2034                 /* Calculate optimal fragment count */
2035                 numFrags = priv->numActiveLinks;
2036                 if (numFrags > m->m_pkthdr.len / MP_MIN_FRAG_LEN)
2037                     numFrags = m->m_pkthdr.len / MP_MIN_FRAG_LEN;
2038                 if (numFrags == 0)
2039                     numFrags = 1;
2040
2041                 fraction = m->m_pkthdr.len / numFrags;
2042                 remain = m->m_pkthdr.len - (fraction * numFrags);
2043
2044                 /* Assign distribution */
2045                 for (i = 0; i < numFrags; i++) {
2046                         distrib[priv->lastLink++ % priv->numActiveLinks]
2047                             = fraction + (((remain--) > 0)?1:0);
2048                 }
2049                 goto deliver;
2050         }
2051
2052         /* Strategy when all links are not equivalent */
2053         ng_ppp_mp_strategy(node, m->m_pkthdr.len, distrib);
2054
2055 deliver:
2056         /* Estimate fragments count */
2057         frags = 0;
2058         for (activeLinkNum = priv->numActiveLinks - 1;
2059             activeLinkNum >= 0; activeLinkNum--) {
2060                 const uint16_t linkNum = priv->activeLinks[activeLinkNum];
2061                 struct ng_ppp_link *const link = &priv->links[linkNum];
2062
2063                 frags += (distrib[activeLinkNum] + link->conf.mru - hdr_len - 1) /
2064                     (link->conf.mru - hdr_len);
2065         }
2066
2067         /* Get out initial sequence number */
2068         seq = priv->xseq;
2069
2070         /* Update next sequence number */
2071         if (priv->conf.xmitShortSeq) {
2072             priv->xseq = (seq + frags) & MP_SHORT_SEQ_MASK;
2073         } else {
2074             priv->xseq = (seq + frags) & MP_LONG_SEQ_MASK;
2075         }
2076
2077         mtx_unlock(&priv->xmtx);
2078
2079         /* Send alloted portions of frame out on the link(s) */
2080         for (firstFragment = 1, activeLinkNum = priv->numActiveLinks - 1;
2081             activeLinkNum >= 0; activeLinkNum--) {
2082                 const uint16_t linkNum = priv->activeLinks[activeLinkNum];
2083                 struct ng_ppp_link *const link = &priv->links[linkNum];
2084
2085                 /* Deliver fragment(s) out the next link */
2086                 for ( ; distrib[activeLinkNum] > 0; firstFragment = 0) {
2087                         int len, lastFragment, error;
2088                         struct mbuf *m2;
2089
2090                         /* Calculate fragment length; don't exceed link MTU */
2091                         len = distrib[activeLinkNum];
2092                         if (len > link->conf.mru - hdr_len)
2093                                 len = link->conf.mru - hdr_len;
2094                         distrib[activeLinkNum] -= len;
2095                         lastFragment = (len == m->m_pkthdr.len);
2096
2097                         /* Split off next fragment as "m2" */
2098                         m2 = m;
2099                         if (!lastFragment) {
2100                                 struct mbuf *n = m_split(m, len, M_DONTWAIT);
2101
2102                                 if (n == NULL) {
2103                                         NG_FREE_M(m);
2104                                         if (firstFragment)
2105                                                 NG_FREE_ITEM(item);
2106                                         return (ENOMEM);
2107                                 }
2108                                 m_tag_copy_chain(n, m, M_DONTWAIT);
2109                                 m = n;
2110                         }
2111
2112                         /* Prepend MP header */
2113                         if (priv->conf.xmitShortSeq) {
2114                                 uint16_t shdr;
2115
2116                                 shdr = seq;
2117                                 seq = (seq + 1) & MP_SHORT_SEQ_MASK;
2118                                 if (firstFragment)
2119                                         shdr |= MP_SHORT_FIRST_FLAG;
2120                                 if (lastFragment)
2121                                         shdr |= MP_SHORT_LAST_FLAG;
2122                                 shdr = htons(shdr);
2123                                 m2 = ng_ppp_prepend(m2, &shdr, 2);
2124                         } else {
2125                                 uint32_t lhdr;
2126
2127                                 lhdr = seq;
2128                                 seq = (seq + 1) & MP_LONG_SEQ_MASK;
2129                                 if (firstFragment)
2130                                         lhdr |= MP_LONG_FIRST_FLAG;
2131                                 if (lastFragment)
2132                                         lhdr |= MP_LONG_LAST_FLAG;
2133                                 lhdr = htonl(lhdr);
2134                                 m2 = ng_ppp_prepend(m2, &lhdr, 4);
2135                         }
2136                         if (m2 == NULL) {
2137                                 if (!lastFragment)
2138                                         m_freem(m);
2139                                 if (firstFragment)
2140                                         NG_FREE_ITEM(item);
2141                                 return (ENOBUFS);
2142                         }
2143
2144                         /* Send fragment */
2145                         if (firstFragment) {
2146                                 NGI_M(item) = m2; /* Reuse original item. */
2147                         } else {
2148                                 item = ng_package_data(m2, NG_NOFLAGS);
2149                         }
2150                         if (item != NULL) {
2151                                 error = ng_ppp_link_xmit(node, item, PROT_MP,
2152                                             linkNum, (firstFragment?plen:0));
2153                                 if (error != 0) {
2154                                         if (!lastFragment)
2155                                                 NG_FREE_M(m);
2156                                         return (error);
2157                                 }
2158                         }
2159                 }
2160         }
2161
2162         /* Done */
2163         return (0);
2164 }
2165
2166 /*
2167  * Computing the optimal fragmentation
2168  * -----------------------------------
2169  *
2170  * This routine tries to compute the optimal fragmentation pattern based
2171  * on each link's latency, bandwidth, and calculated additional latency.
2172  * The latter quantity is the additional latency caused by previously
2173  * written data that has not been transmitted yet.
2174  *
2175  * This algorithm is only useful when not all of the links have the
2176  * same latency and bandwidth values.
2177  *
2178  * The essential idea is to make the last bit of each fragment of the
2179  * frame arrive at the opposite end at the exact same time. This greedy
2180  * algorithm is optimal, in that no other scheduling could result in any
2181  * packet arriving any sooner unless packets are delivered out of order.
2182  *
2183  * Suppose link i has bandwidth b_i (in tens of bytes per milisecond) and
2184  * latency l_i (in miliseconds). Consider the function function f_i(t)
2185  * which is equal to the number of bytes that will have arrived at
2186  * the peer after t miliseconds if we start writing continuously at
2187  * time t = 0. Then f_i(t) = b_i * (t - l_i) = ((b_i * t) - (l_i * b_i).
2188  * That is, f_i(t) is a line with slope b_i and y-intersect -(l_i * b_i).
2189  * Note that the y-intersect is always <= zero because latency can't be
2190  * negative.  Note also that really the function is f_i(t) except when
2191  * f_i(t) is negative, in which case the function is zero.  To take
2192  * care of this, let Q_i(t) = { if (f_i(t) > 0) return 1; else return 0; }.
2193  * So the actual number of bytes that will have arrived at the peer after
2194  * t miliseconds is f_i(t) * Q_i(t).
2195  *
2196  * At any given time, each link has some additional latency a_i >= 0
2197  * due to previously written fragment(s) which are still in the queue.
2198  * This value is easily computed from the time since last transmission,
2199  * the previous latency value, the number of bytes written, and the
2200  * link's bandwidth.
2201  *
2202  * Assume that l_i includes any a_i already, and that the links are
2203  * sorted by latency, so that l_i <= l_{i+1}.
2204  *
2205  * Let N be the total number of bytes in the current frame we are sending.
2206  *
2207  * Suppose we were to start writing bytes at time t = 0 on all links
2208  * simultaneously, which is the most we can possibly do.  Then let
2209  * F(t) be equal to the total number of bytes received by the peer
2210  * after t miliseconds. Then F(t) = Sum_i (f_i(t) * Q_i(t)).
2211  *
2212  * Our goal is simply this: fragment the frame across the links such
2213  * that the peer is able to reconstruct the completed frame as soon as
2214  * possible, i.e., at the least possible value of t. Call this value t_0.
2215  *
2216  * Then it follows that F(t_0) = N. Our strategy is first to find the value
2217  * of t_0, and then deduce how many bytes to write to each link.
2218  *
2219  * Rewriting F(t_0):
2220  *
2221  *   t_0 = ( N + Sum_i ( l_i * b_i * Q_i(t_0) ) ) / Sum_i ( b_i * Q_i(t_0) )
2222  *
2223  * Now, we note that Q_i(t) is constant for l_i <= t <= l_{i+1}. t_0 will
2224  * lie in one of these ranges.  To find it, we just need to find the i such
2225  * that F(l_i) <= N <= F(l_{i+1}).  Then we compute all the constant values
2226  * for Q_i() in this range, plug in the remaining values, solving for t_0.
2227  *
2228  * Once t_0 is known, then the number of bytes to send on link i is
2229  * just f_i(t_0) * Q_i(t_0).
2230  *
2231  * In other words, we start allocating bytes to the links one at a time.
2232  * We keep adding links until the frame is completely sent.  Some links
2233  * may not get any bytes because their latency is too high.
2234  *
2235  * Is all this work really worth the trouble?  Depends on the situation.
2236  * The bigger the ratio of computer speed to link speed, and the more
2237  * important total bundle latency is (e.g., for interactive response time),
2238  * the more it's worth it.  There is however the cost of calling this
2239  * function for every frame.  The running time is O(n^2) where n is the
2240  * number of links that receive a non-zero number of bytes.
2241  *
2242  * Since latency is measured in miliseconds, the "resolution" of this
2243  * algorithm is one milisecond.
2244  *
2245  * To avoid this algorithm altogether, configure all links to have the
2246  * same latency and bandwidth.
2247  */
2248 static void
2249 ng_ppp_mp_strategy(node_p node, int len, int *distrib)
2250 {
2251         const priv_p priv = NG_NODE_PRIVATE(node);
2252         int latency[NG_PPP_MAX_LINKS];
2253         int sortByLatency[NG_PPP_MAX_LINKS];
2254         int activeLinkNum;
2255         int t0, total, topSum, botSum;
2256         struct timeval now;
2257         int i, numFragments;
2258
2259         /* If only one link, this gets real easy */
2260         if (priv->numActiveLinks == 1) {
2261                 distrib[0] = len;
2262                 return;
2263         }
2264
2265         /* Get current time */
2266         getmicrouptime(&now);
2267
2268         /* Compute latencies for each link at this point in time */
2269         for (activeLinkNum = 0;
2270             activeLinkNum < priv->numActiveLinks; activeLinkNum++) {
2271                 struct ng_ppp_link *alink;
2272                 struct timeval diff;
2273                 int xmitBytes;
2274
2275                 /* Start with base latency value */
2276                 alink = &priv->links[priv->activeLinks[activeLinkNum]];
2277                 latency[activeLinkNum] = alink->latency;
2278                 sortByLatency[activeLinkNum] = activeLinkNum;   /* see below */
2279
2280                 /* Any additional latency? */
2281                 if (alink->bytesInQueue == 0)
2282                         continue;
2283
2284                 /* Compute time delta since last write */
2285                 diff = now;
2286                 timevalsub(&diff, &alink->lastWrite);
2287
2288                 /* alink->bytesInQueue will be changed, mark change time. */
2289                 alink->lastWrite = now;
2290
2291                 if (now.tv_sec < 0 || diff.tv_sec >= 10) {      /* sanity */
2292                         alink->bytesInQueue = 0;
2293                         continue;
2294                 }
2295
2296                 /* How many bytes could have transmitted since last write? */
2297                 xmitBytes = (alink->conf.bandwidth * 10 * diff.tv_sec)
2298                     + (alink->conf.bandwidth * (diff.tv_usec / 1000)) / 100;
2299                 alink->bytesInQueue -= xmitBytes;
2300                 if (alink->bytesInQueue < 0)
2301                         alink->bytesInQueue = 0;
2302                 else
2303                         latency[activeLinkNum] +=
2304                             (100 * alink->bytesInQueue) / alink->conf.bandwidth;
2305         }
2306
2307         /* Sort active links by latency */
2308         qsort_r(sortByLatency,
2309             priv->numActiveLinks, sizeof(*sortByLatency), latency, ng_ppp_intcmp);
2310
2311         /* Find the interval we need (add links in sortByLatency[] order) */
2312         for (numFragments = 1;
2313             numFragments < priv->numActiveLinks; numFragments++) {
2314                 for (total = i = 0; i < numFragments; i++) {
2315                         int flowTime;
2316
2317                         flowTime = latency[sortByLatency[numFragments]]
2318                             - latency[sortByLatency[i]];
2319                         total += ((flowTime * priv->links[
2320                             priv->activeLinks[sortByLatency[i]]].conf.bandwidth)
2321                                 + 99) / 100;
2322                 }
2323                 if (total >= len)
2324                         break;
2325         }
2326
2327         /* Solve for t_0 in that interval */
2328         for (topSum = botSum = i = 0; i < numFragments; i++) {
2329                 int bw = priv->links[
2330                     priv->activeLinks[sortByLatency[i]]].conf.bandwidth;
2331
2332                 topSum += latency[sortByLatency[i]] * bw;       /* / 100 */
2333                 botSum += bw;                                   /* / 100 */
2334         }
2335         t0 = ((len * 100) + topSum + botSum / 2) / botSum;
2336
2337         /* Compute f_i(t_0) all i */
2338         for (total = i = 0; i < numFragments; i++) {
2339                 int bw = priv->links[
2340                     priv->activeLinks[sortByLatency[i]]].conf.bandwidth;
2341
2342                 distrib[sortByLatency[i]] =
2343                     (bw * (t0 - latency[sortByLatency[i]]) + 50) / 100;
2344                 total += distrib[sortByLatency[i]];
2345         }
2346
2347         /* Deal with any rounding error */
2348         if (total < len) {
2349                 struct ng_ppp_link *fastLink =
2350                     &priv->links[priv->activeLinks[sortByLatency[0]]];
2351                 int fast = 0;
2352
2353                 /* Find the fastest link */
2354                 for (i = 1; i < numFragments; i++) {
2355                         struct ng_ppp_link *const link =
2356                             &priv->links[priv->activeLinks[sortByLatency[i]]];
2357
2358                         if (link->conf.bandwidth > fastLink->conf.bandwidth) {
2359                                 fast = i;
2360                                 fastLink = link;
2361                         }
2362                 }
2363                 distrib[sortByLatency[fast]] += len - total;
2364         } else while (total > len) {
2365                 struct ng_ppp_link *slowLink =
2366                     &priv->links[priv->activeLinks[sortByLatency[0]]];
2367                 int delta, slow = 0;
2368
2369                 /* Find the slowest link that still has bytes to remove */
2370                 for (i = 1; i < numFragments; i++) {
2371                         struct ng_ppp_link *const link =
2372                             &priv->links[priv->activeLinks[sortByLatency[i]]];
2373
2374                         if (distrib[sortByLatency[slow]] == 0
2375                           || (distrib[sortByLatency[i]] > 0
2376                             && link->conf.bandwidth <
2377                               slowLink->conf.bandwidth)) {
2378                                 slow = i;
2379                                 slowLink = link;
2380                         }
2381                 }
2382                 delta = total - len;
2383                 if (delta > distrib[sortByLatency[slow]])
2384                         delta = distrib[sortByLatency[slow]];
2385                 distrib[sortByLatency[slow]] -= delta;
2386                 total -= delta;
2387         }
2388 }
2389
2390 /*
2391  * Compare two integers
2392  */
2393 static int
2394 ng_ppp_intcmp(void *latency, const void *v1, const void *v2)
2395 {
2396         const int index1 = *((const int *) v1);
2397         const int index2 = *((const int *) v2);
2398
2399         return ((int *)latency)[index1] - ((int *)latency)[index2];
2400 }
2401
2402 /*
2403  * Prepend a possibly compressed PPP protocol number in front of a frame
2404  */
2405 static struct mbuf *
2406 ng_ppp_addproto(struct mbuf *m, uint16_t proto, int compOK)
2407 {
2408         if (compOK && PROT_COMPRESSABLE(proto)) {
2409                 uint8_t pbyte = (uint8_t)proto;
2410
2411                 return ng_ppp_prepend(m, &pbyte, 1);
2412         } else {
2413                 uint16_t pword = htons((uint16_t)proto);
2414
2415                 return ng_ppp_prepend(m, &pword, 2);
2416         }
2417 }
2418
2419 /*
2420  * Cut a possibly compressed PPP protocol number from the front of a frame.
2421  */
2422 static struct mbuf *
2423 ng_ppp_cutproto(struct mbuf *m, uint16_t *proto)
2424 {
2425
2426         *proto = 0;
2427         if (m->m_len < 1 && (m = m_pullup(m, 1)) == NULL)
2428                 return (NULL);
2429
2430         *proto = *mtod(m, uint8_t *);
2431         m_adj(m, 1);
2432
2433         if (!PROT_VALID(*proto)) {
2434                 if (m->m_len < 1 && (m = m_pullup(m, 1)) == NULL)
2435                         return (NULL);
2436
2437                 *proto = (*proto << 8) + *mtod(m, uint8_t *);
2438                 m_adj(m, 1);
2439         }
2440
2441         return (m);
2442 }
2443
2444 /*
2445  * Prepend some bytes to an mbuf.
2446  */
2447 static struct mbuf *
2448 ng_ppp_prepend(struct mbuf *m, const void *buf, int len)
2449 {
2450         M_PREPEND(m, len, M_DONTWAIT);
2451         if (m == NULL || (m->m_len < len && (m = m_pullup(m, len)) == NULL))
2452                 return (NULL);
2453         bcopy(buf, mtod(m, uint8_t *), len);
2454         return (m);
2455 }
2456
2457 /*
2458  * Update private information that is derived from other private information
2459  */
2460 static void
2461 ng_ppp_update(node_p node, int newConf)
2462 {
2463         const priv_p priv = NG_NODE_PRIVATE(node);
2464         int i;
2465
2466         /* Update active status for VJ Compression */
2467         priv->vjCompHooked = priv->hooks[HOOK_INDEX_VJC_IP] != NULL
2468             && priv->hooks[HOOK_INDEX_VJC_COMP] != NULL
2469             && priv->hooks[HOOK_INDEX_VJC_UNCOMP] != NULL
2470             && priv->hooks[HOOK_INDEX_VJC_VJIP] != NULL;
2471
2472         /* Increase latency for each link an amount equal to one MP header */
2473         if (newConf) {
2474                 for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
2475                         int hdrBytes;
2476
2477                         if (priv->links[i].conf.bandwidth == 0)
2478                             continue;
2479
2480                         hdrBytes = MP_AVERAGE_LINK_OVERHEAD
2481                             + (priv->links[i].conf.enableACFComp ? 0 : 2)
2482                             + (priv->links[i].conf.enableProtoComp ? 1 : 2)
2483                             + (priv->conf.xmitShortSeq ? 2 : 4);
2484                         priv->links[i].latency =
2485                             priv->links[i].conf.latency +
2486                             (hdrBytes / priv->links[i].conf.bandwidth + 50) / 100;
2487                 }
2488         }
2489
2490         /* Update list of active links */
2491         bzero(&priv->activeLinks, sizeof(priv->activeLinks));
2492         priv->numActiveLinks = 0;
2493         priv->allLinksEqual = 1;
2494         for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
2495                 struct ng_ppp_link *const link = &priv->links[i];
2496
2497                 /* Is link active? */
2498                 if (link->conf.enableLink && link->hook != NULL) {
2499                         struct ng_ppp_link *link0;
2500
2501                         /* Add link to list of active links */
2502                         priv->activeLinks[priv->numActiveLinks++] = i;
2503                         link0 = &priv->links[priv->activeLinks[0]];
2504
2505                         /* Determine if all links are still equal */
2506                         if (link->latency != link0->latency
2507                           || link->conf.bandwidth != link0->conf.bandwidth)
2508                                 priv->allLinksEqual = 0;
2509
2510                         /* Initialize rec'd sequence number */
2511                         if (link->seq == MP_NOSEQ) {
2512                                 link->seq = (link == link0) ?
2513                                     MP_INITIAL_SEQ : link0->seq;
2514                         }
2515                 } else
2516                         link->seq = MP_NOSEQ;
2517         }
2518
2519         /* Update MP state as multi-link is active or not */
2520         if (priv->conf.enableMultilink && priv->numActiveLinks > 0)
2521                 ng_ppp_start_frag_timer(node);
2522         else {
2523                 ng_ppp_stop_frag_timer(node);
2524                 ng_ppp_frag_reset(node);
2525                 priv->xseq = MP_INITIAL_SEQ;
2526                 priv->mseq = MP_INITIAL_SEQ;
2527                 for (i = 0; i < NG_PPP_MAX_LINKS; i++) {
2528                         struct ng_ppp_link *const link = &priv->links[i];
2529
2530                         bzero(&link->lastWrite, sizeof(link->lastWrite));
2531                         link->bytesInQueue = 0;
2532                         link->seq = MP_NOSEQ;
2533                 }
2534         }
2535 }
2536
2537 /*
2538  * Determine if a new configuration would represent a valid change
2539  * from the current configuration and link activity status.
2540  */
2541 static int
2542 ng_ppp_config_valid(node_p node, const struct ng_ppp_node_conf *newConf)
2543 {
2544         const priv_p priv = NG_NODE_PRIVATE(node);
2545         int i, newNumLinksActive;
2546
2547         /* Check per-link config and count how many links would be active */
2548         for (newNumLinksActive = i = 0; i < NG_PPP_MAX_LINKS; i++) {
2549                 if (newConf->links[i].enableLink && priv->links[i].hook != NULL)
2550                         newNumLinksActive++;
2551                 if (!newConf->links[i].enableLink)
2552                         continue;
2553                 if (newConf->links[i].mru < MP_MIN_LINK_MRU)
2554                         return (0);
2555                 if (newConf->links[i].bandwidth == 0)
2556                         return (0);
2557                 if (newConf->links[i].bandwidth > NG_PPP_MAX_BANDWIDTH)
2558                         return (0);
2559                 if (newConf->links[i].latency > NG_PPP_MAX_LATENCY)
2560                         return (0);
2561         }
2562
2563         /* Disallow changes to multi-link configuration while MP is active */
2564         if (priv->numActiveLinks > 0 && newNumLinksActive > 0) {
2565                 if (!priv->conf.enableMultilink
2566                                 != !newConf->bund.enableMultilink
2567                     || !priv->conf.xmitShortSeq != !newConf->bund.xmitShortSeq
2568                     || !priv->conf.recvShortSeq != !newConf->bund.recvShortSeq)
2569                         return (0);
2570         }
2571
2572         /* At most one link can be active unless multi-link is enabled */
2573         if (!newConf->bund.enableMultilink && newNumLinksActive > 1)
2574                 return (0);
2575
2576         /* Configuration change would be valid */
2577         return (1);
2578 }
2579
2580 /*
2581  * Free all entries in the fragment queue
2582  */
2583 static void
2584 ng_ppp_frag_reset(node_p node)
2585 {
2586         const priv_p priv = NG_NODE_PRIVATE(node);
2587         struct ng_ppp_frag *qent, *qnext;
2588
2589         for (qent = TAILQ_FIRST(&priv->frags); qent; qent = qnext) {
2590                 qnext = TAILQ_NEXT(qent, f_qent);
2591                 NG_FREE_M(qent->data);
2592                 TAILQ_INSERT_HEAD(&priv->fragsfree, qent, f_qent);
2593         }
2594         TAILQ_INIT(&priv->frags);
2595 }
2596
2597 /*
2598  * Start fragment queue timer
2599  */
2600 static void
2601 ng_ppp_start_frag_timer(node_p node)
2602 {
2603         const priv_p priv = NG_NODE_PRIVATE(node);
2604
2605         if (!(callout_pending(&priv->fragTimer)))
2606                 ng_callout(&priv->fragTimer, node, NULL, MP_FRAGTIMER_INTERVAL,
2607                     ng_ppp_frag_timeout, NULL, 0);
2608 }
2609
2610 /*
2611  * Stop fragment queue timer
2612  */
2613 static void
2614 ng_ppp_stop_frag_timer(node_p node)
2615 {
2616         const priv_p priv = NG_NODE_PRIVATE(node);
2617
2618         if (callout_pending(&priv->fragTimer))
2619                 ng_uncallout(&priv->fragTimer, node);
2620 }