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