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