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