1 2 /* 3 * ng_ppp.c 4 * 5 * Copyright (c) 1996-1999 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@whistle.com> 38 * 39 * $FreeBSD$ 40 * $Whistle: ng_ppp.c,v 1.24 1999/11/01 09:24:52 julian Exp $ 41 */ 42 43 /* 44 * PPP node type. 45 */ 46 47 #include <sys/param.h> 48 #include <sys/systm.h> 49 #include <sys/kernel.h> 50 #include <sys/conf.h> 51 #include <sys/mbuf.h> 52 #include <sys/malloc.h> 53 #include <sys/errno.h> 54 #include <sys/socket.h> 55 #include <sys/syslog.h> 56 #include <sys/ctype.h> 57 58 #include <netgraph/ng_message.h> 59 #include <netgraph/netgraph.h> 60 #include <netgraph/ng_ppp.h> 61 #include <netgraph/ng_vjc.h> 62 63 #define PROT_VALID(p) (((p) & 0x0101) == 0x0001) 64 #define PROT_COMPRESSABLE(p) (((p) & 0xff00) == 0x0000) 65 66 /* Some PPP protocol numbers we're interested in */ 67 #define PROT_APPLETALK 0x0029 68 #define PROT_COMPD 0x00fd 69 #define PROT_CRYPTD 0x0053 70 #define PROT_IP 0x0021 71 #define PROT_IPX 0x002b 72 #define PROT_MP 0x003d 73 #define PROT_VJCOMP 0x002d 74 #define PROT_VJUNCOMP 0x002f 75 76 /* Multilink PPP definitions */ 77 #define MP_MIN_MRRU 1500 /* per RFC 1990 */ 78 #define MP_INITIAL_SEQ 0 /* per RFC 1990 */ 79 #define MP_MIN_LINK_MRU 32 80 81 #define MP_MAX_SEQ_LINGER 64 /* max frags we will hold */ 82 #define MP_INSANE_SEQ_JUMP 128 /* a sequence # jump too far */ 83 #define MP_MIN_FRAG_LEN 6 /* don't frag smaller frames */ 84 85 #define MP_SHORT_SEQ_MASK 0x00000fff /* short seq # mask */ 86 #define MP_SHORT_SEQ_HIBIT 0x00000800 /* short seq # high bit */ 87 #define MP_SHORT_FIRST_FLAG 0x00008000 /* first fragment in frame */ 88 #define MP_SHORT_LAST_FLAG 0x00004000 /* last fragment in frame */ 89 90 #define MP_LONG_SEQ_MASK 0x00ffffff /* long seq # mask */ 91 #define MP_LONG_SEQ_HIBIT 0x00800000 /* long seq # high bit */ 92 #define MP_LONG_FIRST_FLAG 0x80000000 /* first fragment in frame */ 93 #define MP_LONG_LAST_FLAG 0x40000000 /* last fragment in frame */ 94 95 #define MP_SEQ_MASK (priv->conf.recvShortSeq ? \ 96 MP_SHORT_SEQ_MASK : MP_LONG_SEQ_MASK) 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) : (s)) 101 #define MP_LONG_EXTEND(s) (((s) & MP_LONG_SEQ_HIBIT) ? \ 102 ((s) | ~MP_LONG_SEQ_MASK) : (s)) 103 104 /* Comparision of MP sequence numbers */ 105 #define MP_SHORT_SEQ_DIFF(x,y) (MP_SHORT_EXTEND(x) - MP_SHORT_EXTEND(y)) 106 #define MP_LONG_SEQ_DIFF(x,y) (MP_LONG_EXTEND(x) - MP_LONG_EXTEND(y)) 107 108 #define MP_SEQ_DIFF(x,y) (priv->conf.recvShortSeq ? \ 109 MP_SHORT_SEQ_DIFF((x), (y)) : \ 110 MP_LONG_SEQ_DIFF((x), (y))) 111 112 /* We store incoming fragments this way */ 113 struct ng_ppp_frag { 114 int seq; 115 u_char first; 116 u_char last; 117 struct mbuf *data; 118 meta_p meta; 119 CIRCLEQ_ENTRY(ng_ppp_frag) f_qent; 120 }; 121 122 /* We keep track of link queue status this way */ 123 struct ng_ppp_link_qstat { 124 struct timeval lastWrite; /* time of last write */ 125 int bytesInQueue; /* bytes in the queue then */ 126 }; 127 128 /* We use integer indicies to refer to the non-link hooks */ 129 static const char *const ng_ppp_hook_names[] = { 130 NG_PPP_HOOK_ATALK, 131 #define HOOK_INDEX_ATALK 0 132 NG_PPP_HOOK_BYPASS, 133 #define HOOK_INDEX_BYPASS 1 134 NG_PPP_HOOK_COMPRESS, 135 #define HOOK_INDEX_COMPRESS 2 136 NG_PPP_HOOK_ENCRYPT, 137 #define HOOK_INDEX_ENCRYPT 3 138 NG_PPP_HOOK_DECOMPRESS, 139 #define HOOK_INDEX_DECOMPRESS 4 140 NG_PPP_HOOK_DECRYPT, 141 #define HOOK_INDEX_DECRYPT 5 142 NG_PPP_HOOK_INET, 143 #define HOOK_INDEX_INET 6 144 NG_PPP_HOOK_IPX, 145 #define HOOK_INDEX_IPX 7 146 NG_PPP_HOOK_VJC_COMP, 147 #define HOOK_INDEX_VJC_COMP 8 148 NG_PPP_HOOK_VJC_IP, 149 #define HOOK_INDEX_VJC_IP 9 150 NG_PPP_HOOK_VJC_UNCOMP, 151 #define HOOK_INDEX_VJC_UNCOMP 10 152 NG_PPP_HOOK_VJC_VJIP, 153 #define HOOK_INDEX_VJC_VJIP 11 154 NULL 155 #define HOOK_INDEX_MAX 12 156 }; 157 158 /* We store index numbers in the hook private pointer. The HOOK_INDEX() 159 for a hook is either the index (above) for normal hooks, or the ones 160 complement of the link number for link hooks. */ 161 #define HOOK_INDEX(hook) (*((int16_t *) &(hook)->private)) 162 163 /* Node private data */ 164 struct private { 165 struct ng_ppp_node_config conf; 166 struct ng_ppp_link_stat bundleStats; 167 struct ng_ppp_link_stat linkStats[NG_PPP_MAX_LINKS]; 168 hook_p links[NG_PPP_MAX_LINKS]; 169 hook_p hooks[HOOK_INDEX_MAX]; 170 u_char vjCompHooked; 171 u_char allLinksEqual; 172 u_short activeLinks[NG_PPP_MAX_LINKS]; 173 u_int numActiveLinks; 174 u_int lastLink; /* for round robin */ 175 struct ng_ppp_link_qstat qstat[NG_PPP_MAX_LINKS]; 176 CIRCLEQ_HEAD(ng_ppp_fraglist, ng_ppp_frag) 177 frags; /* incoming fragments */ 178 int mpSeqOut; /* next out MP seq # */ 179 }; 180 typedef struct private *priv_p; 181 182 /* Netgraph node methods */ 183 static ng_constructor_t ng_ppp_constructor; 184 static ng_rcvmsg_t ng_ppp_rcvmsg; 185 static ng_shutdown_t ng_ppp_rmnode; 186 static ng_newhook_t ng_ppp_newhook; 187 static ng_rcvdata_t ng_ppp_rcvdata; 188 static ng_disconnect_t ng_ppp_disconnect; 189 190 /* Helper functions */ 191 static int ng_ppp_input(node_p node, int bypass, 192 int linkNum, struct mbuf *m, meta_p meta); 193 static int ng_ppp_output(node_p node, int bypass, 194 int linkNum, struct mbuf *m, meta_p meta); 195 static int ng_ppp_mp_input(node_p node, int linkNum, 196 struct mbuf *m, meta_p meta); 197 static int ng_ppp_mp_output(node_p node, struct mbuf *m, meta_p meta); 198 static void ng_ppp_mp_strategy(node_p node, int len, int *distrib); 199 static int ng_ppp_intcmp(const void *v1, const void *v2); 200 static struct mbuf *ng_ppp_addproto(struct mbuf *m, int proto, int compOK); 201 static int ng_ppp_config_valid(node_p node, 202 const struct ng_ppp_node_config *newConf); 203 static void ng_ppp_update(node_p node, int newConf); 204 static void ng_ppp_free_frags(node_p node); 205 206 /* Node type descriptor */ 207 static struct ng_type ng_ppp_typestruct = { 208 NG_VERSION, 209 NG_PPP_NODE_TYPE, 210 NULL, 211 ng_ppp_constructor, 212 ng_ppp_rcvmsg, 213 ng_ppp_rmnode, 214 ng_ppp_newhook, 215 NULL, 216 NULL, 217 ng_ppp_rcvdata, 218 ng_ppp_rcvdata, 219 ng_ppp_disconnect 220 }; 221 NETGRAPH_INIT(ppp, &ng_ppp_typestruct); 222 223 static int *compareLatencies; /* hack for ng_ppp_intcmp() */ 224 225 #define ERROUT(x) do { error = (x); goto done; } while (0) 226 227 /************************************************************************ 228 NETGRAPH NODE STUFF 229 ************************************************************************/ 230 231 /* 232 * Node type constructor 233 */ 234 static int 235 ng_ppp_constructor(node_p *nodep) 236 { 237 priv_p priv; 238 int error; 239 240 /* Allocate private structure */ 241 MALLOC(priv, priv_p, sizeof(*priv), M_NETGRAPH, M_WAITOK); 242 if (priv == NULL) 243 return (ENOMEM); 244 bzero(priv, sizeof(*priv)); 245 246 /* Call generic node constructor */ 247 if ((error = ng_make_node_common(&ng_ppp_typestruct, nodep))) { 248 FREE(priv, M_NETGRAPH); 249 return (error); 250 } 251 (*nodep)->private = priv; 252 253 /* Initialize state */ 254 CIRCLEQ_INIT(&priv->frags); 255 256 /* Done */ 257 return (0); 258 } 259 260 /* 261 * Give our OK for a hook to be added 262 */ 263 static int 264 ng_ppp_newhook(node_p node, hook_p hook, const char *name) 265 { 266 const priv_p priv = node->private; 267 int linkNum = -1; 268 hook_p *hookPtr = NULL; 269 int hookIndex = -1; 270 271 /* Figure out which hook it is */ 272 if (strncmp(name, NG_PPP_HOOK_LINK_PREFIX, /* a link hook? */ 273 strlen(NG_PPP_HOOK_LINK_PREFIX)) == 0) { 274 const char *cp, *eptr; 275 276 cp = name + strlen(NG_PPP_HOOK_LINK_PREFIX); 277 if (!isdigit(*cp) || (cp[0] == '0' && cp[1] != '\0')) 278 return (EINVAL); 279 linkNum = (int)strtoul(cp, &eptr, 10); 280 if (*eptr != '\0' || linkNum < 0 || linkNum >= NG_PPP_MAX_LINKS) 281 return (EINVAL); 282 hookPtr = &priv->links[linkNum]; 283 hookIndex = ~linkNum; 284 } else { /* must be a non-link hook */ 285 int i; 286 287 for (i = 0; ng_ppp_hook_names[i] != NULL; i++) { 288 if (strcmp(name, ng_ppp_hook_names[i]) == 0) { 289 hookPtr = &priv->hooks[i]; 290 hookIndex = i; 291 break; 292 } 293 } 294 if (ng_ppp_hook_names[i] == NULL) 295 return (EINVAL); /* no such hook */ 296 } 297 298 /* See if hook is already connected */ 299 if (*hookPtr != NULL) 300 return (EISCONN); 301 302 /* Disallow more than one link unless multilink is enabled */ 303 if (linkNum != -1 && priv->conf.links[linkNum].enableLink 304 && !priv->conf.enableMultilink && priv->numActiveLinks >= 1) 305 return (ENODEV); 306 307 /* OK */ 308 *hookPtr = hook; 309 HOOK_INDEX(hook) = hookIndex; 310 ng_ppp_update(node, 0); 311 return (0); 312 } 313 314 /* 315 * Receive a control message 316 */ 317 static int 318 ng_ppp_rcvmsg(node_p node, struct ng_mesg *msg, 319 const char *raddr, struct ng_mesg **rptr) 320 { 321 const priv_p priv = node->private; 322 struct ng_mesg *resp = NULL; 323 int error = 0; 324 325 switch (msg->header.typecookie) { 326 case NGM_PPP_COOKIE: 327 switch (msg->header.cmd) { 328 case NGM_PPP_SET_CONFIG: 329 { 330 struct ng_ppp_node_config *const newConf = 331 (struct ng_ppp_node_config *) msg->data; 332 333 /* Check for invalid or illegal config */ 334 if (msg->header.arglen != sizeof(*newConf)) 335 ERROUT(EINVAL); 336 if (!ng_ppp_config_valid(node, newConf)) 337 ERROUT(EINVAL); 338 priv->conf = *newConf; 339 ng_ppp_update(node, 1); 340 break; 341 } 342 case NGM_PPP_GET_CONFIG: 343 NG_MKRESPONSE(resp, msg, sizeof(priv->conf), M_NOWAIT); 344 if (resp == NULL) 345 ERROUT(ENOMEM); 346 bcopy(&priv->conf, resp->data, sizeof(priv->conf)); 347 break; 348 case NGM_PPP_GET_LINK_STATS: 349 case NGM_PPP_CLR_LINK_STATS: 350 case NGM_PPP_GETCLR_LINK_STATS: 351 { 352 struct ng_ppp_link_stat *stats; 353 u_int16_t linkNum; 354 355 if (msg->header.arglen != sizeof(u_int16_t)) 356 ERROUT(EINVAL); 357 linkNum = *((u_int16_t *) msg->data); 358 if (linkNum >= NG_PPP_MAX_LINKS 359 && linkNum != NG_PPP_BUNDLE_LINKNUM) 360 ERROUT(EINVAL); 361 stats = (linkNum == NG_PPP_BUNDLE_LINKNUM) ? 362 &priv->bundleStats : &priv->linkStats[linkNum]; 363 if (msg->header.cmd != NGM_PPP_CLR_LINK_STATS) { 364 NG_MKRESPONSE(resp, msg, 365 sizeof(struct ng_ppp_link_stat), M_NOWAIT); 366 if (resp == NULL) 367 ERROUT(ENOMEM); 368 bcopy(stats, resp->data, sizeof(*stats)); 369 } 370 if (msg->header.cmd != NGM_PPP_GET_LINK_STATS) 371 bzero(stats, sizeof(*stats)); 372 break; 373 } 374 default: 375 error = EINVAL; 376 break; 377 } 378 break; 379 case NGM_VJC_COOKIE: 380 { 381 char path[NG_PATHLEN + 1]; 382 node_p origNode; 383 384 if ((error = ng_path2node(node, raddr, &origNode, NULL)) != 0) 385 ERROUT(error); 386 snprintf(path, sizeof(path), "[%lx]:%s", 387 (long) node, NG_PPP_HOOK_VJC_IP); 388 return ng_send_msg(origNode, msg, path, rptr); 389 break; 390 } 391 default: 392 error = EINVAL; 393 break; 394 } 395 if (rptr) 396 *rptr = resp; 397 else if (resp) 398 FREE(resp, M_NETGRAPH); 399 400 done: 401 FREE(msg, M_NETGRAPH); 402 return (error); 403 } 404 405 /* 406 * Receive data on a hook 407 */ 408 static int 409 ng_ppp_rcvdata(hook_p hook, struct mbuf *m, meta_p meta) 410 { 411 const node_p node = hook->node; 412 const priv_p priv = node->private; 413 const int index = HOOK_INDEX(hook); 414 u_int16_t linkNum = NG_PPP_BUNDLE_LINKNUM; 415 hook_p outHook = NULL; 416 int proto = 0, error; 417 418 /* Did it come from a link hook? */ 419 if (index < 0) { 420 421 /* Convert index into a link number */ 422 linkNum = (u_int16_t)~index; 423 KASSERT(linkNum < NG_PPP_MAX_LINKS, 424 ("%s: bogus index 0x%x", __FUNCTION__, index)); 425 426 /* Stats */ 427 priv->linkStats[linkNum].recvFrames++; 428 priv->linkStats[linkNum].recvOctets += m->m_pkthdr.len; 429 430 /* Dispatch incoming frame (if not enabled, to bypass) */ 431 return ng_ppp_input(node, 432 !priv->conf.links[linkNum].enableLink, linkNum, m, meta); 433 } 434 435 /* Get protocol & check if data allowed from this hook */ 436 switch (index) { 437 438 /* Outgoing data */ 439 case HOOK_INDEX_ATALK: 440 if (!priv->conf.enableAtalk) { 441 NG_FREE_DATA(m, meta); 442 return (ENXIO); 443 } 444 proto = PROT_APPLETALK; 445 break; 446 case HOOK_INDEX_IPX: 447 if (!priv->conf.enableIPX) { 448 NG_FREE_DATA(m, meta); 449 return (ENXIO); 450 } 451 proto = PROT_IPX; 452 break; 453 case HOOK_INDEX_INET: 454 case HOOK_INDEX_VJC_VJIP: 455 if (!priv->conf.enableIP) { 456 NG_FREE_DATA(m, meta); 457 return (ENXIO); 458 } 459 proto = PROT_IP; 460 break; 461 case HOOK_INDEX_VJC_COMP: 462 if (!priv->conf.enableVJCompression) { 463 NG_FREE_DATA(m, meta); 464 return (ENXIO); 465 } 466 proto = PROT_VJCOMP; 467 break; 468 case HOOK_INDEX_VJC_UNCOMP: 469 if (!priv->conf.enableVJCompression) { 470 NG_FREE_DATA(m, meta); 471 return (ENXIO); 472 } 473 proto = PROT_VJUNCOMP; 474 break; 475 case HOOK_INDEX_COMPRESS: 476 if (!priv->conf.enableCompression) { 477 NG_FREE_DATA(m, meta); 478 return (ENXIO); 479 } 480 proto = PROT_COMPD; 481 break; 482 case HOOK_INDEX_ENCRYPT: 483 if (!priv->conf.enableEncryption) { 484 NG_FREE_DATA(m, meta); 485 return (ENXIO); 486 } 487 proto = PROT_CRYPTD; 488 break; 489 case HOOK_INDEX_BYPASS: 490 if (m->m_pkthdr.len < 4) { 491 NG_FREE_META(meta); 492 return (EINVAL); 493 } 494 if (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL) { 495 NG_FREE_META(meta); 496 return (ENOBUFS); 497 } 498 linkNum = ntohs(mtod(m, u_int16_t *)[0]); 499 proto = ntohs(mtod(m, u_int16_t *)[1]); 500 m_adj(m, 4); 501 if (linkNum >= NG_PPP_MAX_LINKS 502 && linkNum != NG_PPP_BUNDLE_LINKNUM) 503 return (EINVAL); 504 break; 505 506 /* Incoming data */ 507 case HOOK_INDEX_VJC_IP: 508 if (!priv->conf.enableIP || !priv->conf.enableVJDecompression) { 509 NG_FREE_DATA(m, meta); 510 return (ENXIO); 511 } 512 break; 513 case HOOK_INDEX_DECOMPRESS: 514 if (!priv->conf.enableDecompression) { 515 NG_FREE_DATA(m, meta); 516 return (ENXIO); 517 } 518 break; 519 case HOOK_INDEX_DECRYPT: 520 if (!priv->conf.enableDecryption) { 521 NG_FREE_DATA(m, meta); 522 return (ENXIO); 523 } 524 break; 525 default: 526 panic("%s: bogus index 0x%x", __FUNCTION__, index); 527 } 528 529 /* Now figure out what to do with the frame */ 530 switch (index) { 531 532 /* Outgoing data */ 533 case HOOK_INDEX_INET: 534 if (priv->conf.enableVJCompression && priv->vjCompHooked) { 535 outHook = priv->hooks[HOOK_INDEX_VJC_IP]; 536 break; 537 } 538 /* FALLTHROUGH */ 539 case HOOK_INDEX_ATALK: 540 case HOOK_INDEX_IPX: 541 case HOOK_INDEX_VJC_COMP: 542 case HOOK_INDEX_VJC_UNCOMP: 543 case HOOK_INDEX_VJC_VJIP: 544 if (priv->conf.enableCompression 545 && priv->hooks[HOOK_INDEX_COMPRESS] != NULL) { 546 if ((m = ng_ppp_addproto(m, proto, 1)) == NULL) { 547 NG_FREE_META(meta); 548 return (ENOBUFS); 549 } 550 outHook = priv->hooks[HOOK_INDEX_COMPRESS]; 551 break; 552 } 553 /* FALLTHROUGH */ 554 case HOOK_INDEX_COMPRESS: 555 if (priv->conf.enableEncryption 556 && priv->hooks[HOOK_INDEX_ENCRYPT] != NULL) { 557 if ((m = ng_ppp_addproto(m, proto, 1)) == NULL) { 558 NG_FREE_META(meta); 559 return (ENOBUFS); 560 } 561 outHook = priv->hooks[HOOK_INDEX_ENCRYPT]; 562 break; 563 } 564 /* FALLTHROUGH */ 565 case HOOK_INDEX_ENCRYPT: 566 case HOOK_INDEX_BYPASS: 567 if ((m = ng_ppp_addproto(m, proto, 568 linkNum == NG_PPP_BUNDLE_LINKNUM 569 || priv->conf.links[linkNum].enableProtoComp)) == NULL) { 570 NG_FREE_META(meta); 571 return (ENOBUFS); 572 } 573 return ng_ppp_output(node, 574 index == HOOK_INDEX_BYPASS, NG_PPP_BUNDLE_LINKNUM, m, meta); 575 576 /* Incoming data */ 577 case HOOK_INDEX_DECRYPT: 578 case HOOK_INDEX_DECOMPRESS: 579 return ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta); 580 581 case HOOK_INDEX_VJC_IP: 582 outHook = priv->hooks[HOOK_INDEX_INET]; 583 break; 584 } 585 586 /* Send packet out hook */ 587 NG_SEND_DATA(error, outHook, m, meta); 588 return (error); 589 } 590 591 /* 592 * Destroy node 593 */ 594 static int 595 ng_ppp_rmnode(node_p node) 596 { 597 const priv_p priv = node->private; 598 599 /* Take down netgraph node */ 600 node->flags |= NG_INVALID; 601 ng_cutlinks(node); 602 ng_unname(node); 603 ng_ppp_free_frags(node); 604 bzero(priv, sizeof(*priv)); 605 FREE(priv, M_NETGRAPH); 606 node->private = NULL; 607 ng_unref(node); /* let the node escape */ 608 return (0); 609 } 610 611 /* 612 * Hook disconnection 613 */ 614 static int 615 ng_ppp_disconnect(hook_p hook) 616 { 617 if (hook->node->numhooks == 0) 618 ng_rmnode(hook->node); 619 return (0); 620 } 621 622 /************************************************************************ 623 HELPER STUFF 624 ************************************************************************/ 625 626 /* 627 * Handle an incoming frame. Extract the PPP protocol number 628 * and dispatch accordingly. 629 */ 630 static int 631 ng_ppp_input(node_p node, int bypass, int linkNum, struct mbuf *m, meta_p meta) 632 { 633 const priv_p priv = node->private; 634 hook_p outHook = NULL; 635 int proto, error; 636 637 /* Extract protocol number */ 638 for (proto = 0; !PROT_VALID(proto) && m->m_pkthdr.len > 0; ) { 639 if (m->m_len < 1 && (m = m_pullup(m, 1)) == NULL) { 640 NG_FREE_META(meta); 641 return (ENOBUFS); 642 } 643 proto = (proto << 8) + *mtod(m, u_char *); 644 m_adj(m, 1); 645 } 646 if (!PROT_VALID(proto)) { 647 if (linkNum == NG_PPP_BUNDLE_LINKNUM) 648 priv->bundleStats.badProtos++; 649 else 650 priv->linkStats[linkNum].badProtos++; 651 NG_FREE_DATA(m, meta); 652 return (EINVAL); 653 } 654 655 /* Bypass frame? */ 656 if (bypass) 657 goto bypass; 658 659 /* Check protocol */ 660 switch (proto) { 661 case PROT_COMPD: 662 if (priv->conf.enableDecompression) 663 outHook = priv->hooks[HOOK_INDEX_DECOMPRESS]; 664 break; 665 case PROT_CRYPTD: 666 if (priv->conf.enableDecryption) 667 outHook = priv->hooks[HOOK_INDEX_DECRYPT]; 668 break; 669 case PROT_VJCOMP: 670 if (priv->conf.enableVJDecompression && priv->vjCompHooked) 671 outHook = priv->hooks[HOOK_INDEX_VJC_COMP]; 672 break; 673 case PROT_VJUNCOMP: 674 if (priv->conf.enableVJDecompression && priv->vjCompHooked) 675 outHook = priv->hooks[HOOK_INDEX_VJC_UNCOMP]; 676 break; 677 case PROT_MP: 678 if (priv->conf.enableMultilink) { 679 NG_FREE_META(meta); 680 return ng_ppp_mp_input(node, linkNum, m, meta); 681 } 682 break; 683 case PROT_APPLETALK: 684 if (priv->conf.enableAtalk) 685 outHook = priv->hooks[HOOK_INDEX_ATALK]; 686 break; 687 case PROT_IPX: 688 if (priv->conf.enableIPX) 689 outHook = priv->hooks[HOOK_INDEX_IPX]; 690 break; 691 case PROT_IP: 692 if (priv->conf.enableIP) 693 outHook = priv->hooks[HOOK_INDEX_INET]; 694 break; 695 } 696 697 /* For unknown/inactive protocols, forward out the bypass hook */ 698 bypass: 699 if (outHook == NULL) { 700 M_PREPEND(m, 4, M_NOWAIT); 701 if (m == NULL || (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL)) 702 return (ENOBUFS); 703 mtod(m, u_int16_t *)[0] = htons(linkNum); 704 mtod(m, u_int16_t *)[1] = htons(proto); 705 outHook = priv->hooks[HOOK_INDEX_BYPASS]; 706 } 707 708 /* Forward frame */ 709 NG_SEND_DATA(error, outHook, m, meta); 710 return (error); 711 } 712 713 /* 714 * Deliver a frame out a link, either a real one or NG_PPP_BUNDLE_LINKNUM 715 */ 716 static int 717 ng_ppp_output(node_p node, int bypass, int linkNum, struct mbuf *m, meta_p meta) 718 { 719 const priv_p priv = node->private; 720 int len, error; 721 722 /* Check for bundle virtual link */ 723 if (linkNum == NG_PPP_BUNDLE_LINKNUM) { 724 if (priv->conf.enableMultilink) 725 return ng_ppp_mp_output(node, m, meta); 726 linkNum = priv->activeLinks[0]; 727 } 728 729 /* Check link status */ 730 if (!bypass && !priv->conf.links[linkNum].enableLink) 731 return (ENXIO); 732 if (priv->links[linkNum] == NULL) { 733 NG_FREE_DATA(m, meta); 734 return (ENETDOWN); 735 } 736 737 /* Deliver frame */ 738 len = m->m_pkthdr.len; 739 NG_SEND_DATA(error, priv->links[linkNum], m, meta); 740 741 /* Update stats and 'bytes in queue' counter */ 742 if (error == 0) { 743 priv->linkStats[linkNum].xmitFrames++; 744 priv->linkStats[linkNum].xmitOctets += len; 745 priv->qstat[linkNum].bytesInQueue += len; 746 microtime(&priv->qstat[linkNum].lastWrite); 747 } 748 return error; 749 } 750 751 /* 752 * Handle an incoming multi-link fragment 753 */ 754 static int 755 ng_ppp_mp_input(node_p node, int linkNum, struct mbuf *m, meta_p meta) 756 { 757 const priv_p priv = node->private; 758 struct ng_ppp_frag frag0, *frag = &frag0; 759 struct ng_ppp_frag *qent, *qnext; 760 struct ng_ppp_frag *first = NULL, *last = NULL; 761 int diff, highSeq, nextSeq; 762 struct mbuf *tail; 763 764 /* Extract fragment information from MP header */ 765 if (priv->conf.recvShortSeq) { 766 u_int16_t shdr; 767 768 if (m->m_pkthdr.len < 2) { 769 NG_FREE_DATA(m, meta); 770 return (EINVAL); 771 } 772 if (m->m_len < 2 && (m = m_pullup(m, 2)) == NULL) { 773 NG_FREE_META(meta); 774 return (ENOBUFS); 775 } 776 shdr = ntohs(*mtod(m, u_int16_t *)); 777 frag->seq = shdr & MP_SHORT_SEQ_MASK; 778 frag->first = (shdr & MP_SHORT_FIRST_FLAG) != 0; 779 frag->last = (shdr & MP_SHORT_LAST_FLAG) != 0; 780 highSeq = CIRCLEQ_EMPTY(&priv->frags) ? 781 frag->seq : CIRCLEQ_FIRST(&priv->frags)->seq; 782 diff = MP_SHORT_SEQ_DIFF(frag->seq, highSeq); 783 m_adj(m, 2); 784 } else { 785 u_int32_t lhdr; 786 787 if (m->m_pkthdr.len < 4) { 788 NG_FREE_DATA(m, meta); 789 return (EINVAL); 790 } 791 if (m->m_len < 4 && (m = m_pullup(m, 4)) == NULL) { 792 NG_FREE_META(meta); 793 return (ENOBUFS); 794 } 795 lhdr = ntohl(*mtod(m, u_int32_t *)); 796 frag->seq = lhdr & MP_LONG_SEQ_MASK; 797 frag->first = (lhdr & MP_LONG_FIRST_FLAG) != 0; 798 frag->last = (lhdr & MP_LONG_LAST_FLAG) != 0; 799 highSeq = CIRCLEQ_EMPTY(&priv->frags) ? 800 frag->seq : CIRCLEQ_FIRST(&priv->frags)->seq; 801 diff = MP_LONG_SEQ_DIFF(frag->seq, highSeq); 802 m_adj(m, 4); 803 } 804 frag->data = m; 805 frag->meta = meta; 806 807 /* If the sequence number makes a large jump, empty the queue */ 808 if (diff <= -MP_INSANE_SEQ_JUMP || diff >= MP_INSANE_SEQ_JUMP) 809 ng_ppp_free_frags(node); 810 811 /* Optimization: handle a frame that's all in one fragment */ 812 if (frag->first && frag->last) 813 return ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta); 814 815 /* Allocate a new frag struct for the queue */ 816 MALLOC(frag, struct ng_ppp_frag *, sizeof(*frag), M_NETGRAPH, M_NOWAIT); 817 if (frag == NULL) { 818 NG_FREE_DATA(m, meta); 819 return (ENOMEM); 820 } 821 *frag = frag0; 822 meta = NULL; 823 m = NULL; 824 825 /* Add fragment to queue, which is reverse sorted by sequence number */ 826 CIRCLEQ_FOREACH(qent, &priv->frags, f_qent) { 827 diff = MP_SEQ_DIFF(frag->seq, qent->seq); 828 if (diff > 0) { 829 CIRCLEQ_INSERT_BEFORE(&priv->frags, qent, frag, f_qent); 830 break; 831 } else if (diff == 0) { /* should never happen! */ 832 log(LOG_ERR, "%s: rec'd dup MP fragment\n", node->name); 833 if (linkNum == NG_PPP_BUNDLE_LINKNUM) 834 priv->linkStats[linkNum].dupFragments++; 835 else 836 priv->bundleStats.dupFragments++; 837 NG_FREE_DATA(frag->data, frag->meta); 838 FREE(frag, M_NETGRAPH); 839 return (EINVAL); 840 } 841 } 842 if (qent == NULL) 843 CIRCLEQ_INSERT_TAIL(&priv->frags, frag, f_qent); 844 845 /* Find the first fragment in the possibly newly completed frame */ 846 for (nextSeq = frag->seq, qent = frag; 847 qent != (void *) &priv->frags; 848 qent = CIRCLEQ_PREV(qent, f_qent)) { 849 if (qent->seq != nextSeq) 850 goto pruneQueue; 851 if (qent->first) { 852 first = qent; 853 break; 854 } 855 nextSeq = (nextSeq + 1) & MP_SEQ_MASK; 856 } 857 858 /* Find the last fragment in the possibly newly completed frame */ 859 for (nextSeq = frag->seq, qent = frag; 860 qent != (void *) &priv->frags; 861 qent = CIRCLEQ_NEXT(qent, f_qent)) { 862 if (qent->seq != nextSeq) 863 goto pruneQueue; 864 if (qent->last) { 865 last = qent; 866 break; 867 } 868 nextSeq = (nextSeq - 1) & MP_SEQ_MASK; 869 } 870 871 /* We have a complete frame, extract it from the queue */ 872 for (tail = NULL, qent = first; qent != NULL; qent = qnext) { 873 qnext = CIRCLEQ_PREV(qent, f_qent); 874 CIRCLEQ_REMOVE(&priv->frags, qent, f_qent); 875 if (tail == NULL) { 876 tail = m = qent->data; 877 meta = qent->meta; /* inherit first frag's meta */ 878 } else { 879 m->m_pkthdr.len += qent->data->m_pkthdr.len; 880 tail->m_next = qent->data; 881 NG_FREE_META(qent->meta); /* drop other frag's metas */ 882 } 883 while (tail->m_next != NULL) 884 tail = tail->m_next; 885 if (qent == last) 886 qnext = NULL; 887 FREE(qent, M_NETGRAPH); 888 } 889 890 pruneQueue: 891 /* Prune out stale entries in the queue */ 892 for (qent = CIRCLEQ_LAST(&priv->frags); 893 qent != (void *) &priv->frags; qent = qnext) { 894 if (MP_SEQ_DIFF(highSeq, qent->seq) <= MP_MAX_SEQ_LINGER) 895 break; 896 qnext = CIRCLEQ_PREV(qent, f_qent); 897 CIRCLEQ_REMOVE(&priv->frags, qent, f_qent); 898 NG_FREE_DATA(qent->data, qent->meta); 899 FREE(qent, M_NETGRAPH); 900 } 901 902 /* Deliver newly completed frame, if any */ 903 return m ? ng_ppp_input(node, 0, NG_PPP_BUNDLE_LINKNUM, m, meta) : 0; 904 } 905 906 /* 907 * Deliver a frame out on the bundle, i.e., figure out how to fragment 908 * the frame across the individual PPP links and do so. 909 */ 910 static int 911 ng_ppp_mp_output(node_p node, struct mbuf *m, meta_p meta) 912 { 913 const priv_p priv = node->private; 914 int distrib[NG_PPP_MAX_LINKS]; 915 int firstFragment; 916 int activeLinkNum; 917 918 /* At least one link must be active */ 919 if (priv->numActiveLinks == 0) { 920 NG_FREE_DATA(m, meta); 921 return (ENETDOWN); 922 } 923 924 /* Round-robin strategy */ 925 if (priv->conf.enableRoundRobin || m->m_pkthdr.len < MP_MIN_FRAG_LEN) { 926 activeLinkNum = priv->lastLink++ % priv->numActiveLinks; 927 bzero(&distrib, priv->numActiveLinks * sizeof(distrib[0])); 928 distrib[activeLinkNum] = m->m_pkthdr.len; 929 goto deliver; 930 } 931 932 /* Strategy when all links are equivalent (optimize the common case) */ 933 if (priv->allLinksEqual) { 934 const int fraction = m->m_pkthdr.len / priv->numActiveLinks; 935 int i, remain; 936 937 for (i = 0; i < priv->numActiveLinks; i++) 938 distrib[priv->lastLink++ % priv->numActiveLinks] 939 = fraction; 940 remain = m->m_pkthdr.len - (fraction * priv->numActiveLinks); 941 while (remain > 0) { 942 distrib[priv->lastLink++ % priv->numActiveLinks]++; 943 remain--; 944 } 945 goto deliver; 946 } 947 948 /* Strategy when all links are not equivalent */ 949 ng_ppp_mp_strategy(node, m->m_pkthdr.len, distrib); 950 951 deliver: 952 /* Update stats */ 953 priv->bundleStats.xmitFrames++; 954 priv->bundleStats.xmitOctets += m->m_pkthdr.len; 955 956 /* Send alloted portions of frame out on the link(s) */ 957 for (firstFragment = 1, activeLinkNum = priv->numActiveLinks - 1; 958 activeLinkNum >= 0; activeLinkNum--) { 959 const int linkNum = priv->activeLinks[activeLinkNum]; 960 961 /* Deliver fragment(s) out the next link */ 962 for ( ; distrib[activeLinkNum] > 0; firstFragment = 0) { 963 int len, lastFragment, error; 964 struct mbuf *m2; 965 meta_p meta2; 966 967 /* Calculate fragment length; don't exceed link MTU */ 968 len = distrib[activeLinkNum]; 969 if (len > priv->conf.links[linkNum].mru) 970 len = priv->conf.links[linkNum].mru; 971 distrib[activeLinkNum] -= len; 972 lastFragment = (len == m->m_pkthdr.len); 973 974 /* Split off next fragment as "m2" */ 975 m2 = m; 976 if (!lastFragment) { 977 struct mbuf *n = m_split(m, len, M_NOWAIT); 978 979 if (n == NULL) { 980 NG_FREE_DATA(m, meta); 981 return (ENOMEM); 982 } 983 m = n; 984 } 985 986 /* Prepend MP header */ 987 if (priv->conf.xmitShortSeq) { 988 u_int16_t shdr; 989 990 M_PREPEND(m2, 2, M_NOWAIT); 991 if (m2 == NULL 992 || (m2->m_len < 2 993 && (m2 = m_pullup(m2, 2)) == NULL)) { 994 if (!lastFragment) 995 m_freem(m); 996 NG_FREE_META(meta); 997 return (ENOBUFS); 998 } 999 shdr = priv->mpSeqOut; 1000 priv->mpSeqOut = 1001 (priv->mpSeqOut + 1) % MP_SHORT_SEQ_MASK; 1002 if (firstFragment) 1003 shdr |= MP_SHORT_FIRST_FLAG; 1004 if (lastFragment) 1005 shdr |= MP_SHORT_LAST_FLAG; 1006 *mtod(m2, u_int16_t *) = htons(shdr); 1007 } else { 1008 u_int32_t lhdr; 1009 1010 M_PREPEND(m2, 4, M_NOWAIT); 1011 if (m2 == NULL 1012 || (m2->m_len < 4 1013 && (m2 = m_pullup(m2, 4)) == NULL)) { 1014 if (!lastFragment) 1015 m_freem(m); 1016 NG_FREE_META(meta); 1017 return (ENOBUFS); 1018 } 1019 lhdr = priv->mpSeqOut; 1020 priv->mpSeqOut = 1021 (priv->mpSeqOut + 1) % MP_LONG_SEQ_MASK; 1022 if (firstFragment) 1023 lhdr |= MP_LONG_FIRST_FLAG; 1024 if (lastFragment) 1025 lhdr |= MP_LONG_LAST_FLAG; 1026 *mtod(m2, u_int32_t *) = htonl(lhdr); 1027 } 1028 1029 /* Add MP protocol number */ 1030 m2 = ng_ppp_addproto(m, PROT_MP, 1031 priv->conf.links[linkNum].enableProtoComp); 1032 if (m2 == NULL) { 1033 if (!lastFragment) 1034 m_freem(m); 1035 NG_FREE_META(meta); 1036 return (ENOBUFS); 1037 } 1038 1039 /* Copy the meta information, if any */ 1040 if (meta != NULL && !lastFragment) { 1041 MALLOC(meta2, meta_p, 1042 meta->used_len, M_NETGRAPH, M_NOWAIT); 1043 if (meta2 == NULL) { 1044 m_freem(m2); 1045 NG_FREE_DATA(m, meta); 1046 return (ENOMEM); 1047 } 1048 meta2->allocated_len = meta->used_len; 1049 bcopy(meta, meta2, meta->used_len); 1050 } else 1051 meta2 = meta; 1052 1053 /* Send fragment */ 1054 error = ng_ppp_output(node, 0, linkNum, m2, meta2); 1055 1056 /* Abort for error */ 1057 if (error != 0) { 1058 if (!lastFragment) 1059 NG_FREE_DATA(m, meta); 1060 return (error); 1061 } 1062 } 1063 } 1064 1065 /* Done */ 1066 return (0); 1067 } 1068 1069 /* 1070 * Computing the optimal fragmentation 1071 * ----------------------------------- 1072 * 1073 * This routine tries to compute the optimal fragmentation pattern based 1074 * on each link's latency, bandwidth, and calculated additional latency. 1075 * The latter quantity is the additional latency caused by previously 1076 * written data that has not been transmitted yet. 1077 * 1078 * This algorithm is only useful when not all of the links have the 1079 * same latency and bandwidth values. 1080 * 1081 * The essential idea is to make the last bit of each fragment of the 1082 * frame arrive at the opposite end at the exact same time. This greedy 1083 * algorithm is optimal, in that no other scheduling could result in any 1084 * packet arriving any sooner unless packets are delivered out of order. 1085 * 1086 * Suppose link i has bandwidth b_i (in tens of bytes per milisecond) and 1087 * latency l_i (in miliseconds). Consider the function function f_i(t) 1088 * which is equal to the number of bytes that will have arrived at 1089 * the peer after t miliseconds if we start writing continuously at 1090 * time t = 0. Then f_i(t) = b_i * (t - l_i) = ((b_i * t) - (l_i * b_i). 1091 * That is, f_i(t) is a line with slope b_i and y-intersect -(l_i * b_i). 1092 * Note that the y-intersect is always <= zero because latency can't be 1093 * negative. Note also that really the function is f_i(t) except when 1094 * f_i(t) is negative, in which case the function is zero. To take 1095 * care of this, let Q_i(t) = { if (f_i(t) > 0) return 1; else return 0; }. 1096 * So the actual number of bytes that will have arrived at the peer after 1097 * t miliseconds is f_i(t) * Q_i(t). 1098 * 1099 * At any given time, each link has some additional latency a_i >= 0 1100 * due to previously written fragment(s) which are still in the queue. 1101 * This value is easily computed from the time since last transmission, 1102 * the previous latency value, the number of bytes written, and the 1103 * link's bandwidth. 1104 * 1105 * Assume that l_i includes any a_i already, and that the links are 1106 * sorted by latency, so that l_i <= l_{i+1}. 1107 * 1108 * Let N be the total number of bytes in the current frame we are sending. 1109 * 1110 * Suppose we were to start writing bytes at time t = 0 on all links 1111 * simultaneously, which is the most we can possibly do. Then let 1112 * F(t) be equal to the total number of bytes received by the peer 1113 * after t miliseconds. Then F(t) = Sum_i (f_i(t) * Q_i(t)). 1114 * 1115 * Our goal is simply this: fragment the frame across the links such 1116 * that the peer is able to reconstruct the completed frame as soon as 1117 * possible, i.e., at the least possible value of t. Call this value t_0. 1118 * 1119 * Then it follows that F(t_0) = N. Our strategy is first to find the value 1120 * of t_0, and then deduce how many bytes to write to each link. 1121 * 1122 * Rewriting F(t_0): 1123 * 1124 * t_0 = ( N + Sum_i ( l_i * b_i * Q_i(t_0) ) ) / Sum_i ( b_i * Q_i(t_0) ) 1125 * 1126 * Now, we note that Q_i(t) is constant for l_i <= t <= l_{i+1}. t_0 will 1127 * lie in one of these ranges. To find it, we just need to find the i such 1128 * that F(l_i) <= N <= F(l_{i+1}). Then we compute all the constant values 1129 * for Q_i() in this range, plug in the remaining values, solving for t_0. 1130 * 1131 * Once t_0 is known, then the number of bytes to send on link i is 1132 * just f_i(t_0) * Q_i(t_0). 1133 * 1134 * In other words, we start allocating bytes to the links one at a time. 1135 * We keep adding links until the frame is completely sent. Some links 1136 * may not get any bytes because their latency is too high. 1137 * 1138 * Is all this work really worth the trouble? Depends on the situation. 1139 * The bigger the ratio of computer speed to link speed, and the more 1140 * important total bundle latency is (e.g., for interactive response time), 1141 * the more it's worth it. There is however the cost of calling this 1142 * function for every frame. The running time is O(n^2) where n is the 1143 * number of links that receive a non-zero number of bytes. 1144 * 1145 * Since latency is measured in miliseconds, the "resolution" of this 1146 * algorithm is one milisecond. 1147 * 1148 * To avoid this algorithm altogether, configure all links to have the 1149 * same latency and bandwidth. 1150 */ 1151 static void 1152 ng_ppp_mp_strategy(node_p node, int len, int *distrib) 1153 { 1154 const priv_p priv = node->private; 1155 int latency[NG_PPP_MAX_LINKS]; 1156 int sortByLatency[NG_PPP_MAX_LINKS]; 1157 int activeLinkNum, linkNum; 1158 int t0, total, topSum, botSum; 1159 struct timeval now; 1160 int i, numFragments; 1161 1162 /* If only one link, this gets real easy */ 1163 if (priv->numActiveLinks == 1) { 1164 distrib[0] = len; 1165 return; 1166 } 1167 1168 /* Get current time */ 1169 microtime(&now); 1170 1171 /* Compute latencies for each link at this point in time */ 1172 for (activeLinkNum = 0; 1173 activeLinkNum < priv->numActiveLinks; activeLinkNum++) { 1174 struct timeval diff; 1175 int xmitBytes; 1176 1177 /* Start with base latency value */ 1178 linkNum = priv->activeLinks[activeLinkNum]; 1179 latency[activeLinkNum] = priv->conf.links[linkNum].latency; 1180 sortByLatency[activeLinkNum] = activeLinkNum; /* see below */ 1181 1182 /* Any additional latency? */ 1183 if (priv->qstat[activeLinkNum].bytesInQueue == 0) 1184 continue; 1185 1186 /* Compute time delta since last write */ 1187 diff = now; 1188 timevalsub(&diff, &priv->qstat[activeLinkNum].lastWrite); 1189 if (now.tv_sec < 0 || diff.tv_sec >= 10) { /* sanity */ 1190 priv->qstat[activeLinkNum].bytesInQueue = 0; 1191 continue; 1192 } 1193 1194 /* How many bytes could have transmitted since last write? */ 1195 xmitBytes = priv->conf.links[linkNum].bandwidth * diff.tv_sec 1196 + (priv->conf.links[linkNum].bandwidth 1197 * (diff.tv_usec / 1000)) / 100; 1198 priv->qstat[activeLinkNum].bytesInQueue -= xmitBytes; 1199 if (priv->qstat[activeLinkNum].bytesInQueue < 0) 1200 priv->qstat[activeLinkNum].bytesInQueue = 0; 1201 else 1202 latency[activeLinkNum] += 1203 (100 * priv->qstat[activeLinkNum].bytesInQueue) 1204 / priv->conf.links[linkNum].bandwidth; 1205 } 1206 1207 /* Sort links by latency */ 1208 compareLatencies = latency; 1209 qsort(sortByLatency, 1210 priv->numActiveLinks, sizeof(*sortByLatency), ng_ppp_intcmp); 1211 compareLatencies = NULL; 1212 1213 /* Find the interval we need (add links in sortByLatency[] order) */ 1214 for (numFragments = 1; 1215 numFragments < priv->numActiveLinks; numFragments++) { 1216 for (total = i = 0; i < numFragments; i++) { 1217 int flowTime; 1218 1219 flowTime = latency[sortByLatency[numFragments]] 1220 - latency[sortByLatency[i]]; 1221 total += ((flowTime * priv->conf.links[ 1222 priv->activeLinks[sortByLatency[i]]].bandwidth) 1223 + 99) / 100; 1224 } 1225 if (total >= len) 1226 break; 1227 } 1228 1229 /* Solve for t_0 in that interval */ 1230 for (topSum = botSum = i = 0; i < numFragments; i++) { 1231 int bw = priv->conf.links[ 1232 priv->activeLinks[sortByLatency[i]]].bandwidth; 1233 1234 topSum += latency[sortByLatency[i]] * bw; /* / 100 */ 1235 botSum += bw; /* / 100 */ 1236 } 1237 t0 = ((len * 100) + topSum + botSum / 2) / botSum; 1238 1239 /* Compute f_i(t_0) all i */ 1240 bzero(distrib, priv->numActiveLinks * sizeof(*distrib)); 1241 for (total = i = 0; i < numFragments; i++) { 1242 int bw = priv->conf.links[ 1243 priv->activeLinks[sortByLatency[i]]].bandwidth; 1244 1245 distrib[sortByLatency[i]] = 1246 (bw * (t0 - latency[sortByLatency[i]]) + 50) / 100; 1247 total += distrib[sortByLatency[i]]; 1248 } 1249 1250 /* Deal with any rounding error */ 1251 if (total < len) { 1252 int fast = 0; 1253 1254 /* Find the fastest link */ 1255 for (i = 1; i < numFragments; i++) { 1256 if (priv->conf.links[ 1257 priv->activeLinks[sortByLatency[i]]].bandwidth > 1258 priv->conf.links[ 1259 priv->activeLinks[sortByLatency[fast]]].bandwidth) 1260 fast = i; 1261 } 1262 distrib[sortByLatency[fast]] += len - total; 1263 } else while (total > len) { 1264 int delta, slow = 0; 1265 1266 /* Find the slowest link that still has bytes to remove */ 1267 for (i = 1; i < numFragments; i++) { 1268 if (distrib[sortByLatency[slow]] == 0 1269 || (distrib[sortByLatency[i]] > 0 1270 && priv->conf.links[priv->activeLinks[ 1271 sortByLatency[i]]].bandwidth < 1272 priv->conf.links[priv->activeLinks[ 1273 sortByLatency[slow]]].bandwidth)) 1274 slow = i; 1275 } 1276 delta = total - len; 1277 if (delta > distrib[sortByLatency[slow]]) 1278 delta = distrib[sortByLatency[slow]]; 1279 distrib[sortByLatency[slow]] -= delta; 1280 total -= delta; 1281 } 1282 } 1283 1284 /* 1285 * Compare two integers 1286 */ 1287 static int 1288 ng_ppp_intcmp(const void *v1, const void *v2) 1289 { 1290 const int index1 = *((const int *) v1); 1291 const int index2 = *((const int *) v2); 1292 1293 return compareLatencies[index1] - compareLatencies[index2]; 1294 } 1295 1296 /* 1297 * Prepend a possibly compressed PPP protocol number in front of a frame 1298 */ 1299 static struct mbuf * 1300 ng_ppp_addproto(struct mbuf *m, int proto, int compOK) 1301 { 1302 int psize = (PROT_COMPRESSABLE(proto) && compOK) ? 1 : 2; 1303 1304 /* Add protocol number */ 1305 M_PREPEND(m, psize, M_NOWAIT); 1306 if (m == NULL || (m->m_len < psize && (m = m_pullup(m, psize)) == NULL)) 1307 return (NULL); 1308 if (psize == 1) 1309 *mtod(m, u_char *) = (u_char)proto; 1310 else 1311 *mtod(m, u_int16_t *) = htons((u_int16_t)proto); 1312 return (m); 1313 } 1314 1315 /* 1316 * Update private information that is derived from other private information 1317 */ 1318 static void 1319 ng_ppp_update(node_p node, int newConf) 1320 { 1321 const priv_p priv = node->private; 1322 int i; 1323 1324 /* Update active status for VJ Compression */ 1325 priv->vjCompHooked = priv->hooks[HOOK_INDEX_VJC_IP] != NULL 1326 && priv->hooks[HOOK_INDEX_VJC_COMP] != NULL 1327 && priv->hooks[HOOK_INDEX_VJC_UNCOMP] != NULL 1328 && priv->hooks[HOOK_INDEX_VJC_VJIP] != NULL; 1329 1330 /* Increase latency for each link an amount equal to one MP header */ 1331 if (newConf) { 1332 for (i = 0; i < NG_PPP_MAX_LINKS; i++) { 1333 int hdrBytes; 1334 1335 hdrBytes = (priv->conf.links[i].enableProtoComp ? 1 : 2) 1336 + (priv->conf.xmitShortSeq ? 2 : 4); 1337 priv->conf.links[i].latency += 1338 ((hdrBytes * priv->conf.links[i].bandwidth) + 50) 1339 / 100; 1340 } 1341 } 1342 1343 /* Update list of active links */ 1344 bzero(&priv->activeLinks, sizeof(priv->activeLinks)); 1345 priv->numActiveLinks = 0; 1346 priv->allLinksEqual = 1; 1347 for (i = 0; i < NG_PPP_MAX_LINKS; i++) { 1348 if (priv->conf.links[i].enableLink && priv->links[i] != NULL) { 1349 priv->activeLinks[priv->numActiveLinks++] = i; 1350 if (priv->conf.links[i].latency 1351 != priv->conf.links[0].latency 1352 || priv->conf.links[i].bandwidth 1353 != priv->conf.links[0].bandwidth) 1354 priv->allLinksEqual = 0; 1355 } 1356 } 1357 1358 /* Reset MP state if no longer active */ 1359 if (!priv->conf.enableMultilink || priv->numActiveLinks == 0) { 1360 ng_ppp_free_frags(node); 1361 priv->mpSeqOut = MP_INITIAL_SEQ; 1362 bzero(&priv->qstat, sizeof(priv->qstat)); 1363 } 1364 } 1365 1366 /* 1367 * Determine if a new configuration would represent a valid change 1368 * from the current configuration and link activity status. 1369 */ 1370 static int 1371 ng_ppp_config_valid(node_p node, const struct ng_ppp_node_config *newConf) 1372 { 1373 const priv_p priv = node->private; 1374 int i, newNumLinksActive; 1375 1376 /* Check per-link config and count how many links would be active */ 1377 for (newNumLinksActive = i = 0; i < NG_PPP_MAX_LINKS; i++) { 1378 if (newConf->links[i].enableLink && priv->links[i] != NULL) 1379 newNumLinksActive++; 1380 if (!newConf->links[i].enableLink) 1381 continue; 1382 if (newConf->links[i].mru < MP_MIN_LINK_MRU) 1383 return (0); 1384 if (newConf->links[i].bandwidth == 0) 1385 return (0); 1386 if (newConf->links[i].bandwidth > NG_PPP_MAX_BANDWIDTH) 1387 return (0); 1388 if (newConf->links[i].latency > NG_PPP_MAX_LATENCY) 1389 return (0); 1390 } 1391 1392 /* Check bundle parameters */ 1393 if (newConf->enableMultilink && newConf->mrru < MP_MIN_MRRU) 1394 return (0); 1395 1396 /* Disallow changes to multi-link configuration while MP is active */ 1397 if (priv->numActiveLinks > 0 && newNumLinksActive > 0) { 1398 if (!priv->conf.enableMultilink != !newConf->enableMultilink 1399 || !priv->conf.xmitShortSeq != !newConf->xmitShortSeq 1400 || !priv->conf.recvShortSeq != !newConf->recvShortSeq) 1401 return (0); 1402 } 1403 1404 /* At most one link can be active unless multi-link is enabled */ 1405 if (!newConf->enableMultilink && newNumLinksActive > 1) 1406 return (0); 1407 1408 /* Configuration change would be valid */ 1409 return (1); 1410 } 1411 1412 /* 1413 * Free all entries in the fragment queue 1414 */ 1415 static void 1416 ng_ppp_free_frags(node_p node) 1417 { 1418 const priv_p priv = node->private; 1419 struct ng_ppp_frag *qent, *next; 1420 1421 for (qent = CIRCLEQ_FIRST(&priv->frags); 1422 qent != (void *) &priv->frags; qent = next) { 1423 next = CIRCLEQ_NEXT(qent, f_qent); 1424 NG_FREE_DATA(qent->data, qent->meta); 1425 FREE(qent, M_NETGRAPH); 1426 } 1427 CIRCLEQ_INIT(&priv->frags); 1428 } 1429 1430