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