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