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